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() const { 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     /**
 160       remove  i-th element, and return it.
 161      */
 162     T get(int i) {
 163         T t = elem(i);
 164         del (i);
 165         return t;
 166     }
 167     void del(int i) {
 168         assert(i >=0&& i < size_);
 169         arrcpy(thearray+i, thearray+i+1, size_-i-1);
 170         size_--;
 171     }
 172     // quicksort.
 173     void sort (int (*compare)( T const&,T const&),
 174                int lower = -1, int upper = -1 ) {
 175         if (lower < 0) {
 176             lower = 0 ;
 177             upper = size()-1;
 178         }
 179         if (lower >= upper)
 180             return;
 181         swap(lower, (lower+upper)/2);
 182         int last = lower;
 183         for (int i= lower +1; i <= upper; i++)
 184             if (compare(thearray[i], thearray[lower]) < 0 )
 185                 swap( ++last,i);
 186         swap(lower, last);
 187         sort(compare, lower, last-1);
 188         sort(compare, last+1, upper);
 189     }
 190     void concat(Array<T> const &src) {
 191         int s = size_;
 192         set_size(size_ + src.size_);
 193         arrcpy(thearray+s,src.thearray, src.size_);
 194     }
 195     Array<T> subvec(int lower, int upper) {
 196         assert(lower >= 0 && lower <=upper&& upper <= size_);
 197         Array<T> r;
 198         int s =upper-lower;
 199         r.set_size(s);
 200         arrcpy(r.thearray, thearray  + lower, s);
 201         return r;
 202     }
 203     void reverse() {
 204         int h = size_/2;
 205         for (int i =0,j = size_-1; i < h; i++,j--)
 206             swap(i,j);
 207     }
 208 };
 209
 210 #endif