btree_seq.h

Go to the documentation of this file.

//  Copyright (C) 2014 by Aleksandr Kupriianov
//  email: alexkupri host: gmail dot com

// Distributed under the Boost Software License, Version 1.0.
//    (See the file LICENSE_1_0.txt or copy at
//          http://www.boost.org/LICENSE_1_0.txt)

//  Purpose: fast sequence declaration
//  See documentation at http://alexkupri.github.io/array/

  
#ifndef __BTREE_SEQ_H
#define __BTREE_SEQ_H

#include <assert.h>
#include <iterator>

#if __cplusplus >= 201103L

#include <initializer_list>
#include <utility>

#endif

// This is private namespace.
namespace ___alexkupri_helpers
{
    struct my_false_type{};
    struct my_true_type{};
    template<typename _Tp> struct my_is_integer  {  typedef my_false_type __type;  };
    template<> struct my_is_integer<bool>  {  typedef my_true_type __type;  };
    template<> struct my_is_integer<char>  {  typedef my_true_type __type;  };
    template<> struct my_is_integer<signed char>  {  typedef my_true_type __type;  };
    template<> struct my_is_integer<unsigned char>  {  typedef my_true_type __type;  };
    template<> struct my_is_integer<short>  {  typedef my_true_type __type;  };
    template<> struct my_is_integer<unsigned short>  {  typedef my_true_type __type;  };
    template<> struct my_is_integer<int>  {  typedef my_true_type __type;  };
    template<> struct my_is_integer<unsigned int>  {  typedef my_true_type __type;  };
    template<> struct my_is_integer<long>  {  typedef my_true_type __type;  };
    template<> struct my_is_integer<unsigned long>  {  typedef my_true_type __type;  };
}


template <typename T,int L=30,int M=60,typename A=std::allocator<T> >
class btree_seq
{
public:
    typedef A allocator_type;
    typedef typename A::value_type value_type;
    typedef typename A::reference reference;
    typedef typename A::const_reference const_reference;
    typedef typename A::pointer pointer;
    typedef typename A::const_pointer const_pointer;
    typedef typename A::size_type size_type;
    typedef typename A::difference_type difference_type;
    typedef typename A::difference_type diff_type;
private:
    //data types
    //In the whole library Node* can be cast to either Branch* or Leaf*.
    //This is determined entirely via depth variable.
    struct Branch;
    struct Node
    {
        Branch *parent;
    };
    struct Branch:public Node
    {
        Node* children[L];
        size_type nums[L];
        size_type fillament;
    };
    struct Leaf:public Node
    {
        value_type elements[M];
        size_type fillament;
    };
    typedef typename allocator_type::template rebind<Branch>::other Branch_alloc_type;
    typedef typename allocator_type::template rebind<Leaf>::other Leaf_alloc_type;
    allocator_type T_alloc;
    Branch_alloc_type branch_alloc;
    Leaf_alloc_type leaf_alloc;
    //Data
    Node *root;
    size_type depth,count;
    //Element helper functions
    void move_elements_inc(pointer dst,pointer src,size_type num);
    void move_elements_dec(pointer dst,pointer limit,size_type num);
    template <class InputIterator>
        diff_type fill_elements(pointer dst,diff_type num,InputIterator &first,InputIterator last,
            std::random_access_iterator_tag);
    template <class InputIterator>
        diff_type fill_elements(pointer dst,diff_type num,InputIterator &first,InputIterator last,
            std::input_iterator_tag);
    template <class InputIterator>
        diff_type count_difference(InputIterator,InputIterator,diff_type limit,
        std::input_iterator_tag){return limit+1;}
    template <class InputIterator>
        diff_type count_difference(InputIterator first,InputIterator last,diff_type,
        std::random_access_iterator_tag){return last-first;}
    void burn_elements(pointer ptr,size_type num);
    //branch helpers
    void insert_children(Branch *b,size_type idx,size_type num);
    void delete_children(Branch *b,size_type idx,size_type num);
    size_type move_children(Branch *dst,size_type idst,Branch *src,size_type isrc,size_type num);
    size_type fill_leaves(Branch *b,size_type place,Leaf **l,size_type num);
    //leaf balancing helpers
    bool try_merge_leaves(Branch *b,size_type idx);
    void balance_leaves_lr(Branch *b,size_type idx);
    void balance_leaves_rl(Branch *b,size_type idx);
    void delete_leaf(Leaf *l);
    void underflow_leaf(Leaf *l);
    //branch balancing helpers
    bool try_merge_branches(Branch *b,size_type idx);
    void balance_branch_lr(Branch *b,size_type idx);
    void balance_branch_rl(Branch *b,size_type idx);
    void underflow_branch(Branch *node);
    //find and read functions
    size_type  find_leaf(Leaf *&l,size_type pos)const;
    size_type  find_leaf(Node *&l,size_type pos,difference_type increment,size_type depth_lim=0);
    static size_type  find_child(Branch *b,Node* c);
    //some initialization functions
    void init_tree();
    void increase_depth(Branch *new_branch);
    //splitting algorithms
    Branch *reserve_enough_branches_splitting(Node* existing);
    template <typename Alloc,typename Node_type>
        void prepare_for_splitting(Branch *&branch_bundle,
                Node_type *&result,Node_type *existing,Alloc &alloc);
    void split(Node* existing,Node* right_to_existing,size_type right_count,Branch *branch_bundle);
    void add_child(Branch* parent,Node* inserted,size_type elements,size_type pos,size_type rl,Branch *branch_bundle);
    //underflow and sew functions
    void deep_sew(size_type pos);
    void my_deep_sew(size_type pos);
    void advanced_sew_together(Leaf *last_leaf,size_type pos);
    //helper functions and a class for inserting
    size_type prepare_leaf_for_inserting
        (size_type pos,diff_type num,Leaf *&res,Leaf **sibling);
    void undo_preparing_to_insert
        (size_type pos,diff_type num,Leaf *l,Leaf *sibling,size_type found);

    template <class InputIterator>
        Leaf* start_inserting(size_type &pos,InputIterator &first,InputIterator last);
    void insert_leaves(Leaf **l,size_type num_leaves,diff_type num_elems,size_type pos);
    template <class InputIterator>
        Leaf* insert_whole_leaves(size_type startpos,size_type &pos,InputIterator first,InputIterator last,Leaf *last_leaf);
    class FillIterator
    {
        const_pointer ptr;
        size_type j;
    public:
    //ok with default fns: op=, ~, copy cn
        typedef std::random_access_iterator_tag iterator_category;
        typedef 
            typename std::iterator<std::random_access_iterator_tag, T>::value_type
            value_type;
        typedef
            typename std::iterator<std::random_access_iterator_tag, T>::difference_type
            difference_type;
        typedef 
            typename std::iterator<std::random_access_iterator_tag, T>::reference
            reference;
        typedef 
            typename std::iterator<std::random_access_iterator_tag, T>::pointer
            pointer;    
    
        // 
        FillIterator(const_pointer ptrptr,size_type jj):ptr(ptrptr),j(jj){};
        const_reference operator*(){return *ptr;}
        FillIterator &operator++(){j++;return *this;}
        bool operator==(const FillIterator &that)const
            { return j==that.j; }
        bool operator!=(const FillIterator &that)const
            { return j!=that.j; }
        difference_type operator-(const FillIterator &that)const
            {return static_cast<diff_type>(j)-static_cast<diff_type>(that.j);}
    };
    //helper function and classes for delete and iterative access
    template<typename Action>
        bool recursive_action(Action &act,size_type start,size_type diff,size_type dep,Node *node);
    class erase_helper
    {
        Leaf *last_leaf;
        size_type leaves;
        btree_seq &aka;
    public:
        erase_helper(btree_seq &akaaka):last_leaf(0),leaves(0),aka(akaaka){}
        void decrement_value(size_type &a,size_type b){a-=b;}
        bool shift_array(){return true;}
        bool process_leaf(Leaf *l,size_type start,size_type end);
        Leaf *get_last_leaf(){return last_leaf;}
        size_type num_leaves(){return leaves;}
    };
    template<typename V>
    class visitor_helper
    {
        V &v;
        size_type iters;
    public:
        visitor_helper(V &vv):v(vv),iters(0){};
        void decrement_value(size_type &,size_type){}
        bool shift_array(){return false;}
        bool process_leaf(Leaf *l,size_type st,size_type fin);
        size_type get_iters(){return iters;}
    };
    //attach and detach helpers
    void detach_some(btree_seq<T,L,M,A> &that,Branch *b,size_type dep,bool last);
    void insert_tree(btree_seq<T,L,M,A> &that,bool last);
    //assign helpers
    template <class Integer>
        void impl_insert(size_type pos,Integer n,Integer val,___alexkupri_helpers::my_true_type)
    {
        fill(pos,static_cast<size_type>(n),val);
    }
    template <class InputIterator>
        void impl_insert(size_type pos,InputIterator first,InputIterator last,___alexkupri_helpers::my_false_type)
    {
        insert(pos,first,last);
    }
    //others
    void check_node(Node* c,size_type sum,bool nothead,size_type depth,Branch *parent);
    template <class output_stream>
        void output_node(output_stream &o,Node* c,size_type tabs,size_type depth);
    static void my_assert(bool,const char*);
    void assert_range(size_type n);
public:

    template<typename TT>
    class iterator_base
    { 
    public:
    typedef std::random_access_iterator_tag iterator_category;
    typedef 
        typename std::iterator<std::random_access_iterator_tag, TT>::value_type
        value_type;
    typedef
        typename std::iterator<std::random_access_iterator_tag, TT>::difference_type
        difference_type;
    typedef 
        typename std::iterator<std::random_access_iterator_tag, TT>::reference
        reference;
    typedef 
        typename std::iterator<std::random_access_iterator_tag, TT>::pointer
        pointer;    
    private:
        const btree_seq *tree;
        size_type abs_idx;
        mutable pointer elems;
        mutable size_type avail_ptr;
        mutable size_type rel_idx;
        mutable Branch *br;
        mutable size_type idx_in_br;
        pointer rebase()const;
        pointer access()const
            {return (rel_idx<avail_ptr)?(elems+rel_idx):(rebase());}
    public:
        iterator_base():
            tree(0),abs_idx(),elems(),avail_ptr(0),rel_idx(),br(),idx_in_br(){};
        iterator_base(const btree_seq *t,size_type pos):
            tree(t),abs_idx(pos),elems(),avail_ptr(0),rel_idx(),br(0),idx_in_br(){};
        iterator_base(const iterator_base &that):
            tree(that.tree),
            abs_idx(that.abs_idx),
            elems(that.elems),
            avail_ptr(that.avail_ptr),
            rel_idx(that.rel_idx),
            br(that.br),
            idx_in_br(that.idx_in_br){};
        template<typename T2>
        iterator_base(const iterator_base<T2> &that):
            tree(that.get_container()),
            abs_idx(that.get_position()),
            elems(that.__get_null_pointer()),
            avail_ptr(0),
            rel_idx(),
            br(),
            idx_in_br(){}
        iterator_base& operator=(const iterator_base/*<T2>*/ &that)
            {
                elems=that.elems;
                tree=that.tree;
                abs_idx=that.abs_idx;
                rel_idx=that.rel_idx;
                avail_ptr=that.avail_ptr;
                idx_in_br=that.idx_in_br;
                br=that.br;
                return *this;
            }
        template<typename T2>
        iterator_base& operator=(const iterator_base<T2> &that)
            {
                tree=that.get_container();
                abs_idx=that.get_position();
                elems=that.__get_null_pointer();
                avail_ptr=0;
                return *this;
            }
        reference operator*()const{return *access();}
        pointer   operator->()const{return access();}
        reference operator[](difference_type n)const
            {iterator_base tmp(this);tmp+=n;return *tmp;};
        //comparison operators, < > = != <= >=
        template<typename T2>
        bool operator==(const iterator_base<T2>& that)const
            {return get_position()==that.get_position();}
        template<typename T2>
        bool operator!=(const iterator_base<T2>& that)const
            {return get_position()!=that.get_position();}
        template<typename T2>
        bool operator>(const iterator_base<T2>& that)const
            {return get_position()>that.get_position();}
        template<typename T2>
        bool operator<(const iterator_base<T2>& that)const
            {return get_position()<that.get_position();}
        template<typename T2>
        bool operator>=(const iterator_base<T2>& that)const
            {return get_position()>=that.get_position();}
        template<typename T2>
        bool operator<=(const iterator_base<T2>& that)const
            {return get_position()<=that.get_position();}
        template<typename T2>
        difference_type operator-(const iterator_base<T2>& that)const
            {return static_cast<diff_type>(get_position())-
                    static_cast<diff_type>(that.get_position());}
        iterator_base& operator++(){++abs_idx;++rel_idx;return *this;}
        iterator_base& operator--(){--abs_idx;--rel_idx;return *this;}
        iterator_base operator++(int){iterator_base tmp(*this);++(*this);return tmp;}
        iterator_base operator--(int){iterator_base tmp(*this);--(*this);return tmp;}
        iterator_base& operator+=(difference_type n){abs_idx=abs_idx+n;rel_idx=rel_idx+n;return *this;}
        iterator_base& operator-=(difference_type n){abs_idx-=n;rel_idx-=n;return *this;}
        iterator_base operator+(difference_type n)const
            {iterator_base tmp(*this);tmp+=n;return tmp;}
        iterator_base operator-(difference_type n)const
            {iterator_base tmp(*this);tmp-=n;return tmp;}
        size_type get_position()const{return abs_idx;}
        const btree_seq* get_container()const{return tree;}
        pointer __get_null_pointer()const{return 0;}
    };
    typedef iterator_base<const T> const_iterator;
    typedef iterator_base<T> iterator;
    typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
    typedef std::reverse_iterator<iterator> reverse_iterator; 

    explicit btree_seq(const allocator_type &alloc=allocator_type())
        :T_alloc(alloc),branch_alloc(alloc),leaf_alloc(alloc),root(),count(0)
    {
    };

    btree_seq(const btree_seq<T,L,M,A> &that)
        :T_alloc(that.T_alloc),branch_alloc(that.T_alloc),leaf_alloc(that.T_alloc),
         root(),count(0)
    {
        const_iterator first=that.begin(),last=that.end();
        insert(0,first,last);
    }

    explicit btree_seq(size_type n,const value_type &val,
            const allocator_type &alloc=allocator_type())
        :T_alloc(alloc),branch_alloc(alloc),leaf_alloc(alloc),root(),count(0)
    {
        fill(0,n,val);
    }

    template <typename Iterator>
    btree_seq(Iterator first,Iterator last,
        const allocator_type &alloc=allocator_type())
        :T_alloc(alloc),branch_alloc(alloc),leaf_alloc(alloc),root(),count(0)
    {
        typename ___alexkupri_helpers::my_is_integer<Iterator>::__type is_int_type;
        impl_insert(0,first,last,is_int_type);
    }
    #if __cplusplus >= 201103L


    btree_seq(btree_seq<T,L,M,A> &&that, const allocator_type &alloc=allocator_type()):T_alloc(alloc)
    {
        root=that.root;
        count=that.count;
        depth=that.depth;
        that.count=0;
        that.depth=0;
    }


    btree_seq(std::initializer_list<value_type> il,
            const allocator_type &alloc=allocator_type())
        :btree_seq(il.begin(),il.end(),alloc){}

    #endif


    ~btree_seq(){erase(0,count);}


    const_iterator begin()const{return const_iterator(this,0);}

    const_iterator end()const{return const_iterator(this,count);}

    const_iterator cbegin()const{return const_iterator(this,0);}

    const_iterator cend()const{return const_iterator(this,count);}

    iterator begin(){return iterator(this,0);}

    iterator end(){return iterator(this,count);}

    const_reverse_iterator rbegin()const{return const_reverse_iterator(end());}

    const_reverse_iterator rend()const{return const_reverse_iterator(begin());}

    const_reverse_iterator crbegin()const{return const_reverse_iterator(cend());}

    const_reverse_iterator crend()const{return const_reverse_iterator(cbegin());}

    reverse_iterator rbegin(){return reverse_iterator(end());}

    reverse_iterator rend(){return reverse_iterator(begin());}

    iterator iterator_at(size_type pos){return iterator(this,pos);}

    const_iterator citerator_at(size_type pos)const{return const_iterator(this,pos);}



    reference operator [](size_type pos)
    {
        Leaf *l=(Leaf*)root;
        size_type found=depth?find_leaf(l,pos):pos;
        T *ptr=l->elements;
        return *(ptr+found);
    }

    const_reference operator [](size_type pos)const
    {
        Leaf *l=(Leaf*)root;
        size_type found=depth?find_leaf(l,pos):pos;
        const T *ptr=l->elements;
        return *(ptr+found);
    }
    size_type size()const{return count;}

    reference at(size_type pos){
        assert_range(pos);
        return (*this)[pos];
    }

    const_reference at(size_type pos)const{
        assert_range(pos);
        return (*this)[pos];
    }

    reference front(){return (*this)[0];}

    const_reference front()const{return (*this)[0];}

    reference back(){return (*this)[size()-1];}

    const_reference back()const{return (*this)[size()-1];}
    bool empty()const{return count==0;}

    template<typename V>
        size_type visit(size_type first,size_type last,V& v);



    void insert(size_type pos,const value_type& val)
    {
       Leaf *l;
       size_type found=prepare_leaf_for_inserting(pos,1,l,0);
       try{
           T_alloc.construct(l->elements+found,val);
       }catch(...){
           undo_preparing_to_insert(pos,1,l,0,found);
           throw;
       }
    }

    template <class InputIterator>
        void insert(size_type pos,InputIterator first,InputIterator last);

    iterator insert(const_iterator pos,const value_type &val)
    {
        size_type position=pos.get_position();
        insert(position,val);
        return iterator_at(position);
    }

    iterator insert(const_iterator pos,size_type n,const value_type &val)
    {
        size_type position=pos.get_position();
        fill(position,n,val);
        return iterator_at(position);
    }

    template<class InputIterator>
    iterator insert(const_iterator pos,InputIterator first,InputIterator last)
    {
        typename ___alexkupri_helpers::my_is_integer<InputIterator>::__type is_int_type;
        size_type position=pos.get_position();
        impl_insert(position,first,last,is_int_type);
        return iterator_at(position);
    }
    #if __cplusplus >= 201103L

    void insert(size_type pos,value_type&& val)
    {
        emplace(pos,std::move(val));
    }


    iterator insert(const_iterator pos,value_type &&val)
    {
        size_type position=pos.get_position();
        emplace(position,std::move(val));
        return iterator_at(position);
    }


    void insert(size_type pos,std::initializer_list<value_type> il)
    {
        insert(pos,il.begin(),il.end());
    }


    iterator insert(const_iterator pos,std::initializer_list<value_type> il)
    {
        size_type position=pos.get_position();
        insert(position,il.begin(),il.end());
        return iterator_at(position);
    }
    #endif

    void fill(size_type pos,size_type repetition,const value_type& val)
    {
        FillIterator first(&val,0),last(&val,repetition);
        insert(pos,first,last);
    }

    void resize(size_type n,const value_type& val = value_type());

    void erase(size_type first,size_type last);

    iterator erase(const_iterator pos)
    {
        size_type position=pos.get_position();
        erase(position,position+1);
        return iterator_at(position);
    }

    iterator erase(const_iterator first,const_iterator last)
    {
        size_type first_position=first.get_position(),last_position=last.get_position();
        erase(first_position,last_position);
        return iterator_at(first_position);
    }

    void push_back(const value_type &val)
        {   insert(count,val);  }

    void push_front(const value_type &val)
        {   insert(0,val); }

    void pop_back()
        {   erase(count-1,count); }

    void pop_front()
        {   erase(0,1); }
    #if __cplusplus >= 201103L
    void push_back(value_type &&val)
    {
        emplace(count,std::move(val));
    }

    void push_front(value_type &&val)
    {
        emplace(0,std::move(val));
    }


    template <class ...Args>
    void emplace(size_type pos,Args&&... args)
    {
        Leaf *l;
        size_type found=prepare_leaf_for_inserting(pos,1,l,0);
        try{
            T_alloc.construct(l->elements+found,std::forward<Args>(args)...);
        }catch(...){
            undo_preparing_to_insert(pos,1,l,0,found);
            throw;
        }
    }


    template <class ...Args>
    iterator emplace(const_iterator pos,Args&&... args)
    {
        size_type position=pos.get_position();
        emplace(position,std::forward<Args>(args)...);
        return iterator_at(position);
    }

    template <class ...Args>
    void emplace_front(Args&&... args)
    {
        emplace(0,std::forward<Args>(args)...);
    }

    template <class... Args>
    void emplace_back(Args&&... args)
    {
        emplace(count,std::forward<Args>(args)...);
    }

    #endif



    btree_seq &operator=(const btree_seq<T,L,M,A> &that)
    {
        const_iterator first=that.begin(),last=that.end();
        clear();
        insert(0,first,last);
        return *this;
    }

    void swap(btree_seq<T,L,M,A> &that);

    void clear(){erase(0,count);}

    void assign(size_type n,const value_type &val);

    template <class InputIterator>
        void assign(InputIterator first,InputIterator last)
    {
        typename ___alexkupri_helpers::my_is_integer<InputIterator>::__type is_int_type;
        clear();
        impl_insert(0,first,last,is_int_type);
    }

    void concatenate_right(btree_seq<T,L,M,A> &that);

    void concatenate_left(btree_seq<T,L,M,A> &that);

    void split_right(btree_seq<T,L,M,A> &that,size_type pos);

    void split_left(btree_seq<T,L,M,A> &that,size_type pos);

    #if __cplusplus >= 201103L

    btree_seq &operator=(btree_seq<T,L,M,A> &&that)
    {
        clear();
        swap(that);
        return *this;
    }


    btree_seq &operator=(std::initializer_list<value_type> il)
    {
        assign(il);
        return *this;
    }


    void assign(std::initializer_list<value_type> il)
    {
        clear();
        insert(0,il.begin(),il.end());
    }

    #endif




    void __check_consistency();
    template <class output_stream>
        void __output(output_stream &o,const char *comm="");
    size_type __children_in_branch(){return L;}
    size_type __elements_in_leaf(){return M;}
    size_type __branch_size(){return sizeof(Branch);}
    size_type __leaf_size(){return sizeof(Leaf);}
    void reserve(size_type n){/*NOTHING*/}
    void shrink_to_fit(){/*NOTHING*/}
    allocator_type get_allocator()const{return T_alloc;}
};

template <typename T,int L,int M,typename A>
void swap(btree_seq<T,L,M,A> &first,btree_seq<T,L,M,A> &second)
{
    first.swap(second);
}

template <typename T,int L,int M,typename A>
bool   operator<(const btree_seq<T,L,M,A> &x,const btree_seq<T,L,M,A> &y)
    { return std::lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); }

template <typename T,int L,int M,typename A>
bool   operator>(const btree_seq<T,L,M,A> &x,const btree_seq<T,L,M,A> &y)
    { return (y<x); }

template <typename T,int L,int M,typename A>
bool   operator<=(const btree_seq<T,L,M,A> &x,const btree_seq<T,L,M,A> &y)
    { return !(y<x); }

template <typename T,int L,int M,typename A>
bool   operator>=(const btree_seq<T,L,M,A> &x,const btree_seq<T,L,M,A> &y)
    { return !(x<y); }

template <typename T,int L,int M,typename A>
bool  operator==(const btree_seq<T,L,M,A> &x,const btree_seq<T,L,M,A> &y)
    { return (x.size() == y.size()
          && std::equal(x.begin(), x.end(), y.begin())); }

template <typename T,int L,int M,typename A>
bool  operator!=(const btree_seq<T,L,M,A> &x,const btree_seq<T,L,M,A> &y)
    { return !(x==y); }


#include "btree_seq2.h"

#endif /*__BTREE_SEQ_H*/