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