Debian Codegraph @

lib/data/skew-list.scm

raw
1 ;;;
2 ;;; data.skew-list - Skewed Binary Random Access List
3 ;;;
4 ;;; Copyright (c) 2019-2024 Shiro Kawai <[email protected]>
5 ;;;
6 ;;; Redistribution and use in source and binary forms, with or without
7 ;;; modification, are permitted provided that the following conditions
8 ;;; are met:
9 ;;;
10 ;;; 1. Redistributions of source code must retain the above copyright
11 ;;; notice, this list of conditions and the following disclaimer.
12 ;;;
13 ;;; 2. Redistributions in binary form must reproduce the above copyright
14 ;;; notice, this list of conditions and the following disclaimer in the
15 ;;; documentation and/or other materials provided with the distribution.
16 ;;;
17 ;;; 3. Neither the name of the authors nor the names of its contributors
18 ;;; may be used to endorse or promote products derived from this
19 ;;; software without specific prior written permission.
20 ;;;
21 ;;; THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 ;;; "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 ;;; LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24 ;;; A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25 ;;; OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26 ;;; SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
27 ;;; TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
28 ;;; PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
29 ;;; LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
30 ;;; NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
31 ;;; SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32 ;;;
33
34 ;; Implements SkewList as described in
35 ;; Chris Okasaki: Purely Functional Data Structures
36 ;;
37 ;; Tree a = Leaf a | Node a (Tree a) (Tree a)
38 ;; SkewList a = SL [(Int, Tree a)]
39
40 (define-module data.skew-list
41 (use gauche.record)
42 (use gauche.sequence)
43 (use util.match)
44 (use util.queue)
45 (export <skew-list>
46 skew-list?
47 skew-list-empty?
48 skew-list-null
49 skew-list-cons
50 skew-list-car
51 skew-list-cdr
52 skew-list-ref
53 skew-list-set
54 skew-list-fold
55 skew-list-map
56 skew-list-length
57 skew-list-length<=?
58 list*->skew-list
59 list->skew-list
60 skew-list->list
61 skew-list->generator
62 skew-list->lseq
63 skew-list-take
64 skew-list-drop
65 skew-list-split-at
66 skew-list-append)
67 )
68 (select-module data.skew-list)
69
70 (define-class <skew-list-meta> (<record-meta>) ())
71 (define-record-type (<skew-list> #f :mixins (<sequence>)
72 :metaclass <skew-list-meta>)
73 %make-sl skew-list?
74 (elements skew-list-elements)) ; [(Int, Tree)]]
75
76 (define (SL elts)
77 (if (null? elts)
78 skew-list-null ;singleton to save allocation
79 (%make-sl elts)))
80
81 ;; We use these frequently. NB: n is always 2^k-1.
82 (define-inline (/2 n) (ash n -1))
83 (define-inline (/4 n) (ash n -2))
84
85 ;;;
86 ;;; Primitives
87 ;;;
88
89 (define (skew-list-empty? sl)
90 (assume-type sl <skew-list>)
91 (null? (skew-list-elements sl)))
92 (define skew-list-null (%make-sl '()))
93
94 (define (skew-list-cons x y)
95 (assume-type y <skew-list>)
96 (match (skew-list-elements y)
97 [([w1 . t1] [w2 . t2] . ts)
98 (if (= w1 w2)
99 (SL `([,(+ 1 w1 w2) . (Node ,x ,t1 ,t2)] ,@ts))
100 (SL `([1 . (Leaf ,x)] ,@(skew-list-elements y))))]
101 [_ (SL `([1 . (Leaf ,x)] ,@(skew-list-elements y)))]))
102
103 (define (skew-list-car sl)
104 (assume-type sl <skew-list>)
105 (match (skew-list-elements sl)
106 [() (error "Attempt to take skew-list-car of empty skew-list")]
107 [([_ . ('Leaf x)] . _) x]
108 [([_ . ('Node x _ _)] . _) x]))
109
110 (define (skew-list-cdr sl)
111 (assume-type sl <skew-list>)
112 (match (skew-list-elements sl)
113 [() (error "Attempt to take skew-list-cdr of empty skew-list")]
114 [([_ . ('Leaf _)] . ts) (SL ts)]
115 [([w . ('Node x t1 t2)] . ts)
116 (SL `([,(/2 w) . ,t1] [,(/2 w) . ,t2] ,@ts))]))
117
118 (define (skew-list-ref sl n :optional fallback)
119 (define (tree-ref w i t)
120 (if (= i 0)
121 (cadr t)
122 (if (= w 1)
123 (if (undefined? fallback)
124 (error "index out of range" n)
125 fallback)
126 (match-let1 ('Node x t1 t2) t
127 (let1 w2 (/2 w)
128 (if (<= i w2)
129 (tree-ref w2 (- i 1) t1)
130 (tree-ref w2 (- i 1 w2) t2)))))))
131 (define (ref i ts)
132 (match ts
133 [() (if (undefined? fallback)
134 (error "index out of range" n)
135 fallback)]
136 [((w . t) . ts)
137 (if (< i w) (tree-ref w i t) (ref (- i w) ts))]))
138 (assume-type sl <skew-list>)
139 (ref n (skew-list-elements sl)))
140
141 (define (skew-list-set sl n v)
142 (define (tree-set w i t)
143 (if (= i 0)
144 (match t
145 [('Leaf _) `(Leaf ,v)]
146 [(`Node _ t1 t2) `(Node ,v ,t1 ,t2)])
147 (if (= w 1)
148 (error "index out of range" n)
149 (match-let1 ('Node x t1 t2) t
150 (let1 w2 (/2 w)
151 (if (<= i w2)
152 `(Node ,x ,(tree-set w2 (- i 1) t1) ,t2)
153 `(Node ,x ,t1 ,(tree-set w2 (- i 1 w2) t2))))))))
154 (define (set i ts)
155 (match ts
156 [() (error "index out of range" n)]
157 [((w . t) . ts)
158 (if (< i w)
159 `((,w . ,(tree-set w i t)) ,@ts)
160 `((,w . ,t) ,@(set (- i w) ts)))]))
161 (assume-type sl <skew-list>)
162 (SL (set n (skew-list-elements sl))))
163
164 ;;;
165 ;;; Conversion
166 ;;;
167
168 ;; Input may be an improper list. Returns SL and the last cdr.
169 (define (list*->skew-list lis)
170 (if (pair? lis)
171 (let1 spine-len (let loop ((lis lis) (n 0))
172 (if (pair? lis) (loop (cdr lis) (+ n 1)) n))
173 ;; divide n into (k0 k1 ...) where each k is 2^j-1 and decreasing order
174 (define (series-2^n-1 n)
175 (cond [(= n 0) '()]
176 [(= n 1) '(1)]
177 [else (let1 k (- (ash 1 (- (integer-length (+ n 1)) 1)) 1)
178 (cons k (series-2^n-1 (- n k))))]))
179 ;; make tree from first n elts of lis (n = 2^j-1)
180 ;; returns the rest of the lis as well,
181 ;; being careful not to copy the spine of lis.
182 (define (make-tree n lis)
183 (if (= n 1)
184 (values `(Leaf ,(car lis)) (cdr lis))
185 (let1 n2 (ash (- n 1) -1)
186 (receive (t1 rest) (make-tree n2 (cdr lis))
187 (receive (t2 rest) (make-tree n2 rest)
188 (values `(Node ,(car lis) ,t1 ,t2) rest))))))
189 ;; get reversed series-2^n-1
190 ;; returns [(Size . Tree)] and the last cdr of lis
191 (define (make-forest ns lis)
192 (if (null? ns)
193 (values '() lis)
194 (receive (tree rest) (make-tree (car ns) lis)
195 (receive (forest last-cdr) (make-forest (cdr ns) rest)
196 (values (acons (car ns) tree forest) last-cdr)))))
197 ;; Build one.
198 (receive (forest last-cdr)
199 (make-forest (reverse (series-2^n-1 spine-len)) lis)
200 (values (SL forest) last-cdr)))
201 (values skew-list-null lis)))
202
203 (define (list->skew-list lis)
204 (receive (sl last-cdr) (list*->skew-list lis)
205 (unless (null? last-cdr)
206 (error "proper list required, but got" lis))
207 sl))
208
209 (define (skew-list->list sl)
210 (assume-type sl <skew-list>)
211 (reverse (skew-list-fold sl cons '())))
212
213 ;;;
214 ;;; Comparison
215 ;;;
216
217 (define-method object-equal? ((a <skew-list>) (b <skew-list>))
218 (equal? (skew-list-elements a)
219 (skew-list-elements b)))
220
221 ;;;
222 ;;; Utilities
223 ;;;
224
225 (define (skew-list-fold sl proc seed)
226 (define (tree-fold tree seed)
227 (match tree
228 [('Leaf x) (proc x seed)]
229 [('Node x t1 t2)
230 (tree-fold t2 (tree-fold t1 (proc x seed)))]))
231 (assume-type sl <skew-list>)
232 (fold (^[p s] (tree-fold (cdr p) s)) seed (skew-list-elements sl)))
233
234 ;; NB: We don't support general (n-ary) map; it can be done via
235 ;; sequence framework. One arg map is worth to support, for we can take
236 ;; advantage of isomorphism of input and output.
237 (define (skew-list-map sl f)
238 (define (tmap tree)
239 (match tree
240 [('Leaf x) `(Leaf ,(f x))]
241 [('Node x t0 t1) `(Node ,(f x) ,(tmap t0) ,(tmap t1))]))
242 (SL (map (^p `(,(car p) . ,(tmap (cdr p)))) (skew-list-elements sl))))
243
244 (define (skew-list-length sl)
245 (assume-type sl <skew-list>)
246 (fold (^[p s] (+ (car p) s)) 0 (skew-list-elements sl)))
247
248 (define (skew-list-length<=? sl k)
249 (assume-type sl <skew-list>)
250 (let loop ([es (skew-list-elements sl)] [s 0])
251 (cond [(< k s) #f]
252 [(null? es) #t]
253 [else (loop (cdr es) (+ s (caar es)))])))
254
255 ;; Tree, Int, Int, [Tree] -> [Tree]
256 ;; Given Tree of size N, returns [Tree] which includes the K-th element
257 ;; and after. The last input is the tail of the output.
258 (define (tree-kth-and-after t n k tail)
259 (if (zero? k)
260 (cons t tail)
261 (match-let1 ('Node _ t1 t2) t
262 (let1 m (/2 n)
263 (if (<= k m)
264 (tree-kth-and-after t1 m (- k 1) (cons t2 tail))
265 (tree-kth-and-after t2 m (- k m 1) tail))))))
266
267 ;; [(Int, Tree)], Int -> [(Int, Tree)], Int
268 ;; Skips elts in seq that doesn't contain K-th element. Returns offset as well.
269 (define (skip-seq seq k)
270 (if (< k (caar seq))
271 (values seq k)
272 (skip-seq (cdr seq) (- k (caar seq)))))
273
274 (define (%skew-list-iterator sl start end_)
275 (define seq (skew-list-elements sl))
276 (define stack '()) ; [Tree]
277 (define end (or end_ (skew-list-length sl)))
278 (define pos start)
279 (define (next)
280 (if (= pos end)
281 (values #f #t)
282 (match stack
283 [() (set! stack (list (cdr (pop! seq)))) (next)]
284 [(('Leaf x) . xs) (set! stack xs) (inc! pos)(values x #f)]
285 [(('Node x t1 t2) . xs) (set! stack (list* t1 t2 xs)) (inc! pos) (values x #f)])))
286 ;; Adjust start point
287 (unless (<= start end) (errorf "start ~s is greater than end ~s" start end))
288 (when (< 0 start)
289 (receive (seq_ k) (skip-seq seq start)
290 (set! stack (tree-kth-and-after (cdar seq_) (caar seq_) k '()))
291 (set! seq (cdr seq_))))
292 next)
293
294 (define (skew-list->generator sl :optional start end)
295 (define iter (%skew-list-iterator sl
296 (if (undefined? start) 0 start)
297 (if (undefined? end) #f end)))
298 (^[] (receive (x eof?) (iter)
299 (if eof? (eof-object) x))))
300
301 (define (skew-list->lseq sl :optional start end)
302 (define iter (%skew-list-iterator sl
303 (if (undefined? start) 0 start)
304 (if (undefined? end) #f end)))
305 ((rec (loop)
306 (receive (x eof?) (iter)
307 (if eof?
308 '()
309 (lcons x (loop)))))))
310
311 ;; take/drop first k elements
312 ;; In some cases we can share the some of the trees in the original skew-list.
313 ;; Other than the obvious cases when k is the sum of prefix of the original
314 ;; seq, there are some nontrivial cases. Suppose 1 < n and n = 2m+1.
315 ;; If original seq begins with:
316 ;; [1 n ...] -> We can take 2 and 2+m if m>1
317 ;; (e.g. from [1 7 ..] we can take [1 1] and [1 1 3]
318 ;; [n ...] -> We can take 1, 2, 1+m, 2+m' (where m = 2m'+1)
319 ;; (e.g. from [15 ...] we can take [1 7], [1 1 3]
320
321 (define (%skew-list-splitter sl k rettype)
322 ;; The branch logic is common among take, drop and split-at. This macro
323 ;; dispatches the return value.
324 (define-syntax ret
325 (syntax-rules ()
326 [(_ taken dropped)
327 (case rettype
328 [(take) (SL taken)]
329 [(drop) (SL dropped)]
330 [(split) (cons (SL taken) (SL dropped))])]))
331 (define elts (skew-list-elements sl))
332 (define (trivial-prefix)
333 (let loop ([seq elts] [sum 0] [i 0])
334 (cond [(= k sum) (ret (take elts i) (drop elts i))]
335 [(> k sum) (loop (cdr seq) (+ sum (caar seq)) (+ i 1))]
336 [else #f])))
337 (define (special-prefix)
338 (match (skew-list-elements sl)
339 [((1 . x) (n . ('Node y t1 t2)) . zs)
340 (if (= k 2)
341 (ret `((1 . ,x) (1 . (Leaf ,y)))
342 `((,(/2 n) . ,t1) (,(/2 n) . ,t2) ,@zs))
343 (and (> n 3)
344 (= k (+ 2 (/2 n)))
345 (ret `((1 . ,x) (1 . (Leaf ,y)) (,(/2 n) . ,t1))
346 `((,(/2 n) . ,t2) ,@zs))))]
347 [((n . ('Node x (and ('Node y t11 t12) t1) t2)) . zs)
348 (cond [(= k 1) (ret `((1 . (Leaf ,x)))
349 `((,(/2 n) . ,t1) (,(/2 n) . ,t2) ,@zs))]
350 [(= k 2) (ret `((1 . (Leaf ,x)) (1 . (Leaf ,y)))
351 `((,(/4 n) . ,t11) (,(/4 n) . ,t12) (,(/2 n) . ,t2) ,@zs))]
352 [(= k (+ 1 (/2 n)))
353 (ret `((1 . (Leaf ,x)) (,(/2 n) . ,t1))
354 `((,(/2 n) . ,t2) ,@zs))]
355 [(and (> k 3) (= k (+ 2 (/4 n))) )
356 (ret `((1 . (Leaf ,x)) (1 . (Leaf ,y)) (,(/4 n) . ,t11))
357 `((,(/4 n) . ,t12) (,(/2 n) . ,t2) ,@zs))]
358 [else #f])]
359 [((n . ('Node x ('Leaf y) t2)) . zs)
360 (cond [(= k 1) (ret `((1 . (Leaf ,x)))
361 `((1 . (Leaf ,y)) (,(/2 n) . ,t2) ,@zs))]
362 [(= k 2) (ret `((1 . (Leaf ,x)) (1 . (Leaf ,y)))
363 `((,(/2 n) . ,t2) ,@zs))]
364 [else #f])]))
365 (define (fallback)
366 (case rettype
367 [(take) (list->skew-list (skew-list->lseq sl 0 k))]
368 [(drop) (list->skew-list (skew-list->lseq sl k))]
369 [(split) (let1 lis (skew-list->list sl)
370 (receive (t d) (split-at lis k)
371 (cons (list->skew-list t) (list->skew-list d))))]))
372 (or (trivial-prefix)
373 (special-prefix)
374 (fallback)))
375
376 (define (skew-list-take sl k) (%skew-list-splitter sl k 'take))
377 (define (skew-list-drop sl k) (%skew-list-splitter sl k 'drop))
378 (define (skew-list-split-at sl k)
379 (let1 r (%skew-list-splitter sl k 'split)
380 (values (car r) (cdr r))))
381
382 (define (skew-list-append sl . sls)
383 (cond [(null? sls) sl]
384 [(skew-list-empty? sl) (apply skew-list-append sls)]
385 [(not (skew-list? sl)) (error "argument must be a skew list:" sl)]
386 [else (%skew-list-append2 sl (apply skew-list-append sls))]))
387
388 (define (%skew-list-append2 sl1 sl2)
389 (define (slow-append sl1 sl2)
390 (list->skew-list (append (skew-list->list sl1) (skew-list->list sl2))))
391 (match (skew-list-elements sl1)
392 [((1 . ('Leaf x))) (skew-list-cons x sl2)]
393 [((w0 . t0))
394 (match-let1 ((w1 . t1) . ts) (skew-list-elements sl2)
395 (if (= w0 w1)
396 (SL (cons (car (skew-list-elements sl1)) (skew-list-elements sl2)))
397 (slow-append sl1 sl2)))]
398 [_
399 (match-let1 (wz . tz) (last (skew-list-elements sl1))
400 (match-let1 ((w1 . t1) . ts) (skew-list-elements sl2)
401 (if (< wz w1)
402 (SL (append (skew-list-elements sl1) (skew-list-elements sl2)))
403 (slow-append sl1 sl2))))]))
404
405
406 ;;;
407 ;;; Collection & sequence protocol
408 ;;;
409
410 (define-method call-with-iterator ((sl <skew-list>) proc)
411 (define iter (%skew-list-iterator sl 0 #f))
412 (define-values (item end) (iter))
413 (define (end?) end)
414 (define (next) (begin0 item
415 (set!-values (item end) (iter))))
416 (proc end? next))
417
418 (define-method call-with-builder ((slc <skew-list-meta>) proc :allow-other-keys)
419 (let1 q (make-queue)
420 (proc (cut enqueue! q <>)
421 (cut list->skew-list (dequeue-all! q)))))
422
423 (define-method fold (proc knil (sl <skew-list>))
424 (skew-list-fold sl proc knil))
425
426 (define-method size-of ((sl <skew-list>)) (skew-list-length sl))
427
428 (define-method referencer ((sl <skew-list>))
429 (^[o i] (skew-list-ref o i)))