Class: RubyPriorityQueue

Inherits:
Object show all
Includes:
Enumerable
Defined in:
lib/amp/dependencies/priority_queue/ruby_priority_queue.rb

Overview

Pure ruby Priority Queue

Defined Under Namespace

Classes: Node

Instance Attribute Summary collapse

Instance Method Summary collapse

Methods included from Enumerable

#inject, #select_map

Constructor Details

#initialize ⇒ RubyPriorityQueue

Create a new, empty PriorityQueue



163
164
165
166
167
168
 
# File 'lib/amp/dependencies/priority_queue/ruby_priority_queue.rb', line 163

def initialize
  @nodes = Hash.new
  @rootlist = nil
  @min = nil
  @length = 0
end

Instance Attribute Details

#length ⇒ Object (readonly)

Returns the number of elements of the queue.

q = PriorityQueue.new
q.length #=> 0
q[0] = 1
q.length #=> 1



160
161
162
 
# File 'lib/amp/dependencies/priority_queue/ruby_priority_queue.rb', line 160

def length
  @length
end

Instance Method Details

#[](key) ⇒ Object

call-seq:

[key] -> priority

Return the priority of a key or nil if the key is not in the queue.

q = PriorityQueue.new
(0..10).each do | i | q[i.to_s] = i end
q["5"] #=> 5
q[5] #=> nil



262
263
264
 
# File 'lib/amp/dependencies/priority_queue/ruby_priority_queue.rb', line 262

def [](key)
  @nodes[key] and @nodes[key].priority
end

#change_priority(key, priority) ⇒ Object

call-seq:

[key] = priority
change_priority(key, priority)
push(key, priority)

Set the priority of a key.

q = PriorityQueue.new
q["car"] = 50
q["train"] = 50
q["bike"] = 10
q.min #=> ["bike", 10]
q["car"] = 0
q.min #=> ["car", 0]



207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
 
# File 'lib/amp/dependencies/priority_queue/ruby_priority_queue.rb', line 207

def change_priority(key, priority)
  return push(key, priority) unless @nodes[key]

  n = @nodes[key]
  if n.priority < priority # Priority was increased. Remove the node and reinsert.
    self.delete(key)
    self.push(key, priority);
    return self
  end
  n.priority = priority;
  @min = n if n.priority < @min.priority

  return self if !n.parent or n.parent.priority <= n.priority # Already in rootlist or bigger than parent
  begin # Cascading Cuts
    p = n.parent
    cut_node(n)
    n = p
  end while n.mark and n.parent
  n.mark = true if n.parent

  self
end

#delete(key) ⇒ Object

call-seq:

delete(key) -> [key, priority]
delete(key) -> nil

Delete a key from the priority queue. Returns nil when the key was not in the queue and [key, priority] otherwise.

q = PriorityQueue.new
(0..10).each do | i | q[i.to_s] = i end
q.delete(5)                              #=> ["5", 5]
q.delete(5)                              #=> nil



354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
 
# File 'lib/amp/dependencies/priority_queue/ruby_priority_queue.rb', line 354

def delete(key)
  return nil unless n = @nodes.delete(key)

  if n.child 
    c = n.child
    e = n.child
    begin
     r = c.right
     cut_node(c)
     c = r
    end while c != e
  end
  cut_node(n) if n.parent

  if n == n.right 
    @min = nil;
    @rootlist = nil;
  else 
    @rootlist = n.right if @rootlist == n
    if @min == n
     n1 = n.right
     @min = n1
     begin
       @min = n1 if n1.priority < @min.priority
       n1 = n1.right
     end while(n1 != n);
    end
    n.right.left = n.left
    n.left.right = n.right
    n.left = n
    n.right = n
  end
  @length -= 1
  return [n.key, n.priority]
end

#delete_min ⇒ Object

call-seq:

delete_min -> [key, priority]

Delete key with minimal priority and return [key, priority]

q = PriorityQueue.new
q["a"] = 1
q["b"] = 0
q.delete_min #=> ["b", 0]
q.delete_min #=> ["a", 1]
q.delete_min #=> nil



431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
 
# File 'lib/amp/dependencies/priority_queue/ruby_priority_queue.rb', line 431

def delete_min
  return nil if self.empty?
  result = self.min

  @nodes.delete(@min.key)

  if @length == 1
    @rootlist = @min = nil
    @length = 0
  else 
    min = @min
    if @min == @rootlist # If the rootlist is anchored at the minimum, shift to the right
     if @rootlist == @rootlist.right 
       @rootlist = @min = nil
     else
       @rootlist = @min = @min.right
     end 
    end
    min.left.right = min.right;
    min.right.left = min.left;
    min.left = min.right = min;
    if min.child
     # Kinder und Eltern trennen, Markierung aufheben
     n = min.child;
     begin
       n.parent = nil;
       n.mark = false;
       n = n.right;
     end while n != min.child
      
     # Kinder einfugen
     if @rootlist
       l1 = @rootlist.left
       l2 = n.left
      
       l1.right = n
       n.left = l1
       l2.right = @rootlist
       @rootlist.left = l2
     else
       @rootlist = n
     end
    end

    # Grosse anpassen
    @length -= 1

    # Wieder aufhubschen
    consolidate
  end

  result
end

#delete_min_return_key ⇒ Object

call-seq:

delete_min_return_key -> key

Delete key with minimal priority and return the key

q = PriorityQueue.new
q["a"] = 1
q["b"] = 0
q.delete_min_return_key #=> "b"
q.delete_min_return_key #=> "a"
q.delete_min_return_key #=> nil



401
402
403
 
# File 'lib/amp/dependencies/priority_queue/ruby_priority_queue.rb', line 401

def delete_min_return_key
  delete_min[0] rescue nil
end

#delete_min_return_priority ⇒ Object

call-seq:

delete_min_return_priority -> priority

Delete key with minimal priority and return the priority value

q = PriorityQueue.new
q["a"] = 1
q["b"] = 0
q.delete_min_return_priority #=> 0
q.delete_min_return_priority #=> 1
q.delete_min_return_priority #=> nil



416
417
418
 
# File 'lib/amp/dependencies/priority_queue/ruby_priority_queue.rb', line 416

def delete_min_return_priority
  delete_min[1] rescue nil
end

#display_dot ⇒ Object

Call dot and gv displaying the datstructure



188
189
190
191
 
# File 'lib/amp/dependencies/priority_queue/ruby_priority_queue.rb', line 188

def display_dot
  puts to_dot
  system "echo '#{to_dot}' | twopi -Tps -Groot=ROOT -Goverlap=false> /tmp/dotfile.ps; gv /tmp/dotfile.ps"
end

#each ⇒ Object

Call the given block with each [key, priority] pair in the queue

Beware: Changing the queue in the block may lead to unwanted behaviour and even infinite loops.



285
286
287
288
289
 
# File 'lib/amp/dependencies/priority_queue/ruby_priority_queue.rb', line 285

def each
  @nodes.each do | key, node |
    yield(key, node.priority)
  end
end

#empty? ⇒ Boolean

Returns true if the array is empty, false otherwise.

Returns:



249
250
251
 
# File 'lib/amp/dependencies/priority_queue/ruby_priority_queue.rb', line 249

def empty?
  @rootlist.nil?
end

#has_key?(key) ⇒ Boolean

call-seq:

has_key? key -> boolean

Return false if the key is not in the queue, true otherwise.

q = PriorityQueue.new
(0..10).each do | i | q[i.to_s] = i end
q.has_key("5") #=> true 
q.has_key(5)   #=> false

Returns:



275
276
277
 
# File 'lib/amp/dependencies/priority_queue/ruby_priority_queue.rb', line 275

def has_key?(key)
  @nodes.has_key?(key)
end

#initialize_copy(copy) ⇒ Object 



490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
 
# File 'lib/amp/dependencies/priority_queue/ruby_priority_queue.rb', line 490

def initialize_copy(copy)
  copy_nodes = @nodes
  @nodes = {}

  copy_nodes.each do | (_, cn) |
    n = @nodes[cn.key] = Node.new(cn.key, cn.priority)
    n.mark = cn.mark
    n.degree = cn.degree
  end
  
  copy_nodes.each do | (_, cn) |
    n = @nodes[cn.key]
    n.left   = @nodes[cn.left.key]   if cn.left
    n.right  = @nodes[cn.right.key]  if cn.right
    n.parent = @nodes[cn.parent.key] if cn.parent
    n.child  = @nodes[cn.child.key]  if cn.child
  end
  @rootlist = @nodes[@rootlist.key] if @rootlist
  @min = @nodes[@min.key] if @min
  self
end

#inspect ⇒ Object

Returns a string representation of the priority queue.



486
487
488
 
# File 'lib/amp/dependencies/priority_queue/ruby_priority_queue.rb', line 486

def inspect
  "<PriorityQueue: #{@nodes.map{|(_, n)| [n.key, n.priority]}.sort_by{|(_,p)|p}.inspect}>"
end

#min ⇒ Object

call-seq:

min -> [object, priority]

Return the pair [object, priority] with minimal priority or nil when the queue is empty.

q = PriorityQueue.new
q["a"] = 10
q["b"] = 20
q.min          #=> ["a", 10]
q.delete_min   #=> ["a", 10]
q.min          #=> ["b", 20]
q.delete_min   #=> ["b", 20]
q.min          #=> nil



305
306
307
 
# File 'lib/amp/dependencies/priority_queue/ruby_priority_queue.rb', line 305

def min
  [@min.key, @min.priority] rescue nil
end

#min_key ⇒ Object

call-seq:

min_key -> object

Return the key that has the minimal priority or nil when the queue is empty.

q = PriorityQueue.new
q["a"] = 10
q["b"] = 20
q.min_key      #=> "a"
q.delete_min   #=> ["a", 10]
q.min_key      #=> "b"
q.delete_min   #=> ["b", 20]
q.min_key      #=> nil



322
323
324
 
# File 'lib/amp/dependencies/priority_queue/ruby_priority_queue.rb', line 322

def min_key    
  @min.key rescue nil
end

#min_priority ⇒ Object

call-seq:

min_priority -> priority

Return the minimal priority or nil when the queue is empty.

q = PriorityQueue.new
q["a"] = 10
q["b"] = 20
q.min_priority #=> 10
q.delete_min   #=> ["a", 10]
q.min_priority #=> 20
q.delete_min   #=> ["b", 20]
q.min_priority #=> nil



339
340
341
 
# File 'lib/amp/dependencies/priority_queue/ruby_priority_queue.rb', line 339

def min_priority
  @min.priority rescue nil
end

#push(key, priority) ⇒ Object Also known as: []=

Add an object to the queue.



231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
 
# File 'lib/amp/dependencies/priority_queue/ruby_priority_queue.rb', line 231

def push(key, priority)    
  return change_priority(key, priority) if @nodes[key]
  @nodes[key] = node = Node.new(key, priority)
  @min = node if !@min or priority < @min.priority
  if not @rootlist
    @rootlist = node
    node.left = node.right = node
  else
    node.left = @rootlist.left
    node.right = @rootlist
    @rootlist.left.right = node
    @rootlist.left = node
  end
  @length += 1
  self
end

#to_dot ⇒ Object

Print a priority queue as a dot-graph. The output can be fed to dot from the vizgraph suite to create a tree depicting the internal datastructure.



172
173
174
175
176
177
178
179
180
181
182
183
184
185
 
# File 'lib/amp/dependencies/priority_queue/ruby_priority_queue.rb', line 172

def to_dot
  r = ["digraph fibheap {"]
  #r << @rootlist.to_dot.join("\n") if @rootlist
    r << "ROOT -> #{@rootlist.dot_id};" if @rootlist
    @nodes.to_a.sort.each do | (_, n) |
    r << "  #{n.dot_id} [label=\"#{n.key}: #{n.priority}\"];"
    r << "  #{n.dot_id} -> #{n.right.dot_id} [constraint=false];" if n.right# and n.dot_id < n.right.dot_id
    r << "  #{n.dot_id} -> #{n.left.dot_id} [constraint=false];" if n.left #and n.dot_id < n.left.dot_id
    r << "  #{n.dot_id} -> #{n.child.dot_id}" if n.child
  end
  r << "}"
  r.join("\n")
  r
end