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

- skiplists
- Documentation
- skiplists
- dups
- skip-remove-all!
- skip-remove!
- skip-insert!
- skip-found?
- skip-search!
- skip-compare
- skip-dups?
- skip-max-links
- skip-orders
- skip-list
- skip-for-each
- skip-restructure
- skip-reorder
- skip-filter
- make-skiplist-with-gap-from-list
- make-skiplist-from-list
- make-skiplist-with-gap
- make-skiplist
- skip-links
- skip-count
- skip-gap
- skiplist?

- Examples
- Requirements
- Last update
- Author
- License
- Version History

## 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 one of the two modules in form of a procedure with the module's name. Apart from this documentation procedure the two modules, %skiplists and skiplists, have the same interface. The first module contains the raw implementations of the procedures, the second imports the first with prefix % and wraps those prefixed routines with contracts.

#### 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) (letloop((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) (letloop((acc '()) (k (- n 1))) (if(negative? k) acc (loop(cons k acc) (- k 1))))) (definelst (random-list 60)) (definedlst (map (lambda(x) (list x (car (random-list 5)))) lst)) ;; make skiplist from already sorted list (defineord (make-skiplist-with-gap-from-list (enum 60) 5 3 -)) ;; make skiplist from random list (defineskp (make-skiplist-from-list lst 5 -)) ; without dups ;; make skiplist with dups from random list (defineskp* (make-skiplist-from-list lst 5 - dups)) ; with dups ;; make skiplist with dups from list of pairs (defineskp12 (make-skiplist-from-list dlst 5 (lambda(x y) (- (car x) (car y))) (lambda(x y) (- (cadr x) (cadr y))))) (defineskp21 (apply skip-reorder skp12 (reverse (skip-orders skp12)))) (defineflt (skip-filter skp* even?)) ;; print list from skiplist as well as its sublists at each level (letloop((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

## Last update

Aug 3, 2012

## Author

## License

Copyright (c) 2012, 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.7
- dependency on records removed, define-record-type and define-record-printer used instead
- 0.6
- code restructured into two modules
- 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