Generic doubly linked lists. More...

#include <agrum/base/core/list.h>

Public Types
enum class	location { BEFORE , AFTER }
	Locations around iterators where insertions of new elements can take / place. More...

using	value_type = Val
	Types for STL compliance.
using	reference = Val&
	Types for STL compliance.
using	const_reference = const Val&
	Types for STL compliance.
using	pointer = Val*
	Types for STL compliance.
using	const_pointer = const Val*
	Types for STL compliance.
using	size_type = Size
	Types for STL compliance.
using	difference_type = std::ptrdiff_t
	Types for STL compliance.
using	iterator = ListIterator< Val >
	Types for STL compliance.
using	const_iterator = ListConstIterator< Val >
	Types for STL compliance.
using	iterator_safe = ListIteratorSafe< Val >
	Types for STL compliance.
using	const_iterator_safe = ListConstIteratorSafe< Val >
	Types for STL compliance.

Public Member Functions
Constructors / Destructors
	List ()
	A basic constructor that creates an empty list.
	List (const List< Val > &src)
	Copy constructor.
	List (List< Val > &&src) noexcept
	Move constructor.
	List (std::initializer_list< Val > list)
	Initializer_list constructor.
	~List ()
	Class destructor.
Iterators
const const_iterator_safe &	cendSafe () const noexcept
	Returns a safe const iterator pointing to the end of the List.
const iterator_safe &	endSafe () noexcept
	Returns a safe iterator pointing to the end of the List.
const const_iterator_safe &	crendSafe () const noexcept
	Return a safe const iterator pointing just before the beginning of the List.
const iterator_safe &	rendSafe () noexcept
	Returns a safe iterator pointing just before the beginning of the List.
const_iterator_safe	cbeginSafe () const
	Returns a safe const iterator pointing to the beginning of the List.
iterator_safe	beginSafe ()
	Returns a safe iterator pointing to the beginning of the List.
const_iterator_safe	crbeginSafe () const
	Returns a safe const iterator pointing to the last element of the List.
iterator_safe	rbeginSafe ()
	Returns a safe iterator pointing to the last element of the List.
const const_iterator &	cend () const noexcept
	Returns an unsafe const iterator pointing to the end of the List.
const iterator &	end () noexcept
	Returns an unsafe iterator pointing to the end of the List.
const const_iterator &	end () const noexcept
	Returns an unsafe const iterator pointing to the end of the List.
const const_iterator &	crend () const noexcept
	Returns an unsafe const iterator pointing just before the beginning of the List.
const iterator &	rend () noexcept
	Returns an unsafe iterator pointing just before the beginning of the List.
const const_iterator &	rend () const noexcept
	Returns an unsafe const iterator pointing just before the beginning of the List.
const_iterator	cbegin () const
	Returns an unsafe const iterator pointing to the beginning of the List.
iterator	begin ()
	Returns an unsafe iterator pointing to the beginning of the List.
const_iterator	begin () const
	Returns an unsafe const iterator pointing to the beginning of the List.
const_iterator	crbegin () const
	Returns an unsafe const iterator pointing to the last element of the List.
iterator	rbegin ()
	Returns an unsafe iterator pointing to the last element of the List.
const_iterator	rbegin () const
	Returns an unsafe const iterator pointing to the last element of the List.
Accessors / Modifiers
Val &	pushFront (const Val &val)
	Inserts a new element (a copy) at the beginning of the chained list.
Val &	pushFront (Val &&val)
	Inserts a new element (a move) at the beginning of the chained list.
template<typename... Args>
Val &	push_front (Args &&... args)
	An alias for pushFront used for STL compliance.
template<typename... Args>
Val &	emplaceFront (Args &&... args)
	Emplace elements at the beginning of the chained list.
Val &	pushBack (const Val &val)
	Inserts a new element (a copy) at the end of the chained list.
Val &	pushBack (Val &&val)
	Inserts a new element (a move) at the end of the chained list.
template<typename... Args>
Val &	push_back (Args &&... args)
	An alias for pushBack used for STL compliance.
template<typename... Args>
Val &	emplaceBack (Args &&... args)
	Emplace elements at the end of the chained list.
Val &	insert (const Val &val)
	Inserts a new element at the end of the chained list (alias of pushBack).
Val &	insert (Val &&val)
	Inserts a new element at the end of the chained list (alias of pushBack).
Val &	insert (Size pos, const Val &val)
	Inserts a new element at the ith pos of the chained list.
Val &	insert (Size pos, Val &&val)
	Insert an rvalue at the ith pos of the chained list.
Val &	insert (const const_iterator_safe &iter, const Val &val, location place=location::BEFORE)
	Inserts a new element before or after a given iterator.
Val &	insert (const const_iterator_safe &iter, Val &&val, location place=location::BEFORE)
	Inserts an rvalue before or after a given iterator.
Val &	insert (const const_iterator &iter, const Val &val, location place=location::BEFORE)
	Inserts a new element before or after a given iterator.
Val &	insert (const const_iterator &iter, Val &&val, location place=location::BEFORE)
	Inserts an rvalue before or after a given iterator.
template<typename... Args>
Val &	emplace (const const_iterator &iter, Args &&... args)
	Emplace a new element before a given iterator.
template<typename... Args>
Val &	emplace (const const_iterator_safe &iter, Args &&... args)
	Emplace a new element before a given safe iterator.
Val &	front () const
	Returns a reference to first element of a list, if any.
Val &	back () const
	Returns a reference to last element of a list, if any.
Size	size () const noexcept
	Returns the number of elements in the list.
bool	exists (const Val &val) const
	Checks whether there exists a given element in the list.
void	erase (Size i)
	Erases the ith element of the List (the first one is in position 0).
void	erase (const iterator_safe &iter)
	Erases the element of the List pointed to by the safe iterator.
void	erase (const const_iterator_safe &iter)
	Erases the element of the List pointed to by the safe const iterator.
void	eraseByVal (const Val &val)
	erases the first element encountered with a given value.
void	eraseAllVal (const Val &val)
	erases all the elements encountered with a given value
void	popBack ()
	Removes the last element of a List, if any.
void	popFront ()
	Removes the first element of a List, if any.
void	clear ()
	Deletes all the elements of a chained list.
bool	empty () const noexcept
	Returns a boolean indicating whether the chained list is empty.
void	swap (List &other_list)
	Swap the current list with another one.
std::string	toString () const
	Converts a list into a string.
template<typename Mount>
List< Mount >	map (Mount(*f)(Val)) const
	Creates a list of mountains from a list of val.
template<typename Mount>
List< Mount >	map (Mount(*f)(Val &)) const
	Creates a list of mountains from a list of val.
template<typename Mount>
List< Mount >	map (Mount(*f)(const Val &)) const
	Creates a list of mountains from a list of val.
template<typename Mount>
List< Mount >	map (const Mount &mount) const
	Creates a list of mountains with a given value from a list of val.
Operators
List< Val > &	operator= (const List< Val > &src)
	Copy operator.
List< Val > &	operator= (List< Val > &&src)
	Move operator.
Val &	operator+= (const Val &val)
	Inserts a new element at the end of the list (alias of pushBack).
Val &	operator+= (Val &&val)
	Inserts a new element at the end of the list (alias of pushBack).
bool	operator== (const List< Val > &src) const
	Checks whether two lists are identical (same elements in the same order).
bool	operator!= (const List< Val > &src) const
	Checks whether two lists are different (different elements or orders).
Val &	operator[] (const Size i)
	Returns the ith element in the current chained list.
const Val &	operator[] (const Size i) const
	Returns the const ith element in the current chained list.

Private Member Functions
void	_copy_elements_ (const List< Val > &src)
	A function used to perform copies of elements of Lists.
ListBucket< Val > *	_getIthBucket_ (Size i) const noexcept
	Returns the bucket corresponding to the ith position in the list.
ListBucket< Val > *	_getBucket_ (const Val &val) const noexcept
	Returns the bucket corresponding to a given value.
void	_erase_ (ListBucket< Val > *bucket)
	Removes an element from a chained list.
ListBucket< Val > *	_createBucket_ (const Val &val) const
	Create a new bucket with a given value.
ListBucket< Val > *	_createBucket_ (Val &&val) const
	Create a new bucket with a given value.
template<typename... Args>
ListBucket< Val > *	_createEmplaceBucket_ (Args &&... args) const
	Create an emplace bucket.
Val &	_pushFront_ (ListBucket< Val > *new_elt)
	Insert a bucket at the front of the list.
Val &	_pushBack_ (ListBucket< Val > *new_elt)
	Insert a bucket at the end of the list.
Val &	_insertBefore_ (ListBucket< Val > new_elt, ListBucket< Val > current_elt)
	Insert a new bucket before another one.
Val &	_insertAfter_ (ListBucket< Val > new_elt, ListBucket< Val > current_elt)
	Insert a new bucket after another one.
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.
Val &	_insert_ (const const_iterator &iter, ListBucket< Val > *new_elt, location place)
	Inserts a new bucket before or after the location pointed to by an iterator.

Private Attributes
ListBucket< Val > *	_deb_list_ {nullptr}
	A pointer on the first element of the chained list.
ListBucket< Val > *	_end_list_ {nullptr}
	A pointer on the last element of the chained list.
Size	_nb_elements_ {Size(0)}
	The number of elements in the list.
std::vector< const_iterator_safe * >	_safe_iterators_
	The list of "safe" iterators attached to the list.

Friends

class	ListIterator< Val >
	ListIterator should be a friend to optimize access to elements.
class	ListConstIterator< Val >
	ListIterator should be a friend to optimize access to elements.
class	ListIteratorSafe< Val >
	ListIterator should be a friend to optimize access to elements.
class	ListConstIteratorSafe< Val >
	ListIterator should be a friend to optimize access to elements.

Detailed Description

template<typename Val>
class gum::List< Val >

Generic doubly linked lists.

List enables fast and safe manipulation of chained lists. Unless the elements are rvalues, the insertions of new elements into the lists are ALWAYS performed by copy, i.e., each time we add a new element X to the List, a copy of X is actually created and this very copy is stored into the list. For rvalues, move operations are performed.

The List iterators are implemented so as to avoid segmentation faults when elements of the list are deleted while some safe iterators are pointing on them. Moreover they ensure that, when elements are removed from a List, iterators on that list will never access these elements (which is not the case for the iterators in the C++ standard library). Note that this guarantee is ensured at low cost as experimental results show that List and ListIterator are as efficient as their STL counterparts. However, this guarantee can hold only if List is aware of all of the iterators pointing to it: thus, when List erases one element, it can parse the list of its iterators and update those that point toward the now deleted element. When parsing elements without removing any element, you can use unsafe iterators instead of safe ones because they are slightly faster. But those will most certainly segfault if they perform some operations on deleted elements.

Usage example:: // creation of an empty list

List<int> list1;

List<int> list2 { 3, 4, 5 }; // initializer list

// adding elements to the list

list1.pushFront (23);

list1.pushBack (10);

list1 += 25;

list1.insert (12);

// getting the second element of the list

cerr << "10 = " << list1[1] << endl;

// getting the first and last elements

cerr << "first = " << list1.front() << " last = " << list1.back() << endl;

// get the number of elements in the list

cerr << "number of elements = " << list1.size () << endl;

// display the content of the list

cerr << list1 << endl;

// copy the list

List<int> list2 = list1, list3;

list3 = list1;

// delete the second element from the list

list1.erase (1);

// delete the first and last elements

list1.popFront ();

list1.popBack ();

// delete element whose value is 25

list1.eraseByVal (25);

// check whether the list is empty

if (list1.empty()) cerr << "empty list" << endl;

// remove all elements from the list

list1.clear ();

// parse all the elements of a list using unsafe iterators

for (List<int>::iterator iter = list2.begin();

iter != list2.end(); ++iter)

cerr << *iter << endl;

for (List<int>::iterator iter = list2.rbegin();

iter != list2.rend(); --iter)

cerr << *iter << endl;

for (List<int>::const_iterator iter = list2.cbegin();

iter != list2.cend(); ++iter)

cerr << *iter << endl;

for (List<int>::const_iterator iter = list2.crbegin();

iter != list2.crend(); --iter)

cerr << *iter << endl;

// parse all the elements of a list using safe iterators

for (List<int>::iterator_safe iter = list2.beginSafe();

iter != list2.endSafe(); ++iter)

cerr << *iter << endl;

for (List<int>::iterator_safe iter = list2.rbeginSafe();

iter != list2.rendSafe(); --iter)

cerr << *iter << endl;

for (List<int>::const_iterator_safe iter = list2.cbeginSafe();

iter != list2.cendSafe(); ++iter)

cerr << *iter << endl;

for (List<int>::const_iterator_safe iter = list2.crbeginSafe();

iter != list2.crendSafe(); --iter)

cerr << *iter << endl;

// use an iterator to point the element we wish to erase

List<int>::iterator_safe iter = list2.beginSafe();

List2.erase ( iter );

List<int>::iterator iter2 = list2.begin() + 4; // 5th element of the list

iter2 = iter + 4;

// map a list into another list (assuming function f is defined as

// float f (int x) { return (2.5 * x); } )

List<float> flist = list2.map (f);

gum::List
Generic doubly linked lists.
Definition list.h:378

gum::List::size
Size size() const noexcept
Returns the number of elements in the list.
Definition list_tpl.h:1710

gum::List::rend
const iterator & rend() noexcept
Returns an unsafe iterator pointing just before the beginning of the List.
Definition list_tpl.h:1323

gum::List::rbegin
iterator rbegin()
Returns an unsafe iterator pointing to the last element of the List.
Definition list_tpl.h:1386

gum::List::cbegin
const_iterator cbegin() const
Returns an unsafe const iterator pointing to the beginning of the List.
Definition list_tpl.h:1347

gum::List::const_iterator_safe
ListConstIteratorSafe< Val > const_iterator_safe
Types for STL compliance.
Definition list.h:392

gum::List::pushFront
Val & pushFront(const Val &val)
Inserts a new element (a copy) at the beginning of the chained list.
Definition list_tpl.h:1455

gum::List::cend
const const_iterator & cend() const noexcept
Returns an unsafe const iterator pointing to the end of the List.
Definition list_tpl.h:1287

gum::List::back
Val & back() const
Returns a reference to last element of a list, if any.
Definition list_tpl.h:1702

gum::List::clear
void clear()
Deletes all the elements of a chained list.
Definition list_tpl.h:1147

gum::List::front
Val & front() const
Returns a reference to first element of a list, if any.
Definition list_tpl.h:1694

gum::List::rendSafe
const iterator_safe & rendSafe() noexcept
Returns a safe iterator pointing just before the beginning of the List.
Definition list_tpl.h:1311

gum::List::iterator
ListIterator< Val > iterator
Types for STL compliance.
Definition list.h:389

gum::List::beginSafe
iterator_safe beginSafe()
Returns a safe iterator pointing to the beginning of the List.
Definition list_tpl.h:1341

gum::List::map
List< Mount > map(Mount(*f)(Val)) const
Creates a list of mountains from a list of val.
Definition list_tpl.h:1847

gum::List::pushBack
Val & pushBack(const Val &val)
Inserts a new element (a copy) at the end of the chained list.
Definition list_tpl.h:1481

gum::List::cbeginSafe
const_iterator_safe cbeginSafe() const
Returns a safe const iterator pointing to the beginning of the List.
Definition list_tpl.h:1335

gum::List::end
const iterator & end() noexcept
Returns an unsafe iterator pointing to the end of the List.
Definition list_tpl.h:1293

gum::List::popBack
void popBack()
Removes the last element of a List, if any.
Definition list_tpl.h:1810

gum::List::List
List()
A basic constructor that creates an empty list.
Definition list_tpl.h:1167

gum::List::crend
const const_iterator & crend() const noexcept
Returns an unsafe const iterator pointing just before the beginning of the List.
Definition list_tpl.h:1317

gum::List::iterator_safe
ListIteratorSafe< Val > iterator_safe
Types for STL compliance.
Definition list.h:391

gum::List::begin
iterator begin()
Returns an unsafe iterator pointing to the beginning of the List.
Definition list_tpl.h:1353

gum::List::insert
Val & insert(const Val &val)
Inserts a new element at the end of the chained list (alias of pushBack).
Definition list_tpl.h:1508

gum::List::empty
bool empty() const noexcept
Returns a boolean indicating whether the chained list is empty.
Definition list_tpl.h:1822

gum::List::crbeginSafe
const_iterator_safe crbeginSafe() const
Returns a safe const iterator pointing to the last element of the List.
Definition list_tpl.h:1365

gum::List::popFront
void popFront()
Removes the first element of a List, if any.
Definition list_tpl.h:1816

gum::List::crbegin
const_iterator crbegin() const
Returns an unsafe const iterator pointing to the last element of the List.
Definition list_tpl.h:1379

gum::List::cendSafe
const const_iterator_safe & cendSafe() const noexcept
Returns a safe const iterator pointing to the end of the List.
Definition list_tpl.h:1275

gum::List::eraseByVal
void eraseByVal(const Val &val)
erases the first element encountered with a given value.
Definition list_tpl.h:1793

gum::List::rbeginSafe
iterator_safe rbeginSafe()
Returns a safe iterator pointing to the last element of the List.
Definition list_tpl.h:1372

gum::List::const_iterator
ListConstIterator< Val > const_iterator
Types for STL compliance.
Definition list.h:390

gum::List::crendSafe
const const_iterator_safe & crendSafe() const noexcept
Return a safe const iterator pointing just before the beginning of the List.
Definition list_tpl.h:1305

gum::List::endSafe
const iterator_safe & endSafe() noexcept
Returns a safe iterator pointing to the end of the List.
Definition list_tpl.h:1281

gum::List::erase
void erase(Size i)
Erases the ith element of the List (the first one is in position 0).
Definition list_tpl.h:1763

Template Parameters

Val	The values type stored in the gum::List.

Definition at line 378 of file list.h.

Member Typedef Documentation

◆ const_iterator

template<typename Val>

using gum::List< Val >::const_iterator = ListConstIterator< Val >

Types for STL compliance.

Definition at line 390 of file list.h.

◆ const_iterator_safe

template<typename Val>

using gum::List< Val >::const_iterator_safe = ListConstIteratorSafe< Val >

Types for STL compliance.

Definition at line 392 of file list.h.

◆ const_pointer

template<typename Val>

using gum::List< Val >::const_pointer = const Val*

Types for STL compliance.

Definition at line 386 of file list.h.

◆ const_reference

template<typename Val>

using gum::List< Val >::const_reference = const Val&

Types for STL compliance.

Definition at line 384 of file list.h.

◆ difference_type

template<typename Val>

using gum::List< Val >::difference_type = std::ptrdiff_t

Types for STL compliance.

Definition at line 388 of file list.h.

◆ iterator

template<typename Val>

using gum::List< Val >::iterator = ListIterator< Val >

Types for STL compliance.

Definition at line 389 of file list.h.

◆ iterator_safe

template<typename Val>

using gum::List< Val >::iterator_safe = ListIteratorSafe< Val >

Types for STL compliance.

Definition at line 391 of file list.h.

◆ pointer

template<typename Val>

using gum::List< Val >::pointer = Val*

Types for STL compliance.

Definition at line 385 of file list.h.

◆ reference

template<typename Val>

using gum::List< Val >::reference = Val&

Types for STL compliance.

Definition at line 383 of file list.h.

◆ size_type

template<typename Val>

using gum::List< Val >::size_type = Size

Types for STL compliance.

Definition at line 387 of file list.h.

◆ value_type

template<typename Val>

using gum::List< Val >::value_type = Val

Types for STL compliance.

Definition at line 382 of file list.h.

Member Enumeration Documentation

◆ location

template<typename Val>

enum class gum::List::location

strong

Locations around iterators where insertions of new elements can take / place.

Enumerator
BEFORE
AFTER

Definition at line 397 of file list.h.

397{ BEFORE, AFTER };

Constructor & Destructor Documentation

◆ List() [1/4]

template<typename Val>

gum::List< Val >::List ( )

explicit

A basic constructor that creates an empty list.

Definition at line 1167 of file list_tpl.h.

                    {
    // for debugging purposes
    GUM_CONSTRUCTOR(List);
 
    // reserve space for only the default number of iterators
    _safe_iterators_.reserve(GUM_DEFAULT_ITERATOR_NUMBER);
  }

References List(), _safe_iterators_, and GUM_DEFAULT_ITERATOR_NUMBER.

Referenced by List(), List(), List(), List(), ~List(), _copy_elements_(), map(), map(), map(), map(), operator!=(), operator=(), operator=(), operator==(), and swap().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ List() [2/4]

template<typename Val>

gum::List< Val >::List ( const List< Val > & src )

Copy constructor.

The new list and that which is copied do not share their elements: the new list contains new instances of the values stored in the list to be copied. Of course if these values are pointers, the new values point toward the same elements. This constructor runs in linear time.

Parameters

src	the list the contents of which is copied into the current one.

Definition at line 1177 of file list_tpl.h.

                                          {
    // for debugging purposes
    GUM_CONS_CPY(List);
 
    // copy the elements
    _copy_elements_(src);
 
    // reserve space for only the default number of iterators
    _safe_iterators_.reserve(GUM_DEFAULT_ITERATOR_NUMBER);
  }

References List(), and _copy_elements_().

Here is the call graph for this function:

◆ List() [3/4]

template<typename Val>

gum::List< Val >::List ( List< Val > && src )

noexcept

Move constructor.

Parameters

src	The gum::List to move.

Definition at line 1190 of file list_tpl.h.

                                              :
      _deb_list_{std::move(src._deb_list_)}, _end_list_{std::move(src._end_list_)},
      _nb_elements_{std::move(src._nb_elements_)},
      _safe_iterators_{std::move(src._safe_iterators_)} {
    // for debugging purposes
    GUM_CONS_MOV(List);
 
    src._deb_list_    = nullptr;
    src._end_list_    = nullptr;
    src._nb_elements_ = 0;
    src._safe_iterators_.clear();
  }

References List(), and _deb_list_.

Here is the call graph for this function:

◆ List() [4/4]

template<typename Val>

gum::List< Val >::List ( std::initializer_list< Val > list )

Initializer_list constructor.

Parameters

list	The initializer list.

Definition at line 1205 of file list_tpl.h.

                                                   {
    // for debugging purposes
    GUM_CONSTRUCTOR(List);
 
    // adding all the elements
    for (const auto& val: list) {
      pushBack(val);
    }
 
    // reserve space for only the default number of iterators
    _safe_iterators_.reserve(GUM_DEFAULT_ITERATOR_NUMBER);
  }

References List().

Here is the call graph for this function:

◆ ~List()

template<typename Val>

gum::List< Val >::~List ( )

Class destructor.

Definition at line 1220 of file list_tpl.h.

                     {
    // for debugging (although this program is bug-free)
    GUM_DESTRUCTOR(List);
 
    // we detach all the safe iterators attached to the current List and we
    // remove all the elements from the list
    clear();
  }

References List(), and clear().

Here is the call graph for this function:

Member Function Documentation

◆ _copy_elements_()

template<typename Val>

void gum::List< Val >::_copy_elements_ ( const List< Val > & src )

private

A function used to perform copies of elements of Lists.

Before performing the copy, we assume in this function that the current list (this) is empty (else there would be memory leak).

Parameters

src	The gum::List to copy.

Definition at line 1108 of file list_tpl.h.

                                                          {
    ListBucket< Val >* ptr;
    ListBucket< Val >* old_ptr = nullptr;
    ListBucket< Val >* new_elt = nullptr;
 
    // copy src's list
    try {
      for (ptr = src._deb_list_; ptr != nullptr; ptr = ptr->_next_) {
        // create a copy bucket
        new_elt = new ListBucket< Val >(*ptr);
 
        // rechain properly the new list (the next field is already initialized
        // with nullptr)
        new_elt->_prev_ = old_ptr;
 
        if (old_ptr) old_ptr->_next_ = new_elt;
        else _deb_list_ = new_elt;
 
        old_ptr = new_elt;
      }
    } catch (...) {
      // problem: we could not allocate an element in the list => we delete
      // the elements created so far and we throw an exception
      for (; _deb_list_ != nullptr; _deb_list_ = const_cast< ListBucket< Val >* >(ptr)) {
        ptr = _deb_list_->_next_;
        delete _deb_list_;
      }
 
      _deb_list_ = nullptr;
      throw;
    }
 
    // update properly the end of the chained list and the number of elements
    _end_list_    = old_ptr;
    _nb_elements_ = src._nb_elements_;
  }

References List().

Referenced by List().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ _createBucket_() [1/2]

template<typename Val>

ListBucket< Val > * gum::List< Val >::_createBucket_ ( const Val & val ) const

private

Create a new bucket with a given value.

Parameters

val	The value of the new bucket.

Returns: Returns the bucket holding val.

Definition at line 1400 of file list_tpl.h.

                                                                     {
    return new ListBucket< Val >(val);
  }

Referenced by insert(), insert(), insert(), insert(), insert(), insert(), pushBack(), pushBack(), pushFront(), and pushFront().

Here is the caller graph for this function:

◆ _createBucket_() [2/2]

template<typename Val>

ListBucket< Val > * gum::List< Val >::_createBucket_ ( Val && val ) const

private

Create a new bucket with a given value.

Parameters

val	The value of the new bucket.

Returns: Returns the bucket holding val.

Definition at line 1406 of file list_tpl.h.

                                                                {
    return new ListBucket< Val >(std::move(val));
  }

◆ _createEmplaceBucket_()

template<typename Val>

template<typename... Args>

ListBucket< Val > * gum::List< Val >::_createEmplaceBucket_ ( Args &&... args ) const

private

Create an emplace bucket.

Template Parameters

Args	The emplace arguments types.

Parameters

args	The emplace arguments.

Returns: Returns the bucket holding the new value.

Definition at line 1413 of file list_tpl.h.

                                                                            {
    return new ListBucket< Val >(ListBucket< Val >::Emplace::EMPLACE,
                                 std::forward< Args >(args)...);
  }

References gum::ListBucket< Val >::EMPLACE.

Referenced by emplace(), emplace(), emplaceBack(), and emplaceFront().

Here is the caller graph for this function:

◆ _erase_()

template<typename Val>

void gum::List< Val >::_erase_ ( ListBucket< Val > * bucket )

private

Removes an element from a chained list.

If parameter bucket is equal to 0, then the method does not perform anything, else the bucket is deleted. In the latter case, no test is ever performed to check that the bucket does actually belong to the List. The method runs in constant time.

Parameters

bucket A pointer on the bucket in the chained list we wish to remove.

Definition at line 1725 of file list_tpl.h.

                                                     {
    // perform deletion only if there is a bucket to remove
    if (bucket != nullptr) {
      // update the iterators pointing on this element
      for (const auto ptr_iter: _safe_iterators_) {
        if (ptr_iter->_bucket_ == bucket) {
          ptr_iter->_next_current_bucket_ = bucket->_prev_;
          ptr_iter->_prev_current_bucket_ = bucket->_next_;
          ptr_iter->_bucket_              = nullptr;
          ptr_iter->_null_pointing_       = true;
        } else {
          if (ptr_iter->_null_pointing_) {
            if (ptr_iter->_next_current_bucket_ == bucket)
              ptr_iter->_next_current_bucket_ = bucket->_prev_;
 
            if (ptr_iter->_prev_current_bucket_ == bucket)
              ptr_iter->_prev_current_bucket_ = bucket->_next_;
          }
        }
      }
 
      // set properly the begin and end of the chained list (the other chainings
      // will be performed by operator delete)
      if (bucket->_prev_ == nullptr) _deb_list_ = bucket->_next_;
      else bucket->_prev_->_next_ = bucket->_next_;
 
      if (bucket->_next_ == nullptr) _end_list_ = bucket->_prev_;
      else bucket->_next_->_prev_ = bucket->_prev_;
 
      // remove the current element src the list
      delete bucket;
 
      --_nb_elements_;
    }
  }

References _deb_list_, _end_list_, _nb_elements_, gum::ListBucket< Val >::_next_, gum::ListBucket< Val >::_prev_, and _safe_iterators_.

Referenced by erase(), erase(), erase(), eraseAllVal(), eraseByVal(), popBack(), and popFront().

Here is the caller graph for this function:

◆ _getBucket_()

template<typename Val>

ListBucket< Val > * gum::List< Val >::_getBucket_ ( const Val & val ) const

privatenoexcept

Returns the bucket corresponding to a given value.

Actually, this is the first bucket of value val encountered in the list, if any, that is returned. If the element cannot be found, 0 is returned. This method enables fast removals of buckets. It runs in linear time.

Comparisons between Val instances are performed through == operators.

Parameters

val	The value of the element the bucket of which we wish to return.

Returns: Returns the bucket corresponding to a given value.

Definition at line 1784 of file list_tpl.h.

                                                                           {
    for (ListBucket< Val >* ptr = _deb_list_; ptr != nullptr; ptr = ptr->_next_)
      if (ptr->_val_ == val) return ptr;
 
    return nullptr;
  }

References _deb_list_, gum::ListBucket< Val >::_next_, and gum::ListBucket< Val >::_val_.

Referenced by eraseByVal().

Here is the caller graph for this function:

◆ _getIthBucket_()

template<typename Val>

ListBucket< Val > * gum::List< Val >::_getIthBucket_ ( Size i ) const

privatenoexcept

Returns the bucket corresponding to the ith position in the list.

This method assumes that the list contains at least i+1 elements. The index of the first element of the list is 0.

Parameters

i	The position of the returned element.

Returns: Returns the gum::ListBucket of the ith element.

Definition at line 1520 of file list_tpl.h.

                                                                      {
    ListBucket< Val >* ptr;
 
    if (i < _nb_elements_ / 2) {
      for (ptr = _deb_list_; i; --i, ptr = ptr->_next_) {}
    } else {
      for (ptr = _end_list_, i = _nb_elements_ - i - 1; i; --i, ptr = ptr->_prev_) {}
    }
 
    return ptr;
  }

References _deb_list_, _end_list_, _nb_elements_, gum::ListBucket< Val >::_next_, and gum::ListBucket< Val >::_prev_.

Referenced by erase(), insert(), insert(), operator[](), and operator[]().

Here is the caller graph for this function:

◆ _insert_() [1/2]

template<typename Val>

Val & gum::List< Val >::_insert_	(	const const_iterator &	iter,
		ListBucket< Val > *	new_elt,
		location	place )

private

Inserts a new bucket before or after the location pointed to by an iterator.

Parameters

iter	An iterator pointing where to insert a new element.
new_elt	The new element ot insert in the gum::List.
place	Where to insert the new element relatively to the iterator.

Returns: Returns a reference over the value stored in the gum::List.

Definition at line 1620 of file list_tpl.h.

                                                          {
    // find the location around which the new element should be inserted
    ListBucket< Val >* ptr = iter._getBucket_();
 
    if (ptr == nullptr) {
      // here, we are at the end of the list
      return _pushBack_(new_elt);
    } else {
      switch (place) {
        case location::BEFORE : return _insertBefore_(new_elt, ptr);
 
        case location::AFTER : return _insertAfter_(new_elt, ptr);
 
        default : GUM_ERROR(FatalError, "List insertion for this location unimplemented")
      }
    }
  }

References gum::ListConstIterator< Val >::_getBucket_(), _insertAfter_(), _insertBefore_(), _pushBack_(), AFTER, BEFORE, and GUM_ERROR.

Here is the call graph for this function:

◆ _insert_() [2/2]

template<typename Val>

Val & gum::List< Val >::_insert_	(	const const_iterator_safe &	iter,
		ListBucket< Val > *	new_elt,
		location	place )

private

Inserts a new bucket before or after the location pointed to by an iterator.

Parameters

iter	An iterator pointing where to insert a new element.
new_elt	The new element ot insert in the gum::List.
place	Where to insert the new element relatively to the iterator.

Returns: Returns a reference over the value stored in the gum::List.

Definition at line 1587 of file list_tpl.h.

                                                               {
    // find the location around which the new element should be inserted
    ListBucket< Val >* ptr;
 
    if (iter._null_pointing_) {
      if (place == location::BEFORE) {
        ptr = iter._next_current_bucket_;
      } else {
        ptr = iter._prev_current_bucket_;
      }
    } else {
      ptr = iter._getBucket_();
    }
 
    if (ptr == nullptr) {
      // here, we are at the end of the list
      return _pushBack_(new_elt);
    } else {
      switch (place) {
        case location::BEFORE : return _insertBefore_(new_elt, ptr);
 
        case location::AFTER : return _insertAfter_(new_elt, ptr);
 
        default : GUM_ERROR(FatalError, "List insertion for this location unimplemented")
      }
    }
  }

References gum::ListConstIteratorSafe< Val >::_getBucket_(), _insertAfter_(), _insertBefore_(), gum::ListConstIteratorSafe< Val >::_next_current_bucket_, gum::ListConstIteratorSafe< Val >::_null_pointing_, gum::ListConstIteratorSafe< Val >::_prev_current_bucket_, _pushBack_(), AFTER, BEFORE, and GUM_ERROR.

Referenced by emplace(), emplace(), insert(), insert(), insert(), and insert().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ _insertAfter_()

template<typename Val>

Val & gum::List< Val >::_insertAfter_	(	ListBucket< Val > *	new_elt,
		ListBucket< Val > *	current_elt )

private

Insert a new bucket after another one.

Parameters

new_elt	The new element to insert in the gum::List.
current_elt	The element before which new_elt will be inserted.

Returns: Returns a reference over the value stored in the gum::List.

Definition at line 1551 of file list_tpl.h.

                                                                                            {
    new_elt->_prev_     = current_elt;
    new_elt->_next_     = current_elt->_next_;
    current_elt->_next_ = new_elt;
 
    if (new_elt->_next_ == nullptr) _end_list_ = new_elt;
    else new_elt->_next_->_prev_ = new_elt;
 
    // update the number of elements
    ++_nb_elements_;
 
    // returns the current value
    return new_elt->_val_;
  }

References _end_list_, _nb_elements_, gum::ListBucket< Val >::_next_, gum::ListBucket< Val >::_prev_, and gum::ListBucket< Val >::_val_.

Referenced by _insert_(), and _insert_().

Here is the caller graph for this function:

◆ _insertBefore_()

template<typename Val>

Val & gum::List< Val >::_insertBefore_	(	ListBucket< Val > *	new_elt,
		ListBucket< Val > *	current_elt )

private

Insert a new bucket before another one.

Parameters

new_elt	The new element to insert in the gum::List.
current_elt	The element before which new_elt will be inserted.

Returns: Returns a reference over the value stored in the gum::List.

Definition at line 1534 of file list_tpl.h.

                                                                                             {
    new_elt->_next_     = current_elt;
    new_elt->_prev_     = current_elt->_prev_;
    current_elt->_prev_ = new_elt;
 
    if (new_elt->_prev_ == nullptr) _deb_list_ = new_elt;
    else new_elt->_prev_->_next_ = new_elt;
 
    // update the number of elements
    ++_nb_elements_;
 
    // returns the current value
    return new_elt->_val_;
  }

References _deb_list_, _nb_elements_, gum::ListBucket< Val >::_next_, gum::ListBucket< Val >::_prev_, and gum::ListBucket< Val >::_val_.

Referenced by _insert_(), _insert_(), insert(), and insert().

Here is the caller graph for this function:

◆ _pushBack_()

template<typename Val>

Val & gum::List< Val >::_pushBack_ ( ListBucket< Val > * new_elt )

private

Insert a bucket at the end of the list.

Parameters

new_elt The new element pushed at the end of the gum::List.

Returns: Returns a refefence over the value stored in the gum::List.

Definition at line 1437 of file list_tpl.h.

                                                         {
    // place the bucket at the end of the list
    new_elt->_prev_ = _end_list_;
 
    if (_end_list_ != nullptr) _end_list_->_next_ = new_elt;
    else _deb_list_ = new_elt;
 
    _end_list_ = new_elt;
 
    // update the number of elements
    ++_nb_elements_;
 
    // returns the current value
    return new_elt->_val_;
  }

References _deb_list_, _end_list_, _nb_elements_, gum::ListBucket< Val >::_prev_, and gum::ListBucket< Val >::_val_.

Referenced by _insert_(), _insert_(), emplaceBack(), pushBack(), and pushBack().

Here is the caller graph for this function:

◆ _pushFront_()

template<typename Val>

Val & gum::List< Val >::_pushFront_ ( ListBucket< Val > * new_elt )

private

Insert a bucket at the front of the list.

Parameters

new_elt The new element pushed at the front of the gum::List.

Returns: Returns a refefence over the value stored in the gum::List.

Definition at line 1420 of file list_tpl.h.

                                                          {
    new_elt->_next_ = _deb_list_;
 
    if (_deb_list_ != nullptr) _deb_list_->_prev_ = new_elt;
    else _end_list_ = new_elt;
 
    _deb_list_ = new_elt;
 
    // update the number of elements
    ++_nb_elements_;
 
    // return the inserted element
    return new_elt->_val_;
  }

References _deb_list_, _end_list_, _nb_elements_, gum::ListBucket< Val >::_next_, and gum::ListBucket< Val >::_val_.

Referenced by emplaceFront(), pushFront(), and pushFront().

Here is the caller graph for this function:

◆ back()

template<typename Val>

Val & gum::List< Val >::back ( ) const

Returns a reference to last element of a list, if any.

Exceptions

NotFound exception is thrown if the list is empty.

Definition at line 1702 of file list_tpl.h.

                               {
    if (_nb_elements_ == Size(0)) { GUM_ERROR(NotFound, "not enough elements in the chained list") }
 
    return _end_list_->_val_;
  }

References _end_list_, _nb_elements_, and GUM_ERROR.

◆ begin() [1/2]

template<typename Val>

ListIterator< Val > gum::List< Val >::begin ( )

Returns an unsafe iterator pointing to the beginning of the List.

Unsafe iterators are a little bit faster than safe iterators and they consume less memory. However, if the element they point to is erased, their dereference or their increment/decrement will produce a mess, probably a segfault. You should use them only when performance is an issue and if you are sure that they will never point to an element erased.

Returns: Returns an unsafe iterator pointing to the beginning of the List.

Definition at line 1353 of file list_tpl.h.

                                         {
    return ListIterator< Val >{*this};
  }

References ListIterator< Val >.

Referenced by map(), map(), and map().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ begin() [2/2]

template<typename Val>

ListConstIterator< Val > gum::List< Val >::begin ( ) const

Returns an unsafe const iterator pointing to the beginning of the List.

Unsafe const iterators are a little bit faster than safe const iterators and they consume less memory. However, if the element they point to is erased, their dereference or their increment/decrement will produce a mess, probably a segfault. You should use them only when performance is an issue and if you are sure that they will never point to an element erased.

Returns an unsafe const iterator pointing to the beginning of the List.

Definition at line 1359 of file list_tpl.h.

                                                    {
    return ListConstIterator< Val >{*this};
  }

References ListConstIterator< Val >.

Here is the call graph for this function:

◆ beginSafe()

template<typename Val>

ListIteratorSafe< Val > gum::List< Val >::beginSafe ( )

Returns a safe iterator pointing to the beginning of the List.

Safe iterators are iterators whose state is updated by the list when the element they point to is erased. As such, in this case, they can throw an exception when we try to derefence them and they are able to perform a valid ++ or – step.

Returns: Returns a safe iterator pointing to the beginning of the List.

Definition at line 1341 of file list_tpl.h.

                                                 {
    return ListIteratorSafe< Val >{*this};
  }

◆ cbegin()

template<typename Val>

ListConstIterator< Val > gum::List< Val >::cbegin ( ) const

Returns an unsafe const iterator pointing to the beginning of the List.

Unsafe const iterators are a little bit faster than safe const iterators and they consume less memory. However, if the element they point to is erased, their dereference or their increment/decrement will produce a mess, probably a segfault. You should use them only when performance is an issue and if you are sure that they will never point to an element erased.

Returns: Returns an unsafe const iterator pointing to the beginning of the List.

Definition at line 1347 of file list_tpl.h.

                                                     {
    return ListConstIterator< Val >{*this};
  }

References ListConstIterator< Val >.

Here is the call graph for this function:

◆ cbeginSafe()

template<typename Val>

ListConstIteratorSafe< Val > gum::List< Val >::cbeginSafe ( ) const

Returns a safe const iterator pointing to the beginning of the List.

Safe const iterators are const iterators whose state is updated by the list when the element they point to is erased. As such, in this case, they can throw an exception when we try to derefence them and they are able to perform a valid ++ or – step.

Returns: Returns a safe const iterator pointing to the beginning of the List.

Definition at line 1335 of file list_tpl.h.

                                                             {
    return ListConstIteratorSafe< Val >{*this};
  }

References ListConstIteratorSafe< Val >.

Here is the call graph for this function:

◆ cend()

template<typename Val>

const ListConstIterator< Val > & gum::List< Val >::cend ( ) const

noexcept

Returns an unsafe const iterator pointing to the end of the List.

Unsafe const iterators are a little bit faster than safe const iterators and they consume less memory. However, if the element they point to is erased, their dereference or their increment/decrement will produce a mess, probably a segfault. You should use them only when performance is an issue and if you are sure that they will never point to an element erased.

Returns an unsafe const iterator pointing to the end of the List.

Definition at line 1287 of file list_tpl.h.

                                                                   {
    return *(reinterpret_cast< const ListConstIterator< Val >* >(_list_end_));
  }

References ListConstIterator< Val >.

Here is the call graph for this function:

◆ cendSafe()

template<typename Val>

const ListConstIteratorSafe< Val > & gum::List< Val >::cendSafe ( ) const

noexcept

Returns a safe const iterator pointing to the end of the List.

Safe const iterators are const iterators whose state is updated by the list when the element they point to is erased. As such, in this case, they can throw an exception when we try to derefence them and they are able to perform a valid ++ or – step

Returns a safe const iterator pointing to the end of the List.

Definition at line 1275 of file list_tpl.h.

                                                                           {
    return *(reinterpret_cast< const ListConstIteratorSafe< Val >* >(_list_end_safe_));
  }

References ListConstIteratorSafe< Val >.

Here is the call graph for this function:

◆ clear()

template<typename Val>

void gum::List< Val >::clear ( )

Deletes all the elements of a chained list.

All the iterators of the list will be resetted to rend. The method runs in linear time of both the size of the list and the number of iterators attached to the List.

Definition at line 1147 of file list_tpl.h.

                          {
    // first we update all the safe iterators of the list : they should now
    // point to end/rend
    for (const auto ptr_iter: _safe_iterators_) {
      ptr_iter->clear();
    }
 
    // clear all the values
    for (ListBucket< Val >*ptr = _deb_list_, *next_ptr = nullptr; ptr != nullptr; ptr = next_ptr) {
      next_ptr = ptr->_next_;
      delete ptr;
    }
 
    _nb_elements_ = 0;
    _deb_list_    = nullptr;
    _end_list_    = nullptr;
  }

References _deb_list_, _end_list_, _nb_elements_, gum::ListBucket< Val >::_next_, and _safe_iterators_.

Referenced by ~List(), and operator=().

Here is the caller graph for this function:

◆ crbegin()

template<typename Val>

ListConstIterator< Val > gum::List< Val >::crbegin ( ) const

Returns an unsafe const iterator pointing to the last element of the List.

Unsafe iterators are a little bit faster than safe iterators and they consume less memory. However, if the element they point to is erased, their dereference or their increment/decrement will produce a mess, probably a segfault. You should use them only when performance is an issue and if you are sure that they will never point to an element erased.

Returns: Returns an unsafe const iterator pointing to the last element of the List.

Definition at line 1379 of file list_tpl.h.

                                                      {
    if (_nb_elements_) return ListConstIterator< Val >{*this, _nb_elements_ - 1};
    else return ListConstIterator< Val >{};
  }

References _nb_elements_, and ListConstIterator< Val >.

Here is the call graph for this function:

◆ crbeginSafe()

template<typename Val>

ListConstIteratorSafe< Val > gum::List< Val >::crbeginSafe ( ) const

Returns a safe const iterator pointing to the last element of the List.

Safe const iterators are const iterators whose state is updated by the list when the element they point to is erased. As such, in this case, they can throw an exception when we try to derefence them and they are able to perform a valid ++ or – step.

Returns: Returns a safe const iterator pointing to the last element of the List.

Definition at line 1365 of file list_tpl.h.

                                                              {
    if (_nb_elements_) return ListConstIteratorSafe< Val >{*this, _nb_elements_ - 1};
    else return ListConstIteratorSafe< Val >{};
  }

References _nb_elements_, and ListConstIteratorSafe< Val >.

Here is the call graph for this function:

◆ crend()

template<typename Val>

const ListConstIterator< Val > & gum::List< Val >::crend ( ) const

noexcept

Returns an unsafe const iterator pointing just before the beginning of the List.

Unsafe const iterators are a little bit faster than safe const iterators and they consume less memory. However, if the element they point to is erased, their dereference or their increment/decrement will produce a mess, probably a segfault. You should use them only when performance is an issue and if you are sure that they will never point to an element erased.

Returns: Returns an unsafe const iterator pointing just before the beginning of the List

Definition at line 1317 of file list_tpl.h.

                                                                    {
    return *(reinterpret_cast< const ListConstIterator< Val >* >(_list_end_));
  }

References ListConstIterator< Val >.

Here is the call graph for this function:

◆ crendSafe()

template<typename Val>

const ListConstIteratorSafe< Val > & gum::List< Val >::crendSafe ( ) const

noexcept

Return a safe const iterator pointing just before the beginning of the List.

Safe const iterators are const iterators whose state is updated by the list when the element they point to is erased. As such, in this case, they can throw an exception when we try to derefence them and they are able to perform a valid ++ or – step.

Return a safe const iterator pointing just before the beginning of the List.

Definition at line 1305 of file list_tpl.h.

                                                                            {
    return *(reinterpret_cast< const ListConstIteratorSafe< Val >* >(_list_end_safe_));
  }

References ListConstIteratorSafe< Val >.

Here is the call graph for this function:

◆ emplace() [1/2]

template<typename Val>

template<typename... Args>

Val & gum::List< Val >::emplace	(	const const_iterator &	iter,
		Args &&...	args )

Emplace a new element before a given iterator.

Emplace is a method that allows to construct directly an element of type Val by passing to its constructor all the arguments it needs. The first element of the list is at pos 0. After the insert, the element is placed precisely at pos if pos is less than the size of the list before insertion, else it is inserted at the end of the list.

Parameters

iter	The position in the list
args	The arguments passed to the constructor

Returns: Returns a reference on the copy inserted into the list.

Definition at line 1681 of file list_tpl.h.

                                                                      {
    return _insert_(iter, _createEmplaceBucket_(std::forward< Args >(args)...), location::BEFORE);
  }

References _createEmplaceBucket_(), _insert_(), and BEFORE.

Here is the call graph for this function:

◆ emplace() [2/2]

template<typename Val>

template<typename... Args>

Val & gum::List< Val >::emplace	(	const const_iterator_safe &	iter,
		Args &&...	args )

Emplace a new element before a given safe iterator.

Emplace is a method that allows to construct directly an element of type Val by passing to its constructor all the arguments it needs. The first element of the list is at pos 0. After the insert, the element is placed precisely at pos if pos is less than the size of the list before insertion, else it is inserted at the end of the list.

Parameters

iter	The position in the list.
args	the arguments passed to the constructor.

Returns: Returns a reference on the copy inserted into the list.

Definition at line 1688 of file list_tpl.h.

                                                                           {
    return _insert_(iter, _createEmplaceBucket_(std::forward< Args >(args)...), location::BEFORE);
  }

References _createEmplaceBucket_(), _insert_(), and BEFORE.

Here is the call graph for this function:

◆ emplaceBack()

template<typename Val>

template<typename... Args>

Val & gum::List< Val >::emplaceBack ( Args &&... args )

Emplace elements at the end of the chained list.

Emplace is a method that allows to construct directly an element of type Val by passing to its constructor all the arguments it needs

Template Parameters

Args	The emplaced arguments types.

Parameters

args	The arguments passed to the constructor

Returns: A reference on the copy inserted into the list.

Definition at line 1501 of file list_tpl.h.

                                              {
    return _pushBack_(_createEmplaceBucket_(std::forward< Args >(args)...));
  }

References _createEmplaceBucket_(), and _pushBack_().

Here is the call graph for this function:

◆ emplaceFront()

template<typename Val>

template<typename... Args>

Val & gum::List< Val >::emplaceFront ( Args &&... args )

Emplace elements at the beginning of the chained list.

Emplace is a method that allows to construct directly an element of type Val by passing to its constructor all the arguments it needs

Parameters

args	The arguments passed to the constructor.

Returns: Returns a reference on the copy inserted into the list.

Definition at line 1475 of file list_tpl.h.

                                               {
    return _pushFront_(_createEmplaceBucket_(std::forward< Args >(args)...));
  }

References _createEmplaceBucket_(), and _pushFront_().

Here is the call graph for this function:

◆ empty()

template<typename Val>

bool gum::List< Val >::empty ( ) const

noexcept

Returns a boolean indicating whether the chained list is empty.

Returns: Returns a boolean indicating whether the chained list is empty.

Definition at line 1822 of file list_tpl.h.

                                         {
    return (_nb_elements_ == Size(0));
  }

References _nb_elements_.

Referenced by gum::graph::_bayesBall_(), gum::prm::SVE< GUM_SCALAR >::_eliminateNodes_(), gum::prm::SVED< GUM_SCALAR >::_eliminateNodes_(), gum::prm::SVED< GUM_SCALAR >::_eliminateNodesDownward_(), gum::learning::ConstraintBasedLearning::_existsDirectedPath_(), gum::learning::SimpleMiic::_existsDirectedPath_(), gum::MeekRules::_existsDirectedPath_(), gum::BarrenNodesFinder::barrenNodes(), gum::BarrenNodesFinder::barrenNodes(), gum::graph::directedPath(), gum::graph::directedUnorientedPath(), gum::InfluenceDiagram< GUM_SCALAR >::existsPathBetween(), gum::InfluenceDiagram< GUM_SCALAR >::getChildrenDecision_(), gum::graph::hasDirectedPath(), gum::graph::hasUndirectedCycle(), gum::graph::mixedOrientedPath(), gum::graph::mixedUnorientedPath(), gum::BayesBall::relevantTensors(), gum::dSeparationAlgorithm::relevantTensors(), gum::dSeparationAlgorithm::requisiteNodes(), gum::DAGCycleDetector::setDAG(), and gum::graph::undirectedPath().

Here is the caller graph for this function:

◆ end() [1/2]

template<typename Val>

const ListConstIterator< Val > & gum::List< Val >::end ( ) const

noexcept

Returns an unsafe const iterator pointing to the end of the List.

Unsafe const iterators are a little bit faster than safe const iterators and they consume less memory. However, if the element they point to is erased, their dereference or their increment/decrement will produce a mess, probably a segfault. You should use them only when performance is an issue and if you are sure that they will never point to an element erased.

Returns: Returns an unsafe const iterator pointing to the end of the List.

Definition at line 1299 of file list_tpl.h.

                                                                  {
    return *(reinterpret_cast< const ListConstIterator< Val >* >(_list_end_));
  }

References ListConstIterator< Val >.

Here is the call graph for this function:

◆ end() [2/2]

template<typename Val>

const ListIterator< Val > & gum::List< Val >::end ( )

noexcept

Returns an unsafe iterator pointing to the end of the List.

Unsafe iterators are a little bit faster than safe iterators and they consume less memory. However, if the element they point to is erased, their dereference or their increment/decrement will produce a mess, probably a segfault. You should use them only when performance is an issue and if you are sure that they will never point to an element erased.

Returns: Returns an unsafe iterator pointing to the end of the List.

Definition at line 1293 of file list_tpl.h.

                                                       {
    return *(reinterpret_cast< const ListIterator< Val >* >(_list_end_));
  }

References ListIterator< Val >.

Referenced by map(), map(), and map().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ endSafe()

template<typename Val>

const ListIteratorSafe< Val > & gum::List< Val >::endSafe ( )

noexcept

Returns a safe iterator pointing to the end of the List.

Safe iterators are iterators whose state is updated by the list when the element they point to is erased. As such, in this case, they can throw an exception when we try to derefence them and they are able to perform a valid ++ or – step.

Ceturns a safe iterator pointing to the end of the List.

Definition at line 1281 of file list_tpl.h.

                                                               {
    return *(reinterpret_cast< const ListIteratorSafe< Val >* >(_list_end_safe_));
  }

References ListIteratorSafe< Val >.

Here is the call graph for this function:

◆ erase() [1/3]

template<typename Val>

void gum::List< Val >::erase ( const const_iterator_safe & iter )

Erases the element of the List pointed to by the safe const iterator.

If the element cannot be found, i.e., it has already been erased or the iterator points to end/rend, the function returns without throwing any exception. It runs in linear time in the size of the list.

Parameters

iter	An iterator pointing to the element to remove.

Definition at line 1778 of file list_tpl.h.

                                                         {
    _erase_(iter._getBucket_());
  }

References _erase_(), and gum::ListConstIteratorSafe< Val >::_getBucket_().

Here is the call graph for this function:

◆ erase() [2/3]

template<typename Val>

void gum::List< Val >::erase ( const iterator_safe & iter )

Erases the element of the List pointed to by the safe iterator.

If the element cannot be found, i.e., it has already been erased or the iterator points to end/rend, the function returns without throwing any exception. It runs in linear time in the size of the list.

Parameters

iter	An iterator pointing to the element to remove.

Definition at line 1772 of file list_tpl.h.

                                                   {
    _erase_(iter._getBucket_());
  }

References _erase_(), and gum::ListConstIteratorSafe< Val >::_getBucket_().

Here is the call graph for this function:

◆ erase() [3/3]

template<typename Val>

void gum::List< Val >::erase ( Size i )

Erases the ith element of the List (the first one is in position 0).

If the element cannot be found, the function returns without throwing any exception. It runs in linear time in the size of the list.

Parameters

i	The position in the list of the element we wish to remove.

Definition at line 1763 of file list_tpl.h.

                                {
    if (i >= _nb_elements_) return;
 
    // erase the ith bucket
    _erase_(_getIthBucket_(i));
  }

References _erase_(), _getIthBucket_(), and _nb_elements_.

Referenced by gum::prm::StructuredInference< GUM_SCALAR >::_reduceAloneInstances_().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ eraseAllVal()

template<typename Val>

void gum::List< Val >::eraseAllVal ( const Val & val )

erases all the elements encountered with a given value

If no element equal to val can be found, the function returns without throwing any exception.

Comparisons between Val instances are performed through == operators.

Parameters

val	the value of the element we wish to remove.

Definition at line 1799 of file list_tpl.h.

                                              {
    for (ListBucket< Val >*iter = _deb_list_, *next_bucket = nullptr; iter != nullptr;
         iter = next_bucket) {
      next_bucket = iter->_next_;
 
      if (val == iter->_val_) _erase_(iter);
    }
  }

References _deb_list_, and _erase_().

Here is the call graph for this function:

◆ eraseByVal()

template<typename Val>

void gum::List< Val >::eraseByVal ( const Val & val )

erases the first element encountered with a given value.

If no element equal to val can be found, the function returns without throwing any exception. It runs in linear time both in the size of the list and in the number of iterators referenced in the list. Comparisons between Val instances are performed through == operators.

Parameters

val	The value of the element we wish to remove.

Definition at line 1793 of file list_tpl.h.

                                             {
    _erase_(_getBucket_(val));
  }

References _erase_(), and _getBucket_().

Here is the call graph for this function:

◆ exists()

template<typename Val>

bool gum::List< Val >::exists ( const Val & val ) const

Checks whether there exists a given element in the list.

This method runs in linear time.

Comparisons between Val instances are performed through == operators.

Parameters

val	the value of the element we wish to check the existence of.

Returns: Returns true if val is in the gum::List.

Definition at line 1716 of file list_tpl.h.

                                               {
    for (ListBucket< Val >* ptr = _deb_list_; ptr != nullptr; ptr = ptr->_next_)
      if (ptr->_val_ == val) return true;
 
    return false;
  }

References _deb_list_, gum::ListBucket< Val >::_next_, and gum::ListBucket< Val >::_val_.

Referenced by gum::EssentialGraph::toDot(), gum::PDAG::toDot(), and gum::UndiGraph::toDot().

Here is the caller graph for this function:

◆ front()

template<typename Val>

Val & gum::List< Val >::front ( ) const

Returns a reference to first element of a list, if any.

Exceptions

NotFound exception is thrown if the list is empty.

Definition at line 1694 of file list_tpl.h.

                                {
    if (_nb_elements_ == Size(0)) { GUM_ERROR(NotFound, "not enough elements in the chained list") }
 
    return _deb_list_->_val_;
  }

References _deb_list_, _nb_elements_, and GUM_ERROR.

Referenced by gum::graph::_bayesBall_(), gum::prm::SVE< GUM_SCALAR >::_eliminateNodes_(), gum::prm::SVED< GUM_SCALAR >::_eliminateNodes_(), gum::prm::SVED< GUM_SCALAR >::_eliminateNodesDownward_(), gum::learning::ConstraintBasedLearning::_existsDirectedPath_(), gum::learning::SimpleMiic::_existsDirectedPath_(), gum::MeekRules::_existsDirectedPath_(), gum::BarrenNodesFinder::barrenNodes(), gum::BarrenNodesFinder::barrenNodes(), gum::graph::directedPath(), gum::graph::directedUnorientedPath(), gum::InfluenceDiagram< GUM_SCALAR >::existsPathBetween(), gum::InfluenceDiagram< GUM_SCALAR >::getChildrenDecision_(), gum::graph::hasDirectedPath(), gum::graph::hasUndirectedCycle(), gum::graph::mixedOrientedPath(), gum::graph::mixedUnorientedPath(), gum::BayesBall::relevantTensors(), gum::dSeparationAlgorithm::relevantTensors(), gum::dSeparationAlgorithm::requisiteNodes(), gum::DAGCycleDetector::setDAG(), and gum::graph::undirectedPath().

Here is the caller graph for this function:

◆ insert() [1/8]

template<typename Val>

Val & gum::List< Val >::insert	(	const const_iterator &	iter,
		const Val &	val,
		location	place = location::BEFORE )

Inserts a new element before or after a given iterator.

Parameters

iter	The iterator pointing where to inser the new element.
val	The value to insert.
place	Defines where to insert the new element relatively to iter.

Returns: Returns a reference on the copy inserted into the list.

Warning: Note that val is not actually inserted into the list. Rather, it is a copy of val that is inserted.

Definition at line 1667 of file list_tpl.h.

                                                                                     {
    return _insert_(iter, _createBucket_(val), place);
  }

References _createBucket_(), and _insert_().

Here is the call graph for this function:

◆ insert() [2/8]

template<typename Val>

Val & gum::List< Val >::insert	(	const const_iterator &	iter,
		Val &&	val,
		location	place = location::BEFORE )

Inserts an rvalue before or after a given iterator.

Parameters

iter	The iterator pointing where to inser the new element.
val	The value to insert.
place	Defines where to insert the new element relatively to iter.

Returns: Returns a reference on the copy inserted into the list.

Warning: Note that val is not actually inserted into the list. Rather, it is a copy of val that is inserted.

Definition at line 1674 of file list_tpl.h.

                                                                                {
    return _insert_(iter, _createBucket_(std::move(val)), place);
  }

References _createBucket_(), and _insert_().

Here is the call graph for this function:

◆ insert() [3/8]

template<typename Val>

Val & gum::List< Val >::insert	(	const const_iterator_safe &	iter,
		const Val &	val,
		location	place = location::BEFORE )

Inserts a new element before or after a given iterator.

Parameters

iter	The iterator pointing where to inser the new element.
val	The value to insert.
place	Defines where to insert the new element relatively to iter.

Returns: Returns a reference on the copy inserted into the list.

Warning: Note that val is not actually inserted into the list. Rather, it is a copy of val that is inserted.

Definition at line 1643 of file list_tpl.h.

                                                                                          {
    // if the iterator does not point to the list, raise an exception
    if (iter._list_ != this) {
      GUM_ERROR(InvalidArgument, "the iterator does not point to the correct list")
    }
 
    return _insert_(iter, _createBucket_(val), place);
  }

References _createBucket_(), _insert_(), gum::ListConstIteratorSafe< Val >::_list_, and GUM_ERROR.

Here is the call graph for this function:

◆ insert() [4/8]

template<typename Val>

Val & gum::List< Val >::insert	(	const const_iterator_safe &	iter,
		Val &&	val,
		location	place = location::BEFORE )

Inserts an rvalue before or after a given iterator.

Parameters

iter	The iterator pointing where to inser the new element.
val	The value to insert.
place	Defines where to insert the new element relatively to iter.

Returns: Returns a reference on the copy inserted into the list.

Warning: Note that val is not actually inserted into the list. Rather, it is a copy of val that is inserted.

Definition at line 1655 of file list_tpl.h.

                                                                                     {
    // if the iterator does not point to the list, raise an exception
    if (iter._list_ != this) {
      GUM_ERROR(InvalidArgument, "the iterator does not point to the correct list")
    }
 
    return _insert_(iter, _createBucket_(std::move(val)), place);
  }

References _createBucket_(), _insert_(), gum::ListConstIteratorSafe< Val >::_list_, and GUM_ERROR.

Here is the call graph for this function:

◆ insert() [5/8]

template<typename Val>

Val & gum::List< Val >::insert ( const Val & val )

Inserts a new element at the end of the chained list (alias of pushBack).

Parameters

val	The value inserted.

Returns: a reference on the copy inserted into the list.

Warning: Note that val is not actually inserted into the list. Rather, it is a copy of val that is inserted.

Definition at line 1508 of file list_tpl.h.

                                         {
    return pushBack(val);
  }

References pushBack().

Referenced by gum::graph::_bayesBall_(), gum::prm::SVE< GUM_SCALAR >::_eliminateNodes_(), gum::prm::SVED< GUM_SCALAR >::_eliminateNodes_(), gum::prm::SVED< GUM_SCALAR >::_eliminateNodesDownward_(), gum::prm::SVE< GUM_SCALAR >::_eliminateNodesUpward_(), gum::prm::gspan::StrictSearch< GUM_SCALAR >::_elimination_cost_(), gum::credal::CNMonteCarloSampling< GUM_SCALAR, BNInferenceEngine >::_insertEvidence_(), gum::prm::StructuredInference< GUM_SCALAR >::_reduceAloneInstances_(), gum::BarrenNodesFinder::barrenNodes(), gum::BarrenNodesFinder::barrenNodes(), gum::BayesBall::relevantTensors(), gum::dSeparationAlgorithm::relevantTensors(), gum::dSeparationAlgorithm::requisiteNodes(), gum::DAGCycleDetector::setDAG(), gum::EssentialGraph::toDot(), gum::PDAG::toDot(), and gum::UndiGraph::toDot().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ insert() [6/8]

template<typename Val>

Val & gum::List< Val >::insert	(	Size	pos,
		const Val &	val )

Inserts a new element at the ith pos of the chained list.

The first element of the list is at pos 0. After the insert, the element is placed precisely at pos if pos is less than the size of the list before insertion, else it is inserted at the end of the list.

Parameters

pos	The position where to inser the new element.
val	The value to insert.

Returns: a reference on the copy inserted into the list.

Warning: Note that val is not actually inserted into the list. Rather, it is a copy of val that is inserted.

Definition at line 1568 of file list_tpl.h.

                                                   {
    // if ther are fewer elements than pos, put the value at the end of the list
    if (_nb_elements_ <= pos) { return pushBack(val); }
 
    return _insertBefore_(_createBucket_(val), _getIthBucket_(pos));
  }

References _createBucket_(), _getIthBucket_(), _insertBefore_(), _nb_elements_, and pushBack().

Here is the call graph for this function:

◆ insert() [7/8]

template<typename Val>

Val & gum::List< Val >::insert	(	Size	pos,
		Val &&	val )

Insert an rvalue at the ith pos of the chained list.

The first element of the list is at pos 0. After the insert, the element is placed precisely at pos if pos is less than the size of the list before insertion, else it is inserted at the end of the list.

Parameters

pos	The position where to inser the new element.
val	The value to insert.

Returns: Returns a reference on the copy inserted into the list.

Definition at line 1577 of file list_tpl.h.

                                              {
    // if ther are fewer elements than pos, put the value at the end of the list
    if (_nb_elements_ <= pos) { return pushBack(std::move(val)); }
 
    return _insertBefore_(_createBucket_(std::move(val)), _getIthBucket_(pos));
  }

References _createBucket_(), _getIthBucket_(), _insertBefore_(), _nb_elements_, and pushBack().

Here is the call graph for this function:

◆ insert() [8/8]

template<typename Val>

Val & gum::List< Val >::insert ( Val && val )

Inserts a new element at the end of the chained list (alias of pushBack).

Parameters

val	The value inserted.

Returns: a reference on the copy inserted into the list.

Warning: Note that val is not actually inserted into the list. Rather, it is a copy of val that is inserted.

Definition at line 1514 of file list_tpl.h.

                                    {
    return pushBack(std::move(val));
  }

References pushBack().

Here is the call graph for this function:

◆ map() [1/4]

template<typename Val>

template<typename Mount>

List< Mount > gum::List< Val >::map ( const Mount & mount ) const

Creates a list of mountains with a given value from a list of val.

Parameters

mount the value taken by all the elements of the resulting list

Returns: Returns a lsit of mountains.

Template Parameters

Mount The type of mountains.

Definition at line 1892 of file list_tpl.h.

                                                         {
    // create a new empty list
    List< Mount > list;
 
    // fill the new list
    for (Size i = Size(0); i < _nb_elements_; ++i)
      list.pushBack(mount);
 
    return list;
  }

References List(), _nb_elements_, and pushBack().

Here is the call graph for this function:

◆ map() [2/4]

template<typename Val>

template<typename Mount>

List< Mount > gum::List< Val >::map ( Mount(* f )(const Val &) ) const

Creates a list of mountains from a list of val.

Parameters

f	A function that maps any Val element into a Mount

Returns: Returns a lsit of mountains.

Template Parameters

Mount The type of mountains.

Definition at line 1877 of file list_tpl.h.

                                                             {
    // create a new empty list
    List< Mount > list;
 
    // fill the new list
    for (const_iterator iter = begin(); iter != end(); ++iter) {
      list.pushBack(f(*iter));
    }
 
    return list;
  }

References List(), begin(), end(), and pushBack().

Here is the call graph for this function:

◆ map() [3/4]

template<typename Val>

template<typename Mount>

List< Mount > gum::List< Val >::map ( Mount(* f )(Val &) ) const

Creates a list of mountains from a list of val.

Parameters

f	A function that maps any Val element into a Mount

Returns: Returns a lsit of mountains.

Template Parameters

Mount The type of mountains.

Definition at line 1862 of file list_tpl.h.

                                                       {
    // create a new empty list
    List< Mount > list;
 
    // fill the new list
    for (const_iterator iter = begin(); iter != end(); ++iter) {
      list.pushBack(f(*iter));
    }
 
    return list;
  }

References List(), begin(), end(), and pushBack().

Here is the call graph for this function:

◆ map() [4/4]

template<typename Val>

template<typename Mount>

List< Mount > gum::List< Val >::map ( Mount(* f )(Val) ) const

Creates a list of mountains from a list of val.

Parameters

f	A function that maps any Val element into a Mount

Returns: Returns a lsit of mountains.

Template Parameters

Mount The type of mountains.

Definition at line 1847 of file list_tpl.h.

                                                      {
    // create a new empty list
    List< Mount > list;
 
    // fill the new list
    for (const_iterator iter = begin(); iter != end(); ++iter) {
      list.pushBack(f(*iter));
    }
 
    return list;
  }

References List(), begin(), end(), and pushBack().

Here is the call graph for this function:

◆ operator!=()

template<typename Val>

bool gum::List< Val >::operator!= ( const List< Val > & src ) const

Checks whether two lists are different (different elements or orders).

This method runs in time linear in the number of elements of the list.

Returns: Returns true if src and this gum::List are identical.

Definition at line 1933 of file list_tpl.h.

                                                         {
    return !operator==(src);
  }

References List(), and gum::operator==().

Here is the call graph for this function:

◆ operator+=() [1/2]

template<typename Val>

Val & gum::List< Val >::operator+= ( const Val & val )

Inserts a new element at the end of the list (alias of pushBack).

This enables writing code like list += xxx; to add element xxx to the list.

Warning: Note that val is not actually inserted into the list. Rather, it is a copy of val that is inserted.

Parameters

val	Tha value inserted int the list.

Returns: Returns a reference on the copy inserted into the list.

Definition at line 1906 of file list_tpl.h.

                                           {
    return pushBack(val);
  }

References pushBack().

Here is the call graph for this function:

◆ operator+=() [2/2]

template<typename Val>

Val & gum::List< Val >::operator+= ( Val && val )

Inserts a new element at the end of the list (alias of pushBack).

This enables writing code like list += xxx; to add element xxx to the list.

Warning: Note that val is not actually inserted into the list. Rather, it is a copy of val that is inserted.

Parameters

val	Tha value inserted int the list.

Returns: Returns a reference on the copy inserted into the list.

Definition at line 1913 of file list_tpl.h.

                                      {
    return pushBack(std::move(val));
  }

References pushBack().

Here is the call graph for this function:

◆ operator=() [1/2]

template<typename Val>

List< Val > & gum::List< Val >::operator= ( const List< Val > & src )

Copy operator.

The new list and that which is copied do not share the elements: the new list contains new instances of the values stored in the list to be copied. Of course if these values are pointers, the new values point toward the same elements. The List on which the operator is applied keeps its iterator's list. Of course, if it previously contained some elements, those are removed prior to the copy. This operator runs in linear time.

Warning: If the current List previously contained iterators, those will be resetted to end()/rend().

Parameters

src	the list the content of which will be copied into the current List.

Returns: Returns this gum::List.

Definition at line 1231 of file list_tpl.h.

                                                          {
    // avoid self assignment
    if (this != &src) {
      // for debugging purposes
      GUM_OP_CPY(List);
 
      // remove the old content of 'this' and update accordingly the iterators
      clear();
 
      // perform the copy
      _copy_elements_(src);
    }
 
    return *this;
  }

References List().

Here is the call graph for this function:

◆ operator=() [2/2]

template<typename Val>

List< Val > & gum::List< Val >::operator= ( List< Val > && src )

Move operator.

Parameters

src	The gum::List to move.

Returns: Returns this gum::List.

Definition at line 1249 of file list_tpl.h.

                                                     {
    // avoid self assignment
    if (this != &src) {
      // for debugging purposes
      GUM_OP_MOV(List);
 
      // remove the old content of 'this' and update accordingly the iterators
      clear();
 
      // perform the move
      _deb_list_       = std::move(src._deb_list_);
      _end_list_       = std::move(src._end_list_);
      _nb_elements_    = std::move(src._nb_elements_);
      _safe_iterators_ = std::move(src._safe_iterators_);
 
      src._deb_list_    = nullptr;
      src._end_list_    = nullptr;
      src._nb_elements_ = 0;
      src._safe_iterators_.clear();
    }
 
    return *this;
  }

References List(), _deb_list_, _end_list_, _nb_elements_, _safe_iterators_, and clear().

Here is the call graph for this function:

◆ operator==()

template<typename Val>

bool gum::List< Val >::operator== ( const List< Val > & src ) const

Checks whether two lists are identical (same elements in the same order).

This method runs in time linear in the number of elements of the list.

Returns: Returns true if src and this gum::List are identical.

Definition at line 1919 of file list_tpl.h.

                                                         {
    // check if the two lists have at least the same number of elements
    if (_nb_elements_ != src._nb_elements_) return false;
 
    // parse the two lists
    for (ListBucket< Val >*iter1 = _deb_list_, *iter2 = src._deb_list_; iter1 != nullptr;
         iter1 = iter1->_next_, iter2 = iter2->_next_)
      if (*iter1 != *iter2) return false;
 
    return true;
  }

References List(), _deb_list_, and _nb_elements_.

Here is the call graph for this function:

◆ operator[]() [1/2]

template<typename Val>

Val & gum::List< Val >::operator[] ( const Size i )

Returns the ith element in the current chained list.

The first of the list element has index 0.

This method runs in linear time.

Parameters

i	The position of the element in the list (0 = first element).

Exceptions

NotFound Raised if the element to be retrieved does not exist.

Returns: Returns a reference on the element stored at the ith position in the list.

Definition at line 1939 of file list_tpl.h.

                                           {
    // check if we can return the element we ask for
    if (i >= _nb_elements_) { GUM_ERROR(NotFound, "not enough elements in the chained list") }
 
    return **_getIthBucket_(i);
  }

References _getIthBucket_(), _nb_elements_, and GUM_ERROR.

Here is the call graph for this function:

◆ operator[]() [2/2]

template<typename Val>

const Val & gum::List< Val >::operator[] ( const Size i ) const

Returns the const ith element in the current chained list.

The first of the list element has index 0.

This method runs in linear time.

Parameters

i	the position of the element in the list (0 = first element).

Exceptions

NotFound Raised if the element to be retrieved does not exist.

Returns: Returns a reference on the element stored at the ith position in the list.

Definition at line 1948 of file list_tpl.h.

                                                       {
    // check if we can return the element we ask for
    if (i >= _nb_elements_) { GUM_ERROR(NotFound, "not enough elements in the chained list") }
 
    return **_getIthBucket_(i);
  }

References _getIthBucket_(), _nb_elements_, and GUM_ERROR.

Here is the call graph for this function:

◆ popBack()

template<typename Val>

void gum::List< Val >::popBack ( )

Removes the last element of a List, if any.

When the list is empty, it does not do anything.

Definition at line 1810 of file list_tpl.h.

                            {
    _erase_(_end_list_);
  }

References _end_list_, and _erase_().

Here is the call graph for this function:

◆ popFront()

template<typename Val>

void gum::List< Val >::popFront ( )

Removes the first element of a List, if any.

When the list is empty, it does not do anything.

Definition at line 1816 of file list_tpl.h.

                             {
    _erase_(_deb_list_);
  }

References _deb_list_, and _erase_().

Referenced by gum::graph::_bayesBall_(), gum::prm::SVE< GUM_SCALAR >::_eliminateNodes_(), gum::prm::SVED< GUM_SCALAR >::_eliminateNodes_(), gum::prm::SVED< GUM_SCALAR >::_eliminateNodesDownward_(), gum::learning::ConstraintBasedLearning::_existsDirectedPath_(), gum::learning::SimpleMiic::_existsDirectedPath_(), gum::MeekRules::_existsDirectedPath_(), gum::BarrenNodesFinder::barrenNodes(), gum::BarrenNodesFinder::barrenNodes(), gum::graph::directedPath(), gum::graph::directedUnorientedPath(), gum::InfluenceDiagram< GUM_SCALAR >::existsPathBetween(), gum::InfluenceDiagram< GUM_SCALAR >::getChildrenDecision_(), gum::graph::hasDirectedPath(), gum::graph::hasUndirectedCycle(), gum::graph::mixedOrientedPath(), gum::graph::mixedUnorientedPath(), gum::BayesBall::relevantTensors(), gum::dSeparationAlgorithm::relevantTensors(), gum::dSeparationAlgorithm::requisiteNodes(), gum::DAGCycleDetector::setDAG(), and gum::graph::undirectedPath().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ push_back()

template<typename Val>

template<typename... Args>

Val & gum::List< Val >::push_back ( Args &&... args )

An alias for pushBack used for STL compliance.

Defining push_back allows using, for instance, BackInserters.

Template Parameters

Args	The emplace arguments type.

Parameters

args	The emplace arguments values.

Returns: Returns a reference on the copy inserted into the list.

Definition at line 1494 of file list_tpl.h.

                                            {
    return pushBack(std::forward< Args >(args)...);
  }

References pushBack().

Referenced by gum::prm::SVE< GUM_SCALAR >::_initLiftedNodes_(), gum::prm::StructuredInference< GUM_SCALAR >::_reduceAloneInstances_(), gum::AggregatorDecomposition< GUM_SCALAR >::addDepthLayer_(), and gum::AggregatorDecomposition< GUM_SCALAR >::decomposeAggregator_().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ push_front()

template<typename Val>

template<typename... Args>

Val & gum::List< Val >::push_front ( Args &&... args )

An alias for pushFront used for STL compliance.

Defining push_front allows using, for instance, FrontInserters.

Template Parameters

Args	The emplace values type.

Parameters

args	The emplace values.

Returns: Returns a reference on the copy inserted into the list.

Definition at line 1468 of file list_tpl.h.

                                             {
    return pushFront(std::forward< Args >(args)...);
  }

References pushFront().

Here is the call graph for this function:

◆ pushBack() [1/2]

template<typename Val>

Val & gum::List< Val >::pushBack ( const Val & val )

Inserts a new element (a copy) at the end of the chained list.

The value passed in argument is not actually inserted into the list: this is a copy of this value that is inserted. The method runs in constant time.

Parameters

val	The value pushed back.

Returns: Returns a reference on the copy inserted into the list.

Warning: Note that val is not actually inserted into the list. Rather, it is a copy of val that is inserted.

Definition at line 1481 of file list_tpl.h.

                                           {
    return _pushBack_(_createBucket_(val));
  }

References _createBucket_(), and _pushBack_().

Referenced by gum::learning::ConstraintBasedLearning::_existsDirectedPath_(), gum::learning::SimpleMiic::_existsDirectedPath_(), gum::MeekRules::_existsDirectedPath_(), gum::BayesNetFactory< GUM_SCALAR >::_fillProbaWithValuesTable_(), gum::prm::SVED< GUM_SCALAR >::_initLiftedNodes_(), gum::graph::directedPath(), gum::graph::directedUnorientedPath(), gum::InfluenceDiagram< GUM_SCALAR >::existsPathBetween(), gum::InfluenceDiagram< GUM_SCALAR >::getChildrenDecision_(), gum::graph::hasDirectedPath(), gum::graph::hasUndirectedCycle(), insert(), insert(), insert(), insert(), gum::Set< Key >::listMap(), map(), map(), map(), map(), gum::graph::mixedOrientedPath(), gum::graph::mixedUnorientedPath(), operator+=(), operator+=(), push_back(), and gum::graph::undirectedPath().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ pushBack() [2/2]

template<typename Val>

Val & gum::List< Val >::pushBack ( Val && val )

Inserts a new element (a move) at the end of the chained list.

The value passed in argument is not actually inserted into the list: this is a copy of this value that is inserted. The method runs in constant time.

Parameters

val	The value pushed back.

Returns: Returns a reference on the copy inserted into the list.

Warning: Note that val is not actually inserted into the list. Rather, it is a copy of val that is inserted.

Definition at line 1487 of file list_tpl.h.

                                      {
    return _pushBack_(_createBucket_(std::move(val)));
  }

References _createBucket_(), and _pushBack_().

Here is the call graph for this function:

◆ pushFront() [1/2]

template<typename Val>

Val & gum::List< Val >::pushFront ( const Val & val )

Inserts a new element (a copy) at the beginning of the chained list.

The value passed in argument is not actually inserted into the list: this is a copy of this value that is inserted. The method runs in constant time.

Parameters

val	The valus pushed at the front.

Returns: Returns a reference on the copy inserted into the list.

Warning: Note that val is not actually inserted into the list. Rather, it is a copy of val that is inserted.

Definition at line 1455 of file list_tpl.h.

                                            {
    return _pushFront_(_createBucket_(val));
  }

References _createBucket_(), and _pushFront_().

Referenced by push_front().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ pushFront() [2/2]

template<typename Val>

Val & gum::List< Val >::pushFront ( Val && val )

Inserts a new element (a move) at the beginning of the chained list.

Parameters

val	The valus pushed at the front.

Returns: Returns a reference on the copy inserted into the list.

Warning: Note that val is not actually inserted into the list. Rather, it is a copy of val that is inserted.

Definition at line 1461 of file list_tpl.h.

                                       {
    return _pushFront_(_createBucket_(std::move(val)));
  }

References _createBucket_(), and _pushFront_().

Here is the call graph for this function:

◆ rbegin() [1/2]

template<typename Val>

ListIterator< Val > gum::List< Val >::rbegin ( )

Returns an unsafe iterator pointing to the last element of the List.

Unsafe iterators are a little bit faster than safe iterators and they consume less memory. However, if the element they point to is erased, their dereference or their increment/decrement will produce a mess, probably a segfault. You should use them only when performance is an issue and if you are sure that they will never point to an element erased.

Returns: Returns an unsafe iterator pointing to the last element of the List.

Definition at line 1386 of file list_tpl.h.

                                          {
    if (_nb_elements_) return ListIterator< Val >{*this, _nb_elements_ - 1};
    else return ListIterator< Val >{};
  }

References _nb_elements_, and ListIterator< Val >.

Here is the call graph for this function:

◆ rbegin() [2/2]

template<typename Val>

ListConstIterator< Val > gum::List< Val >::rbegin ( ) const

Returns an unsafe const iterator pointing to the last element of the List.

Unsafe iterators are a little bit faster than safe iterators and they consume less memory. However, if the element they point to is erased, their dereference or their increment/decrement will produce a mess, probably a segfault. You should use them only when performance is an issue and if you are sure that they will never point to an element erased.

Returns: Returns an unsafe const iterator pointing to the last element of the List.

Definition at line 1393 of file list_tpl.h.

                                                     {
    if (_nb_elements_) return ListConstIterator< Val >{*this, _nb_elements_ - 1};
    else return ListConstIterator< Val >{};
  }

References _nb_elements_, and ListConstIterator< Val >.

Here is the call graph for this function:

◆ rbeginSafe()

template<typename Val>

ListIteratorSafe< Val > gum::List< Val >::rbeginSafe ( )

Returns a safe iterator pointing to the last element of the List.

Safe iterators are iterators whose state is updated by the list when the element they point to is erased. As such, in this case, they can throw an exception when we try to derefence them and they are able to perform a valid ++ or – step.

Returns: Returns a safe iterator pointing to the last element of the List.

Definition at line 1372 of file list_tpl.h.

                                                  {
    if (_nb_elements_) return ListIteratorSafe< Val >{*this, _nb_elements_ - 1};
    else return ListIteratorSafe< Val >{};
  }

References _nb_elements_, and ListIteratorSafe< Val >.

Here is the call graph for this function:

◆ rend() [1/2]

template<typename Val>

const ListConstIterator< Val > & gum::List< Val >::rend ( ) const

noexcept

Returns an unsafe const iterator pointing just before the beginning of the List.

Unsafe const iterators are a little bit faster than safe const iterators and they consume less memory. However, if the element they point to is erased, their dereference or their increment/decrement will produce a mess, probably a segfault. You should use them only when performance is an issue and if you are sure that they will never point to an element erased.

Returns: Returns an unsafe const iterator pointing just before the beginning of the List.

Definition at line 1329 of file list_tpl.h.

                                                                   {
    return *(reinterpret_cast< const ListConstIterator< Val >* >(_list_end_));
  }

References ListConstIterator< Val >.

Here is the call graph for this function:

◆ rend() [2/2]

template<typename Val>

const ListIterator< Val > & gum::List< Val >::rend ( )

noexcept

Returns an unsafe iterator pointing just before the beginning of the List.

Unsafe iterators are a little bit faster than safe iterators and they consume less memory. However, if the element they point to is erased, their dereference or their increment/decrement will produce a mess, probably a segfault. You should use them only when performance is an issue and if you are sure that they will never point to an element erased.

Returns an unsafe iterator pointing just before the beginning of the List.

Definition at line 1323 of file list_tpl.h.

                                                        {
    return *(reinterpret_cast< const ListIterator< Val >* >(_list_end_));
  }

References ListIterator< Val >.

Here is the call graph for this function:

◆ rendSafe()

template<typename Val>

const ListIteratorSafe< Val > & gum::List< Val >::rendSafe ( )

noexcept

Returns a safe iterator pointing just before the beginning of the List.

Safe iterators are iterators whose state is updated by the list when the element they point to is erased. As such, in this case, they can throw an exception when we try to derefence them and they are able to perform a valid ++ or – step.

Returns: Returns a safe iterator pointing just before the beginning of the List.

Definition at line 1311 of file list_tpl.h.

                                                                {
    return *(reinterpret_cast< const ListIteratorSafe< Val >* >(_list_end_safe_));
  }

◆ size()

template<typename Val>

Size gum::List< Val >::size ( ) const

noexcept

Returns the number of elements in the list.

This method runs in constant time.

Definition at line 1710 of file list_tpl.h.

                                        {
    return _nb_elements_;
  }

References _nb_elements_.

Referenced by gum::BayesNetFactory< GUM_SCALAR >::_fillProbaWithValuesTable_(), gum::BayesNetFactory< GUM_SCALAR >::_increment_(), gum::credal::CNMonteCarloSampling< GUM_SCALAR, BNInferenceEngine >::_insertEvidence_(), and gum::prm::StructuredInference< GUM_SCALAR >::_reduceAloneInstances_().

Here is the caller graph for this function:

◆ swap()

template<typename Val>

void gum::List< Val >::swap ( List< Val > & other_list )

Swap the current list with another one.

Parameters

other_list The list to swap elements with.

Definition at line 1957 of file list_tpl.h.

                                         {
    std::swap(_deb_list_, other_list._deb_list_);
    std::swap(_end_list_, other_list._end_list_);
    std::swap(_nb_elements_, other_list._nb_elements_);
    std::swap(_safe_iterators_, other_list._safe_iterators_);
  }

References List(), _deb_list_, _end_list_, _nb_elements_, and _safe_iterators_.

Here is the call graph for this function:

◆ toString()

template<typename Val>

std::string gum::List< Val >::toString ( ) const

Converts a list into a string.

Returns: Returns a std::string representation of the gum::List.

Definition at line 1828 of file list_tpl.h.

                                        {
    bool              deja = false;
    std::stringstream stream;
    stream << "[";
 
    for (ListBucket< Val >* ptr = _deb_list_; ptr != nullptr; ptr = ptr->_next_, deja = true) {
      if (deja) stream << " --> ";
 
      stream << ptr->_val_;
    }
 
    stream << "]";
 
    return stream.str();
  }

References _deb_list_, gum::ListBucket< Val >::_next_, and gum::ListBucket< Val >::_val_.

Referenced by gum::operator<<().

Here is the caller graph for this function:

◆ ListConstIterator< Val >

template<typename Val>

friend class ListConstIterator< Val >

friend

ListIterator should be a friend to optimize access to elements.

Definition at line 1384 of file list.h.

Referenced by begin(), cbegin(), cend(), crbegin(), crend(), end(), rbegin(), and rend().

◆ ListConstIteratorSafe< Val >

template<typename Val>

friend class ListConstIteratorSafe< Val >

friend

ListIterator should be a friend to optimize access to elements.

Definition at line 1384 of file list.h.

Referenced by cbeginSafe(), cendSafe(), crbeginSafe(), and crendSafe().

◆ ListIterator< Val >

template<typename Val>

friend class ListIterator< Val >

friend

ListIterator should be a friend to optimize access to elements.

Definition at line 1384 of file list.h.

Referenced by begin(), end(), rbegin(), and rend().

◆ ListIteratorSafe< Val >

template<typename Val>

friend class ListIteratorSafe< Val >

friend

ListIterator should be a friend to optimize access to elements.

Definition at line 1384 of file list.h.

Referenced by endSafe(), and rbeginSafe().

Member Data Documentation

◆ _deb_list_

template<typename Val>

ListBucket< Val >* gum::List< Val >::_deb_list_ {nullptr}

private

A pointer on the first element of the chained list.

Definition at line 1253 of file list.h.

1253{nullptr};

Referenced by List(), _erase_(), _getBucket_(), _getIthBucket_(), _insertBefore_(), _pushBack_(), _pushFront_(), clear(), eraseAllVal(), exists(), front(), gum::List< gum::Instantiation * >::map(), operator=(), operator==(), popFront(), swap(), and toString().

◆ _end_list_

template<typename Val>

ListBucket< Val >* gum::List< Val >::_end_list_ {nullptr}

private

A pointer on the last element of the chained list.

Definition at line 1256 of file list.h.

1256{nullptr};

Referenced by _erase_(), _getIthBucket_(), _insertAfter_(), _pushBack_(), _pushFront_(), back(), clear(), operator=(), popBack(), and swap().

◆ _nb_elements_

template<typename Val>

Size gum::List< Val >::_nb_elements_ {Size(0)}

private

The number of elements in the list.

Definition at line 1259 of file list.h.

1259{Size(0)};

Referenced by gum::ListConstIterator< Val >::ListConstIterator(), _erase_(), _getIthBucket_(), _insertAfter_(), _insertBefore_(), _pushBack_(), _pushFront_(), back(), clear(), crbegin(), crbeginSafe(), empty(), erase(), front(), insert(), insert(), map(), operator=(), operator==(), operator[](), operator[](), rbegin(), rbegin(), rbeginSafe(), size(), and swap().

◆ _safe_iterators_

template<typename Val>

std::vector< const_iterator_safe* > gum::List< Val >::_safe_iterators_

mutableprivate

The list of "safe" iterators attached to the list.

Definition at line 1262 of file list.h.

Referenced by List(), _erase_(), clear(), operator=(), and swap().

The documentation for this class was generated from the following files:

agrum/base/core/list.h
agrum/base/core/list_tpl.h

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Friends

Detailed Description

Member Typedef Documentation

◆ const_iterator

◆ const_iterator_safe

◆ const_pointer

◆ const_reference

◆ difference_type

◆ iterator

◆ iterator_safe

◆ pointer

◆ reference

◆ size_type

◆ value_type

Member Enumeration Documentation

◆ location

Constructor & Destructor Documentation

◆ List() [1/4]

◆ List() [2/4]

◆ List() [3/4]

◆ List() [4/4]

◆ ~List()

Member Function Documentation

◆ _copy_elements_()

◆ _createBucket_() [1/2]

◆ _createBucket_() [2/2]

◆ _createEmplaceBucket_()

◆ _erase_()

◆ _getBucket_()

◆ _getIthBucket_()

◆ _insert_() [1/2]

◆ _insert_() [2/2]

◆ _insertAfter_()

◆ _insertBefore_()

◆ _pushBack_()

◆ _pushFront_()

◆ back()

◆ begin() [1/2]

◆ begin() [2/2]

◆ beginSafe()

◆ cbegin()

◆ cbeginSafe()

◆ cend()

◆ cendSafe()

◆ clear()

◆ crbegin()

◆ crbeginSafe()

◆ crend()

◆ crendSafe()

◆ emplace() [1/2]

◆ emplace() [2/2]

◆ emplaceBack()

◆ emplaceFront()

◆ empty()

◆ end() [1/2]

◆ end() [2/2]

◆ endSafe()

◆ erase() [1/3]

◆ erase() [2/3]

◆ erase() [3/3]

◆ eraseAllVal()

◆ eraseByVal()

◆ exists()

◆ front()

◆ insert() [1/8]

◆ insert() [2/8]

◆ insert() [3/8]

◆ insert() [4/8]

◆ insert() [5/8]

◆ insert() [6/8]

◆ insert() [7/8]

◆ insert() [8/8]

◆ map() [1/4]

◆ map() [2/4]

◆ map() [3/4]

◆ map() [4/4]