# Disjoint set implementation as linked list

I have just 'wrote' a linked list implementation of Disjoint Sets. This is the changed version of Bob Tian's implememnation. Can you take a look and tell me if there is something missing ? For instance memory leaks while destroying nodes. And please judge it also in performance matter.

I would like to change the long NodeAddress[9999] = {0}; to something better but: this implementation is used for Connected-component labeling so every time I examine the pixel that needs to be added to labels array I add it. But in the end I do not know how many of them will be there and I need some way to access them (in case i would need to use them later on - for instance union it with another label)

#include <iostream>

using namespace std;

int n=0;

class ListSet {
private:
struct Item;
struct node {
int val;
node *next;
Item *itemPtr;
};
struct Item {
node *hd, *tl;
};

public:
ListSet() { }
long makeset(int a);
long find (long a);
void Union (long s1, long s2);
};

long ListSet::makeset (int a) {
Item *newSet = new Item;
newSet->hd = new node;
newSet->tl = newSet->hd;
node *shd = newSet->hd;
shd->val = a;
shd->itemPtr = newSet;
shd->next = 0;
return (long) newSet;
}

long ListSet::find (long a) {
node *ptr = (node*)a;
return (long)(ptr->itemPtr);
}

void ListSet::Union (long s1, long s2) {
node *ptr1 = (node*)s1;
node *ptr2 = (node*)s2;

Item *set2 = ptr1->itemPtr;
node *cur = set2->hd;

Item *set1 = ptr2->itemPtr;

while (cur != 0) {
cur->itemPtr = set1;
cur = cur->next;
}
//join the tail of the set to head of the input set
(set1->tl)->next = set2->hd;
set1->tl = set2->tl;
delete set2;
}

int main () {

ListSet a;
long s1, s2, s3, s4;
s1 = a.makeset(13);
s2 = a.makeset(25);
s3 = a.makeset(45);
s4 = a.makeset(65);
cout<<s1<<' '<<s2<<' '<<s3<<' '<<s4<<endl;

}

• Your code does not show any nodes being deleted. Assuming that you do not want to leak them all like this, do you intend to delete them and then continue to have calls to find and union operate correctly on remaining nodes, or do you only need to delete all the nodes after the last call to find or union? – Paul Martel Jan 18 '12 at 2:25
• @PaulMartel I want to continue using them. This will be just a part of bigger function so I do not know if wrapping it up in a class is worth it but on the other hand I will have a memory leak anyway. Can you suggest a way how this can be implemented ? (code snippet) – Patryk Jan 18 '12 at 2:57

#include <assert.h> // for assert
#include <string.h> // for memset

#include <iostream>

using namespace std;


// OMIT these as not very useful. Anyway, don't needlessly expose globals.

long NodeAddress[9999] = {0};
int n=0;


/* I've kept the class names for now, for the sake of recognition, but they've each got different problems.

ListSet does a poor job of describing the class' purpose. Since its purpose is to generate, find, and merge disjoint sets, call it something like DisjointSetSource.

Item is too generic and not very descriptive of the class' function. It represents a disjoint set, but to reserve the name DisjointSet for its exported opaque equivalent, just call it Set, or since it's represented as a linked list of member nodes, maybe SetNodeList or SetMemberList.

node is also very generic, but it's a little more apt. Also, it's name should be capitalized by convention and for consistency. So, Node is OK, but better might be Member or since it's main features are to refer to its parent list and successor, call it ListMember. */

class ListSet {
private:
typedef int ValueType;
struct Item;


/* There's a non-trivial smattering of node and item processing cluttering up the ListMember methods. They really want to be full-fledged classes with a constructor, (possibly) destructor, and (possibly) mutators. Item needs write access to node::next and ListMember needs write access to itemPtr, so I'd keep the node members public. */

    struct node {
ValueType val;
node *next;
Item *itemPtr;


        node (const ValueType& a);
~node ();
};

struct Item {


        Item(node *shd) : hd(shd), tl(shd) {}
void append(const Item*);
// returns head node as "sign of life"
node* remove(node* old);
private:
node *hd, *tl;
};


/* Avoid exposing nodeAddress, especially as a global. It SHOULD use std::vec for dynamic growth or std::map if values are sparse. Wrap this in accessors to stay flexible, especially WRT ValueType, opening the door for (re)templatizing as in the originally posted code. */

private:

public:

void setNodeAddress(const ValueType& a, node* shd) {
}

}

// removeAll requires or maybe IS a third form of nodeAddress accessor


/* Why does a ListSet object ever need to be created? When the original implementation used the global NodeAddress as its state, all functions could be static and no ListSet instance ever created. This would also be true if NodeAddress was a static member.

Yet, it was easy enough to improve on the design by making nodeAddress a normal data member. This provides a useful purpose for multiple ListSet instances.
Each managing its own disjoint sets, completely independently. All the more reason to pull NodeAddress out of the API, where it is just noise. See main. */

    ListSet() {
// zero out nodeAddress in some type appropriate way
}

~ListSet() {
removeAll();
}


/* "long" is too general a type to use for "handles" like the return type, here. Better to make up a unique fictitious type: */

    class DisjointSet;

DisjointSet* exportSet(Item* result) { return (DisjointSet*) result; }
Item* importSet(DisjointSet* input) { return (Item*) input; }


/* Use camelCase or under_scoring to makemultiwordnamesreadable. */

    DisjointSet* makeSet(const ValueType& a);
DisjointSet* find (const ValueType& a);
void remove(const ValueType& a);
void removeAll();


// Use suffix word rather than breaking lowercase convention to get around reserved words

    void unionSets (const ValueType& a1, const ValueType& a2) {
DisjointSet* s1 = find(a1);
DisjointSet* s2 = find(a2);
if (s1 && s2) {
(void) unionSets(s1, s2);
}
// else error?
}

DisjointSet* unionSets (DisjointSet* s1, DisjointSet* s2);
};

ListSet::DisjointSet* ListSet::makeSet (const ValueType& a) {
node *shd = new node(a);
Item *newSet = new Item(shd);
shd->itemPtr = newSet;
return exportSet(newSet);
}

ListSet::DisjointSet* ListSet::find (const ValueType& a) {
if (ptr)
return exportSet(ptr->itemPtr);
// else error?
return 0;
}


/* This used to be needlessly confusing with lines like:

Item *set2 = ptr1->itemPtr;
Item *set1 = ptr2->itemPtr;


I'm really still not sure the revision, below maintains the original intent, because of the set1/set2 naming confusion, but it does what the old code did.

Aside from avoiding such confused naming, use of an Item method makes this code much easier to read. */

ListSet::DisjointSet* ListSet::unionSets (DisjointSet* s1, DisjointSet* s2) {
Item *set1 = importSet(s1);
Item *set2 = importSet(s2);

set2->append(set1);
delete set1;
}

void ListSet::Item::append (const Item* other) {
//join the tail of the set to head of the other set
tl->next = other->hd;
tl = other->tl;
for (node* cur = other->hd; cur; cur = cur->next) {
cur->itemPtr = this;
}
}

ListSet::node::node (const ValueType& a) : val(a), next(0), itemPtr(0)
{ }


/* Here's mutator code that allows values to be incrementally dropped as operations continue. Note that after "union(1,2); union(2,3); remove(2);", 1 and 3 are still considered to be in the same set. */

// Returns hd as a sign of life -- null if empty/dead.
ListSet::node* ListSet::Item::remove(node* old) {
if (old == hd) {
if (old == tl) {
assert(! old->next);
return 0;
}
assert(old->next);
hd = old->next;
} else {
node* prev;
for (prev = hd; prev->next != old; prev = prev->next) {
assert(prev->next);
;
}
if (old == tl) {
assert(! old->next);
//
tl = prev;
prev->next = 0;
} else {
assert(old->next);
prev->next = old->next;
}
}
return hd;
}

ListSet::node::~node() {
if (itemPtr) {
if (! itemPtr->remove(this)) {
// Don't leak an empty set.
delete itemPtr;
}
}
}

void ListSet::remove(const ValueType& a) {
if (ptr) {
delete ptr;
}
// else error?
}

void ListSet::removeAll() {
assert( 0 ); // TBD
// This just needs to iterate over nodeAddress
// and call delete on each remaining node*.
}


/* There's no reason to expose anything other than the original elements (raw numbers), the ListSet and the DisjointSets it returned. So don't clutter the interface with Item*s disguised as longs, node*s disguised (indistinguishably) as longs, or NodeAddress. A cleaner, safer API results:

int main () {

ListSet a;
ListSet::DisjointSet *s1, *s2, *s3, *s4;
s1 = a.makeSet(13);
s2 = a.makeSet(25);
s3 = a.makeSet(45);
s4 = a.makeSet(65);

/* If this really needs to work, either define a stream io operator
for our DisjointSet type or let it get dumped as a hex value. */
cout<<s1<<' '<<s2<<' '<<s3<<' '<<s4 <<endl;

cout<<"a.find(65): "<<a.find(65) <<endl;
cout<<"a.find(45): "<<a.find(45) <<endl;
cout<<"a.Union(65, 45) "<<endl;

// The next line is a safer way to express a.unionSets(s3, s4);
// which may crash if s3 or s4 had been previously merged/deleted,
// but it's also a little slower.
a.unionSets(65, 45);

cout<<"a.find(65): "<<a.find(65) <<endl;
cout<<"a.find(45): "<<a.find(45) <<endl;
}

• Thanks A LOT for your answer you have helped a lot but IMHO you are a bit mixing the names too much. Can you post a comment or edit your answer so that it is more clear in some places like e.g. I do not understand what DisjointSet serves for. – Patryk Jan 25 '12 at 16:17
• I have removed the top-level typedef ListSet::DisjointSet* DisjointSet; so that there is only one "definition" of DisjointSet, the one within ListSet. So now main has to explicitly use ListSet::DisjointSet * in its decl's -- not sure that's an improvement. Maybe typedef ListSet::DisjointSet* DisjointSetHandle; would be clearer? – Paul Martel Jan 25 '12 at 17:43
• The remaining DisjointSet is purposely not a true definition but just a declaration. It's intended as an opaque handle so callers can do useful things like s1 == s2, cout<<s1, a.unionSets(s1,s2) but not make mistakes like 3*s1+s2 which would be legal using long. DisjointSet* is (secretly) just Item*. But Items are a (hidden) implementation detail. In the real world, when I put ListSet in a header, I'd remove the nesting of Node and Item. That leaves a clean ListSet API passing DisjointSet*s and raw (int) values. Node and Item can then hide completely in ListSet.cpp. – Paul Martel Jan 25 '12 at 18:10

The first thing that meets my eye is all this C-style casting, and in particular you are casting long to pointers and back. Why is the code not typesafe? If you want a pointer use a pointer. If you want a number use a number.

Your node class. Well it's "struct" but that just means the members are all public. It doesn't mean you can't put the logic within the class itself - how they are created, how they manage their data, etc.

Actually there were other things that caught my eye first like using namespace std; Get rid of that.