1 /++ 2 $(H1 Ordered string-value associtaive 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 11 /++ 12 Checks if the type is instance of $(LREF StringMap). 13 +/ 14 enum isStringMap(T) = is(Unqual!T == StringMap!V, V); 15 16 version(mir_test) 17 /// 18 unittest 19 { 20 static assert(isStringMap!(StringMap!int)); 21 static assert(isStringMap!(const StringMap!int)); 22 static assert(!isStringMap!int); 23 } 24 25 /++ 26 Ordered string-value associtaive array with extremely fast lookup. 27 28 Params: 29 T = mutable value type, can be instance of $(AlgebraicREF Algebraic) for example. 30 U = an unsigned type that can hold an index of keys. `U.max` must be less then the maximum possible number of struct members. 31 +/ 32 struct StringMap(T, U = uint) 33 if (isMutable!T && !__traits(hasMember, T, "opPostMove") && __traits(isUnsigned, U)) 34 { 35 import mir.utility: _expect; 36 import core.lifetime: move; 37 import mir.conv: emplaceRef; 38 39 private alias Impl = StructImpl!(T, U); 40 private Impl* implementation; 41 42 /// 43 // current implementation is workaround for linking bugs when used in self referencing algebraic types 44 bool opEquals(const StringMap rhs) const 45 { 46 if (keys != rhs.keys) 47 return false; 48 if (implementation) 49 foreach (const i; 0 .. implementation._length) 50 if (implementation._values[i] != rhs.implementation._values[i]) 51 return false; 52 return true; 53 } 54 55 // // linking bug 56 // version(none) 57 // { 58 // /++ 59 // +/ 60 // bool opEquals()(typeof(null)) @safe pure nothrow @nogc const 61 // { 62 // return implementation is null; 63 // } 64 65 // version(mir_test) static if (is(T == int)) 66 // /// 67 // @safe pure unittest 68 // { 69 // StringMap!int map; 70 // assert(map == null); 71 // map = StringMap!int(["key" : 1]); 72 // assert(map != null); 73 // map.remove("key"); 74 // assert(map != null); 75 // } 76 // } 77 78 /++ 79 Reset the associtave array 80 +/ 81 ref opAssign()(typeof(null)) return @safe pure nothrow @nogc 82 { 83 implementation = null; 84 return this; 85 } 86 87 version(mir_test) static if (is(T == int)) 88 /// 89 @safe pure unittest 90 { 91 StringMap!int map = ["key" : 1]; 92 map = null; 93 } 94 95 /++ 96 Initialize the associtave array with default value. 97 +/ 98 this()(typeof(null) aa) @safe pure nothrow @nogc 99 { 100 implementation = null; 101 } 102 103 version(mir_test) static if (is(T == int)) 104 /// Usefull for default funcion argument. 105 @safe pure unittest 106 { 107 StringMap!int map = null; // 108 } 109 110 /++ 111 Constructs an associative array using keys and values from the builtin associative array 112 Complexity: `O(n log(n))` 113 +/ 114 this()(T[string] aa) @trusted pure nothrow 115 { 116 this(aa.keys, aa.values); 117 } 118 119 version(mir_test) static if (is(T == int)) 120 /// 121 @safe pure unittest 122 { 123 StringMap!int map = ["key" : 1]; 124 assert(map.findPos("key") == 0); 125 } 126 127 /// 128 string toString()() const 129 { 130 import mir.format: stringBuf; 131 stringBuf buffer; 132 toString(buffer); 133 return buffer.data.idup; 134 } 135 136 ///ditto 137 void toString(W)(scope ref W w) const 138 { 139 bool next; 140 w.put('['); 141 import mir.format: printEscaped, EscapeFormat, print; 142 foreach (i, ref value; values) 143 { 144 if (next) 145 w.put(`, `); 146 next = true; 147 w.put('\"'); 148 printEscaped!(char, EscapeFormat.ion)(w, keys[i]); 149 w.put(`": `); 150 print(w, value); 151 } 152 w.put(']'); 153 } 154 155 /++ 156 Constructs an associative array using keys and values. 157 Params: 158 keys = mutable array of keys 159 values = mutable array of values 160 Key and value arrays must have the same length. 161 162 Complexity: `O(n log(n))` 163 +/ 164 this()(string[] keys, T[] values) @trusted pure nothrow 165 { 166 assert(keys.length == values.length); 167 implementation = new Impl(keys, values); 168 } 169 170 version(mir_test) static if (is(T == int)) 171 /// 172 @safe pure unittest 173 { 174 auto keys = ["ba", "a"]; 175 auto values = [1.0, 3.0]; 176 auto map = StringMap!double(keys, values); 177 assert(map.keys is keys); 178 assert(map.values is values); 179 } 180 181 /++ 182 Returns: number of elements in the table. 183 +/ 184 size_t length()() @safe pure nothrow @nogc const @property 185 { 186 return implementation ? implementation.length : 0; 187 } 188 189 version(mir_test) static if (is(T == int)) 190 /// 191 @safe pure unittest 192 { 193 StringMap!double map; 194 assert(map.length == 0); 195 map["a"] = 3.0; 196 assert(map.length == 1); 197 map["c"] = 4.0; 198 assert(map.length == 2); 199 assert(map.remove("c")); 200 assert(map.length == 1); 201 assert(!map.remove("c")); 202 assert(map.length == 1); 203 assert(map.remove("a")); 204 assert(map.length == 0); 205 } 206 207 /++ 208 Returns a dynamic array, the elements of which are the keys in the associative array. 209 Doesn't allocate a new copy. 210 211 Complexity: `O(1)` 212 +/ 213 const(string)[] keys()() @safe pure nothrow @nogc const @property 214 { 215 return implementation ? implementation.keys : null; 216 } 217 218 version(mir_test) static if (is(T == int)) 219 /// 220 @safe pure unittest 221 { 222 StringMap!double map; 223 assert(map.keys == []); 224 map["c"] = 4.0; 225 assert(map.keys == ["c"]); 226 map["a"] = 3.0; 227 assert(map.keys == ["c", "a"]); 228 map.remove("c"); 229 assert(map.keys == ["a"]); 230 map.remove("a"); 231 assert(map.keys == []); 232 map["c"] = 4.0; 233 assert(map.keys == ["c"]); 234 } 235 236 /++ 237 Returns a dynamic array, the elements of which are the values in the associative array. 238 Doesn't allocate a new copy. 239 240 Complexity: `O(1)` 241 +/ 242 inout(T)[] values()() @safe pure nothrow @nogc inout @property 243 { 244 return implementation ? implementation.values : null; 245 } 246 247 version(mir_test) static if (is(T == int)) 248 /// 249 @safe pure unittest 250 { 251 StringMap!double map; 252 assert(map.values == []); 253 map["c"] = 4.0; 254 assert(map.values == [4.0]); 255 map["a"] = 3.0; 256 assert(map.values == [4.0, 3.0]); 257 map.values[0]++; 258 assert(map.values == [5.0, 3.0]); 259 map.remove("c"); 260 assert(map.values == [3.0]); 261 map.remove("a"); 262 assert(map.values == []); 263 map["c"] = 4.0; 264 assert(map.values == [4.0]); 265 } 266 267 /++ 268 (Property) Gets the current capacity of an associative array. 269 The capacity is the size that the underlaynig slices can grow to before the underlying arrays may be reallocated or extended. 270 271 Complexity: `O(1)` 272 +/ 273 size_t capacity()() @safe pure nothrow const @property 274 { 275 import mir.utility: min; 276 277 return !implementation ? 0 : min( 278 implementation.keys.capacity, 279 implementation.values.capacity, 280 implementation.indices.capacity, 281 ); 282 } 283 284 version(mir_test) static if (is(T == int)) 285 /// 286 unittest 287 { 288 StringMap!double map; 289 assert(map.capacity == 0); 290 map["c"] = 4.0; 291 assert(map.capacity >= 1); 292 map["a"] = 3.0; 293 assert(map.capacity >= 2); 294 map.remove("c"); 295 map.assumeSafeAppend; 296 assert(map.capacity >= 2); 297 } 298 299 /++ 300 Reserves capacity for an associative array. 301 The capacity is the size that the underlaying slices can grow to before the underlying arrays may be reallocated or extended. 302 +/ 303 size_t reserve()(size_t newcapacity) @trusted pure nothrow 304 { 305 import mir.utility: min; 306 307 if (_expect(!implementation, false)) 308 { 309 implementation = new Impl; 310 } 311 312 auto keysV = implementation.keys; 313 auto keysVCaacity = keysV.reserve(newcapacity); 314 implementation._keys = keysV.ptr; 315 316 auto valuesV = implementation.values; 317 auto valuesCapacity = valuesV.reserve(newcapacity); 318 implementation._values = valuesV.ptr; 319 320 auto indicesV = implementation.indices; 321 auto indicesCapacity = indicesV.reserve(newcapacity); 322 implementation._indices = indicesV.ptr; 323 324 return min( 325 keysVCaacity, 326 valuesCapacity, 327 indicesCapacity, 328 ); 329 } 330 331 version(mir_test) static if (is(T == int)) 332 /// 333 unittest 334 { 335 StringMap!double map; 336 auto capacity = map.reserve(10); 337 assert(capacity >= 10); 338 assert(map.capacity == capacity); 339 map["c"] = 4.0; 340 assert(map.capacity == capacity); 341 map["a"] = 3.0; 342 assert(map.capacity >= 2); 343 assert(map.remove("c")); 344 capacity = map.reserve(20); 345 assert(capacity >= 20); 346 assert(map.capacity == capacity); 347 } 348 349 /++ 350 Assume that it is safe to append to this associative array. 351 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. 352 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. 353 354 Warning: Calling this function, and then using references to data located after the given associative array results in undefined behavior. 355 356 Returns: The input is returned. 357 +/ 358 ref inout(typeof(this)) assumeSafeAppend()() @system nothrow inout return 359 { 360 if (implementation) 361 { 362 implementation.keys.assumeSafeAppend; 363 implementation.values.assumeSafeAppend; 364 implementation.indices.assumeSafeAppend; 365 } 366 return this; 367 } 368 369 version(mir_test) static if (is(T == int)) 370 /// 371 unittest 372 { 373 StringMap!double map; 374 map["c"] = 4.0; 375 map["a"] = 3.0; 376 assert(map.capacity >= 2); 377 map.remove("c"); 378 assert(map.capacity == 0); 379 map.assumeSafeAppend; 380 assert(map.capacity >= 2); 381 } 382 383 /++ 384 Removes all remaining keys and values from an associative array. 385 386 Complexity: `O(1)` 387 +/ 388 void clear()() @safe pure nothrow @nogc 389 { 390 if (implementation) 391 { 392 implementation._length = 0; 393 implementation._lengthTable = implementation._lengthTable[0 .. 0]; 394 } 395 396 } 397 398 version(mir_test) static if (is(T == int)) 399 /// 400 unittest 401 { 402 StringMap!double map; 403 map["c"] = 4.0; 404 map["a"] = 3.0; 405 map.clear; 406 assert(map.length == 0); 407 assert(map.capacity == 0); 408 map.assumeSafeAppend; 409 assert(map.capacity >= 2); 410 } 411 412 /++ 413 `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. 414 415 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. 416 +/ 417 bool remove()(scope const(char)[] key) @trusted pure nothrow @nogc 418 { 419 size_t index; 420 if (implementation && implementation.findIndex(key, index)) 421 { 422 implementation.removeAt(index); 423 return true; 424 } 425 return false; 426 } 427 428 version(mir_test) static if (is(T == int)) 429 /// 430 unittest 431 { 432 StringMap!double map; 433 map["a"] = 3.0; 434 map["c"] = 4.0; 435 assert(map.remove("c")); 436 assert(!map.remove("c")); 437 assert(map.remove("a")); 438 assert(map.length == 0); 439 assert(map.capacity == 0); 440 assert(map.assumeSafeAppend.capacity >= 2); 441 } 442 443 /++ 444 Finds position of the key in the associative array . 445 446 Return: An index starting from `0` that corresponds to the key or `-1` if the associative array doesn't contain the key. 447 448 Complexity: `O(log(s))`, where `s` is the number of the keys with the same length as the input key. 449 +/ 450 ptrdiff_t findPos()(scope const(char)[] key) @trusted pure nothrow @nogc const 451 { 452 if (!implementation) 453 return -1; 454 size_t index; 455 if (!implementation.findIndex(key, index)) 456 return -1; 457 return implementation._indices[index]; 458 } 459 460 version(mir_test) static if (is(T == int)) 461 /// 462 @safe pure unittest 463 { 464 StringMap!double map; 465 map["c"] = 3.0; 466 map["La"] = 4.0; 467 map["a"] = 5.0; 468 469 assert(map.findPos("C") == -1); 470 assert(map.findPos("c") == 0); 471 assert(map.findPos("La") == 1); 472 assert(map.findPos("a") == 2); 473 474 map.remove("c"); 475 476 assert(map.findPos("c") == -1); 477 assert(map.findPos("La") == 0); 478 assert(map.findPos("a") == 1); 479 } 480 481 /++ 482 Complexity: `O(log(s))`, where `s` is the number of the keys with the same length as the input key. 483 +/ 484 inout(T)* opBinaryRight(string op : "in")(scope const(char)[] key) @system pure nothrow @nogc inout 485 { 486 if (!implementation) 487 return null; 488 size_t index; 489 if (!implementation.findIndex(key, index)) 490 return null; 491 assert (index < length); 492 index = implementation.indices[index]; 493 assert (index < length); 494 return implementation._values + index; 495 } 496 497 version(mir_test) static if (is(T == int)) 498 /// 499 @system nothrow pure unittest 500 { 501 StringMap!double map; 502 assert(("c" in map) is null); 503 map["c"] = 3.0; 504 assert(*("c" in map) == 3.0); 505 } 506 507 /++ 508 Complexity: `O(log(s))`, where `s` is the number of the keys with the same length as the input key. 509 +/ 510 ref inout(T) opIndex()(scope const(char)[] key) @trusted pure inout //@nogc 511 { 512 size_t index; 513 if (implementation && implementation.findIndex(key, index)) 514 { 515 assert (index < length); 516 index = implementation._indices[index]; 517 assert (index < length); 518 return implementation._values[index]; 519 } 520 import mir.exception: MirException; 521 throw new MirException("No member: ", key); 522 } 523 524 version(mir_test) static if (is(T == int)) 525 /// 526 @safe pure unittest 527 { 528 StringMap!double map; 529 map["c"] = 3.0; 530 map["La"] = 4.0; 531 map["a"] = 5.0; 532 533 map["La"] += 10; 534 assert(map["La"] == 14.0); 535 } 536 537 /++ 538 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. 539 +/ 540 ref T opIndexAssign(R)(auto ref R value, string key) @trusted pure nothrow 541 { 542 import core.lifetime: forward, move; 543 T v; 544 v = forward!value; 545 return opIndexAssign(move(v), key); 546 } 547 548 /// ditto 549 ref T opIndexAssign()(T value, string key) @trusted pure nothrow 550 { 551 size_t index; 552 if (_expect(!implementation, false)) 553 { 554 implementation = new Impl; 555 } 556 else 557 { 558 if (key.length + 1 < implementation.lengthTable.length) 559 { 560 if (implementation.findIndex(key, index)) 561 { 562 assert (index < length); 563 index = implementation._indices[index]; 564 assert (index < length); 565 implementation._values[index] = move(value); 566 return implementation._values[index]; 567 } 568 assert (index <= length); 569 } 570 else 571 { 572 index = length; 573 } 574 } 575 assert (index <= length); 576 implementation.insertAt(key, move(value), index); 577 index = implementation._indices[index]; 578 return implementation._values[index]; 579 } 580 581 /++ 582 Looks up key; if it exists returns corresponding value else evaluates and returns defaultValue. 583 584 Complexity: `O(log(s))`, where `s` is the number of the keys with the same length as the input key. 585 +/ 586 inout(T) get()(scope const(char)[] key, lazy inout(T) defaultValue) 587 { 588 size_t index; 589 if (implementation && implementation.findIndex(key, index)) 590 { 591 assert (index < length); 592 index = implementation.indices[index]; 593 assert (index < length); 594 return implementation.values[index]; 595 } 596 return defaultValue; 597 } 598 599 version(mir_test) static if (is(T == int)) 600 /// 601 @safe pure unittest 602 { 603 StringMap!int map; 604 map["c"] = 3; 605 assert(map.get("c", 1) == 3); 606 assert(map.get("C", 1) == 1); 607 } 608 609 /++ 610 Looks up key; if it exists returns corresponding value else evaluates value, adds it to the associative array and returns it. 611 612 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. 613 +/ 614 ref T require()(string key, lazy T value = T.init) 615 { 616 import std.stdio; 617 size_t index; 618 if (_expect(!implementation, false)) 619 { 620 implementation = new Impl; 621 } 622 else 623 { 624 if (key.length + 1 < implementation.lengthTable.length) 625 { 626 if (implementation.findIndex(key, index)) 627 { 628 assert (index < length); 629 index = implementation.indices[index]; 630 assert (index < length); 631 return implementation.values[index]; 632 } 633 assert (index <= length); 634 } 635 else 636 { 637 index = length; 638 } 639 } 640 assert (index <= length); 641 implementation.insertAt(key, value, index); 642 index = implementation.indices[index]; 643 return implementation.values[index]; 644 } 645 646 version(mir_test) static if (is(T == int)) 647 /// 648 @safe pure unittest 649 { 650 StringMap!int map = ["aa": 1]; 651 int add3(ref int x) { x += 3; return x; } 652 assert(add3(map.require("aa", 10)) == 4); 653 assert(add3(map.require("bb", 10)) == 13); 654 assert(map.require("a", 100)); 655 assert(map.require("aa") == 4); 656 assert(map.require("bb") == 13); 657 assert(map.keys == ["aa", "bb", "a"]); 658 } 659 660 /++ 661 Converts the associtave array to a common Dlang associative array. 662 663 Complexity: `O(n)`. 664 +/ 665 template toAA() 666 { 667 static if (__traits(compiles, (ref const T a) { T b; b = a;})) 668 { 669 /// 670 T[string] toAA()() const 671 { 672 T[string] ret; 673 foreach (i; 0 .. length) 674 { 675 ret[implementation.keys[i]] = implementation.values[i]; 676 } 677 return ret; 678 } 679 } 680 else 681 { 682 /// 683 T[string] toAA()() 684 { 685 T[string] ret; 686 foreach (i; 0 .. length) 687 { 688 ret[implementation.keys[i]] = implementation.values[i]; 689 } 690 return ret; 691 } 692 693 /// 694 const(T)[string] toAA()() const 695 { 696 const(T)[string] ret; 697 foreach (i; 0 .. length) 698 { 699 ret[implementation.keys[i]] = implementation.values[i]; 700 } 701 return ret; 702 } 703 } 704 } 705 706 /// 707 @safe pure nothrow unittest 708 { 709 StringMap!int map = ["k": 1]; 710 int[string] aa = map.toAA; 711 assert(aa["k"] == 1); 712 } 713 } 714 715 version(mir_test) 716 /// 717 unittest 718 { 719 StringMap!int table; 720 table["L"] = 3; 721 table["A"] = 2; 722 table["val"] = 1; 723 assert(table.keys == ["L", "A", "val"]); 724 assert(table.values == [3, 2, 1]); 725 assert(table["A"] == 2); 726 table.values[2] += 10; 727 assert(table["A"] == 2); 728 assert(table["L"] == 3); 729 assert(table["val"] == 11); 730 assert(table.keys == ["L", "A", "val"]); 731 assert(table.values == [3, 2, 11]); 732 table.remove("A"); 733 assert(table.keys == ["L", "val"]); 734 assert(table.values == [3, 11]); 735 assert(table["L"] == 3); 736 assert(table["val"] == 11); 737 738 assert(table == table); 739 } 740 741 private struct StructImpl(T, U = uint) 742 if (!__traits(hasMember, T, "opPostMove") && __traits(isUnsigned, U)) 743 { 744 import core.lifetime: move; 745 import mir.conv: emplaceRef; 746 747 size_t _length; 748 string* _keys; 749 T* _values; 750 U* _indices; 751 U[] _lengthTable; 752 753 /++ 754 +/ 755 this()(string[] keys, T[] values) @trusted pure nothrow 756 { 757 import mir.array.allocation: array; 758 import mir.ndslice.sorting: makeIndex; 759 import mir.ndslice.topology: iota, indexed; 760 import mir.string_table: smallerStringFirst; 761 762 assert(keys.length == values.length); 763 if (keys.length == 0) 764 return; 765 _length = keys.length; 766 _keys = keys.ptr; 767 _values = values.ptr; 768 _indices = keys.makeIndex!(U, smallerStringFirst).ptr; 769 auto sortedKeys = _keys.indexed(indices); 770 size_t maxKeyLength = sortedKeys[$ - 1].length; 771 _lengthTable = new U[maxKeyLength + 2]; 772 773 size_t ski; 774 foreach (length; 0 .. maxKeyLength + 1) 775 { 776 while(ski < sortedKeys.length && sortedKeys[ski].length == length) 777 ski++; 778 _lengthTable[length + 1] = cast(U)ski; 779 } 780 } 781 782 void insertAt()(string key, T value, size_t i) @trusted 783 { 784 pragma(inline, false); 785 786 assert(i <= length); 787 { 788 auto a = keys; 789 a ~= key; 790 _keys = a.ptr; 791 } 792 { 793 auto a = values; 794 a ~= move(value); 795 _values = a.ptr; 796 } 797 { 798 auto a = indices; 799 a ~= 0; 800 _indices = a.ptr; 801 802 if (__ctfe) 803 { 804 foreach_reverse (idx; i .. length) 805 { 806 _indices[idx + 1] = _indices[idx]; 807 } 808 } 809 else 810 { 811 import core.stdc..string: memmove; 812 memmove(_indices + i + 1, _indices + i, (length - i) * U.sizeof); 813 } 814 assert(length <= U.max); 815 _indices[i] = cast(U)length; 816 _length++; 817 } 818 { 819 if (key.length + 2 <= lengthTable.length) 820 { 821 ++lengthTable[key.length + 1 .. $]; 822 } 823 else 824 { 825 auto oldLen = _lengthTable.length; 826 _lengthTable.length = key.length + 2; 827 auto oldVal = oldLen ? _lengthTable[oldLen - 1] : 0; 828 _lengthTable[oldLen .. key.length + 1] = oldVal; 829 _lengthTable[key.length + 1] = oldVal + 1; 830 } 831 } 832 } 833 834 void removeAt()(size_t i) 835 { 836 assert(i < length); 837 auto j = _indices[i]; 838 assert(j < length); 839 { 840 --_lengthTable[_keys[j].length + 1 .. $]; 841 } 842 { 843 if (__ctfe) 844 { 845 foreach (idx; i .. length) 846 { 847 _indices[idx] = _indices[idx + 1]; 848 _indices[idx] = _indices[idx + 1]; 849 } 850 } 851 else 852 { 853 import core.stdc..string: memmove; 854 memmove(_indices + i, _indices + i + 1, (length - 1 - i) * U.sizeof); 855 } 856 foreach (ref elem; indices[0 .. $ - 1]) 857 if (elem > j) 858 elem--; 859 } 860 { 861 if (__ctfe) 862 { 863 foreach_reverse (idx; j .. length - 1) 864 { 865 _keys[idx] = _keys[idx + 1]; 866 _values[idx] = move(_values[idx + 1]); 867 } 868 } 869 else 870 { 871 import core.stdc..string: memmove; 872 destroy!false(_values[j]); 873 memmove(_keys + j, _keys + j + 1, (length - 1 - j) * string.sizeof); 874 memmove(_values + j, _values + j + 1, (length - 1 - j) * T.sizeof); 875 emplaceRef(_values[length - 1]); 876 } 877 } 878 _length--; 879 _lengthTable = _lengthTable[0 .. length ? _keys[_indices[length - 1]].length + 2 : 0]; 880 } 881 882 size_t length()() @safe pure nothrow @nogc const @property 883 { 884 return _length; 885 } 886 887 inout(string)[] keys()() @trusted inout @property 888 { 889 return _keys[0 .. _length]; 890 } 891 892 inout(T)[] values()() @trusted inout @property 893 { 894 return _values[0 .. _length]; 895 } 896 897 inout(U)[] indices()() @trusted inout @property 898 { 899 return _indices[0 .. _length]; 900 } 901 902 inout(U)[] lengthTable()() @trusted inout @property 903 { 904 return _lengthTable; 905 } 906 907 auto sortedKeys()() @trusted const @property 908 { 909 import mir.ndslice.topology: indexed; 910 return _keys.indexed(indices); 911 } 912 913 bool findIndex()(scope const(char)[] key, ref size_t index) @trusted pure nothrow @nogc const 914 { 915 import mir.utility: _expect; 916 if (_expect(key.length + 1 < _lengthTable.length, true)) 917 { 918 919 // 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 920 // 0 1 2 3 4 5 6 8 9 10 12 16 921 922 auto low = _lengthTable[key.length] + 0u; 923 auto high = _lengthTable[key.length + 1] + 0u; 924 while (low < high) 925 { 926 auto mid = (low + high) / 2; 927 928 import core.stdc..string: memcmp; 929 int r = void; 930 931 if (__ctfe) 932 r = __cmp(key, _keys[_indices[mid]]); 933 else 934 r = memcmp(key.ptr, _keys[_indices[mid]].ptr, key.length); 935 936 if (r == 0) 937 { 938 index = mid; 939 return true; 940 } 941 if (r > 0) 942 low = mid + 1; 943 else 944 high = mid; 945 } 946 index = low; 947 } 948 return false; 949 } 950 } 951 952 version(mir_test) 953 unittest 954 { 955 import mir.algebraic_alias.json: JsonAlgebraic; 956 import mir.string_map: StringMap; 957 958 StringMap!JsonAlgebraic token; 959 token[`access_token`] = "secret-data"; 960 token[`expires_in`] = 3599; 961 token[`token_type`] = "Bearer"; 962 963 assert(token[`access_token`] == "secret-data"); 964 assert(token[`expires_in`] == 3599); 965 assert(token[`token_type`] == "Bearer"); // mir/string_map.d(511): No member: token_type 966 967 const tkType = `token_type` in token; 968 969 assert((*tkType) == "Bearer"); // *tkType contains value 3599 970 }