Add D front-end, libphobos library, and D2 testsuite.

ChangeLog:

	* Makefile.def (target_modules): Add libphobos.
	(flags_to_pass): Add GDC, GDCFLAGS, GDC_FOR_TARGET and
	GDCFLAGS_FOR_TARGET.
	(dependencies): Make libphobos depend on libatomic, libbacktrace
	configure, and zlib configure.
	(language): Add language d.
	* Makefile.in: Rebuild.
	* Makefile.tpl (BUILD_EXPORTS): Add GDC and GDCFLAGS.
	(HOST_EXPORTS): Add GDC.
	(POSTSTAGE1_HOST_EXPORTS): Add GDC and GDC_FOR_BUILD.
	(BASE_TARGET_EXPORTS): Add GDC.
	(GDC_FOR_BUILD, GDC, GDCFLAGS): New variables.
	(GDC_FOR_TARGET, GDC_FLAGS_FOR_TARGET): New variables.
	(EXTRA_HOST_FLAGS): Add GDC.
	(STAGE1_FLAGS_TO_PASS): Add GDC.
	(EXTRA_TARGET_FLAGS): Add GDC and GDCFLAGS.
	* config-ml.in: Treat GDC and GDCFLAGS like other compiler/flag
	environment variables.
	* configure: Rebuild.
	* configure.ac: Add target-libphobos to target_libraries.  Set and
	substitute GDC_FOR_BUILD and GDC_FOR_TARGET.

config/ChangeLog:

	* multi.m4: Set GDC.

gcc/ChangeLog:

	* Makefile.in (tm_d_file_list, tm_d_include_list): New variables.
	(TM_D_H, D_TARGET_DEF, D_TARGET_H, D_TARGET_OBJS): New variables.
	(tm_d.h, cs-tm_d.h, default-d.o): New rules.
	(d/d-target-hooks-def.h, s-d-target-hooks-def-h): New rules.
	(s-tm-texi): Also check timestamp on d-target.def.
	(generated_files): Add TM_D_H and d-target-hooks-def.h.
	(build/genhooks.o): Also depend on D_TARGET_DEF.
	* config.gcc (tm_d_file, d_target_objs, target_has_targetdm): New
	variables.
	* config/aarch64/aarch64-d.c: New file.
	* config/aarch64/aarch64-linux.h (GNU_USER_TARGET_D_CRITSEC_SIZE):
	Define.
	* config/aarch64/aarch64-protos.h (aarch64_d_target_versions): New
	prototype.
	* config/aarch64/aarch64.h (TARGET_D_CPU_VERSIONS): Define.
	* config/aarch64/t-aarch64 (aarch64-d.o): New rule.
	* config/arm/arm-d.c: New file.
	* config/arm/arm-protos.h (arm_d_target_versions): New prototype.
	* config/arm/arm.h (TARGET_D_CPU_VERSIONS): Define.
	* config/arm/linux-eabi.h (EXTRA_TARGET_D_OS_VERSIONS): Define.
	* config/arm/t-arm (arm-d.o): New rule.
	* config/default-d.c: New file.
	* config/glibc-d.c: New file.
	* config/gnu.h (GNU_USER_TARGET_D_OS_VERSIONS): Define.
	* config/i386/i386-d.c: New file.
	* config/i386/i386-protos.h (ix86_d_target_versions): New prototype.
	* config/i386/i386.h (TARGET_D_CPU_VERSIONS): Define.
	* config/i386/linux-common.h (EXTRA_TARGET_D_OS_VERSIONS): Define.
	(GNU_USER_TARGET_D_CRITSEC_SIZE): Define.
	* config/i386/t-i386 (i386-d.o): New rule.
	* config/kfreebsd-gnu.h (GNU_USER_TARGET_D_OS_VERSIONS): Define.
	* config/kopensolaris-gnu.h (GNU_USER_TARGET_D_OS_VERSIONS): Define.
	* config/linux-android.h (ANDROID_TARGET_D_OS_VERSIONS): Define.
	* config/linux.h (GNU_USER_TARGET_D_OS_VERSIONS): Define.
	* config/mips/linux-common.h (EXTRA_TARGET_D_OS_VERSIONS): Define.
	* config/mips/mips-d.c: New file.
	* config/mips/mips-protos.h (mips_d_target_versions): New prototype.
	* config/mips/mips.h (TARGET_D_CPU_VERSIONS): Define.
	* config/mips/t-mips (mips-d.o): New rule.
	* config/powerpcspe/linux.h (GNU_USER_TARGET_D_OS_VERSIONS): Define.
	* config/powerpcspe/linux64.h (GNU_USER_TARGET_D_OS_VERSIONS): Define.
	* config/powerpcspe/powerpcspe-d.c: New file.
	* config/powerpcspe/powerpcspe-protos.h (rs6000_d_target_versions):
	New prototype.
	* config/powerpcspe/powerpcspe.c (rs6000_output_function_epilogue):
	Support GNU D by using 0 as the language type.
	* config/powerpcspe/powerpcspe.h (TARGET_D_CPU_VERSIONS): Define.
	* config/powerpcspe/t-powerpcspe (powerpcspe-d.o): New rule.
	* config/riscv/riscv-d.c: New file.
	* config/riscv/riscv-protos.h (riscv_d_target_versions): New
	prototype.
	* config/riscv/riscv.h (TARGET_D_CPU_VERSIONS): Define.
	* config/riscv/t-riscv (riscv-d.o): New rule.
	* config/rs6000/linux.h (GNU_USER_TARGET_D_OS_VERSIONS): Define.
	* config/rs6000/linux64.h (GNU_USER_TARGET_D_OS_VERSIONS): Define.
	* config/rs6000/rs6000-d.c: New file.
	* config/rs6000/rs6000-protos.h (rs6000_d_target_versions): New
	prototype.
	* config/rs6000/rs6000.c (rs6000_output_function_epilogue):
	Support GNU D by using 0 as the language type.
	* config/rs6000/rs6000.h (TARGET_D_CPU_VERSIONS): Define.
	* config/rs6000/t-rs6000 (rs6000-d.o): New rule.
	* config/s390/s390-d.c: New file.
	* config/s390/s390-protos.h (s390_d_target_versions): New prototype.
	* config/s390/s390.h (TARGET_D_CPU_VERSIONS): Define.
	* config/s390/t-s390 (s390-d.o): New rule.
	* config/sparc/sparc-d.c: New file.
	* config/sparc/sparc-protos.h (sparc_d_target_versions): New
	prototype.
	* config/sparc/sparc.h (TARGET_D_CPU_VERSIONS): Define.
	* config/sparc/t-sparc (sparc-d.o): New rule.
	* config/t-glibc (glibc-d.o): New rule.
	* configure: Regenerated.
	* configure.ac (tm_d_file): New variable.
	(tm_d_file_list, tm_d_include_list, d_target_objs): Add substitutes.
	* doc/contrib.texi (Contributors): Add self for the D frontend.
	* doc/frontends.texi (G++ and GCC): Mention D as a supported language.
	* doc/install.texi (Configuration): Mention libphobos as an option for
	--enable-shared.  Mention d as an option for --enable-languages.
	(Testing): Mention check-d as a target.
	* doc/invoke.texi (Overall Options): Mention .d, .dd, and .di as file
	name suffixes.  Mention d as a -x option.
	* doc/sourcebuild.texi (Top Level): Mention libphobos.
	* doc/standards.texi (Standards): Add section on D language.
	* doc/tm.texi: Regenerated.
	* doc/tm.texi.in: Add @node for D language and ABI, and @hook for
	TARGET_CPU_VERSIONS, TARGET_D_OS_VERSIONS, and TARGET_D_CRITSEC_SIZE.
	* dwarf2out.c (is_dlang): New function.
	(gen_compile_unit_die): Use DW_LANG_D for D.
	(declare_in_namespace): Return module die for D, instead of adding
	extra declarations into the namespace.
	(gen_namespace_die): Generate DW_TAG_module for D.
	(gen_decl_die): Handle CONST_DECLSs for D.
	(dwarf2out_decl): Likewise.
	(prune_unused_types_walk_local_classes): Handle DW_tag_interface_type.
	(prune_unused_types_walk): Handle DW_tag_interface_type same as other
	kinds of aggregates.
	* gcc.c (default_compilers): Add entries for .d, .dd and .di.
	* genhooks.c: Include d/d-target.def.

gcc/po/ChangeLog:

	* EXCLUDES: Add sources from d/dmd.

gcc/testsuite/ChangeLog:

	* gcc.misc-tests/help.exp: Add D to option descriptions check.
	* gdc.dg/asan/asan.exp: New file.
	* gdc.dg/asan/gdc272.d: New test.
	* gdc.dg/compilable.d: New test.
	* gdc.dg/dg.exp: New file.
	* gdc.dg/gdc254.d: New test.
	* gdc.dg/gdc260.d: New test.
	* gdc.dg/gdc270a.d: New test.
	* gdc.dg/gdc270b.d: New test.
	* gdc.dg/gdc282.d: New test.
	* gdc.dg/gdc283.d: New test.
	* gdc.dg/imports/gdc170.d: New test.
	* gdc.dg/imports/gdc231.d: New test.
	* gdc.dg/imports/gdc239.d: New test.
	* gdc.dg/imports/gdc241a.d: New test.
	* gdc.dg/imports/gdc241b.d: New test.
	* gdc.dg/imports/gdc251a.d: New test.
	* gdc.dg/imports/gdc251b.d: New test.
	* gdc.dg/imports/gdc253.d: New test.
	* gdc.dg/imports/gdc254a.d: New test.
	* gdc.dg/imports/gdc256.d: New test.
	* gdc.dg/imports/gdc27.d: New test.
	* gdc.dg/imports/gdcpkg256/package.d: New test.
	* gdc.dg/imports/runnable.d: New test.
	* gdc.dg/link.d: New test.
	* gdc.dg/lto/lto.exp: New file.
	* gdc.dg/lto/ltotests_0.d: New test.
	* gdc.dg/lto/ltotests_1.d: New test.
	* gdc.dg/runnable.d: New test.
	* gdc.dg/simd.d: New test.
	* gdc.test/gdc-test.exp: New file.
	* lib/gdc-dg.exp: New file.
	* lib/gdc.exp: New file.

libphobos/ChangeLog:

	* Makefile.am: New file.
	* Makefile.in: New file.
	* acinclude.m4: New file.
	* aclocal.m4: New file.
	* config.h.in: New file.
	* configure: New file.
	* configure.ac: New file.
	* d_rules.am: New file.
	* libdruntime/Makefile.am: New file.
	* libdruntime/Makefile.in: New file.
	* libdruntime/__entrypoint.di: New file.
	* libdruntime/__main.di: New file.
	* libdruntime/gcc/attribute.d: New file.
	* libdruntime/gcc/backtrace.d: New file.
	* libdruntime/gcc/builtins.d: New file.
	* libdruntime/gcc/config.d.in: New file.
	* libdruntime/gcc/deh.d: New file.
	* libdruntime/gcc/libbacktrace.d.in: New file.
	* libdruntime/gcc/unwind/arm.d: New file.
	* libdruntime/gcc/unwind/arm_common.d: New file.
	* libdruntime/gcc/unwind/c6x.d: New file.
	* libdruntime/gcc/unwind/generic.d: New file.
	* libdruntime/gcc/unwind/package.d: New file.
	* libdruntime/gcc/unwind/pe.d: New file.
	* m4/autoconf.m4: New file.
	* m4/druntime.m4: New file.
	* m4/druntime/cpu.m4: New file.
	* m4/druntime/libraries.m4: New file.
	* m4/druntime/os.m4: New file.
	* m4/gcc_support.m4: New file.
	* m4/gdc.m4: New file.
	* m4/libtool.m4: New file.
	* src/Makefile.am: New file.
	* src/Makefile.in: New file.
	* src/libgphobos.spec.in: New file.
	* testsuite/Makefile.am: New file.
	* testsuite/Makefile.in: New file.
	* testsuite/config/default.exp: New file.
	* testsuite/lib/libphobos-dg.exp: New file.
	* testsuite/lib/libphobos.exp: New file.
	* testsuite/testsuite_flags.in: New file.

From-SVN: r265573

7 files changed, 8309 insertions, 0 deletions

diff --git a/libphobos/src/std/container/array.d b/libphobos/src/std/container/array.d
new file mode 100644
index 0000000..eee8901
--- /dev/null
+++ b/libphobos/src/std/container/array.d
@@ -0,0 +1,2419 @@
+/**
+ * This module provides an `Array` type with deterministic memory usage not
+ * reliant on the GC, as an alternative to the built-in arrays.
+ *
+ * This module is a submodule of $(MREF std, container).
+ *
+ * Source: $(PHOBOSSRC std/container/_array.d)
+ *
+ * Copyright: 2010- Andrei Alexandrescu. All rights reserved by the respective holders.
+ *
+ * License: Distributed under the Boost Software License, Version 1.0.
+ * (See accompanying file LICENSE_1_0.txt or copy at $(HTTP
+ * boost.org/LICENSE_1_0.txt)).
+ *
+ * Authors: $(HTTP erdani.com, Andrei Alexandrescu)
+ *
+ * $(SCRIPT inhibitQuickIndex = 1;)
+ */
+module std.container.array;
+
+import core.exception : RangeError;
+import std.range.primitives;
+import std.traits;
+
+public import std.container.util;
+
+///
+@system unittest
+{
+    auto arr = Array!int(0, 2, 3);
+    assert(arr[0] == 0);
+    assert(arr.front == 0);
+    assert(arr.back == 3);
+
+    // reserve space
+    arr.reserve(1000);
+    assert(arr.length == 3);
+    assert(arr.capacity >= 1000);
+
+    // insertion
+    arr.insertBefore(arr[1..$], 1);
+    assert(arr.front == 0);
+    assert(arr.length == 4);
+
+    arr.insertBack(4);
+    assert(arr.back == 4);
+    assert(arr.length == 5);
+
+    // set elements
+    arr[1] *= 42;
+    assert(arr[1] == 42);
+}
+
+///
+@system unittest
+{
+    import std.algorithm.comparison : equal;
+    auto arr = Array!int(1, 2, 3);
+
+    // concat
+    auto b = Array!int(11, 12, 13);
+    arr ~= b;
+    assert(arr.length == 6);
+
+    // slicing
+    assert(arr[1 .. 3].equal([2, 3]));
+
+    // remove
+    arr.linearRemove(arr[1 .. 3]);
+    assert(arr[0 .. 2].equal([1, 11]));
+}
+
+/// `Array!bool` packs together values efficiently by allocating one bit per element
+@system unittest
+{
+    Array!bool arr;
+    arr.insert([true, true, false, true, false]);
+    assert(arr.length == 5);
+}
+
+private struct RangeT(A)
+{
+    /* Workaround for Issue 13629 at https://issues.dlang.org/show_bug.cgi?id=13629
+       See also: http://forum.dlang.org/post/vbmwhzvawhnkoxrhbnyb@forum.dlang.org
+    */
+    private A[1] _outer_;
+    private @property ref inout(A) _outer() inout { return _outer_[0]; }
+
+    private size_t _a, _b;
+
+    /* E is different from T when A is more restrictively qualified than T:
+       immutable(Array!int) => T == int, E = immutable(int) */
+    alias E = typeof(_outer_[0]._data._payload[0]);
+
+    private this(ref A data, size_t a, size_t b)
+    {
+        _outer_ = data;
+        _a = a;
+        _b = b;
+    }
+
+    @property RangeT save()
+    {
+        return this;
+    }
+
+    @property bool empty() @safe pure nothrow const
+    {
+        return _a >= _b;
+    }
+
+    @property size_t length() @safe pure nothrow const
+    {
+        return _b - _a;
+    }
+    alias opDollar = length;
+
+    @property ref inout(E) front() inout
+    {
+        assert(!empty, "Attempting to access the front of an empty Array");
+        return _outer[_a];
+    }
+    @property ref inout(E) back() inout
+    {
+        assert(!empty, "Attempting to access the back of an empty Array");
+        return _outer[_b - 1];
+    }
+
+    void popFront() @safe @nogc pure nothrow
+    {
+        assert(!empty, "Attempting to popFront an empty Array");
+        ++_a;
+    }
+
+    void popBack() @safe @nogc pure nothrow
+    {
+        assert(!empty, "Attempting to popBack an empty Array");
+        --_b;
+    }
+
+    static if (isMutable!A)
+    {
+        import std.algorithm.mutation : move;
+
+        E moveFront()
+        {
+            assert(!empty && _a < _outer.length);
+            return move(_outer._data._payload[_a]);
+        }
+
+        E moveBack()
+        {
+            assert(!empty && _b  <= _outer.length);
+            return move(_outer._data._payload[_b - 1]);
+        }
+
+        E moveAt(size_t i)
+        {
+            assert(_a + i < _b && _a + i < _outer.length);
+            return move(_outer._data._payload[_a + i]);
+        }
+    }
+
+    ref inout(E) opIndex(size_t i) inout
+    {
+        assert(_a + i < _b);
+        return _outer[_a + i];
+    }
+
+    RangeT opSlice()
+    {
+        return typeof(return)(_outer, _a, _b);
+    }
+
+    RangeT opSlice(size_t i, size_t j)
+    {
+        assert(i <= j && _a + j <= _b);
+        return typeof(return)(_outer, _a + i, _a + j);
+    }
+
+    RangeT!(const(A)) opSlice() const
+    {
+        return typeof(return)(_outer, _a, _b);
+    }
+
+    RangeT!(const(A)) opSlice(size_t i, size_t j) const
+    {
+        assert(i <= j && _a + j <= _b);
+        return typeof(return)(_outer, _a + i, _a + j);
+    }
+
+    static if (isMutable!A)
+    {
+        void opSliceAssign(E value)
+        {
+            assert(_b <= _outer.length);
+            _outer[_a .. _b] = value;
+        }
+
+        void opSliceAssign(E value, size_t i, size_t j)
+        {
+            assert(_a + j <= _b);
+            _outer[_a + i .. _a + j] = value;
+        }
+
+        void opSliceUnary(string op)()
+        if (op == "++" || op == "--")
+        {
+            assert(_b <= _outer.length);
+            mixin(op~"_outer[_a .. _b];");
+        }
+
+        void opSliceUnary(string op)(size_t i, size_t j)
+        if (op == "++" || op == "--")
+        {
+            assert(_a + j <= _b);
+            mixin(op~"_outer[_a + i .. _a + j];");
+        }
+
+        void opSliceOpAssign(string op)(E value)
+        {
+            assert(_b <= _outer.length);
+            mixin("_outer[_a .. _b] "~op~"= value;");
+        }
+
+        void opSliceOpAssign(string op)(E value, size_t i, size_t j)
+        {
+            assert(_a + j <= _b);
+            mixin("_outer[_a + i .. _a + j] "~op~"= value;");
+        }
+    }
+}
+
+/**
+ * _Array type with deterministic control of memory. The memory allocated
+ * for the array is reclaimed as soon as possible; there is no reliance
+ * on the garbage collector. `Array` uses `malloc`, `realloc` and `free`
+ * for managing its own memory.
+ *
+ * This means that pointers to elements of an `Array` will become
+ * dangling as soon as the element is removed from the `Array`. On the other hand
+ * the memory allocated by an `Array` will be scanned by the GC and
+ * GC managed objects referenced from an `Array` will be kept alive.
+ *
+ * Note:
+ *
+ * When using `Array` with range-based functions like those in `std.algorithm`,
+ * `Array` must be sliced to get a range (for example, use `array[].map!`
+ * instead of `array.map!`). The container itself is not a range.
+ */
+struct Array(T)
+if (!is(Unqual!T == bool))
+{
+    import core.stdc.stdlib : malloc, realloc, free;
+    import core.stdc.string : memcpy, memmove, memset;
+
+    import core.memory : GC;
+
+    import std.exception : enforce;
+    import std.typecons : RefCounted, RefCountedAutoInitialize;
+
+    // This structure is not copyable.
+    private struct Payload
+    {
+        size_t _capacity;
+        T[] _payload;
+
+        this(T[] p) { _capacity = p.length; _payload = p; }
+
+        // Destructor releases array memory
+        ~this()
+        {
+            // Warning: destroy would destroy also class instances.
+            // The hasElaborateDestructor protects us here.
+            static if (hasElaborateDestructor!T)
+                foreach (ref e; _payload)
+                    .destroy(e);
+
+            static if (hasIndirections!T)
+                GC.removeRange(_payload.ptr);
+
+            free(_payload.ptr);
+        }
+
+        this(this) @disable;
+
+        void opAssign(Payload rhs) @disable;
+
+        @property size_t length() const
+        {
+            return _payload.length;
+        }
+
+        @property void length(size_t newLength)
+        {
+            import std.algorithm.mutation : initializeAll;
+
+            if (length >= newLength)
+            {
+                // shorten
+                static if (hasElaborateDestructor!T)
+                    foreach (ref e; _payload.ptr[newLength .. _payload.length])
+                        .destroy(e);
+
+                _payload = _payload.ptr[0 .. newLength];
+                return;
+            }
+            immutable startEmplace = length;
+            if (_capacity < newLength)
+            {
+                // enlarge
+                import core.checkedint : mulu;
+
+                bool overflow;
+                const nbytes = mulu(newLength, T.sizeof, overflow);
+                if (overflow)
+                    assert(0);
+                _payload = (cast(T*) realloc(_payload.ptr, nbytes))[0 .. newLength];
+                _capacity = newLength;
+            }
+            else
+            {
+                _payload = _payload.ptr[0 .. newLength];
+            }
+            initializeAll(_payload.ptr[startEmplace .. newLength]);
+        }
+
+        @property size_t capacity() const
+        {
+            return _capacity;
+        }
+
+        void reserve(size_t elements)
+        {
+            if (elements <= capacity) return;
+            import core.checkedint : mulu;
+            bool overflow;
+            const sz = mulu(elements, T.sizeof, overflow);
+            if (overflow)
+                assert(0);
+            static if (hasIndirections!T)
+            {
+                /* Because of the transactional nature of this
+                 * relative to the garbage collector, ensure no
+                 * threading bugs by using malloc/copy/free rather
+                 * than realloc.
+                 */
+                immutable oldLength = length;
+
+                auto newPayloadPtr = cast(T*) malloc(sz);
+                newPayloadPtr || assert(false, "std.container.Array.reserve failed to allocate memory");
+                auto newPayload = newPayloadPtr[0 .. oldLength];
+
+                // copy old data over to new array
+                memcpy(newPayload.ptr, _payload.ptr, T.sizeof * oldLength);
+                // Zero out unused capacity to prevent gc from seeing false pointers
+                memset(newPayload.ptr + oldLength,
+                        0,
+                        (elements - oldLength) * T.sizeof);
+                GC.addRange(newPayload.ptr, sz);
+                GC.removeRange(_payload.ptr);
+                free(_payload.ptr);
+                _payload = newPayload;
+            }
+            else
+            {
+                // These can't have pointers, so no need to zero unused region
+                auto newPayloadPtr = cast(T*) realloc(_payload.ptr, sz);
+                newPayloadPtr || assert(false, "std.container.Array.reserve failed to allocate memory");
+                auto newPayload = newPayloadPtr[0 .. length];
+                _payload = newPayload;
+            }
+            _capacity = elements;
+        }
+
+        // Insert one item
+        size_t insertBack(Elem)(Elem elem)
+        if (isImplicitlyConvertible!(Elem, T))
+        {
+            import std.conv : emplace;
+            if (_capacity == length)
+            {
+                reserve(1 + capacity * 3 / 2);
+            }
+            assert(capacity > length && _payload.ptr);
+            emplace(_payload.ptr + _payload.length, elem);
+            _payload = _payload.ptr[0 .. _payload.length + 1];
+            return 1;
+        }
+
+        // Insert a range of items
+        size_t insertBack(Range)(Range r)
+        if (isInputRange!Range && isImplicitlyConvertible!(ElementType!Range, T))
+        {
+            static if (hasLength!Range)
+            {
+                immutable oldLength = length;
+                reserve(oldLength + r.length);
+            }
+            size_t result;
+            foreach (item; r)
+            {
+                insertBack(item);
+                ++result;
+            }
+            static if (hasLength!Range)
+            {
+                assert(length == oldLength + r.length);
+            }
+            return result;
+        }
+    }
+    private alias Data = RefCounted!(Payload, RefCountedAutoInitialize.no);
+    private Data _data;
+
+    /**
+     * Constructor taking a number of items.
+     */
+    this(U)(U[] values...)
+    if (isImplicitlyConvertible!(U, T))
+    {
+        import core.checkedint : mulu;
+        import std.conv : emplace;
+        bool overflow;
+        const nbytes = mulu(values.length, T.sizeof, overflow);
+        if (overflow) assert(0);
+        auto p = cast(T*) malloc(nbytes);
+        static if (hasIndirections!T)
+        {
+            if (p)
+                GC.addRange(p, T.sizeof * values.length);
+        }
+
+        foreach (i, e; values)
+        {
+            emplace(p + i, e);
+        }
+        _data = Data(p[0 .. values.length]);
+    }
+
+    /**
+     * Constructor taking an input range
+     */
+    this(Range)(Range r)
+    if (isInputRange!Range && isImplicitlyConvertible!(ElementType!Range, T) && !is(Range == T[]))
+    {
+        insertBack(r);
+    }
+
+    /**
+     * Comparison for equality.
+     */
+    bool opEquals(const Array rhs) const
+    {
+        return opEquals(rhs);
+    }
+
+    /// ditto
+    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 array's primary range, which is a random-access range.
+     *
+     *  `ConstRange` is a variant with `const` elements.
+     *  `ImmutableRange` is a variant with `immutable` elements.
+     */
+    alias Range = RangeT!Array;
+
+    /// ditto
+    alias ConstRange = RangeT!(const Array);
+
+    /// ditto
+    alias ImmutableRange = RangeT!(immutable Array);
+
+    /**
+     * Duplicates the array. The elements themselves are not transitively
+     * duplicated.
+     *
+     * Complexity: $(BIGOH length).
+     */
+    @property Array dup()
+    {
+        if (!_data.refCountedStore.isInitialized) return this;
+        return Array(_data._payload);
+    }
+
+    /**
+     * Returns: `true` if and only if the array has no elements.
+     *
+     * Complexity: $(BIGOH 1)
+     */
+    @property bool empty() const
+    {
+        return !_data.refCountedStore.isInitialized || _data._payload.empty;
+    }
+
+    /**
+     * Returns: The number of elements in the array.
+     *
+     * Complexity: $(BIGOH 1).
+     */
+    @property size_t length() const
+    {
+        return _data.refCountedStore.isInitialized ? _data._payload.length : 0;
+    }
+
+    /// ditto
+    size_t opDollar() const
+    {
+        return length;
+    }
+
+    /**
+     * Returns: The maximum number of elements the array can store without
+     * reallocating memory and invalidating iterators upon insertion.
+     *
+     * Complexity: $(BIGOH 1)
+     */
+    @property size_t capacity()
+    {
+        return _data.refCountedStore.isInitialized ? _data._capacity : 0;
+    }
+
+    /**
+     * Ensures sufficient capacity to accommodate `e` _elements.
+     * If `e < capacity`, this method does nothing.
+     *
+     * Postcondition: `capacity >= e`
+     *
+     * Note: If the capacity is increased, one should assume that all
+     * iterators to the elements are invalidated.
+     *
+     * Complexity: at most $(BIGOH length) if `e > capacity`, otherwise $(BIGOH 1).
+     */
+    void reserve(size_t elements)
+    {
+        if (!_data.refCountedStore.isInitialized)
+        {
+            if (!elements) return;
+            import core.checkedint : mulu;
+            bool overflow;
+            const sz = mulu(elements, T.sizeof, overflow);
+            if (overflow) assert(0);
+            auto p = malloc(sz);
+            p || assert(false, "std.container.Array.reserve failed to allocate memory");
+            static if (hasIndirections!T)
+            {
+                GC.addRange(p, sz);
+            }
+            _data = Data(cast(T[]) p[0 .. 0]);
+            _data._capacity = elements;
+        }
+        else
+        {
+            _data.reserve(elements);
+        }
+    }
+
+    /**
+     * Returns: A range that iterates over elements of the array in
+     * forward order.
+     *
+     * Complexity: $(BIGOH 1)
+     */
+    Range opSlice()
+    {
+        return typeof(return)(this, 0, length);
+    }
+
+    ConstRange opSlice() const
+    {
+        return typeof(return)(this, 0, length);
+    }
+
+    ImmutableRange opSlice() immutable
+    {
+        return typeof(return)(this, 0, length);
+    }
+
+    /**
+     * Returns: A range that iterates over elements of the array from
+     * index `i` up to (excluding) index `j`.
+     *
+     * Precondition: `i <= j && j <= length`
+     *
+     * Complexity: $(BIGOH 1)
+     */
+    Range opSlice(size_t i, size_t j)
+    {
+        assert(i <= j && j <= length);
+        return typeof(return)(this, i, j);
+    }
+
+    ConstRange opSlice(size_t i, size_t j) const
+    {
+        assert(i <= j && j <= length);
+        return typeof(return)(this, i, j);
+    }
+
+    ImmutableRange opSlice(size_t i, size_t j) immutable
+    {
+        assert(i <= j && j <= length);
+        return typeof(return)(this, i, j);
+    }
+
+    /**
+     * Returns: The first element of the array.
+     *
+     * Precondition: `empty == false`
+     *
+     * Complexity: $(BIGOH 1)
+     */
+    @property ref inout(T) front() inout
+    {
+        assert(_data.refCountedStore.isInitialized);
+        return _data._payload[0];
+    }
+
+    /**
+     * Returns: The last element of the array.
+     *
+     * Precondition: `empty == false`
+     *
+     * Complexity: $(BIGOH 1)
+     */
+    @property ref inout(T) back() inout
+    {
+        assert(_data.refCountedStore.isInitialized);
+        return _data._payload[$ - 1];
+    }
+
+    /**
+     * Returns: The element or a reference to the element at the specified index.
+     *
+     * Precondition: `i < length`
+     *
+     * Complexity: $(BIGOH 1)
+     */
+    ref inout(T) opIndex(size_t i) inout
+    {
+        assert(_data.refCountedStore.isInitialized);
+        return _data._payload[i];
+    }
+
+    /**
+     * Slicing operators executing the specified operation on the entire slice.
+     *
+     * Precondition: `i < j && j < length`
+     *
+     * Complexity: $(BIGOH slice.length)
+     */
+    void opSliceAssign(T value)
+    {
+        if (!_data.refCountedStore.isInitialized) return;
+        _data._payload[] = value;
+    }
+
+    /// ditto
+    void opSliceAssign(T value, size_t i, size_t j)
+    {
+        auto slice = _data.refCountedStore.isInitialized ?
+            _data._payload :
+            T[].init;
+        slice[i .. j] = value;
+    }
+
+    /// ditto
+    void opSliceUnary(string op)()
+    if (op == "++" || op == "--")
+    {
+        if (!_data.refCountedStore.isInitialized) return;
+        mixin(op~"_data._payload[];");
+    }
+
+    /// ditto
+    void opSliceUnary(string op)(size_t i, size_t j)
+    if (op == "++" || op == "--")
+    {
+        auto slice = _data.refCountedStore.isInitialized ? _data._payload : T[].init;
+        mixin(op~"slice[i .. j];");
+    }
+
+    /// ditto
+    void opSliceOpAssign(string op)(T value)
+    {
+        if (!_data.refCountedStore.isInitialized) return;
+        mixin("_data._payload[] "~op~"= value;");
+    }
+
+    /// ditto
+    void opSliceOpAssign(string op)(T value, size_t i, size_t j)
+    {
+        auto slice = _data.refCountedStore.isInitialized ? _data._payload : T[].init;
+        mixin("slice[i .. j] "~op~"= value;");
+    }
+
+    private enum hasSliceWithLength(T) = is(typeof({ T t = T.init; t[].length; }));
+
+    /**
+     * Returns: A new array which is a concatenation of `this` and its argument.
+     *
+     * Complexity:
+     * $(BIGOH length + m), where `m` is the number of elements in `stuff`.
+     */
+    Array opBinary(string op, Stuff)(Stuff stuff)
+    if (op == "~")
+    {
+        Array result;
+
+        static if (hasLength!Stuff || isNarrowString!Stuff)
+            result.reserve(length + stuff.length);
+        else static if (hasSliceWithLength!Stuff)
+            result.reserve(length + stuff[].length);
+        else static if (isImplicitlyConvertible!(Stuff, T))
+            result.reserve(length + 1);
+
+        result.insertBack(this[]);
+        result ~= stuff;
+        return result;
+    }
+
+    /**
+     * Forwards to `insertBack`.
+     */
+    void opOpAssign(string op, Stuff)(auto ref Stuff stuff)
+    if (op == "~")
+    {
+        static if (is(typeof(stuff[])) && isImplicitlyConvertible!(typeof(stuff[0]), T))
+        {
+            insertBack(stuff[]);
+        }
+        else
+        {
+            insertBack(stuff);
+        }
+    }
+
+    /**
+     * Removes all the elements from the array and releases allocated memory.
+     *
+     * Postcondition: `empty == true && capacity == 0`
+     *
+     * Complexity: $(BIGOH length)
+     */
+    void clear()
+    {
+        _data = Data.init;
+    }
+
+    /**
+     * Sets the number of elements in the array to `newLength`. If `newLength`
+     * is greater than `length`, the new elements are added to the end of the
+     * array and initialized with `T.init`.
+     *
+     * Complexity:
+     * Guaranteed $(BIGOH abs(length - newLength)) if `capacity >= newLength`.
+     * If `capacity < newLength` the worst case is $(BIGOH newLength).
+     *
+     * Postcondition: `length == newLength`
+     */
+    @property void length(size_t newLength)
+    {
+        _data.refCountedStore.ensureInitialized();
+        _data.length = newLength;
+    }
+
+    /**
+     * Removes the last element from the array and returns it.
+     * Both stable and non-stable versions behave the same and guarantee
+     * that ranges iterating over the array are never invalidated.
+     *
+     * Precondition: `empty == false`
+     *
+     * Returns: The element removed.
+     *
+     * Complexity: $(BIGOH 1).
+     *
+     * Throws: `Exception` if the array is empty.
+     */
+    T removeAny()
+    {
+        auto result = back;
+        removeBack();
+        return result;
+    }
+
+    /// ditto
+    alias stableRemoveAny = removeAny;
+
+    /**
+     * Inserts the specified elements at the back of the array. `stuff` can be
+     * a value convertible to `T` or a range of objects convertible to `T`.
+     *
+     * Returns: The number of elements inserted.
+     *
+     * Complexity:
+     * $(BIGOH length + m) if reallocation takes place, otherwise $(BIGOH m),
+     * where `m` is the number of elements in `stuff`.
+     */
+    size_t insertBack(Stuff)(Stuff stuff)
+    if (isImplicitlyConvertible!(Stuff, T) ||
+            isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T))
+    {
+        _data.refCountedStore.ensureInitialized();
+        return _data.insertBack(stuff);
+    }
+
+    /// ditto
+    alias insert = insertBack;
+
+    /**
+     * Removes the value from the back of the array. Both stable and non-stable
+     * versions behave the same and guarantee that ranges iterating over the
+     * array are never invalidated.
+     *
+     * Precondition: `empty == false`
+     *
+     * Complexity: $(BIGOH 1).
+     *
+     * Throws: `Exception` if the array is empty.
+     */
+    void removeBack()
+    {
+        enforce(!empty);
+        static if (hasElaborateDestructor!T)
+            .destroy(_data._payload[$ - 1]);
+
+        _data._payload = _data._payload[0 .. $ - 1];
+    }
+
+    /// ditto
+    alias stableRemoveBack = removeBack;
+
+    /**
+     * Removes `howMany` values from the back of the array.
+     * Unlike the unparameterized versions above, these functions
+     * do not throw if they could not remove `howMany` elements. Instead,
+     * if `howMany > n`, all elements are removed. The returned value is
+     * the effective number of elements removed. Both stable and non-stable
+     * versions behave the same and guarantee that ranges iterating over
+     * the array 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 (hasElaborateDestructor!T)
+            foreach (ref e; _data._payload[$ - howMany .. $])
+                .destroy(e);
+
+        _data._payload = _data._payload[0 .. $ - howMany];
+        return howMany;
+    }
+
+    /// ditto
+    alias stableRemoveBack = removeBack;
+
+    /**
+     * Inserts `stuff` before, after, or instead range `r`, which must
+     * be a valid range previously extracted from this array. `stuff`
+     * can be a value convertible to `T` or a range of objects convertible
+     * to `T`. Both stable and non-stable version behave the same and
+     * guarantee that ranges iterating over the array are never invalidated.
+     *
+     * Returns: The number of values inserted.
+     *
+     * Complexity: $(BIGOH length + m), where `m` is the length of `stuff`.
+     *
+     * Throws: `Exception` if `r` is not a range extracted from this array.
+     */
+    size_t insertBefore(Stuff)(Range r, Stuff stuff)
+    if (isImplicitlyConvertible!(Stuff, T))
+    {
+        import std.conv : emplace;
+        enforce(r._outer._data is _data && r._a <= length);
+        reserve(length + 1);
+        assert(_data.refCountedStore.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(_data._payload.ptr + r._a, 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))
+    {
+        import std.conv : emplace;
+        enforce(r._outer._data is _data && r._a <= length);
+        static if (isForwardRange!Stuff)
+        {
+            // Can find the length in advance
+            auto extra = walkLength(stuff);
+            if (!extra) return 0;
+            reserve(length + extra);
+            assert(_data.refCountedStore.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(p, stuff.front);
+                stuff.popFront();
+            }
+            _data._payload =
+                _data._payload.ptr[0 .. _data._payload.length + extra];
+            return extra;
+        }
+        else
+        {
+            import std.algorithm.mutation : bringToFront;
+            enforce(_data);
+            immutable offset = r._a;
+            enforce(offset <= length);
+            auto result = insertBack(stuff);
+            bringToFront(this[offset .. length - result],
+                    this[length - result .. length]);
+            return result;
+        }
+    }
+
+    /// ditto
+    alias stableInsertBefore = insertBefore;
+
+    /// ditto
+    size_t insertAfter(Stuff)(Range r, Stuff stuff)
+    {
+        import std.algorithm.mutation : bringToFront;
+        enforce(r._outer._data is _data);
+        // TODO: optimize
+        immutable offset = r._b;
+        enforce(offset <= length);
+        auto result = insertBack(stuff);
+        bringToFront(this[offset .. length - result],
+                this[length - result .. length]);
+        return result;
+    }
+
+    /// ditto
+    size_t replace(Stuff)(Range r, Stuff stuff)
+    if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T))
+    {
+        enforce(r._outer._data is _data);
+        size_t result;
+        for (; !stuff.empty; stuff.popFront())
+        {
+            if (r.empty)
+            {
+                // insert the rest
+                return result + insertBefore(r, stuff);
+            }
+            r.front = stuff.front;
+            r.popFront();
+            ++result;
+        }
+        // Remove remaining stuff in r
+        linearRemove(r);
+        return result;
+    }
+
+    /// ditto
+    size_t replace(Stuff)(Range r, Stuff stuff)
+    if (isImplicitlyConvertible!(Stuff, T))
+    {
+        enforce(r._outer._data is _data);
+        if (r.empty)
+        {
+            insertBefore(r, stuff);
+        }
+        else
+        {
+            r.front = stuff;
+            r.popFront();
+            linearRemove(r);
+        }
+        return 1;
+    }
+
+    /**
+     * Removes all elements belonging to `r`, which must be a range
+     * obtained originally from this array.
+     *
+     * Returns: A range spanning the remaining elements in the array that
+     * initially were right after `r`.
+     *
+     * Complexity: $(BIGOH length)
+     *
+     * Throws: `Exception` if `r` is not a valid range extracted from this array.
+     */
+    Range linearRemove(Range r)
+    {
+        import std.algorithm.mutation : copy;
+
+        enforce(r._outer._data is _data);
+        enforce(_data.refCountedStore.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];
+    }
+}
+
+@system unittest
+{
+    Array!int a;
+    assert(a.empty);
+}
+
+@system unittest
+{
+    Array!int a;
+    a.length = 10;
+    assert(a.length == 10);
+    assert(a.capacity >= a.length);
+}
+
+@system unittest
+{
+    struct Dumb { int x = 5; }
+    Array!Dumb a;
+    a.length = 10;
+    assert(a.length == 10);
+    assert(a.capacity >= a.length);
+    immutable cap = a.capacity;
+    foreach (ref e; a)
+        e.x = 10;
+    a.length = 5;
+    assert(a.length == 5);
+    // do not realloc if length decreases
+    assert(a.capacity == cap);
+    foreach (ref e; a)
+        assert(e.x == 10);
+
+    a.length = 8;
+    assert(a.length == 8);
+    // do not realloc if capacity sufficient
+    assert(a.capacity == cap);
+    assert(Dumb.init.x == 5);
+    foreach (i; 0 .. 5)
+        assert(a[i].x == 10);
+    foreach (i; 5 .. a.length)
+        assert(a[i].x == Dumb.init.x);
+
+    // realloc required, check if values properly copied
+    a[] = Dumb(1);
+    a.length = 20;
+    assert(a.capacity >= 20);
+    foreach (i; 0 .. 8)
+        assert(a[i].x == 1);
+    foreach (i; 8 .. a.length)
+        assert(a[i].x == Dumb.init.x);
+
+    // check if overlapping elements properly initialized
+    a.length = 1;
+    a.length = 20;
+    assert(a[0].x == 1);
+    foreach (e; a[1 .. $])
+        assert(e.x == Dumb.init.x);
+}
+
+@system unittest
+{
+    Array!int a = Array!int(1, 2, 3);
+    //a._data._refCountedDebug = true;
+    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));
+}
+
+@system unittest
+{
+    auto a = Array!int(1, 2, 3);
+    assert(a.length == 3);
+}
+
+@system unittest
+{
+    const Array!int a = [1, 2];
+
+    assert(a[0] == 1);
+    assert(a.front == 1);
+    assert(a.back == 2);
+
+    static assert(!__traits(compiles, { a[0] = 1; }));
+    static assert(!__traits(compiles, { a.front = 1; }));
+    static assert(!__traits(compiles, { a.back = 1; }));
+
+    auto r = a[];
+    size_t i;
+    foreach (e; r)
+    {
+        assert(e == i + 1);
+        i++;
+    }
+}
+
+@safe unittest
+{
+    // REG https://issues.dlang.org/show_bug.cgi?id=13621
+    import std.container : Array, BinaryHeap;
+    alias Heap = BinaryHeap!(Array!int);
+}
+
+@system unittest
+{
+    Array!int a;
+    a.reserve(1000);
+    assert(a.length == 0);
+    assert(a.empty);
+    assert(a.capacity >= 1000);
+    auto p = a._data._payload.ptr;
+    foreach (i; 0 .. 1000)
+    {
+        a.insertBack(i);
+    }
+    assert(p == a._data._payload.ptr);
+}
+
+@system unittest
+{
+    auto a = Array!int(1, 2, 3);
+    a[1] *= 42;
+    assert(a[1] == 84);
+}
+
+@system unittest
+{
+    auto a = Array!int(1, 2, 3);
+    auto b = Array!int(11, 12, 13);
+    auto c = a ~ b;
+    assert(c == Array!int(1, 2, 3, 11, 12, 13));
+    assert(a ~ b[] == Array!int(1, 2, 3, 11, 12, 13));
+    assert(a ~ [4,5] == Array!int(1,2,3,4,5));
+}
+
+@system 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));
+}
+
+@system unittest
+{
+    auto a = Array!int(1, 2, 3, 4);
+    assert(a.removeAny() == 4);
+    assert(a == Array!int(1, 2, 3));
+}
+
+@system unittest
+{
+    auto a = Array!int(1, 2, 3, 4, 5);
+    auto r = a[2 .. a.length];
+    assert(a.insertBefore(r, 42) == 1);
+    assert(a == Array!int(1, 2, 42, 3, 4, 5));
+    r = a[2 .. 2];
+    assert(a.insertBefore(r, [8, 9]) == 2);
+    assert(a == Array!int(1, 2, 8, 9, 42, 3, 4, 5));
+}
+
+@system unittest
+{
+    auto a = Array!int(0, 1, 2, 3, 4, 5, 6, 7, 8);
+    a.linearRemove(a[4 .. 6]);
+    assert(a == Array!int(0, 1, 2, 3, 6, 7, 8));
+}
+
+// Give the Range object some testing.
+@system unittest
+{
+    import std.algorithm.comparison : equal;
+    import std.range : retro;
+    auto a = Array!int(0, 1, 2, 3, 4, 5, 6)[];
+    auto b = Array!int(6, 5, 4, 3, 2, 1, 0)[];
+    alias A = typeof(a);
+
+    static assert(isRandomAccessRange!A);
+    static assert(hasSlicing!A);
+    static assert(hasAssignableElements!A);
+    static assert(hasMobileElements!A);
+
+    assert(equal(retro(b), a));
+    assert(a.length == 7);
+    assert(equal(a[1 .. 4], [1, 2, 3]));
+}
+// Test issue 5920
+@system unittest
+{
+    struct structBug5920
+    {
+        int order;
+        uint* pDestructionMask;
+        ~this()
+        {
+            if (pDestructionMask)
+                *pDestructionMask += 1 << order;
+        }
+    }
+
+    alias S = structBug5920;
+    uint dMask;
+
+    auto arr = Array!S(cast(S[])[]);
+    foreach (i; 0 .. 8)
+        arr.insertBack(S(i, &dMask));
+    // don't check dMask now as S may be copied multiple times (it's ok?)
+    {
+        assert(arr.length == 8);
+        dMask = 0;
+        arr.length = 6;
+        assert(arr.length == 6);    // make sure shrinking calls the d'tor
+        assert(dMask == 0b1100_0000);
+        arr.removeBack();
+        assert(arr.length == 5);    // make sure removeBack() calls the d'tor
+        assert(dMask == 0b1110_0000);
+        arr.removeBack(3);
+        assert(arr.length == 2);    // ditto
+        assert(dMask == 0b1111_1100);
+        arr.clear();
+        assert(arr.length == 0);    // make sure clear() calls the d'tor
+        assert(dMask == 0b1111_1111);
+    }
+    assert(dMask == 0b1111_1111);   // make sure the d'tor is called once only.
+}
+// Test issue 5792 (mainly just to check if this piece of code is compilable)
+@system unittest
+{
+    auto a = Array!(int[])([[1,2],[3,4]]);
+    a.reserve(4);
+    assert(a.capacity >= 4);
+    assert(a.length == 2);
+    assert(a[0] == [1,2]);
+    assert(a[1] == [3,4]);
+    a.reserve(16);
+    assert(a.capacity >= 16);
+    assert(a.length == 2);
+    assert(a[0] == [1,2]);
+    assert(a[1] == [3,4]);
+}
+
+// test replace!Stuff with range Stuff
+@system unittest
+{
+    import std.algorithm.comparison : equal;
+    auto a = Array!int([1, 42, 5]);
+    a.replace(a[1 .. 2], [2, 3, 4]);
+    assert(equal(a[], [1, 2, 3, 4, 5]));
+}
+
+// test insertBefore and replace with empty Arrays
+@system unittest
+{
+    import std.algorithm.comparison : equal;
+    auto a = Array!int();
+    a.insertBefore(a[], 1);
+    assert(equal(a[], [1]));
+}
+@system unittest
+{
+    import std.algorithm.comparison : equal;
+    auto a = Array!int();
+    a.insertBefore(a[], [1, 2]);
+    assert(equal(a[], [1, 2]));
+}
+@system unittest
+{
+    import std.algorithm.comparison : equal;
+    auto a = Array!int();
+    a.replace(a[], [1, 2]);
+    assert(equal(a[], [1, 2]));
+}
+@system unittest
+{
+    import std.algorithm.comparison : equal;
+    auto a = Array!int();
+    a.replace(a[], 1);
+    assert(equal(a[], [1]));
+}
+// make sure that Array instances refuse ranges that don't belong to them
+@system unittest
+{
+    import std.exception : assertThrown;
+
+    Array!int a = [1, 2, 3];
+    auto r = a.dup[];
+    assertThrown(a.insertBefore(r, 42));
+    assertThrown(a.insertBefore(r, [42]));
+    assertThrown(a.insertAfter(r, 42));
+    assertThrown(a.replace(r, 42));
+    assertThrown(a.replace(r, [42]));
+    assertThrown(a.linearRemove(r));
+}
+@system unittest
+{
+    auto a = Array!int([1, 1]);
+    a[1]  = 0; //Check Array.opIndexAssign
+    assert(a[1] == 0);
+    a[1] += 1; //Check Array.opIndexOpAssign
+    assert(a[1] == 1);
+
+    //Check Array.opIndexUnary
+    ++a[0];
+    //a[0]++ //op++ doesn't return, so this shouldn't work, even with 5044 fixed
+    assert(a[0] == 2);
+    assert(+a[0] == +2);
+    assert(-a[0] == -2);
+    assert(~a[0] == ~2);
+
+    auto r = a[];
+    r[1]  = 0; //Check Array.Range.opIndexAssign
+    assert(r[1] == 0);
+    r[1] += 1; //Check Array.Range.opIndexOpAssign
+    assert(r[1] == 1);
+
+    //Check Array.Range.opIndexUnary
+    ++r[0];
+    //r[0]++ //op++ doesn't return, so this shouldn't work, even with 5044 fixed
+    assert(r[0] == 3);
+    assert(+r[0] == +3);
+    assert(-r[0] == -3);
+    assert(~r[0] == ~3);
+}
+
+@system unittest
+{
+    import std.algorithm.comparison : equal;
+
+    //Test "array-wide" operations
+    auto a = Array!int([0, 1, 2]); //Array
+    a[] += 5;
+    assert(a[].equal([5, 6, 7]));
+    ++a[];
+    assert(a[].equal([6, 7, 8]));
+    a[1 .. 3] *= 5;
+    assert(a[].equal([6, 35, 40]));
+    a[0 .. 2] = 0;
+    assert(a[].equal([0, 0, 40]));
+
+    //Test empty array
+    auto a2 = Array!int.init;
+    ++a2[];
+    ++a2[0 .. 0];
+    a2[] = 0;
+    a2[0 .. 0] = 0;
+    a2[] += 0;
+    a2[0 .. 0] += 0;
+
+    //Test "range-wide" operations
+    auto r = Array!int([0, 1, 2])[]; //Array.Range
+    r[] += 5;
+    assert(r.equal([5, 6, 7]));
+    ++r[];
+    assert(r.equal([6, 7, 8]));
+    r[1 .. 3] *= 5;
+    assert(r.equal([6, 35, 40]));
+    r[0 .. 2] = 0;
+    assert(r.equal([0, 0, 40]));
+
+    //Test empty Range
+    auto r2 = Array!int.init[];
+    ++r2[];
+    ++r2[0 .. 0];
+    r2[] = 0;
+    r2[0 .. 0] = 0;
+    r2[] += 0;
+    r2[0 .. 0] += 0;
+}
+
+// Test issue 11194
+@system unittest
+{
+    static struct S {
+        int i = 1337;
+        void* p;
+        this(this) { assert(i == 1337); }
+        ~this() { assert(i == 1337); }
+    }
+    Array!S arr;
+    S s;
+    arr ~= s;
+    arr ~= s;
+}
+
+@safe unittest //11459
+{
+    static struct S
+    {
+        bool b;
+        alias b this;
+    }
+    alias A = Array!S;
+    alias B = Array!(shared bool);
+}
+
+@system unittest //11884
+{
+    import std.algorithm.iteration : filter;
+    auto a = Array!int([1, 2, 2].filter!"true"());
+}
+
+@safe unittest //8282
+{
+    auto arr = new Array!int;
+}
+
+@system unittest //6998
+{
+    static int i = 0;
+    class C
+    {
+        int dummy = 1;
+        this(){++i;}
+        ~this(){--i;}
+    }
+
+    assert(i == 0);
+    auto c = new C();
+    assert(i == 1);
+
+    //scope
+    {
+        auto arr = Array!C(c);
+        assert(i == 1);
+    }
+    //Array should not have destroyed the class instance
+    assert(i == 1);
+
+    //Just to make sure the GC doesn't collect before the above test.
+    assert(c.dummy == 1);
+}
+@system unittest //6998-2
+{
+    static class C {int i;}
+    auto c = new C;
+    c.i = 42;
+    Array!C a;
+    a ~= c;
+    a.clear;
+    assert(c.i == 42); //fails
+}
+
+@safe unittest
+{
+    static assert(is(Array!int.Range));
+    static assert(is(Array!int.ConstRange));
+}
+
+@system unittest // const/immutable Array and Ranges
+{
+    static void test(A, R, E, S)()
+    {
+        A a;
+        R r = a[];
+        assert(r.empty);
+        assert(r.length == 0);
+        static assert(is(typeof(r.front) == E));
+        static assert(is(typeof(r.back) == E));
+        static assert(is(typeof(r[0]) == E));
+        static assert(is(typeof(r[]) == S));
+        static assert(is(typeof(r[0 .. 0]) == S));
+    }
+
+    alias A = Array!int;
+
+    test!(A, A.Range, int, A.Range);
+    test!(A, const A.Range, const int, A.ConstRange);
+
+    test!(const A, A.ConstRange, const int, A.ConstRange);
+    test!(const A, const A.ConstRange, const int, A.ConstRange);
+
+    test!(immutable A, A.ImmutableRange, immutable int, A.ImmutableRange);
+    test!(immutable A, const A.ImmutableRange, immutable int, A.ImmutableRange);
+    test!(immutable A, immutable A.ImmutableRange, immutable int,
+        A.ImmutableRange);
+}
+
+// ensure @nogc
+@nogc @system unittest
+{
+    Array!int ai;
+    ai ~= 1;
+    assert(ai.front == 1);
+
+    ai.reserve(10);
+    assert(ai.capacity == 10);
+
+    static immutable arr = [1, 2, 3];
+    ai.insertBack(arr);
+}
+
+
+////////////////////////////////////////////////////////////////////////////////
+// Array!bool
+////////////////////////////////////////////////////////////////////////////////
+
+/**
+ * _Array specialized for `bool`. Packs together values efficiently by
+ * allocating one bit per element.
+ */
+struct Array(T)
+if (is(Unqual!T == bool))
+{
+    import std.exception : enforce;
+    import std.typecons : RefCounted, RefCountedAutoInitialize;
+
+    static immutable uint bitsPerWord = size_t.sizeof * 8;
+    private static struct Data
+    {
+        Array!size_t.Payload _backend;
+        size_t _length;
+    }
+    private RefCounted!(Data, RefCountedAutoInitialize.no) _store;
+
+    private @property ref size_t[] data()
+    {
+        assert(_store.refCountedStore.isInitialized);
+        return _store._backend._payload;
+    }
+
+    /**
+     * Defines the array's primary range.
+     */
+    struct Range
+    {
+        private Array _outer;
+        private size_t _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, "Attempting to access the front of an empty Array");
+            return _outer[_a];
+        }
+        /// Ditto
+        @property void front(bool value)
+        {
+            enforce(!empty, "Attempting to set the front of an empty Array");
+            _outer[_a] = value;
+        }
+        /// Ditto
+        T moveFront()
+        {
+            enforce(!empty, "Attempting to move the front of an empty Array");
+            return _outer.moveAt(_a);
+        }
+        /// Ditto
+        void popFront()
+        {
+            enforce(!empty, "Attempting to popFront an empty Array");
+            ++_a;
+        }
+        /// Ditto
+        @property T back()
+        {
+            enforce(!empty, "Attempting to access the back of an empty Array");
+            return _outer[_b - 1];
+        }
+        /// Ditto
+        @property void back(bool value)
+        {
+            enforce(!empty, "Attempting to set the back of an empty Array");
+            _outer[_b - 1] = value;
+        }
+        /// Ditto
+        T moveBack()
+        {
+            enforce(!empty, "Attempting to move the back of an empty Array");
+            return _outer.moveAt(_b - 1);
+        }
+        /// Ditto
+        void popBack()
+        {
+            enforce(!empty, "Attempting to popBack an empty Array");
+            --_b;
+        }
+        /// Ditto
+        T opIndex(size_t i)
+        {
+            return _outer[_a + i];
+        }
+        /// Ditto
+        void opIndexAssign(T value, size_t i)
+        {
+            _outer[_a + i] = value;
+        }
+        /// Ditto
+        T moveAt(size_t i)
+        {
+            return _outer.moveAt(_a + i);
+        }
+        /// Ditto
+        @property size_t length() const
+        {
+            assert(_a <= _b);
+            return _b - _a;
+        }
+        alias opDollar = length;
+        /// ditto
+        Range opSlice(size_t low, size_t high)
+        {
+            assert(
+                _a <= low && low <= high && high <= _b,
+                "Using out of bounds indexes on an Array"
+            );
+            return Range(_outer, _a + low, _a + high);
+        }
+    }
+
+    /**
+     * Property returning `true` if and only if the array has
+     * no elements.
+     *
+     * Complexity: $(BIGOH 1)
+     */
+    @property bool empty()
+    {
+        return !length;
+    }
+
+    /**
+     * Returns: A duplicate of the array.
+     *
+     * Complexity: $(BIGOH length).
+     */
+    @property Array dup()
+    {
+        Array result;
+        result.insertBack(this[]);
+        return result;
+    }
+
+    /**
+     * Returns the number of elements in the array.
+     *
+     * Complexity: $(BIGOH 1).
+     */
+    @property size_t length() const
+    {
+        return _store.refCountedStore.isInitialized ? _store._length : 0;
+    }
+    size_t opDollar() const
+    {
+        return length;
+    }
+
+    /**
+     * Returns: The maximum number of elements the array can store without
+     * reallocating memory and invalidating iterators upon insertion.
+     *
+     * Complexity: $(BIGOH 1).
+     */
+    @property size_t capacity()
+    {
+        return _store.refCountedStore.isInitialized
+            ? cast(size_t) bitsPerWord * _store._backend.capacity
+            : 0;
+    }
+
+    /**
+     * Ensures sufficient capacity to accommodate `e` _elements.
+     * If `e < capacity`, this method does nothing.
+     *
+     * Postcondition: `capacity >= e`
+     *
+     * Note: If the capacity is increased, one should assume that all
+     * iterators to the elements are invalidated.
+     *
+     * Complexity: at most $(BIGOH length) if `e > capacity`, otherwise $(BIGOH 1).
+     */
+    void reserve(size_t e)
+    {
+        import std.conv : to;
+        _store.refCountedStore.ensureInitialized();
+        _store._backend.reserve(to!size_t((e + bitsPerWord - 1) / bitsPerWord));
+    }
+
+    /**
+     * Returns: A range that iterates over all elements of the array in forward order.
+     *
+     * Complexity: $(BIGOH 1)
+     */
+    Range opSlice()
+    {
+        return Range(this, 0, length);
+    }
+
+
+    /**
+     * Returns: A range that iterates the array between two specified positions.
+     *
+     * Complexity: $(BIGOH 1)
+     */
+    Range opSlice(size_t a, size_t b)
+    {
+        enforce(a <= b && b <= length);
+        return Range(this, a, b);
+    }
+
+    /**
+     * Returns: The first element of the array.
+     *
+     * Precondition: `empty == false`
+     *
+     * Complexity: $(BIGOH 1)
+     *
+     * Throws: `Exception` if the array is empty.
+     */
+    @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;
+    }
+
+    /**
+     * Returns: The last element of the array.
+     *
+     * Precondition: `empty == false`
+     *
+     * Complexity: $(BIGOH 1)
+     *
+     * Throws: `Exception` if the array is empty.
+     */
+    @property bool back()
+    {
+        enforce(!empty);
+        return cast(bool)(data.back & (cast(size_t) 1 << ((_store._length - 1) % bitsPerWord)));
+    }
+
+    /// Ditto
+    @property void back(bool value)
+    {
+        enforce(!empty);
+        if (value)
+        {
+            data.back |= (cast(size_t) 1 << ((_store._length - 1) % bitsPerWord));
+        }
+        else
+        {
+            data.back &=
+                ~(cast(size_t) 1 << ((_store._length - 1) % bitsPerWord));
+        }
+    }
+
+    /**
+     * Indexing operators yielding or modifyng the value at the specified index.
+     *
+     * Precondition: `i < length`
+     *
+     * Complexity: $(BIGOH 1)
+     */
+    bool opIndex(size_t i)
+    {
+        auto div = cast(size_t) (i / bitsPerWord);
+        auto rem = i % bitsPerWord;
+        enforce(div < data.length);
+        return cast(bool)(data.ptr[div] & (cast(size_t) 1 << rem));
+    }
+
+    /// ditto
+    void opIndexAssign(bool value, size_t i)
+    {
+        auto div = cast(size_t) (i / bitsPerWord);
+        auto rem = i % bitsPerWord;
+        enforce(div < data.length);
+        if (value) data.ptr[div] |= (cast(size_t) 1 << rem);
+        else data.ptr[div] &= ~(cast(size_t) 1 << rem);
+    }
+
+    /// ditto
+    void opIndexOpAssign(string op)(bool value, size_t i)
+    {
+        auto div = cast(size_t) (i / bitsPerWord);
+        auto rem = i % bitsPerWord;
+        enforce(div < data.length);
+        auto oldValue = cast(bool) (data.ptr[div] & (cast(size_t) 1 << rem));
+        // Do the deed
+        auto newValue = mixin("oldValue "~op~" value");
+        // Write back the value
+        if (newValue != oldValue)
+        {
+            if (newValue) data.ptr[div] |= (cast(size_t) 1 << rem);
+            else data.ptr[div] &= ~(cast(size_t) 1 << rem);
+        }
+    }
+
+    /// Ditto
+    T moveAt(size_t i)
+    {
+        return this[i];
+    }
+
+    /**
+     * Returns: A new array which is a concatenation of `this` and its argument.
+     *
+     * Complexity:
+     * $(BIGOH length + m), where `m` is the number of elements in `stuff`.
+     */
+    Array!bool opBinary(string op, Stuff)(Stuff rhs)
+    if (op == "~")
+    {
+        Array!bool result;
+
+        static if (hasLength!Stuff)
+            result.reserve(length + rhs.length);
+        else static if (is(typeof(rhs[])) && hasLength!(typeof(rhs[])))
+            result.reserve(length + rhs[].length);
+        else static if (isImplicitlyConvertible!(Stuff, bool))
+            result.reserve(length + 1);
+
+        result.insertBack(this[]);
+        result ~= rhs;
+        return result;
+    }
+
+    /**
+     * Forwards to `insertBack`.
+     */
+    Array!bool opOpAssign(string op, Stuff)(Stuff stuff)
+    if (op == "~")
+    {
+        static if (is(typeof(stuff[]))) insertBack(stuff[]);
+        else insertBack(stuff);
+        return this;
+    }
+
+    /**
+     * Removes all the elements from the array and releases allocated memory.
+     *
+     * Postcondition: `empty == true && capacity == 0`
+     *
+     * Complexity: $(BIGOH length)
+     */
+    void clear()
+    {
+        this = Array();
+    }
+
+    /**
+     * Sets the number of elements in the array to `newLength`. If `newLength`
+     * is greater than `length`, the new elements are added to the end of the
+     * array and initialized with `false`.
+     *
+     * Complexity:
+     * Guaranteed $(BIGOH abs(length - newLength)) if `capacity >= newLength`.
+     * If `capacity < newLength` the worst case is $(BIGOH newLength).
+     *
+     * Postcondition: `length == newLength`
+     */
+    @property void length(size_t newLength)
+    {
+        import std.conv : to;
+        _store.refCountedStore.ensureInitialized();
+        auto newDataLength =
+            to!size_t((newLength + bitsPerWord - 1) / bitsPerWord);
+        _store._backend.length = newDataLength;
+        _store._length = newLength;
+    }
+
+    /**
+     * Removes the last element from the array and returns it.
+     * Both stable and non-stable versions behave the same and guarantee
+     * that ranges iterating over the array are never invalidated.
+     *
+     * Precondition: `empty == false`
+     *
+     * Returns: The element removed.
+     *
+     * Complexity: $(BIGOH 1).
+     *
+     * Throws: `Exception` if the array is empty.
+     */
+    T removeAny()
+    {
+        auto result = back;
+        removeBack();
+        return result;
+    }
+
+    /// ditto
+    alias stableRemoveAny = removeAny;
+
+    /**
+     * Inserts the specified elements at the back of the array. `stuff` can be
+     * a value convertible to `bool` or a range of objects convertible to `bool`.
+     *
+     * Returns: The number of elements inserted.
+     *
+     * Complexity:
+     * $(BIGOH length + m) if reallocation takes place, otherwise $(BIGOH m),
+     * where `m` is the number of elements in `stuff`.
+     */
+    size_t insertBack(Stuff)(Stuff stuff)
+    if (is(Stuff : bool))
+    {
+        _store.refCountedStore.ensureInitialized();
+        auto rem = _store._length % bitsPerWord;
+        if (rem)
+        {
+            // Fits within the current array
+            if (stuff)
+            {
+                data[$ - 1] |= (cast(size_t) 1 << rem);
+            }
+            else
+            {
+                data[$ - 1] &= ~(cast(size_t) 1 << rem);
+            }
+        }
+        else
+        {
+            // Need to add more data
+            _store._backend.insertBack(stuff);
+        }
+        ++_store._length;
+        return 1;
+    }
+
+    /// ditto
+    size_t insertBack(Stuff)(Stuff stuff)
+    if (isInputRange!Stuff && is(ElementType!Stuff : bool))
+    {
+        static if (!hasLength!Stuff) size_t 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 stableInsertBack = insertBack;
+
+    /// ditto
+    alias insert = insertBack;
+
+    /// ditto
+    alias stableInsert = insertBack;
+
+    /// ditto
+    alias linearInsert = insertBack;
+
+    /// ditto
+    alias stableLinearInsert = insertBack;
+
+    /**
+     * Removes the value from the back of the array. Both stable and non-stable
+     * versions behave the same and guarantee that ranges iterating over the
+     * array are never invalidated.
+     *
+     * Precondition: `empty == false`
+     *
+     * Complexity: $(BIGOH 1).
+     *
+     * Throws: `Exception` if the array is empty.
+     */
+    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 stableRemoveBack = removeBack;
+
+    /**
+     * Removes `howMany` values from the back of the array. Unlike the
+     * unparameterized versions above, these functions do not throw if
+     * they could not remove `howMany` elements. Instead, if `howMany > n`,
+     * all elements are removed. The returned value is the effective number
+     * of elements removed. Both stable and non-stable versions behave the same
+     * and guarantee that ranges iterating over the array are never invalidated.
+     *
+     * Returns: The number of elements removed.
+     *
+     * Complexity: $(BIGOH howMany).
+     */
+    size_t removeBack(size_t howMany)
+    {
+        if (howMany >= length)
+        {
+            howMany = length;
+            clear();
+        }
+        else
+        {
+            length = length - howMany;
+        }
+        return howMany;
+    }
+
+    /// ditto
+    alias stableRemoveBack = removeBack;
+
+    /**
+     * Inserts `stuff` before, after, or instead range `r`, which must
+     * be a valid range previously extracted from this array. `stuff`
+     * can be a value convertible to `bool` or a range of objects convertible
+     * to `bool`. Both stable and non-stable version behave the same and
+     * guarantee that ranges iterating over the array are never invalidated.
+     *
+     * Returns: The number of values inserted.
+     *
+     * Complexity: $(BIGOH length + m), where `m` is the length of `stuff`.
+     */
+    size_t insertBefore(Stuff)(Range r, Stuff stuff)
+    {
+        import std.algorithm.mutation : bringToFront;
+        // 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 stableInsertBefore = insertBefore;
+
+    /// ditto
+    size_t insertAfter(Stuff)(Range r, Stuff stuff)
+    {
+        import std.algorithm.mutation : bringToFront;
+        // 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 stableInsertAfter = insertAfter;
+
+    /// 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 stableReplace = replace;
+
+    /**
+     * Removes all elements belonging to `r`, which must be a range
+     * obtained originally from this array.
+     *
+     * Returns: A range spanning the remaining elements in the array that
+     * initially were right after `r`.
+     *
+     * Complexity: $(BIGOH length)
+     */
+    Range linearRemove(Range r)
+    {
+        import std.algorithm.mutation : copy;
+        copy(this[r._b .. length], this[r._a .. length]);
+        length = length - r.length;
+        return this[r._a .. length];
+    }
+}
+
+@system unittest
+{
+    Array!bool a;
+    assert(a.empty);
+}
+
+@system unittest
+{
+    Array!bool arr;
+    arr.insert([false, false, false, false]);
+    assert(arr.front == false);
+    assert(arr.back == false);
+    assert(arr[1] == false);
+    auto slice = arr[];
+    slice = arr[0 .. $];
+    slice = slice[1 .. $];
+    slice.front = true;
+    slice.back = true;
+    slice[1] = true;
+    assert(slice.front == true);
+    assert(slice.back == true);
+    assert(slice[1] == true);
+    assert(slice.moveFront == true);
+    assert(slice.moveBack == true);
+    assert(slice.moveAt(1) == true);
+}
+
+// issue 16331 - uncomparable values are valid values for an array
+@system unittest
+{
+    double[] values = [double.nan, double.nan];
+    auto arr = Array!double(values);
+}
+
+@nogc @system unittest
+{
+    auto a = Array!int(0, 1, 2);
+    int[3] b = [3, 4, 5];
+    short[3] ci = [0, 1, 0];
+    auto c = Array!short(ci);
+    assert(Array!int(0, 1, 2, 0, 1, 2) == a ~ a);
+    assert(Array!int(0, 1, 2, 3, 4, 5) == a ~ b);
+    assert(Array!int(0, 1, 2, 3) == a ~ 3);
+    assert(Array!int(0, 1, 2, 0, 1, 0) == a ~ c);
+}
+
+@nogc @system unittest
+{
+    auto a = Array!char('a', 'b');
+    assert(Array!char("abc") == a ~ 'c');
+    import std.utf : byCodeUnit;
+    assert(Array!char("abcd") == a ~ "cd".byCodeUnit);
+}
+
+@nogc @system unittest
+{
+    auto a = Array!dchar("ąćę"d);
+    assert(Array!dchar("ąćęϢϖ"d) == a ~ "Ϣϖ"d);
+    wchar x = 'Ϣ';
+    assert(Array!dchar("ąćęϢz"d) == a ~ x ~ 'z');
+}
+
+@system unittest
+{
+    Array!bool a;
+    assert(a.empty);
+    a.insertBack(false);
+    assert(!a.empty);
+}
+
+@system unittest
+{
+    Array!bool a;
+    assert(a.empty);
+    auto b = a.dup;
+    assert(b.empty);
+    a.insertBack(true);
+    assert(b.empty);
+}
+
+@system unittest
+{
+    import std.conv : to;
+    Array!bool a;
+    assert(a.length == 0);
+    a.insert(true);
+    assert(a.length == 1, to!string(a.length));
+}
+
+@system unittest
+{
+    import std.conv : to;
+    Array!bool a;
+    assert(a.capacity == 0);
+    foreach (i; 0 .. 100)
+    {
+        a.insert(true);
+        assert(a.capacity >= a.length, to!string(a.capacity));
+    }
+}
+
+@system unittest
+{
+    Array!bool a;
+    assert(a.capacity == 0);
+    a.reserve(15657);
+    assert(a.capacity >= 15657);
+    a.reserve(100);
+    assert(a.capacity >= 15657);
+}
+
+@system unittest
+{
+    Array!bool a;
+    a.insertBack([true, false, true, true]);
+    assert(a[0 .. 2].length == 2);
+}
+
+@system unittest
+{
+    Array!bool a;
+    a.insertBack([true, false, true, true]);
+    assert(a[].length == 4);
+}
+
+@system unittest
+{
+    Array!bool a;
+    a.insertBack([true, false, true, true]);
+    assert(a.front);
+    a.front = false;
+    assert(!a.front);
+}
+
+@system unittest
+{
+    Array!bool a;
+    a.insertBack([true, false, true, true]);
+    assert(a[].length == 4);
+}
+
+@system unittest
+{
+    Array!bool a;
+    a.insertBack([true, false, true, true]);
+    assert(a.back);
+    a.back = false;
+    assert(!a.back);
+}
+
+@system unittest
+{
+    Array!bool a;
+    a.insertBack([true, false, true, true]);
+    assert(a[0] && !a[1]);
+    a[0] &= a[1];
+    assert(!a[0]);
+}
+
+@system unittest
+{
+    import std.algorithm.comparison : equal;
+    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]));
+    assert((a ~ [true, false])[].equal([true, false, true, true, true, false]));
+    Array!bool c;
+    c.insertBack(true);
+    assert((c ~ false)[].equal([true, false]));
+}
+@system unittest
+{
+    import std.algorithm.comparison : equal;
+    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]));
+}
+
+@system unittest
+{
+    Array!bool a;
+    a.insertBack([true, false, true, true]);
+    a.clear();
+    assert(a.capacity == 0);
+}
+
+@system unittest
+{
+    Array!bool a;
+    a.length = 1057;
+    assert(a.length == 1057);
+    assert(a.capacity >= a.length);
+    foreach (e; a)
+    {
+        assert(!e);
+    }
+    immutable cap = a.capacity;
+    a.length = 100;
+    assert(a.length == 100);
+    // do not realloc if length decreases
+    assert(a.capacity == cap);
+}
+
+@system unittest
+{
+    Array!bool a;
+    a.length = 1057;
+    assert(!a.removeAny());
+    assert(a.length == 1056);
+    foreach (e; a)
+    {
+        assert(!e);
+    }
+}
+
+@system unittest
+{
+    Array!bool a;
+    for (int i = 0; i < 100; ++i)
+        a.insertBack(true);
+    foreach (e; a)
+        assert(e);
+}
+
+@system unittest
+{
+    Array!bool a;
+    a.length = 1057;
+    assert(a.removeBack(1000) == 1000);
+    assert(a.length == 57);
+    foreach (e; a)
+    {
+        assert(!e);
+    }
+}
+
+@system unittest
+{
+    import std.conv : to;
+    Array!bool a;
+    version (bugxxxx)
+    {
+        a._store.refCountedDebug = true;
+    }
+    a.insertBefore(a[], true);
+    assert(a.length == 1, to!string(a.length));
+    a.insertBefore(a[], false);
+    assert(a.length == 2, to!string(a.length));
+    a.insertBefore(a[1 .. $], true);
+    import std.algorithm.comparison : equal;
+    assert(a[].equal([false, true, true]));
+}
+
+@system unittest
+{
+    import std.conv : to;
+    Array!bool a;
+    a.length = 10;
+    a.insertAfter(a[0 .. 5], true);
+    assert(a.length == 11, to!string(a.length));
+    assert(a[5]);
+}
+@system unittest
+{
+    alias V3 = int[3];
+    V3 v = [1, 2, 3];
+    Array!V3 arr;
+    arr ~= v;
+    assert(arr[0] == [1, 2, 3]);
+}
+@system unittest
+{
+    alias V3 = int[3];
+    V3[2] v = [[1, 2, 3], [4, 5, 6]];
+    Array!V3 arr;
+    arr ~= v;
+    assert(arr[0] == [1, 2, 3]);
+    assert(arr[1] == [4, 5, 6]);
+}
diff --git a/libphobos/src/std/container/binaryheap.d b/libphobos/src/std/container/binaryheap.d
new file mode 100644
index 0000000..4adf604
--- /dev/null
+++ b/libphobos/src/std/container/binaryheap.d
@@ -0,0 +1,595 @@
+/**
+This module provides a $(D BinaryHeap) (aka priority queue)
+adaptor that makes a binary heap out of any user-provided random-access range.
+
+This module is a submodule of $(MREF std, container).
+
+Source: $(PHOBOSSRC std/container/_binaryheap.d)
+
+Copyright: 2010- Andrei Alexandrescu. All rights reserved by the respective holders.
+
+License: Distributed under the Boost Software License, Version 1.0.
+(See accompanying file LICENSE_1_0.txt or copy at $(HTTP
+boost.org/LICENSE_1_0.txt)).
+
+Authors: $(HTTP erdani.com, Andrei Alexandrescu)
+*/
+module std.container.binaryheap;
+
+import std.range.primitives;
+import std.traits;
+
+public import std.container.util;
+
+///
+@system unittest
+{
+    import std.algorithm.comparison : equal;
+    import std.range : take;
+    auto maxHeap = heapify([4, 7, 3, 1, 5]);
+    assert(maxHeap.take(3).equal([7, 5, 4]));
+
+    auto minHeap = heapify!"a > b"([4, 7, 3, 1, 5]);
+    assert(minHeap.take(3).equal([1, 3, 4]));
+}
+
+// BinaryHeap
+/**
+Implements a $(HTTP 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.
+
+The binary heap induces structure over the underlying store such that
+accessing the largest element (by using the $(D front) property) is a
+$(BIGOH 1) operation and extracting it (by using the $(D
+removeFront()) method) is done fast in $(BIGOH log n) time.
+
+If $(D less) is the less-than operator, which is the default option,
+then $(D BinaryHeap) defines a so-called max-heap that optimizes
+extraction of the $(I largest) elements. To define a min-heap,
+instantiate BinaryHeap with $(D "a > b") as its predicate.
+
+Simply extracting elements from a $(D BinaryHeap) container is
+tantamount to lazily fetching elements of $(D Store) in descending
+order. Extracting elements from the $(D BinaryHeap) to completion
+leaves the underlying store sorted in ascending order but, again,
+yields elements in descending order.
+
+If $(D Store) is a range, the $(D BinaryHeap) cannot grow beyond the
+size of that range. If $(D Store) is a container that supports $(D
+insertBack), the $(D BinaryHeap) may grow by adding elements to the
+container.
+     */
+struct BinaryHeap(Store, alias less = "a < b")
+if (isRandomAccessRange!(Store) || isRandomAccessRange!(typeof(Store.init[])))
+{
+    import std.algorithm.comparison : min;
+    import std.algorithm.mutation : move, swapAt;
+    import std.algorithm.sorting : HeapOps;
+    import std.exception : enforce;
+    import std.functional : binaryFun;
+    import std.typecons : RefCounted, RefCountedAutoInitialize;
+
+    static if (isRandomAccessRange!Store)
+        alias Range = Store;
+    else
+        alias Range = typeof(Store.init[]);
+    alias percolate = HeapOps!(less, Range).percolate;
+    alias buildHeap = HeapOps!(less, Range).buildHeap;
+
+// Really weird @@BUG@@: if you comment out the "private:" label below,
+// std.algorithm can't unittest anymore
+//private:
+
+    // The payload includes the support store and the effective length
+    private static struct Data
+    {
+        Store _store;
+        size_t _length;
+    }
+    private RefCounted!(Data, RefCountedAutoInitialize.no) _payload;
+    // Comparison predicate
+    private alias comp = binaryFun!(less);
+    // Convenience accessors
+    private @property ref Store _store()
+    {
+        assert(_payload.refCountedStore.isInitialized);
+        return _payload._store;
+    }
+    private @property ref size_t _length()
+    {
+        assert(_payload.refCountedStore.isInitialized);
+        return _payload._length;
+    }
+
+    // Asserts that the heap property is respected.
+    private void assertValid()
+    {
+        debug
+        {
+            import std.conv : to;
+            if (!_payload.refCountedStore.isInitialized) return;
+            if (_length < 2) return;
+            for (size_t n = _length - 1; n >= 1; --n)
+            {
+                auto parentIdx = (n - 1) / 2;
+                assert(!comp(_store[parentIdx], _store[n]), to!string(n));
+            }
+        }
+    }
+
+    // @@@BUG@@@: add private here, std.algorithm doesn't unittest anymore
+    /*private*/ void pop(Store store)
+    {
+        assert(!store.empty, "Cannot pop an empty store.");
+        if (store.length == 1) return;
+        auto t1 = store[].moveFront();
+        auto t2 = store[].moveBack();
+        store.front = move(t2);
+        store.back = move(t1);
+        percolate(store[], 0, store.length - 1);
+    }
+
+public:
+
+    /**
+       Converts the store $(D s) into a heap. If $(D initialSize) is
+       specified, only the first $(D initialSize) elements in $(D s)
+       are transformed into a heap, after which the heap can grow up
+       to $(D r.length) (if $(D Store) is a range) or indefinitely (if
+       $(D Store) is a container with $(D insertBack)). Performs
+       $(BIGOH min(r.length, initialSize)) evaluations of $(D less).
+     */
+    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)
+    {
+        _payload.refCountedStore.ensureInitialized();
+        _store = move(s);
+        _length = min(_store.length, initialSize);
+        if (_length < 2) return;
+        buildHeap(_store[]);
+        assertValid();
+    }
+
+/**
+Takes ownership of a store assuming it already was organized as a
+heap.
+     */
+    void assume(Store s, size_t initialSize = size_t.max)
+    {
+        _payload.refCountedStore.ensureInitialized();
+        _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 $(LINK2 https://en.wikipedia.org/wiki/Heap_(data_structure),
+heap property).
+     */
+    auto release()
+    {
+        if (!_payload.refCountedStore.isInitialized)
+        {
+            return typeof(_store[0 .. _length]).init;
+        }
+        assertValid();
+        auto result = _store[0 .. _length];
+        _payload = _payload.init;
+        return result;
+    }
+
+/**
+Returns $(D true) if the heap is _empty, $(D false) otherwise.
+     */
+    @property bool empty()
+    {
+        return !length;
+    }
+
+/**
+Returns a duplicate of the heap. The $(D dup) method is available only if the
+underlying store supports it.
+     */
+    static if (is(typeof((Store s) { return s.dup; }(Store.init)) == Store))
+    {
+        @property BinaryHeap dup()
+        {
+            BinaryHeap result;
+            if (!_payload.refCountedStore.isInitialized) return result;
+            result.assume(_store.dup, length);
+            return result;
+        }
+    }
+
+/**
+Returns the _length of the heap.
+     */
+    @property size_t length()
+    {
+        return _payload.refCountedStore.isInitialized ? _length : 0;
+    }
+
+/**
+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()
+    {
+        if (!_payload.refCountedStore.isInitialized) return 0;
+        static if (is(typeof(_store.capacity) : size_t))
+        {
+            return _store.capacity;
+        }
+        else
+        {
+            return _store.length;
+        }
+    }
+
+/**
+Returns a copy of the _front of the heap, which is the largest element
+according to $(D less).
+     */
+    @property ElementType!Store front()
+    {
+        enforce(!empty, "Cannot call front on an empty heap.");
+        return _store.front;
+    }
+
+/**
+Clears the heap by detaching it from the underlying store.
+     */
+    void clear()
+    {
+        _payload = _payload.init;
+    }
+
+/**
+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(typeof(_store.insertBack(value))))
+        {
+            _payload.refCountedStore.ensureInitialized();
+            if (length == _store.length)
+            {
+                // reallocate
+                _store.insertBack(value);
+            }
+            else
+            {
+                // no reallocation
+                _store[_length] = value;
+            }
+        }
+        else
+        {
+            import std.traits : isDynamicArray;
+            static if (isDynamicArray!Store)
+            {
+                if (length == _store.length)
+                    _store.length = (length < 6 ? 8 : length * 3 / 2);
+                _store[_length] = value;
+            }
+            else
+            {
+                // can't grow
+                enforce(length < _store.length,
+                        "Cannot grow a heap created over a range");
+            }
+        }
+
+        // sink down the element
+        for (size_t n = _length; n; )
+        {
+            auto parentIdx = (n - 1) / 2;
+            if (!comp(_store[parentIdx], _store[n])) break; // done!
+            // must swap and continue
+            _store.swapAt(parentIdx, n);
+            n = parentIdx;
+        }
+        ++_length;
+        debug(BinaryHeap) assertValid();
+        return 1;
+    }
+
+/**
+Removes the largest element from the heap.
+     */
+    void removeFront()
+    {
+        enforce(!empty, "Cannot call removeFront on an empty heap.");
+        if (_length > 1)
+        {
+            auto t1 = _store[].moveFront();
+            auto t2 = _store[].moveAt(_length - 1);
+            _store.front = move(t2);
+            _store[_length - 1] = move(t1);
+        }
+        --_length;
+        percolate(_store[], 0, _length);
+    }
+
+    /// ditto
+    alias popFront = removeFront;
+
+/**
+Removes the largest element from the heap and returns a copy of
+it. The element still resides in the heap's store. For performance
+reasons you may want to use $(D removeFront) with heaps of objects
+that are expensive to copy.
+     */
+    ElementType!Store removeAny()
+    {
+        removeFront();
+        return _store[_length];
+    }
+
+/**
+Replaces the largest element in the store with $(D value).
+     */
+    void replaceFront(ElementType!Store value)
+    {
+        // must replace the top
+        assert(!empty, "Cannot call replaceFront on an empty heap.");
+        _store.front = value;
+        percolate(_store[], 0, _length);
+        debug(BinaryHeap) assertValid();
+    }
+
+/**
+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)
+    {
+        _payload.refCountedStore.ensureInitialized();
+        if (_length < _store.length)
+        {
+            insert(value);
+            return true;
+        }
+
+        assert(!_store.empty, "Cannot replace front of an empty heap.");
+        if (!comp(value, _store.front)) return false; // value >= largest
+        _store.front = value;
+
+        percolate(_store[], 0, _length);
+        debug(BinaryHeap) assertValid();
+        return true;
+    }
+
+/**
+Swapping is allowed if the heap is full. If $(D less(value, front)), the
+method exchanges store.front and value and returns $(D true). Otherwise, it
+leaves the heap unaffected and returns $(D false).
+     */
+    bool conditionalSwap(ref ElementType!Store value)
+    {
+        _payload.refCountedStore.ensureInitialized();
+        assert(_length == _store.length);
+        assert(!_store.empty, "Cannot swap front of an empty heap.");
+
+        if (!comp(value, _store.front)) return false; // value >= largest
+
+        import std.algorithm.mutation : swap;
+        swap(_store.front, value);
+
+        percolate(_store[], 0, _length);
+        debug(BinaryHeap) assertValid();
+
+        return true;
+    }
+}
+
+/// Example from "Introduction to Algorithms" Cormen et al, p 146
+@system unittest
+{
+    import std.algorithm.comparison : equal;
+    int[] a = [ 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 ];
+    auto h = heapify(a);
+    // largest element
+    assert(h.front == 16);
+    // a has the heap property
+    assert(equal(a, [ 16, 14, 10, 8, 7, 9, 3, 2, 4, 1 ]));
+}
+
+/// $(D BinaryHeap) implements the standard input range interface, allowing
+/// lazy iteration of the underlying range in descending order.
+@system unittest
+{
+    import std.algorithm.comparison : equal;
+    import std.range : take;
+    int[] a = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7];
+    auto top5 = heapify(a).take(5);
+    assert(top5.equal([16, 14, 10, 9, 8]));
+}
+
+/**
+Convenience function that returns a $(D BinaryHeap!Store) object
+initialized with $(D s) and $(D initialSize).
+ */
+BinaryHeap!(Store, less) heapify(alias less = "a < b", Store)(Store s,
+        size_t initialSize = size_t.max)
+{
+
+    return BinaryHeap!(Store, less)(s, initialSize);
+}
+
+///
+@system unittest
+{
+    import std.conv : to;
+    import std.range.primitives;
+    {
+        // example from "Introduction to Algorithms" Cormen et al., p 146
+        int[] a = [ 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 ];
+        auto h = heapify(a);
+        h = heapify!"a < b"(a);
+        assert(h.front == 16);
+        assert(a == [ 16, 14, 10, 8, 7, 9, 3, 2, 4, 1 ]);
+        auto witness = [ 16, 14, 10, 9, 8, 7, 4, 3, 2, 1 ];
+        for (; !h.empty; h.removeFront(), witness.popFront())
+        {
+            assert(!witness.empty);
+            assert(witness.front == h.front);
+        }
+        assert(witness.empty);
+    }
+    {
+        int[] a = [ 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 ];
+        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 ], to!string(b));
+    }
+}
+
+@system unittest
+{
+    // Test range interface.
+    import std.algorithm.comparison : equal;
+    int[] a = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7];
+    auto h = heapify(a);
+    static assert(isInputRange!(typeof(h)));
+    assert(h.equal([16, 14, 10, 9, 8, 7, 4, 3, 2, 1]));
+}
+
+@system unittest // 15675
+{
+    import std.container.array : Array;
+
+    Array!int elements = [1, 2, 10, 12];
+    auto heap = heapify(elements);
+    assert(heap.front == 12);
+}
+
+@system unittest // 16072
+{
+    auto q = heapify!"a > b"([2, 4, 5]);
+    q.insert(1);
+    q.insert(6);
+    assert(q.front == 1);
+
+    // test more multiple grows
+    int[] arr;
+    auto r = heapify!"a < b"(arr);
+    foreach (i; 0 .. 100)
+        r.insert(i);
+
+    assert(r.front == 99);
+}
+
+@system unittest
+{
+    import std.algorithm.comparison : equal;
+    int[] a = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7];
+    auto heap = heapify(a);
+    auto dup = heap.dup();
+    assert(dup.equal([16, 14, 10, 9, 8, 7, 4, 3, 2, 1]));
+}
+
+@safe unittest
+{
+    static struct StructWithoutDup
+    {
+        int[] a;
+        @disable StructWithoutDup dup()
+        {
+            StructWithoutDup d;
+            return d;
+        }
+        alias a this;
+    }
+
+    // Assert Binary heap can be created when Store doesn't have dup
+    // if dup is not used.
+    assert(__traits(compiles, ()
+        {
+            auto s = StructWithoutDup([1,2]);
+            auto h = heapify(s);
+        }));
+
+    // Assert dup can't be used on BinaryHeaps when Store doesn't have dup
+    assert(!__traits(compiles, ()
+        {
+            auto s = StructWithoutDup([1,2]);
+            auto h = heapify(s);
+            h.dup();
+        }));
+}
+
+@safe unittest
+{
+    static struct StructWithDup
+    {
+        int[] a;
+        StructWithDup dup()
+        {
+            StructWithDup d;
+            return d;
+        }
+        alias a this;
+    }
+
+    // Assert dup can be used on BinaryHeaps when Store has dup
+    assert(__traits(compiles, ()
+        {
+            auto s = StructWithDup([1, 2]);
+            auto h = heapify(s);
+            h.dup();
+        }));
+}
+
+@system unittest
+{
+    import std.algorithm.comparison : equal;
+    import std.internal.test.dummyrange;
+
+    alias RefRange = DummyRange!(ReturnBy.Reference, Length.Yes, RangeType.Random);
+
+    RefRange a;
+    RefRange b;
+    a.reinit();
+    b.reinit();
+
+    auto heap = heapify(a);
+    foreach (ref elem; b)
+    {
+        heap.conditionalSwap(elem);
+    }
+
+    assert(equal(heap, [ 5, 5, 4, 4, 3, 3, 2, 2, 1, 1]));
+    assert(equal(b, [10, 9, 8, 7, 6, 6, 7, 8, 9, 10]));
+}
+
+@system unittest // Issue 17314
+{
+    import std.algorithm.comparison : equal;
+    int[] a = [5];
+    auto heap = heapify(a);
+    heap.insert(6);
+    assert(equal(heap, [6, 5]));
+}
diff --git a/libphobos/src/std/container/dlist.d b/libphobos/src/std/container/dlist.d
new file mode 100644
index 0000000..633371f
--- /dev/null
+++ b/libphobos/src/std/container/dlist.d
@@ -0,0 +1,1039 @@
+/**
+This module implements a generic doubly-linked list container.
+It can be used as a queue, dequeue or stack.
+
+This module is a submodule of $(MREF std, container).
+
+Source: $(PHOBOSSRC std/container/_dlist.d)
+
+Copyright: 2010- Andrei Alexandrescu. All rights reserved by the respective holders.
+
+License: Distributed under the Boost Software License, Version 1.0.
+(See accompanying file LICENSE_1_0.txt or copy at $(HTTP
+boost.org/LICENSE_1_0.txt)).
+
+Authors: $(HTTP erdani.com, Andrei Alexandrescu)
+
+$(SCRIPT inhibitQuickIndex = 1;)
+*/
+module std.container.dlist;
+
+///
+@safe unittest
+{
+    import std.algorithm.comparison : equal;
+    import std.container : DList;
+
+    auto s = DList!int(1, 2, 3);
+    assert(equal(s[], [1, 2, 3]));
+
+    s.removeFront();
+    assert(equal(s[], [2, 3]));
+    s.removeBack();
+    assert(equal(s[], [2]));
+
+    s.insertFront([4, 5]);
+    assert(equal(s[], [4, 5, 2]));
+    s.insertBack([6, 7]);
+    assert(equal(s[], [4, 5, 2, 6, 7]));
+
+    // If you want to apply range operations, simply slice it.
+    import std.algorithm.searching : countUntil;
+    import std.range : popFrontN, popBackN, walkLength;
+
+    auto sl = DList!int([1, 2, 3, 4, 5]);
+    assert(countUntil(sl[], 2) == 1);
+
+    auto r = sl[];
+    popFrontN(r, 2);
+    popBackN(r, 2);
+    assert(r.equal([3]));
+    assert(walkLength(r) == 1);
+
+    // DList.Range can be used to remove elements from the list it spans
+    auto nl = DList!int([1, 2, 3, 4, 5]);
+    for (auto rn = nl[]; !rn.empty;)
+        if (rn.front % 2 == 0)
+            nl.popFirstOf(rn);
+        else
+            rn.popFront();
+    assert(equal(nl[], [1, 3, 5]));
+    auto rs = nl[];
+    rs.popFront();
+    nl.remove(rs);
+    assert(equal(nl[], [1]));
+}
+
+import std.range.primitives;
+import std.traits;
+
+public import std.container.util;
+
+/+
+A DList Node without payload. Used to handle the sentinel node (henceforth "sentinode").
+
+Also used for parts of the code that don't depend on the payload type.
+ +/
+private struct BaseNode
+{
+    private BaseNode* _prev = null;
+    private BaseNode* _next = null;
+
+    /+
+    Gets the payload associated with this node.
+    This is trusted because all nodes are associated with a payload, even
+    the sentinel node.
+    It is also not possible to mix Nodes in DLists of different types.
+    This function is implemented as a member function here, as UFCS does not
+    work with pointers.
+    +/
+    ref inout(T) getPayload(T)() inout @trusted
+    {
+        return (cast(inout(DList!T.PayNode)*)&this)._payload;
+    }
+
+    // Helper: Given nodes p and n, connects them.
+    static void connect(BaseNode* p, BaseNode* n) @safe nothrow pure
+    {
+        p._next = n;
+        n._prev = p;
+    }
+}
+
+/+
+The base DList Range. Contains Range primitives that don't depend on payload type.
+ +/
+private struct DRange
+{
+    @safe unittest
+    {
+        static assert(isBidirectionalRange!DRange);
+        static assert(is(ElementType!DRange == BaseNode*));
+    }
+
+nothrow @safe pure:
+    private BaseNode* _first;
+    private BaseNode* _last;
+
+    private this(BaseNode* first, BaseNode* last)
+    {
+        assert((first is null) == (last is null), "Dlist.Range.this: Invalid arguments");
+        _first = first;
+        _last = last;
+    }
+    private this(BaseNode* n)
+    {
+        this(n, n);
+    }
+
+    @property
+    bool empty() const
+    {
+        assert((_first is null) == (_last is null), "DList.Range: Invalidated state");
+        return !_first;
+    }
+
+    @property BaseNode* front()
+    {
+        assert(!empty, "DList.Range.front: Range is empty");
+        return _first;
+    }
+
+    void popFront()
+    {
+        assert(!empty, "DList.Range.popFront: Range is empty");
+        if (_first is _last)
+        {
+            _first = _last = null;
+        }
+        else
+        {
+            assert(_first._next && _first is _first._next._prev, "DList.Range: Invalidated state");
+            _first = _first._next;
+        }
+    }
+
+    @property BaseNode* back()
+    {
+        assert(!empty, "DList.Range.front: Range is empty");
+        return _last;
+    }
+
+    void popBack()
+    {
+        assert(!empty, "DList.Range.popBack: Range is empty");
+        if (_first is _last)
+        {
+            _first = _last = null;
+        }
+        else
+        {
+            assert(_last._prev && _last is _last._prev._next, "DList.Range: Invalidated state");
+            _last = _last._prev;
+        }
+    }
+
+    /// Forward range primitive.
+    @property DRange save() { return this; }
+}
+
+/**
+Implements a doubly-linked list.
+
+$(D DList) uses reference semantics.
+ */
+struct DList(T)
+{
+    import std.range : Take;
+
+    /*
+    A Node with a Payload. A PayNode.
+     */
+    struct PayNode
+    {
+        BaseNode _base;
+        alias _base this;
+
+        T _payload = T.init;
+
+        inout(BaseNode)* asBaseNode() inout @trusted
+        {
+            return &_base;
+        }
+    }
+
+    //The sentinel node
+    private BaseNode* _root;
+
+  private
+  {
+    //Construct as new PayNode, and returns it as a BaseNode.
+    static BaseNode* createNode(Stuff)(auto ref Stuff arg, BaseNode* prev = null, BaseNode* next = null)
+    {
+        return (new PayNode(BaseNode(prev, next), arg)).asBaseNode();
+    }
+
+    void initialize() nothrow @safe pure
+    {
+        if (_root) return;
+        //Note: We allocate a PayNode for safety reasons.
+        _root = (new PayNode()).asBaseNode();
+        _root._next = _root._prev = _root;
+    }
+    ref inout(BaseNode*) _first() @property @safe nothrow pure inout
+    {
+        assert(_root);
+        return _root._next;
+    }
+    ref inout(BaseNode*) _last() @property @safe nothrow pure inout
+    {
+        assert(_root);
+        return _root._prev;
+    }
+  } //end private
+
+/**
+Constructor taking a number of nodes
+     */
+    this(U)(U[] values...) if (isImplicitlyConvertible!(U, T))
+    {
+        insertBack(values);
+    }
+
+/**
+Constructor taking an input range
+     */
+    this(Stuff)(Stuff stuff)
+    if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T))
+    {
+        insertBack(stuff);
+    }
+
+/**
+Comparison for equality.
+
+Complexity: $(BIGOH min(n, n1)) where $(D n1) is the number of
+elements in $(D rhs).
+     */
+    bool opEquals()(ref const DList rhs) const
+    if (is(typeof(front == front)))
+    {
+        const lhs = this;
+        const lroot = lhs._root;
+        const rroot = rhs._root;
+
+        if (lroot is rroot) return true;
+        if (lroot is null) return rroot is rroot._next;
+        if (rroot is null) return lroot is lroot._next;
+
+        const(BaseNode)* pl = lhs._first;
+        const(BaseNode)* pr = rhs._first;
+        while (true)
+        {
+            if (pl is lroot) return pr is rroot;
+            if (pr is rroot) return false;
+
+            // !== because of NaN
+            if (!(pl.getPayload!T() == pr.getPayload!T())) return false;
+
+            pl = pl._next;
+            pr = pr._next;
+        }
+    }
+
+    /**
+    Defines the container's primary range, which embodies a bidirectional range.
+     */
+    struct Range
+    {
+        static assert(isBidirectionalRange!Range);
+
+        DRange _base;
+        alias _base this;
+
+        private this(BaseNode* first, BaseNode* last)
+        {
+            _base = DRange(first, last);
+        }
+        private this(BaseNode* n)
+        {
+            this(n, n);
+        }
+
+        @property ref T front()
+        {
+            return _base.front.getPayload!T();
+        }
+
+        @property ref T back()
+        {
+            return _base.back.getPayload!T();
+        }
+
+        //Note: shadows base DRange.save.
+        //Necessary for static covariance.
+        @property Range save() { return this; }
+    }
+
+/**
+Property returning $(D true) if and only if the container has no
+elements.
+
+Complexity: $(BIGOH 1)
+     */
+    bool empty() @property const nothrow
+    {
+        return _root is null || _root is _first;
+    }
+
+/**
+Removes all contents from the $(D DList).
+
+Postcondition: $(D empty)
+
+Complexity: $(BIGOH 1)
+     */
+    void clear()
+    {
+        //remove actual elements.
+        remove(this[]);
+    }
+
+/**
+Duplicates the container. The elements themselves are not transitively
+duplicated.
+
+Complexity: $(BIGOH n).
+     */
+    @property DList dup()
+    {
+        return DList(this[]);
+    }
+
+/**
+Returns a range that iterates over all elements of the container, in
+forward order.
+
+Complexity: $(BIGOH 1)
+     */
+    Range opSlice()
+    {
+        if (empty)
+            return Range(null, null);
+        else
+            return Range(_first, _last);
+    }
+
+/**
+Forward to $(D opSlice().front).
+
+Complexity: $(BIGOH 1)
+     */
+    @property ref inout(T) front() inout
+    {
+        assert(!empty, "DList.front: List is empty");
+        return _first.getPayload!T();
+    }
+
+/**
+Forward to $(D opSlice().back).
+
+Complexity: $(BIGOH 1)
+     */
+    @property ref inout(T) back() inout
+    {
+        assert(!empty, "DList.back: List is empty");
+        return _last.getPayload!T();
+    }
+
+/+ ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ +/
+/+                        BEGIN CONCAT FUNCTIONS HERE                         +/
+/+ ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ +/
+
+/**
+Returns a new $(D DList) that's the concatenation of $(D this) and its
+argument $(D rhs).
+     */
+    DList opBinary(string op, Stuff)(Stuff rhs)
+    if (op == "~" && is(typeof(insertBack(rhs))))
+    {
+        auto ret = this.dup;
+        ret.insertBack(rhs);
+        return ret;
+    }
+
+/**
+Returns a new $(D DList) that's the concatenation of the argument $(D lhs)
+and $(D this).
+     */
+    DList opBinaryRight(string op, Stuff)(Stuff lhs)
+    if (op == "~" && is(typeof(insertFront(lhs))))
+    {
+        auto ret = this.dup;
+        ret.insertFront(lhs);
+        return ret;
+    }
+
+/**
+Appends the contents of the argument $(D rhs) into $(D this).
+     */
+    DList opOpAssign(string op, Stuff)(Stuff rhs)
+    if (op == "~" && is(typeof(insertBack(rhs))))
+    {
+        insertBack(rhs);
+        return this;
+    }
+
+/+ ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ +/
+/+                        BEGIN INSERT FUNCTIONS HERE                         +/
+/+ ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ +/
+
+/**
+Inserts $(D stuff) to the front/back of the container. $(D stuff) can be a
+value convertible to $(D T) or a range of objects convertible to $(D
+T). 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))
+     */
+    size_t insertFront(Stuff)(Stuff stuff)
+    {
+        initialize();
+        return insertAfterNode(_root, stuff);
+    }
+
+    /// ditto
+    size_t insertBack(Stuff)(Stuff stuff)
+    {
+        initialize();
+        return insertBeforeNode(_root, stuff);
+    }
+
+    /// ditto
+    alias insert = insertBack;
+
+    /// ditto
+    alias stableInsert = insert;
+
+    /// ditto
+    alias stableInsertFront = insertFront;
+
+    /// ditto
+    alias stableInsertBack = insertBack;
+
+/**
+Inserts $(D stuff) after range $(D r), which must be a non-empty range
+previously extracted from this container.
+
+$(D stuff) can be a value convertible to $(D T) or a range of objects
+convertible to $(D T). 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 k + m), where $(D k) is the number of elements in
+$(D r) and $(D m) is the length of $(D stuff).
+     */
+    size_t insertBefore(Stuff)(Range r, Stuff stuff)
+    {
+        if (r._first)
+            return insertBeforeNode(r._first, stuff);
+        else
+        {
+            initialize();
+            return insertAfterNode(_root, stuff);
+        }
+    }
+
+    /// ditto
+    alias stableInsertBefore = insertBefore;
+
+    /// ditto
+    size_t insertAfter(Stuff)(Range r, Stuff stuff)
+    {
+        if (r._last)
+            return insertAfterNode(r._last, stuff);
+        else
+        {
+            initialize();
+            return insertBeforeNode(_root, stuff);
+        }
+    }
+
+    /// ditto
+    alias stableInsertAfter = insertAfter;
+
+/+ ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ +/
+/+                        BEGIN REMOVE FUNCTIONS HERE                         +/
+/+ ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ +/
+
+/**
+Picks one value in an unspecified position 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 1).
+     */
+    T removeAny()
+    {
+        import std.algorithm.mutation : move;
+
+        assert(!empty, "DList.removeAny: List is empty");
+        auto result = move(back);
+        removeBack();
+        return result;
+    }
+    /// ditto
+    alias stableRemoveAny = removeAny;
+
+/**
+Removes the value at the front/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 1).
+     */
+    void removeFront()
+    {
+        assert(!empty, "DList.removeFront: List is empty");
+        assert(_root is _first._prev, "DList: Inconsistent state");
+        BaseNode.connect(_root, _first._next);
+    }
+
+    /// ditto
+    alias stableRemoveFront = removeFront;
+
+    /// ditto
+    void removeBack()
+    {
+        assert(!empty, "DList.removeBack: List is empty");
+        assert(_last._next is _root, "DList: Inconsistent state");
+        BaseNode.connect(_last._prev, _root);
+    }
+
+    /// ditto
+    alias stableRemoveBack = removeBack;
+
+/**
+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).
+     */
+    size_t removeFront(size_t howMany)
+    {
+        if (!_root) return 0;
+        size_t result;
+        auto p = _first;
+        while (p !is _root && result < howMany)
+        {
+            p = p._next;
+            ++result;
+        }
+        BaseNode.connect(_root, p);
+        return result;
+    }
+
+    /// ditto
+    alias stableRemoveFront = removeFront;
+
+    /// ditto
+    size_t removeBack(size_t howMany)
+    {
+        if (!_root) return 0;
+        size_t result;
+        auto p = _last;
+        while (p !is _root && result < howMany)
+        {
+            p = p._prev;
+            ++result;
+        }
+        BaseNode.connect(p, _root);
+        return result;
+    }
+
+    /// ditto
+    alias stableRemoveBack = removeBack;
+
+/**
+Removes all elements belonging to $(D r), which must be a range
+obtained originally from this container.
+
+Returns: A range spanning the remaining elements in the container that
+initially were right after $(D r).
+
+Complexity: $(BIGOH 1)
+     */
+    Range remove(Range r)
+    {
+        if (r.empty)
+            return r;
+
+        assert(_root !is null, "Cannot remove from an un-initialized List");
+        assert(r._first, "Remove: Range is empty");
+
+        BaseNode.connect(r._first._prev, r._last._next);
+        auto after = r._last._next;
+        if (after is _root)
+            return Range(null, null);
+        else
+            return Range(after, _last);
+    }
+
+    /// ditto
+    Range linearRemove(Range r)
+    {
+        return remove(r);
+    }
+
+/**
+Removes first element of $(D r), wich must be a range obtained originally
+from this container, from both DList instance and range $(D r).
+
+Compexity: $(BIGOH 1)
+     */
+    void popFirstOf(ref Range r)
+    {
+        assert(_root !is null, "Cannot remove from an un-initialized List");
+        assert(r._first, "popFirstOf: Range is empty");
+        auto prev = r._first._prev;
+        auto next = r._first._next;
+        r.popFront();
+        BaseNode.connect(prev, next);
+    }
+
+/**
+Removes last element of $(D r), wich must be a range obtained originally
+from this container, from both DList instance and range $(D r).
+
+Compexity: $(BIGOH 1)
+     */
+    void popLastOf(ref Range r)
+    {
+        assert(_root !is null, "Cannot remove from an un-initialized List");
+        assert(r._first, "popLastOf: Range is empty");
+        auto prev = r._last._prev;
+        auto next = r._last._next;
+        r.popBack();
+        BaseNode.connect(prev, next);
+    }
+
+/**
+$(D linearRemove) functions as $(D remove), but also accepts ranges that are
+result the of a $(D take) operation. This is a convenient way to remove a
+fixed amount of elements from the range.
+
+Complexity: $(BIGOH r.walkLength)
+     */
+    Range linearRemove(Take!Range r)
+    {
+        assert(_root !is null, "Cannot remove from an un-initialized List");
+        assert(r.source._first, "Remove: Range is empty");
+
+        BaseNode* first = r.source._first;
+        BaseNode* last = null;
+        do
+        {
+            last = r.source._first;
+            r.popFront();
+        } while ( !r.empty );
+
+        return remove(Range(first, last));
+    }
+
+    /// ditto
+    alias stableRemove = remove;
+    /// ditto
+    alias stableLinearRemove = linearRemove;
+
+private:
+
+    // Helper: Inserts stuff before the node n.
+    size_t insertBeforeNode(Stuff)(BaseNode* n, ref Stuff stuff)
+    if (isImplicitlyConvertible!(Stuff, T))
+    {
+        auto p = createNode(stuff, n._prev, n);
+        n._prev._next = p;
+        n._prev = p;
+        return 1;
+    }
+    // ditto
+    size_t insertBeforeNode(Stuff)(BaseNode* n, ref Stuff stuff)
+    if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T))
+    {
+        if (stuff.empty) return 0;
+        size_t result;
+        Range r = createRange(stuff, result);
+        BaseNode.connect(n._prev, r._first);
+        BaseNode.connect(r._last, n);
+        return result;
+    }
+
+    // Helper: Inserts stuff after the node n.
+    size_t insertAfterNode(Stuff)(BaseNode* n, ref Stuff stuff)
+    if (isImplicitlyConvertible!(Stuff, T))
+    {
+        auto p = createNode(stuff, n, n._next);
+        n._next._prev = p;
+        n._next = p;
+        return 1;
+    }
+    // ditto
+    size_t insertAfterNode(Stuff)(BaseNode* n, ref Stuff stuff)
+    if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T))
+    {
+        if (stuff.empty) return 0;
+        size_t result;
+        Range r = createRange(stuff, result);
+        BaseNode.connect(r._last, n._next);
+        BaseNode.connect(n, r._first);
+        return result;
+    }
+
+    // Helper: Creates a chain of nodes from the range stuff.
+    Range createRange(Stuff)(ref Stuff stuff, ref size_t result)
+    {
+        BaseNode* first = createNode(stuff.front);
+        BaseNode* last = first;
+        ++result;
+        for ( stuff.popFront() ; !stuff.empty ; stuff.popFront() )
+        {
+            auto p = createNode(stuff.front, last);
+            last = last._next = p;
+            ++result;
+        }
+        return Range(first, last);
+    }
+}
+
+@safe unittest
+{
+    import std.algorithm.comparison : equal;
+
+    //Tests construction signatures
+    alias IntList = DList!int;
+    auto a0 = IntList();
+    auto a1 = IntList(0);
+    auto a2 = IntList(0, 1);
+    auto a3 = IntList([0]);
+    auto a4 = IntList([0, 1]);
+
+    assert(a0[].empty);
+    assert(equal(a1[], [0]));
+    assert(equal(a2[], [0, 1]));
+    assert(equal(a3[], [0]));
+    assert(equal(a4[], [0, 1]));
+}
+
+@safe unittest
+{
+    import std.algorithm.comparison : equal;
+
+    alias IntList = DList!int;
+    IntList list = IntList([0,1,2,3]);
+    assert(equal(list[],[0,1,2,3]));
+    list.insertBack([4,5,6,7]);
+    assert(equal(list[],[0,1,2,3,4,5,6,7]));
+
+    list = IntList();
+    list.insertFront([0,1,2,3]);
+    assert(equal(list[],[0,1,2,3]));
+    list.insertFront([4,5,6,7]);
+    assert(equal(list[],[4,5,6,7,0,1,2,3]));
+}
+
+@safe unittest
+{
+    import std.algorithm.comparison : equal;
+    import std.range : take;
+
+    alias IntList = DList!int;
+    IntList list = IntList([0,1,2,3]);
+    auto range = list[];
+    for ( ; !range.empty; range.popFront())
+    {
+        int item = range.front;
+        if (item == 2)
+        {
+            list.stableLinearRemove(take(range, 1));
+            break;
+        }
+    }
+    assert(equal(list[],[0,1,3]));
+
+    list = IntList([0,1,2,3]);
+    range = list[];
+    for ( ; !range.empty; range.popFront())
+    {
+        int item = range.front;
+        if (item == 2)
+        {
+            list.stableLinearRemove(take(range,2));
+            break;
+        }
+    }
+    assert(equal(list[],[0,1]));
+
+    list = IntList([0,1,2,3]);
+    range = list[];
+    for ( ; !range.empty; range.popFront())
+    {
+        int item = range.front;
+        if (item == 0)
+        {
+            list.stableLinearRemove(take(range,2));
+            break;
+        }
+    }
+    assert(equal(list[],[2,3]));
+
+    list = IntList([0,1,2,3]);
+    range = list[];
+    for ( ; !range.empty; range.popFront())
+    {
+        int item = range.front;
+        if (item == 1)
+        {
+            list.stableLinearRemove(take(range,2));
+            break;
+        }
+    }
+    assert(equal(list[],[0,3]));
+}
+
+@safe unittest
+{
+    import std.algorithm.comparison : equal;
+
+    auto dl = DList!int([1, 2, 3, 4, 5]);
+    auto r = dl[];
+    r.popFront();
+    dl.popFirstOf(r);
+    assert(equal(dl[], [1, 3, 4, 5]));
+    assert(equal(r, [3, 4, 5]));
+    r.popBack();
+    dl.popLastOf(r);
+    assert(equal(dl[], [1, 3, 5]));
+    assert(equal(r, [3]));
+    dl = DList!int([0]);
+    r = dl[];
+    dl.popFirstOf(r);
+    assert(dl.empty);
+    dl = DList!int([0]);
+    r = dl[];
+    dl.popLastOf(r);
+    assert(dl.empty);
+}
+
+@safe unittest
+{
+    import std.algorithm.comparison : equal;
+
+    auto dl = DList!string(["a", "b", "d"]);
+    dl.insertAfter(dl[], "e"); // insert at the end
+    assert(equal(dl[], ["a", "b", "d", "e"]));
+    auto dlr = dl[];
+    dlr.popBack(); dlr.popBack();
+    dl.insertAfter(dlr, "c"); // insert after "b"
+    assert(equal(dl[], ["a", "b", "c", "d", "e"]));
+}
+
+@safe unittest
+{
+    import std.algorithm.comparison : equal;
+
+    auto dl = DList!string(["a", "b", "d"]);
+    dl.insertBefore(dl[], "e"); // insert at the front
+    assert(equal(dl[], ["e", "a", "b", "d"]));
+    auto dlr = dl[];
+    dlr.popFront(); dlr.popFront();
+    dl.insertBefore(dlr, "c"); // insert before "b"
+    assert(equal(dl[], ["e", "a", "c", "b", "d"]));
+}
+
+@safe unittest
+{
+    auto d = DList!int([1, 2, 3]);
+    d.front = 5; //test frontAssign
+    assert(d.front == 5);
+    auto r = d[];
+    r.back = 1;
+    assert(r.back == 1);
+}
+
+// Issue 8895
+@safe unittest
+{
+    auto a = make!(DList!int)(1,2,3,4);
+    auto b = make!(DList!int)(1,2,3,4);
+    auto c = make!(DList!int)(1,2,3,5);
+    auto d = make!(DList!int)(1,2,3,4,5);
+    assert(a == b); // this better terminate!
+    assert(!(a == c));
+    assert(!(a == d));
+}
+
+@safe unittest
+{
+    auto d = DList!int([1, 2, 3]);
+    d.front = 5; //test frontAssign
+    assert(d.front == 5);
+    auto r = d[];
+    r.back = 1;
+    assert(r.back == 1);
+}
+
+@safe unittest
+{
+    auto a = DList!int();
+    assert(a.removeFront(10) == 0);
+    a.insert([1, 2, 3]);
+    assert(a.removeFront(10) == 3);
+    assert(a[].empty);
+}
+
+@safe unittest
+{
+    import std.algorithm.comparison : equal;
+
+    //Verify all flavors of ~
+    auto a = DList!int();
+    auto b = DList!int();
+    auto c = DList!int([1, 2, 3]);
+    auto d = DList!int([4, 5, 6]);
+
+    assert((a ~ b[])[].empty);
+    assert((c ~ d[])[].equal([1, 2, 3, 4, 5, 6]));
+    assert(c[].equal([1, 2, 3]));
+    assert(d[].equal([4, 5, 6]));
+
+    assert((c[] ~ d)[].equal([1, 2, 3, 4, 5, 6]));
+    assert(c[].equal([1, 2, 3]));
+    assert(d[].equal([4, 5, 6]));
+
+    a~=c[];
+    assert(a[].equal([1, 2, 3]));
+    assert(c[].equal([1, 2, 3]));
+
+    a~=d[];
+    assert(a[].equal([1, 2, 3, 4, 5, 6]));
+    assert(d[].equal([4, 5, 6]));
+
+    a~=[7, 8, 9];
+    assert(a[].equal([1, 2, 3, 4, 5, 6, 7, 8, 9]));
+
+    //trick test:
+    auto r = c[];
+    c.removeFront();
+    c.removeBack();
+}
+
+@safe unittest
+{
+    import std.algorithm.comparison : equal;
+
+    //8905
+    auto a = DList!int([1, 2, 3, 4]);
+    auto r = a[];
+    a.stableRemoveBack();
+    a.stableInsertBack(7);
+    assert(a[].equal([1, 2, 3, 7]));
+}
+
+@safe unittest //12566
+{
+    auto dl2 = DList!int([2,7]);
+    dl2.removeFront();
+    assert(dl2[].walkLength == 1);
+    dl2.removeBack();
+    assert(dl2.empty, "not empty?!");
+}
+
+@safe unittest //13076
+{
+    DList!int list;
+    assert(list.empty);
+    list.clear();
+}
+
+@safe unittest //13425
+{
+    import std.range : drop, take;
+    auto list = DList!int([1,2,3,4,5]);
+    auto r = list[].drop(4); // r is a view of the last element of list
+    assert(r.front == 5 && r.walkLength == 1);
+    r = list.linearRemove(r.take(1));
+    assert(r.empty); // fails
+}
+
+@safe unittest //14300
+{
+    interface ITest {}
+    static class Test : ITest {}
+
+    DList!ITest().insertBack(new Test());
+}
+
+@safe unittest //15263
+{
+    import std.range : iota;
+    auto a = DList!int();
+    a.insertFront(iota(0, 5)); // can insert range with non-ref front
+    assert(a.front == 0 && a.back == 4);
+}
diff --git a/libphobos/src/std/container/package.d b/libphobos/src/std/container/package.d
new file mode 100644
index 0000000..fa00505
--- /dev/null
+++ b/libphobos/src/std/container/package.d
@@ -0,0 +1,1156 @@
+// Written in the D programming language.
+
+/**
+This module defines generic containers.
+
+Construction:
+
+To implement the different containers both struct and class based
+approaches have been used. $(REF make, std,_container,util) allows for
+uniform construction with either approach.
+
+---
+import std.container;
+// Construct a red-black tree and an array both containing the values 1, 2, 3.
+// RedBlackTree should typically be allocated using `new`
+RedBlackTree!int rbTree = new RedBlackTree!int(1, 2, 3);
+// But `new` should not be used with Array
+Array!int array = Array!int(1, 2, 3);
+// `make` hides the differences
+RedBlackTree!int rbTree2 = make!(RedBlackTree!int)(1, 2, 3);
+Array!int array2 = make!(Array!int)(1, 2, 3);
+---
+
+Note that $(D make) can infer the element type from the given arguments.
+
+---
+import std.container;
+auto rbTree = make!RedBlackTree(1, 2, 3); // RedBlackTree!int
+auto array = make!Array("1", "2", "3"); // Array!string
+---
+
+Reference_semantics:
+
+All containers have reference semantics, which means that after
+assignment both variables refer to the same underlying data.
+
+To make a copy of a _container, use the $(D c._dup) _container primitive.
+---
+import std.container, std.range;
+Array!int originalArray = make!(Array!int)(1, 2, 3);
+Array!int secondArray = originalArray;
+assert(equal(originalArray[], secondArray[]));
+
+// changing one instance changes the other one as well!
+originalArray[0] = 12;
+assert(secondArray[0] == 12);
+
+// secondArray now refers to an independent copy of originalArray
+secondArray = originalArray.dup;
+secondArray[0] = 1;
+// assert that originalArray has not been affected
+assert(originalArray[0] == 12);
+---
+
+$(B Attention:) If the _container is implemented as a class, using an
+uninitialized instance can cause a null pointer dereference.
+
+---
+import std.container;
+
+RedBlackTree!int rbTree;
+rbTree.insert(5); // null pointer dereference
+---
+
+Using an uninitialized struct-based _container will work, because the struct
+intializes itself upon use; however, up to this point the _container will not
+have an identity and assignment does not create two references to the same
+data.
+
+---
+import std.container;
+
+// create an uninitialized array
+Array!int array1;
+// array2 does _not_ refer to array1
+Array!int array2 = array1;
+array2.insertBack(42);
+// thus array1 will not be affected
+assert(array1.empty);
+
+// after initialization reference semantics work as expected
+array1 = array2;
+// now affects array2 as well
+array1.removeBack();
+assert(array2.empty);
+---
+It is therefore recommended to always construct containers using
+$(REF make, std,_container,util).
+
+This is in fact necessary to put containers into another _container.
+For example, to construct an $(D Array) of ten empty $(D Array)s, use
+the following that calls $(D make) ten times.
+
+---
+import std.container, std.range;
+
+auto arrOfArrs = make!Array(generate!(() => make!(Array!int)).take(10));
+---
+
+Submodules:
+
+This module consists of the following submodules:
+
+$(UL
+    $(LI
+        The $(MREF std, _container, array) module provides
+        an array type with deterministic control of memory, not reliant on
+        the GC unlike built-in arrays.
+    )
+    $(LI
+        The $(MREF std, _container, binaryheap) module
+        provides a binary heap implementation that can be applied to any
+        user-provided random-access range.
+    )
+    $(LI
+        The $(MREF std, _container, dlist) module provides
+        a doubly-linked list implementation.
+    )
+    $(LI
+        The $(MREF std, _container, rbtree) module
+        implements red-black trees.
+    )
+    $(LI
+        The $(MREF std, _container, slist) module
+        implements singly-linked lists.
+    )
+    $(LI
+        The $(MREF std, _container, util) module contains
+        some generic tools commonly used by _container implementations.
+    )
+)
+
+The_primary_range_of_a_container:
+
+While some _containers offer direct access to their elements e.g. via
+$(D opIndex), $(D c.front) or $(D c.back), access
+and modification of a _container's contents is generally done through
+its primary $(MREF_ALTTEXT range, std, range) type,
+which is aliased as $(D C.Range). For example, the primary range type of
+$(D Array!int) is $(D Array!int.Range).
+
+If the documentation of a member function of a _container takes
+a parameter of type $(D Range), then it refers to the primary range type of
+this _container. Oftentimes $(D Take!Range) will be used, in which case
+the range refers to a span of the elements in the _container. Arguments to
+these parameters $(B must) be obtained from the same _container instance
+as the one being worked with. It is important to note that many generic range
+algorithms return the same range type as their input range.
+
+---
+import std.algorithm.comparison : equal;
+import std.algorithm.iteration : find;
+import std.container;
+import std.range : take;
+
+auto array = make!Array(1, 2, 3);
+
+// `find` returns an Array!int.Range advanced to the element "2"
+array.linearRemove(array[].find(2));
+
+assert(array[].equal([1]));
+
+array = make!Array(1, 2, 3);
+
+// the range given to `linearRemove` is a Take!(Array!int.Range)
+// spanning just the element "2"
+array.linearRemove(array[].find(2).take(1));
+
+assert(array[].equal([1, 3]));
+---
+
+When any $(MREF_ALTTEXT range, std, range) can be passed as an argument to
+a member function, the documention usually refers to the parameter's templated
+type as $(D Stuff).
+
+---
+import std.algorithm.comparison : equal;
+import std.container;
+import std.range : iota;
+
+auto array = make!Array(1, 2);
+
+// the range type returned by `iota` is completely unrelated to Array,
+// which is fine for Array.insertBack:
+array.insertBack(iota(3, 10));
+
+assert(array[].equal([1, 2, 3, 4, 5, 6, 7, 8, 9]));
+---
+
+Container_primitives:
+
+Containers do not form a class hierarchy, instead they implement a
+common set of primitives (see table below). These primitives each guarantee
+a specific worst case complexity and thus allow generic code to be written
+independently of the _container implementation.
+
+For example the primitives $(D c.remove(r)) and $(D c.linearRemove(r)) both
+remove the sequence of elements in range $(D r) from the _container $(D c).
+The primitive $(D c.remove(r)) guarantees
+$(BIGOH n$(SUBSCRIPT r) log n$(SUBSCRIPT c)) complexity in the worst case and
+$(D c.linearRemove(r)) relaxes this guarantee to $(BIGOH n$(SUBSCRIPT c)).
+
+Since a sequence of elements can be removed from a $(MREF_ALTTEXT doubly linked list,std,_container,dlist)
+in constant time, $(D DList) provides the primitive $(D c.remove(r))
+as well as $(D c.linearRemove(r)). On the other hand
+$(MREF_ALTTEXT Array, std,_container, array) only offers $(D c.linearRemove(r)).
+
+The following table describes the common set of primitives that containers
+implement.  A _container need not implement all primitives, but if a
+primitive is implemented, it must support the syntax described in the $(B
+syntax) column with the semantics described in the $(B description) column, and
+it must not have a worst-case complexity worse than denoted in big-O notation in
+the $(BIGOH &middot;) column.  Below, $(D C) means a _container type, $(D c) is
+a value of _container type, $(D n$(SUBSCRIPT x)) represents the effective length of
+value $(D x), which could be a single element (in which case $(D n$(SUBSCRIPT x)) is
+$(D 1)), a _container, or a range.
+
+$(BOOKTABLE Container primitives,
+$(TR
+    $(TH Syntax)
+    $(TH $(BIGOH &middot;))
+    $(TH Description)
+)
+$(TR
+    $(TDNW $(D C(x)))
+    $(TDNW $(D n$(SUBSCRIPT x)))
+    $(TD Creates a _container of type $(D C) from either another _container or a range.
+    The created _container must not be a null reference even if x is empty.)
+)
+$(TR
+    $(TDNW $(D c.dup))
+    $(TDNW $(D n$(SUBSCRIPT c)))
+    $(TD Returns a duplicate of the _container.)
+)
+$(TR
+    $(TDNW $(D c ~ x))
+    $(TDNW $(D n$(SUBSCRIPT c) + n$(SUBSCRIPT x)))
+    $(TD Returns the concatenation of $(D c) and $(D r). $(D x) may be a single
+        element or an input range.)
+)
+$(TR
+    $(TDNW $(D x ~ c))
+    $(TDNW $(D n$(SUBSCRIPT c) + n$(SUBSCRIPT x)))
+    $(TD Returns the concatenation of $(D x) and $(D c).  $(D x) may be a
+        single element or an input range type.)
+)
+$(LEADINGROWN 3, Iteration
+)
+$(TR
+    $(TD $(D c.Range))
+    $(TD)
+    $(TD The primary range type associated with the _container.)
+)
+$(TR
+    $(TD $(D c[]))
+    $(TDNW $(D log n$(SUBSCRIPT c)))
+    $(TD Returns a range
+         iterating over the entire _container, in a _container-defined order.)
+)
+$(TR
+    $(TDNW $(D c[a .. b]))
+    $(TDNW $(D log n$(SUBSCRIPT c)))
+    $(TD Fetches a portion of the _container from key $(D a) to key $(D b).)
+)
+$(LEADINGROWN 3, Capacity
+)
+$(TR
+    $(TD $(D c.empty))
+    $(TD $(D 1))
+    $(TD Returns $(D true) if the _container has no elements, $(D false) otherwise.)
+)
+$(TR
+    $(TD $(D c.length))
+    $(TDNW $(D log n$(SUBSCRIPT c)))
+    $(TD Returns the number of elements in the _container.)
+)
+$(TR
+    $(TDNW $(D c.length = n))
+    $(TDNW $(D n$(SUBSCRIPT c) + n))
+    $(TD Forces the number of elements in the _container to $(D n).
+        If the _container ends up growing, the added elements are initialized
+        in a _container-dependent manner (usually with $(D T.init)).)
+)
+$(TR
+    $(TD $(D c.capacity))
+    $(TDNW $(D log n$(SUBSCRIPT c)))
+    $(TD Returns the maximum number of elements that can be stored in the
+    _container without triggering a reallocation.)
+)
+$(TR
+    $(TD $(D c.reserve(x)))
+    $(TD $(D n$(SUBSCRIPT c)))
+    $(TD Forces $(D capacity) to at least $(D x) without reducing it.)
+)
+$(LEADINGROWN 3, Access
+)
+$(TR
+    $(TDNW $(D c.front))
+    $(TDNW $(D log n$(SUBSCRIPT c)))
+    $(TD Returns the first element of the _container, in a _container-defined order.)
+)
+$(TR
+    $(TDNW $(D c.moveFront))
+    $(TDNW $(D log n$(SUBSCRIPT c)))
+    $(TD Destructively reads and returns the first element of the
+         _container. The slot is not removed from the _container; it is left
+         initialized with $(D T.init). This routine need not be defined if $(D
+         front) returns a $(D ref).)
+)
+$(TR
+    $(TDNW $(D c.front = v))
+    $(TDNW $(D log n$(SUBSCRIPT c)))
+    $(TD Assigns $(D v) to the first element of the _container.)
+)
+$(TR
+    $(TDNW $(D c.back))
+    $(TDNW $(D log n$(SUBSCRIPT c)))
+    $(TD Returns the last element of the _container, in a _container-defined order.)
+)
+$(TR
+    $(TDNW $(D c.moveBack))
+    $(TDNW $(D log n$(SUBSCRIPT c)))
+    $(TD Destructively reads and returns the last element of the
+         _container. The slot is not removed from the _container; it is left
+         initialized with $(D T.init). This routine need not be defined if $(D
+         front) returns a $(D ref).)
+)
+$(TR
+    $(TDNW $(D c.back = v))
+    $(TDNW $(D log n$(SUBSCRIPT c)))
+    $(TD Assigns $(D v) to the last element of the _container.)
+)
+$(TR
+    $(TDNW $(D c[x]))
+    $(TDNW $(D log n$(SUBSCRIPT c)))
+    $(TD Provides indexed access into the _container. The index type is
+         _container-defined. A _container may define several index types (and
+         consequently overloaded indexing).)
+)
+$(TR
+    $(TDNW $(D c.moveAt(x)))
+    $(TDNW $(D log n$(SUBSCRIPT c)))
+    $(TD Destructively reads and returns the value at position $(D x). The slot
+         is not removed from the _container; it is left initialized with $(D
+         T.init).)
+)
+$(TR
+    $(TDNW $(D c[x] = v))
+    $(TDNW $(D log n$(SUBSCRIPT c)))
+    $(TD Sets element at specified index into the _container.)
+)
+$(TR
+    $(TDNW $(D c[x] $(I op)= v))
+    $(TDNW $(D log n$(SUBSCRIPT c)))
+    $(TD Performs read-modify-write operation at specified index into the
+        _container.)
+)
+$(LEADINGROWN 3, Operations
+)
+$(TR
+    $(TDNW $(D e in c))
+    $(TDNW $(D log n$(SUBSCRIPT c)))
+    $(TD Returns nonzero if e is found in $(D c).)
+)
+$(TR
+    $(TDNW $(D c.lowerBound(v)))
+    $(TDNW $(D log n$(SUBSCRIPT c)))
+    $(TD Returns a range of all elements strictly less than $(D v).)
+)
+$(TR
+    $(TDNW $(D c.upperBound(v)))
+    $(TDNW $(D log n$(SUBSCRIPT c)))
+    $(TD Returns a range of all elements strictly greater than $(D v).)
+)
+$(TR
+    $(TDNW $(D c.equalRange(v)))
+    $(TDNW $(D log n$(SUBSCRIPT c)))
+    $(TD Returns a range of all elements in $(D c) that are equal to $(D v).)
+)
+$(LEADINGROWN 3, Modifiers
+)
+$(TR
+    $(TDNW $(D c ~= x))
+    $(TDNW $(D n$(SUBSCRIPT c) + n$(SUBSCRIPT x)))
+    $(TD Appends $(D x) to $(D c). $(D x) may be a single element or an input range type.)
+)
+$(TR
+    $(TDNW $(D c.clear()))
+    $(TDNW $(D n$(SUBSCRIPT c)))
+    $(TD Removes all elements in $(D c).)
+)
+$(TR
+    $(TDNW $(D c.insert(x)))
+    $(TDNW $(D n$(SUBSCRIPT x) * log n$(SUBSCRIPT c)))
+    $(TD Inserts $(D x) in $(D c) at a position (or positions) chosen by $(D c).)
+)
+$(TR
+    $(TDNW $(D c.stableInsert(x)))
+    $(TDNW $(D n$(SUBSCRIPT x) * log n$(SUBSCRIPT c)))
+    $(TD Same as $(D c.insert(x)), but is guaranteed to not invalidate any ranges.)
+)
+$(TR
+    $(TDNW $(D c.linearInsert(v)))
+    $(TDNW $(D n$(SUBSCRIPT c)))
+    $(TD Same as $(D c.insert(v)) but relaxes complexity to linear.)
+)
+$(TR
+    $(TDNW $(D c.stableLinearInsert(v)))
+    $(TDNW $(D n$(SUBSCRIPT c)))
+    $(TD Same as $(D c.stableInsert(v)) but relaxes complexity to linear.)
+)
+$(TR
+    $(TDNW $(D c.removeAny()))
+    $(TDNW $(D log n$(SUBSCRIPT c)))
+    $(TD Removes some element from $(D c) and returns it.)
+)
+$(TR
+    $(TDNW $(D c.stableRemoveAny()))
+    $(TDNW $(D log n$(SUBSCRIPT c)))
+    $(TD Same as $(D c.removeAny()), but is guaranteed to not invalidate any
+         iterators.)
+)
+$(TR
+    $(TDNW $(D c.insertFront(v)))
+    $(TDNW $(D log n$(SUBSCRIPT c)))
+    $(TD Inserts $(D v) at the front of $(D c).)
+)
+$(TR
+    $(TDNW $(D c.stableInsertFront(v)))
+    $(TDNW $(D log n$(SUBSCRIPT c)))
+    $(TD Same as $(D c.insertFront(v)), but guarantees no ranges will be
+         invalidated.)
+)
+$(TR
+    $(TDNW $(D c.insertBack(v)))
+    $(TDNW $(D log n$(SUBSCRIPT c)))
+    $(TD Inserts $(D v) at the back of $(D c).)
+)
+$(TR
+    $(TDNW $(D c.stableInsertBack(v)))
+    $(TDNW $(D log n$(SUBSCRIPT c)))
+    $(TD Same as $(D c.insertBack(v)), but guarantees no ranges will be
+         invalidated.)
+)
+$(TR
+    $(TDNW $(D c.removeFront()))
+    $(TDNW $(D log n$(SUBSCRIPT c)))
+    $(TD Removes the element at the front of $(D c).)
+)
+$(TR
+    $(TDNW $(D c.stableRemoveFront()))
+    $(TDNW $(D log n$(SUBSCRIPT c)))
+    $(TD Same as $(D c.removeFront()), but guarantees no ranges will be
+         invalidated.)
+)
+$(TR
+    $(TDNW $(D c.removeBack()))
+    $(TDNW $(D log n$(SUBSCRIPT c)))
+    $(TD Removes the value at the back of $(D c).)
+)
+$(TR
+    $(TDNW $(D c.stableRemoveBack()))
+    $(TDNW $(D log n$(SUBSCRIPT c)))
+    $(TD Same as $(D c.removeBack()), but guarantees no ranges will be
+         invalidated.)
+)
+$(TR
+    $(TDNW $(D c.remove(r)))
+    $(TDNW $(D n$(SUBSCRIPT r) * log n$(SUBSCRIPT c)))
+    $(TD Removes range $(D r) from $(D c).)
+)
+$(TR
+    $(TDNW $(D c.stableRemove(r)))
+    $(TDNW $(D n$(SUBSCRIPT r) * log n$(SUBSCRIPT c)))
+    $(TD Same as $(D c.remove(r)), but guarantees iterators are not
+         invalidated.)
+)
+$(TR
+    $(TDNW $(D c.linearRemove(r)))
+    $(TDNW $(D n$(SUBSCRIPT c)))
+    $(TD Removes range $(D r) from $(D c).)
+)
+$(TR
+    $(TDNW $(D c.stableLinearRemove(r)))
+    $(TDNW $(D n$(SUBSCRIPT c)))
+    $(TD Same as $(D c.linearRemove(r)), but guarantees iterators are not
+         invalidated.)
+)
+$(TR
+    $(TDNW $(D c.removeKey(k)))
+    $(TDNW $(D log n$(SUBSCRIPT c)))
+    $(TD Removes an element from $(D c) by using its key $(D k).
+         The key's type is defined by the _container.)
+)
+$(TR
+    $(TDNW $(D ))
+    $(TDNW $(D ))
+    $(TD )
+)
+)
+
+Source: $(PHOBOSSRC std/_container/package.d)
+
+Copyright: Red-black tree code copyright (C) 2008- by Steven Schveighoffer. Other code
+copyright 2010- Andrei Alexandrescu. All rights reserved by the respective holders.
+
+License: Distributed under the Boost Software License, Version 1.0.
+(See accompanying file LICENSE_1_0.txt or copy at $(HTTP
+boost.org/LICENSE_1_0.txt)).
+
+Authors: Steven Schveighoffer, $(HTTP erdani.com, Andrei Alexandrescu)
+ */
+
+module std.container;
+
+public import std.container.array;
+public import std.container.binaryheap;
+public import std.container.dlist;
+public import std.container.rbtree;
+public import std.container.slist;
+
+import std.meta;
+
+
+/* The following documentation and type $(D TotalContainer) are
+intended for developers only.
+
+$(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.
+
+Things to remember: any container must be a reference type, whether
+implemented as a $(D class) or $(D struct). No primitive below
+requires the container to escape addresses of elements, which means
+that compliant containers can be defined to use reference counting or
+other deterministic memory management techniques.
+
+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.
+ */
+struct TotalContainer(T)
+{
+/**
+If the container has a notion of key-value mapping, $(D KeyType)
+defines the type of the key of the container.
+ */
+    alias KeyType = 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.
+ */
+    alias KeyTypes = AliasSeq!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 $(D KeyType) to be $(D K) and $(D ValueType) to be $(D V).
+ */
+    alias ValueType = T;
+
+/**
+Defines the container's primary range, which embodies one of the
+ranges defined in $(MREF std,range).
+
+Generally a container may define several types of ranges.
+ */
+    struct Range
+    {
+        /++
+        Range primitives.
+        +/
+        @property bool empty()
+        {
+            assert(0);
+        }
+        /// Ditto
+        @property ref T front() //ref return optional
+        {
+            assert(0);
+        }
+        /// Ditto
+        @property void front(T value) //Only when front does not return by ref
+        {
+            assert(0);
+        }
+        /// Ditto
+        T moveFront()
+        {
+            assert(0);
+        }
+        /// Ditto
+        void popFront()
+        {
+            assert(0);
+        }
+        /// Ditto
+        @property ref T back() //ref return optional
+        {
+            assert(0);
+        }
+        /// Ditto
+        @property void back(T value) //Only when front does not return by ref
+        {
+            assert(0);
+        }
+        /// Ditto
+        T moveBack()
+        {
+            assert(0);
+        }
+        /// Ditto
+        void popBack()
+        {
+            assert(0);
+        }
+        /// Ditto
+        T opIndex(size_t i) //ref return optional
+        {
+            assert(0);
+        }
+        /// Ditto
+        void opIndexAssign(size_t i, T value) //Only when front does not return by ref
+        {
+            assert(0);
+        }
+        /// Ditto
+        T opIndexUnary(string op)(size_t i) //Only when front does not return by ref
+        {
+            assert(0);
+        }
+        /// Ditto
+        void opIndexOpAssign(string op)(size_t i, T value) //Only when front does not return by ref
+        {
+            assert(0);
+        }
+        /// Ditto
+        T moveAt(size_t i)
+        {
+            assert(0);
+        }
+        /// Ditto
+        @property size_t length()
+        {
+            assert(0);
+        }
+    }
+
+/**
+Property returning $(D true) if and only if the container has no
+elements.
+
+Complexity: $(BIGOH 1)
+ */
+    @property bool empty()
+    {
+        assert(0);
+    }
+
+/**
+Returns a duplicate of the container. The elements themselves are not
+transitively duplicated.
+
+Complexity: $(BIGOH n).
+ */
+    @property TotalContainer dup()
+    {
+        assert(0);
+    }
+
+/**
+Returns the number of elements in the container.
+
+Complexity: $(BIGOH log(n)).
+*/
+    @property size_t length()
+    {
+        assert(0);
+    }
+
+/**
+Returns the maximum number of elements the container can store without
+(a) allocating memory, (b) invalidating iterators upon insertion.
+
+Complexity: $(BIGOH log(n)).
+ */
+    @property size_t capacity()
+    {
+        assert(0);
+    }
+
+/**
+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(size_t e)
+    {
+        assert(0);
+    }
+
+/**
+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()
+    {
+        assert(0);
+    }
+
+    /**
+       Returns a range that iterates the container between two
+       specified positions.
+
+       Complexity: $(BIGOH log(n))
+     */
+    Range opSlice(size_t a, size_t b)
+    {
+        assert(0);
+    }
+
+/**
+Forward to $(D opSlice().front) and $(D opSlice().back), respectively.
+
+Complexity: $(BIGOH log(n))
+ */
+    @property ref T front() //ref return optional
+    {
+        assert(0);
+    }
+    /// Ditto
+    @property void front(T value) //Only when front does not return by ref
+    {
+        assert(0);
+    }
+    /// Ditto
+    T moveFront()
+    {
+        assert(0);
+    }
+    /// Ditto
+    @property ref T back() //ref return optional
+    {
+        assert(0);
+    }
+    /// Ditto
+    @property void back(T value) //Only when front does not return by ref
+    {
+        assert(0);
+    }
+    /// Ditto
+    T moveBack()
+    {
+        assert(0);
+    }
+
+/**
+Indexing operators yield or modify the value at a specified index.
+ */
+    ref T opIndex(KeyType) //ref return optional
+    {
+        assert(0);
+    }
+    /// ditto
+    void opIndexAssign(KeyType i, T value) //Only when front does not return by ref
+    {
+        assert(0);
+    }
+    /// ditto
+    T opIndexUnary(string op)(KeyType i) //Only when front does not return by ref
+    {
+        assert(0);
+    }
+    /// ditto
+    void opIndexOpAssign(string op)(KeyType i, T value) //Only when front does not return by ref
+    {
+        assert(0);
+    }
+    /// ditto
+    T moveAt(KeyType i)
+    {
+        assert(0);
+    }
+
+/**
+$(D k in container) returns true if the given key is in the container.
+ */
+    bool opBinaryRight(string op)(KeyType k) if (op == "in")
+    {
+        assert(0);
+    }
+
+/**
+Returns a range of all elements containing $(D k) (could be empty or a
+singleton range).
+ */
+    Range equalRange(KeyType k)
+    {
+        assert(0);
+    }
+
+/**
+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.
+ */
+    Range lowerBound(KeyType k)
+    {
+        assert(0);
+    }
+
+/**
+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.
+ */
+    Range upperBound(KeyType k)
+    {
+        assert(0);
+    }
+
+/**
+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)
+ */
+    TotalContainer opBinary(string op)(Stuff rhs) if (op == "~")
+    {
+        assert(0);
+    }
+
+    /// ditto
+    TotalContainer opBinaryRight(string op)(Stuff lhs) if (op == "~")
+    {
+        assert(0);
+    }
+
+/**
+Forwards to $(D insertAfter(this[], stuff)).
+ */
+    void opOpAssign(string op)(Stuff stuff) if (op == "~")
+    {
+        assert(0);
+    }
+
+/**
+Removes all contents from the container. The container decides how $(D
+capacity) is affected.
+
+Postcondition: $(D empty)
+
+Complexity: $(BIGOH n)
+ */
+    void clear()
+    {
+        assert(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
+unspecified positions in the container and initialized with $(D
+.init).
+
+Complexity: $(BIGOH abs(n - newLength))
+
+Postcondition: $(D _length == newLength)
+ */
+    @property void length(size_t newLength)
+    {
+        assert(0);
+    }
+
+/**
+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
+behavior. $(D stuff) can be a value convertible to 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.
+
+Complexity: $(BIGOH m * log(n)), where $(D m) is the number of
+elements in $(D stuff)
+ */
+    size_t insert(Stuff)(Stuff stuff)
+    {
+        assert(0);
+    }
+    ///ditto
+    size_t stableInsert(Stuff)(Stuff stuff)
+    {
+        assert(0);
+    }
+
+/**
+Same as $(D insert(stuff)) and $(D stableInsert(stuff)) respectively,
+but relax the complexity constraint to linear.
+ */
+    size_t linearInsert(Stuff)(Stuff stuff)
+    {
+        assert(0);
+    }
+    ///ditto
+    size_t stableLinearInsert(Stuff)(Stuff stuff)
+    {
+        assert(0);
+    }
+
+/**
+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. 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()
+    {
+        assert(0);
+    }
+    /// ditto
+    T stableRemoveAny()
+    {
+        assert(0);
+    }
+
+/**
+Inserts $(D value) to the front or back of the container. $(D stuff)
+can be a value convertible to the container's element type or a range
+of values convertible to it. 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)).
+ */
+    size_t insertFront(Stuff)(Stuff stuff)
+    {
+        assert(0);
+    }
+    /// ditto
+    size_t stableInsertFront(Stuff)(Stuff stuff)
+    {
+        assert(0);
+    }
+    /// ditto
+    size_t insertBack(Stuff)(Stuff stuff)
+    {
+        assert(0);
+    }
+    /// ditto
+    size_t stableInsertBack(T value)
+    {
+        assert(0);
+    }
+
+/**
+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 removeFront()
+    {
+        assert(0);
+    }
+    /// ditto
+    void stableRemoveFront()
+    {
+        assert(0);
+    }
+    /// ditto
+    void removeBack()
+    {
+        assert(0);
+    }
+    /// ditto
+    void stableRemoveBack()
+    {
+        assert(0);
+    }
+
+/**
+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)).
+ */
+    size_t removeFront(size_t howMany)
+    {
+        assert(0);
+    }
+    /// ditto
+    size_t stableRemoveFront(size_t howMany)
+    {
+        assert(0);
+    }
+    /// ditto
+    size_t removeBack(size_t howMany)
+    {
+        assert(0);
+    }
+    /// ditto
+    size_t stableRemoveBack(size_t howMany)
+    {
+        assert(0);
+    }
+
+/**
+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.
+ */
+    size_t removeKey(KeyType k)
+    {
+        assert(0);
+    }
+
+/**
+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 the container's element type or a range
+of objects convertible to it. 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)
+ */
+    size_t insertBefore(Stuff)(Range r, Stuff stuff)
+    {
+        assert(0);
+    }
+    /// ditto
+    size_t stableInsertBefore(Stuff)(Range r, Stuff stuff)
+    {
+        assert(0);
+    }
+    /// ditto
+    size_t insertAfter(Stuff)(Range r, Stuff stuff)
+    {
+        assert(0);
+    }
+    /// ditto
+    size_t stableInsertAfter(Stuff)(Range r, Stuff stuff)
+    {
+        assert(0);
+    }
+    /// ditto
+    size_t replace(Stuff)(Range r, Stuff stuff)
+    {
+        assert(0);
+    }
+    /// ditto
+    size_t stableReplace(Stuff)(Range r, Stuff stuff)
+    {
+        assert(0);
+    }
+
+/**
+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)
+ */
+    Range remove(Range r)
+    {
+        assert(0);
+    }
+    /// ditto
+    Range stableRemove(Range r)
+    {
+        assert(0);
+    }
+
+/**
+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)
+ */
+    Range linearRemove(Range r)
+    {
+        assert(0);
+    }
+    /// ditto
+    Range stableLinearRemove(Range r)
+    {
+        assert(0);
+    }
+}
+
+@safe unittest
+{
+    TotalContainer!int test;
+}
diff --git a/libphobos/src/std/container/rbtree.d b/libphobos/src/std/container/rbtree.d
new file mode 100644
index 0000000..861da5e
--- /dev/null
+++ b/libphobos/src/std/container/rbtree.d
@@ -0,0 +1,2065 @@
+/**
+This module implements a red-black tree container.
+
+This module is a submodule of $(MREF std, container).
+
+Source: $(PHOBOSSRC std/container/_rbtree.d)
+
+Copyright: Red-black tree code copyright (C) 2008- by Steven Schveighoffer. Other code
+copyright 2010- Andrei Alexandrescu. All rights reserved by the respective holders.
+
+License: Distributed under the Boost Software License, Version 1.0.
+(See accompanying file LICENSE_1_0.txt or copy at $(HTTP
+boost.org/LICENSE_1_0.txt)).
+
+Authors: Steven Schveighoffer, $(HTTP erdani.com, Andrei Alexandrescu)
+*/
+module std.container.rbtree;
+
+///
+@safe pure unittest
+{
+    import std.algorithm.comparison : equal;
+    import std.container.rbtree;
+
+    auto rbt = redBlackTree(3, 1, 4, 2, 5);
+    assert(rbt.front == 1);
+    assert(equal(rbt[], [1, 2, 3, 4, 5]));
+
+    rbt.removeKey(1, 4);
+    assert(equal(rbt[], [2, 3, 5]));
+
+    rbt.removeFront();
+    assert(equal(rbt[], [3, 5]));
+
+    rbt.insert([1, 2, 4]);
+    assert(equal(rbt[], [1, 2, 3, 4, 5]));
+
+    // Query bounds in O(log(n))
+    assert(rbt.lowerBound(3).equal([1, 2]));
+    assert(rbt.equalRange(3).equal([3]));
+    assert(rbt.upperBound(3).equal([4, 5]));
+
+    // A Red Black tree with the highest element at front:
+    import std.range : iota;
+    auto maxTree = redBlackTree!"a > b"(iota(5));
+    assert(equal(maxTree[], [4, 3, 2, 1, 0]));
+
+    // adding duplicates will not add them, but return 0
+    auto rbt2 = redBlackTree(1, 3);
+    assert(rbt2.insert(1) == 0);
+    assert(equal(rbt2[], [1, 3]));
+    assert(rbt2.insert(2) == 1);
+
+    // however you can allow duplicates
+    auto ubt = redBlackTree!true([0, 1, 0, 1]);
+    assert(equal(ubt[], [0, 0, 1, 1]));
+}
+
+import std.format;
+import std.functional : binaryFun;
+
+public import std.container.util;
+
+version (unittest) debug = RBDoChecks;
+
+//debug = RBDoChecks;
+
+/*
+ * Implementation for a Red Black node for use in a Red Black Tree (see below)
+ *
+ * this implementation assumes we have a marker Node that is the parent of the
+ * root Node.  This marker Node is not a valid Node, but marks the end of the
+ * collection.  The root is the left child of the marker Node, so it is always
+ * last in the collection.  The marker Node is passed in to the setColor
+ * function, and the Node which has this Node as its parent is assumed to be
+ * the root Node.
+ *
+ * A Red Black tree should have O(lg(n)) insertion, removal, and search time.
+ */
+struct RBNode(V)
+{
+    /*
+     * Convenience alias
+     */
+    alias Node = RBNode*;
+
+    private Node _left;
+    private Node _right;
+    private Node _parent;
+
+    /**
+     * The value held by this node
+     */
+    V value;
+
+    /**
+     * Enumeration determining what color the node is.  Null nodes are assumed
+     * to be black.
+     */
+    enum Color : byte
+    {
+        Red,
+        Black
+    }
+
+    /**
+     * The color of the node.
+     */
+    Color color;
+
+    /**
+     * Get the left child
+     */
+    @property inout(RBNode)* left() inout
+    {
+        return _left;
+    }
+
+    /**
+     * Get the right child
+     */
+    @property inout(RBNode)* right() inout
+    {
+        return _right;
+    }
+
+    /**
+     * Get the parent
+     */
+    @property inout(RBNode)* parent() inout
+    {
+        return _parent;
+    }
+
+    /**
+     * Set the left child.  Also updates the new child's parent node.  This
+     * does not update the previous child.
+     *
+     * Returns newNode
+     */
+    @property Node left(Node newNode)
+    {
+        _left = newNode;
+        if (newNode !is null)
+            newNode._parent = &this;
+        return newNode;
+    }
+
+    /**
+     * Set the right child.  Also updates the new child's parent node.  This
+     * does not update the previous child.
+     *
+     * Returns newNode
+     */
+    @property Node right(Node newNode)
+    {
+        _right = newNode;
+        if (newNode !is null)
+            newNode._parent = &this;
+        return newNode;
+    }
+
+    // assume _left is not null
+    //
+    // performs rotate-right operation, where this is T, _right is R, _left is
+    // L, _parent is P:
+    //
+    //      P         P
+    //      |   ->    |
+    //      T         L
+    //     / \       / \
+    //    L   R     a   T
+    //   / \           / \
+    //  a   b         b   R
+    //
+    /**
+     * Rotate right.  This performs the following operations:
+     *  - The left child becomes the parent of this node.
+     *  - This node becomes the new parent's right child.
+     *  - The old right child of the new parent becomes the left child of this
+     *    node.
+     */
+    Node rotateR()
+    in
+    {
+        assert(_left !is null);
+    }
+    body
+    {
+        // sets _left._parent also
+        if (isLeftNode)
+            parent.left = _left;
+        else
+            parent.right = _left;
+        Node tmp = _left._right;
+
+        // sets _parent also
+        _left.right = &this;
+
+        // sets tmp._parent also
+        left = tmp;
+
+        return &this;
+    }
+
+    // assumes _right is non null
+    //
+    // performs rotate-left operation, where this is T, _right is R, _left is
+    // L, _parent is P:
+    //
+    //      P           P
+    //      |    ->     |
+    //      T           R
+    //     / \         / \
+    //    L   R       T   b
+    //       / \     / \
+    //      a   b   L   a
+    //
+    /**
+     * Rotate left.  This performs the following operations:
+     *  - The right child becomes the parent of this node.
+     *  - This node becomes the new parent's left child.
+     *  - The old left child of the new parent becomes the right child of this
+     *    node.
+     */
+    Node rotateL()
+    in
+    {
+        assert(_right !is null);
+    }
+    body
+    {
+        // sets _right._parent also
+        if (isLeftNode)
+            parent.left = _right;
+        else
+            parent.right = _right;
+        Node tmp = _right._left;
+
+        // sets _parent also
+        _right.left = &this;
+
+        // sets tmp._parent also
+        right = tmp;
+        return &this;
+    }
+
+
+    /**
+     * Returns true if this node is a left child.
+     *
+     * Note that this should always return a value because the root has a
+     * parent which is the marker node.
+     */
+    @property bool isLeftNode() const
+    in
+    {
+        assert(_parent !is null);
+    }
+    body
+    {
+        return _parent._left is &this;
+    }
+
+    /**
+     * Set the color of the node after it is inserted.  This performs an
+     * update to the whole tree, possibly rotating nodes to keep the Red-Black
+     * properties correct.  This is an O(lg(n)) operation, where n is the
+     * number of nodes in the tree.
+     *
+     * end is the marker node, which is the parent of the topmost valid node.
+     */
+    void setColor(Node end)
+    {
+        // test against the marker node
+        if (_parent !is end)
+        {
+            if (_parent.color == Color.Red)
+            {
+                Node cur = &this;
+                while (true)
+                {
+                    // because root is always black, _parent._parent always exists
+                    if (cur._parent.isLeftNode)
+                    {
+                        // parent is left node, y is 'uncle', could be null
+                        Node y = cur._parent._parent._right;
+                        if (y !is null && y.color == Color.Red)
+                        {
+                            cur._parent.color = Color.Black;
+                            y.color = Color.Black;
+                            cur = cur._parent._parent;
+                            if (cur._parent is end)
+                            {
+                                // root node
+                                cur.color = Color.Black;
+                                break;
+                            }
+                            else
+                            {
+                                // not root node
+                                cur.color = Color.Red;
+                                if (cur._parent.color == Color.Black)
+                                    // satisfied, exit the loop
+                                    break;
+                            }
+                        }
+                        else
+                        {
+                            if (!cur.isLeftNode)
+                                cur = cur._parent.rotateL();
+                            cur._parent.color = Color.Black;
+                            cur = cur._parent._parent.rotateR();
+                            cur.color = Color.Red;
+                            // tree should be satisfied now
+                            break;
+                        }
+                    }
+                    else
+                    {
+                        // parent is right node, y is 'uncle'
+                        Node y = cur._parent._parent._left;
+                        if (y !is null && y.color == Color.Red)
+                        {
+                            cur._parent.color = Color.Black;
+                            y.color = Color.Black;
+                            cur = cur._parent._parent;
+                            if (cur._parent is end)
+                            {
+                                // root node
+                                cur.color = Color.Black;
+                                break;
+                            }
+                            else
+                            {
+                                // not root node
+                                cur.color = Color.Red;
+                                if (cur._parent.color == Color.Black)
+                                    // satisfied, exit the loop
+                                    break;
+                            }
+                        }
+                        else
+                        {
+                            if (cur.isLeftNode)
+                                cur = cur._parent.rotateR();
+                            cur._parent.color = Color.Black;
+                            cur = cur._parent._parent.rotateL();
+                            cur.color = Color.Red;
+                            // tree should be satisfied now
+                            break;
+                        }
+                    }
+                }
+
+            }
+        }
+        else
+        {
+            //
+            // this is the root node, color it black
+            //
+            color = Color.Black;
+        }
+    }
+
+    /**
+     * Remove this node from the tree.  The 'end' node is used as the marker
+     * which is root's parent.  Note that this cannot be null!
+     *
+     * Returns the next highest valued node in the tree after this one, or end
+     * if this was the highest-valued node.
+     */
+    Node remove(Node end)
+    {
+        //
+        // remove this node from the tree, fixing the color if necessary.
+        //
+        Node x;
+        Node ret = next;
+
+        // if this node has 2 children
+        if (_left !is null && _right !is null)
+        {
+            //
+            // normally, we can just swap this node's and y's value, but
+            // because an iterator could be pointing to y and we don't want to
+            // disturb it, we swap this node and y's structure instead.  This
+            // can also be a benefit if the value of the tree is a large
+            // struct, which takes a long time to copy.
+            //
+            Node yp, yl, yr;
+            Node y = ret; // y = next
+            yp = y._parent;
+            yl = y._left;
+            yr = y._right;
+            auto yc = y.color;
+            auto isyleft = y.isLeftNode;
+
+            //
+            // replace y's structure with structure of this node.
+            //
+            if (isLeftNode)
+                _parent.left = y;
+            else
+                _parent.right = y;
+            //
+            // need special case so y doesn't point back to itself
+            //
+            y.left = _left;
+            if (_right is y)
+                y.right = &this;
+            else
+                y.right = _right;
+            y.color = color;
+
+            //
+            // replace this node's structure with structure of y.
+            //
+            left = yl;
+            right = yr;
+            if (_parent !is y)
+            {
+                if (isyleft)
+                    yp.left = &this;
+                else
+                    yp.right = &this;
+            }
+            color = yc;
+        }
+
+        // if this has less than 2 children, remove it
+        if (_left !is null)
+            x = _left;
+        else
+            x = _right;
+
+        bool deferedUnlink = false;
+        if (x is null)
+        {
+            // pretend this is a null node, defer unlinking the node
+            x = &this;
+            deferedUnlink = true;
+        }
+        else if (isLeftNode)
+            _parent.left = x;
+        else
+            _parent.right = x;
+
+        // if the color of this is black, then it needs to be fixed
+        if (color == color.Black)
+        {
+            // need to recolor the tree.
+            while (x._parent !is end && x.color == Node.Color.Black)
+            {
+                if (x.isLeftNode)
+                {
+                    // left node
+                    Node w = x._parent._right;
+                    if (w.color == Node.Color.Red)
+                    {
+                        w.color = Node.Color.Black;
+                        x._parent.color = Node.Color.Red;
+                        x._parent.rotateL();
+                        w = x._parent._right;
+                    }
+                    Node wl = w.left;
+                    Node wr = w.right;
+                    if ((wl is null || wl.color == Node.Color.Black) &&
+                            (wr is null || wr.color == Node.Color.Black))
+                    {
+                        w.color = Node.Color.Red;
+                        x = x._parent;
+                    }
+                    else
+                    {
+                        if (wr is null || wr.color == Node.Color.Black)
+                        {
+                            // wl cannot be null here
+                            wl.color = Node.Color.Black;
+                            w.color = Node.Color.Red;
+                            w.rotateR();
+                            w = x._parent._right;
+                        }
+
+                        w.color = x._parent.color;
+                        x._parent.color = Node.Color.Black;
+                        w._right.color = Node.Color.Black;
+                        x._parent.rotateL();
+                        x = end.left; // x = root
+                    }
+                }
+                else
+                {
+                    // right node
+                    Node w = x._parent._left;
+                    if (w.color == Node.Color.Red)
+                    {
+                        w.color = Node.Color.Black;
+                        x._parent.color = Node.Color.Red;
+                        x._parent.rotateR();
+                        w = x._parent._left;
+                    }
+                    Node wl = w.left;
+                    Node wr = w.right;
+                    if ((wl is null || wl.color == Node.Color.Black) &&
+                            (wr is null || wr.color == Node.Color.Black))
+                    {
+                        w.color = Node.Color.Red;
+                        x = x._parent;
+                    }
+                    else
+                    {
+                        if (wl is null || wl.color == Node.Color.Black)
+                        {
+                            // wr cannot be null here
+                            wr.color = Node.Color.Black;
+                            w.color = Node.Color.Red;
+                            w.rotateL();
+                            w = x._parent._left;
+                        }
+
+                        w.color = x._parent.color;
+                        x._parent.color = Node.Color.Black;
+                        w._left.color = Node.Color.Black;
+                        x._parent.rotateR();
+                        x = end.left; // x = root
+                    }
+                }
+            }
+            x.color = Node.Color.Black;
+        }
+
+        if (deferedUnlink)
+        {
+            //
+            // unlink this node from the tree
+            //
+            if (isLeftNode)
+                _parent.left = null;
+            else
+                _parent.right = null;
+        }
+
+        // clean references to help GC - Bugzilla 12915
+        _left = _right = _parent = null;
+
+        return ret;
+    }
+
+    /**
+     * Return the leftmost descendant of this node.
+     */
+    @property inout(RBNode)* leftmost() inout
+    {
+        inout(RBNode)* result = &this;
+        while (result._left !is null)
+            result = result._left;
+        return result;
+    }
+
+    /**
+     * Return the rightmost descendant of this node
+     */
+    @property inout(RBNode)* rightmost() inout
+    {
+        inout(RBNode)* result = &this;
+        while (result._right !is null)
+            result = result._right;
+        return result;
+    }
+
+    /**
+     * Returns the next valued node in the tree.
+     *
+     * You should never call this on the marker node, as it is assumed that
+     * there is a valid next node.
+     */
+    @property inout(RBNode)* next() inout
+    {
+        inout(RBNode)* n = &this;
+        if (n.right is null)
+        {
+            while (!n.isLeftNode)
+                n = n._parent;
+            return n._parent;
+        }
+        else
+            return n.right.leftmost;
+    }
+
+    /**
+     * Returns the previous valued node in the tree.
+     *
+     * You should never call this on the leftmost node of the tree as it is
+     * assumed that there is a valid previous node.
+     */
+    @property inout(RBNode)* prev() inout
+    {
+        inout(RBNode)* n = &this;
+        if (n.left is null)
+        {
+            while (n.isLeftNode)
+                n = n._parent;
+            return n._parent;
+        }
+        else
+            return n.left.rightmost;
+    }
+
+    Node dup(scope Node delegate(V v) alloc)
+    {
+        //
+        // duplicate this and all child nodes
+        //
+        // The recursion should be lg(n), so we shouldn't have to worry about
+        // stack size.
+        //
+        Node copy = alloc(value);
+        copy.color = color;
+        if (_left !is null)
+            copy.left = _left.dup(alloc);
+        if (_right !is null)
+            copy.right = _right.dup(alloc);
+        return copy;
+    }
+
+    Node dup()
+    {
+        Node copy = new RBNode!V(null, null, null, value);
+        copy.color = color;
+        if (_left !is null)
+            copy.left = _left.dup();
+        if (_right !is null)
+            copy.right = _right.dup();
+        return copy;
+    }
+}
+
+//constness checks
+@safe pure unittest
+{
+    const RBNode!int n;
+    static assert(is(typeof(n.leftmost)));
+    static assert(is(typeof(n.rightmost)));
+    static assert(is(typeof(n.next)));
+    static assert(is(typeof(n.prev)));
+}
+
+private struct RBRange(N)
+{
+    alias Node = N;
+    alias Elem = typeof(Node.value);
+
+    private Node _begin;
+    private Node _end;
+
+    private this(Node b, Node e)
+    {
+        _begin = b;
+        _end = e;
+    }
+
+    /**
+     * Returns $(D true) if the range is _empty
+     */
+    @property bool empty() const
+    {
+        return _begin is _end;
+    }
+
+    /**
+     * Returns the first element in the range
+     */
+    @property Elem front()
+    {
+        return _begin.value;
+    }
+
+    /**
+     * Returns the last element in the range
+     */
+    @property Elem back()
+    {
+        return _end.prev.value;
+    }
+
+    /**
+     * pop the front element from the range
+     *
+     * Complexity: amortized $(BIGOH 1)
+     */
+    void popFront()
+    {
+        _begin = _begin.next;
+    }
+
+    /**
+     * pop the back element from the range
+     *
+     * Complexity: amortized $(BIGOH 1)
+     */
+    void popBack()
+    {
+        _end = _end.prev;
+    }
+
+    /**
+     * Trivial _save implementation, needed for $(D isForwardRange).
+     */
+    @property RBRange save()
+    {
+        return this;
+    }
+}
+
+/**
+ * Implementation of a $(LINK2 https://en.wikipedia.org/wiki/Red%E2%80%93black_tree,
+ * red-black tree) container.
+ *
+ * All inserts, removes, searches, and any function in general has complexity
+ * of $(BIGOH lg(n)).
+ *
+ * To use a different comparison than $(D "a < b"), pass a different operator string
+ * that can be used by $(REF binaryFun, std,functional), or pass in a
+ * function, delegate, functor, or any type where $(D less(a, b)) results in a $(D bool)
+ * value.
+ *
+ * Note that less should produce a strict ordering.  That is, for two unequal
+ * elements $(D a) and $(D b), $(D less(a, b) == !less(b, a)). $(D less(a, a)) should
+ * always equal $(D false).
+ *
+ * If $(D allowDuplicates) is set to $(D true), then inserting the same element more than
+ * once continues to add more elements.  If it is $(D false), duplicate elements are
+ * ignored on insertion.  If duplicates are allowed, then new elements are
+ * inserted after all existing duplicate elements.
+ */
+final class RedBlackTree(T, alias less = "a < b", bool allowDuplicates = false)
+if (is(typeof(binaryFun!less(T.init, T.init))))
+{
+    import std.meta : allSatisfy;
+    import std.range : Take;
+    import std.range.primitives : isInputRange, walkLength;
+    import std.traits : isIntegral, isDynamicArray, isImplicitlyConvertible;
+
+    alias _less = binaryFun!less;
+
+    version (unittest)
+    {
+        static if (is(typeof(less) == string))
+        {
+            private enum doUnittest = isIntegral!T && (less == "a < b" || less == "a > b");
+        }
+        else
+            enum doUnittest = false;
+
+        // note, this must be final so it does not affect the vtable layout
+        bool arrayEqual(T[] arr)
+        {
+            if (walkLength(this[]) == arr.length)
+            {
+                foreach (v; arr)
+                {
+                    if (!(v in this))
+                        return false;
+                }
+                return true;
+            }
+            return false;
+        }
+    }
+    else
+    {
+        private enum doUnittest = false;
+    }
+
+    /**
+      * Element type for the tree
+      */
+    alias Elem = T;
+
+    // used for convenience
+    private alias RBNode = .RBNode!Elem;
+    private alias Node = RBNode.Node;
+
+    private Node   _end;
+    private Node   _begin;
+    private size_t _length;
+
+    private void _setup()
+    {
+        assert(!_end); //Make sure that _setup isn't run more than once.
+        _begin = _end = allocate();
+    }
+
+    static private Node allocate()
+    {
+        return new RBNode;
+    }
+
+    static private Node allocate(Elem v)
+    {
+        return new RBNode(null, null, null, v);
+    }
+
+    /**
+     * The range types for $(D RedBlackTree)
+     */
+    alias Range = RBRange!(RBNode*);
+    alias ConstRange = RBRange!(const(RBNode)*); /// Ditto
+    alias ImmutableRange = RBRange!(immutable(RBNode)*); /// Ditto
+
+    static if (doUnittest) @safe pure unittest
+    {
+        import std.algorithm.comparison : equal;
+        import std.range.primitives;
+        auto ts = new RedBlackTree(1, 2, 3, 4, 5);
+        assert(ts.length == 5);
+        auto r = ts[];
+
+        static if (less == "a < b")
+            auto vals = [1, 2, 3, 4, 5];
+        else
+            auto vals = [5, 4, 3, 2, 1];
+        assert(equal(r, vals));
+
+        assert(r.front == vals.front);
+        assert(r.back != r.front);
+        auto oldfront = r.front;
+        auto oldback = r.back;
+        r.popFront();
+        r.popBack();
+        assert(r.front != r.back);
+        assert(r.front != oldfront);
+        assert(r.back != oldback);
+        assert(ts.length == 5);
+    }
+
+    // find a node based on an element value
+    private inout(RBNode)* _find(Elem e) inout
+    {
+        static if (allowDuplicates)
+        {
+            inout(RBNode)* cur = _end.left;
+            inout(RBNode)* result = null;
+            while (cur)
+            {
+                if (_less(cur.value, e))
+                    cur = cur.right;
+                else if (_less(e, cur.value))
+                    cur = cur.left;
+                else
+                {
+                    // want to find the left-most element
+                    result = cur;
+                    cur = cur.left;
+                }
+            }
+            return result;
+        }
+        else
+        {
+            inout(RBNode)* cur = _end.left;
+            while (cur)
+            {
+                if (_less(cur.value, e))
+                    cur = cur.right;
+                else if (_less(e, cur.value))
+                    cur = cur.left;
+                else
+                    return cur;
+            }
+            return null;
+        }
+    }
+
+    // add an element to the tree, returns the node added, or the existing node
+    // if it has already been added and allowDuplicates is false
+    private auto _add(Elem n)
+    {
+        Node result;
+        static if (!allowDuplicates)
+            bool added = true;
+
+        if (!_end.left)
+        {
+            _end.left = _begin = result = allocate(n);
+        }
+        else
+        {
+            Node newParent = _end.left;
+            Node nxt;
+            while (true)
+            {
+                if (_less(n, newParent.value))
+                {
+                    nxt = newParent.left;
+                    if (nxt is null)
+                    {
+                        //
+                        // add to right of new parent
+                        //
+                        newParent.left = result = allocate(n);
+                        break;
+                    }
+                }
+                else
+                {
+                    static if (!allowDuplicates)
+                    {
+                        if (!_less(newParent.value, n))
+                        {
+                            result = newParent;
+                            added = false;
+                            break;
+                        }
+                    }
+                    nxt = newParent.right;
+                    if (nxt is null)
+                    {
+                        //
+                        // add to right of new parent
+                        //
+                        newParent.right = result = allocate(n);
+                        break;
+                    }
+                }
+                newParent = nxt;
+            }
+            if (_begin.left)
+                _begin = _begin.left;
+        }
+
+        static if (allowDuplicates)
+        {
+            result.setColor(_end);
+            debug(RBDoChecks)
+                check();
+            ++_length;
+            return result;
+        }
+        else
+        {
+            import std.typecons : Tuple;
+
+            if (added)
+            {
+                ++_length;
+                result.setColor(_end);
+            }
+            debug(RBDoChecks)
+                check();
+            return Tuple!(bool, "added", Node, "n")(added, result);
+        }
+    }
+
+
+    /**
+     * Check if any elements exist in the container.  Returns $(D false) if at least
+     * one element exists.
+     */
+    @property bool empty()
+    {
+        return _end.left is null;
+    }
+
+    /++
+        Returns the number of elements in the container.
+
+        Complexity: $(BIGOH 1).
+    +/
+    @property size_t length() const
+    {
+        return _length;
+    }
+
+    /**
+     * Duplicate this container.  The resulting container contains a shallow
+     * copy of the elements.
+     *
+     * Complexity: $(BIGOH n)
+     */
+    @property RedBlackTree dup()
+    {
+        return new RedBlackTree(_end.dup(), _length);
+    }
+
+    static if (doUnittest) @safe pure unittest
+    {
+        import std.algorithm.comparison : equal;
+        auto ts = new RedBlackTree(1, 2, 3, 4, 5);
+        assert(ts.length == 5);
+        auto ts2 = ts.dup;
+        assert(ts2.length == 5);
+        assert(equal(ts[], ts2[]));
+        ts2.insert(cast(Elem) 6);
+        assert(!equal(ts[], ts2[]));
+        assert(ts.length == 5 && ts2.length == 6);
+    }
+
+    /**
+     * Fetch a range that spans all the elements in the container.
+     *
+     * Complexity: $(BIGOH 1)
+     */
+    Range opSlice()
+    {
+        return Range(_begin, _end);
+    }
+
+    /// Ditto
+    ConstRange opSlice() const
+    {
+        return ConstRange(_begin, _end);
+    }
+
+    /// Ditto
+    ImmutableRange opSlice() immutable
+    {
+        return ImmutableRange(_begin, _end);
+    }
+
+    /**
+     * The front element in the container
+     *
+     * Complexity: $(BIGOH 1)
+     */
+    Elem front()
+    {
+        return _begin.value;
+    }
+
+    /**
+     * The last element in the container
+     *
+     * Complexity: $(BIGOH log(n))
+     */
+    Elem back()
+    {
+        return _end.prev.value;
+    }
+
+    /++
+        $(D in) operator. Check to see if the given element exists in the
+        container.
+
+       Complexity: $(BIGOH log(n))
+     +/
+    bool opBinaryRight(string op)(Elem e) const if (op == "in")
+    {
+        return _find(e) !is null;
+    }
+
+    static if (doUnittest) @safe pure unittest
+    {
+        auto ts = new RedBlackTree(1, 2, 3, 4, 5);
+        assert(cast(Elem) 3 in ts);
+        assert(cast(Elem) 6 !in ts);
+    }
+
+    /**
+     * Compares two trees for equality.
+     *
+     * Complexity: $(BIGOH n)
+     */
+    override bool opEquals(Object rhs)
+    {
+        import std.algorithm.comparison : equal;
+
+        RedBlackTree that = cast(RedBlackTree) rhs;
+        if (that is null) return false;
+
+        // If there aren't the same number of nodes, we can't be equal.
+        if (this._length != that._length) return false;
+
+        auto thisRange = this[];
+        auto thatRange = that[];
+        return equal!(function(Elem a, Elem b) => !_less(a,b) && !_less(b,a))
+                     (thisRange, thatRange);
+    }
+
+    static if (doUnittest) @system unittest
+    {
+        auto t1 = new RedBlackTree(1,2,3,4);
+        auto t2 = new RedBlackTree(1,2,3,4);
+        auto t3 = new RedBlackTree(1,2,3,5);
+        auto t4 = new RedBlackTree(1,2,3,4,5);
+        auto o = new Object();
+
+        assert(t1 == t1);
+        assert(t1 == t2);
+        assert(t1 != t3);
+        assert(t1 != t4);
+        assert(t1 != o);  // pathological case, must not crash
+    }
+
+    /**
+     * Removes all elements from the container.
+     *
+     * Complexity: $(BIGOH 1)
+     */
+    void clear()
+    {
+        _end.left = null;
+        _begin = _end;
+        _length = 0;
+    }
+
+    static if (doUnittest) @safe pure unittest
+    {
+        auto ts = new RedBlackTree(1,2,3,4,5);
+        assert(ts.length == 5);
+        ts.clear();
+        assert(ts.empty && ts.length == 0);
+    }
+
+    /**
+     * Insert a single element in the container.  Note that this does not
+     * invalidate any ranges currently iterating the container.
+     *
+     * Returns: The number of elements inserted.
+     *
+     * Complexity: $(BIGOH log(n))
+     */
+    size_t stableInsert(Stuff)(Stuff stuff) if (isImplicitlyConvertible!(Stuff, Elem))
+    {
+        static if (allowDuplicates)
+        {
+            _add(stuff);
+            return 1;
+        }
+        else
+        {
+            return(_add(stuff).added ? 1 : 0);
+        }
+    }
+
+    /**
+     * Insert a range of elements in the container.  Note that this does not
+     * invalidate any ranges currently iterating the container.
+     *
+     * Returns: The number of elements inserted.
+     *
+     * Complexity: $(BIGOH m * log(n))
+     */
+    size_t stableInsert(Stuff)(Stuff stuff) if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, Elem))
+    {
+        size_t result = 0;
+        static if (allowDuplicates)
+        {
+            foreach (e; stuff)
+            {
+                ++result;
+                _add(e);
+            }
+        }
+        else
+        {
+            foreach (e; stuff)
+            {
+                if (_add(e).added)
+                    ++result;
+            }
+        }
+        return result;
+    }
+
+    /// ditto
+    alias insert = stableInsert;
+
+    static if (doUnittest) @safe pure unittest
+    {
+        auto ts = new RedBlackTree(2,1,3,4,5,2,5);
+        static if (allowDuplicates)
+        {
+            assert(ts.length == 7);
+            assert(ts.stableInsert(cast(Elem[])[7, 8, 6, 9, 10, 8]) == 6);
+            assert(ts.length == 13);
+            assert(ts.stableInsert(cast(Elem) 11) == 1 && ts.length == 14);
+            assert(ts.stableInsert(cast(Elem) 7) == 1 && ts.length == 15);
+
+            static if (less == "a < b")
+                assert(ts.arrayEqual([1,2,2,3,4,5,5,6,7,7,8,8,9,10,11]));
+            else
+                assert(ts.arrayEqual([11,10,9,8,8,7,7,6,5,5,4,3,2,2,1]));
+        }
+        else
+        {
+            assert(ts.length == 5);
+            Elem[] elems = [7, 8, 6, 9, 10, 8];
+            assert(ts.stableInsert(elems) == 5);
+            assert(ts.length == 10);
+            assert(ts.stableInsert(cast(Elem) 11) == 1 && ts.length == 11);
+            assert(ts.stableInsert(cast(Elem) 7) == 0 && ts.length == 11);
+
+            static if (less == "a < b")
+                assert(ts.arrayEqual([1,2,3,4,5,6,7,8,9,10,11]));
+            else
+                assert(ts.arrayEqual([11,10,9,8,7,6,5,4,3,2,1]));
+        }
+    }
+
+    /**
+     * Remove an element from the container and return its value.
+     *
+     * Complexity: $(BIGOH log(n))
+     */
+    Elem removeAny()
+    {
+        scope(success)
+            --_length;
+        auto n = _begin;
+        auto result = n.value;
+        _begin = n.remove(_end);
+        debug(RBDoChecks)
+            check();
+        return result;
+    }
+
+    static if (doUnittest) @safe pure unittest
+    {
+        auto ts = new RedBlackTree(1,2,3,4,5);
+        assert(ts.length == 5);
+        auto x = ts.removeAny();
+        assert(ts.length == 4);
+        Elem[] arr;
+        foreach (Elem i; 1 .. 6)
+            if (i != x) arr ~= i;
+        assert(ts.arrayEqual(arr));
+    }
+
+    /**
+     * Remove the front element from the container.
+     *
+     * Complexity: $(BIGOH log(n))
+     */
+    void removeFront()
+    {
+        scope(success)
+            --_length;
+        _begin = _begin.remove(_end);
+        debug(RBDoChecks)
+            check();
+    }
+
+    /**
+     * Remove the back element from the container.
+     *
+     * Complexity: $(BIGOH log(n))
+     */
+    void removeBack()
+    {
+        scope(success)
+            --_length;
+        auto lastnode = _end.prev;
+        if (lastnode is _begin)
+            _begin = _begin.remove(_end);
+        else
+            lastnode.remove(_end);
+        debug(RBDoChecks)
+            check();
+    }
+
+    static if (doUnittest) @safe pure unittest
+    {
+        auto ts = new RedBlackTree(1,2,3,4,5);
+        assert(ts.length == 5);
+        ts.removeBack();
+        assert(ts.length == 4);
+
+        static if (less == "a < b")
+            assert(ts.arrayEqual([1,2,3,4]));
+        else
+            assert(ts.arrayEqual([2,3,4,5]));
+
+        ts.removeFront();
+        assert(ts.arrayEqual([2,3,4]) && ts.length == 3);
+    }
+
+    /++
+        Removes the given range from the container.
+
+        Returns: A range containing all of the elements that were after the
+                 given range.
+
+        Complexity: $(BIGOH m * log(n)) (where m is the number of elements in
+                    the range)
+     +/
+    Range remove(Range r)
+    {
+        auto b = r._begin;
+        auto e = r._end;
+        if (_begin is b)
+            _begin = e;
+        while (b !is e)
+        {
+            b = b.remove(_end);
+            --_length;
+        }
+        debug(RBDoChecks)
+            check();
+        return Range(e, _end);
+    }
+
+    static if (doUnittest) @safe pure unittest
+    {
+        import std.algorithm.comparison : equal;
+        auto ts = new RedBlackTree(1,2,3,4,5);
+        assert(ts.length == 5);
+        auto r = ts[];
+        r.popFront();
+        r.popBack();
+        assert(ts.length == 5);
+        auto r2 = ts.remove(r);
+        assert(ts.length == 2);
+        assert(ts.arrayEqual([1,5]));
+
+        static if (less == "a < b")
+            assert(equal(r2, [5]));
+        else
+            assert(equal(r2, [1]));
+    }
+
+    /++
+        Removes the given $(D Take!Range) from the container
+
+        Returns: A range containing all of the elements that were after the
+                 given range.
+
+        Complexity: $(BIGOH m * log(n)) (where m is the number of elements in
+                    the range)
+     +/
+    Range remove(Take!Range r)
+    {
+        immutable isBegin = (r.source._begin is _begin);
+        auto b = r.source._begin;
+
+        while (!r.empty)
+        {
+            r.popFront();
+            b = b.remove(_end);
+            --_length;
+        }
+
+        if (isBegin)
+            _begin = b;
+
+        return Range(b, _end);
+    }
+
+    static if (doUnittest) @safe pure unittest
+    {
+        import std.algorithm.comparison : equal;
+        import std.range : take;
+        auto ts = new RedBlackTree(1,2,3,4,5);
+        auto r = ts[];
+        r.popFront();
+        assert(ts.length == 5);
+        auto r2 = ts.remove(take(r, 0));
+
+        static if (less == "a < b")
+        {
+            assert(equal(r2, [2,3,4,5]));
+            auto r3 = ts.remove(take(r, 2));
+            assert(ts.arrayEqual([1,4,5]) && ts.length == 3);
+            assert(equal(r3, [4,5]));
+        }
+        else
+        {
+            assert(equal(r2, [4,3,2,1]));
+            auto r3 = ts.remove(take(r, 2));
+            assert(ts.arrayEqual([5,2,1]) && ts.length == 3);
+            assert(equal(r3, [2,1]));
+        }
+    }
+
+    /++
+       Removes elements from the container that are equal to the given values
+       according to the less comparator. One element is removed for each value
+       given which is in the container. If $(D allowDuplicates) is true,
+       duplicates are removed only if duplicate values are given.
+
+       Returns: The number of elements removed.
+
+       Complexity: $(BIGOH m log(n)) (where m is the number of elements to remove)
+
+       Example:
+--------------------
+auto rbt = redBlackTree!true(0, 1, 1, 1, 4, 5, 7);
+rbt.removeKey(1, 4, 7);
+assert(equal(rbt[], [0, 1, 1, 5]));
+rbt.removeKey(1, 1, 0);
+assert(equal(rbt[], [5]));
+--------------------
+      +/
+    size_t removeKey(U...)(U elems)
+        if (allSatisfy!(isImplicitlyConvertibleToElem, U))
+    {
+        Elem[U.length] toRemove = [elems];
+        return removeKey(toRemove[]);
+    }
+
+    /++ Ditto +/
+    size_t removeKey(U)(U[] elems)
+        if (isImplicitlyConvertible!(U, Elem))
+    {
+        immutable lenBefore = length;
+
+        foreach (e; elems)
+        {
+            auto beg = _firstGreaterEqual(e);
+            if (beg is _end || _less(e, beg.value))
+                // no values are equal
+                continue;
+            immutable isBegin = (beg is _begin);
+            beg = beg.remove(_end);
+            if (isBegin)
+                _begin = beg;
+            --_length;
+        }
+
+        return lenBefore - length;
+    }
+
+    /++ Ditto +/
+    size_t removeKey(Stuff)(Stuff stuff)
+        if (isInputRange!Stuff &&
+           isImplicitlyConvertible!(ElementType!Stuff, Elem) &&
+           !isDynamicArray!Stuff)
+    {
+        import std.array : array;
+        //We use array in case stuff is a Range from this RedBlackTree - either
+        //directly or indirectly.
+        return removeKey(array(stuff));
+    }
+
+    //Helper for removeKey.
+    private template isImplicitlyConvertibleToElem(U)
+    {
+        enum isImplicitlyConvertibleToElem = isImplicitlyConvertible!(U, Elem);
+    }
+
+    static if (doUnittest) @safe pure unittest
+    {
+        import std.algorithm.comparison : equal;
+        import std.range : take;
+        auto rbt = new RedBlackTree(5, 4, 3, 7, 2, 1, 7, 6, 2, 19, 45);
+
+        //The cast(Elem) is because these tests are instantiated with a variety
+        //of numeric types, and the literals are all int, which is not always
+        //implicitly convertible to Elem (e.g. short).
+        static if (allowDuplicates)
+        {
+            assert(rbt.length == 11);
+            assert(rbt.removeKey(cast(Elem) 4) == 1 && rbt.length == 10);
+            assert(rbt.arrayEqual([1,2,2,3,5,6,7,7,19,45]) && rbt.length == 10);
+
+            assert(rbt.removeKey(cast(Elem) 6, cast(Elem) 2, cast(Elem) 1) == 3);
+            assert(rbt.arrayEqual([2,3,5,7,7,19,45]) && rbt.length == 7);
+
+            assert(rbt.removeKey(cast(Elem)(42)) == 0 && rbt.length == 7);
+            assert(rbt.removeKey(take(rbt[], 3)) == 3 && rbt.length == 4);
+
+            static if (less == "a < b")
+                assert(equal(rbt[], [7,7,19,45]));
+            else
+                assert(equal(rbt[], [7,5,3,2]));
+        }
+        else
+        {
+            assert(rbt.length == 9);
+            assert(rbt.removeKey(cast(Elem) 4) == 1 && rbt.length == 8);
+            assert(rbt.arrayEqual([1,2,3,5,6,7,19,45]));
+
+            assert(rbt.removeKey(cast(Elem) 6, cast(Elem) 2, cast(Elem) 1) == 3);
+            assert(rbt.arrayEqual([3,5,7,19,45]) && rbt.length == 5);
+
+            assert(rbt.removeKey(cast(Elem)(42)) == 0 && rbt.length == 5);
+            assert(rbt.removeKey(take(rbt[], 3)) == 3 && rbt.length == 2);
+
+            static if (less == "a < b")
+                assert(equal(rbt[], [19,45]));
+            else
+                assert(equal(rbt[], [5,3]));
+        }
+    }
+
+    // find the first node where the value is > e
+    private inout(RBNode)* _firstGreater(Elem e) inout
+    {
+        // can't use _find, because we cannot return null
+        auto cur = _end.left;
+        inout(RBNode)* result = _end;
+        while (cur)
+        {
+            if (_less(e, cur.value))
+            {
+                result = cur;
+                cur = cur.left;
+            }
+            else
+                cur = cur.right;
+        }
+        return result;
+    }
+
+    // find the first node where the value is >= e
+    private inout(RBNode)* _firstGreaterEqual(Elem e) inout
+    {
+        // can't use _find, because we cannot return null.
+        auto cur = _end.left;
+        inout(RBNode)* result = _end;
+        while (cur)
+        {
+            if (_less(cur.value, e))
+                cur = cur.right;
+            else
+            {
+                result = cur;
+                cur = cur.left;
+            }
+
+        }
+        return result;
+    }
+
+    /**
+     * Get a range from the container with all elements that are > e according
+     * to the less comparator
+     *
+     * Complexity: $(BIGOH log(n))
+     */
+    Range upperBound(Elem e)
+    {
+        return Range(_firstGreater(e), _end);
+    }
+
+    /// Ditto
+    ConstRange upperBound(Elem e) const
+    {
+        return ConstRange(_firstGreater(e), _end);
+    }
+
+    /// Ditto
+    ImmutableRange upperBound(Elem e) immutable
+    {
+        return ImmutableRange(_firstGreater(e), _end);
+    }
+
+    /**
+     * Get a range from the container with all elements that are < e according
+     * to the less comparator
+     *
+     * Complexity: $(BIGOH log(n))
+     */
+    Range lowerBound(Elem e)
+    {
+        return Range(_begin, _firstGreaterEqual(e));
+    }
+
+    /// Ditto
+    ConstRange lowerBound(Elem e) const
+    {
+        return ConstRange(_begin, _firstGreaterEqual(e));
+    }
+
+    /// Ditto
+    ImmutableRange lowerBound(Elem e) immutable
+    {
+        return ImmutableRange(_begin, _firstGreaterEqual(e));
+    }
+
+    /**
+     * Get a range from the container with all elements that are == e according
+     * to the less comparator
+     *
+     * Complexity: $(BIGOH log(n))
+     */
+    auto equalRange(this This)(Elem e)
+    {
+        auto beg = _firstGreaterEqual(e);
+        alias RangeType = RBRange!(typeof(beg));
+        if (beg is _end || _less(e, beg.value))
+            // no values are equal
+            return RangeType(beg, beg);
+        static if (allowDuplicates)
+        {
+            return RangeType(beg, _firstGreater(e));
+        }
+        else
+        {
+            // no sense in doing a full search, no duplicates are allowed,
+            // so we just get the next node.
+            return RangeType(beg, beg.next);
+        }
+    }
+
+    static if (doUnittest) @safe pure unittest
+    {
+        import std.algorithm.comparison : equal;
+        auto ts = new RedBlackTree(1, 2, 3, 4, 5);
+        auto rl = ts.lowerBound(3);
+        auto ru = ts.upperBound(3);
+        auto re = ts.equalRange(3);
+
+        static if (less == "a < b")
+        {
+            assert(equal(rl, [1,2]));
+            assert(equal(ru, [4,5]));
+        }
+        else
+        {
+            assert(equal(rl, [5,4]));
+            assert(equal(ru, [2,1]));
+        }
+
+        assert(equal(re, [3]));
+    }
+
+    debug(RBDoChecks)
+    {
+        /*
+         * Print the tree.  This prints a sideways view of the tree in ASCII form,
+         * with the number of indentations representing the level of the nodes.
+         * It does not print values, only the tree structure and color of nodes.
+         */
+        void printTree(Node n, int indent = 0)
+        {
+            import std.stdio : write, writeln;
+            if (n !is null)
+            {
+                printTree(n.right, indent + 2);
+                for (int i = 0; i < indent; i++)
+                    write(".");
+                writeln(n.color == n.color.Black ? "B" : "R");
+                printTree(n.left, indent + 2);
+            }
+            else
+            {
+                for (int i = 0; i < indent; i++)
+                    write(".");
+                writeln("N");
+            }
+            if (indent is 0)
+                writeln();
+        }
+
+        /*
+         * Check the tree for validity.  This is called after every add or remove.
+         * This should only be enabled to debug the implementation of the RB Tree.
+         */
+        void check()
+        {
+            //
+            // check implementation of the tree
+            //
+            int recurse(Node n, string path)
+            {
+                import std.stdio : writeln;
+                if (n is null)
+                    return 1;
+                if (n.parent.left !is n && n.parent.right !is n)
+                    throw new Exception("Node at path " ~ path ~ " has inconsistent pointers");
+                Node next = n.next;
+                static if (allowDuplicates)
+                {
+                    if (next !is _end && _less(next.value, n.value))
+                        throw new Exception("ordering invalid at path " ~ path);
+                }
+                else
+                {
+                    if (next !is _end && !_less(n.value, next.value))
+                        throw new Exception("ordering invalid at path " ~ path);
+                }
+                if (n.color == n.color.Red)
+                {
+                    if ((n.left !is null && n.left.color == n.color.Red) ||
+                            (n.right !is null && n.right.color == n.color.Red))
+                        throw new Exception("Node at path " ~ path ~ " is red with a red child");
+                }
+
+                int l = recurse(n.left, path ~ "L");
+                int r = recurse(n.right, path ~ "R");
+                if (l != r)
+                {
+                    writeln("bad tree at:");
+                    debug printTree(n);
+                    throw new Exception(
+                        "Node at path " ~ path ~ " has different number of black nodes on left and right paths"
+                    );
+                }
+                return l + (n.color == n.color.Black ? 1 : 0);
+            }
+
+            try
+            {
+                recurse(_end.left, "");
+            }
+            catch (Exception e)
+            {
+                debug printTree(_end.left, 0);
+                throw e;
+            }
+        }
+    }
+
+    /**
+      Formats the RedBlackTree into a sink function. For more info see $(D
+      std.format.formatValue). Note that this only is available when the
+      element type can be formatted. Otherwise, the default toString from
+      Object is used.
+     */
+    static if (is(typeof((){FormatSpec!(char) fmt; formatValue((const(char)[]) {}, ConstRange.init, fmt);})))
+    {
+        void toString(scope void delegate(const(char)[]) sink, FormatSpec!char fmt) const {
+            sink("RedBlackTree(");
+            sink.formatValue(this[], fmt);
+            sink(")");
+        }
+    }
+
+    /**
+     * Constructor. Pass in an array of elements, or individual elements to
+     * initialize the tree with.
+     */
+    this(Elem[] elems...)
+    {
+        _setup();
+        stableInsert(elems);
+    }
+
+    /**
+     * Constructor. Pass in a range of elements to initialize the tree with.
+     */
+    this(Stuff)(Stuff stuff) if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, Elem))
+    {
+        _setup();
+        stableInsert(stuff);
+    }
+
+    ///
+    this()
+    {
+        _setup();
+    }
+
+    private this(Node end, size_t length)
+    {
+        _end = end;
+        _begin = end.leftmost;
+        _length = length;
+    }
+}
+
+//Verify Example for removeKey.
+@safe pure unittest
+{
+    import std.algorithm.comparison : equal;
+    auto rbt = redBlackTree!true(0, 1, 1, 1, 4, 5, 7);
+    rbt.removeKey(1, 4, 7);
+    assert(equal(rbt[], [0, 1, 1, 5]));
+    rbt.removeKey(1, 1, 0);
+    assert(equal(rbt[], [5]));
+}
+
+//Tests for removeKey
+@safe pure unittest
+{
+    import std.algorithm.comparison : equal;
+    {
+        auto rbt = redBlackTree(["hello", "world", "foo", "bar"]);
+        assert(equal(rbt[], ["bar", "foo", "hello", "world"]));
+        assert(rbt.removeKey("hello") == 1);
+        assert(equal(rbt[], ["bar", "foo", "world"]));
+        assert(rbt.removeKey("hello") == 0);
+        assert(equal(rbt[], ["bar", "foo", "world"]));
+        assert(rbt.removeKey("hello", "foo", "bar") == 2);
+        assert(equal(rbt[], ["world"]));
+        assert(rbt.removeKey(["", "world", "hello"]) == 1);
+        assert(rbt.empty);
+    }
+
+    {
+        auto rbt = redBlackTree([1, 2, 12, 27, 4, 500]);
+        assert(equal(rbt[], [1, 2, 4, 12, 27, 500]));
+        assert(rbt.removeKey(1u) == 1);
+        assert(equal(rbt[], [2, 4, 12, 27, 500]));
+        assert(rbt.removeKey(cast(byte) 1) == 0);
+        assert(equal(rbt[], [2, 4, 12, 27, 500]));
+        assert(rbt.removeKey(1, 12u, cast(byte) 27) == 2);
+        assert(equal(rbt[], [2, 4, 500]));
+        assert(rbt.removeKey([cast(short) 0, cast(short) 500, cast(short) 1]) == 1);
+        assert(equal(rbt[], [2, 4]));
+    }
+}
+
+@safe pure unittest
+{
+    void test(T)()
+    {
+        auto rt1 = new RedBlackTree!(T, "a < b", false)();
+        auto rt2 = new RedBlackTree!(T, "a < b", true)();
+        auto rt3 = new RedBlackTree!(T, "a > b", false)();
+        auto rt4 = new RedBlackTree!(T, "a > b", true)();
+    }
+
+    test!long();
+    test!ulong();
+    test!int();
+    test!uint();
+    test!short();
+    test!ushort();
+    test!byte();
+    test!byte();
+}
+
+import std.range.primitives : isInputRange, isSomeString, ElementType;
+import std.traits : isArray;
+
+/++
+    Convenience function for creating a $(D RedBlackTree!E) from a list of
+    values.
+
+    Params:
+        allowDuplicates =  Whether duplicates should be allowed (optional, default: false)
+        less = predicate to sort by (optional)
+        elems = elements to insert into the rbtree (variadic arguments)
+        range = range elements to insert into the rbtree (alternative to elems)
+  +/
+auto redBlackTree(E)(E[] elems...)
+{
+    return new RedBlackTree!E(elems);
+}
+
+/++ Ditto +/
+auto redBlackTree(bool allowDuplicates, E)(E[] elems...)
+{
+    return new RedBlackTree!(E, "a < b", allowDuplicates)(elems);
+}
+
+/++ Ditto +/
+auto redBlackTree(alias less, E)(E[] elems...)
+if (is(typeof(binaryFun!less(E.init, E.init))))
+{
+    return new RedBlackTree!(E, less)(elems);
+}
+
+/++ Ditto +/
+auto redBlackTree(alias less, bool allowDuplicates, E)(E[] elems...)
+if (is(typeof(binaryFun!less(E.init, E.init))))
+{
+    //We shouldn't need to instantiate less here, but for some reason,
+    //dmd can't handle it if we don't (even though the template which
+    //takes less but not allowDuplicates works just fine).
+    return new RedBlackTree!(E, binaryFun!less, allowDuplicates)(elems);
+}
+
+/++ Ditto +/
+auto redBlackTree(Stuff)(Stuff range)
+if (isInputRange!Stuff && !isArray!(Stuff))
+{
+    return new RedBlackTree!(ElementType!Stuff)(range);
+}
+
+/++ Ditto +/
+auto redBlackTree(bool allowDuplicates, Stuff)(Stuff range)
+if (isInputRange!Stuff && !isArray!(Stuff))
+{
+    return new RedBlackTree!(ElementType!Stuff, "a < b", allowDuplicates)(range);
+}
+
+/++ Ditto +/
+auto redBlackTree(alias less, Stuff)(Stuff range)
+if ( is(typeof(binaryFun!less((ElementType!Stuff).init, (ElementType!Stuff).init)))
+    && isInputRange!Stuff && !isArray!(Stuff))
+{
+    return new RedBlackTree!(ElementType!Stuff, less)(range);
+}
+
+/++ Ditto +/
+auto redBlackTree(alias less, bool allowDuplicates, Stuff)(Stuff range)
+if ( is(typeof(binaryFun!less((ElementType!Stuff).init, (ElementType!Stuff).init)))
+    && isInputRange!Stuff && !isArray!(Stuff))
+{
+    //We shouldn't need to instantiate less here, but for some reason,
+    //dmd can't handle it if we don't (even though the template which
+    //takes less but not allowDuplicates works just fine).
+    return new RedBlackTree!(ElementType!Stuff, binaryFun!less, allowDuplicates)(range);
+}
+
+///
+@safe pure unittest
+{
+    import std.range : iota;
+
+    auto rbt1 = redBlackTree(0, 1, 5, 7);
+    auto rbt2 = redBlackTree!string("hello", "world");
+    auto rbt3 = redBlackTree!true(0, 1, 5, 7, 5);
+    auto rbt4 = redBlackTree!"a > b"(0, 1, 5, 7);
+    auto rbt5 = redBlackTree!("a > b", true)(0.1, 1.3, 5.9, 7.2, 5.9);
+
+    // also works with ranges
+    auto rbt6 = redBlackTree(iota(3));
+    auto rbt7 = redBlackTree!true(iota(3));
+    auto rbt8 = redBlackTree!"a > b"(iota(3));
+    auto rbt9 = redBlackTree!("a > b", true)(iota(3));
+}
+
+//Combinations not in examples.
+@safe pure unittest
+{
+    auto rbt1 = redBlackTree!(true, string)("hello", "hello");
+    auto rbt2 = redBlackTree!((a, b){return a < b;}, double)(5.1, 2.3);
+    auto rbt3 = redBlackTree!("a > b", true, string)("hello", "world");
+}
+
+//Range construction.
+@safe pure unittest
+{
+    import std.algorithm.comparison : equal;
+    import std.range : iota;
+    auto rbt = new RedBlackTree!(int, "a > b")(iota(5));
+    assert(equal(rbt[], [4, 3, 2, 1, 0]));
+}
+
+
+// construction with arrays
+@safe pure unittest
+{
+    import std.algorithm.comparison : equal;
+
+    auto rbt = redBlackTree!"a > b"([0, 1, 2, 3, 4]);
+    assert(equal(rbt[], [4, 3, 2, 1, 0]));
+
+    auto rbt2 = redBlackTree!"a > b"(["a", "b"]);
+    assert(equal(rbt2[], ["b", "a"]));
+
+    auto rbt3 = redBlackTree!"a > b"([1, 2]);
+    assert(equal(rbt3[], [2, 1]));
+
+    auto rbt4 = redBlackTree([0, 1, 7, 5]);
+    assert(equal(rbt4[], [0, 1, 5, 7]));
+
+    auto rbt5 = redBlackTree(["hello", "world"]);
+    assert(equal(rbt5[], ["hello", "world"]));
+
+    auto rbt6 = redBlackTree!true([0, 1, 5, 7, 5]);
+    assert(equal(rbt6[], [0, 1, 5, 5, 7]));
+
+    auto rbt7 = redBlackTree!"a > b"([0, 1, 5, 7]);
+    assert(equal(rbt7[], [7, 5, 1, 0]));
+
+    auto rbt8 = redBlackTree!("a > b", true)([0.1, 1.3, 5.9, 7.2, 5.9]);
+    assert(equal(rbt8[], [7.2, 5.9, 5.9, 1.3, 0.1]));
+}
+
+// convenience wrapper range construction
+@safe pure unittest
+{
+    import std.algorithm.comparison : equal;
+    import std.range : chain, iota;
+
+    auto rbt = redBlackTree(iota(3));
+    assert(equal(rbt[], [0, 1, 2]));
+
+    auto rbt2 = redBlackTree!"a > b"(iota(2));
+    assert(equal(rbt2[], [1, 0]));
+
+    auto rbt3 = redBlackTree(chain([0, 1], [7, 5]));
+    assert(equal(rbt3[], [0, 1, 5, 7]));
+
+    auto rbt4 = redBlackTree(chain(["hello"], ["world"]));
+    assert(equal(rbt4[], ["hello", "world"]));
+
+    auto rbt5 = redBlackTree!true(chain([0, 1], [5, 7, 5]));
+    assert(equal(rbt5[], [0, 1, 5, 5, 7]));
+
+    auto rbt6 = redBlackTree!("a > b", true)(chain([0.1, 1.3], [5.9, 7.2, 5.9]));
+    assert(equal(rbt6[], [7.2, 5.9, 5.9, 1.3, 0.1]));
+}
+
+@safe pure unittest
+{
+    import std.array : array;
+
+    auto rt1 = redBlackTree(5, 4, 3, 2, 1);
+    assert(rt1.length == 5);
+    assert(array(rt1[]) == [1, 2, 3, 4, 5]);
+
+    auto rt2 = redBlackTree!"a > b"(1.1, 2.1);
+    assert(rt2.length == 2);
+    assert(array(rt2[]) == [2.1, 1.1]);
+
+    auto rt3 = redBlackTree!true(5, 5, 4);
+    assert(rt3.length == 3);
+    assert(array(rt3[]) == [4, 5, 5]);
+
+    auto rt4 = redBlackTree!string("hello", "hello");
+    assert(rt4.length == 1);
+    assert(array(rt4[]) == ["hello"]);
+}
+
+@system unittest
+{
+    import std.conv : to;
+
+    auto rt1 = redBlackTree!string();
+    assert(rt1.to!string == "RedBlackTree([])");
+
+    auto rt2 = redBlackTree!string("hello");
+    assert(rt2.to!string == "RedBlackTree([\"hello\"])");
+
+    auto rt3 = redBlackTree!string("hello", "world", "!");
+    assert(rt3.to!string == "RedBlackTree([\"!\", \"hello\", \"world\"])");
+
+    // type deduction can be done automatically
+    auto rt4 = redBlackTree(["hello"]);
+    assert(rt4.to!string == "RedBlackTree([\"hello\"])");
+}
+
+//constness checks
+@safe pure unittest
+{
+    const rt1 = redBlackTree(5,4,3,2,1);
+    static assert(is(typeof(rt1.length)));
+    static assert(is(typeof(5 in rt1)));
+
+    static assert(is(typeof(rt1.upperBound(3).front) == const(int)));
+    import std.algorithm.comparison : equal;
+    assert(rt1.upperBound(3).equal([4, 5]));
+    assert(rt1.lowerBound(3).equal([1, 2]));
+    assert(rt1.equalRange(3).equal([3]));
+    assert(rt1[].equal([1, 2, 3, 4, 5]));
+}
+
+//immutable checks
+@safe pure unittest
+{
+    immutable rt1 = redBlackTree(5,4,3,2,1);
+    static assert(is(typeof(rt1.length)));
+
+    static assert(is(typeof(rt1.upperBound(3).front) == immutable(int)));
+    import std.algorithm.comparison : equal;
+    assert(rt1.upperBound(2).equal([3, 4, 5]));
+}
+
+// issue 15941
+@safe pure unittest
+{
+    class C {}
+    RedBlackTree!(C, "cast(void*)a < cast(void*) b") tree;
+}
+
+@safe pure unittest // const/immutable elements (issue 17519)
+{
+    RedBlackTree!(immutable int) t1;
+    RedBlackTree!(const int) t2;
+
+    import std.algorithm.iteration : map;
+    static struct S { int* p; }
+    auto t3 = new RedBlackTree!(immutable S, (a, b) => *a.p < *b.p);
+    t3.insert([1, 2, 3].map!(x => immutable S(new int(x))));
+    static assert(!__traits(compiles, *t3.front.p = 4));
+    assert(*t3.front.p == 1);
+}
diff --git a/libphobos/src/std/container/slist.d b/libphobos/src/std/container/slist.d
new file mode 100644
index 0000000..820b0bb
--- /dev/null
+++ b/libphobos/src/std/container/slist.d
@@ -0,0 +1,846 @@
+/**
+This module implements a singly-linked list container.
+It can be used as a stack.
+
+This module is a submodule of $(MREF std, container).
+
+Source: $(PHOBOSSRC std/container/_slist.d)
+
+Copyright: 2010- Andrei Alexandrescu. All rights reserved by the respective holders.
+
+License: Distributed under the Boost Software License, Version 1.0.
+(See accompanying file LICENSE_1_0.txt or copy at $(HTTP
+boost.org/LICENSE_1_0.txt)).
+
+Authors: $(HTTP erdani.com, Andrei Alexandrescu)
+
+$(SCRIPT inhibitQuickIndex = 1;)
+*/
+module std.container.slist;
+
+///
+@safe unittest
+{
+    import std.algorithm.comparison : equal;
+    import std.container : SList;
+
+    auto s = SList!int(1, 2, 3);
+    assert(equal(s[], [1, 2, 3]));
+
+    s.removeFront();
+    assert(equal(s[], [2, 3]));
+
+    s.insertFront([5, 6]);
+    assert(equal(s[], [5, 6, 2, 3]));
+
+    // If you want to apply range operations, simply slice it.
+    import std.algorithm.searching : countUntil;
+    import std.range : popFrontN, walkLength;
+
+    auto sl = SList!int(1, 2, 3, 4, 5);
+    assert(countUntil(sl[], 2) == 1);
+
+    auto r = sl[];
+    popFrontN(r, 2);
+    assert(walkLength(r) == 3);
+}
+
+public import std.container.util;
+
+/**
+   Implements a simple and fast singly-linked list.
+   It can be used as a stack.
+
+   $(D SList) uses reference semantics.
+ */
+struct SList(T)
+{
+    import std.exception : enforce;
+    import std.range : Take;
+    import std.range.primitives : isInputRange, isForwardRange, ElementType;
+    import std.traits : isImplicitlyConvertible;
+
+    private struct Node
+    {
+        Node * _next;
+        T _payload;
+    }
+    private struct NodeWithoutPayload
+    {
+        Node* _next;
+    }
+    static assert(NodeWithoutPayload._next.offsetof == Node._next.offsetof);
+
+    private Node * _root;
+
+    private void initialize() @trusted nothrow pure
+    {
+        if (_root) return;
+        _root = cast (Node*) new NodeWithoutPayload();
+    }
+
+    private ref inout(Node*) _first() @property @safe nothrow pure inout
+    {
+        assert(_root);
+        return _root._next;
+    }
+
+    private static Node * findLastNode(Node * n)
+    {
+        assert(n);
+        auto ahead = n._next;
+        while (ahead)
+        {
+            n = ahead;
+            ahead = n._next;
+        }
+        return n;
+    }
+
+    private static Node * findLastNode(Node * n, size_t limit)
+    {
+        assert(n && limit);
+        auto ahead = n._next;
+        while (ahead)
+        {
+            if (!--limit) break;
+            n = ahead;
+            ahead = n._next;
+        }
+        return n;
+    }
+
+    private static Node * findNode(Node * n, Node * findMe)
+    {
+        assert(n);
+        auto ahead = n._next;
+        while (ahead != findMe)
+        {
+            n = ahead;
+            enforce(n);
+            ahead = n._next;
+        }
+        return n;
+    }
+
+/**
+Constructor taking a number of nodes
+     */
+    this(U)(U[] values...) if (isImplicitlyConvertible!(U, T))
+    {
+        insertFront(values);
+    }
+
+/**
+Constructor taking an input range
+     */
+    this(Stuff)(Stuff stuff)
+    if (isInputRange!Stuff
+            && isImplicitlyConvertible!(ElementType!Stuff, T)
+            && !is(Stuff == T[]))
+    {
+        insertFront(stuff);
+    }
+
+/**
+Comparison for equality.
+
+Complexity: $(BIGOH min(n, n1)) where $(D n1) is the number of
+elements in $(D rhs).
+     */
+    bool opEquals(const SList rhs) const
+    {
+        return opEquals(rhs);
+    }
+
+    /// ditto
+    bool opEquals(ref const SList rhs) const
+    {
+        if (_root is rhs._root) return true;
+        if (_root is null) return rhs._root is null || rhs._first is null;
+        if (rhs._root is null) return _root is null || _first is null;
+
+        const(Node) * n1 = _first, n2 = rhs._first;
+
+        for (;; n1 = n1._next, n2 = n2._next)
+        {
+            if (!n1) return !n2;
+            if (!n2 || n1._payload != n2._payload) return false;
+        }
+    }
+
+/**
+Defines the container's primary range, which embodies a forward range.
+     */
+    struct Range
+    {
+        private Node * _head;
+        private this(Node * p) { _head = p; }
+
+        /// Input range primitives.
+        @property bool empty() const { return !_head; }
+
+        /// ditto
+        @property ref T front()
+        {
+            assert(!empty, "SList.Range.front: Range is empty");
+            return _head._payload;
+        }
+
+        /// ditto
+        void popFront()
+        {
+            assert(!empty, "SList.Range.popFront: Range is empty");
+            _head = _head._next;
+        }
+
+        /// Forward range primitive.
+        @property Range save() { return this; }
+
+        T moveFront()
+        {
+            import std.algorithm.mutation : move;
+
+            assert(!empty, "SList.Range.moveFront: Range is empty");
+            return move(_head._payload);
+        }
+
+        bool sameHead(Range rhs)
+        {
+            return _head && _head == rhs._head;
+        }
+    }
+
+    @safe unittest
+    {
+        static assert(isForwardRange!Range);
+    }
+
+/**
+Property returning $(D true) if and only if the container has no
+elements.
+
+Complexity: $(BIGOH 1)
+     */
+    @property bool empty() const
+    {
+        return _root is null || _first is null;
+    }
+
+/**
+Duplicates the container. The elements themselves are not transitively
+duplicated.
+
+Complexity: $(BIGOH n).
+     */
+    @property SList dup()
+    {
+        return SList(this[]);
+    }
+
+/**
+Returns a range that iterates over all elements of the container, in
+forward order.
+
+Complexity: $(BIGOH 1)
+     */
+    Range opSlice()
+    {
+        if (empty)
+            return Range(null);
+        else
+            return Range(_first);
+    }
+
+/**
+Forward to $(D opSlice().front).
+
+Complexity: $(BIGOH 1)
+     */
+    @property ref T front()
+    {
+        assert(!empty, "SList.front: List is empty");
+        return _first._payload;
+    }
+
+    @safe unittest
+    {
+        auto s = SList!int(1, 2, 3);
+        s.front = 42;
+        assert(s == SList!int(42, 2, 3));
+    }
+
+/**
+Returns a new $(D SList) that's the concatenation of $(D this) and its
+argument. $(D opBinaryRight) is only defined if $(D Stuff) does not
+define $(D opBinary).
+     */
+    SList opBinary(string op, Stuff)(Stuff rhs)
+    if (op == "~" && is(typeof(SList(rhs))))
+    {
+        auto toAdd = SList(rhs);
+        if (empty) return toAdd;
+        // TODO: optimize
+        auto result = dup;
+        auto n = findLastNode(result._first);
+        n._next = toAdd._first;
+        return result;
+    }
+
+    /// ditto
+    SList opBinaryRight(string op, Stuff)(Stuff lhs)
+    if (op == "~" && !is(typeof(lhs.opBinary!"~"(this))) && is(typeof(SList(lhs))))
+    {
+        auto toAdd = SList(lhs);
+        if (empty) return toAdd;
+        auto result = dup;
+        result.insertFront(toAdd[]);
+        return result;
+    }
+
+/**
+Removes all contents from the $(D SList).
+
+Postcondition: $(D empty)
+
+Complexity: $(BIGOH 1)
+     */
+    void clear()
+    {
+        if (_root)
+            _first = null;
+    }
+
+/**
+Reverses SList in-place. Performs no memory allocation.
+
+Complexity: $(BIGOH n)
+     */
+    void reverse()
+    {
+        if (!empty)
+        {
+            Node* prev;
+            while (_first)
+            {
+                auto next = _first._next;
+                _first._next = prev;
+                prev = _first;
+                _first = next;
+            }
+            _first = prev;
+        }
+    }
+
+/**
+Inserts $(D stuff) to the front of the container. $(D stuff) can be a
+value convertible to $(D T) or a range of objects convertible to $(D
+T). 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 m), where $(D m) is the length of $(D stuff)
+     */
+    size_t insertFront(Stuff)(Stuff stuff)
+    if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T))
+    {
+        initialize();
+        size_t result;
+        Node * n, newRoot;
+        foreach (item; stuff)
+        {
+            auto newNode = new Node(null, item);
+            (newRoot ? n._next : newRoot) = newNode;
+            n = newNode;
+            ++result;
+        }
+        if (!n) return 0;
+        // Last node points to the old root
+        n._next = _first;
+        _first = newRoot;
+        return result;
+    }
+
+    /// ditto
+    size_t insertFront(Stuff)(Stuff stuff)
+    if (isImplicitlyConvertible!(Stuff, T))
+    {
+        initialize();
+        auto newRoot = new Node(_first, stuff);
+        _first = newRoot;
+        return 1;
+    }
+
+/// ditto
+    alias insert = insertFront;
+
+/// ditto
+    alias stableInsert = insert;
+
+    /// ditto
+    alias stableInsertFront = insertFront;
+
+/**
+Picks one value in an unspecified position 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 1).
+     */
+    T removeAny()
+    {
+        import std.algorithm.mutation : move;
+
+        assert(!empty, "SList.removeAny: List is empty");
+        auto result = move(_first._payload);
+        _first = _first._next;
+        return result;
+    }
+    /// ditto
+    alias stableRemoveAny = removeAny;
+
+/**
+Removes the value at the front 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 1).
+     */
+    void removeFront()
+    {
+        assert(!empty, "SList.removeFront: List is empty");
+        _first = _first._next;
+    }
+
+    /// ditto
+    alias stableRemoveFront = removeFront;
+
+/**
+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)).
+     */
+    size_t removeFront(size_t howMany)
+    {
+        size_t result;
+        while (_first && result < howMany)
+        {
+            _first = _first._next;
+            ++result;
+        }
+        return result;
+    }
+
+    /// ditto
+    alias stableRemoveFront = removeFront;
+
+/**
+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.
+
+$(D stuff) can be a value convertible to $(D T) or a range of objects
+convertible to $(D T). 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 k + m), where $(D k) is the number of elements in
+$(D r) and $(D m) is the length of $(D stuff).
+
+Example:
+--------------------
+auto sl = SList!string(["a", "b", "d"]);
+sl.insertAfter(sl[], "e"); // insert at the end (slowest)
+assert(std.algorithm.equal(sl[], ["a", "b", "d", "e"]));
+sl.insertAfter(std.range.take(sl[], 2), "c"); // insert after "b"
+assert(std.algorithm.equal(sl[], ["a", "b", "c", "d", "e"]));
+--------------------
+     */
+
+    size_t insertAfter(Stuff)(Range r, Stuff stuff)
+    {
+        initialize();
+        if (!_first)
+        {
+            enforce(!r._head);
+            return insertFront(stuff);
+        }
+        enforce(r._head);
+        auto n = findLastNode(r._head);
+        SList tmp;
+        auto result = tmp.insertFront(stuff);
+        n._next = tmp._first;
+        return result;
+    }
+
+/**
+Similar to $(D insertAfter) above, but accepts a range bounded in
+count. This is important for ensuring fast insertions in the middle of
+the list.  For fast insertions after a specified position $(D r), use
+$(D insertAfter(take(r, 1), stuff)). The complexity of that operation
+only depends on the number of elements in $(D stuff).
+
+Precondition: $(D r.original.empty || r.maxLength > 0)
+
+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)(Take!Range r, Stuff stuff)
+    {
+        auto orig = r.source;
+        if (!orig._head)
+        {
+            // Inserting after a null range counts as insertion to the
+            // front
+            return insertFront(stuff);
+        }
+        enforce(!r.empty);
+        // Find the last valid element in the range
+        foreach (i; 1 .. r.maxLength)
+        {
+            if (!orig._head._next) break;
+            orig.popFront();
+        }
+        // insert here
+        SList tmp;
+        tmp.initialize();
+        tmp._first = orig._head._next;
+        auto result = tmp.insertFront(stuff);
+        orig._head._next = tmp._first;
+        return result;
+    }
+
+/// ditto
+    alias stableInsertAfter = insertAfter;
+
+/**
+Removes a range from the list in linear time.
+
+Returns: An empty range.
+
+Complexity: $(BIGOH n)
+     */
+    Range linearRemove(Range r)
+    {
+        if (!_first)
+        {
+            enforce(!r._head);
+            return this[];
+        }
+        auto n = findNode(_root, r._head);
+        n._next = null;
+        return Range(null);
+    }
+
+/**
+Removes a $(D Take!Range) from the list in linear time.
+
+Returns: A range comprehending the elements after the removed range.
+
+Complexity: $(BIGOH n)
+     */
+    Range linearRemove(Take!Range r)
+    {
+        auto orig = r.source;
+        // We have something to remove here
+        if (orig._head == _first)
+        {
+            // remove straight from the head of the list
+            for (; !r.empty; r.popFront())
+            {
+                removeFront();
+            }
+            return this[];
+        }
+        if (!r.maxLength)
+        {
+            // Nothing to remove, return the range itself
+            return orig;
+        }
+        // Remove from somewhere in the middle of the list
+        enforce(_first);
+        auto n1 = findNode(_root, orig._head);
+        auto n2 = findLastNode(orig._head, r.maxLength);
+        n1._next = n2._next;
+        return Range(n1._next);
+    }
+
+/// ditto
+    alias stableLinearRemove = linearRemove;
+}
+
+@safe unittest
+{
+    import std.algorithm.comparison : equal;
+
+    auto a = SList!int(5);
+    auto b = a;
+    auto r = a[];
+    a.insertFront(1);
+    b.insertFront(2);
+    assert(equal(a[], [2, 1, 5]));
+    assert(equal(b[], [2, 1, 5]));
+    r.front = 9;
+    assert(equal(a[], [2, 1, 9]));
+    assert(equal(b[], [2, 1, 9]));
+}
+
+@safe unittest
+{
+    auto s = SList!int(1, 2, 3);
+    auto n = s.findLastNode(s._root);
+    assert(n && n._payload == 3);
+}
+
+@safe unittest
+{
+    import std.range.primitives;
+    auto s = SList!int(1, 2, 5, 10);
+    assert(walkLength(s[]) == 4);
+}
+
+@safe unittest
+{
+    import std.range : take;
+    auto src = take([0, 1, 2, 3], 3);
+    auto s = SList!int(src);
+    assert(s == SList!int(0, 1, 2));
+}
+
+@safe unittest
+{
+    auto a = SList!int();
+    auto b = SList!int();
+    auto c = a ~ b[];
+    assert(c.empty);
+}
+
+@safe unittest
+{
+    auto a = SList!int(1, 2, 3);
+    auto b = SList!int(4, 5, 6);
+    auto c = a ~ b[];
+    assert(c == SList!int(1, 2, 3, 4, 5, 6));
+}
+
+@safe unittest
+{
+    auto a = SList!int(1, 2, 3);
+    auto b = [4, 5, 6];
+    auto c = a ~ b;
+    assert(c == SList!int(1, 2, 3, 4, 5, 6));
+}
+
+@safe unittest
+{
+    auto a = SList!int(1, 2, 3);
+    auto c = a ~ 4;
+    assert(c == SList!int(1, 2, 3, 4));
+}
+
+@safe unittest
+{
+    auto a = SList!int(2, 3, 4);
+    auto b = 1 ~ a;
+    assert(b == SList!int(1, 2, 3, 4));
+}
+
+@safe unittest
+{
+    auto a = [1, 2, 3];
+    auto b = SList!int(4, 5, 6);
+    auto c = a ~ b;
+    assert(c == SList!int(1, 2, 3, 4, 5, 6));
+}
+
+@safe unittest
+{
+    auto s = SList!int(1, 2, 3, 4);
+    s.insertFront([ 42, 43 ]);
+    assert(s == SList!int(42, 43, 1, 2, 3, 4));
+}
+
+@safe unittest
+{
+    auto s = SList!int(1, 2, 3);
+    assert(s.removeAny() == 1);
+    assert(s == SList!int(2, 3));
+    assert(s.stableRemoveAny() == 2);
+    assert(s == SList!int(3));
+}
+
+@safe unittest
+{
+    import std.algorithm.comparison : equal;
+
+    auto s = SList!int(1, 2, 3);
+    s.removeFront();
+    assert(equal(s[], [2, 3]));
+    s.stableRemoveFront();
+    assert(equal(s[], [3]));
+}
+
+@safe unittest
+{
+    auto s = SList!int(1, 2, 3, 4, 5, 6, 7);
+    assert(s.removeFront(3) == 3);
+    assert(s == SList!int(4, 5, 6, 7));
+}
+
+@safe unittest
+{
+    auto a = SList!int(1, 2, 3);
+    auto b = SList!int(1, 2, 3);
+    assert(a.insertAfter(a[], b[]) == 3);
+}
+
+@safe unittest
+{
+    import std.range : take;
+    auto s = SList!int(1, 2, 3, 4);
+    auto r = take(s[], 2);
+    assert(s.insertAfter(r, 5) == 1);
+    assert(s == SList!int(1, 2, 5, 3, 4));
+}
+
+@safe unittest
+{
+    import std.algorithm.comparison : equal;
+    import std.range : take;
+
+    // insertAfter documentation example
+    auto sl = SList!string(["a", "b", "d"]);
+    sl.insertAfter(sl[], "e"); // insert at the end (slowest)
+    assert(equal(sl[], ["a", "b", "d", "e"]));
+    sl.insertAfter(take(sl[], 2), "c"); // insert after "b"
+    assert(equal(sl[], ["a", "b", "c", "d", "e"]));
+}
+
+@safe unittest
+{
+    import std.range.primitives;
+    auto s = SList!int(1, 2, 3, 4, 5);
+    auto r = s[];
+    popFrontN(r, 3);
+    auto r1 = s.linearRemove(r);
+    assert(s == SList!int(1, 2, 3));
+    assert(r1.empty);
+}
+
+@safe unittest
+{
+    auto s = SList!int(1, 2, 3, 4, 5);
+    auto r = s[];
+    auto r1 = s.linearRemove(r);
+    assert(s == SList!int());
+    assert(r1.empty);
+}
+
+@safe unittest
+{
+    import std.algorithm.comparison : equal;
+    import std.range;
+
+    auto s = SList!int(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);
+    auto r = s[];
+    popFrontN(r, 3);
+    auto r1 = take(r, 4);
+    assert(equal(r1, [4, 5, 6, 7]));
+    auto r2 = s.linearRemove(r1);
+    assert(s == SList!int(1, 2, 3, 8, 9, 10));
+    assert(equal(r2, [8, 9, 10]));
+}
+
+@safe unittest
+{
+    import std.range.primitives;
+    auto lst = SList!int(1, 5, 42, 9);
+    assert(!lst.empty);
+    assert(lst.front == 1);
+    assert(walkLength(lst[]) == 4);
+
+    auto lst2 = lst ~ [ 1, 2, 3 ];
+    assert(walkLength(lst2[]) == 7);
+
+    auto lst3 = lst ~ [ 7 ];
+    assert(walkLength(lst3[]) == 5);
+}
+
+@safe unittest
+{
+    auto s = make!(SList!int)(1, 2, 3);
+}
+
+@safe unittest
+{
+    // 5193
+    static struct Data
+    {
+        const int val;
+    }
+    SList!Data list;
+}
+
+@safe unittest
+{
+    auto s = SList!int([1, 2, 3]);
+    s.front = 5; //test frontAssign
+    assert(s.front == 5);
+    auto r = s[];
+    r.front = 1; //test frontAssign
+    assert(r.front == 1);
+}
+
+@safe unittest
+{
+    // issue 14920
+    SList!int s;
+    s.insertAfter(s[], 1);
+    assert(s.front == 1);
+}
+
+@safe unittest
+{
+    // issue 15659
+    SList!int s;
+    s.clear();
+}
+
+@safe unittest
+{
+    SList!int s;
+    s.reverse();
+}
+
+@safe unittest
+{
+    import std.algorithm.comparison : equal;
+
+    auto s = SList!int([1, 2, 3]);
+    assert(s[].equal([1, 2, 3]));
+
+    s.reverse();
+    assert(s[].equal([3, 2, 1]));
+}
diff --git a/libphobos/src/std/container/util.d b/libphobos/src/std/container/util.d
new file mode 100644
index 0000000..5be9e7d
--- /dev/null
+++ b/libphobos/src/std/container/util.d
@@ -0,0 +1,189 @@
+/**
+This module contains some common utilities used by containers.
+
+This module is a submodule of $(MREF std, container).
+
+Source: $(PHOBOSSRC std/container/_util.d)
+
+Copyright: 2010- Andrei Alexandrescu. All rights reserved by the respective holders.
+
+License: Distributed under the Boost Software License, Version 1.0.
+(See accompanying file LICENSE_1_0.txt or copy at $(HTTP
+boost.org/LICENSE_1_0.txt)).
+
+Authors: $(HTTP erdani.com, Andrei Alexandrescu)
+
+$(SCRIPT inhibitQuickIndex = 1;)
+*/
+module std.container.util;
+
+/**
+Returns an initialized object. This function is mainly for eliminating
+construction differences between structs and classes. It allows code to not
+worry about whether the type it's constructing is a struct or a class.
+ */
+template make(T)
+if (is(T == struct) || is(T == class))
+{
+    T make(Args...)(Args arguments)
+    if (is(T == struct) && __traits(compiles, T(arguments)))
+    {
+        // constructing an std.container.Array without arguments,
+        // does not initialize its payload and is equivalent
+        // to a null reference. We therefore construct an empty container
+        // by passing an empty array to its constructor.
+        // Issue #13872.
+        static if (arguments.length == 0)
+        {
+            import std.range.primitives : ElementType;
+            alias ET = ElementType!(T.Range);
+            return T(ET[].init);
+        }
+        else
+            return T(arguments);
+    }
+
+    T make(Args...)(Args arguments)
+    if (is(T == class) && __traits(compiles, new T(arguments)))
+    {
+        return new T(arguments);
+    }
+}
+
+
+///
+@system unittest
+{
+    import std.algorithm.comparison : equal;
+    import std.container;
+
+    auto arr = make!(Array!int)([4, 2, 3, 1]);
+    assert(equal(arr[], [4, 2, 3, 1]));
+
+    auto rbt = make!(RedBlackTree!(int, "a > b"))([4, 2, 3, 1]);
+    assert(equal(rbt[], [4, 3, 2, 1]));
+
+    alias makeList = make!(SList!int);
+    auto slist = makeList(1, 2, 3);
+    assert(equal(slist[], [1, 2, 3]));
+}
+
+@system unittest
+{
+    import std.algorithm.comparison : equal;
+    import std.container;
+
+    auto arr1 = make!(Array!dchar)();
+    assert(arr1.empty);
+    auto arr2 = make!(Array!dchar)("hello"d);
+    assert(equal(arr2[], "hello"d));
+
+    auto rtb1 = make!(RedBlackTree!dchar)();
+    assert(rtb1.empty);
+    auto rtb2 = make!(RedBlackTree!dchar)('h', 'e', 'l', 'l', 'o');
+    assert(equal(rtb2[], "ehlo"d));
+}
+
+// Issue 8895
+@safe unittest
+{
+    import std.algorithm.comparison : equal;
+    import std.container;
+
+    auto a = make!(DList!int)(1,2,3,4);
+    auto b = make!(DList!int)(1,2,3,4);
+    auto c = make!(DList!int)(1,2,3,5);
+    auto d = make!(DList!int)(1,2,3,4,5);
+    assert(a == b); // this better terminate!
+    assert(a != c);
+    assert(a != d);
+}
+
+/**
+ * Convenience function for constructing a generic container.
+ */
+template make(alias Container, Args...)
+if (!is(Container))
+{
+    import std.range : isInputRange, isInfinite;
+    import std.traits : isDynamicArray;
+
+    auto make(Range)(Range range)
+        if (!isDynamicArray!Range && isInputRange!Range && !isInfinite!Range)
+    {
+        import std.range : ElementType;
+        return .make!(Container!(ElementType!Range, Args))(range);
+    }
+
+    auto make(T)(T[] items...)
+        if (!isInfinite!T)
+    {
+        return .make!(Container!(T, Args))(items);
+    }
+}
+
+/// forbid construction from infinite range
+@safe unittest
+{
+    import std.container.array : Array;
+    import std.range : only, repeat;
+    import std.range.primitives : isInfinite;
+    static assert(__traits(compiles, { auto arr = make!Array(only(5)); }));
+    static assert(!__traits(compiles, { auto arr = make!Array(repeat(5)); }));
+}
+
+///
+@system unittest
+{
+    import std.algorithm.comparison : equal;
+    import std.container.array, std.container.rbtree, std.container.slist;
+    import std.range : iota;
+
+    auto arr = make!Array(iota(5));
+    assert(equal(arr[], [0, 1, 2, 3, 4]));
+
+    auto rbtmax = make!(RedBlackTree, "a > b")(iota(5));
+    assert(equal(rbtmax[], [4, 3, 2, 1, 0]));
+
+    auto rbtmin = make!RedBlackTree(4, 1, 3, 2);
+    assert(equal(rbtmin[], [1, 2, 3, 4]));
+
+    alias makeList = make!SList;
+    auto list = makeList(1, 7, 42);
+    assert(equal(list[], [1, 7, 42]));
+}
+
+@safe unittest
+{
+    import std.algorithm.comparison : equal;
+    import std.container.rbtree;
+
+    auto rbtmin = make!(RedBlackTree, "a < b", false)(3, 2, 2, 1);
+    assert(equal(rbtmin[], [1, 2, 3]));
+}
+
+// Issue 13872
+@system unittest
+{
+    import std.container;
+
+    auto tree1 = make!(RedBlackTree!int)();
+    auto refToTree1 = tree1;
+    refToTree1.insert(1);
+    assert(1 in tree1);
+
+    auto array1 = make!(Array!int)();
+    auto refToArray1 = array1;
+    refToArray1.insertBack(1);
+    assert(!array1.empty);
+
+    auto slist = make!(SList!int)();
+    auto refToSlist = slist;
+    refToSlist.insert(1);
+    assert(!slist.empty);
+
+    auto dlist = make!(DList!int)();
+    auto refToDList = dlist;
+    refToDList.insert(1);
+    assert(!dlist.empty);
+}