libphobos/src/std/container/slist.d

   1 /**
   2 This module implements a singly-linked list container.
   3 It can be used as a stack.
   4
   5 This module is a submodule of $(MREF std, container).
   6
   7 Source: $(PHOBOSSRC std/container/_slist.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.slist;
  20
  21 ///
  22 @safe unittest
  23 {
  24     import std.algorithm.comparison : equal;
  25     import std.container : SList;
  26
  27     auto s = SList!int(1, 2, 3);
  28     assert(equal(s[], [1, 2, 3]));
  29
  30     s.removeFront();
  31     assert(equal(s[], [2, 3]));
  32
  33     s.insertFront([5, 6]);
  34     assert(equal(s[], [5, 6, 2, 3]));
  35
  36     // If you want to apply range operations, simply slice it.
  37     import std.algorithm.searching : countUntil;
  38     import std.range : popFrontN, walkLength;
  39
  40     auto sl = SList!int(1, 2, 3, 4, 5);
  41     assert(countUntil(sl[], 2) == 1);
  42
  43     auto r = sl[];
  44     popFrontN(r, 2);
  45     assert(walkLength(r) == 3);
  46 }
  47
  48 public import std.container.util;
  49
  50 /**
  51    Implements a simple and fast singly-linked list.
  52    It can be used as a stack.
  53
  54    $(D SList) uses reference semantics.
  55  */
  56 struct SList(T)
  57 {
  58     import std.exception : enforce;
  59     import std.range : Take;
  60     import std.range.primitives : isInputRange, isForwardRange, ElementType;
  61     import std.traits : isImplicitlyConvertible;
  62
  63     private struct Node
  64     {
  65         Node * _next;
  66         T _payload;
  67     }
  68     private struct NodeWithoutPayload
  69     {
  70         Node* _next;
  71     }
  72     static assert(NodeWithoutPayload._next.offsetof == Node._next.offsetof);
  73
  74     private Node * _root;
  75
  76     private void initialize() @trusted nothrow pure
  77     {
  78         if (_root) return;
  79         _root = cast (Node*) new NodeWithoutPayload();
  80     }
  81
  82     private ref inout(Node*) _first() @property @safe nothrow pure inout
  83     {
  84         assert(_root);
  85         return _root._next;
  86     }
  87
  88     private static Node * findLastNode(Node * n)
  89     {
  90         assert(n);
  91         auto ahead = n._next;
  92         while (ahead)
  93         {
  94             n = ahead;
  95             ahead = n._next;
  96         }
  97         return n;
  98     }
  99
 100     private static Node * findLastNode(Node * n, size_t limit)
 101     {
 102         assert(n && limit);
 103         auto ahead = n._next;
 104         while (ahead)
 105         {
 106             if (!--limit) break;
 107             n = ahead;
 108             ahead = n._next;
 109         }
 110         return n;
 111     }
 112
 113     private static Node * findNode(Node * n, Node * findMe)
 114     {
 115         assert(n);
 116         auto ahead = n._next;
 117         while (ahead != findMe)
 118         {
 119             n = ahead;
 120             enforce(n);
 121             ahead = n._next;
 122         }
 123         return n;
 124     }
 125
 126 /**
 127 Constructor taking a number of nodes
 128      */
 129     this(U)(U[] values...) if (isImplicitlyConvertible!(U, T))
 130     {
 131         insertFront(values);
 132     }
 133
 134 /**
 135 Constructor taking an input range
 136      */
 137     this(Stuff)(Stuff stuff)
 138     if (isInputRange!Stuff
 139             && isImplicitlyConvertible!(ElementType!Stuff, T)
 140             && !is(Stuff == T[]))
 141     {
 142         insertFront(stuff);
 143     }
 144
 145 /**
 146 Comparison for equality.
 147
 148 Complexity: $(BIGOH min(n, n1)) where $(D n1) is the number of
 149 elements in $(D rhs).
 150      */
 151     bool opEquals(const SList rhs) const
 152     {
 153         return opEquals(rhs);
 154     }
 155
 156     /// ditto
 157     bool opEquals(ref const SList rhs) const
 158     {
 159         if (_root is rhs._root) return true;
 160         if (_root is null) return rhs._root is null || rhs._first is null;
 161         if (rhs._root is null) return _root is null || _first is null;
 162
 163         const(Node) * n1 = _first, n2 = rhs._first;
 164
 165         for (;; n1 = n1._next, n2 = n2._next)
 166         {
 167             if (!n1) return !n2;
 168             if (!n2 || n1._payload != n2._payload) return false;
 169         }
 170     }
 171
 172 /**
 173 Defines the container's primary range, which embodies a forward range.
 174      */
 175     struct Range
 176     {
 177         private Node * _head;
 178         private this(Node * p) { _head = p; }
 179
 180         /// Input range primitives.
 181         @property bool empty() const { return !_head; }
 182
 183         /// ditto
 184         @property ref T front()
 185         {
 186             assert(!empty, "SList.Range.front: Range is empty");
 187             return _head._payload;
 188         }
 189
 190         /// ditto
 191         void popFront()
 192         {
 193             assert(!empty, "SList.Range.popFront: Range is empty");
 194             _head = _head._next;
 195         }
 196
 197         /// Forward range primitive.
 198         @property Range save() { return this; }
 199
 200         T moveFront()
 201         {
 202             import std.algorithm.mutation : move;
 203
 204             assert(!empty, "SList.Range.moveFront: Range is empty");
 205             return move(_head._payload);
 206         }
 207
 208         bool sameHead(Range rhs)
 209         {
 210             return _head && _head == rhs._head;
 211         }
 212     }
 213
 214     @safe unittest
 215     {
 216         static assert(isForwardRange!Range);
 217     }
 218
 219 /**
 220 Property returning $(D true) if and only if the container has no
 221 elements.
 222
 223 Complexity: $(BIGOH 1)
 224      */
 225     @property bool empty() const
 226     {
 227         return _root is null || _first is null;
 228     }
 229
 230 /**
 231 Duplicates the container. The elements themselves are not transitively
 232 duplicated.
 233
 234 Complexity: $(BIGOH n).
 235      */
 236     @property SList dup()
 237     {
 238         return SList(this[]);
 239     }
 240
 241 /**
 242 Returns a range that iterates over all elements of the container, in
 243 forward order.
 244
 245 Complexity: $(BIGOH 1)
 246      */
 247     Range opSlice()
 248     {
 249         if (empty)
 250             return Range(null);
 251         else
 252             return Range(_first);
 253     }
 254
 255 /**
 256 Forward to $(D opSlice().front).
 257
 258 Complexity: $(BIGOH 1)
 259      */
 260     @property ref T front()
 261     {
 262         assert(!empty, "SList.front: List is empty");
 263         return _first._payload;
 264     }
 265
 266     @safe unittest
 267     {
 268         auto s = SList!int(1, 2, 3);
 269         s.front = 42;
 270         assert(s == SList!int(42, 2, 3));
 271     }
 272
 273 /**
 274 Returns a new $(D SList) that's the concatenation of $(D this) and its
 275 argument. $(D opBinaryRight) is only defined if $(D Stuff) does not
 276 define $(D opBinary).
 277      */
 278     SList opBinary(string op, Stuff)(Stuff rhs)
 279     if (op == "~" && is(typeof(SList(rhs))))
 280     {
 281         auto toAdd = SList(rhs);
 282         if (empty) return toAdd;
 283         // TODO: optimize
 284         auto result = dup;
 285         auto n = findLastNode(result._first);
 286         n._next = toAdd._first;
 287         return result;
 288     }
 289
 290     /// ditto
 291     SList opBinaryRight(string op, Stuff)(Stuff lhs)
 292     if (op == "~" && !is(typeof(lhs.opBinary!"~"(this))) && is(typeof(SList(lhs))))
 293     {
 294         auto toAdd = SList(lhs);
 295         if (empty) return toAdd;
 296         auto result = dup;
 297         result.insertFront(toAdd[]);
 298         return result;
 299     }
 300
 301 /**
 302 Removes all contents from the $(D SList).
 303
 304 Postcondition: $(D empty)
 305
 306 Complexity: $(BIGOH 1)
 307      */
 308     void clear()
 309     {
 310         if (_root)
 311             _first = null;
 312     }
 313
 314 /**
 315 Reverses SList in-place. Performs no memory allocation.
 316
 317 Complexity: $(BIGOH n)
 318      */
 319     void reverse()
 320     {
 321         if (!empty)
 322         {
 323             Node* prev;
 324             while (_first)
 325             {
 326                 auto next = _first._next;
 327                 _first._next = prev;
 328                 prev = _first;
 329                 _first = next;
 330             }
 331             _first = prev;
 332         }
 333     }
 334
 335 /**
 336 Inserts $(D stuff) to the front of the container. $(D stuff) can be a
 337 value convertible to $(D T) or a range of objects convertible to $(D
 338 T). The stable version behaves the same, but guarantees that ranges
 339 iterating over the container are never invalidated.
 340
 341 Returns: The number of elements inserted
 342
 343 Complexity: $(BIGOH m), where $(D m) is the length of $(D stuff)
 344      */
 345     size_t insertFront(Stuff)(Stuff stuff)
 346     if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T))
 347     {
 348         initialize();
 349         size_t result;
 350         Node * n, newRoot;
 351         foreach (item; stuff)
 352         {
 353             auto newNode = new Node(null, item);
 354             (newRoot ? n._next : newRoot) = newNode;
 355             n = newNode;
 356             ++result;
 357         }
 358         if (!n) return 0;
 359         // Last node points to the old root
 360         n._next = _first;
 361         _first = newRoot;
 362         return result;
 363     }
 364
 365     /// ditto
 366     size_t insertFront(Stuff)(Stuff stuff)
 367     if (isImplicitlyConvertible!(Stuff, T))
 368     {
 369         initialize();
 370         auto newRoot = new Node(_first, stuff);
 371         _first = newRoot;
 372         return 1;
 373     }
 374
 375 /// ditto
 376     alias insert = insertFront;
 377
 378 /// ditto
 379     alias stableInsert = insert;
 380
 381     /// ditto
 382     alias stableInsertFront = insertFront;
 383
 384 /**
 385 Picks one value in an unspecified position in the container, removes
 386 it from the container, and returns it. The stable version behaves the same,
 387 but guarantees that ranges iterating over the container are never invalidated.
 388
 389 Precondition: $(D !empty)
 390
 391 Returns: The element removed.
 392
 393 Complexity: $(BIGOH 1).
 394      */
 395     T removeAny()
 396     {
 397         import std.algorithm.mutation : move;
 398
 399         assert(!empty, "SList.removeAny: List is empty");
 400         auto result = move(_first._payload);
 401         _first = _first._next;
 402         return result;
 403     }
 404     /// ditto
 405     alias stableRemoveAny = removeAny;
 406
 407 /**
 408 Removes the value at the front of the container. The stable version
 409 behaves the same, but guarantees that ranges iterating over the
 410 container are never invalidated.
 411
 412 Precondition: $(D !empty)
 413
 414 Complexity: $(BIGOH 1).
 415      */
 416     void removeFront()
 417     {
 418         assert(!empty, "SList.removeFront: List is empty");
 419         _first = _first._next;
 420     }
 421
 422     /// ditto
 423     alias stableRemoveFront = removeFront;
 424
 425 /**
 426 Removes $(D howMany) values at the front or back of the
 427 container. Unlike the unparameterized versions above, these functions
 428 do not throw if they could not remove $(D howMany) elements. Instead,
 429 if $(D howMany > n), all elements are removed. The returned value is
 430 the effective number of elements removed. The stable version behaves
 431 the same, but guarantees that ranges iterating over the container are
 432 never invalidated.
 433
 434 Returns: The number of elements removed
 435
 436 Complexity: $(BIGOH howMany * log(n)).
 437      */
 438     size_t removeFront(size_t howMany)
 439     {
 440         size_t result;
 441         while (_first && result < howMany)
 442         {
 443             _first = _first._next;
 444             ++result;
 445         }
 446         return result;
 447     }
 448
 449     /// ditto
 450     alias stableRemoveFront = removeFront;
 451
 452 /**
 453 Inserts $(D stuff) after range $(D r), which must be a range
 454 previously extracted from this container. Given that all ranges for a
 455 list end at the end of the list, this function essentially appends to
 456 the list and uses $(D r) as a potentially fast way to reach the last
 457 node in the list. Ideally $(D r) is positioned near or at the last
 458 element of the list.
 459
 460 $(D stuff) can be a value convertible to $(D T) or a range of objects
 461 convertible to $(D T). The stable version behaves the same, but
 462 guarantees that ranges iterating over the container are never
 463 invalidated.
 464
 465 Returns: The number of values inserted.
 466
 467 Complexity: $(BIGOH k + m), where $(D k) is the number of elements in
 468 $(D r) and $(D m) is the length of $(D stuff).
 469
 470 Example:
 471 --------------------
 472 auto sl = SList!string(["a", "b", "d"]);
 473 sl.insertAfter(sl[], "e"); // insert at the end (slowest)
 474 assert(std.algorithm.equal(sl[], ["a", "b", "d", "e"]));
 475 sl.insertAfter(std.range.take(sl[], 2), "c"); // insert after "b"
 476 assert(std.algorithm.equal(sl[], ["a", "b", "c", "d", "e"]));
 477 --------------------
 478      */
 479
 480     size_t insertAfter(Stuff)(Range r, Stuff stuff)
 481     {
 482         initialize();
 483         if (!_first)
 484         {
 485             enforce(!r._head);
 486             return insertFront(stuff);
 487         }
 488         enforce(r._head);
 489         auto n = findLastNode(r._head);
 490         SList tmp;
 491         auto result = tmp.insertFront(stuff);
 492         n._next = tmp._first;
 493         return result;
 494     }
 495
 496 /**
 497 Similar to $(D insertAfter) above, but accepts a range bounded in
 498 count. This is important for ensuring fast insertions in the middle of
 499 the list.  For fast insertions after a specified position $(D r), use
 500 $(D insertAfter(take(r, 1), stuff)). The complexity of that operation
 501 only depends on the number of elements in $(D stuff).
 502
 503 Precondition: $(D r.original.empty || r.maxLength > 0)
 504
 505 Returns: The number of values inserted.
 506
 507 Complexity: $(BIGOH k + m), where $(D k) is the number of elements in
 508 $(D r) and $(D m) is the length of $(D stuff).
 509      */
 510     size_t insertAfter(Stuff)(Take!Range r, Stuff stuff)
 511     {
 512         auto orig = r.source;
 513         if (!orig._head)
 514         {
 515             // Inserting after a null range counts as insertion to the
 516             // front
 517             return insertFront(stuff);
 518         }
 519         enforce(!r.empty);
 520         // Find the last valid element in the range
 521         foreach (i; 1 .. r.maxLength)
 522         {
 523             if (!orig._head._next) break;
 524             orig.popFront();
 525         }
 526         // insert here
 527         SList tmp;
 528         tmp.initialize();
 529         tmp._first = orig._head._next;
 530         auto result = tmp.insertFront(stuff);
 531         orig._head._next = tmp._first;
 532         return result;
 533     }
 534
 535 /// ditto
 536     alias stableInsertAfter = insertAfter;
 537
 538 /**
 539 Removes a range from the list in linear time.
 540
 541 Returns: An empty range.
 542
 543 Complexity: $(BIGOH n)
 544      */
 545     Range linearRemove(Range r)
 546     {
 547         if (!_first)
 548         {
 549             enforce(!r._head);
 550             return this[];
 551         }
 552         auto n = findNode(_root, r._head);
 553         n._next = null;
 554         return Range(null);
 555     }
 556
 557 /**
 558 Removes a $(D Take!Range) from the list in linear time.
 559
 560 Returns: A range comprehending the elements after the removed range.
 561
 562 Complexity: $(BIGOH n)
 563      */
 564     Range linearRemove(Take!Range r)
 565     {
 566         auto orig = r.source;
 567         // We have something to remove here
 568         if (orig._head == _first)
 569         {
 570             // remove straight from the head of the list
 571             for (; !r.empty; r.popFront())
 572             {
 573                 removeFront();
 574             }
 575             return this[];
 576         }
 577         if (!r.maxLength)
 578         {
 579             // Nothing to remove, return the range itself
 580             return orig;
 581         }
 582         // Remove from somewhere in the middle of the list
 583         enforce(_first);
 584         auto n1 = findNode(_root, orig._head);
 585         auto n2 = findLastNode(orig._head, r.maxLength);
 586         n1._next = n2._next;
 587         return Range(n1._next);
 588     }
 589
 590 /// ditto
 591     alias stableLinearRemove = linearRemove;
 592 }
 593
 594 @safe unittest
 595 {
 596     import std.algorithm.comparison : equal;
 597
 598     auto a = SList!int(5);
 599     auto b = a;
 600     auto r = a[];
 601     a.insertFront(1);
 602     b.insertFront(2);
 603     assert(equal(a[], [2, 1, 5]));
 604     assert(equal(b[], [2, 1, 5]));
 605     r.front = 9;
 606     assert(equal(a[], [2, 1, 9]));
 607     assert(equal(b[], [2, 1, 9]));
 608 }
 609
 610 @safe unittest
 611 {
 612     auto s = SList!int(1, 2, 3);
 613     auto n = s.findLastNode(s._root);
 614     assert(n && n._payload == 3);
 615 }
 616
 617 @safe unittest
 618 {
 619     import std.range.primitives;
 620     auto s = SList!int(1, 2, 5, 10);
 621     assert(walkLength(s[]) == 4);
 622 }
 623
 624 @safe unittest
 625 {
 626     import std.range : take;
 627     auto src = take([0, 1, 2, 3], 3);
 628     auto s = SList!int(src);
 629     assert(s == SList!int(0, 1, 2));
 630 }
 631
 632 @safe unittest
 633 {
 634     auto a = SList!int();
 635     auto b = SList!int();
 636     auto c = a ~ b[];
 637     assert(c.empty);
 638 }
 639
 640 @safe unittest
 641 {
 642     auto a = SList!int(1, 2, 3);
 643     auto b = SList!int(4, 5, 6);
 644     auto c = a ~ b[];
 645     assert(c == SList!int(1, 2, 3, 4, 5, 6));
 646 }
 647
 648 @safe unittest
 649 {
 650     auto a = SList!int(1, 2, 3);
 651     auto b = [4, 5, 6];
 652     auto c = a ~ b;
 653     assert(c == SList!int(1, 2, 3, 4, 5, 6));
 654 }
 655
 656 @safe unittest
 657 {
 658     auto a = SList!int(1, 2, 3);
 659     auto c = a ~ 4;
 660     assert(c == SList!int(1, 2, 3, 4));
 661 }
 662
 663 @safe unittest
 664 {
 665     auto a = SList!int(2, 3, 4);
 666     auto b = 1 ~ a;
 667     assert(b == SList!int(1, 2, 3, 4));
 668 }
 669
 670 @safe unittest
 671 {
 672     auto a = [1, 2, 3];
 673     auto b = SList!int(4, 5, 6);
 674     auto c = a ~ b;
 675     assert(c == SList!int(1, 2, 3, 4, 5, 6));
 676 }
 677
 678 @safe unittest
 679 {
 680     auto s = SList!int(1, 2, 3, 4);
 681     s.insertFront([ 42, 43 ]);
 682     assert(s == SList!int(42, 43, 1, 2, 3, 4));
 683 }
 684
 685 @safe unittest
 686 {
 687     auto s = SList!int(1, 2, 3);
 688     assert(s.removeAny() == 1);
 689     assert(s == SList!int(2, 3));
 690     assert(s.stableRemoveAny() == 2);
 691     assert(s == SList!int(3));
 692 }
 693
 694 @safe unittest
 695 {
 696     import std.algorithm.comparison : equal;
 697
 698     auto s = SList!int(1, 2, 3);
 699     s.removeFront();
 700     assert(equal(s[], [2, 3]));
 701     s.stableRemoveFront();
 702     assert(equal(s[], [3]));
 703 }
 704
 705 @safe unittest
 706 {
 707     auto s = SList!int(1, 2, 3, 4, 5, 6, 7);
 708     assert(s.removeFront(3) == 3);
 709     assert(s == SList!int(4, 5, 6, 7));
 710 }
 711
 712 @safe unittest
 713 {
 714     auto a = SList!int(1, 2, 3);
 715     auto b = SList!int(1, 2, 3);
 716     assert(a.insertAfter(a[], b[]) == 3);
 717 }
 718
 719 @safe unittest
 720 {
 721     import std.range : take;
 722     auto s = SList!int(1, 2, 3, 4);
 723     auto r = take(s[], 2);
 724     assert(s.insertAfter(r, 5) == 1);
 725     assert(s == SList!int(1, 2, 5, 3, 4));
 726 }
 727
 728 @safe unittest
 729 {
 730     import std.algorithm.comparison : equal;
 731     import std.range : take;
 732
 733     // insertAfter documentation example
 734     auto sl = SList!string(["a", "b", "d"]);
 735     sl.insertAfter(sl[], "e"); // insert at the end (slowest)
 736     assert(equal(sl[], ["a", "b", "d", "e"]));
 737     sl.insertAfter(take(sl[], 2), "c"); // insert after "b"
 738     assert(equal(sl[], ["a", "b", "c", "d", "e"]));
 739 }
 740
 741 @safe unittest
 742 {
 743     import std.range.primitives;
 744     auto s = SList!int(1, 2, 3, 4, 5);
 745     auto r = s[];
 746     popFrontN(r, 3);
 747     auto r1 = s.linearRemove(r);
 748     assert(s == SList!int(1, 2, 3));
 749     assert(r1.empty);
 750 }
 751
 752 @safe unittest
 753 {
 754     auto s = SList!int(1, 2, 3, 4, 5);
 755     auto r = s[];
 756     auto r1 = s.linearRemove(r);
 757     assert(s == SList!int());
 758     assert(r1.empty);
 759 }
 760
 761 @safe unittest
 762 {
 763     import std.algorithm.comparison : equal;
 764     import std.range;
 765
 766     auto s = SList!int(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);
 767     auto r = s[];
 768     popFrontN(r, 3);
 769     auto r1 = take(r, 4);
 770     assert(equal(r1, [4, 5, 6, 7]));
 771     auto r2 = s.linearRemove(r1);
 772     assert(s == SList!int(1, 2, 3, 8, 9, 10));
 773     assert(equal(r2, [8, 9, 10]));
 774 }
 775
 776 @safe unittest
 777 {
 778     import std.range.primitives;
 779     auto lst = SList!int(1, 5, 42, 9);
 780     assert(!lst.empty);
 781     assert(lst.front == 1);
 782     assert(walkLength(lst[]) == 4);
 783
 784     auto lst2 = lst ~ [ 1, 2, 3 ];
 785     assert(walkLength(lst2[]) == 7);
 786
 787     auto lst3 = lst ~ [ 7 ];
 788     assert(walkLength(lst3[]) == 5);
 789 }
 790
 791 @safe unittest
 792 {
 793     auto s = make!(SList!int)(1, 2, 3);
 794 }
 795
 796 @safe unittest
 797 {
 798     // 5193
 799     static struct Data
 800     {
 801         const int val;
 802     }
 803     SList!Data list;
 804 }
 805
 806 @safe unittest
 807 {
 808     auto s = SList!int([1, 2, 3]);
 809     s.front = 5; //test frontAssign
 810     assert(s.front == 5);
 811     auto r = s[];
 812     r.front = 1; //test frontAssign
 813     assert(r.front == 1);
 814 }
 815
 816 @safe unittest
 817 {
 818     // issue 14920
 819     SList!int s;
 820     s.insertAfter(s[], 1);
 821     assert(s.front == 1);
 822 }
 823
 824 @safe unittest
 825 {
 826     // issue 15659
 827     SList!int s;
 828     s.clear();
 829 }
 830
 831 @safe unittest
 832 {
 833     SList!int s;
 834     s.reverse();
 835 }
 836
 837 @safe unittest
 838 {
 839     import std.algorithm.comparison : equal;
 840
 841     auto s = SList!int([1, 2, 3]);
 842     assert(s[].equal([1, 2, 3]));
 843
 844     s.reverse();
 845     assert(s[].equal([3, 2, 1]));
 846 }