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

Last change on this file since 31097 was 31097, checked in by juergen, 6 years ago

skiplists docu beautified

File size: 17.6 KB
Line 
1[[tags: egg]]
2[[toc:]]
3
4
5== Skiplists
6
7Skiplists are data-types, which can replace balanced search-trees. They
8are invented by Pugh. The idea is as follows:
9
10Contrary to listnodes, which are pairs of an item and a next pointer,
11skipnodes are pairs of an item and a vector of next pointers. The
12length' of these vectors depend on each skipnode itself. They are
13choosen randomly in such a way, that, in the average, the number of
14nodes with at least k links is half the number of links with at least
15k-1 links, for k>1. Following the next pointers at a fixed link-level,
16k say, one skips all nodes with less than k pointers.
17
18Inserting an item into a skiplist now works as follows.
19First one packages the item into a skipnode, where the number of links
20is generated randomly as described above.
21Second, one follows the skiplist along the highest occupied number of
22links as long as the skiplist's nodes point to items less then the item
23of the node to be inserted.
24Third, one steps down one level and continues following the skiplist's
25nodes at this new smaller level.
26Repeating this process until level 0 is reached we eventually find the
27place where our new node is to be inserted.
28
29Some additional remarks are in order.
30
31We described the process with a width of two, i.e. at each level in the
32average one node of the level below is skipped.  A higher value than two
33for the width is possible as well, trading performance against space.
34
35We have to decide, what to do with duplicates. We choose the following
36approach: The skiplist itself stores a list of either one or several numerical
37comparison operators. Only if the last of those operators is the special
38comparison operator dups (which returns constantly 0, i.e. it compares
39nothing) duplicates are allowed. Moreover, we arrage matters in such a
40way, that all nodes of duplicates with the same key have the same
41height, so that a search for the item which was inserted last will be
42found first.
43
44=== Documentation
45
46In this implementation skiplists are implemented in the Design by
47Contract style, i.e. using the dbc module. A corollary of this is,
48that the documentation is included in one of the two modules in form of
49a procedure with the module's name. Apart from this documentation
50procedure the two modules, %skiplists and skiplists, have the same
51interface.  The first module contains the raw implementations of the
52procedures, the second imports the first with prefix % and wraps those
53prefixed routines with contracts.
54
55==== skiplists
56
57<procedure>(skiplists [symbol|string])</procedure>
58
59returns all available routines of the module when called without an
60argument.
61When called with one of these routines as a symbol, returns its contract.
62When called with a string, writes a file with name of string containing
63rudimentary wiki documentation.
64
65==== dups
66
67<procedure>(dups x y)</procedure>
68
69function (result)
70
71trivial numerical comparison operator to allow for duplicates
72
73<enscript highlight=scheme>
74(dups x y)
75requires (and ((skiplist-item? sls) x) ((skiplist-item? sls) y))
76ensures  (fx= result 0)
77</enscript>
78
79==== skiplist
80
81<procedure>(skiplist width max-height item? order . orders)</procedure>
82<procedure>(skiplist max-height item? order . orders)</procedure>
83<procedure>(skiplist item? order . orders))</procedure>
84
85function (result)
86
87<enscript highlight=scheme>
88(skiplist width max-height item? order . orders)
89requires (and (fixnum? width)
90              (fx> width 1)
91              (fixnum? max-height)
92              (fx> max-height 1)
93              (procedure? item?)
94              (item? item)
95              (procedure? order)
96              "(fixnum? (order item? item?))"
97              ((list-of? procedure?) orders)
98              " like order, last one might be dups")
99ensures  (skiplist? result)
100
101(skiplist max-height item? order . orders)
102"width defaults to 2"
103requires (and (fixnum? max-height)
104              (fx> max-height 1)
105              (procedure? item?)
106              (item? item)
107              (procedure? order)
108              "(fixnum? (order item? item?))"
109              ((list-of? procedure?) orders)
110              " like order, last one might be dups")
111ensures  (skiplist? result)
112
113(skiplist item? order . orders)
114"width defaults to 2, max-height to 10"
115requires (and (procedure? item?)
116              (item? item)
117              (procedure? order)
118              "(fixnum? (order item? item?))"
119              ((list-of? procedure?) orders)
120              " like order, last one might be dups")
121ensures  (skiplist? result)
122</enscript>
123
124==== skiplist->list
125
126<procedure>(or (skiplist->list sls) (skiplist->list sls level))</procedure>
127
128function (result)
129
130<enscript highlight=scheme>
131(skiplist->list sls)
132requires (skiplist? sls)
133ensures  ((list-of? (skiplist-item? sls)) result)
134
135(skiplist->list sls level)
136requires (and (skiplist? sls)
137              (fixnum? level)
138              (fx<= 0 level)
139              (fx< level (skiplist-height sls)))
140ensures  ((list-of? (skiplist-item? sls)) result)
141</enscript>
142
143==== skiplist-clear!
144
145<procedure>(skiplist-clear! sls)</procedure>
146
147command ((oldcount newcount skiplist-count) (oldheight newheight skiplist-height))
148
149<enscript highlight=scheme>
150(skiplist-clear! sls)
151requires (skiplist? sls)
152ensures  (and (fx= 0 newcount) (fx= 1 newheight))
153</enscript>
154
155==== skiplist-compare
156
157<procedure>(skiplist-compare sls)</procedure>
158
159function (result)
160
161<enscript highlight=scheme>
162(skiplist-compare sls)
163requires (skiplist? sls)
164ensures  (and (procedure? result) "(fixnum? (result x y))")
165</enscript>
166
167==== skiplist-count
168
169<procedure>(skiplist-count sls)</procedure>
170
171function (result)
172
173<enscript highlight=scheme>
174(skiplist-count sls)
175requires (skiplist? sls)
176ensures  (and (fixnum? result) (fx>= result 0))
177</enscript>
178
179==== skiplist-dups?
180
181<procedure>(skiplist-dups? sls)</procedure>
182
183function (result)
184
185<enscript highlight=scheme>
186(skiplist-dups? sls)
187requires (skiplist? sls)
188ensures  (boolean? result)
189</enscript>
190
191==== skiplist-filter
192
193<procedure>(skiplist-filter sls ok?)</procedure>
194
195function (result)
196
197<enscript highlight=scheme>
198(skiplist-filter sls ok?)
199requires (and (skiplist? sls) (procedure? ok?) "(boolean? (ok? x))")
200ensures  (skiplist? result)
201</enscript>
202
203==== skiplist-for-each
204
205<procedure>(skiplist-for-each sls proc)</procedure>
206
207command ((old new (constantly #t)))
208
209<enscript highlight=scheme>
210(skiplist-for-each sls proc)
211requires (and (skiplist? sls) (procedure? proc))
212ensures  new
213</enscript>
214
215==== skiplist-found
216
217<procedure>(skiplist-found sls)</procedure>
218
219function (result)
220
221<enscript highlight=scheme>
222(skiplist-found sls)
223requires (skiplist? sls)
224ensures  ((list-of? (skiplist-item? sls)) result)
225</enscript>
226
227==== skiplist-found?
228
229<procedure>(skiplist-found? sls item)</procedure>
230
231function (result)
232
233<enscript highlight=scheme>
234(skiplist-found? sls item)
235requires (and (skiplist? sls) ((skiplist-item? sls) item))
236ensures  (boolean? result)
237</enscript>
238
239==== skiplist-height
240
241<procedure>(skiplist-height sls)</procedure>
242
243function (result)
244
245<enscript highlight=scheme>
246(skiplist-height sls)
247requires (skiplist? sls)
248ensures  (and (fixnum? result) (fx> result 0))
249</enscript>
250
251==== skiplist-insert!
252
253<procedure>(skiplist-insert! sls item . items)</procedure>
254
255command ((oldcount newcount (lambda (sls . items) (skiplist-count sls)))
256         (oldfound newfound (lambda (sls . items)
257                              (skiplist-search! sls (car items))
258                              (skiplist-found sls))))
259
260<enscript highlight=scheme>
261(skiplist-insert! sls item . items)
262requires (and (skiplist? sls)
263              ((list-of? (skiplist-item? sls)) (cons item items)))
264ensures  (and (fx>= newcount oldcount) (member item newfound))
265</enscript>
266
267==== skiplist-item?
268
269<procedure>(skiplist-item? sls)</procedure>
270
271function (result)
272
273<enscript highlight=scheme>
274(skiplist-item? sls)
275requires (skiplist? sls)
276ensures  (procedure? result)
277</enscript>
278
279==== skiplist-map
280
281<procedure>(skiplist-map sls fn)</procedure>
282<procedure>(skiplist-map sls fn order . orders)</procedure>
283<procedure>(skiplist-map sls fn width)</procedure>
284<procedure>(skiplist-map sls fn width order . orders)</procedure>
285
286function (result)
287
288<enscript highlight=scheme>
289(skiplist-map sls fn)
290requires (and (skiplist? sls)
291              (procedure? fn)
292              "((skiplist-item? sls) (fn x))")
293ensures  (skiplist? result)
294
295(skiplist-map sls fn item? order . orders)
296requires (and (skiplist? sls)
297              (procedure? fn)
298              (procedure? item?)
299              (((list-of? procedure?) (cons order orders))))
300ensures  (skiplist? result)
301</enscript>
302
303==== skiplist-max
304
305<procedure>(skiplist-max sls)</procedure>
306
307function (result)
308
309<enscript highlight=scheme>
310(skiplist-max sls)
311requires (skiplist? sls)
312ensures  ((list-of? (skiplist-item? sls)) result)
313</enscript>
314
315==== skiplist-max-height
316
317<procedure>(skiplist-max-height sls)</procedure>
318
319function (result)
320
321<enscript highlight=scheme>
322(skiplist-max-height sls)
323requires (skiplist? sls)
324ensures  (and (fixnum? result) (fx> result 1))
325</enscript>
326
327==== skiplist-min
328
329<procedure>(skiplist-min sls)</procedure>
330
331function (result)
332
333<enscript highlight=scheme>
334(skiplist-min sls)
335requires (skiplist? sls)
336ensures  ((list-of? (skiplist-item? sls)) result)
337</enscript>
338
339==== skiplist-null?
340
341<procedure>(skiplist-null? sls)</procedure>
342
343function (result)
344
345<enscript highlight=scheme>
346(skiplist-null? sls)
347requires (skiplist? sls)
348ensures  (boolean? result)
349</enscript>
350
351==== skiplist-orders
352
353<procedure>(skiplist-orders sls)</procedure>
354
355function (result)
356
357<enscript highlight=scheme>
358(skiplist-orders sls)
359requires (skiplist? sls)
360ensures  ((list-of? procedure?) result)
361</enscript>
362
363==== skiplist-remove!
364
365<procedure>(skiplist-remove! sls item . items)</procedure>
366
367command ((oldcount newcount (lambda (sls . items)
368                              (skiplist-count sls))))
369
370<enscript highlight=scheme>
371(skiplist-remove! sls item . items)
372requires (and (skiplist? sls)
373              ((list-of? (skiplist-item? sls)) (cons item items)))
374ensures  (fx<= newcount oldcount)
375</enscript>
376
377==== skiplist-reorder
378
379<procedure>(skiplist-reorder sls order . orders)</procedure>
380
381function (result)
382
383<enscript highlight=scheme>
384(skiplist-reorder sls order . orders)
385requires (and (skiplist? sls)
386              ((list-of? procedure?) (cons order orders))
387              "each (fixnum? (order x y))")
388ensures  (skiplist? result)
389</enscript>
390
391==== skiplist-restructure
392
393<procedure>(skiplist-restructure sls width max-height)</procedure>
394
395function (result)
396
397<enscript highlight=scheme>
398(skiplist-restructure sls width max-height)
399requires (and (skiplist? sls) (fixnum? width) (fx> width 1)
400              (fixnum? max-height) (fx> max-height 1))
401ensures  (skiplist? result)
402</enscript>
403
404==== skiplist-search!
405
406<procedure>(skiplist-search! sls item)</procedure>
407
408command ((oldlevel newlevel (lambda (sls item)
409                              (skiplist-search-level sls)))
410         (oldfound newfound (lambda (sls item) (skiplist-found sls))))
411
412<enscript highlight=scheme>
413(skiplist-search! sls item)
414requires (and (skiplist? sls)
415              ((skiplist-item? sls) item))
416ensures  (and (fx>= newlevel 0)
417              (fx< newlevel (skiplist-height sls))
418              ((list-of? (skiplist-item? sls)) newfound)
419              ((list-of? zero?)
420               (map (lambda (x) ((skiplist-compare sls) item x))
421                    newfound)))
422</enscript>
423
424==== skiplist-search-level
425
426<procedure>(skiplist-search-level sls)</procedure>
427
428function (result)
429
430<enscript highlight=scheme>
431(skiplist-search-level sls)
432requires (skiplist? sls)
433ensures  (and (fixnum? result) (fx>= result 0) (fx< result (skiplist-height sls)))
434</enscript>
435
436==== skiplist-width
437
438<procedure>(skiplist-width sls)</procedure>
439
440function (result)
441
442<enscript highlight=scheme>
443(skiplist-width sls)
444requires (skiplist? sls)
445ensures  (and (fixnum? result) (fx> result 1))
446</enscript>
447
448==== skiplist?
449
450<procedure>(skiplist? xpr)</procedure>
451
452function (result)
453
454<enscript highlight=scheme>
455(skiplist? xpr)
456requires #t
457ensures  (boolean? result)
458</enscript>
459
460=== Examples
461
462A skiplist with primary and secondary search order, allowing duplicates
463
464<enscript highlight=scheme>
465
466;; some constructors
467
468  (define sls1 (skiplist 15 fixnum? -))
469  (fx= (skiplist-width sls1) 2)
470  (fx= (skiplist-max-height sls1) 15)
471  (not (skiplist-dups? sls1))
472
473  (define sls2 (skiplist 4 20 fixnum? - dups))
474  (fx= (skiplist-width sls2) 4)
475  (fx= (skiplist-max-height sls2) 20)
476  (skiplist-dups? sls2)
477
478;; create ...
479
480  (define item-type (lambda (x)
481                      (and ((list-of? integer?) x) (> (length x) 2))))
482
483  (define primary-order (lambda (x y) (- (car x) (car y))))
484
485  (define secondary-order (lambda (x y) (- (cadr x) (cadr y))))
486
487  (define sls3 (skiplist 3
488                         15
489                         item-type
490                         primary-order
491                         secondary-order
492                         dups))
493
494;; and populate ...
495
496  (define lst1
497          (let loop ((k 0) (lst '()))
498            (if (= k 100)
499              lst
500              (loop (+ k 1) (cons (random 10) lst)))))
501
502  (define lst2
503          (let loop ((k 0) (lst '()))
504            (if (= k 100)
505              lst
506              (loop (+ k 1) (cons (random 10) lst)))))
507
508  (define lst3
509          (let loop ((k 0) (lst '()))
510            (if (= k 100)
511              lst
512              (loop (+ k 1) (cons (random 100) lst)))))
513
514  (apply skiplist-insert! sls3
515         (map (lambda (x y z) (list x y z))
516              lst1 lst2 lst3))
517
518  (= (skiplist-count sls3) 100)
519
520  (= (skiplist-width sls3) 3)
521
522;; inserting item and removing all with same key ...
523
524  ((skiplist-item? sls3) '(1 2 3))
525
526  (skiplist-search! sls3 '(1 2 3))
527
528  (if (skiplist-found? sls3 '(1 2 3))
529    (apply skiplist-remove! sls3 (skiplist-found sls3)))
530
531  (skiplist-insert! sls3 '(1 2 3))
532
533  (skiplist-search! sls3 '(1 2 3))
534
535  (member '(1 2 3) (skiplist-found sls3))
536
537  (apply skiplist-remove! sls3 (skiplist-found sls3))
538
539  (skiplist-search! sls3 '(1 2 3))
540
541  (null? (skiplist-found sls3))
542
543;; produce duplicates at the ends ...
544
545  (skiplist-insert! sls3 '(-1 2 3) '(-1 2 3 4))
546
547  (equal? (skiplist-min sls3) '((-1 2 3 4) (-1 2 3)))
548
549  (skiplist-insert! sls3 '(10 1 2) '(10 1 2 3) '(10 1 3))
550
551  (equal? (skiplist-found sls3) '((10 1 3) (10 1 2 3) (10 1 2)))
552
553  (equal? (skiplist-max sls3) '((10 1 3) (10 1 2 3) (10 1 2)))
554
555;; and remove them again ...
556
557  (skiplist-search! sls3 '(-1 2 3 4))
558
559  (apply skiplist-remove! sls3 (skiplist-found sls3))
560
561  (skiplist-search! sls3 '(-1 2 3 4))
562
563  (null? (skiplist-found sls3))
564
565  (skiplist-search! sls3 '(10 1 3))
566
567  (apply skiplist-remove! sls3 (skiplist-found sls3))
568
569  (null? (skiplist-found sls3))
570
571;; reorder removing all dups ...
572
573  (apply <= (map car
574                 (skiplist->list
575                   (skiplist-reorder sls3 primary-order secondary-order))))
576
577  (<= (skiplist-count (skiplist-reorder sls3 primary-order secondary-order))
578      (skiplist-count sls3))
579
580;; reorder using only secondary order ...
581
582  (apply < (map cadr
583                (skiplist->list
584                  (skiplist-reorder sls3 secondary-order))))
585
586  (>= 10 (skiplist-count
587           (skiplist-reorder sls3 secondary-order)))
588
589;; restructure ...
590
591  (equal? (skiplist->list sls3)
592          (skiplist->list (skiplist-restructure sls3 2 10)))
593
594;; filter ...
595
596  ((list-of? odd?) (map caddr
597                        (skiplist->list
598                          (skiplist-filter sls3 (lambda (x) (odd? (caddr x)))))))
599
600;; map ...
601
602  (let ((fn (lambda (x) (* 2 x))))
603    (equal?
604      (map fn (skiplist->list sls3))
605      (skiplist->list (skiplist-map sls3 fn))))
606
607</enscript>
608
609== Requirements
610
611[[dbc]]
612
613== Last update
614
615Feb 06, 2014
616
617== Author
618
619[[/users/juergen-lorenz|Juergen Lorenz]]
620
621== License
622
623 Copyright (c) 2012-2014, Juergen Lorenz
624 All rights reserved.
625
626 Redistribution and use in source and binary forms, with or without
627 modification, are permitted provided that the following conditions are
628 met:
629 
630 Redistributions of source code must retain the above copyright
631 notice, this list of conditions and the following disclaimer.
632 
633 Redistributions in binary form must reproduce the above copyright
634 notice, this list of conditions and the following disclaimer in the
635 documentation and/or other materials provided with the distribution.
636 Neither the name of the author nor the names of its contributors may be
637 used to endorse or promote products derived from this software without
638 specific prior written permission.
639   
640 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
641 IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
642 TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
643 PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
644 HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
645 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
646 TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
647 PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
648 LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
649 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
650 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
651
652== Version History
653
654; 1.1.4 : bug in contract of skiplist-map fixed
655; 1.1.3 : tests updated
656; 1.1.2 : tests updated
657; 1.1 : skiplist-max-height added, constructor now accepts max-height argument (default is 10), width argument may be omitted (defaults to 2)
658; 1.0 : complete rewrite, dependency changed to dbc, prefixes changed to skiplist, only one constructor remained
659; 0.7 : dependency on records removed, define-record-type and define-record-printer used instead
660; 0.6 : code restructured into two modules
661; 0.4 : assert call corrected
662; 0.3 : added skip-orders, skip-reorder, skip-filter
663; 0.2 : skip-map removed, skip-insert!, skip-remove! and skip-remove-all! now accept multiple item arguments
664; 0.1 : initial import
Note: See TracBrowser for help on using the repository browser.