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