flower/vray.hh

   1 /*
   2   (c) Han-Wen Nienhuys 1995,96
   3
   4   Distributed under GNU GPL
   5 */
   6
   7 #ifndef SVEC_H
   8 #define SVEC_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 template, for T with def ctor.
  19 template<class T>
  20 class svec {
  21 protected:
  22
  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     int sz() const  { return size; }
  48
  49     /// POST: sz() == 0
  50     void clear() { size = 0; }
  51
  52     svec() { thearray = 0; max =0; size =0; }
  53     /// set the size to #s#
  54     void set_size(int s) {
  55         if (s >= max) remax(s);
  56         size = s;
  57     }
  58     /** POST: sz() == s.
  59     Warning: contents are unspecified */
  60
  61     ~svec() { delete[] thearray; }
  62
  63     /// return a  "new"ed copy of array
  64     T* copy_array() const {
  65         T* Tarray = new T[size];
  66         arrcpy(Tarray, thearray, size);
  67         return Tarray;
  68     }
  69     // depracated
  70     operator T* () const {
  71         return copy_array();
  72     }
  73     void operator=(svec const & src) {
  74         set_size (src.size);
  75         arrcpy(thearray,src.thearray, size);
  76     }
  77     svec(const svec & src) {
  78         thearray = src.copy_array();
  79         max = size = src.size;
  80     }
  81
  82     /// tighten array size.
  83     void precompute () { remax(size); }
  84
  85     /// this makes svec behave like an array
  86     T &operator[] (const int i) const {
  87         assert(i >=0&&i<size);
  88         return ((T*)thearray)[i];
  89     }
  90
  91     /// add to the end of array
  92     void add(T x) {
  93         if (size == max)
  94             remax(2*max + 1);
  95
  96         // T::operator=(T &) is called here. Safe to use with automatic
  97         // vars
  98         thearray[size++] = x;
  99     }
 100
 101     /// junk last entry.
 102     void pop() { size -- ; }
 103
 104     /// return last entry
 105     T& last(int j=0) {
 106         return (*this)[size-j-1];
 107     }
 108     void swap (int i,int j) {
 109         T t((*this)[i]);
 110         (*this)[i]=(*this)[j];
 111         (*this)[j]=t;
 112     }
 113     bool empty() { return !size; }
 114     void insert(T&k, int j) {
 115         assert(j >=0 && j<= size);
 116         set_size(size+1);
 117         for (int i=size-1; i > j; i--)
 118             thearray[i] = thearray[i-1];
 119         thearray[j] = k;
 120     }
 121     void del(int i) {
 122         assert(i >=0&& i < size);
 123         arrcpy(thearray+i, thearray+i+1, size-i-1);
 124         size--;
 125     }
 126     // quicksort.
 127     void sort (int (*compare)(T& , T& ),
 128                int lower = -1, int upper = -1 ) {
 129         if (lower < 0) {
 130             lower = 0 ;
 131             upper = sz();
 132         }
 133         if (lower >= upper)
 134             return;
 135         swap(lower, (lower+upper)/2);
 136         int last = lower;
 137         for (int i= lower +1; i <= upper; i++)
 138             if (compare(thearray[i], thearray[lower]) < 0 )
 139                 swap( ++last,i);
 140         swap(lower, last);
 141         sort(compare, lower, last-1);
 142         sort(compare, last+1, lower);
 143     }
 144     void concat(svec<T> const &src) {
 145         int s = size;
 146         set_size(size + src.size);
 147         arrcpy(thearray+s,src.thearray, src.size);
 148     }
 149 };
 150 /**
 151
 152   This template implements a scaleable vector. With (or without) range
 153   checking. It may be flaky for objects with complicated con- and
 154   destructors. The type T should have a default constructor. It is
 155   best suited for simple types, such as int, double or String
 156
 157   */
 158
 159 /// A simple stack based on svec.
 160 template<class T>
 161 class sstack : svec<T> {
 162  public:
 163     T top() { return last(); }
 164     T pop() {
 165         assert(!empty());
 166         T l = last();
 167         svec<T>::pop();
 168         return l;
 169     }
 170     void push(T l) { add(l); }
 171     bool empty() { return svec<T>::empty(); }
 172 };
 173 /**
 174   Same as for #svec# goes here.
 175 */
 176 #endif