class RxRuby::PriorityQueue

Priority Queue implemented as a binary heap.

Public Class Methods

new() click to toggle source
# File lib/rx_ruby/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_ruby/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_ruby/internal/priority_queue.rb, line 45
def length
  @items.length
end
peek() click to toggle source
# File lib/rx_ruby/internal/priority_queue.rb, line 12
def peek
  @mutex.synchronize do
    unsafe_peek
  end
end
push(item) click to toggle source
# File lib/rx_ruby/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_ruby/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_ruby/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_ruby/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_ruby/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_ruby/internal/priority_queue.rb, line 51
def unsafe_peek
  @items.first.value unless @items.empty?
end