| 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)) |