[Bug c++/22227] g++ 4.0.0 has issues with the typedef of reference

jcurran2 at uiuc dot edu gcc-bugzilla@gcc.gnu.org
Wed Jun 29 05:37:00 GMT 2005


------- Additional Comments From jcurran2 at uiuc dot edu  2005-06-29 05:36 -------
Subject: Re:  g++ 4.0.0 has issues
 with the typedef of reference

Well it compiles perfectly fine on a Sun Solaris Machine with 
Sun Studio 9 installed that has the Sun CC compiler.  Also It 
was written by a Computer Science Professor at the University 
of Illinois at Urbana-Champaign, a school ranked in the list 
of the top 5 in the nation for Computer Science.  What does 
not look like C++ to you, 

This is a templated overloaded operator*() that has a return 
type as a const reference to the element type.  Returns by 
const_reference the cell storing the element to which this 
const_iterator points to.  

I dont know if you are confusing this with Java or not but 
there is at least one thing that distinguishes Java from C++ 
which is the fact that C++ supports Operator Overloading 
while Java does not and this function you looked at is an 
Overloaded Operator.

Take a look at the attached files I sent you that are used to 
for an Machine Problem on implementing a De La Briandais Tree
(A trie implementation).  The problem occurs when compiling 
list225.cpp with g++ but it has no problems compiling with 
the Sun CC compiler.  Take a look at the error messages the 
pop up when compiling with g++ 4.0.0 then compare to Sun CC 
if you have access to the Sun CC compiler and then you should 
see what I am talking about.

Jeremy Curran   
// *****************************************************************
// *                                                               *
// *  list225.cpp                                                  *
// *                                                               *
// *  This file provides the implementation for our abbreviated    *
// *  version of the STL list class. The code is not               *
// *  optimized to the extent that a "real" STL                    *
// *  implementation would be, but it has much of the same         *
// *  functionality, and has more understandable source code.      *
// *                                                               *
// *  Written July 1999 by Jason Zych                              *
// *    - September 2003 : "typename" added to iterator            *
// *                                functions in .cpp              *
// *                     : old MP function stubs and #include      *
// *                          of vector225.h removed               *
// *                     : listNode permissions fixed in .h        *   
// *                     : #ifndef macro changed in .h             *  
// *                                                               *
// *   - September 2004 : changes made by Jason Zych               *
// *                     - standard header includes fixed          *
// *                     - iterator implementation moved to .cpp   *
// *                     - enhanced description of this class in   *
// *                           file header and other comments      *
// *                                                               *   
// *****************************************************************



#include <iostream>
#include <cstddef>
#include "asserts.h"
#include "list225.h"


// ***********************************************************
// *        member functions for the iterator class          *
// ***********************************************************


// iterator
//    - constructor
//    - initializes this iterator to point to NULL
template <class Etype>
list<Etype>::iterator::iterator() 
{ 
   ptr = NULL;
}



// operator*
//    - return type : a reference to the element type
//    - returns by reference the cell storing the element
//         to which this iterator points.  There is no
//          error checking done to ensure that this is
//          a legal cell on which to perform this operation.
template <class Etype>
typename list<Etype>::reference list<Etype>::iterator::operator*() 
{ 
   return ptr->element;  
}


// operator->
//    - return type : a pointer to the element type
//    - returns a pointer to the cell storing the element
//         to which this iterator points.  There is no
//          error checking done to ensure that this is
//          a legal cell on which to perform this operation.
template <class Etype>
typename list<Etype>::pointer list<Etype>::iterator::operator->()  
{ 
   return &(ptr->element); 
}



// operator++ (prefix version)
//    - return type : reference to an iterator
//    - moves this iterator one position forward in the
//          collection it points to, and then returns
//          this iterator after moving it. There is no
//          error checking done to ensure that this is
//          a legal position at which to perform this
//          operation.
template <class Etype>
typename list<Etype>::iterator& list<Etype>::iterator::operator++() 
{ 
   ptr = ptr->next;
   return *this; 
}



// operator-- (prefix version)
//    - return type: reference to an iterator
//    - moves this iterator one position backward in the
//          collection it points to, and then returns
//          this iterator after moving it. There is no
//          error checking done to ensure that this is
//          a legal position at which to perform this
//          operation.
template <class Etype>
typename list<Etype>::iterator& list<Etype>::iterator::operator--()  
{ 
   ptr = ptr->prev; 
   return *this; 
}



// operator++ (postfix version)
//    - parameters : ignore - argument always the integer 1, to
//                       distinguish this from prefix version
//    - return type : an iterator
//    - moves this iterator one position forward in the
//          collection it points to, and then returns an
//          iterator to the position this iterator pointed
//          to before this function was run. There is no
//          error checking done to ensure that this is a
//          legal position at which to perform this operation.
template <class Etype>
typename list<Etype>::iterator list<Etype>::iterator::operator++(int ignore)
{
   typename list<Etype>::iterator temp = *this;
   ptr = ptr->next;
   return temp;
}





// operator-- (postfix version)
//    - parameters : ignore - argument always the integer 1, to
//                       distinguish this from prefix version
//    - return type : an iterator
//    - moves this iterator one position backward in the
//          collection it points to, and then returns an
//          iterator to the position this iterator pointed
//          to before this function was run. There is no
//          error checking done to ensure that this is a
//          legal position at which to perform this operation.
template <class Etype>
typename list<Etype>::iterator list<Etype>::iterator::operator--(int ignore)
{
   typename list<Etype>::iterator temp = *this;
   ptr = ptr->prev;
   return temp;
}



// operator==
//    - parameters : origVal - previously created iterator
//    - return value : boolean integer
//    - returns 1 if this iterator and the parameter
//         iterator point to the same location, 0 else
template <class Etype>
int list<Etype>::iterator::operator==(
               typename const list<Etype>::iterator& origVal) const
{ 
   return (ptr == origVal.ptr); 
}


// operator!=
//    - parameters : origVal - previously created iterator
//    - return value : boolean integer
//    - returns 1 if this iterator and the parameter
//         iterator point different locations, 0 else
template <class Etype>
int list<Etype>::iterator::operator!=(
               typename const list<Etype>::iterator& origVal) const
{ 
   return (ptr != origVal.ptr); 
}



// iterator
//    - constructor
//    - parameters : assignPtr - a pointer to the same type
//           that this iterator points to
//    - initializes iterator to point to the same place as
//         the parameter pointer points to
template <class Etype>
list<Etype>::iterator::iterator(
                     typename list<Etype>::listNode* assignPtr) 
{ 
   ptr = assignPtr; 
}





// ***********************************************************
// *     member functions for the const_iterator class       *
// ***********************************************************


// const_iterator
//    - constructor
//    - initializes this const_iterator to point to NULL
template <class Etype>
list<Etype>::const_iterator::const_iterator() 
{ 
   ptr = NULL;
}



// const_iterator
//    - constructor
//    - parameters : theIter - an iterator
//    - initializes this const_iterator to point to the same
//           location as the parameter iterator
template <class Etype>
list<Etype>::const_iterator::const_iterator(
               typename const list<Etype>::iterator& theIter) 
{
   ptr = theIter.ptr;
}




// operator*
//    - return type : a const reference to the element type
//    - returns by const_reference the cell storing the element
//         to which this const_iterator points.  There is no
//          error checking done to ensure that this is
//          a legal cell on which to perform this operation.
template <class Etype>
typename list<Etype>::reference 
                    list<Etype>::const_iterator::operator*() const
{ 
   return ptr->element;  
}


// operator->
//    - return type : a const_pointer to the element type
//    - returns a const_pointer to the cell storing the element
//         to which this const_iterator points.  There is no
//          error checking done to ensure that this is
//          a legal cell on which to perform this operation.
template <class Etype>
typename list<Etype>::pointer 
                    list<Etype>::const_iterator::operator->() const 
{ 
   return &(ptr->element); 
}



// operator++ (prefix version)
//    - return type : reference to an const_iterator
//    - moves this const_iterator one position forward in the
//          collection it points to, and then returns
//          this const_iterator after moving it. There is no
//          error checking done to ensure that this is
//          a legal position at which to perform this
//          operation.
template <class Etype>
typename list<Etype>::const_iterator& 
                    list<Etype>::const_iterator::operator++() 
{ 
   ptr= ptr->next;
   return *this; 
}





// operator-- (prefix version)
//    - return type: reference to an const_iterator
//    - moves this const_iterator one position backward in the
//          collection it points to, and then returns
//          this const_iterator after moving it. There is no
//          error checking done to ensure that this is
//          a legal position at which to perform this
//          operation.
template <class Etype>
typename list<Etype>::const_iterator& 
                    list<Etype>::const_iterator::operator--()  
{ 
   ptr = ptr->prev; 
   return *this; 
}



// operator++ (postfix version)
//    - parameters : ignore - argument always the integer 1, to
//                       distinguish this from prefix version
//    - return type : an const_iterator
//    - moves this const_iterator one position forward in the
//          collection it points to, and then returns an
//          const_iterator to the position this iterator pointed
//          to before this function was run. There is no
//          error checking done to ensure that this is a
//          legal position at which to perform this operation.
template <class Etype>
typename list<Etype>::const_iterator 
                    list<Etype>::const_iterator::operator++(int ignore)
{
   typename list<Etype>::const_iterator temp = *this;
   ptr = ptr->next;
   return temp;
}





// operator-- (postfix version)
//    - parameters : ignore - argument always the integer 1, to
//                       distinguish this from prefix version
//    - return type : an const_iterator
//    - moves this const_iterator one position backward in the
//          collection it points to, and then returns an
//          const_iterator to the position this iterator pointed
//          to before this function was run. There is no
//          error checking done to ensure that this is a
//          legal position at which to perform this operation.
template <class Etype>
typename list<Etype>::const_iterator 
                    list<Etype>::const_iterator::operator--(int ignore)
{
   typename list<Etype>::const_iterator temp = *this;
   ptr = ptr->prev;
   return temp;
}



// operator==
//    - parameters : origVal - previously created const_iterator
//    - return value : boolean integer
//    - returns 1 if this const_iterator and the parameter
//         const_iterator point to the same location, 0 else
template <class Etype>
int list<Etype>::const_iterator::operator==(
               typename const list<Etype>::const_iterator& origVal) const
{ 
   return (ptr == origVal.ptr); 
}


// operator!=
//    - parameters : origVal - previously created const_iterator
//    - return value : boolean integer
//    - returns 1 if this const_iterator and the parameter
//         const_iterator point different locations, 0 else
template <class Etype>
int list<Etype>::const_iterator::operator!=(
               typename const list<Etype>::const_iterator& origVal) const
{ 
   return (ptr != origVal.ptr); 
}




// const_iterator
//    - constructor
//    - parameters : assignPtr - a const_pointer to the same type
//           that this const_iterator points to
//    - initializes const_iterator to point to the same place as
//         the parameter pointer points to
template <class Etype>
list<Etype>::const_iterator::const_iterator( 
                           typename list<Etype>::listNode* assignPtr)
{
   ptr = assignPtr;
}




// ***********************************************************
// *     member functions for the reverse_iterator class     * 
// ***********************************************************



// reverse_iterator
//    - constructor
//    - initializes this reverse_iterator to point to NULL
template <class Etype>
list<Etype>::reverse_iterator::reverse_iterator() : current()
{ 
   // initializer list used above; no code needed here
}



// operator*
//    - return type : a reference to the element type
//    - returns by reference the cell storing the element
//         to which this reverse_iterator points.  There is no
//          error checking done to ensure that this is
//          a legal cell on which to perform this operation.
template <class Etype>
typename list<Etype>::reference list<Etype>::reverse_iterator::operator*() 
{ 
   iterator temp = current;
   --temp;
   return *temp;
}


// operator->
//    - return type : a pointer to the element type
//    - returns a pointer to the cell storing the element
//         to which this reverse_iterator points.  There is no
//          error checking done to ensure that this is
//          a legal cell on which to perform this operation.
template <class Etype>
typename list<Etype>::pointer list<Etype>::reverse_iterator::operator->()  
{ 
   return &(this->operator*());
}



// operator++ (prefix version)
//    - return type : reference to an reverse_iterator
//    - moves this reverse_iterator one position forward in the
//          collection it points to, and then returns
//          this reverse_iterator after moving it. There is no
//          error checking done to ensure that this is
//          a legal position at which to perform this
//          operation.
template <class Etype>
typename list<Etype>::reverse_iterator& 
                    list<Etype>::reverse_iterator::operator++() 
{ 
   --current;
   return *this; 
}




// operator-- (prefix version)
//    - return type: reference to an reverse_iterator
//    - moves this reverse_iterator one position backward in the
//          collection it points to, and then returns
//          this reverse_iterator after moving it. There is no
//          error checking done to ensure that this is
//          a legal position at which to perform this
//          operation.
template <class Etype>
typename list<Etype>::reverse_iterator& 
                    list<Etype>::reverse_iterator::operator--()  
{ 
   ++current;
   return *this; 
}



// operator++ (postfix version)
//    - parameters : ignore - argument always the integer 1, to
//                       distinguish this from prefix version
//    - return type : an reverse_iterator
//    - moves this reverse_iterator one position forward in the
//          collection it points to, and then returns an
//          reverse_iterator to the position this iterator pointed
//          to before this function was run. There is no
//          error checking done to ensure that this is a
//          legal position at which to perform this operation.
template <class Etype>
typename list<Etype>::reverse_iterator 
                    list<Etype>::reverse_iterator::operator++(int ignore)
{
   typename list<Etype>::reverse_iterator temp = *this;
   --current;
   return temp;
}





// operator-- (postfix version)
//    - parameters : ignore - argument always the integer 1, to
//                       distinguish this from prefix version
//    - return type : an reverse_iterator
//    - moves this reverse_iterator one position backward in the
//          collection it points to, and then returns an
//          reverse_iterator to the position this iterator pointed
//          to before this function was run. There is no
//          error checking done to ensure that this is a
//          legal position at which to perform this operation.
template <class Etype>
typename list<Etype>::reverse_iterator 
                    list<Etype>::reverse_iterator::operator--(int ignore)
{
   typename list<Etype>::reverse_iterator temp = *this;
   ++current;
   return temp;
}



// operator==
//    - parameters : origVal - previously created reverse_iterator
//    - return value : boolean integer
//    - returns 1 if this reverse_iterator and the parameter
//         reverse_iterator point to the same location, 0 else
template <class Etype>
int list<Etype>::reverse_iterator::operator==(
               typename const list<Etype>::reverse_iterator& origVal) const
{ 
   return (current == origVal.current);
}


// operator!=
//    - parameters : origVal - previously created reverse_iterator
//    - return value : boolean integer
//    - returns 1 if this reverse_iterator and the parameter
//         reverse_iterator point different locations, 0 else
template <class Etype>
int list<Etype>::reverse_iterator::operator!=(
               typename const list<Etype>::reverse_iterator& origVal) const
{ 
   return (current != origVal.current); 
}




// reverse_iterator
//    - constructor
//    - parameters : assignIter - iterator to the same type of
//         data to which this reverse_iterator points
//    - initializes this reverse_iterator to point to the same
//       place that the parameter iterator points to
template <class Etype>
list<Etype>::reverse_iterator::reverse_iterator(
                             typename list<Etype>::iterator assignIter)
{
   current = assignIter;
}





// ***********************************************************
// *  member functions for the const_reverse_iterator class  *
// ***********************************************************



// const_reverse_iterator
//    - constructor
//    - initializes this const_reverse_iterator to point to NULL
template <class Etype>
list<Etype>::const_reverse_iterator::const_reverse_iterator() : current()
{ 
   // initializer list used above; no code needed here
}



// const_reverse_iterator
//    - constructor
//    - parameters : theIter - a reverse_iterator which points
//           to the same time as this const_reverse_iterator
//    - initializes this const_reverse_iterator to point to the
//        same place to which the parameter reverses_iterator
//        points
template <class Etype>
list<Etype>::const_reverse_iterator::const_reverse_iterator(
           typename const list<Etype>::reverse_iterator& theIter)
{
   current = theIter.current;
}




// operator*
//    - return type : a const_reference to the element type
//    - returns by const_reference the cell storing the element
//         to which this const_reverse_iterator points.  There is no
//          error checking done to ensure that this is a legal 
//          cell on which to perform this operation.
template <class Etype>
typename list<Etype>::const_reference 
                    list<Etype>::const_reverse_iterator::operator*() const
{ 
   iterator temp = current;
   --temp;
   return *temp;
}


// operator->
//    - return type : a const_pointer to the element type
//    - returns a const_pointer to the cell storing the element
//         to which this const_reverse_iterator points.  There is no
//          error checking done to ensure that this is
//          a legal cell on which to perform this operation.
template <class Etype>
typename list<Etype>::const_pointer 
                    list<Etype>::const_reverse_iterator::operator->() const 
{ 
   return &(this->operator*());
}



// operator++ (prefix version)
//    - return type : reference to an const_reverse_iterator
//    - moves this const_reverse_iterator one position forward in the
//          collection it points to, and then returns
//          this const_reverse_iterator after moving it. There is no
//          error checking done to ensure that this is
//          a legal position at which to perform this
//          operation.
template <class Etype>
typename list<Etype>::const_reverse_iterator& 
                    list<Etype>::const_reverse_iterator::operator++() 
{ 
   --current;
   return *this; 
}




// operator-- (prefix version)
//    - return type: reference to an const_reverse_iterator
//    - moves this const_reverse_iterator one position backward in the
//          collection it points to, and then returns
//          this const_reverse_iterator after moving it. There is no
//          error checking done to ensure that this is
//          a legal position at which to perform this
//          operation.
template <class Etype>
typename list<Etype>::const_reverse_iterator& 
                    list<Etype>::const_reverse_iterator::operator--()  
{ 
   ++current;
   return *this; 
}


// operator++ (postfix version)
//    - parameters : ignore - argument always the integer 1, to
//                       distinguish this from prefix version
//    - return type : an const_reverse_iterator
//    - moves this const_reverse_iterator one position forward in the
//          collection it points to, and then returns an
//          const_reverse_iterator to the position this iterator pointed
//          to before this function was run. There is no
//          error checking done to ensure that this is a
//          legal position at which to perform this operation.
template <class Etype>
typename list<Etype>::const_reverse_iterator 
                    list<Etype>::const_reverse_iterator::operator++(int ignore)
{
   typename list<Etype>::const_reverse_iterator temp = *this;
   --current;
   return temp;
}





// operator-- (postfix version)
//    - parameters : ignore - argument always the integer 1, to
//                       distinguish this from prefix version
//    - return type : an const_reverse_iterator
//    - moves this const_reverse_iterator one position backward in the
//          collection it points to, and then returns an
//          const_reverse_iterator to the position this iterator pointed
//          to before this function was run. There is no
//          error checking done to ensure that this is a
//          legal position at which to perform this operation.
template <class Etype>
typename list<Etype>::const_reverse_iterator 
                    list<Etype>::const_reverse_iterator::operator--(int ignore)
{
   typename list<Etype>::const_reverse_iterator temp = *this;
   ++current;
   return temp;
}


// operator==
//    - parameters : origVal - previously created const_reverse_iterator
//    - return value : boolean integer
//    - returns 1 if this const_reverse_iterator and the parameter
//         const_reverse_iterator point to the same location, 0 else
template <class Etype>
int list<Etype>::const_reverse_iterator::operator==(
           typename const list<Etype>::const_reverse_iterator& origVal) const
{ 
   return (current == origVal.current);
}


// operator!=
//    - parameters : origVal - previously created const_reverse_iterator
//    - return value : boolean integer
//    - returns 1 if this const_reverse_iterator and the parameter
//         const_reverse_iterator point different locations, 0 else
template <class Etype>
int list<Etype>::const_reverse_iterator::operator!=(
           typename const list<Etype>::const_reverse_iterator& origVal) const
{ 
   return (current != origVal.current); 
}




// ***********************************************************
// *         member functions for the list class             *
// ***********************************************************



// list
//    - default constructor
template <class Etype>
list<Etype>::list()
{
   headerNode = new listNode(); 
   headerNode->next = headerNode->prev = headerNode;
   listSize=0; 
}



// list
//    - constructor
//    - parameters : theListSize - number of elements in this list
//    - creates a list of listSize default elements
template <class Etype>
list<Etype>::list(int theListSize)
{
   headerNode = new listNode(); 
   listNode* temp = headerNode; 
   for (int i = 1; i <= theListSize; i++)
   { 
      temp->next = new listNode(); 
      temp->next->prev = temp; 
      temp = temp->next; 
   }
   temp->next = headerNode;
   headerNode->prev = temp;   
   listSize = theListSize; 
}



// list
//    - constructor
//    - parameters : theListSize - number of elements in this list
//    - creates a list of listSize elements each initialized to 
//           initElem
template <class Etype> 
list<Etype>::list(int theListSize, Etype initElem)
{
   headerNode = new listNode(); 
   listNode* temp = headerNode; 
   for (int i = 1; i <= theListSize; i++)
   { 
      temp->next = new listNode(); 
      temp->next->prev = temp; 
      temp = temp->next; 
      temp->element = initElem;
   }   
   temp->next = headerNode;
   headerNode->prev = temp;
   listSize = theListSize;
}





// list
//    - copy constructor
//    - parameters : origlist - a previously allocated list object
//    - initializes the list to be a copy of origlist
template <class Etype>
list<Etype>::list(const list<Etype>& origlist)
{
   listNode* origlistPtr = (origlist.headerNode)->next;
   listNode* newlistPtr; 

   headerNode = new listNode(); 
   newlistPtr = headerNode; 
   
   if(origlistPtr == (origlist.headerNode))  // then origlist is empty
   {
      headerNode->next = headerNode;
      headerNode->prev = headerNode;
      listSize = 0;
   }
   else    // origlist is not empty; copy it node for node
   {
      while (origlistPtr!=origlist.headerNode) 
      {
         // at least one node in origlist; create that node
         newlistPtr->next = new listNode(); 
         newlistPtr->next->prev = newlistPtr;
         newlistPtr = newlistPtr->next; 
         newlistPtr->element = origlistPtr->element; 
         origlistPtr = origlistPtr->next;
      }
      newlistPtr->next = headerNode; 
      headerNode->prev = newlistPtr; 
      listSize = origlist.listSize;       
   }
}




// ~list
//    - destructor
//    - deallocates all dynamically allocated memory inside the list
template <class Etype>
list<Etype>::~list()
{
   clear(); 
   delete headerNode; 
}



// operator=
//    - parameters: origlist - a previously allocated list object
//    - sets the the list to be a copy of origlist
template <class Etype>
list<Etype>& list<Etype>::operator=(const list<Etype>& origlist)
{

   if (this!=&origlist)
   {
      clear(); 

      listNode *origlistPtr = (origlist.headerNode)->next,
           *newlistPtr;

      newlistPtr = headerNode; 
   
      if (origlistPtr == (origlist.headerNode))  // then origlist is empty 
      {
         headerNode->next = headerNode->prev = headerNode;
         listSize = 0;
      }
      else    // origlist is not empty; copy it node for node
      {
         while (origlistPtr!=origlist.headerNode) 
         {
            // at least one node in origlist; create that node
            newlistPtr->next = new listNode;
            newlistPtr->next->prev = newlistPtr;
            newlistPtr = newlistPtr->next; 
            newlistPtr->element = origlistPtr->element;
            origlistPtr = origlistPtr->next;
         }
         newlistPtr->next = headerNode; 
         headerNode->prev = newlistPtr; 
         listSize = origlist.listSize;
      }
   }
   return *this;
}


// assign
//    - parameters : listSize - new listSize of list
//                 : assignElem - assigning element
//    - assigns list to be of given listSize with each cell
//        assigned to hold assignElem
template <class Etype>
void list<Etype>::assign(int requestedSize, Etype assignElem)
{
   list L(requestedSize, assignElem);
   operator=(L);
}




 // *************** list public functions for iterators

// begin
//    - return type : iterator
//    - returns an iterator that points to first
//        node of list
template <class Etype>
typename list<Etype>::iterator list<Etype>::begin()
{ 
   // the first real node of the abstract list is the 
   //   node after the implementation's header node
   return iterator(headerNode->next); 
}


// begin
//    - return type : iterator
//    - returns an iterator that points to first
//        node of list
template <class Etype>
typename list<Etype>::const_iterator list<Etype>::begin() const
{
   // the first real node of the abstract list is the
   //   node after the implementation's header node
   return iterator(headerNode->next);
}



// end
//    - return type : iterator
//    - returns an iterator that points to "after the last node"
//        so we know we are "off the list".
template <class Etype>
typename list<Etype>::iterator list<Etype>::end() 
{ 
   // The header node follows the last element and comes before
   //   the first element (i.e. the list is circular), so if we 
   //   want to refer to the abstract ``just past the end of list'' 
   //   location, we should return an iterator to this header node 
   //   which immediately follows the last element
   return iterator(headerNode);
}


// end
//    - return type : iterator
//    - returns an iterator that points to "after the last node"
//        so we know we are "off the list".
template <class Etype>
typename list<Etype>::const_iterator list<Etype>::end() const
{
   // The header node follows the last element and comes before
   //   the first element (i.e. the list is circular), so if we
   //   want to refer to the abstract ``just past the end of list''
   //   location, we should return an iterator to this header node
   //   which immediately follows the last element
   return iterator(headerNode);
}


// rbegin
//    - return type : reverse iterator
//    - returns a reverse iterator that points to
//        first node of abstract "reverse list", i.e.
//        last real node of list
template <class Etype>
typename list<Etype>::reverse_iterator list<Etype>::rbegin() 
{ 
   // To create an iterator that traverses back to front
   //   instead of front to back, we would need to have the
   //   idea of an abstract "before head of list" element
   //   so we can traverse from the last node of the list
   //   to the "before head of list" value in the same way
   //   our forward iterator traverses from the first 
   //   element in the list to the "just after the last
   //   element" position. Since we don't want to bother 
   //   with two "special nodes", the standard way to
   //   implement this is to have the reverse iterator
   //   traverse from our "after the list" spot to the 
   //   first element, but when we access the iterator's
   //   value, we really return the location to the left
   //   of this iterator, i.e. the position one earlier 
   //   in the list. Hence, if we abstractly want a
   //   reverse iterator to start at the last node, then
   //   the implementation should return an iterator to the
   //   "after the list" position.  
   // 
   //   That is, generally the rbegin() function is defined
   //   to be equivalent to end() except for the iterator 
   //   type returned. 
   return reverse_iterator(headerNode);
}



// rbegin
//    - return type : reverse iterator
//    - returns a reverse iterator that points to
//        first node of abstract "reverse list", i.e.
//        last real node of list
template <class Etype>
typename list<Etype>::const_reverse_iterator list<Etype>::rbegin() const
{
   // To create an iterator that traverses back to front
   //   instead of front to back, we would need to have the
   //   idea of an abstract "before head of list" element
   //   so we can traverse from the last node of the list
   //   to the "before head of list" value in the same way
   //   our forward iterator traverses from the first
   //   element in the list to the "just after the last
   //   element" position. Since we don't want to bother
   //   with two "special nodes", the standard way to
   //   implement this is to have the reverse iterator
   //   traverse from our "after the list" spot to the
   //   first element, but when we access the iterator's
   //   value, we really return the location to the left
   //   of this iterator, i.e. the position one earlier
   //   in the list. Hence, if we abstractly want a
   //   reverse iterator to start at the last node, then
   //   the implementation should return an iterator to the
   //   "after the list" position.
   //
   //   That is, generally the rbegin() function is defined
   //   to be equivalent to end() except for the iterator
   //   type returned.
   return reverse_iterator(headerNode);
}

// rend
//    - return type : reverse iterator
//    - returns a reverse iterator that points to
//        "end position" of abstract "reverse list", 
//         i.e. the abstract "before first element"
//         spot in list 
template <class Etype>
typename list<Etype>::reverse_iterator list<Etype>::rend() 
{ 
   // Likewise (see the rbegin description), rend() should
   // be equivalent to begin() except for the iterator
   // returned. Abstractly, this function is returning
   // an iterator to the "just before the list" position,
   // but since our implementation doesn't want to mess
   // with a "just before the list" position, we instead 
   // return the "first element" node and the reverse iterator
   // knows to move one to the left for the access. 
   return reverse_iterator(headerNode->next); 
}




// rend
//    - return type : reverse iterator
//    - returns a reverse iterator that points to
//        "end position" of abstract "reverse list",
//         i.e. the abstract "before first element"
//         spot in list
template <class Etype>
typename list<Etype>::const_reverse_iterator list<Etype>::rend() const
{
   // Likewise (see the rbegin description), rend() should
   // be equivalent to begin() except for the iterator
   // returned. Abstractly, this function is returning
   // an iterator to the "just before the list" position,
   // but since our implementation doesn't want to mess
   // with a "just before the list" position, we instead
   // return the "first element" node and the reverse iterator
   // knows to move one to the left for the access.
   return reverse_iterator(headerNode->next);
}


 // ************** Element Access  


// front
//    - return type : a constant reference to a list element 
//    - returns a constant reference to the first cell in the list 
template <class Etype>
const Etype& list<Etype>::front() const 
{   
   // node after header is first real node
   // NOTE: if list is empty, the default element in 
   //   the header node gets returned, since both
   //   pointers of the header node point to itself 
   //   when list is empty. This way, we *do* return
   //   *something*, and don't necessarily need to crash
   //   the program with an assert.
   return headerNode->next->element; 
}



// front 
//    - return type : a reference to a list element 
//    - returns a reference to the first cell in the list 
template <class Etype>
Etype& list<Etype>::front()  
{    
   // node after header is first real node
   // NOTE: if list is empty, the default element in 
   //   the header node gets returned, since both
   //   pointers of the header node point to itself 
   //   when list is empty. This way, we *do* return
   //   *something*, and don't necessarily need to crash
   //   the program with an assert.
   return headerNode->next->element; 
}



// back 
//    - return type : a constant reference to a list element 
//    - returns a constant reference to the first cell in the list 
template <class Etype>
const Etype& list<Etype>::back() const 
{  
   // node prior to header is actual ending node
   // NOTE: if list is empty, the default element in 
   //   the header node gets returned, since both
   //   pointers of the header node point to itself 
   //   when list is empty. This way, we *do* return
   //   *something*, and don't necessarily need to crash
   //   the program with an assert.
   return headerNode->prev->element; 
}



// back 
//    - return type : a reference to a list element 
//    - returns a reference to the first cell in the list 
template <class Etype>
Etype& list<Etype>::back()  
{    
   // node prior to header is actual ending node
   // NOTE: if list is empty, the default element in 
   //   the header node gets returned, since both
   //   pointers of the header node point to itself 
   //   when list is empty. This way, we *do* return
   //   *something*, and don't necessarily need to crash
   //   the program with an assert.
   return headerNode->prev->element; 
}
  




 // ********** (Stack/Queue)-type access



// push_back
//    - parameters : insElem - element to insert
//    - inserts element as last element in list
template <class Etype>
void list<Etype>::push_back(Etype insElem)
{
   listNode* temp = new listNode(insElem); 

   temp->prev = headerNode->prev;
   temp->next = headerNode;

   // if list is empty, headerNode->prev->next is
   //   the next pointer of the headerNode, so
   //   the empty case gets handled gracefully as well. 
   headerNode->prev->next = temp;
   headerNode->prev = temp;
   listSize++;
}




// pop_back
//    - removes last element of list (but does NOT
//        return it)
template <class Etype>
void list<Etype>::pop_back()
{
   // if list is not empty...
   if (headerNode->next != headerNode)
   {   
      listNode* temp = headerNode->prev; 

      // If we want the last node removed, then second-to-last
      //   node should point to header instead of last node.
      // If list had only one element, we will be settting
      //   headerNode to point to itself.
      headerNode->prev->prev->next = headerNode; 
      headerNode->prev = headerNode->prev->prev;
      delete temp;
   }
   // else...?
   // 
   // Do nothing if list is empty. Since we
   //   don't return a value, this will not cause
   //   a problem (though we could have used a 
   //   Warn() call in that case if we wanted to.
   listSize--;
}



 

// push_front
//    - parameters : insElem - element to insert
//    - inserts element as first element in list
template <class Etype>
void list<Etype>::push_front(Etype insElem)
{
   listNode* temp = new listNode(insElem);
   temp->next = headerNode->next;
   temp->prev = headerNode;

   // if list is empty, headerNode->next->prev is
   //   the prev pointer of the headerNode, so
   //   the empty case gets handled gracefully as well. 
   headerNode->next->prev = temp;
   headerNode->next = temp;
   listSize++;
}




// pop_front
//    - removes first element of list (but does NOT 
//        return it. 
template <class Etype>
void list<Etype>::pop_front()
{
   // if list is not empty...
   if (headerNode->next != headerNode)
   {   
      listNode* temp = headerNode->next; 

      // If we want the first node removed, then the second
      //   node should point to header instead of first node.
      // If list had only one element, we will be settting
      //   headerNode to point to itself.
      headerNode->next->next->prev = headerNode;
      headerNode->next = headerNode->next->next;
      delete temp;
   }
   // else...?
   // 
   // Do nothing if list is empty. Since we
   //   don't return a value, this will not cause
   //   a problem (though we could have used a
   //   Warn() call in that case if we wanted to.
   listSize--;
}





 // *************** General list operations




// insert
//    - parameters : insIter - an iterator to the element we want to
//                     insert before
//                 : newElem - an element of the list's type
//    - inserts newElem before the position indicated by the iterator
template <class Etype>
void list<Etype>::insert(iterator insIter, Etype newElem)
{
   listNode *tempPtr = new listNode(newElem); 
    
   tempPtr->next = (insIter.ptr);
   tempPtr->prev = (insIter.ptr)->prev; 
   tempPtr->prev->next = tempPtr;
   tempPtr->next->prev = tempPtr; 
   listSize++; 
}




// insert
//    - parameters : insIter - an iterator to the element we want 
//                     to insert before
//                 : the number of copies of our new element that 
//                     we want
//                 : newElem - an element of the list's type
//    - inserts numCopies copies of newElem before the position 
//        indicated by the iterator
template <class Etype>
void list<Etype>::insert(iterator insIter, int numCopies, Etype insElem)
{
   if (numCopies > 0)
   {
      listNode *headOfChain, *chainTrav; 
      headOfChain = new listNode(insElem); 
      chainTrav = headOfChain;
      for (int i = 1; i <= numCopies - 1; i++) 
      {
         chainTrav->next = new listNode(insElem); 
         chainTrav->next->prev = chainTrav; 
         chainTrav = chainTrav->next; 
      }
      // now headOfChain points to the first node in a 
      // list of numCopies nodes all of which hold insElem;
      // chainTrav points to the last node in that same list.

      headOfChain->prev = (insIter.ptr)->prev;
      chainTrav->next = (insIter.ptr);
      (insIter.ptr)->prev->next = headOfChain;
      //(insIter.ptr)->next->prev = chainTrav;
      (insIter.ptr)->prev = chainTrav;  //@@@@@@@@@@
   
      listSize += numCopies;  
   }
}




// insert
//    - parameters : insIter - an iterator to the element we want 
//                     to insert before
//                 : first - an iterator to the first element in 
//                     a sequence of elements we want to insert
//                 : last - an iterator to the element just past  
//                     the last element in the sequence we want 
//                     to insert (i.e. we are inserting the values
//                     in the range [first, last) meaning first
//                     is included, but last is not
//    - inserts the sequence first (included) through last  
//        (non-included) into this list before the position 
//        indicated by insIter
template <class Etype>
void list<Etype>::insert(iterator insIter, iterator first, iterator last)
{
   if (first != last)
   {
      listNode *headOfChain, *chainTrav;
      int numNewElements = 1; 
      headOfChain = new listNode(*first);
      chainTrav = headOfChain;
      ++first; 
      while (first != last)
      {
         chainTrav->next = new listNode(*first); 
         chainTrav->next->prev = chainTrav; 
         chainTrav = chainTrav->next; 
         ++first;
         numNewElements++; 
      }
      // now headOfChain points to the first node in a 
      // list of nodes which contains the sequential values
      // indicated by [first, last)  

      headOfChain->prev = (insIter.ptr)->prev;
      chainTrav->next = (insIter.ptr);
      (insIter.ptr)->prev->next = headOfChain; 
      //(insIter.ptr)->next->prev = chainTrav;
      (insIter.ptr)->prev = chainTrav; //@@@@@@@@@
      listSize += numNewElements;
   }
}





// erase
//    - parameters : eraseIter - iterator to element to be removed
//    - removes the element at the current postition of the list
template <class Etype> 
void list<Etype>::erase(iterator eraseIter)
{
   // The STL doesn't print out warnings when you do things
   //  such as removing from an empty list, and so we won't
   //  either, even though that is what we did in the list 
   //  class we inspected in section 
   if (eraseIter.ptr != headerNode)
   {
      listNode* temp = eraseIter.ptr;
      temp->prev->next = temp->next;
      temp->next->prev = temp->prev;
      delete temp;
      listSize--;
   }
}


// erase
//    - parameters : first - iterator to first element in sequence 
//                     to be removed
//                 : last - iterator to element after last one to
//                     be removed (see 3rd insert comments for more
//                     explanation)
//    - removes the sequence [first, last) from this list
template <class Etype>
void list<Etype>::erase(iterator first, iterator last)  
{
   if (first.ptr != headerNode)
   {
      listNode* lastRealNode = (last.ptr)->prev;
      (first.ptr)->prev->next = last.ptr; //@@@@
      lastRealNode->next->prev = (first.ptr)->prev;
      // at this point, the relevant elements are 
      //  spliced out of the list
  
      int numElementsDeleted = 0; 
      iterator trav = first;
      while (first != last)
      {
         ++first;
         numElementsDeleted++;
         delete (trav.ptr);
         trav = first;
      }
      // at this point the given sequence, which was spliced out,
      //  is completely deleted

      listSize -= numElementsDeleted; 
   }
}


// clear
//    - deletes all values from list, resulting in an empty list
template <class Etype>
void list<Etype>::clear()
{
   listNode *deletionPtr = headerNode->next;
   listNode *listRestPtr = deletionPtr;

   while (listRestPtr != headerNode)
   {
      listRestPtr = listRestPtr->next;
      delete deletionPtr;
      deletionPtr = listRestPtr;
   }
   headerNode->next = headerNode->prev = headerNode;
   listSize=0;
}




// **************** Other general operations


// size
//    - parameters : none
//    - return value : integer
//    - returns size of list
template <class Etype>
int list<Etype>::size() const
{
   return listSize;
}


// empty
//    - parameters : none
//    - return value : boolean integer
//    - returns 1 if list is empty, 0 else
template <class Etype>
int list<Etype>::empty() const
{
   return (headerNode->next == headerNode);
}




// operator==
//    - parameters : secondVal - another list object to compare to
//    - return type : boolean integer
//    - returns 1 if this list is equal to secondVal, 0 else
template <class Etype>
int list<Etype>::operator==(const list<Etype>& secondVal)
{
   int result = 1;
   if (listSize == secondVal.listSize)
   {
      iterator temp = begin();
      iterator temp2 = iterator(secondVal.begin());
      while (temp != end())
      {
         if (*temp != *temp2)
         {
           result = 0;
           break;
         }
         else
         {
            temp++;
            temp2++;
         }
      }
   } 
   return result;
}

// operator!=
//    - parameters : secondVal - another list object to compare to
//    - return type : boolean integer
//    - returns 1 if this list is not equal to secondVal, 0 else
template <class Etype>
int  list<Etype>::operator!=(const list<Etype>& secondVal)
{
   int result = 0;
   if (listSize == secondVal.listSize)
   {
      iterator temp = iterator(begin());
      iterator temp2 = iterator(secondVal.begin());
      while (temp != end())
      {
         if (*temp != *temp2)
         {
           result = 1;
           break;
         }
         else
         {
            temp++;
            temp2++;
         }
      }
   } 
   return result;
}


// operator<
//    - parameters : secondVal - another list object to compare to
//    - return type : boolean integer
//    - returns 1 if this list is less than secondVal, 0 else
template <class Etype>
int list<Etype>::operator<(const list<Etype>& secondVal)
{
   int result = 0;
   const_iterator temp = iterator(begin());
   const_iterator temp2 = iterator(begin());
   while ((temp != end()) && (temp2 != secondVal.end()))
   {
      if (*temp < *temp2)
      {
        result = 1;
        break;
      }
      else if (*temp > *temp2)
         break;
      else  // *temp == *temp2
      {
         temp++;
         temp2++;
      }
   } 
   return result;
}



	
// **************  list-class-specific operations

// operator<<
//    - friend function of list class
//    - parameters : Out - the output stream to which we will write
//                 : printlist - the list that we will write to the output stream
//    - return value : a reference to the same output stream we passed in
//    - writes list values to parameter stream and returns stream
template <class Etype>
std::ostream& operator<<(std::ostream& Out, const list<Etype>& printlist)
{
   list<Etype>::listNode* listHead = printlist.headerNode;
   list<Etype>::listNode* temp = listHead->next;

   if (printlist.listSize==0)
      Out << "< empty list >";
   else
   {
      Out << "< ";
      while (temp != listHead)
      {
         Out << temp->element << " ";
         temp=temp->next;
      }
      Out << ">";
   }
   return Out;
}




// split
//   - parameters: pos - the position where we want to split the list
//   - this list will be splitted into two list before pos, and the new
//           list will be from pos on.
template <class Etype>
list<Etype> list<Etype>::split(iterator pos)
{

   list<Etype> newL;
   iterator iC=pos;
   int nCounter = 0;
   while(iC!=end())
   {
        nCounter++;
        iC++;
   }
   if(nCounter==0)
        return newL;

   newL.headerNode->prev = headerNode->prev;
   headerNode->prev->next = newL.headerNode;

   pos.ptr->prev->next = headerNode;
   headerNode->prev=pos.ptr->prev;
   listSize-=nCounter;

   newL.listSize=nCounter;
   newL.headerNode->next = pos.ptr;
   pos.ptr->prev = newL.headerNode;

   return newL;
}


// *****************************************************************
// *                                                               *
// *  list225.h                                                    *
// *                                                               *
// *  This file provides the interface for our abbreviated         *
// *  version of the STL list class. The code is not               *
// *  optimized to the extent that a "real" STL                    *
// *  implementation would be, but it has much of the same         *
// *  functionality, and has more understandable source code.      *
// *                                                               *
// *  Written July 1999 by Jason Zych                              *
// *    - September 2003 : "typename" added to iterator            *
// *                                functions in .cpp              *
// *                     : old MP function stubs and #include      *
// *                          of vector225.h removed               *
// *                     : listNode permissions fixed in .h        *    
// *                     : #ifndef macro changed in .h             * 
// *                                                               *
// *   - September 2004 : changes made by Jason Zych               *
// *                     - standard header includes fixed          *
// *                     - iterator implementation moved to .cpp   *
// *                     - enhanced description of this class in   *
// *                           file header and other comments      *
// *                                                               *   
// ***************************************************************** 



/*  
   TO THE CS225 STUDENT:


   This file will at first look large and difficult
   to understand. It will make more sense if you realize
   that it is grouped into four sections as follows:


     (1) typedefs

         This first section is not terribly important to you
         right now and you can skip over it if you like. We've
         designed the file so that it can be ignored until you
         specifically want to use these tools. 

         A "typedef" is a type definition. You are taking an
         existing type, and assigning it an additional name. 
         For example, if you wanted to use the name "foo" to
         create integers, you could use the following line:
 
                     typedef int foo;
         
         and from that point on, these two lines:

                     int x;
                     foo x;

         are indentical, i.e. the name "foo" is equivalent to
         the name "int".

         In the case of the list class, these typedefs --
         -- these "new type names" -- are standard names that exist 
         for every STL class. The idea is that if you are given
         some container object myObj, and you don't know whether 
         it is a vector, or a list, or whatever, you can still say
         myObj::value_type, and that expression will give you
         the type of the value held in this container.


     (2) iterators

         Four kinds of iterators are defined, all of which are
         pretty similar, so once you understand one, you're not
         too far from understanding them all:
 
             iterator 
             const_iterator  
                  same as iterator except you can only read
                  the container through this iterator, not alter it.
                  So, for example, the operator*() function 
                  returns a const reference, so that:

                            cout << *it1 << endl;
   
                  would work, but:

                            *it1 = someValue;

                  would not work. The return value of *it1
                  is const, so you cannot assign to it as with
                  a variable.
                            
             reverse_iterator  
                  same as iterator except that it works in reverse;
                  that is, ++it1 moves the reverse_iterator toward the 
                  front of the container, and --it1 moves the iterator 
                  toward the end of the container, rather than vice-versa 
                  as with (regular) iterators
             const_reverse_iterator
                  same as reverse_iterator except you can only read 
                  the container through this iterator, not alter it, 
                  i.e. const_reverse_iterator is to reverse_iterator
                  as const_iterator is to iterator


     (3) the declarations for the list member functions themselves


     (4) private data and private member functions 
     
*/


#ifndef LIST_225_H
#define LIST_225_H

#include <iostream>
#include <cstddef>

// some forward declarations; we tell the compiler these classes
// and functions exist, so that the compiler knows about their
// existence, but we have more info about them later on.  
template <class Etype> class list;
template<class Etype> std::ostream& 
      operator<< (std::ostream& Out, const list<Etype>& theList);



template <class Etype>
class list
{
public:


   // ************************
   // *                      *
   // *  typedefs            *
   // *                      *
   // ************************


   // C++ STL classes have 12 type definitions, so that every class 
   //   defines the following type names as nested types:
   //      
   //     value_type, pointer, reference, const_pointer, const_reference
   //     iterator, const_iterator, reverse_iterator, const_reverse_iterator
   //     allocator_type, size_type, difference_type


   // Here is the first set of five type definitions
   typedef Etype value_type;       // the client can use 
                                   // list<...>::value_type to access
                                   // whatever type this list holds

   typedef Etype* pointer;         // list<...>::pointer is now the same
                                   //  type as a pointer to whatever type
                                   //  the list holds
 
   typedef Etype& reference;       // list<...>::reference is now the
                                   //  type as a reference to whatever
                                   //  type the list holds

   // these two types give you a pointer to a constant item, 
   //  and a reference to a constant item, respectively
   typedef const Etype* const_pointer;
   typedef const Etype& const_reference;


   // Declarations for
   //    iterator
   //    const_iterator
   //    reverse_iterator
   //    const_reverse_iterator
   // appear below.


   // The declarations  
   //    allocator_type
   //    size_type
   //    difference_type
   //  will not be used in CS225 and thus do not appear in this list class.


public:

   // forward declarations for the iterator classes; that is, we
   // proclaim their existence now, but will add more info later
   // in the file
   class iterator;
   class reverse_iterator;
   class const_iterator;
   class const_reverse_iterator;


private:
    
   // The iterators need access to listNode, which is a private
   // nested type of the list class. So, we need all four iterators
   // to be friends of the list class. If we did not forward declare
   // the iterators above, the lines below would not compile.
   friend class iterator;
   friend class reverse_iterator;
   friend class const_iterator;
   friend class const_reverse_iterator;


   // forward declaration for the listNode implementation class
   class listNode;



public:

   
   // *********************************************
   // *                                           *
   // *  list<>::iterator                         *
   // *                                           *
   // *  iterator for our list class              *
   // *                                           *
   // *********************************************

   class iterator 
   {
   public:

      // same typedefs as for list, only now they are in the
      //  iterator class, so (for example), if you want the type
      //  an iterator points to, not only would list<...>::value_type
      //  work, but so would list<...>::iterator::value_type.
      //  This is especially helpful once you pass iterator objects
      //  as arguments to generic functions.
      typedef Etype value_type;
      typedef Etype* pointer;
      typedef Etype& reference;

      // iterator
      //    - constructor
      //    - initializes this iterator to point to NULL
      iterator();


      // operator*
      //    - return type : a reference to the element type
      //    - returns by reference the cell storing the element
      //         to which this iterator points.  There is no
      //          error checking done to ensure that this is 
      //          a legal cell on which to perform this operation. 
      reference operator*();

     
      // operator->
      //    - return type : a pointer to the element type
      //    - returns a pointer to the cell storing the element
      //         to which this iterator points.  There is no
      //          error checking done to ensure that this is 
      //          a legal cell on which to perform this operation. 
      pointer operator->();

      
      // operator++ (prefix version)
      //    - return type : reference to an iterator
      //    - moves this iterator one position forward in the
      //          collection it points to, and then returns
      //          this iterator after moving it. There is no
      //          error checking done to ensure that this is 
      //          a legal position at which to perform this 
      //          operation.  
      iterator& operator++();

 
      // operator-- (prefix version)
      //    - return type: reference to an iterator     
      //    - moves this iterator one position backward in the
      //          collection it points to, and then returns
      //          this iterator after moving it. There is no
      //          error checking done to ensure that this is 
      //          a legal position at which to perform this 
      //          operation.
      iterator& operator--();



      // operator++ (postfix version)
      //    - parameters : ignore - argument always the integer 1, to 
      //                       distinguish this from prefix version
      //    - return type : an iterator
      //    - moves this iterator one position forward in the 
      //          collection it points to, and then returns an
      //          iterator to the position this iterator pointed
      //          to before this function was run. There is no
      //          error checking done to ensure that this is a
      //          legal position at which to perform this operation. 
      iterator operator++(int ignore);


      // operator-- (postfix version)
      //    - parameters : ignore - argument always the integer 1, to 
      //                       distinguish this from prefix version
      //    - return type : an iterator
      //    - moves this iterator one position backward in the 
      //          collection it points to, and then returns an
      //          iterator to the position this iterator pointed
      //          to before this function was run. There is no
      //          error checking done to ensure that this is a
      //          legal position at which to perform this operation. 
      iterator operator--(int ignore);


      // operator==
      //    - parameters : origVal - previously created iterator
      //    - return value : boolean integer
      //    - returns 1 if this iterator and the parameter 
      //         iterator point to the same location, 0 else
      int operator==(const iterator& origVal) const;


      // operator!=
      //    - parameters : origVal - previously created iterator
      //    - return value : boolean integer
      //    - returns 1 if this iterator and the parameter 
      //         iterator point different locations, 0 else
      int operator!=(const iterator& origVal) const;



   private:

      // pointer to an internal node of the list; however, the
      // iterator, from the client's point of view, is only 
      // supposed to point to the element inside a listNode, 
      // not to the entire listNode itself. 
      // 
      // The entire iterator object is basically a wrapper for
      // this pointer.
      typename list<value_type>::listNode* ptr; 

   
   
      // iterator
      //    - constructor
      //    - parameters : assignPtr - a pointer to the same type
      //           that this iterator points to
      //    - initializes iterator to point to the same place as
      //         the parameter pointer points to
      iterator(typename list<Etype>::listNode* assignPtr);


      // these lines give the list class and the const_iterator class
      //   access to the above private members of iterator
      friend class list<value_type>;
      friend class list<value_type>::const_iterator;
   };




   // *********************************************
   // *                                           *
   // *  list<>::const_iterator                   *
   // *                                           *
   // *  const_iterator for our list class        *
   // *                                           *
   // *********************************************

   class const_iterator
   {
   public:

      // same typedefs as for list, only now they are in the
      //  iterator class, so (for example), if you want the type
      //  an iterator points to, not only would list<...>::value_type
      //  work, but so would list<...>::iterator::value_type.
      //  This is especially helpful once you pass iterator objects
      //  as arguments to generic functions.
      typedef const Etype value_type;
      typedef const Etype* const_pointer;
      typedef const Etype& const_reference;


      // const_iterator
      //    - constructor
      //    - initializes this const_iterator to point to NULL
      const_iterator();


      // const_iterator
      //    - constructor
      //    - parameters : theIter - an iterator
      //    - initializes this const_iterator to point to the same
      //           location as the parameter iterator
      const_iterator(const iterator& theIter);


      // operator*
      //    - return type : a const_reference to the element type
      //    - returns by const_reference the element to which this
      //         const_iterator points. There is no error checking 
      //         done to ensure that this is a legal cell on which
      //         to perform this operation.
      const_reference operator*() const;


      // operator->
      //    - return type : a const_pointer to the element type
      //    - returns a const_pointer to the element to which
      //        this const_iterator points. There is no error checking 
      //        done to ensure that this is a legal cell on which
      //        to perform this operation.
      const_pointer operator->() const;


      // operator++ (prefix version)
      //    - return type : const_reference to an iterator
      //    - moves this iterator one position forward in the
      //          collection it points to, and then returns
      //          this iterator after moving it. There is no
      //          error checking done to ensure that this is 
      //          a legal position at which to perform this 
      //          operation.  
      const_iterator& operator++();


      // operator-- (prefix version)
      //    - return type: const_reference to an iterator     
      //    - moves this iterator one position backward in the
      //          collection it points to, and then returns
      //          this iterator after moving it. There is no
      //          error checking done to ensure that this is 
      //          a legal position at which to perform this 
      //          operation.
      const_iterator& operator--();


      // operator++ (postfix version)
      //    - parameters : ignore - argument always the integer 1, to 
      //                       distinguish this from prefix version
      //    - return type : a const_iterator
      //    - moves this iterator one position forward in the 
      //          collection it points to, and then returns an
      //          iterator to the position this iterator pointed
      //          to before this function was run. There is no
      //          error checking done to ensure that this is a
      //          legal position at which to perform this operation. 
      const_iterator operator++(int ignore);


      // operator-- (postfix version)
      //    - parameters : ignore - argument always the integer 1, to 
      //                       distinguish this from prefix version
      //    - return type : a const_iterator
      //    - moves this iterator one position backward in the 
      //          collection it points to, and then returns an
      //          iterator to the position this iterator pointed
      //          to before this function was run. There is no
      //          error checking done to ensure that this is a
      //          legal position at which to perform this operation. 
      const_iterator operator--(int ignore);


      // operator==
      //    - parameters : origVal - previously created const_iterator
      //    - return value : boolean integer
      //    - returns 1 if this iterator and the parameter 
      //         iterator point to the same location, 0 else
      int operator==(const const_iterator& origVal) const;


      // operator!=
      //    - parameters : origVal - previously created const_iterator
      //    - return value : boolean integer
      //    - returns 1 if this iterator and the parameter 
      //         iterator point different locations, 0 else
      int operator!=(const const_iterator& origVal) const;


   private:

      // pointer to an internal node of the list; however, the
      // iterator, from the client's point of view, is only 
      // supposed to point to the element inside a listNode, 
      // not to the entire listNode itself. 
      // 
      // The entire iterator object is basically a wrapper for
      // this pointer.
      typename list<Etype>::listNode* ptr;

      // const_iterator
      //    - constructor
      //    - parameters : assignPtr - a const_pointer to the same type
      //           that this const_iterator points to
      //    - initializes const_iterator to point to the same place as
      //         the parameter pointer points to
      const_iterator(typename list<Etype>::listNode* assignPtr);



      // this line gives the list class access to the above
      // private members of iterator
      friend class list<Etype>;
   };




   // ***********************************************
   // *                                             *
   // *  listr<>::reverse_iterator                  *
   // *                                             *
   // *  reverse_iterator for list class            *
   // *                                             *
   // ***********************************************

   class reverse_iterator
   {
   public:

      // same typedefs as for list, only now they are in the
      //  iterator class, so (for example), if you want the type
      //  an iterator points to, not only would list<...>::value_type
      //  work, but so would list<...>::iterator::value_type.
      //  This is especially helpful once you pass iterator objects
      //  as arguments to generic functions.
      typedef Etype value_type;
      typedef Etype* pointer;
      typedef Etype& reference;



      // reverse_iterator
      //    - constructor
      //    - initializes this reverse_iterator to point to NULL
      reverse_iterator();


      // operator*
      //    - return type : a reference to the element type
      //    - returns by reference the cell storing the element
      //         to which this reverse_iterator points.  There is 
      //          no error checking done to ensure that this is 
      //          a legal cell on which to perform this operation. 
      reference operator*();


      // operator->
      //    - return type : a pointer to the element type
      //    - returns a pointer to the cell storing the element
      //         to which this reverse_iterator points.  There is 
      //          no error checking done to ensure that this is 
      //          a legal cell on which to perform this operation. 
      pointer operator->();


      // operator++ (prefix version)
      //    - return type : reference to a reverse_iterator
      //    - moves this iterator one position forward in the
      //          collection it points to, and then returns
      //          this iterator after moving it. There is no
      //          error checking done to ensure that this is 
      //          a legal position at which to perform this 
      //          operation.  
      reverse_iterator& operator++();


      // operator-- (prefix version)
      //    - return type: reference to a reverse_iterator     
      //    - moves this iterator one position backward in the
      //          collection it points to, and then returns
      //          this iterator after moving it. There is no
      //          error checking done to ensure that this is 
      //          a legal position at which to perform this 
      //          operation.
      reverse_iterator& operator--();


      // operator++ (postfix version)
      //    - parameters : ignore - argument always the integer 1, to 
      //                       distinguish this from prefix version
      //    - return type : a reverse_iterator
      //    - moves this iterator one position forward in the 
      //          collection it points to, and then returns an
      //          iterator to the position this iterator pointed
      //          to before this function was run. There is no
      //          error checking done to ensure that this is a
      //          legal position at which to perform this operation. 
      reverse_iterator operator++(int ignore);


      // operator-- (postfix version)
      //    - parameters : ignore - argument always the integer 1, to 
      //                       distinguish this from prefix version
      //    - return type : a reverse_iterator
      //    - moves this iterator one position backward in the 
      //          collection it points to, and then returns an
      //          iterator to the position this iterator pointed
      //          to before this function was run. There is no
      //          error checking done to ensure that this is a
      //          legal position at which to perform this operation. 
      reverse_iterator operator--(int ignore);


      // operator==
      //    - parameters : origVal - previously created reverse_iterator
      //    - return value : boolean integer
      //    - returns 1 if this iterator and the parameter 
      //         iterator point to the same location, 0 else
      int operator==(const reverse_iterator& origVal) const;

 
      // operator!=
      //    - parameters : origVal - previously created reverse_iterator
      //    - return value : boolean integer
      //    - returns 1 if this iterator and the parameter 
      //         iterator point different locations, 0 else
      int operator!=(const reverse_iterator& origVal) const;



   private:

      iterator current;  // reverse iterators are implemented
                         // by using an iterator to the position
                         // to the right of where we want the
                         // reverse iterator to be. Then when 
                         // dereferencing the reverse_iterator, we
                         // return the value to the left of current 


      // reverse_iterator
      //    - constructor
      //    - parameters : assignIter - iterator to the same type of
      //         data to which this reverse_iterator points 
      //    - initializes this reverse_iterator to point to the same
      //       place that the parameter iterator points to
      reverse_iterator(iterator assignIter);


      friend class list<value_type>;
      friend class list<value_type>::const_reverse_iterator;
   };




   // ***********************************************
   // *                                             *
   // *  list<>::const_reverse_iterator             *
   // *                                             *
   // *  const_reverse iterator for our list class. *
   // *                                             *
   // ***********************************************

   class const_reverse_iterator
   {
   public:

      // same typedefs as for list, only now they are in the
      //  iterator class, so (for example), if you want the type
      //  an iterator points to, not only would list<...>::value_type
      //  work, but so would list<...>::iterator::value_type.
      //  This is especially helpful once you pass iterator objects
      //  as arguments to generic functions.
      typedef const Etype value_type;
      typedef const Etype* const_pointer;
      typedef const Etype& const_reference;



      // const_reverse_iterator
      //    - constructor
      //    - initializes this const_reverse_iterator to NULL
      const_reverse_iterator();


      // const_reverse_iterator
      //    - constructor
      //    - parameters : theIter - a reverse_iterator which points
      //           to the same time as this const_reverse_iterator
      //    - initializes this const_reverse_iterator to point to the
      //        same place to which the parameter reverses_iterator
      //        points
      const_reverse_iterator(const reverse_iterator& theIter);


      // operator*
      //    - return type : a const_reference to the element type
      //    - returns by const_reference the cell storing the element
      //         to which this const_reverse_iterator points.  There is 
      //          no error checking done to ensure that this is 
      //          a legal cell on which to perform this operation. 
      const_reference operator*() const;


      // operator->
      //    - return type : a const_pointer to the element type
      //    - returns a const_pointer to the cell storing the element
      //         to which this const_reverse_iterator points.  There is 
      //          no error checking done to ensure that this is 
      //          a legal cell on which to perform this operation. 
      const_pointer operator->() const;


      // operator++ (prefix version)
      //    - return type : reference to a const_reverse_iterator
      //    - moves this iterator one position forward in the
      //          collection it points to, and then returns
      //          this iterator after moving it. There is no
      //          error checking done to ensure that this is 
      //          a legal position at which to perform this 
      //          operation.  
      const_reverse_iterator& operator++();


      // operator-- (prefix version)
      //    - return type: reference to a const_reverse_iterator     
      //    - moves this iterator one position backward in the
      //          collection it points to, and then returns
      //          this iterator after moving it. There is no
      //          error checking done to ensure that this is 
      //          a legal position at which to perform this 
      //          operation.
      const_reverse_iterator& operator--();


      // operator++ (postfix version)
      //    - parameters : ignore - argument always the integer 1, to 
      //                       distinguish this from prefix version
      //    - return type : a const_reverse_iterator
      //    - moves this iterator one position forward in the 
      //          collection it points to, and then returns an
      //          iterator to the position this iterator pointed
      //          to before this function was run. There is no
      //          error checking done to ensure that this is a
      //          legal position at which to perform this operation. 
      const_reverse_iterator operator++(int ignore);


      // operator-- (postfix version)
      //    - parameters : ignore - argument always the integer 1, to 
      //                       distinguish this from prefix version
      //    - return type : a const_reverse_iterator
      //    - moves this iterator one position backward in the 
      //          collection it points to, and then returns an
      //          iterator to the position this iterator pointed
      //          to before this function was run. There is no
      //          error checking done to ensure that this is a
      //          legal position at which to perform this operation. 
      const_reverse_iterator operator--(int ignore);


      // operator==
      //    - parameters : origVal - previously created const_reverse_iterator
      //    - return value : boolean integer
      //    - returns 1 if this iterator and the parameter 
      //         iterator point to the same location, 0 else
      int operator==(const const_reverse_iterator& origVal) const;


      // operator!=
      //    - parameters : origVal - previously created const_reverse_iterator
      //    - return value : boolean integer
      //    - returns 1 if this iterator and the parameter 
      //         iterator point different locations, 0 else
      int operator!=(const const_reverse_iterator& origVal) const;



   private:

      iterator current;  // reverse iterators are implemented
                         // by using an iterator to the position
                         // to the right of where we want the
                         // reverse iterator to be. Then when 
                         // dereferencing the reverse_iterator, we
                         // return the value to the left of current 


      // these lines give the list class access to the
      //   above private members of const_reverse_iterator
      friend class list<value_type>;

   };



  // ************************
  // *                      *
  // *  list functions      *
  // *                      *
  // ************************



 // *** Constructors and Big Three

   // list
   //    - default constructor
   //    - creates an empty list
   list();



   // list
   //    - constructor
   //    - parameters : theListSize - number of elements in this list
   //    - creates a list of listSize default elements   
   list(int theListSize); 



   // list
   //    - constructor
   //    - parameters : theListSize - number of elements in this list
   //    - creates a list of listSize elements each initialized to 
   //           initElem 
   list(int theListSize, Etype initElem); 




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



   // ~list
   //    - destructor
   //    - deallocates all dynamically allocated memory inside the list
   ~list();



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




   // assign
   //    - parameters : listSize - new size of list
   //                 : assignElem - assigning element
   //    - assigns list to be of given size with each cell
   //        assigned to hold assignElem
   void assign(int listSize, Etype assignElem);




 // *** list public functions for iterators

   // begin
   //    - return type : iterator
   //    - returns an iterator that points to first
   //        node of list
   iterator begin();


   // begin
   //    - return type : iterator
   //    - returns an iterator that points to first
   //        node of list
   const_iterator begin() const;


   // end
   //    - return type : iterator
   //    - returns an iterator that points to "after the last node"
   //        so we know we are "off the list".
   iterator end();


   // end
   //    - return type : iterator
   //    - returns an iterator that points to "after the last node"
   //        so we know we are "off the list".
   const_iterator end() const;


   // rbegin
   //    - return type : reverse iterator
   //    - returns a reverse iterator that points to
   //        first node of abstract "reverse list", i.e.
   //        last real node of list
   reverse_iterator rbegin();



   // rbegin
   //    - return type : reverse iterator
   //    - returns a reverse iterator that points to
   //        first node of abstract "reverse list", i.e.
   //        last real node of list
   const_reverse_iterator rbegin() const;

 
   // rend
   //    - return type : reverse iterator
   //    - returns a reverse iterator that points to
   //        "end position" of abstract "reverse list",
   //         i.e. the abstract "before first element"
   //         spot in list  
   reverse_iterator rend();
 

   // rend
   //    - return type : reverse iterator
   //    - returns a reverse iterator that points to
   //        "end position" of abstract "reverse list",
   //         i.e. the abstract "before first element"
   //         spot in list
   const_reverse_iterator rend() const;
 


 // ******** Element access


   // front
   //    - return type : a constant reference to a list element
   //    - returns a constant reference to the first cell in the list 
   const Etype& front() const;


   // front
   //    - return type : a reference to a list element 
   //    - returns a reference to the first cell in the list 
   Etype& front();


   // back 
   //    - return type : a constant reference to a list element 
   //    - returns a constant reference to the first cell in the list 
   const Etype& back() const;


   // back 
   //    - return type : a reference to a list element 
   //    - returns a reference to the first cell in the list 
   Etype& back();



 // ********** (Stack/Queue)-type access


   // push_back
   //    - parameters : insElem - element to insert
   //    - inserts element as last element in list   
   void push_back(Etype insElem);


   // pop_back
   //    - removes last element of list (but does NOT
   //        return it)
   void pop_back(); 
  

   // push_front
   //    - parameters : insElem - element to insert
   //    - inserts element as first element in list
   void push_front(Etype insElem);


   // pop_front
   //    - removes first element of list (but does NOT 
   //        return it. 
   void pop_front(); 



 // *************** General list operations


   // insert
   //    - parameters : insIter - an iterator to the element we want to
   //                     insert before
   //                 : newElem - an element of the list's type
   //    - inserts newElem before the position indicated by the iterator
   void insert(iterator insIter, Etype newElem); 



   // insert
   //    - parameters : insIter - an iterator to the element we want 
   //                     to insert before
   //                 : the number of copies of our new element that 
   //                     we want
   //                 : newElem - an element of the list's type
   //    - inserts numCopies copies of newElem before the position 
   //        indicated by the iterator
   void insert(iterator insIter, int numCopies, Etype insElem);



   // insert
   //    - parameters : insIter - an iterator to the element we want 
   //                     to insert before
   //                 : first - an iterator to the first element in
   //                     a sequence of elements we want to insert 
   //                 : last - an iterator to the element just past
   //                     the last element in the sequence we want 
   //                     to insert (i.e. we are inserting the values
   //                     in the range [first, last) meaning first
   //                     is included, but last is not
   //    - inserts the sequence first (included) through last 
   //        (non-included) into this list before the position 
   //        indicated by insIter
   void insert(iterator insIter, iterator first, iterator last);



   // erase 
   //    - parameters : eraseIter - iterator to element to be removed
   //    - removes the element at the current postition of the list
   void erase(iterator eraseIter);



   // erase
   //    - parameters : first - iterator to first element in sequence
   //                     to be removed
   //                 : last - iterator to element after last one to
   //                     be removed (see 3rd insert comments for more
   //                     explanation) 
   //    - removes the sequence [first, last) from this list
   void erase(iterator first, iterator last);  


   // clear
   //    - deletes all values from list, resulting in an empty list
   void clear();


// **************** Other general operations

   // size
   //    - parameters : none
   //    - return value : integer
   //    - returns size of list 
   int size() const; 


   // Empty
   //    - parameters : none
   //    - return value : boolean integer
   //    - returns 1 if list is empty, 0 else
   int empty() const;


   // operator==
   //    - parameters : secondVal - another list object to compare to
   //    - return type : boolean integer
   //    - returns 1 if this list is equal to secondVal, 0 else 
   int operator==(const list& secondVal);

 

   // operator!=
   //    - parameters : secondVal - another list object to compare to
   //    - return type : boolean integer
   //    - returns 1 if this list is not equal to secondVal, 0 else 
   int operator!=(const list& secondVal);


   // operator<
   //    - parameters : secondVal - another list object to compare to
   //    - return type : boolean integer
   //    - returns 1 if this list is less than secondVal, 0 else 
   int operator<(const list& secondVal);




// **************  list-class-specific operations


   // merge and splice to be added later

   // split
   // 	- parameters: pos - the position where we want to split the list
   //   - this list will be splitted into two list before pos, and the new 
   //		list will be from pos on.
   list<Etype> split(iterator pos);




   // operator<<
   //    - friend function of list class
   //    - parameters : Out - the output stream to which we will write
   //                 : printlist - the list that we will write to the 
   //                                                   output stream
   //    - return value : a reference to the same output stream we passed in
   //    - writes list values to parameter stream and returns stream
   friend std::ostream&
              operator<< <Etype> (std::ostream& Out, 
                                             const list<Etype>& printlist);


private:

   class listNode
   {
   public:    // public within context of list class
              // protected outside list class

      // listNode Constructor
      listNode() { prev = NULL; next = NULL; }
      listNode(Etype elem) { prev=NULL; next = NULL; element = elem; }

      Etype element;
      listNode* next;
      listNode* prev;
   };


private:

   listNode *headerNode;  

   int listSize;          // number of nodes in list


};

#endif 

   

// *************************************************************
// *                                                           *
// *  utility225.cpp                                           *
// *                                                           *
// *  This file provides definitions for the four general      *
// *  relational operator functions and the pair class.        * 
// *                                                           *
// *  Written July 1999 by Jason Zych                          *
// *                                                           *
// *     - updates March 2005 by Jason Zych                    *
// *          - #ifndef macro name changed                     *
// *          - .h removed on standard header include          *
// *          - const standardized to the right of what it     *
// *               modifies                                    *
// *          - bool now used as return type                   *
// *          - typename used instead of class where needed    *
// *          - pair <=, >=, >, != removed (use given          *
// *               universal versions instead)                 *
// *                                                           *
// *************************************************************


#include "utility225.h"


// operator!=
//    - parameters : firstVal - the first of two values to be compared
//                 : secondVal - the second of two values to be compared
//    - return type : boolean with true meaning "not equal"
//    - returns true if firstVal != secondVal, false else
template <typename Etype>
bool operator!=(Etype const & firstVal, Etype const & secondVal)
{
   return !(firstVal == secondVal);
}



// operator>
//    - parameters : firstVal - the first of two values to be compared 
//                 : secondVal - the second of two values to be compared
//    - return type : boolean with true meaning "greater than"
//    - returns true if firstVal > secondVal, false else
template <typename Etype>
bool operator>(Etype const & firstVal, Etype const & secondVal)
{
   return (secondVal < firstVal);
}



// operator<=
//    - parameters : firstVal - the first of two values to be compared 
//                 : secondVal - the second of two values to be compared
//    - return type : boolean with true meaning <=
//    - returns true if firstVal <= secondVal, false else
template <typename Etype>
bool operator<=(Etype const & firstVal, Etype const & secondVal)
{
   return !(secondVal < firstVal);
}



// operator>=
//    - parameters : firstVal - the first of two values to be compared 
//                 : secondVal - the second of two values to be compared
//    - return type : boolean with true meaning >=
//    - returns true if firstVal >= secondVal, false else
template <typename Etype>
bool operator>=(Etype const & firstVal, Etype const & secondVal)
{
   return !(firstVal < secondVal);
}



// pair
//    - default constructor
//    - sets object to hold default values
//        (on the initializer line, each member variable
//         is being initialized to the default value
//         of the appropriate type) 
template <typename Type1, typename Type2>
pair<Type1, Type2>::pair() : first(), second()  {}


// pair
//    - constructor
//    - parameters : firstVal - value of the first type
//                 : secondVal - value of the second type
//    - sets object to hold parameter values
template <typename Type1, typename Type2>
pair<Type1, Type2>::pair(Type1 const & firstVal, Type2 const & secondVal) :  
                          first(firstVal), second(secondVal)  {}
     




// operator==
//    - parameters : firstpair - the first of two pairs to compare
//                 : secondpair - the second of two pairs to compare
//    - return value : boolean with true meaning "equal"
//    - returns true if the firstpair is equal to the secondpair, false else.
template <typename Type1, typename Type2>
bool operator==(pair<Type1, Type2> const & firstpair,
                           pair<Type1, Type2> const & secondpair)
{ 
   // two pairs are equal if their first elements are equal and
   //   their second elements are equal
   return ((firstpair.first == secondpair.first) && 
		(firstpair.second == secondpair.second)); 
}




// operator<
//    - parameters : firstpair - the first of two pairs to compare
//                 : secondpair - the second of two pairs to compare
//    - return value : boolean with true meaning "less than"
//    - returns true if the firstpair is less than the secondpair, false else;
//         for pairs, less than is defined as, A < B if A.first < B.first,
//         or if A.first == B.first and A.second < B.second
template <typename Type1, typename Type2>
bool operator<(pair<Type1, Type2> const & firstpair,
                                pair<Type1, Type2> const & secondpair)
{ 
   //  firstpair is less than secondpair if either:
   //    1) firstpair's first element is less than secondpair's 
   //        first element; that is, the first element is the key
   //        and the key is most important for comparison, so 
   //        if firstpair.first < secondpair.first, that automatically
   //        means firstpair < secondpair regardless of the relationship
   //        between the second elements of both pairs
   //    2) assuming that (1) was not the case, we at least don't
   //        want the secondpair's first element to be less than
   //        firstpair's first element. So, if (1) doesn't hold,
   //        our second case will only hold if 
   //        secondpair.first is not less than firstpair.first.
   //        Once we have established that, we also need for 
   //        firstpair's second element to be less than secondpair's
   //        second element. So, there are two conditions inherent
   //        in case (2), and they must both be true for (2) to be
   //        true.  
   return ((firstpair.first < secondpair.first) || 
                     (   (!(secondpair.first < firstpair.first)) && 
	                 (firstpair.second < secondpair.second)   )); 
}


// *************************************************************
// *                                                           *
// *  utility225.h                                             *
// *                                                           *
// *  This file provides four general relational operator      *
// *   functions and the pair class.                           *
// *                                                           *
// *  Written July 1999 by Jason Zych                          *
// *                                                           *
// *     - updates March 2005 by Jason Zych                    *
// *          - #ifndef macro name changed                     *
// *          - .h removed on standard header include          *
// *          - const standardized to the right of what it     *
// *               modifies                                    *
// *          - bool now used as return type                   *
// *          - typename used instead of class where needed    *
// *          - pair <=, >=, >, != removed (use given          *
// *               universal versions instead)                 *
// *                                                           *
// *************************************************************

#ifndef UTILITY_225_H
#define UTILITY_225_H


// ************ Types used to fill in the template parameter 
//              for a template class often need to have the 
//              relational operations defined. Typically, the 
//              specification requires only that the < and == operations
//              be defined, since the other four operations can be
//              derived from those two. So, the function implementations
//              below all assume that < and == exist on the Etype in
//              question.
// 
// ************ Note that we have the implementation in the .h file.
//              This *is* permissible in some situations, usually when
//              the code for a function is very short. There is also 
//              an "inline" keyword which makes these function calls
//              to short functions more efficient, but we have not 
//              discussed it yet so we will leave it out of these function
//              implementations. 
// 
// ************ Note that we went ahead and defined these four relational
//              operators again for the pair class (or rather, as global
//              functions after we had finished the pair class declaration --
//              see below). I am not entirely sure this was necessary,
//              as pair<Type1, Type2> can probably be filled in for Etype
//              below and the four functions below could be used instead. 
//              However, I have seen some implementations which implement 
//              pair's other four relational operations separately, as we
//              have done. For that reason, I defined them separately in
//              our code as well. I suspect that they were originally 
//              defined separately for the purposes of getting around any
//              difficulty compilers may have had filling in generic types
//              with other template expressions, as we would be doing
//              if we replaced Etype below with some pair<Type1, Type2> 
//              expression.



// operator!=
//    - parameters : firstVal - the first of two values to be compared
//                 : secondVal - the second of two values to be compared
//    - return type : boolean with true meaning "not equal"
//    - returns true if firstVal != secondVal, false else
template <typename Etype>
bool operator!=(Etype const & firstVal, Etype const & secondVal);



// operator>
//    - parameters : firstVal - the first of two values to be compared 
//                 : secondVal - the second of two values to be compared
//    - return type : boolean with true meaning "greater than"
//    - returns true if firstVal > secondVal, false else
template <typename Etype>
bool operator>(Etype const & firstVal, Etype const & secondVal);



// operator<=
//    - parameters : firstVal - the first of two values to be compared 
//                 : secondVal - the second of two values to be compared
//    - return type : boolean with true meaning <=
//    - returns true if firstVal <= secondVal, false else
template <typename Etype>
bool operator<=(Etype const & firstVal, Etype const & secondVal);



// operator>=
//    - parameters : firstVal - the first of two values to be compared 
//                 : secondVal - the second of two values to be compared
//    - return type : boolean with true meaning >=
//    - returns true if firstVal >= secondVal, false else
template <typename Etype>
bool operator>=(Etype const & firstVal, Etype const & secondVal);



template <typename Type1, typename Type2>
class pair
{
public:

   // ************* Useful type definitions for later
 
   typedef Type1 first_type;  // whatever Type1 is can now also
                              // be called First_Type...well, 
                              // with some scoping restrictions 
                              // that we won't worry about right now

   typedef Type2 second_type; // whatever Type2 is can now also
                              // be called Second_Type...well, 
                              // with some scoping restrictions 
                              // that we won't worry about right now


 
   // ************ Member functions 

   // pair
   //    - default constructor
   //    - sets object to hold default values
   //        (on the initializer line, each member variable
   //         is being initialized to the default value
   //         of the appropriate type) 
   pair();


   // pair
   //    - constructor
   //    - parameters : firstVal - value of the first type
   //                 : secondVal - value of the second type
   //    - sets object to hold parameter values
   pair(Type1 const & firstVal, Type2 const & secondVal);



  // There is also another constructor that is similar to a 
  // copy constructor but makes use of the Type1 and Type2 constructors,
  // but it requires template member functions and the compiler isn't
  // fond of those, so we'll leave it out right now.
 


   // ************* Member data
   //    - we intend for the data to be public, too

   Type1 first;       // variable of the first type
   Type2 second;      // variable of the second type

};   // end of pair class



// operator==
//    - parameters : firstpair - the first of two pairs to compare
//                 : secondpair - the second of two pairs to compare
//    - return value : boolean with true meaning "equal"
//    - returns true if the firstpair is equal to the secondpair, false else.
template <typename Type1, typename Type2>
bool operator==(pair<Type1, Type2> const & firstpair, 
                           pair<Type1, Type2> const & secondpair);



// operator<
//    - parameters : firstpair - the first of two pairs to compare
//                 : secondpair - the second of two pairs to compare
//    - return value : boolean with true meaning "less than"
//    - returns true if the firstpair is less than the secondpair, false else;
//         for pairs, less than is defined as, A < B if A.first < B.first,
//         or if A.first == B.first and A.second < B.second
template <typename Type1, typename Type2>
bool operator<(pair<Type1, Type2> const & firstpair, 
				pair<Type1, Type2> const & secondpair);


#endif



#*************************************************************************
#  CS225 General Makefile
#*************************************************************************

#*************************************************************************
# To begin our Makefile, we want to create various helpful macros.
#
# First of all, we need to name our program. The "executable file" is the 
# actual program -- all the individual compiled files linked together.

NAME_OF_EXECUTABLE_FILE = mp7

# Next, we want to define which C++ compiler we are using and what options
# we are using for that compiler. 

COMPILER = CC
COMPILER_OPTS = -c -g

# Next, we want to define which program we are using to link all our
# files together (often, we are using the compiler we used to compile them
# in the first place) and what options we are using for that linker.

LINKER = CC
LINKER_OPTS = -o $(NAME_OF_EXECUTABLE_FILE)

# Finally, we want a list of all the .o files (object files) that 
# NAME_OF_EXECUTABLE_FILE depends on. That is, we want a list of all 
# the object files that make up the program. 

OBJS = asserts.o array.o list225.o utility225.o \
	trie.o string.o mp7fns.o main.o

# And that is it for the macros; we now are ready to compile and link
# the program.
#**************************************************************************


#************************************************************************
# Rule for linking the program.

$(NAME_OF_EXECUTABLE_FILE) : $(OBJS)
	$(LINKER) $(LINKER_OPTS) $(OBJS)

# And that is it for the linking step! However, the assorted .o files 
# must be created before the above line can finish, so the compilation
# rules below get run before the above rule can finish.
#************************************************************************


#**************************************************************************
# Rules for performing the compilation of each individual object file.

asserts.o : asserts.h asserts.cpp
	$(COMPILER) $(COMPILER_OPTS) asserts.cpp

array.o : array.h array.cpp asserts.h
	$(COMPILER) $(COMPILER_OPTS) array.cpp

list225.o : list225.h list225.cpp 
	$(COMPILER) $(COMPILER_OPTS) list225.cpp

utility225.o : utility225.h utility225.cpp
	$(COMPILER) $(COMPILER_OPTS) utility225.cpp

trie.o : trie.h trie.cpp
	$(COMPILER) $(COMPILER_OPTS) trie.cpp

string.o : string.h string.cpp
	$(COMPILER) $(COMPILER_OPTS) string.cpp

mp7fns.o : mp7fns.h mp7fns.cpp
	$(COMPILER) $(COMPILER_OPTS) mp7fns.cpp

main.o : main.cpp asserts.h array.h list225.h utility225.h \
	trie.h string.h mp7fns.h
	$(COMPILER) $(COMPILER_OPTS) main.cpp

# And now we have created all the individual object files specified with 
# the macro "OBJS". 
#************************************************************************


#***********************************************************************
# The "clean" rule -- triggered with the command "make clean" -- will
# erase any files created by the compilation. That is, it cleans up
# the directory you are in, so that the next compilation must proceed
# completely from scratch. This is sometimes very helpful.

clean:
	-rm *.o $(NAME_OF_EXECUTABLE_FILE)
	-rm -rf SunWS_cache

# 
#***********************************************************************



// ***************************************************
// *                                                 *
// *  main.cpp (MP7)                                 *
// *                                                 *
// *  Test code for a de la Briandais tree           *
// *                                                 *
// *  Written April 2005 by Jason Zych               *
// *                                                 *
// ***************************************************

#include <iostream>
#include "asserts.h"
#include "array.h"
#include "string.h"
#include "trie.h"
#include "mp7fns.h"


int main()
{
   Array<String> myStrings(1, 19);
   myStrings[1] = "maxwell";
   myStrings[2] = "pasteur";
   myStrings[3] = "turing";
   myStrings[4] = "mendel";
   myStrings[5] = "poincare";
   myStrings[6] = "poisson";
   myStrings[7] = "pavlov";
   myStrings[8] = "peano";
   myStrings[9] = "mendeleev";
   myStrings[10] = "impossibly";
   myStrings[11] = "impossible";
   myStrings[12] = "important";
   myStrings[13] = "impossibility";
   myStrings[14] = "interesting";
   myStrings[15] = "bohr"; 
   myStrings[16] = "mentos";
   myStrings[17] = "menace";
   myStrings[18] = "mensa";
   myStrings[19] = "mendelin";
   Trie testTrie;

   Trie theEqual;
   for (int i = 15; i <= 18; i++)
   {
      insertTest(theEqual, myStrings[i], false);
      //theEqual.print();
   }
   std::cout << "*** small trie ***" << std::endl;
   theEqual.print();
   std::cout << std::endl << std::endl;


   for (int i = 1; i <= 15; i++)
      insertTest(testTrie, myStrings[i], false);

   Trie theCopy(testTrie);
   theEqual = testTrie;

   insertTest(testTrie, myStrings[16], false);
   insertTest(testTrie, myStrings[17], false);
   insertTest(testTrie, myStrings[18], true);

   //testTrie.print();

   for (int i = 1; i <= 17; i++)
      removeTest(testTrie, myStrings[i], false);
   removeTest(testTrie, myStrings[18], true);

   std::cout << "*** original ***" << std::endl;
   testTrie.print();
   std::cout << std::endl << std::endl;
   std::cout << "*** earlier-created copy ***" << std::endl;
   theCopy.print();
   std::cout << std::endl << std::endl;

   std::cout << "*** earlier-created copy ***" << std::endl;
   theEqual.print();
   std::cout << std::endl << std::endl;

   return EXIT_SUCCESS;
}
// *****************************************************
// *                                                   *
// *   array.cpp                                       *
// *                                                   *
// *   Implementation for a generalized array class    *
// *                                                   *
// *   Written June 1998 by Jason Zych                 *
// *                                                   *
// *     - changes by Jason Zych October 1999          *
// *        - added constructor to create an array     *
// *           of size 0                               *
// *       - altered other functions so that an array  *
// *           of size 0 is supported                  *
// *                                                   *
// *     - changes by Jason Zych October 2004          *
// *        - #ifndef macro name changed               *
// *        - const standardized on right of item      *
// *        - comments enhanced                        *
// *        - some code clean-up done                  *
// *        - class changed to typename for generic    *
// *             variable                              *
// *                                                   *
// *     - changes by Jason Zych January 2005          *
// *        - iterators and iterator support functions *
// *             added to class                        *
// *        - put <Etype> qualifier for the name of    *
// *             type into header file                 *
// *                                                   *
// *****************************************************

#include <cstddef>    // for definition of NULL

#include "asserts.h"
#include "array.h"




// ***********************************************************
// *        member functions for the iterator class          *
// ***********************************************************



// iterator
//    - constructor
//    - initializes this iterator to point to NULL
template <typename Etype>
Array<Etype>::iterator::iterator() : ptr(NULL)
{
   // initializer list used above; no code needed here
}


// operator*
//    - return type : a reference to the element type
//    - returns by reference the cell storing the element
//         to which this iterator points.  There is no 
//          error checking done to ensure that this is 
//          a legal cell on which to perform this operation. 
template <typename Etype>
Etype & Array<Etype>::iterator::operator*() 
{ 
   return *ptr;  
}


// operator->
//    - return type : a pointer to the element type
//    - returns a pointer to the cell storing the element
//         to which this iterator points.  There is no 
//          error checking done to ensure that this is 
//          a legal cell on which to perform this operation. 
template <typename Etype>
Etype * Array<Etype>::iterator::operator->()  
{ 
   return ptr; 
}



// operator++ (prefix version)
//    - return type : reference to an iterator
//    - moves this iterator one position forward in the
//          collection it points to, and then returns
//          this iterator after moving it. There is no
//          error checking done to ensure that this is 
//          a legal position at which to perform this 
//          operation.
template <typename Etype>
typename Array<Etype>::iterator & Array<Etype>::iterator::operator++() 
{ 
   ptr = ptr + 1;  // pointer arithmetic, not integer addition
   return *this; 
}


// operator-- (prefix version)
//    - return type: reference to an iterator
//    - moves this iterator one position backward in the
//          collection it points to, and then returns
//          this iterator after moving it. There is no
//          error checking done to ensure that this is 
//          a legal position at which to perform this 
//          operation.
template <typename Etype>
typename Array<Etype>::iterator & Array<Etype>::iterator::operator--() 
{ 
   ptr = ptr - 1;   // pointer arithmetic, not integer addition
   return *this; 
}



// operator++ (postfix version)
//    - parameters : ignore - argument always the integer 1, to 
//                       distinguish this from prefix version
//    - return type : an iterator
//    - moves this iterator one position forward in the 
//          collection it points to, and then returns an
//          iterator to the position this iterator pointed
//          to before this function was run. There is no
//          error checking done to ensure that this is a
//          legal position at which to perform this operation. 
template <typename Etype>
typename Array<Etype>::iterator 
                     Array<Etype>::iterator::operator++(int ignore) 
{
   typename Array<Etype>::iterator temp = *this;
   ptr = ptr + 1;   // pointer arithmetic, not integer addition
   return temp;
}


// operator-- (postfix version)
//    - parameters : ignore - argument always the integer 1, to 
//                       distinguish this from prefix version
//    - return type : an iterator
//    - moves this iterator one position backward in the 
//          collection it points to, and then returns an
//          iterator to the position this iterator pointed
//          to before this function was run. There is no
//          error checking done to ensure that this is a
//          legal position at which to perform this operation. 
template <typename Etype>
typename Array<Etype>::iterator 
                     Array<Etype>::iterator::operator--(int ignore) 
{
   typename Array<Etype>::iterator temp = *this;
   ptr = ptr - 1;  // pointer arithmetic, not integer addition
   return temp;
}


// operator==
//    - parameters : origVal - previously created iterator
//    - return value : boolean with true indicating equality
//    - returns true if this iterator and the parameter
//         iterator point to the same location; else returns false
template <typename Etype>
bool Array<Etype>::iterator::operator==(
                 typename Array<Etype>::iterator const & origVal) const
{ 
   return (ptr == origVal.ptr); 
}


// operator!=
//    - parameters : origVal - previously created iterator
//    - return value : boolean with true indicating inequality
//    - returns true if this iterator and the parameter
//         iterator point different locations; else returns false
template <typename Etype>
bool Array<Etype>::iterator::operator!=(
                 typename Array<Etype>::iterator const & origVal) const
{ 
   return (ptr != origVal.ptr); 
}




// iterator
//    - constructor
//    - parameters : assignPtr - a pointer to the same type
//           that this iterator points to
//    - initializes iterator to point to the same place as
//         the parameter pointer points to
template <typename Etype>
Array<Etype>::iterator::iterator(Etype * assignPtr) : ptr(assignPtr)
{ 
   // initializer list used above; no code needed here
}




// ***********************************************************
// *     member functions for the const_iterator class       *
// ***********************************************************



// const_iterator
//    - constructor
//    - initializes this const_iterator to point to NULL
template <typename Etype>
Array<Etype>::const_iterator::const_iterator() : ptr(NULL)
{
   // initializer list used above; no code needed here
}



// const_iterator
//    - constructor
//    - parameters : theIter - an iterator
//    - initializes this const_iterator to point to the same
//           location as the parameter iterator
template <typename Etype>
Array<Etype>::const_iterator::const_iterator(
        typename Array<Etype>::iterator const & theIter) : ptr(theIter.ptr)
{
   // initializer list used above; no code needed here
}




// operator*
//    - return type : a reference to a value of the element type,
//        a value that cannot be altered through this reference
//    - returns by reference the element to which this
//         const_iterator points; it will not be possible to change
//         that value through the returned reference. There is no 
//         error checking done to ensure that this is a legal cell on 
//         which to perform this operation.
template <typename Etype>
Etype const & Array<Etype>::const_iterator::operator*() const
{ 
   return *ptr;  
}


// operator->
//    - return type : a pointer to a value of the element type,
//        a value that cannot be altered through this pointer
//    - returns a pointer to the element to which this 
//        const_iterator points; it will not be possible to change
//        that value through the returned pointer. There is no error
//        checking done to ensure that this is a legal cell on which
//        to perform this operation.
template <typename Etype>
Etype const * Array<Etype>::const_iterator::operator->() const
{ 
   return ptr; 
}



// operator++ (prefix version)
//    - return type : reference to an const_iterator
//    - moves this const_iterator one position forward in the
//          collection it points to, and then returns
//          this const_iterator after moving it. There is no
//          error checking done to ensure that this is 
//          a legal position at which to perform this 
//          operation.
template <typename Etype>
typename Array<Etype>::const_iterator & 
                      Array<Etype>::const_iterator::operator++() 
{ 
   ptr = ptr + 1;  // pointer arithmetic, not integer addition
   return *this; 
}



// operator-- (prefix version)
//    - return type: reference to an const_iterator
//    - moves this const_iterator one position backward in the
//          collection it points to, and then returns
//          this const_iterator after moving it. There is no
//          error checking done to ensure that this is 
//          a legal position at which to perform this 
//          operation.
template <typename Etype>
typename Array<Etype>::const_iterator & 
                      Array<Etype>::const_iterator::operator--() 
{ 
   ptr = ptr - 1;   // pointer arithmetic, not integer addition
   return *this; 
}



// operator++ (postfix version)
//    - parameters : ignore - argument always the integer 1, to 
//                       distinguish this from prefix version
//    - return type : a const_iterator
//    - moves this const_iterator one position forward in the 
//          collection it points to, and then returns an
//          const_iterator to the position this iterator pointed
//          to before this function was run. There is no
//          error checking done to ensure that this is a
//          legal position at which to perform this operation. 
template <typename Etype>
typename Array<Etype>::const_iterator 
                      Array<Etype>::const_iterator::operator++(int ignore) 
{
   typename Array<Etype>::const_iterator temp = *this;
   ptr = ptr + 1;    //  pointer arithmetic, not integer addition
   return temp;
}


// operator-- (postfix version)
//    - parameters : ignore - argument always the integer 1, to 
//                       distinguish this from prefix version
//    - return type : a const_iterator
//    - moves this const_iterator one position backward in the 
//          collection it points to, and then returns an
//          const_iterator to the position this iterator pointed
//          to before this function was run. There is no
//          error checking done to ensure that this is a
//          legal position at which to perform this operation. 
template <typename Etype>
typename Array<Etype>::const_iterator 
                      Array<Etype>::const_iterator::operator--(int ignore) 
{
   typename Array<Etype>::const_iterator temp = *this;
   ptr = ptr - 1;   // pointer arithmetic, not integer addition
   return temp;
}


// operator==
//    - parameters : origVal - previously created const_iterator
//    - return value : boolean with true indicating equality
//    - returns true if this const_iterator and the parameter
//         const_iterator point to the same location; else returns false
template <typename Etype>
bool Array<Etype>::const_iterator::operator==(
          typename Array<Etype>::const_iterator const & origVal) const
{ 
   return (ptr == origVal.ptr); 
}


// operator!=
//    - parameters : origVal - previously created const_iterator
//    - return value : boolean with true indicating inequality
//    - returns true if this const_iterator and the parameter
//         const_iterator point different locations; else returns false
template <typename Etype>
bool Array<Etype>::const_iterator::operator!=(
            typename Array<Etype>::const_iterator const & origVal) const
{ 
   return (ptr != origVal.ptr); 
}



// const_iterator
//    - constructor
//    - parameters : assignPtr - a const_pointer to the same type
//           that this const_iterator points to
//    - initializes const_iterator to point to the same place as
//         the parameter pointer points to
template <typename Etype>
Array<Etype>::const_iterator::const_iterator(
                               Etype const * assignPtr) : ptr(assignPtr)
{ 
   // initializer list used above; no code needed here
}




// ***********************************************************
// *     member functions for the reverse_iterator class     * 
// ***********************************************************


// reverse_iterator
//    - constructor
//    - initializes this reverse_iterator to point to NULL
template <typename Etype>
Array<Etype>::reverse_iterator::reverse_iterator() : current()
{
   // initializer list used above; no code needed here
}


// operator*
//    - return type : a reference to the element type
//    - returns by reference the cell storing the element
//         to which this reverse_iterator points.  There is
//          no error checking done to ensure that this is
//          a legal cell on which to perform this operation.
template <typename Etype>
Etype & Array<Etype>::reverse_iterator::operator*()
{
   iterator temp = current;
   --temp;
   return *temp;
}


// operator->
//    - return type : a pointer to the element type
//    - returns a pointer to the cell storing the element
//         to which this reverse_iterator points.  There is
//          no error checking done to ensure that this is
//          a legal cell on which to perform this operation.
template <typename Etype>
Etype * Array<Etype>::reverse_iterator::operator->() 
{ 
   return &(this->operator*()); 
}


// operator++ (prefix version)
//    - return type : reference to a reverse_iterator
//    - moves this iterator one position forward in the
//          collection it points to, and then returns
//          this iterator after moving it. There is no
//          error checking done to ensure that this is
//          a legal position at which to perform this
//          operation.
template <typename Etype>
typename Array<Etype>::reverse_iterator &
             Array<Etype>::reverse_iterator::operator++() 
{ 
   --current; 
   return *this; 
}


// operator-- (prefix version)
//    - return type: reference to a reverse_iterator
//    - moves this iterator one position backward in the
//          collection it points to, and then returns
//          this iterator after moving it. There is no
//          error checking done to ensure that this is
//          a legal position at which to perform this
//          operation.
template <typename Etype>
typename Array<Etype>::reverse_iterator &
             Array<Etype>::reverse_iterator::operator--()
{ 
   ++current; 
   return *this; 
}



// operator++ (postfix version)
//    - parameters : ignore - argument always the integer 1, to
//                       distinguish this from prefix version
//    - return type : a reverse_iterator
//    - moves this iterator one position forward in the
//          collection it points to, and then returns an
//          iterator to the position this iterator pointed
//          to before this function was run. There is no
//          error checking done to ensure that this is a
//          legal position at which to perform this operation.
template <typename Etype>
typename Array<Etype>::reverse_iterator 
                      Array<Etype>::reverse_iterator::operator++(int ignore)
{
   typename Array<Etype>::reverse_iterator temp = *this;
   --current;
   return temp;
}


// operator-- (postfix version)
//    - parameters : ignore - argument always the integer 1, to
//                       distinguish this from prefix version
//    - return type : a reverse_iterator
//    - moves this iterator one position backward in the
//          collection it points to, and then returns an
//          iterator to the position this iterator pointed
//          to before this function was run. There is no
//          error checking done to ensure that this is a
//          legal position at which to perform this operation.
template <typename Etype>
typename Array<Etype>::reverse_iterator
                      Array<Etype>::reverse_iterator::operator--(int ignore)
{
   typename Array<Etype>::reverse_iterator temp = *this;
   ++current;
   return temp;
}


// operator==
//    - parameters : origVal - previously created reverse_iterator
//    - return value : boolean with true indicating equality
//    - returns true if this iterator and the parameter
//         iterator point to the same location; else returns false
template <typename Etype>
bool Array<Etype>::reverse_iterator::operator==(
             typename Array<Etype>::reverse_iterator const & origVal) const
{ 
   return (current == origVal.current); 
}



// operator!=
//    - parameters : origVal - previously created reverse_iterator
//    - return value : boolean with true indicating inequality
//    - returns true if this iterator and the parameter
//         iterator point different locations; else returns false
template <typename Etype>
bool Array<Etype>::reverse_iterator::operator!=(
         typename Array<Etype>::reverse_iterator const & origVal) const
{ 
   return (current != origVal.current); 
}




// reverse_iterator
//    - constructor
//    - parameters : assignIter - iterator to the same type of 
//         data to which this reverse_iterator points
//    - initializes this reverse_iterator to point to the same
//       place that the parameter iterator points to
template <typename Etype>
Array<Etype>::reverse_iterator::reverse_iterator(
          typename Array<Etype>::iterator assignIter) : current(assignIter)
{
   // initializer list used above; no code needed here
}







// ***********************************************************
// *  member functions for the const_reverse_iterator class  *
// ***********************************************************


// const_reverse_iterator
//    - constructor
//    - initializes this const_reverse_iterator to point to NULL
template <typename Etype>
Array<Etype>::const_reverse_iterator::const_reverse_iterator() : current()
{
   // initializer list used above; no code needed here
}



// const_reverse_iterator
//    - constructor
//    - parameters : theIter - a reverse_iterator which points
//           to the same time as this const_reverse_iterator
//    - initializes this const_reverse_iterator to point to the
//        same place to which the parameter reverses_iterator
//        points
template <typename Etype>
Array<Etype>::const_reverse_iterator::const_reverse_iterator(
            typename Array<Etype>::reverse_iterator const & theIter) :
                                            current(theIter.current) 
{
   // initializer list used above; no code needed here
}




// operator*
//    - return type : a reference to a value of the element type,
//        a value that cannot be altered through this reference
//    - returns by reference the element to which this
//         const_reverse_iterator points; it will not be possible to 
//         change that value through the returned reference. There is no 
//         error checking done to ensure that this is a legal cell on 
//         which to perform this operation.
template <typename Etype>
Etype const & Array<Etype>::const_reverse_iterator::operator*() const
{
   iterator temp = current;
   --temp;
   return *temp;
}


// operator->
//    - return type : a pointer to a value of the element type,
//        a value that cannot be altered through this pointer
//    - returns a pointer to the element to which this 
//        const_reverse_iterator points; it will not be possible to 
//        change that value through the returned pointer. There is no 
//        error checking done to ensure that this is a legal cell on 
//        which to perform this operation.
template <typename Etype>
Etype const * Array<Etype>::const_reverse_iterator::operator->() const
{ 
   return &(this->operator*()); 
}




// operator++ (prefix version)
//    - return type : reference to a const_reverse_iterator
//    - moves this iterator one position forward in the
//          collection it points to, and then returns
//          this iterator after moving it. There is no
//          error checking done to ensure that this is
//          a legal position at which to perform this
//          operation.
template <typename Etype>
typename Array<Etype>::const_reverse_iterator &
             Array<Etype>::const_reverse_iterator::operator++() 
{ 
   --current; 
   return *this; 
}


// operator-- (prefix version)
//    - return type: reference to a const_reverse_iterator
//    - moves this iterator one position backward in the
//          collection it points to, and then returns
//          this iterator after moving it. There is no
//          error checking done to ensure that this is
//          a legal position at which to perform this
//          operation.
template <typename Etype>
typename Array<Etype>::const_reverse_iterator &
             Array<Etype>::const_reverse_iterator::operator--()
{ 
   ++current; 
   return *this; 
}




// operator++ (postfix version)
//    - parameters : ignore - argument always the integer 1, to
//                       distinguish this from prefix version
//    - return type : a const_reverse_iterator
//    - moves this iterator one position forward in the
//          collection it points to, and then returns an
//          iterator to the position this iterator pointed
//          to before this function was run. There is no
//          error checking done to ensure that this is a
//          legal position at which to perform this operation.
template <typename Etype>
typename Array<Etype>::const_reverse_iterator 
            Array<Etype>::const_reverse_iterator::operator++(int ignore)
{
   const_reverse_iterator temp = *this;
   --current;
   return temp;
}


// operator-- (postfix version)
//    - parameters : ignore - argument always the integer 1, to
//                       distinguish this from prefix version
//    - return type : a const_reverse_iterator
//    - moves this iterator one position backward in the
//          collection it points to, and then returns an
//          iterator to the position this iterator pointed
//          to before this function was run. There is no
//          error checking done to ensure that this is a
//          legal position at which to perform this operation.
template <typename Etype>
typename Array<Etype>::const_reverse_iterator
            Array<Etype>::const_reverse_iterator::operator--(int ignore)
{
   const_reverse_iterator temp = *this;
   ++current;
   return temp;
}


// operator==
//    - parameters : origVal - previously created const_reverse_iterator
//    - return value : boolean with true indicating equality
//    - returns true if this iterator and the parameter
//         iterator point to the same location; else returns false
template <typename Etype>
bool Array<Etype>::const_reverse_iterator::operator==(
        typename Array<Etype>::const_reverse_iterator const & origVal) const
{ 
   return (current == origVal.current); 
}



// operator!=
//    - parameters : origVal - previously created const_reverse_iterator
//    - return value : boolean with true indicating inequality
//    - returns true if this iterator and the parameter
//         iterator point different locations; else returns false
template <typename Etype>
bool Array<Etype>::const_reverse_iterator::operator!=(
        typename Array<Etype>::const_reverse_iterator const & origVal) const
{ 
   return (current != origVal.current); 
}




// ***********************************************************
// *         member functions for the Array class           *
// ***********************************************************


// ***** Constructors, etc.


// Array
//    - constructor
//    - initializes object to be a zero-element array; low and high
//        indices will be 0 and -1, respectively
template <typename Etype>
Array<Etype>::Array()
{
   lowerBound = 0;
   upperBound = -1;
   data = NULL;
   onePastLast = NULL;
}




// Array
//    - constructor
//    - parameters : low - desired lower bound of array
//                 : high - desired higher bound of array
//    - high is required to be greater than or equal to low - 1; if it
//       is not, an assertion is triggered. Assuming high >= low - 1,
//        initializes object to be a (high - low + 1)-element array; cells
//        themselves are uninitialized (for primitive types) or
//        initialized using the no-argument constructor (for non-primitive
//        types). Note that if high == low - 1, then the value of the
//        expression high - low + 1 is 0 and we create an Array object
//        without any legal indices
template <typename Etype>
Array<Etype>::Array(int low, int high)
{
   Assert(high >= low - 1, "Array: illegal bounds in Array(int, int)");
   lowerBound = low;
   upperBound = high;

   // When we create array below, all values in array cells are 
   // automatically initialized using no-argument constructor of
   // Etype (if Etype is a primitive type, this no-argument constructor 
   // does nothing, so cells hold garbage)
   data = new Etype[upperBound - lowerBound + 1]; 

   onePastLast = data + (upperBound - lowerBound + 1);
}




// Array
//    - constructor
//    - parameters : origVal - reference to previously-created Array
//                    object; that Array object cannot be changed through
//                    the parameter reference
//    - initializes array to be a copy of origVal
template <typename Etype>
Array<Etype>::Array(Array<Etype> const & origVal)
{
   // set the bounds of the array
   lowerBound = origVal.lowerBound;  
   upperBound = origVal.upperBound;   

   if (lowerBound <= upperBound)
   {
      data = new Etype[upperBound - lowerBound + 1];  
      for (int i = lowerBound; i <= upperBound; ++i)
         data[i - lowerBound] = (origVal.data)[i - lowerBound];
      onePastLast = data + (upperBound - lowerBound + 1);
   }
   else    // lowerBound > upperBound ===> lowerBound - 1 == upperBound
   {
      data = NULL;
      onePastLast = NULL;
   }
}


 
// ~Array
//    - destructor
//    - deletes dynamically allocated memory
template <typename Etype>
Array<Etype>::~Array() 
{
   delete[] data;
}




// operator=
//    - parameters : origVal - reference to previously-created Array
//                    object; that Array object cannot be changed through
//                    the parameter reference
//    - return value : reference to this Array object, after the
//        assignment operation has been performed; we cannot change this 
//        object through the returned reference
//    - assigns this object to be a copy of origVal
template <typename Etype>
Array<Etype> const & Array<Etype>::operator=(Array<Etype> const & origVal)
{
   if (this != &origVal)  // self-assignment check
   {
      delete[] data;

      // set the bounds of the array  
      lowerBound = origVal.lowerBound;
      upperBound = origVal.upperBound;

      if (lowerBound <= upperBound)
      {
         data = new Etype[upperBound - lowerBound + 1];
         for (int i = lowerBound; i <= upperBound; ++i)
            data[i - lowerBound] = (origVal.data)[i - lowerBound];
         onePastLast = data + (upperBound - lowerBound + 1);
      }
      else
      {
         data = NULL;
         onePastLast = NULL;
      }
   }	
   return *this;
}



// ****** information access/manipulation


// operator[]
//    - parameters : index - integer index into array
//    - return type : reference to the array cell at the parameter index;
//         value stored in array cell cannot be changed through the
//         returned reference
//    - This version of the operator[] will be called on const objects.
//       The parameter index is required to be a legal index into the
//       array, i.e. lowerBound <= index and index <= upperBound. (Note 
//       that for arrays of size 0, there *is* no legal index.) If the 
//       index is NOT legal, an assertion is triggered. Otherwise, the 
//       function returns a reference to the array cell at the given 
//       index, but the array cell is const (i.e. its value cannot be 
//       changed if accessed through the returned index.
template <typename Etype>
Etype const & Array<Etype>::operator[](int index) const
{
   Assert((lowerBound <= index) && (index <= upperBound), 
                         "Array: illegal index in operator[](int) const");
   return (data[index - lowerBound]);
}




// operator[]
//    - parameters : index - integer index into array
//    - return type : reference to the array cell at the parameter index
//    - This version of the operator[] will be called on non-const objects.
//       The parameter index is required to be a legal index into the
//       array, i.e. lowerBound <= index and index <= upperBound. (Note
//       that for arrays of size 0, there *is* no legal index.) If the
//       index is NOT legal, an assertion is triggered. Otherwise, the
//       function returns a reference to the array cell at the given index.
template <typename Etype>
Etype & Array<Etype>::operator[](int index) 
{
   Assert((lowerBound <= index) && (index <= upperBound), 
                         "Array: illegal index in operator[](int)");
   return (data[index - lowerBound]);
}





// initialize
//    - parameters : initElement - reference to object with which to
//                     initialize the array; that object cannot be
//                     changed through the parameter reference
//    - assigns each cell in the array to hold a copy of parameter value
template <typename Etype>
void Array<Etype>::initialize(Etype const & initElement)
{
   for (int i = lowerBound; i <= upperBound; ++i)
      data[i - lowerBound] = initElement;
}



// setBounds
//    - parameters : theLow - desired new lower bound of array
//                 : theHigh - desired new upper bound of array
//    - theHigh is required to be greater than or equal to theLow - 1; 
//        if it is not, an assertion is triggered. Assuming
//        theHigh >= theLow - 1,assigns object to be a 
//        (theHigh - theLow + 1)-element array. For any indices in
//        the array's new index range (theLow <= index <= theHigh) that 
//        were also in the array's old index range 
//        (lower() <= index <= upper()), the cells at those contain the
//        same values that they contained before this function was called. 
//        For any indices in the array's new index range that were NOT 
//        in the array's old index range, the cells at those indices are 
//        uninitialized (for primitive types) or initialized using the
//        no-argument constructor (for non-primitive types). For any 
//        indices in the array's old index range that are NOT indices in
//        the array's new index range, the values in the cells at those
//        indices are lost, since we no longer have cells with those 
//        indices in our array.
template <typename Etype>
void Array<Etype>::setBounds(int theLow, int theHigh)
{
   Assert(theHigh >= theLow - 1, 
                      "Array: illegal bounds in setBounds(int, int)");

   // create the new array; our member variable "data" will 
   //   ultimately point to this new array
   Etype * newData;
   int newSize = theHigh - theLow + 1;
   if (newSize == 0)
      newData = NULL; 
   else
      newData = new Etype[newSize]; // all values automatically initialized
                                    //  using no-argument constructor of Etype
                                    //  (if Etype is a primitive type, this
                                    //  no-argument constructor does nothing,
                                    //  so cells hold garbage)


   // Deal with the intersection of old and new ranges, if there is one.
   // If one or both of the ranges is size 0, there definitely isn't any
   // intersection. Otherwise, we need to check.
   int lowIntersect, highIntersect;
   if ((theHigh >= theLow) && (upperBound >= lowerBound)) // both size >= 1
   {
      // greater of two low values is low bound of intersection
      if (theLow > lowerBound)
         lowIntersect = theLow;        // new low value
      else
         lowIntersect = lowerBound;    // old low value

      // lowerBound of two high values is high bound of intersection
      if (theHigh < upperBound)
         highIntersect = theHigh;      // new high value
      else
         highIntersect = upperBound;   // old high value
  
      // Transfer data from old to new.
      for (int i = lowIntersect; i <= highIntersect; ++i)
         newData[i - theLow] = data[i - lowerBound];
   }

   delete[] data;    // deallocate old array
   data = newData;   // the new array is now this object's array
   lowerBound = theLow;      // set internal bounds to be equal
   upperBound = theHigh;     //    to the parameter bounds
   onePastLast = data + (upperBound - lowerBound + 1);  // set "end" pointer
}
 

 
 
// size
//    - return value : non-negative integer
//    - returns size of array
template <typename Etype>
int Array<Etype>::size() const 
{
   return (upperBound - lowerBound + 1);
}



// lower
//    - return value : integer index
//    - returns "lower bound" index of array. If array has size >= 1,
//        this will be lowest legal index of array. If array is of 
//        size 0, then this will be an integer one greater than the
//        value returned by upper(), but will not be a legal index.
template <typename Etype>
int Array<Etype>::lower() const 
{ 
   return lowerBound;
}



// upper
//    - return value : integer index
//    - returns "upper bound" of array. If array has size >= 1,
//        this will be highest legal index of array. If array is of
//        size 0, then this will be an integer one less than the
//        value returned by lower(), but will not be a legal index.
template <typename Etype>
int Array<Etype>::upper() const 
{
   return upperBound;
}




// ****************** iterator functions


// begin
//    - return type : iterator
//    - returns an iterator that points to first
//        cell of Array
template <typename Etype>
typename Array<Etype>::iterator Array<Etype>::begin()
{
   return iterator(data);
}



// begin
//    - return type : const_iterator
//    - returns a const_iterator that points to first
//        cell of Array
template <typename Etype>
typename Array<Etype>::const_iterator Array<Etype>::begin() const
{
   return iterator(data);
}




// end
//    - return type : iterator
//    - returns an iterator that points to "after the last cell"
//        so we know we are "off the Array".
template <typename Etype>
typename Array<Etype>::iterator Array<Etype>::end()
{
   // Our functions will treat finish as an iterator
   //   to the cell right after the last one filled
   return iterator(onePastLast);
}



// end
//    - return type : const_iterator
//    - returns an const_iterator that points to "after the last cell"
//        so we know we are "off the Array".
template <typename Etype>
typename Array<Etype>::const_iterator Array<Etype>::end() const
{
   // Our functions will treat finish as an iterator
   //   to the cell right after the last one filled
   return iterator(onePastLast);
}



// rbegin
//    - return type : reverse iterator
//    - returns a reverse iterator that points to
//        first cell of abstract "reverse Array", i.e.
//        last real cell of Array
template <typename Etype>
typename Array<Etype>::reverse_iterator Array<Etype>::rbegin()
{
   return reverse_iterator(onePastLast);
}



// rbegin
//    - return type : const_reverse_iterator
//    - returns a const_reverse_iterator that points to
//        first cell of abstract "reverse Array", i.e.
//        last real cell of Array
template <typename Etype>
typename Array<Etype>::const_reverse_iterator Array<Etype>::rbegin() const
{
   return reverse_iterator(onePastLast);
}




// rend
//    - return type : reverse_iterator
//    - returns a reverse iterator that points to
//        "end position" of abstract "reverse Array",
//         i.e. the abstract "before first cell"
//         spot in Array
template <typename Etype>
typename Array<Etype>::reverse_iterator Array<Etype>::rend()
{
   return reverse_iterator(data);
}



// rend
//    - return type : const_reverse_iterator
//    - returns a const_reverse_iterator that points to
//        "end position" of abstract "reverse Array",
//         i.e. the abstract "before first cell"
//         spot in Array
template <typename Etype>
typename Array<Etype>::const_reverse_iterator Array<Etype>::rend() const
{
   return reverse_iterator(data);
}



// *****************************************************
// *                                                   *
// *   array.h                                         *
// *                                                   *
// *   Interface for a generalized array class         *
// *                                                   *
// *   Written June 1998 by Jason Zych                 *
// *                                                   *
// *     - changes by Jason Zych October 1999          *
// *        - added constructor to create an array     *
// *           of size 0                               *
// *       - altered other functions so that an array  *
// *           of size 0 is supported                  *
// *                                                   *
// *     - changes by Jason Zych October 2004          *
// *        - #ifndef macro name changed               *
// *        - const standardized on right of item      *
// *        - comments enhanced                        *
// *        - some code clean-up done                  *
// *        - class changed to typename for generic    *
// *             variable                              *
// *                                                   *
// *     - changes by Jason Zych January 2005          *
// *        - iterators and iterator support functions *
// *             added to class                        *
// *        - put <Etype> qualifier for the name of    *
// *             type into header file                 *
// *                                                   *
// *****************************************************

/*  
   TO THE CS225 STUDENT:

   See the vector225.h file for a full description of the
   standard container class typedefs and iterators.

*/


#ifndef ARRAY_225_H
#define ARRAY_225_H

template <typename Etype>
class Array
{
public:


   // ************************
   // *                      *
   // *  typedefs            *
   // *                      *
   // ************************

   typedef Etype value_type;      
   typedef Etype * pointer;        
   typedef Etype & reference;     
   typedef Etype const * const_pointer;
   typedef Etype const & const_reference;



   // *********************************************
   // *                                           *
   // *  Array<>::iterator                        *
   // *                                           *
   // *  iterator for our Array class.            *
   // *                                           *
   // *********************************************

   class iterator 
   {
   public:

      // typedefs
      typedef Etype value_type;
      typedef Etype * pointer;
      typedef Etype & reference;


      // iterator
      //    - constructor
      //    - initializes this iterator to point to NULL
      iterator();


      // operator*
      //    - return type : a reference to the element type
      //    - returns by reference the cell storing the element
      //         to which this iterator points.  There is no
      //          error checking done to ensure that this is 
      //          a legal cell on which to perform this operation. 
      Etype & operator*();

     
      // operator->
      //    - return type : a pointer to the element type
      //    - returns a pointer to the cell storing the element
      //         to which this iterator points.  There is no
      //          error checking done to ensure that this is 
      //          a legal cell on which to perform this operation. 
      Etype * operator->();

      
      // operator++ (prefix version)
      //    - return type : reference to an iterator
      //    - moves this iterator one position forward in the
      //          collection it points to, and then returns
      //          this iterator after moving it. There is no
      //          error checking done to ensure that this is 
      //          a legal position at which to perform this 
      //          operation.  
      typename Array<Etype>::iterator & operator++();

 
      // operator-- (prefix version)
      //    - return type: reference to an iterator     
      //    - moves this iterator one position backward in the
      //          collection it points to, and then returns
      //          this iterator after moving it. There is no
      //          error checking done to ensure that this is 
      //          a legal position at which to perform this 
      //          operation.
      typename Array<Etype>::iterator & operator--();


      // operator++ (postfix version)
      //    - parameters : ignore - argument always the integer 1, to 
      //                       distinguish this from prefix version
      //    - return type : an iterator
      //    - moves this iterator one position forward in the 
      //          collection it points to, and then returns an
      //          iterator to the position this iterator pointed
      //          to before this function was run. There is no
      //          error checking done to ensure that this is a
      //          legal position at which to perform this operation. 
      typename Array<Etype>::iterator operator++(int ignore);


      // operator-- (postfix version)
      //    - parameters : ignore - argument always the integer 1, to 
      //                       distinguish this from prefix version
      //    - return type : an iterator
      //    - moves this iterator one position backward in the 
      //          collection it points to, and then returns an
      //          iterator to the position this iterator pointed
      //          to before this function was run. There is no
      //          error checking done to ensure that this is a
      //          legal position at which to perform this operation. 
      typename Array<Etype>::iterator operator--(int ignore); 


      // operator==
      //    - parameters : origVal - previously created iterator
      //    - return value : boolean with true indicating inequality
      //    - returns true if this iterator and the parameter 
      //         iterator point to the same location; else returns false
      bool operator==(typename Array<Etype>::iterator const & origVal) const;


      // operator!=
      //    - parameters : origVal - previously created iterator
      //    - return value : boolean with true indicating inequality
      //    - returns true if this iterator and the parameter 
      //         iterator point different locations; else returns false
      bool operator!=(typename Array<Etype>::iterator const & origVal) const;


   private:

      Etype * ptr;   // pointer to whatever type of value this
                     // iterator is meant to point to; the entire 
                     // iterator object is basically a wrapper for 
                     // this pointer.


      // iterator
      //    - constructor
      //    - parameters : assignPtr - a pointer to the same type
      //           that this iterator points to
      //    - initializes iterator to point to the same place as
      //         the parameter pointer points to
      iterator(Etype * assignPtr);


      // these lines give the Array class and the const_iterator class
      //   access to the above private members of iterator
      friend class Array<Etype>;
      friend class Array<Etype>::const_iterator;
   };




   // *********************************************
   // *                                           *
   // *  Array<>::const_iterator                  *
   // *                                           *
   // *  const_iterator for our Array class.      *
   // *                                           *
   // *********************************************

   class const_iterator
   {
   public:

      // typedefs
      typedef Etype value_type;
      typedef Etype const * const_pointer;
      typedef Etype const & const_reference;


      // const_iterator
      //    - constructor
      //    - initializes this iterator to point to NULL
      const_iterator();


      // const_iterator
      //    - constructor
      //    - parameters : theIter - an iterator
      //    - initializes this const_iterator to point to the same
      //           location as the parameter iterator
      const_iterator(typename Array<Etype>::iterator const & theIter);


      // operator*
      //    - return type : a reference to a value of the element type,
      //        a value that cannot be altered through this reference
      //    - returns by reference the element to which this
      //         const_iterator points; it will not be possible to change
      //         that value through the returned reference. There is no 
      //         error checking done to ensure that this is a legal cell on 
      //         which to perform this operation.
      Etype const & operator*() const;


      // operator->
      //    - return type : a pointer to a value of the element type,
      //        a value that cannot be altered through this pointer
      //    - returns a pointer to the element to which this 
      //        const_iterator points; it will not be possible to change
      //        that value through the returned pointer. There is no error
      //        checking done to ensure that this is a legal cell on which
      //        to perform this operation.
      Etype const * operator->() const;


      // operator++ (prefix version)
      //    - return type : reference to a const_iterator
      //    - moves this iterator one position forward in the
      //          collection it points to, and then returns
      //          this iterator after moving it. There is no
      //          error checking done to ensure that this is 
      //          a legal position at which to perform this 
      //          operation.  
      typename Array<Etype>::const_iterator & operator++();


      // operator-- (prefix version)
      //    - return type: reference to a const_iterator     
      //    - moves this iterator one position backward in the
      //          collection it points to, and then returns
      //          this iterator after moving it. There is no
      //          error checking done to ensure that this is 
      //          a legal position at which to perform this 
      //          operation.
      typename Array<Etype>::const_iterator & operator--();


      // operator++ (postfix version)
      //    - parameters : ignore - argument always the integer 1, to 
      //                       distinguish this from prefix version
      //    - return type : a const_iterator
      //    - moves this iterator one position forward in the 
      //          collection it points to, and then returns an
      //          iterator to the position this iterator pointed
      //          to before this function was run. There is no
      //          error checking done to ensure that this is a
      //          legal position at which to perform this operation. 
      typename Array<Etype>::const_iterator operator++(int ignore);


      // operator-- (postfix version)
      //    - parameters : ignore - argument always the integer 1, to 
      //                       distinguish this from prefix version
      //    - return type : a const_iterator
      //    - moves this iterator one position backward in the 
      //          collection it points to, and then returns an
      //          iterator to the position this iterator pointed
      //          to before this function was run. There is no
      //          error checking done to ensure that this is a
      //          legal position at which to perform this operation. 
      typename Array<Etype>::const_iterator operator--(int ignore);


      // operator==
      //    - parameters : origVal - previously created const_iterator
      //    - return value : boolean with true indicating equality
      //    - returns true if this iterator and the parameter 
      //         iterator point to the same location; else returns false
      bool operator==(
              typename Array<Etype>::const_iterator const & origVal) const;


      // operator!=
      //    - parameters : origVal - previously created const_iterator
      //    - return value : boolean with true indicating inequality 
      //    - returns true if this iterator and the parameter 
      //         iterator point different locations; else returns false
      bool operator!=(
              typename Array<Etype>::const_iterator const & origVal) const;



   private:


      Etype * ptr;   // pointer to whatever type of value this
                     // const_iterator is meant to point to; the entire 
                     // const_iterator object is basically a wrapper for 
                     // this pointer.


      // const_iterator
      //    - constructor
      //    - parameters : assignPtr - a const_pointer to the same type
      //           that this const_iterator points to
      //    - initializes const_iterator to point to the same place as
      //         the parameter pointer points to
      const_iterator(Etype const * assignPtr);



      // these lines give the Array class access to the above
      // private members of iterator
      friend class Array<Etype>;
   };





   // ***********************************************
   // *                                             *
   // *  Array<>::reverse_iterator                  *
   // *                                             *
   // *  Reverse iterator for our Array class.      *
   // *                                             *
   // ***********************************************

   class reverse_iterator
   {
   public:

      // typedefs
      typedef Etype value_type;
      typedef Etype * pointer;
      typedef Etype & reference;


      // reverse_iterator
      //    - constructor
      //    - initializes this reverse_iterator to point to NULL
      reverse_iterator();


      // operator*
      //    - return type : a reference to the element type
      //    - returns by reference the cell storing the element
      //         to which this reverse_iterator points.  There is 
      //          no error checking done to ensure that this is 
      //          a legal cell on which to perform this operation. 
      Etype & operator*();


      // operator->
      //    - return type : a pointer to the element type
      //    - returns a pointer to the cell storing the element
      //         to which this reverse_iterator points.  There is 
      //          no error checking done to ensure that this is 
      //          a legal cell on which to perform this operation. 
      Etype * operator->();


      // operator++ (prefix version)
      //    - return type : reference to a reverse_iterator
      //    - moves this iterator one position forward in the
      //          collection it points to, and then returns
      //          this iterator after moving it. There is no
      //          error checking done to ensure that this is 
      //          a legal position at which to perform this 
      //          operation.  
      typename Array<Etype>::reverse_iterator & operator++();


      // operator-- (prefix version)
      //    - return type: reference to a reverse_iterator     
      //    - moves this iterator one position backward in the
      //          collection it points to, and then returns
      //          this iterator after moving it. There is no
      //          error checking done to ensure that this is 
      //          a legal position at which to perform this 
      //          operation.
      typename Array<Etype>::reverse_iterator & operator--();


      // operator++ (postfix version)
      //    - parameters : ignore - argument always the integer 1, to 
      //                       distinguish this from prefix version
      //    - return type : a reverse_iterator
      //    - moves this iterator one position forward in the 
      //          collection it points to, and then returns an
      //          iterator to the position this iterator pointed
      //          to before this function was run. There is no
      //          error checking done to ensure that this is a
      //          legal position at which to perform this operation. 
      typename Array<Etype>::reverse_iterator operator++(int ignore);


      // operator-- (postfix version)
      //    - parameters : ignore - argument always the integer 1, to 
      //                       distinguish this from prefix version
      //    - return type : a reverse_iterator
      //    - moves this iterator one position backward in the 
      //          collection it points to, and then returns an
      //          iterator to the position this iterator pointed
      //          to before this function was run. There is no
      //          error checking done to ensure that this is a
      //          legal position at which to perform this operation. 
      typename Array<Etype>::reverse_iterator operator--(int ignore);


      // operator==
      //    - parameters : origVal - previously created reverse_iterator
      //    - return value : boolean with true indicating equality
      //    - returns true if this iterator and the parameter 
      //         iterator point to the same location; else returns false
      bool operator==(
              typename Array<Etype>::reverse_iterator const & origVal) const;

 
      // operator!=
      //    - parameters : origVal - previously created reverse_iterator
      //    - return value : boolean with true indicating inequality 
      //    - returns true if this iterator and the parameter 
      //         iterator point different locations; else returns false
      bool operator!=(
              typename Array<Etype>::reverse_iterator const & origVal) const;

    
   private:

      // reverse iterators are implemented by using an iterator to 
      // the position to the right of where we want the reverse 
      // iterator to be. Then when dereferencing the reverse_iterator,
      // we return the value to the left of current
      typename Array<Etype>::iterator current;  


      // reverse_iterator
      //    - constructor
      //    - parameters : assignIter - iterator to the same type of
      //         data to which this reverse_iterator points 
      //    - initializes this reverse_iterator to point to the same
      //       place that the parameter iterator points to
      reverse_iterator(typename Array<Etype>::iterator assignIter);


      // these lines give the Array class and the const_reverse_iterator
      //   class access to the above private members of reverse_iterator
      friend class Array<Etype>;
      friend class Array<Etype>::const_reverse_iterator;
   };


   // ************************************************
   // *                                              *
   // *  Array<>::const_reverse_iterator             *
   // *                                              *
   // *  const_reverse_iterator for our Array class  *
   // *                                              *
   // ************************************************

   class const_reverse_iterator
   {
   public:

      // typedefs
      typedef Etype value_type;
      typedef Etype const * const_pointer;
      typedef Etype const & const_reference;


      // const_reverse_iterator
      //    - constructor
      //    - initializes this const_reverse_iterator to NULL
      const_reverse_iterator();


      // const_reverse_iterator
      //    - constructor
      //    - parameters : theIter - a reverse_iterator which points
      //           to the same time as this const_reverse_iterator
      //    - initializes this const_reverse_iterator to point to the
      //        same place to which the parameter reverses_iterator
      //        points
      const_reverse_iterator(
            typename Array<Etype>::reverse_iterator const & theIter);


      // operator*
      //    - return type : a reference to a value of the element type,
      //        a value that cannot be altered through this reference
      //    - returns by reference the element to which this
      //         const_reverse_iterator points; it will not be possible to 
      //         change that value through the returned reference. There is no 
      //         error checking done to ensure that this is a legal cell on 
      //         which to perform this operation.
      Etype const & operator*() const;


      // operator->
      //    - return type : a pointer to a value of the element type,
      //        a value that cannot be altered through this pointer
      //    - returns a pointer to the element to which this 
      //        const_reverse_iterator points; it will not be possible to 
      //        change that value through the returned pointer. There is no 
      //        error checking done to ensure that this is a legal cell on 
      //        which to perform this operation.
      Etype const * operator->() const;


      // operator++ (prefix version)
      //    - return type : reference to a const_reverse_iterator
      //    - moves this iterator one position forward in the
      //          collection it points to, and then returns
      //          this iterator after moving it. There is no
      //          error checking done to ensure that this is 
      //          a legal position at which to perform this 
      //          operation.  
      typename Array<Etype>::const_reverse_iterator & operator++();


      // operator-- (prefix version)
      //    - return type: reference to a const_reverse_iterator     
      //    - moves this iterator one position backward in the
      //          collection it points to, and then returns
      //          this iterator after moving it. There is no
      //          error checking done to ensure that this is 
      //          a legal position at which to perform this 
      //          operation.
      typename Array<Etype>::const_reverse_iterator & operator--();


      // operator++ (postfix version)
      //    - parameters : ignore - argument always the integer 1, to 
      //                       distinguish this from prefix version
      //    - return type : a const_reverse_iterator
      //    - moves this iterator one position forward in the 
      //          collection it points to, and then returns an
      //          iterator to the position this iterator pointed
      //          to before this function was run. There is no
      //          error checking done to ensure that this is a
      //          legal position at which to perform this operation. 
      typename Array<Etype>::const_reverse_iterator operator++(int ignore);


      // operator-- (postfix version)
      //    - parameters : ignore - argument always the integer 1, to 
      //                       distinguish this from prefix version
      //    - return type : a const_reverse_iterator
      //    - moves this iterator one position backward in the 
      //          collection it points to, and then returns an
      //          iterator to the position this iterator pointed
      //          to before this function was run. There is no
      //          error checking done to ensure that this is a
      //          legal position at which to perform this operation. 
      typename Array<Etype>::const_reverse_iterator operator--(int ignore);


      // operator==
      //    - parameters : origVal - previously created const_reverse_iterator
      //    - return value : boolean with true indicating equality 
      //    - returns true if this iterator and the parameter 
      //         iterator point to the same location; else returns false
      bool operator==(
         typename Array<Etype>::const_reverse_iterator const & origVal) const;


      // operator!=
      //    - parameters : origVal - previously created const_reverse_iterator
      //    - return value : boolean with true indicating inequality
      //    - returns true if this iterator and the parameter 
      //         iterator point different locations; else returns false
      bool operator!=(
         typename Array<Etype>::const_reverse_iterator const & origVal) const;



   private:

      // reverse iterators are implemented by using an iterator to 
      // the position to the right of where we want the reverse 
      // iterator to be. Then when dereferencing the reverse_iterator,
      // we return the value to the left of current
      typename Array<Etype>::iterator current;  


      // these lines give the Array class access to the
      //   above private members of const_reverse_iterator
      friend class Array<Etype>;

   };



  

   // ************************
   // *                      *
   // *  Array functions     *
   // *                      *
   // ************************


   // ***** Constructors, etc.

   // Array
   //    - constructor
   //    - initializes object to be a zero-element array; low and high
   //        indices will be 0 and -1, respectively
   Array();


   // Array
   //    - constructor
   //    - parameters : low - desired lower bound of array 
   //                 : high - desired higher bound of array
   //    - high is required to be greater than or equal to low - 1; if it
   //       is not, an assertion is triggered. Assuming high >= low - 1,
   //        initializes object to be a (high - low + 1)-element array; cells 
   //        themselves are uninitialized (for primitive types) or 
   //        initialized using the no-argument constructor (for non-primitive 
   //        types). Note that if high == low - 1, then the value of the 
   //        expression high - low + 1 is 0 and we create an Array object
   //        without any legal indices
   Array(int low, int high); 


   // Array
   //    - constructor
   //    - parameters : origVal - reference to previously-created Array
   //                    object; that Array object cannot be changed through
   //                    the parameter reference
   //    - initializes array to be a copy of origVal	
   Array(Array<Etype> const & origVal);

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


   // operator=
   //    - parameters : origVal - reference to previously-created Array
   //                    object; that Array object cannot be changed through
   //                    the parameter reference
   //    - return value : reference to this Array object, after the
   //        assignment operation has been performed; we cannot change this 
   //        object through the returned reference
   //    - assigns this object to be a copy of origVal
   Array<Etype> const & operator=(Array<Etype> const & origVal);


   // ****** information access/manipulation
 

   // operator[]
   //    - parameters : index - integer index into array
   //    - return type : reference to the array cell at the parameter index;
   //         value stored in array cell cannot be changed through the 
   //         returned reference
   //    - This version of the operator[] will be called on const objects.
   //       The parameter index is required to be a legal index into the
   //       array, i.e. lowerBound <= index and index <= upperBound. (Note 
   //       that for arrays of size 0, there *is* no legal index.) If the 
   //       index is NOT legal, an assertion is triggered. Otherwise, the 
   //       function returns a reference to the array cell at the given 
   //       index, but the array cell is const (i.e. its value cannot be 
   //       changed if accessed through the returned index.  
   Etype const & operator[](int index) const;					


   // operator[]
   //    - parameters : index - integer index into array
   //    - return type : reference to the array cell at the parameter index
   //    - This version of the operator[] will be called on non-const objects.
   //       The parameter index is required to be a legal index into the
   //       array, i.e. lowerBound <= index and index <= upperBound. (Note
   //       that for arrays of size 0, there *is* no legal index.) If the
   //       index is NOT legal, an assertion is triggered. Otherwise, the
   //       function returns a reference to the array cell at the given index.
   Etype & operator[](int index);


   // initialize
   //    - parameters : initElement - reference to object with which to 
   //                     initialize the array; that object cannot be
   //                     changed through the parameter reference
   //    - assigns each cell in the array to hold a copy of parameter value
   void initialize(Etype const & initElement);


   // setBounds
   //    - parameters : theLow - desired new lower bound of array
   //                 : theHigh - desired new upper bound of array
   //    - theHigh is required to be greater than or equal to theLow - 1;  
   //        if it is not, an assertion is triggered. Assuming 
   //        theHigh >= theLow - 1,assigns object to be a 
   //        (theHigh - theLow + 1)-element array. For any indices in 
   //        the array's new index range (theLow <= index <= theHigh) that 
   //        were also in the array's old index range 
   //        (lower() <= index <= upper()), the cells at those contain the 
   //        same values that they contained before this function was called. 
   //        For any indices in the array's new index range that were NOT 
   //        in the array's old index range, the cells at those indices are 
   //        uninitialized (for primitive types) or initialized using the
   //        no-argument constructor (for non-primitive types). For any 
   //        indices in the array's old index range that are NOT indices in
   //        the array's new index range, the values in the cells at those
   //        indices are lost, since we no longer have cells with those 
   //        indices in our array.
   void setBounds(int theLow, int theHigh);


   // size
   //    - return value : non-negative integer
   //    - returns size of array  
   int size() const; 


   // lower
   //    - return value : integer index
   //    - returns "lower bound" index of array. If array has size >= 1,
   //        this will be lowest legal index of array. If array is of 
   //        size 0, then this will be an integer one greater than the
   //        value returned by upper(), but will not be a legal index.
   int lower() const; 


   // upper
   //    - return value : integer index
   //    - returns "upper bound" of array. If array has size >= 1,
   //        this will be highest legal index of array. If array is of
   //        size 0, then this will be an integer one less than the
   //        value returned by lower(), but will not be a legal index.
   int upper() const; 



   // ******* iterator functions

   // begin
   //    - return type : iterator
   //    - returns an iterator that points to first
   //        cell of Array
   typename Array<Etype>::iterator begin();


   // begin
   //    - return type : const_iterator
   //    - returns a const_iterator that points to first
   //        cell of Array
   typename Array<Etype>::const_iterator begin() const;


   // end
   //    - return type : iterator
   //    - returns an iterator that points to "after the last cell"
   //        so we know we are "off the Array".
   typename Array<Etype>::iterator end();


   // end
   //    - return type : const_iterator
   //    - returns an const_iterator that points to "after the last cell"
   //        so we know we are "off the Array".
   typename Array<Etype>::const_iterator end() const;


   // rbegin
   //    - return type : reverse iterator
   //    - returns a reverse iterator that points to
   //        first cell of abstract "reverse Array", i.e.
   //        last real cell of Array
   typename Array<Etype>::reverse_iterator rbegin();


   // rbegin
   //    - return type : const_reverse_iterator
   //    - returns a const_reverse_iterator that points to
   //        first cell of abstract "reverse Array", i.e.
   //        last real cell of Array
   typename Array<Etype>::const_reverse_iterator rbegin() const;


   // rend
   //    - return type : reverse iterator
   //    - returns a reverse iterator that points to
   //        "end position" of abstract "reverse Array",
   //         i.e. the abstract "before first cell" 
   //         spot in Array 
   typename Array<Etype>::reverse_iterator rend();


   // rend
   //    - return type : const_reverse_iterator
   //    - returns a const_reverse_iterator that points to
   //        "end position" of abstract "reverse Array",
   //         i.e. the abstract "before first cell"
   //         spot in Array
   typename Array<Etype>::const_reverse_iterator rend() const;


private:

   int lowerBound;       // lower bound 
   int upperBound;       // upper bound
   Etype * data;         // pointer to the start of the array elements. 
   Etype * onePastLast;  // pointer to the memory one past end of array

};


#endif
// ***********************************************************
// *                                                         *
// *   asserts.cpp                                           *
// *                                                         *
// *   Implementation for error alert functions              *
// *                                                         *
// *   Written September 2003 by Jason Zych                  *
// *                                                         *            
// *     - changes by Jason Zych October 2004:               *
// *        - changed ints-as-booleans to bool               *
// *        - standardized const on right of item            *
// *        - enhanced comments                              *
// *        - #ifndef macro changed                          *
// *        - EXIT_FAILURE used as return value              *
// *                                                         *
// ***********************************************************

// *** includes of files in the standard library

#include <cstdlib>     // contains exit() function and EXIT_FAILURE flag
#include <iostream>    // contains output stream tools (such as cerr)

// lack of the line
//     using namespace std;
// here means we have to have "std::" in front of all usages 
// of cerr and endl below. If we indicated we were using the
// "std" namespace, then we automatically get to use everything
// in that namespace -- including cerr and endl -- without 
// specifically noting that it is from the std namespace.


// *** includes of our own declarations

#include "asserts.h"       // contains declarations for the four 
                           //   functions defined below


// Assert
//    - parameters : safeCondition - value of a boolean expression
//                 : errorMessage - a pointer to a character array 
//                    containing an error message to print out;
//                    we cannot change this character array through
//                    this pointer
//    - if safeCondition is true, do nothing. Otherwise, print
//              errorMessage with specific formatting, and then 
//              forcefully exit the program with error status flag.
void Assert(bool safeCondition, char const * errorMessage)
{
   if (!safeCondition)
   {
      std::cerr << "***Error: " << errorMessage << std::endl;
      exit(EXIT_FAILURE);   // exits the program, sends "program 
                            // ended abnormally" flag to operating system
   }
}



// Assert
//    - parameters :  errorMessage - a pointer to a character array
//                     containing an error message to print out;
//                     we cannot change this character array through
//                     this pointer
//    - print errorMessage with specific formatting, and then forcefully 
//        exit the program with error status flag.
void Assert(char const * errorMessage)
{
   std::cerr << "***Error: " << errorMessage << std::endl;
   exit(EXIT_FAILURE);   // exits the program, sends "program
                         // ended abnormally" flag to operating system
}





// Warn
//    - parameters : safeCondition - value of a boolean expression
//                 : warningMessage - a pointer to a character array
//                    containing a warning message to print out;
//                    we cannot change this character array through
//                    this pointer
//    - if safeCondition is true, do nothing. Otherwise, print
//              warningMessage with specific formatting
void Warn(bool safeCondition, char const * warningMessage)
{
   if (!safeCondition)
      std::cerr << "***Warning: " << warningMessage << std::endl;
}



// Warn
//    - parameters : warningMessage - a pointer to a character array
//                    containing a warning message to print out;
//                    we cannot change this character array through
//                    this pointer
//    - print warningMessage with specific formatting
void Warn(char const * warningMessage)
{
   std::cerr << "***Warning: " << warningMessage << std::endl;
}



// ***********************************************************
// *                                                         *
// *   asserts.h                                             *    
// *                                                         *
// *   Interface for error alert functions                   *
// *                                                         *
// *   Written September 2003 by Jason Zych                  *
// *                                                         *
// *     - changes by Jason Zych October 2004:               *
// *        - changed ints-as-booleans to bool               *
// *        - standardized const on right of item            *
// *        - enhanced comments                              *
// *        - #ifndef macro changed                          *
// *        - EXIT_FAILURE used as return value              *
// *                                                         * 
// ***********************************************************

#ifndef ASSERTS_225_H
#define ASSERTS_225_H


// There are two versions each of Assert and Warn below. The 
// first in each case is meant for when you aren't sure if the
// assertion or warning is needed, so the function checks a 
// condition for you. The second is meant for when you already 
// know for sure that you want that assertion or warning to activate;
// in those situations, just passing in the message is easier than 
// requiring a 0 to be passed in for the condition.

// The "char const *" type refers to a C++ low-level string; we
// will discuss the "const" keyword further in lecture 4. 


// Assert
//    - parameters : safeCondition - value of a boolean expression
//                 : errorMessage - a pointer to a character array 
//                    containing an error message to print out;
//                    we cannot change this character array through
//                    this pointer
//    - if safeCondition is true, do nothing. Otherwise, print
//              errorMessage with specific formatting, and then 
//              forcefully exit the program with error status flag. 
void Assert(bool safeCondition, char const * errorMessage);



// Assert
//    - parameters : errorMessage - a pointer to a character array 
//                    containing an error message to print out;
//                    we cannot change this character array through
//                    this pointer
//    - print errorMessage with specific formatting, and then forcefully 
//        exit the program with error status flag.
void Assert(char const * errorMessage);



// Warn
//    - parameters : safeCondition - value of a boolean expression
//                 : warningMessage - a pointer to a character array
//                    containing a warning message to print out;
//                    we cannot change this character array through
//                    this pointer
//    - if safeCondition is true, do nothing. Otherwise, print
//              warningMessage with specific formatting
void Warn(bool safeCondition, char const * warningMessage);



// Warn
//    - parameters : warningMessage - a pointer to a character array
//                    containing a warning message to print out;
//                    we cannot change this character array through
//                    this pointer
//    - print warningMessage with specific formatting
void Warn(char const * warningMessage);


#endif

// ********************************************************
// *                                                      *
// *  mp7fns.cpp (MP7)                                    *
// *                                                      *
// *  This file provides some definitions for helper      *
// *    functions for testing MP7                         *   
// *                                                      *
// *  Written April 2005 by Jason Zych                    *
// *                                                      *
// ********************************************************

#include <iostream>

#include "mp7fns.h"


// ************* Actual definitions 


// insertTest
//    - parameters : theTrie - a trie tree to be searched   
//                 : insertKey - a key to be inserted into the trie
//                 : printFlag - a flag indicating whether to print 
//                         the trie after this insertion or not
//    - inserts insertKey into theTrie, and also prints trie after
//          insertion if printFlag is true
void insertTest(Trie & theTrie, String const & insertKey, bool printFlag)
{
   theTrie.insert(insertKey); 
   if (printFlag == true)
   {
      theTrie.print();
      std::cout << std::endl << std::endl;
   }
}



// removeTest
//    - parameters : theTrie - a trie tree to be searched
//                 : removeKey - a key to be removed from the trie
//                 : printFlag - a flag indicating whether to print 
//                         the trie after this removal or not 
//    - removes removeKey from theTrie, and also prints trie after
//          removal if printFlag is true
void removeTest(Trie & theTrie, String const & removeKey, bool printFlag)
{
   theTrie.remove(removeKey);
   if (printFlag == true)
   {
      theTrie.print();
      std::cout << std::endl << std::endl;
   }
}


// ********************************************************
// *                                                      *
// *  mp7fns.h (MP7)                                      *
// *                                                      *
// *  This file provides some declarations for helper     *
// *    functions for testing MP7                         *
// *                                                      *
// *  Written April 2005 by Jason Zych                    *
// *                                                      *
// ********************************************************

#ifndef MP7FNS_H
#define MP7FNS_H

#include "string.h"
#include "trie.h"


// insertTest
//    - parameters : theTrie - a trie tree to be searched
//                 : insertKey - a key to be inserted into the trie
//                 : printFlag - a flag indicating whether to print 
//                         the trie after this insertion or not
//    - inserts insertKey into theTrie, and also prints trie after
//          insertion if printFlag is true 
void insertTest(Trie & theTrie, String const & insertKey, bool printFlag); 


// removeTest
//    - parameters : theTrie - a trie tree to be searched
//                 : removeKey - a key to be removed from the trie
//                 : printFlag - a flag indicating whether to print 
//                         the trie after this removal or not
//    - removes removeKey from theTrie, and also prints trie after
//          removal if printFlag is true 
void removeTest(Trie & theTrie, String const & removeKey, bool printFlag);


#endif



// ********************************************************
// *                                                      *
// *   string.cpp                                         *
// *                                                      *
// *   Implementation for a character string class.       *
// *     NOTE: This interface does not exactly match      *
// *     that of the C++ standard library string          *
// *     class; it's a separate String class entirely.    *
// *                                                      *
// *   Written June 1998 by Jason Zych                    *
// *                                                      *
// *    - changes by Jason Zych January 2003:             *
// *       - remaining const correctness added            *
// *       - assorted comments/other style issues tweaked *
// *       - operator<= and operator>= added              *
// *                                                      *
// *    - changes by Jason Zych August 2004:              *
// *       - default value in const char* constructor     *
// *          eliminated and new, no-argument constructor *
// *          written to handle that case instead.        *
// *       - operator+ renamed to concat                  *
// *                                                      *
// *    - changes by Jason Zych October 2004:             *
// *       - const standardized on right side of          *
// *          modified item                               *
// *       - enhanced some comments                       *
// *       - replaced int with bool as comparison         *
// *            return type                               *
// *                                                      *
// *    - changes by Jason Zych January 2005:             *
// *       - return value of const version of operator[]  *
// *           changed from "by const reference" to       *
// *           "by value"                                 *
// *                                                      *
// ********************************************************

// *** includes of files in the standard library

#include <cstring>    // contains the strlen and strcmp functions
#include <iostream>   // contains output stream tools

// lack of the line
//     using namespace std;
// here means we have to have "std::" in front of all usages 
// of ostream below. If we indicated we were using the
// "std" namespace, then we automatically get to use everything
// in that namespace -- including ostream -- without specifically 
// noting that it is from the std namespace.



// *** includes of our own declarations

#include "string.h"
#include "asserts.h"



// String
//    - constructor
//    - initializes object to the empty string
String::String()
{
   stringLength = 0;
   stringArray = new char[1];
   stringArray[0] = '\0';
}




// String
//    - constructor
//    - parameters : initString - a pointer to a character array;
//                     that character array cannot be changed
//                     through the parameter pointer
//    - initializes object to the string stored in the character
//         array
String::String(char const * initString) 
{ 
    if (initString == NULL)
    {
        stringLength = 0; 
        stringArray = new char[1];  
        stringArray[0]='\0';
    }
    else
    {
        stringLength = strlen(initString); 
        stringArray = new char[stringLength+1];
        for (int i = 0; i <= stringLength; i++)
            stringArray[i] = initString[i];
    }
}



// String
//    - constructor
//    - parameters : origVal - reference to previously-created String
//                    object; that String object cannot be changed
//                    through the parameter reference variable
//    - initializes object to be a copy of origVal
String::String(String const & origVal)
{
    stringLength = origVal.stringLength; 
    stringArray = new char[stringLength+1]; 
    for (int i = 0; i <= stringLength; i++)
        stringArray[i] = origVal.stringArray[i];
}


 
// ~String
//    - destructor
//    - deletes dynamically allocated memory
String::~String()
{ 
   delete[] stringArray; 
}



// operator=
//    - parameters : origVal - reference to previously-created String
//                    object; that String object cannot be changed 
//                    through the parameter reference variable
//    - return value : reference to this String object, after the 
//          assignment operation has been performed; we cannot change
//          this object through the returned reference
//    - assigns this object to be a copy of origVal
String const & String::operator=(String const & origVal)
{
   if (this != &origVal) 
   {
      delete[] stringArray;

      stringLength = origVal.stringLength; 
      stringArray = new char[stringLength+1]; 
      for (int i = 0; i <= stringLength; i++)
         stringArray[i] = origVal.stringArray[i];
   }
   return *this;
}




// operator[]
//    - parameters : index - integer index into the String
//    - return type : copy of the character at the parameter index
//    - This version of the operator[] will be called on const String
//       objects. The parameter index is required to be a legal index
//       into the String, i.e. 0 <= index and index <= stringLength.
//       (If index == stringLength you are indexing the null character.)
//       If the index is NOT legal, an assertion is triggered. Otherwise,
//       the function returns a copy of the character at the given index. 
//       (Since you return a copy of that character, the String cannot
//       have its characters changed via the use of this function.)
char String::operator[](int index) const
{
    Assert(((index >= 0) && (index <= stringLength)),
             "Index to string is out of bounds.");
    return stringArray[index];
}




// operator[]
//    - parameters : index - integer index into the String
//    - return type : reference to the character at the parameter
//         index; that character cannot be changed through the 
//         returned reference
//    - This version of the operator[] will be called on non-const String
//       objects. The parameter index is required to be a legal index 
//       into the String, i.e. 0 <= index and index <= stringLength.  
//       (If index == stringLength you are indexing the null character.)
//       If the index is NOT legal, an assertion is triggered. Otherwise, 
//       the function returns a reference to the character at the given 
//       index.
char & String::operator[](int index) 
{
    Assert(((index >= 0) && (index <= stringLength)), 
             "Index to string is out of bounds.");
    return stringArray[index];
}





// substring
//    - parameters : startIndex - index in string where substring 
//                        begins
//                 : substringLength - length of substring
//    - return value : a String object
//    - returns a String which is a substring of this object, 
//         starting at parameter index and with parameter length. 
//         If the suffix starting at startIndex is less than the
//         requested substring length, then the substring
//         consisting of only that suffix is what is returned.
//         Assertions are triggered if the starting index of  
//         the substring is not a real (non-null) character of
//         the String, and if the substring length is negative.  
String String::substring(int startIndex, int substringLength) const
{
   Assert((startIndex >= 0) && (startIndex < stringLength), 
                 "Start of substring not in string bounds.");  
   Assert((substringLength >= 0), 
                 "Length of substring cannot be negative."); 

   // if substringLength is too big for end of string, reduce
   //   it accordingly. stringLength - 1 is last non-null index
   //   of string, and startIndex + substringLength - 1 is
   //   index of last character of proposed substring.
   if (startIndex + substringLength - 1 > stringLength - 1)
      substringLength = stringLength - startIndex;


   // copy relevant characters into new array 
   char* substringArray = new char[substringLength + 1];   
   for (int i = startIndex; i < startIndex + substringLength; i++)
      substringArray[i - startIndex] = (*this)[i];
   substringArray[substringLength] = '\0';


   // use array to initialize String object
   String finalSubstring(substringArray); 
   delete[] substringArray;
   return finalSubstring;
}



 

// concat
//    - parameters : secondString - reference to another String object;
//                      that String object cannot be changed through
//                      the parameter reference variable
//    - return value : a String object
//    - creates a String object, initialized to the concatenation
//         of this String object and the parameter String object, 
//         and returns a copy of that newly-created String object
String String::concat(String const & secondString) const
{
   int firstLength = stringLength; 
   int concatStringLength = stringLength + secondString.stringLength; 
   char* concatArray = new char[concatStringLength + 1]; 

   for (int i = 0; i < firstLength; i++)
      concatArray[i] = (*this)[i]; 
   for (int i = firstLength; i < concatStringLength; i++)
      concatArray[i] = secondString[i - firstLength];  
   concatArray[concatStringLength] = '\0'; 

   String finalConcat(concatArray); 
   delete[] concatArray;
   return finalConcat;
}
 



// length
//    - return value : integer stringLengthgth of string
//    - returns the number of characters in the String
//         (not counting terminating null character)
//    - this function cannot change this String
int String::length() const
{
   return stringLength;
}




// operator==
//    - parameters : secondString - reference to another String object;
//                    that String object cannot be changed through the
//                    parameter reference variable
//    - return value : a boolean indicating whether or not this
//          String and the object refered to by the parameter reference
//          are equal
//    - returns true if this String object and the String object referred 
//        to by the parameter reference, are a character-by-character 
//        match. Otherwise, returns false.
bool String::operator==(String const & secondString) const
{
   return strcmp(stringArray, secondString.stringArray) == 0;
}




// operator!=
//    - parameters : secondString - reference to another String object;
//                    that String object cannot be changed through the
//                    parameter reference variable
//    - return value : a boolean indicating whether or not this
//          String and the object refered to by the parameter reference
//          are unequal
//    - returns true if this String object and the String object referred 
//        to by the parameter reference, are NOT a character-by-character 
//        match. Otherwise, returns false.
bool String::operator!=(String const & secondString) const
{
   return strcmp(stringArray, secondString.stringArray) != 0;
}



// operator<
//    - parameters : secondString - reference to another String object;
//                    that String object cannot be changed through the
//                    parameter reference variable
//    - return value : a boolean indicating whether or not this
//          String is less than the object refered to by the parameter
//          reference
//    - returns true if there is at least one index where this String object 
//       and the String object referred to by the parameter reference
//       differ, and if at the smallest such index, this String object's 
//       character is less than the character at that index in the 
//       parameter String. Otherwise returns false.
bool String::operator<(String const & secondString) const
{
   return strcmp(stringArray, secondString.stringArray) < 0;
}




// operator>
//    - parameters : secondString - reference to another String object;
//                    that String object cannot be changed through the
//                    parameter reference variable
//    - return value : a boolean indicating whether or not this
//          String is greater than the object refered to by the parameter
//          reference
//    - returns true if there is at least one index where this String object 
//       and the String object referred to by the parameter reference
//       differ, and if at the smallest such index, this String object's 
//       character is greater than the character at that index in the 
//       parameter String. Otherwise returns false.
bool String::operator>(String const & secondString) const
{
   return strcmp(stringArray, secondString.stringArray) > 0;
}




// operator<=
//    - parameters : secondString - reference to another String object;
//                    that String object cannot be changed through the
//                    parameter reference variable
//    - return value : a boolean indicating whether or not this
//          String is less than or equal to the object refered to by 
//          the parameter reference
//    - returns true if either this String and the String referred to
//       by the parameter reference are a perfect character-by-
//       character match, or else if at the lowest index where the two
//       String objects differ, this String object's character is less 
//       than the character at that index in the parameter String.
//       Otherwise returns false.
bool String::operator<=(String const & secondString) const
{
   return strcmp(stringArray, secondString.stringArray) <= 0;
}



// operator>=
//    - parameters : secondString - reference to another String object;
//                    that String object cannot be changed through the
//                    parameter reference variable
//    - return value : a boolean indicating whether or not this
//          String is greater than or equal to the object refered to by 
//          the parameter reference
//    - returns true if either this String and the String referred to
//       by the parameter reference are a perfect character-by-
//       character match, or else if at the lowest index where the two
//       String objects differ, this String object's character is greater
//       than the character at that index in the parameter String.
//       Otherwise returns false.
bool String::operator>=(String const & secondString) const
{
   return strcmp(stringArray, secondString.stringArray) >= 0;
}




// operator<<
//    - friend function of the String class, not member function
//    - parameters : Out - a reference to an ostream object
//                 : outputString - a reference to a String object we 
//                     wish to write to the output stream; that String
//                     object cannot be changed through the parameter 
//                     reference variable
//    - return value : the parameter ostream reference, after it has
//          been altered through this operation
//    - writes the data of the parameter String to the parameter  
//        output stream, and then returns that output stream 
std::ostream & operator<<(std::ostream & Out, 
                                 String const & outputString)
{
    Out << outputString.stringArray;
    return Out;
}
 
 
// ********************************************************
// *                                                      *
// *   string.h                                           *    
// *                                                      *
// *   Interface for a character string class.            *
// *     NOTE: This interface does not exactly match      *
// *     that of the C++ standard library string          *
// *     class; it's a separate String class entirely.    *
// *                                                      *
// *   Written June 1998 by Jason Zych                    *
// *                                                      *
// *    - changes by Jason Zych January 2003:             *
// *       - remaining const correctness added            *
// *       - assorted comments/other style issues tweaked *
// *       - operator<= and operator>= added              *
// *                                                      *
// *    - changes by Jason Zych August 2004:              *
// *       - default value in const char* constructor     *
// *          eliminated and new, no-argument constructor *
// *          written to handle that case instead.        *
// *       - operator+ renamed to concat                  *
// *                                                      *
// *    - changes by Jason Zych October 2004:             *
// *       - const standardized on right side of          *
// *          modified item                               *
// *       - enhanced some comments                       *
// *       - replaced int with bool as comparison         *
// *            return type                               *
// *                                                      *   
// *    - changes by Jason Zych January 2005:             *
// *       - return value of const version of operator[]  *
// *           changed from "by const reference" to       *
// *           "by value"                                 *
// *                                                      *
// ********************************************************

// every header file declaring a class, needs a #ifndef setup like 
//   this to avoid issues with multiple inclusion

#ifndef STRING_225_H
#define STRING_225_H



// *** includes of files in the standard library

#include <iostream>    // contains output stream tools 

// lack of the line
//     using namespace std;
// here means we have to have "std::" in front of all usages 
// of ostream below. If we indicated we were using the
// "std" namespace, then we automatically get to use everything
// in that namespace -- including ostream -- without specifically 
// noting that it is from the std namespace.




class String
{
public:

   // String
   //    - constructor
   //    - initializes object to the empty string
   String();



   // String
   //    - constructor 
   //    - parameters : initString - a pointer to a character array;
   //                     that character array cannot be changed 
   //                     through the parameter pointer 
   //    - initializes object to the string stored in the character 
   //         array 
   String(char const * initString);



   // String
   //    - constructor
   //    - parameters : origVal - reference to previously-created String
   //                    object; that String object cannot be changed
   //                    through the parameter reference variable
   //    - initializes object to be a copy of origVal
   String(String const & origVal);



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



   // operator=
   //    - parameters : origVal - reference to previously-created String
   //                    object; that String object cannot be changed 
   //                    through the parameter reference variable
   //    - return value : reference to this String object, after the 
   //          assignment operation has been performed; we cannot change
   //          this object through the returned reference
   //    - assigns this object to be a copy of origVal  
   String const & operator=(String const & origVal);



   // operator[]
   //    - parameters : index - integer index into the String
   //    - return type : copy of the character at the parameter index
   //    - This version of the operator[] will be called on const String
   //       objects. The parameter index is required to be a legal index 
   //       into the String, i.e. 0 <= index and index <= stringLength.  
   //       (If index == stringLength you are indexing the null character.)
   //       If the index is NOT legal, an assertion is triggered. Otherwise, 
   //       the function returns a copy of the character at the given index. 
   //       (Since you return a copy of that character, the String cannot
   //       have its characters changed via the use of this function.)
   char operator[](int index) const;



   // operator[]
   //    - parameters : index - integer index into the String
   //    - return type : reference to the character at the parameter
   //         index; that character cannot be changed through the 
   //         returned reference
   //    - This version of the operator[] will be called on non-const String
   //       objects. The parameter index is required to be a legal index 
   //       into the String, i.e. 0 <= index and index <= stringLength.  
   //       (If index == stringLength you are indexing the null character.)
   //       If the index is NOT legal, an assertion is triggered. Otherwise, 
   //       the function returns a reference to the character at the given 
   //       index.
   char & operator[](int index);



   // substring
   //    - parameters : startIndex - index in string where substring 
   //                        begins
   //                 : substringLength - length of substring
   //    - return value : a String object
   //    - returns a String which is a substring of this object, 
   //         starting at parameter index and with parameter length.
   //         If the suffix starting at startIndex is less than the
   //         requested substring length, then the substring
   //         consisting of only that suffix is what is returned.
   //         Assertions are triggered if the starting index of
   //         the substring is not a real (non-null) character of
   //         the String, and if the substring length is negative.  
   String substring(int startIndex, int substringLength) const;



   // concat
   //    - parameters : secondString - reference to another String object;
   //                      that String object cannot be changed through
   //                      the parameter reference variable
   //    - return value : a String object
   //    - creates a String object, initialized to the concatenation
   //         of this String object and the parameter String object, 
   //         and returns a copy of that newly-created String object
   String concat(String const & secondString) const;



   // length
   //    - return value : integer length of string
   //    - returns the number of characters in the String
   //        (not counting terminating null character); this
   //        function cannot change this String
   int length() const;


   
   // operator==
   //    - parameters : secondString - reference to another String object;
   //                    that String object cannot be changed through the
   //                    parameter reference variable
   //    - return value : a boolean indicating whether or not this
   //          String and the object refered to by the parameter reference
   //          are equal
   //    - returns true if this String object and the String object referred 
   //        to by the parameter reference, are a character-by-character 
   //        match. Otherwise, returns false.
   bool operator==(String const & secondString) const;

 

   // operator!=
   //    - parameters : secondString - reference to another String object;
   //                    that String object cannot be changed through the
   //                    parameter reference variable
   //    - return value : a boolean indicating whether or not this
   //          String and the object refered to by the parameter reference
   //          are unequal
   //    - returns true if this String object and the String object referred 
   //        to by the parameter reference, are NOT a character-by-character 
   //        match. Otherwise, returns false.
   bool operator!=(String const & secondString) const;



   // operator<
   //    - parameters : secondString - reference to another String object;
   //                    that String object cannot be changed through the
   //                    parameter reference variable
   //    - return value : a boolean indicating whether or not this
   //          String is less than the object refered to by the parameter 
   //          reference
   //    - returns true if there is at least one index where this String object 
   //       and the String object referred to by the parameter reference
   //       differ, and if at the smallest such index, this String object's 
   //       character is less than the character at that index in the 
   //       parameter String. Otherwise returns false.
   bool operator<(String const & secondString) const;



   // operator>
   //    - parameters : secondString - reference to another String object;
   //                    that String object cannot be changed through the
   //                    parameter reference variable
   //    - return value : a boolean indicating whether or not this
   //          String is greater than the object refered to by the parameter
   //          reference
   //    - returns true if there is at least one index where this String object 
   //       and the String object referred to by the parameter reference
   //       differ, and if at the smallest such index, this String object's 
   //       character is greater than the character at that index in the 
   //       parameter String. Otherwise returns false.
   bool operator>(String const & secondString) const;



   // operator<=
   //    - parameters : secondString - reference to another String object;
   //                    that String object cannot be changed through the
   //                    parameter reference variable
   //    - return value : a boolean indicating whether or not this
   //          String is less than or equal to the object refered to by 
   //          the parameter reference
   //    - returns true if either this String and the String referred to
   //       by the parameter reference are a perfect character-by-
   //       character match, or else if at the lowest index where the two
   //       String objects differ, this String object's character is less 
   //       than the character at that index in the parameter String.
   //       Otherwise returns false.
   bool operator<=(String const & secondString) const;




   // operator>=
   //    - parameters : secondString - reference to another String object;
   //                    that String object cannot be changed through the
   //                    parameter reference variable
   //    - return value : a boolean indicating whether or not this
   //          String is greater than or equal to the object refered to by 
   //          the parameter reference
   //    - returns true if either this String and the String referred to
   //       by the parameter reference are a perfect character-by-
   //       character match, or else if at the lowest index where the two
   //       String objects differ, this String object's character is greater
   //       than the character at that index in the parameter String.
   //       Otherwise returns false.
   bool operator>=(String const & secondString) const;


   // operator<< 
   //    - friend function of the String class, not member function
   //    - parameters : Out - a reference to an ostream object
   //                 : outputString - a reference to a String object we 
   //                     wish to write to the output stream; that String
   //                     object cannot be changed through the parameter 
   //                     reference variable
   //    - return value : the parameter ostream reference, after it has
   //          been altered through this operation
   //    - writes the data of the parameter String to the parameter  
   //        output stream, and then returns that output stream 
   friend std::ostream & operator<<(std::ostream & Out, 
                                 String const & outputString);


private:

   int stringLength;    // length of string
   char * stringArray;   // pointer to array holding string characters 
};

#endif

// *****************************************************************
// *                                                               *
// *  trie.cpp                                                     *
// *                                                               *
// *  mp7 implementation file                                      *
// *                                                               *
// *  This file the implementation file of the Trie class used to  *
// *  implement a de la Briandais tree to have String values       *
// *  as keys.  But instead of an array, this is a 27-ary tree     *
// *  that has most 27 children.                                   *
// *                                                               *
// *  Written April 2005 by Jeremy Curran                          *
// *                                                               *
// *                                                               *   
// ***************************************************************** 

#include<iostream>
#include "trie.h"
#include "list225.h"
#include "asserts.h"
#include "utility225.h"


//Trie(void)
//Default constructor of the Trie class
//  -Creates an empty trie.
Trie::Trie(void)
{
   root = NULL;
}

//Trie(Trie const & origVal)
//Trie class copy constructor
//parameter -origVal, a constant reference to a Trie class object
//that the copy constructor uses to copy to other Trie class objects.
Trie::Trie(Trie const & origVal)
{
   root = Copy(origVal.root);   
}
   
//Trie const & operator=(Trie const & origVal)
//Trie class assignment operator
//parameter: -origVal, a constant reference to
//a Trie class object, that the operator= uses
//to assign two objects to be copies of each other
//if the object we are assigning to is not equal, calls
//the destructor if two objects are not equal to avoid
//garbage memory before copying.
Trie const & Trie::operator=(Trie const & origVal)
{
   if(this != & origVal)
   {
      Clear(root);

      root = Copy(origVal.root);
   }
   return *this;
}

   
//~Trie()
//Trie class destructor
//Used to delete any Trie objects that are created by
//allocating dynamic memory, to send unused memory
//back to the operating system when the user specifies
//to do so.  
Trie::~Trie(void)
{
   Clear(root);
}

//public insert function
//parameter -s, a String that the user specifies to be inserted
//into the trie when calling insertion.
//Calls the private insert function that recursively inserts the parameter 
//string passed in into the trie if the parameter string is not already in 
//the tree, else it ignores it.
void Trie::insert(String s)
{
   int Level =0;
   TrieNode* parentofRoot = NULL;
   //call the recursive insert function
   insert(root, s, Level);
}

//private recursive insert method
//parameters: -ptr: A pointer to a TrieNode, a node in the Trie, allows
//the insert function to traverse through the trie recursively until
//the proper position in the trie for insertion has been reached.
//  -s: A String containing the word that the user wants to add to the
//trie.
//  -prevLevel: the level of the string that is needed to traverse
//through the string and to be stored in the trie allows us to traverse 
//down the trie searching the characters stored in the list of the
//parameter pointer recursively until all nodes have been checked in
//that pointers subtrie list.
//Inserts TrieNode's and their list of subtries storing storing pairs that 
//store a TrieNode and a character from an appropriate position in the 
//parameter string into the trie, into order to form a pure de la Briandais
//tree.
void Trie::insert(TrieNode* & ptr, String s, int prevLevel)
{
   //check whether this node of the trie is
   //empty
   if(ptr == NULL)
   {
      //if the current position in the string is not the null charcter than 
      //insert a new TrieNode, and a new pair into its subtrie list containing
      //a TrieNode of a subtrie of this node and a character stored and call 
      //insert recursively, else, insert a TrieNode and a pair into the
      //nodes list, but do not call recursively on insert since the end of the 
      //string has been reached and the NULL character inserted is the
      //end of that subtrie.
      if(prevLevel < s.length())//internal node case
      {
	 //create the root node
	 ptr = new TrieNode(prevLevel, list<pair<char, Trie::TrieNode*> >());

	 pair<char, TrieNode*> newpair;
	 newpair.first = s[prevLevel];
	 newpair.second = NULL;
 
	 //call insert recursively on the TrieNode
         //stored by in the new pair to add the
         //next valid character in the string
	 insert(newpair.second, s, prevLevel+1);
         //insert first element in the list
	 ptr->subtrieList.push_front(newpair);      
      }
      else if(prevLevel == s.length())//leaf node case
      {
	 ptr = new TrieNode(prevLevel, list<pair<char, TrieNode*> >());

         pair<char, TrieNode*> leafpair;
         leafpair.first = '\0';
         leafpair.second = NULL;

         ptr->subtrieList.push_front(leafpair);
      } 
      
   }
   else //the TrieNode at the level being considered to insert to is not NULL
   {
      //search the list until reaching a node in the list containing a pair
      //that stores the first character that is greater than or equal to the 
      //first character in the parameter string or until reaching the end of
      //the list  
      list<pair<char, TrieNode*> >::iterator entire = 
                                             ptr->subtrieList.begin();
      while((entire != ptr->subtrieList.end()) && 
                                       (entire->first < s[prevLevel]))
      {
         entire++;
      }
      
      //if entire is not at the position of the end of the list and its
      //character stored in its pair is equal to the parameter string, then
      //the character already exists in this nodes list of trie nodes, and it
      //must make the decision to insert recursively or do nothing based on the
      //current positon of the string.  Else make a new pair, storing a NULL
      //TrieNode and the character stored at the current position of the, 
      //string and insert it to the list and decide whether to insert again
      //recursively on this node based on the current position of the string.
      if((entire != ptr->subtrieList.end()) && (entire->first == s[prevLevel]))
      {
	 //the character exists in the list, check whether the current
         //position in the list is not storing the null character and call
         //insert recursively if it is not storing the null character, else
         //do nothing if the TrieNode stored in this iterator's pair is 
         //a leaf
         if(entire->first != '\0')
	 {
	    //Make recursive call, if the TrieNode stored
            //in this iterator is not a leaf. 
	    insert(entire->second, s, prevLevel+1);
	 }
      }
      else  
      {
	 //Character you need does not exist
	 //Make a new pair
	 //Insert pair into list
	 //Make recursive call if prevLevel < s.length()
	 if(prevLevel < s.length()) //internal node case
	 {
	    //if the first character of the string is not in the list
            //and the current position of the string is not the
            //null character, then the new list node's TrieNode stored in 
            //its pair should be an internal node, not a leaf.	    
	    
            //creating new pair   
	    pair<char, TrieNode*> newpair;
            //storing character in the
            //current position of the
            //string
	    newpair.first = s[prevLevel];
            //new pair's always have a
            //NULL TrieNode stored
	    newpair.second = NULL;
	  
	    //call recursively on newpair.second to
	    //add child subtries of this new list node's 
            //TrieNode since this node is an internal
            //TrieNode
	    insert(newpair.second, s, prevLevel+1);

	    //add new pair before an existing
	    //pair in the list 
	    ptr->subtrieList.insert(entire,newpair);
	     
	 }
	 else if(prevLevel == s.length()) //leaf node case
	 { 
	    //store null character at beginning of list
	    //and store a TrieNode pointing to NULL

            //creating new pair
	    pair<char, TrieNode*> firstpair;
	    firstpair.first = '\0';
	    firstpair.second = NULL;
               
	    //store null character at the front of
	    //the list
	    ptr->subtrieList.insert(entire,firstpair);

	    //no need to call recursively since this is
	    //the pair only containing the null character
	    //marking the end of the string and the end of
	    //the list
	 }  
      }    
   }  
} 

//remove
//parameter -r, a String that the user specifies to be removed
//from the trie.
//Calls the private recursive remove function that removes the parameter 
//string r from the trie recursively if the parameter string exists in the 
//trie, else it does nothing.
void Trie::remove(String r)
{
   int Level = 0;
   remove(root, r, Level);
}

//private recursive remove function
//parameters -ptr: a reference pointer of type TrieNode, points to a TrieNode 
//in the tree, passed by reference to allow us to modify the trie removing the 
//nodes recursively
// -s: A String containing the word that the user wants to remove from the trie
// -prevLevel: an int variable containing the current level of the string used 
//to access the next character in the string during recursive calls that the 
//user wants to remove from the trie.
//   Traverses through TrieNode's list of child TrieNodes using iterators until 
//the iterators the iterator that contains the pair storing the first character 
//of the string to be removed is found.
//Then it recursively searches for a leaf following the path of stored 
//characters that match the string to be removed. The subtrie lists of the leaf 
//are erased and then the leaf is deleted if after this erase the TrieNode 
//pointing to this list has an empty list.  Each subsequent leaf created after
//each recursive call is removed in the same manner until either the root of 
//the entire trie is deleted or until reaching a node of the subtrie List 
//pointed to by a TrieNode that does not have an empty subtrie list.  
void Trie::remove(TrieNode* & ptr, String s, int prevLevel)
{
   if(ptr != NULL)
   {
      list<pair<char, Trie::TrieNode*> >::iterator it = 
                                      ptr->subtrieList.begin();

      //traverse the list of subtries of this TrieNode
      while(it != ptr->subtrieList.end())
      {
         //if the character at the level in the string matches the character 
         //stored in this node's subtrie currently pointed to internally by 
         //the iterator then procees to check whether the node stored in the 
         //subtrie List at this iterator position in the list is a leaf 
         //TrieNode or an internal TrieNode, else do nothing and increment 
         //to the next iterator position in the list
	 if(s[prevLevel] == it->first)
	 {
	    //if the node stored in this iterator's pair is an internal 
            //TrieNode, it calls remove recursively on this node's 
            //subtrie's until a leaf is found marked by the null character,
            //else the internal TrieNode stored in this iterator must be a 
            //leaf and nothing needs to be done and the function can proceed 
            //to the next instruction
	    if(it->first != '\0')
	    {
	       //calls remove recursively
	       remove(it->second, s, prevLevel+1);
	    }
            
            //if the TrieNode stored inside the iterator is NULL, then
            //this NULL is the leaf and its subtrie List must be erased 
            //else this node is not a leaf because it has other subtries 
            //attached that depend on this node to form a word in the try 
            //and to keep a connection with the root and it so it should 
            //not be deleted   
	    if(it->second == NULL)
	    {
	       ptr->subtrieList.erase(it);
	    }
            //when finished deleting the
            //proper nodes, break out of the
            //while loop. 
            break;
	 }
         it++;  
      }    
      //if the list pointed to by the current node that was stopped at 
      //after breaking out of the while loop is empty, then proceed to 
      //delete this TrieNode else do not delete it since it has other 
      //subtrie's that depend on this node to form a proper character 
      //and to keep a connection to the root.
      if(ptr->subtrieList.empty())
      {
	 delete ptr;
	 ptr = NULL;
      }   
   }
   return;  
}
   
//print
//Prints out the trie and has no parameters because it has
//access to the private member variables directly.  Calls
//the recursive print function on the root of the trie.
void Trie::print(void)
{
   print(root);
}

//private print function
//parameter: -ptr: A pointer to a TrieNode of the trie, used to
//recursively traverse the nodes in the trie.
//prints out the characters of the trie using recursive preorder 
//depth first search.
void Trie::print(TrieNode* ptr)
{  
   if(ptr != NULL)
   {
      std::cout<< "Entering level " << ptr->nodeLevel << " node...\n";
      list<pair<char, Trie::TrieNode*> >::iterator it = 
                                         ptr->subtrieList.begin();
      while(it != ptr->subtrieList.end())
      {
         //if the pair stored in this iterator does not contain the
         //null character, print out the character and its node level
         //and do recursive calls on this iterators TrieNode stored in
         //the pair, else print a message telling user that the null
         //character exists at this level and do not do any recursive
         //call on print since the TrieNode stored in this iterator
         //is NULL and the end of the list has been reached.
	 if(it->first != '\0')
	 {
            
	    std::cout<< "The " << it->first << " subtree pointed to by "
		     << "level " << ptr->nodeLevel << " is as follows:\n";
	    TrieNode* temp = it->second;
	    print(temp);
	    std::cout<< "The " << it->first << " subtree pointed to by " 
                     << "level " << ptr->nodeLevel << " has been explored." 
                     << std::endl;
	 }
	 else
	 {
	    std::cout<< "The null character exists in this level " << 
                     ptr->nodeLevel << " node." << std::endl;
	 } 
	
         it++;
      }
      std::cout<< "Leaving level " << ptr->nodeLevel << " node." << std::endl; 
      
   }   
}

//private Copy function
//parameter: -ptr: A pointer to a TrieNode in the trie which allows
//copying of the nodes in the trie to be done recursively.
//Copies all TrieNode's and their subtrie lists in the de la Briandais 
//tree recursively using recursive preorder depth-first search.
typename Trie::TrieNode* Trie::Copy(typename Trie::TrieNode* ptr)
{
   if(ptr != NULL)
   {
      //calling 2 argument TrieNode constructor passing in the
      //pointer's node level and its subtrie list will automatically
      //copy the subtrie lists and the node's level into the new node
      TrieNode* newnode = new TrieNode(ptr->nodeLevel,ptr->subtrieList);

      //second iterator used only for copying the TrieNode's stored in
      //the list to the new node recursively, using only "it" will alter
      //the contents of the list when trying to copy which is bad
      list<pair<char, TrieNode*> >::iterator copyIT = 
                                            newnode->subtrieList.begin();      
   
      list<pair<char, Trie::TrieNode*> >::iterator it = 
                                            ptr->subtrieList.begin();
      //traverse through this nodes list of subtries and copy all
      //nodes in the subtrie list and children of those tries that
      //are not pointing to NULL.
      while(it != ptr->subtrieList.end())
      {
         //Copy TrieNode's at current it position into the
         //pair stored in the new list stored in copyIT
         //at the same position in the list as it
	 copyIT->second = Copy(it->second);
         ++it;
         copyIT++;
      }
     
      return newnode;
   }
   else
   {
      return NULL;
   }
}  

//private Clear function
//deletes all of the nodes and their list of
//subtries in the trie recursively in post order
void Trie::Clear(TrieNode* & ptr)
{
   if(ptr != NULL)
   {
      list<pair<char, Trie::TrieNode*> >::iterator it = 
	 ptr->subtrieList.begin();
      while(it != ptr->subtrieList.end())
      {
	 Clear(it->second);
	 it++;
      }
   
      delete ptr;
      ptr = NULL;
   }
   
}
// *****************************************************************
// *                                                               *
// *  trie.h                                                       *
// *                                                               *
// *  mp7 header file                                              *
// *                                                               *
// *  This file is the header file of the Trie class used to       *
// *  implement a de la Briandais tree to have String values       *
// *  as keys.  But instead of an array, this is a 27-ary tree     *
// *  that has most 27 children.                                   *
// *                                                               *
// *  Written April 2005 by Jeremy Curran                          *
// *                                                               *
// *                                                               *   
// ***************************************************************** 

#ifndef trie_h
#define trie_h

#include "list225.h"
#include "utility225.h"
#include "string.h"

class Trie
{
public:

   //Trie(void)
   //Default constructor of the Trie class
   //  -Creates an empty trie(an empty
   //de la Briandais tree).
   Trie(void);

   //Trie(Trie const & origVal)
   //Trie class copy constructor
   //parameter -origVal, a constant reference to a Trie class object
   //that the copy constructor uses to copy to other Trie class objects.
   Trie(Trie const & origVal);
   
   //Trie const & operator=(Trie const & origVal)
   //Trie class assignment operator
   //parameter: -origVal, a constant reference to
   //a Trie class object, that the operator= uses
   //to assign two objects to be copies of each other
   //if the object we are assigning to is not equal, calls
   //the destructor if two objects are not equal to avoid
   //garbage memory before copying.
   Trie const & operator=(Trie const & origVal);

   
   //~Trie()
   //Trie class destructor
   //Used to delete any Trie objects that are created by
   //allocating dynamic memory, to send unused memory
   //back to the operating system when the user specifies
   //to do so.  
   ~Trie(void);

   //insert
   //parameter -s, a String that the user specifies to be inserted
   //into the trie when calling insertion.
   //Calls the private insert function that recursively inserts the 
   //parameter string passed in into the trie if the parameter string 
   //is not already in the tree, else it ignores it.
   void insert(String s);

   //remove
   //parameter -r, a String that the user specifies to be removed
   //from the trie.
   //removes the parameter string r from the trie if the parameter 
   //string exists in the trie, else it does nothing.
   void remove(String r);

   //print
   //Prints out the trie and has no parameters because it has
   //access to the private member variables directly.
   void print(void);

private:

   class TrieNode
   {
   public: //public within scope of Trie implementation
           //private to members outside of the Trie
      
      //TrieNode default constructor
      //initialzes the new nodes children to NULL and its
      //subtrieList to NULL in the member initializer
      //list
      TrieNode(void): nodeLevel(0), subtrieList(NULL){}

      //TrieNode 2 argument constructor
      //Allows us the ability to assign a new TrieNodes level,
      //and its subtrieLists on the same line while allocating
      //a NULL TrieNode with dynamic memory
      TrieNode(int level, list<pair<char, TrieNode*> > List): 
                      nodeLevel(level),subtrieList(List){}
    
      //TrieNode class member variables
      int nodeLevel;  //level of the node
      list<pair<char, TrieNode*> > subtrieList; //subtrie Linked list 

   };//end of TrieNode class   

   //root of the le Briandais tree
   Trie::TrieNode* root;

   //private insert function
   //parameters: -ptr: A pointer to a TrieNode, a node in the Trie, allows
   //the insert function to traverse through the trie recursively until
   //the proper position in the trie for insertion has been reached.
   //  -s: A String containing the word that the user wants to add to the
   //trie.
   //  -prevLevel: the level of the string that is needed to traverse
   //through the string and to be stored in the trie allows us to traverse 
   //down the trie searching the characters stored in the list of the
   //parameter pointer recursively until all nodes have been checked in
   //that pointers subtrie list.
   //Inserts TrieNode's and their list of subtries storing storing pairs that 
   //store a TrieNode and a character from an appropriate position in the 
   //parameter string into the trie, into order to form a pure de la Briandais
   //tree.
   void insert(TrieNode* & ptr, String s, int prevLevel);

   //private recursive remove function
   //parameters -ptr: a reference pointer of type TrieNode, points to a 
   //TrieNode in the tree, passed by reference to allow us to modify the trie
   // removing the nodes recursively
   // -s: A String containing the word that the user wants to remove from the 
   //trie
   // -prevLevel: an int variable containing the current level of the string 
   //used to access the next character in the string during recursive calls 
   //that the user wants to remove from the trie.
   //   Traverses through TrieNode's list of child TrieNodes using iterators 
   //until the iterators the iterator that contains the pair storing the first 
   //character of the string to be removed is found. Then it recursively 
   //searches for a leaf following the path of stored characters that match 
   //the string to be removed. The subtrie lists of the leaf are erased and 
   //then the leaf is deleted if after this erase the TrieNode pointing to 
   //this list has an empty list.  Each subsequent leaf created after each 
   //recursive call is removed in the same manner until either the root of 
   //the entire trie is deleted or until reaching a node of the subtrie List 
   //pointed to by a TrieNode that does not have an empty subtrie list.  
   void remove(TrieNode* & ptr, String s, int prevLevel);

   //private Copy function
   //parameter: -ptr: A pointer to a TrieNode in the trie which allows
   //copying of the nodes in the trie to be done recursively.
   //Copies all TrieNode's and their subtrie lists in the de la Briandais 
   //tree recursively using recursive preorder depth-first search.
   Trie::TrieNode* Copy(Trie::TrieNode* ptr);

   //private Clear function
   //deletes all of the nodes and their list of
   //subtries in the trie recursively in post order
   void Clear(TrieNode* & ptr);

   //private print function
   //parameter: -ptr: A pointer to a TrieNode of the trie, used to
   //recursively traverse the nodes in the trie.
   //prints out the characters of the trie using recursive preorder 
   //depth first search.
   void print(TrieNode* ptr);

};




#endif


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=22227



More information about the Gcc-bugs mailing list