From: Joel VanderWerf <vjoel@...>
Date: 2008-09-10T03:44:31+09:00
Subject: Re: Extending standard library by priority queue or search tree

Robert Klemme wrote:
> Rather put an RBTree into the std lib.  Note that such a thing does
> exist already:
> 
> http://raa.ruby-lang.org/search.rhtml?search=rbtree

Also: gem install rbtree

Using rbtree, a priority queue is simple:

require 'rbtree'

class PriorityQueue
   def initialize
     @tree = MultiRBTree.new
     @mutex = Mutex.new
     @cond = ConditionVariable.new
   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.
   def push(obj, pri = obj.queue_priority)
     @mutex.synchronize do
       @tree.store(pri, obj)
       @cond.signal
     end
   end

   def pop(non_block=false)
     @mutex.synchronize do
       if (last=@tree.last)
         return @tree.delete(last[0]) # highest key, oldest first
       end

       if non_block
         raise ThreadError, "priority queue empty"
       end

       loop do
         @cond.wait(@mutex)
         if (last=@tree.last)
           return @tree.delete(last[0])
         end
       end
     end
   end
end

pq = PriorityQueue.new
pq.push "a", 1
pq.push "c", 3
pq.push "b", 2
p pq.pop


-- 
       vjoel : Joel VanderWerf : path berkeley edu : 510 665 3407