1 | /* $Id: vector.hpp 3746 2015-11-09 04:50:27Z bradbell $ */ |
---|
2 | # ifndef CPPAD_VECTOR_INCLUDED |
---|
3 | # define CPPAD_VECTOR_INCLUDED |
---|
4 | |
---|
5 | /* -------------------------------------------------------------------------- |
---|
6 | CppAD: C++ Algorithmic Differentiation: Copyright (C) 2003-15 Bradley M. Bell |
---|
7 | |
---|
8 | CppAD is distributed under multiple licenses. This distribution is under |
---|
9 | the terms of the |
---|
10 | Eclipse Public License Version 1.0. |
---|
11 | |
---|
12 | A copy of this license is included in the COPYING file of this distribution. |
---|
13 | Please visit http://www.coin-or.org/CppAD/ for information on other licenses. |
---|
14 | -------------------------------------------------------------------------- */ |
---|
15 | |
---|
16 | /* |
---|
17 | $begin CppAD_vector$$ |
---|
18 | $spell |
---|
19 | rvalues |
---|
20 | thread_alloc |
---|
21 | cppad.hpp |
---|
22 | Bool |
---|
23 | resize |
---|
24 | cout |
---|
25 | endl |
---|
26 | std |
---|
27 | Cpp |
---|
28 | const |
---|
29 | vec |
---|
30 | ostream |
---|
31 | elem |
---|
32 | $$ |
---|
33 | |
---|
34 | $index vector, CppAD template class$$ |
---|
35 | $index class, template CppAD vector$$ |
---|
36 | $index template, CppAD vector class$$ |
---|
37 | |
---|
38 | $section The CppAD::vector Template Class$$ |
---|
39 | |
---|
40 | $head Syntax$$ |
---|
41 | $code # include <cppad/vector.hpp>$$ |
---|
42 | |
---|
43 | $head Description$$ |
---|
44 | The include file $code cppad/vector.hpp$$ defines the |
---|
45 | vector template class $code CppAD::vector$$. |
---|
46 | This is a $cref SimpleVector$$ template class and in addition |
---|
47 | it has the features listed below: |
---|
48 | |
---|
49 | $head Include$$ |
---|
50 | The file $code cppad/vector.hpp$$ is included by $code cppad/cppad.hpp$$ |
---|
51 | but it can also be included separately with out the rest of the |
---|
52 | CppAD include files. |
---|
53 | |
---|
54 | $head capacity$$ |
---|
55 | If $icode x$$ is a $codei%CppAD::vector<%Scalar%>%$$, |
---|
56 | and $icode cap$$ is a $code size_t$$ object, |
---|
57 | $codei% |
---|
58 | %cap% = %x%.capacity() |
---|
59 | %$$ |
---|
60 | set $icode cap$$ to the number of $icode Scalar$$ objects that |
---|
61 | could fit in the memory currently allocated for $icode x$$. |
---|
62 | Note that |
---|
63 | $codei% |
---|
64 | %x%.size() <= %x%.capacity() |
---|
65 | %$$ |
---|
66 | |
---|
67 | $head Assignment$$ |
---|
68 | $index assignment, CppAD vector$$ |
---|
69 | If $icode x$$ and $icode y$$ are |
---|
70 | $codei%CppAD::vector<%Scalar%>%$$ objects, |
---|
71 | $codei% |
---|
72 | %y% = %x% |
---|
73 | %$$ |
---|
74 | has all the properties listed for a |
---|
75 | $cref/simple vector assignment/SimpleVector/Assignment/$$ |
---|
76 | plus the following: |
---|
77 | |
---|
78 | $subhead Check Size$$ |
---|
79 | The $code CppAD::vector$$ template class will check that |
---|
80 | the size of $icode x$$ is either zero or the size of $icode y$$ |
---|
81 | before doing the assignment. |
---|
82 | If this is not the case, $code CppAD::vector$$ will use |
---|
83 | $cref ErrorHandler$$ |
---|
84 | to generate an appropriate error report. |
---|
85 | Allowing for assignment to a vector with size zero makes the following |
---|
86 | code work: |
---|
87 | $codei% |
---|
88 | CppAD::vector<%Scalar%> %y%; |
---|
89 | %y% = %x%; |
---|
90 | %$$ |
---|
91 | |
---|
92 | $subhead Return Reference$$ |
---|
93 | A reference to the vector $icode y$$ is returned. |
---|
94 | An example use of this reference is in multiple assignments of the form |
---|
95 | $codei% |
---|
96 | %z% = %y% = %x% |
---|
97 | %$$ |
---|
98 | |
---|
99 | $subhead Move Semantics$$ |
---|
100 | If the C++ compiler supports move semantic rvalues using the $code &&$$ |
---|
101 | syntax, then it will be used during the vector assignment statement. |
---|
102 | This means that return values and other temporaries are not be copied, |
---|
103 | but rather pointers are transferred. |
---|
104 | |
---|
105 | $head Element Access$$ |
---|
106 | $index [], CppAD vector$$ |
---|
107 | $index vector, [] CppAD$$ |
---|
108 | If $icode x$$ is a $codei%CppAD::vector<%Scalar%>%$$ object |
---|
109 | and $code i$$ has type $code size_t$$, |
---|
110 | $codei% |
---|
111 | %x%[%i%] |
---|
112 | %$$ |
---|
113 | has all the properties listed for a |
---|
114 | $cref/simple vector element access/SimpleVector/Element Access/$$ |
---|
115 | plus the following: |
---|
116 | $pre |
---|
117 | |
---|
118 | $$ |
---|
119 | The object $icode%x%[%i%]%$$ has type $icode Scalar$$ |
---|
120 | (is not possibly a different type that can be converted to $icode Scalar$$). |
---|
121 | $pre |
---|
122 | |
---|
123 | $$ |
---|
124 | If $icode i$$ is not less than the size of the $icode x$$, |
---|
125 | $code CppAD::vector$$ will use |
---|
126 | $cref ErrorHandler$$ |
---|
127 | to generate an appropriate error report. |
---|
128 | |
---|
129 | $head push_back$$ |
---|
130 | $index push_back, CppAD vector$$ |
---|
131 | $index vector, CppAD push_back$$ |
---|
132 | If $icode x$$ is a $codei%CppAD::vector<%Scalar%>%$$ object |
---|
133 | with size equal to $icode n$$ and |
---|
134 | $icode s$$ has type $icode Scalar$$, |
---|
135 | $codei% |
---|
136 | %x%.push_back(%s%) |
---|
137 | %$$ |
---|
138 | extends the vector $icode x$$ so that its new size is $icode n$$ plus one |
---|
139 | and $icode%x%[%n%]%$$ is equal to $icode s$$ |
---|
140 | (equal in the sense of the $icode Scalar$$ assignment operator). |
---|
141 | |
---|
142 | $head push_vector$$ |
---|
143 | $index push_vector, CppAD$$ |
---|
144 | $index vector, CppAD push$$ |
---|
145 | If $icode x$$ is a $codei%CppAD::vector<%Scalar%>%$$ object |
---|
146 | with size equal to $icode n$$ and |
---|
147 | $icode v$$ is a $cref/simple vector/SimpleVector/$$ |
---|
148 | with elements of type $icode Scalar$$ and size $icode m$$, |
---|
149 | $codei% |
---|
150 | %x%.push_vector(%v%) |
---|
151 | %$$ |
---|
152 | extends the vector $icode x$$ so that its new size is $icode%n%+%m%$$ |
---|
153 | and $icode%x%[%n% + %i%]%$$ is equal to $icode%v%[%i%]%$$ |
---|
154 | for $icode%i = 1 , ... , m-1%$$ |
---|
155 | (equal in the sense of the $icode Scalar$$ assignment operator). |
---|
156 | |
---|
157 | $head Output$$ |
---|
158 | If $icode x$$ is a $codei%CppAD::vector<%Scalar%>%$$ object |
---|
159 | and $icode os$$ is an $code std::ostream$$, |
---|
160 | and the operation |
---|
161 | $codei% |
---|
162 | %os% << %x% |
---|
163 | %$$ |
---|
164 | will output the vector $icode x$$ to the standard |
---|
165 | output stream $icode os$$. |
---|
166 | The elements of $icode x$$ are enclosed at the beginning by a |
---|
167 | $code {$$ character, |
---|
168 | they are separated by $code ,$$ characters, |
---|
169 | and they are enclosed at the end by $code }$$ character. |
---|
170 | It is assumed by this operation that if $icode e$$ |
---|
171 | is an object with type $icode Scalar$$, |
---|
172 | $codei% |
---|
173 | %os% << %e% |
---|
174 | %$$ |
---|
175 | will output the value $icode e$$ to the standard |
---|
176 | output stream $icode os$$. |
---|
177 | |
---|
178 | $head resize$$ |
---|
179 | The call $icode%x%.resize(%n%)%$$ set the size of $icode x$$ equal to |
---|
180 | $icode n$$. |
---|
181 | If $icode%n% <= %x%.capacity()%$$, |
---|
182 | no memory is freed or allocated, the capacity of $icode x$$ does not change, |
---|
183 | and the data in $icode x$$ is preserved. |
---|
184 | If $icode%n% > %x%.capacity()%$$, |
---|
185 | new memory is allocated and the data in $icode x$$ is lost |
---|
186 | (not copied to the new memory location). |
---|
187 | |
---|
188 | $head clear$$ |
---|
189 | All memory allocated for the vector is freed |
---|
190 | and both its size and capacity are set to zero. |
---|
191 | The can be useful when using very large vectors |
---|
192 | and when checking for memory leaks (and there are global vectors) |
---|
193 | see the $cref/memory/CppAD_vector/Memory and Parallel Mode/$$ discussion. |
---|
194 | |
---|
195 | $head data$$ |
---|
196 | $index data, CppAD vector$$ |
---|
197 | $index vector, CppAD data$$ |
---|
198 | If $icode x$$ is a $codei%CppAD::vector<%Scalar%>%$$ object |
---|
199 | $codei% |
---|
200 | %x%.data() |
---|
201 | %$$ |
---|
202 | returns a pointer to a $icode Scalar$$ object such that for |
---|
203 | $codei%0 <= %i% < %x%.size()%$$, |
---|
204 | $icode%x%[%i%]%$$ and $icode%x%.data()[%i%]%$$ |
---|
205 | are the same $icode Scalar$$ object. |
---|
206 | If $icode x$$ is $code const$$, the pointer is $code const$$. |
---|
207 | If $icode%x%.capacity()%$$ is zero, the value of the pointer is not defined. |
---|
208 | The pointer may no longer be valid after the following operations on |
---|
209 | $icode x$$: |
---|
210 | its destructor, |
---|
211 | $code clear$$, |
---|
212 | $code resize$$, |
---|
213 | $code push_back$$, |
---|
214 | $code push_vector$$, |
---|
215 | assignment to another vector when original size of $icode x$$ is zero. |
---|
216 | |
---|
217 | $head vectorBool$$ |
---|
218 | $index vectorBool$$ |
---|
219 | The file $code <cppad/vector.hpp>$$ also defines the class |
---|
220 | $code CppAD::vectorBool$$. |
---|
221 | This has the same specifications as $code CppAD::vector<bool>$$ |
---|
222 | with the following exceptions: |
---|
223 | |
---|
224 | $subhead Memory$$ |
---|
225 | The class $code vectorBool$$ conserves on memory |
---|
226 | (on the other hand, $code CppAD::vector<bool>$$ is expected to be faster |
---|
227 | than $code vectorBool$$). |
---|
228 | |
---|
229 | $subhead bit_per_unit$$ |
---|
230 | The static function call |
---|
231 | $codei% |
---|
232 | %s% = vectorBool::bit_per_unit() |
---|
233 | %$$ |
---|
234 | returns the $code size_t$$ value $icode s$$ |
---|
235 | which is equal to the number of boolean values (bits) that are |
---|
236 | packed into one operational unit. |
---|
237 | For example, a logical $code or$$ |
---|
238 | acts on this many boolean values with one operation. |
---|
239 | |
---|
240 | $subhead data$$ |
---|
241 | The $cref/data/CppAD_vector/data/$$ function is not supported by |
---|
242 | $code vectorBool$$. |
---|
243 | |
---|
244 | $subhead Output$$ |
---|
245 | The $code CppAD::vectorBool$$ output operator |
---|
246 | prints each boolean value as |
---|
247 | a $code 0$$ for false, |
---|
248 | a $code 1$$ for true, |
---|
249 | and does not print any other output; i.e., |
---|
250 | the vector is written a long sequence of zeros and ones with no |
---|
251 | surrounding $code {$$, $code }$$ and with no separating commas or spaces. |
---|
252 | |
---|
253 | $subhead Element Type$$ |
---|
254 | If $icode x$$ has type $code vectorBool$$ |
---|
255 | and $icode i$$ has type $code size_t$$, |
---|
256 | the element access value $icode%x%[%i%]%$$ has an unspecified type, |
---|
257 | referred to here as $icode elementType$$, that supports the following |
---|
258 | operations: |
---|
259 | |
---|
260 | $list number$$ |
---|
261 | $icode elementType$$ can be converted to $code bool$$; e.g. |
---|
262 | the following syntax is supported: |
---|
263 | $codei% |
---|
264 | static_cast<bool>( %x%[%i%] ) |
---|
265 | %$$ |
---|
266 | |
---|
267 | $lnext |
---|
268 | $icode elementType$$ supports the assignment operator $code =$$ where the |
---|
269 | right hand side is a $code bool$$ or an $icode elementType$$ object; e.g., |
---|
270 | if $icode y$$ has type $code bool$$, the following syntax is supported: |
---|
271 | $codei% |
---|
272 | %x%[%i%] = %y% |
---|
273 | %$$ |
---|
274 | |
---|
275 | $lnext |
---|
276 | The result of an assignment to an $icode elementType$$ |
---|
277 | also has type $icode elementType$$. |
---|
278 | Thus, if $icode z$$ has type $code bool$$, the following syntax is supported: |
---|
279 | $codei% |
---|
280 | %z% = %x%[%i%] = %y% |
---|
281 | %$$ |
---|
282 | $lend |
---|
283 | |
---|
284 | $head Memory and Parallel Mode$$ |
---|
285 | $index thread_alloc, vector$$ |
---|
286 | $index vector, thread_alloc$$ |
---|
287 | These vectors use the multi-threaded fast memory allocator |
---|
288 | $cref thread_alloc$$: |
---|
289 | |
---|
290 | $list number$$ |
---|
291 | The routine $cref/parallel_setup/ta_parallel_setup/$$ must |
---|
292 | be called before these vectors can be used |
---|
293 | $cref/in parallel/ta_in_parallel/$$. |
---|
294 | $lnext |
---|
295 | Using these vectors affects the amount of memory |
---|
296 | $cref/in_use/ta_inuse/$$ and $cref/available/ta_available/$$. |
---|
297 | $lnext |
---|
298 | Calling $cref/clear/CppAD_vector/clear/$$, |
---|
299 | makes the corresponding memory available (though $code thread_alloc$$) |
---|
300 | to the current thread. |
---|
301 | $lnext |
---|
302 | Available memory |
---|
303 | can then be completely freed using $cref/free_available/ta_free_available/$$. |
---|
304 | $lend |
---|
305 | |
---|
306 | $head Example$$ |
---|
307 | $children% |
---|
308 | example/cppad_vector.cpp% |
---|
309 | example/vector_bool.cpp |
---|
310 | %$$ |
---|
311 | The files |
---|
312 | $cref cppad_vector.cpp$$ and |
---|
313 | $cref vector_bool.cpp$$ each |
---|
314 | contain an example and test of this template class. |
---|
315 | They return true if they succeed and false otherwise. |
---|
316 | |
---|
317 | $head Exercise$$ |
---|
318 | $index exercise, CppAD::vector$$ |
---|
319 | Create and run a program that contains the following code: |
---|
320 | $codep |
---|
321 | CppAD::vector<double> x(3); |
---|
322 | size_t i; |
---|
323 | for(i = 0; i < 3; i++) |
---|
324 | x[i] = 4. - i; |
---|
325 | std::cout << "x = " << x << std::endl; |
---|
326 | $$ |
---|
327 | |
---|
328 | $end |
---|
329 | |
---|
330 | |
---|
331 | $end |
---|
332 | |
---|
333 | ------------------------------------------------------------------------ |
---|
334 | */ |
---|
335 | |
---|
336 | # include <cstddef> |
---|
337 | # include <iostream> |
---|
338 | # include <limits> |
---|
339 | # include <cppad/local/cppad_assert.hpp> |
---|
340 | # include <cppad/check_simple_vector.hpp> |
---|
341 | # include <cppad/thread_alloc.hpp> |
---|
342 | |
---|
343 | namespace CppAD { // BEGIN_CPPAD_NAMESPACE |
---|
344 | /*! |
---|
345 | \file vector.hpp |
---|
346 | File used to define CppAD::vector and CppAD::vectorBool |
---|
347 | */ |
---|
348 | |
---|
349 | // --------------------------------------------------------------------------- |
---|
350 | /*! |
---|
351 | The CppAD Simple Vector template class. |
---|
352 | */ |
---|
353 | template <class Type> |
---|
354 | class vector { |
---|
355 | private: |
---|
356 | /// maximum number of Type elements current allocation can hold |
---|
357 | size_t capacity_; |
---|
358 | /// number of Type elements currently in this vector |
---|
359 | size_t length_; |
---|
360 | /// pointer to the first type elements |
---|
361 | /// (not defined and should not be used when capacity_ = 0) |
---|
362 | Type* data_; |
---|
363 | /// delete data pointer |
---|
364 | void delete_data(Type* data_ptr) |
---|
365 | { thread_alloc::delete_array(data_ptr); } |
---|
366 | public: |
---|
367 | /// type of the elements in the vector |
---|
368 | typedef Type value_type; |
---|
369 | |
---|
370 | /// default constructor sets capacity_ = length_ = data_ = 0 |
---|
371 | inline vector(void) |
---|
372 | : capacity_(0), length_(0), data_(CPPAD_NULL) |
---|
373 | { } |
---|
374 | /// sizing constructor |
---|
375 | inline vector( |
---|
376 | /// number of elements in this vector |
---|
377 | size_t n |
---|
378 | ) : capacity_(0), length_(0), data_(CPPAD_NULL) |
---|
379 | { resize(n); } |
---|
380 | |
---|
381 | /// copy constructor |
---|
382 | inline vector( |
---|
383 | /// the *this vector will be a copy of \c x |
---|
384 | const vector& x |
---|
385 | ) : capacity_(0), length_(0), data_(CPPAD_NULL) |
---|
386 | { resize(x.length_); |
---|
387 | |
---|
388 | // copy the data |
---|
389 | for(size_t i = 0; i < length_; i++) |
---|
390 | data_[i] = x.data_[i]; |
---|
391 | } |
---|
392 | /// destructor |
---|
393 | ~vector(void) |
---|
394 | { if( capacity_ > 0 ) |
---|
395 | delete_data(data_); |
---|
396 | } |
---|
397 | |
---|
398 | /// maximum number of elements current allocation can store |
---|
399 | inline size_t capacity(void) const |
---|
400 | { return capacity_; } |
---|
401 | |
---|
402 | /// number of elements currently in this vector. |
---|
403 | inline size_t size(void) const |
---|
404 | { return length_; } |
---|
405 | |
---|
406 | /// raw pointer to the data |
---|
407 | inline Type* data(void) |
---|
408 | { return data_; } |
---|
409 | |
---|
410 | /// const raw pointer to the data |
---|
411 | inline const Type* data(void) const |
---|
412 | { return data_; } |
---|
413 | |
---|
414 | /// change the number of elements in this vector. |
---|
415 | inline void resize( |
---|
416 | /// new number of elements for this vector |
---|
417 | size_t n |
---|
418 | ) |
---|
419 | { length_ = n; |
---|
420 | |
---|
421 | // check if we can use current memory |
---|
422 | if( capacity_ >= length_ ) |
---|
423 | return; |
---|
424 | |
---|
425 | // check if there is old memory to be freed |
---|
426 | if( capacity_ > 0 ) |
---|
427 | delete_data(data_); |
---|
428 | |
---|
429 | // get new memory and set capacity |
---|
430 | data_ = thread_alloc::create_array<Type>(length_, capacity_); |
---|
431 | } |
---|
432 | |
---|
433 | /// free memory and set number of elements to zero |
---|
434 | inline void clear(void) |
---|
435 | { length_ = 0; |
---|
436 | // check if there is old memory to be freed |
---|
437 | if( capacity_ > 0 ) |
---|
438 | delete_data(data_); |
---|
439 | capacity_ = 0; |
---|
440 | } |
---|
441 | |
---|
442 | /// vector assignment operator |
---|
443 | inline vector& operator=( |
---|
444 | /// right hand size of the assingment operation |
---|
445 | const vector& x |
---|
446 | ) |
---|
447 | { size_t i; |
---|
448 | // If original lenght is zero, then resize it. |
---|
449 | // Otherwise a length mismatch is an error. |
---|
450 | if( length_ == 0 ) |
---|
451 | resize( x.length_ ); |
---|
452 | CPPAD_ASSERT_KNOWN( |
---|
453 | length_ == x.length_ , |
---|
454 | "vector: size miss match in assignment operation" |
---|
455 | ); |
---|
456 | for(i = 0; i < length_; i++) |
---|
457 | data_[i] = x.data_[i]; |
---|
458 | return *this; |
---|
459 | } |
---|
460 | # if CPPAD_USE_CPLUSPLUS_2011 |
---|
461 | /// vector assignment operator with move semantics |
---|
462 | inline vector& operator=( |
---|
463 | /// right hand size of the assingment operation |
---|
464 | vector&& x |
---|
465 | ) |
---|
466 | { CPPAD_ASSERT_KNOWN( |
---|
467 | length_ == x.length_ || (length_ == 0), |
---|
468 | "vector: size miss match in assignment operation" |
---|
469 | ); |
---|
470 | if( this != &x ) |
---|
471 | { clear(); |
---|
472 | // |
---|
473 | length_ = x.length_; |
---|
474 | capacity_ = x.capacity_; |
---|
475 | data_ = x.data_; |
---|
476 | // |
---|
477 | x.length_ = 0; |
---|
478 | x.capacity_ = 0; |
---|
479 | x.data_ = CPPAD_NULL; |
---|
480 | } |
---|
481 | return *this; |
---|
482 | } |
---|
483 | # endif |
---|
484 | /// non-constant element access; i.e., we can change this element value |
---|
485 | Type& operator[]( |
---|
486 | /// element index, must be less than length |
---|
487 | size_t i |
---|
488 | ) |
---|
489 | { CPPAD_ASSERT_KNOWN( |
---|
490 | i < length_, |
---|
491 | "vector: index greater than or equal vector size" |
---|
492 | ); |
---|
493 | return data_[i]; |
---|
494 | } |
---|
495 | /// constant element access; i.e., we cannot change this element value |
---|
496 | const Type& operator[]( |
---|
497 | /// element index, must be less than length |
---|
498 | size_t i |
---|
499 | ) const |
---|
500 | { CPPAD_ASSERT_KNOWN( |
---|
501 | i < length_, |
---|
502 | "vector: index greater than or equal vector size" |
---|
503 | ); |
---|
504 | return data_[i]; |
---|
505 | } |
---|
506 | /// add an element to the back of this vector |
---|
507 | void push_back( |
---|
508 | /// value of the element |
---|
509 | const Type& s |
---|
510 | ) |
---|
511 | { // case where no allocation is necessary |
---|
512 | if( length_ + 1 <= capacity_ ) |
---|
513 | { data_[length_++] = s; |
---|
514 | return; |
---|
515 | } |
---|
516 | CPPAD_ASSERT_UNKNOWN( length_ == capacity_ ); |
---|
517 | |
---|
518 | // store old length, capacity and data |
---|
519 | size_t old_length = length_; |
---|
520 | size_t old_capacity = capacity_; |
---|
521 | Type* old_data = data_; |
---|
522 | |
---|
523 | // set the new length, capacity and data |
---|
524 | length_ = 0; |
---|
525 | capacity_ = 0; |
---|
526 | resize(old_length + 1); |
---|
527 | |
---|
528 | // copy old data values |
---|
529 | for(size_t i = 0; i < old_length; i++) |
---|
530 | data_[i] = old_data[i]; |
---|
531 | |
---|
532 | // put the new element in the vector |
---|
533 | CPPAD_ASSERT_UNKNOWN( old_length + 1 <= capacity_ ); |
---|
534 | data_[old_length] = s; |
---|
535 | |
---|
536 | // free old data |
---|
537 | if( old_capacity > 0 ) |
---|
538 | delete_data(old_data); |
---|
539 | |
---|
540 | CPPAD_ASSERT_UNKNOWN( old_length + 1 == length_ ); |
---|
541 | CPPAD_ASSERT_UNKNOWN( length_ <= capacity_ ); |
---|
542 | } |
---|
543 | |
---|
544 | /*! add vector to the back of this vector |
---|
545 | (we could not use push_back becasue MS V++ 7.1 did not resolve |
---|
546 | to non-template member function when scalar is used.) |
---|
547 | */ |
---|
548 | template <class Vector> |
---|
549 | void push_vector( |
---|
550 | /// value of the vector that we are adding |
---|
551 | const Vector& v |
---|
552 | ) |
---|
553 | { CheckSimpleVector<Type, Vector>(); |
---|
554 | size_t m = v.size(); |
---|
555 | |
---|
556 | // case where no allcoation is necessary |
---|
557 | if( length_ + m <= capacity_ ) |
---|
558 | { for(size_t i = 0; i < m; i++) |
---|
559 | data_[length_++] = v[i]; |
---|
560 | return; |
---|
561 | } |
---|
562 | |
---|
563 | // store old length, capacity and data |
---|
564 | size_t old_length = length_; |
---|
565 | size_t old_capacity = capacity_; |
---|
566 | Type* old_data = data_; |
---|
567 | |
---|
568 | // set new length, capacity and data |
---|
569 | length_ = 0; |
---|
570 | capacity_ = 0; |
---|
571 | resize(old_length + m); |
---|
572 | |
---|
573 | // copy old data values |
---|
574 | for(size_t i = 0; i < old_length; i++) |
---|
575 | data_[i] = old_data[i]; |
---|
576 | |
---|
577 | // put the new elements in the vector |
---|
578 | CPPAD_ASSERT_UNKNOWN( old_length + m <= capacity_ ); |
---|
579 | for(size_t i = 0; i < m; i++) |
---|
580 | data_[old_length + i] = v[i]; |
---|
581 | |
---|
582 | // free old data |
---|
583 | if( old_capacity > 0 ) |
---|
584 | delete_data(old_data); |
---|
585 | |
---|
586 | CPPAD_ASSERT_UNKNOWN( old_length + m == length_ ); |
---|
587 | CPPAD_ASSERT_UNKNOWN( length_ <= capacity_ ); |
---|
588 | } |
---|
589 | }; |
---|
590 | |
---|
591 | /// output a vector |
---|
592 | template <class Type> |
---|
593 | inline std::ostream& operator << ( |
---|
594 | /// stream to write the vector to |
---|
595 | std::ostream& os , |
---|
596 | /// vector that is output |
---|
597 | const CppAD::vector<Type>& vec ) |
---|
598 | { size_t i = 0; |
---|
599 | size_t n = vec.size(); |
---|
600 | |
---|
601 | os << "{ "; |
---|
602 | while(i < n) |
---|
603 | { os << vec[i++]; |
---|
604 | if( i < n ) |
---|
605 | os << ", "; |
---|
606 | } |
---|
607 | os << " }"; |
---|
608 | return os; |
---|
609 | } |
---|
610 | |
---|
611 | // --------------------------------------------------------------------------- |
---|
612 | /*! |
---|
613 | Class that is used to hold a non-constant element of a vector. |
---|
614 | */ |
---|
615 | class vectorBoolElement { |
---|
616 | /// the boolean data is packed with sizeof(UnitType) bits per value |
---|
617 | typedef size_t UnitType; |
---|
618 | private: |
---|
619 | /// pointer to the UnitType value holding this eleemnt |
---|
620 | UnitType* unit_; |
---|
621 | /// mask for the bit corresponding to this element |
---|
622 | /// (all zero except for bit that corresponds to this element) |
---|
623 | UnitType mask_; |
---|
624 | public: |
---|
625 | /// constructor from member values |
---|
626 | vectorBoolElement( |
---|
627 | /// unit for this element |
---|
628 | UnitType* unit , |
---|
629 | /// mask for this element |
---|
630 | UnitType mask ) |
---|
631 | : unit_(unit) , mask_(mask) |
---|
632 | { } |
---|
633 | /// constuctor from another element |
---|
634 | vectorBoolElement( |
---|
635 | /// other element |
---|
636 | const vectorBoolElement& e ) |
---|
637 | : unit_(e.unit_) , mask_(e.mask_) |
---|
638 | { } |
---|
639 | /// conversion to a boolean value |
---|
640 | operator bool() const |
---|
641 | { return (*unit_ & mask_) != 0; } |
---|
642 | /// assignment of this element to a bool |
---|
643 | vectorBoolElement& operator=( |
---|
644 | /// right hand side for assignment |
---|
645 | bool bit |
---|
646 | ) |
---|
647 | { if(bit) |
---|
648 | *unit_ |= mask_; |
---|
649 | else *unit_ &= ~mask_; |
---|
650 | return *this; |
---|
651 | } |
---|
652 | /// assignment of this element to another element |
---|
653 | vectorBoolElement& operator=(const vectorBoolElement& e) |
---|
654 | { if( *(e.unit_) & e.mask_ ) |
---|
655 | *unit_ |= mask_; |
---|
656 | else *unit_ &= ~mask_; |
---|
657 | return *this; |
---|
658 | } |
---|
659 | }; |
---|
660 | |
---|
661 | class vectorBool { |
---|
662 | /// the boolean data is packed with sizeof(UnitType) bits per value |
---|
663 | typedef size_t UnitType; |
---|
664 | private: |
---|
665 | /// number of bits packed into each UnitType value in data_ |
---|
666 | static const size_t bit_per_unit_ |
---|
667 | = std::numeric_limits<UnitType>::digits; |
---|
668 | /// number of UnitType values in data_ |
---|
669 | size_t n_unit_; |
---|
670 | /// number of bits currently stored in this vector |
---|
671 | size_t length_; |
---|
672 | /// pointer to where the bits are stored |
---|
673 | UnitType *data_; |
---|
674 | |
---|
675 | /// minimum number of UnitType values that can store length_ bits |
---|
676 | /// (note that this is really a function of length_) |
---|
677 | size_t unit_min(void) |
---|
678 | { if( length_ == 0 ) |
---|
679 | return 0; |
---|
680 | return (length_ - 1) / bit_per_unit_ + 1; |
---|
681 | } |
---|
682 | public: |
---|
683 | /// type corresponding to the elements of this vector |
---|
684 | /// (note that non-const elements actually use vectorBoolElement) |
---|
685 | typedef bool value_type; |
---|
686 | |
---|
687 | // static member function |
---|
688 | static size_t bit_per_unit(void) |
---|
689 | { return bit_per_unit_; } |
---|
690 | |
---|
691 | /// default constructor (sets all member data to zero) |
---|
692 | inline vectorBool(void) : n_unit_(0), length_(0), data_(CPPAD_NULL) |
---|
693 | { } |
---|
694 | /// sizing constructor |
---|
695 | inline vectorBool( |
---|
696 | /// number of bits in this vector |
---|
697 | size_t n |
---|
698 | ) : n_unit_(0), length_(n), data_(CPPAD_NULL) |
---|
699 | { if( length_ > 0 ) |
---|
700 | { // set n_unit and data |
---|
701 | size_t min_unit = unit_min(); |
---|
702 | data_ = thread_alloc::create_array<UnitType>(min_unit, n_unit_); |
---|
703 | } |
---|
704 | } |
---|
705 | /// copy constructor |
---|
706 | inline vectorBool( |
---|
707 | /// the *this vector will be a copy of \c v |
---|
708 | const vectorBool& v |
---|
709 | ) : n_unit_(0), length_(v.length_), data_(CPPAD_NULL) |
---|
710 | { if( length_ > 0 ) |
---|
711 | { // set n_unit and data |
---|
712 | size_t min_unit = unit_min(); |
---|
713 | data_ = thread_alloc::create_array<UnitType>(min_unit, n_unit_); |
---|
714 | |
---|
715 | // copy values using UnitType assignment operator |
---|
716 | CPPAD_ASSERT_UNKNOWN( min_unit <= v.n_unit_ ); |
---|
717 | size_t i; |
---|
718 | for(i = 0; i < min_unit; i++) |
---|
719 | data_[i] = v.data_[i]; |
---|
720 | } |
---|
721 | } |
---|
722 | /// destructor |
---|
723 | ~vectorBool(void) |
---|
724 | { if( n_unit_ > 0 ) |
---|
725 | thread_alloc::delete_array(data_); |
---|
726 | } |
---|
727 | |
---|
728 | /// number of elements in this vector |
---|
729 | inline size_t size(void) const |
---|
730 | { return length_; } |
---|
731 | |
---|
732 | /// maximum number of elements current allocation can store |
---|
733 | inline size_t capacity(void) const |
---|
734 | { return n_unit_ * bit_per_unit_; } |
---|
735 | |
---|
736 | /// change number of elements in this vector |
---|
737 | inline void resize( |
---|
738 | /// new number of elements for this vector |
---|
739 | size_t n |
---|
740 | ) |
---|
741 | { length_ = n; |
---|
742 | // check if we can use the current memory |
---|
743 | size_t min_unit = unit_min(); |
---|
744 | if( n_unit_ >= min_unit ) |
---|
745 | return; |
---|
746 | // check if there is old memory to be freed |
---|
747 | if( n_unit_ > 0 ) |
---|
748 | thread_alloc::delete_array(data_); |
---|
749 | // get new memory and set n_unit |
---|
750 | data_ = thread_alloc::create_array<UnitType>(min_unit, n_unit_); |
---|
751 | } |
---|
752 | |
---|
753 | /// free memory and set number of elements to zero |
---|
754 | inline void clear(void) |
---|
755 | { length_ = 0; |
---|
756 | // check if there is old memory to be freed |
---|
757 | if( n_unit_ > 0 ) |
---|
758 | thread_alloc::delete_array(data_); |
---|
759 | n_unit_ = 0; |
---|
760 | } |
---|
761 | |
---|
762 | /// vector assignment operator |
---|
763 | inline vectorBool& operator=( |
---|
764 | /// right hand size of the assingment operation |
---|
765 | const vectorBool& v |
---|
766 | ) |
---|
767 | { size_t i; |
---|
768 | // If original lenght is zero, then resize it. |
---|
769 | // Otherwise a length mismatch is an error. |
---|
770 | if( length_ == 0 ) |
---|
771 | resize( v.length_ ); |
---|
772 | CPPAD_ASSERT_KNOWN( |
---|
773 | length_ == v.length_ , |
---|
774 | "vectorBool: size miss match in assignment operation" |
---|
775 | ); |
---|
776 | size_t min_unit = unit_min(); |
---|
777 | CPPAD_ASSERT_UNKNOWN( min_unit <= n_unit_ ); |
---|
778 | CPPAD_ASSERT_UNKNOWN( min_unit <= v.n_unit_ ); |
---|
779 | for(i = 0; i < min_unit; i++) |
---|
780 | data_[i] = v.data_[i]; |
---|
781 | return *this; |
---|
782 | } |
---|
783 | # if CPPAD_USE_CPLUSPLUS_2011 |
---|
784 | /// vector assignment operator with move semantics |
---|
785 | inline vectorBool& operator=( |
---|
786 | /// right hand size of the assingment operation |
---|
787 | vectorBool&& x |
---|
788 | ) |
---|
789 | { CPPAD_ASSERT_KNOWN( |
---|
790 | length_ == x.length_ || (length_ == 0), |
---|
791 | "vectorBool: size miss match in assignment operation" |
---|
792 | ); |
---|
793 | if( this != &x ) |
---|
794 | { clear(); |
---|
795 | // |
---|
796 | length_ = x.length_; |
---|
797 | n_unit_ = x.n_unit_; |
---|
798 | data_ = x.data_; |
---|
799 | // |
---|
800 | x.length_ = 0; |
---|
801 | x.n_unit_ = 0; |
---|
802 | x.data_ = CPPAD_NULL; |
---|
803 | } |
---|
804 | return *this; |
---|
805 | } |
---|
806 | # endif |
---|
807 | |
---|
808 | |
---|
809 | /// non-constant element access; i.e., we can change this element value |
---|
810 | vectorBoolElement operator[]( |
---|
811 | /// element index, must be less than length |
---|
812 | size_t k |
---|
813 | ) |
---|
814 | { size_t i, j; |
---|
815 | CPPAD_ASSERT_KNOWN( |
---|
816 | k < length_, |
---|
817 | "vectorBool: index greater than or equal vector size" |
---|
818 | ); |
---|
819 | i = k / bit_per_unit_; |
---|
820 | j = k - i * bit_per_unit_; |
---|
821 | return vectorBoolElement(data_ + i , UnitType(1) << j ); |
---|
822 | } |
---|
823 | /// constant element access; i.e., we cannot change this element value |
---|
824 | bool operator[](size_t k) const |
---|
825 | { size_t i, j; |
---|
826 | UnitType unit, mask; |
---|
827 | CPPAD_ASSERT_KNOWN( |
---|
828 | k < length_, |
---|
829 | "vectorBool: index greater than or equal vector size" |
---|
830 | ); |
---|
831 | i = k / bit_per_unit_; |
---|
832 | j = k - i * bit_per_unit_; |
---|
833 | unit = data_[i]; |
---|
834 | mask = UnitType(1) << j; |
---|
835 | return (unit & mask) != 0; |
---|
836 | } |
---|
837 | /// add an element to the back of this vector |
---|
838 | void push_back( |
---|
839 | /// value of the element |
---|
840 | bool bit |
---|
841 | ) |
---|
842 | { CPPAD_ASSERT_UNKNOWN( unit_min() <= n_unit_ ); |
---|
843 | size_t i, j; |
---|
844 | UnitType mask; |
---|
845 | if( length_ + 1 > n_unit_ * bit_per_unit_ ) |
---|
846 | { CPPAD_ASSERT_UNKNOWN( unit_min() == n_unit_ ); |
---|
847 | // store old n_unit and data values |
---|
848 | size_t old_n_unit = n_unit_; |
---|
849 | UnitType* old_data = data_; |
---|
850 | // set new n_unit and data values |
---|
851 | data_ = thread_alloc::create_array<UnitType>(n_unit_+1, n_unit_); |
---|
852 | // copy old data values |
---|
853 | for(i = 0; i < old_n_unit; i++) |
---|
854 | data_[i] = old_data[i]; |
---|
855 | // free old data |
---|
856 | if( old_n_unit > 0 ) |
---|
857 | thread_alloc::delete_array(old_data); |
---|
858 | } |
---|
859 | i = length_ / bit_per_unit_; |
---|
860 | j = length_ - i * bit_per_unit_; |
---|
861 | mask = UnitType(1) << j; |
---|
862 | if( bit ) |
---|
863 | data_[i] |= mask; |
---|
864 | else data_[i] &= ~mask; |
---|
865 | length_++; |
---|
866 | } |
---|
867 | /// add vector to the back of this vector |
---|
868 | template <class Vector> |
---|
869 | void push_vector( |
---|
870 | /// value of the vector that we are adding |
---|
871 | const Vector& v |
---|
872 | ) |
---|
873 | { CheckSimpleVector<bool, Vector>(); |
---|
874 | size_t min_unit = unit_min(); |
---|
875 | CPPAD_ASSERT_UNKNOWN( length_ <= n_unit_ * bit_per_unit_ ); |
---|
876 | // some temporaries |
---|
877 | size_t i, j, k, ell; |
---|
878 | UnitType mask; |
---|
879 | bool bit; |
---|
880 | // store old length |
---|
881 | size_t old_length = length_; |
---|
882 | // new length and minium number of units; |
---|
883 | length_ = length_ + v.size(); |
---|
884 | min_unit = unit_min(); |
---|
885 | if( length_ >= n_unit_ * bit_per_unit_ ) |
---|
886 | { // store old n_unit and data value |
---|
887 | size_t old_n_unit = n_unit_; |
---|
888 | UnitType* old_data = data_; |
---|
889 | // set new n_unit and data values |
---|
890 | data_ = thread_alloc::create_array<UnitType>(min_unit, n_unit_); |
---|
891 | // copy old data values |
---|
892 | for(i = 0; i < old_n_unit; i++) |
---|
893 | data_[i] = old_data[i]; |
---|
894 | // free old data |
---|
895 | if( old_n_unit > 0 ) |
---|
896 | thread_alloc::delete_array(old_data); |
---|
897 | } |
---|
898 | ell = old_length; |
---|
899 | for(k = 0; k < v.size(); k++) |
---|
900 | { |
---|
901 | i = ell / bit_per_unit_; |
---|
902 | j = ell - i * bit_per_unit_; |
---|
903 | bit = v[k]; |
---|
904 | mask = UnitType(1) << j; |
---|
905 | if( bit ) |
---|
906 | data_[i] |= mask; |
---|
907 | else data_[i] &= ~mask; |
---|
908 | ell++; |
---|
909 | } |
---|
910 | CPPAD_ASSERT_UNKNOWN( length_ == ell ); |
---|
911 | CPPAD_ASSERT_UNKNOWN( length_ <= n_unit_ * bit_per_unit_ ); |
---|
912 | } |
---|
913 | }; |
---|
914 | |
---|
915 | /// output a vector |
---|
916 | inline std::ostream& operator << ( |
---|
917 | /// steam to write the vector to |
---|
918 | std::ostream& os , |
---|
919 | /// vector that is output |
---|
920 | const vectorBool& v ) |
---|
921 | { size_t i = 0; |
---|
922 | size_t n = v.size(); |
---|
923 | |
---|
924 | while(i < n) |
---|
925 | os << v[i++]; |
---|
926 | return os; |
---|
927 | } |
---|
928 | |
---|
929 | } // END_CPPAD_NAMESPACE |
---|
930 | # endif |
---|