Debian Codegraph @

libsrc/data/trie.scm

raw
1 ;; trie.scm - trie
2 ;;
3 ;; Copyright (c) 2005 OOHASHI Daichi, All rights reserved.
4 ;; Copyright (c) 2006-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 ;; [SK] Various people contributed to this module to improve it.
34 ;; See http://practical-scheme.net/wiliki/wiliki.cgi/Gauche:Trie for
35 ;; the details of the discussion (in Japanese). I ended up rewriting
36 ;; almost everything during the course of adjusting APIs to other
37 ;; parts of Gauche, but the discussion was the source of inspiration anyway.
38
39 (define-module data.trie
40 (use gauche.sequence)
41 (use gauche.generator)
42 (use gauche.dictionary)
43 (export <trie>
44 make-trie trie trie-with-keys
45 trie? trie-num-entries trie-exists? trie-partial-key?
46 trie-get trie-put! trie-update! trie-delete!
47 trie-common-prefix
48 trie-common-prefix-keys
49 trie-common-prefix-values
50 trie-common-prefix-fold
51 trie-common-prefix-map
52 trie-common-prefix-for-each
53 trie-longest-match
54 trie->list trie->hash-table
55 trie-keys trie-values trie-fold trie-map trie-for-each
56 call-with-iterator call-with-builder size-of lazy-size-of
57 alist->trie
58 ))
59
60 (select-module data.trie)
61
62 ;; Trie node structure
63 ;;
64 ;; <node> := (<table> <terminal> ...)
65 ;;
66 ;; <terminal> := (<sequence> . <value>)
67 ;;
68 ;; We may have more than one terminal if the Trie contains heterogeneous
69 ;; sequences, e.g. "foo" and (#\f #\o #\o).
70 ;;
71 ;; <table> can be any structure that can map an element of the sequence
72 ;; to other nodes. Hashtables and assoc-lists are handy ones.
73 ;; The actual table can be specified by a set of procedures given
74 ;; to make-trie:
75 ;;
76 ;; tab-make :: () -> table construct an empty table
77 ;; tab-get table, key -> node or #f
78 ;; lookup the table by the key. return #f if there's
79 ;; no entry for the key.
80 ;; tab-put! :: table, key, node -> table
81 ;; put a key&node pair into the table, or delete the
82 ;; entry if node is #f. returned table is used for
83 ;; subsequent opration.
84 ;; tab-fold :: table, (key, node, seed -> seed), seed -> seed
85 ;; iterator on the table entries.
86 ;; tab-empty? :: table -> boolean [ optional ]
87 ;; check if the table is empty or not. may be used for
88 ;; efficient handling of certain apis. when omitted,
89 ;; fold is used but that may need unnecessary walking
90 ;; over the table.
91
92 (define-class <trie-meta> (<class>)
93 ())
94
95 (define-class <trie> (<dictionary>)
96 ((root :init-form (%make-node))
97 (size :init-value 0)
98 (tab-make :init-keyword :tab-make
99 :init-value (cut make-hash-table 'eqv?))
100 (tab-get :init-keyword :tab-get
101 :init-value (cut hash-table-get <> <> #f))
102 (tab-put! :init-keyword :tab-put!
103 :init-value (^[t k v]
104 (if v
105 (hash-table-put! t k v)
106 (hash-table-delete! t k))
107 t))
108 (tab-fold :init-keyword :tab-fold
109 :init-value hash-table-fold)
110 (tab-empty? :init-keyword :tab-empty?
111 :init-value #f)
112 )
113 :metaclass <trie-meta>)
114
115 ;;;===========================================================
116 ;;; Constructors etc.
117 ;;;
118
119 (define (make-trie :optional (tab-make #f) (tab-get #f) (tab-put! #f)
120 (tab-fold #f))
121 (apply make <trie>
122 (cond-list
123 (tab-make @ `(:tab-make ,tab-make))
124 (tab-get @ `(:tab-get ,tab-get))
125 (tab-put! @ `(:tab-put! ,tab-put!))
126 (tab-fold @ `(:tab-fold ,tab-fold)))))
127
128 (define (trie params . keys&vals)
129 (rlet1 t (apply make-trie params)
130 (for-each (^p (trie-put! t (car p) (cdr p))) keys&vals)))
131
132 (define (trie-with-keys params . seqs)
133 (rlet1 t (apply make-trie params)
134 (for-each (^[seq] (trie-put! t seq seq)) seqs)))
135
136 (define (trie? x)
137 (is-a? x <trie>))
138
139 (define (trie-num-entries trie)
140 (slot-ref trie 'size))
141
142 ;;;===========================================================
143 ;;; Lookup and modification
144 ;;;
145
146 ;; internal: node constructor
147 (define (%make-node) (list #f))
148 (define %node-table car)
149 (define %node-terminals cdr)
150
151 (define (%node-table-create trie node)
152 (rlet1 tab ((slot-ref trie 'tab-make))
153 (set! (%node-table node) tab)))
154
155 ;; We don't need to compare entire sequence, for we know all the elements
156 ;; would match. We only need to make sure the class of the sequence match.
157 (define (%node-find-terminal node seq)
158 (let1 c (class-of seq)
159 (find (^p (eq? c (class-of (car p)))) (cdr node))))
160
161 (define (%fallback fallback seq)
162 (if (undefined? fallback)
163 (error "Trie does not have an entry for a key:" seq)
164 fallback))
165
166 ;;
167 ;; Primitive accessors
168 ;; We have three accessors; they are slightly different from each other, and
169 ;; it is simpler to define them separately than compounding them
170 ;; into one routine.
171 ;;
172
173 ;; internal: Trie, [a] -> Maybe Node
174 (define (%trie-get-node trie seq)
175 (define (lookup parent tab elt)
176 ((slot-ref trie 'tab-get) tab elt))
177 (define (descent node elt)
178 (and-let* ([tab (%node-table node)])
179 (lookup node tab elt)))
180 (let1 g (x->generator seq)
181 (let loop ([elt (g)] [node (slot-ref trie 'root)])
182 (if (eof-object? elt)
183 node
184 (and-let* ([next (descent node elt)])
185 (loop (g) next))))))
186
187 ;; internal: Trie, [a] -> Node
188 (define (%trie-get-node-or-create trie seq)
189 (define (lookup parent tab elt)
190 (if-let1 node ((slot-ref trie 'tab-get) tab elt)
191 node
192 (rlet1 node (%make-node)
193 (set! (%node-table parent)
194 ((slot-ref trie 'tab-put!) tab elt node)))))
195 (define (descent node elt)
196 (if-let1 tab (%node-table node)
197 (lookup node tab elt)
198 (lookup node (%node-table-create trie node) elt)))
199 (let1 g (x->generator seq)
200 (let loop ([elt (g)] [node (slot-ref trie 'root)])
201 (if (eof-object? elt)
202 node
203 (and-let* ([next (descent node elt)])
204 (loop (g) next))))))
205
206 ;; internal: Trie, [a] -> Maybe (Key . Value)
207 (define (%trie-get-node-longest trie seq)
208 (define (lookup parent tab elt)
209 ((slot-ref trie 'tab-get) tab elt))
210 (define (descent node elt)
211 (and-let* ([tab (%node-table node)])
212 (lookup node tab elt)))
213 (let1 g (x->generator seq)
214 ;; last holds the last matched (key . value) pair
215 (let loop ([elt (g)]
216 [node (slot-ref trie 'root)]
217 [last (%node-find-terminal (slot-ref trie 'root) seq)])
218 (if (eof-object? elt)
219 last
220 (if-let1 next (descent node elt)
221 (loop (g) next (or (%node-find-terminal next seq) last))
222 last)))))
223
224 ;; internal: Trie, Node -> Boolean
225 (define (%trie-node-empty? trie node)
226 (cond
227 [(slot-ref trie'tab-empty?) => (^[empty?] (empty? node))]
228 ;; some heuristics
229 [(and (hash-table? (%node-table node))
230 (eq? (slot-ref trie'tab-fold) hash-table-fold))
231 (zero? (hash-table-num-entries (%node-table node)))]
232 [(%node-table node) => (cut (slot-ref trie'tab-fold) <> (^[k n s] #t) #f)]
233 [else #t]))
234
235 ;; Public APIs
236
237 (define (trie-exists? trie seq)
238 (and-let1 node (%trie-get-node trie seq)
239 (boolean (%node-find-terminal node seq))))
240
241 ;; trie-partial-key? trie seq
242 ;; returns #t if seq is a pure partial prefix of existing key, that is,
243 ;; there's at least one entry with the key whose pure prefix is seq.
244 ;; seq may be a key itself, but it doesn't count to a partial key.
245 (define (trie-partial-key? trie seq)
246 (and-let1 node (%trie-get-node trie seq)
247 (not (%trie-node-empty? trie node))))
248
249 (define (trie-get trie seq :optional fallback)
250 (or (and-let* ([node (%trie-get-node trie seq)]
251 [p (%node-find-terminal node seq)])
252 (cdr p))
253 (%fallback fallback seq)))
254
255 (define (trie-put! trie seq val)
256 (let* ([node (%trie-get-node-or-create trie seq)]
257 [p (%node-find-terminal node seq)])
258 (cond [p (set-cdr! p val)]
259 [else
260 (push! (%node-terminals node) (cons seq val))
261 (inc! (slot-ref trie 'size))]))
262 (undefined))
263
264 (define (trie-update! trie seq proc :optional fallback)
265 (let* ([node (%trie-get-node-or-create trie seq)]
266 [p (%node-find-terminal node seq)])
267 (cond [p (update! (cdr p) proc)]
268 [else
269 (push! (%node-terminals node)
270 (cons seq (proc (%fallback fallback seq))))
271 (inc! (slot-ref trie 'size))])
272 (undefined)))
273
274 (define (trie-delete! trie seq)
275 ;; TODO: prune a table if it becomes empty
276 (and-let* ([c (class-of seq)]
277 [node (%trie-get-node trie seq)])
278 (update! (cdr node)
279 (^[terminals]
280 (remove (^p (and (eq? (class-of (car p)) c)
281 (begin (dec! (slot-ref trie 'size))
282 #t)))
283 terminals))))
284 (undefined))
285
286 (define (trie-longest-match trie seq :optional fallback)
287 (or (%trie-get-node-longest trie seq)
288 (%fallback fallback seq)))
289
290 ;;;===========================================================
291 ;;; Scanning
292 ;;;
293
294 ;; iterate keys under the given node, depth-first.
295 (define (%trie-node-fold trie node proc seed)
296 (define (fold-descendants seed)
297 (or (and-let* ([tab (%node-table node)])
298 ((slot-ref trie 'tab-fold)
299 tab
300 (^[elt node seed] (%trie-node-fold trie node proc seed))
301 seed))
302 seed))
303 (define (fold-siblings seed)
304 (fold (^[p seed] (proc (car p) (cdr p) seed))
305 seed
306 (%node-terminals node)))
307 (fold-siblings (fold-descendants seed)))
308
309 (define (%trie-prefix-collect trie prefix collector)
310 (or (and-let* ([node (%trie-get-node trie prefix)])
311 ;; NB: we don't need to reverse, since the order of entries
312 ;; are unspecified anyway.
313 (%trie-node-fold trie node collector '()))
314 '()))
315
316 (define (trie-common-prefix trie prefix)
317 (%trie-prefix-collect trie prefix acons))
318
319 (define (trie-common-prefix-keys trie prefix)
320 (%trie-prefix-collect trie prefix (^[k v s] (cons k s))))
321
322 (define (trie-common-prefix-values trie prefix)
323 (%trie-prefix-collect trie prefix (^[k v s] (cons v s))))
324
325 (define (trie-common-prefix-fold trie prefix proc seed)
326 (%trie-node-fold trie (or (%trie-get-node trie prefix) '()) proc seed))
327
328 (define (trie-common-prefix-map trie prefix proc)
329 (trie-common-prefix-fold trie prefix
330 (^[k v s] (cons (proc k v) s))
331 '()))
332
333 (define (trie-common-prefix-for-each trie prefix proc)
334 (trie-common-prefix-fold trie prefix
335 (^[k v s] (proc k v) #f)
336 #f)
337 (undefined))
338
339 (define (trie->list trie)
340 (trie-common-prefix trie '()))
341
342 (define (trie->hash-table trie htype)
343 (rlet1 ht (make-hash-table htype)
344 (trie-for-each trie (cut hash-table-put! ht <> <>))))
345
346 (define (trie-keys trie)
347 (trie-common-prefix-keys trie '()))
348
349 (define (trie-values trie)
350 (trie-common-prefix-values trie '()))
351
352 (define (trie-fold trie proc seed)
353 (trie-common-prefix-fold trie '() proc seed))
354
355 (define (trie-map trie proc)
356 (trie-common-prefix-map trie '() proc))
357
358 (define (trie-for-each trie proc)
359 (trie-common-prefix-for-each trie '() proc))
360
361 ;;;===========================================================
362 ;;; Collection framework
363 ;;;
364
365 (define-method call-with-iterator ((trie <trie>) proc . opts)
366 (define count 0)
367 (define (next)
368 (let/cc return
369 (%trie-node-fold trie (slot-ref trie 'root)
370 (^[key value seed]
371 (let/cc restart
372 (inc! count)
373 (set! next (^[] (restart #f)))
374 (return (cons key value))))
375 #f)))
376 (proc (^[] (= count (trie-num-entries trie)))
377 (^[] (next))))
378
379 (define-method call-with-builder ((class <trie-meta>) proc . opts)
380 (let1 trie (apply make-trie (get-keyword :trie-options opts '()))
381 (proc (^[val]
382 (unless (pair? val)
383 (error "pair required to build a trie, but got" val))
384 (trie-put! trie (car val) (cdr val)))
385 (^[] trie))))
386
387 (define-method size-of ((trie <trie>))
388 (trie-num-entries trie))
389
390 (define-method lazy-size-of ((trie <trie>))
391 (trie-num-entries trie))
392
393 ;; some shortcuts, so that we can avoid call/cc trampolines
394 ;;
395
396 (define-method coerce-to ((class <list-meta>) (trie <trie>))
397 (trie->list trie))
398
399 (define-method coerce-to ((class <vector-meta>) (trie <trie>))
400 (rlet1 vec (make-vector (trie-num-entries trie))
401 (trie-fold trie
402 (^[k v ind]
403 (vector-set! vec ind (cons k v))
404 (+ ind 1))
405 0)))
406
407 (define-method coerce-to ((class <hash-table-meta>) (trie <trie>))
408 (trie->hash-table trie 'equal?))
409
410 (define (alist->trie alist . rest)
411 (apply trie rest alist) )
412
413 ;;;===========================================================
414 ;;; Dictionary framework
415 ;;;
416
417 (define-dict-interface <trie>
418 :get trie-get
419 :put! trie-put!
420 :delete! trie-delete!
421 :exists? trie-exists?
422 :fold trie-fold
423 :for-each trie-for-each
424 :map trie-map
425 :keys trie-keys
426 :values trie-values
427 :update! trie-update!
428 :->alist trie->list
429 :transparent? (^_ #t))