1 files changed, 595 insertions, 0 deletions
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]));
+}