2 * Copyright 2002, 2006 Adrian Thurston <thurston@complang.org>
5 /* This file is part of Aapl.
7 * Aapl is free software; you can redistribute it and/or modify it under the
8 * terms of the GNU Lesser General Public License as published by the Free
9 * Software Foundation; either version 2.1 of the License, or (at your option)
12 * Aapl is distributed in the hope that it will be useful, but WITHOUT ANY
13 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
14 * FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for
17 * You should have received a copy of the GNU Lesser General Public License
18 * along with Aapl; if not, write to the Free Software Foundation, Inc., 59
19 * Temple Place, Suite 330, Boston, MA 02111-1307 USA
22 #ifndef _AAPL_VECTOR_H
23 #define _AAPL_VECTOR_H
41 * \brief Dynamic array.
43 * This is typical vector implementation. It is a dynamic array that can be
44 * used to contain complex data structures that have constructors and
45 * destructors as well as simple types such as integers and pointers.
47 * Vector supports inserting, overwriting, and removing single or multiple
48 * elements at once. Constructors and destructors are called wherever
49 * appropriate. For example, before an element is overwritten, it's
50 * destructor is called.
52 * Vector provides automatic resizing of allocated memory as needed and offers
53 * different allocation schemes for controlling how the automatic allocation
54 * is done. Two senses of the the length of the data is maintained: the
55 * amount of raw memory allocated to the vector and the number of actual
56 * elements in the vector. The various allocation schemes control how the
57 * allocated space is changed in relation to the number of elements in the
60 * \include ex_vector.cpp
65 template < class T, class Resize = ResizeExpn > class Vector
66 : public Table<T>, public Resize
69 typedef Table<T> BaseTable;
73 * \brief Initialize an empty vector with no space allocated.
75 * If a linear resizer is used, the step defaults to 256 units of T. For a
76 * runtime vector both up and down allocation schemes default to
82 * \brief Create a vector that contains an initial element.
84 * The vector becomes one element in length. The element's copy
85 * constructor is used to place the value in the vector.
87 Vector(const T &val) { setAs(&val, 1); }
90 * \brief Create a vector that contains an array of elements.
92 * The vector becomes len elements in length. Copy constructors are used
93 * to place the new elements in the vector.
95 Vector(const T *val, long len) { setAs(val, len); }
98 Vector( const Vector &v );
100 /* Free all mem used by the vector. */
101 ~Vector() { empty(); }
103 /* Delete all items. */
106 /* Abandon the contents of the vector without deleteing. */
109 /* Transfers the elements of another vector into this vector. First emptys
110 * the current vector. */
111 void transfer( Vector &v );
113 /* Perform a deep copy of another vector into this vector. */
114 Vector &operator=( const Vector &v );
119 * \brief Insert one element at position pos.
121 * Elements in the vector from pos onward are shifted one space to the
122 * right. The copy constructor is used to place the element into this
123 * vector. If pos is greater than the length of the vector then undefined
124 * behaviour results. If pos is negative then it is treated as an offset
125 * relative to the length of the vector.
127 void insert(long pos, const T &val) { insert(pos, &val, 1); }
129 /* Insert an array of values. */
130 void insert(long pos, const T *val, long len);
133 * \brief Insert all the elements from another vector at position pos.
135 * Elements in this vector from pos onward are shifted v.tabLen spaces to
136 * the right. The element's copy constructor is used to copy the items
137 * into this vector. The other vector is left unchanged. If pos is off the
138 * end of the vector, then undefined behaviour results. If pos is negative
139 * then it is treated as an offset relative to the length of the vector.
140 * Equivalent to vector.insert(pos, other.data, other.tabLen).
142 void insert(long pos, const Vector &v) { insert(pos, v.data, v.tabLen); }
144 /* Insert len copies of val into the vector. */
145 void insertDup(long pos, const T &val, long len);
148 * \brief Insert one new element using the default constrcutor.
150 * Elements in the vector from pos onward are shifted one space to the
151 * right. The default constructor is used to init the new element. If pos
152 * is greater than the length of the vector then undefined behaviour
153 * results. If pos is negative then it is treated as an offset relative to
154 * the length of the vector.
156 void insertNew(long pos) { insertNew(pos, 1); }
158 /* Insert len new items using default constructor. */
159 void insertNew(long pos, long len);
164 * \brief Remove one element at position pos.
166 * The element's destructor is called. Elements to the right of pos are
167 * shifted one space to the left to take up the free space. If pos is greater
168 * than or equal to the length of the vector then undefined behavior results.
169 * If pos is negative then it is treated as an offset relative to the length
172 void remove(long pos) { remove(pos, 1); }
174 /* Delete a number of elements. */
175 void remove(long pos, long len);
180 * \brief Replace one element at position pos.
182 * If there is an existing element at position pos (if pos is less than
183 * the length of the vector) then its destructor is called before the
184 * space is used. The copy constructor is used to place the element into
185 * the vector. If pos is greater than the length of the vector then
186 * undefined behaviour results. If pos is negative then it is treated as
187 * an offset relative to the length of the vector.
189 void replace(long pos, const T &val) { replace(pos, &val, 1); }
191 /* Replace with an array of values. */
192 void replace(long pos, const T *val, long len);
195 * \brief Replace at position pos with all the elements of another vector.
197 * Replace at position pos with all the elements of another vector. The
198 * other vector is left unchanged. If there are existing elements at the
199 * positions to be replaced, then destructors are called before the space
200 * is used. Copy constructors are used to place the elements into this
201 * vector. It is allowable for the pos and length of the other vector to
202 * specify a replacement that overwrites existing elements and creates new
203 * ones. If pos is greater than the length of the vector then undefined
204 * behaviour results. If pos is negative, then it is treated as an offset
205 * relative to the length of the vector.
207 void replace(long pos, const Vector &v) { replace(pos, v.data, v.tabLen); }
209 /* Replace len items with len copies of val. */
210 void replaceDup(long pos, const T &val, long len);
213 * \brief Replace at position pos with one new element.
215 * If there is an existing element at the position to be replaced (pos is
216 * less than the length of the vector) then the element's destructor is
217 * called before the space is used. The default constructor is used to
218 * initialize the new element. If pos is greater than the length of the
219 * vector then undefined behaviour results. If pos is negative, then it is
220 * treated as an offset relative to the length of the vector.
222 void replaceNew(long pos) { replaceNew(pos, 1); }
224 /* Replace len items at pos with newly constructed objects. */
225 void replaceNew(long pos, long len);
230 * \brief Set the contents of the vector to be val exactly.
232 * The vector becomes one element in length. Destructors are called on any
233 * existing elements in the vector. The element's copy constructor is used
234 * to place the val in the vector.
236 void setAs(const T &val) { setAs(&val, 1); }
238 /* Set to the contents of an array. */
239 void setAs(const T *val, long len);
242 * \brief Set the vector to exactly the contents of another vector.
244 * The vector becomes v.tabLen elements in length. Destructors are called
245 * on any existing elements. Copy constructors are used to place the new
246 * elements in the vector.
248 void setAs(const Vector &v) { setAs(v.data, v.tabLen); }
250 /* Set as len copies of item. */
251 void setAsDup(const T &item, long len);
254 * \brief Set the vector to exactly one new item.
256 * The vector becomes one element in length. Destructors are called on any
257 * existing elements in the vector. The default constructor is used to
260 void setAsNew() { setAsNew(1); }
262 /* Set as newly constructed objects using the default constructor. */
263 void setAsNew(long len);
268 * \brief Append one elment to the end of the vector.
270 * Copy constructor is used to place the element in the vector.
272 void append(const T &val) { replace(BaseTable::tabLen, &val, 1); }
275 * \brief Append len elements to the end of the vector.
277 * Copy constructors are used to place the elements in the vector.
279 void append(const T *val, long len) { replace(BaseTable::tabLen, val, len); }
282 * \brief Append the contents of another vector.
284 * The other vector is left unchanged. Copy constructors are used to place the
285 * elements in the vector.
287 void append(const Vector &v) { replace(BaseTable::tabLen, v.data, v.tabLen); }
290 * \brief Append len copies of item.
292 * The copy constructor is used to place the item in the vector.
294 void appendDup(const T &item, long len) { replaceDup(BaseTable::tabLen, item, len); }
297 * \brief Append a single newly created item.
299 * The new element is initialized with the default constructor.
301 void appendNew() { replaceNew(BaseTable::tabLen, 1); }
304 * \brief Append len newly created items.
306 * The new elements are initialized with the default constructor.
308 void appendNew(long len) { replaceNew(BaseTable::tabLen, len); }
312 /** \fn Vector::prepend(const T &val)
313 * \brief Prepend one elment to the front of the vector.
315 * Copy constructor is used to place the element in the vector.
317 void prepend(const T &val) { insert(0, &val, 1); }
320 * \brief Prepend len elements to the front of the vector.
322 * Copy constructors are used to place the elements in the vector.
324 void prepend(const T *val, long len) { insert(0, val, len); }
327 * \brief Prepend the contents of another vector.
329 * The other vector is left unchanged. Copy constructors are used to place the
330 * elements in the vector.
332 void prepend(const Vector &v) { insert(0, v.data, v.tabLen); }
335 * \brief Prepend len copies of item.
337 * The copy constructor is used to place the item in the vector.
339 void prependDup(const T &item, long len) { insertDup(0, item, len); }
342 * \brief Prepend a single newly created item.
344 * The new element is initialized with the default constructor.
346 void prependNew() { insertNew(0, 1); }
349 * \brief Prepend len newly created items.
351 * The new elements are initialized with the default constructor.
353 void prependNew(long len) { insertNew(0, len); }
356 /* Convenience access. */
357 T &operator[](int i) const { return BaseTable::data[i]; }
358 long size() const { return BaseTable::tabLen; }
360 /* Forward this so a ref can be used. */
363 /* Various classes for setting the iterator */
364 struct IterFirst { IterFirst( const Vector &v ) : v(v) { } const Vector &v; };
365 struct IterLast { IterLast( const Vector &v ) : v(v) { } const Vector &v; };
366 struct IterNext { IterNext( const Iter &i ) : i(i) { } const Iter &i; };
367 struct IterPrev { IterPrev( const Iter &i ) : i(i) { } const Iter &i; };
370 * \brief Vector Iterator.
375 /* Construct, assign. */
376 Iter() : ptr(0), ptrBeg(0), ptrEnd(0) { }
379 Iter( const Vector &v );
380 Iter( const IterFirst &vf );
381 Iter( const IterLast &vl );
382 inline Iter( const IterNext &vn );
383 inline Iter( const IterPrev &vp );
386 Iter &operator=( const Vector &v );
387 Iter &operator=( const IterFirst &vf );
388 Iter &operator=( const IterLast &vl );
389 inline Iter &operator=( const IterNext &vf );
390 inline Iter &operator=( const IterPrev &vl );
392 /** \brief Less than end? */
393 bool lte() const { return ptr != ptrEnd; }
395 /** \brief At end? */
396 bool end() const { return ptr == ptrEnd; }
398 /** \brief Greater than beginning? */
399 bool gtb() const { return ptr != ptrBeg; }
401 /** \brief At beginning? */
402 bool beg() const { return ptr == ptrBeg; }
404 /** \brief At first element? */
405 bool first() const { return ptr == ptrBeg+1; }
407 /** \brief At last element? */
408 bool last() const { return ptr == ptrEnd-1; }
410 /* Return the position. */
411 long pos() const { return ptr - ptrBeg - 1; }
412 T &operator[](int i) const { return ptr[i]; }
414 /** \brief Implicit cast to T*. */
415 operator T*() const { return ptr; }
417 /** \brief Dereference operator returns T&. */
418 T &operator *() const { return *ptr; }
420 /** \brief Arrow operator returns T*. */
421 T *operator->() const { return ptr; }
423 /** \brief Move to next item. */
424 T *operator++() { return ++ptr; }
426 /** \brief Move to next item. */
427 T *operator++(int) { return ptr++; }
429 /** \brief Move to next item. */
430 T *increment() { return ++ptr; }
432 /** \brief Move n items forward. */
433 T *operator+=(long n) { return ptr+=n; }
435 /** \brief Move to previous item. */
436 T *operator--() { return --ptr; }
438 /** \brief Move to previous item. */
439 T *operator--(int) { return ptr--; }
441 /** \brief Move to previous item. */
442 T *decrement() { return --ptr; }
444 /** \brief Move n items back. */
445 T *operator-=(long n) { return ptr-=n; }
447 /** \brief Return the next item. Does not modify this. */
448 inline IterNext next() const { return IterNext(*this); }
450 /** \brief Return the previous item. Does not modify this. */
451 inline IterPrev prev() const { return IterPrev(*this); }
453 /** \brief The iterator is simply a pointer. */
456 /* For testing endpoints. */
460 /** \brief Return first element. */
461 IterFirst first() { return IterFirst( *this ); }
463 /** \brief Return last element. */
464 IterLast last() { return IterLast( *this ); }
467 void makeRawSpaceFor(long pos, long len);
469 void upResize(long len);
470 void downResize(long len);
473 /* Init a vector iterator with just a vector. */
474 template <class T, class Resize> Vector<T, Resize>::Iter::Iter( const Vector &v )
477 ptr = ptrBeg = ptrEnd = 0;
481 ptrEnd = v.data+v.tabLen;
485 /* Init a vector iterator with the first of a vector. */
486 template <class T, class Resize> Vector<T, Resize>::Iter::Iter(
487 const IterFirst &vf )
489 if ( vf.v.tabLen == 0 )
490 ptr = ptrBeg = ptrEnd = 0;
493 ptrBeg = vf.v.data-1;
494 ptrEnd = vf.v.data+vf.v.tabLen;
498 /* Init a vector iterator with the last of a vector. */
499 template <class T, class Resize> Vector<T, Resize>::Iter::Iter(
502 if ( vl.v.tabLen == 0 )
503 ptr = ptrBeg = ptrEnd = 0;
505 ptr = vl.v.data+vl.v.tabLen-1;
506 ptrBeg = vl.v.data-1;
507 ptrEnd = vl.v.data+vl.v.tabLen;
511 /* Init a vector iterator with the next of some other iterator. */
512 template <class T, class Resize> Vector<T, Resize>::Iter::Iter(
521 /* Init a vector iterator with the prev of some other iterator. */
522 template <class T, class Resize> Vector<T, Resize>::Iter::Iter(
531 /* Set a vector iterator with some vector. */
532 template <class T, class Resize> typename Vector<T, Resize>::Iter &
533 Vector<T, Resize>::Iter::operator=( const Vector &v )
536 ptr = ptrBeg = ptrEnd = 0;
540 ptrEnd = v.data+v.tabLen;
545 /* Set a vector iterator with the first element in a vector. */
546 template <class T, class Resize> typename Vector<T, Resize>::Iter &
547 Vector<T, Resize>::Iter::operator=( const IterFirst &vf )
549 if ( vf.v.tabLen == 0 )
550 ptr = ptrBeg = ptrEnd = 0;
553 ptrBeg = vf.v.data-1;
554 ptrEnd = vf.v.data+vf.v.tabLen;
559 /* Set a vector iterator with the last element in a vector. */
560 template <class T, class Resize> typename Vector<T, Resize>::Iter &
561 Vector<T, Resize>::Iter::operator=( const IterLast &vl )
563 if ( vl.v.tabLen == 0 )
564 ptr = ptrBeg = ptrEnd = 0;
566 ptr = vl.v.data+vl.v.tabLen-1;
567 ptrBeg = vl.v.data-1;
568 ptrEnd = vl.v.data+vl.v.tabLen;
573 /* Set a vector iterator with the next of some other iterator. */
574 template <class T, class Resize> typename Vector<T, Resize>::Iter &
575 Vector<T, Resize>::Iter::operator=( const IterNext &vn )
578 ptrBeg = vn.i.ptrBeg;
579 ptrEnd = vn.i.ptrEnd;
583 /* Set a vector iterator with the prev of some other iterator. */
584 template <class T, class Resize> typename Vector<T, Resize>::Iter &
585 Vector<T, Resize>::Iter::operator=( const IterPrev &vp )
588 ptrBeg = vp.i.ptrBeg;
589 ptrEnd = vp.i.ptrEnd;
594 * \brief Forget all elements in the vector.
596 * The contents of the vector are reset to null without without the space
599 template<class T, class Resize> void Vector<T, Resize>::
603 BaseTable::tabLen = 0;
604 BaseTable::allocLen = 0;
608 * \brief Transfer the contents of another vector into this vector.
610 * The dynamic array of the other vector is moved into this vector by
611 * reference. If this vector is non-empty then its contents are first deleted.
612 * Afterward the other vector will be empty.
614 template<class T, class Resize> void Vector<T, Resize>::
615 transfer( Vector &v )
619 BaseTable::data = v.data;
620 BaseTable::tabLen = v.tabLen;
621 BaseTable::allocLen = v.allocLen;
627 * \brief Deep copy another vector into this vector.
629 * Copies the entire contents of the other vector into this vector. Any
630 * existing contents are first deleted. Equivalent to setAs.
632 * \returns A reference to this.
634 template<class T, class Resize> Vector<T, Resize> &Vector<T, Resize>::
635 operator=( const Vector &v )
637 setAs(v.data, v.tabLen);
641 /* Up resize the data for len elements using Resize::upResize to tell us the
642 * new tabLen. Reads and writes allocLen. Does not read or write tabLen. */
643 template<class T, class Resize> void Vector<T, Resize>::
646 /* Ask the resizer what the new tabLen will be. */
647 long newLen = Resize::upResize(BaseTable::allocLen, len);
649 /* Did the data grow? */
650 if ( newLen > BaseTable::allocLen ) {
651 BaseTable::allocLen = newLen;
652 if ( BaseTable::data != 0 ) {
653 /* Table exists already, resize it up. */
654 BaseTable::data = (T*) realloc( BaseTable::data, sizeof(T) * newLen );
655 if ( BaseTable::data == 0 )
656 throw std::bad_alloc();
659 /* Create the data. */
660 BaseTable::data = (T*) malloc( sizeof(T) * newLen );
661 if ( BaseTable::data == 0 )
662 throw std::bad_alloc();
667 /* Down resize the data for len elements using Resize::downResize to determine
668 * the new tabLen. Reads and writes allocLen. Does not read or write tabLen. */
669 template<class T, class Resize> void Vector<T, Resize>::
672 /* Ask the resizer what the new tabLen will be. */
673 long newLen = Resize::downResize( BaseTable::allocLen, len );
675 /* Did the data shrink? */
676 if ( newLen < BaseTable::allocLen ) {
677 BaseTable::allocLen = newLen;
679 /* Simply free the data. */
680 free( BaseTable::data );
684 /* Not shrinking to size zero, realloc it to the smaller size. */
685 BaseTable::data = (T*) realloc( BaseTable::data, sizeof(T) * newLen );
686 if ( BaseTable::data == 0 )
687 throw std::bad_alloc();
693 * \brief Perform a deep copy of the vector.
695 * The contents of the other vector are copied into this vector. This vector
696 * gets the same allocation size as the other vector. All items are copied
697 * using the element's copy constructor.
699 template<class T, class Resize> Vector<T, Resize>::
700 Vector(const Vector<T, Resize> &v)
702 BaseTable::tabLen = v.tabLen;
703 BaseTable::allocLen = v.allocLen;
705 if ( BaseTable::allocLen > 0 ) {
706 /* Allocate needed space. */
707 BaseTable::data = (T*) malloc(sizeof(T) * BaseTable::allocLen);
708 if ( BaseTable::data == 0 )
709 throw std::bad_alloc();
711 /* If there are any items in the src data, copy them in. */
712 T *dst = BaseTable::data, *src = v.data;
713 for (long pos = 0; pos < BaseTable::tabLen; pos++, dst++, src++ )
717 /* Nothing allocated. */
722 /** \fn Vector::~Vector()
723 * \brief Free all memory used by the vector.
725 * The vector is reset to zero elements. Destructors are called on all
726 * elements in the vector. The space allocated for the vector is freed.
731 * \brief Free all memory used by the vector.
733 * The vector is reset to zero elements. Destructors are called on all
734 * elements in the vector. The space allocated for the vector is freed.
736 template<class T, class Resize> void Vector<T, Resize>::
739 if ( BaseTable::data != 0 ) {
740 /* Call All destructors. */
741 T *pos = BaseTable::data;
742 for ( long i = 0; i < BaseTable::tabLen; pos++, i++ )
745 /* Free the data space. */
746 free( BaseTable::data );
748 BaseTable::tabLen = BaseTable::allocLen = 0;
753 * \brief Set the contents of the vector to be len elements exactly.
755 * The vector becomes len elements in length. Destructors are called on any
756 * existing elements in the vector. Copy constructors are used to place the
757 * new elements in the vector.
759 template<class T, class Resize> void Vector<T, Resize>::
760 setAs(const T *val, long len)
762 /* Call All destructors. */
764 T *pos = BaseTable::data;
765 for ( i = 0; i < BaseTable::tabLen; pos++, i++ )
768 /* Adjust the allocated length. */
769 if ( len < BaseTable::tabLen )
771 else if ( len > BaseTable::tabLen )
774 /* Set the new data length to exactly len. */
775 BaseTable::tabLen = len;
778 T *dst = BaseTable::data;
780 for ( i = 0; i < len; i++, dst++, src++ )
785 * \brief Set the vector to len copies of item.
787 * The vector becomes len elements in length. Destructors are called on any
788 * existing elements in the vector. The element's copy constructor is used to
789 * copy the item into the vector.
791 template<class T, class Resize> void Vector<T, Resize>::
792 setAsDup(const T &item, long len)
794 /* Call All destructors. */
795 T *pos = BaseTable::data;
796 for ( long i = 0; i < BaseTable::tabLen; pos++, i++ )
799 /* Adjust the allocated length. */
800 if ( len < BaseTable::tabLen )
802 else if ( len > BaseTable::tabLen )
805 /* Set the new data length to exactly len. */
806 BaseTable::tabLen = len;
808 /* Copy item in one spot at a time. */
809 T *dst = BaseTable::data;
810 for ( long i = 0; i < len; i++, dst++ )
815 * \brief Set the vector to exactly len new items.
817 * The vector becomes len elements in length. Destructors are called on any
818 * existing elements in the vector. Default constructors are used to init the
821 template<class T, class Resize> void Vector<T, Resize>::
824 /* Call All destructors. */
825 T *pos = BaseTable::data;
826 for ( long i = 0; i < BaseTable::tabLen; pos++, i++ )
829 /* Adjust the allocated length. */
830 if ( len < BaseTable::tabLen )
832 else if ( len > BaseTable::tabLen )
835 /* Set the new data length to exactly len. */
836 BaseTable::tabLen = len;
838 /* Create items using default constructor. */
839 T *dst = BaseTable::data;
840 for ( long i = 0; i < len; i++, dst++ )
846 * \brief Replace len elements at position pos.
848 * If there are existing elements at the positions to be replaced, then
849 * destructors are called before the space is used. Copy constructors are used
850 * to place the elements into the vector. It is allowable for the pos and
851 * length to specify a replacement that overwrites existing elements and
852 * creates new ones. If pos is greater than the length of the vector then
853 * undefined behaviour results. If pos is negative, then it is treated as an
854 * offset relative to the length of the vector.
856 template<class T, class Resize> void Vector<T, Resize>::
857 replace(long pos, const T *val, long len)
862 /* If we are given a negative position to replace at then
863 * treat it as a position relative to the length. */
865 pos = BaseTable::tabLen + pos;
867 /* The end is the one past the last item that we want
871 /* Make sure we have enough space. */
872 if ( endPos > BaseTable::tabLen ) {
875 /* Delete any objects we need to delete. */
876 item = BaseTable::data + pos;
877 for ( i = pos; i < BaseTable::tabLen; i++, item++ )
880 /* We are extending the vector, set the new data length. */
881 BaseTable::tabLen = endPos;
884 /* Delete any objects we need to delete. */
885 item = BaseTable::data + pos;
886 for ( i = pos; i < endPos; i++, item++ )
890 /* Copy data in using copy constructor. */
891 T *dst = BaseTable::data + pos;
893 for ( i = 0; i < len; i++, dst++, src++ )
898 * \brief Replace at position pos with len copies of an item.
900 * If there are existing elements at the positions to be replaced, then
901 * destructors are called before the space is used. The copy constructor is
902 * used to place the element into this vector. It is allowable for the pos and
903 * length to specify a replacement that overwrites existing elements and
904 * creates new ones. If pos is greater than the length of the vector then
905 * undefined behaviour results. If pos is negative, then it is treated as an
906 * offset relative to the length of the vector.
908 template<class T, class Resize> void Vector<T, Resize>::
909 replaceDup(long pos, const T &val, long len)
914 /* If we are given a negative position to replace at then
915 * treat it as a position relative to the length. */
917 pos = BaseTable::tabLen + pos;
919 /* The end is the one past the last item that we want
923 /* Make sure we have enough space. */
924 if ( endPos > BaseTable::tabLen ) {
927 /* Delete any objects we need to delete. */
928 item = BaseTable::data + pos;
929 for ( i = pos; i < BaseTable::tabLen; i++, item++ )
932 /* We are extending the vector, set the new data length. */
933 BaseTable::tabLen = endPos;
936 /* Delete any objects we need to delete. */
937 item = BaseTable::data + pos;
938 for ( i = pos; i < endPos; i++, item++ )
942 /* Copy data in using copy constructor. */
943 T *dst = BaseTable::data + pos;
944 for ( long i = 0; i < len; i++, dst++ )
949 * \brief Replace at position pos with len new elements.
951 * If there are existing elements at the positions to be replaced, then
952 * destructors are called before the space is used. The default constructor is
953 * used to initialize the new elements. It is allowable for the pos and length
954 * to specify a replacement that overwrites existing elements and creates new
955 * ones. If pos is greater than the length of the vector then undefined
956 * behaviour results. If pos is negative, then it is treated as an offset
957 * relative to the length of the vector.
959 template<class T, class Resize> void Vector<T, Resize>::
960 replaceNew(long pos, long len)
965 /* If we are given a negative position to replace at then
966 * treat it as a position relative to the length. */
968 pos = BaseTable::tabLen + pos;
970 /* The end is the one past the last item that we want
974 /* Make sure we have enough space. */
975 if ( endPos > BaseTable::tabLen ) {
978 /* Delete any objects we need to delete. */
979 item = BaseTable::data + pos;
980 for ( i = pos; i < BaseTable::tabLen; i++, item++ )
983 /* We are extending the vector, set the new data length. */
984 BaseTable::tabLen = endPos;
987 /* Delete any objects we need to delete. */
988 item = BaseTable::data + pos;
989 for ( i = pos; i < endPos; i++, item++ )
993 /* Copy data in using copy constructor. */
994 T *dst = BaseTable::data + pos;
995 for ( long i = 0; i < len; i++, dst++ )
1000 * \brief Remove len elements at position pos.
1002 * Destructor is called on all elements removed. Elements to the right of pos
1003 * are shifted len spaces to the left to take up the free space. If pos is
1004 * greater than or equal to the length of the vector then undefined behavior
1005 * results. If pos is negative then it is treated as an offset relative to the
1006 * length of the vector.
1008 template<class T, class Resize> void Vector<T, Resize>::
1009 remove(long pos, long len)
1011 long newLen, lenToSlideOver, endPos;
1014 /* If we are given a negative position to remove at then
1015 * treat it as a position relative to the length. */
1017 pos = BaseTable::tabLen + pos;
1019 /* The first position after the last item deleted. */
1022 /* The new data length. */
1023 newLen = BaseTable::tabLen - len;
1025 /* The place in the data we are deleting at. */
1026 dst = BaseTable::data + pos;
1028 /* Call Destructors. */
1030 for ( long i = 0; i < len; i += 1, item += 1 )
1033 /* Shift data over if necessary. */
1034 lenToSlideOver = BaseTable::tabLen - endPos;
1035 if ( len > 0 && lenToSlideOver > 0 )
1036 memmove(dst, dst + len, sizeof(T)*lenToSlideOver);
1038 /* Shrink the data if necessary. */
1039 downResize( newLen );
1041 /* Set the new data length. */
1042 BaseTable::tabLen = newLen;
1046 * \brief Insert len elements at position pos.
1048 * Elements in the vector from pos onward are shifted len spaces to the right.
1049 * The copy constructor is used to place the elements into this vector. If pos
1050 * is greater than the length of the vector then undefined behaviour results.
1051 * If pos is negative then it is treated as an offset relative to the length
1054 template<class T, class Resize> void Vector<T, Resize>::
1055 insert(long pos, const T *val, long len)
1057 /* If we are given a negative position to insert at then
1058 * treat it as a position relative to the length. */
1060 pos = BaseTable::tabLen + pos;
1062 /* Calculate the new length. */
1063 long newLen = BaseTable::tabLen + len;
1065 /* Up resize, we are growing. */
1068 /* Shift over data at insert spot if needed. */
1069 if ( len > 0 && pos < BaseTable::tabLen ) {
1070 memmove(BaseTable::data + pos + len, BaseTable::data + pos,
1071 sizeof(T)*(BaseTable::tabLen-pos));
1074 /* Copy data in element by element. */
1075 T *dst = BaseTable::data + pos;
1077 for ( long i = 0; i < len; i++, dst++, src++ )
1080 /* Set the new length. */
1081 BaseTable::tabLen = newLen;
1085 * \brief Insert len copies of item at position pos.
1087 * Elements in the vector from pos onward are shifted len spaces to the right.
1088 * The copy constructor is used to place the element into this vector. If pos
1089 * is greater than the length of the vector then undefined behaviour results.
1090 * If pos is negative then it is treated as an offset relative to the length
1093 template<class T, class Resize> void Vector<T, Resize>::
1094 insertDup(long pos, const T &item, long len)
1096 /* If we are given a negative position to insert at then
1097 * treat it as a position relative to the length. */
1099 pos = BaseTable::tabLen + pos;
1101 /* Calculate the new length. */
1102 long newLen = BaseTable::tabLen + len;
1104 /* Up resize, we are growing. */
1107 /* Shift over data at insert spot if needed. */
1108 if ( len > 0 && pos < BaseTable::tabLen ) {
1109 memmove(BaseTable::data + pos + len, BaseTable::data + pos,
1110 sizeof(T)*(BaseTable::tabLen-pos));
1113 /* Copy the data item in one at a time. */
1114 T *dst = BaseTable::data + pos;
1115 for ( long i = 0; i < len; i++, dst++ )
1118 /* Set the new length. */
1119 BaseTable::tabLen = newLen;
1123 * \brief Insert len new elements using the default constructor.
1125 * Elements in the vector from pos onward are shifted len spaces to the right.
1126 * Default constructors are used to init the new elements. If pos is off the
1127 * end of the vector then undefined behaviour results. If pos is negative then
1128 * it is treated as an offset relative to the length of the vector.
1130 template<class T, class Resize> void Vector<T, Resize>::
1131 insertNew(long pos, long len)
1133 /* If we are given a negative position to insert at then
1134 * treat it as a position relative to the length. */
1136 pos = BaseTable::tabLen + pos;
1138 /* Calculate the new length. */
1139 long newLen = BaseTable::tabLen + len;
1141 /* Up resize, we are growing. */
1144 /* Shift over data at insert spot if needed. */
1145 if ( len > 0 && pos < BaseTable::tabLen ) {
1146 memmove(BaseTable::data + pos + len, BaseTable::data + pos,
1147 sizeof(T)*(BaseTable::tabLen-pos));
1150 /* Init new data with default constructors. */
1151 T *dst = BaseTable::data + pos;
1152 for ( long i = 0; i < len; i++, dst++ )
1155 /* Set the new length. */
1156 BaseTable::tabLen = newLen;
1159 /* Makes space for len items, Does not init the items in any way. If pos is
1160 * greater than the length of the vector then undefined behaviour results.
1161 * Updates the length of the vector. */
1162 template<class T, class Resize> void Vector<T, Resize>::
1163 makeRawSpaceFor(long pos, long len)
1165 /* Calculate the new length. */
1166 long newLen = BaseTable::tabLen + len;
1168 /* Up resize, we are growing. */
1171 /* Shift over data at insert spot if needed. */
1172 if ( len > 0 && pos < BaseTable::tabLen ) {
1173 memmove(BaseTable::data + pos + len, BaseTable::data + pos,
1174 sizeof(T)*(BaseTable::tabLen-pos));
1177 /* Save the new length. */
1178 BaseTable::tabLen = newLen;
1181 #ifdef AAPL_NAMESPACE
1185 #endif /* _AAPL_VECTOR_H */