CppAD: A C++ Algorithmic Differentiation Package 20110419
|
00001 // $Id$ 00002 # ifndef CPPAD_SPARSE_SET_INCLUDED 00003 # define CPPAD_SPARSE_SET_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 <set> 00016 # include <algorithm> 00017 # include <cppad/local/cppad_assert.hpp> 00018 00019 00020 CPPAD_BEGIN_NAMESPACE 00021 /*! 00022 \file sparse_set.hpp 00023 Vector of sets of positive integers. 00024 */ 00025 00026 /*! 00027 Vector of sets of postivie integers, each set stored as a standard set. 00028 */ 00029 00030 class sparse_set { 00031 private: 00032 /// type used for each set in the vector sets 00033 typedef std::set<size_t> Set; 00034 /// Number of sets that we are representing 00035 /// (set by constructor and resize). 00036 size_t n_set_; 00037 /// Possible elements in each set are 0, 1, ..., end_ - 1 00038 /// (set by constructor and resize). 00039 size_t end_; 00040 /// The vector of sets 00041 CppAD::vector<Set> data_; 00042 /// index for which we were retrieving next_element 00043 /// (use n_set_ if no such index exists). 00044 size_t next_index_; 00045 /// Next element that we will return using next_element 00046 /// (use end_ for no such element exists; i.e., past end of the set). 00047 Set::iterator next_element_; 00048 public: 00049 // ----------------------------------------------------------------- 00050 /*! Default constructor (no sets) 00051 */ 00052 sparse_set(void) : 00053 n_set_(0) , 00054 end_(0) , 00055 next_index_(0) 00056 { } 00057 // ----------------------------------------------------------------- 00058 /*! Make use of copy constructor an error 00059 00060 \param v 00061 vector that we are attempting to make a copy of. 00062 */ 00063 sparse_set(const sparse_set& v) 00064 { // Error: 00065 // Probably a sparse_set argument has been passed by value 00066 CPPAD_ASSERT_UNKNOWN(0); 00067 } 00068 // ----------------------------------------------------------------- 00069 /*! Destructor 00070 */ 00071 ~sparse_set(void) 00072 { } 00073 // ----------------------------------------------------------------- 00074 /*! Change number of sets, set end, and initialize all sets as empty 00075 00076 Any memory currently allocated for this object is freed. If 00077 \a n_set_in is zero, no new memory is allocated for the set. 00078 Otherwise, new memory may be allocated for the sets. 00079 00080 \param n_set_in 00081 is the number of sets in this vector of sets. 00082 00083 \param end_in 00084 is the maximum element plus one (the minimum element is 0). 00085 */ 00086 void resize(size_t n_set_in, size_t end_in) 00087 { n_set_ = n_set_in; 00088 end_ = end_in; 00089 // free all memory connected with data_ 00090 data_.resize(0); 00091 // now start a new vector with empty sets 00092 data_.resize(n_set_); 00093 00094 // value that signfies past end of list 00095 next_index_ = n_set_; 00096 } 00097 // ----------------------------------------------------------------- 00098 /*! Add one element to a set. 00099 00100 \param index 00101 is the index for this set in the vector of sets. 00102 00103 \param element 00104 is the element we are adding to the set. 00105 00106 \par Checked Assertions 00107 \li index < n_set_ 00108 \li element < end_ 00109 */ 00110 void add_element(size_t index, size_t element) 00111 { // This routine should use the std::insert operator 00112 // that cashes the iterator of previous insertion for when 00113 // insertions occur in order. We should speed test that this 00114 // actually makes things faster. 00115 CPPAD_ASSERT_UNKNOWN( index < n_set_ ); 00116 CPPAD_ASSERT_UNKNOWN( element < end_ ); 00117 data_[ index ].insert( element ); 00118 } 00119 // ----------------------------------------------------------------- 00120 /*! Begin retrieving elements from one of the sets. 00121 00122 \param index 00123 is the index for the set that is going to be retrieved. 00124 The elements of the set are retrieved in increasing order. 00125 00126 \par Checked Assertions 00127 \li index < n_set_ 00128 */ 00129 void begin(size_t index) 00130 { // initialize element to search for in this set 00131 CPPAD_ASSERT_UNKNOWN( index < n_set_ ); 00132 next_index_ = index; 00133 next_element_ = data_[index].begin(); 00134 00135 return; 00136 } 00137 // ----------------------------------------------------------------- 00138 /*! Get the next element from the current retrieval set. 00139 00140 \return 00141 is the next element in the set with index 00142 specified by the previous call to \c begin. 00143 If no such element exists, \c this->end() is returned. 00144 */ 00145 size_t next_element(void) 00146 { 00147 if( next_element_ == data_[next_index_].end() ) 00148 return end_; 00149 00150 return *next_element_++; 00151 } 00152 // ----------------------------------------------------------------- 00153 /*! Assign the empty set to one of the sets. 00154 00155 \param target 00156 is the index of the set we are setting to the empty set. 00157 00158 \par Checked Assertions 00159 \li target < n_set_ 00160 */ 00161 void clear(size_t target) 00162 { CPPAD_ASSERT_UNKNOWN( target < n_set_ ); 00163 data_[target].clear(); 00164 } 00165 // ----------------------------------------------------------------- 00166 /*! Assign one set equal to another set. 00167 00168 \param this_target 00169 is the index (in this \c sparse_set object) of the set being assinged. 00170 00171 \param other_value 00172 is the index (in the other \c sparse_set object) of the 00173 that we are using as the value to assign to the target set. 00174 00175 \param other 00176 is the other \c sparse_set object (which may be the same as this 00177 \c sparse_set object). 00178 00179 \par Checked Assertions 00180 \li this_target < n_set_ 00181 \li other_value < other.n_set_ 00182 */ 00183 void assignment( 00184 size_t this_target , 00185 size_t other_value , 00186 const sparse_set& other ) 00187 { CPPAD_ASSERT_UNKNOWN( this_target < n_set_ ); 00188 CPPAD_ASSERT_UNKNOWN( other_value < other.n_set_ ); 00189 00190 data_[this_target] = other.data_[other_value]; 00191 } 00192 00193 // ----------------------------------------------------------------- 00194 /*! Assign a set equal to the union of two other sets. 00195 00196 \param this_target 00197 is the index (in this \c sparse_set object) of the set being assinged. 00198 00199 \param this_left 00200 is the index (in this \c sparse_set object) of the 00201 left operand for the union operation. 00202 It is OK for \a this_target and \a this_left to be the same value. 00203 00204 \param other_right 00205 is the index (in the other \c sparse_set object) of the 00206 right operand for the union operation. 00207 It is OK for \a this_target and \a other_right to be the same value. 00208 00209 \param other 00210 is the other \c sparse_set object (which may be the same as this 00211 \c sparse_set object). 00212 00213 \par Checked Assertions 00214 \li this_target < n_set_ 00215 \li this_left < n_set_ 00216 \li other_right < other.n_set_ 00217 */ 00218 void binary_union( 00219 size_t this_target , 00220 size_t this_left , 00221 size_t other_right , 00222 const sparse_set& other ) 00223 { CPPAD_ASSERT_UNKNOWN( this_target < n_set_ ); 00224 CPPAD_ASSERT_UNKNOWN( this_left < n_set_ ); 00225 CPPAD_ASSERT_UNKNOWN( other_right < other.n_set_ ); 00226 00227 // use a temporary set for holding results 00228 // (in case target set is same as one of the other sets) 00229 Set temp; 00230 std::set_union( 00231 data_[this_left].begin() , 00232 data_[this_left].end() , 00233 other.data_[other_right].begin() , 00234 other.data_[other_right].end() , 00235 std::inserter(temp, temp.begin()) 00236 ); 00237 00238 // move results to the target set with out copying elements 00239 data_[this_target].swap(temp); 00240 00241 } 00242 // ----------------------------------------------------------------- 00243 /*! Sum over all sets of the number of elements 00244 00245 /return 00246 The the total number of elements 00247 */ 00248 size_t number_elements(void) const 00249 { size_t i, count; 00250 count = 0; 00251 for(i = 0; i < n_set_; i++) 00252 count += data_[i].size(); 00253 return count; 00254 } 00255 // ----------------------------------------------------------------- 00256 /*! Fetch n_set for vector of sets object. 00257 00258 \return 00259 Number of from sets for this vector of sets object 00260 */ 00261 size_t n_set(void) const 00262 { return n_set_; } 00263 // ----------------------------------------------------------------- 00264 /*! Fetch end for this vector of sets object. 00265 00266 \return 00267 is the maximum element value plus one (the minimum element value is 0). 00268 */ 00269 size_t end(void) const 00270 { return end_; } 00271 }; 00272 00273 CPPAD_END_NAMESPACE 00274 # endif