hashset.h

/*
 This Source Code Form is subject to the terms of the Mozilla Public
 License, v. 2.0. If a copy of the MPL was not distributed with this
 file, You can obtain one at http://mozilla.org/MPL/2.0/.
 \author Auberval Florian
*/
 
#pragma once
 
#include "../defines.h"
#include "./iteratorUtils.h"
 
namespace Ponca
{
    template <int N, typename T = int>
    struct HashDefaultFunctor
    {
        PONCA_MULTIARCH [[nodiscard]] static constexpr T hash(const int _x)
        {
            PONCA_MULTIARCH_STD_MATH(abs);
            return (abs(_x) * 2654435761u) % N;
        }
    };
 
    template <int N, typename T = int, template <int, typename> typename _HashFunctor = HashDefaultFunctor>
    class HashSet
    {
        static_assert(N > 0, "The capacity must be strictly positive");
        using HashFunctor = _HashFunctor<N, T>;
 
    protected:
        PONCA_MULTIARCH [[nodiscard]] inline bool search(int _value, int& _searchedIdx) const;
 
    public:
        constexpr PONCA_MULTIARCH HashSet() : m_data()
        {
            // Skip this initialization step if EMPTY is set to 0
            if constexpr (EMPTY != T(0))
            {
                Ponca::internal::fill(m_data, m_data + N, EMPTY);
            }
        }
 
        PONCA_MULTIARCH void clear();
 
        PONCA_MULTIARCH bool insert(int _value);
 
        PONCA_MULTIARCH [[nodiscard]] bool contains(int _value) const;
 
    private:
        static constexpr T OFFSET =
            T(1); //< Offsets the value when storing in m_data, to avoid mistaking the stored index value with EMPTY
        static constexpr T EMPTY = T(0); //< The flag to tell if the address is available or not (Should always be zero)
        T m_data[N];                     //< Where we store the elements in memory
    };
} // namespace Ponca
 
#include "./hashset.hpp"