_List.hh

    
#ifndef ALREADY_INCLUDED_2006_LIBD__LIST_HH
#define ALREADY_INCLUDED_2006_LIBD__LIST_HH

#include "libd.hh"
//#include "single-g-c.hh"

#define for_list(X,iterator,list)           for (ptr<List_Iterator<X> > iterator = (list)->get_first(); iterator->has_more(); iterator->advance())
#define for_list_backwards(X,iterator,list) for (ptr<List_Iterator<X> > iterator = (list)->get_last(); iterator->has_more(); iterator->retreat())

namespace dmp
{
   template<class X>
   class List_Node;

template<class X>
   class List_Iterator;

template<class X>
   class List : private Single
   {
      rtti_same(List);
      POOL1;
      friend class List_Node<X>;
      friend class List_Iterator<X>;

private:
      ptr<List_Node<X> > private_first;
      ptr<List_Node<X> > private_last;
      int                  private_length; // length is cached for better performance
      dmp::string          private_name;

      ///
      /// NOTE: prevents passing and returning by value
      ///
   private:
      List(const List& list);
      List& operator = (const List&);

public:

ptr<List> clone_shallow()
      {
         ptr<List<X> > p = List<X>::ctor();
         for_list (X, it, this)
         {
            p->add_element(it->get_data());
         }
         return p;
      }
      ptr<List<X> > clone_deep()
      {
         //PRINT(*this);
         ptr<List<X> > p = List<X>::ctor(private_name);
         ASSERT(p->get_length() == 0);
         int count = 0;
         for_list (X, it, this)
         {
            ptr<X> px = it->get_data()->clone_deep();
            //PRINT(px);
            //PRINT(*p);
            //PRINT(p->get_length());
            p->add_element(px);
            count++;
            //PRINT(p->private_length);
            //PRINT(*p);
            //PRINT(p->private_length);
            //PRINT(*p);
            //PRINT(p->private_length);
            //PRINT(p->get_length());
            //PRINT(*p);
            ASSERT_INFO(p->get_length() == count,
                        dmp::string() + "p->get_length()=" + p->get_length() + ", count=" + count);
            //PRINT(*p);
         }
         //PRINT(*p);
         return p;
      }
      void delete_all()
      {
         for_list (X, n, this)
         {
            n->delete_current();
            //n->get_data()->delete_node();
         }
         assert(private_length == 0);
         assert(private_first  == null);
         assert(private_last   == null);
      }

private:
      List(dmp::string list_name) : Single(DCODE_LIST)
      {
         ///
         /// NOTE: these are done automatically by this constructor
         ///
         //private_first = null;
         //private_last  = null;
         private_length    = 0;
         private_name = list_name;
      }

public:
      static ptr<List<X> > ctor(dmp::string name)
      {
         return new List<X>(name);
      }
      static ptr<List<X> > ctor()
      {
         return new List<X>("no name");
      }
      // template <class X> friend ptr<List<X> > new_List<X>()
      // {
      //    return new List<X>();
      // }

   private:
      ///
      /// NOTE: opens up ~List() to ptr class
      ///
      template <class T> friend class ptr;
      ~List()
      {
         //BEGIN_FUNCTION;
         if (this == null)
         {
            return;
         }
         ptr<List_Node<X> > n_next = null;
         for (ptr<List_Node<X> > n = private_first; n != null; n = n_next)
         {
            n_next = n->private_next;
            n->delete_node();
         }
         /* CHECK LENGTH: */
#ifdef DAVINS_IO_ONLINE
         ASSERT_INFO(private_length == 0, dmp::string() + "private_length=" + private_length);
#else
         ASSERT(private_length == 0);
#endif /* DAVINS_IO_ONLINE */
         //CHECKPOINT;
         {
            ///
            /// NOTE: these are done automatically by this destructor
            ///
            //private_first = null;
            //private_last  = null;
         }
         //END_FUNCTION;
      }

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

   public:
      ///
      /// NOTE: this method is the inverse of int List_Iterator<X>::get_index()
      ///
      /// NOTE: the cleverness of iterating forward or backward depending on what is the most efficient
      ///
      ptr<List_Iterator<X> > get_element_at(int i)
      {
         ASSERT(this != null);
         if (i < private_length/2)
         {
            int count = 0;
            ///
            /// NOTE: This loop is quicker than for_list
            ///
            for (ptr<List_Node<X> > n = private_first; n != null; n = n->private_next)
            {
               if (count == i)
               {
                  return List_Iterator<X>::ctor(n.operator->());
               }
               count++;
            }
         }
         else
         {
            int count = private_length-1;
            ///
            /// NOTE: This loop is quicker than for_list
            ///
            for (ptr<List_Node<X> > n = private_last; n != null; n = n->private_previous)
            {
               if (count == i)
               {
                  return List_Iterator<X>::ctor(n.operator->());
               }
               count--;
            }
         }
         ///
         /// Which is good??? Error or null?
         ///
         /// NOTE: this problem does not arise in Java...
         ///
         ERROR(dmp::string() + "No such list element: " + i + ", get_length()=" + private_length);
      }

      ///
      /// NOTE: efficient getters
      ///
      ptr<List_Iterator<X> > get_first() const /// HAZEL
      {
         return List_Iterator<X>::ctor(private_first.get_ptr());
      }
      ptr<List_Iterator<X> > get_last() const /// HAZEL
      {
         return List_Iterator<X>::ctor(private_last.get_ptr());
      }

      ///
      /// NOTE: Returns the length of the list
      ///
      int get_length() const
      {
         ASSERT(this != null);
         return private_length;
      }

dmp::string get_name() const
      {
         return private_name;
      }

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

      ///
      /// Adds a node onto the start of the list
      ///
      ptr<List<X> > add_to_start(const ptr<X>& x)
      {
         //BEGIN_FUNCTION;
         ASSERT(this != null);
         ASSERT(&x   != null);
         ASSERT(x    != null);

ptr<List_Node<X> > n = List_Node<X>::ctor();

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++;

         //END_FUNCTION;
         return this;
      }

      ///
      /// Adds a node onto the end of the list.
      ///
      ptr<List<X> > add_to_end(const ptr<X>& x)
      {
         //BEGIN_FUNCTION;
         ASSERT(this != null);
         ASSERT(&x   != null);
         //ASSERT(x    != null);

         ptr<List_Node<X> > n = List_Node<X>::ctor();
         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++;

         //PRINT(private_length);
         //END_FUNCTION;
         return this;
      }

      // REVERSE: Takes O(n) time.

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

/* SWAP NEXT AND PREVIOUS POINTERS: */
         ///
         /// NOTE: This loop is quicker than for_list
         ///
         ptr<List_Node<X> > n_next = null;
         for (ptr<List_Node<X> > n = private_first; n != null; n=n_next)
         {
            n_next = n->private_next;
            ptr<List_Node<X> > tmp = n->private_previous;
            n->private_previous = n->private_next;
            n->private_next = tmp;
         }

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

      // NON ESSENTIAL ADDERS:

      ///
      /// Adds argument "list" onto the current list
      ///
      ptr<List<X> > add_list(const ptr<List<X> >& list)
      {
         ASSERT(this != null);
         ASSERT(&list != null);
         if (list != null)
         {
            for_list (X,n,list)
            {
               add_to_end(n);
            }
         }
         return this;
      }
      ///
      /// Alias for add_to_end
      ///
      //ptr<List<X> > add_element(const ptr<X>& x)
      ptr<List<X> > add_element(const ptr<X>& x)
      {
         //BEGIN_FUNCTION;
         ASSERT(this != null);
         ASSERT(&x != null);
         //ASSERT(x != null);
         add_to_end(x);
         //END_FUNCTION;
         return this;
      }

      ///
      /// 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 List_Node
      /// classes and therefore there is no way a circular list
      /// could be created.
      ///
      bool OK()
      {
#ifdef DAVINS_IO_ONLINE
         assert(this != null);

if (this == null)
         {
            return true;
         }

dmp::string_buffer sb;
         int error_count = 0;

         /// TEST 1!
         {
            if (private_first == null)
            {
               if (private_last != null)
               {
                  /// NOTE: picked up be length calculation
                  //error_count++;
                  //sb << "(" << error_count << ") private_first == null but private_last != null\n";
               }
            }
            else
            {
               if (private_first->private_previous != null)
               {
                  error_count++;
                  sb << "(" << error_count << ") private_first->private_previous != null\n";
               }
            }
         }

         /// TEST 2!
         {
            if (private_last == null)
            {
               if (private_first != null)
               {
                  /// NOTE: picked up be length calculation
                  //error_count++;
                  //sb << "(" << error_count << ") private_last == null but private_first != null\n";
               }
            }
            else
            {
               if (private_last->private_next != null)
               {
                  error_count++;
                  sb << "(" << error_count << ") private_last->private_next != null\n";
               }
            }
         }

         /// TEST 3!
         {
            ptr<List_Node<X> > n = private_first;
            if (n != null)
            {
               for (; n->private_next != null; n=n->private_next)
               {
               }
               if (n != private_last)
               {
                  error_count++;
                  sb << "(" << error_count << ") Calculated last (" << n->private_data << ") ";
                  sb << "does not agree with last element of list (";
                  sb << private_last << ")\n";
               }
            }
         }

         /// TEST 4!
         {
            ptr<List_Node<X> > n = private_last;
            if (n != null)
            {
               for (; n->private_previous != null; n=n->private_previous)
               {
               }
               if (n != private_first)
               {
                  error_count++;
                  sb << "(" << error_count << ") Calculated first (" << n->private_data << ") ";
                  sb << "does not agree with first element of list (";
                  sb << private_first << ")\n";
               }
            }
         }

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

for (ptr<List_Node<X> > n = this->private_first; n != null; n=n->private_next)
            {
               if (n->private_owner != this) {
                  ok = false;
                  break;
               }
            }
            for (ptr<List_Node<X> > n = this->private_last; n != null; n=n->private_previous)
            {
               if (n->private_owner != this)
               {
                  ok = false;
                  break;
               }
            }

if (!ok)
            {
               error_count++;
               sb << "(" << error_count << ") Some list element(s) do not have the correct owner field!\n";
            }
         }

         /// TEST 6! correct length forward
         {
            int calculated_length_forward = 0;
            for (ptr<List_Node<X> > n = this->private_first; n != null; n=n->private_next)
            {
               calculated_length_forward++;
            }
            if (calculated_length_forward != private_length)
            {
               error_count++;
               sb << "(" << error_count << ") Calculated length forward (" << calculated_length_forward << ") ";
               sb << "does not match list length (" << private_length << ")\n";
            }
         }

         /// TEST 7! correct length backward
         {
            int calculated_length_backward = 0;
            for (ptr<List_Node<X> > n = this->private_last; n != null; n=n->private_previous)
            {
               calculated_length_backward++;
            }
            if (calculated_length_backward != private_length)
            {
               error_count++;
               sb << "(" << error_count << ") Calculated length backward (" << calculated_length_backward << ") ";
               sb << "does not match list length (" << private_length << ")\n";
            }
         }

if (error_count != 0)
         {
            dmp::cout << '\n';
            dmp::cout << "*** Error(s) in List<X>::OK() method:\n";
            dmp::cout << "------------------------------------------\n";
            dmp::cout << sb;
         }

return error_count == 0;
#else
         return true;
#endif /* DAVINS_IO_ONLINE */
      }

#ifdef DAVINS_IO_ONLINE

friend dmp::Writer& operator << (dmp::Writer& w, const List<X>& list)
      {
         ASSERT(&w    != null);
         ASSERT(&list != null);
         w << '(' << "List";
         //PRINT(list.private_length);
         for_list (X,it,&list)
         {
            //PRINT(it->get_owner()->private_length);
            w << ' ' << it->get_data();
            //PRINT(it->get_owner()->private_length);
         }
         //PRINT(list.private_length);
         w << ')';
         return w;
      }

friend dmp::Reader& operator >> (dmp::Reader& r, List<X>& list)
      {
         //BEGIN_FUNCTION;
         ASSERT(&r != null);
         ASSERT(&list != null);
         ASSERT(list.get_length() == 0);
         r >> '(' >> "List";
         //r.skip('(');
         //r.skip("List");
         //CHECKPOINT;
         while (!r.looking_at(')'))
         {
            //CHECKPOINT;
            if (r.looking_at("null"))
            {
               //CHECKPOINT;
               X* x = null;
               list.add_to_end(x);
               r.next_token(); // more efficient than r >> "null";
               //CHECKPOINT;
            }
            else
            {
               //CHECKPOINT;
               ptr<X> x = X::ctor();
               r >> *x.get_ptr();
               list.add_to_end(x);
               //CHECKPOINT;
            }
         }
         //CHECKPOINT;
         //r.skip(')');
         r >> ')';
         //CHECKPOINT;
         //END_FUNCTION;
         return r;
      }
#endif /* DAVINS_IO_ONLINE */

      ///
      /// COOL: generalised find method
      ///
      ptr<List_Iterator<X> > find(bool pred(const ptr<X>& p))
      {
         for_list (X,n,this)
         {
            if (pred(n->get_data()))
            {
               return n;
            }
         }
         return null;
      }

      ///
      /// TODO: Write: int List::find_element_eq(int start,const ptr<X>& key) cf List::find_element_equal
      ///
      /// NOTE: this method uses operator == (const X*,const X*)
      ///
      static ptr<List_Iterator<X> > find_element_eq(const ptr<List_Iterator<X> > start, const ptr<X>& key)
      {
         //ASSERT(&start != null);
         ASSERT(&key != null);
         for (ptr<List_Iterator<X> > it = start->clone(); it->has_more(); it->advance())
         {
            if (it->get_data() == key)
            {
               return it;
            }
         }
         return null;
      }

      ///
      /// NOTE: these two methods use operator == (const X&,const X&)
      ///
      ptr<List_Iterator<X> > find_element_equal(int start, const ptr<X>& key)
      {
         int count = 0;
         for_list (X, it, this)
         {
            if (count >= start)
            {
               if (*it->get_data() == *key.get_ptr())
               {
                  return it;
               }
            }
            count++;
         }
         return null;
      }

friend ptr<List_Iterator<X> > find_element_equal(const ptr<List_Iterator<X> >& start, const ptr<X>& key)
      {
         ASSERT(&start != null);
         ASSERT(&key != null);
         for (ptr<List_Iterator<X> > it = start->clone(); it->has_more(); it->advance())
         {
            if (*it->get_data() == *key.get_ptr())
            {
               return it;
            }
         }
         return null;
      }

void remove_element_eq(const ptr<X>& s)
      {
         ASSERT(this != null);
         assert(&s   != null); /// note works without this
         for_list (X,n,this)
         {
            if (n->get_data() == s)
            {
               n->delete_current();
            }
         }
      }

      ///
      /// NOTE: compare function is more efficient than any of these is it requires less calls
      ///
      ///  (1) less_than(x1,x2) or
      ///  (2) less_than_eq(x1,x2) or
      ///  (3) greater_than(x1,x2) or
      ///  (4) greater_than_eq(x1,x2).
      ///
      friend ptr<List<X> > quicksort(const ptr<List<X> >& list, int compare(const ptr<X>& x1, const ptr<X>& x2))
      {
         //BEGIN_FUNCTION;
         //PRINT(list);

         //PRINT(input_list->get_length());

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

ptr<X> mid = list->get_element_at(list->get_length() / 2)->get_data();

ptr<List<X> > smaller_than = List<X>::ctor(list->private_name);
         ptr<List<X> > equal_to     = List<X>::ctor(list->private_name);
         ptr<List<X> > greater_than = List<X>::ctor(list->private_name);

if (compare == null)
         {
            should_never_happen();
            ///
            /// if compare is null, do nothing
            ///
            return list;
         }

{
            ///
            /// build sub lists
            ///
            for_list (X, n, list)
            {
               ptr<X> t = n->get_data();
               int c = compare(t,mid);
               if (c < 0)
               {
                  smaller_than->add_element(t);
               }
               else if (c > 0)
               {
                  greater_than->add_element(t);
               }
               else
               {
                  equal_to->add_element(t);
               }
            }
         }

{
            ///
            /// Recursive call
            ///
            if (smaller_than->get_length() > 1)
            {
               smaller_than = quicksort(smaller_than, compare);
            }
            if (greater_than->get_length() > 1)
            {
               greater_than = quicksort(greater_than, compare);
            }
         }
         {
            ptr<List<X> > result = List<X>::ctor(list->private_name);

            ///
            /// Merge lists
            ///
            for_list (X,n,smaller_than)
            {
               result->add_element(n->get_data());
            }
            for_list (X,n,equal_to)
            {
               result->add_element(n->get_data());
            }
            for_list (X,n,greater_than)
            {
               result->add_element(n->get_data());
            }
            return result;
         }
         //END_FUNCTION;
      }

      ///
      /// NOTE: these don't need to access private properties
      ///
      friend bool operator == (const List<X>& list1, const List<X>& list2)
      {
         if (list1.get_length() != list2.get_length())
         {
            return false;
         }
         ptr<List_Iterator<X> > it1 = list1.get_first();
         ptr<List_Iterator<X> > it2 = list2.get_first();
         for (;;)
         {
            if (*it1->get_data() != *it2->get_data())
            {
               return false;
            }
            it1->advance();
            it2->advance();
            if (!it1->has_more() && !it2->has_more())
            {
               return true;
            }
            else if (!it1->has_more() || !it2->has_more())
            {
               should_never_happen();
               return false;
            }
         }
         return true;
      }

friend bool operator != (const List<X>& list1, const List<X>& list2)
      {
         return !(list1 == list2);
      }
   };
}

#include "_List_Node.hh"
#include "_List_Iterator.hh"

#endif /* ALREADY_INCLUDED_2006_LIBD__LIST_HH */