Need a unique gift idea?
A Pastebin account makes a great Christmas gift
SHARE
TWEET

Untitled

a guest Dec 6th, 2018 66 Never
Upgrade to PRO!
ENDING IN00days00hours00mins00secs
 
  1. module dsets;
  2.  
  3. /// dsets is an implementation of disjoint sets. It is implemented
  4. /// with a simple class. To construct it, you provide the maximum node
  5. /// number.
  6. public class DSets
  7. {
  8. private:
  9.     ulong[] ids, heights;
  10. public:
  11.     /// A `DSets(10)` would create a disjoint set of 0 to 10
  12.     /// inclusive.
  13.     this(ulong maxN)
  14.     {
  15.         ids.reserve(maxN + 1);
  16.         heights.reserve(maxN + 1);
  17.  
  18.         foreach (n; 0 .. maxN + 1)
  19.         {
  20.             ids ~= n;
  21.             heights ~= 0;
  22.         }
  23.     }
  24.  
  25.     /// Returns the root id of a given node
  26.     ulong getRoot(ulong n) const
  27.     {
  28.         ulong result = n;
  29.         while (ids[result] != result)
  30.             result = ids[result];
  31.         return result;
  32.     }
  33.  
  34.     /// Connect two nodes. Does not check membership so may throw
  35.     /// errors
  36.     void connect(ulong n, ulong m)
  37.     {
  38.         auto nRoot = getRoot(n), mRoot = getRoot(m);
  39.         if (nRoot != mRoot)
  40.         {
  41.             if (heights[nRoot] >= heights[mRoot])
  42.             {
  43.                 ids[mRoot] = ids[nRoot];
  44.                 heights[nRoot] += heights[mRoot];
  45.             }
  46.             else
  47.             {
  48.                 ids[nRoot] = ids[mRoot];
  49.                 heights[mRoot] += heights[nRoot];
  50.             }
  51.         }
  52.     }
  53.  
  54.     /// Check if two given nodes are connected.
  55.     bool connected(ulong n, ulong m) const
  56.     {
  57.         return getRoot(n) == getRoot(m);
  58.     }
  59.  
  60.     ulong length() const @safe
  61.     {
  62.         return ids.length;
  63.     }
  64.  
  65.     // TODO: implement disconnectNode, toArray
  66.  
  67.     /// Add a node
  68.     void grow(ulong nodes = 0)
  69.     {
  70.         auto toAdd = ids[$ - 1];
  71.         foreach (_; 0 .. nodes + 1)
  72.         {
  73.             ids ~= toAdd++;
  74.             heights ~= 0;
  75.         }
  76.     }
  77.  
  78. }
  79.  
  80. unittest
  81. {
  82.     auto forrest = new DSets(9);
  83.  
  84.     forrest.connect(9, 3);
  85.     forrest.connect(1, 3);
  86.     forrest.connect(9, 0);
  87.     forrest.connect(7, 5);
  88.     forrest.connect(6, 4);
  89.     assert(forrest.connected(1, 0));
  90.     assert(forrest.connected(3, 0));
  91.     assert(!forrest.connected(5, 4));
  92. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top