#ifdef __BORLANDC__
// suppress the warning message that functions containing for are not
// expanded inline
#pragma warn -8027
#endif   // __BORLANDC__

class iterator;
class const_iterator;
   // declare the iterator classes so the names are available

friend class iterator;
friend class const_iterator;
   // allow the iterator classes to access the private section
   // of stree

class iterator
{
   friend class stree<T>;
   friend class const_iterator;

   public:

      // constructor
      iterator ()
      {}

      // comparison operators. just compare node pointers
      bool operator== (const iterator& rhs) const
      {
         return nodePtr == rhs.nodePtr;
      }

      bool operator!= (const iterator& rhs) const
      {
         return nodePtr != rhs.nodePtr;
      }

      // dereference operator. return a reference to
      // the value pointed to by nodePtr
      T& operator* () const
      {
         if (nodePtr == NULL)
            throw
               referenceError("stree iterator operator* (): NULL reference");

         return nodePtr->nodeValue;
      }

      // preincrement. move forward to next larger value
      iterator& operator++ ()
      {
         stnode<T> *p;

         if (nodePtr == NULL)
         {
            // ++ from end(). get the root of the tree
            nodePtr = tree->root;

            // error! ++ requested for an empty tree
            if (nodePtr == NULL)
               throw
                  underflowError("stree iterator operator++ (): tree empty");

            // move to the smallest value in the tree,
            // which is the first node inorder
            while (nodePtr->left != NULL)
               nodePtr = nodePtr->left;
         }
         else
         if (nodePtr->right != NULL)
         {
            // successor is the furthest left node of
            // right subtree
            nodePtr = nodePtr->right;

            while (nodePtr->left != NULL)
               nodePtr = nodePtr->left;
         }
         else
         {
            // have already processed the left subtree, and
            // there is no right subtree. move up the tree,
            // looking for a parent for which nodePtr is a left child,
            // stopping if the parent becomes NULL. a non-NULL parent
            // is the successor. if parent is NULL, the original node
            // was the last node inorder, and its successor
            // is the end of the list
            p = nodePtr->parent;

            while (p != NULL && nodePtr == p->right)
            {
               nodePtr = p;
               p = p->parent;
            }

            // if we were previously at the right-most node in
            // the tree, nodePtr = NULL, and the iterator specifies
            // the end of the list
            nodePtr = p;
         }

         return *this;
      }

      // postincrement
      iterator operator++ (int)
      {
         // save current iterator
         iterator tmp = *this;

         // move myself forward to the next tree node
         ++*this;

         // return the previous value
         return tmp;
      }

      // predecrement. move backward to largest value < current value
      iterator& operator-- ()
      {
         stnode<T> *p;

         if (nodePtr == NULL)
         {
            // -- from end(). get the root of the tree
            nodePtr = tree->root;

            // error! -- requested for an empty tree
            if (nodePtr == NULL)
               throw
                  underflowError("stree iterator operator--: tree empty");

            // move to the largest value in the tree,
            // which is the last node inorder
            while (nodePtr->right != NULL)
               nodePtr = nodePtr->right;
         } else if (nodePtr->left != NULL)
         {
            // must have gotten here by processing all the nodes
            // on the left branch. predecessor is the farthest
            // right node of the left subtree
            nodePtr = nodePtr->left;

            while (nodePtr->right != NULL)
               nodePtr = nodePtr->right;
         }
         else
         {
            // must have gotten here by going right and then
            // far left. move up the tree, looking for a parent
            // for which nodePtr is a right child, stopping if the
            // parent becomes NULL. a non-NULL parent is the
            // predecessor. if parent is NULL, the original node
            // was the first node inorder, and its predecessor
            // is the end of the list
            p = nodePtr->parent;
            while (p != NULL && nodePtr == p->left)
            {
               nodePtr = p;
               p = p->parent;
            }

            // if we were previously at the left-most node in
            // the tree, nodePtr = NULL, and the iterator specifies
            // the end of the list
            nodePtr = p;
         }

         return *this;
      }

      // postdecrement
      iterator operator-- (int)
      {
         // save current iterator
         iterator tmp = *this;

         // move myself backward to the previous tree node
         --*this;

         // return the previous value
         return tmp;
      }

   private:

      // nodePtr is the current location in the tree. we can move
      // freely about the tree using left, right, and parent.
      // tree is the address of the stree object associated
      // with this iterator. it is used only to access the
      // root pointer, which is needed for ++ and --
      // when the iterator value is end()
      stnode<T> *nodePtr;
      stree<T> *tree;

      // used to construct an iterator return value from
      // an stnode pointer
      iterator (stnode<T> *p, stree<T> *t) : nodePtr(p), tree(t)
      {}

};

class const_iterator
{
   friend class stree<T>;

   public:

      // constructor
      const_iterator ()
      {}

      // used to convert a const iterator to a const_iterator
      const_iterator (const iterator& pos): nodePtr(pos.nodePtr)
      {}

      // comparison operators. just compare node pointers
      bool operator== (const const_iterator& rhs) const
      {
         return nodePtr == rhs.nodePtr;
      }

      bool operator!= (const const_iterator& rhs) const
      {
         return nodePtr != rhs.nodePtr;
      }

      // dereference operator. return a reference to
      // the value pointed to by nodePtr
      const T& operator* () const
      {
         if (nodePtr == NULL)
            throw
               referenceError("stree const_iterator operator* (): NULL reference");

         return nodePtr->nodeValue;
      }

      // preincrement. move forward to next larger value
      const_iterator& operator++ ()
      {
         stnode<T> *p;

         if (nodePtr == NULL)
         {
            // ++ from end(). get the root of the tree
            nodePtr = tree->root;

            // error! ++ requested for an empty tree
            if (nodePtr == NULL)
               throw underflowError("stree const_iterator operator++ (): tree empty");

            // move to the smallest value in the tree,
            // which is the first node inorder
            while (nodePtr->left != NULL)
               nodePtr = nodePtr->left;
         }
         else
         if (nodePtr->right != NULL)
         {
            // successor is the furthest left node of
            // right subtree
            nodePtr = nodePtr->right;

            while (nodePtr->left != NULL)
               nodePtr = nodePtr->left;
         }
         else
         {
            // have already processed the left subtree, and
            // there is no right subtree. move up the tree,
            // looking for a parent for which nodePtr is a left child,
            // stopping if the parent becomes NULL. a non-NULL parent
            // is the successor. if parent is NULL, the original node
            // was the last node inorder, and its successor
            // is the end of the list
            p = nodePtr->parent;

            while (p != NULL && nodePtr == p->right)
            {
               nodePtr = p;
               p = p->parent;
            }

            // if we were previously at the right-most node in
            // the tree, nodePtr = NULL, and the iterator specifies
            // the end of the list
            nodePtr = p;
         }

         return *this;
      }

      // postincrement
      const_iterator operator++ (int)
      {
         // save current const_iterator
         const_iterator tmp = *this;

         // move myself forward to the next tree node
         ++*this;

         // return the previous value
         return tmp;
      }

      // predecrement. move backward to largest value < current value
      const_iterator& operator-- ()
      {
         stnode<T> *p;

         if (nodePtr == NULL)
         {
            // -- from end(). get the root of the tree
            nodePtr = tree->root;

            // error! -- requested for an empty tree
            if (nodePtr == NULL)
               throw
                  underflowError("stree iterator operator--: tree empty");

            // move to the largest value in the tree,
            // which is the last node inorder
            while (nodePtr->right != NULL)
               nodePtr = nodePtr->right;
         } else if (nodePtr->left != NULL)
         {
            // must have gotten here by processing all the nodes
            // on the left branch. predecessor is the farthest
            // right node of the left subtree
            nodePtr = nodePtr->left;

            while (nodePtr->right != NULL)
               nodePtr = nodePtr->right;
         }
         else
         {
            // must have gotten here by going right and then
            // far left. move up the tree, looking for a parent
            // for which nodePtr is a right child, stopping if the
            // parent becomes NULL. a non-NULL parent is the
            // predecessor. if parent is NULL, the original node
            // was the first node inorder, and its predecessor
            // is the end of the list
            p = nodePtr->parent;
            while (p != NULL && nodePtr == p->left)
            {
               nodePtr = p;
               p = p->parent;
            }

            // if we were previously at the left-most node in
            // the tree, nodePtr = NULL, and the iterator specifies
            // the end of the list
            nodePtr = p;
         }

         return *this;
      }

      // postdecrement
      const_iterator operator-- (int)
      {
         // save current const_iterator
         const_iterator tmp = *this;

         // move myself backward to the previous tree node
         --*this;

         // return the previous value
         return tmp;
      }

   private:

      // nodePtr is the current location in the tree. we can move
      // freely about the tree using left, right, and parent.
      // tree is the address of the stree object associated
      // with this iterator. it is used only to access the
      // root pointer, which is needed for ++ and --
      // when the iterator value is end()
      const stnode<T> *nodePtr;
      const stree<T> *tree;

      // used to construct a const_iterator return value from
      // an stnode pointer
      const_iterator (const stnode<T> *p, const stree<T> *t) : nodePtr(p), tree(t)
      {}

};