1 | [[tags: egg]] |
---|
2 | [[toc:]] |
---|
3 | |
---|
4 | == skiplists |
---|
5 | |
---|
6 | Skiplists are data-types, which can replace balanced search-trees. They are described by Sedgewick. The idea is as follows: |
---|
7 | |
---|
8 | 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 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 | |
---|
10 | 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 in some randomized way. |
---|
11 | |
---|
12 | Second, 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 | |
---|
14 | Third, one steps down one level and continues following the skiplist's nodes at this new smaller level. |
---|
15 | |
---|
16 | Repeating this process until level 0 is reached we eventually find the place where our new node is to be inserted. |
---|
17 | |
---|
18 | Some additional remarks are in order. |
---|
19 | |
---|
20 | We 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 | |
---|
22 | 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. 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 | |
---|
27 | In this implementation skiplists are implemented in the Design by |
---|
28 | Contract style, i.e. using the contracts module. A corollary of this is, |
---|
29 | that the documentation is included in one of the two modules in form of |
---|
30 | a procedure with the module's name. Apart from this documentation |
---|
31 | procedure the two modules, %skiplists and skiplists, have the same |
---|
32 | interface. The first module contains the raw implementations of the |
---|
33 | procedures, the second imports the first with prefix % and wraps those |
---|
34 | prefixed routines with contracts. |
---|
35 | |
---|
36 | ==== skiplists |
---|
37 | |
---|
38 | <procedure>(skiplists [sym])</procedure> |
---|
39 | |
---|
40 | returns all available routines of the module when called without an |
---|
41 | argument, but when called with one of these routines as a symbol, |
---|
42 | returns its contract and documentation string. |
---|
43 | |
---|
44 | Another 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 | |
---|
51 | you'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 | |
---|
57 | trivial 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 | |
---|
68 | remove 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 | |
---|
79 | remove 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 | |
---|
90 | insert 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 | |
---|
101 | check, 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 | |
---|
112 | move 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 | |
---|
123 | combined 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 | |
---|
133 | check 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 | |
---|
144 | maximal 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 | |
---|
155 | list 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 | |
---|
169 | map 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 | |
---|
179 | apply 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 | |
---|
192 | restructure 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 | |
---|
207 | reorder 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 | |
---|
220 | filter 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 | |
---|
236 | construct 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 | |
---|
251 | construct 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 | |
---|
265 | skiplist 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 | |
---|
278 | skiplist 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 | |
---|
289 | maximal 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 | |
---|
300 | number 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 | |
---|
311 | gap of skiplist |
---|
312 | |
---|
313 | ==== skiplist? |
---|
314 | |
---|
315 | <procedure>(skiplist? xpr)</procedure> |
---|
316 | |
---|
317 | type 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 | |
---|
390 | Aug 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 |
---|