tree.hpp

#pragma once
 
#include <algorithm>
#include <array>
#include <iterator>
#include <limits>
#include <memory>
#include <type_traits>
#include <utility>
#include <vector>
 
namespace wordring
{
    template <typename T, typename Allocator>
    class tree;
}
 
namespace wordring::detail
{
    // ------------------------------------------------------------------------
    // tree_node
    // ------------------------------------------------------------------------
 
    template <typename T>
    struct tree_node
    {
        using index_type = std::uint32_t;
        using value_type = T;
 
        static constexpr index_type null_value = 0;
 
        index_type m_parent;
        index_type m_prev;
        index_type m_next;
        index_type m_child;
 
        value_type m_value;
    };
 
    // ------------------------------------------------------------------------
    // tree_node_iterator
    // ------------------------------------------------------------------------
 
    template <typename Container>
    class tree_node_iterator
    {
        template <typename T1, typename Allocator1>
        friend class wordring::tree;
 
        template <typename Container1>
        friend class tree_node_iterator;
 
        template <typename Container1, typename Container2>
        friend bool operator==(tree_node_iterator<Container1> const&, tree_node_iterator<Container2> const&);
 
        template <typename Container1, typename Container2>
        friend bool operator!=(tree_node_iterator<Container1> const&, tree_node_iterator<Container2> const&);
 
    protected:
        using container  = Container;
        using node_type  = typename container::value_type;
        using index_type = typename node_type::index_type;
 
        static constexpr index_type null_value = node_type::null_value;
 
    public:
        using value_type        = typename node_type::value_type;
        using difference_type   = std::ptrdiff_t;
        using reference         = value_type&;
        using const_reference   = value_type const&;
        using pointer           = value_type*;
        using const_pointer     = value_type const*;
        using iterator_category = std::bidirectional_iterator_tag;
 
        using reverse_iterator = std::reverse_iterator<tree_node_iterator<container>>;
 
    public:
        tree_node_iterator() noexcept
            : m_c(nullptr)
            , m_parent(null_value)
            , m_index(null_value)
        {
        }
 
    protected:
        tree_node_iterator(container& c, index_type parent, index_type idx) noexcept
            : m_c(std::addressof(c))
            , m_parent(parent)
            , m_index(idx)
        {
        }
 
    public:
        operator tree_node_iterator<container const>() const
        {
            tree_node_iterator<container const> result;
            result.m_c = m_c;
            result.m_parent = m_parent;
            result.m_index = m_index;
            return result;
        }
 
        auto& operator*() const
        {
            assert(m_index != null_value);
 
            return (m_c->data() + m_index)->m_value;
        }
 
        auto operator->() const
        {
            assert(m_index != null_value);
 
            return std::addressof((m_c->data() + m_index)->m_value);
        }
 
        tree_node_iterator& operator++()
        {
            assert(m_index != null_value);
 
            m_index = (m_c->data() + m_index)->m_next;
 
            return *this;
        }
 
        tree_node_iterator operator++(int)
        {
            assert(m_index != null_value);
 
            auto result = *this;
            operator++();
 
            return result;
        }
        
        /* @brief デクリメントする
        */
        tree_node_iterator& operator--()
        {
            auto const* d = m_c->data();
 
            if (m_index != 0) // prevがある場合(end以外はある)
            {
                assert(m_parent != 0 && (d + m_parent)->m_child != m_index); // 先頭をデクリメントしようとしている。
                m_index = (d + m_index)->m_prev;
            }
            else if (m_parent != 0) // prevが無い(endは無い)且つ根以外の場合
            {
                index_type child = (d + m_parent)->m_child; // begin
                m_index = (d + child)->m_prev; // endの前はtail
            }
            else // 根の終端
            {
                m_index = d->m_child;
                assert(m_index != 0); // 空のツリーで根をデクリメントしようとしている。
            }
 
            return *this;
        }
 
        /* @brief デクリメントする
        */
        tree_node_iterator operator--(int)
        {
            auto result = *this;
            operator--();
            return result;
        }
 
        tree_node_iterator begin() const
        {
            assert(m_index != null_value);
            return tree_node_iterator(*m_c, m_index, (m_c->data() + m_index)->m_child);
        }
 
        tree_node_iterator end() const
        {
            assert(m_index != null_value);
            return tree_node_iterator(*m_c, m_index, null_value);
        }
 
        reverse_iterator rbegin() const
        {
            return std::make_reverse_iterator(end());
        }
 
        reverse_iterator rend() const
        {
            return std::make_reverse_iterator(begin());
        }
 
        tree_node_iterator parent() const
        {
            auto* d = m_c->data();
 
            index_type p = m_parent;                                            // 親
            index_type pp = (p == null_value) ? null_value : (d + p)->m_parent; // 親の親
 
            return tree_node_iterator(*m_c, pp, p);
        }
 
    protected:
        container* m_c;
        index_type m_parent;
        index_type m_index;
    };
 
    template <typename Container1, typename Container2>
    inline bool operator==(tree_node_iterator<Container1> const& lhs, tree_node_iterator<Container2> const& rhs)
    {
        return !(lhs != rhs);
    }
 
    template <typename Container1, typename Container2>
    inline bool operator!=(tree_node_iterator<Container1> const& lhs, tree_node_iterator<Container2> const& rhs)
    {
#ifndef NDEBUG
        Container1 const* c1 = const_cast<Container1 const*>(lhs.m_c);
        Container2 const* c2 = const_cast<Container1 const*>(lhs.m_c);
        assert(c1 == c2 || c1 == nullptr || c2 == nullptr);
#endif
 
        return lhs.m_index != rhs.m_index || lhs.m_parent != rhs.m_parent;
    }
}
 
namespace wordring
{
    // ------------------------------------------------------------------------
    // tree
    // ------------------------------------------------------------------------
 
    template <typename T, typename Allocator = std::allocator<detail::tree_node<T>>>
    class tree
    {
        template <typename Container1>
        friend class detail::tree_node_iterator;
 
    protected:
        using node_type  = detail::tree_node<T>;
        using index_type = typename node_type::index_type;
        using container  = std::vector<node_type, Allocator>;
 
        static constexpr index_type null_value = node_type::null_value;
 
    public:
        // メンバ型
        using value_type      = T;
        using allocator_type  = Allocator;
        using size_type       = std::size_t;
        using difference_type = std::ptrdiff_t;
        using reference       = value_type&;
        using const_reference = value_type const&;
        using pointer         = value_type*;
        using const_pointer   = value_type const*;
        using iterator        = detail::tree_node_iterator<container>;
        using const_iterator  = detail::tree_node_iterator<container const>;
 
    public:
        tree()
            : m_c(1, node_type{})
        {
        }
 
        explicit tree(allocator_type const& alloc)
            : m_c(1, node_type{}, alloc)
        {
        }
 
        explicit tree(value_type const& value, allocator_type const& alloc = allocator_type())
            : m_c(1, node_type{}, alloc)
        {
            insert(begin(), value);
        }
 
        explicit tree(value_type&& value, allocator_type const& alloc = allocator_type())
            : m_c(1, node_type{}, alloc)
        {
            insert(begin(), std::move(value));
        }
 
        void assign(value_type const& value)
        {
            clear();
            insert(begin(), value);
        }
 
        void assign(value_type&& value)
        {
            clear();
            insert(begin(), std::move(value));
        }
 
        allocator_type get_allocator() const { return m_c.get_allocator(); }
 
        // 要素アクセス --------------------------------------------------------
 
        reference front()
        {
            assert(!empty());
            return *begin();
        }
 
        const_reference front() const
        {
            assert(!empty());
            return *cbegin();
        }
 
        reference back() { return front(); }
 
        const_reference back() const { return front(); }
 
        // イテレータ ----------------------------------------------------------
 
        iterator begin() noexcept { return iterator(m_c, 0, m_c[0].m_child); }
 
        const_iterator begin() const noexcept { return const_iterator(m_c, 0, m_c[0].m_child); }
 
        const_iterator cbegin() const noexcept { return begin(); }
 
        iterator end() noexcept { return iterator(m_c, 0, 0); }
 
        const_iterator end() const noexcept { return const_iterator(m_c, 0, 0); }
 
        const_iterator cend() const noexcept { return end(); }
 
        // 容量 ---------------------------------------------------------------
 
        bool empty() const noexcept { return size() == 0; }
 
        size_type size() const
        {
            size_type n = 0;
            const_iterator it1 = begin();
            const_iterator it2 = end();
            
            while (it1 != it2)
            {
                n += size(it1);
                ++it1;
            }
 
            return n;
        }
 
        size_type size(const_iterator pos) const
        {
            index_type idx = pos.m_index;
            if (idx == 0) return 0;
 
            index_type n = 0;
 
            node_type const* d = m_c.data();
 
            std::vector<index_type> stack(1, idx);
            while (!stack.empty())
            {
                index_type parent = stack.back();
                stack.pop_back();
                ++n;
 
                for (index_type i = (d + parent)->m_child; i != 0; i = (d + i)->m_next) stack.push_back(i);
            }
 
            return static_cast<std::make_unsigned_t<index_type>>(n);
        }
 
        size_type max_size() const noexcept { return m_c.max_size(); }
 
        // 変更 ---------------------------------------------------------------
 
        void clear() noexcept
        {
            m_c.clear();
            m_c.emplace_back(node_type{});
        }
 
        void swap(tree& other) { m_c.swap(other.m_c); }
 
        iterator insert(const_iterator pos, value_type&& value)
        {
            index_type idx = allocate(std::move(value));
 
            link(pos.m_parent, pos.m_index, idx);
 
            return iterator(m_c, pos.m_parent, idx);
        }
 
        iterator insert(const_iterator pos, value_type const& value)
        {
            return insert(pos, std::move(value_type(value)));
        }
 
        iterator insert(const_iterator pos, const_iterator sub)
        {
            std::vector<std::array<const_iterator, 2>> x; // 親スタック [pos, sub]
            std::vector<const_iterator> v;                // 探索スタック
 
            // 根を特別扱い
            iterator ret = insert(pos, *sub);
            x.push_back({ ret, sub });
            {
                auto it1 = sub.rbegin();
                auto it2 = sub.rend();
                while (it1 != it2) v.push_back((++it1).base());
            }
 
            // 根以外
            while (!v.empty())
            {
                const_iterator it = v.back();
                v.pop_back();
 
                if (it.parent() != x.back()[1]) x.pop_back();
                const_iterator p = insert(x.back()[0].end(), *it);
 
                if (it.begin() != it.end()) // 子がある
                {
                    auto it1 = it.rbegin();
                    auto it2 = it.rend();
                    while(it1 != it2)  v.push_back((++it1).base());
 
                    x.push_back({ p, it });
                }
            }
 
            return ret;
        }
 
        template <typename... Args>
        iterator emplace(const_iterator pos, Args&&... args)
        {
            return insert(pos, value_type(std::forward<Args>(args)...));
        }
 
        iterator move(const_iterator pos, const_iterator sub)
        {
            node_type* d = m_c.data();
 
            for (index_type i = pos.m_index; i != 0; i = (d + i)->m_parent)
            {
                if (i == sub.m_index) throw std::invalid_argument("");
            }
 
            unlink(sub.m_index);
            link(pos.m_parent, pos.m_index, sub.m_index);
 
            return iterator(m_c, pos.m_parent, sub.m_index);
        }
 
        iterator erase(const_iterator pos)
        {
            assert(pos.m_index != 0);
 
            node_type* d = m_c.data();
 
            index_type idx    = pos.m_index;
            index_type parent = pos.m_parent;
            index_type after  = (d + idx)->m_next;
 
            unlink(idx);
 
            // 解放
            std::vector<index_type> v(1, idx);
            while (!v.empty())
            {
                index_type i = v.back();
                v.pop_back();
                for (index_type j = (d + i)->m_child; j != 0; j = (d + j)->m_next) v.push_back(j); // i の子をスタックに追加
 
                free(i);
            }
 
            return iterator(m_c, parent, after);
        }
 
    protected:
        // 内部 ---------------------------------------------------------------
 
        index_type allocate(value_type&& val)
        {
            node_type* d = m_c.data();
            index_type idx = d->m_next;
 
            if (idx == 0)
            {
                idx = m_c.size();
                m_c.emplace_back(node_type{ 0, 0, 0, 0, std::move(val) });
            }
            else
            {
                index_type before = (d + idx)->m_prev;
                index_type after = (d + idx)->m_next;
                (d + idx)->m_value = std::move(val);
 
                (d + before)->m_next = after;
                (d + after)->m_prev = before;
            }
 
            return idx;
        }
 
        void free(index_type idx)
        {
            assert(idx < m_c.size());
 
            node_type* d = m_c.data();
 
            // idx を超えない最後の未使用ノードを探す
            index_type before = 0;
            for (index_type i = d->m_next; i != 0 && i < idx; i = (d + before)->m_next) before = i;
 
            // idx を超える最初の未使用ノードを探す
            index_type after = (d + before)->m_next;
 
            // リンクを張り替える
            (d + before)->m_next = idx;
 
            (d + idx)->m_prev = before;
            (d + idx)->m_next = after;
 
            (d + after)->m_prev = idx;
 
            // 使わない項目を0に初期化
            (d + idx)->m_parent = 0;
            (d + idx)->m_child = 0;
        }
 
        void link(index_type parent, index_type pos, index_type idx)
        {
            node_type* d = m_c.data();
 
            index_type child = (d + parent)->m_child;
            index_type after = pos;
            index_type before = 0;
            if (after != 0) before = (child != after) ? (d + after)->m_prev : 0;
            else before = (child != 0) ? (d + child)->m_prev : 0;
 
            if (before == 0)
            {
                (d + parent)->m_child = idx;
                index_type tail = (after != 0) ? (d + after)->m_prev : idx;
                (d + idx)->m_prev = tail;
            }
            else
            {
                (d + before)->m_next = idx;
                (d + idx)->m_prev = before;
            }
 
            if (after == 0)
            {
                (d + idx)->m_next = 0;
                if (before != 0) (d + child)->m_prev = idx;
            }
            else
            {
                (d + after)->m_prev = idx;
                (d + idx)->m_next = after;
            }
            (d + idx)->m_parent = parent;
        }
 
        void unlink(index_type idx)
        {
            assert(idx != 0);
 
            node_type* d = m_c.data();
 
            index_type parent = (d + idx)->m_parent;
            index_type child  = (d + parent)->m_child;
            index_type before = (child != idx) ? (d + idx)->m_prev : 0;
            index_type after  = (d + idx)->m_next;
 
            if (before == 0)
            {
                if (after == 0) (d + parent)->m_child = 0;
                else
                {
                    (d + parent)->m_child = after;
                    (d + after)->m_prev = (d + idx)->m_prev;
                }
            }
            else (d + before)->m_next = after;
 
            if (after == 0)
            {
                if (before != 0) (d + child)->m_prev = before;
            }
            else (d + after)->m_prev = (d + idx)->m_prev;
        }
 
    protected:
        container  m_c;
    };
}