hashTable.h

Go to the documentation of this file.

/****************************************************************************
 *   This file is part of the aGrUM/pyAgrum library.                        *
 *                                                                          *
 *   Copyright (c) 2005-2026 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-2026                            *
 *       - 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_HASHTABLE_H
#define GUM_HASHTABLE_H
 
#include <cstddef>
#include <iostream>
#include <limits>
#include <string>
#include <utility>
#include <vector>
 
#include <agrum/agrum.h>
 
#include <agrum/base/core/hashFunc.h>
#include <agrum/base/core/staticInitializer.h>
 
#include <agrum/base/core/optional_ref.h>
#include <initializer_list>
#include <string_view>
 
namespace gum {
#ifndef DOXYGEN_SHOULD_SKIP_THIS
 
  // the templates used by this file
  template < typename Key, typename Val >
  class HashTable;
  template < typename Key, typename Val >
  class HashTableList;
  template < typename Key, typename Val >
  class HashTableIterator;
  template < typename Key, typename Val >
  class HashTableConstIterator;
  template < typename Key, typename Val >
  class HashTableIteratorSafe;
  template < typename Key, typename Val >
  class HashTableConstIteratorSafe;
  template < typename T1, typename T2 >
  class Bijection;
 
#endif /* DOXYGEN_SHOULD_SKIP_THIS */

  struct HashTableConst {
    static constexpr Size default_size{Size(4)};

    static constexpr Size default_mean_val_by_slot{Size(3)};

    static constexpr bool default_resize_policy{true};

    static constexpr bool default_uniqueness_policy{true};
  };
 
  // Doxygen raises warning with the following comment bloc
  // @brief Prints the content of a gum::HashTableList in the stream.
  // @ingroup hashtable_group
  // @param s The s used to print the gum::HashTableList.
  // @param list The gum::HashTableList to print.
  // @return Returns the std::ostream s.
  // @tparam Key The type of keys in the gum::HashTableList.
  // @tparam Val The type of values in the gum::HashTableList.

  template < typename Key, typename Val >
  std::ostream& operator<<(std::ostream& s, const HashTableList< Key, Val >& list);
 
  // Doxygen raises warning with the following comment bloc
  // @brief Prints the content of a gum::HashTableList with pointers key in the
  // stream.
  // @ingroup hashtable_group
  // @param s The s used to print the gum::HashTableList.
  // @param list The gum::HashTableList to print.
  // @return Returns the std::ostream s.
  // @tparam Key The type of keys in the gum::HashTableList.
  // @tparam Val The type of values in the gum::HashTableList.
  //

  template < typename Key, typename Val >
  std::ostream& operator<<(std::ostream& s, const HashTableList< Key*, Val >& list);
 
  // Doxygen raises warning with the following comment bloc
  // @brief Prints the content of a gum::HashTable in the stream.
  // @ingroup hashtable_group
  // @param s The stream used to print the gum::HashTable.
  // @param table The gum::HashTable to print.
  // @return Returns the std::ostream s.
  // @tparam Key The type of keys in the gum::HashTable.
  // @tparam Val The type of values in the gum::HashTable.

  template < typename Key, typename Val >
  std::ostream& operator<<(std::ostream& s, const HashTable< Key, Val >& table);
 
  // Doxygen raises warning with the following comment bloc
  // @brief Prints the content of a gum::HashTable with pointers key in the
  // stream.
  // @ingroup hashtable_group
  // @param s The stream used to print the gum::HashTable.
  // @param table The gum::HashTable to print.
  // @return Returns the std::ostream s.
  // @tparam Key The type of keys in the gum::HashTable.
  // @tparam Val The type of values in the gum::HashTable.

  template < typename Key, typename Val >
  std::ostream& operator<<(std::ostream& s, const HashTable< Key*, Val >& table);
 
  // ===========================================================================
  // ===          LISTS SPECIFIC FOR SAVING ELEMENTS IN HASHTABLES           ===
  // ===========================================================================

  template < typename Key, typename Val >
  struct HashTableBucket {
    std::pair< const Key, Val > pair;

    HashTableBucket< Key, Val >* prev{nullptr};

    HashTableBucket< Key, Val >* next{nullptr};

    enum class Emplace { EMPLACE };

    HashTableBucket() = default;

    HashTableBucket(const HashTableBucket< Key, Val >& from) : pair{from.pair} {}

    HashTableBucket(const Key& k, const Val& v) : pair{k, v} {}

    HashTableBucket(Key&& k, Val&& v) : pair{std::move(k), std::move(v)} {}

    explicit HashTableBucket(const std::pair< const Key, Val >& p);

    explicit HashTableBucket(std::pair< const Key, Val >&& p);

    template < typename... Args >
    HashTableBucket(Emplace e, Args&&... args);

    ~HashTableBucket() = default;

    std::pair< const Key, Val >& elt();

    Key& key();

    Val& val();
  };
 
  // ===========================================================================
  // ===       DOUBLY CHAINED LISTS FOR STORING ELEMENTS IN HASH TABLES      ===
  // ===========================================================================

  template < typename Key, typename Val >
  class HashTableList {
    public:
    using key_type        = Key;
    using mapped_type     = Val;
    using value_type      = std::pair< const Key, Val >;
    using reference       = value_type&;
    using const_reference = const value_type&;
    using pointer         = value_type*;
    using const_pointer   = const value_type*;
    using size_type       = Size;
    using Bucket          = HashTableBucket< Key, Val >;
 
    // ============================================================================
    // ============================================================================

    HashTableList() noexcept;

    HashTableList(const HashTableList< Key, Val >& from);

    HashTableList(HashTableList< Key, Val >&& from) noexcept;

    ~HashTableList();

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

    HashTableList< Key, Val >& operator=(const HashTableList< Key, Val >& from);

    HashTableList< Key, Val >& operator=(HashTableList< Key, Val >&& from) noexcept;

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

    value_type& at(Size i);

    const value_type& at(Size i) const;

    mapped_type& operator[](const key_type& key);

    const mapped_type& operator[](const key_type& key) const;

    bool exists(const key_type& key) const;

    void insert(Bucket* new_elt) noexcept;

    void erase(Bucket* ptr);

    void clear();

    bool empty() const noexcept;

    Bucket* bucket(const Key& key) const;

    Bucket* bucket(std::string_view key) const
      requires std::same_as< Key, std::string >;

 
    private:
    friend class HashTable< Key, Val >;
    friend class HashTableIterator< Key, Val >;
    friend class HashTableConstIterator< Key, Val >;
    friend class HashTableIteratorSafe< Key, Val >;
    friend class HashTableConstIteratorSafe< Key, Val >;
    friend std::ostream& operator<< <>(std::ostream&, const HashTableList< Key, Val >&);
    friend std::ostream& operator<< <>(std::ostream&, const HashTableList< Key*, Val >&);
    friend std::ostream& operator<< <>(std::ostream&, const HashTable< Key, Val >&);
    friend std::ostream& operator<< <>(std::ostream&, const HashTable< Key*, Val >&);

    HashTableBucket< Key, Val >* _deb_list_{nullptr};

    HashTableBucket< Key, Val >* _end_list_{nullptr};

    Size _nb_elements_{Size(0)};

    void _copy_(const HashTableList< Key, Val >& from);
  };
 
  // ===========================================================================
  // ===                          GENERIC HASH TABLES                        ===
  // ===========================================================================
  template < typename Key, typename Val >
  class HashTable {
    public:
    using key_type            = Key;
    using mapped_type         = Val;
    using value_type          = std::pair< const Key, Val >;
    using reference           = value_type&;
    using const_reference     = const value_type&;
    using pointer             = value_type*;
    using const_pointer       = const value_type*;
    using size_type           = Size;
    using difference_type     = std::ptrdiff_t;
    using iterator            = HashTableIterator< Key, Val >;
    using const_iterator      = HashTableConstIterator< Key, Val >;
    using iterator_safe       = HashTableIteratorSafe< Key, Val >;
    using const_iterator_safe = HashTableConstIteratorSafe< Key, Val >;

    using Bucket = HashTableBucket< Key, Val >;
 
    // ============================================================================
    // ============================================================================

    explicit HashTable(Size size_param         = HashTableConst::default_size,
                       bool resize_pol         = HashTableConst::default_resize_policy,
                       bool key_uniqueness_pol = HashTableConst::default_uniqueness_policy);

    explicit HashTable(std::initializer_list< std::pair< Key, Val > > list);

    HashTable(const HashTable< Key, Val >& from);

    HashTable(HashTable< Key, Val >&& from) noexcept;

    ~HashTable();

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

    const iterator& end() noexcept;

    const const_iterator& end() const noexcept;

    const const_iterator& cend() const noexcept;

    iterator begin();

    const_iterator begin() const;

    const_iterator cbegin() const;

    const iterator_safe& endSafe() noexcept;

    const const_iterator_safe& endSafe() const noexcept;

    const const_iterator_safe& cendSafe() const noexcept;

    iterator_safe beginSafe();

    const_iterator_safe beginSafe() const;

    const_iterator_safe cbeginSafe() const;

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

    HashTable< Key, Val >& operator=(const HashTable< Key, Val >& from);

    HashTable< Key, Val >& operator=(HashTable< Key, Val >&& from) noexcept;

    Val& operator[](const Key& key);


    const Val& operator[](const Key& key) const;

    template < typename K >
      requires(std::same_as< Key, std::string > && std::convertible_to< K, std::string_view >
               && !std::same_as< std::decay_t< K >, std::string >)
    Val& operator[](const K& key);

    template < typename K >
      requires(std::same_as< Key, std::string > && std::convertible_to< K, std::string_view >
               && !std::same_as< std::decay_t< K >, std::string >)
    const Val& operator[](const K& key) const;

    bool operator==(const HashTable< Key, Val >& from) const;
 

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

    Size capacity() const noexcept;


    void resize(Size new_size);

    void setResizePolicy(const bool new_policy) noexcept;

    bool resizePolicy() const noexcept;

    void setKeyUniquenessPolicy(const bool new_policy) noexcept;

    bool keyUniquenessPolicy() const noexcept;

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

    Size size() const noexcept;

    bool exists(const Key& key) const;

    template < typename K >
      requires(std::same_as< Key, std::string > && std::convertible_to< K, std::string_view >
               && !std::same_as< std::decay_t< K >, std::string >)
    bool exists(const K& key) const;

    optional_ref< Val > tryGet(const Key& key);

    optional_ref< const Val > tryGet(const Key& key) const;

    template < typename K >
      requires(std::same_as< Key, std::string > && std::convertible_to< K, std::string_view >
               && !std::same_as< std::decay_t< K >, std::string >)
    optional_ref< Val > tryGet(const K& key);

    template < typename K >
      requires(std::same_as< Key, std::string > && std::convertible_to< K, std::string_view >
               && !std::same_as< std::decay_t< K >, std::string >)
    optional_ref< const Val > tryGet(const K& key) const;

    value_type& insert(const Key& key, const Val& val);

    value_type& insert(Key&& key, Val&& val);

    value_type& insert(const std::pair< Key, Val >& elt);

    value_type& insert(std::pair< Key, Val >&& elt);

    template < typename... Args >
    value_type& emplace(Args&&... args);

    mapped_type& getWithDefault(const Key& key, const Val& default_value);

    mapped_type& getWithDefault(Key&& key, Val&& default_value);

    void set(const Key& key, const Val& default_value);

    void reset(const Key& key);

    void erase(const Key& key);

    template < typename K >
      requires(std::same_as< Key, std::string > && std::convertible_to< K, std::string_view >
               && !std::same_as< std::decay_t< K >, std::string >)
    void erase(const K& key);

    void erase(const iterator_safe& iter);

    void erase(const const_iterator_safe& iter);

    void eraseByVal(const Val& val);

    const Key& keyByVal(const Val& val) const;

    const Key& key(const Key& key) const;

    optional_ref< const Key > tryGetKey(const Key& key) const;

    void eraseAllVal(const Val& val);

    void clear();

    bool empty() const noexcept;

    template < typename Mount >
    HashTable< Key, Mount > map(Mount (*f)(Val),
                                Size size       = Size(0),
                                bool resize_pol = HashTableConst::default_resize_policy,
                                bool key_uniqueness_pol
                                = HashTableConst::default_uniqueness_policy) const;

    template < typename Mount >
    HashTable< Key, Mount > map(Mount (*f)(Val&),
                                Size size       = Size(0),
                                bool resize_pol = HashTableConst::default_resize_policy,
                                bool key_uniqueness_pol
                                = HashTableConst::default_uniqueness_policy) const;

    template < typename Mount >
    HashTable< Key, Mount > map(Mount (*f)(const Val&),
                                Size size       = Size(0),
                                bool resize_pol = HashTableConst::default_resize_policy,
                                bool key_uniqueness_pol
                                = HashTableConst::default_uniqueness_policy) const;

    template < typename Mount >
    HashTable< Key, Mount > map(const Mount& val,
                                Size         size       = Size(0),
                                bool         resize_pol = HashTableConst::default_resize_policy,
                                bool         key_uniqueness_pol
                                = HashTableConst::default_uniqueness_policy) const;

 
    private:
    friend class HashTableIterator< Key, Val >;
    friend class HashTableConstIterator< Key, Val >;
    friend class HashTableIteratorSafe< Key, Val >;
    friend class HashTableConstIteratorSafe< Key, Val >;
 
    friend std::ostream& operator<< <>(std::ostream&, const HashTable< Key, Val >&);
    friend std::ostream& operator<< <>(std::ostream& s, const HashTable< Key*, Val >& table);

    template < typename T1, typename T2 >
    friend class Bijection;

    std::vector< HashTableList< Key, Val > > _nodes_;

    Size _size_;

    Size _nb_elements_{Size(0)};

    HashFunc< Key > _hash_func_;

    bool _resize_policy_{true};

    bool _key_uniqueness_policy_{true};

    mutable Size _begin_index_{std::numeric_limits< Size >::max()};

    mutable std::vector< HashTableConstIteratorSafe< Key, Val >* > _safe_iterators_;
 

    void _erase_(HashTableBucket< Key, Val >* bucket, Size index);

    void _copy_(const HashTable< Key, Val >& table);

    void _create_(Size size);

    void _clearIterators_();

    void _insert_(Bucket* bucket);
  };
 
  // ===========================================================================
  // ===                   SAFE HASH TABLES CONST ITERATORS                  ===
  // ===========================================================================
  template < typename Key, typename Val >
  class HashTableConstIteratorSafe {
    public:
    using iterator_category = std::forward_iterator_tag;
    using key_type          = Key;
    using mapped_type       = Val;
    using value_type        = std::pair< const Key, Val >;
    using reference         = value_type&;
    using const_reference   = const value_type&;
    using pointer           = value_type*;
    using const_pointer     = const value_type*;
    using difference_type   = std::ptrdiff_t;
 
    // ============================================================================
    // ============================================================================

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

    explicit HashTableConstIteratorSafe(const HashTable< Key, Val >& tab);


    HashTableConstIteratorSafe(const HashTable< Key, Val >& tab, Size ind_elt);

    HashTableConstIteratorSafe(const HashTableConstIteratorSafe< Key, Val >& from);

    explicit HashTableConstIteratorSafe(const HashTableConstIterator< Key, Val >& from);

    HashTableConstIteratorSafe(HashTableConstIteratorSafe< Key, Val >&& from) noexcept;

    ~HashTableConstIteratorSafe() noexcept;

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

    const key_type& key() const;


    const mapped_type& val() const;

    void clear() noexcept;

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

    HashTableConstIteratorSafe< Key, Val >&
        operator=(const HashTableConstIteratorSafe< Key, Val >& from);

    HashTableConstIteratorSafe< Key, Val >&
        operator=(const HashTableConstIterator< Key, Val >& from);

    HashTableConstIteratorSafe< Key, Val >&
        operator=(HashTableConstIteratorSafe< Key, Val >&& from) noexcept;

    HashTableConstIteratorSafe< Key, Val >& operator++() noexcept;

    HashTableConstIteratorSafe< Key, Val >& operator+=(Size i) noexcept;

    HashTableConstIteratorSafe< Key, Val > operator+(Size i) const;

    bool operator==(const HashTableConstIteratorSafe< Key, Val >& from) const noexcept;

    const value_type& operator*() const;

 
    protected:
    friend class HashTable< Key, Val >;

    const HashTable< Key, Val >* _table_{nullptr};

    Size _index_{Size(0)};

    HashTableBucket< Key, Val >* _bucket_{nullptr};

    HashTableBucket< Key, Val >* _next_bucket_{nullptr};

    [[nodiscard]] HashTableBucket< Key, Val >* _getBucket_() const noexcept;

    [[nodiscard]] Size _getIndex_() const noexcept;

    void _removeFromSafeList_() const;

    void _insertIntoSafeList_() const;
  };
 
  // ===========================================================================
  // ===                         HASH TABLES ITERATORS                       ===
  // ===========================================================================

  template < typename Key, typename Val >
  class HashTableIteratorSafe: public HashTableConstIteratorSafe< Key, Val > {
    public:
    using iterator_category = std::forward_iterator_tag;
    using key_type          = Key;
    using mapped_type       = Val;
    using value_type        = std::pair< const Key, Val >;
    using reference         = value_type&;
    using const_reference   = const value_type&;
    using pointer           = value_type*;
    using const_pointer     = const value_type*;
    using difference_type   = std::ptrdiff_t;
 
    // ============================================================================
    // ============================================================================

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

    explicit HashTableIteratorSafe(const HashTable< Key, Val >& tab);

    HashTableIteratorSafe(const HashTable< Key, Val >& tab, Size ind_elt);

    HashTableIteratorSafe(const HashTableIteratorSafe< Key, Val >& from);

    explicit HashTableIteratorSafe(const HashTableIterator< Key, Val >& from);

    HashTableIteratorSafe(HashTableIteratorSafe< Key, Val >&& from) noexcept;

    ~HashTableIteratorSafe() noexcept;

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

    using HashTableConstIteratorSafe< Key, Val >::key;
    using HashTableConstIteratorSafe< Key, Val >::val;
    using HashTableConstIteratorSafe< Key, Val >::clear;

    mapped_type& val();

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

    HashTableIteratorSafe< Key, Val >& operator=(const HashTableIteratorSafe< Key, Val >& from);

    HashTableIteratorSafe< Key, Val >& operator=(const HashTableIterator< Key, Val >& from);

    HashTableIteratorSafe< Key, Val >& operator=(HashTableIteratorSafe< Key, Val >&& from) noexcept;

    HashTableIteratorSafe< Key, Val >& operator++() noexcept;

    HashTableIteratorSafe< Key, Val >& operator+=(Size i) noexcept;

    HashTableIteratorSafe< Key, Val > operator+(Size i) const;

    bool operator==(const HashTableIteratorSafe< Key, Val >& from) const noexcept;

    value_type& operator*();

    const value_type& operator*() const;

  };
 
  // ===========================================================================
  // ===                  UNSAFE HASH TABLES CONST ITERATORS                 ===
  // ===========================================================================

  template < typename Key, typename Val >
  class HashTableConstIterator {
    public:
    using iterator_category = std::forward_iterator_tag;
    using key_type          = Key;
    using mapped_type       = Val;
    using value_type        = std::pair< const Key, Val >;
    using reference         = value_type&;
    using const_reference   = const value_type&;
    using pointer           = value_type*;
    using const_pointer     = const value_type*;
    using difference_type   = std::ptrdiff_t;
 
    // ============================================================================
    // ============================================================================

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

    explicit HashTableConstIterator(const HashTable< Key, Val >& tab) noexcept;

    HashTableConstIterator(const HashTable< Key, Val >& tab, Size ind_elt);

    HashTableConstIterator(const HashTableConstIterator< Key, Val >& from) noexcept;

    HashTableConstIterator(HashTableConstIterator< Key, Val >&& from) noexcept;

    ~HashTableConstIterator() noexcept;

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

    [[nodiscard]] const key_type& key() const;

    [[nodiscard]] const mapped_type& val() const;

    void clear() noexcept;

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

    HashTableConstIterator< Key, Val >&
        operator=(const HashTableConstIterator< Key, Val >& from) noexcept;

    HashTableConstIterator< Key, Val >&
        operator=(HashTableConstIterator< Key, Val >&& from) noexcept;


    HashTableConstIterator< Key, Val >& operator++() noexcept;

    HashTableConstIterator< Key, Val >& operator+=(Size i) noexcept;

    HashTableConstIterator< Key, Val > operator+(Size i) const noexcept;

    bool operator==(const HashTableConstIterator< Key, Val >& from) const noexcept;
 

    const value_type& operator*() const;

 
    protected:
    friend class HashTable< Key, Val >;

    friend class HashTableConstIteratorSafe< Key, Val >;

    const HashTable< Key, Val >* _table_{nullptr};

    Size _index_{Size(0)};

    typename HashTable< Key, Val >::Bucket* _bucket_{nullptr};

    [[nodiscard]] typename HashTable< Key, Val >::Bucket* _getBucket_() const noexcept;

    [[nodiscard]] Size _getIndex_() const noexcept;
  };
 
  // ===========================================================================
  // ===                      UNSAFE HASH TABLES ITERATORS                   ===
  // ===========================================================================

  template < typename Key, typename Val >
  class HashTableIterator: public HashTableConstIterator< Key, Val > {
    public:
    using iterator_category = std::forward_iterator_tag;
    using key_type          = Key;
    using mapped_type       = Val;
    using value_type        = std::pair< const Key, Val >;
    using reference         = value_type&;
    using const_reference   = const value_type&;
    using pointer           = value_type*;
    using const_pointer     = const value_type*;
    using difference_type   = std::ptrdiff_t;
 
    // ############################################################################
    // ############################################################################

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

    explicit HashTableIterator(const HashTable< Key, Val >& tab) noexcept;


    HashTableIterator(const HashTable< Key, Val >& tab, Size ind_elt);

    HashTableIterator(const HashTableIterator< Key, Val >& from) noexcept;

    HashTableIterator(HashTableIterator< Key, Val >&& from) noexcept;

    ~HashTableIterator() noexcept;

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

    using HashTableConstIterator< Key, Val >::key;
    using HashTableConstIterator< Key, Val >::val;
    using HashTableConstIterator< Key, Val >::clear;

    mapped_type& val();

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

    HashTableIterator< Key, Val >& operator=(const HashTableIterator< Key, Val >& from) noexcept;

    HashTableIterator< Key, Val >& operator=(HashTableIterator< Key, Val >&& from) noexcept;

    HashTableIterator< Key, Val >& operator++() noexcept;

    HashTableIterator< Key, Val >& operator+=(Size i) noexcept;

    HashTableIterator< Key, Val > operator+(Size i) const noexcept;

    bool operator==(const HashTableIterator< Key, Val >& from) const noexcept;

    value_type& operator*();

    const value_type& operator*() const;

  };
 
 
#ifndef DOXYGEN_SHOULD_SKIP_THIS
  // _static_HashTable_end_ is a 'constant' iterator initialized at compile time
  // that represents the end/rend iterators for all hash tables (whatever their
  // type). This global variable avoids creating the same iterators within every
  // HashTable instance (this would be quite inefficient as end is precisely
  // identical for all AVL trees). The same hold for const and safe end iterators.
  // The type of _HashTable_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 HashTableIterator< int, int >          _static_HashTable_end_;
  extern const HashTableConstIterator< int, int >     _static_HashTable_cend_;
  extern const HashTableIteratorSafe< int, int >      _static_HashTable_end_safe_;
  extern const HashTableConstIteratorSafe< int, int > _static_HashTable_cend_safe_;
 
  inline constexpr void* const _HashTable_end_       = (void* const)&_static_HashTable_end_;
  inline constexpr void* const _HashTable_cend_      = (void* const)&_static_HashTable_cend_;
  inline constexpr void* const _HashTable_end_safe_  = (void* const)&_static_HashTable_end_safe_;
  inline constexpr void* const _HashTable_cend_safe_ = (void* const)&_static_HashTable_cend_safe_;
#endif   // DOXYGEN_SHOULD_SKIP_THIS
}   // namespace gum
 
 
#ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
extern template class gum::HashTable< int, int >;
extern template class gum::HashTable< int, std::string >;
extern template class gum::HashTable< std::string, std::string >;
extern template class gum::HashTable< std::string, int >;
#endif
 
 
// always include the implementation of the templates
#include <agrum/base/core/hashTable_tpl.h>
 
#endif   // GUM_HASHTABLE_H