1 module util.multi_index; 2 3 /** 4 * TODO: 5 * random access index 6 * insertAfter ? insertBefore ? 7 * fix BitHackery 8 * make MutableView a per index thing? 9 * modify(r, mod, rollback) 10 * contain const/immutable value types 11 * other indices? 12 * dup 13 * make reserve perform reserve on all appropriate indices? 14 * ensure MultiIndexContainer is strongly exception safe. 15 */ 16 17 version = BucketHackery; 18 19 import std.array; 20 import std.range; 21 import std.exception: enforce; 22 import std.algorithm: find, swap, copy, fill, max, startsWith, moveAll; 23 import std.algorithm: move, sort, map; 24 import std.traits: isImplicitlyConvertible, isDynamicArray; 25 import util.replace: Replace; 26 import std.typetuple: TypeTuple, staticMap, NoDuplicates, staticIndexOf, allSatisfy; 27 import std.functional: unaryFun, binaryFun; 28 import std.string: format; 29 version(PtrHackery){ 30 import core.bitop: bt, bts, btr; 31 } 32 33 // stopgap allocator implementation 34 // drat: using GCAllocator is probably less efficient than arr.length = i 35 // cf GC.extend 36 37 struct GCAllocator{ 38 static T* allocate(T)(size_t i) { 39 return (new T[](i)).ptr; 40 } 41 42 static void deallocate(T)(T* t) { 43 // gc deallocates when it does. whee. 44 } 45 46 } 47 48 import core.stdc.stdlib: malloc, free; 49 import core.stdc.string: memset; 50 import core.memory: GC; 51 import core.exception: OutOfMemoryError; 52 53 struct MallocAllocator{ 54 static T* allocate(T)(size_t i) { 55 T* p = cast(T*) malloc(T.sizeof * i); 56 memset(p, 0, T.sizeof * i); 57 if(!p) throw new OutOfMemoryError(); 58 GC.addRange(cast(void*) p, T.sizeof * i); 59 return p; 60 } 61 static void deallocate(T)(T* t) { 62 GC.removeRange(cast(void*) t); 63 free(t); 64 } 65 } 66 67 import std.traits: isIterable, isNarrowString, ForeachType, Unqual; 68 // stolen from phobos and modified. 69 // when phobos gets real allocators, this hopefully will go away. 70 Unqual!(ForeachType!Range)[] allocatedArray(Allocator,Range)(Range r) 71 if (isIterable!Range && !isNarrowString!Range) 72 { 73 alias Unqual!(ForeachType!Range) E; 74 static if (hasLength!Range) 75 { 76 if(r.length == 0) return null; 77 78 auto result = Allocator.allocate!E(r.length)[0 .. r.length]; 79 80 size_t i = 0; 81 foreach (e; r) 82 { 83 // hacky 84 static if (is(typeof(e.opAssign(e)))) 85 { 86 // this should be in-place construction 87 emplace!E(result.ptr + i, e); 88 } 89 else 90 { 91 result[i] = e; 92 } 93 i++; 94 } 95 return result; 96 } 97 else 98 { 99 auto result = Allocator.allocate!(Unqual!E)(1)[0 .. 1]; 100 size_t i = 0; 101 foreach (e; r) 102 { 103 result[i] = e; 104 i++; 105 if(i == result.length) { 106 auto nlen = result.length*2+1; 107 auto nresult = Allocator.allocate!(Unqual!E)(nlen)[0 .. nlen]; 108 auto rest = moveAll(result, nresult); 109 fill(rest, E.init); 110 Allocator.deallocate(result.ptr); 111 result = nresult; 112 } 113 } 114 return result[0 .. i]; 115 } 116 } 117 118 template IsAllocator(T) { 119 enum bool IsAllocator = is(typeof(T.allocate!int(1)) == int*) && 120 is(typeof(T.deallocate!int((int*).init)) == void); 121 } 122 123 /// A doubly linked list index. 124 template Sequenced() { 125 // no memory allocations occur within this index. 126 enum bool BenefitsFromSignals = false; 127 // damn you, ddoc 128 /// _ 129 template Inner(ThisContainer,ThisNode, Value, ValueView, size_t N, Allocator) { 130 131 /** 132 Defines the index' primary range, which embodies a 133 bidirectional range 134 */ 135 struct SequencedRange(bool is_const) { 136 static if(is_const) { 137 alias const(ThisNode) Node; 138 alias const(ThisContainer) Container; 139 }else { 140 alias ThisContainer Container; 141 alias ThisNode Node; 142 } 143 Container c; 144 Node* _front, _back; 145 alias _front front_node; 146 alias _back back_node; 147 148 this(Container _c, Node* f, Node* b) { 149 c = _c; 150 _front = f; 151 _back = b; 152 } 153 154 @property bool empty() { 155 return 156 !(_front && _back && 157 _front !is _back.index!N.next && 158 _back !is _front.index!N.prev); 159 } 160 @property front(){ 161 return _front.value; 162 } 163 @property back(){ 164 return _back.value; 165 } 166 167 @property save(){ return this; } 168 169 void popFront() 170 in{ 171 assert(_front !is _front.index!N.next); 172 }body{ 173 _front = _front.index!N.next; 174 } 175 176 void popBack(){ 177 _back = _back.index!N.prev; 178 } 179 } 180 181 alias TypeTuple!(N,SequencedRange) IndexTuple; 182 alias TypeTuple!(N) NodeTuple; 183 184 // node implementation 185 mixin template NodeMixin(size_t N){ 186 typeof(this)* next, prev; 187 188 // inserts node between this and this.next 189 // a,b = this, this.next; then 190 // old: a <-> b, null <- node -> null 191 // new: a <-> node <-> b 192 void insertNext(typeof(this)* node) nothrow 193 in{ 194 assert(node !is null); 195 assert(node.index!N.prev is null, 196 format("node.prev = %x",node.index!N.prev)); 197 assert(node.index!N.next is null, 198 format("node.next = %x",node.index!N.next)); 199 }body{ 200 typeof(this)* n = next; 201 next = node; 202 node.index!N.prev = &this; 203 if(n !is null) n.index!N.prev = node; 204 node.index!N.next = n; 205 } 206 207 // a,b = this, this.prev; then 208 // old: b <-> a, null <- node -> null 209 // new: b <-> node <-> a 210 void insertPrev(typeof(this)* node) nothrow 211 in{ 212 assert(node !is null); 213 assert(node.index!N.prev is null, 214 format("node.prev = %x",node.index!N.prev)); 215 assert(node.index!N.next is null, 216 format("node.next = %x",node.index!N.next)); 217 }body{ 218 typeof(this)* p = prev; 219 if(p !is null) p.index!N.next = node; 220 node.index!N.prev = p; 221 prev = node; 222 node.index!N.next = &this; 223 } 224 225 // a,b,c = this, this.next, this.next.next; then 226 // old: a <-> b <-> c 227 // new: a <-> c, null <- b -> null 228 typeof(this)* removeNext() nothrow 229 in{ 230 assert(next); 231 }body{ 232 typeof(this)* n = next, nn = n.index!N.next; 233 next = nn; 234 if(nn) nn.index!N.prev = &this; 235 n.index!N.prev = n.index!N.next = null; 236 return n; 237 } 238 239 // a,b,c = this, this.prev, this.prev.prev; then 240 // old: c <-> b <-> a 241 // new: c <-> a, null <- b -> null 242 typeof(this)* removePrev() nothrow 243 in{ 244 assert(prev); 245 }body{ 246 typeof(this)* p = prev, pp = p.index!N.prev; 247 prev = pp; 248 if(pp) pp.index!N.next = &this; 249 p.index!N.prev = p.index!N.next = null; 250 return p; 251 } 252 } 253 254 /// Sequenced index implementation 255 /// 256 /// Requirements: the following symbols must be 257 /// defined in the scope in which this index is mixed in: 258 /// 259 // dangit, ddoc, show my single starting underscore! 260 /// ThisNode, Value, __InsertAllBut!N, __InsertAll, __Replace, 261 /// __RemoveAllBut!N, node_count 262 mixin template IndexMixin(size_t N, alias Range_0){ 263 ThisNode* _front, _back; 264 alias Range_0!false SeqRange; 265 alias Range_0!true ConstSeqRange; 266 267 template IsMyRange(T) { 268 enum bool IsMyRange = 269 is(T == SeqRange) || 270 is(T == ConstSeqRange); 271 } 272 273 /** 274 Returns the number of elements in the container. 275 276 Complexity: $(BIGOH 1). 277 */ 278 @property size_t length() const{ 279 return node_count; 280 } 281 282 /** 283 Property returning $(D true) if and only if the container has no 284 elements. 285 286 Complexity: $(BIGOH 1) 287 */ 288 @property bool empty() const{ 289 return node_count == 0; 290 } 291 292 /** 293 Fetch a range that spans all the elements in the container. 294 295 Complexity: $(BIGOH 1) 296 */ 297 SeqRange opSlice(){ 298 return SeqRange(this, _front, _back); 299 } 300 301 ConstSeqRange opSlice() const{ 302 return ConstSeqRange(this, _front, _back); 303 } 304 305 /** 306 Complexity: $(BIGOH 1) 307 */ 308 @property front() inout{ 309 return _front.value; 310 } 311 312 /** 313 Complexity: $(BIGOH r(n)); $(BR) $(BIGOH 1) for this index 314 */ 315 @property void front(Value value){ 316 _Replace(_front, value); 317 } 318 319 320 /** 321 * Complexity: $(BIGOH 1) 322 */ 323 @property back() inout{ 324 return _back.value; 325 } 326 327 /** 328 * Complexity: $(BIGOH r(n)) 329 */ 330 @property void back(Value value) { 331 _Replace(_back, value); 332 } 333 334 void _ClearIndex() { 335 _front = _back = null; 336 } 337 338 void clear(){ 339 _Clear(); 340 } 341 /** 342 Moves moveme.front to the position before tohere.front and inc both ranges. 343 Probably not safe to use either range afterwards, but who knows. 344 Preconditions: moveme and tohere are both ranges of the same container. 345 Postconditions: moveme.front is incremented 346 Complexity: $(BIGOH 1) 347 */ 348 void relocateFront(PosRange)(ref PosRange moveme, PosRange tohere) 349 if(is(ElementType!PosRange == Position!(ThisNode)) || 350 is(PosRange == SeqRange)) 351 in{ 352 // rubbish, now we can't ensure two ranges are from same 353 // index, container 354 static if(is(PosRange == SeqRange)) { 355 // well, do it if you can 356 assert(moveme.c == tohere.c); 357 assert(moveme.front_node); 358 assert(tohere.front_node); 359 }else { 360 assert(moveme.front.node); 361 assert(tohere.front.node); 362 } 363 }body{ 364 static if(is(PosRange == SeqRange)) { 365 ThisNode* m = moveme.front_node; 366 ThisNode* n = tohere.front_node; 367 }else { 368 ThisNode* m = moveme.front.node; 369 ThisNode* n = tohere.front.node; 370 } 371 moveme.popFront(); 372 if (m is n) return; //?? 373 if (m is n.index!N.prev) return; //?? 374 _Remove(m); 375 n.index!N.insertPrev(m); 376 if(n is _front) _front = m; 377 } 378 /** 379 Moves moveme.back to the position after tohere.back and dec both ranges. 380 Probably not safe to use either range afterwards, but who knows. 381 Preconditions: moveme and tohere are both ranges of the same container 382 Postconditions: moveme.back is decremented 383 Complexity: $(BIGOH 1) 384 */ 385 void relocateBack(PosRange)(ref PosRange moveme, PosRange tohere) 386 if(is(ElementType!PosRange == Position!(ThisNode)) || 387 is(PosRange == SeqRange)) 388 in{ 389 static if(is(PosRange == SeqRange)) { 390 assert(moveme.c == tohere.c); 391 assert(moveme.back_node); 392 assert(tohere.back_node); 393 }else { 394 assert(moveme.back.node); 395 assert(tohere.back.node); 396 } 397 }body{ 398 static if(is(PosRange == SeqRange)) { 399 ThisNode* m = moveme.back_node; 400 ThisNode* n = tohere.back_node; 401 }else{ 402 ThisNode* m = moveme.back.node; 403 ThisNode* n = tohere.back.node; 404 } 405 moveme.popBack(); 406 if (m is n) return; //?? 407 if (m is n.index!N.next) return; //?? 408 _Remove(m); 409 n.index!N.insertNext(m); 410 if(n is _back) _back = m; 411 } 412 413 void modify(SomeRange, Modifier)(SomeRange r, Modifier mod) 414 if(is(SomeRange == SeqRange) || 415 is(ElementType!SomeRange == Position!(ThisNode))) { 416 while(!r.empty) { 417 static if(is(SomeRange == SeqRange)){ 418 ThisNode* node = r.front_node; 419 }else{ 420 ThisNode* node = r.front.node; 421 } 422 _Modify(node, mod); 423 r.popFront(); 424 } 425 } 426 427 /** 428 Replaces r.front with value 429 Returns: whether replacement succeeded 430 Complexity: ?? 431 */ 432 bool replace(Position!ThisNode r, Value value) 433 { 434 return _Replace(r.node, value); 435 } 436 437 bool _insertFront(ThisNode* node) nothrow 438 in{ 439 assert(node !is null); 440 assert(node.index!N.prev is null); 441 assert(node.index!N.next is null); 442 }body{ 443 if(_front is null){ 444 debug assert(_back is null); 445 _front = _back = node; 446 }else{ 447 _front.index!N.insertPrev(node); 448 _front = node; 449 } 450 451 return true; 452 } 453 454 alias _insertBack _Insert; 455 456 bool _insertBack(ThisNode* node) nothrow 457 in{ 458 debug assert (node !is null); 459 }body{ 460 if(_front is null){ 461 debug assert(_back is null); 462 _front = _back = node; 463 }else{ 464 _back.index!N.insertNext(node); 465 _back = node; 466 } 467 468 return true; 469 } 470 471 /++ 472 Inserts every element of stuff not rejected by another index into the front 473 of the index. 474 Returns: 475 The number of elements inserted. 476 Complexity: $(BIGOH n $(SUB stuff) * i(n)); $(BR) $(BIGOH n $(SUB stuff)) for 477 this index 478 +/ 479 size_t insertFront(SomeRange)(SomeRange stuff) 480 if(isInputRange!SomeRange && 481 isImplicitlyConvertible!(ElementType!SomeRange, 482 ValueView)) 483 { 484 import std.array: empty, front; 485 if(stuff.empty) return 0; 486 size_t count = 0; 487 ThisNode* prev; 488 while(count == 0 && !stuff.empty){ 489 prev = _InsertAllBut!N(stuff.front); 490 if (!prev) continue; 491 _insertFront(prev); 492 stuff.popFront(); 493 count++; 494 } 495 foreach(item; stuff){ 496 ThisNode* node = _InsertAllBut!N(item); 497 if (!node) continue; 498 prev.index!N.insertNext(node); 499 prev = node; 500 count ++; 501 } 502 return count; 503 } 504 505 /++ 506 Inserts value into the front of the sequence, if no other index rejects value 507 Returns: 508 The number if elements inserted into the index. 509 Complexity: $(BIGOH i(n)); $(BR) $(BIGOH 1) for this index 510 +/ 511 size_t insertFront(SomeValue)(SomeValue value) 512 if(isImplicitlyConvertible!(SomeValue, ValueView)){ 513 ThisNode* node = _InsertAllBut!N(value); 514 if(!node) return 0; 515 _insertFront(node); 516 return 1; 517 } 518 519 /++ 520 Inserts every element of stuff not rejected by another index into the back 521 of the index. 522 Returns: 523 The number of elements inserted. 524 Complexity: $(BIGOH n $(SUB stuff) * i(n)); $(BR) $(BIGOH n $(SUB stuff)) for 525 this index 526 +/ 527 size_t insertBack (SomeRange)(SomeRange stuff) 528 if(isInputRange!SomeRange && 529 isImplicitlyConvertible!(ElementType!SomeRange, ValueView)) 530 { 531 size_t count = 0; 532 533 foreach(item; stuff){ 534 count += insertBack(item); 535 } 536 return count; 537 } 538 539 /++ 540 Inserts value into the back of the sequence, if no other index rejects value 541 Returns: 542 The number if elements inserted into the index. 543 Complexity: $(BIGOH i(n)); $(BR) $(BIGOH 1) for this index 544 +/ 545 size_t insertBack(SomeValue)(SomeValue value) 546 if(isImplicitlyConvertible!(SomeValue, ValueView)){ 547 ThisNode* node = _InsertAllBut!N(value); 548 if (!node) return 0; 549 _insertBack(node); 550 return 1; 551 } 552 553 /++ 554 Forwards to insertBack 555 +/ 556 alias insertBack insert; 557 558 // reckon we'll trust n is somewhere between _front and _back 559 void _Remove(ThisNode* n){ 560 if(n is _front){ 561 _removeFront(); 562 }else{ 563 ThisNode* prev = n.index!N.prev; 564 prev.index!N.removeNext(); 565 if(n is _back) _back = prev; 566 } 567 } 568 569 ThisNode* _removeFront() 570 in{ 571 assert(_back !is null); 572 assert(_front !is null); 573 }body{ 574 ThisNode* n = _front; 575 if(_back == _front){ 576 _back = _front = null; 577 }else{ 578 _front = _front.index!N.next; 579 n.index!N.next = null; 580 _front.index!N.prev = null; 581 } 582 return n; 583 } 584 585 /++ 586 Removes the value at the front of the index from the container. 587 Precondition: $(D !empty) 588 Complexity: $(BIGOH d(n)); $(BIGOH 1) for this index 589 +/ 590 void removeFront(){ 591 _RemoveAll(_front); 592 } 593 594 /++ 595 Removes the value at the back of the index from the container. 596 Precondition: $(D !empty) 597 Complexity: $(BIGOH d(n)); $(BR) $(BIGOH 1) for this index 598 +/ 599 void removeBack(){ 600 _RemoveAll(_back); 601 } 602 /++ 603 Forwards to removeBack 604 +/ 605 alias removeBack removeAny; 606 607 /++ 608 Removes the values of r from the container. 609 Preconditions: r came from this index 610 Complexity: $(BIGOH n $(SUB r) * d(n)), $(BR) $(BIGOH n $(SUB r)) for this index 611 +/ 612 SeqRange remove(R)(R r) 613 if(is(R == SeqRange) || 614 is(ElementType!R == Position!ThisNode)) 615 { 616 while(!r.empty){ 617 static if(is(R == SeqRange)){ 618 ThisNode* f = r.front_node; 619 }else{ 620 ThisNode* f = r.front.node; 621 r.front.obliterated = true; 622 } 623 r.popFront(); 624 _RemoveAll(f); 625 } 626 return SeqRange(this,null,null); 627 } 628 // in: old is from this index 629 // out: old is disconnected from this index and replaced by newnode 630 void _NodeReplace(ThisNode* old, ThisNode* newnode) { 631 ThisNode* next = old.index!N.next; 632 ThisNode* prev = old.index!N.prev; 633 newnode.index!N.next = next; 634 newnode.index!N.prev = prev; 635 if(next) { 636 next.index!N.prev = newnode; 637 }else { 638 assert(old is _back); 639 _back = newnode; 640 } 641 if(prev) { 642 prev.index!N.next = newnode; 643 }else{ 644 assert(old is _front); 645 _front = newnode; 646 } 647 648 old.index!N.prev = null; 649 old.index!N.next = null; 650 } 651 652 653 void _Check(){ 654 } 655 656 string toString0(){ 657 string r = "["; 658 auto rng = opSlice(); 659 while(!rng.empty){ 660 r ~= format("%s", rng.front); 661 rng.popFront(); 662 r ~= rng.empty ? "]" : ", "; 663 } 664 return r; 665 } 666 667 private SeqRange fromNode(ThisNode* n){ 668 return SeqRange(this, n, this.index!N._back); 669 } 670 } 671 672 } 673 } 674 675 /// A random access index. 676 template RandomAccess() { 677 enum bool BenefitsFromSignals = false; 678 /// _ 679 template Inner(ThisContainer,ThisNode, Value, ValueView, size_t N, Allocator) { 680 alias TypeTuple!() NodeTuple; 681 alias TypeTuple!(N,ThisContainer) IndexTuple; 682 683 // node implementation 684 mixin template NodeMixin(){ 685 size_t _index; 686 } 687 688 /// index implementation 689 /// 690 /// Requirements: the following symbols must be 691 /// defined in the scope in which this index is mixed in: 692 /// 693 // dangit, ddoc, show my single starting underscore! 694 /// ThisNode, Value, __InsertAllBut!N, __InsertAll, __Replace, 695 /// __RemoveAllBut!N, node_count 696 mixin template IndexMixin(size_t N, ThisContainer){ 697 ThisNode*[] ra; 698 699 /// Defines the index' primary range, which embodies a 700 /// random access range 701 struct RARangeT(bool is_const) { 702 static if(is_const) { 703 alias const(ThisNode) Node; 704 alias const(ThisContainer) Container; 705 }else { 706 alias ThisContainer Container; 707 alias ThisNode Node; 708 } 709 Container c; 710 size_t s, e; 711 712 this(Container _c, size_t _s, size_t _e) { 713 c = _c; 714 s = _s; 715 e = _e; 716 } 717 718 private @property Node* front_node(){ 719 assert(s < e && e <= c.index!N.length); 720 return c.index!N.ra[s]; 721 } 722 private @property Node* back_node() { 723 assert(s < e && e <= c.index!N.length); 724 return c.index!N.ra[e-1]; 725 } 726 727 @property front(){ 728 assert(s < e && e <= c.index!N.length); 729 return front_node.value; 730 } 731 732 void popFront(){ s++; } 733 734 @property bool empty()const{ return s >= e; } 735 @property size_t length()const { return s <= e ? e-s : 0; } 736 737 @property back(){ 738 return back_node.value; 739 } 740 741 void popBack(){ e--; } 742 743 @property save(){ return this; } 744 745 auto opIndex(size_t i){ return nth_node(i).value; } 746 747 private auto nth_node(size_t i) { return c.index!N.ra[i]; } 748 749 auto opSlice(size_t a, size_t b) { 750 assert(a <= b && b < length); 751 return RARangeT(c, s+a, s+b); 752 } 753 754 static if(!is_const) { 755 private @property front_node(ThisNode* n) { 756 assert(s < e && e <= c.index!N.length); 757 c.index!N.ra[s] = n; 758 } 759 } 760 } 761 762 763 alias RARangeT!true ConstRARange; 764 alias RARangeT!false RARange; 765 766 /* 767 static assert(is(typeof( 768 { 769 RARange r = void; // can define a range object 770 if (r.empty) {} // can test for empty 771 r.popFront(); // can invoke popFront() 772 auto h = r.front; // can get the front of the range 773 }))); 774 775 static assert(isInputRange!RARange); 776 static assert(isForwardRange!RARange); 777 static assert(isBidirectionalRange!RARange); 778 static assert(isRandomAccessRange!RARange); 779 */ 780 781 template IsMyRange(T) { 782 enum bool IsMyRange = 783 is(T == RARange) || 784 is(T == ConstRARange); 785 } 786 787 788 /** 789 Fetch a range that spans all the elements in the container. 790 791 Complexity: $(BIGOH 1) 792 */ 793 RARange opSlice (){ 794 return RARange(this, 0, node_count); 795 } 796 ConstRARange opSlice () const{ 797 return ConstRARange(this, 0, node_count); 798 } 799 800 /** 801 Fetch a range that spans all the elements in the container from 802 index $(D a) (inclusive) to index $(D b) (exclusive). 803 Preconditions: a <= b && b <= length 804 805 Complexity: $(BIGOH 1) 806 */ 807 RARange opSlice(size_t a, size_t b){ 808 enforce(a <= b && b <= length); 809 return RARange(this, a, b); 810 } 811 ConstRARange opSlice(size_t a, size_t b) const{ 812 enforce(a <= b && b <= length); 813 return ConstRARange(this, a, b); 814 } 815 816 /** 817 Returns the number of elements in the container. 818 819 Complexity: $(BIGOH 1). 820 */ 821 @property size_t length()const{ 822 return node_count; 823 } 824 825 /** 826 Property returning $(D true) if and only if the container has no elements. 827 828 Complexity: $(BIGOH 1) 829 */ 830 @property bool empty() const{ 831 return node_count == 0; 832 } 833 834 /** 835 Returns the _capacity of the index, which is the length of the 836 underlying store 837 */ 838 @property size_t capacity() const{ 839 return ra.length; 840 } 841 842 /** 843 Ensures sufficient capacity to accommodate $(D count) elements. 844 845 Postcondition: $(D capacity >= count) 846 847 Complexity: $(BIGOH ??) if $(D e > capacity), 848 otherwise $(BIGOH 1). 849 */ 850 void reserve(size_t count){ 851 if(ra.length < count){ 852 auto newra = Allocator.allocate!(ThisNode*)(count)[0 .. count]; 853 auto rest = moveAll(ra, newra); 854 fill(rest, null); 855 Allocator.deallocate(ra.ptr); 856 ra = newra; 857 } 858 } 859 860 /** 861 Complexity: $(BIGOH 1) 862 */ 863 @property front() inout{ 864 return ra[0].value; 865 } 866 867 /** 868 Complexity: $(BIGOH r(n)); $(BR) $(BIGOH 1) for this index 869 */ 870 @property void front(ValueView value){ 871 _Replace(ra[0], cast(Value) value); 872 } 873 874 /** 875 Complexity: $(BIGOH 1) 876 */ 877 @property back() inout{ 878 return ra[node_count-1].value; 879 } 880 881 /** 882 Complexity: $(BIGOH r(n)); $(BR) $(BIGOH 1) for this index 883 */ 884 @property void back(ValueView value){ 885 _Replace(ra[node_count-1], cast(Value) value); 886 } 887 888 void _ClearIndex(){ 889 fill(ra, (ThisNode*).init); 890 } 891 892 /// _ 893 void clear(){ 894 _Clear(); 895 } 896 897 /** 898 Preconditions: i < length 899 Complexity: $(BIGOH 1) 900 */ 901 auto opIndex(size_t i) inout{ 902 enforce(i < length); 903 return ra[i].value; 904 } 905 /** 906 Sets index i to value, unless another index refuses value 907 Preconditions: i < length 908 Returns: the resulting _value at index i 909 Complexity: $(BIGOH r(n)); $(BR) $(BIGOH 1) for this index 910 */ 911 ValueView opIndexAssign(ValueView value, size_t i){ 912 enforce(i < length); 913 _Replace(ra[i], cast(Value) value); 914 return ra[i].value; 915 } 916 917 /** 918 Swaps element at index $(D i) with element at index $(D j). 919 Preconditions: i < length && j < length 920 Complexity: $(BIGOH 1) 921 */ 922 void swapAt( size_t i, size_t j){ 923 enforce(i < length && j < length); 924 swap(ra[i], ra[j]); 925 swap(ra[i].index!N._index, ra[j].index!N._index); 926 } 927 928 /** 929 Removes the last element from this index. 930 Preconditions: !empty 931 Complexity: $(BIGOH d(n)); $(BR) $(BIGOH 1) for this index 932 */ 933 void removeBack(){ 934 _RemoveAllBut!N(ra[node_count-1]); 935 dealloc(ra[node_count]); 936 ra[node_count] = null; 937 } 938 939 alias removeBack removeAny; 940 941 void _Remove(ThisNode* n){ 942 size_t i = n.index!N._index; 943 copy(ra[i+1 .. node_count], ra[i .. node_count-1]); 944 foreach(k,r; ra[i .. node_count-1]) 945 r.index!N._index = i+k; 946 ra[node_count-1] = null; 947 return; 948 } 949 950 /** 951 inserts value in the back of this index. 952 Complexity: $(BIGOH i(n)), $(BR) amortized $(BIGOH 1) for this index 953 */ 954 size_t insertBack(SomeValue)(SomeValue value) 955 if(isImplicitlyConvertible!(SomeValue, ValueView)) 956 { 957 ThisNode* n = _InsertAllBut!N(value); 958 if (!n) return 0; 959 node_count--; 960 _Insert(n); 961 node_count++; 962 return 1; 963 } 964 965 /** 966 inserts elements of r in the back of this index. 967 Complexity: $(BIGOH n $(SUB r) * i(n)), $(BR) amortized $(BIGOH n $(SUB r)) 968 for this index 969 */ 970 size_t insertBack(SomeRange)(SomeRange r) 971 if(isImplicitlyConvertible!(ElementType!SomeRange, ValueView)) 972 { 973 enum haslen = hasLength!SomeRange; 974 975 static if(haslen){ 976 if(capacity() < node_count + r.length){ 977 reserve(node_count + r.length); 978 } 979 } 980 size_t count = 0; 981 foreach(e; r){ 982 count += insertBack(e); 983 } 984 return count; 985 } 986 987 void _Insert(ThisNode* node){ 988 if (node_count >= ra.length){ 989 reserve(max(ra.length * 2 + 1, node_count+1)); 990 } 991 ra[node_count] = node; 992 ra[node_count].index!N._index = node_count; 993 } 994 995 /** 996 inserts elements of r in the back of this index. 997 Complexity: $(BIGOH n $(SUB r) * i(n)), $(BR) amortized $(BIGOH n $(SUB r)) 998 for this index 999 */ 1000 alias insertBack insert; 1001 1002 /** 1003 Perform mod on r.front and performs any necessary fixups to container's 1004 indices. If the result of mod violates any index' invariant, r.front is 1005 removed from the container. 1006 Preconditions: !r.empty, $(BR) 1007 mod is a callable of the form void mod(ref Value) 1008 Complexity: $(BIGOH m(n)), $(BR) $(BIGOH 1) for this index 1009 */ 1010 1011 void modify(SomeRange, Modifier)(SomeRange r, Modifier mod) 1012 if(is(SomeRange == RARange) || 1013 is(ElementType!SomeRange == Position!(ThisNode))) { 1014 while(!r.empty) { 1015 static if(is(SomeRange == RARange)){ 1016 ThisNode* node = r.front_node; 1017 }else{ 1018 ThisNode* node = r.front.node; 1019 } 1020 _Modify(node, mod); 1021 r.popFront(); 1022 } 1023 } 1024 /** 1025 Replaces r.front with value 1026 Returns: whether replacement succeeded 1027 Complexity: ?? 1028 */ 1029 bool replace(Position!ThisNode r, ValueView value) { 1030 return _Replace(r.node, cast(Value) value); 1031 } 1032 1033 static bool _RemovePred(Position!ThisNode a, Position!ThisNode b) { 1034 return a.node.index!N._index < b.node.index!N._index; 1035 } 1036 static size_t _RemoveUn(Position!ThisNode a) { 1037 return a.node.index!N._index; 1038 } 1039 static size_t _RemoveUn2(ThisNode* a) { 1040 return a.index!N._index; 1041 } 1042 /** 1043 removes elements of r from this container. 1044 Complexity: $(BIGOH n $(SUB r) * d(n)), $(BR) $(BIGOH n) 1045 for this index 1046 */ 1047 RARange remove(Range)(Range r) 1048 if(is(Range == RARange) || 1049 is(ElementType!Range == Position!ThisNode)) { 1050 static if(is(Range == RARange)) { 1051 // definitely contiguous 1052 size_t _length = node_count; 1053 size_t s = r.front_node.index!N._index; 1054 size_t e = r.back_node.index!N._index+1; 1055 size_t newlen = _length - (e-s); 1056 while(!r.empty){ 1057 ThisNode* node = r.front_node; 1058 _RemoveAllBut!N(node); 1059 dealloc(node); 1060 r.popFront(); 1061 } 1062 copy(ra[e .. _length], ra[s .. newlen]); 1063 foreach(k, rx; ra[s .. newlen]) { 1064 rx.index!N._index = s+k; 1065 } 1066 fill(ra[newlen .. _length], cast(ThisNode*) null); 1067 _length -= e-s; 1068 }else { 1069 // maybe not contiguous 1070 // need to be efficient with moving chunks 1071 auto arr = allocatedArray!Allocator(r); 1072 sort!_RemovePred(arr); 1073 if(arr.length == 1) _RemoveAll(arr[0].node); 1074 else{ 1075 auto ixs = map!_RemoveUn(arr); 1076 auto ab = zip(ixs, chain(drop(ixs, 1), [node_count])); 1077 size_t p = ixs.front; 1078 foreach(a,b; ab) { 1079 auto pstart = p; 1080 p += b-a-1; 1081 _RemoveAllBut!N(ra[a]); 1082 dealloc(ra[a]); 1083 copy(ra[a+1 .. b], ra[pstart .. p]); 1084 foreach(k, n; arr[pstart .. p]) 1085 n.node.index!N._index = pstart+k; 1086 } 1087 fill(ra[p .. $], cast(ThisNode*) null); 1088 } 1089 foreach(p; arr) p.obliterated = true; 1090 } 1091 return RARange(this, 0, 0); 1092 } 1093 1094 void _NodeReplace(ThisNode* old, ThisNode* newnode) { 1095 move(newnode, ra[old.index!N._index]); 1096 newnode.index!N._index = old.index!N._index; 1097 } 1098 1099 void _Check(){ 1100 foreach(i, n; ra[0 .. node_count]) { 1101 assert(n.index!N._index == i); 1102 } 1103 } 1104 1105 string toString0(){ 1106 string r = "["; 1107 auto rng = opSlice(); 1108 while(!rng.empty){ 1109 r ~= format("%s", rng.front); 1110 rng.popFront(); 1111 r ~= rng.empty ? "]" : ", "; 1112 } 1113 return r; 1114 } 1115 1116 private RARange fromNode(ThisNode* n){ 1117 size_t ix = n.index!N._index; 1118 return RARange(this, ix, this.node_count); 1119 } 1120 } 1121 } 1122 } 1123 1124 // RBTree node impl. taken from std.container - that's Steven Schveighoffer's 1125 // code - and modified to suit. 1126 1127 /** 1128 * Enumeration determining what color the node is. Null nodes are assumed 1129 * to be black. 1130 */ 1131 enum Color : byte 1132 { 1133 Red, 1134 Black 1135 } 1136 1137 /// ordered node implementation 1138 mixin template OrderedNodeMixin(size_t N){ 1139 alias typeof(this)* Node; 1140 Node _left; 1141 Node _right; 1142 1143 version(PtrHackery){ 1144 size_t _p; 1145 1146 @property void _parent(Node p){ 1147 Color c = color; 1148 _p = cast(size_t) p; 1149 color = c; 1150 } 1151 @property Node _parent(){ 1152 size_t r = _p; 1153 btr(&r,0); 1154 return cast(Node) r; 1155 } 1156 1157 @property void color(Color c){ 1158 if(c) bts(&_p,0); 1159 else btr(&_p,0); 1160 } 1161 @property Color color(){ 1162 return cast(Color) bt(&_p,0); 1163 } 1164 }else{ 1165 Node _parent; 1166 /** 1167 * The color of the node. 1168 */ 1169 Color color; 1170 } 1171 1172 /** 1173 * Get the left child 1174 */ 1175 @property inout(typeof(this))* left() inout 1176 { 1177 return _left; 1178 } 1179 1180 /** 1181 * Get the right child 1182 */ 1183 @property inout(typeof(this))* right() inout 1184 { 1185 return _right; 1186 } 1187 1188 /** 1189 * Get the parent 1190 */ 1191 @property Node parent() 1192 { 1193 return _parent; 1194 } 1195 1196 /** 1197 * Set the left child. Also updates the new child's parent node. This 1198 * does not update the previous child. 1199 * 1200 * Returns newNode 1201 */ 1202 @property Node left(Node newNode) 1203 { 1204 _left = newNode; 1205 if(newNode !is null) 1206 newNode.index!N._parent = &this; 1207 return newNode; 1208 } 1209 1210 /** 1211 * Set the right child. Also updates the new child's parent node. This 1212 * does not update the previous child. 1213 * 1214 * Returns newNode 1215 */ 1216 @property Node right(Node newNode) 1217 { 1218 _right = newNode; 1219 if(newNode !is null) 1220 newNode.index!N._parent = &this; 1221 return newNode; 1222 } 1223 1224 // assume _left is not null 1225 // 1226 // performs rotate-right operation, where this is T, _right is R, _left is 1227 // L, _parent is P: 1228 // 1229 // P P 1230 // | -> | 1231 // T L 1232 // / \ / \ 1233 // L R a T 1234 // / \ / \ 1235 // a b b R 1236 // 1237 /** 1238 * Rotate right. This performs the following operations: 1239 * - The left child becomes the parent of this node. 1240 * - This node becomes the new parent's right child. 1241 * - The old right child of the new parent becomes the left child of this 1242 * node. 1243 */ 1244 Node rotateR() 1245 in 1246 { 1247 assert(_left !is null); 1248 } 1249 body 1250 { 1251 // sets _left._parent also 1252 if(isLeftNode) 1253 parent.index!N.left = _left; 1254 else 1255 parent.index!N.right = _left; 1256 Node tmp = _left.index!N._right; 1257 1258 // sets _parent also 1259 _left.index!N.right = &this; 1260 1261 // sets tmp._parent also 1262 left = tmp; 1263 1264 return &this; 1265 } 1266 1267 // assumes _right is non null 1268 // 1269 // performs rotate-left operation, where this is T, _right is R, _left is 1270 // L, _parent is P: 1271 // 1272 // P P 1273 // | -> | 1274 // T R 1275 // / \ / \ 1276 // L R T b 1277 // / \ / \ 1278 // a b L a 1279 // 1280 /** 1281 * Rotate left. This performs the following operations: 1282 * - The right child becomes the parent of this node. 1283 * - This node becomes the new parent's left child. 1284 * - The old left child of the new parent becomes the right child of this 1285 * node. 1286 */ 1287 Node rotateL() 1288 in 1289 { 1290 assert(_right !is null); 1291 } 1292 body 1293 { 1294 // sets _right._parent also 1295 if(isLeftNode) 1296 parent.index!N.left = _right; 1297 else 1298 parent.index!N.right = _right; 1299 Node tmp = _right.index!N._left; 1300 1301 // sets _parent also 1302 _right.index!N.left = &this; 1303 1304 // sets tmp._parent also 1305 right = tmp; 1306 return &this; 1307 } 1308 1309 1310 /** 1311 * Returns true if this node is a left child. 1312 * 1313 * Note that this should always return a value because the root has a 1314 * parent which is the marker node. 1315 */ 1316 @property bool isLeftNode() const 1317 in 1318 { 1319 assert(_parent !is null); 1320 } 1321 body 1322 { 1323 return _parent.index!N._left is &this; 1324 } 1325 1326 /** 1327 * Set the color of the node after it is inserted. This performs an 1328 * update to the whole tree, possibly rotating nodes to keep the Red-Black 1329 * properties correct. This is an O(lg(n)) operation, where n is the 1330 * number of nodes in the tree. 1331 * 1332 * end is the marker node, which is the parent of the topmost valid node. 1333 */ 1334 void setColor(Node end) 1335 { 1336 // test against the marker node 1337 if(_parent !is end) 1338 { 1339 if(_parent.index!N.color == Color.Red) 1340 { 1341 Node cur = &this; 1342 while(true) 1343 { 1344 // because root is always black, _parent._parent always exists 1345 if(cur.index!N._parent.index!N.isLeftNode) 1346 { 1347 // parent is left node, y is 'uncle', could be null 1348 Node y = cur.index!N._parent.index!N._parent.index!N._right; 1349 if(y !is null && y.index!N.color == Color.Red) 1350 { 1351 cur.index!N._parent.index!N.color = Color.Black; 1352 y.index!N.color = Color.Black; 1353 cur = cur.index!N._parent.index!N._parent; 1354 if(cur.index!N._parent is end) 1355 { 1356 // root node 1357 cur.index!N.color = Color.Black; 1358 break; 1359 } 1360 else 1361 { 1362 // not root node 1363 cur.index!N.color = Color.Red; 1364 if(cur.index!N._parent.index!N.color == Color.Black) 1365 // satisfied, exit the loop 1366 break; 1367 } 1368 } 1369 else 1370 { 1371 if(!cur.index!N.isLeftNode) 1372 cur = cur.index!N._parent.index!N.rotateL(); 1373 cur.index!N._parent.index!N.color = Color.Black; 1374 cur = cur.index!N._parent.index!N._parent.index!N.rotateR(); 1375 cur.index!N.color = Color.Red; 1376 // tree should be satisfied now 1377 break; 1378 } 1379 } 1380 else 1381 { 1382 // parent is right node, y is 'uncle' 1383 Node y = cur.index!N._parent.index!N._parent.index!N._left; 1384 if(y !is null && y.index!N.color == Color.Red) 1385 { 1386 cur.index!N._parent.index!N.color = Color.Black; 1387 y.index!N.color = Color.Black; 1388 cur = cur.index!N._parent.index!N._parent; 1389 if(cur.index!N._parent is end) 1390 { 1391 // root node 1392 cur.index!N.color = Color.Black; 1393 break; 1394 } 1395 else 1396 { 1397 // not root node 1398 cur.index!N.color = Color.Red; 1399 if(cur.index!N._parent.index!N.color == Color.Black) 1400 // satisfied, exit the loop 1401 break; 1402 } 1403 } 1404 else 1405 { 1406 if(cur.index!N.isLeftNode) 1407 cur = cur.index!N._parent.index!N.rotateR(); 1408 cur.index!N._parent.index!N.color = Color.Black; 1409 cur = cur.index!N._parent.index!N._parent.index!N.rotateL(); 1410 cur.index!N.color = Color.Red; 1411 // tree should be satisfied now 1412 break; 1413 } 1414 } 1415 } 1416 1417 } 1418 } 1419 else 1420 { 1421 // 1422 // this is the root node, color it black 1423 // 1424 color = Color.Black; 1425 } 1426 } 1427 1428 /** 1429 * Remove this node from the tree. The 'end' node is used as the marker 1430 * which is root's parent. Note that this cannot be null! 1431 * 1432 * Returns the next highest valued node in the tree after this one, or end 1433 * if this was the highest-valued node. 1434 */ 1435 Node remove(Node end) 1436 { 1437 // 1438 // remove this node from the tree, fixing the color if necessary. 1439 // 1440 Node x; 1441 Node ret; 1442 if(_left is null || _right is null) 1443 { 1444 ret = next; 1445 } 1446 else 1447 { 1448 // 1449 // normally, we can just swap this node's and y's value, but 1450 // because an iterator could be pointing to y and we don't want to 1451 // disturb it, we swap this node and y's structure instead. This 1452 // can also be a benefit if the value of the tree is a large 1453 // struct, which takes a long time to copy. 1454 // 1455 Node yp, yl, yr; 1456 Node y = next; 1457 yp = y.index!N._parent; 1458 yl = y.index!N._left; 1459 yr = y.index!N._right; 1460 auto yc = y.index!N.color; 1461 auto isyleft = y.index!N.isLeftNode; 1462 1463 // 1464 // replace y's structure with structure of this node. 1465 // 1466 if(isLeftNode) 1467 _parent.index!N.left = y; 1468 else 1469 _parent.index!N.right = y; 1470 // 1471 // need special case so y doesn't point back to itself 1472 // 1473 y.index!N.left = _left; 1474 if(_right is y) 1475 y.index!N.right = &this; 1476 else 1477 y.index!N.right = _right; 1478 y.index!N.color = color; 1479 1480 // 1481 // replace this node's structure with structure of y. 1482 // 1483 left = yl; 1484 right = yr; 1485 if(_parent !is y) 1486 { 1487 if(isyleft) 1488 yp.index!N.left = &this; 1489 else 1490 yp.index!N.right = &this; 1491 } 1492 color = yc; 1493 1494 // 1495 // set return value 1496 // 1497 ret = y; 1498 } 1499 1500 // if this has less than 2 children, remove it 1501 if(_left !is null) 1502 x = _left; 1503 else 1504 x = _right; 1505 1506 // remove this from the tree at the end of the procedure 1507 bool removeThis = false; 1508 if(x is null) 1509 { 1510 // pretend this is a null node, remove this on finishing 1511 x = &this; 1512 removeThis = true; 1513 } 1514 else if(isLeftNode) 1515 _parent.index!N.left = x; 1516 else 1517 _parent.index!N.right = x; 1518 1519 // if the color of this is black, then it needs to be fixed 1520 if(color == color.Black) 1521 { 1522 // need to recolor the tree. 1523 while(x.index!N._parent !is end && x.index!N.color == Color.Black) 1524 { 1525 if(x.index!N.isLeftNode) 1526 { 1527 // left node 1528 Node w = x.index!N._parent.index!N._right; 1529 if(w.index!N.color == Color.Red) 1530 { 1531 w.index!N.color = Color.Black; 1532 x.index!N._parent.index!N.color = Color.Red; 1533 x.index!N._parent.index!N.rotateL(); 1534 w = x.index!N._parent.index!N._right; 1535 } 1536 Node wl = w.index!N.left; 1537 Node wr = w.index!N.right; 1538 if((wl is null || wl.index!N.color == Color.Black) && 1539 (wr is null || wr.index!N.color == Color.Black)) 1540 { 1541 w.index!N.color = Color.Red; 1542 x = x.index!N._parent; 1543 } 1544 else 1545 { 1546 if(wr is null || wr.index!N.color == Color.Black) 1547 { 1548 // wl cannot be null here 1549 wl.index!N.color = Color.Black; 1550 w.index!N.color = Color.Red; 1551 w.index!N.rotateR(); 1552 w = x.index!N._parent.index!N._right; 1553 } 1554 1555 w.index!N.color = x.index!N._parent.index!N.color; 1556 x.index!N._parent.index!N.color = Color.Black; 1557 w.index!N._right.index!N.color = Color.Black; 1558 x.index!N._parent.index!N.rotateL(); 1559 x = end.index!N.left; // x = root 1560 } 1561 } 1562 else 1563 { 1564 // right node 1565 Node w = x.index!N._parent.index!N._left; 1566 if(w.index!N.color == Color.Red) 1567 { 1568 w.index!N.color = Color.Black; 1569 x.index!N._parent.index!N.color = Color.Red; 1570 x.index!N._parent.index!N.rotateR(); 1571 w = x.index!N._parent.index!N._left; 1572 } 1573 Node wl = w.index!N.left; 1574 Node wr = w.index!N.right; 1575 if((wl is null || wl.index!N.color == Color.Black) && 1576 (wr is null || wr.index!N.color == Color.Black)) 1577 { 1578 w.index!N.color = Color.Red; 1579 x = x.index!N._parent; 1580 } 1581 else 1582 { 1583 if(wl is null || wl.index!N.color == Color.Black) 1584 { 1585 // wr cannot be null here 1586 wr.index!N.color = Color.Black; 1587 w.index!N.color = Color.Red; 1588 w.index!N.rotateL(); 1589 w = x.index!N._parent.index!N._left; 1590 } 1591 1592 w.index!N.color = x.index!N._parent.index!N.color; 1593 x.index!N._parent.index!N.color = Color.Black; 1594 w.index!N._left.index!N.color = Color.Black; 1595 x.index!N._parent.index!N.rotateR(); 1596 x = end.index!N.left; // x = root 1597 } 1598 } 1599 } 1600 x.index!N.color = Color.Black; 1601 } 1602 1603 if(removeThis) 1604 { 1605 // 1606 // clear this node out of the tree 1607 // 1608 if(isLeftNode) 1609 _parent.index!N.left = null; 1610 else 1611 _parent.index!N.right = null; 1612 } 1613 1614 return ret; 1615 } 1616 1617 /** 1618 * Return the leftmost descendant of this node. 1619 */ 1620 @property leftmost() inout 1621 { 1622 typeof(this)* result = &this; 1623 while(result.index!N._left !is null) 1624 result = result.index!N._left; 1625 return result; 1626 } 1627 1628 /** 1629 * Return the rightmost descendant of this node 1630 */ 1631 @property rightmost() inout 1632 { 1633 auto result = &this; 1634 while(result.index!N._right !is null) 1635 result = result.index!N._right; 1636 return result; 1637 } 1638 1639 @property parentmost() inout 1640 { 1641 auto result = &this; 1642 while(result.index!N._parent !is null) 1643 result = result.index!N._parent; 1644 return result; 1645 } 1646 1647 /** 1648 * Returns the next valued node in the tree. 1649 * 1650 * You should never call this on the marker node, as it is assumed that 1651 * there is a valid next node. 1652 */ 1653 @property inout(typeof(this))* next() inout 1654 in{ 1655 debug assert( &this !is this.index!N.parentmost.index!N.rightmost, 1656 "calling prev on _end.rightmost"); 1657 }body{ 1658 auto n = &this; 1659 if(n.index!N.right is null) 1660 { 1661 while(!n.index!N.isLeftNode) 1662 n = n.index!N._parent; 1663 return n.index!N._parent; 1664 } 1665 else 1666 return n.index!N.right.index!N.leftmost; 1667 } 1668 1669 /** 1670 * Returns the previous valued node in the tree. 1671 * 1672 * You should never call this on the leftmost node of the tree as it is 1673 * assumed that there is a valid previous node. 1674 */ 1675 @property inout(typeof(this))* prev() inout 1676 in{ 1677 debug assert( &this !is this.index!N.parentmost.index!N.leftmost, 1678 "calling prev on _end.leftmost"); 1679 }body{ 1680 auto n = &this; 1681 if(n.index!N.left is null) 1682 { 1683 while(n.index!N.isLeftNode) 1684 n = n.index!N._parent; 1685 n = n.index!N._parent; 1686 return n; 1687 } 1688 else 1689 return n.index!N.left.index!N.rightmost; 1690 } 1691 1692 } 1693 1694 /// ordered index implementation 1695 mixin template OrderedIndex(size_t N, bool allowDuplicates, alias KeyFromValue, alias Compare, ThisContainer) { 1696 // this index does do memory allocation 1697 // 1) in removeKey, moves stuff to allocated array 1698 // 2) somewhere does new Exception(...) 1699 alias ThisNode* Node; 1700 alias binaryFun!Compare _less; 1701 alias unaryFun!KeyFromValue key; 1702 alias typeof(key(Value.init)) KeyType; 1703 1704 /** 1705 * The range type for this index, which embodies a bidirectional range 1706 */ 1707 struct OrderedRangeT(bool is_const) 1708 { 1709 static if(is_const) { 1710 alias const(ThisNode) Node; 1711 alias const(ThisContainer) Container; 1712 }else { 1713 alias ThisContainer Container; 1714 alias ThisNode Node; 1715 } 1716 Container c; 1717 private Node* _begin; 1718 private Node* _end; 1719 1720 this(Container _c, Node* b, Node* e) { 1721 c = _c; 1722 _begin = b; 1723 _end = e; 1724 } 1725 1726 /** 1727 * Returns $(D true) if the range is _empty 1728 */ 1729 @property bool empty() const 1730 { 1731 return _begin is _end; 1732 } 1733 1734 @property front_node() { 1735 return _begin; 1736 }; 1737 1738 @property back_node() { 1739 return _end.index!N.prev; 1740 } 1741 /** 1742 * Returns the first element in the range 1743 */ 1744 @property front() 1745 { 1746 return front_node.value; 1747 } 1748 1749 /** 1750 * Returns the last element in the range 1751 */ 1752 @property back() 1753 { 1754 return back_node.value; 1755 } 1756 1757 /** 1758 * pop the front element from the range 1759 * 1760 * complexity: amortized $(BIGOH 1) 1761 */ 1762 void popFront() 1763 { 1764 _begin = _begin.index!N.next; 1765 } 1766 1767 /** 1768 * pop the back element from the range 1769 * 1770 * complexity: amortized $(BIGOH 1) 1771 */ 1772 void popBack() 1773 { 1774 _end = _end.index!N.prev; 1775 } 1776 1777 /** 1778 * Trivial _save implementation, needed for $(D isForwardRange). 1779 */ 1780 @property save() 1781 { 1782 return this; 1783 } 1784 } 1785 1786 alias OrderedRangeT!true ConstOrderedRange; 1787 alias OrderedRangeT!false OrderedRange; 1788 1789 template IsMyRange(T) { 1790 enum bool IsMyRange = 1791 is(T == OrderedRange) || 1792 is(T == ConstOrderedRange); 1793 } 1794 1795 auto _add(Node n) 1796 { 1797 bool added = true; 1798 1799 if(!_end.index!N.left) 1800 { 1801 _end.index!N.left = n; 1802 } 1803 else 1804 { 1805 Node newParent = _end.index!N.left; 1806 Node nxt = void; 1807 auto k = key(n.value); 1808 while(true) 1809 { 1810 auto pk = key(newParent.value); 1811 if(_less(k, pk)) 1812 { 1813 nxt = newParent.index!N.left; 1814 if(nxt is null) 1815 { 1816 // 1817 // add to right of new parent 1818 // 1819 newParent.index!N.left = n; 1820 break; 1821 } 1822 } 1823 else 1824 { 1825 static if(!allowDuplicates) 1826 { 1827 if(!_less(pk, k)) 1828 { 1829 added = false; 1830 break; 1831 } 1832 } 1833 nxt = newParent.index!N.right; 1834 if(nxt is null) 1835 { 1836 // 1837 // add to right of new parent 1838 // 1839 newParent.index!N.right = n; 1840 break; 1841 } 1842 } 1843 newParent = nxt; 1844 } 1845 } 1846 1847 static if(allowDuplicates) 1848 { 1849 n.index!N.setColor(_end); 1850 version(RBDoChecks) _Check(); 1851 return added; 1852 } 1853 else 1854 { 1855 if(added) 1856 n.index!N.setColor(_end); 1857 version(RBDoChecks) _Check(); 1858 return added; 1859 } 1860 } 1861 1862 /** 1863 * Element type for the tree 1864 */ 1865 alias ValueView Elem; 1866 1867 Node _end; 1868 1869 static if(!allowDuplicates){ 1870 bool _DenyInsertion(Node n, out Node cursor){ 1871 return _find2(key(n.value), cursor); 1872 } 1873 } 1874 1875 static if(allowDuplicates) alias _add _Insert; 1876 else void _Insert(Node n, Node cursor){ 1877 if(cursor !is null){ 1878 if (_less(key(n.value), key(cursor.value))){ 1879 cursor.index!N.left = n; 1880 }else{ 1881 cursor.index!N.right = n; 1882 } 1883 n.index!N.setColor(_end); 1884 }else{ 1885 _add(n); 1886 } 1887 1888 } 1889 1890 1891 // if k exists in this index, returns par such that eq(key(par.value),k), 1892 // and returns true 1893 // if k !exists in this index, returns par such that k value belongs either 1894 // as par.left or par.right. remember to setColor! returns false. 1895 private bool _find2(KeyType k, out inout(ThisNode)* par) inout 1896 { 1897 auto cur = _end.index!N.left; 1898 par = null; 1899 while(cur) 1900 { 1901 // BAD!!! TODO: figure out unaryFun & inout 1902 auto ck = key(cast() cur.value); 1903 par = cur; 1904 if(_less(ck, k)){ 1905 cur = cur.index!N.right; 1906 }else if(_less(k, ck)){ 1907 cur = cur.index!N.left; 1908 }else{ 1909 return true; 1910 } 1911 } 1912 return false; 1913 } 1914 1915 private bool _find2At(KeyType k, Node cur, out Node par) 1916 { 1917 par = null; 1918 while(cur) 1919 { 1920 auto ck = key(cur.value); 1921 par = cur; 1922 if(_less(ck, k)){ 1923 cur = cur.index!N.right; 1924 }else if(_less(k, ck)){ 1925 cur = cur.index!N.left; 1926 }else{ 1927 return true; 1928 } 1929 } 1930 return false; 1931 } 1932 1933 /** 1934 * Check if any elements exist in the container. Returns $(D true) if at least 1935 * one element exists. 1936 * Complexity: $(BIGOH 1) 1937 */ 1938 @property bool empty() const 1939 { 1940 return node_count == 0; 1941 } 1942 1943 /++ 1944 Returns the number of elements in the container. 1945 1946 Complexity: $(BIGOH 1). 1947 +/ 1948 @property size_t length() const 1949 { 1950 return node_count; 1951 } 1952 1953 /** 1954 * Fetch a range that spans all the elements in the container. 1955 * 1956 * Complexity: $(BIGOH log(n)) 1957 */ 1958 OrderedRange opSlice() 1959 { 1960 return OrderedRange(this,_end.index!N.leftmost, _end); 1961 } 1962 1963 ConstOrderedRange opSlice() const{ 1964 return ConstOrderedRange(this,_end.index!N.leftmost, _end); 1965 } 1966 1967 /** 1968 * The front element in the container 1969 * 1970 * Complexity: $(BIGOH log(n)) 1971 */ 1972 @property front() inout 1973 { 1974 return _end.index!N.leftmost.value; 1975 } 1976 1977 /** 1978 * The last element in the container 1979 * 1980 * Complexity: $(BIGOH log(n)) 1981 */ 1982 @property back() inout 1983 { 1984 return _end.index!N.prev.value; 1985 } 1986 1987 /++ 1988 $(D in) operator. Check to see if the given element exists in the 1989 container. 1990 1991 Complexity: $(BIGOH log(n)) 1992 +/ 1993 bool opBinaryRight(string op)(Elem e) const 1994 if (op == "in") 1995 { 1996 const(ThisNode)* p; 1997 return _find2(key(e),p); 1998 } 1999 /++ 2000 $(D in) operator. Check to see if the given element exists in the 2001 container. 2002 2003 Complexity: $(BIGOH log(n)) 2004 +/ 2005 static if(!isImplicitlyConvertible!(KeyType, Elem)){ 2006 bool opBinaryRight(string op,K)(K k) if (op == "in" && 2007 isImplicitlyConvertible!(K, KeyType)) 2008 { 2009 Node p; 2010 return _find2(k,p); 2011 } 2012 } 2013 2014 void _ClearIndex() { 2015 _end.index!N._left = null; 2016 } 2017 2018 /** 2019 * Removes all elements from the container. 2020 * 2021 * Complexity: ?? 2022 */ 2023 void clear() 2024 { 2025 _Clear(); 2026 } 2027 2028 static if(!allowDuplicates){ 2029 /** 2030 Available for Unique variant. 2031 Complexity: 2032 $(BIGOH log(n)) 2033 */ 2034 ValueView opIndex(KeyType k) inout{ 2035 inout(ThisNode)* n; 2036 enforce(_find2(k,n)); 2037 return cast(ValueView) n.value; 2038 } 2039 } 2040 2041 /** 2042 Perform mod on r.front and performs any necessary fixups to container's 2043 indices. If the result of mod violates any index' invariant, r.front is 2044 removed from the container. 2045 Preconditions: !r.empty, $(BR) 2046 mod is a callable of the form void mod(ref Value) 2047 Complexity: $(BIGOH m(n)), $(BR) $(BIGOH log(n)) for this index 2048 */ 2049 2050 void modify(SomeRange, Modifier)(SomeRange r, Modifier mod) 2051 if(is(SomeRange == OrderedRange) || 2052 is(ElementType!SomeRange == Position!ThisNode)) { 2053 while(!r.empty) { 2054 static if(is(SomeRange == OrderedRange)) { 2055 Node node = r.front_node; 2056 }else { 2057 Node node = r.front.node; 2058 } 2059 r.popFront(); 2060 _Modify(node, mod); 2061 } 2062 } 2063 /** 2064 Replaces r.front with value 2065 Returns: whether replacement succeeded 2066 Complexity: ?? 2067 */ 2068 bool replace(Position!ThisNode r, ValueView value) { 2069 return _Replace(r.node, cast(Value) value); 2070 } 2071 2072 KeyType _NodePosition(ThisNode* node){ 2073 return key(node.value); 2074 } 2075 2076 // cursor = null -> no fixup needed 2077 // cursor != null -> fixup needed 2078 bool _PositionFixable(ThisNode* node, KeyType oldPosition, 2079 out ThisNode* cursor){ 2080 cursor = null; 2081 // case 1: key hasn't changed 2082 auto newPosition = key(node.value); 2083 if(!_less(newPosition, oldPosition) && 2084 !_less(oldPosition, newPosition)) return true; 2085 Node next = _end.index!N.rightmost is node ? null : node.index!N.next; 2086 auto prev = _end.index!N.leftmost is node ? null : node.index!N.prev; 2087 2088 // case 2: key has changed, but relative position hasn't 2089 bool outOfBounds = (next && next != _end && 2090 !_less(newPosition, key(next.value))) || 2091 prev && !_less(key(prev.value), newPosition); 2092 if (!outOfBounds) return true; 2093 2094 // case 3: key has changed, position has changed 2095 static if(allowDuplicates){ 2096 cursor = node; 2097 return true; 2098 }else{ 2099 bool found = _find2(newPosition, cursor); 2100 if(cursor is node){ 2101 // node's old value is in path to node's new value 2102 if(_less(newPosition, oldPosition)){ 2103 if(cursor.index!N._left){ 2104 found = _find2At(newPosition, 2105 cursor.index!N._left, cursor); 2106 }else{ 2107 found = false; 2108 } 2109 }else{ 2110 if(cursor.index!N._right){ 2111 found = _find2At(newPosition, 2112 cursor.index!N._right, cursor); 2113 }else{ 2114 found = false; 2115 } 2116 } 2117 } 2118 return !found; 2119 } 2120 } 2121 2122 void _FixPosition(ThisNode* node, KeyType oldPosition, ThisNode* cursor) 2123 out{ 2124 version(RBDoChecks) _Check(); 2125 }body{ 2126 static if(allowDuplicates){ 2127 if(cursor){ 2128 _Remove(node); 2129 node.index!N._parent = 2130 node.index!N._left = 2131 node.index!N._right = null; 2132 node.index!N.color = Color.Red; 2133 _Insert(node); 2134 } 2135 }else{ 2136 if(!cursor) return; 2137 _Remove(node); 2138 node.index!N._parent = 2139 node.index!N._left = 2140 node.index!N._right = null; 2141 node.index!N.color = Color.Red; 2142 _Insert(node, cursor); 2143 } 2144 } 2145 2146 // n's value has changed and its position might be invalid. 2147 // remove n if it violates an invariant. 2148 // returns: true iff n's validity has been restored 2149 bool _NotifyChange(Node node) 2150 out(r){ 2151 _Check(); 2152 }body{ 2153 auto newPosition = key(node.value); 2154 Node next = _end.index!N.rightmost is node ? null : node.index!N.next; 2155 Node prev = _end.index!N.leftmost is node ? null : node.index!N.prev; 2156 2157 // case 1: key has changed, but relative position hasn't 2158 bool outOfBounds = (next && next != _end && 2159 !_less(newPosition, key(next.value))) || 2160 prev && !_less(key(prev.value), newPosition); 2161 if (!outOfBounds) return true; 2162 2163 // case 2: key has changed, position has changed 2164 static if(allowDuplicates){ 2165 _Remove(node); 2166 node.index!N._parent = 2167 node.index!N._left = 2168 node.index!N._right = null; 2169 node.index!N.color = Color.Red; 2170 _Insert(node); 2171 return true; 2172 }else{ 2173 Node cursor; 2174 _Remove(node); 2175 bool found = _find2(newPosition, cursor); 2176 if(found){ 2177 _RemoveAllBut!N(node); 2178 return false; 2179 } 2180 node.index!N._parent = 2181 node.index!N._left = 2182 node.index!N._right = null; 2183 node.index!N.color = Color.Red; 2184 _Insert(node, cursor); 2185 return true; 2186 } 2187 } 2188 2189 /** 2190 * Insert a single element in the container. Note that this does not 2191 * invalidate any ranges currently iterating the container. 2192 * 2193 * Complexity: $(BIGOH i(n)); $(BR) $(BIGOH log(n)) for this index 2194 */ 2195 size_t insert(Stuff)(Stuff stuff) 2196 if (isImplicitlyConvertible!(Stuff, Elem)) 2197 out(r){ 2198 version(RBDoChecks) _Check(); 2199 }body{ 2200 static if(!allowDuplicates){ 2201 Node p; 2202 if(_find2(key(stuff),p)){ 2203 return 0; 2204 } 2205 } 2206 Node n = _InsertAllBut!N(stuff); 2207 if(!n) return 0; 2208 static if(!allowDuplicates){ 2209 _Insert(n,p); 2210 }else _add(n); 2211 return 1; 2212 } 2213 2214 /** 2215 * Insert a range of elements in the container. Note that this does not 2216 * invalidate any ranges currently iterating the container. 2217 * 2218 * Complexity: $(BIGOH n $(SUB stuff) * i(n)); $(BR) $(BIGOH n $(SUB 2219 stuff) * log(n)) for this index 2220 */ 2221 size_t insert(Stuff)(Stuff stuff) 2222 if(isInputRange!Stuff && 2223 isImplicitlyConvertible!(ElementType!Stuff, Elem)) 2224 out(r){ 2225 version(RBDoChecks) _Check(); 2226 }body{ 2227 size_t result = 0; 2228 foreach(e; stuff) 2229 { 2230 result += insert(e); 2231 } 2232 return result; 2233 } 2234 2235 Node _Remove(Node n) 2236 out(r){ 2237 version(RBDoChecks) _Check(); 2238 }body{ 2239 return n.index!N.remove(_end); 2240 } 2241 2242 /** 2243 * Remove an element from the container and return its value. 2244 * 2245 * Complexity: $(BIGOH d(n)); $(BR) $(BIGOH log(n)) for this index 2246 */ 2247 Elem removeAny() { 2248 auto n = _end.index!N.leftmost; 2249 auto result = n.value; 2250 _RemoveAll(n); 2251 return result; 2252 } 2253 2254 /** 2255 * Remove the front element from the container. 2256 * 2257 * Complexity: $(BIGOH d(n)); $(BR) $(BIGOH log(n)) for this index 2258 */ 2259 void removeFront() { 2260 auto n = _end.index!N.leftmost; 2261 _RemoveAll(n); 2262 } 2263 2264 /** 2265 * Remove the back element from the container. 2266 * 2267 * Complexity: $(BIGOH d(n)); $(BR) $(BIGOH log(n)) for this index 2268 */ 2269 void removeBack() { 2270 auto n = _end.index!N.prev; 2271 _RemoveAll(n); 2272 } 2273 2274 /++ 2275 Removes the given range from the container. 2276 2277 Returns: A range containing all of the elements that were after the 2278 given range. 2279 2280 Complexity:$(BIGOH n $(SUB r) * d(n)); $(BR) $(BIGOH n $(SUB r) * 2281 log(n)) for this index 2282 +/ 2283 OrderedRange remove(R)(R r) 2284 if(is(R == OrderedRange) || 2285 is(ElementType!R == Position!ThisNode)) 2286 out(r2){ 2287 version(RBDoChecks) _Check(); 2288 }body{ 2289 while(!r.empty) { 2290 static if(is(R == OrderedRange)) { 2291 auto node = r.front_node; 2292 }else{ 2293 auto node = r.front.node; 2294 r.front.obliterated = true; 2295 } 2296 r.popFront(); 2297 _RemoveAll!N(node); 2298 } 2299 return OrderedRange(this, _end, _end); 2300 } 2301 2302 /++ 2303 Removes elements from the container that are equal to the given values 2304 according to the less comparator. One element is removed for each value 2305 given which is in the container. If $(D allowDuplicates) is true, 2306 duplicates are removed only if duplicate values are given. 2307 2308 Returns: The number of elements removed. 2309 2310 Complexity: $(BIGOH n $(SUB keys) d(n)); $(BR) $(BIGOH n 2311 $(SUB keys) log(n)) for this index 2312 2313 Examples: 2314 -------------------- 2315 // ya, this needs updating 2316 auto rbt = redBlackTree!true(0, 1, 1, 1, 4, 5, 7); 2317 rbt.removeKey(1, 4, 7); 2318 assert(std.algorithm.equal(rbt[], [0, 1, 1, 5])); 2319 rbt.removeKey(1, 1, 0); 2320 assert(std.algorithm.equal(rbt[], [5])); 2321 -------------------- 2322 +/ 2323 size_t removeKey(Keys...)(Keys keys) 2324 if(allSatisfy!(implicitlyConverts,Keys)) 2325 out(r){ 2326 version(RBDoChecks) _Check(); 2327 }body{ 2328 // stack allocation - is ok 2329 Unqual!KeyType[Keys.length] toRemove; 2330 foreach(i,k; keys) { 2331 Unqual!KeyType k2 = k; 2332 move(k2, toRemove[i]); 2333 } 2334 2335 return removeKey(cast(KeyType[])(toRemove[])); 2336 } 2337 2338 size_t removeKey(Key)(Key[] keys) 2339 if(isImplicitlyConvertible!(Key, KeyType)) 2340 out(r){ 2341 version(RBDoChecks) _Check(); 2342 }body{ 2343 size_t count = 0; 2344 2345 foreach(k; keys) 2346 { 2347 auto beg = _firstGreaterEqual(k); 2348 if(beg is _end || _less(k, key(beg.value))) 2349 // no values are equal 2350 continue; 2351 _RemoveAll(beg); 2352 count++; 2353 } 2354 2355 return count; 2356 } 2357 2358 private template implicitlyConverts(Key){ 2359 enum implicitlyConverts = isImplicitlyConvertible!(Key,KeyType); 2360 } 2361 2362 /++ Ditto +/ 2363 size_t removeKey(Stuff)(Stuff stuff) 2364 if(isInputRange!Stuff && 2365 isImplicitlyConvertible!(ElementType!Stuff, KeyType) && 2366 !isDynamicArray!Stuff) 2367 out(r){ 2368 version(RBDoChecks) _Check(); 2369 }body{ 2370 //We use array in case stuff is a Range from this RedBlackTree - either 2371 //directly or indirectly. 2372 2373 alias ElementType!Stuff E; 2374 2375 auto stuffy = allocatedArray!Allocator(stuff); 2376 auto res = removeKey(stuffy); 2377 Allocator.deallocate(stuffy.ptr); 2378 return res; 2379 } 2380 2381 // find the first node where the value is > k 2382 private inout(ThisNode)* _firstGreater(U)(U k) inout 2383 if(isImplicitlyConvertible!(U, KeyType)) 2384 { 2385 // can't use _find, because we cannot return null 2386 typeof(return) cur = _end.index!N.left; 2387 typeof(return) result = _end; 2388 while(cur) 2389 { 2390 // TODO: figure out unaryFun & inout 2391 if(_less(k, key(cast() cur.value))) 2392 { 2393 result = cur; 2394 cur = cur.index!N.left; 2395 } 2396 else 2397 cur = cur.index!N.right; 2398 } 2399 return result; 2400 } 2401 private inout(ThisNode)* 2402 _firstGreater(CompatibleLess, CompatibleKey) 2403 (CompatibleKey k) inout { 2404 // can't use _find, because we cannot return null 2405 typeof(return) cur = _end.index!N.left; 2406 typeof(return) result = _end; 2407 while(cur) 2408 { 2409 // TODO: figure out unaryFun & inout 2410 if(CompatibleLess.ck_less(k, key(cast() cur.value))) 2411 { 2412 result = cur; 2413 cur = cur.index!N.left; 2414 } 2415 else 2416 cur = cur.index!N.right; 2417 } 2418 return result; 2419 } 2420 2421 // find the first node where the value is >= k 2422 private inout(ThisNode)* _firstGreaterEqual(U)(U k) inout 2423 if(isImplicitlyConvertible!(U, KeyType)) 2424 { 2425 // can't use _find, because we cannot return null. 2426 typeof(return) cur = _end.index!N.left; 2427 typeof(return) result = _end; 2428 while(cur) 2429 { 2430 // TODO: figure out unaryFun & inout 2431 if(_less(key(cast() cur.value), k)) 2432 cur = cur.index!N.right; 2433 else 2434 { 2435 result = cur; 2436 cur = cur.index!N.left; 2437 } 2438 2439 } 2440 return result; 2441 } 2442 2443 // find the first node where the value is >= k 2444 private inout(ThisNode)* 2445 _firstGreaterEqual(CompatibleLess, CompatibleKey) 2446 (CompatibleKey k) inout { 2447 // can't use _find, because we cannot return null. 2448 typeof(return) cur = _end.index!N.left; 2449 typeof(return) result = _end; 2450 while(cur) 2451 { 2452 // TODO: figure out unaryFun & inout 2453 if(CompatibleLess.kc_less(key(cast() cur.value), k)) 2454 cur = cur.index!N.right; 2455 else 2456 { 2457 result = cur; 2458 cur = cur.index!N.left; 2459 } 2460 2461 } 2462 return result; 2463 } 2464 2465 /** 2466 * Get a range from the container with all elements that are > k according 2467 * to the less comparator 2468 * 2469 * Complexity: $(BIGOH log(n)) 2470 */ 2471 auto upperBound(U)(U k) 2472 if(isImplicitlyConvertible!(U, KeyType)) 2473 { 2474 return OrderedRange(this,_firstGreater(k), _end); 2475 } 2476 auto upperBound(U)(U k) const 2477 if(isImplicitlyConvertible!(U, KeyType)) 2478 { 2479 return ConstOrderedRange(this,_firstGreater(k), _end); 2480 } 2481 auto upperBound(CompatibleLess, CompatibleKey)(CompatibleKey k) 2482 { 2483 return OrderedRange(this,_firstGreater!CompatibleLess(k), _end); 2484 } 2485 auto upperBound(CompatibleLess, CompatibleKey)(CompatibleKey k) const 2486 { 2487 return ConstOrderedRange(this,_firstGreater!CompatibleLess(k), _end); 2488 } 2489 2490 /** 2491 * Get a range from the container with all elements that are < k according 2492 * to the less comparator 2493 * 2494 * Complexity: $(BIGOH log(n)) 2495 */ 2496 auto lowerBound(U)(U k) 2497 if(isImplicitlyConvertible!(U, KeyType)) 2498 { 2499 return OrderedRange(this,_end.index!N.leftmost, _firstGreaterEqual(k)); 2500 } 2501 auto lowerBound(U)(U k) const 2502 if(isImplicitlyConvertible!(U, KeyType)) 2503 { 2504 return ConstOrderedRange(this,_end.index!N.leftmost, _firstGreaterEqual(k)); 2505 } 2506 2507 auto lowerBound(CompatibleLess, CompatibleKey)(CompatibleKey k) 2508 { 2509 return OrderedRange(this,_end.index!N.leftmost, 2510 _firstGreaterEqual!CompatibleLess(k)); 2511 } 2512 auto lowerBound(CompatibleLess, CompatibleKey)(CompatibleKey k) const 2513 { 2514 return ConstOrderedRange(this,_end.index!N.leftmost, 2515 _firstGreaterEqual!CompatibleLess(k)); 2516 } 2517 2518 /** 2519 * Get a range from the container with all elements that are == k according 2520 * to the less comparator 2521 * 2522 * Complexity: $(BIGOH log(n)) 2523 */ 2524 // TODO: compact these back into one 2525 auto equalRange(U)(U k) 2526 if(isImplicitlyConvertible!(U, KeyType)) 2527 { 2528 auto beg = _firstGreaterEqual(k); 2529 if(beg is _end || _less(k, key(beg.value))) 2530 // no values are equal 2531 return OrderedRange(this,beg, beg); 2532 static if(allowDuplicates) 2533 { 2534 return OrderedRange(this,beg, _firstGreater(k)); 2535 } 2536 else 2537 { 2538 // no sense in doing a full search, no duplicates are allowed, 2539 // so we just get the next node. 2540 return OrderedRange(this,beg, beg.index!N.next); 2541 } 2542 } 2543 auto equalRange(U)(U k) const 2544 if(isImplicitlyConvertible!(U, KeyType)) 2545 { 2546 auto beg = _firstGreaterEqual(k); 2547 if(beg is _end || _less(k, key(beg.value))) 2548 // no values are equal 2549 return ConstOrderedRange(this,beg, beg); 2550 static if(allowDuplicates) 2551 { 2552 return ConstOrderedRange(this,beg, _firstGreater(k)); 2553 } 2554 else 2555 { 2556 // no sense in doing a full search, no duplicates are allowed, 2557 // so we just get the next node. 2558 return ConstOrderedRange(this,beg, beg.index!N.next); 2559 } 2560 } 2561 2562 // @@@BUG@@@ dmd issue 8440 prevents us frem naming this function equalRange 2563 OrderedRange cEqualRange(CompatibleLess, CompatibleKey)(CompatibleKey k) 2564 if(IsCompatibleLess!(CompatibleLess, KeyType, CompatibleKey)) 2565 { 2566 auto beg = _firstGreaterEqual!CompatibleLess(k); 2567 if(beg is _end || CompatibleLess.ck_less(k, key(beg.value))) 2568 // no values are equal 2569 return OrderedRange(this,beg, beg); 2570 return OrderedRange(this,beg, _firstGreater!CompatibleLess(k)); 2571 } 2572 ConstOrderedRange cEqualRange(CompatibleLess, CompatibleKey)(CompatibleKey k) const 2573 if(IsCompatibleLess!(CompatibleLess, KeyType, CompatibleKey)) 2574 { 2575 auto beg = _firstGreaterEqual!CompatibleLess(k); 2576 if(beg is _end || CompatibleLess.ck_less(k, key(beg.value))) 2577 // no values are equal 2578 return ConstOrderedRange(this,beg, beg); 2579 return ConstOrderedRange(this,beg, _firstGreater!CompatibleLess(k)); 2580 } 2581 2582 /++ 2583 Get a range of values bounded below by lower and above by upper, with 2584 inclusiveness defined by boundaries. 2585 Complexity: $(BIGOH log(n)) 2586 +/ 2587 auto bounds(string boundaries = "[]", U)(U lower, U upper) 2588 if(isImplicitlyConvertible!(U, KeyType)) 2589 in{ 2590 static if(boundaries == "[]") assert(!_less(upper,lower), 2591 format("nonsensical bounds %s%s,%s%s", 2592 boundaries[0], lower, upper, boundaries[1])); 2593 else assert(_less(lower,upper), 2594 format("nonsensical bounds %s%s,%s%s", 2595 boundaries[0], lower, upper, boundaries[1])); 2596 }body{ 2597 static if(boundaries[0] == '[') { 2598 auto n_lower = _firstGreaterEqual(lower); 2599 }else static if(boundaries[0] == '('){ 2600 auto n_lower = _firstGreater(lower); 2601 }else static assert(false); 2602 static if(boundaries[1] == ']') { 2603 auto n_upper = _firstGreater(upper); 2604 }else static if(boundaries[1] == ')'){ 2605 auto n_upper = _firstGreaterEqual(upper); 2606 }else static assert(false); 2607 return OrderedRange(this, n_lower, n_upper); 2608 } 2609 2610 auto cbounds(CompatibleLess,string boundaries = "[]", CompatibleKey) 2611 (CompatibleKey lower, CompatibleKey upper) 2612 if(IsCompatibleLess!(CompatibleLess, KeyType, CompatibleKey)) 2613 in{ 2614 static if(boundaries == "[]") 2615 assert(!CompatibleLess.cc_less(upper,lower), 2616 format("nonsensical bounds %s%s,%s%s", 2617 boundaries[0], lower, upper, boundaries[1])); 2618 else assert(CompatibleLess.cc_less(lower,upper), 2619 format("nonsensical bounds %s%s,%s%s", 2620 boundaries[0], lower, upper, boundaries[1])); 2621 }body{ 2622 static if(boundaries[0] == '[') { 2623 auto n_lower = _firstGreaterEqual!CompatibleLess(lower); 2624 }else static if(boundaries[0] == '('){ 2625 auto n_lower = _firstGreater!CompatibleLess(lower); 2626 }else static assert(false); 2627 static if(boundaries[1] == ']') { 2628 auto n_upper = _firstGreater!CompatibleLess(upper); 2629 }else static if(boundaries[1] == ')'){ 2630 auto n_upper = _firstGreaterEqual!CompatibleLess(upper); 2631 }else static assert(false); 2632 return OrderedRange(this, n_lower, n_upper); 2633 } 2634 2635 /* 2636 * Print the tree. This prints a sideways view of the tree in ASCII form, 2637 * with the number of indentations representing the level of the nodes. 2638 * It does not print values, only the tree structure and color of nodes. 2639 */ 2640 void printTree(Node n, int indent = 0) 2641 { 2642 if(n !is null) 2643 { 2644 printTree(n.index!N.right, indent + 2); 2645 for(int i = 0; i < indent; i++) 2646 write("."); 2647 write(n.index!N.color == Color.Black ? "B" : "R"); 2648 writefln("(%s)", n.value); 2649 printTree(n.index!N.left, indent + 2); 2650 } 2651 else 2652 { 2653 for(int i = 0; i < indent; i++) 2654 write("."); 2655 writeln("N"); 2656 } 2657 if(indent is 0) 2658 writeln(); 2659 } 2660 void _NodeReplace(ThisNode* old, ThisNode* newnode) { 2661 ThisNode* lch = old.index!N.left; 2662 ThisNode* rch = old.index!N.right; 2663 ThisNode* p = old.index!N.parent; 2664 2665 newnode.index!N.left = lch; 2666 if(lch) { 2667 lch.index!N._parent = newnode; 2668 } 2669 newnode.index!N.right = rch; 2670 if(rch) { 2671 rch.index!N._parent = newnode; 2672 } 2673 newnode.index!N._parent = p; 2674 if(p) { 2675 if(p.index!N.left is old) { 2676 p.index!N.left = newnode; 2677 }else if(p.index!N.right is old) { 2678 p.index!N.right = newnode; 2679 } 2680 }else if(old is _end) { 2681 _end = newnode; 2682 } 2683 2684 newnode.index!N.left = null; 2685 newnode.index!N.right = null; 2686 newnode.index!N._parent = null; 2687 } 2688 2689 2690 /* 2691 * Check the tree for validity. This is called after every add or remove. 2692 * This should only be enabled to debug the implementation of the RB Tree. 2693 */ 2694 void _Check() 2695 { 2696 // 2697 // check implementation of the tree 2698 // 2699 int recurse(Node n, string path) 2700 { 2701 if(n is null) 2702 return 1; 2703 if(n.index!N.parent.index!N.left !is n && n.index!N.parent.index!N.right !is n) 2704 // memory allocation! ..how to fix? 2705 throw new Exception("Node at path " ~ path ~ " has inconsistent pointers"); 2706 Node next = n.index!N.next; 2707 static if(allowDuplicates) 2708 { 2709 if(next !is _end && _less(key(next.value), key(n.value))) 2710 // memory allocation! ..how to fix? 2711 throw new Exception("ordering invalid at path " ~ path); 2712 } 2713 else 2714 { 2715 if(next !is _end && !_less(key(n.value), key(next.value))) 2716 // memory allocation! ..how to fix? 2717 throw new Exception("ordering invalid at path " ~ path); 2718 } 2719 if(n.index!N.color == Color.Red) 2720 { 2721 if((n.index!N.left !is null && n.index!N.left.index!N.color == Color.Red) || 2722 (n.index!N.right !is null && n.index!N.right.index!N.color == Color.Red)) 2723 // memory allocation! ..how to fix? 2724 throw new Exception("Node at path " ~ path ~ " is red with a red child"); 2725 } 2726 2727 int l = recurse(n.index!N.left, path ~ "L"); 2728 int r = recurse(n.index!N.right, path ~ "R"); 2729 if(l != r) 2730 { 2731 writeln("bad tree at:"); 2732 printTree(n); 2733 // memory allocation! ..how to fix? 2734 throw new Exception("Node at path " ~ path ~ " has different number of black nodes on left and right paths"); 2735 } 2736 return l + (n.index!N.color == Color.Black ? 1 : 0); 2737 } 2738 2739 try 2740 { 2741 recurse(_end.index!N.left, ""); 2742 } 2743 catch(Exception e) 2744 { 2745 printTree(_end.index!N.left, 0); 2746 throw e; 2747 } 2748 } 2749 2750 string toString0(){ 2751 string r = "["; 2752 auto rng = opSlice(); 2753 while(!rng.empty){ 2754 r ~= format("%s", (rng.front)); 2755 rng.popFront(); 2756 r ~= rng.empty ? "]" : ", "; 2757 } 2758 return r; 2759 } 2760 2761 private OrderedRange fromNode(ThisNode* n){ 2762 return OrderedRange(this,n, this.index!N._end); 2763 } 2764 } 2765 2766 /// A red black tree index 2767 template Ordered(bool allowDuplicates = false, alias KeyFromValue="a", 2768 alias Compare = "a<b") { 2769 2770 enum bool BenefitsFromSignals = true; 2771 2772 template Inner(ThisContainer, ThisNode, Value, ValueView, size_t N, Allocator){ 2773 alias TypeTuple!(N, allowDuplicates, KeyFromValue, Compare,ThisContainer) IndexTuple; 2774 alias OrderedIndex IndexMixin; 2775 2776 enum IndexCtorMixin = Replace!(q{ 2777 index!($N)._end = Allocator.allocate!ThisNode(1); 2778 }, "$N", N); 2779 /// node implementation (ish) 2780 alias TypeTuple!(N) NodeTuple; 2781 alias OrderedNodeMixin NodeMixin; 2782 } 2783 } 2784 2785 /// A red black tree index 2786 template OrderedNonUnique(alias KeyFromValue="a", alias Compare = "a<b") { 2787 alias Ordered!(true, KeyFromValue, Compare) OrderedNonUnique; 2788 } 2789 /// A red black tree index 2790 template OrderedUnique(alias KeyFromValue="a", alias Compare = "a<b") { 2791 alias Ordered!(false, KeyFromValue, Compare) OrderedUnique; 2792 } 2793 2794 // end RBTree impl 2795 2796 /// a max heap index 2797 template Heap(alias KeyFromValue = "a", alias Compare = "a<b") { 2798 // this index allocates the heap array 2799 2800 enum bool BenefitsFromSignals = true; 2801 2802 /// _ 2803 template Inner(ThisContainer, ThisNode, Value, ValueView, size_t N, Allocator) { 2804 alias TypeTuple!() NodeTuple; 2805 alias TypeTuple!(N,KeyFromValue, Compare, ThisContainer) IndexTuple; 2806 2807 mixin template NodeMixin(){ 2808 size_t _index; 2809 } 2810 2811 /// index implementation 2812 mixin template IndexMixin(size_t N, alias KeyFromValue, alias Compare, 2813 ThisContainer){ 2814 alias unaryFun!KeyFromValue key; 2815 alias binaryFun!Compare less; 2816 alias typeof(key((Value).init)) KeyType; 2817 2818 /// The primary range of the index, which embodies a bidirectional 2819 /// range. 2820 /// 2821 /// Ends up performing a breadth first traversal (I think..) 2822 /// 2823 /// removeFront and removeBack are not possible. 2824 struct HeapRangeT(bool is_const) { 2825 static if(is_const) { 2826 alias const(ThisNode) Node; 2827 alias const(ThisContainer) Container; 2828 }else { 2829 alias ThisContainer Container; 2830 alias ThisNode Node; 2831 } 2832 Container c; 2833 size_t s,e; 2834 2835 this(Container _c, size_t _s, size_t _e) { 2836 c = _c; 2837 s = _s; 2838 e = _e; 2839 } 2840 2841 @property Node* front_node() { 2842 return c.index!N._heap[s]; 2843 } 2844 2845 @property front(){ 2846 return front_node.value; 2847 } 2848 2849 void popFront(){ 2850 s++; 2851 } 2852 2853 @property back_node(){ 2854 return c.index!N._heap[e-1]; 2855 } 2856 2857 @property back(){ 2858 return back_node.value; 2859 } 2860 void popBack(){ 2861 e--; 2862 } 2863 2864 @property bool empty()const{ 2865 assert(e <= c.index!N.length); 2866 return s >= c.index!N.length; 2867 } 2868 @property size_t length()const{ 2869 assert(e <= c.index!N.length); 2870 return s <= e ? e - s : 0; 2871 } 2872 2873 @property save(){ return this; } 2874 } 2875 2876 alias HeapRangeT!true ConstHeapRange; 2877 alias HeapRangeT!false HeapRange; 2878 2879 template IsMyRange(T) { 2880 enum bool IsMyRange = 2881 is(T == ConstHeapRange) || 2882 is(T == HeapRange); 2883 } 2884 2885 ThisNode*[] _heap; 2886 2887 static size_t p(size_t n) pure{ 2888 return (n-1) / 2; 2889 } 2890 2891 static size_t l(size_t n) pure{ 2892 return 2*n + 1; 2893 } 2894 2895 static size_t r(size_t n) pure{ 2896 return 2*n + 2; 2897 } 2898 2899 void swapAt(size_t n1, size_t n2){ 2900 swap(_heap[n1].index!N._index, _heap[n2].index!N._index); 2901 swap(_heap[n1], _heap[n2]); 2902 } 2903 2904 void sift(size_t n){ 2905 auto k = key(_heap[n].value); 2906 if(n > 0 && less(key(_heap[p(n)].value), k)){ 2907 do{ 2908 swapAt(n, p(n)); 2909 n = p(n); 2910 }while(n > 0 && less(key(_heap[p(n)].value), k)); 2911 }else 2912 while(l(n) < node_count){ 2913 auto ch = l(n); 2914 auto lk = key(_heap[ch].value); 2915 if(!less(k, lk)) break; 2916 if (r(n) < node_count){ 2917 auto rk = key(_heap[r(n)].value); 2918 if(less(lk, rk)){ 2919 if(!less(k, rk)) break; 2920 ch = r(n); 2921 } 2922 } 2923 swapAt(n, ch); 2924 n = ch; 2925 } 2926 } 2927 2928 /** 2929 Fetch a range that spans all the elements in the container. 2930 2931 Complexity: $(BIGOH 1) 2932 */ 2933 HeapRange opSlice() { 2934 return HeapRange(this,0, node_count); 2935 } 2936 ConstHeapRange opSlice() const{ 2937 return ConstHeapRange(this,0, node_count); 2938 } 2939 2940 /** 2941 Returns the number of elements in the container. 2942 2943 Complexity: $(BIGOH 1). 2944 */ 2945 @property size_t length()const{ 2946 return node_count; 2947 } 2948 2949 /** 2950 Property returning $(D true) if and only if the container has no 2951 elements. 2952 2953 Complexity: $(BIGOH 1) 2954 */ 2955 @property bool empty()const{ 2956 return node_count == 0; 2957 } 2958 2959 /** 2960 Returns: the max element in this index 2961 Complexity: $(BIGOH 1) 2962 */ 2963 @property front() inout{ 2964 return _heap[0].value; 2965 } 2966 /** 2967 Returns: the back of this index 2968 Complexity: $(BIGOH 1) 2969 */ 2970 @property back() inout{ 2971 return _heap[node_count-1].value; 2972 } 2973 2974 void _ClearIndex(){ 2975 fill(_heap, (ThisNode*).init); 2976 } 2977 /** 2978 ?? 2979 */ 2980 void clear(){ 2981 _Clear(); 2982 } 2983 2984 void modify(SomeRange, Modifier)(SomeRange r, Modifier mod) 2985 if(is(SomeRange == HeapRange) || 2986 is(ElementType!SomeRange == Position!ThisNode)) { 2987 while(!r.empty) { 2988 static if(is(SomeRange == HeapRange)) { 2989 ThisNode* node = r.front_node; 2990 }else{ 2991 ThisNode* node = r.front.node; 2992 } 2993 r.popFront(); 2994 _Modify(node, mod); 2995 } 2996 } 2997 2998 bool replace(Position!ThisNode r, ValueView value) 2999 { 3000 return _Replace(r.node, cast(Value) value); 3001 } 3002 3003 KeyType _NodePosition(ThisNode* node){ 3004 return key(node.value); 3005 } 3006 3007 bool _PositionFixable(ThisNode* node, KeyType oldPosition, 3008 out ThisNode* cursor){ 3009 return true; 3010 } 3011 3012 void _FixPosition(ThisNode* node, KeyType oldPosition, 3013 ThisNode* cursor){ 3014 // sift will take O(1) if key hasn't changed 3015 sift(node.index!N._index); 3016 } 3017 3018 bool _NotifyChange(ThisNode* node){ 3019 // sift will take O(1) if key hasn't changed 3020 sift(node.index!N._index); 3021 return true; 3022 } 3023 3024 /** 3025 Returns the _capacity of the index, which is the length of the 3026 underlying store 3027 */ 3028 size_t capacity()const{ 3029 return _heap.length; 3030 } 3031 3032 /** 3033 Ensures sufficient capacity to accommodate $(D n) elements. 3034 3035 Postcondition: $(D capacity >= n) 3036 3037 Complexity: $(BIGOH ??) if $(D e > capacity), 3038 otherwise $(BIGOH 1). 3039 */ 3040 void reserve(size_t count){ 3041 if(_heap.length < count){ 3042 auto newheap = Allocator.allocate!(ThisNode*)(count)[0 .. count]; 3043 auto rest = moveAll(_heap, newheap); 3044 fill(rest, (ThisNode*).init); 3045 Allocator.deallocate(_heap.ptr); 3046 _heap = newheap; 3047 } 3048 } 3049 /** 3050 Inserts value into this heap, unless another index refuses it. 3051 Returns: the number of values added to the container 3052 Complexity: $(BIGOH i(n)); $(BR) $(BIGOH log(n)) for this index 3053 */ 3054 size_t insert(SomeValue)(SomeValue value) 3055 if(isImplicitlyConvertible!(SomeValue, ValueView)) 3056 { 3057 ThisNode* n = _InsertAllBut!N(value); 3058 if(!n) return 0; 3059 node_count--; 3060 _Insert(n); 3061 node_count++; 3062 return 1; 3063 } 3064 3065 size_t insert(SomeRange)(SomeRange r) 3066 if(isImplicitlyConvertible!(ElementType!SomeRange, ValueView)) 3067 { 3068 size_t count; 3069 foreach(e; r){ 3070 count += insert(e); 3071 } 3072 return count; 3073 } 3074 3075 void _Insert(ThisNode* node){ 3076 if(node_count == _heap.length){ 3077 reserve(max(_heap.length*2+1, node_count+1)); 3078 } 3079 _heap[node_count] = node; 3080 _heap[node_count].index!N._index = node_count; 3081 sift(node_count); 3082 } 3083 3084 /** 3085 Removes the max element of this index from the container. 3086 Complexity: $(BIGOH d(n)); $(BR) $(BIGOH log(n)) for this index 3087 */ 3088 void removeFront(){ 3089 _RemoveAll(_heap[0]); 3090 } 3091 3092 void _Remove(ThisNode* node){ 3093 if(node.index!N._index == node_count-1){ 3094 _heap[node_count-1] = null; 3095 }else{ 3096 size_t ix = node.index!N._index; 3097 swapAt(ix, node_count-1); 3098 _heap[node_count-1] = null; 3099 node_count--; 3100 sift(ix); 3101 node_count++; 3102 } 3103 } 3104 /** 3105 Forwards to removeFront 3106 */ 3107 alias removeFront removeAny; 3108 3109 3110 /** 3111 * removes the back of this index from the container. Why would you do this? 3112 No idea. 3113 Complexity: $(BIGOH d(n)); $(BR) $(BIGOH 1) for this index 3114 */ 3115 void removeBack(){ 3116 ThisNode* node = _heap[node_count-1]; 3117 _RemoveAll(node); 3118 } 3119 3120 HeapRange remove(R)(R r) 3121 if (is(R == HeapRange) || 3122 is(ElementType!R == Position!ThisNode)){ 3123 while(!r.empty){ 3124 static if(is(R == HeapRange)){ 3125 ThisNode* node = r.front_node; 3126 }else{ 3127 ThisNode* node = r.front.node; 3128 r.front.obliterated = true; 3129 } 3130 r.popFront(); 3131 _RemoveAll(node); 3132 } 3133 return HeapRange(this,0,0); 3134 } 3135 3136 bool isLe(size_t a, size_t b){ 3137 return(!less(key(_heap[b].value),key(_heap[a].value))); 3138 } 3139 3140 bool _invariant(size_t i){ 3141 bool result = true; 3142 if(i > 0){ 3143 result &= (isLe(i,p(i))); 3144 } 3145 if( l(i) < node_count ){ 3146 result &= (isLe(l(i), i)); 3147 } 3148 if( r(i) < node_count ){ 3149 result &= (isLe(r(i), i)); 3150 } 3151 return result; 3152 } 3153 3154 void _NodeReplace(ThisNode* old, ThisNode* newnode) { 3155 move(newnode, _heap[old.index!N._index]); 3156 newnode.index!N._index = old.index!N._index; 3157 } 3158 3159 void _Check(){ 3160 for(size_t i = 0; i < node_count; i++){ 3161 assert (_heap[i].index!N._index == i); 3162 assert (_invariant(i)); 3163 } 3164 3165 } 3166 3167 void printHeap(){ 3168 printHeap1(0,0); 3169 } 3170 3171 void printHeap1(size_t n, size_t indent){ 3172 if (l(n) < node_count) printHeap1(l(n), indent+1); 3173 for(int i = 0; i < indent; i++) 3174 write(".."); 3175 static if(__traits(compiles, (_heap[n].value.toString0()))){ 3176 writefln("%s (%s) %s", n, _heap[n].value.toString0(), _invariant(n) ? "" : "<--- bad!!!"); 3177 }else{ 3178 writefln("(%s)", _heap[n].value); 3179 } 3180 3181 if (r(n) < node_count) printHeap1(r(n), indent+1); 3182 } 3183 3184 string toString0(){ 3185 string r = "["; 3186 auto rng = opSlice(); 3187 while(!rng.empty){ 3188 r ~= format("%s", (rng.front)); 3189 rng.popFront(); 3190 r ~= rng.empty ? "]" : ", "; 3191 } 3192 return r; 3193 } 3194 3195 private HeapRange fromNode(ThisNode* n){ 3196 return HeapRange(this, n.index!N._index, this.node_count); 3197 } 3198 } 3199 } 3200 } 3201 3202 // thieved from boost::multi_index::detail::bucket_array. 3203 static if(size_t.sizeof == 4){ 3204 immutable size_t[] primes = [ 3205 53u, 97u, 193u, 389u, 769u, 3206 1543u, 3079u, 6151u, 12289u, 24593u, 3207 49157u, 98317u, 196613u, 393241u, 786433u, 3208 1572869u, 3145739u, 6291469u, 12582917u, 25165843u, 3209 50331653u, 100663319u, 201326611u, 402653189u, 805306457u, 3210 1610612741u, 3221225473u, 4294967291u 3211 ]; 3212 }else static if(size_t.sizeof == 8){ 3213 immutable size_t[] primes = [ 3214 53uL, 97uL, 193uL, 389uL, 769uL, 3215 1543uL, 3079uL, 6151uL, 12289uL, 24593uL, 3216 49157uL, 98317uL, 196613uL, 393241uL, 786433uL, 3217 1572869uL, 3145739uL, 6291469uL, 12582917uL, 25165843uL, 3218 50331653uL, 100663319uL, 201326611uL, 402653189uL, 805306457uL, 3219 1610612741uL, 3221225473uL, 4294967291uL, 3220 6442450939uL, 12884901893uL, 25769803751uL, 51539607551uL, 3221 103079215111uL, 206158430209uL, 412316860441uL, 824633720831uL, 3222 1649267441651uL, 3298534883309uL, 6597069766657uL, 13194139533299uL, 3223 26388279066623uL, 52776558133303uL, 105553116266489uL, 3224 211106232532969uL, 3225 422212465066001uL, 844424930131963uL, 1688849860263953uL, 3226 3377699720527861uL, 6755399441055731uL, 13510798882111483uL, 3227 27021597764222939uL, 54043195528445957uL, 108086391056891903uL, 3228 216172782113783843uL, 432345564227567621uL, 864691128455135207uL, 3229 1729382256910270481uL, 3458764513820540933uL, 6917529027641081903uL, 3230 13835058055282163729uL, 18446744073709551557uL 3231 ]; 3232 }else static assert(false, 3233 Replace!("waht is this weird sizeof(size_t) == %s?", "%s",size_t.sizeof)); 3234 3235 /// a hash table index 3236 /// KeyFromValue(value) = key of type KeyType 3237 /// Hash(key) = hash of type size_t 3238 /// Eq(key1, key2) determines equality of key1, key2 3239 template Hashed(bool allowDuplicates = false, alias KeyFromValue="a", 3240 alias Hash="typeid(a).getHash(&a)", alias Eq="a==b") { 3241 // this index allocates the table, and an array in removeKey 3242 3243 enum bool BenefitsFromSignals = true; 3244 3245 /// _ 3246 template Inner(ThisContainer, ThisNode, Value, ValueView, size_t N, Allocator) { 3247 alias unaryFun!KeyFromValue key; 3248 alias typeof(key(Value.init)) KeyType; 3249 3250 alias TypeTuple!(N) NodeTuple; 3251 alias TypeTuple!(N,KeyFromValue, Hash, Eq, allowDuplicates, 3252 Sequenced!().Inner!(ThisContainer, ThisNode,Value,ValueView,N,Allocator).SequencedRange, 3253 ThisContainer) IndexTuple; 3254 // node implementation 3255 // could be singly linked, but that would make aux removal more 3256 // difficult 3257 alias Sequenced!().Inner!(ThisContainer, ThisNode, Value, ValueView,N,Allocator).NodeMixin 3258 NodeMixin; 3259 3260 enum IndexCtorMixin = Replace!(q{ 3261 index!$N .hashes = Allocator.allocate!(ThisNode*)(primes[0])[0 .. primes[0]]; 3262 index!$N .load_factor = 0.80; 3263 }, "$N", N); 3264 3265 /// index implementation 3266 mixin template IndexMixin(size_t N, alias KeyFromValue, alias Hash, 3267 alias Eq, bool allowDuplicates, alias SeqRange, ThisContainer){ 3268 alias unaryFun!KeyFromValue key; 3269 alias typeof(key((Value).init)) KeyType; 3270 alias unaryFun!Hash hash; 3271 alias binaryFun!Eq eq; 3272 alias SeqRange!false BucketSeqRange; 3273 alias SeqRange!true ConstBucketSeqRange; 3274 3275 /// the primary range for this index, which embodies a forward 3276 /// range. iteration has time complexity O(n) 3277 struct HashedRangeT(bool is_const) { 3278 static if(is_const) { 3279 alias const(ThisNode) Node; 3280 alias const(ThisContainer) Container; 3281 }else { 3282 alias ThisContainer Container; 3283 alias ThisNode Node; 3284 } 3285 Container c; 3286 Node* node; 3287 alias node front_node; 3288 size_t n; 3289 3290 this(Container _c, Node* _node, size_t _n) { 3291 c = _c; 3292 node = _node; 3293 n = _n; 3294 } 3295 3296 @property bool empty()/*const*/{ 3297 return n >= c.index!N.hashes.length; 3298 } 3299 3300 @property front() { 3301 return node.value; 3302 } 3303 3304 void popFront(){ 3305 node = node.index!N.next; 3306 if(!node){ 3307 do n++; 3308 while(n < c.index!N.hashes.length && !c.index!N.hashes[n]); 3309 if( n < c.index!N.hashes.length ){ 3310 node = c.index!N.hashes[n]; 3311 } 3312 } 3313 } 3314 3315 @property save(){ 3316 return this; 3317 } 3318 } 3319 3320 alias HashedRangeT!true ConstHashedRange; 3321 alias HashedRangeT!false HashedRange; 3322 3323 template IsMyRange(T) { 3324 enum bool IsMyRange = 3325 is(T == HashedRange) || 3326 is(T == ConstHashedRange) || 3327 is(T == BucketSeqRange) || 3328 is(T == ConstBucketSeqRange); 3329 } 3330 3331 ThisNode*[] hashes; 3332 ThisNode* _first; 3333 double load_factor; 3334 3335 bool isFirst(ThisNode* n){ 3336 version(BucketHackery){ 3337 size_t ix = cast(size_t) n.index!N.prev; 3338 return ix < hashes.length && hashes[ix] == n; 3339 }else{ 3340 return n.index!N.prev is null; 3341 } 3342 } 3343 3344 // sets n as the first in bucket list at index 3345 void setFirst(ThisNode* n, size_t index){ 3346 // first: see if the index of this bucket list is before 3347 // _front's bucket list index 3348 version(BucketHackery){ 3349 size_t findex = !_first?-1: 3350 cast(size_t) _first.index!N.prev; 3351 }else{ 3352 size_t findex = !_first?-1: 3353 hash(key(_first.value))%hashes.length; 3354 } 3355 if(findex >= index) _first = n; 3356 if(hashes[index] && hashes[index] != n){ 3357 version(BucketHackery){ 3358 // be sure not to give insertPrev any bogus 3359 // links to follow and impale itself with 3360 hashes[index].index!N.prev=null; 3361 } 3362 hashes[index].index!N.insertPrev(n); 3363 } 3364 hashes[index] = n; 3365 version(BucketHackery){ 3366 n.index!N.prev = cast(ThisNode*) index; 3367 } 3368 } 3369 3370 void removeFirst(ThisNode* n){ 3371 version(BucketHackery){ 3372 size_t index = cast(size_t) n.index!N.prev; 3373 }else{ 3374 size_t index = hash(key(n.value))%hashes.length; 3375 } 3376 auto nxt = n.index!N.next; 3377 hashes[index] = nxt; 3378 n.index!N.next = null; 3379 n.index!N.prev = null; 3380 if (nxt){ 3381 version(BucketHackery){ 3382 nxt.index!N.prev = cast(ThisNode*) index; 3383 }else{ 3384 nxt.index!N.removePrev(); 3385 } 3386 if(_first == n){ 3387 _first = nxt; 3388 } 3389 }else if(_first == n){ 3390 while(index < hashes.length && !hashes[index]){ 3391 index++; 3392 } 3393 if(index < hashes.length) _first = hashes[index]; 3394 } 3395 } 3396 3397 3398 /** 3399 Returns the number of elements in the container. 3400 3401 Complexity: $(BIGOH 1). 3402 */ 3403 @property size_t length()const{ 3404 return node_count; 3405 } 3406 3407 /** 3408 Property returning $(D true) if and only if the container has no 3409 elements. 3410 3411 Complexity: $(BIGOH 1) 3412 */ 3413 @property bool empty()const{ 3414 return node_count == 0; 3415 } 3416 3417 /** 3418 Preconditions: !empty 3419 Complexity: $(BIGOH 1) 3420 */ 3421 @property front() inout{ 3422 return _first.value; 3423 } 3424 3425 void _ClearIndex(){ 3426 _first = null; 3427 fill(hashes, cast(ThisNode*)null); 3428 } 3429 /** 3430 ?? 3431 */ 3432 void clear(){ 3433 _Clear(); 3434 } 3435 3436 /** 3437 Gets a range of all elements in container. 3438 Complexity: $(BIGOH 1) 3439 */ 3440 HashedRange opSlice(){ 3441 if(empty) return HashedRange(this, null, hashes.length); 3442 auto ix = hash(key(_first.value))%hashes.length; 3443 return HashedRange(this, _first, ix); 3444 } 3445 ConstHashedRange opSlice() const{ 3446 if(empty) 3447 return ConstHashedRange(this, null, hashes.length); 3448 auto ix = hash(key(_first.value))%hashes.length; 3449 return ConstHashedRange(this, _first, ix); 3450 } 3451 3452 // returns true iff k was found. 3453 // when k in hashtable: 3454 // node = first node in hashes[ix] such that eq(key(node.value),k) 3455 // when k not in hashtable: 3456 // node = null -> put value of k in hashes[ix] 3457 // or node is last node in hashes[ix] chain -> 3458 // put value of k in node.next 3459 bool _find(const(KeyType) k, out inout(ThisNode)* node, out size_t index) inout{ 3460 index = hash(k)%hashes.length; 3461 if(!hashes[index]){ 3462 node = null; 3463 return false; 3464 } 3465 node = hashes[index]; 3466 // TODO: figure out unaryFun & inout 3467 while(!eq(k, key(cast()node.value))){ 3468 if (node.index!N.next is null){ 3469 return false; 3470 } 3471 node = node.index!N.next; 3472 } 3473 return true; 3474 } 3475 3476 static if(!allowDuplicates){ 3477 /** 3478 Available for Unique variant. 3479 Complexity: 3480 $(BIGOH n) ($(BIGOH 1) on a good day) 3481 */ 3482 ValueView opIndex ( KeyType k ) const{ 3483 const(ThisNode)* node; 3484 size_t index; 3485 enforce(_find(k, node, index)); 3486 return cast(ValueView) node.value; 3487 } 3488 } 3489 3490 /** 3491 Reports whether a value exists in the collection such that eq(k, key(value)). 3492 Complexity: 3493 $(BIGOH n) ($(BIGOH 1) on a good day) 3494 */ 3495 static if(!isImplicitlyConvertible!(KeyType, ValueView)){ 3496 bool opBinaryRight(string op)(KeyType k) const 3497 if (op == "in") 3498 { 3499 ThisNode* node; 3500 size_t index; 3501 return _find(k, node,index); 3502 } 3503 } 3504 3505 /** 3506 Reports whether value exists in this collection. 3507 Complexity: 3508 $(BIGOH n) ($(BIGOH n 1) on a good day) 3509 */ 3510 bool opBinaryRight(string op)(ValueView value) const 3511 if (op == "in") 3512 { 3513 const(ThisNode)* node; 3514 size_t index; 3515 return _find(key(value), node,index); 3516 } 3517 3518 /** 3519 Reports whether value exists in this collection 3520 Complexity: 3521 $(BIGOH n) ($(BIGOH n 1) on a good day) 3522 */ 3523 bool containsValue(ValueView value) const{ 3524 const(ThisNode)* node; 3525 size_t index; 3526 auto r = _find(key(value), node,index); 3527 return r; 3528 } 3529 3530 ///ditto 3531 bool contains(KeyType k) const{ 3532 const(ThisNode)* node; 3533 size_t index; 3534 return _find(k, node,index); 3535 } 3536 3537 void modify(SomeRange, Modifier)(SomeRange r, Modifier mod) 3538 if(is(SomeRange == HashedRange) || 3539 is(ElementType!SomeRange == Position!ThisNode)) { 3540 while(!r.empty) { 3541 static if(is(SomeRange == HashedRange)) { 3542 ThisNode* node = r.front_node; 3543 }else{ 3544 ThisNode* node = r.front.node; 3545 } 3546 r.popFront(); 3547 _Modify(node, mod); 3548 } 3549 } 3550 3551 bool replace(Position!ThisNode r, ValueView value) { 3552 return _Replace(r.node, cast(Value) value); 3553 } 3554 3555 KeyType _NodePosition(ThisNode* node){ 3556 return key(node.value); 3557 } 3558 3559 // cursor = null -> no fixup necessary or fixup to start of chain 3560 // cursor != null -> fixup necessary 3561 bool _PositionFixable(ThisNode* node, KeyType oldPosition, 3562 out ThisNode* cursor){ 3563 cursor = null; 3564 auto newPosition = key(node.value); 3565 if(eq(newPosition, oldPosition)) return true; 3566 static if(allowDuplicates){ 3567 cursor = node; 3568 return true; 3569 }else{ 3570 ThisNode* n; 3571 size_t index; 3572 return !(_find(newPosition, cursor, index)); 3573 } 3574 3575 } 3576 3577 void _FixPosition(ThisNode* node, KeyType oldPosition, 3578 ThisNode* cursor){ 3579 auto newPosition = key(node.value); 3580 if(eq(newPosition, oldPosition)) return; 3581 static if(allowDuplicates){ 3582 if(cursor){ 3583 _Remove(node); 3584 node.index!N.prev = null; 3585 node.index!N.next = null; 3586 _Insert(node); 3587 } 3588 }else{ 3589 if(eq(oldPosition, key(node.value))) return; 3590 _Remove(node); 3591 _Insert(node, cursor); 3592 } 3593 } 3594 3595 bool _NotifyChange(ThisNode* node){ 3596 size_t index; 3597 if(isFirst(node)){ 3598 version(BucketHackery){ 3599 index = cast(size_t) node.index!N.prev; 3600 }else{ 3601 static assert(0,"signals not implemented for Hashed " ~ 3602 "indices without version=BucketHackery"); 3603 } 3604 }else{ 3605 index = hash(key(node.index!N.prev.value))%hashes.length; 3606 } 3607 3608 size_t newindex = hash(key(node.value))%hashes.length; 3609 if(index != newindex){ 3610 ThisNode* cursor; 3611 _Remove(node); 3612 if(_find(key(node.value), cursor, newindex)){ 3613 static if(!allowDuplicates){ 3614 _RemoveAllBut!N(node); 3615 return false; 3616 }else{ 3617 if(isFirst(cursor)){ 3618 setFirst(node, index); 3619 }else{ 3620 cursor.index!N.insertPrev(node); 3621 } 3622 } 3623 }else if(cursor){ 3624 cursor.index!N.insertNext(node); 3625 }else{ 3626 setFirst(node, index); 3627 } 3628 return true; 3629 } 3630 return true; 3631 } 3632 3633 3634 /** 3635 Returns a range of all elements with eq(key(elem), k). 3636 Complexity: 3637 $(BIGOH n) ($(BIGOH n $(SUB result)) on a good day) 3638 */ 3639 // TODO: compact these back into one 3640 BucketSeqRange equalRange( KeyType k ){ 3641 ThisNode* node; 3642 size_t index; 3643 if(!_find(k, node,index)){ 3644 return BucketSeqRange(this,null,null); 3645 } 3646 static if(!allowDuplicates){ 3647 return BucketSeqRange(this,node,node); 3648 }else{ 3649 ThisNode* node2 = node; 3650 while(node2.index!N.next !is null && 3651 eq(k, key(node2.index!N.next.value))){ 3652 node2 = node2.index!N.next; 3653 } 3654 return BucketSeqRange(this, node, node2); 3655 } 3656 } 3657 ConstBucketSeqRange equalRange( KeyType k ) const{ 3658 const(ThisNode)* node; 3659 size_t index; 3660 if(!_find(k, node,index)){ 3661 return ConstBucketSeqRange(this,null,null); 3662 } 3663 static if(!allowDuplicates){ 3664 return ConstBucketSeqRange(this,node,node); 3665 }else{ 3666 const(ThisNode)* node2 = node; 3667 while(node2.index!N.next !is null && 3668 eq(k, key(node2.index!N.next.value))){ 3669 node2 = node2.index!N.next; 3670 } 3671 return ConstBucketSeqRange(this, node, node2); 3672 } 3673 } 3674 3675 static if(allowDuplicates){ 3676 void _Insert(ThisNode* n){ 3677 ThisNode* cursor; 3678 size_t index; 3679 if(_find(key(n.value), cursor, index)){ 3680 if(isFirst(cursor)){ 3681 setFirst(n, index); 3682 }else{ 3683 cursor.index!N.insertPrev(n); 3684 } 3685 }else if(cursor){ 3686 cursor.index!N.insertNext(n); 3687 }else{ 3688 setFirst(n, index); 3689 } 3690 } 3691 }else{ 3692 bool _DenyInsertion(ThisNode* node, out ThisNode* cursor) 3693 { 3694 size_t index; 3695 auto r = _find(key(node.value), cursor, index); 3696 return r; 3697 } 3698 void _Insert(ThisNode* node, ThisNode* cursor){ 3699 if(cursor){ 3700 cursor.index!N.insertNext(node); 3701 }else{ 3702 size_t index = hash(key(node.value))%hashes.length; 3703 assert ( !hashes[index] ); 3704 setFirst(node, index); 3705 } 3706 } 3707 } 3708 3709 void _Remove(ThisNode* n){ 3710 if(isFirst(n)){ 3711 removeFirst(n); 3712 }else{ 3713 n.index!N.prev.index!N.removeNext(); 3714 } 3715 } 3716 3717 @property loadFactor() const{ 3718 return load_factor; 3719 } 3720 3721 @property loadFactor(size_t _load_factor) { 3722 load_factor = load_factor; 3723 // TODO: what else do we do here? 3724 assert(0); 3725 } 3726 3727 size_t maxLoad(size_t n) const{ 3728 double load = n * load_factor; 3729 if(load > size_t.max) return size_t.max; 3730 return cast(size_t) load; 3731 } 3732 3733 @property size_t capacity() const{ 3734 return hashes.length; 3735 } 3736 3737 void reserve(size_t n){ 3738 if (n <= maxLoad(hashes.length)) return; 3739 size_t i = 0; 3740 while(i < primes.length && maxLoad(primes[i]) < n){ 3741 i++; 3742 } 3743 if (hashes.length == primes[i] && i == primes.length-1){ 3744 // tough 3745 return; 3746 }else if (hashes.length >= primes[i]){ 3747 // hmm. 3748 return; 3749 } 3750 3751 auto r = opSlice(); 3752 auto newhashes = Allocator.allocate!(ThisNode*)(primes[i])[0 .. primes[i]]; 3753 ThisNode* newfirst; 3754 size_t newfindex = -1; 3755 while(!r.empty){ 3756 ThisNode* node = r.front_node; 3757 ThisNode* lastInChain = node; 3758 auto k = key(node.value); 3759 size_t index = hash(key(node.value))%newhashes.length; 3760 r.popFront(); 3761 while(!r.empty && eq(k, key(r.front))){ 3762 lastInChain = r.front_node; 3763 r.popFront(); 3764 } 3765 version(BucketHackery){ 3766 node.index!N.prev = cast(ThisNode*)index; 3767 }else{ 3768 node.index!N.prev = null; 3769 } 3770 lastInChain.index!N.next = null; 3771 if(!newhashes[index]){ 3772 newhashes[index] = node; 3773 if (index < newfindex){ 3774 newfirst = node; 3775 newfindex = index; 3776 } 3777 }else{ 3778 auto p = newhashes[index]; 3779 newhashes[index] = node; 3780 p.index!N.prev = lastInChain; 3781 lastInChain.index!N.next = p; 3782 if(newfirst == p){ 3783 newfirst = node; 3784 } 3785 } 3786 } 3787 3788 Allocator.deallocate(hashes.ptr); 3789 hashes = newhashes; 3790 _first = newfirst; 3791 } 3792 /** 3793 insert value into this container. For Unique variant, will refuse value 3794 if value already exists in index. 3795 Returns: 3796 number of items inserted into this container. 3797 Complexity: 3798 $(BIGOH i(n)) $(BR) $(BIGOH n) for this index ($(BIGOH 1) on a good day) 3799 */ 3800 size_t insert(SomeValue)(SomeValue value) 3801 if(isImplicitlyConvertible!(SomeValue, ValueView)) { 3802 ThisNode* node; 3803 size_t index; 3804 if(maxLoad(hashes.length) < node_count+1){ 3805 reserve(max(maxLoad(2* hashes.length + 1), node_count+1)); 3806 } 3807 static if(!allowDuplicates){ 3808 // might deny, so have to look 3809 auto k = key(value); 3810 bool found = _find(k, node, index); 3811 if(found) return 0; 3812 ThisNode* newnode = _InsertAllBut!N(value); 3813 if(!newnode) return 0; 3814 }else{ 3815 // won't deny, so don't bother looking until 3816 // we know other indices won't deny. 3817 ThisNode* newnode = _InsertAllBut!N(value); 3818 if(!newnode) return 0; 3819 auto k = key(value); 3820 bool found = _find(k, node, index); 3821 } 3822 if(found){ 3823 // meh, lets not walk to the end of equal range 3824 if (isFirst(node)){ 3825 setFirst(newnode,index); 3826 }else{ 3827 node.index!N.insertPrev(newnode); 3828 } 3829 }else if(node){ 3830 node.index!N.insertNext(newnode); 3831 }else{ 3832 setFirst(newnode,index); 3833 } 3834 return 1; 3835 } 3836 3837 /** 3838 insert contents of r into this container. For Unique variant, will refuse 3839 any items in content if it already exists in index. 3840 Returns: 3841 number of items inserted into this container. 3842 Complexity: 3843 $(BIGOH i(n)) $(BR) $(BIGOH n+n $(SUB r)) for this index 3844 ($(BIGOH n $(SUB r)) on a good day) 3845 */ 3846 size_t insert(SomeRange)(SomeRange r) 3847 if(isImplicitlyConvertible!(ElementType!SomeRange, ValueView)){ 3848 size_t count = 0; 3849 static if(hasLength!SomeRange){ 3850 if(maxLoad(node_count) < node_count+r.length){ 3851 reserve(max(2 * node_count + 1, node_count+r.length)); 3852 } 3853 } 3854 foreach(e; r){ 3855 count += insert(e); 3856 static if(hasLength!SomeRange){ 3857 if(maxLoad(node_count) < node_count+1){ 3858 reserve(max(2* node_count + 1, node_count+1)); 3859 } 3860 } 3861 } 3862 return count; 3863 } 3864 3865 /** 3866 Removes all of r from this container. 3867 Preconditions: 3868 r came from this index 3869 Returns: 3870 an empty range 3871 Complexity: 3872 $(BIGOH n $(SUB r) * d(n)), $(BR) 3873 $(BIGOH n $(SUB r)) for this index 3874 */ 3875 HashedRange remove(R)( R r ) 3876 if(is(R == HashedRange) || is(R == BucketSeqRange) || 3877 is(ElementType!R == Position!ThisNode)){ 3878 while(!r.empty){ 3879 static if(IsMyRange!R){ 3880 ThisNode* node = r.front_node; 3881 }else{ 3882 ThisNode* node = r.front.node; 3883 r.front.obliterated = true; 3884 } 3885 r.popFront(); 3886 _RemoveAll(node); 3887 } 3888 return HashedRange(this, null, hashes.length); 3889 } 3890 3891 /** 3892 Removes all elements with key k from this container. 3893 Returns: 3894 the number of elements removed 3895 Complexity: 3896 $(BIGOH n $(SUB k) * d(n)), $(BR) 3897 $(BIGOH n + n $(SUB k)) for this index ($(BIGOH n $(SUB k)) on a good day) 3898 */ 3899 version(OldWay){ 3900 size_t removeKey(KeyType k){ 3901 auto r = equalRange(k); 3902 size_t count = 0; 3903 while(!r.empty){ 3904 ThisNode* node = r._front; 3905 r.popFront(); 3906 _RemoveAll(node); 3907 count++; 3908 } 3909 return count; 3910 } 3911 }else{ 3912 3913 size_t removeKey(Keys...)(Keys keys) 3914 if(allSatisfy!(implicitlyConverts,Keys)) { 3915 Unqual!KeyType[Keys.length] toRemove; 3916 foreach(i,k; keys) { 3917 Unqual!KeyType k2 = k; 3918 toRemove[i] = k2; 3919 } 3920 return removeKey(cast(KeyType[]) (toRemove[])); 3921 } 3922 3923 size_t removeKey(Key)(Key[] keys) 3924 if(isImplicitlyConvertible!(Key, KeyType)) 3925 out(r){ 3926 version(RBDoChecks) _Check(); 3927 }body{ 3928 ThisNode* node; 3929 size_t index; 3930 size_t count = 0; 3931 3932 foreach(k; keys) 3933 { 3934 if(!_find(k, node, index)){ 3935 continue; 3936 } 3937 _RemoveAll(node); 3938 count++; 3939 } 3940 3941 return count; 3942 } 3943 3944 private template implicitlyConverts(Key){ 3945 enum implicitlyConverts = isImplicitlyConvertible!(Key,KeyType); 3946 } 3947 3948 /++ Ditto +/ 3949 size_t removeKey(Stuff)(Stuff stuff) 3950 if(isInputRange!Stuff && 3951 isImplicitlyConvertible!(ElementType!Stuff, KeyType) && 3952 !isDynamicArray!Stuff) { 3953 //We use array in case stuff is a Range from this 3954 // hash - either directly or indirectly. 3955 auto stuffy = allocatedArray!Allocator(stuff); 3956 auto res = removeKey(stuffy); 3957 Allocator.deallocate(stuffy.ptr); 3958 return res; 3959 } 3960 } 3961 3962 void _NodeReplace(ThisNode* old, ThisNode* newnode) { 3963 ThisNode* next = old.index!N.next; 3964 ThisNode* prev = old.index!N.prev; 3965 newnode.index!N.next = next; 3966 newnode.index!N.prev = prev; 3967 if(next) { 3968 next.index!N.prev = newnode; 3969 } 3970 if(prev) { 3971 prev.index!N.next = newnode; 3972 } 3973 if(old is _first) { 3974 _first = newnode; 3975 } 3976 3977 old.index!N.prev = null; 3978 old.index!N.next = null; 3979 } 3980 3981 void _Check(){ 3982 bool first = true; 3983 foreach(i, node; hashes){ 3984 if(!node) continue; 3985 if(first){ 3986 assert(_first is node); 3987 first = false; 3988 } 3989 assert(isFirst(node)); 3990 ThisNode* prev = null; 3991 while(node){ 3992 3993 assert(hash(key(node.value))%hashes.length == i); 3994 if(!isFirst(node)){ 3995 static if(!allowDuplicates){ 3996 assert(!eq(key(prev.value), key(node.value))); 3997 } 3998 // gonna be hard to enforce that equal elements are contiguous 3999 } 4000 4001 prev = node; 4002 node = node.index!N.next; 4003 } 4004 } 4005 } 4006 4007 string toString0(){ 4008 string r = "["; 4009 auto rng = opSlice(); 4010 while(!rng.empty){ 4011 r ~= format("%s", (rng.front)); 4012 rng.popFront(); 4013 r ~= rng.empty ? "]" : ", "; 4014 } 4015 return r; 4016 } 4017 4018 private HashedRange fromNode(ThisNode* n){ 4019 auto ix = hash(key(n.value))%this.index!N.hashes.length; 4020 return HashedRange(this, n, ix); 4021 } 4022 } 4023 } 4024 } 4025 4026 /// _ 4027 template HashedUnique(alias KeyFromValue="a", 4028 alias Hash="typeid(a).getHash(&a)", alias Eq="a==b"){ 4029 alias Hashed!(false, KeyFromValue, Hash, Eq) HashedUnique; 4030 } 4031 /// _ 4032 template HashedNonUnique(alias KeyFromValue="a", 4033 alias Hash="typeid(a).getHash(&a)", alias Eq="a==b"){ 4034 alias Hashed!(true, KeyFromValue, Hash, Eq) HashedNonUnique; 4035 } 4036 4037 4038 class Position(MNode) { 4039 alias MNode.ThisContainer.ValueView ValueView; 4040 alias MNode.ThisContainer.Allocator Allocator; 4041 4042 @property ValueView v() { 4043 return node.value; 4044 } 4045 4046 private: 4047 bool obliterated = true; 4048 MNode* _node; 4049 4050 @disable this(); 4051 4052 static auto create(MNode* _node) { 4053 import std.conv : emplace; 4054 auto p = cast(Position)Allocator.allocate!void(__traits(classInstanceSize, Position)); 4055 p.emplace(); 4056 p.obliterated = false; 4057 p._node = _node; 4058 return p; 4059 } 4060 4061 void release(Position p){ 4062 Allocator.deallocate(cast(void*) p); 4063 } 4064 4065 @property node() { 4066 enforce(!obliterated, 4067 "this position no longer exists in container"); 4068 return _node; 4069 } 4070 } 4071 4072 auto PSR(Range)(Range rng) 4073 { 4074 alias Position!(typeof(*rng.front_node)) Pos; 4075 4076 static struct PositionRange { 4077 4078 Range source; 4079 4080 @property empty() { 4081 return source.empty(); 4082 } 4083 4084 @property Pos front() { 4085 return Pos.create(source.front_node); 4086 } 4087 4088 void popFront() { 4089 source.popFront(); 4090 } 4091 4092 static if(isBidirectionalRange!Range) { 4093 @property Pos back() { 4094 return Pos.create(source.back_node); 4095 } 4096 4097 void popBack() { 4098 source.popBack(); 4099 } 4100 } 4101 4102 static if(isForwardRange!Range) { 4103 @property save() { 4104 return PositionRange(source.save()); 4105 } 4106 } 4107 4108 static if(isRandomAccessRange!Range) { 4109 auto opIndex(size_t i) { 4110 return source.nth_node(i); 4111 } 4112 4113 @property length() { 4114 return source.length; 4115 } 4116 4117 @property front(typeof(source.front_node) n) { 4118 source.front_node = n; 4119 } 4120 4121 @property opSlice(size_t a, size_t b) { 4122 return PositionRange(source[a .. b]); 4123 } 4124 } 4125 } 4126 4127 return PositionRange(rng); 4128 } 4129 4130 struct IndexedBy(L...) 4131 { 4132 template _inner(size_t index, List...) { 4133 static if(List.length <= 1) { 4134 alias TypeTuple!() names; 4135 alias TypeTuple!() name_indices; 4136 alias TypeTuple!(List) indices; 4137 }else static if(IsIndex!(List[0]) && is(typeof(List[1]) == string)) { 4138 alias _inner!(index+1,List[2 .. $]) next; 4139 alias TypeTuple!(List[1], next.names) names; 4140 alias TypeTuple!(index, next.name_indices) name_indices; 4141 alias TypeTuple!(List[0], next.indices) indices; 4142 }else { 4143 alias _inner!(index+1,List[1 .. $]) next; 4144 alias next.names names; 4145 alias next.name_indices name_indices; 4146 alias TypeTuple!(List[0], next.indices) indices; 4147 } 4148 } 4149 4150 alias _inner!(0, L).names Names; 4151 alias _inner!(0, L).name_indices NameIndices; 4152 alias _inner!(0, L).indices Indices; 4153 alias L List; 4154 } 4155 4156 template GetMixinAlias(valueSignal){ 4157 alias valueSignal.MixinAlias GetMixinAlias; 4158 } 4159 4160 // todo - find better name 4161 template OU(T){ 4162 template arr2tuple(stuff...){ 4163 static assert(is(typeof(stuff[0]) == T[])); 4164 4165 static if(stuff[0].length){ 4166 alias arr2tuple!(stuff[0][1 .. $], stuff[1 .. $], stuff[0][0]) arr2tuple; 4167 }else{ 4168 alias stuff[1 .. $] arr2tuple; 4169 } 4170 } 4171 4172 T[] orderedUniqueInsert(T[] x, T value){ 4173 size_t i; 4174 while(i < x.length && x[i] < value) i++; 4175 if(i < x.length && x[i] == value) return x; 4176 T[] ret = new T[](x.length+1); 4177 ret[0 .. i] = x[0 .. i]; 4178 ret[i] = value; 4179 ret[i+1 .. $] = x[i .. $]; 4180 return ret; 4181 } 4182 T[] TypeList2SortedArray(L...)(){ 4183 alias L List; 4184 T[] ret = []; 4185 foreach(T l; List){ 4186 ret = orderedUniqueInsert(ret, l); 4187 } 4188 return ret; 4189 } 4190 } 4191 4192 /** 4193 Specifies how to hook up value signals to indices. 4194 4195 A value type Value is a signal whenever Value supports the signal 4196 interface, ie $(BR) 4197 4198 value.connect(void delegate() slot) $(BR) 4199 value.disconnect(void delegate() slot) 4200 4201 and has the semantics that whenever value changes in a way that will cause 4202 its position in index to change or become invalid, a call is made to slot. 4203 The index will respond by fixing the position, or if that is not possible, 4204 by throwing an exception. 4205 4206 A value may contain multiple signals within different mixin aliases. If this 4207 is the case, the interface is 4208 4209 value.mixinAlias.connect(void delegate() slot) $(BR) 4210 value.mixinAlias.disconnect(void delegate() slot) 4211 4212 where mixinAlias is passed in as a string to each element of L. 4213 4214 Arguments must be instantiations of ValueSignal. 4215 4216 Signals to single indices can be specified by ValueSignal!(index[, mixinAlias]) 4217 4218 Signals to all indices can be specified by ValueSignal!("*"[, mixinAlias]) 4219 4220 A signal can be shared by multiple indices; however do not associate a signal 4221 to the same index more than once. 4222 */ 4223 4224 struct ValueChangedSlots(L...) { 4225 struct Inner(IndexedBy){ 4226 // by some forward referencing error or other, (issue 6475) 4227 // I can't seem to get a hold of inner in, but 4228 // typeof(exposeType()) seems to work. Desparate times require 4229 // desparate measures, I guess 4230 static exposeType(){ 4231 Inner i; 4232 return i; 4233 } 4234 enum N = IndexedBy.Indices.length; 4235 alias ExpandStarSignals!(IndexedBy,L) List; 4236 4237 4238 template GetIndex(valueSignal){ 4239 static if(__traits(compiles,valueSignal.Index)){ 4240 enum GetIndex = valueSignal.Index; 4241 }else{ 4242 static assert(__traits(compiles,valueSignal.Tag)); 4243 static if(valueSignal.Tag == "*") { 4244 static assert(false, "you bad, bad person"); 4245 }else { 4246 enum _TagIndex = staticIndexOf!(valueSignal.Tag, IndexedBy.Names); 4247 enum GetIndex = IndexedBy.NameIndices[_TagIndex]; 4248 } 4249 } 4250 } 4251 4252 enum string[] AllSignals = OU!(string).TypeList2SortedArray!( 4253 NoDuplicates!(staticMap!(GetMixinAlias, List)))(); 4254 4255 template FindIndices(string mixinAlias, size_t i, indices...) 4256 if(indices.length == 1 && is(typeof(indices[0]) == size_t[])){ 4257 static if(i < List.length){ 4258 static if(List[i].MixinAlias == mixinAlias){ 4259 enum index = GetIndex!(List[i]); 4260 static if(IndexedBy.Indices[index].BenefitsFromSignals){ 4261 enum size_t[] result = 4262 FindIndices!(mixinAlias, i+1, 4263 OU!(size_t).orderedUniqueInsert( 4264 indices[0], index)).result; 4265 }else{ 4266 enum size_t[] result = 4267 FindIndices!(mixinAlias, i+1, indices[0]).result; 4268 } 4269 }else{ 4270 enum size_t[] result = 4271 FindIndices!(mixinAlias, i+1, indices[0]).result; 4272 } 4273 }else{ 4274 enum size_t[] result = indices[0]; 4275 } 4276 } 4277 4278 template GenSets(size_t i, MI...){ 4279 static if (i < AllSignals.length){ 4280 enum mixinAlias = AllSignals[i]; 4281 enum indices = FindIndices!(mixinAlias,0,cast(size_t[])[]).result; 4282 template InsertIndices(size_t j){ 4283 static if(j < MI.length){ 4284 static if(MI[j].Indices == indices){ 4285 alias TypeTuple!(MI[0 .. j], 4286 Mixin2Indices!( 4287 OU!(string).orderedUniqueInsert( 4288 MI[j].MixinAliases,mixinAlias), 4289 indices 4290 ), 4291 MI[j+1 .. $]) InsertIndices; 4292 }else{ 4293 alias InsertIndices!(i+1) InsertIndices; 4294 } 4295 }else{ 4296 alias TypeTuple!(MI, Mixin2Indices!([mixinAlias], 4297 indices)) InsertIndices; 4298 } 4299 } 4300 4301 static if(indices.length > 0){ 4302 alias InsertIndices!(0) MI2; 4303 alias GenSets!(i+1, MI2).result result; 4304 }else{ 4305 alias GenSets!(i+1, MI).result result; 4306 } 4307 }else{ 4308 alias MI result; 4309 } 4310 } 4311 4312 // map { set of mixin aliases -> set of indices } 4313 // since we don't have maps or sets in ct (boo), 4314 // really this is a list of ((list of mixin aliases), (list of indices)) 4315 // with each inner list sorted ascending. 4316 // 4317 // what's the background? 4318 // we want to generate no more than M slots for this index/signal 4319 // spec, where M is the number of distinct signals (mixin aliases) 4320 // passed in. This should minimize the amount of additional memory 4321 // that each value has to keep track of. 4322 // 4323 // We also want to know when different signals share the same index 4324 // set, so we don't have to generate redundant slots. 4325 // so we generate this mapping, which should help. 4326 // 4327 // Requires: In the map's key set - a set of sets of mixin aliases - 4328 // each mixin appears in exactly one set. (it is a true set) 4329 // The map's value set - a set of sets of indices - is a true set, 4330 // each index set is unique 4331 // 4332 // Then: for each entry in the map (K,V), we generate a slot function W 4333 // inside our node. W gets connected/disconnected to/from each of 4334 // the signals in K. W notifies each of the indices in V. 4335 4336 alias GenSets!(0).result Mixin2Index; 4337 4338 4339 template _GetIndicesForSignal(string signal, size_t i){ 4340 static if(i < N){ 4341 static if(staticIndexOf!(signal, GetMixinAliases!(List[i])) 4342 != -1){ 4343 alias TypeTuple!(i,_GetIndicesForSignal!(signal,i+1)) 4344 _GetIndicesForSignal; 4345 }else{ 4346 alias _GetIndicesForSignal!(signal,i+1) 4347 _GetIndicesForSignal; 4348 } 4349 }else{ 4350 alias TypeTuple!() _GetIndicesForSignal; 4351 } 4352 } 4353 4354 template GetIndicesForSignal(string signal){ 4355 alias _GetIndicesForSignal!(signal, 0) GetIndicesForSignal; 4356 } 4357 } 4358 } 4359 4360 template ExpandStarSignals(IndexedBy, L...) { 4361 static if(L.length == 0) { 4362 alias TypeTuple!() ExpandStarSignals; 4363 }else static if(__traits(compiles,L[0].Tag) && L[0].Tag == "*") { 4364 alias TypeTuple!(ExpandStarSignal!(IndexedBy, 0, L[0]), 4365 ExpandStarSignals!(IndexedBy, L[1 .. $])) ExpandStarSignals; 4366 }else{ 4367 alias TypeTuple!(L[0], ExpandStarSignals!(IndexedBy, L[1 .. $])) 4368 ExpandStarSignals; 4369 } 4370 } 4371 4372 template ExpandStarSignal(IndexedBy, size_t i, ProtoSignal) { 4373 static if(i >= IndexedBy.Indices.length) { 4374 alias TypeTuple!() ExpandStarSignal; 4375 }else { 4376 alias TypeTuple!(ValueSignal!(i, ProtoSignal.MixinAlias), 4377 ExpandStarSignal!(IndexedBy, i+1, ProtoSignal)) ExpandStarSignal; 4378 } 4379 4380 } 4381 4382 /// _ 4383 struct ValueSignal(size_t index, string mixinAlias = "") 4384 { 4385 enum size_t Index = index; 4386 enum MixinAlias = mixinAlias; 4387 } 4388 4389 /// _ 4390 struct ValueSignal(string tag, string mixinAlias = "") 4391 { 4392 enum Tag = tag; 4393 enum MixinAlias = mixinAlias; 4394 } 4395 4396 struct Mixin2Indices(stuff...) 4397 // wish we could pass arrays directly (cough) 4398 if(stuff.length == 2 && is(typeof(stuff[0]) == string[]) && 4399 is(typeof(stuff[1]) == size_t[])){ 4400 enum string[] MixinAliases = stuff[0]; 4401 enum size_t[] Indices = stuff[1]; 4402 } 4403 4404 4405 /++ 4406 A multi_index node. Holds the value of a single element, 4407 plus per-node headers of each index, if any. 4408 The headers are all mixed in in the same scope. To prevent 4409 naming conflicts, a header field must be accessed with the number 4410 of its index. 4411 Example: 4412 ---- 4413 alias MNode!(IndexedBy!(Sequenced!(), Sequenced!(), OrderedUnique!()), int) Node; 4414 Node* n1 = new Node(); 4415 Node* n2 = new Node(); 4416 n1.index!0 .next = n2; 4417 n2.index!0 .prev = n1; 4418 n1.index!1 .prev = n2; 4419 n2.index!1 .next = n1; 4420 n1.index!2 .left = n2; 4421 ---- 4422 +/ 4423 struct MNode(_ThisContainer, IndexedBy, Allocator, Signals, Value, ValueView) { 4424 alias _ThisContainer ThisContainer; 4425 static if(MutableValue!(MNode, Value)) { 4426 Value value; 4427 }else{ 4428 // do a dumb tail const sort of thing 4429 struct Capsule { 4430 Value value; 4431 } 4432 Capsule* val_ptr; 4433 4434 @property Value value() pure inout { return val_ptr.value; } 4435 @property void value(Value v) { 4436 if(val_ptr != null) { 4437 Allocator.deallocate(val_ptr); 4438 } 4439 val_ptr = Allocator.allocate!(Capsule)(1); 4440 Capsule c = Capsule(v); 4441 move(c, *val_ptr); 4442 } 4443 this(Value val) { 4444 this.value = val; 4445 } 4446 ~this() { 4447 if(val_ptr != null) { 4448 Allocator.deallocate(val_ptr); 4449 val_ptr = null; 4450 } 4451 } 4452 } 4453 4454 static if(Signals.AllSignals.length > 0) { 4455 // notifications need to go somewhere 4456 ThisContainer container; 4457 4458 /// generate slots 4459 template ForEachSignal(size_t i) { 4460 static if(i < Signals.Mixin2Index.length) { 4461 alias Signals.Mixin2Index[i] Mixin2Index; 4462 4463 template ForEachIndex2(size_t j) { 4464 static if(j < Mixin2Index.Indices.length) { 4465 enum result = Replace!(q{ 4466 if(!container.index!($i)._NotifyChange(&this)) { 4467 goto denied; 4468 } 4469 }, "$i", Mixin2Index.Indices[j]) ~ ForEachIndex2!(j+1).result; 4470 }else{ 4471 enum result = ""; 4472 } 4473 } 4474 enum stuff = Replace!(q{ 4475 void slot$i(){ 4476 $x 4477 return; 4478 denied: enforce(false, "todo: put a useful message in here"); 4479 } 4480 }, "$i", i, "$x", ForEachIndex2!(0).result); 4481 }else{ 4482 enum stuff = ""; 4483 } 4484 } 4485 4486 enum signal_stuff = ForEachSignal!(0).stuff; 4487 mixin(signal_stuff); 4488 } 4489 4490 4491 template ForEachIndex(size_t N,L...){ 4492 static if(L.length > 0){ 4493 enum indexN = Replace!("index%s","%s", N); 4494 //alias L[0] L0; 4495 enum result = 4496 Replace!(q{ 4497 alias IndexedBy.Indices[$N] L$N; 4498 alias L$N.Inner!(ThisContainer, typeof(this),Value,ValueView,$N, Allocator) M$N; 4499 mixin M$N.NodeMixin!(M$N.NodeTuple) index$N; 4500 template index(size_t n) if(n == $N){ alias index$N index; } 4501 }, "$N", N) ~ 4502 ForEachIndex!(N+1, L[1 .. $]).result; 4503 }else{ 4504 enum result = ""; 4505 } 4506 } 4507 4508 enum stuff = ForEachIndex!(0, IndexedBy.Indices).result; 4509 mixin(stuff); 4510 } 4511 4512 struct ConstView{} 4513 struct MutableView{} 4514 4515 template IsIndexedBy(alias x) { 4516 // test x.stringof in case we have a bare Sequenced!() or somesuch 4517 enum bool IsIndexedBy = __traits(compiles, x.stringof) && 4518 x.stringof.startsWith("IndexedBy!") && 4519 __traits(compiles, x.List); 4520 } 4521 4522 template IsIndex(alias x) { 4523 enum bool IsIndex = __traits(hasMember, x, "Inner"); 4524 } 4525 4526 int IndexedByCount(X...)() { 4527 int r = 0; 4528 foreach(i,x; X){ 4529 static if(__traits(compiles,IsIndexedBy!x) && IsIndexedBy!x) { 4530 r++; 4531 } 4532 } 4533 return r; 4534 } 4535 size_t[] IndexedByAllIndices(X)() { 4536 // erm. returns list of nonindices in IndexedBy 4537 size_t[] res = []; 4538 foreach(i,x; X.List){ 4539 static if(!IsIndex!x && 4540 (i == 0 || !IsIndex!(X.List[i-1]) || !is(typeof(x) == string))) { 4541 res ~= i; 4542 } 4543 } 4544 return res; 4545 } 4546 4547 4548 template FindIndexedBy(Args...) { 4549 static if(IsIndexedBy!(Args[0])) { 4550 alias Args[0] FindIndexedBy; 4551 }else { 4552 alias FindIndexedBy!(Args[1 .. $]) FindIndexedBy; 4553 } 4554 } 4555 4556 template IsValueChangedSlots(alias X) { 4557 enum bool IsValueChangedSlots = __traits(compiles, X.stringof) && 4558 X.stringof.startsWith("ValueChangedSlots!"); 4559 } 4560 4561 int ValueChangedSlotsCount(Args...)() { 4562 int r = 0; 4563 foreach(i,x; Args){ 4564 static if(__traits(compiles,IsValueChangedSlots!x) && IsValueChangedSlots!x) { 4565 r++; 4566 } 4567 } 4568 return r; 4569 } 4570 4571 template FindValueChangedSlots(Args...) { 4572 static if(Args.length == 0) { 4573 alias ValueChangedSlots!() FindValueChangedSlots; 4574 }else static if(IsValueChangedSlots!(Args[0])) { 4575 alias Args[0] FindValueChangedSlots; 4576 }else { 4577 alias FindValueChangedSlots!(Args[1 .. $]) FindValueChangedSlots; 4578 } 4579 } 4580 4581 template IsConstnessView(alias T) { 4582 enum bool IsConstnessView = is(T == MutableView) || is(T == ConstView); 4583 } 4584 4585 int ConstnessViewCount(Args...)() { 4586 int r = 0; 4587 foreach(i,x; Args){ 4588 static if(__traits(compiles,IsConstnessView!x) && IsConstnessView!x) { 4589 r++; 4590 } 4591 } 4592 return r; 4593 } 4594 4595 template FindConstnessView(Args...) { 4596 static if(Args.length == 0) { 4597 alias ConstView FindConstnessView; 4598 }else static if(IsConstnessView!(Args[0])) { 4599 alias Args[0] FindConstnessView; 4600 }else { 4601 alias FindConstnessView!(Args[1 .. $]) FindConstnessView; 4602 } 4603 } 4604 4605 int AllocatorCount(Args...)() { 4606 int r = 0; 4607 foreach(i,x; Args){ 4608 static if(__traits(compiles, IsAllocator!x) && IsAllocator!x) { 4609 r++; 4610 } 4611 } 4612 return r; 4613 } 4614 4615 template FindAllocator(Args...) { 4616 static if(Args.length == 0) { 4617 alias GCAllocator FindAllocator; 4618 }else static if(IsAllocator!(Args[0])) { 4619 alias Args[0] FindAllocator; 4620 }else { 4621 alias FindAllocator!(Args[1 .. $]) FindAllocator; 4622 } 4623 } 4624 4625 size_t[] IndexGarbage(Args...)() { 4626 size_t[] res = []; 4627 foreach(i,x; Args){ 4628 static if(!(__traits(compiles,IsIndexedBy!x) && IsIndexedBy!x) && 4629 !(__traits(compiles,IsValueChangedSlots!x) && IsValueChangedSlots!x) && 4630 !(__traits(compiles,IsConstnessView!x) && IsConstnessView!x) && 4631 !(__traits(compiles,IsAllocator!x) && IsAllocator!x)) { 4632 res ~= i; 4633 } 4634 } 4635 return res; 4636 } 4637 4638 4639 struct ComparisonEx(alias _key, alias _less) { 4640 alias _less _less_; 4641 alias binaryFun!_less less; 4642 alias unaryFun!_key key; 4643 } 4644 4645 struct DefaultComparison(alias _less) { 4646 alias _less less; 4647 } 4648 4649 template MultiCompare(F...) { 4650 template NormComps(size_t i = 0, alias Dflt = "a<b") { 4651 static if(i == F.length) { 4652 alias TypeTuple!() NormComps; 4653 }else { 4654 static if(F[i].stringof.startsWith("DefaultComparison!") && 4655 __traits(compiles, F[i].less)) { 4656 alias NormComps!(i+1, F[i].less) NormComps; 4657 }else{ 4658 static if (F[i].stringof.startsWith("ComparisonEx!") && 4659 __traits(compiles, F[i].less) && 4660 __traits(compiles, F[i].key)) { 4661 alias F[i] Cmp; 4662 }else { 4663 alias ComparisonEx!(F[i], Dflt) Cmp; 4664 } 4665 alias TypeTuple!(Cmp, NormComps!(i+1, Dflt)) NormComps; 4666 } 4667 } 4668 } 4669 4670 alias NormComps!() Comps; 4671 4672 bool MultiCompare(T)(T a, T b) { 4673 foreach(i, cmp; Comps) { 4674 auto a1 = cmp.key(a); 4675 auto b1 = cmp.key(b); 4676 auto less = cmp.less(a1,b1); 4677 if(less) return true; 4678 auto gtr = cmp.less(b1,a1); 4679 if(gtr) return false; 4680 static if(i == Comps.length-1) { 4681 return false; 4682 } 4683 } 4684 assert(0); 4685 } 4686 } 4687 4688 template IsCompatibleLess(Less, Key, CKey) { 4689 enum bool IsCompatibleLess = is(typeof({ 4690 Less less; 4691 auto c = CKey.init; 4692 auto k = Key.init; 4693 less.cc_less(c,c); 4694 less.kc_less(k,c); 4695 less.ck_less(c,k); 4696 })); 4697 } 4698 4699 struct CriterionFromKey(MultiIndex, size_t index, 4700 alias CompatibleKeyFromKey, 4701 alias CompatibleLess = "a<b") { 4702 alias binaryFun!CompatibleLess less; 4703 alias MultiIndex.index!(index).key key; 4704 alias MultiIndex.index!(index).KeyType KeyType; 4705 alias unaryFun!CompatibleKeyFromKey ckey; 4706 alias typeof(ckey(MultiIndex.ValueView.init)) CompatibleKeyType; 4707 4708 static: 4709 bool kc_less(KeyType a, CompatibleKeyType b) { 4710 return less(ckey(a),b); 4711 } 4712 bool ck_less(CompatibleKeyType a, KeyType b) { 4713 return less(a, ckey(b)); 4714 } 4715 bool cc_less(CompatibleKeyType a, CompatibleKeyType b) { 4716 return less(a, b); 4717 } 4718 } 4719 4720 // error sinks 4721 4722 class MultiIndexContainer(Value, Args...) 4723 if(IndexedByCount!(Args)() != 1) { 4724 static assert (IndexedByCount!(Args)() > 0, "MultiIndexContainer requires indices to be wrapped with IndexedBy!(..)"); 4725 static assert (IndexedByCount!(Args)() < 2, "MultiIndexContainer takes exactly one IndexedBy!(..)"); 4726 } 4727 4728 class MultiIndexContainer(Value, Args...) 4729 if(FindIndexedBy!Args .List.length == 0) { 4730 static assert(false, "MultiIndexContainer requires at least one index"); 4731 } 4732 4733 class MultiIndexContainer(Value, Args...) 4734 if(IndexedByAllIndices!(FindIndexedBy!Args)().length != 0) { 4735 import std.conv; 4736 alias FindIndexedBy!Args IndexedBy; 4737 enum lst = IndexedByAllIndices!(IndexedBy)(); 4738 pragma(msg, "IndexedBy contains non-index at indices"); 4739 mixin template Frch(size_t i) { 4740 static if(i < lst.length) { 4741 static if(__traits(compiles, IndexedBy.List[lst[i]].stringof)) { 4742 pragma(msg, to!string(lst[i]) ~ ": " ~ IndexedBy.List[lst[i]].stringof); 4743 }else{ 4744 pragma(msg, to!string(lst[i])); 4745 } 4746 mixin Frch!(i+1); 4747 } 4748 } 4749 mixin Frch!(0); 4750 static assert(false); 4751 // @@@ PHOBOS ISSUE 8320 @@@ 4752 /+ 4753 static assert (false, 4754 Replace!(/*"IndexedBy contains non-index at indices*/" %s", "%s", 4755 IndexedByAllIndices!(FindIndexedBy!Args)())); 4756 +/ 4757 } 4758 4759 class MultiIndexContainer(Value, Args...) 4760 if(ValueChangedSlotsCount!(Args)() > 1) { 4761 static assert(false, "Multiple ValueChangedSlots specifications are not allowed"); 4762 } 4763 4764 class MultiIndexContainer(Value, Args...) 4765 if(ConstnessViewCount!(Args)() > 1) { 4766 static assert(false, "Multiple Constness Views are not allowed"); 4767 } 4768 4769 class MultiIndexContainer(Value, Args...) 4770 if(AllocatorCount!(Args)() > 1) { 4771 static assert(false, "Multiple allocators are not allowed"); 4772 } 4773 4774 class MultiIndexContainer(Value, Args...) 4775 if(IndexGarbage!(Args)().length != 0) { 4776 import std.conv; 4777 enum lst = IndexGarbage!(Args)(); 4778 pragma(msg, "MultiIndexContainer unknown arguments at"); 4779 mixin template Frch(size_t i) { 4780 static if(i < lst.length) { 4781 static if(__traits(compiles, Args[lst[i]].stringof)) { 4782 pragma(msg, to!string(lst[i]) ~ ": " ~ Args[lst[i]].stringof); 4783 }else{ 4784 pragma(msg, to!string(lst[i])); 4785 } 4786 mixin Frch!(i+1); 4787 } 4788 } 4789 mixin Frch!(0); 4790 static assert(false); 4791 // @@@ PHOBOS ISSUE 8320 @@@ 4792 /+ 4793 static assert (false, 4794 Replace!(/*"IndexedBy contains non-index at indices*/" %s", "%s", 4795 IndexedByAllIndices!(FindIndexedBy!Args)())); 4796 +/ 4797 } 4798 4799 template MutableValue(Node, Value) { 4800 enum MutableValue = __traits(compiles, { Value value; value = Value.init; }); 4801 } 4802 4803 template _AllUnique(Thing...) { 4804 enum _AllUnique = NoDuplicates!Thing .length == Thing.length; 4805 } 4806 class MultiIndexContainer(Value, Args...) 4807 if(!_AllUnique!(FindIndexedBy!Args .Names)) { 4808 static assert(false, "duplicates!"); 4809 } 4810 4811 4812 4813 // end error sinks 4814 4815 /++ 4816 The container. Don't call any index methods from this container directly; use 4817 a reference to an individual index, which can be obtained via 4818 --- 4819 container.get_index!N 4820 --- 4821 or 4822 --- 4823 container.name 4824 --- 4825 for named indices. 4826 4827 If you have a range into an index of this container, you can convert it to a 4828 range of index N via 4829 --- 4830 container.to_range!N(range) 4831 --- 4832 This is equivalent to c++ multi_index' project 4833 +/ 4834 class MultiIndexContainer(Value, Args...) 4835 if(IndexedByCount!(Args)() == 1 && 4836 FindIndexedBy!Args .List.length != 0 && 4837 IndexedByAllIndices!(FindIndexedBy!Args)().length == 0 && 4838 _AllUnique!(FindIndexedBy!Args .Names) && 4839 ValueChangedSlotsCount!(Args)() <= 1 && 4840 ConstnessViewCount!(Args)() <= 1 && 4841 AllocatorCount!(Args)() <= 1 && 4842 IndexGarbage!(Args)().length == 0) { 4843 4844 alias FindIndexedBy!Args IndexedBy; 4845 // @@@ DMD ISSUE 6475 @@@ following gives forward reference error 4846 //alias FindValueChangedSlots!Args .Inner!(IndexedBy) NormSignals; 4847 alias typeof(FindValueChangedSlots!Args .Inner!(IndexedBy).exposeType()) NormSignals; 4848 alias FindConstnessView!Args ConstnessView; 4849 alias FindAllocator!Args Allocator; 4850 4851 static if(is(ConstnessView == ConstView)){ 4852 alias const(Value) ValueView; 4853 }else static if(is(ConstnessView == MutableView)){ 4854 alias Value ValueView; 4855 }else static assert(false); 4856 alias MNode!(typeof(this), IndexedBy,Allocator,NormSignals,Value, ValueView) ThisNode; 4857 4858 /+ 4859 template IndexedByList0(size_t i, stuff...){ 4860 static if(i < IndexedBy.Indices.length){ 4861 alias typeof(IndexedBy.Indices[i].Inner!(typeof(this), ThisNode, Value, i).exposeType()) x; 4862 alias IndexedByList0!(i+1, stuff, x).result result; 4863 }else{ 4864 alias stuff result; 4865 } 4866 } 4867 4868 alias IndexedByList0!(0).result IndexedByList; 4869 +/ 4870 4871 size_t node_count; 4872 4873 template ForEachCtorMixin(size_t i){ 4874 static if(i < IndexedBy.Indices.length){ 4875 static if(is(typeof(IndexedBy.Indices[i].Inner!(typeof(this), 4876 ThisNode,Value,ValueView,i,Allocator).IndexCtorMixin))){ 4877 enum result = IndexedBy.Indices[i].Inner!(typeof(this), 4878 ThisNode,Value, ValueView,i,Allocator).IndexCtorMixin ~ 4879 ForEachCtorMixin!(i+1).result; 4880 }else enum result = ForEachCtorMixin!(i+1).result; 4881 }else enum result = ""; 4882 } 4883 4884 // private to help avoid people accidentally using `new`, 4885 // can't be @disable because then emplace doesn't work 4886 // no point calling initialize because emplace doesn't call this 4887 private this(){ 4888 } 4889 4890 void initialize(){ 4891 mixin(ForEachCtorMixin!(0).result); 4892 } 4893 4894 void dealloc(ThisNode* node){ 4895 // disconnect signals from slots 4896 foreach(i, x; NormSignals.Mixin2Index){ 4897 foreach(j, malias; OU!(string).arr2tuple!(x.MixinAliases)){ 4898 static if(malias == ""){ 4899 mixin(Replace!(q{ 4900 node.value.disconnect(&node.slot$i); 4901 }, "$i", i)); 4902 }else{ 4903 mixin(Replace!(q{ 4904 node.value.$alias.disconnect(&node.slot$i); 4905 }, "$i", i,"$alias", malias)); 4906 } 4907 } 4908 } 4909 object.destroy(node); 4910 Allocator.deallocate(node); 4911 } 4912 4913 static auto create(){ 4914 import std.conv : emplace; 4915 auto c = cast(MultiIndexContainer) Allocator.allocate!void(__traits(classInstanceSize, MultiIndexContainer)); 4916 c.emplace(); 4917 c.initialize(); 4918 return c; 4919 } 4920 4921 void release(MultiIndexContainer c){ 4922 Allocator.deallocate(cast(void*) c); 4923 } 4924 4925 template ForEachIndex(size_t N,L...){ 4926 static if(L.length > 0){ 4927 enum result = 4928 Replace!(q{ 4929 alias IndexedBy.Indices[$N] L$N; 4930 alias L$N.Inner!(typeof(this),ThisNode,Value, ValueView,$N,Allocator) M$N; 4931 mixin M$N.IndexMixin!(M$N.IndexTuple) index$N; 4932 template index(size_t n) if(n == $N){ alias index$N index; } 4933 struct Index$N{ 4934 MultiIndexContainer _this; 4935 4936 // grr opdispatch not handle this one 4937 auto opSlice(T...)(T ts){ 4938 return _this.index!($N).opSlice(ts); 4939 } 4940 4941 // grr opdispatch not handle this one 4942 auto opIndex(T...)(T ts){ 4943 return _this.index!($N).opIndex(ts); 4944 } 4945 4946 // grr opdispatch not handle this one 4947 auto opIndexAssign(T...)(T ts){ 4948 return _this.index!($N).opIndexAssign(ts); 4949 } 4950 4951 // grr opdispatch not handle this one 4952 auto opBinaryRight(string op, T...)(T ts){ 4953 return _this.index!($N).opBinaryRight!(op)(ts); 4954 } 4955 4956 // grr opdispatch not handle this one 4957 auto bounds(string bs = "[]", T)(T t1, T t2){ 4958 return _this.index!($N).bounds!(bs,T)(t1,t2); 4959 } 4960 // grr opdispatch not handle this one 4961 auto bounds(V, string bs = "[]", T)(T t1, T t2){ 4962 return _this.index!($N).cbounds!(V,bs,T)(t1,t2); 4963 } 4964 // grr opdispatch not handle this one 4965 auto cEqualRange(L, K)(K k) 4966 { 4967 return _this.index!($N).cEqualRange!(L, K).equalRange(k); 4968 } 4969 // grr opdispatch not handle this one 4970 auto cEqualRange(L, K)(K k) const 4971 { 4972 return _this.index!($N).cEqualRange!(L, K).equalRange(k); 4973 } 4974 4975 auto opDispatch(string s, T...)(T args){ 4976 mixin("return _this.index!($N)."~s~"(args);"); 4977 } 4978 } 4979 @property Index$N get_index(size_t n)() if(n == $N){ 4980 return Index$N(this); 4981 } 4982 }, "$N", N) ~ 4983 ForEachIndex!(N+1, L[1 .. $]).result; 4984 }else{ 4985 enum result = ""; 4986 } 4987 } 4988 4989 enum stuff = (ForEachIndex!(0, IndexedBy.Indices).result); 4990 mixin(stuff); 4991 4992 template ForEachNamedIndex(size_t i){ 4993 static if(i >= IndexedBy.Names.length) { 4994 enum result = ""; 4995 }else { 4996 enum result = Replace!(q{ 4997 alias get_index!$N $name; 4998 }, "$N", IndexedBy.NameIndices[i], "$name", IndexedBy.Names[i]) ~ 4999 ForEachNamedIndex!(i+1).result; 5000 } 5001 } 5002 5003 enum named_stuff = ForEachNamedIndex!0 .result; 5004 mixin(named_stuff); 5005 5006 5007 template ForEachCheckInsert(size_t i, size_t N){ 5008 static if(i < IndexedBy.Indices.length){ 5009 static if(i != N && __traits(hasMember, index!i,"_DenyInsertion")){ 5010 enum result = (Replace!(q{ 5011 ThisNode* aY; 5012 bool bY = index!(Y)._DenyInsertion(node,aY); 5013 if (bY) goto denied; 5014 }, "Y", i)) ~ ForEachCheckInsert!(i+1, N).result; 5015 }else enum result = ForEachCheckInsert!(i+1, N).result; 5016 }else enum result = ""; 5017 } 5018 5019 template ForEachDoInsert(size_t i, size_t N){ 5020 static if(i < IndexedBy.Indices.length){ 5021 static if(i != N){ 5022 import std.traits; 5023 static if(ParameterTypeTuple!(index!i._Insert).length == 2){ 5024 enum result = Replace!(q{ 5025 index!(Y)._Insert(node,aY); 5026 }, "Y", i) ~ ForEachDoInsert!(i+1,N).result; 5027 }else{ 5028 enum result = Replace!(q{ 5029 index!(Y)._Insert(node); 5030 }, "Y", i) ~ ForEachDoInsert!(i+1,N).result; 5031 } 5032 }else enum result = ForEachDoInsert!(i+1, N).result; 5033 }else enum result = ""; 5034 } 5035 5036 ThisNode* _InsertAllBut(size_t N)(Value value){ 5037 ThisNode* node = Allocator.allocate!(ThisNode)(1); 5038 static if(MutableValue!(ThisNode, Value)) { 5039 node.value = value; 5040 }else{ 5041 auto t = ThisNode(value); 5042 move(t, *node); 5043 } 5044 5045 // connect signals to slots 5046 foreach(i, x; NormSignals.Mixin2Index){ 5047 static if(i == 0) node.container = this; 5048 5049 foreach(j, malias; OU!(string).arr2tuple!(x.MixinAliases)){ 5050 static if(malias == ""){ 5051 mixin(Replace!(q{ 5052 node.value.connect(&node.slot$i); 5053 }, "$i", i)); 5054 }else{ 5055 mixin(Replace!(q{ 5056 node.value.$alias.connect(&node.slot$i); 5057 }, "$i", i,"$alias", malias)); 5058 } 5059 } 5060 } 5061 5062 // check with each index about insert op 5063 /+ 5064 foreach(i, x; IndexedByList){ 5065 /+ 5066 static if(i != N && is(typeof({ ThisNode* p; 5067 index!i._DenyInsertion(p,p);}))){ 5068 enum result = (Replace!(q{ 5069 ThisNode* aY; 5070 bool bY = index!(Y)._DenyInsertion(node,aY); 5071 if (bY) goto denied; 5072 }, "Y", i)) ~ ForEachCheckInsert!(i+1, N).result; 5073 }kelse enum result = ForEachCheckInsert!(i+1, N).result; 5074 +/ 5075 } 5076 +/ 5077 mixin(ForEachCheckInsert!(0, N).result); 5078 // perform insert op on each index 5079 mixin(ForEachDoInsert!(0, N).result); 5080 node_count++; 5081 return node; 5082 denied: 5083 return null; 5084 } 5085 5086 template ForEachDoRemove(size_t i, size_t N){ 5087 static if(i < IndexedBy.Indices.length){ 5088 static if(i != N){ 5089 enum result = Replace!(q{ 5090 index!(Y)._Remove(node); 5091 }, "Y", i) ~ ForEachDoRemove!(i+1,N).result; 5092 }else enum result = ForEachDoRemove!(i+1, N).result; 5093 }else enum result = ""; 5094 } 5095 5096 // disattach node from all indices except index N 5097 void _RemoveAllBut(size_t N)(ThisNode* node){ 5098 mixin(ForEachDoRemove!(0, N).result); 5099 node_count --; 5100 } 5101 5102 // disattach node from all indices. 5103 // @@@BUG@@@ cannot pass length directly to _RemoveAllBut 5104 auto _RemoveAll(size_t N = size_t.max)(ThisNode* node){ 5105 static if(N == size_t.max) { 5106 enum _grr_bugs = IndexedBy.Indices.length; 5107 _RemoveAllBut!(_grr_bugs)(node); 5108 }else { 5109 _RemoveAllBut!N(node); 5110 auto res = index!N._Remove(node); 5111 } 5112 dealloc(node); 5113 5114 static if(N != size_t.max) { 5115 return res; 5116 } 5117 } 5118 5119 template ForEachIndexPosition(size_t i){ 5120 static if(i < IndexedBy.Indices.length){ 5121 static if(is(typeof(index!i ._NodePosition((ThisNode*).init)))){ 5122 enum variableDeclarations = Replace!(q{ 5123 ThisNode* node$i; 5124 }, "$i", i) ~ ForEachIndexPosition!(i+1).variableDeclarations; 5125 enum getNodePositions = Replace!(q{ 5126 auto pos$i = index!$i ._NodePosition(node); 5127 }, "$i", i) ~ ForEachIndexPosition!(i+1).getNodePositions; 5128 enum gotoDeniedOnInvalid = Replace!(q{ 5129 if(!index!$i ._PositionFixable(node, pos$i, node$i)) 5130 goto denied; 5131 }, "$i", i) ~ ForEachIndexPosition!(i+1).gotoDeniedOnInvalid; 5132 enum fixupIndices = Replace!(q{ 5133 index!$i ._FixPosition(node, pos$i, node$i); 5134 }, "$i", i) ~ ForEachIndexPosition!(i+1).fixupIndices; 5135 }else{ 5136 enum getNodePositions = ForEachIndexPosition!(i+1).getNodePositions; 5137 enum variableDeclarations = ForEachIndexPosition!(i+1).variableDeclarations; 5138 enum gotoDeniedOnInvalid = ForEachIndexPosition!(i+1).gotoDeniedOnInvalid; 5139 enum fixupIndices = ForEachIndexPosition!(i+1).fixupIndices; 5140 } 5141 }else{ 5142 enum getNodePositions = ""; 5143 enum variableDeclarations = ""; 5144 enum gotoDeniedOnInvalid = ""; 5145 enum fixupIndices = ""; 5146 } 5147 } 5148 5149 bool _Replace(ThisNode* node, Value value){ 5150 mixin(ForEachIndexPosition!0 .variableDeclarations); 5151 mixin(ForEachIndexPosition!0 .getNodePositions); 5152 Value old = node.value; 5153 node.value = value; 5154 { 5155 mixin(ForEachIndexPosition!0 .gotoDeniedOnInvalid); 5156 mixin(ForEachIndexPosition!0 .fixupIndices); 5157 } 5158 return true; 5159 denied: 5160 node.value = old; 5161 return false; 5162 } 5163 5164 /* 5165 Perform mod on node.value and perform any necessary fixups to this container's 5166 indices. mod may be of the form void mod(ref Value), in which case mod directly modifies the value in node. If the result of mod violates any index' invariant, 5167 the node is removed from the container. 5168 Preconditions: mod is a callable of the form void mod(ref Value) 5169 Complexity: $(BIGOH m(n)) 5170 */ 5171 void _Modify(Modifier)(ThisNode* node, Modifier mod){ 5172 mixin(ForEachIndexPosition!0 .variableDeclarations); 5173 mixin(ForEachIndexPosition!0 .getNodePositions); 5174 mod(node.value); 5175 mixin(ForEachIndexPosition!0 .gotoDeniedOnInvalid); 5176 mixin(ForEachIndexPosition!0 .fixupIndices); 5177 return; 5178 denied: 5179 _RemoveAll(node); 5180 } 5181 5182 template ForEachClear(size_t i){ 5183 static if(i < IndexedBy.Indices.length){ 5184 enum string result = Replace!(q{ 5185 index!$i ._ClearIndex(); 5186 }, "$i", i) ~ ForEachClear!(i+1).result; 5187 }else enum string result = ""; 5188 } 5189 5190 void _Clear(){ 5191 auto r = index!0 .opSlice(); 5192 while(!r.empty){ 5193 ThisNode* node = r.front_node; 5194 r.popFront(); 5195 dealloc(node); 5196 } 5197 mixin(ForEachClear!0 .result); 5198 node_count = 0; 5199 } 5200 5201 template ForEachCheck(size_t i){ 5202 static if(i < IndexedBy.Indices.length){ 5203 enum result = Replace!(q{ 5204 index!($i)._Check(); 5205 },"$i", i) ~ ForEachCheck!(i+1).result; 5206 }else{ 5207 enum result = ""; 5208 } 5209 } 5210 5211 void check(){ 5212 mixin(ForEachCheck!(0).result); 5213 } 5214 5215 template ForEachAlias(size_t N,size_t index, alias X){ 5216 alias X.Inner!(ThisNode,Value, ValueView,N,Allocator).Index!() Index; 5217 static if(Index.container_aliases.length > index){ 5218 enum aliashere = NAliased!(Index.container_aliases[index][0], 5219 Index.container_aliases[index][1], N); 5220 enum result = aliashere ~ "\n" ~ ForEachAlias!(N,index+1, X).result; 5221 }else{ 5222 enum result = ""; 5223 } 5224 } 5225 5226 5227 @property auto to_range(size_t N, Range0)(Range0 r) 5228 if(RangeIndexNo!Range0 != -1){ 5229 static if(N == RangeIndexNo!Range0){ 5230 return r; 5231 }else{ 5232 return index!N.fromNode(r.front_node); 5233 } 5234 } 5235 5236 private template RangeIndexNo(R){ 5237 template IndexNoI(size_t i){ 5238 static if(i == IndexedBy.Indices.length){ 5239 enum size_t IndexNoI = -1; 5240 }else static if(index!(i).IsMyRange!(R)){ 5241 enum size_t IndexNoI = i; 5242 }else{ 5243 enum IndexNoI = IndexNoI!(i+1); 5244 } 5245 } 5246 enum size_t RangeIndexNo = IndexNoI!(0); 5247 } 5248 } 5249 5250 /// simple Slot implementation 5251 mixin template Slots() { 5252 void delegate()[] slots; 5253 5254 void connect(void delegate() slot){ 5255 slots ~= slot; 5256 } 5257 void disconnect(void delegate() slot){ 5258 size_t index = slots.length; 5259 foreach(i, slot1; slots){ 5260 if(slot is slot1){ 5261 index = i; 5262 moveAll(slots[i+1 .. $], slots[i .. $-1]); 5263 slots.length-=1; 5264 break; 5265 } 5266 } 5267 } 5268 void emit(){ 5269 foreach(slot; slots){ 5270 slot(); 5271 } 5272 } 5273 } 5274 5275 import std.stdio; 5276 5277 int[] arr(Range)(Range r){ 5278 int[] result = new int[](r.length); 5279 size_t j = 0; 5280 foreach(e; r){ 5281 result[j++] = e; 5282 } 5283 return result; 5284 } 5285 5286 struct S1{ 5287 string _s; 5288 int _i; 5289 void delegate() slot = null; 5290 5291 @property string s()const{ return _s;} 5292 @property void s(string s_){ _s = s_; emit(); } 5293 5294 @property int i()const{ return _i;} 5295 @property void i(int i_){ _i = i_; } 5296 5297 void emit(){ 5298 if (slot) slot(); 5299 } 5300 5301 void connect(void delegate() slot){ this.slot = slot; } 5302 void disconnect(void delegate() slot){ 5303 if(this.slot is slot) this.slot = null; 5304 } 5305 5306 string toString0()const{ 5307 return format("%s: %s", s, i); 5308 } 5309 } 5310 5311 version(TestMultiIndex) 5312 void main(){ 5313 alias MultiIndexContainer!(S1, 5314 IndexedBy!(Sequenced!(), 5315 OrderedUnique!("a.s") 5316 ), 5317 ValueChangedSlots!(ValueSignal!(1))) C; 5318 5319 C i = C.create(); 5320 5321 alias MultiIndexContainer!(const(S1), 5322 IndexedBy!(OrderedUnique!("a.s")) 5323 ) CCC; 5324 CCC c2 = new CCC; 5325 c2.insert(cast(const)S1("abc", 22)); 5326 pragma(msg, typeof(c2[])); 5327 pragma(msg, ElementType!(typeof(c2[]))); 5328 foreach(const(S1) thing; c2[]) { 5329 } 5330 5331 auto pr = PSR(c2[]); 5332 c2.replace(pr.front, const(S1)("def", 44)); 5333 }