Class: RubyLabs::PriorityQueue
- Inherits:
-
Object
- Object
- RubyLabs::PriorityQueue
- 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
-
#on_canvas ⇒ Object
Returns the value of attribute on_canvas.
Instance Method Summary collapse
-
#<<(obj) ⇒ Object
Insert an item into the queue.
-
#[](i) ⇒ Object
Return the item at location
i
in the queue. -
#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 themap
operation defined for Ruby’s Enumeration interface). -
#each(&b) ⇒ Object
Evaluate block
b
for every item in the queue (equivalent toArray#each
). -
#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 toArray#each_with_index
). -
#initialize ⇒ PriorityQueue
constructor
Create a new, initially empty, priority queue.
-
#left_edge(tree) ⇒ Object
:nodoc:.
-
#right_edge(tree) ⇒ Object
:nodoc:.
-
#shift ⇒ Object
Remove the first item from the queue, returning a reference to that item.
-
#tree_sep(left, right) ⇒ Object
:nodoc:.
-
#update(op, node) ⇒ Object
Update the drawing of the priority queue after operation
op
has been performed onnode
.
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.[: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 |