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 new(size_t sz) { 4043 void* p = Allocator.allocate!void(sz); 4044 return p; 4045 } 4046 delete(void* p) { 4047 Allocator.deallocate(p); 4048 } 4049 4050 @property ValueView v() { 4051 return node.value; 4052 } 4053 4054 private: 4055 bool obliterated = true; 4056 MNode* _node; 4057 4058 this(MNode* _node) { 4059 obliterated = false; 4060 this._node = _node; 4061 } 4062 4063 @property node() { 4064 enforce(!obliterated, 4065 "this position no longer exists in container"); 4066 return _node; 4067 } 4068 } 4069 4070 auto PSR(Range)(Range rng) 4071 { 4072 alias Position!(typeof(*rng.front_node)) Pos; 4073 4074 static struct PositionRange { 4075 4076 Range source; 4077 4078 @property empty() { 4079 return source.empty(); 4080 } 4081 4082 @property Pos front() { 4083 return new Pos(source.front_node); 4084 } 4085 4086 void popFront() { 4087 source.popFront(); 4088 } 4089 4090 static if(isBidirectionalRange!Range) { 4091 @property Pos back() { 4092 return new Pos(source.back_node); 4093 } 4094 4095 void popBack() { 4096 source.popBack(); 4097 } 4098 } 4099 4100 static if(isForwardRange!Range) { 4101 @property save() { 4102 return PositionRange(source.save()); 4103 } 4104 } 4105 4106 static if(isRandomAccessRange!Range) { 4107 auto opIndex(size_t i) { 4108 return source.nth_node(i); 4109 } 4110 4111 @property length() { 4112 return source.length; 4113 } 4114 4115 @property front(typeof(source.front_node) n) { 4116 source.front_node = n; 4117 } 4118 4119 @property opSlice(size_t a, size_t b) { 4120 return PositionRange(source[a .. b]); 4121 } 4122 } 4123 } 4124 4125 return PositionRange(rng); 4126 } 4127 4128 struct IndexedBy(L...) 4129 { 4130 template _inner(size_t index, List...) { 4131 static if(List.length <= 1) { 4132 alias TypeTuple!() names; 4133 alias TypeTuple!() name_indices; 4134 alias TypeTuple!(List) indices; 4135 }else static if(IsIndex!(List[0]) && is(typeof(List[1]) == string)) { 4136 alias _inner!(index+1,List[2 .. $]) next; 4137 alias TypeTuple!(List[1], next.names) names; 4138 alias TypeTuple!(index, next.name_indices) name_indices; 4139 alias TypeTuple!(List[0], next.indices) indices; 4140 }else { 4141 alias _inner!(index+1,List[1 .. $]) next; 4142 alias next.names names; 4143 alias next.name_indices name_indices; 4144 alias TypeTuple!(List[0], next.indices) indices; 4145 } 4146 } 4147 4148 alias _inner!(0, L).names Names; 4149 alias _inner!(0, L).name_indices NameIndices; 4150 alias _inner!(0, L).indices Indices; 4151 alias L List; 4152 } 4153 4154 template GetMixinAlias(valueSignal){ 4155 alias valueSignal.MixinAlias GetMixinAlias; 4156 } 4157 4158 // todo - find better name 4159 template OU(T){ 4160 template arr2tuple(stuff...){ 4161 static assert(is(typeof(stuff[0]) == T[])); 4162 4163 static if(stuff[0].length){ 4164 alias arr2tuple!(stuff[0][1 .. $], stuff[1 .. $], stuff[0][0]) arr2tuple; 4165 }else{ 4166 alias stuff[1 .. $] arr2tuple; 4167 } 4168 } 4169 4170 T[] orderedUniqueInsert(T[] x, T value){ 4171 size_t i; 4172 while(i < x.length && x[i] < value) i++; 4173 if(i < x.length && x[i] == value) return x; 4174 T[] ret = new T[](x.length+1); 4175 ret[0 .. i] = x[0 .. i]; 4176 ret[i] = value; 4177 ret[i+1 .. $] = x[i .. $]; 4178 return ret; 4179 } 4180 T[] TypeList2SortedArray(L...)(){ 4181 alias L List; 4182 T[] ret = []; 4183 foreach(T l; List){ 4184 ret = orderedUniqueInsert(ret, l); 4185 } 4186 return ret; 4187 } 4188 } 4189 4190 /** 4191 Specifies how to hook up value signals to indices. 4192 4193 A value type Value is a signal whenever Value supports the signal 4194 interface, ie $(BR) 4195 4196 value.connect(void delegate() slot) $(BR) 4197 value.disconnect(void delegate() slot) 4198 4199 and has the semantics that whenever value changes in a way that will cause 4200 its position in index to change or become invalid, a call is made to slot. 4201 The index will respond by fixing the position, or if that is not possible, 4202 by throwing an exception. 4203 4204 A value may contain multiple signals within different mixin aliases. If this 4205 is the case, the interface is 4206 4207 value.mixinAlias.connect(void delegate() slot) $(BR) 4208 value.mixinAlias.disconnect(void delegate() slot) 4209 4210 where mixinAlias is passed in as a string to each element of L. 4211 4212 Arguments must be instantiations of ValueSignal. 4213 4214 Signals to single indices can be specified by ValueSignal!(index[, mixinAlias]) 4215 4216 Signals to all indices can be specified by ValueSignal!("*"[, mixinAlias]) 4217 4218 A signal can be shared by multiple indices; however do not associate a signal 4219 to the same index more than once. 4220 */ 4221 4222 struct ValueChangedSlots(L...) { 4223 struct Inner(IndexedBy){ 4224 // by some forward referencing error or other, (issue 6475) 4225 // I can't seem to get a hold of inner in, but 4226 // typeof(exposeType()) seems to work. Desparate times require 4227 // desparate measures, I guess 4228 static exposeType(){ 4229 Inner i; 4230 return i; 4231 } 4232 enum N = IndexedBy.Indices.length; 4233 alias ExpandStarSignals!(IndexedBy,L) List; 4234 4235 4236 template GetIndex(valueSignal){ 4237 static if(__traits(compiles,valueSignal.Index)){ 4238 enum GetIndex = valueSignal.Index; 4239 }else{ 4240 static assert(__traits(compiles,valueSignal.Tag)); 4241 static if(valueSignal.Tag == "*") { 4242 static assert(false, "you bad, bad person"); 4243 }else { 4244 enum _TagIndex = staticIndexOf!(valueSignal.Tag, IndexedBy.Names); 4245 enum GetIndex = IndexedBy.NameIndices[_TagIndex]; 4246 } 4247 } 4248 } 4249 4250 enum string[] AllSignals = OU!(string).TypeList2SortedArray!( 4251 NoDuplicates!(staticMap!(GetMixinAlias, List)))(); 4252 4253 template FindIndices(string mixinAlias, size_t i, indices...) 4254 if(indices.length == 1 && is(typeof(indices[0]) == size_t[])){ 4255 static if(i < List.length){ 4256 static if(List[i].MixinAlias == mixinAlias){ 4257 enum index = GetIndex!(List[i]); 4258 static if(IndexedBy.Indices[index].BenefitsFromSignals){ 4259 enum size_t[] result = 4260 FindIndices!(mixinAlias, i+1, 4261 OU!(size_t).orderedUniqueInsert( 4262 indices[0], index)).result; 4263 }else{ 4264 enum size_t[] result = 4265 FindIndices!(mixinAlias, i+1, indices[0]).result; 4266 } 4267 }else{ 4268 enum size_t[] result = 4269 FindIndices!(mixinAlias, i+1, indices[0]).result; 4270 } 4271 }else{ 4272 enum size_t[] result = indices[0]; 4273 } 4274 } 4275 4276 template GenSets(size_t i, MI...){ 4277 static if (i < AllSignals.length){ 4278 enum mixinAlias = AllSignals[i]; 4279 enum indices = FindIndices!(mixinAlias,0,cast(size_t[])[]).result; 4280 template InsertIndices(size_t j){ 4281 static if(j < MI.length){ 4282 static if(MI[j].Indices == indices){ 4283 alias TypeTuple!(MI[0 .. j], 4284 Mixin2Indices!( 4285 OU!(string).orderedUniqueInsert( 4286 MI[j].MixinAliases,mixinAlias), 4287 indices 4288 ), 4289 MI[j+1 .. $]) InsertIndices; 4290 }else{ 4291 alias InsertIndices!(i+1) InsertIndices; 4292 } 4293 }else{ 4294 alias TypeTuple!(MI, Mixin2Indices!([mixinAlias], 4295 indices)) InsertIndices; 4296 } 4297 } 4298 4299 static if(indices.length > 0){ 4300 alias InsertIndices!(0) MI2; 4301 alias GenSets!(i+1, MI2).result result; 4302 }else{ 4303 alias GenSets!(i+1, MI).result result; 4304 } 4305 }else{ 4306 alias MI result; 4307 } 4308 } 4309 4310 // map { set of mixin aliases -> set of indices } 4311 // since we don't have maps or sets in ct (boo), 4312 // really this is a list of ((list of mixin aliases), (list of indices)) 4313 // with each inner list sorted ascending. 4314 // 4315 // what's the background? 4316 // we want to generate no more than M slots for this index/signal 4317 // spec, where M is the number of distinct signals (mixin aliases) 4318 // passed in. This should minimize the amount of additional memory 4319 // that each value has to keep track of. 4320 // 4321 // We also want to know when different signals share the same index 4322 // set, so we don't have to generate redundant slots. 4323 // so we generate this mapping, which should help. 4324 // 4325 // Requires: In the map's key set - a set of sets of mixin aliases - 4326 // each mixin appears in exactly one set. (it is a true set) 4327 // The map's value set - a set of sets of indices - is a true set, 4328 // each index set is unique 4329 // 4330 // Then: for each entry in the map (K,V), we generate a slot function W 4331 // inside our node. W gets connected/disconnected to/from each of 4332 // the signals in K. W notifies each of the indices in V. 4333 4334 alias GenSets!(0).result Mixin2Index; 4335 4336 4337 template _GetIndicesForSignal(string signal, size_t i){ 4338 static if(i < N){ 4339 static if(staticIndexOf!(signal, GetMixinAliases!(List[i])) 4340 != -1){ 4341 alias TypeTuple!(i,_GetIndicesForSignal!(signal,i+1)) 4342 _GetIndicesForSignal; 4343 }else{ 4344 alias _GetIndicesForSignal!(signal,i+1) 4345 _GetIndicesForSignal; 4346 } 4347 }else{ 4348 alias TypeTuple!() _GetIndicesForSignal; 4349 } 4350 } 4351 4352 template GetIndicesForSignal(string signal){ 4353 alias _GetIndicesForSignal!(signal, 0) GetIndicesForSignal; 4354 } 4355 } 4356 } 4357 4358 template ExpandStarSignals(IndexedBy, L...) { 4359 static if(L.length == 0) { 4360 alias TypeTuple!() ExpandStarSignals; 4361 }else static if(__traits(compiles,L[0].Tag) && L[0].Tag == "*") { 4362 alias TypeTuple!(ExpandStarSignal!(IndexedBy, 0, L[0]), 4363 ExpandStarSignals!(IndexedBy, L[1 .. $])) ExpandStarSignals; 4364 }else{ 4365 alias TypeTuple!(L[0], ExpandStarSignals!(IndexedBy, L[1 .. $])) 4366 ExpandStarSignals; 4367 } 4368 } 4369 4370 template ExpandStarSignal(IndexedBy, size_t i, ProtoSignal) { 4371 static if(i >= IndexedBy.Indices.length) { 4372 alias TypeTuple!() ExpandStarSignal; 4373 }else { 4374 alias TypeTuple!(ValueSignal!(i, ProtoSignal.MixinAlias), 4375 ExpandStarSignal!(IndexedBy, i+1, ProtoSignal)) ExpandStarSignal; 4376 } 4377 4378 } 4379 4380 /// _ 4381 struct ValueSignal(size_t index, string mixinAlias = "") 4382 { 4383 enum size_t Index = index; 4384 enum MixinAlias = mixinAlias; 4385 } 4386 4387 /// _ 4388 struct ValueSignal(string tag, string mixinAlias = "") 4389 { 4390 enum Tag = tag; 4391 enum MixinAlias = mixinAlias; 4392 } 4393 4394 struct Mixin2Indices(stuff...) 4395 // wish we could pass arrays directly (cough) 4396 if(stuff.length == 2 && is(typeof(stuff[0]) == string[]) && 4397 is(typeof(stuff[1]) == size_t[])){ 4398 enum string[] MixinAliases = stuff[0]; 4399 enum size_t[] Indices = stuff[1]; 4400 } 4401 4402 4403 /++ 4404 A multi_index node. Holds the value of a single element, 4405 plus per-node headers of each index, if any. 4406 The headers are all mixed in in the same scope. To prevent 4407 naming conflicts, a header field must be accessed with the number 4408 of its index. 4409 Example: 4410 ---- 4411 alias MNode!(IndexedBy!(Sequenced!(), Sequenced!(), OrderedUnique!()), int) Node; 4412 Node* n1 = new Node(); 4413 Node* n2 = new Node(); 4414 n1.index!0 .next = n2; 4415 n2.index!0 .prev = n1; 4416 n1.index!1 .prev = n2; 4417 n2.index!1 .next = n1; 4418 n1.index!2 .left = n2; 4419 ---- 4420 +/ 4421 struct MNode(_ThisContainer, IndexedBy, Allocator, Signals, Value, ValueView) { 4422 alias _ThisContainer ThisContainer; 4423 static if(MutableValue!(MNode, Value)) { 4424 Value value; 4425 }else{ 4426 // do a dumb tail const sort of thing 4427 struct Capsule { 4428 Value value; 4429 } 4430 Capsule* val_ptr; 4431 4432 @property Value value() pure inout { return val_ptr.value; } 4433 @property void value(Value v) { 4434 if(val_ptr != null) { 4435 Allocator.deallocate(val_ptr); 4436 } 4437 val_ptr = Allocator.allocate!(Capsule)(1); 4438 Capsule c = Capsule(v); 4439 move(c, *val_ptr); 4440 } 4441 this(Value val) { 4442 this.value = val; 4443 } 4444 ~this() { 4445 if(val_ptr != null) { 4446 Allocator.deallocate(val_ptr); 4447 val_ptr = null; 4448 } 4449 } 4450 } 4451 4452 static if(Signals.AllSignals.length > 0) { 4453 // notifications need to go somewhere 4454 ThisContainer container; 4455 4456 /// generate slots 4457 template ForEachSignal(size_t i) { 4458 static if(i < Signals.Mixin2Index.length) { 4459 alias Signals.Mixin2Index[i] Mixin2Index; 4460 4461 template ForEachIndex2(size_t j) { 4462 static if(j < Mixin2Index.Indices.length) { 4463 enum result = Replace!(q{ 4464 if(!container.index!($i)._NotifyChange(&this)) { 4465 goto denied; 4466 } 4467 }, "$i", Mixin2Index.Indices[j]) ~ ForEachIndex2!(j+1).result; 4468 }else{ 4469 enum result = ""; 4470 } 4471 } 4472 enum stuff = Replace!(q{ 4473 void slot$i(){ 4474 $x 4475 return; 4476 denied: enforce(false, "todo: put a useful message in here"); 4477 } 4478 }, "$i", i, "$x", ForEachIndex2!(0).result); 4479 }else{ 4480 enum stuff = ""; 4481 } 4482 } 4483 4484 enum signal_stuff = ForEachSignal!(0).stuff; 4485 mixin(signal_stuff); 4486 } 4487 4488 4489 template ForEachIndex(size_t N,L...){ 4490 static if(L.length > 0){ 4491 enum indexN = Replace!("index%s","%s", N); 4492 //alias L[0] L0; 4493 enum result = 4494 Replace!(q{ 4495 alias IndexedBy.Indices[$N] L$N; 4496 alias L$N.Inner!(ThisContainer, typeof(this),Value,ValueView,$N, Allocator) M$N; 4497 mixin M$N.NodeMixin!(M$N.NodeTuple) index$N; 4498 template index(size_t n) if(n == $N){ alias index$N index; } 4499 }, "$N", N) ~ 4500 ForEachIndex!(N+1, L[1 .. $]).result; 4501 }else{ 4502 enum result = ""; 4503 } 4504 } 4505 4506 enum stuff = ForEachIndex!(0, IndexedBy.Indices).result; 4507 mixin(stuff); 4508 } 4509 4510 struct ConstView{} 4511 struct MutableView{} 4512 4513 template IsIndexedBy(alias x) { 4514 // test x.stringof in case we have a bare Sequenced!() or somesuch 4515 enum bool IsIndexedBy = __traits(compiles, x.stringof) && 4516 x.stringof.startsWith("IndexedBy!") && 4517 __traits(compiles, x.List); 4518 } 4519 4520 template IsIndex(alias x) { 4521 enum bool IsIndex = __traits(hasMember, x, "Inner"); 4522 } 4523 4524 int IndexedByCount(X...)() { 4525 int r = 0; 4526 foreach(i,x; X){ 4527 static if(__traits(compiles,IsIndexedBy!x) && IsIndexedBy!x) { 4528 r++; 4529 } 4530 } 4531 return r; 4532 } 4533 size_t[] IndexedByAllIndices(X)() { 4534 // erm. returns list of nonindices in IndexedBy 4535 size_t[] res = []; 4536 foreach(i,x; X.List){ 4537 static if(!IsIndex!x && 4538 (i == 0 || !IsIndex!(X.List[i-1]) || !is(typeof(x) == string))) { 4539 res ~= i; 4540 } 4541 } 4542 return res; 4543 } 4544 4545 4546 template FindIndexedBy(Args...) { 4547 static if(IsIndexedBy!(Args[0])) { 4548 alias Args[0] FindIndexedBy; 4549 }else { 4550 alias FindIndexedBy!(Args[1 .. $]) FindIndexedBy; 4551 } 4552 } 4553 4554 template IsValueChangedSlots(alias X) { 4555 enum bool IsValueChangedSlots = __traits(compiles, X.stringof) && 4556 X.stringof.startsWith("ValueChangedSlots!"); 4557 } 4558 4559 int ValueChangedSlotsCount(Args...)() { 4560 int r = 0; 4561 foreach(i,x; Args){ 4562 static if(__traits(compiles,IsValueChangedSlots!x) && IsValueChangedSlots!x) { 4563 r++; 4564 } 4565 } 4566 return r; 4567 } 4568 4569 template FindValueChangedSlots(Args...) { 4570 static if(Args.length == 0) { 4571 alias ValueChangedSlots!() FindValueChangedSlots; 4572 }else static if(IsValueChangedSlots!(Args[0])) { 4573 alias Args[0] FindValueChangedSlots; 4574 }else { 4575 alias FindValueChangedSlots!(Args[1 .. $]) FindValueChangedSlots; 4576 } 4577 } 4578 4579 template IsConstnessView(alias T) { 4580 enum bool IsConstnessView = is(T == MutableView) || is(T == ConstView); 4581 } 4582 4583 int ConstnessViewCount(Args...)() { 4584 int r = 0; 4585 foreach(i,x; Args){ 4586 static if(__traits(compiles,IsConstnessView!x) && IsConstnessView!x) { 4587 r++; 4588 } 4589 } 4590 return r; 4591 } 4592 4593 template FindConstnessView(Args...) { 4594 static if(Args.length == 0) { 4595 alias ConstView FindConstnessView; 4596 }else static if(IsConstnessView!(Args[0])) { 4597 alias Args[0] FindConstnessView; 4598 }else { 4599 alias FindConstnessView!(Args[1 .. $]) FindConstnessView; 4600 } 4601 } 4602 4603 int AllocatorCount(Args...)() { 4604 int r = 0; 4605 foreach(i,x; Args){ 4606 static if(__traits(compiles, IsAllocator!x) && IsAllocator!x) { 4607 r++; 4608 } 4609 } 4610 return r; 4611 } 4612 4613 template FindAllocator(Args...) { 4614 static if(Args.length == 0) { 4615 alias GCAllocator FindAllocator; 4616 }else static if(IsAllocator!(Args[0])) { 4617 alias Args[0] FindAllocator; 4618 }else { 4619 alias FindAllocator!(Args[1 .. $]) FindAllocator; 4620 } 4621 } 4622 4623 size_t[] IndexGarbage(Args...)() { 4624 size_t[] res = []; 4625 foreach(i,x; Args){ 4626 static if(!(__traits(compiles,IsIndexedBy!x) && IsIndexedBy!x) && 4627 !(__traits(compiles,IsValueChangedSlots!x) && IsValueChangedSlots!x) && 4628 !(__traits(compiles,IsConstnessView!x) && IsConstnessView!x) && 4629 !(__traits(compiles,IsAllocator!x) && IsAllocator!x)) { 4630 res ~= i; 4631 } 4632 } 4633 return res; 4634 } 4635 4636 4637 struct ComparisonEx(alias _key, alias _less) { 4638 alias _less _less_; 4639 alias binaryFun!_less less; 4640 alias unaryFun!_key key; 4641 } 4642 4643 struct DefaultComparison(alias _less) { 4644 alias _less less; 4645 } 4646 4647 template MultiCompare(F...) { 4648 template NormComps(size_t i = 0, alias Dflt = "a<b") { 4649 static if(i == F.length) { 4650 alias TypeTuple!() NormComps; 4651 }else { 4652 static if(F[i].stringof.startsWith("DefaultComparison!") && 4653 __traits(compiles, F[i].less)) { 4654 alias NormComps!(i+1, F[i].less) NormComps; 4655 }else{ 4656 static if (F[i].stringof.startsWith("ComparisonEx!") && 4657 __traits(compiles, F[i].less) && 4658 __traits(compiles, F[i].key)) { 4659 alias F[i] Cmp; 4660 }else { 4661 alias ComparisonEx!(F[i], Dflt) Cmp; 4662 } 4663 alias TypeTuple!(Cmp, NormComps!(i+1, Dflt)) NormComps; 4664 } 4665 } 4666 } 4667 4668 alias NormComps!() Comps; 4669 4670 bool MultiCompare(T)(T a, T b) { 4671 foreach(i, cmp; Comps) { 4672 auto a1 = cmp.key(a); 4673 auto b1 = cmp.key(b); 4674 auto less = cmp.less(a1,b1); 4675 if(less) return true; 4676 auto gtr = cmp.less(b1,a1); 4677 if(gtr) return false; 4678 static if(i == Comps.length-1) { 4679 return false; 4680 } 4681 } 4682 assert(0); 4683 } 4684 } 4685 4686 template IsCompatibleLess(Less, Key, CKey) { 4687 enum bool IsCompatibleLess = is(typeof({ 4688 Less less; 4689 auto c = CKey.init; 4690 auto k = Key.init; 4691 less.cc_less(c,c); 4692 less.kc_less(k,c); 4693 less.ck_less(c,k); 4694 })); 4695 } 4696 4697 struct CriterionFromKey(MultiIndex, size_t index, 4698 alias CompatibleKeyFromKey, 4699 alias CompatibleLess = "a<b") { 4700 alias binaryFun!CompatibleLess less; 4701 alias MultiIndex.index!(index).key key; 4702 alias MultiIndex.index!(index).KeyType KeyType; 4703 alias unaryFun!CompatibleKeyFromKey ckey; 4704 alias typeof(ckey(MultiIndex.ValueView.init)) CompatibleKeyType; 4705 4706 static: 4707 bool kc_less(KeyType a, CompatibleKeyType b) { 4708 return less(ckey(a),b); 4709 } 4710 bool ck_less(CompatibleKeyType a, KeyType b) { 4711 return less(a, ckey(b)); 4712 } 4713 bool cc_less(CompatibleKeyType a, CompatibleKeyType b) { 4714 return less(a, b); 4715 } 4716 } 4717 4718 // error sinks 4719 4720 class MultiIndexContainer(Value, Args...) 4721 if(IndexedByCount!(Args)() != 1) { 4722 static assert (IndexedByCount!(Args)() > 0, "MultiIndexContainer requires indices to be wrapped with IndexedBy!(..)"); 4723 static assert (IndexedByCount!(Args)() < 2, "MultiIndexContainer takes exactly one IndexedBy!(..)"); 4724 } 4725 4726 class MultiIndexContainer(Value, Args...) 4727 if(FindIndexedBy!Args .List.length == 0) { 4728 static assert(false, "MultiIndexContainer requires at least one index"); 4729 } 4730 4731 class MultiIndexContainer(Value, Args...) 4732 if(IndexedByAllIndices!(FindIndexedBy!Args)().length != 0) { 4733 import std.conv; 4734 alias FindIndexedBy!Args IndexedBy; 4735 enum lst = IndexedByAllIndices!(IndexedBy)(); 4736 pragma(msg, "IndexedBy contains non-index at indices"); 4737 mixin template Frch(size_t i) { 4738 static if(i < lst.length) { 4739 static if(__traits(compiles, IndexedBy.List[lst[i]].stringof)) { 4740 pragma(msg, to!string(lst[i]) ~ ": " ~ IndexedBy.List[lst[i]].stringof); 4741 }else{ 4742 pragma(msg, to!string(lst[i])); 4743 } 4744 mixin Frch!(i+1); 4745 } 4746 } 4747 mixin Frch!(0); 4748 static assert(false); 4749 // @@@ PHOBOS ISSUE 8320 @@@ 4750 /+ 4751 static assert (false, 4752 Replace!(/*"IndexedBy contains non-index at indices*/" %s", "%s", 4753 IndexedByAllIndices!(FindIndexedBy!Args)())); 4754 +/ 4755 } 4756 4757 class MultiIndexContainer(Value, Args...) 4758 if(ValueChangedSlotsCount!(Args)() > 1) { 4759 static assert(false, "Multiple ValueChangedSlots specifications are not allowed"); 4760 } 4761 4762 class MultiIndexContainer(Value, Args...) 4763 if(ConstnessViewCount!(Args)() > 1) { 4764 static assert(false, "Multiple Constness Views are not allowed"); 4765 } 4766 4767 class MultiIndexContainer(Value, Args...) 4768 if(AllocatorCount!(Args)() > 1) { 4769 static assert(false, "Multiple allocators are not allowed"); 4770 } 4771 4772 class MultiIndexContainer(Value, Args...) 4773 if(IndexGarbage!(Args)().length != 0) { 4774 import std.conv; 4775 enum lst = IndexGarbage!(Args)(); 4776 pragma(msg, "MultiIndexContainer unknown arguments at"); 4777 mixin template Frch(size_t i) { 4778 static if(i < lst.length) { 4779 static if(__traits(compiles, Args[lst[i]].stringof)) { 4780 pragma(msg, to!string(lst[i]) ~ ": " ~ Args[lst[i]].stringof); 4781 }else{ 4782 pragma(msg, to!string(lst[i])); 4783 } 4784 mixin Frch!(i+1); 4785 } 4786 } 4787 mixin Frch!(0); 4788 static assert(false); 4789 // @@@ PHOBOS ISSUE 8320 @@@ 4790 /+ 4791 static assert (false, 4792 Replace!(/*"IndexedBy contains non-index at indices*/" %s", "%s", 4793 IndexedByAllIndices!(FindIndexedBy!Args)())); 4794 +/ 4795 } 4796 4797 template MutableValue(Node, Value) { 4798 enum MutableValue = __traits(compiles, { Value value; value = Value.init; }); 4799 } 4800 4801 template _AllUnique(Thing...) { 4802 enum _AllUnique = NoDuplicates!Thing .length == Thing.length; 4803 } 4804 class MultiIndexContainer(Value, Args...) 4805 if(!_AllUnique!(FindIndexedBy!Args .Names)) { 4806 static assert(false, "duplicates!"); 4807 } 4808 4809 4810 4811 // end error sinks 4812 4813 /++ 4814 The container. Don't call any index methods from this container directly; use 4815 a reference to an individual index, which can be obtained via 4816 --- 4817 container.get_index!N 4818 --- 4819 or 4820 --- 4821 container.name 4822 --- 4823 for named indices. 4824 4825 If you have a range into an index of this container, you can convert it to a 4826 range of index N via 4827 --- 4828 container.to_range!N(range) 4829 --- 4830 This is equivalent to c++ multi_index' project 4831 +/ 4832 class MultiIndexContainer(Value, Args...) 4833 if(IndexedByCount!(Args)() == 1 && 4834 FindIndexedBy!Args .List.length != 0 && 4835 IndexedByAllIndices!(FindIndexedBy!Args)().length == 0 && 4836 _AllUnique!(FindIndexedBy!Args .Names) && 4837 ValueChangedSlotsCount!(Args)() <= 1 && 4838 ConstnessViewCount!(Args)() <= 1 && 4839 AllocatorCount!(Args)() <= 1 && 4840 IndexGarbage!(Args)().length == 0) { 4841 4842 alias FindIndexedBy!Args IndexedBy; 4843 // @@@ DMD ISSUE 6475 @@@ following gives forward reference error 4844 //alias FindValueChangedSlots!Args .Inner!(IndexedBy) NormSignals; 4845 alias typeof(FindValueChangedSlots!Args .Inner!(IndexedBy).exposeType()) NormSignals; 4846 alias FindConstnessView!Args ConstnessView; 4847 alias FindAllocator!Args Allocator; 4848 4849 static if(is(ConstnessView == ConstView)){ 4850 alias const(Value) ValueView; 4851 }else static if(is(ConstnessView == MutableView)){ 4852 alias Value ValueView; 4853 }else static assert(false); 4854 alias MNode!(typeof(this), IndexedBy,Allocator,NormSignals,Value, ValueView) ThisNode; 4855 4856 /+ 4857 template IndexedByList0(size_t i, stuff...){ 4858 static if(i < IndexedBy.Indices.length){ 4859 alias typeof(IndexedBy.Indices[i].Inner!(typeof(this), ThisNode, Value, i).exposeType()) x; 4860 alias IndexedByList0!(i+1, stuff, x).result result; 4861 }else{ 4862 alias stuff result; 4863 } 4864 } 4865 4866 alias IndexedByList0!(0).result IndexedByList; 4867 +/ 4868 4869 size_t node_count; 4870 4871 template ForEachCtorMixin(size_t i){ 4872 static if(i < IndexedBy.Indices.length){ 4873 static if(is(typeof(IndexedBy.Indices[i].Inner!(typeof(this), 4874 ThisNode,Value,ValueView,i,Allocator).IndexCtorMixin))){ 4875 enum result = IndexedBy.Indices[i].Inner!(typeof(this), 4876 ThisNode,Value, ValueView,i,Allocator).IndexCtorMixin ~ 4877 ForEachCtorMixin!(i+1).result; 4878 }else enum result = ForEachCtorMixin!(i+1).result; 4879 }else enum result = ""; 4880 } 4881 4882 this(){ 4883 mixin(ForEachCtorMixin!(0).result); 4884 } 4885 4886 void dealloc(ThisNode* node){ 4887 // disconnect signals from slots 4888 foreach(i, x; NormSignals.Mixin2Index){ 4889 foreach(j, malias; OU!(string).arr2tuple!(x.MixinAliases)){ 4890 static if(malias == ""){ 4891 mixin(Replace!(q{ 4892 node.value.disconnect(&node.slot$i); 4893 }, "$i", i)); 4894 }else{ 4895 mixin(Replace!(q{ 4896 node.value.$alias.disconnect(&node.slot$i); 4897 }, "$i", i,"$alias", malias)); 4898 } 4899 } 4900 } 4901 object.destroy(node); 4902 Allocator.deallocate(node); 4903 } 4904 4905 new(size_t sz) { 4906 void* p = Allocator.allocate!void(sz); 4907 return p; 4908 } 4909 delete(void* p) { 4910 Allocator.deallocate(p); 4911 } 4912 4913 template ForEachIndex(size_t N,L...){ 4914 static if(L.length > 0){ 4915 enum result = 4916 Replace!(q{ 4917 alias IndexedBy.Indices[$N] L$N; 4918 alias L$N.Inner!(typeof(this),ThisNode,Value, ValueView,$N,Allocator) M$N; 4919 mixin M$N.IndexMixin!(M$N.IndexTuple) index$N; 4920 template index(size_t n) if(n == $N){ alias index$N index; } 4921 struct Index$N{ 4922 MultiIndexContainer _this; 4923 4924 // grr opdispatch not handle this one 4925 auto opSlice(T...)(T ts){ 4926 return _this.index!($N).opSlice(ts); 4927 } 4928 4929 // grr opdispatch not handle this one 4930 auto opIndex(T...)(T ts){ 4931 return _this.index!($N).opIndex(ts); 4932 } 4933 4934 // grr opdispatch not handle this one 4935 auto opIndexAssign(T...)(T ts){ 4936 return _this.index!($N).opIndexAssign(ts); 4937 } 4938 4939 // grr opdispatch not handle this one 4940 auto opBinaryRight(string op, T...)(T ts){ 4941 return _this.index!($N).opBinaryRight!(op)(ts); 4942 } 4943 4944 // grr opdispatch not handle this one 4945 auto bounds(string bs = "[]", T)(T t1, T t2){ 4946 return _this.index!($N).bounds!(bs,T)(t1,t2); 4947 } 4948 // grr opdispatch not handle this one 4949 auto bounds(V, string bs = "[]", T)(T t1, T t2){ 4950 return _this.index!($N).cbounds!(V,bs,T)(t1,t2); 4951 } 4952 // grr opdispatch not handle this one 4953 auto cEqualRange(L, K)(K k) 4954 { 4955 return _this.index!($N).cEqualRange!(L, K).equalRange(k); 4956 } 4957 // grr opdispatch not handle this one 4958 auto cEqualRange(L, K)(K k) const 4959 { 4960 return _this.index!($N).cEqualRange!(L, K).equalRange(k); 4961 } 4962 4963 auto opDispatch(string s, T...)(T args){ 4964 mixin("return _this.index!($N)."~s~"(args);"); 4965 } 4966 } 4967 @property Index$N get_index(size_t n)() if(n == $N){ 4968 return Index$N(this); 4969 } 4970 }, "$N", N) ~ 4971 ForEachIndex!(N+1, L[1 .. $]).result; 4972 }else{ 4973 enum result = ""; 4974 } 4975 } 4976 4977 enum stuff = (ForEachIndex!(0, IndexedBy.Indices).result); 4978 mixin(stuff); 4979 4980 template ForEachNamedIndex(size_t i){ 4981 static if(i >= IndexedBy.Names.length) { 4982 enum result = ""; 4983 }else { 4984 enum result = Replace!(q{ 4985 alias get_index!$N $name; 4986 }, "$N", IndexedBy.NameIndices[i], "$name", IndexedBy.Names[i]) ~ 4987 ForEachNamedIndex!(i+1).result; 4988 } 4989 } 4990 4991 enum named_stuff = ForEachNamedIndex!0 .result; 4992 mixin(named_stuff); 4993 4994 4995 template ForEachCheckInsert(size_t i, size_t N){ 4996 static if(i < IndexedBy.Indices.length){ 4997 static if(i != N && __traits(hasMember, index!i,"_DenyInsertion")){ 4998 enum result = (Replace!(q{ 4999 ThisNode* aY; 5000 bool bY = index!(Y)._DenyInsertion(node,aY); 5001 if (bY) goto denied; 5002 }, "Y", i)) ~ ForEachCheckInsert!(i+1, N).result; 5003 }else enum result = ForEachCheckInsert!(i+1, N).result; 5004 }else enum result = ""; 5005 } 5006 5007 template ForEachDoInsert(size_t i, size_t N){ 5008 static if(i < IndexedBy.Indices.length){ 5009 static if(i != N){ 5010 import std.traits; 5011 static if(ParameterTypeTuple!(index!i._Insert).length == 2){ 5012 enum result = Replace!(q{ 5013 index!(Y)._Insert(node,aY); 5014 }, "Y", i) ~ ForEachDoInsert!(i+1,N).result; 5015 }else{ 5016 enum result = Replace!(q{ 5017 index!(Y)._Insert(node); 5018 }, "Y", i) ~ ForEachDoInsert!(i+1,N).result; 5019 } 5020 }else enum result = ForEachDoInsert!(i+1, N).result; 5021 }else enum result = ""; 5022 } 5023 5024 ThisNode* _InsertAllBut(size_t N)(Value value){ 5025 ThisNode* node = Allocator.allocate!(ThisNode)(1); 5026 static if(MutableValue!(ThisNode, Value)) { 5027 node.value = value; 5028 }else{ 5029 auto t = ThisNode(value); 5030 move(t, *node); 5031 } 5032 5033 // connect signals to slots 5034 foreach(i, x; NormSignals.Mixin2Index){ 5035 static if(i == 0) node.container = this; 5036 5037 foreach(j, malias; OU!(string).arr2tuple!(x.MixinAliases)){ 5038 static if(malias == ""){ 5039 mixin(Replace!(q{ 5040 node.value.connect(&node.slot$i); 5041 }, "$i", i)); 5042 }else{ 5043 mixin(Replace!(q{ 5044 node.value.$alias.connect(&node.slot$i); 5045 }, "$i", i,"$alias", malias)); 5046 } 5047 } 5048 } 5049 5050 // check with each index about insert op 5051 /+ 5052 foreach(i, x; IndexedByList){ 5053 /+ 5054 static if(i != N && is(typeof({ ThisNode* p; 5055 index!i._DenyInsertion(p,p);}))){ 5056 enum result = (Replace!(q{ 5057 ThisNode* aY; 5058 bool bY = index!(Y)._DenyInsertion(node,aY); 5059 if (bY) goto denied; 5060 }, "Y", i)) ~ ForEachCheckInsert!(i+1, N).result; 5061 }kelse enum result = ForEachCheckInsert!(i+1, N).result; 5062 +/ 5063 } 5064 +/ 5065 mixin(ForEachCheckInsert!(0, N).result); 5066 // perform insert op on each index 5067 mixin(ForEachDoInsert!(0, N).result); 5068 node_count++; 5069 return node; 5070 denied: 5071 return null; 5072 } 5073 5074 template ForEachDoRemove(size_t i, size_t N){ 5075 static if(i < IndexedBy.Indices.length){ 5076 static if(i != N){ 5077 enum result = Replace!(q{ 5078 index!(Y)._Remove(node); 5079 }, "Y", i) ~ ForEachDoRemove!(i+1,N).result; 5080 }else enum result = ForEachDoRemove!(i+1, N).result; 5081 }else enum result = ""; 5082 } 5083 5084 // disattach node from all indices except index N 5085 void _RemoveAllBut(size_t N)(ThisNode* node){ 5086 mixin(ForEachDoRemove!(0, N).result); 5087 node_count --; 5088 } 5089 5090 // disattach node from all indices. 5091 // @@@BUG@@@ cannot pass length directly to _RemoveAllBut 5092 auto _RemoveAll(size_t N = size_t.max)(ThisNode* node){ 5093 static if(N == size_t.max) { 5094 enum _grr_bugs = IndexedBy.Indices.length; 5095 _RemoveAllBut!(_grr_bugs)(node); 5096 }else { 5097 _RemoveAllBut!N(node); 5098 auto res = index!N._Remove(node); 5099 } 5100 dealloc(node); 5101 5102 static if(N != size_t.max) { 5103 return res; 5104 } 5105 } 5106 5107 template ForEachIndexPosition(size_t i){ 5108 static if(i < IndexedBy.Indices.length){ 5109 static if(is(typeof(index!i ._NodePosition((ThisNode*).init)))){ 5110 enum variableDeclarations = Replace!(q{ 5111 ThisNode* node$i; 5112 }, "$i", i) ~ ForEachIndexPosition!(i+1).variableDeclarations; 5113 enum getNodePositions = Replace!(q{ 5114 auto pos$i = index!$i ._NodePosition(node); 5115 }, "$i", i) ~ ForEachIndexPosition!(i+1).getNodePositions; 5116 enum gotoDeniedOnInvalid = Replace!(q{ 5117 if(!index!$i ._PositionFixable(node, pos$i, node$i)) 5118 goto denied; 5119 }, "$i", i) ~ ForEachIndexPosition!(i+1).gotoDeniedOnInvalid; 5120 enum fixupIndices = Replace!(q{ 5121 index!$i ._FixPosition(node, pos$i, node$i); 5122 }, "$i", i) ~ ForEachIndexPosition!(i+1).fixupIndices; 5123 }else{ 5124 enum getNodePositions = ForEachIndexPosition!(i+1).getNodePositions; 5125 enum variableDeclarations = ForEachIndexPosition!(i+1).variableDeclarations; 5126 enum gotoDeniedOnInvalid = ForEachIndexPosition!(i+1).gotoDeniedOnInvalid; 5127 enum fixupIndices = ForEachIndexPosition!(i+1).fixupIndices; 5128 } 5129 }else{ 5130 enum getNodePositions = ""; 5131 enum variableDeclarations = ""; 5132 enum gotoDeniedOnInvalid = ""; 5133 enum fixupIndices = ""; 5134 } 5135 } 5136 5137 bool _Replace(ThisNode* node, Value value){ 5138 mixin(ForEachIndexPosition!0 .variableDeclarations); 5139 mixin(ForEachIndexPosition!0 .getNodePositions); 5140 Value old = node.value; 5141 node.value = value; 5142 { 5143 mixin(ForEachIndexPosition!0 .gotoDeniedOnInvalid); 5144 mixin(ForEachIndexPosition!0 .fixupIndices); 5145 } 5146 return true; 5147 denied: 5148 node.value = old; 5149 return false; 5150 } 5151 5152 /* 5153 Perform mod on node.value and perform any necessary fixups to this container's 5154 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, 5155 the node is removed from the container. 5156 Preconditions: mod is a callable of the form void mod(ref Value) 5157 Complexity: $(BIGOH m(n)) 5158 */ 5159 void _Modify(Modifier)(ThisNode* node, Modifier mod){ 5160 mixin(ForEachIndexPosition!0 .variableDeclarations); 5161 mixin(ForEachIndexPosition!0 .getNodePositions); 5162 mod(node.value); 5163 mixin(ForEachIndexPosition!0 .gotoDeniedOnInvalid); 5164 mixin(ForEachIndexPosition!0 .fixupIndices); 5165 return; 5166 denied: 5167 _RemoveAll(node); 5168 } 5169 5170 template ForEachClear(size_t i){ 5171 static if(i < IndexedBy.Indices.length){ 5172 enum string result = Replace!(q{ 5173 index!$i ._ClearIndex(); 5174 }, "$i", i) ~ ForEachClear!(i+1).result; 5175 }else enum string result = ""; 5176 } 5177 5178 void _Clear(){ 5179 auto r = index!0 .opSlice(); 5180 while(!r.empty){ 5181 ThisNode* node = r.front_node; 5182 r.popFront(); 5183 dealloc(node); 5184 } 5185 mixin(ForEachClear!0 .result); 5186 node_count = 0; 5187 } 5188 5189 template ForEachCheck(size_t i){ 5190 static if(i < IndexedBy.Indices.length){ 5191 enum result = Replace!(q{ 5192 index!($i)._Check(); 5193 },"$i", i) ~ ForEachCheck!(i+1).result; 5194 }else{ 5195 enum result = ""; 5196 } 5197 } 5198 5199 void check(){ 5200 mixin(ForEachCheck!(0).result); 5201 } 5202 5203 template ForEachAlias(size_t N,size_t index, alias X){ 5204 alias X.Inner!(ThisNode,Value, ValueView,N,Allocator).Index!() Index; 5205 static if(Index.container_aliases.length > index){ 5206 enum aliashere = NAliased!(Index.container_aliases[index][0], 5207 Index.container_aliases[index][1], N); 5208 enum result = aliashere ~ "\n" ~ ForEachAlias!(N,index+1, X).result; 5209 }else{ 5210 enum result = ""; 5211 } 5212 } 5213 5214 5215 @property auto to_range(size_t N, Range0)(Range0 r) 5216 if(RangeIndexNo!Range0 != -1){ 5217 static if(N == RangeIndexNo!Range0){ 5218 return r; 5219 }else{ 5220 return index!N.fromNode(r.front_node); 5221 } 5222 } 5223 5224 private template RangeIndexNo(R){ 5225 template IndexNoI(size_t i){ 5226 static if(i == IndexedBy.Indices.length){ 5227 enum size_t IndexNoI = -1; 5228 }else static if(index!(i).IsMyRange!(R)){ 5229 enum size_t IndexNoI = i; 5230 }else{ 5231 enum IndexNoI = IndexNoI!(i+1); 5232 } 5233 } 5234 enum size_t RangeIndexNo = IndexNoI!(0); 5235 } 5236 } 5237 5238 /// simple Slot implementation 5239 mixin template Slots() { 5240 void delegate()[] slots; 5241 5242 void connect(void delegate() slot){ 5243 slots ~= slot; 5244 } 5245 void disconnect(void delegate() slot){ 5246 size_t index = slots.length; 5247 foreach(i, slot1; slots){ 5248 if(slot is slot1){ 5249 index = i; 5250 moveAll(slots[i+1 .. $], slots[i .. $-1]); 5251 slots.length-=1; 5252 break; 5253 } 5254 } 5255 } 5256 void emit(){ 5257 foreach(slot; slots){ 5258 slot(); 5259 } 5260 } 5261 } 5262 5263 import std.stdio; 5264 5265 int[] arr(Range)(Range r){ 5266 int[] result = new int[](r.length); 5267 size_t j = 0; 5268 foreach(e; r){ 5269 result[j++] = e; 5270 } 5271 return result; 5272 } 5273 5274 struct S1{ 5275 string _s; 5276 int _i; 5277 void delegate() slot = null; 5278 5279 @property string s()const{ return _s;} 5280 @property void s(string s_){ _s = s_; emit(); } 5281 5282 @property int i()const{ return _i;} 5283 @property void i(int i_){ _i = i_; } 5284 5285 void emit(){ 5286 if (slot) slot(); 5287 } 5288 5289 void connect(void delegate() slot){ this.slot = slot; } 5290 void disconnect(void delegate() slot){ 5291 if(this.slot is slot) this.slot = null; 5292 } 5293 5294 string toString0()const{ 5295 return format("%s: %s", s, i); 5296 } 5297 } 5298 5299 version(TestMultiIndex) 5300 void main(){ 5301 alias MultiIndexContainer!(S1, 5302 IndexedBy!(Sequenced!(), 5303 OrderedUnique!("a.s") 5304 ), 5305 ValueChangedSlots!(ValueSignal!(1))) C; 5306 5307 C i = new C; 5308 5309 alias MultiIndexContainer!(const(S1), 5310 IndexedBy!(OrderedUnique!("a.s")) 5311 ) CCC; 5312 CCC c2 = new CCC; 5313 c2.insert(cast(const)S1("abc", 22)); 5314 pragma(msg, typeof(c2[])); 5315 pragma(msg, ElementType!(typeof(c2[]))); 5316 foreach(const(S1) thing; c2[]) { 5317 } 5318 5319 auto pr = PSR(c2[]); 5320 c2.replace(pr.front, const(S1)("def", 44)); 5321 }