source: project/wiki/eggref/4/random-access-lists @ 31103

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

docu of skiplists and random-access-lists improved

File size: 16.7 KB
Line 
1[[tags: egg]]
2[[toc:]]
3
4
5== Random-access-lists
6
7Random-access-lists combine the advantages of vectors (fast access) and
8linked-lists (fast insertions). They can be implemented on the basis of
9skiplists.
10
11Whereas an ordinary skiplist-node consists of an item and a vector of
12next nodes, whose length is computed randomly in such a way, that the
13number of nodes with length n are in the average one half of the number
14of nodes with length (- n 1), a random-access-list-node must have an
15additional vector of same length containing the jumps, i.e. numbers
16indicating how far the node is moved when following the next nodes at a
17given level. Following a node at level n describes a fast lane across
18the random-access-list, where the jumps at level n are in the average
19twice as long as the jumps at the level below.
20
21In our implementation of random-access-lists we store a vector of nodes,
22called cursors, and a vector of positions, called places, which are
23updated along the movement accross the list. Moving cursors and places
24to a given position, pos, works as follows: One starts at the highest
25level and follows the next link at that level adding the jump at that
26level to the place at that level until the latter is less than pos but
27a further movement at that level would be greater or equal pos. Then
28one saves cursor and place and restarts the same movement process at
29the level below, starting with the values saved in the level above.
30Eventually one reaches level 0 and stops at a place one less than pos.
31The stored cursors can than be used to insert or remove an item, as
32well as getting or setting pos' item. Note, that in the latter case we
33only need to step down until a level where the next place is equal to
34pos. Since this cursor and place movement is O(log n), so are all the
35fundamental random-access-list operations, insert!, remove!, ref and set!
36
37The other supplied operators like map, filter split and join work only
38at a fixed level, whence are ordinary linked list operators, which
39perform as O(n).
40
41Some additional remarks are in order.
42
43We described the process with a width of two, i.e. increasing the level
44of movement doubles the jumps of next nodes in the average.  A higher
45value than two for the width is possible as well, trading performance
46against space.
47
48We said nothing about the maximal length of the nodes, i.e. of the
49maximal height of the random-access-list. Our default is 10, but this
50can be changed in the constructor. This should be appropriate in most
51cases. But note, that the highest actual, i.e. computed, node height
52might be smaller, so it must be updated in the list, so that the cursor
53knows where to start.
54
55=== Documentation
56
57In this implementation random-access-lists are implemented in the Design
58by Contract style, i.e. using the dbc module. A corollary of this is,
59that the documentation is included in one of the two modules in form of
60a procedure with the module's name. Apart from this documentation
61procedure the two modules, %random-access-lists and random-access-lists,
62have the same interface.  The first module contains the raw
63implementations of the procedures, the second imports the first with
64prefix % and wraps those prefixed routines with contracts.
65
66==== random-access-lists
67
68<procedure>(random-access-lists [symbol|string])</procedure>
69
70returns all available routines of the module when called without an
71argument.
72When called with one of these routines as a symbol, returns its contract.
73When called with a string, writes a file with name of string containing
74rudimentary wiki documentation.
75
76==== make-ral
77
78<procedure>(make-ral item? . args)</procedure>
79
80<enscript highlight=scheme>
81function (result)
82requires (and ((list-of? (lambda (arg) (and (fixnum? arg) (fx> arg 1)))) args)
83              (procedure? item?) "(item? item)")
84ensures  (ral? result)
85</enscript>
86
87==== ral->list
88
89<procedure>(ral->list ls)</procedure>
90<procedure>(ral->list ls level)</procedure>
91
92<enscript highlight=scheme>
93function (result)
94requires (and (ral? ls) (fixnum? level)
95              (fx<= 0 level) (fx< level (ral-height ls)))
96         ; default (fx= level 0)
97ensures  ((list-of? (ral-item? ls)) result)
98</enscript>
99
100==== ral-add!
101
102<procedure>(ral-add! ls item . items)</procedure>
103
104<enscript highlight=scheme>
105command ((oldcount newcount (lambda (ls item . items) (ral-count ls))))
106requires (and (ral? ls) ((ral-item? ls) item)
107              ((list-of? (ral-item? ls)) items))
108ensures  (fx= newcount (fx+ (length (cons item items)) oldcount))
109</enscript>
110
111==== ral-add-left!
112
113<procedure>(ral-add-left! ls item . items)</procedure>
114
115<enscript highlight=scheme>
116command ((oldcount newcount (lambda (ls item . items) (ral-count ls))))
117requires (and (ral? ls) ((ral-item? ls) item)
118              ((list-of? (ral-item? ls)) items))
119ensures  (fx= newcount (fx+ (length (cons item items)) oldcount))
120</enscript>
121
122==== ral-clear!
123
124<procedure>(ral-clear! ls)</procedure>
125
126<enscript highlight=scheme>
127command ((oldcount newcount ral-count) (oldheight newheight ral-height))
128requires (ral? ls)
129ensures  (and (fx= 0 newcount) (fx= 1 newheight))
130</enscript>
131
132==== ral-count
133
134<procedure>(ral-count ls)</procedure>
135
136<enscript highlight=scheme>
137function (result)
138requires (ral? ls)
139ensures  (and (fixnum? result) (fx>= result 0))
140</enscript>
141
142==== ral-cursor-jump
143
144<procedure>(ral-cursor-jump ls k)</procedure>
145
146<enscript highlight=scheme>
147function (result)
148requires (and (ral? ls) (fixnum? k)
149              (fx>= k 0) (fx< k (ral-height ls)))
150ensures  (and (fixnum? result)
151              (fx> result 0) (fx<= result (ral-count ls)))
152</enscript>
153
154==== ral-cursor-next
155
156<procedure>(ral-cursor-next ls k)</procedure>
157
158<enscript highlight=scheme>
159function (result)
160requires (and (ral? ls) (fixnum? k)
161              (fx>= k 0) (fx< k (ral-height ls)))
162ensures  (or (null? result) (ral-node? result))
163</enscript>
164
165==== ral-eq?
166
167<procedure>(ral-eq? ls0 ls1)</procedure>
168
169<enscript highlight=scheme>
170function (result)
171requires (and (ral? ls0) (ral? ls1))
172ensures  (boolean? result)
173</enscript>
174
175==== ral-eql?
176
177<procedure>(ral-eql? eql? ls0 ls1)</procedure>
178
179<enscript highlight=scheme>
180function (result)
181requires (and (procedure? eql?) "(eql? item0 item1)"
182              (ral? ls0) (ral? ls1))
183ensures  (boolean? result)
184</enscript>
185
186==== ral-equal?
187
188<procedure>(ral-equal? ls0 ls1)</procedure>
189
190<enscript highlight=scheme>
191function (result)
192requires (and (ral? ls0) (ral? ls1))
193ensures  (boolean? result)
194</enscript>
195
196==== ral-eqv?
197
198<procedure>(ral-eqv? ls0 ls1)</procedure>
199
200<enscript highlight=scheme>
201function (result)
202requires (and (ral? ls0) (ral? ls1))
203ensures  (boolean? result)
204</enscript>
205
206==== ral-filter
207
208<procedure>(ral-filter ls ok?)</procedure>
209
210<enscript highlight=scheme>
211function (result)
212requires (and (ral? ls) (procedure? ok?) "(ok? item)")
213ensures  (and (ral? result)
214              (fx<= (ral-count result) (ral-count ls)))
215</enscript>
216
217==== ral-for-each
218
219<procedure>(ral-for-each ls proc)</procedure>
220
221<enscript highlight=scheme>
222command ((old new (constantly #t)))
223requires (and (ral? ls) (procedure? proc) "(proc item)")
224ensures  new
225</enscript>
226
227==== ral-from-upto
228
229<procedure>(ral-from-upto ls from upto)</procedure>
230
231<enscript highlight=scheme>
232function (result)
233requires (and (ral? ls) (fixnum? from) (fixnum? upto)
234              (fx>= from 0) (fx>= upto from)
235              (fx<= upto (ral-count ls)))
236ensures  (and (ral? result)
237              (fx= (ral-count result) (fx- upto from)))
238</enscript>
239
240==== ral-height
241
242<procedure>(ral-height ls)</procedure>
243
244<enscript highlight=scheme>
245function (result)
246requires (ral? ls)
247ensures  (and (fixnum? result) (fx> result 0))
248</enscript>
249
250==== ral-insert!
251
252<procedure>(ral-insert! ls place item)</procedure>
253
254<enscript highlight=scheme>
255command ((oldcount newcount (lambda (ls place item) (ral-count ls)))
256         (olditem newitem (lambda (ls place item) (ral-ref ls place))))
257requires (and (ral? ls) ((ral-item? ls) item)
258              (fixnum? place) (fx>= place 0) (fx<= place (ral-count ls)))
259ensures  (and (fx= newcount (fx+ 1 oldcount)) (equal? newitem item))
260</enscript>
261
262==== ral-item?
263
264<procedure>(ral-item? ls)</procedure>
265
266<enscript highlight=scheme>
267function (result)
268requires (ral? ls)
269ensures  (procedure? result)
270</enscript>
271
272==== ral-join
273
274<procedure>(ral-join head tail)</procedure>
275
276<enscript highlight=scheme>
277function (result)
278requires (and (ral? head) (ral? tail)
279              (eq? (ral-item? head) (ral-item? tail)))
280ensures  (and (ral? result)
281              (fx= (ral-count result)
282                   (fx+ (ral-count head) (ral-count tail))))
283</enscript>
284
285==== ral-level
286
287<procedure>(ral-level ls)</procedure>
288
289<enscript highlight=scheme>
290function (result)
291requires (ral? ls)
292ensures  (and (fixnum? result) (fx> result 0)
293              (fx< result (ral-height ls)))
294</enscript>
295
296==== ral-map
297
298<procedure>(ral-map ls fn)</procedure>
299<procedure>(ral-map ls fn item?)</procedure>
300
301<enscript highlight=scheme>
302function (result)
303requires (and (ral? ls) (procedure? fn) "(fn item)"
304              (procedure? item?) "(item? item)")
305         ; default (eq? item? ral-item?)
306ensures  (and (ral? result) (fx= (ral-count result) (ral-count ls))
307              (eq? item? (ral-item? result)))
308</enscript>
309
310==== ral-max-height
311
312<procedure>(ral-max-height ls)</procedure>
313
314<enscript highlight=scheme>
315function (result)
316requires (ral? ls)
317ensures  (and (fixnum? result) (fx> result 0))
318</enscript>
319
320==== ral-node?
321
322<procedure>(ral-node? xpr)</procedure>
323
324<enscript highlight=scheme>
325function (result)
326requires #t
327ensures  (boolean? result)
328</enscript>
329
330==== ral-null?
331
332<procedure>(ral-null? ls)</procedure>
333
334<enscript highlight=scheme>
335function (result)
336requires (ral? ls)
337ensures  (boolean? result)
338</enscript>
339
340==== ral-place
341
342<procedure>(ral-place ls k)</procedure>
343
344<enscript highlight=scheme>
345function (result)
346requires (and (ral? ls) (fixnum? k)
347              (fx>= k 0) (fx< k (ral-height ls)))
348ensures  (and (fixnum? result) (fx>= result -1)
349              (fx< result (ral-count ls)))
350</enscript>
351
352==== ral-place-next
353
354<procedure>(ral-place-next ls k)</procedure>
355
356<enscript highlight=scheme>
357function (result)
358requires (and (ral? ls) (fixnum? k)
359              (fx>= k 0) (fx< k (ral-height ls)))
360ensures  (and (fixnum? result) (fx>= result 0)
361              (fx<= result (ral-count ls)))
362</enscript>
363
364==== ral-print
365
366<procedure>(ral-print ls)</procedure>
367
368<enscript highlight=scheme>
369command ((old new (constantly #t)))
370requires (ral? ls)
371ensures  new
372</enscript>
373
374==== ral-ref
375
376<procedure>(ral-ref ls place)</procedure>
377
378<enscript highlight=scheme>
379function (result)
380requires (and (ral? ls) (fixnum? place)
381              (fx>= place 0) (fx< place (ral-count ls)))
382ensures  ((ral-item? ls) result)
383</enscript>
384
385==== ral-remove!
386
387<procedure>(ral-remove! ls place)</procedure>
388
389<enscript highlight=scheme>
390command ((oldcount newcount (lambda (ls place) (ral-count ls))))
391requires (ral? ls)
392ensures  (and (fx= newcount (fx- oldcount 1)))
393</enscript>
394
395==== ral-restructure
396
397<procedure>(ral-restructure ls width)</procedure>
398<procedure>(ral-restructure ls width max-height)</procedure>
399
400<enscript highlight=scheme>
401function (result)
402requires (and (ral? ls) (fixnum? width)
403              (fx> width 1) (fixnum? max-height) (fx> max-height 1))
404         ; default (fx= max-height (ral-max-height ls))
405ensures  (and (ral? result) (fx= (ral-count ls) (ral-count result))
406              (fx= (ral-width result) width)
407              (fx= (ral-max-height result) max-height))
408</enscript>
409
410==== ral-set!
411
412<procedure>(ral-set! ls place item)</procedure>
413
414<enscript highlight=scheme>
415command ((old new (lambda (ls place item) (ral-ref ls place))))
416requires (and (ral? ls) ((ral-item? ls) item)
417              (fixnum? place) (fx>= place 0)
418              (fx< place (ral-count ls)))
419ensures  (equal? new item)
420</enscript>
421
422==== ral-split
423
424<procedure>(ral-split ls place)</procedure>
425
426<enscript highlight=scheme>
427function (head tail)
428requires (and (ral? ls) (fixnum? place)
429              (fx>= place 0) (fx< place (ral-count ls)))
430ensures  (and (ral? head) (ral? tail)
431              (fx= (ral-count head) place)
432              (fx= (ral-count tail) (fx- (ral-count ls) place)))
433</enscript>
434
435==== ral-start
436
437<procedure>(ral-start ls)</procedure>
438
439<enscript highlight=scheme>
440function (result)
441requires (ral? ls)
442ensures  (ral-node? result)
443</enscript>
444
445==== ral-width
446
447<procedure>(ral-width ls)</procedure>
448
449<enscript highlight=scheme>
450function (result)
451requires (ral? ls)
452ensures  (and (fixnum? result) (fx> result 1))
453</enscript>
454
455==== ral?
456
457<procedure>(ral? xpr)</procedure>
458
459<enscript highlight=scheme>
460function (result)
461requires #t
462ensures  (boolean? result)
463</enscript>
464
465=== Examples
466
467<enscript highlight=scheme>
468
469;an empty ral of integers
470(define ls (make-ral integer?))
471(ral? ls)
472(ral-null? ls)
473(fx= (ral-height ls) 1)
474
475;populate it at the right end
476(ral-add! ls 0 1 2 3 4)
477(fx= (ral-count ls) 5)
478(equal? (ral->list ls) '(0 1 2 3 4))
479
480;remove some items
481(ral-remove! ls 2)
482(fx= (ral-count ls) 4)
483(equal? (ral->list ls) '(0 1 3 4))
484(ral-remove! ls (fx- (ral-count ls) 1))
485(fx= (ral-count ls) 3)
486(equal? (ral->list ls) '(0 1 3))
487(ral-remove! ls 0)
488(fx= (ral-count ls) 2)
489(equal? (ral->list ls) '(1 3))
490
491;insert an item
492(ral-insert! ls 1 2)
493(fx= (ral-ref ls 1) 2)
494(fx= (ral-count ls) 3)
495(equal? (ral->list ls) '(1 2 3))
496
497;reset ral
498(ral-clear! ls)
499(ral-null? ls)
500
501;populate ral again
502(do ((k 0 (fx+ 1 k)))
503  ((fx= k 100))
504  (ral-add! ls k))
505(fx= (ral-count ls) 100)
506
507;split, join and subral
508(ral-eql? fx=
509          ls
510          (receive (head tail) (ral-split ls 50)
511            (ral-join head tail)))
512(equal?
513  (ral->list (ral-from-upto ls 20 70))
514  (let loop ((k 69) (result '()))
515    (if (fx= k 19)
516      result
517      (loop (fx- k 1) (cons k result)))))
518
519;inspect and change an item in the middle
520(fx= (ral-ref ls 50) 50)
521(ral-set! ls 50 500)
522(fx= (ral-ref ls 50) 500)
523
524;change item back again
525(ral-set! ls 50 50)
526(fx= (ral-ref ls 50) 50)
527
528;change items at the ends and back again
529(ral-set! ls 0 1000)
530(fx= (ral-ref ls 0) 1000)
531(ral-set! ls 0 0)
532(fx= (ral-ref ls 0) 0)
533(ral-set! ls 99 1000)
534(fx= (ral-ref ls 99) 1000)
535(ral-set! ls 99 99)
536(fx= (ral-ref ls 99) 99)
537
538;insert at left end
539(ral-add-left! ls -1 -2 -3)
540(fx= (ral-ref ls 0) -3)
541(fx= (ral-ref ls 1) -2)
542(fx= (ral-ref ls 2) -1)
543
544;remove them again
545(ral-remove! ls 0)
546(ral-remove! ls 0)
547(ral-remove! ls 0)
548(fx= (ral-ref ls 0) 0)
549(fx= (ral-count ls) 100)
550
551;insert at right end and remove it again
552(ral-add! ls 100 101)
553(fx= (ral-ref ls (fx- (ral-count ls) 1)) 101)
554(ral-remove! ls (fx- (ral-count ls) 1))
555(ral-remove! ls (fx- (ral-count ls) 1))
556(fx= (ral-ref ls (fx- (ral-count ls) 1)) 99)
557
558;insert in the middle and remove it again
559(ral-insert! ls 20 200)
560(fx= (ral-ref ls 20) 200)
561(fx= (ral-ref ls 21) 20)
562(fx= (ral-count ls) 101)
563(ral-remove! ls 20)
564(fx= (ral-ref ls 20) 20)
565(fx= (ral-count ls) 100)
566
567;restructure
568(define lsr (ral-restructure ls 4 20))
569(ral-eql? fx= ls lsr)
570(fx= (ral-width lsr) 4)
571(fx= (ral-max-height lsr) 20)
572
573;map and filter
574(equal? (ral->list (ral-map ls add1))
575        (let loop ((k 100) (result '()))
576          (if (fx= k 0)
577            result
578            (loop (fx- k 1) (cons k result)))))
579(equal? (ral->list (ral-filter ls odd?))
580        (let loop ((k 99) (result '()))
581          (if (fx< k 0)
582            result
583            (loop (fx- k 2) (cons k result)))))
584
585</enscript>
586
587== Requirements
588
589[[dbc]]
590
591== Last update
592
593Nov 27, 2013
594
595== Author
596
597[[/users/juergen-lorenz|Juergen Lorenz]]
598
599== License
600
601 Copyright (c) 2012-2013, Juergen Lorenz
602 All rights reserved.
603
604 Redistribution and use in source and binary forms, with or without
605 modification, are permitted provided that the following conditions are
606 met:
607 
608 Redistributions of source code must retain the above copyright
609 notice, this list of conditions and the following disclaimer.
610 
611 Redistributions in binary form must reproduce the above copyright
612 notice, this list of conditions and the following disclaimer in the
613 documentation and/or other materials provided with the distribution.
614 Neither the name of the author nor the names of its contributors may be
615 used to endorse or promote products derived from this software without
616 specific prior written permission.
617   
618 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
619 IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
620 TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
621 PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
622 HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
623 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
624 TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
625 PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
626 LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
627 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
628 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
629
630== Version History
631
632; 0.1.2 : tests updated
633; 0.1.1 : tests updated
634; 0.1 : initial import
Note: See TracBrowser for help on using the repository browser.