class Dynflow::Utils::PriorityQueue

Heavily inspired by rubyworks/pqueue

Public Class Methods

new() { |a, b| ... } click to toggle source
# File lib/dynflow/utils/priority_queue.rb, line 6
def initialize(&block) # :yields: a, b
  @backing_store = []
  @comparator = block || :<=>.to_proc
end

Public Instance Methods

pop() click to toggle source
# File lib/dynflow/utils/priority_queue.rb, line 24
def pop
  @backing_store.pop
end
push(element) click to toggle source
# File lib/dynflow/utils/priority_queue.rb, line 19
def push(element)
  @backing_store << element
  reposition_element(@backing_store.size - 1)
end
size() click to toggle source
# File lib/dynflow/utils/priority_queue.rb, line 11
def size
  @backing_store.size
end
to_a() click to toggle source
# File lib/dynflow/utils/priority_queue.rb, line 28
def to_a
  @backing_store
end
top() click to toggle source
# File lib/dynflow/utils/priority_queue.rb, line 15
def top
  @backing_store.last
end

Private Instance Methods

binary_index(array, target) click to toggle source

Find index where a new element should be inserted using binary search

# File lib/dynflow/utils/priority_queue.rb, line 45
def binary_index(array, target)
  upper = array.size - 1
  lower = 0

  while upper >= lower
    center = lower + (upper - lower) / 2

    case @comparator.call(target, array[center])
    when 0
      return center
    when 1
      lower = center + 1
    when -1
      upper = center - 1
    end
  end
  lower
end
reposition_element(index) click to toggle source

The element at index k will be repositioned to its proper place.

# File lib/dynflow/utils/priority_queue.rb, line 35
def reposition_element(index)
  return if size <= 1

  element = @backing_store.delete_at(index)
  index = binary_index(@backing_store, element)

  @backing_store.insert(index, element)
end