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   // ugh, get around gcc 2.8.1 ice; see bezier.cc
  80   Array (int i)
  81   {
  82     max_ = size_ = i;
  83     array_p_ = new T[i];
  84   }
  85
  86
  87   /** set the size_ to #s#.
  88       POST: size() == s.
  89       Warning: contents are unspecified */
  90   void set_size (int s)
  91     {
  92       if (s >= max_) remax (s);
  93       size_ = s;
  94     }
  95
  96   ~Array()
  97     { delete[] array_p_; }
  98
  99   /// return a  "new"ed copy of array
 100     T* copy_array() const
 101     {
 102       T* Tarray = new T[size_];
 103       arrcpy (Tarray, array_p_, size_);
 104       return Tarray;
 105     }
 106   // depracated
 107   operator T*() const
 108     {
 109       return copy_array();
 110     }
 111   void operator=(Array const & src)
 112     {
 113       set_size (src.size_);
 114       arrcpy (array_p_,src.array_p_, size_);
 115     }
 116   Array (Array const & src)
 117     {
 118       array_p_ = src.copy_array();
 119       max_ = size_ = src.size_;
 120     }
 121
 122   /// tighten array size_.
 123     void precompute()     {
 124       remax (size_);
 125     }
 126
 127   T * remove_array_p () {
 128     T * p = array_p_;
 129     size_ = 0;
 130     max_ = 0;
 131     array_p_ =0;
 132     return p;
 133   }
 134
 135   /// access element
 136   T &operator[] (int i)
 137     {
 138       return elem (i);
 139     }
 140   /// access element
 141     T const & operator[] (int i) const
 142     {
 143       return elem (i);
 144     }
 145   /// access element
 146     T &elem (int i) const
 147     {
 148       assert (i >=0&&i<size_);
 149       return ((T*)array_p_)[i];
 150     }
 151
 152   /// add to the end of array
 153     void push (T x)
 154     {
 155       if (size_ == max_)
 156         remax (2*max_ + 1);
 157
 158       // T::operator=(T &) is called here. Safe to use with automatic
 159       // vars
 160       array_p_[size_++] = x;
 161     }
 162   /// remove and return last entry
 163     T pop()
 164     {
 165       assert (!empty());
 166       T l = top (0);
 167       set_size (size()-1);
 168       return l;
 169     }
 170   /// access last entry
 171     T& top (int j=0)
 172     {
 173       return (*this)[size_-j-1];
 174     }
 175   /// return last entry
 176     T top (int j=0) const
 177     {
 178       return (*this)[size_-j-1];
 179     }
 180
 181
 182   void swap (int i,int j)
 183     {
 184       T t ((*this)[i]);
 185       (*this)[i]=(*this)[j];
 186       (*this)[j]=t;
 187     }
 188   bool empty() const
 189     { return !size_; }
 190   void insert (T k, int j)
 191     {
 192       assert (j >=0 && j<= size_);
 193       set_size (size_+1);
 194       for (int i=size_-1; i > j; i--)
 195         array_p_[i] = array_p_[i-1];
 196       array_p_[j] = k;
 197     }
 198   /**
 199      remove  i-th element, and return it.
 200   */
 201   T get (int i)
 202     {
 203       T t = elem (i);
 204       del (i);
 205       return t;
 206     }
 207   void unordered_del (int i)
 208
 209     {
 210       elem (i) = top();
 211       set_size (size() -1);
 212     }
 213   void del (int i)
 214     {
 215       assert (i >=0&& i < size_);
 216       arrcpy (array_p_+i, array_p_+i+1, size_-i-1);
 217       size_--;
 218     }
 219   // quicksort.
 220   void sort (int (*compare)(T const&,T const&),
 221              int lower = -1, int upper = -1)
 222     {
 223       if (lower < 0)
 224         {
 225           lower = 0 ;
 226           upper = size()-1;
 227         }
 228       if (lower >= upper)
 229         return;
 230       swap (lower, (lower+upper)/2);
 231       int last = lower;
 232       for (int i= lower +1; i <= upper; i++)
 233         if (compare (array_p_[i], array_p_[lower]) < 0)
 234           swap (++last,i);
 235       swap (lower, last);
 236       sort (compare, lower, last-1);
 237       sort (compare, last+1, upper);
 238     }
 239   void concat (Array<T> const &src)
 240     {
 241       int s = size_;
 242       set_size (size_ + src.size_);
 243       arrcpy (array_p_+s,src.array_p_, src.size_);
 244     }
 245   Array<T> slice (int lower, int upper)
 246     {
 247       assert (lower >= 0 && lower <=upper&& upper <= size_);
 248       Array<T> r;
 249       int s =upper-lower;
 250       r.set_size (s);
 251       arrcpy (r.array_p_, array_p_  + lower, s);
 252       return r;
 253     }
 254   void reverse()
 255     {
 256       int h = size_/2;
 257       for (int i =0,j = size_-1; i < h; i++,j--)
 258         swap (i,j);
 259     }
 260 };
 261
 262 #endif