Class: Bogo::PriorityQueue
- Inherits:
-
Object
- Object
- Bogo::PriorityQueue
- Defined in:
- lib/bogo/priority_queue.rb
Overview
Note:
does not allow duplicate objects to be queued
Specialized priority based queue
Instance Method Summary collapse
- #empty? ⇒ TrueClass, FalseClass
- #include?(object) ⇒ TrueClass, FalseClass
-
#initialize(*args) ⇒ self
constructor
Create a new priority queue.
-
#multi_push(items) ⇒ self
Push multiple items onto the queue at once.
-
#pop ⇒ Object, NilClass
Item or nil if empty.
-
#push(item, cost = nil) { ... } ⇒ self
Push new item to the queue.
-
#size ⇒ Integer
Current size of queue.
-
#sort! ⇒ Object
Sort the queue based on cost.
Constructor Details
#initialize(*args) ⇒ self
Create a new priority queue
11 12 13 14 15 16 |
# 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 |
Instance Method Details
#empty? ⇒ TrueClass, FalseClass
80 81 82 |
# File 'lib/bogo/priority_queue.rb', line 80 def empty? size == 0 end |
#include?(object) ⇒ TrueClass, FalseClass
85 86 87 88 89 |
# File 'lib/bogo/priority_queue.rb', line 85 def include?(object) lock.synchronize do queue.keys.include?(object) end end |
#multi_push(items) ⇒ self
Push multiple items onto the queue at once
43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
# 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 ⇒ Object, NilClass
Returns item or nil if empty.
62 63 64 65 66 67 68 69 70 |
# 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) { ... } ⇒ self
Push new item to the queue
24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
# 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 ⇒ Integer
Returns current size of queue.
73 74 75 76 77 |
# File 'lib/bogo/priority_queue.rb', line 73 def size lock.synchronize do queue.size end end |
#sort! ⇒ Object
Sort the queue based on cost
92 93 94 95 96 97 98 99 100 101 102 103 104 |
# 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 |