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 5 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 23 def pop @backing_store.pop end
push(element)
click to toggle source
# File lib/dynflow/utils/priority_queue.rb, line 18 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 10 def size @backing_store.size end
to_a()
click to toggle source
# File lib/dynflow/utils/priority_queue.rb, line 27 def to_a @backing_store end
top()
click to toggle source
# File lib/dynflow/utils/priority_queue.rb, line 14 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 44 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 34 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