flower/include/array.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 #ifndef INLINE
  12 #define INLINE inline
  13 #endif
  14
  15 /// copy a bare (C-)array from #src# to #dest# sized  #count#
  16 template<class T> void arrcpy (T*dest, T*src, int count);
  17
  18 /**
  19   Scaleable array/stack template, for a type T with default constructor.
  20
  21
  22   This template implements a scaleable vector. With (or without) range
  23   checking. The type T should have a default constructor. It is
  24   best suited for simple types, such as int, double or String, it
  25   provides a paranoidly safe replacement for the new T[int] construct.
  26
  27   You should \bf{never} store pointers to objects in an Array (since
  28   the array may be relocated without the pointer knowing it).
  29
  30   It uses stack terminology, (push, pop, top), and  can be used as a stack.
  31
  32
  33   */
  34 template<class T>
  35 class Array
  36 {
  37 protected:
  38   /// maximum length of array.
  39   int max_;
  40
  41   /// the data itself
  42   T *array_p_;
  43
  44   /// stretch or shrink  array.
  45   void remax (int newmax)
  46     {
  47       T* newarr = new T[newmax];
  48       size_ = (newmax < size_) ? newmax : size_;
  49       arrcpy (newarr, array_p_, size_);
  50
  51       delete[] array_p_;
  52       array_p_ = newarr;
  53       max_ = newmax;
  54     }
  55   int size_;
  56
  57 public:
  58   /// check invariants
  59   void OK() const
  60     {
  61       assert (max_ >= size_ && size_ >=0);
  62       if (max_) assert (array_p_);
  63     }
  64   /** report the size_.
  65       @see
  66       {setsize_}
  67   */
  68   int size() const
  69     { return size_; }
  70
  71   /// POST: size() == 0
  72     void clear()
  73     { size_ = 0; }
  74
  75   Array()
  76     { array_p_ = 0; max_ =0; size_ =0; }
  77
  78   // ugh, get around gcc 2.8.1 ice; see bezier.cc
  79   Array (int i)
  80   {
  81     max_ = size_ = i;
  82     array_p_ = new T[i];
  83   }
  84
  85
  86   /** set the size_ to #s#.
  87       POST: size() == s.
  88       Warning: contents are unspecified */
  89   void set_size (int s)
  90     {
  91       if (s >= max_) remax (s);
  92       size_ = s;
  93     }
  94
  95   ~Array()
  96     { delete[] array_p_; }
  97
  98   /// return a  "new"ed copy of array
  99     T* copy_array() const
 100     {
 101       T* Tarray = new T[size_];
 102       arrcpy (Tarray, array_p_, size_);
 103       return Tarray;
 104     }
 105   // depracated
 106   operator T*() const
 107     {
 108       return copy_array();
 109     }
 110   void operator=(Array const & src)
 111     {
 112       set_size (src.size_);
 113       arrcpy (array_p_,src.array_p_, size_);
 114     }
 115   Array (Array const & src)
 116     {
 117       array_p_ = src.copy_array();
 118       max_ = size_ = src.size_;
 119     }
 120
 121   /// tighten array size_.
 122     void precompute()     {
 123       remax (size_);
 124     }
 125
 126   T * remove_array_p () {
 127     T * p = array_p_;
 128     size_ = 0;
 129     max_ = 0;
 130     array_p_ =0;
 131     return p;
 132   }
 133
 134   /// access element
 135   T &operator[] (int i)
 136     {
 137       return elem (i);
 138     }
 139   /// access element
 140     T const & operator[] (int i) const
 141     {
 142       return elem (i);
 143     }
 144   /// access element
 145     T &elem (int i) const
 146     {
 147       assert (i >=0&&i<size_);
 148       return ((T*)array_p_)[i];
 149     }
 150
 151   /// add to the end of array
 152     void push (T x)
 153     {
 154       if (size_ == max_)
 155         remax (2*max_ + 1);
 156
 157       // T::operator=(T &) is called here. Safe to use with automatic
 158       // vars
 159       array_p_[size_++] = x;
 160     }
 161   /// remove and return last entry
 162     T pop()
 163     {
 164       assert (!empty());
 165       T l = top (0);
 166       set_size (size()-1);
 167       return l;
 168     }
 169   /// access last entry
 170     T& top (int j=0)
 171     {
 172       return (*this)[size_-j-1];
 173     }
 174   /// return last entry
 175     T top (int j=0) const
 176     {
 177       return (*this)[size_-j-1];
 178     }
 179
 180
 181   void swap (int i,int j)
 182     {
 183       T t ((*this)[i]);
 184       (*this)[i]=(*this)[j];
 185       (*this)[j]=t;
 186     }
 187   bool empty() const
 188     { return !size_; }
 189
 190   void insert (T k, int j);
 191   /**
 192      remove  i-th element, and return it.
 193   */
 194   T get (int i)
 195     {
 196       T t = elem (i);
 197       del (i);
 198       return t;
 199     }
 200   void unordered_del (int i)
 201
 202     {
 203       elem (i) = top();
 204       set_size (size() -1);
 205     }
 206   void del (int i)
 207     {
 208       assert (i >=0&& i < size_);
 209       arrcpy (array_p_+i, array_p_+i+1, size_-i-1);
 210       size_--;
 211     }
 212   // quicksort.
 213   void sort (int (*compare)(T const&,T const&),
 214              int lower = -1, int upper = -1);
 215   void concat (Array<T> const &src)
 216     {
 217       int s = size_;
 218       set_size (size_ + src.size_);
 219       arrcpy (array_p_+s,src.array_p_, src.size_);
 220     }
 221   Array<T> slice (int lower, int upper)
 222     {
 223       assert (lower >= 0 && lower <=upper&& upper <= size_);
 224       Array<T> r;
 225       int s =upper-lower;
 226       r.set_size (s);
 227       arrcpy (r.array_p_, array_p_  + lower, s);
 228       return r;
 229     }
 230   void reverse();
 231 };
 232
 233 #include "array.icc"
 234
 235 #endif