CppAD: A C++ Algorithmic Differentiation Package  20130918
sparse_list.hpp
Go to the documentation of this file.
00001 /* $Id$ */
00002 # ifndef CPPAD_SPARSE_LIST_INCLUDED
00003 # define CPPAD_SPARSE_LIST_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 <cppad/local/define.hpp>
00016 # include <list>
00017 
00018 namespace CppAD { // BEGIN_CPPAD_NAMESPACE
00019 /*!
00020 \file sparse_list.hpp
00021 Vector of sets of positive integers stored as singly linked lists.
00022 */
00023 
00024 /*!
00025 Vector of sets of positive integers, each set stored as a singly
00026 linked list.
00027 */
00028 class sparse_list {
00029 private:
00030      /// type used for each set in the vector of sets
00031      /// (note that next is index in data_ for next element in this set).
00032      struct Element { size_t value; size_t next; };
00033      /// Number of sets that we are representing
00034      /// (set by constructor and resize).
00035      size_t n_set_;
00036      /// Possible elements in each set are 0, 1, ..., end_ - 1;
00037      size_t end_;
00038      /// The data for all the elements in all the sets
00039      CppAD::pod_vector<Element> data_;
00040      /// next element
00041      Element next_element_;
00042 public:
00043      // -----------------------------------------------------------------
00044      /*! Default constructor (no sets)
00045      */
00046      sparse_list(void) : 
00047      n_set_(0)                     , 
00048      end_(0) 
00049      {    next_element_.value = end_; }
00050      // -----------------------------------------------------------------
00051      /*! Make use of copy constructor an error
00052  
00053      \param v
00054      vector that we are attempting to make a copy of.
00055      */
00056      sparse_list(const sparse_list& v)
00057      {    // Error: 
00058           // Probably a sparse_list argument has been passed by value
00059           CPPAD_ASSERT_UNKNOWN(false); 
00060      }
00061      // -----------------------------------------------------------------
00062      /*! Destructor 
00063      */
00064      ~sparse_list(void)
00065      { } 
00066      // -----------------------------------------------------------------
00067      /*! Change number of sets, end marker, and initialize all sets as empty
00068 
00069      If \c n_set_in is zero, any memory currently allocated for this object 
00070      is freed. Otherwise, new memory may be allocated for the sets (if needed).
00071 
00072      \param n_set_in
00073      is the number of sets in this vector of sets.
00074 
00075      \param end_in
00076      is the maximum element plus one (the minimum element is 0).
00077      */
00078      void resize(size_t n_set_in, size_t end_in) 
00079      {    n_set_                 = n_set_in;
00080           end_                   = end_in;
00081           next_element_.value    = end_in;
00082           if( n_set_in == 0 )
00083           {    // free all memory connected with this object
00084                data_.free();
00085                return;
00086           }
00087           // now start a new vector with empty sets
00088           data_.erase();
00089           data_.extend(n_set_);
00090           for(size_t i = 0; i < n_set_; i++)
00091                data_[i].value = end_;
00092      }
00093      // -----------------------------------------------------------------
00094      /*! Add one element to a set.
00095 
00096      \param index
00097      is the index for this set in the vector of sets.
00098 
00099      \param element
00100      is the element we are adding to the set.
00101 
00102      \par Checked Assertions
00103      \li index    < n_set_
00104      \li element  < end_
00105      */
00106      void add_element(size_t index, size_t element)
00107      {    CPPAD_ASSERT_UNKNOWN( index   < n_set_ );
00108           CPPAD_ASSERT_UNKNOWN( element < end_ );
00109 
00110           size_t value = data_[index].value;
00111 
00112           // case of inserting at beginning
00113           if( element < value )
00114           {    size_t insert       = data_.extend(1);
00115                data_[insert]       = data_[index];
00116                data_[index].value  = element;
00117                data_[index].next   = insert;
00118                return;
00119           }
00120 
00121           // search list for place to insert 
00122           size_t  previous = index;
00123           size_t  current  = data_[previous].next;
00124           value            = data_[current].value;
00125           while( value < element )
00126           {    previous = current;
00127                current = data_[previous].next;
00128                value   = data_[current].value; 
00129           }
00130           if( element != value )
00131           {    CPPAD_ASSERT_UNKNOWN( element < value ); 
00132                size_t insert         = data_.extend(1);
00133                //
00134                data_[insert].next    = data_[previous].next;
00135                data_[previous].next  = insert;
00136                data_[insert].value   = element;
00137           }
00138      }
00139      // -----------------------------------------------------------------
00140      /*! Is an element of a set.
00141 
00142      \param index
00143      is the index for this set in the vector of sets.
00144 
00145      \param element
00146      is the element we are adding to the set.
00147 
00148      \par Checked Assertions
00149      \li index    < n_set_
00150      \li element  < end_
00151      */
00152      bool is_element(size_t index, size_t element)
00153      {    CPPAD_ASSERT_UNKNOWN( index   < n_set_ );
00154           CPPAD_ASSERT_UNKNOWN( element < end_ );
00155 
00156           size_t i     = index;
00157           size_t value = data_[i].value;
00158           while( value < element )
00159           {    i     = data_[i].next;
00160                value = data_[i].value;
00161           }
00162 
00163           return element == value;
00164      }
00165      // -----------------------------------------------------------------
00166      /*! Begin retrieving elements from one of the sets.
00167      
00168      \param index
00169      is the index for the set that is going to be retrieved.
00170      The elements of the set are retrieved in increasing order.
00171 
00172      \par Checked Assertions
00173      \li index  < n_set_
00174 
00175      */
00176      void begin(size_t index)
00177      {    // initialize element to search for in this set
00178           CPPAD_ASSERT_UNKNOWN( index < n_set_ );
00179           next_element_  = data_[index]; 
00180 
00181           return;
00182      }
00183      // -----------------------------------------------------------------
00184      /*! Get the next element from the current retrieval set.
00185      
00186      \return
00187      is the next element in the set with index
00188      specified by the previous call to \c begin.
00189      If no such element exists, \c this->end() is returned.
00190 
00191      \par Assumption
00192      There is no call to \c add_element since the previvious \c begin
00193      */
00194      size_t next_element(void)
00195      {    size_t element = next_element_.value;
00196           if( element != end_ )
00197                next_element_ = data_[next_element_.next];
00198 
00199           return element;
00200      }
00201      // -----------------------------------------------------------------
00202      /*! Assign the empty set to one of the sets.
00203 
00204      \param target
00205      is the index of the set we are setting to the empty set.
00206 
00207      \par Checked Assertions
00208      \li target < n_set_
00209      */
00210      void clear(size_t target)
00211      {    CPPAD_ASSERT_UNKNOWN( target < n_set_ );
00212           data_[target].value = end_;
00213      }
00214      // -----------------------------------------------------------------
00215      /*! Assign one set equal to another set.
00216 
00217      \param this_target
00218      is the index (in this \c sparse_list object) of the set being assinged.
00219 
00220      \param other_source
00221      is the index (in the other \c sparse_list object) of the 
00222      that we are using as the value to assign to the target set.
00223 
00224      \param other
00225      is the other \c sparse_list object (which may be the same as this
00226      \c sparse_list object).
00227 
00228      \par Checked Assertions
00229      \li this_target  < n_set_
00230      \li other_index  < other.n_set_
00231      */
00232      void assignment(
00233           size_t               this_target  , 
00234           size_t               other_source , 
00235           const sparse_list&   other        )
00236      {    CPPAD_ASSERT_UNKNOWN( this_target  <   n_set_        );
00237           CPPAD_ASSERT_UNKNOWN( other_source <   other.n_set_  );
00238           CPPAD_ASSERT_UNKNOWN( end_        == other.end()   );
00239 
00240           size_t this_index        = this_target;
00241           size_t other_index       = other_source;
00242           size_t value             = other.data_[other_index].value;
00243           while( value != end_ )
00244           {    size_t next             = data_.extend(1);
00245                data_[this_index].value = value;
00246                data_[this_index].next  = next;
00247                this_index              = next;
00248                other_index             = other.data_[other_index].next;
00249                value                   = other.data_[other_index].value;
00250           }
00251           data_[this_index].value = end_;
00252      }
00253      // -----------------------------------------------------------------
00254      /*! Assign a set equal to the union of two other sets.
00255 
00256      \param this_target
00257      is the index (in this \c sparse_list object) of the set being assinged.
00258 
00259      \param this_left
00260      is the index (in this \c sparse_list object) of the 
00261      left operand for the union operation.
00262      It is OK for \a this_target and \a this_left to be the same value.
00263 
00264      \param other_right
00265      is the index (in the other \c sparse_list object) of the 
00266      right operand for the union operation.
00267      It is OK for \a this_target and \a other_right to be the same value.
00268 
00269      \param other
00270      is the other \c sparse_list object (which may be the same as this
00271      \c sparse_list object).
00272 
00273      \par Checked Assertions
00274      \li this_target <  n_set_
00275      \li this_left   <  n_set_
00276      \li other_right <  other.n_set_
00277      */
00278      void binary_union(
00279           size_t                  this_target  , 
00280           size_t                  this_left    , 
00281           size_t                  other_right  , 
00282           const sparse_list&      other        )
00283      {    
00284           CPPAD_ASSERT_UNKNOWN( this_target < n_set_         );
00285           CPPAD_ASSERT_UNKNOWN( this_left   < n_set_         );
00286           CPPAD_ASSERT_UNKNOWN( other_right < other.n_set_   );
00287           CPPAD_ASSERT_UNKNOWN( end_        == other.end()   );
00288 
00289           // merge left and right into target set
00290           size_t left_value  = data_[this_left].value;
00291           size_t left_next   = data_[this_left].next;
00292           size_t right_value = other.data_[other_right].value;
00293           size_t right_next  = other.data_[other_right].next;
00294           size_t current       = this_target;
00295           while( (left_value < end_) | (right_value < end_) )
00296           {    if( left_value == right_value )
00297                {    right_value = other.data_[right_next].value;
00298                     right_next  = other.data_[right_next].next;
00299                }
00300                size_t next         = data_.extend(1);
00301                data_[current].next = next;
00302                if( left_value < right_value )
00303                {    data_[current].value = left_value;
00304                     left_value           = data_[left_next].value;
00305                     left_next            = data_[left_next].next;
00306                }
00307                else
00308                {    data_[current].value = right_value;
00309                     right_value = other.data_[right_next].value;
00310                     right_next  = other.data_[right_next].next;
00311                }
00312                current = next;
00313           }
00314           data_[current].value = end_;
00315      }
00316      // -----------------------------------------------------------------
00317      /*! Sum over all sets of the number of elements
00318  
00319      /return
00320      The the total number of elements
00321      */
00322      size_t number_elements(void) const
00323      {    size_t i, count;
00324           count = 0;
00325           for(i = 0; i < n_set_; i++)
00326           {    size_t index = i;
00327                while( data_[index].value != end_ )
00328                {    count++;
00329                     index = data_[index].next;
00330                }
00331           }
00332           return count;
00333      }
00334      // -----------------------------------------------------------------
00335      /*! Fetch n_set for vector of sets object.
00336      
00337      \return
00338      Number of from sets for this vector of sets object
00339      */
00340      size_t n_set(void) const
00341      {    return n_set_; }
00342      // -----------------------------------------------------------------
00343      /*! Fetch end for this vector of sets object. 
00344      
00345      \return
00346      is the maximum element value plus one (the minimum element value is 0).
00347      */
00348      size_t end(void) const
00349      {    return end_; }
00350 };
00351 
00352 /*! 
00353 Copy a user vector of sets sparsity pattern to an internal sparse_list object.
00354 
00355 \tparam VectorSet
00356 is a simple vector with elements of type \c std::list<set>.
00357 
00358 \param internal
00359 The input value of sparisty does not matter.
00360 Upon return it contains the same sparsity pattern as \c user
00361 (or the transposed sparsity pattern).
00362 
00363 \param user
00364 sparsity pattern that we are placing \c internal.
00365 
00366 \param n_row
00367 number of rows in the sparsity pattern in \c user
00368 (range dimension).
00369 
00370 \param n_col
00371 number of columns in the sparsity pattern in \c user
00372 (domain dimension).
00373 
00374 \param transpose
00375 if true, the sparsity pattern in \c internal is the transpose
00376 of the one in \c user. 
00377 Otherwise it is the same sparsity pattern.
00378 */
00379 template<class VectorSet>
00380 void sparsity_user2internal(
00381      sparse_list&            internal  , 
00382      const VectorSet&        user      ,
00383      size_t                  n_row     ,
00384      size_t                  n_col     ,
00385      bool                    transpose )
00386 {    CPPAD_ASSERT_UNKNOWN( n_row == size_t(user.size()) );
00387 
00388      CPPAD_ASSERT_KNOWN(
00389           size_t( user.size() ) == n_row,
00390           "Size of this vector of lists sparsity pattern is not equal "
00391           "the range dimension for the corresponding function."
00392      );
00393 
00394      size_t i, j;
00395      std::set<size_t>::const_iterator itr;
00396 
00397      // transposed pattern case
00398      if( transpose )
00399      {    internal.resize(n_col, n_row);
00400           for(i = 0; i < n_row; i++)
00401           {    itr = user[i].begin();
00402                while(itr != user[i].end())
00403                {    j = *itr++;
00404                     CPPAD_ASSERT_UNKNOWN( j < n_col );
00405                     internal.add_element(j, i);
00406                }
00407           }
00408           return;
00409      }
00410 
00411      // same pattern case
00412      internal.resize(n_row, n_col);
00413      for(i = 0; i < n_row; i++)
00414      {    itr = user[i].begin();
00415           while(itr != user[i].end())
00416           {    j = *itr++;
00417                CPPAD_ASSERT_UNKNOWN( j < n_col );
00418                internal.add_element(i, j);
00419           }
00420      }
00421      return;
00422 }
00423 
00424 
00425 } // END_CPPAD_NAMESPACE
00426 # endif
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines