module TDiff::Unordered

def self.included(base)
  base.send :include, TDiff
end

def tdiff_recursive_unordered(tree,&block)
  x = enum_for(:tdiff_each_child,self)
  y = enum_for(:tdiff_each_child,tree)
  unchanged = {}
  changes = []
  x.each_with_index do |xi,i|
    y.each_with_index do |yj,j|
      if (!unchanged.has_value?(yj) && xi.tdiff_equal(yj))
        unchanged[xi] = yj
        changes << [i, ' ', xi]
        break
      end
    end
    unless unchanged.has_key?(xi)
      changes << [i, '-', xi]
    end
  end
  y.each_with_index do |yj,j|
    unless unchanged.has_value?(yj)
      changes << [j, '+', yj]
    end
  end
  # order the changes by index to match the behavior of `tdiff`
  changes.sort_by { |change| change[0] }.each do |index,change,node|
    yield change, node
  end
  # explicitly release the changes variable
  changes = nil
  # recurse down the unchanged nodes
  unchanged.each do |xi,yj|
    xi.tdiff_recursive_unordered(yj,&block)
  end
  unchanged = nil
end

def tdiff_unordered(tree,&block)
  return enum_for(:tdiff_unordered,tree) unless block
  # check if the nodes differ
  unless tdiff_equal(tree)
    yield '-', self
    yield '+', tree
    return self
  end
  yield ' ', self
  tdiff_recursive_unordered(tree,&block)
  return self
end