dsets.h

/**********************************************************
 * dsets.h -- part of mp7
 *
 *  Allows us to create disjoint sets. We have up-trees stored as a vector of
 *  integers. It also uses path compression and union-by-size. Each place in the
 *  private vector represents a node. (Note that this means that the elements in
 *  our universe are indexed starting at 0). A nonnegative number is the index
 *  of the parent of the current node; a negative number in a root node is the
 *  negative of the set size.
 *
 *   Authors: Kevin Cathey and G. Carl Evans
 *     Date: 22/04/2007
 */

#ifndef dsets_H
#define dsets_H

#include <vector>

class DisjointSets
{
    public:
        DisjointSets();
        
        /*
         *  This function creates n unconnected root nodes at the end of the
         *  private vector.
         */
        void addelements(int n);
        
        /*
         *  Finds the set given by the integer.
         */
        int find(int a);
        
        /*
         *  Unions two sets, a and b
         */
        void setunion(int a, int b);
    
    private:
        /*
         *  This class is the node that is actual stored in the vector of nodes.
         */
        typedef struct _MPDisjointSetsNode
        {
            public:
                /*
                 *  Creates a node with no owner and size of 1
                 */
                _MPDisjointSetsNode():owner(-1),size(1) {};
                
                /*
                 *  States whether the receiver is bigger than the given node.
                 *  Ties are returned false. Think about why (hint, > != >=).
                 */
                bool isBiggerThanNode(_MPDisjointSetsNode &node)
                {
                    return (size > node.size);
                }
                
                /*
                 *  Tells us if the receiver is a root node. A root node is
                 *  determined by whether or not the owner is less than 0, or -1
                 *  in our case.
                 */
                bool isRoot()
                {
                    return (owner < 0);
                }
                
                /*
                 *  Member Variables. Owner is the node the node belongs too. If
                 *  it is -1, then we have a root. The size is the size of the
                 *  node. The size really only applies to the root node, since
                 *  that is where the size gets set by the DisjointSets class.
                 */
                int owner;
                int size;
        } MPDisjointSetsNode;

   std::vector<MPDisjointSetsNode> _nodes;
};

#endif