wbtree.hpp

#ifndef YGG_WBTREE_HPP
#define YGG_WBTREE_HPP

#include "bst.hpp"
#include "debug.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 {
template <class Node, class Options = DefaultOptions, class Tag = int>
class WBTreeNodeBase : public bst::BSTNodeBase<Node, Tag> {
public:
    // TODO namespacing!
    void swap_parent_with(Node * other) noexcept;
    size_t _wbt_size;
};

class WBDefaultNodeTraits {
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
    splice_out_left_knee(Node & node, Tree & t) noexcept
    {
        (void)node;
        (void)t;
    }

    template <class Node, class Tree>
    static void
    splice_out_right_knee(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 WBTree : public bst::BinarySearchTree<Node, Options, Tag, Compare> {
public:
    using MyClass = WBTree<Node, NodeTraits, Options, Tag, Compare>;
    // Node Base
    using NB = WBTreeNodeBase<Node, Options, Tag>;
    using TB = bst::BinarySearchTree<Node, Options, Tag, Compare>;
    static_assert(std::is_base_of<NB, Node>::value,
                  "Node class not properly derived from WBTreeNodeBase");

    WBTree() noexcept;

    WBTree(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);

    // TODO document
    void insert_left_leaning(Node & node) CMP_NOEXCEPT(node);
    void insert_right_leaning(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);

    // TODO document
    template <class Comparable>
    Node * erase_optimistic(const Comparable & c) CMP_NOEXCEPT(c);

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

    // Mainly debugging methods
    bool verify_integrity() const;

    /* Debugging methods */
    // TODO only here for compatibility with the Zip Tree
    void dbg_verify() const;
    size_t dbg_count_violations(std::vector<size_t> * depths = nullptr,
                                std::vector<size_t> * amounts = nullptr) const;
    void dbg_assert_balance_at(Node * n) const;

protected:
    template <bool fix_upward>
    void remove_onepass(Node & node) CMP_NOEXCEPT(node);
    void remove_to_leaf(Node & node) CMP_NOEXCEPT(node);
    void fixup_after_delete(Node * parent, bool deleted_left)
        CMP_NOEXCEPT(*parent);

    template <bool call_fixup>
    bool remove_swap_and_remove_left(Node * node, Node * replacement)
        CMP_NOEXCEPT(*node);
    template <bool call_fixup>
    bool remove_swap_and_remove_right(Node * node, Node * replacement)
        CMP_NOEXCEPT(*node);
    template <bool call_fixup>
    void remove_leaf(Node * node) CMP_NOEXCEPT(*node);

    template <bool on_equality_prefer_left>
    void insert_leaf_base_twopass(Node & node, Node * start) CMP_NOEXCEPT(node);
    void fixup_after_insert_twopass(Node * node) CMP_NOEXCEPT(*node);

    template <bool on_equality_prefer_left>
    void insert_leaf_onepass(Node & node) CMP_NOEXCEPT(node);

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

    void swap_nodes(Node * n1, Node * n2) 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_sizes() const;
};

} // namespace ygg

#ifndef YGG_WBTREE_CPP
#include "wbtree.cpp"
#endif

#endif // YGG_WBTREE_HPP