flower/include/array.hh

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