#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