// LinList.H
// JR 10/15/95  Totally new linear list,
//   with forward and reverse iterators and browsers.
//    10/16/95  All functions successfully tested.
// later   Added == and !=
//  Added Browser from Iterator copy constructors
//    10/17/95  Disallowed Iterator delete from empty list.
//  Added and tested commonLeadingSublist.
//         Put DLNode in a separate header file.
//    10/18/95  Added constructor from CircList.
//    10/19/95  Tested constructor from CircList.
//              Added include of CircList.H. (Otherwise won't compile.)
//    10/24/95  Added and tested operator[].
//  Forced to make non-const versions of Iterator::ahead and behind.
//  Discovered and fixed error in constructor 
//  LinListIterator(LinList<T>&). 
//   Added bok() (backwards ok) for Iterators and Browsers.
//    10/26/95  Added const T& first() and last().
//    12/28/95  Noticed and fixed problem with L.prepend(L), L.append(L).
//     1/1/96   Note fixed bug in work of 12/28/95 (which had never been tested!).
//     1/1/96 Qi said that in Borland C++, a copy constructor will call
//  the default constructor first, and therefore I have a
//  memory leak (duplicate calls to "new"). This is not the 
//  case in Irix. I checked.
//     1/2/96   In iterators' ++, might want to take out assert(ok), since
//  we may want to try to advance past the end before checking
//  that it's ok().
//     3/9/96   Added and tested LinList(istream&).
//     3/10/96  Added substitute( old, new ).
//     4/3/96   Added has().
//     4/7/96 Commented out the #include "CircList.H".
//  Not sure why it was there in the first place.
//  It was interfering with compilation of istream stuff.
//  Added indexOf.
  
#ifndef LINLIST_H
#define LINLIST_H

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

template <class T>
class CircList;

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


template <class T>
class LinList
{
   private:
 DLNode<T>* lptr; // ptr to dummy node sitting before first element
 DLNode<T>* rptr; // ptr to dummy node sitting after   last element

   public:
 LinList();     // construct empty list
 LinList(const T& t);                            // construct from T
 LinList(const T& t1,const T& t2);               // construct from 2 T's
 LinList(const T& t1,const T& t2,const T& t3);   // construct from 3 T's LinList(istream& in);
 LinList(const LinList<T>& L);   // copy constructor 
  LinList(const T& first,const CircList<T>& L); // copy constructor 
       ~LinList();     // destructor
 LinList<T>& clear();    // delete all elements
 LinList<T>& operator=(const LinList<T>& L);     // assignment

 Boolean isEmpty() const
 { return( lptr->next==rptr);
 }
 int length() const;

 Boolean operator==(const LinList<T>& L) const;
 Boolean operator!=(const LinList<T>& L) const;
 
 LinList<T>& prepend(const T& t);
 LinList<T>& prepend(const LinList<T>& L);
	LinList<T>& append(const T& t);
	LinList<T>& append(const LinList<T>& L);

	T popFirst();
	T popLast();
	const T& first() const;
	const T& last() const;

	T& operator[](int k);
	const T& operator[](int k) const;

	int indexOf(const T& t) const;

	LinList<T> commonLeadingSublist( const LinList<T>& other ) const;

	void substitute( T oldt, T newt );

	Boolean has(const T& t) const;

	friend ostream& operator<< <> (ostream& out, const LinList<T>& s);
	friend istream& operator>> <> (istream& in,LinList<T>& L);	
	friend class LinListBrowser<T>;
	friend class LinListReverseBrowser<T>;
	friend class LinListIterator<T>;
	friend class LinListReverseIterator<T>;
};

template <class T>
int LinList<T>::indexOf(const T& t) const	// This is a quick fix.
						// Don't use extensively!
{
	LinListBrowser<T> i(*this);
	int k=0;
	for(i.init();i.ok();++i)
	{
		if(t==i.ahead()) return k;
		else k++;
	}

	assert(0);	// t is not in the list.
}


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

template <class T>
LinList<T>::LinList()
{	
	lptr = new DLNode<T>;
	rptr = new DLNode<T>;
	lptr->next=rptr;
	rptr->prev=lptr;
}

template <class T>
LinList<T>::LinList(const T& t)
{	
	lptr = new DLNode<T>;
	rptr = new DLNode<T>;
	lptr->next=rptr;
	rptr->prev=lptr;
	prepend(t);
}

template <class T>
LinList<T>::LinList(const T& t1,const T& t2)
{	
	lptr = new DLNode<T>;
	rptr = new DLNode<T>;
	lptr->next=rptr;
	rptr->prev=lptr;
	prepend(t2);
	prepend(t1);
}

template <class T>
LinList<T>::LinList(const T& t1,const T& t2,const T& t3)
{	
	lptr = new DLNode<T>;
	rptr = new DLNode<T>;
	lptr->next=rptr;
	rptr->prev=lptr;
	prepend(t3);
	prepend(t2);
	prepend(t1);
}

template <class T>
LinList<T>::LinList(const LinList<T>& L)
{	
	lptr = new DLNode<T>;
	rptr = new DLNode<T>;
	lptr->next=rptr;
	rptr->prev=lptr;
	prepend(L);
}

template <class T>                        
LinList<T>::LinList(const T& first,const CircList<T>& L) // copy constructor
{
	lptr = new DLNode<T>;
	rptr = new DLNode<T>;
	lptr->next=rptr;
	rptr->prev=lptr;
	CircList<T> tmp(L);
	assert(tmp.rotateToJustBeforeThe(first));
	while(!tmp.isEmpty()) append(tmp.popf());
}	

template <class T>                        // destructor
LinList<T>::~LinList()
{
	clear();
	delete rptr;
	delete lptr;
}

template <class T>                        // delete all elements
LinList<T>& LinList<T>::clear()
{
	while( !isEmpty() ) popFirst();
	return *this;
}

template <class T>                       
LinList<T>& LinList<T>::operator=(const LinList<T>& L)	//assignment
{
	if(&L!=this)
	{	
		clear();
		append(L);
	}		
	return *this;	
}

	
template <class T>
int LinList<T>::length() const
{
	LinListBrowser<T> i(*this);
	int len=0;
	for(i.init();i.ok();++i) 
	{
		len++;
//cout << " + " << i.ahead() << " : " << len << endl;
	}
	return len;
}

template <class T>
Boolean LinList<T>::operator==(const LinList<T>& L) const
{
	if( &L==this ) return 1;
	LinListBrowser<T> i1(*this);
	LinListBrowser<T> i2(L);
	for(i1.init(),i2.init(); i1.ok(); ++i1,++i2)
	{
		if(!i2.ok()) return 0;
		if( i1.ahead()!=i2.ahead() ) return 0;
	}
	if(i2.ok()) return 0;
	return 1;
}

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

template <class T>
LinList<T>& LinList<T>::prepend(const T& t)
{
	DLNode<T>* node = new DLNode<T>(t);
	node->next=lptr->next;
	node->prev=lptr;
	lptr->next=node->next->prev=node;
	return *this;
}

template <class T>
LinList<T>& LinList<T>::prepend(const LinList<T>& L)
{
	if(&L==this)
	{
		LinList<T> tmp(L);
		LinListReverseBrowser<T> i(tmp);
		for(i.init();i.ok();++i) prepend(i.ahead());
	}
	else
	{
		LinListReverseBrowser<T> i(L);
		for(i.init();i.ok();++i) prepend(i.ahead());
	}
	return *this;
}

template <class T>
LinList<T>& LinList<T>::append(const T& t)
{
	DLNode<T>* node = new DLNode<T>(t);
	node->next=rptr;
	node->prev=rptr->prev;
	rptr->prev=node->prev->next=node; // segfault while testing 10/19/95
	return *this;
}

template <class T>
LinList<T>& LinList<T>::append(const LinList<T>& L)
{
	if(&L==this)
	{
		LinList<T> tmp(L);
		LinListBrowser<T> i(tmp);
		for(i.init();i.ok();++i) append(i.ahead());
	}
	else
	{
		LinListBrowser<T> i(L);
		for(i.init();i.ok();++i) append(i.ahead());
	}
	return *this;
}

template <class T>
T LinList<T>::popFirst()
{
	assert( !isEmpty() );
	DLNode<T>* deletee=lptr->next;
	T tmp=deletee->data;
	deletee->next->prev=lptr;
	lptr->next=deletee->next;
	delete deletee;	
	return tmp;
}

template <class T>
T LinList<T>::popLast()
{
	assert( !isEmpty() );
	DLNode<T>* deletee=rptr->prev;
	T tmp=deletee->data;
	deletee->prev->next=rptr;
	rptr->prev=deletee->prev;
	delete deletee;	
	return tmp;
}

template <class T>
const T& LinList<T>::first() const
{
	assert( !isEmpty() );
	return lptr->next->data;
}

template <class T>
const T& LinList<T>::last() const
{
	assert( !isEmpty() );
	return rptr->prev->data;
}

template <class T>
const T& LinList<T>::operator[](int k) const
{
			// check subscript valid
	Boolean subscriptValid=( (k>=0) && (k<length()) );
	if(!subscriptValid)
	{
		cout << k << "th element requested of list " 
		     << (*this) << " (which doesn't have one)." << endl;
		assert( subscriptValid );
	}	
	LinListBrowser<T> i(*this);
	while((k--)>0) ++i;
	return i.ahead();
}

template <class T>
T& LinList<T>::operator[](int k)
{
	assert( (k>=0) && (k<length()) );	// check subscript valid
	LinListIterator<T> i(*this);
	while((k--)>0) ++i;
	return i.ahead();
}



template <class T>
LinList<T> LinList<T>::commonLeadingSublist( const LinList<T>& other ) const
{
        LinListBrowser<T> i1(*this);
        LinListBrowser<T> i2(other);

        LinList<T> tmp;

        for( i1.init(),i2.init(); (i1.ok())&&(i2.ok()); ++i1,++i2)
        {
                if( i1.ahead() != i2.ahead() ) return tmp;
		tmp.append(i1.ahead());
        }

        return tmp;
}

template <class T>
void LinList<T>::substitute( T oldt, T newt )
{
	LinListIterator<T> i(*this);
	for(i.init();i.ok();++i) if(i.ahead()==oldt) i.ahead()=newt;
}

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


template <class T>
istream& operator>>(istream& in,LinList<T>& L)
{
	while( !L.isEmpty() ) L.popFirst();
	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.append(tmp);
	}
}


//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
// LinListIterator<T>

template <class T>
class LinListIterator
{
   public:
	LinListIterator(LinList<T>& s);         // constructor (binds to list)

	LinListIterator(const LinListIterator<T>& i)	// copy constructor
	: list(i.list),f(i.f),b(f->prev)
	{}

       ~LinListIterator()                          // destructor
	{}

	LinListIterator<T>& operator=(const LinListIterator<T>& i)
	{	list=i.list;
		f=i.f;
		b=i.b;
		return *this;
	}
	
        void init()                             // initializer
	{  b=list.lptr; f=b->next; }

        LinListIterator<T>& operator=(int n);	// initialize with offset
                                              	// This is NOT assignment!

        int ok() const                          // test for more elements
	{ return(f!=list.rptr); }
        int bok() const                         // test for elements behind
	{ return(b!=list.lptr); }

	LinListIterator<T>& operator++();   // prefix,  step forward  over one node
        LinListIterator<T>& operator++(int);// postfix, step forward  over one node
        LinListIterator<T>& operator--();   // prefix,  step backward over one node
        LinListIterator<T>& operator--(int);// postfix, step backward over one node

        T& ahead()             // ref to data in node ahead
	{	assert( ok() );
		return f->data;
	}
        T& behind()             // ref to data in node behind
	{	assert( b != list.lptr );
		return b->data;
	}

        const T& ahead() const           // const ref to data in node ahead
	{	assert( ok() );
		return f->data;
	}
        const T& behind() const          // const ref to data in node behind
	{	assert( b != list.lptr );
		return b->data;
	}

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

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

        void replacef(const T& t)               // replace data in node ahead
	{	assert(f!=list.rptr);
		f->data=t;	
	}
        void replaceb(const T& t)               // replace data in node behind
	{	assert(b!=list.lptr);
		b->data=t;	
	}

        void replacef(const LinList<T>& );      // replace node ahead
        void replaceb(const LinList<T>& );      // replace node behind

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

   private:

        LinList<T>&  list;    	// reference to  list
        DLNode<T>*   f;        	// pointer to node ahead
        DLNode<T>*   b;       	// pointer to node behind

        friend class LinListBrowser<T>;
};

template <class T>
LinListIterator<T>::LinListIterator(LinList<T>& s)   // constructor
: list(s), f(s.lptr->next), b(s.lptr)
{}

template <class T>
LinListIterator<T>& LinListIterator<T>::operator=(int n)// offset initialization
{                                                       // NOT assignment   
	init();
	assert(n>=0);
	while(n--)
	{	assert(ok());
		++(*this);
	}
	return *this;
}
 		
template <class T>
LinListIterator<T>& LinListIterator<T>::operator++()
{
     if( list.isEmpty() ) return *this;
     assert( ok() ); 		// Make sure not already at end.
     b=f;
     f=f->next;
     return *this;
}

template <class T>
LinListIterator<T>& LinListIterator<T>::operator++(int)  // postfix
{
	assert(0);
	// Use prefix!
	return *this;
}

template <class T>
LinListIterator<T>& LinListIterator<T>::operator--()
{
     if( list.isEmpty() ) return *this;
     assert( b!=list.lptr );		// Make sure not already at beginning.
     f=b;
     b=b->prev;
     return *this;
}

template <class T>
LinListIterator<T>& LinListIterator<T>::operator--(int)  // postfix
{
	assert(0);
	// Use prefix!
	return *this;
}

template <class T>
void LinListIterator<T>::insertf(const T& t)
{
	DLNode<T>* node = new DLNode<T>(t);
	node->next=f;
	node->prev=b;
	f=b->next=f->prev=node;
}	

template <class T>
void LinListIterator<T>::insertf(const LinList<T>& L)
{
	LinListReverseBrowser<T> i(L);
	for(i.init(); i.ok(); ++i) insertf(i.ahead());
}

template <class T>
void LinListIterator<T>::insertb(const T& t)
{
	DLNode<T>* node = new DLNode<T>(t);
	node->next=f;
	node->prev=b;
	b=f->prev=b->next=node;
}	

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

template <class T>
void LinListIterator<T>::replacef(const LinList<T>& L)        // replace data in node ahead
{	assert(f!=list.rptr);
	deletef();
	insertf(L);	
}

template <class T>
void LinListIterator<T>::replaceb(const LinList<T>& L)        // replace data in node behind
{	assert(b!=list.lptr);
	deleteb();
	insertb(L);	
}

template <class T>
void LinListIterator<T>::deletef()
{
	assert( ok() );		// Make sure there is an element to delete.
	DLNode<T>* deletee=f;
	f=deletee->next;
	f->prev=b;
	b->next=f;
	delete deletee;
} 

template <class T>
void LinListIterator<T>::deleteb()
{
	assert( b!=list.lptr );	// Make sure there is an element to delete.
	DLNode<T>* deletee=b;
	b=deletee->prev;
	b->next=f;
	f->prev=b;
	delete deletee;
} 

//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
// LinListReverseIterator<T>

template <class T>
class LinListReverseIterator
{
   public:
	LinListReverseIterator(LinList<T>& s);         // constructor (binds to list)

	LinListReverseIterator(const LinListReverseIterator<T>& i)	// copy constructor
	: list(i.list),b(i.b),f(i.f)
	{}

       ~LinListReverseIterator()                          // destructor
	{}

	LinListReverseIterator<T>& operator=(const LinListReverseIterator<T>& i)
	{	list=i.list;
		f=i.f;
		b=i.b;
		return *this;
	}
	
        void init()                             // initializer
	{  b=list.rptr; f=b->prev; }

        LinListReverseIterator<T>& operator=(int n);	// initialize with offset
                                              	// This is NOT assignment!

        int ok() const                          // test for more elements
	{ return(f!=list.lptr); }
        int bok() const                          // test for more elements
	{ return(b!=list.rptr); }

	LinListReverseIterator<T>& operator++();   // prefix,  step forward  over one node
        LinListReverseIterator<T>& operator++(int);// postfix, step forward  over one node
        LinListReverseIterator<T>& operator--();   // prefix,  step backward over one node
        LinListReverseIterator<T>& operator--(int);// postfix, step backward over one node

        const T& ahead()  const             // const ref to data in node ahead
	{	assert( ok() );
		return f->data;
	}
        const T& behind() const             // const ref to data in node behind
	{	assert( b != list.rptr );
		return b->data;
	}

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

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

        void replacef(const T& t)               // replace data in node ahead
	{	assert(f!=list.lptr);
		f->data=t;	
	}
        void replaceb(const T& t)               // replace data in node behind
	{	assert(b!=list.rptr);
		b->data=t;	
	}

        void replacef(const LinList<T>& );      // replace node ahead
        void replaceb(const LinList<T>& );      // replace node behind

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

   private:

        LinList<T>&  list;    	// reference to  list
        DLNode<T>*   b;       	// pointer to node behind
        DLNode<T>*   f;        	// pointer to node ahead

        friend class LinListReverseBrowser<T>;
};

template <class T>
LinListReverseIterator<T>::LinListReverseIterator(LinList<T>& s)   // constructor
: list(s), b(list.rptr), f(b->prev)
{}

template <class T>
LinListReverseIterator<T>& LinListReverseIterator<T>::operator=(int n)// offset initialization
{                                                       // NOT assignment   
	init();
	assert(n>=0);
	while(n--)
	{	assert(ok());
		++(*this);
	}
	return *this;
}
 		
template <class T>
LinListReverseIterator<T>& LinListReverseIterator<T>::operator++()
{
     if( list.isEmpty() ) return *this;
     assert( ok() ); 		// Make sure not already at end.
     b=f;
     f=f->prev;
     return *this;
}

template <class T>
LinListReverseIterator<T>& LinListReverseIterator<T>::operator++(int)  // postfix
{
	assert(0);
	// Use prefix!
	return *this;
}

template <class T>
LinListReverseIterator<T>& LinListReverseIterator<T>::operator--()
{
     if( list.isEmpty() ) return *this;
     assert( b!=list.rptr );		// Make sure not already at beginning.
     f=b;
     b=b->next;
     return *this;
}

template <class T>
LinListReverseIterator<T>& LinListReverseIterator<T>::operator--(int)  // postfix
{
	assert(0);
	// Use prefix!
	return *this;
}

template <class T>
void LinListReverseIterator<T>::insertf(const T& t)
{
	DLNode<T>* node = new DLNode<T>(t);
	node->next=b;
	node->prev=f;
	f=b->prev=f->next=node;
}	

template <class T>
void LinListReverseIterator<T>::insertf(const LinList<T>& L)
{
	LinListReverseBrowser<T> i(L);
	for(i.init(); i.ok(); ++i) insertf(i.ahead());
}

template <class T>
void LinListReverseIterator<T>::insertb(const T& t)
{
	DLNode<T>* node = new DLNode<T>(t);
	node->next=b;
	node->prev=f;
	b=f->next=b->prev=node;
}	

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

template <class T>
void LinListReverseIterator<T>::replacef(const LinList<T>& L)        // replace data in node ahead
{	assert(f!=list.lptr);
	deletef();
	insertf(L);	
}

template <class T>
void LinListReverseIterator<T>::replaceb(const LinList<T>& L)        // replace data in node behind
{	assert(b!=list.rptr);
	deleteb();
	insertb(L);	
}

template <class T>
void LinListReverseIterator<T>::deletef()
{
	assert( ok() );		// Make sure there is an element to delete.
	DLNode<T>* deletee=f;
	f=deletee->prev;
	f->next=b;
	b->prev=f;
	delete deletee;
} 

template <class T>
void LinListReverseIterator<T>::deleteb()
{
	assert( b!=list.rptr );	// Make sure there is an element to delete.
	DLNode<T>* deletee=b;
	b=deletee->next;
	b->prev=f;
	f->next=b;
	delete deletee;
} 


//////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////
// LinListBrowser<T>

template <class T>
class LinListBrowser
{
   public:
	LinListBrowser(const LinList<T>& s); // constructor (binds to list)

	LinListBrowser(const LinListBrowser<T>& i) // copy constructor
	: list(i.list),f(i.f),b(i.b)
	{}

	LinListBrowser(const LinListIterator<T>& i) // copy constructor
	: list(i.list),f(i.f),b(i.b)
	{}

       ~LinListBrowser()                          // destructor
	{}

	LinListBrowser<T>& operator=(const LinListBrowser<T>& i)
	{	assert(0);
		// Don't try to do this!
		i.ahead();	// Just to avoid "i not used" warning.
		return *this;
	}
	
        void init()                             // initializer
	{  b=list.lptr; f=b->next; }

        LinListBrowser<T>& operator=(int n);	// initialize with offset
                                              	// This is NOT assignment!

        int ok() const                          // test for more elements
	{ return(f!=list.rptr); }
        int bok() const                          // test for elements behind
	{ return(b!=list.lptr); }

	LinListBrowser<T>& operator++(); // prefix,  step forward  over one node
        LinListBrowser<T>&  operator++(int);// postfix, step forward  over one node
        LinListBrowser<T>& operator--(); // prefix,  step backward over one node
        LinListBrowser<T>&  operator--(int);// postfix, step backward over one node

        const T& ahead()  const             // const ref to data in node ahead
	{	assert( ok() );
		return f->data;
	}

        const T& behind() const             // const ref to data in node behind
	{	assert( b != list.lptr );
		return b->data;
	}

   private:

        const LinList<T>&  list;    		// reference to  list
        const DLNode<T>* f;        	// pointer to node ahead
        const DLNode<T>*  b;       	// pointer to node behind

};

/********************* diagnostic version
template <class T>
const T& LinListBrowser<T>::ahead()  const             // const ref to data in node ahead
	{
#ifndef SAFETY_CHECKS_OFF
		if (!ok())
		{
cout << "!ok(): " << list << endl; // Why won't this compile if defined in class definition??
T blank;
cout << "Here's the null object of type T: " << blank << endl;
			assert( ok() );
		}
#endif
		return f->data;
	}
**************/

template <class T>
LinListBrowser<T>::LinListBrowser(const LinList<T>& s)   // constructor
: list(s), f(s.lptr->next), b(s.lptr)
{}

template <class T>
LinListBrowser<T>& LinListBrowser<T>::operator=(int n)// offset initialization
{                                                       // NOT assignment   
	init();
	assert(n>=0);
	while(n--)
	{	assert(ok());
		++(*this);
	}
	return *this;
}
 		
template <class T>
LinListBrowser<T>& LinListBrowser<T>::operator++()
{
     if( list.isEmpty() ) return *this;
     assert( ok() ); 		// Make sure not already at end.
     b=f;
     f=f->next;
     return *this;
}

template <class T>
LinListBrowser<T>& LinListBrowser<T>::operator++(int)  // postfix
{
	assert(0);
	// Use prefix!
	return *this;
}

template <class T>
LinListBrowser<T>& LinListBrowser<T>::operator--()
{
     if( list.isEmpty() ) return *this;
     assert( b!=list.lptr );		// Make sure not already at beginning.
     f=b;
     b=b->prev;
     return *this;
}

template <class T>
LinListBrowser<T>& LinListBrowser<T>::operator--(int)  // postfix
{
	assert(0);
	// Use prefix!
	return *this;
}




//////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////
// LinListReverseBrowser<T>

template <class T>
class LinListReverseBrowser
{
   public:
	LinListReverseBrowser(const LinList<T>& s); // constructor (binds to list)

	LinListReverseBrowser(const LinListReverseBrowser<T>& i) // copy constructor
	: list(i.list),f(i.f),b(i.b)
	{}

	LinListReverseBrowser(const LinListReverseIterator<T>& i) // copy constructor
	: list(i.list),f(i.f),b(i.b)
	{}

       ~LinListReverseBrowser()                          // destructor
	{}

	LinListReverseBrowser<T>& operator=(const LinListReverseBrowser<T>& i)
	{	assert(0);
		// Don't try to do this!
		i.ahead();	// Just to avoid "i not used" warning.
		return *this;
	}
	
        void init()                             // initializer
	{  b=list.rptr; f=b->prev; }

        LinListReverseBrowser<T>& operator=(int n);	// initialize with offset
                                              	// This is NOT assignment!

        int ok() const                          // test for more elements
	{ return(f!=list.lptr); }
        int bok() const                          // test for elements behind
	{ return(b!=list.rptr); }

	LinListReverseBrowser<T>& operator++(); // prefix,  step forward  over one node
        LinListReverseBrowser<T>&  operator++(int);// postfix, step forward  over one node
        LinListReverseBrowser<T>& operator--(); // prefix,  step backward over one node
        LinListReverseBrowser<T>&  operator--(int);// postfix, step backward over one node

        const T& ahead()  const             // const ref to data in node ahead
	{	assert( ok() );
		return f->data;
	}
        const T& behind() const             // const ref to data in node behind
	{	assert( b != list.rptr );
		return b->data;
	}

   private:

        const LinList<T>&  list;    		// reference to  list
        const DLNode<T>* b;       	// pointer to node behind
        const DLNode<T>* f;        	// pointer to node ahead

};

template <class T>
LinListReverseBrowser<T>::LinListReverseBrowser(const LinList<T>& s)   // constructor
: list(s), b(list.rptr), f(b->prev)
{}

template <class T>
LinListReverseBrowser<T>& LinListReverseBrowser<T>::operator=(int n)// offset initialization
{                                                       // NOT assignment   
	init();
	assert(n>=0);
	while(n--)
	{	assert(ok());  // failure means subscript out of range
		++(*this);
	}
	return *this;
}
 		
template <class T>
LinListReverseBrowser<T>& LinListReverseBrowser<T>::operator++()
{
     if( list.isEmpty() ) return *this;
     assert( ok() ); 		// Make sure not already at end.
     b=f;
     f=f->prev;
     return *this;
}

template <class T>
LinListReverseBrowser<T>& LinListReverseBrowser<T>::operator++(int)  // postfix
{
	assert(0);
	// Use prefix!
	return *this;
}

template <class T>
LinListReverseBrowser<T>& LinListReverseBrowser<T>::operator--()
{
     if( list.isEmpty() ) return *this;
     assert( f!=list.rptr );  // Make sure not already at beginning.
     f=b;
     b=b->next;
     return *this;
}

template <class T>
LinListReverseBrowser<T>& LinListReverseBrowser<T>::operator--(int)  // postfix
{
 assert(0);
 // Use prefix!
 return *this;
}



















#endif