class RubyCollections::UnionFind

Public Class Methods

new(arr) click to toggle source
# 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

Public Instance Methods

cluster(elem) click to toggle source
# 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) click to toggle source
# 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() click to toggle source
# 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) click to toggle source
# 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

Private Instance Methods

get_hash(key) click to toggle source
# File lib/ruby_collections/union_find.rb, line 42
def get_hash(key)
  @leadership_hash[key.to_s]
end
hash() click to toggle source
# File lib/ruby_collections/union_find.rb, line 46
def hash
  @leadership_hash
end
set_hash(key, value) click to toggle source
# File lib/ruby_collections/union_find.rb, line 38
def set_hash(key, value)
  @leadership_hash[key.to_s] = value
end
set_size(elem, val) click to toggle source
# File lib/ruby_collections/union_find.rb, line 54
def set_size(elem, val)
  @count[elem.to_s] = val
end
size(elem) click to toggle source
# File lib/ruby_collections/union_find.rb, line 50
def size(elem)
  @count[elem.to_s]
end
uf_hash() click to toggle source
# File lib/ruby_collections/union_find.rb, line 58
def uf_hash
  @uf_hash ||= {}
end