intervalmap.hpp

//
// Created by lukas on 31.08.17.
//

#ifndef YGG_INTERVALMAP_HPP
#define YGG_INTERVALMAP_HPP

#include "intervaltree.hpp"
#include "list.hpp"
#include "options.hpp"
#include "rbtree.hpp"
#include "size_holder.hpp"

namespace ygg {

namespace intervalmap_internal {
class SegListTag {
};
class RepresentativeSegListTag {
};
class InnerRBTTag {
};

template <class KeyT, class ValueT>
class InnerNode
    : public RBTreeNodeBase<InnerNode<KeyT, ValueT>,
                            TreeOptions<TreeFlags::MULTIPLE>, InnerRBTTag>,
      public ListNodeBase<InnerNode<KeyT, ValueT>, SegListTag>,
      public ListNodeBase<InnerNode<KeyT, ValueT>, RepresentativeSegListTag> {
public:
    KeyT point;
    ValueT aggregate;
    InnerNode<KeyT, ValueT> * repr;

    class Compare {
    public:
        constexpr bool
        operator()(const InnerNode<KeyT, ValueT> & lhs,
                   const InnerNode<KeyT, ValueT> & rhs) const
        {
            return lhs.point < rhs.point;
        }

        constexpr bool
        operator()(int lhs, const InnerNode<KeyT, ValueT> & rhs) const
        {
            return lhs < rhs.point;
        }

        constexpr bool
        operator()(const InnerNode<KeyT, ValueT> & lhs, int rhs) const
        {
            return lhs.point < rhs;
        }
    };
};
} // namespace intervalmap_internal

template <class KeyT, class ValueT, class Tag = int>
class IMapNodeBase {
public:
    using Segment = intervalmap_internal::InnerNode<KeyT, ValueT>;

    Segment _imap_begin;
    Segment _imap_end;

    using value_type = ValueT;
    using key_type = KeyT;
};

template <class Node>
class IMapNodeTraits {
public:
    using key_type = typename Node::key_type;
    using value_type = typename Node::value_type;

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

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

    static value_type get_value(const Node & n) = delete;

    static void
    on_value_changed(typename Node::Segment & seg, const value_type & old_val,
                     const value_type & new_val)
    {
        (void)seg;
        (void)old_val;
        (void)new_val;
    }

    static void
    on_length_changed(typename Node::Segment & seg)
    {
        (void)seg;
    }

    static void
    on_segment_inserted(typename Node::Segment & seg)
    {
        (void)seg;
    }

    static void
    on_segment_removed(typename Node::Segment & seg)
    {
        (void)seg;
    }
};

template <class Node, class NodeTraits, class Options = DefaultOptions,
          class Tag = int>
class IntervalMap {
public:
    using Segment = intervalmap_internal::InnerNode<typename Node::key_type,
                                                    typename Node::value_type>;

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

    static_assert(Options::multiple,
                  "IntervalMap always allows multiple equal intervals.");

    using NB =
        IMapNodeBase<typename Node::key_type, typename Node::value_type, Tag>;
    static_assert(std::is_base_of<NB, Node>::value,
                  "Node class not properly derived from IMapNodeBase!");
    using ITree =
        RBTree<Segment, RBDefaultNodeTraits, TreeOptions<TreeFlags::MULTIPLE>,
               intervalmap_internal::InnerRBTTag, typename Segment::Compare>;
    using SegList =
        List<Segment, TreeOptions<>, intervalmap_internal::SegListTag>;
    using RepresentativeSegList =
        List<Segment, TreeOptions<>,
             intervalmap_internal::RepresentativeSegListTag>;
    using value_type = typename Node::value_type;
    using key_type = typename Node::key_type;

    void insert(Node & n);

    void remove(Node & n);

    size_t size() const;

    bool empty() const;

    value_type get_aggregate(Segment & s);

    template <class ConcreteIterator, class InnerIterator>
    class IteratorBase {
    public:
        typedef typename InnerIterator::difference_type difference_type;
        typedef typename InnerIterator::value_type value_type;
        typedef typename InnerIterator::reference reference;
        typedef typename InnerIterator::pointer pointer;
        typedef std::input_iterator_tag iterator_category;

        IteratorBase();
        IteratorBase(const InnerIterator & it, RepresentativeSegList * l);
        IteratorBase(const ConcreteIterator & other);

        ConcreteIterator & operator=(const ConcreteIterator & other);
        ConcreteIterator & operator=(ConcreteIterator && other);

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

        ConcreteIterator & operator++();
        ConcreteIterator operator++(int);
        ConcreteIterator & operator+=(size_t steps);
        ConcreteIterator operator+(size_t steps) const;

        ConcreteIterator & operator--();
        ConcreteIterator operator--(int);

        reference operator*() const;
        pointer operator->() const;

        key_type get_lower() const;
        key_type get_upper() const;
        const typename IntervalMap<Node, NodeTraits, Options, Tag>::value_type &
        get_value() const;

    private:
        InnerIterator inner;
        RepresentativeSegList * l;
    };

    class const_iterator
        : public IteratorBase<const_iterator,
                              typename RepresentativeSegList::const_iterator> {
    public:
        using IteratorBase<
            const_iterator,
            typename RepresentativeSegList::const_iterator>::IteratorBase;
    };

    class iterator
        : public IteratorBase<iterator,
                              typename RepresentativeSegList::iterator> {
    public:
        using IteratorBase<iterator,
                           typename RepresentativeSegList::iterator>::IteratorBase;
    };

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

    void dbg_verify();

private:
    Segment * get_head(Segment * seg);

    Segment * insert_segment(Segment * seg);
    void remove_segment(Segment * seg);

    void repr_now_equal(Segment * a, Segment * b);
    void repr_now_different(Segment * a, Segment * b);
    void repr_replaced(Segment * old, Segment * replacement);

    // TODO FIXME is this needed?
    iterator find_lower_bound_representative(typename Node::key_type point);

    ITree t;
    SegList l;
    RepresentativeSegList repr_list;

    SizeHolder<Options::constant_time_size> s;

    void dbg_verify_list();
    void dbg_verify_representatives();
};

} // namespace ygg

#include "intervalmap.cpp"

#endif // YGG_INTERVALMAP_HPP