Class: Canon::TreeDiff::Core::Matching

Inherits:
Object
  • Object
show all
Defined in:
lib/canon/tree_diff/core/matching.rb

Overview

Matching stores and manages node pair matches

A matching is a set of pairs (n1, n2) where:

  1. One-to-one: Each node appears in at most one pair

  2. Prefix closure: If (n1, n2) matched, ancestors can match

Features:

  • Efficient lookup: O(1) for checking if node is matched

  • Validation: Ensures constraints are maintained

  • Iteration: Supports enumeration of all pairs

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ Matching

Initialize empty matching



20
21
22
23
24
 
# File 'lib/canon/tree_diff/core/matching.rb', line 20

def initialize
  @pairs = []
  @tree1_map = {} # node => matched_node
  @tree2_map = {} # node => matched_node
end

Instance Attribute Details

#pairs ⇒ Object (readonly)

Returns the value of attribute pairs.



17
18
19
 
# File 'lib/canon/tree_diff/core/matching.rb', line 17

def pairs
  @pairs
end

Instance Method Details

#add(node1, node2) ⇒ Boolean

Add a matched pair

Parameters:

Returns:

  • (Boolean) —

    true if added, false if violates constraints



31
32
33
34
35
36
37
38
39
 
# File 'lib/canon/tree_diff/core/matching.rb', line 31

def add(node1, node2) # rubocop:disable Naming/PredicateMethod
  return false unless valid_pair?(node1, node2)

  @pairs << [node1, node2]
  @tree1_map[node1] = node2
  @tree2_map[node2] = node1

  true
end

#each {|node1, node2| ... } ⇒ Object

Iterate over all pairs

Yields:

  • (node1, node2) 


121
122
123
 
# File 'lib/canon/tree_diff/core/matching.rb', line 121

def each(&block)
  @pairs.each(&block)
end

#empty? ⇒ Boolean

Check if matching is empty

Returns:

  • (Boolean) 


114
115
116
 
# File 'lib/canon/tree_diff/core/matching.rb', line 114

def empty?
  @pairs.empty?
end

#inspect ⇒ String

Detailed inspection

Returns:

  • (String) 


196
197
198
199
200
201
202
 
# File 'lib/canon/tree_diff/core/matching.rb', line 196

def inspect
  pairs_str = @pairs.map do |n1, n2|
    "(#{n1.label} ↔ #{n2.label})"
  end.join(", ")

  "#<Matching [#{pairs_str}]>"
end

#match_for1(node) ⇒ TreeNode?

Get the match for a node from tree 1

Parameters:

Returns:

  • (TreeNode, nil) —

    Matched node from tree 2, or nil



76
77
78
 
# File 'lib/canon/tree_diff/core/matching.rb', line 76

def match_for1(node)
  @tree1_map[node]
end

#match_for2(node) ⇒ TreeNode?

Get the match for a node from tree 2

Parameters:

Returns:

  • (TreeNode, nil) —

    Matched node from tree 1, or nil



84
85
86
 
# File 'lib/canon/tree_diff/core/matching.rb', line 84

def match_for2(node)
  @tree2_map[node]
end

#matched1?(node) ⇒ Boolean

Check if a node from tree 1 is matched

Parameters:

Returns:

  • (Boolean) 


60
61
62
 
# File 'lib/canon/tree_diff/core/matching.rb', line 60

def matched1?(node)
  @tree1_map.key?(node)
end

#matched2?(node) ⇒ Boolean

Check if a node from tree 2 is matched

Parameters:

Returns:

  • (Boolean) 


68
69
70
 
# File 'lib/canon/tree_diff/core/matching.rb', line 68

def matched2?(node)
  @tree2_map.key?(node)
end

#one_to_one? ⇒ Boolean

Check one-to-one constraint

Each node appears in at most one pair

Returns:

  • (Boolean) 


143
144
145
146
147
148
149
150
151
152
153
154
 
# File 'lib/canon/tree_diff/core/matching.rb', line 143

def one_to_one?
  # Check tree1 map has unique values
  tree1_values = @tree1_map.values
  return false unless tree1_values.size == tree1_values.uniq.size

  # Check tree2 map has unique values
  tree2_values = @tree2_map.values
  return false unless tree2_values.size == tree2_values.uniq.size

  # Check maps are consistent
  @tree1_map.all? { |n1, n2| @tree2_map[n2] == n1 }
end

#prefix_closure? ⇒ Boolean

Check prefix closure constraint

If (n1, n2) matched and ancestors (a1, a2) matched, then a1 is ancestor of n1 iff a2 is ancestor of n2

Returns:

  • (Boolean) 


162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
 
# File 'lib/canon/tree_diff/core/matching.rb', line 162

def prefix_closure?
  @pairs.each do |node1, node2|
    # Check each ancestor pair
    node1.ancestors.each_with_index do |anc1, idx|
      anc2 = node2.ancestors[idx]

      # If ancestor matched, must be to corresponding ancestor
      if matched1?(anc1)
        match = match_for1(anc1)
        return false unless match == anc2
      end
    end
  end

  true
end

#remove(node1, node2) ⇒ Boolean

Remove a matched pair

Parameters:

Returns:

  • (Boolean) —

    true if removed, false if not found



46
47
48
49
50
51
52
53
54
 
# File 'lib/canon/tree_diff/core/matching.rb', line 46

def remove(node1, node2) # rubocop:disable Naming/PredicateMethod
  removed = @pairs.delete([node1, node2])
  return false unless removed

  @tree1_map.delete(node1)
  @tree2_map.delete(node2)

  true
end

#size ⇒ Integer

Get number of matched pairs

Returns:

  • (Integer) 


107
108
109
 
# File 'lib/canon/tree_diff/core/matching.rb', line 107

def size
  @pairs.size
end

#to_a ⇒ Array<Array<TreeNode, TreeNode>>

Convert to array of pairs

Returns:



182
183
184
 
# File 'lib/canon/tree_diff/core/matching.rb', line 182

def to_a
  @pairs.dup
end

#to_s ⇒ String

String representation

Returns:

  • (String) 


189
190
191
 
# File 'lib/canon/tree_diff/core/matching.rb', line 189

def to_s
  "#<Matching #{size} pairs>"
end

#unmatched1(nodes) ⇒ Array<TreeNode>

Get all unmatched nodes from tree 1

Parameters:

  • nodes (Array<TreeNode>) —

    All nodes from tree 1

Returns:



92
93
94
 
# File 'lib/canon/tree_diff/core/matching.rb', line 92

def unmatched1(nodes)
  nodes.reject { |node| matched1?(node) }
end

#unmatched2(nodes) ⇒ Array<TreeNode>

Get all unmatched nodes from tree 2

Parameters:

  • nodes (Array<TreeNode>) —

    All nodes from tree 2

Returns:



100
101
102
 
# File 'lib/canon/tree_diff/core/matching.rb', line 100

def unmatched2(nodes)
  nodes.reject { |node| matched2?(node) }
end

#valid? ⇒ Boolean

Check if matching satisfies all constraints

Returns:

  • (Boolean) 


128
129
130
131
132
133
134
135
136
 
# File 'lib/canon/tree_diff/core/matching.rb', line 128

def valid?
  # Check one-to-one constraint
  return false unless one_to_one?

  # Check prefix closure constraint
  return false unless prefix_closure?

  true
end