Changeset 1740

Timestamp:

07/09/10 03:59:53 (14 years ago)

Author:

andrei

Message:

Defined TotalContainer? such that all member functions issue assert(0). That way it's easy to build new containers by copying and pasting TotalContainer?. Also added specialization of Array for bool that stores one bit per element.

Files:

• trunk/phobos/std/container.d (modified) (18 diffs)

trunk/phobos/std/container.d

@@ -10 +10 @@
-
-License: Distributed under the Boost Software License, Version 1.0.
-(See accompanying file LICENSE_1_0.txt or copy at $(WEB
-boost.org/LICENSE_1_0.txt)).
-
-Authors: $(WEB erdani.com, Andrei Alexandrescu)
-
- */
-module std.container;
-
-stdc.stdlib, core.stdc.string, std.algorithm, std.contracts
-functional, std.range, std.traits, std.typecon
-core.memory
+memory, core.stdc.stdlib, core.stdc.string, std.algorithm
+exception, std.functional, std.range, std.trait
+std.typecons, std.typetuple
-version(unittest) import std.stdio;
-
-/**
-$(D TotalContainer) is an unimplemented container that illustrates a
-host of primitives that a container may define. It is to some extent
-the bottom of the conceptual container hierarchy. A given container
-most often will choose to only implement a subset of these primitives,
-and define its own additional ones. Adhering to the standard primitive
-names below allows generic code to work independently of containers.
-
@@ -39 +39 @@
-A container may choose to define additional specific operations. The
-only requirement is that those operations bear different names than
-the ones below, lest user code gets confused.
-
-Complexity of operations should be interpreted as "at least as good
-as". If an operation is required to have $(BIGOH n) complexity, it
-could have anything lower than that, e.g. $(BIGOH log(n)). Unless
-specified otherwise, $(D n) inside a $(BIGOH) expression stands for
-the number of elements in the container.
- */
-Whatever
+T
-{
-/**
-If the container has a notion of key-value mapping, $(D KeyType)
-defines the type of the key of the container.
- */
-SomeType
+T
-
-/**
-If the container has a notion of multikey-value mapping, $(D
-KeyTypes[k]), where $(D k) is a zero-based unsigned number, defines
-the type of the $(D k)th key of the container.
-
-A container may define both $(D KeyType) and $(D KeyTypes), e.g. in
-the case it has the notion of primary/preferred key.
- */
-Key1, Key2
+T
-
-/**
-If the container has a notion of key-value mapping, $(D ValueType)
-defines the type of the value of the container. Typically, a map-style
-container mapping values of type $(D K) to values of type $(D V)
-
-
-
-
+
+
+
-
-/**
-Defines the container's primary range, which embodies one of the
-archetypal 
+
-
-Generally a container may define several types of ranges.
- */
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
-
-/**
-Property returning $(D true) if and only if the container has no
-elements.
-
-Complexity: $(BIGOH 1)
- */
-
+
+
+
+
-
-/**
-Returns a duplicate of the container. The elements themselves are not
-transitively duplicated.
-
-Complexity: $(BIGOH n).
- */
-
+
+
+
+
-
-/**
-Returns the number of elements in the container.
-
-Complexity: $(BIGOH log(n)).
-
-
+
+
+
+
+
-
-/**
-Returns the maximum number of elements the container can store without
-(a) allocating memory, (b) invalidating iterators upon insertion.
-
-Complexity: $(BIGOH log(n)).
- */
-
+
+
+
+
-
-/**
-Ensures sufficient capacity to accommodate $(D n) elements.
-
-Postcondition: $(D capacity >= n)
-
-Complexity: $(BIGOH log(e - capacity)) if $(D e > capacity), otherwise
-$(BIGOH 1).
- */
-
+
+
+
+
-
-/**
-Returns a range that iterates over all elements of the container, in a
-container-defined order. The container should choose the most
-convenient and fast method of iteration for $(D opSlice()).
-
-Complexity: $(BIGOH log(n))
- */
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
-
-/**
-Forward to $(D opSlice().front) and $(D opSlice().back), respectively.
-
-Complexity: $(BIGOH log(n))
- */
-
-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
-
-/**
-Indexing operators yield or modify the value at a specified index.
- */
-
-
-
-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
-
-/**
-$(D k in container) returns true if the given key is in the container.
- */
-
+
+
+
+
-
-/**
-Returns a range of all elements containing $(D k) (could be empty or a
-singleton range).
- */
-
+
+
+
+
-
-/**
-Returns a range of all elements with keys less than $(D k) (could be
-empty or a singleton range). Only defined by containers that store
-data sorted at all times.
- */
-
+
+
+
+
-
-/**
-Returns a range of all elements with keys larger than $(D k) (could be
-empty or a singleton range).  Only defined by containers that store
-data sorted at all times.
- */
-
+
+
+
+
-
-/**
-Returns a new container that's the concatenation of $(D this) and its
-argument. $(D opBinaryRight) is only defined if $(D Stuff) does not
-define $(D opBinary).
-
-Complexity: $(BIGOH n + m), where m is the number of elements in $(D
-stuff)
- */
-
-
-
-
+
+
+
+
+
+
+
+
+
+
-
-/**
-Forwards to $(D insertAfter(this[], stuff)).
- */
-
+
+
+
+
-
-/**
-Removes all contents from the container. The container decides how $(D
-capacity) is affected.
-
-Postcondition: $(D empty)
-
-Complexity: $(BIGOH n)
- */
-
+
+
+
+
-
-/**
-Sets the number of elements in the container to $(D newSize). If $(D
-newSize) is greater than $(D length), the added elements are added to
-unspecified positions in the container and initialized with $(D
-ElementType
+
-
-Complexity: $(BIGOH abs(n - newLength))
-
-
-
-
+
+
+
+
+
+
-
-/**
-Inserts $(D stuff) in an unspecified position in the
-container. Implementations should choose whichever insertion means is
-the most advantageous for the container, but document the exact
-$(D ElementType) or
-a range of objects convertible to $(D ElementType)
+the element type of
+the container, or a range of values convertible to it
-
-The $(D stable) version guarantees that ranges iterating over the
-container are never invalidated. Client code that counts on
-non-invalidating insertion should use $(D stableInsert). Such code would
-not compile against containers that don't support it.
-
-Returns: The number of elements added.
-
-
-
-
-
+
+
+
+
+
+
+
-    ///ditto
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
-
-/**
-Picks one value in an unspecified position in the container, removes
-it from the container, and returns it. Implementations should pick the
-value that's the most advantageous for the container, but document the
-exact behavior. The stable version behaves the same, but guarantees that
-ranges iterating over the container are never invalidated.
-
-Precondition: $(D !empty)
-
-Returns: The element removed.
-
-Complexity: $(BIGOH log(n)).
- */
-
-
-
+
+
+
+
+
+
+
+
+
-
-/**
-Inserts $(D value) to the front or back of the container. $(D stuff)
-$(D ElementType) or a range of objects
-
-but 
+the container's element type or a range
+
+
-invalidated.
-
-Returns: The number of elements inserted
-
-Complexity: $(BIGOH log(n)).
- */
-
-
-
-
-
-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
-
-/**
-Removes the value at the front or back of the container. The stable
-version behaves the same, but guarantees that ranges iterating over
-the container are never invalidated. The optional parameter $(D
-howMany) instructs removal of that many elements. If $(D howMany > n),
-all elements are removed and no exception is thrown.
-
-Precondition: $(D !empty)
-
-Complexity: $(BIGOH log(n)).
- */
-
-
-
-
-
-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
-
-/**
-Removes $(D howMany) values at the front or back of the
-container. Unlike the unparameterized versions above, these functions
-do not throw if they could not remove $(D howMany) elements. Instead,
-if $(D howMany > n), all elements are removed. The returned value is
-the effective number of elements removed. The stable version behaves
-the same, but guarantees that ranges iterating over the container are
-never invalidated.
-
-Returns: The number of elements removed
-
-Complexity: $(BIGOH howMany * log(n)).
- */
-
-
-
-
-
-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
-
-/**
-Removes all values corresponding to key $(D k).
-
-Complexity: $(BIGOH m * log(n)), where $(D m) is the number of
-elements with the same key.
-
-Returns: The number of elements removed.
- */
-
+
+
+
+
-
-/**
-Inserts $(D stuff) before, after, or instead range $(D r), which must
-be a valid range previously extracted from this container. $(D stuff)
-$(D ElementType) or a range of objects
-
-but 
+the container's element type or a range
+
+
-invalidated.
-
-Returns: The number of values inserted.
-
-Complexity: $(BIGOH n + m), where $(D m) is the length of $(D stuff)
- */
-
-
-
-
-
-
-
-
-
-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
-
-/**
-Removes all elements belonging to $(D r), which must be a range
-obtained originally from this container. The stable version behaves the
-same, but guarantees that ranges iterating over the container are
-never invalidated.
-
-Returns: A range spanning the remaining elements in the container that
-initially were right after $(D r).
-
-Complexity: $(BIGOH m * log(n)), where $(D m) is the number of
-elements in $(D r)
- */
-
-
-
+
+
+
+
+
+
+
+
+
-
-/**
-Same as $(D remove) above, but has complexity relaxed to linear.
-
-Returns: A range spanning the remaining elements in the container that
-initially were right after $(D r).
-
-Complexity: $(BIGOH n)
- */
-
-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
-}
-
-/**
-Returns an initialized container. This function is mainly for
-eliminating construction differences between $(D class) containers and
-$(D struct) containers.
- */
-Container make(Container, T...)(T arguments) if (is(Container == struct))
-{
-    static if (T.length == 0)
@@ -601 +849 @@
-
-Complexity: $(BIGOH 1)
- */
-    void clear()
-    {
-        _root = null;
-    }
-
-/**
-Inserts $(D stuff) to the front of the container. $(D stuff) can be a
-
-
-
-
+
+
+
-
-Returns: The number of elements inserted
-
-Complexity: $(BIGOH log(n))
- */
-    size_t insertFront(Stuff)(Stuff stuff)
-    if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T))
-    {
-        size_t result;
-        Node * n, newRoot;
@@ -720 +967 @@
-    alias removeFront stableRemoveFront;
-
-/**
-Inserts $(D stuff) after range $(D r), which must be a range
-previously extracted from this container. Given that all ranges for a
-list end at the end of the list, this function essentially appends to
-the list and uses $(D r) as a potentially fast way to reach the last
-node in the list. (Ideally $(D r) is positioned near or at the last
-element of the list.)
-
-ElementType) or a range
-
-
-never 
+T) or a range of objects
+
+
+
-
-Returns: The number of values inserted.
-
-Complexity: $(BIGOH k + m), where $(D k) is the number of elements in
-$(D r) and $(D m) is the length of $(D stuff).
- */
-
-    size_t insertAfter(Stuff)(Range r, Stuff stuff)
-    {
-        if (!_root)
@@ -970 +1217 @@
-
-    auto lst3 = lst ~ [ 7 ];
-    assert(walkLength(lst3[]) == 5);
-}
-
-unittest
-{
-    auto s = make!(SList!int)(1, 2, 3);
-}
-
-
-
-
-
-
-
-
-
+
+
+
+
+
+
+
+
+
+
-    {
-        size_t _capacity;
-        T[] _payload;
-
-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
-
-    this(U)(U[] values...) if (isImplicitlyConvertible!(U, T))
-    {
-
+
+
+
+
+
-        foreach (i, e; values)
-        {
-
-
+
+
+
+
-    }
-
-/**
-Comparison for equality.
- */
-    bool opEquals(ref const Array rhs) const
-    {
-        if (empty) return rhs.empty;
-        if (rhs.empty) return false;
-        return _data._payload == rhs._data._payload;
-    }
-
-/**
-Defines the container's primary range, which is a random-access range.
-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
-
-/**
-Property returning $(D true) if and only if the container has no
-elements.
-
-Complexity: $(BIGOH 1)
- */
-    @property bool empty() const
-    {
-
+.RefCounted.isInitialized
-    }
-
-/**
-Duplicates the container. The elements themselves are not transitively
-duplicated.
-
-Complexity: $(BIGOH n).
- */
-    @property Array dup()
-    {
-
-
-
-
+
+
-    }
-
-/**
-Returns the number of elements in the container.
-
-Complexity: $(BIGOH 1).
- */
-    @property size_t length() const
-    {
-
+.RefCounted.isInitialized
-    }
-
-/**
-Returns the maximum number of elements the container can store without
-   (a) allocating memory, (b) invalidating iterators upon insertion.
-
-Complexity: $(BIGOH 1)
- */
-    @property size_t capacity()
-    {
-
+.RefCounted.isInitialized
-    }
-
-/**
-Ensures sufficient capacity to accommodate $(D e) elements.
-
-Postcondition: $(D capacity >= e)
-
-Complexity: $(BIGOH 1)
-
-
-
-
-
-
-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
-        }
-        else
-        {
-
-
-
-
-
-
+
-        }
-    }
-
-/**
-Returns a range that iterates over elements of the container, in
-forward order.
-
-Complexity: $(BIGOH 1)
- */
-    Range opSlice()
-    {
-
+
+
+
+
-    }
-
-/**
-Returns a range that iterates over elements of the container from
-index $(D a) up to (excluding) index $(D b).
-
-Precondition: $(D a <= b && b <= length)
-
-Complexity: $(BIGOH 1)
- */
-    Range opSlice(size_t a, size_t b)
-    {
-        enforce(a <= b && b <= length);
-
+
+
+
+
-    }
-
-/**
-@@@BUG@@@ This doesn't work yet
- */
-    size_t opDollar() const
-    {
-        return length;
-    }
-
@@ -1157 +1640 @@
-
-/**
-Indexing operators yield or modify the value at a specified index.
-
-Precondition: $(D i < length)
-
-Complexity: $(BIGOH 1)
- */
-    T opIndex(size_t i)
-    {
-
+.RefCounted.isInitialized
-        return _data._payload[i];
-    }
-
-    /// ditto
-    void opIndexAssign(T value, size_t i)
-    {
-
+.RefCounted.isInitialized
-        _data._payload[i] = value;
-    }
-
-/// ditto
-    void opIndexOpAssign(string op)(T value, size_t i)
-    {
-        mixin("_data._payload[i] "~op~"= value;");
-    }
-
-/**
-Returns a new container that's the concatenation of $(D this) and its
-argument. $(D opBinaryRight) is only defined if $(D Stuff) does not
-define $(D opBinary).
-
-Complexity: $(BIGOH n + m), where m is the number of elements in $(D
-stuff)
- */
-    Array opBinary(string op, Stuff)(Stuff stuff) if (op == "~")
-    {
-        // TODO: optimize
-
-
+
+
+
+
+
+
-        return result;
-    }
-
-/**
-Forwards to $(D insertBack(stuff)).
- */
-    void opOpAssign(string op, Stuff)(Stuff stuff) if (op == "~")
-    {
-        static if (is(typeof(stuff[])))
-        {
@@ -1215 +1702 @@
-/**
-Removes all contents from the container. The container decides how $(D
-capacity) is affected.
-
-Postcondition: $(D empty)
-
-Complexity: $(BIGOH n)
- */
-    void clear()
-    {
-_data = null
+.clear(_data)
-    }
-
-/**
-Sets the number of elements in the container to $(D newSize). If $(D
-newSize) is greater than $(D length), the added elements are added to
-unspecified positions in the container and initialized with $(D
-ElementType
+T
-
-Complexity: $(BIGOH abs(n - newLength))
-
-Postcondition: $(D length == newLength)
- */
-    @property void length(size_t newLength)
-    {
-
-
-
-
-
-
-
-
-
-
-
-
+
+
-    }
-
-/**
-Picks one value in an unspecified position in the container, removes
-it from the container, and returns it. Implementations should pick the
-value that's the most advantageous for the container, but document the
-exact behavior. The stable version behaves the same, but guarantees
-that ranges iterating over the container are never invalidated.
-
-Precondition: $(D !empty)
@@ -1268 +1745 @@
-    {
-        auto result = back;
-        removeBack();
-        return result;
-    }
-    /// ditto
-    alias removeAny stableRemoveAny;
-
-/**
-Inserts $(D value) to the front or back of the container. $(D stuff)
-
-
-
-
+
+
+
-
-Returns: The number of elements inserted
-
-Complexity: $(BIGOH m * log(n)), where $(D m) is the number of
-elements in $(D stuff)
- */
-    size_t insertBack(Stuff)(Stuff stuff)
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
+
+
+
+
+
-    }
-/// ditto
-    alias insertBack insert;
-
-/**
-Removes the value at the back of the container. The stable version
-behaves the same, but guarantees that ranges iterating over the
-container are never invalidated.
-
-Precondition: $(D !empty)
-
-Complexity: $(BIGOH log(n)).
- */
-    void removeBack()
-    {
-        enforce(!empty);
+        static if (is(T == struct))
+        {
+            // Destroy this guy
+            clear(_data._payload[$ - 1]);
+        }
-        _data._payload = _data._payload[0 .. $ - 1];
-    }
-/// ditto
-    alias removeBack stableRemoveBack;
-
-/**
-Removes $(D howMany) values at the front or back of the
-container. Unlike the unparameterized versions above, these functions
-do not throw if they could not remove $(D howMany) elements. Instead,
-if $(D howMany > n), all elements are removed. The returned value is
@@ -1338 +1802 @@
-the same, but guarantees that ranges iterating over the container are
-never invalidated.
-
-Returns: The number of elements removed
-
-Complexity: $(BIGOH howMany).
- */
-    size_t removeBack(size_t howMany)
-    {
-        if (howMany > length) howMany = length;
+        static if (is(T == struct))
+        {
+            // Destroy this guy
+            foreach (ref e; _data._payload[$ - howMany .. $])
+            {
+                clear(e);
+            }
+        }
-        _data._payload = _data._payload[0 .. $ - howMany];
-        return howMany;
-    }
-    /// ditto
-    alias removeBack stableRemoveBack;
-
-/**
-Inserts $(D stuff) before, after, or instead range $(D r), which must
-be a valid range previously extracted from this container. $(D stuff)
-
-
-
-
+
+
+
-
-Returns: The number of values inserted.
-
-Complexity: $(BIGOH n + m), where $(D m) is the length of $(D stuff)
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
+
-    size_t insertBefore(Stuff)(Range r, Stuff stuff)
-    if (isImplicitlyConvertible!(Stuff, T))
-    {
-
+outer._
-        reserve(length + 1);
-
+.RefCounted.isInitialized
-        // Move elements over by one slot
-        memmove(_data._payload.ptr + r._a + 1,
-                _data._payload.ptr + r._a,
-                T.sizeof * (length - r._a));
-        emplace!T((cast(void*) (_data._payload.ptr + r._a))[0 .. T.sizeof],
-                stuff);
-        _data._payload = _data._payload.ptr[0 .. _data._payload.length + 1];
-        return 1;
-    }
-
-/// ditto
-    size_t insertBefore(Stuff)(Range r, Stuff stuff)
-    if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T))
-    {
-data == _data && r._a <
+outer._data == _data && r._a <=
-        static if (isForwardRange!Stuff)
-        {
-            // Can find the length in advance
-            auto extra = walkLength(stuff);
-            if (!extra) return 0;
-            reserve(length + extra);
-
+.RefCounted.isInitialized
-            // Move elements over by extra slots
-            memmove(_data._payload.ptr + r._a + extra,
-                    _data._payload.ptr + r._a,
-                    T.sizeof * (length - r._a));
-            foreach (p; _data._payload.ptr + r._a ..
-                    _data._payload.ptr + r._a + extra)
-            {
-                emplace!T((cast(void*) p)[0 .. T.sizeof], stuff.front);
-                stuff.popFront();
-            }
@@ -2243 +1949 @@
-never invalidated.
-
-Returns: A range spanning the remaining elements in the container that
-initially were right after $(D r).
-
-Complexity: $(BIGOH n - m), where $(D m) is the number of elements in
-$(D r)
- */
-    Range linearRemove(Range r)
-    {
-
+.RefCounted.isInitialized
-        enforce(r._a <= r._b && r._b <= length);
-        immutable offset1 = r._a;
-        immutable offset2 = r._b;
-        immutable tailLength = length - offset2;
-        // Use copy here, not a[] = b[] because the ranges may overlap
-        copy(this[offset2 .. length], this[offset1 .. offset1 + tailLength]);
-        length = offset1 + tailLength;
-        return this[length - tailLength .. length];
-    }
-
-    /// ditto
-    alias remove stableLinearRemove;
-
-}
-
+// unittest
+// {
+//     Array!int a;
+//     assert(a.empty);
+// }
+
-unittest
-{
-
-
-
-
-
-
-
+
+
-    auto b = a.dup;
-    assert(b == Array!int(1, 2, 3));
-    b.front = 42;
-    assert(b == Array!int(42, 2, 3));
-    assert(a == Array!int(1, 2, 3));
-}
-
-unittest
-{
-    auto a = Array!int(1, 2, 3);
@@ -2307 +2014 @@
-{
-    auto a = Array!int(1, 2, 3);
-    a[1] *= 42;
-    assert(a[1] == 84);
-}
-
-unittest
-{
-    auto a = Array!int(1, 2, 3);
-    auto b = Array!int(11, 12, 13);
-
-
+
+
+
+
-}
-
-unittest
-{
-    auto a = Array!int(1, 2, 3);
-    auto b = Array!int(11, 12, 13);
-    a ~= b;
-    assert(a == Array!int(1, 2, 3, 11, 12, 13));
-}
-
@@ -2342 +2051 @@
-    r = a[2 .. 2];
-    assert(a.insertBefore(r, [8, 9]) == 2);
-    assert(a == Array!int(1, 2, 8, 9, 42, 3, 4, 5));
-}
-
-unittest
-{
-    auto a = Array!int(0, 1, 2, 3, 4, 5, 6, 7, 8);
-    a.linearRemove(a[4 .. 6]);
-    auto b = Array!int(0, 1, 2, 3, 6, 7, 8);
+    //writeln(a.length);
+    //foreach (e; a) writeln(e);
-    assert(a == Array!int(0, 1, 2, 3, 6, 7, 8));
-}
-
-// BinaryHeap
-/**
-Implements a $(WEB en.wikipedia.org/wiki/Binary_heap, binary heap)
-container on top of a given random-access range type (usually $(D
-T[])) or a random-access container type (usually $(D Array!T)). The
-documentation of $(D BinaryHeap) will refer to the underlying range or
-container as the $(I store) of the heap.
@@ -2400 +2111 @@
-//private:
-
-    // The payload includes the support store and the effective length
-    private RefCounted!(Tuple!(Store, "_store", size_t, "_length"),
-                       RefCountedAutoInitialize.no) _payload;
-    // Comparison predicate
-    private alias binaryFun!(less) comp;
-    // Convenience accessors
-    private @property ref Store _store()
-    {
-refCountedI
+RefCounted.i
-        return _payload._store;
-    }
-    private @property ref size_t _length()
-    {
-refCountedI
+RefCounted.i
-        return _payload._length;
-    }
-
-    // Asserts that the heap property is respected.
-    private void assertValid()
-    {
-        debug
-        {
-refCountedI
+RefCounted.i
-            if (_length < 2) return;
-            for (size_t n = _length - 1; n >= 1; --n)
-            {
-                auto parentIdx = (n - 1) / 2;
-                assert(!comp(_store[parentIdx], _store[n]), text(n));
-            }
-        }
-    }
-
-    // Assuming the element at index i perturbs the heap property in
@@ -2484 +2195 @@
-        {
-            auto t1 = _store[].moveAt(i);
-            auto t2 = _store[].moveAt(j);
-            _store[i] = move(t2);
-            _store[j] = move(t1);
-        }
-    }
-
-public:
-
-
-
-
-
-
-
-
-
+    
+       
+
+
+
+
+       $(BIGOH min(r.length, 
+    
-    this(Store s, size_t initialSize = size_t.max)
-    {
-        acquire(s, initialSize);
-    }
-
-/**
-Takes ownership of a store. After this, manipulating $(D s) may make
-the heap work incorrectly.
- */
-    void acquire(Store s, size_t initialSize = size_t.max)
-    {
-refCountedE
+RefCounted.e
-        _store() = move(s);
-        _length() = min(_store.length, initialSize);
-        if (_length < 2) return;
-        for (auto i = (_length - 2) / 2; ; )
-        {
-            this.percolateDown(_store, i, _length);
-            if (i-- == 0) break;
-        }
-        assertValid;
-    }
-
-/**
-Takes ownership of a store assuming it already was organized as a
-heap.
- */
-    void assume(Store s, size_t initialSize = size_t.max)
-    {
-refCountedE
+RefCounted.e
-        _store() = s;
-        _length() = min(_store.length, initialSize);
-        assertValid;
-    }
-
-/**
-Clears the heap. Returns the portion of the store from $(D 0) up to
-$(D length), which satisfies the $(LUCKY heap property).
- */
-    auto release()
-    {
-refCountedI
+RefCounted.i
-        {
-            return typeof(_store[0 .. _length]).init;
-        }
-        assertValid();
-        auto result = _store[0 .. _length];
-        _payload = _payload.init;
-        return result;
-    }
-
-/**
@@ -2558 +2269 @@
-        return !length;
-    }
-
-/**
-Returns a duplicate of the heap. The underlying store must also
-support a $(D dup) method.
- */
-    @property BinaryHeap dup()
-    {
-        BinaryHeap result;
-refCountedI
+RefCounted.i
-        result.assume(_store.dup, length);
-        return result;
-    }
-
-/**
-Returns the _length of the heap.
- */
-    @property size_t length()
-    {
-refCountedI
+RefCounted.i
-    }
-
-/**
-Returns the _capacity of the heap, which is the length of the
-underlying store (if the store is a range) or the _capacity of the
-underlying store (if the store is a container).
- */
-    @property size_t capacity()
-    {
-refCountedI
+RefCounted.i
-        static if (is(typeof(_store.capacity) : size_t))
-        {
-            return _store.capacity;
-        }
-        else
-        {
-            return _store.length;
-        }
-    }
-
@@ -2615 +2326 @@
-    }
-
-/**
-Inserts $(D value) into the store. If the underlying store is a range
-and $(D length == capacity), throws an exception.
- */
-    size_t insert(ElementType!Store value)
-    {
-        static if (is(_store.insertBack(value)))
-        {
-refCountedE
+RefCounted.e
-            if (length == _store.length)
-            {
-                // reallocate
-                _store.insertBack(value);
-            }
-            else
-            {
-                // no reallocation
-                _store[_length] = value;
-            }
@@ -2700 +2411 @@
-/**
-If the heap has room to grow, inserts $(D value) into the store and
-returns $(D true). Otherwise, if $(D less(value, front)), calls $(D
-replaceFront(value)) and returns again $(D true). Otherwise, leaves
-the heap unaffected and returns $(D false). This method is useful in
-scenarios where the smallest $(D k) elements of a set of candidates
-must be collected.
- */
-    bool conditionalInsert(ElementType!Store value)
-    {
-refCountedE
+RefCounted.e
-        if (_length < _store.length)
-        {
-            insert(value);
-            return true;
-        }
-        // must replace the top
-        assert(!_store.empty);
-        if (!comp(value, _store.front)) return false; // value >= largest
-        _store.front = value;
-        percolateDown(_store, 0, _length);
@@ -2753 +2464 @@
-        int[] b = new int[a.length];
-        BinaryHeap!(int[]) h = BinaryHeap!(int[])(b, 0);
-        foreach (e; a)
-        {
-            h.insert(e);
-        }
-        assert(b == [ 16, 14, 10, 8, 7, 3, 9, 1, 4, 2 ], text(b));
-    }
-}
-
+////////////////////////////////////////////////////////////////////////////////
+// Array!bool
+////////////////////////////////////////////////////////////////////////////////
+
+/**
+_Array specialized for $(D bool). Packs together values efficiently by
+allocating one bit per element.
+ */
+struct Array(T) if (is(T == bool))
+{
+    static immutable uint bitsPerWord = size_t.sizeof * 8;
+    private alias Tuple!(Array!(size_t).Payload, "_backend", ulong, "_length")
+    Data;
+    private RefCounted!(Data, RefCountedAutoInitialize.no) _store;
+
+    private ref size_t[] data()
+    {
+        assert(_store.RefCounted.isInitialized);
+        return _store._backend._payload;
+    }
+
+    private ref size_t dataCapacity()
+    {
+        return _store._backend._capacity;
+    }
+
+    /**
+       Defines the container's primary range.
+     */
+    struct Range
+    {
+        private Array!bool _outer;
+        private ulong _a, _b;
+        /// Range primitives
+        @property Range save()
+        {
+            version (bug4437)
+            {
+                return this;
+            }
+            else
+            {
+                auto copy = this;
+                return copy;
+            }
+        }
+        /// Ditto
+        @property bool empty()
+        {
+            return _a >= _b || _outer.length < _b;
+        }
+        /// Ditto
+        @property T front()
+        {
+            enforce(!empty);
+            return _outer[_a];
+        }
+        /// Ditto
+        @property void front(bool value)
+        {
+            enforce(!empty);
+            _outer[_a] = value;
+        }
+        /// Ditto
+        T moveFront()
+        {
+            enforce(!empty);
+            return _outer.moveAt(_a);
+        }
+        /// Ditto
+        void popFront()
+        {
+            enforce(!empty);
+            ++_a;
+        }
+        /// Ditto
+        @property T back()
+        {
+            enforce(!empty);
+            return _outer[_b - 1];
+        }
+        /// Ditto
+        T moveBack()
+        {
+            enforce(!empty);
+            return _outer.moveAt(_b - 1);
+        }
+        /// Ditto
+        void popBack()
+        {
+            enforce(!empty);
+            --_b;
+        }
+        /// Ditto
+        T opIndex(size_t i)
+        {
+            return _outer[_a + i];
+        }
+        /// Ditto
+        void opIndexAssign(T value, uint i)
+        {
+            _outer[_a + i] = value;
+        }
+        /// Ditto
+        T moveAt(size_t i)
+        {
+            return _outer.moveAt(_a + i);
+        }
+        /// Ditto
+        @property ulong length() const
+        {
+            assert(_a <= _b);
+            return _b - _a;
+        }
+    }
+
+    /**
+       Property returning $(D true) if and only if the container has
+       no elements.
+
+       Complexity: $(BIGOH 1)
+     */
+    @property bool empty()
+    {
+        return !length;
+    }
+
+    unittest
+    {
+        Array!bool a;
+        //a._store._refCountedDebug = true;
+        assert(a.empty);
+        a.insertBack(false);
+        assert(!a.empty);
+    }
+
+    /**
+       Returns a duplicate of the container. The elements themselves
+       are not transitively duplicated.
+
+       Complexity: $(BIGOH n).
+     */
+    @property Array!bool dup()
+    {
+        Array!bool result;
+        result.insertBack(this[]);
+        return result;
+    }
+
+    unittest
+    {
+        Array!bool a;
+        assert(a.empty);
+        auto b = a.dup;
+        assert(b.empty);
+        a.insertBack(true);
+        assert(b.empty);
+    }
+
+    /**
+       Returns the number of elements in the container.
+
+       Complexity: $(BIGOH log(n)).
+    */
+    @property ulong length()
+    {
+        return _store.RefCounted.isInitialized ? _store._length : 0;
+    }
+
+    unittest
+    {
+        Array!bool a;
+        assert(a.length == 0);
+        a.insert(true);
+        assert(a.length == 1, text(a.length));
+    }
+
+    /**
+       Returns the maximum number of elements the container can store
+       without (a) allocating memory, (b) invalidating iterators upon
+       insertion.
+
+       Complexity: $(BIGOH log(n)).
+     */
+    @property ulong capacity()
+    {
+        return _store.RefCounted.isInitialized
+            ? cast(ulong) bitsPerWord * _store._backend.capacity
+            : 0;
+    }
+
+    unittest
+    {
+        Array!bool a;
+        assert(a.capacity == 0);
+        foreach (i; 0 .. 100)
+        {
+            a.insert(true);
+            assert(a.capacity >= a.length, text(a.capacity));
+        }
+    }
+
+    /**
+       Ensures sufficient capacity to accommodate $(D n) elements.
+
+       Postcondition: $(D capacity >= n)
+
+       Complexity: $(BIGOH log(e - capacity)) if $(D e > capacity),
+       otherwise $(BIGOH 1).
+     */
+    void reserve(ulong e)
+    {
+        _store.RefCounted.ensureInitialized();
+        _store._backend.reserve(to!size_t((e + bitsPerWord - 1) / bitsPerWord));
+    }
+
+    unittest
+    {
+        Array!bool a;
+        assert(a.capacity == 0);
+        a.reserve(15657);
+        assert(a.capacity >= 15657);
+    }
+
+    /**
+       Returns a range that iterates over all elements of the
+       container, in a container-defined order. The container should
+       choose the most convenient and fast method of iteration for $(D
+       opSlice()).
+
+       Complexity: $(BIGOH log(n))
+     */
+    Range opSlice()
+    {
+        return Range(this, 0, length);
+    }
+
+    unittest
+    {
+        Array!bool a;
+        a.insertBack([true, false, true, true]);
+        assert(a[].length == 4);
+    }
+
+    /**
+       Returns a range that iterates the container between two
+       specified positions.
+
+       Complexity: $(BIGOH log(n))
+     */
+    Range opSlice(ulong a, ulong b)
+    {
+        enforce(a <= b && b <= length);
+        return Range(this, a, b);
+    }
+
+    unittest
+    {
+        Array!bool a;
+        a.insertBack([true, false, true, true]);
+        assert(a[0 .. 2].length == 2);
+    }
+
+    /**
+       Equivalent to $(D opSlice().front) and $(D opSlice().back),
+       respectively.
+
+       Complexity: $(BIGOH log(n))
+     */
+    @property bool front()
+    {
+        enforce(!empty);
+        return data.ptr[0] & 1;
+    }
+
+    /// Ditto
+    @property void front(bool value)
+    {
+        enforce(!empty);
+        if (value) data.ptr[0] |= 1;
+        else data.ptr[0] &= ~cast(size_t) 1;
+    }
+
+    unittest
+    {
+        Array!bool a;
+        a.insertBack([true, false, true, true]);
+        assert(a.front);
+        a.front = false;
+        assert(!a.front);
+    }
+
+    /// Ditto
+    @property bool back()
+    {
+        enforce(!empty);
+        return data.back & (1u << ((_store._length - 1) % bitsPerWord));
+    }
+
+    /// Ditto
+    @property void back(bool value)
+    {
+        enforce(!empty);
+        if (value)
+        {
+            data.back |= (1u << ((_store._length - 1) % bitsPerWord));
+        }
+        else
+        {
+            data.back &=
+                ~(cast(size_t)1 << ((_store._length - 1) % bitsPerWord));
+        }
+    }
+
+    unittest
+    {
+        Array!bool a;
+        a.insertBack([true, false, true, true]);
+        assert(a.back);
+        a.back = false;
+        assert(!a.back);
+    }
+
+    /**
+       Indexing operators yield or modify the value at a specified index.
+     */
+    bool opIndex(ulong i)
+    {
+        auto div = cast(size_t) (i / bitsPerWord);
+        auto rem = i % bitsPerWord;
+        enforce(div < data.length);
+        return data.ptr[div] & (1u << rem);
+    }
+    /// ditto
+    void opIndexAssign(bool value, ulong i)
+    {
+        auto div = cast(size_t) (i / bitsPerWord);
+        auto rem = i % bitsPerWord;
+        enforce(div < data.length);
+        if (value) data.ptr[div] |= (1u << rem);
+        else data.ptr[div] &= ~(cast(size_t)1 << rem);
+    }
+    /// ditto
+    void opIndexOpAssign(string op)(bool value, ulong i)
+    {
+        auto div = cast(size_t) (i / bitsPerWord);
+        auto rem = i % bitsPerWord;
+        enforce(div < data.length);
+        auto oldValue = cast(bool) (data.ptr[div] & (1u << rem));
+        // Do the deed
+        auto newValue = mixin("oldValue "~op~" value");
+        // Write back the value
+        if (newValue != oldValue)
+        {
+            if (newValue) data.ptr[div] |= (1u << rem);
+            else data.ptr[div] &= ~(cast(size_t)1 << rem);
+        }
+    }
+    /// Ditto
+    T moveAt(ulong i)
+    {
+        return this[i];
+    }
+
+    unittest
+    {
+        Array!bool a;
+        a.insertBack([true, false, true, true]);
+        assert(a[0] && !a[1]);
+        a[0] &= a[1];
+        assert(!a[0]);
+    }
+
+    /**
+       Returns a new container that's the concatenation of $(D this)
+       and its argument.
+
+       Complexity: $(BIGOH n + m), where m is the number of elements
+       in $(D stuff)
+     */
+    Array!bool opBinary(string op, Stuff)(Stuff rhs) if (op == "~")
+    {
+        auto result = this;
+        return result ~= rhs;
+    }
+
+    unittest
+    {
+        Array!bool a;
+        a.insertBack([true, false, true, true]);
+        Array!bool b;
+        b.insertBack([true, true, false, true]);
+        assert(equal((a ~ b)[],
+                        [true, false, true, true, true, true, false, true]));
+    }
+
+    // /// ditto
+    // TotalContainer opBinaryRight(Stuff, string op)(Stuff lhs) if (op == "~")
+    // {
+    //     assert(0);
+    // }
+
+    /**
+       Forwards to $(D insertAfter(this[], stuff)).
+     */
+    // @@@BUG@@@
+    //ref Array!bool opOpAssign(string op, Stuff)(Stuff stuff) if (op == "~")
+    Array!bool opOpAssign(string op, Stuff)(Stuff stuff) if (op == "~")
+    {
+        static if (is(typeof(stuff[]))) insertBack(stuff[]);
+        else insertBack(stuff);
+        return this;
+    }
+
+    unittest
+    {
+        Array!bool a;
+        a.insertBack([true, false, true, true]);
+        Array!bool b;
+        a.insertBack([false, true, false, true, true]);
+        a ~= b;
+        assert(equal(
+                    a[],
+                    [true, false, true, true, false, true, false, true, true]));
+    }
+
+    /**
+       Removes all contents from the container. The container decides
+       how $(D capacity) is affected.
+
+       Postcondition: $(D empty)
+
+       Complexity: $(BIGOH n)
+     */
+    void clear()
+    {
+        this = Array!bool();
+    }
+
+    unittest
+    {
+        Array!bool a;
+        a.insertBack([true, false, true, true]);
+        a.clear();
+        assert(a.capacity == 0);
+    }
+
+    /**
+       Sets the number of elements in the container to $(D
+       newSize). If $(D newSize) is greater than $(D length), the
+       added elements are added to the container and initialized with
+       $(D ElementType.init).
+
+       Complexity: $(BIGOH abs(n - newLength))
+
+       Postcondition: $(D _length == newLength)
+     */
+    @property void length(ulong newLength)
+    {
+        _store.RefCounted.ensureInitialized();
+        auto newDataLength =
+            to!size_t((newLength + bitsPerWord - 1) / bitsPerWord);
+        _store._backend.length = newDataLength;
+        _store._length = newLength;
+    }
+
+    unittest
+    {
+        Array!bool a;
+        a.length = 1057;
+        assert(a.length == 1057);
+        foreach (e; a)
+        {
+            assert(!e);
+        }
+    }
+
+    /**
+       Inserts $(D stuff) in the container. $(D stuff) can be a value
+       convertible to $(D ElementType) or a range of objects
+       convertible to $(D ElementType).
+
+       The $(D stable) version guarantees that ranges iterating over
+       the container are never invalidated. Client code that counts on
+       non-invalidating insertion should use $(D stableInsert).
+
+       Returns: The number of elements added.
+
+       Complexity: $(BIGOH m * log(n)), where $(D m) is the number of
+       elements in $(D stuff)
+     */
+    alias insertBack insert;
+    ///ditto
+    alias insertBack stableInsert;
+
+    /**
+       Same as $(D insert(stuff)) and $(D stableInsert(stuff))
+       respectively, but relax the complexity constraint to linear.
+     */
+    alias insertBack linearInsert;
+    ///ditto
+    alias insertBack stableLinearInsert;
+
+    /**
+       Picks one value in the container, removes it from the
+       container, and returns it. The stable version behaves the same,
+       but guarantees that ranges iterating over the container are
+       never invalidated.
+
+       Precondition: $(D !empty)
+
+       Returns: The element removed.
+
+       Complexity: $(BIGOH log(n))
+     */
+    T removeAny()
+    {
+        auto result = back();
+        removeBack();
+        return result;
+    }
+    /// ditto
+    alias removeAny stableRemoveAny;
+
+    unittest
+    {
+        Array!bool a;
+        a.length = 1057;
+        assert(!a.removeAny());
+        assert(a.length == 1056);
+        foreach (e; a)
+        {
+            assert(!e);
+        }
+    }
+
+    /**
+       Inserts $(D value) to the back of the container. $(D stuff) can
+       be a value convertible to $(D ElementType) or a range of
+       objects convertible to $(D ElementType). The stable version
+       behaves the same, but guarantees that ranges iterating over the
+       container are never invalidated.
+
+       Returns: The number of elements inserted
+
+       Complexity: $(BIGOH log(n))
+     */
+    ulong insertBack(Stuff)(Stuff stuff) if (is(Stuff : bool))
+    {
+        _store.RefCounted.ensureInitialized();
+        auto rem = _store._length % bitsPerWord;
+        if (rem)
+        {
+            // Fits within the current array
+            if (stuff)
+            {
+                data[$ - 1] |= (1u << rem);
+            }
+            else
+            {
+                data[$ - 1] &= ~(1u << rem);
+            }
+        }
+        else
+        {
+            // Need to add more data
+            _store._backend.insertBack(stuff);
+        }
+        ++_store._length;
+        return 1;
+    }
+    /// Ditto
+    ulong insertBack(Stuff)(Stuff stuff)
+    if (isInputRange!Stuff && is(ElementType!Stuff : bool))
+    {
+        static if (!hasLength!Stuff) ulong result;
+        for (; !stuff.empty; stuff.popFront())
+        {
+            insertBack(stuff.front);
+            static if (!hasLength!Stuff) ++result;
+        }
+        static if (!hasLength!Stuff) return result;
+        else return stuff.length;
+    }
+    /// ditto
+    alias insertBack stableInsertBack;
+
+    /**
+       Removes the value at the front or back of the container. The
+       stable version behaves the same, but guarantees that ranges
+       iterating over the container are never invalidated. The
+       optional parameter $(D howMany) instructs removal of that many
+       elements. If $(D howMany > n), all elements are removed and no
+       exception is thrown.
+
+       Precondition: $(D !empty)
+
+       Complexity: $(BIGOH log(n)).
+     */
+    void removeBack()
+    {
+        enforce(_store._length);
+        if (_store._length % bitsPerWord)
+        {
+            // Cool, just decrease the length
+            --_store._length;
+        }
+        else
+        {
+            // Reduce the allocated space
+            --_store._length;
+            _store._backend.length = _store._backend.length - 1;
+        }
+    }
+    /// ditto
+    alias removeBack stableRemoveBack;
+
+    /**
+       Removes $(D howMany) values at the front or back of the
+       container. Unlike the unparameterized versions above, these
+       functions do not throw if they could not remove $(D howMany)
+       elements. Instead, if $(D howMany > n), all elements are
+       removed. The returned value is the effective number of elements
+       removed. The stable version behaves the same, but guarantees
+       that ranges iterating over the container are never invalidated.
+
+       Returns: The number of elements removed
+
+       Complexity: $(BIGOH howMany * log(n)).
+     */
+    /// ditto
+    ulong removeBack(ulong howMany)
+    {
+        if (howMany >= length)
+        {
+            howMany = length;
+            clear();
+        }
+        else
+        {
+            length = length - howMany;
+        }
+        return howMany;
+    }
+
+    unittest
+    {
+        Array!bool a;
+        a.length = 1057;
+        assert(a.removeBack(1000) == 1000);
+        assert(a.length == 57);
+        foreach (e; a)
+        {
+            assert(!e);
+        }
+    }
+
+    /**
+       Inserts $(D stuff) before, after, or instead range $(D r),
+       which must be a valid range previously extracted from this
+       container. $(D stuff) can be a value convertible to $(D
+       ElementType) or a range of objects convertible to $(D
+       ElementType). The stable version behaves the same, but
+       guarantees that ranges iterating over the container are never
+       invalidated.
+
+       Returns: The number of values inserted.
+
+       Complexity: $(BIGOH n + m), where $(D m) is the length of $(D stuff)
+     */
+    ulong insertBefore(Stuff)(Range r, Stuff stuff)
+    {
+        // TODO: make this faster, it moves one bit at a time
+        immutable inserted = stableInsertBack(stuff);
+        immutable tailLength = length - inserted;
+        bringToFront(
+            this[r._a .. tailLength],
+            this[tailLength .. length]);
+        return inserted;
+    }
+    /// ditto
+    alias insertBefore stableInsertBefore;
+
+    unittest
+    {
+        Array!bool a;
+        version (bugxxxx)
+        {
+            a._store.refCountedDebug = true;
+        }
+        a.insertBefore(a[], true);
+        assert(a.length == 1, text(a.length));
+        a.insertBefore(a[], false);
+        assert(a.length == 2, text(a.length));
+    }
+
+    /// ditto
+    ulong insertAfter(Stuff)(Range r, Stuff stuff)
+    {
+        // TODO: make this faster, it moves one bit at a time
+        immutable inserted = stableInsertBack(stuff);
+        immutable tailLength = length - inserted;
+        bringToFront(
+            this[r._b .. tailLength],
+            this[tailLength .. length]);
+        return inserted;
+    }
+    /// ditto
+    alias insertAfter stableInsertAfter;
+
+    unittest
+    {
+        Array!bool a;
+        a.length = 10;
+        a.insertAfter(a[0 .. 5], true);
+        assert(a.length == 11, text(a.length));
+        assert(a[5]);
+    }
+    /// ditto
+    size_t replace(Stuff)(Range r, Stuff stuff) if (is(Stuff : bool))
+    {
+        if (!r.empty)
+        {
+            // There is room
+            r.front = stuff;
+            r.popFront();
+            linearRemove(r);
+        }
+        else
+        {
+            // No room, must insert
+            insertBefore(r, stuff);
+        }
+        return 1;
+    }
+    /// ditto
+    alias replace stableReplace;
+
+    unittest
+    {
+        Array!bool a;
+        a.length = 10;
+        a.replace(a[3 .. 5], true);
+        assert(a.length == 9, text(a.length));
+        assert(a[3]);
+    }
+
+    /**
+       Removes all elements belonging to $(D r), which must be a range
+       obtained originally from this container. The stable version
+       behaves the same, but guarantees that ranges iterating over the
+       container are never invalidated.
+
+       Returns: A range spanning the remaining elements in the container that
+       initially were right after $(D r).
+
+       Complexity: $(BIGOH n)
+     */
+    Range linearRemove(Range r)
+    {
+        copy(this[r._b .. length], this[r._a .. length]);
+        length = length - r.length;
+        return this[r._a .. length];
+    }
+    /// ditto
+    alias linearRemove stableLinearRemove;
+}
+
+unittest
+{
+    Array!bool a;
+    assert(a.empty);
+}