source: project/wiki/eggref/5/skiplists @ 37468

Last change on this file since 37468 was 37468, checked in by juergen, 17 months ago

skiplists docu

File size: 10.3 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. First one
19packages the item into a skipnode, where the number of links is
20generated randomly as described above. Second, one follows the skiplist
21along the highest occupied number of links as long as the skiplist's
22nodes point to items less then the item of the node to be inserted.
23Third, one steps down one level and continues following the skiplist's
24nodes at this new smaller level. Repeating this process until level 0
25is reached we eventually find the place where our new node is to be
26inserted.
27
28Some additional remarks are in order.
29
30We described the process with a width of two, i.e. at each level in the
31average one node of the level below is skipped. A higher value than two
32for the width is possible as well, trading performance against space.
33
34We have to decide, what to do with duplicates. We choose the following
35approach: The skiplist itself stores a list of either one or several
36numerical comparison operators. Only if the last of those operators is
37the special comparison operator dups (which returns constantly 0, i.e.
38it compares nothing) duplicates are allowed. Moreover, we arrage
39matters in such a way, that all nodes of duplicates with the same key
40have the same height, so that a search for the item which was inserted
41last will be found first.
42
43=== Documentation
44
45;;;;;
46In this implementation skiplists are implemented in the Design by
47Contract style, i.e. using the dbc module. A corollary of this is, that
48the documentation is included in one of the two modules in form of a
49procedure 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)
58<procedure>(skiplists sym)
59
60documentation procedure.
61The first call shows the list of exported symbols,
62the second documentation of symbol sym.
63
64==== skiplist
65
66<procedure>(skiplist width max-height item? order . orders)</procedure>
67<procedure>(skiplist max-height item? order . orders)</procedure>
68<procedure>(skiplist item? order . orders))</procedure>
69
70constructors:
71width is the jump width,
72max-height the maximum allowed length of pointers of an item,
73item? checks
74
75==== skiplist?
76
77<procedure>(skiplist? xpr)</procedure>
78
79type predicate.
80
81==== skiplist->list
82
83<procedure>(skiplist->list sls)</procedure>
84<procedure>(skiplist->list sls level)</procedure>
85
86the list of items stored in each level
87
88==== sl-null?
89
90<procedure>(sl-null? sls)</procedure>
91
92is skiplist empty?
93
94==== sl-dups?
95
96<procedure>(sl-dups? sls)</procedure>
97
98are duplicates allowed?
99
100==== sl-item?
101
102<procedure>(sl-item? sls)</procedure>
103
104item type predicate
105
106==== dups
107
108<procedure>(dups x y)</procedure>
109
110trivial numerical comparison operator to allow for duplicates
111
112transformer.
113
114==== sl-compare
115
116<procedure>(sl-compare sls)</procedure>
117
118combined comparison function
119
120==== sl-count
121
122<procedure>(sl-count sls)</procedure>
123
124number of items stored in skiplist
125
126==== sl-found
127
128<procedure>(sl-found sls)</procedure>
129
130list of found items, to be called after search!
131
132==== sl-found?
133
134<procedure>(sl-found? sls item)</procedure>
135
136is item found?
137
138==== sl-height
139
140<procedure>(sl-height sls)</procedure>
141
142actual maximal height of nodes (can be changed)
143
144==== sl-map
145
146<procedure>(sl-map fn sls)</procedure>
147<procedure>(sl-map fn sls order . orders)</procedure>
148<procedure>(sl-map fn sls width)</procedure>
149<procedure>(sl-map fn sls width order . orders)</procedure>
150
151depending on the mapping function, different order
152procedures might be necessary
153
154==== sl-for-each
155
156<procedure>(sl-for-each proc sls)</procedure>
157
158apply proc to each item in skiplist
159
160==== sl-filter
161
162<procedure>(sl-filter ok? sls)</procedure>
163
164filtering
165
166==== sl-max-height
167
168<procedure>(sl-max-height sls)</procedure>
169
170absolute maximum heigth of nodes in skiplist (not changeble)
171
172==== sl-max
173
174<procedure>(sl-max sls)</procedure>
175
176biggest items stored in skiplist
177
178==== sl-min
179
180<procedure>(sl-min sls)</procedure>
181
182smallest item stored in skiplist
183
184==== sl-orders
185
186<procedure>(sl-orders sls)</procedure>
187
188list of orders defined in the constructor
189
190==== sl-search-level
191
192<procedure>(sl-search-level sls)</procedure>
193
194down to which level a previous search descended?
195
196==== sl-width
197
198<procedure>(sl-width sls)</procedure>
199
200width skipped on average at each search level supplied by constructor
201
202==== sl-reorder
203
204<procedure>(sl-reorder sls order . orders)</procedure>
205
206changing orders
207
208==== sl-restructure
209
210<procedure>(sl-restructure sls width max-height)</procedure>
211
212changing width
213
214==== sl-insert!
215
216<procedure>(sl-insert! sls item . items)</procedure>
217
218insert items into skiplist
219
220==== sl-remove!
221
222<procedure>(sl-remove! sls item . items)</procedure>
223
224remove items from skiplist
225
226==== sl-search!
227
228<procedure>(sl-search! sls item)</procedure>
229
230searching for an item changes cursor transparently
231
232==== sl-clear!
233
234<procedure>(sl-clear! sls)</procedure>
235
236reset skiplist
237
238=== Examples
239
240<enscript highlight=scheme>
241
242(import skiplists)
243
244   A skiplist with primary and secondary search order, allowing duplicates
245;; some constructors
246
247(define sls1 (skiplist 15 fixnum? -))
248(sl-width sls1) ;-> 2
249(sl-max-height sls1) ;-> 15
250(sl-dups? sls1) ;-> #f
251
252(define sls2 (skiplist 4 20 fixnum? - dups))
253(fx= (sl-width sls2) ;-> 4
254(fx= (sl-max-height sls2) ;-> 20
255(sl-dups? sls2) ;-> #t
256
257;; create ...
258
259(define item-type (lambda (x)
260                    (and ((list-of? integer?) x) (> (length x) 2))))
261
262(define primary-order (lambda (x y) (- (car x) (car y))))
263
264(define secondary-order (lambda (x y) (- (cadr x) (cadr y))))
265
266(define sls3 (skiplist 3
267                       15
268                       item-type
269                       primary-order
270                       secondary-order
271                       dups))
272
273;; and populate ...
274
275(define lst1
276        (let loop ((k 0) (lst '()))
277          (if (= k 100)
278            lst
279            (loop (+ k 1) (cons (pseudo-random-integer 10) lst)))))
280
281(define lst2
282        (let loop ((k 0) (lst '()))
283          (if (= k 100)
284            lst
285            (loop (+ k 1) (cons (pseudo-random-integer 10) lst)))))
286
287(define lst3
288        (let loop ((k 0) (lst '()))
289          (if (= k 100)
290            lst
291            (loop (+ k 1) (cons (pseudo-random-integer 100) lst)))))
292
293(apply sl-insert! sls3
294       (map (lambda (x y z) (list x y z))
295            lst1 lst2 lst3))
296
297(sl-count sls3) ;-> 100
298
299(sl-width sls3) ;-> 3
300
301;; inserting item and removing all with same key ...
302
303((sl-item? sls3) '(1 2 3)) ;-> #t
304
305(sl-search! sls3 '(1 2 3))
306
307(if (sl-found? sls3 '(1 2 3))
308  (apply sl-remove! sls3 (sl-found sls3)))
309
310(sl-insert! sls3 '(1 2 3))
311
312(sl-search! sls3 '(1 2 3))
313
314(member '(1 2 3) (sl-found sls3))
315
316(apply sl-remove! sls3 (sl-found sls3))
317
318(sl-search! sls3 '(1 2 3))
319
320(null? (sl-found sls3))
321
322;; produce duplicates at the ends ...
323
324(sl-insert! sls3 '(-1 2 3) '(-1 2 3 4))
325
326(sl-min sls3) ;-> '((-1 2 3 4) (-1 2 3))
327
328(sl-insert! sls3 '(10 1 2) '(10 1 2 3) '(10 1 3))
329
330(sl-found sls3) ;-> '((10 1 3) (10 1 2 3) (10 1 2))
331
332(sl-max sls3) ;-> '((10 1 3) (10 1 2 3) (10 1 2))
333
334;; and remove them again ...
335
336(sl-search! sls3 '(-1 2 3 4))
337
338(apply sl-remove! sls3 (sl-found sls3))
339
340(sl-search! sls3 '(-1 2 3 4))
341
342(null? (sl-found sls3)) ;-> #t
343
344(sl-search! sls3 '(10 1 3))
345
346(apply sl-remove! sls3 (sl-found sls3))
347
348(null? (sl-found sls3)) ;-> #t
349
350;; reorder removing all dups ...
351
352(apply <= (map car
353               (skiplist->list
354                 (sl-reorder sls3 primary-order secondary-order))))
355
356(<= (sl-count (sl-reorder sls3 primary-order secondary-order))
357    (sl-count sls3))
358
359 reorder using only secondary order ...
360
361(apply < (map cadr
362              (skiplist->list
363                (sl-reorder sls3 secondary-order))))
364
365(>= 10 (sl-count
366         (sl-reorder sls3 secondary-order)))
367
368;; restructure ...
369
370(equal? (skiplist->list sls3)
371        (skiplist->list (sl-restructure sls3 2 10)))
372
373;; filter ...
374
375((list-of? odd?) (map caddr
376                      (skiplist->list
377                        (sl-filter sls3 (lambda (x) (odd? (caddr x)))))))
378
379;; map ...
380
381(let ((fn (lambda (x) (* 2 x))))
382  (equal?
383    (map fn (skiplist->list sls3))
384    (skiplist->list (sl-map sls3 fn))))
385
386</enscript>
387
388=== Requirements
389
390none
391
392=== Last update
393
394Mar 25, 2019
395
396== Author
397
398[[/users/juergen-lorenz|Juergen Lorenz]]
399
400== License
401
402Copyright (c) 2012-2019, Juergen Lorenz
403All rights reserved.
404Redistribution and use in source and binary forms, with or without
405modification, are permitted provided that the following conditions are
406met:
407
408Redistributions of source code must retain the above copyright
409notice, this list of conditions and the following disclaimer.
410
411Redistributions in binary form must reproduce the above copyright
412notice, this list of conditions and the following disclaimer in the
413documentation and/or other materials provided with the distribution.
414Neither the name of the author nor the names of its contributors may be
415used to endorse or promote products derived from this software without
416specific prior written permission.
417
418THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
419IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
420TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
421PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
422HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
423SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
424TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
425PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
426LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
427NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
428SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
429
430== Version History
431
432; 1.0 : port from chicken-4
Note: See TracBrowser for help on using the repository browser.