// IndexedLinList.H
// This is a list of T's indexed by I's.
// Functionally the same as LinList.

// JR 12/28/95  Adaptation of LinList.
//		Compiled.
//	 	Tested all the IndexedLinList members.
//		Still have to test the iterators and browsers.


// Precursor LinList's history:
// 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().
 
#ifndef INDEXEDLINLIST_H
#define INDEXEDLINLIST_H

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

template <class I, class T>
class IndexedLinList;
template <class I, class T>
class IndexedLinListIterator;
template <class I, class T>
class IndexedLinListBrowser;
template <class I, class T>
class IndexedLinListReverseIterator;
template <class I, class T>
class IndexedLinListReverseBrowser;


template <class I, class T>
class IDLNode            // 9/23/95:
                        // Tried to nest this within CircList<T>,
                        // but SGI compiler appears not to permit 
                        // nested classes in templates.
{
   private:
      IDLNode<I,T>* next;
      IDLNode<I,T>* prev;
      I indx;
      T data;

      IDLNode()
      {}
      IDLNode(const I&i,const T& s)
         : indx(i),data(s)
      {}
     ~IDLNode()
      {}

      friend class IndexedLinList<I,T>;
      friend class IndexedLinListBrowser<I,T>;
      friend class IndexedLinListIterator<I,T>;
      friend class IndexedLinListReverseBrowser<I,T>;
      friend class IndexedLinListReverseIterator<I,T>;
};

template <class I, class T>
class IndexedLinList
{
   private:
	IDLNode<I,T>* lptr; // ptr to dummy node sitting before first element
	IDLNode<I,T>* rptr; // ptr to dummy node sitting after   last element

   public:
	IndexedLinList();					// construct empty list
	IndexedLinList(const I& i,const T& t);                           	// construct from T
 	IndexedLinList(const IndexedLinList<I,T>& L);			// copy constructor	
       ~IndexedLinList();					// destructor
	IndexedLinList<I,T>& clear();				// delete all elements
	IndexedLinList<I,T>& operator=(const IndexedLinList<I,T>& L);    	// assignment

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

	Boolean operator==(const IndexedLinList<I,T>& L) const;
	Boolean operator!=(const IndexedLinList<I,T>& L) const;
	
	IndexedLinList<I,T>& prepend(const I& i,const T& t);
	IndexedLinList<I,T>& prepend(const IndexedLinList<I,T>& L);
	IndexedLinList<I,T>& append(const I& i,const T& t);
	IndexedLinList<I,T>& append(const IndexedLinList<I,T>& L);

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

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

	IndexedLinList<I,T> commonLeadingSublist( const IndexedLinList<I,T>& other ) const;

//2002_12_27	friend ostream& operator << <> (ostream& out, const IndexedLinList<I,T>& s);
	friend class IndexedLinListBrowser<I,T>;
	friend class IndexedLinListReverseBrowser<I,T>;
	friend class IndexedLinListIterator<I,T>;
	friend class IndexedLinListReverseIterator<I,T>;
};


template <class I, class T>
IndexedLinList<I,T>::IndexedLinList()
{	
	lptr = new IDLNode<I,T>;
	rptr = new IDLNode<I,T>;
	lptr->next=rptr;
	rptr->prev=lptr;
}

template <class I, class T>
IndexedLinList<I,T>::IndexedLinList(const I& i,const T& t)
{	
	lptr = new IDLNode<I,T>;
	rptr = new IDLNode<I,T>;
	lptr->next=rptr;
	rptr->prev=lptr;
	prepend(i,t);
}


template <class I, class T>
IndexedLinList<I,T>::IndexedLinList(const IndexedLinList<I,T>& L)
{	
	lptr = new IDLNode<I,T>;
	rptr = new IDLNode<I,T>;
	lptr->next=rptr;
	rptr->prev=lptr;
	prepend(L);
}


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

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

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

	
template <class I, class T>
int IndexedLinList<I,T>::length() const
{
	IndexedLinListBrowser<I,T> i(*this);
	int len=0;
	for(i.init();i.ok();++i) len++;
	return len;
}

template <class I, class T>
Boolean IndexedLinList<I,T>::operator==(const IndexedLinList<I,T>& L) const
{
	if( &L==this ) return 1;
	IndexedLinListBrowser<I,T> i1(*this);
	IndexedLinListBrowser<I,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 I, class T>
Boolean IndexedLinList<I,T>::operator!=(const IndexedLinList<I,T>& L) const
{
	return !((*this)==L);
}

template <class I, class T>
IndexedLinList<I,T>& IndexedLinList<I,T>::prepend(const I& i,const T& t)
{
	IDLNode<I,T>* node = new IDLNode<I,T>(i,t);
	node->next=lptr->next;
	node->prev=lptr;
	lptr->next=node->next->prev=node;
	return *this;
}

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

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

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

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

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

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

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

template <class I, class T>
const T& IndexedLinList<I,T>::operator[](const I& k) const
{
	IndexedLinListBrowser<I,T> i(*this);
	for(i.init();i.ok();++i)
	   if(i.iahead()==k) return i.ahead();
	assert(0);
}

template <class I, class T>
T& IndexedLinList<I,T>::operator[](const I& k)
{
	IndexedLinListIterator<I,T> i(*this);
	for(i.init();i.ok();++i)
	   if(i.iahead()==k) return i.ahead();
	assert(0);
}



template <class I, class T>
IndexedLinList<I,T> IndexedLinList<I,T>::commonLeadingSublist( const IndexedLinList<I,T>& other ) const
{
        IndexedLinListBrowser<I,T> i1(*this);
        IndexedLinListBrowser<I,T> i2(other);

        IndexedLinList<I,T> tmp;

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

        return tmp;
}

template <class I, class T>
ostream& operator<<(ostream& out,const IndexedLinList<I,T>& L)
{
	IndexedLinListBrowser<I,T> i(L);
 	out << "( ";
	for(i.init();i.ok();++i) 
		out << "[" << i.iahead() << "]" << i.ahead() << " ";
	out << ")";
	return out;
}



//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
// IndexedLinListIterator<I,T>

template <class I, class T>
class IndexedLinListIterator
{
   public:
	IndexedLinListIterator(IndexedLinList<I,T>& s);         // constructor (binds to list)

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

       ~IndexedLinListIterator()                          // destructor
	{}

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

        IndexedLinListIterator<I,T>& operator=(const I& 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); }

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

        I& iahead()             // ref to index in node ahead
	{	assert( ok() );
		return f->indx;
	}
        I& ibehind()             // ref to index in node behind
	{	assert( b != list.lptr );
		return b->indx;
	}

        const I& iahead() const           // const ref to index in node ahead
	{	assert( ok() );
		return f->indx;
	}
        const I& ibehind() const          // const ref to index in node behind
	{	assert( b != list.lptr );
		return b->indx;
	}

        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 I& k,const T& t);               // insert new node ahead
        void insertf(const IndexedLinList<I,T>& );       // insert list ahead

        void insertb(const I& k,const T& t);               // insert new node behind
        void insertb(const IndexedLinList<I,T>& );       // insert list behind

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

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

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

   private:

        IndexedLinList<I,T>&  list;    	// reference to  list
        IDLNode<I,T>*   f;        	// pointer to node ahead
        IDLNode<I,T>*   b;       	// pointer to node behind

        friend class IndexedLinListBrowser<I,T>;
};

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

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

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

template <class I, class T>
IndexedLinListIterator<I,T>& IndexedLinListIterator<I,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 I, class T>
IndexedLinListIterator<I,T>& IndexedLinListIterator<I,T>::operator--(int)  // postfix
{
	assert(0);
	// Use prefix!
	return *this;
}

template <class I, class T>
void IndexedLinListIterator<I,T>::insertf(const I& k,const T& t)
{
	IDLNode<I,T>* node = new IDLNode<I,T>(k,t);
	node->next=f;
	node->prev=b;
	f=b->next=f->prev=node;
}	

template <class I, class T>
void IndexedLinListIterator<I,T>::insertf(const IndexedLinList<I,T>& L)
{
	IndexedLinListReverseBrowser<I,T> i(L);
	for(i.init(); i.ok(); ++i) insertf(i.iahead(),i.ahead());
}

template <class I, class T>
void IndexedLinListIterator<I,T>::insertb(const I& k,const T& t)
{
	IDLNode<I,T>* node = new IDLNode<I,T>(k,t);
	node->next=f;
	node->prev=b;
	b=f->prev=b->next=node;
}	

template <class I, class T>
void IndexedLinListIterator<I,T>::insertb(const IndexedLinList<I,T>& L)
{
	IndexedLinListBrowser<I,T> i(L);
	for(i.init(); i.ok(); ++i) insertb(i.iahead(),i.ahead());
}

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

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

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

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

//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
// IndexedLinListReverseIterator<I,T>

template <class I, class T>
class IndexedLinListReverseIterator
{
   public:
	IndexedLinListReverseIterator(IndexedLinList<I,T>& s);         // constructor (binds to list)

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

       ~IndexedLinListReverseIterator()                          // destructor
	{}

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

        IndexedLinListReverseIterator<I,T>& operator=(const I& 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); }

	IndexedLinListReverseIterator<I,T>& operator++();   // prefix,  step forward  over one node
        IndexedLinListReverseIterator<I,T>& operator++(int);// postfix, step forward  over one node
        IndexedLinListReverseIterator<I,T>& operator--();   // prefix,  step backward over one node
        IndexedLinListReverseIterator<I,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;
	}

        const I& iahead()  const             // const ref to index in node ahead
	{	assert( ok() );
		return f->indx;
	}
        const I& ibehind() const             // const ref to index in node behind
	{	assert( b != list.rptr );
		return b->indx;
	}

        void insertf(const I& k,const T& t);               // insert new node ahead
        void insertf(const IndexedLinList<I,T>& );       // insert list ahead

        void insertb(const I& k,const T& t);               // insert new node behind
        void insertb(const IndexedLinList<I,T>& );       // insert list behind

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

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

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

   private:

        IndexedLinList<I,T>&  list;    	// reference to  list
        IDLNode<I,T>*   b;       	// pointer to node behind
        IDLNode<I,T>*   f;        	// pointer to node ahead

        friend class IndexedLinListReverseBrowser<I,T>;
};

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

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

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

template <class I, class T>
IndexedLinListReverseIterator<I,T>& IndexedLinListReverseIterator<I,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 I, class T>
IndexedLinListReverseIterator<I,T>& IndexedLinListReverseIterator<I,T>::operator--(int)  // postfix
{
	assert(0);
	// Use prefix!
	return *this;
}

template <class I, class T>
void IndexedLinListReverseIterator<I,T>::insertf(const I& k,const T& t)
{
	IDLNode<I,T>* node = new IDLNode<I,T>(k,t);
	node->next=b;
	node->prev=f;
	f=b->prev=f->next=node;
}	

template <class I, class T>
void IndexedLinListReverseIterator<I,T>::insertf(const IndexedLinList<I,T>& L)
{
	IndexedLinListReverseBrowser<I,T> i(L);
	for(i.init(); i.ok(); ++i) insertf(i.iahead(),i.ahead());
}

template <class I, class T>
void IndexedLinListReverseIterator<I,T>::insertb(const I& k,const T& t)
{
	IDLNode<I,T>* node = new IDLNode<I,T>(k,t);
	node->next=b;
	node->prev=f;
	b=f->next=b->prev=node;
}	

template <class I, class T>
void IndexedLinListReverseIterator<I,T>::insertb(const IndexedLinList<I,T>& L)
{
	IndexedLinListBrowser<I,T> i(L);
	for(i.init(); i.ok(); ++i) insertb(i.iahead(),i.ahead());
}

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

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

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

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


//////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////
// IndexedLinListBrowser<I,T>

template <class I, class T>
class IndexedLinListBrowser
{
   public:
	IndexedLinListBrowser(const IndexedLinList<I,T>& s); // constructor (binds to list)

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

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

       ~IndexedLinListBrowser()                          // destructor
	{}

	IndexedLinListBrowser<I,T>& operator=(const IndexedLinListBrowser<I,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; }

        IndexedLinListBrowser<I,T>& operator=(const I& 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); }

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

        const I& iahead()  const             // const ref to index in node ahead
	{	assert( ok() );
		return f->indx;
	}
        const I& ibehind() const             // const ref to index in node behind
	{	assert( b != list.lptr );
		return b->indx;
	}

        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 IndexedLinList<I,T>&  list;    		// reference to  list
        const IDLNode<I,T>* f;        	// pointer to node ahead
        const IDLNode<I,T>*  b;       	// pointer to node behind

};

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

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

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

template <class I, class T>
IndexedLinListBrowser<I,T>& IndexedLinListBrowser<I,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 I, class T>
IndexedLinListBrowser<I,T>& IndexedLinListBrowser<I,T>::operator--(int)  // postfix
{
	assert(0);
	// Use prefix!
	return *this;
}




//////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////
// IndexedLinListReverseBrowser<I,T>

template <class I, class T>
class IndexedLinListReverseBrowser
{
   public:
	IndexedLinListReverseBrowser(const IndexedLinList<I,T>& s); // constructor (binds to list)

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

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

       ~IndexedLinListReverseBrowser()                          // destructor
	{}

	IndexedLinListReverseBrowser<I,T>& operator=(const IndexedLinListReverseBrowser<I,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; }

        IndexedLinListReverseBrowser<I,T>& operator=(const I& 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); }

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

        const I& iahead()  const             // const ref to index in node ahead
	{	assert( ok() );
		return f->indx;
	}
        const I& ibehind() const             // const ref to index in node behind
	{	assert( b != list.rptr );
		return b->indx;
	}

        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 IndexedLinList<I,T>&  list;    		// reference to  list
        const IDLNode<I,T>* b;       	// pointer to node behind
        const IDLNode<I,T>* f;        	// pointer to node ahead

};

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

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

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

template <class I, class T>
IndexedLinListReverseBrowser<I,T>& IndexedLinListReverseBrowser<I,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 I, class T>
IndexedLinListReverseBrowser<I,T>& IndexedLinListReverseBrowser<I,T>::operator--(int)  // postfix
{
	assert(0);
	// Use prefix!
	return *this;
}



















#endif