Class: GroupByMatchType::UnionFind

Inherits:
Object
  • Object
show all
Defined in:
lib/group_by_match_type/union_find.rb

Instance Method Summary collapse

Constructor Details

#initialize ⇒ UnionFind

Returns a new instance of UnionFind.



5
6
7
 
# File 'lib/group_by_match_type/union_find.rb', line 5

def initialize
  @parent = {}
end

Instance Method Details

#find(item) ⇒ Object 



9
10
11
12
 
# File 'lib/group_by_match_type/union_find.rb', line 9

def find(item)
  @parent[item] = find(@parent[item]) if @parent[item] && @parent[item] != item
  @parent[item] ||= item
end

#find_or_create(items) ⇒ Object 



20
21
22
23
24
25
26
27
28
 
# File 'lib/group_by_match_type/union_find.rb', line 20

def find_or_create(items)
  return nil if items.empty?

  items.map!(&:to_s)
  roots = items.map { |item| find(item) }
  main_root = roots.first
  roots[1..].each { |root| union(main_root, root) }
  main_root
end

#union(source_item, target_item) ⇒ Object 



14
15
16
17
18
 
# File 'lib/group_by_match_type/union_find.rb', line 14

def union(source_item, target_item)
  source_root = find(source_item)
  target_root = find(target_item)
  @parent[source_root] = target_root unless source_root == target_root
end