tools/core/list_tpl.h

/**
 *
 *   Copyright (c) 2005-2021 by Pierre-Henri WUILLEMIN(_at_LIP6) & Christophe GONZALES(_at_AMU)
 *   info_at_agrum_dot_org
 *
 *  This library is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU Lesser General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This library is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU Lesser General Public License for more details.
 *
 *  You should have received a copy of the GNU Lesser General Public License
 *  along with this library.  If not, see <http://www.gnu.org/licenses/>.
 *
 */


/**
 * @file
 * @brief template implementation of chained lists
 *
 * @author Christophe GONZALES(_at_AMU) and Pierre-Henri WUILLEMIN(_at_LIP6)
 */

// to ease parser
#include <agrum/tools/core/list.h>

namespace gum {

  // ===========================================================================
  // ===========================================================================
  // ===                         BUCKET IMPLEMENTATION                       ===
  // ===========================================================================
  // ===========================================================================

  // default constructor
  template < typename Val >
  INLINE ListBucket< Val >::ListBucket(const Val& v) : _val_{v} {
    // for debugging purposes
    GUM_CONSTRUCTOR(ListBucket);
  }

  // constructor for Val rvalues
  template < typename Val >
  INLINE ListBucket< Val >::ListBucket(Val&& v) noexcept : _val_{std::move(v)} {
    // for debugging purposes
    GUM_CONSTRUCTOR(ListBucket);
  }

  // emplace constructor
  template < typename Val >
  template < typename... Args >
  INLINE ListBucket< Val >::ListBucket(typename ListBucket< Val >::Emplace, Args&&... args) :
      _val_(std::forward< Args >(args)...) {
    // for debugging purposes
    GUM_CONSTRUCTOR(ListBucket);
  }

  // copy constructor
  template < typename Val >
  INLINE ListBucket< Val >::ListBucket(const ListBucket< Val >& src) : _val_{src._val_} {
    // for debugging purposes
    GUM_CONS_CPY(ListBucket);
  }

  // copy operator
  template < typename Val >
  INLINE ListBucket< Val >& ListBucket< Val >::operator=(const ListBucket< Val >& src) {
    // for debugging purposes
    GUM_OP_CPY(ListBucket);

    // no need to avoid self assignment
    _val_ = src._val_;
    return *this;
  }

  // WARNING: during its deletion, the bucket does not take care of properly
  // re-chaining the chained list. This should be done by the Lists themselves
  template < typename Val >
  INLINE ListBucket< Val >::~ListBucket() {
    // for debugging purposes
    GUM_DESTRUCTOR(ListBucket);
  }

  // equality check
  template < typename Val >
  INLINE bool ListBucket< Val >::operator==(const ListBucket< Val >& src) const {
    return (src._val_ == _val_);
  }

  // inequality check
  template < typename Val >
  INLINE bool ListBucket< Val >::operator!=(const ListBucket< Val >& src) const {
    return (src._val_ != _val_);
  }

  // dereferencing operator
  template < typename Val >
  INLINE const Val& ListBucket< Val >::operator*() const noexcept {
    return _val_;
  }

  // dereferencing operator
  template < typename Val >
  INLINE Val& ListBucket< Val >::operator*() noexcept {
    return _val_;
  }

  // returns the bucket toward the next element
  template < typename Val >
  INLINE const ListBucket< Val >* ListBucket< Val >::next() const noexcept {
    return _next_;
  }

  // returns the bucket toward the preceding element
  template < typename Val >
  INLINE const ListBucket< Val >* ListBucket< Val >::previous() const noexcept {
    return _prev_;
  }

  // ===========================================================================
  // ===========================================================================
  // ===               UNSAFE_CONST_LIST_ITERATOR IMPLEMENTATION             ===
  // ===========================================================================
  // ===========================================================================

  // default constructor
  template < typename Val >
  INLINE ListConstIterator< Val >::ListConstIterator() noexcept {
    // for debugging purposes
    GUM_CONSTRUCTOR(ListConstIterator);
  }

  // default constructor
  template < typename Val >
  template < typename Alloc >
  INLINE ListConstIterator< Val >::ListConstIterator(const List< Val, Alloc >& theList) noexcept :
      _bucket_{theList._deb_list_} {
    // for debugging purposes
    GUM_CONSTRUCTOR(ListConstIterator);
  }

  // copy constructor
  template < typename Val >
  INLINE ListConstIterator< Val >::ListConstIterator(const ListConstIterator< Val >& src) noexcept :
      _bucket_{src._bucket_} {
    // for debugging purposes
    GUM_CONS_CPY(ListConstIterator);
  }

  // move constructor
  template < typename Val >
  INLINE ListConstIterator< Val >::ListConstIterator(ListConstIterator< Val >&& src) noexcept :
      _bucket_{std::move(src._bucket_)} {
    // for debugging purposes
    GUM_CONS_MOV(ListConstIterator);
  }

  // Constructor for an iterator pointing to the \e ind_eltth element of a
  // List.
  template < typename Val >
  INLINE ListConstIterator< Val >::ListConstIterator(const List< Val >& theList, Size ind_elt) {
    // for debugging purposes
    GUM_CONSTRUCTOR(ListConstIterator);

    // check if the index ind_elt passed as parameter is valid
    if (ind_elt >= theList._nb_elements_) {
      GUM_ERROR(UndefinedIteratorValue, "Not enough elements in the list")
    }

    // check if it is faster to find the indexth element from the start or
    // from the end of the list
    if (ind_elt < (theList._nb_elements_ >> 1)) {
      // find the element we shall point to src the start of the list
      for (_bucket_ = theList._deb_list_; ind_elt; --ind_elt, _bucket_ = _bucket_->_next_) {}
    } else {
      // find the element we shall point to src the end of the list
      for (_bucket_ = theList._end_list_, ind_elt = theList._nb_elements_ - ind_elt - 1; ind_elt;
           --ind_elt, _bucket_                    = _bucket_->_prev_) {}
    }
  }

  // Destructor
  template < typename Val >
  INLINE ListConstIterator< Val >::~ListConstIterator() noexcept {
    // for debugging purposes
    GUM_DESTRUCTOR(ListConstIterator);
  }

  // Copy operator
  template < typename Val >
  INLINE ListConstIterator< Val >&
     ListConstIterator< Val >::operator=(const ListConstIterator< Val >& src) noexcept {
    // for debugging purposes
    GUM_OP_CPY(ListConstIterator);

    _bucket_ = src._bucket_;
    return *this;
  }

  // move operator
  template < typename Val >
  INLINE ListConstIterator< Val >&
     ListConstIterator< Val >::operator=(ListConstIterator< Val >&& src) noexcept {
    // for debugging purposes
    GUM_OP_MOV(ListConstIterator);
    _bucket_ = src._bucket_;
    return *this;
  }

  // returns the bucket the iterator is pointing to
  template < typename Val >
  INLINE ListBucket< Val >* ListConstIterator< Val >::_getBucket_() const noexcept {
    return _bucket_;
  }

  // Makes the iterator point toward nothing
  template < typename Val >
  INLINE void ListConstIterator< Val >::clear() noexcept {
    _bucket_ = nullptr;
  }

  // positions the iterator to the end of the list
  template < typename Val >
  INLINE void ListConstIterator< Val >::setToEnd() noexcept {
    _bucket_ = nullptr;
  }

  // returns a bool indicating whether the iterator points to the end of the
  // list
  template < typename Val >
  INLINE bool ListConstIterator< Val >::isEnd() const noexcept {
    return (_bucket_ == nullptr);
  }

  // makes the iterator point to the next element in the List
  template < typename Val >
  INLINE ListConstIterator< Val >& ListConstIterator< Val >::operator++() noexcept {
    // if we are pointing to an element of the chained list, just
    // point on the next bucket in this list
    if (_bucket_ != nullptr) { _bucket_ = _bucket_->_next_; }

    return *this;
  }

  // makes the iterator point to the next element in the List
  template < typename Val >
  INLINE ListConstIterator< Val >& ListConstIterator< Val >::operator+=(
     typename ListConstIterator< Val >::difference_type i) noexcept {
    if (i >= 0) {
      for (; i && (_bucket_ != nullptr); --i, _bucket_ = _bucket_->_next_) {}
    } else {
      for (; i && (_bucket_ != nullptr); ++i, _bucket_ = _bucket_->_prev_) {}
    }
    return *this;
  }

  // makes the iterator point to the preceding element in the List
  template < typename Val >
  INLINE ListConstIterator< Val >& ListConstIterator< Val >::operator--() noexcept {
    // if we are pointing to an element of the chained list, just
    // point on the preceding bucket in this list
    if (_bucket_ != nullptr) { _bucket_ = _bucket_->_prev_; }

    return *this;
  }

  // makes the iterator point to i elements before in the list
  template < typename Val >
  INLINE ListConstIterator< Val >& ListConstIterator< Val >::operator-=(
     typename ListConstIterator< Val >::difference_type i) noexcept {
    if (i >= 0) {
      for (; i && (_bucket_ != nullptr); --i, _bucket_ = _bucket_->_prev_) {}
    } else {
      for (; i && (_bucket_ != nullptr); ++i, _bucket_ = _bucket_->_next_) {}
    }
    return *this;
  }

  // returns a new iterator
  template < typename Val >
  INLINE ListConstIterator< Val > ListConstIterator< Val >::operator+(
     typename ListConstIterator< Val >::difference_type i) noexcept {
    return ListConstIterator< Val >(*this) += i;
  }

  // returns a new iterator
  template < typename Val >
  INLINE ListConstIterator< Val > ListConstIterator< Val >::operator-(
     typename ListConstIterator< Val >::difference_type i) noexcept {
    return ListConstIterator< Val >(*this) -= i;
  }

  // checks whether two iterators point toward different elements
  template < typename Val >
  INLINE bool
     ListConstIterator< Val >::operator!=(const ListConstIterator< Val >& src) const noexcept {
    return (_bucket_ != src._bucket_);
  }

  // checks whether two iterators point toward the same elements.
  template < typename Val >
  INLINE bool
     ListConstIterator< Val >::operator==(const ListConstIterator< Val >& src) const noexcept {
    return (_bucket_ == src._bucket_);
  }

  // dereferences the value pointed to by the iterator
  template < typename Val >
  INLINE const Val* ListConstIterator< Val >::operator->() const {
    if (_bucket_ != nullptr)
      return &(_bucket_->_val_);
    else {
      GUM_ERROR(UndefinedIteratorValue, "Accessing a NULL object")
    }
  }

  // gives access to the content of the iterator
  template < typename Val >
  INLINE const Val& ListConstIterator< Val >::operator*() const {
    if (_bucket_ != nullptr)
      return _bucket_->_val_;
    else {
      GUM_ERROR(UndefinedIteratorValue, "Accessing a NULL object")
    }
  }

  // for STL compliance, a distance operator
  template < typename Val >
  INLINE typename ListConstIterator< Val >::difference_type
     operator-(const ListConstIterator< Val >& iter1, const ListConstIterator< Val >& iter2) {
    typename ListConstIterator< Val >::difference_type res = 0;

    for (ListConstIterator< Val > iter3 = iter2; iter1 != iter3; ++iter3, ++res) {}

    return res;
  }

  // ===========================================================================
  // ===========================================================================
  // ===                  UNSAFE_LIST_ITERATOR IMPLEMENTATION                ===
  // ===========================================================================
  // ===========================================================================

  // basic constructor
  template < typename Val >
  INLINE ListIterator< Val >::ListIterator() noexcept : ListConstIterator< Val >() {
    GUM_CONSTRUCTOR(ListIterator);
  }

  // constructor for a begin
  template < typename Val >
  template < typename Alloc >
  INLINE ListIterator< Val >::ListIterator(const List< Val, Alloc >& theList) noexcept :
      ListConstIterator< Val >(theList) {
    GUM_CONSTRUCTOR(ListIterator);
  }

  // copy constructor
  template < typename Val >
  INLINE ListIterator< Val >::ListIterator(const ListIterator< Val >& src) noexcept :
      ListConstIterator< Val >(src) {
    GUM_CONS_CPY(ListIterator);
  }

  // move constructor
  template < typename Val >
  INLINE ListIterator< Val >::ListIterator(ListIterator< Val >&& src) noexcept :
      ListConstIterator< Val >(std::move(src)) {
    GUM_CONS_MOV(ListIterator);
  }

  // Constructor for an iterator pointing to the \e ind_eltth element of a
  // List.
  template < typename Val >
  INLINE ListIterator< Val >::ListIterator(const List< Val >& theList, Size ind_elt) :
      ListConstIterator< Val >(theList, ind_elt) {
    GUM_CONSTRUCTOR(ListIterator);
  }

  // Copy operator
  template < typename Val >
  INLINE ListIterator< Val >&
     ListIterator< Val >::operator=(const ListIterator< Val >& src) noexcept {
    GUM_OP_CPY(ListIterator);
    ListConstIterator< Val >::operator=(src);
    return *this;
  }

  // move operator
  template < typename Val >
  INLINE ListIterator< Val >& ListIterator< Val >::operator=(ListIterator< Val >&& src) noexcept {
    GUM_OP_MOV(ListIterator);
    ListConstIterator< Val >::operator=(std::move(src));
    return *this;
  }

  // Destructor
  template < typename Val >
  INLINE ListIterator< Val >::~ListIterator() noexcept {
    GUM_DESTRUCTOR(ListIterator);
  }

  // makes the iterator point to the next element in the List
  template < typename Val >
  INLINE ListIterator< Val >& ListIterator< Val >::operator++() noexcept {
    ListConstIterator< Val >::operator++();
    return *this;
  }

  // makes the iterator point to i elements further in the List
  template < typename Val >
  INLINE ListIterator< Val >&
     ListIterator< Val >::operator+=(typename ListIterator< Val >::difference_type i) noexcept {
    ListConstIterator< Val >::operator+=(i);
    return *this;
  }

  // makes the iterator point to the preceding element in the List
  template < typename Val >
  INLINE ListIterator< Val >& ListIterator< Val >::operator--() noexcept {
    ListConstIterator< Val >::operator--();
    return *this;
  }

  // makes the iterator point to i elements before in the List
  template < typename Val >
  INLINE ListIterator< Val >&
     ListIterator< Val >::operator-=(typename ListIterator< Val >::difference_type i) noexcept {
    ListConstIterator< Val >::operator-=(i);
    return *this;
  }

  // returns a new iterator
  template < typename Val >
  INLINE ListIterator< Val >
     ListIterator< Val >::operator+(typename ListIterator< Val >::difference_type i) noexcept {
    return ListIterator< Val >(*this) += i;
  }

  // returns a new iterator
  template < typename Val >
  INLINE ListIterator< Val >
     ListIterator< Val >::operator-(typename ListIterator< Val >::difference_type i) noexcept {
    return ListIterator< Val >(*this) -= i;
  }

  // dereferences the value pointed to by the iterator
  template < typename Val >
  INLINE Val* ListIterator< Val >::operator->() {
    return const_cast< Val* >(ListConstIterator< Val >::operator->());
  }

  // gives access to the content of the iterator
  template < typename Val >
  INLINE Val& ListIterator< Val >::operator*() {
    return const_cast< Val& >(ListConstIterator< Val >::operator*());
  }

  // ===========================================================================
  // ===========================================================================
  // ===               SAFE LIST CONST ITERATOR IMPLEMENTATION               ===
  // ===========================================================================
  // ===========================================================================

  // basic constructor
  template < typename Val >
  INLINE ListConstIteratorSafe< Val >::ListConstIteratorSafe() noexcept {
    // for debugging purposes
    GUM_CONSTRUCTOR(ListConstIteratorSafe);
  }

  // Constructor for a begin
  template < typename Val >
  template < typename Alloc >
  INLINE ListConstIteratorSafe< Val >::ListConstIteratorSafe(const List< Val, Alloc >& theList) :
      _list_{reinterpret_cast< const List< Val, std::allocator< Val > >* >(&theList)},
      _bucket_{theList._deb_list_} {
    // for debugging purposes
    GUM_CONSTRUCTOR(ListConstIteratorSafe);

    // add the iterator to the list of safe iterators
    theList._safe_iterators_.push_back(this);
  }

  // copy constructor
  template < typename Val >
  INLINE
     ListConstIteratorSafe< Val >::ListConstIteratorSafe(const ListConstIteratorSafe< Val >& src) :
      _list_{src._list_},
      _bucket_{src._bucket_}, _next_current_bucket_{src._next_current_bucket_},
      _prev_current_bucket_{src._prev_current_bucket_}, _null_pointing_{src._null_pointing_} {
    // for debugging purposes
    GUM_CONS_CPY(ListConstIteratorSafe);

    // add the iterator to the list of safe iterators
    if (_list_ != nullptr) _list_->_safe_iterators_.push_back(this);
  }

  // Constructor for an iterator pointing to the \e ind_eltth element of a
  // List.
  template < typename Val >
  template < typename Alloc >
  ListConstIteratorSafe< Val >::ListConstIteratorSafe(const List< Val, Alloc >& theList,
                                                      Size                      ind_elt) :
      _list_{reinterpret_cast< const List< Val, std::allocator< Val > >* >(&theList)} {
    // for debugging purposes
    GUM_CONSTRUCTOR(ListConstIteratorSafe);

    // check if the index ind_elt passed as parameter is valid
    if (ind_elt >= _list_->_nb_elements_) {
      GUM_ERROR(UndefinedIteratorValue, "Not enough elements in the list")
    }

    // check if it is faster to find the indexth element src the start or
    // src the end of the list
    if (ind_elt < (_list_->_nb_elements_ >> 1)) {
      // find the element we shall point to src the start of the list
      for (_bucket_ = _list_->_deb_list_; ind_elt; --ind_elt, _bucket_ = _bucket_->_next_) {}
    } else {
      // find the element we shall point to src the end of the list
      for (_bucket_ = _list_->_end_list_, ind_elt = _list_->_nb_elements_ - ind_elt - 1; ind_elt;
           --ind_elt, _bucket_                    = _bucket_->_prev_) {}
    }

    // add the iterator to the list of safe iterators
    theList._safe_iterators_.push_back(this);
  }

  // move constructor
  template < typename Val >
  INLINE ListConstIteratorSafe< Val >::ListConstIteratorSafe(ListConstIteratorSafe< Val >&& src) :
      _list_{src._list_}, _bucket_{src._bucket_}, _next_current_bucket_{src._next_current_bucket_},
      _prev_current_bucket_{src._prev_current_bucket_}, _null_pointing_{src._null_pointing_} {
    // for debugging purposes
    GUM_CONS_MOV(ListConstIteratorSafe);

    if (_list_ != nullptr) {
      // substitute src by this in the list of safe iterators
      std::vector< ListConstIteratorSafe< Val >* >& vect = _list_->_safe_iterators_;

      for (auto ptr = vect.rbegin(); ptr != vect.rend(); --ptr) {
        if (*ptr == &src) {
          *ptr = this;
          break;
        }
      }

      src._list_          = nullptr;
      src._bucket_        = nullptr;
      src._null_pointing_ = false;
    }
  }

  // remove the iterator for its list' safe iterators list
  template < typename Val >
  INLINE void ListConstIteratorSafe< Val >::_removeFromSafeList_() const {
    // find where the iterator is
    std::vector< ListConstIteratorSafe< Val >* >& vect = _list_->_safe_iterators_;

    for (auto i = vect.size() - 1; i >= 0; --i) {
      if (vect[i] == this) {
        vect.erase(vect.begin() + i);
        break;
      }
    }
  }

  // Copy operator
  template < typename Val >
  ListConstIteratorSafe< Val >&
     ListConstIteratorSafe< Val >::operator=(const ListConstIteratorSafe< Val >& src) {
    // avoid self assignment
    if (this != &src) {
      // for debugging purposes
      GUM_OP_CPY(ListConstIteratorSafe);

      // check if src and this belong to the same list. If this is not
      // the case, we shall remove this from its iterator's list and
      // put it into src's list one.
      if (_list_ && (src._list_ != _list_)) {
        _removeFromSafeList_();
        _list_ = nullptr;
      }

      // if necessary, put this into the same list of safe iterators as src
      if (src._list_ && (src._list_ != _list_)) {
        try {
          src._list_->_safe_iterators_.push_back(this);
        } catch (...) {
          _list_          = nullptr;
          _bucket_        = nullptr;
          _null_pointing_ = false;
          throw;
        }
      }

      _list_                = src._list_;
      _bucket_              = src._bucket_;
      _prev_current_bucket_ = src._prev_current_bucket_;
      _next_current_bucket_ = src._next_current_bucket_;
      _null_pointing_       = src._null_pointing_;
    }

    return *this;
  }

  // move operator
  template < typename Val >
  ListConstIteratorSafe< Val >&
     ListConstIteratorSafe< Val >::operator=(ListConstIteratorSafe< Val >&& src) {
    // avoid self assignment
    if (this != &src) {
      // for debugging purposes
      GUM_OP_MOV(ListConstIteratorSafe);

      // if the two iterators do not point to the same list, remove
      // the current iterator from its safe iterators list
      if ((_list_ != nullptr) && (src._list_ != _list_)) {
        _removeFromSafeList_();
        _list_ = nullptr;
      }

      // now if src points to a list, put this at its location
      if ((src._list_ != nullptr)) {
        std::vector< ListConstIteratorSafe< Val >* >& vect      = src._list_->_safe_iterators_;
        Idx                                           index_src = Size(vect.size()) - 1;

        for (;; --index_src) {
          if (vect[index_src] == &src) { break; }
        }

        if (_list_ == nullptr) {
          vect[index_src] = this;
        } else {
          vect.erase(vect.begin() + index_src);
        }
      }

      _list_                = src._list_;
      _bucket_              = src._bucket_;
      _prev_current_bucket_ = src._prev_current_bucket_;
      _next_current_bucket_ = src._next_current_bucket_;
      _null_pointing_       = src._null_pointing_;

      src._list_          = nullptr;
      src._bucket_        = nullptr;
      src._null_pointing_ = false;
    }

    return *this;
  }

  // Destructor
  template < typename Val >
  INLINE ListConstIteratorSafe< Val >::~ListConstIteratorSafe() {
    // for debugging purposes
    GUM_DESTRUCTOR(ListConstIteratorSafe);

    // remove the iterator src the table's iterator list
    if (_list_) _removeFromSafeList_();
  }

  // returns the bucket the iterator is pointing to
  template < typename Val >
  INLINE ListBucket< Val >* ListConstIteratorSafe< Val >::_getBucket_() const noexcept {
    return _bucket_;
  }

  // Makes the iterator point toward nothing
  template < typename Val >
  INLINE void ListConstIteratorSafe< Val >::clear() {
    // remove the iterator src the list's iterator list
    if (_list_) _removeFromSafeList_();

    // set its list as well as the element it points to to nullptr
    _list_          = nullptr;
    _bucket_        = nullptr;
    _null_pointing_ = false;
  }

  // positions the iterator to the end of the list
  template < typename Val >
  INLINE void ListConstIteratorSafe< Val >::setToEnd() {
    clear();
  }

  // returns a bool indicating whether the iterator points to the end of the
  // list
  template < typename Val >
  INLINE bool ListConstIteratorSafe< Val >::isEnd() const {
    return _null_pointing_
            ? (_next_current_bucket_ == nullptr) && (_prev_current_bucket_ == nullptr)
            : (_bucket_ == nullptr);
  }

  // makes the iterator point to the next element in the List
  template < typename Val >
  INLINE ListConstIteratorSafe< Val >& ListConstIteratorSafe< Val >::operator++() noexcept {
    // check if we are pointing to something that has been deleted
    if (_null_pointing_) {
      _null_pointing_ = false;

      // if we are pointing to an element of the chained list that has been
      // deleted
      // but that has a next element, just point on the latter
      if (_next_current_bucket_ != nullptr) {
        _bucket_ = _next_current_bucket_->_next_;
        return *this;
      }

      // here we were pointing on an extremity of the list (either end or rend)
      // if prev_current_bucket is not null, then we are at rend and doing
      // a ++ shall now point to the beginning of the list
      if (_prev_current_bucket_ != nullptr) {
        _bucket_ = _prev_current_bucket_;
        return *this;
      }

      // here, we are at the end of the chained list, hence we shall remain at
      // end
      _bucket_ = nullptr;
      return *this;
    } else {
      // if we are pointing to an element of the chained list, just
      // point on the next bucket in this list
      if (_bucket_ != nullptr) { _bucket_ = _bucket_->_next_; }

      return *this;
    }
  }

  // makes the iterator point to i elements before in the List
  template < typename Val >
  INLINE ListConstIteratorSafe< Val >& ListConstIteratorSafe< Val >::_opMinus_(Size i) noexcept {
    // check if we are pointing to something that has been deleted
    if (_null_pointing_) {
      _null_pointing_ = false;

      // if we are pointing to an element of the chained list that has been
      // deleted
      // but that has a preceding element, just point on the latter
      if (_prev_current_bucket_ != nullptr) {
        _bucket_ = _prev_current_bucket_->_prev_;
      } else {
        // here we were pointing on an extremity of the list (either end or
        // rend)
        // if next_current_bucket is not null, then we are at end and doing
        // a -- shall now point to the beginning of the list
        if (_next_current_bucket_ != nullptr) {
          _bucket_ = _next_current_bucket_;
        } else {
          // here, we are at the rend of the chained list, hence we shall remain
          // at rend
          _bucket_ = nullptr;
          return *this;
        }
      }
    } else {
      // if we are pointing to an element of the chained list, just
      // point on the preceding bucket in this list
      if (_bucket_ != nullptr) { _bucket_ = _bucket_->_prev_; }
    }

    for (--i; i && (_bucket_ != nullptr); --i, _bucket_ = _bucket_->_prev_) {}

    return *this;
  }

  // makes the iterator point to the next element in the List
  template < typename Val >
  INLINE ListConstIteratorSafe< Val >& ListConstIteratorSafe< Val >::_opPlus_(Size i) noexcept {
    // check if we are pointing to something that has been deleted
    if (_null_pointing_) {
      _null_pointing_ = false;

      // if we are pointing to an element of the chained list that has been
      // deleted
      // but that has a next element, just point on the latter
      if (_next_current_bucket_ != nullptr) {
        _bucket_ = _next_current_bucket_->_next_;
      } else {
        // here we were pointing on an extremity of the list (either end or
        // rend)
        // if prev_current_bucket is not null, then we are at rend and doing
        // a ++ shall now point to the beginning of the list
        if (_prev_current_bucket_ != nullptr) {
          _bucket_ = _prev_current_bucket_;
        } else {
          // here, we are at the end of the chained list, hence we shall
          // remain at end
          _bucket_ = nullptr;
          return *this;
        }
      }
    } else {
      // if we are pointing to an element of the chained list, just
      // point on the next bucket in this list
      if (_bucket_ != nullptr) { _bucket_ = _bucket_->_next_; }
    }

    for (--i; i && (_bucket_ != nullptr); --i, _bucket_ = _bucket_->_next_) {}

    return *this;
  }

  // makes the iterator point to the next element in the List
  template < typename Val >
  INLINE ListConstIteratorSafe< Val >& ListConstIteratorSafe< Val >::operator+=(
     typename ListConstIteratorSafe< Val >::difference_type i) noexcept {
    if (!i) return *this;

    if (i < 0)
      return _opMinus_(-i);
    else
      return _opPlus_(i);
  }

  // makes the iterator point to the preceding element in the List
  template < typename Val >
  INLINE ListConstIteratorSafe< Val >& ListConstIteratorSafe< Val >::operator--() noexcept {
    // check if we are pointing to something that has been deleted
    if (_null_pointing_) {
      _null_pointing_ = false;

      // if we are pointing to an element of the chained list that has been
      // deleted
      // but that has a preceding element, just point on the latter
      if (_prev_current_bucket_ != nullptr) {
        _bucket_ = _prev_current_bucket_->_prev_;
        return *this;
      }

      // here we were pointing on an extremity of the list (either end or rend)
      // if next_current_bucket is not null, then we are at end and doing
      // a -- shall now point to the beginning of the list
      if (_next_current_bucket_ != nullptr) {
        _bucket_ = _next_current_bucket_;
        return *this;
      }

      // here, we are at the rend of the chained list, hence we shall remain
      // at rend
      _bucket_ = nullptr;
      return *this;
    } else {
      // if we are pointing to an element of the chained list, just
      // point on the preceding bucket in this list
      if (_bucket_ != nullptr) { _bucket_ = _bucket_->_prev_; }

      return *this;
    }
  }

  // makes the iterator point to i elements before in the List
  template < typename Val >
  INLINE ListConstIteratorSafe< Val >& ListConstIteratorSafe< Val >::operator-=(
     typename ListConstIteratorSafe< Val >::difference_type i) noexcept {
    if (!i) return *this;

    if (i < 0)
      return _opPlus_(-i);
    else
      return _opMinus_(i);
  }

  // returns a new iterator
  template < typename Val >
  INLINE ListConstIteratorSafe< Val > ListConstIteratorSafe< Val >::operator+(
     typename ListConstIteratorSafe< Val >::difference_type i) noexcept {
    return ListConstIteratorSafe< Val >(*this) += i;
  }

  // returns a new iterator
  template < typename Val >
  INLINE ListConstIteratorSafe< Val > ListConstIteratorSafe< Val >::operator-(
     typename ListConstIteratorSafe< Val >::difference_type i) noexcept {
    return ListConstIteratorSafe< Val >(*this) -= i;
  }

  // checks whether two iterators point toward different elements
  template < typename Val >
  INLINE bool
     ListConstIteratorSafe< Val >::operator!=(const ListConstIteratorSafe< Val >& src) const {
    return _null_pointing_ ? (_next_current_bucket_ != src._next_current_bucket_)
                                || (_prev_current_bucket_ != src._prev_current_bucket_)
                           : (_bucket_ != src._bucket_);
  }

  // checks whether two iterators point toward the same elements.
  template < typename Val >
  INLINE bool
     ListConstIteratorSafe< Val >::operator==(const ListConstIteratorSafe< Val >& src) const {
    return _null_pointing_ ? (_next_current_bucket_ == src._next_current_bucket_)
                                && (_prev_current_bucket_ == src._prev_current_bucket_)
                           : (_bucket_ == src._bucket_);
  }

  // dereferences the value pointed to by the iterator
  template < typename Val >
  INLINE const Val* ListConstIteratorSafe< Val >::operator->() const {
    if (_bucket_ != nullptr)
      return &(_bucket_->_val_);
    else {
      GUM_ERROR(UndefinedIteratorValue, "Accessing a NULL object")
    }
  }

  // gives access to the content of the iterator
  template < typename Val >
  INLINE const Val& ListConstIteratorSafe< Val >::operator*() const {
    if (_bucket_ != nullptr)
      return _bucket_->_val_;
    else {
      GUM_ERROR(UndefinedIteratorValue, "Accessing a NULL object")
    }
  }

  // for STL compliance, a distance operator
  template < typename Val >
  INLINE typename ListConstIteratorSafe< Val >::difference_type
     operator-(const ListConstIteratorSafe< Val >& iter1,
               const ListConstIteratorSafe< Val >& iter2) {
    typename ListConstIteratorSafe< Val >::difference_type res = 0;
    ListConstIteratorSafe< Val >                           iter3{iter2};

    for (; iter1 != iter3; ++iter3, ++res) {}

    return res;
  }

  // ===========================================================================
  // ===========================================================================
  // ===                     LIST ITERATOR IMPLEMENTATION                    ===
  // ===========================================================================
  // ===========================================================================

  // basic constructor
  template < typename Val >
  INLINE ListIteratorSafe< Val >::ListIteratorSafe() noexcept : ListConstIteratorSafe< Val >() {
    GUM_CONSTRUCTOR(ListIteratorSafe);
  }

  // constructor for a begin
  template < typename Val >
  template < typename Alloc >
  INLINE ListIteratorSafe< Val >::ListIteratorSafe(const List< Val, Alloc >& theList) :
      ListConstIteratorSafe< Val >(theList) {
    GUM_CONSTRUCTOR(ListIteratorSafe);
  }

  // copy constructor
  template < typename Val >
  INLINE ListIteratorSafe< Val >::ListIteratorSafe(const ListIteratorSafe< Val >& src) :
      ListConstIteratorSafe< Val >(src) {
    GUM_CONS_CPY(ListIteratorSafe);
  }

  // Constructor for an iterator pointing to the \e ind_eltth element of a
  // List.
  template < typename Val >
  template < typename Alloc >
  INLINE ListIteratorSafe< Val >::ListIteratorSafe(const List< Val, Alloc >& theList,
                                                   Size                      ind_elt) :
      ListConstIteratorSafe< Val >(theList, ind_elt) {
    GUM_CONSTRUCTOR(ListIteratorSafe);
  }

  // move constructor
  template < typename Val >
  INLINE ListIteratorSafe< Val >::ListIteratorSafe(ListIteratorSafe< Val >&& src) :
      ListConstIteratorSafe< Val >(std::move(src)) {
    GUM_CONS_MOV(ListIteratorSafe);
  }

  // Copy operator
  template < typename Val >
  INLINE ListIteratorSafe< Val >&
     ListIteratorSafe< Val >::operator=(const ListIteratorSafe< Val >& src) {
    // for debugging purposes
    GUM_OP_CPY(ListIteratorSafe);
    ListConstIteratorSafe< Val >::operator=(src);
    return *this;
  }

  // move operator
  template < typename Val >
  INLINE ListIteratorSafe< Val >&
     ListIteratorSafe< Val >::operator=(ListIteratorSafe< Val >&& src) {
    // for debugging purposes
    GUM_OP_MOV(ListIteratorSafe);
    ListConstIteratorSafe< Val >::operator=(std::move(src));
    return *this;
  }

  // Destructor
  template < typename Val >
  INLINE ListIteratorSafe< Val >::~ListIteratorSafe() {
    GUM_DESTRUCTOR(ListIteratorSafe);
  }

  // makes the iterator point to the next element in the List
  template < typename Val >
  INLINE ListIteratorSafe< Val >& ListIteratorSafe< Val >::operator++() noexcept {
    ListConstIteratorSafe< Val >::operator++();
    return *this;
  }

  // makes the iterator point to the next element in the List
  template < typename Val >
  INLINE ListIteratorSafe< Val >& ListIteratorSafe< Val >::operator+=(
     typename ListIteratorSafe< Val >::difference_type i) noexcept {
    ListConstIteratorSafe< Val >::operator+=(i);
    return *this;
  }

  // makes the iterator point to the preceding element in the List
  template < typename Val >
  INLINE ListIteratorSafe< Val >& ListIteratorSafe< Val >::operator--() noexcept {
    ListConstIteratorSafe< Val >::operator--();
    return *this;
  }

  // makes the iterator point to the preceding element in the List
  template < typename Val >
  INLINE ListIteratorSafe< Val >& ListIteratorSafe< Val >::operator-=(
     typename ListIteratorSafe< Val >::difference_type i) noexcept {
    ListConstIteratorSafe< Val >::operator-=(i);
    return *this;
  }

  // returns a new iterator
  template < typename Val >
  INLINE ListIteratorSafe< Val > ListIteratorSafe< Val >::operator+(
     typename ListIteratorSafe< Val >::difference_type i) noexcept {
    return ListIteratorSafe< Val >(*this) += i;
  }

  // returns a new iterator
  template < typename Val >
  INLINE ListIteratorSafe< Val > ListIteratorSafe< Val >::operator-(
     typename ListIteratorSafe< Val >::difference_type i) noexcept {
    return ListIteratorSafe< Val >(*this) -= i;
  }

  // dereferences the value pointed to by the iterator
  template < typename Val >
  INLINE Val* ListIteratorSafe< Val >::operator->() {
    return const_cast< Val* >(ListConstIteratorSafe< Val >::operator->());
  }

  // gives access to the content of the iterator
  template < typename Val >
  INLINE Val& ListIteratorSafe< Val >::operator*() {
    return const_cast< Val& >(ListConstIteratorSafe< Val >::operator*());
  }

  // ===========================================================================
  // ===========================================================================
  // ===                          LIST IMPLEMENTATION                        ===
  // ===========================================================================
  // ===========================================================================

  // a function used to perform copies of elements of Lists
  template < typename Val, typename Alloc >
  template < typename OtherAlloc >
  void List< Val, Alloc >::_copy_elements_(const List< Val, OtherAlloc >& src) {
    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 = _alloc_bucket_.allocate(1);

        try {
          _alloc_bucket_.construct(new_elt, *ptr);
        } catch (...) {
          _alloc_bucket_.deallocate(new_elt, 1);
          throw;
        }

        // 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_;
        _alloc_bucket_.destroy(_deb_list_);
        _alloc_bucket_.deallocate(_deb_list_, 1);
      }

      _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_;
  }

  // deletes all the elements of a chained list.
  template < typename Val, typename Alloc >
  void List< Val, Alloc >::clear() {
    // 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_;
      _alloc_bucket_.destroy(ptr);
      _alloc_bucket_.deallocate(ptr, 1);
    }

    _nb_elements_ = 0;
    _deb_list_    = nullptr;
    _end_list_    = nullptr;
  }

  // A basic constructor that creates an empty list
  template < typename Val, typename Alloc >
  INLINE List< Val, Alloc >::List() {
    // for debugging purposes
    GUM_CONSTRUCTOR(List);

    // reserve space for only the default number of iterators
    _safe_iterators_.reserve(GUM_DEFAULT_ITERATOR_NUMBER);
  }

  // Copy constructor
  template < typename Val, typename Alloc >
  INLINE List< Val, Alloc >::List(const List< Val, Alloc >& src) {
    // 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);
  }

  // generalized copy constructor
  template < typename Val, typename Alloc >
  template < typename OtherAlloc >
  INLINE List< Val, Alloc >::List(const List< Val, OtherAlloc >& src) {
    // 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);
  }

  // move constructor
  template < typename Val, typename Alloc >
  INLINE List< Val, Alloc >::List(List< Val, Alloc >&& src) :
      _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_)}, _alloc_bucket_{
                                                            std::move(src._alloc_bucket_)} {
    // for debugging purposes
    GUM_CONS_MOV(List);

    src._deb_list_    = nullptr;
    src._end_list_    = nullptr;
    src._nb_elements_ = 0;
    src._safe_iterators_.clear();
  }

  // initializer_list constructor
  template < typename Val, typename Alloc >
  INLINE List< Val, Alloc >::List(std::initializer_list< Val > list) {
    // 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);
  }

  // Destructor
  template < typename Val, typename Alloc >
  INLINE List< Val, Alloc >::~List() {
    // 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();
  }

  // Copy operator. The List iterator's list is not shared with that of \e src.
  template < typename Val, typename Alloc >
  INLINE List< Val, Alloc >& List< Val, Alloc >::operator=(const List< Val, Alloc >& src) {
    // 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;
  }

  // Generalized copy operator.
  template < typename Val, typename Alloc >
  template < typename OtherAlloc >
  INLINE List< Val, Alloc >& List< Val, Alloc >::operator=(const List< Val, OtherAlloc >& src) {
    // avoid self assignment
    if (this != reinterpret_cast< List< Val, Alloc >* >(&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;
  }

  // move operator
  template < typename Val, typename Alloc >
  INLINE List< Val, Alloc >& List< Val, Alloc >::operator=(List< Val, Alloc >&& src) {
    // 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_);
      _alloc_bucket_   = std::move(src._alloc_bucket_);

      src._deb_list_    = nullptr;
      src._end_list_    = nullptr;
      src._nb_elements_ = 0;
      src._safe_iterators_.clear();
    }

    return *this;
  }

  // the iterator pointing to the end of the List
  template < typename Val, typename Alloc >
  INLINE const ListConstIteratorSafe< Val >& List< Val, Alloc >::cendSafe() const noexcept {
    return *(reinterpret_cast< const ListConstIteratorSafe< Val >* >(_list_end_safe_));
  }

  // the iterator pointing to the end of the List
  template < typename Val, typename Alloc >
  INLINE const ListIteratorSafe< Val >& List< Val, Alloc >::endSafe() noexcept {
    return *(reinterpret_cast< const ListIteratorSafe< Val >* >(_list_end_safe_));
  }

  // the iterator pointing to the end of the List
  template < typename Val, typename Alloc >
  INLINE const ListConstIterator< Val >& List< Val, Alloc >::cend() const noexcept {
    return *(reinterpret_cast< const ListConstIterator< Val >* >(_list_end_));
  }

  // the iterator pointing to the end of the List
  template < typename Val, typename Alloc >
  INLINE const ListIterator< Val >& List< Val, Alloc >::end() noexcept {
    return *(reinterpret_cast< const ListIterator< Val >* >(_list_end_));
  }

  // the iterator pointing to the end of the List
  template < typename Val, typename Alloc >
  INLINE const ListConstIterator< Val >& List< Val, Alloc >::end() const noexcept {
    return *(reinterpret_cast< const ListConstIterator< Val >* >(_list_end_));
  }

  // the iterator pointing to the rend (just before the beginning) of the List
  template < typename Val, typename Alloc >
  INLINE const ListConstIteratorSafe< Val >& List< Val, Alloc >::crendSafe() const noexcept {
    return *(reinterpret_cast< const ListConstIteratorSafe< Val >* >(_list_end_safe_));
  }

  // the iterator pointing to the rend (just before the beginning) of the List
  template < typename Val, typename Alloc >
  INLINE const ListIteratorSafe< Val >& List< Val, Alloc >::rendSafe() noexcept {
    return *(reinterpret_cast< const ListIteratorSafe< Val >* >(_list_end_safe_));
  }

  // the iterator pointing to the rend (just before the beginning) of the List
  template < typename Val, typename Alloc >
  INLINE const ListConstIterator< Val >& List< Val, Alloc >::crend() const noexcept {
    return *(reinterpret_cast< const ListConstIterator< Val >* >(_list_end_));
  }

  // the iterator pointing to the rend (just before the beginning) of the List
  template < typename Val, typename Alloc >
  INLINE const ListIterator< Val >& List< Val, Alloc >::rend() noexcept {
    return *(reinterpret_cast< const ListIterator< Val >* >(_list_end_));
  }

  // the iterator pointing to the rend (just before the beginning) of the List
  template < typename Val, typename Alloc >
  INLINE const ListConstIterator< Val >& List< Val, Alloc >::rend() const noexcept {
    return *(reinterpret_cast< const ListConstIterator< Val >* >(_list_end_));
  }

  // the iterator pointing to the beginning of the List
  template < typename Val, typename Alloc >
  INLINE ListConstIteratorSafe< Val > List< Val, Alloc >::cbeginSafe() const {
    return ListConstIteratorSafe< Val >{*this};
  }

  // the iterator pointing to the beginning of the List
  template < typename Val, typename Alloc >
  INLINE ListIteratorSafe< Val > List< Val, Alloc >::beginSafe() {
    return ListIteratorSafe< Val >{*this};
  }

  // the iterator pointing to the beginning of the List
  template < typename Val, typename Alloc >
  INLINE ListConstIterator< Val > List< Val, Alloc >::cbegin() const {
    return ListConstIterator< Val >{*this};
  }

  // the iterator pointing to the beginning of the List
  template < typename Val, typename Alloc >
  INLINE ListIterator< Val > List< Val, Alloc >::begin() {
    return ListIterator< Val >{*this};
  }

  // the iterator pointing to the beginning of the List
  template < typename Val, typename Alloc >
  INLINE ListConstIterator< Val > List< Val, Alloc >::begin() const {
    return ListConstIterator< Val >{*this};
  }

  // the iterator pointing to the rbegin (the last element) of the List
  template < typename Val, typename Alloc >
  INLINE ListConstIteratorSafe< Val > List< Val, Alloc >::crbeginSafe() const {
    if (_nb_elements_)
      return ListConstIteratorSafe< Val >{*this, _nb_elements_ - 1};
    else
      return ListConstIteratorSafe< Val >{};
  }

  // the iterator pointing to the rbegin (the last element) of the List
  template < typename Val, typename Alloc >
  INLINE ListIteratorSafe< Val > List< Val, Alloc >::rbeginSafe() {
    if (_nb_elements_)
      return ListIteratorSafe< Val >{*this, _nb_elements_ - 1};
    else
      return ListIteratorSafe< Val >{};
  }

  // the iterator pointing to the rbegin (the last element) of the List
  template < typename Val, typename Alloc >
  INLINE ListConstIterator< Val > List< Val, Alloc >::crbegin() const {
    if (_nb_elements_)
      return ListConstIterator< Val >{*this, _nb_elements_ - 1};
    else
      return ListConstIterator< Val >{};
  }

  // the iterator pointing to the rbegin (the last element) of the List
  template < typename Val, typename Alloc >
  INLINE ListIterator< Val > List< Val, Alloc >::rbegin() {
    if (_nb_elements_)
      return ListIterator< Val >{*this, _nb_elements_ - 1};
    else
      return ListIterator< Val >{};
  }

  // the iterator pointing to the rbegin (the last element) of the List
  template < typename Val, typename Alloc >
  INLINE ListConstIterator< Val > List< Val, Alloc >::rbegin() const {
    if (_nb_elements_)
      return ListConstIterator< Val >{*this, _nb_elements_ - 1};
    else
      return ListConstIterator< Val >{};
  }

  // create a new bucket with a given value
  template < typename Val, typename Alloc >
  INLINE ListBucket< Val >* List< Val, Alloc >::_createBucket_(const Val& val) const {
    // create a new bucket (catch allocation and construction exceptions)
    ListBucket< Val >* new_elt = _alloc_bucket_.allocate(1);

    try {
      _alloc_bucket_.construct(new_elt, val);
    } catch (...) {
      _alloc_bucket_.deallocate(new_elt, 1);
      throw;
    }

    return new_elt;
  }

  // create a new bucket with a given value
  template < typename Val, typename Alloc >
  INLINE ListBucket< Val >* List< Val, Alloc >::_createBucket_(Val&& val) const {
    // create a new bucket (catch allocation and construction exceptions)
    ListBucket< Val >* new_elt = _alloc_bucket_.allocate(1);

    try {
      _alloc_bucket_.construct(new_elt, std::move(val));
    } catch (...) {
      _alloc_bucket_.deallocate(new_elt, 1);
      throw;
    }

    return new_elt;
  }

  // create an emplace bucket
  template < typename Val, typename Alloc >
  template < typename... Args >
  INLINE ListBucket< Val >* List< Val, Alloc >::_createEmplaceBucket_(Args&&... args) const {
    // create a new bucket (catch allocation and construction exceptions)
    ListBucket< Val >* new_elt = _alloc_bucket_.allocate(1);

    try {
      _alloc_bucket_.construct(new_elt,
                               ListBucket< Val >::Emplace::EMPLACE,
                               std::forward< Args >(args)...);
    } catch (...) {
      _alloc_bucket_.deallocate(new_elt, 1);
      throw;
    }

    return new_elt;
  }

  // insert a bucket at the front of the list
  template < typename Val, typename Alloc >
  INLINE Val& List< Val, Alloc >::_pushFront_(ListBucket< Val >* new_elt) {
    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_;
  }

  // insert a bucket at the end of the list
  template < typename Val, typename Alloc >
  INLINE Val& List< Val, Alloc >::_pushBack_(ListBucket< Val >* new_elt) {
    // 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_;
  }

  // Insertion of a new element (a copy) at the beginning of the chained list.
  template < typename Val, typename Alloc >
  INLINE Val& List< Val, Alloc >::pushFront(const Val& val) {
    return _pushFront_(_createBucket_(val));
  }

  // Insertion of a new element (a copy) at the beginning of the chained list.
  template < typename Val, typename Alloc >
  INLINE Val& List< Val, Alloc >::pushFront(Val&& val) {
    return _pushFront_(_createBucket_(std::move(val)));
  }

  // an alias for pushFront used for STL compliance
  template < typename Val, typename Alloc >
  template < typename... Args >
  INLINE Val& List< Val, Alloc >::push_front(Args&&... args) {
    return pushFront(std::forward< Args >(args)...);
  }

  // emplace elements at the beginning of the chained list
  template < typename Val, typename Alloc >
  template < typename... Args >
  INLINE Val& List< Val, Alloc >::emplaceFront(Args&&... args) {
    return _pushFront_(_createEmplaceBucket_(std::forward< Args >(args)...));
  }

  // Insertion of a new element (a copy) at the end of the chained list.
  template < typename Val, typename Alloc >
  INLINE Val& List< Val, Alloc >::pushBack(const Val& val) {
    return _pushBack_(_createBucket_(val));
  }

  // pushBack for rvalues
  template < typename Val, typename Alloc >
  INLINE Val& List< Val, Alloc >::pushBack(Val&& val) {
    return _pushBack_(_createBucket_(std::move(val)));
  }

  // an alias for pushBack used for STL compliance
  template < typename Val, typename Alloc >
  template < typename... Args >
  INLINE Val& List< Val, Alloc >::push_back(Args&&... args) {
    return pushBack(std::forward< Args >(args)...);
  }

  // emplace elements at the end of the chained list
  template < typename Val, typename Alloc >
  template < typename... Args >
  INLINE Val& List< Val, Alloc >::emplaceBack(Args&&... args) {
    return _pushBack_(_createEmplaceBucket_(std::forward< Args >(args)...));
  }

  // Insertion of a new element at the end of the chained list (alias of
  // pushBack)
  template < typename Val, typename Alloc >
  INLINE Val& List< Val, Alloc >::insert(const Val& val) {
    return pushBack(val);
  }

  // insert for rvalues
  template < typename Val, typename Alloc >
  INLINE Val& List< Val, Alloc >::insert(Val&& val) {
    return pushBack(std::move(val));
  }

  // returns the bucket corresponding to the ith position
  template < typename Val, typename Alloc >
  INLINE ListBucket< Val >* List< Val, Alloc >::_getIthBucket_(Size i) const noexcept {
    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;
  }

  // insert a new bucket before another one
  template < typename Val, typename Alloc >
  INLINE Val& List< Val, Alloc >::_insertBefore_(ListBucket< Val >* new_elt,
                                                 ListBucket< Val >* current_elt) {
    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_;
  }

  // insert a new bucket after another one
  template < typename Val, typename Alloc >
  INLINE Val& List< Val, Alloc >::_insertAfter_(ListBucket< Val >* new_elt,
                                                ListBucket< Val >* current_elt) {
    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_;
  }

  // inserts a new element at the ith pos of the chained list
  template < typename Val, typename Alloc >
  INLINE Val& List< Val, Alloc >::insert(Size pos, const Val& val) {
    // 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));
  }

  // insert an rvalue at the ith pos of the chained list
  template < typename Val, typename Alloc >
  INLINE Val& List< Val, Alloc >::insert(Size pos, Val&& val) {
    // 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));
  }

  // inserts a new bucket before or after the location pointed to by an
  // iterator
  template < typename Val, typename Alloc >
  INLINE Val& List< Val, Alloc >::_insert_(const const_iterator_safe& iter,
                                           ListBucket< Val >*         new_elt,
                                           location                   place) {
    // 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")
      }
    }
  }

  // inserts a new bucket before or after the location pointed to by an
  // iterator
  template < typename Val, typename Alloc >
  INLINE Val& List< Val, Alloc >::_insert_(const const_iterator& iter,
                                           ListBucket< Val >*    new_elt,
                                           location              place) {
    // 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")
      }
    }
  }

  // inserts a new element before or after the location pointed to by an
  // iterator
  template < typename Val, typename Alloc >
  INLINE Val&
     List< Val, Alloc >::insert(const const_iterator_safe& iter, const Val& val, location place) {
    // 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);
  }

  // inserts a new element before or after the location pointed to by an
  // iterator
  template < typename Val, typename Alloc >
  INLINE Val&
         List< Val, Alloc >::insert(const const_iterator_safe& iter, Val&& val, location place) {
    // 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);
  }

  // inserts a new element before or after the location pointed to by an
  // iterator
  template < typename Val, typename Alloc >
  INLINE Val&
         List< Val, Alloc >::insert(const const_iterator& iter, const Val& val, location place) {
    return _insert_(iter, _createBucket_(val), place);
  }

  // inserts a new element before or after the location pointed to by an
  // iterator
  template < typename Val, typename Alloc >
  INLINE Val& List< Val, Alloc >::insert(const const_iterator& iter, Val&& val, location place) {
    return _insert_(iter, _createBucket_(std::move(val)), place);
  }

  // emplace a new element before a given iterator
  template < typename Val, typename Alloc >
  template < typename... Args >
  INLINE Val& List< Val, Alloc >::emplace(const const_iterator& iter, Args&&... args) {
    return _insert_(iter, _createEmplaceBucket_(std::forward< Args >(args)...), location::BEFORE);
  }

  // emplace a new element before a given iterator
  template < typename Val, typename Alloc >
  template < typename... Args >
  INLINE Val& List< Val, Alloc >::emplace(const const_iterator_safe& iter, Args&&... args) {
    return _insert_(iter, _createEmplaceBucket_(std::forward< Args >(args)...), location::BEFORE);
  }

  // returns a reference to first element of a list
  template < typename Val, typename Alloc >
  INLINE Val& List< Val, Alloc >::front() const {
    if (_nb_elements_ == Size(0)) { GUM_ERROR(NotFound, "not enough elements in the chained list") }

    return _deb_list_->_val_;
  }

  // returns a reference to last element of a list
  template < typename Val, typename Alloc >
  INLINE Val& List< Val, Alloc >::back() const {
    if (_nb_elements_ == Size(0)) { GUM_ERROR(NotFound, "not enough elements in the chained list") }

    return _end_list_->_val_;
  }

  // returns the number of elements in the list.
  template < typename Val, typename Alloc >
  INLINE Size List< Val, Alloc >::size() const noexcept {
    return _nb_elements_;
  }

  // checks whether there exists a given element in the list.
  template < typename Val, typename Alloc >
  INLINE bool List< Val, Alloc >::exists(const Val& val) const {
    for (ListBucket< Val >* ptr = _deb_list_; ptr != nullptr; ptr = ptr->_next_)
      if (ptr->_val_ == val) return true;

    return false;
  }

  // suppresses a given bucket from a chained list.
  template < typename Val, typename Alloc >
  INLINE void List< Val, Alloc >::_erase_(ListBucket< Val >* bucket) {
    // 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
      _alloc_bucket_.destroy(bucket);
      _alloc_bucket_.deallocate(bucket, 1);

      --_nb_elements_;
    }
  }

  // erases the ith element of the List (the first one is in position 0)
  template < typename Val, typename Alloc >
  INLINE void List< Val, Alloc >::erase(Size i) {
    if (i >= _nb_elements_) return;

    // erase the ith bucket
    _erase_(_getIthBucket_(i));
  }

  // erases the element of the List pointed to by the iterator
  template < typename Val, typename Alloc >
  INLINE void List< Val, Alloc >::erase(const iterator_safe& iter) {
    _erase_(iter._getBucket_());
  }

  // erases the element of the List pointed to by the iterator
  template < typename Val, typename Alloc >
  INLINE void List< Val, Alloc >::erase(const const_iterator_safe& iter) {
    _erase_(iter._getBucket_());
  }

  // returns the bucket corresponding to a given value.
  template < typename Val, typename Alloc >
  INLINE ListBucket< Val >* List< Val, Alloc >::_getBucket_(const Val& val) const noexcept {
    for (ListBucket< Val >* ptr = _deb_list_; ptr != nullptr; ptr = ptr->_next_)
      if (ptr->_val_ == val) return ptr;

    return nullptr;
  }

  // erases the first element encountered with a given value
  template < typename Val, typename Alloc >
  INLINE void List< Val, Alloc >::eraseByVal(const Val& val) {
    _erase_(_getBucket_(val));
  }

  // erases all the elements encountered with a given value
  template < typename Val, typename Alloc >
  INLINE void List< Val, Alloc >::eraseAllVal(const Val& val) {
    for (ListBucket< Val >*iter = _deb_list_, *next_bucket = nullptr; iter != nullptr;
         iter = next_bucket) {
      next_bucket = iter->_next_;

      if (val == iter->_val_) _erase_(iter);
    }
  }

  // removes the last element of a List
  template < typename Val, typename Alloc >
  INLINE void List< Val, Alloc >::popBack() {
    _erase_(_end_list_);
  }

  // removes the first element of a List
  template < typename Val, typename Alloc >
  INLINE void List< Val, Alloc >::popFront() {
    _erase_(_deb_list_);
  }

  // returns a boolean indicating whether the chained list is empty
  template < typename Val, typename Alloc >
  INLINE bool List< Val, Alloc >::empty() const noexcept {
    return (_nb_elements_ == Size(0));
  }

  // displays the content of a chained list
  template < typename Val, typename Alloc >
  std::string List< Val, Alloc >::toString() const {
    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();
  }

  // creates a list of mountains src a list of val
  template < typename Val, typename Alloc >
  template < typename Mount, typename OtherAlloc >
  List< Mount, OtherAlloc > List< Val, Alloc >::map(Mount (*f)(Val)) const {
    // create a new empty list
    List< Mount, OtherAlloc > list;

    // fill the new list
    for (const_iterator iter = begin(); iter != end(); ++iter) {
      list.pushBack(f(*iter));
    }

    return list;
  }

  // creates a list of mountains src a list of val
  template < typename Val, typename Alloc >
  template < typename Mount, typename OtherAlloc >
  List< Mount, OtherAlloc > List< Val, Alloc >::map(Mount (*f)(Val&)) const {
    // create a new empty list
    List< Mount, OtherAlloc > list;

    // fill the new list
    for (const_iterator iter = begin(); iter != end(); ++iter) {
      list.pushBack(f(*iter));
    }

    return list;
  }

  // creates a list of mountains src a list of val
  template < typename Val, typename Alloc >
  template < typename Mount, typename OtherAlloc >
  List< Mount, OtherAlloc > List< Val, Alloc >::map(Mount (*f)(const Val&)) const {
    // create a new empty list
    List< Mount, OtherAlloc > list;

    // fill the new list
    for (const_iterator iter = begin(); iter != end(); ++iter) {
      list.pushBack(f(*iter));
    }

    return list;
  }

  // creates a list of mountains with a given value src a list of val
  template < typename Val, typename Alloc >
  template < typename Mount, typename OtherAlloc >
  List< Mount, OtherAlloc > List< Val, Alloc >::map(const Mount& mount) const {
    // create a new empty list
    List< Mount, OtherAlloc > list;

    // fill the new list
    for (Size i = Size(0); i < _nb_elements_; ++i)
      list.pushBack(mount);

    return list;
  }

  // creates and insert a new element at the end of the list (alias of
  // pushBack).
  template < typename Val, typename Alloc >
  INLINE Val& List< Val, Alloc >::operator+=(const Val& val) {
    return pushBack(val);
  }

  // creates and insert a new element at the end of the list (alias of
  // pushBack).
  template < typename Val, typename Alloc >
  INLINE Val& List< Val, Alloc >::operator+=(Val&& val) {
    return pushBack(std::move(val));
  }

  // checks whether two lists are identical (same elements in the same order)
  template < typename Val, typename Alloc >
  template < typename OtherAlloc >
  INLINE bool List< Val, Alloc >::operator==(const List< Val, OtherAlloc >& src) const {
    // 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;
  }

  // checks whether two lists are different (different elements or orders)
  template < typename Val, typename Alloc >
  template < typename OtherAlloc >
  INLINE bool List< Val, Alloc >::operator!=(const List< Val, OtherAlloc >& src) const {
    return !operator==(src);
  }

  // returns the ith element in the current chained list.
  template < typename Val, typename Alloc >
  INLINE Val& List< Val, Alloc >::operator[](const Size i) {
    // 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);
  }

  // returns the ith element in the current chained list.
  template < typename Val, typename Alloc >
  INLINE const Val& List< Val, Alloc >::operator[](const Size i) const {
    // 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);
  }

  // replace the current list with another one
  template < typename Val, typename Alloc >
  INLINE void List< Val, Alloc >::swap(List& other_list) {
    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_);
    std::swap(_alloc_bucket_, other_list._alloc_bucket_);
  }

  // A \c << operator for List
  template < typename Val >
  std::ostream& operator<<(std::ostream& stream, const List< Val >& list) {
    stream << list.toString();
    return stream;
  }

} /* namespace gum */