orbtree.h

/*  -*- C++ -*-
 * orbtree.h -- generalized order statistic red-black tree implementation
 *  main interface
 * 
 * Copyright 2019 Daniel Kondor <kondor.dani@gmail.com>
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met:
 * 
 * * Redistributions of source code must retain the above copyright
 *   notice, this list of conditions and the following disclaimer.
 * * Redistributions in binary form must reproduce the above
 *   copyright notice, this list of conditions and the following disclaimer
 *   in the documentation and/or other materials provided with the
 *   distribution.
 * * Neither the name of the  nor the names of its
 *   contributors may be used to endorse or promote products derived from
 *   this software without specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 * 
 * 
 */


#ifndef ORBTREE_H
#define ORBTREE_H

#include "orbtree_base.h"
#include <type_traits>
#include <limits>
#include <stdexcept>
#include <vector>
#include <math.h>

/* constexpr if support only for c++17 or newer */
#if __cplusplus >= 201703L
#define CONSTEXPR constexpr
#else
#define CONSTEXPR
#endif


namespace orbtree {
    
    /* main class with public interface */
    template<class NodeAllocator, class Compare, class NVFunc, bool multi, bool simple = false>
    class orbtree : public orbtree_base<NodeAllocator, Compare, NVFunc, multi> {
        protected:
            typedef typename orbtree_base<NodeAllocator, Compare, NVFunc, multi>::NodeHandle NodeHandle;
            typedef typename orbtree_base<NodeAllocator, Compare, NVFunc, multi>::KeyValue KeyValue;
        
        public:
/* typedefs */
            typedef typename NodeAllocator::KeyValue::ValueType value_type;
            typedef typename NodeAllocator::KeyValue::KeyType key_type;
            typedef typename NodeAllocator::NVType NVType;
            /* conditionally define mapped_type ?? */
            typedef size_t size_type;
            typedef size_t difference_type; /* note: unsigned difference_type not standard?
                        -- since iterators are InputIterators, only unsigned differences are possible */
            
            
            explicit orbtree(const NVFunc& f_ = NVFunc(), const Compare& c_ = Compare())
                    : orbtree_base<NodeAllocator, Compare, NVFunc, multi>(f_,c_) {
                if CONSTEXPR (simple) if(this->f.get_nr() != 1) {
                    throw std::runtime_error("For simple tree, weight function can only return one component!\n");
                }
            }
            explicit orbtree(NVFunc&& f_,const Compare& c_ = Compare())
                    : orbtree_base<NodeAllocator, Compare, NVFunc, multi>(f_,c_) { 
                if CONSTEXPR (simple) if(this->f.get_nr() != 1) {
                    throw std::runtime_error("For simple tree, weight function can only return one component!\n");
                }
            }
            template<class T>
            explicit orbtree(const T& t, const Compare& c_ = Compare())
                    : orbtree_base<NodeAllocator, Compare, NVFunc, multi>(t,c_) {
                if CONSTEXPR (simple) if(this->f.get_nr() != 1) {
                    throw std::runtime_error("For simple tree, weight function can only return one component!\n");
                }
            }
                    
            
            
            
            /* iterators -- note: set should only have const iterators */
            template<bool is_const>
            struct iterator_base {
                protected:
                    typedef typename NodeAllocator::KeyValue::ValueType value_base;
                    typedef typename std::conditional<is_const, const orbtree, orbtree>::type orbtree_t;
                public:
                    /* typedefs */
                    typedef std::bidirectional_iterator_tag iterator_category;
                    /* note: value type is always const, value cannot be changed
                     * by dereferincing the iterator since rank function might depend on it
                     * need to call set_value() explicitely */

                    typedef const value_base value_type;
                    typedef const value_base* pointer;
                    typedef const value_base& reference;
                    
                    friend class iterator_base<!is_const>;
                    friend class orbtree<NodeAllocator,Compare,NVFunc,multi,simple>;
                protected:
                    orbtree_t& t; /* has to be const reference for const iterator */
                    NodeHandle n;
                    iterator_base() = delete;
                    /* create iterator (by orbtree class) */
                    iterator_base(orbtree_t& t_, NodeHandle n_):t(t_),n(n_) { }
                    /* convert const iterator to non-const -- protected, might be needed internally ? */
                    template<bool is_const_ = is_const>
                    explicit iterator_base(const iterator_base<true>& it, typename std::enable_if<!is_const_>::type* = 0)
                        :t(const_cast<orbtree>(it.t)),n(it.n) { }
                public:
                    
                    /* any iterator can be copied from non-const iterator;
                     * this is not explicit so comparison operators can auto-convert */
                    iterator_base(const iterator_base<false>& it):t(it.t),n(it.n) { }
                    /* only const iterator can be copied from const iterator */
                    template<bool is_const_ = is_const>
                    iterator_base(const iterator_base<true>& it, typename std::enable_if<is_const_>::type* = 0 ):t(it.t),n(it.n) { }
                    

                    reference operator * () {
                        if(n == NodeAllocator::Invalid) throw std::runtime_error("Attempt to dereference invalid orbtree::iterator!\n");
                        return t.get_node(n).get_key_value().keyvalue();
                    }
                    pointer operator -> () {
                        if(n == NodeAllocator::Invalid) throw std::runtime_error("Attempt to dereference invalid orbtree::iterator!\n");
                        return &(t.get_node(n).get_key_value().keyvalue());
                    }
                    template<bool is_const_ = is_const, class KeyValue_ = typename NodeAllocator::KeyValue>
                    typename std::enable_if<!is_const_>::type set_value(typename KeyValue_::MappedType&& v) {
                        t.update_value(n,std::move(v));
                    }
                    template<bool is_const_ = is_const, class KeyValue_ = typename NodeAllocator::KeyValue>
                    typename std::enable_if<!is_const_>::type set_value(typename KeyValue_::MappedType const& v) {
                        t.update_value(n,v);
                    }
                    
                    const key_type& key() const { return t.get_node(n).get_key_value().key(); }
                    

                    template<bool is_const2> bool operator == (const iterator_base<is_const2>& i) const { return n == i.n; }

                    template<bool is_const2> bool operator != (const iterator_base<is_const2>& i) const { return n != i.n; }
                    
                    iterator_base& operator ++() { n = t.next(n); return *this; }
                    iterator_base operator ++(int) { iterator_base<is_const> i(*this); n = t.next(n); return i; }
                    iterator_base& operator --() { n = t.previous(n); return *this; }
                    iterator_base operator --(int) { iterator_base<is_const> i(*this); n = t.previous(n); return i; }
            };
            
            typedef iterator_base<true> const_iterator;
            typedef typename std::conditional<NodeAllocator::KeyValue::keyonly, iterator_base<true>, iterator_base<false> >::type iterator;
            
            iterator begin() { return iterator(*this,this->first()); } 
            const_iterator begin() const { return const_iterator(*this,this->first()); } 
            const_iterator cbegin() const { return const_iterator(*this,this->first()); } 
            
            iterator end() { return iterator(*this,this->nil()); } 
            const_iterator end() const { return const_iterator(*this,this->nil()); } 
            const_iterator cend() const { return const_iterator(*this,this->nil()); } 
            
            bool empty() const { return this->size1 == 0; } 
            size_t size() const { return this->size1; } 
            constexpr size_t max_size() const {
                return NodeAllocator::max_nodes ? NodeAllocator::max_nodes : std::numeric_limits<size_t>::max();
            }
            
/* 2. add / remove */
            //~ void clear(); -- defined in orbtree_base already, no need to add functionality
            
            /* for insert, we need to distinguish between map and multimap
             * create a return typedef which is either an iterator or a pair */
            typedef typename std::conditional<multi, iterator, std::pair<iterator, bool> >::type insert_type;
            
        protected:
            template<bool multi_ = multi>
            typename std::enable_if<multi_,insert_type>::type insert_helper(const value_type& v) {
                return iterator(*this, orbtree_base<NodeAllocator, Compare, NVFunc, multi>::insert(v).first);
            }
            template<bool multi_ = multi>
            typename std::enable_if<!multi_,insert_type>::type insert_helper(const value_type& v) {
                auto x = orbtree_base<NodeAllocator, Compare, NVFunc, multi>::insert(v);
                return std::pair<iterator,bool>(iterator(*this,x.first),x.second);
            }
            template<bool multi_ = multi>
            typename std::enable_if<multi_,insert_type>::type insert_helper(value_type&& v) {
                return iterator(*this, orbtree_base<NodeAllocator, Compare, NVFunc, multi>::insert(std::move(v)).first);
            }
            template<bool multi_ = multi>
            typename std::enable_if<!multi_,insert_type>::type insert_helper(value_type&& v) {
                auto x = orbtree_base<NodeAllocator, Compare, NVFunc, multi>::insert(std::move(v));
                return std::pair<iterator,bool>(iterator(*this,x.first),x.second);
            }
            
            
            template<class... Args, bool multi_ = multi>
            typename std::enable_if<multi_,insert_type>::type emplace_helper(Args&... args) {
                return iterator(*this, orbtree_base<NodeAllocator, Compare, NVFunc, multi>::emplace(std::forward<Args...>(args...)).first);
            }
            template<class... Args, bool multi_ = multi>
            typename std::enable_if<!multi_,insert_type>::type emplace_helper(Args&... args) {
                auto x = orbtree_base<NodeAllocator, Compare, NVFunc, multi>::emplace(std::forward<Args...>(args...));
                return std::pair<iterator,bool>(iterator(*this,x.first),x.second);
            }
            
            
        public:
            
            insert_type insert(const value_type& v) { return insert_helper(v); }
            insert_type insert(value_type&& v) { return insert_helper(std::move(v)); }
            
            
            
            iterator insert(const_iterator hint, const value_type& v) {
                if(hint.n == this->nil()) return iterator(*this, orbtree_base<NodeAllocator, Compare, NVFunc, multi>::insert(v).first);
                else return iterator(*this, orbtree_base<NodeAllocator, Compare, NVFunc, multi>::insert(hint.n,v));
            }
            iterator insert(const_iterator hint, value_type&& v) {
                if(hint.n == this->nil()) return iterator(*this, orbtree_base<NodeAllocator, Compare, NVFunc, multi>::insert(std::move(v)).first);
                else return iterator(*this, orbtree_base<NodeAllocator, Compare, NVFunc, multi>::insert(hint.n,std::move(v)));
            }
            
            
            template<class InputIt> void insert(InputIt first, InputIt last) {
                for(;first!=last;++first) orbtree::insert(*first);
            }
            
            template<class... Args> insert_type emplace(Args&&... args) { return emplace_helper(std::forward<Args...>(args...)); }
            template<class... Args> iterator emplace_hint(const_iterator hint, Args&&... args) {
                if(hint.n == this->nil()) return iterator(*this, orbtree_base<NodeAllocator, Compare, NVFunc, multi>::emplace(std::forward<Args...>(args...)).first);
                else return iterator(*this, orbtree_base<NodeAllocator, Compare, NVFunc, multi>::emplace_hint(hint, std::forward<Args...>(args...)));
            }
            
             
            //~ iterator erase(iterator pos) { return iterator(*this,orbtree_base<NodeAllocator, Compare, NVFunc, multi>::erase(pos.n)); }
            iterator erase(const_iterator pos) { return iterator(*this,orbtree_base<NodeAllocator, Compare, NVFunc, multi>::erase(pos.n)); }
            iterator erase(const_iterator first, const_iterator last) {
                if(first == last) return iterator(*this,first.n);
                iterator x = erase(first);
                while(x != last) x = erase(x);
                return x;
            }
            
            size_t erase(const key_type& k) {
                size_t r = 0;
                for(NodeHandle n = orbtree_base<NodeAllocator, Compare, NVFunc, multi>::lower_bound(k);
                    n != this->nil() && n != this->Invalid && this->compare_key_equals(n,k);
                    n = orbtree_base<NodeAllocator, Compare, NVFunc, multi>::erase(n)) r++;
                return r;
            }
            
            size_t count(const key_type& k) const {
                size_t r = 0;
                for(NodeHandle n = orbtree_base<NodeAllocator, Compare, NVFunc, multi>::lower_bound(k);
                    n != this->nil() && n != this->Invalid && this->compare_key_equals(n,k); n = this->next(n)) r++;
                return r;
            }
            template<class K>
            size_t count(const K& k) const {
                size_t r = 0;
                for(NodeHandle n = orbtree_base<NodeAllocator, Compare, NVFunc, multi>::lower_bound(k);
                    n != this->nil() && n != this->Invalid && this->compare_key_equals(n,k); n = this->next(n)) r++;
                return r;
            }
            
/* 3. search based on key */
            
            
            iterator find(const key_type& k) {
                return iterator(*this,orbtree_base<NodeAllocator, Compare, NVFunc, multi>::find(k));
            }
            const_iterator find(const key_type& k) const {
                return const_iterator(*this,orbtree_base<NodeAllocator, Compare, NVFunc, multi>::find(k));
            }
            template<class K> iterator find(const K& k) {
                return iterator(*this,orbtree_base<NodeAllocator, Compare, NVFunc, multi>::find(k));
            }
            template<class K> const_iterator find(const K& k) const {
                return const_iterator(*this,orbtree_base<NodeAllocator, Compare, NVFunc, multi>::find(k));
            }
            
            
            iterator lower_bound(const key_type& k) {
                return iterator(*this,orbtree_base<NodeAllocator, Compare, NVFunc, multi>::lower_bound(k));
            }
            const_iterator lower_bound(const key_type& k) const {
                return const_iterator(*this,orbtree_base<NodeAllocator, Compare, NVFunc, multi>::lower_bound(k));
            }
            template<class K> iterator lower_bound(const K& k) {
                return iterator(*this,orbtree_base<NodeAllocator, Compare, NVFunc, multi>::lower_bound(k));
            }
            template<class K> const_iterator lower_bound(const K& k) const {
                return const_iterator(*this,orbtree_base<NodeAllocator, Compare, NVFunc, multi>::lower_bound(k));
            }
            iterator upper_bound(const key_type& k) {
                return iterator(*this,orbtree_base<NodeAllocator, Compare, NVFunc, multi>::upper_bound(k));
            }
            const_iterator upper_bound(const key_type& k) const {
                return const_iterator(*this,orbtree_base<NodeAllocator, Compare, NVFunc, multi>::upper_bound(k));
            }
            template<class K> iterator upper_bound(const K& k) {
                return iterator(*this,orbtree_base<NodeAllocator, Compare, NVFunc, multi>::upper_bound(k));
            }
            template<class K> const_iterator upper_bound(const K& k) const {
                return const_iterator(*this,orbtree_base<NodeAllocator, Compare, NVFunc, multi>::upper_bound(k));
            }
            
            std::pair<iterator,iterator> equal_range(const key_type& k) {
                return std::pair<iterator,iterator>(lower_bound(k),upper_bound(k));
            }
            std::pair<const_iterator,const_iterator> equal_range(const key_type& k) const {
                return std::pair<const_iterator,const_iterator>(lower_bound(k),upper_bound(k));
            }
            template<class K> std::pair<iterator,iterator> equal_range(const K& k) {
                return std::pair<iterator,iterator>(lower_bound(k),upper_bound(k));
            }
            template<class K> std::pair<const_iterator,const_iterator> equal_range(const K& k) const {
                return std::pair<const_iterator,const_iterator>(lower_bound(k),upper_bound(k));
            }
            
            bool contains(const key_type& k) const {
                return orbtree_base<NodeAllocator, Compare, NVFunc, multi>::find(k) != this->nil();
            }
            template<class K> bool contains(const K& k) const {
                return orbtree_base<NodeAllocator, Compare, NVFunc, multi>::find(k) != this->nil();
            }
            
            
        public:
            template<bool simple_ = simple>
            void get_sum_node(const_iterator it, typename std::enable_if<!simple_,NVType*>::type res) const {
                if(it == cend()) this->get_norm_fv(res);
                this->get_sum_fv_node(it.n,res);
            }
            template<bool simple_ = simple>
            NVType get_sum_node(typename std::enable_if<simple_,const_iterator>::type it) const {
                NVType res;
                if(it == cend()) this->get_norm_fv(&res);
                this->get_sum_fv_node(it.n,&res);
                return res;
            }
            
            
            template<bool simple_ = simple>
            void get_sum(const key_type& k, typename std::enable_if<!simple_,NVType*>::type res) const {
                auto it = lower_bound(k);
                get_sum_node(it,res);
            }
            template<bool simple_ = simple>
            NVType get_sum(typename std::enable_if<simple_,const key_type&>::type k) const {
                auto it = lower_bound(k);
                return get_sum_node(it);
            }
            
            template<class K, bool simple_ = simple>
            void get_sum(const K& k, typename std::enable_if<!simple_,NVType*>::type res) const {
                auto it = lower_bound(k);
                get_sum_node(it,res);
            }
            template<class K, bool simple_ = simple>
            NVType get_sum(typename std::enable_if<simple_,const K&>::type k) const {
                auto it = lower_bound(k);
                return get_sum_node(it);
            }
            
            template<bool simple_ = simple>
            void get_norm(typename std::enable_if<!simple_,NVType*>::type res) const { this->get_norm_fv(res); }
            template<bool simple_ = simple> NVType get_norm(typename std::enable_if<simple_,void*>::type k = 0) const {
                NVType res;
                this->get_norm_fv(&res);
                return res;
            }
            
            
    };
    
    
    template<class NVFunc> 
    struct NVFunc_Adapter_Simple {
        typedef typename NVFunc::result_type result_type;

        constexpr unsigned int get_nr() const { return 1; }

        void operator ()(const typename NVFunc::argument_type& node_value, result_type* res) const {
            *res = f(node_value);
        }
        NVFunc f;
        NVFunc_Adapter_Simple() { }
        explicit NVFunc_Adapter_Simple(const NVFunc& f_):f(f_) { }
        explicit NVFunc_Adapter_Simple(NVFunc&& f_):f(f_) { }
        template<class T>
        explicit NVFunc_Adapter_Simple(const T& t):f(t) { }
    };
    
    
    /* basic classes */
    
    /* general set and multiset -- needs to be given a node value type and function */
    /* function has to have a defined return type */
    template<class Key, class NVFunc, class Compare = std::less<Key> >
    using orbset = orbtree< NodeAllocatorPtr< KeyOnly<Key>, typename NVFunc::result_type >, Compare, NVFunc, false >;
    
    template<class Key, class NVFunc, class Compare = std::less<Key> >
    using simple_set = orbtree< NodeAllocatorPtr< KeyOnly<Key>, typename NVFunc::result_type, true >,
        Compare, NVFunc_Adapter_Simple<NVFunc>, false, true >;
    
    
    template<class Key, class NVFunc, class Compare = std::less<Key> >
    using orbmultiset = orbtree< NodeAllocatorPtr< KeyOnly<Key>, typename NVFunc::result_type >, Compare, NVFunc, true >;
    
    template<class Key, class NVFunc, class Compare = std::less<Key> >
    using simple_multiset = orbtree< NodeAllocatorPtr< KeyOnly<Key>, typename NVFunc::result_type, true >,
        Compare, NVFunc_Adapter_Simple<NVFunc>, true, true >;
    
    
    template<class Key, class NVFunc, class IndexType = uint32_t, class Compare = std::less<Key> >
    using orbsetC = orbtree< NodeAllocatorCompact< KeyOnly<Key>, typename NVFunc::result_type, IndexType >, Compare, NVFunc, false >;
    
    template<class Key, class NVFunc, class IndexType = uint32_t, class Compare = std::less<Key> >
    using simple_setC = orbtree< NodeAllocatorCompact< KeyOnly<Key>, typename NVFunc::result_type, IndexType >,
        Compare, NVFunc_Adapter_Simple<NVFunc>, false, true >;
    
    
    
    template<class Key, class NVFunc, class IndexType = uint32_t, class Compare = std::less<Key> >
    using orbmultisetC = orbtree< NodeAllocatorCompact< KeyOnly<Key>, typename NVFunc::result_type, IndexType >, Compare, NVFunc, true >;
    
    template<class Key, class NVFunc, class IndexType = uint32_t, class Compare = std::less<Key> >
    using simple_multisetC = orbtree< NodeAllocatorCompact< KeyOnly<Key>, typename NVFunc::result_type, IndexType >,
        Compare, NVFunc_Adapter_Simple<NVFunc>, true, true >;
        
    
    /* more specialized version: order statistic set / multiset with compact nodes (i.e. calculates ranks, either 32-bit or 64-bit) */
    template<class KeyValueType, class NVType = uint32_t> struct RankFunc {
        static_assert(std::is_integral<NVType>::value, "rank variable must be integral!\n");
        typedef KeyValueType argument_type;
        NVType operator ()(const KeyValueType& k) const { return (NVType)1; }
        typedef NVType result_type;
    };
    
    

    template<class NVFunc> 
    struct NVFunc_Adapter_Vec {
        NVFunc f;
        const std::vector<typename NVFunc::ParType> pars;
        typedef typename NVFunc::result_type result_type;
        unsigned int get_nr() const { return pars.size(); }
        void operator ()(const typename NVFunc::argument_type& node_value, result_type* res) const {
            for(size_t i=0;i<pars.size();i++) res[i] = f(node_value,pars[i]);
        }
        NVFunc_Adapter_Vec() = delete; /* need parameter vector at least */
        explicit NVFunc_Adapter_Vec(const std::vector<typename NVFunc::ParType>& pars_, const NVFunc& f_ = NVFunc()):f(f_),pars(pars_) { }
        explicit NVFunc_Adapter_Vec(std::vector<typename NVFunc::ParType>&& pars_, const NVFunc& f_ = NVFunc()):f(f_),pars(std::move(pars_)) { }
        explicit NVFunc_Adapter_Vec(const std::vector<typename NVFunc::ParType>& pars_, NVFunc&& f_):f(std::move(f_)),pars(pars_) { }
        explicit NVFunc_Adapter_Vec(std::vector<typename NVFunc::ParType>&& pars_, NVFunc&& f_):f(std::move(f_)),pars(std::move(pars_)) { }
    };
    
    
    template<class KeyType> struct NVPower {
        double operator () (const KeyType& k, double a) const {
            double x = (double)k;
            return pow(x,a);
        }
        typedef double result_type;
        typedef KeyType argument_type;
        typedef double ParType;
    };
    
    template<class KeyType> struct NVPowerMulti {
        double operator () (const KeyType& k, double a) const {
            double x = (double)(k.first);
            double n = (double)(k.second);
            return n*pow(x,a);
        }
        typedef double result_type;
        typedef KeyType argument_type;
        typedef double ParType;
    };
    
    template<class KeyType> using NVPower2 = NVFunc_Adapter_Vec<NVPower<KeyType> >;
    template<class KeyType> using NVPowerMulti2 = NVFunc_Adapter_Vec<NVPowerMulti<KeyType> >;
    
    template<class Key, class NVType = uint32_t, class Compare = std::less<Key> >
    using rankset = orbtree< NodeAllocatorPtr< KeyOnly<Key>, NVType, true >, Compare,
            NVFunc_Adapter_Simple<RankFunc<Key, NVType> >, false, true >;
    
    template<class Key, class NVType = uint32_t, class Compare = std::less<Key> >
    using rankmultiset = orbtree< NodeAllocatorPtr< KeyOnly<Key>, NVType, true >, Compare,
            NVFunc_Adapter_Simple<RankFunc<Key, NVType> >, true, true >;
    
    template<class Key, class NVType = uint32_t, class IndexType = uint32_t, class Compare = std::less<Key> >
    using ranksetC = orbtree< NodeAllocatorCompact< KeyOnly<Key>, NVType, IndexType >, Compare,
            NVFunc_Adapter_Simple<RankFunc<Key, NVType> >, false, true >;
    
    template<class Key, class NVType = uint32_t, class IndexType = uint32_t, class Compare = std::less<Key> >
    using rankmultisetC = orbtree< NodeAllocatorCompact< KeyOnly<Key>, NVType, IndexType >, Compare,
            NVFunc_Adapter_Simple<RankFunc<Key, NVType> >, true, true >;
    
        
    /* map types -- extra step in adding accessor functions (only for map, multimap does not have them)
     * note: this definition does not explicitely require KeyValue to have value, but the extra functions rely on Value being present
     * 
     * note: only const values are supported since modifying the value might modify the rank function as well */
    template<class NodeAllocator, class Compare, class NVFunc, bool simple = false>
    class orbtreemap : public orbtree<NodeAllocator, Compare, NVFunc, false, simple> {
        protected:
            typedef typename orbtree<NodeAllocator, Compare, NVFunc, false, simple>::NodeHandle NodeHandle;
            typedef typename orbtree<NodeAllocator, Compare, NVFunc, false, simple>::KeyValue KeyValue;
        
        public:
            /* typedefs */
            typedef typename orbtree<NodeAllocator, Compare, NVFunc, false, simple>::value_type value_type;
            typedef typename orbtree<NodeAllocator, Compare, NVFunc, false, simple>::key_type key_type;
            typedef typename orbtree<NodeAllocator, Compare, NVFunc, false, simple>::size_type size_type;
            typedef typename orbtree<NodeAllocator, Compare, NVFunc, false, simple>::difference_type difference_type;
            typedef typename orbtree<NodeAllocator, Compare, NVFunc, false, simple>::iterator iterator;
            typedef typename orbtree<NodeAllocator, Compare, NVFunc, false, simple>::const_iterator const_iterator;
            typedef typename NodeAllocator::KeyValue::MappedType mapped_type;
            
            explicit orbtreemap(const NVFunc& f_ = NVFunc(), const Compare& c_ = Compare()) :
                orbtree<NodeAllocator, Compare, NVFunc, false, simple>(f_,c_) { }
            explicit orbtreemap(NVFunc&& f_,const Compare& c_ = Compare()) : orbtree<NodeAllocator, Compare, NVFunc, false, simple>(f_,c_) { }
            template <class T>
            explicit orbtreemap(const T& t, const Compare& c_ = Compare()) : orbtree<NodeAllocator, Compare, NVFunc, false, simple>(t,c_) { }
            

            const mapped_type& at(const key_type& k) const {
                NodeHandle n = orbtree_base<NodeAllocator, Compare, NVFunc, false>::find(k);
                if(n == this->nil()) throw std::out_of_range("orbtreemap::at(): key not present in map!\n");
                return get_node(n).get_key_value().value();
            }

            template<class K> const mapped_type& at(const K& k) const {
                NodeHandle n = orbtree_base<NodeAllocator, Compare, NVFunc, false>::find(k);
                if(n == this->nil()) throw std::out_of_range("orbtreemap::at(): key not present in map!\n");
                return get_node(n).get_key_value().value();
            }
            

            const mapped_type& operator[](const key_type& k) {
                NodeHandle n = orbtree_base<NodeAllocator, Compare, NVFunc, false>::find(k);
                if(n == this->nil()) n = orbtree_base<NodeAllocator, Compare, NVFunc, false>::insert(value_type(k,mapped_type()));
                return get_node(n).get_key_value().value();
            }
            
            bool set_value(const key_type& k, const mapped_type& v) {
                std::pair<iterator,bool> tmp = orbtree<NodeAllocator, Compare, NVFunc, false, simple>::insert(value_type(k,v));
                if(tmp.second == false) tmp.first.set_value(v);
                return tmp.second;
            }
            bool set_value(key_type&& k, const mapped_type& v) {
                std::pair<iterator,bool> tmp = orbtree<NodeAllocator, Compare, NVFunc, false, simple>::insert(value_type(std::move(k),v));
                if(tmp.second == false) tmp.first.set_value(v);
                return tmp.second;
            }
            bool set_value(const key_type& k, mapped_type&& v) {
                auto it = orbtree<NodeAllocator, Compare, NVFunc, false, simple>::find(k);
                if(it == orbtree<NodeAllocator, Compare, NVFunc, false, simple>::end()) {
                    orbtree<NodeAllocator, Compare, NVFunc, false, simple>::insert(value_type(k,std::move(v)));
                    return true;
                }
                it.set_value(std::move(v));
                return false;
            }
            bool set_value(key_type&& k, mapped_type&& v) {
                auto it = orbtree<NodeAllocator, Compare, NVFunc, false, simple>::find(k);
                if(it == orbtree<NodeAllocator, Compare, NVFunc, false, simple>::end()) {
                    orbtree<NodeAllocator, Compare, NVFunc, false, simple>::insert(value_type(std::move(k),std::move(v)));
                    return true;
                }
                it.set_value(std::move(v));
                return false;
            }
            
            void update_value(const key_type& k, const mapped_type& v) {
                NodeHandle n = orbtree_base<NodeAllocator, Compare, NVFunc, false>::find(k);
                if(n == this->nil()) throw std::out_of_range("orbtreemap::at(): key not present in map!\n");
                orbtree_base<NodeAllocator, Compare, NVFunc, false>::update_value(n,v);
            }
            void update_value(const key_type& k, mapped_type&& v) {
                NodeHandle n = orbtree_base<NodeAllocator, Compare, NVFunc, false>::find(k);
                if(n == this->nil()) throw std::out_of_range("orbtreemap::at(): key not present in map!\n");
                orbtree_base<NodeAllocator, Compare, NVFunc, false>::update_value(n,std::move(v));
            }
    };
    
    template<class Key, class Value, class NVFunc, class Compare = std::less<Key> >
    using orbmap = orbtreemap< NodeAllocatorPtr< KeyValue<Key,Value>, typename NVFunc::result_type >, Compare, NVFunc >;
    
    template<class Key, class Value, class NVFunc, class Compare = std::less<Key> >
    using simple_map = orbtreemap< NodeAllocatorPtr< KeyValue<Key,Value>, typename NVFunc::result_type, true >,
        Compare, NVFunc_Adapter_Simple<NVFunc>, true >;
    
    
    template<class Key, class Value, class NVFunc, class Compare = std::less<Key> >
    using orbmultimap = orbtree< NodeAllocatorPtr< KeyValue<Key,Value>, typename NVFunc::result_type >, Compare, NVFunc, true >;
    
    template<class Key, class Value, class NVFunc, class Compare = std::less<Key> >
    using simple_multimap = orbtree< NodeAllocatorPtr< KeyValue<Key,Value>, typename NVFunc::result_type, true >,
        Compare, NVFunc_Adapter_Simple<NVFunc>, true, true>;
    
    
    template<class Key, class Value, class NVFunc, class IndexType = uint32_t, class Compare = std::less<Key> >
    using orbmapC = orbtreemap< NodeAllocatorCompact< KeyValue<Key,Value>, typename NVFunc::result_type, IndexType>, Compare, NVFunc >;
    
    template<class Key, class Value, class NVFunc, class IndexType = uint32_t, class Compare = std::less<Key> >
    using simple_mapC = orbtreemap< NodeAllocatorCompact< KeyValue<Key,Value>, typename NVFunc::result_type, IndexType>,
        Compare, NVFunc_Adapter_Simple<NVFunc>, true >;
    
    
    template<class Key, class Value, class NVFunc, class IndexType = uint32_t, class Compare = std::less<Key> >
    using orbmultimapC = orbtree< NodeAllocatorCompact< KeyValue<Key,Value>, typename NVFunc::result_type, IndexType>, Compare, NVFunc, true >;
    
    template<class Key, class Value, class NVFunc, class IndexType = uint32_t, class Compare = std::less<Key> >
    using simple_multimapC = orbtree< NodeAllocatorCompact< KeyValue<Key,Value>, typename NVFunc::result_type, IndexType>,
        Compare, NVFunc_Adapter_Simple<NVFunc>, true, true >;
    
    
    template<class Key, class Value, class NVType, class Compare = std::less<Key> >
    using rankmap = orbtreemap< NodeAllocatorPtr< KeyValue<Key,Value>, NVType, true >, Compare,
            NVFunc_Adapter_Simple< RankFunc<NVType,KeyValue<Key,Value> > >, true >;
    
    template<class Key, class Value, class NVType, class Compare = std::less<Key> >
    using rankmultimap = orbtree< NodeAllocatorPtr< KeyValue<Key,Value>, NVType, true >, Compare,
            NVFunc_Adapter_Simple< RankFunc<NVType,KeyValue<Key,Value> > >, true, true >;
    
    template<class Key, class Value, class NVType, class IndexType = uint32_t, class Compare = std::less<Key> >
    using rankmapC = orbtreemap< NodeAllocatorCompact< KeyValue<Key,Value>, NVType, IndexType >, Compare,
            NVFunc_Adapter_Simple< RankFunc<NVType,KeyValue<Key,Value> > >, true >;
    
    template<class Key, class Value, class NVType, class IndexType = uint32_t, class Compare = std::less<Key> >
    using rankmultimapC = orbtree< NodeAllocatorCompact< KeyValue<Key,Value>, NVType, IndexType >, Compare,
            NVFunc_Adapter_Simple< RankFunc<NVType,KeyValue<Key,Value> > >, true, true >;
    
}

#undef CONSTEXPR

#endif