list.ht

    
// -*- c++ -*-

#include "list.hh"

                                      // Node METHODS!

template<class X>
Node<X>::~Node()
{
   if (private_next) private_next->private_previous = private_previous;
   if (private_previous) 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;
   }
}
template<class X>
void Node<X>::add(const X& x)
{
   add_next(x);
}
template<class X>
void Node<X>::add_next(const X& x)
{
   Node* n = new Node();

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

/* SYNCING WITH ADJACENTS: */
   if (n->private_previous) n->private_previous->private_next = n;
   if (n->private_next) n->private_next->private_previous = n;

/* SYNC LAST: */
   if (n->private_owner->private_last == this)
      n->private_owner->private_last = n;
}
template<class X>
void Node<X>::add_previous(const X& x)
{
   Node* n = new Node();

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

/* SYNCING WITH ADJACENTS: */
   if (n->private_previous) n->private_previous->private_next = n;
   if (n->private_next) n->private_next->private_previous = n;

/* SYNC FIRST: */
   if (n->private_owner->private_first == this)
      n->private_owner->private_first = n;
}
template<class X>
Node<X>* Node<X>::cyclic_next() const
{
   if (private_next) {
      return private_next;
   }
   else {
      return private_owner->private_first;
   }
}
template<class X>
Node<X>* Node<X>::cyclic_previous() const
{
   if (private_previous) {
      return private_previous;
   }
   else {
      return private_owner->private_last;
   }
}

                                      // List METHODS!

template<class X>
void List<X>::add_to_start(const X& x)
{
   Node<X>* n = new Node<X>();

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

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

/* SYNC LAST: */
   if (private_last == null) {
      private_last = n;
   }
}
template<class X>
void List<X>::add_to_end(const X& x)
{
   Node<X>* n = new Node<X>();

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

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

/* SYNC FIRST: */
   if (private_first == null) {
      private_first = n;
   }
}
template<class X>
void List<X>::add(const X& x)
{
   add_to_end(x);
}
template<class X>
void List<X>::reverse()
{

/* SWAP NEXT AND PREVIOUS POINTERS: */
   Node<X>* n_next = null;
   for (Node<X>* n = private_first; n != null; n=n_next) {
      n_next = n->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;

}
template<class X>
List<X>* List<X>::clone()
{
   List* answer = new List();
   for (Node<X>* n = private_first; n != null; n=n->next()) {
      answer->add_to_end(n->current);
   }
   return answer;
}
template<class X>
int List<X>::length() const
{
   int count = 0;
   for (Node<X>* n = private_first; n != null; n=n->next()) {
      count++;
   }
   return count;
}
template<class X>
bool List<X>::is_empty() const
{
   return private_first == null;
}
template<class X>
void List<X>::OK() const
{
   Node<X>* n = private_first;
   if (n != null) {
      for (; n->next() != null; n=n->next()) {
      }
   }

CONTRACT(n == private_last,
            "last pointer does not agree with last element of list!\n" <<
            "list = " << *this << endl);

n = private_last;
   if (n != null) {
      for (; n->previous() != null; n=n->previous()) {
      }
   }

CONTRACT(n == private_first,
            "first pointer does not agree with last element of list!\n" <<
            "list = " << *this << endl);

n = private_first;
   bool ok = true;
   for (; n != null; n=n->next()) {
      if (n->private_owner != this) {
         ok = false;
      }
   }

CONTRACT(ok,
            "some list element(s) do not have the correct 'owner' field!\n" <<
            "list = " << *this << endl);

   //cout << "Integrity check succeeded!\n";
}
template<class X>
List<X>::~List()
{
   Node<X>* n_next;
   for (Node<X>* n = private_first; n != null; n=n_next) {
      n_next = n->next();
      delete n;
   }
}