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