module TDiff

def tdiff(tree,&block)
  return enum_for(:tdiff,tree) unless block
  # check if the nodes differ
  unless tdiff_equal(self,tree)
    yield '-', self
    yield '+', tree
    return self
  end
  c = Hash.new { |hash,key| hash[key] = Hash.new(0) }
  x = enum_for(:tdiff_each_child,self)
  y = enum_for(:tdiff_each_child,tree)
  x.each_with_index do |xi,i|
    y.each_with_index do |yj,j|
      c[i][j] = if tdiff_equal(xi,yj)
                  c[i-1][j-1] + 1
                else
                  if c[i][j-1] > c[i-1][j]
                    c[i][j-1]
                  else
                    c[i-1][j]
                  end
                end
    end
  end
  unchanged = []
  changes = []
  x_backtrack = x.each_with_index.reverse_each
  y_backtrack = y.each_with_index.reverse_each
  next_child = lambda { |children|
    begin
      children.next
    rescue StopIteration
      # end of iteration, return a -1 index
      [nil, -1]
    end
  }
  xi, i = next_child[x_backtrack]
  yj, j = next_child[y_backtrack]
  until (i == -1 && j == -1)
    if (i != -1 && j != -1 && tdiff_equal(xi,yj))
      changes.unshift [' ', xi]
      unchanged.unshift [xi, yj]
      xi, i = next_child[x_backtrack]
      yj, j = next_child[y_backtrack]
    else
      if (j >= 0 && (i == -1 || c[i][j-1] >= c[i-1][j]))
        changes.unshift ['+', yj]
        yj, j = next_child[y_backtrack]
      elsif (i >= 0 && (j == -1 || c[i][j-1] < c[i-1][j]))
        changes.unshift ['-', xi]
        xi, i = next_child[x_backtrack]
      end
    end
  end
  # explicitly discard the c matrix
  c = nil
  # sequentially iterate over the changed nodes
  changes.each(&block)
  changes = nil
  # recurse down through unchanged nodes
  unchanged.each { |x,y| x.tdiff(y,&block) }
  unchanged = nil
  return self
end

def tdiff_each_child(node,&block)
  node.each(&block) if node.kind_of?(Enumerable)
end

def tdiff_equal(original_node,new_node)
  original_node == new_node
end