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

CppAD is distributed under the terms of the
             Eclipse Public License Version 2.0.

This Source Code may also be made available under the following
Secondary License when the conditions for such availability set forth
in the Eclipse Public License, Version 2.0 are satisfied:
      GNU General Public License, Version 2.0 or later.
---------------------------------------------------------------------------- */

$begin SetVector$$
$spell
    dereference
    itr
    iterator
    const
    resize
    vec
    CppAD
    bool
$$

$section C++ Concept: Vector of Sets With size_t Elements$$

$head Purpose$$
The main CppAD use of this C++ Concept is to compute sparsity patterns
as fast as possible.
It is also used for conditional expression optimization.
We refer to a type that supports this concept as $icode SetVector$$ below.

$head Vector Operations$$

$subhead Constructor$$
In the specifications below, $icode vec$$ and $icode other$$
are $icode SetVector$$ objects created using the default constructor; e.g.,
$codei%
    %SetVector% %vec%, %other%;
%$$
After this constructor the vectors are empty; i.e.,
there are no sets in either vector.
The $code resize$$ for $icode vec$$ and $icode other$$ can
have different $cref/n_set/SetVector/Vector Operations/n_set/$$ values,
but must have the same $cref/end/SetVector/Vector Operations/end/$$ value.

$subhead resize$$
This operation has the following syntax:
$codei%
    %vec%.resize(%n_set%, %end%)
%$$
The argument $icode n_set$$ has type $code size_t$$ and is the
number of sets in $icode vec$$.
The argument $icode end$$ has type $code size_t$$ and is greater than
any element allowed in any set in $icode vec$$.
Any information in $icode vec$$ before this operation is lost.
After this operation, all the sets in $icode vec$$ are empty.
If $icode n_set$$ is zero,
any allocated memory to keep track of this vector of sets is freed.

$subhead n_set$$
The syntax
$codei%
    %n_set% = %vec%.n_set()
%$$
sets the $code size_t$$ value $icode n_set$$ equal to the
number of sets in $icode vec$$.
The $icode vec$$ object is $code const$$ for this operation.

$subhead end$$
The syntax
$codei%
    %end% = %vec%.end()
%$$
sets the $code size_t$$ value $icode end$$ equal to the
end value for the sets in $icode vec$$.
(This is one greater than the maximum value for any element
in any set in $icode vec$$.)
The $icode vec$$ object is $code const$$ for this operation.

$subhead Assignment$$
The following
makes $icode vec$$ into a separate copy of $icode other$$:
$codei%
    %vec% = %other%
%$$
The $icode other$$ object is $code const$$ for this operation.

$subhead swap$$
The following
exchanges to vector of sets in $icode vec$$ and $icode other$$:
$codei%
    %vec%.swap(%other%)
%$$

$head number_elements$$
If $icode i$$ is a $code size_t$$ value less than $icode n_set$$,
$codei%
    %count% = %vec%.number_elements(%i%)
%$$
returns the $code size_t$$ value $icode count$$
equal to the number of elements in the $th i$$ set.
The $icode vec$$ object is $code const$$ for this operation.
It is an error to have postings to $th i$$ that have not been processed.

$head add_element$$
If $icode i$$ is a $code size_t$$ value less than $icode n_set$$
and $icode element$$ is a $code size_t$$ value less than $icode end$$,
$codei%
    %vec%.add_element(%i%, %element%)
%$$
adds the specified element to the $th i$$ set.

$head post_element$$
If $icode i$$ is a $code size_t$$ value less than $icode n_set$$
and $icode element$$ is a $code size_t$$ value less than $icode end$$,
$codei%
    %vec%.post_element(%i%, %element%)
%$$
post the specified element for addition to the $th i$$ set.
Posting multiple elements to one set and then processing them may be faster
than adding one element at a time.
It is an error to use $icode vec$$,
in a way that depends on the values in the $th i$$ set,
between a $code post_element$$ and the corresponding $code process_post$$.

$head process_post$$
If $icode i$$ is a $code size_t$$ value less than $icode n_set$$,
$codei%
    %vec%.process_post(%i%)
%$$
Processes all of the posts that have been made for the $th i$$ set; i.e.,
adds the posted elements to the set.

$head is_element$$
If $icode i$$ is a $code size_t$$ value less than $icode n_set$$
and $icode element$$ is a $code size_t$$ value less than $icode end$$,
$codei%
    %find% = %vec%.is_element(%i%, %element%)
%$$
returns the $code bool$$ value $icode find$$
which is  true (false) if the specified element is in
(is not in) the $th i$$ set.
The $icode vec$$ object is $code const$$ for this operation.

$head clear$$
If $icode i$$ is a $code size_t$$ value less than $icode n_set$$,
$codei%
    %vec%.clear(%i%)
%$$
assigns the empty set to the $th i$$ set.
It is OK to have postings to $th i$$ that have not been processed
(they are removed).

$head assignment$$
If $icode this_target$$ and $icode other_source$$
are $code size_t$$ with value less than the end value,
$codei%
    %vec%.assignment(%this_target%, %other_source%, %other%)
%$$
sets the $icode this_target$$ set in $icode vec$$
equal to the $icode other_source$$ set in $icode other$$.
If $icode vec$$ and $icode other$$ are the same object,
this operation may save memory and time using smart pointers.
The $icode other$$ object is $code const$$ for this operation.
It is OK (is an error) to have postings to $icode this_target$$
($icode other_source$$) that have not been processed.

$head binary_union$$
If $icode this_target$$, $icode this_left$$, and $icode other_right$$
are $code size_t$$ with value less than the end value,
$codei%
    %vec%.binary_union(
        %this_target%, %this_left%, %other_right%, %other%
    )
%$$
sets the $icode this_target$$ set in $icode vec$$ equal to the union of
the $icode this_left$$ set in $icode vec$$ and
the $icode other_right$$ set in $icode other$$.
If the resulting set is equal to the left set (right set),
this operation may use save memory and time using smart pointers
(provided $icode vec$$ and $icode other$$ are the same object),
The $icode other$$ object is $code const$$ for this operation.
It is OK (is an error) to have postings to $icode this_target$$
($icode this_left$$ and $code other_right$$) that have not been processed.

$head binary_intersection$$
If $icode this_target$$, $icode this_left$$, and $icode other_right$$
are $code size_t$$ with value less than the end value,
$codei%
    %vec%.binary_intersection(
        %this_target%, %this_left%, %other_right%, %other%
    )
%$$
sets the $icode this_target$$ set in $icode vec$$ equal to the intersection of
the $icode this_left$$ set in $icode vec$$ and
the $icode other_right$$ set in $icode other$$.
If the resulting set is equal to the left set (right set),
this operation may use save memory and time using smart pointers
(provided $icode vec$$ and $icode other$$ are the same object),
The $icode other$$ object is $code const$$ for this operation.
It is OK (is an error) to have postings to $icode this_target$$
($icode this_left$$ and $code other_right$$) that have not been processed.


$head const_iterator$$

$subhead Constructor$$
Given a $icode SetVector$$ object $icode vec$$,
and a $code size_t$$ index $icode i$$,
a constant iterator $icode itr$$ is constructed as follows:
$codei%
    %SetVector%::const_iterator %itr%(%vec%, %i%)
%$$
After this constructor, $icode itr$$ points to the first
(smallest) element in the $th i$$ set.
The $icode vec$$ object is $code const$$ for this operation.
It is an error to have postings to $th i$$ that have not been processed.

$subhead Dereference$$
The operation
$codei%
    %element% = *%itr
%$$
sets the $code size_t$$ value $icode element$$ to the current element value.
If $icode element$$ is equal to value $icode%vec%.end()%$$,
we have iterated through all the elements of the set
($icode element$$ is not in the set).
It is an error to have postings to $th i$$ that have not been processed.

$subhead Increment$$
The operation $codei%++%itr%$$ points $icode itr$$ to the next larger
element in the set.
The increment operation is not defined when the value of
$codei%*%itr%$$ is equal to $icode%vec%.end()%$$.
The operation
$codei%
    %element% = *(++%itr%)
%$$
increments the iterator $icode itr$$ and sets $icode element$$
to the deference after the increment (see dereference above).
It is an error to have postings to $th i$$ that have not been processed.

$head Implementation$$
$children%
    include/cppad/local/sparse/list_setvec.omh%
    include/cppad/local/sparse/pack_setvec.omh
%$$
$table
$rref list_setvec$$
$rref pack_setvec$$
$tend

$end