LTOList
LTOList.hpp
1 #include <cassert>
2 #include <iostream>
3 #include <stack>
4 #include <type_traits>
5 #include <stdexcept>
6 #include <initializer_list>
7 
17 template<class T>
18 class LTOList {
19 public:
25  using value_type = T;
26 
33  using size_type = size_t;
34 
41  using difference_type = ptrdiff_t;
42 
49  using reference = T &;
50 
57  using const_reference = const T &;
58 
64  using pointer = T *;
65 
72  using const_pointer = const T *;
73 
75  // Node is an internal class and therefore not to be documented
76 
77  struct Node;
78  using pNode = Node *;
79 
80  struct Node {
81  pNode parent;
82  pNode child[2];
83  size_type n_children[2];
84  bool red; // as red-black tree
85  value_type value;
86 
87  // Constructors
88  Node()
89  : parent(nullptr), child{ nullptr, nullptr },
90  n_children{ 0, 0 }, red(false), value() {}
91  Node(bool is_red)
92  : parent(nullptr), child{ nullptr, nullptr },
93  n_children{ 0, 0 }, red(is_red), value() {}
94  Node(bool is_red, const_reference v)
95  : parent(nullptr), child{ nullptr, nullptr },
96  n_children{ 0, 0 }, red(is_red), value(v) {}
97  Node(bool is_red, T && v)
98  : parent(nullptr), child{ nullptr, nullptr },
99  n_children{ 0, 0 }, red(is_red), value(std::move(v)) {}
100  template<class... Args>
101  Node(bool is_red, Args... args)
102  : parent(nullptr), child{ nullptr, nullptr },
103  n_children{ 0, 0 }, red(is_red), value(args...) {}
104 
105  // For Base::origin (see below)
106  inline pNode o_root() const { return child[1]; }
107  inline pNode & o_root() { return child[1]; }
108  inline pNode o_front() const { return parent; }
109  inline pNode & o_front() { return parent; }
110  inline pNode o_back() const { return child[0]; }
111  inline pNode & o_back() { return child[0]; }
112 
113  void recompute_n_children(size_type side) {
114  if(side) side = 1;
115 
116  if(child[side]) {
117  n_children[side] = 1 + child[side]->n_children[0] +
118  child[side]->n_children[1];
119  } else {
120  n_children[side] = 0;
121  }
122  }
123 
124  // Return the side of the childrens in which `ch` is located
125  //
126  // NOTE 1:
127  // `ch` is assumed to be either child of `this`, that is,
128  // this method does not return the result that `ch` is not a
129  // child of `this`.
130  //
131  // NOTE 2:
132  // However, this method must checks whether `ch` is equal to
133  // `child[1]`, not `child[0]`, because of the construction of
134  // `Base::origin`. See the note in `struct Base` below.
135  size_type side_of_child(pNode ch) {
136  return (child[1] == ch ? 1 : 0);
137  }
138  };
140  // End of the definition of Node
141 
143  // Base is an internal class and therefore not to be documented
144 
145  // The base of LTOList: all operations are done by directly
146  // accessing nodes
147  struct Base {
148  // origin: pointer for ending iterator
149  // origin->child[1] (= origin->o_root()): root node in the
150  // tree origin->parent (= origin->o_front()): leftmost
151  // (smallest index) node in the tree origin->child[0] (=
152  // origin->o_back()): rightmost (largest index) node in the
153  // tree (To let `origin` work also as a sentinel, the root
154  // node must be represented as a child of `origin`.)
155  //
156  // The setups above are determined for the purpose of the
157  // following convenience:
158  // 1. Either child of `origin` must be the root node, and
159  // `origin->side_of_child(root)` must correctly identify
160  // the side of `root` from `origin`. This is because of the
161  // convenience that the root node can have a (virtual)
162  // parent node.
163  // 2. The previous element of `origin` computed by `neighbor`,
164  // namely `neighbor(origin, 0)`,
165  // must be the last element that truly stores an element
166  // (i.e., other than `origin`).
167  //
168  // `origin->parent`, `origin->child[0]` and `origin->child[1]`
169  // must be either "all of them are `nullptr`" or "none of them
170  // are `nullptr`". The list is empty if and only if all of
171  // them are `nullptr`.
172  pNode origin;
173 
174  Base() : origin(new Node(true)) {}
175  ~Base() { delete origin; }
176 
177  bool empty() const { return origin->o_root() == nullptr; }
178 
179  size_type size() const {
180  return origin->o_root()
181  ? (origin->o_root()->n_children[0] +
182  origin->o_root()->n_children[1] + 1)
183  : 0;
184  }
185 
186  size_type position(pNode n) {
187  // Find the index (number) of node `n`
188 
189  // If `end` is given
190  if(n == origin) return size();
191 
192  difference_type moved = 0; // How many `n` is moved
193  while(n != origin->o_root()) {
194  pNode p = n->parent;
195  size_type side = p->side_of_child(n);
196  if(side == 0) {
197  moved += n->n_children[1] + 1;
198  } else {
199  moved -= n->n_children[0] + 1;
200  }
201  n = p;
202  }
203  moved -= n->n_children[0];
204  moved = -moved;
205  assert(moved >= 0);
206  return static_cast<size_type>(moved);
207  }
208 
209  pNode advance(pNode n, difference_type dir) {
210  // Step 1: Move to parents
211  size_type side = (dir > 0 ? 1 : 0);
212  difference_type count = (dir > 0 ? dir : -dir);
213 
214  while(count > n->n_children[side]) {
215  // Loop until there are enough children under `n`
216 
217  pNode p = n->parent;
218  if(p == origin) {
219  // If reached at the root
220  return origin;
221  }
222 
223  // Note that 'count > n->n_children[side]' is assumed,
224  // that is, `count` cannot be negative here
225  if(side == p->side_of_child(n)) {
226  count += (n->n_children[1 - side] + 1);
227  } else {
228  count -= (n->n_children[side] + 1);
229  }
230  n = p;
231  }
232 
233  // Step 2: Move to children
234  while(count != 0) {
235  assert(count > 0);
236 
237  pNode c = n->child[side];
238  if(!c) {
239  // If no more child is found
240  return origin;
241  }
242 
243  count -= (1 + c->n_children[1 - side]);
244  if(count < 0) {
245  count = -count;
246  side = 1 - side;
247  }
248  n = c;
249  }
250  return n;
251  }
252 
253  pNode neighbor(pNode n, size_type side) {
254  if(side) side = 1;
255 
256  pNode tmp = n->child[side];
257  if(tmp) {
258  while(tmp->child[1 - side]) {
259  tmp = tmp->child[1 - side];
260  }
261  return tmp;
262  } else {
263  tmp = n;
264  for(;;) {
265  if(tmp->parent == origin) return origin;
266  if(tmp->parent->side_of_child(tmp) == 1 - side)
267  return tmp->parent;
268  tmp = tmp->parent;
269  }
270  }
271  }
272 
273  template<class STREAM>
274  static void display_tree_main(
275  STREAM & sr, const pNode n, size_type depth,
276  size_type offset) {
277  if(!n) return;
278 
279  display_tree_main(sr, n->child[0], depth + 1, offset);
280 
281  for(size_type i = 0; i < depth; ++i) {
282  sr << " ";
283  }
284  sr << '<' << (n->red ? 'R' : 'B') << ">["
285  << (offset + n->n_children[0]) << " this=" << n
286  << " parent=" << n->parent
287  << " children=" << n->n_children[0] << ","
288  << n->n_children[1] << "] " << n->value << std::endl;
289 
290  display_tree_main(
291  sr, n->child[1], depth + 1,
292  offset + n->n_children[0] + 1);
293  }
294 
295  template<class STREAM>
296  inline void display_tree(STREAM & sr) const {
297  sr << "{LTOList Size=" << size() << " Origin=" << origin
298  << " Root=" << origin->o_root()
299  << " Front=" << origin->o_front()
300  << " Back=" << origin->o_back() << "}" << std::endl;
301  display_tree_main(sr, origin->o_root(), 0, 0);
302  }
303 
304  pNode add(pNode pos, size_type side, const_reference v) {
305  pNode newnode = new Node(true, v);
306  return add_main(pos, side, newnode);
307  }
308 
309  pNode add(pNode pos, size_type side, T && v) {
310  pNode newnode = new Node(true, std::move(v));
311  return add_main(pos, side, newnode);
312  }
313 
314  template<class... Args>
315  pNode add_emplace(pNode pos, size_type side, Args... args) {
316  pNode newnode = new Node(true, args...);
317  return add_main(pos, side, newnode);
318  }
319 
320  pNode add_main(pNode pos, size_type side, pNode newnode) {
321  if(side) side = 1;
322 
323  // Node addition cannot be conducted if either of the
324  // followings is satisfied:
325  // - "pos == nullptr" and the tree is not empty
326  // - "pos == end()" and "side == 1"
327 
328  // ------------------------------------------------------------
329  // If no element is in the tree
330  // ------------------------------------------------------------
331  if(empty()) {
332  newnode->red = false;
333  newnode->parent = origin;
334  origin->o_root() = newnode;
335  origin->o_front() = newnode;
336  origin->o_back() = newnode;
337  return newnode;
338  }
339 
340  if(pos == origin && side == 0) {
341  pos = origin->o_back();
342  side = 1;
343  }
344 
345  if(pos == nullptr) throw std::invalid_argument("Invalid iterator");
346  if(pos == origin) throw std::invalid_argument("Elements cannot be inserted after the end of the list");
347 
348  // ------------------------------------------------------------
349  // If at least one element is in the tree
350  // ------------------------------------------------------------
351 
352  // If the new node becomes the new first/last element,
353  // point it
354  if(pos == origin->o_front() && side == 0) {
355  origin->o_front() = newnode;
356  } else if(pos == origin->o_back() && side == 1) {
357  origin->o_back() = newnode;
358  }
359 
360  // Since a node insertion must begin with a leaf to
361  // conduct rotations, in case `pos->child[side]` is not
362  // `nullptr`, 1) Find the `side` neighbor of `pos`,
363  // denoted by `pos_ins`. 2) Insert the new node to the
364  // opposite of `side`.
365  pNode pos_ins;
366  size_type side_ins;
367  if(pos->child[side] == nullptr) {
368  pos_ins = pos;
369  side_ins = side;
370  } else {
371  pos_ins = neighbor(pos, side);
372  // Since `pos->child[side]` is not `nullptr`,
373  // `neighbor(pos, side)` cannot be `nullptr`
374  side_ins = 1 - side;
375  }
376  assert(pos_ins->child[side_ins] == nullptr);
377  pos_ins->child[side_ins] = newnode;
378  newnode->parent = pos_ins;
379  pos_ins->n_children[side_ins] = 1;
380 
381  // Rotations
382  pNode rotpos[4];
383  size_type rotsides[3];
384  rotpos[0] = newnode;
385  rotpos[1] = pos_ins;
386  rotsides[0] = side_ins;
387  while(rotpos[1]->red) {
388  assert(rotpos[0]->red);
389  if(rotpos[0] == origin->o_root()) {
390  // If reached the root
391  rotpos[0]->red = false;
392  break;
393  }
394  if(rotpos[1] == origin->o_root()) {
395  // If reached the root
396  rotpos[1]->red = false;
397  break;
398  }
399 
400  rotpos[2] = rotpos[1]->parent;
401  rotpos[3] = rotpos[2]->parent;
402  rotsides[1] = rotpos[2]->side_of_child(rotpos[1]);
403  rotsides[2] = rotpos[3]->side_of_child(rotpos[2]);
404 
405  if(rotsides[0] == rotsides[1]) {
406  // (The figure below is rotsides[0] == 0; invert
407  // if rotsides[0] == 1)
408  // [3] [3]
409  // : :
410  // b[2] r[1]
411  // / \ / \
412  // r[1] [D] --> b[0]* b[2]
413  // / \ / \ / \
414  // r[0] [C] [A] [B] [C] [D]
415  // / \
416  // [A] [B]
417  //
418  // (*: repainted red to black)
419  // ([A], [B], [C] and [D] has the same 'black
420  // height')
421 
422  // Connection 2-C
423  rotpos[2]->child[rotsides[0]] =
424  rotpos[1]->child[1 - rotsides[0]];
425  if(rotpos[2]->child[rotsides[0]])
426  rotpos[2]->child[rotsides[0]]->parent =
427  rotpos[2];
428  // Connection 1-2
429  rotpos[1]->child[1 - rotsides[0]] = rotpos[2];
430  if(rotpos[2]) rotpos[2]->parent = rotpos[1];
431  // Connection 1-3
432  rotpos[3]->child[rotsides[2]] = rotpos[1];
433  if(rotpos[1]) rotpos[1]->parent = rotpos[3];
434 
435  rotpos[0]->red = false;
436 
437  rotpos[2]->recompute_n_children(rotsides[0]);
438  rotpos[1]->recompute_n_children(0);
439  rotpos[1]->recompute_n_children(1);
440  } else { // rotsides[0] != rotsides[1]
441  // (The figure below is rotsides[0] == 0; invert
442  // if rotsides[0] == 1)
443  // [3] [3]
444  // : :
445  // b[2] r[0]
446  // / \ / \
447  // [A] [1]r --> b[2] b[1]*
448  // / \ / \ / \
449  // r[0] [D] [A] [B] [C] [D]
450  // / \
451  // [B] [C]
452  //
453  // (*: repainted red to black)
454  // ([A], [B], [C] and [D] has the same 'black
455  // height')
456 
457  // Connection 1-C
458  rotpos[1]->child[rotsides[0]] =
459  rotpos[0]->child[rotsides[1]];
460  if(rotpos[0]->child[rotsides[1]])
461  rotpos[0]->child[rotsides[1]]->parent =
462  rotpos[1];
463  // Connection 2-B
464  rotpos[2]->child[rotsides[1]] =
465  rotpos[0]->child[rotsides[0]];
466  if(rotpos[0]->child[rotsides[0]])
467  rotpos[0]->child[rotsides[0]]->parent =
468  rotpos[2];
469  // Connection 0-1
470  rotpos[0]->child[rotsides[1]] = rotpos[1];
471  if(rotpos[1]) rotpos[1]->parent = rotpos[0];
472  // Connection 0-2
473  rotpos[0]->child[rotsides[0]] = rotpos[2];
474  if(rotpos[2]) rotpos[2]->parent = rotpos[0];
475  // Connection 3-0
476  rotpos[3]->child[rotsides[2]] = rotpos[0];
477  if(rotpos[0]) rotpos[0]->parent = rotpos[3];
478 
479  rotpos[1]->red = false;
480 
481  rotpos[2]->recompute_n_children(1 - rotsides[0]);
482  rotpos[1]->recompute_n_children(rotsides[0]);
483  rotpos[0]->recompute_n_children(0);
484  rotpos[0]->recompute_n_children(1);
485  }
486 
487  // Next step
488  rotpos[0] = rotpos[3]->child[rotsides[2]];
489  rotpos[1] = rotpos[3];
490  rotsides[0] = rotsides[2];
491  }
492 
493  // Recomputation of `n_children`
494  // At this point, `recpos` already has correct
495  // `n_children`, but its ancestors not
496  pNode recpos = rotpos[0];
497  if(recpos != origin) {
498  for(;;) {
499  pNode par = recpos->parent;
500  if(par == origin) break;
501  size_type recpos_side =
502  par->side_of_child(recpos);
503 
504  par->recompute_n_children(recpos_side);
505  recpos = par;
506  }
507  }
508 
509  return newnode;
510  }
511 
512  pNode remove(pNode pos) {
513  // Remove the node
514 
515  if(pos == nullptr) throw std::invalid_argument("Invalid iterator");
516  if(pos == origin) throw std::invalid_argument("The end of the list cannot be deleted");
517 
518  // In case the removed node is the only node in the tree
519  if(pos == origin->o_front() && pos == origin->o_back()) {
520  origin->o_root() = nullptr;
521  origin->o_front() = nullptr;
522  origin->o_back() = nullptr;
523  delete pos;
524  return origin;
525  }
526 
527  pNode returned_pos = nullptr;
528  pNode neighbor_pos = nullptr;
529 
530  // - returned_pos: the next element of the removed element
531  // - neighbor_pos: the neighboring element if the removed
532  // element has two children, or null otherwise
533  //
534  // Noticing that
535  // - returned_pos must be always identified, and
536  // - neighbor_pos must be identified only if the removed
537  // element (`pos`) has two children, we process as
538  // follows.
539  if(pos == origin->o_back()) {
540  // In case we cannot take `returned_pos` directly,
541  // that is, `pos` is the last element, `pos` CANNOT
542  // have two children.
543  returned_pos = origin; // end()
544  } else {
545  returned_pos = neighbor(pos, 1);
546  if(pos->child[0] && pos->child[1]) {
547  neighbor_pos = returned_pos;
548  }
549  }
550 
551  if(neighbor_pos) {
552  // Notice that `neighbor_pos` must be descendant of
553  // `pos`, since this exists only if `pos->child[1]`
554  // exists.
555  // TODO: Test this
556  pNode pos_parent = pos->parent;
557  size_t pos_parent_side =
558  pos_parent->side_of_child(pos);
559  pNode pos_lc = pos->child[0];
560  pNode pos_rc = pos->child[1];
561 
562  pNode neighbor_pos_parent = neighbor_pos->parent;
563  size_t neighbor_pos_parent_side =
564  neighbor_pos_parent->side_of_child(neighbor_pos);
565  pNode neighbor_pos_lc = neighbor_pos->child[0];
566  pNode neighbor_pos_rc = neighbor_pos->child[1];
567 
568  if(neighbor_pos_parent == pos) {
569  // If two swapped nodes are neighboring
570  pos_parent->child[pos_parent_side] = neighbor_pos;
571  if(neighbor_pos_parent_side == 1) {
572  if(pos_lc) pos_lc->parent = neighbor_pos;
573  } else {
574  if(pos_rc) pos_rc->parent = neighbor_pos;
575  }
576  if(neighbor_pos_lc) neighbor_pos_lc->parent = pos;
577  if(neighbor_pos_rc) neighbor_pos_rc->parent = pos;
578 
579  pos->parent = neighbor_pos;
580  pos->child[0] = neighbor_pos_lc;
581  pos->child[1] = neighbor_pos_rc;
582  neighbor_pos->parent = pos_parent;
583  if(neighbor_pos_parent_side == 1) {
584  neighbor_pos->child[0] = pos_lc;
585  neighbor_pos->child[1] = pos;
586  } else {
587  neighbor_pos->child[0] = pos;
588  neighbor_pos->child[1] = pos_rc;
589  }
590  } else {
591  pos_parent->child[pos_parent_side] = neighbor_pos;
592  if(pos_lc) pos_lc->parent = neighbor_pos;
593  if(pos_rc) pos_rc->parent = neighbor_pos;
594  neighbor_pos_parent
595  ->child[neighbor_pos_parent_side] = pos;
596  if(neighbor_pos_lc) neighbor_pos_lc->parent = pos;
597  if(neighbor_pos_rc) neighbor_pos_rc->parent = pos;
598 
599  pos->parent = neighbor_pos_parent;
600  pos->child[0] = neighbor_pos_lc;
601  pos->child[1] = neighbor_pos_rc;
602  neighbor_pos->parent = pos_parent;
603  neighbor_pos->child[0] = pos_lc;
604  neighbor_pos->child[1] = pos_rc;
605  }
606  std::swap(
607  pos->n_children[0], neighbor_pos->n_children[0]);
608  std::swap(
609  pos->n_children[1], neighbor_pos->n_children[1]);
610  std::swap(pos->red, neighbor_pos->red);
611 
612  if(pos == origin->o_front()) {
613  // In case the removed node is the first element
614  origin->o_front() = neighbor_pos;
615  }
616  } else {
617  // In case the removed node is ...
618  if(pos == origin->o_front()) {
619  // In case the removed node is the first element
620  origin->o_front() = neighbor(pos, 1);
621  } else if(pos == origin->o_back()) {
622  // In case the removed node is the last element
623  origin->o_back() = neighbor(pos, 0);
624  }
625  }
626  assert(
627  pos->child[0] == nullptr || pos->child[1] == nullptr);
628 
629  pNode pos_adjust = pos->parent;
630  bool adjust_needed = !(pos->red);
631  size_type side_adjust = pos_adjust->side_of_child(pos);
632  pos_adjust->child[side_adjust] =
633  (pos->child[1] ? pos->child[1] : pos->child[0]);
634  if(pos_adjust->child[side_adjust]) {
635  pos_adjust->child[side_adjust]->parent = pos_adjust;
636  }
637 
638  delete pos;
639  pos_adjust->recompute_n_children(side_adjust);
640 
641  // Rotate the tree to adjust the 'black'-height
642  while(adjust_needed && pos_adjust != origin) {
643  adjust_needed = false;
644 
645  // Here, pos_adjust->child[side_adjust] has fewer
646  // 'black'-height by one than others
647  pNode pos_reduced = pos_adjust->child[side_adjust];
648  pNode pos_sibling =
649  pos_adjust->child[1 - side_adjust];
650 
651  assert(pos_sibling);
652 
653  if(pos_sibling->red) {
654  // (The figure below is side_adjust == 0; invert
655  // if side_adjust == 1) [a]: pos_adjust [r]:
656  // pos_reduced (possibly null) [s]: pos_sibling
657  // "%": fewer 'black'-height
658  //
659  // b[a]
660  // _/ \_
661  // %[r] r[s]
662  // / \ / \
663  // [A] [B] b[C] [D]b
664  //
665  // is rotated as
666  //
667  // b[s]
668  // / \
669  // r[a] [D]b
670  // / \
671  // %[r] [C]b
672  // / \
673  // [A] [B]
674  //
675  // Here, since the subtree [r] still has fewer
676  // 'black'-height by one, we rotate it for
677  // [r]-[a]-[C] (processed next).
678  pNode pos_adjust_parent = pos_adjust->parent;
679  size_type side_adjust_parent =
680  pos_adjust_parent->side_of_child(pos_adjust);
681 
682  pos_adjust->child[1 - side_adjust] =
683  pos_sibling->child[side_adjust];
684  if(pos_sibling->child[side_adjust])
685  pos_sibling->child[side_adjust]->parent =
686  pos_adjust;
687  pos_sibling->child[side_adjust] = pos_adjust;
688  pos_adjust->parent = pos_sibling;
689  pos_sibling->parent = pos_adjust_parent;
690  pos_adjust_parent->child[side_adjust_parent] =
691  pos_sibling;
692 
693  pos_adjust->recompute_n_children(0);
694  pos_adjust->recompute_n_children(1);
695  pos_sibling->recompute_n_children(side_adjust);
696  pos_adjust_parent->recompute_n_children(
697  side_adjust_parent);
698 
699  pos_adjust->red = true;
700  pos_sibling->red = false;
701 
702  pos_sibling = pos_adjust->child[1 - side_adjust];
703  }
704 
705  assert(!(pos_sibling->red));
706 
707  // (The figure below is side_adjust == 0; invert if
708  // side_adjust == 1) [a]: pos_adjust [r]: pos_reduced
709  // (possibly null) [s]: pos_sibling
710  // "%": fewer 'black'-height
711  //
712  // [a]
713  // _/ \_
714  // %[r] b[s]
715  // / \ / \
716  // [A] [B] [C] [D]
717 
718  if(
719  pos_sibling->child[side_adjust] &&
720  pos_sibling->child[side_adjust]->red) {
721  // [a]
722  // _/ \_
723  // %[r] b[s]
724  // / \ / \
725  // [A] [B] r[n] [D]
726  // / \
727  // [C1] [C2]
728  //
729  // is rotated as
730  // [n]@ ... set the color that [a]
731  // originally has
732  // _/ \_
733  // b[a]* [s]b
734  // / \ / \
735  // %[r] [C1] [C2] [D]
736  // / \
737  // [A] [B]
738  pNode pos_adjust_parent = pos_adjust->parent;
739  size_type side_adjust_parent =
740  pos_adjust_parent->side_of_child(pos_adjust);
741 
742  pNode pos_nephew =
743  pos_sibling->child[side_adjust];
744  pos_adjust->child[side_adjust] = pos_reduced;
745  if(pos_reduced) pos_reduced->parent = pos_adjust;
746  pos_adjust->child[1 - side_adjust] =
747  pos_nephew->child[side_adjust];
748  if(pos_nephew->child[side_adjust])
749  pos_nephew->child[side_adjust]->parent =
750  pos_adjust;
751  pos_sibling->child[side_adjust] =
752  pos_nephew->child[1 - side_adjust];
753  if(pos_nephew->child[1 - side_adjust])
754  pos_nephew->child[1 - side_adjust]->parent =
755  pos_sibling;
756  pos_nephew->child[side_adjust] = pos_adjust;
757  pos_adjust->parent = pos_nephew;
758  pos_nephew->child[1 - side_adjust] = pos_sibling;
759  pos_sibling->parent = pos_nephew;
760 
761  pos_nephew->parent = pos_adjust_parent;
762  pos_adjust_parent->child[side_adjust_parent] =
763  pos_nephew;
764 
765  pos_nephew->red = pos_adjust->red;
766  pos_adjust->red = false;
767 
768  pos_adjust->recompute_n_children(0);
769  pos_adjust->recompute_n_children(1);
770  pos_sibling->recompute_n_children(side_adjust);
771  pos_nephew->recompute_n_children(0);
772  pos_nephew->recompute_n_children(1);
773 
774  pos_adjust = pos_nephew;
775 
776  side_adjust = side_adjust_parent;
777  pos_adjust = pos_adjust_parent;
778  } else if(
779  pos_sibling->child[1 - side_adjust] &&
780  pos_sibling->child[1 - side_adjust]->red) {
781  // [a]
782  // _/ \_
783  // %[r] b[s]
784  // / \ / \
785  // [A] [B] [C] [n]r
786  // / \
787  // [D1] [D2]
788  //
789  // is rotated as
790  // [s]@ ... set the color that [a]
791  // originally has
792  // _/ \_
793  // b[a]* b[n]*
794  // / \ / \
795  // %[r] [C] [D1] [D2]
796  // / \
797  // [A] [B]
798  pNode pos_adjust_parent = pos_adjust->parent;
799  size_type side_adjust_parent =
800  pos_adjust_parent->side_of_child(pos_adjust);
801 
802  pNode pos_nephew =
803  pos_sibling->child[1 - side_adjust];
804  pos_adjust->child[1 - side_adjust] =
805  pos_sibling->child[side_adjust];
806  if(pos_sibling->child[side_adjust])
807  pos_sibling->child[side_adjust]->parent =
808  pos_adjust;
809  pos_sibling->child[side_adjust] = pos_adjust;
810  pos_adjust->parent = pos_sibling;
811  pos_sibling->child[1 - side_adjust] = pos_nephew;
812  if(pos_nephew) pos_nephew->parent = pos_sibling;
813 
814  pos_sibling->red = pos_adjust->red;
815  pos_adjust->red = false;
816  pos_nephew->red = false;
817 
818  pos_sibling->parent = pos_adjust_parent;
819  pos_adjust_parent->child[side_adjust_parent] =
820  pos_sibling;
821 
822  pos_adjust->recompute_n_children(0);
823  pos_adjust->recompute_n_children(1);
824  pos_sibling->recompute_n_children(0);
825  pos_sibling->recompute_n_children(1);
826 
827  side_adjust = side_adjust_parent;
828  pos_adjust = pos_adjust_parent;
829  } else {
830  // [a]
831  // _/ \_
832  // %[r] b[s]
833  // / \ / \
834  // [A] [B] b[C] [D]b
835  //
836  // is modified as
837  //
838  // b[a]*
839  // _/ \_
840  // %[r] r[s]*
841  // / \ / \
842  // [A] [B] b[C] [D]b
843  //
844  // Here, in case [a] is black before the
845  // modification, this modification makes the
846  // 'black'-height of [a] be fewer by one than
847  // others, that is, we check the rotation once
848  // more.
849 
850  pos_sibling->red = true;
851  if(!(pos_adjust->red)) {
852  adjust_needed = true;
853  } else {
854  pos_adjust->red = false;
855  }
856  pos_adjust->recompute_n_children(side_adjust);
857  side_adjust =
858  pos_adjust->parent->side_of_child(pos_adjust);
859  pos_adjust = pos_adjust->parent;
860  }
861  }
862 
863  while(pos_adjust != origin) {
864  pos_adjust->recompute_n_children(side_adjust);
865  side_adjust =
866  pos_adjust->parent->side_of_child(pos_adjust);
867  pos_adjust = pos_adjust->parent;
868  }
869 
870  origin->o_root()->red = false;
871 
872  return returned_pos;
873  }
874 
875  void clear() {
876  if(this->empty()) return;
877 
878  // Remove all elements
879  using deletion_status_t = std::pair<pNode, bool>;
880  std::stack<deletion_status_t> st;
881  st.push(std::make_pair(origin->o_root(), false));
882 
883  while(!(st.empty())) {
884  deletion_status_t ds = st.top();
885  st.pop();
886 
887  if(!ds.first) continue;
888 
889  if(ds.second) {
890  delete ds.first;
891  } else {
892  st.push(std::make_pair(ds.first, true));
893  st.push(
894  std::make_pair(ds.first->child[1], false));
895  st.push(
896  std::make_pair(ds.first->child[0], false));
897  }
898  }
899 
900  origin->o_root() = nullptr;
901  origin->o_front() = nullptr;
902  origin->o_back() = nullptr;
903  }
904 
905  void copy_from(const Base & other) {
906  using copy_status_t = std::pair<pNode, pNode>;
907 
908  this->clear();
909  if(other.empty()) return;
910 
911  // Add the root node of `this` from `other`
912  pNode newOrignode = new Node();
913  *newOrignode = *(other.origin->o_root());
914  newOrignode->parent = origin;
915  origin->o_root() = newOrignode;
916  if(other.origin->o_root() == other.origin->o_front()) {
917  origin->o_front() = newOrignode;
918  }
919  if(other.origin->o_root() == other.origin->o_back()) {
920  origin->o_back() = newOrignode;
921  }
922 
923  // Copy
924  std::stack<copy_status_t> st;
925  st.push(
926  std::make_pair(newOrignode, other.origin->o_root()));
927 
928  while(!(st.empty())) {
929  copy_status_t cs = st.top();
930  st.pop();
931 
932  for(size_t p = 0; p <= 1; ++p) {
933  if(cs.second->child[p]) {
934  pNode newnode = new Node();
935  *newnode = *(cs.second->child[p]);
936  newnode->parent = cs.first;
937  cs.first->child[p] = newnode;
938  if(
939  cs.second->child[p] ==
940  other.origin->o_front()) {
941  origin->o_front() = newnode;
942  }
943  if(
944  cs.second->child[p] ==
945  other.origin->o_back()) {
946  origin->o_back() = newnode;
947  }
948 
949  st.push(std::make_pair(
950  newnode, cs.second->child[p]));
951  } else {
952  cs.first->child[p] = nullptr;
953  }
954  }
955  }
956  }
957  };
959  // End of the definition of Base
960 
961  // ------------------------------------------------------------
962  // APIs begin here
963  // ------------------------------------------------------------
964  class const_iterator;
965 
971  class iterator {
972  private:
973  Base * pbase_;
974  pNode n_;
975  iterator(Base & base, pNode n) : pbase_(&base), n_(n) {}
976 
977  public:
978  iterator() : pbase_(nullptr), n_(nullptr) {}
979  iterator(const iterator & other)
980  : pbase_(other.pbase_), n_(other.n_) {}
981  iterator operator=(const iterator & other) {
982  pbase_ = other.pbase_;
983  n_ = other.n_;
984  return *this;
985  }
986 
987  pointer operator->() const { return &(n_->value); }
988  reference operator*() const { return n_->value; }
989  iterator operator++() {
990  n_ = pbase_->neighbor(n_, 1);
991  return *this;
992  }
993  iterator operator--() {
994  n_ = pbase_->neighbor(n_, 0);
995  return *this;
996  }
997  iterator operator++(int) {
998  iterator tmp(*this);
999  n_ = pbase_->neighbor(n_, 1);
1000  return tmp;
1001  }
1002  iterator operator--(int) {
1003  iterator tmp(*this);
1004  n_ = pbase_->neighbor(n_, 0);
1005  return tmp;
1006  }
1007  iterator operator+=(difference_type dir) {
1008  n_ = pbase_->advance(n_, dir);
1009  return *this;
1010  }
1011  iterator operator-=(difference_type dir) {
1012  n_ = pbase_->advance(n_, -dir);
1013  return *this;
1014  }
1015  reference operator[](difference_type dir) {
1016  return pbase_->advance(n_, dir)->value;
1017  }
1018 
1020  friend class ::LTOList<value_type>;
1021  friend class const_iterator;
1023  template<class TT>
1024  friend std::ostream & operator<<(
1025  std::ostream & os,
1026  const typename ::LTOList<TT>::iterator & it);
1027 
1028  private:
1029  template<class IT1, class IT2>
1030  void from_same_list(const IT1 & it1, const IT2 & it2){
1031  if(it1.pbase_ != it2.pbase_){
1032  throw std::invalid_argument("The difference of iterators cannot be taken for different lists");
1033  }
1034  }
1035 
1036  // Global functions that accesses private members of
1037  // `iterator`
1038  friend iterator operator+(iterator it, difference_type dir) {
1039  iterator after = it;
1040  after += dir;
1041  return after;
1042  }
1043  friend iterator operator+(difference_type dir, iterator it) {
1044  iterator after = it;
1045  after += dir;
1046  return after;
1047  }
1048  friend iterator operator-(iterator it, difference_type dir) {
1049  iterator after = it;
1050  after -= dir;
1051  return after;
1052  }
1053  friend difference_type
1054  operator-(iterator it, iterator other) {
1055  from_same_list(it.pbase_, other.pbase_);
1056  return static_cast<difference_type>(
1057  it.pbase_->position(it.n_)) -
1058  static_cast<difference_type>(
1059  other.pbase_->position(other.n_));
1060  }
1061  friend bool operator<(iterator it, iterator other) {
1062  from_same_list(it.pbase_, other.pbase_);
1063  return it.pbase_->position(it.n_) <
1064  other.pbase_->position(other.n_);
1065  }
1066  friend bool operator<=(iterator it, iterator other) {
1067  from_same_list(it.pbase_, other.pbase_);
1068  return it.pbase_->position(it.n_) <=
1069  other.pbase_->position(other.n_);
1070  }
1071  friend bool operator>(iterator it, iterator other) {
1072  from_same_list(it.pbase_, other.pbase_);
1073  return it.pbase_->position(it.n_) >
1074  other.pbase_->position(other.n_);
1075  }
1076  friend bool operator>=(iterator it, iterator other) {
1077  from_same_list(it.pbase_, other.pbase_);
1078  return it.pbase_->position(it.n_) >=
1079  other.pbase_->position(other.n_);
1080  }
1081  friend bool operator==(iterator it, iterator other) {
1082  return it.n_ == other.n_;
1083  }
1084  friend bool operator!=(iterator it, iterator other) {
1085  return it.n_ != other.n_;
1086  }
1087  friend std::ostream &
1088  operator<<(std::ostream & out, iterator it) {
1089  out << "<LTOList::iterator " << it.n_ << ">";
1090  return out;
1091  }
1092  };
1093 
1099  class const_iterator {
1100  private:
1101  const Base * pbase_;
1102  pNode n_;
1103  const_iterator(const Base & base, pNode n)
1104  : pbase_(&base), n_(n) {}
1105 
1106  public:
1107  const_iterator() : pbase_(nullptr), n_(nullptr) {}
1108  const_iterator(const iterator & other)
1109  : pbase_(other.pbase_), n_(other.n_) {}
1110  const_iterator(const const_iterator & other)
1111  : pbase_(other.pbase_), n_(other.n_) {}
1112  const_iterator operator=(const iterator & other) {
1113  pbase_ = other.pbase_;
1114  n_ = other.n_;
1115  return *this;
1116  }
1117  const_iterator operator=(const const_iterator & other) {
1118  pbase_ = other.pbase_;
1119  n_ = other.n_;
1120  return *this;
1121  }
1122 
1123  const_pointer operator->() const { return &(n_->value); }
1124  const_reference operator*() const { return n_->value; }
1125  const_iterator operator++() {
1126  n_ = pbase_->neighbor(n_, 1);
1127  return *this;
1128  }
1129  const_iterator operator--() {
1130  n_ = pbase_->neighbor(n_, 0);
1131  return *this;
1132  }
1133  const_iterator operator++(int) {
1134  const_iterator tmp(*this);
1135  n_ = pbase_->neighbor(n_, 1);
1136  return tmp;
1137  }
1138  const_iterator operator--(int) {
1139  const_iterator tmp(*this);
1140  n_ = pbase_->neighbor(n_, 0);
1141  return tmp;
1142  }
1143  const_iterator operator+=(difference_type dir) {
1144  n_ = pbase_->advance(n_, dir);
1145  return *this;
1146  }
1147  const_iterator operator-=(difference_type dir) {
1148  n_ = pbase_->advance(n_, -dir);
1149  return *this;
1150  }
1151  const_reference operator[](difference_type dir) {
1152  return pbase_->advance(n_, dir)->value;
1153  }
1154 
1156  friend class ::LTOList<value_type>;
1158  template<class TT>
1159  friend std::ostream & operator<<(
1160  std::ostream & os,
1161  const typename ::LTOList<TT>::const_iterator & it);
1162 
1163  private:
1164  // Global functions that accesses private members of
1165  // `iterator`
1166  friend const_iterator
1167  operator+(const_iterator it, difference_type dir) {
1168  const_iterator after = it;
1169  after += dir;
1170  return after;
1171  }
1172  friend const_iterator
1173  operator+(difference_type dir, const_iterator it) {
1174  const_iterator after = it;
1175  after += dir;
1176  return after;
1177  }
1178  friend const_iterator
1179  operator-(const_iterator it, difference_type dir) {
1180  const_iterator after = it;
1181  after -= dir;
1182  return after;
1183  }
1184  friend difference_type
1185  operator-(const_iterator it, const_iterator other) {
1186  from_same_list(it.pbase_, other.pbase_);
1187  return static_cast<difference_type>(
1188  it.pbase_->position(it.n_)) -
1189  static_cast<difference_type>(
1190  other.pbase_->position(other.n_));
1191  }
1192  friend bool
1193  operator<(const_iterator it, const_iterator other) {
1194  from_same_list(it.pbase_, other.pbase_);
1195  return it.pbase_->position(it.n_) <
1196  other.pbase_->position(other.n_);
1197  }
1198  friend bool
1199  operator<=(const_iterator it, const_iterator other) {
1200  from_same_list(it.pbase_, other.pbase_);
1201  return it.pbase_->position(it.n_) <=
1202  other.pbase_->position(other.n_);
1203  }
1204  friend bool
1205  operator>(const_iterator it, const_iterator other) {
1206  from_same_list(it.pbase_, other.pbase_);
1207  return it.pbase_->position(it.n_) >
1208  other.pbase_->position(other.n_);
1209  }
1210  friend bool
1211  operator>=(const_iterator it, const_iterator other) {
1212  from_same_list(it.pbase_, other.pbase_);
1213  return it.pbase_->position(it.n_) >=
1214  other.pbase_->position(other.n_);
1215  }
1216  friend bool
1217  operator==(const_iterator it, const_iterator other) {
1218  return it.n_ == other.n_;
1219  }
1220  friend bool
1221  operator!=(const_iterator it, const_iterator other) {
1222  return it.n_ != other.n_;
1223  }
1224  friend std::ostream &
1225  operator<<(std::ostream & out, const_iterator it) {
1226  out << "<LTOList::const_iterator " << it.n_ << ">";
1227  return out;
1228  }
1229 
1230  friend difference_type
1231  operator-(const_iterator it, iterator other) {
1232  from_same_list(it.pbase_, other.pbase_);
1233  return static_cast<difference_type>(
1234  it.pbase_->position(it.n_)) -
1235  static_cast<difference_type>(
1236  other.pbase_->position(other.n_));
1237  }
1238  friend difference_type
1239  operator-(iterator it, const_iterator other) {
1240  from_same_list(it.pbase_, other.pbase_);
1241  return static_cast<difference_type>(
1242  it.pbase_->position(it.n_)) -
1243  static_cast<difference_type>(
1244  other.pbase_->position(other.n_));
1245  }
1246  friend bool operator<(const_iterator it, iterator other) {
1247  from_same_list(it.pbase_, other.pbase_);
1248  return it.pbase_->position(it.n_) <
1249  other.pbase_->position(other.n_);
1250  }
1251  friend bool operator<(iterator it, const_iterator other) {
1252  from_same_list(it.pbase_, other.pbase_);
1253  return it.pbase_->position(it.n_) <
1254  other.pbase_->position(other.n_);
1255  }
1256  friend bool operator<=(const_iterator it, iterator other) {
1257  from_same_list(it.pbase_, other.pbase_);
1258  return it.pbase_->position(it.n_) <=
1259  other.pbase_->position(other.n_);
1260  }
1261  friend bool operator<=(iterator it, const_iterator other) {
1262  from_same_list(it.pbase_, other.pbase_);
1263  return it.pbase_->position(it.n_) <=
1264  other.pbase_->position(other.n_);
1265  }
1266  friend bool operator>(const_iterator it, iterator other) {
1267  from_same_list(it.pbase_, other.pbase_);
1268  return it.pbase_->position(it.n_) >
1269  other.pbase_->position(other.n_);
1270  }
1271  friend bool operator>(iterator it, const_iterator other) {
1272  from_same_list(it.pbase_, other.pbase_);
1273  return it.pbase_->position(it.n_) >
1274  other.pbase_->position(other.n_);
1275  }
1276  friend bool operator>=(const_iterator it, iterator other) {
1277  from_same_list(it.pbase_, other.pbase_);
1278  return it.pbase_->position(it.n_) >=
1279  other.pbase_->position(other.n_);
1280  }
1281  friend bool operator>=(iterator it, const_iterator other) {
1282  from_same_list(it.pbase_, other.pbase_);
1283  return it.pbase_->position(it.n_) >=
1284  other.pbase_->position(other.n_);
1285  }
1286  friend bool operator==(const_iterator it, iterator other) {
1287  return it.n_ == other.n_;
1288  }
1289  friend bool operator==(iterator it, const_iterator other) {
1290  return it.n_ == other.n_;
1291  }
1292  friend bool operator!=(const_iterator it, iterator other) {
1293  return it.n_ != other.n_;
1294  }
1295  friend bool operator!=(iterator it, const_iterator other) {
1296  return it.n_ != other.n_;
1297  }
1298  };
1299 
1300 private:
1301  Base base_;
1302 
1303 public:
1304  LTOList() : base_() {}
1305  LTOList(LTOList && other) : base_() {
1306  other.swap(*this);
1307  other.clear();
1308  }
1309  LTOList(const LTOList & other) : base_() {
1310  base_.copy_from(other.base_);
1311  }
1312  LTOList(std::initializer_list<T> init) : base_() {
1313  this->insert(this->begin(), init.begin(), init.end());
1314  }
1315 
1316  iterator begin() {
1317  return iterator(base_, base_.origin->o_front());
1318  }
1319  iterator end() {
1320  return iterator(
1321  base_, base_.origin->o_front() ? base_.origin : nullptr);
1322  }
1323  iterator rbegin() {
1324  return iterator(base_, base_.origin->o_front());
1325  }
1326  iterator rend() {
1327  return iterator(
1328  base_, base_.origin->o_front() ? base_.origin : nullptr);
1329  }
1330  const_iterator begin() const {
1331  return const_iterator(base_, base_.origin->o_front());
1332  }
1333  const_iterator end() const {
1334  return const_iterator(
1335  base_, base_.origin->o_front() ? base_.origin : nullptr);
1336  }
1337  const_iterator rbegin() const {
1338  return const_iterator(base_, base_.origin->o_front());
1339  }
1340  const_iterator rend() const {
1341  return const_iterator(
1342  base_, base_.origin->o_front() ? base_.origin : nullptr);
1343  }
1344  const_iterator cbegin() const {
1345  return const_iterator(base_, base_.origin->o_front());
1346  }
1347  const_iterator cend() const {
1348  return const_iterator(
1349  base_, base_.origin->o_front() ? base_.origin : nullptr);
1350  }
1351  const_iterator crbegin() const {
1352  return const_iterator(base_, base_.origin->o_front());
1353  }
1354  const_iterator crend() const {
1355  return const_iterator(
1356  base_, base_.origin->o_front() ? base_.origin : nullptr);
1357  }
1358 
1359  size_type size() const { return base_.size(); }
1360  bool empty() const { return base_.empty(); }
1361 
1362  reference at(size_type i) {
1363  if(i >= size())
1364  throw std::out_of_range(
1365  "reference LTOList::operator[]: Index out of range");
1366 
1367  difference_type adpos =
1368  static_cast<difference_type>(i) -
1369  static_cast<difference_type>(
1370  base_.origin->o_root()->n_children[0]);
1371  return base_.advance(base_.origin->o_root(), adpos)->value;
1372  }
1373 
1374  const_reference at(size_type i) const {
1375  if(empty())
1376  throw std::out_of_range(
1377  "const_reference LTOList::at: Index out of range");
1378 
1379  difference_type adpos =
1380  static_cast<difference_type>(i) -
1381  static_cast<difference_type>(
1382  base_.origin->o_root()->n_children[0]);
1383  return base_.advance(base_.origin->o_root(), adpos)->value;
1384  }
1385 
1386  inline reference operator[](size_type i) { return this->at(i); }
1387  inline const_reference operator[](size_type i) const {
1388  return this->at(i);
1389  }
1390 
1391  reference front() { return base_.origin->o_front()->value; }
1392  const_reference front() const {
1393  return base_.origin->o_front()->value;
1394  }
1395  reference back() { return base_.origin->o_back()->value; }
1396  const_reference back() const {
1397  return base_.origin->o_back()->value;
1398  }
1399 
1425  iterator
1426  insert(size_type side, iterator position, const_reference val) {
1427  return iterator(base_, base_.add(position.n_, side, val));
1428  }
1429 
1456  iterator insert(size_type side, iterator position, T && val) {
1457  return iterator(
1458  base_, base_.add(position.n_, side, std::move(val)));
1459  }
1460 
1483  template<class... Args>
1484  iterator
1485  emplace(size_type side, iterator position, Args... args) {
1486  return iterator(
1487  base_, base_.add_emplace(position.n_, side, args...));
1488  }
1489 
1498  iterator insert(iterator position, const_reference val) {
1499  return insert(0, position, val);
1500  }
1501 
1510  iterator insert(iterator position, T && val) {
1511  return insert(0, position, std::move(val));
1512  }
1513 
1522  template<class... Args>
1523  iterator emplace(iterator position, Args... args) {
1524  return emplace(0, position, args...);
1525  }
1526 
1555  void insert(
1556  size_type side, iterator position, size_type n,
1557  const_reference val) {
1558  for(size_type i = 0; i < n; ++i) insert(side, position, val);
1559  }
1560 
1591  template<class... Args>
1592  void emplace(
1593  size_type side, iterator position, size_type n, Args... args) {
1594  for(size_type i = 0; i < n; ++i)
1595  emplace(side, position, args...);
1596  }
1597 
1606  void insert(iterator position, size_type n, const_reference val) {
1607  for(size_type i = 0; i < n; ++i) insert(0, position, val);
1608  }
1609 
1618  template<class... Args>
1619  void emplace(iterator position, size_type n, Args... args) {
1620  for(size_type i = 0; i < n; ++i)
1621  emplace(0, position, args...);
1622  }
1623 
1657  template<class InputIterator>
1658  void insert(
1659  size_type side, iterator position, InputIterator elem_begin,
1660  InputIterator elem_end) {
1661  iterator tmp = position;
1662  for(InputIterator it = elem_begin; it != elem_end; ++it) {
1663  tmp = insert(side, tmp, *it);
1664  side = 1; // insertion side should be considered only for
1665  // the first insertion
1666  }
1667  }
1668 
1678  template<class InputIterator>
1679  void insert(
1680  iterator position, InputIterator elem_begin,
1681  InputIterator elem_end) {
1682  insert(0, position, elem_begin, elem_end);
1683  }
1684 
1685  iterator erase(iterator position) {
1686  return iterator(base_, base_.remove(position.n_));
1687  }
1688  iterator erase(const_iterator position) {
1689  return iterator(base_, base_.remove(position.n_));
1690  }
1691 
1692  iterator erase(iterator elem_begin, iterator elem_end) {
1693  // Should we check elem_begin < elem_end beforehand?
1694  while(elem_begin != elem_end) {
1695  elem_begin = erase(elem_begin);
1696  }
1697  return elem_begin;
1698  }
1699  iterator
1700  erase(const_iterator elem_begin, const_iterator elem_end) {
1701  while(elem_begin != elem_end) elem_begin = erase(elem_begin);
1702  return elem_begin;
1703  }
1704 
1705  template<class InputIterator>
1706  void assign(InputIterator elem_begin, InputIterator elem_end) {
1707  clear();
1708  insert(begin(), elem_begin, elem_end);
1709  }
1710 
1711  void assign(size_type n, const T & val) {
1712  clear();
1713  insert(begin(), n, val);
1714  }
1715 
1716  void push_front(const T & val) { insert(begin(), val); }
1717  void push_front(T && val) { insert(begin(), std::move(val)); }
1718  template<class... Args>
1719  void emplace_front(Args... args) {
1720  emplace(begin(), args...);
1721  }
1722 
1723  void push_back(const T & val) { insert(end(), val); }
1724  void push_back(T && val) { insert(end(), std::move(val)); }
1725  template<class... Args>
1726  void emplace_back(Args... args) {
1727  emplace(end(), args...);
1728  }
1729 
1730  void pop_front() { erase(begin()); }
1731  void pop_back() { erase(--(end())); }
1732 
1733  void clear() { base_.clear(); }
1734 
1735  void swap(LTOList<T> & other) {
1736  std::swap(base_.origin, other.base_.origin);
1737  }
1738 };
1739 
1740 template<class T>
1741 std::ostream & operator<<(
1742  std::ostream & os, const typename LTOList<T>::iterator & it) {
1743  os << "LTOList::iterator<" << it.n_ << ">";
1744  return os;
1745 }
1746 
1747 template<class T>
1748 std::ostream & operator<<(
1749  std::ostream & os, const typename LTOList<T>::const_iterator & it) {
1750  os << "LTOList::const_iterator<" << it.n_ << ">";
1751  return os;
1752 }
LTOList::insert
void insert(iterator position, InputIterator elem_begin, InputIterator elem_end)
Definition: LTOList.hpp:1679
LTOList::insert
iterator insert(size_type side, iterator position, T &&val)
Definition: LTOList.hpp:1456
LTOList::emplace
void emplace(iterator position, size_type n, Args... args)
Definition: LTOList.hpp:1619
LTOList::insert
iterator insert(iterator position, const_reference val)
Definition: LTOList.hpp:1498
LTOList::insert
iterator insert(iterator position, T &&val)
Definition: LTOList.hpp:1510
LTOList
Definition: LTOList.hpp:18
LTOList::emplace
iterator emplace(size_type side, iterator position, Args... args)
Definition: LTOList.hpp:1485
LTOList::pointer
T * pointer
Definition: LTOList.hpp:64
LTOList::emplace
void emplace(size_type side, iterator position, size_type n, Args... args)
Definition: LTOList.hpp:1592
LTOList::const_reference
const T & const_reference
Definition: LTOList.hpp:57
LTOList::const_iterator
Definition: LTOList.hpp:1099
LTOList::value_type
T value_type
Definition: LTOList.hpp:25
LTOList::const_pointer
const T * const_pointer
Definition: LTOList.hpp:72
LTOList::size_type
size_t size_type
Definition: LTOList.hpp:33
LTOList::reference
T & reference
Definition: LTOList.hpp:49
LTOList::difference_type
ptrdiff_t difference_type
Definition: LTOList.hpp:41
LTOList::iterator
Definition: LTOList.hpp:971
LTOList::insert
void insert(size_type side, iterator position, InputIterator elem_begin, InputIterator elem_end)
Definition: LTOList.hpp:1658
LTOList::insert
iterator insert(size_type side, iterator position, const_reference val)
Definition: LTOList.hpp:1426
LTOList::insert
void insert(iterator position, size_type n, const_reference val)
Definition: LTOList.hpp:1606
LTOList::insert
void insert(size_type side, iterator position, size_type n, const_reference val)
Definition: LTOList.hpp:1555
LTOList::emplace
iterator emplace(iterator position, Args... args)
Definition: LTOList.hpp:1523
Generated by   doxygen 1.8.16