From: Artem Voroztsov <artem.voroztsov@...>
Date: 2008-09-10T05:35:09+09:00
Subject: Re: Extending standard library by priority queue or search tree

Thank you all!

2008/9/9 Joel VanderWerf <vjoel@path.berkeley.edu>:
> 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
>
>