flower/include/varray.hh

   1 /*
   2   (c) Han-Wen Nienhuys 1995,96
   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. It may be flaky for objects with complicated con- and
  25   destructors. The type T should have a default constructor. It is
  26   best suited for simple types, such as int, double or String, it
  27   provides a paranoidly safe replacement for the new T[int] construct.
  28
  29   It uses stack terminology, (push, pop, top), and  can be used as a stack.
  30
  31
  32   */
  33 template<class T>
  34 class Array {
  35 protected:
  36     /// maximum length of array.
  37     int max;
  38
  39     /// the data itself
  40     T *thearray;
  41
  42     /// stretch or shrink  array.
  43     void remax(int newmax) {
  44         T* newarr = new T[newmax];
  45         size_ = (newmax < size_) ? newmax : size_;
  46         arrcpy(newarr, thearray, size_);
  47
  48         delete[] thearray;
  49         thearray = newarr;
  50         max = newmax;
  51     }
  52     int size_;
  53
  54 public:
  55     /// check invariants
  56     void OK() const {
  57         assert(max >= size_ && size_ >=0);
  58         if (max) assert(thearray);
  59     }
  60     /** report the size_.
  61       @see {setsize_}
  62       */
  63     int size() const  { return size_; }
  64
  65     /// POST: size() == 0
  66     void clear() { size_ = 0; }
  67
  68     Array() { thearray = 0; max =0; size_ =0; }
  69
  70
  71     /** set the size_ to #s#.
  72       POST: size() == s.
  73     Warning: contents are unspecified */
  74     void set_size(int s) {
  75         if (s >= max) remax(s);
  76         size_ = s;
  77     }
  78
  79     ~Array() { delete[] thearray; }
  80
  81     /// return a  "new"ed copy of array
  82     T* copy_array() const {
  83         T* Tarray = new T[size_];
  84         arrcpy(Tarray, thearray, size_);
  85         return Tarray;
  86     }
  87     // depracated
  88     operator T* () const {
  89         return copy_array();
  90     }
  91     void operator=(Array const & src) {
  92         set_size (src.size_);
  93         arrcpy(thearray,src.thearray, size_);
  94     }
  95     Array(Array const & src) {
  96         thearray = src.copy_array();
  97         max = size_ = src.size_;
  98     }
  99
 100     /// tighten array size_.
 101     void precompute () { remax(size_); }
 102
 103     /// this makes Array behave like an array
 104     T &operator[] (const int i) const {
 105         assert(i >=0&&i<size_);
 106         return ((T*)thearray)[i];
 107     }
 108
 109     /// add to the end of array
 110     void push(T x) {
 111         if (size_ == max)
 112             remax(2*max + 1);
 113
 114         // T::operator=(T &) is called here. Safe to use with automatic
 115         // vars
 116         thearray[size_++] = x;
 117     }
 118     /// remove and return last entry
 119     T pop() {
 120         assert(!empty());
 121         T l = top(0);
 122         set_size(size()-1);
 123         return l;
 124     }
 125     /// access last entry
 126     T& top(int j=0) {
 127         return (*this)[size_-j-1];
 128     }
 129      /// return last entry
 130     T top (int j=0) const {
 131         return (*this)[size_-j-1];
 132     }
 133
 134
 135     void swap (int i,int j) {
 136         T t((*this)[i]);
 137         (*this)[i]=(*this)[j];
 138         (*this)[j]=t;
 139     }
 140     bool empty() { return !size_; }
 141     void insert(T k, int j) {
 142         assert(j >=0 && j<= size_);
 143         set_size(size_+1);
 144         for (int i=size_-1; i > j; i--)
 145             thearray[i] = thearray[i-1];
 146         thearray[j] = k;
 147     }
 148     void del(int i) {
 149         assert(i >=0&& i < size_);
 150         arrcpy(thearray+i, thearray+i+1, size_-i-1);
 151         size_--;
 152     }
 153     // quicksort.
 154     void sort (int (*compare)( T const&,T const&),
 155                int lower = -1, int upper = -1 ) {
 156         if (lower < 0) {
 157             lower = 0 ;
 158             upper = size()-1;
 159         }
 160         if (lower >= upper)
 161             return;
 162         swap(lower, (lower+upper)/2);
 163         int last = lower;
 164         for (int i= lower +1; i <= upper; i++)
 165             if (compare(thearray[i], thearray[lower]) < 0 )
 166                 swap( ++last,i);
 167         swap(lower, last);
 168         sort(compare, lower, last-1);
 169         sort(compare, last+1, upper);
 170     }
 171     void concat(Array<T> const &src) {
 172         int s = size_;
 173         set_size(size_ + src.size_);
 174         arrcpy(thearray+s,src.thearray, src.size_);
 175     }
 176     Array<T> subvec(int lower, int upper) {
 177         assert(lower >= 0 && lower <=upper&& upper <= size_);
 178         Array<T> r;
 179         int s =upper-lower;
 180         r.set_size(s);
 181         arrcpy(r.thearray, thearray  + lower, s);
 182         return r;
 183     }
 184 };
 185
 186 #endif