# source:project/wiki/eggref/4/skiplists@27159

Last change on this file since 27159 was 27159, checked in by juergen, 9 years ago

kiplists documentation rewritten

File size: 12.1 KB
Line
1[[tags: egg]]
2[[toc:]]
3
4== skiplists
5
6Skiplists are data-types, which can replace balanced search-trees. They are described by Sedgewick. The idea is as follows:
7
8Contrary 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.
9
10Inserting 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.
11
12Second, 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.
13
14Third, one steps down one level and continues following the skiplist's nodes at this new smaller level.
15
16Repeating this process until level 0 is reached we eventually find the place where our new node is to be inserted.
17
18Some additional remarks are in order.
19
20We 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.
21
22We 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.
23
24
25== Documentation
26
27In this implementation skiplists are implemented in the Design by
28Contract style, i.e. using the contracts module. A corollary of this is,
29that the documentation is included in the module in form of procedure with the module's name.
30
31==== skiplists
32
33<procedure>(skiplists [sym])</procedure>
34
35returns all available routines of the module when called without an
36argument, but when called with one of these routines as a symbol,
37returns its contract and documentation string.
38
39Another way to get the complete documentation is to use print-doclist from the contracts module. Issuing
40
41<enscript highlight=scheme>
42  (import skiplists (only contracts print-doclist))
43  (with-output-to-file "skiplists.docu" (lambda () (print-doclist)))
44</enscript>
45
46you'll get a file skiplists.docu, which is the basis of the following documentation
47
48==== dups
49
50<procedure>(dups x y)</procedure>
51
52trivial numerical comparison operator to allow for duplicates
53
54==== skip-remove-all!
55
56<procedure>(skip-remove-all! skp . items)</procedure>
57
58<enscript highlight=scheme>
59(domain (%skiplist? skp))
60(effect (count (%skip-count skp) count >=))
61</enscript>
62
63remove nodes (all per found item) with items from skiplist
64
65==== skip-remove!
66
67<procedure>(skip-remove! skp . items)</procedure>
68
69<enscript highlight=scheme>
70(domain (%skiplist? skp))
71(effect (count (%skip-count skp) (- count (length items)) <=))
72</enscript>
73
74remove nodes (one per found item) with items from skiplist
75
76==== skip-insert!
77
78<procedure>(skip-insert! skp . items)</procedure>
79
80<enscript highlight=scheme>
81(domain (%skiplist? skp))
82(effect (count (%skip-count skp) (+ count (length items)) (if (skip-dups? skp) = >=)))
83</enscript>
84
85insert new nodes with items into skiplist
86
87==== skip-found?
88
89<procedure>(skip-found? skp item)</procedure>
90
91<enscript highlight=scheme>
92(domain (%skiplist? skp))
93(range (boolean? result))
94</enscript>
95
96check, if last skip-search! was successfull
97
98==== skip-search!
99
100<procedure>(skip-search! skp item)</procedure>
101
102<enscript highlight=scheme>
103(domain (%skiplist? skp))
104(effect (count (%skip-count skp) count =) (links (%skip-links skp) links =))
105</enscript>
106
107move cursor to a place, where one can look for item
108
109==== skip-compare
110
111<procedure>(skip-compare skp)</procedure>
112
113<enscript highlight=scheme>
114(domain (%skiplist? skp))
115(range (procedure? result))
116</enscript>
117
118combined numerical comparison procedure
119
120==== skip-dups?
121
122<procedure>(skip-dups? skp)</procedure>
123
124<enscript highlight=scheme>
125(domain (%skiplist? skp))
126</enscript>
127
128check if duplicates are allowed
129
130==== skip-max-links
131
132<procedure>(skip-max-links skp)</procedure>
133
134<enscript highlight=scheme>
135(domain (%skiplist? skp))
136(range (integer? result) (positive? result))
137</enscript>
138
139maximal number of links
140
141==== skip-orders
142
143<procedure>(skip-orders skp)</procedure>
144
145<enscript highlight=scheme>
146(domain (%skiplist? skp))
147(range ((list-of? procedure?) result))
148</enscript>
149
150list of numerical comparison operators
151
152==== skip-list
153
154<procedure>(skip-list skp . ks)</procedure>
155
156<enscript highlight=scheme>
157(domain (%skiplist? skp)
158        ((list-of? (lambda (k)
159                     (and (integer? k) (>= k 0) (< k (%skip-max-links skp)))))
160         ks))
161(range (list? result))
162</enscript>
163
164map skiplist to an ordinary list (at link level k, if provided)
165
166==== skip-for-each
167
168<procedure>(skip-for-each skp proc)</procedure>
169
170<enscript highlight=scheme>
171(domain (%skiplist? skp) (procedure? proc))
172</enscript>
173
174apply proc to each item of skiplist
175
176==== skip-restructure
177
178<procedure>(skip-restructure skp max-links gap)</procedure>
179
180<enscript highlight=scheme>
181(domain (integer? max-links) (positive? max-links) (integer? gap) (> gap 1))
182(range (%skiplist? result)
183       (= (%skip-max-links result) max-links)
184       (= (%skip-gap result) gap))
185</enscript>
186
187restructure skiplist by changing max-links and gap
188
189==== skip-reorder
190
191<procedure>(skip-reorder skp . orders)</procedure>
192
193<enscript highlight=scheme>
194(domain (%skiplist? skp)
195        ((list-of? procedure?) orders)
196        (set-in? orders (%skip-orders skp))
197        (set-in? (%skip-orders skp) orders))
198(range (%skiplist? result)
199       (= (%skip-count result) (%skip-count skp)))
200</enscript>
201
202reorder skiplist by changing the order of comparison operators
203
204==== skip-filter
205
206<procedure>(skip-filter skp ok?)</procedure>
207
208<enscript highlight=scheme>
209(domain (%skiplist? skp)
210        (procedure? ok?)
211        one argument predicate)
212(range (%skiplist? result))
213</enscript>
214
215filter a skiplist according to predicate ok?
216
217==== make-skiplist-with-gap-from-list
218
219<procedure>(make-skiplist-with-gap-from-list lst max-links gap .  cmps)</procedure>
220
221<enscript highlight=scheme>
222(domain (list? lst)
223        list items must be comparable by operators in cmps
224        (integer? max-links) (positive? max-links)
225        (integer? gap) (> gap 1)
226        ((list-of? procedure?) cmps) (not (null? cmps))
227        numerical valued comparison procedures)
228(range (%skiplist? result))
229</enscript>
230
231construct a skiplist with gap different from 2 from an ordinary list
232
233==== make-skiplist-from-list
234
235<procedure>(make-skiplist-from-list lst max-links . cmps)</procedure>
236
237<enscript highlight=scheme>
238(domain (list? lst)
239        list items must be comparable by operators in cmps
240        (integer? max-links) (positive? max-links)
241        ((list-of? procedure?) cmps) (not (null? cmps))
242        numerical valued comparison procedures)
243(range (%skiplist? result))
244</enscript>
245
246construct a skiplist from an ordinary list
247
248==== make-skiplist-with-gap
249
250<procedure>(make-skiplist-with-gap max-links gap . cmps)</procedure>
251
252<enscript highlight=scheme>
253(domain (integer? max-links) (positive? max-links)
254        (integer? gap) (> gap 1)
255        ((list-of? procedure?) cmps) (not (null? cmps))
256        numerical valued comparison procedures)
257(range (%skiplist? result))
258</enscript>
259
260skiplist constructor with gap different from 2
261
262==== make-skiplist
263
264<procedure>(make-skiplist max-links . cmps)</procedure>
265
266<enscript highlight=scheme>
267(domain (integer? max-links) (positive? max-links)
268        ((list-of? procedure?) cmps) (not (null? cmps))
269        numerical valued comparison procedures)
270(range (%skiplist? result))
271</enscript>
272
273skiplist constructor
274
275==== skip-links
276
277<procedure>(skip-links skp)</procedure>
278
279<enscript highlight=scheme>
280(domain (%skiplist? skp))
281(range (integer? result) (>= (%skip-max-links skp) result 1))
282</enscript>
283
284maximal number of occupied links
285
286==== skip-count
287
288<procedure>(skip-count skp)</procedure>
289
290<enscript highlight=scheme>
291(domain (%skiplist? skp))
292(range (integer? result) (>= result 0))
293</enscript>
294
295number of nodes stored in skiplist
296
297==== skip-gap
298
299<procedure>(skip-gap skp)</procedure>
300
301<enscript highlight=scheme>
302(domain (%skiplist? skp))
303(range (integer? result) (> result 1))
304</enscript>
305
306gap of skiplist
307
308==== skiplist?
309
310<procedure>(skiplist? xpr)</procedure>
311
312type predicate
313
314== Examples
315
316<enscript highlight=scheme>
317
318  (use skiplists)
319
320  ;;; build a list of length n of random numbers between 0 and n
321  (define (random-list n)
322    (let loop ((acc '()) (k n))
323      (if (zero? k)
324        acc
325        (loop (cons (random n) acc) (- k 1)))))
326
327  ;;; build the list of cardinals less than n
328  (define (enum n)
329    (let loop ((acc '()) (k (- n 1)))
330      (if (negative? k)
331        acc
332        (loop (cons k acc) (- k 1)))))
333
334  (define lst (random-list 60))
335
336  (define dlst (map (lambda (x) (list x (car (random-list 5)))) lst))
337
338  ;; make skiplist from already sorted list
339  (define ord (make-skiplist-with-gap-from-list (enum 60) 5 3 -))
340
341  ;; make skiplist from random list
342  (define skp (make-skiplist-from-list lst 5 -)) ; without dups
343
344  ;; make skiplist with dups from random list
345  (define skp* (make-skiplist-from-list lst 5 - dups)) ; with dups
346
347  ;; make skiplist with dups from list of pairs
348(define skp12 (make-skiplist-from-list dlst 5
349                                      (lambda (x y) (- (car x) (car y)))
350                                      (lambda (x y) (- (cadr x) (cadr y)))))
351(define skp21 (apply skip-reorder skp12 (reverse (skip-orders skp12))))
352(define flt (skip-filter skp* even?))
353
354
355  ;; print list from skiplist as well as its sublists at each level
356  (let loop ((k 0))
357    (unless (= k (skip-links skp*))
358      (print (skip-list skp* k))
359      (loop (+ k 1))))
360
361  ;; insert enumerated list into list without dups
362  (apply skip-insert! skp (enum 60))
363
364  ;; check if skp* is ordered
365  (apply <= (skip-list skp*))
366
367  ;; check if car of skp12 is ordered
368  (apply <= (map car (skip-list skp12)))
369
370  ;; check if cadr of skp21 is ordered
371  (apply <= (map cadr (skip-list skp21)))
372
373  ;; check if flt has only even members
374  (not (memq #f (map even? (skip-list flt))))
375
376</enscript>
377
378== Requirements
379
380[[contracts]]
381[[records]]
382
383== Last update
384
385May 18, 2012
386
387== Author
388
389[[/users/juergen-lorenz|Juergen Lorenz]]
390
391== License
392
393 Copyright (c) 2011, Juergen Lorenz
394 All rights reserved.
395
396 Redistribution and use in source and binary forms, with or without
397 modification, are permitted provided that the following conditions are
398 met:
399
400 Redistributions of source code must retain the above copyright
401 notice, this list of conditions and the following disclaimer.
402
403 Redistributions in binary form must reproduce the above copyright
404 notice, this list of conditions and the following disclaimer in the
405 documentation and/or other materials provided with the distribution.
406 Neither the name of the author nor the names of its contributors may be
407 used to endorse or promote products derived from this software without
408 specific prior written permission.
409
410 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
411 IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
412 TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
413 PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
414 HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
415 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
416 TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
417 PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
418 LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
419 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
420 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
421
422== Version History
423
424; 0.4 : assert call corrected
425; 0.3 : added skip-orders, skip-reorder, skip-filter
426; 0.2 : skip-map removed, skip-insert!, skip-remove! and skip-remove-all! now accept multiple item arguments
427; 0.1 : initial import
Note: See TracBrowser for help on using the repository browser.