Module: Ryac::UnionFind

Included in:
KeywordRenameMapping, MethodRenameMapping
Defined in:
sig/ryac/union_find.rbs,
lib/ryac/union_find.rb

Overview

Union-Find over arbitrary hashable keys; each includer picks its key type (both current includers use method_key).

Instance Method Summary collapse

Instance Method Details

#merge_groups(key1, key2) ⇒ void

This method returns an undefined value.

Parameters:

  • key1 (K)
  • key2 (K) 


15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
# File 'lib/ryac/union_find.rb', line 15

def merge_groups(key1, key2)
  root1 = uf_root(key1)
  root2 = uf_root(key2)
  return if root1 == root2

  if @rank[root1] < @rank[root2]
    @parent[root1] = root2
  elsif @rank[root1] > @rank[root2]
    @parent[root2] = root1
  else
    @parent[root2] = root1
    @rank[root1] += 1
  end
end

#uf_add(key) ⇒ Integer

Parameters:

  • key (K)

Returns:

  • (Integer) 


32
33
34
35
 
# File 'lib/ryac/union_find.rb', line 32

def uf_add(key)
  @parent[key] ||= key
  @rank[key] ||= 0
end

#uf_init ⇒ void

This method returns an undefined value.



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

def uf_init
  @parent = {}
  @rank = {}
end

#uf_remove(key) ⇒ void

This method returns an undefined value.

Parameters:

  • key (K) 


37
38
39
40
 
# File 'lib/ryac/union_find.rb', line 37

def uf_remove(key)
  @parent.delete(key)
  @rank.delete(key)
end

#uf_root(key) ⇒ K

Parameters:

  • key (K)

Returns:

  • (K) 


10
11
12
13
 
# File 'lib/ryac/union_find.rb', line 10

def uf_root(key)
  @parent[key] = uf_root(@parent[key]) if @parent[key] != key
  @parent[key]
end