aGrUM  0.18.1
a C++ library for (probabilistic) graphical models
list_tpl.h
Go to the documentation of this file.
1 
30 // to ease parser
31 #include <agrum/tools/core/list.h>
32 
33 namespace gum {
34 
35  // ===========================================================================
36  // ===========================================================================
37  // === BUCKET IMPLEMENTATION ===
38  // ===========================================================================
39  // ===========================================================================
40 
41  // default constructor
42  template < typename Val >
43  INLINE ListBucket< Val >::ListBucket(const Val& v) : val__{v} {
44  // for debugging purposes
45  GUM_CONSTRUCTOR(ListBucket);
46  }
47 
48  // constructor for Val rvalues
49  template < typename Val >
50  INLINE ListBucket< Val >::ListBucket(Val&& v) noexcept : val__{std::move(v)} {
51  // for debugging purposes
52  GUM_CONSTRUCTOR(ListBucket);
53  }
54 
55  // emplace constructor
56  template < typename Val >
57  template < typename... Args >
59  Args&&... args) :
60  val__(std::forward< Args >(args)...) {
61  // for debugging purposes
62  GUM_CONSTRUCTOR(ListBucket);
63  }
64 
65  // copy constructor
66  template < typename Val >
68  val__{src.val__} {
69  // for debugging purposes
70  GUM_CONS_CPY(ListBucket);
71  }
72 
73  // copy operator
74  template < typename Val >
75  INLINE ListBucket< Val >&
77  // for debugging purposes
78  GUM_OP_CPY(ListBucket);
79 
80  // no need to avoid self assignment
81  val__ = src.val__;
82  return *this;
83  }
84 
85  // WARNING: during its deletion, the bucket does not take care of properly
86  // re-chaining the chained list. This should be done by the Lists themselves
87  template < typename Val >
89  // for debugging purposes
90  GUM_DESTRUCTOR(ListBucket);
91  }
92 
93  // equality check
94  template < typename Val >
95  INLINE bool ListBucket< Val >::operator==(const ListBucket< Val >& src) const {
96  return (src.val__ == val__);
97  }
98 
99  // inequality check
100  template < typename Val >
101  INLINE bool ListBucket< Val >::operator!=(const ListBucket< Val >& src) const {
102  return (src.val__ != val__);
103  }
104 
105  // dereferencing operator
106  template < typename Val >
107  INLINE const Val& ListBucket< Val >::operator*() const noexcept {
108  return val__;
109  }
110 
111  // dereferencing operator
112  template < typename Val >
113  INLINE Val& ListBucket< Val >::operator*() noexcept {
114  return val__;
115  }
116 
117  // returns the bucket toward the next element
118  template < typename Val >
119  INLINE const ListBucket< Val >* ListBucket< Val >::next() const noexcept {
120  return next__;
121  }
122 
123  // returns the bucket toward the preceding element
124  template < typename Val >
125  INLINE const ListBucket< Val >* ListBucket< Val >::previous() const noexcept {
126  return prev__;
127  }
128 
129  // ===========================================================================
130  // ===========================================================================
131  // === UNSAFE_CONST_LIST_ITERATOR IMPLEMENTATION ===
132  // ===========================================================================
133  // ===========================================================================
134 
135  // default constructor
136  template < typename Val >
138  // for debugging purposes
139  GUM_CONSTRUCTOR(ListConstIterator);
140  }
141 
142  // default constructor
143  template < typename Val >
144  template < typename Alloc >
146  const List< Val, Alloc >& theList) noexcept :
147  bucket__{theList.deb_list__} {
148  // for debugging purposes
149  GUM_CONSTRUCTOR(ListConstIterator);
150  }
151 
152  // copy constructor
153  template < typename Val >
155  const ListConstIterator< Val >& src) noexcept :
156  bucket__{src.bucket__} {
157  // for debugging purposes
158  GUM_CONS_CPY(ListConstIterator);
159  }
160 
161  // move constructor
162  template < typename Val >
164  ListConstIterator< Val >&& src) noexcept :
165  bucket__{std::move(src.bucket__)} {
166  // for debugging purposes
167  GUM_CONS_MOV(ListConstIterator);
168  }
169 
170  // Constructor for an iterator pointing to the \e ind_eltth element of a
171  // List.
172  template < typename Val >
174  Size ind_elt) {
175  // for debugging purposes
176  GUM_CONSTRUCTOR(ListConstIterator);
177 
178  // check if the index ind_elt passed as parameter is valid
179  if (ind_elt >= theList.nb_elements__) {
180  GUM_ERROR(UndefinedIteratorValue, "Not enough elements in the list");
181  }
182 
183  // check if it is faster to find the indexth element from the start or
184  // from the end of the list
185  if (ind_elt < (theList.nb_elements__ >> 1)) {
186  // find the element we shall point to src the start of the list
187  for (bucket__ = theList.deb_list__; ind_elt;
188  --ind_elt, bucket__ = bucket__->next__) {}
189  } else {
190  // find the element we shall point to src the end of the list
191  for (bucket__ = theList.end_list__,
192  ind_elt = theList.nb_elements__ - ind_elt - 1;
193  ind_elt;
194  --ind_elt, bucket__ = bucket__->prev__) {}
195  }
196  }
197 
198  // Destructor
199  template < typename Val >
201  // for debugging purposes
202  GUM_DESTRUCTOR(ListConstIterator);
203  }
204 
205  // Copy operator
206  template < typename Val >
208  const ListConstIterator< Val >& src) noexcept {
209  // for debugging purposes
210  GUM_OP_CPY(ListConstIterator);
211 
212  bucket__ = src.bucket__;
213  return *this;
214  }
215 
216  // move operator
217  template < typename Val >
220  // for debugging purposes
221  GUM_OP_MOV(ListConstIterator);
222  bucket__ = src.bucket__;
223  return *this;
224  }
225 
226  // returns the bucket the iterator is pointing to
227  template < typename Val >
228  INLINE ListBucket< Val >*
230  return bucket__;
231  }
232 
233  // Makes the iterator point toward nothing
234  template < typename Val >
235  INLINE void ListConstIterator< Val >::clear() noexcept {
236  bucket__ = nullptr;
237  }
238 
239  // positions the iterator to the end of the list
240  template < typename Val >
241  INLINE void ListConstIterator< Val >::setToEnd() noexcept {
242  bucket__ = nullptr;
243  }
244 
245  // returns a bool indicating whether the iterator points to the end of the
246  // list
247  template < typename Val >
248  INLINE bool ListConstIterator< Val >::isEnd() const noexcept {
249  return (bucket__ == nullptr);
250  }
251 
252  // makes the iterator point to the next element in the List
253  template < typename Val >
256  // if we are pointing to an element of the chained list, just
257  // point on the next bucket in this list
258  if (bucket__ != nullptr) { bucket__ = bucket__->next__; }
259 
260  return *this;
261  }
262 
263  // makes the iterator point to the next element in the List
264  template < typename Val >
266  typename ListConstIterator< Val >::difference_type i) noexcept {
267  if (i >= 0) {
268  for (; i && (bucket__ != nullptr); --i, bucket__ = bucket__->next__) {}
269  } else {
270  for (; i && (bucket__ != nullptr); ++i, bucket__ = bucket__->prev__) {}
271  }
272  return *this;
273  }
274 
275  // makes the iterator point to the preceding element in the List
276  template < typename Val >
279  // if we are pointing to an element of the chained list, just
280  // point on the preceding bucket in this list
281  if (bucket__ != nullptr) { bucket__ = bucket__->prev__; }
282 
283  return *this;
284  }
285 
286  // makes the iterator point to i elements before in the list
287  template < typename Val >
289  typename ListConstIterator< Val >::difference_type i) noexcept {
290  if (i >= 0) {
291  for (; i && (bucket__ != nullptr); --i, bucket__ = bucket__->prev__) {}
292  } else {
293  for (; i && (bucket__ != nullptr); ++i, bucket__ = bucket__->next__) {}
294  }
295  return *this;
296  }
297 
298  // returns a new iterator
299  template < typename Val >
301  typename ListConstIterator< Val >::difference_type i) noexcept {
302  return ListConstIterator< Val >(*this) += i;
303  }
304 
305  // returns a new iterator
306  template < typename Val >
308  typename ListConstIterator< Val >::difference_type i) noexcept {
309  return ListConstIterator< Val >(*this) -= i;
310  }
311 
312  // checks whether two iterators point toward different elements
313  template < typename Val >
315  const ListConstIterator< Val >& src) const noexcept {
316  return (bucket__ != src.bucket__);
317  }
318 
319  // checks whether two iterators point toward the same elements.
320  template < typename Val >
322  const ListConstIterator< Val >& src) const noexcept {
323  return (bucket__ == src.bucket__);
324  }
325 
326  // dereferences the value pointed to by the iterator
327  template < typename Val >
328  INLINE const Val* ListConstIterator< Val >::operator->() const {
329  if (bucket__ != nullptr)
330  return &(bucket__->val__);
331  else {
332  GUM_ERROR(UndefinedIteratorValue, "Accessing a NULL object");
333  }
334  }
335 
336  // gives access to the content of the iterator
337  template < typename Val >
338  INLINE const Val& ListConstIterator< Val >::operator*() const {
339  if (bucket__ != nullptr)
340  return bucket__->val__;
341  else {
342  GUM_ERROR(UndefinedIteratorValue, "Accessing a NULL object");
343  }
344  }
345 
346  // for STL compliance, a distance operator
347  template < typename Val >
350  const ListConstIterator< Val >& iter2) {
352 
353  for (ListConstIterator< Val > iter3 = iter2; iter1 != iter3; ++iter3, ++res) {}
354 
355  return res;
356  }
357 
358  // ===========================================================================
359  // ===========================================================================
360  // === UNSAFE_LIST_ITERATOR IMPLEMENTATION ===
361  // ===========================================================================
362  // ===========================================================================
363 
364  // basic constructor
365  template < typename Val >
367  ListConstIterator< Val >() {
368  GUM_CONSTRUCTOR(ListIterator);
369  }
370 
371  // constructor for a begin
372  template < typename Val >
373  template < typename Alloc >
374  INLINE
376  :
377  ListConstIterator< Val >(theList) {
378  GUM_CONSTRUCTOR(ListIterator);
379  }
380 
381  // copy constructor
382  template < typename Val >
384  :
386  GUM_CONS_CPY(ListIterator);
387  }
388 
389  // move constructor
390  template < typename Val >
392  ListConstIterator< Val >(std::move(src)) {
393  GUM_CONS_MOV(ListIterator);
394  }
395 
396  // Constructor for an iterator pointing to the \e ind_eltth element of a
397  // List.
398  template < typename Val >
400  Size ind_elt) :
401  ListConstIterator< Val >(theList, ind_elt) {
402  GUM_CONSTRUCTOR(ListIterator);
403  }
404 
405  // Copy operator
406  template < typename Val >
407  INLINE ListIterator< Val >&
409  GUM_OP_CPY(ListIterator);
411  return *this;
412  }
413 
414  // move operator
415  template < typename Val >
416  INLINE ListIterator< Val >&
418  GUM_OP_MOV(ListIterator);
419  ListConstIterator< Val >::operator=(std::move(src));
420  return *this;
421  }
422 
423  // Destructor
424  template < typename Val >
426  GUM_DESTRUCTOR(ListIterator);
427  }
428 
429  // makes the iterator point to the next element in the List
430  template < typename Val >
433  return *this;
434  }
435 
436  // makes the iterator point to i elements further in the List
437  template < typename Val >
439  typename ListIterator< Val >::difference_type i) noexcept {
441  return *this;
442  }
443 
444  // makes the iterator point to the preceding element in the List
445  template < typename Val >
448  return *this;
449  }
450 
451  // makes the iterator point to i elements before in the List
452  template < typename Val >
454  typename ListIterator< Val >::difference_type i) noexcept {
456  return *this;
457  }
458 
459  // returns a new iterator
460  template < typename Val >
462  typename ListIterator< Val >::difference_type i) noexcept {
463  return ListIterator< Val >(*this) += i;
464  }
465 
466  // returns a new iterator
467  template < typename Val >
469  typename ListIterator< Val >::difference_type i) noexcept {
470  return ListIterator< Val >(*this) -= i;
471  }
472 
473  // dereferences the value pointed to by the iterator
474  template < typename Val >
476  return const_cast< Val* >(ListConstIterator< Val >::operator->());
477  }
478 
479  // gives access to the content of the iterator
480  template < typename Val >
482  return const_cast< Val& >(ListConstIterator< Val >::operator*());
483  }
484 
485  // ===========================================================================
486  // ===========================================================================
487  // === SAFE LIST CONST ITERATOR IMPLEMENTATION ===
488  // ===========================================================================
489  // ===========================================================================
490 
491  // basic constructor
492  template < typename Val >
494  // for debugging purposes
495  GUM_CONSTRUCTOR(ListConstIteratorSafe);
496  }
497 
498  // Constructor for a begin
499  template < typename Val >
500  template < typename Alloc >
502  const List< Val, Alloc >& theList) :
503  list__{
504  reinterpret_cast< const List< Val, std::allocator< Val > >* >(&theList)},
505  bucket__{theList.deb_list__} {
506  // for debugging purposes
507  GUM_CONSTRUCTOR(ListConstIteratorSafe);
508 
509  // add the iterator to the list of safe iterators
510  theList.safe_iterators__.push_back(this);
511  }
512 
513  // copy constructor
514  template < typename Val >
516  const ListConstIteratorSafe< Val >& src) :
517  list__{src.list__},
518  bucket__{src.bucket__}, next_current_bucket__{src.next_current_bucket__},
519  prev_current_bucket__{src.prev_current_bucket__}, null_pointing__{
520  src.null_pointing__} {
521  // for debugging purposes
522  GUM_CONS_CPY(ListConstIteratorSafe);
523 
524  // add the iterator to the list of safe iterators
525  if (list__ != nullptr) list__->safe_iterators__.push_back(this);
526  }
527 
528  // Constructor for an iterator pointing to the \e ind_eltth element of a
529  // List.
530  template < typename Val >
531  template < typename Alloc >
533  const List< Val, Alloc >& theList, Size ind_elt) :
534  list__{
535  reinterpret_cast< const List< Val, std::allocator< Val > >* >(&theList)} {
536  // for debugging purposes
537  GUM_CONSTRUCTOR(ListConstIteratorSafe);
538 
539  // check if the index ind_elt passed as parameter is valid
540  if (ind_elt >= list__->nb_elements__) {
541  GUM_ERROR(UndefinedIteratorValue, "Not enough elements in the list");
542  }
543 
544  // check if it is faster to find the indexth element src the start or
545  // src the end of the list
546  if (ind_elt < (list__->nb_elements__ >> 1)) {
547  // find the element we shall point to src the start of the list
548  for (bucket__ = list__->deb_list__; ind_elt;
549  --ind_elt, bucket__ = bucket__->next__) {}
550  } else {
551  // find the element we shall point to src the end of the list
552  for (bucket__ = list__->end_list__,
553  ind_elt = list__->nb_elements__ - ind_elt - 1;
554  ind_elt;
555  --ind_elt, bucket__ = bucket__->prev__) {}
556  }
557 
558  // add the iterator to the list of safe iterators
559  theList.safe_iterators__.push_back(this);
560  }
561 
562  // move constructor
563  template < typename Val >
566  list__{src.list__},
567  bucket__{src.bucket__}, next_current_bucket__{src.next_current_bucket__},
568  prev_current_bucket__{src.prev_current_bucket__}, null_pointing__{
569  src.null_pointing__} {
570  // for debugging purposes
571  GUM_CONS_MOV(ListConstIteratorSafe);
572 
573  if (list__ != nullptr) {
574  // substitute src by this in the list of safe iterators
575  std::vector< ListConstIteratorSafe< Val >* >& vect =
577 
578  for (auto ptr = vect.rbegin(); ptr != vect.rend(); --ptr) {
579  if (*ptr == &src) {
580  *ptr = this;
581  break;
582  }
583  }
584 
585  src.list__ = nullptr;
586  src.bucket__ = nullptr;
587  src.null_pointing__ = false;
588  }
589  }
590 
591  // remove the iterator for its list' safe iterators list
592  template < typename Val >
594  // find where the iterator is
595  std::vector< ListConstIteratorSafe< Val >* >& vect = list__->safe_iterators__;
596 
597  for (auto i = vect.size() - 1; i >= 0; --i) {
598  if (vect[i] == this) {
599  vect.erase(vect.begin() + i);
600  break;
601  }
602  }
603  }
604 
605  // Copy operator
606  template < typename Val >
608  const ListConstIteratorSafe< Val >& src) {
609  // avoid self assignment
610  if (this != &src) {
611  // for debugging purposes
612  GUM_OP_CPY(ListConstIteratorSafe);
613 
614  // check if src and this belong to the same list. If this is not
615  // the case, we shall remove this from its iterator's list and
616  // put it into src's list one.
617  if (list__ && (src.list__ != list__)) {
619  list__ = nullptr;
620  }
621 
622  // if necessary, put this into the same list of safe iterators as src
623  if (src.list__ && (src.list__ != list__)) {
624  try {
625  src.list__->safe_iterators__.push_back(this);
626  } catch (...) {
627  list__ = nullptr;
628  bucket__ = nullptr;
629  null_pointing__ = false;
630  throw;
631  }
632  }
633 
634  list__ = src.list__;
635  bucket__ = src.bucket__;
639  }
640 
641  return *this;
642  }
643 
644  // move operator
645  template < typename Val >
648  // avoid self assignment
649  if (this != &src) {
650  // for debugging purposes
651  GUM_OP_MOV(ListConstIteratorSafe);
652 
653  // if the two iterators do not point to the same list, remove
654  // the current iterator from its safe iterators list
655  if ((list__ != nullptr) && (src.list__ != list__)) {
657  list__ = nullptr;
658  }
659 
660  // now if src points to a list, put this at its location
661  if ((src.list__ != nullptr)) {
662  std::vector< ListConstIteratorSafe< Val >* >& vect =
663  src.list__->safe_iterators__;
664  Idx index_src = Size(vect.size()) - 1;
665 
666  for (;; --index_src) {
667  if (vect[index_src] == &src) { break; }
668  }
669 
670  if (list__ == nullptr) {
671  vect[index_src] = this;
672  } else {
673  vect.erase(vect.begin() + index_src);
674  }
675  }
676 
677  list__ = src.list__;
678  bucket__ = src.bucket__;
679  prev_current_bucket__ = src.prev_current_bucket__;
680  next_current_bucket__ = src.next_current_bucket__;
681  null_pointing__ = src.null_pointing__;
682 
683  src.list__ = nullptr;
684  src.bucket__ = nullptr;
685  src.null_pointing__ = false;
686  }
687 
688  return *this;
689  }
690 
691  // Destructor
692  template < typename Val >
694  // for debugging purposes
695  GUM_DESTRUCTOR(ListConstIteratorSafe);
696 
697  // remove the iterator src the table's iterator list
699  }
700 
701  // returns the bucket the iterator is pointing to
702  template < typename Val >
703  INLINE ListBucket< Val >*
705  return bucket__;
706  }
707 
708  // Makes the iterator point toward nothing
709  template < typename Val >
711  // remove the iterator src the list's iterator list
713 
714  // set its list as well as the element it points to to nullptr
715  list__ = nullptr;
716  bucket__ = nullptr;
717  null_pointing__ = false;
718  }
719 
720  // positions the iterator to the end of the list
721  template < typename Val >
723  clear();
724  }
725 
726  // returns a bool indicating whether the iterator points to the end of the
727  // list
728  template < typename Val >
730  return null_pointing__ ? (next_current_bucket__ == nullptr)
731  && (prev_current_bucket__ == nullptr)
732  : (bucket__ == nullptr);
733  }
734 
735  // makes the iterator point to the next element in the List
736  template < typename Val >
739  // check if we are pointing to something that has been deleted
740  if (null_pointing__) {
741  null_pointing__ = false;
742 
743  // if we are pointing to an element of the chained list that has been
744  // deleted
745  // but that has a next element, just point on the latter
746  if (next_current_bucket__ != nullptr) {
748  return *this;
749  }
750 
751  // here we were pointing on an extremity of the list (either end or rend)
752  // if prev_current_bucket is not null, then we are at rend and doing
753  // a ++ shall now point to the beginning of the list
754  if (prev_current_bucket__ != nullptr) {
756  return *this;
757  }
758 
759  // here, we are at the end of the chained list, hence we shall remain at
760  // end
761  bucket__ = nullptr;
762  return *this;
763  } else {
764  // if we are pointing to an element of the chained list, just
765  // point on the next bucket in this list
766  if (bucket__ != nullptr) { bucket__ = bucket__->next__; }
767 
768  return *this;
769  }
770  }
771 
772  // makes the iterator point to i elements before in the List
773  template < typename Val >
776  // check if we are pointing to something that has been deleted
777  if (null_pointing__) {
778  null_pointing__ = false;
779 
780  // if we are pointing to an element of the chained list that has been
781  // deleted
782  // but that has a preceding element, just point on the latter
783  if (prev_current_bucket__ != nullptr) {
785  } else {
786  // here we were pointing on an extremity of the list (either end or
787  // rend)
788  // if next_current_bucket is not null, then we are at end and doing
789  // a -- shall now point to the beginning of the list
790  if (next_current_bucket__ != nullptr) {
792  } else {
793  // here, we are at the rend of the chained list, hence we shall remain
794  // at rend
795  bucket__ = nullptr;
796  return *this;
797  }
798  }
799  } else {
800  // if we are pointing to an element of the chained list, just
801  // point on the preceding bucket in this list
802  if (bucket__ != nullptr) { bucket__ = bucket__->prev__; }
803  }
804 
805  for (--i; i && (bucket__ != nullptr); --i, bucket__ = bucket__->prev__) {}
806 
807  return *this;
808  }
809 
810  // makes the iterator point to the next element in the List
811  template < typename Val >
814  // check if we are pointing to something that has been deleted
815  if (null_pointing__) {
816  null_pointing__ = false;
817 
818  // if we are pointing to an element of the chained list that has been
819  // deleted
820  // but that has a next element, just point on the latter
821  if (next_current_bucket__ != nullptr) {
823  } else {
824  // here we were pointing on an extremity of the list (either end or
825  // rend)
826  // if prev_current_bucket is not null, then we are at rend and doing
827  // a ++ shall now point to the beginning of the list
828  if (prev_current_bucket__ != nullptr) {
830  } else {
831  // here, we are at the end of the chained list, hence we shall
832  // remain at end
833  bucket__ = nullptr;
834  return *this;
835  }
836  }
837  } else {
838  // if we are pointing to an element of the chained list, just
839  // point on the next bucket in this list
840  if (bucket__ != nullptr) { bucket__ = bucket__->next__; }
841  }
842 
843  for (--i; i && (bucket__ != nullptr); --i, bucket__ = bucket__->next__) {}
844 
845  return *this;
846  }
847 
848  // makes the iterator point to the next element in the List
849  template < typename Val >
851  typename ListConstIteratorSafe< Val >::difference_type i) noexcept {
852  if (!i) return *this;
853 
854  if (i < 0)
855  return opMinus__(-i);
856  else
857  return opPlus__(i);
858  }
859 
860  // makes the iterator point to the preceding element in the List
861  template < typename Val >
864  // check if we are pointing to something that has been deleted
865  if (null_pointing__) {
866  null_pointing__ = false;
867 
868  // if we are pointing to an element of the chained list that has been
869  // deleted
870  // but that has a preceding element, just point on the latter
871  if (prev_current_bucket__ != nullptr) {
873  return *this;
874  }
875 
876  // here we were pointing on an extremity of the list (either end or rend)
877  // if next_current_bucket is not null, then we are at end and doing
878  // a -- shall now point to the beginning of the list
879  if (next_current_bucket__ != nullptr) {
881  return *this;
882  }
883 
884  // here, we are at the rend of the chained list, hence we shall remain
885  // at rend
886  bucket__ = nullptr;
887  return *this;
888  } else {
889  // if we are pointing to an element of the chained list, just
890  // point on the preceding bucket in this list
891  if (bucket__ != nullptr) { bucket__ = bucket__->prev__; }
892 
893  return *this;
894  }
895  }
896 
897  // makes the iterator point to i elements before in the List
898  template < typename Val >
900  typename ListConstIteratorSafe< Val >::difference_type i) noexcept {
901  if (!i) return *this;
902 
903  if (i < 0)
904  return opPlus__(-i);
905  else
906  return opMinus__(i);
907  }
908 
909  // returns a new iterator
910  template < typename Val >
912  typename ListConstIteratorSafe< Val >::difference_type i) noexcept {
913  return ListConstIteratorSafe< Val >(*this) += i;
914  }
915 
916  // returns a new iterator
917  template < typename Val >
919  typename ListConstIteratorSafe< Val >::difference_type i) noexcept {
920  return ListConstIteratorSafe< Val >(*this) -= i;
921  }
922 
923  // checks whether two iterators point toward different elements
924  template < typename Val >
926  const ListConstIteratorSafe< Val >& src) const {
927  return null_pointing__
930  : (bucket__ != src.bucket__);
931  }
932 
933  // checks whether two iterators point toward the same elements.
934  template < typename Val >
936  const ListConstIteratorSafe< Val >& src) const {
937  return null_pointing__
940  : (bucket__ == src.bucket__);
941  }
942 
943  // dereferences the value pointed to by the iterator
944  template < typename Val >
945  INLINE const Val* ListConstIteratorSafe< Val >::operator->() const {
946  if (bucket__ != nullptr)
947  return &(bucket__->val__);
948  else {
949  GUM_ERROR(UndefinedIteratorValue, "Accessing a NULL object");
950  }
951  }
952 
953  // gives access to the content of the iterator
954  template < typename Val >
955  INLINE const Val& ListConstIteratorSafe< Val >::operator*() const {
956  if (bucket__ != nullptr)
957  return bucket__->val__;
958  else {
959  GUM_ERROR(UndefinedIteratorValue, "Accessing a NULL object");
960  }
961  }
962 
963  // for STL compliance, a distance operator
964  template < typename Val >
967  const ListConstIteratorSafe< Val >& iter2) {
969  ListConstIteratorSafe< Val > iter3{iter2};
970 
971  for (; iter1 != iter3; ++iter3, ++res) {}
972 
973  return res;
974  }
975 
976  // ===========================================================================
977  // ===========================================================================
978  // === LIST ITERATOR IMPLEMENTATION ===
979  // ===========================================================================
980  // ===========================================================================
981 
982  // basic constructor
983  template < typename Val >
985  ListConstIteratorSafe< Val >() {
986  GUM_CONSTRUCTOR(ListIteratorSafe);
987  }
988 
989  // constructor for a begin
990  template < typename Val >
991  template < typename Alloc >
992  INLINE
994  ListConstIteratorSafe< Val >(theList) {
995  GUM_CONSTRUCTOR(ListIteratorSafe);
996  }
997 
998  // copy constructor
999  template < typename Val >
1001  const ListIteratorSafe< Val >& src) :
1002  ListConstIteratorSafe< Val >(src) {
1003  GUM_CONS_CPY(ListIteratorSafe);
1004  }
1005 
1006  // Constructor for an iterator pointing to the \e ind_eltth element of a
1007  // List.
1008  template < typename Val >
1009  template < typename Alloc >
1010  INLINE
1012  Size ind_elt) :
1013  ListConstIteratorSafe< Val >(theList, ind_elt) {
1014  GUM_CONSTRUCTOR(ListIteratorSafe);
1015  }
1016 
1017  // move constructor
1018  template < typename Val >
1020  ListConstIteratorSafe< Val >(std::move(src)) {
1021  GUM_CONS_MOV(ListIteratorSafe);
1022  }
1023 
1024  // Copy operator
1025  template < typename Val >
1026  INLINE ListIteratorSafe< Val >&
1028  // for debugging purposes
1029  GUM_OP_CPY(ListIteratorSafe);
1031  return *this;
1032  }
1033 
1034  // move operator
1035  template < typename Val >
1036  INLINE ListIteratorSafe< Val >&
1038  // for debugging purposes
1039  GUM_OP_MOV(ListIteratorSafe);
1041  return *this;
1042  }
1043 
1044  // Destructor
1045  template < typename Val >
1047  GUM_DESTRUCTOR(ListIteratorSafe);
1048  }
1049 
1050  // makes the iterator point to the next element in the List
1051  template < typename Val >
1054  return *this;
1055  }
1056 
1057  // makes the iterator point to the next element in the List
1058  template < typename Val >
1060  typename ListIteratorSafe< Val >::difference_type i) noexcept {
1062  return *this;
1063  }
1064 
1065  // makes the iterator point to the preceding element in the List
1066  template < typename Val >
1069  return *this;
1070  }
1071 
1072  // makes the iterator point to the preceding element in the List
1073  template < typename Val >
1075  typename ListIteratorSafe< Val >::difference_type i) noexcept {
1077  return *this;
1078  }
1079 
1080  // returns a new iterator
1081  template < typename Val >
1083  typename ListIteratorSafe< Val >::difference_type i) noexcept {
1084  return ListIteratorSafe< Val >(*this) += i;
1085  }
1086 
1087  // returns a new iterator
1088  template < typename Val >
1090  typename ListIteratorSafe< Val >::difference_type i) noexcept {
1091  return ListIteratorSafe< Val >(*this) -= i;
1092  }
1093 
1094  // dereferences the value pointed to by the iterator
1095  template < typename Val >
1097  return const_cast< Val* >(ListConstIteratorSafe< Val >::operator->());
1098  }
1099 
1100  // gives access to the content of the iterator
1101  template < typename Val >
1103  return const_cast< Val& >(ListConstIteratorSafe< Val >::operator*());
1104  }
1105 
1106  // ===========================================================================
1107  // ===========================================================================
1108  // === LIST IMPLEMENTATION ===
1109  // ===========================================================================
1110  // ===========================================================================
1111 
1112  // a function used to perform copies of elements of Lists
1113  template < typename Val, typename Alloc >
1114  template < typename OtherAlloc >
1116  ListBucket< Val >* ptr;
1117  ListBucket< Val >* old_ptr = nullptr;
1118  ListBucket< Val >* new_elt = nullptr;
1119 
1120  // copy src's list
1121  try {
1122  for (ptr = src.deb_list__; ptr != nullptr; ptr = ptr->next__) {
1123  // create a copy bucket
1124  new_elt = alloc_bucket__.allocate(1);
1125 
1126  try {
1127  alloc_bucket__.construct(new_elt, *ptr);
1128  } catch (...) {
1129  alloc_bucket__.deallocate(new_elt, 1);
1130  throw;
1131  }
1132 
1133  // rechain properly the new list (the next field is already initialized
1134  // with nullptr)
1135  new_elt->prev__ = old_ptr;
1136 
1137  if (old_ptr)
1138  old_ptr->next__ = new_elt;
1139  else
1140  deb_list__ = new_elt;
1141 
1142  old_ptr = new_elt;
1143  }
1144  } catch (...) {
1145  // problem: we could not allocate an element in the list => we delete
1146  // the elements created so far and we throw an exception
1147  for (; deb_list__ != nullptr;
1148  deb_list__ = const_cast< ListBucket< Val >* >(ptr)) {
1149  ptr = deb_list__->next__;
1150  alloc_bucket__.destroy(deb_list__);
1151  alloc_bucket__.deallocate(deb_list__, 1);
1152  }
1153 
1154  deb_list__ = nullptr;
1155  throw;
1156  }
1157 
1158  // update properly the end of the chained list and the number of elements
1159  end_list__ = old_ptr;
1160  nb_elements__ = src.nb_elements__;
1161  }
1162 
1163  // deletes all the elements of a chained list.
1164  template < typename Val, typename Alloc >
1166  // first we update all the safe iterators of the list : they should now
1167  // point to end/rend
1168  for (const auto ptr_iter: safe_iterators__) {
1169  ptr_iter->clear();
1170  }
1171 
1172  // clear all the values
1173  for (ListBucket< Val >*ptr = deb_list__, *next_ptr = nullptr; ptr != nullptr;
1174  ptr = next_ptr) {
1175  next_ptr = ptr->next__;
1176  alloc_bucket__.destroy(ptr);
1177  alloc_bucket__.deallocate(ptr, 1);
1178  }
1179 
1180  nb_elements__ = 0;
1181  deb_list__ = nullptr;
1182  end_list__ = nullptr;
1183  }
1184 
1185  // A basic constructor that creates an empty list
1186  template < typename Val, typename Alloc >
1188  // for debugging purposes
1189  GUM_CONSTRUCTOR(List);
1190 
1191  // reserve space for only the default number of iterators
1192  safe_iterators__.reserve(GUM_DEFAULT_ITERATOR_NUMBER);
1193  }
1194 
1195  // Copy constructor
1196  template < typename Val, typename Alloc >
1198  // for debugging purposes
1199  GUM_CONS_CPY(List);
1200 
1201  // copy the elements
1202  copy_elements__(src);
1203 
1204  // reserve space for only the default number of iterators
1205  safe_iterators__.reserve(GUM_DEFAULT_ITERATOR_NUMBER);
1206  }
1207 
1208  // generalized copy constructor
1209  template < typename Val, typename Alloc >
1210  template < typename OtherAlloc >
1212  // for debugging purposes
1213  GUM_CONS_CPY(List);
1214 
1215  // copy the elements
1216  copy_elements__(src);
1217 
1218  // reserve space for only the default number of iterators
1219  safe_iterators__.reserve(GUM_DEFAULT_ITERATOR_NUMBER);
1220  }
1221 
1222  // move constructor
1223  template < typename Val, typename Alloc >
1225  deb_list__{std::move(src.deb_list__)}, end_list__{std::move(src.end_list__)},
1226  nb_elements__{std::move(src.nb_elements__)},
1227  safe_iterators__{std::move(src.safe_iterators__)}, alloc_bucket__{std::move(
1228  src.alloc_bucket__)} {
1229  // for debugging purposes
1230  GUM_CONS_MOV(List);
1231 
1232  src.deb_list__ = nullptr;
1233  src.end_list__ = nullptr;
1234  src.nb_elements__ = 0;
1235  src.safe_iterators__.clear();
1236  }
1237 
1238  // initializer_list constructor
1239  template < typename Val, typename Alloc >
1240  INLINE List< Val, Alloc >::List(std::initializer_list< Val > list) {
1241  // for debugging purposes
1242  GUM_CONSTRUCTOR(List);
1243 
1244  // adding all the elements
1245  for (const auto& val: list) {
1246  pushBack(val);
1247  }
1248 
1249  // reserve space for only the default number of iterators
1250  safe_iterators__.reserve(GUM_DEFAULT_ITERATOR_NUMBER);
1251  }
1252 
1253  // Destructor
1254  template < typename Val, typename Alloc >
1256  // for debugging (although this program is bug-free)
1257  GUM_DESTRUCTOR(List);
1258 
1259  // we detach all the safe iterators attached to the current List and we
1260  // remove all the elements from the list
1261  clear();
1262  }
1263 
1264  // Copy operator. The List iterator's list is not shared with that of \e src.
1265  template < typename Val, typename Alloc >
1266  INLINE List< Val, Alloc >&
1268  // avoid self assignment
1269  if (this != &src) {
1270  // for debugging purposes
1271  GUM_OP_CPY(List);
1272 
1273  // remove the old content of 'this' and update accordingly the iterators
1274  clear();
1275 
1276  // perform the copy
1277  copy_elements__(src);
1278  }
1279 
1280  return *this;
1281  }
1282 
1283  // Generalized copy operator.
1284  template < typename Val, typename Alloc >
1285  template < typename OtherAlloc >
1286  INLINE List< Val, Alloc >&
1288  // avoid self assignment
1289  if (this != reinterpret_cast< List< Val, Alloc >* >(&src)) {
1290  // for debugging purposes
1291  GUM_OP_CPY(List);
1292 
1293  // remove the old content of 'this' and update accordingly the iterators
1294  clear();
1295 
1296  // perform the copy
1297  copy_elements__(src);
1298  }
1299 
1300  return *this;
1301  }
1302 
1303  // move operator
1304  template < typename Val, typename Alloc >
1305  INLINE List< Val, Alloc >&
1307  // avoid self assignment
1308  if (this != &src) {
1309  // for debugging purposes
1310  GUM_OP_MOV(List);
1311 
1312  // remove the old content of 'this' and update accordingly the iterators
1313  clear();
1314 
1315  // perform the move
1316  deb_list__ = std::move(src.deb_list__);
1317  end_list__ = std::move(src.end_list__);
1318  nb_elements__ = std::move(src.nb_elements__);
1319  safe_iterators__ = std::move(src.safe_iterators__);
1320  alloc_bucket__ = std::move(src.alloc_bucket__);
1321 
1322  src.deb_list__ = nullptr;
1323  src.end_list__ = nullptr;
1324  src.nb_elements__ = 0;
1325  src.safe_iterators__.clear();
1326  }
1327 
1328  return *this;
1329  }
1330 
1331  // the iterator pointing to the end of the List
1332  template < typename Val, typename Alloc >
1333  INLINE const ListConstIteratorSafe< Val >&
1334  List< Val, Alloc >::cendSafe() const noexcept {
1335  return *(
1336  reinterpret_cast< const ListConstIteratorSafe< Val >* >(list_end_safe__));
1337  }
1338 
1339  // the iterator pointing to the end of the List
1340  template < typename Val, typename Alloc >
1342  return *(reinterpret_cast< const ListIteratorSafe< Val >* >(list_end_safe__));
1343  }
1344 
1345  // the iterator pointing to the end of the List
1346  template < typename Val, typename Alloc >
1347  INLINE const ListConstIterator< Val >&
1348  List< Val, Alloc >::cend() const noexcept {
1349  return *(reinterpret_cast< const ListConstIterator< Val >* >(list_end__));
1350  }
1351 
1352  // the iterator pointing to the end of the List
1353  template < typename Val, typename Alloc >
1355  return *(reinterpret_cast< const ListIterator< Val >* >(list_end__));
1356  }
1357 
1358  // the iterator pointing to the end of the List
1359  template < typename Val, typename Alloc >
1360  INLINE const ListConstIterator< Val >& List< Val, Alloc >::end() const noexcept {
1361  return *(reinterpret_cast< const ListConstIterator< Val >* >(list_end__));
1362  }
1363 
1364  // the iterator pointing to the rend (just before the beginning) of the List
1365  template < typename Val, typename Alloc >
1366  INLINE const ListConstIteratorSafe< Val >&
1368  return *(
1369  reinterpret_cast< const ListConstIteratorSafe< Val >* >(list_end_safe__));
1370  }
1371 
1372  // the iterator pointing to the rend (just before the beginning) of the List
1373  template < typename Val, typename Alloc >
1375  return *(reinterpret_cast< const ListIteratorSafe< Val >* >(list_end_safe__));
1376  }
1377 
1378  // the iterator pointing to the rend (just before the beginning) of the List
1379  template < typename Val, typename Alloc >
1380  INLINE const ListConstIterator< Val >&
1381  List< Val, Alloc >::crend() const noexcept {
1382  return *(reinterpret_cast< const ListConstIterator< Val >* >(list_end__));
1383  }
1384 
1385  // the iterator pointing to the rend (just before the beginning) of the List
1386  template < typename Val, typename Alloc >
1388  return *(reinterpret_cast< const ListIterator< Val >* >(list_end__));
1389  }
1390 
1391  // the iterator pointing to the rend (just before the beginning) of the List
1392  template < typename Val, typename Alloc >
1393  INLINE const ListConstIterator< Val >&
1394  List< Val, Alloc >::rend() const noexcept {
1395  return *(reinterpret_cast< const ListConstIterator< Val >* >(list_end__));
1396  }
1397 
1398  // the iterator pointing to the beginning of the List
1399  template < typename Val, typename Alloc >
1401  return ListConstIteratorSafe< Val >{*this};
1402  }
1403 
1404  // the iterator pointing to the beginning of the List
1405  template < typename Val, typename Alloc >
1407  return ListIteratorSafe< Val >{*this};
1408  }
1409 
1410  // the iterator pointing to the beginning of the List
1411  template < typename Val, typename Alloc >
1413  return ListConstIterator< Val >{*this};
1414  }
1415 
1416  // the iterator pointing to the beginning of the List
1417  template < typename Val, typename Alloc >
1419  return ListIterator< Val >{*this};
1420  }
1421 
1422  // the iterator pointing to the beginning of the List
1423  template < typename Val, typename Alloc >
1425  return ListConstIterator< Val >{*this};
1426  }
1427 
1428  // the iterator pointing to the rbegin (the last element) of the List
1429  template < typename Val, typename Alloc >
1431  if (nb_elements__)
1432  return ListConstIteratorSafe< Val >{*this, nb_elements__ - 1};
1433  else
1435  }
1436 
1437  // the iterator pointing to the rbegin (the last element) of the List
1438  template < typename Val, typename Alloc >
1440  if (nb_elements__)
1441  return ListIteratorSafe< Val >{*this, nb_elements__ - 1};
1442  else
1443  return ListIteratorSafe< Val >{};
1444  }
1445 
1446  // the iterator pointing to the rbegin (the last element) of the List
1447  template < typename Val, typename Alloc >
1449  if (nb_elements__)
1450  return ListConstIterator< Val >{*this, nb_elements__ - 1};
1451  else
1452  return ListConstIterator< Val >{};
1453  }
1454 
1455  // the iterator pointing to the rbegin (the last element) of the List
1456  template < typename Val, typename Alloc >
1458  if (nb_elements__)
1459  return ListIterator< Val >{*this, nb_elements__ - 1};
1460  else
1461  return ListIterator< Val >{};
1462  }
1463 
1464  // the iterator pointing to the rbegin (the last element) of the List
1465  template < typename Val, typename Alloc >
1467  if (nb_elements__)
1468  return ListConstIterator< Val >{*this, nb_elements__ - 1};
1469  else
1470  return ListConstIterator< Val >{};
1471  }
1472 
1473  // create a new bucket with a given value
1474  template < typename Val, typename Alloc >
1475  INLINE ListBucket< Val >*
1476  List< Val, Alloc >::createBucket__(const Val& val) const {
1477  // create a new bucket (catch allocation and construction exceptions)
1478  ListBucket< Val >* new_elt = alloc_bucket__.allocate(1);
1479 
1480  try {
1481  alloc_bucket__.construct(new_elt, val);
1482  } catch (...) {
1483  alloc_bucket__.deallocate(new_elt, 1);
1484  throw;
1485  }
1486 
1487  return new_elt;
1488  }
1489 
1490  // create a new bucket with a given value
1491  template < typename Val, typename Alloc >
1493  // create a new bucket (catch allocation and construction exceptions)
1494  ListBucket< Val >* new_elt = alloc_bucket__.allocate(1);
1495 
1496  try {
1497  alloc_bucket__.construct(new_elt, std::move(val));
1498  } catch (...) {
1499  alloc_bucket__.deallocate(new_elt, 1);
1500  throw;
1501  }
1502 
1503  return new_elt;
1504  }
1505 
1506  // create an emplace bucket
1507  template < typename Val, typename Alloc >
1508  template < typename... Args >
1509  INLINE ListBucket< Val >*
1511  // create a new bucket (catch allocation and construction exceptions)
1512  ListBucket< Val >* new_elt = alloc_bucket__.allocate(1);
1513 
1514  try {
1515  alloc_bucket__.construct(new_elt,
1517  std::forward< Args >(args)...);
1518  } catch (...) {
1519  alloc_bucket__.deallocate(new_elt, 1);
1520  throw;
1521  }
1522 
1523  return new_elt;
1524  }
1525 
1526  // insert a bucket at the front of the list
1527  template < typename Val, typename Alloc >
1529  new_elt->next__ = deb_list__;
1530 
1531  if (deb_list__ != nullptr)
1532  deb_list__->prev__ = new_elt;
1533  else
1534  end_list__ = new_elt;
1535 
1536  deb_list__ = new_elt;
1537 
1538  // update the number of elements
1539  ++nb_elements__;
1540 
1541  // return the inserted element
1542  return new_elt->val__;
1543  }
1544 
1545  // insert a bucket at the end of the list
1546  template < typename Val, typename Alloc >
1548  // place the bucket at the end of the list
1549  new_elt->prev__ = end_list__;
1550 
1551  if (end_list__ != nullptr)
1552  end_list__->next__ = new_elt;
1553  else
1554  deb_list__ = new_elt;
1555 
1556  end_list__ = new_elt;
1557 
1558  // update the number of elements
1559  ++nb_elements__;
1560 
1561  // returns the current value
1562  return new_elt->val__;
1563  }
1564 
1565  // Insertion of a new element (a copy) at the beginning of the chained list.
1566  template < typename Val, typename Alloc >
1567  INLINE Val& List< Val, Alloc >::pushFront(const Val& val) {
1568  return pushFront__(createBucket__(val));
1569  }
1570 
1571  // Insertion of a new element (a copy) at the beginning of the chained list.
1572  template < typename Val, typename Alloc >
1573  INLINE Val& List< Val, Alloc >::pushFront(Val&& val) {
1574  return pushFront__(createBucket__(std::move(val)));
1575  }
1576 
1577  // an alias for pushFront used for STL compliance
1578  template < typename Val, typename Alloc >
1579  template < typename... Args >
1580  INLINE Val& List< Val, Alloc >::push_front(Args&&... args) {
1581  return pushFront(std::forward< Args >(args)...);
1582  }
1583 
1584  // emplace elements at the beginning of the chained list
1585  template < typename Val, typename Alloc >
1586  template < typename... Args >
1587  INLINE Val& List< Val, Alloc >::emplaceFront(Args&&... args) {
1588  return pushFront__(createEmplaceBucket__(std::forward< Args >(args)...));
1589  }
1590 
1591  // Insertion of a new element (a copy) at the end of the chained list.
1592  template < typename Val, typename Alloc >
1593  INLINE Val& List< Val, Alloc >::pushBack(const Val& val) {
1594  return pushBack__(createBucket__(val));
1595  }
1596 
1597  // pushBack for rvalues
1598  template < typename Val, typename Alloc >
1599  INLINE Val& List< Val, Alloc >::pushBack(Val&& val) {
1600  return pushBack__(createBucket__(std::move(val)));
1601  }
1602 
1603  // an alias for pushBack used for STL compliance
1604  template < typename Val, typename Alloc >
1605  template < typename... Args >
1606  INLINE Val& List< Val, Alloc >::push_back(Args&&... args) {
1607  return pushBack(std::forward< Args >(args)...);
1608  }
1609 
1610  // emplace elements at the end of the chained list
1611  template < typename Val, typename Alloc >
1612  template < typename... Args >
1613  INLINE Val& List< Val, Alloc >::emplaceBack(Args&&... args) {
1614  return pushBack__(createEmplaceBucket__(std::forward< Args >(args)...));
1615  }
1616 
1617  // Insertion of a new element at the end of the chained list (alias of
1618  // pushBack)
1619  template < typename Val, typename Alloc >
1620  INLINE Val& List< Val, Alloc >::insert(const Val& val) {
1621  return pushBack(val);
1622  }
1623 
1624  // insert for rvalues
1625  template < typename Val, typename Alloc >
1626  INLINE Val& List< Val, Alloc >::insert(Val&& val) {
1627  return pushBack(std::move(val));
1628  }
1629 
1630  // returns the bucket corresponding to the ith position
1631  template < typename Val, typename Alloc >
1632  INLINE ListBucket< Val >*
1634  ListBucket< Val >* ptr;
1635 
1636  if (i < nb_elements__ / 2) {
1637  for (ptr = deb_list__; i; --i, ptr = ptr->next__) {}
1638  } else {
1639  for (ptr = end_list__, i = nb_elements__ - i - 1; i;
1640  --i, ptr = ptr->prev__) {}
1641  }
1642 
1643  return ptr;
1644  }
1645 
1646  // insert a new bucket before another one
1647  template < typename Val, typename Alloc >
1649  ListBucket< Val >* current_elt) {
1650  new_elt->next__ = current_elt;
1651  new_elt->prev__ = current_elt->prev__;
1652  current_elt->prev__ = new_elt;
1653 
1654  if (new_elt->prev__ == nullptr)
1655  deb_list__ = new_elt;
1656  else
1657  new_elt->prev__->next__ = new_elt;
1658 
1659  // update the number of elements
1660  ++nb_elements__;
1661 
1662  // returns the current value
1663  return new_elt->val__;
1664  }
1665 
1666  // insert a new bucket after another one
1667  template < typename Val, typename Alloc >
1669  ListBucket< Val >* current_elt) {
1670  new_elt->prev__ = current_elt;
1671  new_elt->next__ = current_elt->next__;
1672  current_elt->next__ = new_elt;
1673 
1674  if (new_elt->next__ == nullptr)
1675  end_list__ = new_elt;
1676  else
1677  new_elt->next__->prev__ = new_elt;
1678 
1679  // update the number of elements
1680  ++nb_elements__;
1681 
1682  // returns the current value
1683  return new_elt->val__;
1684  }
1685 
1686  // inserts a new element at the ith pos of the chained list
1687  template < typename Val, typename Alloc >
1688  INLINE Val& List< Val, Alloc >::insert(Size pos, const Val& val) {
1689  // if ther are fewer elements than pos, put the value at the end of the list
1690  if (nb_elements__ <= pos) { return pushBack(val); }
1691 
1692  return insertBefore__(createBucket__(val), getIthBucket__(pos));
1693  }
1694 
1695  // insert an rvalue at the ith pos of the chained list
1696  template < typename Val, typename Alloc >
1697  INLINE Val& List< Val, Alloc >::insert(Size pos, Val&& val) {
1698  // if ther are fewer elements than pos, put the value at the end of the list
1699  if (nb_elements__ <= pos) { return pushBack(std::move(val)); }
1700 
1701  return insertBefore__(createBucket__(std::move(val)), getIthBucket__(pos));
1702  }
1703 
1704  // inserts a new bucket before or after the location pointed to by an
1705  // iterator
1706  template < typename Val, typename Alloc >
1708  ListBucket< Val >* new_elt,
1709  location place) {
1710  // find the location around which the new element should be inserted
1711  ListBucket< Val >* ptr;
1712 
1713  if (iter.null_pointing__) {
1714  if (place == location::BEFORE) {
1715  ptr = iter.next_current_bucket__;
1716  } else {
1717  ptr = iter.prev_current_bucket__;
1718  }
1719  } else {
1720  ptr = iter.getBucket__();
1721  }
1722 
1723  if (ptr == nullptr) {
1724  // here, we are at the end of the list
1725  return pushBack__(new_elt);
1726  } else {
1727  switch (place) {
1728  case location::BEFORE: return insertBefore__(new_elt, ptr);
1729 
1730  case location::AFTER: return insertAfter__(new_elt, ptr);
1731 
1732  default:
1733  GUM_ERROR(FatalError, "List insertion for this location unimplemented");
1734  }
1735  }
1736  }
1737 
1738  // inserts a new bucket before or after the location pointed to by an
1739  // iterator
1740  template < typename Val, typename Alloc >
1742  ListBucket< Val >* new_elt,
1743  location place) {
1744  // find the location around which the new element should be inserted
1745  ListBucket< Val >* ptr = iter.getBucket__();
1746 
1747  if (ptr == nullptr) {
1748  // here, we are at the end of the list
1749  return pushBack__(new_elt);
1750  } else {
1751  switch (place) {
1752  case location::BEFORE: return insertBefore__(new_elt, ptr);
1753 
1754  case location::AFTER: return insertAfter__(new_elt, ptr);
1755 
1756  default:
1757  GUM_ERROR(FatalError, "List insertion for this location unimplemented");
1758  }
1759  }
1760  }
1761 
1762  // inserts a new element before or after the location pointed to by an
1763  // iterator
1764  template < typename Val, typename Alloc >
1766  const Val& val,
1767  location place) {
1768  // if the iterator does not point to the list, raise an exception
1769  if (iter.list__ != this) {
1771  "the iterator does not point to the correct list");
1772  }
1773 
1774  return insert__(iter, createBucket__(val), place);
1775  }
1776 
1777  // inserts a new element before or after the location pointed to by an
1778  // iterator
1779  template < typename Val, typename Alloc >
1781  Val&& val,
1782  location place) {
1783  // if the iterator does not point to the list, raise an exception
1784  if (iter.list__ != this) {
1786  "the iterator does not point to the correct list");
1787  }
1788 
1789  return insert__(iter, createBucket__(std::move(val)), place);
1790  }
1791 
1792  // inserts a new element before or after the location pointed to by an
1793  // iterator
1794  template < typename Val, typename Alloc >
1796  const Val& val,
1797  location place) {
1798  return insert__(iter, createBucket__(val), place);
1799  }
1800 
1801  // inserts a new element before or after the location pointed to by an
1802  // iterator
1803  template < typename Val, typename Alloc >
1805  Val&& val,
1806  location place) {
1807  return insert__(iter, createBucket__(std::move(val)), place);
1808  }
1809 
1810  // emplace a new element before a given iterator
1811  template < typename Val, typename Alloc >
1812  template < typename... Args >
1814  Args&&... args) {
1815  return insert__(iter,
1816  createEmplaceBucket__(std::forward< Args >(args)...),
1817  location::BEFORE);
1818  }
1819 
1820  // emplace a new element before a given iterator
1821  template < typename Val, typename Alloc >
1822  template < typename... Args >
1824  Args&&... args) {
1825  return insert__(iter,
1826  createEmplaceBucket__(std::forward< Args >(args)...),
1827  location::BEFORE);
1828  }
1829 
1830  // returns a reference to first element of a list
1831  template < typename Val, typename Alloc >
1832  INLINE Val& List< Val, Alloc >::front() const {
1833  if (nb_elements__ == Size(0)) {
1834  GUM_ERROR(NotFound, "not enough elements in the chained list");
1835  }
1836 
1837  return deb_list__->val__;
1838  }
1839 
1840  // returns a reference to last element of a list
1841  template < typename Val, typename Alloc >
1842  INLINE Val& List< Val, Alloc >::back() const {
1843  if (nb_elements__ == Size(0)) {
1844  GUM_ERROR(NotFound, "not enough elements in the chained list");
1845  }
1846 
1847  return end_list__->val__;
1848  }
1849 
1850  // returns the number of elements in the list.
1851  template < typename Val, typename Alloc >
1852  INLINE Size List< Val, Alloc >::size() const noexcept {
1853  return nb_elements__;
1854  }
1855 
1856  // checks whether there exists a given element in the list.
1857  template < typename Val, typename Alloc >
1858  INLINE bool List< Val, Alloc >::exists(const Val& val) const {
1859  for (ListBucket< Val >* ptr = deb_list__; ptr != nullptr; ptr = ptr->next__)
1860  if (ptr->val__ == val) return true;
1861 
1862  return false;
1863  }
1864 
1865  // suppresses a given bucket from a chained list.
1866  template < typename Val, typename Alloc >
1868  // perform deletion only if there is a bucket to remove
1869  if (bucket != nullptr) {
1870  // update the iterators pointing on this element
1871  for (const auto ptr_iter: safe_iterators__) {
1872  if (ptr_iter->bucket__ == bucket) {
1873  ptr_iter->next_current_bucket__ = bucket->prev__;
1874  ptr_iter->prev_current_bucket__ = bucket->next__;
1875  ptr_iter->bucket__ = nullptr;
1876  ptr_iter->null_pointing__ = true;
1877  } else {
1878  if (ptr_iter->null_pointing__) {
1879  if (ptr_iter->next_current_bucket__ == bucket)
1880  ptr_iter->next_current_bucket__ = bucket->prev__;
1881 
1882  if (ptr_iter->prev_current_bucket__ == bucket)
1883  ptr_iter->prev_current_bucket__ = bucket->next__;
1884  }
1885  }
1886  }
1887 
1888  // set properly the begin and end of the chained list (the other chainings
1889  // will be performed by operator delete)
1890  if (bucket->prev__ == nullptr)
1891  deb_list__ = bucket->next__;
1892  else
1893  bucket->prev__->next__ = bucket->next__;
1894 
1895  if (bucket->next__ == nullptr)
1896  end_list__ = bucket->prev__;
1897  else
1898  bucket->next__->prev__ = bucket->prev__;
1899 
1900  // remove the current element src the list
1901  alloc_bucket__.destroy(bucket);
1902  alloc_bucket__.deallocate(bucket, 1);
1903 
1904  --nb_elements__;
1905  }
1906  }
1907 
1908  // erases the ith element of the List (the first one is in position 0)
1909  template < typename Val, typename Alloc >
1911  if (i >= nb_elements__) return;
1912 
1913  // erase the ith bucket
1914  erase__(getIthBucket__(i));
1915  }
1916 
1917  // erases the element of the List pointed to by the iterator
1918  template < typename Val, typename Alloc >
1919  INLINE void List< Val, Alloc >::erase(const iterator_safe& iter) {
1920  erase__(iter.getBucket__());
1921  }
1922 
1923  // erases the element of the List pointed to by the iterator
1924  template < typename Val, typename Alloc >
1926  erase__(iter.getBucket__());
1927  }
1928 
1929  // returns the bucket corresponding to a given value.
1930  template < typename Val, typename Alloc >
1931  INLINE ListBucket< Val >*
1932  List< Val, Alloc >::getBucket__(const Val& val) const noexcept {
1933  for (ListBucket< Val >* ptr = deb_list__; ptr != nullptr; ptr = ptr->next__)
1934  if (ptr->val__ == val) return ptr;
1935 
1936  return nullptr;
1937  }
1938 
1939  // erases the first element encountered with a given value
1940  template < typename Val, typename Alloc >
1941  INLINE void List< Val, Alloc >::eraseByVal(const Val& val) {
1942  erase__(getBucket__(val));
1943  }
1944 
1945  // erases all the elements encountered with a given value
1946  template < typename Val, typename Alloc >
1947  INLINE void List< Val, Alloc >::eraseAllVal(const Val& val) {
1948  for (ListBucket< Val >*iter = deb_list__, *next_bucket = nullptr;
1949  iter != nullptr;
1950  iter = next_bucket) {
1951  next_bucket = iter->next__;
1952 
1953  if (val == iter->val__) erase__(iter);
1954  }
1955  }
1956 
1957  // removes the last element of a List
1958  template < typename Val, typename Alloc >
1960  erase__(end_list__);
1961  }
1962 
1963  // removes the first element of a List
1964  template < typename Val, typename Alloc >
1966  erase__(deb_list__);
1967  }
1968 
1969  // returns a boolean indicating whether the chained list is empty
1970  template < typename Val, typename Alloc >
1971  INLINE bool List< Val, Alloc >::empty() const noexcept {
1972  return (nb_elements__ == Size(0));
1973  }
1974 
1975  // displays the content of a chained list
1976  template < typename Val, typename Alloc >
1977  std::string List< Val, Alloc >::toString() const {
1978  bool deja = false;
1979  std::stringstream stream;
1980  stream << "[";
1981 
1982  for (ListBucket< Val >* ptr = deb_list__; ptr != nullptr;
1983  ptr = ptr->next__, deja = true) {
1984  if (deja) stream << " --> ";
1985 
1986  stream << ptr->val__;
1987  }
1988 
1989  stream << "]";
1990 
1991  return stream.str();
1992  }
1993 
1994  // creates a list of mountains src a list of val
1995  template < typename Val, typename Alloc >
1996  template < typename Mount, typename OtherAlloc >
1998  // create a new empty list
2000 
2001  // fill the new list
2002  for (const_iterator iter = begin(); iter != end(); ++iter) {
2003  list.pushBack(f(*iter));
2004  }
2005 
2006  return list;
2007  }
2008 
2009  // creates a list of mountains src a list of val
2010  template < typename Val, typename Alloc >
2011  template < typename Mount, typename OtherAlloc >
2013  // create a new empty list
2015 
2016  // fill the new list
2017  for (const_iterator iter = begin(); iter != end(); ++iter) {
2018  list.pushBack(f(*iter));
2019  }
2020 
2021  return list;
2022  }
2023 
2024  // creates a list of mountains src a list of val
2025  template < typename Val, typename Alloc >
2026  template < typename Mount, typename OtherAlloc >
2027  List< Mount, OtherAlloc > List< Val, Alloc >::map(Mount (*f)(const Val&)) const {
2028  // create a new empty list
2030 
2031  // fill the new list
2032  for (const_iterator iter = begin(); iter != end(); ++iter) {
2033  list.pushBack(f(*iter));
2034  }
2035 
2036  return list;
2037  }
2038 
2039  // creates a list of mountains with a given value src a list of val
2040  template < typename Val, typename Alloc >
2041  template < typename Mount, typename OtherAlloc >
2043  // create a new empty list
2045 
2046  // fill the new list
2047  for (Size i = Size(0); i < nb_elements__; ++i)
2048  list.pushBack(mount);
2049 
2050  return list;
2051  }
2052 
2053  // creates and insert a new element at the end of the list (alias of
2054  // pushBack).
2055  template < typename Val, typename Alloc >
2056  INLINE Val& List< Val, Alloc >::operator+=(const Val& val) {
2057  return pushBack(val);
2058  }
2059 
2060  // creates and insert a new element at the end of the list (alias of
2061  // pushBack).
2062  template < typename Val, typename Alloc >
2063  INLINE Val& List< Val, Alloc >::operator+=(Val&& val) {
2064  return pushBack(std::move(val));
2065  }
2066 
2067  // checks whether two lists are identical (same elements in the same order)
2068  template < typename Val, typename Alloc >
2069  template < typename OtherAlloc >
2070  INLINE bool
2072  // check if the two lists have at least the same number of elements
2073  if (nb_elements__ != src.nb_elements__) return false;
2074 
2075  // parse the two lists
2076  for (ListBucket< Val >*iter1 = deb_list__, *iter2 = src.deb_list__;
2077  iter1 != nullptr;
2078  iter1 = iter1->next__, iter2 = iter2->next__)
2079  if (*iter1 != *iter2) return false;
2080 
2081  return true;
2082  }
2083 
2084  // checks whether two lists are different (different elements or orders)
2085  template < typename Val, typename Alloc >
2086  template < typename OtherAlloc >
2087  INLINE bool
2089  return !operator==(src);
2090  }
2091 
2092  // returns the ith element in the current chained list.
2093  template < typename Val, typename Alloc >
2094  INLINE Val& List< Val, Alloc >::operator[](const Size i) {
2095  // check if we can return the element we ask for
2096  if (i >= nb_elements__) {
2097  GUM_ERROR(NotFound, "not enough elements in the chained list");
2098  }
2099 
2100  return **getIthBucket__(i);
2101  }
2102 
2103  // returns the ith element in the current chained list.
2104  template < typename Val, typename Alloc >
2105  INLINE const Val& List< Val, Alloc >::operator[](const Size i) const {
2106  // check if we can return the element we ask for
2107  if (i >= nb_elements__) {
2108  GUM_ERROR(NotFound, "not enough elements in the chained list");
2109  }
2110 
2111  return **getIthBucket__(i);
2112  }
2113 
2114  // replace the current list with another one
2115  template < typename Val, typename Alloc >
2116  INLINE void List< Val, Alloc >::swap(List& other_list) {
2117  std::swap(deb_list__, other_list.deb_list__);
2118  std::swap(end_list__, other_list.end_list__);
2119  std::swap(nb_elements__, other_list.nb_elements__);
2120  std::swap(safe_iterators__, other_list.safe_iterators__);
2121  std::swap(alloc_bucket__, other_list.alloc_bucket__);
2122  }
2123 
2124  // A \c << operator for List
2125  template < typename Val >
2126  std::ostream& operator<<(std::ostream& stream, const List< Val >& list) {
2127  stream << list.toString();
2128  return stream;
2129  }
2130 
2131 } /* namespace gum */
Size nb_elements__
The number of elements in the list.
Definition: list.h:1308
ListBucket< Val > * bucket__
The bucket in the chained list pointed to by the iterator.
Definition: list.h:1728
const List< Val, std::allocator< Val > > * list__
The list the iterator is pointing to.
Definition: list.h:2253
ListConstIteratorSafe() noexcept
Default constructor.
Definition: list_tpl.h:493
ListIterator< Val > & operator-=(difference_type i) noexcept
Makes the iterator point to i elements befor in the List.
Definition: list_tpl.h:453
const Val & operator*() const
Gives access to the content of the iterator.
Definition: list_tpl.h:338
ListConstIteratorSafe< Val > & operator+=(difference_type i) noexcept
Makes the iterator point to i elements further in the List.
Definition: list_tpl.h:850
ListConstIteratorSafe< Val > operator+(difference_type i) noexcept
Returns a new iterator pointing to i further elements in the gum::List.
Definition: list_tpl.h:911
Val val__
Val is the value contained in the box.
Definition: list.h:249
ListConstIteratorSafe< Val > & opPlus__(Size i) noexcept
Makes the iterator point to the next element in the List.
Definition: list_tpl.h:813
const Val & operator*() const
Gives access to the content of the iterator.
Definition: list_tpl.h:955
ListConstIterator< Val > & operator+=(difference_type i) noexcept
Makes the iterator point to i elements further in the List.
Definition: list_tpl.h:265
Safe iterators for Lists.
Definition: list.h:2342
Unsafe but fast iterators for Lists.
Definition: list.h:1794
location
Locations around iterators where insertions of new elements can take / place.
Definition: list.h:396
#define GUM_DEFAULT_ITERATOR_NUMBER
Definition: list.h:42
STL namespace.
ListBucket< Val > * bucket__
The bucket in the chained list pointed to by the iterator.
Definition: list.h:2256
ListIterator< Val > & operator++() noexcept
Makes the iterator point to the next element in the List.
Definition: list_tpl.h:431
std::ptrdiff_t difference_type
Types for STL compliance.
Definition: list.h:1518
Val & operator*()
Gives access to the iterator&#39;s content.
Definition: list_tpl.h:481
void swap(HashTable< LpCol, double > *&a, HashTable< LpCol, double > *&b)
Swap the addresses of two pointers to hashTables.
ListBucket< Val > * end_list__
A pointer on the last element of the chained list.
Definition: list.h:1305
ListConstIteratorSafe< Val > & operator-=(difference_type i) noexcept
Makes the iterator point to i elements befor in the List.
Definition: list_tpl.h:899
Generic doubly linked lists.
Definition: list.h:372
ListConstIterator< Val > & operator++() noexcept
Makes the iterator point to the next element in the List.
Definition: list_tpl.h:255
Copyright 2005-2020 Pierre-Henri WUILLEMIN() & Christophe GONZALES() info_at_agrum_dot_org.
Definition: agrum.h:25
bool operator==(const ListConstIteratorSafe< Val > &src) const
Checks whether two iterators point toward the same elements.
Definition: list_tpl.h:935
ListBucket< Val > * getBucket__() const noexcept
Returns the bucket the iterator is pointing to.
Definition: list_tpl.h:704
ListIterator< Val > & operator=(const ListIterator< Val > &src) noexcept
Copy operator.
Definition: list_tpl.h:408
ListConstIterator< Val > & operator-=(difference_type i) noexcept
Makes the iterator point to i elements befor in the List.
Definition: list_tpl.h:288
~ListIteratorSafe()
Class Desctructor.
Definition: list_tpl.h:1046
ListIteratorSafe< Val > operator-(difference_type i) noexcept
Returns a new iterator pointing to i preceding elements in the gum::List.
Definition: list_tpl.h:1089
ListIteratorSafe< Val > & operator+=(difference_type i) noexcept
Makes the iterator point to i elements further in the List.
Definition: list_tpl.h:1059
ListIteratorSafe< Val > & operator++() noexcept
Makes the iterator point to the next element in the List.
Definition: list_tpl.h:1052
Emplace
C dummy type for the emplace constructor.
Definition: list.h:112
ListIterator< Val > & operator+=(difference_type i) noexcept
Makes the iterator point to i elements further in the List.
Definition: list_tpl.h:438
ListBucket< Val > * next_current_bucket__
The bucket we should start from when we are pointing on a deleted bucket and we decide to do a ++...
Definition: list.h:2260
ListBucket()=delete
Removes empty constructor.
ListConstIterator< Val > & operator=(const ListConstIterator< Val > &src) noexcept
Copy operator.
Definition: list_tpl.h:207
ListIterator< Val > operator-(difference_type i) noexcept
Returns a new iterator pointing to i preceding elements in the gum::List.
Definition: list_tpl.h:468
ListIteratorSafe< Val > & operator=(const ListIteratorSafe< Val > &src)
Copy operator.
Definition: list_tpl.h:1027
ListConstIteratorSafe< Val > operator-(difference_type i) noexcept
Returns a new iterator pointing to i preceding elements in the gum::List.
Definition: list_tpl.h:918
BucketAllocator alloc_bucket__
The allocator for the buckets.
Definition: list.h:1314
Copyright 2005-2020 Pierre-Henri WUILLEMIN() & Christophe GONZALES() info_at_agrum_dot_org.
std::ptrdiff_t difference_type
Types for STL compliance.
Definition: list.h:2040
ListConstIteratorSafe< Val > & operator--() noexcept
Makes the iterator point to the preceding element in the List.
Definition: list_tpl.h:863
void copy_elements__(const List< Val, OtherAlloc > &src)
A function used to perform copies of elements of Lists.
Definition: list_tpl.h:1115
ListIteratorSafe< Val > & operator-=(difference_type i) noexcept
Makes the iterator point to i elements befor in the List.
Definition: list_tpl.h:1074
LpExpr operator+(LpExpr &&lhs, const T2 &rhs)
Overload of operator + between anything ( a scalar, a variable or an expression ) and anything except...
Val & pushBack(const Val &val)
Inserts a new element (a copy) at the end of the chained list.
Definition: list_tpl.h:1593
bool null_pointing__
Indicates whether the bucket the iterator points to has been deleted.
Definition: list.h:2267
ListBucket< Val > * getBucket__() const noexcept
Returns the bucket the iterator is pointing to.
Definition: list_tpl.h:229
bool operator==(const TiXmlString &a, const TiXmlString &b)
Definition: tinystr.h:243
std::ptrdiff_t difference_type
Types for STL compliance.
Definition: list.h:2352
Unsafe but fast const iterators for Lists.
Definition: list.h:1508
ListIteratorSafe() noexcept
Default constructor.
Definition: list_tpl.h:984
void setToEnd()
Positions the iterator to the end of the list.
Definition: list_tpl.h:722
~ListIterator() noexcept
Class destructor.
Definition: list_tpl.h:425
LpExpr operator*(const SCALAR &lhs, const LpCol &rhs)
Overload of operator * between a scalar and a variable.
Val * operator->()
Dereferences the value pointed to by the iterator.
Definition: list_tpl.h:1096
~ListConstIteratorSafe()
Class Desctructor.
Definition: list_tpl.h:693
void removeFromSafeList__() const
Remove the iterator for its list&#39; safe iterators list.
Definition: list_tpl.h:593
Val & operator*()
Gives access to the content of the iterator.
Definition: list_tpl.h:1102
std::vector< const_iterator_safe *> safe_iterators__
The list of "safe" iterators attached to the list.
Definition: list.h:1311
void clear()
Makes the iterator point toward nothing.
Definition: list_tpl.h:710
bool operator!=(const TiXmlString &a, const TiXmlString &b)
Definition: tinystr.h:251
bool operator!=(const ListConstIteratorSafe< Val > &src) const
Checks whether two iterators point toward different elements.
Definition: list_tpl.h:925
List()
A basic constructor that creates an empty list.
Definition: list_tpl.h:1187
Safe const iterators for Lists.
Definition: list.h:2030
ListConstIterator< Val > & operator--() noexcept
Makes the iterator point to the preceding element in the List.
Definition: list_tpl.h:278
Val * operator->()
Dereferences the value pointed to by the iterator.
Definition: list_tpl.h:475
ListConstIteratorSafe< Val > & operator++() noexcept
Makes the iterator point to the next element in the List.
Definition: list_tpl.h:738
Bucket for a chained list.
Definition: list.h:105
Size Idx
Type for indexes.
Definition: types.h:53
INLINE ListConstIteratorSafe< Val >::difference_type operator-(const ListConstIteratorSafe< Val > &iter1, const ListConstIteratorSafe< Val > &iter2)
For STL compliance, a distance operator.
Definition: list_tpl.h:966
ListConstIteratorSafe< Val > & operator=(const ListConstIteratorSafe< Val > &src)
Copy operator.
Definition: list_tpl.h:607
ListConstIteratorSafe< Val > & opMinus__(Size i) noexcept
Makes the iterator point to i elements before in the List.
Definition: list_tpl.h:775
bool isEnd() const
Returns a bool indicating whether the iterator points to the end of the list.
Definition: list_tpl.h:729
std::size_t Size
In aGrUM, hashed values are unsigned long int.
Definition: types.h:48
void clear()
Deletes all the elements of a chained list.
Definition: list_tpl.h:1165
ListIteratorSafe< Val > operator+(difference_type i) noexcept
Returns a new iterator pointing to i further elements in the gum::List.
Definition: list_tpl.h:1082
ListIterator< Val > operator+(difference_type i) noexcept
Returns a new iterator pointing to i further elements in the gum::List.
Definition: list_tpl.h:461
ListBucket< Val > * prev_current_bucket__
The bucket we should start from when we are pointing on a deleted bucket and we decide to do a –...
Definition: list.h:2264
std::ptrdiff_t difference_type
Types for STL compliance.
Definition: list.h:1804
const Val * operator->() const
Dereferences the value pointed to by the iterator.
Definition: list_tpl.h:328
ListBucket< Val > * prev__
Chaining toward the adjacent elements.
Definition: list.h:244
ListIteratorSafe< Val > & operator--() noexcept
Makes the iterator point to the preceding element in the List.
Definition: list_tpl.h:1067
ListBucket< Val > * next__
Chaining toward the adjacent elements.
Definition: list.h:245
#define GUM_ERROR(type, msg)
Definition: exceptions.h:55
ListBucket< Val > * deb_list__
A pointer on the first element of the chained list.
Definition: list.h:1302
ListIterator< Val > & operator--() noexcept
Makes the iterator point to the preceding element in the List.
Definition: list_tpl.h:446
const Val * operator->() const
Dereferences the value pointed to by the iterator.
Definition: list_tpl.h:945