CppAD: A C++ Algorithmic Differentiation Package  20130102
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-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
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines