CppAD: A C++ Algorithmic Differentiation Package  20171217
sparse_sizevec.hpp
Go to the documentation of this file.
3
4 /* --------------------------------------------------------------------------
6
8 the terms of the
9  Eclipse Public License Version 1.0.
10
11 A copy of this license is included in the COPYING file of this distribution.
13 -------------------------------------------------------------------------- */
16 # include <list>
17
19 /*!
20 \file sparse_sizevec.hpp
21 Vector of sets of positive integers stored as size_t vector
22 with the element values strictly increasing.
23 */
24 class sparse_sizevec_const_iterator;
25
26 // =========================================================================
27 /*!
28 Vector of sets of positive integers, each set stored as a size_t vector.
29
30 All the public members for this class are also in the
31 sparse_pack and sparse_list classes.
32 This defines the CppAD vector_of_sets concept.
33 */
36 private:
37  /// Possible elements in each set are 0, 1, ..., end_ - 1;
38  size_t end_;
39
40  /// number of elements in data_ that have been allocated
41  /// and are no longer being used.
43
44  /// The data for all the singly linked lists.
46
47  /*!
48  Starting point for i-th set is start_[i].
49
50  \li
51  If the i-th set has no elements, start_[i] is zero.
52  Othersize the conditions below hold.
53
54  \li
55  data_[ start_[i] ] is the reference count for this set
56
57  \li
58  data_[ start_[i] + 1 ] is the first element in this set.
59
60  \li
61  data_[ start_[i] + 2 ] is the first element in this set.
62
63  \li
64  data_[ start_[i] + 2 + n ] = end_ where n is the number of
65  elements in this set
66  */
68
69  /*!
70  Vectors of elements that have not yet been added to corresponding sets.
71
72  \li
73  If all the post_element calls for the i-th set have been added,
74  post_[i] is zero. Otherwise the conditions below hold.
75
76  \li
77  data_[ post_[i] ] the number of elements that have been posted,
78  but not yet added, to set i.
79
80  \li
81  data_[ post_[i] + 1 ] is the capacity for holding elements
82  which is greater than or equal the number of elements.
83
84  \li
85  data_[ post_[i] + 2 ] is the first element that has been posted,
86  but not yet added, to set i.
87
88  \li
89  data_[ post_[i] + 1 + n] is the last element that has been posted,
90  but not yet added, to set i.
91  Here n is the number of elements that are posted and not yet added
92  to set i.
93  */
95  // -----------------------------------------------------------------
96  /*!
97  Counts references to a set.
98
99  \param i
100  is the index of the set that we are counting the references to.
101
102  \return
103  if the set is empty, the return value is zero.
104  Otherwise it is the number of sets that share the same vector.
105  */
106  size_t reference_count(size_t i) const
107  { // start data index
108  size_t start = start_[i];
109  if( start == 0 )
110  return 0;
111  //
112  // reference count
113  return data_[start];
114  }
115  // -----------------------------------------------------------------
116  /*!
117  drop a set.
118
119  \param i
120  is the index of the set that will be dropped.
121
122  \par reference_count
123  if the set is non-empty,
124  the reference count corresponding to index will be decremented.
125
126  \return
127  is the number of elements of data_ that will be lost when the set is
128  dropped. This is non-zero when the initial reference count is one.
129  */
130  size_t drop(size_t i)
131  {
132  // reference count
133  size_t ref_count = reference_count(i);
134
135  // empty set case
136  if( ref_count == 0 )
137  return 0;
138
139  // start
140  size_t start = start_[i];
141  CPPAD_ASSERT_UNKNOWN( data_[start] == ref_count );
142
143  // decrement reference counter
144  data_[start]--;
145
146  // nothing lost unless new reference count is zero
147  if( ref_count != 1 )
148  return 0;
149
150  // number of elements in the set
151  size_t length = data_[start + 1];
152
153  // reference count, length, end marker, plus elements in set
154  size_t number_lost = 3 + length;
155
156  // number_lost
157  return number_lost;
158  }
159  // -----------------------------------------------------------------
160  /*!
161  Checks data structure
162  (effectively const, but modifies and restores values)
163  */
164 # ifdef NDEBUG
165  void check_data_structure(void)
166  { return; }
167 # else
169  { // number of sets
171  size_t n_set = start_.size();
172  if( n_set == 0 )
173  { CPPAD_ASSERT_UNKNOWN( end_ == 0 );
175  CPPAD_ASSERT_UNKNOWN( data_.size() == 0 );
176  CPPAD_ASSERT_UNKNOWN( start_.size() == 0 );
177  CPPAD_ASSERT_UNKNOWN( post_.size() == 0 );
178  return;
179  }
180  // ------------------------------------------------------------------
181  // save the reference counters
182  pod_vector<size_t> ref_count(n_set);
183  for(size_t i = 0; i < n_set; i++)
184  ref_count[i] = reference_count(i);
185  // ------------------------------------------------------------------
186
187  // ------------------------------------------------------------------
188  // count the number of entries in data_ that are used by sets
189  size_t data_used_by_sets = 0;
190  for(size_t i = 0; i < n_set; i++)
191  { size_t start = start_[i];
192  if( start > 0 )
193  { // check structure for this non-empty set
194  size_t reference_count = data_[start + 0];
195  size_t length = data_[start + 1];
196  size_t first = data_[start + 2];
197  size_t last = data_[start + 2 + length];
198  CPPAD_ASSERT_UNKNOWN( reference_count > 0 );
199  CPPAD_ASSERT_UNKNOWN( length > 0 );
202  //
203  // decrement the reference counter
204  data_[start]--;
205  //
206  // count the entries when find last reference
207  if( data_[start] == 0 )
208  {
209  // restore reference count
210  data_[start] = ref_count[i];
211
212  // number of data_ entries used for this set
213  data_used_by_sets += number_elements(i) + 3;
214  }
215  }
216  }
217  // ------------------------------------------------------------------
218  // count the number of entries in data_ that are used by posts
219  size_t data_used_by_posts = 0;
220  for(size_t i = 0; i < n_set; i++)
221  { size_t post = post_[i];
222  if( post > 0 )
223  { CPPAD_ASSERT_UNKNOWN( data_[post] > 0 );
224  CPPAD_ASSERT_UNKNOWN( data_[post + 1] > 0 );
225  CPPAD_ASSERT_UNKNOWN( data_[post + 2] < end_ );
226  //
227  size_t capacity = data_[post + 1];
228  data_used_by_posts += capacity + 2;
229  }
230  }
231  // ------------------------------------------------------------------
232  size_t data_used = data_used_by_sets + data_used_by_posts;
234  data_used + data_not_used_ == data_.size()
235  );
236  return;
237  }
238 # endif
239  // -----------------------------------------------------------------
240  /*!
241  Check if one of two sets is a subset of the other set
242
243  \param one_this
244  is the index in this sparse_sizevec object of the first set.
245
246  \param two_other
247  is the index in other sparse_sizevec object of the second set.
248
249  \param other
250  is the other sparse_sizevec object which may be the same as this object.
251
252  \return
253  If zero, niether set is a subset of the other.
254  If one, then one is a subset of two and they are not equal.
255  If two, then two is a subset of one and they are not equal.
256  If three, then the sets are equal.
257  */
258  size_t is_subset(
259  size_t one_this ,
260  size_t two_other ,
261  const sparse_sizevec& other ) const
262  {
263  CPPAD_ASSERT_UNKNOWN( one_this < start_.size() );
264  CPPAD_ASSERT_UNKNOWN( two_other < other.start_.size() );
265  CPPAD_ASSERT_UNKNOWN( end_ == other.end_ );
266  //
267  // start
268  size_t start_one = start_[one_this];
269  size_t start_two = other.start_[two_other];
270  //
271  if( start_one == 0 )
272  { // set one is empty
273  if( start_two == 0 )
274  { // set two is empty
275  return 3;
276  }
277  // set one is empty and two is not empty
278  return 1;
279  }
280  if( start_two == 0 )
281  { // set two is empty and one is not empty
282  return 2;
283  }
284  //
285  // data index
286  size_t index_one = start_one + 2;
287  size_t index_two = start_two + 2;
288  //
289  // value
290  size_t value_one = data_[index_one];
291  size_t value_two = other.data_[index_two];
292  //
293  bool one_subset = true;
294  bool two_subset = true;
295  //
296  size_t value_union = std::min(value_one, value_two);
297  while( (one_subset | two_subset) & (value_union < end_) )
298  { //
299  if( value_one > value_union )
300  two_subset = false;
301  else
302  { // value_one <= value_two and value_one < end_
303  value_one = data_[++index_one];
304  }
305  //
306  if( value_two > value_union )
307  one_subset = false;
308  else
309  { // value_two <= value_one and value_two < end_
310  value_two = other.data_[++index_two];
311  }
312  value_union = std::min(value_one, value_two);
313  }
314  if( one_subset )
315  { if( two_subset )
316  { // sets are equal
317  return 3;
318  }
319  // one is a subset of two
320  return 1;
321  }
322  if( two_subset )
323  { // two is a subset of one
324  return 2;
325  }
326  //
327  // neither is a subset
328  return 0;
329  }
330  // -----------------------------------------------------------------
331  /*!
332  Does garbage collection when indicated.
333
334  This routine should be called when more entries are not being used.
335  If a significant propotion are not being used, the data structure
336  will be compacted.
337
338  The size of data_ should equal the number of entries used by the sets
339  plus the number of entries that are not being used data_not_used_.
340  Note that data_[0] never gets used.
341  */
342  void collect_garbage(void)
343  { if( data_not_used_ < data_.size() / 2 + 100)
344  return;
346  //
347  // number of sets including empty ones
348  size_t n_set = start_.size();
349  //
350  // use temporary to hold copy of data_ and start_
351  pod_vector<size_t> data_tmp(1); // data_tmp[0] will not be used
352  pod_vector<size_t> start_tmp(n_set);
353  //
354  for(size_t i = 0; i < n_set; i++)
355  { size_t start = start_[i];
356  if( start == 0 )
357  start_tmp[i] = 0;
358  else
359  { // check if this set has already been copied
360  if( data_[start] == 0 )
361  { // starting address in data_tmp has been stored here
362  start_tmp[i] = data_[start + 1];
363  }
364  else
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];
369  //
370  for(size_t j = 2; data_[start + j] != end_; ++j)
371  data_tmp.push_back( data_[start + j] );
372  data_tmp.push_back(end_);
373  //
374  // flag that indicates this set already copied
375  data_[start] = 0;
376  //
377  // store the starting address here
378  data_[start + 1] = tmp_start;
379  }
380  }
381  }
382
383  // swap the tmp and old data vectors
384  start_.swap(start_tmp);
385  data_.swap(data_tmp);
386
387  // all of the elements, except the first, are used
388  data_not_used_ = 1;
389  }
390  // -----------------------------------------------------------------
391  /*!
392  Assign a set equal to the union of a set and a vector;
393
394  \param target
395  is the index in this sparse_sizevec object of the set being assinged.
396
397  \param left
398  is the index in this sparse_sizevec object of the
399  left operand for the union operation.
400  It is OK for target and left to be the same value.
401
402  \param right
403  is a vector of size_t, sorted in accending order.
404  right operand for the union operation.
405  Elements can be repeated in right, but are not be repeated in the
406  resulting set.
407  All of the elements must have value less than end();
408  */
410  size_t target ,
411  size_t left ,
412  const pod_vector<size_t>& right )
413  { CPPAD_ASSERT_UNKNOWN( post_[left] == 0 );
414  //
415  CPPAD_ASSERT_UNKNOWN( target < start_.size() );
416  CPPAD_ASSERT_UNKNOWN( left < start_.size() );
417
418  size_t start_left = start_[left];
419  // -------------------------------------------------------------------
420  // Check if right is a subset of left so that we used reference count
421  // and not make copies of identical sets.
422  //
423  // initialize index for left and right sets
424  size_t current_left = start_left;
425  size_t current_right = 0;
426  //
427  // initialize value_left
428  size_t value_left = end_;
429  if( current_left > 0 )
430  { // advance from reference counter to data
431  current_left = current_left + 2;
432  value_left = data_[current_left];
434  }
435  //
436  // initialize value_right
437  size_t value_right = end_;
438  if( right.size() > 0 )
439  value_right = right[current_right];
440  //
441  bool subset = true;
442  while( subset & (value_right < end_) )
443  { while( value_left < value_right )
445  value_left = data_[++current_left];
446  }
447  if( value_right < value_left )
448  subset = false;
449  else
451  ++current_right;
452  if( current_right == right.size() )
453  value_right = end_;
454  else
455  value_right = right[current_right];
456  }
457  }
458  //
459  if( subset )
460  { // target = left will use reference count for identical sets
461  assignment(target, left, *this);
462  return;
463  }
464
465  // -------------------------------------------------------------------
466  // number of elements that will be deleted by removing old version
467  // of target
468  size_t number_lost = drop(target);
469
470  // drop any posting for the target set
471  size_t post = post_[target];
472  if( post > 0 )
473  { CPPAD_ASSERT_UNKNOWN( target != left );
474  size_t capacity = data_[post + 1];
475  number_lost += capacity + 2;
476  post_[target] = 0;
477  }
478  //
479  // start new version of target
480  size_t start = data_.extend(2);
481  start_[target] = start;
482  data_[start] = 1; // reference count
483  // data_[start + 1] = length is not yet known
484  //
485  // initialize value_left
486  current_left = start_left;
487  value_left = end_;
488  if( current_left > 0 )
489  { // advance from reference counter to data
490  current_left = current_left + 2;
491  value_left = data_[current_left];
493  }
494  //
495  // initialize value_right
496  value_right = end_;
497  if( right.size() > 0 )
498  value_right = right[current_right];
499  //
500  // merge
501  while( (value_left < end_) | (value_right < end_) )
502  { if( value_left == value_right)
503  { // advance left so left and right are no longer equal
504  ++current_left;
505  value_left = data_[current_left];
506  CPPAD_ASSERT_UNKNOWN( value_right < value_left );
507  }
508  //
509  if( value_left < value_right )
510  { // value_left case
511  CPPAD_ASSERT_UNKNOWN( value_left < end_ );
512  data_.push_back( value_left );
513  //
515  ++current_left;
516  value_left = data_[current_left];
517  }
518  else
519  { CPPAD_ASSERT_UNKNOWN( value_right < value_left )
520  // value_right case
522  data_.push_back( value_right );
523  //
524  // advance right (skip values equal to this one)
525  size_t previous_value = value_right;
526  while( value_right == previous_value )
527  { ++current_right;
528  if( current_right == right.size() )
529  value_right = end_;
530  else
531  { value_right = right[current_right];
532  CPPAD_ASSERT_UNKNOWN( value_right < end_ );
533  }
534  }
535  }
536  }
537  // make end of target list
538  data_.push_back( end_ );
539  //
540  // reference count, length, and end_ are not elements of set
541  CPPAD_ASSERT_UNKNOWN( data_.size() > start + 3 );
542  size_t length = data_.size() - (start + 3);
543  data_[start + 1] = length;
544  //
545
547  data_not_used_ += number_lost;
548  collect_garbage();
549  }
550 public:
551  /// declare a const iterator
553  // -----------------------------------------------------------------
554  /*!
555  Default constructor (no sets)
556  */
558  end_(0) ,
559  data_not_used_(0) ,
560  data_(0) ,
561  start_(0) ,
562  post_(0)
563  { }
564  // -----------------------------------------------------------------
565  /// Destructor
568  }
569  // -----------------------------------------------------------------
570  /*!
571  Using copy constructor is a programing (not user) error
572
573  \param v
574  vector of sets that we are attempting to make a copy of.
575  */
577  { // Error: Probably a sparse_sizevec argument has been passed by value
579  }
580  // -----------------------------------------------------------------
581  /*!
582  Assignement operator.
583
584  \param other
585  this sparse_sizevec with be set to a deep copy of other.
586  */
587  void operator=(const sparse_sizevec& other)
588  { end_ = other.end_;
590  data_ = other.data_;
591  start_ = other.start_;
592  post_ = other.post_;
593  }
594  // -----------------------------------------------------------------
595  /*!
596  Start a new vector of sets.
597
598  \param n_set
599  is the number of sets in this vector of sets.
600  \li
601  If n_set is zero, any memory currently allocated for this object
602  is freed.
603  \li
604  If n_set is non-zero, a vector of n_set sets is created and all
605  the sets are initilaized as empty.
606
607  \param end
608  is the maximum element plus one (the minimum element is 0).
609  If n_set is zero, end must also be zero.
610  */
611  void resize(size_t n_set, size_t end)
613
614  if( n_set == 0 )
615  { CPPAD_ASSERT_UNKNOWN(end == 0 );
616  //
617  // restore object to start after constructor
618  // (no memory allocated for this object)
619  data_.clear();
620  start_.clear();
621  post_.clear();
622  data_not_used_ = 0;
623  end_ = 0;
624  //
625  return;
626  }
627  end_ = end;
628  //
629  start_.resize(n_set);
630  post_.resize(n_set);
631  for(size_t i = 0; i < n_set; i++)
632  { start_[i] = 0;
633  post_[i] = 0;
634  }
635  //
636  data_.resize(1); // first element is not used
637  data_not_used_ = 1;
638  }
639  // -----------------------------------------------------------------
640  /*!
641  Return number of elements in a set.
642
643  \param i
644  is the index of the set we are checking number of the elements of.
645  */
646  size_t number_elements(size_t i) const
647  { CPPAD_ASSERT_UNKNOWN( post_[i] == 0 );
648  //
649  size_t start = start_[i];
650  if( start == 0 )
651  return 0;
652  return data_[start + 1];
653  }
654  // ------------------------------------------------------------------
655  /*!
656  Post an element for delayed addition to a set.
657
658  \param i
659  is the index for this set in the vector of sets.
660
661  \param element
662  is the value of the element that we are posting.
663  The same element may be posted multiple times.
664
665  \par
666  It is faster to post multiple elements to set i and then call
667  process_post(i) then to add each element individually.
668  It is an error to call any member function,
669  that depends on the value of set i,
670  before processing the posts to set i.
671  */
672  void post_element(size_t i, size_t element)
673  { CPPAD_ASSERT_UNKNOWN( i < start_.size() );
674  CPPAD_ASSERT_UNKNOWN( element < end_ );
675
676  size_t post = post_[i];
677  if( post == 0 )
678  { // minimum capacity for an post vector
679  size_t min_capacity = 10;
680  size_t post_new = data_.extend(min_capacity + 2);
681  data_[post_new] = 1; // length
682  data_[post_new + 1] = min_capacity; // capacity
683  data_[post_new + 2] = element;
684  post_[i] = post_new;
685  }
686  else
687  { size_t length = data_[post];
688  size_t capacity = data_[post + 1];
689  if( length == capacity )
690  {
691  size_t post_new = data_.extend( 2 * capacity );
692  //
693  data_[post_new] = length + 1;
694  data_[post_new + 1] = 2 * capacity;
695  //
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;
699  //
700  post_[i] = post_new;
701  size_t number_lost = length + 2;
702  data_not_used_ += number_lost;
703  }
704  else
705  { data_[post] = length + 1;
706  data_[post + 2 + length] = element;
707  }
708  }
709
710  // check amount of data_not_used_
711  collect_garbage();
712
713  return;
714  }
715  // -----------------------------------------------------------------
716  /*!
717  process post entries for a specific set.
718
719  \param i
720  index of the set for which we are processing the post entries.
721
722  \par post_
723  Upon call, post_[i] is location in data_ of the elements that get
724  added to the i-th set. Upon return, post_[i] is zero.
725  */
726  void process_post(size_t i)
727  { // start
728  size_t start = start_[i];
729  // post
730  size_t post = post_[i];
731  //
732  // check if there are no elements to process
733  if( post == 0 )
734  return;
735  //
736  // sort the elements that need to be processed
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);
742  // -------------------------------------------------------------------
743  // check if posted elements are a subset of set
744  //
745  // first element of the set
746  size_t current_set = start;
747  size_t value_set = end_;
748  if( start > 0 )
749  { current_set = start + 2;
750  value_set = data_[current_set];
751  }
752  //
753  // first element to post
754  size_t* current_post = first_post;
755  size_t value_post = *current_post;
756  //
757  bool subset = true;
758  while( subset & (value_post != end_) )
759  { while( value_set < value_post )
760  value_set = data_[++current_set];
761  if( value_post < value_set )
762  subset = false;
763  else
764  { ++current_post;
765  if( current_post == last_post )
766  value_post = end_;
767  else
768  value_post = *current_post;
769  }
770  }
771  //
772  if( subset )
773  { // drop the post_ elements
774  post_[i] = 0;
775  //
776  size_t number_lost = capacity_post + 2;
777  data_not_used_ += number_lost;
778  collect_garbage();
779  //
780  // nothing else to do
781  return;
782  }
783  // -------------------------------------------------------------------
784  // number of element that will be lost by removing old i-th set
785  size_t number_lost = drop(i);
786
787  // start new version of i-th set
788  size_t start_new = data_.extend(2);
789  start_[i] = start_new;
790  data_[start_new] = 1; // reference count
791  // data[start_new + 1] = length_new is not yet known
792  //
793  // first element of the set
794  current_set = start;
795  value_set = end_;
796  if( start > 0 )
797  { current_set = start + 2;
798  value_set = data_[current_set];
799  }
800  //
801  // first element to process
802  current_post = first_post;
803  value_post = *current_post;
804  //
805  // merge
806  while( (value_set < end_) | (current_post != last_post ) )
807  { if( value_set == value_post )
808  { // advance left so left and right are no longer equal
809  ++current_set;
810  value_set = data_[current_set];
811  CPPAD_ASSERT_UNKNOWN( value_post < value_set );
812  }
813  //
814  if( value_set < value_post )
816  CPPAD_ASSERT_UNKNOWN( value_set < end_ );
817  data_.push_back( value_set );
818  //
820  ++current_set;
821  value_set = data_[current_set];
822  }
823  else
824  { CPPAD_ASSERT_UNKNOWN( value_post < value_set )
827  data_.push_back( value_post );
828  //
829  // advance post (skip values equal to this one)
830  size_t value_previous = value_post;
831  while( value_post == value_previous )
832  { ++current_post;
833  if( current_post == last_post )
834  value_post = end_;
835  else
836  value_post = *current_post;
837  }
838  }
839  }
840  // make end of target list
841  data_.push_back( end_ );
842  //
843  // reference count, length, and end_ are not elements of set
844  CPPAD_ASSERT_UNKNOWN( data_.size() > start_new + 3 );
845  size_t length_new = data_.size() - (start_new + 3);
846  data_[start_new + 1] = length_new;
847  CPPAD_ASSERT_UNKNOWN( data_[start_new + length_new + 2] == end_ );
848  //
849  // drop to post_ elements for this set
850  post_[i] = 0;
851  //
852  number_lost += capacity_post + 2;
853  data_not_used_ += number_lost;
854  collect_garbage();
855  //
856  return;
857  }
858  // -----------------------------------------------------------------
859  /*!
860  Add one element to a set.
861
862  \param i
863  is the index for this set in the vector of sets.
864
865  \param element
866  is the element we are adding to the set.
867  */
868  void add_element(size_t i, size_t element)
869  { CPPAD_ASSERT_UNKNOWN( i < start_.size() );
870  CPPAD_ASSERT_UNKNOWN( element < end_ );
871
872  // check if element is already in the set
873  if( is_element(i, element) )
874  return;
875
876  // check for case where old set is empty
877  size_t start = start_[i];
878  if( start == 0 )
879  { start = data_.extend(4);
880  start_[i] = start;
881  data_[start] = 1; // reference count
882  data_[start + 1] = 1; // length
883  data_[start + 2] = element; // the element
884  data_[start + 3] = end_; // end marker
885  return;
886  }
887  //
888  size_t number_lost = drop(i);
889  //
890  // start of new set
891  size_t length = data_[start + 1];
892  size_t new_start = data_.extend(2);
893  data_[new_start] = 1; // reference count
894  data_[new_start + 1] = length + 1; // new length
895  //
896  size_t count = 0;
897  size_t value = data_[start + 2 + count];
898  // before new element
899  while( value < element)
900  { data_.push_back( value );
901  ++count;
902  value = data_[start + 2 + count];
903  }
904  CPPAD_ASSERT_UNKNOWN( element < value )
905  // new element
906  data_.push_back( element );
907  // after new element
908  while( value < end_ )
909  { data_.push_back( value );
910  ++count;
911  value = data_[start + 2 + count];
912  }
913  data_.push_back( end_ );
914
915  //
916  // connect up new set
917  start_[i] = new_start;
918
920  data_not_used_ += number_lost;
921  collect_garbage();
922  //
923  return;
924  }
925  // -----------------------------------------------------------------
926  /*!
927  Check if an element is in a set.
928
929  \param i
930  is the index for this set in the vector of sets.
931
932  \param element
933  is the element we are checking to see if it is in the set.
934  */
935  bool is_element(size_t i, size_t element) const
936  { CPPAD_ASSERT_UNKNOWN( post_[i] == 0 );
937  CPPAD_ASSERT_UNKNOWN( element < end_ );
938  //
939  size_t start = start_[i];
940  if( start == 0 )
941  return false;
942  //
943  size_t length = data_[start + 1];
944  const size_t* first = data_.data() + start + 2;
945  const size_t* last = first + length;
946  if( length < 10 )
947  { bool result = false;
948  while( last > first )
949  result |= *(--last) == element;
950  return result;
951  }
952  //
953  return std::binary_search(first, last, element);
954  }
955  // -----------------------------------------------------------------
956  /*!
957  Assign the empty set to one of the sets.
958
959  \param target
960  is the index of the set we are setting to the empty set.
961
962  \par data_not_used_
963  increments this value by number of data_ elements that are lost
965  */
966  void clear(size_t target)
967  {
968  // number of data_ elements used for this set
969  size_t number_lost = drop( target );
970
971  // set target to empty set
972  start_[target] = 0;
973
974  // drop the posted elements
975  if( post_[target] != 0 )
976  { size_t capacity = post_[target + 1];
977  number_lost += capacity + 2;
978  //
979  post_[target] = 0;
980  }
981
983  data_not_used_ += number_lost;
984  collect_garbage();
985  }
986  // -----------------------------------------------------------------
987  /*!
988  Assign one set equal to another set.
989
990  \param this_target
991  is the index in this sparse_sizevec object of the set being assinged.
992
993  \param other_source
994  is the index in the other \c sparse_sizevec object of the
995  set that we are using as the value to assign to the target set.
996
997  \param other
998  is the other sparse_sizevec object (which may be the same as this
999  sparse_sizevec object). This must have the same value for end_.
1000
1001  \par data_not_used_
1002  increments this value by number of elements lost.
1003  */
1005  size_t this_target ,
1006  size_t other_source ,
1007  const sparse_sizevec& other )
1008  { CPPAD_ASSERT_UNKNOWN( other.post_[ other_source ] == 0 );
1009  //
1010  CPPAD_ASSERT_UNKNOWN( this_target < start_.size() );
1011  CPPAD_ASSERT_UNKNOWN( other_source < other.start_.size() );
1012  CPPAD_ASSERT_UNKNOWN( end_ == other.end_ );
1013
1014  // check if we are assigning a set to itself
1015  if( (this == &other) & (this_target == other_source) )
1016  return;
1017
1018  // number of elements that will be deleted by this operation
1019  size_t number_lost = drop(this_target);
1020
1021  // drop any posting for the target set
1022  size_t post = post_[this_target];
1023  if( post > 0 )
1024  { // do not need to worry about target being same as source
1025  size_t capacity = data_[post + 1];
1026  number_lost += capacity + 2;
1027  post_[this_target] = 0;
1028  }
1029
1030  // If this and other are the same, use another reference to same list
1031  size_t other_start = other.start_[other_source];
1032  if( this == &other )
1033  { CPPAD_ASSERT_UNKNOWN( this_target != other_source );
1034  start_[this_target] = other_start;
1035  if( other_start != 0 )
1036  { // increment reference count
1037  data_[other_start]++;
1038  }
1039  }
1040  else if( other_start == 0 )
1041  { // the target list is empty
1042  start_[this_target] = 0;
1043  }
1044  else
1045  { // make a copy of the other list in this sparse_sizevec
1046  size_t length = other.data_[other_start + 1];
1047  size_t this_start = data_.extend(2);
1048  start_[this_target] = this_start;
1049  data_[this_start] = 1; // reference count
1050  data_[this_start + 1] = length; // length
1051  for(size_t j = 0; j < length; ++j)
1052  data_.push_back( other.data_[other_start + 2 + j] );
1053  data_.push_back(end_);
1054  }
1055
1057  data_not_used_ += number_lost;
1058  collect_garbage();
1059  }
1060  // -----------------------------------------------------------------
1061  /*!
1062  Assign a set equal to the union of two other sets.
1063
1064  \param this_target
1065  is the index in this sparse_sizevec object of the set being assinged.
1066
1067  \param this_left
1068  is the index in this sparse_sizevec object of the
1069  left operand for the union operation.
1070  It is OK for this_target and this_left to be the same value.
1071
1072  \param other_right
1073  is the index in the other sparse_sizevec object of the
1074  right operand for the union operation.
1075  It is OK for this_target and other_right to be the same value.
1076
1077  \param other
1078  is the other sparse_sizevec object (which may be the same as this
1079  sparse_sizevec object).
1080  */
1082  size_t this_target ,
1083  size_t this_left ,
1084  size_t other_right ,
1085  const sparse_sizevec& other )
1086  { CPPAD_ASSERT_UNKNOWN( post_[this_left] == 0 );
1087  CPPAD_ASSERT_UNKNOWN( other.post_[ other_right ] == 0 );
1088  //
1089  CPPAD_ASSERT_UNKNOWN( this_target < start_.size() );
1090  CPPAD_ASSERT_UNKNOWN( this_left < start_.size() );
1091  CPPAD_ASSERT_UNKNOWN( other_right < other.start_.size() );
1092  CPPAD_ASSERT_UNKNOWN( end_ == other.end_ );
1093
1094  // check if one of the two operands is a subset of the the other
1095  size_t subset = is_subset(this_left, other_right, other);
1096
1097  // case where right is a subset of left or right and left are equal
1098  if( subset == 2 || subset == 3 )
1099  { assignment(this_target, this_left, *this);
1100  return;
1101  }
1102  // case where the left is a subset of right and they are not equal
1103  if( subset == 1 )
1104  { assignment(this_target, other_right, other);
1105  return;
1106  }
1107  // if niether case holds, then both left and right are non-empty
1108  CPPAD_ASSERT_UNKNOWN( reference_count(this_left) > 0 );
1109  CPPAD_ASSERT_UNKNOWN( other.reference_count(other_right) > 0 );
1110
1111  // must get all the start indices before modify start_this
1112  // (incase start_this is the same as start_left or start_right)
1113  size_t start_left = start_[this_left];
1114  size_t start_right = other.start_[other_right];
1115
1116  // number of list elements that will be deleted by this operation
1117  size_t number_lost = drop(this_target);
1118
1119  // drop any posting for the target set
1120  size_t post = post_[this_target];
1121  if( post > 0 )
1122  { // do not need to worry about target being same as left or right
1123  size_t capacity = data_[post + 1];
1124  number_lost += capacity + 2;
1125  post_[this_target] = 0;
1126  }
1127
1128  // start the new list
1129  size_t start = data_.extend(2);
1130  start_[this_target] = start;
1131  data_[start] = 1; // reference count
1132  // data_[start + 1] = length is not yet known
1133
1134  // initilaize left
1135  CPPAD_ASSERT_UNKNOWN( start_left != 0 );
1136  size_t current_left = start_left + 2;
1137  size_t value_left = data_[current_left];
1138  CPPAD_ASSERT_UNKNOWN( value_left < end_ );
1139
1140  // initilaize right
1141  CPPAD_ASSERT_UNKNOWN( start_right != 0 );
1142  size_t current_right = start_right + 2;
1143  size_t value_right = other.data_[current_right];
1144  CPPAD_ASSERT_UNKNOWN( value_right < end_ );
1145
1146
1147  CPPAD_ASSERT_UNKNOWN( value_left < end_ && value_right < end_ );
1148  while( (value_left < end_) | (value_right < end_) )
1149  { if( value_left == value_right )
1150  { // advance right so left and right are no longer equal
1151  ++current_right;
1152  value_right = other.data_[current_right];
1153  }
1154  if( value_left < value_right )
1155  { data_.push_back( value_left );
1156  // advance left to its next element
1157  ++current_left;
1158  value_left = data_[current_left];
1159  }
1160  else
1161  { CPPAD_ASSERT_UNKNOWN( value_right < value_left )
1162  data_.push_back( value_right );
1163  // advance right to its next element
1164  ++current_right;
1165  value_right = other.data_[current_right];
1166  }
1167  }
1168  // make end of target list
1169  data_.push_back( end_ );
1170  //
1171  // reference count, length, and end_ are not elements of set
1172  CPPAD_ASSERT_UNKNOWN( data_.size() > start + 3 );
1173  size_t length = data_.size() - (start + 3);
1174  data_[start + 1] = length;
1175
1177  data_not_used_ += number_lost;
1178  collect_garbage();
1179  }
1180  // -----------------------------------------------------------------
1181  /*!
1182  Assign a set equal to the intersection of two other sets.
1183
1184  \param this_target
1185  is the index in this sparse_sizevec object of the set being assinged.
1186
1187  \param this_left
1188  is the index in this sparse_sizevec object of the
1189  left operand for the intersection operation.
1190  It is OK for this_target and this_left to be the same value.
1191
1192  \param other_right
1193  is the index in the other sparse_sizevec object of the
1194  right operand for the intersection operation.
1195  It is OK for this_target and other_right to be the same value.
1196
1197  \param other
1198  is the other sparse_sizevec object (which may be the same as this
1199  sparse_sizevec object).
1200  */
1202  size_t this_target ,
1203  size_t this_left ,
1204  size_t other_right ,
1205  const sparse_sizevec& other )
1206  { CPPAD_ASSERT_UNKNOWN( post_[this_left] == 0 );
1207  CPPAD_ASSERT_UNKNOWN( other.post_[ other_right ] == 0 );
1208  //
1209  CPPAD_ASSERT_UNKNOWN( this_target < start_.size() );
1210  CPPAD_ASSERT_UNKNOWN( this_left < start_.size() );
1211  CPPAD_ASSERT_UNKNOWN( other_right < other.start_.size() );
1212  CPPAD_ASSERT_UNKNOWN( end_ == other.end_ );
1213  //
1214  // check if one of the two operands is a subset of the the other
1215  size_t subset = is_subset(this_left, other_right, other);
1216
1217  // case where left is a subset of right or left and right are equal
1218  if( subset == 1 || subset == 3 )
1219  { assignment(this_target, this_left, *this);
1220  return;
1221  }
1222  // case where the right is a subset of left and they are not equal
1223  if( subset == 2 )
1224  { assignment(this_target, other_right, other);
1225  return;
1226  }
1227  // if niether case holds, then both left and right are non-empty
1228  CPPAD_ASSERT_UNKNOWN( reference_count(this_left) > 0 );
1229  CPPAD_ASSERT_UNKNOWN( other.reference_count(other_right) > 0 );
1230
1231  // must get all the start indices before modify start_this
1232  // (incase start_this is the same as start_left or start_right)
1233  size_t start_left = start_[this_left];
1234  size_t start_right = other.start_[other_right];
1235
1236
1237  // number of list elements that will be deleted by this operation
1238  size_t number_lost = drop(this_target);
1239
1240  // drop any posting for the target set
1241  size_t post = post_[this_target];
1242  if( post > 0 )
1243  { // do not need to worry about target being same as left or right
1244  size_t capacity = data_[post + 1];
1245  number_lost += capacity + 2;
1246  post_[this_target] = 0;
1247  }
1248
1249  // initialize intersection as empty
1250  size_t start = 0;
1251  start_[this_target] = start;
1252
1253  // initilaize left
1254  CPPAD_ASSERT_UNKNOWN( start_left != 0 );
1255  size_t current_left = start_left + 2;
1256  size_t value_left = data_[current_left];
1257  CPPAD_ASSERT_UNKNOWN( value_left < end_ );
1258
1259  // initilaize right
1260  CPPAD_ASSERT_UNKNOWN( start_right != 0 );
1261  size_t current_right = start_right + 2;
1262  size_t value_right = other.data_[current_right];
1263  CPPAD_ASSERT_UNKNOWN( value_right < end_ );
1264
1265  while( (value_left < end_) & (value_right < end_) )
1266  { if( value_left == value_right )
1267  { if( start == 0 )
1268  { // this is the first element in the intersection
1269  start = data_.extend(2);
1270  start_[this_target] = start;
1271  data_[start] = 1; // reference count
1272  // data_[start + 1] = length is not yet known
1273  }
1274  data_.push_back( value_left );
1275  //
1276  // advance left to its next element
1277  ++current_left;
1278  value_left = data_[current_left];
1279  }
1280  if( value_left > value_right )
1282  ++current_right;
1283  value_right = other.data_[current_right];
1284  }
1285  if( value_right > value_left )
1287  ++current_left;
1288  value_left = data_[current_left];
1289  }
1290  }
1291  if( start != 0 )
1292  { data_.push_back(end_);
1293  CPPAD_ASSERT_UNKNOWN( data_.size() > start + 3 );
1294  size_t length = data_.size() - (start + 3);
1295  data_[start + 1] = length;
1296  }
1297
1299  data_not_used_ += number_lost;
1300  collect_garbage();
1301  }
1302  // -----------------------------------------------------------------
1303  /*! Fetch n_set for vector of sets object.
1304
1305  \return
1306  Number of from sets for this vector of sets object
1307  */
1308  size_t n_set(void) const
1309  { return start_.size(); }
1310  // -----------------------------------------------------------------
1311  /*! Fetch end for this vector of sets object.
1312
1313  \return
1314  is the maximum element value plus one (the minimum element value is 0).
1315  */
1316  size_t end(void) const
1317  { return end_; }
1318  // -----------------------------------------------------------------
1319  /*! Amount of memory used by this vector of sets
1320
1321  \return
1322  The amount of memory in units of type unsigned char memory.
1323  */
1324  size_t memory(void) const
1325  { return data_.capacity() * sizeof(size_t);
1326  }
1327  /*!
1328  Print the vector of sets (used for debugging)
1329  */
1330  void print(void) const;
1331 };
1332 // =========================================================================
1333 /*!
1334 cons_iterator for one set of positive integers in a sparse_sizevec object.
1335
1336 All the public member functions for this class are also in the
1337 sparse_pack_const_iterator and sparse_list_const_iterator classes.
1338 This defines the CppAD vector_of_sets iterator concept.
1339 */
1341 private:
1342  /// data for the entire vector of sets
1344
1345  /// Possible elements in a list are 0, 1, ..., end_ - 1;
1346  const size_t end_;
1347
1348  /// data index of next entry, zero for no more entries
1349  size_t data_index_;
1350 public:
1351  /// construct a const_iterator for a set in a sparse_sizevec object
1353  :
1354  data_( vec_set.data_ ) ,
1355  end_ ( vec_set.end_ )
1356  { CPPAD_ASSERT_UNKNOWN( vec_set.post_[i] == 0 );
1357  //
1358  size_t start = vec_set.start_[i];
1359  if( start == 0 )
1360  { data_index_ = 0;
1361  }
1362  else
1363  { // data index of the first element in the set
1364  data_index_ = start + 2;
1366  }
1367  }
1368
1369  /// advance to next element in this list
1371  { if( data_index_ != 0 )
1372  { ++data_index_;
1373  if( data_[data_index_] == end_ )
1374  data_index_ = 0;
1375  }
1376  return *this;
1377  }
1378
1379  /// obtain value of this element of the set of positive integers
1380  /// (end_ for no such element)
1381  size_t operator*(void)
1382  { if( data_index_ == 0 )
1383  return end_;
1384  return data_[data_index_];
1385  }
1386 };
1387 // =========================================================================
1388 /*!
1389 Print the vector of sets (used for debugging)
1390 */
1391 inline void sparse_sizevec::print(void) const
1392 { std::cout << "sparse_sizevec:\n";
1393  for(size_t i = 0; i < n_set(); i++)
1394  { std::cout << "set[" << i << "] = {";
1395  const_iterator itr(*this, i);
1396  while( *itr != end() )
1397  { std::cout << *itr;
1398  if( *(++itr) != end() )
1399  std::cout << ",";
1400  }
1401  std::cout << "}\n";
1402  }
1403  return;
1404 }
1405
1406 /*!
1407 Copy a user vector of sets sparsity pattern to an internal sparse_sizevec object.
1408
1409 \tparam VectorSet
1410 is a simple vector with elements of type std::set<size_t>.
1411
1412 \param internal
1413 The input value of sparisty does not matter.
1414 Upon return it contains the same sparsity pattern as \c user
1415 (or the transposed sparsity pattern).
1416
1417 \param user
1418 sparsity pattern that we are placing internal.
1419
1420 \param n_set
1421 number of sets (rows) in the internal sparsity pattern.
1422
1423 \param end
1424 end of set value (number of columns) in the interanl sparsity pattern.
1425
1426 \param transpose
1427 if true, the user sparsity patter is the transposed.
1428
1429 \param error_msg
1430 is the error message to display if some values in the user sparstiy
1431 pattern are not valid.
1432 */
1433 template<class VectorSet>
1435  sparse_sizevec& internal ,
1436  const VectorSet& user ,
1437  size_t n_set ,
1438  size_t end ,
1439  bool transpose ,
1440  const char* error_msg )
1441 {
1442 # ifndef NDEBUG
1443  if( transpose )
1444  CPPAD_ASSERT_KNOWN( end == size_t( user.size() ), error_msg);
1445  if( ! transpose )
1446  CPPAD_ASSERT_KNOWN( n_set == size_t( user.size() ), error_msg);
1447 # endif
1448
1449  // iterator for user set
1450  std::set<size_t>::const_iterator itr;
1451
1452  // size of internal sparsity pattern
1453  internal.resize(n_set, end);
1454
1455  if( transpose )
1456  { // transposed pattern case
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++;
1463  }
1464  }
1465  }
1466  else
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++;
1471  CPPAD_ASSERT_KNOWN( j < end, error_msg);
1473  }
1474  }
1475  }
1476  return;
1477 }
1478
1480 # endif
size_t memory(void) const
Amount of memory used by this vector of sets.
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 &lt;= capacity_).
Definition: pod_vector.hpp:180
void clear(void)
Remove all the elements from this vector and free its memory.
Definition: pod_vector.hpp:246
size_t extend(size_t n)
Increase the number of elements the end of this vector (existing elements are always preserved)...
Definition: pod_vector.hpp:115
void push_back(const Type &e)
Add an element to theh back of this vector.
Definition: pod_vector.hpp:312
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.
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.
Definition: pod_vector.hpp:79
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.
Definition: pod_vector.hpp:89
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.
Definition: pod_vector.hpp:300
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.
Definition: pod_vector.hpp:83
~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.