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