From: Joel VanderWerf <vjoel@...>
Date: 2005-03-09T15:47:56+09:00
Subject: priority queue using RBTree

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