class RSpec::Matchers::BuiltIn::ContainExactly::PairingsMaximizer

@private
that produces the fewest unmatched items.
looking for a solution which pairs all elements in both lists, or, barring that,
(or vice versa). From here, it performs a brute-force depth-first search,
What’s left is only the items which match multiple items from the other list
considered further.
* Any items which reciprocally match only each other are paired up and not
from these arrays.
The extra items and missing items in the matcher failure message are derived
placed into the ‘unmatched_expected_indexes` or `unmatched_actual_indexes` array.
* Any items which match none of the items in the other list are immediately
problem space:
force solution, but with a few heuristics applied to reduce the size of the
conversely, to minimize the number of unpaired items. It’s essentially a brute
This class is designed to maximize the number of actual/expected pairings – or,
compared to another expected element matcher, we need to consider every possible pairing.
an expected element which is a matcher that matches a superset of actual items
(/foo/ with “fool”), which would leave /fool/ and “food” unmatched. When we have
the original algorithm used by this matcher would pair the first elements it could
This should pass (because we can pair /fool/ with “fool” and /foo/ with “food”), but
expect([“fool”, “food”]).to contain_exactly(/foo/, /fool/)
much more complicated. Consider this expression:
Once we started supporting composing matchers, the algorithm for this matcher got

def apply_pairing_to(indeterminates, original_matches, other_list_index)

def apply_pairing_to(indeterminates, original_matches, other_list_index)
  indeterminates.inject({}) do |accum, index|
    accum[index] = original_matches[index] - [other_list_index]
    accum
  end
end

def best_solution_for_pairing(expected_index, actual_index)

def best_solution_for_pairing(expected_index, actual_index)
  modified_expecteds = apply_pairing_to(
    solution.indeterminate_expected_indexes,
    expected_to_actual_matched_indexes, actual_index)
  modified_expecteds.delete(expected_index)
  modified_actuals = apply_pairing_to(
    solution.indeterminate_actual_indexes,
    actual_to_expected_matched_indexes, expected_index)
  modified_actuals.delete(actual_index)
  solution + self.class.new(modified_expecteds, modified_actuals).find_best_solution
end

def categorize_indexes(indexes_to_categorize, other_indexes)

def categorize_indexes(indexes_to_categorize, other_indexes)
  unmatched     = []
  indeterminate = []
  indexes_to_categorize.each_pair do |index, matches|
    if matches.empty?
      unmatched << index
    elsif !reciprocal_single_match?(matches, index, other_indexes)
      indeterminate << index
    end
  end
  return unmatched, indeterminate
end

def find_best_solution

def find_best_solution
  return solution if solution.candidate?
  best_solution_so_far = NullSolution
  expected_index = solution.indeterminate_expected_indexes.first
  actuals = expected_to_actual_matched_indexes[expected_index]
  actuals.each do |actual_index|
    solution = best_solution_for_pairing(expected_index, actual_index)
    return solution if solution.ideal?
    best_solution_so_far = solution if best_solution_so_far.worse_than?(solution)
  end
  best_solution_so_far
end

def initialize(expected_to_actual_matched_indexes, actual_to_expected_matched_indexes)

def initialize(expected_to_actual_matched_indexes, actual_to_expected_matched_indexes)
  @expected_to_actual_matched_indexes = expected_to_actual_matched_indexes
  @actual_to_expected_matched_indexes = actual_to_expected_matched_indexes
  unmatched_expected_indexes, indeterminate_expected_indexes =
    categorize_indexes(expected_to_actual_matched_indexes, actual_to_expected_matched_indexes)
  unmatched_actual_indexes, indeterminate_actual_indexes =
    categorize_indexes(actual_to_expected_matched_indexes, expected_to_actual_matched_indexes)
  @solution = Solution.new(unmatched_expected_indexes,     unmatched_actual_indexes,
                           indeterminate_expected_indexes, indeterminate_actual_indexes)
end

def reciprocal_single_match?(matches, index, other_list)

def reciprocal_single_match?(matches, index, other_list)
  return false unless matches.one?
  other_list[matches.first] == [index]
end

Modules

Classes