hashFunc.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_HASH_FUNC_H
#define GUM_HASH_FUNC_H
 
// utility provides the std::pair <> template
#include <climits>
#include <memory>
#include <string>
#include <utility>
 
#include <agrum/agrum.h>
 
#include <string_view>
#include <type_traits>
 
namespace gum {

  unsigned int _hashTableLog2_(const Size nb);

  struct HashFuncConst {
    static constexpr Size gold
        = sizeof(Size) == 4 ? Size(2654435769UL) : Size(11400714819323198486UL);
    static constexpr Size pi      // pi / 4
        = sizeof(Size) == 4 ? Size(3373259426UL) : Size(14488038916154245684UL);
    static constexpr Size sqrt3   // sqrt(3) / 2
        = sizeof(Size) == 4 ? Size(3719550786UL) : Size(15975348984942515101UL);
    static constexpr Size mask
        = sizeof(Size) == 4 ? Size(4294967295UL) : Size(18446744073709551615UL);
    static constexpr Size offset = sizeof(Size) == 4 ? Size(32) : Size(64);
  };
 
  // ===========================================================================
  // ===             BASE CLASS SHARED BY ALL THE HASH FUNCTIONS             ===
  // ===========================================================================
  template < typename Key >
  class HashFuncBase {
    public:
    void resize(const Size new_size);

    Size size() const;

    virtual Size operator()(const Key& key) const = 0;
 
    protected:
    Size hash_size_{Size(0)};

    unsigned int hash_log2_size_{0};

    Size hash_mask_{Size(0)};

    unsigned int right_shift_{0};
  };
 
  // ===========================================================================
  // ===                GENERIC HASH FUNCTIONS FOR SIMPLE TYPES              ===
  // ===========================================================================

  template < typename Key >
  class HashFuncSmallKey: public HashFuncBase< Key > {
    public:
    HashFuncSmallKey();

    static Size castToSize(const Key& key);

 
    private:   // best attempt to get rid of overloaded virtual warnings
    using HashFuncBase< Key >::operator();
 
    public:
    Size operator()(const Key& key) const final;
  };

  template < typename Key >
  class HashFuncSmallCastKey: public HashFuncBase< Key > {
    public:
    HashFuncSmallCastKey();

    static Size castToSize(const Key& key);

    Size operator()(const Key& key) const final;
 
    protected:
    static constexpr Size small_key_mask_{(Size(1) << (8 * sizeof(Key))) - Size(1)};
  };

  template < typename Key >
  class HashFuncMediumCastKey: public HashFuncBase< Key > {
    public:
    HashFuncMediumCastKey();

    static Size castToSize(const Key& key);

    Size operator()(const Key& key) const final;
  };

  template < typename Key >
  class HashFuncLargeCastKey: public HashFuncBase< Key > {
    public:
    HashFuncLargeCastKey();

    static Size castToSize(const Key& key);

    virtual Size operator()(const Key& key) const final;
  };

  template < typename Key >
  struct HashFuncCastKey {
    using type = typename std::conditional<
        sizeof(Key) <= sizeof(Size) && std::is_integral< Key >::value,
        HashFuncSmallKey< Key >,
        typename std::conditional<
            sizeof(Key) < sizeof(Size),
            HashFuncSmallCastKey< Key >,
            typename std::conditional< sizeof(Key) == sizeof(Size),
                                       HashFuncMediumCastKey< Key >,
                                       typename std::conditional< sizeof(Key) == 2 * sizeof(Size),
                                                                  HashFuncLargeCastKey< Key >,
                                                                  void >::type >::type >::type >::
        type;
  };
 
  // ===========================================================================
  // ===   CLASSES FOR NOT DEFINING SEVERAL TIMES THE SAME HASH FUNCTIONS    ===
  // ===========================================================================
 
  // a dummy hash type
  template < typename Key >
  class dummyHash {};
 
  // the general type of the recursive type to select the appropriate hash function
  template < typename... >
  struct HashFuncConditionalType;
 
  // base of the recursive type to select the appropriate hash function
  template < typename Key >
  struct HashFuncConditionalType< Key > {
    using type = Key;
  };
 
  // base of the recursive type to select the appropriate hash function
  template < typename KEY_TYPE, typename TYPE >
  struct HashFuncConditionalType< KEY_TYPE, TYPE > {
    using type = typename std::
        conditional< std::is_same< KEY_TYPE, TYPE >::value, dummyHash< KEY_TYPE >, KEY_TYPE >::type;
  };

  template < typename KEY_TYPE, typename FIRST_TYPE, typename... OTHER_TYPES >
  struct HashFuncConditionalType< KEY_TYPE, FIRST_TYPE, OTHER_TYPES... > {
    using type = typename std::conditional<
        std::is_same< KEY_TYPE, FIRST_TYPE >::value,
        dummyHash< KEY_TYPE >,
        typename HashFuncConditionalType< KEY_TYPE, OTHER_TYPES... >::type >::type;
  };
 
  // ===========================================================================
  // ===                  HASH FUNCTIONS FOR PAIRS OF KEYS                   ===
  // ===========================================================================

  template < typename key >
  class HashFunc {};

  template < typename Key1, typename Key2 >
  class HashFunc< std::pair< Key1, Key2 > >: public HashFuncBase< std::pair< Key1, Key2 > > {
    public:
    static Size castToSize(const std::pair< Key1, Key2 >& key);

    Size operator()(const std::pair< Key1, Key2 >& key) const final;
  };
 
  // ===========================================================================
  // ===                      WIDELY USED HASH FUNCTIONS                     ===
  // ===========================================================================

  template <>
  class HashFunc< bool >: public HashFuncSmallKey< bool > {};

  template <>
  class HashFunc< int >: public HashFuncSmallKey< int > {};

  template <>
  class HashFunc< unsigned int >: public HashFuncSmallKey< unsigned int > {};

  template <>
  class HashFunc< long >: public HashFuncSmallKey< long > {};

  template <>
  class HashFunc< unsigned long >: public HashFuncSmallKey< unsigned long > {};

  template <>
  class HashFunc<
      typename HashFuncConditionalType< std::size_t, unsigned long, unsigned int, long, int >::
          type >: public HashFuncCastKey< std::size_t >::type {};

  template <>
  class HashFunc< float >: public HashFuncCastKey< float >::type {};

  template <>
  class HashFunc< double >: public HashFuncCastKey< double >::type {};

  template < typename Type >
  class HashFunc< Type* >: public HashFuncCastKey< Type* >::type {};

  template <>
  class HashFunc< std::string >: public HashFuncBase< std::string > {
    public:
    static Size castToSize(const std::string& key);

    static Size castToSize(std::string_view key);

    Size operator()(const std::string& key) const final;

    Size operator()(std::string_view key) const;
  };

  template <>
  class HashFunc< std::vector< Idx > >: public HashFuncBase< std::vector< Idx > > {
    public:
    static Size castToSize(const std::vector< Idx >& key);

    Size operator()(const std::vector< Idx >& key) const final;
  };

  template <>
  class HashFunc< Debug >: public HashFuncBase< Debug > {
    public:
    static Size castToSize(const Debug& key);

    Size operator()(const Debug& key) const final;
 
    template < typename OTHER_KEY >
    friend class HashFunc;
  };

  template < typename Type >
  class HashFunc< std::shared_ptr< Type > >: public HashFuncBase< std::shared_ptr< Type > > {
    public:
    static Size castToSize(const std::shared_ptr< Type >& key);

    Size operator()(const std::shared_ptr< Type >& key) const final;
  };
 
} /* namespace gum */

#ifndef GUM_NO_INLINE
#  include <agrum/base/core/hashFunc_inl.h>
#endif /* GUM_NO_INLINE */

#include <agrum/base/core/hashFunc_tpl.h>
 
#endif /* GUM_HASHFUNC_H */