1 /++ 2 $(H1 Ordered string-value associative array) 3 Macros: 4 AlgebraicREF = $(GREF_ALTTEXT mir-core, $(TT $1), $1, mir, algebraic)$(NBSP) 5 +/ 6 7 module mir.string_map; 8 9 import std.traits; 10 import mir.internal.meta: basicElementType; 11 12 /++ 13 Checks if the type is instance of $(LREF StringMap). 14 +/ 15 enum isStringMap(T) = is(Unqual!T == StringMap!V, V); 16 17 version(mir_test) 18 /// 19 unittest 20 { 21 static assert(isStringMap!(StringMap!int)); 22 static assert(isStringMap!(const StringMap!int)); 23 static assert(!isStringMap!int); 24 } 25 26 private alias U = uint; 27 28 /++ 29 Ordered string-value associative array with extremely fast lookup. 30 31 Params: 32 T = mutable value type, can be instance of $(AlgebraicREF Algebraic) for example. 33 U = an unsigned type that can hold an index of keys. `U.max` must be less then the maximum possible number of struct members. 34 +/ 35 struct StringMap(T) 36 // if (!is(typeof(T.opPostMove))) 37 { 38 import mir.utility: _expect; 39 import core.lifetime: move; 40 import mir.conv: emplaceRef; 41 import mir.algebraic: Algebraic; 42 43 /// 44 static struct KeyValue 45 { 46 /// 47 string key; 48 /// 49 T value; 50 } 51 52 /// `hashOf` Implementation. Doesn't depend on order 53 static if (is(T == Algebraic!Union, Union) && is(Union == union)) 54 size_t toHash() scope @trusted const nothrow pure @nogc 55 { 56 if (implementation is null) 57 return 0; 58 size_t hash; 59 foreach (i, index; implementation.indices) 60 { 61 hash = hashOf(implementation._keys[index], hash); 62 static if (__traits(hasMember, T, "toHash")) 63 hash = hashOf(implementation._values[index].toHash, hash); 64 else 65 hash = hashOf(implementation._values[index], hash); 66 } 67 return hash; 68 } 69 else 70 size_t toHash() scope @trusted const nothrow // pure @nogc 71 { 72 if (implementation is null) 73 return 0; 74 size_t hash; 75 foreach (i, index; implementation.indices) 76 { 77 hash = hashOf(implementation._keys[index], hash); 78 static if (__traits(hasMember, T, "toHash")) 79 hash = hashOf(implementation._values[index].toHash, hash); 80 else 81 hash = hashOf(implementation._values[index], hash); 82 } 83 return hash; 84 } 85 86 /// `==` implementation. Doesn't depend on order 87 // current implementation is workaround for linking bugs when used in self referencing algebraic types 88 bool opEquals(V)(scope const StringMap!V rhs) scope const @trusted pure @nogc nothrow 89 { 90 import std.traits: isAggregateType; 91 // NOTE: moving this to template restriction fails with recursive template instanation 92 if (implementation is null) 93 return rhs.length == 0; 94 if (rhs.implementation is null) 95 return length == 0; 96 if (implementation._length != rhs.implementation._length) 97 return false; 98 foreach (const i, const index; implementation.indices) 99 if (implementation._keys[index] != rhs.implementation._keys[rhs.implementation._indices[i]] || 100 implementation._values[index] != rhs.implementation._values[rhs.implementation._indices[i]]) 101 return false; 102 return true; 103 } 104 105 /// ditto 106 bool opEquals(K, V)(scope const const(V)[const(K)] rhs) scope const 107 if (is(typeof(K.init == string.init) : bool) && 108 is(typeof(V.init == T.init) : bool)) 109 { 110 if (implementation is null) 111 return rhs.length == 0; 112 if (implementation._length != rhs.length) 113 return false; 114 foreach (const i; 0 .. implementation._length) 115 { 116 if (const valuePtr = implementation.keys[i] in rhs) 117 { 118 if (*valuePtr != implementation.values[i]) 119 return false; 120 } 121 else 122 return false; 123 } 124 return true; 125 } 126 127 // // linking bug 128 // version(none) 129 // { 130 // /++ 131 // +/ 132 // bool opEquals()(typeof(null)) @safe pure nothrow @nogc const 133 // { 134 // return implementation is null; 135 // } 136 137 // version(mir_test) static if (is(T == int)) 138 // /// 139 // @safe pure unittest 140 // { 141 // StringMap!int map; 142 // assert(map == null); 143 // map = StringMap!int(["key" : 1]); 144 // assert(map != null); 145 // map.remove("key"); 146 // assert(map != null); 147 // } 148 // } 149 150 /++ 151 Reset the associative array 152 +/ 153 ref opAssign()(typeof(null)) return @safe pure nothrow @nogc 154 { 155 implementation = null; 156 return this; 157 } 158 159 version(mir_test) static if (is(T == int)) 160 /// 161 @safe pure unittest 162 { 163 StringMap!int map = ["key" : 1]; 164 map = null; 165 } 166 167 /++ 168 Initialize the associative array with default value. 169 +/ 170 this()(typeof(null) aa) @safe pure nothrow @nogc 171 { 172 implementation = null; 173 } 174 175 version(mir_test) static if (is(T == int)) 176 /// Usefull for default funcion argument. 177 @safe pure unittest 178 { 179 StringMap!int map = null; // 180 } 181 182 /++ 183 Constructs an associative array using keys and values from the builtin associative array 184 Complexity: `O(n log(n))` 185 +/ 186 this()(T[string] aa) @trusted pure nothrow 187 { 188 this(aa.keys, aa.values); 189 } 190 191 version(mir_test) static if (is(T == int)) 192 /// 193 @safe pure unittest 194 { 195 StringMap!int map = ["key" : 1]; 196 assert(map.findPos("key") == 0); 197 } 198 199 /// 200 string toString()() const scope 201 { 202 import mir.format: stringBuf; 203 stringBuf buffer; 204 toString(buffer); 205 return buffer.data.idup; 206 } 207 208 ///ditto 209 void toString(W)(ref scope W w) const scope 210 { 211 bool next; 212 w.put('['); 213 import mir.format: printEscaped, EscapeFormat, print; 214 foreach (i, ref value; values) 215 { 216 if (next) 217 w.put(`, `); 218 next = true; 219 w.put('\"'); 220 printEscaped!(char, EscapeFormat.ion)(w, keys[i]); 221 w.put(`": `); 222 print(w, value); 223 } 224 w.put(']'); 225 } 226 227 /++ 228 Constructs an associative array using keys and values. 229 Params: 230 keys = mutable array of keys 231 values = mutable array of values 232 Key and value arrays must have the same length. 233 234 Complexity: `O(n log(n))` 235 +/ 236 this()(string[] keys, T[] values) @trusted pure nothrow 237 { 238 assert(keys.length == values.length); 239 implementation = new Impl(keys, values); 240 } 241 242 version(mir_test) static if (is(T == int)) 243 /// 244 @safe pure unittest 245 { 246 auto keys = ["ba", "a"]; 247 auto values = [1.0, 3.0]; 248 auto map = StringMap!double(keys, values); 249 assert(map.keys is keys); 250 assert(map.values is values); 251 } 252 253 /++ 254 Returns: number of elements in the table. 255 +/ 256 size_t length()() @safe pure nothrow @nogc const @property 257 { 258 return implementation ? implementation.length : 0; 259 } 260 261 /++ 262 Returns: number of elements in the table. 263 +/ 264 bool empty()() @safe pure nothrow @nogc const @property 265 { 266 return !implementation || implementation.length == 0; 267 } 268 269 version(mir_test) static if (is(T == int)) 270 /// 271 @safe pure unittest 272 { 273 StringMap!double map; 274 assert(map.length == 0); 275 map["a"] = 3.0; 276 assert(map.length == 1); 277 map["c"] = 4.0; 278 assert(map.length == 2); 279 assert(map.remove("c")); 280 assert(map.length == 1); 281 assert(!map.remove("c")); 282 assert(map.length == 1); 283 assert(map.remove("a")); 284 assert(map.length == 0); 285 } 286 287 /++ 288 Returns a dynamic array, the elements of which are the keys in the associative array. 289 Doesn't allocate a new copy. 290 291 The keys returned are guaranteed to be in the ordered inserted as long as no 292 key removals followed by at least one key insertion has been performed. 293 294 Complexity: `O(1)` 295 +/ 296 const(string)[] keys()() @safe pure nothrow @nogc const @property 297 { 298 return implementation ? implementation.keys : null; 299 } 300 /// 301 alias byKey = keys; 302 303 version(mir_test) static if (is(T == int)) 304 /// 305 @safe pure unittest 306 { 307 StringMap!double map; 308 assert(map.keys == []); 309 map["c"] = 4.0; 310 assert(map.keys == ["c"]); 311 map["a"] = 3.0; 312 assert(map.keys == ["c", "a"]); 313 map.remove("c"); 314 assert(map.keys == ["a"]); 315 map.remove("a"); 316 assert(map.keys == []); 317 map["c"] = 4.0; 318 assert(map.keys == ["c"]); 319 } 320 321 /++ 322 Returns a dynamic array, the elements of which are the values in the associative array. 323 Doesn't allocate a new copy. 324 325 The values returned are guaranteed to be in the ordered inserted as long as no 326 key removals followed by at least one key insertion has been performed. 327 328 Complexity: `O(1)` 329 +/ 330 inout(T)[] values()() @safe pure nothrow @nogc inout @property 331 { 332 return implementation ? implementation.values : null; 333 } 334 335 /// ditto 336 alias byValue = values; 337 338 version(mir_test) static if (is(T == int)) 339 /// 340 @safe pure unittest 341 { 342 StringMap!double map; 343 assert(map.byKeyValue == StringMap!double.KeyValue[].init); 344 map["c"] = 4.0; 345 map["a"] = 3.0; 346 assert(map.byKeyValue == [StringMap!double.KeyValue("c", 4.0), StringMap!double.KeyValue("a", 3.0)]); 347 } 348 349 /** Return a range over all elements (key-values pairs) currently stored in the associative array. 350 351 The elements returned are guaranteed to be in the ordered inserted as 352 long as no key removals nor no value mutations has been performed. 353 */ 354 auto byKeyValue(this This)() @trusted pure nothrow @nogc 355 { 356 import mir.ndslice.topology: map; 357 return this.opIndex.map!KeyValue; 358 } 359 360 version(mir_test) static if (is(T == int)) 361 /// 362 @safe pure unittest 363 { 364 StringMap!double map; 365 assert(map.values == []); 366 map["c"] = 4.0; 367 assert(map.values == [4.0]); 368 map["a"] = 3.0; 369 assert(map.values == [4.0, 3.0]); 370 map.values[0]++; 371 assert(map.values == [5.0, 3.0]); 372 map.remove("c"); 373 assert(map.values == [3.0]); 374 map.remove("a"); 375 assert(map.values == []); 376 map["c"] = 4.0; 377 assert(map.values == [4.0]); 378 } 379 380 /// 381 auto opIndex(this This)() @trusted pure nothrow @nogc 382 { 383 import mir.ndslice.topology: zip; 384 return keys.zip(values); 385 } 386 387 /// 388 auto dup(this This)() @trusted 389 { 390 return StringMap(keys.dup, values.dup); 391 } 392 393 /++ 394 (Property) Gets the current capacity of an associative array. 395 The capacity is the size that the underlaynig slices can grow to before the underlying arrays may be reallocated or extended. 396 397 Complexity: `O(1)` 398 +/ 399 size_t capacity()() @safe pure nothrow const @property 400 { 401 import mir.utility: min; 402 403 return !implementation ? 0 : min( 404 implementation.keys.capacity, 405 implementation.values.capacity, 406 implementation.indices.capacity, 407 ); 408 } 409 410 version(mir_test) static if (is(T == int)) 411 /// 412 unittest 413 { 414 StringMap!double map; 415 assert(map.capacity == 0); 416 map["c"] = 4.0; 417 assert(map.capacity >= 1); 418 map["a"] = 3.0; 419 assert(map.capacity >= 2); 420 map.remove("c"); 421 map.assumeSafeAppend; 422 assert(map.capacity >= 2); 423 } 424 425 /++ 426 Reserves capacity for an associative array. 427 The capacity is the size that the underlaying slices can grow to before the underlying arrays may be reallocated or extended. 428 +/ 429 size_t reserve()(size_t newcapacity) @trusted pure nothrow 430 { 431 import mir.utility: min; 432 433 if (_expect(!implementation, false)) 434 { 435 implementation = new Impl; 436 } 437 438 auto keysV = implementation.keys; 439 auto keysVCaacity = keysV.reserve(newcapacity); 440 implementation._keys = keysV.ptr; 441 442 auto valuesV = implementation.values; 443 auto valuesCapacity = valuesV.reserve(newcapacity); 444 implementation._values = valuesV.ptr; 445 446 auto indicesV = implementation.indices; 447 auto indicesCapacity = indicesV.reserve(newcapacity); 448 implementation._indices = indicesV.ptr; 449 450 return min( 451 keysVCaacity, 452 valuesCapacity, 453 indicesCapacity, 454 ); 455 } 456 457 version(mir_test) static if (is(T == int)) 458 /// 459 unittest 460 { 461 StringMap!double map; 462 auto capacity = map.reserve(10); 463 assert(capacity >= 10); 464 assert(map.capacity == capacity); 465 map["c"] = 4.0; 466 assert(map.capacity == capacity); 467 map["a"] = 3.0; 468 assert(map.capacity >= 2); 469 assert(map.remove("c")); 470 capacity = map.reserve(20); 471 assert(capacity >= 20); 472 assert(map.capacity == capacity); 473 } 474 475 /++ 476 Assume that it is safe to append to this associative array. 477 Appends made to this associative array after calling this function may append in place, even if the array was a slice of a larger array to begin with. 478 Use this only when it is certain there are no elements in use beyond the associative array in the memory block. If there are, those elements will be overwritten by appending to this associative array. 479 480 Warning: Calling this function, and then using references to data located after the given associative array results in undefined behavior. 481 482 Returns: The input is returned. 483 +/ 484 ref inout(typeof(this)) assumeSafeAppend()() nothrow inout return 485 { 486 if (implementation) 487 { 488 implementation.keys.assumeSafeAppend; 489 implementation.values.assumeSafeAppend; 490 implementation.indices.assumeSafeAppend; 491 } 492 return this; 493 } 494 495 version(mir_test) static if (is(T == int)) 496 /// 497 unittest 498 { 499 StringMap!double map; 500 map["c"] = 4.0; 501 map["a"] = 3.0; 502 assert(map.capacity >= 2); 503 map.remove("c"); 504 assert(map.capacity == 0); 505 map.assumeSafeAppend; 506 assert(map.capacity >= 2); 507 } 508 509 /++ 510 Removes all remaining keys and values from an associative array. 511 512 Complexity: `O(1)` 513 +/ 514 void clear()() @safe pure nothrow @nogc 515 { 516 if (implementation) 517 { 518 implementation._length = 0; 519 implementation._lengthTable = implementation._lengthTable[0 .. 0]; 520 } 521 522 } 523 524 version(mir_test) static if (is(T == int)) 525 /// 526 unittest 527 { 528 StringMap!double map; 529 map["c"] = 4.0; 530 map["a"] = 3.0; 531 map.clear; 532 assert(map.length == 0); 533 assert(map.capacity == 0); 534 map.assumeSafeAppend; 535 assert(map.capacity >= 2); 536 } 537 538 /++ 539 `remove(key)` does nothing if the given key does not exist and returns false. If the given key does exist, it removes it from the AA and returns true. 540 541 Complexity: `O(log(s))` (not exist) or `O(n)` (exist), where `s` is the count of the strings with the same length as they key. 542 +/ 543 bool remove()(scope const(char)[] key) @trusted pure nothrow @nogc 544 { 545 size_t index; 546 if (implementation && implementation.findIndex(key, index)) 547 { 548 implementation.removeAt(index); 549 return true; 550 } 551 return false; 552 } 553 554 version(mir_test) static if (is(T == int)) 555 /// 556 unittest 557 { 558 StringMap!double map; 559 map["a"] = 3.0; 560 map["c"] = 4.0; 561 assert(map.remove("c")); 562 assert(!map.remove("c")); 563 assert(map.remove("a")); 564 assert(map.length == 0); 565 assert(map.capacity == 0); 566 assert(map.assumeSafeAppend.capacity >= 2); 567 } 568 569 /++ 570 Finds position of the key in the associative array . 571 572 Return: An index starting from `0` that corresponds to the key or `-1` if the associative array doesn't contain the key. 573 574 Complexity: `O(log(s))`, where `s` is the number of the keys with the same length as the input key. 575 +/ 576 ptrdiff_t findPos()(scope const(char)[] key) @trusted pure nothrow @nogc const 577 { 578 if (!implementation) 579 return -1; 580 size_t index; 581 if (!implementation.findIndex(key, index)) 582 return -1; 583 return implementation._indices[index]; 584 } 585 586 version(mir_test) static if (is(T == int)) 587 /// 588 @safe pure unittest 589 { 590 StringMap!double map; 591 map["c"] = 3.0; 592 map["La"] = 4.0; 593 map["a"] = 5.0; 594 595 assert(map.findPos("C") == -1); 596 assert(map.findPos("c") == 0); 597 assert(map.findPos("La") == 1); 598 assert(map.findPos("a") == 2); 599 600 map.remove("c"); 601 602 assert(map.findPos("c") == -1); 603 assert(map.findPos("La") == 0); 604 assert(map.findPos("a") == 1); 605 } 606 607 /++ 608 Complexity: `O(log(s))`, where `s` is the number of the keys with the same length as the input key. 609 +/ 610 inout(T)* opBinaryRight(string op : "in")(scope const(char)[] key) pure nothrow @nogc inout 611 { 612 if (!implementation) 613 return null; 614 size_t index; 615 if (!implementation.findIndex(key, index)) 616 return null; 617 assert (index < length); 618 index = implementation.indices[index]; 619 assert (index < length); 620 return &implementation.values[index]; 621 } 622 623 version(mir_test) static if (is(T == int)) 624 /// 625 @safe nothrow pure unittest 626 { 627 StringMap!double map; 628 assert(("c" in map) is null); 629 map["c"] = 3.0; 630 assert(*("c" in map) == 3.0); 631 } 632 633 /++ 634 Complexity: `O(log(s))`, where `s` is the number of the keys with the same length as the input key. 635 +/ 636 ref inout(T) opIndex()(scope const(char)[] key) @trusted pure inout //@nogc 637 { 638 size_t index; 639 if (implementation && implementation.findIndex(key, index)) 640 { 641 assert (index < length); 642 index = implementation._indices[index]; 643 assert (index < length); 644 return implementation._values[index]; 645 } 646 import mir.exception: MirException; 647 throw new MirException("No member: ", key); 648 } 649 650 version(mir_test) static if (is(T == int)) 651 /// 652 @safe pure unittest 653 { 654 StringMap!double map; 655 map["c"] = 3.0; 656 map["La"] = 4.0; 657 map["a"] = 5.0; 658 659 map["La"] += 10; 660 assert(map["La"] == 14.0); 661 } 662 663 /++ 664 Complexity: `O(log(s))` (exist) or `O(n)` (not exist), where `s` is the count of the strings with the same length as they key. 665 +/ 666 ref T opIndexAssign(R)(auto ref R value, string key) @trusted pure nothrow 667 { 668 import core.lifetime: forward, move; 669 T v; 670 v = forward!value; 671 return opIndexAssign(move(v), key); 672 } 673 674 /// ditto 675 ref T opIndexAssign()(T value, string key) @trusted pure nothrow 676 { 677 size_t index; 678 if (_expect(!implementation, false)) 679 { 680 implementation = new Impl; 681 } 682 else 683 { 684 if (key.length + 1 < implementation.lengthTable.length) 685 { 686 if (implementation.findIndex(key, index)) 687 { 688 assert (index < length); 689 index = implementation._indices[index]; 690 assert (index < length); 691 move(cast()value, cast()(implementation._values[index])); 692 return implementation._values[index]; 693 } 694 assert (index <= length); 695 } 696 else 697 { 698 index = length; 699 } 700 } 701 assert (index <= length); 702 implementation.insertAt(key, move(cast()value), index); 703 index = implementation._indices[index]; 704 return implementation._values[index]; 705 } 706 707 /++ 708 Looks up key; if it exists returns corresponding value else evaluates and returns defaultValue. 709 710 Complexity: `O(log(s))`, where `s` is the number of the keys with the same length as the input key. 711 +/ 712 inout(T) get()(scope const(char)[] key, lazy inout(T) defaultValue) inout 713 { 714 size_t index; 715 if (implementation && implementation.findIndex(key, index)) 716 { 717 assert (index < length); 718 index = implementation.indices[index]; 719 assert (index < length); 720 return implementation.values[index]; 721 } 722 return defaultValue; 723 } 724 725 version(mir_test) static if (is(T == int)) 726 /// 727 @safe pure unittest 728 { 729 StringMap!int map; 730 map["c"] = 3; 731 assert(map.get("c", 1) == 3); 732 assert(map.get("C", 1) == 1); 733 } 734 735 /++ 736 Looks up key; if it exists returns corresponding value else evaluates value, adds it to the associative array and returns it. 737 738 Complexity: `O(log(s))` (exist) or `O(n)` (not exist), where `s` is the count of the strings with the same length as they key. 739 +/ 740 ref T require()(string key, lazy T value = T.init) 741 { 742 size_t index; 743 if (_expect(!implementation, false)) 744 { 745 implementation = new Impl; 746 } 747 else 748 { 749 if (key.length + 1 < implementation.lengthTable.length) 750 { 751 if (implementation.findIndex(key, index)) 752 { 753 assert (index < length); 754 index = implementation.indices[index]; 755 assert (index < length); 756 return implementation.values[index]; 757 } 758 assert (index <= length); 759 } 760 else 761 { 762 index = length; 763 } 764 } 765 assert (index <= length); 766 implementation.insertAt(key, value, index); 767 index = implementation.indices[index]; 768 return implementation.values[index]; 769 } 770 771 version(mir_test) static if (is(T == int)) 772 /// 773 @safe pure unittest 774 { 775 StringMap!int map = ["aa": 1]; 776 int add3(ref int x) { x += 3; return x; } 777 assert(add3(map.require("aa", 10)) == 4); 778 assert(add3(map.require("bb", 10)) == 13); 779 assert(map.require("a", 100)); 780 assert(map.require("aa") == 4); 781 assert(map.require("bb") == 13); 782 assert(map.keys == ["aa", "bb", "a"]); 783 } 784 785 /++ 786 Converts to a builtin associative array. 787 788 Complexity: `O(n)`. 789 +/ 790 template toAA() 791 { 792 static if (__traits(compiles, (ref const T a) { T b; b = a;})) 793 { 794 /// 795 T[string] toAA()() const 796 { 797 T[string] ret; 798 foreach (i; 0 .. length) 799 { 800 ret[implementation.keys[i]] = implementation.values[i]; 801 } 802 return ret; 803 } 804 } 805 else 806 { 807 /// 808 T[string] toAA()() 809 { 810 T[string] ret; 811 foreach (i; 0 .. length) 812 { 813 ret[implementation.keys[i]] = implementation.values[i]; 814 } 815 return ret; 816 } 817 818 /// 819 const(T)[string] toAA()() const 820 { 821 const(T)[string] ret; 822 foreach (i; 0 .. length) 823 { 824 ret[implementation.keys[i]] = implementation.values[i]; 825 } 826 return ret; 827 } 828 } 829 } 830 831 /// 832 version(mir_test) static if (is(T == int)) 833 @safe pure nothrow unittest 834 { 835 StringMap!int map = ["k": 1]; 836 int[string] aa = map.toAA; 837 assert(aa["k"] == 1); 838 } 839 840 private static struct Impl 841 { 842 import core.lifetime: move; 843 import mir.conv: emplaceRef; 844 845 size_t _length; 846 string* _keys; 847 T* _values; 848 U* _indices; 849 U[] _lengthTable; 850 851 /++ 852 +/ 853 this()(string[] keys, T[] values) @trusted pure nothrow 854 { 855 assert(keys.length == values.length); 856 if (keys.length == 0) 857 return; 858 _length = keys.length; 859 _keys = keys.ptr; 860 _values = values.ptr; 861 _indices = new U[keys.length].ptr; 862 size_t maxKeyLength; 863 foreach(ref key; keys) 864 if (key.length > maxKeyLength) 865 maxKeyLength = key.length; 866 _lengthTable = new U[maxKeyLength + 2]; 867 sortIndices(); 868 } 869 870 private void sortIndices() pure nothrow 871 { 872 import mir.ndslice.sorting: sort; 873 import mir.ndslice.topology: indexed; 874 import mir.string_table: smallerStringFirst; 875 foreach (i, ref index; indices) 876 index = cast(U)i; 877 878 indices.sort!((a, b) => smallerStringFirst(keys[a], keys[b])); 879 auto sortedKeys = _keys.indexed(indices); 880 size_t maxKeyLength = sortedKeys[$ - 1].length; 881 882 size_t ski; 883 foreach (length; 0 .. maxKeyLength + 1) 884 { 885 while(ski < sortedKeys.length && sortedKeys[ski].length == length) 886 ski++; 887 _lengthTable[length + 1] = cast(U)ski; 888 } 889 } 890 891 void insertAt()(string key, T value, size_t i) @trusted 892 { 893 pragma(inline, false); 894 895 assert(i <= length); 896 { 897 auto a = keys; 898 a ~= key; 899 _keys = a.ptr; 900 } 901 { 902 auto a = values; 903 a ~= move(cast()value); 904 _values = a.ptr; 905 } 906 { 907 auto a = indices; 908 a ~= 0; 909 _indices = a.ptr; 910 911 if (__ctfe) 912 { 913 foreach_reverse (idx; i .. length) 914 { 915 _indices[idx + 1] = _indices[idx]; 916 } 917 } 918 else 919 { 920 import core.stdc.string: memmove; 921 memmove(_indices + i + 1, _indices + i, (length - i) * U.sizeof); 922 } 923 assert(length <= U.max); 924 _indices[i] = cast(U)length; 925 _length++; 926 } 927 { 928 if (key.length + 2 <= lengthTable.length) 929 { 930 ++lengthTable[key.length + 1 .. $]; 931 } 932 else 933 { 934 auto oldLen = _lengthTable.length; 935 _lengthTable.length = key.length + 2; 936 auto oldVal = oldLen ? _lengthTable[oldLen - 1] : 0; 937 _lengthTable[oldLen .. key.length + 1] = oldVal; 938 _lengthTable[key.length + 1] = oldVal + 1; 939 } 940 } 941 } 942 943 void removeAt()(size_t i) 944 { 945 assert(i < length); 946 auto j = _indices[i]; 947 assert(j < length); 948 { 949 --_lengthTable[_keys[j].length + 1 .. $]; 950 } 951 { 952 if (__ctfe) 953 { 954 foreach (idx; i .. length) 955 { 956 _indices[idx] = _indices[idx + 1]; 957 _indices[idx] = _indices[idx + 1]; 958 } 959 } 960 else 961 { 962 import core.stdc.string: memmove; 963 memmove(_indices + i, _indices + i + 1, (length - 1 - i) * U.sizeof); 964 } 965 foreach (ref elem; indices[0 .. $ - 1]) 966 if (elem > j) 967 elem--; 968 } 969 { 970 if (__ctfe) 971 { 972 foreach_reverse (idx; j .. length - 1) 973 { 974 _keys[idx] = _keys[idx + 1]; 975 _values[idx] = move(_values[idx + 1]); 976 } 977 } 978 else 979 { 980 import core.stdc.string: memmove; 981 destroy!false(_values[j]); 982 memmove(_keys + j, _keys + j + 1, (length - 1 - j) * string.sizeof); 983 memmove(_values + j, _values + j + 1, (length - 1 - j) * T.sizeof); 984 emplaceRef(_values[length - 1]); 985 } 986 } 987 _length--; 988 _lengthTable = _lengthTable[0 .. length ? _keys[_indices[length - 1]].length + 2 : 0]; 989 } 990 991 size_t length()() @safe pure nothrow @nogc const @property 992 { 993 return _length; 994 } 995 996 inout(string)[] keys()() @trusted inout @property pure @nogc nothrow 997 { 998 return _keys[0 .. _length]; 999 } 1000 1001 inout(T)[] values()() @trusted inout @property pure @nogc nothrow 1002 { 1003 return _values[0 .. _length]; 1004 } 1005 1006 inout(U)[] indices()() @trusted inout @property pure @nogc nothrow 1007 { 1008 return _indices[0 .. _length]; 1009 } 1010 1011 inout(U)[] lengthTable()() @trusted inout @property pure @nogc nothrow 1012 { 1013 return _lengthTable; 1014 } 1015 1016 auto sortedKeys()() @trusted const @property 1017 { 1018 import mir.ndslice.topology: indexed; 1019 return _keys.indexed(indices); 1020 } 1021 1022 bool findIndex()(scope const(char)[] key, ref size_t index) @trusted pure nothrow @nogc const 1023 { 1024 import mir.utility: _expect; 1025 if (_expect(key.length + 1 < _lengthTable.length, true)) 1026 { 1027 1028 // 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1029 // 0 1 2 3 4 5 6 8 9 10 12 16 1030 1031 auto low = _lengthTable[key.length] + 0u; 1032 auto high = _lengthTable[key.length + 1] + 0u; 1033 while (low < high) 1034 { 1035 const mid = (low + high) / 2; 1036 1037 import core.stdc.string: memcmp; 1038 int r = void; 1039 1040 if (__ctfe) 1041 r = __cmp(key, _keys[_indices[mid]]); 1042 else 1043 r = memcmp(key.ptr, _keys[_indices[mid]].ptr, key.length); 1044 1045 if (r == 0) 1046 { 1047 index = mid; 1048 return true; 1049 } 1050 if (r > 0) 1051 low = mid + 1; 1052 else 1053 high = mid; 1054 } 1055 index = low; 1056 } 1057 return false; 1058 } 1059 } 1060 1061 /// Sorts table according to the keys 1062 ref sort(alias less = "a < b")() return 1063 { 1064 import mir.functional: naryFun; 1065 import mir.ndslice.sorting: sort; 1066 import mir.ndslice.topology: zip; 1067 if (length) { 1068 zip(implementation.keys, implementation.values).sort!((l, r) => naryFun!less(l.a, r.a)); 1069 implementation.sortIndices; 1070 } 1071 return this; 1072 } 1073 1074 import std.traits: isAssociativeArray, isAggregateType; 1075 // static if (!isAssociativeArray!(.basicElementType!T) && (!isAggregateType!(.basicElementType!T) || __traits(hasMember, .basicElementType!T, "opCmp"))) 1076 /// `opCmp` Implementation. Doesn't depend on order 1077 int opCmp()(scope const typeof(this) rhs) scope const @trusted // pure nothrow @nogc 1078 { 1079 if (sizediff_t d = length - rhs.length) 1080 return d < 0 ? -1 : 1; 1081 if (length == 0) 1082 return 0; 1083 1084 foreach (i, index; implementation.indices) 1085 if (auto d = __cmp(implementation._keys[index], rhs.implementation._keys[rhs.implementation._indices[i]])) 1086 return d; 1087 foreach (i, index; implementation.indices) 1088 static if (__traits(compiles, __cmp(implementation._values[index], rhs.implementation._values[rhs.implementation._indices[i]]))) 1089 { 1090 if (auto d = __cmp(implementation._values[index], rhs.implementation._values[rhs.implementation._indices[i]])) 1091 return d; 1092 } 1093 else 1094 static if (__traits(hasMember, T, "opCmp")) 1095 { 1096 if (auto d = implementation._values[index].opCmp(rhs.implementation._values[rhs.implementation._indices[i]])) 1097 return d; 1098 } 1099 else 1100 { 1101 return 1102 implementation._values[index] < rhs.implementation._values[rhs.implementation._indices[i]] ? -1 : 1103 implementation._values[index] > rhs.implementation._values[rhs.implementation._indices[i]] ? +1 : 0; 1104 } 1105 return false; 1106 } 1107 1108 private Impl* implementation; 1109 1110 /// 1111 static if (is(T == const) || is(T == immutable)) 1112 { 1113 alias serdeKeysProxy = Unqual!T; 1114 } 1115 else 1116 { 1117 alias serdeKeysProxy = T; 1118 } 1119 } 1120 1121 version(mir_test) 1122 /// 1123 @safe unittest 1124 { 1125 class C 1126 { 1127 this(int x) { this.x = x; } 1128 int x; 1129 bool opEquals(scope const C rhs) const scope @safe pure nothrow @nogc 1130 { 1131 return x == rhs.x; 1132 } 1133 1134 override size_t toHash() @safe const scope pure nothrow @nogc 1135 { 1136 return x; 1137 } 1138 } 1139 StringMap!(const C) table; 1140 const v0 = new C(42); 1141 const v1 = new C(43); 1142 table["0"] = v0; 1143 table["1"] = v1; 1144 assert(table.keys == ["0", "1"]); 1145 assert(table.values == [v0, v1]); // TODO: qualify unittest as `pure` when this is inferred `pure` 1146 static assert(is(typeof(table.values) == const(C)[])); 1147 } 1148 1149 version(mir_test) 1150 /// 1151 @safe pure unittest 1152 { 1153 StringMap!int table; 1154 table["L"] = 3; 1155 table["A"] = 2; 1156 table["val"] = 1; 1157 assert(table.keys == ["L", "A", "val"]); 1158 assert(table.values == [3, 2, 1]); 1159 assert(table["A"] == 2); 1160 table.values[2] += 10; 1161 assert(table["A"] == 2); 1162 assert(table["L"] == 3); 1163 assert(table["val"] == 11); 1164 assert(table.keys == ["L", "A", "val"]); 1165 assert(table.values == [3, 2, 11]); 1166 table.remove("A"); 1167 assert(table.keys == ["L", "val"]); 1168 assert(table.values == [3, 11]); 1169 assert(table["L"] == 3); 1170 assert(table["val"] == 11); 1171 1172 assert(table == table); 1173 1174 // sorting 1175 table["A"] = 2; 1176 table.sort; 1177 assert(table.keys == ["A", "L", "val"]); 1178 assert(table.values == [2, 3, 11]); 1179 assert(table["A"] == 2); 1180 assert(table["L"] == 3); 1181 assert(table["val"] == 11); 1182 } 1183 1184 version(mir_test) 1185 /// 1186 @safe pure unittest 1187 { 1188 static void testEquals(X, Y)() 1189 { 1190 X x; 1191 Y y; 1192 assert(x == y); 1193 1194 x["L"] = 3; 1195 assert(x != y); 1196 x["A"] = 2; 1197 assert(x != y); 1198 x["val"] = 1; 1199 assert(x != y); 1200 1201 y["val"] = 1; 1202 assert(x != y); 1203 y["L"] = 3; 1204 assert(x != y); 1205 y["A"] = 2; 1206 assert(x == y); 1207 1208 x = X.init; 1209 assert(x != y); 1210 1211 y = Y.init; 1212 assert(x == y); 1213 } 1214 1215 testEquals!(StringMap!int, StringMap!uint)(); 1216 testEquals!(StringMap!int, uint[string])(); 1217 testEquals!(uint[string], StringMap!int)(); 1218 } 1219 1220 version(mir_test) 1221 @safe pure unittest 1222 { 1223 import mir.algebraic_alias.json: JsonAlgebraic; 1224 import mir.string_map: StringMap; 1225 1226 StringMap!JsonAlgebraic token; 1227 token[`access_token`] = "secret-data"; 1228 token[`expires_in`] = 3599; 1229 token[`token_type`] = "Bearer"; 1230 1231 assert(token[`access_token`] == "secret-data"); 1232 assert(token[`expires_in`] == 3599); 1233 assert(token[`token_type`] == "Bearer"); // mir/string_map.d(511): No member: token_type 1234 1235 const tkType = `token_type` in token; 1236 1237 assert((*tkType) == "Bearer"); // *tkType contains value 3599 1238 } 1239 1240 /// 1241 template intersectionMap(alias merger) 1242 { 1243 /// 1244 StringMap!V intersectionMap(V)(StringMap!V a, StringMap!V b) 1245 { 1246 import mir.functional : naryFun; 1247 typeof(return) res; 1248 foreach (key, ref value; a) 1249 if (auto bValPtr = key in b) 1250 res[key] = naryFun!merger(value, *bValPtr); 1251 return res; 1252 } 1253 } 1254 1255 /// 1256 version(mir_test) 1257 @safe pure 1258 unittest { 1259 import mir.test: should; 1260 import mir.string_map : StringMap; 1261 auto m0 = StringMap!int(["foo", "bar"], [1, 2]); 1262 auto m1 = StringMap!int(["foo"], [2]); 1263 auto m2 = StringMap!int(["foo"], [3]); 1264 intersectionMap!"a + b"(m0, m1).should == m2; 1265 } 1266 1267 /// 1268 template unionMap(alias merger) 1269 { 1270 /// 1271 StringMap!V unionMap(V)(StringMap!V a, StringMap!V b) 1272 { 1273 import mir.functional : naryFun; 1274 typeof(return) res; 1275 foreach (key, ref value; a) 1276 if (auto bValPtr = key in b) 1277 res[key] = naryFun!merger(value, *bValPtr); 1278 else 1279 res[key] = value; 1280 foreach (key, ref value; b) 1281 if (key !in res) 1282 res[key] = value; 1283 return res; 1284 } 1285 } 1286 1287 /// 1288 version(mir_test) 1289 @safe pure 1290 unittest { 1291 import mir.test: should; 1292 import mir.string_map : StringMap; 1293 auto m0 = StringMap!int(["foo", "bar"], [1, 2]); 1294 auto m1 = StringMap!int(["foo"], [2]); 1295 auto m2 = StringMap!int(["foo", "bar"], [3, 2]); 1296 unionMap!"a + b"(m0, m1).should == m2; 1297 }