_persistent_avl.ipp

Go to the documentation of this file.

 
 
#pragma once
 
#include "_persistent_avl.hpp"
 
#include <algorithm>
#include <stack>
#include <unordered_map>
#include <utility>
 
namespace datastructures {
namespace detail {
 
// ==== Constructors & Assigments ====
 
template <class TKey, class TItem, class TKeyComp, class TAlloc>
persistent_avl_tree<TKey, TItem, TKeyComp, TAlloc>::persistent_avl_tree(
    const typename base::comparator_type &comparator,
    const typename base::allocator_type &allocator)
    : base(comparator, allocator) {}
 
template <class TKey, class TItem, class TKeyComp, class TAlloc>
persistent_avl_tree<TKey, TItem, TKeyComp, TAlloc>::persistent_avl_tree(
    const persistent_avl_tree &other)
    : base(other.comparator, other.allocator), based_on(other.based_on) {
    clone_tree(other);
}
 
template <class TKey, class TItem, class TKeyComp, class TAlloc>
persistent_avl_tree<TKey, TItem, TKeyComp, TAlloc> &
persistent_avl_tree<TKey, TItem, TKeyComp, TAlloc>::operator=(
    const persistent_avl_tree &other) {
 
    this->comparator = other.comparator;
    this->allocator = other.allocator;
 
    based_on = other.based_on;
 
    clone_tree(other);
 
    return *this;
}
 
template <class TKey, class TItem, class TKeyComp, class TAlloc>
persistent_avl_tree<TKey, TItem, TKeyComp, TAlloc>::persistent_avl_tree(
    persistent_avl_tree &&other) noexcept
    : base(std::move(other.comparator), std::move(other.allocator)),
      roots(std::move(other.roots)), node_counts(std::move(other.node_counts)),
      based_on(std::move(other.based_on)) {}
 
template <class TKey, class TItem, class TKeyComp, class TAlloc>
persistent_avl_tree<TKey, TItem, TKeyComp, TAlloc> &
persistent_avl_tree<TKey, TItem, TKeyComp, TAlloc>::operator=(
    persistent_avl_tree &&other) noexcept {
    this->comparator = std::move(other.comparator);
    this->allocator = std::move(other.allocator);
 
    roots = std::move(other.roots);
    node_counts = std::move(other.node_counts);
    based_on = std::move(other.based_on);
 
    return *this;
}
 
template <class TKey, class TItem, class TKeyComp, class TAlloc>
persistent_avl_tree<TKey, TItem, TKeyComp,
                    TAlloc>::~persistent_avl_tree() noexcept {
    clear_all();
}
 
// ==== Helper Functions ====
 
template <class TKey, class TItem, class TKeyComp, class TAlloc>
void persistent_avl_tree<TKey, TItem, TKeyComp, TAlloc>::clone_tree(
    const persistent_avl_tree &other) {
 
    node_counts = other.node_counts;
 
    std::unordered_map<node_ptr, node_ptr> old_to_new;
    std::vector<std::pair<node_ptr, node_ptr *>> stack;
 
    roots.assign(other.roots.size(), nullptr);
 
    for (int version = 0; static_cast<size_t>(version) < other.roots.size();
         ++version) {
        node_ptr root = other.roots[version];
 
        if (root == nullptr) {
            continue;
        }
 
        if (root->version != version) {
            roots[version] = old_to_new.at(root);
            continue;
        }
 
        stack.clear();
        stack.push_back(std::make_pair(root, &roots[version]));
 
        while (!stack.empty()) {
            auto [node, location] = stack.back();
            stack.pop_back();
 
            node_ptr new_node = copy_node(node, version);
            old_to_new[node] = new_node;
            *location = new_node;
 
            if (node->left != nullptr) {
                if (node->left->version == version) {
                    stack.push_back(
                        std::make_pair(node->left, &new_node->left));
                }
                else {
                    // points to previous version
                    new_node->left = old_to_new.at(node->left);
                }
            }
            if (node->right != nullptr) {
                if (node->right->version == version) {
                    stack.push_back(
                        std::make_pair(node->right, &new_node->right));
                }
                else {
                    // points to previous version
                    new_node->right = old_to_new.at(node->right);
                }
            }
        }
    }
}
 
template <class TKey, class TItem, class TKeyComp, class TAlloc>
typename persistent_avl_tree<TKey, TItem, TKeyComp, TAlloc>::node_ptr
persistent_avl_tree<TKey, TItem, TKeyComp, TAlloc>::copy_node(
    node_ptr node, version_type version) {
    // copy the item
    typename base::item_type new_item = node->item;
    node_ptr new_node = this->create_node(new_item);
    new_node->sign = node->sign;
    new_node->left = node->left;
    new_node->right = node->right;
    new_node->version = version;
    return new_node;
}
 
template <class TKey, class TItem, class TKeyComp, class TAlloc>
template <std::invocable TCallback>
typename persistent_avl_tree<TKey, TItem, TKeyComp, TAlloc>::node_ptr
persistent_avl_tree<TKey, TItem, TKeyComp, TAlloc>::copy_node(
    node_ptr node, TCallback &&callback, version_type version) {
    node_ptr new_node = this->create_node(std::forward<TCallback>(callback));
    new_node->sign = node->sign;
    new_node->left = node->left;
    new_node->right = node->right;
    new_node->version = version;
    return new_node;
}
 
template <class TKey, class TItem, class TKeyComp, class TAlloc>
typename persistent_avl_tree<TKey, TItem, TKeyComp, TAlloc>::path_type
persistent_avl_tree<TKey, TItem, TKeyComp, TAlloc>::copy_path(
    const path_type &path, node_ptr new_child, version_type version) {
 
    path_type new_path;
 
    new_path.resize(path.size(), std::make_pair(nullptr, false));
 
    for (int i = path.size() - 1; i >= 0; --i) {
        auto [parent, child_is_right] = path[i];
 
        node_ptr new_parent = copy_node(parent, version);
 
        new_path[i] = std::make_pair(new_parent, child_is_right);
 
        if (child_is_right) {
            new_parent->right = new_child;
        }
        else {
            new_parent->left = new_child;
        }
 
        new_child = new_parent;
    }
 
    return new_path;
}
 
template <class TKey, class TItem, class TKeyComp, class TAlloc>
void persistent_avl_tree<TKey, TItem, TKeyComp, TAlloc>::rotate(
    node_ptr parent, node_ptr child, bool child_is_right, int parent_index,
    const path_type &parents) {
 
    if (child_is_right) {
        parent->right = child->left;
        child->left = parent;
    }
    else {
        parent->left = child->right;
        child->right = parent;
    }
 
    if (parent_index == 0) {
        // it's root
        roots.back() = child;
    }
    else {
        auto [grandpa, parent_is_right] = parents[parent_index - 1];
 
        if (parent_is_right) {
            grandpa->right = child;
        }
        else {
            grandpa->left = child;
        }
    }
}
 
template <class TKey, class TItem, class TKeyComp, class TAlloc>
void persistent_avl_tree<TKey, TItem, TKeyComp, TAlloc>::double_rotate(
    node_ptr parent, node_ptr child, node_ptr grand_child, bool child_is_right,
    int parent_index, const path_type &parents) {
 
    if (child_is_right) {
        parent->right = grand_child->left;
        child->left = grand_child->right;
        grand_child->left = parent;
        grand_child->right = child;
    }
    else {
        parent->left = grand_child->right;
        child->right = grand_child->left;
        grand_child->left = child;
        grand_child->right = parent;
    }
 
    if (parent_index == 0) {
        roots.back() = grand_child;
    }
    else {
        auto [grandpa, parent_is_right] = parents[parent_index - 1];
 
        if (parent_is_right) {
            grandpa->right = grand_child;
        }
        else {
            grandpa->left = grand_child;
        }
    }
}
 
// ==== Access Operations ====
 
template <class TKey, class TItem, class TKeyComp, class TAlloc>
std::vector<
    typename persistent_avl_tree<TKey, TItem, TKeyComp, TAlloc>::node_ptr>
persistent_avl_tree<TKey, TItem, TKeyComp, TAlloc>::list_in_order(
    version_type version) const noexcept {
    if (!is_valid_version(version)) {
        return std::vector<node_ptr>{};
    }
 
    std::vector<node_ptr> result;
    std::stack<node_ptr> stack;
    node_ptr current = roots[version];
 
    while (current != nullptr || !stack.empty()) {
        while (current != nullptr) {
            stack.push(current);
            current = current->left;
        }
 
        current = stack.top();
        stack.pop();
 
        result.push_back(current);
 
        current = current->right;
    }
 
    return result;
}
 
template <class TKey, class TItem, class TKeyComp, class TAlloc>
typename persistent_avl_tree<TKey, TItem, TKeyComp, TAlloc>::node_ptr
persistent_avl_tree<TKey, TItem, TKeyComp, TAlloc>::find(
    const key_type &key, version_type version) const noexcept {
 
    if (!is_valid_version(version)) {
        return nullptr;
    }
 
    node_ptr node = roots[version];
 
    while (true) {
        if (node == nullptr) {
            return nullptr;
        }
        if (this->comparator(key, node->item)) {
            node = node->left;
        }
        else if (this->comparator(node->item, key)) {
            node = node->right;
        }
        else {
            return node;
        }
    }
}
 
// ==== Update Operations ====
 
template <class TKey, class TItem, class TKeyComp, class TAlloc>
void persistent_avl_tree<TKey, TItem, TKeyComp, TAlloc>::clear_all() noexcept {
 
    for (version_type version = roots.size() - 1; version >= 0; --version) {
        node_ptr node = roots[version];
 
        while (node != nullptr && node->version == version) {
            if (node->left != nullptr && node->left->version == version) {
                node_ptr tmp = node->left;
                node->left = tmp->right;
                tmp->right = node;
                node = tmp;
            }
            else {
                node_ptr tmp = node->right;
                this->destroy_node(node);
                node = tmp;
            }
        }
    }
 
    roots.clear();
    node_counts.clear();
    based_on.clear();
}
 
template <class TKey, class TItem, class TKeyComp, class TAlloc>
template <std::invocable TCallback>
std::pair<typename persistent_avl_tree<TKey, TItem, TKeyComp, TAlloc>::node_ptr,
          bool>
persistent_avl_tree<TKey, TItem, TKeyComp, TAlloc>::insert(const key_type &key,
                                                           TCallback &&callback,
                                                           version_type version,
                                                           bool do_assign) {
 
    if (!is_valid_version(version)) {
        version = -1;
    }
 
    const version_type new_version = roots.size();
 
    if (version == -1 || roots[version] == nullptr) {
        const node_ptr new_root =
            this->create_node(std::forward<TCallback>(callback));
        new_root->version = new_version;
 
        roots.push_back(new_root);
        node_counts.push_back(1);
        based_on.push_back(version);
 
        return std::make_pair(new_root, true);
    }
 
    node_ptr node = roots[version];
    node_ptr new_node = nullptr;
    path_type parents;
 
    while (true) {
        if (this->comparator(key, node->item)) {
            parents.push_back(std::make_pair(node, false));
 
            if (node->left == nullptr) {
                new_node = this->create_node(std::forward<TCallback>(callback));
                new_node->version = new_version;
                break;
            }
 
            node = node->left;
        }
        else if (this->comparator(node->item, key)) {
            parents.push_back(std::make_pair(node, true));
 
            if (node->right == nullptr) {
                new_node = this->create_node(std::forward<TCallback>(callback));
                new_node->version = new_version;
                break;
            }
 
            node = node->right;
        }
        else {
            if (!do_assign) {
                return std::make_pair(node, false);
            }
 
            // copy the path and return the new node
 
            new_node =
                copy_node(node, std::forward<TCallback>(callback), new_version);
            new_node->version = new_version;
 
            path_type new_parents = copy_path(parents, new_node, new_version);
 
            if (new_parents.empty()) {
                roots.push_back(new_node);
            }
            else {
                auto [last_parent, attach_right] = new_parents.back();
                if (attach_right) {
                    last_parent->right = new_node;
                }
                else {
                    last_parent->left = new_node;
                }
                roots.push_back(new_parents[0].first);
            }
 
            // the node_count in this version didn't change
            node_counts.push_back(node_counts[version]);
            based_on.push_back(version);
 
            return std::make_pair(new_node, false);
        }
    }
 
    path_type new_parents = copy_path(parents, new_node, new_version);
 
    auto [last_parent, attach_right] = new_parents.back();
    if (attach_right) {
        last_parent->right = new_node;
    }
    else {
        last_parent->left = new_node;
    }
 
    roots.push_back(new_parents[0].first);
    node_counts.push_back(node_counts[version] + 1);
    based_on.push_back(version);
 
    // now we have a correctly copied path and the newly created node, but
    // the tree can be inbalanced.
 
    int parent_index = static_cast<int>(new_parents.size()) - 1;
 
    while (parent_index >= 0) {
        auto [parent, node_is_right] = new_parents[parent_index];
 
        const typename base::sign_type positive = node_is_right ? +1 : -1;
 
        if (parent->sign == -positive) {
            parent->sign = 0;
            break; // balanced itself
        }
 
        if (parent->sign == positive) {
            // we need to rotate
 
            if (node->sign == positive) {
                rotate(parent, node, node_is_right, parent_index, new_parents);
 
                parent->sign = 0;
                node->sign = 0;
            }
 
            else { // node->sign cannot be 0 here => must be -positive
                node_ptr child = (positive == 1) ? node->left : node->right;
 
                double_rotate(parent, node, child, node_is_right, parent_index,
                              new_parents);
 
                // correct the signs for parent, node and child
                if (child->sign == positive) {
                    node->sign = 0;
                    parent->sign = -positive;
                }
                else if (child->sign == -positive) {
                    node->sign = +positive;
                    parent->sign = 0;
                }
                else { // child is a new-born
                    node->sign = 0;
                    parent->sign = 0;
                }
                child->sign = 0;
            }
 
            break; // balanced
        }
 
        // parent->sign == 0
 
        parent->sign = positive;
        node = parent;
        --parent_index;
    }
 
    return std::make_pair(new_node, true);
}
 
template <class TKey, class TItem, class TKeyComp, class TAlloc>
std::pair<bool, typename persistent_avl_tree<TKey, TItem, TKeyComp,
                                             TAlloc>::version_type>
persistent_avl_tree<TKey, TItem, TKeyComp, TAlloc>::erase(
    const key_type &key, version_type version) noexcept {
 
    if (!is_valid_version(version)) {
        return std::make_pair(false, version);
    }
 
    if (roots[version] == nullptr) {
        return std::make_pair(false, version);
    }
 
    // find path
 
    node_ptr node = roots[version];
 
    path_type parents;
 
    while (true) {
        if (node == nullptr) {
            return std::make_pair(false, version);
        }
 
        if (this->comparator(key, node->item)) {
            parents.push_back(std::make_pair(node, false));
            node = node->left;
        }
        else if (this->comparator(node->item, key)) {
            parents.push_back(std::make_pair(node, true));
            node = node->right;
        }
        else {
            break;
        }
    }
 
 
    version_type new_version = roots.size();
 
    node_counts.push_back(node_counts[version] - 1);
    based_on.push_back(version);
 
    // copy the path with the replacement at the end
 
    path_type new_parents = copy_path(parents, nullptr, new_version);
 
    node_ptr *path_end_location;
 
    if (new_parents.empty()) {
        roots.push_back(nullptr);
        path_end_location = &roots.back();
    }
    else {
        roots.push_back(new_parents[0].first);
 
        auto [end, place_right] = new_parents.back();
 
        if (place_right) {
            path_end_location = &end->right;
        }
        else {
            path_end_location = &end->left;
        }
    }
 
    // find the replacement and the path to the replacement
 
    node_ptr left_child = node->left;
    node_ptr right_child = node->right;
 
    if (left_child != nullptr && right_child != nullptr) {
        node_ptr candidate = right_child;
 
        if (candidate->left == nullptr) {
            // candidate is successor
 
            node_ptr replacement = copy_node(candidate, new_version);
 
            replacement->left = left_child;
            replacement->sign = node->sign;
 
            *path_end_location = replacement;
 
            new_parents.push_back(std::make_pair(replacement, true));
        }
        else {
            path_type min_search_path;
            node_ptr min_candidate;
 
            while ((min_candidate = candidate->left) != nullptr) {
                min_search_path.push_back(std::make_pair(candidate, false));
                candidate = min_candidate;
            }
 
            path_type new_min_path =
                copy_path(min_search_path, candidate->right, new_version);
 
            node_ptr replacement = copy_node(candidate, new_version);
 
            replacement->left = left_child;
            replacement->right = new_min_path[0].first;
            replacement->sign = node->sign;
 
            *path_end_location = replacement;
 
            new_parents.push_back(std::make_pair(replacement, true));
 
            for (size_t i = 0; i < new_min_path.size(); ++i) {
                new_parents.push_back(new_min_path[i]);
            }
        }
    }
    else if (left_child != nullptr || right_child != nullptr) {
        node_ptr replacement;
 
        if (left_child != nullptr) {
            replacement = copy_node(left_child, new_version);
        }
        else {
            replacement = copy_node(right_child, new_version);
        }
 
        *path_end_location = replacement;
    }
 
    int parent_index = static_cast<int>(new_parents.size()) - 1;
 
    while (parent_index >= 0) {
        auto [parent, remove_was_right] = new_parents[parent_index];
 
        const typename base::sign_type positive = remove_was_right ? +1 : -1;
 
        if (parent->sign == 0) {
            parent->sign = -positive;
            return std::make_pair(true, new_version);
        }
        else if (parent->sign == positive) {
            parent->sign = 0;
            // continue propagating
        }
        else {
            // we need to rotate
 
            const bool child_is_right = !remove_was_right;
            node_ptr child_original =
                child_is_right ? parent->right : parent->left;
            node_ptr child = copy_node(child_original, new_version);
 
            // child != nullptr, because the parents sign is -positive
 
            if (child->sign == -positive) {
                rotate(parent, child, child_is_right, parent_index,
                       new_parents);
                child->sign = 0;
                parent->sign = 0;
                // continue propagating
            }
            else if (child->sign == 0) {
                rotate(parent, child, child_is_right, parent_index,
                       new_parents);
                child->sign = positive;
                parent->sign = -positive;
                return std::make_pair(true, new_version);
            }
            else {
                node_ptr grand_child_original =
                    child_is_right ? child->left : child->right;
                node_ptr grand_child =
                    copy_node(grand_child_original, new_version);
 
                double_rotate(parent, child, grand_child, child_is_right,
                              parent_index, new_parents);
 
                if (grand_child->sign == positive) {
                    parent->sign = 0;
                    child->sign = -positive;
                }
                else if (grand_child->sign == -positive) {
                    parent->sign = positive;
                    child->sign = 0;
                }
                else {
                    parent->sign = 0;
                    child->sign = 0;
                }
 
                grand_child->sign = 0;
 
                // continue propagating
            }
        }
 
        --parent_index;
    }
 
    return std::make_pair(true, new_version);
}
 
template <class TKey, class TItem, class TKeyComp, class TAlloc>
int persistent_avl_tree<TKey, TItem, TKeyComp, TAlloc>::get_height(
    version_type version) const {
 
    if (!is_valid_version(version)) {
        return -1;
    }
 
    node_ptr root = roots[version];
 
    if (root == nullptr) {
        return -1;
    }
 
    int height = 0;
    std::stack<std::pair<node_ptr, int>> stack;
    stack.emplace(root, 0);
 
    while (!stack.empty()) {
        auto [node, level] = stack.top();
        stack.pop();
 
        height = std::max(level, height);
 
        if (node->left != nullptr) {
            stack.emplace(node->left, level + 1);
        }
 
        if (node->right != nullptr) {
            stack.emplace(node->right, level + 1);
        }
    }
 
    return height;
}
 
} // namespace detail
} // namespace datastructures