dynamic_segment_tree.hpp

//
// Created by lukas on 10.11.17.
//

#ifndef YGG_DYNAMIC_SEGMENT_TREE_HPP
#define YGG_DYNAMIC_SEGMENT_TREE_HPP

#include "debug.hpp"
#include "options.hpp"
#include "rbtree.hpp"
#include "size_holder.hpp"
#include "util.hpp"
#include "wbtree.hpp"
#include "ziptree.hpp"

namespace ygg {

// Forwards
template <class Node, class NodeTraits, class Combiners, class Options,
          class TreeSelector, class Tag>
class DynamicSegmentTree;

namespace dyn_segtree_internal {

/* Interface for when modification sequences should be stored for benchmarking
 * purposes */
template <class InnerNode, class KeyT_in>
class InnerSequenceInterface {
public:
    using KeyT = KeyT_in;

    static KeyT_in
    get_key(const InnerNode & n) noexcept
    {
        return n.get_point();
    }

    static KeyT_in
    get_key(const KeyT_in query) noexcept
    {
        return query;
    }

    static KeyT_in
    get_key(const std::pair<KeyT_in, bool> & query) noexcept
    {
        return std::get<0>(query);
    }
};

// Forwards
template <class InnerNode>
class Compare;
template <class InnerTree, class InnerNode, class Node, class NodeTraits>
class InnerRBNodeTraits;
template <class InnerTree, class InnerNode, class AggValueT>
class InnerZNodeTraits;
template <class InnerTree, class InnerNode, class Node, class AggValueT>
class InnerWBNodeTraits;

template <class Tag>
class InnerRBTTag {
};

template <class Tag>
class InnerZTTag {
};

template <class Tag>
class InnerWBTTag {
};

/********************************************
 * Base Class Definitions for RBTree
 ********************************************/
template <class... AdditionalOptions>
struct UseRBTree
{
    template <class InnerNode, class KeyT>
    using Options = TreeOptions<TreeFlags::MULTIPLE,
                                TreeFlags::BENCHMARK_SEQUENCE_INTERFACE<
                                    InnerSequenceInterface<InnerNode, KeyT>>,
                                AdditionalOptions...>;

    template <class Tag>
    struct InnerNodeBaseBuilder
    {
        template <class InnerNodeCRTP, class KeyT>
        using Base =
            RBTreeNodeBase<InnerNodeCRTP, Options<InnerNodeCRTP, KeyT>, Tag>;
    };

    template <class CRTP, class Node, class NodeTraits, class InnerNode,
              class Tag>
    using BaseTree =
        RBTree<InnerNode,
               dyn_segtree_internal::InnerRBNodeTraits<CRTP, InnerNode, Node,
                                                       NodeTraits>,
               Options<InnerNode, typename InnerNode::KeyT>,
               dyn_segtree_internal::InnerRBTTag<Tag>, Compare<InnerNode>>;

    template <class TagType>
    using Tag = InnerRBTTag<TagType>;
};

/********************************************
 * Base Class Definitions for WBTree
 ********************************************/
template <class... AdditionalOptions>
struct UseWBTree
{
    template <class InnerNode, class KeyT>
    using Options = TreeOptions<TreeFlags::MULTIPLE, TreeFlags::WBT_SINGLE_PASS,
                                TreeFlags::BENCHMARK_SEQUENCE_INTERFACE<
                                    InnerSequenceInterface<InnerNode, KeyT>>,
                                AdditionalOptions...>;

    template <class Tag>
    struct InnerNodeBaseBuilder
    {
        template <class InnerNodeCRTP, class KeyT>
        using Base = WBTreeNodeBase<InnerNodeCRTP, Options<InnerNodeCRTP, KeyT>,
                                    Tag>; // TODO make options passable here
    };

    template <class CRTP, class Node, class NodeTraits, class InnerNode,
              class Tag>
    using BaseTree =
        WBTree<InnerNode,
               dyn_segtree_internal::InnerWBNodeTraits<CRTP, InnerNode, Node,
                                                       NodeTraits>,
               Options<InnerNode, typename InnerNode::KeyT>,
               dyn_segtree_internal::InnerWBTTag<Tag>, Compare<InnerNode>>;

    template <class TagType>
    using Tag = InnerWBTTag<TagType>;
};

/********************************************
 * Base Class Definitions for Zip Tree
 ********************************************/
template <class... AdditionalOptions>
struct UseZipTree
{
    template <class InnerNode, class KeyT>
    using Options =
        TreeOptions<TreeFlags::MULTIPLE, TreeFlags::ZTREE_RANK_TYPE<uint8_t>,
                    TreeFlags::BENCHMARK_SEQUENCE_INTERFACE<
                        InnerSequenceInterface<InnerNode, KeyT>>,
                    AdditionalOptions...>;
    template <class Tag>
    struct InnerNodeBaseBuilder
    {
        template <class InnerNodeCRTP, class KeyT>
        using Base =
            ZTreeNodeBase<InnerNodeCRTP, Options<InnerNodeCRTP, KeyT>, Tag>;
    };

    template <class CRTP, class Node, class NodeTraits, class InnerNode,
              class Tag>
    using BaseTree =
        ZTree<InnerNode,
              dyn_segtree_internal::InnerZNodeTraits<
                  CRTP, InnerNode, typename InnerNode::AggValueT>,
              Options<InnerNode, typename InnerNode::KeyT>,
              dyn_segtree_internal::InnerZTTag<Tag>, Compare<InnerNode>>;

    template <class TagType>
    using Tag = InnerZTTag<TagType>;
};

template <template <class InnerNodeCRTP, class BaseKeyT> class Base,
          class OuterNode, class KeyT_in, class ValueT_in, class AggValueT_in,
          class Combiners, class Tag>
class InnerNode : public Base<InnerNode<Base, OuterNode, KeyT_in, ValueT_in,
                                        AggValueT_in, Combiners, Tag>,
                              KeyT_in> {
public:
    using KeyT = KeyT_in;
    using ValueT = ValueT_in;
    using AggValueT = AggValueT_in;

    KeyT get_point() const noexcept;

    bool is_start() const noexcept;

    bool is_end() const noexcept;

    bool is_closed() const noexcept;

    const OuterNode * get_interval() const noexcept;

    // TODO this must be reset when inserting into the tree!
    size_t lca_tag = 0;

private:
    // TODO instead of storing all of these use interval traits and container
    // pointer?
    KeyT point;
    bool start;
    bool closed;

    // TODO remove this
    OuterNode * container;

    AggValueT agg_left;
    AggValueT agg_right;

    Combiners combiners;

    // The tree and the node traits have full access to the nodes
    template <class FNode, class FNodeTraits, class FCombiners, class FOptions,
              class TreeSelector, class FTag>
    friend class ::ygg::DynamicSegmentTree;
    template <class FInnerTree, class FInnerNode, class FNode, class FNodeTraits>
    friend class InnerRBNodeTraits;
    template <class FInnerTree, class FInnerNode, class FNode, class FNodeTraits>
    friend class InnerWBNodeTraits;
    template <class FInnerTree, class FInnerNode, class FAggValueT>
    friend class InnerZNodeTraits;

    // Also, debugging classes are friends
    template <class FInnerNode, class... FCombiners>
    friend class ASCIIInnerNodeNameGetter;
    template <class FInnerNode, class... FCombiners>
    friend class DOTInnerNodeNameGette;
};


template <class InnerTree, class InnerNode, class AggValueT>
class InnerZNodeTraits { // TODO inherit from default traits?
public:
    /*
     * Data for Zipping
     */
    AggValueT left_accumulated;
    AggValueT right_accumulated;

    /*
     * Callbacks for Zipping
     */
    void init_zipping(const InnerNode * to_be_deleted) noexcept;
    void before_zip_from_left(InnerNode * left_head) noexcept;
    void before_zip_from_right(InnerNode * right_head) noexcept;
    void before_zip_tree_from_left(InnerNode * left_head) const noexcept;
    void before_zip_tree_from_right(InnerNode * right_head) const noexcept;
    void zipping_ended_left_without_tree(InnerNode * prev_left_head) const
        noexcept;
    void zipping_ended_right_without_tree(InnerNode * prev_right_head) const
        noexcept;
    void zipping_done(InnerNode * head, InnerNode * tail) const noexcept;
    void delete_without_zipping(const InnerNode * to_be_deleted) const noexcept;

    /*
     * Data for Unzipping
     */
    InnerNode * unzip_left_last;
    InnerNode * unzip_right_last;
    bool unzip_left_first;
    bool unzip_right_first;

    void init_unzipping(InnerNode * to_be_inserted) noexcept;
    void unzip_to_left(InnerNode * n) noexcept;
    void unzip_to_right(InnerNode * n) noexcept;
    void unzip_done(InnerNode * unzip_root, InnerNode * left_spine_end,
                    InnerNode * right_spine_end) noexcept;
};

template <class InnerTree, class InnerNode, class Node, class NodeTraits>
class InnerRBNodeTraits : public RBDefaultNodeTraits {
public:
    template <class RBTreeBase>
    static void leaf_inserted(const InnerNode & node,
                              const RBTreeBase & t) noexcept;
    template <class RBTreeBase>
    static void rotated_left(InnerNode & node, const RBTreeBase & t) noexcept;
    template <class RBTreeBase>
    static void rotated_right(InnerNode & node, const RBTreeBase & t) noexcept;
    template <class RBTreeBase>
    static void delete_leaf(const InnerNode & node,
                            const RBTreeBase & t) noexcept;
    template <class RBTreeBase>
    static void swapped(InnerNode & n1, InnerNode & n2, RBTreeBase & t) noexcept;

private:
    static InnerNode * get_partner(const InnerNode & n) noexcept;
};

/*
 * Since weight-balanced trees are based on the very same rotations that
 * red-black trees are, we can use the exact same traits.
 */
template <class InnerTree, class InnerNode, class Node, class NodeTraits>
class InnerWBNodeTraits
    : public InnerRBNodeTraits<InnerTree, InnerNode, Node, NodeTraits> {
public:
    template <class WBTreeBase>
    static void splice_out_left_knee(
        InnerNode & node,
        const WBTreeBase & t) noexcept; // TODO if aggregate-addition is noexcept
    template <class WBTreeBase>
    static void
    splice_out_right_knee(InnerNode & node,
                          const WBTreeBase & t) noexcept; // TODO see above
};

template <class InnerNode>
class Compare {
public:
    using PointDescription =
        std::pair<const typename InnerNode::KeyT, const int_fast8_t>;

    bool operator()(const InnerNode & lhs, const InnerNode & rhs) const noexcept;
    bool operator()(const typename InnerNode::KeyT & lhs,
                    const InnerNode & rhs) const noexcept;
    bool operator()(const InnerNode & lhs,
                    const typename InnerNode::KeyT & rhs) const noexcept;
    bool operator()(const PointDescription & lhs, const InnerNode & rhs) const
        noexcept;
    bool operator()(const InnerNode & lhs, const PointDescription & rhs) const
        noexcept;
};

/*
 * Debugging helpers
 */
template <class InnerNode, class... Combiners>
class ASCIIInnerNodeNameGetter {
public:
    std::string get_name(InnerNode * node) const;
};

template <class InnerNode, class... Combiners>
class DOTInnerNodeNameGetter {
public:
    std::string get_name(InnerNode * node) const;
};

template <class InnerNode>
class DOTInnerEdgeNameGetter {
public:
    std::string get_name(InnerNode * node, bool left) const;
};

} // namespace dyn_segtree_internal

template <class... AdditionalOptions>
class UseRBTree : public dyn_segtree_internal::UseRBTree<AdditionalOptions...> {
};
using UseDefaultRBTree = UseRBTree<>;

template <class... AdditionalOptions>
class UseZipTree
    : public dyn_segtree_internal::UseZipTree<AdditionalOptions...> {
};
using UseDefaultZipTree = UseZipTree<>;

template <class... AdditionalOptions>
class UseWBTree : public dyn_segtree_internal::UseWBTree<AdditionalOptions...> {
};
using UseDefaultWBTree = UseWBTree<>;

template <class KeyType, class ValueType>
class MaxCombiner {
public:
    using ValueT = ValueType;
    using KeyT = KeyType;
    using MyType = MaxCombiner<KeyT, ValueT>;

    // TODO the bool is only returned for sake of expansion! Fix that!
    bool collect_left(const KeyT my_point, const MyType * left_child_combiner,
                      const ValueType edge_val);
    // TODO make all keys / values references?
    bool collect_right(const KeyT my_point, const MyType * right_child_combiner,
                       const ValueType edge_val);

    // TODO the bool is only returned for sake of expansion! Fix that!
    bool traverse_left_edge_up(const KeyT new_point, const ValueT edge_val);
    bool traverse_right_edge_up(const KeyT new_point, const ValueT edge_val);

    // bool aggregate_with(ValueT a);

    bool rebuild(KeyT my_point, const MyType * left_child_combiner,
                 ValueT left_edge_val, const MyType * right_child_combiner,
                 ValueT right_edge_val);

    ValueT get() const noexcept;

    // TODO DEBUG
    static std::string
    get_name()
    {
        return "MaxCombiner";
    }
    // TODO DEBUG
    std::string
    get_dbg_value() const
    {
        return std::to_string(this->val);
    }

private:
    ValueT val;

    ValueT child_value(const MyType * child) const noexcept;
};

template <class KeyType, class ValueType>
class RangedMaxCombiner {
public:
    using ValueT = ValueType;
    using KeyT = KeyType;
    using MyType = RangedMaxCombiner<KeyT, ValueT>;

    RangedMaxCombiner();

    // TODO the bool is only returned for sake of expansion! Fix that!
    bool collect_left(KeyT my_point, const MyType * left_child_combiner,
                      ValueType edge_val);
    bool collect_right(KeyT my_point, const MyType * right_child_combiner,
                       ValueType edge_val);

    // TODO the bool is only returned for sake of expansion! Fix that!
    bool traverse_left_edge_up(KeyT new_point, ValueT edge_val);
    bool traverse_right_edge_up(KeyT new_point, ValueT edge_val);

    // bool aggregate_with(ValueT a);

    bool rebuild(KeyT my_point, const MyType * left_child_combiner,
                 ValueT left_edge_val, const MyType * right_child_combiner,
                 ValueT right_edge_val);

    ValueT get() const noexcept;

    bool is_left_border_valid() const noexcept;
    bool is_right_border_valid() const noexcept;

    KeyT get_left_border() const noexcept;

    KeyT get_right_border() const noexcept;

    // TODO DEBUG
    static std::string
    get_name()
    {
        return "RangedMaxCombiner";
    }
    // TODO DEBUG
    std::string
    get_dbg_value() const
    {
        std::string res = std::to_string(this->val) + std::string("@[");
        if (this->left_border_valid) {
            res += std::to_string(this->left_border);
        } else {
            res += std::string("--");
        }
        res += ":";
        if (this->right_border_valid) {
            res += std::to_string(this->right_border);
        } else {
            res += "--";
        }
        res += "]";

        return res;
    }

private:
    ValueT val;

    // TODO replace by std::optional when switching to C++17
    KeyT left_border;
    bool left_border_valid;
    KeyT right_border;
    bool right_border_valid;

    ValueT child_value(const MyType * child) const noexcept;
};

template <class KeyT, class AggValueT, class... Combiners>
class CombinerPack {
public:
    using MyType = CombinerPack<KeyT, AggValueT, Combiners...>;

    CombinerPack() = default;

    bool rebuild(KeyT my_point, const MyType * left_child,
                 AggValueT left_edge_val, const MyType * right_child,
                 AggValueT right_edge_val);

    // TODO the bool is only returned for sake of expansion! Fix that!
    bool collect_left(KeyT my_point, const MyType * left_child_combiner,
                      AggValueT edge_val);
    bool collect_right(KeyT my_point, const MyType * right_child_combiner,
                       AggValueT edge_val);

    // TODO the bool is only returned for sake of expansion! Fix that!
    bool traverse_left_edge_up(KeyT new_point, AggValueT edge_val);
    bool traverse_right_edge_up(KeyT new_point, AggValueT edge_val);

    template <class Combiner>
    typename Combiner::ValueT get() const;

    template <class Combiner>
    const Combiner & get_combiner() const;

    using pack = std::tuple<Combiners...>;

private:
    template <class Combiner>
    const Combiner * child_combiner(const MyType * child) const;

    std::tuple<Combiners...> data;
};

template <class KeyT, class AggValueT>
using EmptyCombinerPack = CombinerPack<KeyT, AggValueT>;

template <class KeyType, class ValueType, class AggValueType, class Combiners,
          class TreeSelector = UseDefaultRBTree, class Tag = int>
class DynSegTreeNodeBase {
    // TODO why is all of this public?
public:
    using KeyT = KeyType;
    using ValueT = ValueType;
    using AggValueT = AggValueType;
    using MyClass = DynSegTreeNodeBase<KeyType, ValueType, AggValueType,
                                       Combiners, TreeSelector, Tag>;

    using InnerNode = dyn_segtree_internal::InnerNode<
        TreeSelector::template InnerNodeBaseBuilder<
            typename TreeSelector::template Tag<Tag>>::template Base,
        MyClass, KeyT, ValueT, AggValueT, Combiners, Tag>;

    // TODO make these private
    InnerNode start;

    InnerNode end;
};

template <class Node> // TODO move this into the methods
class DynSegTreeNodeTraits {
public:
    using KeyT = typename Node::KeyT;
    using ValueT = typename Node::ValueT;

    static KeyT get_lower(const Node & n);

    static KeyT get_upper(const Node & n);

    static bool
    is_lower_closed(const Node & n)
    {
        (void)n;
        return true;
    };

    static bool
    is_upper_closed(const Node & n)
    {
        (void)n;
        return false;
    };

    static ValueT get_value(const Node & n);
};

// TODO DOC right-open intervals

// TODO constant-time size
template <class Node, class NodeTraits, class Combiners,
          class Options = DefaultOptions, class TreeSelector = UseDefaultRBTree,
          class Tag = int>
class DynamicSegmentTree {
    // TODO add a static assert that checks that the types in all combiners are
    // right
private:
    using NB = DynSegTreeNodeBase<typename Node::KeyT, typename Node::ValueT,
                                  typename Node::AggValueT, Combiners,
                                  TreeSelector, Tag>;
    using InnerNode = typename NB::InnerNode;

    static_assert(std::is_base_of<DynSegTreeNodeTraits<Node>, NodeTraits>::value,
                  "NodeTraits not properly derived from DynSegTreeNodeTraits!");
    static_assert(std::is_base_of<NB, Node>::value,
                  "Node class not properly derived from DynSegTreeNodeBase!");
    static_assert(Options::multiple,
                  "DynamicSegmentTree always allows multiple equal intervals.");

public:
    using KeyT = typename Node::KeyT;
    using ValueT = typename Node::ValueT;
    using AggValueT = typename Node::AggValueT;
    using MyClass = DynamicSegmentTree<Node, NodeTraits, Combiners, Options,
                                       TreeSelector, Tag>;

private:
    class InnerTree
        : public TreeSelector::template BaseTree<InnerTree, Node, NodeTraits,
                                                 InnerNode, Tag> {
    public:
        using BaseTree =
            typename TreeSelector::template BaseTree<InnerTree, Node, NodeTraits,
                                                     InnerNode, Tag>;

        using BaseTree::BaseTree;

        void modify_contour(InnerNode * left, InnerNode * right, ValueT val);

        using Contour =
            std::pair<std::vector<InnerNode *>, std::vector<InnerNode *>>;
        void build_lca(InnerNode * left, InnerNode * right) const;

        static bool rebuild_combiners_at(InnerNode * n);
        static void rebuild_combiners_recursively(InnerNode * n);

    private:
        // Generation to be used to tag nodes during LCA search
        mutable size_t generation = 0;
        // Allocate-once buffers for the contour

        // TODO this is real bad style: public mutable members?
    public:
        mutable std::vector<InnerNode *> contour_left_path;
        mutable std::vector<InnerNode *> contour_right_path;
    };

public:
    DynamicSegmentTree(MyClass && other);

    DynamicSegmentTree();

    void insert(Node & n);

    void remove(Node & n);

    bool empty() const;

    AggValueT query(const typename Node::KeyT & x) const noexcept;

    template <class Combiner>
    Combiner get_combiner() const;

    template <class Combiner>
    Combiner get_combiner(const typename Node::KeyT & lower,
                          const typename Node::KeyT & upper,
                          bool lower_closed = true,
                          bool upper_closed = false) const;

    template <class Combiner>
    typename Combiner::ValueT get_combined() const;

    template <class Combiner>
    typename Combiner::ValueT get_combined(const typename Node::KeyT & lower,
                                           const typename Node::KeyT & upper,
                                           bool lower_closed = true,
                                           bool upper_closed = false) const;

    /*
     * Iteration
     */
    template <bool reverse>
    using const_iterator = typename InnerTree::template const_iterator<reverse>;
    template <bool reverse>
    using iterator = typename InnerTree::template iterator<reverse>;

    // TODO derive a non-internal class from the InnerNode, and make the iterator
    // return a pointer to that.

    const_iterator<false> cbegin() const;
    const_iterator<false> cend() const;
    const_iterator<false> begin() const;
    iterator<false> begin();

    const_iterator<false> end() const;
    iterator<false> end();

    const_iterator<true> crbegin() const;
    const_iterator<true> crend() const;
    const_iterator<true> rbegin() const;
    iterator<true> rbegin();

    const_iterator<true> rend() const;
    iterator<true> rend();

    const_iterator<false>
    lower_bound_event(const typename Node::KeyT & key) const;
    iterator<false> lower_bound_event(const typename Node::KeyT & key);

    const_iterator<false>
    upper_bound_event(const typename Node::KeyT & key) const;
    iterator<false> upper_bound_event(const typename Node::KeyT & key);

    void clear();

    /*
     * DEBUGGING
     */
    void dbg_verify() const;

    template <class Combiner>
    void dbg_verify_max_combiner() const;

private:
    // TODO build a generic function for this
    template <class... Ts>
    using NodeNameGetterCurried =
        dyn_segtree_internal::ASCIIInnerNodeNameGetter<InnerNode, Ts...>;
    using NodeNameGetter =
        typename utilities::pass_pack<typename Combiners::pack,
                                      NodeNameGetterCurried>::type;
    template <class... Ts>
    using DotNameGetterCurried =
        dyn_segtree_internal::DOTInnerNodeNameGetter<InnerNode, Ts...>;
    using DotNameGetter =
        typename utilities::pass_pack<typename Combiners::pack,
                                      DotNameGetterCurried>::type;

    using TreePrinter = debug::TreePrinter<InnerNode, NodeNameGetter>;
    using TreeDotExporter = debug::TreeDotExport<
        InnerNode, DotNameGetter,
        dyn_segtree_internal::DOTInnerEdgeNameGetter<InnerNode>>;

public:
    // TODO Debugging only!
    void dbg_print_inner_tree() const;
    std::stringstream & dbg_get_dot() const;

private:
    void apply_interval(Node & n);
    void unapply_interval(Node & n);

    InnerTree t;

    void dbg_verify_all_points() const;
    void dbg_verify_start_end() const;
};

} // namespace ygg

#ifndef YGG_DYNAMIC_SEGMENT_TREE_CPP
#include "dynamic_segment_tree.cpp"
#endif

#endif // YGG_DYNAMIC_SEGMENT_TREE_HPP