Class: RubyLabs::PriorityQueue

Inherits:
Object
  • Object
show all
Defined in:
lib/bitlab.rb,
lib/rubylabs.rb

Overview

PriorityQueue

A PriorityQueue is a collection of objects that is always maintained in order. Any kind of object can be in the queue as long as it can be compared with the < operator. More precisely, if an object x responds to the < operator, and x < y is defined for every object y already in the queue, then x can be inserted.

The methods that insert and remove items check to see if an instance variable named @on_canvas is true. If so, a method named update is called.

update is not defined here, but is added to the class by modules that use the queue during visualizations (see the definition of the priority queue used in the Huffman tree project in bitlab.rb for an example).

Several methods of the Array class are defined dynamically in the PriorityQueue class when this module is loaded. These methods have the same meaning for PriorityQueue objects as they do for Array objects:

length

return the number of items in the queue

first

return a reference to the first item in the queue

last

return a reference to the last item in the queue

to_s

generate a String representation of the queue (by calling Array#to_s)

inspect

generate a String representation of the queue (by calling Array#inspect)

clear

remove all items from the queue

empty?

return true if the queue has no items

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ PriorityQueue

Create a new, initially empty, priority queue.



1408
1409
1410
 
# File 'lib/rubylabs.rb', line 1408

def initialize
  @q = Array.new
end

Instance Attribute Details

#on_canvas ⇒ Object

Returns the value of attribute on_canvas.



909
910
911
 
# File 'lib/bitlab.rb', line 909

def on_canvas
  @on_canvas
end

Instance Method Details

#<<(obj) ⇒ Object

Insert an item into the queue. The item’s location is determined by how it compares with other items, according to the < operator. Specifically, when item x is added to a queue, it it put before the first item y where x < y.

Example: suppose object q has three strings:

>> q
=> ["Au", "He", "O"]

This expression adds the string “Fe” to the queue:

>> q << "Fe"
=> ["Au", "Fe", "He", "O"]

The new string went into the second position because “Fe” < “Au” is false but “Fe” < “He” is true.



1425
1426
1427
1428
1429
1430
1431
1432
1433
1434
1435
 
# File 'lib/rubylabs.rb', line 1425

def <<(obj)
  raise "Object cannot be inserted into priority queue" unless obj.respond_to?(:<)
  i = 0
  while (i < @q.length)
    break if obj < @q[i]
    i += 1
  end
  @q.insert(i, obj)
  update(:insert, obj) if @on_canvas
  return @q
end

#[](i) ⇒ Object

Return the item at location i in the queue. Note: unlike Array objects, an index expression cannot be used on the left side of an assignment. If q is a PriorityQueue object,

x = q[i]

is valid, but

q[i] = x

is undefined.



1463
1464
1465
 
# File 'lib/rubylabs.rb', line 1463

def [](i)
  @q[i]
end

#collect(&f) ⇒ Object

Call f for every item in the queue, and return an array with the result of each call (essentially the same as the map operation defined for Ruby’s Enumeration interface).

Example:

>> q
=> ["avocado", "boysenberry", "clementine", "elderberry", "loquat"]
>> q.collect { |x| x.length }
=> [7, 11, 10, 10, 6]



1477
1478
1479
 
# File 'lib/rubylabs.rb', line 1477

def collect(&f)
  @q.map { |x| f.call(x) }
end

#each(&b) ⇒ Object

Evaluate block b for every item in the queue (equivalent to Array#each)

Example:

>> q
=> ["Au", "He", "O"]
>> q.each { |x| puts x }
Ar
He
O
=> ["Au", "He", "O"]



1492
1493
1494
 
# File 'lib/rubylabs.rb', line 1492

def each(&b)
  @q.each &b
end

#each_with_index(&b) ⇒ Object

Evaluate block b for every item in the queue, also passing the item’s location in the queue to the block (equivalent to Array#each_with_index)

Example:

>> q
=> ["Au", "He", "O"]
>> q.each_with_index { |x,i| puts "#{i}: #{x}" }
0: Ar
1: He
2: O
=> ["Au", "He", "O"]



1508
1509
1510
 
# File 'lib/rubylabs.rb', line 1508

def each_with_index(&b)
  @q.each_with_index &b
end

#left_edge(tree) ⇒ Object

:nodoc:



946
947
948
949
950
951
952
953
 
# File 'lib/bitlab.rb', line 946

def left_edge(tree)   # :nodoc:
  x = tree.coords.x
  while tree.lfchain != tree
    tree = tree.lfchain
    x = min(x, tree.coords.x)
  end
  return x
end

#right_edge(tree) ⇒ Object

:nodoc:



955
956
957
958
959
960
961
962
 
# File 'lib/bitlab.rb', line 955

def right_edge(tree)  # :nodoc:
  x = tree.coords.x
  while tree.rfchain != tree
    tree = tree.rfchain
    x = max(x, tree.coords.x)
  end
  return x
end

#shift ⇒ Object

Remove the first item from the queue, returning a reference to that item.

Example: suppose object q has three strings:

>> q
=> ["Au", "He", "O"]

Then a call to shift removes the string “Au” and leaves the remaining items in order in the queue:

>> x = q.shift
=> "Au"
>> q
=> ["He", "O"]



1449
1450
1451
1452
1453
 
# File 'lib/rubylabs.rb', line 1449

def shift
  res = @q.shift
  update(:shift, res) if @on_canvas
  return res
end

#tree_sep(left, right) ⇒ Object

:nodoc:



964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
 
# File 'lib/bitlab.rb', line 964

def tree_sep(left, right)   # :nodoc:
  res = right.coords.x - left.coords.x
  while (left.rfchain != left && right.lfchain != right)
    left = left.rfchain
    right = right.lfchain
    dist = right.coords.x - left.coords.x
    res = dist if dist < res
  end
  # loop do
  #   puts "res = #{res}"
  #   break if left == left.rfchain || right == right.lfchain
  #   left = left.rfchain
  #   right = right.lfchain
  #   puts "down #{left.inspect} --- #{right.inspect}"
  #   dist = right.coords.x - left.coords.x
  #   res = dist if dist < res
  # end
  return res
end

#update(op, node) ⇒ Object

Update the drawing of the priority queue after operation op has been performed on node. Operation is either :shift or <<, and node is a reference to the Node object being removed or inserted into the queue.

Calls helper methods left_edge, right_edge, and tree_sep to figure out how to place subtrees to use the minimum amount of horizontal space (see bitlab.rb).



919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
 
# File 'lib/bitlab.rb', line 919

def update(op, node)
  if op == :shift
    move_tree(node, 0, 4 * @@unit)         # move subtree rooted at node down 4 units
  else
    i = 0
    dx = @@drawing.options[:qx] - left_edge(@q[0])
    while @q[i] != node
      move_tree(@q[i], dx, 0)
      dx = 3 * @@unit - tree_sep(@q[i], node)
      move_tree(node, dx, 0)
      dx = 3 * @@unit - tree_sep(@q[i], @q[i+1])
      i += 1
      sleep(0.2)
    end
    move_tree(node, 0, -2 * @@unit)
    if i < @q.length - 1
      dx = 3 * @@unit - tree_sep(@q[i], @q[i+1])
      i += 1
      while i < @q.length
        sleep(0.2)
        move_tree(@q[i], dx, 0)
        i += 1
      end
    end
  end
end