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     {
  70       return size_;
  71     }
  72
  73   /// POST: size() == 0
  74   void clear()
  75     {
  76       size_ = 0;
  77     }
  78
  79   Array (T *tp, int n)
  80     {
  81       array_p_ = new T[n];
  82       max_ =size_ = n;
  83       arrcpy (array_p_, tp, n);
  84     }
  85
  86   Array()
  87     { array_p_ = 0; max_ =0; size_ =0; }
  88
  89   // ugh, get around gcc 2.8.1 ice; see bezier.cc
  90   Array (int i)
  91   {
  92     max_ = size_ = i;
  93     array_p_ = new T[i];
  94   }
  95
  96
  97   /** set the size_ to #s#.
  98       POST: size() == s.
  99       Warning: contents are unspecified */
 100   void set_size (int s)
 101     {
 102       if (s >= max_) remax (s);
 103       size_ = s;
 104     }
 105
 106   ~Array()
 107     { delete[] array_p_; }
 108
 109   /// return a  "new"ed copy of array
 110     T* copy_array() const
 111     {
 112       T* Tarray = new T[size_];
 113       arrcpy (Tarray, array_p_, size_);
 114       return Tarray;
 115     }
 116   // depracated
 117   operator T*() const
 118     {
 119       return copy_array();
 120     }
 121   void operator=(Array const & src)
 122     {
 123       set_size (src.size_);
 124       arrcpy (array_p_,src.array_p_, size_);
 125     }
 126   Array (Array const & src)
 127     {
 128       array_p_ = src.copy_array();
 129       max_ = size_ = src.size_;
 130     }
 131
 132   /// tighten array size_.
 133     void precompute()     {
 134       remax (size_);
 135     }
 136
 137   T * remove_array_p () {
 138     T * p = array_p_;
 139     size_ = 0;
 140     max_ = 0;
 141     array_p_ =0;
 142     return p;
 143   }
 144
 145   /// access element
 146   T &operator[] (int i)
 147     {
 148       return elem (i);
 149     }
 150   /// access element
 151     T const & operator[] (int i) const
 152     {
 153       return elem (i);
 154     }
 155   /// access element
 156     T &elem (int i) const
 157     {
 158       assert (i >=0&&i<size_);
 159       return ((T*)array_p_)[i];
 160     }
 161
 162   /// add to the end of array
 163     void push (T x)
 164     {
 165       if (size_ == max_)
 166         remax (2*max_ + 1);
 167
 168       // T::operator=(T &) is called here. Safe to use with automatic
 169       // vars
 170       array_p_[size_++] = x;
 171     }
 172   /// remove and return last entry
 173     T pop()
 174     {
 175       assert (!empty());
 176       T l = top (0);
 177       set_size (size()-1);
 178       return l;
 179     }
 180   /// access last entry
 181     T& top (int j=0)
 182     {
 183       return (*this)[size_-j-1];
 184     }
 185   /// return last entry
 186     T top (int j=0) const
 187     {
 188       return (*this)[size_-j-1];
 189     }
 190
 191
 192   void swap (int i,int j)
 193     {
 194       T t ((*this)[i]);
 195       (*this)[i]=(*this)[j];
 196       (*this)[j]=t;
 197     }
 198   bool empty() const
 199     { return !size_; }
 200
 201   void insert (T k, int j);
 202   /**
 203      remove  i-th element, and return it.
 204   */
 205   T get (int i)
 206     {
 207       T t = elem (i);
 208       del (i);
 209       return t;
 210     }
 211   void unordered_del (int i)
 212
 213     {
 214       elem (i) = top();
 215       set_size (size() -1);
 216     }
 217   void del (int i)
 218     {
 219       assert (i >=0&& i < size_);
 220       arrcpy (array_p_+i, array_p_+i+1, size_-i-1);
 221       size_--;
 222     }
 223   // quicksort.
 224   void sort (int (*compare)(T const&,T const&),
 225              int lower = -1, int upper = -1);
 226   void concat (Array<T> const &src)
 227     {
 228       int s = size_;
 229       set_size (size_ + src.size_);
 230       arrcpy (array_p_+s,src.array_p_, src.size_);
 231     }
 232   Array<T> slice (int lower, int upper)
 233     {
 234       assert (lower >= 0 && lower <=upper&& upper <= size_);
 235       Array<T> r;
 236       int s =upper-lower;
 237       r.set_size (s);
 238       arrcpy (r.array_p_, array_p_  + lower, s);
 239       return r;
 240     }
 241   void reverse();
 242 };
 243
 244 #include "array.icc"
 245
 246 #endif