▼ |  | Unstable

1 | Guidelines for developing unstable libraries
2 | Bytes
3 | Contracts
4 | Exceptions
5 | Lists
6 | Net
7 | Path
8 | Source Locations
9 | Strings
10 | Structs
11 | Syntax
12 | Anaphoric Contracts
13 | Finding Mutated Variables
14 | Find
15 | Interface-Oriented Programming for Classes
16 | Sequences
17 | Hash Tables
18 | Match
19 | Skip Lists
20 | Interval Maps
21 | GUI libraries

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: 4.2.4
top ← prev up next →

### 19`` Skip Lists

Ryan Culpepper <ryanc@plt-scheme.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 scheme/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?

Implementations of dict-ref, dict-set!, dict-remove!, dict-count, dict-iterate-first, dict-iterate-next, dict-iterate-key, and dict-iterate-value, respectively.

( 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.
top ← prev up next →