CppAD: A C++ Algorithmic Differentiation Package 20110419
sparse_set.hpp
Go to the documentation of this file.
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