/**This module provides a `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 $(HTTPboost.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 $(DT[])) or a random-access container type (usually `Array!T`). Thedocumentation of `BinaryHeap` will refer to the underlying range orcontainer as the $(I store) of the heap. The binary heap induces structure over the underlying store such thataccessing the largest element (by using the `front` property) is a$(BIGOH 1) operation and extracting it (by using the $(DremoveFront()) method) is done fast in $(BIGOH log n) time. If `less` is the less-than operator, which is the default option,then `BinaryHeap` defines a so-called max-heap that optimizesextraction of the $(I largest) elements. To define a min-heap,instantiate BinaryHeap with $(D "a > b") as its predicate. Simply extracting elements from a `BinaryHeap` container istantamount to lazily fetching elements of `Store` in descendingorder. Extracting elements from the `BinaryHeap` to completionleaves the underlying store sorted in ascending order but, again,yields elements in descending order. If `Store` is a range, the `BinaryHeap` cannot grow beyond thesize of that range. If `Store` is a container that supports $(DinsertBack), the `BinaryHeap` may grow by adding elements to thecontainer.     */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;    }    // TODO: migrate to use the SafeRefCounted. The problem is that some member    // functions here become @system with a naive switch.    private RefCounted!(Data, RefCountedAutoInitialize.no) _payload;    // Comparison predicate    private alias comp = binaryFun!(less);    // Convenience accessors    private @property ref Store _store()    {        assert(_payload.refCountedStore.isInitialized,                "BinaryHeap not initialized");        return _payload._store;    }    private @property ref size_t _length()    {        assert(_payload.refCountedStore.isInitialized,                "BinaryHeap not initialized");        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 `s` into a heap. If `initialSize` is       specified, only the first `initialSize` elements in `s`       are transformed into a heap, after which the heap can grow up       to `r.length` (if `Store` is a range) or indefinitely (if       `Store` is a container with `insertBack`). Performs       $(BIGOH min(r.length, initialSize)) evaluations of `less`.     */    this(Store s, size_t initialSize = size_t.max)    {        acquire(s, initialSize);    } /**Takes ownership of a store. After this, manipulating `s` may makethe 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 aheap.     */    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 `0` up to`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 `true` if the heap is _empty, `false` otherwise.     */    @property bool empty()    {        return !length;    } /**Returns a duplicate of the heap. The `dup` method is available only if theunderlying 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 theunderlying store (if the store is a range) or the _capacity of theunderlying 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 elementaccording to `less`.     */    @property ElementType!Store front()    {        assert(!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 `value` into the store. If the underlying store is a rangeand $(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()    {        assert(!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 ofit. The element still resides in the heap's store. For performancereasons you may want to use `removeFront` with heaps of objectsthat are expensive to copy.     */    ElementType!Store removeAny()    {        removeFront();        return _store[_length];    } /**Replaces the largest element in the store with `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 `value` into the store andreturns `true`. Otherwise, if $(D less(value, front)), calls $(DreplaceFront(value)) and returns again `true`. Otherwise, leavesthe heap unaffected and returns `false`. This method is useful inscenarios where the smallest `k` elements of a set of candidatesmust 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)), themethod exchanges store.front and value and returns `true`. Otherwise, itleaves the heap unaffected and returns `false`.     */    bool conditionalSwap(ref ElementType!Store value)    {        _payload.refCountedStore.ensureInitialized();        assert(_length == _store.length,                "length and number of stored items out of sync");        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 ]));} /// `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 `BinaryHeap!Store` objectinitialized with `s` and `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]));} // https://issues.dlang.org/show_bug.cgi?id=15675@system unittest{    import std.container.array : Array;     Array!int elements = [1, 2, 10, 12];    auto heap = heapify(elements);    assert(heap.front == 12);} // https://issues.dlang.org/show_bug.cgi?id=16072@system unittest{    auto q = heapify!"a > b"([2, 4, 5]);    q.insert(1);    q.insert(6);

Lines 1–500 of 639. Load more