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.



1401
1402
1403
 
# File 'lib/rubylabs.rb', line 1401

def initialize
  @q = Array.new
end

Instance Attribute Details

#on_canvas ⇒ Object

Returns the value of attribute on_canvas.



911
912
913
 
# File 'lib/bitlab.rb', line 911

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.



1418
1419
1420
1421
1422
1423
1424
1425
1426
1427
1428
 
# File 'lib/rubylabs.rb', line 1418

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.



1456
1457
1458
 
# File 'lib/rubylabs.rb', line 1456

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]



1470
1471
1472
 
# File 'lib/rubylabs.rb', line 1470

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"]



1485
1486
1487
 
# File 'lib/rubylabs.rb', line 1485

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"]



1501
1502
1503
 
# File 'lib/rubylabs.rb', line 1501

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

#left_edge(tree) ⇒ Object

:nodoc:



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

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:



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

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"]



1442
1443
1444
1445
1446
 
# File 'lib/rubylabs.rb', line 1442

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

#tree_sep(left, right) ⇒ Object

:nodoc:



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

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).



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

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