_avl.ipp

Go to the documentation of this file.

 
 
#pragma once
 
#include "_avl.hpp" // for clangd
 
#include <format>
#include <sstream>
#include <stack>
#include <string>
#include <type_traits>
 
namespace datastructures {
namespace detail {
 
// ==== Constructors & Assigments ====
 
template <class TKey, class TItem, class TKeyComp, class TAlloc>
avl_tree<TKey, TItem, TKeyComp, TAlloc>::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>
avl_tree<TKey, TItem, TKeyComp, TAlloc>::avl_tree(const avl_tree &other)
    : base(other.comparator, other.allocator) {
    clone_tree(other);
}
 
template <class TKey, class TItem, class TKeyComp, class TAlloc>
avl_tree<TKey, TItem, TKeyComp, TAlloc> &
avl_tree<TKey, TItem, TKeyComp, TAlloc>::operator=(const avl_tree &other) {
    this->comparator = other.comparator;
    this->allocator = other.allocator;
 
    clone_tree(other);
 
    return *this;
}
 
template <class TKey, class TItem, class TKeyComp, class TAlloc>
avl_tree<TKey, TItem, TKeyComp, TAlloc>::avl_tree(avl_tree &&other) noexcept
    : base(std::move(other.comparator), std::move(other.allocator)) {
    root = other.root;
    this->node_count = other.node_count;
 
    other.root = nullptr;
    other.node_count = 0;
}
 
template <class TKey, class TItem, class TKeyComp, class TAlloc>
avl_tree<TKey, TItem, TKeyComp, TAlloc> &
avl_tree<TKey, TItem, TKeyComp, TAlloc>::operator=(avl_tree &&other) noexcept {
    this->comparator = std::move(other.comparator);
    this->allocator = std::move(other.allocator);
 
    root = other.root;
    this->node_count = other.node_count;
 
    other.root = nullptr;
    other.node_count = 0;
 
    return *this;
}
 
template <class TKey, class TItem, class TKeyComp, class TAlloc>
avl_tree<TKey, TItem, TKeyComp, TAlloc>::~avl_tree() noexcept {
    clear();
}
 
// ==== Helper Functions ====
 
template <class TKey, class TItem, class TKeyComp, class TAlloc>
void avl_tree<TKey, TItem, TKeyComp, TAlloc>::clone_tree(
    const avl_tree &other) {
    this->node_count = other.node_count;
 
    root = this->create_node(other.root->item);
    root->sign = other.root->sign;
 
    std::stack<std::pair<node_ptr, node_ptr>> stack;
 
    stack.push(std::make_pair(root, other.root));
 
    while (!stack.empty()) {
        auto [node, other_node] = stack.top();
        stack.pop();
 
        if (other_node->left != nullptr) {
            node->left = this->create_node(other_node->left->item);
            node->left->parent = node;
            node->left->sign = other_node->left->sign;
 
            stack.push(std::make_pair(node->left, other_node->left));
        }
 
        if (other_node->right != nullptr) {
            node->right = this->create_node(other_node->right->item);
            node->right->parent = node;
            node->right->sign = other_node->right->sign;
 
            stack.push(std::make_pair(node->right, other_node->right));
        }
    }
}
 
template <class TKey, class TItem, class TKeyComp, class TAlloc>
void avl_tree<TKey, TItem, TKeyComp, TAlloc>::rotate(node_ptr x) noexcept {
    node_ptr y = x->parent;
    node_ptr p = y->parent;
 
    // update the parent of the x,y pair
    if (p != nullptr) {
        if (p->left == y) {
            p->left = x;
        }
        else {
            p->right = x;
        }
    }
 
    if (y == root) {
        root = x;
    }
 
    // swap x and y
    node_ptr b;
 
    if (y->left == x) {
        b = x->right;
        y->left = b;
        x->right = y;
    }
    else {
        b = x->left;
        y->right = b;
        x->left = y;
    }
 
    // update parents
    x->parent = p;
    y->parent = x;
 
    if (b != nullptr) {
        b->parent = y;
    }
}
 
// ==== Access Operations ====
 
template <class TKey, class TItem, class TKeyComp, class TAlloc>
typename avl_tree<TKey, TItem, TKeyComp, TAlloc>::node_ptr
avl_tree<TKey, TItem, TKeyComp, TAlloc>::find(
    const key_type &key) const noexcept {
    node_ptr node = root;
 
    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;
        }
    }
}
 
template <class TKey, class TItem, class TKeyComp, class TAlloc>
typename avl_tree<TKey, TItem, TKeyComp, TAlloc>::node_ptr
avl_tree<TKey, TItem, TKeyComp, TAlloc>::successor(
    node_ptr node) const noexcept {
    if (node == nullptr) {
        return nullptr;
    }
 
    if (node->right == nullptr) {
        while (node->parent != nullptr) {
            if (!is_right_child(node)) {
                return node->parent;
            }
            node = node->parent;
        }
        return nullptr;
    }
 
    return this->min_from(node->right);
}
 
template <class TKey, class TItem, class TKeyComp, class TAlloc>
typename avl_tree<TKey, TItem, TKeyComp, TAlloc>::node_ptr
avl_tree<TKey, TItem, TKeyComp, TAlloc>::predecessor(
    node_ptr node) const noexcept {
    if (node == nullptr) {
        return nullptr;
    }
 
    if (node->left == nullptr) {
        while (node->parent != nullptr) {
            if (is_right_child(node)) {
                return node->parent;
            }
            node = node->parent;
        }
        return nullptr;
    }
 
    return this->max_from(node->left);
}
 
template <class TKey, class TItem, class TKeyComp, class TAlloc>
template <bool lower>
typename avl_tree<TKey, TItem, TKeyComp, TAlloc>::node_ptr
avl_tree<TKey, TItem, TKeyComp, TAlloc>::bound(
    const key_type &key) const noexcept {
    if (root == nullptr) {
        return nullptr;
    }
 
    node_ptr node = root;
 
    while (true) {
        if (this->comparator(key, node->item)) {
            if (node->left == nullptr) {
                return node;
            }
            node = node->left;
        }
        else if (this->comparator(node->item, key)) {
            if (node->right == nullptr) {
                return successor(node);
            }
            node = node->right;
        }
        else {
            if constexpr (lower) {
                return node;
            }
            else {
                return successor(node);
            }
        }
    }
}
 
// ==== Update Operations ====
 
template <class TKey, class TItem, class TKeyComp, class TAlloc>
void avl_tree<TKey, TItem, TKeyComp, TAlloc>::clear() noexcept {
    node_ptr node = root;
 
    while (node != nullptr) {
        if (node->left != nullptr) {
            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;
        }
    }
 
    root = nullptr;
    this->node_count = 0;
}
 
template <class TKey, class TItem, class TKeyComp, class TAlloc>
template <class TInsertCallback, class TAssignCallback>
std::pair<typename avl_tree<TKey, TItem, TKeyComp, TAlloc>::node_ptr, bool>
avl_tree<TKey, TItem, TKeyComp, TAlloc>::insert(
    const key_type &key, TInsertCallback &&insert_callback,
    TAssignCallback &&assign_callback) {
    if (root == nullptr) {
        root =
            this->create_node(std::forward<TInsertCallback>(insert_callback));
        ++this->node_count;
        return std::make_pair(root, true);
    }
 
    node_ptr node = root;
 
    node_ptr new_node = nullptr;
 
    while (true) {
        if (this->comparator(key, node->item)) {
            if (node->left == nullptr) {
                new_node = this->create_node(
                    std::forward<TInsertCallback>(insert_callback));
 
                node->left = new_node;
                node->left->parent = node;
                ++this->node_count;
 
                node = node->left;
                break; // propagate height change
            }
            node = node->left;
        }
        else if (this->comparator(node->item, key)) {
            if (node->right == nullptr) {
                new_node = this->create_node(
                    std::forward<TInsertCallback>(insert_callback));
 
                node->right = new_node;
                node->right->parent = node;
                ++this->node_count;
 
                node = node->right;
                break; // propagate height change
            }
            node = node->right;
        }
        else {
            assign_callback(node->item);
            return std::make_pair(node, false);
        }
    }
 
    // height changed
 
    while (node->parent != nullptr) {
        node_ptr parent = node->parent;
 
        const typename base::sign_type positive =
            (is_right_child(node)) ? +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(node);
                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;
                rotate(child);
                rotate(child);
 
                // 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;
    }
 
    return std::make_pair(new_node, true);
}
 
template <class TKey, class TItem, class TKeyComp, class TAlloc>
void avl_tree<TKey, TItem, TKeyComp, TAlloc>::erase(node_ptr node) noexcept {
    node_ptr replacement;
    node_ptr parent = node->parent;
 
    bool from_right = false;
 
    if (parent != nullptr) {
        from_right = is_right_child(node);
        // otherwise we wont need this flag
    }
 
    // also find and store the location from where to bubble the balancing
    // events
 
    node_ptr balance_from_node = parent;
    bool balance_from_right = from_right;
 
    if (is_leaf(node)) {
        replacement = nullptr;
    }
    else if (node->left == nullptr) {
        replacement = node->right;
 
        // we do not need to worry about the sign of the old node and we can
        // keep the old `balance_from_node`, since the replacement is always
        // a leaf, same in the next case
    }
    else if (node->right == nullptr) {
        replacement = node->left;
    }
    else {
        // both children exist
        replacement = this->min_from(node->right);
 
        if (replacement->parent != node) {
            node_ptr par = replacement->parent;
 
            // we need to balance from down there
            balance_from_node = replacement->parent;
            balance_from_right = false;
 
            par->left = replacement->right;
 
            // set new parent for the former right child of the new root
            if (par->left != nullptr) {
                par->left->parent = par;
            }
 
            replacement->right = node->right;
            replacement->right->parent = replacement;
        }
        else {
            // we actually need to balance from the replacement node itself
            // because it is now the parent of the deleted space
            balance_from_node = replacement;
            balance_from_right = true;
        }
 
        // don't forget to update the sign
        replacement->sign = node->sign;
 
        replacement->left = node->left;
        if (replacement->left != nullptr) {
            replacement->left->parent = replacement;
        }
    }
 
    // Free the node.
 
    this->destroy_node(node);
    --this->node_count;
 
    // Update the deleted node's parent
 
    if (parent == nullptr) {
        // the node was root
        root = replacement;
    }
    else if (from_right) {
        parent->right = replacement;
    }
    else {
        parent->left = replacement;
    }
 
    if (replacement != nullptr) {
        replacement->parent = parent;
    }
 
    // balance
 
    if (balance_from_node == nullptr) {
        return;
    }
 
    while (true) {
        node_ptr next_node = balance_from_node->parent;
        bool next_from_right = false;
        if (next_node != nullptr) {
            next_from_right = is_right_child(balance_from_node);
        }
 
        const typename base::sign_type positive = balance_from_right ? +1 : -1;
 
        if (balance_from_node->sign == 0) {
            balance_from_node->sign = -positive;
            // height didn't change
            return;
        }
        else if (balance_from_node->sign == -positive) {
            // we need to rotate
 
            node_ptr child = balance_from_right ? balance_from_node->left
                                                : balance_from_node->right;
 
            // child != nullptr, because it's parent's sign is -positive
 
            if (child->sign == -positive) {
                rotate(child);
                child->sign = 0;
                balance_from_node->sign = 0;
                // continue propagating
            }
            else if (child->sign == 0) {
                rotate(child);
                child->sign = positive;
                balance_from_node->sign = -positive;
                return;
            }
            else { // child->sign == positive
                node_ptr grand_child =
                    balance_from_right ? child->right : child->left;
 
                rotate(grand_child);
                rotate(grand_child);
 
                if (grand_child->sign == positive) {
                    balance_from_node->sign = 0;
                    child->sign = -positive;
                }
                else if (grand_child->sign == -positive) {
                    balance_from_node->sign = positive;
                    child->sign = 0;
                }
                else {
                    balance_from_node->sign = 0;
                    child->sign = 0;
                }
 
                grand_child->sign = 0;
 
                // continue propagating
            }
        }
        else { // balance_from_node->sign == positive
            balance_from_node->sign = 0;
            // continue propagating
        }
 
        if (next_node == nullptr) {
            return;
        }
 
        balance_from_node = next_node;
        balance_from_right = next_from_right;
    }
};
 
// ==== Size ====
 
template <class TKey, class TItem, class TKeyComp, class TAlloc>
int avl_tree<TKey, TItem, TKeyComp, TAlloc>::get_height() const {
    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;
}
 
// ==== Debug Function ====
 
template <class TKey, class TItem, class TKeyComp, class TAlloc>
std::string
avl_tree<TKey, TItem, TKeyComp, TAlloc>::to_dot(bool print_invis) const {
    auto get_repr = [](node_ptr node) -> std::string {
        if (node == nullptr) {
            return "NULL";
        }
 
        if constexpr (std::is_convertible_v<decltype(node->item),
                                            std::string>) {
            return std::string(node->item);
        }
        else if constexpr (requires { std::to_string(node->item); }) {
            return std::to_string(node->item);
        }
        else if constexpr (requires { std::format("{}", node->item); }) {
            return std::format("{}", node->item);
        }
        else {
            return std::format("{}", static_cast<const void *>(node));
        }
    };
 
    auto get_id = [](node_ptr node) -> std::string {
        return std::format("{}", static_cast<const void *>(node));
    };
 
    std::stringstream ss;
 
    ss << "digraph {\n";
 
    std::stack<node_ptr> s;
    if (root != nullptr) {
        s.push(root);
    }
 
    while (!s.empty()) {
        node_ptr node = s.top();
        s.pop();
 
        std::string sign = "0";
 
        if (node->sign == +1) {
            sign = "+1";
        }
        else if (node->sign == -1) {
            sign = "-1";
        }
 
        ss << "    " << get_id(node) << " [label=\"" << get_repr(node) << "\\n"
           << sign << "\"";
 
        if (node == root) {
            ss << ", style=filled, fillcolor=lightblue";
        }
 
        ss << "];\n";
 
        if (node->left != nullptr) {
            ss << "    " << get_id(node) << " -> " << get_id(node->left)
               << ";\n";
            s.push(node->left);
        }
        else if (print_invis) {
            ss << "    inv" << get_id(node) << "L [style=invis];\n";
            ss << "    " << get_id(node) << " -> inv" << get_id(node)
               << "L [style=invis];\n";
        }
        if (node->right != nullptr) {
            ss << "    " << get_id(node) << " -> " << get_id(node->right)
               << ";\n";
            s.push(node->right);
        }
        else if (print_invis) {
            ss << "    inv" << get_id(node) << "R [style=invis];\n";
            ss << "    " << get_id(node) << " -> inv" << get_id(node)
               << "R [style=invis];\n";
        }
    }
 
    ss << "}\n\n";
 
    return ss.str();
}
 
} // namespace detail
} // namespace datastructures