Debian Codegraph @

ext/data/test-trie.scm

raw
1 ;; trie
2 (use gauche.test)
3 (test-start "data.trie")
4 (test-section "data.trie")
5 (use data.trie)
6 (test-module 'data.trie)
7 (use gauche.uvector)
8 (use gauche.sequence)
9 (use scheme.list)
10 (use srfi.13)
11
12 (let* ((strs '("kana" "kanaono" "kanawai" "kanawai koa"
13 "kanawai mele" "kane" "Kane" "kane make" "kane makua"
14 "ku" "kua" "kua`aina" "kua`ana"
15 "liliko`i" "lilinoe" "lili`u" "lilo" "maoli" ""))
16 (lists (map string->list strs))
17 (vecs (map list->vector lists))
18 (uvecs (map string->u8vector strs)))
19
20 ;; string trie tests
21 (let1 t1 (make-trie)
22 (test* "trie: constructor" '(#t 0)
23 (list (trie? t1) (trie-num-entries t1)))
24 (test* "trie: exists?" #f (trie-exists? t1 "kane"))
25
26 (test* "trie: put!" 1
27 (begin (trie-put! t1 "lilo" 4)
28 (trie-num-entries t1)))
29 (test* "trie: get" 4
30 (trie-get t1 "lilo"))
31 (test* "trie: get (error)" (test-error)
32 (trie-get t1 "LILO"))
33 (test* "trie: get (fallback)" 'foo
34 (trie-get t1 "LILO" 'foo))
35
36 (test* "trie: put! more" (length strs)
37 (begin (for-each (lambda (s)
38 (trie-put! t1 s (string-length s)))
39 strs)
40 (trie-num-entries t1)))
41 (test* "trie: get more" #t
42 (every (lambda (s)
43 (= (trie-get t1 s) (string-length s)))
44 strs))
45 (test* "trie: exists? more" #t
46 (every (cut trie-exists? t1 <>) strs))
47 (test* "trie: exists? on partial key" #f
48 (every (cut trie-exists? t1 <>) '("k" "ka" "kan")))
49 (test* "trie: partial-key?"
50 '(("k" #t) ("kana" #t) ("kanawai koa" #f) ("" #t) ("zzz" #f))
51 (map (^k (list k (trie-partial-key? t1 k)))
52 '("k" "kana" "kanawai koa" "" "zzz")))
53 (test* "trie: longest match" '(("kana" . 4)
54 ("kana" . 4)
55 ("kanawai" . 7)
56 ("" . 0))
57 (map (^k (trie-longest-match t1 k #f))
58 '("kana" "kanaoka" "kanawai pele" "mahalo")))
59 (test* "trie: common-prefix" '(19 12 8 4 4 3)
60 (map (^p (length (trie-common-prefix t1 p)))
61 '("" "k" "ka" "ku" "li" "lili")))
62 (test* "trie: common-prefix" '(("kua" . 3)
63 ("kua`aina" . 8)
64 ("kua`ana" . 7))
65 (trie-common-prefix t1 "kua")
66 (cut lset= equal? <> <>))
67 (test* "trie: common-prefix-keys" '("kua" "kua`aina" "kua`ana")
68 (trie-common-prefix-keys t1 "kua")
69 (cut lset= equal? <> <>))
70 (test* "trie: common-prefix-values" '(3 8 7)
71 (trie-common-prefix-values t1 "kua")
72 (cut lset= = <> <>))
73 (test* "trie: common-prefix-fold" 18
74 (trie-common-prefix-fold t1 "kua"
75 (lambda (k v s) (+ v s))
76 0))
77 (test* "trie: common-prefix-map" '("KUA" "KUA`AINA" "KUA`ANA")
78 (trie-common-prefix-map t1 "kua"
79 (lambda (k v) (string-upcase k)))
80 (cut lset= equal? <> <>))
81 (test* "trie: common-prefix-for-each" '("KUA" "KUA`AINA" "KUA`ANA")
82 (let1 p '()
83 (trie-common-prefix-for-each t1 "kua"
84 (lambda (k v)
85 (push! p (string-upcase k))))
86 p)
87 (cut lset= equal? <> <>))
88 (test* "trie: trie-fold" (fold (lambda (k s) (+ (string-length k) s))
89 0 strs)
90 (trie-fold t1 (lambda (k v s) (+ v s)) 0))
91 (test* "trie: trie-map" (fold (lambda (k s) (+ (string-length k) s))
92 0 strs)
93 (apply + (trie-map t1 (lambda (k v) v))))
94 (test* "trie: trie-for-each"
95 (fold (lambda (k s) (+ (string-length k) s))
96 0 strs)
97 (let1 c 0 (trie-for-each t1 (lambda (k v) (inc! c v))) c))
98 (test* "trie: trie->list"
99 (map (^s (cons s (string-length s))) strs)
100 (trie->list t1)
101 (cut lset= equal? <> <>))
102 (test* "trie: trie-keys"
103 strs
104 (trie-keys t1)
105 (cut lset= equal? <> <>))
106 (test* "trie: trie-values"
107 (map string-length strs)
108 (trie-values t1)
109 (cut lset= equal? <> <>))
110 (test* "trie: trie-update!" 16
111 (begin (trie-update! t1 "liliko`i" (cut + <> 8))
112 (trie-get t1 "liliko`i")))
113 (test* "trie: trie-update! (nonexistent)" (test-error)
114 (trie-update! t1 "humuhumu" (cut + <> 8)))
115 (test* "trie: trie-update! (nonexistent)" 16
116 (begin (trie-update! t1 "humuhumu" (cut + <> 8) 8)
117 (trie-get t1 "humuhumu")))
118 (test* "trie: delete!" '(19 #f)
119 (begin (trie-delete! t1 "humuhumu")
120 (list (trie-num-entries t1)
121 (trie-get t1 "humuhumu" #f))))
122 (test* "trie: delete! (nonexistent)" '(19 #f)
123 (begin (trie-delete! t1 "HUMUHUMU")
124 (list (trie-num-entries t1)
125 (trie-get t1 "HUMUHUMU" #f))))
126 (test* "trie: delete! (everything)" 0
127 (begin (for-each (cut trie-delete! t1 <>) strs)
128 (trie-num-entries t1)))
129 )
130 ;; trie and trie-with-keys
131 (let1 t2 (trie '() '("foo" . 0) '("foof" . 1) '("far" . 2))
132 (test* "trie: trie" '(("foo" . 0) ("foof" . 1) ("far" . 2))
133 (trie->list t2)
134 (cut lset= equal? <> <>)))
135 (let1 t3 (trie-with-keys '() "foo" "foof" "far")
136 (test* "trie: trie-with-keys"
137 '(("foo" . "foo") ("foof" . "foof") ("far" . "far"))
138 (trie->list t3)
139 (cut lset= equal? <> <>)))
140
141 ;; heterogeneous tries
142 (let1 t4 (make-trie)
143 (for-each (cut for-each
144 (lambda (seq)
145 (trie-put! t4 seq (class-of seq)))
146 <>)
147 (list strs lists vecs uvecs))
148 (test* "trie(hetero): put!" (* 4 (length strs))
149 (trie-num-entries t4))
150 (test* "trie(hetero): get" <vector> (trie-get t4 '#()))
151 (test* "trie(hetero): get" <u8vector> (trie-get t4 '#u8()))
152 (test* "trie(hetero): get" <pair> (trie-get t4 '(#\k #\u)))
153
154 (test* "trie(hetero): delete!" <string>
155 (begin (trie-delete! t4 '()) (trie-get t4 "")))
156 (test* "trie(hetero): delete!" (* 3 (length strs))
157 (begin (for-each (cut trie-delete! t4 <>) lists)
158 (trie-num-entries t4)))
159 )
160
161 ;; customizing tables
162 (let1 t5 (make-trie list
163 (cut assoc-ref <> <> #f char-ci=?)
164 (lambda (t k v)
165 (if v
166 (assoc-set! t k v char-ci=?)
167 (alist-delete! k t char-ci=?)))
168 (lambda (t f s) (fold f s t)))
169 (test* "trie(custom): put!" (- (length strs) 1)
170 (begin
171 (for-each (^s (trie-put! t5 s (string-length s))) strs)
172 (trie-num-entries t5)))
173 (test* "trie(custom): get" 99
174 (begin
175 (trie-put! t5 "LILIKO`I" 99)
176 (trie-get t5 "liliko`i")))
177 )
178
179 ;; collection api
180 (let1 t6 #f
181 (test* "trie(collection): builder" (length strs)
182 (begin
183 (set! t6 (coerce-to <trie> (map (cut cons <> #t) strs)))
184 (and (trie? t6) (size-of t6))))
185 (test* "trie(collection): iterator" strs
186 (let1 p '()
187 (call-with-iterator t6
188 (lambda (end next)
189 (until (end)
190 (push! p (car (next))))))
191 p)
192 (cut lset= equal? <> <>))
193 (test* "trie(collection): coerce to list" (map (cut cons <> #t) strs)
194 (coerce-to <list> t6)
195 (cut lset= equal? <> <>))
196 (test* "trie(collection): coerce to vector"
197 (map (cut cons <> #t) strs)
198 (vector->list (coerce-to <vector> t6))
199 (cut lset= equal? <> <>))
200 (test* "trie(collection): coerce to hashtable" #t
201 (let1 h (coerce-to <hash-table> t6)
202 (every (cut hash-table-get h <>) strs)))
203 )
204 )
205
206 (test-end)