On this page:
make-skip-list
skip-list?
skip-list-ref
skip-list-set!
skip-list-remove!
skip-list-count
skip-list-iterate-first
skip-list-iterate-next
skip-list-iterate-key
skip-list-iterate-value
skip-list-iterate-greatest/ <?
skip-list-iterate-greatest/ <=?
skip-list-iterate-least/ >?
skip-list-iterate-least/ >=?
skip-list-iterate-set-key!
skip-list-iterate-set-value!
skip-list-iter?
Version: 5.0

21 Skip Lists

Ryan Culpepper <ryanc@racket-lang.org>

 (require unstable/skip-list)

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.

(make-skip-list =? <?)  skip-list?
  =? : (any/c any/c . -> . any/c)
  <? : (any/c any/c . -> . any/c)
Makes a new empty skip-list. The skip-list uses =? and <? to order keys.

Examples:

  > (define skip-list (make-skip-list = <))
  > (skip-list-set! skip-list 3 'apple)
  > (skip-list-set! skip-list 6 'cherry)
  > (dict-map skip-list list)

  '((3 apple) (6 cherry))

  > (skip-list-ref skip-list 3)

  'apple

  > (skip-list-remove! skip-list 6)
  > (skip-list-count skip-list)

  1

(skip-list? v)  boolean?
  v : any/c
Returns #t if v is a skip-list, #f otherwise.

(skip-list-ref skip-list key [default])  any/c
  skip-list : skip-list?
  key : any/c
  default : any/c = (lambda () (error ....))
(skip-list-set! skip-list key value)  void?
  skip-list : skip-list?
  key : any/c
  value : any/c
(skip-list-remove! skip-list key)  void?
  skip-list : skip-list?
  key : any/c
(skip-list-count skip-list)  exact-nonnegative-integer?
  skip-list : skip-list?
(skip-list-iterate-first skip-list)  (or/c skip-list-iter? #f)
  skip-list : skip-list?
(skip-list-iterate-next skip-list iter)
  (or/c skip-list-iter? #f)
  skip-list : skip-list?
  iter : skip-list-iter?
(skip-list-iterate-key skip-list iter)  any/c
  skip-list : skip-list?
  iter : skip-list-iter?
(skip-list-iterate-value skip-list iter)  any/c
  skip-list : skip-list?
  iter : skip-list-iter?

(skip-list-iterate-greatest/<? skip-list 
  key) 
  (or/c skip-list-iter? #f)
  skip-list : skip-list?
  key : any/c
(skip-list-iterate-greatest/<=? skip-list 
  key) 
  (or/c skip-list-iter? #f)
  skip-list : skip-list?
  key : any/c
(skip-list-iterate-least/>? skip-list key)
  (or/c skip-list-iter? #f)
  skip-list : skip-list?
  key : any/c
(skip-list-iterate-least/>=? skip-list key)
  (or/c skip-list-iter? #f)
  skip-list : skip-list?
  key : any/c
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.

(skip-list-iterate-set-key! skip-list    
  iter    
  key)  void?
  skip-list : skip-list?
  iter : skip-list-iter?
  key : any/c
(skip-list-iterate-set-value! skip-list    
  iter    
  value)  void?
  skip-list : skip-list?
  iter : skip-list-iter?
  value : any/c
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.

(skip-list-iter? v)  boolean?
  v : any/c
Returns #t if v represents a position in a skip-list, #f otherwise.