CppAD: A C++ Algorithmic Differentiation Package 20110419
|
00001 // $Id$ 00002 # ifndef CPPAD_SPARSE_PACK_INCLUDED 00003 # define CPPAD_SPARSE_PACK_INCLUDED 00004 00005 /* -------------------------------------------------------------------------- 00006 CppAD: C++ Algorithmic Differentiation: Copyright (C) 2003-11 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 # include <cppad/local/cppad_assert.hpp> 00016 00017 CPPAD_BEGIN_NAMESPACE 00018 /*! 00019 \file sparse_pack.hpp 00020 Vector of sets of positive integers. 00021 */ 00022 00023 /*! 00024 Vector of sets of postivie integers, each set stored as a packed boolean array. 00025 */ 00026 00027 00028 class sparse_pack { 00029 private: 00030 /// Type used to pack elements (should be the same as corresponding 00031 /// typedef in multiple_n_bit() in test_more/sparse_hacobian.cpp) 00032 typedef size_t Pack; 00033 /// Number of bits per Pack value 00034 static const size_t n_bit_ = std::numeric_limits<Pack>::digits; 00035 /// Number of sets that we are representing 00036 /// (set by constructor and resize). 00037 size_t n_set_; 00038 /// Possible elements in each set are 0, 1, ..., end_ - 1 00039 /// (set by constructor and resize). 00040 size_t end_; 00041 /// Number of \c Pack values necessary to represent \c end_ bits. 00042 /// (set by constructor and resize). 00043 size_t n_pack_; 00044 /// Is the memory pointed to by \c data_ allocated by this object 00045 /// (set by contructor and resize) 00046 bool allocated_; 00047 /// Pointer to the beginning of data for all the sets. 00048 Pack* data_; 00049 /// index for which we were retrieving next_element 00050 /// (use n_set_ if no such index exists). 00051 size_t next_index_; 00052 /// Next element to start search at 00053 /// (use end_ for no such element exists; i.e., past end of the set). 00054 size_t next_element_; 00055 public: 00056 // ----------------------------------------------------------------- 00057 /*! Default constructor (no sets) 00058 */ 00059 sparse_pack(void) : 00060 n_set_(0) , 00061 end_(0) , 00062 n_pack_(0) , 00063 allocated_(false) , 00064 data_(CPPAD_NULL) , 00065 next_index_(0) , 00066 next_element_(0) 00067 { } 00068 // ----------------------------------------------------------------- 00069 /*! Make use of copy constructor an error 00070 00071 \param v 00072 vector that we are attempting to make a copy of. 00073 */ 00074 sparse_pack(const sparse_pack& v) 00075 { // Error: 00076 // Probably a sparse_pack argument has been passed by value 00077 CPPAD_ASSERT_UNKNOWN(0); 00078 } 00079 // ----------------------------------------------------------------- 00080 /*! Destructor 00081 */ 00082 ~sparse_pack(void) 00083 { if( allocated_ ) 00084 { allocated_ = false; 00085 CPPAD_TRACK_DEL_VEC( data_ ); 00086 } 00087 } 00088 // ----------------------------------------------------------------- 00089 /*! Change number of sets, set end, and initialize all sets as empty 00090 00091 Any memory currently allocated for this object is freed. If both 00092 \a n_set_in and \a end_in are non-zero new memory is allocated, otherwise 00093 no new memory is allocated for the object. 00094 00095 \param n_set_in 00096 is the number of sets in this vector of sets. 00097 00098 \param end_in 00099 is the maximum element plus one (the minimum element is 0). 00100 */ 00101 void resize(size_t n_set_in, size_t end_in) 00102 { Pack zero(0); 00103 if( allocated_ ) 00104 { allocated_ = false; 00105 CPPAD_TRACK_DEL_VEC(data_); 00106 } 00107 00108 n_set_ = n_set_in; 00109 end_ = end_in; 00110 n_pack_ = ( 1 + (end_ - 1) / n_bit_ ); 00111 size_t i = n_set_ * n_pack_; 00112 00113 if( i > 0 ) 00114 { data_ = CPPAD_TRACK_NEW_VEC(i, data_); 00115 allocated_ = true; 00116 while(i--) 00117 data_[i] = zero; 00118 } 00119 00120 // values that signify past end of list 00121 next_index_ = n_set_; 00122 next_element_ = end_; 00123 } 00124 // ----------------------------------------------------------------- 00125 /*! Add one element to a set. 00126 00127 \param index 00128 is the index for this set in the vector of sets. 00129 00130 \param element 00131 is the element we are adding to the set. 00132 00133 \par Checked Assertions 00134 \li index < n_set_ 00135 \li element < end_ 00136 */ 00137 void add_element(size_t index, size_t element) 00138 { static Pack one(1); 00139 CPPAD_ASSERT_UNKNOWN( index < n_set_ ); 00140 CPPAD_ASSERT_UNKNOWN( element < end_ ); 00141 size_t j = element / n_bit_; 00142 size_t k = element - j * n_bit_; 00143 Pack mask = one << k; 00144 data_[ index * n_pack_ + j] |= mask; 00145 } 00146 // ----------------------------------------------------------------- 00147 /*! Begin retrieving elements from one of the sets. 00148 00149 \param index 00150 is the index for the set that is going to be retrieved. 00151 The elements of the set are retrieved in increasing order. 00152 00153 \par Checked Assertions 00154 \li index < n_set_ 00155 */ 00156 void begin(size_t index) 00157 { // initialize element to search for in this set 00158 CPPAD_ASSERT_UNKNOWN( index < n_set_ ); 00159 next_index_ = index; 00160 next_element_ = 0; 00161 } 00162 /*! Get the next element from the current retrieval set. 00163 00164 \return 00165 is the next element in the set with index 00166 specified by the previous call to \c begin. 00167 If no such element exists, \c this->end() is returned. 00168 */ 00169 size_t next_element(void) 00170 { static Pack one(1); 00171 CPPAD_ASSERT_UNKNOWN( next_index_ < n_set_ ); 00172 CPPAD_ASSERT_UNKNOWN( next_element_ <= end_ ); 00173 00174 if( next_element_ == end_ ) 00175 return end_; 00176 00177 // initialize packed data index 00178 size_t j = next_element_ / n_bit_; 00179 00180 // initialize bit index 00181 size_t k = next_element_ - j * n_bit_; 00182 00183 // start search at this packed value 00184 Pack check = data_[ next_index_ * n_pack_ + j ]; 00185 while( true ) 00186 { // increment next element before checking this one 00187 next_element_++; 00188 // check if this element is in the set 00189 if( check & (one << k) ) 00190 return next_element_ - 1; 00191 // check if no more elements in the set 00192 if( next_element_ == end_ ) 00193 return end_; 00194 // increment bit index in Pack value so corresponds to 00195 // next element 00196 k++; 00197 CPPAD_ASSERT_UNKNOWN( k <= n_bit_ ); 00198 if( k == n_bit_ ) 00199 { // get next packed value 00200 k = 0; 00201 j++; 00202 CPPAD_ASSERT_UNKNOWN( j < n_pack_ ); 00203 check = data_[ next_index_ * n_pack_ + j ]; 00204 } 00205 } 00206 // should never get here 00207 CPPAD_ASSERT_UNKNOWN(false); 00208 return end_; 00209 } 00210 // ----------------------------------------------------------------- 00211 /*! Assign the empty set to one of the sets. 00212 00213 \param target 00214 is the index of the set we are setting to the empty set. 00215 00216 \par Checked Assertions 00217 \li target < n_set_ 00218 */ 00219 void clear(size_t target) 00220 { // value with all its bits set to false 00221 static Pack zero(0); 00222 CPPAD_ASSERT_UNKNOWN( target < n_set_ ); 00223 Pack *t = data_ + target * n_pack_; 00224 00225 size_t j = n_pack_; 00226 while(j--) 00227 *t++ = zero; 00228 } 00229 // ----------------------------------------------------------------- 00230 /*! Assign one set equal to another set. 00231 00232 \param this_target 00233 is the index (in this \c sparse_pack object) of the set being assinged. 00234 00235 \param other_value 00236 is the index (in the other \c sparse_pack object) of the 00237 that we are using as the value to assign to the target set. 00238 00239 \param other 00240 is the other \c sparse_pack object (which may be the same as this 00241 \c sparse_pack object). 00242 00243 \par Checked Assertions 00244 \li this_target < n_set_ 00245 \li other_value < other.n_set_ 00246 \li n_pack_ == other.n_pack_ 00247 */ 00248 void assignment( 00249 size_t this_target , 00250 size_t other_value , 00251 const sparse_pack& other ) 00252 { CPPAD_ASSERT_UNKNOWN( this_target < n_set_ ); 00253 CPPAD_ASSERT_UNKNOWN( other_value < other.n_set_ ); 00254 CPPAD_ASSERT_UNKNOWN( n_pack_ == other.n_pack_ ); 00255 Pack *t = data_ + this_target * n_pack_; 00256 Pack *v = other.data_ + other_value * n_pack_; 00257 00258 size_t j = n_pack_; 00259 while(j--) 00260 *t++ = *v++; 00261 } 00262 00263 // ----------------------------------------------------------------- 00264 /*! Assing a set equal to the union of two other sets. 00265 00266 \param this_target 00267 is the index (in this \c sparse_pack object) of the set being assinged. 00268 00269 \param this_left 00270 is the index (in this \c sparse_pack object) of the 00271 left operand for the union operation. 00272 It is OK for \a this_target and \a this_left to be the same value. 00273 00274 \param other_right 00275 is the index (in the other \c sparse_pack object) of the 00276 right operand for the union operation. 00277 It is OK for \a this_target and \a other_right to be the same value. 00278 00279 \param other 00280 is the other \c sparse_pack object (which may be the same as this 00281 \c sparse_pack object). 00282 00283 \par Checked Assertions 00284 \li this_target < n_set_ 00285 \li this_left < n_set_ 00286 \li other_right < other.n_set_ 00287 \li n_pack_ == other.n_pack_ 00288 */ 00289 void binary_union( 00290 size_t this_target , 00291 size_t this_left , 00292 size_t other_right , 00293 const sparse_pack& other ) 00294 { CPPAD_ASSERT_UNKNOWN( this_target < n_set_ ); 00295 CPPAD_ASSERT_UNKNOWN( this_left < n_set_ ); 00296 CPPAD_ASSERT_UNKNOWN( other_right < other.n_set_ ); 00297 CPPAD_ASSERT_UNKNOWN( n_pack_ == other.n_pack_ ); 00298 00299 Pack *t = data_ + this_target * n_pack_; 00300 Pack *l = data_ + this_left * n_pack_; 00301 Pack *r = other.data_ + other_right * n_pack_; 00302 00303 size_t j = n_pack_; 00304 while(j--) 00305 *t++ = (*l++ | *r++); 00306 } 00307 // ----------------------------------------------------------------- 00308 /*! Amount of memory used by this vector of sets 00309 00310 \return 00311 The amount of memory in units of type unsigned char memory. 00312 */ 00313 size_t memory(void) const 00314 { return n_set_ * n_pack_ * sizeof(Pack); 00315 } 00316 // ----------------------------------------------------------------- 00317 /*! Fetch n_set for vector of sets object. 00318 00319 \return 00320 Number of from sets for this vector of sets object 00321 */ 00322 size_t n_set(void) const 00323 { return n_set_; } 00324 // ----------------------------------------------------------------- 00325 /*! Fetch end for this vector of sets object. 00326 00327 \return 00328 is the maximum element value plus one (the minimum element value is 0). 00329 */ 00330 size_t end(void) const 00331 { return end_; } 00332 }; 00333 00334 CPPAD_END_NAMESPACE 00335 # endif