orbtree_node.h

/*  -*- C++ -*-
 * orbtree_node.h -- generalized order statistic red-black tree implementation
 *  tree nodes and node allocators
 * 
 * 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_NODE_H
#define ORBTREE_NODE_H

#include <functional>
#include <stdexcept>
#include <type_traits>
#include <limits>
#include <utility>
#include <algorithm>


//~ #ifdef USE_STACKED_VECTOR
#include "vector_stacked.h"
//~ template <class T> using compact_vector = stacked_vector::vector<T>;
//~ #else
#include "vector_realloc.h"
//~ template <class T> using compact_vector = realloc_vector::vector<T>;
//~ #endif

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


namespace orbtree {
    
    template<class T1, class T2>
    struct trivial_pair {
        T1 first;
        T2 second;
        trivial_pair() = default;
        trivial_pair(const T1& x, const T2& y):first(x),second(y) { }
        trivial_pair(const T1& x, T2&& y):first(x),second(std::move(y)) { }
        trivial_pair(T1&& x, const T2& y):first(std::move(x)),second(y) { }
        trivial_pair(T1&& x, T2&& y):first(std::move(x)),second(std::move(y)) { }
        trivial_pair(const std::pair<T1,T2>& p):first(p.first),second(p.second) { }
        operator std::pair<T1,T2>() const { return std::pair<T1,T2>(first,second); }
        operator trivial_pair<const T1,T2>() const { return trivial_pair<const T1,T2>(first,second); }
    };
    
    /* key and optionally value classes */
    template<class Key> struct KeyOnly {
        protected:
            Key k; 
        public:
            typedef Key KeyType;
            typedef const Key ValueType;
            
            explicit KeyOnly(const Key& k_):k(k_) { }
            explicit KeyOnly(Key&& k_):k(std::move(k_)) { }
            template<class... T> explicit KeyOnly(T&&... args) : k(std::forward<T...>(args...)) { }
            KeyOnly():k() { }
            const Key& key() const { return k; }
            
            ValueType& keyvalue() const { return k; } 
            static const Key& key(const ValueType& k) { return k; }
            
            static const bool keyonly = true; 
            void swap(KeyOnly& k_) {
                using std::swap;
                swap(k,k_.k);
            }
    };
    template<class Key, class Value, template<class,class> class pair_type = trivial_pair> struct KeyValue {
        protected:
            pair_type<Key, Value> p; 
        public:
            typedef Key KeyType;
            typedef Value MappedType;
            /* note: key is not const to make things simpler -- all accessor functions return const ValueType */
            typedef pair_type<Key, Value> ValueType;
            
            explicit KeyValue(const std::pair<Key,Value>& kv):p(kv) { }
            explicit KeyValue(pair_type<Key,Value>&& kv):p(std::move(kv)) { }
            explicit KeyValue(const pair_type<Key,Value>& kv):p(kv) { }
            KeyValue():p() { }
            const Key& key() const { return p.first; }
            Value& value() { return p.second; }
            const Value& value() const { return p.second; }
            
            ValueType& keyvalue() { return p; } 
            const ValueType& keyvalue() const { return p; } 
            static const Key& key(const ValueType& kv) { return kv.first; }
            
            static const bool keyonly = false; 
            void swap(KeyValue& k_) {
                using std::swap;
                swap(p,k_.p);
            }
    };
    
    template<class Key>
    void swap(KeyOnly<Key>& x, KeyOnly<Key>& y) {
        x.swap(y);
    }
    template<class Key,class Value>
    void swap(KeyValue<Key,Value>& x, KeyValue<Key,Value>& y) {
        x.swap(y);
    }
     
    
    
    
    template<class KeyValueT, class NVTypeT, bool simple = false>
    class NodeAllocatorPtr {
        protected: /* everything is protected, red-black tree class inherits from this */
            
            typedef KeyValueT KeyValue;
            typedef NVTypeT NVType;
            
            struct Node {
                protected:
                    KeyValue kv; 
                    typename std::conditional<simple, NVType, NVType*>::type partialsum;
                    Node* parent;
                    Node* left;
                    Node* right;
                    bool red;
                
                public:
                    /* node functionality */
                    Node(const KeyValue& kv_) : kv(kv_), partialsum(0) { }
                    Node(KeyValue&& kv_) : kv(std::move(kv_)), partialsum(0) { }
                    Node():kv(), partialsum(0) { }
                    template<class... T> Node(T&&... args) : kv(std::forward<T...>(args...)), partialsum(0) { }
                    /* note: destructor only deletes the partial sum, does not recursively delete the children */
                    template<bool simple_ = simple> void do_delete(typename std::enable_if<simple_,void*>::type = 0) { }
                    template<bool simple_ = simple> void do_delete(typename std::enable_if<!simple_,void*>::type = 0) {
                        if(partialsum) delete[]partialsum;
                    }
                    ~Node() { do_delete(); }
                    
                    KeyValue& get_key_value() { return kv; }
                    const KeyValue& get_key_value() const { return kv; }
                    
                    bool is_red() const { return red; } 
                    bool is_black() const { return !red; } 
                    void set_red() { red = true; } 
                    void set_black() { red = false; } 
                    
                    /* get / set for parent, left and right -- node is considered opaque
                     * by the tree to allow different optimizations here */
                    const Node* get_parent() const { return parent; } 
                    const Node* get_left() const { return left; } 
                    const Node* get_right() const { return right; } 
                    void set_parent(const Node* p) { parent = const_cast<Node*>(p); } 
                    void set_left(const Node* x) { left = const_cast<Node*>(x); } 
                    void set_right(const Node* x) { right = const_cast<Node*>(x); } 
                
                    friend class NodeAllocatorPtr<KeyValueT,NVTypeT,simple>;
            };
            
            typedef const Node* NodeHandle;
            
            Node* root;
            Node* nil; 
            
            const unsigned int nv_per_node;
            unsigned int get_nv_per_node() const { return nv_per_node; }
            
            NodeAllocatorPtr():root(0),nil(0),nv_per_node(1) {
                root = new_node();
                nil = new_node();
            }
            explicit NodeAllocatorPtr(unsigned int nv_per_node_):root(0),nil(0),nv_per_node(nv_per_node_) {
                if CONSTEXPR (simple) if(nv_per_node != 1)
                    throw std::runtime_error("For simple tree, weight function can only return one component!\n");
                root = new_node();
                nil = new_node();
            }
            ~NodeAllocatorPtr() { 
                if(root) free_tree_nodes_r(root);
                if(nil) delete nil;
            }
            
            Node& get_node(NodeHandle x) { return *const_cast<Node*>(x); }
            const Node& get_node(const NodeHandle x) const { return *x; }
            
            constexpr static Node* Invalid = 0; /* null pointer */
            const static size_t max_nodes = 0; /* unlimited */
            Node* new_node() { Node* n = new Node(); init_node(n); return n; }
            Node* new_node(const KeyValue& kv) { Node* n = new Node(kv); init_node(n); return n; }
            Node* new_node(KeyValue&& kv) { Node* n = new Node(std::move(kv)); init_node(n); return n; }
            template<class... T>
            Node* new_node(T&&... kv) { Node* n = new Node(std::forward<T>(kv)...); init_node(n); return n; }
            
            void free_node(NodeHandle n) { delete (Node*)n; }
            void clear_tree() { 
                if(root) {
                    Node* n = root;
                    if(n->left && n->left != nil) free_tree_nodes_r((Node*)(n->left));
                    if(n->right && n->right != nil) free_tree_nodes_r((Node*)(n->right));
                    n->left = 0;
                    n->right = 0;
                }
            }
            
            void free_tree_nodes_r(Node* n) {
                if(n->left && n->left != nil) free_tree_nodes_r((Node*)(n->left));
                if(n->right && n->right != nil) free_tree_nodes_r((Node*)(n->right));
                delete n;
            }
            
            template <bool simple_ = simple>
            void init_node(typename std::enable_if<simple_, Node*>::type n) {
                if(n) {
                    n->parent = Invalid;
                    n->left = Invalid;
                    n->right = Invalid;
                }
                if(!n) throw std::runtime_error("NodeAllocatorPtr::init_node(): out of memory!\n");
            }
            template <bool simple_ = simple>
            void init_node(typename std::enable_if<!simple_, Node*>::type n) {
                if(n) {
                    n->parent = Invalid;
                    n->left = Invalid;
                    n->right = Invalid;
                    n->partialsum = new NVType[nv_per_node];
                }
                if( !n || ! (n->partialsum) ) throw std::runtime_error("NodeAllocatorPtr::init_node(): out of memory!\n");
            }
            
            template<bool simple_ = simple>
            void get_node_sum(NodeHandle n, typename std::enable_if<simple_,NVType*>::type s) const {
                *s = n->partialsum;
            }
            template<bool simple_ = simple>
            void get_node_sum(NodeHandle n, typename std::enable_if<!simple_,NVType*>::type s) const {
                for(unsigned int i = 0; i < nv_per_node; i++) s[i] = n->partialsum[i];
            }
            template<bool simple_ = simple>
            void set_node_sum(NodeHandle n1, typename std::enable_if<simple_,const NVType*>::type s) { 
                Node* n = const_cast<Node*>(n1);
                n->partialsum = *s;
            }
            template<bool simple_ = simple>
            void set_node_sum(NodeHandle n1, typename std::enable_if<!simple_,const NVType*>::type s) { 
                Node* n = const_cast<Node*>(n1);
                for(unsigned int i = 0; i < nv_per_node; i++) n->partialsum[i] = s[i];
            }
    };
    
    
    template<class KeyValueT, class NVTypeT, class IndexType>
    class NodeAllocatorCompact {
        protected:
            //~ static_assert(std::is_trivially_copyable<KeyValueT>::value,
                //~ "Key and Value must be trivially copyable to use compact flat allocator!\n");
            typedef IndexType NodeHandle;
            typedef KeyValueT KeyValue;
            typedef NVTypeT NVType;
        
        private:
            static constexpr IndexType redbit = 1U << (std::numeric_limits<IndexType>::digits - 1);
            static constexpr IndexType max_nodes = redbit - 1;
            static constexpr IndexType deleted_indicator = (max_nodes | redbit); /* 0xFFFFFFFFh */
            
        protected:
            struct Node {
                protected:
                    KeyValue kv;
                    IndexType parent;
                    IndexType left; 
                    IndexType right; 
                    /* red-black flag is stored inside parent */
                    
                public:
                    Node(const KeyValue& kv_) : kv(kv_), parent(NodeAllocatorCompact::Invalid),
                        left(NodeAllocatorCompact::Invalid), right(NodeAllocatorCompact::Invalid) { }
                    Node(KeyValue&& kv_) : kv(kv_), parent(NodeAllocatorCompact::Invalid),
                        left(NodeAllocatorCompact::Invalid), right(NodeAllocatorCompact::Invalid) { }
                    template<class... T> Node(T&&... args) : kv(std::forward<T...>(args...)), parent(NodeAllocatorCompact::Invalid),
                        left(NodeAllocatorCompact::Invalid), right(NodeAllocatorCompact::Invalid) { }
                    Node():kv(), parent(NodeAllocatorCompact::Invalid),
                        left(NodeAllocatorCompact::Invalid), right(NodeAllocatorCompact::Invalid) { }
                                        
                    KeyValue& get_key_value() { return kv; }
                    const KeyValue& get_key_value() const { return kv; }
                    bool is_red() const { return parent & NodeAllocatorCompact::redbit; }
                    bool is_black() const { return !is_red(); }
                    void set_red() { parent |= NodeAllocatorCompact::redbit; }
                    void set_black() { parent &= (~NodeAllocatorCompact::redbit); }
                    
                    NodeHandle get_parent() const { return parent & (~NodeAllocatorCompact::redbit); }
                    NodeHandle get_left() const { return left; }
                    NodeHandle get_right() const { return right; }
                    void set_parent(NodeHandle p) {
                        if(p > NodeAllocatorCompact::max_nodes) throw std::runtime_error("NodeAllocatorCompact::Node::set_parent(): parent ID too large!\n");
                        parent = p | (parent & NodeAllocatorCompact::redbit);
                    }
                    void set_left(NodeHandle x) { left = x; }
                    void set_right(NodeHandle x) { right = x; }
                    
                    void set_deleted() { parent = NodeAllocatorCompact::deleted_indicator; }
                    bool is_deleted() const { return (parent == NodeAllocatorCompact::deleted_indicator); }
                    
                    /* swap contents with other node */
                    void swap(Node& n) {
                        using std::swap;
                        swap(kv,n.kv);
                        swap(parent,n.parent);
                        swap(left,n.left);
                        swap(right,n.right);
                    }
                    
                    friend class NodeAllocatorCompact<KeyValueT,NVTypeT,IndexType>;
            };
            
        private:

#ifdef USE_STACKED_VECTOR
            typedef stacked_vector::vector<Node> node_vector_type;
#else           
            typedef typename std::conditional< std::is_trivially_copyable<KeyValueT>::value,
                realloc_vector::vector<Node>, stacked_vector::vector<Node> >::type node_vector_type;
#endif
            
            realloc_vector::vector<NVType> nvarray; 
            node_vector_type nodes; 
            const unsigned int nv_per_node; 
            size_t n_del; 
            NodeHandle deleted_nodes_head; 

        protected:
            static constexpr NodeHandle Invalid = max_nodes;
            NodeHandle root; 
            NodeHandle nil; 
            NodeAllocatorCompact():nv_per_node(1),n_del(0),deleted_nodes_head(Invalid),root(Invalid),nil(Invalid) { 
                root = new_node();
                nil = new_node();
            }
            explicit NodeAllocatorCompact(unsigned int nv_per_node_):nv_per_node(nv_per_node_),n_del(0),
                    deleted_nodes_head(Invalid),root(Invalid),nil(Invalid) {
                root = new_node();
                nil = new_node();
            }
            //~ ~NodeAllocatorCompact() { }
            /* main interface */
            Node& get_node(NodeHandle x) { return nodes[x]; }
            const Node& get_node(NodeHandle x) const { return nodes[x]; }
            
            
        private:
            bool try_get_node(NodeHandle& n) {
                if(deleted_nodes_head != Invalid) {
                    if(!n_del) throw std::runtime_error("NodeAllocatorCompact::alloc_node(): inconsistent deleted nodes!\n");
                    n_del--;
                    n = deleted_nodes_head;
                    nodes[n].set_parent(Invalid);
                    deleted_nodes_head = nodes[deleted_nodes_head].get_left();
                    if(deleted_nodes_head != Invalid) nodes[deleted_nodes_head].set_right(Invalid);
                    return true;
                }
                else return false;
            }
            
            void move_nv(IndexType x, IndexType y) {
                size_t xbase = ((size_t)x)*nv_per_node;
                size_t ybase = ((size_t)y)*nv_per_node;
                for(unsigned int i=0;i<nv_per_node;i++) nvarray[xbase + i] = nvarray[ybase + i];
            }
            
            void move_node(NodeHandle x, NodeHandle y) {
                nodes[x] = std::move(nodes[y]); /* no need to swap (i.e. preserve values in x) */
                move_nv(x,y); /* move rank function as well */
                /* note: destructor is not called for y (memory is not freed) */
                if(y == root || y == nil) throw std::runtime_error("NodeAllocatorCompact::move_node(): root or nil is moved!\n");
                /* update parent and children if needed */
                if(nodes[x].get_parent() != Invalid && nodes[x].get_parent() != nil) {
                    if(nodes[nodes[x].get_parent()].get_left() == y) nodes[nodes[x].get_parent()].set_left(x);
                    else {
                        if(nodes[nodes[x].get_parent()].get_right() == y) nodes[nodes[x].get_parent()].set_right(x);
                        else throw std::runtime_error("NodeAllocatorCompact::move_node(): inconsistent tree detected!\n");
                    }
                }
                else throw std::runtime_error("NodeAllocatorCompact::move_node(): node with no parent!\n");
                if(nodes[x].get_left() != Invalid && nodes[x].get_left() != nil) {
                    if(nodes[nodes[x].get_left()].get_parent() != y)
                        throw std::runtime_error("NodeAllocatorCompact::move_node(): inconsistent tree detected!\n");
                    nodes[nodes[x].get_left()].set_parent(x);
                }
                if(nodes[x].get_right() != Invalid && nodes[x].get_right() != nil) {
                    if(nodes[nodes[x].get_right()].get_parent() != y)
                        throw std::runtime_error("NodeAllocatorCompact::move_node(): inconsistent tree detected!\n");
                    nodes[nodes[x].get_right()].set_parent(x);
                }
            }
            
            void shrink_memory(IndexType new_capacity = 0) {
                nodes.shrink_to_fit(new_capacity);
                nvarray.shrink_to_fit(((size_t)new_capacity)*nv_per_node);
            }
            
        protected:
            NodeHandle new_node() {
                NodeHandle n = nodes.size();
                /* use previously deleted node, if available */
                if(try_get_node(n)) nodes[n] = Node();
                else {
                    /* create new node */
                    if(n == max_nodes) throw std::runtime_error("NodeAllocatorFlat::new_node(): reached maximum number of nodes!\n");
                    nodes.emplace_back();
                    nvarray.resize(((size_t)(n+1))*nv_per_node,NVType());
                }
                return n;
            }
            NodeHandle new_node(const KeyValue& kv) {
                NodeHandle n = nodes.size();
                if(try_get_node(n)) nodes[n] = Node(kv);
                else {
                    if(n == max_nodes) throw std::runtime_error("NodeAllocatorFlat::new_node(): reached maximum number of nodes!\n");
                    nodes.emplace_back(kv);
                    nvarray.resize(((size_t)(n+1))*nv_per_node,NVType());
                }
                return n;
            }
            NodeHandle new_node(KeyValue&& kv) {
                NodeHandle n = nodes.size();
                if(try_get_node(n)) nodes[n] = Node(std::forward<KeyValue>(kv));
                else {
                    if(n == max_nodes) throw std::runtime_error("NodeAllocatorFlat::new_node(): reached maximum number of nodes!\n");
                    nodes.emplace_back(std::forward<KeyValue>(kv));
                    nvarray.resize(((size_t)(n+1))*nv_per_node,NVType());
                }
                return n;
            }
            template<class... T> NodeHandle new_node(T&&... kv) {
                NodeHandle n = nodes.size();
                if(try_get_node(n)) nodes[n] = Node(std::forward<T>(kv)...);
                else {
                    if(n == max_nodes) throw std::runtime_error("NodeAllocatorFlat::new_node(): reached maximum number of nodes!\n");
                    nodes.emplace_back(std::forward<T>(kv)...);
                    nvarray.resize(((size_t)(n+1))*nv_per_node,NVType());
                }
                return n;
            }
        
            void free_node(NodeHandle n) { 
                /* store deleted nodes in a linked list */
                nodes[n].set_deleted();
                nodes[n].set_right(Invalid);
                nodes[n].set_left(deleted_nodes_head);
                if(deleted_nodes_head != Invalid) nodes[deleted_nodes_head].set_right(n);
                deleted_nodes_head = n;
                n_del++;
            }
            void clear_tree() {
                nodes.resize(2);
                nvarray.resize(2);
                //~ size = 2;
                root = 0;
                nil = 1;
                nodes[root] = Node();
                nodes[nil] = Node();
                shrink_memory(4);
            }
            
            
            unsigned int get_nv_per_node() const { return nv_per_node; }
            
            void get_node_sum(NodeHandle n, NVType* s) const {
                size_t base = ((size_t)n)*nv_per_node;
                for(unsigned int i=0;i<nv_per_node;i++) s[i] = nvarray[base+i];
            }
            void set_node_sum(NodeHandle n, const NVType* s) {
                size_t base = ((size_t)n)*nv_per_node;
                for(unsigned int i=0;i<nv_per_node;i++) nvarray[base+i] = s[i];
            }
        
        public:
            
            size_t capacity() const { return nodes.capacity(); }
            size_t deleted_nodes() const { return n_del; }
            
            void shrink_to_fit() {
                while(deleted_nodes_head != Invalid) {
                    /* remove nodes at the end */
                    NodeHandle size = nodes.size();
                    if(size == 0) throw std::runtime_error("NodeAllocatorCompact::shrink_size(): ran out of nodes!\n");
                    size--;
                    if(nodes[size].is_deleted()) {
                        /* if last node was deleted, update the list of deleted nodes */
                        NodeHandle left = nodes[size].get_left();
                        NodeHandle right = nodes[size].get_right();
                        if(left != Invalid) nodes[left].set_right(right);
                        if(right != Invalid) nodes[right].set_left(left);
                        if(deleted_nodes_head == size) deleted_nodes_head = left;
                    }
                    else {
                        /* otherwise move last node into the place of a deleted node */
                        NodeHandle n = deleted_nodes_head;
                        if(n == size)
                            throw std::runtime_error("NodeAllocatorCompact::shrink_size(): inconsistent deleted nodes!\n");
                        deleted_nodes_head = nodes[deleted_nodes_head].get_left();
                        nodes[deleted_nodes_head].set_right(Invalid);
                        move_node(n,size);
                    }
                    nodes.pop_back();
                    nvarray.resize(((size_t)size)*nv_per_node);
                    if(!n_del) throw std::runtime_error("NodeAllocatorCompact::shrink_size(): inconsistent deleted nodes!\n");
                    n_del--;
                }
                shrink_memory();
            }
            
            void reserve(size_t size) {
                nvarray.reserve(size);
                nodes.reserve(size);
            }
    };
}



#endif