aapl/vector.h

   1 /*
   2  *  Copyright 2002, 2006 Adrian Thurston <thurston@cs.queensu.ca>
   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         /* Performs a shallow copy of another vector into this vector. If this
 110          * vector is non-empty then its contents are lost (not freed). */
 111         void shallowCopy( const 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 #if 0
 474 /* Create a vector with an intial number of elements and size. */
 475 template<class T, class Resize> Vector<T, Resize>::
 476                 Vector( long size, long allocLen )
 477 {
 478         /* Allocate the space if we are given a positive allocLen. */
 479         BaseTable::allocLen = allocLen;
 480         if ( allocLen > 0 ) {
 481                 BaseTable::data = (T*) malloc(sizeof(T) * BaseTable::allocLen);
 482                 if ( BaseTable::data == 0 )
 483                         throw std::bad_alloc();
 484         }
 485
 486         /* Grow to the size specified. If we did not have enough space
 487          * allocated that is ok. Table will be grown to right size. */
 488         setAsNew( size );
 489 }
 490 #endif
 491
 492 /* Init a vector iterator with just a vector. */
 493 template <class T, class Resize> Vector<T, Resize>::Iter::Iter( const Vector &v )
 494 {
 495         if ( v.tabLen == 0 )
 496                 ptr = ptrBeg = ptrEnd = 0;
 497         else {
 498                 ptr = v.data;
 499                 ptrBeg = v.data-1;
 500                 ptrEnd = v.data+v.tabLen;
 501         }
 502 }
 503
 504 /* Init a vector iterator with the first of a vector. */
 505 template <class T, class Resize> Vector<T, Resize>::Iter::Iter(
 506                 const IterFirst &vf )
 507 {
 508         if ( vf.v.tabLen == 0 )
 509                 ptr = ptrBeg = ptrEnd = 0;
 510         else {
 511                 ptr = vf.v.data;
 512                 ptrBeg = vf.v.data-1;
 513                 ptrEnd = vf.v.data+vf.v.tabLen;
 514         }
 515 }
 516
 517 /* Init a vector iterator with the last of a vector. */
 518 template <class T, class Resize> Vector<T, Resize>::Iter::Iter(
 519                 const IterLast &vl )
 520 {
 521         if ( vl.v.tabLen == 0 )
 522                 ptr = ptrBeg = ptrEnd = 0;
 523         else {
 524                 ptr = vl.v.data+vl.v.tabLen-1;
 525                 ptrBeg = vl.v.data-1;
 526                 ptrEnd = vl.v.data+vl.v.tabLen;
 527         }
 528 }
 529
 530 /* Init a vector iterator with the next of some other iterator. */
 531 template <class T, class Resize> Vector<T, Resize>::Iter::Iter(
 532                 const IterNext &vn )
 533 :
 534         ptr(vn.i.ptr+1),
 535         ptrBeg(vn.i.ptrBeg),
 536         ptrEnd(vn.i.ptrEnd)
 537 {
 538 }
 539
 540 /* Init a vector iterator with the prev of some other iterator. */
 541 template <class T, class Resize> Vector<T, Resize>::Iter::Iter(
 542                 const IterPrev &vp )
 543 :
 544         ptr(vp.i.ptr-1),
 545         ptrBeg(vp.i.ptrBeg),
 546         ptrEnd(vp.i.ptrEnd)
 547 {
 548 }
 549
 550 /* Set a vector iterator with some vector. */
 551 template <class T, class Resize> typename Vector<T, Resize>::Iter &
 552                 Vector<T, Resize>::Iter::operator=( const Vector &v )
 553 {
 554         if ( v.tabLen == 0 )
 555                 ptr = ptrBeg = ptrEnd = 0;
 556         else {
 557                 ptr = v.data;
 558                 ptrBeg = v.data-1;
 559                 ptrEnd = v.data+v.tabLen;
 560         }
 561         return *this;
 562 }
 563
 564 /* Set a vector iterator with the first element in a vector. */
 565 template <class T, class Resize> typename Vector<T, Resize>::Iter &
 566                 Vector<T, Resize>::Iter::operator=( const IterFirst &vf )
 567 {
 568         if ( vf.v.tabLen == 0 )
 569                 ptr = ptrBeg = ptrEnd = 0;
 570         else {
 571                 ptr = vf.v.data;
 572                 ptrBeg = vf.v.data-1;
 573                 ptrEnd = vf.v.data+vf.v.tabLen;
 574         }
 575         return *this;
 576 }
 577
 578 /* Set a vector iterator with the last element in a vector. */
 579 template <class T, class Resize> typename Vector<T, Resize>::Iter &
 580                 Vector<T, Resize>::Iter::operator=( const IterLast &vl )
 581 {
 582         if ( vl.v.tabLen == 0 )
 583                 ptr = ptrBeg = ptrEnd = 0;
 584         else {
 585                 ptr = vl.v.data+vl.v.tabLen-1;
 586                 ptrBeg = vl.v.data-1;
 587                 ptrEnd = vl.v.data+vl.v.tabLen;
 588         }
 589         return *this;
 590 }
 591
 592 /* Set a vector iterator with the next of some other iterator. */
 593 template <class T, class Resize> typename Vector<T, Resize>::Iter &
 594                 Vector<T, Resize>::Iter::operator=( const IterNext &vn )
 595 {
 596         ptr = vn.i.ptr+1;
 597         ptrBeg = vn.i.ptrBeg;
 598         ptrEnd = vn.i.ptrEnd;
 599         return *this;
 600 }
 601
 602 /* Set a vector iterator with the prev of some other iterator. */
 603 template <class T, class Resize> typename Vector<T, Resize>::Iter &
 604                 Vector<T, Resize>::Iter::operator=( const IterPrev &vp )
 605 {
 606         ptr = vp.i.ptr-1;
 607         ptrBeg = vp.i.ptrBeg;
 608         ptrEnd = vp.i.ptrEnd;
 609         return *this;
 610 }
 611
 612 /**
 613  * \brief Forget all elements in the vector.
 614  *
 615  * The contents of the vector are reset to null without without the space
 616  * being freed.
 617  */
 618 template<class T, class Resize> void Vector<T, Resize>::
 619                 abandon()
 620 {
 621         BaseTable::data = 0;
 622         BaseTable::tabLen = 0;
 623         BaseTable::allocLen = 0;
 624 }
 625
 626 /**
 627  * \brief Shallow copy another vector into this vector.
 628  *
 629  * The dynamic array of the other vector is copied into this vector by
 630  * reference. If this vector is non-empty then its contents are lost. This
 631  * routine must be used with care. After a shallow copy one vector should
 632  * abandon its contents to prevent both destructors from attempting to free
 633  * the common array.
 634  */
 635 template<class T, class Resize> void Vector<T, Resize>::
 636                 shallowCopy( const Vector &v )
 637 {
 638         BaseTable::data = v.data;
 639         BaseTable::tabLen = v.tabLen;
 640         BaseTable::allocLen = v.allocLen;
 641 }
 642
 643 /**
 644  * \brief Deep copy another vector into this vector.
 645  *
 646  * Copies the entire contents of the other vector into this vector. Any
 647  * existing contents are first deleted. Equivalent to setAs.
 648  *
 649  * \returns A reference to this.
 650  */
 651 template<class T, class Resize> Vector<T, Resize> &Vector<T, Resize>::
 652                 operator=( const Vector &v )
 653 {
 654         setAs(v.data, v.tabLen);
 655         return *this;
 656 }
 657
 658 /* Up resize the data for len elements using Resize::upResize to tell us the
 659  * new tabLen. Reads and writes allocLen. Does not read or write tabLen. */
 660 template<class T, class Resize> void Vector<T, Resize>::
 661                 upResize(long len)
 662 {
 663         /* Ask the resizer what the new tabLen will be. */
 664         long newLen = Resize::upResize(BaseTable::allocLen, len);
 665
 666         /* Did the data grow? */
 667         if ( newLen > BaseTable::allocLen ) {
 668                 BaseTable::allocLen = newLen;
 669                 if ( BaseTable::data != 0 ) {
 670                         /* Table exists already, resize it up. */
 671                         BaseTable::data = (T*) realloc( BaseTable::data, sizeof(T) * newLen );
 672                         if ( BaseTable::data == 0 )
 673                                 throw std::bad_alloc();
 674                 }
 675                 else {
 676                         /* Create the data. */
 677                         BaseTable::data = (T*) malloc( sizeof(T) * newLen );
 678                         if ( BaseTable::data == 0 )
 679                                 throw std::bad_alloc();
 680                 }
 681         }
 682 }
 683
 684 /* Down resize the data for len elements using Resize::downResize to determine
 685  * the new tabLen. Reads and writes allocLen. Does not read or write tabLen. */
 686 template<class T, class Resize> void Vector<T, Resize>::
 687                 downResize(long len)
 688 {
 689         /* Ask the resizer what the new tabLen will be. */
 690         long newLen = Resize::downResize( BaseTable::allocLen, len );
 691
 692         /* Did the data shrink? */
 693         if ( newLen < BaseTable::allocLen ) {
 694                 BaseTable::allocLen = newLen;
 695                 if ( newLen == 0 ) {
 696                         /* Simply free the data. */
 697                         free( BaseTable::data );
 698                         BaseTable::data = 0;
 699                 }
 700                 else {
 701                         /* Not shrinking to size zero, realloc it to the smaller size. */
 702                         BaseTable::data = (T*) realloc( BaseTable::data, sizeof(T) * newLen );
 703                         if ( BaseTable::data == 0 )
 704                                 throw std::bad_alloc();
 705                 }
 706         }
 707 }
 708
 709 /**
 710  * \brief Perform a deep copy of the vector.
 711  *
 712  * The contents of the other vector are copied into this vector. This vector
 713  * gets the same allocation size as the other vector. All items are copied
 714  * using the element's copy constructor.
 715  */
 716 template<class T, class Resize> Vector<T, Resize>::
 717                 Vector(const Vector<T, Resize> &v)
 718 {
 719         BaseTable::tabLen = v.tabLen;
 720         BaseTable::allocLen = v.allocLen;
 721
 722         if ( BaseTable::allocLen > 0 ) {
 723                 /* Allocate needed space. */
 724                 BaseTable::data = (T*) malloc(sizeof(T) * BaseTable::allocLen);
 725                 if ( BaseTable::data == 0 )
 726                         throw std::bad_alloc();
 727
 728                 /* If there are any items in the src data, copy them in. */
 729                 T *dst = BaseTable::data, *src = v.data;
 730                 for (long pos = 0; pos < BaseTable::tabLen; pos++, dst++, src++ )
 731                         new(dst) T(*src);
 732         }
 733         else {
 734                 /* Nothing allocated. */
 735                 BaseTable::data = 0;
 736         }
 737 }
 738
 739 /** \fn Vector::~Vector()
 740  * \brief Free all memory used by the vector.
 741  *
 742  * The vector is reset to zero elements. Destructors are called on all
 743  * elements in the vector. The space allocated for the vector is freed.
 744  */
 745
 746
 747 /**
 748  * \brief Free all memory used by the vector.
 749  *
 750  * The vector is reset to zero elements. Destructors are called on all
 751  * elements in the vector. The space allocated for the vector is freed.
 752  */
 753 template<class T, class Resize> void Vector<T, Resize>::
 754                 empty()
 755 {
 756         if ( BaseTable::data != 0 ) {
 757                 /* Call All destructors. */
 758                 T *pos = BaseTable::data;
 759                 for ( long i = 0; i < BaseTable::tabLen; pos++, i++ )
 760                         pos->~T();
 761
 762                 /* Free the data space. */
 763                 free( BaseTable::data );
 764                 BaseTable::data = 0;
 765                 BaseTable::tabLen = BaseTable::allocLen = 0;
 766         }
 767 }
 768
 769 /**
 770  * \brief Set the contents of the vector to be len elements exactly.
 771  *
 772  * The vector becomes len elements in length. Destructors are called on any
 773  * existing elements in the vector. Copy constructors are used to place the
 774  * new elements in the vector.
 775  */
 776 template<class T, class Resize> void Vector<T, Resize>::
 777                 setAs(const T *val, long len)
 778 {
 779         /* Call All destructors. */
 780         long i;
 781         T *pos = BaseTable::data;
 782         for ( i = 0; i < BaseTable::tabLen; pos++, i++ )
 783                 pos->~T();
 784
 785         /* Adjust the allocated length. */
 786         if ( len < BaseTable::tabLen )
 787                 downResize( len );
 788         else if ( len > BaseTable::tabLen )
 789                 upResize( len );
 790
 791         /* Set the new data length to exactly len. */
 792         BaseTable::tabLen = len;
 793
 794         /* Copy data in. */
 795         T *dst = BaseTable::data;
 796         const T *src = val;
 797         for ( i = 0; i < len; i++, dst++, src++ )
 798                 new(dst) T(*src);
 799 }
 800
 801 /**
 802  * \brief Set the vector to len copies of item.
 803  *
 804  * The vector becomes len elements in length. Destructors are called on any
 805  * existing elements in the vector. The element's copy constructor is used to
 806  * copy the item into the vector.
 807  */
 808 template<class T, class Resize> void Vector<T, Resize>::
 809                 setAsDup(const T &item, long len)
 810 {
 811         /* Call All destructors. */
 812         T *pos = BaseTable::data;
 813         for ( long i = 0; i < BaseTable::tabLen; pos++, i++ )
 814                 pos->~T();
 815
 816         /* Adjust the allocated length. */
 817         if ( len < BaseTable::tabLen )
 818                 downResize( len );
 819         else if ( len > BaseTable::tabLen )
 820                 upResize( len );
 821
 822         /* Set the new data length to exactly len. */
 823         BaseTable::tabLen = len;
 824
 825         /* Copy item in one spot at a time. */
 826         T *dst = BaseTable::data;
 827         for ( long i = 0; i < len; i++, dst++ )
 828                 new(dst) T(item);
 829 }
 830
 831 /**
 832  * \brief Set the vector to exactly len new items.
 833  *
 834  * The vector becomes len elements in length. Destructors are called on any
 835  * existing elements in the vector. Default constructors are used to init the
 836  * new items.
 837  */
 838 template<class T, class Resize> void Vector<T, Resize>::
 839                 setAsNew(long len)
 840 {
 841         /* Call All destructors. */
 842         T *pos = BaseTable::data;
 843         for ( long i = 0; i < BaseTable::tabLen; pos++, i++ )
 844                 pos->~T();
 845
 846         /* Adjust the allocated length. */
 847         if ( len < BaseTable::tabLen )
 848                 downResize( len );
 849         else if ( len > BaseTable::tabLen )
 850                 upResize( len );
 851
 852         /* Set the new data length to exactly len. */
 853         BaseTable::tabLen = len;
 854
 855         /* Create items using default constructor. */
 856         T *dst = BaseTable::data;
 857         for ( long i = 0; i < len; i++, dst++ )
 858                 new(dst) T();
 859 }
 860
 861
 862 /**
 863  * \brief Replace len elements at position pos.
 864  *
 865  * If there are existing elements at the positions to be replaced, then
 866  * destructors are called before the space is used. Copy constructors are used
 867  * to place the elements into the vector. It is allowable for the pos and
 868  * length to specify a replacement that overwrites existing elements and
 869  * creates new ones.  If pos is greater than the length of the vector then
 870  * undefined behaviour results. If pos is negative, then it is treated as an
 871  * offset relative to the length of the vector.
 872  */
 873 template<class T, class Resize> void Vector<T, Resize>::
 874                 replace(long pos, const T *val, long len)
 875 {
 876         long endPos, i;
 877         T *item;
 878
 879         /* If we are given a negative position to replace at then
 880          * treat it as a position relative to the length. */
 881         if ( pos < 0 )
 882                 pos = BaseTable::tabLen + pos;
 883
 884         /* The end is the one past the last item that we want
 885          * to write to. */
 886         endPos = pos + len;
 887
 888         /* Make sure we have enough space. */
 889         if ( endPos > BaseTable::tabLen ) {
 890                 upResize( endPos );
 891
 892                 /* Delete any objects we need to delete. */
 893                 item = BaseTable::data + pos;
 894                 for ( i = pos; i < BaseTable::tabLen; i++, item++ )
 895                         item->~T();
 896
 897                 /* We are extending the vector, set the new data length. */
 898                 BaseTable::tabLen = endPos;
 899         }
 900         else {
 901                 /* Delete any objects we need to delete. */
 902                 item = BaseTable::data + pos;
 903                 for ( i = pos; i < endPos; i++, item++ )
 904                         item->~T();
 905         }
 906
 907         /* Copy data in using copy constructor. */
 908         T *dst = BaseTable::data + pos;
 909         const T *src = val;
 910         for ( i = 0; i < len; i++, dst++, src++ )
 911                 new(dst) T(*src);
 912 }
 913
 914 /**
 915  * \brief Replace at position pos with len copies of an item.
 916  *
 917  * If there are existing elements at the positions to be replaced, then
 918  * destructors are called before the space is used. The copy constructor is
 919  * used to place the element into this vector. It is allowable for the pos and
 920  * length to specify a replacement that overwrites existing elements and
 921  * creates new ones. If pos is greater than the length of the vector then
 922  * undefined behaviour results.  If pos is negative, then it is treated as an
 923  * offset relative to the length of the vector.
 924  */
 925 template<class T, class Resize> void Vector<T, Resize>::
 926                 replaceDup(long pos, const T &val, long len)
 927 {
 928         long endPos, i;
 929         T *item;
 930
 931         /* If we are given a negative position to replace at then
 932          * treat it as a position relative to the length. */
 933         if ( pos < 0 )
 934                 pos = BaseTable::tabLen + pos;
 935
 936         /* The end is the one past the last item that we want
 937          * to write to. */
 938         endPos = pos + len;
 939
 940         /* Make sure we have enough space. */
 941         if ( endPos > BaseTable::tabLen ) {
 942                 upResize( endPos );
 943
 944                 /* Delete any objects we need to delete. */
 945                 item = BaseTable::data + pos;
 946                 for ( i = pos; i < BaseTable::tabLen; i++, item++ )
 947                         item->~T();
 948
 949                 /* We are extending the vector, set the new data length. */
 950                 BaseTable::tabLen = endPos;
 951         }
 952         else {
 953                 /* Delete any objects we need to delete. */
 954                 item = BaseTable::data + pos;
 955                 for ( i = pos; i < endPos; i++, item++ )
 956                         item->~T();
 957         }
 958
 959         /* Copy data in using copy constructor. */
 960         T *dst = BaseTable::data + pos;
 961         for ( long i = 0; i < len; i++, dst++ )
 962                 new(dst) T(val);
 963 }
 964
 965 /**
 966  * \brief Replace at position pos with len new elements.
 967  *
 968  * If there are existing elements at the positions to be replaced, then
 969  * destructors are called before the space is used. The default constructor is
 970  * used to initialize the new elements. It is allowable for the pos and length
 971  * to specify a replacement that overwrites existing elements and creates new
 972  * ones. If pos is greater than the length of the vector then undefined
 973  * behaviour results. If pos is negative, then it is treated as an offset
 974  * relative to the length of the vector.
 975  */
 976 template<class T, class Resize> void Vector<T, Resize>::
 977                 replaceNew(long pos, long len)
 978 {
 979         long endPos, i;
 980         T *item;
 981
 982         /* If we are given a negative position to replace at then
 983          * treat it as a position relative to the length. */
 984         if ( pos < 0 )
 985                 pos = BaseTable::tabLen + pos;
 986
 987         /* The end is the one past the last item that we want
 988          * to write to. */
 989         endPos = pos + len;
 990
 991         /* Make sure we have enough space. */
 992         if ( endPos > BaseTable::tabLen ) {
 993                 upResize( endPos );
 994
 995                 /* Delete any objects we need to delete. */
 996                 item = BaseTable::data + pos;
 997                 for ( i = pos; i < BaseTable::tabLen; i++, item++ )
 998                         item->~T();
 999
1000                 /* We are extending the vector, set the new data length. */
1001                 BaseTable::tabLen = endPos;
1002         }
1003         else {
1004                 /* Delete any objects we need to delete. */
1005                 item = BaseTable::data + pos;
1006                 for ( i = pos; i < endPos; i++, item++ )
1007                         item->~T();
1008         }
1009
1010         /* Copy data in using copy constructor. */
1011         T *dst = BaseTable::data + pos;
1012         for ( long i = 0; i < len; i++, dst++ )
1013                 new(dst) T();
1014 }
1015
1016 /**
1017  * \brief Remove len elements at position pos.
1018  *
1019  * Destructor is called on all elements removed. Elements to the right of pos
1020  * are shifted len spaces to the left to take up the free space. If pos is
1021  * greater than or equal to the length of the vector then undefined behavior
1022  * results. If pos is negative then it is treated as an offset relative to the
1023  * length of the vector.
1024  */
1025 template<class T, class Resize> void Vector<T, Resize>::
1026                 remove(long pos, long len)
1027 {
1028         long newLen, lenToSlideOver, endPos;
1029         T *dst, *item;
1030
1031         /* If we are given a negative position to remove at then
1032          * treat it as a position relative to the length. */
1033         if ( pos < 0 )
1034                 pos = BaseTable::tabLen + pos;
1035
1036         /* The first position after the last item deleted. */
1037         endPos = pos + len;
1038
1039         /* The new data length. */
1040         newLen = BaseTable::tabLen - len;
1041
1042         /* The place in the data we are deleting at. */
1043         dst = BaseTable::data + pos;
1044
1045         /* Call Destructors. */
1046         item = dst;
1047         for ( long i = 0; i < len; i += 1, item += 1 )
1048                 item->~T();
1049
1050         /* Shift data over if necessary. */
1051         lenToSlideOver = BaseTable::tabLen - endPos;
1052         if ( len > 0 && lenToSlideOver > 0 )
1053                 memmove(dst, dst + len, sizeof(T)*lenToSlideOver);
1054
1055         /* Shrink the data if necessary. */
1056         downResize( newLen );
1057
1058         /* Set the new data length. */
1059         BaseTable::tabLen = newLen;
1060 }
1061
1062 /**
1063  * \brief Insert len elements at position pos.
1064  *
1065  * Elements in the vector from pos onward are shifted len spaces to the right.
1066  * The copy constructor is used to place the elements into this vector. If pos
1067  * is greater than the length of the vector then undefined behaviour results.
1068  * If pos is negative then it is treated as an offset relative to the length
1069  * of the vector.
1070  */
1071 template<class T, class Resize> void Vector<T, Resize>::
1072                 insert(long pos, const T *val, long len)
1073 {
1074         /* If we are given a negative position to insert at then
1075          * treat it as a position relative to the length. */
1076         if ( pos < 0 )
1077                 pos = BaseTable::tabLen + pos;
1078
1079         /* Calculate the new length. */
1080         long newLen = BaseTable::tabLen + len;
1081
1082         /* Up resize, we are growing. */
1083         upResize( newLen );
1084
1085         /* Shift over data at insert spot if needed. */
1086         if ( len > 0 && pos < BaseTable::tabLen ) {
1087                 memmove(BaseTable::data + pos + len, BaseTable::data + pos,
1088                                 sizeof(T)*(BaseTable::tabLen-pos));
1089         }
1090
1091         /* Copy data in element by element. */
1092         T *dst = BaseTable::data + pos;
1093         const T *src = val;
1094         for ( long i = 0; i < len; i++, dst++, src++ )
1095                 new(dst) T(*src);
1096
1097         /* Set the new length. */
1098         BaseTable::tabLen = newLen;
1099 }
1100
1101 /**
1102  * \brief Insert len copies of item at position pos.
1103  *
1104  * Elements in the vector from pos onward are shifted len spaces to the right.
1105  * The copy constructor is used to place the element into this vector. If pos
1106  * is greater than the length of the vector then undefined behaviour results.
1107  * If pos is negative then it is treated as an offset relative to the length
1108  * of the vector.
1109  */
1110 template<class T, class Resize> void Vector<T, Resize>::
1111                 insertDup(long pos, const T &item, long len)
1112 {
1113         /* If we are given a negative position to insert at then
1114          * treat it as a position relative to the length. */
1115         if ( pos < 0 )
1116                 pos = BaseTable::tabLen + pos;
1117
1118         /* Calculate the new length. */
1119         long newLen = BaseTable::tabLen + len;
1120
1121         /* Up resize, we are growing. */
1122         upResize( newLen );
1123
1124         /* Shift over data at insert spot if needed. */
1125         if ( len > 0 && pos < BaseTable::tabLen ) {
1126                 memmove(BaseTable::data + pos + len, BaseTable::data + pos,
1127                                 sizeof(T)*(BaseTable::tabLen-pos));
1128         }
1129
1130         /* Copy the data item in one at a time. */
1131         T *dst = BaseTable::data + pos;
1132         for ( long i = 0; i < len; i++, dst++ )
1133                 new(dst) T(item);
1134
1135         /* Set the new length. */
1136         BaseTable::tabLen = newLen;
1137 }
1138
1139 /**
1140  * \brief Insert len new elements using the default constructor.
1141  *
1142  * Elements in the vector from pos onward are shifted len spaces to the right.
1143  * Default constructors are used to init the new elements. If pos is off the
1144  * end of the vector then undefined behaviour results. If pos is negative then
1145  * it is treated as an offset relative to the length of the vector.
1146  */
1147 template<class T, class Resize> void Vector<T, Resize>::
1148                 insertNew(long pos, long len)
1149 {
1150         /* If we are given a negative position to insert at then
1151          * treat it as a position relative to the length. */
1152         if ( pos < 0 )
1153                 pos = BaseTable::tabLen + pos;
1154
1155         /* Calculate the new length. */
1156         long newLen = BaseTable::tabLen + len;
1157
1158         /* Up resize, we are growing. */
1159         upResize( newLen );
1160
1161         /* Shift over data at insert spot if needed. */
1162         if ( len > 0 && pos < BaseTable::tabLen ) {
1163                 memmove(BaseTable::data + pos + len, BaseTable::data + pos,
1164                                 sizeof(T)*(BaseTable::tabLen-pos));
1165         }
1166
1167         /* Init new data with default constructors. */
1168         T *dst = BaseTable::data + pos;
1169         for ( long i = 0; i < len; i++, dst++ )
1170                 new(dst) T();
1171
1172         /* Set the new length. */
1173         BaseTable::tabLen = newLen;
1174 }
1175
1176 /* Makes space for len items, Does not init the items in any way.  If pos is
1177  * greater than the length of the vector then undefined behaviour results.
1178  * Updates the length of the vector. */
1179 template<class T, class Resize> void Vector<T, Resize>::
1180                 makeRawSpaceFor(long pos, long len)
1181 {
1182         /* Calculate the new length. */
1183         long newLen = BaseTable::tabLen + len;
1184
1185         /* Up resize, we are growing. */
1186         upResize( newLen );
1187
1188         /* Shift over data at insert spot if needed. */
1189         if ( len > 0 && pos < BaseTable::tabLen ) {
1190                 memmove(BaseTable::data + pos + len, BaseTable::data + pos,
1191                         sizeof(T)*(BaseTable::tabLen-pos));
1192         }
1193
1194         /* Save the new length. */
1195         BaseTable::tabLen = newLen;
1196 }
1197
1198 #ifdef AAPL_NAMESPACE
1199 }
1200 #endif
1201
1202 #endif /* _AAPL_VECTOR_H */