libphobos/src/std/container/binaryheap.d

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