// ***********************************************************
// *                                                         *
// *  nodedisjoint.C                                         *
// *                                                         *
// *  Sample solution for MP8: (Spring 99)                   *
// *  disjoint set class with Undo added                     *
// *                                                         *
// *  Written 30 October 1998 by Jason Zych                  *
// *  Update  07 April 1999 by David Bunde                   *
// *                  added path compression and Undo        *
// *                                                         *
// ***********************************************************

#include "nodedisjoint.h"

// Undo
//    - return value: boolean integer
//    - undoes the most recent Union operation and any intervening
//		path compression.  Returns 1 if there was a union to
//		undo, 0 otherwise
template<class Etype>
int DisjointSets<Etype>::Undo()
{
UndoRecord<Etype>* step;	//instructions for undoing one change

try		//try undo- see if enough information available
  {
  step = undoinfo -> Pop();	//get first change to make
  while(step->was_union != 1)	//stop when we get to the union
    {
    step -> node -> ptr = step -> prevparent;	//undo that change
    delete step;		//deallocate UndoRecord
    step = undoinfo -> Pop();	//get next change to make
    }

  //now undo change that was union: (count and pointers)
  (step -> node -> ptr -> count) -= (step -> node -> count);
  step -> node -> ptr = step -> prevparent;

  delete step;		//deallocate UndoRecord
  }
catch(StackError)
  {
  return 0;			//not enough undo information
  }

return 1;			//undo was successful
}

// 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>*>(); 
   undoinfo = new Stack<UndoRecord<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)
{
   UpTreeNode<Etype> *uptr1, *uptr2; 

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

   uptr1 = PFind(uptr1);
   uptr2 = PFind(uptr2);
   
   if (uptr1->count >= uptr2->count)
   {
      uptr1->count += uptr2->count; 
      undoinfo -> Push(new UndoRecord<Etype>(uptr2, uptr2->ptr, 1));
      uptr2->ptr = uptr1; 
   }
   else
   {
      uptr2->count += uptr1->count;
      undoinfo -> Push(new UndoRecord<Etype>(uptr1, uptr1->ptr, 1));
      uptr1->ptr = uptr2; 
   }
   
   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
     {
     undoinfo -> Push(new UndoRecord<Etype>(start, start->ptr, 0));
				//store undo information first

     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
     }

  return root;
}

// Copy
//    - parameters : origVal - previously allocated DisjointSets object
//    - copies origVal into this object
//    - the copy does not have any undo information
template <class Etype>
void DisjointSets<Etype>::Copy(const DisjointSets& origVal)
{
   keyLookup = new SetLookup<UpTreeNode<Etype>*>();
   orderList = new List<UpTreeNode<Etype>*>();
   undoinfo = new Stack<UndoRecord<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;

   UndoRecord<Etype>* temp;
   while(!(undoinfo->Is_Empty()))
     {
     temp = undoinfo -> Pop();
     delete temp;
     }
   delete undoinfo;
}

