fork download

copy

#pragma once
#include "mpd/value_iterator/value_iterator.h"
#include <memory>
#include <cassert>
#include <stdexcept>
#include <vector>
//#include <functional>
 
#ifdef DEBUG_THE_TRACK_CLASS
#include <iostream>
#include <iomanip>
extern unsigned rotate_count;
#endif
 
#ifdef _MSC_VER 
    #if _MSC_VER > 1500
        #define HAS_RVALUES
    #endif
    #if _MSC_VER > 1600
		#define HAS_VARIADIC
	#endif
    #define noexcept(X) throw()
 
#elif __GNUC__
    #define GCC_VERSION (__GNUC__ * 10000  + __GNUC_MINOR__ * 100  + __GNUC_PATCHLEVEL__)
    #if GCC_VERSION>30000
		#define HAS_RVALUES
		#define HAS_VARIADIC
	#else
		#define noexcept(X) throw()
	#endif
	#if GCC_VERSION<40600
        #define nullptr NULL
        #define nullptr_t void*
    #endif
#else
    #if __cplusplus > 199711L
        #define HAS_RVALUES
        #define HAS_VARIADIC
    #endif
    #define noexcept(X) throw()
#endif
 
 
/*This container matches the same interface with the following exceptions
The elements are non-contiguous.
There is no capacity(), reserve(), shrink_to_fit(), or data() member functions.
Iterators and references are never invalidated, unless the element has been erased/cleared
Virtually all operations are logarithmic. (including iterator advancement)
*/
namespace mpd {
    enum side_type {left=0, right=1};
    static side_type other(side_type side) noexcept(true) {return side!=left?left:right;}
    struct use_def_ctor {};
    use_def_ctor& def_ctor() noexcept(true) {static use_def_ctor udc; return udc;}
 
    template<class type, class allocator>
    class track_base;
    template<class allocator>
    class track_base<void, allocator>{
    protected:
        typedef typename allocator::difference_type difference_type;
        typedef typename allocator::size_type size_type;
        struct node {
            typedef typename allocator::template rebind<node>::other node_allocator_type;
            typedef typename node_allocator_type::reference reference;
            //typedef typename node_allocator_type::const_reference const_reference;
            typedef typename node_allocator_type::pointer pointer;
            typedef typename node_allocator_type::const_pointer const_pointer;
 
            size_type nodes_on_left;
            pointer parent;
            pointer child[2];
            node() noexcept(true) :nodes_on_left(), parent(), child() {}
			~node() {if (parent) pop();}
			void swap(node& rhs) {
                using std::swap;
				swap(parent, rhs.parent);
                swap(nodes_on_left, rhs.nodes_on_left);
 
                swap(child[left], rhs.child[left]);
                if (child[left])
                    child[left]->parent = this;
                if (rhs.child[left])
                    rhs.child[left]->parent = &rhs;
 
                swap(child[right], rhs.child[right]);
                if (child[right])
                    child[right]->parent = this;
                if (rhs.child[right])
                    rhs.child[right]->parent = &rhs;
			}
            pointer& parent_ptr_to_this() noexcept(true) {return parent->child[get_side()];}
            const_pointer down_to_far(side_type dir) const noexcept(true) {
                const_pointer ptr=this; 
                while(ptr->child[dir]) 
                    ptr = ptr->child[dir]; 
                return ptr;
            }
            pointer down_to_far(side_type dir) noexcept(true) 
            {return const_cast<pointer>(((const_pointer)this)->down_to_far(dir));}
            side_type get_side() const noexcept(true) {return parent->child[right]==this ? right : left;} 
            size_type num_nodes_on(side_type dir, size_type total_nodes) const noexcept(true) 
            {assert(total_nodes); if (dir == right) return total_nodes-nodes_on_left-1; return nodes_on_left;}
            size_type child_offset(side_type dir, size_type my_offset) noexcept(true) 
            {if (dir == right) return my_offset+nodes_on_left+1; return my_offset;}
            const_pointer find_parent_on(side_type dir) const noexcept(true) {
                const_pointer ptr=this;
                while(ptr->get_side() == dir)
                    ptr = ptr->parent;
                return ptr->parent;
            }
            size_type get_size() const noexcept(true) {
                size_type r = nodes_on_left;
                const_pointer ptr=child[right];
                while(ptr) {
                    r += ptr->nodes_on_left + 1;
                    ptr = ptr->child[right];
                }
                return r;
            }
            const_pointer find_root() const noexcept(true) {
                const_pointer ptr=this;
                while(ptr->parent)
                    ptr = ptr->parent;
                assert(ptr->child[right]==nullptr);
                return ptr;
            }
            pointer find_root() noexcept(true)
            {return const_cast<pointer>(((const_pointer)this)->find_root());}
            const_pointer find_one_to(side_type dir) const noexcept(true) {
                const_pointer ptr=this;
                if(ptr->child[dir]) return ptr->child[dir]->down_to_far(other(dir));
                return ptr->find_parent_on(dir);
            }
            pointer find_one_to(side_type dir) noexcept(true)
            {return const_cast<pointer>(((const_pointer)this)->find_one_to(dir));}
            const_pointer down_to_offset(size_type index) const noexcept(true) { //cannot go up
                const_pointer ptr=this;
                while(ptr->nodes_on_left != index) {
                    if (ptr->nodes_on_left > index) {
                        ptr = ptr->child[left];
                    } else{
                        index = index - ptr->nodes_on_left - 1;
                        ptr = ptr->child[right];
                    }
                }
                return ptr;
            }
            pointer down_to_offset(size_type index) noexcept(true) 
            {return const_cast<pointer>(((const_pointer)this)->down_to_offset(index));}
	        const_pointer find_many_to(side_type dir, size_type count) const noexcept(true) { //can go up
                const_pointer ptr=this;
                if (dir == right) {
                    for(;;) {
                        if (count == 0) return ptr;
                        if (ptr->parent == nullptr) return ptr->down_to_offset(count);
                        if (ptr->get_side() == left) {
                            unsigned nodes_on_right = ptr->parent->nodes_on_left - ptr->nodes_on_left - 1;
                            if (count <= nodes_on_right) 
                                return ptr->child[right]->down_to_offset(count-1);
                            count -= nodes_on_right + 1;
                            ptr = ptr->parent;
                        } else {
                            count += ptr->parent->nodes_on_left + 1;
                            ptr = ptr->parent;
                        }
                    }
                } else {
                    for(;;) {
                        if (count == 0) return ptr;
                        if (ptr->nodes_on_left >= count)
                            return ptr->child[left]->down_to_offset(ptr->nodes_on_left - count);
                        count -= ptr->nodes_on_left + 1;
                        ptr = ptr->parent;
                    }
                }
            }
            pointer find_many_to(side_type dir, size_type count) noexcept(true) 
            {return const_cast<pointer>(((const_pointer)this)->find_many_to(dir, count));}
            size_type get_index() const noexcept(true) {
                const_pointer ptr=this;
                size_type o = ptr->nodes_on_left;
                while(ptr->parent) {
                    if (ptr->get_side()==left)
                        ptr = ptr->parent;
                    else {
                        ptr = ptr->parent;
                        o += ptr->nodes_on_left + 1;
                    }
                }
                return o;
            }
            void add_size(side_type dir, size_type count) noexcept(true){
                pointer ptr = this;
                if (dir == left)
                    ptr->nodes_on_left += count;
                while(ptr->parent != nullptr) {
                    dir = ptr->get_side();
                    ptr = ptr->parent;
                    if (dir == left)
                        ptr->nodes_on_left += count;
                }
            }
            void sub_size(side_type dir, size_type count) noexcept(true){
                pointer ptr = this;
                if (dir == left)
                    ptr->nodes_on_left -= count;
                while(ptr->parent != nullptr) {
                    dir = ptr->get_side();
                    ptr = ptr->parent;
                    if (dir == left)
                        ptr->nodes_on_left -= count;
                }
            }
	        bool is_just_to(side_type dir, const_pointer oldroot) const noexcept(true) {
		        oldroot = oldroot->child[dir];
		        while(oldroot) {
			        if (oldroot == this) 
				        return true;
			        oldroot = oldroot->child[!dir];
		        }
		        return false;
	        }
#ifdef DEBUG_THE_TRACK_CLASS
            void print_tree() const noexcept(true) {
                std::vector<const node*> out(1, find_root()->child[left]);
                if (out[0] == NULL) return;
                std::vector<const node*> in;
                std::vector<const node*> summary;
                const size_type width = 64;
                bool recurse;
                do {
                    recurse = false;
                    in = out;
                    out.clear();
                    out.reserve(in.size()*2);
                    size_type width_per = width/in.size();
                    for(size_type i=0; i<in.size(); ++i) {
                        if (in[i]) {
                            if (width_per==2) {
                                std::cout << std::hex << std::setw(width_per) << ((unsigned(in[i])&0xFF0)>>4);
                            } else {
                                if (i==0) std::cout << ' ';
                                std::cout << std::hex << std::setw(width_per/2) << ((unsigned(in[i])&0xFF0)>>4);
                                std::cout << std::setw(width_per-width_per/2);
                            }
                            if (in.size()>1) std::cout << ' ';
                            else std::cout << std::dec << in[i]->parent->nodes_on_left;
                            summary.push_back(in[i]);
                            out.push_back(in[i]->child[left]);
                            out.push_back(in[i]->child[right]);
                            if (in[i]->child[left] || in[i]->child[right]) 
                                recurse = true;
                        } else {
                            if (width_per==2)
                                std::cout << ". ";
                            else {
                                if (i==0) std::cout << ' ';
                                std::cout << std::setw(width_per/2) << ". " << std::setw(width_per-width_per/2) << ' ';
                            }
                            out.push_back(nullptr);
                            out.push_back(nullptr);
                        }
                    }
                    std::cout << '\n';
                }while(recurse && out.size()<64);
                for(size_type i=0; i<summary.size(); ++i) {
                    std::cout << std::hex << ((unsigned(summary[i])&0xFF0)>>4) << ' ';
                    std::cout << summary[i] << ' ';
                    std::cout << std::dec << summary[i]->nodes_on_left << '\n';
                }
            }
            bool sub_tree_valid(size_type total_size) const noexcept(true) {
                if (child[left]) {
                    assert(child[left]->parent == this);
                    child[left]->sub_tree_valid(nodes_on_left);
                } else
                    assert(nodes_on_left == 0);
                if (child[right]) {
                    assert(child[right]->parent == this);
                    child[right]->sub_tree_valid(total_size-1-nodes_on_left);
                } else
                    assert(nodes_on_left + 1 == total_size);
                return true;
            }
            bool whole_tree_valid() const noexcept(true) {
                const node* p = find_root();
                print_tree();
                if (p->child[left]) 
                    return p->child[left]->sub_tree_valid(p->nodes_on_left);
                assert(p->nodes_on_left == 0);
                return true;
            }
            void get_heights(std::vector<size_type>& heights, size_type cur=1) const noexcept(true) {
                if (child[left])
                    child[left]->get_heights(heights, cur+1);
                if (child[right])
                    child[right]->get_heights(heights, cur+1);
                if (child[left]==nullptr || child[right]==nullptr) {
                    if (heights.size()<=cur)
                        heights.resize(cur+1);
                    heights[cur]++;
                }
            }
            bool assert_heights() const noexcept(true) {
                const node* p = find_root();
                if (p->nodes_on_left==0) return true;
                double log2 = std::log(double(p->nodes_on_left));
 
                std::vector<size_type> heights;
                heights.reserve(size_type(log2*2.0+4.0));
                p->child[left]->get_heights(heights);
 
                size_type expected_max = size_type(log2*2.0+2.0);
                size_type found_max = heights.size()-1;
                if (found_max > expected_max) {
                    print_tree();
                    assert(found_max<=expected_max);
                }
                size_type expected_min = size_type(log2*.5-1.0);
                size_type found_min = 1;
                while(heights[found_min-1]==0)
                    ++found_min;
                if (found_min < expected_min) {
                    print_tree();
                    assert(found_min>=expected_max);
                }
                return true;
            }
#else
			void print_tree() const noexcept(true) {}
			bool whole_tree_valid() const noexcept(true) {return true;}
            bool assert_heights() const noexcept(true) {return true;}
#endif
	        pointer rotate(side_type dir, pointer newroot) noexcept(true) {
                //std::cout << "rotating " << newroot << " around " << this << '\n';
                //print_tree();
		        assert(newroot->is_just_to(other(dir), this));
                assert(whole_tree_valid());
                pointer A = child[!dir]; //might be D
                pointer B = newroot->parent; //might be F
                pointer C = newroot->child[!dir]; //might be NULL
                pointer D = newroot;
                pointer E = newroot->child[dir]; //might be NULL
                pointer F = this;
                pointer Z = parent;
                size_type sizeofE=0;
                if (dir == right)
                    sizeofE = F->get_index() - D->get_index() - 1;
                else
                    sizeofE = D->nodes_on_left;
                side_type D_side = D->get_side();
                side_type F_side = get_side();
                /*
                ROTATES D TO BE NEW ROOT
                          Z                 Z
                          ?                 ?
	                      F*                D*
	                    /   \             /    \
	                  A*      O        A*         F*
	                 / \              / \        / \
	                O   B*      ---> O   B*     E   O  
	                   / \              / \    / \
	                  O	  D*           O   C  O   O
		                 / \              / \
	                   C     E           O   O
                      / \   / \
	                 O   O O   O                          
                */
                B->child[D_side] = C;
                if (C) C->parent = B;
                A = F->child[!dir]; //might be changed
                D->child[!dir] = A;
                if (A) A->parent = D;
                F->child[!dir] = E; 
                if (E) E->parent = F;
                D->child[dir] = F; 
                F->parent = D;
                Z->child[F_side] = D; 
                D->parent = Z;
 
                if (dir==right) {
                    D->nodes_on_left = F->nodes_on_left - sizeofE- 1;
                    F->nodes_on_left = sizeofE;
                } else {
                    D->nodes_on_left += F->nodes_on_left + 1;
                    while(B!=F && B!=D) {
                        B->nodes_on_left -= sizeofE + 1;
                        B = B->parent;
                    }
                }
                assert(whole_tree_valid());
#ifdef DEBUG_THE_TRACK_CLASS
                ++rotate_count;
#endif
                return newroot;
	        }
	        pointer rotate_at_least(side_type dir, size_type& count, size_type total_size) noexcept(true) {
				assert(total_size);
                pointer ptr = child[!dir];
                total_size = num_nodes_on(other(dir), total_size);
                size_type check_next = ptr->num_nodes_on(dir, total_size);
                while(check_next>count && ptr->child[dir]) {
                    total_size = check_next;
                    ptr = ptr->child[dir];
                    check_next = ptr->num_nodes_on(dir, total_size);
                }
                count = total_size;
                return rotate(dir, ptr);
            }
            void balance(size_type seek_offset, size_type total_size, bool down_left, bool down_right) noexcept(true) {
				assert(total_size);
                //seek_offset may be out of bounds, that's fine
                bool did_rotate_thistime;
                bool did_rotate_any = false;
                pointer ptr = this;
                size_type nodes_on_right=0;
                do {
                    did_rotate_thistime = false;
                    nodes_on_right = ptr->num_nodes_on(right, total_size);
                    //more than twice as many on the left as right
                    if (ptr->nodes_on_left > (nodes_on_right+1)*2) {
                        size_type delta = ptr->nodes_on_left - (nodes_on_right+1)*2;
                        ptr = ptr->rotate_at_least(right, delta, total_size);
                        did_rotate_thistime = true;
                        did_rotate_any = true;
                    //more than twice as many on the right as left
                    } else if ((ptr->nodes_on_left+1)*2 < nodes_on_right) {
                        size_type delta = nodes_on_right - (ptr->nodes_on_left+1)*2;
                        ptr = ptr->rotate_at_least(left, delta, total_size);
                        did_rotate_thistime = true;
                        did_rotate_any = true;
                    }
                } while(did_rotate_thistime);
 
                bool seek_left = false;
                bool seek_right = false;
                if (seek_offset < ptr->nodes_on_left)
                    seek_left = true;
                if (seek_offset > ptr->nodes_on_left+1 && seek_offset < total_size)
                    seek_right = true;
 
                if (ptr->child[left] && (did_rotate_any || down_left ||seek_left))
                    ptr->child[left]->balance(seek_offset, ptr->nodes_on_left, down_left, did_rotate_any);
                if (ptr->child[right] && (did_rotate_any || down_right || seek_right)) {
                    seek_offset -= ptr->nodes_on_left+1;
                    ptr->child[right]->balance(seek_offset, nodes_on_right, did_rotate_any, down_right);
                }
            }
            void pop() noexcept(true) {
                side_type old_side = get_side();
                if (child[left]==nullptr && child[right]==nullptr) {
                    parent->child[old_side] = nullptr;
                    parent = nullptr;
                } else if (this->child[left]==nullptr || child[right]==nullptr) {
                    bool child_on_right = (child[right] != nullptr);
                    parent->child[old_side] = child[child_on_right];
                    child[child_on_right]->parent = parent;
                    parent = nullptr;
                    child[child_on_right] = nullptr;
                    nodes_on_left = 0;
                } else {
                    pointer replacement = child[left]->down_to_far(right);
                    side_type replacement_side = replacement->get_side();
                    //remove references to replacement
                    replacement->parent->child[replacement_side] = replacement->child[left];
                    if (replacement->child[left])
                        replacement->child[left]->parent = replacement->parent;
                    //nothing points at replacement, set up replacement
                    replacement->parent = parent;
                    replacement->child[left] = child[left];
                    replacement->child[right] = child[right];
                    //point things at replacement
                    parent->child[old_side] = replacement;
                    if (child[left])
                        child[left]->parent = replacement;
                    if (child[right])
                        child[right]->parent = replacement;
                    //no longer point at tree
                    parent = nullptr;
                    child[left] = nullptr;
                    child[right] = nullptr;
                    nodes_on_left = 0;
                }
            }
			template<class node_smart_ptr>
            node* add_child(side_type dir, node_smart_ptr* first, size_type total_its) noexcept(true) {
				assert(total_its);
                assert(child[dir] == nullptr);
                size_type half = total_its/2;
                node_smart_ptr* mid = first+half;
                child[dir] = (*mid).release();
                child[dir]->parent = this;
                child[dir]->nodes_on_left = half;
                if (half < total_its-1)
                    child[dir]->add_child(right, std::next(mid), total_its-half-1);
                if (half > 0)
                    return child[dir]->add_child(left, first, half);
                return child[dir];
            }
			//optimize non-recursive case
            node* pop(node* endpoplist, size_type min_index, size_type max_index, size_type total_size) {
				assert(total_size);
			    assert(min_index<=max_index);
                if (min_index==max_index) return endpoplist;
				//store info before making any changes
				bool remove_self = (min_index <= nodes_on_left && max_index > nodes_on_left);
				size_type self_index = nodes_on_left;
				//pop nodes on right
				if (max_index>nodes_on_left+1 && child[right]) {
					size_type skip = nodes_on_left+1;
					size_type min = min_index<skip ? 0 : min_index-skip;
					size_type nodes_on_right = num_nodes_on(right, total_size);
					endpoplist = child[right]->pop(endpoplist, min, max_index-skip, nodes_on_right);
				}
				node* left_child = child[left];
				//if removing self, do so
				if (remove_self) {
					pop();
					endpoplist->child[right] = this;
					this->parent = endpoplist;
					endpoplist = this;
				}
				//pop nodes that were previously on left
				if (min_index<=self_index && left_child) {
					endpoplist = left_child->pop(endpoplist, min_index, max_index, self_index);
					if (nodes_on_left<max_index)
						nodes_on_left -= (self_index-min_index);
					else
						nodes_on_left -= (max_index-min_index);
				}
				return endpoplist;
            }
        protected:
            node(node& nocopy);
            node&operator=(node& nocopy);
        };
    };
 
    template<class type, class allocator>
    class track_base : private track_base<void, typename allocator::template rebind<char>::other>{
    protected:
        typedef track_base<void, typename allocator::template rebind<char>::other> parent;
        typedef typename parent::node node;
 
        typedef typename allocator::template rebind<type>::other allocator_type;
        typedef typename allocator_type::value_type value_type;
        typedef typename allocator_type::const_pointer const_pointer;
        typedef typename allocator_type::const_reference const_reference;
        typedef typename allocator_type::difference_type difference_type;
        typedef typename allocator_type::pointer pointer;
        typedef typename allocator_type::reference reference;
        typedef typename allocator_type::size_type size_type;
 
        struct payload : public node {
            typedef typename allocator::template rebind<payload>::other payload_allocator_type;
 
            value_type data;
            payload() :node(), data() {}
            payload(use_def_ctor) :node(), data() {}
#ifdef HAS_RVALUES
			template<class U> payload(U&& d) :node(), data(std::forward<U>(d)) {}
#endif
            template<class U> payload(const U& d) :node(), data(d) {}
 
			void erase(payload_allocator_type& al) noexcept(true) {
				al.destroy(this);
				al.deallocate(this, sizeof(this));
			}
        };
        typedef typename allocator::template rebind<payload>::other payload_allocator_type; 
 
        struct root_type : public node, public payload_allocator_type {
            //root's parent and child[right] are always nullptr.  Always.  Period.
            root_type() : node(), payload_allocator_type() {}
		    root_type(node* own_tree, payload_allocator_type& a) :node(), payload_allocator_type(a) {this->child[left] = own_tree; own_tree->parent = this;}
            explicit root_type(const payload_allocator_type& a) : node(), payload_allocator_type(a) {}
            root_type(const root_type& rhs) : node(), payload_allocator_type(rhs) {cpy_ctor_(rhs);}
            root_type(const root_type& rhs, const payload_allocator_type& a) : node(), payload_allocator_type(a) {cpy_ctor_(rhs);}
#ifdef HAS_RVALUES
			root_type(root_type&& rhs) noexcept(true) : node(), payload_allocator_type(std::move(rhs)) {node::swap(rhs);}
#endif
            ~root_type() noexcept(true) {erase(0, this->nodes_on_left);}
            root_type& operator=(root_type rhs) noexcept(true) {swap(rhs); return *this;}
            void swap(root_type& rhs) noexcept(true) {
				using std::swap;
				node::swap(rhs); 
                swap(static_cast<payload_allocator_type&>(*this), static_cast<payload_allocator_type&>(rhs));
		    }
            template <class T0>
			node* emplace(node* ptr, T0&&p0) {
				assert(ptr->find_root() == this);
				assert(this->whole_tree_valid());
				side_type side = left;
				if (ptr->child[left]) {
					side = right;
					ptr = ptr->child[left];
					ptr = ptr->down_to_far(right);
				}
				root_type todo = construct_from(std::forward<T0>(p0));
				node* r = ptr->add_child(side, &todo, 1);
				ptr->add_size(side, 1);
                todo.release();
				this->child[left]->balance(r->get_index(), this->nodes_on_left, false, false);
                assert(this->assert_heights());
				return r;
            }
			template <class input_iterator>
			node* insert(node* ptr, input_iterator first, input_iterator last) {
				assert(ptr->find_root() == this);
				assert(this->whole_tree_valid());
				side_type side = left;
				if (ptr->child[left]) {
					side = right;
					ptr = ptr->child[left];
					ptr = ptr->down_to_far(right);
				}
				std::vector<root_type> todo;
				reserve_vector(todo, first, last, typename std::iterator_traits<input_iterator>::iterator_category());
				while(first != last)
					todo.push_back(construct_from(*(first++)));
				node* r = ptr->add_child(side, &todo.front(), todo.size());
				ptr->add_size(side, todo.size());
				for(auto it=todo.begin(); it!=todo.end();++it)
					it->release();
				this->child[left]->balance(r->get_index(), this->nodes_on_left, false, false);
                assert(this->assert_heights());
				return r;
			}
			void erase(node* p) noexcept(true) {
				assert(this->whole_tree_valid());
				assert(p->find_root() == this);
				size_type index = p->get_index();
				p->parent->sub_size(p->get_side(), 1);
				static_cast<payload*>(p)->erase(*this); 
				if (this->child[left]) {
					this->child[left]->balance(index, this->nodes_on_left, false, false);
				} else
                    assert(this->whole_tree_valid());
                assert(this->assert_heights());
			}
			void erase(size_type min_index, size_type max_index) noexcept(true) {
				assert(max_index<=this->nodes_on_left);
				assert(min_index<=max_index);
				assert(this->whole_tree_valid());
                if (min_index==max_index) return;
				node poplist;
				this->child[left]->pop(&poplist, min_index, max_index, this->nodes_on_left);
                this->nodes_on_left -= max_index-min_index;
				while(poplist.child[right])
					static_cast<payload*>(poplist.child[right])->erase(*this);
				if (this->child[left]) {
					this->child[left]->balance(min_index, this->nodes_on_left, false, false);
					this->child[left]->balance(min_index+1, this->nodes_on_left, false, false);
				} else
                    assert(this->whole_tree_valid());
                assert(this->assert_heights());
			}
			void erase(node* first, node* last) noexcept(true) {
				assert(first->find_root() ==this);
				assert( last->find_root() ==this);
				size_type min = first->get_index();
				size_type max = last->get_index();
				erase(min, max);
			}
            node* release() noexcept(true) {
                node* r = this->child[left];
                this->child[left] = NULL;
                this->nodes_on_left = 0;
                return r;
            }
        private:
            node* get() noexcept(true) {return this->child[left];}
            node* operator->() noexcept(true) {return this->child[left];}
            operator void*() noexcept(true) {return this->child[left];}
            size_type& total() noexcept(true) {return this->nodes_on_left;}
            root_type copy_from(const node& rhs)
            {
                root_type l(static_cast<const payload_allocator_type&>(*this));
                if(rhs.child[left])
			        l = copy_from(*(rhs.child[left]));
                root_type p = construct_from(static_cast<const payload&>(rhs).data);
                if (rhs.child[left]) {
			        p.total() += l.total();
                    l->parent = p.get();
                    p->nodes_on_left = l.total();
                    p->child[left] = l.release();
                }
                if(rhs.child[right]){
			        root_type r(copy_from(*(rhs.child[right])));
                    r->parent = p.get();
			        p.total() += r.total();
			        p->child[right] = r.release();
                }
                return p;
            }
            void cpy_ctor_(const root_type& rhs) {
                this->nodes_on_left = rhs.nodes_on_left;
                if (rhs.child[left]) {
                    this->child[left] = copy_from(*rhs.child[left]).release();
                    this->child[left]->parent = this;
                }
                assert(this->whole_tree_valid());
            }
 
			template <class U>
			root_type construct_from(U&& value)
			{
                root_type r(static_cast<const payload_allocator_type&>(*this));
                payload* t = payload_allocator_type::allocate(sizeof(payload));
                try {
				    payload_allocator_type::construct(t,  std::forward<U>(value));
                } catch(...) {
                    payload_allocator_type::deallocate(t, sizeof(payload));
                    throw;
                }
                r.child[left] = t;
                r.nodes_on_left = 1;
                return r;
			}
 
			template <class input_iterator>
			static void reserve_vector(std::vector<root_type>& v, input_iterator, input_iterator, std::input_iterator_tag)
			{v.reserve(32);} //arbitrarily picked
			template <class input_iterator>
			static void reserve_vector(std::vector<root_type>& v, input_iterator first, input_iterator last, std::random_access_iterator_tag)
			{v.reserve(last-first);}
        };
    };
 
    template<class type, class allocator=std::allocator<type>>
    class track : private track_base<type, typename allocator::template rebind<type>::other>{
    protected:
        typedef track_base<type, typename allocator::template rebind<type>::other> parent;
        typedef typename parent::root_type root_type;
        typedef typename parent::node node;
        typedef typename parent::payload payload;
 
        root_type root;
    public:
        typedef typename parent::allocator_type allocator_type;
        typedef typename parent::value_type value_type;
        typedef typename parent::reference reference;
        typedef typename parent::const_reference const_reference;
        typedef typename parent::pointer pointer;
        typedef typename parent::const_pointer const_pointer;
        typedef typename parent::difference_type difference_type;
        typedef typename parent::size_type size_type;
 
        class const_iterator;
        class iterator {
        public:
            typedef typename allocator_type::difference_type difference_type;
            typedef typename allocator_type::value_type value_type;
            typedef typename allocator_type::reference reference;
            typedef typename allocator_type::pointer pointer;
            typedef std::random_access_iterator_tag iterator_category;
 
            iterator() noexcept(true) :ptr() {}
            iterator(const iterator& rhs) noexcept(true) :ptr(rhs.ptr) {}
            friend bool operator==(const iterator& lhs, const iterator& rhs) noexcept(true) {return lhs.ptr==rhs.ptr;}
            friend bool operator!=(const iterator& lhs, const iterator& rhs) noexcept(true) {return lhs.ptr!=rhs.ptr;} 
            friend bool operator< (const iterator& lhs, const iterator& rhs) noexcept(true) {return lhs.ptr->get_index()< rhs.ptr->get_index();}
            friend bool operator<=(const iterator& lhs, const iterator& rhs) noexcept(true) {return lhs.ptr->get_index()<=rhs.ptr->get_index();}
            friend bool operator> (const iterator& lhs, const iterator& rhs) noexcept(true) {return lhs.ptr->get_index()> rhs.ptr->get_index();}
            friend bool operator>=(const iterator& lhs, const iterator& rhs) noexcept(true) {return lhs.ptr->get_index()>=rhs.ptr->get_index();} 
            iterator& operator++() noexcept(true) {ptr=ptr->find_one_to(right); return *this;}
            iterator operator++(int) noexcept(true) {iterator t(*this); ++*this; return t;}
            iterator& operator--() noexcept(true) {ptr=ptr->find_one_to(left); return *this;}
            iterator operator--(int) noexcept(true) {iterator t(*this); --*this; return t;}
            iterator& operator+=(size_type o) noexcept(true) {ptr = ptr->find_many_to(right, o); return *this;}
            friend iterator operator+(iterator it, size_type o) noexcept(true) {return it+=o;}
            friend iterator operator+(size_type o, iterator it) noexcept(true) {return it+=o;}
            iterator& operator-=(size_type o) noexcept(true) {ptr = ptr->find_many_to(left, o); return *this;} 
            friend iterator operator-(iterator it, size_type o) noexcept(true) {return it-=o;}
            difference_type operator-(const iterator& it) noexcept(true) {return ptr->get_index() - it.ptr->get_index();}
            reference operator*() const noexcept(true) {return static_cast<payload*>(ptr)->data;}
            pointer operator->() const noexcept(true) {return &static_cast<payload*>(ptr)->data;}
            reference operator[](size_type o) const noexcept(true) {return static_cast<payload*>(ptr->find_many_to(right, o))->data;}
            friend void swap(iterator& lhs, iterator& rhs) noexcept(true) {std::swap(lhs.ptr, rhs.ptr);}
        private:
            node* ptr;
            friend class track;
            friend class const_iterator;
            iterator(node* p) noexcept(true) :ptr(p) {}
        };
        class const_iterator {
        public:
            typedef typename allocator_type::difference_type difference_type;
            typedef typename allocator_type::value_type value_type;
            typedef typename allocator_type::const_reference reference;
            typedef typename allocator_type::const_pointer pointer;
            typedef std::bidirectional_iterator_tag iterator_category;
 
            const_iterator() noexcept(true) :ptr() {}
            const_iterator(const const_iterator& rhs) noexcept(true) :ptr(rhs.ptr) {}
            const_iterator(const iterator& rhs) noexcept(true) :ptr(rhs.ptr) {}
            friend bool operator==(const const_iterator& lhs, const const_iterator& rhs) noexcept(true) {return lhs.ptr==rhs.ptr;}
            friend bool operator!=(const const_iterator& lhs, const const_iterator& rhs) noexcept(true) {return lhs.ptr!=rhs.ptr;} 
            friend bool operator< (const const_iterator& lhs, const const_iterator& rhs) noexcept(true) {return lhs.ptr->get_index()< rhs.ptr->get_index();}
            friend bool operator<=(const const_iterator& lhs, const const_iterator& rhs) noexcept(true) {return lhs.ptr->get_index()<=rhs.ptr->get_index();}
            friend bool operator> (const const_iterator& lhs, const const_iterator& rhs) noexcept(true) {return lhs.ptr->get_index()> rhs.ptr->get_index();}
            friend bool operator>=(const const_iterator& lhs, const const_iterator& rhs) noexcept(true) {return lhs.ptr->get_index()>=rhs.ptr->get_index();} 
            const_iterator& operator++() noexcept(true) {ptr=ptr->find_one_to(right); return *this;}
            const_iterator operator++(int) noexcept(true) {const_iterator t(*this); ++*this; return t;}
            const_iterator& operator--() noexcept(true) {ptr=ptr->find_one_to(left); return *this;}
            const_iterator operator--(int) noexcept(true) {const_iterator t(*this); --*this; return t;}
            const_iterator& operator+=(size_type o) noexcept(true) {ptr = ptr->find_many_to(right, o); return *this;}
            friend const_iterator operator+(const_iterator it, size_type o) noexcept(true) {return it+=o;}
            friend const_iterator operator+(size_type o, const_iterator it) noexcept(true) {return it+=o;}
            const_iterator& operator-=(size_type o) noexcept(true) {ptr = ptr->find_many_to(left, o); return *this;} 
            friend const_iterator operator-(const_iterator it, size_type o) noexcept(true) {return it-=o;}
            friend difference_type operator-(const const_iterator& lhs, const const_iterator& rhs) noexcept(true) {return lhs.ptr->get_index() - rhs.ptr->get_index();}
            reference operator*() const noexcept(true) {return static_cast<const payload*>(ptr)->data;}
            pointer operator->() const noexcept(true) {return &static_cast<const payload*>(ptr)->data;}
            reference operator[](size_type o) const noexcept(true) {return static_cast<const payload*>(ptr->find_many_to(right, o))->data;}
            friend void swap(const_iterator& lhs, const_iterator& rhs) noexcept(true) {std::swap(lhs.ptr, rhs.ptr);}
        private:
            const node* ptr;
            friend class track;
            const_iterator(const node* p) noexcept(true) :ptr(p) {}
            iterator unconst() const noexcept(true) {return iterator(const_cast<node*>(ptr));}
        };
        typedef std::reverse_iterator<iterator> reverse_iterator;
        typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
 
        track() noexcept(true) : root() {}
	    track(const track& rhs) : root(rhs.root) {} //DARN YOU MSVC AND YOU'RE FAULURE OF IMPLICIT MOVE CONSTRUCTORS
#ifdef HAS_RVALUES
		track(track&& rhs) noexcept(true) :root(std::move(rhs.root)) {} //DARN YOU MSVC AND YOU'RE FAULURE OF IMPLICIT MOVE CONSTRUCTORS
#endif
		~track(){}
        explicit track(size_type n)
		    : root() {root.insert(&root, make_value_iterator(def_ctor()), make_value_iterator(n, def_ctor()));}
        track(size_type n, const value_type& val, const allocator_type& alloc = allocator_type())
             : root(alloc) {root.insert(&root, make_value_iterator(val), make_value_iterator(val)+n);}
        template <class input_iterator>
        track(input_iterator first, input_iterator last, const allocator_type& alloc = allocator_type())
             : root(alloc) {root.insert(&root, first, last);}
        //track(std::initializer_list<T> init, const allocator_type& alloc = allocator_type())
             //: allocator_type(alloc), root() {insert(&root, init.begin(), init.end(), root);}
        explicit track(const allocator_type& alloc) : root(alloc) {}
	    track(const track& rhs, const allocator_type& alloc) : root(rhs.root, alloc) {}
#ifdef HAS_RVALUES
		track(track&& rhs, const allocator_type& alloc) noexcept(true) :root(std::move(rhs), alloc) {}
#endif
 
	    iterator begin() noexcept(true) {return iterator(root.down_to_far(left));}
	    iterator end() noexcept(true) {return iterator(&root);}
        reverse_iterator rbegin() noexcept(true) {return reverse_iterator(iterator(root.down_to_far(left)));}
        reverse_iterator rend() noexcept(true) {return reverse_iterator(iterator(&root));}
        const_iterator begin() const noexcept(true) {return const_iterator(root.down_to_far(left));}
        const_iterator end() const noexcept(true) {return const_iterator(&root);}
        const_reverse_iterator rbegin() const noexcept(true) {return const_reverse_iterator(const_iterator(root.down_to_far(left)));}
        const_reverse_iterator rend() const noexcept(true) {return const_reverse_iterator(const_iterator(&root));}
        const_iterator cbegin() const noexcept(true) {return const_iterator(root.down_to_far(left));}
        const_iterator cend() const noexcept(true) {return const_iterator(&root);}
        const_reverse_iterator crbegin() const noexcept(true) {return const_reverse_iterator(const_iterator(root.down_to_far(left)));}
        const_reverse_iterator crend() const noexcept(true) {return const_reverse_iterator(const_iterator(&root));}
 
	    size_type size() const noexcept(true) {return root.nodes_on_left;}
	    size_type max_size() const noexcept(noexcept(root.max_size())) {return root.max_size();}
        void resize(size_type n) {
            if (n<root.nodes_on_left) {
				root.erase(root.down_to_offset(n), &root);
            } else if (n>root.nodes_on_left)
                root.insert(&root, make_value_iterator(def_ctor())+root.nodes_on_left, make_value_iterator(n, def_ctor()));
			assert(root.whole_tree_valid());
        }
        void resize(size_type n, value_type val) {
            if (n<root.nodes_on_left) {
				root.erase(root.down_to_offset(n), &root);
            } else if (n>root.nodes_on_left)
                root.insert(&root, make_value_iterator(val)+root.nodes_on_left, make_value_iterator(val)+n);
			assert(root.whole_tree_valid());
        }
        //size_type capacity() const noexcept;
	    bool empty() const noexcept(true) {return root.nodes_on_left==0;}
        //void reserve(size_type n);
        //void shrink_to_fit();
 
	    reference operator[](size_type n) noexcept(true) {return static_cast<payload*>(root.down_to_offset(n))->data;}
        const_reference operator[](size_type n) const noexcept(true) {return static_cast<const payload*>(root.down_to_offset(n))->data;}
        const_reference at(size_type n) const {
		    if (n>=size()) throw std::out_of_range("invalid index");
		    return static_cast<const payload*>(root.down_to_offset(n))->data;
	    }
        reference at(size_type n) {
		    if (n>=size()) throw std::out_of_range("invalid index");
		    return static_cast<payload*>(root.down_to_offset(n))->data;
	    }
	    reference front() noexcept(true) {return static_cast<payload*>(root.down_to_far(left))->data;}
        const_reference front() const noexcept(true) {return static_cast<const payload*>(root.down_to_far(left))->data;}
        reference back() noexcept(true) {return static_cast<payload*>(root.child[left]->down_to_far(right))->data;}
        const_reference back() const noexcept(true) {return static_cast<const payload*>(root.child[left]->down_to_far(right))->data;}
        //value_type* data() noexcept;
        //const value_type* data() const noexcept;
 
        template <class input_iterator>
        void assign(input_iterator first, input_iterator last) {track(first, last).swap(*this);}
        void assign(size_type n, const value_type& val) {track(make_value_iterator(val), make_value_iterator(val)+n).swap(*this);}
	    //void assign(std::initializer_list<value_type> il) {track(il.begin(), il.end().swap(*this);}
#ifdef HAS_RVALUES
		void push_back(value_type&& val) {root.emplace(&root, std::move(val));}
#endif
        void push_back(const value_type& val) {root.emplace(&root, val);}
	    void pop_back() noexcept(true) {root.erase(root.child[left]->down_to_far(right), &root);}
        iterator insert(const_iterator position, size_type n, const value_type& val) {return root.insert(position.unconst().ptr, make_value_iterator(val), make_value_iterator(val)+n);}
        template <class input_iterator>
        iterator insert(const_iterator position, input_iterator first, input_iterator last) {return root.insert(position.unconst().ptr, first, last);}
#ifdef HAS_RVALUES
		iterator insert(const_iterator position, value_type&& val) {return root.emplace(position.unconst().ptr, std::move(val));}
#endif
	    iterator insert(const_iterator position, const value_type& val) {return root.emplace(position.unconst().ptr, val);}
        //iterator insert(const_iterator position, std::initializer_list<value_type> il) {return root.insert(position.unconst().ptr, il.begin(), il.end());}
        iterator erase(const_iterator position) noexcept(true) {iterator p(position.unconst()); iterator r(p+1); root.erase(p.ptr); return r;}
        iterator erase(const_iterator first, const_iterator last) noexcept(true) {iterator l(last.unconst()); root.erase(first.unconst().ptr, l.ptr); return l;}
        void swap(track& rhs) noexcept(true) {root.swap(rhs.root);}
        void clear() noexcept(true) {root.erase(root.down_to_far(left), &root);}
#ifdef HAS_VARIADIC
		template <class... Args>
		iterator emplace(const_iterator position, Args&&... args) {return root.emplace(position.unconst().ptr, std::forward<Args...>(args));}
		template <class... Args>
		void emplace_back(Args&&... args) {emplace(cend(), std::forward<Args...>(args)...);}
#else
        template <class Args>
        iterator emplace(const_iterator position, Args&& args) {return root.emplace(position.unconst().ptr, std::forward<Args>(args));}
        template <class Args>
	    void emplace_back(Args&& args) {root.emplace(&root, std::forward<Args>(args));}
#endif
 
	    allocator_type get_allocator() const noexcept(true) {return root;}
 
        friend bool operator==(const track& lhs, const track& rhs) //these are affectively noexcept if == or whatever is noexcept
	    {return lhs.size()==rhs.size() && std::equal(lhs.cbegin(), lhs.cend(), rhs.cbegin());}
        friend bool operator!=(const track& lhs, const track& rhs) //but if I declare them as such, it requires those functions to exist
	    {return lhs.size()!=rhs.size() || !std::equal(lhs.cbegin(), lhs.cend(), rhs.cbegin());}
        friend bool operator< (const track& lhs, const track& rhs)
	    {return lexicographical_compare(lhs.cbegin(), lhs.cend(), rhs.cbegin(), rhs.cend(), std::less<value_type>());}
        friend bool operator<=(const track& lhs, const track& rhs)
	    {return lexicographical_compare(lhs.cbegin(), lhs.cend(), rhs.cbegin(), rhs.cend(), std::less_equal<value_type>());}
        friend bool operator> (const track& lhs, const track& rhs)
	    {return lexicographical_compare(lhs.cbegin(), lhs.cend(), rhs.cbegin(), rhs.cend(), std::greater<value_type>());}
        friend bool operator>=(const track& lhs, const track& rhs)
	    {return lexicographical_compare(lhs.cbegin(), lhs.cend(), rhs.cbegin(), rhs.cend(), std::greater_equal<value_type>());}
 
	    friend void swap(track& lhs, track& rhs) noexcept(true) {lhs.root.swap(rhs.root);}
    };
 
} //namespace mpd