stable_trie_base.hpp

#pragma once
 
#include <wordring/trie/stable_trie_base_iterator.hpp>
#include <wordring/trie/trie_heap.hpp>
 
#include <algorithm>
#include <cassert>
#include <climits>
#include <cstdint>
#include <istream>
#include <iterator>
#include <memory>
#include <ostream>
#include <stdexcept>
#include <type_traits>
#include <utility>
 
namespace wordring::detail
{
    // ------------------------------------------------------------------------
    // stable_trie_base
    // ------------------------------------------------------------------------
 
    template <typename Allocator = std::allocator<trie_node>>
    class stable_trie_base : public trie_heap<Allocator>
    {
        template <typename Allocator1>
        friend std::ostream& operator<<(std::ostream&, stable_trie_base<Allocator1> const&);
 
        template <typename Allocator1>
        friend std::istream& operator>>(std::istream&, stable_trie_base<Allocator1>&);
 
    protected:
        using base_type = trie_heap<Allocator>;
 
        using typename base_type::container;
        using typename base_type::label_vector;
        using typename base_type::index_type;
        using typename base_type::node_type;
 
        using base_type::null_value;
 
    public:
        using label_type      = typename base_type::label_type;
        using value_type      = std::uint32_t;
        using size_type       = typename container::size_type;
        using allocator_type  = Allocator;
        using reference       = trie_value_proxy;
        using const_reference = trie_value_proxy const;
        using const_iterator  = const_stable_trie_base_iterator<container const>;
 
    public:
        using typename base_type::serialize_iterator;
 
        using base_type::get_allocator;
        using base_type::ibegin;
        using base_type::iend;
        using base_type::clear;
 
    protected:
        using base_type::limit;
        using base_type::free;
        using base_type::has_child;
        using base_type::has_null;
        using base_type::at;
        using base_type::add;
 
        using base_type::m_c;
 
    public:
        stable_trie_base()
            : base_type()
        {
        }
 
        explicit stable_trie_base(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>
        stable_trie_base(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>
        stable_trie_base(InputIterator first, InputIterator last, allocator_type const& alloc = allocator_type())
            : base_type(alloc)
        {
            assign(first, last);
        }
 
        stable_trie_base(std::initializer_list<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)
        {
            clear();
            while (first != last)
            {
                insert(*first);
                ++first;
            }
        }
 
        // 要素アクセス --------------------------------------------------------
 
        reference at(const_iterator pos, index_type& idx)
        {
            node_type* d = m_c.data();
 
            idx = (d + pos.m_index)->m_base + null_value;
            assert(1 < idx && idx < limit());
 
            return reference(d + idx);
        }
 
        reference at(const_iterator pos)
        {
            index_type idx = 0;
            return at(pos, idx);
        }
 
        const_reference at(const_iterator pos) const
        {
            return const_cast<stable_trie_base*>(this)->at(pos);
        }
 
        template <typename InputIterator>
        reference at(InputIterator first, InputIterator last)
        {
            auto it = find(first, last);
            if (it == cend()) throw std::out_of_range("");
 
            return at(it);
        }
 
        template <typename InputIterator>
        const_reference at(InputIterator first, InputIterator last) const
        {
            return const_cast<stable_trie_base*>(this)->at(first, last);
        }
 
        template <typename Key>
        reference at(Key const& key)
        {
            return at(std::begin(key), std::end(key));
        }
 
        template <typename Key>
        const_reference at(Key const& key) const
        {
            return at(std::begin(key), std::end(key));
        }
 
        template <typename Key>
        reference operator[](Key const& key)
        {
            auto it = find(key);
            if (it == cend()) it = insert(key);
 
            node_type* d = m_c.data();
            index_type idx = (d + it.m_index)->m_base + null_value;
            assert(1 < idx && idx < limit());
 
            return reference(d + idx);
        }
 
        // イテレータ ----------------------------------------------------------
 
        const_iterator begin() const noexcept { return const_iterator(m_c, 1); }
 
        const_iterator cbegin() const noexcept { return const_iterator(m_c, 1); }
 
        const_iterator end() const noexcept { return const_iterator(m_c, 0); }
 
        const_iterator cend() const noexcept { return const_iterator(m_c, 0); }
 
        // 容量 ---------------------------------------------------------------
 
        bool empty() const noexcept { return size() == 0; }
 
        size_type size() const noexcept { return m_c.front().m_base; }
 
        static constexpr size_type max_size() noexcept
        {
            return std::numeric_limits<std::int32_t>::max() / sizeof(node_type);
        }
 
        // 変更 ---------------------------------------------------------------
 
        template <typename InputIterator>
        const_iterator insert(InputIterator first, InputIterator last, value_type value = 0)
        {
            assert(value <= static_cast<value_type>(std::numeric_limits<int32_t>::max()));
 
            if (first == last) return cend();
 
            index_type parent = 1;
 
            // 登録済み遷移をスキップする
            for (index_type idx = at(parent, static_cast<std::uint8_t>(*first)); idx != 0; idx = at(parent, static_cast<std::uint8_t>(*first)))
            {
                parent = idx;
                ++first;
                if (first == last) break;
            }
 
            if (!has_null(parent) || first != last)
            {
                // 新規文字列による遷移を追加
                while (first != last)
                {
                    std::uint16_t label = static_cast<std::uint8_t>(*first++);
                    index_type base = add(parent, label);
                    parent = base + label;
                }
                assert(parent != 1);
 
                // 終端の空遷移を追加
                index_type idx = add(parent, null_value) + null_value;
                (m_c.data() + idx)->m_base = -static_cast<index_type>(value);
 
                ++m_c.front().m_base;
            }
 
            return const_iterator(m_c, parent);
        }
 
        template <typename Key>
        const_iterator insert(Key const& key, value_type value = 0)
        {
            return insert(std::begin(key), std::end(key), value);
        }
 
        void erase(const_iterator pos)
        {
            index_type idx = pos.m_index;
            assert(0 <= idx && idx < limit());
 
            if (idx <= 1 || !has_null(idx)) return;
            assert(has_null(idx));
 
            index_type term = (m_c.data() + idx)->m_base + null_value;
            assert((m_c.data() + term)->m_check == idx);
            free(term);
 
            while (idx != 1 && !has_null(idx) && !has_child(idx))
            {
                index_type parent = (m_c.data() + idx)->m_check;
                free(idx);
                idx = parent;
            }
 
            --m_c.front().m_base;
            if (empty()) clear();
        }
 
        template <typename InputIterator>
        void erase(InputIterator first, InputIterator last)
        {
            erase(find(first, last));
        }
 
        template <typename Key>
        void erase(Key const& key)
        {
            erase(std::begin(key), std::end(key));
        }
 
        void swap(stable_trie_base& other)
        {
            base_type::swap(other);
        }
 
        // 検索 ---------------------------------------------------------------
 
    protected:
        template <typename InputIterator>
        auto lookup(InputIterator first, InputIterator last, std::uint32_t& i) const
        {
            assert(i == 0);
 
            index_type parent = 1;
 
            while (first != last)
            {
                std::uint16_t ch = static_cast<std::uint8_t>(*first);
                index_type idx = at(parent, ch);
                if (idx == 0) break;
                ++first;
                ++i;
                parent = idx;
                assert(1 <= parent && parent < limit());
            }
 
            return std::make_pair(const_iterator(m_c, parent), first);
        }
 
    public:
        template <typename InputIterator>
        auto lookup(InputIterator first, InputIterator last) const
        {
            std::uint32_t i = 0;
            return lookup(first, last, i);
        }
 
        template <typename Key>
        const_iterator search(Key const& key) const
        {
            auto it1 = std::begin(key);
            auto it2 = std::end(key);
 
            auto pair = lookup(it1, it2);
 
            return (pair.second == it2)
                ? pair.first
                : cend();
        }
 
        template <typename InputIterator>
        const_iterator find(InputIterator first, InputIterator last) const
        {
            auto pair = lookup(first, last);
 
            auto it = pair.second;
            index_type idx = pair.first.m_index;
 
            return (it == last && has_null(idx))
                ? pair.first
                : cend();
        }
 
        template <typename Key>
        const_iterator find(Key const& key) const
        {
            return find(std::begin(key), std::end(key));
        }
 
        template <typename InputIterator>
        bool contains(InputIterator first, InputIterator last) const
        {
            auto pair = lookup(first, last);
 
            auto it = pair.second;
            index_type idx = pair.first.m_index;
 
            return !(it != last || !has_null(idx));
        }
 
        template <typename Key>
        bool contains(Key const& key) const
        {
            return contains(std::begin(key), std::end(key));
        }
    };
 
    template <typename Allocator1>
    inline std::ostream& operator<<(std::ostream& os, stable_trie_base<Allocator1> const& trie)
    {
        typename stable_trie_base<Allocator1>::base_type const& heap = trie;
        return os << heap;
    }
 
    template <typename Allocator1>
    inline std::istream& operator>>(std::istream& is, stable_trie_base<Allocator1>& trie)
    {
        typename stable_trie_base<Allocator1>::base_type& heap = trie;
        return is >> heap;
    }
}