From: David Brady <ruby_talk@...>
Date: 2005-07-30T09:08:58+09:00
Subject: Re: [QUIZ] Drawing Trees (#40) [SOLUTION]

Sorry if this is too late to be a legitimate entry.

James, what is the official way to submit an entry?  If posting to the 
list is good enough, here you go.  :-)

My solution doesn't use recursion.  It deterministically transforms 
(heapindex, heapsize) coordinates into (x, y) coordinates.  My only 
gripe with this solution is that pre-initializing a 2D text buffer 
beforehand looks kinda kludgy.

My full solution is at http://www.shinybit.com/ruby_quiz_40.rb , but 
it's just the original code from James (with the bugfix addendum) with 
three methods added.  They are poorly named and could use some cleaning 
up.  Here is my output, followed by the three methods I added to the 
Heap class.

I've used some kludgy mechanisms in my code.  I would *love* to hear any 
input on how to clean them up.  If you spot an obviously missing Ruby 
idiom, please let me know.

The output:

dbrady@gromit:~$ ruby ruby_quiz_40.rb
         ,- 35
     ,- 29
     |   `- 40
 ,- 20
 |   |   ,- 26
 |   `- 23
 |       `- 51
12
 |       ,- 19
 |   ,- 17
 |   |
 `- 15
     |
     `- 22
         ,- 35
     ,- 29
     |   `- 40
 ,- 20
 |   |   ,- 26
 |   `- 23
 |       `- 51
12
 |       ,- 19
 |   ,- 15
 |   |   `- 17
 `- 13
     |
     `- 22
         ,- 35
     ,- 29
     |   `- 40
 ,- 20
 |   |   ,- 26
 |   `- 23
 |       `- 51
13
 |       ,- 19
 |   ,- 17
 |   |
 `- 15
     |
     `- 22

And here are the three methods I added to the Heap class:

  # One bit of kludginess: The /= operator breaks indenting in emacs
  # ruby-mode.  This is why I use the x = x / 2 form instead.

  # ----------------------------------------------------------------------
  # get_depth
  #
  # returns the depth in the tree of a given 0-based index.
  # num - 1-based index of element.
  # returns - depth of the tree at this index.  The root node has a
  # depth of zero.
  def get_depth(num)
    (Math.log(num)/Math.log(2)).to_i
  end

  # ----------------------------------------------------------------------
  # get_line
  #
  # for index num in a heap of depth rows, returns the line.
  # num is 1-based index of element.
  # returns 0-based line number, with 0 at the top (left-hand
  # side).  Sample tree, get_line(1) returns 7, etc.
  def get_line(num)
    depth = get_depth(@heap.length)
    # Okay, scary algorithm.  Odd-numbered indexes are down from their
    # parents while even-numbered indexes are up from their parents.
    # We want to move from this node, up the tree to the root,
    # considering each node for even/oddness.  At the leafmost level,
    # the leaves move up or down 1 line.  Each level you move up, the
    # offset doubles, until node 1 is moved down 1/2 the size of the
    # tree (because it's odd).
    line = 0
    while num > 0
      offset = 2**(depth - get_depth(num))
      if num % 2 == 1
        line += offset
      else
        line -= offset
      end
      num = num / 2 # Integer divide to get parent index.
    end
    line-1
  end
 
  # ----------------------------------------------------------------------
  # to_s
  #
  # converts the heap to an ascii art tree representation.
  def to_s
    output = []

    # Initialize output as an array of strings.  We're going to "draw" 
into the
    # output like it's a 2D text buffer, so we need to make sure the 
output is
    # initialized with indent strings.  (By an odd coincidence, all of 
ascii art
    # is confined to the area to the left of each given string.  
However, some
    # elements are empty, so we need to make sure that all lines have 
their left
    # indent already buffered out.
    #
    # This hairy bit of math calculates the next largest power of 2 up 
from @heap.length.
    max_lines = 2**((Math.log(@heap.length)/Math.log(2)).to_i + 1)
    max_indent = get_depth(max_lines)
   
    (@heap.length).times { output.push(' ' * INDENT_AMOUNT * max_indent) }

    @heap.each_with_index do |item, index|
      next if index.zero?  # @heap[0] appears to be a dummy node
      output[get_line(index)] = ' ' * INDENT_AMOUNT * get_depth(index) + 
item.to_s
    end

    # Okay, the tree nodes are now "drawn" into the output buffer.
    # Now draw connecting lines.  At each child node, draw ,- or `-
    # into their left margin.  Then bring down a column of |'s to
    # the parent node.
    #
    # Note that since we're drilling "down" from the parent nodes, we
    # only need to traverse the first half of the items in the tree.
    # The careful observer might note that in the sample tree, node 7
    # ("22") never gets traversed.  This is okay; it gets skipped
    # because we know it can't possibly have any children.
    (@heap.length / 2).times do |i|
      j = i+1 # The math is easier when done 1-based.

      # this whole mess could be refactored; these 2 blocks
      # differ only in start line, ,- vs `- text, and loop
      # direction.

      # connect node i to node i*2 (up from parent)
      indent = get_depth(j*2) * INDENT_AMOUNT
      stop_line = get_line(j)

      next if j*2 >= @heap.length

      start_line = get_line(j*2)
      output[start_line][indent-3..indent-2] = ',-'
      start_line += 1
      while start_line < stop_line
        output[start_line][indent-3] = '|'
        start_line += 1
      end

      # connect node i to node i*2+1 (down from parent)
      start_line = get_line(j*2+1)
      indent = get_depth(j*2+1) * INDENT_AMOUNT
      next if j*2+1 >= @heap.length

      output[start_line][indent-3..indent-2] = '`-'
      start_line -= 1
      while start_line > stop_line
        output[start_line][indent-3] = '|'
        start_line -= 1
      end
    end

    output.join("\n")
  end

Cheers!

-dB

-- 
David Brady
ruby-talk@shinybit.com
I'm having a really surreal day... OR AM I?