_avl.hpp

Go to the documentation of this file.

 
 
#pragma once
 
#include "_avl_common.hpp"
 
#include <utility>
 
namespace datastructures {
namespace detail {
 
template <class TItem, class TAlloc>
struct avl_node {
    TItem item;
 
    avl_sign_type sign = 0;
 
    avl_node_ptr<avl_node, TAlloc> parent = nullptr;
 
    avl_node_ptr<avl_node, TAlloc> left = nullptr;
 
    avl_node_ptr<avl_node, TAlloc> right = nullptr;
};
 
template <class TKey, class TItem, class TKeyComp, class TAlloc>
class avl_tree : public avl_tree_base<TKey, TItem, TKeyComp, TAlloc,
                                      avl_node<TItem, TAlloc>> {
  private:
    using base =
        avl_tree_base<TKey, TItem, TKeyComp, TAlloc, avl_node<TItem, TAlloc>>;
 
  public:
    using node_ptr = typename base::node_ptr;
    using key_type = typename base::key_type;
 
  private:
    node_ptr root = nullptr;
 
    typename base::size_type node_count = 0;
 
    // ==== Helper Functions ====
 
    void clone_tree(const avl_tree &other);
 
    void rotate(node_ptr x) noexcept;
 
    inline bool is_leaf(node_ptr node) const noexcept {
        return node->right == nullptr && node->left == nullptr;
    }
 
    inline bool is_right_child(node_ptr node) const noexcept {
        return node->parent->right == node;
    }
 
  public:
    // ==== Constructors & Assigments ====
 
    avl_tree(const typename base::comparator_type &comparator,
             const typename base::allocator_type &allocator);
 
    avl_tree(const avl_tree &other);
 
    avl_tree &operator=(const avl_tree &other);
 
    avl_tree(avl_tree &&other) noexcept;
 
    avl_tree &operator=(avl_tree &&other) noexcept;
 
    ~avl_tree() noexcept;
 
    // ==== Access Operations ====
 
    [[nodiscard]] node_ptr get_root() const noexcept {
        return root;
    }
 
    [[nodiscard]] node_ptr find(const key_type &key) const noexcept;
 
    [[nodiscard]] node_ptr successor(node_ptr node) const noexcept;
 
    [[nodiscard]] node_ptr predecessor(node_ptr node) const noexcept;
 
    template <bool lower>
    [[nodiscard]] node_ptr bound(const key_type &key) const noexcept;
 
    // ==== Update Operations ====
 
    void clear() noexcept;
 
    template <class TInsertCallback, class TAssignCallback>
    std::pair<node_ptr, bool> insert(const key_type &key,
                                     TInsertCallback &&insert_callback,
                                     TAssignCallback &&assign_callback);
 
    template <class TInsertCallback>
    std::pair<node_ptr, bool> insert(const key_type &key,
                                     TInsertCallback &&insert_callback) {
        return insert(key, std::forward<TInsertCallback>(insert_callback),
                      [](typename base::item_type &) {});
    }
 
    void erase(node_ptr node) noexcept;
 
    // ==== Size ====
 
    [[nodiscard]] typename base::size_type size() const noexcept {
        return node_count;
    };
 
    [[nodiscard]] int get_height() const;
 
    // ==== Debug Functions ====
 
    std::string to_dot(bool print_invis) const;
};
 
} // namespace detail
} // namespace datastructures
 
// ==== Implementation ====
 
#include "_avl.ipp"