flower/include/array.hh

   1 /*
   2   (c) 1995--2005 Han-Wen Nienhuys
   3
   4   Distributed under GNU GPL
   5 */
   6
   7 #ifndef ARRAY_H
   8 #define ARRAY_H
   9 #include <cassert>
  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 const*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_;
  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_, size_);
  50
  51       delete[] array_;
  52       array_ = 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_ = new T[n];
  79       max_ =size_ = n;
  80       arrcpy (array_, tp, n);
  81     }
  82
  83   Array ()
  84     { array_ = 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_ = 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_; }
 105
 106   /// return a  "new"ed copy of array
 107   T* copys () const
 108     {
 109       T* Tarray = new T[size_];
 110       arrcpy (Tarray, array_, size_);
 111       return Tarray;
 112     }
 113
 114   T const *accesses () const
 115     {
 116       return array_;
 117     }
 118   void operator= (Array const & src)
 119     {
 120       set_size (src.size_);
 121       arrcpy (array_,src.array_, size_);
 122     }
 123   Array (Array const & src)
 124     {
 125       array_ = src.copys ();
 126       max_ = size_ = src.size_;
 127     }
 128
 129   /// tighten array size_.
 130   void tighten_maxsize ()     {
 131     remax (size_);
 132   }
 133
 134   T * remove_array ();
 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_)[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_[size_++] = x;
 167     }
 168   /// remove and return last entry
 169   T pop ()
 170     {
 171       assert (!is_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   T& boundary (int dir, int idx)
 188     {
 189       assert (dir);
 190       if (dir == 1)
 191         return top (idx);
 192       else
 193         return elem_ref (idx);
 194     }
 195   T boundary (int dir, int idx) const
 196     {
 197       assert (dir);
 198       if (dir == 1)
 199         return top (idx);
 200       else
 201         return elem (idx);
 202     }
 203   void swap (int i,int j)
 204     {
 205       T t ((*this)[i]);
 206  (*this)[i]= (*this)[j];
 207  (*this)[j]=t;
 208     }
 209   bool is_empty () const
 210     { return !size_; }
 211
 212   void insert (T k, int j);
 213   /**
 214      remove  i-th element, and return it.
 215   */
 216   T get (int i)
 217     {
 218       T t = elem (i);
 219       del (i);
 220       return t;
 221     }
 222   void unordered_del (int i)
 223     {
 224       elem_ref (i) = top ();
 225       set_size (size () -1);
 226     }
 227   void del (int i)
 228     {
 229       assert (i >=0&& i < size_);
 230       arrcpy (array_+i, array_+i+1, size_-i-1);
 231       size_--;
 232     }
 233   // quicksort.
 234   void sort (int (*compare) (T const&,T const&),
 235              int lower = -1, int upper = -1);
 236   void concat (Array<T> const &src)
 237     {
 238       int s = size_;
 239       set_size (size_ + src.size_);
 240       arrcpy (array_+s,src.array_, src.size_);
 241     }
 242   Array<T> slice (int lower, int upper) const;
 243   void reverse ();
 244 };
 245
 246 template<class T>
 247 int default_compare (T const&a , T const&b)
 248 {
 249   if (a < b)
 250     return -1;
 251   else if (a > b)
 252     return 1;
 253   else
 254     return 0;
 255 }
 256
 257 #include "array.icc"
 258
 259 #endif