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