1 # ifndef CPPAD_LOCAL_SPARSE_SIZEVEC_HPP
2 # define CPPAD_LOCAL_SPARSE_SIZEVEC_HPP
15 # include <cppad/local/is_pod.hpp>
18 namespace CppAD {
namespace local {
24 class sparse_sizevec_const_iterator;
151 size_t length =
data_[start + 1];
154 size_t number_lost = 3 + length;
183 for(
size_t i = 0; i <
n_set; i++)
189 size_t data_used_by_sets = 0;
190 for(
size_t i = 0; i <
n_set; i++)
191 {
size_t start =
start_[i];
195 size_t length =
data_[start + 1];
196 size_t first =
data_[start + 2];
197 size_t last =
data_[start + 2 + length];
207 if(
data_[start] == 0 )
210 data_[start] = ref_count[i];
219 size_t data_used_by_posts = 0;
220 for(
size_t i = 0; i <
n_set; i++)
221 {
size_t post =
post_[i];
227 size_t capacity =
data_[post + 1];
228 data_used_by_posts += capacity + 2;
232 size_t data_used = data_used_by_sets + data_used_by_posts;
268 size_t start_one =
start_[one_this];
269 size_t start_two = other.
start_[two_other];
286 size_t index_one = start_one + 2;
287 size_t index_two = start_two + 2;
290 size_t value_one =
data_[index_one];
291 size_t value_two = other.
data_[index_two];
293 bool one_subset =
true;
294 bool two_subset =
true;
296 size_t value_union = std::min(value_one, value_two);
297 while( (one_subset | two_subset) & (value_union <
end_) )
299 if( value_one > value_union )
303 value_one =
data_[++index_one];
306 if( value_two > value_union )
310 value_two = other.
data_[++index_two];
312 value_union = std::min(value_one, value_two);
354 for(
size_t i = 0; i <
n_set; i++)
355 {
size_t start =
start_[i];
360 if(
data_[start] == 0 )
362 start_tmp[i] =
data_[start + 1];
365 {
size_t tmp_start = data_tmp.
extend(2);
366 start_tmp[i] = tmp_start;
367 data_tmp[tmp_start + 0] =
data_[start + 0];
368 data_tmp[tmp_start + 1] =
data_[start + 1];
370 for(
size_t j = 2;
data_[start + j] !=
end_; ++j)
378 data_[start + 1] = tmp_start;
418 size_t start_left =
start_[left];
424 size_t current_left = start_left;
425 size_t current_right = 0;
428 size_t value_left =
end_;
429 if( current_left > 0 )
431 current_left = current_left + 2;
432 value_left =
data_[current_left];
437 size_t value_right =
end_;
438 if( right.
size() > 0 )
439 value_right = right[current_right];
442 while( subset & (value_right <
end_) )
443 {
while( value_left < value_right )
445 value_left =
data_[++current_left];
447 if( value_right < value_left )
452 if( current_right == right.
size() )
455 value_right = right[current_right];
468 size_t number_lost =
drop(target);
471 size_t post =
post_[target];
474 size_t capacity =
data_[post + 1];
475 number_lost += capacity + 2;
486 current_left = start_left;
488 if( current_left > 0 )
490 current_left = current_left + 2;
491 value_left =
data_[current_left];
497 if( right.
size() > 0 )
498 value_right = right[current_right];
501 while( (value_left <
end_) | (value_right <
end_) )
502 {
if( value_left == value_right)
505 value_left =
data_[current_left];
509 if( value_left < value_right )
516 value_left =
data_[current_left];
525 size_t previous_value = value_right;
526 while( value_right == previous_value )
528 if( current_right == right.
size() )
531 { value_right = right[current_right];
542 size_t length =
data_.
size() - (start + 3);
543 data_[start + 1] = length;
631 for(
size_t i = 0; i <
n_set; i++)
652 return data_[start + 1];
676 size_t post =
post_[i];
679 size_t min_capacity = 10;
682 data_[post_new + 1] = min_capacity;
683 data_[post_new + 2] = element;
687 {
size_t length =
data_[post];
688 size_t capacity =
data_[post + 1];
689 if( length == capacity )
693 data_[post_new] = length + 1;
694 data_[post_new + 1] = 2 * capacity;
696 for(
size_t j = 0; j < length; j++)
697 data_[post_new + 2 + j] =
data_[post + 2 + j];
698 data_[post_new + 2 + length] = element;
701 size_t number_lost = length + 2;
705 {
data_[post] = length + 1;
706 data_[post + 2 + length] = element;
730 size_t post =
post_[i];
737 size_t length_post =
data_[post];
738 size_t capacity_post =
data_[post + 1];
739 size_t* first_post =
data_.
data() + post + 2;
740 size_t* last_post = first_post + length_post;
741 std::sort(first_post, last_post);
746 size_t current_set = start;
747 size_t value_set =
end_;
749 { current_set = start + 2;
750 value_set =
data_[current_set];
754 size_t* current_post = first_post;
755 size_t value_post = *current_post;
758 while( subset & (value_post !=
end_) )
759 {
while( value_set < value_post )
760 value_set =
data_[++current_set];
761 if( value_post < value_set )
765 if( current_post == last_post )
768 value_post = *current_post;
776 size_t number_lost = capacity_post + 2;
785 size_t number_lost =
drop(i);
790 data_[start_new] = 1;
797 { current_set = start + 2;
798 value_set =
data_[current_set];
802 current_post = first_post;
803 value_post = *current_post;
806 while( (value_set <
end_) | (current_post != last_post ) )
807 {
if( value_set == value_post )
810 value_set =
data_[current_set];
814 if( value_set < value_post )
821 value_set =
data_[current_set];
830 size_t value_previous = value_post;
831 while( value_post == value_previous )
833 if( current_post == last_post )
836 value_post = *current_post;
845 size_t length_new =
data_.
size() - (start_new + 3);
846 data_[start_new + 1] = length_new;
852 number_lost += capacity_post + 2;
882 data_[start + 1] = 1;
883 data_[start + 2] = element;
888 size_t number_lost =
drop(i);
891 size_t length =
data_[start + 1];
893 data_[new_start] = 1;
894 data_[new_start + 1] = length + 1;
897 size_t value =
data_[start + 2 + count];
899 while( value < element)
902 value =
data_[start + 2 + count];
908 while( value <
end_ )
911 value =
data_[start + 2 + count];
943 size_t length =
data_[start + 1];
944 const size_t* first =
data_.
data() + start + 2;
945 const size_t* last = first + length;
947 {
bool result =
false;
948 while( last > first )
949 result |= *(--last) == element;
953 return std::binary_search(first, last, element);
969 size_t number_lost =
drop( target );
975 if(
post_[target] != 0 )
976 {
size_t capacity =
post_[target + 1];
977 number_lost += capacity + 2;
1005 size_t this_target ,
1006 size_t other_source ,
1015 if( (
this == &other) & (this_target == other_source) )
1019 size_t number_lost =
drop(this_target);
1022 size_t post =
post_[this_target];
1025 size_t capacity =
data_[post + 1];
1026 number_lost += capacity + 2;
1027 post_[this_target] = 0;
1031 size_t other_start = other.
start_[other_source];
1032 if(
this == &other )
1034 start_[this_target] = other_start;
1035 if( other_start != 0 )
1037 data_[other_start]++;
1040 else if( other_start == 0 )
1046 size_t length = other.
data_[other_start + 1];
1048 start_[this_target] = this_start;
1049 data_[this_start] = 1;
1050 data_[this_start + 1] = length;
1051 for(
size_t j = 0; j < length; ++j)
1082 size_t this_target ,
1084 size_t other_right ,
1095 size_t subset =
is_subset(this_left, other_right, other);
1098 if( subset == 2 || subset == 3 )
1104 {
assignment(this_target, other_right, other);
1113 size_t start_left =
start_[this_left];
1114 size_t start_right = other.
start_[other_right];
1117 size_t number_lost =
drop(this_target);
1120 size_t post =
post_[this_target];
1123 size_t capacity =
data_[post + 1];
1124 number_lost += capacity + 2;
1125 post_[this_target] = 0;
1130 start_[this_target] = start;
1136 size_t current_left = start_left + 2;
1137 size_t value_left =
data_[current_left];
1142 size_t current_right = start_right + 2;
1143 size_t value_right = other.
data_[current_right];
1148 while( (value_left <
end_) | (value_right <
end_) )
1149 {
if( value_left == value_right )
1152 value_right = other.
data_[current_right];
1154 if( value_left < value_right )
1158 value_left =
data_[current_left];
1165 value_right = other.
data_[current_right];
1173 size_t length =
data_.
size() - (start + 3);
1174 data_[start + 1] = length;
1202 size_t this_target ,
1204 size_t other_right ,
1215 size_t subset =
is_subset(this_left, other_right, other);
1218 if( subset == 1 || subset == 3 )
1224 {
assignment(this_target, other_right, other);
1233 size_t start_left =
start_[this_left];
1234 size_t start_right = other.
start_[other_right];
1238 size_t number_lost =
drop(this_target);
1241 size_t post =
post_[this_target];
1244 size_t capacity =
data_[post + 1];
1245 number_lost += capacity + 2;
1246 post_[this_target] = 0;
1251 start_[this_target] = start;
1255 size_t current_left = start_left + 2;
1256 size_t value_left =
data_[current_left];
1261 size_t current_right = start_right + 2;
1262 size_t value_right = other.
data_[current_right];
1265 while( (value_left <
end_) & (value_right <
end_) )
1266 {
if( value_left == value_right )
1270 start_[this_target] = start;
1278 value_left =
data_[current_left];
1280 if( value_left > value_right )
1283 value_right = other.
data_[current_right];
1285 if( value_right > value_left )
1288 value_left =
data_[current_left];
1294 size_t length =
data_.
size() - (start + 3);
1295 data_[start + 1] = length;
1330 void print(
void)
const;
1358 size_t start = vec_set.
start_[i];
1392 { std::cout <<
"sparse_sizevec:\n";
1393 for(
size_t i = 0; i <
n_set(); i++)
1394 { std::cout <<
"set[" << i <<
"] = {";
1396 while( *itr !=
end() )
1397 { std::cout << *itr;
1398 if( *(++itr) !=
end() )
1433 template<
class VectorSet>
1436 const VectorSet& user ,
1440 const char* error_msg )
1450 std::set<size_t>::const_iterator itr;
1453 internal.resize(n_set, end);
1457 for(
size_t j = 0; j < end; j++)
1458 { itr = user[j].begin();
1459 while(itr != user[j].end())
1460 {
size_t i = *itr++;
1462 internal.add_element(i, j);
1467 {
for(
size_t i = 0; i < n_set; i++)
1468 { itr = user[i].begin();
1469 while(itr != user[i].end())
1470 {
size_t j = *itr++;
1472 internal.add_element(i, j);
size_t memory(void) const
Amount of memory used by this vector of sets.
#define CPPAD_ASSERT_KNOWN(exp, msg)
Check that exp is true, if not print msg and terminate execution.
sparse_sizevec_const_iterator(const sparse_sizevec &vec_set, size_t i)
construct a const_iterator for a set in a sparse_sizevec object
size_t n_set(void) const
Fetch n_set for vector of sets object.
Define processor symbols and macros that are used by CppAD.
void binary_intersection(size_t this_target, size_t this_left, size_t other_right, const sparse_sizevec &other)
Assign a set equal to the intersection of two other sets.
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.
size_t extend(size_t n)
Increase the number of elements the end of this vector (existing elements are always preserved)...
void push_back(const Type &e)
Add an element to theh back of this vector.
void assignment(size_t this_target, size_t other_source, const sparse_sizevec &other)
Assign one set equal to another set.
sparse_sizevec_const_iterator & operator++(void)
advance to next element in this list
size_t reference_count(size_t i) const
Counts references to a set.
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;.
size_t data_index_
data index of next entry, zero for no more entries
size_t data_not_used_
number of elements in data_ that have been allocated and are no longer being used.
void print(void) const
Print the vector of sets (used for debugging)
cons_iterator for one set of positive integers in a sparse_sizevec object.
const size_t end_
Possible elements in a list are 0, 1, ..., end_ - 1;.
pod_vector< size_t > start_
Starting point for i-th set is start_[i].
size_t drop(size_t i)
drop a set.
void clear(size_t target)
Assign the empty set to one of the sets.
void collect_garbage(void)
Does garbage collection when indicated.
pod_vector< size_t > data_
The data for all the singly linked lists.
bool is_element(size_t i, size_t element) const
Check if an element is in a set.
pod_vector< size_t > post_
Vectors of elements that have not yet been added to corresponding sets.
const pod_vector< size_t > & data_
data for the entire vector of sets
void check_data_structure(void)
Checks data structure (effectively const, but modifies and restores values)
void post_element(size_t i, size_t element)
Post an element for delayed addition to a set.
size_t size(void) const
current number of elements in this vector.
sparse_sizevec_const_iterator const_iterator
declare a const iterator
void process_post(size_t i)
process post entries for a specific set.
sparse_sizevec(const sparse_sizevec &v)
Using copy constructor is a programing (not user) error.
void binary_union(size_t this_target, size_t this_left, size_t other_right, const sparse_sizevec &other)
Assign a set equal to the union of two other sets.
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.
size_t is_subset(size_t one_this, size_t two_other, const sparse_sizevec &other) const
Check if one of two sets is a subset of the other set.
void swap(pod_vector &other)
Swap all properties of this vector with another.
#define CPPAD_ASSERT_UNKNOWN(exp)
Check that exp is true, if not terminate execution.
sparse_sizevec(void)
Default constructor (no sets)
void operator=(const sparse_sizevec &other)
Assignement operator.
size_t operator*(void)
obtain value of this element of the set of positive integers (end_ for no such element) ...
void resize(size_t n_set, size_t end)
Start a new vector of sets.
size_t end(void) const
Fetch end for this vector of sets object.
size_t number_elements(size_t i) const
Return number of elements in a set.
Vector of sets of positive integers, each set stored as a size_t vector.
size_t capacity(void) const
current capacity (amount of allocated storage) for this vector.
~sparse_sizevec(void)
Destructor.
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;.
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.