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