chickadee » treap » make-treap

make-treap:procedure

where KEY-COMPARE-PROC is a user-supplied function that takes two keys and returns a negative, positive, or zero number depending on how the first key compares to the second.

The returned selector procedure can take one of the following arguments:

'getreturns a procedure LAMBDA KEY . DEFAULT-CLAUSE which searches the treap for an association with a given KEY, and returns a (key . value) pair of the found association. If an association with KEY cannot be located in the treap, the PROC returns the result of evaluating the DEFAULT-CLAUSE. If the default clause is omitted, an error is signalled. KEY must be comparable to the keys in the treap by a key-compare predicate (which has been specified when the treap was created)
'get-minreturns a (key . value) pair for an association in the treap with the smallest key. If the treap is empty, an error is signalled.
'delete-min!removes the min key and the corresponding association from the treap. Returns a (key . value) pair of the removed association. If the treap is empty, an error is signalled.
'get-maxreturns a (key . value) pair for an association in the treap with the largest key. If the treap is empty, an error is signalled.
'delete-max!removes the max key and the corresponding association from the treap. Returns a (key . value) pair of the removed association. If the treap is empty, an error is signalled.
'empty?returns #t if the treap is empty
'sizereturns the size (the number of associations) in the treap
'depthreturns the depth of the tree. It requires the complete traversal of the tree, so use sparingly
'clear!removes all associations from the treap (thus making it empty)
'put!returns a procedure LAMBDA KEY VALUE which, given a KEY and a VALUE, adds the corresponding association to the treap. If an association with the same KEY already exists, its value is replaced with the VALUE (and the old (key . value) association is returned). Otherwise, the return value is #f.
'delete!returns a procedure LAMBDA KEY . DEFAULT-CLAUSE which searches the treap for an association with a given KEY, deletes it, and returns a (key . value) pair of the found and deleted association. If an association with the KEY cannot be located in the treap, the PROC returns the result of evaluating DEFAULT-CLAUSE. If the default clause is omitted, an error is signalled.
'for-each-ascendingreturns a procedure LAMBDA PROC that will apply the given procedure PROC to each (key . value) association of the treap, from the one with the smallest key all the way to the one with the max key, in an ascending order of keys. The treap must not be empty.
'for-each-descendingreturns a procedure LAMBDA PROC that will apply the given procedure PROCto each (key . value) association of the treap, in the descending order of keys. The treap must not be empty.
'debugprintprints out all the nodes in the treap, for debug purposes