patternjavaMinor
Implementation of disjoint set in Java with linked-list
Viewed 0 times
withjavadisjointimplementationlistlinkedset
Problem
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
{
int rank;
DNode head;
DNode tail;
public DisJointSet(E data)
{
DNode node = new DNode<>(data);
head = node;
tail = node;
rank = 1;
node.represantive = this;
}
public void union(DNode x, DNode y)
{
DisJointSet xSet = findSet(x);
DisJointSet ySet = findSet(y);
if (xSet.rank>= ySet.rank)
append(xSet, ySet);
else
append(ySet, xSet);
}
public void append(DisJointSet first, DisJointSet 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 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 findSet (DNode x)
{
return x.represantive;
}
}
class DNode
{
DNode next;
DisJointSet represantive;
E data;
DNode(E val)
{
data = val;
}
}Solution
Nitpicks
Formatting and Style
OOP vs. Functional-Style
Your way of writing OOP is... strange.
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
Additionally your
- 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 != nullandxSet.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.Context
StackExchange Code Review Q#119771, answer score: 2
Revisions (0)
No revisions yet.