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