list.h

Go to the documentation of this file.

/***************************************************************************
 *   Copyright (C) 2005 by Christophe GONZALES and Pierre-Henri WUILLEMIN  *
 *   {prenom.nom}_at_lip6.fr                                               *
 *                                                                         *
 *   This program is free software; you can redistribute it and/or modify  *
 *   it under the terms of the GNU General Public License as published by  *
 *   the Free Software Foundation; either version 2 of the License, or     *
 *   (at your option) any later version.                                   *
 *                                                                         *
 *   This program 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 General Public License for more details.                          *
 *                                                                         *
 *   You should have received a copy of the GNU General Public License     *
 *   along with this program; if not, write to the                         *
 *   Free Software Foundation, Inc.,                                       *
 *   59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.             *
 ***************************************************************************/
#ifndef GUM_LIST_H
#define GUM_LIST_H

#include <cstddef>
#include <initializer_list>
#include <iostream>
#include <sstream>
#include <vector>

#include <agrum/agrum.h>
#include <agrum/core/refPtr.h>

#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, typename Alloc >
  class List;

#endif   // DOXYGEN_SHOULD_SKIP_THIS

#ifndef SWIG   // SWIG cannot read these lines
  template < typename Val, typename Alloc >
  std::ostream& operator<<(std::ostream& stream, const List< Val, Alloc >& list);
#endif   // SWIG

#ifndef DOXYGEN_SHOULD_SKIP_THIS
  // __list_end is a 'pseudo static' iterator that represents both end and rend
  // iterators for all Lists (whatever their type). This global variable
  // avoids creating the same iterators whithin every List instance (this would
  // be quite inefficient as end and rend are precisely identical for all
  // lists).
  // 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 weird strict-aliasing rule warning
  extern const void* const __list_end_safe;
  extern const void* const __list_end;
#endif   // DOXYGEN_SHOULD_SKIP_THIS


  // ===========================================================================
  // ===             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:
    template < typename T, typename A >
    friend class List;
    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, typename Alloc = std::allocator< 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 allocator_type = Alloc;
    using iterator = ListIterator< Val >;
    using const_iterator = ListConstIterator< Val >;
    using iterator_safe = ListIteratorSafe< Val >;
    using const_iterator_safe = ListConstIteratorSafe< Val >;

    using BucketAllocator =
       typename Alloc::template rebind< ListBucket< Val > >::other;

    enum class location { BEFORE, AFTER };

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

    List();

    List(const List< Val, Alloc >& src);

    template < typename OtherAlloc >
    List(const List< Val, OtherAlloc >& src);

    List(List< Val, Alloc >&& src);

    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, typename OtherAlloc = std::allocator< Mount > >
    List< Mount, OtherAlloc > map(Mount (*f)(Val)) const;

    template < typename Mount, typename OtherAlloc = std::allocator< Mount > >
    List< Mount, OtherAlloc > map(Mount (*f)(Val&)) const;

    template < typename Mount, typename OtherAlloc = std::allocator< Mount > >
    List< Mount, OtherAlloc > map(Mount (*f)(const Val&)) const;

    template < typename Mount, typename OtherAlloc = std::allocator< Mount > >
    List< Mount, OtherAlloc > map(const Mount& mount) const;

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

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

    template < typename OtherAlloc >
    List< Val, Alloc >& operator=(const List< Val, OtherAlloc >& src);

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

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

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

    template < typename OtherAlloc >
    bool operator==(const List< Val, OtherAlloc >& src) const;

    template < typename OtherAlloc >
    bool operator!=(const List< Val, OtherAlloc >& 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;

    mutable BucketAllocator __alloc_bucket;

    template < typename OtherAlloc >
    void __copy_elements(const List< Val, OtherAlloc >& 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;

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

    ListConstIterator() noexcept;

    template < typename Alloc >
    ListConstIterator(const List< Val, Alloc >& 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:
    template < typename T, typename A >
    friend class List;

    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;

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

    ListIterator() noexcept;

    template < typename Alloc >
    ListIterator(const List< Val, Alloc >& 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;

    using ListConstIterator< Val >::operator==;
    using ListConstIterator< Val >::operator!=;
    using ListConstIterator< Val >::operator*;
    using ListConstIterator< Val >::operator->;

    Val& operator*();

    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;

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

    ListConstIteratorSafe() noexcept;

    template < typename Alloc >
    ListConstIteratorSafe(const List< Val, Alloc >& theList);

    ListConstIteratorSafe(const ListConstIteratorSafe< Val >& src);

    template < typename Alloc >
    ListConstIteratorSafe(const List< Val, Alloc >& 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:
    template < typename T, typename A >
    friend class List;
    friend class ListConstIterator< Val >;

    const List< Val, std::allocator< 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;

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

    ListIteratorSafe() noexcept;

    template < typename Alloc >
    ListIteratorSafe(const List< Val, Alloc >& theList);

    ListIteratorSafe(const ListIteratorSafe< Val >& src);

    template < typename Alloc >
    ListIteratorSafe(const List< Val, Alloc >& 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->();

    using ListConstIteratorSafe< Val >::operator!=;
    using ListConstIteratorSafe< Val >::operator==;
    using ListConstIteratorSafe< Val >::operator*;
    using ListConstIteratorSafe< Val >::operator->;
  };

#ifndef DOXYGEN_SHOULD_SKIP_THIS
  // constructor and destructor for the iterator that represents end and rend
  template <>
  ListConstIteratorSafe< Debug >::ListConstIteratorSafe() noexcept;
  template <>
  ListConstIteratorSafe< Debug >::~ListConstIteratorSafe();
  template <>
  ListConstIterator< Debug >::ListConstIterator() noexcept;
  template <>
  ListConstIterator< Debug >::~ListConstIterator() noexcept;
#endif /* DOXYGEN_SHOULD_SKIP_THIS */

} /* namespace gum */


#ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
#  ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
#    ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
extern template class gum::List< bool >;
#    endif
#  endif
#endif
#ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
#  ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
#    ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
extern template class gum::List< int >;
#    endif
#  endif
#endif
#ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
#  ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
#    ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
extern template class gum::List< unsigned int >;
#    endif
#  endif
#endif


// always include the implementation of the templates
#include <agrum/core/list_tpl.h>

#endif /* GUM_LIST_H */