You are looking at historical revision 25405 of this page. It may differ significantly from its current revision.

skiplists

Skiplists are data-types, which can replace balanced search-trees. They are described by Sedgewick. The idea is as follows:

Contrary to listnodes, which are pairs of an item and a next pointer, skipnodes are pairs of an item and a vector of next pointers. The length' of these vectors depend on each skipnode itself, they vary between 1 and a predefind integer, max-links. An alternative to balancing is achieved by some randomization in such a way, that, in the average, the number of nodes with at least k+1 links is half the number of links with at least k links, for k=1,...,max-links. Following the next pointers at a fixed link-level, k say, one skips all nodes with less pointers than k.

Inserting an item into a skiplist now works as follows. First one packages the item into a skipnode, where the number of links is generated in some randomized way.

Second, one follows the skiplist along the highest occupied number of links as long as the skiplist's nodes have items less then the item of the node to be inserted.

Third, one steps down one level and continues following the skiplist's nodes at this new smaller level.

Repeating this process until level 0 is reached we eventually find the place where our new node is to be inserted.

Some additional remarks are in order.

We described the process with a gap of two, i.e. at each level one node of the level below is skipped. Another value than two for the gap is possible as well.

We have to decide, what to do with duplicates. We choose the following approach: The skiplist itself stores a list of either one or several numerical comparison operators. One means, duplicates are not allowed, several means, that the nth operator resolves the remaining duplicates the operators below n.

Documentation

In this implementation skiplists are implemented in the Design by Contract style, i.e. using the contracts module. A corollary of this is, that the documentation is included in the module. By convention, there is a routine with the module's name, skiplists, which when called with no argument

 (skiplists)

shows the exported contract-checked symbols, and called with one of its symbols, e.g.

 (skiplists 'skip-list)

shows the documentation of this symbol in all it's glory, i.e. together with call-structure, docstring, assumptions and propositions.

Note that most contract-checked routines have brethren whith identical signature which are not contract-checked and are not exported. They are prefixed with an % sign and used internally, especially for contract-checking, thus avoiding double-checking.

Another way to get the complete documentation is to use print-doclist from the contracts module. Issuing

 (import skiplists (only contracts print-doclist))
 (with-output-to-file "skiplists.docu" (lambda () (print-doclist)))

you'll get a file skiplists.docu with the following content

dups
----
(dups x y)
trivial numerical comparison operator to allow for duplicates
skip-remove-all!
----------------
(skip-remove-all! skp item)
remove all skipnodes with item from skiplist, if found
(domain (%skiplist? skp))
(effect (count (%skip-count skp) count >=))
skip-remove!
------------
(skip-remove! skp item)
remove skipnode with item from skiplist, if found
(domain (%skiplist? skp))
(effect (count (%skip-count skp) (- count 1) <=))
skip-insert!
------------
(skip-insert! skp item)
insert a new node with item in order
(domain (%skiplist? skp))
(effect (count (%skip-count skp) (+ count 1) (if (skip-dups? skp) = >=)))
skip-found?
-----------
(skip-found? skp item)
check, if last skip-search! was successfull
(domain (%skiplist? skp))
(range (boolean? result))
skip-search!
------------
(skip-search! skp item)
move cursor to a place, where one can look for item
(domain (%skiplist? skp))
(effect (count (%skip-count skp) count =) (links (%skip-links skp) links =))
skip-compare
------------
(skip-compare skp)
combined numerical comparison procedure
(domain (%skiplist? skp))
(range (procedure? result))
skip-dups?
----------
(skip-dups? skp)
check if duplicates are allowed
(domain (%skiplist? skp))
skip-max-links
--------------
(skip-max-links skp)
maximal number of links
(domain (%skiplist? skp))
(range (integer? result) (positive? result))
skip-list
---------
(skip-list skp . ks)
map skiplist to an ordinary list (at link level k, if provided)
(domain (%skiplist? skp) ((list-of? (lambda (k) (and (integer? k) (>= k 0) (< k (%skip-max-links skp))))) ks))
(range (list? result))
skip-for-each
-------------
(skip-for-each skp proc)
apply proc to each item of skiplist
(domain (%skiplist? skp) (procedure? proc))
skip-map
--------
(skip-map skp proc . cmps)
map skiplist with proc using new comparison operators if necessary
(domain (%skiplist? skp) (procedure? proc) ((list-of? procedure?) cmps) new numeric comparison procedures)
(range (%skiplist? result) (<= (%skip-count result) (%skip-count skp)))
skip-restructure
----------------
(skip-restructure skp max-links gap)
restructure skiplist by changing max-links and gap
(domain (integer? max-links) (positive? max-links) (integer? gap) (> gap 1))
(range (%skiplist? result) (= (%skip-max-links result) max-links) (= (%skip-gap result) gap))
make-skiplist-with-gap-from-list
--------------------------------
(make-skiplist-with-gap-from-list lst max-links gap . cmps)
construct a skiplist with gap different from 2 from an ordinary list
(domain (list? lst) list items must be comparable by operators in cmps (integer? max-links) (positive? max-links) (integer? gap) (> gap 1) ((list-of? procedure?) cmps) (not (null? cmps)) numerical valued comparison procedures)
(range (%skiplist? result))
make-skiplist-from-list
-----------------------
(make-skiplist-from-list lst max-links . cmps)
construct a skiplist from an ordinary list
(domain (list? lst) list items must be comparable by operators in cmps (integer? max-links) (positive? max-links) ((list-of? procedure?) cmps) (not (null? cmps)) numerical valued comparison procedures)
(range (%skiplist? result))
make-skiplist-with-gap
----------------------
(make-skiplist-with-gap max-links gap . cmps)
skiplist constructor with gap different from 2
(domain (integer? max-links) (positive? max-links) (integer? gap) (> gap 1) ((list-of? procedure?) cmps) (not (null? cmps)) numerical valued comparison procedures)
(range (%skiplist? result))
make-skiplist
-------------
(make-skiplist max-links . cmps)
skiplist constructor
(domain (integer? max-links) (positive? max-links) ((list-of? procedure?) cmps) (not (null? cmps)) numerical valued comparison procedures)
(range (%skiplist? result))
skip-links
----------
(skip-links skp)
maximal number of occupied links
(domain (%skiplist? skp))
(range (integer? result) (>= (%skip-max-links skp) result 1))
skip-count
----------
(skip-count skp)
number of nodes stored in skiplist
(domain (%skiplist? skp))
(range (integer? result) (>= result 0))
skip-gap
--------
(skip-gap skp)
gap of skiplist
(domain (%skiplist? skp))
(range (integer? result) (> result 1))
skiplist?
---------
(skiplist? xpr)
type predicate

Requirements

contracts records

Last update

Oct 21, 2011

Author

Juergen Lorenz

License

Copyright (c) 2011, Juergen Lorenz
All rights reserved.
Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following
conditions are met:
  Redistributions of source code must retain the above copyright notice, this list of conditions and the following
    disclaimer. 
  Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following
    disclaimer in the documentation and/or other materials provided with the distribution. 
  Neither the name of the author nor the names of its contributors may be used to endorse or promote
    products derived from this software without specific prior written permission. 
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS
OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDERS OR
CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
POSSIBILITY OF SUCH DAMAGE.

Version History

0.1
initial import