// ***********************************************************
// *                                                         *
// *  nodedisjoint.C                                         *
// *                                                         *
// *  Implementation for a disjoint set class                *
// *                                                         *
// *  Written 30 October 1998 by Jason Zych                  *
// *  Update  07 April 1999 by David Bunde                   *
// *                  added path compression                 *
// *						             *
// *  Update  14 April 1999 by Mariusz Zaczek		     *
// *            - added Undo() - this required modifying     *
// *              the Union() and PFind() function.          *
// *                                                         *
// ***********************************************************

#include "nodedisjoint.h"

// DisjointSets
//    - default constructor
//    - initializes object to be an empty universe
template <class Etype>
DisjointSets<Etype>::DisjointSets()
{
   keyLookup = new SetLookup<UpTreeNode<Etype>*>(); 
   orderList = new List<UpTreeNode<Etype>*>(); 
}

// DisjointSets
//    - copy constructor
//    - parameters : origVal - previously allocated DisjointSets object
//    - initializes object to be a copy of origVal
template <class Etype>
DisjointSets<Etype>::DisjointSets(const DisjointSets<Etype>& origVal)
{
   Copy(origVal);  
}

// DisjointSets
//    - destructor
template <class Etype>
DisjointSets<Etype>::~DisjointSets()
{
   Clear(); 
}

// operator=
//    - parameters : origVal - previously allocated DisjointSets object
//    - return value : reference to this DisjointSets object
//    - sets this object to be a copy of origVal
template <class Etype>
DisjointSets<Etype>& 
DisjointSets<Etype>::operator=(const DisjointSets<Etype>& origVal)
{
   if (this != &origVal)
   {
      Clear(); 
      Copy(origVal); 
   }
   return *this; 
}

// MakeSet
//    - parameters : theKey - the key for a new set element
//                 : theInfo - the info record for a new set element
//    - add a new set to the universe, consisting of one element
//         that has the parameter values as its values
template <class Etype>
void DisjointSets<Etype>::MakeSet(int theKey, Etype theInfo)
{
   UpTreeNode<Etype>* uptr = new UpTreeNode<Etype>(); 
   uptr->key = theKey; 
   uptr->info = theInfo; 
   keyLookup->Insert(theKey, uptr);
   orderList->Tail(); 
   orderList->InsertAfter(uptr); 
}

// Union
//    - parameters : key1 - key of first element involved in union
//                 : key2 - key of second element involved in union
//    - return value : boolean integer
//    - attempts to union the set that contains key1 and the set
//         that contains key2. If it turns out that there is either
//         no node with key1 as a key, or else no node with key2 as
//         a key, then return 0. Otherwise, perform the union if
//         the two elements are in different sets, do nothing if
//         the two elements are in the same set, and return 1 in
//         either case.
template <class Etype>
int DisjointSets<Etype>::Union(int key1, int key2)
{
   List<Node<Etype> *> *MyList = new List<Node<Etype> *>;
    
   UpTreeNode<Etype> *uptr1, *uptr2; 

   if (keyLookup->Find(key1))
      uptr1 = keyLookup->Retrieve(); 
   else
      return 0; 
   if (keyLookup->Find(key2))
      uptr2 = keyLookup->Retrieve(); 
   else
      return 0; 

   // Push an empty list onto the stack
   UndoStack.Push(MyList);

   // Define two new _Node_ variables to store
   //   the node parameters.
   Node<Etype> *MyNode1 = new Node<Etype>;
   Node<Etype> *MyNode2 = new Node<Etype>;

   // Initialize the _Node_ variable with 
   //   the origNode & parentNode pointers,
   //   as well as the node counts and method.
   MyNode1 -> origNode = uptr1;
   MyNode2 -> origNode = uptr2;

   MyNode1 -> parentNode = uptr1 -> ptr;
   MyNode2 -> parentNode = uptr2 -> ptr;

   MyNode1 -> count = uptr1 -> count;
   MyNode2 -> count = uptr2 -> count;

   MyNode1 -> method = 0;
   MyNode2 -> method = 0;

   uptr1 = PFind(uptr1);
   uptr2 = PFind(uptr2);
 
   if (uptr1->count >= uptr2->count)
   {
      uptr1->count += uptr2->count; 
      uptr2->ptr = uptr1; 

     // Insert the _Node_ in the front of the list
     //    currently on the Top of the stack.
     ( UndoStack.Top() ) -> InsertBefore(MyNode2);
   }
   else
   {
      uptr2->count += uptr1->count; 
      uptr1->ptr = uptr2; 
     
     // Insert the _Node_ in the front of the list
     //    currently on the Top of the stack.
     ( UndoStack.Top() ) -> InsertBefore(MyNode1);
   }

   return 1; 
}

// Find
//    - parameters : theKey - the key of the node we want
//    - return value : integer element key
//    - finds what set the element with key theKey is a member
//         of, and returns the key of the representative element
//         of that set. If the key is not found, return 0. (Usage
//         of this class requires that 0 is not an element key.)
template <class Etype>
int DisjointSets<Etype>::Find(int theKey) 
{
   UpTreeNode<Etype>* uptr1;		//pointer to initial node

   if (keyLookup->Find(theKey))
      uptr1 = keyLookup->Retrieve(); 
   else
      return 0; 
   
   uptr1 = PFind(uptr1);

   return uptr1->key; 
}

// Lookup
//    - parameters : theKey - key of the node we want
//                 : result - reference where we will hold the
//                      info record of the node we want
//    - return value: boolean integer
//    - find node with given key. If such a node exists, store its
//         info record in "result" and return 1. Otherwise, return 0.
template <class Etype>
int DisjointSets<Etype>::Lookup(int theKey, Etype& result) 
{
   if (keyLookup->Find(theKey))
   {
      result = keyLookup->Retrieve()->info; 
      return 1; 
   }
   else
      return 0; 
}

//PFind
//   - parameters: start - pointer to node
//   - returns a pointer to the root of the uptree containing start
template<class Etype>
UpTreeNode<Etype>* DisjointSets<Etype>::PFind(UpTreeNode<Etype>* start)
{
   UpTreeNode<Etype>* temp;		//used during path compression
   UpTreeNode<Etype>* root;		//pointer to the root of uptree
  
   root = start;
   while (root->ptr != NULL)		//find the root of the uptree
      root=root->ptr;

   while(start != root)			//do path compression
   {
     // Make a new _Node_
     Node<Etype> *MyNode = new Node<Etype>;
  
     // For every node traversed assign the node pointers to the
     //   original and parent nodes and set the "method" to 1 (1=Find)
     MyNode -> origNode = start;
     MyNode -> parentNode = start->ptr;
     MyNode -> method = 1;

     temp = start -> ptr;	//get pointer to current node's parent
     start -> ptr = root;	//set current node's parent to root
     start = temp;		//go to node's original parent
 
     // Insert the _Node_ in the front of the list of the 
     //    current Top element of the stack.
     ( UndoStack.Top() ) -> InsertBefore(MyNode);
   }
  return root;
}



// Undo
//    - parameters : none
//    - return value: integer, 0 if Undo is unsuccessful
//                             1 if Undo is successful
//    - Reverses the effect of the last effective call to Union.
//       ... it will separate the combined sets made by Union and
//           will also reverse any path compressions.
template<class Etype>
int DisjointSets<Etype>::Undo()
{
  // Check this code for exception errors...in particular
  //   any errors resulting from a Pop() or Top() of an
  //   empty stack - replaces using a Is_Empty() function.
  try 
  { 
    // Create a list and assign the Popped element from
    //   the UndoStack to it.
    List<Node<Etype> *> *theList = UndoStack.Pop();

    // Move to the head of the list 
    theList -> Head();
 
    // While the list is not empty begin retrieving elements
    //   from the front of the list. 
    while (theList -> Length() != 0)
    {         
      Node<Etype> *MyNode = theList -> Retrieve();

      // Remove an element from the front of the list.
      theList -> Remove();
      
      // If the removed element was placed in the Listas a result
      //    of a Union operation then update that node's parent's
      //    count (# of nodes) to be equal to the old value stored.
      if (MyNode -> method == 0)
         MyNode -> origNode -> ptr -> count = MyNode -> count;

      // Update the nodes parent pointer to be the old 
      //    pointer - i.e. before a Union or Find was performed.
      MyNode -> origNode -> ptr = MyNode -> parentNode;

    }
   return 1;
  }
  catch(StackError mess)     // Catch the exection.
  {
    return 0;    
  }
}



// Copy
//    - parameters : origVal - previously allocated DisjointSets object
//    - copies origVal into this object
template <class Etype>
void DisjointSets<Etype>::Copy(const DisjointSets& origVal)
{
   keyLookup = new SetLookup<UpTreeNode<Etype>*>();
   orderList = new List<UpTreeNode<Etype>*>();

   ListIterator<UpTreeNode<Etype>*> iterator1(*(origVal.orderList));
   while (!iterator1.AtEnd())
   {
      MakeSet(iterator1.Retrieve()->key, iterator1.Retrieve()->info);
      iterator1.Forward();
   }

   orderList->Head();
   ListIterator<UpTreeNode<Etype>*> iterator2(*(origVal.orderList));
   while (!iterator2.AtEnd())
   {
      if (iterator2.Retrieve()->ptr == NULL)
         orderList->Retrieve()->ptr = NULL;
      else
      {
         keyLookup->Find(iterator2.Retrieve()->ptr->key);
         orderList->Retrieve()->ptr = keyLookup->Retrieve();
      }
      iterator2.Forward();
      (*orderList)++;
   }

}



// Clear
//    - deletes all internal dynamically allocated memory
template <class Etype>
void DisjointSets<Etype>::Clear()
{
   UpTreeNode<Etype>* deletePtr;
   delete keyLookup;
   orderList->Head();
   for (int i=1; i<=orderList->Length(); i++)
   {
      deletePtr = orderList->Retrieve();
      delete deletePtr;
      (*orderList)++;
   }
   delete orderList;

}

