Version: 5.0
21 Skip Lists
This library is
unstable;
compatibility will not be maintained.
See
Unstable for more information.
Skip lists are a simple, efficient data structure for mutable
dictionaries with totally ordered keys. They were described in the
paper “Skip Lists: A Probabilistic Alternative to Balanced Trees” by
William Pugh in Communications of the ACM, June 1990, 33(6) pp668-676.
A skip-list is a dictionary (dict? from
racket/dict). It also supports extensions of the
dictionary interface for iterator-based search and mutation.
Makes a new empty skip-list. The skip-list uses =? and <? to order keys.
Returns #t if v is a skip-list, #f
otherwise.
Return the position of, respectively, the greatest key less than
key, the greatest key less than or equal to key, the
least key greater than key, and the least key greater than or
equal to key.
Set the key and value, respectively, at the position iter in
skip-list.
Warning: Changing a position’s key to be less than its
predecessor’s key or greater than its successor’s key results in an
out-of-order skip-list, which may cause comparison-based operations to
behave incorrectly.
Returns #t if v represents a position in a
skip-list, #f otherwise.