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