atom.hpp

#pragma once
 
#include <wordring/compatibility.hpp>
#include <wordring/trie/trie.hpp>
 
#include <string>
#include <string_view>
#include <type_traits>
 
namespace wordring
{
    template <typename String, typename Allocator>
    class basic_atom_set;
}
 
namespace wordring::detail
{
    template <typename String, typename Allocator = std::allocator<detail::trie_node>>
    class basic_atom : public wordring::stable_trie<typename String::value_type>::const_iterator
    {
        template <typename String1, typename Allocator1>
        friend class wordring::basic_atom_set;
 
        template <typename String1, typename Allocator1>
        friend bool operator==(basic_atom<String1, Allocator1> const&, basic_atom<String1, Allocator1> const&);
 
        template <typename String1, typename Allocator1>
        friend bool operator!=(basic_atom<String1, Allocator1> const&, basic_atom<String1, Allocator1> const&);
 
    protected:
        using base_type = typename stable_trie<typename String::value_type>::const_iterator;
 
        using typename base_type::container;
        using typename base_type::index_type;
        using typename base_type::node_type;
 
    public:
        using string_type = String;
        using label_type  = typename string_type::value_type;
 
        using base_type::operator bool;
        using base_type::operator !;
        using base_type::string;
 
    protected:
        using base_type::m_c;
        using base_type::m_index;
 
    protected:
        basic_atom(base_type it)
            : base_type(it)
        {
        }
 
        basic_atom(container const& c, index_type idx)
            : base_type(c, idx)
        {
        }
 
    public:
        basic_atom()
            : base_type()
        {
        }
 
        operator std::uint32_t() const
        {
            typename base_type::index_type idx = 0;
 
            if (m_index != 0)
            {
                node_type const* d = m_c->data();
 
                idx = (d + m_index)->m_base + base_type::null_value;
                assert(1 < idx && idx < base_type::limit());
                assert((d + idx)->m_check == m_index);
            }
 
            return idx;
        }
 
        operator string_type() const
        {
            string_type result;
            base_type::string(result);
            return result;
        }
 
        string_type& string(string_type& result) const
        {
            if(m_index != 0) base_type::string(result);
 
            return result;
        }
    };
 
    /* @brief 二つのアトムが等しいか調べる
 
        @par 例
        @code
            // アトム・コンテナを構築する
            std::vector<std::u32string> v{ U"あ", U"あう", U"い", U"うあい", U"うえ" };
            auto as = basic_atom_set<std::u32string>(v.begin(), v.end());
 
            // コンテナからアトムを取得する
            auto a1 = as.at(U"あ");
            auto a2 = as.at(U"あ");
 
            // 二つのアトムが等しいか調べる
            assert(a1 == a2);
        @endcode
    */
    template <typename String1, typename Allocator1>
    inline bool operator==(basic_atom<String1, Allocator1> const& lhs, basic_atom<String1, Allocator1> const& rhs)
    {
        assert(lhs.m_c == rhs.m_c);
 
        return lhs.m_index == rhs.m_index;
    }
 
    /* @brief 二つのアトムが等しくないか調べる
 
        @par 例
        @code
            // アトム・コンテナを構築する
            std::vector<std::u32string> v{ U"あ", U"あう", U"い", U"うあい", U"うえ" };
            auto as = basic_atom_set<std::u32string>(v.begin(), v.end());
 
            // コンテナからアトムを取得する
            auto a1 = as.at(U"あ");
            auto a2 = as.at(U"あう");
 
            // 二つのアトムが等しくないか調べる
            assert(a1 != a2);
        @endcode
    */
    template <typename String1, typename Allocator1>
    inline bool operator!=(basic_atom<String1, Allocator1> const& lhs, basic_atom<String1, Allocator1> const& rhs)
    {
        assert(lhs.m_c == rhs.m_c);
 
        return lhs.m_index != rhs.m_index;
    }
 
}
 
namespace wordring
{
    template <typename String, typename Allocator = std::allocator<detail::trie_node>>
    class basic_atom_set : public stable_trie<typename String::value_type>
    {
    protected:
        using base_type = stable_trie<typename String::value_type>;
 
    public:
        using allocator_type = Allocator;
 
        using key_type   = String;
        using value_type = detail::basic_atom<key_type>;
        using label_type = typename String::value_type;
 
        using typename base_type::serialize_iterator;
 
        using base_type::get_allocator;
        using base_type::size;
        using base_type::ibegin;
        using base_type::iend;
        using base_type::clear;
 
    protected:
        using base_type::null_value;
 
    public:
        basic_atom_set()
            : base_type()
        {
        }
 
        explicit basic_atom_set(allocator_type const& alloc)
            : base_type(alloc)
        {
        }
 
        template <typename InputIterator, typename std::enable_if_t<std::is_integral_v<typename std::iterator_traits<InputIterator>::value_type>, std::nullptr_t> = nullptr>
        basic_atom_set(InputIterator first, InputIterator last, allocator_type const& alloc = allocator_type())
            : base_type(alloc)
        {
            assign(first, last);
        }
 
        template <typename InputIterator, typename std::enable_if_t<std::negation_v<std::is_integral<typename std::iterator_traits<InputIterator>::value_type>>, std::nullptr_t> = nullptr>
        basic_atom_set(InputIterator first, InputIterator last, allocator_type const& alloc = allocator_type())
            : base_type(alloc)
        {
            assign(first, last);
        }
 
        basic_atom_set(std::initializer_list<detail::trie_node> il, allocator_type const& alloc = allocator_type())
            : base_type(il, alloc)
        {
        }
 
        template <typename InputIterator, typename std::enable_if_t<std::is_integral_v<typename std::iterator_traits<InputIterator>::value_type>, std::nullptr_t> = nullptr>
        void assign(InputIterator first, InputIterator last)
        {
            base_type::assign(first, last);
        }
 
        template <typename InputIterator, typename std::enable_if_t<std::negation_v<std::is_integral<typename std::iterator_traits<InputIterator>::value_type>>, std::nullptr_t> = nullptr>
        void assign(InputIterator first, InputIterator last)
        {
            while (first != last) insert(*first++);
        }
 
        // 要素アクセス --------------------------------------------------------
 
        value_type at(std::uint32_t id) const
        {
            typename base_type::node_type const* d = base_type::m_c.data();
 
            typename base_type::index_type idx = (d + id)->m_check;
            assert(1 < idx && idx < static_cast<int>(base_type::m_c.size()));
            assert((d + idx)->m_base + base_type::null_value == id);
 
            return value_type(base_type::m_c, idx);
        }
              
        template <typename InputIterator>
        value_type at(InputIterator first, InputIterator last) const
        {
            return base_type::find(first, last);
        }
 
        value_type at(std::basic_string_view<label_type> sv) const
        {
            return at(sv.begin(), sv.end());
        }
 
        value_type operator[](std::basic_string_view<label_type> sv)
        {
            value_type it = base_type::find(sv.begin(), sv.end());
            if (!it) it = insert(sv.begin(), sv.end());
            return it;
        }
        
        // 変更 ---------------------------------------------------------------
 
        template <typename InputIterator>
        value_type insert(InputIterator first, InputIterator last)
        {
            auto it = base_type::insert(first, last);
 
            typename base_type::index_type idx;
            
            if (it)
            {
                auto proxy = base_type::at(it, idx);
                proxy = idx;
            }
 
            return it;
        }
 
        value_type insert(std::basic_string_view<label_type> sv)
        {
            return insert(sv.begin(), sv.end());
        }
 
        void erase(std::uint32_t id)
        {
            if(id != 0) base_type::erase(static_cast<typename base_type::const_iterator>(at(id)));
        }
 
        template <typename InputIterator>
        void erase(InputIterator first, InputIterator last)
        {
            base_type::erase(base_type::find(first, last));
        }
 
        void erase(std::basic_string_view<label_type> sv)
        {
            erase(sv.begin(), sv.end());
        }
 
        // 検索 ---------------------------------------------------------------
 
        template <typename InputIterator>
        bool contains(InputIterator first, InputIterator last) const
        {
            return base_type::contains(first, last);
        }
 
        bool contains(std::basic_string_view<label_type> sv) const
        {
            return contains(sv.begin(), sv.end());
        }
    };
 
    template <typename Allocator = std::allocator<detail::trie_node>>
    using u8atom_set = basic_atom_set<std::u8string, Allocator>;
 
    template <typename Allocator = std::allocator<detail::trie_node>>
    using u16atom_set = basic_atom_set<std::u16string, Allocator>;
 
    template <typename Allocator = std::allocator<detail::trie_node>>
    using u32atom_set = basic_atom_set<std::u32string, Allocator>;
}