CppAD: A C++ Algorithmic Differentiation Package
20130918
|
00001 /* $Id$ */ 00002 # ifndef CPPAD_VECTOR_INCLUDED 00003 # define CPPAD_VECTOR_INCLUDED 00004 00005 /* -------------------------------------------------------------------------- 00006 CppAD: C++ Algorithmic Differentiation: Copyright (C) 2003-14 Bradley M. Bell 00007 00008 CppAD is distributed under multiple licenses. This distribution is under 00009 the terms of the 00010 Eclipse 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 rvalues 00020 thread_alloc 00021 cppad.hpp 00022 Bool 00023 resize 00024 cout 00025 endl 00026 std 00027 Cpp 00028 const 00029 vec 00030 ostream 00031 elem 00032 $$ 00033 00034 $index vector, CppAD template class$$ 00035 $index class, template CppAD vector$$ 00036 $index template, CppAD vector class$$ 00037 00038 $section The CppAD::vector Template Class$$ 00039 00040 $head Syntax$$ 00041 $code # include <cppad/vector.hpp>$$ 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 $cref 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 capacity$$ 00055 If $icode x$$ is a $codei%CppAD::vector<%Scalar%>%$$, 00056 and $icode cap$$ is a $code size_t$$ object, 00057 $codei% 00058 %cap% = %x%.capacity() 00059 %$$ 00060 set $icode cap$$ to the number of $icode Scalar$$ objects that 00061 could fit in the memory currently allocated for $icode x$$. 00062 Note that 00063 $codei% 00064 %x%.size() <= %x%.capacity() 00065 %$$ 00066 00067 $head Assignment$$ 00068 $index assignment, CppAD vector$$ 00069 If $icode x$$ and $icode y$$ are 00070 $codei%CppAD::vector<%Scalar%>%$$ objects, 00071 $codei% 00072 %y% = %x% 00073 %$$ 00074 has all the properties listed for a 00075 $cref/simple vector assignment/SimpleVector/Assignment/$$ 00076 plus the following: 00077 00078 $subhead Check Size$$ 00079 The $code CppAD::vector$$ template class will check that 00080 the size of $icode x$$ is either zero or the size of $icode y$$ 00081 before doing the assignment. 00082 If this is not the case, $code CppAD::vector$$ will use 00083 $cref ErrorHandler$$ 00084 to generate an appropriate error report. 00085 Allowing for assignment to a vector with size zero makes the following 00086 code work: 00087 $codei% 00088 CppAD::vector<%Scalar%> %y%; 00089 %y% = %x%; 00090 %$$ 00091 00092 $subhead Return Reference$$ 00093 A reference to the vector $icode y$$ is returned. 00094 An example use of this reference is in multiple assignments of the form 00095 $codei% 00096 %z% = %y% = %x% 00097 %$$ 00098 00099 $subhead Move Semantics$$ 00100 If the C++ compiler supports move semantic rvalues using the $code &&$$ 00101 syntax, then it will be used during the vector assignment statement. 00102 This means that return values and other temporaries are not be copied, 00103 but rather pointers are transferred. 00104 00105 $head Element Access$$ 00106 $index [], CppAD vector$$ 00107 $index vector, [] CppAD$$ 00108 If $icode x$$ is a $codei%CppAD::vector<%Scalar%>%$$ object 00109 and $code i$$ has type $code size_t$$, 00110 $codei% 00111 %x%[%i%] 00112 %$$ 00113 has all the properties listed for a 00114 $cref/simple vector element access/SimpleVector/Element Access/$$ 00115 plus the following: 00116 $pre 00117 00118 $$ 00119 The object $icode%x%[%i%]%$$ has type $icode Scalar$$ 00120 (is not possibly a different type that can be converted to $icode Scalar$$). 00121 $pre 00122 00123 $$ 00124 If $icode i$$ is not less than the size of the $icode x$$, 00125 $code CppAD::vector$$ will use 00126 $cref ErrorHandler$$ 00127 to generate an appropriate error report. 00128 00129 $head push_back$$ 00130 $index push_back, CppAD vector$$ 00131 $index vector, CppAD push_back$$ 00132 If $icode x$$ is a $codei%CppAD::vector<%Scalar%>%$$ object 00133 with size equal to $icode n$$ and 00134 $icode s$$ has type $icode Scalar$$, 00135 $codei% 00136 %x%.push_back(%s%) 00137 %$$ 00138 extends the vector $icode x$$ so that its new size is $icode n$$ plus one 00139 and $icode%x%[%n%]%$$ is equal to $icode s$$ 00140 (equal in the sense of the $icode Scalar$$ assignment operator). 00141 00142 $head push_vector$$ 00143 $index push_vector, CppAD$$ 00144 $index vector, CppAD push$$ 00145 If $icode x$$ is a $codei%CppAD::vector<%Scalar%>%$$ object 00146 with size equal to $icode n$$ and 00147 $icode v$$ is a $cref/simple vector/SimpleVector/$$ 00148 with elements of type $icode Scalar$$ and size $icode m$$, 00149 $codei% 00150 %x%.push_vector(%v%) 00151 %$$ 00152 extends the vector $icode x$$ so that its new size is $icode%n%+%m%$$ 00153 and $icode%x%[%n% + %i%]%$$ is equal to $icode%v%[%i%]%$$ 00154 for $icode%i = 1 , ... , m-1%$$ 00155 (equal in the sense of the $icode Scalar$$ assignment operator). 00156 00157 $head Output$$ 00158 If $icode x$$ is a $codei%CppAD::vector<%Scalar%>%$$ object 00159 and $icode os$$ is an $code std::ostream$$, 00160 and the operation 00161 $codei% 00162 %os% << %x% 00163 %$$ 00164 will output the vector $icode x$$ to the standard 00165 output stream $icode os$$. 00166 The elements of $icode x$$ are enclosed at the beginning by a 00167 $code {$$ character, 00168 they are separated by $code ,$$ characters, 00169 and they are enclosed at the end by $code }$$ character. 00170 It is assumed by this operation that if $icode e$$ 00171 is an object with type $icode Scalar$$, 00172 $codei% 00173 %os% << %e% 00174 %$$ 00175 will output the value $icode e$$ to the standard 00176 output stream $icode os$$. 00177 00178 $head resize$$ 00179 The call $icode%x%.resize(%n%)%$$ set the size of $icode x$$ equal to 00180 $icode n$$. 00181 If $icode%n% <= %x%.capacity()%$$, 00182 no memory is freed or allocated and the capacity of $icode x$$ does not change. 00183 00184 $head clear$$ 00185 All memory allocated for the vector is freed 00186 and both its size and capacity are set to zero. 00187 The can be useful when using very large vectors 00188 and when checking for memory leaks (and there are global vectors) 00189 see the $cref/memory/CppAD_vector/Memory and Parallel Mode/$$ discussion. 00190 00191 $head data$$ 00192 $index data, CppAD vector$$ 00193 $index vector, CppAD data$$ 00194 If $icode x$$ is a $codei%CppAD::vector<%Scalar%>%$$ object 00195 $codei% 00196 %x%.data() 00197 %$$ 00198 returns a pointer to a $icode Scalar$$ object such that for 00199 $codei%0 <= %i% < %x%.size()%$$, 00200 $icode%x%[%i%]%$$ and $icode%x%.data()[%i%]%$$ 00201 are the same $icode Scalar$$ object. 00202 If $icode x$$ is $code const$$, the pointer is $code const$$. 00203 If $icode%x%.capacity()%$$ is zero, the value of the pointer is not defined. 00204 The pointer may no longer be valid after the following operations on 00205 $icode x$$: 00206 its destructor, 00207 $code clear$$, 00208 $code resize$$, 00209 $code push_back$$, 00210 $code push_vector$$, 00211 assignment to another vector when original size of $icode x$$ is zero. 00212 00213 $head vectorBool$$ 00214 $index vectorBool$$ 00215 The file $code <cppad/vector.hpp>$$ also defines the class 00216 $code CppAD::vectorBool$$. 00217 This has the same specifications as $code CppAD::vector<bool>$$ 00218 with the following exceptions: 00219 00220 $subhead Memory$$ 00221 The class $code vectorBool$$ conserves on memory 00222 (on the other hand, $code CppAD::vector<bool>$$ is expected to be faster 00223 than $code vectorBool$$). 00224 00225 $subhead data$$ 00226 The $cref/data/CppAD_vector/data/$$ function is not supported by 00227 $code vectorBool$$. 00228 00229 $subhead Output$$ 00230 The $code CppAD::vectorBool$$ output operator 00231 prints each boolean value as 00232 a $code 0$$ for false, 00233 a $code 1$$ for true, 00234 and does not print any other output; i.e., 00235 the vector is written a long sequence of zeros and ones with no 00236 surrounding $code {$$, $code }$$ and with no separating commas or spaces. 00237 00238 $subhead Element Type$$ 00239 If $icode x$$ has type $code vectorBool$$ 00240 and $icode i$$ has type $code size_t$$, 00241 the element access value $icode%x%[%i%]%$$ has an unspecified type, 00242 referred to here as $icode elementType$$, that supports the following 00243 operations: 00244 00245 $list number$$ 00246 $icode elementType$$ can be converted to $code bool$$; e.g. 00247 the following syntax is supported: 00248 $codei% 00249 static_cast<bool>( %x%[%i%] ) 00250 %$$ 00251 00252 $lnext 00253 $icode elementType$$ supports the assignment operator $code =$$ where the 00254 right hand side is a $code bool$$ or an $icode elementType$$ object; e.g., 00255 if $icode y$$ has type $code bool$$, the following syntax is supported: 00256 $codei% 00257 %x%[%i%] = %y% 00258 %$$ 00259 00260 $lnext 00261 The result of an assignment to an $icode elementType$$ 00262 also has type $icode elementType$$. 00263 Thus, if $icode z$$ has type $code bool$$, the following syntax is supported: 00264 $codei% 00265 %z% = %x%[%i%] = %y% 00266 %$$ 00267 $lend 00268 00269 $head Memory and Parallel Mode$$ 00270 $index thread_alloc, vector$$ 00271 $index vector, thread_alloc$$ 00272 These vectors use the multi-threaded fast memory allocator 00273 $cref thread_alloc$$: 00274 00275 $list number$$ 00276 The routine $cref/parallel_setup/ta_parallel_setup/$$ must 00277 be called before these vectors can be used 00278 $cref/in parallel/ta_in_parallel/$$. 00279 $lnext 00280 Using these vectors affects the amount of memory 00281 $cref/in_use/ta_inuse/$$ and $cref/available/ta_available/$$. 00282 $lnext 00283 Calling $cref/clear/CppAD_vector/clear/$$, 00284 makes the corresponding memory available (though $code thread_alloc$$) 00285 to the current thread. 00286 $lnext 00287 Available memory 00288 can then be completely freed using $cref/free_available/ta_free_available/$$. 00289 $lend 00290 00291 $head Example$$ 00292 $children% 00293 example/cppad_vector.cpp% 00294 example/vector_bool.cpp 00295 %$$ 00296 The files 00297 $cref cppad_vector.cpp$$ and 00298 $cref vector_bool.cpp$$ each 00299 contain an example and test of this template class. 00300 They return true if they succeed and false otherwise. 00301 00302 $head Exercise$$ 00303 $index exercise, CppAD::vector$$ 00304 Create and run a program that contains the following code: 00305 $codep 00306 CppAD::vector<double> x(3); 00307 size_t i; 00308 for(i = 0; i < 3; i++) 00309 x[i] = 4. - i; 00310 std::cout << "x = " << x << std::endl; 00311 $$ 00312 00313 $end 00314 00315 00316 $end 00317 00318 ------------------------------------------------------------------------ 00319 */ 00320 00321 # include <cstddef> 00322 # include <iostream> 00323 # include <limits> 00324 # include <cppad/local/cppad_assert.hpp> 00325 # include <cppad/check_simple_vector.hpp> 00326 # include <cppad/thread_alloc.hpp> 00327 00328 namespace CppAD { // BEGIN_CPPAD_NAMESPACE 00329 /*! 00330 \file vector.hpp 00331 File used to define CppAD::vector and CppAD::vectorBool 00332 */ 00333 00334 // --------------------------------------------------------------------------- 00335 /*! 00336 The CppAD Simple Vector template class. 00337 */ 00338 template <class Type> 00339 class vector { 00340 private: 00341 /// maximum number of Type elements current allocation can hold 00342 size_t capacity_; 00343 /// number of Type elements currently in this vector 00344 size_t length_; 00345 /// pointer to the first type elements 00346 /// (not defined and should not be used when capacity_ = 0) 00347 Type * data_; 00348 public: 00349 /// type of the elements in the vector 00350 typedef Type value_type; 00351 00352 /// default constructor sets capacity_ = length_ = data_ = 0 00353 inline vector(void) 00354 : capacity_(0), length_(0), data_(CPPAD_NULL) 00355 { } 00356 /// sizing constructor 00357 inline vector( 00358 /// number of elements in this vector 00359 size_t n 00360 ) : capacity_(0), length_(n), data_(CPPAD_NULL) 00361 { if( length_ > 0 ) 00362 { // set capacity and data 00363 data_ = thread_alloc::create_array<Type>(length_, capacity_); 00364 } 00365 } 00366 /// copy constructor 00367 inline vector( 00368 /// the *this vector will be a copy of \c x 00369 const vector& x 00370 ) : capacity_(0), length_(x.length_), data_(CPPAD_NULL) 00371 { if( length_ > 0 ) 00372 { // set capacity and data 00373 data_ = thread_alloc::create_array<Type>(length_, capacity_); 00374 00375 // copy values using assignment operator 00376 size_t i; 00377 for(i = 0; i < length_; i++) 00378 data_[i] = x.data_[i]; 00379 } 00380 } 00381 /// destructor 00382 ~vector(void) 00383 { if( capacity_ > 0 ) 00384 thread_alloc::delete_array(data_); 00385 } 00386 00387 /// maximum number of elements current allocation can store 00388 inline size_t capacity(void) const 00389 { return capacity_; } 00390 00391 /// number of elements currently in this vector. 00392 inline size_t size(void) const 00393 { return length_; } 00394 00395 /// raw pointer to the data 00396 inline Type* data(void) 00397 { return data_; } 00398 00399 /// const raw pointer to the data 00400 inline const Type* data(void) const 00401 { return data_; } 00402 00403 /// change the number of elements in this vector. 00404 inline void resize( 00405 /// new number of elements for this vector 00406 size_t n 00407 ) 00408 { length_ = n; 00409 // check if we can use current memory 00410 if( capacity_ >= length_ ) 00411 return; 00412 // check if there is old memory to be freed 00413 if( capacity_ > 0 ) 00414 thread_alloc::delete_array(data_); 00415 // get new memory and set capacity 00416 data_ = thread_alloc::create_array<Type>(length_, capacity_); 00417 } 00418 00419 /// free memory and set number of elements to zero 00420 inline void clear(void) 00421 { length_ = 0; 00422 // check if there is old memory to be freed 00423 if( capacity_ > 0 ) 00424 thread_alloc::delete_array(data_); 00425 capacity_ = 0; 00426 } 00427 00428 /// vector assignment operator 00429 inline vector& operator=( 00430 /// right hand size of the assingment operation 00431 const vector& x 00432 ) 00433 { size_t i; 00434 // If original lenght is zero, then resize 00435 // otherwise a length mismatch is an error. 00436 if( length_ == 0 ) 00437 resize( x.length_ ); 00438 CPPAD_ASSERT_KNOWN( 00439 length_ == x.length_ , 00440 "vector: size miss match in assignment operation" 00441 ); 00442 for(i = 0; i < length_; i++) 00443 data_[i] = x.data_[i]; 00444 return *this; 00445 } 00446 # if CPPAD_HAS_RVALUE 00447 /// vector assignment operator with move semantics 00448 inline vector& operator=( 00449 /// right hand size of the assingment operation 00450 vector&& x 00451 ) 00452 { CPPAD_ASSERT_KNOWN( 00453 length_ == x.length_ || (length_ == 0), 00454 "vector: size miss match in assignment operation" 00455 ); 00456 if( this != &x ) 00457 { clear(); 00458 // 00459 length_ = x.length_; 00460 capacity_ = x.capacity_; 00461 data_ = x.data_; 00462 // 00463 x.length_ = 0; 00464 x.capacity_ = 0; 00465 x.data_ = CPPAD_NULL; 00466 } 00467 return *this; 00468 } 00469 # endif 00470 /// non-constant element access; i.e., we can change this element value 00471 Type& operator[]( 00472 /// element index, must be less than length 00473 size_t i 00474 ) 00475 { CPPAD_ASSERT_KNOWN( 00476 i < length_, 00477 "vector: index greater than or equal vector size" 00478 ); 00479 return data_[i]; 00480 } 00481 /// constant element access; i.e., we cannot change this element value 00482 const Type& operator[]( 00483 /// element index, must be less than length 00484 size_t i 00485 ) const 00486 { CPPAD_ASSERT_KNOWN( 00487 i < length_, 00488 "vector: index greater than or equal vector size" 00489 ); 00490 return data_[i]; 00491 } 00492 /// add an element to the back of this vector 00493 void push_back( 00494 /// value of the element 00495 const Type& s 00496 ) 00497 { CPPAD_ASSERT_UNKNOWN( length_ <= capacity_ ); 00498 if( length_ + 1 > capacity_ ) 00499 { // store old capacity and data values 00500 size_t old_capacity = capacity_; 00501 Type* old_data = data_; 00502 // set new capacity and data values 00503 data_ = thread_alloc::create_array<Type>(length_ + 1, capacity_); 00504 // copy old data values 00505 size_t i; 00506 for(i = 0; i < length_; i++) 00507 data_[i] = old_data[i]; 00508 // free old data 00509 if( old_capacity > 0 ) 00510 thread_alloc::delete_array(old_data); 00511 } 00512 data_[length_++] = s; 00513 CPPAD_ASSERT_UNKNOWN( length_ <= capacity_ ); 00514 } 00515 00516 /*! add vector to the back of this vector 00517 (we could not use push_back becasue MS V++ 7.1 did not resolve 00518 to non-template member function when scalar is used.) 00519 */ 00520 template <class Vector> 00521 void push_vector( 00522 /// value of the vector that we are adding 00523 const Vector& v 00524 ) 00525 { CheckSimpleVector<Type, Vector>(); 00526 CPPAD_ASSERT_UNKNOWN( length_ <= capacity_ ); 00527 size_t m = v.size(); 00528 size_t i; 00529 if( length_ + m > capacity_ ) 00530 { // store old capacity and data values 00531 size_t old_capacity = capacity_; 00532 Type* old_data = data_; 00533 // set new capacity and data values 00534 data_ = thread_alloc::create_array<Type>(length_ + m, capacity_); 00535 // copy old data values 00536 for(i = 0; i < length_; i++) 00537 data_[i] = old_data[i]; 00538 // free old data 00539 if( old_capacity > 0 ) 00540 thread_alloc::delete_array(old_data); 00541 } 00542 for(i = 0; i < m; i++) 00543 data_[length_++] = v[i]; 00544 CPPAD_ASSERT_UNKNOWN( length_ <= capacity_ ); 00545 } 00546 }; 00547 00548 /// output a vector 00549 template <class Type> 00550 inline std::ostream& operator << ( 00551 /// stream to write the vector to 00552 std::ostream& os , 00553 /// vector that is output 00554 const CppAD::vector<Type>& vec ) 00555 { size_t i = 0; 00556 size_t n = vec.size(); 00557 00558 os << "{ "; 00559 while(i < n) 00560 { os << vec[i++]; 00561 if( i < n ) 00562 os << ", "; 00563 } 00564 os << " }"; 00565 return os; 00566 } 00567 00568 // --------------------------------------------------------------------------- 00569 /*! 00570 Class that is used to hold a non-constant element of a vector. 00571 */ 00572 class vectorBoolElement { 00573 /// the boolean data is packed with sizeof(UnitType) bits per value 00574 typedef size_t UnitType; 00575 private: 00576 /// pointer to the UnitType value holding this eleemnt 00577 UnitType* unit_; 00578 /// mask for the bit corresponding to this element 00579 /// (all zero except for bit that corresponds to this element) 00580 UnitType mask_; 00581 public: 00582 /// constructor from member values 00583 vectorBoolElement( 00584 /// unit for this element 00585 UnitType* unit , 00586 /// mask for this element 00587 UnitType mask ) 00588 : unit_(unit) , mask_(mask) 00589 { } 00590 /// constuctor from another element 00591 vectorBoolElement( 00592 /// other element 00593 const vectorBoolElement& e ) 00594 : unit_(e.unit_) , mask_(e.mask_) 00595 { } 00596 /// conversion to a boolean value 00597 operator bool() const 00598 { return (*unit_ & mask_) != 0; } 00599 /// assignment of this element to a bool 00600 vectorBoolElement& operator=( 00601 /// right hand side for assignment 00602 bool bit 00603 ) 00604 { if(bit) 00605 *unit_ |= mask_; 00606 else *unit_ &= ~mask_; 00607 return *this; 00608 } 00609 /// assignment of this element to another element 00610 vectorBoolElement& operator=(const vectorBoolElement& e) 00611 { if( *(e.unit_) & e.mask_ ) 00612 *unit_ |= mask_; 00613 else *unit_ &= ~mask_; 00614 return *this; 00615 } 00616 }; 00617 00618 class vectorBool { 00619 /// the boolean data is packed with sizeof(UnitType) bits per value 00620 typedef size_t UnitType; 00621 private: 00622 /// number of bits packed into each UnitType value in data_ 00623 static const size_t bit_per_unit_ 00624 = std::numeric_limits<UnitType>::digits; 00625 /// number of UnitType values in data_ 00626 size_t n_unit_; 00627 /// number of bits currently stored in this vector 00628 size_t length_; 00629 /// pointer to where the bits are stored 00630 UnitType *data_; 00631 00632 /// minimum number of UnitType values that can store length_ bits 00633 /// (note that this is really a function of length_) 00634 size_t unit_min(void) 00635 { if( length_ == 0 ) 00636 return 0; 00637 return (length_ - 1) / bit_per_unit_ + 1; 00638 } 00639 public: 00640 /// type corresponding to the elements of this vector 00641 /// (note that non-const elements actually use vectorBoolElement) 00642 typedef bool value_type; 00643 00644 /// default constructor (sets all member data to zero) 00645 inline vectorBool(void) : n_unit_(0), length_(0), data_(CPPAD_NULL) 00646 { } 00647 /// sizing constructor 00648 inline vectorBool( 00649 /// number of bits in this vector 00650 size_t n 00651 ) : n_unit_(0), length_(n), data_(CPPAD_NULL) 00652 { if( length_ > 0 ) 00653 { // set n_unit and data 00654 size_t min_unit = unit_min(); 00655 data_ = thread_alloc::create_array<UnitType>(min_unit, n_unit_); 00656 } 00657 } 00658 /// copy constructor 00659 inline vectorBool( 00660 /// the *this vector will be a copy of \c v 00661 const vectorBool& v 00662 ) : n_unit_(0), length_(v.length_), data_(CPPAD_NULL) 00663 { if( length_ > 0 ) 00664 { // set n_unit and data 00665 size_t min_unit = unit_min(); 00666 data_ = thread_alloc::create_array<UnitType>(min_unit, n_unit_); 00667 00668 // copy values using UnitType assignment operator 00669 CPPAD_ASSERT_UNKNOWN( min_unit <= v.n_unit_ ); 00670 size_t i; 00671 for(i = 0; i < min_unit; i++) 00672 data_[i] = v.data_[i]; 00673 } 00674 } 00675 /// destructor 00676 ~vectorBool(void) 00677 { if( n_unit_ > 0 ) 00678 thread_alloc::delete_array(data_); 00679 } 00680 00681 /// number of elements in this vector 00682 inline size_t size(void) const 00683 { return length_; } 00684 00685 /// maximum number of elements current allocation can store 00686 inline size_t capacity(void) const 00687 { return n_unit_ * bit_per_unit_; } 00688 00689 /// change number of elements in this vector 00690 inline void resize( 00691 /// new number of elements for this vector 00692 size_t n 00693 ) 00694 { length_ = n; 00695 // check if we can use the current memory 00696 size_t min_unit = unit_min(); 00697 if( n_unit_ >= min_unit ) 00698 return; 00699 // check if there is old memory to be freed 00700 if( n_unit_ > 0 ) 00701 thread_alloc::delete_array(data_); 00702 // get new memory and set n_unit 00703 data_ = thread_alloc::create_array<UnitType>(min_unit, n_unit_); 00704 } 00705 00706 /// free memory and set number of elements to zero 00707 inline void clear(void) 00708 { length_ = 0; 00709 // check if there is old memory to be freed 00710 if( n_unit_ > 0 ) 00711 thread_alloc::delete_array(data_); 00712 n_unit_ = 0; 00713 } 00714 00715 /// vector assignment operator 00716 inline vectorBool& operator=( 00717 /// right hand size of the assingment operation 00718 const vectorBool& v 00719 ) 00720 { size_t i; 00721 CPPAD_ASSERT_KNOWN( 00722 length_ == v.length_ , 00723 "vectorBool: size miss match in assignment operation" 00724 ); 00725 size_t min_unit = unit_min(); 00726 CPPAD_ASSERT_UNKNOWN( min_unit <= n_unit_ ); 00727 CPPAD_ASSERT_UNKNOWN( min_unit <= v.n_unit_ ); 00728 for(i = 0; i < min_unit; i++) 00729 data_[i] = v.data_[i]; 00730 return *this; 00731 } 00732 # if CPPAD_HAS_RVALUE 00733 /// vector assignment operator with move semantics 00734 inline vectorBool& operator=( 00735 /// right hand size of the assingment operation 00736 vectorBool&& x 00737 ) 00738 { if( this != &x ) 00739 { clear(); 00740 // 00741 length_ = x.length_; 00742 n_unit_ = x.n_unit_; 00743 data_ = x.data_; 00744 // 00745 x.length_ = 0; 00746 x.n_unit_ = 0; 00747 x.data_ = CPPAD_NULL; 00748 } 00749 return *this; 00750 } 00751 # endif 00752 00753 00754 /// non-constant element access; i.e., we can change this element value 00755 vectorBoolElement operator[]( 00756 /// element index, must be less than length 00757 size_t k 00758 ) 00759 { size_t i, j; 00760 CPPAD_ASSERT_KNOWN( 00761 k < length_, 00762 "vectorBool: index greater than or equal vector size" 00763 ); 00764 i = k / bit_per_unit_; 00765 j = k - i * bit_per_unit_; 00766 return vectorBoolElement(data_ + i , UnitType(1) << j ); 00767 } 00768 /// constant element access; i.e., we cannot change this element value 00769 bool operator[](size_t k) const 00770 { size_t i, j; 00771 UnitType unit, mask; 00772 CPPAD_ASSERT_KNOWN( 00773 k < length_, 00774 "vectorBool: index greater than or equal vector size" 00775 ); 00776 i = k / bit_per_unit_; 00777 j = k - i * bit_per_unit_; 00778 unit = data_[i]; 00779 mask = UnitType(1) << j; 00780 return (unit & mask) != 0; 00781 } 00782 /// add an element to the back of this vector 00783 void push_back( 00784 /// value of the element 00785 bool bit 00786 ) 00787 { CPPAD_ASSERT_UNKNOWN( unit_min() <= n_unit_ ); 00788 size_t i, j; 00789 UnitType mask; 00790 if( length_ + 1 > n_unit_ * bit_per_unit_ ) 00791 { CPPAD_ASSERT_UNKNOWN( unit_min() == n_unit_ ); 00792 // store old n_unit and data values 00793 size_t old_n_unit = n_unit_; 00794 UnitType* old_data = data_; 00795 // set new n_unit and data values 00796 data_ = thread_alloc::create_array<UnitType>(n_unit_+1, n_unit_); 00797 // copy old data values 00798 for(i = 0; i < old_n_unit; i++) 00799 data_[i] = old_data[i]; 00800 // free old data 00801 if( old_n_unit > 0 ) 00802 thread_alloc::delete_array(old_data); 00803 } 00804 i = length_ / bit_per_unit_; 00805 j = length_ - i * bit_per_unit_; 00806 mask = UnitType(1) << j; 00807 if( bit ) 00808 data_[i] |= mask; 00809 else data_[i] &= ~mask; 00810 length_++; 00811 } 00812 /// add vector to the back of this vector 00813 template <class Vector> 00814 void push_vector( 00815 /// value of the vector that we are adding 00816 const Vector& v 00817 ) 00818 { CheckSimpleVector<bool, Vector>(); 00819 size_t min_unit = unit_min(); 00820 CPPAD_ASSERT_UNKNOWN( length_ <= n_unit_ * bit_per_unit_ ); 00821 // some temporaries 00822 size_t i, j, k, ell; 00823 UnitType mask; 00824 bool bit; 00825 // store old length 00826 size_t old_length = length_; 00827 // new length and minium number of units; 00828 length_ = length_ + v.size(); 00829 min_unit = unit_min(); 00830 if( length_ >= n_unit_ * bit_per_unit_ ) 00831 { // store old n_unit and data value 00832 size_t old_n_unit = n_unit_; 00833 UnitType* old_data = data_; 00834 // set new n_unit and data values 00835 data_ = thread_alloc::create_array<UnitType>(min_unit, n_unit_); 00836 // copy old data values 00837 for(i = 0; i < old_n_unit; i++) 00838 data_[i] = old_data[i]; 00839 // free old data 00840 if( old_n_unit > 0 ) 00841 thread_alloc::delete_array(old_data); 00842 } 00843 ell = old_length; 00844 for(k = 0; k < v.size(); k++) 00845 { 00846 i = ell / bit_per_unit_; 00847 j = ell - i * bit_per_unit_; 00848 bit = v[k]; 00849 mask = UnitType(1) << j; 00850 if( bit ) 00851 data_[i] |= mask; 00852 else data_[i] &= ~mask; 00853 ell++; 00854 } 00855 CPPAD_ASSERT_UNKNOWN( length_ == ell ); 00856 CPPAD_ASSERT_UNKNOWN( length_ <= n_unit_ * bit_per_unit_ ); 00857 } 00858 }; 00859 00860 /// output a vector 00861 inline std::ostream& operator << ( 00862 /// steam to write the vector to 00863 std::ostream& os , 00864 /// vector that is output 00865 const vectorBool& v ) 00866 { size_t i = 0; 00867 size_t n = v.size(); 00868 00869 while(i < n) 00870 os << v[i++]; 00871 return os; 00872 } 00873 00874 } // END_CPPAD_NAMESPACE 00875 # endif