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