1 /** 2 * Associative Array utility functions 3 * 4 * License: 5 * This Source Code Form is subject to the terms of 6 * the Mozilla Public License, v. 2.0. If a copy of 7 * the MPL was not distributed with this file, You 8 * can obtain one at http://mozilla.org/MPL/2.0/. 9 * 10 * Authors: 11 * Vladimir Panteleev <ae@cy.md> 12 */ 13 14 module ae.utils.aa; 15 16 import std.algorithm; 17 import std.range; 18 import std.traits; 19 import std.typecons; 20 21 import ae.utils.meta : progn, BoxVoid, BoxedVoid; 22 23 // *************************************************************************** 24 25 /// Polyfill for object.require 26 static if (!__traits(hasMember, object, "require")) 27 ref V require(K, V)(ref V[K] aa, K key, lazy V value = V.init) 28 { 29 auto p = key in aa; 30 if (p) 31 return *p; 32 return aa[key] = value; 33 } 34 35 debug(ae_unittest) unittest 36 { 37 int[int] aa; 38 aa.require(1, 2); 39 assert(aa[1] == 2); 40 aa.require(2, 3) = 4; 41 assert(aa[2] == 4); 42 aa.require(1, 5); 43 assert(aa[1] == 2); 44 aa.require(1, 6) = 7; 45 assert(aa[1] == 7); 46 } 47 48 static if (!__traits(hasMember, object, "update")) 49 { 50 /// Polyfill for object.update 51 void updatePolyfill(K, V, C, U)(ref V[K] aa, K key, scope C create, scope U update) 52 if (is(typeof(create()) : V) && is(typeof(update(aa[K.init])) : V)) 53 { 54 auto p = key in aa; 55 if (p) 56 *p = update(*p); 57 else 58 aa[key] = create(); 59 } 60 61 /// Work around https://issues.dlang.org/show_bug.cgi?id=15795 62 alias update = updatePolyfill; 63 } 64 65 // https://github.com/dlang/druntime/pull/3012 66 private enum haveObjectUpdateWithVoidUpdate = is(typeof({ 67 int[int] aa; 68 .object.update(aa, 0, { return 0; }, (ref int v) { }); 69 })); 70 71 static if (!haveObjectUpdateWithVoidUpdate) 72 { 73 /// Polyfill for object.update with void update function 74 void updateVoid(K, V, C, U)(ref V[K] aa, K key, scope C create, scope U update) 75 if (is(typeof(create()) : V) && is(typeof(update(aa[K.init])) == void)) 76 { 77 // We can polyfill this in two ways. 78 // What's more expensive, copying the value, or a second key lookup? 79 enum haveObjectUpdate = __traits(hasMember, object, "update"); 80 enum valueIsExpensiveToCopy = V.sizeof > string.sizeof 81 || hasElaborateCopyConstructor!V 82 || hasElaborateDestructor!V; 83 static if (haveObjectUpdate && !valueIsExpensiveToCopy) 84 { 85 .object.update(aa, key, 86 delegate V() { return create(); }, 87 (ref V v) { update(v); return v; }); 88 } 89 else 90 { 91 auto p = key in aa; 92 if (p) 93 update(*p); 94 else 95 aa[key] = create(); 96 } 97 } 98 99 /// Work around https://issues.dlang.org/show_bug.cgi?id=15795 100 alias update = updateVoid; 101 } 102 else 103 alias updateVoid = object.update; /// Use `object.update` for void update function 104 105 // Inject overload 106 static if (__traits(hasMember, object, "update")) 107 private alias update = object.update; 108 109 // *************************************************************************** 110 111 /// Get a value from an AA, and throw an exception (not an error) if not found 112 ref auto aaGet(AA, K)(auto ref AA aa, auto ref K key) 113 if (is(typeof(key in aa))) 114 { 115 import std.conv; 116 117 auto p = key in aa; 118 if (p) 119 return *p; 120 else 121 static if (is(typeof(text(key)))) 122 throw new Exception("Absent value: " ~ text(key)); 123 else 124 throw new Exception("Absent value"); 125 } 126 127 /// If key is not in aa, add it with defaultValue. 128 /// Returns a reference to the value corresponding to key. 129 ref V getOrAdd(K, V)(ref V[K] aa, auto ref K key, auto ref V defaultValue) 130 { 131 return aa.require(key, defaultValue); 132 } 133 134 /// ditto 135 ref V getOrAdd(K, V)(ref V[K] aa, auto ref K key) 136 { 137 return getOrAdd(aa, key, V.init); 138 } 139 140 debug(ae_unittest) unittest 141 { 142 int[int] aa; 143 aa.getOrAdd(1, 2) = 3; 144 assert(aa[1] == 3); 145 assert(aa.getOrAdd(1, 4) == 3); 146 } 147 148 /// If key is not in aa, add it with the given value, and return true. 149 /// Otherwise, return false. 150 bool addNew(K, V)(ref V[K] aa, auto ref K key, auto ref V value) 151 { 152 bool added = void; 153 updateVoid(aa, key, 154 delegate V ( ) { added = true ; return value; }, 155 delegate void(ref V v) { added = false; }, 156 ); 157 return added; 158 } 159 160 debug(ae_unittest) unittest 161 { 162 int[int] aa; 163 assert( aa.addNew(1, 2)); 164 assert(!aa.addNew(1, 3)); 165 assert(aa[1] == 2); 166 } 167 168 debug(ae_unittest) unittest 169 { 170 OrderedMap!(int, int) aa; 171 assert( aa.addNew(1, 2)); 172 assert(!aa.addNew(1, 3)); 173 assert(aa[1] == 2); 174 } 175 176 // *************************************************************************** 177 178 /// Key/value pair 179 struct KeyValuePair(K, V) { K key; /***/ V value; /***/ } 180 181 /// Get key/value pairs from AA 182 deprecated KeyValuePair!(K, V)[] pairs(K, V)(V[K] aa) 183 { 184 KeyValuePair!(K, V)[] result; 185 foreach (key, value; aa) 186 result ~= KeyValuePair!(K, V)(key, value); 187 return result; 188 } 189 190 /// Get key/value pairs from AA, sorted by keys 191 KeyValuePair!(K, V)[] sortedPairs(K, V)(V[K] aa) 192 { 193 KeyValuePair!(K, V)[] result; 194 foreach (key; aa.keys.sort) 195 result ~= KeyValuePair!(K, V)(key, aa[key]); 196 return result; 197 } 198 199 /// Get values from AA, sorted by keys 200 V[] sortedValues(K, V)(in V[K] aa) 201 { 202 V[] result; 203 foreach (key; aa.keys.sort()) 204 result ~= aa[key]; 205 return result; 206 } 207 208 /// Merge source into target. Return target. 209 V[K] merge(K, V)(auto ref V[K] target, V[K] source) 210 { 211 foreach (k, v; source) 212 target[k] = v; 213 return target; 214 } 215 216 debug(ae_unittest) unittest 217 { 218 int[int] target; 219 int[int] source = [2:4]; 220 merge(target, source); 221 assert(source == target); 222 223 target = [1:1, 2:2, 3:3]; 224 merge(target, source); 225 assert(target == [1:1, 2:4, 3:3]); 226 227 assert(merge([1:1], [2:2]) == [1:1, 2:2]); 228 } 229 230 debug(ae_unittest) unittest 231 { 232 ubyte[][string] a, b; 233 merge(a, b); 234 } 235 236 /// Slurp a range of two elements (or two-element struct/class) into an AA. 237 auto toAA(R)(R r) 238 if (is(typeof(r.front[1]))) 239 { 240 alias K = typeof(r.front[0]); 241 alias V = typeof(r.front[1]); 242 V[K] result; 243 foreach (pair; r) 244 { 245 assert(pair.length == 2); 246 result[pair[0]] = pair[1]; 247 } 248 return result; 249 } 250 251 /// ditto 252 auto toAA(R)(R r) 253 if (is(typeof(r.front.tupleof)) && r.front.tupleof.length == 2 && !is(typeof(r.front[1]))) 254 { 255 return r.map!(el => tuple(el.tupleof)).toAA(); 256 } 257 258 debug(ae_unittest) deprecated unittest 259 { 260 assert([[2, 4]].toAA() == [2:4]); 261 assert([2:4].pairs.toAA() == [2:4]); 262 } 263 264 /// Ensure that arr is non-null if empty. 265 V[K] nonNull(K, V)(V[K] aa) 266 { 267 if (aa !is null) 268 return aa; 269 aa[K.init] = V.init; 270 aa.remove(K.init); 271 assert(aa !is null); 272 return aa; 273 } 274 275 debug(ae_unittest) unittest 276 { 277 int[int] aa; 278 assert(aa is null); 279 aa = aa.nonNull; 280 assert(aa !is null); 281 assert(aa.length == 0); 282 } 283 284 // *************************************************************************** 285 286 // Helpers for HashCollection 287 private 288 { 289 alias Void = BoxedVoid; 290 static assert(Void.sizeof == 0); 291 292 // Abstraction layer for single/multi-value type holding one or many T. 293 // Optimizer representation for Void. 294 struct SingleOrMultiValue(bool multi, T) 295 { 296 alias ValueType = Select!(multi, 297 // multi==true 298 Select!(is(T == Void), 299 size_t, // "store" the items by keeping track of their count only. 300 T[], 301 ), 302 303 // multi==false 304 Select!(is(T == Void), 305 Void, 306 T[1], 307 ), 308 ); 309 310 // Using free functions instead of struct methods, 311 // as structs always have non-zero size. 312 static: 313 314 size_t length(ref const ValueType v) nothrow 315 { 316 static if (is(T == Void)) 317 static if (multi) 318 return v; // count 319 else 320 return 1; 321 else 322 return v.length; // static or dynamic array 323 } 324 } 325 } 326 327 /// Base type for ordered/unordered single-value/multi-value map/set 328 /*private*/ struct HashCollection(K, V, bool ordered, bool multi) 329 { 330 private: 331 enum bool haveValues = !is(V == void); // Not a set 332 333 // The type for values used when a value variable is needed 334 alias ValueVarType = Select!(haveValues, V, Void); 335 336 // The type of a single element of the values of `this.lookup`. 337 // When ordered==true, we use size_t (index into `this.items`). 338 alias LookupItem = Select!(ordered, size_t, ValueVarType); 339 340 // The type of the values of `this.lookup`. 341 alias SM = SingleOrMultiValue!(multi, LookupItem); 342 alias LookupValue = SM.ValueType; 343 344 // Return type of assign operations, "in" operator, etc. 345 static if (haveValues) 346 alias ReturnType = V; 347 else 348 alias ReturnType = void; 349 enum haveReturnType = !is(ReturnType == void); 350 351 static if (ordered) 352 alias OrderIndex = size_t; 353 else 354 alias OrderIndex = void; 355 356 // DWIM: a[k] should mean key lookup for maps, 357 // otherwise index lookup for ordered sets. 358 static if (haveValues) 359 { 360 alias OpIndexKeyType = K; 361 alias OpIndexValueType = V; // also the return type of opIndex 362 } 363 else 364 { 365 static if (ordered) 366 { 367 alias OpIndexKeyType = size_t; 368 alias OpIndexValueType = K; 369 } 370 else 371 { 372 alias OpIndexKeyType = void; 373 alias OpIndexValueType = void; 374 } 375 } 376 enum haveIndexing = !is(OpIndexKeyType == void); 377 static assert(haveIndexing == haveValues || ordered); 378 alias IK = OpIndexKeyType; 379 alias IV = OpIndexValueType; 380 381 // The contract we try to follow is that adding/removing items in 382 // one copy of the object will not affect other copies. 383 // Therefore, when we have array fields, make sure they are dup'd 384 // on copy, so that we don't trample older copies' data. 385 enum bool needDupOnCopy = ordered; 386 387 static if (ordered) 388 /* */ ref inout(ReturnType) lookupToReturnValue(in LookupItem lookupItem) inout { return items[lookupItem].returnValue; } 389 else 390 static if (haveValues) 391 static ref inout(ReturnType) lookupToReturnValue(ref inout(LookupItem) lookupItem) { return lookupItem ; } 392 else 393 static ref inout(ReturnType) lookupToReturnValue(ref inout(LookupItem) lookupItem) { } 394 395 static if (ordered) 396 /* */ ref inout(IV) lookupToIndexValue(in LookupItem lookupItem) inout { return items[lookupItem].indexValue; } 397 else 398 static if (haveValues) 399 static ref inout(IV) lookupToIndexValue(ref inout(LookupItem) lookupItem) { return lookupItem ; } 400 else 401 static ref inout(IV) lookupToIndexValue(ref inout(LookupItem) lookupItem) { } 402 403 // *** Data *** 404 405 // This is used for all key hash lookups. 406 LookupValue[K] lookup; 407 408 static if (ordered) 409 { 410 struct Item 411 { 412 K key; 413 ValueVarType value; 414 415 static if (haveValues) 416 alias /*ReturnType*/ returnValue = value; 417 else 418 @property ReturnType returnValue() const {} 419 420 static if (haveValues) 421 alias /*OpIndexValueType*/ indexValue = value; 422 else 423 static if (ordered) 424 alias /*OpIndexValueType*/ indexValue = key; 425 } 426 Item[] items; 427 428 enum bool canDup = is(typeof(lookup.dup)) && is(typeof(items.dup)); 429 } 430 else 431 { 432 enum bool canDup = is(typeof(lookup.dup)); 433 } 434 435 public: 436 437 // *** Lifetime *** 438 439 /// Postblit 440 static if (needDupOnCopy) 441 { 442 static if (canDup) 443 this(this) 444 { 445 lookup = lookup.dup; 446 items = items.dup; 447 } 448 else 449 @disable this(this); 450 } 451 452 /// Create shallow copy 453 static if (canDup) 454 typeof(this) dup() 455 { 456 static if (needDupOnCopy) 457 return this; 458 else 459 { 460 typeof(this) copy; 461 copy.lookup = lookup.dup; 462 static if (ordered) 463 copy.items = items.dup; 464 return copy; 465 } 466 } 467 468 // *** Conversions (from) *** 469 470 /// Construct from something else 471 this(Input)(Input input) 472 if (is(typeof(opAssign(input)))) 473 { 474 opAssign(input); 475 } 476 477 /// Null assignment 478 ref typeof(this) opAssign(typeof(null) _) 479 { 480 clear(); 481 return this; 482 } 483 484 /// Convert from an associative type 485 ref typeof(this) opAssign(AA)(AA aa) 486 if (haveValues 487 && !is(AA : typeof(this)) 488 && is(typeof({ foreach (ref k, ref v; aa) add(k, v); }))) 489 { 490 clear(); 491 foreach (ref k, ref v; aa) 492 add(k, v); 493 return this; 494 } 495 496 /// Convert from an associative type of multiple items 497 ref typeof(this) opAssign(AA)(AA aa) 498 if (haveValues 499 && multi 500 && !is(AA : typeof(this)) 501 && is(typeof({ foreach (ref k, ref vs; aa) foreach (ref v; vs) add(k, v); }))) 502 { 503 clear(); 504 foreach (ref k, ref vs; aa) 505 foreach (ref v; vs) 506 add(k, v); 507 return this; 508 } 509 510 /// Convert from a range of tuples 511 ref typeof(this) opAssign(R)(R input) 512 if (haveValues 513 && is(typeof({ foreach (ref pair; input) add(pair[0], pair[1]); })) 514 && !is(typeof({ foreach (ref k, ref v; input) add(k, v); })) 515 && is(typeof(input.front.length)) 516 && input.front.length == 2) 517 { 518 clear(); 519 foreach (ref pair; input) 520 add(pair[0], pair[1]); 521 return this; 522 } 523 524 /// Convert from a range of key/value pairs 525 ref typeof(this) opAssign(R)(R input) 526 if (haveValues 527 && is(typeof({ foreach (ref pair; input) add(pair.key, pair.value); })) 528 && !is(typeof({ foreach (ref k, ref v; input) add(k, v); }))) 529 { 530 clear(); 531 foreach (ref pair; input) 532 add(pair.key, pair.value); 533 return this; 534 } 535 536 /// Convert from a range of values 537 ref typeof(this) opAssign(R)(R input) 538 if (!haveValues 539 && !is(R : typeof(this)) 540 && is(typeof({ foreach (ref v; input) add(v); }))) 541 { 542 clear(); 543 foreach (ref v; input) 544 add(v); 545 return this; 546 } 547 548 // *** Conversions (to) *** 549 550 /// Convert to bool (true if non-null) 551 bool opCast(T)() const 552 if (is(T == bool)) 553 { 554 return lookup !is null; 555 } 556 557 /// Convert to D associative array 558 static if (!ordered) 559 { 560 const(LookupValue[K]) toAA() const 561 { 562 return lookup; 563 } 564 565 static if (is(typeof(lookup.dup))) 566 LookupValue[K] toAA() 567 { 568 return lookup.dup; 569 } 570 571 deprecated alias items = toAA; 572 } 573 574 // *** Query (basic) *** 575 576 /// True when there are no items. 577 bool empty() pure const nothrow @nogc @trusted 578 { 579 static if (ordered) 580 return items.length == 0; // optimization 581 else 582 return lookup.byKey.empty; // generic version 583 } 584 585 /// Total number of items, including with duplicate keys. 586 size_t length() pure const nothrow @nogc @trusted 587 { 588 static if (ordered) 589 return items.length; // optimization 590 else 591 static if (!multi) 592 return lookup.length; // optimization 593 else // generic version 594 { 595 size_t result; 596 foreach (ref v; lookup.byValue) 597 result += SM.length(v); 598 return result; 599 } 600 } 601 602 // *** Query (by key) *** 603 604 /// Check if item with this key has been added. 605 /// When applicable, return a pointer to the last value added with this key. 606 Select!(haveReturnType, inout(ReturnType)*, bool) opBinaryRight(string op : "in", _K)(auto ref _K key) inout 607 if (is(typeof(key in lookup))) 608 { 609 enum missValue = select!haveReturnType(null, false); 610 611 auto p = key in lookup; 612 if (!p) 613 return missValue; 614 615 static if (haveReturnType) 616 return &lookupToIndexValue((*p)[$-1]); 617 else 618 return true; 619 } 620 621 // *** Query (by index) *** 622 623 /// Index access (for ordered collections). 624 /// For maps, returns the key. 625 static if (ordered) 626 ref inout(K) at()(size_t i) inout 627 { 628 return items[i].key; 629 } 630 631 /// ditto 632 static if (ordered) 633 auto ref inout(K) getAt()(size_t i, auto ref K defaultValue) inout 634 { 635 return i < items.length ? items[i].key : defaultValue; 636 } 637 638 // *** Query (by key/index - DWIM) *** 639 640 /// Index operator. 641 /// The key must exist. Indexing with a key which does not exist 642 /// is an error. 643 static if (haveIndexing) 644 ref inout(IV) opIndex()(auto ref const IK k) inout 645 { 646 static if (haveValues) 647 return lookupToIndexValue(lookup[k][$-1]); 648 else 649 return items[k].indexValue; 650 } 651 652 /// Retrieve last value associated with key, or `defaultValue` if none. 653 static if (haveIndexing) 654 { 655 static if (haveValues) 656 auto ref IV get(this This, KK)(auto ref KK k, auto ref IV defaultValue) 657 if (is(typeof(k in lookup))) 658 { 659 auto p = k in lookup; 660 return p ? lookupToIndexValue((*p)[$-1]) : defaultValue; 661 } 662 else 663 auto ref IV get(this This, KK)(auto ref KK k, auto ref IV defaultValue) 664 if (is(typeof(items[k]))) 665 { 666 return k < items.length ? items[k].returnValue : defaultValue; 667 } 668 } 669 670 // *** Query (ranges) *** 671 672 /// Return a range which iterates over key/value pairs. 673 static if (haveValues) 674 auto byKeyValue(this This)() 675 { 676 static if (ordered) 677 return items; 678 else 679 { 680 return lookup 681 .byKeyValue 682 .map!(pair => 683 pair 684 .value 685 .map!(value => KeyValuePair!(K, V)(pair.key, value)) 686 ) 687 .joiner; 688 } 689 } 690 691 /// ditto 692 static if (haveValues) 693 auto byPair(this This)() 694 { 695 return byKeyValue 696 .map!(pair => tuple!("key", "value")(pair.key, pair.value)); 697 } 698 699 /// Return a range which iterates over all keys. 700 /// Duplicate keys will occur several times in the range. 701 auto byKey(this This)() 702 { 703 static if (ordered) 704 { 705 static ref getKey(MItem)(ref MItem item) { return item.key; } 706 return items.map!getKey; 707 } 708 else 709 { 710 return lookup 711 .byKeyValue 712 .map!(pair => 713 pair.key.repeat(SM.length(pair.value)) 714 ) 715 .joiner; 716 } 717 } 718 719 /// Return a range which iterates over all values. 720 static if (haveValues) 721 auto byValue(this This)() 722 { 723 static if (ordered) 724 { 725 static ref getValue(MItem)(ref MItem item) { return item.value; } 726 return items.map!getValue; 727 } 728 else 729 { 730 return lookup 731 .byKeyValue 732 .map!(pair => 733 pair 734 .value 735 ) 736 .joiner; 737 } 738 } 739 740 /// Returns all keys as an array. 741 @property auto keys(this This)() { return byKey.array; } 742 743 /// Returns all values as an array. 744 @property auto values(this This)() { return byValue.array; } 745 746 // *** Query (search by key) *** 747 748 static if (ordered) 749 { 750 /// Returns index of key `k`. 751 sizediff_t indexOf()(auto ref const K k) const 752 { 753 auto p = k in lookup; 754 return p ? (*p)[0] : -1; 755 } 756 757 /// Returns all indices of key `k`. 758 inout(size_t)[] indicesOf()(auto ref const K k) inout 759 { 760 auto p = k in lookup; 761 return p ? (*p)[] : null; 762 } 763 } 764 765 /// Return the number of items with the given key. 766 /// When multi==false, always returns 0 or 1. 767 size_t count()(auto ref K k) 768 { 769 static if (ordered) 770 return indicesOf(k).length; 771 else 772 { 773 auto p = k in lookup; 774 return p ? SM.length(*p) : 0; 775 } 776 } 777 778 /// Return a range with all values with the given key. 779 /// If the key is not present, returns an empty range. 780 static if (haveValues) 781 auto byValueOf(this This)(auto ref K k) 782 { 783 static if (ordered) 784 return indicesOf(k).map!(index => items[index].value); 785 else 786 return valuesOf(k); 787 } 788 789 /// Return an array with all values with the given key. 790 /// If the key is not present, returns an empty array. 791 static if (haveValues) 792 V[] valuesOf()(auto ref K k) 793 { 794 static if (ordered) 795 return byValueOf(k).array; 796 else 797 { 798 static if (multi) 799 return lookup.get(k, null); 800 else 801 { 802 auto p = k in lookup; 803 return p ? (*p)[] : null; 804 } 805 } 806 } 807 808 static if (haveValues) 809 deprecated alias getAll = valuesOf; 810 811 // *** Iteration *** 812 813 // Note: When iterating over keys in an AA, you must choose 814 // mutable OR ref, but not both. This is an important reason for 815 // the complexity below. 816 817 private enum isParameterRef(size_t index, fun...) = (){ 818 foreach (keyStorageClass; __traits(getParameterStorageClasses, fun[0], index)) 819 if (keyStorageClass == "ref") 820 return true; 821 return false; 822 }(); 823 824 private int opApplyImpl(this This, Dg)(scope Dg dg) 825 { 826 enum single = arity!dg == 1; 827 828 int result = 0; 829 830 static if (ordered) 831 { 832 foreach (ref item; items) 833 { 834 static if (single) 835 result = dg(item.indexValue); 836 else 837 result = dg(item.key, item.value); 838 if (result) 839 break; 840 } 841 } 842 else 843 { 844 static if (single && haveValues) 845 { 846 // Dg accepts value only, so use whatever we want for the key iteration. 847 alias LK = const(K); 848 enum useRef = true; 849 } 850 else 851 { 852 // Dg accepts a key (and maybe a value), so use the Dg signature for iteration. 853 alias LK = Parameters!Dg[0]; 854 enum useRef = isParameterRef!(0, Dg); 855 } 856 // LookupValue or const(LookupValue), depending on the constness of This 857 alias LV = typeof(lookup.values[0]); 858 859 bool handle()(ref LK key, ref LV values) 860 { 861 static if (haveValues) 862 { 863 foreach (ref value; values) 864 { 865 static if (single) 866 result = dg(value); 867 else 868 result = dg(key, value); 869 if (result) 870 return false; 871 } 872 } 873 else 874 { 875 foreach (iteration; 0 .. SM.length(values)) 876 { 877 static assert(single); 878 result = dg(key); 879 if (result) 880 return false; 881 } 882 } 883 return true; 884 } 885 886 static if (useRef) 887 { 888 foreach (ref LK key, ref LV values; lookup) 889 if (!handle(key, values)) 890 break; 891 } 892 else 893 { 894 foreach (LK key, ref LV values; lookup) 895 if (!handle(key, values)) 896 break; 897 } 898 } 899 return result; 900 } 901 902 private alias KeyIterationType(bool isConst, bool byRef) = typeof(*(){ 903 904 static if (isConst) 905 const bool[K] aa; 906 else 907 bool[K] aa; 908 909 static if (byRef) 910 foreach (ref k, v; aa) 911 return &k; 912 else 913 foreach (k, v; aa) 914 return &k; 915 916 assert(false); 917 }()); 918 919 private enum needRefOverload(bool isConst) = 920 // Unfortunately this doesn't work: https://issues.dlang.org/show_bug.cgi?id=21683 921 // !is(KeyIterationType!(isConst, false) == KeyIterationType!(isConst, true)); 922 !isCopyable!K; 923 924 private template needIter(bool isConst, bool byRef) 925 { 926 static if (!isCopyable!K) 927 enum needIter = byRef; 928 else 929 static if (!byRef) 930 enum needIter = true; 931 else 932 enum needIter = needRefOverload!isConst; 933 } 934 935 static if (haveValues) 936 { 937 /// Iterate over values (maps). 938 int opApply(scope int delegate( ref V) dg) { return opApplyImpl(dg); } 939 int opApply(scope int delegate(const ref V) dg) const { return opApplyImpl(dg); } /// ditto 940 } 941 else 942 { 943 /// Iterate over keys (sets). 944 static if (needIter!(false, false)) int opApply(scope int delegate( KeyIterationType!(false, false)) dg) { return opApplyImpl(dg); } 945 static if (needIter!(true , false)) int opApply(scope int delegate( KeyIterationType!(true , false)) dg) const { return opApplyImpl(dg); } /// ditto 946 static if (needIter!(false, true )) int opApply(scope int delegate(ref KeyIterationType!(false, true )) dg) { return opApplyImpl(dg); } /// ditto 947 static if (needIter!(true , true )) int opApply(scope int delegate(ref KeyIterationType!(true , true )) dg) const { return opApplyImpl(dg); } /// ditto 948 } 949 950 static if (haveValues) 951 { 952 /// Iterate over keys and values. 953 static if (needIter!(false, false)) int opApply(scope int delegate( KeyIterationType!(false, false), ref V) dg) { return opApplyImpl(dg); } 954 static if (needIter!(true , false)) int opApply(scope int delegate( KeyIterationType!(true , false), const ref V) dg) const { return opApplyImpl(dg); } /// ditto 955 static if (needIter!(false, true )) int opApply(scope int delegate(ref KeyIterationType!(false, true ), ref V) dg) { return opApplyImpl(dg); } /// ditto 956 static if (needIter!(true , true )) int opApply(scope int delegate(ref KeyIterationType!(true , true ), const ref V) dg) const { return opApplyImpl(dg); } /// ditto 957 } 958 959 private struct ByRef(bool isConst) 960 { 961 static if (isConst) 962 const(HashCollection)* c; 963 else 964 HashCollection* c; 965 966 static if (haveValues) 967 { 968 static if (isConst) 969 int opApply(scope int delegate(ref KeyIterationType!(true , true ), const ref V) dg) const { return c.opApplyImpl(dg); } 970 else 971 int opApply(scope int delegate(ref KeyIterationType!(false, true ), ref V) dg) { return c.opApplyImpl(dg); } 972 } 973 else 974 { 975 static if (isConst) 976 int opApply(scope int delegate(ref KeyIterationType!(true , true )) dg) const { return c.opApplyImpl(dg); } 977 else 978 int opApply(scope int delegate(ref KeyIterationType!(false, true )) dg) { return c.opApplyImpl(dg); } 979 } 980 } 981 982 /// Returns an object that allows iterating over this collection with ref keys. 983 /// Workaround for https://issues.dlang.org/show_bug.cgi?id=21683 984 auto byRef() return { return ByRef!false(&this); } 985 auto byRef() const return { return ByRef!true (&this); } /// ditto 986 987 // *** Mutation (addition) *** 988 989 private enum AddMode 990 { 991 add, /// Always add value 992 replace, /// Replace all previous values 993 require, /// Only add value if it did not exist before 994 addNew, /// Only add value if it did not exist before; call getValue in that case 995 } 996 997 private auto addImpl(AddMode mode, AK, GV)(ref AK key, scope GV getValue) 998 if (is(AK : K)) 999 { 1000 static if (ordered) 1001 { 1002 size_t addedIndex; 1003 1004 static if (multi && mode == AddMode.add) 1005 { 1006 addedIndex = items.length; 1007 lookup[key] ~= addedIndex; 1008 items ~= Item(key, getValue()); 1009 } 1010 else 1011 { 1012 lookup.updateVoid(key, 1013 delegate LookupValue() 1014 { 1015 addedIndex = items.length; 1016 auto item = Item(key, getValue()); 1017 items.length++; 1018 move(item, items[$-1]); 1019 return [addedIndex]; 1020 }, 1021 delegate void(ref LookupValue existingIndex) 1022 { 1023 addedIndex = existingIndex[0]; 1024 static if (mode != AddMode.require && mode != AddMode.addNew) 1025 { 1026 static if (multi) 1027 { 1028 static assert(mode == AddMode.replace); 1029 existingIndex = existingIndex[0 .. 1]; 1030 } 1031 items[addedIndex].value = getValue(); 1032 } 1033 }); 1034 } 1035 1036 auto self = &this; 1037 static struct Result 1038 { 1039 size_t orderIndex; 1040 typeof(self) context; 1041 @property ref auto returnValue() { return context.items[orderIndex].returnValue; } 1042 } 1043 return Result(addedIndex, self); 1044 } 1045 else // ordered 1046 { 1047 static if (haveValues) 1048 { 1049 static struct Result 1050 { 1051 ReturnType* ptr; 1052 @property ref ReturnType returnValue() { return *ptr; } 1053 } 1054 1055 static if (mode == AddMode.require || mode == AddMode.addNew) 1056 return Result(&(lookup.require(key, [getValue()]))[0]); 1057 else 1058 static if (multi && mode == AddMode.add) 1059 return Result(&(lookup[key] ~= getValue())[$-1]); 1060 else 1061 return Result(&(lookup[key] = [getValue()])[0]); 1062 } 1063 else 1064 { 1065 static if (multi) 1066 { 1067 static if (mode == AddMode.require) 1068 lookup.require(key, 1); 1069 else 1070 static if (mode == AddMode.addNew) 1071 lookup.require(key, progn(getValue(), 1)); 1072 else 1073 static if (mode == AddMode.add) 1074 lookup[key]++; 1075 else 1076 lookup[key] = 1; 1077 } 1078 else 1079 { 1080 static if (mode == AddMode.addNew) 1081 lookup.require(key, progn(getValue(), LookupValue.init)); 1082 else 1083 lookup[key] = LookupValue.init; 1084 } 1085 // This branch returns void, as there is no reasonable 1086 // ref to an AA key that we can return here. 1087 static struct Result { @property void returnValue(){} } 1088 return Result(); 1089 } 1090 } 1091 } 1092 1093 /*private*/ template _addSetFunc(AddMode mode) 1094 { 1095 static if (haveValues) 1096 { 1097 ref ReturnType _addSetFunc(AK, AV)(auto ref AK key, ref AV value) 1098 if (is(AK : K) && is(AV : V)) 1099 { 1100 return addImpl!mode(key, () => value).returnValue; 1101 } 1102 1103 ref ReturnType _addSetFunc(AK, AV)(auto ref AK key, AV value) 1104 if (is(AK : K) && is(AV : V)) 1105 { 1106 return addImpl!mode(key, () => move(value)).returnValue; 1107 } 1108 } 1109 else 1110 { 1111 ref ReturnType _addSetFunc(AK)(auto ref AK key) 1112 if (is(AK : K)) 1113 { 1114 ValueVarType value; // void[0] 1115 return addImpl!mode(key, () => value).returnValue; 1116 } 1117 } 1118 } 1119 1120 /// Add an item. 1121 alias add = _addSetFunc!(AddMode.add); 1122 1123 /// Ensure a key exists (with the given value). 1124 /// When `multi==true`, replaces all previous entries with this key. 1125 /// Otherwise, behaves identically to `add`. 1126 alias set = _addSetFunc!(AddMode.replace); 1127 1128 /// Add `value` only if `key` is not present. 1129 static if (haveValues) 1130 ref V require()(auto ref K key, lazy V value = V.init) 1131 { 1132 return addImpl!(AddMode.require)(key, () => value).returnValue; 1133 } 1134 1135 static if (ordered) 1136 size_t requireIndex()(auto ref K key, lazy ValueVarType value = ValueVarType.init) 1137 { 1138 return addImpl!(AddMode.require)(key, () => value).orderIndex; 1139 } 1140 1141 deprecated alias getOrAdd = require; 1142 1143 private alias UpdateFuncRT(U) = typeof({ U u = void; V v = void; return u(v); }()); 1144 1145 /// If `key` is present, call `update` for every value; 1146 /// otherwise, add new value with `create`. 1147 static if (haveValues) 1148 void update(C, U)(auto ref K key, scope C create, scope U update) 1149 if (is(typeof(create()) : V) && (is(UpdateFuncRT!U : V) || is(UpdateFuncRT!U == void))) 1150 { 1151 static if (ordered) 1152 { 1153 lookup.updateVoid(key, 1154 delegate LookupValue() 1155 { 1156 auto addedIndex = items.length; 1157 items ~= Item(key, create()); 1158 return [addedIndex]; 1159 }, 1160 delegate void(ref LookupValue existingIndex) 1161 { 1162 foreach (i; existingIndex) 1163 static if (is(UpdateFuncRT!U == void)) 1164 update(items[i].value); 1165 else 1166 items[i].value = update(items[i].value); 1167 }); 1168 } 1169 else // ordered 1170 { 1171 lookup.updateVoid(key, 1172 delegate LookupValue () 1173 { 1174 return [create()]; 1175 }, 1176 delegate void (ref LookupValue values) 1177 { 1178 foreach (ref value; values) 1179 static if (is(UpdateFuncRT!U == void)) 1180 update(value); 1181 else 1182 value = update(value); 1183 }); 1184 } 1185 } 1186 1187 static if (haveValues) 1188 { 1189 bool addNew()(auto ref K key, lazy V value = V.init) 1190 { 1191 bool added = false; 1192 // update(key, 1193 // delegate V ( ) { added = true ; return value; }, 1194 // delegate void(ref V v) { added = false; }, 1195 // ); 1196 addImpl!(AddMode.addNew)(key, { added = true; return value; }); 1197 return added; 1198 } 1199 } 1200 else 1201 { 1202 bool addNew()(auto ref K key) 1203 { 1204 bool added = false; 1205 ValueVarType value; // void[0] 1206 addImpl!(AddMode.addNew)(key, { added = true; return value; }); 1207 return added; 1208 } 1209 } 1210 1211 // *** Mutation (editing) *** 1212 1213 static if (haveIndexing) 1214 { 1215 static if (haveValues) 1216 { 1217 /// Same as `set(k, v)`. 1218 ref IV opIndexAssign(AK, AV)(ref AV v, auto ref AK k) 1219 if (is(AK : K) && is(AV : V)) 1220 { 1221 return set(k, v); 1222 } 1223 1224 ref IV opIndexAssign(AK, AV)(AV v, auto ref AK k) 1225 if (is(AK : K) && is(AV : V)) 1226 { 1227 return set(k, move(v)); 1228 } /// ditto 1229 1230 /// Perform cumulative operation with value 1231 /// (initialized with `.init` if the key does not exist). 1232 ref IV opIndexOpAssign(string op, AK, AV)(auto ref AV v, auto ref AK k) 1233 if (is(AK : K) && is(AV : V)) 1234 { 1235 auto pv = &require(k); 1236 return mixin("(*pv) " ~ op ~ "= v"); 1237 } 1238 1239 /// Perform unary operation with value 1240 /// (initialized with `.init` if the key does not exist). 1241 ref IV opIndexUnary(string op, AK)(auto ref AK k) 1242 if (is(AK : K)) 1243 { 1244 auto pv = &require(k); 1245 mixin("(*pv) " ~ op ~ ";"); 1246 return *pv; 1247 } 1248 } 1249 else 1250 { 1251 private ref K editIndex(size_t index, scope void delegate(ref K) edit) 1252 { 1253 auto item = &items[index]; 1254 K oldKey = item.key; 1255 auto pOldIndices = oldKey in lookup; 1256 assert(pOldIndices); 1257 1258 edit(item.key); 1259 1260 // Add new value 1261 1262 lookup.updateVoid(item.key, 1263 delegate LookupValue() 1264 { 1265 // New value did not exist. 1266 if ((*pOldIndices).length == 1) 1267 { 1268 // Optimization - migrate the Indexes value 1269 assert((*pOldIndices)[0] == index); 1270 return *pOldIndices; 1271 } 1272 else 1273 return [index]; 1274 }, 1275 delegate void(ref LookupValue existingIndex) 1276 { 1277 // Value(s) with the new key already existed 1278 static if (multi) 1279 existingIndex ~= index; 1280 else 1281 assert(false, "Collision after in-place edit of a non-multi ordered set element"); 1282 }); 1283 1284 // Remove old value 1285 1286 if ((*pOldIndices).length == 1) 1287 lookup.remove(oldKey); 1288 else 1289 static if (multi) 1290 *pOldIndices = (*pOldIndices).remove!(i => i == index); 1291 else 1292 assert(false); // Should be unreachable (`if` above will always be true) 1293 1294 return item.key; 1295 } 1296 1297 /// Allows writing to ordered sets by index. 1298 /// The total number of elements never changes as a result 1299 /// of such an operation - a consequence of which is that 1300 /// if multi==false, changing the value to one that's 1301 /// already in the set is an error. 1302 ref IV opIndexAssign()(auto ref IV v, auto ref IK k) 1303 { 1304 static if (haveValues) 1305 return set(k, v); 1306 else 1307 return editIndex(k, (ref IV e) { e = v; }); 1308 } 1309 1310 /// Perform cumulative operation with value at index. 1311 ref IV opIndexOpAssign(string op)(auto ref VV v, auto ref IK k) 1312 { 1313 return editIndex(k, (ref IV e) { mixin("e " ~ op ~ "= v;"); }); 1314 } 1315 1316 /// Perform unary operation with value at index. 1317 ref IV opIndexUnary(string op)(auto ref IK k) 1318 { 1319 return editIndex(k, (ref IV e) { mixin("e " ~ op ~ ";"); }); 1320 } 1321 } 1322 } 1323 1324 // *** Mutation (removal) *** 1325 1326 /// Removes all elements with the given key. 1327 bool remove(AK)(auto ref AK key) 1328 if (is(typeof(lookup.remove(key)))) 1329 { 1330 static if (ordered) 1331 { 1332 auto p = key in lookup; 1333 if (!p) 1334 return false; 1335 1336 auto targets = *p; 1337 foreach (target; targets) 1338 { 1339 items = items.remove!(SwapStrategy.stable)(target); 1340 foreach (ref k, ref vs; lookup) 1341 foreach (ref v; vs) 1342 if (v > target) 1343 v--; 1344 } 1345 auto success = lookup.remove(key); 1346 assert(success); 1347 return true; 1348 } 1349 else 1350 return lookup.remove(key); 1351 } 1352 1353 /// Removes all elements. 1354 void clear() 1355 { 1356 lookup.clear(); 1357 static if (ordered) 1358 items = null; 1359 } 1360 } 1361 1362 /// An associative array which retains the order in which elements were added. 1363 alias OrderedMap(K, V) = HashCollection!(K, V, true, false); 1364 1365 debug(ae_unittest) unittest 1366 { 1367 alias M = OrderedMap!(string, int); 1368 M m; 1369 m["a"] = 1; 1370 m["b"] = 2; 1371 m["c"] = 3; 1372 assert(m.length == 3); 1373 assert("a" in m); 1374 assert("d" !in m); 1375 1376 assert( m.addNew("x", 1)); 1377 assert(!m.addNew("x", 2)); 1378 assert(m["x"] == 1); 1379 assert( m.remove("x")); 1380 assert(!m.remove("x")); 1381 1382 { 1383 auto r = m.byKeyValue; 1384 assert(!r.empty); 1385 assert(r.front.key == "a"); 1386 r.popFront(); 1387 assert(!r.empty); 1388 assert(r.front.key == "b"); 1389 r.popFront(); 1390 assert(!r.empty); 1391 assert(r.front.key == "c"); 1392 r.popFront(); 1393 assert(r.empty); 1394 } 1395 1396 assert(m.byKey.equal(["a", "b", "c"])); 1397 assert(m.byValue.equal([1, 2, 3])); 1398 assert(m.byKeyValue.map!(p => p.key).equal(m.byKey)); 1399 assert(m.byKeyValue.map!(p => p.value).equal(m.byValue)); 1400 assert(m.keys == ["a", "b", "c"]); 1401 assert(m.values == [1, 2, 3]); 1402 1403 { 1404 const(M)* c = &m; 1405 assert(c.byKey.equal(["a", "b", "c"])); 1406 assert(c.byValue.equal([1, 2, 3])); 1407 assert(c.keys == ["a", "b", "c"]); 1408 assert(c.values == [1, 2, 3]); 1409 } 1410 1411 m.byValue.front = 5; 1412 assert(m.byValue.equal([5, 2, 3])); 1413 1414 m.remove("a"); 1415 assert(m.length == 2); 1416 m["x"] -= 1; 1417 assert(m["x"] == -1); 1418 ++m["y"]; 1419 assert(m["y"] == 1); 1420 auto cm = cast(const)m.dup; 1421 foreach (k, v; cm) 1422 if (k == "x") 1423 assert(v == -1); 1424 } 1425 1426 debug(ae_unittest) unittest 1427 { 1428 OrderedMap!(string, int) m; 1429 m["a"] = 1; 1430 m["b"] = 2; 1431 m.remove("a"); 1432 assert(m["b"] == 2); 1433 } 1434 1435 debug(ae_unittest) unittest 1436 { 1437 OrderedMap!(string, int) m; 1438 m["a"] = 1; 1439 auto m2 = m; 1440 m2.remove("a"); 1441 m2["b"] = 2; 1442 assert(m["a"] == 1); 1443 } 1444 1445 debug(ae_unittest) unittest 1446 { 1447 OrderedMap!(string, int) m; 1448 m["a"] = 1; 1449 m["b"] = 2; 1450 auto m2 = m; 1451 m.remove("a"); 1452 assert(m2["a"] == 1); 1453 } 1454 1455 debug(ae_unittest) unittest 1456 { 1457 class C {} 1458 const OrderedMap!(string, C) m; 1459 cast(void)m.byKeyValue; 1460 } 1461 1462 debug(ae_unittest) unittest 1463 { 1464 OrderedMap!(int, int) m; 1465 m.update(10, 1466 { return 20; }, 1467 (ref int k) { k++; return 30; }, 1468 ); 1469 assert(m.length == 1 && m[10] == 20); 1470 m.update(10, 1471 { return 40; }, 1472 (ref int k) { k++; return 50; }, 1473 ); 1474 assert(m.length == 1 && m[10] == 50); 1475 } 1476 1477 // https://issues.dlang.org/show_bug.cgi?id=18606 1478 debug(ae_unittest) unittest 1479 { 1480 struct S 1481 { 1482 struct T 1483 { 1484 int foo; 1485 int[] bar; 1486 } 1487 1488 OrderedMap!(int, T) m; 1489 } 1490 } 1491 1492 debug(ae_unittest) unittest 1493 { 1494 OrderedMap!(string, int) m; 1495 static assert(is(typeof(m.keys))); 1496 static assert(is(typeof(m.values))); 1497 } 1498 1499 debug(ae_unittest) unittest 1500 { 1501 OrderedMap!(string, int) m; 1502 foreach (k, v; m) 1503 k = k ~ k; 1504 } 1505 1506 debug(ae_unittest) unittest 1507 { 1508 struct S { @disable this(); } 1509 const OrderedMap!(string, S) m; 1510 } 1511 1512 debug(ae_unittest) unittest 1513 { 1514 class C {} 1515 OrderedMap!(string, C) m; 1516 m.get(null, new C); 1517 } 1518 1519 /// Like assocArray 1520 auto orderedMap(R)(R input) 1521 if (is(typeof(input.front.length) : size_t) && input.front.length == 2) 1522 { 1523 alias K = typeof(input.front[0]); 1524 alias V = typeof(input.front[1]); 1525 return OrderedMap!(K, V)(input); 1526 } 1527 1528 auto orderedMap(R)(R input) 1529 if (is(typeof(input.front.key)) && is(typeof(input.front.value)) && !is(typeof(input.front.length))) 1530 { 1531 alias K = typeof(input.front.key); 1532 alias V = typeof(input.front.value); 1533 return OrderedMap!(K, V)(input); 1534 } /// ditto 1535 1536 debug(ae_unittest) unittest 1537 { 1538 auto map = 3.iota.map!(n => tuple(n, n + 1)).orderedMap; 1539 assert(map.length == 3 && map[1] == 2); 1540 } 1541 1542 debug(ae_unittest) unittest 1543 { 1544 OrderedMap!(string, int) m; 1545 m = m.byKeyValue.orderedMap; 1546 m = m.byPair.orderedMap; 1547 } 1548 1549 debug(ae_unittest) unittest 1550 { 1551 OrderedMap!(string, int) m; 1552 const(char)[] s; 1553 m.get(s, 0); 1554 } 1555 1556 debug(ae_unittest) unittest 1557 { 1558 OrderedMap!(string, OrderedMap!(string, string[][])) m; 1559 1560 m.require(""); 1561 } 1562 1563 debug(ae_unittest) unittest 1564 { 1565 struct Q { void* p; } 1566 struct S { OrderedMap!(string, Q) m; } 1567 OrderedMap!(string, S) objects; 1568 1569 objects[""] = S(); 1570 } 1571 1572 // *************************************************************************** 1573 1574 /// Helper/wrapper for void[0][T] 1575 alias HashSet(T) = HashCollection!(T, void, false, false); 1576 1577 debug(ae_unittest) unittest 1578 { 1579 HashSet!int s; 1580 assert(!s); 1581 assert(s.length == 0); 1582 assert(!(1 in s)); 1583 assert(1 !in s); 1584 s.add(1); 1585 assert(1 in s); 1586 assert(s.length == 1); 1587 foreach (k; s) 1588 assert(k == 1); 1589 foreach (ref k; s.byRef) 1590 assert(k == 1); 1591 s.remove(1); 1592 assert(s.length == 0); 1593 1594 s.add(1); 1595 auto t = s.dup; 1596 s.add(2); 1597 assert(t.length==1); 1598 t.remove(1); 1599 assert(t.length==0); 1600 1601 assert( t.addNew(5)); 1602 assert(!t.addNew(5)); 1603 assert(5 in t); 1604 assert( t.remove(5)); 1605 assert(!t.remove(5)); 1606 } 1607 1608 debug(ae_unittest) unittest 1609 { 1610 struct S { int[int] aa; } 1611 HashSet!S set; 1612 S s; 1613 set.add(s); 1614 assert(s in set); 1615 } 1616 1617 /// Construct a set from the range `r`. 1618 auto toSet(R)(R r) 1619 { 1620 alias E = ElementType!R; 1621 return HashSet!E(r); 1622 } 1623 1624 debug(ae_unittest) unittest 1625 { 1626 auto set = [1, 2, 3].toSet(); 1627 assert(2 in set); 1628 assert(4 !in set); 1629 } 1630 1631 debug(ae_unittest) unittest 1632 { 1633 HashSet!int m; 1634 const int i; 1635 m.remove(i); 1636 } 1637 1638 debug(ae_unittest) unittest 1639 { 1640 HashSet!Object m; 1641 Object o; 1642 m.remove(o); 1643 } 1644 1645 debug(ae_unittest) unittest 1646 { 1647 struct S 1648 { 1649 @disable this(this); 1650 } 1651 1652 HashSet!S set; 1653 } 1654 1655 // *************************************************************************** 1656 1657 /// An ordered set of `T`, which retains 1658 /// the order in which elements are added. 1659 alias OrderedSet(T) = HashCollection!(T, void, true, false); 1660 1661 debug(ae_unittest) unittest 1662 { 1663 OrderedSet!int set; 1664 1665 assert(1 !in set); 1666 set.add(1); 1667 assert(1 in set); 1668 set.remove(1); 1669 assert(1 !in set); 1670 1671 set.add(1); 1672 set.clear(); 1673 assert(1 !in set); 1674 1675 set = set.init; 1676 assert(!set); 1677 set.add(1); 1678 assert(!!set); 1679 1680 assert(set[0] == 1); 1681 set[0] = 2; 1682 assert(set[0] == 2); 1683 assert(1 !in set); 1684 assert(2 in set); 1685 1686 assert(set.length == 1); 1687 set.remove(2); 1688 assert(set.length == 0); 1689 1690 set.add(1); 1691 auto set2 = set; 1692 set.remove(1); 1693 set.add(2); 1694 assert(1 !in set && 2 in set); 1695 assert(1 in set2 && 2 !in set2); 1696 1697 foreach (v; set) 1698 assert(v == 2); 1699 1700 assert(set.length == 1); 1701 auto index1 = set.requireIndex(1); 1702 assert(set[index1] == 1); 1703 assert(set.length == 2); 1704 auto index2 = set.requireIndex(2); 1705 assert(set[index2] == 2); 1706 assert(set.length == 2); 1707 1708 assert(set[set.indexOf(2)] == 2); 1709 1710 void f(ref const OrderedSet!int set) 1711 { 1712 const size_t i = 0; 1713 assert(set[i] == 2); 1714 } 1715 1716 assert(set.at(set.indexOf(2)) == 2); 1717 assert(set.getAt(set.indexOf(2), 99) == 2); 1718 assert(set.getAt(99, 99) == 99); 1719 } 1720 1721 /// Construct an ordered set from the range `r`. 1722 auto orderedSet(R)(R r) 1723 { 1724 alias E = ElementType!R; 1725 return OrderedSet!E(r); 1726 } 1727 1728 // *************************************************************************** 1729 1730 /// An object which acts mostly as an associative array, 1731 /// with the added property of being able to hold keys with 1732 /// multiple values. These are only exposed explicitly and 1733 /// through iteration 1734 alias MultiAA(K, V) = HashCollection!(K, V, false, true); 1735 1736 debug(ae_unittest) unittest 1737 { 1738 alias MASS = MultiAA!(string, int); 1739 MASS aa; 1740 aa.add("foo", 42); 1741 assert(aa["foo"] == 42); 1742 assert(aa.valuesOf("foo") == [42]); 1743 assert(aa.byPair.front.key == "foo"); 1744 1745 auto aa2 = MASS([tuple("foo", 42)]); 1746 aa2 = ["a":1,"b":2]; 1747 1748 const int i; 1749 aa["a"] = i; 1750 } 1751 1752 debug(ae_unittest) unittest 1753 { 1754 MultiAA!(int, int) m; 1755 int[][int] a; 1756 m = a; 1757 } 1758 1759 // *************************************************************************** 1760 1761 /// Given an AA literal, construct an AA-like object which can be built 1762 /// at compile-time and queried at run-time. 1763 /// The AA literal is unrolled into code. 1764 auto staticAA(alias aa)() 1765 { 1766 alias K = typeof(aa.keys[0]); 1767 alias V = typeof(aa.values[0]); 1768 ref auto value(alias v)() // Work around "... is already defined in another scope in ..." 1769 { 1770 static immutable iv = v; 1771 return iv; 1772 } 1773 struct StaticMap 1774 { 1775 static immutable K[] keys = aa.keys; 1776 static immutable V[] values = aa.values; 1777 1778 ref immutable(V) opIndex(K key) const 1779 { 1780 final switch (key) 1781 { 1782 static foreach (i, aaKey; aa.keys) 1783 { 1784 case aaKey: 1785 return value!(aa.values[i]); 1786 } 1787 } 1788 } 1789 1790 bool opBinaryRight(string op : "in")(K key) inout 1791 { 1792 switch (key) 1793 { 1794 static foreach (aaKey; aa.keys) 1795 { 1796 case aaKey: 1797 return true; 1798 } 1799 default: 1800 return false; 1801 } 1802 } 1803 1804 int opApply(scope int delegate(ref immutable K, ref immutable V) dg) const 1805 { 1806 static foreach (i, aaKey; aa.keys) 1807 {{ 1808 int ret = dg(value!aaKey, value!(aa.values[i])); 1809 if (ret) 1810 return ret; 1811 }} 1812 return 0; 1813 } 1814 } 1815 return StaticMap(); 1816 } 1817 1818 debug(ae_unittest) unittest 1819 { 1820 static immutable aa = staticAA!([ 1821 "foo" : 1, 1822 "bar" : 2, 1823 ]); 1824 1825 assert(aa["foo"] == 1); 1826 1827 assert("foo" in aa); 1828 assert("baz" !in aa); 1829 1830 assert(aa.keys == ["foo", "bar"]); 1831 assert(aa.values == [1, 2]); 1832 1833 foreach (key, value; aa) 1834 assert((key == "foo" && value == 1) || (key == "bar" && value == 2)); 1835 }