priority queue using RBTree

[Joel VanderWerf]

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

 

[Joel VanderWerf]

On Wed, 9 Mar 2005, Joel VanderWerf wrote:

very cool joel - i'm pasting this one into my personal lib. i use
rbtree all
the time and think it's one of the most underrated libs on the raa - i'd be
great to see it in the core...

Thanks! (And thanks for mailing directly--the gateway seems to be
list->ng only these days.)

I would also like rbtree in the stdlib... anyone else?

Btw, these aliases should be added to PriorityQueue for completeness, in
case you use << or enq:

alias << push
alias enq push

 

[Martin DeMello]

I would also like rbtree in the stdlib... anyone else?

+1

In fact, having a priority queue in there would be a nice idea too.

martin