class Rx::PriorityQueue
Priority Queue implemented as a binary heap.
Public Class Methods
new()
click to toggle source
# File lib/rx/internal/priority_queue.rb, line 7 def initialize @items = [] @mutex = Mutex.new end
Public Instance Methods
delete(item)
click to toggle source
# File lib/rx/internal/priority_queue.rb, line 33 def delete(item) @mutex.synchronize do index = @items.index {|it| it.value == item } if index delete_at index true else false end end end
length()
click to toggle source
# File lib/rx/internal/priority_queue.rb, line 45 def length @items.length end
peek()
click to toggle source
# File lib/rx/internal/priority_queue.rb, line 12 def peek @mutex.synchronize do unsafe_peek end end
push(item)
click to toggle source
# File lib/rx/internal/priority_queue.rb, line 26 def push(item) @mutex.synchronize do @items.push IndexedItem.new(item) percolate length - 1 end end
shift()
click to toggle source
# File lib/rx/internal/priority_queue.rb, line 18 def shift @mutex.synchronize do result = unsafe_peek delete_at 0 result end end
Private Instance Methods
delete_at(index)
click to toggle source
# File lib/rx/internal/priority_queue.rb, line 55 def delete_at(index) substitute = @items.pop if substitute and index < @items.length @items[index] = substitute heapify index end end
heapify(index)
click to toggle source
bubble down an item while it’s bigger than children
# File lib/rx/internal/priority_queue.rb, line 79 def heapify(index) current_index = index left_index = 2 * index + 1 right_index = 2 * index + 2 current_value = @items[index] left_value = @items[left_index] right_value = @items[right_index] if right_value && right_value < current_value && right_value < left_value current_index = right_index elsif left_value && left_value < current_value current_index = left_index end if current_index != index @items[index] = @items[current_index] @items[current_index] = current_value heapify current_index end end
percolate(index)
click to toggle source
bubble up an item while it’s smaller than parents
# File lib/rx/internal/priority_queue.rb, line 64 def percolate(index) parent = (index - 1) / 2 return if parent < 0 current_value = @items[index] parent_value = @items[parent] if current_value < parent_value @items[index] = parent_value @items[parent] = current_value percolate parent end end
unsafe_peek()
click to toggle source
# File lib/rx/internal/priority_queue.rb, line 51 def unsafe_peek @items.first.value unless @items.empty? end