list.h

Go to the documentation of this file.

/****************************************************************************
 *   This file is part of the aGrUM/pyAgrum library.                        *
 *                                                                          *
 *   Copyright (c) 2005-2025 by                                             *
 *       - Pierre-Henri WUILLEMIN(_at_LIP6)                                 *
 *       - Christophe GONZALES(_at_AMU)                                     *
 *                                                                          *
 *   The aGrUM/pyAgrum library is free software; you can redistribute it    *
 *   and/or modify it under the terms of either :                           *
 *                                                                          *
 *    - 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,                              *
 *    - the MIT license (MIT),                                              *
 *    - or both in dual license, as here.                                   *
 *                                                                          *
 *   (see https://agrum.gitlab.io/articles/dual-licenses-lgplv3mit.html)    *
 *                                                                          *
 *   This aGrUM/pyAgrum library is distributed in the hope that it will be  *
 *   useful, but WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,          *
 *   INCLUDING BUT NOT LIMITED TO THE WARRANTIES MERCHANTABILITY or FITNESS *
 *   FOR A PARTICULAR PURPOSE  AND NONINFRINGEMENT. IN NO EVENT SHALL THE   *
 *   AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER *
 *   LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,        *
 *   ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR  *
 *   OTHER DEALINGS IN THE SOFTWARE.                                        *
 *                                                                          *
 *   See LICENCES for more details.                                         *
 *                                                                          *
 *   SPDX-FileCopyrightText: Copyright 2005-2025                            *
 *       - Pierre-Henri WUILLEMIN(_at_LIP6)                                 *
 *       - Christophe GONZALES(_at_AMU)                                     *
 *   SPDX-License-Identifier: LGPL-3.0-or-later OR MIT                      *
 *                                                                          *
 *   Contact  : info_at_agrum_dot_org                                       *
 *   homepage : http://agrum.gitlab.io                                      *
 *   gitlab   : https://gitlab.com/agrumery/agrum                           *
 *                                                                          *
 ****************************************************************************/
 

#ifndef GUM_LIST_H
#define GUM_LIST_H
 
#include <cstddef>
#include <iostream>
#include <sstream>
#include <vector>
 
#include <agrum/agrum.h>
 
#include <agrum/base/core/refPtr.h>
#include <agrum/base/core/staticInitializer.h>
 
#include <initializer_list>
 
#define GUM_DEFAULT_ITERATOR_NUMBER 4
 
namespace gum {
 
  // ==============================================================================
  // templates provided by this header
  // ==============================================================================
 
#ifndef DOXYGEN_SHOULD_SKIP_THIS
 
  template < typename Val >
  class ListBucket;
  template < typename Val >
  class ListIterator;
  template < typename Val >
  class ListConstIterator;
  template < typename Val >
  class ListIteratorSafe;
  template < typename Val >
  class ListConstIteratorSafe;
  template < typename Val >
  class List;
 
#endif         // DOXYGEN_SHOULD_SKIP_THIS
 
#ifndef SWIG   // SWIG cannot read these lines
  template < typename Val >
  std::ostream& operator<<(std::ostream& stream, const List< Val >& list);
#endif   // SWIG
 
 
  // ===========================================================================
  // ===             BUCKETS: SINGLE ELEMENTS OF A CHAINED LIST              ===
  // ===========================================================================

  template < typename Val >
  class ListBucket {
    private:
    enum class Emplace { EMPLACE };
 
    public:
    // ============================================================================
    // ============================================================================

    ListBucket() = delete;

    explicit ListBucket(const Val& v);

    explicit ListBucket(Val&& v) noexcept;

    template < typename... Args >
    explicit ListBucket(Emplace, Args&&... args);

    ListBucket(const ListBucket< Val >& src);

    ListBucket(ListBucket< Val >&& src) = delete;

    ~ListBucket();

    // ============================================================================
    // ============================================================================

    ListBucket< Val >& operator=(const ListBucket< Val >& src);

    ListBucket< Val >& operator=(ListBucket< Val >&& src) = delete;

    bool operator==(const ListBucket< Val >& src) const;

    bool operator!=(const ListBucket< Val >& src) const;

    // ============================================================================
    // ============================================================================

    Val& operator*() noexcept;

    const Val& operator*() const noexcept;

    const ListBucket< Val >* next() const noexcept;

    const ListBucket< Val >* previous() const noexcept;

 
    private:
    friend class List< Val >;
    friend class ListIterator< Val >;
    friend class ListConstIterator< Val >;
    friend class ListIteratorSafe< Val >;
    friend class ListConstIteratorSafe< Val >;

    ListBucket< Val >* _prev_{nullptr};
    ListBucket< Val >* _next_{nullptr};

    Val _val_;
  };
 
  // ===========================================================================
  // ===                     GENERIC DOUBLY CHAINED LISTS                    ===
  // ===========================================================================

  template < typename Val >
  class List {
    public:
    using value_type          = Val;
    using reference           = Val&;
    using const_reference     = const Val&;
    using pointer             = Val*;
    using const_pointer       = const Val*;
    using size_type           = Size;
    using difference_type     = std::ptrdiff_t;
    using iterator            = ListIterator< Val >;
    using const_iterator      = ListConstIterator< Val >;
    using iterator_safe       = ListIteratorSafe< Val >;
    using const_iterator_safe = ListConstIteratorSafe< Val >;

    enum class location { BEFORE, AFTER };
 
    // ============================================================================
    // ============================================================================

    explicit List();

    List(const List< Val >& src);

    List(List< Val >&& src) noexcept;

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

    ~List();

    // ============================================================================
    // ============================================================================

    const const_iterator_safe& cendSafe() const noexcept;

    const iterator_safe& endSafe() noexcept;

    const const_iterator_safe& crendSafe() const noexcept;

    const iterator_safe& rendSafe() noexcept;

    const_iterator_safe cbeginSafe() const;

    iterator_safe beginSafe();

    const_iterator_safe crbeginSafe() const;

    iterator_safe rbeginSafe();

    const const_iterator& cend() const noexcept;

    const iterator& end() noexcept;

    const const_iterator& end() const noexcept;

    const const_iterator& crend() const noexcept;

    const iterator& rend() noexcept;

    const const_iterator& rend() const noexcept;

    const_iterator cbegin() const;

    iterator begin();

    const_iterator begin() const;

    const_iterator crbegin() const;

    iterator rbegin();

    const_iterator rbegin() const;

    // ============================================================================
    // ============================================================================

    Val& pushFront(const Val& val);

    Val& pushFront(Val&& val);

    template < typename... Args >
    Val& push_front(Args&&... args);

    template < typename... Args >
    Val& emplaceFront(Args&&... args);

    Val& pushBack(const Val& val);

    Val& pushBack(Val&& val);

    template < typename... Args >
    Val& push_back(Args&&... args);

    template < typename... Args >
    Val& emplaceBack(Args&&... args);

    Val& insert(const Val& val);

    Val& insert(Val&& val);

    Val& insert(Size pos, const Val& val);

    Val& insert(Size pos, Val&& val);

    Val& insert(const const_iterator_safe& iter, const Val& val, location place = location::BEFORE);

    Val& insert(const const_iterator_safe& iter, Val&& val, location place = location::BEFORE);

    Val& insert(const const_iterator& iter, const Val& val, location place = location::BEFORE);

    Val& insert(const const_iterator& iter, Val&& val, location place = location::BEFORE);

    template < typename... Args >
    Val& emplace(const const_iterator& iter, Args&&... args);

    template < typename... Args >
    Val& emplace(const const_iterator_safe& iter, Args&&... args);

    Val& front() const;

    Val& back() const;

    Size size() const noexcept;

    bool exists(const Val& val) const;

    void erase(Size i);

    void erase(const iterator_safe& iter);

    void erase(const const_iterator_safe& iter);

    void eraseByVal(const Val& val);

    void eraseAllVal(const Val& val);

    void popBack();

    void popFront();

    void clear();

    bool empty() const noexcept;

    void swap(List& other_list);

    std::string toString() const;

    template < typename Mount >
    List< Mount > map(Mount (*f)(Val)) const;

    template < typename Mount >
    List< Mount > map(Mount (*f)(Val&)) const;

    template < typename Mount >
    List< Mount > map(Mount (*f)(const Val&)) const;

    template < typename Mount >
    List< Mount > map(const Mount& mount) const;

    // ============================================================================
    // ============================================================================

    List< Val >& operator=(const List< Val >& src);

    List< Val >& operator=(List< Val >&& src);

    Val& operator+=(const Val& val);

    Val& operator+=(Val&& val);

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

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

    Val& operator[](const Size i);

    const Val& operator[](const Size i) const;

 
    private:
    ListBucket< Val >* _deb_list_{nullptr};

    ListBucket< Val >* _end_list_{nullptr};

    Size _nb_elements_{Size(0)};

    mutable std::vector< const_iterator_safe* > _safe_iterators_;

    void _copy_elements_(const List< Val >& src);

    ListBucket< Val >* _getIthBucket_(Size i) const noexcept;

    ListBucket< Val >* _getBucket_(const Val& val) const noexcept;

    void _erase_(ListBucket< Val >* bucket);

    ListBucket< Val >* _createBucket_(const Val& val) const;

    ListBucket< Val >* _createBucket_(Val&& val) const;

    template < typename... Args >
    ListBucket< Val >* _createEmplaceBucket_(Args&&... args) const;

    Val& _pushFront_(ListBucket< Val >* new_elt);

    Val& _pushBack_(ListBucket< Val >* new_elt);

    Val& _insertBefore_(ListBucket< Val >* new_elt, ListBucket< Val >* current_elt);

    Val& _insertAfter_(ListBucket< Val >* new_elt, ListBucket< Val >* current_elt);

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

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

    friend class ListIterator< Val >;
    friend class ListConstIterator< Val >;
    friend class ListIteratorSafe< Val >;
    friend class ListConstIteratorSafe< Val >;
  };
 
  // ===========================================================================
  // ===                      UNSAFE LIST CONST ITERATORS                    ===
  // ===========================================================================
  template < typename Val >
  class ListConstIterator {
    public:
    using iterator_category = std::bidirectional_iterator_tag;
    using value_type        = Val;
    using reference         = Val&;
    using const_reference   = const Val&;
    using pointer           = Val*;
    using const_pointer     = const Val*;
    using difference_type   = std::ptrdiff_t;
 
    // ============================================================================
    // ============================================================================

    explicit ListConstIterator() noexcept;
 
#ifndef DOXYGEN_SHOULD_SKIP_THIS
    // constructor for the static cend/crend iterator
    // only list.cpp should use this constructor
    explicit consteval ListConstIterator(StaticInitializer init) noexcept {}
#endif   // DOXYGEN_SHOULD_SKIP_THIS

    ListConstIterator(const List< Val >& theList) noexcept;

    ListConstIterator(const ListConstIterator< Val >& src) noexcept;

    ListConstIterator(ListConstIterator< Val >&& src) noexcept;

    ListConstIterator(const List< Val >& theList, Size ind_elt);

    ~ListConstIterator() noexcept;

    // ============================================================================
    // ============================================================================

    void clear() noexcept;

    void setToEnd() noexcept;

    bool isEnd() const noexcept;

    // ============================================================================
    // ============================================================================

    ListConstIterator< Val >& operator=(const ListConstIterator< Val >& src) noexcept;

    ListConstIterator< Val >& operator=(ListConstIterator< Val >&& src) noexcept;

    ListConstIterator< Val >& operator++() noexcept;

    ListConstIterator< Val >& operator+=(difference_type i) noexcept;

    ListConstIterator< Val >& operator--() noexcept;

    ListConstIterator< Val >& operator-=(difference_type i) noexcept;

    ListConstIterator< Val > operator+(difference_type i) noexcept;

    ListConstIterator< Val > operator-(difference_type i) noexcept;

    bool operator!=(const ListConstIterator< Val >& src) const noexcept;

    bool operator==(const ListConstIterator< Val >& src) const noexcept;

    const Val& operator*() const;

    const Val* operator->() const;

 
    private:
    friend class List< Val >;

    ListBucket< Val >* _bucket_{nullptr};

    ListBucket< Val >* _getBucket_() const noexcept;
  };

  template < typename Val >
  typename ListConstIterator< Val >::difference_type
      operator-(const ListConstIterator< Val >& iter1, const ListConstIterator< Val >& iter2);
 
  // ===========================================================================
  // ===                         UNSAFE LIST ITERATORS                       ===
  // ===========================================================================

  template < typename Val >
  class ListIterator: public ListConstIterator< Val > {
    public:
    using iterator_category = std::bidirectional_iterator_tag;
    using value_type        = Val;
    using reference         = Val&;
    using const_reference   = const Val&;
    using pointer           = Val*;
    using const_pointer     = const Val*;
    using difference_type   = std::ptrdiff_t;
 
    // ============================================================================
    // ============================================================================

    explicit ListIterator() noexcept;
 
#ifndef DOXYGEN_SHOULD_SKIP_THIS
    // constructor for the static end/rend iterator
    // only list.cpp should use this constructor
    explicit consteval ListIterator(StaticInitializer init) noexcept :
        ListConstIterator< Val >(init) {}
#endif   // DOXYGEN_SHOULD_SKIP_THIS

    ListIterator(const List< Val >& theList) noexcept;

    ListIterator(const ListIterator< Val >& src) noexcept;

    ListIterator(ListIterator< Val >&& src) noexcept;

    ListIterator(const List< Val >& theList, Size ind_elt);

    ~ListIterator() noexcept;

    // ============================================================================
    // ============================================================================
 
    using ListConstIterator< Val >::clear;
    using ListConstIterator< Val >::setToEnd;
    using ListConstIterator< Val >::isEnd;

 
    // ============================================================================
    // ============================================================================

    ListIterator< Val >& operator=(const ListIterator< Val >& src) noexcept;


    ListIterator< Val >& operator=(ListIterator< Val >&& src) noexcept;

    ListIterator< Val >& operator++() noexcept;

    ListIterator< Val >& operator+=(difference_type i) noexcept;

    ListIterator< Val >& operator--() noexcept;

    ListIterator< Val >& operator-=(difference_type i) noexcept;

    ListIterator< Val > operator+(difference_type i) noexcept;

    ListIterator< Val > operator-(difference_type i) noexcept;

    bool operator==(const ListIterator< Val >& src) const noexcept;

    bool operator!=(const ListIterator< Val >& src) const noexcept;

    const Val& operator*() const;

    Val& operator*();

    const Val* operator->() const;

    Val* operator->();

  };
 
  // ===========================================================================
  // ===                          LIST CONST ITERATORS                       ===
  // ===========================================================================
  template < typename Val >
  class ListConstIteratorSafe {
    public:
    using iterator_category = std::bidirectional_iterator_tag;
    using value_type        = Val;
    using reference         = Val&;
    using const_reference   = const Val&;
    using pointer           = Val*;
    using const_pointer     = const Val*;
    using difference_type   = std::ptrdiff_t;
 
    // ============================================================================
    // ============================================================================

    explicit ListConstIteratorSafe() noexcept;
 
#ifndef DOXYGEN_SHOULD_SKIP_THIS
    // constructor for the static cendSafe/crendSafe iterator
    // only list.cpp should use this constructor
    explicit consteval ListConstIteratorSafe(StaticInitializer init) noexcept {}
#endif   // DOXYGEN_SHOULD_SKIP_THIS

    ListConstIteratorSafe(const List< Val >& theList);

    ListConstIteratorSafe(const ListConstIteratorSafe< Val >& src);

    ListConstIteratorSafe(const List< Val >& theList, Size ind_elt);

    ListConstIteratorSafe(ListConstIteratorSafe< Val >&& src);

    ~ListConstIteratorSafe();

    // ============================================================================
    // ============================================================================

    void clear();

    void setToEnd();

    bool isEnd() const;

    // ============================================================================
    // ============================================================================

    ListConstIteratorSafe< Val >& operator=(const ListConstIteratorSafe< Val >& src);

    ListConstIteratorSafe< Val >& operator=(ListConstIteratorSafe< Val >&& src);

    ListConstIteratorSafe< Val >& operator++() noexcept;

    ListConstIteratorSafe< Val >& operator+=(difference_type i) noexcept;

    ListConstIteratorSafe< Val >& operator--() noexcept;

    ListConstIteratorSafe< Val >& operator-=(difference_type i) noexcept;

    ListConstIteratorSafe< Val > operator+(difference_type i) noexcept;

    ListConstIteratorSafe< Val > operator-(difference_type i) noexcept;

    bool operator!=(const ListConstIteratorSafe< Val >& src) const;

    bool operator==(const ListConstIteratorSafe< Val >& src) const;

    const Val& operator*() const;

    const Val* operator->() const;

 
    private:
    friend class List< Val >;
    friend class ListConstIterator< Val >;

    const List< Val >* _list_{nullptr};

    ListBucket< Val >* _bucket_{nullptr};

    ListBucket< Val >* _next_current_bucket_{nullptr};

    ListBucket< Val >* _prev_current_bucket_{nullptr};

    bool _null_pointing_{false};

    ListBucket< Val >* _getBucket_() const noexcept;

    void _removeFromSafeList_() const;

    ListConstIteratorSafe< Val >& _opPlus_(Size i) noexcept;

    ListConstIteratorSafe< Val >& _opMinus_(Size i) noexcept;
  };

  template < typename Val >
  typename ListConstIteratorSafe< Val >::difference_type
      operator-(const ListConstIteratorSafe< Val >& iter1,
                const ListConstIteratorSafe< Val >& iter2);
 
  // ===========================================================================
  // ===                             LIST ITERATORS                          ===
  // ===========================================================================

  template < typename Val >
  class ListIteratorSafe: public ListConstIteratorSafe< Val > {
    public:
    using iterator_category = std::bidirectional_iterator_tag;
    using value_type        = Val;
    using reference         = Val&;
    using const_reference   = const Val&;
    using pointer           = Val*;
    using const_pointer     = const Val*;
    using difference_type   = std::ptrdiff_t;
 
    // ============================================================================
    // ============================================================================

    explicit ListIteratorSafe() noexcept;
 
#ifndef DOXYGEN_SHOULD_SKIP_THIS
    // constructor for the static endSafe/rendSafe iterator
    // only list.cpp should use this constructor
    explicit consteval ListIteratorSafe(StaticInitializer init) noexcept :
        ListConstIteratorSafe< Val >(init) {}
#endif   // DOXYGEN_SHOULD_SKIP_THIS

    ListIteratorSafe(const List< Val >& theList);

    ListIteratorSafe(const ListIteratorSafe< Val >& src);

    ListIteratorSafe(const List< Val >& theList, Size ind_elt);

    ListIteratorSafe(ListIteratorSafe< Val >&& src);

    ~ListIteratorSafe();

    // ============================================================================
    // ============================================================================
 
    using ListConstIteratorSafe< Val >::clear;
    using ListConstIteratorSafe< Val >::setToEnd;
    using ListConstIteratorSafe< Val >::isEnd;

    // ============================================================================
    // ============================================================================

    ListIteratorSafe< Val >& operator=(const ListIteratorSafe< Val >& src);

    ListIteratorSafe< Val >& operator=(ListIteratorSafe< Val >&& src);

    ListIteratorSafe< Val >& operator++() noexcept;

    ListIteratorSafe< Val >& operator+=(difference_type i) noexcept;

    ListIteratorSafe< Val >& operator--() noexcept;

    ListIteratorSafe< Val >& operator-=(difference_type i) noexcept;

    ListIteratorSafe< Val > operator+(difference_type i) noexcept;

    ListIteratorSafe< Val > operator-(difference_type i) noexcept;

    Val& operator*();

    Val* operator->();

    bool operator!=(const ListIteratorSafe< Val >& src) const;

    bool operator==(const ListIteratorSafe< Val >& src) const;

    const Val& operator*() const;

    const Val* operator->() const;
  };
 
#ifndef DOXYGEN_SHOULD_SKIP_THIS
  // _static_list_end_ is a 'constant' iterator initialized at compile time
  // that represents the end iterators for all lists (whatever their content).
  // This global variable avoids creating the same iterators within every
  // List instance (this would be quite inefficient as end is precisely
  // identical for all lists). The same holds for reverse and safe end iterators.
  // The type of _list_end_ is a pointer to void because C++ allows
  // pointers to void to be cast into pointers to other types (and conversely).
  // This avoids the painful strict-aliasing rule warning
  extern const ListConstIteratorSafe< Debug > _static_list_end_safe_;
  extern const ListConstIterator< Debug >     _static_list_end_;
 
  inline constexpr void* const _list_end_safe_ = (void* const)&_static_list_end_safe_;
  inline constexpr void* const _list_end_      = (void* const)&_static_list_end_;
#endif   // DOXYGEN_SHOULD_SKIP_THIS
 
} /* namespace gum */
 
 
#ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
extern template class gum::List< bool >;
extern template class gum::List< int >;
extern template class gum::List< unsigned int >;
#endif
 
 
// always include the implementation of the templates
#include <agrum/base/core/list_tpl.h>
 
#endif /* GUM_LIST_H */