<> <> <> <> <> <> DIRECTORY Basics USING [bitsPerWord, BITXOR, BITAND, BITSHIFT, Comparison, LowHalf, HighHalf]; PrioritySearchRef: CEDAR DEFINITIONS IMPORTS Basics = BEGIN Tree: TYPE = REF TreeObject _ NIL; TreeObject: TYPE; Item: TYPE = REF; RadixIndex: TYPE = NAT; equal: RadixIndex = LAST[RadixIndex]; Half: TYPE = {lower, upper}; <> 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 ]; <> <> <> <> <<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]].>> <> 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 ] ]; <> <> <> <> <<>> <> <> TreeHalf: PROC [ value: LONG UNSPECIFIED, i: RadixIndex ] RETURNS [ Half ] = TRUSTED INLINE BEGIN OPEN Basics; RETURN[IF (IF i> TreeHalfImpl: PROC [ LONG UNSPECIFIED, RadixIndex ] RETURNS[ Half ]; PrefixImpl: PROC [ LONG UNSPECIFIED, LONG UNSPECIFIED ] RETURNS[ RadixIndex ]; END. -- ofPrioritySearchRef