xref: /netbsd-src/external/gpl3/gcc.old/dist/libphobos/src/std/container/binaryheap.d (revision 627f7eb200a4419d89b531d55fccd2ee3ffdcde0)
1*627f7eb2Smrg /**
2*627f7eb2Smrg This module provides a $(D BinaryHeap) (aka priority queue)
3*627f7eb2Smrg adaptor that makes a binary heap out of any user-provided random-access range.
4*627f7eb2Smrg 
5*627f7eb2Smrg This module is a submodule of $(MREF std, container).
6*627f7eb2Smrg 
7*627f7eb2Smrg Source: $(PHOBOSSRC std/container/_binaryheap.d)
8*627f7eb2Smrg 
9*627f7eb2Smrg Copyright: 2010- Andrei Alexandrescu. All rights reserved by the respective holders.
10*627f7eb2Smrg 
11*627f7eb2Smrg License: Distributed under the Boost Software License, Version 1.0.
12*627f7eb2Smrg (See accompanying file LICENSE_1_0.txt or copy at $(HTTP
13*627f7eb2Smrg boost.org/LICENSE_1_0.txt)).
14*627f7eb2Smrg 
15*627f7eb2Smrg Authors: $(HTTP erdani.com, Andrei Alexandrescu)
16*627f7eb2Smrg */
17*627f7eb2Smrg module std.container.binaryheap;
18*627f7eb2Smrg 
19*627f7eb2Smrg import std.range.primitives;
20*627f7eb2Smrg import std.traits;
21*627f7eb2Smrg 
22*627f7eb2Smrg public import std.container.util;
23*627f7eb2Smrg 
24*627f7eb2Smrg ///
25*627f7eb2Smrg @system unittest
26*627f7eb2Smrg {
27*627f7eb2Smrg     import std.algorithm.comparison : equal;
28*627f7eb2Smrg     import std.range : take;
29*627f7eb2Smrg     auto maxHeap = heapify([4, 7, 3, 1, 5]);
30*627f7eb2Smrg     assert(maxHeap.take(3).equal([7, 5, 4]));
31*627f7eb2Smrg 
32*627f7eb2Smrg     auto minHeap = heapify!"a > b"([4, 7, 3, 1, 5]);
33*627f7eb2Smrg     assert(minHeap.take(3).equal([1, 3, 4]));
34*627f7eb2Smrg }
35*627f7eb2Smrg 
36*627f7eb2Smrg // BinaryHeap
37*627f7eb2Smrg /**
38*627f7eb2Smrg Implements a $(HTTP en.wikipedia.org/wiki/Binary_heap, binary heap)
39*627f7eb2Smrg container on top of a given random-access range type (usually $(D
40*627f7eb2Smrg T[])) or a random-access container type (usually $(D Array!T)). The
41*627f7eb2Smrg documentation of $(D BinaryHeap) will refer to the underlying range or
42*627f7eb2Smrg container as the $(I store) of the heap.
43*627f7eb2Smrg 
44*627f7eb2Smrg The binary heap induces structure over the underlying store such that
45*627f7eb2Smrg accessing the largest element (by using the $(D front) property) is a
46*627f7eb2Smrg $(BIGOH 1) operation and extracting it (by using the $(D
47*627f7eb2Smrg removeFront()) method) is done fast in $(BIGOH log n) time.
48*627f7eb2Smrg 
49*627f7eb2Smrg If $(D less) is the less-than operator, which is the default option,
50*627f7eb2Smrg then $(D BinaryHeap) defines a so-called max-heap that optimizes
51*627f7eb2Smrg extraction of the $(I largest) elements. To define a min-heap,
52*627f7eb2Smrg instantiate BinaryHeap with $(D "a > b") as its predicate.
53*627f7eb2Smrg 
54*627f7eb2Smrg Simply extracting elements from a $(D BinaryHeap) container is
55*627f7eb2Smrg tantamount to lazily fetching elements of $(D Store) in descending
56*627f7eb2Smrg order. Extracting elements from the $(D BinaryHeap) to completion
57*627f7eb2Smrg leaves the underlying store sorted in ascending order but, again,
58*627f7eb2Smrg yields elements in descending order.
59*627f7eb2Smrg 
60*627f7eb2Smrg If $(D Store) is a range, the $(D BinaryHeap) cannot grow beyond the
61*627f7eb2Smrg size of that range. If $(D Store) is a container that supports $(D
62*627f7eb2Smrg insertBack), the $(D BinaryHeap) may grow by adding elements to the
63*627f7eb2Smrg container.
64*627f7eb2Smrg      */
65*627f7eb2Smrg struct BinaryHeap(Store, alias less = "a < b")
66*627f7eb2Smrg if (isRandomAccessRange!(Store) || isRandomAccessRange!(typeof(Store.init[])))
67*627f7eb2Smrg {
68*627f7eb2Smrg     import std.algorithm.comparison : min;
69*627f7eb2Smrg     import std.algorithm.mutation : move, swapAt;
70*627f7eb2Smrg     import std.algorithm.sorting : HeapOps;
71*627f7eb2Smrg     import std.exception : enforce;
72*627f7eb2Smrg     import std.functional : binaryFun;
73*627f7eb2Smrg     import std.typecons : RefCounted, RefCountedAutoInitialize;
74*627f7eb2Smrg 
75*627f7eb2Smrg     static if (isRandomAccessRange!Store)
76*627f7eb2Smrg         alias Range = Store;
77*627f7eb2Smrg     else
78*627f7eb2Smrg         alias Range = typeof(Store.init[]);
79*627f7eb2Smrg     alias percolate = HeapOps!(less, Range).percolate;
80*627f7eb2Smrg     alias buildHeap = HeapOps!(less, Range).buildHeap;
81*627f7eb2Smrg 
82*627f7eb2Smrg // Really weird @@BUG@@: if you comment out the "private:" label below,
83*627f7eb2Smrg // std.algorithm can't unittest anymore
84*627f7eb2Smrg //private:
85*627f7eb2Smrg 
86*627f7eb2Smrg     // The payload includes the support store and the effective length
87*627f7eb2Smrg     private static struct Data
88*627f7eb2Smrg     {
89*627f7eb2Smrg         Store _store;
90*627f7eb2Smrg         size_t _length;
91*627f7eb2Smrg     }
92*627f7eb2Smrg     private RefCounted!(Data, RefCountedAutoInitialize.no) _payload;
93*627f7eb2Smrg     // Comparison predicate
94*627f7eb2Smrg     private alias comp = binaryFun!(less);
95*627f7eb2Smrg     // Convenience accessors
_storeBinaryHeap96*627f7eb2Smrg     private @property ref Store _store()
97*627f7eb2Smrg     {
98*627f7eb2Smrg         assert(_payload.refCountedStore.isInitialized);
99*627f7eb2Smrg         return _payload._store;
100*627f7eb2Smrg     }
_lengthBinaryHeap101*627f7eb2Smrg     private @property ref size_t _length()
102*627f7eb2Smrg     {
103*627f7eb2Smrg         assert(_payload.refCountedStore.isInitialized);
104*627f7eb2Smrg         return _payload._length;
105*627f7eb2Smrg     }
106*627f7eb2Smrg 
107*627f7eb2Smrg     // Asserts that the heap property is respected.
assertValidBinaryHeap108*627f7eb2Smrg     private void assertValid()
109*627f7eb2Smrg     {
110*627f7eb2Smrg         debug
111*627f7eb2Smrg         {
112*627f7eb2Smrg             import std.conv : to;
113*627f7eb2Smrg             if (!_payload.refCountedStore.isInitialized) return;
114*627f7eb2Smrg             if (_length < 2) return;
115*627f7eb2Smrg             for (size_t n = _length - 1; n >= 1; --n)
116*627f7eb2Smrg             {
117*627f7eb2Smrg                 auto parentIdx = (n - 1) / 2;
118*627f7eb2Smrg                 assert(!comp(_store[parentIdx], _store[n]), to!string(n));
119*627f7eb2Smrg             }
120*627f7eb2Smrg         }
121*627f7eb2Smrg     }
122*627f7eb2Smrg 
123*627f7eb2Smrg     // @@@BUG@@@: add private here, std.algorithm doesn't unittest anymore
popBinaryHeap124*627f7eb2Smrg     /*private*/ void pop(Store store)
125*627f7eb2Smrg     {
126*627f7eb2Smrg         assert(!store.empty, "Cannot pop an empty store.");
127*627f7eb2Smrg         if (store.length == 1) return;
128*627f7eb2Smrg         auto t1 = store[].moveFront();
129*627f7eb2Smrg         auto t2 = store[].moveBack();
130*627f7eb2Smrg         store.front = move(t2);
131*627f7eb2Smrg         store.back = move(t1);
132*627f7eb2Smrg         percolate(store[], 0, store.length - 1);
133*627f7eb2Smrg     }
134*627f7eb2Smrg 
135*627f7eb2Smrg public:
136*627f7eb2Smrg 
137*627f7eb2Smrg     /**
138*627f7eb2Smrg        Converts the store $(D s) into a heap. If $(D initialSize) is
139*627f7eb2Smrg        specified, only the first $(D initialSize) elements in $(D s)
140*627f7eb2Smrg        are transformed into a heap, after which the heap can grow up
141*627f7eb2Smrg        to $(D r.length) (if $(D Store) is a range) or indefinitely (if
142*627f7eb2Smrg        $(D Store) is a container with $(D insertBack)). Performs
143*627f7eb2Smrg        $(BIGOH min(r.length, initialSize)) evaluations of $(D less).
144*627f7eb2Smrg      */
145*627f7eb2Smrg     this(Store s, size_t initialSize = size_t.max)
146*627f7eb2Smrg     {
147*627f7eb2Smrg         acquire(s, initialSize);
148*627f7eb2Smrg     }
149*627f7eb2Smrg 
150*627f7eb2Smrg /**
151*627f7eb2Smrg Takes ownership of a store. After this, manipulating $(D s) may make
152*627f7eb2Smrg the heap work incorrectly.
153*627f7eb2Smrg      */
154*627f7eb2Smrg     void acquire(Store s, size_t initialSize = size_t.max)
155*627f7eb2Smrg     {
156*627f7eb2Smrg         _payload.refCountedStore.ensureInitialized();
157*627f7eb2Smrg         _store = move(s);
158*627f7eb2Smrg         _length = min(_store.length, initialSize);
159*627f7eb2Smrg         if (_length < 2) return;
160*627f7eb2Smrg         buildHeap(_store[]);
161*627f7eb2Smrg         assertValid();
162*627f7eb2Smrg     }
163*627f7eb2Smrg 
164*627f7eb2Smrg /**
165*627f7eb2Smrg Takes ownership of a store assuming it already was organized as a
166*627f7eb2Smrg heap.
167*627f7eb2Smrg      */
168*627f7eb2Smrg     void assume(Store s, size_t initialSize = size_t.max)
169*627f7eb2Smrg     {
170*627f7eb2Smrg         _payload.refCountedStore.ensureInitialized();
171*627f7eb2Smrg         _store = s;
172*627f7eb2Smrg         _length = min(_store.length, initialSize);
173*627f7eb2Smrg         assertValid();
174*627f7eb2Smrg     }
175*627f7eb2Smrg 
176*627f7eb2Smrg /**
177*627f7eb2Smrg Clears the heap. Returns the portion of the store from $(D 0) up to
178*627f7eb2Smrg $(D length), which satisfies the $(LINK2 https://en.wikipedia.org/wiki/Heap_(data_structure),
179*627f7eb2Smrg heap property).
180*627f7eb2Smrg      */
releaseBinaryHeap181*627f7eb2Smrg     auto release()
182*627f7eb2Smrg     {
183*627f7eb2Smrg         if (!_payload.refCountedStore.isInitialized)
184*627f7eb2Smrg         {
185*627f7eb2Smrg             return typeof(_store[0 .. _length]).init;
186*627f7eb2Smrg         }
187*627f7eb2Smrg         assertValid();
188*627f7eb2Smrg         auto result = _store[0 .. _length];
189*627f7eb2Smrg         _payload = _payload.init;
190*627f7eb2Smrg         return result;
191*627f7eb2Smrg     }
192*627f7eb2Smrg 
193*627f7eb2Smrg /**
194*627f7eb2Smrg Returns $(D true) if the heap is _empty, $(D false) otherwise.
195*627f7eb2Smrg      */
emptyBinaryHeap196*627f7eb2Smrg     @property bool empty()
197*627f7eb2Smrg     {
198*627f7eb2Smrg         return !length;
199*627f7eb2Smrg     }
200*627f7eb2Smrg 
201*627f7eb2Smrg /**
202*627f7eb2Smrg Returns a duplicate of the heap. The $(D dup) method is available only if the
203*627f7eb2Smrg underlying store supports it.
204*627f7eb2Smrg      */
205*627f7eb2Smrg     static if (is(typeof((Store s) { return s.dup; }(Store.init)) == Store))
206*627f7eb2Smrg     {
dupBinaryHeap207*627f7eb2Smrg         @property BinaryHeap dup()
208*627f7eb2Smrg         {
209*627f7eb2Smrg             BinaryHeap result;
210*627f7eb2Smrg             if (!_payload.refCountedStore.isInitialized) return result;
211*627f7eb2Smrg             result.assume(_store.dup, length);
212*627f7eb2Smrg             return result;
213*627f7eb2Smrg         }
214*627f7eb2Smrg     }
215*627f7eb2Smrg 
216*627f7eb2Smrg /**
217*627f7eb2Smrg Returns the _length of the heap.
218*627f7eb2Smrg      */
lengthBinaryHeap219*627f7eb2Smrg     @property size_t length()
220*627f7eb2Smrg     {
221*627f7eb2Smrg         return _payload.refCountedStore.isInitialized ? _length : 0;
222*627f7eb2Smrg     }
223*627f7eb2Smrg 
224*627f7eb2Smrg /**
225*627f7eb2Smrg Returns the _capacity of the heap, which is the length of the
226*627f7eb2Smrg underlying store (if the store is a range) or the _capacity of the
227*627f7eb2Smrg underlying store (if the store is a container).
228*627f7eb2Smrg      */
capacityBinaryHeap229*627f7eb2Smrg     @property size_t capacity()
230*627f7eb2Smrg     {
231*627f7eb2Smrg         if (!_payload.refCountedStore.isInitialized) return 0;
232*627f7eb2Smrg         static if (is(typeof(_store.capacity) : size_t))
233*627f7eb2Smrg         {
234*627f7eb2Smrg             return _store.capacity;
235*627f7eb2Smrg         }
236*627f7eb2Smrg         else
237*627f7eb2Smrg         {
238*627f7eb2Smrg             return _store.length;
239*627f7eb2Smrg         }
240*627f7eb2Smrg     }
241*627f7eb2Smrg 
242*627f7eb2Smrg /**
243*627f7eb2Smrg Returns a copy of the _front of the heap, which is the largest element
244*627f7eb2Smrg according to $(D less).
245*627f7eb2Smrg      */
246*627f7eb2Smrg     @property ElementType!Store front()
247*627f7eb2Smrg     {
248*627f7eb2Smrg         enforce(!empty, "Cannot call front on an empty heap.");
249*627f7eb2Smrg         return _store.front;
250*627f7eb2Smrg     }
251*627f7eb2Smrg 
252*627f7eb2Smrg /**
253*627f7eb2Smrg Clears the heap by detaching it from the underlying store.
254*627f7eb2Smrg      */
clearBinaryHeap255*627f7eb2Smrg     void clear()
256*627f7eb2Smrg     {
257*627f7eb2Smrg         _payload = _payload.init;
258*627f7eb2Smrg     }
259*627f7eb2Smrg 
260*627f7eb2Smrg /**
261*627f7eb2Smrg Inserts $(D value) into the store. If the underlying store is a range
262*627f7eb2Smrg and $(D length == capacity), throws an exception.
263*627f7eb2Smrg      */
264*627f7eb2Smrg     size_t insert(ElementType!Store value)
265*627f7eb2Smrg     {
266*627f7eb2Smrg         static if (is(typeof(_store.insertBack(value))))
267*627f7eb2Smrg         {
268*627f7eb2Smrg             _payload.refCountedStore.ensureInitialized();
269*627f7eb2Smrg             if (length == _store.length)
270*627f7eb2Smrg             {
271*627f7eb2Smrg                 // reallocate
272*627f7eb2Smrg                 _store.insertBack(value);
273*627f7eb2Smrg             }
274*627f7eb2Smrg             else
275*627f7eb2Smrg             {
276*627f7eb2Smrg                 // no reallocation
277*627f7eb2Smrg                 _store[_length] = value;
278*627f7eb2Smrg             }
279*627f7eb2Smrg         }
280*627f7eb2Smrg         else
281*627f7eb2Smrg         {
282*627f7eb2Smrg             import std.traits : isDynamicArray;
283*627f7eb2Smrg             static if (isDynamicArray!Store)
284*627f7eb2Smrg             {
285*627f7eb2Smrg                 if (length == _store.length)
286*627f7eb2Smrg                     _store.length = (length < 6 ? 8 : length * 3 / 2);
287*627f7eb2Smrg                 _store[_length] = value;
288*627f7eb2Smrg             }
289*627f7eb2Smrg             else
290*627f7eb2Smrg             {
291*627f7eb2Smrg                 // can't grow
292*627f7eb2Smrg                 enforce(length < _store.length,
293*627f7eb2Smrg                         "Cannot grow a heap created over a range");
294*627f7eb2Smrg             }
295*627f7eb2Smrg         }
296*627f7eb2Smrg 
297*627f7eb2Smrg         // sink down the element
298*627f7eb2Smrg         for (size_t n = _length; n; )
299*627f7eb2Smrg         {
300*627f7eb2Smrg             auto parentIdx = (n - 1) / 2;
301*627f7eb2Smrg             if (!comp(_store[parentIdx], _store[n])) break; // done!
302*627f7eb2Smrg             // must swap and continue
303*627f7eb2Smrg             _store.swapAt(parentIdx, n);
304*627f7eb2Smrg             n = parentIdx;
305*627f7eb2Smrg         }
306*627f7eb2Smrg         ++_length;
307*627f7eb2Smrg         debug(BinaryHeap) assertValid();
308*627f7eb2Smrg         return 1;
309*627f7eb2Smrg     }
310*627f7eb2Smrg 
311*627f7eb2Smrg /**
312*627f7eb2Smrg Removes the largest element from the heap.
313*627f7eb2Smrg      */
removeFrontBinaryHeap314*627f7eb2Smrg     void removeFront()
315*627f7eb2Smrg     {
316*627f7eb2Smrg         enforce(!empty, "Cannot call removeFront on an empty heap.");
317*627f7eb2Smrg         if (_length > 1)
318*627f7eb2Smrg         {
319*627f7eb2Smrg             auto t1 = _store[].moveFront();
320*627f7eb2Smrg             auto t2 = _store[].moveAt(_length - 1);
321*627f7eb2Smrg             _store.front = move(t2);
322*627f7eb2Smrg             _store[_length - 1] = move(t1);
323*627f7eb2Smrg         }
324*627f7eb2Smrg         --_length;
325*627f7eb2Smrg         percolate(_store[], 0, _length);
326*627f7eb2Smrg     }
327*627f7eb2Smrg 
328*627f7eb2Smrg     /// ditto
329*627f7eb2Smrg     alias popFront = removeFront;
330*627f7eb2Smrg 
331*627f7eb2Smrg /**
332*627f7eb2Smrg Removes the largest element from the heap and returns a copy of
333*627f7eb2Smrg it. The element still resides in the heap's store. For performance
334*627f7eb2Smrg reasons you may want to use $(D removeFront) with heaps of objects
335*627f7eb2Smrg that are expensive to copy.
336*627f7eb2Smrg      */
337*627f7eb2Smrg     ElementType!Store removeAny()
338*627f7eb2Smrg     {
339*627f7eb2Smrg         removeFront();
340*627f7eb2Smrg         return _store[_length];
341*627f7eb2Smrg     }
342*627f7eb2Smrg 
343*627f7eb2Smrg /**
344*627f7eb2Smrg Replaces the largest element in the store with $(D value).
345*627f7eb2Smrg      */
346*627f7eb2Smrg     void replaceFront(ElementType!Store value)
347*627f7eb2Smrg     {
348*627f7eb2Smrg         // must replace the top
349*627f7eb2Smrg         assert(!empty, "Cannot call replaceFront on an empty heap.");
350*627f7eb2Smrg         _store.front = value;
351*627f7eb2Smrg         percolate(_store[], 0, _length);
352*627f7eb2Smrg         debug(BinaryHeap) assertValid();
353*627f7eb2Smrg     }
354*627f7eb2Smrg 
355*627f7eb2Smrg /**
356*627f7eb2Smrg If the heap has room to grow, inserts $(D value) into the store and
357*627f7eb2Smrg returns $(D true). Otherwise, if $(D less(value, front)), calls $(D
358*627f7eb2Smrg replaceFront(value)) and returns again $(D true). Otherwise, leaves
359*627f7eb2Smrg the heap unaffected and returns $(D false). This method is useful in
360*627f7eb2Smrg scenarios where the smallest $(D k) elements of a set of candidates
361*627f7eb2Smrg must be collected.
362*627f7eb2Smrg      */
363*627f7eb2Smrg     bool conditionalInsert(ElementType!Store value)
364*627f7eb2Smrg     {
365*627f7eb2Smrg         _payload.refCountedStore.ensureInitialized();
366*627f7eb2Smrg         if (_length < _store.length)
367*627f7eb2Smrg         {
368*627f7eb2Smrg             insert(value);
369*627f7eb2Smrg             return true;
370*627f7eb2Smrg         }
371*627f7eb2Smrg 
372*627f7eb2Smrg         assert(!_store.empty, "Cannot replace front of an empty heap.");
373*627f7eb2Smrg         if (!comp(value, _store.front)) return false; // value >= largest
374*627f7eb2Smrg         _store.front = value;
375*627f7eb2Smrg 
376*627f7eb2Smrg         percolate(_store[], 0, _length);
377*627f7eb2Smrg         debug(BinaryHeap) assertValid();
378*627f7eb2Smrg         return true;
379*627f7eb2Smrg     }
380*627f7eb2Smrg 
381*627f7eb2Smrg /**
382*627f7eb2Smrg Swapping is allowed if the heap is full. If $(D less(value, front)), the
383*627f7eb2Smrg method exchanges store.front and value and returns $(D true). Otherwise, it
384*627f7eb2Smrg leaves the heap unaffected and returns $(D false).
385*627f7eb2Smrg      */
386*627f7eb2Smrg     bool conditionalSwap(ref ElementType!Store value)
387*627f7eb2Smrg     {
388*627f7eb2Smrg         _payload.refCountedStore.ensureInitialized();
389*627f7eb2Smrg         assert(_length == _store.length);
390*627f7eb2Smrg         assert(!_store.empty, "Cannot swap front of an empty heap.");
391*627f7eb2Smrg 
392*627f7eb2Smrg         if (!comp(value, _store.front)) return false; // value >= largest
393*627f7eb2Smrg 
394*627f7eb2Smrg         import std.algorithm.mutation : swap;
395*627f7eb2Smrg         swap(_store.front, value);
396*627f7eb2Smrg 
397*627f7eb2Smrg         percolate(_store[], 0, _length);
398*627f7eb2Smrg         debug(BinaryHeap) assertValid();
399*627f7eb2Smrg 
400*627f7eb2Smrg         return true;
401*627f7eb2Smrg     }
402*627f7eb2Smrg }
403*627f7eb2Smrg 
404*627f7eb2Smrg /// Example from "Introduction to Algorithms" Cormen et al, p 146
405*627f7eb2Smrg @system unittest
406*627f7eb2Smrg {
407*627f7eb2Smrg     import std.algorithm.comparison : equal;
408*627f7eb2Smrg     int[] a = [ 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 ];
409*627f7eb2Smrg     auto h = heapify(a);
410*627f7eb2Smrg     // largest element
411*627f7eb2Smrg     assert(h.front == 16);
412*627f7eb2Smrg     // a has the heap property
413*627f7eb2Smrg     assert(equal(a, [ 16, 14, 10, 8, 7, 9, 3, 2, 4, 1 ]));
414*627f7eb2Smrg }
415*627f7eb2Smrg 
416*627f7eb2Smrg /// $(D BinaryHeap) implements the standard input range interface, allowing
417*627f7eb2Smrg /// lazy iteration of the underlying range in descending order.
418*627f7eb2Smrg @system unittest
419*627f7eb2Smrg {
420*627f7eb2Smrg     import std.algorithm.comparison : equal;
421*627f7eb2Smrg     import std.range : take;
422*627f7eb2Smrg     int[] a = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7];
423*627f7eb2Smrg     auto top5 = heapify(a).take(5);
424*627f7eb2Smrg     assert(top5.equal([16, 14, 10, 9, 8]));
425*627f7eb2Smrg }
426*627f7eb2Smrg 
427*627f7eb2Smrg /**
428*627f7eb2Smrg Convenience function that returns a $(D BinaryHeap!Store) object
429*627f7eb2Smrg initialized with $(D s) and $(D initialSize).
430*627f7eb2Smrg  */
431*627f7eb2Smrg BinaryHeap!(Store, less) heapify(alias less = "a < b", Store)(Store s,
432*627f7eb2Smrg         size_t initialSize = size_t.max)
433*627f7eb2Smrg {
434*627f7eb2Smrg 
435*627f7eb2Smrg     return BinaryHeap!(Store, less)(s, initialSize);
436*627f7eb2Smrg }
437*627f7eb2Smrg 
438*627f7eb2Smrg ///
439*627f7eb2Smrg @system unittest
440*627f7eb2Smrg {
441*627f7eb2Smrg     import std.conv : to;
442*627f7eb2Smrg     import std.range.primitives;
443*627f7eb2Smrg     {
444*627f7eb2Smrg         // example from "Introduction to Algorithms" Cormen et al., p 146
445*627f7eb2Smrg         int[] a = [ 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 ];
446*627f7eb2Smrg         auto h = heapify(a);
447*627f7eb2Smrg         h = heapify!"a < b"(a);
448*627f7eb2Smrg         assert(h.front == 16);
449*627f7eb2Smrg         assert(a == [ 16, 14, 10, 8, 7, 9, 3, 2, 4, 1 ]);
450*627f7eb2Smrg         auto witness = [ 16, 14, 10, 9, 8, 7, 4, 3, 2, 1 ];
451*627f7eb2Smrg         for (; !h.empty; h.removeFront(), witness.popFront())
452*627f7eb2Smrg         {
453*627f7eb2Smrg             assert(!witness.empty);
454*627f7eb2Smrg             assert(witness.front == h.front);
455*627f7eb2Smrg         }
456*627f7eb2Smrg         assert(witness.empty);
457*627f7eb2Smrg     }
458*627f7eb2Smrg     {
459*627f7eb2Smrg         int[] a = [ 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 ];
460*627f7eb2Smrg         int[] b = new int[a.length];
461*627f7eb2Smrg         BinaryHeap!(int[]) h = BinaryHeap!(int[])(b, 0);
foreach(e;a)462*627f7eb2Smrg         foreach (e; a)
463*627f7eb2Smrg         {
464*627f7eb2Smrg             h.insert(e);
465*627f7eb2Smrg         }
466*627f7eb2Smrg         assert(b == [ 16, 14, 10, 8, 7, 3, 9, 1, 4, 2 ], to!string(b));
467*627f7eb2Smrg     }
468*627f7eb2Smrg }
469*627f7eb2Smrg 
470*627f7eb2Smrg @system unittest
471*627f7eb2Smrg {
472*627f7eb2Smrg     // Test range interface.
473*627f7eb2Smrg     import std.algorithm.comparison : equal;
474*627f7eb2Smrg     int[] a = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7];
475*627f7eb2Smrg     auto h = heapify(a);
476*627f7eb2Smrg     static assert(isInputRange!(typeof(h)));
477*627f7eb2Smrg     assert(h.equal([16, 14, 10, 9, 8, 7, 4, 3, 2, 1]));
478*627f7eb2Smrg }
479*627f7eb2Smrg 
480*627f7eb2Smrg @system unittest // 15675
481*627f7eb2Smrg {
482*627f7eb2Smrg     import std.container.array : Array;
483*627f7eb2Smrg 
484*627f7eb2Smrg     Array!int elements = [1, 2, 10, 12];
485*627f7eb2Smrg     auto heap = heapify(elements);
486*627f7eb2Smrg     assert(heap.front == 12);
487*627f7eb2Smrg }
488*627f7eb2Smrg 
489*627f7eb2Smrg @system unittest // 16072
490*627f7eb2Smrg {
491*627f7eb2Smrg     auto q = heapify!"a > b"([2, 4, 5]);
492*627f7eb2Smrg     q.insert(1);
493*627f7eb2Smrg     q.insert(6);
494*627f7eb2Smrg     assert(q.front == 1);
495*627f7eb2Smrg 
496*627f7eb2Smrg     // test more multiple grows
497*627f7eb2Smrg     int[] arr;
498*627f7eb2Smrg     auto r = heapify!"a < b"(arr);
499*627f7eb2Smrg     foreach (i; 0 .. 100)
500*627f7eb2Smrg         r.insert(i);
501*627f7eb2Smrg 
502*627f7eb2Smrg     assert(r.front == 99);
503*627f7eb2Smrg }
504*627f7eb2Smrg 
505*627f7eb2Smrg @system unittest
506*627f7eb2Smrg {
507*627f7eb2Smrg     import std.algorithm.comparison : equal;
508*627f7eb2Smrg     int[] a = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7];
509*627f7eb2Smrg     auto heap = heapify(a);
510*627f7eb2Smrg     auto dup = heap.dup();
511*627f7eb2Smrg     assert(dup.equal([16, 14, 10, 9, 8, 7, 4, 3, 2, 1]));
512*627f7eb2Smrg }
513*627f7eb2Smrg 
514*627f7eb2Smrg @safe unittest
515*627f7eb2Smrg {
516*627f7eb2Smrg     static struct StructWithoutDup
517*627f7eb2Smrg     {
518*627f7eb2Smrg         int[] a;
dupStructWithoutDup519*627f7eb2Smrg         @disable StructWithoutDup dup()
520*627f7eb2Smrg         {
521*627f7eb2Smrg             StructWithoutDup d;
522*627f7eb2Smrg             return d;
523*627f7eb2Smrg         }
524*627f7eb2Smrg         alias a this;
525*627f7eb2Smrg     }
526*627f7eb2Smrg 
527*627f7eb2Smrg     // Assert Binary heap can be created when Store doesn't have dup
528*627f7eb2Smrg     // if dup is not used.
529*627f7eb2Smrg     assert(__traits(compiles, ()
530*627f7eb2Smrg         {
531*627f7eb2Smrg             auto s = StructWithoutDup([1,2]);
532*627f7eb2Smrg             auto h = heapify(s);
533*627f7eb2Smrg         }));
534*627f7eb2Smrg 
535*627f7eb2Smrg     // Assert dup can't be used on BinaryHeaps when Store doesn't have dup
536*627f7eb2Smrg     assert(!__traits(compiles, ()
537*627f7eb2Smrg         {
538*627f7eb2Smrg             auto s = StructWithoutDup([1,2]);
539*627f7eb2Smrg             auto h = heapify(s);
540*627f7eb2Smrg             h.dup();
541*627f7eb2Smrg         }));
542*627f7eb2Smrg }
543*627f7eb2Smrg 
544*627f7eb2Smrg @safe unittest
545*627f7eb2Smrg {
546*627f7eb2Smrg     static struct StructWithDup
547*627f7eb2Smrg     {
548*627f7eb2Smrg         int[] a;
dupStructWithDup549*627f7eb2Smrg         StructWithDup dup()
550*627f7eb2Smrg         {
551*627f7eb2Smrg             StructWithDup d;
552*627f7eb2Smrg             return d;
553*627f7eb2Smrg         }
554*627f7eb2Smrg         alias a this;
555*627f7eb2Smrg     }
556*627f7eb2Smrg 
557*627f7eb2Smrg     // Assert dup can be used on BinaryHeaps when Store has dup
558*627f7eb2Smrg     assert(__traits(compiles, ()
559*627f7eb2Smrg         {
560*627f7eb2Smrg             auto s = StructWithDup([1, 2]);
561*627f7eb2Smrg             auto h = heapify(s);
562*627f7eb2Smrg             h.dup();
563*627f7eb2Smrg         }));
564*627f7eb2Smrg }
565*627f7eb2Smrg 
566*627f7eb2Smrg @system unittest
567*627f7eb2Smrg {
568*627f7eb2Smrg     import std.algorithm.comparison : equal;
569*627f7eb2Smrg     import std.internal.test.dummyrange;
570*627f7eb2Smrg 
571*627f7eb2Smrg     alias RefRange = DummyRange!(ReturnBy.Reference, Length.Yes, RangeType.Random);
572*627f7eb2Smrg 
573*627f7eb2Smrg     RefRange a;
574*627f7eb2Smrg     RefRange b;
575*627f7eb2Smrg     a.reinit();
576*627f7eb2Smrg     b.reinit();
577*627f7eb2Smrg 
578*627f7eb2Smrg     auto heap = heapify(a);
foreach(ref elem;b)579*627f7eb2Smrg     foreach (ref elem; b)
580*627f7eb2Smrg     {
581*627f7eb2Smrg         heap.conditionalSwap(elem);
582*627f7eb2Smrg     }
583*627f7eb2Smrg 
584*627f7eb2Smrg     assert(equal(heap, [ 5, 5, 4, 4, 3, 3, 2, 2, 1, 1]));
585*627f7eb2Smrg     assert(equal(b, [10, 9, 8, 7, 6, 6, 7, 8, 9, 10]));
586*627f7eb2Smrg }
587*627f7eb2Smrg 
588*627f7eb2Smrg @system unittest // Issue 17314
589*627f7eb2Smrg {
590*627f7eb2Smrg     import std.algorithm.comparison : equal;
591*627f7eb2Smrg     int[] a = [5];
592*627f7eb2Smrg     auto heap = heapify(a);
593*627f7eb2Smrg     heap.insert(6);
594*627f7eb2Smrg     assert(equal(heap, [6, 5]));
595*627f7eb2Smrg }
596