array.hh

    
#ifndef ALREADY_INCLUDED_ARRAY_HH
#define ALREADY_INCLUDED_ARRAY_HH

#include "../../2003/noio/io.hh"

template<class T>
class Array
{
private:
   T** internal_array;
   int internal_array_current_length;
   int internal_array_capacity;

public:
   Array()
   {
      ///
      /// Set a decent initial capacity
      /// (not too big not too small)
      ///
      internal_array_capacity = 10;

internal_array = new (T*)[internal_array_capacity];
#ifndef NDEBUG
      for (int i=0; i<internal_array_capacity; i++) {
         internal_array[i] = null;
      }
#endif /* NDEBUG */
      internal_array_current_length = 0;
   }

void delete_shallow()
   {
      ASSERT(this != null);
#ifndef NDEBUG
      for (int i=0; i<internal_array_current_length; i++) {
         internal_array[i] = null;
      }
#endif /* NDEBUG */
      internal_array_current_length = 0;

}
   ///
   /// Useful for deleting a one dimensional array.  For deleting
   /// multi-dimensional arrays, see the the following web page:
   ///
   /// www.geocities.com/davinpearson/research/2004/aas4c.html
   ///
   ///
   void delete_deep()
   {
      ASSERT(this != null);
      for (int i=0; i<internal_array_current_length; i++) {
         delete internal_array[i];
#ifndef NDEBUG
         internal_array[i] = null;
#endif /* NDEBUG */
      }
      internal_array_current_length = 0;
   }



private:
   ///
   /// Disable initialisation
   ///
   Array(const Array& a);
   ///
   /// Disable assignment
   ///
   Array& operator = (const Array&);

public:
   ~Array()
   {
      ASSERT(this != null);
      delete_shallow();
   }



public:
   int get_length() const
   {
      ASSERT(this != null);
      return internal_array_current_length;
   }

private:

static void check_for_index_out_of_range(int index, int length, const char* file, int line)
   {
      if ((index < 0) || (index >= length)) {
         ///
         /// Note how file and line are used here.
         /// A CONTRACT_3 macro could not have
         /// the same effect.
         ///
#ifdef PRINTF_AND_EXIT
         PRINTF_AND_EXIT((PLEASE_EMAIL_DAVIN
                          "*** Array index out of bounds error at\n\n"
                          "LOCATION: (%s:%d)\n\n"
                          "INDEX: %d\n\n"
                          "LENGTH: %d\n\n",
                          file,line,
                          index,
                          length));
#else
         std::cout << "*** Array index out of bounds error\n\n";
         std::cout << "LOCATION: (" << file << ':' << line << ")\n\n";
         std::cout << "INDEX: " << index << ")\n\n";
         std::cout << "LENGTH: " << length << "\n\n";
         exit(EXIT_FAILURE);
#endif /* ALLEGRO_MESSAGE_AND_EXIT */
      }
   }

public:
   /// Analogues of
   //const T* operator [] (int i) const
   //T* operator [] (int i)
   //
   /// This is not const: Compare with design pattern for const in list.hh
   T* get_element_at_nulls_ok(int i)
   {
      ASSERT(this != null);
      assert(i >= 0);
      assert(i < internal_array_current_length);
      return internal_array[i];
   }
   T* get_element_at(int i)
   {
      ASSERT(this != null);
#ifdef NDEBUG
      ///
      /// we are not debugging
      ///
      if ((i >= 0) && (i < internal_array_current_length)) {
         return internal_array[i];
      } else if (internal_array_current_length > 0) {
         return internal_array[0];
      } else {
         SHOULD_NEVER_HAPPEN();
      }
#else /* !NDEBUG */
      ///
      /// We are debugging
      ///
      check_for_index_out_of_range(i,internal_array_current_length,__FILE__,__LINE__);
      assert(internal_array[i] != null);
      return internal_array[i];
#endif /* NDEBUG */
   }
   const T* get_element_at_const_nulls_ok(int i) const
   {
      ASSERT(this != null);
      check_for_index_out_of_range(i,internal_array_current_length,__FILE__,__LINE__);
      return internal_array[i];
   }
   const T* get_element_at_const(int i) const
   {
      ASSERT(this != null);
      check_for_index_out_of_range(i,internal_array_current_length,__FILE__,__LINE__);
      return internal_array[i];
   }
   void set_element_at_nulls_ok(int i, T* element)
   {
      ASSERT(this != null);
      check_for_index_out_of_range(i,internal_array_current_length,__FILE__,__LINE__);
      internal_array[i] = element;
   }
   void set_element_at(int i, T* element)
   {
      ASSERT(this != null);
      assert(element != null);
      check_for_index_out_of_range(i,internal_array_current_length,__FILE__,__LINE__);
      internal_array[i] = element;
   }
   void add_element_nulls_ok(T* new_element)
   {
      ASSERT(this != null);
      assert(internal_array_capacity > 0);

if (internal_array_current_length >= internal_array_capacity) {

         //cout << "*** resizing array";
         //cout << " from " << internal_array_capacity;
         internal_array_capacity *= 2;
         //cout << " to " << internal_array_capacity << '\n';

         T** new_internal_array = new (T*)[internal_array_capacity];
         for (int i=0; i<internal_array_current_length; i++) {
            new_internal_array[i] = internal_array[i];
         }
         delete internal_array;
         internal_array = new_internal_array;
      }
      ASSERT(internal_array_current_length < internal_array_capacity);
      internal_array[internal_array_current_length] = new_element;
      internal_array_current_length++;
   }
   void add_element(T* new_element)
   {
      ASSERT(this != null);
      assert(new_element != null);
      add_element_nulls_ok(new_element);
   }



   ///
   /// Inefficient O(n) methods for adding
   /// or deleting from an array at a
   /// given index.
   ///
   void cascade_down(int index)
   {
      for (int i=index; i<internal_array_current_length-1; i++) {
         internal_array[i] = internal_array[i+1];
      }
      internal_array_current_length--;
   }
   void cascade_up(int index)
   {
      add_element_nulls_ok(null);
      for (int i=internal_array_current_length-1; i>index; i--) {
         internal_array[i] = internal_array[i-1];
      }
      internal_array[index] = null;
   }
};


///
/// This class assumes that const char* get_class_name(const Array<T>*)
/// has been defined.
///
template<class T>
class Array_Io
{
   friend Writer& operator << (Writer& w, const Array<T>& a)
   {
      w << '(' << get_class_name(&a);
      for (int i=0; i < a.get_length(); i++) {
         w << ' ' << *a.get_element_at_const(i);
      }
      w << ')';
      return w;
   }
   friend Reader& operator >> (Reader& r, Array<T>& a)
   {
      ASSERT(a.get_length() == 0);
      r >> '(' >> get_class_name(&a);
      while (!r.looking_at(')')) {
         T* t = new T;
         r >> *t;
         a.add_element(t);
      }
      r >> ')';
      return r;
   }
};



///
/// Non-essential functons
///

template<class T>
class Array_Extra
{
   friend int find_element_eq(const Array<T> array, int start, const T* element)
   {
      int length = array->get_length();
      for (int i=start; i<length; i++) {
         if (element == array->get_element_at_const(i)) {
            return i;
         }
      }
      return -1;
   }
};


///
/// This class assumes that operator == (const T&, const T&) has been defined
///
template<class T>
class Array_Operator_Ee
{
   friend int find_element_equal(const Array<T>* array, int start, const T& element)
   {
      int length = array->get_length();
      for (int i=start; i<length; i++) {
         if (element == *array->get_element_at_const(i)) {
            return i;
         }
      }
      return -1;
   }
};

#endif /* ALREADY_INCLUDED_ARRAY_HH */