# This is a disjoint set implementing union-find
# It can be used for generating a minimal spanning
# tree using Kruskal's algorithm.
# http://en.wikipedia.org/wiki/Kruskal's_algorithm

class DisjointSetNode
  attr_accessor :parent, :rank

  def initialize
    @parent = self
    @rank = 0
  end

  # An optimised union by rank. Attaches smaller tree to larger.
  def union(other)
    self_root = self.find
    other_root = other.find
    if self_root.rank > other_root.rank
      other_root.parent = self_root
    elsif self_root.rank < other_root.rank
      self_root.parent = other_root
    elsif self_root != other_root
      other_root.parent = self_root
      self_root.rank += 1
    end
  end

  def find
    if self.parent === self
      self
    else
      self.parent = self.parent.find
    end
  end

end   # class DisjointSetNode

require 'disjointsetnode'
require 'test/unit'
require 'test/unit/ui/console/testrunner'

    class DisjointSetTest < Test::Unit::TestCase
      N_Nodes = 1000

      def setup
        @nodes = Array.new
        (1..N_Nodes).each do |node|
        @nodes << DisjointSetNode.new
        end
      end

      # def teardown
      # end

      def test_creation
        @nodes.each do |node|
          assert !node.nil?, "A Node is nil!"
        end
      end

      def test_initial_values
        @nodes.each do |node|
          assert node.parent === node, "self #{node}, parent #{node.parent} not equal."
          assert node.rank == 0, " A node's rtank is not 0."
        end
      end

      def test_union
        # Join all nodes in sequence
        @nodes.each do |node|
          if !@lastnode.nil?
            node.union(@lastnode)
            node_f = node.find
            lnode_f = @lastnode.find
            assert node_f == lnode_f, "Join not completed: node_f: #{node_f}, lnode_f: #{lnode_f}"
          end
          @lastnode = node
        end
      end

      def test_random_union
        (1..N_Nodes-1).each do |n|
          node = @nodes[n]
          other = @nodes[rand(N_Nodes-1)]
          node.union(other)
          node_f = node.find
          onode_f = other.find
          assert node_f == onode_f, "Join not completed: node_f: #{node_f}, onode_f: #{onode_f}"
        end
      end
    end

# This runs the tests for ya! 
Test::Unit::UI::Console::TestRunner.run(DisjointSetTest)