_avl_common.ipp

Go to the documentation of this file.

 
 
#pragma once
 
#include "_avl_common.hpp"
 
#include <memory>
 
namespace datastructures {
namespace detail {
 
// ==== Destructor ====
 
template <class TKey, class TItem, class TKeyComp, class TAlloc, class TNode>
avl_tree_base<TKey, TItem, TKeyComp, TAlloc, TNode>::~avl_tree_base() = default;
 
// ==== Memory Management Functions ====
 
template <class TKey, class TItem, class TKeyComp, class TAlloc, class TNode>
template <class T>
    requires(!std::is_invocable_v<T>)
typename avl_tree_base<TKey, TItem, TKeyComp, TAlloc, TNode>::node_ptr
avl_tree_base<TKey, TItem, TKeyComp, TAlloc, TNode>::create_node(T &&item) {
    auto node = node_alloc_traits::allocate(allocator, 1);
 
    try {
        node_alloc_traits::construct(allocator, std::to_address(node),
                                     std::forward<T>(item));
    } catch (...) {
        node_alloc_traits::deallocate(allocator, node, 1);
        throw;
    }
 
    return node;
}
 
template <class TKey, class TItem, class TKeyComp, class TAlloc, class TNode>
template <class TCallback>
    requires std::is_invocable_v<TCallback>
typename avl_tree_base<TKey, TItem, TKeyComp, TAlloc, TNode>::node_ptr
avl_tree_base<TKey, TItem, TKeyComp, TAlloc, TNode>::create_node(
    TCallback &&callback) {
    auto node = node_alloc_traits::allocate(allocator, 1);
 
    try {
        node_alloc_traits::construct(allocator, std::to_address(node),
                                     callback());
    } catch (...) {
        node_alloc_traits::deallocate(allocator, node, 1);
        throw;
    }
 
    return node;
}
 
template <class TKey, class TItem, class TKeyComp, class TAlloc, class TNode>
void avl_tree_base<TKey, TItem, TKeyComp, TAlloc, TNode>::destroy_node(
    node_ptr node) noexcept {
    node_alloc_traits::destroy(allocator, std::to_address(node));
    node_alloc_traits::deallocate(allocator, node, 1);
}
 
// ==== Access Operations ====
 
template <class TKey, class TItem, class TKeyComp, class TAlloc, class TNode>
avl_tree_base<TKey, TItem, TKeyComp, TAlloc, TNode>::node_ptr
avl_tree_base<TKey, TItem, TKeyComp, TAlloc, TNode>::min_from(
    node_ptr node) noexcept {
    if (node == nullptr) {
        return nullptr;
    }
    while (node->left != nullptr) {
        node = node->left;
    }
    return node;
}
 
template <class TKey, class TItem, class TKeyComp, class TAlloc, class TNode>
avl_tree_base<TKey, TItem, TKeyComp, TAlloc, TNode>::node_ptr
avl_tree_base<TKey, TItem, TKeyComp, TAlloc, TNode>::max_from(
    node_ptr node) noexcept {
    if (node == nullptr) {
        return nullptr;
    }
    while (node->right != nullptr) {
        node = node->right;
    }
    return node;
}
 
} // namespace detail
} // namespace datastructures