Version: 5.1.1
5 Skip Lists
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 an ordered dictionary (dict? and
ordered-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 ord to order
keys; in addition, the domain contract of ord is combined
with key-contract to check keys.
Makes a new empty skip-list that permits only exact integers as keys
(in addition to any constraints imposed by
key-contract). The
resulting skip-list answers true to
adjustable-skip-list?
and supports key adjustment.
Returns #t if v is a skip-list, #f
otherwise.
Removes all keys in [from, to); that is, all keys
greater than or equal to from and less than to.
This operation takes time proportional to the number of elements with
keys greater than or equal to to.
Increases the value of all keys greater than or equal to
from
by
(- to from).
This operation takes time proportional to the number of elements with
keys greater than or equal to from.
Returns #t if v represents a position in a
skip-list, #f otherwise.
Returns an association list with the keys and values of
skip-list, in order.