Debian Codegraph @

lib/data/imap.scm

raw
1 ;;;
2 ;;; data.imap - immutable tree map
3 ;;;
4 ;;; Copyright (c) 2015-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 ;; This implements functional red-black tree
35 ;; as described in Chris Okasaki's Purely Functional Data Structures.
36
37 (define-module data.imap
38 (use gauche.sequence)
39 (use gauche.dictionary)
40 (use gauche.record)
41 (use data.queue)
42 (use util.match)
43 (use srfi.114)
44 (export <imap> <imap-meta>
45 make-imap alist->imap tree-map->imap
46 imap? imap-empty?
47 imap-exists? imap-get imap-put
48 imap-delete
49 imap-min imap-max)
50 )
51 (select-module data.imap)
52
53 ;;
54 ;; Internal implementation
55 ;;
56
57 (define-record-type (T (pseudo-rtd <vector>)) #t #t color left elem right)
58 ;; NB: We just use #f as E node.
59 (define (E? x) (not x))
60
61 (define balance
62 (match-lambda*
63 [(or ('B #('R #('R a x b) y c) z d)
64 ('B #('R a x #('R b y c)) z d)
65 ('B a x #('R #('R b y c) z d))
66 ('B a x #('R b y #('R c z d))))
67 (make-T 'R (make-T 'B a x b) y (make-T 'B c z d))]
68 [(color a x b)
69 (make-T color a x b)]))
70
71 (define (get key tree cmpr)
72 (and (T? tree)
73 (match-let1 #(_ a p b) tree
74 (if3 (comparator-compare cmpr key (car p))
75 (get key a cmpr)
76 p
77 (get key b cmpr)))))
78
79 (define (insert key val tree cmpr)
80 (define (ins tree)
81 (if (E? tree)
82 (make-T 'R #f (cons key val) #f)
83 (match-let1 #(color a p b) tree
84 (if3 (comparator-compare cmpr key (car p))
85 (balance color (ins a) p b)
86 (make-T color a (cons key val) b)
87 (balance color a p (ins b))))))
88 (match-let1 #(_ a p b) (ins tree)
89 (make-T 'B a p b)))
90
91 (define (populate tree alist cmpr)
92 ((rec (f tree alist)
93 (if (null? alist)
94 tree
95 (f (insert (caar alist) (cdar alist) tree cmpr) (cdr alist))))
96 tree alist))
97
98 (define (delete key tree cmpr)
99 (define (del-min tree)
100 (match tree
101 [#(color #f p #f) (values p #f)]
102 [#(color #f p b) (values p b)]
103 [#(color a p b) (receive (min-p a.) (del-min a)
104 (values min-p (balance color a. p b)))]))
105 (define (del tree)
106 (if (E? tree)
107 tree
108 (match-let1 #(color a p b) tree
109 (if3 (comparator-compare cmpr key (car p))
110 (balance color (del a) p b)
111 (if a
112 (if b
113 (receive (min-p b.) (del-min b)
114 (balance color a min-p b.))
115 a)
116 b)
117 (balance color a p (del b))))))
118 (match (del tree)
119 [#f #f] ;empty
120 [#(_ a p b) (make-T 'B a p b)]))
121
122 ;; aux fn
123 (define (%key-proc->comparator key=? key<?)
124 (make-comparator #t key=? key<? #f))
125
126 ;;
127 ;; External interface
128 ;;
129 (define-class <imap-meta> (<class>) ())
130
131 (define-class <imap> (<ordered-dictionary>)
132 ((comparator :init-keyword :comparator)
133 (tree :init-keyword :tree :init-form #f))
134 :metaclass <imap-meta>)
135
136 ;; API
137 (define (imap? x) (is-a? x <imap>))
138
139 ;; API
140 (define make-imap
141 (case-lambda
142 [() (make-imap default-comparator)]
143 [(cmpr)
144 (unless (comparator? cmpr)
145 (error "comparator required, but got:" cmpr))
146 (make <imap> :comparator cmpr)]
147 [(key=? key<?) (make-imap (%key-proc->comparator key=? key<?))]))
148
149 ;; API
150 (define alist->imap
151 (case-lambda
152 [(alist) (alist->imap alist default-comparator)]
153 [(alist cmpr)
154 (unless (comparator? cmpr)
155 (error "comparator required, but got:" cmpr))
156 (make <imap>
157 :comparator cmpr :tree (populate #f alist cmpr))]
158 [(alist key=? key<?)
159 (alist->imap alist (%key-proc->comparator key=? key<?))]))
160
161 ;; API
162 (define (tree-map->imap tree-map)
163 (alist->imap (tree-map->alist tree-map)
164 (tree-map-comparator tree-map)))
165
166 ;; API
167 (define (imap-empty? immap) (E? (~ immap'tree)))
168
169 ;; API
170 (define (imap-exists? immap key)
171 (boolean (get key (~ immap'tree) (~ immap'comparator))))
172
173 ;; API
174 (define (imap-get immap key :optional default)
175 (if-let1 p (get key (~ immap'tree) (~ immap'comparator))
176 (cdr p)
177 (if (undefined? default)
178 (errorf "No such key in a imap ~s: ~s" immap key)
179 default)))
180
181 ;; API
182 (define (imap-put immap key val)
183 (make <imap>
184 :comparator (~ immap'comparator)
185 :tree (insert key val (~ immap'tree) (~ immap'comparator))))
186
187 ;; API
188 (define (imap-delete immap key)
189 (make <imap>
190 :comparator (~ immap'comparator)
191 :tree (delete key (~ immap'tree) (~ immap'comparator))))
192
193 ;; API
194 (define (imap-min immap)
195 (define (descend tree)
196 (match-let1 #(_ a p b) tree
197 (if (E? a) p (descend a))))
198 (let1 t (~ immap'tree)
199 (and (not (E? t)) (descend t))))
200
201 ;; API
202 (define (imap-max immap)
203 (define (descend tree)
204 (match-let1 #(_ a p b) tree
205 (if (E? b) p (descend b))))
206 (let1 t (~ immap'tree)
207 (and (not (E? t)) (descend t))))
208
209 ;; Fundamental iterators
210 (define (%imap-fold immap proc seed)
211 (define (rec tree seed)
212 (if (E? tree)
213 seed
214 (match-let1 #(_ a p b) tree
215 (rec b (proc p (rec a seed))))))
216 (rec (~ immap'tree) seed))
217
218 (define (%imap-fold-right immap proc seed)
219 (define (rec tree seed)
220 (if (E? tree)
221 seed
222 (match-let1 #(_ a p b) tree
223 (rec a (proc p (rec b seed))))))
224 (rec (~ immap'tree) seed))
225
226 ;; Collection framework
227 (define-method call-with-iterator ((coll <imap>) proc :allow-other-keys)
228 (if (imap-empty? coll)
229 (proc (^[] #t) (^[] #t))
230 (let1 q (make-queue) ; only contains T
231 (enqueue! q (~ coll'tree))
232 (proc (^[] (queue-empty? q))
233 (rec (next)
234 (match-let1 #(c a p b) (dequeue! q)
235 (if (E? a)
236 (if (E? b)
237 p
238 (begin (queue-push! q b) p))
239 (begin (queue-push! q (make-T c #f p b))
240 (queue-push! q a)
241 (next)))))))))
242
243 (define-method call-with-builder ((class <imap-meta>) proc
244 :key (comparator default-comparator)
245 :allow-other-keys)
246 (define alist '())
247 (proc (^p (push! alist p))
248 (^[] (alist->imap alist comparator))))
249
250 ;; Key comparator
251 (define (imap-comparator imap)
252 (slot-ref imap 'comparator))
253
254 ;; A couple of conversion methods for the efficiency
255 (define-method coerce-to ((c <imap-meta>) (src <list>))
256 (alist->imap src))
257 (define-method coerce-to ((c <imap-meta>) (src <tree-map>))
258 (tree-map->imap src))
259
260 ;; Dictionary interface
261 ;; As a dictionary, it behaves as immutable dictionary.
262 (define-dict-interface <imap>
263 :get imap-get
264 :put! (^[m k v] (error "imap is immutable:" m))
265 :immutable? (^m #t)
266 :fold (^[m proc seed]
267 (%imap-fold m (^[p s] (proc (car p) (cdr p) s)) seed))
268 :fold-right (^[m proc seed]
269 (%imap-fold-right m (^[p s] (proc (car p) (cdr p) s)) seed))
270 :exists? imap-exists?
271 :comparator imap-comparator)