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

Standard output is empty