The OpenD Programming Language

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 }