flower/include/array.hh

   1 /*
   2   (c) 1995--2005 Han-Wen Nienhuys
   3
   4   Distributed under GNU GPL
   5 */
   6
   7 #ifndef ARRAY_H
   8 #define ARRAY_H
   9 #include <cassert>
  10
  11 #ifndef INLINE
  12 #define INLINE inline
  13 #endif
  14
  15 /// copy a bare (C-)array from #src# to #dest# sized  #count#
  16 template<class T> void arrcpy (T *dest, T const *src, int count);
  17
  18 /**
  19    Scaleable array/stack template, for a type T with default constructor.
  20
  21
  22    This template implements a scaleable vector. With (or without) range
  23    checking. The type T should have a default constructor. It is
  24    best suited for simple types, such as int, double or String, it
  25    provides a paranoidly safe replacement for the new T[int] construct.
  26
  27    You should \bf{never} store pointers to objects in an Array (since
  28    the array may be relocated without the pointer knowing it).
  29
  30    It uses stack terminology, (push, pop, top), and  can be used as a stack.
  31 */
  32 template<class T>
  33 class Array
  34 {
  35 protected:
  36   /// maximum length of array.
  37   int max_;
  38
  39   /// the data itself
  40   T *array_;
  41
  42   /// stretch or shrink  array.
  43   void remax (int newmax)
  44   {
  45     T *newarr = new T[newmax];
  46     size_ = (newmax < size_) ? newmax : size_;
  47     arrcpy (newarr, array_, size_);
  48
  49     delete[] array_;
  50     array_ = newarr;
  51     max_ = newmax;
  52   }
  53   int size_;
  54
  55 public:
  56   /// check invariants
  57   void OK () const;
  58   /** report the size_.
  59       @see
  60       {setsize_}
  61   */
  62
  63   int size () const
  64   {
  65     return size_;
  66   }
  67
  68   /// POST: size () == 0
  69   void clear ()
  70   {
  71     size_ = 0;
  72   }
  73
  74   Array (T *tp, int n)
  75   {
  76     array_ = new T[n];
  77     max_ = size_ = n;
  78     arrcpy (array_, tp, n);
  79   }
  80
  81   Array ()
  82   { array_ = 0; max_ = 0; size_ = 0; }
  83
  84   // ugh, get around gcc 2.8.1 ice; see bezier.cc
  85   Array (int i)
  86   {
  87     max_ = size_ = i;
  88     array_ = new T[i];
  89   }
  90
  91   /** set the size_ to #s#.
  92       POST: size () == s.
  93       Warning: contents are unspecified */
  94   void set_size (int s)
  95   {
  96     if (s > max_) remax (s);
  97     size_ = s;
  98   }
  99
 100   ~Array ()
 101   { delete[] array_; }
 102
 103   /// return a  "new"ed copy of array
 104   T *copys () const
 105   {
 106     T *Tarray = new T[size_];
 107     arrcpy (Tarray, array_, size_);
 108     return Tarray;
 109   }
 110
 111   T const *accesses () const
 112   {
 113     return array_;
 114   }
 115   void operator = (Array const &src)
 116   {
 117     set_size (src.size_);
 118     arrcpy (array_, src.array_, size_);
 119   }
 120   Array (Array const &src)
 121   {
 122     array_ = src.copys ();
 123     max_ = size_ = src.size_;
 124   }
 125
 126   /// tighten array size_.
 127   void tighten_maxsize ()
 128   {
 129     remax (size_);
 130   }
 131
 132   T *remove_array ();
 133
 134   /// access element
 135   T &operator [] (int i)
 136   {
 137     return elem_ref (i);
 138   }
 139   /// access element
 140   T const &operator [] (int i) const
 141   {
 142     return elem_ref (i);
 143   }
 144   /// access element
 145   T &elem_ref (int i) const
 146   {
 147     assert (i >= 0 && i < size_);
 148     return ((T *)array_)[i];
 149   }
 150   /// access element
 151   T elem (int i) const
 152   {
 153     return elem_ref (i);
 154   }
 155
 156   /// add to the end of array
 157   void push (T x)
 158   {
 159     if (size_ == max_)
 160       remax (2 * max_ + 1);
 161
 162     // T::operator= (T &) is called here. Safe to use with automatic
 163     // vars
 164     array_[size_++] = x;
 165   }
 166   /// remove and return last entry
 167   T pop ()
 168   {
 169     assert (!is_empty ());
 170     T l = top (0);
 171     set_size (size () - 1);
 172     return l;
 173   }
 174   /// access last entry
 175   T &top (int j = 0)
 176   {
 177     return (*this)[size_ - j - 1];
 178   }
 179   /// return last entry
 180   T top (int j = 0) const
 181   {
 182     return (*this)[size_ - j - 1];
 183   }
 184
 185   T &boundary (int dir, int idx)
 186   {
 187     assert (dir);
 188     if (dir == 1)
 189       return top (idx);
 190     else
 191       return elem_ref (idx);
 192   }
 193   T boundary (int dir, int idx) const
 194   {
 195     assert (dir);
 196     if (dir == 1)
 197       return top (idx);
 198     else
 199       return elem (idx);
 200   }
 201   void swap (int i, int j)
 202   {
 203     T t ((*this)[i]);
 204     (*this)[i] = (*this)[j];
 205     (*this)[j] = t;
 206   }
 207   bool is_empty () const
 208   { return !size_; }
 209
 210   void insert (T k, int j);
 211   /**
 212      remove  i-th element, and return it.
 213   */
 214   T get (int i)
 215   {
 216     T t = elem (i);
 217     del (i);
 218     return t;
 219   }
 220   void unordered_del (int i)
 221   {
 222     elem_ref (i) = top ();
 223     set_size (size () -1);
 224   }
 225   void del (int i)
 226   {
 227     assert (i >= 0&& i < size_);
 228     arrcpy (array_ + i, array_ + i + 1, size_ - i - 1);
 229     size_--;
 230   }
 231   // quicksort.
 232   void sort (int (*compare) (T const &, T const &),
 233              int lower = -1, int upper = -1);
 234   void concat (Array<T> const &src)
 235   {
 236     int s = size_;
 237     set_size (size_ + src.size_);
 238     arrcpy (array_ + s, src.array_, src.size_);
 239   }
 240   Array<T> slice (int lower, int upper) const;
 241   void reverse ();
 242 };
 243
 244 template<class T>
 245 int default_compare (T const &a, T const &b)
 246 {
 247   if (a < b)
 248     return -1;
 249   else if (a > b)
 250     return 1;
 251   else
 252     return 0;
 253 }
 254
 255 #include "array.icc"
 256
 257 #endif