// CircList.H
// Bi-directional circular list, browser, and iterator: 
// JR 10/17/95  New. Adapted from BaseList.
//  Note: sense of rotation for toJustBefore and After is changed
//  All CircList members tested.
//  Browser tested.
//  Non-invasive Iterator members tested.
//  Rest of Iterator members tested.
//    10/18/95 Added and tested "occurrencesOf" member.
//  Renamed rotateToJustBefore to rotateToJustBeforeThe
//  and added assertion that there is no more than one occurrence
//  of the argument: otherwise equal lists could become unequal
//  by the same operation. (Likewise for rotateToJustBefore.)
//  Tested the changes.
//  Added "ahead" and "behind" members.
// 3/21/96 Added atstart(i.atstart) to Browser copy constructors.
//  4/3/96  Added has().


#ifndef CIRCLIST_H
#define CIRCLIST_H

//#include <iostream.h>
#include <iostream>
using namespace std;
#include <assert.h>
#include "DLNode.H"
#include "LinList.H"
#include "Boolean.H"

// 2006_02_22 ///////////////////////////////////////////////////
// Added to allow compilation with g++ version 3.4.4
template <class T>
class CircList;
template <class T>
ostream& operator << (ostream& out, const CircList<T>& s);
template <class T>
istream& operator>>(istream& in,CircList<T>& L);
// 2006_02_22 //////////////////////////////////////////////////

template <class T>
class CircList
{
   public:
      CircList();
      CircList(const CircList<T>& s);              // copy constructor
      CircList(const LinList<T>& s);               // copy constructor
      CircList(const T* inputarray, int n);        // construct from array of T
      CircList(const T& t);                           // construct from T
      CircList(const T& t1,const T& t2);              // construct from 2 T's
      CircList(const T& t1,const T& t2,const T& t3);  // construct from 3 T's
     ~CircList();                               // destructor
      Boolean isEmpty() const;
      int length() const;                     // return number of elements

      CircList<T>& operator=(const CircList<T>& L); // assignment
      CircList<T>& operator=(const LinList<T>& L); // assignment

      CircList<T>& clear();   // remove all elements

      CircList<T>& pushf(const T&);        // insert at beginning
      CircList<T>& pushb(const T&);             // insert at end
      CircList<T>& pushf(const CircList<T>& L);    // append a list
      CircList<T>& pushb(const CircList<T>& L);    // prepend a list
      CircList<T>& pushf(const LinList<T>& L);     // append a list
      CircList<T>& pushb(const LinList<T>& L);    // prepend a list

      T popf();                               // return and delete first element
      T popb();                               // return and delete last element

      T ahead() const
      { return fpointer->data; }
      T behind() const
      { return bpointer->data; }

      CircList<T>& rotatef();         // rotate list forward one node
      CircList<T>& rotateb();         // rotate list backward one node
      Boolean rotateToJustBeforeThe(const T& t);// position list just before t
      Boolean rotateToJustAfterThe(const T& t); // position list just atfer t

      Boolean operator==(const CircList<T>& L) const;
      Boolean operator!=(const CircList<T>& L) const;

      int occurrencesOf(const T& t) const;  // return number of times t occurs
      Boolean has(const T& t) const;

      friend ostream& operator << <> (ostream& out, const CircList<T>& s);
      friend istream& operator>> <> (istream& in,CircList<T>& L); 


// private:
   protected:
      DLNode<T>* fpointer;    // We think of the "current position" as
      DLNode<T>* bpointer;    // being *between* nodes.

      friend class CircListBrowser<T>;
      friend class CircListIterator<T>;

};

//==== CircList<T> implementation =======================================

template <class T>
Boolean CircList<T>::has(const T& t) const 
{
 CircListBrowser<T> i(*this);
 for(i.init();i.ok();++i) if(i.ahead()==t) return 1;
 return 0;
}


      template <class T>                        // initializer from array
      CircList<T>::CircList(const T* tarray, int n )
         : fpointer(0), bpointer(0)
      {   while(n)
          {   pushf(tarray[--n]);
          }
      }
      template <class T>                        // initializer from T
      CircList<T>::CircList(const T& t )
         : fpointer(0), bpointer(0)
      {   pushb(t);
      }
      template <class T>                        // initializer from 2 T's
      CircList<T>::CircList(const T& t1,const T& t2)
         : fpointer(0), bpointer(0)
      {   pushb(t1);
          pushb(t2);
      }
      template <class T>                        // initializer from 3 T's
      CircList<T>::CircList(const T& t1,const T& t2,const T& t3)
         : fpointer(0), bpointer(0)
      {   pushb(t1);
          pushb(t2);
          pushb(t3);
      }
      template <class T>                        // copy constructor
      CircList<T>::CircList(const CircList<T>& s)
         : fpointer(0), bpointer(0)
      {
          CircListBrowser<T> si(s);
          for( si.init(); si.ok(); ++si )
          {   pushb(si.ahead());
          }
      }
      template <class T>                        // copy constructor
      CircList<T>::CircList(const LinList<T>& s)
         : fpointer(0), bpointer(0)
      {
          LinListBrowser<T> si(s);
          for( si.init(); si.ok(); ++si )
          {   pushb(si.ahead());
          }
      }
      template <class T>                        // constructor of empty list
      CircList<T>::CircList()
         : fpointer(0), bpointer(0)
      {}

      template <class T>                        // destructor
      CircList<T>::~CircList()
      {
           while( !isEmpty() ) popb();
      }

      template <class T>                        // determine if empty
      Boolean CircList<T>::isEmpty() const
      {        return fpointer==0;
      }

      template <class T>                        // number of elements
      int CircList<T>::length() const
      {
                CircListBrowser<T> i(*this);
                int tmp=0;
                for(i.init();i.ok();++i)  ++tmp;
                return tmp;
      }

      template <class T>                        // insert at beginning
      CircList<T>& CircList<T>::pushf(const T& t)
      {   DLNode<T>* node = new DLNode<T>(t);
          if(fpointer)
          {   node->next=fpointer;
              node->prev=bpointer;
              fpointer=fpointer->prev=bpointer->next=node;
          }
          else  // list is empty
          {
              node->next=node->prev=fpointer=bpointer=node;
          }
   return *this;
      }

      template <class T>                        // insert at end
      CircList<T>& CircList<T>::pushb(const T& t)
      {   DLNode<T>* node = new DLNode<T>(t);
          if(bpointer)
          {   node->next=fpointer;
              node->prev=bpointer;
              bpointer=bpointer->next=fpointer->prev=node;
          }
          else  // list is empty
          {
              node->next=node->prev=fpointer=bpointer=node;
          }
   return *this;
      }

      template <class T>
      T CircList<T>::popf()  // return and remove first element
      {   assert(fpointer);
          T tmp(fpointer->data);
          if(fpointer==bpointer) // only 1 element in list
          {   delete fpointer;
              fpointer=0;
              bpointer=0;
          }
          else
          {   bpointer->next=fpointer->next;
              fpointer->next->prev=bpointer;
              delete fpointer;
              fpointer=bpointer->next;
          }
          return tmp;
      }

      template <class T>
      T CircList<T>::popb()  // return and remove last element
      {   assert(bpointer);
          T tmp(bpointer->data);
          if(fpointer==bpointer) // only 1 element in list
          {   delete fpointer;
              fpointer=0;
              bpointer=0;
          }
          else
          {   fpointer->prev=bpointer->prev;
              bpointer->prev->next=fpointer;
              delete bpointer;
              bpointer=fpointer->prev;
          }
          return tmp;
      }

      template <class T>
      CircList<T>& CircList<T>::pushb(const CircList<T>& L)
      {
          if(&L==this)       //  append to self
          {
              CircList<T> tmp(L);
              pushb(tmp);   // using recursion !
          }
          else
          {
              CircListBrowser<T> i(L);
              for(i.init(); i.ok(); ++i ) pushb(i.ahead());
          }
          return *this;
      }

      template <class T>
      CircList<T>& CircList<T>::pushb(const LinList<T>& L)
      {
              LinListBrowser<T> i(L);
              for(i.init(); i.ok(); ++i ) pushb(i.ahead());
       return *this;
      }

      template <class T>
      CircList<T>& CircList<T>::pushf(const CircList<T>& L)
      {
          if(&L==this)       //  append to self
          {
              CircList<T> tmp(L);
              pushf(tmp);   // using recursion !
          }
          else
          {
              CircListBrowser<T> i(L);
              for(i.init(); i.ok(); --i ) pushf(i.behind());
          }
          return *this;
      }

      template <class T>
      CircList<T>& CircList<T>::pushf(const LinList<T>& L)
      {
              LinListReverseBrowser<T> i(L);
              for(i.init(); i.ok(); ++i ) pushf(i.ahead());
              return *this;
      }

      template <class T>
      CircList<T>& CircList<T>::operator=(const CircList<T>& L)   // assignment
      {
          if(this==&L) return *this;   // assignment to self

          while( !isEmpty() ) popb();  // delete any existing list
   pushf(L);
          return *this;
      }

      template <class T>
      CircList<T>& CircList<T>::operator=(const LinList<T>& L)   // assignment
      {
          while( !isEmpty() ) popb();  // delete any existing list
   pushf(L);
          return *this;
      }

      template <class T>
      CircList<T>& CircList<T>::clear()  // remove all elements
      {
          while( !isEmpty() ) popb(); 
          return *this;
      }

      template <class T>
      CircList<T>& CircList<T>::rotateb()  
           // rotate the list backward (current pos forward!)
      {   if(!fpointer) return *this;
   bpointer=fpointer;
   fpointer=fpointer->next;
   return *this;   
      }

      template <class T>
      CircList<T>& CircList<T>::rotatef()  
  // rotate the list forward (current pos backward!)
      {   if(!bpointer) return *this;
   fpointer=bpointer;
   bpointer=bpointer->prev;
   return *this;   
      }

      template <class T>
      Boolean CircList<T>::rotateToJustBeforeThe(const T& t)  // position list just before t
      {   if(!fpointer) return 0;
   assert((*this).occurrencesOf(t)<2); 
   if( fpointer->data==t ) return 1;  // already in desired position
   DLNode<T>* start=fpointer;
   while(1)
   {   rotateb();
       if(fpointer==start) return 0; // all elements inspected, t not found
              if( fpointer->data==t) return 1;
          }
      }

      template <class T>
      Boolean CircList<T>::rotateToJustAfterThe(const T& t)  // position list just after t
      {
   if( !rotateToJustBeforeThe(t) ) return 0;
   rotateb();
   return 1;
      }


template <class T>
Boolean CircList<T>::operator==(const CircList<T>& L) const // equality
{
 if( this == &L ) return 1;
 int tl=length();
 int Ll=L.length();
 if( tl != Ll ) return 0;
 if( tl==0 )    return 1;

 // Without the funny constructor ListBrowser<T>(ListBrowser<T>),
 // it's awkward to do this without making a copy

 CircList<T> tmp(*this);  // Ouch!

 CircListBrowser<T> i(*this),k(L);
 Boolean match;
 for( i.init(); i.ok(); ++i,tmp.rotatef() )
 {
  match=1;
  CircListBrowser<T> j(tmp);  
  for( j.init(),k.init(); j.ok() ; ++j,++k )
  {
   if( j.ahead() != k.ahead() ) 
   {
    match=0;
    break;
   }
  }
  if( match ) return 1;     
 }
 return 0;
}

template <class T>
Boolean CircList<T>::operator!=(const CircList<T>& L) const // equality
{
 return !((*this)==L);
}

template <class T>
int CircList<T>::occurrencesOf(const T& t) const
{
 CircListBrowser<T> i(*this);
 int n=0;
 for(i.init();i.ok();++i) if(i.ahead()==t) ++n;
 return n;  
}

template <class T>
ostream& operator << (ostream& out, const CircList<T>& s)
{    out << "< ";
     CircListBrowser<T> i(s);
 for(i.init(); i.ok(); ++i )
                out << i.ahead() << " ";
        out << ">";
   return out;
}

template <class T>
istream& operator>>(istream& in,CircList<T>& L)
{
 L.clear();
 int c;
 T tmp;
 while ( (c=in.get()) != '<' )
 {}
 while(in)
 {
  while((c=in.get()) == ' ' || c==',' || c=='\n' )
  {}
  if(  c== '>' ) return in;
  in.putback(c);
  in >> tmp;
  L.pushb(tmp);
 }
}

/******************************
      template <class T>  // diagnostic version
      ostream& operator << (ostream& out, const CircList<T>& s)
      {   out << "<- " << s.bpointer << " , " << s.fpointer << "->\n";
          out << "...\n";
          CircListIterator<T> i(s);
          for(i.init(); i.ok(); ++i )
                out << i.f << ":   < " << i.f->prev << "  " << i.f->data << "  "
                     << i.f->next << " >\n";
          out << "...\n";
          return out;
      }
***********************/

/////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////
template <class T>
class CircListBrowser
{
        // JR 8/25/95
        // This is largely almost identical to CircListIterator.
        // The differences are: no list-modifying member functions,
        //                      const ref to list.

   public:
        CircListBrowser(const CircList<T>& s);      // constructor (binds to list)
        CircListBrowser(const CircListBrowser<T>& i);   // copy constructor 
                // 9/27/95 Note: Originally bound to list
                // with head at current position of i,
                // but this conflicted with the need to
                // actually have a copy constructor.
        CircListBrowser(const CircListIterator<T>& i);  // copy constructor 
       ~CircListBrowser() {}                        // destructor
        void init();                            // initializer
        CircListBrowser<T>& operator=(int n);      // initialize with offset
                                                // This is NOT assignment!
        int ok();                               // test for back to start
 
        CircListBrowser<T>& operator++();          // prefix, step forward over one node
        CircListBrowser<T>  operator++(int);       // postfix, step forward over one node
        CircListBrowser<T>& operator--();          // prefix, step backward over one node
        CircListBrowser<T>  operator--(int);       // postfix, step backward over one node

        T& ahead() const;                       // ref to data in node ahead
        T& behind() const;                      // ref to data in node behind

   private:
        const CircList<T>&    list; // reference to  list, reinstated 10/7/95
        DLNode<T>*   f;          // pointer to node ahead
        DLNode<T>*   b;          // pointer to node behind
        int          atstart;    // used to get around problem that
                                 // end-condition is same as start-condition
};

//==== CircListBrowser<T> implementation =======================================

      template <class T>
      CircListBrowser<T>::CircListBrowser(const CircList<T>& s)   // constructor
         : list(s)
      {}

/* original version was different: see note beside declaration.
      template <class T>
      CircListBrowser<T>::CircListBrowser(const CircListBrowser<T>& i)
         : list.fpointer(i.f),
           list.bpointer(i.b)
      {}
*/

      template <class T>                // copy constructor
      CircListBrowser<T>::CircListBrowser(const CircListBrowser<T>& i)
         : list(i.list),f(i.f),b(i.b),atstart(i.atstart)
      {}

      template <class T>                // copy constructor
      CircListBrowser<T>::CircListBrowser(const CircListIterator<T>& i)
         : list(i.list),f(i.f),b(i.b),atstart(i.atstart)
      {}

      template <class T>
      void CircListBrowser<T>::init()          // initialization
      {                                      // Can also use  =0
 	  f=list.fpointer;
          b=list.bpointer;
          atstart=1;
      }
      template <class T>
      CircListBrowser<T>& CircListBrowser<T>::operator=(int n)
      {                                       // offset initialization
					      // (NOT assignment!)
 	  f=list.fpointer;
          b=list.bpointer;
          if(list.fpointer)
          {
              if(n>0) while(n) {++(*this); n--;}
              if(n<0) while(n) {--(*this); n++;}
          }
          atstart=1;
          return *this;
      }

      template <class T>
      CircListBrowser<T>& CircListBrowser<T>::operator++()
      {
          if( !list.fpointer ) return *this;
          b=f;
          f=f->next;
          atstart=0;
          return *this;
      }

      template <class T>
      CircListBrowser<T> CircListBrowser<T>::operator++(int)  // postfix version
      {
	  assert(0);  // Forbid use: this is inefficient compared with prefix
          if( !list.fpointer ) return *this;
	  CircListBrowser<T> tmp(*this);
          b=f;
          f=f->next;
          atstart=0;
          return tmp;
      }

      template <class T>
      CircListBrowser<T>& CircListBrowser<T>::operator--()
      {
          if( !list.bpointer ) return *this;
 	  f=b;
          b=b->prev;
          atstart=0;
          return *this;
      }

      template <class T>
      CircListBrowser<T> CircListBrowser<T>::operator--(int) // postfix version
      {
	  assert(0);  // Forbid use: this is extremely inefficient compared with prefix
          if( !list.bpointer ) return *this;
	  CircListBrowser<T> tmp(*this);
 	  f=b;
          b=b->prev;
          atstart=0;
          return tmp;
      }

      template <class T>
      int CircListBrowser<T>::ok()
      {
                if(!list.fpointer) return 0;  // List is empty
                if(atstart) return 1;
                return f!=list.fpointer;
      }

      template <class T>
      T& CircListBrowser<T>::ahead() const
      {
                return f->data;
      }

      template <class T>
      T& CircListBrowser<T>::behind() const
      {
                return b->data;
      }


/////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////


template <class T>
class CircListIterator
{
   public:
        CircListIterator(CircList<T>& s);           // constructor (binds to list)
       ~CircListIterator() {}                      // destructor
        void init();                            // initializer
        CircListIterator<T>& operator=(int n);     // initialize with offset
                                                // This is NOT assignment!
        int ok();                               // test for back to start
        CircListIterator<T>& operator++();         // prefix, step forward over one node
        CircListIterator<T>  operator++(int);      // postfix, step forward over one node
        CircListIterator<T>& operator--();         // prefix, step backward over one node
        CircListIterator<T>  operator--(int);      // postfix, step backward over one node

        T& ahead() const;                       // ref to data in node ahead
        T& behind() const;                      // ref to data in node behind

        void insertf(const T& t);               // insert new node ahead
        void insertb(const T& t);               // insert new node behind
        void insertf(const CircList<T>& );      // insert list ahead
        void insertb(const CircList<T>& );      // insert list behind
        void insertf(const LinList<T>& );       // insert list ahead
        void insertb(const LinList<T>& );       // insert list behind

        void replacef(const T& t);              // replace data in node ahead
        void replaceb(const T& t);              // replace data in node behind

        void deletef();                         // delete node ahead
        void deleteb();                         // delete node behind

   private:

        CircList<T>&    list;    // reference to  list : reinstated 10/7/95
        DLNode<T>*   f;          // pointer to node ahead
        DLNode<T>*   b;          // pointer to node behind
        int          atstart;    // used to get around problem that
                                 // end-condition is same as start-condition

        friend class CircListBrowser<T>;
};

//==== CircListIterator<T> implementation =======================================

      template <class T>
      CircListIterator<T>::CircListIterator(CircList<T>& s)   // constructor
         : list(s)
      {}
      template <class T>
      void CircListIterator<T>::init()          // initialization
      {                                      // Can also use  =0
          f=list.fpointer;
          b=list.bpointer;
          atstart=1;
      }
      template <class T>
      CircListIterator<T>& CircListIterator<T>::operator=(int n)
      {                                       // offset initialization
          f=list.fpointer;
          b=list.bpointer;
          if(list.fpointer)
          {
              if(n>0) while(n) {++(*this); n--;}
              if(n<0) while(n) {--(*this); n++;}
          }
          atstart=1;
          return *this;
      }

      template <class T>
      CircListIterator<T>& CircListIterator<T>::operator++()
      {
          if( !list.fpointer ) return *this;
          b=f;
          f=f->next;
          atstart=0;
          return *this;
      }

      template <class T>
      CircListIterator<T> CircListIterator<T>::operator++(int)  // postfix version
      {
	  assert(0);  // Forbid use: this is extremely inefficient compared with prefix
          if( !list.fpointer ) return *this;
	  CircListIterator<T> tmp(*this);
          b=f;
          f=f->next;
          atstart=0;
          return tmp;
      }

      template <class T>
      CircListIterator<T>& CircListIterator<T>::operator--()
      {
          if( !list.bpointer ) return *this;
 	  f=b;
          b=b->prev;
          atstart=0;
          return *this;
      }

      template <class T>
      CircListIterator<T> CircListIterator<T>::operator--(int) // postfix version
      {
	  assert(0);  // Forbid use: this is extremely inefficient compared with prefix
          if( !list.bpointer ) return *this;
	  CircListIterator<T> tmp(*this);
 	  f=b;
          b=b->prev;
          atstart=0;
          return tmp;
      }

      template <class T>
      int CircListIterator<T>::ok()
      {
 		if(!list.fpointer) return 0;  // List is empty
                if(atstart) return 1;
                return f!=list.fpointer;
      }

      template <class T>
      T& CircListIterator<T>::ahead() const
      {
 		return f->data;
      }

      template <class T>
      T& CircListIterator<T>::behind() const
      {
 		return b->data;
      }

      template <class T>
      void CircListIterator<T>::replacef(const T& t)
       {
                (f->data)=t;
      }

      template <class T>
      void CircListIterator<T>::replaceb(const T& t)
      {
                (b->data)=t;
      }

      template <class T>
      void CircListIterator<T>::insertf(const T& t)
      {
          DLNode<T>* node = new DLNode<T>(t);
	  if(list.fpointer)  // list not empty
	  {
	        node->next=f;
          	node->prev=b;
          	f=f->prev=b->next=node;
          	if(b==list.bpointer) list.fpointer=f;
	  }
	  else
	  {
		f=b=list.fpointer=list.bpointer=node->next=node->prev=node;
	  }
      }

      template <class T>
      void CircListIterator<T>::insertf(const CircList<T>& L)   
      {           		
	  if(&list==&L)  // inserting list into self
	  {	
		CircList<T> tmp(list);
		insertf(tmp);
	  }
	  else
	  {
	        CircListBrowser<T> i(L);
	  	for(i.init();i.ok();--i) insertf(i.behind());
	  }
      }

      template <class T>
      void CircListIterator<T>::insertf(const LinList<T>& L)   
      {           		
	        LinListBrowser<T> i(L);
	  	for(i.init();i.ok();--i) insertf(i.behind());
      }

      template <class T>
      void CircListIterator<T>::insertb(const T& t)
      {
          DLNode<T>* node = new DLNode<T>(t);
	  if(list.fpointer)  // list not empty
	  {
             node->next=f;
             node->prev=b;
             b=f->prev=b->next=node;
             if(f==list.fpointer) list.bpointer=b;
	  }
	  else
	  {
		f=b=list.fpointer=list.bpointer=node->next=node->prev=node;
	  }
      }

      template <class T>
      void CircListIterator<T>::insertb(const CircList<T>& L)    
      {           			
	  if(&list==&L)  // inserting list into self
	  {	
		CircList<T> tmp(list);
		insertb(tmp);
	  }
	  else
	  {
	  	CircListBrowser<T> i(L);
	  	for(i.init();i.ok();++i) insertb(i.ahead());
	  }
      }

      template <class T>
      void CircListIterator<T>::insertb(const LinList<T>& L)    
      {           			
	  	LinListBrowser<T> i(L);
	  	for(i.init();i.ok();++i) insertb(i.ahead());
      }

      template <class T>
      void CircListIterator<T>::deletef()
      {
          assert( list.fpointer );  // Make sure list not already empty.
          if( list.fpointer == list.bpointer ) // One element
          {   f=b=list.fpointer=list.bpointer=0;
              return; 
          }
          DLNode<T>* newf=f->next;
          f->prev->next = newf;
          newf->prev=f->prev;
          if     ( f==list.fpointer ) // deleting first element
                  list.fpointer=newf; 
          else if( f==list.bpointer ) list.bpointer=b;
          delete f;
          f=newf;
      } 

      template <class T>
      void CircListIterator<T>::deleteb()
      {
          assert( list.bpointer );  // Make sure list not already empty.
          if( list.fpointer == list.bpointer ) // One element
          {   f=b=list.fpointer=list.bpointer=0;
              return; 
          }
          DLNode<T>* newb=b->prev;
          b->next->prev = newb;
          newb->next=b->next;
          if     ( b==list.bpointer ) list.bpointer=newb; // deleting first element
          else if( b==list.fpointer ) list.fpointer=f;
          delete b;
          b=newb;
      } 

#endif