flower/include/array.hh

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