trie.hpp

Go to the documentation of this file.

 
#if !defined(TETENGO_TRIE_TRIE_HPP)
#define TETENGO_TRIE_TRIE_HPP
 
#include <algorithm> // IWYU pragma: keep
#include <any>
#include <cstddef>
#include <functional>
#include <initializer_list>
#include <iterator>
#include <memory>
#include <string>
#include <string_view>
#include <type_traits>
#include <utility>
#include <vector>
 
#include <boost/core/noncopyable.hpp>
 
#include <tetengo/trie/default_serializer.hpp> // IWYU pragma: keep
#include <tetengo/trie/trie_iterator.hpp>
 
 
namespace tetengo::trie
{
    template <typename Object, typename>
    class default_serializer; // IWYU pragma: keep
 
    class double_array;
    class storage;
 

    class trie_impl : private boost::noncopyable
    {
    public:
        // types

        struct building_observer_set_type
        {
            std::function<void(const std::string_view& serialized_key)> adding;

            std::function<void()> done;
        };
 
 
        // static functions

        [[nodiscard]] static const building_observer_set_type& null_building_observer_set();

        [[nodiscard]] static std::size_t default_double_array_density_factor();
 
 
        // constructors and destructor

        trie_impl();

        trie_impl(
            std::vector<std::pair<std::string_view, std::any>> elements,
            const building_observer_set_type&                  building_observer_set,
            std::size_t                                        double_array_density_factor);

        trie_impl(
            std::vector<std::pair<std::string, std::any>> elements,
            const building_observer_set_type&             building_observer_set,
            std::size_t                                   double_array_density_factor);

        explicit trie_impl(std::unique_ptr<storage>&& p_storage);

        explicit trie_impl(std::unique_ptr<double_array>&& p_double_array);

        trie_impl(trie_impl&& another) noexcept;

        ~trie_impl();
 
 
        // functions

        [[nodiscard]] bool empty() const;

        [[nodiscard]] std::size_t size() const;

        [[nodiscard]] bool contains(const std::string_view& key) const;

        [[nodiscard]] const std::any* find(const std::string_view& key) const;

        [[nodiscard]] trie_iterator_impl begin() const;

        [[nodiscard]] trie_iterator_impl end() const;

        [[nodiscard]] std::unique_ptr<trie_impl> subtrie(const std::string_view& key_prefix) const;

        [[nodiscard]] const storage& get_storage() const;
 
 
    private:
        // types
 
        class impl;
 
 
        // variables
 
        std::unique_ptr<impl> m_p_impl;
    };
 

    template <typename Key, typename Value, typename KeySerializer = default_serializer<Key, void>>
    class trie : private boost::noncopyable
    {
    public:
        // types

        using key_type = Key;

        using value_type = Value;

        using key_serializer_type = KeySerializer;

        using iterator = trie_iterator<value_type>;

        using building_observer_set_type = trie_impl::building_observer_set_type;
 
 
        // static functions

        [[nodiscard]] static const building_observer_set_type& null_building_observer_set()
        {
            return trie_impl::null_building_observer_set();
        }

        [[nodiscard]] static std::size_t default_double_array_density_factor()
        {
            return trie_impl::default_double_array_density_factor();
        }
 
 
        // constructors and destructor

        explicit trie(const key_serializer_type& key_serializer = default_serializer<key_type, void>{ true }) :
        m_impl{},
        m_key_serializer{ key_serializer }
        {}

        explicit trie(
            std::initializer_list<std::pair<key_type, value_type>> elements,
            const key_serializer_type&        key_serializer = default_serializer<key_type, void>{ true },
            const building_observer_set_type& building_observer_set = null_building_observer_set(),
            std::size_t                       double_array_density_factor = default_double_array_density_factor()) :
        m_impl{ serialize_key<true>(std::begin(elements), std::end(elements), key_serializer),
                building_observer_set,
                double_array_density_factor },
        m_key_serializer{ key_serializer }
        {}

        template <typename InputIterator>
        trie(
            InputIterator                     first,
            InputIterator                     last,
            const key_serializer_type&        key_serializer = default_serializer<key_type, void>{ true },
            const building_observer_set_type& building_observer_set = null_building_observer_set(),
            std::size_t                       double_array_density_factor = default_double_array_density_factor()) :
        m_impl{ serialize_key<false>(first, last, key_serializer), building_observer_set, double_array_density_factor },
        m_key_serializer{ key_serializer }
        {}

        template <typename InputIterator>
        trie(
            std::move_iterator<InputIterator> first,
            std::move_iterator<InputIterator> last,
            const key_serializer_type&        key_serializer = default_serializer<key_type, void>{ true },
            const building_observer_set_type& building_observer_set = null_building_observer_set(),
            std::size_t                       double_array_density_factor = default_double_array_density_factor()) :
        m_impl{ serialize_key<true>(first, last, key_serializer), building_observer_set, double_array_density_factor },
        m_key_serializer{ key_serializer }
        {}

        explicit trie(
            std::unique_ptr<storage>&& p_storage,
            const key_serializer_type& key_serializer = default_serializer<key_type, void>{ true }) :
        m_impl{ std::move(p_storage) },
        m_key_serializer{ key_serializer }
        {}
 
 
        // functions

        [[nodiscard]] bool empty() const
        {
            return std::empty(m_impl);
        }

        [[nodiscard]] std::size_t size() const
        {
            return std::size(m_impl);
        }

        [[nodiscard]] bool contains(const key_type& key) const
        {
            if constexpr (std::is_same_v<key_type, std::string_view> || std::is_same_v<key_type, std::string>)
            {
                return m_impl.contains(m_key_serializer(key));
            }
            else
            {
                const auto serialized_key = m_key_serializer(key);
                return m_impl.contains(std::string_view{ std::data(serialized_key), std::size(serialized_key) });
            }
        }

        [[nodiscard]] const value_type* find(const key_type& key) const
        {
            const auto* const p_found = [this, &key]() {
                if constexpr (std::is_same_v<key_type, std::string_view> || std::is_same_v<key_type, std::string>)
                {
                    return m_impl.find(m_key_serializer(key));
                }
                else
                {
                    const auto serialized_key = m_key_serializer(key);
                    return m_impl.find(std::string_view{ std::data(serialized_key), std::size(serialized_key) });
                }
            }();
            if (!p_found)
            {
                return nullptr;
            }
            return std::any_cast<value_type>(p_found);
        }

        [[nodiscard]] iterator begin() const
        {
            return iterator{ std::move(std::begin(m_impl)) };
        }

        [[nodiscard]] iterator end() const
        {
            return iterator{ std::move(std::end(m_impl)) };
        }

        [[nodiscard]] std::unique_ptr<trie> subtrie(const key_type& key_prefix) const
        {
            auto p_trie_impl = [this, &key_prefix]() {
                if constexpr (std::is_same_v<key_type, std::string_view> || std::is_same_v<key_type, std::string>)
                {
                    return m_impl.subtrie(m_key_serializer(key_prefix));
                }
                else
                {
                    const auto serialized_key_prefix = m_key_serializer(key_prefix);
                    return m_impl.subtrie(
                        std::string_view{ std::data(serialized_key_prefix), std::size(serialized_key_prefix) });
                }
            }();
            if (!p_trie_impl)
            {
                return nullptr;
            }
            std::unique_ptr<trie> p_trie{ new trie{ std::move(p_trie_impl), m_key_serializer } };
            return p_trie;
        }

        [[nodiscard]] const storage& get_storage() const
        {
            return m_impl.get_storage();
        }
 
 
    private:
        // types
 
        using serialized_element_type = std::pair<
            std::conditional_t<std::is_same_v<key_type, std::string_view>, std::string_view, std::string>,
            std::any>;
 
 
        // static functions
 
        template <bool MoveValue, typename InputIterator>
        static std::vector<serialized_element_type>
        serialize_key(InputIterator first, InputIterator last, const key_serializer_type& key_serializer)
        {
            std::vector<serialized_element_type> serialized{};
            if constexpr (std::is_convertible_v<
                              typename std::iterator_traits<InputIterator>::iterator_category,
                              std::forward_iterator_tag>)
            {
                serialized.reserve(std::distance(first, last));
            }
            std::transform(first, last, std::back_inserter(serialized), [&key_serializer](auto&& value) {
                if constexpr (std::is_same_v<key_type, std::string_view> || std::is_same_v<key_type, std::string>)
                {
                    if constexpr (MoveValue)
                    {
                        return serialized_element_type{ key_serializer(value.first), std::move(value.second) };
                    }
                    else
                    {
                        return serialized_element_type{ key_serializer(value.first), value.second };
                    }
                }
                else
                {
                    const auto  serialized_key_vector = key_serializer(value.first);
                    std::string serialized_key{ std::begin(serialized_key_vector), std::end(serialized_key_vector) };
                    if constexpr (MoveValue)
                    {
                        return serialized_element_type{ std::move(serialized_key), std::move(value.second) };
                    }
                    else
                    {
                        return serialized_element_type{ std::move(serialized_key), value.second };
                    }
                }
            });
            return serialized;
        }
 
 
        // variables
 
        const trie_impl m_impl;
 
        const key_serializer_type m_key_serializer;
 
 
        // constructors
 
        explicit trie(std::unique_ptr<trie_impl>&& p_impl, const key_serializer_type& ker_serializer) :
        m_impl{ std::move(*p_impl) },
        m_key_serializer{ ker_serializer }
        {}
    };
 
 
}
 
 
#endif