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