/**
-This module provides a $(D BinaryHeap) (aka priority queue)
+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)
+Source: $(PHOBOSSRC std/container/binaryheap.d)
Copyright: 2010- Andrei Alexandrescu. All rights reserved by the respective holders.
/**
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
+T[])) or a random-access container type (usually `Array!T`). The
+documentation of `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
+accessing the largest element (by using the `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
+If `less` is the less-than operator, which is the default option,
+then `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
+Simply extracting elements from a `BinaryHeap` container is
+tantamount to lazily fetching elements of `Store` in descending
+order. Extracting elements from the `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
+If `Store` is a range, the `BinaryHeap` cannot grow beyond the
+size of that range. If `Store` is a container that supports $(D
+insertBack), the `BinaryHeap` may grow by adding elements to the
container.
*/
struct BinaryHeap(Store, alias less = "a < b")
// Convenience accessors
private @property ref Store _store()
{
- assert(_payload.refCountedStore.isInitialized);
+ assert(_payload.refCountedStore.isInitialized,
+ "BinaryHeap not initialized");
return _payload._store;
}
private @property ref size_t _length()
{
- assert(_payload.refCountedStore.isInitialized);
+ assert(_payload.refCountedStore.isInitialized,
+ "BinaryHeap not initialized");
return _payload._length;
}
public:
/**
- Converts the store $(D s) into a heap. If $(D initialSize) is
- specified, only the first $(D initialSize) elements in $(D s)
+ 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 $(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).
+ 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)
{
}
/**
-Takes ownership of a store. After this, manipulating $(D s) may make
+Takes ownership of a store. After this, manipulating `s` may make
the heap work incorrectly.
*/
void acquire(Store s, size_t initialSize = size_t.max)
}
/**
-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),
+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()
}
/**
-Returns $(D true) if the heap is _empty, $(D false) otherwise.
+Returns `true` if the heap is _empty, `false` otherwise.
*/
@property bool empty()
{
}
/**
-Returns a duplicate of the heap. The $(D dup) method is available only if the
+Returns a duplicate of the heap. The `dup` method is available only if the
underlying store supports it.
*/
static if (is(typeof((Store s) { return s.dup; }(Store.init)) == Store))
/**
Returns a copy of the _front of the heap, which is the largest element
-according to $(D less).
+according to `less`.
*/
@property ElementType!Store front()
{
}
/**
-Inserts $(D value) into the store. If the underlying store is a range
+Inserts `value` into the store. If the underlying store is a range
and $(D length == capacity), throws an exception.
*/
size_t insert(ElementType!Store value)
/**
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
+reasons you may want to use `removeFront` with heaps of objects
that are expensive to copy.
*/
ElementType!Store removeAny()
}
/**
-Replaces the largest element in the store with $(D value).
+Replaces the largest element in the store with `value`.
*/
void replaceFront(ElementType!Store value)
{
}
/**
-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
+If the heap has room to grow, inserts `value` into the store and
+returns `true`. Otherwise, if $(D less(value, front)), calls $(D
+replaceFront(value)) and returns again `true`. Otherwise, leaves
+the heap unaffected and returns `false`. This method is useful in
+scenarios where the smallest `k` elements of a set of candidates
must be collected.
*/
bool conditionalInsert(ElementType!Store value)
/**
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).
+method exchanges store.front and value and returns `true`. Otherwise, it
+leaves the heap unaffected and returns `false`.
*/
bool conditionalSwap(ref ElementType!Store value)
{
_payload.refCountedStore.ensureInitialized();
- assert(_length == _store.length);
+ 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
assert(equal(a, [ 16, 14, 10, 8, 7, 9, 3, 2, 4, 1 ]));
}
-/// $(D BinaryHeap) implements the standard input range interface, allowing
+/// `BinaryHeap` implements the standard input range interface, allowing
/// lazy iteration of the underlying range in descending order.
@system unittest
{
}
/**
-Convenience function that returns a $(D BinaryHeap!Store) object
-initialized with $(D s) and $(D initialSize).
+Convenience function that returns a `BinaryHeap!Store` object
+initialized with `s` and `initialSize`.
*/
BinaryHeap!(Store, less) heapify(alias less = "a < b", Store)(Store s,
size_t initialSize = size_t.max)
assert(h.equal([16, 14, 10, 9, 8, 7, 4, 3, 2, 1]));
}
-@system unittest // 15675
+// https://issues.dlang.org/show_bug.cgi?id=15675
+@system unittest
{
import std.container.array : Array;
assert(heap.front == 12);
}
-@system unittest // 16072
+// https://issues.dlang.org/show_bug.cgi?id=16072
+@system unittest
{
auto q = heapify!"a > b"([2, 4, 5]);
q.insert(1);
static struct StructWithoutDup
{
int[] a;
- @disable StructWithoutDup dup()
- {
- StructWithoutDup d;
- return d;
- }
+ @disable StructWithoutDup dup();
alias a this;
}
assert(equal(b, [10, 9, 8, 7, 6, 6, 7, 8, 9, 10]));
}
-@system unittest // Issue 17314
+// https://issues.dlang.org/show_bug.cgi?id=17314
+@system unittest
{
import std.algorithm.comparison : equal;
int[] a = [5];
projects / thirdparty / gcc.git / blobdiff