class Bogo::PriorityQueue

Specialized priority based queue @note does not allow duplicate objects to be queued

Attributes

lock[R]
queue[R]

Public Class Methods

new(*args) click to toggle source

Create a new priority queue

@return [self]

# File lib/bogo/priority_queue.rb, line 11
def initialize(*args)
  @lock = Mutex.new
  @queue = Hash.new
  @block_costs = 0
  @reverse_sort = args.include?(:highscore)
end

Public Instance Methods

empty?() click to toggle source

@return [TrueClass, FalseClass]

# File lib/bogo/priority_queue.rb, line 80
def empty?
  size == 0
end
include?(object) click to toggle source

@return [TrueClass, FalseClass]

# File lib/bogo/priority_queue.rb, line 85
def include?(object)
  lock.synchronize do
    queue.keys.include?(object)
  end
end
multi_push(items) click to toggle source

Push multiple items onto the queue at once

@param items [Array<Array<item, cost>>] @return [self]

# File lib/bogo/priority_queue.rb, line 43
def multi_push(items)
  lock.synchronize do
    items.each do |item_pair|
      item, cost = item_pair
      if(queue[item])
        raise ArgumentError.new "Item already exists in queue. Items must be unique! (#{item})"
      end
      unless(cost.is_a?(Numeric) || cost.is_a?(Proc))
        raise ArgumentError.new "Cost must be provided as parameter or proc! (item: #{item})"
      end
      @block_costs += 1 if cost.is_a?(Proc)
      queue[item] = cost
    end
  end
  sort!
  self
end
pop() click to toggle source

@return [Object, NilClass] item or nil if empty

# File lib/bogo/priority_queue.rb, line 62
def pop
  sort! if @block_costs > 0
  lock.synchronize do
    item, score = queue.first
    @block_costs -= 1 if score.respond_to?(:call)
    queue.delete(item)
    item
  end
end
push(item, cost=nil, &block) click to toggle source

Push new item to the queue

@param item [Object] @param cost [Float] @yield provide cost via proc @return [self]

# File lib/bogo/priority_queue.rb, line 24
def push(item, cost=nil, &block)
  lock.synchronize do
    if(queue[item])
      raise ArgumentError.new "Item already exists in queue. Items must be unique! (#{item})"
    end
    unless(cost || block_given?)
      raise ArgumentError.new 'Cost must be provided as parameter or block!'
    end
    @block_costs += 1 if cost.nil?
    queue[item] = cost || block
  end
  sort!
  self
end
size() click to toggle source

@return [Integer] current size of queue

# File lib/bogo/priority_queue.rb, line 73
def size
  lock.synchronize do
    queue.size
  end
end
sort!() click to toggle source

Sort the queue based on cost

# File lib/bogo/priority_queue.rb, line 92
def sort!
  lock.synchronize do
    queue.replace(
      Hash[
        queue.sort do |x,y|
          x,y = y,x if @reverse_sort
          (x.last.respond_to?(:call) ? x.last.call : x.last).to_f <=>
            (y.last.respond_to?(:call) ? y.last.call : y.last).to_f
        end
      ]
    )
  end
end