Class Set

java.lang.Object
  Set

public class Set

extends java.lang.Object

This class is used for implementing and manipulating a tree representation of a generic set, which allows for efficient union and find-set operations. A set consists of a Set class instance and zero or more instances of Element class, one for each element that is a member of the set. The Set instance contains the set's size, and a reference to the set representative Element. It supports a union(s1, s2) method that performs the union of set s1 and s2 as follows. If the size of s1 (i.e., the number of elements in s1) is strictly smaller than the size of s2, then we make the root of the tree of s1 point to the root of the tree of s2; otherwise, we make the root of the tree of s2 point to the root of the tree of s1.

Constructor Summary

Set(Element e)
This is the class constructor.

Method Summary

Element	getReprElmnt() This method returns the set's representative Element, or null if the set is empty.
static Set	union(Set s1, Set s2) This method performs the union by size of sets s1, s2.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

Set

public Set(Element e)

This is the class constructor. It builds a set of a single Element, e, which, initially, is also the set's representative Element.

Parameters:

e - the set's single Element and representative.

Method Detail

getReprElmnt

public Element getReprElmnt()

This method returns the set's representative Element, or null if the set is empty.

Returns:

the set's representative Element

union

public static Set union(Set s1,
                        Set s2)

This method performs the union by size of sets s1, s2. In more detail, if the size of s1 is strictly smaller than the size of s2, then it makes the root of the tree of s1 point to the root of the tree of s2, and returns s2; otherwise, it make the root of the tree of s2 point to the root of the tree of s1, and returns s1.

Parameters:

s1 - the first set

s2 - the second set

Returns:

the union of s1 and s2