fork download 
  1. #pragma once
  2. #include "mpd/value_iterator/value_iterator.h"
  3.  
  4. #include <memory>
  5. #include <cassert>
  6. #include <stdexcept>
  7. #include <vector>
  8.  
  9. #ifdef DEBUG_THE_TRACK_CLASS
  10. #include <iostream>
  11. #include <iomanip>
  12. #endif
  13.  
  14. #ifdef _MSC_VER
  15. #define noexcept(X) throw()
  16. #define DEFAULTED {}
  17. namespace std {
  18.     template<class T>
  19.     struct is_copy_constructible 
  20.         :std::conditional<__has_copy(T), std::true_type, std::false_type>::type
  21.     {};
  22.     template<class T>
  23.     struct is_copy_assignable 
  24.         :std::conditional<__has_assign(T), std::true_type, std::false_type>::type
  25.     {};
  26. }
  27. #else
  28. #define DEFAULTED  = default;
  29. #endif
  30.  
  31.  
  32. /*This container matches the same interface with the following exceptions
  33. The elements are non-contiguous.
  34. There is no capacity(), reserve(), shrink_to_fit(), or data() member functions.
  35. Iterators and references are never invalidated, unless the element has been erased/cleared
  36. Virtually all operations are logarithmic. (including iterator advancement)
  37. */
  38. namespace mpd {
  39.  
  40. enum side_type {left=0, right=1};
  41. static side_type other(side_type side) noexcept(true) {return side!=left?left:right;}
  42. struct use_def_ctor{}; //when "constructing from" this, the default constructor is used instead
  43.  
  44. template<class type, class allocator>
  45. class track_base;
  46. template<class allocator>
  47. class track_base<void, allocator>{
  48. protected:
  49.     typedef typename allocator::difference_type difference_type;
  50.     typedef typename allocator::size_type size_type;
  51.     struct node {
  52.         typedef typename allocator::template rebind<node>::other node_allocator_type;
  53.         typedef typename node_allocator_type::reference reference;
  54.         //typedef typename node_allocator_type::const_reference const_reference;
  55.         typedef typename node_allocator_type::pointer pointer;
  56.         typedef typename node_allocator_type::const_pointer const_pointer;
  57.  
  58.         size_type nodes_on_left;
  59.         pointer parent;
  60.         pointer child[2];
  61.         node() noexcept(true) :nodes_on_left(), parent(), child() {}
  62.         pointer& parent_ptr_to_this() noexcept(true) {return parent->child[get_side()];}
  63.         const_pointer down_to_far(side_type dir) const noexcept(true) {
  64.             const_pointer ptr=this; 
  65.             while(ptr->child[dir]) 
  66.                 ptr = ptr->child[dir]; 
  67.             return ptr;
  68.         }
  69.         pointer down_to_far(side_type dir) noexcept(true) 
  70.         {return const_cast<pointer>(((const_pointer)this)->down_to_far(dir));}
  71.         side_type get_side() const noexcept(true) {return parent->child[right]==this ? right : left;} 
  72.         size_type num_nodes_on(side_type dir, size_type total_nodes) const noexcept(true) 
  73.         {if (dir == right) return total_nodes-nodes_on_left-1; return nodes_on_left;}
  74.         size_type child_offset(side_type dir, size_type my_offset) noexcept(true) 
  75.         {if (dir == right) return my_offset+nodes_on_left+1; return my_offset;}
  76.         const_pointer find_parent_on(side_type dir) const noexcept(true) {
  77.             const_pointer ptr=this;
  78.             while(ptr->get_side() == dir)
  79.                 ptr = ptr->parent;
  80.             return ptr->parent;
  81.         }
  82.         size_type get_size() const noexcept(true) {
  83.             size_type r = nodes_on_left;
  84.             const_pointer ptr=child[right];
  85.             while(ptr) {
  86.                 r += ptr->nodes_on_left + 1;
  87.                 ptr = ptr->child[right];
  88.             }
  89.             return r;
  90.         }
  91.         const_pointer find_root() const noexcept(true) {
  92.             const_pointer ptr=this;
  93.             while(ptr->parent)
  94.                 ptr = ptr->parent;
  95.             assert(ptr->child[right]==nullptr);
  96.             return ptr;
  97.         }
  98.         pointer find_root() noexcept(true)
  99.         {return const_cast<pointer>(((const_pointer)this)->find_root());}
  100.         const_pointer find_one_to(side_type dir) const noexcept(true) {
  101.             const_pointer ptr=this;
  102.             if(ptr->child[dir]) return ptr->child[dir]->down_to_far(other(dir));
  103.             return ptr->find_parent_on(dir);
  104.         }
  105.         pointer find_one_to(side_type dir) noexcept(true)
  106.         {return const_cast<pointer>(((const_pointer)this)->find_one_to(dir));}
  107.         const_pointer down_to_offset(size_type index) const noexcept(true) { //cannot go up
  108.             const_pointer ptr=this;
  109.             while(ptr->nodes_on_left != index) {
  110.                 if (ptr->nodes_on_left > index) {
  111.                     ptr = ptr->child[left];
  112.                 } else{
  113.                     index = index - ptr->nodes_on_left - 1;
  114.                     ptr = ptr->child[right];
  115.                 }
  116.             }
  117.             return ptr;
  118.         }
  119.         pointer down_to_offset(size_type index) noexcept(true) 
  120.         {return const_cast<pointer>(((const_pointer)this)->down_to_offset(index));}
  121.         const_pointer find_many_to(side_type dir, size_type count) const noexcept(true) { //can go up
  122.             const_pointer ptr=this;
  123.             if (dir == right) {
  124.                 for(;;) {
  125.                     if (count == 0) return ptr;
  126.                     if (ptr->parent == nullptr) return ptr->down_to_offset(count);
  127.                     if (ptr->get_side() == left) {
  128.                         unsigned nodes_on_right = ptr->parent->nodes_on_left - ptr->nodes_on_left - 1;
  129.                         if (count <= nodes_on_right) 
  130.                             return ptr->child[right]->down_to_offset(count-1);
  131.                         count -= nodes_on_right + 1;
  132.                         ptr = ptr->parent;
  133.                     } else {
  134.                         count += ptr->parent->nodes_on_left + 1;
  135.                         ptr = ptr->parent;
  136.                     }
  137.                 }
  138.             } else {
  139.                 for(;;) {
  140.                     if (count == 0) return ptr;
  141.                     if (ptr->nodes_on_left >= count)
  142.                         return ptr->child[left]->down_to_offset(ptr->nodes_on_left - count);
  143.                     count -= ptr->nodes_on_left + 1;
  144.                     ptr = ptr->parent;
  145.                 }
  146.             }
  147.         }
  148.         pointer find_many_to(side_type dir, size_type count) noexcept(true) 
  149.         {return const_cast<pointer>(((const_pointer)this)->find_many_to(dir, count));}
  150.         size_type get_index() const noexcept(true) {
  151.             const_pointer ptr=this;
  152.             size_type o = ptr->nodes_on_left;
  153.             while(ptr->parent) {
  154.                 if (ptr->get_side()==left)
  155.                     ptr = ptr->parent;
  156.                 else {
  157.                     ptr = ptr->parent;
  158.                     o += ptr->nodes_on_left + 1;
  159.                 }
  160.             }
  161.             return o;
  162.         }
  163.         void change_size(side_type dir, difference_type count) noexcept(true){
  164.             pointer ptr = this;
  165.             if (dir == left)
  166.                 ptr->nodes_on_left += count;
  167.             while(ptr->parent != nullptr) {
  168.                 dir = ptr->get_side();
  169.                 ptr = ptr->parent;
  170.                 if (dir == left)
  171.                     ptr->nodes_on_left += count;
  172.             }
  173.         }
  174. 	    bool is_just_to(side_type dir, const_pointer oldroot) const noexcept(true) {
  175. 		    oldroot = oldroot->child[dir];
  176. 		    while(oldroot) {
  177. 			    if (oldroot == this) 
  178. 				    return true;
  179. 			    oldroot = oldroot->child[!dir];
  180. 		    }
  181. 		    return false;
  182. 	    }
  183.         void print_tree() const noexcept(true) {
  184. #ifdef DEBUG_THE_TRACK_CLASS
  185.             std::vector<const node*> out(1, find_root()->child[left]);
  186.             std::vector<const node*> in;
  187.             std::vector<const node*> summary;
  188.             const size_type width = 64;
  189.             bool recurse;
  190.             do {
  191.                 recurse = false;
  192.                 in = out;
  193.                 out.clear();
  194.                 out.reserve(in.size()*2);
  195.                 size_type width_per = width/in.size();
  196.                 for(size_type i=0; i<in.size(); ++i) {
  197.                     if (in[i]) {
  198.                         std::cout << std::setw(width_per/2) << std::hex << ((unsigned(in[i])&0xFF0)>>4) << std::setw(width_per-width_per/2) << ' ';
  199.                         summary.push_back(in[i]);
  200.                         out.push_back(in[i]->child[left]);
  201.                         out.push_back(in[i]->child[right]);
  202.                         if (in[i]->child[left] || in[i]->child[right]) 
  203.                             recurse = true;
  204.                     } else {
  205.                         std::cout << std::setw(width_per/2) << ". " << std::setw(width_per-width_per/2) << ' ';
  206.                         out.push_back(nullptr);
  207.                         out.push_back(nullptr);
  208.                     }
  209.                 }
  210.                 std::cout << '\n';
  211.             }while(recurse && out.size()<32);
  212.             for(size_type i=0; i<summary.size(); ++i)
  213.                 std::cout << ((unsigned(summary[i])&0xFF0)>>4) << ' ' << summary[i] << ' ' << summary[i]->nodes_on_left << '\n';
  214. #endif
  215.         }
  216.         bool sub_tree_valid(size_type total_size) const noexcept(true) {
  217.             if (child[left]) {
  218.                 assert(child[left]->parent == this);
  219.                 child[left]->sub_tree_valid(nodes_on_left);
  220.             } else
  221.                 assert(nodes_on_left == 0);
  222.             if (child[right]) {
  223.                 assert(child[right]->parent == this);
  224.                 child[right]->sub_tree_valid(total_size-1-nodes_on_left);
  225.             } else
  226.                 assert(nodes_on_left + 1 == total_size);
  227.             return true;
  228.         }
  229.         bool whole_tree_valid() const noexcept(true) {
  230. #ifdef DEBUG_THE_TRACK_CLASS
  231.             const node* p = find_root();
  232.             if (p->child[left]) 
  233.                 return p->child[left]->sub_tree_valid(p->nodes_on_left);
  234.             assert(p->nodes_on_left == 0);
  235. #endif
  236.             return true;
  237.         }
  238. 	    pointer rotate(side_type dir, pointer newroot) noexcept(true) {
  239.             std::cout << "rotating " << newroot << " around " << this << '\n';
  240.             print_tree();
  241. 		    assert(newroot->is_just_to(other(dir), this));
  242.             assert(whole_tree_valid());
  243.             pointer A = child[!dir]; //might be D
  244.             pointer B = newroot->parent; //might be F
  245.             pointer C = newroot->child[!dir]; //might be NULL
  246.             pointer D = newroot;
  247.             pointer E = newroot->child[dir]; //might be NULL
  248.             pointer F = this;
  249.             pointer Z = parent;
  250.             size_type sizeofE=0;
  251.             if (dir == right)
  252.                 sizeofE = F->get_index() - D->get_index() - 1;
  253.             else
  254.                 sizeofE = D->nodes_on_left;
  255.             side_type D_side = D->get_side();
  256.             side_type F_side = get_side();
  257.             /*
  258.             ROTATES D TO BE NEW ROOT
  259.                       Z                 Z
  260.                       ?                 ?
  261. 	                  F*                D*
  262. 	                /   \             /    \
  263. 	              A*      O        A*         F*
  264. 	             / \              / \        / \
  265. 	            O   B*      ---> O   B*     E   O  
  266. 	               / \              / \    / \
  267. 	              O	  D*           O   C  O   O
  268. 		             / \              / \
  269. 	               C     E           O   O
  270.                   / \   / \
  271. 	             O   O O   O                          
  272.             */
  273.             B->child[D_side] = C;
  274.             if (C) C->parent = B;
  275.             A = F->child[!dir]; //might be changed
  276.             D->child[!dir] = A;
  277.             A->parent = D;
  278.             F->child[!dir] = E; 
  279.             if (E) E->parent = F;
  280.             D->child[dir] = F; 
  281.             F->parent = D;
  282.             Z->child[F_side] = D; 
  283.             D->parent = Z;
  284.  
  285.             print_tree();
  286.             if (dir==right) {
  287.                 D->nodes_on_left = F->nodes_on_left - sizeofE- 1;
  288.                 F->nodes_on_left = sizeofE;
  289.             } else {
  290.                 D->nodes_on_left += F->nodes_on_left + 1;
  291.                 while(B!=F && B!=D) {
  292.                     B->nodes_on_left -= sizeofE + 1;
  293.                     B = B->parent;
  294.                 }
  295.             }
  296.             print_tree();
  297.             assert(whole_tree_valid());
  298.             return newroot;
  299. 	    }
  300. 	    pointer rotate_at_least(side_type dir, size_type& count, size_type total_size) noexcept(true) {
  301.             assert(whole_tree_valid());
  302.             pointer ptr = child[!dir];
  303.             total_size = num_nodes_on(dir, total_size);
  304.             size_type check_next = ptr->num_nodes_on(dir, total_size);
  305.             while(check_next>count && ptr->child[dir]) {
  306.                 total_size = check_next;
  307.                 ptr = ptr->child[dir];
  308.                 check_next = ptr->num_nodes_on(dir, total_size);
  309.             }
  310.             count = total_size;
  311.             return rotate(dir, ptr);
  312.         }
  313.         void balance(size_type seek_offset, size_type total_size) noexcept(true) {balance(seek_offset, total_size, false, false);}
  314.         void balance(size_type seek_offset, size_type total_size, bool down_left, bool down_right) noexcept(true) {
  315.             assert(whole_tree_valid());
  316.             //seek_offset may be out of bounds, that's fine
  317.             bool did_rotate_thistime;
  318.             bool did_rotate_any = false;
  319.             pointer ptr = this;
  320.             size_type nodes_on_right=0;
  321.             do {
  322.                 did_rotate_thistime = false;
  323.                 nodes_on_right = ptr->num_nodes_on(right, total_size);
  324.                 //more than twice as many on the left as right
  325.                 if (ptr->nodes_on_left > (nodes_on_right+1)*2) {
  326.                     size_type delta = ptr->nodes_on_left - nodes_on_right*2 - 1;
  327.                     ptr = ptr->rotate_at_least(right, delta, total_size);
  328.                     did_rotate_thistime = true;
  329.                     did_rotate_any = true;
  330.                 //more than twice as many on the right as left
  331.                 } else if ((ptr->nodes_on_left+1)*2 < nodes_on_right) {
  332.                     size_type delta = nodes_on_right - ptr->nodes_on_left*2 - 1;
  333.                     ptr = ptr->rotate_at_least(left, delta, total_size);
  334.                     did_rotate_thistime = true;
  335.                     did_rotate_any = true;
  336.                 }
  337.             } while(did_rotate_thistime);
  338.  
  339.             bool seek_left = false;
  340.             bool seek_right = false;
  341.             if (seek_offset < ptr->nodes_on_left)
  342.                 seek_left = true;
  343.             if (seek_offset > ptr->nodes_on_left+1 && seek_offset < total_size)
  344.                 seek_right = true;
  345.  
  346.             if (ptr->child[left] && (did_rotate_any || down_left ||seek_left))
  347.                 ptr->child[left]->balance(seek_offset, ptr->nodes_on_left, down_left, did_rotate_any);
  348.             if (ptr->child[right] && (did_rotate_any || down_right || seek_right)) {
  349.                 seek_offset -= ptr->nodes_on_left-1;
  350.                 ptr->child[right]->balance(seek_offset, nodes_on_right, did_rotate_any, down_right);
  351.             }
  352.             assert(whole_tree_valid());
  353.         }
  354.         void pop() noexcept(true) {
  355.             side_type old_side = get_side();
  356.             if (child[left]==nullptr && child[right]==nullptr) {
  357.                 parent->child[old_side] = nullptr;
  358.             } else if (this->child[left]==nullptr || child[right]==nullptr) {
  359.                 bool child_on_right = (child[right] != nullptr);
  360.                 parent->child[old_side] = child[child_on_right];
  361.                 child[child_on_right]->parent = parent;
  362.             } else {
  363.                 pointer replacement = child[left]->down_to_far(right);
  364.                 side_type replacement_side = replacement->get_side();
  365.                 //remove references to replacement
  366.                 replacement->parent->child[replacement_side] = replacement->child[left];
  367.                 if (replacement->child[left])
  368.                     replacement->child[left]->parent = replacement->parent;
  369.                 //nothing points at replacement, set up replacement
  370.                 replacement->parent = parent;
  371.                 replacement->child[left] = child[left];
  372.                 replacement->child[right] = child[right];
  373.                 //point things at replacement
  374.                 parent->child[old_side] = replacement;
  375.                 if (child[left])
  376.                     child[left]->parent = replacement;
  377.                 if (child[right])
  378.                     child[right]->parent = replacement;
  379.             }
  380.         }
  381.     protected:
  382.         node(node& nocopy);
  383.         node&operator=(node& nocopy);
  384.         ~node() DEFAULTED
  385.     };
  386.     struct balance_after_no_matter_what {
  387.         balance_after_no_matter_what(node* root, size_type seek_offset) :root_(root), seek_offset_(seek_offset) {}
  388.         ~balance_after_no_matter_what()
  389.         {if (root_->child[left]) root_->child[left]->balance(seek_offset_, root_->nodes_on_left, false, false);}
  390.     protected:
  391.         node* root_;
  392.         size_type seek_offset_;
  393.     };
  394.     struct add_assign_no_matter_what {
  395.         add_assign_no_matter_what(size_type& lhs, size_type& rhs) :lhs_(&lhs), rhs_(&rhs) {}
  396.         ~add_assign_no_matter_what() {*lhs_ += *rhs_;}
  397.     protected:
  398.         size_type* lhs_;
  399.         size_type* rhs_;
  400.     };
  401.     struct sub_assign_no_matter_what {
  402.         sub_assign_no_matter_what(size_type& lhs, size_type& rhs) :lhs_(&lhs), rhs_(&rhs) {}
  403.         ~sub_assign_no_matter_what() {*lhs_ -= *rhs_;}
  404.     protected:
  405.         size_type* lhs_;
  406.         size_type* rhs_;
  407.     };
  408.     struct change_size_no_matter_what {
  409.         change_size_no_matter_what(node* ptr, side_type dir, size_type& count) :ptr_(ptr),dir_(dir),count_(&count){}
  410.         ~change_size_no_matter_what() {ptr_->change_size(dir_, *count_);}
  411.     protected:
  412.         node* ptr_;
  413.         side_type dir_;
  414.         size_type* count_;
  415.     };
  416.     struct assert_valid_after_no_matter_what {
  417.         assert_valid_after_no_matter_what(const node* root) :root_(root) {}
  418.         ~assert_valid_after_no_matter_what()
  419.         {assert(root_->whole_tree_valid());}
  420.     protected:
  421.         const node* root_;
  422.     };
  423. };
  424.  
  425. template<class type, class allocator>
  426. class track_base : private track_base<void, typename allocator::template rebind<char>::other>{
  427. protected:
  428.     typedef track_base<void, typename allocator::template rebind<char>::other> parent;
  429.     typedef typename parent::node node;
  430.     typedef typename parent::balance_after_no_matter_what balance_after_no_matter_what;
  431.     typedef typename parent::add_assign_no_matter_what add_assign_no_matter_what;
  432.     typedef typename parent::sub_assign_no_matter_what sub_assign_no_matter_what;
  433.     typedef typename parent::assert_valid_after_no_matter_what assert_valid_after_no_matter_what;
  434.     typedef typename parent::change_size_no_matter_what change_size_no_matter_what;
  435.  
  436.     typedef typename allocator::template rebind<type>::other allocator_type;
  437.     typedef typename allocator_type::value_type value_type;
  438.     typedef typename allocator_type::const_pointer const_pointer;
  439.     typedef typename allocator_type::const_reference const_reference;
  440.     typedef typename allocator_type::difference_type difference_type;
  441.     typedef typename allocator_type::pointer pointer;
  442.     typedef typename allocator_type::reference reference;
  443.     typedef typename allocator_type::size_type size_type;
  444.  
  445.     struct payload : public node {
  446.         typedef typename allocator::template rebind<payload>::other payload_allocator_type;
  447.  
  448.         value_type data;
  449.         payload() :node(), data() {}
  450.         template<class U> payload(U&& d) :node(), data(std::forward<U>(d)) {}
  451.  
  452.         void erase(payload_allocator_type& al) {
  453.             this->pop();
  454.             al.destroy(this);
  455.             al.deallocate(this, sizeof(payload));
  456.         }
  457.         void erase(payload_allocator_type& al, size_type min_index, size_type max_index, size_type total_size, size_type& out_erased) {
  458. 			assert(min_index<=max_index);
  459.             if (max_index+1>this->nodes_on_left && this->child[right]) {
  460.                 size_type skip = this->nodes_on_left+1;
  461. 				size_type min = min_index<skip ? 0 : min_index-skip;
  462. 				size_type max = max_index<skip ? 0 : max_index-skip;
  463.                 size_type nodes_on_right = this->num_nodes_on(right, total_size);
  464.                 static_cast<payload*>(this->child[right])->erase(al, min, max, nodes_on_right, out_erased);
  465.             }
  466.             size_type self_index = this->nodes_on_left; //cache it before we change the nodes_on_left
  467.             if (min_index<this->nodes_on_left && this->child[left]) {
  468.                 size_type erased_on_left=0;
  469.                 add_assign_no_matter_what t0(out_erased, erased_on_left);
  470.                 sub_assign_no_matter_what t1(this->nodes_on_left, erased_on_left);
  471.                 static_cast<payload*>(this->child[left])->erase(al, min_index, max_index, this->nodes_on_left, erased_on_left);
  472.             }
  473.             if (min_index <= self_index && max_index > self_index) {
  474.                 erase(al);
  475.                 ++out_erased;
  476.             }
  477.         }
  478.     };
  479.     typedef typename payload::payload_allocator_type payload_allocator_type;
  480.  
  481. 	struct tree_deleter {
  482. 		payload_allocator_type* a;
  483. 		size_type total;
  484. 		tree_deleter(payload_allocator_type& alloc, size_type total_nodes) noexcept(true) :a(&alloc), total(total_nodes) {}
  485. 		void operator()(payload* ptr) {size_type e;ptr->erase(*a, 0, total, total, e);}
  486. 	};
  487. 	typedef std::unique_ptr<payload, tree_deleter> owning_ptr;
  488. 	struct just_deallocate {
  489. 		payload_allocator_type* a;
  490. 		explicit just_deallocate(payload_allocator_type& alloc) noexcept(true) :a(&alloc) {}
  491. 		void operator()(payload* ptr) {a->deallocate(ptr, sizeof(payload));}
  492. 	};
  493. 	typedef std::unique_ptr<payload, just_deallocate> allocated_ptr;
  494.  
  495.     template <class U>
  496.     static owning_ptr construct_from(U&& value, payload_allocator_type& al)
  497.     {
  498. 		allocated_ptr t(al.allocate(sizeof(payload)), just_deallocate(al));
  499. 		al.construct(t.get(),  std::forward<U>(value));
  500. 		return owning_ptr(t.release(), tree_deleter(al, 1));
  501. 	}
  502.     static owning_ptr construct_from(use_def_ctor, payload_allocator_type& al)
  503.     {
  504. 		allocated_ptr t(al.allocate(sizeof(payload)), just_deallocate(al));
  505.         //@@@TODO MSVC10's allocator doesn't have this
  506. 		//al.construct(t.get());
  507.         new(t.get())payload();
  508. 		return owning_ptr(t.release(), tree_deleter(al, 1));
  509. 	}
  510.     static owning_ptr construct_from(node& rhs, payload_allocator_type& al)
  511.     {
  512. 		owning_ptr p(construct_from(static_cast<payload&>(rhs).data, al));
  513.         if(rhs.child[left]){
  514. 			owning_ptr l(construct_from(*(rhs.child[left]), al));
  515. 			p.get_deleter().total += l.get_deleter().total;
  516.             l->nodes_on_left = l.get_deleter().total;
  517.             l->parent = p.get();
  518. 			p->child[left] = l.release();
  519.         }
  520.         if(rhs.child[right]){
  521. 			owning_ptr r(construct_from(*(rhs.child[right]), al));
  522. 			p.get_deleter().total += r.get_deleter().total;
  523.             r->parent = p.get();
  524. 			p->child[right] = r.release();
  525.         }
  526.         return p;
  527.     }
  528.     template <class input_iterator>
  529.     node* add_child(node* par, side_type dir, input_iterator first, input_iterator last, payload_allocator_type& al, size_type, std::output_iterator_tag) {
  530.         std::vector<value_type> t(first, last); //copy to turn input iterators into random access
  531.         size_type out_added=0;
  532.         change_size_no_matter_what t0(par, dir, out_added);
  533.         return add_child(par, dir, std::make_move_iterator(t.begin()), al, t.size(), out_added);
  534.     }
  535.     template <class forward_iterator>
  536.     node* add_child(node* par, side_type dir, forward_iterator first, forward_iterator last, payload_allocator_type& al, size_type total_its, std::forward_iterator_tag){
  537.         if (total_its == 0) total_its = std::distance(first, last);
  538.         size_type out_added=0;
  539.         change_size_no_matter_what t0(par, dir, out_added);
  540.         return add_child(par, dir, first, al, total_its, out_added);
  541.     }
  542.     template <class forward_iterator>
  543.     node* add_child(node* par, side_type dir, forward_iterator first, payload_allocator_type& al, size_type total_its, size_type& out_added){
  544.         size_type half = total_its/2;
  545.         forward_iterator mid = std::next(first, half);
  546.         par->child[dir] = construct_from(*mid, al).release();
  547.         node* added = par->child[dir];
  548.         out_added += 1;
  549.         added->parent = par;
  550.         if (half < total_its-1)
  551.             add_child(added, right, std::next(mid), al, total_its-half-1, out_added);
  552.         if (half <= 0) 
  553.             return added;
  554.         size_type added_on_left = 0;
  555.         add_assign_no_matter_what t0(out_added, added_on_left);
  556.         add_assign_no_matter_what t1(added->nodes_on_left, added_on_left);
  557.         return add_child(added, left, first, al, half, added_on_left);
  558.     }        
  559.     struct root_type : public node, public payload_allocator_type {
  560.         //root's parent and child[right] are always nullptr.  Always.  Period.
  561.         root_type() : node(), payload_allocator_type() {}
  562. 		root_type(node* own_tree, payload_allocator_type& a) :node(), payload_allocator_type(a) {this->child[left] = own_tree;}
  563.         explicit root_type(const payload_allocator_type& a) : node(), payload_allocator_type(a) {}
  564.         root_type(const root_type& rhs) : node(), payload_allocator_type(rhs) {cpy_ctor_(rhs);}
  565.         root_type(const root_type& rhs, const payload_allocator_type& a) : node(), payload_allocator_type(a) {cpy_ctor_(rhs);}
  566.         root_type(root_type&& rhs) noexcept(true) : node(), payload_allocator_type() {swap(rhs);}
  567.         ~root_type() {size_type e=0; if (this->child[left]) static_cast<payload*>(this->child[left])->erase(*this, 0, this->nodes_on_left, this->nodes_on_left, e);}
  568.         root_type& operator=(root_type rhs) noexcept(true) {swap(rhs); return *this;}
  569.         void swap(root_type& rhs) noexcept(true) {
  570.             using std::swap;
  571.             swap(this->child[left], rhs.child[left]);
  572.             if (this->child[left])
  573.                 this->child[left]->parent = this;
  574.             if (rhs.child[left])
  575.                 rhs.child[left]->parent = &rhs;
  576.             swap(this->nodes_on_left, rhs.nodes_on_left);
  577.             swap(static_cast<payload_allocator_type&>(*this), static_cast<payload_allocator_type&>(rhs));
  578. 		}
  579.     private:
  580.         void cpy_ctor_(const root_type& rhs) {
  581.             this->nodes_on_left = rhs.nodes_on_left;
  582.             if (rhs.child[left]) {
  583.                 this->child[left] = construct_from(*rhs.child[left], *this).release();
  584.                 this->child[left]->parent = this;
  585.             }
  586.         }
  587.     };
  588.     template <class input_iterator>
  589.     node* insert(node* ptr, input_iterator first, input_iterator last, root_type& root) {
  590.         assert(ptr->find_root() == &root);
  591.         assert_valid_after_no_matter_what verify(&root);
  592.         side_type side = left;
  593.         if (ptr->child[left]) {
  594.             side = right;
  595.             ptr = ptr->child[left];
  596.             ptr = ptr->down_to_far(right);
  597.         }
  598.         balance_after_no_matter_what t0(&root, ptr->get_index());
  599.         return this->add_child(ptr, side, first, last, root, 0, typename std::iterator_traits<input_iterator>::iterator_category());
  600.     }
  601.     node* erase(node* p, root_type& root) {
  602.         assert(p->find_root() == &root);
  603.         assert_valid_after_no_matter_what verify(&root);
  604.         node* r(p+1); 
  605. 		p->parent->change_size(p->get_side(), -1);
  606.         static_cast<payload*>(p)->erase(root); 
  607.         return r;
  608.     }
  609.     node* erase(node* first, node* last, root_type& root) {
  610.         if (first != last) {
  611. 			assert(first->find_root() ==&root);
  612. 			assert( last->find_root() ==&root);
  613.             size_type min = first->get_index();
  614.             size_type max = last->get_index();
  615.             assert(min<max);
  616.             size_type out_num_erased=0;
  617.             balance_after_no_matter_what t0(&root, min+1);
  618.             balance_after_no_matter_what t1(&root, min);
  619.             assert_valid_after_no_matter_what verify(&root);
  620.             sub_assign_no_matter_what t3(root.nodes_on_left, out_num_erased);			
  621.             root.print_tree();
  622.             static_cast<payload*>(root.child[left])->erase(root, min, max, root.nodes_on_left, out_num_erased);
  623.         }
  624.         return last;
  625.     }
  626. };
  627.  
  628. template<class type, class allocator=std::allocator<type>>
  629. class track : private track_base<type, typename allocator::template rebind<type>::other>{
  630. protected:
  631.     typedef track_base<type, typename allocator::template rebind<type>::other> parent;
  632.     typedef typename parent::root_type root_type;
  633.     typedef typename parent::node node;
  634.     typedef typename parent::payload payload;
  635.     typedef typename parent::assert_valid_after_no_matter_what assert_valid_after_no_matter_what;
  636.  
  637.     root_type root;
  638. public:
  639.     typedef typename parent::allocator_type allocator_type;
  640.     typedef typename parent::value_type value_type;
  641.     typedef typename parent::reference reference;
  642.     typedef typename parent::const_reference const_reference;
  643.     typedef typename parent::pointer pointer;
  644.     typedef typename parent::const_pointer const_pointer;
  645.     typedef typename parent::difference_type difference_type;
  646.     typedef typename parent::size_type size_type;
  647.  
  648.     class const_iterator;
  649.     class iterator {
  650.     public:
  651.         typedef typename allocator_type::difference_type difference_type;
  652.         typedef typename allocator_type::value_type value_type;
  653.         typedef typename allocator_type::reference reference;
  654.         typedef typename allocator_type::pointer pointer;
  655.         typedef std::random_access_iterator_tag iterator_category;
  656.  
  657.         iterator() noexcept(true) :ptr() {}
  658.         iterator(const iterator& rhs) noexcept(true) :ptr(rhs.ptr) {}
  659.         friend bool operator==(const iterator& lhs, const iterator& rhs) noexcept(true) {return lhs.ptr==rhs.ptr;}
  660.         friend bool operator!=(const iterator& lhs, const iterator& rhs) noexcept(true) {return lhs.ptr!=rhs.ptr;} 
  661.         friend bool operator< (const iterator& lhs, const iterator& rhs) noexcept(true) {return lhs.ptr->get_index()< rhs.ptr->get_index();}
  662.         friend bool operator<=(const iterator& lhs, const iterator& rhs) noexcept(true) {return lhs.ptr->get_index()<=rhs.ptr->get_index();}
  663.         friend bool operator> (const iterator& lhs, const iterator& rhs) noexcept(true) {return lhs.ptr->get_index()> rhs.ptr->get_index();}
  664.         friend bool operator>=(const iterator& lhs, const iterator& rhs) noexcept(true) {return lhs.ptr->get_index()>=rhs.ptr->get_index();} 
  665.         iterator& operator++() noexcept(true) {ptr=ptr->find_one_to(right); return *this;}
  666.         iterator operator++(int) noexcept(true) {iterator t(*this); ++*this; return t;}
  667.         iterator& operator--() noexcept(true) {ptr=ptr->find_one_to(left); return *this;}
  668.         iterator operator--(int) noexcept(true) {iterator t(*this); --*this; return t;}
  669.         iterator& operator+=(size_type o) noexcept(true) {ptr = ptr->find_many_to(right, o); return *this;}
  670.         friend iterator operator+(iterator it, size_type o) noexcept(true) {return it+=o;}
  671.         friend iterator operator+(size_type o, iterator it) noexcept(true) {return it+=o;}
  672.         iterator& operator-=(size_type o) noexcept(true) {ptr = ptr->find_many_to(left, o); return *this;} 
  673.         friend iterator operator-(iterator it, size_type o) noexcept(true) {return it-=o;}
  674.         difference_type operator-(const iterator& it) noexcept(true) {return ptr->get_index() - it.ptr->get_index();}
  675.         reference operator*() const noexcept(true) {return static_cast<payload*>(ptr)->data;}
  676.         pointer operator->() const noexcept(true) {return &static_cast<payload*>(ptr)->data;}
  677.         reference operator[](size_type o) const noexcept(true) {return static_cast<payload*>(ptr->find_many_to(right, o))->data;}
  678.         friend void swap(iterator& lhs, iterator& rhs) noexcept(true) {std::swap(lhs.ptr, rhs.ptr);}
  679.     private:
  680.         node* ptr;
  681.         friend track;
  682.         friend const_iterator;
  683.         iterator(node* p) noexcept(true) :ptr(p) {}
  684.     };
  685.     class const_iterator {
  686.     public:
  687.         typedef typename allocator_type::difference_type difference_type;
  688.         typedef typename allocator_type::value_type value_type;
  689.         typedef typename allocator_type::const_reference reference;
  690.         typedef typename allocator_type::const_pointer pointer;
  691.         typedef std::bidirectional_iterator_tag iterator_category;
  692.  
  693.         const_iterator() noexcept(true) :ptr() {}
  694.         const_iterator(const const_iterator& rhs) noexcept(true) :ptr(rhs.ptr) {}
  695.         const_iterator(const iterator& rhs) noexcept(true) :ptr(rhs.ptr) {}
  696.         friend bool operator==(const const_iterator& lhs, const const_iterator& rhs) noexcept(true) {return lhs.ptr==rhs.ptr;}
  697.         friend bool operator!=(const const_iterator& lhs, const const_iterator& rhs) noexcept(true) {return lhs.ptr!=rhs.ptr;} 
  698.         friend bool operator< (const const_iterator& lhs, const const_iterator& rhs) noexcept(true) {return lhs.ptr->get_index()< rhs.ptr->get_index();}
  699.         friend bool operator<=(const const_iterator& lhs, const const_iterator& rhs) noexcept(true) {return lhs.ptr->get_index()<=rhs.ptr->get_index();}
  700.         friend bool operator> (const const_iterator& lhs, const const_iterator& rhs) noexcept(true) {return lhs.ptr->get_index()> rhs.ptr->get_index();}
  701.         friend bool operator>=(const const_iterator& lhs, const const_iterator& rhs) noexcept(true) {return lhs.ptr->get_index()>=rhs.ptr->get_index();} 
  702.         const_iterator& operator++() noexcept(true) {ptr=ptr->find_one_to(right); return *this;}
  703.         const_iterator operator++(int) noexcept(true) {const_iterator t(*this); ++*this; return t;}
  704.         const_iterator& operator--() noexcept(true) {ptr=ptr->find_one_to(left); return *this;}
  705.         const_iterator operator--(int) noexcept(true) {const_iterator t(*this); --*this; return t;}
  706.         const_iterator& operator+=(size_type o) noexcept(true) {ptr = ptr->find_many_to(right, o); return *this;}
  707.         friend const_iterator operator+(const_iterator it, size_type o) noexcept(true) {return it+=o;}
  708.         friend const_iterator operator+(size_type o, const_iterator it) noexcept(true) {return it+=o;}
  709.         const_iterator& operator-=(size_type o) noexcept(true) {ptr = ptr->find_many_to(left, o); return *this;} 
  710.         friend const_iterator operator-(const_iterator it, size_type o) noexcept(true) {return it-=o;}
  711.         friend difference_type operator-(const const_iterator& lhs, const const_iterator& rhs) noexcept(true) {return lhs.ptr->get_index() - rhs.ptr->get_index();}
  712.         reference operator*() const noexcept(true) {return static_cast<const payload*>(ptr)->data;}
  713.         pointer operator->() const noexcept(true) {return &static_cast<const payload*>(ptr)->data;}
  714.         reference operator[](size_type o) const noexcept(true) {return static_cast<const payload*>(ptr->find_many_to(right, o))->data;}
  715.         friend void swap(const_iterator& lhs, const_iterator& rhs) noexcept(true) {std::swap(lhs.ptr, rhs.ptr);}
  716.     private:
  717.         const node* ptr;
  718.         friend track;
  719.         const_iterator(const node* p) noexcept(true) :ptr(p) {}
  720.         iterator unconst() const noexcept(true) {return iterator(const_cast<node*>(ptr));}
  721.     };
  722.     typedef std::reverse_iterator<iterator> reverse_iterator;
  723.     typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
  724.  
  725.     track() : root() {}
  726. 	track(const track& rhs) : root(rhs.root) {} //DARN YOU MSVC AND YOU'RE FAULURE OF IMPLICIT MOVE CONSTRUCTORS
  727. 	track(track&& rhs) noexcept(true) :root() {swap(rhs);} //DARN YOU MSVC AND YOU'RE FAULURE OF IMPLICIT MOVE CONSTRUCTORS
  728.     explicit track(size_type n)
  729. 		: root() {insert(end(), make_value_iterator(0, use_def_ctor()), make_value_iterator(n, use_def_ctor()));}
  730.     track(size_type n, const value_type& val, const allocator_type& alloc = allocator_type())
  731.          : root(alloc) {insert(end(), make_value_iterator(0, val), make_value_iterator(n, val));}
  732.     template <class input_iterator>
  733.     track(input_iterator first, input_iterator last, const allocator_type& alloc = allocator_type())
  734.          : root(alloc) {insert(end(), first, last);}
  735.     //track(std::initializer_list<T> init, const allocator_type& alloc = allocator_type())
  736.          //: allocator_type(alloc), root() {insert(end(), init.begin(), init.end());}
  737.     explicit track(const allocator_type& alloc) : root(alloc) {}
  738. 	track(const track& rhs, const allocator_type& alloc) : root(rhs.root) {}
  739. 	track(track&& rhs, const allocator_type& alloc) noexcept(true) :root(alloc) {swap(rhs);}
  740.  
  741. 	iterator begin() noexcept(true) {return iterator(root.down_to_far(left));}
  742. 	iterator end() noexcept(true) {return iterator(&root);}
  743.     reverse_iterator rbegin() noexcept(true) {return reverse_iterator(iterator(root.down_to_far(left)));}
  744.     reverse_iterator rend() noexcept(true) {return reverse_iterator(iterator(&root));}
  745.     const_iterator begin() const noexcept(true) {return const_iterator(root.down_to_far(left));}
  746.     const_iterator end() const noexcept(true) {return const_iterator(&root);}
  747.     const_reverse_iterator rbegin() const noexcept(true) {return const_reverse_iterator(const_iterator(root.down_to_far(left)));}
  748.     const_reverse_iterator rend() const noexcept(true) {return const_reverse_iterator(const_iterator(&root));}
  749.     const_iterator cbegin() const noexcept(true) {return const_iterator(root.down_to_far(left));}
  750.     const_iterator cend() const noexcept(true) {return const_iterator(&root);}
  751.     const_reverse_iterator crbegin() const noexcept(true) {return const_reverse_iterator(const_iterator(root.down_to_far(left)));}
  752.     const_reverse_iterator crend() const noexcept(true) {return const_reverse_iterator(const_iterator(&root));}
  753.  
  754. 	size_type size() const noexcept(true) {return root.nodes_on_left;}
  755. 	size_type max_size() const noexcept(noexcept(root.max_size())) {return root.max_size();}
  756.     void resize(size_type n) {
  757.         assert_valid_after_no_matter_what verify(&root);
  758.         if (n<root.nodes_on_left) {
  759.             erase(const_iterator(root.down_to_offset(n)), cend());
  760.         } else if (n>root.nodes_on_left)
  761.             insert(end(), make_value_iterator(root.nodes_on_left, use_def_ctor()), make_value_iterator(n, use_def_ctor()));
  762.     }
  763.     void resize(size_type n, value_type val) {
  764.         assert_valid_after_no_matter_what verify(&root);
  765.         if (n<root.nodes_on_left) {
  766.             erase(const_iterator(root.down_to_offset(n)), cend());
  767.         } else if (n>root.nodes_on_left)
  768.             insert(end(), make_value_iterator(root.nodes_on_left, val), make_value_iterator(n, val));
  769.     }
  770.     //size_type capacity() const noexcept;
  771. 	bool empty() const noexcept(true) {return size()==0;}
  772.     //void reserve(size_type n);
  773.     //void shrink_to_fit();
  774.  
  775. 	reference operator[](size_type n) noexcept(true) {return static_cast<payload*>(root.down_to_offset(n))->data;}
  776.     const_reference operator[](size_type n) const noexcept(true) {return static_cast<const payload*>(root.down_to_offset(n))->data;}
  777.     const_reference at(size_type n) const {
  778. 		if (n>=size()) throw std::out_of_range("invalid index");
  779. 		return static_cast<const payload*>(root.down_to_offset(n))->data;
  780. 	}
  781.     reference at(size_type n) {
  782. 		if (n>=size()) throw std::out_of_range("invalid index");
  783. 		return static_cast<payload*>(root.down_to_offset(n))->data;
  784. 	}
  785. 	reference front() noexcept(true) {return static_cast<payload*>(root.down_to_far(left))->data;}
  786.     const_reference front() const noexcept(true) {return static_cast<const payload*>(root.down_to_far(left))->data;}
  787.     reference back() noexcept(true) {return static_cast<payload*>(root.child[left]->down_to_far(right))->data;}
  788.     const_reference back() const noexcept(true) {return static_cast<const payload*>(root.child[left]->down_to_far(right))->data;}
  789.     //value_type* data() noexcept;
  790.     //const value_type* data() const noexcept;
  791.  
  792.     template <class input_iterator>
  793.     void assign(input_iterator first, input_iterator last) {track(first, last).swap(*this);}
  794.     void assign(size_type n, const value_type& val) {track(value_iterator<value_type>(0, val), value_iterator<value_type>(n, val)).swap(*this);}
  795. 	//void assign(std::initializer_list<value_type> il) {track(il.begin(), il.end().swap(*this);}
  796. 	void push_back(value_type val) {insert(cend(), std::make_move_iterator(&val), std::make_move_iterator(&val + 1));}
  797. 	void pop_back() {erase(cend()-1, cend());}
  798.     iterator insert(const_iterator position, size_type n, const value_type& val) {return insert(position, value_iterator<value_type>(0, val), value_iterator<value_type>(n, val));}
  799.     template <class input_iterator>
  800.     iterator insert(const_iterator position, input_iterator first, input_iterator last) {return parent::insert(position.unconst().ptr, first, last, root);}
  801. 	iterator insert(const_iterator position, value_type val) {return insert(position.unconst().ptr, std::make_move_iterator(&val), std::make_move_iterator(&val + 1));}
  802.     //iterator insert(const_iterator position, std::initializer_list<value_type> il);
  803.     iterator erase(const_iterator position) {return parent::erase(position.unconst().ptr, root);}
  804.     iterator erase(const_iterator first, const_iterator last) {return parent::erase(first.unconst().ptr, last.unconst().ptr, root);}
  805.     void swap(track& rhs) {root.swap(rhs.root);}
  806.     void clear() {root.print_tree(); erase(cbegin(), cend()); root.print_tree();}
  807.     //template <class... Args>
  808.     //iterator emplace(const_iterator position, Args&&... args); //@@@TODO
  809.     template <class Args0>
  810.     iterator emplace(const_iterator position, Args0&& args) {return insert(position, std::make_move_iterator(&args), std::make_move_iterator(&args +1));}
  811.     template <class Args0>
  812.     iterator emplace(const_iterator position, const Args0& args) {return insert(position, &args, &args +1);}
  813.     //template <class... Args>
  814. 	//void emplace_back(Args&&... args){emplace(cend(), std::forward<Args>(args)...);}
  815.     template <class Args0>
  816. 	void emplace_back(Args0&& args) {insert(cend(), std::make_move_iterator(&args), std::make_move_iterator(&args +1));}
  817.     template <class Args0>
  818. 	void emplace_back(const Args0& args) {insert(cend(), &args, &args +1);}
  819.  
  820. 	allocator_type get_allocator() const noexcept(true) {return root;}
  821.  
  822.     friend bool operator==(const track& lhs, const track& rhs)
  823. 	{return lhs.size()==rhs.size() && std::equal(lhs.cbegin(), lhs.cend(), rhs.cbegin());}
  824.     friend bool operator!=(const track& lhs, const track& rhs)
  825. 	{return lhs.size()!=rhs.size() || !std::equal(lhs.cbegin(), lhs.cend(), rhs.cbegin());}
  826.     friend bool operator< (const track& lhs, const track& rhs)
  827. 	{return lexicographical_compare(lhs.cbegin(), lhs.cend(), rhs.cbegin(), rhs.cend(), std::less<value_type>());}
  828.     friend bool operator<=(const track& lhs, const track& rhs)
  829. 	{return lexicographical_compare(lhs.cbegin(), lhs.cend(), rhs.cbegin(), rhs.cend(), std::less_equal<value_type>());}
  830.     friend bool operator> (const track& lhs, const track& rhs)
  831. 	{return lexicographical_compare(lhs.cbegin(), lhs.cend(), rhs.cbegin(), rhs.cend(), std::greater<value_type>());}
  832.     friend bool operator>=(const track& lhs, const track& rhs)
  833. 	{return lexicographical_compare(lhs.cbegin(), lhs.cend(), rhs.cbegin(), rhs.cend(), std::greater_equal<value_type>());}
  834.  
  835. 	friend void swap(track& lhs, track& rhs) {lhs.root.swap(rhs.root);}
  836. };
  837.  
  838. } //namespace mpd
  839.  
Not running #stdin #stdout 0s 0KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/mTrPYX
language:
C++14 (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!