1/* --------------------------------------------------------------------------
2CppAD: C++ Algorithmic Differentiation: Copyright (C) 2003-19 Bradley M. Bell
3
4CppAD is distributed under the terms of the
5             Eclipse Public License Version 2.0.
6
7This Source Code may also be made available under the following
8Secondary License when the conditions for such availability set forth
9in the Eclipse Public License, Version 2.0 are satisfied:
10      GNU General Public License, Version 2.0 or later.
11---------------------------------------------------------------------------- */
12
13$begin SetVector$$
14$spell
15    dereference
16    itr
17    iterator
18    const
19    resize
20    vec
21    CppAD
22    bool
23$$
24
25$section C++ Concept: Vector of Sets With size_t Elements$$
26
27$head Purpose$$
28The main CppAD use of this C++ Concept is to compute sparsity patterns
29as fast as possible.
30It is also used for conditional expression optimization.
31We refer to a type that supports this concept as $icode SetVector$$ below.
32
33$head Vector Operations$$
34
35$subhead Constructor$$
36In the specifications below, $icode vec$$ and $icode other$$
37are $icode SetVector$$ objects created using the default constructor; e.g.,
38$codei%
39    %SetVector% %vec%, %other%;
40%$$
41After this constructor the vectors are empty; i.e.,
42there are no sets in either vector.
43The $code resize$$ for $icode vec$$ and $icode other$$ can
44have different $cref/n_set/SetVector/Vector Operations/n_set/$$ values,
45but must have the same $cref/end/SetVector/Vector Operations/end/$$ value.
46
47$subhead resize$$
48This operation has the following syntax:
49$codei%
50    %vec%.resize(%n_set%, %end%)
51%$$
52The argument $icode n_set$$ has type $code size_t$$ and is the
53number of sets in $icode vec$$.
54The argument $icode end$$ has type $code size_t$$ and is greater than
55any element allowed in any set in $icode vec$$.
56Any information in $icode vec$$ before this operation is lost.
57After this operation, all the sets in $icode vec$$ are empty.
58If $icode n_set$$ is zero,
59any allocated memory to keep track of this vector of sets is freed.
60
61$subhead n_set$$
62The syntax
63$codei%
64    %n_set% = %vec%.n_set()
65%$$
66sets the $code size_t$$ value $icode n_set$$ equal to the
67number of sets in $icode vec$$.
68The $icode vec$$ object is $code const$$ for this operation.
69
70$subhead end$$
71The syntax
72$codei%
73    %end% = %vec%.end()
74%$$
75sets the $code size_t$$ value $icode end$$ equal to the
76end value for the sets in $icode vec$$.
77(This is one greater than the maximum value for any element
78in any set in $icode vec$$.)
79The $icode vec$$ object is $code const$$ for this operation.
80
81$subhead Assignment$$
82The following
83makes $icode vec$$ into a separate copy of $icode other$$:
84$codei%
85    %vec% = %other%
86%$$
87The $icode other$$ object is $code const$$ for this operation.
88
89$subhead swap$$
90The following
91exchanges to vector of sets in $icode vec$$ and $icode other$$:
92$codei%
93    %vec%.swap(%other%)
94%$$
95
96$head number_elements$$
97If $icode i$$ is a $code size_t$$ value less than $icode n_set$$,
98$codei%
99    %count% = %vec%.number_elements(%i%)
100%$$
101returns the $code size_t$$ value $icode count$$
102equal to the number of elements in the $th i$$ set.
103The $icode vec$$ object is $code const$$ for this operation.
104It is an error to have postings to $th i$$ that have not been processed.
105
106$head add_element$$
107If $icode i$$ is a $code size_t$$ value less than $icode n_set$$
108and $icode element$$ is a $code size_t$$ value less than $icode end$$,
109$codei%
110    %vec%.add_element(%i%, %element%)
111%$$
112adds the specified element to the $th i$$ set.
113
114$head post_element$$
115If $icode i$$ is a $code size_t$$ value less than $icode n_set$$
116and $icode element$$ is a $code size_t$$ value less than $icode end$$,
117$codei%
118    %vec%.post_element(%i%, %element%)
119%$$
120post the specified element for addition to the $th i$$ set.
121Posting multiple elements to one set and then processing them may be faster
122than adding one element at a time.
123It is an error to use $icode vec$$,
124in a way that depends on the values in the $th i$$ set,
125between a $code post_element$$ and the corresponding $code process_post$$.
126
127$head process_post$$
128If $icode i$$ is a $code size_t$$ value less than $icode n_set$$,
129$codei%
130    %vec%.process_post(%i%)
131%$$
132Processes all of the posts that have been made for the $th i$$ set; i.e.,
133adds the posted elements to the set.
134
135$head is_element$$
136If $icode i$$ is a $code size_t$$ value less than $icode n_set$$
137and $icode element$$ is a $code size_t$$ value less than $icode end$$,
138$codei%
139    %find% = %vec%.is_element(%i%, %element%)
140%$$
141returns the $code bool$$ value $icode find$$
142which is  true (false) if the specified element is in
143(is not in) the $th i$$ set.
144The $icode vec$$ object is $code const$$ for this operation.
145
146$head clear$$
147If $icode i$$ is a $code size_t$$ value less than $icode n_set$$,
148$codei%
149    %vec%.clear(%i%)
150%$$
151assigns the empty set to the $th i$$ set.
152It is OK to have postings to $th i$$ that have not been processed
153(they are removed).
154
155$head assignment$$
156If $icode this_target$$ and $icode other_source$$
157are $code size_t$$ with value less than the end value,
158$codei%
159    %vec%.assignment(%this_target%, %other_source%, %other%)
160%$$
161sets the $icode this_target$$ set in $icode vec$$
162equal to the $icode other_source$$ set in $icode other$$.
163If $icode vec$$ and $icode other$$ are the same object,
164this operation may save memory and time using smart pointers.
165The $icode other$$ object is $code const$$ for this operation.
166It is OK (is an error) to have postings to $icode this_target$$
167($icode other_source$$) that have not been processed.
168
169$head binary_union$$
170If $icode this_target$$, $icode this_left$$, and $icode other_right$$
171are $code size_t$$ with value less than the end value,
172$codei%
173    %vec%.binary_union(
174        %this_target%, %this_left%, %other_right%, %other%
175    )
176%$$
177sets the $icode this_target$$ set in $icode vec$$ equal to the union of
178the $icode this_left$$ set in $icode vec$$ and
179the $icode other_right$$ set in $icode other$$.
180If the resulting set is equal to the left set (right set),
181this operation may use save memory and time using smart pointers
182(provided $icode vec$$ and $icode other$$ are the same object),
183The $icode other$$ object is $code const$$ for this operation.
184It is OK (is an error) to have postings to $icode this_target$$
185($icode this_left$$ and $code other_right$$) that have not been processed.
186
187$head binary_intersection$$
188If $icode this_target$$, $icode this_left$$, and $icode other_right$$
189are $code size_t$$ with value less than the end value,
190$codei%
191    %vec%.binary_intersection(
192        %this_target%, %this_left%, %other_right%, %other%
193    )
194%$$
195sets the $icode this_target$$ set in $icode vec$$ equal to the intersection of
196the $icode this_left$$ set in $icode vec$$ and
197the $icode other_right$$ set in $icode other$$.
198If the resulting set is equal to the left set (right set),
199this operation may use save memory and time using smart pointers
200(provided $icode vec$$ and $icode other$$ are the same object),
201The $icode other$$ object is $code const$$ for this operation.
202It is OK (is an error) to have postings to $icode this_target$$
203($icode this_left$$ and $code other_right$$) that have not been processed.
204
205
206$head const_iterator$$
207
208$subhead Constructor$$
209Given a $icode SetVector$$ object $icode vec$$,
210and a $code size_t$$ index $icode i$$,
211a constant iterator $icode itr$$ is constructed as follows:
212$codei%
213    %SetVector%::const_iterator %itr%(%vec%, %i%)
214%$$
215After this constructor, $icode itr$$ points to the first
216(smallest) element in the $th i$$ set.
217The $icode vec$$ object is $code const$$ for this operation.
218It is an error to have postings to $th i$$ that have not been processed.
219
220$subhead Dereference$$
221The operation
222$codei%
223    %element% = *%itr
224%$$
225sets the $code size_t$$ value $icode element$$ to the current element value.
226If $icode element$$ is equal to value $icode%vec%.end()%$$,
227we have iterated through all the elements of the set
228($icode element$$ is not in the set).
229It is an error to have postings to $th i$$ that have not been processed.
230
231$subhead Increment$$
232The operation $codei%++%itr%$$ points $icode itr$$ to the next larger
233element in the set.
234The increment operation is not defined when the value of
235$codei%*%itr%$$ is equal to $icode%vec%.end()%$$.
236The operation
237$codei%
238    %element% = *(++%itr%)
239%$$
240increments the iterator $icode itr$$ and sets $icode element$$
241to the deference after the increment (see dereference above).
242It is an error to have postings to $th i$$ that have not been processed.
243
244$head Implementation$$
245$children%
246    include/cppad/local/sparse/list_setvec.omh%
247    include/cppad/local/sparse/pack_setvec.omh
248%$$
249$table
250$rref list_setvec$$
251$rref pack_setvec$$
252$tend
253
254$end
255