Joel VanderWerf
3/9/2005 6:48:00 AM
I couldn't find a nice PriorityQueue in ruby, so I patched one together
using Queue and RBTree. Here it is. Hope someone will find it useful. A
test of the priority ordering property is included. You can find RBTree
using RAA or rpa, but not gem.
require 'rbtree'
require 'thread'
class PriorityQueue < Queue
module MakeMultiRBTreeLikePriorityQueue
# Push object with priority specified by +pri+ or the object's
# #queue_priority method.
def push(obj, pri = obj.queue_priority)
store(pri, obj)
end
# Return oldest item among those with highest key.
def shift
last && delete(last[0])
end
end
def initialize(*)
super
@que = MultiRBTree.new
@que.extend MakeMultiRBTreeLikePriorityQueue
end
# Push +obj+ with priority equal to +pri+ if given or, otherwise,
# the result of sending #queue_priority to +obj+. Objects are
# dequeued in priority order, and first-in-first-out among objects
# with equal priorities. Implementation is the same as the std lib,
# except for the priority arg.
def push(obj, pri = obj.queue_priority)
Thread.critical = true
@que.push obj, pri
begin
t = @waiting.shift
t.wakeup if t
rescue ThreadError
retry
ensure
Thread.critical = false
end
begin
t.run if t
rescue ThreadError
end
end
end
__END__
Thread.abort_on_exception = true
pq = PriorityQueue.new
n = 100
t1 = Thread.new do
n.times do |i|
pri = rand(5)
pq.push([pri, i], pri)
end
end
result = []
t2 = Thread.new do
n.times do
result << pq.pop
end
end
t1.join
t2.join
#puts result.map {|a| a.inspect}.join("\n")
sorted_result = result.sort do |(pri1,i1),(pri2,i2)|
[pri2,i1] <=> [pri1,i2]
end
#puts sorted_result.map {|a| a.inspect}.join("\n")
raise unless result == sorted_result