bintree_avl.h

Go to the documentation of this file.

 
#ifndef CPPCOMMON_CONTAINERS_BINTREE_AVL_H
#define CPPCOMMON_CONTAINERS_BINTREE_AVL_H
 
#include "bintree.h"
 
namespace CppCommon {
 
 
template <typename T, typename TCompare = std::less<T>>
class BinTreeAVL
{
public:
    // Standard container type definitions
    typedef T value_type;
    typedef TCompare value_compare;
    typedef value_type& reference;
    typedef const value_type& const_reference;
    typedef value_type* pointer;
    typedef const value_type* const_pointer;
    typedef ptrdiff_t difference_type;
    typedef size_t size_type;
    typedef BinTreeIterator<BinTreeAVL<T, TCompare>, T> iterator;
    typedef BinTreeConstIterator<BinTreeAVL<T, TCompare>, T> const_iterator;
    typedef BinTreeReverseIterator<BinTreeAVL<T, TCompare>, T> reverse_iterator;
    typedef BinTreeConstReverseIterator<BinTreeAVL<T, TCompare>, T> const_reverse_iterator;
 
    struct Node
    {
        T* parent;              
        T* left;                
        T* right;               
        signed char balance;    
 
        Node() : parent(nullptr), left(nullptr), right(nullptr), balance(0) {}
    };
 
    explicit BinTreeAVL(const TCompare& compare = TCompare()) noexcept
        : _compare(compare),
          _size(0),
          _root(nullptr)
    {}
    template <class InputIterator>
    BinTreeAVL(InputIterator first, InputIterator last, const TCompare& compare = TCompare()) noexcept;
    BinTreeAVL(const BinTreeAVL&) noexcept = default;
    BinTreeAVL(BinTreeAVL&&) noexcept = default;
    ~BinTreeAVL() noexcept = default;
 
    BinTreeAVL& operator=(const BinTreeAVL&) noexcept = default;
    BinTreeAVL& operator=(BinTreeAVL&&) noexcept = default;
 
    explicit operator bool() const noexcept { return !empty(); }
 
    bool empty() const noexcept { return _root == nullptr; }
 
    size_t size() const noexcept { return _size; }
 
    T* root() noexcept { return _root; }
    const T* root() const noexcept { return _root; }
    T* lowest() noexcept;
    const T* lowest() const noexcept;
    T* highest() noexcept;
    const T* highest() const noexcept;
 
    bool compare(const T& item1, const T& item2) const noexcept { return _compare(item1, item2); }
 
    iterator begin() noexcept;
    const_iterator begin() const noexcept;
    const_iterator cbegin() const noexcept;
    iterator end() noexcept;
    const_iterator end() const noexcept;
    const_iterator cend() const noexcept;
 
    reverse_iterator rbegin() noexcept;
    const_reverse_iterator rbegin() const noexcept;
    const_reverse_iterator crbegin() const noexcept;
    reverse_iterator rend() noexcept;
    const_reverse_iterator rend() const noexcept;
    const_reverse_iterator crend() const noexcept;
 
    iterator find(const T& item) noexcept;
    const_iterator find(const T& item) const noexcept;
 
    iterator lower_bound(const T& item) noexcept;
    const_iterator lower_bound(const T& item) const noexcept;
    iterator upper_bound(const T& item) noexcept;
    const_iterator upper_bound(const T& item) const noexcept;
 
 
    std::pair<iterator, bool> insert(T& item) noexcept;
 
    std::pair<iterator, bool> insert(const const_iterator& position, T& item) noexcept;
 
 
    T* erase(const T& item) noexcept;
 
    iterator erase(const iterator& it) noexcept;
 
    void clear() noexcept;
 
    void swap(BinTreeAVL& bintree) noexcept;
    template <typename U, typename UCompare>
    friend void swap(BinTreeAVL<U, UCompare>& bintree1, BinTreeAVL<U, UCompare>& bintree2) noexcept;
 
private:
    TCompare _compare;  // Binary tree compare
    size_t _size;       // Binary tree size
    T* _root;           // Binary tree root node
 
    const T* InternalLowest() const noexcept;
    const T* InternalHighest() const noexcept;
    const T* InternalFind(const T& item) const noexcept;
    const T* InternalLowerBound(const T& item) const noexcept;
    const T* InternalUpperBound(const T& item) const noexcept;
 
    static void RotateLeft(T* node);
    static void RotateRight(T* node);
    static void RotateLeftLeft(T* node);
    static void RotateRightRight(T* node);
    static void Unlink(T* node);
    static void Swap(T*& node1, T*& node2);
};
 
} // namespace CppCommon
 
#include "bintree_avl.inl"
 
#endif // CPPCOMMON_CONTAINERS_BINTREE_AVL_H