From: "Brian Schröder" <ruby.brian@...>
Date: 2005-07-25T21:34:37+09:00
Subject: Re: [QUIZ] Drawing Trees (#40)

Hello Everybody,

so I finally got my internet access again after having struggled with
a big german internet provider for nearly two months and first thing I
did was to complete the ruby quiz of the week.

I decided to fit the binary tree into a very strict mask, I'm not
using information about the width of the subtrees to allow for better
packing, for this kind of things I prefer outputting dot code and
piping it into doc to get a nicely layouted tree in postscript format.
But this was not asked here, so following is my solution.

  def to_s(  )
    # We have log_2(n) levels
    #
    # Level i includes at most 2**i nodes when indexed starting from zero
    # That means last level needs the space for at most (2**(ceil(log_2(n)))) 
    #
    # Basic implementation: Reserve the space and fill it

    # Some constants for the ascii art
    short_arm_left = '/'
    short_arm_right = '\'

    arm_left_start = "'"
    arm_left_end = "."

    arm_right_start = "`"
    arm_right_end = "."

    arm_line = '-'

    join_string = ' '

    # Constants for position calculation
    levels = size.log2.ceil

    max_node_width = @heap[1..-1].map{ | node | node.to_s.length }.max
    max_line_width = 2**(levels-1) * max_node_width +
(2**(levels-1)-1) * join_string.length

    (0...levels).inject([]) { | result, level |
      level_node_width = max_line_width / 2**level

      # Draw the arms leading to the nodes on this level
      if level > 0
        result <<
        Array.new(2**level) { | j |
          if @heap[2**level+j]          # Only draw an arm, if there is a node
            if level_node_width < 5 # Draw short arm for short distances
              (j.even? ? short_arm_left :
short_arm_right).center(level_node_width)
            else                    # Draw long arm for long distances
              if j.even?
                (arm_left_end    + arm_line * (level_node_width / 2 -
1) + arm_left_start).rjust(level_node_width)
              else
                (arm_right_start + arm_line * (level_node_width / 2 -
1) + arm_right_end ).ljust(level_node_width)
              end
            end
          else
            ' ' * level_node_width
          end
        }.join(join_string)#.center(max_line_width)
      end

      # Draw the node on this level
      result << @heap[2**level...2**(level+1)].map { | node |
node.to_s.center(level_node_width)
}.join(join_string)#.center(max_line_width)
    }.join("\n")
  end

I'm drawing each level at a time filling the raster that is given by
the number of nodes at this level. Extra sugar is drawing of different
kinds of arms depending on how much space the arm has to span. If it
is a long distance, I draw a real arm, for short distances I only use
a slash or backslash. This gives quite good results in my opinion.

best regards,

Brian

PS: Can somebody reverse engineer the sentence that lead to the word
heap? I'd be interested in how many insertion orders lead to this same
heap.

Example output:

Start
          12           
     .----' `----.     
    20          15     
  .-' `-.     .-' `-.  
 29    23    17    22  
/    /    /          
35 40 26 51 19

Insert 13
          12           
     .----' `----.     
    20          13     
  .-' `-.     .-' `-.  
 29    23    15    22  
/    /    /         
35 40 26 51 19 17

Pop minimum
          13           
     .----' `----.     
    20          15     
  .-' `-.     .-' `-.  
 29    23    17    22  
/    /    /          
35 40 26 51 19

Word heap
                            another                            
               .--------------' `--------------.               
              are                            data              
       .------' `------.               .------' `------.       
    random           heap             of             kind      
   .--' `--.       .--' `--.       .--' `--.       .--'        
 this     the    words    on      to     some    test  

-- 
http://ruby.brian-schroeder.de/

Stringed instrument chords: http://chordlist.brian-schroeder.de/