intervaltree.hpp

#ifndef INTERVALTREE_HPP
#define INTERVALTREE_HPP

#include "rbtree.hpp"

#include <algorithm>
#include <iostream>
#include <string>

namespace ygg {
namespace intervaltree_internal {
template <class Node, class INB, class NodeTraits, bool skipfirst,
          class Comparable>
Node * find_next_overlapping(Node * cur, const Comparable & q);

template <class KeyType>
class DummyRange : public std::pair<KeyType, KeyType> {
public:
    DummyRange(KeyType lower, KeyType upper);
};

template <class Node, class NodeTraits>
class IntervalCompare {
public:
    template <class T1, class T2>
    bool operator()(const T1 & lhs, const T2 & rhs) const;
};

// TODO add a possibility for bulk updates
template <class Node, class INB, class NodeTraits>
class ExtendedNodeTraits : public NodeTraits {
public:
    // TODO these can probably made more efficient
    template <class BaseTree>
    static void leaf_inserted(Node & node, BaseTree & t);

    static void fix_node(Node & node);
    template <class BaseTree>
    static void rotated_left(Node & node, BaseTree & t);
    template <class BaseTree>
    static void rotated_right(Node & node, BaseTree & t);
    template <class BaseTree>
    static void deleted_below(Node & node, BaseTree & t);
    template <class BaseTree>
    static void
    delete_leaf(Node & node, BaseTree & t)
    {
        (void)node;
        (void)t;
    }
    template <class BaseTree>
    static void swapped(Node & n1, Node & n2, BaseTree & t);

    // Make our DummyRange comparable
    static typename NodeTraits::key_type get_lower(
        const intervaltree_internal::DummyRange<typename NodeTraits::key_type> &
            range);
    static typename NodeTraits::key_type get_upper(
        const intervaltree_internal::DummyRange<typename NodeTraits::key_type> &
            range);
};
} // namespace intervaltree_internal

template <class Node, class NodeTraits, class Options = DefaultOptions,
          class Tag = int>
class ITreeNodeBase : public RBTreeNodeBase<Node, Options, Tag> {
public:
    typename NodeTraits::key_type _it_max_upper;
};

template <class Node>
class ITreeNodeTraits {
public:
    using key_type = void;

    static key_type get_lower(const Node & n) = delete;

    static key_type get_upper(const Node & n) = delete;
};

template <class Node, class NodeTraits, class Options = DefaultOptions,
          class Tag = int>
class IntervalTree
    : private RBTree<
          Node,
          intervaltree_internal::ExtendedNodeTraits<
              Node, ITreeNodeBase<Node, NodeTraits, Options, Tag>, NodeTraits>,
          Options, Tag,
          intervaltree_internal::IntervalCompare<Node, NodeTraits>> {
public:
    using Key = typename NodeTraits::key_type;
    using MyClass = IntervalTree<Node, NodeTraits, Options, Tag>;

    using INB = ITreeNodeBase<Node, NodeTraits, Options, Tag>;
    static_assert(std::is_base_of<INB, Node>::value,
                  "Node class not properly derived from ITreeNodeBase!");

    static_assert(std::is_base_of<ITreeNodeTraits<Node>, NodeTraits>::value,
                  "NodeTraits not properly derived from ITreeNodeTraits!");

    using ENodeTraits =
        intervaltree_internal::ExtendedNodeTraits<Node, INB, NodeTraits>;
    using BaseTree = RBTree<
        Node, intervaltree_internal::ExtendedNodeTraits<Node, INB, NodeTraits>,
        Options, Tag, intervaltree_internal::IntervalCompare<Node, NodeTraits>>;

    IntervalTree();

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

    /* Import some of RBTree's methods into the public namespace */
    using BaseTree::empty;
    using BaseTree::insert;
    using BaseTree::remove;

    // Iteration of sets of intervals
    template <class Comparable>
    class QueryResult {
    public:
        class const_iterator {
        public:
            typedef ptrdiff_t difference_type;
            typedef Node value_type;
            typedef const Node & const_reference;
            typedef const Node * const_pointer;
            typedef std::input_iterator_tag iterator_category;

            const_iterator(Node * n, const Comparable & q);
            const_iterator(const const_iterator & other);
            ~const_iterator();

            const_iterator & operator=(const const_iterator & other);

            bool operator==(const const_iterator & other) const;
            bool operator!=(const const_iterator & other) const;

            const_iterator & operator++();
            const_iterator operator++(int);

            const_reference operator*() const;
            const_pointer operator->() const;

        private:
            Node * n;
            Comparable q;
        };

        QueryResult(Node * n, const Comparable & q);

        const_iterator begin() const;
        const_iterator end() const;

    private:
        Node * n;
        Comparable q;
    };

    template <class Comparable>
    QueryResult<Comparable> query(const Comparable & q) const;

    template <class Comparable>
    typename BaseTree::template const_iterator<false>
    interval_upper_bound(const Comparable & query_range) const;

    // TODO FIXME this is actually very specific?
    void fixup_maxima(Node & lowest);

    // Iterating the events should still be possible
    using BaseTree::begin;
    using BaseTree::end;

private:
    bool verify_maxima(Node * n) const;
};

} // namespace ygg

#include "intervaltree.cpp"

#endif // INTERVALTREE_HPP