1 /** Tries and Prefix Trees. 2 3 Implementation is layered: 4 $(UL 5 $(LI `RawRadixTree` stores its untyped keys as variable length ubyte-strings (`UKey`)) 6 $(LI On top of that `RadixTree` implements typed-key access via its template parameter `Key`.) 7 ) 8 Both layers currently support 9 $(UL 10 $(LI template parameterization on the `Value`-type in the map case (when `Value` is non-`void`)) 11 $(LI `@nogc` and, when possible, `@safe pure nothrow`) 12 $(LI insertion with returned modifications status: `auto newKeyWasInserted = set.insert(Key key)`) 13 $(LI AA-style `in`-operator) 14 $(UL 15 $(LI `key in set` is `bool` for set-case) 16 $(LI `key in map` returns non-`null` `value` pointer when `key` is stored in `map`) 17 ) 18 $(LI AA-style iteration of map keys: `map.byKey()`) 19 $(LI AA-style iteration of map values: `map.byValue()`) 20 $(LI `SortedRange`-style iteration over elements sorted by key: `assert(set[].isSorted)`) 21 $(LI containment checking: `bool contains(in Key key)`) 22 $(LI element indexing and element index assignment for map case via `opIndex` and `opIndexAssign`) 23 $(LI key-prefix Completion (returning a `Range` over all set/map-elements that match a key prefix): `prefix(Key keyPrefix)`) 24 ) 25 Typed layer supports 26 $(UL 27 $(LI ordered access of aggregate types) 28 ) 29 30 See_Also: $(HTTP en.wikipedia.org/wiki/Trie) 31 See_Also: $(HTTP en.wikipedia.org/wiki/Radix_tree) 32 See_Also: $(HTTP github.com/nordlow/phobos-next/blob/master/src/test_trie_prefix.d) for a descriptive usage of prefixed access. 33 34 TODO: split up file into raw_trie.d, trie.d 35 36 TODO: use fast bit-scanning functions in core.bitop for DenseBranch and 37 DenseLeaf iterators 38 39 TODO: shift addresses of class and pointers by its alignment before adding 40 them to make top-branch as dense possible 41 42 TODO: Allow slicing from non-mutable tries and add test-case at line 5300 43 44 TODO: 2. Make as many members as possible free functionss free-functions to 45 reduce compilation times. Alternative make them templates (`template-lazy` ) 46 47 TODO: Use scope on `Range`, `RawRange` and members that return key and value 48 reference when DIP-1000 has been implemented 49 50 TODO: Encode `string` with zero-terminating 0 byte when it's not the last 51 member in a key aggregate 52 53 TODO 54 55 Replace 56 case undefined: return typeof(return).init; // terminate recursion 57 with 58 case undefined: return curr; 59 60 TODO: 61 TODO: Make `Key` and Ix[]-array of `immutable Ix` like `string` 62 63 TODO: Allow `Node`-constructors to take const and immutable prefixes and then 64 make `toRawKey` and `toTypedKey` accept return const-slices 65 66 TODO: Remove @trusted from VLA (variable length array)-members of SparseBranch/SparseLeaf and make their callers @trusted instead. 67 68 TODO: Assure that ~this() is run for argument `nt` in `freeNode`. Can we use `postblit()` for this? 69 70 TODO: Search for "functionize this loop or reuse memmove" and use move() 71 72 TODO: Add Branch-hint allocation flag and re-benchmark construction of `radixTreeSet` with 10000000 uints 73 74 TODO: Add sortedness to `IxsN` and make `IxsN.contains()` use `binarySearch()`. Make use of `sortn`. 75 76 TODO: Check for case when expanding to bit-branch instead of `SparseBranch` in all `expand()` overloads 77 78 TODO: Make array indexing/slicing as @trusted and use .ptr[] instead of [] when things are stable. 79 80 TODO: Add various extra packings in MixLeaf1to4: number of 81 - Ix (0,1,2,3,4,5,6): 3-bits 82 - Ix2 (0,1,2,3): 2-bits 83 - Ix3 (0,1,2): 2-bits 84 - Ix4 (0,1): 1-bit 85 Total bits 8-bits 86 Possible packings with 6 bytes 87 - 4_ 88 - 4_2 89 - 4_2 90 - 4_2_1 91 - 4_1 92 - 4_1_1 93 - 3_2 94 - 3_2_1 95 - 3_1 96 - 3_1_1 97 - 3_1_1_1 98 - 2_2_2 99 - 2_2 100 - 2_2_1 101 - 2_2_1_1 102 - 2 103 - 2_1 104 - 2_1_1 105 - 2_1_1_1 106 - 2_1_1_1_1 107 - 1 108 - 1_1 109 - 1_1_1 110 - 1_1_1_1 111 - 1_1_1_1_1 112 - 1_1_1_1_1_1 113 114 TODO: Sorted Range Primitives over Keys 115 116 - Returns a range of elements which are equivalent (though not necessarily equal) to value. 117 auto equalRange(this This)(inout T value) 118 119 - Returns a range of elements which are greater than low and smaller than highValue. 120 auto bound(this This)(inout T lowValue, inout T highValue) 121 122 - Returns a range of elements which are less than value. 123 auto lowerBound(this This)(inout T value) 124 125 - Returns a range of elements which are greater than value. 126 auto upperBound(this This)(inout T value) 127 128 TODO: opBinaryRight shall return `_rawTree.ElementRef` instead of `bool` 129 130 TODO: Fix vla-allocations in constructVariableSizeNode according 131 C11-recommendations. For reference set commit 132 d2f1971dd570439da4198fa76603b53b072060f8 at 133 https://github.com/emacs-mirror/emacs.git 134 */ 135 module nxt.trie; 136 137 import std.algorithm.mutation : move; 138 import std.algorithm.comparison : min, max; 139 import std.traits : isSomeString, isArray, isPointer, Unqual; 140 import std.range.primitives : isInputRange, ElementType, hasLength; 141 142 import nxt.bijections : isIntegralBijectableType, bijectToUnsigned, bijectFromUnsigned; 143 import nxt.variant_ex : WordVariant; 144 import nxt.typecons_ex : IndexedBy; 145 import nxt.container_traits : mustAddGCRange; 146 import nxt.dynamic_array : Array = DynamicArray; 147 148 // version = enterSingleInfiniteMemoryLeakTest; 149 // version = benchmark; 150 // version = show; 151 // version = useMemoryErrorHandler; 152 // version = showBranchSizes; 153 // version = showAssertTags; 154 155 alias isFixedTrieableKeyType = isIntegralBijectableType; 156 157 /** Returns: `true` if `T` is a scalar trie key-type, `false` otherwise. */ 158 enum isScalarTrieableKeyType(T) = (isFixedTrieableKeyType!T || 159 (isInputRange!T && 160 isFixedTrieableKeyType!(ElementType!T))); 161 162 /** Returns: `true` if `T` is a type that can be stored as a key in a trie, ` false` otherwise. */ 163 template isTrieableKeyType(T) 164 { 165 static if (is(T == struct)) 166 { 167 import std.meta : allSatisfy; 168 enum isTrieableKeyType = allSatisfy!(isScalarTrieableKeyType, // recurse 169 typeof(T.tupleof)); 170 } 171 else static if (is(T == class)) 172 static assert("Class types cannot be stored in a radix tree because classes in D has reference semantics"); 173 else 174 enum isTrieableKeyType = isScalarTrieableKeyType!T; 175 } 176 177 version(useMemoryErrorHandler) unittest 178 { 179 import etc.linux.memoryerror : registerMemoryErrorHandler; 180 registerMemoryErrorHandler(); 181 dbg("registerMemoryErrorHandler done"); 182 } 183 184 @safe pure nothrow @nogc unittest 185 { version(showAssertTags) dbg(); 186 static assert(isTrieableKeyType!(const(char)[])); 187 188 struct S { int x, y, z; double w; bool b; } 189 static assert(isTrieableKeyType!(S)); 190 } 191 192 /** Binary power of radix, typically either 1, 2, 4 or 8. */ 193 private enum span = 8; 194 /** Branch-multiplicity. Also called order. */ 195 private enum radix = 2^^span; 196 197 static assert(span == 8, "Radix is currently limited to 8"); 198 static assert(size_t.sizeof == 8, "Currently requires a 64-bit CPU (size_t.sizeof == 8)"); 199 200 version(unittest) 201 { 202 version = useModulo; 203 } 204 version = useModulo; // TODO: remove and activate only in version(unittest) 205 206 /** Radix Modulo Index 207 Restricted index type avoids range checking in array indexing below. 208 */ 209 version(useModulo) 210 { 211 import nxt.modulo : Mod, mod; // TODO: remove these if radix is `256` 212 alias Ix = Mod!(radix, ubyte); 213 alias UIx = Mod!(radix, size_t); // `size_t` is faster than `uint` on Intel Haswell 214 215 /** Mutable RawTree Key. */ 216 alias Key(size_t span) = Mod!(2^^span)[]; // TODO: use static_bitarray to more naturally support span != 8. 217 /** Immutable RawTree Key. */ 218 alias IKey(size_t span) = immutable(Mod!(2^^span))[]; // TODO: use static_bitarray to more naturally support span != 8. 219 /** Fixed-Length RawTree Key. */ 220 alias KeyN(size_t span, size_t N) = Mod!(2^^span)[N]; 221 222 enum useModuloFlag = true; 223 } 224 else 225 { 226 alias Ix = ubyte; 227 alias UIx = size_t; 228 229 /** Mutable RawTree Key. */ 230 alias Key(size_t span) = ubyte[]; // TODO: use static_bitarray to more naturally support span != 8. 231 /** Immutable RawTree Key. */ 232 alias IKey(size_t span) = immutable(ubyte)[]; // TODO: use static_bitarray to more naturally support span != 8. 233 /** Fixed-Length RawTree Key. */ 234 alias KeyN(size_t span, size_t N) = ubyte[N]; 235 236 enum useModuloFlag = false; 237 } 238 239 import nxt.static_modarray : StaticModArray; 240 alias IxsN(uint capacity, 241 uint elementLength) = StaticModArray!(capacity, 242 elementLength, 243 8, 244 useModuloFlag); 245 246 alias UKey = Key!span; 247 bool empty(UKey ukey) @safe pure nothrow @nogc 248 { 249 return ukey.length == 0; 250 } 251 252 private template IxElt(Value) 253 { 254 static if (is(Value == void)) // set case 255 alias IxElt = UIx; 256 else // map case 257 struct IxElt { UIx ix; Value value; } 258 } 259 260 private static auto eltIx(Value)(inout IxElt!Value elt) 261 { 262 static if (is(Value == void)) // set case 263 return elt; 264 else // map case 265 return elt.ix; 266 } 267 268 private template Elt(Value) 269 { 270 static if (is(Value == void)) // set case 271 alias Elt = UKey; 272 else // map case 273 struct Elt { UKey key; Value value; } 274 } 275 276 private auto eltKey(Value)(inout Elt!Value elt) 277 { 278 static if (is(Value == void)) // set case 279 return elt; 280 else // map case 281 return elt.key; 282 } 283 284 private auto eltKeyDropExactly(Value)(Elt!Value elt, size_t n) 285 { 286 static if (is(Value == void)) // set case 287 return elt[n .. $]; 288 else // map case 289 return Elt!Value(elt.key[n .. $], elt.value); 290 } 291 292 /** Results of attempt at modification sub. */ 293 enum ModStatus:ubyte 294 { 295 maxCapacityReached, // no operation, max capacity reached 296 unchanged, // no operation, element already stored 297 added, inserted = added, // new element was added (inserted) 298 updated, modified = updated, // existing element was update/modified 299 } 300 301 /** Size of a CPU cache line in bytes. 302 * 303 * Container layouts should be adapted to make use of at least this many bytes 304 * in its nodes. 305 */ 306 private enum cacheLineSize = 64; 307 308 shared static this() 309 { 310 import core.cpuid : dataCaches; 311 assert(cacheLineSize == dataCaches()[0].lineSize, "Cache line is not 64 bytes"); 312 } 313 314 enum keySeparator = ','; 315 316 /** Single/1-Key Leaf with maximum key-length 7. */ 317 struct OneLeafMax7 318 { 319 @safe pure: 320 enum capacity = 7; 321 322 this(Ix[] key) nothrow @nogc 323 { 324 pragma(inline, true); 325 assert(key.length != 0); 326 this.key = key; 327 } 328 329 bool contains(UKey key) const nothrow @nogc 330 { 331 pragma(inline, true); 332 return this.key == key; 333 } 334 335 @property string toString() const 336 { 337 import std..string : format; 338 string s; 339 foreach (immutable i, immutable ix; key) 340 { 341 immutable first = i == 0; // first iteration 342 if (!first) { s ~= '_'; } 343 s ~= format("%.2X", ix); // in hexadecimal 344 } 345 return s; 346 } 347 348 IxsN!(capacity, 1) key; 349 } 350 351 /** Binary/2-Key Leaf with key-length 3. */ 352 struct TwoLeaf3 353 { 354 enum keyLength = 3; // fixed length key 355 enum capacity = 2; // maximum number of keys stored 356 357 @safe pure nothrow @nogc: 358 359 this(Keys...)(Keys keys) 360 if (Keys.length != 0 && 361 Keys.length <= capacity) 362 { 363 pragma(inline, true); 364 this.keys = keys; 365 } 366 367 inout(Ix)[] prefix() inout 368 { 369 // version(LDC) pragma(inline, true); 370 assert(!keys.empty); 371 final switch (keys.length) 372 { 373 case 1: 374 return keys.at!0[]; 375 case 2: 376 import std.algorithm.searching : commonPrefix; 377 return commonPrefix(keys.at!0[], keys.at!1[]); 378 } 379 } 380 381 bool contains(UKey key) const 382 { 383 version(LDC) pragma(inline, true); 384 assert(!keys.empty); 385 final switch (keys.length) 386 { 387 case 1: return keys[0] == key; 388 case 2: return keys[0] == key || keys[1] == key; 389 } 390 // return keys.contains(key); 391 } 392 393 IxsN!(capacity, keyLength) keys; // should never be empty 394 } 395 396 /** Ternary/3-Key Leaf with key-length 2. */ 397 struct TriLeaf2 398 { 399 enum keyLength = 2; // fixed length key 400 enum capacity = 3; // maximum number of keys stored 401 402 @safe pure nothrow @nogc: 403 404 this(Keys...)(Keys keys) 405 if (Keys.length != 0 && 406 Keys.length <= capacity) 407 { 408 pragma(inline, true); 409 this.keys = keys; 410 } 411 412 inout(Ix)[] prefix() inout 413 { 414 // version(LDC) pragma(inline, true); 415 assert(!keys.empty); 416 import std.algorithm.searching : commonPrefix; 417 final switch (keys.length) 418 { 419 case 1: 420 return keys.at!0[]; 421 case 2: 422 return commonPrefix(keys.at!0[], keys.at!1[]); 423 case 3: 424 return commonPrefix(keys.at!0[], 425 commonPrefix(keys.at!1[], 426 keys.at!2[])); // TODO: make and reuse variadic commonPrefix 427 } 428 } 429 430 bool contains(UKey key) const 431 { 432 version(LDC) pragma(inline, true); 433 assert(!keys.empty); 434 final switch (keys.length) 435 { 436 case 1: return keys[0] == key; 437 case 2: return keys[0] == key || keys[1] == key; 438 case 3: return keys[0] == key || keys[1] == key || keys[2] == key; 439 } 440 // return keys.contains(key); 441 } 442 443 IxsN!(capacity, keyLength) keys; // should never be empty 444 } 445 446 /** Hepa/7-Key Leaf with key-length 1. */ 447 struct HeptLeaf1 448 { 449 enum keyLength = 1; 450 enum capacity = 7; // maximum number of elements 451 452 @safe pure nothrow @nogc: 453 454 this(Keys...)(Keys keys) 455 if (Keys.length != 0 && 456 Keys.length <= capacity) 457 { 458 pragma(inline, true); 459 // static foreach (const ix, const key; keys) 460 // { 461 // this.keys[ix] = cast(Ix)key; 462 // } 463 this.keys = keys; 464 } 465 466 bool contains(UIx key) const 467 { 468 pragma(inline, true); 469 assert(!keys.empty); 470 // NOTE this is not noticably faster 471 // final switch (keys.length) 472 // { 473 // case 1: return keys[0] == key; 474 // case 2: return keys[0] == key || keys[1] == key; 475 // case 3: return keys[0] == key || keys[1] == key || keys[2] == key; 476 // case 4: return keys[0] == key || keys[1] == key || keys[2] == key || keys[3] == key; 477 // case 5: return keys[0] == key || keys[1] == key || keys[2] == key || keys[3] == key || keys[4] == key; 478 // case 6: return keys[0] == key || keys[1] == key || keys[2] == key || keys[3] == key || keys[4] == key || keys[5] == key; 479 // case 7: return keys[0] == key || keys[1] == key || keys[2] == key || keys[3] == key || keys[4] == key || keys[5] == key || keys[6] == key; 480 // } 481 return keys.contains(key); 482 } 483 bool contains(UKey key) const 484 { 485 pragma(inline, true); 486 return (key.length == 1 && 487 keys.contains(UIx(key[0]))); 488 } 489 490 IxsN!(capacity, 1) keys; // should never be empty 491 } 492 493 /** Check if type `NodeType` is a variable-length aggregate (`struct`) type. */ 494 private template hasVariableSize(NodeType) 495 { 496 import std.traits: hasMember; 497 enum hasVariableSize = hasMember!(NodeType, "allocationSizeOfCapacity"); 498 } 499 500 /** Allocate (if pointer) and Construct a `Node`-type of value type `NodeType` 501 * using constructor arguments `args` of `Args`. 502 */ 503 auto constructFixedSizeNode(NodeType, Args...)(Args args) @trusted pure nothrow @nogc 504 if (!hasVariableSize!NodeType) 505 { 506 static if (isPointer!NodeType) 507 { 508 // debug ++_heapAllocBalance; 509 import core.lifetime : emplace; 510 return emplace(cast(NodeType)malloc((*NodeType.init).sizeof), args); 511 // TODO: ensure alignment of node at least that of NodeType.alignof 512 } 513 else 514 return NodeType(args); 515 } 516 517 /** Allocate (via malloc) and emplace an instance of a variable-length aggregate (`struct`) type `NodeType`. 518 * 519 * Construction is done using `malloc` plus `emplace`. 520 */ 521 private NodeType* constructVariableSizeNode(NodeType, Args...)(size_t requiredCapacity, Args args) @trusted 522 if (is(NodeType == struct) && 523 hasVariableSize!NodeType) 524 { 525 import std.math : nextPow2; 526 import std.algorithm.comparison : clamp; 527 const paddedRequestedCapacity = (requiredCapacity == 1 ? 528 1 : 529 (nextPow2(requiredCapacity - 1).clamp(NodeType.minCapacity, 530 NodeType.maxCapacity))); 531 532 // import nxt.dbgio; 533 // dbg(NodeType.stringof, " paddedRequestedCapacity:", paddedRequestedCapacity, " requiredCapacity:", requiredCapacity); 534 535 // assert(paddedRequestedCapacity >= requiredCapacity); // TODO: this fails for dmd but not for ldc 536 537 import nxt.qcmeman : malloc; 538 import core.lifetime : emplace; 539 return emplace(cast(typeof(return))malloc(NodeType.allocationSizeOfCapacity(paddedRequestedCapacity)), 540 paddedRequestedCapacity, args); 541 } 542 543 void freeNode(NodeType)(NodeType nt) @trusted pure nothrow @nogc 544 { 545 static if (isPointer!NodeType) 546 { 547 free(cast(void*)nt); // TODO: Allocator.free 548 // debug --_heapAllocBalance; 549 } 550 } 551 552 /** Sparsely coded leaves with values of type `Value`. */ 553 static private struct SparseLeaf1(Value) 554 { 555 import nxt.searching_ex : containsStoreIndex; 556 import std.range : assumeSorted; 557 import std.algorithm.sorting : isSorted; 558 559 enum hasValue = !is(Value == void); 560 561 enum minCapacity = 0; // preferred minimum number of preallocated values 562 563 // preferred maximum number of preallocated values, if larger use a DenseLeaf1 instead 564 static if (hasValue) 565 enum maxCapacity = 128; 566 else 567 enum maxCapacity = 48; 568 569 version(useModulo) 570 alias Capacity = Mod!(maxCapacity + 1); 571 else 572 alias Capacity = ubyte; 573 574 alias Length = Capacity; 575 576 pure nothrow @nogc: 577 578 this(size_t capacity) 579 { 580 _capacity = cast(Capacity)capacity; 581 _length = 0; 582 } 583 584 /** Returns a an allocated duplicate of this. 585 * 586 * Shallowly duplicates the values in the map case. 587 */ 588 typeof(this)* dup() 589 { 590 static if (hasValue) 591 return constructVariableSizeNode!(typeof(this))(this._capacity, ixs, values); 592 else 593 return constructVariableSizeNode!(typeof(this))(this._capacity, ixs); 594 } 595 596 static if (hasValue) 597 { 598 static if (mustAddGCRange!Value) 599 import core.memory : GC; 600 601 /** Construct with capacity `capacity`. */ 602 this(size_t capacity, Ix[] ixs, Value[] values) 603 in 604 { 605 assert(ixs.length == values.length); 606 assert(capacity >= ixs.length); 607 assert(values.length <= maxCapacity); 608 assert(ixs.isSorted); 609 } 610 do 611 { 612 _capacity = capacity; 613 _length = ixs.length; 614 foreach (immutable i, immutable ix; ixs) 615 ixsSlots[i] = ix; 616 foreach (immutable i, immutable value; values) 617 valuesSlots[i] = value; 618 static if (mustAddGCRange!Value) 619 GC.addRange(valuesSlots.ptr, _capacity * Value.sizeof); 620 } 621 } 622 else 623 { 624 this(size_t capacity, Ix[] ixs) 625 in 626 { 627 assert(capacity >= ixs.length); 628 assert(ixs.length <= maxCapacity); 629 assert(ixs.isSorted); 630 } 631 do 632 { 633 _capacity = cast(Capacity)capacity; 634 _length = cast(Length)ixs.length; 635 foreach (immutable i, immutable ix; ixs) 636 ixsSlots[i] = ix; 637 } 638 } 639 640 ~this() @nogc 641 { 642 pragma(inline, true); 643 deinit(); 644 } 645 646 private void deinit() @trusted 647 { 648 pragma(inline, true); 649 static if (hasValue && mustAddGCRange!Value) 650 GC.removeRange(valuesSlots.ptr, _capacity * Value.sizeof); 651 } 652 653 auto makeRoom() 654 { 655 auto next = &this; 656 if (full) 657 { 658 if (length < maxCapacity) // if we can expand more 659 { 660 // make room 661 static if (hasValue) 662 next = constructVariableSizeNode!(typeof(this))(length + 1, ixsSlots, valuesSlots); 663 else 664 next = constructVariableSizeNode!(typeof(this))(length + 1, ixsSlots); 665 this.deinit(); free(&this); // clear `this`. TODO: reuse existing helper function in Phobos? 666 } 667 else 668 return null; // indicate that max capacity has been reached 669 } 670 return next; 671 } 672 673 /** Insert `key`, possibly self-reallocating `this` (into return). */ 674 typeof(this)* reconstructingInsert(IxElt!Value elt, 675 out ModStatus modStatus, 676 out size_t index) @trusted 677 { 678 // get index 679 static if (hasValue) 680 immutable ix = elt.ix; 681 else 682 immutable ix = elt; 683 684 // handle existing element 685 if (ixs.assumeSorted.containsStoreIndex(ix, index)) 686 { 687 static if (hasValue) 688 { 689 modStatus = valuesSlots[index] != elt.value ? ModStatus.updated : ModStatus.unchanged; 690 valuesSlots[index] = elt.value; 691 } 692 else 693 modStatus = ModStatus.unchanged; 694 return &this; 695 } 696 697 // try making room for new element 698 auto next = makeRoom(); 699 if (next is null) 700 { 701 modStatus = ModStatus.maxCapacityReached; // TODO: expand to `DenseLeaf1` 702 return &this; 703 } 704 705 // insert new element 706 next.insertAt(index, elt); 707 modStatus = ModStatus.added; 708 709 return next; 710 } 711 712 private void insertAt(size_t index, IxElt!Value elt) 713 { 714 assert(index <= _length); 715 716 foreach (immutable i; 0 .. _length - index) // TODO: functionize this loop or reuse memmove: 717 { 718 immutable iD = _length - i; 719 immutable iS = iD - 1; 720 ixsSlots[iD] = ixsSlots[iS]; 721 } 722 723 static if (hasValue) 724 { 725 ixsSlots[index] = elt.ix; 726 valuesSlots[index] = elt.value; 727 } 728 else 729 { 730 ixsSlots[index] = cast(Ix)elt; 731 } 732 733 ++_length; 734 } 735 736 pragma(inline, true) Length length() const @safe @nogc { return _length; } 737 pragma(inline, true) Capacity capacity() const @safe @nogc { return _capacity; } 738 739 pragma(inline, true) bool empty() const @safe @nogc { return _length == 0; } 740 pragma(inline, true) bool full() const @safe @nogc { return _length == _capacity; } 741 742 /** Get all initialized keys. */ 743 pragma(inline, true) auto ixs() inout @trusted @nogc { return ixsSlots[0 .. _length]; } 744 745 static if (hasValue) 746 { 747 /** Get all intialized values. */ 748 auto values() inout @trusted @nogc 749 { 750 pragma(inline, true) 751 return valuesSlots[0 .. _length]; 752 } 753 754 void setValue(UIx ix, in Value value) @trusted 755 { 756 pragma(inline, true); 757 size_t index; 758 immutable hit = ixs.assumeSorted.containsStoreIndex(ix, index); 759 assert(hit); // assert hit for now 760 assert(index < length); 761 values[index] = value; 762 } 763 764 inout(Value*) contains(UIx key) inout @nogc 765 { 766 pragma(inline, true); 767 size_t index; 768 if (ixs.assumeSorted.containsStoreIndex(key, index)) 769 return &(values[index]); 770 else 771 return null; 772 } 773 } 774 else 775 { 776 bool contains(UIx key) const @nogc 777 { 778 pragma(inline, true); 779 return ixs.assumeSorted.contains(key); 780 } 781 } 782 783 /** Get all reserved keys. */ 784 private auto ixsSlots() inout @trusted @nogc 785 { 786 pragma(inline, true); 787 static if (hasValue) 788 return (cast(Ix*)(_values.ptr + _capacity))[0 .. _capacity]; 789 else 790 return _ixs.ptr[0 .. _capacity]; 791 } 792 static if (hasValue) 793 { 794 /** Get all reserved values. */ 795 private auto valuesSlots() inout @trusted @nogc 796 { 797 pragma(inline, true); 798 return _values.ptr[0 .. _capacity]; 799 } 800 } 801 802 /** Get allocation size (in bytes) needed to hold `length` number of 803 * elements (keys and optionally values). 804 */ 805 static size_t allocationSizeOfCapacity(size_t capacity) @safe pure nothrow @nogc 806 { 807 static if (hasValue) 808 return (this.sizeof + // base plus 809 Value.sizeof*capacity + // actual size of `_values` 810 Ix.sizeof*capacity); // actual size of `_ixs` 811 else 812 return (this.sizeof + // base plus 813 Ix.sizeof*capacity); // actual size of `_ixs` 814 } 815 816 /** Get allocated size (in bytes) of `this` including the variable-length part. 817 */ 818 size_t allocatedSize() const @safe pure nothrow @nogc 819 { 820 return allocationSizeOfCapacity(_capacity); 821 } 822 823 private: 824 Length _length; 825 const Capacity _capacity; 826 static if (hasValue) 827 Value[0] _values; 828 Ix[0] _ixs; 829 } 830 831 /** Densely coded leaves with values of type `Value`. */ 832 static private struct DenseLeaf1(Value) 833 { 834 import nxt.static_bitarray : StaticBitArray; 835 836 enum hasValue = !is(Value == void); 837 838 static if (hasValue) 839 enum hasGCScannedValues = !is(Value == bool) && mustAddGCRange!Value; 840 else 841 enum hasGCScannedValues = false; 842 843 static if (hasGCScannedValues) 844 import core.memory : GC; 845 846 enum capacity = radix; 847 848 @safe pure nothrow @nogc: 849 850 static if (hasValue) 851 { 852 this(Ix[] ixs, Value[] values) 853 { 854 assert(ixs.length <= capacity); 855 assert(ixs.length == values.length); 856 foreach (immutable i, immutable ix; ixs) 857 { 858 _ixBits[ix] = true; 859 _values[ix] = values[i]; 860 } 861 static if (hasGCScannedValues) 862 GC.addRange(_values.ptr, capacity * Value.size); 863 } 864 865 this(ref StaticBitArray!capacity ixBits, Value[] values) 866 { 867 assert(ixBits.length == values.length); 868 _ixBits = ixBits; 869 _values[] = values[]; // TODO: commenting out does not affect unittests 870 static if (hasGCScannedValues) 871 GC.addRange(_values.ptr, capacity * Value.size); 872 } 873 } 874 else 875 { 876 this(Ix[] ixs) 877 { 878 assert(ixs.length <= capacity); 879 foreach (immutable ix; ixs) 880 _ixBits[ix] = true; 881 } 882 883 this(const ref StaticBitArray!capacity ixBits) 884 { 885 _ixBits = ixBits; 886 } 887 } 888 889 890 /** Returns a an allocated duplicate of this. 891 Shallowly duplicates the values in the map case. 892 */ 893 typeof(this)* dup() 894 { 895 pragma(inline, true); 896 static if (hasValue) 897 return constructFixedSizeNode!(typeof(this)*)(_ixBits, _values); 898 else 899 return constructFixedSizeNode!(typeof(this)*)(_ixBits); 900 } 901 902 ~this() @nogc 903 { 904 pragma(inline, true); 905 static if (hasGCScannedValues) 906 GC.removeRange(_values.ptr, capacity * Value.size); 907 } 908 909 pragma(inline, true) bool empty() const { return _ixBits.allZero; } 910 pragma(inline, true) bool full() const { return _ixBits.allOne; } 911 pragma(inline, true) size_t count() const { return _ixBits.countOnes; } 912 913 static if (hasValue) 914 inout(Value*) contains(UIx ix) inout 915 { 916 pragma(inline, true); 917 return _ixBits[ix] ? &(_values[ix]) : null; 918 } 919 else 920 bool contains(UIx ix) const 921 { 922 pragma(inline, true); 923 return _ixBits[ix]; 924 } 925 926 ModStatus insert(IxElt!Value elt) 927 { 928 pragma(inline, true); 929 930 ModStatus modStatus; 931 932 static if (hasValue) 933 immutable ix = elt.ix; 934 else 935 immutable ix = elt; 936 937 if (contains(ix)) 938 { 939 static if (hasValue) 940 modStatus = _values[ix] != elt.value ? ModStatus.updated : ModStatus.unchanged; 941 else 942 modStatus = ModStatus.unchanged; 943 } 944 else 945 { 946 _ixBits[ix] = true; 947 modStatus = ModStatus.added; 948 } 949 950 // set element 951 static if (hasValue) 952 _values[ix] = elt.value; 953 954 return modStatus; 955 } 956 957 /** Try to find index to first set bit in `_ixBits` starting at bit index `ix` and put the result in `nextIx`. 958 Returns: `true` upon find, `false` otherwise. 959 TODO: move to StaticBitArray 960 */ 961 bool tryFindSetBitIx(UIx ix, out UIx nextIx) const 962 { 963 pragma(inline, true); 964 assert(!_ixBits.allZero); 965 return _ixBits.canFindIndexOf(true, ix, nextIx); 966 } 967 968 bool tryFindNextSetBitIx(UIx ix, out UIx nextIx) const 969 { 970 pragma(inline, true); 971 immutable ix1 = cast(uint)(ix + 1); 972 return ix1 != radix && tryFindSetBitIx(UIx(ix1), nextIx); 973 } 974 975 static if (hasValue) 976 { 977 /** Set value at index `ix` to `value`. */ 978 void setValue(UIx ix, in Value value) 979 { 980 pragma(inline, true); 981 _values[ix] = value; 982 } 983 984 auto values() inout 985 { 986 pragma(inline, true); 987 return _values; 988 } 989 } 990 991 private: 992 StaticBitArray!capacity _ixBits; // 32 bytes 993 static if (hasValue) 994 { 995 // static if (is(Value == bool)) 996 // { 997 // StaticBitArray!capacity _values; // packed values 998 // } 999 // else 1000 // { 1001 // Value[capacity] _values; 1002 // } 1003 Value[capacity] _values; 1004 } 1005 } 1006 1007 /** Fixed-Length leaf Key-only Node. */ 1008 alias FixedKeyLeafN = WordVariant!(OneLeafMax7, 1009 TwoLeaf3, 1010 TriLeaf2); 1011 1012 /** Mutable leaf node of 1-Ix leaves. 1013 * 1014 * Used by branch-leaf. 1015 */ 1016 alias Leaf1(Value) = WordVariant!(HeptLeaf1, // TODO: remove from case when Value is void 1017 SparseLeaf1!Value*, 1018 DenseLeaf1!Value*); 1019 1020 /** Returns: `true` if `key` is stored under `curr`, `false` otherwise. */ 1021 UIx firstIx(Value)(Leaf1!Value curr) 1022 { 1023 final switch (curr.typeIx) with (Leaf1!Value.Ix) 1024 { 1025 case undefined: 1026 assert(false); 1027 case ix_HeptLeaf1: 1028 case ix_SparseLeaf1Ptr: 1029 return 0; // always first 1030 case ix_DenseLeaf1Ptr: 1031 auto curr_ = curr.as!(DenseLeaf1!Value*); 1032 UIx nextIx; 1033 immutable bool hit = curr_.tryFindSetBitIx(0, nextIx); 1034 assert(hit); 1035 return nextIx; 1036 } 1037 } 1038 1039 /** Try to iterate leaf index `ix` to index, either sparse or dense and put result in `nextIx`. 1040 * 1041 * Returns: `true` if `nextIx` was set, `false` if no more indexes was available. 1042 */ 1043 pragma(inline) bool tryNextIx(Value)(Leaf1!Value curr, const UIx ix, out Ix nextIx) 1044 { 1045 final switch (curr.typeIx) with (Leaf1!Value.Ix) 1046 { 1047 case undefined: 1048 assert(false); 1049 case ix_HeptLeaf1: 1050 immutable curr_ = curr.as!(HeptLeaf1); 1051 if (ix + 1 == curr_.keys.length) 1052 { 1053 return false; 1054 } 1055 else 1056 { 1057 nextIx = Ix(ix + 1); 1058 return true; 1059 } 1060 case ix_SparseLeaf1Ptr: 1061 immutable curr_ = curr.as!(SparseLeaf1!Value*); 1062 if (ix + 1 == curr_.length) 1063 { 1064 return false; 1065 } 1066 else 1067 { 1068 nextIx = Ix(ix + 1); 1069 return true; 1070 } 1071 case ix_DenseLeaf1Ptr: 1072 return curr.as!(DenseLeaf1!Value*).tryFindNextSetBitIx(ix, nextIx); 1073 } 1074 } 1075 1076 static assert((DenseLeaf1!void).sizeof == 32); 1077 1078 /** Adaptive radix tree (ART) container storing untyped (raw) keys. 1079 1080 In set-case (`Value` is `void`) this container contains specific memory 1081 optimizations for representing a set pointers or integral types (of fixed 1082 length). 1083 1084 Radix-trees are suitable for storing ordered sets/maps with variable-length 1085 keys and provide completion of all its keys matching a given 1086 key-prefix. This enables, for instance, efficient storage and retrieval of 1087 large sets of long URLs with high probability of sharing a common prefix, 1088 typically a domain and path. 1089 1090 Branch packing of leaves is more efficient when `Key.sizeof` is fixed, that 1091 is, the member `hasFixedKeyLength` returns `true`. 1092 1093 For optimal performance, the individual bit-chunks should be arranged 1094 starting with most sparse chunks first. For integers this means most 1095 significant chunk (byte) first. This includes IEEE-compliant floating point 1096 numbers. 1097 1098 For a good introduction to adaptive radix trees (ART) see $(HTTP infosys.cs.uni-saarland.de/publications/ARCD15.pdf) 1099 1100 See_Also: $(HTTP www.ietf.org/rfc/rfc2616.txt, RFC2616) 1101 1102 See_Also: $(HTTP en.wikipedia.org/wiki/Trie) 1103 See_Also: $(HTTP en.wikipedia.org/wiki/Radix_tree) 1104 See_Also: $(HTTP github.com/npgall/concurrent-trees) 1105 See_Also: $(HTTP code.dogmap.org/kart/) 1106 See_Also: $(HTTP cr.yp.to/critbit.html) 1107 See_Also: $(HTTP gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/trie_based_containers.html) 1108 See_Also: $(HTTP github.com/npgall/concurrent-trees) 1109 */ 1110 template RawRadixTree(Value = void) 1111 { 1112 import std.bitmanip : bitfields; 1113 import std.algorithm.iteration : filter; 1114 import std.meta : AliasSeq, staticMap; 1115 1116 import nxt.static_bitarray : StaticBitArray; 1117 1118 enum isValue = !is(Value == void); 1119 1120 version(useModulo) 1121 { 1122 alias SubCount = Mod!(radix + 1); 1123 } 1124 else 1125 { 1126 alias SubCount = uint; // needed because for inclusive range 0 .. 256 1127 } 1128 1129 struct IxSub { UIx ix; Node node; } 1130 1131 /** Sparse/Packed dynamically sized branch implemented as variable-length 1132 struct. 1133 */ 1134 static private struct SparseBranch 1135 { 1136 enum minCapacity = 0; // minimum number of preallocated sub-indexes and sub-nodes 1137 enum maxCapacity = 48; // maximum number of preallocated sub-indexes and sub-nodes 1138 enum prefixCapacity = 5; // 5, 13, 21, ... 1139 1140 version(useModulo) 1141 { 1142 alias Count = Mod!(maxCapacity + 1); 1143 } 1144 else 1145 { 1146 alias Count = ubyte; 1147 } 1148 1149 @safe pure nothrow: 1150 1151 this(size_t subCapacity) 1152 { 1153 version(LDC) pragma(inline, true); 1154 initialize(subCapacity); 1155 } 1156 1157 this(size_t subCapacity, const Ix[] prefix, Leaf1!Value leaf1) 1158 { 1159 version(LDC) pragma(inline, true); 1160 initialize(subCapacity); 1161 this.prefix = prefix; 1162 this.leaf1 = leaf1; 1163 } 1164 1165 this(size_t subCapacity, const Ix[] prefix) 1166 { 1167 version(LDC) pragma(inline, true); 1168 initialize(subCapacity); 1169 this.prefix = prefix; 1170 } 1171 1172 this(size_t subCapacity, Leaf1!Value leaf1) 1173 { 1174 version(LDC) pragma(inline, true); 1175 initialize(subCapacity); 1176 this.leaf1 = leaf1; 1177 } 1178 1179 this(size_t subCapacity, const Ix[] prefix, IxSub sub) 1180 { 1181 version(LDC) pragma(inline, true); 1182 1183 assert(subCapacity); 1184 1185 initialize(subCapacity); 1186 1187 this.prefix = prefix; 1188 this.subCount = 1; 1189 this.subIxSlots[0] = sub.ix; 1190 this.subNodeSlots[0] = sub.node; 1191 } 1192 1193 this(size_t subCapacity, typeof(this)* rhs) 1194 in 1195 { 1196 assert(subCapacity > rhs.subCapacity); 1197 assert(rhs); 1198 } 1199 do 1200 { 1201 version(LDC) pragma(inline, true); 1202 // these two must be in this order: 1203 // 1. 1204 move(rhs.leaf1, this.leaf1); 1205 debug rhs.leaf1 = typeof(rhs.leaf1).init; 1206 this.subCount = rhs.subCount; 1207 move(rhs.prefix, this.prefix); 1208 1209 // 2. 1210 initialize(subCapacity); 1211 1212 // copy variable length part. TODO: optimize: 1213 this.subIxSlots[0 .. rhs.subCount] = rhs.subIxSlots[0 .. rhs.subCount]; 1214 this.subNodeSlots[0 .. rhs.subCount] = rhs.subNodeSlots[0 .. rhs.subCount]; 1215 1216 assert(this.subCapacity > rhs.subCapacity); 1217 } 1218 1219 private pragma(inline, true) void initialize(size_t subCapacity) 1220 { 1221 // assert(subCapacity != 4); 1222 this.subCapacity = cast(Count)subCapacity; 1223 debug // only zero-initialize in debug mode 1224 { 1225 // zero-initialize variable-length part 1226 subIxSlots[] = Ix.init; 1227 subNodeSlots[] = Node.init; 1228 } 1229 } 1230 1231 typeof(this)* dup() @nogc 1232 { 1233 auto copy = constructVariableSizeNode!(typeof(this))(this.subCapacity); 1234 copy.leaf1 = dupAt(this.leaf1); 1235 copy.prefix = this.prefix; 1236 copy.subCount = this.subCount; 1237 1238 copy.subIxSlots[0 .. subCount] = this.subIxSlots[0 .. subCount]; // copy initialized 1239 debug copy.subIxSlots[subCount .. $] = Ix.init; // zero rest in debug 1240 1241 foreach (immutable i; 0 .. subCount) 1242 { 1243 copy.subNodeSlots[i] = dupAt(subNodeSlots[i]); 1244 } 1245 return copy; 1246 } 1247 1248 pragma(inline, true) ~this() @nogc { deinit(); } 1249 1250 private pragma(inline, true) void deinit() @nogc { /* nothing for now */ } 1251 1252 /** Insert `sub`, possibly self-reallocating `this` (into return). 1253 */ 1254 typeof(this)* reconstructingInsert(IxSub sub, 1255 out ModStatus modStatus, 1256 out size_t index) @trusted 1257 { 1258 auto next = &this; 1259 1260 import nxt.searching_ex : containsStoreIndex; 1261 if (subIxs.containsStoreIndex(sub.ix, index)) 1262 { 1263 assert(subIxSlots[index] == sub.ix); // subIxSlots[index] = sub[0]; 1264 subNodeSlots[index] = sub.node; 1265 modStatus = ModStatus.updated; 1266 return next; 1267 } 1268 1269 if (full) 1270 { 1271 if (subCount < maxCapacity) // if we can expand more 1272 { 1273 next = constructVariableSizeNode!(typeof(this))(subCount + 1, &this); 1274 1275 this.deinit(); free(&this); // clear `this`. TODO: reuse existing helper function in Phobos? 1276 } 1277 else 1278 { 1279 modStatus = ModStatus.maxCapacityReached; // TODO: expand to `DenseBranch` 1280 return next; 1281 } 1282 } 1283 1284 next.insertAt(index, sub); 1285 modStatus = ModStatus.added; 1286 return next; 1287 } 1288 1289 private void insertAt(size_t index, IxSub sub) 1290 { 1291 assert(index <= subCount); 1292 foreach (immutable i; 0 .. subCount - index) // TODO: functionize this loop or reuse memmove: 1293 { 1294 immutable iD = subCount - i; 1295 immutable iS = iD - 1; 1296 subIxSlots[iD] = subIxSlots[iS]; 1297 subNodeSlots[iD] = subNodeSlots[iS]; 1298 } 1299 subIxSlots[index] = cast(Ix)sub.ix; // set new element 1300 subNodeSlots[index] = sub.node; // set new element 1301 ++subCount; 1302 } 1303 1304 inout(Node) subNodeAt(UIx ix) inout 1305 { 1306 import nxt.searching_ex : binarySearch; // need this instead of `SortedRange.contains` because we need the index 1307 immutable hitIndex = subIxSlots[0 .. subCount].binarySearch(ix); // find index where insertion should be made 1308 return (hitIndex != typeof(hitIndex).max) ? subNodeSlots[hitIndex] : Node.init; 1309 } 1310 1311 pragma(inline, true) bool empty() const @nogc { return subCount == 0; } 1312 pragma(inline, true) bool full() const @nogc { return subCount == subCapacity; } 1313 1314 pragma(inline, true) auto subIxs() inout @nogc 1315 { 1316 import std.range : assumeSorted; 1317 return subIxSlots[0 .. subCount].assumeSorted; 1318 } 1319 1320 pragma(inline, true) auto subNodes() inout @nogc { return subNodeSlots[0 .. subCount]; } 1321 1322 pragma(inline, true) Node firstSubNode() @nogc 1323 { 1324 return subCount ? subNodeSlots[0] : typeof(return).init; 1325 } 1326 1327 /** Get all sub-`Ix` slots, both initialized and uninitialized. */ 1328 private auto subIxSlots() inout @trusted pure nothrow 1329 { 1330 return (cast(Ix*)(_subNodeSlots0.ptr + subCapacity))[0 .. subCapacity]; 1331 } 1332 /** Get all sub-`Node` slots, both initialized and uninitialized. */ 1333 private auto subNodeSlots() inout @trusted pure nothrow 1334 { 1335 return _subNodeSlots0.ptr[0 .. subCapacity]; 1336 } 1337 1338 /** Append statistics of tree under `this` into `stats`. */ 1339 void calculate(ref Stats stats) const 1340 { 1341 size_t count = 0; // number of non-zero sub-nodes 1342 foreach (immutable sub; subNodes) 1343 { 1344 ++count; 1345 sub.calculate!(Value)(stats); 1346 } 1347 assert(count <= radix); 1348 ++stats.popHist_SparseBranch[count]; // TODO: type-safe indexing 1349 1350 stats.sparseBranchAllocatedSizeSum += allocatedSize; 1351 1352 if (leaf1) 1353 leaf1.calculate!(Value)(stats); 1354 } 1355 1356 /** Get allocation size (in bytes) needed to hold `length` number of 1357 sub-indexes and sub-nodes. */ 1358 static size_t allocationSizeOfCapacity(size_t capacity) @safe pure nothrow @nogc 1359 { 1360 return (this.sizeof + // base plus 1361 Node.sizeof*capacity + // actual size of `_subNodeSlots0` 1362 Ix.sizeof*capacity); // actual size of `_subIxSlots0` 1363 } 1364 1365 /** Get allocated size (in bytes) of `this` including the variable-length part. */ 1366 size_t allocatedSize() const @safe pure nothrow @nogc 1367 { 1368 return allocationSizeOfCapacity(subCapacity); 1369 } 1370 1371 private: 1372 1373 // members in order of decreasing `alignof`: 1374 Leaf1!Value leaf1; 1375 1376 IxsN!(prefixCapacity, 1) prefix; // prefix common to all `subNodes` (also called edge-label) 1377 Count subCount; 1378 Count subCapacity; 1379 static assert(prefix.sizeof + subCount.sizeof + subCapacity.sizeof == 8); // assert alignment 1380 1381 // variable-length part 1382 Node[0] _subNodeSlots0; 1383 Ix[0] _subIxSlots0; // needs to special alignment 1384 } 1385 1386 static assert(hasVariableSize!SparseBranch); 1387 static if (!isValue) 1388 static assert(SparseBranch.sizeof == 16); 1389 1390 /** Dense/Unpacked `radix`-branch with `radix` number of sub-nodes. */ 1391 static private struct DenseBranch 1392 { 1393 enum maxCapacity = 256; 1394 enum prefixCapacity = 15; // 7, 15, 23, ..., we can afford larger prefix here because DenseBranch is so large 1395 1396 @safe pure nothrow: 1397 1398 this(const Ix[] prefix) 1399 { 1400 this.prefix = prefix; 1401 } 1402 1403 this(const Ix[] prefix, IxSub sub) 1404 { 1405 this(prefix); 1406 this.subNodes[sub.ix] = sub.node; 1407 } 1408 1409 this(const Ix[] prefix, IxSub subA, IxSub subB) 1410 { 1411 assert(subA.ix != subB.ix); // disjunct indexes 1412 assert(subA.node != subB.node); // disjunct nodes 1413 1414 this.subNodes[subA.ix] = subA.node; 1415 this.subNodes[subB.ix] = subB.node; 1416 } 1417 1418 this(SparseBranch* rhs) 1419 { 1420 this.prefix = rhs.prefix; 1421 1422 // move leaf 1423 move(rhs.leaf1, this.leaf1); 1424 debug rhs.leaf1 = Leaf1!Value.init; // make reference unique, to be on the safe side 1425 1426 foreach (immutable i; 0 .. rhs.subCount) // each sub node. TODO: use iota!(Mod!N) 1427 { 1428 immutable iN = (cast(ubyte)i).mod!(SparseBranch.maxCapacity); 1429 immutable subIx = UIx(rhs.subIxSlots[iN]); 1430 1431 this.subNodes[subIx] = rhs.subNodeSlots[iN]; 1432 debug rhs.subNodeSlots[iN] = null; // make reference unique, to be on the safe side 1433 } 1434 } 1435 1436 typeof(this)* dup() @trusted // TODO: remove @trusted qualifier when .ptr problem has been fixed 1437 { 1438 auto copy = constructFixedSizeNode!(typeof(this)*); 1439 copy.leaf1 = dupAt(leaf1); 1440 copy.prefix = prefix; 1441 foreach (immutable i, subNode; subNodes) 1442 { 1443 copy.subNodes.ptr[i] = dupAt(subNode); // TODO: remove .ptr access when I inout problem is solved 1444 } 1445 return copy; 1446 } 1447 1448 /** Number of non-null sub-Nodes. */ 1449 SubCount subCount() const 1450 { 1451 typeof(return) count = 0; // number of non-zero sub-nodes 1452 foreach (immutable subNode; subNodes) // TODO: why can't we use std.algorithm.count here? 1453 if (subNode) 1454 ++count; 1455 assert(count <= radix); 1456 return count; 1457 } 1458 1459 bool findSubNodeAtIx(size_t currIx, out UIx nextIx) inout @nogc 1460 { 1461 import std.algorithm.searching : countUntil; 1462 immutable cnt = subNodes[currIx .. $].countUntil!(subNode => cast(bool)subNode); 1463 immutable bool hit = cnt >= 0; 1464 if (hit) 1465 { 1466 const nextIx_ = currIx + cnt; 1467 assert(nextIx_ <= Ix.max); 1468 nextIx = cast(Ix)nextIx_; 1469 } 1470 return hit; 1471 } 1472 1473 /** Append statistics of tree under `this` into `stats`. */ 1474 void calculate(ref Stats stats) const 1475 { 1476 size_t count = 0; // number of non-zero sub-nodes 1477 foreach (immutable subNode; subNodes) 1478 { 1479 if (subNode) 1480 { 1481 ++count; 1482 subNode.calculate!(Value)(stats); 1483 } 1484 } 1485 assert(count <= radix); 1486 ++stats.popHist_DenseBranch[count]; // TODO: type-safe indexing 1487 if (leaf1) 1488 leaf1.calculate!(Value)(stats); 1489 } 1490 1491 private: 1492 // members in order of decreasing `alignof`: 1493 Leaf1!Value leaf1; 1494 IxsN!(prefixCapacity, 1) prefix; // prefix (edge-label) common to all `subNodes` 1495 IndexedBy!(Node[radix], UIx) subNodes; 1496 } 1497 1498 version(showBranchSizes) 1499 { 1500 pragma(msg, "SparseBranch.sizeof:", SparseBranch.sizeof, " SparseBranch.alignof:", SparseBranch.alignof); 1501 pragma(msg, "DenseBranch.sizeof:", DenseBranch.sizeof, " DenseBranch.alignof:", DenseBranch.alignof); 1502 1503 pragma(msg, "SparseBranch.prefix.sizeof:", SparseBranch.prefix.sizeof, " SparseBranch.prefix.alignof:", SparseBranch.prefix.alignof); 1504 pragma(msg, "DenseBranch.prefix.sizeof:", DenseBranch.prefix.sizeof, " DenseBranch.prefix.alignof:", DenseBranch.prefix.alignof); 1505 1506 // pragma(msg, "SparseBranch.subNodes.sizeof:", SparseBranch.subNodes.sizeof, " SparseBranch.subNodes.alignof:", SparseBranch.subNodes.alignof); 1507 // pragma(msg, "SparseBranch.subIxs.sizeof:", SparseBranch.subIxs.sizeof, " SparseBranch.subIxs.alignof:", SparseBranch.subIxs.alignof); 1508 } 1509 1510 // TODO: make these run-time arguments at different key depths and map to statistics of typed-key 1511 alias DefaultBranch = SparseBranch; // either `SparseBranch`, `DenseBranch` 1512 1513 /** Mutable node. */ 1514 alias Node = WordVariant!(OneLeafMax7, 1515 TwoLeaf3, 1516 TriLeaf2, 1517 1518 HeptLeaf1, 1519 SparseLeaf1!Value*, 1520 DenseLeaf1!Value*, 1521 1522 SparseBranch*, 1523 DenseBranch*); 1524 1525 /** Mutable branch node. */ 1526 alias Branch = WordVariant!(SparseBranch*, 1527 DenseBranch*); 1528 1529 static assert(Node.typeBits <= IxsN!(7, 1).typeBits); 1530 static assert(Leaf1!Value.typeBits <= IxsN!(7, 1).typeBits); 1531 static assert(Branch.typeBits <= IxsN!(7, 1).typeBits); 1532 1533 /** Constant node. */ 1534 // TODO: make work with indexNaming 1535 // import std.typecons : ConstOf; 1536 // alias ConstNodePtr = WordVariant!(staticMap!(ConstOf, Node)); 1537 1538 static assert(span <= 8*Ix.sizeof, "Need more precision in Ix"); 1539 1540 /** Element reference. */ 1541 private static struct ElementRef 1542 { 1543 Node node; 1544 UIx ix; // `Node`-specific counter, typically either a sparse or dense index either a sub-branch or a `UKey`-ending `Ix` 1545 ModStatus modStatus; 1546 1547 pragma(inline, true) 1548 @safe pure nothrow: 1549 1550 bool opCast(T : bool)() const @nogc 1551 { 1552 return cast(bool)node; 1553 } 1554 } 1555 1556 /** Branch Range (Iterator). */ 1557 private static struct BranchRange 1558 { 1559 @safe pure nothrow: 1560 1561 this(SparseBranch* branch) 1562 { 1563 this.branch = Branch(branch); 1564 1565 this._subsEmpty = branch.subCount == 0; 1566 this._subCounter = 0; // always zero 1567 1568 if (branch.leaf1) 1569 this.leaf1Range = Leaf1Range(branch.leaf1); 1570 1571 cacheFront(); 1572 } 1573 1574 this(DenseBranch* branch) 1575 { 1576 this.branch = Branch(branch); 1577 1578 this._subCounter = 0; // TODO: needed? 1579 _subsEmpty = !branch.findSubNodeAtIx(0, this._subCounter); 1580 1581 if (branch.leaf1) 1582 this.leaf1Range = Leaf1Range(branch.leaf1); 1583 1584 cacheFront(); 1585 } 1586 1587 pragma(inline, true) UIx frontIx() const @nogc 1588 { 1589 assert(!empty); 1590 return _cachedFrontIx; 1591 } 1592 1593 pragma(inline, true) bool atLeaf1() const @nogc 1594 { 1595 assert(!empty); 1596 return _frontAtLeaf1; 1597 } 1598 1599 private UIx subFrontIx() const 1600 { 1601 final switch (branch.typeIx) with (Branch.Ix) 1602 { 1603 case undefined: 1604 assert(false); 1605 case ix_SparseBranchPtr: 1606 return UIx(branch.as!(SparseBranch*).subIxs[_subCounter]); 1607 case ix_DenseBranchPtr: 1608 return _subCounter; 1609 } 1610 } 1611 1612 private Node subFrontNode() const 1613 { 1614 final switch (branch.typeIx) with (Branch.Ix) 1615 { 1616 case undefined: 1617 assert(false); 1618 case ix_SparseBranchPtr: return branch.as!(SparseBranch*).subNodeSlots[_subCounter]; 1619 case ix_DenseBranchPtr: return branch.as!(DenseBranch*).subNodes[_subCounter]; 1620 } 1621 } 1622 1623 void appendFrontIxsToKey(ref Array!Ix key) const @nogc 1624 { 1625 final switch (branch.typeIx) with (Branch.Ix) 1626 { 1627 case undefined: 1628 assert(false); 1629 case ix_SparseBranchPtr: 1630 key ~= branch.as!(SparseBranch*).prefix[]; 1631 break; 1632 case ix_DenseBranchPtr: 1633 key ~= branch.as!(DenseBranch*).prefix[]; 1634 break; 1635 } 1636 key ~= cast(Ix)frontIx; // uses cached data so ok to not depend on branch type 1637 } 1638 1639 size_t prefixLength() const @nogc 1640 { 1641 final switch (branch.typeIx) with (Branch.Ix) 1642 { 1643 case undefined: 1644 assert(false); 1645 case ix_SparseBranchPtr: return branch.as!(SparseBranch*).prefix.length; 1646 case ix_DenseBranchPtr: return branch.as!(DenseBranch*).prefix.length; 1647 } 1648 } 1649 1650 pragma(inline, true) bool empty() const @nogc { return leaf1Range.empty && _subsEmpty; } 1651 pragma(inline, true) bool subsEmpty() const @nogc { return _subsEmpty; } 1652 1653 /** Try to iterated forward. 1654 Returns: `true` upon successful forward iteration, `false` otherwise (upon completion of iteration), 1655 */ 1656 void popFront() 1657 { 1658 assert(!empty); 1659 1660 // pop front element 1661 if (_subsEmpty) 1662 leaf1Range.popFront(); 1663 else if (leaf1Range.empty) 1664 popBranchFront(); 1665 else // both non-empty 1666 { 1667 if (leaf1Range.front <= subFrontIx) // `a` before `ab` 1668 leaf1Range.popFront(); 1669 else 1670 popBranchFront(); 1671 } 1672 1673 if (!empty) { cacheFront(); } 1674 } 1675 1676 /** Fill cached value and remember if we we next element is direct 1677 (_frontAtLeaf1 is true) or under a sub-branch (_frontAtLeaf1 is 1678 false). 1679 */ 1680 void cacheFront() 1681 { 1682 assert(!empty); 1683 if (_subsEmpty) // no more sub-nodes 1684 { 1685 _cachedFrontIx = leaf1Range.front; 1686 _frontAtLeaf1 = true; 1687 } 1688 else if (leaf1Range.empty) // no more in direct leaf node 1689 { 1690 _cachedFrontIx = subFrontIx; 1691 _frontAtLeaf1 = false; 1692 } 1693 else // both non-empty 1694 { 1695 immutable leaf1Front = leaf1Range.front; 1696 if (leaf1Front <= subFrontIx) // `a` before `ab` 1697 { 1698 _cachedFrontIx = leaf1Front; 1699 _frontAtLeaf1 = true; 1700 } 1701 else 1702 { 1703 _cachedFrontIx = subFrontIx; 1704 _frontAtLeaf1 = false; 1705 } 1706 } 1707 } 1708 1709 private void popBranchFront() 1710 { 1711 // TODO: move all calls to Branch-specific members popFront() 1712 final switch (branch.typeIx) with (Branch.Ix) 1713 { 1714 case undefined: 1715 assert(false); 1716 case ix_SparseBranchPtr: 1717 auto branch_ = branch.as!(SparseBranch*); 1718 if (_subCounter + 1 == branch_.subCount) 1719 _subsEmpty = true; 1720 else 1721 ++_subCounter; 1722 break; 1723 case ix_DenseBranchPtr: 1724 auto branch_ = branch.as!(DenseBranch*); 1725 _subsEmpty = !branch_.findSubNodeAtIx(_subCounter + 1, this._subCounter); 1726 break; 1727 } 1728 } 1729 1730 private: 1731 Branch branch; // branch part of range 1732 Leaf1Range leaf1Range; // range of direct leaves 1733 1734 UIx _subCounter; // `Branch`-specific counter, typically either a sparse or dense index either a sub-branch or a `UKey`-ending `Ix` 1735 UIx _cachedFrontIx; 1736 1737 bool _frontAtLeaf1; // `true` iff front is currently at a leaf1 element 1738 bool _subsEmpty; // `true` iff no sub-nodes exists 1739 } 1740 1741 /** Leaf1 Range (Iterator). */ 1742 private static struct Leaf1Range 1743 { 1744 this(Leaf1!Value leaf1) 1745 { 1746 this.leaf1 = leaf1; 1747 bool empty; 1748 this._ix = firstIx(empty); 1749 if (empty) 1750 this.leaf1 = null; 1751 } 1752 1753 @safe pure nothrow: 1754 1755 /** Get first index in current subkey. */ 1756 UIx front() const 1757 { 1758 assert(!empty); 1759 final switch (leaf1.typeIx) with (Leaf1!Value.Ix) 1760 { 1761 case undefined: 1762 assert(false); 1763 case ix_HeptLeaf1: 1764 static if (isValue) 1765 assert(false, "HeptLeaf1 cannot store a value"); 1766 else 1767 return UIx(leaf1.as!(HeptLeaf1).keys[_ix]); 1768 case ix_SparseLeaf1Ptr: 1769 return UIx(leaf1.as!(SparseLeaf1!Value*).ixs[_ix]); 1770 case ix_DenseLeaf1Ptr: 1771 return _ix; 1772 } 1773 } 1774 1775 static if (isValue) 1776 { 1777 Value frontValue() const 1778 { 1779 assert(!empty); 1780 final switch (leaf1.typeIx) with (Leaf1!Value.Ix) 1781 { 1782 case undefined: 1783 assert(false); 1784 case ix_HeptLeaf1: assert(false, "HeptLeaf1 cannot store a value"); 1785 case ix_SparseLeaf1Ptr: 1786 return leaf1.as!(SparseLeaf1!Value*).values[_ix]; 1787 case ix_DenseLeaf1Ptr: 1788 return leaf1.as!(DenseLeaf1!Value*).values[_ix]; 1789 } 1790 } 1791 } 1792 1793 bool empty() const @nogc { return leaf1.isNull; } 1794 1795 /** Pop front element. 1796 */ 1797 void popFront() 1798 { 1799 assert(!empty); 1800 1801 // TODO: move all calls to leaf1-specific members popFront() 1802 final switch (leaf1.typeIx) with (Leaf1!Value.Ix) 1803 { 1804 case undefined: 1805 assert(false); 1806 case ix_HeptLeaf1: 1807 static if (isValue) 1808 assert(false, "HeptLeaf1 cannot store a value"); 1809 else 1810 { 1811 immutable leaf_ = leaf1.as!(HeptLeaf1); 1812 if (_ix + 1 == leaf_.keys.length) 1813 leaf1 = null; 1814 else 1815 ++_ix; 1816 break; 1817 } 1818 case ix_SparseLeaf1Ptr: 1819 const leaf_ = leaf1.as!(SparseLeaf1!Value*); 1820 if (_ix + 1 == leaf_.length) 1821 leaf1 = null; 1822 else 1823 ++_ix; 1824 break; 1825 case ix_DenseLeaf1Ptr: 1826 const leaf_ = leaf1.as!(DenseLeaf1!Value*); 1827 if (!leaf_.tryFindNextSetBitIx(_ix, _ix)) 1828 leaf1 = null; 1829 break; 1830 } 1831 } 1832 1833 static if (isValue) 1834 { 1835 auto ref value() inout 1836 { 1837 final switch (leaf1.typeIx) with (Leaf1!Value.Ix) 1838 { 1839 case undefined: 1840 assert(false); 1841 case ix_HeptLeaf1: assert(false, "HeptLeaf1 cannot store a value"); 1842 case ix_SparseLeaf1Ptr: return leaf1.as!(SparseLeaf1!Value*).values[_ix]; 1843 case ix_DenseLeaf1Ptr: return leaf1.as!(DenseLeaf1!Value*).values[_ix]; 1844 } 1845 } 1846 } 1847 1848 private UIx firstIx(out bool empty) const 1849 { 1850 final switch (leaf1.typeIx) with (Leaf1!Value.Ix) 1851 { 1852 case undefined: 1853 assert(false); 1854 case ix_HeptLeaf1: 1855 static if (isValue) 1856 assert(false, "HeptLeaf1 cannot store a value"); 1857 else 1858 return UIx(0); // always first 1859 case ix_SparseLeaf1Ptr: 1860 auto leaf_ = leaf1.as!(SparseLeaf1!Value*); 1861 empty = leaf_.empty; 1862 return UIx(0); // always first 1863 case ix_DenseLeaf1Ptr: 1864 auto leaf_ = leaf1.as!(DenseLeaf1!Value*); 1865 UIx nextIx; 1866 immutable bool hit = leaf_.tryFindSetBitIx(UIx(0), nextIx); 1867 assert(hit); 1868 return nextIx; 1869 } 1870 } 1871 1872 private: 1873 Leaf1!Value leaf1; // TODO: Use Leaf1!Value-WordVariant when it includes non-Value leaf1 types 1874 UIx _ix; // `Node`-specific counter, typically either a sparse or dense index either a sub-branch or a `UKey`-ending `Ix` 1875 } 1876 1877 /** Leaf Value Range (Iterator). */ 1878 private static struct LeafNRange 1879 { 1880 this(Node leaf) 1881 { 1882 this.leaf = leaf; 1883 bool emptied; 1884 this.ix = firstIx(emptied); 1885 if (emptied) 1886 this.leaf = null; 1887 } 1888 1889 @safe pure nothrow: 1890 1891 private UIx firstIx(out bool emptied) const 1892 { 1893 switch (leaf.typeIx) with (Node.Ix) 1894 { 1895 case undefined: 1896 assert(false); 1897 case ix_OneLeafMax7: 1898 case ix_TwoLeaf3: 1899 case ix_TriLeaf2: 1900 case ix_HeptLeaf1: 1901 return UIx(0); // always first 1902 case ix_SparseLeaf1Ptr: 1903 const leaf_ = leaf.as!(SparseLeaf1!Value*); 1904 emptied = leaf_.empty; 1905 return UIx(0); // always first 1906 case ix_DenseLeaf1Ptr: 1907 const leaf_ = leaf.as!(DenseLeaf1!Value*); 1908 UIx nextIx; 1909 immutable bool hit = leaf_.tryFindSetBitIx(UIx(0), nextIx); 1910 assert(hit); 1911 return nextIx; 1912 default: assert(false, "Unsupported Node type"); 1913 } 1914 } 1915 1916 /** Get current subkey. */ 1917 Ix[] frontIxs() 1918 { 1919 assert(!empty); 1920 switch (leaf.typeIx) with (Node.Ix) 1921 { 1922 case undefined: 1923 assert(false); 1924 case ix_OneLeafMax7: 1925 assert(ix == 0); 1926 return leaf.as!(OneLeafMax7).key; 1927 case ix_TwoLeaf3: 1928 return leaf.as!(TwoLeaf3).keys[ix][]; 1929 case ix_TriLeaf2: 1930 return leaf.as!(TriLeaf2).keys[ix][]; 1931 case ix_HeptLeaf1: 1932 return [leaf.as!(HeptLeaf1).keys[ix]]; 1933 case ix_SparseLeaf1Ptr: 1934 return [leaf.as!(SparseLeaf1!Value*).ixs[ix]]; 1935 case ix_DenseLeaf1Ptr: 1936 return [Ix(ix)]; 1937 default: assert(false, "Unsupported Node type"); 1938 } 1939 } 1940 1941 /** Get first index in current subkey. */ 1942 UIx frontIx() 1943 { 1944 assert(!empty); 1945 switch (leaf.typeIx) with (Node.Ix) 1946 { 1947 case undefined: 1948 assert(false); 1949 case ix_OneLeafMax7: 1950 assert(ix == 0); 1951 return UIx(leaf.as!(OneLeafMax7).key[0]); 1952 case ix_TwoLeaf3: 1953 return UIx(leaf.as!(TwoLeaf3).keys[ix][0]); 1954 case ix_TriLeaf2: 1955 return UIx(leaf.as!(TriLeaf2).keys[ix][0]); 1956 case ix_HeptLeaf1: 1957 return UIx(leaf.as!(HeptLeaf1).keys[ix]); 1958 case ix_SparseLeaf1Ptr: 1959 return UIx(leaf.as!(SparseLeaf1!Value*).ixs[ix]); 1960 case ix_DenseLeaf1Ptr: 1961 return ix; 1962 default: assert(false, "Unsupported Node type"); 1963 } 1964 } 1965 1966 void appendFrontIxsToKey(ref Array!Ix key) const @nogc 1967 { 1968 assert(!empty); 1969 switch (leaf.typeIx) with (Node.Ix) 1970 { 1971 case undefined: 1972 assert(false); 1973 case ix_OneLeafMax7: 1974 assert(ix == 0); 1975 key ~= leaf.as!(OneLeafMax7).key[]; 1976 break; 1977 case ix_TwoLeaf3: 1978 key ~= leaf.as!(TwoLeaf3).keys[ix][]; 1979 break; 1980 case ix_TriLeaf2: 1981 key ~= leaf.as!(TriLeaf2).keys[ix][]; 1982 break; 1983 case ix_HeptLeaf1: 1984 key ~= Ix(leaf.as!(HeptLeaf1).keys[ix]); 1985 break; 1986 case ix_SparseLeaf1Ptr: 1987 key ~= Ix(leaf.as!(SparseLeaf1!Value*).ixs[ix]); 1988 break; 1989 case ix_DenseLeaf1Ptr: 1990 key ~= cast(Ix)ix; 1991 break; 1992 default: assert(false, "Unsupported Node type"); 1993 } 1994 } 1995 1996 pragma(inline, true) bool empty() const @nogc { return !leaf; } 1997 1998 pragma(inline, true) void makeEmpty() @nogc { leaf = null; } 1999 2000 /** Pop front element. */ 2001 void popFront() 2002 { 2003 assert(!empty); 2004 // TODO: move all calls to leaf-specific members popFront() 2005 switch (leaf.typeIx) with (Node.Ix) 2006 { 2007 case undefined: 2008 assert(false); 2009 case ix_OneLeafMax7: 2010 makeEmpty(); // only one element so forward automatically completes 2011 break; 2012 case ix_TwoLeaf3: 2013 auto leaf_ = leaf.as!(TwoLeaf3); 2014 if (ix + 1 == leaf_.keys.length) { makeEmpty(); } else { ++ix; } 2015 break; 2016 case ix_TriLeaf2: 2017 auto leaf_ = leaf.as!(TriLeaf2); 2018 if (ix + 1 == leaf_.keys.length) { makeEmpty(); } else { ++ix; } 2019 break; 2020 case ix_HeptLeaf1: 2021 auto leaf_ = leaf.as!(HeptLeaf1); 2022 if (ix + 1 == leaf_.keys.length) { makeEmpty(); } else { ++ix; } 2023 break; 2024 case ix_SparseLeaf1Ptr: 2025 auto leaf_ = leaf.as!(SparseLeaf1!Value*); 2026 if (ix + 1 == leaf_.length) { makeEmpty(); } else { ++ix; } 2027 break; 2028 case ix_DenseLeaf1Ptr: 2029 auto leaf_ = leaf.as!(DenseLeaf1!Value*); 2030 immutable bool emptied = !leaf_.tryFindNextSetBitIx(ix, ix); 2031 if (emptied) 2032 makeEmpty(); 2033 break; 2034 default: assert(false, "Unsupported Node type"); 2035 } 2036 } 2037 2038 static if (isValue) 2039 { 2040 auto ref value() inout 2041 { 2042 switch (leaf.typeIx) with (Node.Ix) 2043 { 2044 case ix_SparseLeaf1Ptr: return leaf.as!(SparseLeaf1!Value*).values[ix]; 2045 case ix_DenseLeaf1Ptr: return leaf.as!(DenseLeaf1!Value*).values[ix]; 2046 default: assert(false, "Incorrect Leaf-type"); 2047 } 2048 } 2049 } 2050 2051 private: 2052 Node leaf; // TODO: Use Leaf-WordVariant when it includes non-Value leaf types 2053 UIx ix; // `Node`-specific counter, typically either a sparse or dense index either a sub-branch or a `UKey`-ending `Ix` 2054 } 2055 2056 /** Ordered Set of BranchRanges. */ 2057 private static struct BranchRanges 2058 { 2059 static if (isValue) 2060 { 2061 bool appendFrontIxsToKey(ref Array!Ix key, ref Value value) const @trusted 2062 { 2063 foreach (const ref branchRange; _bRanges) 2064 { 2065 branchRange.appendFrontIxsToKey(key); 2066 if (branchRange.atLeaf1) 2067 { 2068 value = branchRange.leaf1Range.frontValue; 2069 return true; // key and value are both complete 2070 } 2071 } 2072 return false; // only key is partially complete 2073 } 2074 } 2075 else 2076 { 2077 bool appendFrontIxsToKey(ref Array!Ix key) const @trusted 2078 { 2079 foreach (const ref branchRange; _bRanges) 2080 { 2081 branchRange.appendFrontIxsToKey(key); 2082 if (branchRange.atLeaf1) 2083 return true; // key is complete 2084 } 2085 return false; // key is not complete 2086 } 2087 } 2088 size_t get1DepthAt(size_t depth) const @trusted 2089 { 2090 foreach (immutable i, ref branchRange; _bRanges[depth .. $]) 2091 { 2092 if (branchRange.atLeaf1) 2093 return depth + i; 2094 } 2095 return typeof(_branch1Depth).max; 2096 } 2097 2098 private void updateLeaf1AtDepth(size_t depth) @trusted 2099 { 2100 if (_bRanges[depth].atLeaf1) 2101 { 2102 if (_branch1Depth == typeof(_branch1Depth).max) // if not yet defined 2103 _branch1Depth = min(depth, _branch1Depth); 2104 } 2105 assert(_branch1Depth == get1DepthAt(0)); 2106 } 2107 2108 size_t getNext1DepthAt() const 2109 { 2110 pragma(inline, true); 2111 return get1DepthAt(_branch1Depth + 1); 2112 } 2113 2114 bool hasBranch1Front() const 2115 { 2116 pragma(inline, true); 2117 return _branch1Depth != typeof(_branch1Depth).max; 2118 } 2119 2120 void popBranch1Front() 2121 { 2122 pragma(inline, true); 2123 // _branchesKeyPrefix.popBackN(_bRanges.back); 2124 _bRanges[_branch1Depth].popFront(); 2125 } 2126 2127 bool emptyBranch1() const 2128 { 2129 pragma(inline, true); 2130 return _bRanges[_branch1Depth].empty; 2131 } 2132 2133 bool atLeaf1() const 2134 { 2135 pragma(inline, true); 2136 return _bRanges[_branch1Depth].atLeaf1; 2137 } 2138 2139 void shrinkTo(size_t newLength) 2140 { 2141 pragma(inline, true); 2142 // turn emptyness exception into an assert like ranges do 2143 // size_t suffixLength = 0; 2144 // foreach (const ref branchRange; _bRanges[$ - newLength .. $]) // TODO: reverse isearch 2145 // { 2146 // suffixLength += branchRange.prefixLength + 1; 2147 // } 2148 // _branchesKeyPrefix.popBackN(suffixLength); 2149 _bRanges.length = newLength; 2150 } 2151 2152 void push(ref BranchRange branchRange) 2153 { 2154 pragma(inline, true); 2155 // branchRange.appendFrontIxsToKey(_branchesKeyPrefix); 2156 _bRanges ~= branchRange; 2157 } 2158 2159 size_t branchCount() const @safe pure nothrow @nogc 2160 { 2161 pragma(inline, true); 2162 return _bRanges.length; 2163 } 2164 2165 void pop() 2166 { 2167 pragma(inline, true); 2168 // _branchesKeyPrefix.popBackN(_bRanges.back.prefixLength + 1); 2169 _bRanges.popBack(); 2170 } 2171 2172 ref BranchRange bottom() 2173 { 2174 pragma(inline, true); 2175 return _bRanges.back; 2176 } 2177 2178 private void verifyBranch1Depth() 2179 { 2180 pragma(inline, true); 2181 assert(_branch1Depth == get1DepthAt(0)); 2182 } 2183 2184 void resetBranch1Depth() 2185 { 2186 pragma(inline, true); 2187 _branch1Depth = typeof(_branch1Depth).max; 2188 } 2189 2190 @property typeof(this) save() 2191 { 2192 typeof(this) copy; 2193 copy._bRanges = this._bRanges.dup; // ...this is inferred as @safe 2194 copy._branch1Depth = this._branch1Depth; 2195 return copy; 2196 } 2197 2198 private: 2199 Array!BranchRange _bRanges; 2200 // Array!Ix _branchesKeyPrefix; 2201 2202 // index to first branchrange in `_bRanges` that is currently on a leaf1 2203 // or `typeof.max` if undefined 2204 size_t _branch1Depth = size_t.max; 2205 } 2206 2207 /** Forward (Left) Single-Directional Range over Tree. */ 2208 private static struct FrontRange 2209 { 2210 @safe pure nothrow @nogc: 2211 2212 this(Node root) 2213 { 2214 if (root) 2215 { 2216 diveAndVisitTreeUnder(root, 0); 2217 cacheFront(); 2218 } 2219 } 2220 2221 void popFront() 2222 { 2223 debug branchRanges.verifyBranch1Depth(); 2224 2225 if (branchRanges.hasBranch1Front) // if we're currently at leaf1 of branch 2226 popFrontInBranchLeaf1(); 2227 else // if bottommost leaf should be popped 2228 { 2229 leafNRange.popFront(); 2230 if (leafNRange.empty) 2231 postPopTreeUpdate(); 2232 } 2233 2234 if (!empty) 2235 cacheFront(); 2236 } 2237 2238 private void popFrontInBranchLeaf1() // TODO: move to member of BranchRanges 2239 { 2240 branchRanges.popBranch1Front(); 2241 if (branchRanges.emptyBranch1) 2242 { 2243 branchRanges.shrinkTo(branchRanges._branch1Depth); // remove `branchRange` and all others below 2244 branchRanges.resetBranch1Depth(); 2245 postPopTreeUpdate(); 2246 } 2247 else if (!branchRanges.atLeaf1) // if not at leaf 2248 branchRanges._branch1Depth = branchRanges.getNext1DepthAt; 2249 else // still at leaf 2250 { 2251 // nothing needed 2252 } 2253 } 2254 2255 private void cacheFront() 2256 { 2257 _cachedFrontKey.length = 0; // not clear() because we want to keep existing allocation 2258 2259 // branches 2260 static if (isValue) 2261 { 2262 if (branchRanges.appendFrontIxsToKey(_cachedFrontKey, 2263 _cachedFrontValue)) 2264 return; 2265 } 2266 else 2267 { 2268 if (branchRanges.appendFrontIxsToKey(_cachedFrontKey)) 2269 return; 2270 } 2271 2272 // leaf 2273 if (!leafNRange.empty) 2274 { 2275 leafNRange.appendFrontIxsToKey(_cachedFrontKey); 2276 static if (isValue) 2277 _cachedFrontValue = leafNRange.value; // last should be leaf containing value 2278 } 2279 } 2280 2281 // Go upwards and iterate forward in parents. 2282 private void postPopTreeUpdate() 2283 { 2284 while (branchRanges.branchCount) 2285 { 2286 branchRanges.bottom.popFront(); 2287 if (branchRanges.bottom.empty) 2288 branchRanges.pop(); 2289 else // if not empty 2290 { 2291 if (branchRanges.bottom.atLeaf1) 2292 branchRanges._branch1Depth = min(branchRanges.branchCount - 1, 2293 branchRanges._branch1Depth); 2294 break; // branchRanges.bottom is not empty so break 2295 } 2296 } 2297 if (branchRanges.branchCount && 2298 !branchRanges.bottom.subsEmpty) // if any sub nodes 2299 diveAndVisitTreeUnder(branchRanges.bottom.subFrontNode, 2300 branchRanges.branchCount); // visit them 2301 } 2302 2303 /** Find ranges of branches and leaf for all nodes under tree `root`. */ 2304 private void diveAndVisitTreeUnder(Node root, size_t depth) 2305 { 2306 Node curr = root; 2307 Node next; 2308 do 2309 { 2310 final switch (curr.typeIx) with (Node.Ix) 2311 { 2312 case undefined: 2313 assert(false); 2314 case ix_OneLeafMax7: 2315 case ix_TwoLeaf3: 2316 case ix_TriLeaf2: 2317 case ix_HeptLeaf1: 2318 case ix_SparseLeaf1Ptr: 2319 case ix_DenseLeaf1Ptr: 2320 assert(leafNRange.empty); 2321 leafNRange = LeafNRange(curr); 2322 next = null; // we're done diving 2323 break; 2324 case ix_SparseBranchPtr: 2325 auto curr_ = curr.as!(SparseBranch*); 2326 auto currRange = BranchRange(curr_); 2327 branchRanges.push(currRange); 2328 branchRanges.updateLeaf1AtDepth(depth); 2329 next = (curr_.subCount) ? curr_.firstSubNode : Node.init; 2330 break; 2331 case ix_DenseBranchPtr: 2332 auto curr_ = curr.as!(DenseBranch*); 2333 auto currRange = BranchRange(curr_); 2334 branchRanges.push(currRange); 2335 branchRanges.updateLeaf1AtDepth(depth); 2336 next = branchRanges.bottom.subsEmpty ? Node.init : branchRanges.bottom.subFrontNode; 2337 break; 2338 } 2339 curr = next; 2340 ++depth; 2341 } 2342 while (next); 2343 } 2344 2345 @property typeof(this) save() @trusted // TODO: remove @trusted 2346 { 2347 typeof(this) copy; 2348 copy.leafNRange = this.leafNRange; 2349 copy.branchRanges = this.branchRanges.save; 2350 copy._cachedFrontKey = this._cachedFrontKey.dup; 2351 static if (isValue) 2352 copy._cachedFrontValue = this._cachedFrontValue; 2353 return copy; 2354 } 2355 2356 /** Check if empty. */ 2357 bool empty() const 2358 { 2359 pragma(inline, true); 2360 return (leafNRange.empty && 2361 branchRanges.branchCount == 0); 2362 } 2363 2364 /** Get front key. */ 2365 auto frontKey() const @trusted 2366 { 2367 pragma(inline, true); 2368 return _cachedFrontKey[]; // TODO: replace @trusted with DIP-1000 scope 2369 } 2370 2371 static if (isValue) 2372 { 2373 /** Get front value. */ 2374 auto frontValue() const 2375 { 2376 pragma(inline, true); 2377 return _cachedFrontValue; 2378 } 2379 } 2380 2381 private: 2382 LeafNRange leafNRange; 2383 BranchRanges branchRanges; 2384 2385 // cache 2386 Array!Ix _cachedFrontKey; // copy of front key 2387 static if (isValue) 2388 Value _cachedFrontValue; // copy of front value 2389 } 2390 2391 /** Bi-Directional Range over Tree. 2392 Fulfills `isBidirectionalRange`. 2393 */ 2394 private static struct Range 2395 { 2396 import nxt.array_algorithm : startsWith; 2397 2398 pure nothrow @nogc: 2399 2400 this(Node root, UKey keyPrefix) 2401 { 2402 this._rawKeyPrefix = keyPrefix; 2403 2404 this._front = FrontRange(root); 2405 // TODO: this._back = FrontRange(root); 2406 2407 if (!empty && 2408 !_front.frontKey.startsWith(_rawKeyPrefix)) 2409 popFront(); 2410 } 2411 2412 @property typeof(this) save() 2413 { 2414 typeof(this) copy; 2415 copy._front = this._front.save; 2416 copy._back = this._back.save; 2417 copy._rawKeyPrefix = this._rawKeyPrefix; 2418 return copy; 2419 } 2420 2421 bool empty() const 2422 { 2423 pragma(inline, true); 2424 return _front.empty; // TODO: _front == _back; 2425 } 2426 2427 auto lowKey() const 2428 { 2429 pragma(inline, true); 2430 return _front.frontKey[_rawKeyPrefix.length .. $]; 2431 } 2432 auto highKey() const 2433 { 2434 pragma(inline, true); 2435 return _back.frontKey[_rawKeyPrefix.length .. $]; 2436 } 2437 2438 void popFront() 2439 { 2440 assert(!empty); 2441 do { _front.popFront(); } 2442 while (!empty && 2443 !_front.frontKey.startsWith(_rawKeyPrefix)); 2444 } 2445 2446 void popBack() 2447 { 2448 assert(!empty); 2449 do { _back.popFront(); } 2450 while (!empty && 2451 !_back.frontKey.startsWith(_rawKeyPrefix)); 2452 } 2453 2454 private: 2455 FrontRange _front; 2456 FrontRange _back; 2457 UKey _rawKeyPrefix; 2458 } 2459 2460 /** Sparse-Branch population histogram. */ 2461 alias SparseLeaf1_PopHist = size_t[radix]; 2462 2463 /** 256-Branch population histogram. */ 2464 alias DenseLeaf1_PopHist = size_t[radix]; 2465 2466 /** 4-Branch population histogram. 2467 Index maps to population with value range (0 .. 4). 2468 */ 2469 alias SparseBranch_PopHist = size_t[SparseBranch.maxCapacity + 1]; 2470 2471 /** Radix-Branch population histogram. 2472 Index maps to population with value range (0 .. `radix`). 2473 */ 2474 alias DenseBranch_PopHist = size_t[radix + 1]; 2475 2476 /** Tree Population and Memory-Usage Statistics. */ 2477 struct Stats 2478 { 2479 SparseLeaf1_PopHist popHist_SparseLeaf1; 2480 DenseLeaf1_PopHist popHist_DenseLeaf1; 2481 SparseBranch_PopHist popHist_SparseBranch; // packed branch population histogram 2482 DenseBranch_PopHist popHist_DenseBranch; // full branch population histogram 2483 2484 import nxt.typecons_ex : IndexedArray; 2485 2486 /** Maps `Node` type/index `Ix` to population. 2487 2488 Used to calculate complete tree memory usage, excluding allocator 2489 overhead typically via `malloc` and `calloc`. 2490 */ 2491 IndexedArray!(size_t, Node.Ix) popByNodeType; 2492 static assert(is(typeof(popByNodeType).Index == Node.Ix)); 2493 2494 IndexedArray!(size_t, Leaf1!Value.Ix) popByLeaf1Type; 2495 static assert(is(typeof(popByLeaf1Type).Index == Leaf1!Value.Ix)); 2496 2497 /** Number of heap-allocated `Node`s. Should always equal `heapAllocationBalance`. */ 2498 size_t heapNodeCount; 2499 2500 /** Number of heap-allocated `Leaf`s. Should always equal `heapLeafAllocationBalance`. */ 2501 size_t heapLeafCount; 2502 2503 size_t sparseBranchAllocatedSizeSum; 2504 2505 size_t sparseLeaf1AllocatedSizeSum; 2506 } 2507 2508 /** Destructively expand `curr` to a branch node able to store 2509 `capacityIncrement` more sub-nodes. 2510 */ 2511 Branch expand(SparseBranch* curr, size_t capacityIncrement = 1) @safe pure nothrow @nogc 2512 { 2513 typeof(return) next; 2514 assert(curr.subCount < radix); // we shouldn't expand beyond radix 2515 if (curr.empty) // if curr also empty length capacity must be zero 2516 next = constructVariableSizeNode!(typeof(*curr))(1, curr); // so allocate one 2517 else if (curr.subCount + capacityIncrement <= curr.maxCapacity) // if we can expand to curr 2518 { 2519 immutable requiredCapacity = curr.subCapacity + capacityIncrement; 2520 auto next_ = constructVariableSizeNode!(typeof(*curr))(requiredCapacity, curr); 2521 assert(next_.subCapacity >= requiredCapacity); 2522 next = next_; 2523 } 2524 else 2525 next = constructFixedSizeNode!(DenseBranch*)(curr); 2526 freeNode(curr); 2527 return next; 2528 } 2529 2530 /** Destructively expand `curr` to a leaf node able to store 2531 `capacityIncrement` more sub-nodes. 2532 */ 2533 Leaf1!Value expand(SparseLeaf1!Value* curr, size_t capacityIncrement = 1) @safe pure nothrow @nogc 2534 { 2535 typeof(return) next; 2536 assert(curr.length < radix); // we shouldn't expand beyond radix 2537 if (curr.empty) // if curr also empty length capacity must be zero 2538 next = constructVariableSizeNode!(typeof(*curr))(capacityIncrement); // make room for at least one 2539 else if (curr.length + capacityIncrement <= curr.maxCapacity) // if we can expand to curr 2540 { 2541 immutable requiredCapacity = curr.capacity + capacityIncrement; 2542 static if (isValue) 2543 auto next_ = constructVariableSizeNode!(typeof(*curr))(requiredCapacity, curr.ixs, curr.values); 2544 else 2545 auto next_ = constructVariableSizeNode!(typeof(*curr))(requiredCapacity, curr.ixs); 2546 assert(next_.capacity >= requiredCapacity); 2547 next = next_; 2548 } 2549 else 2550 { 2551 static if (isValue) 2552 next = constructFixedSizeNode!(DenseLeaf1!Value*)(curr.ixs, curr.values); // TODO: make use of sortedness of `curr.keys`? 2553 else 2554 next = constructFixedSizeNode!(DenseLeaf1!Value*)(curr.ixs); // TODO: make use of sortedness of `curr.keys`? 2555 } 2556 freeNode(curr); 2557 return next; 2558 } 2559 2560 /// ditto 2561 2562 Branch setSub(SparseBranch* curr, UIx subIx, Node subNode) @safe pure nothrow @nogc 2563 { 2564 // debug if (willFail) { dbg("WILL FAIL: subIx:", subIx); } 2565 size_t insertionIndex; 2566 ModStatus modStatus; 2567 curr = curr.reconstructingInsert(IxSub(subIx, subNode), modStatus, insertionIndex); 2568 if (modStatus == ModStatus.maxCapacityReached) // try insert and if it fails 2569 { 2570 // we need to expand because `curr` is full 2571 auto next = expand(curr); 2572 assert(getSub(next, subIx) == Node.init); // key slot should be unoccupied 2573 return setSub(next, subIx, subNode); 2574 } 2575 return Branch(curr); 2576 } 2577 2578 /// ditto 2579 Branch setSub(DenseBranch* curr, UIx subIx, Node subNode) @safe pure nothrow @nogc 2580 { 2581 pragma(inline, true); 2582 debug assert(!curr.subNodes[subIx], "sub-Node already set "); 2583 // "sub-Node at index " ~ subIx.to!string ~ 2584 // " already set to " ~ subNode.to!string); 2585 curr.subNodes[subIx] = subNode; 2586 return Branch(curr); 2587 } 2588 2589 /** Set sub-`Node` of branch `Node curr` at index `ix` to `subNode`. */ 2590 Branch setSub(Branch curr, UIx subIx, Node subNode) @safe pure nothrow @nogc 2591 { 2592 version(LDC) pragma(inline, true); 2593 final switch (curr.typeIx) with (Branch.Ix) 2594 { 2595 case ix_SparseBranchPtr: return setSub(curr.as!(SparseBranch*), subIx, subNode); 2596 case ix_DenseBranchPtr: return setSub(curr.as!(DenseBranch*), subIx, subNode); 2597 case undefined: 2598 assert(false); 2599 } 2600 } 2601 2602 /** Get sub-`Node` of branch `Node curr` at index `subIx`. */ 2603 Node getSub(Branch curr, UIx subIx) @safe pure nothrow @nogc 2604 { 2605 version(LDC) pragma(inline, true); 2606 final switch (curr.typeIx) with (Branch.Ix) 2607 { 2608 case ix_SparseBranchPtr: return getSub(curr.as!(SparseBranch*), subIx); 2609 case ix_DenseBranchPtr: return getSub(curr.as!(DenseBranch*), subIx); 2610 case undefined: 2611 assert(false); 2612 } 2613 } 2614 /// ditto 2615 Node getSub(SparseBranch* curr, UIx subIx) @safe pure nothrow @nogc 2616 { 2617 version(LDC) pragma(inline, true); 2618 if (auto subNode = curr.subNodeAt(subIx)) 2619 return subNode; 2620 return Node.init; 2621 } 2622 /// ditto 2623 Node getSub(DenseBranch* curr, UIx subIx) @safe pure nothrow @nogc 2624 { 2625 pragma(inline, true); 2626 auto sub = curr.subNodes[subIx]; 2627 debug curr.subNodes[subIx] = Node.init; // zero it to prevent multiple references 2628 return sub; 2629 } 2630 2631 /** Get leaves of node `curr`. */ 2632 inout(Leaf1!Value) getLeaf1(inout Branch curr) @safe pure nothrow @nogc 2633 { 2634 version(LDC) pragma(inline, true); 2635 final switch (curr.typeIx) with (Branch.Ix) 2636 { 2637 case ix_SparseBranchPtr: return curr.as!(SparseBranch*).leaf1; 2638 case ix_DenseBranchPtr: return curr.as!(DenseBranch*).leaf1; 2639 case undefined: 2640 assert(false); 2641 } 2642 } 2643 2644 /** Set direct leaves node of node `curr` to `leaf1`. */ 2645 void setLeaf1(Branch curr, Leaf1!Value leaf1) @safe pure nothrow @nogc 2646 { 2647 version(LDC) pragma(inline, true); 2648 final switch (curr.typeIx) with (Branch.Ix) 2649 { 2650 case ix_SparseBranchPtr: curr.as!(SparseBranch*).leaf1 = leaf1; break; 2651 case ix_DenseBranchPtr: curr.as!(DenseBranch*).leaf1 = leaf1; break; 2652 case undefined: 2653 assert(false); 2654 } 2655 } 2656 2657 /** Get prefix of node `curr`. */ 2658 auto getPrefix(inout Branch curr) @safe pure nothrow @nogc 2659 { 2660 version(LDC) pragma(inline, true); 2661 final switch (curr.typeIx) with (Branch.Ix) 2662 { 2663 case ix_SparseBranchPtr: return curr.as!(SparseBranch*).prefix[]; 2664 case ix_DenseBranchPtr: return curr.as!(DenseBranch*).prefix[]; 2665 case undefined: 2666 assert(false); 2667 } 2668 } 2669 2670 /** Set prefix of branch node `curr` to `prefix`. */ 2671 void setPrefix(Branch curr, const Ix[] prefix) @safe pure nothrow @nogc 2672 { 2673 pragma(inline, true); 2674 final switch (curr.typeIx) with (Branch.Ix) 2675 { 2676 case ix_SparseBranchPtr: curr.as!(SparseBranch*).prefix = typeof(curr.as!(SparseBranch*).prefix)(prefix); break; 2677 case ix_DenseBranchPtr: curr.as!(DenseBranch*).prefix = typeof(curr.as!(DenseBranch*).prefix)(prefix); break; 2678 case undefined: 2679 assert(false); 2680 } 2681 } 2682 2683 /** Pop `n` from prefix. */ 2684 void popFrontNPrefix(Branch curr, size_t n) @safe pure nothrow @nogc 2685 { 2686 version(LDC) pragma(inline, true); 2687 final switch (curr.typeIx) with (Branch.Ix) 2688 { 2689 case ix_SparseBranchPtr: curr.as!(SparseBranch*).prefix.popFrontN(n); break; 2690 case ix_DenseBranchPtr: curr.as!(DenseBranch*).prefix.popFrontN(n); break; 2691 case undefined: 2692 assert(false); 2693 } 2694 } 2695 2696 /** Get number of sub-nodes of node `curr`. */ 2697 SubCount getSubCount(inout Branch curr) @safe pure nothrow @nogc 2698 { 2699 version(LDC) pragma(inline, true); 2700 final switch (curr.typeIx) with (Branch.Ix) 2701 { 2702 case ix_SparseBranchPtr: return cast(typeof(return))curr.as!(SparseBranch*).subCount; 2703 case ix_DenseBranchPtr: return cast(typeof(return))curr.as!(DenseBranch*).subCount; 2704 case undefined: 2705 assert(false); 2706 } 2707 } 2708 2709 static if (isValue) 2710 { 2711 @safe pure nothrow @nogc: 2712 2713 /** Returns: `true` if `key` is stored under `curr`, `false` otherwise. */ 2714 inout(Value*) containsAt(inout Leaf1!Value curr, UKey key) 2715 { 2716 version(LDC) pragma(inline, true); 2717 // debug if (willFail) { dbg("curr:", curr); } 2718 // debug if (willFail) { dbg("key:", key); } 2719 switch (curr.typeIx) with (Leaf1!Value.Ix) 2720 { 2721 case undefined: 2722 return null; 2723 case ix_SparseLeaf1Ptr: return key.length == 1 ? curr.as!(SparseLeaf1!Value*).contains(UIx(key[0])) : null; 2724 case ix_DenseLeaf1Ptr: return key.length == 1 ? curr.as!(DenseLeaf1!Value*).contains(UIx(key[0])) : null; 2725 default: assert(false); 2726 } 2727 } 2728 2729 /// ditto 2730 inout(Value*) containsAt(inout Node curr, UKey key) /* TODO: make @safe */ @trusted 2731 { 2732 assert(key.length); 2733 // debug if (willFail) { dbg("key:", key); } 2734 import nxt.array_algorithm : skipOver; 2735 switch (curr.typeIx) with (Node.Ix) 2736 { 2737 case undefined: 2738 return null; 2739 case ix_SparseLeaf1Ptr: return key.length == 1 ? curr.as!(SparseLeaf1!Value*).contains(UIx(key[0])) : null; 2740 case ix_DenseLeaf1Ptr: return key.length == 1 ? curr.as!(DenseLeaf1!Value*).contains(UIx(key[0])) : null; 2741 case ix_SparseBranchPtr: 2742 auto curr_ = curr.as!(SparseBranch*); 2743 if (key.skipOver(curr_.prefix[])) 2744 return (key.length == 1 ? 2745 containsAt(curr_.leaf1, key) : // in leaf 2746 containsAt(curr_.subNodeAt(UIx(key[0])), key[1 .. $])); // recurse into branch tree 2747 return null; 2748 case ix_DenseBranchPtr: 2749 auto curr_ = curr.as!(DenseBranch*); 2750 if (key.skipOver(curr_.prefix[])) 2751 return (key.length == 1 ? 2752 containsAt(curr_.leaf1, key) : // in leaf 2753 containsAt(curr_.subNodes[UIx(key[0])], key[1 .. $])); // recurse into branch tree 2754 return null; 2755 default: assert(false); 2756 } 2757 } 2758 } 2759 else 2760 { 2761 @safe pure nothrow @nogc: 2762 const: 2763 2764 /** Returns: `true` if `key` is stored under `curr`, `false` otherwise. */ 2765 bool containsAt(Leaf1!Value curr, UKey key) 2766 { 2767 // debug if (willFail) { dbg("key:", key); } 2768 final switch (curr.typeIx) with (Leaf1!Value.Ix) 2769 { 2770 case undefined: 2771 return false; 2772 case ix_HeptLeaf1: return curr.as!(HeptLeaf1).contains(key); 2773 case ix_SparseLeaf1Ptr: return key.length == 1 && curr.as!(SparseLeaf1!Value*).contains(UIx(key[0])); 2774 case ix_DenseLeaf1Ptr: return key.length == 1 && curr.as!(DenseLeaf1!Value*).contains(UIx(key[0])); 2775 } 2776 } 2777 /// ditto 2778 bool containsAt(Node curr, UKey key) /* TODO: make @safe */ @trusted 2779 { 2780 assert(key.length); 2781 // debug if (willFail) { dbg("key:", key); } 2782 import nxt.array_algorithm : skipOver; 2783 final switch (curr.typeIx) with (Node.Ix) 2784 { 2785 case undefined: 2786 return false; 2787 case ix_OneLeafMax7: return curr.as!(OneLeafMax7).contains(key); 2788 case ix_TwoLeaf3: return curr.as!(TwoLeaf3).contains(key); 2789 case ix_TriLeaf2: return curr.as!(TriLeaf2).contains(key); 2790 case ix_HeptLeaf1: return curr.as!(HeptLeaf1).contains(key); 2791 case ix_SparseLeaf1Ptr: 2792 return key.length == 1 && curr.as!(SparseLeaf1!Value*).contains(UIx(key[0])); 2793 case ix_DenseLeaf1Ptr: 2794 return key.length == 1 && curr.as!(DenseLeaf1!Value*).contains(UIx(key[0])); 2795 case ix_SparseBranchPtr: 2796 auto curr_ = curr.as!(SparseBranch*); 2797 return (key.skipOver(curr_.prefix) && // matching prefix 2798 (key.length == 1 ? 2799 containsAt(curr_.leaf1, key) : // in leaf 2800 containsAt(curr_.subNodeAt(UIx(key[0])), key[1 .. $]))); // recurse into branch tree 2801 case ix_DenseBranchPtr: 2802 auto curr_ = curr.as!(DenseBranch*); 2803 return (key.skipOver(curr_.prefix) && // matching prefix 2804 (key.length == 1 ? 2805 containsAt(curr_.leaf1, key) : // in leaf 2806 containsAt(curr_.subNodes[UIx(key[0])], key[1 .. $]))); // recurse into branch tree 2807 } 2808 } 2809 } 2810 2811 inout(Node) prefixAt(inout Node curr, UKey keyPrefix, out UKey keyPrefixRest) /* TODO: make @safe */ @trusted pure nothrow @nogc 2812 { 2813 import nxt.array_algorithm : startsWith; 2814 final switch (curr.typeIx) with (Node.Ix) 2815 { 2816 case undefined: 2817 return typeof(return).init; // terminate recursion 2818 case ix_OneLeafMax7: 2819 if (curr.as!(OneLeafMax7).key[].startsWith(keyPrefix)) { goto processHit; } 2820 break; 2821 case ix_TwoLeaf3: 2822 if (curr.as!(TwoLeaf3).keyLength >= keyPrefix.length) { goto processHit; } 2823 break; 2824 case ix_TriLeaf2: 2825 if (curr.as!(TriLeaf2).keyLength >= keyPrefix.length) { goto processHit; } 2826 break; 2827 case ix_HeptLeaf1: 2828 if (curr.as!(HeptLeaf1).keyLength >= keyPrefix.length) { goto processHit; } 2829 break; 2830 case ix_SparseLeaf1Ptr: 2831 case ix_DenseLeaf1Ptr: 2832 if (keyPrefix.length <= 1) { goto processHit; } 2833 break; 2834 case ix_SparseBranchPtr: 2835 auto curr_ = curr.as!(SparseBranch*); 2836 if (keyPrefix.startsWith(curr_.prefix[])) 2837 { 2838 immutable currPrefixLength = curr_.prefix.length; 2839 if (keyPrefix.length == currPrefixLength || // if no more prefix 2840 (curr_.leaf1 && // both leaf1 2841 curr_.subCount)) // and sub-nodes 2842 goto processHit; 2843 else if (curr_.subCount == 0) // only leaf1 2844 return prefixAt(Node(curr_.leaf1), 2845 keyPrefix[currPrefixLength .. $], 2846 keyPrefixRest); 2847 else // only sub-node(s) 2848 return prefixAt(curr_.subNodeAt(UIx(keyPrefix[currPrefixLength])), 2849 keyPrefix[currPrefixLength + 1 .. $], 2850 keyPrefixRest); 2851 } 2852 break; 2853 case ix_DenseBranchPtr: 2854 auto curr_ = curr.as!(DenseBranch*); 2855 if (keyPrefix.startsWith(curr_.prefix[])) 2856 { 2857 immutable currPrefixLength = curr_.prefix.length; 2858 if (keyPrefix.length == currPrefixLength || // if no more prefix 2859 (curr_.leaf1 && // both leaf1 2860 curr_.subCount)) // and sub-nodes 2861 goto processHit; 2862 else if (curr_.subCount == 0) // only leaf1 2863 return prefixAt(Node(curr_.leaf1), 2864 keyPrefix[currPrefixLength .. $], 2865 keyPrefixRest); 2866 else // only sub-node(s) 2867 return prefixAt(curr_.subNodes[UIx(keyPrefix[currPrefixLength])], 2868 keyPrefix[currPrefixLength + 1 .. $], 2869 keyPrefixRest); 2870 } 2871 break; 2872 } 2873 return typeof(return).init; 2874 processHit: 2875 keyPrefixRest = keyPrefix; 2876 return curr; 2877 } 2878 2879 inout(Node) matchCommonPrefixAt(inout Node curr, UKey key, out UKey keyRest) /* TODO: make @safe */ @trusted pure nothrow @nogc 2880 { 2881 // dbg(curr.typeIx); 2882 import nxt.array_algorithm : startsWith; 2883 final switch (curr.typeIx) with (Node.Ix) 2884 { 2885 case undefined: 2886 return typeof(return).init; // terminate recursion 2887 case ix_OneLeafMax7: 2888 case ix_TwoLeaf3: 2889 case ix_TriLeaf2: 2890 case ix_HeptLeaf1: 2891 case ix_SparseLeaf1Ptr: 2892 case ix_DenseLeaf1Ptr: 2893 goto processHit; 2894 case ix_SparseBranchPtr: 2895 auto curr_ = curr.as!(SparseBranch*); 2896 // dbg(key); 2897 // dbg(curr_.prefix[]); 2898 if (key.startsWith(curr_.prefix[])) 2899 { 2900 immutable currPrefixLength = curr_.prefix.length; 2901 if (key.length == currPrefixLength || // if no more prefix 2902 (curr_.leaf1 && // both leaf1 2903 curr_.subCount)) // and sub-nodes 2904 goto processHit; 2905 else if (curr_.subCount == 0) // only leaf1 2906 return matchCommonPrefixAt(Node(curr_.leaf1), 2907 key[currPrefixLength .. $], 2908 keyRest); 2909 else if (curr_.subCount == 1) // only one sub node 2910 return matchCommonPrefixAt(curr_.subNodeAt(UIx(key[currPrefixLength])), 2911 key[currPrefixLength + 1 .. $], 2912 keyRest); 2913 else 2914 goto processHit; 2915 } 2916 break; 2917 case ix_DenseBranchPtr: 2918 auto curr_ = curr.as!(DenseBranch*); 2919 if (key.startsWith(curr_.prefix[])) 2920 { 2921 immutable currPrefixLength = curr_.prefix.length; 2922 if (key.length == currPrefixLength || // if no more prefix 2923 (curr_.leaf1 && // both leaf1 2924 curr_.subCount)) // and sub-nodes 2925 goto processHit; 2926 else if (curr_.subCount == 0) // only leaf1 2927 return matchCommonPrefixAt(Node(curr_.leaf1), 2928 key[currPrefixLength .. $], 2929 keyRest); 2930 else if (curr_.subCount == 1) // only one sub node 2931 return matchCommonPrefixAt(curr_.subNodes[UIx(key[currPrefixLength])], 2932 key[currPrefixLength + 1 .. $], 2933 keyRest); 2934 else 2935 goto processHit; 2936 } 2937 break; 2938 } 2939 return typeof(return).init; 2940 processHit: 2941 keyRest = key; 2942 return curr; 2943 } 2944 2945 size_t countHeapNodesAt(Node curr) @safe pure nothrow @nogc 2946 { 2947 size_t count = 0; 2948 final switch (curr.typeIx) with (Node.Ix) 2949 { 2950 case undefined: 2951 break; // propagate undefined 2952 case ix_OneLeafMax7: break; 2953 case ix_TwoLeaf3: break; 2954 case ix_TriLeaf2: break; 2955 case ix_HeptLeaf1: break; 2956 case ix_SparseLeaf1Ptr: 2957 case ix_DenseLeaf1Ptr: 2958 ++count; 2959 break; 2960 case ix_SparseBranchPtr: 2961 auto curr_ = curr.as!(SparseBranch*); 2962 ++count; 2963 foreach (subNode; curr_.subNodeSlots[0 .. curr_.subCount]) 2964 if (subNode) 2965 count += countHeapNodesAt(subNode); 2966 break; 2967 case ix_DenseBranchPtr: 2968 ++count; 2969 auto curr_ = curr.as!(DenseBranch*); 2970 foreach (subNode; curr_.subNodes) 2971 if (subNode) 2972 count += countHeapNodesAt(subNode); 2973 break; 2974 } 2975 return count; 2976 } 2977 2978 /** Returns a duplicate of this tree with root at `curr`. 2979 Shallowly duplicates the values in the map case. 2980 */ 2981 Leaf1!Value dupAt(Leaf1!Value curr) @safe pure nothrow @nogc 2982 { 2983 final switch (curr.typeIx) with (Leaf1!Value.Ix) 2984 { 2985 case undefined: // propagate undefined 2986 case ix_HeptLeaf1: return curr; // value semantics so just copy 2987 case ix_SparseLeaf1Ptr: return typeof(return)(curr.as!(SparseLeaf1!Value*).dup); 2988 case ix_DenseLeaf1Ptr: return typeof(return)(curr.as!(DenseLeaf1!Value*).dup); 2989 } 2990 } 2991 2992 /** Returns a duplicate of this tree with root at `curr`. 2993 Shallowly duplicates the values in the map case. 2994 */ 2995 Node dupAt(Node curr) @safe pure nothrow @nogc 2996 { 2997 final switch (curr.typeIx) with (Node.Ix) 2998 { 2999 case undefined: // propagate undefined 3000 case ix_OneLeafMax7: 3001 case ix_TwoLeaf3: 3002 case ix_TriLeaf2: 3003 case ix_HeptLeaf1: return curr; // value semantics so just copy 3004 case ix_SparseLeaf1Ptr: return typeof(return)(curr.as!(SparseLeaf1!Value*).dup); 3005 case ix_DenseLeaf1Ptr: return typeof(return)(curr.as!(DenseLeaf1!Value*).dup); 3006 case ix_SparseBranchPtr: return typeof(return)(curr.as!(SparseBranch*).dup); 3007 case ix_DenseBranchPtr: return typeof(return)(curr.as!(DenseBranch*).dup); 3008 } 3009 } 3010 3011 static if (!isValue) 3012 { 3013 Node insertNew(UKey key, out ElementRef elementRef) @safe pure nothrow @nogc 3014 { 3015 Node next; 3016 // debug if (willFail) { dbg("WILL FAIL: key:", key); } 3017 switch (key.length) 3018 { 3019 case 0: assert(false, "key must not be empty"); // return elementRef = Node(constructFixedSizeNode!(OneLeafMax7)()); 3020 case 1: next = Node(constructFixedSizeNode!(HeptLeaf1)(key[0])); break; 3021 case 2: next = Node(constructFixedSizeNode!(TriLeaf2)(key)); break; 3022 case 3: next = Node(constructFixedSizeNode!(TwoLeaf3)(key)); break; 3023 default: 3024 if (key.length <= OneLeafMax7.capacity) 3025 { 3026 next = Node(constructFixedSizeNode!(OneLeafMax7)(key)); 3027 break; 3028 } 3029 else // key doesn't fit in a `OneLeafMax7` 3030 return Node(insertNewBranch(key, elementRef)); 3031 } 3032 elementRef = ElementRef(next, 3033 UIx(0), // always first index 3034 ModStatus.added); 3035 return next; 3036 } 3037 } 3038 3039 Branch insertNewBranch(Elt!Value elt, out ElementRef elementRef) @safe pure nothrow @nogc 3040 { 3041 // debug if (willFail) { dbg("WILL FAIL: elt:", elt); } 3042 auto key = eltKey!Value(elt); 3043 assert(key.length); 3044 immutable prefixLength = min(key.length - 1, // all but last Ix of key 3045 DefaultBranch.prefixCapacity); // as much as possible of key in branch prefix 3046 auto prefix = key[0 .. prefixLength]; 3047 typeof(return) next = insertAtBelowPrefix(Branch(constructVariableSizeNode!(DefaultBranch)(1, prefix)), 3048 eltKeyDropExactly!Value(elt, prefixLength), elementRef); 3049 assert(elementRef); 3050 return next; 3051 } 3052 3053 /** Insert `key` into sub-tree under root `curr`. */ 3054 Node insertAt(Node curr, Elt!Value elt, out ElementRef elementRef) @safe pure nothrow @nogc 3055 { 3056 auto key = eltKey!Value(elt); 3057 // debug if (willFail) { dbg("WILL FAIL: key:", key, " curr:", curr); } 3058 assert(key.length); 3059 3060 if (!curr) // if no existing `Node` to insert at 3061 { 3062 static if (isValue) 3063 auto next = Node(insertNewBranch(elt, elementRef)); 3064 else 3065 auto next = insertNew(key, elementRef); 3066 assert(elementRef); // must be added to new Node 3067 return next; 3068 } 3069 else 3070 { 3071 final switch (curr.typeIx) with (Node.Ix) 3072 { 3073 case undefined: 3074 return typeof(return).init; 3075 case ix_OneLeafMax7: 3076 static if (isValue) 3077 assert(false); 3078 else 3079 return insertAt(curr.as!(OneLeafMax7), key, elementRef); 3080 case ix_TwoLeaf3: 3081 static if (isValue) 3082 assert(false); 3083 else 3084 return insertAt(curr.as!(TwoLeaf3), key, elementRef); 3085 case ix_TriLeaf2: 3086 static if (isValue) 3087 assert(false); 3088 else 3089 return insertAt(curr.as!(TriLeaf2), key, elementRef); 3090 case ix_HeptLeaf1: 3091 static if (isValue) 3092 assert(false); 3093 else 3094 return insertAt(curr.as!(HeptLeaf1), key, elementRef); 3095 case ix_SparseLeaf1Ptr: 3096 return insertAtLeaf(Leaf1!Value(curr.as!(SparseLeaf1!Value*)), elt, elementRef); // TODO: use toLeaf(curr) 3097 case ix_DenseLeaf1Ptr: 3098 return insertAtLeaf(Leaf1!Value(curr.as!(DenseLeaf1!Value*)), elt, elementRef); // TODO: use toLeaf(curr) 3099 case ix_SparseBranchPtr: 3100 // debug if (willFail) { dbg("WILL FAIL: currPrefix:", curr.as!(SparseBranch*).prefix); } 3101 return Node(insertAtAbovePrefix(Branch(curr.as!(SparseBranch*)), elt, elementRef)); 3102 case ix_DenseBranchPtr: 3103 return Node(insertAtAbovePrefix(Branch(curr.as!(DenseBranch*)), elt, elementRef)); 3104 } 3105 } 3106 } 3107 3108 /** Insert `key` into sub-tree under branch `curr` above prefix, that is 3109 the prefix of `curr` is stripped from `key` prior to insertion. */ 3110 Branch insertAtAbovePrefix(Branch curr, Elt!Value elt, out ElementRef elementRef) @safe pure nothrow @nogc 3111 { 3112 auto key = eltKey!Value(elt); 3113 assert(key.length); 3114 3115 import std.algorithm.searching : commonPrefix; 3116 auto currPrefix = getPrefix(curr); 3117 auto matchedKeyPrefix = commonPrefix(key, currPrefix); 3118 3119 // debug if (willFail) { dbg("WILL FAIL: key:", key, 3120 // " curr:", curr, 3121 // " currPrefix:", getPrefix(curr), 3122 // " matchedKeyPrefix:", matchedKeyPrefix); } 3123 3124 if (matchedKeyPrefix.length == 0) // no prefix key match 3125 { 3126 if (currPrefix.length == 0) // no current prefix 3127 { 3128 // debug if (willFail) { dbg("WILL FAIL"); } 3129 // NOTE: prefix:"", key:"cd" 3130 return insertAtBelowPrefix(curr, elt, elementRef); 3131 } 3132 else // if (currPrefix.length != 0) // non-empty current prefix 3133 { 3134 // NOTE: prefix:"ab", key:"cd" 3135 immutable currSubIx = UIx(currPrefix[0]); // subIx = 'a' 3136 if (currPrefix.length == 1 && getSubCount(curr) == 0) // if `curr`-prefix become empty and only leaf pointer 3137 { 3138 // debug if (willFail) { dbg("WILL FAIL"); } 3139 popFrontNPrefix(curr, 1); 3140 curr = setSub(curr, currSubIx, Node(getLeaf1(curr))); // move it to sub 3141 setLeaf1(curr, Leaf1!Value.init); 3142 3143 return insertAtBelowPrefix(curr, elt, elementRef); // directly call below because `curr`-prefix is now empty 3144 } 3145 else 3146 { 3147 // debug if (willFail) { dbg("WILL FAIL"); } 3148 popFrontNPrefix(curr, 1); 3149 auto next = constructVariableSizeNode!(DefaultBranch)(2, null, IxSub(currSubIx, Node(curr))); 3150 return insertAtAbovePrefix(Branch(next), elt, elementRef); 3151 } 3152 } 3153 } 3154 else if (matchedKeyPrefix.length < key.length) 3155 { 3156 if (matchedKeyPrefix.length == currPrefix.length) 3157 { 3158 // debug if (willFail) { dbg("WILL FAIL"); } 3159 // NOTE: key is an extension of prefix: prefix:"ab", key:"abcd" 3160 return insertAtBelowPrefix(curr, eltKeyDropExactly!Value(elt, currPrefix.length), elementRef); 3161 } 3162 else 3163 { 3164 // debug if (willFail) { dbg("WILL FAIL"); } 3165 // NOTE: prefix and key share beginning: prefix:"ab11", key:"ab22" 3166 immutable currSubIx = UIx(currPrefix[matchedKeyPrefix.length]); // need index first before we modify curr.prefix 3167 popFrontNPrefix(curr, matchedKeyPrefix.length + 1); 3168 auto next = constructVariableSizeNode!(DefaultBranch)(2, matchedKeyPrefix, IxSub(currSubIx, Node(curr))); 3169 return insertAtBelowPrefix(Branch(next), eltKeyDropExactly!Value(elt, matchedKeyPrefix.length), elementRef); 3170 } 3171 } 3172 else // if (matchedKeyPrefix.length == key.length) 3173 { 3174 // debug if (willFail) { dbg("WILL FAIL"); } 3175 assert(matchedKeyPrefix.length == key.length); 3176 if (matchedKeyPrefix.length < currPrefix.length) 3177 { 3178 // NOTE: prefix is an extension of key: prefix:"abcd", key:"ab" 3179 assert(matchedKeyPrefix.length); 3180 immutable nextPrefixLength = matchedKeyPrefix.length - 1; 3181 immutable currSubIx = UIx(currPrefix[nextPrefixLength]); // need index first 3182 popFrontNPrefix(curr, matchedKeyPrefix.length); // drop matchedKeyPrefix plus index to next super branch 3183 auto next = constructVariableSizeNode!(DefaultBranch)(2, matchedKeyPrefix[0 .. $ - 1], 3184 IxSub(currSubIx, Node(curr))); 3185 return insertAtBelowPrefix(Branch(next), eltKeyDropExactly!Value(elt, nextPrefixLength), elementRef); 3186 } 3187 else /* if (matchedKeyPrefix.length == currPrefix.length) and in turn 3188 if (key.length == currPrefix.length */ 3189 { 3190 // NOTE: prefix equals key: prefix:"abcd", key:"abcd" 3191 assert(matchedKeyPrefix.length); 3192 immutable currSubIx = UIx(currPrefix[matchedKeyPrefix.length - 1]); // need index first 3193 popFrontNPrefix(curr, matchedKeyPrefix.length); // drop matchedKeyPrefix plus index to next super branch 3194 auto next = constructVariableSizeNode!(DefaultBranch)(2, matchedKeyPrefix[0 .. $ - 1], 3195 IxSub(currSubIx, Node(curr))); 3196 static if (isValue) 3197 return insertAtLeaf1(Branch(next), UIx(key[$ - 1]), elt.value, elementRef); 3198 else 3199 return insertAtLeaf1(Branch(next), UIx(key[$ - 1]), elementRef); 3200 } 3201 } 3202 } 3203 3204 /** Like `insertAtAbovePrefix` but also asserts that `key` is 3205 currently not stored under `curr`. */ 3206 pragma(inline) Branch insertNewAtAbovePrefix(Branch curr, Elt!Value elt) @safe pure nothrow @nogc 3207 { 3208 pragma(inline, true); 3209 ElementRef elementRef; 3210 auto next = insertAtAbovePrefix(curr, elt, elementRef); 3211 assert(elementRef); 3212 return next; 3213 } 3214 3215 static if (isValue) 3216 { 3217 pragma(inline) Branch insertAtSubNode(Branch curr, UKey key, Value value, out ElementRef elementRef) @safe pure nothrow @nogc 3218 { 3219 // debug if (willFail) { dbg("WILL FAIL"); } 3220 immutable subIx = UIx(key[0]); 3221 return setSub(curr, subIx, 3222 insertAt(getSub(curr, subIx), // recurse 3223 Elt!Value(key[1 .. $], value), 3224 elementRef)); 3225 } 3226 } 3227 else 3228 { 3229 pragma(inline) Branch insertAtSubNode(Branch curr, UKey key, out ElementRef elementRef) @safe pure nothrow @nogc 3230 { 3231 // debug if (willFail) { dbg("WILL FAIL"); } 3232 immutable subIx = UIx(key[0]); 3233 return setSub(curr, subIx, 3234 insertAt(getSub(curr, subIx), // recurse 3235 key[1 .. $], 3236 elementRef)); 3237 } 3238 } 3239 3240 /** Insert `key` into sub-tree under branch `curr` below prefix, that is 3241 the prefix of `curr` is not stripped from `key` prior to 3242 insertion. */ 3243 Branch insertAtBelowPrefix(Branch curr, Elt!Value elt, out ElementRef elementRef) @safe pure nothrow @nogc 3244 { 3245 auto key = eltKey!Value(elt); 3246 assert(key.length); 3247 // debug if (willFail) { dbg("WILL FAIL: key:", key, 3248 // " curr:", curr, 3249 // " currPrefix:", getPrefix(curr), 3250 // " elementRef:", elementRef); } 3251 if (key.length == 1) 3252 { 3253 static if (isValue) 3254 return insertAtLeaf1(curr, UIx(key[0]), elt.value, elementRef); 3255 else 3256 return insertAtLeaf1(curr, UIx(key[0]), elementRef); 3257 } 3258 else // key.length >= 2 3259 { 3260 static if (isValue) 3261 return insertAtSubNode(curr, key, elt.value, elementRef); 3262 else 3263 return insertAtSubNode(curr, key, elementRef); 3264 } 3265 } 3266 3267 Branch insertNewAtBelowPrefix(Branch curr, Elt!Value elt) @safe pure nothrow @nogc 3268 { 3269 pragma(inline, true); 3270 ElementRef elementRef; 3271 auto next = insertAtBelowPrefix(curr, elt, elementRef); 3272 assert(elementRef); 3273 return next; 3274 } 3275 3276 Leaf1!Value insertIxAtLeaftoLeaf(Leaf1!Value curr, IxElt!Value elt, out ElementRef elementRef) @safe pure nothrow @nogc 3277 { 3278 auto key = eltIx!Value(elt); 3279 // debug if (willFail) { dbg("WILL FAIL: elt:", elt, 3280 // " curr:", curr, 3281 // " elementRef:", elementRef); } 3282 switch (curr.typeIx) with (Leaf1!Value.Ix) 3283 { 3284 case undefined: 3285 return typeof(return).init; 3286 case ix_HeptLeaf1: 3287 static if (isValue) 3288 assert(false); 3289 else 3290 return insertAt(curr.as!(HeptLeaf1), key, elementRef); // possibly expanded to other Leaf1!Value 3291 case ix_SparseLeaf1Ptr: 3292 SparseLeaf1!Value* curr_ = curr.as!(SparseLeaf1!Value*); 3293 size_t index; 3294 ModStatus modStatus; 3295 curr_ = curr_.reconstructingInsert(elt, modStatus, index); 3296 curr = Leaf1!Value(curr_); 3297 final switch (modStatus) 3298 { 3299 case ModStatus.unchanged: // already stored at `index` 3300 elementRef = ElementRef(Node(curr_), UIx(index), modStatus); 3301 return curr; 3302 case ModStatus.added: 3303 elementRef = ElementRef(Node(curr_), UIx(index), modStatus); 3304 return curr; 3305 case ModStatus.maxCapacityReached: 3306 auto next = insertIxAtLeaftoLeaf(expand(curr_, 1), // make room for one more 3307 elt, elementRef); 3308 assert(next.peek!(DenseLeaf1!Value*)); 3309 return next; 3310 case ModStatus.updated: 3311 elementRef = ElementRef(Node(curr_), UIx(index), modStatus); 3312 return curr; 3313 } 3314 case ix_DenseLeaf1Ptr: 3315 immutable modStatus = curr.as!(DenseLeaf1!Value*).insert(elt); 3316 static if (isValue) 3317 immutable ix = elt.ix; 3318 else 3319 immutable ix = elt; 3320 elementRef = ElementRef(Node(curr), ix, modStatus); 3321 break; 3322 default: 3323 assert(false, "Unsupported Leaf1!Value type " // ~ curr.typeIx.to!string 3324 ); 3325 } 3326 return curr; 3327 } 3328 3329 static if (isValue) 3330 { 3331 Branch insertAtLeaf1(Branch curr, UIx key, Value value, out ElementRef elementRef) @safe pure nothrow @nogc 3332 { 3333 // debug if (willFail) { dbg("WILL FAIL: key:", key, 3334 // " value:", value, 3335 // " curr:", curr, 3336 // " currPrefix:", getPrefix(curr), 3337 // " elementRef:", elementRef); } 3338 if (auto leaf = getLeaf1(curr)) 3339 setLeaf1(curr, insertIxAtLeaftoLeaf(leaf, IxElt!Value(key, value), elementRef)); 3340 else 3341 { 3342 Ix[1] ixs = [Ix(key)]; // TODO: scope 3343 Value[1] values = [value]; // TODO: scope 3344 auto leaf_ = constructVariableSizeNode!(SparseLeaf1!Value)(1, ixs, values); // needed for values 3345 elementRef = ElementRef(Node(leaf_), UIx(0), ModStatus.added); 3346 setLeaf1(curr, Leaf1!Value(leaf_)); 3347 } 3348 return curr; 3349 } 3350 } 3351 else 3352 { 3353 Branch insertAtLeaf1(Branch curr, UIx key, out ElementRef elementRef) @safe pure nothrow @nogc 3354 { 3355 // debug if (willFail) { dbg("WILL FAIL: key:", key, 3356 // " curr:", curr, 3357 // " currPrefix:", getPrefix(curr), 3358 // " elementRef:", elementRef); } 3359 if (auto leaf = getLeaf1(curr)) 3360 setLeaf1(curr, insertIxAtLeaftoLeaf(leaf, key, elementRef)); 3361 else 3362 { 3363 auto leaf_ = constructFixedSizeNode!(HeptLeaf1)(key); // can pack more efficiently when no value 3364 elementRef = ElementRef(Node(leaf_), UIx(0), ModStatus.added); 3365 setLeaf1(curr, Leaf1!Value(leaf_)); 3366 } 3367 return curr; 3368 } 3369 } 3370 3371 Node insertAtLeaf(Leaf1!Value curr, Elt!Value elt, out ElementRef elementRef) @safe pure nothrow @nogc 3372 { 3373 // debug if (willFail) { dbg("WILL FAIL: elt:", elt); } 3374 auto key = eltKey!Value(elt); 3375 assert(key.length); 3376 if (key.length == 1) 3377 { 3378 static if (isValue) 3379 return Node(insertIxAtLeaftoLeaf(curr, IxElt!Value(UIx(key[0]), elt.value), elementRef)); 3380 else 3381 return Node(insertIxAtLeaftoLeaf(curr, UIx(key[0]), elementRef)); 3382 } 3383 else 3384 { 3385 assert(key.length >= 2); 3386 immutable prefixLength = key.length - 2; // >= 0 3387 const nextPrefix = key[0 .. prefixLength]; 3388 auto next = constructVariableSizeNode!(DefaultBranch)(1, nextPrefix, curr); // one sub-node and one leaf 3389 return Node(insertAtBelowPrefix(Branch(next), eltKeyDropExactly!Value(elt, prefixLength), elementRef)); 3390 } 3391 } 3392 3393 static if (!isValue) 3394 { 3395 Node insertAt(OneLeafMax7 curr, UKey key, out ElementRef elementRef) @safe pure nothrow @nogc 3396 { 3397 assert(curr.key.length); 3398 // debug if (willFail) { dbg("WILL FAIL: key:", key, " curr.key:", curr.key); } 3399 3400 import std.algorithm.searching : commonPrefix; 3401 auto matchedKeyPrefix = commonPrefix(key, curr.key); 3402 if (curr.key.length == key.length) 3403 { 3404 if (matchedKeyPrefix.length == key.length) // curr.key, key and matchedKeyPrefix all equal 3405 return Node(curr); // already stored in `curr` 3406 else if (matchedKeyPrefix.length + 1 == key.length) // key and curr.key are both matchedKeyPrefix plus one extra 3407 { 3408 // TODO: functionize: 3409 Node next; 3410 switch (matchedKeyPrefix.length) 3411 { 3412 case 0: 3413 next = constructFixedSizeNode!(HeptLeaf1)(curr.key[0], key[0]); 3414 elementRef = ElementRef(next, UIx(1), ModStatus.added); 3415 break; 3416 case 1: 3417 next = constructFixedSizeNode!(TriLeaf2)(curr.key, key); 3418 elementRef = ElementRef(next, UIx(1), ModStatus.added); 3419 break; 3420 case 2: 3421 next = constructFixedSizeNode!(TwoLeaf3)(curr.key, key); 3422 elementRef = ElementRef(next, UIx(1), ModStatus.added); 3423 break; 3424 default: 3425 const nextPrefix = matchedKeyPrefix[0 .. min(matchedKeyPrefix.length, 3426 DefaultBranch.prefixCapacity)]; // limit prefix branch capacity 3427 Branch nextBranch = constructVariableSizeNode!(DefaultBranch)(1 + 1, // `curr` and `key` 3428 nextPrefix); 3429 nextBranch = insertNewAtBelowPrefix(nextBranch, curr.key[nextPrefix.length .. $]); 3430 nextBranch = insertAtBelowPrefix(nextBranch, key[nextPrefix.length .. $], elementRef); 3431 assert(elementRef); 3432 next = Node(nextBranch); 3433 break; 3434 } 3435 freeNode(curr); 3436 return next; 3437 } 3438 } 3439 3440 return Node(insertAtAbovePrefix(expand(curr), key, elementRef)); 3441 } 3442 3443 Node insertAt(TwoLeaf3 curr, UKey key, out ElementRef elementRef) @safe pure nothrow @nogc 3444 { 3445 if (curr.keyLength == key.length) 3446 { 3447 if (curr.contains(key)) 3448 return Node(curr); 3449 if (!curr.keys.full) 3450 { 3451 assert(curr.keys.length == 1); 3452 elementRef = ElementRef(Node(curr), UIx(curr.keys.length), ModStatus.added); 3453 curr.keys.pushBack(key); 3454 return Node(curr); 3455 } 3456 } 3457 return Node(insertAtAbovePrefix(expand(curr), key, elementRef)); // NOTE stay at same (depth) 3458 } 3459 3460 Node insertAt(TriLeaf2 curr, UKey key, out ElementRef elementRef) @safe pure nothrow @nogc 3461 { 3462 if (curr.keyLength == key.length) 3463 { 3464 if (curr.contains(key)) 3465 return Node(curr); 3466 if (!curr.keys.full) 3467 { 3468 elementRef = ElementRef(Node(curr), UIx(curr.keys.length), ModStatus.added); 3469 curr.keys.pushBack(key); 3470 return Node(curr); 3471 } 3472 } 3473 return Node(insertAtAbovePrefix(expand(curr), key, elementRef)); // NOTE stay at same (depth) 3474 } 3475 3476 Leaf1!Value insertAt(HeptLeaf1 curr, UIx key, out ElementRef elementRef) @safe pure nothrow @nogc 3477 { 3478 if (curr.contains(key)) 3479 return Leaf1!Value(curr); 3480 if (!curr.keys.full) 3481 { 3482 elementRef = ElementRef(Node(curr), UIx(curr.keys.back), ModStatus.added); 3483 curr.keys.pushBack(cast(Ix)key); 3484 return Leaf1!Value(curr); 3485 } 3486 else // curr is full 3487 { 3488 assert(curr.keys.length == curr.capacity); 3489 3490 // pack `curr.keys` plus `key` into `nextKeys` 3491 Ix[curr.capacity + 1] nextKeys; 3492 nextKeys[0 .. curr.capacity] = curr.keys; 3493 nextKeys[curr.capacity] = cast(Ix)key; 3494 3495 import std.algorithm.sorting : sort; 3496 sort(nextKeys[]); // TODO: move this sorting elsewhere 3497 3498 auto next = constructVariableSizeNode!(SparseLeaf1!Value)(nextKeys.length, nextKeys[]); 3499 elementRef = ElementRef(Node(next), UIx(curr.capacity), ModStatus.added); 3500 3501 freeNode(curr); 3502 return Leaf1!Value(next); 3503 } 3504 } 3505 3506 Node insertAt(HeptLeaf1 curr, UKey key, out ElementRef elementRef) 3507 @safe pure nothrow @nogc 3508 { 3509 if (curr.keyLength == key.length) 3510 return Node(insertAt(curr, UIx(key[0]), elementRef)); // use `Ix key`-overload 3511 return insertAt(Node(constructVariableSizeNode!(DefaultBranch)(1, Leaf1!Value(curr))), // current `key` 3512 key, elementRef); // NOTE stay at same (depth) 3513 } 3514 3515 /** Split `curr` using `prefix`. */ 3516 Node split(OneLeafMax7 curr, UKey prefix, UKey key) // TODO: key here is a bit malplaced 3517 @safe pure nothrow @nogc 3518 { 3519 assert(key.length); 3520 3521 if (curr.key.length == key.length) // balanced tree possible 3522 { 3523 switch (curr.key.length) 3524 { 3525 case 1: 3526 if (prefix.length == 0) 3527 { 3528 freeNode(curr); 3529 return Node(constructFixedSizeNode!(HeptLeaf1)(curr.key)); // TODO: removing parameter has no effect. why? 3530 } 3531 break; 3532 case 2: 3533 freeNode(curr); 3534 return Node(constructFixedSizeNode!(TriLeaf2)(curr.key)); 3535 case 3: 3536 freeNode(curr); 3537 return Node(constructFixedSizeNode!(TwoLeaf3)(curr.key)); 3538 default: 3539 break; 3540 } 3541 } 3542 3543 // default case 3544 Branch next = constructVariableSizeNode!(DefaultBranch)(1 + 1, prefix); // current plus one more 3545 next = insertNewAtBelowPrefix(next, curr.key[prefix.length .. $]); 3546 freeNode(curr); // remove old current 3547 3548 return Node(next); 3549 } 3550 3551 /** Destructively expand `curr` to make room for `capacityIncrement` more keys and return it. */ 3552 Branch expand(OneLeafMax7 curr, size_t capacityIncrement = 1) 3553 @safe pure nothrow @nogc 3554 { 3555 assert(curr.key.length >= 2); 3556 typeof(return) next; 3557 3558 if (curr.key.length <= DefaultBranch.prefixCapacity + 1) // if `key` fits in `prefix` of `DefaultBranch` 3559 { 3560 next = constructVariableSizeNode!(DefaultBranch)(1 + capacityIncrement, curr.key[0 .. $ - 1], // all but last 3561 Leaf1!Value(constructFixedSizeNode!(HeptLeaf1)(curr.key.back))); // last as a leaf 3562 } 3563 else // curr.key.length > DefaultBranch.prefixCapacity + 1 3564 { 3565 next = constructVariableSizeNode!(DefaultBranch)(1 + capacityIncrement, curr.key[0 .. DefaultBranch.prefixCapacity]); 3566 next = insertNewAtBelowPrefix(next, curr.key[DefaultBranch.prefixCapacity .. $]); 3567 } 3568 3569 freeNode(curr); 3570 return next; 3571 } 3572 3573 /** Destructively expand `curr` to make room for `capacityIncrement` more keys and return it. */ 3574 Branch expand(TwoLeaf3 curr, size_t capacityIncrement = 1) 3575 @safe pure nothrow @nogc 3576 { 3577 typeof(return) next; 3578 if (curr.keys.length == 1) // only one key 3579 { 3580 next = constructVariableSizeNode!(DefaultBranch)(1 + capacityIncrement); 3581 next = insertNewAtAbovePrefix(next, // current keys plus one more 3582 curr.keys.at!0); 3583 } 3584 else 3585 { 3586 next = constructVariableSizeNode!(DefaultBranch)(curr.keys.length + capacityIncrement, curr.prefix); 3587 // TODO: functionize and optimize to insertNewAtAbovePrefix(next, curr.keys) 3588 foreach (key; curr.keys) 3589 next = insertNewAtBelowPrefix(next, key[curr.prefix.length .. $]); 3590 } 3591 freeNode(curr); 3592 return next; 3593 } 3594 3595 /** Destructively expand `curr` to make room for `capacityIncrement` more keys and return it. */ 3596 Branch expand(TriLeaf2 curr, size_t capacityIncrement = 1) 3597 @safe pure nothrow @nogc 3598 { 3599 typeof(return) next; 3600 if (curr.keys.length == 1) // only one key 3601 { 3602 next = constructVariableSizeNode!(DefaultBranch)(1 + capacityIncrement); // current keys plus one more 3603 next = insertNewAtAbovePrefix(next, curr.keys.at!0); 3604 } 3605 else 3606 { 3607 next = constructVariableSizeNode!(DefaultBranch)(curr.keys.length + capacityIncrement, curr.prefix); 3608 // TODO: functionize and optimize to insertNewAtAbovePrefix(next, curr.keys) 3609 foreach (key; curr.keys) 3610 next = insertNewAtBelowPrefix(next, key[curr.prefix.length .. $]); 3611 } 3612 freeNode(curr); 3613 return next; 3614 } 3615 3616 /** Destructively expand `curr` making room for `nextKey` and return it. */ 3617 Node expand(HeptLeaf1 curr, size_t capacityIncrement = 1) 3618 { 3619 auto next = constructVariableSizeNode!(SparseLeaf1!Value)(curr.keys.length + capacityIncrement, curr.keys); 3620 freeNode(curr); 3621 return Node(next); 3622 } 3623 } 3624 3625 @safe pure nothrow @nogc 3626 { 3627 pragma(inline, true) void release(SparseLeaf1!Value* curr) { freeNode(curr); } 3628 pragma(inline, true) void release(DenseLeaf1!Value* curr) { freeNode(curr); } 3629 3630 void release(SparseBranch* curr) 3631 { 3632 foreach (immutable sub; curr.subNodes[0 .. curr.subCount]) 3633 release(sub); // recurse branch 3634 if (curr.leaf1) 3635 release(curr.leaf1); // recurse leaf 3636 freeNode(curr); 3637 } 3638 3639 void release(DenseBranch* curr) 3640 { 3641 foreach (immutable sub; curr.subNodes[].filter!(sub => sub)) // TODO: use static foreach 3642 release(sub); // recurse branch 3643 if (curr.leaf1) 3644 release(curr.leaf1); // recurse leaf 3645 freeNode(curr); 3646 } 3647 3648 pragma(inline, true) void release(OneLeafMax7 curr) { freeNode(curr); } 3649 pragma(inline, true) void release(TwoLeaf3 curr) { freeNode(curr); } 3650 pragma(inline, true) void release(TriLeaf2 curr) { freeNode(curr); } 3651 pragma(inline, true) void release(HeptLeaf1 curr) { freeNode(curr); } 3652 3653 /** Release `Leaf1!Value curr`. */ 3654 void release(Leaf1!Value curr) 3655 { 3656 final switch (curr.typeIx) with (Leaf1!Value.Ix) 3657 { 3658 case undefined: 3659 break; // ignored 3660 case ix_HeptLeaf1: return release(curr.as!(HeptLeaf1)); 3661 case ix_SparseLeaf1Ptr: return release(curr.as!(SparseLeaf1!Value*)); 3662 case ix_DenseLeaf1Ptr: return release(curr.as!(DenseLeaf1!Value*)); 3663 } 3664 } 3665 3666 /** Release `Node curr`. */ 3667 void release(Node curr) 3668 { 3669 final switch (curr.typeIx) with (Node.Ix) 3670 { 3671 case undefined: 3672 break; // ignored 3673 case ix_OneLeafMax7: return release(curr.as!(OneLeafMax7)); 3674 case ix_TwoLeaf3: return release(curr.as!(TwoLeaf3)); 3675 case ix_TriLeaf2: return release(curr.as!(TriLeaf2)); 3676 case ix_HeptLeaf1: return release(curr.as!(HeptLeaf1)); 3677 case ix_SparseLeaf1Ptr: return release(curr.as!(SparseLeaf1!Value*)); 3678 case ix_DenseLeaf1Ptr: return release(curr.as!(DenseLeaf1!Value*)); 3679 case ix_SparseBranchPtr: return release(curr.as!(SparseBranch*)); 3680 case ix_DenseBranchPtr: return release(curr.as!(DenseBranch*)); 3681 } 3682 } 3683 3684 bool isHeapAllocatedNode(const Node curr) 3685 { 3686 final switch (curr.typeIx) with (Node.Ix) 3687 { 3688 case undefined: 3689 return false; 3690 case ix_OneLeafMax7: return false; 3691 case ix_TwoLeaf3: return false; 3692 case ix_TriLeaf2: return false; 3693 case ix_HeptLeaf1: return false; 3694 case ix_SparseLeaf1Ptr: return true; 3695 case ix_DenseLeaf1Ptr: return true; 3696 case ix_SparseBranchPtr: return true; 3697 case ix_DenseBranchPtr: return true; 3698 } 3699 } 3700 } 3701 3702 void printAt(Node curr, size_t depth, uint subIx = uint.max) @safe 3703 { 3704 import std.range : repeat; 3705 import std.stdio : write, writeln; 3706 import std..string : format; 3707 3708 if (!curr) 3709 return; 3710 3711 foreach (immutable i; 0 .. depth) 3712 write('-'); // prefix 3713 3714 if (subIx != uint.max) 3715 write(format("%.2X ", subIx)); 3716 3717 final switch (curr.typeIx) with (Node.Ix) 3718 { 3719 case undefined: 3720 assert(false, "Trying to print Node.undefined"); 3721 case ix_OneLeafMax7: 3722 auto curr_ = curr.as!(OneLeafMax7); 3723 import std.conv : to; 3724 writeln(typeof(curr_).stringof, " #", curr_.key.length, ": ", curr_.to!string); 3725 break; 3726 case ix_TwoLeaf3: 3727 auto curr_ = curr.as!(TwoLeaf3); 3728 writeln(typeof(curr_).stringof, " #", curr_.keys.length, ": ", curr_.keys); 3729 break; 3730 case ix_TriLeaf2: 3731 auto curr_ = curr.as!(TriLeaf2); 3732 writeln(typeof(curr_).stringof, " #", curr_.keys.length, ": ", curr_.keys); 3733 break; 3734 case ix_HeptLeaf1: 3735 auto curr_ = curr.as!(HeptLeaf1); 3736 writeln(typeof(curr_).stringof, " #", curr_.keys.length, ": ", curr_.keys); 3737 break; 3738 case ix_SparseLeaf1Ptr: 3739 auto curr_ = curr.as!(SparseLeaf1!Value*); 3740 write(typeof(*curr_).stringof, " #", curr_.length, "/", curr_.capacity, " @", curr_); 3741 write(": "); 3742 bool other = false; 3743 foreach (immutable i, immutable ix; curr_.ixs) 3744 { 3745 string s; 3746 if (other) 3747 s ~= keySeparator; 3748 else 3749 other = true; 3750 import std..string : format; 3751 s ~= format("%.2X", ix); 3752 write(s); 3753 static if (isValue) 3754 write("=>", curr_.values[i]); 3755 } 3756 writeln(); 3757 break; 3758 case ix_DenseLeaf1Ptr: 3759 auto curr_ = curr.as!(DenseLeaf1!Value*); 3760 write(typeof(*curr_).stringof, " #", curr_.count, " @", curr_); 3761 write(": "); 3762 3763 // keys 3764 size_t ix = 0; 3765 bool other = false; 3766 if (curr_._ixBits.allOne) 3767 write("ALL"); 3768 else 3769 { 3770 foreach (immutable keyBit; curr_._ixBits[]) 3771 { 3772 string s; 3773 if (keyBit) 3774 { 3775 if (other) 3776 s ~= keySeparator; 3777 else 3778 other = true; 3779 import std..string : format; 3780 s ~= format("%.2X", ix); 3781 } 3782 write(s); 3783 static if (isValue) 3784 write("=>", curr_.values[ix]); 3785 ++ix; 3786 } 3787 } 3788 3789 writeln(); 3790 break; 3791 case ix_SparseBranchPtr: 3792 auto curr_ = curr.as!(SparseBranch*); 3793 write(typeof(*curr_).stringof, " #", curr_.subCount, "/", curr_.subCapacity, " @", curr_); 3794 if (!curr_.prefix.empty) 3795 write(" prefix=", curr_.prefix.toString('_')); 3796 writeln(":"); 3797 if (curr_.leaf1) 3798 printAt(Node(curr_.leaf1), depth + 1); 3799 foreach (immutable i, immutable subNode; curr_.subNodes) 3800 printAt(subNode, depth + 1, cast(uint)curr_.subIxs[i]); 3801 break; 3802 case ix_DenseBranchPtr: 3803 auto curr_ = curr.as!(DenseBranch*); 3804 write(typeof(*curr_).stringof, " #", curr_.subCount, "/", radix, " @", curr_); 3805 if (!curr_.prefix.empty) 3806 write(" prefix=", curr_.prefix.toString('_')); 3807 writeln(":"); 3808 if (curr_.leaf1) 3809 printAt(Node(curr_.leaf1), depth + 1); 3810 foreach (immutable i, immutable subNode; curr_.subNodes) 3811 printAt(subNode, depth + 1, cast(uint)i); 3812 3813 break; 3814 } 3815 } 3816 3817 struct RawRadixTree 3818 { 3819 alias NodeType = Node; 3820 alias BranchType = Branch; 3821 alias DefaultBranchType = DefaultBranch; 3822 alias ValueType = Value; 3823 alias RangeType = Range; 3824 alias StatsType = Stats; 3825 alias SparseBranchType = SparseBranch; 3826 alias DenseBranchType = DenseBranch; 3827 alias ElementRefType = ElementRef; 3828 3829 import core.lifetime : emplace; 3830 3831 /** Is `true` if this tree stores values of type `Value` along with keys. In 3832 other words: `this` is a $(I map) rather than a $(I set). 3833 */ 3834 alias hasValue = isValue; 3835 3836 Range opSlice() pure nothrow // TODO: DIP-1000 scope 3837 { 3838 pragma(inline, true); 3839 return Range(_root, []); 3840 } 3841 3842 /** Returns a duplicate of this tree if present. 3843 Shallowly duplicates the values in the map case. 3844 */ 3845 typeof(this) dup() @trusted 3846 { 3847 pragma(inline, true); 3848 return typeof(return)(dupAt(_root), length); 3849 } 3850 3851 Stats usageHistograms() const 3852 { 3853 if (!_root) 3854 return typeof(return).init; 3855 typeof(return) stats; 3856 _root.calculate!(Value)(stats); 3857 return stats; 3858 } 3859 3860 @disable this(this); 3861 3862 ~this() @nogc 3863 { 3864 pragma(inline, true); 3865 release(_root); 3866 debug _root = Node.init; 3867 } 3868 3869 /** Removes all contents (elements). */ 3870 void clear() @nogc 3871 { 3872 pragma(inline, true); 3873 release(_root); 3874 _root = null; 3875 _length = 0; 3876 } 3877 3878 @safe pure nothrow @nogc 3879 { 3880 /** Returns: `true` if `key` is stored, `false` otherwise. */ 3881 inout(Node) prefix(UKey keyPrefix, out UKey keyPrefixRest) inout 3882 { 3883 pragma(inline, true); 3884 return prefixAt(_root, keyPrefix, keyPrefixRest); 3885 } 3886 3887 3888 /** Lookup deepest node having whose key starts with `key`. */ 3889 inout(Node) matchCommonPrefix(UKey key, out UKey keyRest) inout 3890 { 3891 pragma(inline, true); 3892 return matchCommonPrefixAt(_root, key, keyRest); 3893 } 3894 3895 static if (isValue) 3896 { 3897 /** Returns: `true` if `key` is stored, `false` otherwise. */ 3898 inout(Value*) contains(UKey key) inout 3899 { 3900 pragma(inline, true); 3901 return containsAt(_root, key); 3902 } 3903 } 3904 else 3905 { 3906 /** Returns: `true` if `key` is stored, `false` otherwise. */ 3907 bool contains(UKey key) const 3908 { 3909 pragma(inline, true); 3910 return containsAt(_root, key); 3911 } 3912 } 3913 3914 /** Insert `key` into `this` tree. */ 3915 static if (isValue) 3916 { 3917 Node insert(UKey key, in Value value, out ElementRef elementRef) 3918 { 3919 version(LDC) pragma(inline, true); 3920 return _root = insertAt(_root, Elt!Value(key, value), elementRef); 3921 } 3922 } 3923 else 3924 { 3925 Node insert(UKey key, out ElementRef elementRef) 3926 { 3927 version(LDC) pragma(inline, true); 3928 return _root = insertAt(_root, key, elementRef); 3929 } 3930 } 3931 3932 size_t countHeapNodes() 3933 { 3934 pragma(inline, true); 3935 return countHeapNodesAt(_root); 3936 } 3937 3938 /** Returns: `true` iff tree is empty (no elements stored). */ 3939 bool empty() const 3940 { 3941 pragma(inline, true); 3942 return !_root; 3943 } 3944 3945 /** Returns: number of elements stored. */ 3946 size_t length() const 3947 { 3948 pragma(inline, true); 3949 return _length; 3950 } 3951 3952 Node rootNode() const 3953 { 3954 pragma(inline, true); 3955 return _root; 3956 } 3957 3958 private: 3959 /** Returns: number of nodes used in `this` tree. Should always equal `Stats.heapNodeCount`. */ 3960 // debug size_t heapAllocationBalance() { return _heapAllocBalance; } 3961 } 3962 3963 void print() @safe const 3964 { 3965 printAt(_root, 0); 3966 } 3967 3968 Node root() 3969 { 3970 pragma(inline, true); 3971 return _root; 3972 } 3973 3974 private: 3975 Node _root; 3976 size_t _length; /// Number of elements (keys or key-value-pairs) currently stored under `_root` 3977 } 3978 } 3979 3980 /** Append statistics of tree under `Node` `curr.` into `stats`. 3981 */ 3982 static private void calculate(Value)(RawRadixTree!(Value).NodeType curr, 3983 ref RawRadixTree!(Value).StatsType stats) 3984 @safe pure nothrow /* TODO: @nogc */ 3985 { 3986 alias RT = RawRadixTree!(Value); 3987 ++stats.popByNodeType[curr.typeIx]; 3988 3989 final switch (curr.typeIx) with (RT.NodeType.Ix) 3990 { 3991 case undefined: 3992 break; 3993 case ix_OneLeafMax7: break; // TODO: calculate() 3994 case ix_TwoLeaf3: break; // TODO: calculate() 3995 case ix_TriLeaf2: break; // TODO: calculate() 3996 case ix_HeptLeaf1: break; // TODO: calculate() 3997 case ix_SparseLeaf1Ptr: 3998 ++stats.heapNodeCount; 3999 const curr_ = curr.as!(SparseLeaf1!Value*); 4000 assert(curr_.length); 4001 ++stats.popHist_SparseLeaf1[curr_.length - 1]; // TODO: type-safe indexing 4002 stats.sparseLeaf1AllocatedSizeSum += curr_.allocatedSize; 4003 break; 4004 case ix_DenseLeaf1Ptr: 4005 const curr_ = curr.as!(DenseLeaf1!Value*); 4006 ++stats.heapNodeCount; 4007 immutable count = curr_._ixBits.countOnes; // number of non-zero sub-nodes 4008 assert(count <= curr_.capacity); 4009 ++stats.popHist_DenseLeaf1[count - 1]; // TODO: type-safe indexing 4010 break; 4011 case ix_SparseBranchPtr: 4012 ++stats.heapNodeCount; 4013 curr.as!(RT.SparseBranchType*).calculate(stats); 4014 break; 4015 case ix_DenseBranchPtr: 4016 ++stats.heapNodeCount; 4017 curr.as!(RT.DenseBranchType*).calculate(stats); 4018 break; 4019 } 4020 } 4021 4022 /** Append statistics of tree under `Leaf1!Value` `curr.` into `stats`. 4023 */ 4024 static private void calculate(Value)(Leaf1!Value curr, 4025 ref RawRadixTree!(Value).StatsType stats) 4026 @safe pure nothrow /* TODO: @nogc */ 4027 { 4028 alias RT = RawRadixTree!(Value); 4029 ++stats.popByLeaf1Type[curr.typeIx]; 4030 4031 final switch (curr.typeIx) with (Leaf1!Value.Ix) 4032 { 4033 case undefined: 4034 break; 4035 case ix_HeptLeaf1: break; // TODO: calculate() 4036 case ix_SparseLeaf1Ptr: 4037 ++stats.heapNodeCount; 4038 const curr_ = curr.as!(SparseLeaf1!Value*); 4039 assert(curr_.length); 4040 ++stats.popHist_SparseLeaf1[curr_.length - 1]; // TODO: type-safe indexing 4041 break; 4042 case ix_DenseLeaf1Ptr: 4043 const curr_ = curr.as!(DenseLeaf1!Value*); 4044 ++stats.heapNodeCount; 4045 immutable count = curr_._ixBits.countOnes; // number of non-zero curr-nodes 4046 assert(count <= curr_.capacity); 4047 assert(count); 4048 ++stats.popHist_DenseLeaf1[count - 1]; // TODO: type-safe indexing 4049 break; 4050 } 4051 } 4052 4053 /** Remap fixed-length typed key `typedKey` to raw (untyped) key of type `UKey`. 4054 TODO: DIP-1000 scope 4055 */ 4056 UKey toFixedRawKey(TypedKey)(const scope TypedKey typedKey, UKey preallocatedFixedUKey) @trusted 4057 { 4058 enum radix = 2^^span; // branch-multiplicity, typically either 2, 4, 16 or 256 4059 immutable key_ = typedKey.bijectToUnsigned; 4060 4061 static assert(key_.sizeof == TypedKey.sizeof); 4062 4063 enum nbits = 8*key_.sizeof; // number of bits in key 4064 enum chunkCount = nbits/span; // number of chunks in key_ 4065 static assert(chunkCount*span == nbits, "Bitsize of TypedKey must be a multiple of span:" ~ span.stringof); 4066 4067 // big-endian storage 4068 foreach (immutable i; 0 .. chunkCount) // for each chunk index 4069 { 4070 immutable bitShift = (chunkCount - 1 - i)*span; // most significant bit chunk first (MSBCF) 4071 preallocatedFixedUKey[i] = (key_ >> bitShift) & (radix - 1); // part of value which is also an index 4072 } 4073 4074 return preallocatedFixedUKey[]; 4075 } 4076 4077 /** Remap typed key `typedKey` to raw (untyped) key of type `UKey`. 4078 */ 4079 UKey toRawKey(TypedKey)(in TypedKey typedKey, ref Array!Ix rawUKey) @trusted 4080 if (isTrieableKeyType!TypedKey) 4081 { 4082 enum radix = 2^^span; // branch-multiplicity, typically either 2, 4, 16 or 256 4083 4084 import nxt.container_traits : isAddress; 4085 static if (isAddress!TypedKey) 4086 static assert(0, "Shift TypedKey " ~ TypedKey.stringof ~ " down by its alignment before returning"); 4087 4088 static if (isFixedTrieableKeyType!TypedKey) 4089 { 4090 rawUKey.length = TypedKey.sizeof; 4091 return typedKey.toFixedRawKey(rawUKey[]); 4092 } 4093 else static if (isArray!TypedKey) 4094 { 4095 alias EType = Unqual!(typeof(TypedKey.init[0])); 4096 static if (is(EType == char)) // TODO: extend to support isTrieableKeyType!TypedKey 4097 { 4098 import std..string : representation; 4099 const ubyte[] ukey = typedKey.representation; // lexical byte-order 4100 return cast(Ix[])ukey; // TODO: needed? 4101 } 4102 else static if (is(EType == wchar)) 4103 { 4104 immutable ushort[] rKey = typedKey.representation; // lexical byte-order. 4105 // TODO: MSByte-order of elements in rKey for ordered access and good branching performance 4106 immutable ubyte[] ukey = (cast(const ubyte*)rKey.ptr)[0 .. rKey[0].sizeof * rKey.length]; // TODO: @trusted functionize. Reuse existing Phobos function? 4107 return ukey; 4108 } 4109 else static if (is(EType == dchar)) 4110 { 4111 immutable uint[] rKey = typedKey.representation; // lexical byte-order 4112 // TODO: MSByte-order of elements in rKey for ordered access and good branching performance 4113 immutable ubyte[] ukey = (cast(const ubyte*)rKey.ptr)[0 .. rKey[0].sizeof * rKey.length]; // TODO: @trusted functionize. Reuse existing Phobos function? 4114 return ukey; 4115 } 4116 else static if (isFixedTrieableKeyType!E) 4117 { 4118 static assert(false, "TODO: Convert array of typed fixed keys"); 4119 } 4120 else 4121 { 4122 static assert(false, "TODO: Handle typed key " ~ TypedKey.stringof); 4123 } 4124 } 4125 else static if (is(TypedKey == struct)) 4126 { 4127 static if (TypedKey.tupleof.length == 1) // TypedKey is a wrapper type 4128 { 4129 return typedKey.tupleof[0].toRawKey(rawUKey); 4130 } 4131 else 4132 { 4133 enum members = __traits(allMembers, TypedKey); 4134 foreach (immutable i, immutable memberName; members) // for each member name in `struct TypedKey` 4135 { 4136 immutable member = __traits(getMember, typedKey, memberName); // member 4137 alias MemberType = typeof(member); 4138 4139 static if (i + 1 == members.length) // last member is allowed to be an array of fixed length 4140 { 4141 Array!Ix memberRawUKey; 4142 const memberRawKey = member.toRawKey(memberRawUKey); // TODO: DIP-1000 scope 4143 rawUKey ~= memberRawUKey; 4144 } 4145 else // non-last member must be fixed 4146 { 4147 static assert(isFixedTrieableKeyType!MemberType, 4148 "Non-last " ~ i.stringof ~ ":th member of type " ~ MemberType.stringof ~ " must be of fixed length"); 4149 Ix[MemberType.sizeof] memberRawUKey; 4150 const memberRawKey = member.toFixedRawKey(memberRawUKey); // TODO: DIP-1000 scope 4151 rawUKey ~= memberRawUKey[]; 4152 } 4153 } 4154 return rawUKey[]; // TODO: return immutable slice 4155 } 4156 } 4157 else 4158 { 4159 static assert(false, "TODO: Handle typed key " ~ TypedKey.stringof); 4160 } 4161 } 4162 4163 /** Remap raw untyped key `ukey` to typed key of type `TypedKey`. */ 4164 inout(TypedKey) toTypedKey(TypedKey)(inout(Ix)[] ukey) @trusted 4165 if (isTrieableKeyType!TypedKey) 4166 { 4167 import nxt.container_traits : isAddress; 4168 static if (isAddress!TypedKey) 4169 static assert(0, "Shift TypedKey " ~ TypedKey.stringof ~ " up by its alignment before returning"); 4170 4171 static if (isFixedTrieableKeyType!TypedKey) 4172 { 4173 enum nbits = 8*TypedKey.sizeof; // number of bits in key 4174 enum chunkCount = nbits/span; // number of chunks in key_ 4175 static assert(chunkCount*span == nbits, "Bitsize of TypedKey must be a multiple of span:" ~ span.stringof); 4176 4177 // TODO: reuse existing trait UnsignedOf!TypedKey 4178 static if (TypedKey.sizeof == 1) { alias RawKey = ubyte; } 4179 else static if (TypedKey.sizeof == 2) { alias RawKey = ushort; } 4180 else static if (TypedKey.sizeof == 4) { alias RawKey = uint; } 4181 else static if (TypedKey.sizeof == 8) { alias RawKey = ulong; } 4182 4183 RawKey bKey = 0; 4184 4185 // big-endian storage 4186 foreach (immutable i; 0 .. chunkCount) // for each chunk index 4187 { 4188 immutable RawKey uix = cast(RawKey)ukey[i]; 4189 immutable bitShift = (chunkCount - 1 - i)*span; // most significant bit chunk first (MSBCF) 4190 bKey |= uix << bitShift; // part of value which is also an index 4191 } 4192 4193 TypedKey typedKey; 4194 bKey.bijectFromUnsigned(typedKey); 4195 return typedKey; 4196 } 4197 else static if (isArray!TypedKey) 4198 { 4199 static if (isArray!TypedKey && 4200 is(Unqual!(typeof(TypedKey.init[0])) == char)) 4201 { 4202 static assert(char.sizeof == Ix.sizeof); 4203 return cast(inout(char)[])ukey; 4204 } 4205 // TODO: handle wchar and dchar 4206 else 4207 { 4208 static assert(false, "TODO: Handle typed key " ~ TypedKey.stringof); 4209 } 4210 } 4211 else static if (is(TypedKey == struct)) 4212 { 4213 static if (TypedKey.tupleof.length == 1) // TypedKey is a wrapper type 4214 { 4215 alias WrappedTypedKey = typeof(TypedKey.tupleof[0]); 4216 return TypedKey(ukey.toTypedKey!(WrappedTypedKey)); 4217 } 4218 else 4219 { 4220 TypedKey typedKey; 4221 size_t ix = 0; 4222 enum members = __traits(allMembers, TypedKey); 4223 foreach (immutable i, immutable memberName; members) // for each member name in `struct TypedKey` 4224 { 4225 alias MemberType = typeof(__traits(getMember, typedKey, memberName)); 4226 static if (i + 1 != members.length) // last member is allowed to be an array of fixed length 4227 static assert(isFixedTrieableKeyType!MemberType, 4228 "Non-last MemberType must be fixed length"); 4229 __traits(getMember, typedKey, memberName) = ukey[ix .. ix + MemberType.sizeof].toTypedKey!MemberType; 4230 ix += MemberType.sizeof; 4231 } 4232 return typedKey; 4233 } 4234 } 4235 else 4236 { 4237 static assert(false, "TODO: Handle typed key " ~ TypedKey.stringof); 4238 } 4239 } 4240 4241 /** Radix-Tree with key of type `K` and value of type `V` (if non-`void`). */ 4242 struct RadixTree(K, V) 4243 if (isTrieableKeyType!(K)) 4244 { 4245 alias RawTree = RawRadixTree!(V); 4246 4247 alias KeyType = K; 4248 alias ValueType = V; 4249 4250 static if (RawTree.hasValue) 4251 { 4252 /** Element type with typed key and value. */ 4253 struct TypedElt 4254 { 4255 K key; 4256 V value; 4257 } 4258 4259 ref V opIndex(K key) 4260 { 4261 pragma(inline, true); 4262 V* value = contains(key); 4263 version(assert) 4264 { 4265 import core.exception : RangeError; 4266 if (value is null) 4267 throw new RangeError("Range violation"); 4268 } 4269 return *value; 4270 } 4271 4272 auto opIndexAssign(in V value, K key) 4273 { 4274 _rawTree.ElementRefType elementRef; // reference to where element was added 4275 4276 Array!Ix rawUKey; 4277 auto rawKey = key.toRawKey(rawUKey); // TODO: DIP-1000 scope 4278 4279 _rawTree.insert(rawKey, value, elementRef); 4280 4281 immutable bool added = elementRef.node && elementRef.modStatus == ModStatus.added; 4282 _length += added; 4283 /* TODO: return reference (via `auto ref` return typed) to stored 4284 value at `elementRef` instead, unless packed static_bitarray storage is used 4285 when `V is bool` */ 4286 return value; 4287 } 4288 4289 /** Insert `key`. 4290 Returns: `true` if `key` wasn't previously added, `false` otherwise. 4291 */ 4292 bool insert(in K key, in V value) @nogc 4293 { 4294 _rawTree.ElementRefType elementRef; // indicates that key was added 4295 4296 Array!Ix rawUKey; 4297 auto rawKey = key.toRawKey(rawUKey); // TODO: DIP-1000 scope 4298 4299 _rawTree.insert(rawKey, value, elementRef); 4300 4301 // debug if (willFail) { dbg("WILL FAIL: elementRef:", elementRef, " key:", key); } 4302 if (elementRef.node) // if `key` was added at `elementRef` 4303 { 4304 // set value 4305 final switch (elementRef.node.typeIx) with (_rawTree.NodeType.Ix) 4306 { 4307 case undefined: 4308 case ix_OneLeafMax7: 4309 case ix_TwoLeaf3: 4310 case ix_TriLeaf2: 4311 case ix_HeptLeaf1: 4312 case ix_SparseBranchPtr: 4313 case ix_DenseBranchPtr: 4314 assert(false); 4315 case ix_SparseLeaf1Ptr: 4316 elementRef.node.as!(SparseLeaf1!V*).setValue(UIx(rawKey[$ - 1]), value); 4317 break; 4318 case ix_DenseLeaf1Ptr: 4319 elementRef.node.as!(DenseLeaf1!V*).setValue(UIx(rawKey[$ - 1]), value); 4320 break; 4321 } 4322 immutable bool hit = elementRef.modStatus == ModStatus.added; 4323 _length += hit; 4324 return hit; 4325 } 4326 else 4327 { 4328 assert(false, "TODO: warning no elementRef for key:"/*, key, " rawKey:", rawKey*/); 4329 } 4330 } 4331 4332 /** Returns: pointer to value if `key` is contained in set, null otherwise. */ 4333 inout(V*) contains(in K key) inout @nogc 4334 { 4335 version(LDC) pragma(inline, true); 4336 Array!Ix rawUKey; 4337 auto rawKey = key.toRawKey(rawUKey); // TODO: DIP-1000 scope 4338 return _rawTree.contains(rawKey); 4339 } 4340 4341 /** AA-style key-value range. */ 4342 Range byKeyValue() @nogc // TODO: inout?, TODO: DIP-1000 scope 4343 { 4344 pragma(inline, true); 4345 return this.opSlice; 4346 } 4347 } 4348 else 4349 { 4350 @nogc: 4351 alias TypedElt = K; 4352 4353 /** Insert `key`. 4354 Returns: `true` if `key` wasn't previously added, `false` otherwise. 4355 */ 4356 bool insert(K key) 4357 { 4358 _rawTree.ElementRefType elementRef; // indicates that elt was added 4359 4360 Array!Ix rawUKey; 4361 auto rawKey = key.toRawKey(rawUKey); // TODO: DIP-1000 scope 4362 4363 _rawTree.insert(rawKey, elementRef); 4364 4365 immutable bool hit = elementRef.node && elementRef.modStatus == ModStatus.added; 4366 _length += hit; 4367 return hit; 4368 } 4369 4370 nothrow: 4371 4372 /** Returns: `true` if `key` is stored, `false` otherwise. */ 4373 bool contains(in K key) inout 4374 { 4375 version(LDC) pragma(inline, true); 4376 Array!Ix rawUKey; 4377 auto rawKey = key.toRawKey(rawUKey); // TODO: DIP-1000 scope 4378 return _rawTree.contains(rawKey); 4379 } 4380 4381 /** AA-style key range. */ 4382 Range byKey() @nogc // TODO: inout?. TODO: DIP-1000 scope 4383 { 4384 pragma(inline, true); 4385 return this.opSlice; 4386 } 4387 } 4388 4389 /** Supports $(B `K` in `this`) syntax. */ 4390 auto opBinaryRight(string op)(in K key) inout 4391 if (op == "in") 4392 { 4393 pragma(inline, true); 4394 return contains(key); // TODO: return `_rawTree.ElementRefType` 4395 } 4396 4397 Range opSlice() @system @nogc // TODO: inout? 4398 { 4399 version(LDC) pragma(inline, true); 4400 return Range(_root, []); 4401 } 4402 4403 /** Get range over elements whose key starts with `keyPrefix`. 4404 The element equal to `keyPrefix` is return as an empty instance of the type. 4405 */ 4406 auto prefix(K keyPrefix) @system 4407 { 4408 Array!Ix rawUKey; 4409 auto rawKeyPrefix = keyPrefix.toRawKey(rawUKey); 4410 4411 UKey rawKeyPrefixRest; 4412 auto prefixedRootNode = _rawTree.prefix(rawKeyPrefix, rawKeyPrefixRest); 4413 4414 return Range(prefixedRootNode, 4415 rawKeyPrefixRest); 4416 } 4417 4418 /** Typed Range. */ 4419 private static struct Range 4420 { 4421 @nogc: 4422 4423 this(RawTree.NodeType root, 4424 UKey keyPrefixRest) 4425 { 4426 pragma(inline, true); 4427 _rawRange = _rawTree.RangeType(root, keyPrefixRest); 4428 } 4429 4430 TypedElt front() const 4431 { 4432 pragma(inline, true); 4433 static if (RawTree.hasValue) 4434 return typeof(return)(_rawRange.lowKey.toTypedKey!K, 4435 _rawRange._front._cachedFrontValue); 4436 else 4437 return _rawRange.lowKey.toTypedKey!K; 4438 } 4439 4440 TypedElt back() const 4441 { 4442 pragma(inline, true); 4443 static if (RawTree.hasValue) 4444 return typeof(return)(_rawRange.highKey.toTypedKey!K, 4445 _rawRange._back._cachedFrontValue); 4446 else 4447 return _rawRange.highKey.toTypedKey!K; 4448 } 4449 4450 @property typeof(this) save() 4451 { 4452 version(LDC) pragma(inline, true); 4453 typeof(return) copy; 4454 copy._rawRange = this._rawRange.save; 4455 return copy; 4456 } 4457 4458 RawTree.RangeType _rawRange; 4459 alias _rawRange this; 4460 } 4461 4462 /** Raw Range. */ 4463 private static struct RawRange 4464 { 4465 this(RawTree.NodeType root, 4466 UKey keyPrefixRest) 4467 { 4468 pragma(inline, true); 4469 this._rawRange = _rawTree.RangeType(root, keyPrefixRest); 4470 } 4471 4472 static if (RawTree.hasValue) 4473 { 4474 const(Elt!V) front() const 4475 { 4476 pragma(inline, true); 4477 return typeof(return)(_rawRange.lowKey, 4478 _rawRange._front._cachedFrontValue); 4479 } 4480 4481 const(Elt!V) back() const 4482 { 4483 pragma(inline, true); 4484 return typeof(return)(_rawRange.highKey, 4485 _rawRange._back._cachedFrontValue); 4486 } 4487 } 4488 else 4489 { 4490 const(Elt!V) front() const 4491 { 4492 pragma(inline, true); 4493 return _rawRange.lowKey; 4494 } 4495 const(Elt!V) back() const 4496 { 4497 pragma(inline, true); 4498 return _rawRange.highKey; 4499 } 4500 } 4501 4502 @property typeof(this) save() 4503 { 4504 pragma(inline, true); 4505 typeof(return) copy; 4506 copy._rawRange = this._rawRange.save; 4507 return copy; 4508 } 4509 4510 RawTree.RangeType _rawRange; 4511 alias _rawRange this; 4512 } 4513 4514 /** This function searches with policy `sp` to find the largest right subrange 4515 on which pred(value, x) is true for all x (e.g., if pred is "less than", 4516 returns the portion of the range with elements strictly greater than 4517 value). 4518 TODO: Add template param (SearchPolicy sp) 4519 4520 TODO: replace `matchCommonPrefix` with something more clever directly 4521 finds the next element after rawKey and returns a TreeRange at that point 4522 */ 4523 auto upperBound(K key) @system 4524 { 4525 Array!Ix rawUKey; 4526 auto rawKey = key.toRawKey(rawUKey); 4527 4528 UKey rawKeyRest; 4529 auto prefixedRootNode = _rawTree.matchCommonPrefix(rawKey, rawKeyRest); 4530 4531 return UpperBoundRange(prefixedRootNode, 4532 rawKey[0 .. $ - rawKeyRest.length], 4533 rawKeyRest); 4534 } 4535 4536 /** Typed Upper Bound Range. 4537 */ 4538 private static struct UpperBoundRange 4539 { 4540 @nogc: 4541 4542 this(RawTree.NodeType root, 4543 UKey rawKeyPrefix, UKey rawKeyRest) 4544 { 4545 _rawRange = _rawTree.RangeType(root, []); 4546 _rawKeyPrefix = rawKeyPrefix; 4547 4548 // skip values 4549 import std.algorithm.comparison : cmp; 4550 while (!_rawRange.empty && 4551 cmp(_rawRange._front.frontKey, rawKeyRest) <= 0) 4552 { 4553 _rawRange.popFront(); 4554 } 4555 } 4556 4557 TypedElt front() 4558 { 4559 Array!Ix wholeRawKey = _rawKeyPrefix.dup; 4560 wholeRawKey ~= _rawRange.lowKey; 4561 static if (RawTree.hasValue) 4562 return typeof(return)(wholeRawKey[].toTypedKey!K, 4563 _rawRange._front._cachedFrontValue); 4564 else 4565 return wholeRawKey[].toTypedKey!K; 4566 } 4567 4568 @property typeof(this) save() 4569 { 4570 pragma(inline, true); 4571 typeof(return) copy; 4572 copy._rawRange = this._rawRange.save; 4573 copy._rawKeyPrefix = this._rawKeyPrefix.dup; 4574 return copy; 4575 } 4576 4577 RawTree.RangeType _rawRange; 4578 alias _rawRange this; 4579 Array!Ix _rawKeyPrefix; 4580 } 4581 4582 static if (RawTree.hasValue) 4583 { 4584 import std.algorithm.iteration : map; 4585 4586 // /** Get range of map keys. */ 4587 // auto byKey() 4588 // { 4589 // return this[].map!(e => e[0]); 4590 // } 4591 4592 // /** Get range of map values. */ 4593 // auto byValue() 4594 // { 4595 // return this[].map!(e => e[1]); 4596 // } 4597 } 4598 4599 /** Returns a duplicate of this tree. 4600 Shallowly duplicates the values in the map case. 4601 */ 4602 typeof(this) dup() 4603 { 4604 return typeof(this)(this._rawTree.dup); 4605 } 4606 4607 RawTree _rawTree; 4608 alias _rawTree this; 4609 } 4610 alias PatriciaTrie = RadixTree; 4611 alias RadixTrie = RadixTree; 4612 alias CompactPrefixTree = RadixTree; 4613 4614 template RadixTreeSet(K) 4615 if (isTrieableKeyType!(K)) 4616 { 4617 alias RadixTreeSet = RadixTree!(K, void); 4618 } 4619 4620 /** Print `tree`. */ 4621 void print(Key, Value)(const ref RadixTree!(Key, Value) tree) @safe 4622 if (isTrieableKeyType!(K)) 4623 { 4624 print(tree._rawTree); 4625 } 4626 4627 /** Keys are stored in a way that they can't be accessed by reference so we 4628 allow array (and string) keys to be of mutable type. 4629 */ 4630 template MutableKey(Key) 4631 { 4632 static if (isArray!Key) 4633 alias MutableKey = const(Unqual!(typeof(Key.init[0])))[]; 4634 else 4635 alias MutableKey = Key; 4636 } 4637 4638 /** Instantiator for the set-version of `RadixTree` where value-type is `void` (unused). */ 4639 RadixTree!(MutableKey!Key, void) radixTreeSet(Key)() @nogc 4640 { 4641 return typeof(return)(); 4642 } 4643 4644 /** Instantiator for the map-version of `RadixTree` where value-type is `Value`. */ 4645 RadixTree!(MutableKey!Key, Value) radixTreeMap(Key, Value)() 4646 { 4647 return typeof(return)(); 4648 } 4649 4650 @safe pure nothrow @nogc unittest 4651 { version(showAssertTags) dbg(); 4652 version(enterSingleInfiniteMemoryLeakTest) 4653 { 4654 while (true) 4655 { 4656 checkNumeric!(bool, float, double, 4657 long, int, short, byte, 4658 ulong, uint, ushort, ubyte); 4659 } 4660 } 4661 else 4662 { 4663 checkNumeric!(bool, float, double, 4664 long, int, short, byte, 4665 ulong, uint, ushort, ubyte); 4666 } 4667 } 4668 4669 /// exercise all switch-cases in `RawRadixTree.prefixAt()` 4670 /*TODO: @safe*/ pure nothrow 4671 /*TODO:@nogc*/ unittest 4672 { version(showAssertTags) dbg(); 4673 import std.algorithm.comparison : equal; 4674 alias Key = string; 4675 auto set = radixTreeSet!(Key); 4676 4677 set.clear(); 4678 set.insert(`-----1`); 4679 assert(set.prefix(`-----`).equal([`1`])); 4680 assert(set.prefix(`-----_`).empty); 4681 assert(set.prefix(`-----____`).empty); 4682 set.insert(`-----2`); 4683 assert(set.prefix(`-----`).equal([`1`, `2`])); 4684 assert(set.prefix(`-----_`).empty); 4685 assert(set.prefix(`-----____`).empty); 4686 set.insert(`-----3`); 4687 assert(set.prefix(`-----`).equal([`1`, `2`, `3`])); 4688 assert(set.prefix(`-----_`).empty); 4689 assert(set.prefix(`-----____`).empty); 4690 set.insert(`-----4`); 4691 assert(set.prefix(`-----`).equal([`1`, `2`, `3`, `4`])); 4692 assert(set.prefix(`-----_`).empty); 4693 assert(set.prefix(`-----____`).empty); 4694 set.insert(`-----5`); 4695 assert(set.prefix(`-----`).equal([`1`, `2`, `3`, `4`, `5`])); 4696 assert(set.prefix(`-----_`).empty); 4697 assert(set.prefix(`-----____`).empty); 4698 set.insert(`-----6`); 4699 assert(set.prefix(`-----`).equal([`1`, `2`, `3`, `4`, `5`, `6`])); 4700 assert(set.prefix(`-----_`).empty); 4701 assert(set.prefix(`-----____`).empty); 4702 set.insert(`-----7`); 4703 assert(set.prefix(`-----`).equal([`1`, `2`, `3`, `4`, `5`, `6`, `7`])); 4704 assert(set.prefix(`-----_`).empty); 4705 assert(set.prefix(`-----____`).empty); 4706 set.insert(`-----8`); 4707 assert(set.prefix(`-----`).equal([`1`, `2`, `3`, `4`, `5`, `6`, `7`, `8`])); 4708 assert(set.prefix(`-----_`).empty); 4709 assert(set.prefix(`-----____`).empty); 4710 set.insert(`-----11`); 4711 assert(set.prefix(`-----`).equal([`1`, `11`, `2`, `3`, `4`, `5`, `6`, `7`, `8`])); 4712 set.insert(`-----22`); 4713 assert(set.prefix(`-----`).equal([`1`, `11`, `2`, `22`, `3`, `4`, `5`, `6`, `7`, `8`])); 4714 set.insert(`-----33`); 4715 assert(set.prefix(`-----`).equal([`1`, `11`, `2`, `22`, `3`, `33`, `4`, `5`, `6`, `7`, `8`])); 4716 set.insert(`-----44`); 4717 assert(set.prefix(`-----`).equal([`1`, `11`, `2`, `22`, `3`, `33`, `4`, `44`, `5`, `6`, `7`, `8`])); 4718 4719 set.clear(); 4720 set.insert(`-----11`); 4721 assert(set.prefix(`-----`).equal([`11`])); 4722 set.insert(`-----22`); 4723 assert(set.prefix(`-----`).equal([`11`, `22`])); 4724 assert(set.prefix(`-----_`).empty); 4725 assert(set.prefix(`-----___`).empty); 4726 4727 set.clear(); 4728 set.insert(`-----111`); 4729 assert(set.prefix(`-----`).equal([`111`])); 4730 set.insert(`-----122`); 4731 assert(set.prefix(`-----`).equal([`111`, `122`])); 4732 set.insert(`-----133`); 4733 assert(set.prefix(`-----`).equal([`111`, `122`, `133`])); 4734 assert(set.prefix(`-----1`).equal([`11`, `22`, `33`])); 4735 assert(set.prefix(`-----1_`).empty); 4736 assert(set.prefix(`-----1___`).empty); 4737 4738 set.clear(); 4739 set.insert(`-----1111`); 4740 assert(set.prefix(`-----`).equal([`1111`])); 4741 assert(set.prefix(`-----_`).empty); 4742 assert(set.prefix(`-----___`).empty); 4743 4744 set.clear(); 4745 set.insert(`-----11111`); 4746 assert(set.prefix(`-----`).equal([`11111`])); 4747 assert(set.prefix(`-----_`).empty); 4748 assert(set.prefix(`-----___`).empty); 4749 set.insert(`-----12222`); 4750 assert(set.prefix(`-----`).equal([`11111`, `12222`])); 4751 assert(set.prefix(`-----_`).empty); 4752 assert(set.prefix(`-----___`).empty); 4753 assert(set.prefix(`-----12`).equal([`222`])); 4754 assert(set.prefix(`-----12_`).empty); 4755 assert(set.prefix(`-----12____`).empty); 4756 } 4757 4758 /// test floating-point key range sortedness 4759 /*@ TODO: safe */ pure nothrow @nogc unittest 4760 { version(showAssertTags) dbg(); 4761 alias T = double; 4762 4763 auto set = radixTreeSet!(T); 4764 4765 import std.range: isForwardRange; 4766 static assert(isForwardRange!(typeof(set[]))); 4767 4768 set.insert(-1.1e6); 4769 set.insert(-2.2e9); 4770 set.insert(-1.1); 4771 set.insert(+2.2); 4772 set.insert(T.max); 4773 set.insert(-T.max); 4774 set.insert(-3.3); 4775 set.insert(-4.4); 4776 set.insert(+4.4); 4777 set.insert(+3.3); 4778 set.insert(+1.1e6); 4779 set.insert(+2.2e9); 4780 4781 import std.algorithm.sorting : isSorted; 4782 assert(set[].isSorted); 4783 } 4784 4785 version(unittest) 4786 auto testScalar(uint span, Keys...)() @safe 4787 if (Keys.length != 0) 4788 { 4789 import std.traits : isIntegral, isFloatingPoint; 4790 import std.range : iota; 4791 foreach (Key; Keys) 4792 { 4793 auto set = radixTreeSet!(Key); 4794 4795 static if (isIntegral!Key) 4796 { 4797 immutable low = max(Key.min, -1_000); 4798 immutable high = min(Key.max, 1_000); 4799 immutable factor = 1; 4800 } 4801 else static if (isFloatingPoint!Key) 4802 { 4803 immutable low = -1_000; 4804 immutable high = 1_000; 4805 immutable factor = 1; 4806 } 4807 else static if (is(Key == bool)) 4808 { 4809 immutable low = false; 4810 immutable high = true; 4811 immutable factor = 1; 4812 } 4813 4814 foreach (immutable uk_; low.iota(high + 1)) 4815 { 4816 immutable uk = factor*uk_; 4817 immutable Key key = cast(Key)uk; 4818 assert(set.insert(key)); // insert new value returns `true` (previously not in set) 4819 assert(!set.insert(key)); // reinsert same value returns `false` (already in set) 4820 } 4821 4822 import std.algorithm.comparison : equal; 4823 import std.algorithm.iteration : map; 4824 () @trusted { assert(set[].equal(low.iota(high + 1).map!(uk => cast(Key)uk))); } (); // TODO: remove @trusted when opSlice support DIP-1000 4825 4826 import std.algorithm.sorting : isSorted; 4827 () @trusted { assert(set[].isSorted); } (); // TODO: remove @trusted when opSlice support DIP-1000 4828 } 4829 } 4830 4831 /// 4832 @safe pure nothrow @nogc unittest 4833 { version(showAssertTags) dbg(); 4834 testScalar!(8, 4835 bool, 4836 double, float, 4837 long, int, short, byte, 4838 ulong, uint, ushort, ubyte); 4839 } 4840 4841 /// 4842 @safe pure nothrow @nogc unittest 4843 { version(showAssertTags) dbg(); 4844 alias Key = ubyte; 4845 auto set = radixTreeSet!(Key); 4846 4847 assert(!set.root); 4848 4849 foreach (immutable i; 0 .. 7) 4850 { 4851 assert(!set.contains(i)); 4852 assert(set.insert(i)); 4853 assert(set.root.peek!HeptLeaf1); 4854 } 4855 4856 foreach (immutable i; 7 .. 48) 4857 { 4858 assert(!set.contains(i)); 4859 assert(set.insert(i)); 4860 assert(set.root.peek!(SparseLeaf1!void*)); 4861 } 4862 4863 foreach (immutable i; 48 .. 256) 4864 { 4865 assert(!set.contains(i)); 4866 assert(set.insert(i)); 4867 assert(set.root.peek!(DenseLeaf1!void*)); 4868 } 4869 } 4870 4871 /** Calculate and print statistics of `tree`. */ 4872 void showStatistics(RT)(const ref RT tree) // why does `in`RT tree` trigger a copy ctor here 4873 { 4874 import std.conv : to; 4875 import std.stdio : writeln; 4876 4877 auto stats = tree.usageHistograms; 4878 4879 writeln("Population By Node Type: ", stats.popByNodeType); 4880 writeln("Population By Leaf1 Type: ", stats.popByLeaf1Type); 4881 4882 writeln("SparseBranch Population Histogram: ", stats.popHist_SparseBranch); 4883 writeln("DenseBranch Population Histogram: ", stats.popHist_DenseBranch); 4884 4885 writeln("SparseLeaf1 Population Histogram: ", stats.popHist_SparseLeaf1); 4886 writeln("DenseLeaf1 Population Histogram: ", stats.popHist_DenseLeaf1); 4887 4888 size_t totalBytesUsed = 0; 4889 4890 // Node-usage 4891 foreach (const index, const pop; stats.popByNodeType) // TODO: use stats.byPair when added to typecons_ex.d 4892 { 4893 size_t bytesUsed = 0; 4894 const ix = cast(RT.NodeType.Ix)index; 4895 final switch (ix) with (RT.NodeType.Ix) 4896 { 4897 case undefined: 4898 continue; // ignore 4899 case ix_OneLeafMax7: 4900 bytesUsed = pop*OneLeafMax7.sizeof; 4901 break; 4902 case ix_TwoLeaf3: 4903 bytesUsed = pop*TwoLeaf3.sizeof; 4904 break; 4905 case ix_TriLeaf2: 4906 bytesUsed = pop*TriLeaf2.sizeof; 4907 break; 4908 case ix_HeptLeaf1: 4909 bytesUsed = pop*HeptLeaf1.sizeof; 4910 break; 4911 case ix_SparseLeaf1Ptr: 4912 bytesUsed = stats.sparseLeaf1AllocatedSizeSum; // variable length struct 4913 totalBytesUsed += bytesUsed; 4914 break; 4915 case ix_DenseLeaf1Ptr: 4916 bytesUsed = pop*DenseLeaf1!(RT.ValueType).sizeof; 4917 totalBytesUsed += bytesUsed; 4918 break; 4919 case ix_SparseBranchPtr: 4920 bytesUsed = stats.sparseBranchAllocatedSizeSum; // variable length struct 4921 totalBytesUsed += bytesUsed; 4922 break; 4923 case ix_DenseBranchPtr: 4924 bytesUsed = pop*RT.DenseBranchType.sizeof; 4925 totalBytesUsed += bytesUsed; 4926 break; 4927 } 4928 writeln(pop, " number of ", 4929 ix.to!string[3 .. $], // TODO: Use RT.NodeType.indexTypeName(ix) 4930 " uses ", bytesUsed/1e6, " megabytes"); 4931 } 4932 4933 writeln("Tree uses ", totalBytesUsed/1e6, " megabytes"); 4934 } 4935 4936 /// test map from `uint` to values of type `double` 4937 @safe pure nothrow @nogc unittest 4938 { version(showAssertTags) dbg(); 4939 alias Key = uint; 4940 alias Value = uint; 4941 4942 auto map = radixTreeMap!(Key, Value); 4943 assert(map.empty); 4944 4945 static assert(map.hasValue); 4946 4947 static Value keyToValue(Key key) @safe pure nothrow @nogc { return cast(Value)((key + 1)*radix); } 4948 4949 foreach (immutable i; 0 .. SparseLeaf1!Value.maxCapacity) 4950 { 4951 assert(!map.contains(i)); 4952 assert(map.length == i); 4953 map[i] = keyToValue(i); 4954 assert(map.contains(i)); 4955 assert(*map.contains(i) == keyToValue(i)); 4956 assert(i in map); 4957 assert(*(i in map) == keyToValue(i)); 4958 assert(map.length == i + 1); 4959 } 4960 4961 foreach (immutable i; SparseLeaf1!Value.maxCapacity .. radix) 4962 { 4963 assert(!map.contains(i)); 4964 assert(map.length == i); 4965 map[i] = keyToValue(i); 4966 assert(map.contains(i)); 4967 assert(*map.contains(i) == keyToValue(i)); 4968 assert(i in map); 4969 assert(*(i in map) == keyToValue(i)); 4970 assert(map.length == i + 1); 4971 } 4972 4973 void testRange() @trusted 4974 { 4975 size_t i = 0; 4976 foreach (immutable keyValue; map[]) 4977 { 4978 assert(keyValue.key == i); 4979 assert(keyValue.value == keyToValue(cast(Key)i)); // TODO: use typed key instead of cast(Key) 4980 ++i; 4981 } 4982 } 4983 4984 testRange(); 4985 } 4986 4987 /** Check string types in `Keys`. */ 4988 auto testString(Keys...)(size_t count, uint maxLength) 4989 if (Keys.length != 0) 4990 { 4991 void testContainsAndInsert(Set, Key)(ref Set set, Key key) 4992 if (isSomeString!Key) 4993 { 4994 import std.conv : to; 4995 immutable failMessage = `Failed for key: "` ~ key.to!string ~ `"`; 4996 4997 assert(!set.contains(key), failMessage); 4998 4999 assert(set.insert(key), failMessage); 5000 assert(set.contains(key), failMessage); 5001 5002 assert(!set.insert(key), failMessage); 5003 assert(set.contains(key), failMessage); 5004 } 5005 5006 import std.algorithm.comparison : equal; 5007 import std.datetime.stopwatch : StopWatch, AutoStart; 5008 5009 foreach (Key; Keys) 5010 { 5011 auto set = radixTreeSet!(Key); 5012 assert(set.empty); 5013 5014 immutable sortedKeys = randomUniqueSortedStrings(count, maxLength); 5015 5016 auto sw1 = StopWatch(AutoStart.yes); 5017 foreach (immutable key; sortedKeys) 5018 { 5019 testContainsAndInsert(set, key); 5020 } 5021 sw1.stop; 5022 5023 version(show) 5024 { 5025 import std.conv : to; 5026 version(show) import std.stdio : writeln; 5027 version(show) writeln("Test for contains and insert took ", sw1.peek()); 5028 } 5029 5030 auto sw2 = StopWatch(AutoStart.yes); 5031 5032 void testPrefix() @trusted 5033 { 5034 assert(set[].equal(sortedKeys)); 5035 import std.algorithm.iteration : filter, map; 5036 assert(set.prefix("a") 5037 .equal(sortedKeys.filter!(x => x.length && x[0] == 'a') 5038 .map!(x => x[1 .. $]))); 5039 assert(set.prefix("aa") 5040 .equal(sortedKeys.filter!(x => x.length >= 2 && x[0] == 'a' && x[1] == 'a') 5041 .map!(x => x[2 .. $]))); 5042 } 5043 5044 testPrefix(); 5045 5046 sw2.stop; 5047 version(show) 5048 { 5049 import std.stdio : writeln; 5050 writeln("Compare took ", sw2.peek()); 5051 } 5052 } 5053 } 5054 5055 /// 5056 @safe /* TODO: pure nothrow @nogc */ 5057 unittest 5058 { version(showAssertTags) dbg(); 5059 testString!(string)(512, 8); 5060 testString!(string)(512, 32); 5061 } 5062 5063 /// test map to values of type `bool` 5064 @safe pure nothrow @nogc unittest 5065 { version(showAssertTags) dbg(); 5066 alias Key = uint; 5067 alias Value = bool; 5068 5069 auto map = radixTreeMap!(Key, Value); 5070 assert(map.empty); 5071 5072 static assert(map.hasValue); 5073 map.insert(Key.init, Value.init); 5074 } 5075 5076 /// test packing of set elements 5077 @safe pure nothrow @nogc unittest 5078 { version(showAssertTags) dbg(); 5079 auto set = radixTreeSet!(ulong); 5080 enum N = HeptLeaf1.capacity; 5081 5082 foreach (immutable i; 0 .. N) 5083 { 5084 assert(!set.contains(i)); 5085 5086 assert(set.insert(i)); 5087 assert(set.contains(i)); 5088 5089 assert(!set.insert(i)); 5090 assert(set.contains(i)); 5091 } 5092 5093 foreach (immutable i; N .. 256) 5094 { 5095 assert(!set.contains(i)); 5096 5097 assert(set.insert(i)); 5098 assert(set.contains(i)); 5099 5100 assert(!set.insert(i)); 5101 assert(set.contains(i)); 5102 } 5103 5104 foreach (immutable i; 256 .. 256 + N) 5105 { 5106 assert(!set.contains(i)); 5107 5108 assert(set.insert(i)); 5109 assert(set.contains(i)); 5110 5111 assert(!set.insert(i)); 5112 assert(set.contains(i)); 5113 } 5114 5115 foreach (immutable i; 256 + N .. 256 + 256) 5116 { 5117 assert(!set.contains(i)); 5118 5119 assert(set.insert(i)); 5120 assert(set.contains(i)); 5121 5122 assert(!set.insert(i)); 5123 assert(set.contains(i)); 5124 } 5125 } 5126 5127 /// 5128 @safe pure nothrow @nogc unittest 5129 { version(showAssertTags) dbg(); 5130 auto set = radixTreeSet!(ubyte); 5131 alias Set = typeof(set); 5132 5133 foreach (immutable i; 0 .. HeptLeaf1.capacity) 5134 { 5135 assert(!set.contains(i)); 5136 5137 assert(set.insert(i)); 5138 assert(set.contains(i)); 5139 5140 assert(!set.insert(i)); 5141 assert(set.contains(i)); 5142 5143 immutable rootRef = set.root.peek!(HeptLeaf1); 5144 assert(rootRef); 5145 } 5146 5147 foreach (immutable i; HeptLeaf1.capacity .. 256) 5148 { 5149 assert(!set.contains(i)); 5150 5151 assert(set.insert(i)); 5152 assert(set.contains(i)); 5153 5154 assert(!set.insert(i)); 5155 assert(set.contains(i)); 5156 } 5157 } 5158 5159 /// 5160 @safe pure nothrow @nogc unittest 5161 { version(showAssertTags) dbg(); 5162 import std.meta : AliasSeq; 5163 foreach (T; AliasSeq!(ushort, uint)) 5164 { 5165 auto set = radixTreeSet!(T); 5166 alias Set = typeof(set); 5167 5168 foreach (immutable i; 0 .. 256) 5169 { 5170 assert(!set.contains(i)); 5171 5172 assert(set.insert(i)); 5173 assert(set.contains(i)); 5174 5175 assert(!set.insert(i)); 5176 assert(set.contains(i)); 5177 } 5178 5179 // 256 5180 assert(!set.contains(256)); 5181 5182 assert(set.insert(256)); 5183 assert(set.contains(256)); 5184 5185 assert(!set.insert(256)); 5186 assert(set.contains(256)); 5187 5188 // 257 5189 assert(!set.contains(257)); 5190 5191 assert(set.insert(257)); 5192 assert(set.contains(257)); 5193 5194 assert(!set.insert(257)); 5195 assert(set.contains(257)); 5196 5197 immutable rootRef = set.root.peek!(Set.DefaultBranchType*); 5198 assert(rootRef); 5199 immutable root = *rootRef; 5200 assert(root.prefix.length == T.sizeof - 2); 5201 5202 } 5203 } 5204 5205 /** Generate `count` number of random unique strings of minimum length 1 and 5206 maximum length of `maxLength`. 5207 */ 5208 private static auto randomUniqueSortedStrings(size_t count, uint maxLength) @trusted pure nothrow 5209 { 5210 import std.random : Random, uniform; 5211 auto gen = Random(); 5212 5213 // store set of unique keys using a builtin D associative array (AA) 5214 bool[string] stringSet; // set of strings using D's AA 5215 5216 try 5217 { 5218 while (stringSet.length < count) 5219 { 5220 const length = uniform(1, maxLength, gen); 5221 auto key = new char[length]; 5222 foreach (immutable ix; 0 .. length) 5223 { 5224 key[ix] = cast(char)('a' + 0.uniform(26, gen)); 5225 } 5226 stringSet[key[].idup] = true; 5227 } 5228 } 5229 catch (Exception e) 5230 { 5231 import nxt.dbgio : dbg; 5232 dbg("Couldn't randomize"); 5233 } 5234 5235 import std.array : array; 5236 import std.algorithm.sorting : sort; 5237 auto keys = stringSet.byKey.array; 5238 sort(keys); 5239 return keys; 5240 } 5241 5242 /** Create a set of words from the file `/usr/share/dict/words`. */ 5243 private void benchmarkReadDictWords(Value)(in size_t maxCount) 5244 { 5245 import std.range : chain; 5246 5247 const path = "/usr/share/dict/words"; 5248 5249 enum hasValue = !is(Value == void); 5250 static if (hasValue) 5251 auto rtr = radixTreeMap!(string, Value); 5252 else 5253 auto rtr = radixTreeSet!(string); 5254 assert(rtr.empty); 5255 5256 enum show = false; 5257 5258 string[] firsts = []; // used to test various things 5259 size_t count = 0; 5260 5261 import std.datetime.stopwatch : StopWatch, AutoStart; 5262 auto sw = StopWatch(AutoStart.yes); 5263 5264 import std.stdio : File; 5265 foreach (const word; chain(firsts, File(path).byLine)) 5266 { 5267 if (count >= maxCount) { break; } 5268 import nxt.array_algorithm : endsWith; 5269 import std.range.primitives : empty; 5270 if (!word.empty && 5271 !word.endsWith(`'s`)) // skip genitive forms 5272 { 5273 assert(!rtr.contains(word)); 5274 5275 static if (show) 5276 { 5277 import std..string : representation; 5278 // dbg(`word:"`, word, `" of length:`, word.length, 5279 // ` of representation:`, word.representation); 5280 // debug rtr.willFail = word == `amiable`; 5281 // if (rtr.willFail) 5282 // { 5283 // rtr.print(); 5284 // } 5285 } 5286 5287 static if (hasValue) 5288 { 5289 assert(rtr.insert(word, count)); 5290 const hitA = rtr.contains(word); 5291 assert(hitA); 5292 assert(*hitA == count); 5293 5294 assert(!rtr.insert(word, count)); 5295 const hitB = rtr.contains(word); 5296 assert(hitB); 5297 assert(*hitB == count); 5298 } 5299 else 5300 { 5301 assert(rtr.insert(word)); 5302 assert(rtr.contains(word)); 5303 5304 assert(!rtr.insert(word)); 5305 assert(rtr.contains(word)); 5306 } 5307 ++count; 5308 } 5309 } 5310 sw.stop; 5311 version(show) 5312 { 5313 import std.stdio : writeln; 5314 writeln("Added ", count, " words from ", path, " in ", sw.peek()); 5315 rtr.showStatistics(); 5316 } 5317 } 5318 5319 unittest 5320 { version(showAssertTags) dbg(); 5321 const maxCount = 1000; 5322 benchmarkReadDictWords!(void)(maxCount); 5323 benchmarkReadDictWords!(size_t)(maxCount); 5324 } 5325 5326 static private void testSlice(T)(ref T x) @trusted 5327 { 5328 auto xr = x[]; 5329 } 5330 5331 bool testEqual(T, U)(ref T x, ref U y) @trusted 5332 { 5333 import std.algorithm.comparison : equal; 5334 return equal(x[], y[]); 5335 } 5336 5337 /** Check correctness when span is `span` and for each `Key` in `Keys`. */ 5338 version(unittest) 5339 private auto checkNumeric(Keys...)() 5340 if (Keys.length != 0) 5341 { 5342 import std.traits : isIntegral, isFloatingPoint; 5343 foreach (immutable it; 0 .. 1) 5344 { 5345 struct TestValueType { int i = 42; float f = 43; char ch = 'a'; } 5346 alias Value = TestValueType; 5347 import std.meta : AliasSeq; 5348 foreach (Key; Keys) 5349 { 5350 auto set = radixTreeSet!(Key); 5351 auto map = radixTreeMap!(Key, Value); 5352 5353 assert(set.empty); 5354 assert(map.empty); 5355 5356 testSlice(set); 5357 testSlice(map); 5358 5359 static assert(!set.hasValue); 5360 static assert(map.hasValue); 5361 5362 static if (is(Key == bool) || 5363 isIntegral!Key || 5364 isFloatingPoint!Key) 5365 { 5366 static if (isIntegral!Key) 5367 { 5368 immutable low = max(Key.min, -1000); 5369 immutable high = min(Key.max, 1000); 5370 immutable factor = 1; 5371 } 5372 else static if (isFloatingPoint!Key) 5373 { 5374 immutable low = -1_000; 5375 immutable high = 1_000; 5376 immutable factor = 100; 5377 } 5378 else static if (is(Key == bool)) 5379 { 5380 immutable low = false; 5381 immutable high = true; 5382 immutable factor = 1; 5383 } 5384 else 5385 { 5386 static assert(false, "Support Key " ~ Key.stringof); 5387 } 5388 immutable length = high - low + 1; 5389 5390 foreach (immutable uk_; low .. high + 1) 5391 { 5392 immutable uk = factor*uk_; 5393 immutable Key key = cast(Key)uk; 5394 5395 assert(!set.contains(key)); // `key` should not yet be in `set` 5396 assert(!map.contains(key)); // `key` should not yet be in 'map 5397 5398 assert(key !in set); // alternative syntax 5399 assert(key !in map); // alternative syntax 5400 5401 // insertion of new `key` is `true` (previously not stored) 5402 assert(set.insert(key)); 5403 assert(map.insert(key, Value.init)); 5404 5405 // `key` should now be in `set` and `map` 5406 assert(set.contains(key)); 5407 assert(map.contains(key)); 5408 5409 // reinsertion of same `key` is `false` (already in stored) 5410 assert(!set.insert(key)); 5411 assert(!map.insert(key, Value.init)); 5412 5413 // `key` should now be `stored` 5414 assert(set.contains(key)); 5415 assert(map.contains(key)); 5416 5417 // alternative syntax 5418 assert(key in set); 5419 assert(key in map); 5420 5421 if (key != Key.max) // except last value 5422 assert(!set.contains(cast(Key)(key + 1))); // next key is not yet in set 5423 } 5424 assert(set.length == length); 5425 } 5426 else 5427 { 5428 static assert(false, `Handle type: "` ~ Key.stringof ~ `"`); 5429 } 5430 5431 auto setDup = set.dup(); 5432 auto mapDup = map.dup(); 5433 5434 assert(testEqual(set, setDup)); 5435 assert(testEqual(map, mapDup)); 5436 5437 set.clear(); 5438 5439 static assert(map.hasValue); 5440 map.clear(); 5441 } 5442 } 5443 } 5444 5445 /** Benchmark performance and memory usage when span is `span`. */ 5446 private void benchmarkTimeAndSpace() 5447 { 5448 version(show) import std.stdio : writeln; 5449 5450 struct TestValueType { int i = 42; float f = 43; char ch = 'a'; } 5451 alias Value = TestValueType; 5452 import std.meta : AliasSeq; 5453 foreach (Key; AliasSeq!(uint)) // just benchmark uint for now 5454 { 5455 auto set = radixTreeSet!(Key); 5456 alias Set = set; 5457 assert(set.empty); 5458 5459 static assert(!set.hasValue); 5460 5461 import std.datetime.stopwatch : StopWatch, AutoStart; 5462 5463 enum n = 1_000_000; 5464 5465 immutable useUniqueRandom = false; 5466 5467 import std.range : generate, take; 5468 import std.random : uniform; 5469 auto randomSamples = generate!(() => uniform!Key).take(n); 5470 5471 { 5472 auto sw = StopWatch(AutoStart.yes); 5473 5474 foreach (immutable Key k; randomSamples) 5475 { 5476 if (useUniqueRandom) 5477 assert(set.insert(k)); 5478 else 5479 set.insert(k); 5480 5481 /* second insert of same key should always return `false` to 5482 indicate that key was already stored */ 5483 static if (false) { assert(!set.insert(k)); } 5484 } 5485 5486 version(show) writeln("trie: Added ", n, " ", Key.stringof, "s of size ", n*Key.sizeof/1e6, " megabytes in ", sw.peek()); 5487 set.showStatistics(); 5488 } 5489 5490 { 5491 auto sw = StopWatch(AutoStart.yes); 5492 bool[int] aa; 5493 5494 foreach (Key k; randomSamples) { aa[k] = true; } 5495 5496 version(show) writeln("D-AA: Added ", n, " ", Key.stringof, "s of size ", n*Key.sizeof/1e6, " megabytes in ", sw.peek()); 5497 } 5498 5499 auto map = radixTreeMap!(Key, Value); 5500 assert(map.empty); 5501 static assert(map.hasValue); 5502 5503 map.insert(Key.init, Value.init); 5504 } 5505 } 5506 5507 /// 5508 @safe pure nothrow @nogc unittest 5509 { version(showAssertTags) dbg(); 5510 struct S { int x; } 5511 5512 alias Key = S; 5513 auto set = radixTreeSet!(Key); 5514 5515 assert(!set.contains(S(43))); 5516 5517 assert(set.insert(S(43))); 5518 assert(set.contains(S(43))); 5519 5520 assert(!set.insert(S(43))); 5521 assert(set.contains(S(43))); 5522 } 5523 5524 /** Static Iota. 5525 * 5526 * TODO: Move to Phobos std.range. 5527 */ 5528 template iota(size_t from, size_t to) 5529 if (from <= to) 5530 { 5531 alias iota = iotaImpl!(to - 1, from); 5532 } 5533 private template iotaImpl(size_t to, size_t now) 5534 { 5535 import std.meta : AliasSeq; 5536 static if (now >= to) 5537 { 5538 alias iotaImpl = AliasSeq!(now); 5539 } 5540 else 5541 { 5542 alias iotaImpl = AliasSeq!(now, iotaImpl!(to, now + 1)); 5543 } 5544 } 5545 5546 unittest 5547 { version(showAssertTags) dbg(); 5548 version(benchmark) benchmarkTimeAndSpace(); 5549 } 5550 5551 import nxt.qcmeman; 5552 5553 version(unittest) 5554 { 5555 import nxt.array_help : s; 5556 version(showAssertTags) import nxt.dbgio : dbg; 5557 }