module TDiff::Unordered

Calculates the differences between two trees, without respecting the order of children nodes.

Public Class Methods

included(base) click to toggle source

Includes {TDiff}.

# File lib/tdiff/unordered.rb, line 12
def self.included(base)
  base.send :include, TDiff
end

Public Instance Methods

tdiff_unordered(tree) { |'-', self| ... } click to toggle source

Finds the differences between `self` and another tree, not respecting the order of the nodes.

@param [#tdiff_each_child] tree

The other tree.

@yield [change, node]

The given block will be passed the added or removed nodes.

@yieldparam [' ', '+', '-'] change

The state-change of the node.

@yieldparam [Object] node

A node from one of the two trees.

@return [Enumerator]

If no block is given, an Enumerator object will be returned.

@since 0.2.0

# File lib/tdiff/unordered.rb, line 37
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

Protected Instance Methods

tdiff_recursive_unordered(tree) { |change, node| ... } click to toggle source

Recursively compares the differences between the children nodes, without respecting the order of the nodes.

@param [#tdiff_each_child] tree

The other tree.

@yield [change, node]

The given block will be passed the added or removed nodes.

@yieldparam [' ', '+', '-'] change

The state-change of the node.

@yieldparam [Object] node

A node from one of the two trees.

@since 0.3.2

# File lib/tdiff/unordered.rb, line 73
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