rbtree.hpp

#ifndef YGG_RBTREE_HPP
#define YGG_RBTREE_HPP

#include "bst.hpp"
#include "options.hpp"
#include "size_holder.hpp"
#include "tree_iterator.hpp"

#include <cassert>
#include <cstddef>
#include <set>
#include <type_traits>

// Only for debugging purposes
#include <fstream>
#include <vector>

namespace ygg {
namespace rbtree_internal {

enum class Color : unsigned char
{
    BLACK = 0,
    RED = 1
};

template <class Node, bool compress_color>
class ColorParentStorage;

template <class Node>
class ColorParentStorage<Node, true> {
public:
    void set_color(Color new_color) noexcept;
    void make_black() noexcept;
    void make_red() noexcept;

    Color get_color() const noexcept;
    void set_parent(Node * new_parent) noexcept;
    Node * get_parent() const noexcept;

    void swap_parent_with(ColorParentStorage<Node, true> & other) noexcept;
    void swap_color_with(ColorParentStorage<Node, true> & other) noexcept;

    static constexpr bool parent_reference = false;

private:
    Node * parent;
};

template <class Node>
class ColorParentStorage<Node, false> {
public:
    void set_color(Color new_color) noexcept;
    void make_black() noexcept;
    void make_red() noexcept;

    Color get_color() const noexcept;
    void set_parent(Node * new_parent) noexcept;
    Node *& get_parent() noexcept;
    Node * get_parent() const noexcept;

    void swap_parent_with(ColorParentStorage<Node, false> & other) noexcept;
    void swap_color_with(ColorParentStorage<Node, false> & other) noexcept;

    static constexpr bool parent_reference = true;

private:
    Node * parent = nullptr;
    Color color;
};

} // namespace rbtree_internal

template <class Node, class Options = DefaultOptions, class Tag = int>
class RBTreeNodeBase
    : public bst::BSTNodeBase<
          Node, Tag,
          rbtree_internal::ColorParentStorage<Node, Options::compress_color>> {
public:
    // TODO namespacing!

    void set_color(rbtree_internal::Color new_color) noexcept;
    void make_black() noexcept;
    void make_red() noexcept;
    rbtree_internal::Color get_color() const noexcept;

    void swap_parent_with(Node * other) noexcept;
    void swap_color_with(Node * other) noexcept;

private:
    using ActiveOptions = Options;
    friend class rbtree_internal::ColorParentStorage<Node,
                                                     Options::compress_color>;
};

class RBDefaultNodeTraits {
public:
    // TODO document
    template <class Node, class Tree>
    static void
    leaf_inserted(Node & node, Tree & t) noexcept
    {
        (void)node;
        (void)t;
    }

    template <class Node, class Tree>
    static void
    rotated_left(Node & node, Tree & t) noexcept
    {
        (void)node;
        (void)t;
    }

    template <class Node, class Tree>
    static void
    rotated_right(Node & node, Tree & t) noexcept
    {
        (void)node;
        (void)t;
    }

    template <class Node, class Tree>
    static void
    delete_leaf(Node & node, Tree & t) noexcept
    {
        (void)node;
        (void)t;
    }

    template <class Node, class Tree>
    static void
    deleted_below(Node & node, Tree & t) noexcept
    {
        (void)node;
        (void)t;
    }

    template <class Node, class Tree>
    static void
    swapped(Node & old_ancestor, Node & old_descendant, Tree & t) noexcept
    {
        (void)old_ancestor;
        (void)old_descendant;
        (void)t;
    }
};

template <class Node, class NodeTraits, class Options = DefaultOptions,
          class Tag = int, class Compare = ygg::utilities::flexible_less>
class RBTree
    : public bst::BinarySearchTree<
          Node, Options, Tag, Compare,
          rbtree_internal::ColorParentStorage<Node, Options::compress_color>>

{
public:
    using MyClass = RBTree<Node, NodeTraits, Options, Tag, Compare>;
    // Node Base
    using NB = RBTreeNodeBase<Node, Options, Tag>;
    using TB = bst::BinarySearchTree<
        Node, Options, Tag, Compare,
        rbtree_internal::ColorParentStorage<Node, Options::compress_color>>;
    static_assert(std::is_base_of<NB, Node>::value,
                  "Node class not properly derived from RBTreeNodeBase");

    RBTree() noexcept;

    RBTree(MyClass && other) noexcept;

    /*
     * Pull in classes from base tree
     */
    template <bool reverse>
    using iterator = typename TB::template iterator<reverse>;
    template <bool reverse>
    using const_iterator = typename TB::template const_iterator<reverse>;

    void insert(Node & node) CMP_NOEXCEPT(node);
    void insert(Node & node, Node & hint) CMP_NOEXCEPT(node);
    void insert(Node & node, iterator<false> hint) CMP_NOEXCEPT(node);

    // TODO document hinted inserts
    // TODO should order be preserved on hints?

    void remove(Node & node) CMP_NOEXCEPT(node);

    template <class Comparable>
    utilities::select_type_t<size_t, Node *, Options::stl_erase>
    erase(const Comparable & c) CMP_NOEXCEPT(c);

    template <bool reverse>
    utilities::select_type_t<const iterator<reverse>, Node *, Options::stl_erase>
    erase(const iterator<reverse> & it) CMP_NOEXCEPT(*it);

    // Mainly debugging methods
    void dbg_verify() const;
    bool verify_integrity() const;

protected:
    using Path = std::vector<Node *>;

    void remove_to_leaf(Node & node) CMP_NOEXCEPT(node);
    void fixup_after_delete(Node * parent, bool deleted_left) noexcept;

    void insert_leaf_base(Node & node, Node * start) CMP_NOEXCEPT(node);

    void fixup_after_insert(Node * node) noexcept;
    void rotate_left(Node * parent) noexcept;
    void rotate_right(Node * parent) noexcept;

    void swap_nodes(Node * n1, Node * n2, bool swap_colors = true) noexcept;
    void replace_node(Node * to_be_replaced, Node * replace_with) noexcept;
    void swap_unrelated_nodes(Node * n1, Node * n2) noexcept;
    void swap_neighbors(Node * parent, Node * child) noexcept;

    void verify_black_root() const;
    void verify_black_paths(const Node * node, unsigned int * path_length) const;
    void verify_red_black(const Node * node) const;
};

} // namespace ygg

#ifndef YGG_RBTREE_CPP
#include "rbtree.cpp"
#endif

#endif // YGG_RBTREE_HPP