CppAD: A C++ Algorithmic Differentiation Package
20130102
|
00001 /* $Id$ */ 00002 # ifndef CPPAD_SPARSE_LIST_INCLUDED 00003 # define CPPAD_SPARSE_LIST_INCLUDED 00004 00005 /* -------------------------------------------------------------------------- 00006 CppAD: C++ Algorithmic Differentiation: Copyright (C) 2003-12 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 # include <cppad/local/define.hpp> 00016 # include <list> 00017 00018 CPPAD_BEGIN_NAMESPACE 00019 /*! 00020 \defgroup sparse_list_hpp sparse_list.hpp 00021 \{ 00022 \file sparse_list.hpp 00023 Vector of sets of positive integers stored as singly linked lists. 00024 */ 00025 00026 /*! 00027 Vector of sets of positive integers, each set stored as a singly 00028 linked list. 00029 */ 00030 class sparse_list { 00031 private: 00032 /// type used for each set in the vector of sets 00033 /// (note that next is index in data_ for next element in this set). 00034 struct Element { size_t value; size_t next; }; 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 size_t end_; 00040 /// The data for all the elements in all the sets 00041 CppAD::pod_vector<Element> data_; 00042 /// next element 00043 Element next_element_; 00044 public: 00045 // ----------------------------------------------------------------- 00046 /*! Default constructor (no sets) 00047 */ 00048 sparse_list(void) : 00049 n_set_(0) , 00050 end_(0) 00051 { next_element_.value = end_; } 00052 // ----------------------------------------------------------------- 00053 /*! Make use of copy constructor an error 00054 00055 \param v 00056 vector that we are attempting to make a copy of. 00057 */ 00058 sparse_list(const sparse_list& v) 00059 { // Error: 00060 // Probably a sparse_list argument has been passed by value 00061 CPPAD_ASSERT_UNKNOWN(false); 00062 } 00063 // ----------------------------------------------------------------- 00064 /*! Destructor 00065 */ 00066 ~sparse_list(void) 00067 { } 00068 // ----------------------------------------------------------------- 00069 /*! Change number of sets, end marker, and initialize all sets as empty 00070 00071 If \c n_set_in is zero, any memory currently allocated for this object 00072 is freed. Otherwise, new memory may be allocated for the sets (if needed). 00073 00074 \param n_set_in 00075 is the number of sets in this vector of sets. 00076 00077 \param end_in 00078 is the maximum element plus one (the minimum element is 0). 00079 */ 00080 void resize(size_t n_set_in, size_t end_in) 00081 { n_set_ = n_set_in; 00082 end_ = end_in; 00083 next_element_.value = end_in; 00084 if( n_set_in == 0 ) 00085 { // free all memory connected with this object 00086 data_.free(); 00087 return; 00088 } 00089 // now start a new vector with empty sets 00090 data_.erase(); 00091 data_.extend(n_set_); 00092 for(size_t i = 0; i < n_set_; i++) 00093 data_[i].value = end_; 00094 } 00095 // ----------------------------------------------------------------- 00096 /*! Add one element to a set. 00097 00098 \param index 00099 is the index for this set in the vector of sets. 00100 00101 \param element 00102 is the element we are adding to the set. 00103 00104 \par Checked Assertions 00105 \li index < n_set_ 00106 \li element < end_ 00107 */ 00108 void add_element(size_t index, size_t element) 00109 { CPPAD_ASSERT_UNKNOWN( index < n_set_ ); 00110 CPPAD_ASSERT_UNKNOWN( element < end_ ); 00111 00112 size_t value = data_[index].value; 00113 00114 // case of inserting at beginning 00115 if( element < value ) 00116 { size_t insert = data_.extend(1); 00117 data_[insert] = data_[index]; 00118 data_[index].value = element; 00119 data_[index].next = insert; 00120 return; 00121 } 00122 00123 // search list for place to insert 00124 size_t previous = index; 00125 size_t current = data_[previous].next; 00126 value = data_[current].value; 00127 while( value < element ) 00128 { previous = current; 00129 current = data_[previous].next; 00130 value = data_[current].value; 00131 } 00132 if( element != value ) 00133 { CPPAD_ASSERT_UNKNOWN( element < value ); 00134 size_t insert = data_.extend(1); 00135 // 00136 data_[insert].next = data_[previous].next; 00137 data_[previous].next = insert; 00138 data_[insert].value = element; 00139 } 00140 } 00141 // ----------------------------------------------------------------- 00142 /*! Is an element of a set. 00143 00144 \param index 00145 is the index for this set in the vector of sets. 00146 00147 \param element 00148 is the element we are adding to the set. 00149 00150 \par Checked Assertions 00151 \li index < n_set_ 00152 \li element < end_ 00153 */ 00154 bool is_element(size_t index, size_t element) 00155 { CPPAD_ASSERT_UNKNOWN( index < n_set_ ); 00156 CPPAD_ASSERT_UNKNOWN( element < end_ ); 00157 00158 size_t i = index; 00159 size_t value = data_[i].value; 00160 while( value < element ) 00161 { i = data_[i].next; 00162 value = data_[i].value; 00163 } 00164 00165 return element == value; 00166 } 00167 // ----------------------------------------------------------------- 00168 /*! Begin retrieving elements from one of the sets. 00169 00170 \param index 00171 is the index for the set that is going to be retrieved. 00172 The elements of the set are retrieved in increasing order. 00173 00174 \par Checked Assertions 00175 \li index < n_set_ 00176 00177 */ 00178 void begin(size_t index) 00179 { // initialize element to search for in this set 00180 CPPAD_ASSERT_UNKNOWN( index < n_set_ ); 00181 next_element_ = data_[index]; 00182 00183 return; 00184 } 00185 // ----------------------------------------------------------------- 00186 /*! Get the next element from the current retrieval set. 00187 00188 \return 00189 is the next element in the set with index 00190 specified by the previous call to \c begin. 00191 If no such element exists, \c this->end() is returned. 00192 00193 \par Assumption 00194 There is no call to \c add_element since the previvious \c begin 00195 */ 00196 size_t next_element(void) 00197 { size_t element = next_element_.value; 00198 if( element != end_ ) 00199 next_element_ = data_[next_element_.next]; 00200 00201 return element; 00202 } 00203 // ----------------------------------------------------------------- 00204 /*! Assign the empty set to one of the sets. 00205 00206 \param target 00207 is the index of the set we are setting to the empty set. 00208 00209 \par Checked Assertions 00210 \li target < n_set_ 00211 */ 00212 void clear(size_t target) 00213 { CPPAD_ASSERT_UNKNOWN( target < n_set_ ); 00214 data_[target].value = end_; 00215 } 00216 // ----------------------------------------------------------------- 00217 /*! Assign one set equal to another set. 00218 00219 \param this_target 00220 is the index (in this \c sparse_list object) of the set being assinged. 00221 00222 \param other_source 00223 is the index (in the other \c sparse_list object) of the 00224 that we are using as the value to assign to the target set. 00225 00226 \param other 00227 is the other \c sparse_list object (which may be the same as this 00228 \c sparse_list object). 00229 00230 \par Checked Assertions 00231 \li this_target < n_set_ 00232 \li other_index < other.n_set_ 00233 */ 00234 void assignment( 00235 size_t this_target , 00236 size_t other_source , 00237 const sparse_list& other ) 00238 { CPPAD_ASSERT_UNKNOWN( this_target < n_set_ ); 00239 CPPAD_ASSERT_UNKNOWN( other_source < other.n_set_ ); 00240 CPPAD_ASSERT_UNKNOWN( end_ == other.end() ); 00241 00242 size_t this_index = this_target; 00243 size_t other_index = other_source; 00244 size_t value = other.data_[other_index].value; 00245 while( value != end_ ) 00246 { size_t next = data_.extend(1); 00247 data_[this_index].value = value; 00248 data_[this_index].next = next; 00249 this_index = next; 00250 other_index = other.data_[other_index].next; 00251 value = other.data_[other_index].value; 00252 } 00253 data_[this_index].value = end_; 00254 } 00255 // ----------------------------------------------------------------- 00256 /*! Assign a set equal to the union of two other sets. 00257 00258 \param this_target 00259 is the index (in this \c sparse_list object) of the set being assinged. 00260 00261 \param this_left 00262 is the index (in this \c sparse_list object) of the 00263 left operand for the union operation. 00264 It is OK for \a this_target and \a this_left to be the same value. 00265 00266 \param other_right 00267 is the index (in the other \c sparse_list object) of the 00268 right operand for the union operation. 00269 It is OK for \a this_target and \a other_right to be the same value. 00270 00271 \param other 00272 is the other \c sparse_list object (which may be the same as this 00273 \c sparse_list object). 00274 00275 \par Checked Assertions 00276 \li this_target < n_set_ 00277 \li this_left < n_set_ 00278 \li other_right < other.n_set_ 00279 */ 00280 void binary_union( 00281 size_t this_target , 00282 size_t this_left , 00283 size_t other_right , 00284 const sparse_list& other ) 00285 { 00286 CPPAD_ASSERT_UNKNOWN( this_target < n_set_ ); 00287 CPPAD_ASSERT_UNKNOWN( this_left < n_set_ ); 00288 CPPAD_ASSERT_UNKNOWN( other_right < other.n_set_ ); 00289 CPPAD_ASSERT_UNKNOWN( end_ == other.end() ); 00290 00291 // merge left and right into target set 00292 size_t left_value = data_[this_left].value; 00293 size_t left_next = data_[this_left].next; 00294 size_t right_value = other.data_[other_right].value; 00295 size_t right_next = other.data_[other_right].next; 00296 size_t current = this_target; 00297 while( (left_value < end_) | (right_value < end_) ) 00298 { if( left_value == right_value ) 00299 { right_value = other.data_[right_next].value; 00300 right_next = other.data_[right_next].next; 00301 } 00302 size_t next = data_.extend(1); 00303 data_[current].next = next; 00304 if( left_value < right_value ) 00305 { data_[current].value = left_value; 00306 left_value = data_[left_next].value; 00307 left_next = data_[left_next].next; 00308 } 00309 else 00310 { data_[current].value = right_value; 00311 right_value = other.data_[right_next].value; 00312 right_next = other.data_[right_next].next; 00313 } 00314 current = next; 00315 } 00316 data_[current].value = end_; 00317 } 00318 // ----------------------------------------------------------------- 00319 /*! Sum over all sets of the number of elements 00320 00321 /return 00322 The the total number of elements 00323 */ 00324 size_t number_elements(void) const 00325 { size_t i, count; 00326 count = 0; 00327 for(i = 0; i < n_set_; i++) 00328 { size_t index = i; 00329 while( data_[index].value != end_ ) 00330 { count++; 00331 index = data_[index].next; 00332 } 00333 } 00334 return count; 00335 } 00336 // ----------------------------------------------------------------- 00337 /*! Fetch n_set for vector of sets object. 00338 00339 \return 00340 Number of from sets for this vector of sets object 00341 */ 00342 size_t n_set(void) const 00343 { return n_set_; } 00344 // ----------------------------------------------------------------- 00345 /*! Fetch end for this vector of sets object. 00346 00347 \return 00348 is the maximum element value plus one (the minimum element value is 0). 00349 */ 00350 size_t end(void) const 00351 { return end_; } 00352 }; 00353 00354 /*! 00355 Copy a user vector of sets sparsity pattern to an internal sparse_list object. 00356 00357 \tparam VectorSet 00358 is a simple vector with elements of type \c std::list<set>. 00359 00360 \param internal 00361 The input value of sparisty does not matter. 00362 Upon return it contains the same sparsity pattern as \c user 00363 (or the transposed sparsity pattern). 00364 00365 \param user 00366 sparsity pattern that we are placing \c internal. 00367 00368 \param n_row 00369 number of rows in the sparsity pattern in \c user 00370 (range dimension). 00371 00372 \param n_col 00373 number of columns in the sparsity pattern in \c user 00374 (domain dimension). 00375 00376 \param transpose 00377 if true, the sparsity pattern in \c internal is the transpose 00378 of the one in \c user. 00379 Otherwise it is the same sparsity pattern. 00380 */ 00381 template<class VectorSet> 00382 void sparsity_user2internal( 00383 sparse_list& internal , 00384 const VectorSet& user , 00385 size_t n_row , 00386 size_t n_col , 00387 bool transpose ) 00388 { CPPAD_ASSERT_UNKNOWN( n_row == size_t(user.size()) ); 00389 00390 CPPAD_ASSERT_KNOWN( 00391 size_t( user.size() ) == n_row, 00392 "Size of this vector of lists sparsity pattern is not equal " 00393 "the range dimension for the corresponding function." 00394 ); 00395 00396 size_t i, j; 00397 std::set<size_t>::const_iterator itr; 00398 00399 // transposed pattern case 00400 if( transpose ) 00401 { internal.resize(n_col, n_row); 00402 for(i = 0; i < n_row; i++) 00403 { itr = user[i].begin(); 00404 while(itr != user[i].end()) 00405 { j = *itr++; 00406 CPPAD_ASSERT_UNKNOWN( j < n_col ); 00407 internal.add_element(j, i); 00408 } 00409 } 00410 return; 00411 } 00412 00413 // same pattern case 00414 internal.resize(n_row, n_col); 00415 for(i = 0; i < n_row; i++) 00416 { itr = user[i].begin(); 00417 while(itr != user[i].end()) 00418 { j = *itr++; 00419 CPPAD_ASSERT_UNKNOWN( j < n_col ); 00420 internal.add_element(i, j); 00421 } 00422 } 00423 return; 00424 } 00425 00426 00427 /*! \} */ 00428 CPPAD_END_NAMESPACE 00429 # endif