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=0; i < count ; i++)
  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 protected:
  38     /// maximum length of array.
  39     int max;
  40
  41     /// the data itself
  42     T *thearray;
  43
  44     /// stretch or shrink  array.
  45     void remax(int newmax) {
  46         T* newarr = new T[newmax];
  47         size_ = (newmax < size_) ? newmax : size_;
  48         arrcpy(newarr, thearray, size_);
  49
  50         delete[] thearray;
  51         thearray = newarr;
  52         max = newmax;
  53     }
  54     int size_;
  55
  56 public:
  57     /// check invariants
  58     void OK() const {
  59         assert(max >= size_ && size_ >=0);
  60         if (max) assert(thearray);
  61     }
  62     /** report the size_.
  63       @see {setsize_}
  64       */
  65     int size() const  { return size_; }
  66
  67     /// POST: size() == 0
  68     void clear() { size_ = 0; }
  69
  70     Array() { thearray = 0; max =0; size_ =0; }
  71
  72
  73     /** set the size_ to #s#.
  74       POST: size() == s.
  75     Warning: contents are unspecified */
  76     void set_size(int s) {
  77         if (s >= max) remax(s);
  78         size_ = s;
  79     }
  80
  81     ~Array() { delete[] thearray; }
  82
  83     /// return a  "new"ed copy of array
  84     T* copy_array() const {
  85         T* Tarray = new T[size_];
  86         arrcpy(Tarray, thearray, size_);
  87         return Tarray;
  88     }
  89     // depracated
  90     operator T* () const {
  91         return copy_array();
  92     }
  93     void operator=(Array const & src) {
  94         set_size (src.size_);
  95         arrcpy(thearray,src.thearray, size_);
  96     }
  97     Array(Array const & src) {
  98         thearray = src.copy_array();
  99         max = size_ = src.size_;
 100     }
 101
 102     /// tighten array size_.
 103     void precompute () { remax(size_); }
 104
 105
 106     /// access element
 107     T &operator[] (int i)  {
 108         return elem(i);
 109     }
 110     /// access element
 111     T const & operator[] (int i) const {
 112         return elem(i);
 113     }
 114     /// access element
 115     T &elem( int i) const {
 116         assert(i >=0&&i<size_);
 117         return ((T*)thearray)[i];
 118     }
 119
 120     /// add to the end of array
 121     void push(T x) {
 122         if (size_ == max)
 123             remax(2*max + 1);
 124
 125         // T::operator=(T &) is called here. Safe to use with automatic
 126         // vars
 127         thearray[size_++] = x;
 128     }
 129     /// remove and return last entry
 130     T pop() {
 131         assert(!empty());
 132         T l = top(0);
 133         set_size(size()-1);
 134         return l;
 135     }
 136     /// access last entry
 137     T& top(int j=0) {
 138         return (*this)[size_-j-1];
 139     }
 140      /// return last entry
 141     T top (int j=0) const {
 142         return (*this)[size_-j-1];
 143     }
 144
 145
 146     void swap (int i,int j) {
 147         T t((*this)[i]);
 148         (*this)[i]=(*this)[j];
 149         (*this)[j]=t;
 150     }
 151     bool empty() { return !size_; }
 152     void insert(T k, int j) {
 153         assert(j >=0 && j<= size_);
 154         set_size(size_+1);
 155         for (int i=size_-1; i > j; i--)
 156             thearray[i] = thearray[i-1];
 157         thearray[j] = k;
 158     }
 159     void del(int i) {
 160         assert(i >=0&& i < size_);
 161         arrcpy(thearray+i, thearray+i+1, size_-i-1);
 162         size_--;
 163     }
 164     // quicksort.
 165     void sort (int (*compare)( T const&,T const&),
 166                int lower = -1, int upper = -1 ) {
 167         if (lower < 0) {
 168             lower = 0 ;
 169             upper = size()-1;
 170         }
 171         if (lower >= upper)
 172             return;
 173         swap(lower, (lower+upper)/2);
 174         int last = lower;
 175         for (int i= lower +1; i <= upper; i++)
 176             if (compare(thearray[i], thearray[lower]) < 0 )
 177                 swap( ++last,i);
 178         swap(lower, last);
 179         sort(compare, lower, last-1);
 180         sort(compare, last+1, upper);
 181     }
 182     void concat(Array<T> const &src) {
 183         int s = size_;
 184         set_size(size_ + src.size_);
 185         arrcpy(thearray+s,src.thearray, src.size_);
 186     }
 187     Array<T> subvec(int lower, int upper) {
 188         assert(lower >= 0 && lower <=upper&& upper <= size_);
 189         Array<T> r;
 190         int s =upper-lower;
 191         r.set_size(s);
 192         arrcpy(r.thearray, thearray  + lower, s);
 193         return r;
 194     }
 195 };
 196
 197 #endif