_avl_common.hpp

Go to the documentation of this file.

 
 
#pragma once
 
#include <cstdint>
#include <memory>
#include <type_traits>
 
namespace datastructures {
namespace detail {
 
inline int avl_calc_max_height(size_t n) {
    int h = -1;
    for (size_t a = 0, b = 1, t = 0; b <= n; t = a + b + 1, a = b, b = t, ++h)
        ;
    return h;
}
 
using avl_sign_type = int8_t;
 
template <class TNode, class TAlloc>
using avl_node_allocator_type =
    std::allocator_traits<TAlloc>::template rebind_alloc<TNode>;
 
template <class TNode, class TAlloc>
using avl_node_ptr =
    std::allocator_traits<avl_node_allocator_type<TNode, TAlloc>>::pointer;
 
template <class TKey, class TItem, class TKeyComp, class TAlloc, class TNode>
class avl_tree_base {
  public:
    using key_type = TKey;
    using item_type = TItem;
    using comparator_type = TKeyComp;
    using allocator_type = TAlloc;
    using node_type = TNode;
 
    using node_alloc_type = avl_node_allocator_type<node_type, allocator_type>;
 
    using node_ptr = avl_node_ptr<node_type, allocator_type>;
 
    using node_alloc_traits = std::allocator_traits<node_alloc_type>;
 
    using size_type = typename node_alloc_traits::size_type;
 
  protected:
    using sign_type = avl_sign_type;
 
    comparator_type comparator;
    node_alloc_type allocator;
 
    // ==== Memory Management Functions ====
 
    template <class T>
        requires(!std::is_invocable_v<T>)
    node_ptr create_node(T &&item);
 
    template <class TCallback>
        requires std::is_invocable_v<TCallback>
    node_ptr create_node(TCallback &&callback);
 
    void destroy_node(node_ptr node) noexcept;
 
  public:
    avl_tree_base(const comparator_type &comparator,
                  const allocator_type &allocator)
        : comparator(comparator), allocator(allocator) {}
 
    avl_tree_base(comparator_type &&comparator,
                  allocator_type &&allocator) noexcept
        : comparator(std::move(comparator)), allocator(std::move(allocator)) {}
 
    virtual ~avl_tree_base() = 0;
 
    // ==== Allocator Getter ====
 
    inline node_alloc_type get_allocator() const noexcept {
        return allocator;
    }
 
    // ==== Access Operations ====
 
    [[nodiscard]] static node_ptr min_from(node_ptr node) noexcept;
 
    [[nodiscard]] static node_ptr max_from(node_ptr node) noexcept;
};
 
} // namespace detail
} // namespace datastructures
 
// ==== Implementation ====
 
#include "_avl_common.ipp"