Class: RubyCollections::UnionFind

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

Instance Method Summary collapse

Constructor Details

#initialize(arr) ⇒ UnionFind

Returns a new instance of UnionFind.



3
4
5
6
 
# File 'lib/ruby_collections/union_find.rb', line 3

def initialize(arr)
  @leadership_hash = {}; @count = {}; @orig_val = {}
  arr.each   {|elem| set_hash(elem, elem); set_size(elem, 0); @orig_val[elem.to_s] = elem}
end

Instance Method Details

#cluster(elem) ⇒ Object 



29
30
31
32
33
34
 
# File 'lib/ruby_collections/union_find.rb', line 29

def cluster(elem)
  leader = find(elem)
  cluster = []
  hash.keys.each {|key| cluster << @orig_val[key] if find(key) == leader}
  cluster
end

#find(elem) ⇒ Object 



8
9
10
11
 
# File 'lib/ruby_collections/union_find.rb', line 8

def find(elem)
  elem = get_hash(elem) while get_hash(elem) != elem
  return elem
end

#to_a ⇒ Object 



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

def to_a
  hash.keys.each do |key|
    leader = find(key)
    uf_hash[leader.to_s] = uf_hash.fetch(leader.to_s, []) << @orig_val[key]
  end
  uf_hash.values
end

#union(elem1, elem2) ⇒ Object 



13
14
15
16
17
18
19
 
# File 'lib/ruby_collections/union_find.rb', line 13

def union(elem1, elem2)
  leader1 = find(elem1)
  leader2 = find(elem2)
  unless leader1 == leader2
    size(leader1) > size(leader2) ? set_hash(leader2, leader1) : set_hash(leader1, leader2)
  end
end