libphobos/src/std/container/dlist.d

   1 /**
   2 This module implements a generic doubly-linked list container.
   3 It can be used as a queue, dequeue or stack.
   4
   5 This module is a submodule of $(MREF std, container).
   6
   7 Source: $(PHOBOSSRC std/container/dlist.d)
   8
   9 Copyright: 2010- Andrei Alexandrescu. All rights reserved by the respective holders.
  10
  11 License: Distributed under the Boost Software License, Version 1.0.
  12 (See accompanying file LICENSE_1_0.txt or copy at $(HTTP
  13 boost.org/LICENSE_1_0.txt)).
  14
  15 Authors: $(HTTP erdani.com, Andrei Alexandrescu)
  16
  17 $(SCRIPT inhibitQuickIndex = 1;)
  18 */
  19 module std.container.dlist;
  20
  21 ///
  22 @safe unittest
  23 {
  24     import std.algorithm.comparison : equal;
  25     import std.container : DList;
  26
  27     auto s = DList!int(1, 2, 3);
  28     assert(equal(s[], [1, 2, 3]));
  29
  30     s.removeFront();
  31     assert(equal(s[], [2, 3]));
  32     s.removeBack();
  33     assert(equal(s[], [2]));
  34
  35     s.insertFront([4, 5]);
  36     assert(equal(s[], [4, 5, 2]));
  37     s.insertBack([6, 7]);
  38     assert(equal(s[], [4, 5, 2, 6, 7]));
  39
  40     // If you want to apply range operations, simply slice it.
  41     import std.algorithm.searching : countUntil;
  42     import std.range : popFrontN, popBackN, walkLength;
  43
  44     auto sl = DList!int([1, 2, 3, 4, 5]);
  45     assert(countUntil(sl[], 2) == 1);
  46
  47     auto r = sl[];
  48     popFrontN(r, 2);
  49     popBackN(r, 2);
  50     assert(r.equal([3]));
  51     assert(walkLength(r) == 1);
  52
  53     // DList.Range can be used to remove elements from the list it spans
  54     auto nl = DList!int([1, 2, 3, 4, 5]);
  55     for (auto rn = nl[]; !rn.empty;)
  56         if (rn.front % 2 == 0)
  57             nl.popFirstOf(rn);
  58         else
  59             rn.popFront();
  60     assert(equal(nl[], [1, 3, 5]));
  61     auto rs = nl[];
  62     rs.popFront();
  63     nl.remove(rs);
  64     assert(equal(nl[], [1]));
  65 }
  66
  67 import std.range.primitives;
  68 import std.traits;
  69
  70 public import std.container.util;
  71
  72 /+
  73 A DList Node without payload. Used to handle the sentinel node (henceforth "sentinode").
  74
  75 Also used for parts of the code that don't depend on the payload type.
  76  +/
  77 private struct BaseNode
  78 {
  79     private BaseNode* _prev = null;
  80     private BaseNode* _next = null;
  81
  82     /+
  83     Gets the payload associated with this node.
  84     This is trusted because all nodes are associated with a payload, even
  85     the sentinel node.
  86     It is also not possible to mix Nodes in DLists of different types.
  87     This function is implemented as a member function here, as UFCS does not
  88     work with pointers.
  89     +/
  90     ref inout(T) getPayload(T)() inout @trusted
  91     {
  92         return (cast(inout(DList!T.PayNode)*)&this)._payload;
  93     }
  94
  95     // Helper: Given nodes p and n, connects them.
  96     static void connect(BaseNode* p, BaseNode* n) @safe nothrow pure
  97     {
  98         p._next = n;
  99         n._prev = p;
 100     }
 101 }
 102
 103 /+
 104 The base DList Range. Contains Range primitives that don't depend on payload type.
 105  +/
 106 private struct DRange
 107 {
 108     @safe unittest
 109     {
 110         static assert(isBidirectionalRange!DRange);
 111         static assert(is(ElementType!DRange == BaseNode*));
 112     }
 113
 114 nothrow @safe pure:
 115     private BaseNode* _first;
 116     private BaseNode* _last;
 117
 118     private this(BaseNode* first, BaseNode* last)
 119     {
 120         assert((first is null) == (last is null), "Dlist.Range.this: Invalid arguments");
 121         _first = first;
 122         _last = last;
 123     }
 124     private this(BaseNode* n)
 125     {
 126         this(n, n);
 127     }
 128
 129     @property
 130     bool empty() const scope
 131     {
 132         assert((_first is null) == (_last is null), "DList.Range: Invalidated state");
 133         return !_first;
 134     }
 135
 136     @property BaseNode* front() return scope
 137     {
 138         assert(!empty, "DList.Range.front: Range is empty");
 139         return _first;
 140     }
 141
 142     void popFront() scope
 143     {
 144         assert(!empty, "DList.Range.popFront: Range is empty");
 145         if (_first is _last)
 146         {
 147             _first = _last = null;
 148         }
 149         else
 150         {
 151             assert(_first._next && _first is _first._next._prev, "DList.Range: Invalidated state");
 152             _first = _first._next;
 153         }
 154     }
 155
 156     @property BaseNode* back() return scope
 157     {
 158         assert(!empty, "DList.Range.front: Range is empty");
 159         return _last;
 160     }
 161
 162     void popBack() scope
 163     {
 164         assert(!empty, "DList.Range.popBack: Range is empty");
 165         if (_first is _last)
 166         {
 167             _first = _last = null;
 168         }
 169         else
 170         {
 171             assert(_last._prev && _last is _last._prev._next, "DList.Range: Invalidated state");
 172             _last = _last._prev;
 173         }
 174     }
 175
 176     /// Forward range primitive.
 177     @property DRange save() return scope { return this; }
 178 }
 179
 180 /**
 181 Implements a doubly-linked list.
 182
 183 `DList` uses reference semantics.
 184  */
 185 struct DList(T)
 186 {
 187     import std.range : Take;
 188
 189     /*
 190     A Node with a Payload. A PayNode.
 191      */
 192     struct PayNode
 193     {
 194         BaseNode _base;
 195         alias _base this;
 196
 197         T _payload = T.init;
 198
 199         inout(BaseNode)* asBaseNode() inout @trusted
 200         {
 201             return &_base;
 202         }
 203     }
 204
 205     //The sentinel node
 206     private BaseNode* _root;
 207
 208   private
 209   {
 210     //Construct as new PayNode, and returns it as a BaseNode.
 211     static BaseNode* createNode(Stuff)(auto ref Stuff arg, BaseNode* prev = null, BaseNode* next = null)
 212     {
 213         return (new PayNode(BaseNode(prev, next), arg)).asBaseNode();
 214     }
 215
 216     void initialize() nothrow @safe pure
 217     {
 218         if (_root) return;
 219         //Note: We allocate a PayNode for safety reasons.
 220         _root = (new PayNode()).asBaseNode();
 221         _root._next = _root._prev = _root;
 222     }
 223     ref inout(BaseNode*) _first() @property @safe nothrow pure inout
 224     {
 225         assert(_root, "Root pointer must not be null");
 226         return _root._next;
 227     }
 228     ref inout(BaseNode*) _last() @property @safe nothrow pure inout
 229     {
 230         assert(_root, "Root pointer must not be null");
 231         return _root._prev;
 232     }
 233   } //end private
 234
 235 /**
 236 Constructor taking a number of nodes
 237      */
 238     this(U)(U[] values...) if (isImplicitlyConvertible!(U, T))
 239     {
 240         insertBack(values);
 241     }
 242
 243 /**
 244 Constructor taking an $(REF_ALTTEXT input range, isInputRange, std,range,primitives)
 245      */
 246     this(Stuff)(Stuff stuff)
 247     if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T))
 248     {
 249         insertBack(stuff);
 250     }
 251
 252 /**
 253 Comparison for equality.
 254
 255 Complexity: $(BIGOH min(n, n1)) where `n1` is the number of
 256 elements in `rhs`.
 257      */
 258     bool opEquals()(ref const DList rhs) const
 259     if (is(typeof(front == front)))
 260     {
 261         const lhs = this;
 262         const lroot = lhs._root;
 263         const rroot = rhs._root;
 264
 265         if (lroot is rroot) return true;
 266         if (lroot is null) return rroot is rroot._next;
 267         if (rroot is null) return lroot is lroot._next;
 268
 269         const(BaseNode)* pl = lhs._first;
 270         const(BaseNode)* pr = rhs._first;
 271         while (true)
 272         {
 273             if (pl is lroot) return pr is rroot;
 274             if (pr is rroot) return false;
 275
 276             // !== because of NaN
 277             if (!(pl.getPayload!T() == pr.getPayload!T())) return false;
 278
 279             pl = pl._next;
 280             pr = pr._next;
 281         }
 282     }
 283
 284     /**
 285     Defines the container's primary range, which embodies a bidirectional range.
 286      */
 287     struct Range
 288     {
 289         static assert(isBidirectionalRange!Range);
 290
 291         DRange _base;
 292         alias _base this;
 293
 294         private this(BaseNode* first, BaseNode* last)
 295         {
 296             _base = DRange(first, last);
 297         }
 298         private this(BaseNode* n)
 299         {
 300             this(n, n);
 301         }
 302
 303         @property ref T front()
 304         {
 305             return _base.front.getPayload!T();
 306         }
 307
 308         @property ref T back()
 309         {
 310             return _base.back.getPayload!T();
 311         }
 312
 313         //Note: shadows base DRange.save.
 314         //Necessary for static covariance.
 315         @property Range save() { return this; }
 316     }
 317
 318 /**
 319 Property returning `true` if and only if the container has no
 320 elements.
 321
 322 Complexity: $(BIGOH 1)
 323      */
 324     bool empty() @property const nothrow
 325     {
 326         return _root is null || _root is _first;
 327     }
 328
 329 /**
 330 Removes all contents from the `DList`.
 331
 332 Postcondition: `empty`
 333
 334 Complexity: $(BIGOH 1)
 335      */
 336     void clear()
 337     {
 338         //remove actual elements.
 339         remove(this[]);
 340     }
 341
 342 /**
 343 Duplicates the container. The elements themselves are not transitively
 344 duplicated.
 345
 346 Complexity: $(BIGOH n).
 347      */
 348     @property DList dup()
 349     {
 350         return DList(this[]);
 351     }
 352
 353 /**
 354 Returns a range that iterates over all elements of the container, in
 355 forward order.
 356
 357 Complexity: $(BIGOH 1)
 358      */
 359     Range opSlice()
 360     {
 361         if (empty)
 362             return Range(null, null);
 363         else
 364             return Range(_first, _last);
 365     }
 366
 367 /**
 368 Forward to `opSlice().front`.
 369
 370 Complexity: $(BIGOH 1)
 371      */
 372     @property ref inout(T) front() inout
 373     {
 374         assert(!empty, "DList.front: List is empty");
 375         return _first.getPayload!T();
 376     }
 377
 378 /**
 379 Forward to `opSlice().back`.
 380
 381 Complexity: $(BIGOH 1)
 382      */
 383     @property ref inout(T) back() inout
 384     {
 385         assert(!empty, "DList.back: List is empty");
 386         return _last.getPayload!T();
 387     }
 388
 389 /+ ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ +/
 390 /+                        BEGIN CONCAT FUNCTIONS HERE                         +/
 391 /+ ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ +/
 392
 393 /**
 394 Returns a new `DList` that's the concatenation of `this` and its
 395 argument `rhs`.
 396      */
 397     DList opBinary(string op, Stuff)(Stuff rhs)
 398     if (op == "~" && is(typeof(insertBack(rhs))))
 399     {
 400         auto ret = this.dup;
 401         ret.insertBack(rhs);
 402         return ret;
 403     }
 404
 405 /**
 406 Returns a new `DList` that's the concatenation of the argument `lhs`
 407 and `this`.
 408      */
 409     DList opBinaryRight(string op, Stuff)(Stuff lhs)
 410     if (op == "~" && is(typeof(insertFront(lhs))))
 411     {
 412         auto ret = this.dup;
 413         ret.insertFront(lhs);
 414         return ret;
 415     }
 416
 417 /**
 418 Appends the contents of the argument `rhs` into `this`.
 419      */
 420     DList opOpAssign(string op, Stuff)(Stuff rhs)
 421     if (op == "~" && is(typeof(insertBack(rhs))))
 422     {
 423         insertBack(rhs);
 424         return this;
 425     }
 426
 427 /+ ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ +/
 428 /+                        BEGIN INSERT FUNCTIONS HERE                         +/
 429 /+ ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ +/
 430
 431 /**
 432 Inserts `stuff` to the front/back of the container. `stuff` can be a
 433 value convertible to `T` or a range of objects convertible to $(D
 434 T). The stable version behaves the same, but guarantees that ranges
 435 iterating over the container are never invalidated.
 436
 437 Returns: The number of elements inserted
 438
 439 Complexity: $(BIGOH log(n))
 440      */
 441     size_t insertFront(Stuff)(Stuff stuff)
 442     {
 443         initialize();
 444         return insertAfterNode(_root, stuff);
 445     }
 446
 447     /// ditto
 448     size_t insertBack(Stuff)(Stuff stuff)
 449     {
 450         initialize();
 451         return insertBeforeNode(_root, stuff);
 452     }
 453
 454     /// ditto
 455     alias insert = insertBack;
 456
 457     /// ditto
 458     alias stableInsert = insert;
 459
 460     /// ditto
 461     alias stableInsertFront = insertFront;
 462
 463     /// ditto
 464     alias stableInsertBack = insertBack;
 465
 466 /**
 467 Inserts `stuff` after range `r`, which must be a non-empty range
 468 previously extracted from this container.
 469
 470 `stuff` can be a value convertible to `T` or a range of objects
 471 convertible to `T`. The stable version behaves the same, but
 472 guarantees that ranges iterating over the container are never
 473 invalidated.
 474
 475 Returns: The number of values inserted.
 476
 477 Complexity: $(BIGOH k + m), where `k` is the number of elements in
 478 `r` and `m` is the length of `stuff`.
 479      */
 480     size_t insertBefore(Stuff)(Range r, Stuff stuff)
 481     {
 482         if (r._first)
 483             return insertBeforeNode(r._first, stuff);
 484         else
 485         {
 486             initialize();
 487             return insertAfterNode(_root, stuff);
 488         }
 489     }
 490
 491     /// ditto
 492     alias stableInsertBefore = insertBefore;
 493
 494     /// ditto
 495     size_t insertAfter(Stuff)(Range r, Stuff stuff)
 496     {
 497         if (r._last)
 498             return insertAfterNode(r._last, stuff);
 499         else
 500         {
 501             initialize();
 502             return insertBeforeNode(_root, stuff);
 503         }
 504     }
 505
 506     /// ditto
 507     alias stableInsertAfter = insertAfter;
 508
 509 /+ ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ +/
 510 /+                        BEGIN REMOVE FUNCTIONS HERE                         +/
 511 /+ ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ +/
 512
 513 /**
 514 Picks one value in an unspecified position in the container, removes
 515 it from the container, and returns it. The stable version behaves the same,
 516 but guarantees that ranges iterating over the container are never invalidated.
 517
 518 Precondition: `!empty`
 519
 520 Returns: The element removed.
 521
 522 Complexity: $(BIGOH 1).
 523      */
 524     T removeAny()
 525     {
 526         import std.algorithm.mutation : move;
 527
 528         assert(!empty, "DList.removeAny: List is empty");
 529         auto result = move(back);
 530         removeBack();
 531         return result;
 532     }
 533     /// ditto
 534     alias stableRemoveAny = removeAny;
 535
 536 /**
 537 Removes the value at the front/back of the container. The stable version
 538 behaves the same, but guarantees that ranges iterating over the
 539 container are never invalidated.
 540
 541 Precondition: `!empty`
 542
 543 Complexity: $(BIGOH 1).
 544      */
 545     void removeFront()
 546     {
 547         assert(!empty, "DList.removeFront: List is empty");
 548         assert(_root is _first._prev, "DList: Inconsistent state");
 549         BaseNode.connect(_root, _first._next);
 550     }
 551
 552     /// ditto
 553     alias stableRemoveFront = removeFront;
 554
 555     /// ditto
 556     void removeBack()
 557     {
 558         assert(!empty, "DList.removeBack: List is empty");
 559         assert(_last._next is _root, "DList: Inconsistent state");
 560         BaseNode.connect(_last._prev, _root);
 561     }
 562
 563     /// ditto
 564     alias stableRemoveBack = removeBack;
 565
 566 /**
 567 Removes `howMany` values at the front or back of the
 568 container. Unlike the unparameterized versions above, these functions
 569 do not throw if they could not remove `howMany` elements. Instead,
 570 if $(D howMany > n), all elements are removed. The returned value is
 571 the effective number of elements removed. The stable version behaves
 572 the same, but guarantees that ranges iterating over the container are
 573 never invalidated.
 574
 575 Returns: The number of elements removed
 576
 577 Complexity: $(BIGOH howMany).
 578      */
 579     size_t removeFront(size_t howMany)
 580     {
 581         if (!_root) return 0;
 582         size_t result;
 583         auto p = _first;
 584         while (p !is _root && result < howMany)
 585         {
 586             p = p._next;
 587             ++result;
 588         }
 589         BaseNode.connect(_root, p);
 590         return result;
 591     }
 592
 593     /// ditto
 594     alias stableRemoveFront = removeFront;
 595
 596     /// ditto
 597     size_t removeBack(size_t howMany)
 598     {
 599         if (!_root) return 0;
 600         size_t result;
 601         auto p = _last;
 602         while (p !is _root && result < howMany)
 603         {
 604             p = p._prev;
 605             ++result;
 606         }
 607         BaseNode.connect(p, _root);
 608         return result;
 609     }
 610
 611     /// ditto
 612     alias stableRemoveBack = removeBack;
 613
 614 /**
 615 Removes all elements belonging to `r`, which must be a range
 616 obtained originally from this container.
 617
 618 Returns: A range spanning the remaining elements in the container that
 619 initially were right after `r`.
 620
 621 Complexity: $(BIGOH 1)
 622      */
 623     Range remove(Range r)
 624     {
 625         if (r.empty)
 626             return r;
 627
 628         assert(_root !is null, "Cannot remove from an un-initialized List");
 629         assert(r._first, "Remove: Range is empty");
 630
 631         BaseNode.connect(r._first._prev, r._last._next);
 632         auto after = r._last._next;
 633         if (after is _root)
 634             return Range(null, null);
 635         else
 636             return Range(after, _last);
 637     }
 638
 639     /// ditto
 640     Range linearRemove(Range r)
 641     {
 642         return remove(r);
 643     }
 644
 645     /// ditto
 646     alias stableRemove = remove;
 647
 648 /**
 649 Removes first element of `r`, wich must be a range obtained originally
 650 from this container, from both DList instance and range `r`.
 651
 652 Compexity: $(BIGOH 1)
 653      */
 654     void popFirstOf(ref Range r)
 655     {
 656         assert(_root !is null, "Cannot remove from an un-initialized List");
 657         assert(r._first, "popFirstOf: Range is empty");
 658         auto prev = r._first._prev;
 659         auto next = r._first._next;
 660         r.popFront();
 661         BaseNode.connect(prev, next);
 662     }
 663
 664 /**
 665 Removes last element of `r`, wich must be a range obtained originally
 666 from this container, from both DList instance and range `r`.
 667
 668 Compexity: $(BIGOH 1)
 669      */
 670     void popLastOf(ref Range r)
 671     {
 672         assert(_root !is null, "Cannot remove from an un-initialized List");
 673         assert(r._first, "popLastOf: Range is empty");
 674         auto prev = r._last._prev;
 675         auto next = r._last._next;
 676         r.popBack();
 677         BaseNode.connect(prev, next);
 678     }
 679
 680 /**
 681 `linearRemove` functions as `remove`, but also accepts ranges that are
 682 result the of a `take` operation. This is a convenient way to remove a
 683 fixed amount of elements from the range.
 684
 685 Complexity: $(BIGOH r.walkLength)
 686      */
 687     Range linearRemove(Take!Range r)
 688     {
 689         assert(_root !is null, "Cannot remove from an un-initialized List");
 690         assert(r.source._first, "Remove: Range is empty");
 691
 692         BaseNode* first = r.source._first;
 693         BaseNode* last = null;
 694         do
 695         {
 696             last = r.source._first;
 697             r.popFront();
 698         } while ( !r.empty );
 699
 700         return remove(Range(first, last));
 701     }
 702
 703     /// ditto
 704     alias stableLinearRemove = linearRemove;
 705
 706 /**
 707 Removes the first occurence of an element from the list in linear time.
 708
 709 Returns: True if the element existed and was successfully removed, false otherwise.
 710
 711 Params:
 712     value = value of the node to be removed
 713
 714 Complexity: $(BIGOH n)
 715      */
 716     bool linearRemoveElement(T value)
 717     {
 718         auto n1 = findNodeByValue(_root, value);
 719         if (n1)
 720         {
 721             auto n2 = n1._next._next;
 722             BaseNode.connect(n1, n2);
 723             return true;
 724         }
 725
 726         return false;
 727     }
 728
 729
 730 private:
 731
 732     BaseNode* findNodeByValue(BaseNode* n, T value)
 733     {
 734         if (!n) return null;
 735         auto ahead = n._next;
 736         while (ahead && ahead.getPayload!T() != value)
 737         {
 738             n = ahead;
 739             ahead = n._next;
 740             if (ahead == _last._next) return null;
 741         }
 742         return n;
 743     }
 744
 745     // Helper: Inserts stuff before the node n.
 746     size_t insertBeforeNode(Stuff)(BaseNode* n, ref Stuff stuff)
 747     if (isImplicitlyConvertible!(Stuff, T))
 748     {
 749         auto p = createNode(stuff, n._prev, n);
 750         n._prev._next = p;
 751         n._prev = p;
 752         return 1;
 753     }
 754     // ditto
 755     size_t insertBeforeNode(Stuff)(BaseNode* n, ref Stuff stuff)
 756     if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T))
 757     {
 758         if (stuff.empty) return 0;
 759         size_t result;
 760         Range r = createRange(stuff, result);
 761         BaseNode.connect(n._prev, r._first);
 762         BaseNode.connect(r._last, n);
 763         return result;
 764     }
 765
 766     // Helper: Inserts stuff after the node n.
 767     size_t insertAfterNode(Stuff)(BaseNode* n, ref Stuff stuff)
 768     if (isImplicitlyConvertible!(Stuff, T))
 769     {
 770         auto p = createNode(stuff, n, n._next);
 771         n._next._prev = p;
 772         n._next = p;
 773         return 1;
 774     }
 775     // ditto
 776     size_t insertAfterNode(Stuff)(BaseNode* n, ref Stuff stuff)
 777     if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T))
 778     {
 779         if (stuff.empty) return 0;
 780         size_t result;
 781         Range r = createRange(stuff, result);
 782         BaseNode.connect(r._last, n._next);
 783         BaseNode.connect(n, r._first);
 784         return result;
 785     }
 786
 787     // Helper: Creates a chain of nodes from the range stuff.
 788     Range createRange(Stuff)(ref Stuff stuff, ref size_t result)
 789     {
 790         BaseNode* first = createNode(stuff.front);
 791         BaseNode* last = first;
 792         ++result;
 793         for ( stuff.popFront() ; !stuff.empty ; stuff.popFront() )
 794         {
 795             auto p = createNode(stuff.front, last);
 796             last = last._next = p;
 797             ++result;
 798         }
 799         return Range(first, last);
 800     }
 801 }
 802
 803 @safe unittest
 804 {
 805     import std.algorithm.comparison : equal;
 806
 807     auto e = DList!int();
 808     auto b = e.linearRemoveElement(1);
 809     assert(b == false);
 810     assert(e.empty());
 811     auto a = DList!int(-1, 1, 2, 1, 3, 4);
 812     b = a.linearRemoveElement(1);
 813     assert(equal(a[], [-1, 2, 1, 3, 4]));
 814     assert(b == true);
 815     b = a.linearRemoveElement(-1);
 816     assert(b == true);
 817     assert(equal(a[], [2, 1, 3, 4]));
 818     b = a.linearRemoveElement(1);
 819     assert(b == true);
 820     assert(equal(a[], [2, 3, 4]));
 821     b = a.linearRemoveElement(2);
 822     assert(b == true);
 823     b = a.linearRemoveElement(20);
 824     assert(b == false);
 825     assert(equal(a[], [3, 4]));
 826     b = a.linearRemoveElement(4);
 827     assert(b == true);
 828     assert(equal(a[], [3]));
 829     b = a.linearRemoveElement(3);
 830     assert(b == true);
 831     assert(a.empty());
 832     a.linearRemoveElement(3);
 833 }
 834
 835 @safe unittest
 836 {
 837     import std.algorithm.comparison : equal;
 838
 839     //Tests construction signatures
 840     alias IntList = DList!int;
 841     auto a0 = IntList();
 842     auto a1 = IntList(0);
 843     auto a2 = IntList(0, 1);
 844     auto a3 = IntList([0]);
 845     auto a4 = IntList([0, 1]);
 846
 847     assert(a0[].empty);
 848     assert(equal(a1[], [0]));
 849     assert(equal(a2[], [0, 1]));
 850     assert(equal(a3[], [0]));
 851     assert(equal(a4[], [0, 1]));
 852 }
 853
 854 @safe unittest
 855 {
 856     import std.algorithm.comparison : equal;
 857
 858     alias IntList = DList!int;
 859     IntList list = IntList([0,1,2,3]);
 860     assert(equal(list[],[0,1,2,3]));
 861     list.insertBack([4,5,6,7]);
 862     assert(equal(list[],[0,1,2,3,4,5,6,7]));
 863
 864     list = IntList();
 865     list.insertFront([0,1,2,3]);
 866     assert(equal(list[],[0,1,2,3]));
 867     list.insertFront([4,5,6,7]);
 868     assert(equal(list[],[4,5,6,7,0,1,2,3]));
 869 }
 870
 871 @safe unittest
 872 {
 873     import std.algorithm.comparison : equal;
 874     import std.range : take;
 875
 876     alias IntList = DList!int;
 877     IntList list = IntList([0,1,2,3]);
 878     auto range = list[];
 879     for ( ; !range.empty; range.popFront())
 880     {
 881         int item = range.front;
 882         if (item == 2)
 883         {
 884             list.stableLinearRemove(take(range, 1));
 885             break;
 886         }
 887     }
 888     assert(equal(list[],[0,1,3]));
 889
 890     list = IntList([0,1,2,3]);
 891     range = list[];
 892     for ( ; !range.empty; range.popFront())
 893     {
 894         int item = range.front;
 895         if (item == 2)
 896         {
 897             list.stableLinearRemove(take(range,2));
 898             break;
 899         }
 900     }
 901     assert(equal(list[],[0,1]));
 902
 903     list = IntList([0,1,2,3]);
 904     range = list[];
 905     for ( ; !range.empty; range.popFront())
 906     {
 907         int item = range.front;
 908         if (item == 0)
 909         {
 910             list.stableLinearRemove(take(range,2));
 911             break;
 912         }
 913     }
 914     assert(equal(list[],[2,3]));
 915
 916     list = IntList([0,1,2,3]);
 917     range = list[];
 918     for ( ; !range.empty; range.popFront())
 919     {
 920         int item = range.front;
 921         if (item == 1)
 922         {
 923             list.stableLinearRemove(take(range,2));
 924             break;
 925         }
 926     }
 927     assert(equal(list[],[0,3]));
 928 }
 929
 930 @safe unittest
 931 {
 932     import std.algorithm.comparison : equal;
 933
 934     auto dl = DList!int([1, 2, 3, 4, 5]);
 935     auto r = dl[];
 936     r.popFront();
 937     dl.popFirstOf(r);
 938     assert(equal(dl[], [1, 3, 4, 5]));
 939     assert(equal(r, [3, 4, 5]));
 940     r.popBack();
 941     dl.popLastOf(r);
 942     assert(equal(dl[], [1, 3, 5]));
 943     assert(equal(r, [3]));
 944     dl = DList!int([0]);
 945     r = dl[];
 946     dl.popFirstOf(r);
 947     assert(dl.empty);
 948     dl = DList!int([0]);
 949     r = dl[];
 950     dl.popLastOf(r);
 951     assert(dl.empty);
 952 }
 953
 954 @safe unittest
 955 {
 956     import std.algorithm.comparison : equal;
 957
 958     auto dl = DList!string(["a", "b", "d"]);
 959     dl.insertAfter(dl[], "e"); // insert at the end
 960     assert(equal(dl[], ["a", "b", "d", "e"]));
 961     auto dlr = dl[];
 962     dlr.popBack(); dlr.popBack();
 963     dl.insertAfter(dlr, "c"); // insert after "b"
 964     assert(equal(dl[], ["a", "b", "c", "d", "e"]));
 965 }
 966
 967 @safe unittest
 968 {
 969     import std.algorithm.comparison : equal;
 970
 971     auto dl = DList!string(["a", "b", "d"]);
 972     dl.insertBefore(dl[], "e"); // insert at the front
 973     assert(equal(dl[], ["e", "a", "b", "d"]));
 974     auto dlr = dl[];
 975     dlr.popFront(); dlr.popFront();
 976     dl.insertBefore(dlr, "c"); // insert before "b"
 977     assert(equal(dl[], ["e", "a", "c", "b", "d"]));
 978 }
 979
 980 @safe unittest
 981 {
 982     auto d = DList!int([1, 2, 3]);
 983     d.front = 5; //test frontAssign
 984     assert(d.front == 5);
 985     auto r = d[];
 986     r.back = 1;
 987     assert(r.back == 1);
 988 }
 989
 990 // https://issues.dlang.org/show_bug.cgi?id=8895
 991 @safe unittest
 992 {
 993     auto a = make!(DList!int)(1,2,3,4);
 994     auto b = make!(DList!int)(1,2,3,4);
 995     auto c = make!(DList!int)(1,2,3,5);
 996     auto d = make!(DList!int)(1,2,3,4,5);
 997     assert(a == b); // this better terminate!
 998     assert(!(a == c));
 999     assert(!(a == d));
1000 }
1001
1002 @safe unittest
1003 {
1004     auto d = DList!int([1, 2, 3]);
1005     d.front = 5; //test frontAssign
1006     assert(d.front == 5);
1007     auto r = d[];
1008     r.back = 1;
1009     assert(r.back == 1);
1010 }
1011
1012 @safe unittest
1013 {
1014     auto a = DList!int();
1015     assert(a.removeFront(10) == 0);
1016     a.insert([1, 2, 3]);
1017     assert(a.removeFront(10) == 3);
1018     assert(a[].empty);
1019 }
1020
1021 @safe unittest
1022 {
1023     import std.algorithm.comparison : equal;
1024
1025     //Verify all flavors of ~
1026     auto a = DList!int();
1027     auto b = DList!int();
1028     auto c = DList!int([1, 2, 3]);
1029     auto d = DList!int([4, 5, 6]);
1030
1031     assert((a ~ b[])[].empty);
1032     assert((c ~ d[])[].equal([1, 2, 3, 4, 5, 6]));
1033     assert(c[].equal([1, 2, 3]));
1034     assert(d[].equal([4, 5, 6]));
1035
1036     assert((c[] ~ d)[].equal([1, 2, 3, 4, 5, 6]));
1037     assert(c[].equal([1, 2, 3]));
1038     assert(d[].equal([4, 5, 6]));
1039
1040     a~=c[];
1041     assert(a[].equal([1, 2, 3]));
1042     assert(c[].equal([1, 2, 3]));
1043
1044     a~=d[];
1045     assert(a[].equal([1, 2, 3, 4, 5, 6]));
1046     assert(d[].equal([4, 5, 6]));
1047
1048     a~=[7, 8, 9];
1049     assert(a[].equal([1, 2, 3, 4, 5, 6, 7, 8, 9]));
1050
1051     //trick test:
1052     auto r = c[];
1053     c.removeFront();
1054     c.removeBack();
1055 }
1056
1057 @safe unittest
1058 {
1059     import std.algorithm.comparison : equal;
1060
1061     // https://issues.dlang.org/show_bug.cgi?id=8905
1062     auto a = DList!int([1, 2, 3, 4]);
1063     auto r = a[];
1064     a.stableRemoveBack();
1065     a.stableInsertBack(7);
1066     assert(a[].equal([1, 2, 3, 7]));
1067 }
1068
1069 // https://issues.dlang.org/show_bug.cgi?id=12566
1070 @safe unittest
1071 {
1072     auto dl2 = DList!int([2,7]);
1073     dl2.removeFront();
1074     assert(dl2[].walkLength == 1);
1075     dl2.removeBack();
1076     assert(dl2.empty, "not empty?!");
1077 }
1078
1079 // https://issues.dlang.org/show_bug.cgi?id=13076
1080 @safe unittest
1081 {
1082     DList!int list;
1083     assert(list.empty);
1084     list.clear();
1085 }
1086
1087 // https://issues.dlang.org/show_bug.cgi?id=13425
1088 @safe unittest
1089 {
1090     import std.range : drop, take;
1091     auto list = DList!int([1,2,3,4,5]);
1092     auto r = list[].drop(4); // r is a view of the last element of list
1093     assert(r.front == 5 && r.walkLength == 1);
1094     r = list.linearRemove(r.take(1));
1095     assert(r.empty); // fails
1096 }
1097
1098 // https://issues.dlang.org/show_bug.cgi?id=14300
1099 @safe unittest
1100 {
1101     interface ITest {}
1102     static class Test : ITest {}
1103
1104     DList!ITest().insertBack(new Test());
1105 }
1106
1107 // https://issues.dlang.org/show_bug.cgi?id=15263
1108 @safe unittest
1109 {
1110     import std.range : iota;
1111     auto a = DList!int();
1112     a.insertFront(iota(0, 5)); // can insert range with non-ref front
1113     assert(a.front == 0 && a.back == 4);
1114 }