als RSS-Feed abonnieren
Hundezuechter
McKinsey
XML-Ferientermine
xml-ferientermine
Go-Spiel-bei-DGS
Projektarbeit
Wohnungssuche
Bewerbungen
Ruby-in-Second-Life
Clatronic-CTV731-bei-Saturn
T_Shirts_Mousepads
Singleboersenvergleich
TimeSystem
Katzen
katzen
Arbeitsamt_I
Klick
2007-01-21
2007-01-19
Leapc
iMacros-to-Watir-Konverter
ASP
Ruby-Stocks
National-Geograpic
Google-Kalender
XML-Ruby
XMLTV
css
scribus
ruby-links
c-sharp
videos-fuer-psp-konvertieren
tchibo-infoglobe
uuencode-ruby
linux-phone-neo-1973
mx600-mouse
ruby-mechanize-https
ncurses
internetcafes
corba
ruby-einladung
ruby-setup
ruby-xml
watir
find-ersatz-in-ruby
ruby-priority-queue
gem-needle
gem-dependency
index
DotNetTests
TDD
Gadgets
RSS
Geocaching
2006-10-22_CSS_hier
2006-10-22-zaurus
2006-10-22
2006-10-22_Mono_und_Linux


vom: 2006-10-23 23:06

Von:        Joel VanderWerf - Profil anzeigen
Datum:        Mi 9 Mrz. 2005 08:47
E-Mail:         Joel VanderWerf <v...@PATH.Berkeley.EDU>
Gruppen:         comp.lang.ruby
Noch nicht bewertet
Bewertung:     
Optionen anzeigen
Antworten | Antwort an Autor | Weiterleiten | Drucken | Einzelne Nachricht | Original anzeigen | Missbrauch melden | Nachrichten dieses Autors suchen

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 

Kontakt: Thomas Preymesser
Prinzenallee 36
13359 Berlin
Telefon: 030 - 49 78 37 06
mobile: 0172-8111959
eMail: thopre@gmail.com