/*
- (c) Han-Wen Nienhuys 1995,96,97
+ (c) 1995--2005 Han-Wen Nienhuys
Distributed under GNU GPL
*/
#ifndef ARRAY_H
#define ARRAY_H
-#include <assert.h>
+#include <cassert>
#ifndef INLINE
#define INLINE inline
#endif
/// copy a bare (C-)array from #src# to #dest# sized #count#
-template<class T> void arrcpy (T*dest, T*src, int count);
+template<class T> void arrcpy (T*dest, T const*src, int count);
/**
Scaleable array/stack template, for a type T with default constructor.
int max_;
/// the data itself
- T *array_p_;
+ T *array_;
/// stretch or shrink array.
void remax (int newmax)
{
T* newarr = new T[newmax];
size_ = (newmax < size_) ? newmax : size_;
- arrcpy (newarr, array_p_, size_);
+ arrcpy (newarr, array_, size_);
- delete[] array_p_;
- array_p_ = newarr;
+ delete[] array_;
+ array_ = newarr;
max_ = newmax;
}
int size_;
public:
/// check invariants
- void OK() const
- {
- assert (max_ >= size_ && size_ >=0);
- if (max_) assert (array_p_);
- }
+ void OK () const ;
/** report the size_.
@see
{setsize_}
*/
- int size() const
+
+ int size () const
{
return size_;
}
- /// POST: size() == 0
- void clear()
+ /// POST: size () == 0
+ void clear ()
{
size_ = 0;
}
Array (T *tp, int n)
{
- array_p_ = new T[n];
+ array_ = new T[n];
max_ =size_ = n;
- arrcpy (array_p_, tp, n);
+ arrcpy (array_, tp, n);
}
- Array()
- { array_p_ = 0; max_ =0; size_ =0; }
+ Array ()
+ { array_ = 0; max_ =0; size_ =0; }
// ugh, get around gcc 2.8.1 ice; see bezier.cc
Array (int i)
- {
- max_ = size_ = i;
- array_p_ = new T[i];
- }
+ {
+ max_ = size_ = i;
+ array_ = new T[i];
+ }
/** set the size_ to #s#.
- POST: size() == s.
+ POST: size () == s.
Warning: contents are unspecified */
void set_size (int s)
{
- if (s >= max_) remax (s);
+ if (s > max_) remax (s);
size_ = s;
}
- ~Array()
- { delete[] array_p_; }
+ ~Array ()
+ { delete[] array_; }
/// return a "new"ed copy of array
- T* copy_array() const
+ T* copys () const
{
T* Tarray = new T[size_];
- arrcpy (Tarray, array_p_, size_);
+ arrcpy (Tarray, array_, size_);
return Tarray;
}
- // depracated
- operator T*() const
+
+ T const *accesses () const
{
- return copy_array();
+ return array_;
}
- void operator=(Array const & src)
+ void operator= (Array const & src)
{
set_size (src.size_);
- arrcpy (array_p_,src.array_p_, size_);
+ arrcpy (array_,src.array_, size_);
}
Array (Array const & src)
{
- array_p_ = src.copy_array();
+ array_ = src.copys ();
max_ = size_ = src.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;
+ void tighten_maxsize () {
+ remax (size_);
}
+
+ T * remove_array ();
/// access element
T &operator[] (int i)
{
- return elem (i);
+ return elem_ref (i);
+ }
+ /// access element
+ T const & operator[] (int i) const
+ {
+ return elem_ref (i);
}
/// access element
- T const & operator[] (int i) const
+ T &elem_ref (int i) const
{
- return elem (i);
+ assert (i >=0 && i < size_);
+ return ((T*)array_)[i];
}
/// access element
- T &elem (int i) const
+ T elem (int i) const
{
- assert (i >=0&&i<size_);
- return ((T*)array_p_)[i];
+ return elem_ref (i);
}
/// add to the end of array
- void push (T x)
+ void push (T x)
{
if (size_ == max_)
remax (2*max_ + 1);
- // T::operator=(T &) is called here. Safe to use with automatic
+ // T::operator= (T &) is called here. Safe to use with automatic
// vars
- array_p_[size_++] = x;
+ array_[size_++] = x;
}
/// remove and return last entry
- T pop()
+ T pop ()
{
- assert (!empty());
+ assert (!is_empty ());
T l = top (0);
- set_size (size()-1);
+ set_size (size ()-1);
return l;
}
/// access last entry
- T& top (int j=0)
+ T& top (int j=0)
{
return (*this)[size_-j-1];
}
/// return last entry
- T top (int j=0) const
+ T top (int j=0) const
{
return (*this)[size_-j-1];
}
-
-
+
+ T& boundary (int dir, int idx)
+ {
+ assert (dir);
+ if (dir == 1)
+ return top (idx);
+ else
+ return elem_ref (idx);
+ }
+ T boundary (int dir, int idx) const
+ {
+ assert (dir);
+ if (dir == 1)
+ return top (idx);
+ else
+ return elem (idx);
+ }
void swap (int i,int j)
{
T t ((*this)[i]);
- (*this)[i]=(*this)[j];
- (*this)[j]=t;
+ (*this)[i]= (*this)[j];
+ (*this)[j]=t;
}
- bool empty() const
+ bool is_empty () const
{ return !size_; }
void insert (T k, int j);
return t;
}
void unordered_del (int i)
-
{
- elem (i) = top();
- set_size (size() -1);
+ elem_ref (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);
+ arrcpy (array_+i, array_+i+1, size_-i-1);
size_--;
}
// quicksort.
- void sort (int (*compare)(T const&,T const&),
+ void sort (int (*compare) (T const&,T const&),
int lower = -1, int upper = -1);
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;
+ arrcpy (array_+s,src.array_, src.size_);
}
- void reverse();
+ Array<T> slice (int lower, int upper) const;
+ void reverse ();
};
+template<class T>
+int default_compare (T const&a , T const&b)
+{
+ if (a < b)
+ return -1;
+ else if (a > b)
+ return 1;
+ else
+ return 0;
+}
+
#include "array.icc"
#endif