1 // Written in the D programming language. 2 3 /** 4 This module defines generic containers. 5 6 Construction: 7 8 To implement the different containers both struct and class based 9 approaches have been used. $(REF make, std,container,util) allows for 10 uniform construction with either approach. 11 12 --- 13 import std.container; 14 // Construct a red-black tree and an array both containing the values 1, 2, 3. 15 // RedBlackTree should typically be allocated using `new` 16 RedBlackTree!int rbTree = new RedBlackTree!int(1, 2, 3); 17 // But `new` should not be used with Array 18 Array!int array = Array!int(1, 2, 3); 19 // `make` hides the differences 20 RedBlackTree!int rbTree2 = make!(RedBlackTree!int)(1, 2, 3); 21 Array!int array2 = make!(Array!int)(1, 2, 3); 22 --- 23 24 Note that `make` can infer the element type from the given arguments. 25 26 --- 27 import std.container; 28 auto rbTree = make!RedBlackTree(1, 2, 3); // RedBlackTree!int 29 auto array = make!Array("1", "2", "3"); // Array!string 30 --- 31 32 Reference_semantics: 33 34 All containers have reference semantics, which means that after 35 assignment both variables refer to the same underlying data. 36 37 To make a copy of a container, use the `c.dup` container primitive. 38 --- 39 import std.container, std.range; 40 Array!int originalArray = make!(Array!int)(1, 2, 3); 41 Array!int secondArray = originalArray; 42 assert(equal(originalArray[], secondArray[])); 43 44 // changing one instance changes the other one as well! 45 originalArray[0] = 12; 46 assert(secondArray[0] == 12); 47 48 // secondArray now refers to an independent copy of originalArray 49 secondArray = originalArray.dup; 50 secondArray[0] = 1; 51 // assert that originalArray has not been affected 52 assert(originalArray[0] == 12); 53 --- 54 55 $(B Attention:) If the container is implemented as a class, using an 56 uninitialized instance can cause a null pointer dereference. 57 58 --- 59 import std.container; 60 61 RedBlackTree!int rbTree; 62 rbTree.insert(5); // null pointer dereference 63 --- 64 65 Using an uninitialized struct-based container will work, because the struct 66 intializes itself upon use; however, up to this point the container will not 67 have an identity and assignment does not create two references to the same 68 data. 69 70 --- 71 import std.container; 72 73 // create an uninitialized array 74 Array!int array1; 75 // array2 does _not_ refer to array1 76 Array!int array2 = array1; 77 array2.insertBack(42); 78 // thus array1 will not be affected 79 assert(array1.empty); 80 81 // after initialization reference semantics work as expected 82 array1 = array2; 83 // now affects array2 as well 84 array1.removeBack(); 85 assert(array2.empty); 86 --- 87 It is therefore recommended to always construct containers using 88 $(REF make, std,container,util). 89 90 This is in fact necessary to put containers into another container. 91 For example, to construct an `Array` of ten empty `Array`s, use 92 the following that calls `make` ten times. 93 94 --- 95 import std.container, std.range; 96 97 auto arrOfArrs = make!Array(generate!(() => make!(Array!int)).take(10)); 98 --- 99 100 Submodules: 101 102 This module consists of the following submodules: 103 104 $(UL 105 $(LI 106 The $(MREF std, container, array) module provides 107 an array type with deterministic control of memory, not reliant on 108 the GC unlike built-in arrays. 109 ) 110 $(LI 111 The $(MREF std, container, binaryheap) module 112 provides a binary heap implementation that can be applied to any 113 user-provided random-access range. 114 ) 115 $(LI 116 The $(MREF std, container, dlist) module provides 117 a doubly-linked list implementation. 118 ) 119 $(LI 120 The $(MREF std, container, rbtree) module 121 implements red-black trees. 122 ) 123 $(LI 124 The $(MREF std, container, slist) module 125 implements singly-linked lists. 126 ) 127 $(LI 128 The $(MREF std, container, util) module contains 129 some generic tools commonly used by container implementations. 130 ) 131 ) 132 133 The_primary_range_of_a_container: 134 135 While some containers offer direct access to their elements e.g. via 136 `opIndex`, `c.front` or `c.back`, access 137 and modification of a container's contents is generally done through 138 its primary $(MREF_ALTTEXT range, std, range) type, 139 which is aliased as `C.Range`. For example, the primary range type of 140 `Array!int` is `Array!int.Range`. 141 142 If the documentation of a member function of a container takes 143 a parameter of type `Range`, then it refers to the primary range type of 144 this container. Oftentimes `Take!Range` will be used, in which case 145 the range refers to a span of the elements in the container. Arguments to 146 these parameters $(B must) be obtained from the same container instance 147 as the one being worked with. It is important to note that many generic range 148 algorithms return the same range type as their input range. 149 150 --- 151 import std.algorithm.comparison : equal; 152 import std.algorithm.iteration : find; 153 import std.container; 154 import std.range : take; 155 156 auto array = make!Array(1, 2, 3); 157 158 // `find` returns an Array!int.Range advanced to the element "2" 159 array.linearRemove(array[].find(2)); 160 161 assert(array[].equal([1])); 162 163 array = make!Array(1, 2, 3); 164 165 // the range given to `linearRemove` is a Take!(Array!int.Range) 166 // spanning just the element "2" 167 array.linearRemove(array[].find(2).take(1)); 168 169 assert(array[].equal([1, 3])); 170 --- 171 172 When any $(MREF_ALTTEXT range, std, range) can be passed as an argument to 173 a member function, the documention usually refers to the parameter's templated 174 type as `Stuff`. 175 176 --- 177 import std.algorithm.comparison : equal; 178 import std.container; 179 import std.range : iota; 180 181 auto array = make!Array(1, 2); 182 183 // the range type returned by `iota` is completely unrelated to Array, 184 // which is fine for Array.insertBack: 185 array.insertBack(iota(3, 10)); 186 187 assert(array[].equal([1, 2, 3, 4, 5, 6, 7, 8, 9])); 188 --- 189 190 Container_primitives: 191 192 Containers do not form a class hierarchy, instead they implement a 193 common set of primitives (see table below). These primitives each guarantee 194 a specific worst case complexity and thus allow generic code to be written 195 independently of the container implementation. 196 197 For example the primitives `c.remove(r)` and `c.linearRemove(r)` both 198 remove the sequence of elements in range `r` from the container `c`. 199 The primitive `c.remove(r)` guarantees 200 $(BIGOH n$(SUBSCRIPT r) log n$(SUBSCRIPT c)) complexity in the worst case and 201 `c.linearRemove(r)` relaxes this guarantee to $(BIGOH n$(SUBSCRIPT c)). 202 203 Since a sequence of elements can be removed from a $(MREF_ALTTEXT doubly linked list,std,container,dlist) 204 in constant time, `DList` provides the primitive `c.remove(r)` 205 as well as `c.linearRemove(r)`. On the other hand 206 $(MREF_ALTTEXT Array, std,container, array) only offers `c.linearRemove(r)`. 207 208 The following table describes the common set of primitives that containers 209 implement. A container need not implement all primitives, but if a 210 primitive is implemented, it must support the syntax described in the $(B 211 syntax) column with the semantics described in the $(B description) column, and 212 it must not have a worst-case complexity worse than denoted in big-O notation in 213 the $(BIGOH ·) column. Below, `C` means a container type, `c` is 214 a value of container type, $(D n$(SUBSCRIPT x)) represents the effective length of 215 value `x`, which could be a single element (in which case $(D n$(SUBSCRIPT x)) is 216 `1`), a container, or a range. 217 218 $(BOOKTABLE Container primitives, 219 $(TR 220 $(TH Syntax) 221 $(TH $(BIGOH ·)) 222 $(TH Description) 223 ) 224 $(TR 225 $(TDNW `C(x)`) 226 $(TDNW $(D n$(SUBSCRIPT x))) 227 $(TD Creates a container of type `C` from either another container or a range. 228 The created container must not be a null reference even if x is empty.) 229 ) 230 $(TR 231 $(TDNW `c.dup`) 232 $(TDNW $(D n$(SUBSCRIPT c))) 233 $(TD Returns a duplicate of the container.) 234 ) 235 $(TR 236 $(TDNW $(D c ~ x)) 237 $(TDNW $(D n$(SUBSCRIPT c) + n$(SUBSCRIPT x))) 238 $(TD Returns the concatenation of `c` and `r`. `x` may be a single 239 element or an input range.) 240 ) 241 $(TR 242 $(TDNW $(D x ~ c)) 243 $(TDNW $(D n$(SUBSCRIPT c) + n$(SUBSCRIPT x))) 244 $(TD Returns the concatenation of `x` and `c`. `x` may be a 245 single element or an input range type.) 246 ) 247 $(LEADINGROWN 3, Iteration 248 ) 249 $(TR 250 $(TD `c.Range`) 251 $(TD) 252 $(TD The primary range type associated with the container.) 253 ) 254 $(TR 255 $(TD `c[]`) 256 $(TDNW $(D log n$(SUBSCRIPT c))) 257 $(TD Returns a range 258 iterating over the entire container, in a container-defined order.) 259 ) 260 $(TR 261 $(TDNW $(D c[a .. b])) 262 $(TDNW $(D log n$(SUBSCRIPT c))) 263 $(TD Fetches a portion of the container from key `a` to key `b`.) 264 ) 265 $(LEADINGROWN 3, Capacity 266 ) 267 $(TR 268 $(TD `c.empty`) 269 $(TD `1`) 270 $(TD Returns `true` if the container has no elements, `false` otherwise.) 271 ) 272 $(TR 273 $(TD `c.length`) 274 $(TDNW $(D log n$(SUBSCRIPT c))) 275 $(TD Returns the number of elements in the container.) 276 ) 277 $(TR 278 $(TDNW $(D c.length = n)) 279 $(TDNW $(D n$(SUBSCRIPT c) + n)) 280 $(TD Forces the number of elements in the container to `n`. 281 If the container ends up growing, the added elements are initialized 282 in a container-dependent manner (usually with `T.init`).) 283 ) 284 $(TR 285 $(TD `c.capacity`) 286 $(TDNW $(D log n$(SUBSCRIPT c))) 287 $(TD Returns the maximum number of elements that can be stored in the 288 container without triggering a reallocation.) 289 ) 290 $(TR 291 $(TD `c.reserve(x)`) 292 $(TD $(D n$(SUBSCRIPT c))) 293 $(TD Forces `capacity` to at least `x` without reducing it.) 294 ) 295 $(LEADINGROWN 3, Access 296 ) 297 $(TR 298 $(TDNW `c.front`) 299 $(TDNW $(D log n$(SUBSCRIPT c))) 300 $(TD Returns the first element of the container, in a container-defined order.) 301 ) 302 $(TR 303 $(TDNW `c.moveFront`) 304 $(TDNW $(D log n$(SUBSCRIPT c))) 305 $(TD Destructively reads and returns the first element of the 306 container. The slot is not removed from the container; it is left 307 initialized with `T.init`. This routine need not be defined if $(D 308 front) returns a `ref`.) 309 ) 310 $(TR 311 $(TDNW $(D c.front = v)) 312 $(TDNW $(D log n$(SUBSCRIPT c))) 313 $(TD Assigns `v` to the first element of the container.) 314 ) 315 $(TR 316 $(TDNW `c.back`) 317 $(TDNW $(D log n$(SUBSCRIPT c))) 318 $(TD Returns the last element of the container, in a container-defined order.) 319 ) 320 $(TR 321 $(TDNW `c.moveBack`) 322 $(TDNW $(D log n$(SUBSCRIPT c))) 323 $(TD Destructively reads and returns the last element of the 324 container. The slot is not removed from the container; it is left 325 initialized with `T.init`. This routine need not be defined if $(D 326 front) returns a `ref`.) 327 ) 328 $(TR 329 $(TDNW $(D c.back = v)) 330 $(TDNW $(D log n$(SUBSCRIPT c))) 331 $(TD Assigns `v` to the last element of the container.) 332 ) 333 $(TR 334 $(TDNW `c[x]`) 335 $(TDNW $(D log n$(SUBSCRIPT c))) 336 $(TD Provides indexed access into the container. The index type is 337 container-defined. A container may define several index types (and 338 consequently overloaded indexing).) 339 ) 340 $(TR 341 $(TDNW `c.moveAt(x)`) 342 $(TDNW $(D log n$(SUBSCRIPT c))) 343 $(TD Destructively reads and returns the value at position `x`. The slot 344 is not removed from the container; it is left initialized with $(D 345 T.init).) 346 ) 347 $(TR 348 $(TDNW $(D c[x] = v)) 349 $(TDNW $(D log n$(SUBSCRIPT c))) 350 $(TD Sets element at specified index into the container.) 351 ) 352 $(TR 353 $(TDNW $(D c[x] $(I op)= v)) 354 $(TDNW $(D log n$(SUBSCRIPT c))) 355 $(TD Performs read-modify-write operation at specified index into the 356 container.) 357 ) 358 $(LEADINGROWN 3, Operations 359 ) 360 $(TR 361 $(TDNW $(D e in c)) 362 $(TDNW $(D log n$(SUBSCRIPT c))) 363 $(TD Returns nonzero if e is found in `c`.) 364 ) 365 $(TR 366 $(TDNW `c.lowerBound(v)`) 367 $(TDNW $(D log n$(SUBSCRIPT c))) 368 $(TD Returns a range of all elements strictly less than `v`.) 369 ) 370 $(TR 371 $(TDNW `c.upperBound(v)`) 372 $(TDNW $(D log n$(SUBSCRIPT c))) 373 $(TD Returns a range of all elements strictly greater than `v`.) 374 ) 375 $(TR 376 $(TDNW `c.equalRange(v)`) 377 $(TDNW $(D log n$(SUBSCRIPT c))) 378 $(TD Returns a range of all elements in `c` that are equal to `v`.) 379 ) 380 $(LEADINGROWN 3, Modifiers 381 ) 382 $(TR 383 $(TDNW $(D c ~= x)) 384 $(TDNW $(D n$(SUBSCRIPT c) + n$(SUBSCRIPT x))) 385 $(TD Appends `x` to `c`. `x` may be a single element or an input range type.) 386 ) 387 $(TR 388 $(TDNW `c.clear()`) 389 $(TDNW $(D n$(SUBSCRIPT c))) 390 $(TD Removes all elements in `c`.) 391 ) 392 $(TR 393 $(TDNW `c.insert(x)`) 394 $(TDNW $(D n$(SUBSCRIPT x) * log n$(SUBSCRIPT c))) 395 $(TD Inserts `x` in `c` at a position (or positions) chosen by `c`.) 396 ) 397 $(TR 398 $(TDNW `c.stableInsert(x)`) 399 $(TDNW $(D n$(SUBSCRIPT x) * log n$(SUBSCRIPT c))) 400 $(TD Same as `c.insert(x)`, but is guaranteed to not invalidate any ranges.) 401 ) 402 $(TR 403 $(TDNW `c.linearInsert(v)`) 404 $(TDNW $(D n$(SUBSCRIPT c))) 405 $(TD Same as `c.insert(v)` but relaxes complexity to linear.) 406 ) 407 $(TR 408 $(TDNW `c.stableLinearInsert(v)`) 409 $(TDNW $(D n$(SUBSCRIPT c))) 410 $(TD Same as `c.stableInsert(v)` but relaxes complexity to linear.) 411 ) 412 $(TR 413 $(TDNW `c.removeAny()`) 414 $(TDNW $(D log n$(SUBSCRIPT c))) 415 $(TD Removes some element from `c` and returns it.) 416 ) 417 $(TR 418 $(TDNW `c.stableRemoveAny()`) 419 $(TDNW $(D log n$(SUBSCRIPT c))) 420 $(TD Same as `c.removeAny()`, but is guaranteed to not invalidate any 421 iterators.) 422 ) 423 $(TR 424 $(TDNW `c.insertFront(v)`) 425 $(TDNW $(D log n$(SUBSCRIPT c))) 426 $(TD Inserts `v` at the front of `c`.) 427 ) 428 $(TR 429 $(TDNW `c.stableInsertFront(v)`) 430 $(TDNW $(D log n$(SUBSCRIPT c))) 431 $(TD Same as `c.insertFront(v)`, but guarantees no ranges will be 432 invalidated.) 433 ) 434 $(TR 435 $(TDNW `c.insertBack(v)`) 436 $(TDNW $(D log n$(SUBSCRIPT c))) 437 $(TD Inserts `v` at the back of `c`.) 438 ) 439 $(TR 440 $(TDNW `c.stableInsertBack(v)`) 441 $(TDNW $(D log n$(SUBSCRIPT c))) 442 $(TD Same as `c.insertBack(v)`, but guarantees no ranges will be 443 invalidated.) 444 ) 445 $(TR 446 $(TDNW `c.removeFront()`) 447 $(TDNW $(D log n$(SUBSCRIPT c))) 448 $(TD Removes the element at the front of `c`.) 449 ) 450 $(TR 451 $(TDNW `c.stableRemoveFront()`) 452 $(TDNW $(D log n$(SUBSCRIPT c))) 453 $(TD Same as `c.removeFront()`, but guarantees no ranges will be 454 invalidated.) 455 ) 456 $(TR 457 $(TDNW `c.removeBack()`) 458 $(TDNW $(D log n$(SUBSCRIPT c))) 459 $(TD Removes the value at the back of `c`.) 460 ) 461 $(TR 462 $(TDNW `c.stableRemoveBack()`) 463 $(TDNW $(D log n$(SUBSCRIPT c))) 464 $(TD Same as `c.removeBack()`, but guarantees no ranges will be 465 invalidated.) 466 ) 467 $(TR 468 $(TDNW `c.remove(r)`) 469 $(TDNW $(D n$(SUBSCRIPT r) * log n$(SUBSCRIPT c))) 470 $(TD Removes range `r` from `c`.) 471 ) 472 $(TR 473 $(TDNW `c.stableRemove(r)`) 474 $(TDNW $(D n$(SUBSCRIPT r) * log n$(SUBSCRIPT c))) 475 $(TD Same as `c.remove(r)`, but guarantees iterators are not 476 invalidated.) 477 ) 478 $(TR 479 $(TDNW `c.linearRemove(r)`) 480 $(TDNW $(D n$(SUBSCRIPT c))) 481 $(TD Removes range `r` from `c`.) 482 ) 483 $(TR 484 $(TDNW `c.stableLinearRemove(r)`) 485 $(TDNW $(D n$(SUBSCRIPT c))) 486 $(TD Same as `c.linearRemove(r)`, but guarantees iterators are not 487 invalidated.) 488 ) 489 $(TR 490 $(TDNW `c.removeKey(k)`) 491 $(TDNW $(D log n$(SUBSCRIPT c))) 492 $(TD Removes an element from `c` by using its key `k`. 493 The key's type is defined by the container.) 494 ) 495 ) 496 497 Source: $(PHOBOSSRC std/container/package.d) 498 499 Copyright: Red-black tree code copyright (C) 2008- by Steven Schveighoffer. Other code 500 copyright 2010- Andrei Alexandrescu. All rights reserved by the respective holders. 501 502 License: Distributed under the Boost Software License, Version 1.0. 503 (See accompanying file LICENSE_1_0.txt or copy at $(HTTP 504 boost.org/LICENSE_1_0.txt)). 505 506 Authors: Steven Schveighoffer, $(HTTP erdani.com, Andrei Alexandrescu) 507 */ 508 509 module std.container; 510 511 public import std.container.array; 512 public import std.container.binaryheap; 513 public import std.container.dlist; 514 public import std.container.rbtree; 515 public import std.container.slist; 516 517 import std.meta; 518 519 520 /* The following documentation and type `TotalContainer` are 521 intended for developers only. 522 523 `TotalContainer` is an unimplemented container that illustrates a 524 host of primitives that a container may define. It is to some extent 525 the bottom of the conceptual container hierarchy. A given container 526 most often will choose to only implement a subset of these primitives, 527 and define its own additional ones. Adhering to the standard primitive 528 names below allows generic code to work independently of containers. 529 530 Things to remember: any container must be a reference type, whether 531 implemented as a `class` or `struct`. No primitive below 532 requires the container to escape addresses of elements, which means 533 that compliant containers can be defined to use reference counting or 534 other deterministic memory management techniques. 535 536 A container may choose to define additional specific operations. The 537 only requirement is that those operations bear different names than 538 the ones below, lest user code gets confused. 539 540 Complexity of operations should be interpreted as "at least as good 541 as". If an operation is required to have $(BIGOH n) complexity, it 542 could have anything lower than that, e.g. $(BIGOH log(n)). Unless 543 specified otherwise, `n` inside a $(BIGOH) expression stands for 544 the number of elements in the container. 545 */ 546 struct TotalContainer(T) 547 { 548 /** 549 If the container has a notion of key-value mapping, `KeyType` 550 defines the type of the key of the container. 551 */ 552 alias KeyType = T; 553 554 /** 555 If the container has a notion of multikey-value mapping, $(D 556 KeyTypes[k]), where `k` is a zero-based unsigned number, defines 557 the type of the `k`th key of the container. 558 559 A container may define both `KeyType` and `KeyTypes`, e.g. in 560 the case it has the notion of primary/preferred key. 561 */ 562 alias KeyTypes = AliasSeq!T; 563 564 /** 565 If the container has a notion of key-value mapping, `ValueType` 566 defines the type of the value of the container. Typically, a map-style 567 container mapping values of type `K` to values of type `V` 568 defines `KeyType` to be `K` and `ValueType` to be `V`. 569 */ 570 alias ValueType = T; 571 572 /** 573 Defines the container's primary range, which embodies one of the 574 ranges defined in $(MREF std,range). 575 576 Generally a container may define several types of ranges. 577 */ 578 struct Range 579 { 580 /++ 581 Range primitives. 582 +/ 583 @property bool empty() 584 { 585 assert(0, "Not implemented"); 586 } 587 /// Ditto 588 @property ref T front() //ref return optional 589 { 590 assert(0, "Not implemented"); 591 } 592 /// Ditto 593 @property void front(T value) //Only when front does not return by ref 594 { 595 assert(0, "Not implemented"); 596 } 597 /// Ditto 598 T moveFront() 599 { 600 assert(0, "Not implemented"); 601 } 602 /// Ditto 603 void popFront() 604 { 605 assert(0, "Not implemented"); 606 } 607 /// Ditto 608 @property ref T back() //ref return optional 609 { 610 assert(0, "Not implemented"); 611 } 612 /// Ditto 613 @property void back(T value) //Only when front does not return by ref 614 { 615 assert(0, "Not implemented"); 616 } 617 /// Ditto 618 T moveBack() 619 { 620 assert(0, "Not implemented"); 621 } 622 /// Ditto 623 void popBack() 624 { 625 assert(0, "Not implemented"); 626 } 627 /// Ditto 628 T opIndex(size_t i) //ref return optional 629 { 630 assert(0, "Not implemented"); 631 } 632 /// Ditto 633 void opIndexAssign(size_t i, T value) //Only when front does not return by ref 634 { 635 assert(0, "Not implemented"); 636 } 637 /// Ditto 638 T opIndexUnary(string op)(size_t i) //Only when front does not return by ref 639 { 640 assert(0, "Not implemented"); 641 } 642 /// Ditto 643 void opIndexOpAssign(string op)(size_t i, T value) //Only when front does not return by ref 644 { 645 assert(0, "Not implemented"); 646 } 647 /// Ditto 648 T moveAt(size_t i) 649 { 650 assert(0, "Not implemented"); 651 } 652 /// Ditto 653 @property size_t length() 654 { 655 assert(0, "Not implemented"); 656 } 657 } 658 659 /** 660 Property returning `true` if and only if the container has no 661 elements. 662 663 Complexity: $(BIGOH 1) 664 */ 665 @property bool empty() 666 { 667 assert(0, "Not implemented"); 668 } 669 670 /** 671 Returns a duplicate of the container. The elements themselves are not 672 transitively duplicated. 673 674 Complexity: $(BIGOH n). 675 */ 676 @property TotalContainer dup() 677 { 678 assert(0, "Not implemented"); 679 } 680 681 /** 682 Returns the number of elements in the container. 683 684 Complexity: $(BIGOH log(n)). 685 */ 686 @property size_t length() 687 { 688 assert(0, "Not implemented"); 689 } 690 691 /** 692 Returns the maximum number of elements the container can store without 693 (a) allocating memory, (b) invalidating iterators upon insertion. 694 695 Complexity: $(BIGOH log(n)). 696 */ 697 @property size_t capacity() 698 { 699 assert(0, "Not implemented"); 700 } 701 702 /** 703 Ensures sufficient capacity to accommodate `n` elements. 704 705 Postcondition: $(D capacity >= n) 706 707 Complexity: $(BIGOH log(e - capacity)) if $(D e > capacity), otherwise 708 $(BIGOH 1). 709 */ 710 void reserve(size_t e) 711 { 712 assert(0, "Not implemented"); 713 } 714 715 /** 716 Returns a range that iterates over all elements of the container, in a 717 container-defined order. The container should choose the most 718 convenient and fast method of iteration for `opSlice()`. 719 720 Complexity: $(BIGOH log(n)) 721 */ 722 Range opSlice() 723 { 724 assert(0, "Not implemented"); 725 } 726 727 /** 728 Returns a range that iterates the container between two 729 specified positions. 730 731 Complexity: $(BIGOH log(n)) 732 */ 733 Range opSlice(size_t a, size_t b) 734 { 735 assert(0, "Not implemented"); 736 } 737 738 /** 739 Forward to `opSlice().front` and `opSlice().back`, respectively. 740 741 Complexity: $(BIGOH log(n)) 742 */ 743 @property ref T front() //ref return optional 744 { 745 assert(0, "Not implemented"); 746 } 747 /// Ditto 748 @property void front(T value) //Only when front does not return by ref 749 { 750 assert(0, "Not implemented"); 751 } 752 /// Ditto 753 T moveFront() 754 { 755 assert(0, "Not implemented"); 756 } 757 /// Ditto 758 @property ref T back() //ref return optional 759 { 760 assert(0, "Not implemented"); 761 } 762 /// Ditto 763 @property void back(T value) //Only when front does not return by ref 764 { 765 assert(0, "Not implemented"); 766 } 767 /// Ditto 768 T moveBack() 769 { 770 assert(0, "Not implemented"); 771 } 772 773 /** 774 Indexing operators yield or modify the value at a specified index. 775 */ 776 ref T opIndex(KeyType) //ref return optional 777 { 778 assert(0, "Not implemented"); 779 } 780 /// ditto 781 void opIndexAssign(KeyType i, T value) //Only when front does not return by ref 782 { 783 assert(0, "Not implemented"); 784 } 785 /// ditto 786 T opIndexUnary(string op)(KeyType i) //Only when front does not return by ref 787 { 788 assert(0, "Not implemented"); 789 } 790 /// ditto 791 void opIndexOpAssign(string op)(KeyType i, T value) //Only when front does not return by ref 792 { 793 assert(0, "Not implemented"); 794 } 795 /// ditto 796 T moveAt(KeyType i) 797 { 798 assert(0, "Not implemented"); 799 } 800 801 /** 802 $(D k in container) returns true if the given key is in the container. 803 */ 804 bool opBinaryRight(string op)(KeyType k) if (op == "in") 805 { 806 assert(0, "Not implemented"); 807 } 808 809 /** 810 Returns a range of all elements containing `k` (could be empty or a 811 singleton range). 812 */ 813 Range equalRange(KeyType k) 814 { 815 assert(0, "Not implemented"); 816 } 817 818 /** 819 Returns a range of all elements with keys less than `k` (could be 820 empty or a singleton range). Only defined by containers that store 821 data sorted at all times. 822 */ 823 Range lowerBound(KeyType k) 824 { 825 assert(0, "Not implemented"); 826 } 827 828 /** 829 Returns a range of all elements with keys larger than `k` (could be 830 empty or a singleton range). Only defined by containers that store 831 data sorted at all times. 832 */ 833 Range upperBound(KeyType k) 834 { 835 assert(0, "Not implemented"); 836 } 837 838 /** 839 Returns a new container that's the concatenation of `this` and its 840 argument. `opBinaryRight` is only defined if `Stuff` does not 841 define `opBinary`. 842 843 Complexity: $(BIGOH n + m), where m is the number of elements in $(D 844 stuff) 845 */ 846 TotalContainer opBinary(string op)(Stuff rhs) if (op == "~") 847 { 848 assert(0, "Not implemented"); 849 } 850 851 /// ditto 852 TotalContainer opBinaryRight(string op)(Stuff lhs) if (op == "~") 853 { 854 assert(0, "Not implemented"); 855 } 856 857 /** 858 Forwards to $(D insertAfter(this[], stuff)). 859 */ 860 void opOpAssign(string op)(Stuff stuff) if (op == "~") 861 { 862 assert(0, "Not implemented"); 863 } 864 865 /** 866 Removes all contents from the container. The container decides how $(D 867 capacity) is affected. 868 869 Postcondition: `empty` 870 871 Complexity: $(BIGOH n) 872 */ 873 void clear() 874 { 875 assert(0, "Not implemented"); 876 } 877 878 /** 879 Sets the number of elements in the container to `newSize`. If $(D 880 newSize) is greater than `length`, the added elements are added to 881 unspecified positions in the container and initialized with $(D 882 .init). 883 884 Complexity: $(BIGOH abs(n - newLength)) 885 886 Postcondition: $(D _length == newLength) 887 */ 888 @property void length(size_t newLength) 889 { 890 assert(0, "Not implemented"); 891 } 892 893 /** 894 Inserts `stuff` in an unspecified position in the 895 container. Implementations should choose whichever insertion means is 896 the most advantageous for the container, but document the exact 897 behavior. `stuff` can be a value convertible to the element type of 898 the container, or a range of values convertible to it. 899 900 The `stable` version guarantees that ranges iterating over the 901 container are never invalidated. Client code that counts on 902 non-invalidating insertion should use `stableInsert`. Such code would 903 not compile against containers that don't support it. 904 905 Returns: The number of elements added. 906 907 Complexity: $(BIGOH m * log(n)), where `m` is the number of 908 elements in `stuff` 909 */ 910 size_t insert(Stuff)(Stuff stuff) 911 { 912 assert(0, "Not implemented"); 913 } 914 ///ditto 915 size_t stableInsert(Stuff)(Stuff stuff) 916 { 917 assert(0, "Not implemented"); 918 } 919 920 /** 921 Same as `insert(stuff)` and `stableInsert(stuff)` respectively, 922 but relax the complexity constraint to linear. 923 */ 924 size_t linearInsert(Stuff)(Stuff stuff) 925 { 926 assert(0, "Not implemented"); 927 } 928 ///ditto 929 size_t stableLinearInsert(Stuff)(Stuff stuff) 930 { 931 assert(0, "Not implemented"); 932 } 933 934 /** 935 Picks one value in an unspecified position in the container, removes 936 it from the container, and returns it. Implementations should pick the 937 value that's the most advantageous for the container. The stable version 938 behaves the same, but guarantees that ranges iterating over the container 939 are never invalidated. 940 941 Precondition: `!empty` 942 943 Returns: The element removed. 944 945 Complexity: $(BIGOH log(n)). 946 */ 947 T removeAny() 948 { 949 assert(0, "Not implemented"); 950 } 951 /// ditto 952 T stableRemoveAny() 953 { 954 assert(0, "Not implemented"); 955 } 956 957 /** 958 Inserts `value` to the front or back of the container. `stuff` 959 can be a value convertible to the container's element type or a range 960 of values convertible to it. The stable version behaves the same, but 961 guarantees that ranges iterating over the container are never 962 invalidated. 963 964 Returns: The number of elements inserted 965 966 Complexity: $(BIGOH log(n)). 967 */ 968 size_t insertFront(Stuff)(Stuff stuff) 969 { 970 assert(0, "Not implemented"); 971 } 972 /// ditto 973 size_t stableInsertFront(Stuff)(Stuff stuff) 974 { 975 assert(0, "Not implemented"); 976 } 977 /// ditto 978 size_t insertBack(Stuff)(Stuff stuff) 979 { 980 assert(0, "Not implemented"); 981 } 982 /// ditto 983 size_t stableInsertBack(T value) 984 { 985 assert(0, "Not implemented"); 986 } 987 988 /** 989 Removes the value at the front or back of the container. The stable 990 version behaves the same, but guarantees that ranges iterating over 991 the container are never invalidated. The optional parameter $(D 992 howMany) instructs removal of that many elements. If $(D howMany > n), 993 all elements are removed and no exception is thrown. 994 995 Precondition: `!empty` 996 997 Complexity: $(BIGOH log(n)). 998 */ 999 void removeFront() 1000 { 1001 assert(0, "Not implemented"); 1002 } 1003 /// ditto 1004 void stableRemoveFront() 1005 { 1006 assert(0, "Not implemented"); 1007 } 1008 /// ditto 1009 void removeBack() 1010 { 1011 assert(0, "Not implemented"); 1012 } 1013 /// ditto 1014 void stableRemoveBack() 1015 { 1016 assert(0, "Not implemented"); 1017 } 1018 1019 /** 1020 Removes `howMany` values at the front or back of the 1021 container. Unlike the unparameterized versions above, these functions 1022 do not throw if they could not remove `howMany` elements. Instead, 1023 if $(D howMany > n), all elements are removed. The returned value is 1024 the effective number of elements removed. The stable version behaves 1025 the same, but guarantees that ranges iterating over the container are 1026 never invalidated. 1027 1028 Returns: The number of elements removed 1029 1030 Complexity: $(BIGOH howMany * log(n)). 1031 */ 1032 size_t removeFront(size_t howMany) 1033 { 1034 assert(0, "Not implemented"); 1035 } 1036 /// ditto 1037 size_t stableRemoveFront(size_t howMany) 1038 { 1039 assert(0, "Not implemented"); 1040 } 1041 /// ditto 1042 size_t removeBack(size_t howMany) 1043 { 1044 assert(0, "Not implemented"); 1045 } 1046 /// ditto 1047 size_t stableRemoveBack(size_t howMany) 1048 { 1049 assert(0, "Not implemented"); 1050 } 1051 1052 /** 1053 Removes all values corresponding to key `k`. 1054 1055 Complexity: $(BIGOH m * log(n)), where `m` is the number of 1056 elements with the same key. 1057 1058 Returns: The number of elements removed. 1059 */ 1060 size_t removeKey(KeyType k) 1061 { 1062 assert(0, "Not implemented"); 1063 } 1064 1065 /** 1066 Inserts `stuff` before, after, or instead range `r`, which must 1067 be a valid range previously extracted from this container. `stuff` 1068 can be a value convertible to the container's element type or a range 1069 of objects convertible to it. The stable version behaves the same, but 1070 guarantees that ranges iterating over the container are never 1071 invalidated. 1072 1073 Returns: The number of values inserted. 1074 1075 Complexity: $(BIGOH n + m), where `m` is the length of `stuff` 1076 */ 1077 size_t insertBefore(Stuff)(Range r, Stuff stuff) 1078 { 1079 assert(0, "Not implemented"); 1080 } 1081 /// ditto 1082 size_t stableInsertBefore(Stuff)(Range r, Stuff stuff) 1083 { 1084 assert(0, "Not implemented"); 1085 } 1086 /// ditto 1087 size_t insertAfter(Stuff)(Range r, Stuff stuff) 1088 { 1089 assert(0, "Not implemented"); 1090 } 1091 /// ditto 1092 size_t stableInsertAfter(Stuff)(Range r, Stuff stuff) 1093 { 1094 assert(0, "Not implemented"); 1095 } 1096 /// ditto 1097 size_t replace(Stuff)(Range r, Stuff stuff) 1098 { 1099 assert(0, "Not implemented"); 1100 } 1101 /// ditto 1102 size_t stableReplace(Stuff)(Range r, Stuff stuff) 1103 { 1104 assert(0, "Not implemented"); 1105 } 1106 1107 /** 1108 Removes all elements belonging to `r`, which must be a range 1109 obtained originally from this container. The stable version behaves the 1110 same, but guarantees that ranges iterating over the container are 1111 never invalidated. 1112 1113 Returns: A range spanning the remaining elements in the container that 1114 initially were right after `r`. 1115 1116 Complexity: $(BIGOH m * log(n)), where `m` is the number of 1117 elements in `r` 1118 */ 1119 Range remove(Range r) 1120 { 1121 assert(0, "Not implemented"); 1122 } 1123 /// ditto 1124 Range stableRemove(Range r) 1125 { 1126 assert(0, "Not implemented"); 1127 } 1128 1129 /** 1130 Same as `remove` above, but has complexity relaxed to linear. 1131 1132 Returns: A range spanning the remaining elements in the container that 1133 initially were right after `r`. 1134 1135 Complexity: $(BIGOH n) 1136 */ 1137 Range linearRemove(Range r) 1138 { 1139 assert(0, "Not implemented"); 1140 } 1141 /// ditto 1142 Range stableLinearRemove(Range r) 1143 { 1144 assert(0, "Not implemented"); 1145 } 1146 } 1147 1148 @safe unittest 1149 { 1150 TotalContainer!int test; 1151 }