aapl/vector.h

   1 /*
   2  *  Copyright 2002, 2006 Adrian Thurston <thurston@complang.org>
   3  */
   4
   5 /*  This file is part of Aapl.
   6  *
   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)
  10  *  any later version.
  11  *
  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
  15  *  more details.
  16  *
  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
  20  */
  21
  22 #ifndef _AAPL_VECTOR_H
  23 #define _AAPL_VECTOR_H
  24
  25 #include <new>
  26 #include <string.h>
  27 #include <stdlib.h>
  28 #include <assert.h>
  29 #include "table.h"
  30
  31 #ifdef AAPL_NAMESPACE
  32 namespace Aapl {
  33 #endif
  34
  35 /**
  36  * \addtogroup vector
  37  * @{
  38  */
  39
  40 /** \class Vector
  41  * \brief Dynamic array.
  42  *
  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.
  46  *
  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.
  51  *
  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
  58  * vector.
  59  *
  60  * \include ex_vector.cpp
  61  */
  62
  63 /*@}*/
  64
  65 template < class T, class Resize = ResizeExpn > class Vector
  66         : public Table<T>, public Resize
  67 {
  68 private:
  69         typedef Table<T> BaseTable;
  70
  71 public:
  72         /**
  73          * \brief Initialize an empty vector with no space allocated.
  74          *
  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
  77          * Exponential.
  78          */
  79         Vector() { }
  80
  81         /**
  82          * \brief Create a vector that contains an initial element.
  83          *
  84          * The vector becomes one element in length. The element's copy
  85          * constructor is used to place the value in the vector.
  86          */
  87         Vector(const T &val)             { setAs(&val, 1); }
  88
  89         /**
  90          * \brief Create a vector that contains an array of elements.
  91          *
  92          * The vector becomes len elements in length.  Copy constructors are used
  93          * to place the new elements in the vector.
  94          */
  95         Vector(const T *val, long len)   { setAs(val, len); }
  96
  97         /* Deep copy. */
  98         Vector( const Vector &v );
  99
 100         /* Free all mem used by the vector. */
 101         ~Vector() { empty(); }
 102
 103         /* Delete all items. */
 104         void empty();
 105
 106         /* Abandon the contents of the vector without deleteing. */
 107         void abandon();
 108
 109         /* Transfers the elements of another vector into this vector. First emptys
 110          * the current vector. */
 111         void transfer( Vector &v );
 112
 113         /* Perform a deep copy of another vector into this vector. */
 114         Vector &operator=( const Vector &v );
 115
 116
 117         /*@{*/
 118         /**
 119          * \brief Insert one element at position pos.
 120          *
 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.
 126          */
 127         void insert(long pos, const T &val)    { insert(pos, &val, 1); }
 128
 129         /* Insert an array of values. */
 130         void insert(long pos, const T *val, long len);
 131
 132         /**
 133          * \brief Insert all the elements from another vector at position pos.
 134          *
 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).
 141          */
 142         void insert(long pos, const Vector &v) { insert(pos, v.data, v.tabLen); }
 143
 144         /* Insert len copies of val into the vector. */
 145         void insertDup(long pos, const T &val, long len);
 146
 147         /**
 148          * \brief Insert one new element using the default constrcutor.
 149          *
 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.
 155          */
 156         void insertNew(long pos)               { insertNew(pos, 1); }
 157
 158         /* Insert len new items using default constructor. */
 159         void insertNew(long pos, long len);
 160         /*@}*/
 161
 162         /*@{*/
 163         /**
 164          * \brief Remove one element at position pos.
 165          *
 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
 170          * of the vector.
 171          */
 172         void remove(long pos)                 { remove(pos, 1); }
 173
 174         /* Delete a number of elements. */
 175         void remove(long pos, long len);
 176         /*@}*/
 177
 178         /*@{*/
 179         /**
 180          * \brief Replace one element at position pos.
 181          *
 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.
 188          */
 189         void replace(long pos, const T &val)    { replace(pos, &val, 1); }
 190
 191         /* Replace with an array of values. */
 192         void replace(long pos, const T *val, long len);
 193
 194         /**
 195          * \brief Replace at position pos with all the elements of another vector.
 196          *
 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.
 206          */
 207         void replace(long pos, const Vector &v) { replace(pos, v.data, v.tabLen); }
 208
 209         /* Replace len items with len copies of val. */
 210         void replaceDup(long pos, const T &val, long len);
 211
 212         /**
 213          * \brief Replace at position pos with one new element.
 214          *
 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.
 221          */
 222         void replaceNew(long pos)               { replaceNew(pos, 1); }
 223
 224         /* Replace len items at pos with newly constructed objects. */
 225         void replaceNew(long pos, long len);
 226         /*@}*/
 227
 228         /*@{*/
 229         /**
 230          * \brief Set the contents of the vector to be val exactly.
 231          *
 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.
 235          */
 236         void setAs(const T &val)             { setAs(&val, 1); }
 237
 238         /* Set to the contents of an array. */
 239         void setAs(const T *val, long len);
 240
 241         /**
 242          * \brief Set the vector to exactly the contents of another vector.
 243          *
 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.
 247          */
 248         void setAs(const Vector &v)          { setAs(v.data, v.tabLen); }
 249
 250         /* Set as len copies of item. */
 251         void setAsDup(const T &item, long len);
 252
 253         /**
 254          * \brief Set the vector to exactly one new item.
 255          *
 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
 258          * init the new item.
 259          */
 260         void setAsNew()                      { setAsNew(1); }
 261
 262         /* Set as newly constructed objects using the default constructor. */
 263         void setAsNew(long len);
 264         /*@}*/
 265
 266         /*@{*/
 267         /**
 268          * \brief Append one elment to the end of the vector.
 269          *
 270          * Copy constructor is used to place the element in the vector.
 271          */
 272         void append(const T &val)                { replace(BaseTable::tabLen, &val, 1); }
 273
 274         /**
 275          * \brief Append len elements to the end of the vector.
 276          *
 277          * Copy constructors are used to place the elements in the vector.
 278          */
 279         void append(const T *val, long len)       { replace(BaseTable::tabLen, val, len); }
 280
 281         /**
 282          * \brief Append the contents of another vector.
 283          *
 284          * The other vector is left unchanged. Copy constructors are used to place the
 285          * elements in the vector.
 286          */
 287         void append(const Vector &v)             { replace(BaseTable::tabLen, v.data, v.tabLen); }
 288
 289         /**
 290          * \brief Append len copies of item.
 291          *
 292          * The copy constructor is used to place the item in the vector.
 293          */
 294         void appendDup(const T &item, long len)   { replaceDup(BaseTable::tabLen, item, len); }
 295
 296         /**
 297          * \brief Append a single newly created item.
 298          *
 299          * The new element is initialized with the default constructor.
 300          */
 301         void appendNew()                         { replaceNew(BaseTable::tabLen, 1); }
 302
 303         /**
 304          * \brief Append len newly created items.
 305          *
 306          * The new elements are initialized with the default constructor.
 307          */
 308         void appendNew(long len)                  { replaceNew(BaseTable::tabLen, len); }
 309         /*@}*/
 310
 311         /*@{*/
 312         /** \fn Vector::prepend(const T &val)
 313          * \brief Prepend one elment to the front of the vector.
 314          *
 315          * Copy constructor is used to place the element in the vector.
 316          */
 317         void prepend(const T &val)               { insert(0, &val, 1); }
 318
 319         /**
 320          * \brief Prepend len elements to the front of the vector.
 321          *
 322          * Copy constructors are used to place the elements in the vector.
 323          */
 324         void prepend(const T *val, long len)      { insert(0, val, len); }
 325
 326         /**
 327          * \brief Prepend the contents of another vector.
 328          *
 329          * The other vector is left unchanged. Copy constructors are used to place the
 330          * elements in the vector.
 331          */
 332         void prepend(const Vector &v)            { insert(0, v.data, v.tabLen); }
 333
 334         /**
 335          * \brief Prepend len copies of item.
 336          *
 337          * The copy constructor is used to place the item in the vector.
 338          */
 339         void prependDup(const T &item, long len)  { insertDup(0, item, len); }
 340
 341         /**
 342          * \brief Prepend a single newly created item.
 343          *
 344          * The new element is initialized with the default constructor.
 345          */
 346         void prependNew()                        { insertNew(0, 1); }
 347
 348         /**
 349          * \brief Prepend len newly created items.
 350          *
 351          * The new elements are initialized with the default constructor.
 352          */
 353         void prependNew(long len)                 { insertNew(0, len); }
 354         /*@}*/
 355
 356         /* Convenience access. */
 357         T &operator[](int i) const { return BaseTable::data[i]; }
 358         long size() const           { return BaseTable::tabLen; }
 359
 360         /* Forward this so a ref can be used. */
 361         struct Iter;
 362
 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; };
 368
 369         /**
 370          * \brief Vector Iterator.
 371          * \ingroup iterators
 372          */
 373         struct Iter
 374         {
 375                 /* Construct, assign. */
 376                 Iter() : ptr(0), ptrBeg(0), ptrEnd(0) { }
 377
 378                 /* Construct. */
 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 );
 384
 385                 /* Assign. */
 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 );
 391
 392                 /** \brief Less than end? */
 393                 bool lte() const { return ptr != ptrEnd; }
 394
 395                 /** \brief At end? */
 396                 bool end() const { return ptr == ptrEnd; }
 397
 398                 /** \brief Greater than beginning? */
 399                 bool gtb() const { return ptr != ptrBeg; }
 400
 401                 /** \brief At beginning? */
 402                 bool beg() const { return ptr == ptrBeg; }
 403
 404                 /** \brief At first element? */
 405                 bool first() const { return ptr == ptrBeg+1; }
 406
 407                 /** \brief At last element? */
 408                 bool last() const { return ptr == ptrEnd-1; }
 409
 410                 /* Return the position. */
 411                 long pos() const { return ptr - ptrBeg - 1; }
 412                 T &operator[](int i) const { return ptr[i]; }
 413
 414                 /** \brief Implicit cast to T*. */
 415                 operator T*() const   { return ptr; }
 416
 417                 /** \brief Dereference operator returns T&. */
 418                 T &operator *() const { return *ptr; }
 419
 420                 /** \brief Arrow operator returns T*. */
 421                 T *operator->() const { return ptr; }
 422
 423                 /** \brief Move to next item. */
 424                 T *operator++()       { return ++ptr; }
 425
 426                 /** \brief Move to next item. */
 427                 T *operator++(int)    { return ptr++; }
 428
 429                 /** \brief Move to next item. */
 430                 T *increment()        { return ++ptr; }
 431
 432                 /** \brief Move n items forward. */
 433                 T *operator+=(long n)       { return ptr+=n; }
 434
 435                 /** \brief Move to previous item. */
 436                 T *operator--()       { return --ptr; }
 437
 438                 /** \brief Move to previous item. */
 439                 T *operator--(int)    { return ptr--; }
 440
 441                 /** \brief Move to previous item. */
 442                 T *decrement()        { return --ptr; }
 443
 444                 /** \brief Move n items back. */
 445                 T *operator-=(long n)       { return ptr-=n; }
 446
 447                 /** \brief Return the next item. Does not modify this. */
 448                 inline IterNext next() const { return IterNext(*this); }
 449
 450                 /** \brief Return the previous item. Does not modify this. */
 451                 inline IterPrev prev() const { return IterPrev(*this); }
 452
 453                 /** \brief The iterator is simply a pointer. */
 454                 T *ptr;
 455
 456                 /* For testing endpoints. */
 457                 T *ptrBeg, *ptrEnd;
 458         };
 459
 460         /** \brief Return first element. */
 461         IterFirst first() { return IterFirst( *this ); }
 462
 463         /** \brief Return last element. */
 464         IterLast last() { return IterLast( *this ); }
 465
 466 protected:
 467         void makeRawSpaceFor(long pos, long len);
 468
 469         void upResize(long len);
 470         void downResize(long len);
 471 };
 472
 473 /* Init a vector iterator with just a vector. */
 474 template <class T, class Resize> Vector<T, Resize>::Iter::Iter( const Vector &v )
 475 {
 476         if ( v.tabLen == 0 )
 477                 ptr = ptrBeg = ptrEnd = 0;
 478         else {
 479                 ptr = v.data;
 480                 ptrBeg = v.data-1;
 481                 ptrEnd = v.data+v.tabLen;
 482         }
 483 }
 484
 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 )
 488 {
 489         if ( vf.v.tabLen == 0 )
 490                 ptr = ptrBeg = ptrEnd = 0;
 491         else {
 492                 ptr = vf.v.data;
 493                 ptrBeg = vf.v.data-1;
 494                 ptrEnd = vf.v.data+vf.v.tabLen;
 495         }
 496 }
 497
 498 /* Init a vector iterator with the last of a vector. */
 499 template <class T, class Resize> Vector<T, Resize>::Iter::Iter(
 500                 const IterLast &vl )
 501 {
 502         if ( vl.v.tabLen == 0 )
 503                 ptr = ptrBeg = ptrEnd = 0;
 504         else {
 505                 ptr = vl.v.data+vl.v.tabLen-1;
 506                 ptrBeg = vl.v.data-1;
 507                 ptrEnd = vl.v.data+vl.v.tabLen;
 508         }
 509 }
 510
 511 /* Init a vector iterator with the next of some other iterator. */
 512 template <class T, class Resize> Vector<T, Resize>::Iter::Iter(
 513                 const IterNext &vn )
 514 :
 515         ptr(vn.i.ptr+1),
 516         ptrBeg(vn.i.ptrBeg),
 517         ptrEnd(vn.i.ptrEnd)
 518 {
 519 }
 520
 521 /* Init a vector iterator with the prev of some other iterator. */
 522 template <class T, class Resize> Vector<T, Resize>::Iter::Iter(
 523                 const IterPrev &vp )
 524 :
 525         ptr(vp.i.ptr-1),
 526         ptrBeg(vp.i.ptrBeg),
 527         ptrEnd(vp.i.ptrEnd)
 528 {
 529 }
 530
 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 )
 534 {
 535         if ( v.tabLen == 0 )
 536                 ptr = ptrBeg = ptrEnd = 0;
 537         else {
 538                 ptr = v.data;
 539                 ptrBeg = v.data-1;
 540                 ptrEnd = v.data+v.tabLen;
 541         }
 542         return *this;
 543 }
 544
 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 )
 548 {
 549         if ( vf.v.tabLen == 0 )
 550                 ptr = ptrBeg = ptrEnd = 0;
 551         else {
 552                 ptr = vf.v.data;
 553                 ptrBeg = vf.v.data-1;
 554                 ptrEnd = vf.v.data+vf.v.tabLen;
 555         }
 556         return *this;
 557 }
 558
 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 )
 562 {
 563         if ( vl.v.tabLen == 0 )
 564                 ptr = ptrBeg = ptrEnd = 0;
 565         else {
 566                 ptr = vl.v.data+vl.v.tabLen-1;
 567                 ptrBeg = vl.v.data-1;
 568                 ptrEnd = vl.v.data+vl.v.tabLen;
 569         }
 570         return *this;
 571 }
 572
 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 )
 576 {
 577         ptr = vn.i.ptr+1;
 578         ptrBeg = vn.i.ptrBeg;
 579         ptrEnd = vn.i.ptrEnd;
 580         return *this;
 581 }
 582
 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 )
 586 {
 587         ptr = vp.i.ptr-1;
 588         ptrBeg = vp.i.ptrBeg;
 589         ptrEnd = vp.i.ptrEnd;
 590         return *this;
 591 }
 592
 593 /**
 594  * \brief Forget all elements in the vector.
 595  *
 596  * The contents of the vector are reset to null without without the space
 597  * being freed.
 598  */
 599 template<class T, class Resize> void Vector<T, Resize>::
 600                 abandon()
 601 {
 602         BaseTable::data = 0;
 603         BaseTable::tabLen = 0;
 604         BaseTable::allocLen = 0;
 605 }
 606
 607 /**
 608  * \brief Transfer the contents of another vector into this vector.
 609  *
 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.
 613  */
 614 template<class T, class Resize> void Vector<T, Resize>::
 615                 transfer( Vector &v )
 616 {
 617         empty();
 618
 619         BaseTable::data = v.data;
 620         BaseTable::tabLen = v.tabLen;
 621         BaseTable::allocLen = v.allocLen;
 622
 623         v.abandon();
 624 }
 625
 626 /**
 627  * \brief Deep copy another vector into this vector.
 628  *
 629  * Copies the entire contents of the other vector into this vector. Any
 630  * existing contents are first deleted. Equivalent to setAs.
 631  *
 632  * \returns A reference to this.
 633  */
 634 template<class T, class Resize> Vector<T, Resize> &Vector<T, Resize>::
 635                 operator=( const Vector &v )
 636 {
 637         setAs(v.data, v.tabLen);
 638         return *this;
 639 }
 640
 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>::
 644                 upResize(long len)
 645 {
 646         /* Ask the resizer what the new tabLen will be. */
 647         long newLen = Resize::upResize(BaseTable::allocLen, len);
 648
 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();
 657                 }
 658                 else {
 659                         /* Create the data. */
 660                         BaseTable::data = (T*) malloc( sizeof(T) * newLen );
 661                         if ( BaseTable::data == 0 )
 662                                 throw std::bad_alloc();
 663                 }
 664         }
 665 }
 666
 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>::
 670                 downResize(long len)
 671 {
 672         /* Ask the resizer what the new tabLen will be. */
 673         long newLen = Resize::downResize( BaseTable::allocLen, len );
 674
 675         /* Did the data shrink? */
 676         if ( newLen < BaseTable::allocLen ) {
 677                 BaseTable::allocLen = newLen;
 678                 if ( newLen == 0 ) {
 679                         /* Simply free the data. */
 680                         free( BaseTable::data );
 681                         BaseTable::data = 0;
 682                 }
 683                 else {
 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();
 688                 }
 689         }
 690 }
 691
 692 /**
 693  * \brief Perform a deep copy of the vector.
 694  *
 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.
 698  */
 699 template<class T, class Resize> Vector<T, Resize>::
 700                 Vector(const Vector<T, Resize> &v)
 701 {
 702         BaseTable::tabLen = v.tabLen;
 703         BaseTable::allocLen = v.allocLen;
 704
 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();
 710
 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++ )
 714                         new(dst) T(*src);
 715         }
 716         else {
 717                 /* Nothing allocated. */
 718                 BaseTable::data = 0;
 719         }
 720 }
 721
 722 /** \fn Vector::~Vector()
 723  * \brief Free all memory used by the vector.
 724  *
 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.
 727  */
 728
 729
 730 /**
 731  * \brief Free all memory used by the vector.
 732  *
 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.
 735  */
 736 template<class T, class Resize> void Vector<T, Resize>::
 737                 empty()
 738 {
 739         if ( BaseTable::data != 0 ) {
 740                 /* Call All destructors. */
 741                 T *pos = BaseTable::data;
 742                 for ( long i = 0; i < BaseTable::tabLen; pos++, i++ )
 743                         pos->~T();
 744
 745                 /* Free the data space. */
 746                 free( BaseTable::data );
 747                 BaseTable::data = 0;
 748                 BaseTable::tabLen = BaseTable::allocLen = 0;
 749         }
 750 }
 751
 752 /**
 753  * \brief Set the contents of the vector to be len elements exactly.
 754  *
 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.
 758  */
 759 template<class T, class Resize> void Vector<T, Resize>::
 760                 setAs(const T *val, long len)
 761 {
 762         /* Call All destructors. */
 763         long i;
 764         T *pos = BaseTable::data;
 765         for ( i = 0; i < BaseTable::tabLen; pos++, i++ )
 766                 pos->~T();
 767
 768         /* Adjust the allocated length. */
 769         if ( len < BaseTable::tabLen )
 770                 downResize( len );
 771         else if ( len > BaseTable::tabLen )
 772                 upResize( len );
 773
 774         /* Set the new data length to exactly len. */
 775         BaseTable::tabLen = len;
 776
 777         /* Copy data in. */
 778         T *dst = BaseTable::data;
 779         const T *src = val;
 780         for ( i = 0; i < len; i++, dst++, src++ )
 781                 new(dst) T(*src);
 782 }
 783
 784 /**
 785  * \brief Set the vector to len copies of item.
 786  *
 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.
 790  */
 791 template<class T, class Resize> void Vector<T, Resize>::
 792                 setAsDup(const T &item, long len)
 793 {
 794         /* Call All destructors. */
 795         T *pos = BaseTable::data;
 796         for ( long i = 0; i < BaseTable::tabLen; pos++, i++ )
 797                 pos->~T();
 798
 799         /* Adjust the allocated length. */
 800         if ( len < BaseTable::tabLen )
 801                 downResize( len );
 802         else if ( len > BaseTable::tabLen )
 803                 upResize( len );
 804
 805         /* Set the new data length to exactly len. */
 806         BaseTable::tabLen = len;
 807
 808         /* Copy item in one spot at a time. */
 809         T *dst = BaseTable::data;
 810         for ( long i = 0; i < len; i++, dst++ )
 811                 new(dst) T(item);
 812 }
 813
 814 /**
 815  * \brief Set the vector to exactly len new items.
 816  *
 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
 819  * new items.
 820  */
 821 template<class T, class Resize> void Vector<T, Resize>::
 822                 setAsNew(long len)
 823 {
 824         /* Call All destructors. */
 825         T *pos = BaseTable::data;
 826         for ( long i = 0; i < BaseTable::tabLen; pos++, i++ )
 827                 pos->~T();
 828
 829         /* Adjust the allocated length. */
 830         if ( len < BaseTable::tabLen )
 831                 downResize( len );
 832         else if ( len > BaseTable::tabLen )
 833                 upResize( len );
 834
 835         /* Set the new data length to exactly len. */
 836         BaseTable::tabLen = len;
 837
 838         /* Create items using default constructor. */
 839         T *dst = BaseTable::data;
 840         for ( long i = 0; i < len; i++, dst++ )
 841                 new(dst) T();
 842 }
 843
 844
 845 /**
 846  * \brief Replace len elements at position pos.
 847  *
 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.
 855  */
 856 template<class T, class Resize> void Vector<T, Resize>::
 857                 replace(long pos, const T *val, long len)
 858 {
 859         long endPos, i;
 860         T *item;
 861
 862         /* If we are given a negative position to replace at then
 863          * treat it as a position relative to the length. */
 864         if ( pos < 0 )
 865                 pos = BaseTable::tabLen + pos;
 866
 867         /* The end is the one past the last item that we want
 868          * to write to. */
 869         endPos = pos + len;
 870
 871         /* Make sure we have enough space. */
 872         if ( endPos > BaseTable::tabLen ) {
 873                 upResize( endPos );
 874
 875                 /* Delete any objects we need to delete. */
 876                 item = BaseTable::data + pos;
 877                 for ( i = pos; i < BaseTable::tabLen; i++, item++ )
 878                         item->~T();
 879
 880                 /* We are extending the vector, set the new data length. */
 881                 BaseTable::tabLen = endPos;
 882         }
 883         else {
 884                 /* Delete any objects we need to delete. */
 885                 item = BaseTable::data + pos;
 886                 for ( i = pos; i < endPos; i++, item++ )
 887                         item->~T();
 888         }
 889
 890         /* Copy data in using copy constructor. */
 891         T *dst = BaseTable::data + pos;
 892         const T *src = val;
 893         for ( i = 0; i < len; i++, dst++, src++ )
 894                 new(dst) T(*src);
 895 }
 896
 897 /**
 898  * \brief Replace at position pos with len copies of an item.
 899  *
 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.
 907  */
 908 template<class T, class Resize> void Vector<T, Resize>::
 909                 replaceDup(long pos, const T &val, long len)
 910 {
 911         long endPos, i;
 912         T *item;
 913
 914         /* If we are given a negative position to replace at then
 915          * treat it as a position relative to the length. */
 916         if ( pos < 0 )
 917                 pos = BaseTable::tabLen + pos;
 918
 919         /* The end is the one past the last item that we want
 920          * to write to. */
 921         endPos = pos + len;
 922
 923         /* Make sure we have enough space. */
 924         if ( endPos > BaseTable::tabLen ) {
 925                 upResize( endPos );
 926
 927                 /* Delete any objects we need to delete. */
 928                 item = BaseTable::data + pos;
 929                 for ( i = pos; i < BaseTable::tabLen; i++, item++ )
 930                         item->~T();
 931
 932                 /* We are extending the vector, set the new data length. */
 933                 BaseTable::tabLen = endPos;
 934         }
 935         else {
 936                 /* Delete any objects we need to delete. */
 937                 item = BaseTable::data + pos;
 938                 for ( i = pos; i < endPos; i++, item++ )
 939                         item->~T();
 940         }
 941
 942         /* Copy data in using copy constructor. */
 943         T *dst = BaseTable::data + pos;
 944         for ( long i = 0; i < len; i++, dst++ )
 945                 new(dst) T(val);
 946 }
 947
 948 /**
 949  * \brief Replace at position pos with len new elements.
 950  *
 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.
 958  */
 959 template<class T, class Resize> void Vector<T, Resize>::
 960                 replaceNew(long pos, long len)
 961 {
 962         long endPos, i;
 963         T *item;
 964
 965         /* If we are given a negative position to replace at then
 966          * treat it as a position relative to the length. */
 967         if ( pos < 0 )
 968                 pos = BaseTable::tabLen + pos;
 969
 970         /* The end is the one past the last item that we want
 971          * to write to. */
 972         endPos = pos + len;
 973
 974         /* Make sure we have enough space. */
 975         if ( endPos > BaseTable::tabLen ) {
 976                 upResize( endPos );
 977
 978                 /* Delete any objects we need to delete. */
 979                 item = BaseTable::data + pos;
 980                 for ( i = pos; i < BaseTable::tabLen; i++, item++ )
 981                         item->~T();
 982
 983                 /* We are extending the vector, set the new data length. */
 984                 BaseTable::tabLen = endPos;
 985         }
 986         else {
 987                 /* Delete any objects we need to delete. */
 988                 item = BaseTable::data + pos;
 989                 for ( i = pos; i < endPos; i++, item++ )
 990                         item->~T();
 991         }
 992
 993         /* Copy data in using copy constructor. */
 994         T *dst = BaseTable::data + pos;
 995         for ( long i = 0; i < len; i++, dst++ )
 996                 new(dst) T();
 997 }
 998
 999 /**
1000  * \brief Remove len elements at position pos.
1001  *
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.
1007  */
1008 template<class T, class Resize> void Vector<T, Resize>::
1009                 remove(long pos, long len)
1010 {
1011         long newLen, lenToSlideOver, endPos;
1012         T *dst, *item;
1013
1014         /* If we are given a negative position to remove at then
1015          * treat it as a position relative to the length. */
1016         if ( pos < 0 )
1017                 pos = BaseTable::tabLen + pos;
1018
1019         /* The first position after the last item deleted. */
1020         endPos = pos + len;
1021
1022         /* The new data length. */
1023         newLen = BaseTable::tabLen - len;
1024
1025         /* The place in the data we are deleting at. */
1026         dst = BaseTable::data + pos;
1027
1028         /* Call Destructors. */
1029         item = dst;
1030         for ( long i = 0; i < len; i += 1, item += 1 )
1031                 item->~T();
1032
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);
1037
1038         /* Shrink the data if necessary. */
1039         downResize( newLen );
1040
1041         /* Set the new data length. */
1042         BaseTable::tabLen = newLen;
1043 }
1044
1045 /**
1046  * \brief Insert len elements at position pos.
1047  *
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
1052  * of the vector.
1053  */
1054 template<class T, class Resize> void Vector<T, Resize>::
1055                 insert(long pos, const T *val, long len)
1056 {
1057         /* If we are given a negative position to insert at then
1058          * treat it as a position relative to the length. */
1059         if ( pos < 0 )
1060                 pos = BaseTable::tabLen + pos;
1061
1062         /* Calculate the new length. */
1063         long newLen = BaseTable::tabLen + len;
1064
1065         /* Up resize, we are growing. */
1066         upResize( newLen );
1067
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));
1072         }
1073
1074         /* Copy data in element by element. */
1075         T *dst = BaseTable::data + pos;
1076         const T *src = val;
1077         for ( long i = 0; i < len; i++, dst++, src++ )
1078                 new(dst) T(*src);
1079
1080         /* Set the new length. */
1081         BaseTable::tabLen = newLen;
1082 }
1083
1084 /**
1085  * \brief Insert len copies of item at position pos.
1086  *
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
1091  * of the vector.
1092  */
1093 template<class T, class Resize> void Vector<T, Resize>::
1094                 insertDup(long pos, const T &item, long len)
1095 {
1096         /* If we are given a negative position to insert at then
1097          * treat it as a position relative to the length. */
1098         if ( pos < 0 )
1099                 pos = BaseTable::tabLen + pos;
1100
1101         /* Calculate the new length. */
1102         long newLen = BaseTable::tabLen + len;
1103
1104         /* Up resize, we are growing. */
1105         upResize( newLen );
1106
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));
1111         }
1112
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++ )
1116                 new(dst) T(item);
1117
1118         /* Set the new length. */
1119         BaseTable::tabLen = newLen;
1120 }
1121
1122 /**
1123  * \brief Insert len new elements using the default constructor.
1124  *
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.
1129  */
1130 template<class T, class Resize> void Vector<T, Resize>::
1131                 insertNew(long pos, long len)
1132 {
1133         /* If we are given a negative position to insert at then
1134          * treat it as a position relative to the length. */
1135         if ( pos < 0 )
1136                 pos = BaseTable::tabLen + pos;
1137
1138         /* Calculate the new length. */
1139         long newLen = BaseTable::tabLen + len;
1140
1141         /* Up resize, we are growing. */
1142         upResize( newLen );
1143
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));
1148         }
1149
1150         /* Init new data with default constructors. */
1151         T *dst = BaseTable::data + pos;
1152         for ( long i = 0; i < len; i++, dst++ )
1153                 new(dst) T();
1154
1155         /* Set the new length. */
1156         BaseTable::tabLen = newLen;
1157 }
1158
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)
1164 {
1165         /* Calculate the new length. */
1166         long newLen = BaseTable::tabLen + len;
1167
1168         /* Up resize, we are growing. */
1169         upResize( newLen );
1170
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));
1175         }
1176
1177         /* Save the new length. */
1178         BaseTable::tabLen = newLen;
1179 }
1180
1181 #ifdef AAPL_NAMESPACE
1182 }
1183 #endif
1184
1185 #endif /* _AAPL_VECTOR_H */