| 1 |
;;; |
| 2 |
;;; scheme.mapping.hash - hashmaps (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.hash |
| 35 |
(define-module scheme.mapping.hash |
| 36 |
(export hashmap hashmap-unfold |
| 37 |
hashmap? hashmap-contains? hashmap-empty? hashmap-disjoint? |
| 38 |
hashmap-ref hashmap-ref/default |
| 39 |
hashmap-key-comparator |
| 40 |
|
| 41 |
hashmap-set hashmap-set! |
| 42 |
hashmap-adjoin hashmap-adjoin! |
| 43 |
hashmap-replace hashmap-replace! |
| 44 |
hashmap-delete hashmap-delete! |
| 45 |
hashmap-delete-all hashmap-delete-all! |
| 46 |
hashmap-intern hashmap-intern! |
| 47 |
hashmap-update hashmap-update! |
| 48 |
hashmap-update/default hashmap-update!/default |
| 49 |
hashmap-pop hashmap-pop! |
| 50 |
hashmap-search hashmap-search! |
| 51 |
hashmap-size hashmap-find hashmap-count |
| 52 |
hashmap-any? hashmap-every? |
| 53 |
hashmap-keys hashmap-values hashmap-entries |
| 54 |
hashmap-map hashmap-map->list hashmap-for-each hashmap-fold |
| 55 |
hashmap-filter hashmap-filter! hashmap-remove hashmap-remove! |
| 56 |
hashmap-partition hashmap-partition! |
| 57 |
hashmap-copy hashmap->alist alist->hashmap alist->hashmap! |
| 58 |
|
| 59 |
hashmap=? hashmap<? hashmap>? hashmap<=? hashmap>=? |
| 60 |
hashmap-union hashmap-intersection hashmap-difference hashmap-xor |
| 61 |
hashmap-union! hashmap-intersection! hashmap-difference! hashmap-xor! |
| 62 |
make-hashmap-comparator |
| 63 |
hashmap-comparator |
| 64 |
|
| 65 |
;; builtin |
| 66 |
comparator?)) |
| 67 |
(select-module scheme.mapping.hash) |
| 68 |
|
| 69 |
;; We provide <hash-table> as hashmap. |
| 70 |
(define <hashmap> <hash-table>) |
| 71 |
(define (hashmap? m) (is-a? m <hashmap>)) |
| 72 |
|
| 73 |
(define-syntax dopairs |
| 74 |
(syntax-rules () |
| 75 |
[(_ [k v lis] body ...) |
| 76 |
(let1 lis lis |
| 77 |
(do ([xs lis (cddr xs)]) |
| 78 |
[(null? xs)] |
| 79 |
(when (null? (cdr xs)) |
| 80 |
(error "mapping kv-list isn't even:" lis)) |
| 81 |
(let ([k (car xs)] |
| 82 |
[v (cadr xs)]) |
| 83 |
body ...)))])) |
| 84 |
|
| 85 |
(define (hashmap comparator . args) |
| 86 |
(assume-type comparator <comparator>) |
| 87 |
(rlet1 m (make-hash-table comparator) |
| 88 |
(dopairs [k v args] (hash-table-adjoin! m k v)))) |
| 89 |
|
| 90 |
(define (hashmap-unfold p f g seed comparator) |
| 91 |
(assume-type comparator <comparator>) |
| 92 |
(rlet1 m (make-hash-table comparator) |
| 93 |
(do ([seed seed (g seed)]) |
| 94 |
[(p seed) m] |
| 95 |
(receive (k v) (f seed) |
| 96 |
(hash-table-adjoin! m k v))))) |
| 97 |
|
| 98 |
(define (hashmap-empty? m) (hash-table-empty? m)) |
| 99 |
(define (hashmap-contains? m key) (hash-table-exists? m key)) |
| 100 |
(define (hashmap-disjoint? m1 m2) |
| 101 |
(assume-type m1 <hashmap>) |
| 102 |
(assume-type m2 <hashmap>) |
| 103 |
(hash-table-seek m1 (^[k _] (hash-table-exists? m2 k)) |
| 104 |
(^[] #t) |
| 105 |
(^[r k v] #f))) |
| 106 |
|
| 107 |
(define %unique (list #f)) |
| 108 |
|
| 109 |
(define (hashmap-ref m key |
| 110 |
:optional |
| 111 |
(failure #f) |
| 112 |
(success identity)) |
| 113 |
(assume-type m <hashmap>) |
| 114 |
(if failure |
| 115 |
(let1 v (hash-table-get m key %unique) |
| 116 |
(if (eq? v %unique) |
| 117 |
(failure) |
| 118 |
(success v))) |
| 119 |
(success (hash-table-get m key)))) ;let hash-table-get handle failure |
| 120 |
|
| 121 |
(define (hashmap-ref/default m key default) |
| 122 |
(assume-type m <hashmap>) |
| 123 |
(hash-table-get m key default)) |
| 124 |
|
| 125 |
(define (hashmap-key-comparator m) (hash-table-comparator m)) |
| 126 |
|
| 127 |
(define (hashmap-set m . args) |
| 128 |
(if (null? args) |
| 129 |
(begin |
| 130 |
(assume-type m <hashmap>) |
| 131 |
m) ;shortcut |
| 132 |
(apply hashmap-set! (hashmap-copy m) args))) |
| 133 |
|
| 134 |
(define (hashmap-set! m . args) |
| 135 |
(assume-type m <hashmap>) |
| 136 |
(dopairs [k v args] (hash-table-put! m k v)) |
| 137 |
m) |
| 138 |
|
| 139 |
(define (hashmap-adjoin m . args) |
| 140 |
(if (null? args) |
| 141 |
(begin |
| 142 |
(assume-type m <hashmap>) |
| 143 |
m) ;shortcut |
| 144 |
(apply hashmap-adjoin! (hash-table-copy m) args))) |
| 145 |
|
| 146 |
(define (hashmap-adjoin! m . args) |
| 147 |
(assume-type m <hashmap>) |
| 148 |
(dopairs [k v args] (hash-table-adjoin! m k v)) |
| 149 |
m) |
| 150 |
|
| 151 |
(define (hashmap-replace m k v) |
| 152 |
(assume-type m <hashmap>) |
| 153 |
(if (hash-table-exists? m k) |
| 154 |
(hashmap-replace! (hash-table-copy m) k v) |
| 155 |
m)) |
| 156 |
|
| 157 |
(define (hashmap-replace! m k v) |
| 158 |
(assume-type m <hashmap>) |
| 159 |
(hash-table-replace! m k v) |
| 160 |
m) |
| 161 |
|
| 162 |
(define (hashmap-delete m . keys) (hashmap-delete-all m keys)) |
| 163 |
(define (hashmap-delete! m . keys) (hashmap-delete-all! m keys)) |
| 164 |
|
| 165 |
(define (hashmap-delete-all m keys) |
| 166 |
(assume-type m <hashmap>) |
| 167 |
;; We delay copy until we actually modify the map. |
| 168 |
(fold (^[k t] |
| 169 |
(if (hash-table-exists? t k) |
| 170 |
(rlet1 t (if (eq? t m) (hash-table-copy m) t) |
| 171 |
(hash-table-delete! t k)) |
| 172 |
t)) |
| 173 |
m keys)) |
| 174 |
|
| 175 |
(define (hashmap-delete-all! m keys) |
| 176 |
(assume-type m <hashmap>) |
| 177 |
(dolist [k keys] (hash-table-delete! m k)) |
| 178 |
m) |
| 179 |
|
| 180 |
(define (hashmap-intern m k newval) |
| 181 |
(assume-type m <hashmap>) |
| 182 |
(let1 v (hash-table-get m k %unique) |
| 183 |
(if (eq? v %unique) |
| 184 |
(let ([t (hash-table-copy m)] |
| 185 |
[v (newval)]) |
| 186 |
(hash-table-put! t k v) |
| 187 |
(values t v)) |
| 188 |
(values m v)))) |
| 189 |
|
| 190 |
(define (hashmap-intern! m k newval) |
| 191 |
(assume-type m <hashmap>) |
| 192 |
(let1 v (hash-table-get m k %unique) |
| 193 |
(if (eq? v %unique) |
| 194 |
(let1 v (newval) |
| 195 |
(hash-table-put! m k v) |
| 196 |
(values m v)) |
| 197 |
(values m v)))) |
| 198 |
|
| 199 |
(define (hashmap-update m k updater |
| 200 |
:optional |
| 201 |
(failure (^[] (errorf "~s doesn't have a key ~s" m k))) |
| 202 |
(success identity)) |
| 203 |
(assume-type m <hashmap>) |
| 204 |
;; We delay copy until we actually modify the map. |
| 205 |
(let* ([v (hash-table-get m k %unique)] |
| 206 |
[v1 (if (eq? v %unique) |
| 207 |
(updater (failure)) |
| 208 |
(updater (success v)))]) |
| 209 |
(if (eq? v v1) |
| 210 |
m ; no action needed |
| 211 |
(rlet1 t (hash-table-copy m) |
| 212 |
(hash-table-put! t k v1))))) |
| 213 |
|
| 214 |
(define (hashmap-update! m k updater |
| 215 |
:optional |
| 216 |
(failure (^[] (errorf "~s doesn't have a key ~s" m k))) |
| 217 |
(success identity)) |
| 218 |
(assume-type m <hashmap>) |
| 219 |
(let* ([v (hash-table-get m k %unique)] |
| 220 |
[v1 (if (eq? v %unique) |
| 221 |
(updater (failure)) |
| 222 |
(updater (success v)))]) |
| 223 |
(hash-table-put! m k v1)) |
| 224 |
m) |
| 225 |
|
| 226 |
(define (hashmap-update/default m k updater default) |
| 227 |
(hashmap-update m k updater (lambda () default))) |
| 228 |
|
| 229 |
(define (hashmap-update!/default m k updater default) |
| 230 |
(hashmap-update! m k updater (lambda () default))) |
| 231 |
|
| 232 |
(define (hashmap-pop! m |
| 233 |
:optional |
| 234 |
(failure (^[] (error "can't pop from an empty map")))) |
| 235 |
(assume-type m <hashmap>) |
| 236 |
;; We cheat to use internal iterator to avoid traversing whole hashtable |
| 237 |
(let1 iter ((with-module gauche.internal %hash-table-iter) m) |
| 238 |
(receive (k v) (iter %unique) |
| 239 |
(if (eq? k %unique) |
| 240 |
(failure) |
| 241 |
(begin |
| 242 |
(hash-table-delete! m k) |
| 243 |
(values m k v)))))) |
| 244 |
|
| 245 |
(define (hashmap-pop m |
| 246 |
:optional |
| 247 |
(failure (^[] (error "can't pop from an empty map")))) |
| 248 |
(assume-type m <hashmap>) |
| 249 |
(if (hash-table-empty? m) |
| 250 |
(failure) ;avoid unnecessary copying |
| 251 |
(hashmap-pop! (hashmap-copy m)))) |
| 252 |
|
| 253 |
(define (hashmap-search m k failure success) |
| 254 |
(assume-type m <hashmap>) |
| 255 |
(let1 v (hash-table-get m k %unique) |
| 256 |
(if (eq? v %unique) |
| 257 |
(failure (^[v o] (let1 m (hash-table-copy m) ;insert |
| 258 |
(hash-table-put! m k v) |
| 259 |
(values m o))) |
| 260 |
(^[o] (values m o))) ;ignore |
| 261 |
(success k v |
| 262 |
(^[k v o] (let1 m (hash-table-copy m) ;update |
| 263 |
(hash-table-put! m k v) |
| 264 |
(values m o))) |
| 265 |
(^[o] (let1 m (hash-table-copy m) ;remove |
| 266 |
(hash-table-delete! m k) |
| 267 |
(values m o))))))) |
| 268 |
|
| 269 |
(define (hashmap-search! m k failure success) |
| 270 |
(assume-type m <hashmap>) |
| 271 |
(let1 v (hash-table-get m k %unique) |
| 272 |
(if (eq? v %unique) |
| 273 |
(failure (^[v o] (hash-table-put! m k v) (values m o)) ;insert |
| 274 |
(^[o] (values m o))) ;ignore |
| 275 |
(success v |
| 276 |
(^[k v o] (hash-table-put! m k v) (values m o)) ;update |
| 277 |
(^[o] (hash-table-delete! m k) (values m o)))))) ;remove |
| 278 |
|
| 279 |
(define (hashmap-size m) |
| 280 |
(assume-type m <hashmap>) |
| 281 |
(hash-table-num-entries m)) |
| 282 |
|
| 283 |
(define (hashmap-find pred m failure) |
| 284 |
(assume-type m <hashmap>) |
| 285 |
(hash-table-seek m pred failure (^[r k v] (values k v)))) |
| 286 |
|
| 287 |
(define (hashmap-count pred m) |
| 288 |
(assume-type m <hashmap>) |
| 289 |
(hash-table-fold m (^[k v c] (if (pred k v) (+ 1 c) c)) 0)) |
| 290 |
|
| 291 |
(define (hashmap-any? pred m) |
| 292 |
(assume-type m <hashmap>) |
| 293 |
(hash-table-seek m pred (^[] #f) (^[r k v] #t))) |
| 294 |
|
| 295 |
(define (hashmap-every? pred m) |
| 296 |
(assume-type m <hashmap>) |
| 297 |
(hash-table-seek m (^[k v] (not (pred k v))) (^[] #t) (^[r k v] #f))) |
| 298 |
|
| 299 |
(define (hashmap-keys m) (hash-table-keys m)) |
| 300 |
(define (hashmap-values m) (hash-table-values m)) |
| 301 |
|
| 302 |
(define (hashmap-entries m) |
| 303 |
(values (hash-table-keys m) (hash-table-values m))) |
| 304 |
|
| 305 |
(define (hashmap-map proc cmpr m) |
| 306 |
(assume-type m <hashmap>) |
| 307 |
(assume-type cmpr <comparator>) |
| 308 |
(rlet1 r (make-hash-table cmpr) |
| 309 |
(hash-table-for-each m (^[k v] (receive [k v] (proc k v) |
| 310 |
(hash-table-put! r k v)))))) |
| 311 |
|
| 312 |
(define (hashmap-for-each proc m) |
| 313 |
(assume-type m <hashmap>) |
| 314 |
(hash-table-for-each m proc)) |
| 315 |
|
| 316 |
(define (hashmap-fold kons knil m) |
| 317 |
(assume-type m <hashmap>) |
| 318 |
(hash-table-fold m kons knil)) |
| 319 |
|
| 320 |
(define (hashmap-map->list proc m) |
| 321 |
(assume-type m <hashmap>) |
| 322 |
(hash-table-map m proc)) |
| 323 |
|
| 324 |
(define (hashmap-filter pred m) |
| 325 |
(assume-type m <hashmap>) |
| 326 |
(rlet1 r (make-hash-table (hash-table-comparator m)) |
| 327 |
(hash-table-for-each m (^[k v] (when (pred k v) |
| 328 |
(hash-table-put! r k v)))))) |
| 329 |
|
| 330 |
(define (hashmap-filter! pred m) |
| 331 |
(assume-type m <hashmap>) |
| 332 |
(hash-table-for-each m (^[k v] (unless (pred k v) |
| 333 |
(hash-table-delete! m k))))) |
| 334 |
|
| 335 |
(define (hashmap-remove pred m) |
| 336 |
(assume-type m <hashmap>) |
| 337 |
(rlet1 r (make-hash-table (hash-table-comparator m)) |
| 338 |
(hash-table-for-each m (^[k v] (unless (pred k v) |
| 339 |
(hash-table-put! r k v)))))) |
| 340 |
|
| 341 |
(define (hashmap-remove! pred m) |
| 342 |
(assume-type m <hashmap>) |
| 343 |
(hash-table-for-each m (^[k v] (when (pred k v) |
| 344 |
(hash-table-delete! m k))))) |
| 345 |
|
| 346 |
(define (hashmap-partition pred m) |
| 347 |
(assume-type m <hashmap>) |
| 348 |
(let ([f (make-hash-table (hash-table-comparator m))] |
| 349 |
[r (make-hash-table (hash-table-comparator m))]) |
| 350 |
(hash-table-for-each m (^[k v] (if (pred k v) |
| 351 |
(hash-table-put! f k v) |
| 352 |
(hash-table-put! r k v)))) |
| 353 |
(values f r))) |
| 354 |
|
| 355 |
(define (hashmap-partition! pred m) |
| 356 |
(assume-type m <hashmap>) |
| 357 |
(let1 r (make-hash-table (hash-table-comparator m)) |
| 358 |
(hash-table-for-each m (^[k v] (unless (pred k v) |
| 359 |
(hash-table-delete! m k) |
| 360 |
(hash-table-put! r k v)))) |
| 361 |
(values m r))) |
| 362 |
|
| 363 |
(define (hashmap-copy m) |
| 364 |
(assume-type m <hashmap>) |
| 365 |
(hash-table-copy m)) |
| 366 |
|
| 367 |
(define (hashmap->alist m) |
| 368 |
(assume-type m <hashmap>) |
| 369 |
(hash-table-fold m acons '())) |
| 370 |
|
| 371 |
(define (alist->hashmap cmpr alist) |
| 372 |
(assume-type cmpr <comparator>) |
| 373 |
(rlet1 m (make-hash-table cmpr) |
| 374 |
(dolist [p alist] |
| 375 |
(hash-table-adjoin! m (car p) (cdr p))))) |
| 376 |
|
| 377 |
(define (alist->hashmap! m alist) |
| 378 |
(assume-type m <hashmap>) |
| 379 |
(dolist [p alist] |
| 380 |
(hash-table-adjoin! m (car p) (cdr p))) |
| 381 |
m) |
| 382 |
|
| 383 |
(define (%hashmap-cmp v=? pred ms) |
| 384 |
(let loop ([ms ms]) |
| 385 |
(cond [(null? (cdr ms)) #t] |
| 386 |
[(not (eqv? (hash-table-comparator (car ms)) |
| 387 |
(hash-table-comparator (cadr ms)))) |
| 388 |
#f] |
| 389 |
[(hash-table-compare-as-sets (car ms) (cadr ms) v=? #f) |
| 390 |
=> (^r (and (pred r) (loop (cdr ms))))] |
| 391 |
[else #f]))) |
| 392 |
|
| 393 |
(define-syntax define-hashmap-cmp |
| 394 |
(syntax-rules () |
| 395 |
[(_ name op) |
| 396 |
(define (name vcmp m . more) |
| 397 |
(assume-type vcmp <comparator>) |
| 398 |
(%hashmap-cmp (comparator-equality-predicate vcmp) |
| 399 |
(^[x] (op x 0)) |
| 400 |
(cons m more)))])) |
| 401 |
|
| 402 |
(define-hashmap-cmp hashmap=? =) |
| 403 |
(define-hashmap-cmp hashmap<? <) |
| 404 |
(define-hashmap-cmp hashmap<=? <=) |
| 405 |
(define-hashmap-cmp hashmap>? >) |
| 406 |
(define-hashmap-cmp hashmap>=? >=) |
| 407 |
|
| 408 |
(define (%union-2! m1 m2) |
| 409 |
(hash-table-for-each m2 (^[k v] (hash-table-adjoin! m1 k v))) |
| 410 |
m1) |
| 411 |
|
| 412 |
(define (hashmap-union! m1 . more) |
| 413 |
(if (null? more) |
| 414 |
m1 |
| 415 |
(apply hashmap-union! (%union-2! m1 (car more)) (cdr more)))) |
| 416 |
|
| 417 |
(define (hashmap-union m1 . more) |
| 418 |
(apply hashmap-union! (hashmap-copy m1) more)) |
| 419 |
|
| 420 |
(define (%intersection-2! m1 m2) |
| 421 |
(hash-table-for-each m1 (^[k v] (unless (hash-table-get m2 k #f) |
| 422 |
(hash-table-delete! m1 k)))) |
| 423 |
m1) |
| 424 |
|
| 425 |
(define (hashmap-intersection! m1 . more) |
| 426 |
(if (null? more) |
| 427 |
m1 |
| 428 |
(apply hashmap-intersection! (%intersection-2! m1 (car more)) (cdr more)))) |
| 429 |
|
| 430 |
(define (hashmap-intersection m1 . more) |
| 431 |
(apply hashmap-intersection! (hashmap-copy m1) more)) |
| 432 |
|
| 433 |
(define (%difference-2! m1 m2) |
| 434 |
(hash-table-for-each m2 (^[k v] (hash-table-delete! m1 k))) |
| 435 |
m1) |
| 436 |
|
| 437 |
(define (hashmap-difference! m1 . more) |
| 438 |
(let loop ([m1 m1] [more more]) |
| 439 |
(if (null? more) |
| 440 |
m1 |
| 441 |
(loop (%difference-2! m1 (car more)) (cdr more))))) |
| 442 |
|
| 443 |
(define (hashmap-difference m1 . more) |
| 444 |
(apply hashmap-difference! (hashmap-copy m1) more)) |
| 445 |
|
| 446 |
(define (hashmap-xor! m1 m2) |
| 447 |
(hash-table-for-each m2 (^[k v] (if (hash-table-get m1 k #f) |
| 448 |
(hash-table-delete! m1 k) |
| 449 |
(hash-table-put! m1 k v)))) |
| 450 |
m1) |
| 451 |
|
| 452 |
(define (hashmap-xor m1 m2) |
| 453 |
(hashmap-xor! (hashmap-copy m1) m2)) |
| 454 |
|
| 455 |
(define (make-hashmap-comparator value-cmpr) |
| 456 |
(define (hash-hash h) |
| 457 |
(let1 key-cmpr (hash-table-comparator h) |
| 458 |
(hash-table-fold h 0 |
| 459 |
(^[k v s] |
| 460 |
(logxor s (combine-hash-value |
| 461 |
(comparator-hash key-cmpr k) |
| 462 |
(comparator-hash value-cmpr v))))))) |
| 463 |
(define (hash-equal? a b) |
| 464 |
(and (hash-table? a) |
| 465 |
(hash-table? b) |
| 466 |
(equal? (hash-table-comparator a) (hash-table-comparator b)) |
| 467 |
(hashmap=? value-cmpr a b))) |
| 468 |
(make-comparator hashmap? hash-equal? #f hash-hash)) |
| 469 |
|
| 470 |
(define hashmap-comparator (make-hashmap-comparator default-comparator)) |