CppAD: A C++ Algorithmic Differentiation Package 20110419
vector.hpp
Go to the documentation of this file.
00001 /* $Id$ */
00002 # ifndef CPPAD_VECTOR_INCLUDED
00003 # define CPPAD_VECTOR_INCLUDED
00004 
00005 /* --------------------------------------------------------------------------
00006 CppAD: C++ Algorithmic Differentiation: Copyright (C) 2003-08 Bradley M. Bell
00007 
00008 CppAD is distributed under multiple licenses. This distribution is under
00009 the terms of the 
00010                     Common Public License Version 1.0.
00011 
00012 A copy of this license is included in the COPYING file of this distribution.
00013 Please visit http://www.coin-or.org/CppAD/ for information on other licenses.
00014 -------------------------------------------------------------------------- */
00015 
00016 /*
00017 $begin CppAD_vector$$
00018 $spell
00019         cppad.hpp
00020         Bool
00021         resize
00022         cout
00023         endl
00024         std
00025         Cpp
00026         const
00027         vec
00028         ostream
00029         elem
00030 $$
00031 
00032 $index vector, CppAD template class$$
00033 $index class, template CppAD vector$$
00034 $index template, CppAD vector class$$
00035 
00036 $section The CppAD::vector Template Class$$
00037 
00038 $head Syntax$$
00039 $code # include <cppad/vector.hpp>$$
00040 
00041 
00042 
00043 $head Description$$
00044 The include file $code cppad/vector.hpp$$ defines the
00045 vector template class $code CppAD::vector$$.
00046 This is a $xref/SimpleVector/$$ template class and in addition
00047 it has the features listed below:
00048 
00049 $head Include$$
00050 The file $code cppad/vector.hpp$$ is included by $code cppad/cppad.hpp$$
00051 but it can also be included separately with out the rest of the 
00052 CppAD include files.
00053 
00054 $head Assignment$$
00055 $index assignment, CppAD vector$$
00056 If $icode x$$ and $icode y$$ are 
00057 $codei%CppAD::vector<%Scalar%>%$$ objects,
00058 $codei%
00059         %y% = %x%
00060 %$$
00061 has all the properties listed for a
00062 $xref/SimpleVector/Assignment/simple vector assignment/$$
00063 plus the following:
00064 $pre
00065 
00066 $$
00067 The $code CppAD::vector$$ template class will check that
00068 the size of $icode x$$ is equal to the size of $icode y$$
00069 before doing the assignment.
00070 If the sizes are not equal, $code CppAD::vector$$ will use
00071 $xref/ErrorHandler/$$
00072 to generate an appropriate error report.
00073 $pre
00074 
00075 $$
00076 A reference to the vector $icode y$$ is returned.
00077 An example use of this reference is in multiple assignments of the form
00078 $codei%
00079         %z% = %y% = %x%
00080 %$$
00081 
00082 $head Element Access$$
00083 $index [], CppAD vector$$
00084 $index vector, [] CppAD$$
00085 If $icode x$$ is a $codei%CppAD::vector<%Scalar%>%$$ object
00086 and $code i$$ has type $code size_t$$,
00087 $codei%
00088         %x%[%i%]
00089 %$$
00090 has all the properties listed for a
00091 $xref/SimpleVector/Element Access/simple vector element access/$$
00092 plus the following:
00093 $pre
00094 
00095 $$
00096 The object $codei%%x%[%i%]%$$ has type $icode Scalar$$
00097 (is not possibly a different type that can be converted to $icode Scalar$$).
00098 $pre
00099 
00100 $$
00101 If $icode i$$ is not less than the size of the $icode x$$,
00102 $code CppAD::vector$$ will use
00103 $xref/ErrorHandler/$$
00104 to generate an appropriate error report.
00105 
00106 $head push_back$$
00107 $index push_back, CppAD vector$$
00108 $index vector, CppAD push_back$$
00109 If $icode x$$ is a $codei%CppAD::vector<%Scalar%>%$$ object
00110 with size equal to $icode n$$ and
00111 $icode s$$ has type $icode Scalar$$,
00112 $codei%
00113         %x%.push_back(%s%)
00114 %$$
00115 extends the vector $icode x$$ so that its new size is $icode n$$ plus one
00116 and $codei%%x%[%n%]%$$ is equal to $icode s$$
00117 (equal in the sense of the $icode Scalar$$ assignment operator).
00118 
00119 
00120 $head push_vector$$
00121 $index push_vector, CppAD$$
00122 $index vector, CppAD push$$
00123 If $icode x$$ is a $codei%CppAD::vector<%Scalar%>%$$ object
00124 with size equal to $icode n$$ and
00125 $icode v$$ is a $cref/simple vector/SimpleVector/$$
00126 with elements of type $icode Scalar$$ and size $icode m$$,
00127 $codei%
00128         %x%.push_vector(%v%)
00129 %$$
00130 extends the vector $icode x$$ so that its new size is $icode%n%+%m%$$
00131 and $icode%x%[%n% + %i%]%$$ is equal to $icode%v%[%i%]%$$
00132 for $icode%i = 1 , ... , m-1%$$
00133 (equal in the sense of the $icode Scalar$$ assignment operator).
00134 
00135 $head Output$$
00136 If $icode x$$ is a $codei%CppAD::vector<%Scalar%>%$$ object
00137 and $icode os$$ is an $code std::ostream$$,
00138 and the operation
00139 $codei%
00140         %os% << %x%
00141 %$$
00142 will output the vector $icode x$$ to the standard
00143 output stream $icode os$$.
00144 The elements of $icode x$$ are enclosed at the beginning by a
00145 $code {$$ character,
00146 they are separated by $code ,$$ characters,
00147 and they are enclosed at the end by $code }$$ character.
00148 It is assumed by this operation that if $icode e$$
00149 is an object with type $icode Scalar$$,
00150 $codei%
00151         %os% << %e%
00152 %$$
00153 will output the value $icode e$$ to the standard
00154 output stream $icode os$$.
00155 
00156 $head resize$$
00157 If the $code resize$$ member function is called with argument
00158 value zero, all memory allocated for the vector will be freed.
00159 The can be useful when using very large vectors
00160 and when checking for memory leaks (and there are global vectors).
00161 
00162 $head vectorBool$$
00163 $index vectorBool$$
00164 The file $code <cppad/vector.hpp>$$ also defines the class
00165 $code CppAD::vectorBool$$.
00166 This has the same specifications as $code CppAD::vector<bool>$$ 
00167 with the following exceptions
00168 
00169 $list number $$
00170 The class $code vectorBool$$ conserves on memory
00171 (on the other hand, $code CppAD::vector<bool>$$ is expected to be faster
00172 than $code vectorBool$$).
00173 
00174 $lnext
00175 The $code CppAD::vectorBool$$ output operator
00176 prints each boolean value as 
00177 a $code 0$$ for false,
00178 a $code 1$$ for true, 
00179 and does not print any other output; i.e.,
00180 the vector is written a long sequence of zeros and ones with no
00181 surrounding $code {$$, $code }$$ and with no separating commas or spaces. 
00182 
00183 $lnext
00184 If $icode x$$ has type $code vectorBool$$
00185 and $icode i$$ has type $code size_t$$,
00186 the element access value $codei%%x%[%i%]%$$ has an unspecified type
00187 (referred to here as $icode elementType$$)
00188 that can be implicitly converted to $code bool$$.
00189 The return value of the assignment operator
00190 $codei%
00191         %x%[%i%] = %y%
00192 %$$
00193 also has type $icode elementType$$. Thus, if $icode z$$
00194 has type $code bool$$, the syntax
00195 $codei%
00196         %z% = %x%[%i%] = %y%
00197 %$$
00198 is valid.
00199 
00200 $lend
00201 
00202 $head Example$$
00203 $children%
00204         example/cppad_vector.cpp%
00205         example/vector_bool.cpp
00206 %$$
00207 The files
00208 $xref/CppAD_vector.cpp/$$ and
00209 $xref/vectorBool.cpp/$$ each
00210 contain an example and test of this template class.
00211 They return true if they succeed and false otherwise.
00212 
00213 $head Exercise$$
00214 $index exercise, CppAD::vector$$
00215 Create and run a program that contains the following code:
00216 $codep
00217         CppAD::vector<double> x(3);
00218         size_t i;
00219         for(i = 0; i < 3; i++)
00220                 x[i] = 4. - i;
00221         std::cout << "x = " << x << std::endl;
00222 $$
00223 
00224 $end
00225 
00226 
00227 $end
00228 
00229 ------------------------------------------------------------------------ 
00230 */
00231 
00232 # include <cstddef>
00233 # include <iostream>
00234 # include <limits>
00235 # include <cppad/local/cppad_assert.hpp>
00236 # include <cppad/track_new_del.hpp>
00237 # include <cppad/check_simple_vector.hpp>
00238 
00239 # ifndef CPPAD_NULL
00240 # define CPPAD_NULL 0
00241 # endif
00242 
00243 namespace CppAD { //  BEGIN CppAD namespace
00244 
00245 // ------------------ CppAD::vector<Type> ----------------------------------
00246 
00247 template <class Type>
00248 class vector {
00249 private:
00250         size_t capacity;
00251         size_t length;
00252         Type   * data;
00253 public:
00254         // type of the elements in the vector
00255         typedef Type value_type;
00256 
00257         // default constructor
00258         inline vector(void) : capacity(0), length(0) , data(CPPAD_NULL)
00259         { }
00260         // constructor with a specified size
00261         inline vector(size_t n) : capacity(n), length(n)
00262         {
00263                 data = CPPAD_NULL;
00264                 if( length > 0 )
00265                         data = CPPAD_TRACK_NEW_VEC(capacity, data);
00266         }
00267         // copy constructor
00268         inline vector(const vector &x) : capacity(x.length), length(x.length)
00269         {       size_t i;
00270                 data = CPPAD_NULL;
00271                 if( length > 0 )
00272                         data = CPPAD_TRACK_NEW_VEC(capacity, data);
00273 
00274                 for(i = 0; i < length; i++)
00275                         data[i] = x.data[i];
00276         }
00277         // destructor
00278         ~vector(void)
00279         {       if( data != CPPAD_NULL )
00280                         CPPAD_TRACK_DEL_VEC(data); 
00281         }
00282 
00283         // size function
00284         inline size_t size(void) const
00285         {       return length; }
00286 
00287         // resize function
00288         inline void resize(size_t n)
00289         {       length = n;
00290                 if( (capacity >= n) & (n > 0)  )
00291                         return;
00292                 if( data != CPPAD_NULL  )
00293                         CPPAD_TRACK_DEL_VEC(data);
00294                 capacity = n;
00295                 if( capacity == 0 )
00296                         data = CPPAD_NULL;
00297                 else    data = CPPAD_TRACK_NEW_VEC(capacity, data);
00298         }
00299         // assignment operator
00300         inline vector & operator=(const vector &x)
00301         {       size_t i;
00302                 CPPAD_ASSERT_KNOWN(
00303                         length == x.length ,
00304                         "size miss match in assignment operation"
00305                 );
00306                 for(i = 0; i < length; i++)
00307                         data[i] = x.data[i];
00308                 return *this;
00309         }
00310         // non-constant element access
00311         Type & operator[](size_t i)
00312         {       CPPAD_ASSERT_KNOWN(
00313                         i < length,
00314                         "vector index greater than or equal vector size"
00315                 );
00316                 return data[i]; 
00317         }
00318         // constant element access
00319         const Type & operator[](size_t i) const
00320         {       CPPAD_ASSERT_KNOWN(
00321                         i < length,
00322                         "vector index greater than or equal vector size"
00323                 );
00324                 return data[i]; 
00325         }
00326         // add scalar to the back of the array
00327         void push_back(const Type &s)
00328         {       CPPAD_ASSERT_UNKNOWN( length <= capacity );
00329                 if( length + 1 > capacity )
00330                 {       // allocate more capacity
00331                         if( capacity == 0 )
00332                                 capacity = 2;
00333                         else    capacity = 2 * length;
00334                         data = CPPAD_TRACK_EXTEND(capacity, length, data);
00335                 }
00336                 data[length++] = s;
00337                 CPPAD_ASSERT_UNKNOWN( length <= capacity );
00338         }
00339 
00340         // add vector to the back of the array
00341         // (Cannot use push_back becasue MS V++ 7.1 does not resolve
00342         // to non-template member function when scalar is used.)
00343         template <class Vector>
00344         void push_vector(const Vector &v)
00345         {       CheckSimpleVector<Type, Vector>();
00346                 size_t m = v.size();
00347                 CPPAD_ASSERT_UNKNOWN( length <= capacity );
00348                 if( length + m > capacity )
00349                 {       // allocate more capacity
00350                         capacity = length + m;
00351                         data     = CPPAD_TRACK_EXTEND(capacity, length, data);
00352                 }
00353                 size_t i;
00354                 for(i = 0; i < m; i++)
00355                         data[length++] = v[i];
00356                 CPPAD_ASSERT_UNKNOWN( length <= capacity );
00357         }
00358 };
00359 
00360 // output operator
00361 template <class Type>
00362 inline std::ostream& operator << (
00363         std::ostream              &os  , 
00364         const CppAD::vector<Type> &vec )
00365 {       size_t i = 0;
00366         size_t n = vec.size();
00367 
00368         os << "{ ";
00369         while(i < n)
00370         {       os << vec[i++]; 
00371                 if( i < n )
00372                         os << ", ";
00373         }
00374         os << " }";
00375         return os;
00376 }
00377 
00378 /*
00379 --------------------------- vectorBool -------------------------------------
00380 */
00381 class vectorBoolElement {
00382         typedef size_t UnitType;
00383 private:
00384         UnitType *unit;
00385         UnitType mask;
00386 public:
00387         vectorBoolElement(UnitType *unit_, UnitType mask_)
00388         : unit(unit_) , mask(mask_)
00389         { }
00390         vectorBoolElement(const vectorBoolElement &e)
00391         : unit(e.unit) , mask(e.mask)
00392         { }
00393         operator bool() const
00394         {       return (*unit & mask) != 0; }
00395         vectorBoolElement& operator=(bool bit)
00396         {       if(bit)
00397                         *unit |= mask;
00398                 else    *unit &= ~mask;
00399                 return *this;
00400         } 
00401         vectorBoolElement& operator=(const vectorBoolElement &e)
00402         {       if( *(e.unit) & e.mask )
00403                         *unit |= mask;
00404                 else    *unit &= ~mask;
00405                 return *this;
00406         } 
00407 };
00408 
00409 class vectorBool {
00410         typedef size_t UnitType;
00411 private:
00412         static const  size_t BitPerUnit 
00413                 = std::numeric_limits<UnitType>::digits;
00414         size_t    nunit;
00415         size_t    length;
00416         UnitType *data;
00417 public:
00418         // type of the elements in the vector
00419         typedef bool value_type;
00420 
00421         // default constructor
00422         inline vectorBool(void) : nunit(0), length(0), data(CPPAD_NULL)
00423         { }
00424         // constructor with a specified size
00425         inline vectorBool(size_t n) : nunit(0), length(0), data(CPPAD_NULL)
00426         {       if( n == 0 )
00427                         data = CPPAD_NULL;
00428                 else 
00429                 {       nunit    = (n - 1) / BitPerUnit + 1;
00430                         length   = n;
00431                         data     = CPPAD_TRACK_NEW_VEC(nunit, data);
00432                 }
00433         }
00434         // copy constructor
00435         inline vectorBool(const vectorBool &v) 
00436         : nunit(v.nunit), length(v.length)
00437         {       size_t i;
00438                 data = CPPAD_NULL;
00439                 if( nunit > 0 )
00440                         data = CPPAD_TRACK_NEW_VEC(nunit, data);
00441 
00442                 for(i = 0; i < nunit; i++)
00443                         data[i] = v.data[i];
00444         }
00445         // destructor
00446         ~vectorBool(void)
00447         {       if( data != CPPAD_NULL )
00448                         CPPAD_TRACK_DEL_VEC(data);
00449         }
00450 
00451         // size function
00452         inline size_t size(void) const
00453         {       return length; }
00454 
00455         // resize function
00456         inline void resize(size_t n)
00457         {       length = n;
00458                 if( (nunit * BitPerUnit >= n) & (n > 0) )
00459                         return;
00460                 if( data != CPPAD_NULL )
00461                         CPPAD_TRACK_DEL_VEC(data);
00462                 if( n == 0 )
00463                 {       nunit = 0;
00464                         data = CPPAD_NULL;
00465                 }
00466                 else
00467                 {       nunit    = (n - 1) / BitPerUnit + 1;
00468                         data     = CPPAD_TRACK_NEW_VEC(nunit, data);
00469                 }
00470         }
00471         // assignment operator
00472         inline vectorBool & operator=(const vectorBool &v)
00473         {       size_t i;
00474                 CPPAD_ASSERT_KNOWN(
00475                         length == v.length ,
00476                         "size miss match in assignment operation"
00477                 );
00478                 CPPAD_ASSERT_UNKNOWN( nunit == v.nunit );
00479                 for(i = 0; i < nunit; i++)
00480                         data[i] = v.data[i];
00481                 return *this;
00482         }
00483         // non-constant element access
00484         vectorBoolElement operator[](size_t k)
00485         {       size_t i, j;
00486                 CPPAD_ASSERT_KNOWN(
00487                         k < length,
00488                         "vector index greater than or equal vector size"
00489                 );
00490                 i    = k / BitPerUnit;
00491                 j    = k - i * BitPerUnit;
00492                 return vectorBoolElement(data + i , UnitType(1) << j );
00493         }
00494         // constant element access
00495         bool operator[](size_t k) const
00496         {       size_t i, j;
00497                 UnitType unit;
00498                 UnitType mask;
00499                 CPPAD_ASSERT_KNOWN(
00500                         k < length,
00501                         "vector index greater than or equal vector size"
00502                 );
00503                 i    = k / BitPerUnit;
00504                 j    = k - i * BitPerUnit;
00505                 unit = data[i];
00506                 mask = UnitType(1) << j;
00507                 return (unit & mask) != 0;
00508         }
00509         // add to the back of the array
00510         void push_back(bool bit)
00511         {       size_t i, j;
00512                 UnitType mask;
00513                 CPPAD_ASSERT_UNKNOWN( length <= nunit * BitPerUnit );
00514                 if( length == nunit * BitPerUnit )
00515                 {       // allocate another unit
00516                         data = CPPAD_TRACK_EXTEND(nunit+1, nunit, data);
00517                         nunit++;
00518                 }
00519                 i    = length / BitPerUnit;
00520                 j    = length - i * BitPerUnit;
00521                 mask = UnitType(1) << j;
00522                 if( bit )
00523                         data[i] |= mask;
00524                 else    data[i] &= ~mask;
00525                 length++;
00526         }
00527         // add vector to back of array
00528         void push_vector(const vectorBool &v)
00529         {       size_t i, j, k;
00530                 UnitType mask;
00531                 bool bit;
00532                 CPPAD_ASSERT_UNKNOWN( length <= nunit * BitPerUnit );
00533                 CPPAD_ASSERT_UNKNOWN( v.length <= v.nunit * BitPerUnit );
00534                 if( length + v.length >= nunit * BitPerUnit )
00535                 {       // allocate enough space
00536                         data = CPPAD_TRACK_EXTEND(nunit+v.nunit, nunit, data);
00537                         nunit += v.nunit;
00538                 }
00539                 for(k = 0; k < v.size(); k++)
00540                 {       i    = length / BitPerUnit;
00541                         j    = length - i * BitPerUnit;
00542                         bit  = v[k];
00543                         mask = UnitType(1) << j;
00544                         if( bit )
00545                                 data[i] |= mask;
00546                         else    data[i] &= ~mask;
00547                         length++;
00548                 }
00549                 CPPAD_ASSERT_UNKNOWN( length <= nunit * BitPerUnit );
00550         }
00551 };
00552 
00553 // output operator
00554 inline std::ostream& operator << (
00555         std::ostream     &os  , 
00556         const vectorBool &v   )
00557 {       size_t i = 0;
00558         size_t n = v.size();
00559 
00560         while(i < n)
00561                 os << v[i++]; 
00562         return os;
00563 }
00564 
00565 } // END CppAD namespace
00566 
00567 
00568 # endif