bintree_splay.h

Go to the documentation of this file.

 
#ifndef CPPCOMMON_CONTAINERS_BINTREE_SPLAY_H
#define CPPCOMMON_CONTAINERS_BINTREE_SPLAY_H
 
#include "bintree.h"
 
namespace CppCommon {
 
 
template <typename T, typename TCompare = std::less<T>>
class BinTreeSplay
{
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<BinTreeSplay<T, TCompare>, T> iterator;
    typedef BinTreeConstIterator<BinTreeSplay<T, TCompare>, T> const_iterator;
    typedef BinTreeReverseIterator<BinTreeSplay<T, TCompare>, T> reverse_iterator;
    typedef BinTreeConstReverseIterator<BinTreeSplay<T, TCompare>, T> const_reverse_iterator;
 
    struct Node
    {
        T* parent;          
        T* left;            
        T* right;           
 
        Node() : parent(nullptr), left(nullptr), right(nullptr) {}
    };
 
    explicit BinTreeSplay(const TCompare& compare = TCompare()) noexcept
        : _compare(compare),
          _size(0),
          _root(nullptr)
    {}
    template <class InputIterator>
    BinTreeSplay(InputIterator first, InputIterator last, const TCompare& compare = TCompare()) noexcept;
    BinTreeSplay(const BinTreeSplay&) noexcept = default;
    BinTreeSplay(BinTreeSplay&&) noexcept = default;
    ~BinTreeSplay() noexcept = default;
 
    BinTreeSplay& operator=(const BinTreeSplay&) noexcept = default;
    BinTreeSplay& operator=(BinTreeSplay&&) 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(BinTreeSplay& bintree) noexcept;
    template <typename U, typename UCompare>
    friend void swap(BinTreeSplay<U, UCompare>& bintree1, BinTreeSplay<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;
 
    void Splay(T* x) const;
    void Zig(T* x) const;
    void ZigZig(T* x) const;
    void ZigZag(T* x) const;
};
 
} // namespace CppCommon
 
#include "bintree_splay.inl"
 
#endif // CPPCOMMON_CONTAINERS_BINTREE_SPLAY_H