1 # ifndef CPPAD_LOCAL_SPARSE_LIST_HPP
2 # define CPPAD_LOCAL_SPARSE_LIST_HPP
15 # include <cppad/local/is_pod.hpp>
18 namespace CppAD {
namespace local {
24 class sparse_list_const_iterator;
50 friend bool is_pod<pair_size_t>(void);
126 return data_[start].value;
154 size_t number_drop = 0;
157 size_t post =
post_[i];
164 size_t previous = post;
165 size_t next =
data_[previous].next;
168 next =
data_[previous].next;
184 data_[start].value--;
191 if(
data_[start].value > 0 )
197 size_t previous = start;
198 size_t next =
data_[previous].next;
201 next =
data_[previous].next;
233 { index =
data_.extend(1);
264 for(
size_t i = 0; i <
n_set; i++)
268 size_t number_used_by_sets = 1;
271 for(
size_t i = 0; i <
n_set; i++)
272 {
size_t start =
start_[i];
276 size_t next =
data_[start].next;
282 data_[start].value--;
285 if(
data_[start].value == 0 )
288 data_[start].value = ref_count[i];
302 size_t number_used_by_posts = 0;
303 for(
size_t i = 0; i <
n_set; i++)
304 {
size_t post =
post_[i];
306 {
size_t value =
data_[post].value;
307 size_t next =
data_[post].next;
310 while( value <
end_ )
311 { ++number_used_by_posts;
312 value =
data_[next].value;
313 next =
data_[next].next;
323 next =
data_[next].next;
327 size_t number_used = number_used_by_sets + number_used_by_posts;
363 size_t start_one =
start_[one_this];
364 size_t start_two = other.
start_[two_other];
380 size_t next_one =
data_[start_one].next;
381 size_t next_two = other.
data_[start_two].next;
384 size_t value_one =
data_[next_one].value;
385 size_t value_two = other.
data_[next_two].value;
387 bool one_subset =
true;
388 bool two_subset =
true;
390 size_t value_union = std::min(value_one, value_two);
391 while( (one_subset | two_subset) & (value_union <
end_) )
392 {
if( value_one > value_union )
395 { next_one =
data_[next_one].next;
396 value_one =
data_[next_one].value;
398 if( value_two > value_union )
401 { next_two = other.
data_[next_two].next;
402 value_two = other.
data_[next_two].value;
404 value_union = std::min(value_one, value_two);
452 size_t start_left =
start_[left];
459 size_t current_left = start_left;
460 size_t current_right = 0;
463 size_t value_left =
end_;
464 if( current_left > 0 )
466 current_left =
data_[current_left].next;
469 value_left =
data_[current_left].value;
474 size_t value_right =
end_;
475 if( right.
size() > 0 )
476 value_right = right[current_right];
479 while( subset & (value_right <
end_) )
480 {
while( value_left < value_right )
482 current_left =
data_[current_left].next;
483 value_left =
data_[current_left].value;
485 if( value_right < value_left )
490 if( current_right == right.
size() )
493 value_right = right[current_right];
507 data_[start].value = 1;
510 size_t previous_target = start;
513 current_left = start_left;
518 if( current_left > 0 )
520 current_left =
data_[current_left].next;
523 value_left =
data_[current_left].value;
529 if( right.
size() > 0 )
530 value_right = right[current_right];
533 while( (value_left <
end_) | (value_right <
end_) )
534 {
if( value_left == value_right)
536 current_left =
data_[current_left].next;
537 value_left =
data_[current_left].value;
542 data_[previous_target].next = current_target;
544 if( value_left < value_right )
547 data_[current_target].value = value_left;
550 current_left =
data_[current_left].next;
551 value_left =
data_[current_left].value;
557 data_[current_target].value = value_right;
560 size_t previous_value = value_right;
561 while( value_right == previous_value )
563 if( current_right == right.
size() )
566 { value_right = right[current_right];
572 previous_target = current_target;
575 data_[previous_target].next = 0;
578 size_t number_drop =
drop(target);
676 for(
size_t i = 0; i <
n_set; i++)
711 size_t next =
data_[start].next;
715 next =
data_[next].next;
742 size_t next =
post_[i];
745 data_[post].value = element;
746 data_[post].next = next;
763 size_t post =
post_[i];
770 size_t next =
data_[post].next;
773 size_t value =
data_[post].value;
786 size_t previous = post;
787 size_t value =
data_[previous].value;
792 value =
data_[previous].value;
795 next =
data_[previous].next;
833 data_[start].value = 1;
836 data_[start].next = next;
838 data_[next].value = element;
839 data_[next].next = 0;
844 size_t previous =
start_[i];
847 size_t next =
data_[previous].next;
848 size_t value =
data_[next].value;
851 while( value < element )
853 next =
data_[next].next;
854 value =
data_[next].value;
858 if( value == element )
864 if(
data_[start].value == 1 )
866 data_[insert].next = next;
867 data_[insert].value = element;
868 data_[previous].next = insert;
875 data_[start].value--;
878 data_[start_new].value = 1;
879 size_t previous_new = start_new;
885 next =
data_[previous].next;
886 value =
data_[next].value;
889 while( value < element )
892 data_[previous_new].next = next_new;
893 data_[next_new].value = value;
894 previous_new = next_new;
898 next =
data_[next].next;
899 value =
data_[next].value;
905 data_[previous_new].next = next_new;
906 data_[next_new].value = element;
907 previous_new = next_new;
910 while( value <
end_ )
913 data_[previous_new].next = next_new;
914 data_[next_new].value = value;
915 previous_new = next_new;
919 next =
data_[next].next;
920 value =
data_[next].value;
923 data_[previous_new].next = 0;
947 size_t next =
data_[start].next;
948 size_t value =
data_[next].value;
949 while( value < element )
950 { next =
data_[next].next;
951 value =
data_[next].value;
953 return element == value;
970 size_t number_drop =
drop(target);
995 size_t other_source ,
1004 if( (
this == &other) & (this_target == other_source) )
1011 size_t other_start = other.
start_[other_source];
1012 if(
this == &other )
1013 { this_start = other_start;
1014 if( other_start != 0 )
1015 {
data_[other_start].value++;
1019 else if( other_start == 0 )
1026 data_[this_start].value = 1;
1027 data_[this_start].next = this_next;
1029 size_t next = other.
data_[other_start].next;
1032 {
data_[this_next].value = other.
data_[next].value;
1033 next = other.
data_[next].next;
1035 data_[this_next].next = 0;
1038 data_[this_next].next = tmp;
1045 size_t number_drop =
drop(this_target);
1049 start_[this_target] = this_start;
1075 size_t this_target ,
1077 size_t other_right ,
1088 size_t subset =
is_subset(this_left, other_right, other);
1091 if( subset == 2 || subset == 3 )
1097 {
assignment(this_target, other_right, other);
1106 size_t start_left =
start_[this_left];
1107 size_t start_right = other.
start_[other_right];
1111 size_t next = start;
1112 data_[start].value = 1;
1115 size_t next_left =
data_[start_left].next;
1116 size_t next_right = other.
data_[start_right].next;
1119 size_t value_left =
data_[next_left].value;
1120 size_t value_right = other.
data_[next_right].value;
1123 while( (value_left <
end_) | (value_right <
end_) )
1124 {
if( value_left == value_right )
1126 next_right = other.
data_[next_right].next;
1127 value_right = other.
data_[next_right].value;
1129 if( value_left < value_right )
1131 data_[next].next = tmp;
1133 data_[next].value = value_left;
1135 next_left =
data_[next_left].next;
1136 value_left =
data_[next_left].value;
1141 data_[next].next = tmp;
1143 data_[next].value = value_right;
1145 next_right = other.
data_[next_right].next;
1146 value_right = other.
data_[next_right].value;
1149 data_[next].next = 0;
1152 size_t number_drop =
drop(this_target);
1156 start_[this_target] = start;
1182 size_t this_target ,
1184 size_t other_right ,
1195 size_t subset =
is_subset(this_left, other_right, other);
1198 if( subset == 1 || subset == 3 )
1204 {
assignment(this_target, other_right, other);
1213 size_t start_left =
start_[this_left];
1214 size_t start_right = other.
start_[other_right];
1218 size_t next = start;
1221 size_t next_left =
data_[start_left].next;
1222 size_t next_right = other.
data_[start_right].next;
1225 size_t value_left =
data_[next_left].value;
1226 size_t value_right = other.
data_[next_right].value;
1229 while( (value_left <
end_) & (value_right <
end_) )
1230 {
if( value_left == value_right )
1235 start_[this_target] = start;
1236 data_[start].value = 1;
1240 data_[next].next = tmp;
1242 data_[next].value = value_left;
1245 next_left =
data_[next_left].next;
1246 value_left =
data_[next_left].value;
1249 if( value_left > value_right )
1251 next_right = other.
data_[next_right].next;
1252 value_right = other.
data_[next_right].value;
1254 if( value_right > value_left )
1256 next_left =
data_[next_left].next;
1257 value_left =
data_[next_left].value;
1262 data_[next].next = 0;
1266 size_t number_drop =
drop(this_target);
1270 start_[this_target] = start;
1302 void print(
void)
const;
1334 size_t start = list.
start_[i];
1344 size_t next =
data_[start].next;
1369 { std::cout <<
"sparse_list:\n";
1370 for(
size_t i = 0; i <
n_set(); i++)
1371 { std::cout <<
"set[" << i <<
"] = {";
1373 while( *itr !=
end() )
1374 { std::cout << *itr;
1375 if( *(++itr) !=
end() )
1385 template <>
inline bool is_pod<sparse_list::pair_size_t>(void)
1415 template<
class VectorSet>
1418 const VectorSet& user ,
1422 const char* error_msg )
1432 std::set<size_t>::const_iterator itr;
1435 internal.resize(n_set, end);
1439 for(
size_t j = 0; j < end; j++)
1440 { itr = user[j].begin();
1441 while(itr != user[j].end())
1442 {
size_t i = *itr++;
1444 internal.add_element(i, j);
1449 {
for(
size_t i = 0; i < n_set; i++)
1450 { itr = user[i].begin();
1451 while(itr != user[i].end())
1452 {
size_t j = *itr++;
1454 internal.add_element(i, j);
void assignment(size_t this_target, size_t other_source, const sparse_list &other)
Assign one set equal to another set.
sparse_list(void)
Default constructor (no sets)
#define CPPAD_ASSERT_KNOWN(exp, msg)
Check that exp is true, if not print msg and terminate execution.
size_t end(void) const
Fetch end for this vector of sets object.
Vector of sets of positive integers, each set stored as a singly linked list.
Define processor symbols and macros that are used by CppAD.
void resize(size_t n)
resize the vector (existing elements preserved when n <= capacity_).
void clear(void)
Remove all the elements from this vector and free its memory.
void push_back(const Type &e)
Add an element to theh back of this vector.
void add_element(size_t i, size_t element)
Add one element to a set.
size_t end_
Possible elements in each set are 0, 1, ..., end_ - 1;.
void binary_intersection(size_t this_target, size_t this_left, size_t other_right, const sparse_list &other)
Assign a set equal to the intersection of two other sets.
pod_vector< size_t > post_
Vectors of elements that have not yet been added to corresponding sets.
A vector class with Type element that does not use element constructors or destructors when Type is P...
void binary_union(size_t target, size_t left, const pod_vector< size_t > &right)
Assign a set equal to the union of a set and a vector;.
size_t next
This is the data index of the next entry in the list. If there are no more entries in the list...
size_t number_not_used_
number of elements in data_ that are not being used.
pod_vector< size_t > start_
Starting point for i-th set is start_[i].
pod_vector< pair_size_t > data_
The data for all the singly linked lists.
size_t is_subset(size_t one_this, size_t two_other, const sparse_list &other) const
Check if one of two sets is a subset of the other set.
size_t number_elements(size_t i) const
Count number of elements in a set.
sparse_list::pair_size_t pair_size_t
type used by sparse_list to represent one element of the list
size_t drop(size_t i)
drop a set and its postings (no longer being used).
sparse_list_const_iterator & operator++(void)
advance to next element in this list
size_t memory(void) const
Amount of memory used by this vector of sets.
type used for each entry in a singly linked list.
void print(void) const
Print the vector of sets (used for debugging)
void post_element(size_t i, size_t element)
Post an element for delayed addition to a set.
void binary_union(size_t this_target, size_t this_left, size_t other_right, const sparse_list &other)
Assign a set equal to the union of two other sets.
size_t size(void) const
current number of elements in this vector.
size_t operator*(void)
obtain value of this element of the set of positive integers (end_ for no such element) ...
~sparse_list(void)
Destructor.
size_t value
For the first entry in each list, this is the reference count. For the other entries in the list this...
Type * data(void)
current data pointer is no longer valid after any of the following: extend, erase, operator=, and ~pod_vector. Take extreem care when using this function.
const size_t end_
Possible elements in a list are 0, 1, ..., end_ - 1;.
const pod_vector< pair_size_t > & data_
data for the entire vector of sets
#define CPPAD_ASSERT_UNKNOWN(exp)
Check that exp is true, if not terminate execution.
void clear(size_t target)
Assign the empty set to one of the sets.
size_t data_not_used_
list of elements of data_ that are not being used.
void resize(size_t n_set, size_t end)
Start a new vector of sets.
size_t reference_count(size_t i) const
Counts references to sets.
size_t get_data_index(void)
get a new data_ element for use.
pair_size_t next_pair_
next element in the singly linked list (next_pair_.value == end_ for past end of list) ...
void process_post(size_t i)
process post entries for a specific set.
size_t n_set(void) const
Fetch n_set for vector of sets object.
void check_data_structure(void)
Checks data structure (effectively const, but modifies and restores values)
bool is_element(size_t i, size_t element) const
check an element is in a set.
pod_vector< size_t > temporary_
A temporary vector used by member functions that keeps its capacity.
sparse_list_const_iterator const_iterator
declare a const iterator
sparse_list_const_iterator(const sparse_list &list, size_t i)
construct a const_iterator for a list in a sparse_list object
void operator=(const sparse_list &other)
Assignement operator.
sparse_list(const sparse_list &v)
Using copy constructor is a programing (not user) error.
cons_iterator for one set of positive integers in a sparse_list object.
void sparsity_user2internal(sparse_list &internal, const VectorSet &user, size_t n_set, size_t end, bool transpose, const char *error_msg)
Copy a user vector of sets sparsity pattern to an internal sparse_list object.