1 /** 2 * Several implementations of standard containers. 3 */ 4 module iz.containers; 5 6 import 7 core.exception, core.stdc..string; 8 import 9 std.exception, std..string, std.traits, std.conv, std.range.primitives, 10 std.typecons; 11 import 12 iz.memory, iz.types, iz.streams; 13 version(unittest) import 14 std.stdio: writeln, write, stdout; 15 16 version(X86_64) 17 version(linux) version = Nux64; 18 19 /** 20 * Generic, manually managed, array. 21 * 22 * Array(T) implements a single-dimension array of uncollected memory. 23 * It internally allocates memory blocks to minimize the reallocation fingerprints, 24 * allowing insertions to be 2 times faster than built-in arrays. 25 * 26 * Its layout differs from built-in D's dynamic arrays and they cannot be cast as T[] 27 * however, most of the slicing operations are possible. 28 * 29 * Manual management implies that $(D destruct()) must be called on the array when 30 * it goes out of scope. $(D destruct()) is only called on the content when the 31 * specialization is a $(D struct()) or a $(D union)). Classes and pointers must 32 * be freed by hand. 33 */ 34 struct Array(T) 35 { 36 37 private: 38 39 size_t _length; 40 @NoGc Ptr _elems; 41 uint _granularity = 4096; 42 size_t _blockCount; 43 44 pragma(inline, true) 45 void setLength(size_t value) @nogc 46 { 47 assert(_granularity != 0); 48 49 const size_t newBlockCount = ((value * T.sizeof) / _granularity) + 1; 50 if (_blockCount != newBlockCount) 51 { 52 _blockCount = newBlockCount; 53 _elems = reallocMem(_elems, _granularity * _blockCount); 54 } 55 _length = value; 56 } 57 58 pragma(inline, true) 59 void grow() @nogc 60 { 61 length(_length + 1); 62 } 63 64 pragma(inline, true) 65 void shrink() @nogc 66 { 67 length(_length - 1); 68 } 69 70 pragma(inline, true) 71 Unqual!T* rwPtr(size_t index) pure const nothrow @nogc 72 { 73 return cast(Unqual!T*) (_elems + index * T.sizeof); 74 } 75 76 struct Range 77 { 78 private size_t _i; 79 private Array!T* _a; 80 /// 81 this(ref Array!T array, size_t index = 0) @nogc @trusted 82 { 83 _a = &array; 84 _i = index; 85 } 86 /// 87 ref T front() @nogc 88 { 89 return _a.opIndex(_i); 90 } 91 /// 92 void popFront() @nogc @safe 93 { 94 ++_i; 95 } 96 /// 97 bool empty() @nogc @safe 98 { 99 return _i >= _a._length; 100 } 101 } 102 103 pragma(inline, true) 104 void postblitElements()() 105 { 106 static if (is(T == struct) && hasMember!(T, "__postblit") && isCopyable!T ) 107 { 108 foreach(i; 0.._length) 109 (*rwPtr(i)).__postblit(); 110 } 111 } 112 113 public: 114 115 /// Constructs the array with a list of T. 116 this(E...)(E elements) @nogc 117 if (is(Unqual!E == T) || is(T == E)) 118 { 119 opAssign(elements); 120 } 121 122 /// Constructs the array with a D array of T. 123 this(E)(E[] elements...) @nogc 124 if (is(Unqual!E == T) || is(T == E)) 125 { 126 opAssign(elements); 127 } 128 129 /// Constructs by dispatching to the existing opAssign overloads. 130 this(E)(auto ref E value) @nogc 131 { 132 opAssign(value); 133 } 134 135 this(this) 136 { 137 Ptr old = _elems; 138 const size_t sz = _granularity * _blockCount; 139 _elems = getMem(sz); 140 moveMem(_elems, old, sz); 141 postblitElements; 142 } 143 144 ~this() 145 { 146 length(0); 147 if (_elems) 148 freeMem(_elems); 149 _elems = null; 150 } 151 152 /** 153 * Indicates the memory allocation block-size. 154 */ 155 uint granurality() const pure nothrow @safe @nogc 156 { 157 return _granularity; 158 } 159 160 /** 161 * Sets the memory allocation block-size. 162 * value should be set to 16 or 4096 (the default). 163 */ 164 void granularity(uint value) @nogc 165 { 166 if (_granularity == value) 167 return; 168 if (value < T.sizeof) 169 { 170 value = 16 * T.sizeof; 171 } 172 else if (value < 16) 173 { 174 value = 16; 175 } 176 else while (_granularity % 16 != 0) 177 { 178 value--; 179 } 180 _granularity = value; 181 setLength(_length); 182 } 183 184 /** 185 * Indicates how many block the array is made of. 186 */ 187 pragma(inline, true) 188 size_t blockCount() const pure nothrow @safe @nogc 189 { 190 return _blockCount; 191 } 192 193 /// Sets or gets the element count. 194 pragma(inline, true) 195 size_t length() const pure nothrow @safe @nogc 196 { 197 return _length; 198 } 199 200 /// ditto 201 void length(V)(V value) 202 if (isIntegral!V) 203 { 204 if (value == _length) 205 return; 206 size_t oldLen = _length; 207 static if (is(T == struct) && !isTuple!T) 208 { 209 if (value < _length) 210 { 211 foreach (i; value.._length) 212 destruct(opIndex(i)); 213 } 214 } 215 setLength(value); 216 static if (is(T == struct)) 217 { 218 if (value > oldLen) 219 foreach (i; oldLen.._length) 220 emplace(rwPtr(i)); 221 } 222 } 223 224 /** 225 * Pointer to the first element. 226 * As it's always assigned It cannot be used to determine if the array is empty. 227 */ 228 pragma(inline, true) 229 Ptr ptr() pure nothrow @nogc 230 { 231 return _elems; 232 } 233 234 /** 235 * Typed pointer to the first element. 236 */ 237 pragma(inline, true) 238 T* typedPtr() pure nothrow @nogc 239 { 240 return cast(T*) _elems; 241 } 242 243 /** 244 * Returns the string representation of the array. 245 * 246 * Throw: 247 * A ConvException if T is not converitble to string. 248 */ 249 static if (__traits(compiles, to!string(opSlice()))) 250 string toString() 251 { 252 if (_length == 0) 253 return "[]"; 254 else 255 { 256 auto r = opSlice(); 257 return to!string(r); 258 } 259 } 260 261 /// Returns a mutable (deep) copy of the array. 262 Array!T dup()() 263 { 264 Array!T result = this; 265 return result; 266 } 267 268 /// Support for associative arrays. 269 size_t toHash() nothrow @trusted 270 { 271 return opSlice().hashOf; 272 } 273 274 /// Support for equality tests. 275 bool opEquals(A)(auto ref A array) const pure @nogc @trusted 276 if ((is(Unqual!A == Unqual!(Array!T)) || is(Unqual!(ElementEncodingType!A) == T))) 277 { 278 if (_length != array.length) 279 return false; 280 else if (_length == 0 && array.length == 0) 281 return true; 282 static if (is(Unqual!A == Unqual!(Array!T))) 283 return _elems[0.._length * T.sizeof] == 284 array._elems[0..array._length * T.sizeof]; 285 else 286 return _elems[0.._length * T.sizeof] == 287 array.ptr[0..array.length]; 288 } 289 290 /// Support for the array syntax. 291 pragma(inline, true) 292 ref T opIndex(size_t i) const pure @nogc 293 { 294 return *rwPtr(i); 295 } 296 297 /// Support for the array syntax. 298 void opIndexAssign()(ref T item, size_t i) @nogc 299 { 300 *rwPtr(i) = item; 301 } 302 303 /// Ditto 304 void opIndexAssign()(T item, size_t i) @nogc 305 { 306 *rwPtr(i) = item; 307 } 308 309 /// ditto 310 static if (isTemplateInstance!(T) && __traits(isSame, TemplateOf!T, TemplateOf!(typeof(this)))) 311 void opIndexAssign()(TemplateArgsOf!(T)[0][] item, size_t i) @nogc 312 { 313 *rwPtr(i) = item; 314 } 315 316 /// Support for the foreach operator. 317 int opApply(scope int delegate(ref T) dg) 318 { 319 int result; 320 foreach (immutable i; 0 .. _length) 321 { 322 result = dg(*rwPtr(i)); 323 if (result) break; 324 } 325 return result; 326 } 327 328 /// Support for the foreach_reverse operator. 329 int opApplyReverse(scope int delegate(ref T) dg) 330 { 331 int result; 332 foreach_reverse (immutable i; 0 .. _length) 333 { 334 result = dg(*rwPtr(i)); 335 if (result) break; 336 } 337 return result; 338 } 339 340 /// Support for the dollar operator. 341 size_t opDollar() const pure nothrow @safe @nogc 342 { 343 return _length; 344 } 345 346 /// Assign another Array!T. 347 void opAssign(E)(auto ref Array!E elements) @nogc 348 if (is(Unqual!E == T) || is(E == T)) 349 { 350 setLength(elements._length); 351 moveMem(_elems, elements._elems, T.sizeof * _length); 352 /*setLength(0); 353 _granularity = elements._granularity; 354 _length = elements.length; 355 _elems = elements._elems; 356 _blockCount = elements._blockCount; 357 __postblit();*/ 358 } 359 360 /// Assigns a D array. 361 void opAssign(E)(auto ref E[] elements) @nogc 362 if (is(Unqual!E == T) || is(E == T)) 363 { 364 setLength(elements.length); 365 foreach (i, element; elements) 366 *rwPtr(i) = cast(T) element; 367 } 368 369 /// Assigns an inpunt range. 370 void opAssign(E)(auto ref E elements) @nogc 371 if (isInputRange!E && is(Unqual!(ElementType!E) == T) && !isRandomAccessRange!E) 372 { 373 const len = walkLength(elements); 374 setLength(len); 375 foreach (immutable i; 0..len) 376 { 377 opAssign(elements.front); 378 elements.popFront; 379 } 380 } 381 382 /// Support for the cat operator 383 auto ref typeof(this) opBinary(string op : "~", R)(auto ref R rhs) return @nogc 384 if (__traits(hasMember, R, "length") && __traits(hasMember, R, "ptr")) 385 { 386 typeof(this) result; 387 result.length = _length + rhs.length; 388 moveMem(result.rwPtr(0), _elems , T.sizeof * _length); 389 moveMem(result.rwPtr(_length), rhs._elems , T.sizeof * rhs.length); 390 return result; 391 } 392 393 /// Support for the cat operator. 394 ref typeof(this) opOpAssign(string op, E = T)(auto ref E[] elements) @nogc 395 if (is(Unqual!E == T) || is(E == T)) 396 { 397 static if (op == "~") 398 { 399 const old = _length; 400 setLength(_length + elements.length); 401 moveMem( rwPtr(old), elements.ptr , T.sizeof * elements.length); 402 return this; 403 } 404 else static assert(0, "operator not implemented"); 405 } 406 407 /// Support for the cat operator. 408 ref typeof(this) opOpAssign(string op)(T aElement) @nogc 409 { 410 static if (op == "~") 411 { 412 grow; 413 opIndexAssign(aElement, _length-1); 414 return this; 415 } 416 else static assert(0, "operator not implemented"); 417 } 418 419 /// Support for output ranges. 420 alias put = opOpAssign!"~"; 421 422 /// ditto 423 void put(E)(auto ref E[] elements) @nogc 424 if (is(Unqual!E == T) || is(E == T)) 425 { 426 const old = _length; 427 setLength(_length + elements.length); 428 moveMem( rwPtr(old), elements.ptr , T.sizeof * elements.length); 429 } 430 431 /// Returns a slice of the array. The memory is not duplicated. 432 auto ref opSlice(bool dSlice = false)(size_t lo, size_t hi) return @nogc 433 { 434 static if (dSlice) 435 { 436 return (cast(T*) _elems)[lo..hi]; 437 } 438 else 439 { 440 Array!T result; 441 result.length = hi - lo; 442 moveMem(result.rwPtr(0), rwPtr(lo), (hi - lo) * T.sizeof); 443 return result; 444 } 445 } 446 447 /// Returns the array as a D slice. The memory is not duplicated. 448 T[] opSlice() const 449 { 450 return (cast(T*) _elems)[0.._length]; 451 } 452 453 /// Support for filling the array with a single element. 454 void opSliceAssign()(T value) @nogc 455 { 456 rwPtr(0)[0.._length] = value; 457 } 458 459 /// ditto 460 void opSliceAssign()(T value, size_t lo, size_t hi) @nogc 461 { 462 foreach (immutable i; lo .. hi) 463 *rwPtr(i) = value; 464 } 465 466 /// Returns an input range with an assignable front. 467 auto range() 468 { 469 return Range(this, 0); 470 } 471 472 /// Allows to use the array as a D built-in array. 473 alias opSlice this; 474 } 475 /// 476 unittest 477 { 478 Array!int a; 479 a.length = 2; 480 a[] = 1; 481 assert(a[0] == 1); 482 assert(a[1] == 1); 483 } 484 485 unittest 486 { 487 import std.range.primitives; 488 static assert(isOutputRange!(Array!int, int)); 489 Array!(char) a; 490 a.put("someString"); 491 } 492 493 494 unittest 495 { 496 alias Key = string; 497 alias A = Array!int; 498 A[Key] x; 499 //x["a"] = [0]; 500 } 501 502 unittest 503 { 504 // init-index 505 Array!size_t a; 506 a.length = 2; 507 a[0] = 8; 508 a[1] = 9; 509 assert( a[0] == 8); 510 assert( a[1] == 9); 511 assert( a[$-1] == 9); 512 513 Array!int b = Array!int(0,1,2,3,4,5,6); 514 assert( b.length == 7); 515 assert( b[$-1] == 6); 516 517 Array!float floatarr = Array!float ([0.0f, 0.1f, 0.2f, 0.3f, 0.4f]); 518 assert( floatarr.length == 5); 519 assert( floatarr[0] == 0.0f); 520 assert( floatarr[1] == 0.1f); 521 assert( floatarr[2] == 0.2f); 522 assert( floatarr[3] == 0.3f); 523 assert( floatarr[4] == 0.4f); 524 525 // loops 526 int i; 527 foreach (float aflt; floatarr) 528 { 529 float v = i * 0.1f; 530 assert( aflt == v); 531 i++; 532 } 533 foreach_reverse(float aflt; floatarr) 534 { 535 i--; 536 float v = i * 0.1f; 537 assert( aflt == v); 538 } 539 540 // opEquals 541 auto nativeArr = [111u, 222u, 333u, 444u, 555u]; 542 auto arrcpy1 = Array!uint(111u, 222u, 333u, 444u, 555u); 543 auto arrcpy2 = Array!uint(111u, 222u, 333u, 444u, 555u); 544 assert( arrcpy1 == nativeArr ); 545 assert( arrcpy2 == nativeArr ); 546 assert( arrcpy1 == arrcpy2 ); 547 arrcpy2[0] = 0; 548 assert( arrcpy1 != arrcpy2 ); 549 arrcpy1.length = 3; 550 assert( nativeArr != arrcpy1 ); 551 arrcpy1.length = 0; 552 arrcpy2.length = 0; 553 assert( arrcpy1 == arrcpy2 ); 554 555 // opSlice 556 Array!float g0 = floatarr[1..4]; 557 assert( g0[0] == floatarr[1]); 558 assert( g0[2] == floatarr[3]); 559 Array!float g1 = floatarr; 560 assert( g1[0] == floatarr[0]); 561 assert( g1[4] == floatarr[4]); 562 563 // opSliceAssign 564 g1[] = 0.123456f; 565 assert( g1[0] == 0.123456f); 566 assert( g1[3] == 0.123456f); 567 g1[0..1] = 0.654321f; 568 assert( g1[0] == 0.654321f); 569 assert( g1[1] == 0.123456f); 570 assert( g1[2] == 0.123456f); 571 572 // huge 573 a.length = 10_000_000; 574 a[$-1] = a.length-1; 575 assert(a[a.length-1] == a.length-1); 576 a.length = 10; 577 a.length = 10_000_000; 578 a[$-1] = a.length-1; 579 assert(a[$-1] == a.length-1); 580 } 581 582 unittest 583 { 584 Array!char a = "123456"; 585 Array!char b = a; 586 assert(b.length == 6); 587 assert(b == "123456"); 588 destructEach(a,b); 589 } 590 591 unittest 592 { 593 static int c; 594 static struct S{int i = 1; ~this() @nogc {c = 1;}} 595 Array!S array; 596 assert(array.toString == "[]"); 597 array.length = 1; 598 assert(array[0].i == 1); 599 array.length = 0; 600 assert(c); 601 } 602 603 unittest 604 { 605 int[] source = [0,1,2]; 606 Array!int a = source; 607 assert(a == source); 608 assert(a.dup == source); 609 destruct(a); 610 } 611 612 @nogc unittest 613 { 614 static int[] source = [0,1,2,3]; 615 static int[] r = [0,2,3]; 616 Array!int a = source; 617 assert(a == source); 618 a = a[0..1] ~ a[2..$]; 619 assert(a == r); 620 destruct(a); 621 } 622 623 @nogc unittest 624 { 625 static int[] aa = [0,1]; 626 static int[] bb = [2,3]; 627 static int[] r0 = [0,1,2,3]; 628 static int[] r1 = [0,1,2,3,0,1,2,3]; 629 Array!int a = aa; 630 Array!int b = bb; 631 Array!int c = a ~ b; 632 assert(c == r0); 633 assert(c ~ c == r1); 634 destructEach(a, b, c); 635 } 636 637 unittest 638 { 639 Array!(Array!(const(char))) a; 640 a.length = 2; 641 a[0] = "first"; 642 a[1] = "second".dup; 643 destruct(a); 644 } 645 646 private mixin template ListHelpers(T) 647 { 648 static if (is (T == class)) 649 { 650 final public T addNewItem(A...)(A a) 651 { 652 T result = construct!T(a); 653 add(result); 654 return result; 655 } 656 } 657 else static if (is (T == struct)) 658 { 659 final public T * addNewItem(A...)(A a) 660 { 661 T * result = construct!T(a); 662 add(result); 663 return result; 664 } 665 } 666 else static if (isPointer!T) 667 { 668 final public T addNewItem(A...)(A a) 669 { 670 T result = newPtr!(PointerTarget!T)(a); 671 add(result); 672 return result; 673 } 674 } 675 676 alias opDollar = count; 677 } 678 679 680 /** 681 * A list, fast to be iterated, slow to be reorganized. 682 * Encapsulates an Array!T and interfaces it as a list. 683 */ 684 class ContiguousList(T) 685 { 686 mixin ListHelpers!T; 687 mixin inheritedDtor; 688 689 private: 690 691 @NoGc Array!T _items; 692 693 694 public: 695 696 /// 697 this(A...)(A elements) 698 { 699 _items = Array!T(elements); 700 } 701 702 ~this() 703 { 704 _items.length = 0; 705 } 706 707 /// Support for the array syntax. 708 ref T opIndex(ptrdiff_t i) 709 { 710 return _items[i]; 711 } 712 713 /// Support for the array syntax. 714 void opIndexAssign(T item, size_t i) 715 { 716 _items[i] = item; 717 } 718 719 /// Support for the foreach operator. 720 int opApply(scope int delegate(ref T) dg) 721 { 722 int result; 723 foreach (immutable i; 0 .. _items.length) 724 { 725 result = dg(_items[i]); 726 if (result) break; 727 } 728 return result; 729 } 730 731 /// Support for the foreach_reverse operator. 732 int opApplyReverse(scope int delegate(ref T) dg) 733 { 734 int result; 735 foreach_reverse(immutable i; 0 .. _items.length) 736 { 737 result = dg(_items[i]); 738 if (result) break; 739 } 740 return result; 741 } 742 743 /// Replaces the items with the content of a D T[]. 744 void opAssign(T[] items) 745 { 746 _items.opAssign(items); 747 } 748 749 /// Replaces the items with the content of an Array!T. 750 void opAssign(Array!T items) 751 { 752 _items.opAssign(items); 753 } 754 755 deprecated("formerly implemented for the List interface") 756 T last() 757 { 758 return _items[$-1]; 759 } 760 761 deprecated("formerly implemented for the List interface") 762 T first() 763 { 764 return _items[0]; 765 } 766 767 /** 768 * Tries to find an item in the list. 769 * 770 * Params: 771 * item = the item to find. 772 * Returns: 773 * -1 if item is not present otherwise its index. 774 */ 775 ptrdiff_t find(T item) 776 { 777 ptrdiff_t result = -1; 778 foreach (immutable i; 0 .. _items.length) 779 { 780 if (_items[i] == item) 781 { 782 result = i; 783 break; 784 } 785 } 786 return result; 787 } 788 789 /** 790 * Adds an item at the end of the list and returns its index. 791 * 792 * Returns: 793 * The last item index. 794 */ 795 ptrdiff_t add(T item) 796 { 797 _items.grow; 798 _items[$-1] = item; 799 return _items.length - 1; 800 } 801 802 /** 803 * Adds items at the end of the list. 804 * 805 * Returns: 806 * The last item index. 807 */ 808 ptrdiff_t add(I)(I items) 809 { 810 _items ~= items; 811 return _items.length - 1; 812 } 813 814 /** 815 * Inserts an item at the beginning of the list. 816 * 817 * In a Contiguous list, add() should be preferred over insert(). 818 * 819 * Returns: 820 * Always 0. 821 */ 822 ptrdiff_t insert(T item) 823 { 824 _items.grow; 825 memmove(_items.ptr + T.sizeof, _items.ptr, (_items.length - 1) * T.sizeof); 826 _items[0] = item; 827 return 0; 828 } 829 830 /** 831 * Inserts an item at a given position. 832 * 833 * In a Contiguous list, add() should ne preferred over insert(). 834 * 835 * Params: 836 * position = The position where to insert. 837 * item = The item to insert. 838 * Returns: 839 * The item index, position if it was valid. 840 */ 841 ptrdiff_t insert(size_t position, T item) 842 { 843 if (position == 0) 844 return insert(item); 845 else if (position >= _items.length) 846 return add(item); 847 else 848 { 849 _items.grow; 850 memmove(_items.ptr + T.sizeof * position + 1, 851 _items.ptr + T.sizeof * position, 852 (_items.length - 1 - position) * T.sizeof); 853 _items[position] = item; 854 return position; 855 } 856 } 857 858 /** 859 * Exchanges the positions of two items. 860 * 861 * Params: 862 * item1 = The first item. 863 * item2 = The second item. 864 */ 865 void swapItems(T item1, T item2) 866 in 867 { 868 assert(item1 != item2); 869 } 870 body 871 { 872 ptrdiff_t i1 = find(item1); 873 ptrdiff_t i2 = find(item2); 874 if (i1 != -1 && i2 != -1) 875 { 876 _items[i1] = _items[i2]; 877 _items[i2] = item1; 878 } 879 } 880 881 /** 882 * Exchanges the positions of two items. 883 * 884 * Params: 885 * index1 = The first item index. 886 * index2 = The second item index. 887 */ 888 void swapIndexes(size_t index1, size_t index2) 889 { 890 if (index1 == index2) return; 891 if ((index1 >= _items.length) | (index2 >= _items.length)) return; 892 893 auto old = _items[index1]; 894 _items[index1] = _items[index2]; 895 _items[index2] = old; 896 } 897 898 /** 899 * Removes an item from the list. 900 * 901 * Params: 902 * item = The item to remove. 903 * Returns: 904 * true if the item wasin the list, false otherwise. 905 */ 906 bool remove(T item) 907 { 908 auto i = find(item); 909 auto result = (i != -1); 910 if (result) 911 extract(i); 912 return result; 913 } 914 915 /** 916 * Removes an item from the list. 917 * 918 * Params: 919 * index = The index of the item to remove. 920 * Returns: 921 * The item that's been removed. 922 */ 923 T extract(size_t index) 924 { 925 T result = _items[index]; 926 if (index == _items.length-1) 927 { 928 _items.shrink; 929 } 930 else if (index == 0) 931 { 932 memmove(_items.ptr, _items.ptr + T.sizeof, (_items.length - 1) * T.sizeof); 933 _items.shrink; 934 } 935 else 936 { 937 Ptr fromPtr = _items.ptr + T.sizeof * index; 938 memmove(fromPtr, fromPtr + T.sizeof, (_items.length - index) * T.sizeof); 939 _items.shrink; 940 } 941 return result; 942 } 943 944 /** 945 * Empties the list. 946 */ 947 void clear() 948 { 949 _items.length = 0; 950 } 951 952 /** 953 * Returns the items count. 954 */ 955 final size_t count() const pure nothrow @safe 956 { 957 return _items.opDollar(); 958 } 959 960 /** 961 * Returns the internal array. 962 * 963 * ContiguousList doesn't contain any other hidden field 964 * and the container can be modified without altering the 965 * state of the list. 966 */ 967 final ref Array!T array() nothrow @safe 968 { 969 return _items; 970 } 971 } 972 973 974 /** 975 * Payload for the dynamic list. 976 */ 977 private template dlistPayload(T) 978 { 979 private static const prevOffs = 0; 980 private static const nextOffs = size_t.sizeof; 981 private static const dataOffs = size_t.sizeof + size_t.sizeof; 982 983 @nogc nothrow private: 984 985 void* newPld(void* aPrevious, void* aNext, ref T aData) @trusted 986 { 987 auto result = getMem( 2 * size_t.sizeof + T.sizeof); 988 if (result) 989 { 990 *cast(size_t*) (result + prevOffs) = cast(size_t) aPrevious; 991 *cast(size_t*) (result + nextOffs) = cast(size_t) aNext; 992 static if (is(T == struct)) 993 { 994 static T init; 995 copyMem(result + dataOffs, &init, T.sizeof); 996 } 997 *cast(T*) (result + dataOffs) = aData; 998 } 999 return result; 1000 } 1001 void freePld(void* aPayload) @trusted 1002 in 1003 { 1004 assert(aPayload); 1005 } 1006 body 1007 { 1008 static if (is(T==struct)) 1009 { 1010 destruct(getData(aPayload)); 1011 } 1012 freeMem(aPayload); 1013 } 1014 1015 void setPrev(void* aPayload, void* aPrevious) @trusted 1016 in 1017 { 1018 assert(aPayload); 1019 } 1020 body 1021 { 1022 *cast(void**) (aPayload + prevOffs) = aPrevious; 1023 } 1024 1025 void setNext(void* aPayload, void* aNext) @trusted 1026 in 1027 { 1028 assert(aPayload); 1029 } 1030 body 1031 { 1032 *cast(void**) (aPayload + nextOffs) = aNext; 1033 } 1034 1035 void setData(void* aPayload, ref T aData) @trusted 1036 in 1037 { 1038 assert(aPayload); 1039 } 1040 body 1041 { 1042 *cast(T*) (aPayload + dataOffs) = aData; 1043 static if (is(T == struct) && hasMember!(T, "__postblit") && isCopyable!T ) 1044 { 1045 (cast(T*) (aPayload + dataOffs)).__postblit(); 1046 } 1047 } 1048 1049 void* getPrev(void* aPayload) @trusted 1050 { 1051 version(X86) asm @nogc nothrow 1052 { 1053 naked; 1054 mov EAX, [EAX + prevOffs]; 1055 ret; 1056 } 1057 else version(Win64) asm @nogc nothrow 1058 { 1059 naked; 1060 mov RAX, [RCX + prevOffs]; 1061 ret; 1062 } 1063 else version(Nux64) asm @nogc nothrow 1064 { 1065 naked; 1066 mov RAX, [RDI + prevOffs]; 1067 ret; 1068 } 1069 else return *cast(void**) (aPayload + prevOffs); 1070 } 1071 1072 void* getNext(void* aPayload) @trusted 1073 { 1074 version(X86) asm @nogc nothrow 1075 { 1076 naked; 1077 mov EAX, [EAX + nextOffs]; 1078 ret; 1079 } 1080 else version(Win64) asm @nogc nothrow 1081 { 1082 naked; 1083 mov RAX, [RCX + nextOffs]; 1084 ret; 1085 } 1086 else version(Nux64) asm @nogc nothrow 1087 { 1088 naked; 1089 mov RAX, [RDI + nextOffs]; 1090 ret; 1091 } 1092 else return *cast(void**) (aPayload + nextOffs); 1093 } 1094 1095 ref T getData(void* aPayload) @trusted 1096 { 1097 /*version(X86) asm @nogc nothrow 1098 { 1099 naked; 1100 mov EAX, [EAX + dataOffs]; 1101 ret; 1102 } 1103 else version(Win64) asm @nogc nothrow 1104 { 1105 naked; 1106 mov RAX, [RCX + dataOffs]; 1107 ret; 1108 } 1109 else version(Nux64) asm @nogc nothrow 1110 { 1111 naked; 1112 mov RAX, [RDI + dataOffs]; 1113 ret; 1114 } 1115 else*/ return *cast(T*) (aPayload + dataOffs); 1116 } 1117 } 1118 1119 1120 /** 1121 * A List implementation, slow to be iterated, fast to be reorganized. 1122 * This is a standard doubly linked list, with GC-free heap allocations. 1123 */ 1124 class DynamicList(T) 1125 { 1126 mixin ListHelpers!T; 1127 mixin inheritedDtor; 1128 1129 private: 1130 1131 size_t _count; 1132 void* _last; 1133 void* _first; 1134 alias payload = dlistPayload!T; 1135 1136 void* getPayloadFromIx(size_t index) @safe @nogc nothrow 1137 { 1138 void* current = _first; 1139 foreach (immutable i; 0 .. index) 1140 current = payload.getNext(current); 1141 return current; 1142 } 1143 1144 void* getPayloadFromDt(ref T item) @trusted 1145 { 1146 void* current = _first; 1147 while (current) 1148 { 1149 if (payload.getData(current) == item) 1150 break; 1151 current = payload.getNext(current); 1152 } 1153 return current; 1154 } 1155 1156 public: 1157 1158 /// 1159 this(A...)(A elements) 1160 { 1161 foreach (elem; elements) 1162 add(elem); 1163 } 1164 1165 ~this() 1166 { 1167 clear; 1168 } 1169 1170 /// Support for the array syntax. 1171 ref T opIndex(ptrdiff_t i) @safe @nogc nothrow 1172 { 1173 void* _pld = getPayloadFromIx(i); 1174 return payload.getData(_pld); 1175 } 1176 1177 /// Support for the array syntax. 1178 void opIndexAssign(ref T item, size_t i) @safe @nogc nothrow 1179 { 1180 void* _pld = getPayloadFromIx(i); 1181 payload.setData(_pld, item); 1182 } 1183 1184 /// Support for the foreach operator. 1185 int opApply(int delegate(ref T) dg) @trusted 1186 { 1187 int result; 1188 void* current = _first; 1189 while (current) 1190 { 1191 result = dg(payload.getData(current)); 1192 if (result) break; 1193 current = payload.getNext(current); 1194 } 1195 return result; 1196 } 1197 1198 /// Support for the foreach_reverse operator. 1199 int opApplyReverse(int delegate(ref T) dg) @trusted 1200 { 1201 int result; 1202 void* current = _last; 1203 while (current) 1204 { 1205 result = dg(payload.getData(current)); 1206 if (result) break; 1207 current = payload.getPrev(current); 1208 } 1209 return result; 1210 } 1211 1212 /// Replaces the items with the content of a D T[]. 1213 void opAssign(T[] elems) @trusted @nogc 1214 { 1215 clear; 1216 foreach (elem; elems) 1217 add(elem); 1218 } 1219 1220 /// Returns the first element. 1221 T last() @safe @nogc nothrow 1222 { 1223 return payload.getData(_last); 1224 } 1225 1226 /// Returns the last element. 1227 T first() @safe @nogc nothrow 1228 { 1229 return payload.getData(_first); 1230 } 1231 1232 /** 1233 * Tries to find an item in the list. 1234 * 1235 * Params: 1236 * item = the item to find. 1237 * Returns: 1238 * -1 if item is not present otherwise its index. 1239 */ 1240 ptrdiff_t find(T item) @trusted 1241 { 1242 void* current = _first; 1243 ptrdiff_t result = -1; 1244 while (current) 1245 { 1246 result++; 1247 if (payload.getData(current) == item) 1248 return result++; 1249 current = payload.getNext(current); 1250 } 1251 return -1; 1252 } 1253 1254 /** 1255 * Adds an item at the end of the list and returns its index. 1256 */ 1257 ptrdiff_t add(ref T item) @trusted @nogc 1258 { 1259 if (!_first) 1260 return insert(item); 1261 else 1262 { 1263 void* _pld = payload.newPld(_last, null, item); 1264 payload.setNext(_last, _pld); 1265 _last = _pld; 1266 return _count++; 1267 } 1268 } 1269 1270 /// ditto 1271 ptrdiff_t add(T item) @trusted @nogc 1272 { 1273 return add(item); 1274 } 1275 1276 /** 1277 * Adds items at the end of the list and returns the last item index. 1278 */ 1279 ptrdiff_t add(T[] items) @trusted @nogc 1280 { 1281 foreach (item; items) 1282 add(item); 1283 return _count - 1; 1284 } 1285 1286 /** 1287 * Inserts an item at the beginning of the list. 1288 */ 1289 ptrdiff_t insert(ref T item) @trusted @nogc 1290 { 1291 void* _pld = payload.newPld(null, _first, item); 1292 if (_first) payload.setPrev(_first, _pld); 1293 else _last = _pld; 1294 _first = _pld; 1295 ++_count; 1296 return 0; 1297 } 1298 1299 /// ditto 1300 ptrdiff_t insert(T item) @trusted @nogc 1301 { 1302 return insert(item); 1303 } 1304 1305 /** 1306 * Inserts an item at a given position. 1307 * 1308 * Params: 1309 * position = The position where to insert. 1310 * item = The item to insert. 1311 * Returns: 1312 * The item index, position if it was valid. 1313 */ 1314 ptrdiff_t insert(size_t position, ref T item) @trusted @nogc 1315 { 1316 if (!_first || position == 0) 1317 { 1318 return insert(item); 1319 } 1320 else if (position >= _count) 1321 { 1322 return add(item); 1323 } 1324 else 1325 { 1326 void* old = getPayloadFromIx(position); 1327 void* prev = payload.getPrev(old); 1328 void* _pld = payload.newPld(prev, old, item); 1329 payload.setPrev(old, _pld); 1330 payload.setNext(prev, _pld); 1331 _count++; 1332 return position; 1333 } 1334 } 1335 1336 /// ditto 1337 ptrdiff_t insert(size_t position, T item) @trusted @nogc 1338 { 1339 return insert(position, item); 1340 } 1341 1342 /** 1343 * Exchanges the positions of two items. 1344 * 1345 * Params: 1346 * item1 = The first item. 1347 * item2 = The second item. 1348 */ 1349 void swapItems(T item1, T item2) @trusted 1350 { 1351 void* _pld1 = getPayloadFromDt(item1); 1352 if (_pld1 == null) return; 1353 void* _pld2 = getPayloadFromDt(item2); 1354 if (_pld2 == null) return; 1355 1356 T _data1 = payload.getData(_pld1); 1357 T _data2 = payload.getData(_pld2); 1358 1359 payload.setData(_pld1, _data2); 1360 payload.setData(_pld2, _data1); 1361 } 1362 1363 /** 1364 * Exchanges the positions of two items. 1365 * 1366 * Params: 1367 * index1 = The first item index. 1368 * index2 = The second item index. 1369 */ 1370 void swapIndexes(size_t index1, size_t index2) @trusted 1371 { 1372 void* _pld1 = getPayloadFromIx(index1); 1373 if (_pld1 == null) return; 1374 void* _pld2 = getPayloadFromIx(index2); 1375 if (_pld2 == null) return; 1376 1377 T _data1 = payload.getData(_pld1); 1378 T _data2 = payload.getData(_pld2); 1379 1380 payload.setData(_pld1, _data2); 1381 payload.setData(_pld2, _data1); 1382 } 1383 1384 /** 1385 * Removes an item from the list. 1386 * 1387 * Params: 1388 * item = The item to remove. 1389 * Returns: 1390 * true if the item wasin the list, false otherwise. 1391 */ 1392 bool remove(T item) @trusted 1393 { 1394 void* _pld = getPayloadFromDt(item); 1395 if (!_pld) return false; 1396 1397 void* _prev = payload.getPrev(_pld); 1398 void* _next = payload.getNext(_pld); 1399 if (_last == _pld && _prev) 1400 { 1401 _last = _prev; 1402 payload.setNext(_last, null); 1403 _next = null; 1404 } 1405 else if (_first == _pld && _next) 1406 { 1407 _first = _next; 1408 payload.setPrev(_first, null); 1409 _prev = null; 1410 } 1411 else if (_prev && _next) 1412 { 1413 if (_prev) payload.setNext(_prev, _next); 1414 if (_next) payload.setPrev(_next, _prev); 1415 } 1416 payload.freePld(_pld); 1417 if (_last == _first && _last == _pld) 1418 { 1419 _last = null; 1420 _first = null; 1421 } 1422 --_count; 1423 return true; 1424 } 1425 1426 /** 1427 * Removes an item from the list. 1428 * 1429 * Params: 1430 * index = The index of the item to remove. 1431 * Returns: 1432 * The item that's been removed. 1433 */ 1434 T extract(size_t index) @trusted 1435 { 1436 T result; 1437 void* _pld = getPayloadFromIx(index); 1438 if (!_pld) return result; 1439 result = payload.getData(_pld); 1440 1441 void* _prev = payload.getPrev(_pld); 1442 void* _next = payload.getNext(_pld); 1443 if (_last == _pld && _prev) 1444 { 1445 _last = _prev; 1446 payload.setNext(_prev, null); 1447 _next = null; 1448 } 1449 else if (_first == _pld && _next) 1450 { 1451 _first = _next; 1452 payload.setPrev(_next, null); 1453 _prev = null; 1454 } 1455 else if (_prev && _next) 1456 { 1457 payload.setNext(_prev, _next); 1458 payload.setPrev(_next, _prev); 1459 } 1460 payload.freePld(_pld); 1461 if (_last == _first && _last == _pld) 1462 { 1463 _last = null; 1464 _first = null; 1465 } 1466 --_count; 1467 return result; 1468 } 1469 1470 /** 1471 * Empties the list. 1472 */ 1473 void clear() @trusted @nogc 1474 { 1475 void* current = _first; 1476 while (current) 1477 { 1478 void* _old = current; 1479 current = payload.getNext(current); 1480 payload.freePld(_old); 1481 } 1482 _count = 0; 1483 _first = null; 1484 _last = null; 1485 } 1486 1487 /** 1488 * Returns the items count. 1489 */ 1490 size_t count() @trusted @nogc 1491 { 1492 return _count; 1493 } 1494 1495 Range opSlice() 1496 { 1497 return Range(_first, _last); 1498 } 1499 1500 Range opSlice(size_t lo, size_t hi) @trusted 1501 { 1502 return Range(getPayloadFromIx(lo), getPayloadFromIx(hi)); 1503 } 1504 1505 alias length = count; 1506 1507 alias put = add; 1508 1509 private struct Range 1510 { 1511 private void* _begin; 1512 private void* _end; 1513 1514 private this(void* b, void* e) 1515 { 1516 _begin = b; 1517 _end = e; 1518 } 1519 1520 /** 1521 * Returns $(D true) if the range is _empty 1522 */ 1523 bool empty() const @property 1524 { 1525 return _begin is null; 1526 } 1527 1528 /** 1529 * Returns the first element in the range 1530 */ 1531 T front() @safe @nogc 1532 { 1533 return payload.getData(_begin); 1534 } 1535 1536 /** 1537 * Returns the last element in the range 1538 */ 1539 T back() @safe @nogc 1540 { 1541 return payload.getData(_end); 1542 } 1543 1544 /** 1545 * pop the front element from the range 1546 * 1547 * complexity: amortized $(BIGOH 1) 1548 */ 1549 void popFront() @safe @nogc 1550 { 1551 _begin = payload.getNext(_begin); 1552 } 1553 1554 /** 1555 * pop the back element from the range 1556 * 1557 * complexity: amortized $(BIGOH 1) 1558 */ 1559 void popBack() @safe @nogc 1560 { 1561 _end = payload.getPrev(_end); 1562 } 1563 1564 /** 1565 * Trivial _save implementation, needed for $(D isForwardRange). 1566 */ 1567 Range save() @safe @nogc 1568 { 1569 return this; 1570 } 1571 1572 size_t length() @safe @nogc 1573 { 1574 size_t result; 1575 auto cur = _begin; 1576 while (cur) 1577 { 1578 cur = payload.getNext(cur); 1579 ++result; 1580 } 1581 return result; 1582 } 1583 } 1584 } 1585 1586 unittest 1587 { 1588 struct S{int a,b; int notPod(){return a;}} 1589 class C{int a,b; int notPod(){return a;}} 1590 1591 void test(alias T )() 1592 { 1593 // struct as ptr 1594 alias SList = T!(S*); 1595 S[200] arrayOfS; 1596 SList sList = construct!SList; 1597 scope(exit) sList.destruct; 1598 1599 for (auto i = 0; i < arrayOfS.length; i++) 1600 { 1601 arrayOfS[i].a = i; 1602 sList.add( &arrayOfS[i] ); 1603 assert( sList[i] == &arrayOfS[i]); 1604 assert( sList.count == i + 1); 1605 assert( sList.find( &arrayOfS[i] ) == i); 1606 } 1607 1608 sList.swapIndexes(0,1); 1609 assert( sList.find(&arrayOfS[0]) == 1 ); 1610 assert( sList.find(&arrayOfS[1]) == 0 ); 1611 sList.swapIndexes(0,1); 1612 assert( sList.find(&arrayOfS[0]) == 0 ); 1613 assert( sList.find(&arrayOfS[1]) == 1 ); 1614 sList.remove(sList.last); 1615 assert( sList.count == arrayOfS.length -1 ); 1616 sList.clear; 1617 assert( sList.count == 0 ); 1618 for (auto i = 0; i < arrayOfS.length; i++) 1619 { 1620 sList.add( &arrayOfS[i] ); 1621 } 1622 sList.extract(50); 1623 assert( sList.find(&arrayOfS[50]) == -1 ); 1624 sList.insert(50,&arrayOfS[50]); 1625 assert( sList.find(&arrayOfS[50]) == 50 ); 1626 sList.extract(50); 1627 sList.insert(&arrayOfS[50]); 1628 assert( sList.find(&arrayOfS[50]) == 0 ); 1629 sList.clear; 1630 assert( sList.count == 0 ); 1631 for (auto i = 0; i < arrayOfS.length; i++) 1632 { 1633 sList.add( &arrayOfS[i] ); 1634 } 1635 1636 // class as ref 1637 alias CList = T!C; 1638 C[200] arrayOfC; 1639 CList cList = construct!CList; 1640 scope(exit) cList.destruct; 1641 1642 for (auto i = 0; i < arrayOfC.length; i++) 1643 { 1644 arrayOfC[i] = construct!C; 1645 arrayOfC[i].a = i; 1646 cList.add( arrayOfC[i] ); 1647 assert( cList[i] is arrayOfC[i]); 1648 assert( cList.count == i + 1); 1649 assert( cList.find( arrayOfC[i] ) == i); 1650 } 1651 cList.swapIndexes(0,1); 1652 assert( cList.find(arrayOfC[0]) == 1 ); 1653 assert( cList.find(arrayOfC[1]) == 0 ); 1654 cList.swapIndexes(0,1); 1655 assert( cList.find(arrayOfC[0]) == 0 ); 1656 assert( cList.find(arrayOfC[1]) == 1 ); 1657 cList.remove(cList.last); 1658 assert( cList.count == arrayOfC.length -1 ); 1659 cList.clear; 1660 assert( cList.count == 0 ); 1661 for (auto i = 0; i < arrayOfC.length; i++) 1662 { 1663 cList.add( arrayOfC[i] ); 1664 } 1665 cList.extract(50); 1666 assert( cList.find(arrayOfC[50]) == -1 ); 1667 cList.insert(50,arrayOfC[50]); 1668 assert( cList.find(arrayOfC[50]) == 50 ); 1669 cList.extract(50); 1670 cList.insert(arrayOfC[50]); 1671 assert( cList.find(arrayOfC[50]) == 0 ); 1672 cList.clear; 1673 assert( cList.count == 0 ); 1674 for (auto i = 0; i < arrayOfC.length; i++) 1675 { 1676 cList.add( arrayOfC[i] ); 1677 } 1678 1679 // cleanup of internally allocated items. 1680 C itm; 1681 cList.clear; 1682 assert(cList.count == 0); 1683 cList.addNewItem; 1684 cList.addNewItem; 1685 assert(cList.count == 2); 1686 1687 itm = cList.extract(0); 1688 assert(itm); 1689 itm.destruct; 1690 assert(cList.count == 1); 1691 itm = cList.extract(0); 1692 assert(itm); 1693 itm.destruct; 1694 assert(cList.count == 0); 1695 1696 cList.add(arrayOfC[0]); 1697 cList[0] = arrayOfC[1]; 1698 assert(cList.find(arrayOfC[0]) == -1); 1699 assert(cList.find(arrayOfC[1]) == 0); 1700 cList.clear; 1701 1702 cList = arrayOfC[10..20]; 1703 assert(cList.count == 10); 1704 assert(cList[0] == arrayOfC[10]); 1705 assert(cList[9] == arrayOfC[19]); 1706 1707 cList.clear; 1708 cList.insert(0, arrayOfC[24]); 1709 assert(cList[0] == arrayOfC[24]); 1710 cList.insert(123456, arrayOfC[25]); 1711 assert(cList.count == 2); 1712 assert(cList[1] == arrayOfC[25]); 1713 cList.swapItems(arrayOfC[24],arrayOfC[25]); 1714 assert(cList[0] == arrayOfC[25]); 1715 assert(cList[1] == arrayOfC[24]); 1716 cList.swapIndexes(0,1); 1717 assert(cList[0] == arrayOfC[24]); 1718 assert(cList[1] == arrayOfC[25]); 1719 C elem = cList.extract(1); 1720 assert(elem is arrayOfC[25]); 1721 assert(cList.count == 1); 1722 1723 size_t i; 1724 cList = arrayOfC[0..10]; 1725 foreach (C c; cList) 1726 { 1727 assert(c is arrayOfC[i]); 1728 ++i; 1729 } 1730 foreach_reverse(C c; cList) 1731 { 1732 --i; 1733 assert(c is arrayOfC[i]); 1734 } 1735 assert(cList.first == arrayOfC[0]); 1736 assert(cList.last == arrayOfC[9]); 1737 1738 cList.clear; 1739 cList.add(arrayOfC[0..10]); 1740 assert(cList.count == 10); 1741 assert(cList.first == arrayOfC[0]); 1742 assert(cList.last == arrayOfC[9]); 1743 1744 foreach(o; arrayOfC) 1745 destruct(o); 1746 } 1747 1748 test!(ContiguousList); 1749 test!(DynamicList); 1750 } 1751 1752 unittest 1753 { 1754 alias List = DynamicList!(Array!int); 1755 Array!int a; 1756 Array!int b = [2,3]; 1757 List lst = construct!List(); 1758 lst.add(a); 1759 lst.add(b); 1760 assert(lst[0].ptr !is a.ptr); 1761 destructEach(a,b, lst); 1762 } 1763 1764 /** 1765 * TreeItemSiblings is an input range that allows to 1766 * iterate the children of a TreeItem. 1767 */ 1768 struct TreeItemChildren(T) 1769 { 1770 1771 private: 1772 1773 T _front; 1774 1775 public: 1776 1777 /// See $(D initialize()). 1778 this(TT)(auto ref TT t) 1779 if (is(TT == T)) 1780 { 1781 initialize(t); 1782 } 1783 1784 /// Initializes the range from a parent. 1785 void initialize(TT)(auto ref TT t) 1786 if (is(TT == T)) 1787 { 1788 _front = t.firstChild; 1789 } 1790 1791 /// 1792 ref T front() 1793 { 1794 return _front; 1795 } 1796 1797 /// 1798 void popFront() 1799 { 1800 _front = _front.nextSibling; 1801 } 1802 1803 /// 1804 bool empty() 1805 { 1806 return _front is null; 1807 } 1808 1809 /** 1810 * Support for the array syntax. 1811 * Should be avoided in for() loops. 1812 */ 1813 T opIndex(ptrdiff_t index) 1814 in 1815 { 1816 assert(_front); 1817 } 1818 body 1819 { 1820 T result = _front; 1821 ptrdiff_t cnt; 1822 while (true) 1823 { 1824 if (cnt++ == index || !result) 1825 return result; 1826 result = result.nextSibling; 1827 } 1828 } 1829 1830 /// Support the array syntax. 1831 void opIndexAssign(T item, size_t i) 1832 in 1833 { 1834 assert(_front); 1835 assert(item); 1836 } 1837 body 1838 { 1839 auto old = opIndex(i); 1840 if (!old) 1841 _front.addSibling(item); 1842 else 1843 { 1844 if (_front.findSibling(item) != -1) 1845 _front.exchangeSibling(item,old); 1846 else 1847 { 1848 _front.removeSibling(old); 1849 _front.insertSibling(i,item); 1850 } 1851 } 1852 } 1853 } 1854 1855 /** 1856 * TreeItemSiblings is an input range that allows to 1857 * iterate over the siblings of a TreeItem. 1858 */ 1859 struct TreeItemSiblings(T) 1860 { 1861 1862 private: 1863 1864 T _front; 1865 1866 public: 1867 1868 /// See $(D initialize()). 1869 this(TT)(auto ref TT t) 1870 if (is(TT == T)) 1871 { 1872 initialize(t); 1873 } 1874 1875 /// Initializes the range from one of the siblings. 1876 void initialize(TT)(auto ref TT t) 1877 if (is(TT == T)) 1878 { 1879 TT tt =t; 1880 if (tt.parent) 1881 _front = tt.parent.firstChild; 1882 else 1883 { 1884 while (tt.prevSibling !is null) 1885 { 1886 tt = tt.prevSibling; 1887 } 1888 _front = tt; 1889 } 1890 } 1891 1892 /// 1893 T front() @safe @nogc 1894 { 1895 return _front; 1896 } 1897 1898 /// 1899 void popFront() 1900 { 1901 _front = _front.nextSibling; 1902 } 1903 1904 /// 1905 bool empty() @safe @nogc 1906 { 1907 return _front is null; 1908 } 1909 1910 /** 1911 * Support for the array syntax. 1912 * Should be avoided in for loops. 1913 */ 1914 T opIndex(ptrdiff_t index) 1915 in 1916 { 1917 assert(_front); 1918 } 1919 body 1920 { 1921 T result = _front; 1922 ptrdiff_t cnt; 1923 while (true) 1924 { 1925 if (cnt++ == index || !result) 1926 return result; 1927 result = result.nextSibling; 1928 } 1929 } 1930 1931 /// Support for the array syntax. 1932 void opIndexAssign(T item, size_t i) 1933 in 1934 { 1935 assert(_front); 1936 } 1937 body 1938 { 1939 if (!item) 1940 _front.removeSibling(i); 1941 else 1942 { 1943 auto old = opIndex(i); 1944 if (!old) 1945 _front.addSibling(item); 1946 else 1947 { 1948 if (_front.findSibling(item) != -1) 1949 _front.exchangeSibling(item,old); 1950 else 1951 { 1952 _front.removeSibling(old); 1953 _front.insertSibling(i,item); 1954 } 1955 } 1956 } 1957 } 1958 } 1959 1960 /** 1961 * The TreeItem mixin turns its target into a tree item. 1962 */ 1963 mixin template TreeItem() 1964 { 1965 1966 protected: 1967 1968 import iz.memory: construct, destruct; 1969 1970 enum isStruct = is(typeof(this) == struct); 1971 static if (isStruct) 1972 alias TreeItemType = typeof(this)*; 1973 else 1974 alias TreeItemType = typeof(this); 1975 1976 TreeItemType _prevSibling, _nextSibling, _firstChild, _parent; 1977 TreeItemSiblings!TreeItemType _siblings; 1978 TreeItemChildren!TreeItemType _children; 1979 1980 import iz.streams: Stream, writeArray; 1981 1982 public: 1983 1984 /// Returns $(D this) when mixed in a class or $(D &this) in a struct. 1985 TreeItemType self() 1986 { 1987 static if (isStruct) 1988 return &this; 1989 else 1990 return this; 1991 } 1992 1993 /** 1994 * Returns the previous TreeItem. 1995 */ 1996 TreeItemType prevSibling() 1997 { 1998 return _prevSibling; 1999 } 2000 2001 /** 2002 * Returns the next TreeItem. 2003 */ 2004 TreeItemType nextSibling() 2005 { 2006 return _nextSibling; 2007 } 2008 2009 /** 2010 * Returns the parent. 2011 */ 2012 TreeItemType parent() 2013 { 2014 return _parent; 2015 } 2016 2017 /** 2018 * Returns the first child. 2019 */ 2020 TreeItemType firstChild() 2021 { 2022 return _firstChild; 2023 } 2024 2025 /** 2026 * Returns an input range that allows to iterate the siblings. 2027 * The array syntax is also supported. 2028 */ 2029 TreeItemSiblings!TreeItemType siblings() 2030 { 2031 _siblings.initialize(self); 2032 return _siblings; 2033 } 2034 2035 /** 2036 * Returns an input range that allows to iterate the children. 2037 * The array syntax is also supported. 2038 */ 2039 TreeItemChildren!TreeItemType children() 2040 { 2041 _children.initialize(self); 2042 return _children; 2043 } 2044 2045 // siblings -------------------------------------------------------------------+ 2046 2047 /** 2048 * Constructs, adds to the back then returns a new sibling. 2049 * This method should be prefered over addChild and insertChild 2050 * if $(D deleteChildren()) is used. 2051 * 2052 * When TreeItem is mixed in a class a template parameter that specifies 2053 * the class type to return must be present, otherwise in both cases the 2054 * function passes the optional run-time parameters to the constructor. 2055 */ 2056 static if (is(TreeItemType == class)) 2057 { 2058 IT addNewSibling(IT,A...)(A a) 2059 if (is(IT : TreeItemType)) 2060 { 2061 auto result = construct!IT(a); 2062 addSibling(result); 2063 return result; 2064 } 2065 } 2066 else 2067 { 2068 TreeItemType addNewSibling(A...)(A a) 2069 { 2070 TreeItemType result = construct!(typeof(this))(a); 2071 addSibling(result); 2072 return result; 2073 } 2074 } 2075 2076 /** 2077 * Returns the last item. 2078 * The value returned is never null. 2079 */ 2080 TreeItemType lastSibling() 2081 { 2082 TreeItemType result; 2083 result = self; 2084 while (result.nextSibling) 2085 { 2086 result = result.nextSibling; 2087 } 2088 return result; 2089 } 2090 2091 /** 2092 * Returns the first item. 2093 * The value returned is never null. 2094 */ 2095 TreeItemType firstSibling() 2096 { 2097 if (_parent) 2098 return _parent._firstChild; 2099 else 2100 { 2101 TreeItemType result; 2102 result = self; 2103 while (result.prevSibling) 2104 { 2105 result = result.prevSibling; 2106 } 2107 return result; 2108 } 2109 } 2110 2111 /** 2112 * Returns the index of sibling if it's found otherwise -1. 2113 */ 2114 ptrdiff_t findSibling(TreeItemType sibling) 2115 in 2116 { 2117 assert(sibling); 2118 } 2119 body 2120 { 2121 auto current = self; 2122 while (current) 2123 { 2124 if (current is sibling) break; 2125 current = current.prevSibling; 2126 } 2127 if (!current) 2128 { 2129 current = self; 2130 while (current) 2131 { 2132 if (current is sibling) break; 2133 current = current.nextSibling; 2134 } 2135 } 2136 if (!current) return -1; 2137 return current.siblingIndex; 2138 } 2139 2140 /** 2141 * Adds an item at the end of list. 2142 */ 2143 void addSibling(TreeItemType sibling) 2144 in 2145 { 2146 assert(sibling); 2147 } 2148 body 2149 { 2150 if (sibling.hasSibling) 2151 { 2152 if (sibling.prevSibling !is null) 2153 sibling.prevSibling.removeSibling(sibling); 2154 else 2155 sibling.nextSibling.removeSibling(sibling); 2156 } 2157 2158 auto oldlast = lastSibling; 2159 assert(oldlast); 2160 oldlast._nextSibling = sibling; 2161 sibling._prevSibling = oldlast; 2162 sibling._nextSibling = null; 2163 sibling._parent = parent; 2164 } 2165 2166 /** 2167 * Inserts an item at the beginning of the list. 2168 */ 2169 void insertSibling(TreeItemType sibling) 2170 in 2171 { 2172 assert(sibling); 2173 } 2174 body 2175 { 2176 if (sibling.hasSibling) 2177 { 2178 if (sibling.prevSibling !is null) 2179 sibling.prevSibling.removeSibling(sibling); 2180 else 2181 sibling.nextSibling.removeSibling(sibling); 2182 } 2183 2184 auto oldfirst = firstSibling; 2185 assert(oldfirst); 2186 oldfirst._prevSibling = sibling; 2187 sibling._nextSibling = oldfirst; 2188 sibling._parent = parent; 2189 2190 if (parent) 2191 { 2192 parent._firstChild = sibling; 2193 } 2194 } 2195 2196 /** 2197 * Inserts a sibling. 2198 * 2199 * Params: 2200 * index = The position where to insert. 2201 * sibling = the item to insert. 2202 */ 2203 void insertSibling(size_t index, TreeItemType sibling) 2204 in 2205 { 2206 assert(sibling); 2207 } 2208 body 2209 { 2210 if (sibling.hasSibling) 2211 { 2212 if (sibling.prevSibling !is null) 2213 sibling.prevSibling.removeSibling(sibling); 2214 else 2215 sibling.nextSibling.removeSibling(sibling); 2216 } 2217 2218 const size_t cnt = siblingCount; 2219 if (index == 0) insertSibling(sibling); 2220 else if (index >= cnt) addSibling(sibling); 2221 else 2222 { 2223 size_t result = 1; 2224 auto old = firstSibling; 2225 while (old) 2226 { 2227 if (result == index) 2228 { 2229 auto item1oldprev = old.prevSibling; 2230 auto item1oldnext = old.nextSibling; 2231 sibling._prevSibling = old; 2232 sibling._nextSibling = item1oldnext; 2233 old._nextSibling = sibling; 2234 item1oldnext._prevSibling = sibling; 2235 sibling._parent = _parent; 2236 assert(sibling.siblingIndex == index); 2237 2238 return; 2239 } 2240 old = old.nextSibling; 2241 result++; 2242 } 2243 } 2244 } 2245 2246 /** 2247 * Exchanges the position of two siblings. 2248 */ 2249 void exchangeSibling(TreeItemType sibling1, TreeItemType sibling2) 2250 in 2251 { 2252 assert(sibling1); 2253 assert(sibling2); 2254 assert(sibling1._parent is sibling2._parent); 2255 } 2256 body 2257 { 2258 auto item1oldprev = sibling1._prevSibling; 2259 auto item1oldnext = sibling1._nextSibling; 2260 auto item2oldprev = sibling2._prevSibling; 2261 auto item2oldnext = sibling2._nextSibling; 2262 const bool contiguous = item2oldprev == sibling1 || item1oldprev == sibling2; 2263 2264 if (!contiguous) 2265 { 2266 sibling1._prevSibling = item2oldprev; 2267 sibling1._nextSibling = item2oldnext; 2268 sibling2._prevSibling = item1oldprev; 2269 sibling2._nextSibling = item1oldnext; 2270 if (item1oldprev) item1oldprev._nextSibling = sibling2; 2271 if (item1oldnext) item1oldnext._prevSibling = sibling2; 2272 if (item2oldprev) item2oldprev._nextSibling = sibling1; 2273 if (item2oldnext) item2oldnext._prevSibling = sibling1; 2274 } 2275 else 2276 { 2277 if (item1oldnext is sibling2) 2278 { 2279 sibling1._prevSibling = sibling2; 2280 sibling1._nextSibling = item2oldnext; 2281 sibling2._nextSibling = sibling1; 2282 sibling2._prevSibling = item1oldprev; 2283 } 2284 else 2285 { 2286 sibling2._prevSibling = sibling1; 2287 sibling2._nextSibling = item1oldnext; 2288 sibling1._nextSibling = sibling2; 2289 sibling1._prevSibling = item2oldprev; 2290 } 2291 } 2292 2293 if (sibling1._parent && sibling1._parent.firstChild is sibling1) 2294 { 2295 sibling1._parent._firstChild = sibling2; 2296 } 2297 else if (sibling2._parent && sibling2._parent.firstChild is sibling2) 2298 { 2299 sibling2._parent._firstChild = sibling1; 2300 } 2301 } 2302 2303 /** 2304 * Removes an item. 2305 * 2306 * Params: 2307 * sibling = The item to remove. 2308 * Returns: 2309 * true if the item is a sibling otherwise false. 2310 */ 2311 bool removeSibling(TreeItemType sibling) 2312 { 2313 if (!sibling || (sibling.parent && sibling.parent != parent)) 2314 return false; 2315 2316 TreeItemType oldprev = sibling._prevSibling; 2317 TreeItemType oldnext = sibling._nextSibling; 2318 if (oldprev) oldprev._nextSibling = oldnext; 2319 if (oldnext) oldnext._prevSibling = oldprev; 2320 2321 if (parent && parent.firstChild is sibling) 2322 { 2323 parent._firstChild = oldnext; 2324 } 2325 2326 sibling._prevSibling = null; 2327 sibling._nextSibling = null; 2328 sibling._parent = null; 2329 2330 return true; 2331 } 2332 2333 /** 2334 * Removes the nth sibling. 2335 * 2336 * Params: 2337 * index = the index of the sibling to remove. 2338 * Returns: 2339 * The item if the index is valid, otherwise null. 2340 */ 2341 TreeItemType removeSibling(size_t index) 2342 { 2343 TreeItemType result = siblings[index]; 2344 if (result) 2345 { 2346 TreeItemType oldprev = result._prevSibling; 2347 TreeItemType oldnext = result._nextSibling; 2348 if (oldprev) oldprev._nextSibling = oldnext; 2349 if (oldnext) oldnext._prevSibling = oldprev; 2350 2351 if (parent && parent.firstChild is result) 2352 { 2353 parent._firstChild = result._nextSibling; 2354 } 2355 2356 result._prevSibling = null; 2357 result._nextSibling = null; 2358 result._parent = null; 2359 } 2360 return result; 2361 } 2362 2363 /** 2364 * Returns the count of sibling in the branch. 2365 * The value returned is always greater than 0. 2366 */ 2367 size_t siblingCount() 2368 { 2369 size_t toFront, toBack; 2370 auto current = self; 2371 while (current) 2372 { 2373 current = current._prevSibling; 2374 toFront++; 2375 } 2376 current = self; 2377 while (current) 2378 { 2379 current = current._nextSibling; 2380 toBack++; 2381 } 2382 return toFront + toBack -1; 2383 } 2384 2385 /** 2386 * Returns the item position in the list. 2387 */ 2388 ptrdiff_t siblingIndex() 2389 { 2390 ptrdiff_t result = -1; 2391 TreeItemType current = self; 2392 while (current) 2393 { 2394 current = current._prevSibling; 2395 result++; 2396 } 2397 return result; 2398 } 2399 2400 /** 2401 * Sets the item position in the list. 2402 * The new position of the previous item is undetermined. 2403 */ 2404 void siblingIndex(size_t position) 2405 { 2406 TreeItemType old = siblings[position]; 2407 if (old !is self) 2408 { 2409 TreeItemType prt = _parent; 2410 removeSibling(self); 2411 old.insertSibling(position, self); 2412 _parent = prt; 2413 } 2414 } 2415 2416 /** 2417 * Indicates if the item has neighboors. 2418 */ 2419 bool hasSibling() 2420 { 2421 return prevSibling !is null || nextSibling !is null; 2422 } 2423 2424 // ----------------------------------------------------------------------------- 2425 // children -------------------------------------------------------------------+ 2426 2427 /** 2428 * Constructs, adds to the back then returns a new child. 2429 * This method should be prefered over addChild and insertChild 2430 * if $(D deleteChildren()) is used. 2431 * 2432 * When TreeItem is mixed in a class a template parameter that specifies 2433 * the class type to return must be present, otherwise in both cases the 2434 * function passes the optional run-time parameters to the constructor. 2435 */ 2436 static if (is(TreeItemType == class)) 2437 { 2438 IT addNewChild(IT,A...)(A a) 2439 if (is(IT : TreeItemType)) 2440 { 2441 auto result = construct!IT(a); 2442 addChild(result); 2443 return result; 2444 } 2445 } 2446 else 2447 { 2448 TreeItemType addNewChild(A...)(A a) 2449 { 2450 TreeItemType result = construct!(typeof(this))(a); 2451 addChild(result); 2452 return result; 2453 } 2454 } 2455 2456 /** 2457 * Returns the distance to the root. 2458 */ 2459 size_t level() 2460 { 2461 size_t result; 2462 auto current = self; 2463 while (current._parent) 2464 { 2465 current = current._parent; 2466 result++; 2467 } 2468 return result; 2469 } 2470 2471 /** 2472 * Returns the root. 2473 */ 2474 TreeItemType root() 2475 { 2476 auto current = self; 2477 while (current._parent) 2478 current = current._parent; 2479 return current; 2480 } 2481 2482 /** 2483 * Returns the children count. 2484 */ 2485 size_t childrenCount() 2486 { 2487 if ( _firstChild is null) 2488 return 0; 2489 else 2490 return _firstChild.siblingCount; 2491 } 2492 2493 /** 2494 * Adds child to the back. 2495 */ 2496 void addChild(TreeItemType child) 2497 { 2498 if (child.parent) 2499 { 2500 if (child.parent !is self) 2501 child.parent.removeChild(child); 2502 else 2503 return; 2504 } 2505 if (!_firstChild) 2506 { 2507 _firstChild = child; 2508 child._parent = self; 2509 return; 2510 } 2511 else _firstChild.addSibling(child); 2512 } 2513 2514 /** 2515 * Inserts the first child. 2516 */ 2517 void insertChild(TreeItemType child) 2518 { 2519 if (!_firstChild) 2520 { 2521 _firstChild = child; 2522 child._parent = self; 2523 return; 2524 } 2525 else _firstChild.insertSibling(child); 2526 } 2527 2528 /** 2529 * Inserts a child. 2530 * 2531 * Params: 2532 * index = The position in the children list. 2533 * child = The child to insert. 2534 */ 2535 void insertChild(size_t index, TreeItemType child) 2536 in 2537 { 2538 assert(child); 2539 } 2540 body 2541 { 2542 if (!_firstChild) 2543 { 2544 _firstChild = child; 2545 child._parent = self; 2546 return; 2547 } 2548 else _firstChild.insertSibling(index, child); 2549 } 2550 2551 /** 2552 * Removes a child from the list. 2553 * 2554 * Params: 2555 * child = The child to remove. 2556 * Returns: 2557 * true if child is removed. 2558 */ 2559 bool removeChild(TreeItemType child) 2560 in 2561 { 2562 assert(child); 2563 } 2564 body 2565 { 2566 ptrdiff_t i = -1; 2567 if (_firstChild) 2568 { 2569 i = firstChild.findSibling(child); 2570 if (i != -1) removeChild(i); 2571 } 2572 return i != -1; 2573 } 2574 2575 /** 2576 * Removes the nth child. 2577 * 2578 * Params: 2579 * index = The child index. 2580 * Returns: 2581 * The child if index was valid, otherwise null. 2582 */ 2583 TreeItemType removeChild(size_t index) 2584 in 2585 { 2586 assert(index >= 0); 2587 } 2588 body 2589 { 2590 TreeItemType result = children[index]; 2591 if (result) 2592 { 2593 if (index > 0) 2594 result.prevSibling.removeSibling(index); 2595 else 2596 { 2597 if (result.siblingCount == 1) 2598 { 2599 result._parent = null; 2600 _firstChild = null; 2601 } 2602 else 2603 result._nextSibling.removeSibling(index); 2604 } 2605 } 2606 return result; 2607 } 2608 2609 /** 2610 * Removes the children, without destructing them. 2611 * After the call, the links to the items siblings are also reset to null. 2612 */ 2613 void removeChildren() 2614 { 2615 auto current = _firstChild; 2616 while (current) 2617 { 2618 current.removeChildren; 2619 2620 auto _next = current.nextSibling; 2621 current._parent = null; 2622 current._prevSibling = null; 2623 current._nextSibling = null; 2624 current = _next; 2625 } 2626 _firstChild = null; 2627 } 2628 2629 /** 2630 * Removes and deletes (destroy) the children. 2631 * 2632 * This method should be used in pair with $(D addNewChild()) and 2633 * $(D addNewSiblings()). If $(D add()) or $(D insert()) have been used to 2634 * build the tree then initial references will be dangling. 2635 */ 2636 void deleteChildren() 2637 { 2638 while (_firstChild) 2639 { 2640 auto current = _firstChild; 2641 _firstChild = current.nextSibling; 2642 2643 current.deleteChildren; 2644 current._parent = null; 2645 current._nextSibling = null; 2646 current._prevSibling = null; 2647 static if (is(TreeItemType == interface) || is(TreeItemType == class)) 2648 destruct(cast(Object) current); 2649 else 2650 destruct(current); 2651 } 2652 } 2653 // ----------------------------------------------------------------------------- 2654 // other ----------------------------------------------------------------------+ 2655 2656 /** 2657 * Converts the node to a string. 2658 * This is used to represent the whole tree in $(D saveToStream()). 2659 */ 2660 char[] itemToTextNative() 2661 { 2662 import std.format: format; 2663 char[] result; 2664 foreach (immutable i; 0 .. level) result ~= '\t'; 2665 result ~= format( "Index: %.4d - NodeType: %s", siblingIndex, typeof(this).stringof); 2666 return result; 2667 } 2668 2669 /** 2670 * Saves the textual representation of the tree to a Stream. 2671 * 2672 * Params: 2673 * stream = The Stream where items are written. 2674 * itemToText = A custom function to render the items. When not specified, 2675 * $(D itemToTextNative()) is used. 2676 */ 2677 void saveToStream(Stream stream, string function(TreeItemType) itemToText = null) 2678 { 2679 char[] txt; 2680 if (itemToText) 2681 txt = itemToText(self).dup; 2682 else 2683 txt = itemToTextNative ~ "\r\n"; 2684 writeArray!false(stream, txt); 2685 foreach (c; children) 2686 c.saveToStream(stream, itemToText); 2687 } 2688 // ----------------------------------------------------------------------------- 2689 } 2690 2691 /** 2692 * Helper class template that implements TreeItem in a C descendant. 2693 */ 2694 class TreeItemClass(C): C 2695 if (is(C==class)) 2696 { 2697 mixin inheritedDtor; 2698 mixin TreeItem; 2699 } 2700 2701 /// Alias to the most simple TreeItem class type. 2702 alias ObjectTreeItem = TreeItemClass!Object; 2703 2704 /** 2705 * Helper struct template that implements TreeItem in a struct. 2706 * 2707 * Params: 2708 * fieldsAndFuncs = The struct declarations, as a string to mix. 2709 */ 2710 struct TreeItemStruct(string fieldsAndFuncs) 2711 { 2712 mixin(fieldsAndFuncs); 2713 mixin TreeItem; 2714 } 2715 2716 /// Alias to the most simple TreeItem struct type. 2717 alias StructTreeItem = TreeItemStruct!q{public void* data;}; 2718 2719 unittest 2720 { 2721 ObjectTreeItem[20] items; 2722 ObjectTreeItem root; 2723 2724 items[0] = construct!ObjectTreeItem; 2725 root = items[0]; 2726 for (auto i =1; i < items.length; i++) 2727 { 2728 items[i] = construct!ObjectTreeItem; 2729 if (i>0) root.addSibling( items[i] ); 2730 assert( items[i].siblingIndex == i ); 2731 assert( root.siblings[i].siblingIndex == i ); 2732 assert( root.siblings[i] == items[i] ); 2733 if (i>0) assert( items[i].prevSibling.siblingIndex == i-1 ); 2734 assert(root.lastSibling.siblingIndex == i); 2735 } 2736 assert(root.siblingCount == items.length); 2737 2738 assert(items[1].nextSibling.siblingIndex == 2); 2739 assert(items[1].prevSibling.siblingIndex == 0); 2740 2741 root.exchangeSibling(items[10],items[16]); 2742 assert(root.siblingCount == items.length); 2743 assert( items[10].siblingIndex == 16); 2744 assert( items[16].siblingIndex == 10); 2745 2746 root.exchangeSibling(items[10],items[16]); 2747 assert(root.siblingCount == items.length); 2748 assert( items[10].siblingIndex == 10); 2749 assert( items[16].siblingIndex == 16); 2750 2751 2752 items[8].siblingIndex = 4; 2753 assert( items[8].siblingIndex == 4); 2754 //assert( ObjectTreeItems[4].siblingIndex == 5); // when siblingIndex() calls remove/insert 2755 //assert( ObjectTreeItems[4].siblingIndex == 8); // when siblingIndex() calls exchangeSibling. 2756 2757 assert( root.siblings[16] == items[16]); 2758 assert( root.siblings[10] == items[10]); 2759 root.siblings[16] = items[10]; // exchg 2760 assert(root.siblingCount == items.length); 2761 root.siblings[16] = items[16]; // exchg 2762 assert(root.siblingCount == items.length); 2763 assert( items[16].siblingIndex == 16); 2764 assert( items[10].siblingIndex == 10); 2765 2766 ObjectTreeItem c = construct!ObjectTreeItem; 2767 root.siblings[10] = c; 2768 root.siblings[16] = items[10]; 2769 assert( items[16].siblingIndex == 0); 2770 assert( items[10].siblingIndex == 16); 2771 assert( c.siblingIndex == 10); 2772 2773 assert(root.findSibling(items[18]) > -1); 2774 assert(root.findSibling(items[0]) > -1); 2775 2776 foreach (item; root.siblings) 2777 { 2778 assert(root.findSibling(item) == item.siblingIndex); 2779 } 2780 2781 root.removeSibling(19); 2782 assert(root.siblingCount == items.length -1); 2783 root.removeSibling(18); 2784 assert(root.siblingCount == items.length -2); 2785 root.removeSibling(items[13]); 2786 assert(root.siblingCount == items.length -3); 2787 //root1[0] = null; // exception because root1[0] = root1 2788 assert(root.siblingCount == items.length -3); 2789 root.siblings[1] = null; 2790 assert(root.siblingCount == items.length -4); 2791 2792 foreach(o; items) 2793 destruct(o); 2794 destruct(c); 2795 } 2796 2797 unittest 2798 { 2799 ObjectTreeItem root; 2800 ObjectTreeItem[20] items1; 2801 ObjectTreeItem[4][20] items2; 2802 2803 root = construct!ObjectTreeItem; 2804 assert(root.level == 0); 2805 for (auto i=0; i < items1.length; i++) 2806 { 2807 items1[i] = construct!ObjectTreeItem; 2808 root.addChild(items1[i]); 2809 assert(root.childrenCount == 1 + i); 2810 assert(items1[i].parent is root); 2811 assert(items1[i].siblingCount == 1 + i); 2812 assert(items1[i].level == 1); 2813 assert(items1[i].siblingIndex == i); 2814 } 2815 root.removeChildren; 2816 assert(root.childrenCount == 0); 2817 for (auto i=0; i < items1.length; i++) 2818 { 2819 root.addChild(items1[i]); 2820 assert(items1[i].siblingIndex == i); 2821 } 2822 2823 for (auto i = 0; i < items2.length; i++) 2824 for (auto j = 0; j < items2[i].length; j++) 2825 { 2826 items2[i][j] = construct!ObjectTreeItem; 2827 items1[i].addChild(items2[i][j]); 2828 assert(items2[i][j].level == 2); 2829 assert(items1[i].childrenCount == 1 + j); 2830 assert(items2[i][j].siblingCount == 1 + j); 2831 } 2832 2833 root.deleteChildren; 2834 /* 2835 // this is an expected behavior: 2836 2837 // original refs are dangling 2838 assert( items1[12] is null); 2839 assert( items2[12][0] is null); 2840 assert( items2[18][3] is null); 2841 // A.V: 'cause the items are destroyed 2842 writeln( items1[12].level ); 2843 */ 2844 2845 root.addNewChild!ObjectTreeItem(); 2846 root.children[0].addNewChild!ObjectTreeItem(); 2847 root.children[0].addNewChild!ObjectTreeItem(); 2848 root.children[0].addNewChild!ObjectTreeItem(); 2849 root.addNewChild!ObjectTreeItem(); 2850 root.children[1].addNewChild!ObjectTreeItem(); 2851 root.children[1].addNewChild!ObjectTreeItem(); 2852 root.children[1].addNewChild!ObjectTreeItem(); 2853 root.children[1].addNewChild!ObjectTreeItem(); 2854 root.children[1].children[3].addNewChild!ObjectTreeItem(); 2855 root.children[1].children[3].addNewChild!ObjectTreeItem(); 2856 root.children[1].children[3].addNewChild!ObjectTreeItem(); 2857 2858 assert(root.childrenCount == 2); 2859 assert(root.children[0].childrenCount == 3); 2860 assert(root.children[1].childrenCount == 4); 2861 assert(root.children[1].children[3].childrenCount == 3); 2862 assert(root.children[1].children[3].children[0].level == 3); 2863 2864 assert(root.children[1].children[3].children[0].root is root); 2865 assert(root.children[1].children[3].root is root); 2866 2867 auto str = construct!MemoryStream; 2868 root.saveToStream(str); 2869 //str.saveToFile("treenodes.txt"); 2870 str.destruct; 2871 root.deleteChildren; 2872 destruct(root); 2873 } 2874 2875 unittest 2876 { 2877 ObjectTreeItem root = construct!ObjectTreeItem; 2878 ObjectTreeItem c0 = root.addNewChild!ObjectTreeItem; 2879 ObjectTreeItem c1 = root.addNewChild!ObjectTreeItem; 2880 ObjectTreeItem c2 = root.addNewChild!ObjectTreeItem; 2881 2882 scope(exit) destructEach(root, c0, c1, c2); 2883 2884 assert(root.childrenCount == 3); 2885 root.removeChild(c0); 2886 assert(root.childrenCount == 2); 2887 root.removeChild(c1); 2888 assert(root.childrenCount == 1); 2889 root.removeChild(c2); 2890 assert(root.childrenCount == 0); 2891 root.removeChild(c2); 2892 assert(root.childrenCount == 0); 2893 } 2894 2895 unittest 2896 { 2897 alias ItemStruct = TreeItemStruct!"uint a;"; 2898 2899 ItemStruct* root = construct!ItemStruct; 2900 2901 auto c0 = root.addNewChild; 2902 auto c1 = root.addNewChild; 2903 auto c2 = root.addNewChild; 2904 2905 scope(exit) destructEach(root, c0, c1, c2); 2906 2907 assert(root.childrenCount == 3); 2908 root.removeChild(0); 2909 assert(root.childrenCount == 2); 2910 root.removeChild(0); 2911 assert(root.childrenCount == 1); 2912 root.removeChild(0); 2913 assert(root.childrenCount == 0); 2914 2915 root.addChild(c0); 2916 root.addChild(c1); 2917 root.addChild(c2); 2918 assert(root.childrenCount == 3); 2919 root.removeChild(0); 2920 assert(root.childrenCount == 2); 2921 root.insertChild(c0); 2922 assert(root.childrenCount == 3); 2923 assert(root.children[0] == c0); 2924 root.removeChild(1); 2925 assert(c1.parent == null); 2926 assert(root.childrenCount == 2); 2927 root.insertChild(1, c1); 2928 assert(root.childrenCount == 3); 2929 root.removeChild(1); 2930 assert(root.childrenCount == 2); 2931 assert(c1.parent == null); 2932 root.insertChild(1, c1); 2933 assert(root.childrenCount == 3); 2934 assert(root.children[1] == c1); 2935 2936 assert(root.children[0] == c0); 2937 assert(root.children[1] == c1); 2938 assert(root.children[2] == c2); 2939 2940 c2.exchangeSibling(c0,c1); 2941 assert(root.firstChild == c1); 2942 assert(root.children[0] == c1); 2943 assert(root.children[1] == c0); 2944 assert(root.children[2] == c2); 2945 c2.exchangeSibling(c0,c1); 2946 assert(root.firstChild == c0); 2947 root.removeChild(c2); 2948 c0.insertSibling(c2); 2949 assert(root.firstChild == c2); 2950 2951 root.removeChildren; 2952 root.addChild(c0); 2953 root.addChild(c1); 2954 root.addChild(c2); 2955 auto r = root.children; 2956 assert(r.front == c0); 2957 r.popFront; 2958 assert(r.front == c1); 2959 r.popFront; 2960 assert(r.front == c2); 2961 r.popFront; 2962 assert(r.empty); 2963 } 2964 2965 unittest 2966 { 2967 ObjectTreeItem root = construct!ObjectTreeItem; 2968 ObjectTreeItem c0 = root.addNewChild!ObjectTreeItem; 2969 ObjectTreeItem c1 = root.addNewChild!ObjectTreeItem; 2970 ObjectTreeItem c2 = root.addNewChild!ObjectTreeItem; 2971 scope(exit) destructEach(root, c0, c1, c2); 2972 2973 size_t it; 2974 foreach (ObjectTreeItem child; root.children) 2975 { 2976 assert(c0.parent); 2977 assert(c1.parent); 2978 assert(c2.parent); 2979 if (it == 0) 2980 { 2981 c1.siblingIndex = c1.siblingCount-1; 2982 c0.siblingIndex = c0.siblingCount-1; 2983 c0.siblingIndex = 0; 2984 } 2985 else if (it == 1) 2986 { 2987 c1.siblingIndex = c1.siblingCount-1; 2988 c0.siblingIndex = c0.siblingCount-1; 2989 c0.siblingIndex = 0; 2990 } 2991 else if (it == 2) 2992 { 2993 c1.siblingIndex = c1.siblingCount-1; 2994 c0.siblingIndex = c0.siblingCount-1; 2995 c0.siblingIndex = 0; 2996 } 2997 it++; 2998 } 2999 } 3000 3001 3002 private struct LinearProbeSlot(K, V = void) 3003 { 3004 3005 enum isMap = !is(V == void); 3006 3007 private: 3008 3009 K _key; 3010 static if (isMap) V _value; 3011 3012 public: 3013 3014 @disable this(); 3015 3016 this(this) @nogc 3017 { 3018 static if (is(K == struct) && hasMember!(K, "__postblit") && isCopyable!K) 3019 _key.__postblit; 3020 static if (isMap && is(V == struct) && hasMember!(V, "__postblit") && isCopyable!V) 3021 _value.__postblit; 3022 } 3023 3024 static if (!isMap) 3025 { 3026 this(K)(auto ref K key) 3027 { 3028 _key = key; 3029 } 3030 } 3031 else 3032 { 3033 this()(auto ref K key, auto ref V value) 3034 { 3035 _key = key; 3036 _value = value; 3037 } 3038 } 3039 3040 ~this() 3041 { 3042 static if (is(K == struct)) 3043 { 3044 destruct(_key); 3045 } 3046 static if (isMap && is(V == struct)) 3047 { 3048 destruct(_value); 3049 } 3050 } 3051 3052 auto opEquals(KK)(auto ref KK key) const 3053 { 3054 static if (!isMap) 3055 { 3056 static if (hasElaborateSelfEquals!K) 3057 return _key.opEquals(key); 3058 else 3059 return _key == key; 3060 } 3061 else 3062 { 3063 static if (hasElaborateSelfEquals!K) 3064 { 3065 if (_key.opEquals(key)) 3066 return cast(const(V)*) &_value; 3067 else 3068 return cast(const(V)*) null; 3069 } 3070 else 3071 { 3072 if (key == _key) 3073 return cast(const(V)*) &_value; 3074 else 3075 return cast(const(V)*) null; 3076 } 3077 } 3078 } 3079 3080 auto ptr() 3081 { 3082 static if (!isMap) 3083 return &this; 3084 else 3085 return cast(Tuple!(K,V)*) &this; 3086 } 3087 3088 alias Slot = typeof(this); 3089 struct FindResult 3090 { 3091 @disable this(this); 3092 /// the hash after probing 3093 size_t endHash; 3094 /// the bucket after probing 3095 Slot* slot; 3096 } 3097 } 3098 3099 unittest 3100 { 3101 LinearProbeSlot!string lpbs = LinearProbeSlot!string("cat"); 3102 assert(lpbs == "cat"); 3103 assert(lpbs != "dog"); 3104 3105 LinearProbeSlot!(string,int) lpbsi = LinearProbeSlot!(string,int)("cat", 1); 3106 assert(*(lpbsi == "cat") == 1); 3107 assert((lpbsi == "rat") is null); 3108 } 3109 3110 3111 /** 3112 * Default hash function used in the HashSet and the HashMap 3113 */ 3114 pragma(inline, true) 3115 size_t fnv1(V, bool fnv1a = false)(auto ref V value) 3116 { 3117 static if (isBasicType!V || is(V==struct) || is(V == union)) 3118 return fnv1Impl!fnv1a(cast(ubyte*) &value, V.sizeof); 3119 else static if (isArray!V) 3120 return fnv1Impl!fnv1a(cast(ubyte*) value.ptr, value.length * (ElementEncodingType!V).sizeof); 3121 else static if (isPointer!V || is(V == class) || is(V == interface)) 3122 return fnv1Impl!fnv1a(cast(ubyte*) value, V.sizeof); 3123 else static assert(0); 3124 } 3125 3126 private size_t fnv1Impl(bool fnv1a = false)(ubyte* data, size_t length) 3127 { 3128 static if (size_t.sizeof == 8) 3129 size_t h = 0xCBF29CE484222325UL; 3130 else static if (size_t.sizeof == 4) 3131 size_t h = 0x811C9DC5UL; 3132 else static assert(0); 3133 3134 static if (size_t.sizeof == 8) 3135 foreach (immutable i; 0..length) 3136 { 3137 static if (fnv1a) 3138 { 3139 h ^= *data++; 3140 h *= 0x100000001B3UL; 3141 } 3142 else 3143 { 3144 h *= 0x100000001B3UL; 3145 h ^= *data++; 3146 } 3147 } 3148 else static if (size_t.sizeof == 4) 3149 foreach (immutable i; 0..length) 3150 { 3151 static if (fnv1a) 3152 { 3153 h ^= *data++; 3154 h *= 0x1000193U; 3155 } 3156 else 3157 { 3158 h *= 0x1000193U; 3159 h ^= *data++; 3160 } 3161 } 3162 else static assert(0); 3163 return h; 3164 } 3165 3166 3167 /** 3168 * Enumerates the hashset and hashmap insertion mode 3169 */ 3170 enum 3171 { 3172 /// Buckets are already reserved. 3173 imReserved = false, 3174 /// Always reserves a bucket. 3175 imExpand = true 3176 } 3177 3178 3179 /** 3180 * Enumerates the collision handling modes that 3181 * can be specified to instantiate a HashSet or a Map. 3182 */ 3183 enum CollisionHandling 3184 { 3185 /// Hanlde collision using linear probing. 3186 linearProbe, 3187 /// Handle the collision by inserting in a bucket. 3188 bucketArray, 3189 /// Assumes the hash function not to produce collisions. 3190 none, 3191 } 3192 3193 private alias CH = CollisionHandling; 3194 3195 /// Aliases an hashset implementation, by default HashSet_AB. 3196 template HashSet(CollisionHandling ch = CH.bucketArray) 3197 { 3198 static if (ch == CH.linearProbe) 3199 alias HashSet = HashSet_LP; 3200 else static if (ch == CH.bucketArray) 3201 alias HashSet = HashSet_AB; 3202 else 3203 static assert(0); 3204 } 3205 3206 /// Aliases an hashset implementation, by default HashMap_LP. 3207 template HashMap(CollisionHandling ch = CH.linearProbe) 3208 { 3209 static if (ch == CH.linearProbe) 3210 alias HashSet = HashMap_LP; 3211 else 3212 static assert(0); 3213 } 3214 3215 private enum 3216 { 3217 rngNoMap, 3218 rngMapByKey, 3219 rngMapByValue, 3220 rngMapByKeyValue, 3221 } 3222 3223 private struct RangeForLpSet(T, alias rngKind = rngNoMap) 3224 { 3225 3226 private: 3227 3228 alias PF = ReturnType!(T.slot); 3229 alias F = PointerTarget!PF; 3230 3231 size_t index; 3232 T* _hashOrMap; 3233 3234 //pragma(inline, true) 3235 void next() 3236 { 3237 while (index < _hashOrMap.slotCount) 3238 { 3239 if ((*_hashOrMap).slot(index)) 3240 break; 3241 else 3242 ++index; 3243 } 3244 } 3245 3246 public: 3247 3248 this(T* hashOrMap) @nogc 3249 { 3250 assert(hashOrMap); 3251 _hashOrMap = hashOrMap; 3252 next(); 3253 } 3254 3255 void popFront() @nogc 3256 { 3257 ++index; 3258 next(); 3259 } 3260 3261 bool empty() @nogc 3262 {return index >= _hashOrMap.slotCount;} 3263 3264 ref front() @nogc 3265 { 3266 static if (rngKind == rngNoMap || rngKind == rngMapByKeyValue) 3267 return *(*_hashOrMap).slot(index); 3268 else static if (rngKind == rngMapByKey) 3269 return (*(*_hashOrMap).slot(index))[0]; 3270 else static if (rngKind == rngMapByValue) 3271 return (*(*_hashOrMap).slot(index))[1]; 3272 } 3273 } 3274 3275 /** 3276 * A manually managed hashset that uses linear probing to solve the collisions. 3277 * 3278 * Params: 3279 * K = the key type. 3280 * hasherFun = The hashing function, a $(D size_t(K value);) function, 3281 * literal delegate or lambda. 3282 */ 3283 struct HashSet_LP(K, alias hasherFun = fnv1) 3284 { 3285 //static assert (is(typeof( (){size_t r = hasherFun(K.init);} )), 3286 // "invalid hash function"); 3287 static assert (!is(K == void), 3288 "invalid Key type"); 3289 3290 private: 3291 3292 alias HashSetT = typeof(this); 3293 alias Slot = LinearProbeSlot!K; 3294 @NoGc Array!(Slot*) _slots; 3295 size_t _count; 3296 3297 pragma(inline, true) 3298 size_t hasher(KK)(auto ref KK key) 3299 { 3300 return hasherFun(key) & (_slots.length - 1); 3301 } 3302 3303 void reHash()() @nogc 3304 { 3305 _count = 0; 3306 Array!(Slot*) old = _slots; 3307 assert(old == _slots); 3308 _slots[] = null; 3309 foreach (immutable i; 0..old.length) 3310 { 3311 if (auto b = old[i]) 3312 { 3313 insert(b._key); 3314 destruct(b); 3315 } 3316 } 3317 destruct(old); 3318 } 3319 3320 pragma(inline, true) 3321 size_t nextHash(size_t value) @nogc @safe 3322 { 3323 return (value + 1) & (_slots.length - 1); 3324 } 3325 3326 //pragma(inline, true) 3327 Slot.FindResult find(KK)(auto ref KK key) 3328 { 3329 Slot.FindResult fr; 3330 const size_t hb = hasher(key); 3331 fr.endHash = hb; 3332 3333 if (_slots.length) 3334 { 3335 fr.slot = _slots[hb]; 3336 while (true) 3337 { 3338 if (fr.slot && *fr.slot != key) 3339 { 3340 fr.endHash = nextHash(fr.endHash); 3341 if (fr.endHash == hb) 3342 break; 3343 fr.slot = _slots[fr.endHash]; 3344 } 3345 else break; 3346 } 3347 } 3348 return fr; 3349 } 3350 3351 public: 3352 3353 /** 3354 * Constructs using either a list of keys, arrays of keys, or both. 3355 */ 3356 this(A...)(A a) 3357 if (A.length) 3358 { 3359 import std.meta: aliasSeqOf; 3360 import std.range: iota; 3361 3362 foreach (i; aliasSeqOf!(iota(0, A.length))) 3363 { 3364 static if (is(A[i] == K)) 3365 continue; 3366 else static if (isArray!(A[i])) 3367 continue; 3368 else static if (is(A[i] == Array!K)) 3369 continue; 3370 else static assert(0, A[i].stringof ~ " not supported"); 3371 } 3372 foreach (i; aliasSeqOf!(iota(0, A.length))) 3373 insert(a[i]); 3374 } 3375 3376 ~this() @nogc 3377 { 3378 foreach (immutable i; 0.._slots.length) 3379 if (Slot* slt = _slots[i]) 3380 destruct(slt); 3381 destruct(_slots); 3382 } 3383 3384 this(this) @nogc 3385 { 3386 foreach (immutable i; 0.._slots.length) 3387 if (Slot* slt = _slots[i]) 3388 { 3389 Slot* n = construct!Slot(slt._key); 3390 n.__postblit(); 3391 _slots[i] = n; 3392 } 3393 } 3394 3395 /** 3396 * Tries to insert key(s) in the set. 3397 * 3398 * Params: 3399 * mode = If true (imExpand) then reserves a slot else (imReserved) 3400 * assumes a previous call to $(D reserve()). 3401 * key = either single keys, array of keys, or both. 3402 * Throws: 3403 * An $(D OutOfMemoryError) if an internal call to $(D reserve()) fails. 3404 * Returns: 3405 * If the key is added or if it's already included then returns $(D true), 3406 * otherwise $(D false). 3407 */ 3408 bool insert(alias mode)(ref K key) @nogc 3409 if (isImplicitlyConvertible!(typeof(mode), bool)) 3410 { 3411 bool result; 3412 static if (mode) 3413 reserve(1); 3414 Slot.FindResult fr = find(key); 3415 if (fr.slot is null || *fr.slot != key) 3416 { 3417 assert(key !in this); 3418 Slot* n = construct!Slot(key); 3419 if (fr.slot is null) 3420 { 3421 assert(key !in this); 3422 _slots[fr.endHash] = n; 3423 result = true; 3424 ++_count; 3425 } 3426 else destruct(n); 3427 } 3428 else if (*fr.slot == key) 3429 result = true; 3430 return result; 3431 } 3432 3433 /// ditto 3434 bool insert(alias mode = true)(K key) @nogc 3435 if (isImplicitlyConvertible!(typeof(mode), bool)) 3436 { 3437 return insert!mode(key); 3438 } 3439 3440 /// ditto 3441 bool insert(KK)(auto ref KK keys) 3442 if ((isArray!KK && is(Unqual!(ElementEncodingType!KK) == K)) || is(KK == Array!K)) 3443 { 3444 bool result = true; 3445 reserve(keys.length); 3446 foreach(k; keys) 3447 result &= insert!false(k); 3448 return result; 3449 } 3450 3451 /// ditto 3452 bool insert(KK...)(auto ref KK keys) 3453 { 3454 bool result = true; 3455 reserve(KK.length); 3456 foreach(k; keys) 3457 result &= insert!false(k); 3458 return result; 3459 } 3460 3461 /** 3462 * Tries to remove a key from the set. 3463 * 3464 * Returns: 3465 * $(D true) if the key was included otherwise $(D false). 3466 */ 3467 bool remove()(auto ref K key) 3468 { 3469 bool result; 3470 Slot.FindResult fr = find(key); 3471 if (fr.slot) 3472 { 3473 result = true; 3474 destruct(fr.slot); 3475 _slots[fr.endHash] = null; 3476 reHash; 3477 } 3478 return result; 3479 } 3480 3481 /** 3482 * Clears and empties the set. 3483 */ 3484 void clear() @nogc 3485 { 3486 foreach (immutable i; 0.._slots.length) 3487 if (auto b = _slots[i]) 3488 destruct(b); 3489 _slots[] = null; 3490 _slots.length = 0; 3491 _count = 0; 3492 } 3493 3494 /** 3495 * Support for appending element(s). Forwards $(D insert()). 3496 */ 3497 auto opOpAssign(string op : "~" , KK...)(auto ref KK keys) 3498 { 3499 return insert(keys); 3500 } 3501 3502 /** 3503 * Reserves slots for at least N supplemental keys. 3504 * 3505 * Throws: 3506 * An $(D OutOfMemoryError) if the reallocation fails. 3507 * Params: 3508 * value = The count of additional slots to reserve. 3509 */ 3510 void reserve()(size_t value) @nogc 3511 { 3512 import std.math: nextPow2; 3513 const size_t nl = nextPow2(_count + value); 3514 const size_t ol = _slots.length; 3515 3516 if (nl > _slots.length) 3517 { 3518 _slots.length = nl; 3519 _slots[ol..nl] = null; 3520 reHash(); 3521 } 3522 } 3523 3524 /** 3525 * Minimizes the memory usage. 3526 * 3527 * Should be used after removal and only if $(D count() < slotCount()). 3528 * 3529 * Throws: 3530 * An $(D OutOfMemoryError) if the reallocation fails. 3531 */ 3532 void minimize()() 3533 { 3534 import std.math: nextPow2; 3535 const size_t nl = nextPow2(_count-1); 3536 3537 if (nl < _slots.length) 3538 { 3539 Array!(K) old; 3540 foreach (immutable i; 0.._slots.length) 3541 if (auto b = _slots[i]) 3542 old ~= b._key; 3543 clear; 3544 foreach (immutable i; 0..old.length) 3545 { 3546 insert(old[i]); 3547 static if (is(K==struct)) 3548 destruct(old[i]); 3549 } 3550 destruct(old); 3551 } 3552 } 3553 3554 /** 3555 * Tests the presence of a key in the set. 3556 * 3557 * Params: 3558 * key = The key to test. 3559 * Returns: 3560 * $(D null) if the key is not present otherwise a pointer to the key. 3561 */ 3562 K* opBinaryRight(string op : "in", KK)(auto ref KK key) 3563 { 3564 K* result; 3565 Slot.FindResult fr = find(key); 3566 if (fr.slot) 3567 result = &fr.slot._key; 3568 return result; 3569 } 3570 3571 /** 3572 * Provides an access to the keys. 3573 * 3574 * Params: 3575 * index = The slot index. Must be in the $(D 0..slotCount()) range. 3576 * Returns: 3577 * A pointer the nth key. 3578 */ 3579 K* slot(const size_t index) 3580 { 3581 return &_slots[index]._key; 3582 } 3583 3584 /** 3585 * Returns an input range that consists of each non-null key. 3586 */ 3587 auto byKey() 3588 { 3589 return RangeForLpSet!HashSetT(&this); 3590 } 3591 3592 /** 3593 * Returns the keys count. 3594 * 3595 * This matches to $(D byKey.walkLength). 3596 */ 3597 size_t count() @nogc {return _count;} 3598 3599 /** 3600 * Returns the slots count. 3601 */ 3602 size_t slotCount() @nogc {return _slots.length;} 3603 } 3604 /// 3605 @nogc unittest 3606 { 3607 HashSet_LP!string commands; 3608 // can insert up to 16 elements without reallocation 3609 commands.reserve(15); 3610 assert(commands.slotCount == 16); 3611 // appends elements 3612 commands.insert("move"); 3613 commands.insert("insert"); 3614 commands.insert("delete"); 3615 // test for inclusion 3616 assert("move" in commands); 3617 // remove something 3618 commands.remove("insert"); 3619 assert(commands.count == 2); 3620 assert("insert" !in commands); 3621 // empties and frees memory 3622 commands.clear; 3623 // manually managed implies to destruct by hand 3624 import iz.memory; 3625 destruct(commands); 3626 } 3627 3628 @nogc unittest 3629 { 3630 HashSet_LP!string hss; 3631 3632 hss.reserve(7); 3633 assert(hss.slotCount == 8); 3634 3635 foreach(i; 0 .. hss._slots.length) 3636 assert(hss._slots[i] is null); 3637 3638 assert(hss.insert("cat")); 3639 assert("dog" !in hss); 3640 assert("cat" in hss); 3641 3642 assert(hss.insert("rat")); 3643 assert("dog" !in hss); 3644 assert("cat" in hss); 3645 assert("rat" in hss); 3646 3647 assert(hss.insert("fly")); 3648 assert("dog" !in hss); 3649 assert("cat" in hss); 3650 assert("rat" in hss); 3651 assert("fly" in hss); 3652 3653 assert(hss.insert("bee")); 3654 assert("dog" !in hss); 3655 assert("cat" in hss); 3656 assert("rat" in hss); 3657 assert("fly" in hss); 3658 assert("bee" in hss); 3659 3660 assert(hss.insert("ant")); 3661 assert("dog" !in hss); 3662 assert("cat" in hss); 3663 assert("rat" in hss); 3664 assert("fly" in hss); 3665 assert("bee" in hss); 3666 assert("ant" in hss); 3667 assert("fox" !in hss); 3668 3669 assert(hss.insert("fox")); 3670 assert("dog" !in hss); 3671 assert("cat" in hss); 3672 assert("rat" in hss); 3673 assert("fly" in hss); 3674 assert("bee" in hss); 3675 assert("ant" in hss); 3676 assert("fox" in hss); 3677 3678 assert(hss.insert("bat")); 3679 assert("dog" !in hss); 3680 assert("cat" in hss); 3681 assert("rat" in hss); 3682 assert("fly" in hss); 3683 assert("bee" in hss); 3684 assert("ant" in hss); 3685 assert("fox" in hss); 3686 assert("bat" in hss); 3687 3688 assert(hss.insert("cow")); 3689 assert("dog" !in hss); 3690 assert("cat" in hss); 3691 assert("rat" in hss); 3692 assert("fly" in hss); 3693 assert("bee" in hss); 3694 assert("ant" in hss); 3695 assert("fox" in hss); 3696 assert("bat" in hss); 3697 assert("cow" in hss); 3698 3699 assert(hss.remove("bat")); 3700 assert("bat" !in hss); 3701 3702 hss.clear; 3703 assert(hss.count == 0); 3704 assert(hss.slotCount == 0); 3705 3706 hss.reserve(8); 3707 import std.algorithm: among; 3708 assert(hss.insert("cow")); 3709 assert(hss.insert("yak")); 3710 auto r = hss.byKey; 3711 assert(!r.empty); 3712 assert((r.front).among("cow","yak")); 3713 r.popFront; 3714 assert(!r.empty); 3715 assert((r.front).among("cow","yak")); 3716 r.popFront; 3717 assert(r.empty); 3718 assert(hss.slotCount == 16); 3719 3720 assert(hss.count == 2); 3721 hss.minimize; 3722 assert(hss.slotCount < 16); 3723 3724 destruct(hss); 3725 } 3726 3727 @nogc unittest 3728 { 3729 HashSet_LP!string co; 3730 assert(co.count == 0); 3731 co.insert("abcd"); 3732 assert(co.count == 1); 3733 co.insert("abcd"); 3734 assert(co.count == 1); 3735 co.insert("abcd"); 3736 assert(co.count == 1); 3737 co.insert("abcde"); 3738 assert(co.count == 2); 3739 co.insert("abcde"); 3740 assert(co.count == 2); 3741 co.insert("abcde"); 3742 assert(co.count == 2); 3743 co.insert("abcde"); 3744 assert(co.count == 2); 3745 destruct(co); 3746 } 3747 3748 @nogc unittest 3749 { 3750 { 3751 HashSet_LP!string co = HashSet_LP!string("ab", "ab", "cd"); 3752 assert(co.count == 2); 3753 destruct(co); 3754 } 3755 { 3756 static a = ["ab", "cd"]; 3757 HashSet_LP!string co = HashSet_LP!string("ab", a); 3758 assert(co.count == 2); 3759 destruct(co); 3760 } 3761 { 3762 HashSet_LP!int co = HashSet_LP!int(1); 3763 assert(co.count == 1); 3764 assert(2 !in co); 3765 assert(1 in co); 3766 destruct(co); 3767 } 3768 } 3769 3770 /** 3771 * A manually managed hashmap that uses linear probing to solve the collisions. 3772 * 3773 * Params: 3774 * K = The key type. 3775 * V = The value type 3776 * hasherFun = The hashing function, a $(D size_t(K value);) function, 3777 * literal delegate or lambda. 3778 */ 3779 struct HashMap_LP(K, V, alias hasherFun = fnv1) 3780 { 3781 static assert (is(typeof( (){size_t r = hasherFun(K.init);} )), 3782 "invalid hash function"); 3783 static assert (!is(K == void), 3784 "invalid Key type"); 3785 static assert (!is(V == void), 3786 "invalid Value type"); 3787 3788 private: 3789 3790 alias MapT = typeof(this); 3791 alias Slot = LinearProbeSlot!(K,V); 3792 @NoGc Array!(Slot*) _slots; 3793 size_t _count; 3794 3795 pragma(inline, true) 3796 size_t hasher(KK)(auto ref KK key) @nogc 3797 { 3798 return hasherFun(key) & (_slots.length - 1); 3799 } 3800 3801 void reHash()() 3802 { 3803 _count = 0; 3804 auto old = _slots.dup; 3805 assert(old == _slots); 3806 _slots[] = null; 3807 foreach (immutable i; 0..old.length) 3808 { 3809 if (auto b = old[i]) 3810 { 3811 insert(b._key, b._value); 3812 destruct(b); 3813 } 3814 } 3815 destruct(old); 3816 } 3817 3818 pragma(inline, true) 3819 size_t nextHash(size_t value) @nogc @safe 3820 { 3821 return (value + 1) & (_slots.length - 1); 3822 } 3823 3824 //pragma(inline, true) 3825 Slot.FindResult find(KK)(auto ref KK key) 3826 { 3827 Slot.FindResult fr; 3828 const size_t hb = hasher(key); 3829 fr.endHash = hb; 3830 3831 if (_slots.length) 3832 { 3833 fr.slot = _slots[hb]; 3834 while (true) 3835 { 3836 if (fr.slot && *fr.slot != key) 3837 { 3838 fr.endHash = nextHash(fr.endHash); 3839 if (fr.endHash == hb) 3840 break; 3841 fr.slot = _slots[fr.endHash]; 3842 } 3843 else break; 3844 } 3845 } 3846 return fr; 3847 } 3848 3849 public: 3850 3851 alias MapPair = Tuple!(K, V); 3852 3853 ~this() @nogc 3854 { 3855 foreach(immutable i; 0.._slots.length) 3856 if (Slot* slt = _slots[i]) 3857 destruct(slt); 3858 destruct(_slots); 3859 } 3860 3861 this(this) @nogc 3862 { 3863 foreach (immutable i; 0.._slots.length) 3864 if (Slot* slt = _slots[i]) 3865 { 3866 Slot* n = construct!Slot(slt._key, slt._value); 3867 n.__postblit(); 3868 _slots[i] = n; 3869 } 3870 } 3871 3872 /** 3873 * Tries to insert a key-value pair in the map. 3874 * 3875 * Params: 3876 * mode = If set to $(D imExpand) then reserves a slot else if set to 3877 * $(D imReserved) assumes a previous call to $(D reserve()). 3878 * key = The key. 3879 * value = The corresponding value. 3880 * Throws: 3881 * An $(D OutOfMemoryError) if an internal call to $(D reserve()) fails. 3882 * Returns: 3883 * If the key is added or if it's already included then returns $(D true), 3884 * otherwise $(D false). 3885 */ 3886 bool insert(alias mode = imExpand)(ref K key, auto ref V value) @nogc 3887 if (isImplicitlyConvertible!(typeof(mode), bool)) 3888 { 3889 bool result; 3890 static if (mode) 3891 reserve(1); 3892 Slot.FindResult fr = find(key); 3893 if (fr.slot is null || *fr.slot != key) 3894 { 3895 assert(key !in this); 3896 Slot* n = construct!Slot(key, value); 3897 if (fr.slot is null) 3898 { 3899 assert(key !in this); 3900 _slots[fr.endHash] = n; 3901 result = true; 3902 ++_count; 3903 } 3904 else destruct(n); 3905 } 3906 else if (*fr.slot == key) 3907 { 3908 result = true; 3909 destruct(fr.slot); 3910 Slot* n = construct!Slot(key, value); 3911 _slots[fr.endHash] = n; 3912 } 3913 return result; 3914 } 3915 3916 /// ditto 3917 bool insert(alias mode = imExpand)(K key, V value) @nogc 3918 if (isImplicitlyConvertible!(typeof(mode), bool)) 3919 { 3920 return insert!mode(key, value); 3921 } 3922 3923 /** 3924 * Tries to remove a key from the set. 3925 * 3926 * Returns: 3927 * $(D true) if the key was included otherwise $(D false). 3928 */ 3929 bool remove()(auto ref K key) 3930 { 3931 bool result; 3932 Slot.FindResult fr = find(key); 3933 if (fr.slot) 3934 { 3935 result = true; 3936 destruct(fr.slot); 3937 _slots[fr.endHash] = null; 3938 reHash; 3939 } 3940 return result; 3941 } 3942 3943 /** 3944 * Clears and empties the set. 3945 * 3946 * Throws: 3947 * An $(D OutOfMemoryError) if the reallocation fails. 3948 */ 3949 void clear() @nogc 3950 { 3951 foreach (immutable i; 0.._slots.length) 3952 if (auto b = _slots[i]) 3953 destruct(b); 3954 _slots[] = null; 3955 _slots.length = 0; 3956 _count = 0; 3957 } 3958 3959 /** 3960 * Support for appending an element. 3961 * 3962 * Forwards $(D insert()) with a default initialized value. 3963 * 3964 * Params: 3965 * key = The key to insert. 3966 * Returns: 3967 * If the key is added or if it's already included then returns $(D true), 3968 * otherwise $(D false). 3969 */ 3970 bool opOpAssign(string op : "~")(auto ref K key) 3971 { 3972 return insert(key, V.init); 3973 } 3974 3975 /** 3976 * Support for inserting using the array syntax. Forwards $(D insert()). 3977 */ 3978 void opIndexAssign(KK)(auto ref V value, auto ref KK key) 3979 { 3980 insert(key, value); 3981 } 3982 3983 /** 3984 * Support for assigning to the value when the value is itself an AA. 3985 * 3986 * Note that this function only exists to port code that uses the runtime AA 3987 * with the syntax $(D aa[k_for_value][k_for_value_of_value] = stuff;). 3988 */ 3989 void opIndexAssign(V2, KK1, KK2)(auto ref V2 value, auto ref KK1 key1, auto ref KK2 key2) 3990 { 3991 if (auto v = key1 in this) 3992 { 3993 v.insert(key2, value); 3994 } 3995 else 3996 { 3997 V v; 3998 v.insert(key2, value); 3999 insert(key1, v); 4000 } 4001 } 4002 4003 /** 4004 * Support for the assignment operators on a value. 4005 */ 4006 void opIndexOpAssign(string op, VV, KK)(auto ref VV value, auto ref KK key) 4007 { 4008 if (auto p = key in this) 4009 { 4010 mixin("(*p)" ~ op ~ "= value;"); 4011 } 4012 else 4013 { 4014 V v; 4015 mixin("v" ~ op ~ "= value;"); 4016 insert(key, v); 4017 } 4018 } 4019 4020 /** 4021 * Returns an input range consisting of each key. 4022 */ 4023 auto byKey() return @nogc 4024 { 4025 return RangeForLpSet!(MapT,rngMapByKey)(&this); 4026 } 4027 4028 /** 4029 * Returns an input range consisting of each value. 4030 */ 4031 auto byValue() return @nogc 4032 { 4033 return RangeForLpSet!(MapT,rngMapByValue)(&this); 4034 } 4035 4036 /** 4037 * Returns an input range consisting of each non-null key-value pair. 4038 */ 4039 auto byKeyValue() return @nogc 4040 { 4041 return RangeForLpSet!MapT(&this); 4042 } 4043 4044 /** 4045 * Reserves slots for at least N supplemental key-value pairs. 4046 * 4047 * Throws: 4048 * An $(D OutOfMemoryError) if the reallocation fails. 4049 * Params: 4050 * value = The count of additional slots to reserve. 4051 */ 4052 void reserve()(size_t value) @nogc 4053 { 4054 import std.math: nextPow2; 4055 const size_t nl = nextPow2(_count + value); 4056 const size_t ol = _slots.length; 4057 4058 if (nl > _slots.length) 4059 { 4060 _slots.length = nl; 4061 _slots[ol..nl] = null; 4062 reHash(); 4063 } 4064 } 4065 4066 /** 4067 * Minimizes the memory usage. 4068 * 4069 * Should be used after removal and only if $(D count() < slotCount()). 4070 */ 4071 void minimize()() 4072 { 4073 import std.math: nextPow2; 4074 const size_t nl = nextPow2(_count-1); 4075 4076 if (nl < _slots.length) 4077 { 4078 Array!(MapPair) old; 4079 foreach (immutable i; 0.._slots.length) 4080 if (auto b = _slots[i]) 4081 old ~= tuple(b._key, b._value); 4082 clear; 4083 foreach (immutable i; 0..old.length) 4084 { 4085 insert(old[i][0..2]); 4086 static if (is(K == struct)) 4087 destruct(old[i]); 4088 } 4089 destruct(old); 4090 } 4091 } 4092 4093 /** 4094 * Tests the presence of a key in the set. 4095 * 4096 * Params: 4097 * key = The key to test. 4098 * Returns: 4099 * $(D null) if the key is not present otherwise a pointer to the 4100 * value that mapped. 4101 */ 4102 V* opBinaryRight(string op : "in", KK)(auto ref KK key) 4103 { 4104 V* result; 4105 Slot.FindResult fr = find(key); 4106 if (fr.slot) 4107 result = &fr.slot._value; 4108 return result; 4109 } 4110 4111 /** 4112 * Provides an access to the key-value pairs. 4113 * 4114 * Params 4115 * index = The pair index. Must be in the $(D 0..slotCount()) range. 4116 * Returns: 4117 * A pointer to a tuple that contains, when not null, the 4118 * key and the value of the element pointed by $(D_PARAM index). 4119 */ 4120 MapPair* slot(const size_t index) @nogc 4121 { 4122 if (auto r = _slots[index]) 4123 return r.ptr; 4124 else 4125 return null; 4126 } 4127 4128 /// ditto 4129 auto ref V opIndex(KK)(auto ref KK key) 4130 if (!is(KK == size_t)) 4131 { 4132 return *(key in this); 4133 } 4134 4135 /** 4136 * Returns the key-value pairs count. 4137 * 4138 * This matches to $(D byKeyValue.walkLength). 4139 */ 4140 size_t count() @nogc {return _count;} 4141 4142 /** 4143 * Returns the slots counts. 4144 */ 4145 size_t slotCount() @nogc {return _slots.length;} 4146 } 4147 /// 4148 @nogc unittest 4149 { 4150 HashMap_LP!(string, size_t) stock; 4151 // can insert up to 16 elements without reallocation 4152 stock.reserve(15); 4153 assert(stock.slotCount == 16); 4154 // appends elements, various syntax allowed 4155 stock.insert("pen", 8); 4156 stock["gum"] += 32; 4157 stock["ruler"] += 12; 4158 stock ~= "tape roll"; 4159 // test for inclusion, various syntax allowed 4160 assert("gum" in stock); 4161 assert(stock["ruler"] == 12); 4162 assert(stock["tape roll"] == 0); 4163 // remove something 4164 stock.remove("ruler"); 4165 assert("ruler" !in stock); 4166 // empties and frees memory 4167 stock.clear; 4168 // manually managed implies to destruct by hand 4169 import iz.memory; 4170 destruct(stock); 4171 } 4172 4173 @nogc unittest 4174 { 4175 HashMap_LP!(string, int) hmsi; 4176 hmsi.reserve(15); 4177 4178 hmsi.insert("cat", 0); 4179 hmsi.insert("dog", 1); 4180 hmsi.insert("pig", 2); 4181 assert(hmsi.count == 3); 4182 assert(*("cat" in hmsi) == 0); 4183 assert(*("dog" in hmsi) == 1); 4184 assert(*("pig" in hmsi) == 2); 4185 assert("bat" !in hmsi); 4186 assert("bug" !in hmsi); 4187 4188 hmsi["bat"] = 3; 4189 hmsi["bug"] = 4; 4190 assert(hmsi.count == 5); 4191 assert(*("cat" in hmsi) == 0); 4192 assert(*("dog" in hmsi) == 1); 4193 assert(*("pig" in hmsi) == 2); 4194 assert(*("bat" in hmsi) == 3); 4195 assert(*("bug" in hmsi) == 4); 4196 4197 assert(hmsi.remove("cat")); 4198 assert(hmsi.count == 4); 4199 assert("cat" !in hmsi); 4200 assert(*("dog" in hmsi) == 1); 4201 assert(*("pig" in hmsi) == 2); 4202 assert(*("bat" in hmsi) == 3); 4203 assert(*("bug" in hmsi) == 4); 4204 4205 hmsi["owl"] = 5; 4206 assert(hmsi.count == 5); 4207 assert("cat" !in hmsi); 4208 assert(*("dog" in hmsi) == 1); 4209 assert(*("pig" in hmsi) == 2); 4210 assert(*("bat" in hmsi) == 3); 4211 assert(*("bug" in hmsi) == 4); 4212 assert(*("owl" in hmsi) == 5); 4213 4214 hmsi.clear; 4215 assert(hmsi.count == 0); 4216 assert("cat" !in hmsi); 4217 assert("dog" !in hmsi); 4218 assert("pig" !in hmsi); 4219 assert("bat" !in hmsi); 4220 assert("bug" !in hmsi); 4221 assert("owl" !in hmsi); 4222 4223 hmsi["bat"] = 3; 4224 hmsi["bug"] = 4; 4225 assert(hmsi.count == 2); 4226 assert(hmsi["bat"] == 3); 4227 assert(hmsi["bug"] == 4); 4228 hmsi["bat"] = 4; 4229 hmsi["bug"] = 3; 4230 assert(hmsi.count == 2); 4231 assert(hmsi["bat"] == 4); 4232 assert(hmsi["bug"] == 3); 4233 4234 destruct(hmsi); 4235 } 4236 4237 @nogc unittest 4238 { 4239 HashMap_LP!(int, int) hmii; 4240 hmii.reserve(32); 4241 hmii[1] = 3; 4242 hmii[2] = 4; 4243 foreach(kv; hmii.byKeyValue) 4244 { 4245 assert(kv[0] == 1 || kv[0] == 2); 4246 assert(kv[1] == 3 || kv[1] == 4); 4247 } 4248 destruct(hmii); 4249 } 4250 4251 /** 4252 * The bucket used in HashSet_AB and HashMap_AB. 4253 */ 4254 struct ArrayBucket(K, V = void) 4255 { 4256 4257 private: 4258 4259 static if (!isMap) 4260 { 4261 alias ArrayT = Array!K; 4262 } 4263 else 4264 { 4265 alias Pair = Tuple!(K, V); 4266 alias ArrayT = Array!(Pair); 4267 } 4268 4269 ArrayT _array; 4270 4271 public: 4272 4273 enum isMap = !is(V == void); 4274 4275 ~this() @nogc 4276 { 4277 static if (isMap) 4278 { 4279 foreach (immutable i; 0.._array.length) 4280 { 4281 static if (is(K == struct)) 4282 destruct(_array[i][0]); 4283 static if (is(V == struct)) 4284 destruct(_array[i][1]); 4285 } 4286 } 4287 destruct(_array); 4288 } 4289 4290 this(this) @nogc 4291 { 4292 _array.__postblit; 4293 } 4294 4295 ref const(ArrayT) array() const @nogc nothrow 4296 {return _array;} 4297 4298 static if (isMap) 4299 void insert(ref K key, ref V value) @nogc nothrow 4300 { 4301 _array ~= tuple(key, value); 4302 } 4303 else 4304 void insert(ref K key) @nogc nothrow 4305 { 4306 _array ~= key; 4307 } 4308 4309 bool remove()(ref K key) 4310 { 4311 bool result; 4312 foreach (immutable i; 0.._array._length) 4313 { 4314 static if (!isMap) 4315 { 4316 static if (hasElaborateSelfEquals!K) 4317 { 4318 if (!_array[i].opEquals(key)) 4319 continue; 4320 } 4321 else 4322 { 4323 if (_array[i] != key) 4324 continue; 4325 } 4326 } 4327 else 4328 { 4329 static if (hasElaborateSelfEquals!K) 4330 { 4331 if (!_array[i][0].opEquals(key)) 4332 continue; 4333 } 4334 else 4335 { 4336 if (_array[i][0] != key) 4337 continue; 4338 } 4339 } 4340 result = true; 4341 if (i == 0) 4342 { 4343 if (_array.length > 1) 4344 _array = _array[1..$]; 4345 else 4346 _array.length = 0; 4347 } 4348 else if (i == _array.length-1) 4349 { 4350 _array.length = _array.length - 1; 4351 } 4352 else _array = _array[0..i] ~ _array[i+1..$]; 4353 break; 4354 } 4355 return result; 4356 } 4357 4358 pragma(inline, true) 4359 void clear() @nogc nothrow 4360 { 4361 _array.length = 0; 4362 } 4363 4364 ptrdiff_t indexOfKey()(ref K key) 4365 { 4366 ptrdiff_t result = -1; 4367 foreach (immutable i; 0.._array.length) 4368 { 4369 static if (isMap) 4370 { 4371 static if (hasElaborateSelfEquals!K) 4372 { 4373 if (_array[i][0].opEquals(key)) 4374 { 4375 result = i; 4376 break; 4377 } 4378 } 4379 else 4380 { 4381 if (_array[i][0] == key) 4382 { 4383 result = i; 4384 break; 4385 } 4386 } 4387 } 4388 else 4389 { 4390 static if (hasElaborateSelfEquals!K) 4391 { 4392 if (_array[i].opEquals(key)) 4393 { 4394 result = i; 4395 break; 4396 } 4397 } 4398 else 4399 { 4400 if (_array[i] == key) 4401 { 4402 result = i; 4403 break; 4404 } 4405 } 4406 } 4407 } 4408 return result; 4409 } 4410 4411 pragma(inline, true) 4412 K* getKey(KK)(ref KK key) 4413 { 4414 K* result; 4415 if (const size_t j = _array.length) 4416 foreach (immutable i; 0..j) 4417 { 4418 static if (isMap) 4419 { 4420 static if (hasElaborateSelfEquals!K) 4421 { 4422 if (_array[i][0].opEquals(key)) 4423 { 4424 result = &_array[i][0]; 4425 break; 4426 } 4427 } 4428 else 4429 { 4430 if (_array[i][0] == key) 4431 { 4432 result = &_array[i][0]; 4433 break; 4434 } 4435 } 4436 } 4437 else 4438 { 4439 static if (hasElaborateSelfEquals!K) 4440 { 4441 if (_array[i].opEquals(key)) 4442 { 4443 result = &_array[i]; 4444 break; 4445 } 4446 } 4447 else 4448 { 4449 if (_array[i] == key) 4450 { 4451 result = &_array[i]; 4452 break; 4453 } 4454 } 4455 } 4456 } 4457 return result; 4458 } 4459 4460 static if (isMap) 4461 V* getValue(KK)(ref KK key) 4462 { 4463 V* result; 4464 if (const size_t j = _array.length) 4465 foreach (immutable i; 0..j) 4466 { 4467 static if (hasElaborateSelfEquals!K) 4468 { 4469 if (_array[i][0].opEquals(key)) 4470 { 4471 result = &_array[i][1]; 4472 break; 4473 } 4474 } 4475 else 4476 { 4477 if (_array[i][0] == key) 4478 { 4479 result = &_array[i][1]; 4480 break; 4481 } 4482 } 4483 } 4484 return result; 4485 } 4486 4487 static if (isMap) 4488 ptrdiff_t indexOfValue()(ref V value) 4489 { 4490 ptrdiff_t result = -1; 4491 foreach(immutable i; 0.._array.length) 4492 { 4493 if (_array[i][1] == value) 4494 { 4495 result = i; 4496 break; 4497 } 4498 } 4499 return result; 4500 } 4501 4502 size_t length() @nogc const pure nothrow {return _array.length;} 4503 } 4504 4505 private struct RangeForAbSet(T, alias rngKind = rngNoMap) 4506 { 4507 4508 private: 4509 4510 T* _hashSetOrMap; 4511 alias B = ReturnType!(T.bucket); 4512 B _currBucket; 4513 bool _empty; 4514 size_t _bucketIndex; 4515 size_t _keyIndex; 4516 4517 public: 4518 4519 this(T* hashSetOrMap) @nogc nothrow 4520 { 4521 assert(hashSetOrMap); 4522 _hashSetOrMap = hashSetOrMap; 4523 popFront; 4524 } 4525 4526 bool empty() @nogc nothrow 4527 { 4528 return _currBucket is null; 4529 } 4530 4531 void popFront() @nogc nothrow 4532 { 4533 if (_currBucket) 4534 { 4535 ++_keyIndex; 4536 if (_keyIndex >= _currBucket.length) 4537 { 4538 _currBucket = null; 4539 _keyIndex = 0; 4540 ++_bucketIndex; 4541 } 4542 } 4543 if (!_currBucket) 4544 { 4545 while (_bucketIndex < _hashSetOrMap._buckets.length) 4546 { 4547 _currBucket = (*_hashSetOrMap).bucket(_bucketIndex); 4548 if (_currBucket.length) 4549 break; 4550 else 4551 ++_bucketIndex; 4552 } 4553 if (_bucketIndex == _hashSetOrMap._buckets.length) 4554 _currBucket = null; 4555 } 4556 } 4557 4558 auto ref front() @nogc 4559 { 4560 static if (rngKind == rngNoMap || rngKind == rngMapByKeyValue) 4561 return _currBucket._array[_keyIndex]; 4562 else static if (rngKind == rngMapByKey) 4563 return _currBucket._array[_keyIndex][0]; 4564 else static if (rngKind == rngMapByValue) 4565 return _currBucket._array[_keyIndex][1]; 4566 } 4567 } 4568 4569 /** 4570 * A manually managed hashset that uses buckets to solve the collisions. 4571 * 4572 * Params: 4573 * K = the key type. 4574 * hasherFun = The hashing function, a $(D size_t(K value);) function, 4575 * literal delegate or lambda. 4576 */ 4577 struct HashSet_AB(K, alias hasherFun = fnv1) 4578 { 4579 static assert (is(typeof( (){size_t r = hasherFun(K.init);} )), 4580 "invalid hash function"); 4581 static assert (!is(K == void), 4582 "invalid Key type"); 4583 4584 private: 4585 4586 alias HashSetT = typeof(this); 4587 alias BucketT = ArrayBucket!K; 4588 @NoGc Array!BucketT _buckets; 4589 size_t _count; 4590 4591 pragma(inline, true) 4592 size_t hasher(KK)(auto ref KK key) @nogc 4593 { 4594 return hasherFun(key) & (_buckets.length - 1); 4595 } 4596 4597 void reHash()() 4598 { 4599 _count = 0; 4600 Array!BucketT old = _buckets; 4601 foreach (immutable i; 0.._buckets.length) 4602 _buckets[i].clear; 4603 foreach (immutable i; 0..old.length) 4604 { 4605 foreach (immutable j; 0..old[i]._array.length) 4606 insert!false(old[i]._array[j]); 4607 } 4608 destruct(old); 4609 } 4610 4611 public: 4612 4613 /** 4614 * Constructs using either a list of keys, arrays of keys, or both. 4615 */ 4616 this(A...)(A a) 4617 { 4618 import std.meta: aliasSeqOf; 4619 import std.range: iota; 4620 4621 foreach (i; aliasSeqOf!(iota(0, A.length))) 4622 { 4623 static if (is(A[i] == K)) 4624 continue; 4625 else static if (isArray!(A[i])) 4626 continue; 4627 else static if (is(A[i] == Array!K)) 4628 continue; 4629 else static assert(0, A[i].stringof ~ " not supported"); 4630 } 4631 foreach (i; aliasSeqOf!(iota(0, A.length))) 4632 insert(a[i]); 4633 } 4634 4635 ~this() @nogc 4636 { 4637 destruct(_buckets); 4638 } 4639 4640 /** 4641 * Tries to insert key(s) in the set. 4642 * 4643 * Params: 4644 * mode = If true (imExpand) then reserves a slot else (imReserved) 4645 * assumes a previous call to $(D reserve()). 4646 * key = either single keys, array of keys, or both. 4647 * Throws: 4648 * An $(D OutOfMemoryError) if an internal call to $(D reserve()) fails. 4649 * Returns: 4650 * If the key is added or if it's already included then returns $(D true), 4651 * otherwise $(D false). 4652 */ 4653 bool insert(alias mode = true)(ref K key) @nogc 4654 if (isImplicitlyConvertible!(typeof(mode), bool)) 4655 { 4656 bool result; 4657 if (!_buckets.length || key !in this) 4658 { 4659 result = true; 4660 static if (mode) 4661 reserve(1); 4662 const size_t h = hasher(key); 4663 assert(h < _buckets.length); 4664 _buckets[h].insert(key); 4665 ++_count; 4666 } 4667 return result; 4668 } 4669 4670 /// ditto 4671 bool insert(alias mode = true)(K key) @nogc 4672 if (isImplicitlyConvertible!(typeof(mode), bool)) 4673 { 4674 return insert!mode(key); 4675 } 4676 4677 /// ditto 4678 bool insert(KK)(auto ref KK keys) 4679 if ((isArray!KK && is(Unqual!(ElementEncodingType!KK) == K)) || is(KK == Array!K)) 4680 { 4681 bool result = true; 4682 reserve(keys.length); 4683 foreach(k; keys) 4684 result &= insert!false(k); 4685 return result; 4686 } 4687 4688 /// ditto 4689 bool insert(KK...)(auto ref KK keys) 4690 { 4691 bool result = true; 4692 reserve(KK.length); 4693 foreach(k; keys) 4694 result &= insert!false(k); 4695 return result; 4696 } 4697 4698 /** 4699 * Tries to remove a key from the set. 4700 * 4701 * Returns: 4702 * $(D true) if the key was included otherwise $(D false). 4703 */ 4704 bool remove()(auto ref K key) 4705 { 4706 const size_t h = hasher(key); 4707 const bool result = _buckets[h].remove(key); 4708 if (result) 4709 --_count; 4710 return result; 4711 } 4712 4713 /** 4714 * Reserves buckets for at least N supplemental keys. 4715 * 4716 * Throws: 4717 * An $(D OutOfMemoryError) if the reallocation fails. 4718 * Params: 4719 * value = The count of additional slots to reserve. 4720 */ 4721 void reserve()(size_t value) 4722 { 4723 import std.math: nextPow2; 4724 const size_t nl = nextPow2(_count + value); 4725 if (nl > _buckets.length) 4726 { 4727 _buckets.length = nl; 4728 reHash(); 4729 } 4730 } 4731 4732 /** 4733 * Minimizes the memory used by the set. 4734 * 4735 * Throws: 4736 * An $(D OutOfMemoryError) if the reallocation fails. 4737 */ 4738 void minimize()() 4739 { 4740 import std.math: nextPow2; 4741 const size_t nl = nextPow2(_count-1); 4742 4743 if (nl < _buckets.length) 4744 { 4745 Array!BucketT old = _buckets; 4746 clear; 4747 _buckets.length = nl; 4748 foreach (immutable i; 0..old.length) 4749 foreach (immutable j; 0..old[i]._array.length) 4750 { 4751 insert!false(old[i]._array[j]); 4752 } 4753 destruct(old); 4754 } 4755 } 4756 4757 /** 4758 * Empties the set. 4759 */ 4760 void clear() @nogc 4761 { 4762 _buckets.length = 0; 4763 _buckets.length = 2; 4764 _count = 0; 4765 } 4766 4767 /** 4768 * Tests the presence of a key in the set. 4769 * 4770 * Params: 4771 * key = The key to test. 4772 * Returns: 4773 * $(D null) if the key is not present otherwise a pointer to the key. 4774 */ 4775 pragma(inline, true) 4776 K* opBinaryRight(string op : "in", KK)(auto ref KK key) 4777 { 4778 return _buckets[hasher(key)].getKey(key); 4779 } 4780 4781 /** 4782 * Provides an access to the buckets. 4783 * 4784 * Params: 4785 * index = The bucket index. Must be in the $(D 0..bucketCount()) range. 4786 * Returns: 4787 * A never null, pointer to a bucket. 4788 */ 4789 BucketT* bucket(const size_t index) pure nothrow @nogc 4790 { 4791 return &_buckets[index]; 4792 } 4793 4794 /** 4795 * Returns: an input range that allows to iterate the keys. 4796 */ 4797 auto byKey() 4798 { 4799 return RangeForAbSet!HashSetT(&this); 4800 } 4801 4802 /** 4803 * Returns: the elements count. 4804 */ 4805 size_t count() pure nothrow @nogc {return _count;} 4806 4807 /** 4808 * Returns: the buckets count. 4809 */ 4810 size_t bucketCount() pure nothrow @nogc {return _buckets.length;} 4811 4812 /** 4813 * Returns: the collisions count. 4814 */ 4815 size_t collisions() pure nothrow @nogc 4816 { 4817 size_t result; 4818 foreach(immutable i; 0.._buckets.length) 4819 result += _buckets[i]._array.length > 1 ? 4820 _buckets[i]._array.length - 1 : 0; 4821 return result; 4822 } 4823 } 4824 /// 4825 @nogc unittest 4826 { 4827 HashSet_AB!string commands; 4828 // can insert up to 16 elements without reallocation 4829 commands.reserve(15); 4830 assert(commands.bucketCount == 16); 4831 // appends elements 4832 commands.insert("move"); 4833 commands.insert("insert"); 4834 commands.insert("delete"); 4835 // test for inclusion 4836 assert("move" in commands); 4837 // remove something 4838 commands.remove("insert"); 4839 assert(commands.count == 2); 4840 assert("insert" !in commands); 4841 // empties and frees memory 4842 commands.clear; 4843 // manually managed implies to destruct by hand 4844 import iz.memory; 4845 destruct(commands); 4846 } 4847 4848 @nogc unittest 4849 { 4850 HashSet_AB!string hss; 4851 4852 assert(hss.insert("cat")); 4853 assert(hss.bucketCount == 2); 4854 assert("dog" !in hss); 4855 assert("cat" in hss); 4856 4857 assert(hss.insert("rat")); 4858 assert("dog" !in hss); 4859 assert("cat" in hss); 4860 assert("rat" in hss); 4861 4862 assert(hss.insert("fly")); 4863 assert("dog" !in hss); 4864 assert("cat" in hss); 4865 assert("rat" in hss); 4866 assert("fly" in hss); 4867 4868 assert(hss.insert("bee")); 4869 assert("dog" !in hss); 4870 assert("cat" in hss); 4871 assert("rat" in hss); 4872 assert("fly" in hss); 4873 assert("bee" in hss); 4874 4875 assert(hss.insert("ant")); 4876 assert("dog" !in hss); 4877 assert("cat" in hss); 4878 assert("rat" in hss); 4879 assert("fly" in hss); 4880 assert("bee" in hss); 4881 assert("ant" in hss); 4882 assert("fox" !in hss); 4883 4884 assert(hss.insert("fox")); 4885 assert("dog" !in hss); 4886 assert("cat" in hss); 4887 assert("rat" in hss); 4888 assert("fly" in hss); 4889 assert("bee" in hss); 4890 assert("ant" in hss); 4891 assert("fox" in hss); 4892 4893 assert(hss.insert("bat")); 4894 assert("dog" !in hss); 4895 assert("cat" in hss); 4896 assert("rat" in hss); 4897 assert("fly" in hss); 4898 assert("bee" in hss); 4899 assert("ant" in hss); 4900 assert("fox" in hss); 4901 assert("bat" in hss); 4902 4903 assert(hss.insert("cow")); 4904 assert("dog" !in hss); 4905 assert("cat" in hss); 4906 assert("rat" in hss); 4907 assert("fly" in hss); 4908 assert("bee" in hss); 4909 assert("ant" in hss); 4910 assert("fox" in hss); 4911 assert("bat" in hss); 4912 assert("cow" in hss); 4913 4914 assert(hss.remove("bat")); 4915 assert("bat" !in hss); 4916 4917 hss.clear; 4918 assert(hss.count == 0); 4919 4920 import std.algorithm: among; 4921 hss.reserve(20); 4922 assert(hss.insert("cow")); 4923 assert(hss.insert("yak")); 4924 auto r = hss.byKey; 4925 assert(!r.empty); 4926 assert((r.front).among("cow","yak")); 4927 r.popFront; 4928 assert(!r.empty); 4929 assert((r.front).among("cow","yak")); 4930 r.popFront; 4931 assert(r.empty); 4932 4933 assert(hss.bucketCount == 32); 4934 hss.minimize; 4935 assert(hss.bucketCount == 2); 4936 4937 destruct(hss); 4938 } 4939 4940 @nogc unittest 4941 { 4942 HashSet_AB!int hsi; 4943 assert(hsi.byKey.empty); 4944 destruct(hsi); 4945 } 4946 4947 /** 4948 * A manually managed hashmap that uses buckets to solve the collisions. 4949 * 4950 * Params: 4951 * K = the key type. 4952 * V = the value type. 4953 * hasherFun = The hashing function, a $(D size_t(K value);) function, 4954 * literal delegate or lambda. 4955 */ 4956 struct HashMap_AB(K, V, alias hasherFun = fnv1) 4957 { 4958 static assert (is(typeof( (){size_t r = hasherFun(K.init);} )), 4959 "invalid hash function"); 4960 static assert (!is(K == void), 4961 "invalid Key type"); 4962 static assert (!is(V == void), 4963 "invalid Value type"); 4964 4965 private: 4966 4967 alias HashMapT = typeof(this); 4968 alias BucketT = ArrayBucket!(K,V); 4969 @NoGc Array!BucketT _buckets; 4970 size_t _count; 4971 4972 pragma(inline, true) 4973 size_t hasher(KK)(auto ref KK key) @nogc 4974 { 4975 return hasherFun(key) & (_buckets.length - 1); 4976 } 4977 4978 void reHash()() 4979 { 4980 //_count = 0; 4981 Array!BucketT old = _buckets; 4982 foreach (immutable i; 0.._buckets.length) 4983 _buckets[i].clear; 4984 foreach (immutable i; 0..old.length) 4985 { 4986 foreach (immutable j; 0..old[i]._array.length) 4987 { 4988 const h = hasher(old[i]._array[j][0]); 4989 _buckets[h].insert(old[i]._array[j][0], old[i]._array[j][1]); 4990 } 4991 } 4992 destruct(old); 4993 } 4994 4995 public: 4996 4997 ~this() @nogc 4998 { 4999 destruct(_buckets); 5000 } 5001 5002 /** 5003 * Tries to insert a key-value pair in the set. 5004 * 5005 * Params: 5006 * mode = If set to $(D imExpand) then reserves a slot else 5007 * if set to $(D imReserved) assumes a previous call to $(D reserve()). 5008 * key = The key. 5009 * value = The value. 5010 * Throws: 5011 * An $(D OutOfMemoryError) if an internal call to $(D reserve()) fails. 5012 * Returns: 5013 * If the key is added or if it's already included then returns $(D true), 5014 * otherwise $(D false). 5015 */ 5016 bool insert(alias mode = imExpand)(ref K key, auto ref V value) @nogc 5017 if (isImplicitlyConvertible!(typeof(mode), bool)) 5018 { 5019 bool result; 5020 if (!_buckets.length) 5021 reserve(1); 5022 if (key !in this) 5023 { 5024 result = true; 5025 static if (mode) 5026 reserve(1); 5027 const size_t h = hasher(key); 5028 assert(h < _buckets.length); 5029 _buckets[h].insert(key, value); 5030 ++_count; 5031 } 5032 else 5033 { 5034 result = true; 5035 const size_t h = hasher(key); 5036 assert(h < _buckets.length); 5037 _buckets[h].remove(key); 5038 _buckets[h].insert(key, value); 5039 } 5040 return result; 5041 } 5042 5043 /// ditto 5044 bool insert(alias mode = imExpand)(K key, V value) @nogc 5045 if (isImplicitlyConvertible!(typeof(mode), bool)) 5046 { 5047 return insert!mode(key, value); 5048 } 5049 5050 /** 5051 * Tries to remove a key from the set. 5052 * 5053 * Returns: 5054 * $(D true) if the key was included otherwise $(D false). 5055 */ 5056 bool remove()(auto ref K key) @nogc 5057 { 5058 const size_t h = hasher(key); 5059 const bool result = _buckets[h].remove(key); 5060 if (result) 5061 --_count; 5062 return result; 5063 } 5064 5065 /** 5066 * Reserves buckets for at least N supplemental key-value pairs. 5067 * 5068 * Throws: 5069 * An $(D OutOfMemoryError) if the reallocation fails. 5070 * Params: 5071 * value = The count of additional slots to reserve. 5072 */ 5073 void reserve()(size_t value) @nogc 5074 { 5075 import std.math: nextPow2; 5076 const size_t nl = nextPow2(_count + value); 5077 if (nl > _buckets.length) 5078 { 5079 _buckets.length = nl; 5080 reHash(); 5081 } 5082 } 5083 5084 /** 5085 * Minimizes the memory used by the map. 5086 * 5087 * Throws: 5088 * An $(D OutOfMemoryError) if the reallocation fails. 5089 */ 5090 void minimize()() 5091 { 5092 import std.math: nextPow2; 5093 const size_t nl = nextPow2(_count-1); 5094 5095 if (nl < _buckets.length) 5096 { 5097 Array!BucketT old = _buckets; 5098 clear; 5099 _buckets.length = nl; 5100 foreach (immutable i; 0..old.length) 5101 foreach (immutable j; 0..old[i]._array.length) 5102 { 5103 insert!false(old[i]._array[j][0], old[i]._array[j][1]); 5104 } 5105 destruct(old); 5106 } 5107 } 5108 5109 /** 5110 * Empties the map. 5111 */ 5112 void clear() @nogc 5113 { 5114 _buckets.length = 0; 5115 _buckets.length = 2; 5116 _count = 0; 5117 } 5118 5119 /** 5120 * Retrieves the value associated to a key. 5121 * 5122 * Params: 5123 * key = The key. 5124 * Returns: 5125 * $(D null) if the key is not present otherwise a pointer to associated value. 5126 */ 5127 V* opBinaryRight(string op : "in", KK)(auto ref KK key) 5128 { 5129 V* result; 5130 if (_buckets.length) 5131 result = _buckets[hasher(key)].getValue(key); 5132 return result; 5133 } 5134 5135 /** 5136 * Support for appending an element. 5137 * 5138 * Forwards $(D insert()) with a default initialized value. 5139 * 5140 * Params: 5141 * key = The key to insert. 5142 * Returns: 5143 * If the key is added or if it's already included then returns $(D true), 5144 * otherwise $(D false). 5145 */ 5146 bool opOpAssign(string op : "~")(auto ref K key) 5147 { 5148 return insert(key, V.init); 5149 } 5150 5151 /** 5152 * Provides an access to the buckets. 5153 * 5154 * Params: 5155 * index = The bucket index. Must be in the $(D 0..bucketCount()) range. 5156 * Returns: 5157 * A never null pointer to a bucket. 5158 */ 5159 BucketT* bucket(const size_t index) pure nothrow @nogc 5160 { 5161 return &_buckets[index]; 5162 } 5163 5164 /** 5165 * Support for retrieving a value using the array syntax. 5166 */ 5167 auto ref V opIndex(KK)(auto ref KK key) 5168 { 5169 import std.stdio; 5170 return *(key in this); 5171 } 5172 5173 /** 5174 * Support for assigning using the array syntax. 5175 */ 5176 void opIndexAssign(KK)(auto ref V value, auto ref KK key) 5177 { 5178 insert(key, value); 5179 } 5180 5181 /** 5182 * Support for assigning to the value when the value is itself an AA. 5183 * 5184 * Note that this function only exists to port code that uses the runtime AA 5185 * with the syntax $(D aa[k_for_value][k_for_value_of_value] = stuff;). 5186 */ 5187 void opIndexAssign(V2, KK1, KK2)(auto ref V2 value, auto ref KK1 key1, auto ref KK2 key2) 5188 { 5189 if (auto v = key1 in this) 5190 { 5191 v.insert(key2, value); 5192 } 5193 else 5194 { 5195 V v; v.reserve(1); 5196 v.insert(key2, value); 5197 insert!imReserved(key1, v); 5198 } 5199 } 5200 5201 /** 5202 * Support for the assignment operators on a value. 5203 */ 5204 void opIndexOpAssign(string op, VV, KK)(auto ref VV value, auto ref KK key) 5205 { 5206 if (auto p = key in this) 5207 { 5208 mixin("(*p) " ~ op ~ "= value;"); 5209 } 5210 else 5211 { 5212 V v; 5213 mixin("v" ~ op ~ "= value;"); 5214 insert(key, v); 5215 } 5216 } 5217 5218 /** 5219 * Returns: an input range that allows to iterate the key-value pairs. 5220 */ 5221 auto byKeyValue() 5222 { 5223 return RangeForAbSet!HashMapT(&this); 5224 } 5225 5226 /** 5227 * Returns: an input range that allows to iterate the keys. 5228 */ 5229 auto byKey() 5230 { 5231 return RangeForAbSet!(HashMapT,rngMapByKey)(&this); 5232 } 5233 5234 /** 5235 * Returns: an input range that allows to iterate the values. 5236 */ 5237 auto byValue() 5238 { 5239 return RangeForAbSet!(HashMapT,rngMapByValue)(&this); 5240 } 5241 5242 /** 5243 * Returns: the elements count. 5244 */ 5245 size_t count() pure nothrow @nogc {return _count;} 5246 5247 /** 5248 * Returns the buckets count. 5249 */ 5250 size_t bucketCount() pure nothrow @nogc {return _buckets.length;} 5251 5252 /** 5253 * Returns: the collisions count. 5254 */ 5255 size_t collisions() pure nothrow @nogc 5256 { 5257 size_t result; 5258 foreach(immutable i; 0.._buckets.length) 5259 result += _buckets[i]._array.length > 1 ? 5260 _buckets[i]._array.length - 1 : 0; 5261 return result; 5262 } 5263 } 5264 /// 5265 @nogc unittest 5266 { 5267 HashMap_AB!(string, size_t) stock; 5268 // can insert up to 16 elements without reallocation 5269 stock.reserve(15); 5270 assert(stock.bucketCount == 16); 5271 // appends elements, various syntax allowed 5272 stock.insert("pen", 8); 5273 stock["gum"] += 32; 5274 stock["ruler"] += 12; 5275 stock ~= "tape roll"; 5276 // test for inclusion, various syntax allowed 5277 assert("gum" in stock); 5278 assert(stock["ruler"] == 12); 5279 assert(stock["tape roll"] == 0); 5280 // remove something 5281 stock.remove("ruler"); 5282 assert("ruler" !in stock); 5283 // empties and frees memory 5284 stock.clear; 5285 // manually managed implies to destruct by hand 5286 import iz.memory; 5287 destruct(stock); 5288 } 5289 5290 @nogc unittest 5291 { 5292 HashMap_AB!(string, int) hmsi; 5293 5294 hmsi.insert("cat", 0); 5295 hmsi.insert("dog", 1); 5296 hmsi.insert("pig", 2); 5297 assert(hmsi.count == 3); 5298 assert(*("cat" in hmsi) == 0); 5299 assert(*("dog" in hmsi) == 1); 5300 assert(*("pig" in hmsi) == 2); 5301 assert("bat" !in hmsi); 5302 assert("bug" !in hmsi); 5303 5304 hmsi["bat"] = 3; 5305 hmsi["bug"] = 4; 5306 assert(hmsi.count == 5); 5307 assert(*("cat" in hmsi) == 0); 5308 assert(*("dog" in hmsi) == 1); 5309 assert(*("pig" in hmsi) == 2); 5310 assert(*("bat" in hmsi) == 3); 5311 assert(*("bug" in hmsi) == 4); 5312 5313 assert(hmsi.remove("cat")); 5314 assert(hmsi.count == 4); 5315 assert("cat" !in hmsi); 5316 assert(*("dog" in hmsi) == 1); 5317 assert(*("pig" in hmsi) == 2); 5318 assert(*("bat" in hmsi) == 3); 5319 assert(*("bug" in hmsi) == 4); 5320 5321 hmsi["owl"] = 5; 5322 assert(hmsi.count == 5); 5323 assert("cat" !in hmsi); 5324 assert(*("dog" in hmsi) == 1); 5325 assert(*("pig" in hmsi) == 2); 5326 assert(*("bat" in hmsi) == 3); 5327 assert(*("bug" in hmsi) == 4); 5328 assert(*("owl" in hmsi) == 5); 5329 5330 hmsi.clear; 5331 assert(hmsi.count == 0); 5332 assert("cat" !in hmsi); 5333 assert("dog" !in hmsi); 5334 assert("pig" !in hmsi); 5335 assert("bat" !in hmsi); 5336 assert("bug" !in hmsi); 5337 assert("owl" !in hmsi); 5338 5339 hmsi["bat"] = 3; 5340 hmsi["bug"] = 4; 5341 assert(hmsi.count == 2); 5342 assert(hmsi["bat"] == 3); 5343 assert(hmsi["bug"] == 4); 5344 hmsi["bat"] = 4; 5345 hmsi["bug"] = 3; 5346 assert(hmsi.count == 2); 5347 assert(hmsi["bat"] == 4); 5348 assert(hmsi["bug"] == 3); 5349 5350 destruct(hmsi); 5351 } 5352 5353 @nogc unittest 5354 { 5355 HashMap_AB!(int, int) aa; 5356 assert(1 !in aa); 5357 } 5358 5359 @nogc unittest 5360 { 5361 HashMap_AB!(int, int) aa; 5362 aa[0] = 0; 5363 } 5364 5365 @nogc unittest 5366 { 5367 HashMap_AB!(string, void*) aa0; 5368 aa0[""] = null; 5369 HashMap_AB!(void*, string) aa1; 5370 //aa1[null] = ""; 5371 } 5372 5373 unittest 5374 { 5375 HashSet_AB!(const(char)[]) aa0; 5376 string s = "s"; 5377 aa0.insert(s); 5378 } 5379 5380 @nogc unittest 5381 { 5382 struct Foo {} 5383 HashMap_AB!(Foo,Foo) a1; 5384 class Bar 5385 { 5386 override bool opEquals(Object o) const pure @nogc nothrow {return o is this;} 5387 } 5388 {HashMap_AB!(Bar,Bar) a2;} 5389 {HashMap_LP!(Bar,Bar) a2;} 5390 { 5391 HashSet_AB!(Bar) a2; 5392 Bar b = construct!Bar; 5393 a2.insert(b); 5394 a2.remove(b); 5395 destruct!true(b); 5396 } 5397 { 5398 HashSet_LP!(Bar) a2; 5399 Bar b = construct!Bar; 5400 a2.insert(b); 5401 a2.remove(b); 5402 destruct!true(b); 5403 } 5404 } 5405 5406 //TODO-cHashMaps: proper support for post++/-- 5407 version (none) unittest 5408 { 5409 { 5410 HashMap_LP!(string, size_t) aa; 5411 aa["0"] += 1; 5412 assert(aa["0"] == 1); 5413 aa["0"]++ ; 5414 assert(aa["0"] == 2); 5415 } 5416 { 5417 //HashMap_AB!(string, size_t) aa; 5418 //aa["0"]++; 5419 //assert(aa["0"] == 1); 5420 //aa["0"]++ ; 5421 //assert(aa["0"] == 2); 5422 //aa["1"]++; 5423 //assert(aa["1"] == 1); 5424 //aa["1"]-- ; 5425 //assert(aa["1"] == 0); 5426 } 5427 { 5428 //HashMap_LP!(string, size_t) aa; 5429 //aa["0"]++; 5430 //assert(aa["0"] == 1); 5431 //aa["0"]++; 5432 //assert(aa["0"] == 2); 5433 //aa["1"]++; 5434 //assert(aa["1"] == 1); 5435 //aa["1"]-- ; 5436 //assert(aa["1"] == 0); 5437 } 5438 } 5439 5440 unittest 5441 { 5442 HashMap_AB!(string, int) aa; 5443 aa.insert("0",2); 5444 aa["0"] += 0; 5445 aa.insert("1",2); 5446 assert("1" in aa); 5447 aa["1"] += 0; 5448 assert(aa.count == 2); 5449 auto rng = aa.byValue; 5450 assert(!rng.empty); 5451 assert(rng.front == 2); 5452 rng.popFront; 5453 assert(!rng.empty); 5454 assert(rng.front == 2); 5455 rng.popFront; 5456 assert(rng.empty); 5457 destruct(aa); 5458 } 5459 5460 unittest 5461 { 5462 { 5463 alias AA1 = HashMap_AB!(string, int); 5464 HashMap_AB!(string, AA1) aa; 5465 // note: runtime AA syntax is `aa["0"]["0"] = 42;` 5466 aa["0", "0"] = 42; 5467 auto aaOf_0 = aa["0"]; 5468 assert(aaOf_0["0"] == 42); 5469 destruct(aa); 5470 } 5471 { 5472 alias AA1 = HashMap_LP!(string, int); 5473 HashMap_LP!(string, AA1) aa; 5474 aa["0", "0"] = 42; 5475 auto aaOf_0 = aa["0"]; 5476 assert(aaOf_0["0"] == 42); 5477 destruct(aa); 5478 } 5479 } 5480