source: project/wiki/eggref/4/skiplists @ 27162

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

version 0.6 of skiplists released

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