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 public:
  42
  43   /// maximum length of array.
  44   vsize max_;
  45
  46   /// the data itself
  47   T *array_;
  48
  49   /// stretch or shrink  array.
  50   void remax (vsize newmax)
  51   {
  52     T *newarr = new T[newmax];
  53     size_ = (newmax < size_) ? newmax : size_;
  54     arrcpy (newarr, array_, size_);
  55
  56     delete[] array_;
  57     array_ = newarr;
  58     max_ = newmax;
  59   }
  60   vsize size_;
  61
  62 public:
  63   /* std::vector interface */
  64   typedef T* iterator;
  65   typedef T const* const_iterator;
  66
  67   Array ()
  68   {
  69     array_ = 0;
  70     max_ = 0;
  71     size_ = 0;
  72   }
  73
  74   Array (Array const &src)
  75   {
  76     array_ = src.copys ();
  77     max_ = size_ = src.size_;
  78   }
  79
  80   Array (const_iterator begin, const_iterator end);
  81
  82   T const &back () const
  83   {
  84     return (*this)[size_ - 1];
  85   }
  86
  87   T &back ()
  88   {
  89     return (*this)[size_ - 1];
  90   }
  91
  92   bool empty () const
  93   {
  94     return !size_;
  95   }
  96
  97   void pop_back ()
  98   {
  99     assert (!empty ());
 100     resize (size () - 1);
 101   }
 102
 103   vsize size () const
 104   {
 105     return size_;
 106   }
 107
 108   /** set the size_ to #s#.
 109       POST: size () == s.
 110       Warning: contents are unspecified */
 111   void resize (vsize s)
 112   {
 113     if (s > max_)
 114       remax (s);
 115     size_ = s;
 116   }
 117
 118   T*
 119   data ()
 120   {
 121     return array_;
 122   }
 123
 124   T const*
 125   data () const
 126   {
 127     return array_;
 128   }
 129
 130   iterator
 131   begin ()
 132   {
 133     return data ();
 134   }
 135
 136   const_iterator
 137   begin () const
 138   {
 139     return data ();
 140   }
 141
 142   iterator
 143   end ()
 144   {
 145     return data () + size_;
 146   }
 147
 148   const_iterator
 149   end () const
 150   {
 151     return data () + size_;
 152   }
 153
 154   void clear ()
 155   {
 156     //resize (0);
 157     size_ = 0;
 158   }
 159
 160   /* std::vector uses unchecked variant for [] */
 161   T &operator [] (vsize i)
 162   {
 163     return elem_ref (i);
 164   }
 165
 166   /* std::vector uses unchecked variant for [] */
 167   T const &operator [] (vsize i) const
 168   {
 169     return elem_ref (i);
 170   }
 171
 172   iterator
 173   erase (iterator p)
 174   {
 175     vsize i = p - data ();
 176 #if !STD_VECTOR
 177     assert (i >= 0 && i < size_);
 178 #else
 179     assert (i < size_);
 180 #endif
 181     arrcpy (array_ + i, array_ + i + 1, size_ - i - 1);
 182     size_--;
 183     return p;
 184   }
 185
 186
 187
 188
 189   /* Flower intererface */
 190
 191
 192   /// check invariants
 193   void OK () const;
 194   /** report the size_.
 195       @see
 196       {setsize_}
 197   */
 198
 199   Array (T *tp, vsize n)
 200   {
 201     array_ = new T[n];
 202     max_ = size_ = n;
 203     arrcpy (array_, tp, n);
 204   }
 205
 206   // ugh, get around gcc 2.8.1 ice; see bezier.cc
 207   Array (vsize i)
 208   {
 209     max_ = size_ = i;
 210     array_ = new T[i];
 211   }
 212
 213   /// tighten array size_.
 214   void tighten_maxsize ()
 215   {
 216     remax (size_);
 217   }
 218
 219   ~Array ()
 220   {
 221     delete[] array_;
 222   }
 223
 224   /// return a  "new"ed copy of array
 225   T *copys () const
 226   {
 227     T *Tarray = new T[size_];
 228     arrcpy (Tarray, array_, size_);
 229     return Tarray;
 230   }
 231
 232   T const *accesses () const
 233   {
 234     return array_;
 235   }
 236   void operator = (Array const &src)
 237   {
 238     resize (src.size_);
 239     arrcpy (array_, src.array_, size_);
 240   }
 241
 242   T *remove_array ();
 243
 244   /// access element
 245   T &elem_ref (vsize i) const
 246   {
 247 #if !STD_VECTOR
 248     assert (i >= 0 && i < size_);
 249 #else
 250     assert (i < size_);
 251 #endif
 252     return ((T *)array_)[i];
 253   }
 254   /// access element
 255   T elem (vsize i) const
 256   {
 257     return elem_ref (i);
 258   }
 259
 260   /// add to the end of array
 261   void push_back (T x)
 262   {
 263     if (size_ == max_)
 264       remax (2 * max_ + 1);
 265
 266     // T::operator= (T &) is called here. Safe to use with automatic
 267     // vars
 268     array_[size_++] = x;
 269   }
 270 #if 0
 271   /// remove and return last entry
 272   T pop ()
 273   {
 274     assert (!empty ());
 275     T l = top (0);
 276     resize (size () - 1);
 277     return l;
 278   }
 279 #endif
 280
 281   /// access last entry
 282   T &top (vsize j)
 283   {
 284     return (*this)[size_ - j - 1];
 285   }
 286   /// return last entry
 287   T top (vsize j) const
 288   {
 289     return (*this)[size_ - j - 1];
 290   }
 291
 292   T &boundary (int dir, vsize idx)
 293   {
 294     assert (dir);
 295     if (dir == 1)
 296       return top (idx);
 297     else
 298       return elem_ref (idx);
 299   }
 300   T boundary (int dir, vsize idx) const
 301   {
 302     assert (dir);
 303     if (dir == 1)
 304       return top (idx);
 305     else
 306       return elem (idx);
 307   }
 308   void swap (vsize i, vsize j)
 309   {
 310     T t ((*this)[i]);
 311     (*this)[i] = (*this)[j];
 312     (*this)[j] = t;
 313   }
 314
 315   void insert (T k, vsize j);
 316
 317   void unordered_del (vsize i)
 318   {
 319     elem_ref (i) = back ();
 320     resize (size () -1);
 321   }
 322   void concat (Array<T> const &src)
 323   {
 324     vsize s = size_;
 325     resize (size_ + src.size_);
 326     arrcpy (array_ + s, src.array_, src.size_);
 327   }
 328   void reverse ();
 329 };
 330
 331 #include "array.icc"
 332
 333 }
 334
 335 #endif