| 1 |
;;; |
| 2 |
;;; scheme.mapping - mappings (R7RS Tangerine) |
| 3 |
;;; |
| 4 |
;;; Copyright (c) 2017-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 |
;; Originally SRFI-146 |
| 35 |
(define-module scheme.mapping |
| 36 |
(export mapping mapping-unfold mapping/ordered mapping-unfold/ordered |
| 37 |
mapping? mapping-contains? mapping-empty? mapping-disjoint? |
| 38 |
mapping-ref mapping-ref/default |
| 39 |
mapping-key-comparator |
| 40 |
|
| 41 |
mapping-set mapping-set! |
| 42 |
mapping-adjoin mapping-adjoin! |
| 43 |
mapping-replace mapping-replace! |
| 44 |
mapping-delete mapping-delete! |
| 45 |
mapping-delete-all mapping-delete-all! |
| 46 |
mapping-intern mapping-intern! |
| 47 |
mapping-update mapping-update! |
| 48 |
mapping-update/default mapping-update!/default |
| 49 |
mapping-pop mapping-pop! |
| 50 |
mapping-search mapping-search! |
| 51 |
mapping-size mapping-find mapping-count |
| 52 |
mapping-any? mapping-every? |
| 53 |
mapping-keys mapping-values mapping-entries |
| 54 |
mapping-map mapping-map->list mapping-for-each mapping-fold |
| 55 |
mapping-filter mapping-filter! mapping-remove mapping-remove! |
| 56 |
mapping-partition mapping-partition! |
| 57 |
mapping-copy mapping->alist alist->mapping alist->mapping! |
| 58 |
alist->mapping/ordered alist->mapping/ordered! |
| 59 |
|
| 60 |
mapping=? mapping<? mapping>? mapping<=? mapping>=? |
| 61 |
mapping-union mapping-intersection mapping-difference mapping-xor |
| 62 |
mapping-union! mapping-intersection! mapping-difference! mapping-xor! |
| 63 |
make-mapping-comparator |
| 64 |
mapping-comparator |
| 65 |
mapping-min-key mapping-max-key |
| 66 |
mapping-min-value mapping-max-value |
| 67 |
mapping-key-predecessor mapping-key-successor |
| 68 |
mapping-range= mapping-range< mapping-range> |
| 69 |
mapping-range<= mapping-range>= |
| 70 |
mapping-range=! mapping-range<! mapping-range>! |
| 71 |
mapping-range<=! mapping-range>=! |
| 72 |
mapping-split |
| 73 |
mapping-catenate mapping-catenate! |
| 74 |
mapping-map/monotone mapping-map/monotone! |
| 75 |
mapping-fold/reverse |
| 76 |
|
| 77 |
;; builtin |
| 78 |
comparator?)) |
| 79 |
(select-module scheme.mapping) |
| 80 |
|
| 81 |
;; We provide <tree-map> as mapping. |
| 82 |
(define <mapping> <tree-map>) |
| 83 |
(define (mapping? m) (is-a? m <mapping>)) |
| 84 |
|
| 85 |
(define-syntax dopairs |
| 86 |
(syntax-rules () |
| 87 |
[(_ [k v lis] body ...) |
| 88 |
(let1 lis lis |
| 89 |
(do ([xs lis (cddr xs)]) |
| 90 |
[(null? xs)] |
| 91 |
(when (null? (cdr xs)) |
| 92 |
(error "mapping kv-list isn't even:" lis)) |
| 93 |
(let ([k (car xs)] |
| 94 |
[v (cadr xs)]) |
| 95 |
body ...)))])) |
| 96 |
|
| 97 |
(define (mapping comparator . args) |
| 98 |
(assume-type comparator <comparator>) |
| 99 |
(rlet1 m (make-tree-map comparator) |
| 100 |
(dopairs [k v args] (tree-map-adjoin! m k v)))) |
| 101 |
|
| 102 |
(define (mapping-unfold p f g seed comparator) |
| 103 |
(assume-type comparator <comparator>) |
| 104 |
(rlet1 m (make-tree-map comparator) |
| 105 |
(do ([seed seed (g seed)]) |
| 106 |
[(p seed) m] |
| 107 |
(receive (k v) (f seed) |
| 108 |
(tree-map-adjoin! m k v))))) |
| 109 |
|
| 110 |
;; We don't take advantage of, neither check, the ordered keys. |
| 111 |
(define mapping/ordered mapping) |
| 112 |
(define mapping-unfold/ordered mapping-unfold) |
| 113 |
|
| 114 |
(define (mapping-empty? m) (tree-map-empty? m)) |
| 115 |
(define (mapping-contains? m key) (tree-map-exists? m key)) |
| 116 |
(define (mapping-disjoint? m1 m2) |
| 117 |
(assume-type m1 <mapping>) |
| 118 |
(assume-type m2 <mapping>) |
| 119 |
(tree-map-seek m1 (^[k _] (tree-map-exists? m2 k)) |
| 120 |
(^[] #t) |
| 121 |
(^[r k v] #f))) |
| 122 |
|
| 123 |
(define %unique (list #f)) |
| 124 |
|
| 125 |
(define (mapping-ref m key |
| 126 |
:optional |
| 127 |
(failure #f) |
| 128 |
(success identity)) |
| 129 |
(assume-type m <mapping>) |
| 130 |
(if failure |
| 131 |
(let1 v (tree-map-get m key %unique) |
| 132 |
(if (eq? v %unique) |
| 133 |
(failure) |
| 134 |
(success v))) |
| 135 |
(success (tree-map-get m key)))) ;let tree-map-get handle failure |
| 136 |
|
| 137 |
(define (mapping-ref/default m key default) |
| 138 |
(assume-type m <mapping>) |
| 139 |
(tree-map-get m key default)) |
| 140 |
|
| 141 |
(define (mapping-key-comparator m) (tree-map-comparator m)) |
| 142 |
|
| 143 |
(define (mapping-set m . args) |
| 144 |
(if (null? args) |
| 145 |
(begin |
| 146 |
(assume-type m <mapping>) |
| 147 |
m) ;shortcut |
| 148 |
(apply mapping-set! (mapping-copy m) args))) |
| 149 |
|
| 150 |
(define (mapping-set! m . args) |
| 151 |
(assume-type m <mapping>) |
| 152 |
(dopairs [k v args] (tree-map-put! m k v)) |
| 153 |
m) |
| 154 |
|
| 155 |
(define (mapping-adjoin m . args) |
| 156 |
(if (null? args) |
| 157 |
(begin |
| 158 |
(assume-type m <mapping>) |
| 159 |
m) ;shortcut |
| 160 |
(apply mapping-adjoin! (tree-map-copy m) args))) |
| 161 |
|
| 162 |
(define (mapping-adjoin! m . args) |
| 163 |
(assume-type m <mapping>) |
| 164 |
(dopairs [k v args] (tree-map-adjoin! m k v)) |
| 165 |
m) |
| 166 |
|
| 167 |
(define (mapping-replace m k v) |
| 168 |
(assume-type m <mapping>) |
| 169 |
(if (tree-map-exists? m k) |
| 170 |
(mapping-replace! (tree-map-copy m) k v) |
| 171 |
m)) |
| 172 |
|
| 173 |
(define (mapping-replace! m k v) |
| 174 |
(assume-type m <mapping>) |
| 175 |
(tree-map-replace! m k v) |
| 176 |
m) |
| 177 |
|
| 178 |
(define (mapping-delete m . keys) (mapping-delete-all m keys)) |
| 179 |
(define (mapping-delete! m . keys) (mapping-delete-all! m keys)) |
| 180 |
|
| 181 |
(define (mapping-delete-all m keys) |
| 182 |
(assume-type m <mapping>) |
| 183 |
;; We delay copy until we actually modify the map. |
| 184 |
(fold (^[k t] |
| 185 |
(if (tree-map-exists? t k) |
| 186 |
(rlet1 t (if (eq? t m) (tree-map-copy m) t) |
| 187 |
(tree-map-delete! t k)) |
| 188 |
t)) |
| 189 |
m keys)) |
| 190 |
|
| 191 |
(define (mapping-delete-all! m keys) |
| 192 |
(assume-type m <mapping>) |
| 193 |
(dolist [k keys] (tree-map-delete! m k)) |
| 194 |
m) |
| 195 |
|
| 196 |
(define (mapping-intern m k newval) |
| 197 |
(assume-type m <mapping>) |
| 198 |
(let1 v (tree-map-get m k %unique) |
| 199 |
(if (eq? v %unique) |
| 200 |
(let ([t (tree-map-copy m)] |
| 201 |
[v (newval)]) |
| 202 |
(tree-map-put! t k v) |
| 203 |
(values t v)) |
| 204 |
(values m v)))) |
| 205 |
|
| 206 |
(define (mapping-intern! m k newval) |
| 207 |
(assume-type m <mapping>) |
| 208 |
(let1 v (tree-map-get m k %unique) |
| 209 |
(if (eq? v %unique) |
| 210 |
(let1 v (newval) |
| 211 |
(tree-map-put! m k v) |
| 212 |
(values m v)) |
| 213 |
(values m v)))) |
| 214 |
|
| 215 |
(define (mapping-update m k updater |
| 216 |
:optional |
| 217 |
(failure (^[] (errorf "~s doesn't have a key ~s" m k))) |
| 218 |
(success identity)) |
| 219 |
(assume-type m <mapping>) |
| 220 |
;; We delay copy until we actually modify the map. |
| 221 |
(let* ([v (tree-map-get m k %unique)] |
| 222 |
[v1 (if (eq? v %unique) |
| 223 |
(updater (failure)) |
| 224 |
(updater (success v)))]) |
| 225 |
(if (eq? v v1) |
| 226 |
m ; no action needed |
| 227 |
(rlet1 t (tree-map-copy m) |
| 228 |
(tree-map-put! t k v1))))) |
| 229 |
|
| 230 |
(define (mapping-update! m k updater |
| 231 |
:optional |
| 232 |
(failure (^[] (errorf "~s doesn't have a key ~s" m k))) |
| 233 |
(success identity)) |
| 234 |
(assume-type m <mapping>) |
| 235 |
(let* ([v (tree-map-get m k %unique)] |
| 236 |
[v1 (if (eq? v %unique) |
| 237 |
(updater (failure)) |
| 238 |
(updater (success v)))]) |
| 239 |
(tree-map-put! m k v1)) |
| 240 |
m) |
| 241 |
|
| 242 |
(define (mapping-update/default m k updater default) |
| 243 |
(mapping-update m k updater (lambda () default))) |
| 244 |
|
| 245 |
(define (mapping-update!/default m k updater default) |
| 246 |
(mapping-update! m k updater (lambda () default))) |
| 247 |
|
| 248 |
(define (mapping-pop! m |
| 249 |
:optional |
| 250 |
(failure (^[] (error "can't pop from an empty map")))) |
| 251 |
(assume-type m <mapping>) |
| 252 |
(if-let1 p (tree-map-pop-min! m) |
| 253 |
(values m (car p) (cdr p)) |
| 254 |
(failure))) |
| 255 |
|
| 256 |
(define (mapping-pop m |
| 257 |
:optional |
| 258 |
(failure (^[] (error "can't pop from an empty map")))) |
| 259 |
(assume-type m <mapping>) |
| 260 |
(if (tree-map-empty? m) |
| 261 |
(failure) ;avoid unnecessary copying |
| 262 |
(mapping-pop! (mapping-copy m)))) |
| 263 |
|
| 264 |
(define (mapping-search m k failure success) |
| 265 |
(assume-type m <mapping>) |
| 266 |
(let1 v (tree-map-get m k %unique) |
| 267 |
(if (eq? v %unique) |
| 268 |
(failure (^[v o] (let1 m (tree-map-copy m) ;insert |
| 269 |
(tree-map-put! m k v) |
| 270 |
(values m o))) |
| 271 |
(^[o] (values m o))) ;ignore |
| 272 |
(success k v |
| 273 |
(^[k v o] (let1 m (tree-map-copy m) ;update |
| 274 |
(tree-map-put! m k v) |
| 275 |
(values m o))) |
| 276 |
(^[o] (let1 m (tree-map-copy m) ;remove |
| 277 |
(tree-map-delete! m k) |
| 278 |
(values m o))))))) |
| 279 |
|
| 280 |
(define (mapping-search! m k failure success) |
| 281 |
(assume-type m <mapping>) |
| 282 |
(let1 v (tree-map-get m k %unique) |
| 283 |
(if (eq? v %unique) |
| 284 |
(failure (^[v o] (tree-map-put! m k v) (values m o)) ;insert |
| 285 |
(^[o] (values m o))) ;ignore |
| 286 |
(success v |
| 287 |
(^[k v o] (tree-map-put! m k v) (values m o)) ;update |
| 288 |
(^[o] (tree-map-delete! m k) (values m o)))))) ;remove |
| 289 |
|
| 290 |
(define (mapping-size m) |
| 291 |
(assume-type m <mapping>) |
| 292 |
(tree-map-num-entries m)) |
| 293 |
|
| 294 |
(define (mapping-find pred m failure) |
| 295 |
(assume-type m <mapping>) |
| 296 |
(tree-map-seek m pred failure (^[r k v] (values k v)))) |
| 297 |
|
| 298 |
(define (mapping-count pred m) |
| 299 |
(assume-type m <mapping>) |
| 300 |
(tree-map-fold m (^[k v c] (if (pred k v) (+ 1 c) c)) 0)) |
| 301 |
|
| 302 |
(define (mapping-any? pred m) |
| 303 |
(assume-type m <mapping>) |
| 304 |
(tree-map-seek m pred (^[] #f) (^[r k v] #t))) |
| 305 |
|
| 306 |
(define (mapping-every? pred m) |
| 307 |
(assume-type m <mapping>) |
| 308 |
(tree-map-seek m (^[k v] (not (pred k v))) (^[] #t) (^[r k v] #f))) |
| 309 |
|
| 310 |
(define (mapping-keys m) (tree-map-keys m)) |
| 311 |
(define (mapping-values m) (tree-map-values m)) |
| 312 |
|
| 313 |
(define (mapping-entries m) |
| 314 |
(values (tree-map-keys m) (tree-map-values m))) |
| 315 |
|
| 316 |
(define (mapping-map proc cmpr m) |
| 317 |
(assume-type m <mapping>) |
| 318 |
(assume-type cmpr <comparator>) |
| 319 |
(rlet1 r (make-tree-map cmpr) |
| 320 |
(tree-map-for-each m (^[k v] (receive [k v] (proc k v) |
| 321 |
(tree-map-put! r k v)))))) |
| 322 |
|
| 323 |
(define (mapping-for-each proc m) |
| 324 |
(assume-type m <mapping>) |
| 325 |
(tree-map-for-each m proc)) |
| 326 |
|
| 327 |
(define (mapping-fold kons knil m) |
| 328 |
(assume-type m <mapping>) |
| 329 |
(tree-map-fold m kons knil)) |
| 330 |
|
| 331 |
(define (mapping-map->list proc m) |
| 332 |
(assume-type m <mapping>) |
| 333 |
(tree-map-map m proc)) |
| 334 |
|
| 335 |
(define (mapping-filter pred m) |
| 336 |
(assume-type m <mapping>) |
| 337 |
(rlet1 r (make-tree-map (tree-map-comparator m)) |
| 338 |
(tree-map-for-each m (^[k v] (when (pred k v) |
| 339 |
(tree-map-put! r k v)))))) |
| 340 |
|
| 341 |
(define (mapping-filter! pred m) |
| 342 |
(assume-type m <mapping>) |
| 343 |
(tree-map-for-each m (^[k v] (unless (pred k v) |
| 344 |
(tree-map-delete! m k))))) |
| 345 |
|
| 346 |
(define (mapping-remove pred m) |
| 347 |
(assume-type m <mapping>) |
| 348 |
(rlet1 r (make-tree-map (tree-map-comparator m)) |
| 349 |
(tree-map-for-each m (^[k v] (unless (pred k v) |
| 350 |
(tree-map-put! r k v)))))) |
| 351 |
|
| 352 |
(define (mapping-remove! pred m) |
| 353 |
(assume-type m <mapping>) |
| 354 |
(tree-map-for-each m (^[k v] (when (pred k v) |
| 355 |
(tree-map-delete! m k))))) |
| 356 |
|
| 357 |
(define (mapping-partition pred m) |
| 358 |
(assume-type m <mapping>) |
| 359 |
(let ([f (make-tree-map (tree-map-comparator m))] |
| 360 |
[r (make-tree-map (tree-map-comparator m))]) |
| 361 |
(tree-map-for-each m (^[k v] (if (pred k v) |
| 362 |
(tree-map-put! f k v) |
| 363 |
(tree-map-put! r k v)))) |
| 364 |
(values f r))) |
| 365 |
|
| 366 |
(define (mapping-partition! pred m) |
| 367 |
(assume-type m <mapping>) |
| 368 |
(let1 r (make-tree-map (tree-map-comparator m)) |
| 369 |
(tree-map-for-each m (^[k v] (unless (pred k v) |
| 370 |
(tree-map-delete! m k) |
| 371 |
(tree-map-put! r k v)))) |
| 372 |
(values m r))) |
| 373 |
|
| 374 |
(define (mapping-copy m) |
| 375 |
(assume-type m <mapping>) |
| 376 |
(tree-map-copy m)) |
| 377 |
|
| 378 |
(define (mapping->alist m) |
| 379 |
(assume-type m <mapping>) |
| 380 |
(tree-map-fold-right m acons '())) |
| 381 |
|
| 382 |
(define (alist->mapping cmpr alist) |
| 383 |
(assume-type cmpr <comparator>) |
| 384 |
(rlet1 m (make-tree-map cmpr) |
| 385 |
(dolist [p alist] |
| 386 |
(tree-map-adjoin! m (car p) (cdr p))))) |
| 387 |
|
| 388 |
(define (alist->mapping! m alist) |
| 389 |
(assume-type m <mapping>) |
| 390 |
(dolist [p alist] |
| 391 |
(tree-map-adjoin! m (car p) (cdr p))) |
| 392 |
m) |
| 393 |
|
| 394 |
;; we don't take advantage of, neither check, ordered keys |
| 395 |
(define alist->mapping/ordered alist->mapping) |
| 396 |
(define alist->mapping/ordered! alist->mapping!) |
| 397 |
|
| 398 |
(define (%mapping-cmp v=? pred ms) |
| 399 |
(let loop ([ms ms]) |
| 400 |
(cond [(null? (cdr ms)) #t] |
| 401 |
[(not (eqv? (tree-map-comparator (car ms)) |
| 402 |
(tree-map-comparator (cadr ms)))) |
| 403 |
#f] |
| 404 |
[(tree-map-compare-as-sets (car ms) (cadr ms) v=? #f) |
| 405 |
=> (^r (and (pred r) (loop (cdr ms))))] |
| 406 |
[else #f]))) |
| 407 |
|
| 408 |
(define-syntax define-mapping-cmp |
| 409 |
(syntax-rules () |
| 410 |
[(_ name op) |
| 411 |
(define (name vcmp m . more) |
| 412 |
(assume-type vcmp <comparator>) |
| 413 |
(%mapping-cmp (comparator-equality-predicate vcmp) |
| 414 |
(^[x] (op x 0)) |
| 415 |
(cons m more)))])) |
| 416 |
|
| 417 |
(define-mapping-cmp mapping=? =) |
| 418 |
(define-mapping-cmp mapping<? <) |
| 419 |
(define-mapping-cmp mapping<=? <=) |
| 420 |
(define-mapping-cmp mapping>? >) |
| 421 |
(define-mapping-cmp mapping>=? >=) |
| 422 |
|
| 423 |
(define (%union-2! m1 m2) |
| 424 |
(tree-map-for-each m2 (^[k v] (tree-map-adjoin! m1 k v))) |
| 425 |
m1) |
| 426 |
|
| 427 |
(define (mapping-union! m1 . more) |
| 428 |
(if (null? more) |
| 429 |
m1 |
| 430 |
(apply mapping-union! (%union-2! m1 (car more)) (cdr more)))) |
| 431 |
|
| 432 |
(define (mapping-union m1 . more) |
| 433 |
(apply mapping-union! (mapping-copy m1) more)) |
| 434 |
|
| 435 |
(define (%intersection-2! m1 m2) |
| 436 |
(tree-map-for-each m1 (^[k v] (unless (tree-map-get m2 k #f) |
| 437 |
(tree-map-delete! m1 k)))) |
| 438 |
m1) |
| 439 |
|
| 440 |
(define (mapping-intersection! m1 . more) |
| 441 |
(if (null? more) |
| 442 |
m1 |
| 443 |
(apply mapping-intersection! (%intersection-2! m1 (car more)) (cdr more)))) |
| 444 |
|
| 445 |
(define (mapping-intersection m1 . more) |
| 446 |
(apply mapping-intersection! (mapping-copy m1) more)) |
| 447 |
|
| 448 |
(define (%difference-2! m1 m2) |
| 449 |
(tree-map-for-each m2 (^[k v] (tree-map-delete! m1 k))) |
| 450 |
m1) |
| 451 |
|
| 452 |
(define (mapping-difference! m1 . more) |
| 453 |
(let loop ([m1 m1] [more more]) |
| 454 |
(if (null? more) |
| 455 |
m1 |
| 456 |
(loop (%difference-2! m1 (car more)) (cdr more))))) |
| 457 |
|
| 458 |
(define (mapping-difference m1 . more) |
| 459 |
(apply mapping-difference! (mapping-copy m1) more)) |
| 460 |
|
| 461 |
(define (mapping-xor! m1 m2) |
| 462 |
(tree-map-for-each m2 (^[k v] (if (tree-map-get m1 k #f) |
| 463 |
(tree-map-delete! m1 k) |
| 464 |
(tree-map-put! m1 k v)))) |
| 465 |
m1) |
| 466 |
|
| 467 |
(define (mapping-xor m1 m2) |
| 468 |
(mapping-xor! (mapping-copy m1) m2)) |
| 469 |
|
| 470 |
(define (mapping-min-key m) |
| 471 |
(assume-type m <mapping>) |
| 472 |
(if-let1 p (tree-map-min m) |
| 473 |
(car p) |
| 474 |
(error "Can't get min key from an empty map:" m))) |
| 475 |
|
| 476 |
(define (mapping-max-key m) |
| 477 |
(assume-type m <mapping>) |
| 478 |
(if-let1 p (tree-map-max m) |
| 479 |
(car p) |
| 480 |
(error "Can't get min key from an empty map:" m))) |
| 481 |
|
| 482 |
(define (mapping-min-value m) |
| 483 |
(assume-type m <mapping>) |
| 484 |
(if-let1 p (tree-map-min m) |
| 485 |
(cdr p) |
| 486 |
(error "Can't get min key from an empty map:" m))) |
| 487 |
|
| 488 |
(define (mapping-max-value m) |
| 489 |
(assume-type m <mapping>) |
| 490 |
(if-let1 p (tree-map-max m) |
| 491 |
(cdr p) |
| 492 |
(error "Can't get min key from an empty map:" m))) |
| 493 |
|
| 494 |
(define (mapping-key-predecessor m probe failure) |
| 495 |
(assume-type m <mapping>) |
| 496 |
(receive [k v] (tree-map-predecessor m probe %unique) |
| 497 |
(if (eq? k %unique) |
| 498 |
(failure) |
| 499 |
k))) |
| 500 |
|
| 501 |
(define (mapping-key-successor m probe failure) |
| 502 |
(assume-type m <mapping>) |
| 503 |
(receive [k v] (tree-map-successor m probe %unique) |
| 504 |
(if (eq? k %unique) |
| 505 |
(failure) |
| 506 |
k))) |
| 507 |
|
| 508 |
(define-syntax define-mapping-range |
| 509 |
(syntax-rules () |
| 510 |
[(_ name! name op) |
| 511 |
(begin |
| 512 |
(define (name! m probe) |
| 513 |
(assume-type m <mapping>) |
| 514 |
(let1 cmpr (tree-map-comparator m) |
| 515 |
($ tree-map-for-each m |
| 516 |
(^[k v] (unless (op (comparator-compare cmpr k probe) 0) |
| 517 |
(tree-map-delete! m k))))) |
| 518 |
m) |
| 519 |
(define (name m probe) |
| 520 |
(name! (mapping-copy m) probe)))])) |
| 521 |
|
| 522 |
(define-mapping-range mapping-range=! mapping-range= =) |
| 523 |
(define-mapping-range mapping-range<! mapping-range< <) |
| 524 |
(define-mapping-range mapping-range<=! mapping-range<= <=) |
| 525 |
(define-mapping-range mapping-range>! mapping-range> >) |
| 526 |
(define-mapping-range mapping-range>=! mapping-range>= >=) |
| 527 |
|
| 528 |
(define (mapping-split m probe) |
| 529 |
(assume-type m <mapping>) |
| 530 |
;; no more efficient than calling each one |
| 531 |
(values (mapping-range< m probe) |
| 532 |
(mapping-range<= m probe) |
| 533 |
(mapping-range= m probe) |
| 534 |
(mapping-range>= m probe) |
| 535 |
(mapping-range> m probe))) |
| 536 |
|
| 537 |
(define (%mapping-catenate! cmpr m1 key val m2 reuse?) |
| 538 |
(define (too-small key m) |
| 539 |
(errorf "Catenating key ~s is too small for ~s" key m)) |
| 540 |
(define (too-large key m) |
| 541 |
(errorf "Catenating key ~s is too large for ~s" key m)) |
| 542 |
(cond [(and reuse? (equal? cmpr (tree-map-comparator m1))) |
| 543 |
;; Reuse m1 |
| 544 |
(when (and (not (tree-map-empty? m1)) |
| 545 |
(>= (comparator-compare cmpr (car (tree-map-max m1)) key) 0)) |
| 546 |
(too-small key m1)) |
| 547 |
(tree-map-put! m1 key val) |
| 548 |
($ tree-map-for-each m2 |
| 549 |
(^[k v] |
| 550 |
(when (<= (comparator-compare cmpr k key) 0) |
| 551 |
(too-large key m2)) |
| 552 |
(tree-map-put! m1 k v))) |
| 553 |
m1] |
| 554 |
[(and reuse? (equal? cmpr (tree-map-comparator m2))) |
| 555 |
;; Reuse m2 |
| 556 |
(when (and (not (tree-map-empty? m2)) |
| 557 |
(<= (comparator-compare cmpr (car (tree-map-max m2)) key) 0)) |
| 558 |
(too-large key m2)) |
| 559 |
(tree-map-put! m2 key val) |
| 560 |
($ tree-map-for-each m1 |
| 561 |
(^[k v] |
| 562 |
(when (>= (comparator-compare cmpr k key) 0) |
| 563 |
(too-small key m1)) |
| 564 |
(tree-map-put! m2 k v))) |
| 565 |
m2] |
| 566 |
[else |
| 567 |
(rlet1 m (make-tree-map cmpr) |
| 568 |
(tree-map-put! m key val) |
| 569 |
($ tree-map-for-each m1 |
| 570 |
(^[k v] |
| 571 |
(when (>= (comparator-compare cmpr k key) 0) |
| 572 |
(too-small key m1)) |
| 573 |
(tree-map-put! m k v))) |
| 574 |
($ tree-map-for-each m2 |
| 575 |
(^[k v] |
| 576 |
(when (<= (comparator-compare cmpr k key) 0) |
| 577 |
(too-large key m2)) |
| 578 |
(tree-map-put! m k v))))])) |
| 579 |
|
| 580 |
(define (mapping-catenate cmpr m1 key val m2) |
| 581 |
(%mapping-catenate! cmpr m1 key val m2 #f)) |
| 582 |
(define (mapping-catenate! cmpr m1 key val m2) |
| 583 |
(%mapping-catenate! cmpr m1 key val m2 #t)) |
| 584 |
|
| 585 |
;; We don't take advantage of monotone |
| 586 |
(define (mapping-map/monotone! proc cmpr m) |
| 587 |
(mapping-map proc cmpr m)) |
| 588 |
(define (mapping-map/monotone proc cmpr m) |
| 589 |
(mapping-map proc cmpr m)) |
| 590 |
|
| 591 |
(define (mapping-fold/reverse kons knil m) |
| 592 |
(tree-map-fold-right m kons knil)) |
| 593 |
|
| 594 |
(define (make-mapping-comparator value-cmpr) |
| 595 |
(define (compare a b) |
| 596 |
(tree-map-compare-as-sequences a b value-cmpr)) |
| 597 |
(make-comparator/compare mapping? #t compare #f)) |
| 598 |
|
| 599 |
(define mapping-comparator (make-mapping-comparator default-comparator)) |