list.hh

    
#ifndef my_include_list_hh
#define my_include_list_hh

                                      // LIST CLASS:

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

private:
   /*
    * Internal pointers.
    */
   Node<X>* private_first;
   Node<X>* private_last;

private:
   /* Disallow passing by value and returning
    * by value of node objects.
    */
   List(const List&);
   List& operator= (const List&);

public:

List()
   {
      private_first = null;
      private_last  = null;
   }
   ~List(); /* performs a shallow delete */

/* fast access to the list members */
   Node<X>* first() const { return private_first; }
   Node<X>* last() const { return private_last; }

/* aliases for add_to_end */
   void   add(const X& x);
//   void   add(Node<X>* n);

   /* adds a node onto the start of the list */
   void   add_to_start(const X& x);
//   void   add_to_start(Node<X>* n);

   /* adds a node onto the end of the list */
   void   add_to_end(const X& x);
//   void   add_to_end(Node<X>* n);

   /* runs inefficiently, at O(n) compared with the rest, at O(1) */
   /* Node<X>* find_element(const X& x); */

/* obvious methods */
   int      length() const;
   bool     is_empty() const;

/* reverses order of elements in the current list */
   void     reverse();

/* returns a shallow copy of the current list */
   List<X>* clone();

/* Ensures the internals of the object are in a consistent state.
    * Takes O(n) time.
    */
   void    OK() const;

};

                                      // NODE CLASS:

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

/* IMPORTANT: constructor is private
    * so only indirect means of construction is
    * possible.
    */
   Node() {}

private:
   /* Disallow passing by value and returning
    * by value of node objects.
    */
   Node(const Node&);
   Node& operator= (const Node&);

private:
   /*
    * Internal pointers.
    */
   Node*    private_next;
   Node*    private_previous;
   List<X>* private_owner;
public:

/* this must be public because the responsibility with the
    * management lies with the users of this class.
    */
   X     current;

/* deletes only the node, not the element attached. */
   ~Node();

bool is_first()              { return private_previous == null; }
   bool is_last()               { return private_next == null; }

/* methods for moving through the list */
   Node* next() const           { return private_next; }
   Node* previous() const       { return private_previous; }
   Node* cyclic_next() const;
   Node* cyclic_previous() const;

/* returns which list the current node belongs to */
   List<X>* owner() const       { return private_owner; }

/* aliases for add_next */
   void   add(const X& x);
//   void   add(Node* n);

   /* adds a node prior to the current one */
   void   add_previous(const X& x);
//   void   add_previous(Node* n);

   /* adds a node after the current one */
   void   add_next(const X& x);
//   void   add_next(Node* n);

};

                                      // INSTANTIATION MARCROS:

#define INSTANTIATE_OUTPUT_PROTOTYPE(X) Writer& operator<<(Writer& w, const List<X>& x)

#define INSTANTIATE_OUTPUT_DEFINITION(X)                                \
INSTANTIATE_OUTPUT_PROTOTYPE(X)                                         \
{                                                                       \
   w << '(';                                                            \
   int count = 0;                                                       \
   for (Node<X>* n=x.first(); n != null; n=n->next(), count++) {        \
      if (count != 0) {                                                 \
         cout << ' ';                                                   \
      }                                                                 \
      w << n->current;                                                  \
   }                                                                    \
   w << ')';                                                            \
   return w;                                                            \
}

#define INSTANTIATE_OUTPUT_DEFINITION_STAR(X)                           \
INSTANTIATE_OUTPUT_PROTOTYPE(X)                                         \
{                                                                       \
   w << '(';                                                            \
   int count = 0;                                                       \
   for (Node<X>* n=x.first(); n != null; n=n->next(), count++) {        \
      if (count != 0) {                                                 \
         cout << ' ';                                                   \
      }                                                                 \
      if (n->current != null) {                                         \
         w << *n->current; /* difference is the extra star here */      \
      }                                                                 \
      else {                                                            \
         w << "null";                                                   \
      }                                                                 \
   }                                                                    \
   w << ')';                                                            \
   return w;                                                            \
}

#endif /* my_include_list_hh */