same_fringe.rb

module Util
  extend self

  # Is there a standard way to do this?
  def yield_or_return(object, &block)
    block_given? ? block.call(object) : object
  end
end

class Tree < Struct.new(:left, :right)
  def leaves(&block)
    [ left, right ].inject([ ]) do |memo, child|
      memo +=
        (child.is_a?(Tree) && child.leaves(&block)) ||
        [ Util.yield_or_return(child, &block) ]
    end
  end
end

# Minimal tree?
class Node
  def leaves(&block)
    [ Util.yield_or_return(self, &block) ]
  end
end

n = Node.new
n.leaves { |leaf| { leaf.class => leaf } } # => [{Node=>#<Node:0x000001009148a0>}]

t = Tree.new(:a, Node.new )
t.leaves { |leaf| { leaf.class => leaf } } # => [{Symbol=>:a}, {Node=>#<Node:0x00000100909380>}]

module SameFringe
  extend self

  # Should have a better name.
  class UnequalFringe < StandardError; end

  # Symbols polute (and might be poluted by) the global variable space.
  # Using module as constant instead.
  # Should perhaps have a less political name.
  module AgentOrangeWasHere; end

  def compare(*trees)
    compare!(*trees)
  rescue UnequalFringe
    false
  end

  def compare!(*trees)
    fibers = trees.map { |tree| tree_fiber(tree) }

    loop do
      leaves =
        fibers.map do |fiber|
          fiber.resume
        end

      case
      when leaves.all? { |leaf| leaf == AgentOrangeWasHere }
        return true
      when leaves.uniq.size != 1
        raise UnequalFringe.new("Not same fringe #{leaves.inspect}")
      end
    end
  end

  # Should probably be private.
  def tree_fiber(tree)
    Fiber.new do
      tree.leaves { |leaf| Fiber.yield leaf }
      AgentOrangeWasHere
    end
  end
end

# Should use inline test/spec code instead of trace printing.

t = Tree.new(Tree.new(Tree.new(:a, :b), :c), Tree.new(:d, :e))
# Simple
t.leaves # => [:a, :b, :c, :d, :e]
# Leaf values can be Arrays. Lesson learned: Array#flatten is considered harmful
t.leaves { |leaf| [ leaf, leaf ] } # => [[:a, :a], [:b, :b], [:c, :c], [:d, :d], [:e, :e]]

f = SameFringe.tree_fiber(t)
# First all the leaves.
# When out of leaves we get to see that the agent was there.
# Then the fiber is dead.
7.times do
  f.resume rescue $! # => :a, :b, :c, :d, :e, SameFringe::AgentOrangeWasHere, #<FiberError: dead fiber called>
end

# The Hundred Acre Wood
ta1 = Tree.new(Tree.new(Tree.new(:a,          :b),         :c),  Tree.new(:d,    :e))
ta2 = Tree.new(Tree.new(         :a, Tree.new(:b, Tree.new(:c,            :d))), :e)
ta3 = Tree.new(Tree.new(         :a, Tree.new(:b,          :c)), Tree.new(:d,    :e))

# Fringe too short
tb1 = Tree.new(Tree.new(         :a, Tree.new(:b,          :c)),          :d)
# Different fringe
tc1 = Tree.new(Tree.new(         :a, Tree.new(:w00t,       :c)), Tree.new(:d,    :e))

# Positive
SameFringe.compare(ta1, ta2, ta3) # => true

# Negative
SameFringe.compare(ta1, tb1) # => false

# With a bang!
SameFringe.compare!(ta1, tb1) rescue $! # => #<SameFringe::UnequalFringe: Not same fringe [:e, SameFringe::AgentOrangeWasHere]>
SameFringe.compare!(ta1, tc1) rescue $! # => #<SameFringe::UnequalFringe: Not same fringe [:b, :w00t]>
SameFringe.compare!(tb1, tc1) rescue $! # => #<SameFringe::UnequalFringe: Not same fringe [:b, :w00t]>