7
\$\begingroup\$

I have just wrote a linked list implementation of disjoint sets in Java for the Rainfall Problem. Can you take a look and tell me if there is something missing and also make a judgement in performance?

public class DisJointSet<E>
{
    int rank;
    DNode<E> head;
    DNode<E> tail;

    public DisJointSet(E data)
    {
        DNode<E> node = new DNode<>(data);
        head = node;
        tail = node;
        rank = 1;
        node.represantive = this;
    }

    public void union(DNode<E> x, DNode<E> y)
    {

        DisJointSet<E> xSet = findSet(x);
        DisJointSet<E> ySet = findSet(y);
        if (xSet.rank>= ySet.rank)
            append(xSet, ySet);
        else
            append(ySet, xSet);
    }

    public void append(DisJointSet<E> first, DisJointSet<E> second)
    {

        if (first.rank == 0 || second.rank == 0)
            throw new IllegalArgumentException();

        // Set the representative of each node in the second set to be
        // the first set.
        DNode<E> curr = second.head;

        while(curr!=null)
        {
            curr.represantive = first;
            curr = curr.next;
        }

        first.tail.next = second.head;
        first.tail = second.tail;
        first.rank += second.rank;

        // Invalidate the second set, just to be sure.
        second.head = null;
        second.tail = null;
        second.rank = 0;
    }

    public DisJointSet<E> findSet (DNode<E> x)
    {
        return x.represantive;
    }
}

class DNode<E>
{
    DNode<E> next;
    DisJointSet<E> represantive;
    E data;

    DNode(E val)
    {
        data = val;
    }
}
\$\endgroup\$
2
\$\begingroup\$

Nitpicks

  • Disjoint is a single word, your class should be named DisjointSet
  • The correct spelling for the "sink" is representative

Formatting and Style

  • It's generally recommended to always put braces around blocks in if-else constructs. Yes, even when they only throw an Exception.
  • Binary operators usually have a space on each side. (applies curr != null and xSet.rank >= ySet.rank)

OOP vs. Functional-Style

Your way of writing OOP is... strange. union, append and findSet are defined as instance methods, meaning they need to be called on a certain instance of DisjointSet, but they don't actually use the instance at all.

Overall these could all be completely extracted into a static utility class, and nothing much would change. I strongly advise you to actually do exactly that. It should clarify responsibilities and make the code clearer to follow.

Alternatively you could make these functions actually start working in an OOP way. If you do that I'd furthermore suggest to make DisjointSet something like an immutable class (see String or Path) that will create a new instance when you union or append another Set to it. In fact I recommend you do that, even when you don't rewrite the code into a more OOP fashion.

Additionally your DNode's data could (and should) be declared final to avoid modification.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.