// ************************************************************
// *                                                          *
// *  graph.cpp                                               *
// *                                                          *
// *  Implementations for graph-related classes               *
// *                                                          *
// *  Written Nov 1998 by Jason Zych                          *
// *   Updated by Nov 2003 by Seunghoon Kim                   *
// *      - Mass Update and Remove functions repaired         *
// *      - general code cleanup and commenting               *
// *                                                          *
// *  Inspiration for this graph class drawn from             *
// *   the publicly posted interface of the LEDA              *
// *   library: http://www.mpi-sb.mpg.de/LEDA/                *
// *                                                          *
// *  This file consists of five separate classes which       *
// *   are all related:                                       *
// *                                                          *
// *       - VertexNode : internal vertex implementation      *
// *       - Vertex : external "iterator" on VertexNode       *
// *                    objects, client uses Vertex objects   *
// *       - EdgeNode : internal edge implementation          *
// *       - Edge : external "iterator" on EdgeNode           *
// *                    objects, client uses Edge objects     *
// *       - Graph : internally, holds collection of vertices *
// *                   and collection of edges; functions     *
// *                   take Vertex and Edge objects as        *
// *                   parameters and manipulate the internal *
// *                   VertexNode and EdgeNode objects they   *
// *                   refer to.                              *
// *                                                          * 
// ************************************************************

#include <stddef.h>
#include <iostream.h>
#include "graph.h"



// InsertVertexAfter
//    - parameters : position - vertex reference
//    - return value : the new vertex
//    - adds a new vertex to graph after the vertex reference and returns it
Vertex Graph::InsertVertexAfter(Vertex position)
{
   // Step 1 : create new VertexNode for the list of vertices
   //    - assign this node an array key, for use in parameterized
   //        class
   //    - verify edge direction or lack of it in this graph 

   VertexNode* insVert = new VertexNode(); 
   vertexKeyCounter++; 
   insVert->vertexKey = vertexKeyCounter; 
   insVert->isDirected = isDirected; 


   // Step 2 : insert this VertexNode at end of vertex list
 
   if (vHead == NULL)
      vHead = insVert;
   else if (position.VPtr() == NULL)
   {
     insVert->nextVertex = vHead;
     insVert->prevVertex = vHead->prevVertex;
     if (vHead->prevVertex != NULL)
       vHead->prevVertex->nextVertex = insVert;
     vHead->prevVertex = insVert;
   }
   else
   {
      VertexNode* refVert = new VertexNode();
      refVert = position.VPtr();

      insVert->nextVertex = refVert->nextVertex; 
      insVert->prevVertex = refVert; 
      if (refVert->nextVertex != NULL)
        refVert->nextVertex->prevVertex = insVert;
      refVert->nextVertex = insVert; 
   }
   vSize++; 


   // Step 3 : return a Vertex that stores a pointer to the 
   //            new VertexNode

   return Vertex(insVert);  
}



// InsertVertexBefore
//    - parameters : position - vertex reference
//    - return value : the new vertex
//    - adds a new vertex to graph before the vertex reference and returns it
Vertex Graph::InsertVertexBefore(Vertex position)
{
   // Step 1 : create new VertexNode for the list of vertices
   //    - assign this node an array key, for use in parameterized
   //        class
   //    - verify edge direction or lack of it in this graph 

   VertexNode* insVert = new VertexNode(); 
   vertexKeyCounter++; 
   insVert->vertexKey = vertexKeyCounter; 
   insVert->isDirected = isDirected; 

   // Step 2 : insert this VertexNode at end of vertex list 

   if (vHead == NULL)
      vHead = insVert; 
   else if (position.VPtr() == NULL)
   {
     insVert->nextVertex = vHead;
     insVert->prevVertex = vHead->prevVertex;
     if (vHead->prevVertex != NULL)
       vHead->prevVertex->nextVertex = insVert;
     vHead->prevVertex = insVert;
     vHead = insVert;
   }
   else
   {
      VertexNode* refVert = new VertexNode();
      refVert = position.VPtr();

      insVert->prevVertex = refVert->prevVertex; 
      insVert->nextVertex = refVert; 
      if (refVert->prevVertex != NULL)
        refVert->prevVertex->nextVertex = insVert;
      refVert->prevVertex = insVert; 
   }
   vSize++; 


   // Step 3 : return a Vertex that stores a pointer to the 
   //            new VertexNode

   return Vertex(insVert);  
}


// InsertEdgeAfter
//    - parameters : sourceVert - source vertex of new edge
//                 : targetVert - target vertex of new edge
//                 : sourcePosition - source edge reference
//                 : targetPosition - target edge reference
//                 : listPosition - edge list reference
//    - return value : the new edge 
//    - adds a new edge to the graph between the parameter vertices, after the parameter edges
//         returns that edge
Edge Graph::InsertEdgeAfter(Vertex sourceVert, Vertex targetVert, Edge sourcePosition, Edge targetPosition, Edge listPosition)
{
   // extract VertexNode pointers from Vertex parameters 
   VertexNode* srcEndpoint = sourceVert.VPtr(); 
   VertexNode* tarEndpoint = targetVert.VPtr(); 
   EdgeNode* srcEdge = sourcePosition.EPtr();
   EdgeNode* tarEdge = targetPosition.EPtr();

   // Step 1 : create new EdgeNode for the list of edges 
   //    - assign this node an array key, for use in parameterized
   //        class
   //    - verify edge direction or lack of it in this graph

   EdgeNode* insEdge = new EdgeNode(); 
   edgeKeyCounter++; 
   insEdge->edgeKey = edgeKeyCounter; 
   insEdge->isDirected = isDirected; 


   // Step 2 : insert node into edge list

   if (eHead == NULL)
      eHead = insEdge; 
   else
     {
       if (srcEdge == NULL)
	 {
	   insEdge->nextSourceEdge = NULL;
	   insEdge->prevSourceEdge = NULL;
	 }
       else
	 {
	   insEdge->nextSourceEdge = srcEdge->nextSourceEdge; 
	   insEdge->prevSourceEdge = srcEdge; 
	   if (srcEdge->nextSourceEdge != NULL)
	     srcEdge->nextSourceEdge->prevSourceEdge = insEdge; 
	   srcEdge->nextSourceEdge = insEdge; 
	 }
       if (tarEdge == NULL)
	 {
	   insEdge->nextTargetEdge = NULL;
	   insEdge->prevTargetEdge = NULL;
	 }
       else
	 {
	   insEdge->nextTargetEdge = tarEdge->nextTargetEdge; 
	   insEdge->prevTargetEdge = tarEdge; 
	   if (tarEdge->nextTargetEdge != NULL)
	     tarEdge->nextTargetEdge->prevTargetEdge = insEdge; 
	   tarEdge->nextTargetEdge = insEdge; 
	 }
     }   
   eSize++; 


   // Step 3 : insert node into source and target edge lists
   // insertion into edge lists is different depending on 
   //   whether graph is directed or undirected

   insEdge->source = srcEndpoint;
   insEdge->target = tarEndpoint;
   if (isDirected)
      InsertEdgeIntoDirected(insEdge); 
   else
      InsertEdgeIntoUndirected(insEdge);


   // Step 4 : return an Edge that stores a pointer to the
   //            new EdgeNode

   return Edge(insEdge);
}


// InsertEdgeBefore
//    - parameters : sourceVert - source vertex of new edge
//                 : targetVert - target vertex of new edge
//                 : sourcePosition - source edge reference
//                 : targetPosition - target edge reference
//                 : listPosition - edge list reference
//    - return value : the new edge 
//    - adds a new edge to the graph between the parameter vertices, before the parameter edges
//         returns that edge
Edge Graph::InsertEdgeBefore(Vertex sourceVert, Vertex targetVert, Edge sourcePosition, Edge targetPosition, Edge listPosition)
{
   // extract VertexNode pointers from Vertex parameters 
   VertexNode* srcEndpoint = sourceVert.VPtr(); 
   VertexNode* tarEndpoint = targetVert.VPtr(); 
   EdgeNode* srcEdge = sourcePosition.EPtr();
   EdgeNode* tarEdge = targetPosition.EPtr();

   // Step 1 : create new EdgeNode for the list of edges 
   //    - assign this node an array key, for use in parameterized
   //        class
   //    - verify edge direction or lack of it in this graph

   EdgeNode* insEdge = new EdgeNode(); 
   edgeKeyCounter++; 
   insEdge->edgeKey = edgeKeyCounter; 
   insEdge->isDirected = isDirected; 


   // Step 2 : insert node into edge list

   if (eHead == NULL)
      eHead = insEdge; 
   else
     {
       if (srcEdge == NULL)
	 {
	   insEdge->nextSourceEdge = NULL;
	   insEdge->prevSourceEdge = NULL;
	 }
       else
	 {
	   insEdge->prevSourceEdge = srcEdge->prevSourceEdge; 
	   insEdge->nextSourceEdge = srcEdge;
	   if (srcEdge->prevSourceEdge != NULL)	  
	     srcEdge->prevSourceEdge->nextSourceEdge = insEdge; 
	   srcEdge->prevSourceEdge = insEdge; 
	 }
       if (tarEdge == NULL)
	 {
	   insEdge->nextTargetEdge = NULL;
	   insEdge->prevTargetEdge = NULL;
	 }
       else
	 {
	   insEdge->prevTargetEdge = tarEdge->prevTargetEdge; 
	   insEdge->nextTargetEdge = tarEdge; 
           if (tarEdge->prevTargetEdge != NULL)
	     tarEdge->prevTargetEdge->nextTargetEdge = insEdge; 
	   tarEdge->prevTargetEdge = insEdge; 
	 }
     }
   eSize++; 


   // Step 3 : insert node into source and target edge lists
   // insertion into edge lists is different depending on 
   //   whether graph is directed or undirected

   insEdge->source = srcEndpoint;
   insEdge->target = tarEndpoint;
   if (isDirected)
      InsertEdgeIntoDirected(insEdge); 
   else
      InsertEdgeIntoUndirected(insEdge);


   // Step 4 : return an Edge that stores a pointer to the
   //            new EdgeNode

   return Edge(insEdge);
}




// *** END OF YOUR CODE

// **************************************************************
// *                                                            *
// *  Class : VertexNode                                        *
// *                                                            *
// *  A vertex implementation, to be manipulated by a           *
// *     Graph class but hidden from the user of the Graph      *
// *     class. This is the implementation for the class.       *
// *                                                            *
// **************************************************************


// VertexNode
//    - default constructor
//    - initializes object to default values
VertexNode::VertexNode()
{
   vertexKey = vertexMark = 0;          
   isDirected = 1;                      // defaults to directed


   numDepartEdges = numEnterEdges = 0;  // no edges of any kind yet
   departingEdges = NULL;  
   enteringEdges =  NULL;  

   prevVertex = this;    // If this is the only vertex
   nextVertex = this;    //   in the list, then it is also 
			 //   its own successor and predecessor,
			 //   since the list is circular. If it
			 //   is not the only vertex in the list,
			 //   these fields can be altered in the
			 //   vertex insertion algorithms. 
}




// **************************************************************
// *                                                            *
// *  Class : Vertex                                            *
// *                                                            *
// *  A vertex wrapper class. This class will provide access    *
// *     to a VertexNode object, but only from within the       *
// *     actual Graph class itself. The only parts of this      *
// *     interface that are available to the user are the       *
// *     creation and assignment operators. This way, the user  *
// *     can maintain "pointers" to vertices without actually   *
// *     being able to access their fields or needing to know   *
// *     their implementation.                                  *
// *                                                            *
// **************************************************************


// Vertex
//    - default constructor
//    - initializes object to default values
Vertex::Vertex()
{
   vertexNodePtr = NULL; 
}



// operator==
//    - parameters : compareVert - a vertex to which we can compare
//                      this object
//    - return value : boolean integer
//    - returns 1 if the two vertices point to the same node,
//         otherwise returns 0
int Vertex::operator==(const Vertex& compareVert)
{
   return (vertexNodePtr == compareVert.vertexNodePtr);
}



// operator!=
//    - parameters : compareVert - a vertex to which we can compare
//                      this object
//    - return value : boolean integer
//    - returns 0 if the two vertices point to the same node,
//         otherwise returns 1
int Vertex::operator!=(const Vertex& compareVert)
{
   return (vertexNodePtr != compareVert.vertexNodePtr);
}



// Vertex
//    - constructor
//    - parameters : initPtr - a VertexNode pointer used to
//                     initialize this object
//    - a private constructor which initializes the Vertex object
//         given a VertexNode pointer. Essentially, this function
//         "casts" the VertexNode pointer to a Vertex object.
Vertex::Vertex(VertexNode* initVPtr)
{
   vertexNodePtr = initVPtr; 
}



// VPtr
//    - return value : pointer to the internal VertexNode pointer
//    - returns the value held in the internal VertexNode pointer.
//         Used to shorten the syntax needed to access the
//         "vertexNodePtr" field of this object
VertexNode* Vertex::VPtr()
{
   return vertexNodePtr; 
}




// **************************************************************
// *                                                            *
// *  Class : EdgeNode                                          *
// *                                                            *
// *  An edge implementation, to be manipulated by a            *
// *     Graph class but hidden from the user of the Graph      *
// *     class. This is the implementation for the class.       *
// *                                                            *
// *  Written 13 Nov 1998 by Jason Zych                         *
// *                                                            *
// **************************************************************


// EdgeNode
//    - default constructor
//    - initializes object to default values
EdgeNode::EdgeNode()
{
   edgeKey = edgeMark = 0;        
   isDirected = 1;               // defaults to directed  

   
   source = NULL;                // endpoints are unknown at 
   target = NULL;                //    creation time



   // EdgeNode objects are part of three lists:
   //    1) the list of all edges
   //    2) the list of all edges departing from its source vertex
   //    3) the list of all edges entering its target vertex
   // For each list, if this is the only edge in the list, then
   // it is also its own successor and predecessor, since we want
   // the lists to be circular. If it is not the only vertex in 
   // a certain list, then these fields can be altered in the edge
   // insertion algorithms. 

   prevEdge = nextEdge = this;               // list of all edges
   prevSourceEdge = nextSourceEdge = this;   // list of edges from source
   prevTargetEdge = nextTargetEdge = this;   // list of edges to target
} 



// ********************************************************************
// *                                                                  *
// *  Class : Edge                                                    *
// *                                                                  *
// *  An edge wrapper class. This class will provide access           *
// *     to an EdgeNode object, but only from within the              *
// *     actual Graph class itself. The only parts of this            *
// *     interface that are available to the user are the             *
// *     creation and assignment operators. This way, the user        *
// *     can maintain "pointers" to edges without actually            *
// *     being able to access their fields or needing to know         *
// *     their implementation.                                        *
// *                                                                  *
// *  Written 13 Nov 1998 by Jason Zych                               *
// *                                                                  *
// ********************************************************************



// Edge
//    - default constructor
//    - initializes object to default values
Edge::Edge()
{
   edgeNodePtr = NULL; 
}


// operator==
//    - parameters : compareEdge - an edge to which we can compare
//                      this object
//    - return value : boolean integer
//    - returns 1 if the two Edge objects wrap around the same edge, 
//         otherwise returns 0
int Edge::operator==(const Edge& compareEdge)
{
   return (edgeNodePtr == compareEdge.edgeNodePtr);
}



// operator!=
//    - parameters : compareEdge - an edge to which we can compare
//                      this object
//    - return value : boolean integer
//    - returns 0 if the two Edge objects wrap around the same edge 
//         otherwise returns 1
int Edge::operator!=(const Edge& compareEdge)
{
   return (edgeNodePtr != compareEdge.edgeNodePtr);
}



// Edge 
//    - constructor
//    - parameters : initEPtr - an EdgeNode pointer used to 
//                     initialize this object
//    - a private constructor which initializes the Edge object
//         given an EdgeNode pointer. Essentially, this function
//         "casts" the EdgeNode pointer to a Edge object.
Edge::Edge(EdgeNode* initEPtr)
{ 
   edgeNodePtr = initEPtr; 
}



// EPtr
//    - return value : pointer to the internal EdgeNode pointer
//    - returns the value held in the internal EdgeNode pointer.
//         Used to shorten the syntax needed to access the
//         "edgeNodePtr" field of this object
EdgeNode* Edge::EPtr()
{
   return edgeNodePtr; 
}





// *********************************************************************
// *                                                                   *
// *  Class : Graph                                                    *
// *                                                                   *
// *  A class providing a graph representation. The interface          *
// *   functions allow the user to manipulate the graph with           *
// *   full knowledge of and access to the structure of the            *
// *   graph -- that is, knowledge of the existence of                 *
// *   vertices and edges, and which vertices are adjacent to          *
// *   which other vertices via which edges -- but the user            *
// *   does not have access to the actual vertex and edge              *
// *   implementations, but rather only knowledge of the               *
// *   _existence_ of the vertices and edges. Therefore, any           *
// *   manipulation of the graph _must_ be done via the graph          *
// *   functions themselves, and therefore the user is able            *
// *   to view the graph in a very abstract manner.                    *
// *                                                                   *
// *  Written 13 Nov 1998 by Jason Zych                                *
// *                                                                   *
// *********************************************************************


// ********************** Mass Update **********************


// Graph
//    - default constructor
//    - initializes object to default values
Graph::Graph(int isDirectedFlag)
{   
   vHead = NULL;         // circularly-linked list of vertices
   vSize = 0;            //   starts out empty

   eHead = NULL;         // circularly-linked list of edges
   eSize = 0;            //   start out empty

   isDirected = isDirectedFlag;   // defaults to directed

   vertexKeyCounter = 0;
   edgeKeyCounter = 0;
}



// Graph
//    - copy constructor
//    - parameters : origVal - previously allocated Graph object
//    - initializes object to be a copy of origVal
Graph::Graph(const Graph& origVal)
{
   Copy(origVal);   
}
 


// ~Graph
//    - destructor
//    - deletes dynamically allocated memory
Graph::~Graph()
{
   Clear(); 
}



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




// Clear 
//    - sets object to be a copy of default (empty) graph. 
//      Graph will remain directed or remain undirected; this
//      function call will not change that.
void Graph::Clear()
{
   // Step 1 : Delete vertex list
   //    - traverse circularly-linked list of VertexNode
   //       objects, deleting them one-by-one 

   VertexNode *frontVPtr, *prevVPtr; 
   frontVPtr = vHead;

   // if there are vertices in the vertex list, set the last
   //   node to point to NULL rather than the first node, 
   //   for ease of loop stopping
   if (frontVPtr!=NULL)
      frontVPtr->prevVertex->nextVertex = NULL; 

   while (frontVPtr != NULL)
   {
      prevVPtr = frontVPtr;
      frontVPtr = frontVPtr->nextVertex; 
      delete prevVPtr; 
   }

 
   // Step 2 : Delete edge list
   //    - traverse circularly-linked list of EdgeNode
   //       objects, deleting them one-by-one

   EdgeNode *frontEPtr, *prevEPtr; 
   frontEPtr = eHead; 

   // if there are edges in the edge list, set the last 
   //   node point to NULL rather than the first node, 
   //   for ease of loop stopping
   if (frontEPtr!=NULL)
      frontEPtr->prevEdge->nextEdge = NULL; 
  
   while (frontEPtr != NULL)
   {
      prevEPtr = frontEPtr; 
      frontEPtr = frontEPtr->nextEdge; 
      delete prevEPtr; 
   }


   // Step 3 : re-initialize the Graph member data, EXCEPT
   //   for the "isDirected" flag. Whatever the user last set
   //   this graph to be -- directed or undirected -- is what
   //   it should still be. 

   vHead = NULL;         // circularly-linked list of vertices
   vSize = 0;            //   is once again empty

   eHead = NULL;         // circularly-linked list of edges
   eSize = 0;            //   is once again empty

   vertexKeyCounter = 0;
   edgeKeyCounter = 0;

}





// ******************* Graph structure alteration *******************

// MakeUndirected
//    - if graph is undirected, function returns without
//       doing anything. If graph is directed, it is converted
//       to an undirected graph. The new graph will be the old
//       graph with direction removed from the edges -- that
//       is, if you previously had an edge from a->b, you now
//       have an a-b edge (i.e. the edge becomes undirected).
void Graph::MakeUndirected()
{
   if (isDirected)
   {
      isDirected = 0;
      int moreVertices;
      VertexNode* vertPtr;
      EdgeNode* tempEdge;
      vertPtr = vHead;    // first vertex of graph
      if (vertPtr == NULL)
         moreVertices = 0;
      else
         moreVertices = 1;
      while (moreVertices)
      {
         if (vertPtr->departingEdges == NULL)
         {
            vertPtr->departingEdges = vertPtr->enteringEdges;
            vertPtr->enteringEdges = NULL;
         }
         else if (vertPtr->enteringEdges != NULL)
         {
            tempEdge = vertPtr->enteringEdges->prevTargetEdge;
            vertPtr->departingEdges->prevSourceEdge->nextSourceEdge =
                vertPtr->enteringEdges;
            vertPtr->enteringEdges->prevTargetEdge->nextTargetEdge =
                vertPtr->departingEdges;
            vertPtr->enteringEdges->prevTargetEdge =
                vertPtr->departingEdges->prevSourceEdge;
            vertPtr->departingEdges->prevSourceEdge = tempEdge;
            vertPtr->numDepartEdges += vertPtr->numEnterEdges;
            vertPtr->enteringEdges = NULL;
            vertPtr->numEnterEdges = 0;
         }

         vertPtr = vertPtr->nextVertex;
         if (vertPtr == vHead)
            moreVertices = 0;
      }

   }
}




// InsertVertex
//    - return value : the new vertex
//    - adds a new vertex to graph and returns it
Vertex Graph::InsertVertex()
{
   // Step 1 : create new VertexNode for the list of vertices
   //    - assign this node an array key, for use in parameterized
   //        class
   //    - verify edge direction or lack of it in this graph 

   VertexNode* insVert = new VertexNode(); 
   vertexKeyCounter++; 
   insVert->vertexKey = vertexKeyCounter; 
   insVert->isDirected = isDirected; 


   // Step 2 : insert this VertexNode at end of vertex list
 
   if (vHead == NULL)
      vHead = insVert; 
   else
   {
      insVert->prevVertex = vHead->prevVertex; 
      insVert->nextVertex = vHead; 
      vHead->prevVertex->nextVertex = insVert;
      vHead->prevVertex = insVert; 
   }
   vSize++; 


   // Step 3 : return a Vertex that stores a pointer to the 
   //            new VertexNode

   return Vertex(insVert);  
}



 
// RemoveVertex
//    - parameters : delVert - vertex to be deleted
//    - deletes parameter vertex from graph
void Graph::RemoveVertex(Vertex delVert)
{
   // extract VertexNode pointer from Vertex
   VertexNode* deleteVertNode = delVert.VPtr();

   EdgeNode *travPtr,   // for traversing down lists of edges 
            *delPtr;    // for deleting edges


   // Step 1 : delete departing edges of delVert 

   travPtr = deleteVertNode->departingEdges; 
   if (travPtr != NULL)   // if the vertex has departing edges 
   {
      // exit loop when our current edge is the last one in
      //   the list, i.e. when the next edge in the circularly
      //   linked list is also the first one
      while (travPtr->nextSourceEdge != deleteVertNode->departingEdges)
      {
         delPtr = travPtr; 
         travPtr = travPtr->nextSourceEdge;
         RemoveEdge(Edge(delPtr));
      }
      RemoveEdge(Edge(travPtr));  // now, take care of that last edge 
   }


   // Step 2 : delete entering edges of delVert

   travPtr = deleteVertNode->enteringEdges;
   if (travPtr != NULL)
   {
      // exit loop when our current edge is the last one in 
      //   the list, i.e. when the next edge in the circularly
      //   linked list is also the first one 
      while (travPtr->nextTargetEdge != deleteVertNode->enteringEdges)
      {
         delPtr = travPtr; 
         travPtr = travPtr->nextTargetEdge;
         RemoveEdge(Edge(delPtr));
      }
      RemoveEdge(Edge(travPtr));  // now, take care of that last edge
   }


   // Step 3 : remove the vertex itself from the graph
    
   // if the vertex points to itself, it is the only vertex in 
   //    the vertex list
   if (deleteVertNode == deleteVertNode->nextVertex)   
      vHead = NULL;    // no more vertices left in list 
   else   // else there is more than vertex in the vertex list
   {
      deleteVertNode->nextVertex->prevVertex = deleteVertNode->prevVertex; 
      deleteVertNode->prevVertex->nextVertex = deleteVertNode->nextVertex; 

      // if the first vertex in the list is being deleted, point the
      //   list pointer (vHead) to the next vertex instead
      if (vHead == deleteVertNode)            
         vHead = deleteVertNode->nextVertex; 
   }                               

   delete deleteVertNode; 
   vSize--;  
}




// InsertEdge
//    - parameters : sourceVert - source vertex of new edge
//                 : targetVert - target vertex of new edge
//    - return value : the new edge 
//    - adds a new edge to the graph between the parameter vertices, 
//         returns that edge
Edge Graph::InsertEdge(Vertex sourceVert, Vertex targetVert)
{
   // extract VertexNode pointers from Vertex parameters 
   VertexNode* srcEndpoint = sourceVert.VPtr(); 
   VertexNode* tarEndpoint = targetVert.VPtr(); 

   // Step 1 : create new EdgeNode for the list of edges 
   //    - assign this node an array key, for use in parameterized
   //        class
   //    - verify edge direction or lack of it in this graph

   EdgeNode* insEdge = new EdgeNode(); 
   edgeKeyCounter++; 
   insEdge->edgeKey = edgeKeyCounter; 
   insEdge->isDirected = isDirected; 


   // Step 2 : insert node into edge list

   if (eHead == NULL)
      eHead = insEdge; 
   else
   {
      insEdge->prevEdge = eHead->prevEdge; 
      insEdge->nextEdge = eHead; 
      eHead->prevEdge->nextEdge = insEdge; 
      eHead->prevEdge = insEdge; 
   }
   eSize++; 


   // Step 3 : insert node into source and target edge lists
   // insertion into edge lists is different depending on 
   //   whether graph is directed or undirected

   insEdge->source = srcEndpoint;
   insEdge->target = tarEndpoint;
   if (isDirected)
      InsertEdgeIntoDirected(insEdge); 
   else
      InsertEdgeIntoUndirected(insEdge);


   // Step 4 : return an Edge that stores a pointer to the
   //            new EdgeNode

   return Edge(insEdge);
}



// RemoveEdge
//    - parameters : delEdge - edge to be deleted
//    - deletes parameter edge
void Graph::RemoveEdge(Edge delEdge)
{
   // Extract EdgeNode pointer from edge
   EdgeNode* deleteEdgeNode = delEdge.edgeNodePtr;


   // Step 1 : Disconnect deleteEdgeNode from the two lists
   //              of vertex's edges that it is a part of 

   if (isDirected)
      RemoveEdgeFromDirected(deleteEdgeNode);
   else
      RemoveEdgeFromUndirected(deleteEdgeNode);



   // Step 2: Remove deleteEdgeNode from list of all edges 
    
   if (eSize == 1)
      eHead = NULL;
   else  // else there is more than one edge in the edge list
   {
      deleteEdgeNode->nextEdge->prevEdge = deleteEdgeNode->prevEdge;
      deleteEdgeNode->prevEdge->nextEdge = deleteEdgeNode->nextEdge;
    
      // if the first edge in the list is being deleted, point the
      //   list pointer (eHead) to the next edge instead
      if (eHead == deleteEdgeNode)
         eHead = deleteEdgeNode->nextEdge;
   }

   delete deleteEdgeNode;
   eSize--;
}



// ReverseEdge
//    - parameters : revEdge - edge to reverse
//    - reverse revEdge (i.e. makes its former source endpoint
//       its target endpoint and vice-versa)
void Graph::ReverseEdge(Edge revEdge)
{
   // Extract EdgeNode pointer from edge
   EdgeNode* edgeToReverse = revEdge.edgeNodePtr;

   VertexNode* tempVert;
   EdgeNode* tempEdge;

   if (isDirected)
   {
      // if this is the last departing edge, then there are now none
      if (edgeToReverse->source->numDepartEdges == 1)
         edgeToReverse->source->departingEdges = NULL;
      // otherwise, if this is the first of many departing edges,
      //   the next one is now first
      else if (edgeToReverse->source->departingEdges == edgeToReverse)
         edgeToReverse->source->departingEdges =
                                edgeToReverse->nextSourceEdge;
      // otherwise, nothing special about this edge as far as its
      //   source vertex is concerned

      // extract from doubly, circularly linked departing edge list
      //    of source
      edgeToReverse->prevSourceEdge->nextSourceEdge =
                                edgeToReverse->nextSourceEdge;
      edgeToReverse->nextSourceEdge->prevSourceEdge =
                                edgeToReverse->prevSourceEdge;
      (edgeToReverse->source->numDepartEdges)--;



      // if this is the last entering edge, then there are now none
      if (edgeToReverse->target->numEnterEdges == 1)
         edgeToReverse->target->enteringEdges = NULL;
      // otherwise, if this is the first of many entering edges,
      //   the next one is now first
      if (edgeToReverse->target->enteringEdges == edgeToReverse)
         edgeToReverse->target->enteringEdges =
                                edgeToReverse->nextTargetEdge;
      // otherwise, nothing special about this edge as far as its
      //   target vertex is concerned

      // extract from doubly, circularly linked entering edge list
      //    of target
      edgeToReverse->prevTargetEdge->nextTargetEdge =
                                edgeToReverse->nextTargetEdge;
      edgeToReverse->nextTargetEdge->prevTargetEdge =
                                edgeToReverse->prevTargetEdge;
      (edgeToReverse->target->numEnterEdges)--;

   

      // reverse source and target
      tempVert = edgeToReverse->source;
      edgeToReverse->source = edgeToReverse->target;
      edgeToReverse->target = tempVert;


      // insert into departing edge list of new source
      if (edgeToReverse->source->departingEdges == NULL)
      {
         edgeToReverse->source->departingEdges = edgeToReverse;
         edgeToReverse->nextSourceEdge = edgeToReverse;
         edgeToReverse->prevSourceEdge = edgeToReverse;
      }
      else
      {
         edgeToReverse->prevSourceEdge =
                edgeToReverse->source->departingEdges->prevSourceEdge;
         edgeToReverse->nextSourceEdge =
                edgeToReverse->source->departingEdges;
         edgeToReverse->source->departingEdges->prevSourceEdge->nextSourceEdge =
                edgeToReverse;
         edgeToReverse->source->departingEdges->prevSourceEdge = edgeToReverse;
      }
      (edgeToReverse->source->numDepartEdges)++;


      // insert into entering edge list of new target
      if (edgeToReverse->target->enteringEdges == NULL)
      {
         edgeToReverse->target->enteringEdges = edgeToReverse;
         edgeToReverse->nextTargetEdge = edgeToReverse;
         edgeToReverse->prevTargetEdge = edgeToReverse;
      }
      else
      {
         edgeToReverse->prevTargetEdge =
                edgeToReverse->target->enteringEdges->prevTargetEdge;
         edgeToReverse->nextTargetEdge =
                edgeToReverse->target->enteringEdges;
         edgeToReverse->target->enteringEdges->prevTargetEdge->nextTargetEdge =
                edgeToReverse;
         edgeToReverse->target->enteringEdges->prevTargetEdge = edgeToReverse;
      }
      (edgeToReverse->target->numEnterEdges)++;
   }
}






// ******************* Graph structure information ******************


//      ---------- Graph information

// NumGraphVertices
//    - return value : integer quantity
//    - returns the number of vertices in the graph
int Graph::NumGraphVertices()
{
   return vSize; 
}


// NumGraphEdges
//    - return value : integer quantity
//    - returns the number of edges in the graph
int Graph::NumGraphEdges()
{ 
   return eSize; 
}



//      ---------- Vertex information

// NumDepartEdges
//    - parameters : queryVert - vertex which we want information about
//    - return value : integer quantity
//    - returns the number of edges departing from Vertex queryVert
int Graph::NumDepartEdges(Vertex queryVert)
{
   return queryVert.VPtr()->numDepartEdges; 
}



// NumEnterEdges
//    - parameters : queryVert - vertex which we want information about
//    - return value : integer quantity
//    - returns the number of edges entering Vertex queryVert
int Graph::NumEnterEdges(Vertex queryVert)
{
   return queryVert.VPtr()->numEnterEdges;
}



// NumTotalEdges
//    - parameters : queryVert - vertex which we want information about
//    - return value : integer quantity
//    - returns the number of edges departing or entering Vertex queryVert
int Graph::NumTotalEdges(Vertex queryVert)
{
   return (queryVert.VPtr()->numEnterEdges + 
	  queryVert.VPtr()->numDepartEdges); 
}




//      ---------- Edge information

// Source
//    - parameters : queryEdge - edge which we want information about
//    - return value : a vertex of the graph
//    - returns source vertex of this edge (i.e. the vertex it departs)
Vertex Graph::Source(Edge queryEdge)
{
   return Vertex(queryEdge.EPtr()->source); 
}


// Target
//    - parameters : queryEdge - edge which we want information about
//    - return value : a vertex of the graph
//    - returns target vertex of this edge (i.e. the vertex it enters)
Vertex Graph::Target(Edge queryEdge)
{
   return Vertex(queryEdge.EPtr()->target); 
}


// OtherEndpoint
//    - parameters : queryEdge - edge which we want information about
//                 : endpointOne - one of the two endpoints of the edge
//    - return value : a vertex of the graph
//    - if endpointOne is the source vertex of this edge, the target 
//        vertex of this edge will be returned. If endpointOne is 
//        instead the target vertex of this edge, the source vertex 
//        will be returned. If endpointOne is not an endpoint of this
//        edge, the nil vertex will be returned
Vertex Graph::OtherEndpoint(Edge queryEdge, Vertex endpointOne)
{
   if (queryEdge.EPtr()->source == endpointOne.VPtr())
      return Vertex(queryEdge.EPtr()->target); 
   else if (queryEdge.EPtr()->target == endpointOne.VPtr())
      return Vertex(queryEdge.EPtr()->source); 
   else 
      return Vertex(); 
}





// ********************** Graph traversal *******************


//      ---------- Vertex traversal 

// FirstVertex
//    - return type : a vertex of the graph
//    - returns the "first" vertex in the abstract set of
//        vertices of the graph. If graph is empty, returns
//        the nil vertex.
Vertex Graph::FirstVertex()
{
   if (vHead == NULL)
      return Vertex(); 
   else
      return Vertex(vHead); 
}



// LastVertex
//    - return type : a vertex of the graph
//    - returns the "last" vertex in the abstract set of
//        vertices of the graph. If graph is empty, returns
//        the nil vertex.
Vertex Graph::LastVertex()
{
   if (vHead == NULL)
      return Vertex(); 
   else
      return Vertex(vHead->prevVertex); 
}



// NextVertex
//    - parameters : currentVert - a vertex of the graph
//    - return type : a vertex of the graph
//    - returns the vertex "after" currentVert in the abstract set 
//        of vertices of the graph. If currentVert is the last vertex 
//        in the vertex set, returns the nil vertex.
Vertex Graph::NextVertex(Vertex currentVert)
{
   if (currentVert.VPtr()->nextVertex == vHead)
      return Vertex(); 
   else
      return Vertex(currentVert.VPtr()->nextVertex); 
}



// PrevVertex
//    - parameters : currentVert - a vertex of the graph
//    - return type : a vertex of the graph
//    - returns the vertex "before" currentVert in the abstract set 
//        of vertices of the graph. If currentVert is the first 
//        vertex in the vertex set, returns the  nil vertex.
Vertex Graph::PrevVertex(Vertex currentVert)
{
   if (currentVert.VPtr() == vHead)
      return Vertex(); 
   else
      return Vertex(currentVert.VPtr()->prevVertex); 
}




//      ---------- Edge traversal 

// FirstEdge
//    - return type : an edge of the graph
//    - returns the "first" edge in the abstract set of
//        edges of the graph. If graph has no edges, returns
//        the nil edge.
Edge Graph::FirstEdge()
{
   if (eHead == NULL)
      return Edge(); 
   else
      return Edge(eHead); 
}


// LastEdge
//    - return type : an edge of the graph
//    - returns the "last" edge in the abstract set of
//        edges of the graph. If graph has no edges, returns
//        the nil edge.
Edge Graph::LastEdge()
{
   if (eHead == NULL)
      return Edge(); 
   else
      return Edge(eHead->prevEdge); 
}


// NextEdge
//    - parameters : currentEdge - an edge of the graph
//    - return type : an edge of the graph
//    - returns the edge "after" currentEdge in the abstract
//        set of edges of the graph. If currentEdge is the last
//        edge in the edge set, returns the nil edge
Edge Graph::NextEdge(Edge currentEdge)
{
   if (currentEdge.EPtr()->nextEdge == eHead) 
      return Edge(); 
   else
      return Edge(currentEdge.EPtr()->nextEdge);  
}


// PrevEdge
//    - parameters : currentEdge - an edge of the graph
//    - return type : an edge of the graph
//    - returns the edge "before" currentEdge in the abstract 
//        set of edges of the graph. If currentEdge is the first 
//        edge in the edge set, returns the nil edge
Edge Graph::PrevEdge(Edge currentEdge)
{
   if (currentEdge.EPtr() == eHead)
      return Edge(); 
   else
      return Edge(currentEdge.EPtr()->prevEdge);  
}



//      ---------- Vertex departing edge traversal
//                     --- meant for directed graphs

// FirstDepartEdge
//    - parameters : departFromVert - vertex we are inspecting
//    - return value : an edge of the graph
//    - returns the "first" edge in the abstract set
//        of all edges departing from the vertex departFromVert. 
//        If departFromVert has no departing edges, returns
//        the nil edge.
Edge Graph::FirstDepartEdge(Vertex departFromVert)
{
   if (departFromVert.VPtr()->departingEdges == NULL)
      return Edge(); 
   else
      return Edge(departFromVert.VPtr()->departingEdges); 
}


// LastDepartEdge
//    - parameters : departFromVert - vertex we are inspecting
//    - return value : an edge of the graph
//    - returns the "last" edge in the abstract set
//        of all edges departing from the vertex departFromVert. 
//        If departFromVert has no departing edges, returns
//        the nil edge.
Edge Graph::LastDepartEdge(Vertex departFromVert)
{
   if (departFromVert.VPtr()->departingEdges == NULL)
      return Edge(); 
   else 
      return Edge(departFromVert.VPtr()->departingEdges->prevSourceEdge); 
}



// NextDepartEdge
//    - parameters : currentEdge - an edge of the graph
//    - return value : an edge of the graph
//    - returns the edge "after" currentEdge in the abstract
//        set of all edges which depart from the same source 
//        vertex as currentEdge. (The source vertex can be found
//        from the edge, which is why we don't need to pass in
//        the source vertex as a parameter.) If this is the last
//        edge in the set described above, returns the nil edge. 
Edge Graph::NextDepartEdge(Edge currentEdge)
{
   if (currentEdge.EPtr()->nextSourceEdge == 
		currentEdge.EPtr()->source->departingEdges)
      return Edge(); 
   else
      return Edge(currentEdge.EPtr()->nextSourceEdge);  
}



// PrevDepartEdge
//    - parameters : currentEdge - an edge of the graph
//    - return value : an edge of the graph
//    - returns the edge "before" currentEdge in the abstract
//        set of all edges which depart from the same source 
//        vertex as currentEdge. (The source vertex can be found
//        from the edge, which is why we don't need to pass in
//        the source vertex as a parameter.) If this is the first 
//        edge in the set described above, returns the nil edge. 
Edge Graph::PrevDepartEdge(Edge currentEdge)
{
   if (currentEdge.EPtr() == currentEdge.EPtr()->source->departingEdges)
      return Edge(); 
   else
      return Edge(currentEdge.EPtr()->prevSourceEdge);  
}



//      ---------- Vertex entering edge traversal
//                     --- meant for directed graphs

// FirstEnterEdge
//    - parameters : enterIntoVert - vertex we are inspecting
//    - return value : an edge of the graph
//    - returns the "first" edge in the abstract set
//        of all edges entering the vertex enterIntoVert. 
//        If enterIntoVert has no entering edges, returns
//        the nil edge.
Edge Graph::FirstEnterEdge(Vertex enterIntoVert)
{
   if ((enterIntoVert.VPtr()->enteringEdges == NULL) || (!isDirected))
      return Edge(); 
   else
      return Edge(enterIntoVert.VPtr()->enteringEdges); 
}


// LastEnterEdge
//    - parameters : enterIntoVert - vertex we are inspecting
//    - return value : an edge of the graph
//    - returns the "last" edge in the abstract set
//        of all edges entering the vertex enterIntoVert. 
//        If enterIntoVert has no entering edges, returns
//        the nil edge.
Edge Graph::LastEnterEdge(Vertex enterIntoVert)
{
   if ((enterIntoVert.VPtr()->enteringEdges == NULL) || (!isDirected))
      return Edge(); 
   else 
      return Edge(enterIntoVert.VPtr()->enteringEdges->prevTargetEdge); 
}


// NextEnterEdge
//    - parameters : currentEdge - an edge of the graph
//    - return value : an edge of the graph
//    - returns the edge "after" currentEdge in the abstract
//        set of all edges which enter same target 
//        vertex as currentEdge. (The target vertex can be found
//        from the edge, which is why we don't need to pass in
//        the target vertex as a parameter.) If this is the last
//        edge in the set described above, returns the nil edge.
Edge Graph::NextEnterEdge(Edge currentEdge)
{
   if ((currentEdge.EPtr()->nextTargetEdge == 
		currentEdge.EPtr()->target->enteringEdges) || (!isDirected))
      return Edge(); 
   else
      return Edge(currentEdge.EPtr()->nextTargetEdge); 
}



// PrevEnterEdge
//    - parameters : currentEdge - an edge of the graph
//    - return value : an edge of the graph
//    - returns the edge "before" currentEdge in the abstract
//        set of all edges which enter the same target 
//        vertex as currentEdge. (The target vertex can be found
//        from the edge, which is why we don't need to pass in
//        the target vertex as a parameter.) If this is the first 
//        edge in the set described above, returns the nil edge. 
Edge Graph::PrevEnterEdge(Edge currentEdge)
{
   if ((currentEdge.EPtr() == 
              currentEdge.EPtr()->target->enteringEdges) || (!isDirected))
      return Edge(); 
   else 
      return Edge(currentEdge.EPtr()->prevTargetEdge); 
}



//      ---------- Vertex adjacent edge traversal 
//                      --- meant for undirected graphs

// FirstAdjacentEdge
//    - parameters : endpointVert - vertex we are inspecting
//    - return value : an edge of the graph
//    - returns the "first" edge in the abstract set
//        of all edges which have endpointVert as an endpoint 
//        If endpointVert is not an endpoint of any edge, returns
//        the nil edge.
Edge Graph::FirstAdjacentEdge(Vertex endpointVert)
{
   if (endpointVert.VPtr()->departingEdges == NULL)
      return Edge(); 
   else
      return Edge(endpointVert.VPtr()->departingEdges); 
}




// LastAdjacentEdge
//    - parameters : endpointVert - vertex we are inspecting
//    - return value : an edge of the graph
//    - returns the "last" edge in the abstract set
//        of all edges which have endpointVert as an endpoint 
//        If endpointVert is not an endpoint of any edge, returns
//        the nil edge.
Edge Graph::LastAdjacentEdge(Vertex endpointVert)
{
   VertexNode* vert1 = endpointVert.VPtr(); 
   if (vert1->departingEdges == NULL)
      return Edge(); 
   else if (vert1->departingEdges->source == vert1)
      return Edge(vert1->departingEdges->prevSourceEdge); 
   else   // vert1->departingEdges->target == vert1
      return Edge(vert1->departingEdges->prevTargetEdge); 
}
      


// NextAdjacentEdge
//    - parameters : currentEdge - an edge in the graph
//                 : endpointVert - an endpoint of currentEdge 
//    - return value : an edge of the graph
//    - returns the edge "after" currentEdge in the abstract 
//        set of all edges that have the vertex endpointVert 
//        as an endpoint. If this is the last edge in the set 
//        described above, returns the nil edge.
Edge Graph::NextAdjacentEdge(Edge currentEdge, Vertex endpointVert)
{
   VertexNode* vert1 = endpointVert.VPtr(); 
   EdgeNode* edge1 = currentEdge.EPtr(); 
   EdgeNode* possibleNextEdge; 
   
   if (edge1->source == vert1)
      possibleNextEdge = edge1->nextSourceEdge; 
   else if (edge1->target == vert1)
      possibleNextEdge = edge1->nextTargetEdge; 
   else // vertex not endpoint of edge
   {
      cout << "ERROR!!!! " << endl; 
      return Edge(); 
   }

   if (possibleNextEdge == vert1->departingEdges)
      return Edge(); 
   else
      return Edge(possibleNextEdge); 
}


// PrevAdjacentEdge
//    - parameters : currentEdge - an edge in the graph
//                 : endpointVert - an endpoint of currentEdge 
//    - return value : an edge of the graph
//    - returns the edge "before" currentEdge in the abstract 
//        set of all edges that have the vertex endpointVert 
//        as an endpoint. If this is the first edge in the set 
//        described above, returns the nil edge.
Edge Graph::PrevAdjacentEdge(Edge currentEdge, Vertex endpointVert)
{
   VertexNode* vert1 = endpointVert.VPtr(); 
   EdgeNode* edge1 = currentEdge.EPtr(); 
   EdgeNode* possiblePrevEdge; 
   
   if (edge1->source == vert1)
      possiblePrevEdge = edge1->prevSourceEdge; 
   else if (edge1->target == vert1)
      possiblePrevEdge = edge1->prevTargetEdge; 
   else // vertex not endpoint of edge
   {
      cout << "ERROR!!!! " << endl; 
      return Edge(); 
   }

   if (edge1 == vert1->departingEdges)
      return Edge(); 
   else
      return Edge(possiblePrevEdge); 
}


// *************** Mark processing *********************


//      ---------- Vertex marks

// GetVertexMark
//    - parameters : markVert - vertex with mark to read 
//    - return value : integer flag
//    - returns the mark value of the vertex markVert
int Graph::GetVertexMark(Vertex markVert)
{
   return (markVert.VPtr()->vertexMark);
}



// SetVertexMark
//    - parameters : markVert - vertex to be marked 
//                 : markToAssign - mark to assign to vertex
//    - sets the mark of vertex markVert to be equal to markToAssign
void Graph::SetVertexMark(Vertex markVert, int markToAssign)
{
   markVert.VPtr()->vertexMark = markToAssign; 
}


// ClearVertexMarks
//    - sets all vertex mark fields to 0
void Graph::ClearVertexMarks()
{
   VertexNode* nodePtr = vHead;
   if (nodePtr != NULL)   // if we have some vertices
   {
      while (nodePtr->nextVertex != vHead)
      {
         nodePtr->vertexMark = 0;
         nodePtr = nodePtr->nextVertex;
      }
      nodePtr->vertexMark = 0;
   }
}



//      ---------- Edge Marks

// GetEdgeMark
//    - parameters : markEdge - edge with mark to read
//    - return value : integer flag
//    - returns the mark value of the edge markEdge
int Graph::GetEdgeMark(Edge markEdge)
{
   return (markEdge.EPtr()->edgeMark);
}



// SetEdgeMark
//    - parameters : markEdge - edge to be marked
//                 : markToAssign - mark to assign to edge
//    - sets the mark of edge markEdge to be equal to markToAssign
void Graph::SetEdgeMark(Edge markEdge, int markToAssign)
{
   markEdge.EPtr()->edgeMark = markToAssign; 
}



// ClearEdgeMarks
//    - sets all edge mark fields to 0
void Graph::ClearEdgeMarks()
{
   EdgeNode* nodePtr = eHead;
   if (nodePtr != NULL)   // if we have some edges 
   {
      while (nodePtr->nextEdge != eHead)
      {
         nodePtr->edgeMark = 0;
         nodePtr = nodePtr->nextEdge;
      }
      nodePtr->edgeMark = 0;
   }
}



// ****************** Queries ***********************

// IsEmpty
//    - return value : boolean integer
//    - returns 1 if the graph has no vertices or edges, and
int Graph::IsEmpty()
{
   return ((vHead == NULL) && (eHead == NULL));
}



// IsDirected
//    - return value : boolean integer
//    - returns 1 if the graph is directed, and 0 otherwis
int Graph::IsDirected()
{
   return isDirected;
}



// IsUndirected
//    - return value : boolean integer
//    - returns 1 if the graph is undirected, and 0 otherwise
int Graph::IsUndirected()
{
   return !isDirected; 
}



// IsNil
//    - parameters : queryVert
//    - return value : boolean integer
//    - returns 1 if queryVert is the nil vertex, and 0 otherwise
int Graph::IsNil(Vertex queryVert)
{
   return (queryVert.VPtr() == NULL);
}



// IsNil
//    - parameters : queryEdge
//    - return value : boolean integer
//    - returns 1 if queryEdge is the nil Edge, and 0 otherwise
int Graph::IsNil(Edge queryEdge)
{
   return (queryEdge.EPtr() == NULL); 
}




// **************** Protected Functions ***********************



// VertexKey
//    - parameters : infoVertex - the vertex whose key we want
//    - return value : integer which is a vertex key
//    - returns the vertex-to-information map key stored inside
int Graph::VertexKey(Vertex infoVertex)
{
   return infoVertex.VPtr()->vertexKey;
}


// EdgeKey
//    - parameters : infoEdge - the edge whose key we want
//    - return value : integer which is an edge key
//    - returns the edge-to-information map key stored inside
//        the edge
int Graph::EdgeKey(Edge infoEdge)
{
   return infoEdge.EPtr()->edgeKey;
}



// ****************** Copying helper functions ******************


// Copy
//    - parameters : origVal - previously allocated Graph object
//    - sets this object to be a copy of origVal; helper function
//         for the copy constructor and assignment operator
void Graph::Copy(const Graph& origVal)
{
   // arrays to map index keys to pointers to the VertexNode
   //   and EdgeNode objects in the new graph. This will make  
   //   setting the pointer fields of those new graph nodes much
   //   easier.  
   Array<VertexNode*> vArray(1, origVal.vertexKeyCounter);
 
   int i;
   for (i = 1; i<=origVal.vertexKeyCounter; i++)
      vArray[i] = NULL; 
   Array<EdgeNode*> eArray(1, origVal.edgeKeyCounter);
   for (i = 1; i<=origVal.edgeKeyCounter; i++)
      eArray[i] = NULL; 

   // copy the vertex list 
   CopyVertexNodes(origVal, vArray); 
   // copy the edge list
   CopyEdgeNodes(origVal, eArray);

   // correctly set the departing/entering edge list pointers in 
   //    the new graph's vertices 
   CopyVertexConnections(origVal, eArray); 
   // correctly set the source/target vertex pointers and the 
   //   source/target edge list pointers in the new graph's edges 
   CopyEdgeConnections(origVal, vArray, eArray); 
   
   isDirected = origVal.isDirected;
}


// CopyVertexNodes
//    - parameters : origVal - previously allocated Graph object
//                 : vArray - array mapping vertex keys to 
//                       VertexNode pointers
//    - correctly creates a copy of the VertexNode list of origVal  
//         and stores it as the VertexNode list of this object.
//         The pointers to EdgeNodes are not set here, but the rest
//         of the VertexNode fields and all other Graph fields that
//         are VertexNode-related will be correctly set (i.e. size
//         and "maximum key value so far").
void Graph::CopyVertexNodes(const Graph& origVal, 
				Array<VertexNode*>& vArray)
{
   int stillVerticesToCopy = 1; 

   vSize = origVal.vSize; 
   if (vSize == 0)
      vHead = NULL; 
   else
   {
      vHead = new VertexNode(*(origVal.vHead)); 
      vArray[vHead->vertexKey] = vHead; 
      
      VertexNode *oldTrav = origVal.vHead; 
      VertexNode *newTrav = vHead; 
      if (oldTrav->nextVertex == origVal.vHead)
         stillVerticesToCopy = 0; 
      while (stillVerticesToCopy)
      {
         oldTrav = oldTrav->nextVertex; 
         newTrav->nextVertex = new VertexNode(*oldTrav); 
         newTrav->nextVertex->prevVertex = newTrav; 
         newTrav = newTrav->nextVertex; 
         newTrav->nextVertex = vHead; 
         vHead->prevVertex = newTrav;
         
         vArray[newTrav->vertexKey] = newTrav; 
         if (oldTrav->nextVertex == origVal.vHead)
            stillVerticesToCopy = 0; 
      }
      vertexKeyCounter = origVal.vertexKeyCounter;
   }
}


// CopyEdgeNodes
//    - parameters : origVal - previously allocated Graph object
//                 : eArray - array mapping edge keys to EdgeNode 
//                       pointers
//    - correctly creates a copy of the EdgeNode list of origVal  
//         and stores it as the EdgeNode list of this object.
//         The only pointers set here are the ones to the previous
//         and next EdgeNode in the main edge list. In addition, all 
//         other Graph fields that are EdgeNode-related will also be 
//         correctly set (i.e. size and "maximum key value so far").
void Graph::CopyEdgeNodes(const Graph& origVal, 
                                Array<EdgeNode*>& eArray)
{
   int stillEdgesToCopy = 1; 

   eSize = origVal.eSize; 
   if (eSize == 0)
      eHead = NULL; 
   else
   {
      eHead = new EdgeNode(*(origVal.eHead)); 
      eArray[eHead->edgeKey] = eHead; 
      
      EdgeNode *oldTrav = origVal.eHead; 
      EdgeNode *newTrav = eHead; 
      if (oldTrav->nextEdge == origVal.eHead)
         stillEdgesToCopy = 0; 
      while (stillEdgesToCopy)
      {
         oldTrav = oldTrav->nextEdge; 
         newTrav->nextEdge = new EdgeNode(*oldTrav); 
         newTrav->nextEdge->prevEdge = newTrav; 
         newTrav = newTrav->nextEdge; 
         newTrav->nextEdge = eHead; 
         eHead->prevEdge = newTrav;
         
         eArray[newTrav->edgeKey] = newTrav; 
         if (oldTrav->nextEdge == origVal.eHead)
            stillEdgesToCopy = 0; 
      }
      edgeKeyCounter = origVal.edgeKeyCounter;
   }
}


// CopyVertexConnections
//    - parameters : origVal - previously allocated Graph object
//                 : eArray - array mapping edge keys to EdgeNode
//                       pointers
//    - correctly reconstructs in this object (the new Graph) the 
//         connections between the VertexNode objects and the EdgeNode 
//         objects which are the heads of the entering and departing
//         edge lists of those VertexNode objects. The object origVal
//         (the old Graph) is used as a guide to do this, and the
//         array eArray is used to quickly obtain a desired EdgeNode, 
//         given its key 
void Graph::CopyVertexConnections(const Graph& origVal, 
			            const Array<EdgeNode*>& eArray)
{
   int stillVerticesToSet = 1; 
   VertexNode *oldTrav = origVal.vHead;
   VertexNode *newTrav = vHead; 
   if (newTrav == NULL)
      stillVerticesToSet = 0; 
   while (stillVerticesToSet)
   {
      if (oldTrav->departingEdges == NULL)
         newTrav->departingEdges = NULL; 
      else
         newTrav->departingEdges = eArray[oldTrav->departingEdges->edgeKey]; 
      if (oldTrav->enteringEdges == NULL)
         newTrav->enteringEdges = NULL; 
      else
         newTrav->enteringEdges = eArray[oldTrav->enteringEdges->edgeKey];
      newTrav = newTrav->nextVertex; 
      oldTrav = oldTrav->nextVertex; 
      if (newTrav==vHead)
         stillVerticesToSet = 0; 
   }
}



// CopyEdgeConnections
//    - parameters : origVal - previously allocated Graph object
//                 : vArray - array mapping vertex keys to 
//                       VertexNode pointers 
//                 : eArray - array mapping edge keys to edge
//                       pointers
//    - correctly reconstructs in this object (the new Graph) the 
//         connections between the EdgeNode objects and 
//            1) the VertexNode objects which are its source and target
//            2) the EdgeNode objects which are its neighbors in the
//                 departing edge list of some VertexNode and the entering 
//                 edge list of some VertexNodes
//         The object origVal (the old Graph) is used as a guide to do 
//         this, and the arrays vArray and eArray are used to quickly 
//         obtain a desired VertexNode or EdgeNode, given its key
void Graph::CopyEdgeConnections(const Graph& origVal, 
			const Array<VertexNode*>& vArray, 
			const Array<EdgeNode*>& eArray)
{
   int stillEdgesToSet = 1; 
   EdgeNode *oldTrav = origVal.eHead; 
   EdgeNode *newTrav = eHead;
   if (newTrav == NULL)
      stillEdgesToSet = 0; 
   while (stillEdgesToSet)
   {
      newTrav->source = vArray[oldTrav->source->vertexKey];
      newTrav->target = vArray[oldTrav->target->vertexKey];
      newTrav->prevSourceEdge = eArray[oldTrav->prevSourceEdge->edgeKey];
      newTrav->nextSourceEdge = eArray[oldTrav->nextSourceEdge->edgeKey];
      newTrav->prevTargetEdge = eArray[oldTrav->prevTargetEdge->edgeKey];
      newTrav->nextTargetEdge = eArray[oldTrav->nextTargetEdge->edgeKey];
   
      newTrav = newTrav->nextEdge;
      oldTrav = oldTrav->nextEdge;

      if (newTrav == eHead)
         stillEdgesToSet = 0;  
   }
}



// ************** Vertex addition helper functions ***************


// InsertEdgeIntoDirected
//    - parameters : insEdge - pointer to EdgeNode being inserted  
//                               into graph
//    - inserts insEdge into the departing edge list of its 
//         source vertex, and into the entering edge list of 
//         its target vertex 
void Graph::InsertEdgeIntoDirected(EdgeNode* insEdge)
{
   VertexNode* source = insEdge->source;
   VertexNode* target = insEdge->target;


   // Step 1 : Insert insEdge into source's departing edges list

   // if there are no entering edges, new edge is the only edge
   if (source->departingEdges == NULL)
      source->departingEdges = insEdge;
   else  // else insert new edge into doubly and circularly linked list
   {
      insEdge->prevSourceEdge = source->departingEdges->prevSourceEdge;
      insEdge->nextSourceEdge = source->departingEdges;
      source->departingEdges->prevSourceEdge->nextSourceEdge = insEdge;
      source->departingEdges->prevSourceEdge = insEdge;
   }
   (source->numDepartEdges)++;



   // Step 2 : Insert insEdge into target's entering edges list

   // if there are no entering edges, new edge is the only edge
   if (target->enteringEdges == NULL)
      target->enteringEdges = insEdge;
   else  // else insert new edge into doubly and circularly linked list 
   {
      insEdge->prevTargetEdge = target->enteringEdges->prevTargetEdge;
      insEdge->nextTargetEdge = target->enteringEdges;
      target->enteringEdges->prevTargetEdge->nextTargetEdge = insEdge;
      target->enteringEdges->prevTargetEdge = insEdge;
   }
   (target->numEnterEdges)++;
}




// InsertEdgeIntoUndirected
//    - parameters : insEdge - pointer to EdgeNode being inserted 
//                                into graph
//    - inserts insEdge into the edge lists of both of its endpoints 
void Graph::InsertEdgeIntoUndirected(EdgeNode* insEdge)
{
   // In an undirected graph, all the edges are listed in a vertex's
   //  "departing edges" list and no edges are listed in a vertex's
   //  "entering edges" list; however, the edge nodes themselves still
   //  point to two endpoints, so one is named "source" and one is named
   //  "target", though from the abstract point of view, the edge's two
   //  endpoints are just "endpoint1" and "endpoint2"
   VertexNode* endpoint1 = insEdge->source;
   VertexNode* endpoint2 = insEdge->target;


   // Step 1 : insert insEdge into endpoint1's departing edges list

   // if there are no adjacent edges, new edge is the only edge 
   if (endpoint1->departingEdges == NULL)
      endpoint1->departingEdges = insEdge;
   else  // else insert into doubly and circularly linked list
   {
      // endpoint1 is the "source" vertex for this edge, simply because
      // it happened to be listed first in the "InsertEdge" function
      // call. But, conceptually, there *is* no "source vertex", there is
      // just an "endpoint1" --  because this is an undirected edge.

      // **** Pointer Assignment #1
      insEdge->nextSourceEdge = endpoint1->departingEdges;

      // Since this graph is undirected, all of a vertex's edges are
      // on its "departing" edges list. Therefore, all the edges which 
      // had that given vertex as its "first" endpoint, AND all the edges 
      // which had that given vertex as its "second" endpoint, are ALL on 
      // that vertex's departing edge list. This means that some edges on a 
      // vertex's departing edge list (again, only for undirected graphs) 
      // point to that vertex with their "source" pointers, and other edges 
      // on that vertex's departing edge list point to that vertex with 
      // their "target" pointers.

      // If the first node in the current list sees endpoint1 as its
      // "first" or "source" endpoint, then it will be connected to the 
      // last vertex in the list with its source list pointers and so it 
      // is those source list pointers we must read and assign to.
      if (endpoint1->departingEdges->source == endpoint1)
      {
         // **** Pointer Assignments #2 and #3 -- possibility 1
         insEdge->prevSourceEdge = endpoint1->departingEdges->prevSourceEdge;
         endpoint1->departingEdges->prevSourceEdge = insEdge;
      }
      // Otherwise, the first node in the current list sees endpoint1
      //  as its "second" or "target" endpoint and it will be connected
      //  to its list neighbors via its target list pointers
      else    // then endpoint1->departingEdges->target == endpoint1 
      {
         // **** Pointer Assignments #2 and #3 - possibility 2
         insEdge->prevSourceEdge = endpoint1->departingEdges->prevTargetEdge;
         endpoint1->departingEdges->prevTargetEdge = insEdge;
      }

      // Likewise, we don't know whether the *last* edge in endpoint1's
      //  edge list thinks of endpoint1 as its "source" or "target" 
      //  endpoint 
      if (insEdge->prevSourceEdge->source == endpoint1 )
         // **** Pointer Assignment #4 - possibility 1
         insEdge->prevSourceEdge->nextSourceEdge = insEdge;
      else    // insEdge->prevSourceEdge->target == endpoint1
         // **** Pointer Assignment #4 - possibility 2
         insEdge->prevSourceEdge->nextTargetEdge = insEdge;
   }
   (endpoint1->numDepartEdges)++;


   // Step 2 : insert insEdge into endpoint2's departing edges list

   // if there are no adjacent edges, then new edge is the only one 
   if (endpoint2->departingEdges == NULL)
      endpoint2->departingEdges = insEdge;
   else // insert into doubly and circularly linked list
   {

      // **** Pointer Assignment #1
      insEdge->nextTargetEdge = endpoint2->departingEdges;


      // If the first node in the current list sees endpoint2 as its
      // "first" or "source" endpoint, then it will be connected to the
      // last vertex in the list with its source list pointers and so it
      // is those source list pointers we must read and assign to.
      if (endpoint2->departingEdges->source == endpoint2)
      {
         // **** Pointer Assignments #2 and #3 -- possibility 1
         insEdge->prevTargetEdge = endpoint2->departingEdges->prevSourceEdge;
         endpoint2->departingEdges->prevSourceEdge = insEdge;
      }
      // Otherwise, the first node in the current list sees endpoint2
      //  as its "second" or "target" endpoint and it will be connected
      //  to its list neighbors via its target list pointers
      else      // then endpoint2->departingEdges->target == endpoint2
      {
         // **** Pointer Assignments #2 and #3 - possibility 2
         insEdge->prevTargetEdge = endpoint2->departingEdges->prevTargetEdge;
         endpoint2->departingEdges->prevTargetEdge = insEdge;
      }

      // Likewise, we don't know whether the *last* edge in endpoint2's
      //  edge list thinks of endpoint2 as its "source" or "target"
      //  endpoint
      if (insEdge->prevTargetEdge->source == endpoint2)
         // **** Pointer Assignment #4 - possibility 1
         insEdge->prevTargetEdge->nextSourceEdge = insEdge;
      else    // insEdge->prevSourceEdge->target == endpoint2
         // **** Pointer Assignment #4 - possibility 2
         insEdge->prevTargetEdge->nextTargetEdge = insEdge;
   }
   (endpoint2->numDepartEdges)++;
}




// RemoveEdgeFromDirected
//    - parameters : deleteEdgeNode - pointer to edge node that
//                      is to be deleted
//    - extracts deleteEdgeNode from the list of edges departing 
//         from its source vertex, and also from the list of edges
//         entering its target vertex
void Graph::RemoveEdgeFromDirected(EdgeNode* deleteEdgeNode)
{
   // Step 1: Remove deleteEdgeNode from source's departing edges list

   // if this is the last edge left in the list of its source vertex 
   if (deleteEdgeNode == deleteEdgeNode->nextSourceEdge)
      deleteEdgeNode->source->departingEdges = NULL;
   else  // else there is more than one vertex in this edge list
   {
      deleteEdgeNode->nextSourceEdge->prevSourceEdge = 
			         deleteEdgeNode->prevSourceEdge;
      deleteEdgeNode->prevSourceEdge->nextSourceEdge = 
                                 deleteEdgeNode->nextSourceEdge;
  
      // if the source vertex's "departing edges" pointer points
      //   to this edge, point it to the next edge instead
      if (deleteEdgeNode->source->departingEdges == deleteEdgeNode)
         deleteEdgeNode->source->departingEdges = 
                                        deleteEdgeNode->nextSourceEdge;
   }
   (deleteEdgeNode->source->numDepartEdges)--; 


   // Step 2: Remove deleteEdgeNode from target's entering edges list

   // if this is the last edge left in the list of its target vertex
   if (deleteEdgeNode == deleteEdgeNode->nextTargetEdge)
      deleteEdgeNode->target->enteringEdges = NULL;
   else  // else there is more than one vertex in this edge list
   {
      deleteEdgeNode->nextTargetEdge->prevTargetEdge = 
				     deleteEdgeNode->prevTargetEdge;
      deleteEdgeNode->prevTargetEdge->nextTargetEdge = 
				     deleteEdgeNode->nextTargetEdge;
  
      // if the target vertex's "entering edges" pointer points
      //   to this edge, point it to the next edge instead 
      if (deleteEdgeNode->target->enteringEdges == deleteEdgeNode)
         deleteEdgeNode->target->enteringEdges = 
                                      deleteEdgeNode->nextTargetEdge;
   }
   (deleteEdgeNode->target->numEnterEdges)--;
}




// RemoveEdgeFromUndirected
//    - parameters : deleteEdgeNode - pointer to edge node that
//                      is to be deleted
//    - extracts deleteEdgeNode from the edge list of deleteEdgeNode's
//         first endpoint, and also extracts it from the edge list of 
//         its second endpoint
void Graph::RemoveEdgeFromUndirected(EdgeNode* deleteEdgeNode)
{
   // In an undirected graph, the "source" and "target" vertices
   //   are really just "endpoint1" and "endpoint2" since the edge
   //   has no direction
   VertexNode* endpoint1 = deleteEdgeNode->source;
   VertexNode* endpoint2 = deleteEdgeNode->target;


   // Step 1: Remove deleteEdgeNode from endpoint1's edge list

   // if this is the last edge left in the list of endpoint1 
   if (deleteEdgeNode == deleteEdgeNode->nextSourceEdge)
      endpoint1->departingEdges = NULL;
   else  // else there is more than one vertex in this edge list
   {
      // the edge after this one in endpoint1's edge list might see 
      //    endpoint1 as its "source" OR as its "target" 
      if (deleteEdgeNode->nextSourceEdge->source == endpoint1)
         deleteEdgeNode->nextSourceEdge->prevSourceEdge = 
                                 deleteEdgeNode->prevSourceEdge;
      else  // deleteEdgeNode->nextSourceEdge->target == endpoint1
         deleteEdgeNode->nextSourceEdge->prevTargetEdge = 
				 deleteEdgeNode->prevSourceEdge;

      // the edge before this one in endpoint1's edge list might see 
      //    endpoint1 as its "source" OR as its "target" 
      if (deleteEdgeNode->prevSourceEdge->source == endpoint1)
         deleteEdgeNode->prevSourceEdge->nextSourceEdge = 
                                 deleteEdgeNode->nextSourceEdge;
      else   // deleteEdgeNode->prevSourceEdge->target == endpoint1
         deleteEdgeNode->prevSourceEdge->nextTargetEdge = 
				 deleteEdgeNode->nextSourceEdge; 
 
 
      // if endpoint1's "departing edges" pointer points
      //   to this edge, point it to the next edge instead
      if (endpoint1->departingEdges == deleteEdgeNode)
         endpoint1->departingEdges = deleteEdgeNode->nextSourceEdge;
   }
   (endpoint1->numDepartEdges)--; 


   // Step 2: Remove deleteEdgeNode from endpoint2's edge list 

   // if this is the last edge left in the list of its target vertex
   if (deleteEdgeNode == deleteEdgeNode->nextTargetEdge)
      deleteEdgeNode->target->enteringEdges = NULL;
   else  // else there is more than one vertex in this edge list
   {
      // the edge after this one in endpoint2's edge list might see 
      //    endpoint2 as its "source" OR as its "target" 
      if (deleteEdgeNode->nextTargetEdge->source == endpoint2)
         deleteEdgeNode->nextTargetEdge->prevSourceEdge =
                                 deleteEdgeNode->prevTargetEdge;
      else  // deleteEdgeNode->nextTargetEdge->target == endpoint2
         deleteEdgeNode->nextTargetEdge->prevTargetEdge = 
                                 deleteEdgeNode->prevTargetEdge;

      // the edge before this one in endpoint2's edge list might see 
      //    endpoint2 as its "source" OR as its "target" 
      if (deleteEdgeNode->prevTargetEdge->source == endpoint2)
         deleteEdgeNode->prevTargetEdge->nextSourceEdge =
                                 deleteEdgeNode->nextTargetEdge;
      else   // deleteEdgeNode->prevTargetEdge->target == endpoint2
         deleteEdgeNode->prevTargetEdge->nextTargetEdge =   
                                 deleteEdgeNode->nextTargetEdge;


      // if endpoint2's "departing edges" pointer points
      //   to this edge, point it to the next edge instead 
      if (endpoint2->enteringEdges == deleteEdgeNode)
         endpoint2->enteringEdges = deleteEdgeNode->nextTargetEdge;
   }
   (endpoint2->numEnterEdges)--;
}

// ****************************************************
// *                                                  *
// *  infograph.cpp                                   *
// *                                                  *
// *  Implementation for a parameterized graph class  *
// *                                                  *
// *  Written 11 Nov 2003 by Seunghoon Kim            *
// *                                                  *
// *  Inspiration for this graph class drawn from     *
// *   the publicly posted interface of the LEDA      *
// *   library: http://www.mpi-sb.mpg.de/LEDA/        *
// *                                                  *
// *  Directed flag added to constructor              *
// *    3 August 1999 by Jason Zych                   *
// ****************************************************

#include "infograph.h"


// InsertVertexAfter
//    - parameters : position - vertex reference
//		     info - information record for the new vertex
//    - return value : the new vertex
//    - adds a new vertex to graph after the vertex reference and returns it
template <class Vtype, class Etype>
Vertex InfoGraph<Vtype, Etype>::InsertVertexAfter(Vertex position, Vtype info)
{
   Vertex newVert = Graph::InsertVertexAfter(position); 
   vertexInfo[VertexKey(newVert)] = info;
   return newVert;
}

// InsertVertexBefore
//    - parameters : position - vertex reference
//		     info - information record for the new vertex
//    - return value : the new vertex
//    - adds a new vertex to graph before the vertex reference and returns it
template <class Vtype, class Etype>
Vertex InfoGraph<Vtype, Etype>::InsertVertexBefore(Vertex position, Vtype info)
{
   Vertex newVert = Graph::InsertVertexBefore(position); 
   vertexInfo[VertexKey(newVert)] = info;
   return newVert;
}

// InsertEdgeAfter
//    - parameters : sourceVert - source vertex of new edge
//                 : targetVert - target vertex of new edge
//                 : sourcePosition - source edge reference
//                 : targetPosition - target edge reference
//                 : listPosition - edge list reference
//		   : info - information record for the new edge
//    - return value : the new edge 
//    - adds a new edge to the graph between the parameter vertices, after the parameter edges
//         returns that edge
template <class Vtype, class Etype>
Edge InfoGraph<Vtype, Etype>::InsertEdgeAfter(Vertex sourceVert, Vertex targetVert, Edge sourcePosition, Edge targetPosition, Edge listPosition, Etype info)
{
   Edge newEdge = Graph::InsertEdgeAfter(sourceVert, targetVert, sourcePosition, targetPosition, listPosition); 
   edgeInfo[EdgeKey(newEdge)] = info;
   return newEdge;
}

// InsertEdgeBefore
//    - parameters : sourceVert - source vertex of new edge
//                 : targetVert - target vertex of new edge
//                 : sourcePosition - source edge reference
//                 : targetPosition - target edge reference
//                 : listPosition - edge list reference
//		   : info - information record for the new edge
//    - return value : the new edge 
//    - adds a new edge to the graph between the parameter vertices, before the parameter edges
//         returns that edge
template <class Vtype, class Etype>
Edge InfoGraph<Vtype, Etype>::InsertEdgeBefore(Vertex sourceVert, Vertex targetVert, Edge sourcePosition, Edge targetPosition, Edge listPosition, Etype info)
{
   Edge newEdge = Graph::InsertEdgeBefore(sourceVert, targetVert, sourcePosition, targetPosition, listPosition); 
   edgeInfo[EdgeKey(newEdge)] = info;
   return newEdge;
}


// InfoGraph
//    - default constructor
//    - initializes object to default values
template <class Vtype, class Etype>
InfoGraph<Vtype, Etype>::InfoGraph(int isDirectedFlag) : Graph(isDirectedFlag)
{
   vertexInfo.SetBounds(1, 100); 
   edgeInfo.SetBounds(1, 100); 
}


// InsertVertex
//    - parameters : vertValue - value to be attached to new vertex
//    - return value : the new vertex
//    - adds a new vertex to graph, assigns the vertex the value
//         vertValue, and returns the vertex
template <class Vtype, class Etype>
Vertex InfoGraph<Vtype, Etype>::InsertVertex(Vtype vertValue)
{
   Vertex v1 = Graph::InsertVertex(); 
   vertexInfo[VertexKey(v1)] = vertValue;
   return v1;
}


// InsertEdge
//    - parameters : sourceVert - source vertex of new edge
//                 : targetVert - target vertex of new edge
//                 : edgeValue - value to be attached to new edge
//    - return value : the new edge
//    - adds a new edge to the graph between the parameter vertices,
//         assigns the edge the value edgeValue, and returns that edge
template <class Vtype, class Etype>
Edge InfoGraph<Vtype, Etype>::InsertEdge(Vertex sourceVert, 
					Vertex targetVert, Etype edgeValue)
{
   Edge e1 = Graph::InsertEdge(sourceVert, targetVert); 
   edgeInfo[EdgeKey(e1)] = edgeValue;
   return e1; 
}



// VertexInfo
//    - parameters : infoVert - vertex whose value we want
//    - return type : a vertex information value
//    - returns the information variable stored in this vertex
template <class Vtype, class Etype>
Vtype InfoGraph<Vtype, Etype>::VertexInfo(Vertex infoVert)
{
   return vertexInfo[VertexKey(infoVert)]; 

}


// EdgeInfo
//    - parameters : infoEdge - edge whose value we want
//    - return type : an edge information value
//    - returns the information variable stored in this edge
template <class Vtype, class Etype>
Etype InfoGraph<Vtype, Etype>::EdgeInfo(Edge infoEdge)
{
   return edgeInfo[EdgeKey(infoEdge)];
}


// VertexAssign
//    - parameters : infoVert - vertex at which we will store info
//                 : vertValue - information value for the vertex
//    - stores the value vertValue at the vertex infoVert, writing
//       over whatever information used to be at infoVert, if any
template <class Vtype, class Etype>
void InfoGraph<Vtype, Etype>::VertexAssign(Vertex infoVert, Vtype vertValue)
{
   vertexInfo[VertexKey(infoVert)] = vertValue;
}


// EdgeAssign
//    - parameters : infoEdge - edge at which we will store info
//                 : edgeValue - information value for the edge
//    - stores the value edgeValue at the edge infoEdge, writing
//       over whatever information used to be at infoEdge, if any
template <class Vtype, class Etype>
void InfoGraph<Vtype, Etype>::EdgeAssign(Edge infoEdge, Etype edgeValue)
{
   edgeInfo[EdgeKey(infoEdge)] = edgeValue; 
}

// *******************************************************
// *                                                     *
// *  patricia.h                                         *
// *                                                     *
// *  Interface for a Patricia tree                      *
// *                                                     *
// *   Written December 2003 by Seunghoon Kim            *
// *                                                     *
// *******************************************************

#ifndef _PATRICIATREE_H
#define _PATRICIATREE_H

#include "string.h"
#include "array.h"
#include "asserts.h"
class PatriciaTreeNode;

class PatriciaTree
{
public:

   // PatriciaTree
   //   - default constructor
   //   - initializes object to default values
   PatriciaTree();


   // PatriciaTree
   //   - copy constructor
   //   - parameters : origVal - previously allocated PatriciaTree object
   //   - initializes object to be a copy of origVal
   PatriciaTree(const PatriciaTree& origVal);


   // ~PatriciaTree
   //   - destructor
   //   - deletes dynamically allocated memory
   ~PatriciaTree();


   // operator=
   //   - parameters : origVal - previously allocated PatriciaTree object
   //   - return value : reference to PatriciaTreeNode
   //   - sets object to be a copy of origVal
   PatriciaTree& operator=(const PatriciaTree& origVal);


   // insert
   //   - parameters : newString - new key to add
   //   - inserts newString into the PatriciaTree
   void insert(String newString);


   // find
   //   - parameters : searchString - key value to search for
   //   - return value : boolean "succesful or not"
   //   - returns 0 if string is not in the tree; else returns 1
   int find(String searchString);


   // remove
   //   - parameters : removeString - key to be removed
   //   - removes removeString if it is in the PatriciaTree
   void remove(String removeString);


   // Print
   //   - prints the info of the PatriciaTree
   void print();


private:
   class PatriciaTreeNode
   {
   public:

      // PatriciaTreeNode
      //   - default constructor
      //   - initializes node to default value as internal array node
      PatriciaTreeNode()
      {
         nodeLevel = 0;
         nodeType = 1;   // arrayNode
         numChildren = 0;
         ArrayPtr = new Array<PatriciaTreeNode*>(1, 27);
         ArrayPtr->Initialize(NULL);
      }


      // PatriciaTreeNode
      //   - constructor
      //   - parameters : initString - string key initializer
      //                : theNodeType - int defining if node is leaf or not
      //   - initializes node to be tree leaf or array node
      PatriciaTreeNode(String initString, int theNodeType)
      {
         nodeLevel = 0;
         nodeType = theNodeType;
         numChildren = 0;
         if (nodeType == 1)
         {
            ArrayPtr = new Array<PatriciaTreeNode*>(1, 27);
            ArrayPtr->Initialize(NULL);
         }
         else
            ArrayPtr = new Array<PatriciaTreeNode*>();
         key = initString;
      }


      // ~PatriciaTreeNode
      //   - destructor
      //   - deletes dynamically allocated memory
      ~PatriciaTreeNode()
      {
         delete ArrayPtr;
      }

      int nodeLevel;				// level of the node
      int nodeType;				// type of the node
      Array<PatriciaTreeNode*>* ArrayPtr;	// ptr to array in array nodes
      String key;				// string key
      int numChildren;				// number of children
   };



   PatriciaTreeNode* root;	// pointer to root node of patricia tree


   // Copy
   //   - parameters : origVal - pointer to a patricia tree structure
   //   - return value : PatriciaTreeNode pointer
   //   - returns a pointer to a copy of the parameter tree
   PatriciaTreeNode* Copy(PatriciaTreeNode*& origVal);


   // Clear
   //   - parameter : origVal - pointer to a patricia tree structure
   //   - clears the entire tree
   void Clear(PatriciaTreeNode*& origVal);


   // ascIndex
   //   - parameters : indexChar - a character for which we want an index
   //   - return value : integer index
   //   - returns the index from 1 - 27 that represents this character
   int ascIndex(char indexChar);


   // insert
   //   - parameters : newString - new key value to add
   //                : nodePtr - pointer to the node currently being examined
   //                : prevLevel - level of the node that contains nodePtr
   //   - inserts newString into the PatriciaTree as a leaf node
   void insert(String newString, PatriciaTreeNode*& nodePtr, int prevLevel);


   // find
   //   - parameters : searchString - key value to search for
   //                : nodePtr - pointer to the node currently being examined
   //   - return value : boolean "succesful or not"
   //   - returns 0 if string is not in tree; else returns 1
   int find(String searchString, PatriciaTreeNode*& nodePtr);


   // remove
   //   - parameters : removeString - key value to be removed
   //                : nodePtr - pointer to the node currently being examined
   //                : prevLevel - level of the node that contains nodePtr
   //   - removes removeString from the PatriciaTree
   void remove(String removeString, PatriciaTreeNode*& nodePtr, int prevLevel);


   // print
   //   - prints the info of the PatriciaTree
   void print(PatriciaTreeNode*& nodePtr);


};
#endif

// *******************************************************
// *                                                     *
// *  patricia.cpp                                       *
// *                                                     *
// *  Implementation for a Patricia tree	         *
// *                                                     *
// *   Written December 2003 by Seunghoon Kim            *
// *                                                     *
// *******************************************************

#include <stddef.h>
#include "patricia.h"
#include "asserts.h"

// PatriciaTree
//   - default constructor
//   - initializes object to default values
PatriciaTree::PatriciaTree()
{
  root = NULL;
}


// PatriciaTree
//   - copy constructor
//   - parameters : origVal - previously allocated PatriciaTree object
//   - initializes object to be a copy of origVal
PatriciaTree::PatriciaTree(const PatriciaTree& origVal)
{
  root = Copy(origVal.root);
}


// ~PatriciaTree
//   - destructor
//   - deletes dynamically allocated memory
PatriciaTree::~PatriciaTree()
{
  Clear(root);
}


// operator=
//   - parameters : origVal - previously allocated PatriciaTree object
//   - return value : reference to PatriciaTreeNode
//   - sets object to be a copy of origVal
PatriciaTree& PatriciaTree::operator=(const PatriciaTree& origVal)
{
  Clear(root);
  root = Copy(origVal.root);
  return *this;
}


// insert
//   - parameters : newString - new key to add
//   - inserts newString into the PatriciaTree
void PatriciaTree::insert(String newString)
{
  insert(newString, root, -1);
}


// find
//   - parameters : searchString - key value to search for
//   - return value : boolean "succesful or not"
//   - returns 0 if string is not in the tree; else returns 1
int PatriciaTree::find(String searchString)
{
  return find(searchString, root);
}


// remove
//   - parameters : removeString - key to be removed
//   - removes removeString if it is in the PatriciaTree
void PatriciaTree::remove(String removeString)
{
  if (find(removeString))
    remove(removeString, root, -1);
}


// print
//   - prints the info of the PatriciaTree
void PatriciaTree::print()
{
  print(root);
}


// Copy
//   - parameters : origVal - pointer to a patricia tree structure
//   - return value : PatriciaTreeNode pointer
//   - returns a pointer to a copy of the parameter tree
PatriciaTree::PatriciaTreeNode* PatriciaTree::Copy(PatriciaTreeNode*& origVal)
{
  PatriciaTreeNode* retVal = new PatriciaTreeNode(origVal->key,
						  origVal->nodeType);
  //if we reached an array
  if (origVal->nodeType == 1)
    {
      for (int i=1; i<=27; ++i)
	{
	  if ((*(origVal->ArrayPtr))[i] != NULL)
            (*(retVal->ArrayPtr))[i] = Copy((*(origVal->ArrayPtr))[i]);
	}
      retVal->nodeLevel = origVal->nodeLevel;
      retVal->numChildren=origVal->numChildren;
    }
  else	//leaf node, all leaf nodes have zero children
    {
      retVal->nodeLevel = origVal->nodeLevel;
      retVal->numChildren=0;
    }

  return retVal;
}


// Clear
//   - parameter : origVal - pointer to a patricia tree structure
//   - clears the entire tree
void PatriciaTree::Clear(PatriciaTreeNode*& origVal)
{
  if (origVal->nodeType == 1)	//array node
    {
      for (int i=1; i<27; i++)
	if ((*(origVal->ArrayPtr))[i] != NULL)
	  {
            Clear((*(origVal->ArrayPtr))[i]);
            ((*(origVal->ArrayPtr))[i]) = NULL;
	  }
    }

  delete origVal;
}


// ascIndex
//   - parameters : indexChar - a character for which we want an index
//   - return value : integer index
//   - returns the index from 1 - 27 that represents this character
int PatriciaTree::ascIndex(char indexChar)
{
  if ((indexChar>='a') && (indexChar<='z'))   // lowercase letter
    return (indexChar-'a'+1);
  else if (indexChar == 0)  // null character
    return 27;
  else
    Assert(0, "Bizarre character in string!");
}


// insert
//   - parameters : newString - new key value to add
//                : nodePtr - pointer to the node currently being examined
//                : prevLevel - level of the node that contains nodePtr
//   - inserts newString into the PatriciaTree as a leaf node
void PatriciaTree::insert(String newString, PatriciaTreeNode*& nodePtr,
			  int prevLevel)
{
  if (nodePtr == NULL)		//NULL case
    {
      nodePtr = new PatriciaTreeNode(newString, 0);
      nodePtr->nodeLevel = newString.length()+1;
      return;
    }

  else if (nodePtr->nodeType == 0)		//leaf case
    {
      if (nodePtr->key == newString)
	{
	  cout << "key already exists!" << endl;
	  return;
	}
      else
	{
	  int i;
	  for (i = prevLevel+1; i<=nodePtr->nodeLevel-2; i++)
	    //check nodePtr's key to see if it matches newString
	    {
	      if ((i>=newString.length()) || ((nodePtr->key)[i] != newString[i]))
		{
		  String tempKey = nodePtr->key;
		  PatriciaTreeNode* tempNode = new PatriciaTreeNode(tempKey, 0);

		  tempNode->nodeLevel = nodePtr->nodeLevel;
		  nodePtr->nodeLevel = i;
		  nodePtr->numChildren = 2;
		  nodePtr->nodeType = 1;
		  nodePtr->ArrayPtr->SetBounds(1, 27);
		  nodePtr->ArrayPtr->Initialize(NULL);

		  if((i-(prevLevel+1))==0)
		    nodePtr->key=NULL;

		  else
		      nodePtr->key = tempKey.substring(prevLevel+1, i-(prevLevel+1));

		  (*(nodePtr->ArrayPtr))[ascIndex(tempKey[i])] = tempNode;
		  if (i>=newString.length())
		    insert(newString, (*(nodePtr->ArrayPtr))[27],
			   nodePtr->nodeLevel);
		  else
		    insert(newString,
			   (*(nodePtr->ArrayPtr))[ascIndex(newString[i])],
			   nodePtr->nodeLevel);
		  return;
		}
	    }
	  String tempKey = nodePtr->key;
	  PatriciaTreeNode* tempNode = new PatriciaTreeNode(tempKey, 0);

	  tempNode->nodeLevel = nodePtr->nodeLevel;
	  nodePtr->nodeLevel = i;
	  tempNode->numChildren = nodePtr->numChildren;
	  nodePtr->numChildren = 2;
	  nodePtr->nodeType = 1;
	  nodePtr->ArrayPtr->SetBounds(1, 27);
	  nodePtr->ArrayPtr->Initialize(NULL);

	  if((i-(prevLevel+1))==0)
	    nodePtr->key=NULL;
	  else
	    nodePtr->key = tempKey.substring(prevLevel+1, i-(prevLevel+1));
	  (*(nodePtr->ArrayPtr))[27] = tempNode;
	  insert(newString, (*(nodePtr->ArrayPtr))[ascIndex(newString[i])],
		 nodePtr->nodeLevel);
	}
    }

  else		//non-NULL array node case
    {
      	//where nodePtr's level is the correct level to insert
      if ((nodePtr->nodeLevel == newString.length())&&(nodePtr->key==NULL))
	{
	  nodePtr->numChildren++;
	  insert(newString, (*(nodePtr->ArrayPtr))[27], nodePtr->nodeLevel);
	}

      else if (prevLevel+1 == nodePtr->nodeLevel)
	//where nodePtr has NOT skipped levels
	{
	  PatriciaTreeNode* insNode =
	    (*(nodePtr->ArrayPtr))[ascIndex(newString[nodePtr->nodeLevel])];
	  insert(newString, insNode, nodePtr->nodeLevel);
	  (*(nodePtr->ArrayPtr))[ascIndex(newString[nodePtr->nodeLevel])] = insNode;
	  if (insNode->nodeType == 0)
            (nodePtr->numChildren)++;
	  return;
	}

      else		//where nodePtr HAS skipped levels
	{
	  int k = 1;
	  for (int i = prevLevel+1; i<=nodePtr->nodeLevel-1; i++)
	    //check nodePtr's key to see if it matches newString
	    {
	      if ((i>=newString.length()) || (nodePtr->key[k-1] != newString[i]))
		{
		  PatriciaTreeNode* tempNode = new PatriciaTreeNode();
		  String tempKey = nodePtr->key;

		  tempNode->nodeLevel = nodePtr->nodeLevel;
		  nodePtr->nodeLevel = i;
		  tempNode->numChildren = nodePtr->numChildren;
		  nodePtr->numChildren = 2;
		  for (int j=1; j<=27; j++)
		    {
		      (*(tempNode->ArrayPtr))[j] = (*(nodePtr->ArrayPtr))[j];
		      (*(nodePtr->ArrayPtr))[j] = NULL;
		    }
		  if (tempKey.length()>1)
		    {
		      nodePtr->key = tempKey.substring(0, k-1);
		      tempNode->key = tempKey.substring(k,tempKey.length()-k);
		    }
		  else
		    nodePtr->key = tempNode->key = NULL;
		  (*(nodePtr->ArrayPtr))[ascIndex(tempKey[k-1])] = tempNode;
		  if (i>=newString.length())
		    insert(newString, (*(nodePtr->ArrayPtr))[27],
			   nodePtr->nodeLevel);
		  else
		    insert(newString,
			   (*(nodePtr->ArrayPtr))[ascIndex(newString[i])],
			   nodePtr->nodeLevel);
		  return;
		}
	      k++;
	    }
	  int charIndex = (nodePtr->key).length()+prevLevel+1;
	  nodePtr->numChildren++;
	  insert(newString, (*(nodePtr->ArrayPtr))[ascIndex(newString[charIndex])],
		 nodePtr->nodeLevel);
	}
    }
}


// find
//   - parameters : searchString - key value to search for
//                : nodePtr - pointer to the node currently being examined
//   - return value : boolean "succesful or not"
//   - returns 0 if string is not in tree; else returns 1
int PatriciaTree::find(String searchString, PatriciaTreeNode*& nodePtr)
{
  if (nodePtr == NULL)		//NULL case
    return 0;
  else if (nodePtr->nodeType == 0)		//leaf case
    {
      if (nodePtr->key == searchString)
	return 1;
      else
	return 0;
    }
  else		//non-NULL array node case
    {
      if (nodePtr->nodeLevel == searchString.length())
	//search string would be in NULL cell if it exists
	return find(searchString, (*(nodePtr->ArrayPtr))[27]);
      else if (nodePtr->nodeLevel > searchString.length())
	//search string got skipped over so it doesn't exist
	return 0;
      else
	//keep looking through array
	return find (searchString,
		     (*(nodePtr->ArrayPtr))[ascIndex(searchString[nodePtr->nodeLevel])]);
    }
}


// remove
//   - parameters : removeString - key value to be removed
//                : nodePtr - pointer to the node currently being examined
//                : prevLevel - level of the node that contains nodePtr
//   - removes removeString from the PatriciaTree
void PatriciaTree::remove(String removeString, PatriciaTreeNode*& nodePtr,
			  int prevLevel)
{
  //base case
  if (nodePtr->nodeType == 0)
    {
      delete nodePtr;
      return;
    }
  else
    {
      PatriciaTreeNode* nodeToRemoveFrom =
	(*(nodePtr->ArrayPtr))[ascIndex(removeString[nodePtr->nodeLevel])];
      int isLeaf = 0;

      //if the node we wish to remove is a leaf
      if (nodeToRemoveFrom->nodeType == 0)
	isLeaf = 1;

      remove(removeString,
	     (*(nodePtr->ArrayPtr))[ascIndex(removeString[nodePtr->nodeLevel])],
	     nodePtr->nodeLevel);

      //if it is a leaf we set the array cell equal to NULL
      if (isLeaf)
	{
	  (*(nodePtr->ArrayPtr))[ascIndex(removeString[nodePtr->nodeLevel])] =
	    NULL;
	}
    }

  PatriciaTreeNode* childNode =
    (*(nodePtr->ArrayPtr))[ascIndex(removeString[nodePtr->nodeLevel])];
    //tempNode is child of nodePtr

  //if the deleted node is now NULL, we decrease the total number of non-NULL cells in the array
  if (childNode == NULL)
    {
      nodePtr->numChildren--;

      //if the root now only has one child
      if ((nodePtr == root) && (nodePtr->numChildren == 1))
	{
	  for (int i=1; i<=27; i++)
            if ((*(nodePtr->ArrayPtr))[i] != NULL)
	      childNode = (*(nodePtr->ArrayPtr))[i];

	  if (childNode->nodeType == 0)		//root's only child is a leaf
	    {
	      delete nodePtr;
	      root = childNode;
	    }
	  else
	    {
	      // int to char conversion
	      int index;
	      for (int i=1; i<=27; i++)
		if ((*(nodePtr->ArrayPtr))[i] != NULL)
                  index = i;
	      char indexChar = char(index-1+'a');

	      if (childNode->key == NULL)
		childNode->key = String(&indexChar);
	      else
		childNode->key = String(&indexChar) + childNode->key;

	      delete nodePtr;
	      root = childNode;
	    }
	}
    }

  //if number of non-NULL cells is now equal to 1
  else if (childNode->numChildren == 1)
    {
      PatriciaTreeNode* grandChild;
      for (int i=1; i<=27; i++)
	if ((*(childNode->ArrayPtr))[i] != NULL)
	  grandChild = (*(childNode->ArrayPtr))[i];

      //have "grandpa" point at "grandchild"
      if (grandChild->nodeType == 0)		//nodePtr's grandchild is a leaf
	{
	  delete childNode;
	  (*(nodePtr->ArrayPtr))[ascIndex(removeString[nodePtr->nodeLevel])] = grandChild;
	}

    }

  //if the number of non-NULL cells is greater than one, array is fine so simply return
  else if (childNode->numChildren > 1)
    return;

}


// print
//   - prints the info of the PatriciaTree
void PatriciaTree::print(PatriciaTreeNode*& nodePtr)
{
  if (nodePtr != NULL)
    {
      //if we reach an internal array
      if(nodePtr->nodeType == 1)
	{
	  cout <<"Internal node at level "<<nodePtr->nodeLevel<<endl;

	  int i;
	  for (i=1; i<=27; i++)
	    {
	      if((*(nodePtr->ArrayPtr))[i]!=NULL)
		{
		  cout<<"The ";
		  if (i==27)
		     cout << "null-character";
		  else
		     cout << char(i-1+'a');
		  cout <<" subtree pointed to by level "<<nodePtr->nodeLevel
		       <<" is as follows: "<<endl;
		  print((*(nodePtr->ArrayPtr))[i]);
		  cout<<"The ";
		  if (i==27)
		     cout << "null-character";
		  else
		     cout << char(i-1+'a');
		  cout <<" subtree pointed to by level "<<nodePtr->nodeLevel
		       <<" has been explored. "<<endl;
		}
	    }

	   if(nodePtr->key == NULL)
	     cout<<"There is no skipped substring for this node. "<<endl;
	   else if(nodePtr->key!=NULL)
	     cout<<"skipped substring for this node is: "<<nodePtr->key<<endl;

	}

      //if we reach a leaf
      if (nodePtr->nodeType == 0)
	{
	  cout << "Leaf node at level "<< nodePtr->nodeLevel <<" has string "
	       <<nodePtr->key << endl;
	  return;
	}

   } } 

// *******************************************************
// *                                                     *
// *  rbtree.h                                           *
// *                                                     *
// *  Interface for a red and black tree                 *
// *                                                     *
// *   Written November 2003 by Seunghoon Kim            *
// *                                                     *
// *******************************************************

#ifndef RBTREE_H
#define RBTREE_H

#include <stddef.h>
#include "utility225.h"


// **************************************************************
// *                                                            *
// *  Class : rb_tree                                           *
// *                                                            *
// *  The interface class for the red and black implementation  * 
// *                                                            *
// **************************************************************
template <class Ktype, class Etype>
class rb_tree
{
public:

   // rb_tree
   //    - default constructor 
   //    - initializes tree to be empty
   rb_tree();

   // insert
   //    - parameters : insElem - value to be inserted
   //    - return value : none
   //    - inserts insElem into tree (does nothing if key is
   //         already there
   void insert(const pair<Ktype, Etype>& insElem)
   {
      insert(insElem, root(), headerNode);
   }

   // erase
   //    - parameters : key - key to the element to be erased
   //    - erases element pointed by remKey from tree if it is in tree
   void erase(const Ktype& key)
   {
      erase(key, root(), headerNode);
   }

   // preorder
   //    - prints tree in preorder format
   void preorder()
   {
      preorder(root());
   }
   
private:
// *********************************************
// *                                           *
// *  rbtree<>::rb_tree_node                   *
// *                                           *
// *  The node class for our red & black tree. * 
// *                                           *
// *********************************************
   class rb_tree_node
   {
   public:
   
      // rb_tree_node
      //    - default constructor
      //    - initializes node to default values
      rb_tree_node() : element(), left(NULL), right(NULL), parent(NULL),
                                                            color(0) {}
      
      
      // rb_tree_node
      //    - constructor
      //    - parameters : elem - initialization element
      //                 : leftPtr - initialization left pointer
      //                 : rightPtr - initialization right pointer
      //                 : color - initialization color
      //    - initializes node to parameter values
      rb_tree_node(pair<Ktype, Etype> elem, rb_tree_node* leftPtr = NULL,
            rb_tree_node* rightPtr = NULL, rb_tree_node* parentPtr = NULL,
                                                         int clr = 0) :
            element(elem), left(leftPtr), right(rightPtr), parent(),
                                                      color(clr) {}
      
      
      pair<Ktype, Etype> element;
      rb_tree_node* left;
      rb_tree_node* right;
      rb_tree_node* parent;
      int color;
      
   };    // end rb_tree_node class
   
   
 // ************* Member data for Red-Black tree
 
 rb_tree_node* headerNode;
 int treeSize;
 
   
   
 // ************* Node access functions
 
   // root
   //    - return value : a reference to an RB tree node pointer
   //    - returns a refernce to root of RB tree
   rb_tree_node*& root() const { return headerNode->parent; }
   
      
   // key
   //    - parameters : value - a value pair we want the key of
   //    - return type : a key value
   //    - value stores a (Key, Info) pair. This function
   //       will extract the key from this pair and return it.
   Ktype key(const pair<Ktype, Etype> value) const { return value.first; }


   // insert
   //    - parameters : insElem - element to be inserted
   //                 : TN - a treenode pointer
   //                 : parentOfTN - the parent of the node TN
   //    recursively inserts insElem into tree if insElem does not already
   //       exists
   void insert(const pair<Ktype, Etype>& insElem, rb_tree_node*& TN,
                                             rb_tree_node* parentOfTN);
   
   
   // remove
   //    - paremeters : remElem - element to be removed
   //                 : TN - a treenode pointer
   //    - recursively removes remElem from tree if exists
   void erase(const Ktype& remElem, rb_tree_node*& TN,
                                          rb_tree_node* parentOfTN);
   
   
   // preorder
   //    - helper function for preorder()
   void preorder(rb_tree_node* TN) const;
   
   
   
 // ************* Additional helper functions
   
   
   // right_rotation
   //    - parameters : k2 - root of subtree
   //    - performs a single right rotation on k2
   void right_rotation(rb_tree_node* k2);
   
   
   // left_rotation
   //    - parameters : k2 - root of subtree
   //    - performs a single left rotation on k2
   void left_rotation(rb_tree_node* k2);
   
};


#endif

// *******************************************************
// *                                                     *
// *  rbtree.cpp                                         *
// *                                                     *
// *  Implementation for a red and black tree	         *
// *                                                     *
// *   Written November 2003 by Seunghoon Kim            *
// *                                                     *
// *******************************************************
#include <stdlib.h>
#include "rbtree.h"
#include <iostream.h>



// rb_tree
//    - default constructor
//    - initializes tree to be empty
template <class Ktype, class Etype>
rb_tree<Ktype, Etype>::rb_tree() : treeSize(0), headerNode(new rb_tree_node())
{
   headerNode->left = headerNode->right = headerNode;
}



// insert
//    - parameters : insElem - element to be inserted
//                 : TN - a treenode pointer
//                 : parentOfTN - the parent of the node TN
//    recursively inserts insElem into tree if insElem does not already
//       exists
template <class Ktype, class Etype>
void rb_tree<Ktype, Etype>::insert(const pair<Ktype, Etype>& insElem,
                           rb_tree_node*& TN, rb_tree_node* parentOfTN)
{
   if (TN == NULL)
   {
      TN = new rb_tree_node();
      TN->element = insElem;
      TN->color = 0; 
      TN->parent = parentOfTN;
      
      if ((treeSize==0) || (key(insElem) < key(headerNode->left->element)))
         headerNode->left = TN;
      if ((treeSize==0) || (key(insElem) > key(headerNode->right->element)))
         headerNode->right = TN;
      
      
      rb_tree_node* X = TN;
      treeSize++;
      
      while ((X != root() ) && (X->parent->color == 0) )
      {
         if ((key(X->element) < key(X->parent->parent->element) ) &&
            (!(X->parent->parent->right) ||
            (X->parent->parent->right->color == 1) ) )				// case 1
         {
            if ((key(X->element) < key(X->parent->element) ) &&
               (key(X->parent->element) > key(X->parent->parent->element) ) )
            {
               rb_tree_node* tmp_X = X->parent;
               right_rotation(X->parent);
               X = tmp_X;
            }
            else if ((key(X->element) > key(X->parent->element) ) &&
               (key(X->parent->element) < key(X->parent->parent->element) ) )
            {
               rb_tree_node* tmp_X = X->parent;
               left_rotation(X->parent);
               X = tmp_X;
            }
            
            
            X->parent->parent->color = 0;
            X->parent->color = 1;
            right_rotation(X->parent->parent);
         }
         
         else if ((key(X->element) > key(X->parent->parent->element) ) &&
            (!(X->parent->parent->left) ||
            (X->parent->parent->left->color == 1) ) )
         {
            if ((key(X->element) < key(X->parent->element) ) &&
               (key(X->parent->element) > key(X->parent->parent->element) ) )
            {
               rb_tree_node* tmp_X = X->parent;
               right_rotation(X->parent);
               X = tmp_X;
            }
            else if ((key(X->element) > key(X->parent->element) ) &&
               (key(X->parent->element) < key(X->parent->parent->element) ) )
            {
               rb_tree_node* tmp_X = X->parent;
               left_rotation(X->parent);
               X = tmp_X;
            }
            
            
            X->parent->parent->color = 0;
            X->parent->color = 1;
            left_rotation(X->parent->parent);
         }
         
         else													// Case 2
         {
            X->parent->parent->left->color = 1;
            X->parent->parent->right->color = 1;
            X->parent->parent->color = 0;
            X = X->parent->parent;
         }

      } 
      

      root()->color = 1;
   
   }
   
   else if (key(insElem) < key(TN->element) )
   {														      // insert in the left subtree
      insert(insElem, TN->left, TN);
   }
   else if (key(insElem) > key(TN->element) )
   {																// insert in the right subtree
      insert(insElem, TN->right, TN);
   }
   // else key(insElem) == key(TN->element)
   else
   {
      return;
   } // BST insert end
}


// remove
//    - paremeters : remElem - element to be removed
//                 : TN - a treenode pointer
//    - recursively removes remElem from tree if exists
template <class Ktype, class Etype>
void rb_tree<Ktype, Etype>::erase(const Ktype& remElem, rb_tree_node*& TN,
                                                rb_tree_node* parentOfTN)
{
   rb_tree_node *tmp_cell, *tmpCellParent, *newCell, *X;
   
   if (TN == NULL)
      return;
   else if (remElem < key(TN->element) )
   {
      erase(remElem, TN->left, TN);
   }
   else if (remElem > key(TN->element) )
   {
      erase(remElem, TN->right, TN);
   }
   else
   {
      if ((TN->left != NULL) && (TN->right != NULL) )
      {

         tmp_cell = TN->right;
         while (tmp_cell->left != NULL)
            tmp_cell = tmp_cell->left;
         
         tmpCellParent = tmp_cell->parent;
         newCell = new rb_tree_node();
         
         newCell->right = tmp_cell->right;
         newCell->left = tmp_cell->left;
         newCell->element = tmp_cell->element;
         newCell->color = tmp_cell->color;
         newCell->parent = tmp_cell->parent;
         
         if (tmpCellParent->left == tmp_cell)
            tmpCellParent->left = newCell;
         else if (tmpCellParent->right == tmp_cell)
            tmpCellParent->right = newCell;
         
         tmp_cell->right = TN->right;
         tmp_cell->parent = TN->parent;
         tmp_cell->left = TN->left;
         tmp_cell->color = TN->color;
         
         delete TN;
         TN = tmp_cell;
         TN->left->parent = TN;
         TN->right->parent = TN;
         
         erase(key(TN->element), TN->right, TN);
         
         X = NULL;
      }
      
      else 
      {
         treeSize--;
         
         if (TN == headerNode->left)
            headerNode->left = TN->parent;
         if (TN == headerNode->right)
            headerNode->right = TN->parent;
         if (treeSize == 1)
         {
            if ((TN->parent == headerNode) && (TN->left) )
               headerNode->right = headerNode->left = TN->left;
            else if ((TN->parent == headerNode) && (TN->right) )
               headerNode->right = headerNode->left = TN->right;
            else
               headerNode->right = headerNode->left = root();
         }
         
         if ((TN->left == NULL) && (TN->right == NULL) ) 
         {
            X = TN;
            
            if ((X->color == 0) || (X == root() ) )
            {
               delete X;
               X = NULL;
            }
            else
               X->left = X;
            
            TN = NULL;
            
         }
         else if ((TN->left == NULL) && (TN->right != NULL) )
         {
            TN = TN->right;
            TN->parent = parentOfTN;
            
            X = TN;
         }
         else if ((TN->left != NULL) && (TN->right == NULL) )
         {
            TN = TN->left;
            TN->parent = parentOfTN;
            
            X = TN;
         }
      }
      
      if (X == NULL)
         return;
      else
      {
         while ((X != root() ) && (X->color == 1) )
         {
																					// Case 1
            if ((key(X->element) < key(X->parent->element) ) &&
               (X->parent->right->color == 0) )
            {
               X->parent->right->color = 1;
               X->parent->color = 0;
               left_rotation(X->parent);
            }
            else if ((key(X->element) > key(X->parent->element) ) &&
               (X->parent->left->color == 0) )
            {
               X->parent->left->color = 1;
               X->parent->color = 0;
               right_rotation(X->parent);
            }
																					//  Case 2a
            if ((key(X->element) < key(X->parent->element) ) &&
               (X->parent->right->left) &&
               (X->parent->right->left->color == 0) &&
               (!(X->parent->right->right) ||
               (X->parent->right->right->color == 1) ) )
            {
               X->parent->right->color = 0;
               X->parent->right->left->color = 1;
               right_rotation(X->parent->right);
            }
            else if ((key(X->element) > key(X->parent->element) ) &&
               (X->parent->left->right) &&
               (X->parent->left->right->color == 0) &&
               (!(X->parent->left->left) ||
               (X->parent->left->left->color == 1) ) )
            {
               X->parent->left->color = 0;
               X->parent->left->right->color = 1;
               left_rotation(X->parent->left);
            }
               
            if ((key(X->element) < key(X->parent->element) ) &&										// Case 2b
               (X->parent->right->right) &&
               (X->parent->right->right->color == 0) )
            {
               X->parent->right->right->color = 1;
               X->parent->right->color = X->parent->color;
               X->parent->color = 1;
               left_rotation(X->parent);
               
               if (X->left == X)
                  delete X;
               
               X = root();
            }
            else if ((key(X->element) > key(X->parent->element) ) &&
               (X->parent->left->left) &&
               (X->parent->left->left->color == 0) )
            {
               X->parent->left->left->color = 1;
               X->parent->left->color = X->parent->color;
               X->parent->color = 1;
               right_rotation(X->parent);
               
               if (X->left == X)
                  delete X;
               
               X = root();  
            }
            
            else																	// Case 3
            {
               if (key(X->element) < key(X->parent->element) )
                  X->parent->right->color = 0;
               else if (key(X->element) > key(X->parent->element) )
                  X->parent->left->color = 0;
               
               rb_tree_node* tmp_X = X;
               X = X->parent;
               
               if (tmp_X->left == tmp_X)
                  delete tmp_X;
            }
         
            
         }
         X->color = 1;
      
      }
   
   }
}


// preorder
//    - helper function for preorder()
template <class Ktype, class Etype>
void rb_tree<Ktype, Etype>::preorder(rb_tree_node* TN) const
{
   if (TN)
   {
      cout << key(TN->element) << endl;
      preorder(TN->left);
      preorder(TN->right);
   }
}




// right_rotation
//    - parameters : k2 - root of subtree
//    - performs a single right rotation on k2
template <class Ktype, class Etype>
void rb_tree<Ktype, Etype>::right_rotation(rb_tree_node* k2)
{
   rb_tree_node *k1 = k2->left;
   rb_tree_node *parentOfk2 = k2->parent;
   
   // rotate k1 up to "root" and k2 down to right
   k2->left = k1->right;
   if (k2->left != NULL)
     k2->left->parent = k2;
   
   k1->right = k2;
   k2->parent = k1;
   
   k1->parent = parentOfk2;
   
   // correct root
   if (k2 == root())
      root() = k1;
   else
   {
      // correct child pointer
      if (key(k1->element) < key(k1->parent->element) )
         k1->parent->left = k1;
      else
         k1->parent->right = k1;
   }
}


// left_rotation
//    - parameters : k2 - root of subtree
//    - performs a single left rotation on k2
template <class Ktype, class Etype>
void rb_tree<Ktype, Etype>::left_rotation(rb_tree_node* k2)
{
   rb_tree_node *k1 = k2->right;
   rb_tree_node *parentOfk2 = k2->parent;
   
   // rotate k1 up to "root" and k2 down to left
   k2->right = k1->left;
   if (k2->right != NULL)
     k2->right->parent = k2;
   k1->left = k2;
   k2->parent = k1;
   
   k1->parent = parentOfk2;
   
   // correct root
   if (k2 == root())
      root() = k1;
   else
   {
      // correct child pointer
      if (key(k1->element) < key(k1->parent->element) )
         k1->parent->left = k1;
      else
         k1->parent->right = k1;
   }
}