_persistent_avl.hpp

Go to the documentation of this file.

 
 
#pragma once
 
#include "_avl_common.hpp"
 
#include <concepts>
#include <vector>
 
namespace datastructures {
namespace detail {
 
template <class TItem, class TAlloc, class TVersion>
struct persistent_avl_node {
    TItem item;
 
    avl_sign_type sign = 0;
 
    avl_node_ptr<persistent_avl_node, TAlloc> left = nullptr;
 
    avl_node_ptr<persistent_avl_node, TAlloc> right = nullptr;
 
    TVersion version;
};
 
using persistent_avl_version_type = int;
 
template <class TKey, class TItem, class TKeyComp, class TAlloc>
class persistent_avl_tree
    : public avl_tree_base<
          TKey, TItem, TKeyComp, TAlloc,
          persistent_avl_node<TItem, TAlloc, persistent_avl_version_type>> {
  public:
    using version_type = persistent_avl_version_type;
 
  private:
    using base =
        avl_tree_base<TKey, TItem, TKeyComp, TAlloc,
                      persistent_avl_node<TItem, TAlloc, version_type>>;
 
  public:
    using node_ptr = typename base::node_ptr;
    using key_type = typename base::key_type;
    using size_type = typename base::size_type;
 
  private:
    using path_type = std::vector<std::pair<node_ptr, bool>>;
 
    std::vector<node_ptr> roots;
 
    std::vector<size_type> node_counts;
 
    std::vector<version_type> based_on;
 
    // ==== Helper Function ====
 
    void clone_tree(const persistent_avl_tree &other);
 
    node_ptr copy_node(node_ptr node, version_type version);
 
    template <std::invocable TCallback>
    node_ptr copy_node(node_ptr node, TCallback &&callback,
                       version_type version);
 
    path_type copy_path(const path_type &path, node_ptr new_child,
                        version_type version);
 
    bool is_valid_version(version_type version) const noexcept {
        return 0 < version || static_cast<size_t>(version) <= roots.size();
    }
 
    void rotate(node_ptr parent, node_ptr child, bool child_is_right,
                int parent_index, const path_type &parents);
 
    void double_rotate(node_ptr parent, node_ptr child, node_ptr grand_child,
                       bool child_is_right, int parent_index,
                       const path_type &parents);
 
  public:
    // ==== Constructors & Assigments ====
 
    persistent_avl_tree(const typename base::comparator_type &comparator,
                        const typename base::allocator_type &allocator);
 
    persistent_avl_tree(const persistent_avl_tree &other);
 
    persistent_avl_tree &operator=(const persistent_avl_tree &other);
 
    persistent_avl_tree(persistent_avl_tree &&other) noexcept;
 
    persistent_avl_tree &operator=(persistent_avl_tree &&other) noexcept;
 
    ~persistent_avl_tree() noexcept;
 
    // ==== Access Operations ====
 
    [[nodiscard]] node_ptr get_root(version_type version) const noexcept {
        if (!is_valid_version(version)) {
            return nullptr;
        }
        return roots[version];
    }
 
    [[nodiscard]] std::vector<node_ptr>
    list_in_order(version_type version) const noexcept;
 
    [[nodiscard]] node_ptr find(const key_type &key,
                                version_type version) const noexcept;
 
    // ==== Update Operations ====
 
    void clear_all() noexcept;
 
    template <std::invocable TCallback>
    std::pair<node_ptr, bool> insert(const key_type &key, TCallback &&callback,
                                     version_type version, bool do_assign);
 
    std::pair<bool, version_type> erase(const key_type &key,
                                        version_type version) noexcept;
 
    // ==== Size ====
 
    [[nodiscard]] typename base::size_type
    size(version_type version) const noexcept {
        if (!is_valid_version(version)) {
            return 0;
        }
        return node_counts[version];
    }
 
    [[nodiscard]] int get_height(version_type version) const;
 
    // ==== Version ====
 
    [[nodiscard]] version_type get_current_version() const noexcept {
        return static_cast<version_type>(roots.size()) - 1;
    }
 
    [[nodiscard]] version_type
    get_preceding_version(version_type version) const {
        return based_on[version];
    }
};
 
} // namespace detail
} // namespace datastructures
 
// ==== Implementation ====
 
#include "_persistent_avl.ipp"