You are looking at historical revision 25449 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 . items)
remove nodes (all per found item) with items from skiplist
(domain (%skiplist? skp))
(effect (count (%skip-count skp) count >=))
skip-remove!
------------
(skip-remove! skp . items)
remove nodes (one per found item) with items from skiplist
(domain (%skiplist? skp))
(effect (count (%skip-count skp) (- count (length items)) <=))
skip-insert!
------------
(skip-insert! skp . items)
insert new nodes with items into skiplist
(domain (%skiplist? skp))
(effect (count (%skip-count skp) (+ count (length items)) (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-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

Examples

(use skiplists)
;;; build a list of length n of random numbers between 0 and n
(define (random-list n)
	(let loop ((acc '()) (k n))
		(if (zero? k)
			acc
			(loop (cons (random n) acc) (- k 1)))))
;;; build the list of cardinals less than n
(define (enum n)
	(let loop ((acc '()) (k (- n 1)))
		(if (negative? k)
			acc
			(loop (cons k acc) (- k 1)))))
(define lst (random-list 60))
(define dlst (map (lambda (x) (list x (car (random-list 5)))) lst))
;; make skiplist from already sorted list
(define ord (make-skiplist-with-gap-from-list (enum 60) 5 3 -))
;; make skiplist from random list
(define skp (make-skiplist-from-list lst 5 -)) ; without dups
;; make skiplist with dups from random list
(define skp* (make-skiplist-from-list lst 5 - dups)) ; with dups
;; make skiplist with dups from list of pairs
(define skp2 (make-skiplist-from-list dlst 5
																			(lambda (x y) (- (car x) (car y)))
																			(lambda (x y) (- (cadr x) (cadr y)))))
;; print list from skiplist as well as its sublists at each level
(let loop ((k 0))
	(unless (= k (skip-links skp*))
		(print (skip-list skp* k))
		(loop (+ k 1))))
;; insert enumerated list into list without dups
(apply skip-insert! skp (enum 60))
;; check if skp* is ordered
(apply <= (skip-list skp*))
;; check if car of skp2 is ordered
(apply <= (map car (skip-list skp2)))

Requirements

contracts records

Last update

Oct 27, 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.2
skip-map removed, skip-insert!, skip-remove! and skip-remove-all! now accept multiple item arguments
0.1
initial import