root/trunk/phobos/std/container.d

Revision 2364, 121.8 kB (checked in by andrei, 4 years ago)

Fix for issue 4942

  • Property svn:eol-style set to native
  • Property svn:executable set to *
Line 
1 // Written in the D programming language.
2
3 /**
4 Defines generic _containers.
5
6 Macros:
7 WIKI = Phobos/StdContainer
8 TEXTWITHCOMMAS = $0
9 LEADINGROW = <tr style=leadingrow bgcolor=#E4E9EF><td colspan=3><b><em>$0</em></b></td></tr>
10
11 Copyright: Red-black tree code copyright (C) 2008- by Steven Schveighoffer. Other code
12 copyright 2010- Andrei Alexandrescu. All rights reserved by the respective holders.
13
14 License: Distributed under the Boost Software License, Version 1.0.
15 (See accompanying file LICENSE_1_0.txt or copy at $(WEB
16 boost.org/LICENSE_1_0.txt)).
17
18 Authors: Steven Schveighoffer, $(WEB erdani.com, Andrei Alexandrescu)
19
20 $(BOOKTABLE $(TEXTWITHCOMMAS Container primitives. Below, $(D C) means
21 a _container type, $(D c) is a value of _container type, $(D n$(SUB
22 x)) represents the effective length of value $(D x), which could be a
23 single element (in which case $(D n$(SUB x)) is $(D 1)), a _container,
24 or a range.),
25
26 $(TR $(TH Syntax) $(TH $(BIGOH &middot;)) $(TH Description))
27
28 $(TR $(TDNW $(D C(x))) $(TDNW $(D n$(SUB x))) $(TD Creates a
29 _container of type $(D C) from either another _container or a range.))
30
31 $(TR $(TDNW $(D c.dup)) $(TDNW $(D n$(SUB c))) $(TD Returns a
32 duplicate of the _container.))
33
34 $(TR $(TDNW $(D c ~ x)) $(TDNW $(D n$(SUB c) + n$(SUB x))) $(TD
35 Returns the concatenation of $(D c) and $(D r). $(D x) may be a single
36 element or an input range.))
37
38 $(TR $(TDNW $(D x ~ c)) $(TDNW $(D n$(SUB c) + n$(SUB x))) $(TD
39 Returns the concatenation of $(D x) and $(D c).  $(D x) may be a
40 single element or an input range type.))
41
42 $(LEADINGROW Iteration)
43
44 $(TR  $(TD $(D c.Range)) $(TD) $(TD The primary range
45 type associated with the _container.))
46
47 $(TR $(TD $(D c[])) $(TDNW $(D log n$(SUB c))) $(TD Returns a range
48 iterating over the entire _container, in a _container-defined order.))
49
50 $(TR $(TDNW $(D c[a, b])) $(TDNW $(D log n$(SUB c))) $(TD Fetches a
51 portion of the _container from key $(D a) to key $(D b).))
52
53 $(LEADINGROW Capacity)
54
55 $(TR $(TD $(D c.empty)) $(TD $(D 1)) $(TD Returns $(D true) if the
56 _container has no elements, $(D false) otherwise.))
57
58 $(TR  $(TD $(D c.length)) $(TDNW $(D log n$(SUB c))) $(TD Returns the
59 number of elements in the _container.))
60
61 $(TR $(TDNW $(D c.length = n)) $(TDNW $(D n$(SUB c) + n)) $(TD Forces
62 the number of elements in the _container to $(D n). If the _container
63 ends up growing, the added elements are initialized in a
64 _container-dependent manner (usually with $(D T.init)).))
65
66 $(TR $(TD $(D c.capacity)) $(TDNW $(D log n$(SUB c))) $(TD Returns the
67 maximum number of elements that can be stored in the _container
68 without triggering a reallocation.))
69
70 $(TR $(TD $(D c.reserve(x))) $(TD $(D n$(SUB c))) $(TD Forces $(D
71 capacity) to at least $(D x) without reducing it.))
72
73 $(LEADINGROW Access)
74
75 $(TR $(TDNW $(D c.front)) $(TDNW $(D log n$(SUB c))) $(TD Returns the
76 first element of the _container, in a _container-defined order.))
77
78 $(TR $(TDNW $(D c.moveFront)) $(TDNW $(D log n$(SUB c))) $(TD
79 Destructively reads and returns the first element of the
80 _container. The slot is not removed from the _container; it is left
81 initalized with $(D T.init). This routine need not be defined if $(D
82 front) returns a $(D ref).))
83
84 $(TR $(TDNW $(D c.front = v)) $(TDNW $(D log n$(SUB c))) $(TD Assigns
85 $(D v) to the first element of the _container.))
86
87 $(TR $(TDNW $(D c.back)) $(TDNW $(D log n$(SUB c))) $(TD Returns the
88 last element of the _container, in a _container-defined order.))
89
90 $(TR $(TDNW $(D c.moveBack)) $(TDNW $(D log n$(SUB c))) $(TD
91 Destructively reads and returns the first element of the
92 container. The slot is not removed from the _container; it is left
93 initalized with $(D T.init). This routine need not be defined if $(D
94 front) returns a $(D ref).))
95
96 $(TR $(TDNW $(D c.back = v)) $(TDNW $(D log n$(SUB c))) $(TD Assigns
97 $(D v) to the last element of the _container.))
98
99 $(TR $(TDNW $(D c[x])) $(TDNW $(D log n$(SUB c))) $(TD Provides
100 indexed access into the _container. The index type is
101 _container-defined. A container may define several index types (and
102 consequently overloaded indexing).))
103
104 $(TR  $(TDNW $(D c.moveAt(x))) $(TDNW $(D log n$(SUB c))) $(TD
105 Destructively reads and returns the value at position $(D x). The slot
106 is not removed from the _container; it is left initialized with $(D
107 T.init).))
108
109 $(TR  $(TDNW $(D c[x] = v)) $(TDNW $(D log n$(SUB c))) $(TD Sets
110 element at specified index into the _container.))
111
112 $(TR  $(TDNW $(D c[x] $(I op)= v)) $(TDNW $(D log n$(SUB c)))
113 $(TD Performs read-modify-write operation at specified index into the
114 _container.))
115
116 $(LEADINGROW Operations)
117
118 $(TR $(TDNW $(D e in c)) $(TDNW $(D log n$(SUB c))) $(TD
119 Returns nonzero if e is found in $(D c).))
120
121 $(TR  $(TDNW $(D c.lowerBound(v))) $(TDNW $(D log n$(SUB c))) $(TD
122 Returns a range of all elements strictly less than $(D v).))
123
124 $(TR  $(TDNW $(D c.upperBound(v))) $(TDNW $(D log n$(SUB c))) $(TD
125 Returns a range of all elements strictly greater than $(D v).))
126
127 $(TR  $(TDNW $(D c.equalRange(v))) $(TDNW $(D log n$(SUB c))) $(TD
128 Returns a range of all elements in $(D c) that are equal to $(D v).))
129
130 $(LEADINGROW Modifiers)
131
132 $(TR $(TDNW $(D c ~= x)) $(TDNW $(D n$(SUB c) + n$(SUB x)))
133 $(TD Appends $(D x) to $(D c). $(D x) may be a single element or an
134 input range type.))
135
136 $(TR  $(TDNW $(D c.clear())) $(TDNW $(D n$(SUB c))) $(TD Removes all
137 elements in $(D c).))
138
139 $(TR  $(TDNW $(D c.insert(x))) $(TDNW $(D n$(SUB x) * log n$(SUB c)))
140 $(TD Inserts $(D x) in $(D c) at a position (or positions) chosen by $(D c).))
141
142 $(TR  $(TDNW $(D c.stableInsert(x)))
143 $(TDNW $(D n$(SUB x) * log n$(SUB c))) $(TD Same as $(D c.insert(x)),
144 but is guaranteed to not invalidate any ranges.))
145
146 $(TR  $(TDNW $(D c.linearInsert(v))) $(TDNW $(D n$(SUB c))) $(TD Same
147 as $(D c.insert(v)) but relaxes complexity to linear.))
148
149 $(TR  $(TDNW $(D c.stableLinearInsert(v))) $(TDNW $(D n$(SUB c)))
150 $(TD Same as $(D c.stableInsert(v)) but relaxes complexity to linear.))
151
152 $(TR  $(TDNW $(D c.removeAny())) $(TDNW $(D log n$(SUB c)))
153 $(TD Removes some element from $(D c) and returns it.))
154
155 $(TR  $(TDNW $(D c.stableRemoveAny(v))) $(TDNW $(D log n$(SUB c)))
156 $(TD Same as $(D c.removeAny(v)), but is guaranteed to not invalidate any
157 iterators.))
158
159 $(TR  $(TDNW $(D c.insertFront(v))) $(TDNW $(D log n$(SUB c)))
160 $(TD Inserts $(D v) at the front of $(D c).))
161
162 $(TR  $(TDNW $(D c.stableInsertFront(v))) $(TDNW $(D log n$(SUB c)))
163 $(TD Same as $(D c.insertFront(v)), but guarantees no ranges will be
164 invalidated.))
165
166 $(TR  $(TDNW $(D c.insertBack(v))) $(TDNW $(D log n$(SUB c)))
167 $(TD Inserts $(D v) at the back of $(D c).))
168
169 $(TR  $(TDNW $(D c.stableInsertBack(v))) $(TDNW $(D log n$(SUB c)))
170 $(TD Same as $(D c.insertBack(v)), but guarantees no ranges will be
171 invalidated.))
172
173 $(TR  $(TDNW $(D c.removeFront())) $(TDNW $(D log n$(SUB c)))
174 $(TD Removes the element at the front of $(D c).))
175
176 $(TR  $(TDNW $(D c.stableRemoveFront())) $(TDNW $(D log n$(SUB c)))
177 $(TD Same as $(D c.removeFront()), but guarantees no ranges will be
178 invalidated.))
179
180 $(TR  $(TDNW $(D c.removeBack())) $(TDNW $(D log n$(SUB c)))
181 $(TD Removes the value at the back of $(D c).))
182
183 $(TR  $(TDNW $(D c.stableRemoveBack())) $(TDNW $(D log n$(SUB c)))
184 $(TD Same as $(D c.removeBack()), but guarantees no ranges will be
185 invalidated.))
186
187 $(TR  $(TDNW $(D c.remove(r))) $(TDNW $(D n$(SUB r) * log n$(SUB c)))
188 $(TD Removes range $(D r) from $(D c).))
189
190 $(TR  $(TDNW $(D c.stableRemove(r)))
191 $(TDNW $(D n$(SUB r) * log n$(SUB c)))
192 $(TD Same as $(D c.remove(r)), but guarantees iterators are not
193 invalidated.))
194
195 $(TR  $(TDNW $(D c.linearRemove(r))) $(TDNW $(D n$(SUB c)))
196 $(TD Removes range $(D r) from $(D c).))
197
198 $(TR  $(TDNW $(D c.stableLinearRemove(r))) $(TDNW $(D n$(SUB c)))
199 $(TD Same as $(D c.linearRemove(r)), but guarantees iterators are not
200 invalidated.))
201
202 $(TR  $(TDNW $(D c.removeKey(k))) $(TDNW $(D log n$(SUB c)))
203 $(TD Removes an element from $(D c) by using its key $(D k).
204 The key's type is defined by the _container.))
205
206 $(TR  $(TDNW $(D )) $(TDNW $(D )) $(TD ))
207
208 )
209  */
210 module std.container;
211
212 import core.memory, core.stdc.stdlib, core.stdc.string, std.algorithm,
213     std.conv, std.exception, std.functional, std.range, std.traits,
214     std.typecons, std.typetuple;
215 version(unittest) import std.stdio;
216
217 version(unittest) version = RBDoChecks;
218
219 //version = RBDoChecks;
220
221 version(RBDoChecks)
222 {
223     import std.stdio;
224 }
225
226
227
228 /* The following documentation and type $(D TotalContainer) are
229 intended for developers only.
230
231 $(D TotalContainer) is an unimplemented container that illustrates a
232 host of primitives that a container may define. It is to some extent
233 the bottom of the conceptual container hierarchy. A given container
234 most often will choose to only implement a subset of these primitives,
235 and define its own additional ones. Adhering to the standard primitive
236 names below allows generic code to work independently of containers.
237
238 Things to remember: any container must be a reference type, whether
239 implemented as a $(D class) or $(D struct). No primitive below
240 requires the container to escape addresses of elements, which means
241 that compliant containers can be defined to use reference counting or
242 other deterministic memory management techniques.
243
244 A container may choose to define additional specific operations. The
245 only requirement is that those operations bear different names than
246 the ones below, lest user code gets confused.
247
248 Complexity of operations should be interpreted as "at least as good
249 as". If an operation is required to have $(BIGOH n) complexity, it
250 could have anything lower than that, e.g. $(BIGOH log(n)). Unless
251 specified otherwise, $(D n) inside a $(BIGOH) expression stands for
252 the number of elements in the container.
253  */
254 struct TotalContainer(T)
255 {
256 /**
257 If the container has a notion of key-value mapping, $(D KeyType)
258 defines the type of the key of the container.
259  */
260     alias T KeyType;
261
262 /**
263 If the container has a notion of multikey-value mapping, $(D
264 KeyTypes[k]), where $(D k) is a zero-based unsigned number, defines
265 the type of the $(D k)th key of the container.
266
267 A container may define both $(D KeyType) and $(D KeyTypes), e.g. in
268 the case it has the notion of primary/preferred key.
269  */
270     alias TypeTuple!(T) KeyTypes;
271
272 /**
273 If the container has a notion of key-value mapping, $(D ValueType)
274 defines the type of the value of the container. Typically, a map-style
275 container mapping values of type $(D K) to values of type $(D V)
276 defines $(D KeyType) to be $(D K) and $(D ValueType) to be $(D V).
277  */
278     alias T ValueType;
279
280 /**
281 Defines the container's primary range, which embodies one of the
282 ranges defined in $(XREFMODULE range).
283
284 Generally a container may define several types of ranges.
285  */
286     struct Range
287     {
288         /// Range primitives.
289         @property bool empty()
290         {
291             assert(0);
292         }
293         /// Ditto
294         @property T front()
295         {
296             assert(0);
297         }
298         /// Ditto
299         T moveFront()
300         {
301             assert(0);
302         }
303         /// Ditto
304         void popFront()
305         {
306             assert(0);
307         }
308         /// Ditto
309         @property T back()
310         {
311             assert(0);
312         }
313         /// Ditto
314         T moveBack()
315         {
316             assert(0);
317         }
318         /// Ditto
319         void popBack()
320         {
321             assert(0);
322         }
323         /// Ditto
324         T opIndex(size_t i)
325         {
326             assert(0);
327         }
328         /// Ditto
329         void opIndexAssign(T value, size_t i)
330         {
331             assert(0);
332         }
333         /// Ditto
334         void opIndexOpAssign(string op)(T value, uint i)
335         {
336             assert(0);
337         }
338         /// Ditto
339         T moveAt(size_t i)
340         {
341             assert(0);
342         }
343         /// Ditto
344         @property size_t length()
345         {
346             assert(0);
347         }
348     }
349
350 /**
351 Property returning $(D true) if and only if the container has no
352 elements.
353
354 Complexity: $(BIGOH 1)
355  */
356     @property bool empty()
357     {
358         assert(0);
359     }
360
361 /**
362 Returns a duplicate of the container. The elements themselves are not
363 transitively duplicated.
364
365 Complexity: $(BIGOH n).
366  */
367     @property TotalContainer dup()
368     {
369         assert(0);
370     }
371
372 /**
373 Returns the number of elements in the container.
374
375 Complexity: $(BIGOH log(n)).
376 */
377     @property size_t length()
378     {
379         assert(0);
380     }
381
382 /**
383 Returns the maximum number of elements the container can store without
384 (a) allocating memory, (b) invalidating iterators upon insertion.
385
386 Complexity: $(BIGOH log(n)).
387  */
388     @property size_t capacity()
389     {
390         assert(0);
391     }
392
393 /**
394 Ensures sufficient capacity to accommodate $(D n) elements.
395
396 Postcondition: $(D capacity >= n)
397
398 Complexity: $(BIGOH log(e - capacity)) if $(D e > capacity), otherwise
399 $(BIGOH 1).
400  */
401     void reserve(size_t e)
402     {
403         assert(0);
404     }
405
406 /**
407 Returns a range that iterates over all elements of the container, in a
408 container-defined order. The container should choose the most
409 convenient and fast method of iteration for $(D opSlice()).
410
411 Complexity: $(BIGOH log(n))
412  */
413     Range opSlice()
414     {
415         assert(0);
416     }
417
418     /**
419        Returns a range that iterates the container between two
420        specified positions.
421
422        Complexity: $(BIGOH log(n))
423      */
424     Range opSlice(size_t a, size_t b)
425     {
426         assert(0);
427     }
428
429 /**
430 Forward to $(D opSlice().front) and $(D opSlice().back), respectively.
431
432 Complexity: $(BIGOH log(n))
433  */
434     @property T front()
435     {
436         assert(0);
437     }
438     /// Ditto
439     T moveFront()
440     {
441         assert(0);
442     }
443     /// Ditto
444     @property T back()
445     {
446         assert(0);
447     }
448     /// Ditto
449     T moveBack()
450     {
451         assert(0);
452     }
453
454 /**
455 Indexing operators yield or modify the value at a specified index.
456  */
457     /**
458        Indexing operators yield or modify the value at a specified index.
459      */
460     ValueType opIndex(KeyType)
461     {
462         assert(0);
463     }
464     /// ditto
465     void opIndexAssign(KeyType)
466     {
467         assert(0);
468     }
469     /// ditto
470     void opIndexOpAssign(string op)(KeyType)
471     {
472         assert(0);
473     }
474     T moveAt(size_t i)
475     {
476         assert(0);
477     }
478
479 /**
480 $(D k in container) returns true if the given key is in the container.
481  */
482     bool opBinary(string op)(KeyType k) if (op == "in")
483     {
484         assert(0);
485     }
486
487 /**
488 Returns a range of all elements containing $(D k) (could be empty or a
489 singleton range).
490  */
491     Range equalRange(KeyType k)
492     {
493         assert(0);
494     }
495
496 /**
497 Returns a range of all elements with keys less than $(D k) (could be
498 empty or a singleton range). Only defined by containers that store
499 data sorted at all times.
500  */
501     Range lowerBound(KeyType k)
502     {
503         assert(0);
504     }
505
506 /**
507 Returns a range of all elements with keys larger than $(D k) (could be
508 empty or a singleton range).  Only defined by containers that store
509 data sorted at all times.
510  */
511     Range upperBound(KeyType k)
512     {
513         assert(0);
514     }
515
516 /**
517 Returns a new container that's the concatenation of $(D this) and its
518 argument. $(D opBinaryRight) is only defined if $(D Stuff) does not
519 define $(D opBinary).
520
521 Complexity: $(BIGOH n + m), where m is the number of elements in $(D
522 stuff)
523  */
524     TotalContainer opBinary(string op)(Stuff rhs) if (op == "~")
525     {
526         assert(0);
527     }
528
529     /// ditto
530     TotalContainer opBinaryRight(string op)(Stuff lhs) if (op == "~")
531     {
532         assert(0);
533     }
534
535 /**
536 Forwards to $(D insertAfter(this[], stuff)).
537  */
538     void opOpAssign(string op)(Stuff stuff) if (op == "~")
539     {
540         assert(0);
541     }
542
543 /**
544 Removes all contents from the container. The container decides how $(D
545 capacity) is affected.
546
547 Postcondition: $(D empty)
548
549 Complexity: $(BIGOH n)
550  */
551     void clear()
552     {
553         assert(0);
554     }
555
556 /**
557 Sets the number of elements in the container to $(D newSize). If $(D
558 newSize) is greater than $(D length), the added elements are added to
559 unspecified positions in the container and initialized with $(D
560 .init).
561
562 Complexity: $(BIGOH abs(n - newLength))
563
564 Postcondition: $(D _length == newLength)
565  */
566     @property void length(size_t newLength)
567     {
568         assert(0);
569     }
570
571 /**
572 Inserts $(D stuff) in an unspecified position in the
573 container. Implementations should choose whichever insertion means is
574 the most advantageous for the container, but document the exact
575 behavior. $(D stuff) can be a value convertible to the element type of
576 the container, or a range of values convertible to it.
577
578 The $(D stable) version guarantees that ranges iterating over the
579 container are never invalidated. Client code that counts on
580 non-invalidating insertion should use $(D stableInsert). Such code would
581 not compile against containers that don't support it.
582
583 Returns: The number of elements added.
584
585 Complexity: $(BIGOH m * log(n)), where $(D m) is the number of
586 elements in $(D stuff)
587  */
588     size_t insert(Stuff)(Stuff stuff)
589     {
590         assert(0);
591     }
592     ///ditto
593     size_t stableInsert(Stuff)(Stuff stuff)
594     {
595         assert(0);
596     }
597
598 /**
599 Same as $(D insert(stuff)) and $(D stableInsert(stuff)) respectively,
600 but relax the complexity constraint to linear.
601  */
602     size_t linearInsert(Stuff)(Stuff stuff)
603     {
604         assert(0);
605     }
606     ///ditto
607     size_t stableLinearInsert(Stuff)(Stuff stuff)
608     {
609         assert(0);
610     }
611
612 /**
613 Picks one value in an unspecified position in the container, removes
614 it from the container, and returns it. Implementations should pick the
615 value that's the most advantageous for the container, but document the
616 exact behavior. The stable version behaves the same, but guarantees that
617 ranges iterating over the container are never invalidated.
618
619 Precondition: $(D !empty)
620
621 Returns: The element removed.
622
623 Complexity: $(BIGOH log(n)).
624  */
625     T removeAny()
626     {
627         assert(0);
628     }
629     /// ditto
630     T stableRemoveAny()
631     {
632         assert(0);
633     }
634
635 /**
636 Inserts $(D value) to the front or back of the container. $(D stuff)
637 can be a value convertible to the container's element type or a range
638 of values convertible to it. The stable version behaves the same, but
639 guarantees that ranges iterating over the container are never
640 invalidated.
641
642 Returns: The number of elements inserted
643
644 Complexity: $(BIGOH log(n)).
645  */
646     size_t insertFront(Stuff)(Stuff stuff)
647     {
648         assert(0);
649     }
650     /// ditto
651     size_t stableInsertFront(Stuff)(Stuff stuff)
652     {
653         assert(0);
654     }
655     /// ditto
656     size_t insertBack(Stuff)(Stuff stuff)
657     {
658         assert(0);
659     }
660     /// ditto
661     size_t stableInsertBack(T value)
662     {
663         assert(0);
664     }
665
666 /**
667 Removes the value at the front or back of the container. The stable
668 version behaves the same, but guarantees that ranges iterating over
669 the container are never invalidated. The optional parameter $(D
670 howMany) instructs removal of that many elements. If $(D howMany > n),
671 all elements are removed and no exception is thrown.
672
673 Precondition: $(D !empty)
674
675 Complexity: $(BIGOH log(n)).
676  */
677     void removeFront()
678     {
679         assert(0);
680     }
681     /// ditto
682     void stableRemoveFront()
683     {
684         assert(0);
685     }
686     /// ditto
687     void removeBack()
688     {
689         assert(0);
690     }
691     /// ditto
692     void stableRemoveBack()
693     {
694         assert(0);
695     }
696
697 /**
698 Removes $(D howMany) values at the front or back of the
699 container. Unlike the unparameterized versions above, these functions
700 do not throw if they could not remove $(D howMany) elements. Instead,
701 if $(D howMany > n), all elements are removed. The returned value is
702 the effective number of elements removed. The stable version behaves
703 the same, but guarantees that ranges iterating over the container are
704 never invalidated.
705
706 Returns: The number of elements removed
707
708 Complexity: $(BIGOH howMany * log(n)).
709  */
710     size_t removeFront(size_t howMany)
711     {
712         assert(0);
713     }
714     /// ditto
715     size_t stableRemoveFront(size_t howMany)
716     {
717         assert(0);
718     }
719     /// ditto
720     size_t removeBack(size_t howMany)
721     {
722         assert(0);
723     }
724     /// ditto
725     size_t stableRemoveBack(size_t howMany)
726     {
727         assert(0);
728     }
729
730 /**
731 Removes all values corresponding to key $(D k).
732
733 Complexity: $(BIGOH m * log(n)), where $(D m) is the number of
734 elements with the same key.
735
736 Returns: The number of elements removed.
737  */
738     size_t removeKey(KeyType k)
739     {
740         assert(0);
741     }
742
743 /**
744 Inserts $(D stuff) before, after, or instead range $(D r), which must
745 be a valid range previously extracted from this container. $(D stuff)
746 can be a value convertible to the container's element type or a range
747 of objects convertible to it. The stable version behaves the same, but
748 guarantees that ranges iterating over the container are never
749 invalidated.
750
751 Returns: The number of values inserted.
752
753 Complexity: $(BIGOH n + m), where $(D m) is the length of $(D stuff)
754  */
755     size_t insertBefore(Stuff)(Range r, Stuff stuff)
756     {
757         assert(0);
758     }
759     /// ditto
760     size_t stableInsertBefore(Stuff)(Range r, Stuff stuff)
761     {
762         assert(0);
763     }
764     /// ditto
765     size_t insertAfter(Stuff)(Range r, Stuff stuff)
766     {
767         assert(0);
768     }
769     /// ditto
770     size_t stableInsertAfter(Stuff)(Range r, Stuff stuff)
771     {
772         assert(0);
773     }
774     /// ditto
775     size_t replace(Stuff)(Range r, Stuff stuff)
776     {
777         assert(0);
778     }
779     /// ditto
780     size_t stableReplace(Stuff)(Range r, Stuff stuff)
781     {
782         assert(0);
783     }
784
785 /**
786 Removes all elements belonging to $(D r), which must be a range
787 obtained originally from this container. The stable version behaves the
788 same, but guarantees that ranges iterating over the container are
789 never invalidated.
790
791 Returns: A range spanning the remaining elements in the container that
792 initially were right after $(D r).
793
794 Complexity: $(BIGOH m * log(n)), where $(D m) is the number of
795 elements in $(D r)
796  */
797     Range remove(Range r)
798     {
799         assert(0);
800     }
801     /// ditto
802     Range stableRemove(Range r)
803     {
804         assert(0);
805     }
806
807 /**
808 Same as $(D remove) above, but has complexity relaxed to linear.
809
810 Returns: A range spanning the remaining elements in the container that
811 initially were right after $(D r).
812
813 Complexity: $(BIGOH n)
814  */
815     Range linearRemove(Range r)
816     {
817         assert(0);
818     }
819     /// ditto
820     Range stableLinearRemove(Range r)
821     {
822         assert(0);
823     }
824 }
825
826 unittest {
827     TotalContainer!int test;
828 }
829
830 /**
831 Returns an initialized container. This function is mainly for
832 eliminating construction differences between $(D class) containers and
833 $(D struct) containers.
834  */
835 Container make(Container, T...)(T arguments) if (is(Container == struct))
836 {
837     static if (T.length == 0)
838         static assert(false, "You must pass at least one argument");
839     else
840         return Container(arguments);
841 }
842
843 /// ditto
844 Container make(Container, T...)(T arguments) if (is(Container == class))
845 {
846     return new Container(arguments);
847 }
848
849 /**
850    Implements a simple and fast singly-linked list.
851  */
852 struct SList(T)
853 {
854     private struct Node
855     {
856         T _payload;
857         Node * _next;
858         this(T a, Node* b) { _payload = a; _next = b; }
859     }
860     private Node * _root;
861
862     private static Node * findLastNode(Node * n)
863     {
864         assert(n);
865         auto ahead = n._next;
866         while (ahead)
867         {
868             n = ahead;
869             ahead = n._next;
870         }
871         return n;
872     }
873
874     private static Node * findLastNode(Node * n, size_t limit)
875     {
876         assert(n && limit);
877         auto ahead = n._next;
878         while (ahead)
879         {
880             if (!--limit) break;
881             n = ahead;
882             ahead = n._next;
883         }
884         return n;
885     }
886
887     private static Node * findNode(Node * n, Node * findMe)
888     {
889         assert(n);
890         auto ahead = n._next;
891         while (ahead != findMe)
892         {
893             n = ahead;
894             enforce(n);
895             ahead = n._next;
896         }
897         return n;
898     }
899
900 /**
901 Constructor taking a number of nodes
902      */
903     this(U)(U[] values...) if (isImplicitlyConvertible!(U, T))
904     {
905         insertFront(values);
906     }
907
908 /**
909 Constructor taking an input range
910      */
911     this(Stuff)(Stuff stuff)
912     if (isInputRange!Stuff
913             && isImplicitlyConvertible!(ElementType!Stuff, T)
914             && !is(Stuff == T[]))
915     {
916         insertFront(stuff);
917     }
918
919 /**
920 Comparison for equality.
921
922 Complexity: $(BIGOH min(n, n1)) where $(D n1) is the number of
923 elements in $(D rhs).
924      */
925     bool opEquals(ref const SList rhs) const
926     {
927         const(Node) * n1 = _root, n2 = rhs._root;
928
929         for (;; n1 = n1._next, n2 = n2._next)
930         {
931             if (!n1) return !n2;
932             if (!n2 || n1._payload != n2._payload) return false;
933         }
934     }
935
936 /**
937 Defines the container's primary range, which embodies a forward range.
938      */
939     struct Range
940     {
941         private Node * _head;
942         private this(Node * p) { _head = p; }
943         /// Forward range primitives.
944         bool empty() const { return !_head; }
945         /// ditto
946         @property Range save() { return this; }
947         /// ditto
948         @property T front() { return _head._payload; }
949         /// ditto
950         @property void front(T value)
951         {
952             enforce(_head);
953             _head._payload = value;
954         }
955         /// ditto
956         void popFront()
957         {
958             enforce(_head);
959             _head = _head._next;
960         }
961
962         T moveFront()
963         {
964             enforce(_head);
965             return move(_head._payload);
966         }
967
968         bool sameHead(Range rhs)
969         {
970             return _head && _head == rhs._head;
971         }
972     }
973
974     unittest
975     {
976         static assert(isForwardRange!Range);
977     }
978
979 /**
980 Property returning $(D true) if and only if the container has no
981 elements.
982
983 Complexity: $(BIGOH 1)
984      */
985     @property bool empty() const
986     {
987         return _root is null;
988     }
989
990 /**
991 Duplicates the container. The elements themselves are not transitively
992 duplicated.
993
994 Complexity: $(BIGOH n).
995      */
996     @property SList dup()
997     {
998         return SList(this[]);
999     }
1000
1001 /**
1002 Returns a range that iterates over all elements of the container, in
1003 forward order.
1004
1005 Complexity: $(BIGOH 1)
1006      */
1007     Range opSlice()
1008     {
1009         return Range(_root);
1010     }
1011
1012 /**
1013 Forward to $(D opSlice().front).
1014
1015 Complexity: $(BIGOH 1)
1016      */
1017     @property T front()
1018     {
1019         enforce(_root);
1020         return _root._payload;
1021     }
1022
1023 /**
1024 Forward to $(D opSlice().front(value)).
1025
1026 Complexity: $(BIGOH 1)
1027      */
1028     @property void front(T value)
1029     {
1030         enforce(_root);
1031         _root._payload = value;
1032     }
1033
1034     unittest
1035     {
1036         auto s = SList!int(1, 2, 3);
1037         s.front = 42;
1038         assert(s == SList!int(42, 2, 3));
1039     }
1040
1041 /**
1042 Returns a new $(D SList) that's the concatenation of $(D this) and its
1043 argument. $(D opBinaryRight) is only defined if $(D Stuff) does not
1044 define $(D opBinary).
1045      */
1046     SList opBinary(string op, Stuff)(Stuff rhs)
1047     if (op == "~" && is(typeof(SList(rhs))))
1048     {
1049         auto toAdd = SList(rhs);
1050         static if (is(Stuff == SList))
1051         {
1052             toAdd = toAdd.dup;
1053         }
1054         if (empty) return toAdd;
1055         // TODO: optimize
1056         auto result = dup;
1057         auto n = findLastNode(result._root);
1058         n._next = toAdd._root;
1059         return result;
1060     }
1061
1062 /**
1063 Removes all contents from the $(D SList).
1064
1065 Postcondition: $(D empty)
1066
1067 Complexity: $(BIGOH 1)
1068      */
1069     void clear()
1070     {
1071         _root = null;
1072     }
1073
1074 /**
1075 Inserts $(D stuff) to the front of the container. $(D stuff) can be a
1076 value convertible to $(D T) or a range of objects convertible to $(D
1077 T). The stable version behaves the same, but guarantees that ranges
1078 iterating over the container are never invalidated.
1079
1080 Returns: The number of elements inserted
1081
1082 Complexity: $(BIGOH log(n))
1083      */
1084     size_t insertFront(Stuff)(Stuff stuff)
1085     if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T))
1086     {
1087         size_t result;
1088         Node * n, newRoot;
1089         foreach (item; stuff)
1090         {
1091             auto newNode = new Node(item, null);
1092             (newRoot ? n._next : newRoot) = newNode;
1093             n = newNode;
1094             ++result;
1095         }
1096         if (!n) return 0;
1097         // Last node points to the old root
1098         n._next = _root;
1099         _root = newRoot;
1100         return result;
1101     }
1102
1103     /// ditto
1104     size_t insertFront(Stuff)(Stuff stuff)
1105     if (isImplicitlyConvertible!(Stuff, T))
1106     {
1107         auto newRoot = new Node(stuff, _root);
1108         _root = newRoot;
1109         return 1;
1110     }
1111
1112 /// ditto
1113     alias insertFront insert;
1114
1115 /// ditto
1116     alias insert stableInsert;
1117
1118     /// ditto
1119     alias insertFront stableInsertFront;
1120
1121 /**
1122 Picks one value from the front of the container, removes it from the
1123 container, and returns it.
1124
1125 Precondition: $(D !empty)
1126
1127 Returns: The element removed.
1128
1129 Complexity: $(BIGOH 1).
1130      */
1131     T removeAny()
1132     {
1133         enforce(!empty);
1134         auto result = move(_root._payload);
1135         _root = _root._next;
1136         return result;
1137     }
1138     /// ditto
1139     alias removeAny stableRemoveAny;
1140
1141 /**
1142 Removes the value at the front of the container. The stable version
1143 behaves the same, but guarantees that ranges iterating over the
1144 container are never invalidated.
1145
1146 Precondition: $(D !empty)
1147
1148 Complexity: $(BIGOH 1).
1149      */
1150     void removeFront()
1151     {
1152         enforce(_root);
1153         _root = _root._next;
1154     }
1155
1156     /// ditto
1157     alias removeFront stableRemoveFront;
1158
1159 /**
1160 Removes $(D howMany) values at the front or back of the
1161 container. Unlike the unparameterized versions above, these functions
1162 do not throw if they could not remove $(D howMany) elements. Instead,
1163 if $(D howMany > n), all elements are removed. The returned value is
1164 the effective number of elements removed. The stable version behaves
1165 the same, but guarantees that ranges iterating over the container are
1166 never invalidated.
1167
1168 Returns: The number of elements removed
1169
1170 Complexity: $(BIGOH howMany * log(n)).
1171      */
1172     size_t removeFront(size_t howMany)
1173     {
1174         size_t result;
1175         while (_root && result < howMany)
1176         {
1177             _root = _root._next;
1178             ++result;
1179         }
1180         return result;
1181     }
1182
1183     /// ditto
1184     alias removeFront stableRemoveFront;
1185
1186 /**
1187 Inserts $(D stuff) after range $(D r), which must be a range
1188 previously extracted from this container. Given that all ranges for a
1189 list end at the end of the list, this function essentially appends to
1190 the list and uses $(D r) as a potentially fast way to reach the last
1191 node in the list. (Ideally $(D r) is positioned near or at the last
1192 element of the list.)
1193
1194 $(D stuff) can be a value convertible to $(D T) or a range of objects
1195 convertible to $(D T). The stable version behaves the same, but
1196 guarantees that ranges iterating over the container are never
1197 invalidated.
1198
1199 Returns: The number of values inserted.
1200
1201 Complexity: $(BIGOH k + m), where $(D k) is the number of elements in
1202 $(D r) and $(D m) is the length of $(D stuff).
1203      */
1204
1205     size_t insertAfter(Stuff)(Range r, Stuff stuff)
1206     {
1207         if (!_root)
1208         {
1209             enforce(!r._head);
1210             return insertFront(stuff);
1211         }
1212         enforce(r._head);
1213         auto n = findLastNode(r._head);
1214         SList tmp;
1215         auto result = tmp.insertFront(stuff);
1216         n._next = tmp._root;
1217         return result;
1218     }
1219
1220 /**
1221 Similar to $(D insertAfter) above, but accepts a range bounded in
1222 count. This is important for ensuring fast insertions in the middle of
1223 the list.  For fast insertions after a specified position $(D r), use
1224 $(D insertAfter(take(r, 1), stuff)). The complexity of that operation
1225 only depends on the number of elements in $(D stuff).
1226
1227 Precondition: $(D r.original.empty || r.maxLength > 0)
1228
1229 Returns: The number of values inserted.
1230
1231 Complexity: $(BIGOH k + m), where $(D k) is the number of elements in
1232 $(D r) and $(D m) is the length of $(D stuff).
1233      */
1234     size_t insertAfter(Stuff)(Take!Range r, Stuff stuff)
1235     {
1236         auto orig = r.original;
1237         if (!orig._head)
1238         {
1239             // Inserting after a null range counts as insertion to the
1240             // front
1241             return insertFront(stuff);
1242         }
1243         enforce(!r.empty);
1244         // Find the last valid element in the range
1245         foreach (i; 1 .. r.maxLength)
1246         {
1247             if (!orig._head._next) break;
1248             orig.popFront();
1249         }
1250         // insert here
1251         SList tmp;
1252         tmp._root = orig._head._next;
1253         auto result = tmp.insertFront(stuff);
1254         orig._head._next = tmp._root;
1255         return result;
1256     }
1257
1258 /// ditto
1259     alias insertAfter stableInsertAfter;
1260
1261 /**
1262 Removes a range from the list in linear time.
1263
1264 Returns: An empty range.
1265
1266 Complexity: $(BIGOH n)
1267      */
1268     Range linearRemove(Range r)
1269     {
1270         if (!_root)
1271         {
1272             enforce(!r._head);
1273             return this[];
1274         }
1275         auto n = findNode(_root, r._head);
1276         n._next = null;
1277         return Range(null);
1278     }
1279
1280 /**
1281 Removes a $(D Take!Range) from the list in linear time.
1282
1283 Returns: A range comprehending the elements after the removed range.
1284
1285 Complexity: $(BIGOH n)
1286      */
1287     Range linearRemove(Take!Range r)
1288     {
1289         auto orig = r.original;
1290         // We have something to remove here
1291         if (orig._head == _root)
1292         {
1293             // remove straight from the head of the list
1294             for (; !orig.empty; orig.popFront())
1295             {
1296                 removeFront();
1297             }
1298             return this[];
1299         }
1300         if (!r.maxLength)
1301         {
1302             // Nothing to remove, return the range itself
1303             return orig;
1304         }
1305         // Remove from somewhere in the middle of the list
1306         enforce(_root);
1307         auto n1 = findNode(_root, orig._head);
1308         auto n2 = findLastNode(orig._head, r.maxLength);
1309         n1._next = n2._next;
1310         return Range(n1._next);
1311     }
1312
1313 /// ditto
1314     alias linearRemove stableLinearRemove;
1315 }
1316
1317 unittest
1318 {
1319     auto s = make!(SList!int)(1, 2, 3);
1320     auto n = s.findLastNode(s._root);
1321     assert(n && n._payload == 3);
1322 }
1323
1324 unittest
1325 {
1326     auto s = SList!int(1, 2, 5, 10);
1327     assert(walkLength(s[]) == 4);
1328 }
1329
1330 unittest
1331 {
1332     auto src = take([0, 1, 2, 3], 3);
1333     auto s = SList!int(src);
1334     assert(s == SList!int(0, 1, 2));
1335 }
1336
1337 unittest
1338 {
1339     auto a = SList!int(1, 2, 3);
1340     auto b = SList!int(4, 5, 6);
1341     // @@@BUG@@@ in compiler
1342     //auto c = a ~ b;
1343     auto d = [ 4, 5, 6 ];
1344     auto e = a ~ d;
1345     assert(e == SList!int(1, 2, 3, 4, 5, 6));
1346 }
1347
1348 unittest
1349 {
1350     auto a = SList!int(1, 2, 3);
1351     auto c = a ~ 4;
1352     assert(c == SList!int(1, 2, 3, 4));
1353 }
1354
1355 unittest
1356 {
1357     auto s = SList!int(1, 2, 3, 4);
1358     s.insertFront([ 42, 43 ]);
1359     assert(s == SList!int(42, 43, 1, 2, 3, 4));
1360 }
1361
1362 unittest
1363 {
1364     auto s = SList!int(1, 2, 3);
1365     assert(s.removeAny() == 1);
1366     assert(s == SList!int(2, 3));
1367     assert(s.stableRemoveAny() == 2);
1368     assert(s == SList!int(3));
1369 }
1370
1371 unittest
1372 {
1373     auto s = SList!int(1, 2, 3);
1374     s.removeFront();
1375     assert(equal(s[], [2, 3]));
1376     s.stableRemoveFront();
1377     assert(equal(s[], [3]));
1378 }
1379
1380 unittest
1381 {
1382     auto s = SList!int(1, 2, 3, 4, 5, 6, 7);
1383     assert(s.removeFront(3) == 3);
1384     assert(s == SList!int(4, 5, 6, 7));
1385 }
1386
1387 unittest
1388 {
1389     auto a = SList!int(1, 2, 3);
1390     auto b = SList!int(1, 2, 3);
1391     assert(a.insertAfter(a[], b[]) == 3);
1392 }
1393
1394 unittest
1395 {
1396     auto s = SList!int(1, 2, 3, 4);
1397     auto r = take(s[], 2);
1398     assert(s.insertAfter(r, 5) == 1);
1399     assert(s == SList!int(1, 2, 5, 3, 4));
1400 }
1401
1402 unittest
1403 {
1404     auto s = SList!int(1, 2, 3, 4, 5);
1405     auto r = s[];
1406     popFrontN(r, 3);
1407     auto r1 = s.linearRemove(r);
1408     assert(s == SList!int(1, 2, 3));
1409     assert(r1.empty);
1410 }
1411
1412 unittest
1413 {
1414     auto s = SList!int(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);
1415     auto r = s[];
1416     popFrontN(r, 3);
1417     auto r1 = take(r, 4);
1418     assert(equal(r1, [4, 5, 6, 7]));
1419     auto r2 = s.linearRemove(r1);
1420     assert(s == SList!int(1, 2, 3, 8, 9, 10));
1421     assert(equal(r2, [8, 9, 10]));
1422 }
1423
1424
1425 unittest
1426 {
1427     auto lst = SList!int(1, 5, 42, 9);
1428     assert(!lst.empty);
1429     assert(lst.front == 1);
1430     assert(walkLength(lst[]) == 4);
1431
1432     auto lst2 = lst ~ [ 1, 2, 3 ];
1433     assert(walkLength(lst2[]) == 7);
1434
1435     auto lst3 = lst ~ [ 7 ];
1436     assert(walkLength(lst3[]) == 5);
1437 }
1438
1439 unittest
1440 {
1441     auto s = make!(SList!int)(1, 2, 3);
1442 }
1443
1444 /**
1445 Array type with deterministic control of memory. The memory allocated
1446 for the array is reclaimed as soon as possible; there is no reliance
1447 on the garbage collector. $(D Array) uses $(D malloc) and $(D free)
1448 for managing its own memory.
1449  */
1450 struct Array(T) if (!is(T : const(bool)))
1451 {
1452     // This structure is not copyable.
1453     private struct Payload
1454     {
1455         size_t _capacity;
1456         T[] _payload;
1457
1458         // Convenience constructor
1459         this(T[] p) { _capacity = p.length; _payload = p; }
1460
1461         // Destructor releases array memory
1462         ~this()
1463         {
1464             foreach (ref e; _payload) .clear(e);
1465             static if (hasIndirections!T)
1466                 GC.removeRange(_payload.ptr);
1467             free(_payload.ptr);
1468         }
1469
1470         this(this)
1471         {
1472             assert(0);
1473         }
1474
1475         void opAssign(Array!(T).Payload rhs)
1476         {
1477             assert(false);
1478         }
1479
1480         // Duplicate data
1481         // @property Payload dup()
1482         // {
1483         //     Payload result;
1484         //     result._payload = _payload.dup;
1485         //     // Conservatively assume initial capacity == length
1486         //     result._capacity = result._payload.length;
1487         //     return result;
1488         // }
1489
1490         // length
1491         @property size_t length() const
1492         {
1493             return _payload.length;
1494         }
1495
1496         // length
1497         @property void length(size_t newLength)
1498         {
1499             if (length >= newLength)
1500             {
1501                 // shorten
1502                 static if (is(T == struct) && hasElaborateDestructor!T)
1503                 {
1504                     foreach (ref e; _payload.ptr[newLength .. _payload.length])
1505                     {
1506                         clear(e);
1507                     }
1508                 }
1509                 _payload = _payload.ptr[0 .. newLength];
1510                 return;
1511             }
1512             // enlarge
1513             auto startEmplace = length;
1514             _payload = (cast(T*) realloc(_payload.ptr,
1515                             T.sizeof * newLength))[0 .. newLength];
1516             initializeAll(_payload.ptr[startEmplace .. length]);
1517         }
1518
1519         // capacity
1520         @property size_t capacity() const
1521         {
1522             return _capacity;
1523         }
1524
1525         // reserve
1526         void reserve(size_t elements)
1527         {
1528             if (elements <= capacity) return;
1529             immutable sz = elements * T.sizeof;
1530             static if (hasIndirections!T)       // should use hasPointers instead
1531             {
1532                 /* Because of the transactional nature of this
1533                  * relative to the garbage collector, ensure no
1534                  * threading bugs by using malloc/copy/free rather
1535                  * than realloc.
1536                  */
1537                 immutable oldLength = length;
1538                 auto newPayload =
1539                     enforce((cast(T*) malloc(sz))[0 .. oldLength]);
1540                 // copy old data over to new array
1541                 newPayload[] = _payload[];
1542                 // Zero out unused capacity to prevent gc from seeing
1543                 // false pointers
1544                 memset(newPayload.ptr + oldLength,
1545                         0,
1546                         (elements - oldLength) * T.sizeof);
1547                 GC.addRange(newPayload.ptr, sz);
1548                 GC.removeRange(_data._payload.ptr);
1549                 free(_data._payload.ptr);
1550                 _data._payload = newPayload;
1551             }
1552             else
1553             {
1554                 /* These can't have pointers, so no need to zero
1555                  * unused region
1556                  */
1557                 auto newPayload =
1558                     enforce(cast(T*) realloc(_payload.ptr, sz))[0 .. length];
1559                 _payload = newPayload;
1560             }
1561             _capacity = elements;
1562         }
1563
1564         // Insert one item
1565         size_t insertBack(Stuff)(Stuff stuff)
1566         if (isImplicitlyConvertible!(Stuff, T))
1567         {
1568             if (_capacity == length)
1569             {
1570                 reserve(1 + capacity * 3 / 2);
1571             }
1572             assert(capacity > length && _payload.ptr);
1573             emplace!T((cast(void*) (_payload.ptr + _payload.length))
1574                     [0 .. T.sizeof],
1575                     stuff);
1576             _payload = _payload.ptr[0 .. _payload.length + 1];
1577             return 1;
1578         }
1579
1580         /// Insert a range of items
1581         size_t insertBack(Stuff)(Stuff stuff)
1582         if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T))
1583         {
1584             static if (hasLength!Stuff)
1585             {
1586                 immutable oldLength = length;
1587                 reserve(oldLength + stuff.length);
1588             }
1589             size_t result;
1590             foreach (item; stuff)
1591             {
1592                 insertBack(item);
1593                 ++result;
1594             }
1595             static if (hasLength!Stuff)
1596             {
1597                 assert(length == oldLength + stuff.length);
1598             }
1599             return result;
1600         }
1601     }
1602     private alias RefCounted!(Payload, RefCountedAutoInitialize.no) Data;
1603     private Data _data;
1604
1605     this(U)(U[] values...) if (isImplicitlyConvertible!(U, T))
1606     {
1607         auto p = malloc(T.sizeof * values.length);
1608         if (hasIndirections!T && p)
1609         {
1610             GC.addRange(p, T.sizeof * values.length);
1611         }
1612         foreach (i, e; values)
1613         {
1614             emplace!T(p[i * T.sizeof .. (i + 1) * T.sizeof], e);
1615             assert((cast(T*) p)[i] == e);
1616         }
1617         _data.RefCounted.initialize((cast(T*) p)[0 .. values.length]);
1618     }
1619
1620 /**
1621 Comparison for equality.
1622      */
1623     bool opEquals(ref const Array rhs) const
1624     {
1625         if (empty) return rhs.empty;
1626         if (rhs.empty) return false;
1627         return _data._payload == rhs._data._payload;
1628     }
1629
1630 /**
1631 Defines the container's primary range, which is a random-access range.
1632      */
1633     struct Range
1634     {
1635         private Array _outer;
1636         private size_t _a, _b;
1637
1638         this(Array data, size_t a, size_t b)
1639         {
1640             _outer = data;
1641             _a = a;
1642             _b = b;
1643         }
1644
1645         @property bool empty() const
1646         {
1647             assert(_outer.length >= _b);
1648             return _a >= _b;
1649         }
1650
1651         @property Range save()
1652         {
1653             return this;
1654         }
1655
1656         @property T front()
1657         {
1658             enforce(!empty);
1659             return _outer[_a];
1660         }
1661
1662         @property void front(T value)
1663         {
1664             enforce(!empty);
1665             _outer[_a] = move(value);
1666         }
1667
1668         void popFront()
1669         {
1670             enforce(!empty);
1671             ++_a;
1672         }
1673
1674         T moveFront()
1675         {
1676             enforce(!empty);
1677             return move(_outer._data._payload[_a]);
1678         }
1679
1680         T moveBack()
1681         {
1682             enforce(!empty);
1683             return move(_outer._data._payload[_b - 1]);
1684         }
1685
1686         T moveAt(size_t i)
1687         {
1688             i += _a;
1689             enforce(i < _b && !empty);
1690             return move(_outer._data._payload[_a + i]);
1691         }
1692
1693         T opIndex(size_t i)
1694         {
1695             i += _a;
1696             enforce(i < _b && _b <= _outer.length);
1697             return _outer[i];
1698         }
1699
1700         void opIndexAssign(T value, size_t i)
1701         {
1702             i += _a;
1703             enforce(i < _b && _b <= _outer.length);
1704             _outer[i] = value;
1705         }
1706
1707         void opIndexOpAssign(string op)(T value, size_t i)
1708         {
1709             enforce(_outer && _a + i < _b && _b <= _outer._payload.length);
1710             mixin("_outer._payload.ptr[_a + i] "~op~"= value;");
1711         }
1712     }
1713
1714 /**
1715 Property returning $(D true) if and only if the container has no
1716 elements.
1717
1718 Complexity: $(BIGOH 1)
1719      */
1720     @property bool empty() const
1721     {
1722         return !_data.RefCounted.isInitialized || _data._payload.empty;
1723     }
1724
1725 /**
1726 Duplicates the container. The elements themselves are not transitively
1727 duplicated.
1728
1729 Complexity: $(BIGOH n).
1730      */
1731     @property Array dup()
1732     {
1733         if (!_data.RefCounted.isInitialized) return this;
1734         return Array(_data._payload);
1735     }
1736
1737 /**
1738 Returns the number of elements in the container.
1739
1740 Complexity: $(BIGOH 1).
1741      */
1742     @property size_t length() const
1743     {
1744         return _data.RefCounted.isInitialized ? _data._payload.length : 0;
1745     }
1746
1747 /**
1748 Returns the maximum number of elements the container can store without
1749    (a) allocating memory, (b) invalidating iterators upon insertion.
1750
1751 Complexity: $(BIGOH 1)
1752      */
1753     @property size_t capacity()
1754     {
1755         return _data.RefCounted.isInitialized ? _data._capacity : 0;
1756     }
1757
1758 /**
1759 Ensures sufficient capacity to accommodate $(D e) elements.
1760
1761 Postcondition: $(D capacity >= e)
1762
1763 Complexity: $(BIGOH 1)
1764      */
1765     void reserve(size_t elements)
1766     {
1767         if (!_data.RefCounted.isInitialized)
1768         {
1769             if (!elements) return;
1770             immutable sz = elements * T.sizeof;
1771             auto p = enforce(malloc(sz));
1772             static if (hasIndirections!T)
1773             {
1774                 GC.addRange(p, sz);
1775             }
1776             _data.RefCounted.initialize(cast(T[]) p[0 .. 0]);
1777             _data._capacity = elements;
1778         }
1779         else
1780         {
1781             _data.reserve(elements);
1782         }
1783     }
1784
1785 /**
1786 Returns a range that iterates over elements of the container, in
1787 forward order.
1788
1789 Complexity: $(BIGOH 1)
1790      */
1791     Range opSlice()
1792     {
1793         // Workaround for bug 4356
1794         Array copy;
1795         copy._data = this._data;
1796         return Range(copy, 0, length);
1797     }
1798
1799 /**
1800 Returns a range that iterates over elements of the container from
1801 index $(D a) up to (excluding) index $(D b).
1802
1803 Precondition: $(D a <= b && b <= length)
1804
1805 Complexity: $(BIGOH 1)
1806      */
1807     Range opSlice(size_t a, size_t b)
1808     {
1809         enforce(a <= b && b <= length);
1810         // Workaround for bug 4356
1811         Array copy;
1812         copy._data = this._data;
1813         return Range(copy, a, b);
1814     }
1815
1816 /**
1817 @@@BUG@@@ This doesn't work yet
1818      */
1819     size_t opDollar() const
1820     {
1821         return length;
1822     }
1823
1824 /**
1825 Forward to $(D opSlice().front) and $(D opSlice().back), respectively.
1826
1827 Precondition: $(D !empty)
1828
1829 Complexity: $(BIGOH 1)
1830      */
1831     @property T front()
1832     {
1833         enforce(!empty);
1834         return *_data._payload.ptr;
1835     }
1836
1837 /// ditto
1838     @property void front(T value)
1839     {
1840         enforce(!empty);
1841         *_data._payload.ptr = value;
1842     }
1843
1844 /// ditto
1845     @property T back()
1846     {
1847         enforce(!empty);
1848         return _data._payload[$ - 1];
1849     }
1850
1851 /// ditto
1852     @property void back(T value)
1853     {
1854         enforce(!empty);
1855         _data._payload[$ - 1] = value;
1856     }
1857
1858 /**
1859 Indexing operators yield or modify the value at a specified index.
1860
1861 Precondition: $(D i < length)
1862
1863 Complexity: $(BIGOH 1)
1864      */
1865     T opIndex(size_t i)
1866     {
1867         enforce(_data.RefCounted.isInitialized);
1868         return _data._payload[i];
1869     }
1870
1871     /// ditto
1872     void opIndexAssign(T value, size_t i)
1873     {
1874         enforce(_data.RefCounted.isInitialized);
1875         _data._payload[i] = value;
1876     }
1877
1878 /// ditto
1879     void opIndexOpAssign(string op)(T value, size_t i)
1880     {
1881         mixin("_data._payload[i] "~op~"= value;");
1882     }
1883
1884 /**
1885 Returns a new container that's the concatenation of $(D this) and its
1886 argument. $(D opBinaryRight) is only defined if $(D Stuff) does not
1887 define $(D opBinary).
1888
1889 Complexity: $(BIGOH n + m), where m is the number of elements in $(D
1890 stuff)
1891      */
1892     Array opBinary(string op, Stuff)(Stuff stuff) if (op == "~")
1893     {
1894         // TODO: optimize
1895         Array result;
1896         // @@@BUG@@ result ~= this[] doesn't work
1897         auto r = this[];
1898         result ~= r;
1899         assert(result.length == length);
1900         result ~= stuff[];
1901         return result;
1902     }
1903
1904     /**
1905        Forwards to $(D insertBack(stuff)).
1906      */
1907     void opOpAssign(string op, Stuff)(Stuff stuff) if (op == "~")
1908     {
1909         static if (is(typeof(stuff[])))
1910         {
1911             insertBack(stuff[]);
1912         }
1913         else
1914         {
1915             insertBack(stuff);
1916         }
1917     }
1918
1919 /**
1920 Removes all contents from the container. The container decides how $(D
1921 capacity) is affected.
1922
1923 Postcondition: $(D empty)
1924
1925 Complexity: $(BIGOH n)
1926      */
1927     void clear()
1928     {
1929         .clear(_data);
1930     }
1931
1932 /**
1933 Sets the number of elements in the container to $(D newSize). If $(D
1934 newSize) is greater than $(D length), the added elements are added to
1935 unspecified positions in the container and initialized with $(D
1936 T.init).
1937
1938 Complexity: $(BIGOH abs(n - newLength))
1939
1940 Postcondition: $(D length == newLength)
1941      */
1942     @property void length(size_t newLength)
1943     {
1944         _data.RefCounted.ensureInitialized();
1945         _data.length = newLength;
1946     }
1947
1948 /**
1949 Picks one value in an unspecified position in the container, removes
1950 it from the container, and returns it. Implementations should pick the
1951 value that's the most advantageous for the container, but document the
1952 exact behavior. The stable version behaves the same, but guarantees
1953 that ranges iterating over the container are never invalidated.
1954
1955 Precondition: $(D !empty)
1956
1957 Returns: The element removed.
1958
1959 Complexity: $(BIGOH log(n)).
1960      */
1961     T removeAny()
1962     {
1963         auto result = back;
1964         removeBack();
1965         return result;
1966     }
1967     /// ditto
1968     alias removeAny stableRemoveAny;
1969
1970 /**
1971 Inserts $(D value) to the front or back of the container. $(D stuff)
1972 can be a value convertible to $(D T) or a range of objects convertible
1973 to $(D T). The stable version behaves the same, but guarantees that
1974 ranges iterating over the container are never invalidated.
1975
1976 Returns: The number of elements inserted
1977
1978 Complexity: $(BIGOH m * log(n)), where $(D m) is the number of
1979 elements in $(D stuff)
1980      */
1981     size_t insertBack(Stuff)(Stuff stuff)
1982     if (isImplicitlyConvertible!(Stuff, T) ||
1983             isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T))
1984     {
1985         _data.RefCounted.ensureInitialized();
1986         return _data.insertBack(stuff);
1987     }
1988 /// ditto
1989     alias insertBack insert;
1990
1991 /**
1992 Removes the value at the back of the container. The stable version
1993 behaves the same, but guarantees that ranges iterating over the
1994 container are never invalidated.
1995
1996 Precondition: $(D !empty)
1997
1998 Complexity: $(BIGOH log(n)).
1999      */
2000     void removeBack()
2001     {
2002         enforce(!empty);
2003         static if (is(T == struct))
2004         {
2005             // Destroy this guy
2006             .clear(_data._payload[$ - 1]);
2007         }
2008         _data._payload = _data._payload[0 .. $ - 1];
2009     }
2010 /// ditto
2011     alias removeBack stableRemoveBack;
2012
2013 /**
2014 Removes $(D howMany) values at the front or back of the
2015 container. Unlike the unparameterized versions above, these functions
2016 do not throw if they could not remove $(D howMany) elements. Instead,
2017 if $(D howMany > n), all elements are removed. The returned value is
2018 the effective number of elements removed. The stable version behaves
2019 the same, but guarantees that ranges iterating over the container are
2020 never invalidated.
2021
2022 Returns: The number of elements removed
2023
2024 Complexity: $(BIGOH howMany).
2025      */
2026     size_t removeBack(size_t howMany)
2027     {
2028         if (howMany > length) howMany = length;
2029         static if (is(T == struct))
2030         {
2031             // Destroy this guy
2032             foreach (ref e; _data._payload[$ - howMany .. $])
2033             {
2034                 .clear(e);
2035             }
2036         }
2037         _data._payload = _data._payload[0 .. $ - howMany];
2038         return howMany;
2039     }
2040     /// ditto
2041     alias removeBack stableRemoveBack;
2042
2043 /**
2044 Inserts $(D stuff) before, after, or instead range $(D r), which must
2045 be a valid range previously extracted from this container. $(D stuff)
2046 can be a value convertible to $(D T) or a range of objects convertible
2047 to $(D T). The stable version behaves the same, but guarantees that
2048 ranges iterating over the container are never invalidated.
2049
2050 Returns: The number of values inserted.
2051
2052 Complexity: $(BIGOH n + m), where $(D m) is the length of $(D stuff)
2053      */
2054     size_t insertBefore(Stuff)(Range r, Stuff stuff)
2055     if (isImplicitlyConvertible!(Stuff, T))
2056     {
2057         enforce(r._outer._data == _data && r._a < length);
2058         reserve(length + 1);
2059         assert(_data.RefCounted.isInitialized);
2060         // Move elements over by one slot
2061         memmove(_data._payload.ptr + r._a + 1,
2062                 _data._payload.ptr + r._a,
2063                 T.sizeof * (length - r._a));
2064         emplace!T((cast(void*) (_data._payload.ptr + r._a))[0 .. T.sizeof],
2065                 stuff);
2066         _data._payload = _data._payload.ptr[0 .. _data._payload.length + 1];
2067         return 1;
2068     }
2069
2070 /// ditto
2071     size_t insertBefore(Stuff)(Range r, Stuff stuff)
2072     if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T))
2073     {
2074         enforce(r._outer._data == _data && r._a <= length);
2075         static if (isForwardRange!Stuff)
2076         {
2077             // Can find the length in advance
2078             auto extra = walkLength(stuff);
2079             if (!extra) return 0;
2080             reserve(length + extra);
2081             assert(_data.RefCounted.isInitialized);
2082             // Move elements over by extra slots
2083             memmove(_data._payload.ptr + r._a + extra,
2084                     _data._payload.ptr + r._a,
2085                     T.sizeof * (length - r._a));
2086             foreach (p; _data._payload.ptr + r._a ..
2087                     _data._payload.ptr + r._a + extra)
2088             {
2089                 emplace!T((cast(void*) p)[0 .. T.sizeof], stuff.front);
2090                 stuff.popFront();
2091             }
2092             _data._payload =
2093                 _data._payload.ptr[0 .. _data._payload.length + extra];
2094             return extra;
2095         }
2096         else
2097         {
2098             enforce(_data);
2099             immutable offset = r._a;
2100             enforce(offset <= length);
2101             auto result = insertBack(stuff);
2102             bringToFront(this[offset .. length - result],
2103                     this[length - result .. length]);
2104             return result;
2105         }
2106     }
2107
2108     /// ditto
2109     size_t insertAfter(Stuff)(Range r, Stuff stuff)
2110     {
2111         // TODO: optimize
2112         enforce(_data);
2113         immutable offset = r.ptr + r.length - _data._payload.ptr;
2114         enforce(offset <= length);
2115         auto result = insertBack(stuff);
2116         bringToFront(this[offset .. length - result],
2117                 this[length - result .. length]);
2118         return result;
2119     }
2120
2121 /// ditto
2122     size_t replace(Stuff)(Range r, Stuff stuff)
2123     if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T))
2124     {
2125         enforce(_data);
2126         immutable offset = r.ptr - _data._payload.ptr;
2127         enforce(offset <= length);
2128         size_t result;
2129         for (; !stuff.empty; stuff.popFront())
2130         {
2131             if (r.empty)
2132             {
2133                 // append the rest
2134                 return result + insertBack(stuff);
2135             }
2136             r.front = stuff.front;
2137             r.popFront();
2138             ++result;
2139         }
2140         // Remove remaining stuff in r
2141         remove(r);
2142         return result;
2143     }
2144
2145 /// ditto
2146     size_t replace(Stuff)(Range r, Stuff stuff)
2147     if (isImplicitlyConvertible!(Stuff, T))
2148     {
2149         if (r.empty)
2150         {
2151             insertBefore(r, stuff);
2152         }
2153         else
2154         {
2155             r.front = stuff;
2156             r.popFront();
2157             remove(r);
2158         }
2159         return 1;
2160     }
2161
2162 /**
2163 Removes all elements belonging to $(D r), which must be a range
2164 obtained originally from this container. The stable version behaves
2165 the same, but guarantees that ranges iterating over the container are
2166 never invalidated.
2167
2168 Returns: A range spanning the remaining elements in the container that
2169 initially were right after $(D r).
2170
2171 Complexity: $(BIGOH n - m), where $(D m) is the number of elements in
2172 $(D r)
2173      */
2174     Range linearRemove(Range r)
2175     {
2176         enforce(_data.RefCounted.isInitialized);
2177         enforce(r._a <= r._b && r._b <= length);
2178         immutable offset1 = r._a;
2179         immutable offset2 = r._b;
2180         immutable tailLength = length - offset2;
2181         // Use copy here, not a[] = b[] because the ranges may overlap
2182         copy(this[offset2 .. length], this[offset1 .. offset1 + tailLength]);
2183         length = offset1 + tailLength;
2184         return this[length - tailLength .. length];
2185     }
2186
2187     /// ditto
2188     alias remove stableLinearRemove;
2189
2190 }
2191
2192 // unittest
2193 // {
2194 //     Array!int a;
2195 //     assert(a.empty);
2196 // }
2197
2198 unittest
2199 {
2200     Array!int a = Array!int(1, 2, 3);
2201     //a._data._refCountedDebug = true;
2202     auto b = a.dup;
2203     assert(b == Array!int(1, 2, 3));
2204     b.front = 42;
2205     assert(b == Array!int(42, 2, 3));
2206     assert(a == Array!int(1, 2, 3));
2207 }
2208
2209 unittest
2210 {
2211     auto a = Array!int(1, 2, 3);
2212     assert(a.length == 3);
2213 }
2214
2215 unittest
2216 {
2217     Array!int a;
2218     a.reserve(1000);
2219     assert(a.length == 0);
2220     assert(a.empty);
2221     assert(a.capacity >= 1000);
2222     auto p = a._data._payload.ptr;
2223     foreach (i; 0 .. 1000)
2224     {
2225         a.insertBack(i);
2226     }
2227     assert(p == a._data._payload.ptr);
2228 }
2229
2230 unittest
2231 {
2232     auto a = Array!int(1, 2, 3);
2233     a[1] *= 42;
2234     assert(a[1] == 84);
2235 }
2236
2237 unittest
2238 {
2239     auto a = Array!int(1, 2, 3);
2240     auto b = Array!int(11, 12, 13);
2241     auto c = a ~ b;
2242     //foreach (e; c) writeln(e);
2243     assert(c == Array!int(1, 2, 3, 11, 12, 13));
2244     //assert(a ~ b[] == Array!int(1, 2, 3, 11, 12, 13));
2245 }
2246
2247 unittest
2248 {
2249     auto a = Array!int(1, 2, 3);
2250     auto b = Array!int(11, 12, 13);
2251     a ~= b;
2252     assert(a == Array!int(1, 2, 3, 11, 12, 13));
2253 }
2254
2255 unittest
2256 {
2257     auto a = Array!int(1, 2, 3, 4);
2258     assert(a.removeAny() == 4);
2259     assert(a == Array!int(1, 2, 3));
2260 }
2261
2262 unittest
2263 {
2264     auto a = Array!int(1, 2, 3, 4, 5);
2265     auto r = a[2 .. a.length];
2266     assert(a.insertBefore(r, 42) == 1);
2267     assert(a == Array!int(1, 2, 42, 3, 4, 5));
2268     r = a[2 .. 2];
2269     assert(a.insertBefore(r, [8, 9]) == 2);
2270     assert(a == Array!int(1, 2, 8, 9, 42, 3, 4, 5));
2271 }
2272
2273 unittest
2274 {
2275     auto a = Array!int(0, 1, 2, 3, 4, 5, 6, 7, 8);
2276     a.linearRemove(a[4 .. 6]);
2277     auto b = Array!int(0, 1, 2, 3, 6, 7, 8);
2278     //writeln(a.length);
2279     //foreach (e; a) writeln(e);
2280     assert(a == Array!int(0, 1, 2, 3, 6, 7, 8));
2281 }
2282
2283 // BinaryHeap
2284 /**
2285 Implements a $(WEB en.wikipedia.org/wiki/Binary_heap, binary heap)
2286 container on top of a given random-access range type (usually $(D
2287 T[])) or a random-access container type (usually $(D Array!T)). The
2288 documentation of $(D BinaryHeap) will refer to the underlying range or
2289 container as the $(I store) of the heap.
2290
2291 The binary heap induces structure over the underlying store such that
2292 accessing the largest element (by using the $(D front) property) is a
2293 $(BIGOH 1) operation and extracting it (by using the $(D
2294 removeFront()) method) is done fast in $(BIGOH log n) time.
2295
2296 If $(D less) is the less-than operator, which is the default option,
2297 then $(D BinaryHeap) defines a so-called max-heap that optimizes
2298 extraction of the $(I largest) elements. To define a min-heap,
2299 instantiate BinaryHeap with $(D "a > b") as its predicate.
2300
2301 Simply extracting elements from a $(D BinaryHeap) container is
2302 tantamount to lazily fetching elements of $(D Store) in descending
2303 order. Extracting elements from the $(D BinaryHeap) to completion
2304 leaves the underlying store sorted in ascending order but, again,
2305 yields elements in descending order.
2306
2307 If $(D Store) is a range, the $(D BinaryHeap) cannot grow beyond the
2308 size of that range. If $(D Store) is a container that supports $(D
2309 insertBack), the $(D BinaryHeap) may grow by adding elements to the
2310 container.
2311
2312 Example:
2313 ----
2314 // Example from "Introduction to Algorithms" Cormen et al, p 146
2315 int[] a = [ 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 ];
2316 auto h = heapify(a);
2317 // largest element
2318 assert(h.front == 16);
2319 // a has the heap property
2320 assert(equal(a, [ 16, 14, 10, 9, 8, 7, 4, 3, 2, 1 ]));
2321 ----
2322      */
2323 struct BinaryHeap(Store, alias less = "a < b")
2324 if (isRandomAccessRange!(Store) || isRandomAccessRange!(typeof(Store.init[])))
2325 {
2326 // Really weird @@BUG@@: if you comment out the "private:" label below,
2327 // std.algorithm can't unittest anymore
2328 //private:
2329
2330     // The payload includes the support store and the effective length
2331     private RefCounted!(Tuple!(Store, "_store", size_t, "_length"),
2332                        RefCountedAutoInitialize.no) _payload;
2333     // Comparison predicate
2334     private alias binaryFun!(less) comp;
2335     // Convenience accessors
2336     private @property ref Store _store()
2337     {
2338         assert(_payload.RefCounted.isInitialized);
2339         return _payload._store;
2340     }
2341     private @property ref size_t _length()
2342     {
2343         assert(_payload.RefCounted.isInitialized);
2344         return _payload._length;
2345     }
2346
2347     // Asserts that the heap property is respected.
2348     private void assertValid()
2349     {
2350         debug
2351         {
2352             if (!_payload.RefCounted.isInitialized) return;
2353             if (_length < 2) return;
2354             for (size_t n = _length - 1; n >= 1; --n)
2355             {
2356                 auto parentIdx = (n - 1) / 2;
2357                 assert(!comp(_store[parentIdx], _store[n]), text(n));
2358             }
2359         }
2360     }
2361
2362     // Assuming the element at index i perturbs the heap property in
2363     // store r, percolates it down the heap such that the heap
2364     // property is restored.
2365     private void percolateDown(Store r, size_t i, size_t length)
2366     {
2367         for (;;)
2368         {
2369             auto left = i * 2 + 1, right = left + 1;
2370             if (right == length)
2371             {
2372                 if (comp(r[i], r[left])) swap(r, i, left);
2373                 return;
2374             }
2375             if (right > length) return;
2376             assert(left < length && right < length);
2377             auto largest = comp(r[i], r[left])
2378                 ? (comp(r[left], r[right]) ? right : left)
2379                 : (comp(r[i], r[right]) ? right : i);
2380             if (largest == i) return;
2381             swap(r, i, largest);
2382             i = largest;
2383         }
2384     }
2385
2386     // @@@BUG@@@: add private here, std.algorithm doesn't unittest anymore
2387     /*private*/ void pop(Store store)
2388     {
2389         assert(!store.empty);
2390         if (store.length == 1) return;
2391         auto t1 = moveFront(store[]);
2392         auto t2 = moveBack(store[]);
2393         store.front = move(t2);
2394         store.back = move(t1);
2395         percolateDown(store, 0, store.length - 1);
2396     }
2397
2398     /*private*/ static void swap(Store _store, size_t i, size_t j)
2399     {
2400         static if (is(typeof(swap(_store[i], _store[j]))))
2401         {
2402             swap(_store[i], _store[j]);
2403         }
2404         else static if (is(typeof(_store.moveAt(i))))
2405         {
2406             auto t1 = _store.moveAt(i);
2407             auto t2 = _store.moveAt(j);
2408             _store[i] = move(t2);
2409             _store[j] = move(t1);
2410         }
2411         else // assume it's a container and access its range with []
2412         {
2413             auto t1 = _store[].moveAt(i);
2414             auto t2 = _store[].moveAt(j);
2415             _store[i] = move(t2);
2416             _store[j] = move(t1);
2417         }
2418     }
2419
2420 public:
2421
2422     /**
2423        Converts the store $(D s) into a heap. If $(D initialSize) is
2424        specified, only the first $(D initialSize) elements in $(D s)
2425        are transformed into a heap, after which the heap can grow up
2426        to $(D r.length) (if $(D Store) is a range) or indefinitely (if
2427        $(D Store) is a container with $(D insertBack)). Performs
2428        $(BIGOH min(r.length, initialSize)) evaluations of $(D less).
2429      */
2430     this(Store s, size_t initialSize = size_t.max)
2431     {
2432         acquire(s, initialSize);
2433     }
2434
2435 /**
2436 Takes ownership of a store. After this, manipulating $(D s) may make
2437 the heap work incorrectly.
2438      */
2439     void acquire(Store s, size_t initialSize = size_t.max)
2440     {
2441         _payload.RefCounted.ensureInitialized();
2442         _store() = move(s);
2443         _length() = min(_store.length, initialSize);
2444         if (_length < 2) return;
2445         for (auto i = (_length - 2) / 2; ; )
2446         {
2447             this.percolateDown(_store, i, _length);
2448             if (i-- == 0) break;
2449         }
2450         assertValid;
2451     }
2452
2453 /**
2454 Takes ownership of a store assuming it already was organized as a
2455 heap.
2456      */
2457     void assume(Store s, size_t initialSize = size_t.max)
2458     {
2459         _payload.RefCounted.ensureInitialized();
2460         _store() = s;
2461         _length() = min(_store.length, initialSize);
2462         assertValid;
2463     }
2464
2465 /**
2466 Clears the heap. Returns the portion of the store from $(D 0) up to
2467 $(D length), which satisfies the $(LUCKY heap property).
2468      */
2469     auto release()
2470     {
2471         if (!_payload.RefCounted.isInitialized)
2472         {
2473             return typeof(_store[0 .. _length]).init;
2474         }
2475         assertValid();
2476         auto result = _store[0 .. _length];
2477         _payload = _payload.init;
2478         return result;
2479     }
2480
2481 /**
2482 Returns $(D true) if the heap is _empty, $(D false) otherwise.
2483      */
2484     @property bool empty()
2485     {
2486         return !length;
2487     }
2488
2489 /**
2490 Returns a duplicate of the heap. The underlying store must also
2491 support a $(D dup) method.
2492      */
2493     @property BinaryHeap dup()
2494     {
2495         BinaryHeap result;
2496         if (!_payload.RefCounted.isInitialized) return result;
2497         result.assume(_store.dup, length);
2498         return result;
2499     }
2500
2501 /**
2502 Returns the _length of the heap.
2503      */
2504     @property size_t length()
2505     {
2506         return _payload.RefCounted.isInitialized ? _length : 0;
2507     }
2508
2509 /**
2510 Returns the _capacity of the heap, which is the length of the
2511 underlying store (if the store is a range) or the _capacity of the
2512 underlying store (if the store is a container).
2513      */
2514     @property size_t capacity()
2515     {
2516         if (!_payload.RefCounted.isInitialized) return 0;
2517         static if (is(typeof(_store.capacity) : size_t))
2518         {
2519             return _store.capacity;
2520         }
2521         else
2522         {
2523             return _store.length;
2524         }
2525     }
2526
2527 /**
2528 Returns a copy of the _front of the heap, which is the largest element
2529 according to $(D less).
2530      */
2531     @property ElementType!Store front()
2532     {
2533         enforce(!empty);
2534         return _store.front;
2535     }
2536
2537 /**
2538 Clears the heap by detaching it from the underlying store.
2539      */
2540     void clear()
2541     {
2542         _payload = _payload.init;
2543     }
2544
2545 /**
2546 Inserts $(D value) into the store. If the underlying store is a range
2547 and $(D length == capacity), throws an exception.
2548      */
2549     size_t insert(ElementType!Store value)
2550     {
2551         static if (is(typeof(_store.insertBack(value))))
2552         {
2553             _payload.RefCounted.ensureInitialized();
2554             if (length == _store.length)
2555             {
2556                 // reallocate
2557                 _store.insertBack(value);
2558             }
2559             else
2560             {
2561                 // no reallocation
2562                 _store[_length] = value;
2563             }
2564         }
2565         else
2566         {
2567             // can't grow
2568             enforce(length < _store.length,
2569                     "Cannot grow a heap created over a range");
2570             _store[_length] = value;
2571         }
2572
2573         // sink down the element
2574         for (size_t n = _length; n; )
2575         {
2576             auto parentIdx = (n - 1) / 2;
2577             if (!comp(_store[parentIdx], _store[n])) break; // done!
2578             // must swap and continue
2579             swap(_store, parentIdx, n);
2580             n = parentIdx;
2581         }
2582         ++_length;
2583         assertValid();
2584         return 1;
2585     }
2586
2587 /**
2588 Removes the largest element from the heap.
2589      */
2590     void removeFront()
2591     {
2592         enforce(!empty);
2593         if (_length > 1)
2594         {
2595             auto t1 = moveFront(_store[]);
2596             auto t2 = moveAt(_store[], _length - 1);
2597             _store.front = move(t2);
2598             _store[_length - 1] = move(t1);
2599         }
2600         --_length;
2601         percolateDown(_store, 0, _length);
2602     }
2603
2604 /**
2605 Removes the largest element from the heap and returns a copy of
2606 it. The element still resides in the heap's store. For performance
2607 reasons you may want to use $(D removeFront) with heaps of objects
2608 that are expensive to copy.
2609      */
2610     ElementType!Store removeAny()
2611     {
2612         removeFront();
2613         return _store[_length];
2614     }
2615
2616 /**
2617 Replaces the largest element in the store with $(D value).
2618      */
2619     void replaceFront(ElementType!Store value)
2620     {
2621         // must replace the top
2622         assert(!empty);
2623         _store.front = value;
2624         percolateDown(_store, 0, _length);
2625         assertValid;
2626     }
2627
2628 /**
2629 If the heap has room to grow, inserts $(D value) into the store and
2630 returns $(D true). Otherwise, if $(D less(value, front)), calls $(D
2631 replaceFront(value)) and returns again $(D true). Otherwise, leaves
2632 the heap unaffected and returns $(D false). This method is useful in
2633 scenarios where the smallest $(D k) elements of a set of candidates
2634 must be collected.
2635      */
2636     bool conditionalInsert(ElementType!Store value)
2637     {
2638         _payload.RefCounted.ensureInitialized();
2639         if (_length < _store.length)
2640         {
2641             insert(value);
2642             return true;
2643         }
2644         // must replace the top
2645         assert(!_store.empty);
2646         if (!comp(value, _store.front)) return false; // value >= largest
2647         _store.front = value;
2648         percolateDown(_store, 0, _length);
2649         assertValid;
2650         return true;
2651     }
2652 }
2653
2654 /**
2655 Convenience function that returns a $(D BinaryHeap!Store) object
2656 initialized with $(D s) and $(D initialSize).
2657  */
2658 BinaryHeap!Store heapify(Store)(Store s, size_t initialSize = size_t.max)
2659 {
2660     return BinaryHeap!Store(s, initialSize);
2661 }
2662
2663 unittest
2664 {
2665     {
2666         // example from "Introduction to Algorithms" Cormen et al., p 146
2667         int[] a = [ 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 ];
2668         auto h = heapify(a);
2669         assert(h.front == 16);
2670         assert(a == [ 16, 14, 10, 8, 7, 9, 3, 2, 4, 1 ]);
2671         auto witness = [ 16, 14, 10, 9, 8, 7, 4, 3, 2, 1 ];
2672         for (; !h.empty; h.removeFront(), witness.popFront())
2673         {
2674             assert(!witness.empty);
2675             assert(witness.front == h.front);
2676         }
2677         assert(witness.empty);
2678     }
2679     {
2680         int[] a = [ 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 ];
2681         int[] b = new int[a.length];
2682         BinaryHeap!(int[]) h = BinaryHeap!(int[])(b, 0);
2683         foreach (e; a)
2684         {
2685             h.insert(e);
2686         }
2687         assert(b == [ 16, 14, 10, 8, 7, 3, 9, 1, 4, 2 ], text(b));
2688     }
2689 }
2690
2691 ////////////////////////////////////////////////////////////////////////////////
2692 // Array!bool
2693 ////////////////////////////////////////////////////////////////////////////////
2694
2695 /**
2696 _Array specialized for $(D bool). Packs together values efficiently by
2697 allocating one bit per element.
2698  */
2699 struct Array(T) if (is(T == bool))
2700 {
2701     static immutable uint bitsPerWord = size_t.sizeof * 8;
2702     private alias Tuple!(Array!(size_t).Payload, "_backend", ulong, "_length")
2703     Data;
2704     private RefCounted!(Data, RefCountedAutoInitialize.no) _store;
2705
2706     private ref size_t[] data()
2707     {
2708         assert(_store.RefCounted.isInitialized);
2709         return _store._backend._payload;
2710     }
2711
2712     private ref size_t dataCapacity()
2713     {
2714         return _store._backend._capacity;
2715     }
2716
2717     /**
2718        Defines the container's primary range.
2719      */
2720     struct Range
2721     {
2722         private Array!bool _outer;
2723         private ulong _a, _b;
2724         /// Range primitives
2725         @property Range save()
2726         {
2727             version (bug4437)
2728             {
2729                 return this;
2730             }
2731             else
2732             {
2733                 auto copy = this;
2734                 return copy;
2735             }
2736         }
2737         /// Ditto
2738         @property bool empty()
2739         {
2740             return _a >= _b || _outer.length < _b;
2741         }
2742         /// Ditto
2743         @property T front()
2744         {
2745             enforce(!empty);
2746             return _outer[_a];
2747         }
2748         /// Ditto
2749         @property void front(bool value)
2750         {
2751             enforce(!empty);
2752             _outer[_a] = value;
2753         }
2754         /// Ditto
2755         T moveFront()
2756         {
2757             enforce(!empty);
2758             return _outer.moveAt(_a);
2759         }
2760         /// Ditto
2761         void popFront()
2762         {
2763             enforce(!empty);
2764             ++_a;
2765         }
2766         /// Ditto
2767         @property T back()
2768         {
2769             enforce(!empty);
2770             return _outer[_b - 1];
2771         }
2772         /// Ditto
2773         T moveBack()
2774         {
2775             enforce(!empty);
2776             return _outer.moveAt(_b - 1);
2777         }
2778         /// Ditto
2779         void popBack()
2780         {
2781             enforce(!empty);
2782             --_b;
2783         }
2784         /// Ditto
2785         T opIndex(size_t i)
2786         {
2787             return _outer[_a + i];
2788         }
2789         /// Ditto
2790         void opIndexAssign(T value, size_t i)
2791         {
2792             _outer[_a + i] = value;
2793         }
2794         /// Ditto
2795         T moveAt(size_t i)
2796         {
2797             return _outer.moveAt(_a + i);
2798         }
2799         /// Ditto
2800         @property ulong length() const
2801         {
2802             assert(_a <= _b);
2803             return _b - _a;
2804         }
2805     }
2806
2807     /**
2808        Property returning $(D true) if and only if the container has
2809        no elements.
2810
2811        Complexity: $(BIGOH 1)
2812      */
2813     @property bool empty()
2814     {
2815         return !length;
2816     }
2817
2818     unittest
2819     {
2820         Array!bool a;
2821         //a._store._refCountedDebug = true;
2822         assert(a.empty);
2823         a.insertBack(false);
2824         assert(!a.empty);
2825     }
2826
2827     /**
2828        Returns a duplicate of the container. The elements themselves
2829        are not transitively duplicated.
2830
2831        Complexity: $(BIGOH n).
2832      */
2833     @property Array!bool dup()
2834     {
2835         Array!bool result;
2836         result.insertBack(this[]);
2837         return result;
2838     }
2839
2840     unittest
2841     {
2842         Array!bool a;
2843         assert(a.empty);
2844         auto b = a.dup;
2845         assert(b.empty);
2846         a.insertBack(true);
2847         assert(b.empty);
2848     }
2849
2850     /**
2851        Returns the number of elements in the container.
2852
2853        Complexity: $(BIGOH log(n)).
2854     */
2855     @property ulong length()
2856     {
2857         return _store.RefCounted.isInitialized ? _store._length : 0;
2858     }
2859
2860     unittest
2861     {
2862         Array!bool a;
2863         assert(a.length == 0);
2864         a.insert(true);
2865         assert(a.length == 1, text(a.length));
2866     }
2867
2868     /**
2869        Returns the maximum number of elements the container can store
2870        without (a) allocating memory, (b) invalidating iterators upon
2871        insertion.
2872
2873        Complexity: $(BIGOH log(n)).
2874      */
2875     @property ulong capacity()
2876     {
2877         return _store.RefCounted.isInitialized
2878             ? cast(ulong) bitsPerWord * _store._backend.capacity
2879             : 0;
2880     }
2881
2882     unittest
2883     {
2884         Array!bool a;
2885         assert(a.capacity == 0);
2886         foreach (i; 0 .. 100)
2887         {
2888             a.insert(true);
2889             assert(a.capacity >= a.length, text(a.capacity));
2890         }
2891     }
2892
2893     /**
2894        Ensures sufficient capacity to accommodate $(D n) elements.
2895
2896        Postcondition: $(D capacity >= n)
2897
2898        Complexity: $(BIGOH log(e - capacity)) if $(D e > capacity),
2899        otherwise $(BIGOH 1).
2900      */
2901     void reserve(ulong e)
2902     {
2903         _store.RefCounted.ensureInitialized();
2904         _store._backend.reserve(to!size_t((e + bitsPerWord - 1) / bitsPerWord));
2905     }
2906
2907     unittest
2908     {
2909         Array!bool a;
2910         assert(a.capacity == 0);
2911         a.reserve(15657);
2912         assert(a.capacity >= 15657);
2913     }
2914
2915     /**
2916        Returns a range that iterates over all elements of the
2917        container, in a container-defined order. The container should
2918        choose the most convenient and fast method of iteration for $(D
2919        opSlice()).
2920
2921        Complexity: $(BIGOH log(n))
2922      */
2923     Range opSlice()
2924     {
2925         return Range(this, 0, length);
2926     }
2927
2928     unittest
2929     {
2930         Array!bool a;
2931         a.insertBack([true, false, true, true]);
2932         assert(a[].length == 4);
2933     }
2934
2935     /**
2936        Returns a range that iterates the container between two
2937        specified positions.
2938
2939        Complexity: $(BIGOH log(n))
2940      */
2941     Range opSlice(ulong a, ulong b)
2942     {
2943         enforce(a <= b && b <= length);
2944         return Range(this, a, b);
2945     }
2946
2947     unittest
2948     {
2949         Array!bool a;
2950         a.insertBack([true, false, true, true]);
2951         assert(a[0 .. 2].length == 2);
2952     }
2953
2954     /**
2955        Equivalent to $(D opSlice().front) and $(D opSlice().back),
2956        respectively.
2957
2958        Complexity: $(BIGOH log(n))
2959      */
2960     @property bool front()
2961     {
2962         enforce(!empty);
2963         return data.ptr[0] & 1;
2964     }
2965
2966     /// Ditto
2967     @property void front(bool value)
2968     {
2969         enforce(!empty);
2970         if (value) data.ptr[0] |= 1;
2971         else data.ptr[0] &= ~cast(size_t) 1;
2972     }
2973
2974     unittest
2975     {
2976         Array!bool a;
2977         a.insertBack([true, false, true, true]);
2978         assert(a.front);
2979         a.front = false;
2980         assert(!a.front);
2981     }
2982
2983     /// Ditto
2984     @property bool back()
2985     {
2986         enforce(!empty);
2987         return data.back & (1u << ((_store._length - 1) % bitsPerWord));
2988     }
2989
2990     /// Ditto
2991     @property void back(bool value)
2992     {
2993         enforce(!empty);
2994         if (value)
2995         {
2996             data.back |= (1u << ((_store._length - 1) % bitsPerWord));
2997         }
2998         else
2999         {
3000             data.back &=
3001                 ~(cast(size_t)1 << ((_store._length - 1) % bitsPerWord));
3002         }
3003     }
3004
3005     unittest
3006     {
3007         Array!bool a;
3008         a.insertBack([true, false, true, true]);
3009         assert(a.back);
3010         a.back = false;
3011         assert(!a.back);
3012     }
3013
3014     /**
3015        Indexing operators yield or modify the value at a specified index.
3016      */
3017     bool opIndex(ulong i)
3018     {
3019         auto div = cast(size_t) (i / bitsPerWord);
3020         auto rem = i % bitsPerWord;
3021         enforce(div < data.length);
3022         return data.ptr[div] & (1u << rem);
3023     }
3024     /// ditto
3025     void opIndexAssign(bool value, ulong i)
3026     {
3027         auto div = cast(size_t) (i / bitsPerWord);
3028         auto rem = i % bitsPerWord;
3029         enforce(div < data.length);
3030         if (value) data.ptr[div] |= (1u << rem);
3031         else data.ptr[div] &= ~(cast(size_t)1 << rem);
3032     }
3033     /// ditto
3034     void opIndexOpAssign(string op)(bool value, ulong i)
3035     {
3036         auto div = cast(size_t) (i / bitsPerWord);
3037         auto rem = i % bitsPerWord;
3038         enforce(div < data.length);
3039         auto oldValue = cast(bool) (data.ptr[div] & (1u << rem));
3040         // Do the deed
3041         auto newValue = mixin("oldValue "~op~" value");
3042         // Write back the value
3043         if (newValue != oldValue)
3044         {
3045             if (newValue) data.ptr[div] |= (1u << rem);
3046             else data.ptr[div] &= ~(cast(size_t)1 << rem);
3047         }
3048     }
3049     /// Ditto
3050     T moveAt(ulong i)
3051     {
3052         return this[i];
3053     }
3054
3055     unittest
3056     {
3057         Array!bool a;
3058         a.insertBack([true, false, true, true]);
3059         assert(a[0] && !a[1]);
3060         a[0] &= a[1];
3061         assert(!a[0]);
3062     }
3063
3064     /**
3065        Returns a new container that's the concatenation of $(D this)
3066        and its argument.
3067
3068        Complexity: $(BIGOH n + m), where m is the number of elements
3069        in $(D stuff)
3070      */
3071     Array!bool opBinary(string op, Stuff)(Stuff rhs) if (op == "~")
3072     {
3073         auto result = this;
3074         return result ~= rhs;
3075     }
3076
3077     unittest
3078     {
3079         Array!bool a;
3080         a.insertBack([true, false, true, true]);
3081         Array!bool b;
3082         b.insertBack([true, true, false, true]);
3083         assert(equal((a ~ b)[],
3084                         [true, false, true, true, true, true, false, true]));
3085     }
3086
3087     // /// ditto
3088     // TotalContainer opBinaryRight(Stuff, string op)(Stuff lhs) if (op == "~")
3089     // {
3090     //     assert(0);
3091     // }
3092
3093     /**
3094        Forwards to $(D insertAfter(this[], stuff)).
3095      */
3096     // @@@BUG@@@
3097     //ref Array!bool opOpAssign(string op, Stuff)(Stuff stuff) if (op == "~")
3098     Array!bool opOpAssign(string op, Stuff)(Stuff stuff) if (op == "~")
3099     {
3100         static if (is(typeof(stuff[]))) insertBack(stuff[]);
3101         else insertBack(stuff);
3102         return this;
3103     }
3104
3105     unittest
3106     {
3107         Array!bool a;
3108         a.insertBack([true, false, true, true]);
3109         Array!bool b;
3110         a.insertBack([false, true, false, true, true]);
3111         a ~= b;
3112         assert(equal(
3113                     a[],
3114                     [true, false, true, true, false, true, false, true, true]));
3115     }
3116
3117     /**
3118        Removes all contents from the container. The container decides
3119        how $(D capacity) is affected.
3120
3121        Postcondition: $(D empty)
3122
3123        Complexity: $(BIGOH n)
3124      */
3125     void clear()
3126     {
3127         this = Array!bool();
3128     }
3129
3130     unittest
3131     {
3132         Array!bool a;
3133         a.insertBack([true, false, true, true]);
3134         a.clear();
3135         assert(a.capacity == 0);
3136     }
3137
3138     /**
3139        Sets the number of elements in the container to $(D
3140        newSize). If $(D newSize) is greater than $(D length), the
3141        added elements are added to the container and initialized with
3142        $(D ElementType.init).
3143
3144        Complexity: $(BIGOH abs(n - newLength))
3145
3146        Postcondition: $(D _length == newLength)
3147      */
3148     @property void length(ulong newLength)
3149     {
3150         _store.RefCounted.ensureInitialized();
3151         auto newDataLength =
3152             to!size_t((newLength + bitsPerWord - 1) / bitsPerWord);
3153         _store._backend.length = newDataLength;
3154         _store._length = newLength;
3155     }
3156
3157     unittest
3158     {
3159         Array!bool a;
3160         a.length = 1057;
3161         assert(a.length == 1057);
3162         foreach (e; a)
3163         {
3164             assert(!e);
3165         }
3166     }
3167
3168     /**
3169        Inserts $(D stuff) in the container. $(D stuff) can be a value
3170        convertible to $(D ElementType) or a range of objects
3171        convertible to $(D ElementType).
3172
3173        The $(D stable) version guarantees that ranges iterating over
3174        the container are never invalidated. Client code that counts on
3175        non-invalidating insertion should use $(D stableInsert).
3176
3177        Returns: The number of elements added.
3178
3179        Complexity: $(BIGOH m * log(n)), where $(D m) is the number of
3180        elements in $(D stuff)
3181      */
3182     alias insertBack insert;
3183     ///ditto
3184     alias insertBack stableInsert;
3185
3186     /**
3187        Same as $(D insert(stuff)) and $(D stableInsert(stuff))
3188        respectively, but relax the complexity constraint to linear.
3189      */
3190     alias insertBack linearInsert;
3191     ///ditto
3192     alias insertBack stableLinearInsert;
3193
3194     /**
3195        Picks one value in the container, removes it from the
3196        container, and returns it. The stable version behaves the same,
3197        but guarantees that ranges iterating over the container are
3198        never invalidated.
3199
3200        Precondition: $(D !empty)
3201
3202        Returns: The element removed.
3203
3204        Complexity: $(BIGOH log(n))
3205      */
3206     T removeAny()
3207     {
3208         auto result = back();
3209         removeBack();
3210         return result;
3211     }
3212     /// ditto
3213     alias removeAny stableRemoveAny;
3214
3215     unittest
3216     {
3217         Array!bool a;
3218         a.length = 1057;
3219         assert(!a.removeAny());
3220         assert(a.length == 1056);
3221         foreach (e; a)
3222         {
3223             assert(!e);
3224         }
3225     }
3226
3227     /**
3228        Inserts $(D value) to the back of the container. $(D stuff) can
3229        be a value convertible to $(D ElementType) or a range of
3230        objects convertible to $(D ElementType). The stable version
3231        behaves the same, but guarantees that ranges iterating over the
3232        container are never invalidated.
3233
3234        Returns: The number of elements inserted
3235
3236        Complexity: $(BIGOH log(n))
3237      */
3238     ulong insertBack(Stuff)(Stuff stuff) if (is(Stuff : bool))
3239     {
3240         _store.RefCounted.ensureInitialized();
3241         auto rem = _store._length % bitsPerWord;
3242         if (rem)
3243         {
3244             // Fits within the current array
3245             if (stuff)
3246             {
3247                 data[$ - 1] |= (1u << rem);
3248             }
3249             else
3250             {
3251                 data[$ - 1] &= ~(1u << rem);
3252             }
3253         }
3254         else
3255         {
3256             // Need to add more data
3257             _store._backend.insertBack(stuff);
3258         }
3259         ++_store._length;
3260         return 1;
3261     }
3262     /// Ditto
3263     ulong insertBack(Stuff)(Stuff stuff)
3264     if (isInputRange!Stuff && is(ElementType!Stuff : bool))
3265     {
3266         static if (!hasLength!Stuff) ulong result;
3267         for (; !stuff.empty; stuff.popFront())
3268         {
3269             insertBack(stuff.front);
3270             static if (!hasLength!Stuff) ++result;
3271         }
3272         static if (!hasLength!Stuff) return result;
3273         else return stuff.length;
3274     }
3275     /// ditto
3276     alias insertBack stableInsertBack;
3277
3278     /**
3279        Removes the value at the front or back of the container. The
3280        stable version behaves the same, but guarantees that ranges
3281        iterating over the container are never invalidated. The
3282        optional parameter $(D howMany) instructs removal of that many
3283        elements. If $(D howMany > n), all elements are removed and no
3284        exception is thrown.
3285
3286        Precondition: $(D !empty)
3287
3288        Complexity: $(BIGOH log(n)).
3289      */
3290     void removeBack()
3291     {
3292         enforce(_store._length);
3293         if (_store._length % bitsPerWord)
3294         {
3295             // Cool, just decrease the length
3296             --_store._length;
3297         }
3298         else
3299         {
3300             // Reduce the allocated space
3301             --_store._length;
3302             _store._backend.length = _store._backend.length - 1;
3303         }
3304     }
3305     /// ditto
3306     alias removeBack stableRemoveBack;
3307
3308     /**
3309        Removes $(D howMany) values at the front or back of the
3310        container. Unlike the unparameterized versions above, these
3311        functions do not throw if they could not remove $(D howMany)
3312        elements. Instead, if $(D howMany > n), all elements are
3313        removed. The returned value is the effective number of elements
3314        removed. The stable version behaves the same, but guarantees
3315        that ranges iterating over the container are never invalidated.
3316
3317        Returns: The number of elements removed
3318
3319        Complexity: $(BIGOH howMany * log(n)).
3320      */
3321     /// ditto
3322     ulong removeBack(ulong howMany)
3323     {
3324         if (howMany >= length)
3325         {
3326             howMany = length;
3327             clear();
3328         }
3329         else
3330         {
3331             length = length - howMany;
3332         }
3333         return howMany;
3334     }
3335
3336     unittest
3337     {
3338         Array!bool a;
3339         a.length = 1057;
3340         assert(a.removeBack(1000) == 1000);
3341         assert(a.length == 57);
3342         foreach (e; a)
3343         {
3344             assert(!e);
3345         }
3346     }
3347
3348     /**
3349        Inserts $(D stuff) before, after, or instead range $(D r),
3350        which must be a valid range previously extracted from this
3351        container. $(D stuff) can be a value convertible to $(D
3352        ElementType) or a range of objects convertible to $(D
3353        ElementType). The stable version behaves the same, but
3354        guarantees that ranges iterating over the container are never
3355        invalidated.
3356
3357        Returns: The number of values inserted.
3358
3359        Complexity: $(BIGOH n + m), where $(D m) is the length of $(D stuff)
3360      */
3361     ulong insertBefore(Stuff)(Range r, Stuff stuff)
3362     {
3363         // TODO: make this faster, it moves one bit at a time
3364         immutable inserted = stableInsertBack(stuff);
3365         immutable tailLength = length - inserted;
3366         bringToFront(
3367             this[r._a .. tailLength],
3368             this[tailLength .. length]);
3369         return inserted;
3370     }
3371     /// ditto
3372     alias insertBefore stableInsertBefore;
3373
3374     unittest
3375     {
3376         Array!bool a;
3377         version (bugxxxx)
3378         {
3379             a._store.refCountedDebug = true;
3380         }
3381         a.insertBefore(a[], true);
3382         assert(a.length == 1, text(a.length));
3383         a.insertBefore(a[], false);
3384         assert(a.length == 2, text(a.length));
3385     }
3386
3387     /// ditto
3388     ulong insertAfter(Stuff)(Range r, Stuff stuff)
3389     {
3390         // TODO: make this faster, it moves one bit at a time
3391         immutable inserted = stableInsertBack(stuff);
3392         immutable tailLength = length - inserted;
3393         bringToFront(
3394             this[r._b .. tailLength],
3395             this[tailLength .. length]);
3396         return inserted;
3397     }
3398     /// ditto
3399     alias insertAfter stableInsertAfter;
3400
3401     unittest
3402     {
3403         Array!bool a;
3404         a.length = 10;
3405         a.insertAfter(a[0 .. 5], true);
3406         assert(a.length == 11, text(a.length));
3407         assert(a[5]);
3408     }
3409     /// ditto
3410     size_t replace(Stuff)(Range r, Stuff stuff) if (is(Stuff : bool))
3411     {
3412         if (!r.empty)
3413         {
3414             // There is room
3415             r.front = stuff;
3416             r.popFront();
3417             linearRemove(r);
3418         }
3419         else
3420         {
3421             // No room, must insert
3422             insertBefore(r, stuff);
3423         }
3424         return 1;
3425     }
3426     /// ditto
3427     alias replace stableReplace;
3428
3429     unittest
3430     {
3431         Array!bool a;
3432         a.length = 10;
3433         a.replace(a[3 .. 5], true);
3434         assert(a.length == 9, text(a.length));
3435         assert(a[3]);
3436     }
3437
3438     /**
3439        Removes all elements belonging to $(D r), which must be a range
3440        obtained originally from this container. The stable version
3441        behaves the same, but guarantees that ranges iterating over the
3442        container are never invalidated.
3443
3444        Returns: A range spanning the remaining elements in the container that
3445        initially were right after $(D r).
3446
3447        Complexity: $(BIGOH n)
3448      */
3449     Range linearRemove(Range r)
3450     {
3451         copy(this[r._b .. length], this[r._a .. length]);
3452         length = length - r.length;
3453         return this[r._a .. length];
3454     }
3455     /// ditto
3456     alias linearRemove stableLinearRemove;
3457 }
3458
3459 unittest
3460 {
3461     Array!bool a;
3462     assert(a.empty);
3463 }
3464
3465 /*
3466  * Implementation for a Red Black node for use in a Red Black Tree (see below)
3467  *
3468  * this implementation assumes we have a marker Node that is the parent of the
3469  * root Node.  This marker Node is not a valid Node, but marks the end of the
3470  * collection.  The root is the left child of the marker Node, so it is always
3471  * last in the collection.  The marker Node is passed in to the setColor
3472  * function, and the Node which has this Node as its parent is assumed to be
3473  * the root Node.
3474  *
3475  * A Red Black tree should have O(lg(n)) insertion, removal, and search time.
3476  */
3477 struct RBNode(V)
3478 {
3479     /*
3480      * Convenience alias
3481      */
3482     alias RBNode* Node;
3483
3484     private Node _left;
3485     private Node _right;
3486     private Node _parent;
3487
3488     /**
3489      * The value held by this node
3490      */
3491     V value;
3492
3493     /**
3494      * Enumeration determining what color the node is.  Null nodes are assumed
3495      * to be black.
3496      */
3497     enum Color : byte
3498     {
3499         Red,
3500         Black
3501     }
3502
3503     /**
3504      * The color of the node.
3505      */
3506     Color color;
3507
3508     /**
3509      * Get the left child
3510      */
3511     @property Node left()
3512     {
3513         return _left;
3514     }
3515
3516     /**
3517      * Get the right child
3518      */
3519     @property Node right()
3520     {
3521         return _right;
3522     }
3523
3524     /**
3525      * Get the parent
3526      */
3527     @property Node parent()
3528     {
3529         return _parent;
3530     }
3531
3532     /**
3533      * Set the left child.  Also updates the new child's parent node.  This
3534      * does not update the previous child.
3535      *
3536      * Returns newNode
3537      */
3538     @property Node left(Node newNode)
3539     {
3540         _left = newNode;
3541         if(newNode !is null)
3542             newNode._parent = &this;
3543         return newNode;
3544     }
3545
3546     /**
3547      * Set the right child.  Also updates the new child's parent node.  This
3548      * does not update the previous child.
3549      *
3550      * Returns newNode
3551      */
3552     @property Node right(Node newNode)
3553     {
3554         _right = newNode;
3555         if(newNode !is null)
3556             newNode._parent = &this;
3557         return newNode;
3558     }
3559
3560     // assume _left is not null
3561     //
3562     // performs rotate-right operation, where this is T, _right is R, _left is
3563     // L, _parent is P:
3564     //
3565     //      P         P
3566     //      |   ->    |
3567     //      T         L
3568     //     / \       / \
3569     //    L   R     a   T
3570     //   / \           / \
3571     //  a   b         b   R
3572     //
3573     /**
3574      * Rotate right.  This performs the following operations:
3575      *  - The left child becomes the parent of this node.
3576      *  - This node becomes the new parent's right child.
3577      *  - The old right child of the new parent becomes the left child of this
3578      *    node.
3579      */
3580     Node rotateR()
3581     in
3582     {
3583         assert(_left !is null);
3584     }
3585     body
3586     {
3587         // sets _left._parent also
3588         if(isLeftNode)
3589             parent.left = _left;
3590         else
3591             parent.right = _left;
3592         Node tmp = _left._right;
3593
3594         // sets _parent also
3595         _left.right = &this;
3596
3597         // sets tmp._parent also
3598         left = tmp;
3599
3600         return &this;
3601     }
3602
3603     // assumes _right is non null
3604     //
3605     // performs rotate-left operation, where this is T, _right is R, _left is
3606     // L, _parent is P:
3607     //
3608     //      P           P
3609     //      |    ->     |
3610     //      T           R
3611     //     / \         / \
3612     //    L   R       T   b
3613     //       / \     / \
3614     //      a   b   L   a
3615     //
3616     /**
3617      * Rotate left.  This performs the following operations:
3618      *  - The right child becomes the parent of this node.
3619      *  - This node becomes the new parent's left child.
3620      *  - The old left child of the new parent becomes the right child of this
3621      *    node.
3622      */
3623     Node rotateL()
3624     in
3625     {
3626         assert(_right !is null);
3627     }
3628     body
3629     {
3630         // sets _right._parent also
3631         if(isLeftNode)
3632             parent.left = _right;
3633         else
3634             parent.right = _right;
3635         Node tmp = _right._left;
3636
3637         // sets _parent also
3638         _right.left = &this;
3639
3640         // sets tmp._parent also
3641         right = tmp;
3642         return &this;
3643     }
3644
3645
3646     /**
3647      * Returns true if this node is a left child.
3648      *
3649      * Note that this should always return a value because the root has a
3650      * parent which is the marker node.
3651      */
3652     @property bool isLeftNode() const
3653     in
3654     {
3655         assert(_parent !is null);
3656     }
3657     body
3658     {
3659         return _parent._left is &this;
3660     }
3661
3662     /**
3663      * Set the color of the node after it is inserted.  This performs an
3664      * update to the whole tree, possibly rotating nodes to keep the Red-Black
3665      * properties correct.  This is an O(lg(n)) operation, where n is the
3666      * number of nodes in the tree.
3667      *
3668      * end is the marker node, which is the parent of the topmost valid node.
3669      */
3670     void setColor(Node end)
3671     {
3672         // test against the marker node
3673         if(_parent !is end)
3674         {
3675             if(_parent.color == Color.Red)
3676             {
3677                 Node cur = &this;
3678                 while(true)
3679                 {
3680                     // because root is always black, _parent._parent always exists
3681                     if(cur._parent.isLeftNode)
3682                     {
3683                         // parent is left node, y is 'uncle', could be null
3684                         Node y = cur._parent._parent._right;
3685                         if(y !is null && y.color == Color.Red)
3686                         {
3687                             cur._parent.color = Color.Black;
3688                             y.color = Color.Black;
3689                             cur = cur._parent._parent;
3690                             if(cur._parent is end)
3691                             {
3692                                 // root node
3693                                 cur.color = Color.Black;
3694                                 break;
3695                             }
3696                             else
3697                             {
3698                                 // not root node
3699                                 cur.color = Color.Red;
3700                                 if(cur._parent.color == Color.Black)
3701                                     // satisfied, exit the loop
3702                                     break;
3703                             }
3704                         }
3705                         else
3706                         {
3707                             if(!cur.isLeftNode)
3708                                 cur = cur._parent.rotateL();
3709                             cur._parent.color = Color.Black;
3710                             cur = cur._parent._parent.rotateR();
3711                             cur.color = Color.Red;
3712                             // tree should be satisfied now
3713                             break;
3714                         }
3715                     }
3716                     else
3717                     {
3718                         // parent is right node, y is 'uncle'
3719                         Node y = cur._parent._parent._left;
3720                         if(y !is null && y.color == Color.Red)
3721                         {
3722                             cur._parent.color = Color.Black;
3723                             y.color = Color.Black;
3724                             cur = cur._parent._parent;
3725                             if(cur._parent is end)
3726                             {
3727                                 // root node
3728                                 cur.color = Color.Black;
3729                                 break;
3730                             }
3731                             else
3732                             {
3733                                 // not root node
3734                                 cur.color = Color.Red;
3735                                 if(cur._parent.color == Color.Black)
3736                                     // satisfied, exit the loop
3737                                     break;
3738                             }
3739                         }
3740                         else
3741                         {
3742                             if(cur.isLeftNode)
3743                                 cur = cur._parent.rotateR();
3744                             cur._parent.color = Color.Black;
3745                             cur = cur._parent._parent.rotateL();
3746                             cur.color = Color.Red;
3747                             // tree should be satisfied now
3748                             break;
3749                         }
3750                     }
3751                 }
3752
3753             }
3754         }
3755         else
3756         {
3757             //
3758             // this is the root node, color it black
3759             //
3760             color = Color.Black;
3761         }
3762     }
3763
3764     /**
3765      * Remove this node from the tree.  The 'end' node is used as the marker
3766      * which is root's parent.  Note that this cannot be null!
3767      *
3768      * Returns the next highest valued node in the tree after this one, or end
3769      * if this was the highest-valued node.
3770      */
3771     Node remove(Node end)
3772     {
3773         //
3774         // remove this node from the tree, fixing the color if necessary.
3775         //
3776         Node x;
3777         Node ret;
3778         if(_left is null || _right is null)
3779         {
3780             ret = next;
3781         }
3782         else
3783         {
3784             //
3785             // normally, we can just swap this node's and y's value, but
3786             // because an iterator could be pointing to y and we don't want to
3787             // disturb it, we swap this node and y's structure instead.  This
3788             // can also be a benefit if the value of the tree is a large
3789             // struct, which takes a long time to copy.
3790             //
3791             Node yp, yl, yr;
3792             Node y = next;
3793             yp = y._parent;
3794             yl = y._left;
3795             yr = y._right;
3796             auto yc = y.color;
3797             auto isyleft = y.isLeftNode;
3798
3799             //
3800             // replace y's structure with structure of this node.
3801             //
3802             if(isLeftNode)
3803                 _parent.left = y;
3804             else
3805                 _parent.right = y;
3806             //
3807             // need special case so y doesn't point back to itself
3808             //
3809             y.left = _left;
3810             if(_right is y)
3811                 y.right = &this;
3812             else
3813                 y.right = _right;
3814             y.color = color;
3815
3816             //
3817             // replace this node's structure with structure of y.
3818             //
3819             left = yl;
3820             right = yr;
3821             if(_parent !is y)
3822             {
3823                 if(isyleft)
3824                     yp.left = &this;
3825                 else
3826                     yp.right = &this;
3827             }
3828             color = yc;
3829
3830             //
3831             // set return value
3832             //
3833             ret = y;
3834         }
3835
3836         // if this has less than 2 children, remove it
3837         if(_left !is null)
3838             x = _left;
3839         else
3840             x = _right;
3841
3842         // remove this from the tree at the end of the procedure
3843         bool removeThis = false;
3844         if(x is null)
3845         {
3846             // pretend this is a null node, remove this on finishing
3847             x = &this;
3848             removeThis = true;
3849         }
3850         else if(isLeftNode)
3851             _parent.left = x;
3852         else
3853             _parent.right = x;
3854
3855         // if the color of this is black, then it needs to be fixed
3856         if(color == color.Black)
3857         {
3858             // need to recolor the tree.
3859             while(x._parent !is end && x.color == Node.Color.Black)
3860             {
3861                 if(x.isLeftNode)
3862                 {
3863                     // left node
3864                     Node w = x._parent._right;
3865                     if(w.color == Node.Color.Red)
3866                     {
3867                         w.color = Node.Color.Black;
3868                         x._parent.color = Node.Color.Red;
3869                         x._parent.rotateL();
3870                         w = x._parent._right;
3871                     }
3872                     Node wl = w.left;
3873                     Node wr = w.right;
3874                     if((wl is null || wl.color == Node.Color.Black) &&
3875                             (wr is null || wr.color == Node.Color.Black))
3876                     {
3877                         w.color = Node.Color.Red;
3878                         x = x._parent;
3879                     }
3880                     else
3881                     {
3882                         if(wr is null || wr.color == Node.Color.Black)
3883                         {
3884                             // wl cannot be null here
3885                             wl.color = Node.Color.Black;
3886                             w.color = Node.Color.Red;
3887                             w.rotateR();
3888                             w = x._parent._right;
3889                         }
3890
3891                         w.color = x._parent.color;
3892                         x._parent.color = Node.Color.Black;
3893                         w._right.color = Node.Color.Black;
3894                         x._parent.rotateL();
3895                         x = end.left; // x = root
3896                     }
3897                 }
3898                 else
3899                 {
3900                     // right node
3901                     Node w = x._parent._left;
3902                     if(w.color == Node.Color.Red)
3903                     {
3904                         w.color = Node.Color.Black;
3905                         x._parent.color = Node.Color.Red;
3906                         x._parent.rotateR();
3907                         w = x._parent._left;
3908                     }
3909                     Node wl = w.left;
3910                     Node wr = w.right;
3911                     if((wl is null || wl.color == Node.Color.Black) &&
3912                             (wr is null || wr.color == Node.Color.Black))
3913                     {
3914                         w.color = Node.Color.Red;
3915                         x = x._parent;
3916                     }
3917                     else
3918                     {
3919                         if(wl is null || wl.color == Node.Color.Black)
3920                         {
3921                             // wr cannot be null here
3922                             wr.color = Node.Color.Black;
3923                             w.color = Node.Color.Red;
3924                             w.rotateL();
3925                             w = x._parent._left;
3926                         }
3927
3928                         w.color = x._parent.color;
3929                         x._parent.color = Node.Color.Black;
3930                         w._left.color = Node.Color.Black;
3931                         x._parent.rotateR();
3932                         x = end.left; // x = root
3933                     }
3934                 }
3935             }
3936             x.color = Node.Color.Black;
3937         }
3938
3939         if(removeThis)
3940         {
3941             //
3942             // clear this node out of the tree
3943             //
3944             if(isLeftNode)
3945                 _parent.left = null;
3946             else
3947                 _parent.right = null;
3948         }
3949
3950         return ret;
3951     }
3952
3953     /**
3954      * Return the leftmost descendant of this node.
3955      */
3956     @property Node leftmost()
3957     {
3958         Node result = &this;
3959         while(result._left !is null)
3960             result = result._left;
3961         return result;
3962     }
3963
3964     /**
3965      * Return the rightmost descendant of this node
3966      */
3967     @property Node rightmost()
3968     {
3969         Node result = &this;
3970         while(result._right !is null)
3971             result = result._right;
3972         return result;
3973     }
3974
3975     /**
3976      * Returns the next valued node in the tree.
3977      *
3978      * You should never call this on the marker node, as it is assumed that
3979      * there is a valid next node.
3980      */
3981     @property Node next()
3982     {
3983         Node n = &this;
3984         if(n.right is null)
3985         {
3986             while(!n.isLeftNode)
3987                 n = n._parent;
3988             return n._parent;
3989         }
3990         else
3991             return n.right.leftmost;
3992     }
3993
3994     /**
3995      * Returns the previous valued node in the tree.
3996      *
3997      * You should never call this on the leftmost node of the tree as it is
3998      * assumed that there is a valid previous node.
3999      */
4000     @property Node prev()
4001     {
4002         Node n = &this;
4003         if(n.left is null)
4004         {
4005             while(n.isLeftNode)
4006                 n = n._parent;
4007             return n._parent;
4008         }
4009         else
4010             return n.left.rightmost;
4011     }
4012
4013     Node dup(scope Node delegate(V v) alloc)
4014     {
4015         //
4016         // duplicate this and all child nodes
4017         //
4018         // The recursion should be lg(n), so we shouldn't have to worry about
4019         // stack size.
4020         //
4021         Node copy = alloc(value);
4022         copy.color = color;
4023         if(_left !is null)
4024             copy.left = _left.dup(alloc);
4025         if(_right !is null)
4026             copy.right = _right.dup(alloc);
4027         return copy;
4028     }
4029
4030     Node dup()
4031     {
4032         Node copy = new RBNode!V;
4033         copy.value = value;
4034         copy.color = color;
4035         if(_left !is null)
4036             copy.left = _left.dup();
4037         if(_right !is null)
4038             copy.right = _right.dup();
4039         return copy;
4040     }
4041 }
4042
4043 /**
4044  * Implementation of a $(LUCKY red-black tree) container.
4045  *
4046  * All inserts, removes, searches, and any function in general has complexity
4047  * of $(BIGOH lg(n)).
4048  *
4049  * To use a different comparison than $(D "a < b"), pass a different operator string
4050  * that can be used by $(XREF functional, binaryFun), or pass in a
4051  * function, delegate, functor, or any type where $(D less(a, b)) results in a $(D bool)
4052  * value.
4053  *
4054  * Note that less should produce a strict ordering.  That is, for two unequal
4055  * elements $(D a) and $(D b), $(D less(a, b) == !less(b, a)). $(D less(a, a)) should
4056  * always equal $(D false).
4057  *
4058  * If $(D allowDuplicates) is set to $(D true), then inserting the same element more than
4059  * once continues to add more elements.  If it is $(D false), duplicate elements are
4060  * ignored on insertion.  If duplicates are allowed, then new elements are
4061  * inserted after all existing duplicate elements.
4062  */
4063 struct RedBlackTree(T, alias less = "a < b", bool allowDuplicates = false)
4064 if (is(typeof(less(T.init, T.init)) == bool) || is(typeof(less) == string))
4065 {
4066     static if(is(typeof(less) == string))
4067         alias binaryFun!(less) _less;
4068     else
4069         alias less _less;
4070
4071     // BUG: this must come first in the struct due to issue 2810
4072
4073     // add an element to the tree, returns the node added, or the existing node
4074     // if it has already been added and allowDuplicates is false
4075
4076     private auto _add(Elem n)
4077     {
4078         Node result;
4079         static if(!allowDuplicates)
4080             bool added = true;
4081         if(!_end.left)
4082         {
4083             _end.left = result = allocate(n);
4084         }
4085         else
4086         {
4087             Node newParent = _end.left;
4088             Node nxt = void;
4089             while(true)
4090             {
4091                 if(_less(n, newParent.value))
4092                 {
4093                     nxt = newParent.left;
4094                     if(nxt is null)
4095                     {
4096                         //
4097                         // add to right of new parent
4098                         //
4099                         newParent.left = result = allocate(n);
4100                         break;
4101                     }
4102                 }
4103                 else
4104                 {
4105                     static if(!allowDuplicates)
4106                     {
4107                         if(!_less(newParent.value, n))
4108                         {
4109                             result = newParent;
4110                             added = false;
4111                             break;
4112                         }
4113                     }
4114                     nxt = newParent.right;
4115                     if(nxt is null)
4116                     {
4117                         //
4118                         // add to right of new parent
4119                         //
4120                         newParent.right = result = allocate(n);
4121                         break;
4122                     }
4123                 }
4124                 newParent = nxt;
4125             }
4126         }
4127
4128         static if(allowDuplicates)
4129         {
4130             result.setColor(_end);
4131             version(RBDoChecks)
4132                 check();
4133             return result;
4134         }
4135         else
4136         {
4137             if(added)
4138                 result.setColor(_end);
4139             version(RBDoChecks)
4140                 check();
4141             return Tuple!(bool, "added", Node, "n")(added, result);
4142         }
4143     }
4144
4145     version(unittest)
4146     {
4147         private enum doUnittest = isIntegral!T;
4148
4149         bool arrayEqual(T[] arr)
4150         {
4151             if(walkLength(this[]) == arr.length)
4152             {
4153                 foreach(v; arr)
4154                 {
4155                     if(!(v in this))
4156                         return false;
4157                 }
4158                 return true;
4159             }
4160             return false;
4161         }
4162
4163         private static RedBlackTree create(Elem[] elems...)
4164         {
4165             return RedBlackTree(elems);
4166         }
4167     }
4168     else
4169     {
4170         private enum doUnittest = false;
4171     }
4172
4173     /**
4174       * Element type for the tree
4175       */
4176     alias T Elem;
4177
4178     // used for convenience
4179     private alias RBNode!Elem.Node Node;
4180
4181     private Node _end;
4182
4183     private void _setup()
4184     {
4185         _end = allocate();
4186     }
4187
4188     static private Node allocate()
4189     {
4190         return new RBNode!Elem;
4191     }
4192
4193     static private Node allocate(Elem v)
4194     {
4195         auto result = allocate();
4196         result.value = v;
4197         return result;
4198     }
4199
4200     /**
4201      * The range type for $(D RedBlackTree)
4202      */
4203     struct Range
4204     {
4205         private Node _begin;
4206         private Node _end;
4207
4208         private this(Node b, Node e)
4209         {
4210             _begin = b;
4211             _end = e;
4212         }
4213
4214         /**
4215          * Returns $(D true) if the range is _empty
4216          */
4217         @property bool empty() const
4218         {
4219             return _begin is _end;
4220         }
4221
4222         /**
4223          * Returns the first element in the range
4224          */
4225         @property Elem front()
4226         {
4227             return _begin.value;
4228         }
4229
4230         /**
4231          * Returns the last element in the range
4232          */
4233         @property Elem back()
4234         {
4235             return _end.prev.value;
4236         }
4237
4238         /**
4239          * pop the front element from the range
4240          *
4241          * complexity: amortized $(BIGOH 1)
4242          */
4243         void popFront()
4244         {
4245             _begin = _begin.next;
4246         }
4247
4248         /**
4249          * pop the back element from the range
4250          *
4251          * complexity: amortized $(BIGOH 1)
4252          */
4253         void popBack()
4254         {
4255             _end = _end.prev;
4256         }
4257
4258         /**
4259          * Trivial _save implementation, needed for $(D isForwardRange).
4260          */
4261         @property Range save()
4262         {
4263             return this;
4264         }
4265     }
4266
4267     static if(doUnittest) unittest
4268     {
4269         auto ts = create(1, 2, 3, 4, 5);
4270         auto r = ts[];
4271         assert(std.algorithm.equal(r, cast(T[])[1, 2, 3, 4, 5]));
4272         assert(r.front == 1);
4273         assert(r.back != r.front);
4274         auto oldfront = r.front;
4275         auto oldback = r.back;
4276         r.popFront();
4277         r.popBack();
4278         assert(r.front != r.back);
4279         assert(r.front != oldfront);
4280         assert(r.back != oldback);
4281     }
4282
4283     // find a node based on an element value
4284     private Node _find(Elem e)
4285     {
4286         static if(allowDuplicates)
4287         {
4288             Node cur = _end.left;
4289             Node result = null;
4290             while(cur)
4291             {
4292                 if(_less(cur.value, e))
4293                     cur = cur.right;
4294                 else if(_less(e, cur.value))
4295                     cur = cur.left;
4296                 else
4297                 {
4298                     // want to find the left-most element
4299                     result = cur;
4300                     cur = cur.left;
4301                 }
4302             }
4303             return result;
4304         }
4305         else
4306         {
4307             Node cur = _end.left;
4308             while(cur)
4309             {
4310                 if(_less(cur.value, e))
4311                     cur = cur.right;
4312                 else if(_less(e, cur.value))
4313                     cur = cur.left;
4314                 else
4315                     return cur;
4316             }
4317             return null;
4318         }
4319     }
4320
4321     /**
4322      * Check if any elements exist in the container.  Returns $(D true) if at least
4323      * one element exists.
4324      */
4325     @property bool empty()
4326     {
4327         return _end.left is null;
4328     }
4329
4330     /**
4331      * Duplicate this container.  The resulting container contains a shallow
4332      * copy of the elements.
4333      *
4334      * Complexity: $(BIGOH n)
4335      */
4336     RedBlackTree dup()
4337     {
4338         RedBlackTree result;
4339         result._setup();
4340         result._end = _end.dup();
4341         return result;
4342     }
4343
4344     static if(doUnittest) unittest
4345     {
4346         auto ts = create(1, 2, 3, 4, 5);
4347         auto ts2 = ts.dup();
4348         assert(std.algorithm.equal(ts[], ts2[]));
4349         ts2.insert(cast(Elem)6);
4350         assert(!std.algorithm.equal(ts[], ts2[]));
4351     }
4352
4353     /**
4354      * Fetch a range that spans all the elements in the container.
4355      *
4356      * Complexity: $(BIGOH log(n))
4357      */
4358     Range opSlice()
4359     {
4360         return Range(_end.leftmost, _end);
4361     }
4362
4363     /**
4364      * The front element in the container
4365      *
4366      * Complexity: $(BIGOH log(n))
4367      */
4368     Elem front()
4369     {
4370         return _end.leftmost.value;
4371     }
4372
4373     /**
4374      * The last element in the container
4375      *
4376      * Complexity: $(BIGOH log(n))
4377      */
4378     Elem back()
4379     {
4380         return _end.prev.value;
4381     }
4382
4383     /**
4384      * Check to see if an element exists in the container
4385      *
4386      * Complexity: $(BIGOH log(n))
4387      */
4388     bool opBinaryRight(string op)(Elem e) if (op == "in")
4389     {
4390         return _find(e) !is null;
4391     }
4392
4393     static if(doUnittest) unittest
4394     {
4395         auto ts = create(1, 2, 3, 4, 5);
4396         assert(cast(Elem)3 in ts);
4397         assert(cast(Elem)6 !in ts);
4398     }
4399
4400     /**
4401      * Clear the container of all elements
4402      *
4403      * Complexity: $(BIGOH 1)
4404      */
4405     void clear()
4406     {
4407         _end.left = null;
4408     }
4409
4410     /**
4411      * Insert a single element in the container.  Note that this does not
4412      * invalidate any ranges currently iterating the container.
4413      *
4414      * Complexity: $(BIGOH log(n))
4415      */
4416     size_t stableInsert(Stuff)(Stuff stuff) if (isImplicitlyConvertible!(Stuff, Elem))
4417     {
4418         static if(allowDuplicates)
4419         {
4420             _add(stuff);
4421             return 1;
4422         }
4423         else
4424         {
4425             return(_add(stuff).added ? 1 : 0);
4426         }
4427     }
4428
4429     /**
4430      * Insert a range of elements in the container.  Note that this does not
4431      * invalidate any ranges currently iterating the container.
4432      *
4433      * Complexity: $(BIGOH m * log(n))
4434      */
4435     size_t stableInsert(Stuff)(Stuff stuff) if(isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, Elem))
4436     {
4437         size_t result = 0;
4438         static if(allowDuplicates)
4439         {
4440             foreach(e; stuff)
4441             {
4442                 ++result;
4443                 _add(e);
4444             }
4445         }
4446         else
4447         {
4448             foreach(e; stuff)
4449             {
4450                 if(_add(e).added)
4451                     ++result;
4452             }
4453         }
4454         return result;
4455     }
4456
4457     /// ditto
4458     alias stableInsert insert;
4459
4460     static if(doUnittest) unittest
4461     {
4462         auto ts = create(1,2,3,4,5);
4463         assert(ts.stableInsert(cast(Elem[])[6, 7, 8, 9, 10]) == 5);
4464         assert(ts.stableInsert(cast(Elem)11) == 1);
4465         assert(ts.arrayEqual([1,2,3,4,5,6,7,8,9,10,11]));
4466     }
4467
4468     /**
4469      * Remove an element from the container and return its value.
4470      *
4471      * Complexity: $(BIGOH log(n))
4472      */
4473     Elem removeAny()
4474     {
4475         auto n = _end.leftmost;
4476         auto result = n.value;
4477         n.remove(_end);
4478         version(RBDoChecks)
4479             check();
4480         return result;
4481     }
4482
4483     static if(doUnittest) unittest
4484     {
4485         auto ts = create(1,2,3,4,5);
4486         auto x = ts.removeAny();
4487         Elem[] arr;
4488         foreach(Elem i; 1..6)
4489             if(i != x) arr ~= i;
4490         assert(ts.arrayEqual(arr));
4491     }
4492
4493     /**
4494      * Remove the front element from the container.
4495      *
4496      * Complexity: $(BIGOH log(n))
4497      */
4498     void removeFront()
4499     {
4500         _end.leftmost.remove(_end);
4501         version(RBDoChecks)
4502             check();
4503     }
4504
4505     /**
4506      * Remove the back element from the container.
4507      *
4508      * Complexity: $(BIGOH log(n))
4509      */
4510     void removeBack()
4511     {
4512         _end.prev.remove(_end);
4513         version(RBDoChecks)
4514             check();
4515     }
4516
4517     static if(doUnittest) unittest
4518     {
4519         auto ts = create(1,2,3,4,5);
4520         ts.removeBack();
4521         assert(ts.arrayEqual([1,2,3,4]));
4522         ts.removeFront();
4523         assert(ts.arrayEqual([2,3,4]));
4524     }
4525
4526     /**
4527      * Remove the given range from the container.  Returns a range containing
4528      * all the elements that were after the given range.
4529      *
4530      * Complexity: $(BIGOH m * log(n))
4531      */
4532     Range remove(Range r)
4533     {
4534         auto b = r._begin;
4535         auto e = r._end;
4536         while(b !is e)
4537         {
4538             b = b.remove(_end);
4539         }
4540         version(RBDoChecks)
4541             check();
4542         return Range(e, _end);
4543     }
4544
4545     static if(doUnittest) unittest
4546     {
4547         auto ts = create(1,2,3,4,5);
4548         auto r = ts[];
4549         r.popFront();
4550         r.popBack();
4551         auto r2 = ts.remove(r);
4552         assert(ts.arrayEqual([1,5]));
4553         assert(std.algorithm.equal(r2, [5]));
4554     }
4555
4556     // find the first node where the value is > e
4557     private Node _firstGreater(Elem e)
4558     {
4559         // can't use _find, because we cannot return null
4560         auto cur = _end.left;
4561         auto result = _end;
4562         while(cur)
4563         {
4564             if(_less(e, cur.value))
4565             {
4566                 result = cur;
4567                 cur = cur.left;
4568             }
4569             else
4570                 cur = cur.right;
4571         }
4572         return result;
4573     }
4574
4575     // find the first node where the value is >= e
4576     private Node _firstGreaterEqual(Elem e)
4577     {
4578         // can't use _find, because we cannot return null.
4579         auto cur = _end.left;
4580         auto result = _end;
4581         while(cur)
4582         {
4583             if(_less(cur.value, e))
4584                 cur = cur.right;
4585             else
4586             {
4587                 result = cur;
4588                 cur = cur.left;
4589             }
4590                
4591         }
4592         return result;
4593     }
4594
4595     /**
4596      * Get a range from the container with all elements that are > e according
4597      * to the less comparator
4598      *
4599      * Complexity: $(BIGOH log(n))
4600      */
4601     Range upperBound(Elem e)
4602     {
4603         return Range(_firstGreater(e), _end);
4604     }
4605
4606     /**
4607      * Get a range from the container with all elements that are < e according
4608      * to the less comparator
4609      *
4610      * Complexity: $(BIGOH log(n))
4611      */
4612     Range lowerBound(Elem e)
4613     {
4614         return Range(_end.leftmost, _firstGreaterEqual(e));
4615     }
4616
4617     /**
4618      * Get a range from the container with all elements that are == e according
4619      * to the less comparator
4620      *
4621      * Complexity: $(BIGOH log(n))
4622      */
4623     Range equalRange(Elem e)
4624     {
4625         auto beg = _firstGreaterEqual(e);
4626         if(beg is _end || _less(e, beg.value))
4627             // no values are equal
4628             return Range(beg, beg);
4629         static if(allowDuplicates)
4630         {
4631             return Range(beg, _firstGreater(e));
4632         }
4633         else
4634         {
4635             // no sense in doing a full search, no duplicates are allowed,
4636             // so we just get the next node.
4637             return Range(beg, beg.next);
4638         }
4639     }
4640
4641     static if(doUnittest) unittest
4642     {
4643         auto ts = create(1, 2, 3, 4, 5);
4644         auto r1 = ts.lowerBound(3);
4645         assert(std.algorithm.equal(r1, [1,2]));
4646         auto r2 = ts.upperBound(3);
4647         assert(std.algorithm.equal(r2, [4,5]));
4648         auto r3 = ts.equalRange(3);
4649         assert(std.algorithm.equal(r3, [3]));
4650     }
4651
4652     version(RBDoChecks)
4653     {
4654         /**
4655          * Print the tree.  This prints a sideways view of the tree in ASCII form,
4656          * with the number of indentations representing the level of the nodes.
4657          * It does not print values, only the tree structure and color of nodes.
4658          */
4659         void printTree(Node n, int indent = 0)
4660         {
4661             if(n !is null)
4662             {
4663                 printTree(n.right, indent + 2);
4664                 for(int i = 0; i < indent; i++)
4665                     write(".");
4666                 writeln(n.color == n.color.Black ? "B" : "R");
4667                 printTree(n.left, indent + 2);
4668             }
4669             else
4670             {
4671                 for(int i = 0; i < indent; i++)
4672                     write(".");
4673                 writeln("N");
4674             }
4675             if(indent is 0)
4676                 writeln();
4677         }
4678
4679         /**
4680          * Check the tree for validity.  This is called after every add or remove.
4681          * This should only be enabled to debug the implementation of the RB Tree.
4682          */
4683         void check()
4684         {
4685             //
4686             // check implementation of the tree
4687             //
4688             int recurse(Node n, string path)
4689             {
4690                 if(n is null)
4691                     return 1;
4692                 if(n.parent.left !is n && n.parent.right !is n)
4693                     throw new Exception("Node at path " ~ path ~ " has inconsistent pointers");
4694                 Node next = n.next;
4695                 static if(allowDuplicates)
4696                 {
4697                     if(next !is _end && _less(next.value, n.value))
4698                         throw new Exception("ordering invalid at path " ~ path);
4699                 }
4700                 else
4701                 {
4702                     if(next !is _end && !_less(n.value, next.value))
4703                         throw new Exception("ordering invalid at path " ~ path);
4704                 }
4705                 if(n.color == n.color.Red)
4706                 {
4707                     if((n.left !is null && n.left.color == n.color.Red) ||
4708                             (n.right !is null && n.right.color == n.color.Red))
4709                         throw new Exception("Node at path " ~ path ~ " is red with a red child");
4710                 }
4711
4712                 int l = recurse(n.left, path ~ "L");
4713                 int r = recurse(n.right, path ~ "R");
4714                 if(l != r)
4715                 {
4716                     writeln("bad tree at:");
4717                     printTree(n);
4718                     throw new Exception("Node at path " ~ path ~ " has different number of black nodes on left and right paths");
4719                 }
4720                 return l + (n.color == n.color.Black ? 1 : 0);
4721             }
4722
4723             try
4724             {
4725                 recurse(_end.left, "");
4726             }
4727             catch(Exception e)
4728             {
4729                 printTree(_end.left, 0);
4730                 throw e;
4731             }
4732         }
4733     }
4734
4735     /**
4736      * Constructor.  Pass in an array of elements, or individual elements to
4737      * initialize the tree with.
4738      */
4739     this(U)(U[] elems...) if (isImplicitlyConvertible!(U, Elem))
4740     {
4741         _setup();
4742         stableInsert(elems);
4743     }
4744
4745     /**
4746      * Constructor.  Pass in a range of elements to initialize the tree with.
4747      */
4748     this(Stuff)(Stuff stuff) if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, Elem) && !is(Stuff == Elem[]))
4749     {
4750         _setup();
4751         stableInsert(stuff);
4752     }
4753
4754 }
4755
4756 unittest
4757 {
4758     RedBlackTree!uint rt1;
4759     RedBlackTree!int rt2;
4760     RedBlackTree!ushort rt3;
4761     RedBlackTree!short rt4;
4762     RedBlackTree!ubyte rt5;
4763     RedBlackTree!byte rt6;
4764 }
4765
4766 version(unittest) struct UnittestMe {
4767   int a;
4768 }
4769
4770 unittest
4771 {
4772     auto c = Array!UnittestMe();
4773 }
Note: See TracBrowser for help on using the browser.