list.hh

    
#ifndef ALREADY_INCLUDED_LIST_HH
#define ALREADY_INCLUDED_LIST_HH

#include "../noio/io.hh" /* for ASSERT, assert, cout, cerr */

                                      // ITERATOR MACROS:

#define for_list(X,cursor,mylist) for (Node<X>* cursor=(mylist)->get_first(); cursor != null; cursor=cursor->get_next())
#define for_list_const(X,cursor,mylist) for (const Node<X>* cursor=(mylist)->get_first_const(); cursor != null; cursor=cursor->get_next_const())
#define for_list_backwards(X,cursor,mylist) for (Node<X>* cursor=(mylist)->get_last(); cursor != null; cursor=cursor->get_previous())
#define for_list_backwards_const(X,cursor,mylist) for (const Node<X>* cursor=(mylist)->get_last_const(); cursor != null; cursor=cursor->get_previous_const())

                                      // LIST CLASS:

template<class X>
class Node;

template<class X>
class List
{
   friend class Node<X>;
private:
   ///
   /// Member variable private_first is first so it has zero
   /// offset.  This allows an optimisation to be made.
   /// -----------------------------------------------------
   /// Member variables are set in this order, which allows
   /// an optimisation to be made.
   ///
   Node<X>* private_first;
   Node<X>* private_last;
   int      private_length;
   bool     private_dirty;

                                   // DISALLOW PASSING AND RETURNING BY VALUE:

   /// DISALLOWED: copying of lists, since it is inefficient.
   /// This prevents (among other things) passing of lists by
   /// value and returning them by value.
   ///
private:
   List(const List&);
   List& operator = (const List&);

                                   // CONSTRUCTORS AND DESTUCTORS:

public:
   List()
   {
      private_first  = null;
      private_last   = null;
      private_length = 0;
      private_dirty  = false;
   }

   ///
   /// Deletes the Nodes of linked list in O(n) time.  The
   /// result is an empty list.
   ///
   void delete_shallow()
   {
      if (this == null) {
         return;
      }

      ///
      /// Yehar -O3 optimisation determines that the following
      /// assertion will never fail, therefore it can be safetly
      /// commented out...
      ///
      assert(this != null);

Node<X>* n_next;
      for (Node<X>* n = private_first; n != null; n=n_next) {
         n_next = n->private_next;
         delete n;
      }

/* ADJUST LENGTH: */
      private_length = 0;
      ///
      /// NOT NEEDED: since done internally by delete n
      ///
      /// private_first = null;
      /// private_last  = null;

      /* MUTATOR ANNOUNCMENT: */
      private_dirty = true;

      //cout << "*** END delete_shallow\n";
   }

   /// Deletes the Nodes and Xs of a linked list in O(n)
   /// time.  The result is an empty list.
   ///
   void delete_deep()
   {
      if (this == null) {
         return;
      }

assert(this != null);

Node<X>* n_next;
      for (Node<X>* n = private_first; n != null; n=n_next) {
         n_next = n->private_next;
         delete n->private_data;
         delete n;
      }

/* ADJUST LENGTH: */
      private_length = 0;

      ///
      /// NOT NEEDED: since done internally by delete n
      /// private_first = null;
      /// private_last  = null;

      /* MUTATOR ANNOUNCMENT: */
      private_dirty = true;
   }

   ///
   /// LIST DESTRUCTOR: Internally calls delete_shallow.  The result is
   /// an empty list.  Destructor is virtual in case someone inherits
   /// from this class.
   ///
   virtual ~List()
   {
      delete_shallow();
   }

                                   // LIST GETTERS: Take O(1) time.

   Node<X>* get_first()
   {
      ASSERT(this != null);
      private_dirty = true;
      return private_first;
   }
   Node<X>* get_last()
   {
      ASSERT(this != null);
      private_dirty = true;
      return private_last;
   }
   const Node<X>* get_first_const() const
   {
      ASSERT(this != null);
      return private_first;
   }
   const Node<X>* get_last_const() const
   {
      ASSERT(this != null);
      return private_last;
   }
   ///
   /// Returns the length of the list
   ///
   int get_length() const
   {
      ASSERT(this != null);
      return private_length;
   }

                                   // DIRTY METHODS: Take O(1) time.

   ///
   /// Returns the private_dirty property
   ///
   bool get_dirty() const
   {
      ASSERT(this != null);
      return private_dirty;
   }
   ///
   /// Clears the private_dirty property
   ///
   void clear_dirty()
   {
      ASSERT(this != null);
      private_dirty = false;
   }

                                   // LIST ADDERS: Take O(1) time.

   ///
   /// Adds a node onto the start of the list
   ///
   void add_to_start(X* x)
   {
      // NOTE: x could be null.
      ASSERT(this != null);

Node<X>* n = new Node<X>();

n->private_data     = x;
      n->private_next     = private_first;
      n->private_previous = null;
      n->private_owner    = this;

/* SYNC ADJACENTS: */
      if (private_first != null) {
         private_first->private_previous = n;
      }

/* SYNC FIRST AND LAST POINTERS: */
      private_first = n;
      if (private_last == null) {
         private_last = n;
      }

/* ADJUST LENGTH: */
      private_length++;

/* MUTATOR ANNOUNCMENT: */
      private_dirty = true;

}

   ///
   /// Adds a node onto the end of the list.
   ///
   void add_to_end(X* x)
   {
      // NOTE: x could be null.
      ASSERT(this != null);

Node<X>* n = new Node<X>();

n->private_data     = x;
      n->private_next     = null;
      n->private_previous = private_last;
      n->private_owner    = this;

/* SYNC ADJACENTS: */
      if (private_last != null) {
         private_last->private_next = n;
      }

/* SYNC FIRST AND LAST POINTERS: */
      if (private_first == null) {
         private_first = n;
      }
      private_last = n;

/* ADJUST LENGTH: */
      private_length++;

/* MUTATOR ANNOUNCMENT: */
      private_dirty = true;
   }

                                   // REVERSE: Takes O(n) time.

   ///
   /// Reverse reverses the list's order.
   ///
   void reverse()
   {
      ASSERT(this != null);

/* SWAP NEXT AND PREVIOUS POINTERS: */
      Node<X>* n_next = null;
      for (Node<X>* n = private_first; n != null; n=n_next) {
         n_next = n->get_next();
         Node<X>* tmp = n->private_previous;
         n->private_previous = n->private_next;
         n->private_next = tmp;
      }

/* SWAP FIRST AND LAST POINTERS: */
      Node<X>* tmp = private_first;
      private_first = private_last;
      private_last  = tmp;

/* MUTATOR ANNOUNCMENT: */
      private_dirty = true;
   }

                                   // NON ESSENTIAL ADDERS:

   ///
   /// Adds argument "list" onto the current list
   ///
   void add_list(List<X>* mylist)
   {
      ASSERT(this != null);
      ASSERT(mylist != null);

for_list (X,n,mylist) {
         add_to_end(n);
      }
   }
   ///
   /// Alias for add_to_end
   ///
   void add_element(X* x)
   {
      // NOTE: x could be null.
      ASSERT(this != null);
      add_to_end(x);
   }
   ///
   /// Eliminates get_data in client code.
   ///
   void add_element(Node<X>* node)
   {
      ASSERT(this != null);
      ASSERT(node != null);
      add_to_end(node->get_data());
   }
   ///
   /// Eliminates get_data in client code
   ///
   void add_to_start(Node<X>* node)
   {
      ASSERT(this != null);
      ASSERT(node != null);
      add_to_start(node->get_data());
   }
   ///
   /// Eliminates get_data in client code
   ///
   void add_to_end(Node<X>* node)
   {
      ASSERT(this != null);
      ASSERT(node != null);
      add_to_end(node->get_data());
   }
};

                                      // NODE CLASS:

template<class X>
class Node
{
   friend class List<X>;

private:

   ///
   /// Member variables are set in this order, which allows an
   /// optimisation to be made.
   ///
   /// Member variable private_data is first so it has zero offset.
   /// This allows an optimisation to be made.
   ///
   X*            private_data;
   Node*         private_next;
   Node*         private_previous;
   List<X>*      private_owner;

                                   // DISALLOW PASSING AND RETURNING BY VALUE:

private:
   ///
   /// DISALLOWED: copying of nodes.  This prevents (among other
   /// things) passing of nodes by value and returning them by value.
   ///
   Node& operator = (const Node&);
   Node(const Node&);

                                   // CONSTRUCTORS AND DESTUCTORS:

   ///
   /// NODE CONSTRUCTOR IS private: The only way a node can be created
   /// is via a call to one of the following methods/functions:
   /// add_to_end, add_to_start, add_before_current, add_after_current,
   /// add_element, add_list, clone_shallow and clone_deep.
   ///
private:
   Node()
   {
      constructor_worker();
   }
   ///
   /// NODE DESTRUCTOR IS PUBLIC: Removes the given node from
   /// the list. Note that the private_data field is not
   /// deleted, since a data member could belong to multiple
   /// lists.
   ///
public:
   ~Node()
   {
      destructor_worker();
   }

private:
   void constructor_worker()
   {
      ASSERT(this != null);
      private_data     = null;
      private_next     = null;
      private_previous = null;
      private_owner    = null;
   }

private:
   void destructor_worker()
   {
      if (this == null) {
         return;
      }
      /* SYNC ADJACENTS: */
      if (private_next != null) {
         private_next->private_previous = private_previous;
      }
      if (private_previous != null) {
         private_previous->private_next = private_next;
      }

ASSERT(private_owner != null);

/* SYNC FIRST: */
      if (private_owner->private_first == this) {
         private_owner->private_first =
            private_owner->private_first->private_next;
      }

/* SYNC LAST: */
      if (private_owner->private_last == this) {
         private_owner->private_last =
            private_owner->private_last->private_previous;
      }

/* ADJUST LENGTH: */
      private_owner->private_length--;

/* MUTATOR ANNOUNCMENT: */
      private_owner->private_dirty = true;

/* SET ALL TO NULL: as node no longer belongs to any
       * linked list.  */
      {
         private_data     = null;
         private_next     = null;
         private_previous = null;
         private_owner    = null;
      }
   }

                                   // NODE GETTERS: Take O(1) time.

public:

X* get_data()
   {
      ASSERT(this != null);
      ASSERT(private_owner != null);
      private_owner->private_dirty = true;
      return private_data;
   }
   void set_data(X* x)
   {
      ASSERT(this != null);
      ASSERT(private_owner != null);
      private_owner->private_dirty = true;
      private_data = x;
   }
   Node* get_next()
   {
      ASSERT(this != null);
      ASSERT(private_owner != null);
      private_owner->private_dirty = true;
      return private_next;
   }
   Node* get_previous()
   {
      ASSERT(this != null);
      ASSERT(private_owner != null);
      private_owner->private_dirty = true;
      return private_previous;
   }
   List<X>* get_owner()
   {
      ASSERT(this != null);
      ASSERT(private_owner != null);
      private_owner->private_dirty = true;
      return private_owner;
   }
   const X* get_data_const() const
   {
      ASSERT(this != null);
      return private_data;
   }
   const Node* get_next_const() const
   {
      ASSERT(this != null);
      return private_next;
   }
   const Node* get_previous_const() const
   {
      ASSERT(this != null);
      return private_previous;
   }
   const List<X>* get_owner_const() const
   {
      ASSERT(this != null);
      return private_owner;
   }

                                   // LIST ADDERS: Take O(1) time.

   void add_before_current(X* x)
   {
      // NOTE: x could be null.
      ASSERT(this != null);

Node* n = new Node<X>();

n->private_data     = x;
      n->private_next     = this;
      n->private_previous = this->private_previous;
      n->private_owner    = this->private_owner;

/* SYNC ADJACENTS: */
      if (n->private_next != null) {
         n->private_next->private_previous = n;
      }
      if (n->private_previous != null) {
         n->private_previous->private_next = n;
      }

/* SYNC FIRST: */
      if (n->private_owner->private_first == this) {
         n->private_owner->private_first = n;
      }

/* ADJUST LENGTH: */
      n->private_owner->private_length++;

/* MUTATOR ANNOUNCMENT: */
      private_owner->private_dirty = true;
   }
   void add_after_current(X* x)
   {
      // NOTE: x could be null.
      ASSERT(this != null);

Node* n = new Node<X>();

n->private_data     = x;
      n->private_next     = this->private_next;
      n->private_previous = this;
      n->private_owner    = this->private_owner;

/* SYNC ADJACENTS: */
      if (n->private_next != null) {
         n->private_next->private_previous = n;
      }
      if (n->private_previous != null) {
         n->private_previous->private_next = n;
      }

/* SYNC LAST: */
      if (n->private_owner->private_last == this) {
         n->private_owner->private_last = n;
      }

/* ADJUST LENGTH: */
      n->private_owner->private_length++;

/* MUTATOR ANNOUNCMENT: */
      private_owner->private_dirty = true;

}

                                   // NON-ESSENTIAL ADDERS: Take O(1) time.

   ///
   /// Eliminates get_data in client code
   ///
   void add_after_current(Node<X>* node)
   {
      ASSERT(this != null);
      ASSERT(node != null);
      add_after_current(node->get_data());
   }
   ///
   /// Eliminates get_data in client code
   ///
   void add_before_current(Node<X>* node)
   {
      ASSERT(this != null);
      ASSERT(node != null);
      add_before_current(node->get_data());
   }
};

                                      // LIST_EXTRA CLASS:

/// The reason for using a macro here is so that more debug
/// information is presented than if an inline function was
/// used...

#define LIST_HH_CHECK_FOR_INDEX_OUT_OF_RANGE()                                         \
   ASSERT_INFO((index >= 0) && (index < mylist->get_length()),                          \
               (string() + "List index out of bounds (0.." + (mylist->get_length()-1) + ") index=" + index)) \

template<class X>
class List_Extra
{
private:
   List_Extra& operator = (List_Extra&);
   List_Extra(const List_Extra&);

public:

                                   // GET_INDEX / ELEMENT_AT FUNCIONS:

   ///
   /// Returns the index of a given node. Takes O(n) time.  Note that
   /// indicies start from zero, like C & Java arrays.
   ///
   friend int get_index(const Node<X>* node)
   {
      ASSERT(node != null);
      const List<X>* mylist = node->get_owner_const();
      ASSERT(mylist != null);
      int count = 0;
      for_list_const (X,n,mylist) {
         if (n == node) {
            return count;
         }
         count++;
      }
      cout << "\n*** This line should never get executed.\n";
      ASSERT(false);
   }
   ///
   /// FUNCTION: get_element_at is the inverse of get_index.
   ///
   /// Examples:
   ///
   /// get_element_at(n->get_owner(),get_index(n))==n.
   ///
   /// get_index(get_element_at(mylist,i))==i
   ///
   /// Takes O(n) time.  Note that indicies start from zero, like C &
   /// Java arrays.
   ///
   friend Node<X>* get_element_at(List<X>* mylist, int index)
   {
      ASSERT(mylist != null);

LIST_HH_CHECK_FOR_INDEX_OUT_OF_RANGE();

if (index <= mylist->get_length() / 2) {
         // COUNT FORWARDS FROM FIRST:
         int count=0;
         for_list (X,n,mylist) {
            if (count == index) {
               ASSERT(mylist->get_dirty() == true);
               return n;
            }
            count++;
         }
      } else {
         // COUNT BACKWARDS FROM LAST:
         int count = mylist->get_length()-1;
         for_list_backwards (X,n,mylist) {
            if (count == index) {
               return n;
            }
            count--;
         }
      }
      cout << "\n*** This line should never get executed.\n";
      ASSERT(false);
   }

friend const Node<X>* get_element_at_const(const List<X>* mylist, int index)
   {
      ASSERT(mylist != null);

LIST_HH_CHECK_FOR_INDEX_OUT_OF_RANGE();

if (index <= mylist->get_length() / 2) {
         // COUNT FORWARDS FROM FIRST:
         int count=0;
         for_list_const (X,n,mylist) {
            if (count == index) {
               return n;
            }
            count++;
         }
      } else {
         // COUNT BACKWARDS FROM LAST::
         int count = mylist->get_length()-1;
         for_list_backwards_const (X,n,mylist) {
            if (count == index) {
               return n;
            }
            count--;
         }
      }
      cout << "\n*** this line should never get executed\n";
      ASSERT(false);
      //return null;
   }

friend void set_element_at(List<X>* mylist, int index, X* x)
   {
      // NOTE: x could be null.
      ASSERT(mylist != null);

LIST_HH_CHECK_FOR_INDEX_OUT_OF_RANGE();

get_element_at(mylist,index)->set_data(x);
   }
   /* Eliminates get_data in client code. */
   friend void set_element_at(List<X>* mylist, int index, Node<X>* node)
   {
      ASSERT(mylist != null);
      ASSERT(node != null);

LIST_HH_CHECK_FOR_INDEX_OUT_OF_RANGE();

set_element_at(mylist, index, node->get_data());
   }

                                   // FIND FUNCTIONS:

   ///
   ///  Takes O(n) time
   ///
   friend Node<X>* find_element_eq(Node<X>* start, const X* element)
   {
      // NOTE: start could be null.
      for (Node<X>* n = start; n != null; n = n->get_next()) {
         if (n->get_data() == element) {
            return n;
         }
      }
      return null;
   }
   ///
   /// Takes O(n) time
   ///
   friend const Node<X>* find_element_eq_const(const Node<X>* start,
                                               const X* element)
   {
      // NOTE: start could be null.
      for (const Node<X>* n = start; n != null; n = n->get_next_const()) {
         if (n->get_data_const() == element) {
            return n;
         }
      }
      return null;
   }

                                   // CLONE FUNCTION:

   ///
   /// Takes O(n) time
   ///
   friend List<X>* clone_shallow(List<X>* mylist)
   {
      List<X>* result = new List<X>;
      for_list (X,n,mylist) {
         X* x = n->get_data();
         result->add_to_end(x);
      }
      return result;
   }

                                   // DELETE_DUPLICATES_EQ FUNCTION:

   ///
   /// Removes duplicates from a list in the sense of operator ==
   /// (const X*, const X*).  Takes O(n^2) time.
   ///
   friend void delete_duplicates_eq(List<X>* mylist)
   {
      ASSERT(mylist != null);

for_list (X, n1, mylist) {
         for_list (X, n2, mylist) {
            if (n1 < n2) {
               if (n1->get_data() != null) {
                  if (n1->get_data() == n2->get_data()) {
                     n2->set_data(null);
                  }
               }
            }
         }
      }
      Node<X>* n_next;
      for (Node<X>* n = mylist->get_first(); n != null; n=n_next) {
         n_next = n->get_next();
         if (n->get_data() == null) {
            delete n;
         }
      }
   }

                                      // QUICKSORT:

   friend void quicksort(List<X>* mylist, bool (*is_less_than)(const X* x1, const X* x2))
   {
      //PRINT(input_list->get_length());

      if (mylist->get_length() < 2) {
         return;
      }

X* mid = get_element_at(mylist,mylist->get_length() / 2)->get_data();
      List<X>* smaller_than = new List<X>();
      List<X>* equal_to     = new List<X>();
      List<X>* greater_than = new List<X>();

{
         ///
         /// build sub lists
         ///
         for_list (X, n, mylist) {
            X* t = n->get_data();
            if (is_less_than(t, mid)) {
               smaller_than->add_element(t);
            } else if (is_less_than(mid,t)) {
               greater_than->add_element(t);
            } else {
               assert(!is_less_than(t,mid));
               assert(!is_less_than(mid,t));
               equal_to->add_element(t);
            }
         }
         mylist->delete_shallow();
      }

{
         ///
         /// Recursive call
         ///
         if (smaller_than->get_length() > 1) {
            quicksort(smaller_than, is_less_than);
         }
         if (greater_than->get_length() > 1) {
            quicksort(greater_than, is_less_than);
         }
      }

{
         ///
         /// Merge lists
         ///
         for_list (X,n,smaller_than) {
            mylist->add_element(n);
         }
         delete smaller_than;
         for_list (X,n,equal_to) {
            mylist->add_element(n);
         }
         delete equal_to;
         for_list (X,n,greater_than) {
            mylist->add_element(n);
         }
         delete greater_than;
      }
   }

                                   // NON-ESSENTIAL LIST FUNCTIONS: Take O(1) time.

   friend bool is_empty(const List<X>* mylist)
   {
      ASSERT(mylist != null);
      return mylist->get_length() == 0;
   }
   // -------------------------------------------
   friend Node<X>* get_second(List<X>* mylist)
   {
      ASSERT(mylist != null);
      ASSERT(mylist->get_length() >= 2);
      return mylist->get_first()->get_next();
      //return get_element_at(mylist, 2);
   }
   friend Node<X>* get_third(List<X>* mylist)
   {
      ASSERT(mylist != null);
      ASSERT(mylist->get_length() >= 3);
      return mylist->get_first()->get_next()->get_next();
      //return get_element_at(mylist, 3);
   }
   friend const Node<X>* get_second_const(const List<X>* mylist)
   {
      ASSERT(mylist != null);
      ASSERT(mylist->get_length() >= 2);
      return mylist->get_first_const()->get_next_const();
      //return get_element_at_const(mylist, 2);
   }
   friend const Node<X>* get_third_const(const List<X>* mylist)
   {
      ASSERT(mylist != null);
      ASSERT(mylist->get_length() >= 3);
      return mylist->get_first_const()->get_next_const()->get_next_const();
      //return get_element_at_const(mylist, 3);
   }
   // -------------------------------------------
   friend Node<X>* get_second_to_last(List<X>* mylist)
   {
      ASSERT(mylist != null);
      ASSERT(mylist->get_length() >= 2);
      return mylist->get_last()->get_previous();
      //return get_element_at(mylist, mylist->get_length() - 1 - 1);
   }
   friend Node<X>* get_third_to_last(List<X>* mylist)
   {
      ASSERT(mylist != null);
      ASSERT(mylist->get_length() >= 3);
      return mylist->get_last()->get_previous()->get_previous();
      //return get_element_at(mylist, mylist->get_length() - 1 - 2);
   }
   friend const Node<X>* get_second_to_last_const(const List<X>* mylist)
   {
      ASSERT(mylist != null);
      ASSERT(mylist->get_length() >= 2);
      return mylist->get_last_const()->get_previous_const();
      //return get_element_at_const(mylist, mylist->get_length() - 1 - 1);
   }
   friend const Node<X>* get_third_to_last_const(const List<X>* mylist)
   {
      ASSERT(mylist != null);
      ASSERT(mylist->get_length() >= 3);
      return mylist->get_last_const()->get_previous_const()->get_previous_const();
      //return get_element_at_const(mylist, mylist->get_length() - 1 - 2);
   }

                                   // NON-ESSENTIAL NODE FUNCTIONS: Take O(1) time.

   friend bool is_first(const Node<X>* node)
   {
      ASSERT(node != null);
      return node->get_previous_const() == null;
   }
   friend bool is_last(const Node<X>* node)
   {
      ASSERT(node != null);
      return node->get_next_const() == null;
   }

friend Node<X>* get_cyclic_next(Node<X>* node)
   {
      ASSERT(node != null);
      if (node->get_next() != null) {
         ASSERT(node->get_owner()->get_dirty() == true);
         return node->get_next();
      }
      else {
         ASSERT(node->get_owner()->get_dirty() == true);
         return node->get_owner()->get_first();
      }
   }
   friend const Node<X>* get_cyclic_next_const(const Node<X>* node)
   {
      ASSERT(node != null);
      if (node->get_next_const() != null) {
         return node->get_next_const();
      }
      else {
         return node->get_owner_const()->get_first_const();
      }
   }
   friend Node<X>* get_cyclic_previous(Node<X>* node)
   {
      ASSERT(node != null);
      if (node->get_previous() != null) {
         ASSERT(node->get_owner()->get_dirty() == true);
         return node->get_previous();
      }
      else {
         ASSERT(node->get_owner()->get_dirty() == true);
         return node->get_owner()->get_last();
      }
   }
   friend const Node<X>* get_cyclic_previous_const(const Node<X>* node)
   {
      ASSERT(node != null);
      if (node->get_previous_const() != null) {
         return node->get_previous_const();
      }
      else {
         return node->get_owner_const()->get_last_const();
      }
   }

};

                                      // LIST_IO CLASS:

class Reader;
class Writer;

///
/// This class assumes that const char* get_class_name(const List<T>*)
/// has been defined.
///
template<class X>
class List_Io
{
private:
   List_Io& operator = (List_Io&);
   List_Io(const List_Io&);

public:
   friend Writer& operator << (Writer& w, const Node<X>& node)
   {
      if (&node == null || node.get_data_const() == null) {
         w << "null";
      } else {
         w << *node.get_data_const();
      }
      return w;
   }
   friend Writer& operator << (Writer& w, const List<X>& mylist)
   {
      if (&mylist == null) {
         w << "null";
      } else {
         w << '(' << get_class_name(&mylist);
         for_list_const (X,n,&mylist) {
            w << ' ' << *n;
         }
         w << ')';
      }
      return w;
   }

friend Reader& operator >> (Reader& r, List<X>& mylist)
   {
      ASSERT(&mylist != null);
      ASSERT(mylist.get_length() == 0);

r >> '(' >> get_class_name(&mylist);
      while (!r.looking_at(')')) {
         if (r.looking_at("null")) {
            X* x = null;
            mylist.add_to_end(x);
            r >> "null";
         } else {
            X* x = new X();
            r >> *x;
            mylist.add_to_end(x);
         }
      }
      r >> ')';
      return r;
   }

                                   // OK FUNCTION:

   ///
   /// Function needs to be in this class because it needs to
   /// call Writer& operator << (Writer&, const List&).
   ///
   /// This function would experience an infinite loop with a
   /// circular list, but there is no way to set private_next
   /// or private_previous from outside the List or Node
   /// classes and therefore there is no way a circular list
   /// could be created.
   ///
   friend void OK(const List<X>* mylist)
   {
      /// NOTE: mylist could be null
      if (mylist == null) {
         return;
      }

string_buffer message;
      bool          was_error = false;

      /// TEST 1!
      {
         if (mylist->get_first_const() == null) {
            // TEST NOT NEEDED AS WITH SHOW UP WITH LENGTH COMPARISION:
            //if (mylist->get_last_const() != null) {
            //message << "\n*** OK failed\n";
            //message << "private_first == null && private_last != null\n";
            //}
         } else {
            if (mylist->get_first_const()->get_previous_const() != null) {
               message << "\n*** OK failed\n";
               message << "private_first->private_previous != null";
            }
         }
      }

      /// TEST 2!
      {
         if (mylist->get_last_const() == null) {
            // TEST NOT NEEDED AS WITH SHOW UP WITH LENGTH COMPARISION:
            //if (mylist->get_first_const() != null) {
            //message << "\n*** OK failed\n";
            //message << "private_last == null && private_first != null\n";
            //}
         } else {
            if (mylist->get_last_const()->get_next_const() != null) {
               message << "\n*** OK failed\n";
               message << "private_last->private_next != null";
            }
         }
      }

      /// TEST 3!
      {
         const Node<X>* n = mylist->get_first_const();
         if (n != null) {
            for (; n->get_next_const() != null; n=n->get_next_const()) {
            }
            if (n != mylist->get_last_const()) {
               message << "\n*** OK failed\n";
               message << "Calculated last (" << *n << ") ";
               message << "does not agree with last element of list (";
               message << *mylist->get_last_const() << ")";
               was_error = true;
            }
         }
      }

      /// TEST 4!
      {
         const Node<X>* n = mylist->get_last_const();
         if (n != null) {
            for (; n->get_previous_const() != null; n=n->get_previous_const()) {
            }
            if (n != mylist->get_first_const()) {
               message << "\n*** OK failed\n";
               message << "Calculated first (" << *n << ") ";
               message << "does not agree with first element of list (";
               message << *mylist->get_first_const() << ")";
               was_error = true;
            }
         }
      }

      /// TEST 5! correct owner field
      {
         bool ok = true;

for_list_const (X,n,mylist) {
            if (n->get_owner_const() != mylist) {
               ok = false;
               break;
            }
         }
         for_list_backwards_const (X,n,mylist) {
            if (n->get_owner_const() != mylist) {
               ok = false;
               break;
            }
         }

if (!ok) {
            message << "\n*** OK failed\n";
            message << "Some list element(s) do not have the correct owner field!";
            was_error = true;
         }
      }

      /// TEST 6! correct length forward
      {
         int calculated_length_forward = 0;
         for_list_const (X,nn,mylist) {
            calculated_length_forward++;
         }
         if (calculated_length_forward != mylist->get_length()) {
            message << "\n*** OK failed\n";
            message << "Calculated length forward (" << calculated_length_forward << ") ";
            message << "does not match list length (" << mylist->get_length() << ")";
            was_error = true;
         }
      }

      /// TEST 7! correct length backward
      {
         int calculated_length_backward = 0;
         for_list_backwards_const (X,nn,mylist) {
            calculated_length_backward++;
         }
         if (calculated_length_backward != mylist->get_length()) {
            message << "\n*** OK failed\n";
            message << "Calculated length backward (" << calculated_length_backward << ") ";
            message << "does not match list length (" << mylist->get_length() << ")";
            was_error = true;
         }
      }

if (was_error) {
         message << "\n\nHere is the list: " << *mylist << endl;
      }

ASSERT_INFO(!was_error, message);
   }
};

                                      // LIST_OPERATOR_EE CLASS:

///
/// This class should be instantiated only if operator
/// == (const X&, const X&) has been defined.
///
template<class X>
class List_Operator_Ee
{
private:
   List_Operator_Ee& operator = (List_Operator_Ee&);
   List_Operator_Ee(const List_Operator_Ee&);

                                   // EQUALITY FUNCTIONS:

public:
   ///
   /// A more readable alternative to operator == (const X&,
   /// const X&).
   ///
   /// BUGGER: can't be a friend function
   /// because this would conflict with other
   /// functions of the same name, unless we
   /// used a namespace
   ///
   static bool xs_equal(const X* x1, const X* x2)
   {
      if ((x1 == null) && (x2 == null)) {
         return true;
      } else if ((x1 == null) || (x2 == null)) {
         return false;
      } else {
         return *x1 == *x2;
      }
   }
   ///
   /// Compares list contents in the sense of operator ==
   /// (const X&, constX&).  Takes
   /// O(min(list1.get_length(),list2.get_length())) time.
   ///
   friend bool operator == (const List<X>& list1, const List<X>& list2)
   {
      if ((&list1 == null) && (&list2 == null)) {
         return true;
      } else if ((&list1 == null) || (&list2 == null)) {
         return false;
      }

const Node<X>* n1 = list1.get_first_const();
      const Node<X>* n2 = list2.get_first_const();
      for ( ; ; ) {
         if ((n1 == null) && (n2 == null)) {
            return true;
         }
         if ((n1 == null) || (n2 == null)) {
            return false;
         }
         if (!xs_equal(n1->get_data_const(), n2->get_data_const())) {
            return false;
         }
         n1 = n1->get_next_const();
         n2 = n2->get_next_const();
      }
      return true;
   }
   friend bool operator != (const List<X>& list1, const List<X>& list2)
   {
      return !(list1 == list2);
   }
   ///
   /// More readable alternative to operator == (const List&, const
   /// List&)
   ///
   friend bool lists_equal(const List<X>* list1, const List<X>* list2)
   {
      return *list1 == *list2;
   }

                                   // FIND FUNCTIONS:

   ///
   /// Finds an element in the sense of operator == (const X&,const X&).
   ///
   /// Takes O(n) time.
   ///
   friend Node<X>* find_element_equal(Node<X>* start, const X& element)
   {
      // NOTE: start could be null.
      for (Node<X>* n = start; n != null; n = n->get_next()) {
         if (xs_equal(n->get_data(), &element)) {
            return n;
         }
      }
      return null;
   }
   friend const Node<X>* find_element_equal_const(const Node<X>* start, const X& element)
   {
      // NOTE: start could be null.
      for (const Node<X>* n = start; n != null; n = n->get_next_const()) {
         if (xs_equal(n->get_data_const(), &element)) {
            return n;
         }
      }
      return null;
   }

                                      // DELETE_DUPLICATES_EQUAL FUNCTION:

   ///
   /// Removes duplicates from a list in the sense of
   /// operator == (const X&, const X&).  Takes O(n^2)
   /// time.
   ///
   friend void delete_duplicates_equal(List<X>* mylist)
   {
      ASSERT(mylist != null);
      for_list (X, n1, mylist) {
         for_list (X, n2, mylist) {
            if (n1 < n2) {
               if (xs_equal(n1->get_data(), n2->get_data())) {
                  n2->set_data(null);
               }
            }
         }
      }
      Node<X>* n_next;
      for (Node<X>* n = mylist->get_first(); n != null; n=n_next) {
         n_next = n->get_next();
         if (n->get_data() == null) {
            delete n;
         }
      }
   }
   friend void delete_duplicates_equal_deep(List<X>* mylist)
   {
      ASSERT(mylist != null);
      for_list (X, n1, mylist) {
         for_list (X, n2, mylist) {
            if (n1 < n2) {
               if (xs_equal(n1->get_data(), n2->get_data())) {
                  delete n2->get_data();
                  n2->set_data(null);
               }
            }
         }
      }
      Node<X>* n_next;
      for (Node<X>* n = mylist->get_first(); n != null; n=n_next) {
         n_next = n->get_next();
         if (n->get_data() == null) {
            delete n;
         }
      }
   }
};

                                      // LIST_CLONE CLASS:

///
/// This class should be instantiated only if X* clone(X&) has
/// been defined.  If X(const X&) is been defined for the class X then
/// it should have the same result as the clone() function.
///
/// We don't use X(const X&) directly so that this
/// method can be set as private to disallow passing
/// and returning by value.
///
template<class X>
class List_Clone
{
   friend void add_element_deep(List<X>* accumulator, const X* x)
   {
      ASSERT(accumulator != null);
      ASSERT(x != null);
      X* xx = clone(*x);
      accumulator->add_to_end(xx);
   }
   friend void add_list_deep(List<X>* accumulator, const List<X>* adder)
   {
      // NOTE: adder could ne null
      ASSERT(accumulator != null);

if (adder != null) {
         for_list_const (X,n,adder) {
            add_element_deep(accumulator, n->get_data_const());
         }
      }
   }
   /* Takes O(n) time. */
   friend List<X>* clone_deep(const List<X>* mylist)
   {
      ASSERT(mylist != null);
      List<X>* result = new List<X>;
      add_list_deep(result, mylist);
      return result;
   }
};

#endif /* ALREADY_INCLUDED_LIST_HH */