sparse_sizevec.hpp

Go to the documentation of this file.

# ifndef CPPAD_LOCAL_SPARSE_SIZEVEC_HPP
# define CPPAD_LOCAL_SPARSE_SIZEVEC_HPP

/* --------------------------------------------------------------------------
CppAD: C++ Algorithmic Differentiation: Copyright (C) 2003-17 Bradley M. Bell

CppAD is distributed under multiple licenses. This distribution is under
the terms of the
                    Eclipse Public License Version 1.0.

A copy of this license is included in the COPYING file of this distribution.
Please visit http://www.coin-or.org/CppAD/ for information on other licenses.
-------------------------------------------------------------------------- */
# include <cppad/core/define.hpp>
# include <cppad/local/is_pod.hpp>
# include <list>

namespace CppAD { namespace local { // BEGIN_CPPAD_LOCAL_NAMESPACE
/*!
\file sparse_sizevec.hpp
Vector of sets of positive integers stored as size_t vector
with the element values strictly increasing.
*/
class sparse_sizevec_const_iterator;

// =========================================================================
/*!
Vector of sets of positive integers, each set stored as a size_t vector.

All the public members for this class are also in the
sparse_pack and sparse_list classes.
This defines the CppAD vector_of_sets concept.
*/
class sparse_sizevec {
     friend class sparse_sizevec_const_iterator;
private:
     /// Possible elements in each set are 0, 1, ..., end_ - 1;
     size_t end_;

     /// number of elements in data_ that have been allocated
     /// and are no longer being used.
     size_t data_not_used_;

     /// The data for all the singly linked lists.
     pod_vector<size_t> data_;

     /*!
     Starting point for i-th set is start_[i].

     \li
     If the i-th set has no elements, start_[i] is zero.
     Othersize the conditions below hold.

     \li
     data_[ start_[i] ] is the reference count for this set

     \li
     data_[ start_[i] + 1 ] is the first element in this set.

     \li
     data_[ start_[i] + 2 ] is the first element in this set.

     \li
     data_[ start_[i] + 2 + n ] = end_ where n is the number of
     elements in this set
     */
     pod_vector<size_t> start_;

     /*!
     Vectors of elements that have not yet been added to corresponding sets.

     \li
     If all the post_element calls for the i-th set have been added,
     post_[i] is zero. Otherwise the conditions below hold.

     \li
     data_[ post_[i] ]  the number of elements that have been posted,
     but not yet added, to set i.

     \li
     data_[ post_[i] + 1 ] is the capacity for holding elements
     which is greater than or equal the number of elements.

     \li
     data_[ post_[i] + 2 ] is the first element that has been posted,
     but not yet added, to set i.

     \li
     data_[ post_[i] + 1 + n] is the last element that has been posted,
     but not yet added, to set i.
     Here n is the number of elements that are posted and not yet added
     to set i.
     */
     pod_vector<size_t> post_;
     // -----------------------------------------------------------------
     /*!
     Counts references to a set.

     \param i
     is the index of the set that we are counting the references to.

     \return
     if the set is empty, the return value is zero.
     Otherwise it is the number of sets that share the same vector.
     */
     size_t reference_count(size_t i) const
     {    // start data index
          size_t start = start_[i];
          if( start == 0 )
               return 0;
          //
          // reference count
          return data_[start];
     }
     // -----------------------------------------------------------------
     /*!
     drop a set.

     \param i
     is the index of the set that will be dropped.

     \par reference_count
     if the set is non-empty,
     the reference count corresponding to index will be decremented.

     \return
     is the number of elements of data_ that will be lost when the set is
     dropped. This is non-zero when the initial reference count is one.
     */
     size_t drop(size_t i)
     {
          // reference count
          size_t ref_count = reference_count(i);

          // empty set case
          if( ref_count == 0 )
               return 0;

          // start
          size_t start = start_[i];
          CPPAD_ASSERT_UNKNOWN( data_[start] == ref_count );

          // decrement reference counter
          data_[start]--;

          // nothing lost unless new reference count is zero
          if( ref_count != 1 )
               return 0;

          // number of elements in the set
          size_t length = data_[start + 1];

          // reference count, length, end marker, plus elements in set
          size_t number_lost = 3 + length;

          // number_lost
          return number_lost;
     }
     // -----------------------------------------------------------------
     /*!
     Checks data structure
     (effectively const, but modifies and restores values)
     */
# ifdef NDEBUG
     void check_data_structure(void)
     {    return; }
# else
     void check_data_structure(void)
     {    // number of sets
          CPPAD_ASSERT_UNKNOWN( post_.size() == start_.size() );
          size_t n_set = start_.size();
          if( n_set == 0 )
          {    CPPAD_ASSERT_UNKNOWN( end_ == 0 );
               CPPAD_ASSERT_UNKNOWN( data_not_used_ == 0 );
               CPPAD_ASSERT_UNKNOWN( data_.size() == 0 );
               CPPAD_ASSERT_UNKNOWN( start_.size() == 0 );
               CPPAD_ASSERT_UNKNOWN( post_.size() == 0 );
               return;
          }
          // ------------------------------------------------------------------
          // save the reference counters
          pod_vector<size_t> ref_count(n_set);
          for(size_t i = 0; i < n_set; i++)
               ref_count[i] = reference_count(i);
          // ------------------------------------------------------------------

          // ------------------------------------------------------------------
          // count the number of entries in data_ that are used by sets
          size_t data_used_by_sets = 0;
          for(size_t i = 0; i < n_set; i++)
          {    size_t start = start_[i];
               if( start > 0 )
               {    // check structure for this non-empty set
                    size_t reference_count = data_[start + 0];
                    size_t length          = data_[start + 1];
                    size_t first           = data_[start + 2];
                    size_t last            = data_[start + 2 + length];
                    CPPAD_ASSERT_UNKNOWN( reference_count > 0 );
                    CPPAD_ASSERT_UNKNOWN( length          > 0 );
                    CPPAD_ASSERT_UNKNOWN( first < end_);
                    CPPAD_ASSERT_UNKNOWN( last == end_);
                    //
                    // decrement the reference counter
                    data_[start]--;
                    //
                    // count the entries when find last reference
                    if( data_[start] == 0 )
                    {
                         // restore reference count
                         data_[start] = ref_count[i];

                         // number of data_ entries used for this set
                         data_used_by_sets += number_elements(i) + 3;
                    }
               }
          }
          // ------------------------------------------------------------------
          // count the number of entries in data_ that are used by posts
          size_t data_used_by_posts = 0;
          for(size_t i = 0; i < n_set; i++)
          {    size_t post = post_[i];
               if( post > 0 )
               {    CPPAD_ASSERT_UNKNOWN( data_[post] > 0 );
                    CPPAD_ASSERT_UNKNOWN( data_[post + 1] > 0 );
                    CPPAD_ASSERT_UNKNOWN( data_[post + 2] < end_ );
                    //
                    size_t capacity     = data_[post + 1];
                    data_used_by_posts += capacity + 2;
               }
          }
          // ------------------------------------------------------------------
          size_t data_used = data_used_by_sets + data_used_by_posts;
          CPPAD_ASSERT_UNKNOWN(
               data_used + data_not_used_ == data_.size()
          );
          return;
     }
# endif
     // -----------------------------------------------------------------
     /*!
     Check if one of two sets is a subset of the other set

     \param one_this
     is the index in this sparse_sizevec object of the first set.

     \param two_other
     is the index in other sparse_sizevec object of the second set.

     \param other
     is the other sparse_sizevec object which may be the same as this object.

     \return
     If zero, niether set is a subset of the other.
     If one, then one is a subset of two and they are not equal.
     If two, then two is a subset of one and they are not equal.
     If three, then the sets are equal.
     */
     size_t is_subset(
          size_t                     one_this    ,
          size_t                     two_other   ,
          const sparse_sizevec&      other       ) const
     {
          CPPAD_ASSERT_UNKNOWN( one_this  < start_.size()         );
          CPPAD_ASSERT_UNKNOWN( two_other < other.start_.size()   );
          CPPAD_ASSERT_UNKNOWN( end_  == other.end_               );
          //
          // start
          size_t start_one    = start_[one_this];
          size_t start_two    = other.start_[two_other];
          //
          if( start_one == 0 )
          {    // set one is empty
               if( start_two == 0 )
               {    // set two is empty
                    return 3;
               }
               // set one is empty and two is not empty
               return 1;
          }
          if( start_two == 0 )
          {    // set two is empty and one is not empty
               return 2;
          }
          //
          // data index
          size_t index_one    = start_one + 2;
          size_t index_two    = start_two + 2;
          //
          // value
          size_t value_one    = data_[index_one];
          size_t value_two    = other.data_[index_two];
          //
          bool one_subset     = true;
          bool two_subset     = true;
          //
          size_t value_union = std::min(value_one, value_two);
          while( (one_subset | two_subset) & (value_union < end_) )
          {    //
               if( value_one > value_union )
                    two_subset = false;
               else
               {    // value_one <= value_two and value_one < end_
                    value_one = data_[++index_one];
               }
               //
               if( value_two > value_union )
                    one_subset = false;
               else
               {    // value_two <= value_one and value_two < end_
                    value_two = other.data_[++index_two];
               }
               value_union = std::min(value_one, value_two);
          }
          if( one_subset )
          {    if( two_subset )
               {    // sets are equal
                    return 3;
               }
               // one is a subset of two
               return 1;
          }
          if( two_subset )
          {    // two is a subset of one
               return 2;
          }
          //
          // neither is a subset
          return 0;
     }
     // -----------------------------------------------------------------
     /*!
     Does garbage collection when indicated.

     This routine should be called when more entries are not being used.
     If a significant propotion are not being used, the data structure
     will be compacted.

     The size of data_ should equal the number of entries used by the sets
     plus the number of entries that are not being used data_not_used_.
     Note that data_[0] never gets used.
     */
     void collect_garbage(void)
     {    if( data_not_used_ < data_.size() / 2 +  100)
               return;
          check_data_structure();
          //
          // number of sets including empty ones
          size_t n_set  = start_.size();
          //
          // use temporary to hold copy of data_ and start_
          pod_vector<size_t> data_tmp(1); // data_tmp[0] will not be used
          pod_vector<size_t> start_tmp(n_set);
          //
          for(size_t i = 0; i < n_set; i++)
          {    size_t start    = start_[i];
               if( start == 0 )
                    start_tmp[i] = 0;
               else
               {    // check if this set has already been copied
                    if( data_[start] == 0 )
                    {    // starting address in data_tmp has been stored here
                         start_tmp[i] = data_[start + 1];
                    }
                    else
                    {    size_t tmp_start          = data_tmp.extend(2);
                         start_tmp[i]              = tmp_start;
                         data_tmp[tmp_start + 0]   = data_[start + 0];
                         data_tmp[tmp_start + 1]   = data_[start + 1];
                         //
                         for(size_t j = 2; data_[start + j] != end_; ++j)
                              data_tmp.push_back( data_[start + j] );
                         data_tmp.push_back(end_);
                         //
                         // flag that indicates this set already copied
                         data_[start] = 0;
                         //
                         // store the starting address here
                         data_[start + 1] = tmp_start;
                    }
               }
          }

          // swap the tmp and old data vectors
          start_.swap(start_tmp);
          data_.swap(data_tmp);

          // all of the elements, except the first, are used
          data_not_used_ = 1;
     }
     // -----------------------------------------------------------------
     /*!
     Assign a set equal to the union of a set and a vector;

     \param target
     is the index in this sparse_sizevec object of the set being assinged.

     \param left
     is the index in this sparse_sizevec object of the
     left operand for the union operation.
     It is OK for target and left to be the same value.

     \param right
     is a vector of size_t, sorted in accending order.
     right operand for the union operation.
     Elements can be repeated in right, but are not be repeated in the
     resulting set.
     All of the elements must have value less than end();
     */
     void binary_union(
          size_t                    target ,
          size_t                    left   ,
          const pod_vector<size_t>& right  )
     {    CPPAD_ASSERT_UNKNOWN( post_[left] == 0 );
          //
          CPPAD_ASSERT_UNKNOWN( target < start_.size() );
          CPPAD_ASSERT_UNKNOWN( left   < start_.size() );

          size_t start_left   = start_[left];
          // -------------------------------------------------------------------
          // Check if right is a subset of left so that we used reference count
          // and not make copies of identical sets.
          //
          // initialize index for left and right sets
          size_t current_left  = start_left;
          size_t current_right = 0;
          //
          // initialize value_left
          size_t value_left  = end_;
          if( current_left > 0 )
          {    // advance from reference counter to data
               current_left = current_left + 2;
               value_left   = data_[current_left];
               CPPAD_ASSERT_UNKNOWN( value_left < end_);
          }
          //
          // initialize value_right
          size_t value_right = end_;
          if( right.size() > 0 )
               value_right = right[current_right];
          //
          bool subset = true;
          while( subset & (value_right < end_) )
          {    while( value_left < value_right )
               {    // advance left
                    value_left = data_[++current_left];
               }
               if( value_right < value_left )
                    subset = false;
               else
               {    // advance right
                    ++current_right;
                    if( current_right == right.size() )
                         value_right = end_;
                    else
                         value_right = right[current_right];
               }
          }
          //
          if( subset )
          {    // target = left will use reference count for identical sets
               assignment(target, left, *this);
               return;
          }

          // -------------------------------------------------------------------
          // number of elements that will be deleted by removing old version
          // of target
          size_t number_lost = drop(target);

          // drop any posting for the target set
          size_t post = post_[target];
          if( post > 0 )
          {    CPPAD_ASSERT_UNKNOWN( target != left );
               size_t capacity = data_[post + 1];
               number_lost += capacity + 2;
               post_[target] = 0;
          }
          //
          // start new version of target
          size_t start       = data_.extend(2);
          start_[target]     = start;
          data_[start]       = 1; // reference count
          // data_[start + 1] = length is not yet known
          //
          // initialize value_left
          current_left = start_left;
          value_left   = end_;
          if( current_left > 0 )
          {    // advance from reference counter to data
               current_left = current_left + 2;
               value_left   = data_[current_left];
               CPPAD_ASSERT_UNKNOWN( value_left < end_);
          }
          //
          // initialize value_right
          value_right = end_;
          if( right.size() > 0 )
               value_right = right[current_right];
          //
          // merge
          while( (value_left < end_) | (value_right < end_) )
          {    if( value_left == value_right)
               {    // advance left so left and right are no longer equal
                    ++current_left;
                    value_left = data_[current_left];
                    CPPAD_ASSERT_UNKNOWN( value_right < value_left );
               }
               //
               if( value_left < value_right )
               {    // value_left case
                    CPPAD_ASSERT_UNKNOWN( value_left < end_ );
                    data_.push_back( value_left );
                    //
                    // advance left
                    ++current_left;
                    value_left = data_[current_left];
               }
               else
               {    CPPAD_ASSERT_UNKNOWN( value_right < value_left )
                    // value_right case
                    CPPAD_ASSERT_UNKNOWN( value_right < end_);
                    data_.push_back( value_right );
                    //
                    // advance right (skip values equal to this one)
                    size_t previous_value = value_right;
                    while( value_right == previous_value )
                    {    ++current_right;
                         if( current_right == right.size() )
                              value_right = end_;
                         else
                         {    value_right = right[current_right];
                              CPPAD_ASSERT_UNKNOWN( value_right < end_ );
                         }
                    }
               }
          }
          // make end of target list
          data_.push_back( end_ );
          //
          // reference count, length, and end_ are not elements of set
          CPPAD_ASSERT_UNKNOWN( data_.size() > start + 3 );
          size_t length    = data_.size() - (start + 3);
          data_[start + 1] = length;
          //

          // adjust data_not_used_
          data_not_used_ += number_lost;
          collect_garbage();
     }
public:
     /// declare a const iterator
     typedef sparse_sizevec_const_iterator const_iterator;
     // -----------------------------------------------------------------
     /*!
     Default constructor (no sets)
     */
     sparse_sizevec(void) :
     end_(0)            ,
     data_not_used_(0)  ,
     data_(0)           ,
     start_(0)          ,
     post_(0)
     { }
     // -----------------------------------------------------------------
     /// Destructor
     ~sparse_sizevec(void)
     {    check_data_structure();
     }
     // -----------------------------------------------------------------
     /*!
     Using copy constructor is a programing (not user) error

     \param v
     vector of sets that we are attempting to make a copy of.
     */
     sparse_sizevec(const sparse_sizevec& v)
     {    // Error: Probably a sparse_sizevec argument has been passed by value
          CPPAD_ASSERT_UNKNOWN(false);
     }
     // -----------------------------------------------------------------
     /*!
     Assignement operator.

     \param other
     this sparse_sizevec with be set to a deep copy of other.
     */
     void operator=(const sparse_sizevec& other)
     {    end_           = other.end_;
          data_not_used_ = other.data_not_used_;
          data_          = other.data_;
          start_         = other.start_;
          post_          = other.post_;
     }
     // -----------------------------------------------------------------
     /*!
     Start a new vector of sets.

     \param n_set
     is the number of sets in this vector of sets.
     \li
     If n_set is zero, any memory currently allocated for this object
     is freed.
     \li
     If n_set is non-zero, a vector of n_set sets is created and all
     the sets are initilaized as empty.

     \param end
     is the maximum element plus one (the minimum element is 0).
     If n_set is zero, end must also be zero.
     */
     void resize(size_t n_set, size_t end)
     {    check_data_structure();

          if( n_set == 0 )
          {    CPPAD_ASSERT_UNKNOWN(end == 0 );
               //
               // restore object to start after constructor
               // (no memory allocated for this object)
               data_.clear();
               start_.clear();
               post_.clear();
               data_not_used_  = 0;
               end_            = 0;
               //
               return;
          }
          end_                   = end;
          //
          start_.resize(n_set);
          post_.resize(n_set);
          for(size_t i = 0; i < n_set; i++)
          {    start_[i] = 0;
               post_[i]  = 0;
          }
          //
          data_.resize(1);     // first element is not used
          data_not_used_  = 1;
     }
     // -----------------------------------------------------------------
     /*!
     Return number of elements in a set.

     \param i
     is the index of the set we are checking number of the elements of.
     */
     size_t number_elements(size_t i) const
     {    CPPAD_ASSERT_UNKNOWN( post_[i] == 0 );
          //
          size_t start = start_[i];
          if( start == 0 )
               return 0;
          return data_[start + 1];
     }
     // ------------------------------------------------------------------
     /*!
     Post an element for delayed addition to a set.

     \param i
     is the index for this set in the vector of sets.

     \param element
     is the value of the element that we are posting.
     The same element may be posted multiple times.

     \par
     It is faster to post multiple elements to set i and then call
     process_post(i) then to add each element individually.
     It is an error to call any member function,
     that depends on the value of set i,
     before processing the posts to set i.
     */
     void post_element(size_t i, size_t element)
     {    CPPAD_ASSERT_UNKNOWN( i < start_.size() );
          CPPAD_ASSERT_UNKNOWN( element < end_ );

          size_t post = post_[i];
          if( post == 0 )
          {    // minimum capacity for an post vector
               size_t min_capacity = 10;
               size_t post_new = data_.extend(min_capacity + 2);
               data_[post_new]     = 1;            // length
               data_[post_new + 1] = min_capacity; // capacity
               data_[post_new + 2] = element;
               post_[i]            = post_new;
          }
          else
          {    size_t length   = data_[post];
               size_t capacity = data_[post + 1];
               if( length == capacity )
               {
                    size_t post_new = data_.extend( 2 * capacity );
                    //
                    data_[post_new]     = length + 1;
                    data_[post_new + 1] = 2 * capacity;
                    //
                    for(size_t j = 0; j < length; j++)
                         data_[post_new + 2 + j] = data_[post + 2 + j];
                    data_[post_new + 2 + length] = element;
                    //
                    post_[i]            = post_new;
                    size_t number_lost = length + 2;
                    data_not_used_    += number_lost;
               }
               else
               {    data_[post]              = length + 1;
                    data_[post + 2 + length] = element;
               }
          }

          // check amount of data_not_used_
          collect_garbage();

          return;
     }
     // -----------------------------------------------------------------
     /*!
     process post entries for a specific set.

     \param i
     index of the set for which we are processing the post entries.

     \par post_
     Upon call, post_[i] is location in data_ of the elements that get
     added to the i-th set.  Upon return, post_[i] is zero.
     */
     void process_post(size_t i)
     {    // start
          size_t start = start_[i];
          // post
          size_t post = post_[i];
          //
          // check if there are no elements to process
          if( post == 0 )
               return;
          //
          // sort the elements that need to be processed
          size_t  length_post   = data_[post];
          size_t  capacity_post = data_[post + 1];
          size_t* first_post    = data_.data() + post + 2;
          size_t* last_post     = first_post + length_post;
          std::sort(first_post, last_post);
          // -------------------------------------------------------------------
          // check if posted elements are a subset of set
          //
          // first element of the set
          size_t current_set = start;
          size_t value_set   = end_;
          if( start > 0 )
          {    current_set = start + 2;
               value_set   = data_[current_set];
          }
          //
          // first element to post
          size_t* current_post = first_post;
          size_t  value_post   = *current_post;
          //
          bool subset = true;
          while( subset & (value_post != end_) )
          {    while( value_set < value_post )
                    value_set = data_[++current_set];
               if( value_post < value_set )
                    subset = false;
               else
               {    ++current_post;
                    if( current_post == last_post )
                         value_post = end_;
                    else
                         value_post = *current_post;
               }
          }
          //
          if( subset )
          {    // drop the post_ elements
               post_[i] = 0;
               //
               size_t number_lost = capacity_post + 2;
               data_not_used_    += number_lost;
               collect_garbage();
               //
               // nothing else to do
               return;
          }
          // -------------------------------------------------------------------
          // number of element that will be lost by removing old i-th set
          size_t number_lost = drop(i);

          // start new version of i-th set
          size_t start_new  = data_.extend(2);
          start_[i]         = start_new;
          data_[start_new]  = 1; // reference count
          // data[start_new + 1] = length_new is not yet known
          //
          // first element of the set
          current_set = start;
          value_set   = end_;
          if( start > 0 )
          {    current_set = start + 2;
               value_set   = data_[current_set];
          }
          //
          // first element to process
          current_post = first_post;
          value_post   = *current_post;
          //
          // merge
          while( (value_set < end_) | (current_post != last_post ) )
          {    if( value_set == value_post )
               {    // advance left so left and right are no longer equal
                    ++current_set;
                    value_set = data_[current_set];
                    CPPAD_ASSERT_UNKNOWN( value_post < value_set );
               }
               //
               if( value_set < value_post )
               {    // add value_set
                    CPPAD_ASSERT_UNKNOWN( value_set < end_ );
                    data_.push_back( value_set );
                    //
                    // advance set
                    ++current_set;
                    value_set = data_[current_set];
               }
               else
               {    CPPAD_ASSERT_UNKNOWN( value_post < value_set )
                    // add value_post
                    CPPAD_ASSERT_UNKNOWN( value_post < end_);
                    data_.push_back( value_post );
                    //
                    // advance post (skip values equal to this one)
                    size_t value_previous = value_post;
                    while( value_post == value_previous )
                    {    ++current_post;
                         if( current_post == last_post )
                              value_post = end_;
                         else
                              value_post = *current_post;
                    }
               }
          }
          // make end of target list
          data_.push_back( end_ );
          //
          // reference count, length, and end_ are not elements of set
          CPPAD_ASSERT_UNKNOWN( data_.size() > start_new + 3 );
          size_t length_new    = data_.size() - (start_new + 3);
          data_[start_new + 1] = length_new;
          CPPAD_ASSERT_UNKNOWN( data_[start_new + length_new + 2] == end_ );
          //
          // drop to post_ elements for this set
          post_[i] = 0;
          //
          number_lost    += capacity_post + 2;
          data_not_used_ += number_lost;
          collect_garbage();
          //
          return;
     }
     // -----------------------------------------------------------------
     /*!
     Add one element to a set.

     \param i
     is the index for this set in the vector of sets.

     \param element
     is the element we are adding to the set.
     */
     void add_element(size_t i, size_t element)
     {    CPPAD_ASSERT_UNKNOWN( i   < start_.size() );
          CPPAD_ASSERT_UNKNOWN( element < end_ );

          // check if element is already in the set
          if( is_element(i, element) )
               return;

          // check for case where old set is empty
          size_t start = start_[i];
          if( start == 0 )
          {    start            = data_.extend(4);
               start_[i]        = start;
               data_[start]     = 1;        // reference count
               data_[start + 1] = 1;        // length
               data_[start + 2] = element;  // the element
               data_[start + 3] = end_;     // end marker
               return;
          }
          //
          size_t number_lost = drop(i);
          //
          // start of new set
          size_t length         = data_[start + 1];
          size_t new_start      = data_.extend(2);
          data_[new_start]      = 1;          // reference count
          data_[new_start + 1]  = length + 1; // new length
          //
          size_t count = 0;
          size_t value     = data_[start + 2 + count];
          // before new element
          while( value < element)
          {    data_.push_back( value );
               ++count;
               value   = data_[start + 2 + count];
          }
          CPPAD_ASSERT_UNKNOWN( element < value )
          // new element
          data_.push_back( element );
          // after new element
          while( value < end_ )
          {    data_.push_back( value );
               ++count;
               value   = data_[start + 2 + count];
          }
          data_.push_back( end_ );

          //
          // connect up new set
          start_[i] = new_start;

          // adjust data_not_used_
          data_not_used_ += number_lost;
          collect_garbage();
          //
          return;
     }
     // -----------------------------------------------------------------
     /*!
     Check if an element is in a set.

     \param i
     is the index for this set in the vector of sets.

     \param element
     is the element we are checking to see if it is in the set.
     */
     bool is_element(size_t i, size_t element) const
     {    CPPAD_ASSERT_UNKNOWN( post_[i] == 0 );
          CPPAD_ASSERT_UNKNOWN( element < end_ );
          //
          size_t start = start_[i];
          if( start == 0 )
               return false;
          //
          size_t length       = data_[start + 1];
          const size_t* first = data_.data() + start + 2;
          const size_t* last  = first + length;
          if( length < 10 )
          {    bool result = false;
               while( last > first )
                    result |= *(--last) == element;
               return result;
          }
          //
          return std::binary_search(first, last, element);
     }
     // -----------------------------------------------------------------
     /*!
     Assign the empty set to one of the sets.

     \param target
     is the index of the set we are setting to the empty set.

     \par data_not_used_
     increments this value by number of data_ elements that are lost
     (unlinked) by this operation.
     */
     void clear(size_t target)
     {
          // number of data_ elements used for this set
          size_t number_lost = drop( target );

          // set target to empty set
          start_[target] = 0;

          // drop the posted elements
          if( post_[target] != 0 )
          {    size_t capacity = post_[target + 1];
               number_lost    += capacity + 2;
               //
               post_[target] = 0;
          }

          // adjust data_not_used_
          data_not_used_ += number_lost;
          collect_garbage();
     }
     // -----------------------------------------------------------------
     /*!
     Assign one set equal to another set.

     \param this_target
     is the index in this sparse_sizevec object of the set being assinged.

     \param other_source
     is the index in the other \c sparse_sizevec object of the
     set that we are using as the value to assign to the target set.

     \param other
     is the other sparse_sizevec object (which may be the same as this
     sparse_sizevec object). This must have the same value for end_.

     \par data_not_used_
     increments this value by number of elements lost.
     */
     void assignment(
          size_t                  this_target  ,
          size_t                  other_source ,
          const sparse_sizevec&   other        )
     {    CPPAD_ASSERT_UNKNOWN( other.post_[ other_source ] == 0 );
          //
          CPPAD_ASSERT_UNKNOWN( this_target  <   start_.size()        );
          CPPAD_ASSERT_UNKNOWN( other_source <   other.start_.size()  );
          CPPAD_ASSERT_UNKNOWN( end_        == other.end_   );

          // check if we are assigning a set to itself
          if( (this == &other) & (this_target == other_source) )
               return;

          // number of elements that will be deleted by this operation
          size_t number_lost = drop(this_target);

          // drop any posting for the target set
          size_t post = post_[this_target];
          if( post > 0 )
          {    // do not need to worry about target being same as source
               size_t capacity = data_[post + 1];
               number_lost += capacity + 2;
               post_[this_target] = 0;
          }

          // If this and other are the same, use another reference to same list
          size_t other_start = other.start_[other_source];
          if( this == &other )
          {    CPPAD_ASSERT_UNKNOWN( this_target != other_source );
               start_[this_target] = other_start;
               if( other_start != 0 )
               {    // increment reference count
                    data_[other_start]++;
               }
          }
          else if( other_start  == 0 )
          {    // the target list is empty
               start_[this_target] = 0;
          }
          else
          {    // make a copy of the other list in this sparse_sizevec
               size_t length         = other.data_[other_start + 1];
               size_t this_start     = data_.extend(2);
               start_[this_target]   = this_start;
               data_[this_start]     = 1;      // reference count
               data_[this_start + 1] = length; // length
               for(size_t j = 0; j < length; ++j)
                    data_.push_back( other.data_[other_start + 2 + j] );
               data_.push_back(end_);
          }

          // adjust data_not_used_
          data_not_used_ += number_lost;
          collect_garbage();
     }
     // -----------------------------------------------------------------
     /*!
     Assign a set equal to the union of two other sets.

     \param this_target
     is the index in this sparse_sizevec object of the set being assinged.

     \param this_left
     is the index in this sparse_sizevec object of the
     left operand for the union operation.
     It is OK for this_target and this_left to be the same value.

     \param other_right
     is the index in the other sparse_sizevec object of the
     right operand for the union operation.
     It is OK for this_target and other_right to be the same value.

     \param other
     is the other sparse_sizevec object (which may be the same as this
     sparse_sizevec object).
     */
     void binary_union(
          size_t                this_target  ,
          size_t                this_left    ,
          size_t                other_right  ,
          const sparse_sizevec& other        )
     {    CPPAD_ASSERT_UNKNOWN( post_[this_left] == 0 );
          CPPAD_ASSERT_UNKNOWN( other.post_[ other_right ] == 0 );
          //
          CPPAD_ASSERT_UNKNOWN( this_target < start_.size()         );
          CPPAD_ASSERT_UNKNOWN( this_left   < start_.size()         );
          CPPAD_ASSERT_UNKNOWN( other_right < other.start_.size()   );
          CPPAD_ASSERT_UNKNOWN( end_        == other.end_           );

          // check if one of the two operands is a subset of the the other
          size_t subset = is_subset(this_left, other_right, other);

          // case where right is a subset of left or right and left are equal
          if( subset == 2 || subset == 3 )
          {    assignment(this_target, this_left, *this);
               return;
          }
          // case where the left is a subset of right and they are not equal
          if( subset == 1 )
          {    assignment(this_target, other_right, other);
               return;
          }
          // if niether case holds, then both left and right are non-empty
          CPPAD_ASSERT_UNKNOWN( reference_count(this_left) > 0 );
          CPPAD_ASSERT_UNKNOWN( other.reference_count(other_right) > 0 );

          // must get all the start indices before modify start_this
          // (incase start_this is the same as start_left or start_right)
          size_t start_left    = start_[this_left];
          size_t start_right   = other.start_[other_right];

          // number of list elements that will be deleted by this operation
          size_t number_lost = drop(this_target);

          // drop any posting for the target set
          size_t post = post_[this_target];
          if( post > 0 )
          {    // do not need to worry about target being same as left or right
               size_t capacity = data_[post + 1];
               number_lost += capacity + 2;
               post_[this_target] = 0;
          }

          // start the new list
          size_t start        = data_.extend(2);
          start_[this_target] = start;
          data_[start]        = 1; // reference count
          // data_[start + 1] = length is not yet known

          // initilaize left
          CPPAD_ASSERT_UNKNOWN( start_left != 0 );
          size_t current_left = start_left + 2;
          size_t value_left   = data_[current_left];
          CPPAD_ASSERT_UNKNOWN( value_left < end_ );

          // initilaize right
          CPPAD_ASSERT_UNKNOWN( start_right != 0 );
          size_t current_right = start_right + 2;
          size_t value_right   = other.data_[current_right];
          CPPAD_ASSERT_UNKNOWN( value_right < end_ );


          CPPAD_ASSERT_UNKNOWN( value_left < end_ && value_right < end_ );
          while( (value_left < end_) | (value_right < end_) )
          {    if( value_left == value_right )
               {    // advance right so left and right are no longer equal
                    ++current_right;
                    value_right = other.data_[current_right];
               }
               if( value_left < value_right )
               {    data_.push_back( value_left );
                    // advance left to its next element
                    ++current_left;
                    value_left = data_[current_left];
               }
               else
               {    CPPAD_ASSERT_UNKNOWN( value_right < value_left )
                    data_.push_back( value_right );
                    // advance right to its next element
                    ++current_right;
                    value_right = other.data_[current_right];
               }
          }
          // make end of target list
          data_.push_back( end_ );
          //
          // reference count, length, and end_ are not elements of set
          CPPAD_ASSERT_UNKNOWN( data_.size() > start + 3 );
          size_t length = data_.size() - (start + 3);
          data_[start + 1] = length;

          // adjust data_not_used_
          data_not_used_ += number_lost;
          collect_garbage();
     }
     // -----------------------------------------------------------------
     /*!
     Assign a set equal to the intersection of two other sets.

     \param this_target
     is the index in this sparse_sizevec object of the set being assinged.

     \param this_left
     is the index in this sparse_sizevec object of the
     left operand for the intersection operation.
     It is OK for this_target and this_left to be the same value.

     \param other_right
     is the index in the other sparse_sizevec object of the
     right operand for the intersection operation.
     It is OK for this_target and other_right to be the same value.

     \param other
     is the other sparse_sizevec object (which may be the same as this
     sparse_sizevec object).
     */
     void binary_intersection(
          size_t                  this_target  ,
          size_t                  this_left    ,
          size_t                  other_right  ,
          const sparse_sizevec&   other        )
     {    CPPAD_ASSERT_UNKNOWN( post_[this_left] == 0 );
          CPPAD_ASSERT_UNKNOWN( other.post_[ other_right ] == 0 );
          //
          CPPAD_ASSERT_UNKNOWN( this_target < start_.size()         );
          CPPAD_ASSERT_UNKNOWN( this_left   < start_.size()         );
          CPPAD_ASSERT_UNKNOWN( other_right < other.start_.size()   );
          CPPAD_ASSERT_UNKNOWN( end_        == other.end_           );
          //
          // check if one of the two operands is a subset of the the other
          size_t subset = is_subset(this_left, other_right, other);

          // case where left is a subset of right or left and right are equal
          if( subset == 1 || subset == 3 )
          {    assignment(this_target, this_left, *this);
               return;
          }
          // case where the right is a subset of left and they are not equal
          if( subset == 2 )
          {    assignment(this_target, other_right, other);
               return;
          }
          // if niether case holds, then both left and right are non-empty
          CPPAD_ASSERT_UNKNOWN( reference_count(this_left) > 0 );
          CPPAD_ASSERT_UNKNOWN( other.reference_count(other_right) > 0 );

          // must get all the start indices before modify start_this
          // (incase start_this is the same as start_left or start_right)
          size_t start_left    = start_[this_left];
          size_t start_right   = other.start_[other_right];


          // number of list elements that will be deleted by this operation
          size_t number_lost = drop(this_target);

          // drop any posting for the target set
          size_t post = post_[this_target];
          if( post > 0 )
          {    // do not need to worry about target being same as left or right
               size_t capacity = data_[post + 1];
               number_lost += capacity + 2;
               post_[this_target] = 0;
          }

          // initialize intersection as empty
          size_t start        = 0;
          start_[this_target] = start;

          // initilaize left
          CPPAD_ASSERT_UNKNOWN( start_left != 0 );
          size_t current_left = start_left + 2;
          size_t value_left   = data_[current_left];
          CPPAD_ASSERT_UNKNOWN( value_left < end_ );

          // initilaize right
          CPPAD_ASSERT_UNKNOWN( start_right != 0 );
          size_t current_right = start_right + 2;
          size_t value_right   = other.data_[current_right];
          CPPAD_ASSERT_UNKNOWN( value_right < end_ );

          while( (value_left < end_) & (value_right < end_) )
          {    if( value_left == value_right )
               {    if( start == 0 )
                    {    // this is the first element in the intersection
                         start               = data_.extend(2);
                         start_[this_target] = start;
                         data_[start]        = 1; // reference count
                         // data_[start + 1] = length is not yet known
                    }
                    data_.push_back( value_left );
                    //
                    // advance left to its next element
                    ++current_left;
                    value_left = data_[current_left];
               }
               if( value_left > value_right )
               {    // advance right
                    ++current_right;
                    value_right = other.data_[current_right];
               }
               if( value_right > value_left )
               {    // advance left
                    ++current_left;
                    value_left = data_[current_left];
               }
          }
          if( start != 0 )
          {    data_.push_back(end_);
               CPPAD_ASSERT_UNKNOWN( data_.size() > start + 3 );
               size_t length = data_.size() - (start + 3);
               data_[start + 1] = length;
          }

          // adjust data_not_used_
          data_not_used_ += number_lost;
          collect_garbage();
     }
     // -----------------------------------------------------------------
     /*! Fetch n_set for vector of sets object.

     \return
     Number of from sets for this vector of sets object
     */
     size_t n_set(void) const
     {    return start_.size(); }
     // -----------------------------------------------------------------
     /*! Fetch end for this vector of sets object.

     \return
     is the maximum element value plus one (the minimum element value is 0).
     */
     size_t end(void) const
     {    return end_; }
     // -----------------------------------------------------------------
     /*! Amount of memory used by this vector of sets

     \return
     The amount of memory in units of type unsigned char memory.
     */
     size_t memory(void) const
     {    return data_.capacity() * sizeof(size_t);
     }
     /*!
     Print the vector of sets (used for debugging)
     */
     void print(void) const;
};
// =========================================================================
/*!
cons_iterator for one set of positive integers in a sparse_sizevec object.

All the public member functions for this class are also in the
sparse_pack_const_iterator and sparse_list_const_iterator classes.
This defines the CppAD vector_of_sets iterator concept.
*/
class sparse_sizevec_const_iterator {
private:
     /// data for the entire vector of sets
     const pod_vector<size_t>& data_;

     /// Possible elements in a list are 0, 1, ..., end_ - 1;
     const size_t                   end_;

     /// data index of next entry, zero for no more entries
     size_t                         data_index_;
public:
     /// construct a const_iterator for a set in a sparse_sizevec object
     sparse_sizevec_const_iterator (const sparse_sizevec& vec_set, size_t i)
     :
     data_( vec_set.data_ ) ,
     end_ ( vec_set.end_ )
     {    CPPAD_ASSERT_UNKNOWN( vec_set.post_[i] == 0 );
          //
          size_t start = vec_set.start_[i];
          if( start == 0 )
          {    data_index_ = 0;
          }
          else
          {    // data index of the first element in the set
               data_index_ = start + 2;
               CPPAD_ASSERT_UNKNOWN( data_[data_index_] < end_ );
          }
     }

     /// advance to next element in this list
     sparse_sizevec_const_iterator& operator++(void)
     {    if( data_index_ != 0 )
          {    ++data_index_;
               if( data_[data_index_] == end_ )
                    data_index_ = 0;
          }
          return *this;
     }

     /// obtain value of this element of the set of positive integers
     /// (end_ for no such element)
     size_t operator*(void)
     {    if( data_index_ == 0 )
               return end_;
          return data_[data_index_];
     }
};
// =========================================================================
/*!
Print the vector of sets (used for debugging)
*/
inline void sparse_sizevec::print(void) const
{    std::cout << "sparse_sizevec:\n";
     for(size_t i = 0; i < n_set(); i++)
     {    std::cout << "set[" << i << "] = {";
          const_iterator itr(*this, i);
          while( *itr != end() )
          {    std::cout << *itr;
               if( *(++itr) != end() )
                    std::cout << ",";
          }
          std::cout << "}\n";
     }
     return;
}

/*!
Copy a user vector of sets sparsity pattern to an internal sparse_sizevec object.

\tparam VectorSet
is a simple vector with elements of type std::set<size_t>.

\param internal
The input value of sparisty does not matter.
Upon return it contains the same sparsity pattern as \c user
(or the transposed sparsity pattern).

\param user
sparsity pattern that we are placing internal.

\param n_set
number of sets (rows) in the internal sparsity pattern.

\param end
end of set value (number of columns) in the interanl sparsity pattern.

\param transpose
if true, the user sparsity patter is the transposed.

\param error_msg
is the error message to display if some values in the user sparstiy
pattern are not valid.
*/
template<class VectorSet>
void sparsity_user2internal(
     sparse_sizevec&         internal  ,
     const VectorSet&        user      ,
     size_t                  n_set     ,
     size_t                  end       ,
     bool                    transpose ,
     const char*             error_msg )
{
# ifndef NDEBUG
     if( transpose )
          CPPAD_ASSERT_KNOWN( end == size_t( user.size() ), error_msg);
     if( ! transpose )
          CPPAD_ASSERT_KNOWN( n_set == size_t( user.size() ), error_msg);
# endif

     // iterator for user set
     std::set<size_t>::const_iterator itr;

     // size of internal sparsity pattern
     internal.resize(n_set, end);

     if( transpose )
     {    // transposed pattern case
          for(size_t j = 0; j < end; j++)
          {    itr = user[j].begin();
               while(itr != user[j].end())
               {    size_t i = *itr++;
                    CPPAD_ASSERT_KNOWN(i < n_set, error_msg);
                    internal.add_element(i, j);
               }
          }
     }
     else
     {    for(size_t i = 0; i < n_set; i++)
          {    itr = user[i].begin();
               while(itr != user[i].end())
               {    size_t j = *itr++;
                    CPPAD_ASSERT_KNOWN( j < end, error_msg);
                    internal.add_element(i, j);
               }
          }
     }
     return;
}

} } // END_CPPAD_LOCAL_NAMESPACE
# endif