2 (c) Han-Wen Nienhuys 1995,96,97
4 Distributed under GNU GPL
11 /// copy a bare (C-)array from #src# to #dest# sized #count#
13 inline void arrcpy(T*dest, T*src, int count) {
14 for (int i=0; i < count ; i++)
20 Scaleable array/stack template, for a type T with default constructor.
23 This template implements a scaleable vector. With (or without) range
24 checking. The type T should have a default constructor. It is
25 best suited for simple types, such as int, double or String, it
26 provides a paranoidly safe replacement for the new T[int] construct.
28 You should \bf{never} store pointers to objects in an Array (since
29 the array may be relocated without the pointer knowing it).
31 It uses stack terminology, (push, pop, top), and can be used as a stack.
38 /// maximum length of array.
44 /// stretch or shrink array.
45 void remax(int newmax) {
46 T* newarr = new T[newmax];
47 size_ = (newmax < size_) ? newmax : size_;
48 arrcpy(newarr, thearray, size_);
59 assert(max >= size_ && size_ >=0);
60 if (max) assert(thearray);
65 int size() const { return size_; }
68 void clear() { size_ = 0; }
70 Array() { thearray = 0; max =0; size_ =0; }
73 /** set the size_ to #s#.
75 Warning: contents are unspecified */
76 void set_size(int s) {
77 if (s >= max) remax(s);
81 ~Array() { delete[] thearray; }
83 /// return a "new"ed copy of array
84 T* copy_array() const {
85 T* Tarray = new T[size_];
86 arrcpy(Tarray, thearray, size_);
90 operator T* () const {
93 void operator=(Array const & src) {
95 arrcpy(thearray,src.thearray, size_);
97 Array(Array const & src) {
98 thearray = src.copy_array();
99 max = size_ = src.size_;
102 /// tighten array size_.
103 void precompute () { remax(size_); }
107 T &operator[] (int i) {
111 T const & operator[] (int i) const {
115 T &elem( int i) const {
116 assert(i >=0&&i<size_);
117 return ((T*)thearray)[i];
120 /// add to the end of array
125 // T::operator=(T &) is called here. Safe to use with automatic
127 thearray[size_++] = x;
129 /// remove and return last entry
136 /// access last entry
138 return (*this)[size_-j-1];
140 /// return last entry
141 T top (int j=0) const {
142 return (*this)[size_-j-1];
146 void swap (int i,int j) {
148 (*this)[i]=(*this)[j];
151 bool empty() { return !size_; }
152 void insert(T k, int j) {
153 assert(j >=0 && j<= size_);
155 for (int i=size_-1; i > j; i--)
156 thearray[i] = thearray[i-1];
160 assert(i >=0&& i < size_);
161 arrcpy(thearray+i, thearray+i+1, size_-i-1);
165 void sort (int (*compare)( T const&,T const&),
166 int lower = -1, int upper = -1 ) {
173 swap(lower, (lower+upper)/2);
175 for (int i= lower +1; i <= upper; i++)
176 if (compare(thearray[i], thearray[lower]) < 0 )
179 sort(compare, lower, last-1);
180 sort(compare, last+1, upper);
182 void concat(Array<T> const &src) {
184 set_size(size_ + src.size_);
185 arrcpy(thearray+s,src.thearray, src.size_);
187 Array<T> subvec(int lower, int upper) {
188 assert(lower >= 0 && lower <=upper&& upper <= size_);
192 arrcpy(r.thearray, thearray + lower, s);