up.hoon (22599B)
1 :- %say 2 |= [* ~ ~] 3 :- %noun 4 :: priority search queue and LRU cache engines 5 :: 6 |% 7 ++ up 8 ~/ %up 9 |* [k=mold v=mold] 10 :: molds and mold builders 11 :: 12 ~% %core + ~ 13 |% 14 +$ pri :: psq 15 $@ ~ 16 $% [%bin =k p=@ v=buc m=@ l=pri r=pri] 17 [%tip =k p=@ v=buc] 18 == 19 :: 20 +$ buc [=v t=pro] :: collision handling 21 :: 22 +$ pro $@(~ [n=elem t=ltree m=k]) :: internal psq 23 :: 24 +$ elem [=k p=@ =v] :: key, pri, value 25 :: 26 +$ ltree :: loser tree 27 $@ ~ 28 $% [%llos s=@ p=lnode] 29 [%rlos s=@ p=lnode] 30 == 31 :: 32 +$ lnode [n=elem l=ltree m=k r=ltree] :: loser tree node 33 :: 34 +$ torn :: tournament view 35 $@ ~ 36 $% [%sing n=elem] 37 [%play l=pro r=pro] 38 == 39 :: utilities 40 :: 41 ++ lex :: muggish lex order 42 ~/ %lex 43 |= [p=@ k=k q=@ l=k] 44 ^- ? 45 ?: =(p q) 46 (gor k l) 47 (lth p q) 48 :: radix tree utilities 49 :: 50 ++ zero :: mask keeps none 51 ~/ %zero 52 |= [m=@ k=k] 53 ^- ? 54 =(0 (dis (mug k) m)) 55 :: 56 ++ peak :: max unlike bit 57 ~/ %peak 58 |= [k=k l=k] 59 ^- @ 60 (rsh 0 (bex (xeb (mix (mug k) (mug l))))) 61 :: 62 ++ feud :: high bits differ 63 ~/ %feud 64 |= [m=@ k=k l=k] 65 ^- ? 66 =/ n (mix (mix (dec m) 0x7fff.ffff) m) :: 31-bit high mask 67 !=((dis (mug k) n) (dis (mug l) n)) 68 :: 69 ++ rule :: decide branch 70 ~/ %rule :: 71 |= [k=k p=@ v=buc a=pri b=pri] :: a must be nonempty 72 ^- pri 73 =/ l +<.a 74 =/ m (peak k l) 75 ?: (zero m l) 76 [%bin k p v m a b] 77 [%bin k p v m b a] 78 :: 79 ++ fuse :: disjoint tree merge 80 ~/ %fuse 81 |= [m=@ l=pri r=pri] 82 ^- pri 83 ?~ l r 84 ?- -.l 85 %tip 86 ?~ r l 87 :- %bin 88 ?- -.r 89 %tip 90 ?: (lex p.l k.l p.r k.r) 91 [k.l p.l v.l m ~ r] 92 [k.r p.r v.r m l ~] 93 :: 94 %bin 95 ?: (lex p.l k.l p.r k.r) 96 [k.l p.l v.l m ~ r] 97 [k.r p.r v.r m l $(m m.r, l l.r, r r.r)] 98 == 99 :: 100 %bin 101 ?~ r l 102 :- %bin 103 ?- -.r 104 %tip 105 ?: (lex p.l k.l p.r k.r) 106 [k.l p.l v.l m $(m m.l, l l.l, r r.l) r] 107 [k.r p.r v.r m l ~] 108 :: 109 %bin 110 ?: (lex p.l k.l p.r k.r) 111 [k.l p.l v.l m $(m m.l, l l.l, r r.l) r] 112 [k.r p.r v.r m l $(m m.r, l l.r, r r.r)] 113 == 114 == 115 :: 116 ++ funk :: shrink node (left) 117 ~/ %funk 118 |= [k=k p=@ v=buc m=@ l=pri r=pri] 119 ^- pri 120 ?~ l 121 ?~ r 122 [%tip k p v] 123 [%bin k p v m ~ r] 124 [%bin k p v m l r] 125 :: 126 ++ wane :: shrink node (right) 127 ~/ %wane 128 |= [k=k p=@ v=buc m=@ l=pri r=pri] 129 ^- pri 130 ?~ r 131 ?~ l 132 [%tip k p v] 133 [%bin k p v m l ~] 134 [%bin k p v m l r] 135 :: collision resolution 136 :: 137 ++ qor 138 ~% %qor ..qor ~ 139 |% 140 :: loser tree internals 141 :: 142 ++ wyt :: queue size 143 ~/ %wyt 144 |= =pro 145 ^- @ 146 ?~ pro 0 147 +((size t.pro)) 148 :: 149 ++ size :: loser tree size 150 ~/ %size 151 |= t=ltree 152 ^- @ 153 ?~(t 0 s.t) 154 :: 155 ++ llos :: left loser node 156 ~/ %llos 157 |= a=lnode 158 ^- ltree 159 [%llos +((add (size l.a) (size r.a))) a] 160 :: 161 ++ rlos :: right loser node 162 ~/ %rlos 163 |= a=lnode 164 ^- ltree 165 [%rlos +((add (size l.a) (size r.a))) a] 166 :: 167 ++ lbal :: left-balance 168 ~/ %lbal 169 |= a=lnode 170 ^- ltree 171 =/ sl (size l.a) 172 =/ sr (size r.a) 173 ?: (lth (add sl sr) 2) 174 (llos a) 175 ?: (gth sr (mul 4 sl)) 176 ?> ?=(^ r.a) 177 ?: (lth (size l.p.r.a) (size r.p.r.a)) 178 (llsin a) 179 ?- -.r.a 180 %llos (llsin n.a l.a m.a (lrsin p.r.a)) 181 %rlos (llsin n.a l.a m.a (rrsin p.r.a)) 182 == 183 ?: (gth sl (mul 4 sr)) 184 ?> ?=(^ l.a) 185 ?: (gth (size l.p.l.a) (size r.p.l.a)) 186 (lrsin a) 187 ?- -.l.a 188 %llos (lrsin n.a (llsin p.l.a) m.a r.a) 189 %rlos (lrsin n.a (rlsin p.l.a) m.a r.a) 190 == 191 (llos a) 192 :: 193 ++ rbal :: right-balance 194 ~/ %rbal 195 |= a=lnode 196 ^- ltree 197 =/ sl (size l.a) 198 =/ sr (size r.a) 199 ?: (lth (add sl sr) 2) 200 (rlos a) 201 ?: (gth sr (mul 4 sl)) 202 ?> ?=(^ r.a) 203 ?: (lth (size l.p.r.a) (size r.p.r.a)) 204 (rlsin a) 205 ?- -.r.a 206 %llos (rlsin n.a l.a m.a (lrsin p.r.a)) 207 %rlos (rlsin n.a l.a m.a (rrsin p.r.a)) 208 == 209 ?: (gth sl (mul 4 sr)) 210 ?> ?=(^ l.a) 211 ?: (gth (size l.p.l.a) (size r.p.l.a)) 212 (rrsin a) 213 ?- -.l.a 214 %llos (rrsin n.a (llsin p.l.a) m.a r.a) 215 %rlos (rrsin n.a (rlsin p.l.a) m.a r.a) 216 == 217 (rlos a) 218 :: 219 ++ llsin :: left single-left 220 ~/ %llsin 221 |= a=lnode 222 ^- ltree 223 ?> ?=(^ r.a) 224 =/ b p.r.a 225 ?- -.r.a 226 %llos 227 ?: (lex p.n.a k.n.a p.n.b k.n.b) 228 (llos n.a (rlos n.b l.a m.a l.b) m.b r.b) 229 (llos n.b (llos n.a l.a m.a l.b) m.b r.b) 230 %rlos 231 (rlos n.b (llos n.a l.a m.a l.b) m.b r.b) 232 == 233 :: 234 ++ rlsin :: right single-right 235 ~/ %rlsin 236 |= a=lnode 237 ^- ltree 238 ?> ?=(^ r.a) 239 =/ b p.r.a 240 ?- -.r.a 241 %llos (rlos n.a (rlos n.b l.a m.a l.b) m.b r.b) 242 %rlos (rlos n.b (rlos n.a l.a m.a l.b) m.b r.b) 243 == 244 :: 245 ++ lrsin 246 ~/ %lrsin 247 |= a=lnode 248 ^- ltree 249 ?> ?=(^ l.a) 250 =/ b p.l.a 251 ?- -.l.a 252 %llos (llos n.b l.b m.b (llos n.a r.b m.a r.a)) 253 %rlos (llos n.a l.b m.b (llos n.b r.b m.a r.a)) 254 == 255 :: 256 ++ rrsin 257 ~/ %rrsin 258 |= a=lnode 259 ^- ltree 260 ?> ?=(^ l.a) 261 =/ b p.l.a 262 ?- -.l.a 263 %llos 264 (llos n.b l.b m.b (rlos n.a r.b m.a r.a)) 265 %rlos 266 ?: (lex p.n.a k.n.a p.n.b k.n.b) 267 (rlos n.a l.b m.b (llos n.b r.b m.a r.a)) 268 (rlos n.b l.b m.b (rlos n.a r.b m.a r.a)) 269 == 270 :: 271 ++ toy :: play 272 ~/ %toy 273 |= [a=pro b=pro] 274 ^- pro 275 ?~ a b 276 ?~ b a 277 ?: (lex p.n.a k.n.a p.n.b k.n.b) 278 [n.a (rbal n.b t.a m.a t.b) m.b] 279 [n.b (lbal n.a t.a m.a t.b) m.b] 280 :: 281 ++ sec :: second best 282 ~/ %sec 283 |= [t=ltree m=k] 284 |- ^- pro 285 ?~ t ~ 286 ?- -.t 287 %llos (toy [n.p.t l.p.t m.p.t] $(t r.p.t)) 288 %rlos (toy $(t l.p.t, m m.p.t) [n.p.t r.p.t m]) 289 == 290 :: 291 ++ sink :: make bucket 292 ~/ %sink 293 |= [a=pro =k p=@ =v] 294 ^- (trel _k @ buc) 295 =. a (put a k p v) 296 =/ val (bot a) 297 ?>(?=(^ val) u.val) 298 :: 299 ++ see :: tournament view 300 ~/ %see 301 |= a=pro 302 ^- torn 303 ?~ a ~ 304 ?~ t.a 305 [%sing n.a] 306 ?- -.t.a 307 %llos [%play [n.p.t.a l.p.t.a m.p.t.a] [n.a r.p.t.a m.a]] 308 %rlos [%play [n.a l.p.t.a m.p.t.a] [n.p.t.a r.p.t.a m.a]] 309 == 310 :: 311 ++ tap :: convert to list 312 ~/ %tap 313 |= a=pro 314 =| b=(list elem) 315 |- ^+ b 316 =/ tor (see a) 317 ?~ tor b 318 ?- -.tor 319 %sing [n.tor b] 320 %play (weld $(a l.tor) $(a r.tor)) 321 == 322 :: 323 ++ put :: add [key pri val] 324 ~/ %put 325 |= [a=pro =k p=@ =v] 326 |- ^- pro 327 ?~ a 328 [[k p v] ~ k] 329 ?: ?=(~ t.a) 330 ?: =(k m.a) 331 [[k p v] ~ k] 332 ?: (gor k m.a) 333 (toy [[k p v] ~ k] [n.a ~ k.n.a]) 334 (toy [n.a ~ k.n.a] [[k p v] ~ k]) 335 ?- -.t.a 336 %rlos 337 =/ b=lnode p.t.a 338 ?: |(=(k m.b) (gor k m.b)) 339 (toy $(a [n.a l.b m.b]) [n.b r.b m.a]) 340 (toy [n.a l.b m.b] $(a [n.b r.b m.a])) 341 :: 342 %llos 343 =/ b=lnode p.t.a 344 ?: |(=(k m.b) (gor k m.b)) 345 (toy $(a [n.b l.b m.b]) [n.a r.b m.a]) 346 (toy [n.b l.b m.b] $(a [n.a r.b m.a])) 347 == 348 :: 349 ++ has :: contains 350 ~/ %has 351 |= [a=pro =k] 352 !=(~ (get a k)) 353 :: 354 ++ get :: lookup 355 ~/ %get 356 |= [a=pro =k] 357 |- ^- (unit (pair @ v)) 358 ?~ a ~ 359 =/ tor=torn (see a) 360 ?~ tor ~ 361 ?- -.tor 362 %sing 363 ?. =(k k.n.tor) ~ 364 `[p.n.tor v.n.tor] 365 :: 366 %play 367 ?> ?=(^ l.tor) 368 ?: |(=(k m.l.tor) (gor k m.l.tor)) 369 $(a l.tor) 370 $(a r.tor) 371 == 372 :: 373 ++ del :: delete at key k 374 ~/ %del 375 |= [a=pro =k] 376 |- ^- pro 377 ?~ a ~ 378 ?: ?=(~ t.a) 379 ?: =(k k.n.a) ~ 380 [n.a ~ k.n.a] 381 ?- -.t.a 382 %rlos 383 =/ b=lnode p.t.a 384 ?: |(=(k m.b) (gor k m.b)) 385 (toy $(a [n.a l.b m.b]) [n.b r.b m.a]) 386 (toy [n.a l.b m.b] $(a [n.b r.b m.a])) 387 :: 388 %llos 389 =/ b=lnode p.t.a 390 ?: |(=(k m.b) (gor k m.b)) 391 (toy $(a [n.b l.b m.b]) [n.a r.b m.a]) 392 (toy [n.b l.b m.b] $(a [n.a r.b m.a])) 393 == 394 :: 395 ++ dew :: delete view 396 ~/ %dew 397 |= [a=pro =k] 398 |- ^- (unit (trel @ v pro)) 399 ?~ a ~ 400 ?~ t.a 401 ?. =(k k.n.a) ~ 402 `[p.n.a v.n.a ~] 403 ?- -.t.a 404 %llos 405 =/ b=lnode p.t.a 406 ?: |(=(k m.b) (gor k m.b)) 407 =/ pat $(a [n.b l.b m.b]) 408 ?~ pat ~ 409 %- some 410 :+ p.u.pat q.u.pat 411 (toy r.u.pat [n.a r.b m.a]) 412 =/ pat $(a [n.a r.b m.a]) 413 ?~ pat ~ 414 %- some 415 :+ p.u.pat q.u.pat 416 (toy [n.b l.b m.b] r.u.pat) 417 :: 418 %rlos 419 =/ b=lnode p.t.a 420 ?: |(=(k m.b) (gor k m.b)) 421 =/ pat $(a [n.a l.b m.b]) 422 ?~ pat ~ 423 %- some 424 :+ p.u.pat q.u.pat 425 (toy r.u.pat [n.b r.b m.a]) 426 =/ pat $(a [n.b r.b m.a]) 427 ?~ pat ~ 428 %- some 429 :+ p.u.pat q.u.pat 430 (toy [n.a l.b m.b] r.u.pat) 431 == 432 :: 433 ++ bot :: lowest-pro view 434 ~/ %bot 435 |= a=pro 436 ^- (unit (trel k @ buc)) 437 ?~ a ~ 438 `[k.n.a p.n.a v.n.a (sec t.a m.a)] 439 -- 440 :: radix tree logic 441 :: 442 ++ qat 443 ~% %qat ..qat ~ 444 |% 445 :: 446 ++ del :: delete at key k 447 ~/ %del 448 |= [a=pri k=k] 449 |- ^- pri 450 ?~ a ~ 451 ?- -.a 452 %tip 453 ?: =(k k.a) ~ 454 a 455 :: 456 %bin 457 ?: (feud m.a k k.a) 458 a 459 ?: =((mug k) (mug k.a)) 460 (fuse m.a l.a r.a) 461 ?: (zero m.a k) 462 (funk k.a p.a v.a m.a $(a l.a) r.a) 463 (wane k.a p.a v.a m.a l.a $(a r.a)) 464 == 465 :: 466 ++ dew :: delete view 467 ~/ %dew 468 |= [a=pri =k] 469 ^- (unit (qual _k @ buc pri)) 470 =- ?~ p.- ~ 471 `[p.u.p.- q.u.p.- r.u.p.- q.-] 472 |- ^- (pair (unit (trel _k @ buc)) pri) 473 ?~ a [~ ~] 474 ?- -.a 475 %tip 476 ?. =((mug k) (mug k.a)) 477 [~ a] 478 [`[k.a p.a v.a] ~] 479 :: 480 %bin 481 ?: (feud m.a k k.a) 482 [~ a] 483 ?: =((mug k) (mug k.a)) 484 :- `[k.a p.a v.a] 485 (fuse m.a l.a r.a) 486 ?: (zero m.a k) 487 =/ mud $(a l.a) 488 :- p.mud 489 (funk k.a p.a v.a m.a q.mud r.a) 490 =/ mud $(a r.a) 491 :- p.mud 492 (wane k.a p.a v.a m.a l.a q.mud) 493 == 494 :: 495 ++ raw :: raw insert 496 ~/ %raw :: 497 |= [a=pri k=k p=@ v=buc] :: k must not exist in 498 ^- pri :: queue 499 ?~ a [%tip k p v] 500 ?- -.a 501 %tip 502 ?: (lex p k p.a k.a) 503 (rule k p v a ~) 504 (rule k.a p.a v.a [%tip k p v] ~) 505 :: 506 %bin 507 ?: (feud m.a k k.a) 508 ?: (lex p k p.a k.a) 509 (rule k p v a ~) 510 (rule k.a p.a v.a [%tip k p v] (fuse m.a l.a r.a)) 511 :- %bin 512 ?: (lex p k p.a k.a) 513 ?: (zero m.a k.a) 514 [k p v m.a $(a l.a, k k.a, p p.a, v v.a) r.a] 515 [k p v m.a l.a $(a r.a, k k.a, p p.a, v v.a)] 516 ?: (zero m.a k) 517 [k.a p.a v.a m.a $(a l.a) r.a] 518 [k.a p.a v.a m.a l.a $(a r.a)] 519 == 520 :: 521 ++ put :: insert 522 ~/ %put 523 |= [a=pri k=k p=@ v=buc] 524 ^- pri 525 (raw (del a k) k p v) 526 :: 527 ++ gas :: concatenate 528 ~/ %gas 529 |= [a=pri b=(list (trel k @ buc))] 530 |- ^- pri 531 ?~ b a 532 $(b t.b, a (put a p.i.b q.i.b r.i.b)) 533 -- 534 :: pri logic 535 :: 536 ++ wyt :: queue size 537 |= a=pri 538 ^- @ 539 %+ rep a 540 |=([[k @ buc] @] +((add +<+ (wyt:qor t.+<->+)))) 541 :: 542 ++ get :: lookup 543 ~/ %get 544 |= [a=pri =k] 545 |- ^- (unit (pair @ v)) 546 ?~ a ~ 547 ?- -.a 548 %tip 549 ?. =((mug k) (mug k.a)) ~ 550 ?: =(k k.a) 551 `[p.a v.v.a] 552 (get:qor t.v.a k) 553 :: 554 %bin 555 ?: (feud m.a k k.a) ~ 556 ?: =((mug k) (mug k.a)) 557 ?: =(k k.a) 558 `[p.a v.v.a] 559 (get:qor t.v.a k) 560 ?: (zero m.a k) 561 $(a l.a) 562 $(a r.a) 563 == 564 :: 565 ++ has :: contains 566 |= [a=pri =k] 567 ^- ? 568 !=(~ (get a k)) 569 :: 570 ++ put :: insert 571 ~/ %put 572 |= [a=pri =k p=@ =v] 573 ^- pri 574 ?~ ded=(dew:qat a k) 575 (raw:qat a k p v ~) 576 =/ val u.ded 577 =. a s.val 578 %+ raw:qat a 579 ?: =(k p.val) 580 (sink:qor t.r.val k p v) 581 ?: |((lth q.val p) &(=(p q.val) (gor p.val k))) 582 [p.val q.val v.r.val (put:qor t.r.val k p v)] 583 :^ k p v 584 ?: (has:qor t.r.val k) 585 (put:qor (del:qor t.r.val k) p.val q.val v.r.val) 586 (put:qor t.r.val p.val q.val v.r.val) 587 :: 588 ++ del :: remove 589 ~/ %del 590 |= [a=pri =k] 591 ^- pri 592 ?~ ded=(dew:qat a k) a 593 =/ val u.ded 594 =. a s.val 595 ?: =(k p.val) 596 ?~ low=(bot:qor t.r.val) a 597 (raw:qat a u.low) 598 (raw:qat a p.val q.val v.r.val (del:qor t.r.val k)) 599 :: 600 ++ dew :: delete view 601 ~/ %dew 602 |= [a=pri =k] 603 ^- (unit (trel @ v pri)) 604 ?~ ded=(dew:qat a k) ~ 605 =/ val u.ded 606 =. a s.val 607 ?: =(k p.val) 608 %- some 609 :+ q.val v.r.val 610 ?~ low=(bot:qor t.r.val) a 611 (raw:qat a u.low) 612 ?~ low=(dew:qor t.r.val k) ~ 613 %- some 614 :+ p.u.low q.u.low 615 (raw:qat a p.val q.val v.r.val r.u.low) 616 :: 617 ++ gas :: concatenate 618 |= [a=pri b=(list (trel k @ v))] 619 |- ^- pri 620 ?~ b a 621 $(b t.b, a (put a p.i.b q.i.b r.i.b)) 622 :: 623 ++ bot :: min-priority view 624 ~/ %bot 625 |= a=pri 626 ^- (unit (qual k @ v pri)) 627 ?~ a ~ 628 %- some 629 ?- -.a 630 %tip [k.a p.a v.v.a (cut a)] 631 %bin [k.a p.a v.v.a (cut a)] 632 == 633 :: 634 ++ sam :: equality 635 |= [a=pri b=pri] 636 ^- ? 637 =/ loa (bot a) 638 =/ lob (bot b) 639 ?| &(=(~ loa) =(~ lob)) 640 !&(=(~ loa) !=(~ lob)) 641 !&(!=(~ loa) =(~ lob)) 642 ?> &(?=(^ loa) ?=(^ lob)) 643 ?& =(p.u.loa p.u.lob) 644 =(q.u.loa q.u.lob) 645 =(r.u.loa r.u.lob) 646 $(a s.u.loa, b s.u.lob) 647 == 648 == 649 :: 650 ++ key :: list of keys 651 |= a=pri 652 ^- (list k) 653 %+ turn `(list (trel k @ v))`(tap a) 654 |=([k @ v] +<-) 655 :: 656 ++ tap :: convert to list 657 |= a=pri 658 =| acc=(list (trel k @ buc)) 659 =/ lis 660 |- ^+ acc 661 ?~ a acc 662 ?- -.a 663 %tip [[k.a p.a v.a] acc] 664 %bin [[k.a p.a v.a] $(acc $(a r.a), a l.a)] 665 == 666 =| acc=(list (trel k @ v)) 667 |- ^+ acc 668 ?~ lis acc 669 =/ hed i.lis 670 =/ res (tap:qor t.r.hed) 671 =. acc (weld res acc) 672 $(lis t.lis, acc [[p.hed q.hed v.r.hed] acc]) 673 :: 674 ++ rep :: fold 675 |* [a=pri f=_=>(buc |=([[* @ buc] *] +<+))] 676 |- 677 ?~ a +<+.f 678 ?- -.a 679 %tip (f [k.a p.a v.a] +<+.f) 680 %bin $(a r.a, +<+.f $(a l.a, +<+.f (f [k.a p.a v.a] +<+.f))) 681 == 682 :: 683 ++ cut :: delete min-pri 684 ~/ %cut 685 |= a=pri 686 ^- pri 687 ?~ a ~ 688 ?- -.a 689 %tip 690 ?~ hol=(bot:qor t.v.a) ~ 691 [%tip u.hol] 692 :: 693 %bin 694 ?~ hol=(bot:qor t.v.a) (fuse m.a l.a r.a) 695 (raw:qat (fuse m.a l.a r.a) u.hol) 696 == 697 :: 698 ++ vip :: very important put 699 ~/ %vip :: 700 |= [a=pri k=k p=@ =v] :: p must be higher 701 ^- (pair (unit (pair @ _v)) pri) :: than resident max 702 ?~ a 703 [~ [%tip k p v ~]] 704 ?- -.a 705 %tip 706 ?: =((mug k) (mug k.a)) 707 ?: =(k k.a) 708 :- `[p.a v.v.a] 709 [%tip (sink:qor t.v.a k p v)] 710 :- (get:qor t.v.a k) 711 [%tip k.a p.a v.v.a (put:qor t.v.a k p v)] 712 [~ (rule k.a p.a v.a [%tip k p v ~] ~)] 713 :: 714 %bin 715 ?: (feud m.a k k.a) 716 [~ (rule k.a p.a v.a [%tip k p v ~] (fuse m.a l.a r.a))] 717 ?: =((mug k) (mug k.a)) 718 ?: =(k k.a) 719 :- `[p.a v.v.a] 720 =/ val (sink:qor t.v.a k p v) 721 ?: (zero m.a p.val) 722 (fuse m.a (raw:qat l.a val) r.a) 723 (fuse m.a l.a (raw:qat r.a val)) 724 :- (get:qor t.v.a k) 725 [%bin k.a p.a [v.v.a (put:qor t.v.a k p v)] m.a l.a r.a] 726 ?: (zero m.a k) 727 =/ val $(a l.a) 728 :- p.val 729 [%bin k.a p.a v.a m.a q.val r.a] 730 =/ val $(a r.a) 731 :- p.val 732 [%bin k.a p.a v.a m.a l.a q.val] 733 == 734 :: 735 ++ see :: get with pri bump 736 ~/ %see :: 737 |= [a=pri =k p=@] :: p must be higher 738 |^ ^- (pair (unit (pair @ v)) pri) :: than resident max 739 ?~ a [~ ~] 740 ?- -.a 741 %tip 742 ?. =((mug k) (mug k.a)) 743 [~ a] 744 =/ mud (stir k.a p.a v.a) 745 :- p.mud 746 [%tip q.mud r.mud s.mud] 747 :: 748 %bin 749 ?: (feud m.a k k.a) 750 [~ a] 751 ?: =((mug k) (mug k.a)) 752 =/ mud (stir k.a p.a v.a) 753 :- p.mud 754 ?: (zero m.a k) 755 (fuse m.a (raw:qat l.a q.mud r.mud s.mud) r.a) 756 (fuse m.a l.a (raw:qat r.a q.mud r.mud s.mud)) 757 ?: (zero m.a k) 758 =/ val $(a l.a) 759 :- p.val 760 [%bin k.a p.a v.a m.a q.val r.a] 761 =/ val $(a r.a) 762 :- p.val 763 [%bin k.a p.a v.a m.a l.a q.val] 764 == 765 :: 766 ++ stir 767 |= [l=_k q=@ =buc] 768 ^- (qual (unit (pair @ v)) _k @ _buc) 769 ?: =(k l) 770 :- `[q v.buc] 771 (sink:qor t.buc l p v.buc) 772 ?~ val=(get:qor t.buc k) [~ l q buc] 773 :^ val l q 774 [v.buc (put:qor t.buc k p q.u.val)] 775 -- 776 -- 777 :: 778 ++ lu :: lru cache engine 779 ~/ %lu 780 |* [k=mold v=mold] 781 :: 782 ~% %core + ~ 783 |% 784 :: 785 +$ pes [cap=_`@`10.000 siz=@ tic=@ pri=pri:psq] :: lru cache 786 :: 787 ++ psq (up k v) 788 :: 789 ++ new :: new cache 790 ~/ %new 791 |= cap=@ 792 ^- pes 793 [cap 0 0 ~] 794 :: 795 ++ ebb :: trim cache 796 ~/ %ebb 797 |= a=pes 798 ?: (gte tic.a 0x7fff.ffff) 799 (new cap.a) 800 ?: (gth siz.a cap.a) 801 a(siz (dec siz.a), pri (cut:psq pri.a)) 802 a 803 :: 804 ++ put :: insert 805 ~/ %put 806 |= [a=pes =k =v] 807 ^- pes 808 =/ vue (vip:psq pri.a k tic.a v) 809 %- ebb 810 %_ a 811 siz ?~(p.vue +(siz.a) siz.a) 812 tic +(tic.a) 813 pri q.vue 814 == 815 :: 816 ++ get :: lookup w/pri bump 817 ~/ %get 818 |= [a=pes =k] 819 ^- (unit (pair v pes)) 820 =/ val (see:psq pri.a k tic.a) 821 ?~ p.val ~ 822 %- some 823 :- q.u.p.val 824 %- ebb 825 %_ a 826 tic +(tic.a) 827 pri q.val 828 == 829 :: 830 ++ del :: remove 831 ~/ %del 832 |= [a=pes =k] 833 ^- pes 834 ?~ ded=(dew:psq pri.a k) a 835 %_ a 836 siz (dec siz.a) 837 pri r.u.ded 838 == 839 :: 840 ++ gas :: concatenate 841 |= [a=pes b=(list (pair k v))] 842 ^- pes 843 ?~ b a 844 $(b t.b, a (put a p.i.b q.i.b)) 845 :: 846 ++ tap :: to list 847 |= a=pes 848 ^- (list (trel k @ v)) 849 (tap:psq pri.a) 850 :: 851 ++ key :: list of keys 852 |= a=pes 853 ^- (list k) 854 (key:psq pri.a) 855 -- 856 --