visitor.rb

require 'stringio'

class Tree
  attr_accessor :value
  attr_reader :children
 
  def initialize(value)
    @value = value
    @children = []
  end
   
  def add(tree)
    @children << tree
  end
   
  def accept(visitor)
    visitor.visit_tree(self)
  end
end

class OakTree < Tree
end

class Branch
  attr_accessor :value
  attr_reader :children

  def initialize(value)
    @value = value
    @children = []
  end

  def accept(visitor)
    visitor.visit_branch(self)
  end

  def add(branch)
    raise unless branch.is_a? Branch
    @children << branch    
  end
end

class ThinBranch < Branch
  def add(branch)
    raise if branch.is_a? ThickBranch
    super
  end

  def accept(visitor)
    visitor.visit_thin_branch(self)
  end
end

class ThickBranch < Branch

end
 
class IndenterVisitor
  def initialize(stream)
    @stream = stream
    @indent = 0
  end
   
  def visit_tree(element)
    visit(element, "Tree")
  end

  def visit_branch(element)
    visit(element, "Branch")    
  end

  def visit_thin_branch(element)
    visit(element, "Thin Branch")    
  end
 
  def visit_thick_branch(element)
    raise "Not implemented"
  end

  private
  def visit(element, prefix)
    @stream.puts " " * @indent * 2 + "#{prefix}: #{element.value}"
    @indent += 1
    if element.respond_to? :children
      element.children.each {|c| c.accept(self) }
    end    
    @indent -= 1
  end
end
 
class IndenterOutsider
  def initialize(stream, tree)
    @stream = stream
    @tree = tree
    @indent = 0
  end
   
  def generate(target=@tree)
    target.class.ancestors.each do |kl|
      meth = "generate_#{kl.to_s.downcase}".to_sym
      if respond_to?(meth, true)
        return send(meth, target)
      end
    end
    raise "Error, don't know how to generate #{target}"
  end
   
  private
  def generate_tree(target)
    generate_template(target, "Tree")
  end

  def generate_thinbranch(target)
    generate_template(target, "Thin Branch")
  end

  def generate_branch(target)
    generate_template(target, "Branch")
  end

  def generate_template(element, prefix)
    @stream.puts " " * @indent * 2 + "#{prefix}: #{element.value}"
    @indent += 1
    if element.respond_to? :children
      element.children.each {|c| generate(c) }
    end    
    @indent -= 1
  end
end
 
t = Tree.new("hi")
t1 = ThickBranch.new("there")
t11 = ThinBranch.new("Steve")
t12 = ThinBranch.new("John")
t2 = ThickBranch.new("to")
t21 = ThinBranch.new("you")
t1.add(t11)
t1.add(t12)
t.add(t1)
t2.add(t21)
t.add(t2)

require 'benchmark'
times = 5000
Benchmark.bmbm do |b|
  b.report("Visitor") do
    times.times do
      tv = IndenterVisitor.new(StringIO.new)
      tv.visit_tree(t)
    end
  end

  b.report("Outsider") do
    times.times do
      tr = IndenterOutsider.new(StringIO.new, t)
      tr.generate
    end
  end
end

# results:
               user     system      total        real
Visitor    0.510000   0.040000   0.550000 (  0.561382)
Outsider   0.920000   0.200000   1.120000 (  1.145166)

# ruby 1.9.0
               user     system      total        real
Visitor    0.190000   0.000000   0.190000 (  0.214908)
Outsider   0.390000   0.010000   0.400000 (  0.430465)