"Fossies" - the Fresh Open Source Software Archive

Member "ponyc-0.33.0/packages/collections/heap.pony" (1 Nov 2019, 3701 Bytes) of package /linux/misc/ponyc-0.33.0.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) Pony source code syntax highlighting (style: standard) with prefixed line numbers. Alternatively you can here view or download the uninterpreted source code file.

    1 
    2 type MinHeap[A: Comparable[A] #read] is BinaryHeap[A, MinHeapPriority[A]]
    3 type MaxHeap[A: Comparable[A] #read] is BinaryHeap[A, MaxHeapPriority[A]]
    4 
    5 class BinaryHeap[A: Comparable[A] #read, P: BinaryHeapPriority[A]]
    6   """
    7   A priority queue implemented as a binary heap. The `BinaryHeapPriority` type
    8   parameter determines whether this is max-heap or a min-heap.
    9   """
   10   embed _data: Array[A]
   11 
   12   new create(len: USize) =>
   13     """
   14     Create an empty heap with space for `len` elements.
   15     """
   16     _data = Array[A](len)
   17 
   18   fun ref clear() =>
   19     """
   20     Remove all elements from the heap.
   21     """
   22     _data.clear()
   23 
   24   fun size(): USize =>
   25     """
   26     Return the number of elements in the heap.
   27     """
   28     _data.size()
   29 
   30   fun peek(): this->A ? =>
   31     """
   32     Return the highest priority item in the heap. For max-heaps, the greatest
   33     item will be returned. For min-heaps, the smallest item will be returned.
   34     """
   35     _data(0)?
   36 
   37   fun ref push(value: A) =>
   38     """
   39     Push an item into the heap.
   40 
   41     The time complexity of this operation is O(log(n)) with respect to the size
   42     of the heap.
   43     """
   44     _data.push(value)
   45     _sift_up(size() - 1)
   46 
   47   fun ref pop(): A^ ? =>
   48     """
   49     Remove the highest priority value from the heap and return it. For
   50     max-heaps, the greatest item will be returned. For min-heaps, the smallest
   51     item will be returned.
   52 
   53     The time complexity of this operation is O(log(n)) with respect to the size
   54     of the heap.
   55     """
   56     let n = size() - 1
   57     _data.swap_elements(0, n)?
   58     _sift_down(0, n)
   59     _data.pop()?
   60 
   61   fun ref append(
   62     seq: (ReadSeq[A] & ReadElement[A^]),
   63     offset: USize = 0,
   64     len: USize = -1)
   65   =>
   66     """
   67     Append len elements from a sequence, starting from the given offset.
   68     """
   69     _data.append(seq, offset, len)
   70     _make_heap()
   71 
   72   fun ref concat(iter: Iterator[A^], offset: USize = 0, len: USize = -1) =>
   73     """
   74     Add len iterated elements, starting from the given offset.
   75     """
   76     _data.concat(iter, offset, len)
   77     _make_heap()
   78 
   79   fun values(): ArrayValues[A, this->Array[A]]^ =>
   80     """
   81     Return an iterator for the elements in the heap. The order of elements is
   82     arbitrary.
   83     """
   84     _data.values()
   85 
   86   fun ref _make_heap() =>
   87     let n = size()
   88     if n < 2 then return end
   89     var i = (n / 2)
   90     while (i = i - 1) > 0 do
   91       _sift_down(i, n)
   92     end
   93 
   94   fun ref _sift_up(n: USize) =>
   95     var idx = n
   96     try
   97       while true do
   98         let parent_idx = (idx - 1) / 2
   99         if (parent_idx == idx) or not P(_data(idx)?, _data(parent_idx)?) then
  100           break
  101         end
  102         _data.swap_elements(parent_idx, idx)?
  103         idx = parent_idx
  104       end
  105     end
  106 
  107   fun ref _sift_down(start: USize, n: USize): Bool =>
  108     var idx = start
  109     try
  110       while true do
  111         var left = (2 * idx) + 1
  112         if (left >= n) or (left < 0) then
  113           break
  114         end
  115         let right = left + 1
  116         if (right < n) and P(_data(right)?, _data(left)?) then
  117           left = right
  118         end
  119         if not P(_data(left)?, _data(idx)?) then
  120           break
  121         end
  122         _data.swap_elements(idx, left)?
  123         idx = left
  124       end
  125     end
  126     idx > start
  127 
  128   fun _apply(i: USize): this->A ? =>
  129     _data(i)?
  130 
  131 type BinaryHeapPriority[A: Comparable[A] #read] is
  132   ( _BinaryHeapPriority[A]
  133   & (MinHeapPriority[A] | MaxHeapPriority[A]))
  134 
  135 interface val _BinaryHeapPriority[A: Comparable[A] #read]
  136   new val create()
  137   fun apply(x: A, y: A): Bool
  138 
  139 primitive MinHeapPriority[A: Comparable[A] #read] is _BinaryHeapPriority[A]
  140   fun apply(x: A, y: A): Bool =>
  141     x < y
  142 
  143 primitive MaxHeapPriority [A: Comparable[A] #read] is _BinaryHeapPriority[A]
  144   fun apply(x: A, y: A): Bool =>
  145     x > y