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