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