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

• egg

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 in form of procedure with the module's name.

skiplists

[procedure] (skiplists [sym])

returns all available routines of the module when called without an argument, but when called with one of these routines as a symbol, returns its contract and documentation string.

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, which is the basis of the following documentation

dups

[procedure] (dups x y)

trivial numerical comparison operator to allow for duplicates

skip-remove-all!

[procedure] (skip-remove-all! skp . items)

(domain (%skiplist? skp))
(effect (count (%skip-count skp) count >=))

remove nodes (all per found item) with items from skiplist

skip-remove!

[procedure] (skip-remove! skp . items)

(domain (%skiplist? skp))
(effect (count (%skip-count skp) (- count (length items)) <=))

remove nodes (one per found item) with items from skiplist

skip-insert!

[procedure] (skip-insert! skp . items)

(domain (%skiplist? skp))
(effect (count (%skip-count skp) (+ count (length items)) (if (skip-dups? skp) = >=)))

insert new nodes with items into skiplist

skip-found?

[procedure] (skip-found? skp item)

(domain (%skiplist? skp))
(range (boolean? result))

check, if last skip-search! was successfull

skip-search!

[procedure] (skip-search! skp item)

(domain (%skiplist? skp))
(effect (count (%skip-count skp) count =) (links (%skip-links skp) links =))

move cursor to a place, where one can look for item

skip-compare

[procedure] (skip-compare skp)

(domain (%skiplist? skp))
(range (procedure? result))

combined numerical comparison procedure

skip-dups?

[procedure] (skip-dups? skp)

(domain (%skiplist? skp))

check if duplicates are allowed

skip-max-links

[procedure] (skip-max-links skp)

(domain (%skiplist? skp))
(range (integer? result) (positive? result))

maximal number of links

skip-orders

[procedure] (skip-orders skp)

(domain (%skiplist? skp))
(range ((list-of? procedure?) result))

list of numerical comparison operators

skip-list

[procedure] (skip-list skp . ks)

(domain (%skiplist? skp)
        ((list-of? (lambda (k)
                     (and (integer? k) (>= k 0) (< k (%skip-max-links skp)))))
         ks))
(range (list? result))

map skiplist to an ordinary list (at link level k, if provided)

skip-for-each

[procedure] (skip-for-each skp proc)

(domain (%skiplist? skp) (procedure? proc))

apply proc to each item of skiplist

skip-restructure

[procedure] (skip-restructure skp max-links 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))

restructure skiplist by changing max-links and gap

skip-reorder

[procedure] (skip-reorder skp . orders)

(domain (%skiplist? skp)
        ((list-of? procedure?) orders)
        (set-in? orders (%skip-orders skp))
        (set-in? (%skip-orders skp) orders))
(range (%skiplist? result)
       (= (%skip-count result) (%skip-count skp)))

reorder skiplist by changing the order of comparison operators

skip-filter

[procedure] (skip-filter skp ok?)

(domain (%skiplist? skp)
        (procedure? ok?)
        one argument predicate)
(range (%skiplist? result))

filter a skiplist according to predicate ok?

make-skiplist-with-gap-from-list

[procedure] (make-skiplist-with-gap-from-list lst max-links gap . cmps)

(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))

construct a skiplist with gap different from 2 from an ordinary list

make-skiplist-from-list

[procedure] (make-skiplist-from-list lst max-links . cmps)

(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))

construct a skiplist from an ordinary list

make-skiplist-with-gap

[procedure] (make-skiplist-with-gap max-links gap . cmps)

(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))

skiplist constructor with gap different from 2

make-skiplist

[procedure] (make-skiplist max-links . cmps)

(domain (integer? max-links) (positive? max-links)
        ((list-of? procedure?) cmps) (not (null? cmps))
        numerical valued comparison procedures)
(range (%skiplist? result))

skiplist constructor

skip-links

[procedure] (skip-links skp)

(domain (%skiplist? skp))
(range (integer? result) (>= (%skip-max-links skp) result 1))

maximal number of occupied links

skip-count

[procedure] (skip-count skp)

(domain (%skiplist? skp))
(range (integer? result) (>= result 0))

number of nodes stored in skiplist

skip-gap

[procedure] (skip-gap skp)

(domain (%skiplist? skp))
(range (integer? result) (> result 1))

gap of skiplist

skiplist?

[procedure] (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 skp12 (make-skiplist-from-list dlst 5
                                      (lambda (x y) (- (car x) (car y)))
                                      (lambda (x y) (- (cadr x) (cadr y)))))
(define skp21 (apply skip-reorder skp12 (reverse (skip-orders skp12))))
(define flt (skip-filter skp* even?))


  ;; 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 skp12 is ordered
  (apply <= (map car (skip-list skp12)))

  ;; check if cadr of skp21 is ordered
  (apply <= (map cadr (skip-list skp21)))

  ;; check if flt has only even members
  (not (memq #f (map even? (skip-list flt))))

Requirements

contracts records

Last update

May 18, 2012

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.4

assert call corrected

0.3

added skip-orders, skip-reorder, skip-filter

0.2

skip-map removed, skip-insert!, skip-remove! and skip-remove-all! now accept multiple item arguments

0.1

initial import