• Adnan (156/156) Dec 07 2018 Hello. Is code-review requests welcome in this forum? If so I

Adnan <contact.adnan.02 protonmail.com> writes:

Hello. Is code-review requests welcome in this forum? If so I 
would like some criticisms and feedback for my disjoint sets 
implementation. The code is as follows:

module dsets;

/// dsets is an implementation of disjoint sets. It is implemented
/// with a simple class. To construct it, you provide the maximum 
node
/// number.
/// Limitation: CANNOT DISCONNECT TWO NODES

/// If the array is big enough, opt for parallel operations if 
possible
immutable ulong minimumParallelArrayLength = 10_000;

public class DSets
{
private:
     ulong[] ids, heights;

     bool isRoot(const ulong n) const
     {
         return ids[n] == n;
     }

public:
     /// A `DSets(10)` would create a disjoint set of 0 to 10
     /// inclusive.
     this(in ulong maxN)
     {
         ids.reserve(maxN + 1);
         heights.reserve(maxN + 1);

         foreach (n; 0 .. maxN + 1)
         {
             ids ~= n;
             heights ~= 0;
         }
     }

     /// Returns the root id of a given node
     ulong getRoot(in ulong n) const
     {
         ulong result = n;
         while (ids[result] != result)
             result = ids[ids[result]]; // path compression
         return result;
     }

     /// Connect two nodes. Does not check membership so may throw
     /// errors
     void connect(in ulong n, in ulong m)
     {
         auto nRoot = getRoot(n), mRoot = getRoot(m);
         if (nRoot != mRoot)
         {
             if (heights[nRoot] >= heights[mRoot])
             {
                 ids[mRoot] = ids[nRoot];
                 heights[nRoot] += heights[mRoot];
             }
             else
             {
                 ids[nRoot] = ids[mRoot];
                 heights[mRoot] += heights[nRoot];
             }
         }
     }

     /// Check if two given nodes are connected.
     bool connected(in ulong n, in ulong m) const
     {
         return getRoot(n) == getRoot(m);
     }

     /// Returns the number of nodes in the set
     ulong length() const  safe
     {
         return ids.length;
     }

     /// Add a node
     void grow(in ulong nodes = 0)
     {
         auto toAdd = ids[$ - 1];
         foreach (_; 0 .. nodes + 1)
         {
             ids ~= toAdd++;
             heights ~= 0;
         }
     }

     /// Get an array of roots
     ulong[] getRoots() const
     {
         if (ids.length == 0)
             return [];

         // D does not have a standard hash-set. The
         // workaround is to use a hash-table
         bool[ulong] roots;

         // premature optimization, if the array is not huge,
         // do not opt for multithreaded operation
         if (ids.length < 10_000)
         {
             foreach (i, id; ids)
                 if (ids[i] == i)
                     if (!(i in roots))
                         roots[i] = true;
         }
         else
         {
             import std.parallelism : parallel;

             foreach (i, id; ids.parallel())
                 if (ids[i] == i)
                     if (!(i in roots))
                         roots[i] = true;
         }
         return roots.keys;
     }

     /// Returns all the nodes connected to the given node
     ulong[] getLinkedNodes(in ulong node) const
     {
         // premature optimization, if the array is not huge,
         // do not opt for multithreaded operation
         ulong[] nodes;
         if (ids.length < 10_000)
         {
             foreach (i, _; ids)
                 if (this.connected(node, i))
                     nodes ~= i;
         }
         else
         {
             import std.parallelism : parallel;

             foreach (i, _; ids.parallel())
                 if (this.connected(node, i))
                     nodes ~= i;
         }
         return nodes;
     }
}

unittest
{
     import std.stdio;

     writefln("Testing %s...", __FILE__);
     scope (success)
         writeln("Success");

     auto forrest = new DSets(9);

     forrest.connect(9, 3);
     forrest.connect(1, 3);
     forrest.connect(9, 0);
     forrest.connect(7, 5);
     forrest.connect(6, 4);
     assert(forrest.connected(1, 0));
     assert(forrest.connected(3, 0));
     assert(!forrest.connected(5, 4));

     foreach (root; forrest.getRoots())
         writeln(root, " ==> ", forrest.getLinkedNodes(root));
}


outupt:

$ dub test -q
Testing source/dsets.d...
6 ==> [4, 6]
7 ==> [5, 7]
2 ==> [2]
1 ==> [0, 1, 3, 9]
8 ==> [8]
Success