/// copy a bare (C-)array from #src# to #dest# sized #count#
template<class T>
inline void arrcpy (T*dest, T*src, int count) {
- for (int i_shadows_local=0; i_shadows_local < count ; i_shadows_local++)
- *dest++ = *src++;
+ for (int i_shadows_local=0; i_shadows_local < count ; i_shadows_local++)
+ *dest++ = *src++;
}
*/
template<class T>
-class Array {
+class Array
+{
protected:
- /// maximum length of array.
- int max;
-
- /// the data itself
- T *thearray;
-
- /// stretch or shrink array.
- void remax (int newmax) {
- T* newarr = new T[newmax];
- size_ = (newmax < size_) ? newmax : size_;
- arrcpy (newarr, thearray, size_);
+ /// maximum length of array.
+ int max_;
+
+ /// the data itself
+ T *array_p_;
+
+ /// stretch or shrink array.
+ void remax (int newmax)
+ {
+ T* newarr = new T[newmax];
+ size_ = (newmax < size_) ? newmax : size_;
+ arrcpy (newarr, array_p_, size_);
- delete[] thearray;
- thearray = newarr;
- max = newmax;
+ delete[] array_p_;
+ array_p_ = newarr;
+ max_ = newmax;
}
- int size_;
+ int size_;
public:
- /// check invariants
- void OK() const {
- assert (max >= size_ && size_ >=0);
- if (max) assert (thearray);
- }
- /** report the size_.
- @see {setsize_}
- */
- int size() const { return size_; }
+ /// check invariants
+ void OK() const
+ {
+ assert (max_ >= size_ && size_ >=0);
+ if (max_) assert (array_p_);
+ }
+ /** report the size_.
+ @see
+ {setsize_}
+ */
+ int size() const
+ { return size_; }
- /// POST: size() == 0
- void clear() { size_ = 0; }
+ /// POST: size() == 0
+ void clear()
+ { size_ = 0; }
- Array() { thearray = 0; max =0; size_ =0; }
+ Array()
+ { array_p_ = 0; max_ =0; size_ =0; }
- /** set the size_ to #s#.
+ /** set the size_ to #s#.
POST: size() == s.
- Warning: contents are unspecified */
- void set_size (int s) {
- if (s >= max) remax (s);
- size_ = s;
+ Warning: contents are unspecified */
+ void set_size (int s)
+ {
+ if (s >= max_) remax (s);
+ size_ = s;
}
- ~Array() { delete[] thearray; }
+ ~Array()
+ { delete[] array_p_; }
- /// return a "new"ed copy of array
- T* copy_array() const {
- T* Tarray = new T[size_];
- arrcpy (Tarray, thearray, size_);
- return Tarray;
+ /// return a "new"ed copy of array
+ T* copy_array() const
+ {
+ T* Tarray = new T[size_];
+ arrcpy (Tarray, array_p_, size_);
+ return Tarray;
}
- // depracated
- operator T*() const {
- return copy_array();
+ // depracated
+ operator T*() const
+ {
+ return copy_array();
}
- void operator=(Array const & src) {
- set_size (src.size_);
- arrcpy (thearray,src.thearray, size_);
+ void operator=(Array const & src)
+ {
+ set_size (src.size_);
+ arrcpy (array_p_,src.array_p_, size_);
}
- Array (Array const & src) {
- thearray = src.copy_array();
- max = size_ = src.size_;
+ Array (Array const & src)
+ {
+ array_p_ = src.copy_array();
+ max_ = size_ = src.size_;
}
- /// tighten array size_.
- void precompute() { remax (size_); }
+ /// tighten array size_.
+ void precompute() {
+ remax (size_);
+ }
+ T * remove_array_p () {
+ T * p = array_p_;
+ size_ = 0;
+ max_ = 0;
+ array_p_ =0;
+ return p;
+ }
+
+ /// access element
+ T &operator[] (int i)
+ {
+ return elem (i);
+ }
+ /// access element
+ T const & operator[] (int i) const
+ {
+ return elem (i);
+ }
+ /// access element
+ T &elem (int i) const
+ {
+ assert (i >=0&&i<size_);
+ return ((T*)array_p_)[i];
+ }
+
+ /// add to the end of array
+ void push (T x)
+ {
+ if (size_ == max_)
+ remax (2*max_ + 1);
+
+ // T::operator=(T &) is called here. Safe to use with automatic
+ // vars
+ array_p_[size_++] = x;
+ }
+ /// remove and return last entry
+ T pop()
+ {
+ assert (!empty());
+ T l = top (0);
+ set_size (size()-1);
+ return l;
+ }
+ /// access last entry
+ T& top (int j=0)
+ {
+ return (*this)[size_-j-1];
+ }
+ /// return last entry
+ T top (int j=0) const
+ {
+ return (*this)[size_-j-1];
+ }
+
- /// access element
- T &operator[] (int i) {
- return elem (i);
- }
- /// access element
- T const & operator[] (int i) const {
- return elem (i);
- }
- /// access element
- T &elem (int i) const {
- assert (i >=0&&i<size_);
- return ((T*)thearray)[i];
- }
-
- /// add to the end of array
- void push (T x) {
- if (size_ == max)
- remax (2*max + 1);
-
- // T::operator=(T &) is called here. Safe to use with automatic
- // vars
- thearray[size_++] = x;
- }
- /// remove and return last entry
- T pop() {
- assert (!empty());
- T l = top (0);
- set_size (size()-1);
- return l;
- }
- /// access last entry
- T& top (int j=0) {
- return (*this)[size_-j-1];
- }
- /// return last entry
- T top (int j=0) const {
- return (*this)[size_-j-1];
- }
-
-
- void swap (int i,int j) {
- T t ((*this)[i]);
- (*this)[i]=(*this)[j];
- (*this)[j]=t;
- }
- bool empty() const { return !size_; }
- void insert (T k, int j) {
- assert (j >=0 && j<= size_);
- set_size (size_+1);
- for (int i=size_-1; i > j; i--)
- thearray[i] = thearray[i-1];
- thearray[j] = k;
- }
- /**
- remove i-th element, and return it.
- */
- T get (int i) {
- T t = elem (i);
- del (i);
- return t;
- }
- void unordered_del (int i)
- {
- elem (i) = top();
- set_size (size() -1);
- }
- void del (int i) {
- assert (i >=0&& i < size_);
- arrcpy (thearray+i, thearray+i+1, size_-i-1);
- size_--;
- }
- // quicksort.
- void sort (int (*compare)(T const&,T const&),
- int lower = -1, int upper = -1) {
- if (lower < 0) {
- lower = 0 ;
- upper = size()-1;
+ void swap (int i,int j)
+ {
+ T t ((*this)[i]);
+ (*this)[i]=(*this)[j];
+ (*this)[j]=t;
+ }
+ bool empty() const
+ { return !size_; }
+ void insert (T k, int j)
+ {
+ assert (j >=0 && j<= size_);
+ set_size (size_+1);
+ for (int i=size_-1; i > j; i--)
+ array_p_[i] = array_p_[i-1];
+ array_p_[j] = k;
+ }
+ /**
+ remove i-th element, and return it.
+ */
+ T get (int i)
+ {
+ T t = elem (i);
+ del (i);
+ return t;
+ }
+ void unordered_del (int i)
+
+ {
+ elem (i) = top();
+ set_size (size() -1);
+ }
+ void del (int i)
+ {
+ assert (i >=0&& i < size_);
+ arrcpy (array_p_+i, array_p_+i+1, size_-i-1);
+ size_--;
+ }
+ // quicksort.
+ void sort (int (*compare)(T const&,T const&),
+ int lower = -1, int upper = -1)
+ {
+ if (lower < 0)
+ {
+ lower = 0 ;
+ upper = size()-1;
}
- if (lower >= upper)
- return;
- swap (lower, (lower+upper)/2);
- int last = lower;
- for (int i= lower +1; i <= upper; i++)
- if (compare (thearray[i], thearray[lower]) < 0)
- swap (++last,i);
- swap (lower, last);
- sort (compare, lower, last-1);
- sort (compare, last+1, upper);
- }
- void concat (Array<T> const &src) {
- int s = size_;
- set_size (size_ + src.size_);
- arrcpy (thearray+s,src.thearray, src.size_);
- }
- Array<T> slice (int lower, int upper) {
- assert (lower >= 0 && lower <=upper&& upper <= size_);
- Array<T> r;
- int s =upper-lower;
- r.set_size (s);
- arrcpy (r.thearray, thearray + lower, s);
- return r;
- }
- void reverse() {
- int h = size_/2;
- for (int i =0,j = size_-1; i < h; i++,j--)
- swap (i,j);
+ if (lower >= upper)
+ return;
+ swap (lower, (lower+upper)/2);
+ int last = lower;
+ for (int i= lower +1; i <= upper; i++)
+ if (compare (array_p_[i], array_p_[lower]) < 0)
+ swap (++last,i);
+ swap (lower, last);
+ sort (compare, lower, last-1);
+ sort (compare, last+1, upper);
+ }
+ void concat (Array<T> const &src)
+ {
+ int s = size_;
+ set_size (size_ + src.size_);
+ arrcpy (array_p_+s,src.array_p_, src.size_);
+ }
+ Array<T> slice (int lower, int upper)
+ {
+ assert (lower >= 0 && lower <=upper&& upper <= size_);
+ Array<T> r;
+ int s =upper-lower;
+ r.set_size (s);
+ arrcpy (r.array_p_, array_p_ + lower, s);
+ return r;
+ }
+ void reverse()
+ {
+ int h = size_/2;
+ for (int i =0,j = size_-1; i < h; i++,j--)
+ swap (i,j);
}
};