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