CppAD: A C++ Algorithmic Differentiation Package 20110419
sparse_pack.hpp
Go to the documentation of this file.
00001 // $Id$
00002 # ifndef CPPAD_SPARSE_PACK_INCLUDED
00003 # define CPPAD_SPARSE_PACK_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 <cppad/local/cppad_assert.hpp>
00016 
00017 CPPAD_BEGIN_NAMESPACE
00018 /*!
00019 \file sparse_pack.hpp
00020 Vector of sets of positive integers.
00021 */
00022 
00023 /*!
00024 Vector of sets of postivie integers, each set stored as a packed boolean array.
00025 */
00026 
00027 
00028 class sparse_pack {
00029 private:
00030         /// Type used to pack elements (should be the same as corresponding
00031         /// typedef in multiple_n_bit() in test_more/sparse_hacobian.cpp)
00032         typedef size_t Pack;
00033         /// Number of bits per Pack value
00034         static const size_t n_bit_ = std::numeric_limits<Pack>::digits;
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         /// Number of \c Pack values necessary to represent \c end_ bits.
00042         /// (set by constructor and resize).
00043         size_t n_pack_;
00044         /// Is the memory pointed to by \c data_ allocated by this object
00045         /// (set by contructor and resize)
00046         bool   allocated_;    
00047         /// Pointer to the beginning of data for all the sets.
00048         Pack*  data_;
00049         /// index for which we were retrieving next_element
00050         /// (use n_set_ if no such index exists).
00051         size_t next_index_;
00052         /// Next element to start search at 
00053         /// (use end_ for no such element exists; i.e., past end of the set).
00054         size_t next_element_;
00055 public:
00056         // -----------------------------------------------------------------
00057         /*! Default constructor (no sets)
00058         */
00059         sparse_pack(void) : 
00060         n_set_(0)                     , 
00061         end_(0)                       , 
00062         n_pack_(0)                    ,
00063         allocated_(false)             ,
00064         data_(CPPAD_NULL)             ,
00065         next_index_(0)                ,
00066         next_element_(0)
00067         { }
00068         // -----------------------------------------------------------------
00069         /*! Make use of copy constructor an error
00070  
00071         \param v
00072         vector that we are attempting to make a copy of.
00073         */
00074         sparse_pack(const sparse_pack& v)
00075         {       // Error: 
00076                 // Probably a sparse_pack argument has been passed by value
00077                 CPPAD_ASSERT_UNKNOWN(0); 
00078         }
00079         // -----------------------------------------------------------------
00080         /*! Destructor 
00081         */
00082         ~sparse_pack(void)
00083         {       if( allocated_ )
00084                 {       allocated_ = false;
00085                         CPPAD_TRACK_DEL_VEC( data_ ); 
00086                 }
00087         }
00088         // -----------------------------------------------------------------
00089         /*! Change number of sets, set end, and initialize all sets as empty
00090 
00091         Any memory currently allocated for this object is freed. If both
00092         \a n_set_in and \a end_in are non-zero new memory is allocated, otherwise
00093         no new memory is allocated for the object.
00094 
00095         \param n_set_in
00096         is the number of sets in this vector of sets.
00097 
00098         \param end_in
00099         is the maximum element plus one (the minimum element is 0).
00100         */
00101         void resize(size_t n_set_in, size_t end_in) 
00102         {       Pack zero(0);
00103                 if( allocated_ )
00104                 {       allocated_ = false;
00105                         CPPAD_TRACK_DEL_VEC(data_);
00106                 }
00107 
00108                 n_set_          = n_set_in;
00109                 end_            = end_in;
00110                 n_pack_         = ( 1 + (end_ - 1) / n_bit_ );
00111                 size_t i        = n_set_ * n_pack_;
00112 
00113                 if( i > 0 )
00114                 {       data_      = CPPAD_TRACK_NEW_VEC(i, data_);
00115                         allocated_ = true;
00116                         while(i--)
00117                                 data_[i] = zero;
00118                 }
00119 
00120                 // values that signify past end of list
00121                 next_index_   = n_set_;
00122                 next_element_ = end_;
00123         }
00124         // -----------------------------------------------------------------
00125         /*! Add one element to a set.
00126 
00127         \param index
00128         is the index for this set in the vector of sets.
00129 
00130         \param element
00131         is the element we are adding to the set.
00132 
00133         \par Checked Assertions
00134         \li index    < n_set_
00135         \li element  < end_
00136         */
00137         void add_element(size_t index, size_t element)
00138         {       static Pack one(1);
00139                 CPPAD_ASSERT_UNKNOWN( index   < n_set_ );
00140                 CPPAD_ASSERT_UNKNOWN( element < end_ );
00141                 size_t j  = element / n_bit_;
00142                 size_t k  = element - j * n_bit_;
00143                 Pack mask = one << k;
00144                 data_[ index * n_pack_ + j] |= mask;
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_ = 0; 
00161         }
00162         /*! Get the next element from the current retrieval set.
00163         
00164         \return
00165         is the next element in the set with index
00166         specified by the previous call to \c begin.
00167         If no such element exists, \c this->end() is returned.
00168         */
00169         size_t next_element(void)
00170         {       static Pack one(1);
00171                 CPPAD_ASSERT_UNKNOWN( next_index_ < n_set_ );
00172                 CPPAD_ASSERT_UNKNOWN( next_element_ <= end_ );
00173 
00174                 if( next_element_ == end_ )
00175                         return end_;
00176 
00177                 // initialize packed data index
00178                 size_t j  = next_element_ / n_bit_;
00179 
00180                 // initialize bit index
00181                 size_t k  = next_element_ - j * n_bit_;
00182 
00183                 // start search at this packed value
00184                 Pack check = data_[ next_index_ * n_pack_ + j ];
00185                 while( true )
00186                 {       // increment next element before checking this one
00187                         next_element_++;
00188                         // check if this element is in the set
00189                         if( check & (one << k) )
00190                                 return next_element_ - 1;
00191                         // check if no more elements in the set
00192                         if( next_element_ == end_ )
00193                                 return end_;
00194                         // increment bit index in Pack value so corresponds to 
00195                         // next element
00196                         k++;
00197                         CPPAD_ASSERT_UNKNOWN( k <= n_bit_ );
00198                         if( k == n_bit_ )
00199                         {       // get next packed value
00200                                 k     = 0;
00201                                 j++;
00202                                 CPPAD_ASSERT_UNKNOWN( j < n_pack_ );
00203                                 check = data_[ next_index_ * n_pack_ + j ];
00204                         }
00205                 }
00206                 // should never get here
00207                 CPPAD_ASSERT_UNKNOWN(false);
00208                 return end_;
00209         }
00210         // -----------------------------------------------------------------
00211         /*! Assign the empty set to one of the sets.
00212 
00213         \param target
00214         is the index of the set we are setting to the empty set.
00215 
00216         \par Checked Assertions
00217         \li target < n_set_
00218         */
00219         void clear(size_t target)
00220         {       // value with all its bits set to false
00221                 static Pack zero(0);
00222                 CPPAD_ASSERT_UNKNOWN( target < n_set_ );
00223                 Pack *t  = data_ + target * n_pack_;
00224 
00225                 size_t j = n_pack_;
00226                 while(j--)
00227                         *t++ = zero;
00228         }
00229         // -----------------------------------------------------------------
00230         /*! Assign one set equal to another set.
00231 
00232         \param this_target
00233         is the index (in this \c sparse_pack object) of the set being assinged.
00234 
00235         \param other_value
00236         is the index (in the other \c sparse_pack object) of the 
00237         that we are using as the value to assign to the target set.
00238 
00239         \param other
00240         is the other \c sparse_pack object (which may be the same as this
00241         \c sparse_pack object).
00242 
00243         \par Checked Assertions
00244         \li this_target  < n_set_
00245         \li other_value  < other.n_set_
00246         \li n_pack_     == other.n_pack_ 
00247         */
00248         void assignment(
00249                 size_t               this_target  , 
00250                 size_t               other_value  , 
00251                 const sparse_pack&   other        )
00252         {       CPPAD_ASSERT_UNKNOWN( this_target  <   n_set_        );
00253                 CPPAD_ASSERT_UNKNOWN( other_value  <   other.n_set_  );
00254                 CPPAD_ASSERT_UNKNOWN( n_pack_      ==  other.n_pack_ );
00255                 Pack *t  = data_       + this_target * n_pack_;
00256                 Pack *v  = other.data_ + other_value * n_pack_;
00257 
00258                 size_t j = n_pack_;
00259                 while(j--)
00260                         *t++ = *v++;
00261         }
00262 
00263         // -----------------------------------------------------------------
00264         /*! Assing a set equal to the union of two other sets.
00265 
00266         \param this_target
00267         is the index (in this \c sparse_pack object) of the set being assinged.
00268 
00269         \param this_left
00270         is the index (in this \c sparse_pack object) of the 
00271         left operand for the union operation.
00272         It is OK for \a this_target and \a this_left to be the same value.
00273 
00274         \param other_right
00275         is the index (in the other \c sparse_pack object) of the 
00276         right operand for the union operation.
00277         It is OK for \a this_target and \a other_right to be the same value.
00278 
00279         \param other
00280         is the other \c sparse_pack object (which may be the same as this
00281         \c sparse_pack object).
00282 
00283         \par Checked Assertions
00284         \li this_target <  n_set_
00285         \li this_left   <  n_set_
00286         \li other_right <  other.n_set_
00287         \li n_pack_     == other.n_pack_ 
00288         */
00289         void binary_union(
00290                 size_t                  this_target  , 
00291                 size_t                  this_left    , 
00292                 size_t                  other_right  , 
00293                 const sparse_pack&      other        )
00294         {       CPPAD_ASSERT_UNKNOWN( this_target < n_set_         );
00295                 CPPAD_ASSERT_UNKNOWN( this_left   < n_set_         );
00296                 CPPAD_ASSERT_UNKNOWN( other_right < other.n_set_   );
00297                 CPPAD_ASSERT_UNKNOWN( n_pack_    ==  other.n_pack_ );
00298 
00299                 Pack *t  = data_       + this_target * n_pack_;
00300                 Pack *l  = data_       + this_left   * n_pack_;
00301                 Pack *r  = other.data_ + other_right * n_pack_;
00302 
00303                 size_t j = n_pack_;
00304                 while(j--)
00305                         *t++ = (*l++ | *r++);
00306         }
00307         // -----------------------------------------------------------------
00308         /*! Amount of memory used by this vector of sets
00309  
00310         \return
00311         The amount of memory in units of type unsigned char memory.
00312         */
00313         size_t memory(void) const
00314         {       return n_set_ * n_pack_ * sizeof(Pack);
00315         }
00316         // -----------------------------------------------------------------
00317         /*! Fetch n_set for vector of sets object.
00318         
00319         \return
00320         Number of from sets for this vector of sets object
00321         */
00322         size_t n_set(void) const
00323         {       return n_set_; }
00324         // -----------------------------------------------------------------
00325         /*! Fetch end for this vector of sets object. 
00326         
00327         \return
00328         is the maximum element value plus one (the minimum element value is 0).
00329         */
00330         size_t end(void) const
00331         {       return end_; }
00332 };
00333 
00334 CPPAD_END_NAMESPACE
00335 # endif