#!/usr/bin/ruby
#
# Drawing Trees
#
# A response to Ruby Quiz of the Week #40 [ruby-talk:149184]
#
# The Heap implementation is from the quiz question.
#
# The tree drawing algorithm in to_s, and the helper methods empty? and depth
# are mine.
#
# Author: Dave Burt
#
# Created: 25 Jul 2005
#
# Last modified: 26 Jul 2005
#
# Fine print: Provided as is. Use at your own risk. Unauthorized copying is
# not disallowed. Credit's appreciated if you use my code. I'd
# appreciate seeing any modifications you make to it.
class Heap
def initialize( *elements, &comp )
@heap = [nil]
@comp = comp || lambda { |p, c| p <=> c }
insert(*elements)
end
def clear( )
@heap = [nil]
end
def extract( )
extracted = @heap[1]
@heap[1] = @heap.pop unless @heap.empty?
sift_down
extracted
end
def insert( *elements )
elements.each do |element|
@heap << element
sift_up
end
end
def size( )
@heap.size - 1
end
def inspect( )
@heap[1..-1].inspect
end
#
# Use a right-hand-side depth-first traversal of the tree to draw the right
# arms above the left arms, with the root at the left and leaves on the
# right:
#
# 1-3
# `2
#
def to_s( )
# empty heap -> empty string
return "" if empty?
d = depth
# w is the width of a column
w = Array.new(d) do |i|
@heap[2**i, 2**i].inject(0) {|m, o| [m, o.to_s.size].max }
end
# ww is the total width of the string (and of each line in it)
ww = w.inject {|m, o| m + o + 1 } - 1
# done is a flag for the traversal algorithm - it marks indexes in
# @heap that have already been traversed.
done = Array.new(2**d)
done[0] = true
# s is the string that will be returned
s = ""
# The outer loop counts down the last @heap index for each row. last
# takes the index of each leaf node, from right to left.
(2**d - 1).downto(2**(d - 1)) do |last|
# a accumulates a list of @heap indexes for a row
a = [last]
a << (a.last >> 1) until done[a.last >> 1]
a.each {|x| done[x] = true }
# The inner loop iterates through the columns, from the root to the
# leaves.
(d - 1).downto(0) do |col|
# Append a fixed-width string: a node, a line or spaces
s << "%#{w[d - col - 1] + 1}s" %
if a.size > col # a node
@heap[a[col]].to_s + "-"
elsif last >> col - 1 & 1 == 1 # a line
"| "
elsif (last + 1) >> col - 1 & 1 == 1 # an "L" angle
"`-"
end
end
# Replace the trailing "-" after all the leaf nodes with a newline.
s[-1] = "\n"
end
s
end
def empty?( )
size == 0
end
def depth( )
if empty?
0
else
(Math.log(@heap.size - 1) / Math.log(2)).to_i + 1
end
end
private
def sift_down( )
i = 1
loop do
c = 2 * i
break if c >= @heap.size
c += 1 if c + 1 < @heap.size and @heap[c + 1] < @heap[c]
break if @comp[@heap[i], @heap[c]] <= 0
@heap[c], @heap[i] = @heap[i], @heap[c]
i = c
end
end
def sift_up( )
i = @heap.size - 1
until i == 1
p = i / 2
break if @comp[@heap[p], @heap[i]] <= 0
@heap[p], @heap[i] = @heap[i], @heap[p]
i = p
end
end
end
if $0 == __FILE__
priority_queue = Heap.new
priority_queue.insert(12, 20, 15, 29, 23, 17, 22, 35, 40, 26, 51, 19)
puts priority_queue
priority_queue.insert(13)
puts priority_queue
priority_queue.extract
puts priority_queue
priority_queue.clear
priority_queue.insert("another", "are", "data", "random", "heap", "of",
"kind", "this", "the", "words", "on", "to", "some", "test")
puts priority_queue
end