Class: Hashira::Duplication::UnionFind

Inherits:

Object

• Object
• Hashira::Duplication::UnionFind

Defined in:

lib/hashira/duplication/union_find.rb

Instance Method Summary

• #clusters ⇒ Object
• #initialize ⇒ UnionFind constructor

  A new instance of UnionFind.

• #root(node) ⇒ Object
• #union(left, right) ⇒ Object

Constructor Details

#initialize ⇒ UnionFind

Returns a new instance of UnionFind.

# File 'lib/hashira/duplication/union_find.rb', line 4

def initialize
  @parent = {}
end

Instance Method Details

#clusters ⇒ Object

# File 'lib/hashira/duplication/union_find.rb', line 10

def clusters = @parent.keys.group_by { root(it) }.values

#root(node) ⇒ Object

# File 'lib/hashira/duplication/union_find.rb', line 12

def root(node)
  @parent[node] = node unless @parent.key?(node)
  found = @parent[node]
  found == node ? node : (@parent[node] = root(found))
end

#union(left, right) ⇒ Object

# File 'lib/hashira/duplication/union_find.rb', line 8

def union(left, right) = @parent[root(left)] = root(right)