Next: Signature
Up: Accompanying material for: A
Previous: Implementation
This section contains an implementation of priority search queues that
uses Adams's weight-balanced trees. It incorporates several small
improvements over the code in the paper.
- Lists have been replaced by John Hughes's efficient sequence
type (in order to vaoid the use of `++').
- The keys and the priorities are stored directly in the nodes
eliminating one level of indirection: we use Winnerkptm
instead of Winner(k:->p)tm (see Remark 2 in the paper).
- The origin of a loser is encoded into the constructor of a
loser tree: we use LLoser and RLoser instead of just Loser
(see Remark 3 in the paper). A slight drawback of this optimization
is that is increases the code size (consider the function balance
and friends).
- The tournament view has been partly eliminated (in ordList,
atMost, and atMostRange).
- We use unsafePlay, that avoids balancing, for fromOrdlist
and adjust.
- Todo: Double rotations are implemented directly rather
than by two single rotations.
Subsections
Next: Signature
Up: Accompanying material for: A
Previous: Implementation
Ralf Hinze
2001-03-20