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