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