CppAD: A C++ Algorithmic Differentiation Package 20110419
|
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