flower/include/varray.hh

   1 /*
   2   (c) Han-Wen Nienhuys 1995,96,97
   3
   4   Distributed under GNU GPL
   5 */
   6
   7 #ifndef ARRAY_H
   8 #define ARRAY_H
   9 #include <assert.h>
  10
  11 /// copy a bare (C-)array from #src# to #dest# sized  #count#
  12 template<class T>
  13 inline void arrcpy (T*dest, T*src, int count) {
  14   for (int i_shadows_local=0; i_shadows_local < count ; i_shadows_local++)
  15     *dest++ = *src++;
  16 }
  17
  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
  34   */
  35 template<class T>
  36 class Array
  37 {
  38 protected:
  39   /// maximum length of array.
  40   int max_;
  41
  42   /// the data itself
  43   T *array_p_;
  44
  45   /// stretch or shrink  array.
  46   void remax (int newmax)
  47     {
  48       T* newarr = new T[newmax];
  49       size_ = (newmax < size_) ? newmax : size_;
  50       arrcpy (newarr, array_p_, size_);
  51
  52       delete[] array_p_;
  53       array_p_ = newarr;
  54       max_ = newmax;
  55     }
  56   int size_;
  57
  58 public:
  59   /// check invariants
  60   void OK() const
  61     {
  62       assert (max_ >= size_ && size_ >=0);
  63       if (max_) assert (array_p_);
  64     }
  65   /** report the size_.
  66       @see
  67       {setsize_}
  68   */
  69   int size() const
  70     { return size_; }
  71
  72   /// POST: size() == 0
  73     void clear()
  74     { size_ = 0; }
  75
  76   Array()
  77     { array_p_ = 0; max_ =0; size_ =0; }
  78
  79
  80   /** set the size_ to #s#.
  81       POST: size() == s.
  82       Warning: contents are unspecified */
  83   void set_size (int s)
  84     {
  85       if (s >= max_) remax (s);
  86       size_ = s;
  87     }
  88
  89   ~Array()
  90     { delete[] array_p_; }
  91
  92   /// return a  "new"ed copy of array
  93     T* copy_array() const
  94     {
  95       T* Tarray = new T[size_];
  96       arrcpy (Tarray, array_p_, size_);
  97       return Tarray;
  98     }
  99   // depracated
 100   operator T*() const
 101     {
 102       return copy_array();
 103     }
 104   void operator=(Array const & src)
 105     {
 106       set_size (src.size_);
 107       arrcpy (array_p_,src.array_p_, size_);
 108     }
 109   Array (Array const & src)
 110     {
 111       array_p_ = src.copy_array();
 112       max_ = size_ = src.size_;
 113     }
 114
 115   /// tighten array size_.
 116     void precompute()     {
 117       remax (size_);
 118     }
 119
 120   T * remove_array_p () {
 121     T * p = array_p_;
 122     size_ = 0;
 123     max_ = 0;
 124     array_p_ =0;
 125     return p;
 126   }
 127
 128   /// access element
 129   T &operator[] (int i)
 130     {
 131       return elem (i);
 132     }
 133   /// access element
 134     T const & operator[] (int i) const
 135     {
 136       return elem (i);
 137     }
 138   /// access element
 139     T &elem (int i) const
 140     {
 141       assert (i >=0&&i<size_);
 142       return ((T*)array_p_)[i];
 143     }
 144
 145   /// add to the end of array
 146     void push (T x)
 147     {
 148       if (size_ == max_)
 149         remax (2*max_ + 1);
 150
 151       // T::operator=(T &) is called here. Safe to use with automatic
 152       // vars
 153       array_p_[size_++] = x;
 154     }
 155   /// remove and return last entry
 156     T pop()
 157     {
 158       assert (!empty());
 159       T l = top (0);
 160       set_size (size()-1);
 161       return l;
 162     }
 163   /// access last entry
 164     T& top (int j=0)
 165     {
 166       return (*this)[size_-j-1];
 167     }
 168   /// return last entry
 169     T top (int j=0) const
 170     {
 171       return (*this)[size_-j-1];
 172     }
 173
 174
 175   void swap (int i,int j)
 176     {
 177       T t ((*this)[i]);
 178       (*this)[i]=(*this)[j];
 179       (*this)[j]=t;
 180     }
 181   bool empty() const
 182     { return !size_; }
 183   void insert (T k, int j)
 184     {
 185       assert (j >=0 && j<= size_);
 186       set_size (size_+1);
 187       for (int i=size_-1; i > j; i--)
 188         array_p_[i] = array_p_[i-1];
 189       array_p_[j] = k;
 190     }
 191   /**
 192      remove  i-th element, and return it.
 193   */
 194   T get (int i)
 195     {
 196       T t = elem (i);
 197       del (i);
 198       return t;
 199     }
 200   void unordered_del (int i)
 201
 202     {
 203       elem (i) = top();
 204       set_size (size() -1);
 205     }
 206   void del (int i)
 207     {
 208       assert (i >=0&& i < size_);
 209       arrcpy (array_p_+i, array_p_+i+1, size_-i-1);
 210       size_--;
 211     }
 212   // quicksort.
 213   void sort (int (*compare)(T const&,T const&),
 214              int lower = -1, int upper = -1)
 215     {
 216       if (lower < 0)
 217         {
 218           lower = 0 ;
 219           upper = size()-1;
 220         }
 221       if (lower >= upper)
 222         return;
 223       swap (lower, (lower+upper)/2);
 224       int last = lower;
 225       for (int i= lower +1; i <= upper; i++)
 226         if (compare (array_p_[i], array_p_[lower]) < 0)
 227           swap (++last,i);
 228       swap (lower, last);
 229       sort (compare, lower, last-1);
 230       sort (compare, last+1, upper);
 231     }
 232   void concat (Array<T> const &src)
 233     {
 234       int s = size_;
 235       set_size (size_ + src.size_);
 236       arrcpy (array_p_+s,src.array_p_, src.size_);
 237     }
 238   Array<T> slice (int lower, int upper)
 239     {
 240       assert (lower >= 0 && lower <=upper&& upper <= size_);
 241       Array<T> r;
 242       int s =upper-lower;
 243       r.set_size (s);
 244       arrcpy (r.array_p_, array_p_  + lower, s);
 245       return r;
 246     }
 247   void reverse()
 248     {
 249       int h = size_/2;
 250       for (int i =0,j = size_-1; i < h; i++,j--)
 251         swap (i,j);
 252     }
 253 };
 254
 255 #endif