Changeset 3989


Ignore:
Timestamp:
Dec 3, 2017 8:35:12 PM (21 months ago)
Author:
bradbell
Message:

merge to branch: trunk
from repository: https://github.com/coin-or/CppAD
start hash code: 43243b5306aebf5005bcab2acbe3a46c500db224
end hash code: 64a62c68cb15d7edb1dec17315b5043b177abd71

commit 64a62c68cb15d7edb1dec17315b5043b177abd71
Author: Brad Bell <bradbell@…>
Date: Sun Dec 3 08:15:28 2017 -0700

Add post_element and process_post to vector_of_sets concept.

commit 899186b45744814c0c181ae57c4de5afa1b85604
Author: Brad Bell <bradbell@…>
Date: Sun Dec 3 07:36:59 2017 -0700

sparse_list.hpp: use drop(i) for clearing out a set.

commit 6187af622944073da3c90b4b98113a83b00f03e8
Author: Brad Bell <bradbell@…>
Date: Sun Dec 3 06:36:36 2017 -0700

Change binary union of set and vector to be private.
sparse_list.hpp: start work on post operation.

commit 5f891a16ed55426bb777a6e53fa6a7a4fd5ac2e0
Author: Brad Bell <bradbell@…>
Date: Sun Dec 3 06:06:41 2017 -0700

Advance to cppad-20171203.
sparse_list.hpp: make data_[0] special marker at end of every list.

commit e28e55a2dfacef778e9561945074bcdbe2275bae
Author: Brad Bell <bradbell@…>
Date: Sat Dec 2 05:05:52 2017 -0700

sparse_list.hpp: make separte_copy easier to understand.

commit c17d006091085c23b7131448e3961ae01daea51c
Author: Brad Bell <bradbell@…>
Date: Sat Dec 2 04:48:42 2017 -0700

sparse_list.hpp: clean up check of data structure.

commit 52f9f0b306e4370a9060f53c492c9c200713c5ca
Author: Brad Bell <bradbell@…>
Date: Sat Dec 2 03:55:35 2017 -0700

Advance to cppad-20171202.

commit 08bc256bd8cb7d75693414b2c854805529c7b2ce
Author: Brad Bell <bradbell@…>
Date: Sat Dec 2 03:54:11 2017 -0700

Remove date from authors file.

commit f7203a857d74703f4732ea9a3c54d12e85286b55
Author: Brad Bell <bradbell@…>
Date: Sat Dec 2 03:45:30 2017 -0700

hold_reverse_memory.hpp: improve documentation.

Location:
trunk
Files:
12 edited

Legend:

Unmodified
Added
Removed
  • trunk/CMakeLists.txt

    r3987 r3989  
    2525#
    2626# cppad_version is used by set_version.sh to get the version number.
    27 SET(cppad_version      "20171201" )
     27SET(cppad_version      "20171203" )
    2828SET(cppad_url          "http://www.coin-or.org/CppAD" )
    2929SET(cppad_description  "Differentiation of C++ Algorithms" )
  • trunk/authors

    r3987 r3989  
    22             ===========================================
    33
    4 To date, 2017-12-01, Bradley M. Bell is the sole author of CppAD.
     4Bradley M. Bell is the sole author of CppAD.
    55While Bradley M. Bell worked for the University of Washington during
    66the development of CppAD, the following are also true:
  • trunk/bin/version.sh

    r3987 r3989  
    6868# -----------------------------------------------------------------------------
    6969# Make the version number in the relevant files is the same
    70 yyyy_mm_dd=`echo $version | sed \
    71         -e 's|\([0-9]\{4\}\)0000|\10101|' \
    72         -e 's|\(....\)\(..\)\(..\).*|\1-\2-\3|'`
    73 sed  \
    74         -e "s/, [0-9]\{4\}-[0-9]\{2\}-[0-9]\{2\} *,/, $yyyy_mm_dd,/" \
    75         -i.old authors
    76 #
    7770sed  \
    7871        -e "s/(\[cppad\], *\[[0-9]\{8\}[.0-9]*\] *,/([cppad], [$version],/"  \
     
    9992list="
    10093        $list
    101         authors
    10294        configure.ac
    10395        configure
  • trunk/configure

    r3987 r3989  
    11#! /bin/sh
    22# Guess values for system-dependent variables and create Makefiles.
    3 # Generated by GNU Autoconf 2.69 for cppad 20171201.
     3# Generated by GNU Autoconf 2.69 for cppad 20171203.
    44#
    55# Report bugs to <cppad@list.coin-or.org>.
     
    580580PACKAGE_NAME='cppad'
    581581PACKAGE_TARNAME='cppad'
    582 PACKAGE_VERSION='20171201'
    583 PACKAGE_STRING='cppad 20171201'
     582PACKAGE_VERSION='20171203'
     583PACKAGE_STRING='cppad 20171203'
    584584PACKAGE_BUGREPORT='cppad@list.coin-or.org'
    585585PACKAGE_URL=''
     
    13751375  # This message is too long to be a string in the A/UX 3.1 sh.
    13761376  cat <<_ACEOF
    1377 \`configure' configures cppad 20171201 to adapt to many kinds of systems.
     1377\`configure' configures cppad 20171203 to adapt to many kinds of systems.
    13781378
    13791379Usage: $0 [OPTION]... [VAR=VALUE]...
     
    14451445if test -n "$ac_init_help"; then
    14461446  case $ac_init_help in
    1447      short | recursive ) echo "Configuration of cppad 20171201:";;
     1447     short | recursive ) echo "Configuration of cppad 20171203:";;
    14481448   esac
    14491449  cat <<\_ACEOF
     
    15791579if $ac_init_version; then
    15801580  cat <<\_ACEOF
    1581 cppad configure 20171201
     1581cppad configure 20171203
    15821582generated by GNU Autoconf 2.69
    15831583
     
    19521952running configure, to aid debugging if configure makes a mistake.
    19531953
    1954 It was created by cppad $as_me 20171201, which was
     1954It was created by cppad $as_me 20171203, which was
    19551955generated by GNU Autoconf 2.69.  Invocation command line was
    19561956
     
    28422842# Define the identity of the package.
    28432843 PACKAGE='cppad'
    2844  VERSION='20171201'
     2844 VERSION='20171203'
    28452845
    28462846
     
    78257825# values after options handling.
    78267826ac_log="
    7827 This file was extended by cppad $as_me 20171201, which was
     7827This file was extended by cppad $as_me 20171203, which was
    78287828generated by GNU Autoconf 2.69.  Invocation command line was
    78297829
     
    78827882ac_cs_config="`$as_echo "$ac_configure_args" | sed 's/^ //; s/[\\""\`\$]/\\\\&/g'`"
    78837883ac_cs_version="\\
    7884 cppad config.status 20171201
     7884cppad config.status 20171203
    78857885configured by $0, generated by GNU Autoconf 2.69,
    78867886  with options \\"\$ac_cs_config\\"
  • trunk/configure.ac

    r3987 r3989  
    1212dnl Process this file with autoconf to produce a configure script.
    1313dnl   package   version              bug-report
    14 AC_INIT([cppad], [20171201], [cppad@list.coin-or.org])
     14AC_INIT([cppad], [20171203], [cppad@list.coin-or.org])
    1515AM_SILENT_RULES([yes])
    1616
  • trunk/cppad/core/hold_reverse_memory.hpp

    r3987 r3989  
    2828
    2929$head Purpose$$
    30 The $cref reverse$$ mode routines compute a derivatives for a number
     30The $cref reverse$$ mode routines compute a derivatives for a specified number
    3131of Taylor coefficients and every variable in the operation sequence.
    32 This routine allows one to decide if that memory should be held onto
    33 by $icode f$$ between calls these routines to avoid repeated memory allocation.
    34 Setting this value to true
     32This setting enables one to hold onto the memory in $icode f$$ used to store
     33these derivatives.
     34Holding onto this memory
    3535may speed up calculations and require more memory.
    3636
     
    5353        bool %b%
    5454%$$
    55 Future calls to $icode%f%.Forward%$$ will (will not) hold onto memory
    56 between calls to reverse mode routines
    57 depending on if $icode b$$ is true (false).
     55If $icode b$$ is true,
     56$icode f$$ will hold onto the memory used to store derivatives
     57of the Taylor coefficients.
     58If $icode b$$ is false,
     59the memory used to store these coefficients will be freed
     60and future calls will not hold onto this memory.
    5861
    5962$head Default$$
  • trunk/cppad/local/sparse_internal.hpp

    r3987 r3989  
    126126        const SizeVector& row( pattern_in.row() );
    127127        const SizeVector& col( pattern_in.col() );
    128         size_t nnz = pattern_in.nnz();
    129         pod_vector<size_t> internal_row;
    130         if( transpose )
    131         {       CPPAD_ASSERT_UNKNOWN( pattern_in.nr() == nc );
    132                 CPPAD_ASSERT_UNKNOWN( pattern_in.nc() == nr );
     128        size_t nnz = row.size();
     129        for(size_t k = 0; k < nnz; k++)
     130        {       size_t r = row[k];
     131                size_t c = col[k];
     132                if( transpose )
     133                        std::swap(r, c);
    133134                //
    134                 SizeVector col_major = pattern_in.col_major();
    135                 size_t k = 0;
    136                 while( k < nnz )
    137                 {       // this column of pattern_in
    138                         size_t c   = col[ col_major[k] ];
    139                         // length of the column
    140                         size_t len = 0;
    141                         internal_row.resize(0);
    142                         while( k + len < nnz && c == col[ col_major[k + len] ] )
    143                         {       internal_row.push_back( row[ col_major[k + len] ] );
    144                                 ++len;
    145                         }
    146                         size_t i_var = internal_index[c];
    147                         CPPAD_ASSERT_UNKNOWN( i_var < internal_pattern.n_set() );
    148                         bool ignore  = zero_empty && i_var == 0;
    149                         if( ! ignore )
    150                                 internal_pattern.binary_union(i_var, i_var, internal_row);
    151                         //
    152                         CPPAD_ASSERT_UNKNOWN( len > 0 );
    153                         k += len;
    154                 }
    155         }
    156         else
    157         {       CPPAD_ASSERT_UNKNOWN( pattern_in.nr() == nr );
    158                 CPPAD_ASSERT_UNKNOWN( pattern_in.nc() == nc );
    159                 //
    160                 SizeVector row_major = pattern_in.row_major();
    161                 size_t k = 0;
    162                 while( k < nnz )
    163                 {       // this row of pattern_in
    164                         size_t r   = row[ row_major[k] ];
    165                         // length of the row
    166                         size_t len = 0;
    167                         internal_row.resize(0);
    168                         while( k + len < nnz && r == row[ row_major[k + len] ] )
    169                         {       internal_row.push_back( col[ row_major[k + len] ] );
    170                                 ++len;
    171                         }
    172                         size_t i_var = internal_index[r];
    173                         CPPAD_ASSERT_UNKNOWN( i_var < internal_pattern.n_set() );
    174                         bool ignore  = zero_empty && i_var == 0;
    175                         if( ! ignore )
    176                                 internal_pattern.binary_union(i_var, i_var, internal_row);
    177                         //
    178                         CPPAD_ASSERT_UNKNOWN( len > 0 );
    179                         k += len;
    180                 }
     135                size_t i_var = internal_index[r];
     136                CPPAD_ASSERT_UNKNOWN( i_var < internal_pattern.n_set() );
     137                CPPAD_ASSERT_UNKNOWN( c < nc );
     138                bool ignore  = zero_empty && i_var == 0;
     139                if( ! ignore )
     140                        internal_pattern.add_element( internal_index[r], c );
    181141        }
    182142}
     
    191151{       size_t nr = internal_index.size();
    192152        size_t nc = internal_pattern.end();
    193         CPPAD_ASSERT_UNKNOWN( pattern_in.size() == nr * nc );
    194153# ifndef NDEBUG
    195154        CPPAD_ASSERT_UNKNOWN( pattern_in.size() == nr * nc );
     
    199158        }
    200159# endif
    201         pod_vector<size_t> internal_row;
    202         for(size_t i = 0; i < nr; i++)
    203         {       internal_row.resize(0);
    204                 for(size_t j = 0; j < nc; j++)
     160        for(size_t i = 0; i < nr; i++)
     161        {       for(size_t j = 0; j < nc; j++)
    205162                {       bool flag = pattern_in[i * nc + j];
    206163                        if( transpose )
    207164                                flag = pattern_in[j * nr + i];
    208165                        if( flag )
    209                                 internal_row.push_back(j);
    210                 }
    211                 size_t i_var = internal_index[i];
    212                 CPPAD_ASSERT_UNKNOWN( i_var < internal_pattern.n_set() );
    213                 bool ignore  = zero_empty && i_var == 0;
    214                 if( ! ignore )
    215                         internal_pattern.binary_union(i_var, i_var, internal_row);
     166                        {       size_t i_var = internal_index[i];
     167                                CPPAD_ASSERT_UNKNOWN( i_var < internal_pattern.n_set() );
     168                                CPPAD_ASSERT_UNKNOWN( j < nc );
     169                                bool ignore  = zero_empty && i_var == 0;
     170                                if( ! ignore )
     171                                        internal_pattern.add_element( i_var, j);
     172                        }
     173                }
    216174        }
    217175        return;
     
    227185{       size_t nr = internal_index.size();
    228186        size_t nc = internal_pattern.end();
    229         CPPAD_ASSERT_UNKNOWN( pattern_in.size() == nr * nc );
    230187# ifndef NDEBUG
    231188        CPPAD_ASSERT_UNKNOWN( pattern_in.size() == nr * nc );
     
    235192        }
    236193# endif
    237         pod_vector<size_t> internal_row;
    238         for(size_t i = 0; i < nr; i++)
    239         {       internal_row.resize(0);
    240                 for(size_t j = 0; j < nc; j++)
     194        for(size_t i = 0; i < nr; i++)
     195        {       for(size_t j = 0; j < nc; j++)
    241196                {       bool flag = pattern_in[i * nc + j];
    242197                        if( transpose )
    243198                                flag = pattern_in[j * nr + i];
    244199                        if( flag )
    245                                 internal_row.push_back(j);
    246                 }
    247                 size_t i_var = internal_index[i];
    248                 CPPAD_ASSERT_UNKNOWN( i_var < internal_pattern.n_set() );
    249                 bool ignore  = zero_empty && i_var == 0;
    250                 if( ! ignore )
    251                         internal_pattern.binary_union(i_var, i_var, internal_row);
     200                        {       size_t i_var = internal_index[i];
     201                                CPPAD_ASSERT_UNKNOWN( i_var < internal_pattern.n_set() );
     202                                CPPAD_ASSERT_UNKNOWN( j < nc );
     203                                bool ignore  = zero_empty && i_var == 0;
     204                                if( ! ignore )
     205                                        internal_pattern.add_element( i_var, j);
     206                        }
     207                }
    252208        }
    253209        return;
     
    261217        InternalSparsity&                  internal_pattern ,
    262218        const vector< std::set<size_t> >&  pattern_in       )
    263 {       // not worried about efficiency with vectors of standard sets
    264         // should use sparse_rc<SizeVector> for efficiency
    265         //
    266         size_t nr = internal_index.size();
    267         size_t nc = internal_pattern.end();
    268         //
    269         // number of non-zeros in pattern_in
    270         size_t nnz = 0;
    271         for(size_t i = 0; i < pattern_in.size(); ++i)
    272                 nnz += pattern_in[i].size();
    273         //
    274         // convert pattern_in to a sparse_rc
    275         size_t nr_in = pattern_in.size();
    276         size_t nc_in;
     219{       size_t nr = internal_index.size();
     220        size_t nc = internal_pattern.end();
     221# ifndef NDEBUG
     222        if( input_empty ) for(size_t i = 0; i < nr; i++)
     223        {       size_t i_var = internal_index[i];
     224                CPPAD_ASSERT_UNKNOWN( internal_pattern.number_elements(i_var) == 0 );
     225        }
     226# endif
    277227        if( transpose )
    278         {       CPPAD_ASSERT_UNKNOWN( pattern_in.size() == nc )
    279                 nc_in = nr;
     228        {       CPPAD_ASSERT_UNKNOWN( pattern_in.size() == nc );
     229                for(size_t j = 0; j < nc; j++)
     230                {       std::set<size_t>::const_iterator itr( pattern_in[j].begin() );
     231                        while( itr != pattern_in[j].end() )
     232                        {       size_t i = *itr;
     233                                size_t i_var = internal_index[i];
     234                                CPPAD_ASSERT_UNKNOWN( i_var < internal_pattern.n_set() );
     235                                CPPAD_ASSERT_UNKNOWN( j < nc );
     236                                bool ignore  = zero_empty && i_var == 0;
     237                                if( ! ignore )
     238                                        internal_pattern.add_element( i_var, j);
     239                                ++itr;
     240                        }
     241                }
    280242        }
    281243        else
    282         {       CPPAD_ASSERT_UNKNOWN( pattern_in.size() == nr )
    283                 nc_in = nc;
    284         }
    285         sparse_rc< vector<size_t> > pattern_rc(nr_in, nc_in, nnz);
    286         size_t k = 0;
    287         for(size_t i = 0; i < pattern_in.size(); ++i)
    288         {       std::set<size_t>::const_iterator itr( pattern_in[i].begin() );
    289                 while( itr != pattern_in[i].end() )
    290                 {       size_t j = *itr++;
    291                         pattern_rc.set(k++, i, j);
    292                 }
    293         }
    294         set_internal_sparsity(
    295                 zero_empty,
    296                 input_empty,
    297                 transpose,
    298                 internal_index,
    299                 internal_pattern,
    300                 pattern_rc
    301         );
    302         //
     244        {       CPPAD_ASSERT_UNKNOWN( pattern_in.size() == nr );
     245                for(size_t i = 0; i < nr; i++)
     246                {       std::set<size_t>::const_iterator itr( pattern_in[i].begin() );
     247                        while( itr != pattern_in[i].end() )
     248                        {       size_t j = *itr;
     249                                size_t i_var = internal_index[i];
     250                                CPPAD_ASSERT_UNKNOWN( i_var < internal_pattern.n_set() );
     251                                CPPAD_ASSERT_UNKNOWN( j < nc );
     252                                bool ignore  = zero_empty && i_var == 0;
     253                                if( ! ignore )
     254                                        internal_pattern.add_element( i_var, j);
     255                                ++itr;
     256                        }
     257                }
     258        }
    303259        return;
    304260}
  • trunk/cppad/local/sparse_list.hpp

    r3987 r3989  
    6969        \li
    7070        data_[ start_[i] ].value is the reference count for this list.
     71        This element is not in the list.
    7172
    7273        \li
    73         data_[ start_[i] ].next is not zero because there
    74         is at least one entry in this list.
     74        data_[ start_[i] ].next point the the first element in the list
     75        and is not zero because there is at least one entry in this list.
     76
     77        \li
     78        For all lists, the last pair in the list has data_ index zero,
     79        data_[0].value == end_ and data_[0].next = 0, and is not in the set.
    7580        */
    7681        pod_vector<size_t> start_;
     82
     83        /*!
     84        Vectors of elements that have not yet been added to corresponding sets.
     85
     86        \li
     87        If all the post_element calls for the i-th set have been added,
     88        post_[i] is zero. Otherwise the conditions below hold.
     89
     90        \li
     91        data_[ post_[i] ].value  is the first element that has been posted,
     92        but not yet added, to set i.
     93
     94        \li
     95        For all lists, the last pair in the list has data_ index zero,
     96        data_[0].value == end_ and data_[0].next = 0, and is not in the posted
     97        elements.
     98        */
     99        pod_vector<size_t> post_;
     100
     101        /*!
     102        A temporary vector used by member functions that keeps its capacity.
     103        */
     104        pod_vector<size_t> temporary_;
    77105
    78106        // -----------------------------------------------------------------
     
    88116        */
    89117        size_t reference_count(size_t i) const
    90         {       size_t ret = start_[i];
    91                 if( ret != 0 )
    92                 {       CPPAD_ASSERT_UNKNOWN( data_[ret].value != 0 );
    93                         CPPAD_ASSERT_UNKNOWN( data_[ret].next != 0 );
    94                         ret = data_[ret].value;
    95                 }
    96                 return ret;
    97         }
    98         // -----------------------------------------------------------------
    99         /*!
    100         Checks the number of data elements not used
     118        {       // start data index
     119                size_t start = start_[i];
     120                if( start == 0 )
     121                        return 0;
     122                //
     123                // reference count
     124                return data_[start].value;
     125        }
     126        // -----------------------------------------------------------------
     127        /*!
     128        drop a set and its postings.
     129
     130        \param i
     131        is the index of the set that will be dropped.
     132
     133        \par reference_count
     134        if the set is non-empty,
     135        the reference count data_[ start_[i] ] will be decremented.
     136
     137        \par start_
     138        The value start_[i] is set to zero.
     139
     140        \par post_
     141        the value post_[i] will be set to zero.
     142
     143        \return
     144        is the number of elements of data_ that will be lost when the set is
     145        dropped. This is non-zero when the initial reference count is one.
     146        */
     147        size_t drop(size_t i)
     148        {       // inialize counter
     149                size_t count = 0;
     150
     151                // count posted elements that will be dropped
     152                size_t next = post_[i];
     153                while( data_[next].value != end_ )
     154                {       ++count;
     155                        next = data_[next].next;
     156                }
     157
     158                // drop posted elements
     159                post_[i] = 0;
     160
     161                // check for empty set
     162                size_t start = start_[i];
     163                if( start == 0 )
     164                        return count;
     165
     166                // decrement reference counter
     167                CPPAD_ASSERT_UNKNOWN( data_[start].value == reference_count(i) );
     168                data_[start].value--;
     169
     170                // set this set to empty
     171                start_[i] = 0;
     172
     173                // nothing else lost unless new reference count is zero
     174                if( data_[start].value > 0 )
     175                        return count;
     176
     177                // count reference counter and elements in the set
     178                ++count;
     179                next = start;            // reference counter
     180                next = data_[next].next; // first element of the set
     181                while( data_[next].value != end_ )
     182                {       ++count;
     183                        next = data_[next].next;
     184                }
     185
     186                return count;
     187        }
     188        // -----------------------------------------------------------------
     189        /*!
     190        Checks data structure
    101191        (effectively const, but modifies and restores values)
    102192        */
    103         void check_data_not_used(void)
     193# ifdef NDEBUG
     194        void check_data_structure(void)
     195        {       return; }
     196# else
     197        void check_data_structure(void)
    104198        {       // number of sets
     199                CPPAD_ASSERT_UNKNOWN( post_.size() == start_.size() );
    105200                size_t n_set = start_.size();
    106                 //
     201                if( n_set == 0 )
     202                {       CPPAD_ASSERT_UNKNOWN( end_ == 0 );
     203                        CPPAD_ASSERT_UNKNOWN( data_not_used_ == 0 );
     204                        CPPAD_ASSERT_UNKNOWN( data_.size() == 0 );
     205                        CPPAD_ASSERT_UNKNOWN( start_.size() == 0 );
     206                        return;
     207                }
     208                // check data index zero
     209                CPPAD_ASSERT_UNKNOWN( data_[0].value == end_ );
     210                CPPAD_ASSERT_UNKNOWN( data_[0].next  == 0  );
     211                // -----------------------------------------------------------
    107212                // save the reference counters
    108213                pod_vector<size_t> ref_count(n_set);
    109214                for(size_t i = 0; i < n_set; i++)
    110215                        ref_count[i] = reference_count(i);
    111 
    112                 // count the number of entries in data_ that are used
    113                 size_t data_used = 0;
     216                // -----------------------------------------------------------
     217                // count the number of entries in data_ that are used by sets
     218                // (data_[0] is used by all the sets)
     219                size_t data_used_by_sets = 1;
    114220                for(size_t i = 0; i < n_set; i++)
    115221                {       size_t start = start_[i];
    116                         if( start != 0 )
    117                         {       // decrement the reference counter
    118                                 CPPAD_ASSERT_UNKNOWN( data_[start].value > 0 );
     222                        if( start > 0 )
     223                        {       // check structure for this non-empty set
     224                                size_t reference_count = data_[start].value;
     225                                size_t next            = data_[start].next;
     226                                CPPAD_ASSERT_UNKNOWN( reference_count > 0 );
     227                                CPPAD_ASSERT_UNKNOWN( next != 0 );
     228                                CPPAD_ASSERT_UNKNOWN( data_[next].value < end_ );
     229                                //
     230                                // decrement the reference counter
    119231                                data_[start].value--;
    120232                                //
    121233                                // count the entries when find last reference
    122234                                if( data_[start].value == 0 )
    123                                 {       // restore reference count
     235                                {
     236                                        // restore reference count
    124237                                        data_[start].value = ref_count[i];
    125238
    126239                                        // number of data entries used for this set
    127                                         data_used += number_elements(i) + 1;
     240                                        data_used_by_sets += number_elements(i) + 1;
     241                                        /*
     242                                        number of elements checks that value < end_
     243                                        each pair in the list except for the start pair
     244                                        and the pair with index zero.
     245                                        */
    128246                                }
    129247                        }
    130248                }
     249                // ------------------------------------------------------------------
     250                // count the number of entries in data_ that are used by posts
     251                size_t data_used_by_posts = 0;
     252                for(size_t i = 0; i < n_set; i++)
     253                {       size_t post = post_[i];
     254                        if( post > 0 )
     255                        {       size_t value = data_[post].value;
     256                                size_t next  = data_[post].next;
     257                                CPPAD_ASSERT_UNKNOWN( value < end_ );
     258                                //
     259                                while( value < end_ )
     260                                {       ++data_used_by_posts;
     261                                        value = data_[next].value;
     262                                        next  = data_[next].next;
     263                                }
     264                        }
     265                }
     266                // ------------------------------------------------------------------
     267                size_t data_used = data_used_by_sets + data_used_by_posts;
    131268                CPPAD_ASSERT_UNKNOWN(
    132269                        data_used + data_not_used_ == data_.size()
     
    134271                return;
    135272        }
     273# endif
    136274        // -----------------------------------------------------------------
    137275        /*!
     
    196334                        else
    197335                        {       next_one = data_[next_one].next;
    198                                 if( next_one == 0 )
    199                                         value_one = end_;
    200                                 else
    201                                         value_one = data_[next_one].value;
     336                                value_one = data_[next_one].value;
    202337                        }
    203338                        if( value_two > value_union )
     
    205340                        else
    206341                        {       next_two = other.data_[next_two].next;
    207                                 if( next_two == 0 )
    208                                         value_two = end_;
    209                                 else
    210                                         value_two = other.data_[next_two].value;
     342                                value_two = other.data_[next_two].value;
    211343                        }
    212344                        value_union = std::min(value_one, value_two);
     
    243375        {       if( data_not_used_ < data_.size() / 2 +  100)
    244376                        return;
    245 # ifndef NDEBUG
    246                 check_data_not_used();
    247 # endif
     377                check_data_structure();
    248378                //
    249379                // number of sets including empty ones
     
    251381                //
    252382                // copy the sets to a temporary version of data_
    253                 pod_vector<pair_size_t> data_tmp(1); // data_tmp[0] will not be used
     383                pod_vector<pair_size_t> data_tmp(1);
     384                data_tmp[0].value = end_;
     385                data_tmp[0].next  = 0;
    254386                //
    255387                pod_vector<size_t> start_tmp(n_set);
     
    290422                                                }
    291423                                        }
     424                                        //
    292425                                        // store the starting address here
    293426                                        data_[start].value = tmp_start;
     427                                        //
    294428                                        // flag that indicates this link list already copied
    295429                                        data_[start].next = 0;
     
    302436                data_.swap(data_tmp);
    303437
    304                 // all of the elements, except the first, are used
    305                 data_not_used_ = 1;
     438                // all of the elements are used, including data_[0] which is used
     439                // by all the lists.
     440                data_not_used_ = 0;
    306441        }
    307442        // -----------------------------------------------------------------
     
    321456                size_t value = data_[next].value;
    322457                //
    323                 size_t copy_cur       = data_.extend(2);
    324                 size_t copy_next      = copy_cur + 1;
    325                 start_[i]             = copy_cur;
    326                 data_[copy_cur].value = 1;
    327                 data_[copy_cur].next  = copy_next;
    328                 copy_cur              = copy_next;
    329                 //
    330                 CPPAD_ASSERT_UNKNOWN( value < end_ );
    331                 while( value < end_ )
    332                 {       data_[copy_cur].value   = value;
    333                         //
    334                         next       = data_[next].next;
     458                // new version of list
     459                size_t start_new   = data_.extend(2);
     460                size_t next_new    = start_new + 1;
     461                //
     462                // reference counter for new version of list
     463                data_[start_new].value = 1;
     464                data_[start_new].next  = next_new;
     465                //
     466                CPPAD_ASSERT_UNKNOWN( next != 0 )
     467                while( next != 0 )
     468                {       data_[next_new].value  = value;
     469                        next                   = data_[next].next;
    335470                        if( next == 0 )
    336                         {       value = end_;
    337                                 data_[copy_cur].next = 0;
    338                         }
     471                                data_[next_new].next = 0;
    339472                        else
    340                         {       value  = data_[next].value;
    341                                 data_[copy_cur].next = data_.extend(1);
    342                         }
    343                 }
    344                 CPPAD_ASSERT_UNKNOWN( next == 0 );
     473                        {       value                  = data_[next].value;
     474                                data_[next_new].next  = data_.extend(1);
     475                                next_new               = data_[next_new].next;
     476                        }
     477                }
    345478                //
    346479                // decrement reference count
     
    348481                data_[start].value--;
    349482                //
     483                // starting point for new list
     484                start_[i] = start_new;
     485                //
     486                return;
     487        }
     488        // -----------------------------------------------------------------
     489        /*!
     490        Assign a set equal to the union of a set and a vector;
     491
     492        \param target
     493        is the index in this sparse_list object of the set being assinged.
     494
     495        \param left
     496        is the index in this sparse_list object of the
     497        left operand for the union operation.
     498        It is OK for target and left to be the same value.
     499
     500        \param right
     501        is a vector of size_t, sorted in accending order.
     502        right operand for the union operation.
     503        Elements can be repeated in right, but are not be repeated in the
     504        resulting set.
     505        All of the elements must have value less than end();
     506        */
     507        void binary_union(
     508                size_t                    target ,
     509                size_t                    left   ,
     510                const pod_vector<size_t>& right  )
     511        {       CPPAD_ASSERT_UNKNOWN( post_[left] == 0 );
     512                //
     513                CPPAD_ASSERT_UNKNOWN( target < start_.size() );
     514                CPPAD_ASSERT_UNKNOWN( left   < start_.size() );
     515
     516                // get start indices before drop modifies modify start_ in case target
     517                // and left are the same.
     518                size_t start_left   = start_[left];
     519
     520                // -------------------------------------------------------------------
     521                // Check if right is a subset of left so that we used reference count
     522                // and not copies of identical sets.
     523                //
     524                // initialize index for left and right sets
     525                size_t current_left  = start_left;
     526                size_t current_right = 0;
     527                //
     528                // initialize value_left
     529                size_t value_left  = end_;
     530                if( current_left > 0 )
     531                {       // advance from reference counter to data
     532                        current_left = data_[current_left].next;
     533                        CPPAD_ASSERT_UNKNOWN( current_left != 0 )
     534                        //
     535                        value_left = data_[current_left].value;
     536                        CPPAD_ASSERT_UNKNOWN( value_left < end_);
     537                }
     538                //
     539                // initialize value_right
     540                size_t value_right = end_;
     541                if( right.size() > 0 )
     542                        value_right = right[current_right];
     543                //
     544                bool subset = true;
     545                while( subset & (value_right < end_) )
     546                {       while( value_left < value_right )
     547                        {       // advance left
     548                                current_left = data_[current_left].next;
     549                                value_left = data_[current_left].value;
     550                        }
     551                        if( value_right < value_left )
     552                                subset = false;
     553                        else
     554                        {       // advance right
     555                                ++current_right;
     556                                if( current_right == right.size() )
     557                                        value_right = end_;
     558                                else
     559                                        value_right = right[current_right];
     560                        }
     561                }
     562                //
     563                if( subset )
     564                {       // target = left will use reference count for identical sets
     565                        assignment(target, left, *this);
     566                        return;
     567                }
     568
     569                // -------------------------------------------------------------------
     570
     571                // number of elements that will be deleted by removing old version
     572                // of target
     573                size_t number_delete = drop(target);
     574
     575                // start new version of target
     576                size_t start        = data_.extend(1);
     577                start_[target]      = start;
     578                data_[start].value  = 1; // reference count
     579                //
     580                // previous index for new set
     581                size_t previous_target = start;
     582                //
     583                // initialize index for left and right sets
     584                current_left  = start_left;
     585                current_right = 0;
     586                //
     587                // initialize value_left
     588                value_left  = end_;
     589                if( current_left > 0 )
     590                {       // advance from reference counter to data
     591                        current_left = data_[current_left].next;
     592                        CPPAD_ASSERT_UNKNOWN( current_left != 0 )
     593                        //
     594                        value_left = data_[current_left].value;
     595                        CPPAD_ASSERT_UNKNOWN( value_left < end_);
     596                }
     597                //
     598                // initialize value_right
     599                value_right = end_;
     600                if( right.size() > 0 )
     601                        value_right = right[current_right];
     602                //
     603                // merge
     604                while( (value_left < end_) | (value_right < end_) )
     605                {       if( value_left == value_right)
     606                        {       // advance left so left and right are no longer equal
     607                                current_left = data_[current_left].next;
     608                                value_left   = data_[current_left].value;
     609                                CPPAD_ASSERT_UNKNOWN( value_right < value_left );
     610                        }
     611                        // place to put new element
     612                        size_t current_target       = data_.extend(1);
     613                        data_[previous_target].next = current_target;
     614                        //
     615                        if( value_left < value_right )
     616                        {       // value_left case
     617                                CPPAD_ASSERT_UNKNOWN( value_left < end_ );
     618                                data_[current_target].value = value_left;
     619                                //
     620                                // advance left
     621                                current_left = data_[current_left].next;
     622                                value_left   = data_[current_left].value;
     623                        }
     624                        else
     625                        {       CPPAD_ASSERT_UNKNOWN( value_right < value_left )
     626                                // value_right case
     627                                CPPAD_ASSERT_UNKNOWN( value_right < end_);
     628                                data_[current_target].value = value_right;
     629                                //
     630                                // advance right (skip values equal to this one)
     631                                size_t previous_value = value_right;
     632                                while( value_right == previous_value )
     633                                {       ++current_right;
     634                                        if( current_right == right.size() )
     635                                                value_right = end_;
     636                                        else
     637                                        {       value_right = right[current_right];
     638                                                CPPAD_ASSERT_UNKNOWN( value_right < end_ );
     639                                        }
     640                                }
     641                        }
     642                        // done setting current target value
     643                        previous_target  = current_target;
     644                }
     645                // make end of target list
     646                data_[previous_target].next = 0;
     647
     648                // adjust data_not_used_
     649                data_not_used_ += number_delete;
     650                collect_garbage();
    350651        }
    351652// ===========================================================================
     
    361662        data_not_used_(0)  ,
    362663        data_(0)           ,
    363         start_(0)
     664        start_(0)          ,
     665        post_(0)
    364666        { }
    365667        // -----------------------------------------------------------------
    366668        /// Destructor
    367669        ~sparse_list(void)
    368         {
    369 # ifndef NDEBUG
    370                 check_data_not_used();
    371 # endif
     670        {       check_data_structure();
    372671        }
    373672        // -----------------------------------------------------------------
     
    396695        {       end_           = other.end_;
    397696                data_not_used_ = other.data_not_used_;
     697                data_          = other.data_;
    398698                start_         = other.start_;
    399                 data_          = other.data_;
     699                post_          = other.post_;
    400700        }
    401701        // -----------------------------------------------------------------
     
    417717        */
    418718        void resize(size_t n_set, size_t end)
    419         {
    420 # ifndef NDEBUG
    421                 check_data_not_used();
    422 # endif
     719        {       check_data_structure();
     720
    423721                if( n_set == 0 )
    424722                {       CPPAD_ASSERT_UNKNOWN( end == 0 );
     
    428726                        data_.clear();
    429727                        start_.clear();
     728                        post_.clear();
    430729                        data_not_used_  = 0;
    431730                        end_            = 0;
     
    436735                //
    437736                start_.resize(n_set);
     737                post_.resize(n_set);
     738                //
    438739                for(size_t i = 0; i < n_set; i++)
    439                         start_[i] = 0;
    440                 //
    441                 data_.resize(1); // first element is not used
    442                 data_not_used_  = 1;
     740                {       start_[i] = 0;
     741                        post_[i]  = 0;
     742                }
     743                //
     744                // last element, marks the end for all lists
     745                data_.resize(1);
     746                data_[0].value  = end_;
     747                data_[0].next   = 0;
     748                //
     749                data_not_used_  = 0;
    443750        }
    444751        // -----------------------------------------------------------------
     
    448755        \param i
    449756        is the index of the set we are counting the elements of.
     757
     758        \par
     759        number of elements checks that value < end_ for each element of the set.
    450760        */
    451761        size_t number_elements(size_t i) const
    452         {       CPPAD_ASSERT_UNKNOWN(i < start_.size() );
    453 
     762        {       CPPAD_ASSERT_UNKNOWN( post_[i] == 0 );
     763
     764                // check if the set is empty
     765                size_t start   = start_[i];
     766                if( start == 0 )
     767                        return 0;
     768
     769                // initialize counter
    454770                size_t count   = 0;
    455                 size_t start   = start_[i];
    456 
    457                 // check if the set is empty
    458                 if( start == 0 )
    459                         return count;
    460                 CPPAD_ASSERT_UNKNOWN( reference_count(i) > 0 );
    461771
    462772                // advance to the first element in the set
     
    470780                return count;
    471781        }
     782        /*!
     783        Post an element for delayed addition to a set.
     784
     785        \param i
     786        is the index for this set in the vector of sets.
     787
     788        \param element
     789        is the value of the element that we are posting.
     790        The same element may be posted multiple times.
     791
     792        \par
     793        It is faster to post multiple elements to set i and then call
     794        process_post(i) then to add each element individually.
     795        It is an error to call any member function,
     796        that depends on the value of set i,
     797        before processing the posts to set i.
     798        */
     799        void post_element(size_t i, size_t element)
     800        {       CPPAD_ASSERT_UNKNOWN( i < start_.size() );
     801                CPPAD_ASSERT_UNKNOWN( element < end_ );
     802
     803                // put element at the front of this list
     804                size_t next         = post_[i];
     805                size_t post         = data_.extend(1);
     806                post_[i]            = post;
     807                data_[post].value   = element;
     808                data_[post].next    = next;
     809
     810                return;
     811        }
     812        // -----------------------------------------------------------------
     813        /*!
     814        process post entries for a specific set.
     815
     816        \param i
     817        index of the set for which we are processing the post entries.
     818
     819        \par post_
     820        Upon call, post_[i] is location in data_ of the elements that get
     821        added to the i-th set.  Upon return, post_[i] is zero.
     822        */
     823        void process_post(size_t i)
     824        {       // post
     825                size_t post = post_[i];
     826                //
     827                // done with this posting
     828                post_[i] = 0;
     829                //
     830                // check if there are no elements to process
     831                if( post == 0 )
     832                        return;
     833                //
     834                // check if there is only one element to process
     835                size_t value = data_[post].value;
     836                size_t next  = data_[post].next;
     837                if( next == 0 )
     838                {       add_element(i, value);
     839                        // only lost the one posting element
     840                        ++data_not_used_;
     841                        collect_garbage();
     842                        return;
     843                }
     844                //
     845                // copy the elements that need to be processed into temporary
     846                temporary_.resize(0);
     847                while( value != end_ )
     848                {       temporary_.push_back(value);
     849                        value = data_[next].value;
     850                        next  = data_[next].next;
     851                }
     852                //
     853                // sort temporary_
     854                size_t number_post = temporary_.size();
     855                CPPAD_ASSERT_UNKNOWN( number_post > 1 );
     856                std::sort( temporary_.data(), temporary_.data() + number_post);
     857                //
     858                // add the elements to the set
     859                binary_union(i, i, temporary_);
     860                //
     861                // adjust data not used_
     862                data_not_used_ += number_post;
     863                collect_garbage();
     864                //
     865                return;
     866        }
    472867        // -----------------------------------------------------------------
    473868        /*!
     
    491886                size_t start = start_[i];
    492887                if( start == 0 )
    493                 {       start         = data_.extend(2);
    494                         start_[i]     = start;
    495                         size_t next   = start + 1;
     888                {       start              = data_.extend(2);
     889                        start_[i]          = start;
    496890                        data_[start].value = 1; // reference count
     891                        //
     892                        size_t next        = start + 1;
    497893                        data_[start].next  = next;
     894                        //
    498895                        data_[next].value  = element;
    499896                        data_[next].next   = 0;
     
    505902                // start of set with this index (after separate_copy)
    506903                size_t previous = start_[i];
     904                //
    507905                // check reference count for this list
    508906                CPPAD_ASSERT_UNKNOWN( data_[previous].value == 1 );
    509                 // first entry in this list (which starts out non-empty)
     907                //
     908                // first entry in this set
    510909                size_t next     = data_[previous].next;
    511910                size_t value    = data_[next].value;
    512                 CPPAD_ASSERT_UNKNOWN( value < end_ );
     911                //
    513912                // locate place to insert this element
    514913                while( value < element )
    515914                {       previous = next;
    516915                        next     = data_[next].next;
    517                         if( next == 0 )
    518                                 value = end_;
    519                         else
    520                                 value = data_[next].value;
     916                        value = data_[next].value;
    521917                }
    522918                CPPAD_ASSERT_UNKNOWN( element < value )
     
    538934        */
    539935        bool is_element(size_t i, size_t element) const
    540         {       CPPAD_ASSERT_UNKNOWN( i   < start_.size() );
     936        {       CPPAD_ASSERT_UNKNOWN( post_[i] == 0 );
    541937                CPPAD_ASSERT_UNKNOWN( element < end_ );
    542938                //
     
    544940                if( start == 0 )
    545941                        return false;
    546                 //
    547                 CPPAD_ASSERT_UNKNOWN( data_[start].value > 0 );
    548                 CPPAD_ASSERT_UNKNOWN( data_[start].next > 0 );
    549942                //
    550943                size_t next  = data_[start].next;
     
    552945                while( value < element )
    553946                {       next  = data_[next].next;
    554                         if( next == 0 )
    555                                 value = end_;
    556                         else
    557                                 value = data_[next].value;
     947                        value = data_[next].value;
    558948                }
    559949                return element == value;
     
    573963        {       CPPAD_ASSERT_UNKNOWN( target < start_.size() );
    574964
    575                 // number of references to this set
    576                 size_t ref_count = reference_count(target);
    577 
    578                 // case by reference count
    579                 if( ref_count > 1  )
    580                 {       // just remove this reference
    581                         size_t start   = start_[target];
    582                         start_[target] = 0;
    583                         CPPAD_ASSERT_UNKNOWN( data_[start].value == ref_count );
    584                         data_[start].value--;
    585                 }
    586                 else if( ref_count == 1 )
    587                 {
    588                         // number of data_ elements that will be lost by this operation
    589                         size_t number_delete = number_elements(target) + 1;
    590 
    591                         // delete the elements from the set
    592                         start_[target] = 0;
    593 
    594                         // adjust data_not_used_
    595                         data_not_used_ += number_delete;
    596                         collect_garbage();
    597                 }
    598                 //
     965                // drop t he set and postings
     966                size_t number_delete = drop(target);
     967
     968                // adjust data_not_used_
     969                data_not_used_ += number_delete;
     970                collect_garbage();
    599971        }
    600972        // -----------------------------------------------------------------
     
    620992                size_t               other_source ,
    621993                const sparse_list&   other        )
    622         {       CPPAD_ASSERT_UNKNOWN( this_target  <   start_.size()        );
     994        {       CPPAD_ASSERT_UNKNOWN( other.post_[ other_source ] == 0 );
     995                //
     996                CPPAD_ASSERT_UNKNOWN( this_target  <   start_.size()        );
    623997                CPPAD_ASSERT_UNKNOWN( other_source <   other.start_.size()  );
    624998                CPPAD_ASSERT_UNKNOWN( end_        == other.end_   );
     
    6291003
    6301004                // number of list elements that will be deleted by this operation
    631                 size_t number_delete = 0;
    632                 size_t ref_count     = reference_count(this_target);
    633                 size_t start         = start_[this_target];
    634                 if( ref_count == 1 )
    635                         number_delete = number_elements(this_target) + 1;
    636                 else if (ref_count > 1 )
    637                 {       // decrement reference counter
    638                         CPPAD_ASSERT_UNKNOWN( data_[start].value > 1 )
    639                         data_[start].value--;
    640                 }
     1005                size_t number_delete = drop(this_target);
    6411006
    6421007                // If this and other are the same, use another reference to same list
     
    6821047        // -----------------------------------------------------------------
    6831048        /*!
    684         Assign a set equal to the union of a set and a vector;
    685 
    686         \param target
    687         is the index in this sparse_list object of the set being assinged.
    688 
    689         \param left
    690         is the index in this sparse_list object of the
    691         left operand for the union operation.
    692         It is OK for target and left to be the same value.
    693 
    694         \param right
    695         is a vector of size_t, sorted in accending order.
    696         right operand for the union operation.
    697         Elements can be repeated in right, but are not be repeated in the
    698         resulting set.
    699         All of the elements must have value less than end();
    700         */
    701         void binary_union(
    702                 size_t                    target ,
    703                 size_t                    left   ,
    704                 const pod_vector<size_t>& right  )
    705         {
    706                 CPPAD_ASSERT_UNKNOWN( target < start_.size() );
    707                 CPPAD_ASSERT_UNKNOWN( left   < start_.size() );
    708 
    709                 // get start indices before we modify start_ in case target
    710                 // and left are the same.
    711                 size_t start_target = start_[target];
    712                 size_t start_left   = start_[left];
    713 
    714                 // -------------------------------------------------------------------
    715                 // Check if right is a subset of left so that we used reference count
    716                 // and not copies of identical sets.
    717                 //
    718                 // initialize index for left and right sets
    719                 size_t current_left  = start_left;
    720                 size_t current_right = 0;
    721                 //
    722                 // initialize value_left
    723                 size_t value_left  = end_;
    724                 if( current_left > 0 )
    725                 {       // advance from reference counter to data
    726                         current_left = data_[current_left].next;
    727                         CPPAD_ASSERT_UNKNOWN( current_left != 0 )
    728                         //
    729                         value_left = data_[current_left].value;
    730                         CPPAD_ASSERT_UNKNOWN( value_left < end_);
    731                 }
    732                 //
    733                 // initialize value_right
    734                 size_t value_right = end_;
    735                 if( right.size() > 0 )
    736                         value_right = right[current_right];
    737                 //
    738                 bool subset = true;
    739                 while( subset & (value_right < end_) )
    740                 {       while( value_left < value_right )
    741                         {       // advance left
    742                                 current_left = data_[current_left].next;
    743                                 if( current_left == 0 )
    744                                         value_left = end_;
    745                                 else
    746                                         value_left = data_[current_left].value;
    747                         }
    748                         if( value_right < value_left )
    749                                 subset = false;
    750                         else
    751                         {       // advance right
    752                                 ++current_right;
    753                                 if( current_right == right.size() )
    754                                         value_right = end_;
    755                                 else
    756                                         value_right = right[current_right];
    757                         }
    758                 }
    759                 //
    760                 if( subset )
    761                 {       // target = left will use reference count for identical sets
    762                         assignment(target, left, *this);
    763                         return;
    764                 }
    765 
    766                 // -------------------------------------------------------------------
    767                 // number of elements that will be deleted by removing old version
    768                 // of target
    769                 size_t number_delete = 0;
    770                 size_t ref_count     = reference_count(target);
    771                 //
    772                 if( ref_count == 1 )
    773                         number_delete = number_elements(target) + 1;
    774                 else if (ref_count > 1 )
    775                 {       // decrement reference counter
    776                         CPPAD_ASSERT_UNKNOWN( data_[start_target].value > 1 )
    777                         data_[start_target].value--;
    778                 }
    779                 //
    780                 // start new version of target
    781                 size_t start        = data_.extend(1);
    782                 start_[target]      = start;
    783                 data_[start].value  = 1; // reference count
    784                 //
    785                 // previous index for new set
    786                 size_t previous_target = start;
    787                 //
    788                 // initialize index for left and right sets
    789                 current_left  = start_left;
    790                 current_right = 0;
    791                 //
    792                 // initialize value_left
    793                 value_left  = end_;
    794                 if( current_left > 0 )
    795                 {       // advance from reference counter to data
    796                         current_left = data_[current_left].next;
    797                         CPPAD_ASSERT_UNKNOWN( current_left != 0 )
    798                         //
    799                         value_left = data_[current_left].value;
    800                         CPPAD_ASSERT_UNKNOWN( value_left < end_);
    801                 }
    802                 //
    803                 // initialize value_right
    804                 value_right = end_;
    805                 if( right.size() > 0 )
    806                         value_right = right[current_right];
    807                 //
    808                 // merge
    809                 while( (value_left < end_) | (value_right < end_) )
    810                 {       if( value_left == value_right)
    811                         {       // advance left so left and right are no longer equal
    812                                 current_left = data_[current_left].next;
    813                                 if( current_left == 0 )
    814                                         value_left = end_;
    815                                 else
    816                                         value_left = data_[current_left].value;
    817                                 CPPAD_ASSERT_UNKNOWN( value_right < value_left );
    818                         }
    819                         // place to put new element
    820                         size_t current_target       = data_.extend(1);
    821                         data_[previous_target].next = current_target;
    822                         //
    823                         if( value_left < value_right )
    824                         {       // value_left case
    825                                 CPPAD_ASSERT_UNKNOWN( value_left < end_ );
    826                                 data_[current_target].value = value_left;
    827                                 //
    828                                 // advance left
    829                                 current_left = data_[current_left].next;
    830                                 if( current_left == 0 )
    831                                         value_left = end_;
    832                                 else
    833                                         value_left = data_[current_left].value;
    834                         }
    835                         else
    836                         {       CPPAD_ASSERT_UNKNOWN( value_right < value_left )
    837                                 // value_right case
    838                                 CPPAD_ASSERT_UNKNOWN( value_right < end_);
    839                                 data_[current_target].value = value_right;
    840                                 //
    841                                 // advance right (skip values equal to this one)
    842                                 size_t previous_value = value_right;
    843                                 while( value_right == previous_value )
    844                                 {       ++current_right;
    845                                         if( current_right == right.size() )
    846                                                 value_right = end_;
    847                                         else
    848                                         {       value_right = right[current_right];
    849                                                 CPPAD_ASSERT_UNKNOWN( value_right < end_ );
    850                                         }
    851                                 }
    852                         }
    853                         // done setting current target value
    854                         previous_target  = current_target;
    855                 }
    856                 // make end of target list
    857                 data_[previous_target].next = 0;
    858 
    859                 // adjust data_not_used_
    860                 data_not_used_ += number_delete;
    861                 collect_garbage();
    862         }
    863         // -----------------------------------------------------------------
    864         /*!
    8651049        Assign a set equal to the union of two other sets.
    8661050
     
    8871071                size_t                  other_right  ,
    8881072                const sparse_list&      other        )
    889         {
     1073        {       CPPAD_ASSERT_UNKNOWN( post_[this_left] == 0 );
     1074                CPPAD_ASSERT_UNKNOWN( other.post_[ other_right ] == 0 );
     1075                //
    8901076                CPPAD_ASSERT_UNKNOWN( this_target < start_.size()         );
    8911077                CPPAD_ASSERT_UNKNOWN( this_left   < start_.size()         );
     
    9121098                // must get all the start indices before modify start_this
    9131099                // (incase start_this is the same as start_left or start_right)
    914                 size_t start_target  = start_[this_target];
    9151100                size_t start_left    = start_[this_left];
    9161101                size_t start_right   = other.start_[other_right];
    9171102
    918 
    9191103                // number of list elements that will be deleted by this operation
    920                 size_t number_delete = 0;
    921                 size_t ref_count     = reference_count(this_target);
    922                 if( ref_count == 1 )
    923                         number_delete = number_elements(this_target) + 1;
    924                 else if (ref_count > 1 )
    925                 {       // decrement reference counter
    926                         CPPAD_ASSERT_UNKNOWN( data_[start_target].value > 1 )
    927                         data_[start_target].value--;
    928                 }
     1104                size_t number_delete = drop(this_target);
    9291105
    9301106                // start the new list
     
    9471123                        {       // advance right so left and right are no longer equal
    9481124                                next_right  = other.data_[next_right].next;
    949                                 if( next_right == 0 )
    950                                         value_right = end_;
    951                                 else
    952                                         value_right = other.data_[next_right].value;
     1125                                value_right = other.data_[next_right].value;
    9531126                        }
    9541127                        if( value_left < value_right )
     
    9591132                                // advance left to its next element
    9601133                                next_left  = data_[next_left].next;
    961                                 if( next_left == 0 )
    962                                         value_left       = end_;
    963                                 else
    964                                         value_left = data_[next_left].value;
     1134                                value_left = data_[next_left].value;
    9651135                        }
    9661136                        else
     
    9721142                                // advance right to its next element
    9731143                                next_right  = other.data_[next_right].next;
    974                                 if( next_right == 0 )
    975                                         value_right = end_;
    976                                 else
    977                                         value_right = other.data_[next_right].value;
     1144                                value_right = other.data_[next_right].value;
    9781145                        }
    9791146                }
     
    10101177                size_t                  other_right  ,
    10111178                const sparse_list&      other        )
    1012         {
     1179        {       CPPAD_ASSERT_UNKNOWN( post_[this_left] == 0 );
     1180                CPPAD_ASSERT_UNKNOWN( other.post_[ other_right ] == 0 );
     1181                //
    10131182                CPPAD_ASSERT_UNKNOWN( this_target < start_.size()         );
    10141183                CPPAD_ASSERT_UNKNOWN( this_left   < start_.size()         );
     
    10351204                // must get all the start indices before modify start_this
    10361205                // (incase start_this is the same as start_left or start_right)
    1037                 size_t start_target  = start_[this_target];
    10381206                size_t start_left    = start_[this_left];
    10391207                size_t start_right   = other.start_[other_right];
    10401208
    1041 
    10421209                // number of list elements that will be deleted by this operation
    1043                 size_t number_delete = 0;
    1044                 size_t ref_count     = reference_count(this_target);
    1045                 if( ref_count == 1 )
    1046                         number_delete = number_elements(this_target) + 1;
    1047                 else if (ref_count > 1 )
    1048                 {       // decrement reference counter
    1049                         CPPAD_ASSERT_UNKNOWN( data_[start_target].value > 1 )
    1050                         data_[start_target].value--;
    1051                 }
     1210                size_t number_delete = drop(this_target);
    10521211
    10531212                // start the new list as emptyh
     
    10801239                                data_[next].value = value_left;
    10811240                                //
    1082                                 // advance left to its next element
     1241                                // advance left
    10831242                                next_left  = data_[next_left].next;
    1084                                 if( next_left == 0 )
    1085                                         value_left = end_;
    1086                                 else
    1087                                         value_left = data_[next_left].value;
     1243                                value_left = data_[next_left].value;
    10881244                                //
    10891245                        }
     
    10911247                        {       // advance right
    10921248                                next_right  = other.data_[next_right].next;
    1093                                 if( next_right == 0 )
    1094                                         value_right = end_;
    1095                                 else
    1096                                         value_right = other.data_[next_right].value;
     1249                                value_right = other.data_[next_right].value;
    10971250                        }
    10981251                        if( value_right > value_left )
    10991252                        {       // advance left
    11001253                                next_left  = data_[next_left].next;
    1101                                 if( next_left == 0 )
    1102                                         value_left = end_;
    1103                                 else
    1104                                         value_left = data_[next_left].value;
     1254                                value_left = data_[next_left].value;
    11051255                        }
    11061256                }
     
    11721322        data_( list.data_ )    ,
    11731323        end_ ( list.end_ )
    1174         {       CPPAD_ASSERT_UNKNOWN( i < list.start_.size() );
     1324        {       CPPAD_ASSERT_UNKNOWN( list.post_[i] == 0 );
     1325                //
    11751326                size_t start = list.start_[i];
    11761327                if( start == 0 )
     
    11941345        /// advance to next element in this list
    11951346        sparse_list_const_iterator& operator++(void)
    1196         {       if( next_pair_.next == 0 )
    1197                         next_pair_.value = end_;
    1198                 else
    1199                 {       next_pair_  = data_[next_pair_.next];
    1200                         CPPAD_ASSERT_UNKNOWN( next_pair_.value < end_ );
    1201                 }
     1347        {       next_pair_  = data_[next_pair_.next];
    12021348                return *this;
    12031349        }
  • trunk/cppad/local/sparse_pack.hpp

    r3987 r3989  
    5151        pod_vector<Pack>  data_;
    5252// ============================================================================
     53        /*!
     54        Assign a set equal to the union of a set and a vector;
     55
     56        \param target
     57        is the index in this sparse_list object of the set being assinged.
     58
     59        \param left
     60        is the index in this sparse_list object of the
     61        left operand for the union operation.
     62        It is OK for target and left to be the same value.
     63
     64        \param right
     65        is a vector of size_t, sorted in accending order.
     66        right operand for the union operation.
     67        Elements can be repeated in right, but are not be repeated in the
     68        resulting set.
     69        All of the elements must have value less than end();
     70        */
     71        void binary_union(
     72                size_t                    target ,
     73                size_t                    left   ,
     74                const pod_vector<size_t>& right  )
     75        {
     76                // initialize target = left
     77                size_t t = target * n_pack_;
     78                size_t l = left   * n_pack_;
     79                size_t j = n_pack_;
     80                while(j--)
     81                        data_[t++] = data_[l++];
     82
     83                // add the elements in right
     84                for(size_t i = 0; i < right.size(); ++i)
     85                        add_element(target, right[i]);
     86        }
    5387public:
    5488        /// declare a const iterator
     
    156190                return count;
    157191        }
     192        /*!
     193        Post an element for delayed addition to a set.
     194
     195        \param i
     196        is the index for this set in the vector of sets.
     197
     198        \param element
     199        is the value of the element that we are posting.
     200        The same element may be posted multiple times.
     201
     202        \par
     203        It is faster to post multiple elements to set i and then call
     204        process_post(i) then to add each element individually.
     205        It is an error to call any member function,
     206        that depends on the value of set i,
     207        before processing the posts to set i.
     208        */
     209        void post_element(size_t i, size_t element)
     210        {       add_element(i, element); }
     211        // -----------------------------------------------------------------
     212        /*!
     213        process post entries for a specific set.
     214
     215        \param i
     216        index of the set for which we are processing the post entries.
     217
     218        \par post_
     219        Upon call, post_[i] is location in data_ of the elements that get
     220        added to the i-th set.  Upon return, post_[i] is zero.
     221        */
     222        void process_post(size_t i)
     223        {       return; }
    158224        // -----------------------------------------------------------------
    159225        /*!
     
    248314                while(j--)
    249315                        data_[t++] = other.data_[v++];
    250         }
    251         // -----------------------------------------------------------------
    252         /*!
    253         Assign a set equal to the union of a set and a vector;
    254 
    255         \param target
    256         is the index in this sparse_list object of the set being assinged.
    257 
    258         \param left
    259         is the index in this sparse_list object of the
    260         left operand for the union operation.
    261         It is OK for target and left to be the same value.
    262 
    263         \param right
    264         is a vector of size_t, sorted in accending order.
    265         right operand for the union operation.
    266         Elements can be repeated in right, but are not be repeated in the
    267         resulting set.
    268         All of the elements must have value less than end();
    269         */
    270         void binary_union(
    271                 size_t                    target ,
    272                 size_t                    left   ,
    273                 const pod_vector<size_t>& right  )
    274         {
    275                 // initialize target = left
    276                 size_t t = target * n_pack_;
    277                 size_t l = left   * n_pack_;
    278                 size_t j = n_pack_;
    279                 while(j--)
    280                         data_[t++] = data_[l++];
    281 
    282                 // add the elements in right
    283                 for(size_t i = 0; i < right.size(); ++i)
    284                         add_element(target, right[i]);
    285316        }
    286317        // -----------------------------------------------------------------
  • trunk/cppad/local/sparse_sizevec.hpp

    r3987 r3989  
    2828Vector of sets of positive integers, each set stored as a size_t vector.
    2929
    30 All the public members for this class, except post_element and process_post,
    31 are also in the sparse_pack and sparse_list classes.
     30All the public members for this class are also in the
     31sparse_pack and sparse_list classes.
    3232This defines the CppAD vector_of_sets concept.
    3333*/
     
    8383
    8484        \li
    85         data_[ post_[i] + 2 ] is the first element that has benn posted,
     85        data_[ post_[i] + 2 ] is the first element that has been posted,
    8686        but not yet added, to set i.
    8787
     
    170170                CPPAD_ASSERT_UNKNOWN( post_.size() == start_.size() );
    171171                size_t n_set = start_.size();
    172 
     172                if( n_set == 0 )
     173                {       CPPAD_ASSERT_UNKNOWN( end_ == 0 );
     174                        CPPAD_ASSERT_UNKNOWN( data_not_used_ == 0 );
     175                        CPPAD_ASSERT_UNKNOWN( data_.size() == 0 );
     176                        CPPAD_ASSERT_UNKNOWN( start_.size() == 0 );
     177                        CPPAD_ASSERT_UNKNOWN( post_.size() == 0 );
     178                        return;
     179                }
    173180                // ------------------------------------------------------------------
    174181                // save the reference counters
     
    184191                {       size_t start = start_[i];
    185192                        if( start > 0 )
    186                         {       // check structure this non-empty set
     193                        {       // check structure for this non-empty set
    187194                                size_t reference_count = data_[start + 0];
    188195                                size_t length          = data_[start + 1];
     
    209216                }
    210217                // ------------------------------------------------------------------
    211                 // check the number of entries in data_ that are used by posts
     218                // count the number of entries in data_ that are used by posts
    212219                size_t data_used_by_posts = 0;
    213220                for(size_t i = 0; i < n_set; i++)
     
    381388                data_not_used_ = 1;
    382389        }
     390        // -----------------------------------------------------------------
     391        /*!
     392        Assign a set equal to the union of a set and a vector;
     393
     394        \param target
     395        is the index in this sparse_sizevec object of the set being assinged.
     396
     397        \param left
     398        is the index in this sparse_sizevec object of the
     399        left operand for the union operation.
     400        It is OK for target and left to be the same value.
     401
     402        \param right
     403        is a vector of size_t, sorted in accending order.
     404        right operand for the union operation.
     405        Elements can be repeated in right, but are not be repeated in the
     406        resulting set.
     407        All of the elements must have value less than end();
     408        */
     409        void binary_union(
     410                size_t                    target ,
     411                size_t                    left   ,
     412                const pod_vector<size_t>& right  )
     413        {       CPPAD_ASSERT_UNKNOWN( post_[left] == 0 );
     414                //
     415                CPPAD_ASSERT_UNKNOWN( target < start_.size() );
     416                CPPAD_ASSERT_UNKNOWN( left   < start_.size() );
     417
     418                size_t start_left   = start_[left];
     419                // -------------------------------------------------------------------
     420                // Check if right is a subset of left so that we used reference count
     421                // and not make copies of identical sets.
     422                //
     423                // initialize index for left and right sets
     424                size_t current_left  = start_left;
     425                size_t current_right = 0;
     426                //
     427                // initialize value_left
     428                size_t value_left  = end_;
     429                if( current_left > 0 )
     430                {       // advance from reference counter to data
     431                        current_left = current_left + 2;
     432                        value_left   = data_[current_left];
     433                        CPPAD_ASSERT_UNKNOWN( value_left < end_);
     434                }
     435                //
     436                // initialize value_right
     437                size_t value_right = end_;
     438                if( right.size() > 0 )
     439                        value_right = right[current_right];
     440                //
     441                bool subset = true;
     442                while( subset & (value_right < end_) )
     443                {       while( value_left < value_right )
     444                        {       // advance left
     445                                value_left = data_[++current_left];
     446                        }
     447                        if( value_right < value_left )
     448                                subset = false;
     449                        else
     450                        {       // advance right
     451                                ++current_right;
     452                                if( current_right == right.size() )
     453                                        value_right = end_;
     454                                else
     455                                        value_right = right[current_right];
     456                        }
     457                }
     458                //
     459                if( subset )
     460                {       // target = left will use reference count for identical sets
     461                        assignment(target, left, *this);
     462                        return;
     463                }
     464
     465                // -------------------------------------------------------------------
     466                // number of elements that will be deleted by removing old version
     467                // of target
     468                size_t number_lost = drop(target);
     469
     470                // drop any posting for the target set
     471                size_t post = post_[target];
     472                if( post > 0 )
     473                {       CPPAD_ASSERT_UNKNOWN( target != left );
     474                        size_t capacity = data_[post + 1];
     475                        number_lost += capacity + 2;
     476                        post_[target] = 0;
     477                }
     478                //
     479                // start new version of target
     480                size_t start       = data_.extend(2);
     481                start_[target]     = start;
     482                data_[start]       = 1; // reference count
     483                // data_[start + 1] = length is not yet known
     484                //
     485                // initialize value_left
     486                current_left = start_left;
     487                value_left   = end_;
     488                if( current_left > 0 )
     489                {       // advance from reference counter to data
     490                        current_left = current_left + 2;
     491                        value_left   = data_[current_left];
     492                        CPPAD_ASSERT_UNKNOWN( value_left < end_);
     493                }
     494                //
     495                // initialize value_right
     496                value_right = end_;
     497                if( right.size() > 0 )
     498                        value_right = right[current_right];
     499                //
     500                // merge
     501                while( (value_left < end_) | (value_right < end_) )
     502                {       if( value_left == value_right)
     503                        {       // advance left so left and right are no longer equal
     504                                ++current_left;
     505                                value_left = data_[current_left];
     506                                CPPAD_ASSERT_UNKNOWN( value_right < value_left );
     507                        }
     508                        //
     509                        if( value_left < value_right )
     510                        {       // value_left case
     511                                CPPAD_ASSERT_UNKNOWN( value_left < end_ );
     512                                data_.push_back( value_left );
     513                                //
     514                                // advance left
     515                                ++current_left;
     516                                value_left = data_[current_left];
     517                        }
     518                        else
     519                        {       CPPAD_ASSERT_UNKNOWN( value_right < value_left )
     520                                // value_right case
     521                                CPPAD_ASSERT_UNKNOWN( value_right < end_);
     522                                data_.push_back( value_right );
     523                                //
     524                                // advance right (skip values equal to this one)
     525                                size_t previous_value = value_right;
     526                                while( value_right == previous_value )
     527                                {       ++current_right;
     528                                        if( current_right == right.size() )
     529                                                value_right = end_;
     530                                        else
     531                                        {       value_right = right[current_right];
     532                                                CPPAD_ASSERT_UNKNOWN( value_right < end_ );
     533                                        }
     534                                }
     535                        }
     536                }
     537                // make end of target list
     538                data_.push_back( end_ );
     539                //
     540                // reference count, length, and end_ are not elements of set
     541                CPPAD_ASSERT_UNKNOWN( data_.size() > start + 3 );
     542                size_t length    = data_.size() - (start + 3);
     543                data_[start + 1] = length;
     544                //
     545
     546                // adjust data_not_used_
     547                data_not_used_ += number_lost;
     548                collect_garbage();
     549        }
    383550public:
    384         // =======================================================================
    385         // Public members NOT in vector_of_sets concept
    386         // =======================================================================
     551        /// declare a const iterator
     552        typedef sparse_sizevec_const_iterator const_iterator;
     553        // -----------------------------------------------------------------
     554        /*!
     555        Default constructor (no sets)
     556        */
     557        sparse_sizevec(void) :
     558        end_(0)            ,
     559        data_not_used_(0)  ,
     560        data_(0)           ,
     561        start_(0)          ,
     562        post_(0)
     563        { }
     564        // -----------------------------------------------------------------
     565        /// Destructor
     566        ~sparse_sizevec(void)
     567        {       check_data_structure();
     568        }
     569        // -----------------------------------------------------------------
     570        /*!
     571        Using copy constructor is a programing (not user) error
     572
     573        \param v
     574        vector of sets that we are attempting to make a copy of.
     575        */
     576        sparse_sizevec(const sparse_sizevec& v)
     577        {       // Error: Probably a sparse_sizevec argument has been passed by value
     578                CPPAD_ASSERT_UNKNOWN(false);
     579        }
     580        // -----------------------------------------------------------------
     581        /*!
     582        Assignement operator.
     583
     584        \param other
     585        this sparse_sizevec with be set to a deep copy of other.
     586        */
     587        void operator=(const sparse_sizevec& other)
     588        {       end_           = other.end_;
     589                data_not_used_ = other.data_not_used_;
     590                data_          = other.data_;
     591                start_         = other.start_;
     592                post_          = other.post_;
     593        }
     594        // -----------------------------------------------------------------
     595        /*!
     596        Start a new vector of sets.
     597
     598        \param n_set
     599        is the number of sets in this vector of sets.
     600        \li
     601        If n_set is zero, any memory currently allocated for this object
     602        is freed.
     603        \li
     604        If n_set is non-zero, a vector of n_set sets is created and all
     605        the sets are initilaized as empty.
     606
     607        \param end
     608        is the maximum element plus one (the minimum element is 0).
     609        If n_set is zero, end must also be zero.
     610        */
     611        void resize(size_t n_set, size_t end)
     612        {       check_data_structure();
     613
     614                if( n_set == 0 )
     615                {       CPPAD_ASSERT_UNKNOWN(end == 0 );
     616                        //
     617                        // restore object to start after constructor
     618                        // (no memory allocated for this object)
     619                        data_.clear();
     620                        start_.clear();
     621                        post_.clear();
     622                        data_not_used_  = 0;
     623                        end_            = 0;
     624                        //
     625                        return;
     626                }
     627                end_                   = end;
     628                //
     629                start_.resize(n_set);
     630                post_.resize(n_set);
     631                for(size_t i = 0; i < n_set; i++)
     632                {       start_[i] = 0;
     633                        post_[i]  = 0;
     634                }
     635                //
     636                data_.resize(1);     // first element is not used
     637                data_not_used_  = 1;
     638        }
     639        // -----------------------------------------------------------------
     640        /*!
     641        Return number of elements in a set.
     642
     643        \param i
     644        is the index of the set we are checking number of the elements of.
     645        */
     646        size_t number_elements(size_t i) const
     647        {       CPPAD_ASSERT_UNKNOWN( post_[i] == 0 );
     648                //
     649                size_t start = start_[i];
     650                if( start == 0 )
     651                        return 0;
     652                return data_[start + 1];
     653        }
     654        // ------------------------------------------------------------------
    387655        /*!
    388656        Post an element for delayed addition to a set.
     
    488756                //
    489757                bool subset = true;
    490                 while( subset & (first_post != last_post) )
    491                 {       CPPAD_ASSERT_UNKNOWN( value_post < end_ );
    492                         while( value_set < value_post )
     758                while( subset & (value_post != end_) )
     759                {       while( value_set < value_post )
    493760                                value_set = data_[++current_set];
    494761                        if( value_post < value_set )
     
    589856                return;
    590857        }
    591         // =======================================================================
    592         // Public members in vector_of_sets concept
    593         // =======================================================================
    594         /// declare a const iterator
    595         typedef sparse_sizevec_const_iterator const_iterator;
    596         // -----------------------------------------------------------------
    597         /*!
    598         Default constructor (no sets)
    599         */
    600         sparse_sizevec(void) :
    601         end_(0)            ,
    602         data_not_used_(0)  ,
    603         data_(0)           ,
    604         start_(0)          ,
    605         post_(0)
    606         { }
    607         // -----------------------------------------------------------------
    608         /// Destructor
    609         ~sparse_sizevec(void)
    610         {       check_data_structure();
    611         }
    612         // -----------------------------------------------------------------
    613         /*!
    614         Using copy constructor is a programing (not user) error
    615 
    616         \param v
    617         vector of sets that we are attempting to make a copy of.
    618         */
    619         sparse_sizevec(const sparse_sizevec& v)
    620         {       // Error: Probably a sparse_sizevec argument has been passed by value
    621                 CPPAD_ASSERT_UNKNOWN(false);
    622         }
    623         // -----------------------------------------------------------------
    624         /*!
    625         Assignement operator.
    626 
    627         \param other
    628         this sparse_sizevec with be set to a deep copy of other.
    629         */
    630         void operator=(const sparse_sizevec& other)
    631         {       end_           = other.end_;
    632                 data_not_used_ = other.data_not_used_;
    633                 start_         = other.start_;
    634                 post_          = other.post_;
    635                 data_          = other.data_;
    636         }
    637         // -----------------------------------------------------------------
    638         /*!
    639         Start a new vector of sets.
    640 
    641         \param n_set
    642         is the number of sets in this vector of sets.
    643         \li
    644         If n_set is zero, any memory currently allocated for this object
    645         is freed.
    646         \li
    647         If n_set is non-zero, a vector of n_set sets is created and all
    648         the sets are initilaized as empty.
    649 
    650         \param end
    651         is the maximum element plus one (the minimum element is 0).
    652         If n_set is zero, end must also be zero.
    653         */
    654         void resize(size_t n_set, size_t end)
    655         {       check_data_structure();
    656 
    657                 if( n_set == 0 )
    658                 {       CPPAD_ASSERT_UNKNOWN(end == 0 );
    659                         //
    660                         // restore object to start after constructor
    661                         // (no memory allocated for this object)
    662                         data_.clear();
    663                         start_.clear();
    664                         post_.clear();
    665                         data_not_used_  = 0;
    666                         end_            = 0;
    667                         //
    668                         return;
    669                 }
    670                 end_                   = end;
    671                 //
    672                 start_.resize(n_set);
    673                 post_.resize(n_set);
    674                 for(size_t i = 0; i < n_set; i++)
    675                 {       start_[i] = 0;
    676                         post_[i]  = 0;
    677                 }
    678                 //
    679                 data_.resize(1);     // first element is not used
    680                 data_not_used_  = 1;
    681         }
    682         // -----------------------------------------------------------------
    683         /*!
    684         Return number of elements in a set.
    685 
    686         \param i
    687         is the index of the set we are checking number of the elements of.
    688         */
    689         size_t number_elements(size_t i) const
    690         {       CPPAD_ASSERT_UNKNOWN( post_[i] == 0 );
    691                 //
    692                 size_t start = start_[i];
    693                 if( start == 0 )
    694                         return 0;
    695                 return data_[start + 1];
    696         }
    697858        // -----------------------------------------------------------------
    698859        /*!
     
    8921053                        data_.push_back(end_);
    8931054                }
    894 
    895                 // adjust data_not_used_
    896                 data_not_used_ += number_lost;
    897                 collect_garbage();
    898         }
    899         // -----------------------------------------------------------------
    900         /*!
    901         Assign a set equal to the union of a set and a vector;
    902 
    903         \param target
    904         is the index in this sparse_sizevec object of the set being assinged.
    905 
    906         \param left
    907         is the index in this sparse_sizevec object of the
    908         left operand for the union operation.
    909         It is OK for target and left to be the same value.
    910 
    911         \param right
    912         is a vector of size_t, sorted in accending order.
    913         right operand for the union operation.
    914         Elements can be repeated in right, but are not be repeated in the
    915         resulting set.
    916         All of the elements must have value less than end();
    917         */
    918         void binary_union(
    919                 size_t                    target ,
    920                 size_t                    left   ,
    921                 const pod_vector<size_t>& right  )
    922         {       CPPAD_ASSERT_UNKNOWN( post_[left] == 0 );
    923                 //
    924                 CPPAD_ASSERT_UNKNOWN( target < start_.size() );
    925                 CPPAD_ASSERT_UNKNOWN( left   < start_.size() );
    926 
    927                 size_t start_left   = start_[left];
    928                 // -------------------------------------------------------------------
    929                 // Check if right is a subset of left so that we used reference count
    930                 // and not make copies of identical sets.
    931                 //
    932                 // initialize index for left and right sets
    933                 size_t current_left  = start_left;
    934                 size_t current_right = 0;
    935                 //
    936                 // initialize value_left
    937                 size_t value_left  = end_;
    938                 if( current_left > 0 )
    939                 {       // advance from reference counter to data
    940                         current_left = current_left + 2;
    941                         value_left   = data_[current_left];
    942                         CPPAD_ASSERT_UNKNOWN( value_left < end_);
    943                 }
    944                 //
    945                 // initialize value_right
    946                 size_t value_right = end_;
    947                 if( right.size() > 0 )
    948                         value_right = right[current_right];
    949                 //
    950                 bool subset = true;
    951                 while( subset & (value_right < end_) )
    952                 {       while( value_left < value_right )
    953                         {       // advance left
    954                                 value_left = data_[++current_left];
    955                         }
    956                         if( value_right < value_left )
    957                                 subset = false;
    958                         else
    959                         {       // advance right
    960                                 ++current_right;
    961                                 if( current_right == right.size() )
    962                                         value_right = end_;
    963                                 else
    964                                         value_right = right[current_right];
    965                         }
    966                 }
    967                 //
    968                 if( subset )
    969                 {       // target = left will use reference count for identical sets
    970                         assignment(target, left, *this);
    971                         return;
    972                 }
    973 
    974                 // -------------------------------------------------------------------
    975                 // number of elements that will be deleted by removing old version
    976                 // of target
    977                 size_t number_lost = drop(target);
    978 
    979                 // drop any posting for the target set
    980                 size_t post = post_[target];
    981                 if( post > 0 )
    982                 {       CPPAD_ASSERT_UNKNOWN( target != left );
    983                         size_t capacity = data_[post + 1];
    984                         number_lost += capacity + 2;
    985                         post_[target] = 0;
    986                 }
    987                 //
    988                 // start new version of target
    989                 size_t start       = data_.extend(2);
    990                 start_[target]     = start;
    991                 data_[start]       = 1; // reference count
    992                 // data_[start + 1] = length is not yet known
    993                 //
    994                 // initialize value_left
    995                 current_left = start_left;
    996                 value_left   = end_;
    997                 if( current_left > 0 )
    998                 {       // advance from reference counter to data
    999                         current_left = current_left + 2;
    1000                         value_left   = data_[current_left];
    1001                         CPPAD_ASSERT_UNKNOWN( value_left < end_);
    1002                 }
    1003                 //
    1004                 // initialize value_right
    1005                 value_right = end_;
    1006                 if( right.size() > 0 )
    1007                         value_right = right[current_right];
    1008                 //
    1009                 // merge
    1010                 while( (value_left < end_) | (value_right < end_) )
    1011                 {       if( value_left == value_right)
    1012                         {       // advance left so left and right are no longer equal
    1013                                 ++current_left;
    1014                                 value_left = data_[current_left];
    1015                                 CPPAD_ASSERT_UNKNOWN( value_right < value_left );
    1016                         }
    1017                         //
    1018                         if( value_left < value_right )
    1019                         {       // value_left case
    1020                                 CPPAD_ASSERT_UNKNOWN( value_left < end_ );
    1021                                 data_.push_back( value_left );
    1022                                 //
    1023                                 // advance left
    1024                                 ++current_left;
    1025                                 value_left = data_[current_left];
    1026                         }
    1027                         else
    1028                         {       CPPAD_ASSERT_UNKNOWN( value_right < value_left )
    1029                                 // value_right case
    1030                                 CPPAD_ASSERT_UNKNOWN( value_right < end_);
    1031                                 data_.push_back( value_right );
    1032                                 //
    1033                                 // advance right (skip values equal to this one)
    1034                                 size_t previous_value = value_right;
    1035                                 while( value_right == previous_value )
    1036                                 {       ++current_right;
    1037                                         if( current_right == right.size() )
    1038                                                 value_right = end_;
    1039                                         else
    1040                                         {       value_right = right[current_right];
    1041                                                 CPPAD_ASSERT_UNKNOWN( value_right < end_ );
    1042                                         }
    1043                                 }
    1044                         }
    1045                 }
    1046                 // make end of target list
    1047                 data_.push_back( end_ );
    1048                 //
    1049                 // reference count, length, and end_ are not elements of set
    1050                 CPPAD_ASSERT_UNKNOWN( data_.size() > start + 3 );
    1051                 size_t length    = data_.size() - (start + 3);
    1052                 data_[start + 1] = length;
    1053                 //
    10541055
    10551056                // adjust data_not_used_
  • trunk/doc.omh

    r3987 r3989  
    9191$comment bin/version assumes that : follows cppad version number here$$
    9292$section
    93 cppad-20171201: A Package for Differentiation of C++ Algorithms
     93cppad-20171203: A Package for Differentiation of C++ Algorithms
    9494$$
    9595$mindex AD algorithmic differentiation automatic C++ algorithm derivative CppAD version cppad.hpp$$
  • trunk/test_more/general/local/vector_set.cpp

    r3987 r3989  
    194194
    195195template<class VectorSet>
    196 bool test_vector_union(void)
     196bool test_post(void)
    197197{       bool ok = true;
    198198        //
     
    206206        vec_set.add_element(1, 2);
    207207        //
    208         // set[1] = {1, 2} union {2, 4} = {1, 2, 4}
     208        // set[1] = {1, 2} union (2, 4, 4) = {1, 2, 4}
    209209        size_t target = 1;
    210         size_t left   = 1;
    211         CppAD::local::pod_vector<size_t> right(3);
    212         right[0] = 2;
    213         right[1] = 4;
    214         right[2] = 4; // repeated element
    215         vec_set.binary_union(target, left, right);
     210        vec_set.post_element(target, 2);
     211        vec_set.post_element(target, 4);
     212        vec_set.post_element(target, 4);
     213        vec_set.process_post(target);
    216214        //
    217215        typename VectorSet::const_iterator itr1(vec_set, target);
     
    221219        ok &= *(++itr1) == end;
    222220        //
    223         // check case where right is a subset of left
    224         target = 0;
    225         left   = 1;
    226         vec_set.binary_union(target, left, right);
     221        // set[1] = {1, 2, 4} union (1, 2)
     222        target = 1;
     223        vec_set.post_element(target, 1);
     224        vec_set.post_element(target, 2);
     225        vec_set.process_post(target);
    227226        //
    228227        typename VectorSet::const_iterator itr2(vec_set, target);
     
    252251        ok     &= test_intersection<CppAD::local::sparse_sizevec>();
    253252        //
    254         ok     &= test_vector_union<CppAD::local::sparse_pack>();
    255         ok     &= test_vector_union<CppAD::local::sparse_list>();
    256         ok     &= test_vector_union<CppAD::local::sparse_sizevec>();
    257         //
    258         return ok;
    259 }
     253        ok     &= test_post<CppAD::local::sparse_pack>();
     254        ok     &= test_post<CppAD::local::sparse_list>();
     255        ok     &= test_post<CppAD::local::sparse_sizevec>();
     256        //
     257        return ok;
     258}
Note: See TracChangeset for help on using the changeset viewer.