DIRECTORY
Basics USING [bitsPerWord, BITXOR, BITAND, BITSHIFT, Comparison, LowHalf, HighHalf];
Tree: TYPE = REF TreeObject ← NIL;
TreeObject: TYPE;
Item: TYPE = REF;
RadixIndex: TYPE = NAT;
equal: RadixIndex = LAST[RadixIndex];
Half: TYPE = {lower, upper};
Priority search trees are a one-and-a-half-dimensional search structure discovered by your humble servant and described in the SIAM Journal on Computing, volume 14, number 2, (May, 1985), pp 257-276. This module implements the simpler radix form of priority search trees, and uses Cedar's runtime type machinery to maintain trees containing different types of items.
Create:
PROC [ prefix:
PROC[ Item, Item ]
RETURNS [ RadixIndex ],
treeHalf: PROC [ Item, RadixIndex ] RETURNS [ Half ],
depth: PROC [ Item, Item ] RETURNS [ Basics.Comparison ],
nodeZone, treeZone: ZONE ← NIL ] RETURNS [ Tree ];
Correct operation requires that
a) depth is a total order on equivalence classes of Items.
b) treeHalf and prefix together determine a total order on items; that is,
for any distinct items i1 and i2,
1) for all j IN [0..prefix[i1, i2]), treeHalf[i1, j] = treeHalf[i2, j], and
2) treeHalf[i1, prefix[i1, i2]] # treeHalf[i2, prefix[i1, i2]].
Note that these two total orders are independent. (In fact, if they were the same, a different data structure, like red-black trees, would probably be more appropriate to use.)
Destroy: PROC [ Tree ] RETURNS [ Tree ];
Size: PROC[ Tree ] RETURNS[ INT ];
Insert: PROC [ Tree, Item ] RETURNS [ rejectedDuplicate: BOOL ];
Delete:
PROC [ Tree, Item ];
CouldntDelete: ERROR;
Check:
PROC [ Tree,
UNSAFE
PROC[ Item ] ←
NIL ];
Malformed: ERROR;
Search:
PROC [ tree: Tree, deepestItem, lowermostItem, uppermostItem: Item, touch:
UNSAFE
PROC [ Item ] ];
enumerates in arbitrary order those items i in the tree such that
a) depth[i, deepestItem]#greater, and
b) treeHalf[i, prefix[lowermostItem, i]]=upper
c) treeHalf[i, prefix[uppermostItem, i]]=lower
The following subroutines are frequently useful for computing all or part of the
prefix and treeHalf functions required by Create.
TreeHalf:
PROC [ value:
LONG
UNSPECIFIED, i: RadixIndex ]
RETURNS [ Half ] =
TRUSTED INLINE BEGIN
OPEN Basics;
RETURN[
IF (
IF i<bitsPerWord
THEN
BITAND[
BITSHIFT[HighHalf[value], i], 08000h]
ELSE BITAND[BITSHIFT[LowHalf[value], i-bitsPerWord], 08000h])#0 THEN upper ELSE lower];
END; -- of TreeHalf
Prefix:
PROC [ a:
LONG
UNSPECIFIED, b:
LONG
UNSPECIFIED ]
RETURNS[ RadixIndex ] =
TRUSTED INLINE BEGIN
OPEN Basics;
r: RadixIndex;
t: WORD;
dif: WORD ← BITXOR[HighHalf[a], HighHalf[b]];
IF dif=0
THEN
BEGIN
r ← bitsPerWord;
dif ← BITXOR[LowHalf[a], LowHalf[b]];
IF dif=0 THEN RETURN[2*bitsPerWord];
END
ELSE r ← 0;
IF (t ← BITAND[dif, 0ff00h])=0 THEN r ← r+8 ELSE dif ← t;
IF (t ← BITAND[dif, 0f0f0h])=0 THEN r ← r+4 ELSE dif ← t;
IF (t ← BITAND[dif, 0cccch])=0 THEN r ← r+2 ELSE dif ← t;
IF BITAND[dif, 0aaaah]=0 THEN r ← r+1;
RETURN[r];
END; -- of Prefix
The following two non-inline procedures are implemented exactly as specified above, but alas the ones above cannot be passed as parameters.
TreeHalfImpl: PROC [ LONG UNSPECIFIED, RadixIndex ] RETURNS[ Half ];
PrefixImpl: PROC [ LONG UNSPECIFIED, LONG UNSPECIFIED ] RETURNS[ RadixIndex ];
END. -- ofPrioritySearchRef