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