## Skiplists

Skiplists are data-types, which can replace balanced search-trees. They are invented by Pugh. 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 are choosen randomly in such a way, that, in the average, the number of nodes with at least k links is half the number of links with at least k-1 links, for k>1. Following the next pointers at a fixed link-level, k say, one skips all nodes with less than k pointers.

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 randomly as described above. Second, one follows the skiplist along the highest occupied number of links as long as the skiplist's nodes point to 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 width of two, i.e. at each level in the average one node of the level below is skipped. A higher value than two for the width is possible as well, trading performance against space.

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. Only if the last of those operators is the special comparison operator dups (which returns constantly 0, i.e. it compares nothing) duplicates are allowed. Moreover, we arrage matters in such a way, that all nodes of duplicates with the same key have the same height, so that a search for the item which was inserted last will be found first.

### Documentation

In this implementation skiplists are implemented in two modules, %skiplists and skiplists. They both have the same interface. The former implements all routines without any checks, the latter imports the former with routines prefixed with % and calling those routines with checked arguments. This way you can trade security against speed ...

#### skiplists

<procedure>(skiplists) <procedure>(skiplists sym)

documentation procedure. The first call shows the list of exported symbols, the second documentation of symbol sym.

#### skiplist

*[procedure]*

`(skiplist width max-height item? order . orders)`

*[procedure]*

`(skiplist max-height item? order . orders)`

*[procedure]*

`(skiplist item? order . orders))`

constructors: width is the jump width, max-height the maximum allowed length of pointers of an item, item? checks

#### skiplist?

*[procedure]*

`(skiplist? xpr)`

type predicate.

#### skiplist->list

*[procedure]*

`(skiplist->list sls)`

*[procedure]*

`(skiplist->list sls level)`

the list of items stored in each level

#### sl-null?

*[procedure]*

`(sl-null? sls)`

is skiplist empty?

#### sl-dups?

*[procedure]*

`(sl-dups? sls)`

are duplicates allowed?

#### sl-item?

*[procedure]*

`(sl-item? sls)`

item type predicate

#### dups

*[procedure]*

`(dups x y)`

trivial numerical comparison operator to be used as last order to allow duplicates.

transformer.

#### sl-compare

*[procedure]*

`(sl-compare sls)`

combined comparison function

#### sl-count

*[procedure]*

`(sl-count sls)`

number of items stored in skiplist

#### sl-found

*[procedure]*

`(sl-found sls)`

list of found items, to be called after search!

#### sl-found?

*[procedure]*

`(sl-found? sls item)`

is item found?

#### sl-height

*[procedure]*

`(sl-height sls)`

actual maximal height of nodes (can be changed)

#### sl-max-height

*[procedure]*

`(sl-max-height sls)`

absolute maximum heigth of nodes in skiplist (not changeble)

#### sl-max

*[procedure]*

`(sl-max sls)`

biggest item stored in skiplist

#### sl-min

*[procedure]*

`(sl-min sls)`

smallest item stored in skiplist

#### sl-orders

*[procedure]*

`(sl-orders sls)`

list of orders defined in the constructor

#### sl-search-level

*[procedure]*

`(sl-search-level sls)`

down to which level a previous search descended?

#### sl-width

*[procedure]*

`(sl-width sls)`

width skipped on average at each search level supplied by constructor

#### sl-map

*[procedure]*

`(sl-map fn sls)`

*[procedure]*

`(sl-map fn sls order . orders)`

*[procedure]*

`(sl-map fn sls width)`

*[procedure]*

`(sl-map fn sls width order . orders)`

depending on the mapping function, different order procedures might be necessary

#### sl-for-each

*[procedure]*

`(sl-for-each proc sls)`

apply proc to each item in skiplist

#### sl-filter

*[procedure]*

`(sl-filter ok? sls)`

filtering

#### sl-reorder

*[procedure]*

`(sl-reorder sls order . orders)`

changing orders

#### sl-restructure

*[procedure]*

`(sl-restructure sls width max-height)`

changing width

#### sl-insert!

*[procedure]*

`(sl-insert! sls item . items)`

insert items into skiplist

#### sl-remove!

*[procedure]*

`(sl-remove! sls item . items)`

remove items from skiplist

#### sl-search!

*[procedure]*

`(sl-search! sls item)`

searching for an item changes internal cursor transparently

#### sl-clear!

*[procedure]*

`(sl-clear! sls)`

reset skiplist

### Examples

(import skiplists) A skiplist with primary and secondary search order, allowing duplicates ;; some constructors (definesls1 (skiplist 15 fixnum? -)) (sl-width sls1) ;-> 2 (sl-max-height sls1) ;-> 15 (sl-dups? sls1) ;-> #f (definesls2 (skiplist 4 20 fixnum? - dups)) (fx= (sl-width sls2) ;-> 4 (fx= (sl-max-height sls2) ;-> 20 (sl-dups? sls2) ;-> #t ;; create ... (defineitem-type (lambda(x) (and ((list-of? integer?) x) (> (length x) 2)))) (defineprimary-order (lambda(x y) (- (car x) (car y)))) (definesecondary-order (lambda(x y) (- (cadr x) (cadr y)))) (definesls3 (skiplist 3 15 item-type primary-order secondary-order dups)) ;; and populate ... (definelst1 (letloop((k 0) (lst '())) (if(= k 100) lst (loop(+ k 1) (cons (pseudo-random-integer 10) lst))))) (definelst2 (letloop((k 0) (lst '())) (if(= k 100) lst (loop(+ k 1) (cons (pseudo-random-integer 10) lst))))) (definelst3 (letloop((k 0) (lst '())) (if(= k 100) lst (loop(+ k 1) (cons (pseudo-random-integer 100) lst))))) (apply sl-insert! sls3 (map (lambda(x y z) (list x y z)) lst1 lst2 lst3)) (sl-count sls3) ;-> 100 (sl-width sls3) ;-> 3 ;; inserting item and removing all with same key ... ((sl-item? sls3) '(1 2 3)) ;-> #t (sl-search! sls3 '(1 2 3)) (if(sl-found? sls3 '(1 2 3)) (apply sl-remove! sls3 (sl-found sls3))) (sl-insert! sls3 '(1 2 3)) (sl-search! sls3 '(1 2 3)) (member '(1 2 3) (sl-found sls3)) (apply sl-remove! sls3 (sl-found sls3)) (sl-search! sls3 '(1 2 3)) (null? (sl-found sls3)) ;; produce duplicates at the ends ... (sl-insert! sls3 '(-1 2 3) '(-1 2 3 4)) (sl-min sls3) ;-> '((-1 2 3 4) (-1 2 3)) (sl-insert! sls3 '(10 1 2) '(10 1 2 3) '(10 1 3)) (sl-found sls3) ;-> '((10 1 3) (10 1 2 3) (10 1 2)) (sl-max sls3) ;-> '((10 1 3) (10 1 2 3) (10 1 2)) ;; and remove them again ... (sl-search! sls3 '(-1 2 3 4)) (apply sl-remove! sls3 (sl-found sls3)) (sl-search! sls3 '(-1 2 3 4)) (null? (sl-found sls3)) ;-> #t (sl-search! sls3 '(10 1 3)) (apply sl-remove! sls3 (sl-found sls3)) (null? (sl-found sls3)) ;-> #t ;; reorder removing all dups ... (apply <= (map car (skiplist->list (sl-reorder sls3 primary-order secondary-order)))) (<= (sl-count (sl-reorder sls3 primary-order secondary-order)) (sl-count sls3)) reorder using only secondary order ... (apply < (map cadr (skiplist->list (sl-reorder sls3 secondary-order)))) (>= 10 (sl-count (sl-reorder sls3 secondary-order))) ;; restructure ... (equal? (skiplist->list sls3) (skiplist->list (sl-restructure sls3 2 10))) ;; filter ... ((list-of? odd?) (map caddr (skiplist->list (sl-filter sls3 (lambda(x) (odd? (caddr x))))))) ;; map ... (let((fn (lambda(x) (* 2 x)))) (equal? (map fn (skiplist->list sls3)) (skiplist->list (sl-map sls3 fn))))

### Requirements

none

### Last update

Mar 25, 2019

## Author

## License

Copyright (c) 2012-2019, 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

- 1.0
- port from chicken-4