ziptree.hpp

#ifndef YGG_ZIPTREE_H
#define YGG_ZIPTREE_H

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

#ifdef YGG_STORE_SEQUENCE
#include "benchmark_sequence.hpp"
#endif

#include <cmath>
#include <functional>

namespace ygg {

// Forward
template <class Node, class Options = DefaultOptions, class Tag = int>
class ZTreeNodeBase;

namespace ztree_internal {

template <class Tree, bool enable>
struct dbg_verify_size_helper
{
    void operator()(const Tree & t, size_t node_count);
};

template <class Node, class Options, bool use_hash, bool store>
class ZTreeRankGenerator;

template <class Node, class Options>
class ZTreeRankGenerator<Node, Options, true, false> {
public:
    ZTreeRankGenerator();
    static void update_rank(Node & node) noexcept;
    static int get_rank(const Node & node) noexcept;
};

template <class Node, class Options>
class ZTreeRankGenerator<Node, Options, true, true> {
public:
    ZTreeRankGenerator();
    static void update_rank(Node & node) noexcept;
    static size_t get_rank(const Node & node) noexcept;

private:
    template <class, class, class>
    friend class ZTreeNodeBase;
    typename Options::ztree_rank_type::type rank;
};

template <class Node, class Options>
class ZTreeRankGenerator<Node, Options, false, true> {
public:
    ZTreeRankGenerator();
    template <class URBG>
    ZTreeRankGenerator(URBG && g);
    static void update_rank(Node & node) noexcept;
    static size_t get_rank(const Node & node) noexcept;

private:
    template <class, class, class>
    friend class ZTreeNodeBase;
    typename Options::ztree_rank_type::type rank;
};

template <class Node, class Options>
class ZTreeRankGenerator<Node, Options, false, false> {
    // Build a static assertion that always fails, but
    // only if this specialization is ever used. Thus, it must depend on
    // the template parameters.
    static_assert(!std::is_class<Node>::value || std::is_class<Node>::value,
                  "If rank-by-hash is not used, ranks must be stored.");
};
} // namespace ztree_internal

template <class Node, class Options, class Tag>
class ZTreeNodeBase : public bst::BSTNodeBase<Node, Tag> {
public:
    // Debugging methods
    size_t get_depth() const noexcept;

protected:
    void
    update_rank() noexcept
    {
        ztree_internal::ZTreeRankGenerator<
            Node, Options, Options::ztree_use_hash,
            Options::ztree_store_rank>::update_rank(*static_cast<Node *>(this));
    }

private:
    template <class, class, bool, bool>
    friend class ztree_internal::ZTreeRankGenerator;

    ztree_internal::ZTreeRankGenerator<Node, Options, Options::ztree_use_hash,
                                       Options::ztree_store_rank>
        _zt_rank;
};

template <class Node>
class ZTreeDefaultNodeTraits {
public:
    // clang-format off
  /*
   * Callbacks for Zipping
   */
  void init_zipping(Node * to_be_deleted) const noexcept {(void)to_be_deleted;};
  void delete_without_zipping(Node * to_be_deleted) const noexcept {(void)to_be_deleted;};
  void before_zip_from_left(Node * left_head) const noexcept {(void)left_head;};
  void before_zip_from_right(Node * right_head) const noexcept {(void)right_head;};
  void zipping_ended_left_without_tree(Node * prev_left_head) const noexcept {(void)prev_left_head;};
  void zipping_ended_right_without_tree(Node * prev_right_head) const noexcept {(void)prev_right_head;};  
  void before_zip_tree_from_left(Node * left_head) const noexcept {(void)left_head;};
  void before_zip_tree_from_right(Node * right_head) const noexcept {(void)right_head;};
  void zipping_done(Node * head, Node * tail) const noexcept {(void)head; (void)tail;}
  
  /*
   * Callbacks for Unzipping
   */
  void init_unzipping(Node * to_be_inserted) const noexcept {(void) to_be_inserted;};
  void unzip_to_left(Node * n) const noexcept {(void)n;}
  void unzip_to_right(Node * n) const noexcept {(void)n;}
  void unzip_done(Node * unzip_root, Node * left_spine_end, Node * right_spine_end) const noexcept
  {
    (void) unzip_root;
    (void) left_spine_end;
    (void) right_spine_end;
  }
    // clang-format on
};

template <
    class Node, class NodeTraits, class Options = DefaultOptions,
    class Tag = int, class Compare = ygg::utilities::flexible_less,
    class RankGetter = ztree_internal::ZTreeRankGenerator<
        Node, Options, Options::ztree_use_hash, Options::ztree_store_rank>>
class ZTree : public bst::BinarySearchTree<Node, Options, Tag, Compare> {
public:
    using NB = ZTreeNodeBase<Node, Options, Tag>;
    using TB = bst::BinarySearchTree<Node, Options, Tag, Compare>;
    using MyClass = ZTree<Node, NodeTraits, Options, Tag, Compare, RankGetter>;

    ZTree() noexcept;

    static_assert(std::is_base_of<NB, Node>::value,
                  "Node class not properly derived from node base!");

    ZTree(MyClass && other) noexcept;

    MyClass & operator=(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) noexcept;
    void insert(Node & node, Node & hint) noexcept;

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

    // Debugging methods
    void dbg_verify() const;
    void dbg_print_rank_stats() const;

    void dump_to_dot(const std::string & filename) const;

private:
    void unzip(Node & oldn, Node & newn) noexcept;
    void zip(Node & old_root) noexcept;

    // Debugging methods
    void dbg_verify_consistency(Node * sub_root, Node * lower_bound,
                                Node * upper_bound) const;
    void dbg_verify_size() const;

    template <class NodeNameGetter>
    void dump_to_dot_base(const std::string & filename,
                          NodeNameGetter name_getter) const;

    template <class NodeNameGetter>
    void output_node_base(const Node * node, std::ofstream & out,
                          NodeNameGetter name_getter) const;

#ifdef YGG_STORE_SEQUENCE
    typename ygg::utilities::template BenchmarkSequenceStorage<
        typename Options::SequenceInterface::KeyT>
        bss;
#endif
};

} // namespace ygg

#ifndef YGG_ZIPTREE_CPP
#include "ziptree.cpp"
#endif

#endif