hashTable.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_HASHTABLE_H
#define GUM_HASHTABLE_H

#include <limits>

#include <cstddef>
#include <initializer_list>
#include <iostream>
#include <string>
#include <utility>
#include <vector>

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

namespace gum {

#ifndef DOXYGEN_SHOULD_SKIP_THIS

  // the templates used by this file
  template < typename Key, typename Val, typename Alloc >
  class HashTable;
  template < typename Key, typename Val, typename Alloc >
  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, typename Alloc >
  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.
  // @tparam Alloc The gum::HashTableList allocator.

  template < typename Key, typename Val, typename Alloc >
  std::ostream& operator<<(std::ostream&                           s,
                           const HashTableList< Key, Val, Alloc >& 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.
  // @tparam Alloc The gum::HashTableList allocator.
  //

  template < typename Key, typename Val, typename Alloc >
  std::ostream& operator<<(std::ostream&                            s,
                           const HashTableList< Key*, Val, Alloc >& 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.
  // @tparam Alloc The gum::HashTable allocator.

  template < typename Key, typename Val, typename Alloc >
  std::ostream& operator<<(std::ostream&                       s,
                           const HashTable< Key, Val, Alloc >& 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.
  // @tparam Alloc The gum::HashTable allocator.

  template < typename Key, typename Val, typename Alloc >
  std::ostream& operator<<(std::ostream&                        s,
                           const HashTable< Key*, Val, Alloc >& 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() {}

    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)} {}

    HashTableBucket(const std::pair< const Key, Val >& p) : pair(p) {}

    HashTableBucket(std::pair< const Key, Val >&& p) : pair(std::move(p)) {}

    template < typename... Args >
    HashTableBucket(Emplace e, Args&&... args) :
        // emplace (universal) constructor
        pair(std::forward< Args >(args)...) {}

    ~HashTableBucket() {}

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

    Key& key() { return const_cast< Key& >(pair.first); }

    Val& val() { return pair.second; }
  };

  // ===========================================================================
  // ===       DOUBLY CHAINED LISTS FOR STORING ELEMENTS IN HASH TABLES      ===
  // ===========================================================================

  template < typename Key, typename Val, typename Alloc >
  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 allocator_type = Alloc;
    using Bucket = HashTableBucket< Key, Val >;

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

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

    HashTableList(BucketAllocator* allocator = nullptr) noexcept;

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

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

    ~HashTableList();

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

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

    template < typename OtherAlloc >
    HashTableList< Key, Val, Alloc >&
       operator=(const HashTableList< Key, Val, OtherAlloc >& from);

    HashTableList< Key, Val, Alloc >&
       operator=(HashTableList< Key, Val, Alloc >&& 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;

    void setAllocator(BucketAllocator& alloc);


    private:
    template < typename K, typename V, typename A >
    friend class HashTableList;
    friend class HashTable< Key, Val, Alloc >;
    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, Alloc >&);
    friend std::ostream& operator<<<>(std::ostream&,
                                      const HashTableList< Key*, Val, Alloc >&);
    friend std::ostream& operator<<<>(std::ostream&,
                                      const HashTable< Key, Val, Alloc >&);
    friend std::ostream& operator<<<>(std::ostream&,
                                      const HashTable< Key*, Val, Alloc >&);

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

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

    Size __nb_elements{Size(0)};

    mutable BucketAllocator* __alloc_bucket;

    template < typename OtherAlloc >
    void __copy(const HashTableList< Key, Val, OtherAlloc >& from);
  };

  // ===========================================================================
  // ===                          GENERIC HASH TABLES                        ===
  // ===========================================================================
  template < typename Key,
             typename Val,
             typename Alloc = std::allocator< std::pair< Key, 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 allocator_type = Alloc;
    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 >;

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

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

    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, Alloc >& from);

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

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

    ~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;

    static const iterator& end4Statics();

    static const const_iterator& constEnd4Statics();

    static const iterator_safe& endSafe4Statics();

    static const const_iterator_safe& constEndSafe4Statics();

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

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

    template < typename OtherAlloc >
    HashTable< Key, Val, Alloc >&
       operator=(const HashTable< Key, Val, OtherAlloc >& from);

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

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


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

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


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

    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);

    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;

    void eraseAllVal(const Val& val);

    void clear();

    bool empty() const noexcept;

    template < typename Mount,
               typename OtherAlloc = typename Alloc::template rebind<
                  std::pair< Key, Mount > >::other >
    HashTable< Key, Mount, OtherAlloc > 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,
               typename OtherAlloc = typename Alloc::template rebind<
                  std::pair< Key, Mount > >::other >
    HashTable< Key, Mount, OtherAlloc > 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,
               typename OtherAlloc = typename Alloc::template rebind<
                  std::pair< Key, Mount > >::other >
    HashTable< Key, Mount, OtherAlloc > 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,
               typename OtherAlloc = typename Alloc::template rebind<
                  std::pair< Key, Mount > >::other >
    HashTable< Key, Mount, OtherAlloc > 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:
    template < typename K, typename V, typename A >
    friend class HashTable;
    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, Alloc >&);
    friend std::ostream& operator<<<>(std::ostream&                        s,
                                      const HashTable< Key*, Val, Alloc >& table);

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

    std::vector< HashTableList< Key, Val, Alloc > > __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;

    BucketAllocator __alloc;

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

    template < typename OtherAlloc >
    void __copy(const HashTable< Key, Val, OtherAlloc >& table);

    void __create(Size size);

    void __clearIterators();

    void __insert(Bucket* bucket);
  };


  // ===========================================================================
  // ===                   SAFE HASH TABLES CONST ITERATORS                  ===
  // ===========================================================================

  class HashTableIteratorStaticEnd {
    private:
    static const HashTableIterator< int, int >* __HashTableIterEnd;

    static const HashTableIteratorSafe< int, int >* __HashTableIterEndSafe;

    static const HashTableIterator< int, int >* end4Statics();

    static const HashTableConstIterator< int, int >* constEnd4Statics();

    static const HashTableIteratorSafe< int, int >* endSafe4Statics();

    static const HashTableConstIteratorSafe< int, int >* constEndSafe4Statics();

    template < typename Key, typename Val, typename Alloc >
    friend class HashTable;
  };


  // ===========================================================================
  // ===                   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;

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

    HashTableConstIteratorSafe();

    template < typename Alloc >
    HashTableConstIteratorSafe(const HashTable< Key, Val, Alloc >& tab);


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

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

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

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

    ~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;

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

    const value_type& operator*() const;


    protected:
    template < typename K, typename V, typename A >
    friend class HashTable;

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

    Size __index{Size(0)};

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

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

    HashTableBucket< Key, Val >* __getBucket() const noexcept;

    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;

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

    HashTableIteratorSafe();

    template < typename Alloc >
    HashTableIteratorSafe(const HashTable< Key, Val, Alloc >& tab);

    template < typename Alloc >
    HashTableIteratorSafe(const HashTable< Key, Val, Alloc >& 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;

    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;

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

    HashTableConstIterator() noexcept;

    template < typename Alloc >
    HashTableConstIterator(const HashTable< Key, Val, Alloc >& tab) noexcept;

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

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

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

    ~HashTableConstIterator() noexcept;

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

    const key_type& key() const;

    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;

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


    const value_type& operator*() const;


    protected:
    template < typename K, typename V, typename A >
    friend class HashTable;

    friend class HashTableConstIteratorSafe< Key, Val >;

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

    Size __index{Size(0)};

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

    typename HashTable< Key, Val >::Bucket* __getBucket() const noexcept;

    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;

    // ############################################################################
    // ############################################################################

    HashTableIterator() noexcept;

    template < typename Alloc >
    HashTableIterator(const HashTable< Key, Val, Alloc >& tab) noexcept;


    template < typename Alloc >
    HashTableIterator(const HashTable< Key, Val, Alloc >& 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;

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

    value_type& operator*();

    const value_type& operator*() const;

  };

}   // namespace gum


#ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
#  ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
#    ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
#      ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
extern template class gum::HashTable< int, int >;
#      endif
#    endif
#  endif
#endif
#ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
#  ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
#    ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
#      ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
extern template class gum::HashTable< int, std::string >;
#      endif
#    endif
#  endif
#endif
#ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
#  ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
#    ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
#      ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
extern template class gum::HashTable< std::string, std::string >;
#      endif
#    endif
#  endif
#endif
#ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
#  ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
#    ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
#      ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
extern template class gum::HashTable< std::string, int >;
#      endif
#    endif
#  endif
#endif


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

#endif   // GUM_HASHTABLE_H