// list.h -- C++ include file for GWG list classes
// written by Bruce J. Bell on April 13, 1996
//
// update history:
//   April 20: made non-intrusive List<T>, renamed nList to nodeList,
//             major renaming and rearrangement of various things
//   April 22: got rid of nodeList -- finished implementation (still testing)
//             has const iterator dllConstP<T>
//             major renaming and rearrangement

// class summary:
//
//
//   list<T>:  abstract class -- defines required list operations
//   listP<T>: abstract class -- iterator on list<T>
//   constP<T>:abstract class -- const iterator on const list<T>
//
//   List<T>:  abstract class -- non-intrusive list, derived from list<T>
//             adding an object to a List<T> has copy semantics
//   ListP<T>: abstract class -- iterator for nList<T>, derived from listP<T>
//
//   node:    doubly linked node (contains most nontrivial methods)
//   Node<T>: doubly linked node with data, derived from node
//
//   dll<T>:       doubly-linked list, derived from List<T> (uses node)
//   dllP<T>:      iterator for dll<T>, derived from ListP<T>
//   dllConstP<T>: const iterator, for const dll<T>, derived from constP<T>
//
/* debug methods:  for any of the above classes the following may be used
   for inspection of data and integrity checks:

   void Dump(ostream&) const;    // print short data dump of object
   bool Check() const;           // do silent integrity check of data
   bool Verify(ostream&) const;  // do verbose integrity check of data

*/
/* method summary for dll<T>:

               dll<T>()
                 // create empty list
               dll<T>(const list<T> &L)
	         // copy list, by value, from L
       dll<T>& operator=(const list<T> &L)
	         // copy list, by value, from L
	       ~dll<T>()
	         // deletes list elements


           int len() const     // return #of elements
          bool empty() const   // return true if len()==0

            T& index(int i), operator[]  // index list (index starts at 0)
            T& head()  // refer to first element -- L[0]
            T& tail()  // refer to last element -- L[ len()-1 ]

               ins(int i, const T &x)  // insert x at i
               ins_head(const T &x)    // insert x at beginning
               ins_tail(const T &x)    // insert x at end

               del(int i)  // delete element i
               del_head()  // delete element at beginning
               del_tail()  // delete element at end

               get(int i, T &dest)  // delete element i, put its value in dest
               pop_head(T &dest)    // delete head, put its value in dest
               pop_tail(T &dest)    // delete tail, put its value in dest

               clear()  // delete all list elements, leaving empty list

       dllP<T> elemP(int i)  // return iter value to element i
       dllP<T> headP()       // return iter value to head
       dllP<T> tailP()       // return iter value to tail

      dllP<T>* new_iter()              // dynamically allocate iterator
 dllConstP<T>* new_const_iter() const  // dynamically allocate const iterator


   method summary for dllP<T>:

               dllP<T>()
	         // create uninitialized iterator -- most operations illegal
               dllP<T>(const dllP<T> &p)
	         // copy constructor
      dllP<T>& operator=(const dllP<T> &P)
                 // copy value
               ~dllP<T>()
	         // destructor -- nothing terribly special about this

          bool initialized() const  // false iff uninitialized
          bool valid(), operator() const  // true iff it is dereferencable
                 // (e.g., if past end or past beginning)
	  bool at_head() const  // true iff iterator at head of list
          bool at_tail() const  // true iff iterator at tail of list
          bool operator==(const dllP&) const;  // equal iff they point
          bool operator!=(const dllP&) const;  // to the same element

            T& Data(), operator*() const // returns reference to data of elt.
         const T& cData() const    // returns const reference to data of elt.

               go(int i)             // set iterator to element i
               go_head()             // set iterator to head of list
               go_tail()             // set iterator to tail of list
               go(dll<T> &L, int i)  //
               go_head(dll<T> &L)    // as above, but set list, also
               go_tail(dll<T> &L)    //

               ins_fwd(const T &x)   // insert element after iterator
               ins_back(const T &x)  // insert element before iterator

               del_fwd()   // delete element, set iterator to next element
               del_back()  // delete element, set iterator to previous element

               get_fwd(T &x)  // like delete, but save value of deleted element
               get_back(T &x) //

	       // to move iterator, it must be dereferencable (valid())
               // 
               inc()           // move iterator to next element
               dec()           // move iterator to previous element
      dllP<T>& operator++()    // as above, but return new iter
      dllP<T>& operator--()    //
       dllP<T> operator++(int) // as above, but return old iter value
       dllP<T> operator--(int) //

       dll<T>& GetList() const
 const dll<T>& cGetList() const


*/

#ifndef LIST_H
#define LIST_H


#include <assert.h>
#include <iostream.h>



// *****  abstract list classes and their iterators


template<class T>
class list {
  // abstract class -- defines operations required for list

public: // constructors, etc
  virtual ~list()  {}

public: // basic operations
  virtual int len() const =0;  // return length of list
  virtual bool empty() const =0;  // return true iff list is empty (len()==0)

  virtual T& Index(int i)=0;
  const T& cIndex(int i) const
    { return (const_cast<list<T>*>(this))->Index(i); }
  T& operator[](int i) { return Index(i); }
  const T& operator[](int i) const { return cIndex(i); }
    // return reference to i'th list element (elements numbered [0..len()-1])
  virtual void del(int i)=0;
    // delete i'th list element from list
  virtual void ins(int i, const T &E)=0;
    // insert element E at position i (existing elements >=i shift forward 1)

  virtual T& head()=0;
    // (*this)[1]  --  list must not be empty
  virtual T& tail()=0;
    // (*this)[len()]  --  list must not be empty
  virtual void del_head()=0;
    // pop and return head
  virtual void del_tail()=0;
    // pop and return tail
  virtual void ins_head(const T &E)=0;
    // insert at head
  virtual void ins_tail(const T &E)=0;
    // insert at tail

  virtual void clear()=0;

public: // generic allocation
  virtual listP<T>* new_iter()=0;
  virtual constP<T>* new_const_iter() const =0;
    // allocates iterator for this list (initialized to head of list)
	 
public:  // debug methods -- for human-readable debug output
  virtual void Dump(ostream&) const =0;  // dump list in human-readable format
  virtual bool Check() const =0;  // do silent integrity check
  virtual bool Verify(ostream&) const =0;  // do verbose integrity check

}; // end class list<T>


template<class T>
class constP {
  // abstract class -- iterator for const list<T>
  // it lacks operations that may modify the list

public: // ctors, etc
  virtual ~constP() {}

public: // initializers
  virtual void go_head()=0;
  virtual void go_tail()=0;
  virtual void go(int)=0;
    // initialize iterator to location in list

public: // basic operations
  virtual const T& cData() const=0;  // returns const reference to data element

  virtual void inc()=0;  // like ++, but returns nothing, so it can be virtual
  virtual void dec()=0;  // like ++, but returns nothing, so it can be virtual

  virtual bool initialized() const=0;  // true iff *this initialized
    // (i.e., has just been created from default ctor)
  virtual bool valid() const =0;  // true iff iterator can be dereferenced
    // *do not apply* to uninitialized listP (listP from default ctor)
  bool operator()() const  // same as valid(), shorter to type
    { return valid(); }
  virtual bool at_head() const =0;
  virtual bool at_tail() const =0;

public: // debug methods -- for human-readable debug output
  virtual void Dump(ostream&) const =0;
  virtual bool Check() const =0;
  virtual bool Verify(ostream&) const =0;

}; // end class constP<T>


template<class T>
class listP: public constP<T> {
  // abstract class -- iterator for list<T>

public: // constructors, etc
  // nothing left in here...

public: // initializers
  // moved to constP<T>

public: // basic operations
  virtual T& Data() const=0;  // returns reference to data element

  virtual void ins_fwd(const T&)=0;  // insert after this location
  virtual void ins_back(const T&)=0; // insert before this location
  virtual void del_fwd()=0;  // delete list element, point to next location
  virtual void del_back()=0; // delete list element, point to prev location

public: // generic allocation
  virtual list<T>& GetList() const =0;
    // returns reference to list it refers to

}; // end class listP<T>


template<class T>
class List: public list<T> {
  // abstract class -- includes operations required for non-intrusive list
  // (adding an element makes a copy of the original object;
  // list "owns" the objects on it

public: // constructors, etc
  virtual List<T>& operator=(const list<T>&)=0;
    // copies entire list; this would not make sense for an intrusive lise
    // note that it can take any list<T> as its argument...

public: // basic operations
  virtual void get(int i, T &dest)=0;
    // copy i'th element from list to dest, then delete it
  virtual void pop_head(T &dest)=0;  // copy head to dest, then delete it
  virtual void pop_tail(T &dest)=0;  // copy tail to list, then delete it
}; // end class List<T>


template<class T>
class ListP: public listP<T> {
  // abstract class -- iterator for List<T>, includes additional operations

public: // basic operations
  virtual void get_fwd(T&)=0;
    // remove list element, return copy, point to next
  virtual void get_back(T&)=0;
    // remove list element, return copy, point to prev
}; //end class ListP<T>



// node classes

class node {
  // node class for doubly linked list
  // (includes most of the actual algorithms for list operations)

public: // this is entirely encapsulated in dll, so this is OK
  node *next;
  node *prev;

public: // constructors, etc
  node(): next(this),prev(this)  {}
  // no copy ctor, as this would disrupt the ring structure
  // no assignment operator, for the same reason
  ~node()  { unlink(); }

public: // basic ring manipulation functions
  // A.link_foo(B) cuts before or after A and B, then joins corresponding ends
  // (this merges separate rings, or splits a single ring into two
  // A.link_foo(B) is self-inverse
  // A.link_foo(B) is the same as B.link_foo(A)

  void link_next(node &);
    // [A alphalist],[B betalist] <==> [A betalist B alphalist]
    // when linking in a single node B, it is inserted immediately after A
  void link_prev(node &);
    // [A alphalist],[B betalist] <==> [A alphalist B betalist]
    // when linking in a single node B, it is inserted immediately before A

  void unlink();
    // remove *this from its ring (*this becomes a ring of 1)
  bool unlinked() const;
    // return true iff there are no other nodes in this ring (len()==1)
  int len() const;
    // count members of ring, including *this

public: // searching and counting functions
  bool find(node &N) const;
    // return true iff node N is in same ring as *this
  int find_fwd(node &N) const;  // count forward to find node N
    // (-1 if not there; 0 if *this==N)
  int find_back(node &N) const;  // count backward to find node N
    // (-1 if not there; 0 if *this==N)

  node& walk_fwd(int i) const;   // count forward i nodes -- may wrap around
  node& walk_back(int i) const;  // count backward i nodes -- may wrap around
  node& index_fwd(int i) const;  // returns i'th ring element (0 is *this)
    // should *not* wrap around -- does assert() bounds check.  Requires i>=0
  node& index_back(int i) const;
    // like index_fwd, but counts backwards instead of forwards
  node& operator[](int i) const
    { return index_fwd(i); }

public:  // debug methods -- for human-readable debug output
  // (Note: these methods are *not* virtual)
  void Dump(ostream &out) const;
  bool Check() const;
  bool Verify(ostream&) const;  

// friends (classes and functions)
  friend class nodeP;  // node iterator
}; // end class node


template<class T>
struct Node: public node {
  T data;

  Node() {}
  Node(const Node<T> &N): data(N.data) {}
  Node<T>& operator=(const Node<T> &x)
    { data=x.data; return *this; }
  ~Node() {}

  Node(const T &x): data(x) {};

  void Dump(ostream&) const;
  bool Check() const;
  bool Verify(ostream&) const;
};




template<class T>
class dll: public List<T> {
  // nonintrusive node-based list -- deep copy semantics

  node anchor;
  int length;

private: // internal operations
  void delete_ring();  // deletes all list members
  void copy_ring(const list<T> &L);  // copies all members of L
    // (appends to tail of list -- useful for copy or append operations)

  Node<T>* find_index(int i)  // locate node at index i, convert to Node<T>&
    { assert(i>=0); return static_cast<Node<T>*>(&anchor[i+1]); }
  Node<T>* find_head()  // locate head node, convert to Node<T>&
    { assert(!anchor.unlinked()); return static_cast<Node<T>*>(anchor.next); }
  Node<T>* find_tail()  // locate tail node, convert to Node<T>&
    { assert(!anchor.unlinked()); return static_cast<Node<T>*>(anchor.prev); }

  static node* new_node(const T &x)
    { return static_cast<node*>(new Node<T>(x)); }
    // allocate new Node<T> from x, convert to node&
  static void del_node(node *n)  // delete node as Node<T>
    { delete static_cast<Node<T>*>(n); }

public: // constructors, etc
  dll(): length(0) {}  // default ctor for node makes empty list
  dll(const dll<T> &L)  // copy ctor:  copies argument data 
    { copy_ring(L); }
  dll(const list<T> &L)  // general list<T> copier:  copies argument data
    { copy_ring(L); }
  dll<T>& operator=(const list<T> &L)  // deletes old data, copies argument
    { delete_ring(); copy_ring(L); return *this; }
  ~dll()  // deletes list data
    { delete_ring(); }

public: // basic operations
  int len() const
    { return length; }
  bool empty() const
    { return anchor.unlinked(); }
  T& Index(int i)
    { return find_index(i)->data; }
  void del(int i)
    { delete find_index(i); --length; };
  void get(int i, T &dest)
    { Node<T>* tmp= find_index(i); dest=tmp->data; delete tmp; --length; }
  void ins(int i, const T &x)
    { assert(i>=0); anchor[i].link_next( *new_node(x) ); ++length; }

  T& head()
    { return find_head()->data; }
  T& tail()
    { return find_tail()->data; }
  const T& head() const
    { return const_cast<dll<T>*>(this)->find_head()->data; }
  const T& tail() const
    { return const_cast<dll<T>*>(this)->find_tail()->data; }
  void del_head()
    { delete find_head(); --length; }
  void del_tail()
    { delete find_tail(); --length; }
  void pop_head(T &dest)
    { Node<T>* tmp= find_head(); dest=tmp->data; delete tmp; --length; }
  void pop_tail(T &dest)
    { Node<T>* tmp= find_tail(); dest=tmp->data; delete tmp; --length; }
  void ins_head(const T &x)
    { anchor.link_next( *new_node(x) ); ++length; }
  void ins_tail(const T &x)
    { anchor.link_prev( *new_node(x) ); ++length; }

  void clear()  // delete all list members, leaving an empty list
    { delete_ring(); }

public: // generic allocation
  dllP<T> headP()  // return iter *value* to head (must have head)
    { assert(!empty()); return dllP<T>(this, anchor.next); }
  dllP<T> tailP()  // return iter *value* to tail (must have tail)
    { assert(!empty()); return dllP<T>(this, anchor.prev); }
  dllP<T> elemP(int i)  // return iter *value* to indexed element (must exist)
    { assert(i>=0); return dllP<T>(this, &anchor[i+1]); }
  dllConstP<T> headP() const
    { assert(!empty()); return dllConstP<T>(this, anchor.next); }
  dllConstP<T> tailP() const
    { assert(!empty()); return dllConstP<T>(this, anchor.prev); }
  dllConstP<T> elemP(int i) const
    { assert(i>=0); return dllConstP<T>(this, &anchor[i+1]); }


  dllP<T>* new_iter()  // return pointer to dynamically allocated iter
    { return new dllP<T>(*this); }
  dllConstP<T>* new_const_iter() const  // same as new_iter(), but const_iter
    { return new dllConstP<T>(*this); }

public: // debug methods
  void Dump(ostream&) const;
  bool Check() const;
  bool Verify(ostream&) const;

// friends (classes and functions)
  friend class dllConstP<T>;
  friend class dllP<T>;
}; // end class dll<T>


template<class T>
class dllP: public ListP<T> {
  // iterator for dll<T>

  dll<T> *Lp;  // refers to list iterated over
  node *Np;  // refers to node iterator points to

private: // internal operations:
  Node<T>& deref() const // do checking and type conversion to Node<T>&
    { assert( valid() ); return *static_cast<Node<T>*>(Np); }

private: // internal constructors
  dllP(dll<T> *lp, node *np): Lp(lp), Np(np) {}

public: // constructors, etc
  dllP(): Lp(0) {}
  dllP(const dllP<T> &p): Lp(p.Lp), Np(p.Np) {}
  dllP<T>& operator=(const dllP<T> &P)
    { Lp=P.Lp; Np=P.Np; return *this; }
  ~dllP() {}

  dllP(dll<T> &L): Lp(&L), Np(L.anchor.next) {}

public: // initializers
  void go_head()
    { assert(initialized); Np= Lp->anchor.next; }
  void go_tail()
    { assert(initialized); Np= Lp->anchor.prev; }
  void go(int i)
    { assert(initialized); assert(i>=0); Np= &Lp->anchor[i+1]; }
  void go_head(dll<T> &L)
    { Lp= &L; Np= L.anchor.next; }
  void go_tail(dll<T> &L)
    { Lp= &L; Np= L.anchor.prev; }
  void go(dll<T> &L, int i)
    { assert(i>=0); Lp= &L; Np= &L.anchor[i+1]; }

public: // basic operations
  T& Data() const // returns reference to data
    { return deref().data; }
  const T& cData() const  // returns const reference to data element
    { return deref().data; }
  T& operator*() const // same as Data()
    { return deref().data; }

  void ins_fwd(const T &x)
    { assert(valid()); Np->link_next(*dll<T>::new_node(x)); ++Lp->length; }
  void ins_back(const T &x)
    { assert(valid()); Np->link_prev(*dll<T>::new_node(x)); ++Lp->length; }
  void del_fwd() {
    assert(valid());
    node *tmp=Np; Np=Np->next;
    dll<T>::del_node(tmp); --Lp->length;
  }
  void del_back() {
    assert(valid());
    node *tmp=Np; Np=Np->prev;
    dll<T>::del_node(tmp); --Lp->length;
  }
  void get_fwd(T &x) {
    x=deref().data;
    node *tmp=Np; Np=Np->next;
    dll<T>::del_node(tmp); --Lp->length;
  }
  void get_back(T &x) {
    x=deref().data;
    node *tmp=Np; Np=Np->prev;
    dll<T>::del_node(tmp); --Lp->length;
  }

  void inc()
    { assert(valid()); Np=Np->next; }
  void dec()
    { assert(valid()); Np=Np->prev; }
  dllP<T>& operator++()
    { inc(); return *this; }
  dllP<T> operator++(int)
    { dllP<T> tmp(*this); inc(); return tmp; }
  dllP<T>& operator--()
    { dec(); return *this; }
  dllP<T> operator--(int)
    { dllP<T> tmp(*this); dec(); return tmp; }
  
  bool operator==(const dllP<T> &P) const {
    assert(Lp==P.Lp); assert(initialized()&&P.initialized());
    return Np==P.Np;
  }
  bool operator!=(const dllP<T> &P) const
    { return !((*this)==P); }
  bool operator==(const dllConstP<T> &P) const {
    assert(Lp==P.Lp); assert(initialized()&&P.initialized());
    return Np==P.Np;
  }
  bool operator!=(const dllConstP<T> &P) const
    { return !((*this)==P); }

  bool initialized() const
    { return Lp!=0; }
  bool valid() const
    { assert(initialized()); return Np != &Lp->anchor; }
  bool at_head() const
    { assert(initialized()); return Np== Lp->anchor.next; }
  bool at_tail() const
    { assert(initialized()); return Np== Lp->anchor.prev; }

public: // generic allocation
  dll<T>& GetList() const
    { assert(initialized()); return *Lp; }
  const dll<T>& cGetList() const
    { assert(initialized()); return *Lp; }

public: // debug methods
  void Dump(ostream&) const;
  bool Check() const;
  bool Verify(ostream&) const;

// friends
  friend class dll<T>;
  friend class dllConstP<T>;
}; // end class dllP<T>


template<class T>
class dllConstP: public constP<T> {
  // iterator for const dll<T>

  const dll<T> *Lp;  // refers to list iterated over
  const node *Np;  // refers to node iterator points to

private: // internal operations:
  const Node<T>& deref() const // do checking and type conversion to Node<T>&
    { assert( valid() ); return *static_cast<const Node<T>*>(Np); }

private: // internal constructors
  dllConstP(const dll<T> *lp, const node *np): Lp(lp), Np(np) {}
  // assumes *Lp valid, *Np in *Lp

public: // constructors, etc
  dllConstP(): Lp(0) {}
  dllConstP(const dllConstP<T> &p): Lp(p.Lp), Np(p.Np) {}
  dllConstP(const dllP<T> &p): Lp(p.Lp), Np(p.Np) {}
  dllConstP<T>& operator=(const dllConstP<T> &P)
    { Lp=P.Lp; Np=P.Np; return *this; }
  dllConstP<T>& operator=(const dllP<T> &P)
    { Lp=P.Lp; Np=P.Np; return *this; }
  ~dllConstP() {}

  dllConstP(const dll<T> &L): Lp(&L), Np(L.anchor.next) {}

public: // initializers
  void go_head()
    { Np= Lp->anchor.next; }
  void go_tail()
    { Np= Lp->anchor.prev; }
  void go(int i)
    { assert(i>=0); Np= &Lp->anchor[i+1]; }
  void go_head(const dll<T> &L)
    { Lp= &L; Np= L.anchor.next; }
  void go_tail(const dll<T> &L)
    { Lp= &L; Np= L.anchor.prev; }
  void go(const dll<T> &L, int i)
    { assert(i>=0); Lp= &L; Np= &L.anchor[i+1]; }

public: // basic operations
  const T& cData() const  // returns const reference to data element
    { return deref().data; }
  const T& operator*() // same as cdata()
    { return deref().data; }

  void inc()
    { assert(valid()); Np=Np->next; }
  void dec()
    { assert(valid()); Np=Np->prev; }
  dllConstP<T>& operator++()
    { inc(); return *this; }
  dllConstP<T> operator++(int)
    { dllConstP<T> tmp(*this); inc(); return tmp; }
  dllConstP<T>& operator--()
    { dec(); return *this; }
  dllConstP<T> operator--(int)
    { dllConstP<T> tmp(*this); dec(); return tmp; }
  
  bool initialized() const
    { return Lp!=0; }
  bool valid() const
    { assert(initialized()); return Np != &Lp->anchor; }
  bool at_head() const
    { assert(initialized()); return Np== Lp->anchor.next; }
  bool at_tail() const
    { assert(initialized()); return Np== Lp->anchor.prev; }

  bool operator==(const dllP<T> &P) const {
    assert(Lp==P.Lp); assert(initialized()&&P.initialized());
    return Np==P.Np;
  }
  bool operator!=(const dllP<T> &P) const
    { return !((*this)==P); }
  bool operator==(const dllConstP<T> &P) const {
    assert(Lp==P.Lp); assert(initialized()&&P.initialized());
    return Np==P.Np;
  }
  bool operator!=(const dllConstP<T> &P) const
    { return !((*this)==P); }



public: // generic allocation
  const dll<T>& cGetList()
    { assert(initialized()); return *Lp; }

public: // debug methods
  void Dump(ostream&) const;
  bool Check() const;
  bool Verify(ostream&) const;

// friends
  friend class dll<T>;
  friend class dllP<T>;
}; // end class dllConstP





// dll methods:

template<class T>
void dll<T>::delete_ring() {
  while(!anchor.unlinked())
    del_node( anchor.next );
  length= 0;
}

template<class T>
void dll<T>::copy_ring(const list<T> &L) {
  // copies elements of L to end of *this list

  constP<T> *pp= L.new_const_iter();  // pp is pointer to iterator
  for(; (*pp).valid(); (*pp).inc()) {
    ins_tail((*pp).cData()); // second * gives reference to list<T> element
  }
  delete pp;
}

template<class T>
void dll<T>::Dump(ostream &out) const {
  out<<"(dll<T>: anchor=";
  anchor.Dump(out);
  out<<" length="<<length<<")";
}

template<class T>
bool dll<T>::Check() const {
  return anchor.Check() && length+1==anchor.len();
}

template<class T>
bool dll<T>::Verify(ostream &out) const {
  out<<"(verify dll<T>:\n";
  Dump(out); out<<"\n\n";

  out<<"verifying anchor: ";
  if(!anchor.Verify(out))
    return false;
  cout<<" anchor OK\n\n";

  out<<"verifying length: "<<length;
  int x=anchor.len();
  if( x!=length+1 ) {
    cout<<" error: ring count "<<x<<" must == length+1\n";
    return false;
  }
  cout<<" length OK\n\n";

  cout<<"verified dll<T> OK)\n\n";
  return true;
}



// dllP methods
template<class T>
void dllP<T>::Dump(ostream &out) const {
  out<<"(dllP<T>: Lp="<<Lp<<"->";
  Lp->Dump(out);
  out<<" Np="<<Np<<"->";
  Np->Dump(out);
  out<<")";
}

template<class T>
bool dllP<T>::Check() const {
  return initialized() && Lp->anchor.Check() && Lp->anchor.find(*Np);
}

template<class T>
bool dllP<T>::Verify(ostream &out) const {
  out<<"(verify dllP<T>:\n";
  if(!initialized()) {
    cout<<" error: dllP<T> not initialized\n";
    return false;
  }
  Dump(out); out<<"\n";

  out<<"verifying *Lp: ";
  if(!Lp->Verify(out))
    return false;
  cout<<"*Lp OK\n\n";

  out<<"verifying *Np: ";
  if( !Lp->anchor.find(*Np) ) {
    cout<<" error: Np doesn't point to list *Lp\n";
    return false;
  }
  if( !valid() )
    cout<<" (note: *Np==Lp->anchor, indicating past beginning or end)\n";
  else
    cout<<" points to element "<<Lp->anchor.find_fwd(*Np)-1<<"\n";
  cout<<"verified dllP<T> OK)\n";

  return true;
}


// dllConstP methods
template<class T>
void dllConstP<T>::Dump(ostream &out) const {
  out<<"(dllConstP<T>: Lp="<<Lp<<"->";
  Lp->Dump(out);
  out<<" Np="<<Np<<"->";
  Np->Dump(out);
  out<<")";
}

template<class T>
bool dllConstP<T>::Check() const {
  return initialized() && Lp->anchor.Check() && Lp->anchor.find(*(node*)Np);
}


template<class T>
bool dllConstP<T>::Verify(ostream &out) const {
  out<<"(verify dllConstP<T>:\n";
  if(!initialized()) {
    cout<<" error: dllConstP<T> not initialized\n";
    return false;
  }
  Dump(out); out<<"\n";

  out<<"verifying *Lp: ";
  if(!Lp->Verify(out))
    return false;
  cout<<"*Lp OK\n\n";

  out<<"verifying *Np: ";
  if( !Lp->anchor.find(*(node*)Np) ) {
    cout<<" error: Np doesn't point to list *Lp\n";
    return false;
  }
  if( !valid() )
    cout<<" (note: *Np==Lp->anchor, indicating past beginning or end)\n";
  else
    cout<<" points to element "<<Lp->anchor.find_fwd(*(node*)Np)-1<<"\n";
  cout<<"verified dllConstP<T> OK)\n";

  return true;
}


 


#endif // LIST_H