stlab.adobe.com Adobe Systems Incorporated
forest.hpp
Go to the documentation of this file.
1 /*
2  Copyright 2005-2007 Adobe Systems Incorporated
3  Distributed under the MIT License (see accompanying file LICENSE_1_0_0.txt
4  or a copy at http://stlab.adobe.com/licenses.html)
5 */
6 
7 /*************************************************************************************************/
8 
9 #ifndef ADOBE_FOREST_HPP
10 #define ADOBE_FOREST_HPP
11 
12 /*************************************************************************************************/
13 
14 #include <adobe/config.hpp>
15 
18 
19 #include <boost/iterator/iterator_facade.hpp>
20 #include <boost/next_prior.hpp>
21 #include <boost/range.hpp>
22 
23 #include <cstddef>
24 #include <iterator>
25 #include <functional>
26 
27 /*************************************************************************************************/
28 
29 namespace adobe {
30 
31 /*************************************************************************************************/
32 
33 /*
34  NOTE (sparent) : These are the edge index value - trailing as 0 and leading as 1 is done to
35  reflect that it used to be a leading bool value. Changing the order of this enum requires
36  code review as some code relies on the test for leading.
37 */
38 
39 enum
40 {
43 };
44 
45 /*************************************************************************************************/
46 
47 template <typename I> // I models FullorderIterator
48 inline void pivot(I& i) { i.edge() ^= 1; }
49 
50 template <typename I> // I models FullorderIterator
51 inline I pivot_of(I i) { pivot(i); return i; }
52 
53 /*************************************************************************************************/
54 
55 template <typename I> // I models a FullorderIterator
56 inline I leading_of(I i) { i.edge() = forest_leading_edge; return i; }
57 
58 template <typename I> // I models a FullorderIterator
59 inline I trailing_of(I i) { i.edge() = forest_trailing_edge; return i; }
60 
61 /*************************************************************************************************/
62 
63 template <typename I> // I models FullorderIterator
65 {
66  do { i = trailing_of(i); ++i; } while (i.edge() != forest_trailing_edge);
67  return i;
68 }
69 
70 /*************************************************************************************************/
71 
72 template <typename I> // I models FullorderIterator
73 bool has_children(const I& i)
74 { return !i.equal_node(boost::next(leading_of(i))); }
75 
76 /*************************************************************************************************/
77 
78 template <typename I> // I models FullorderIterator
79 class child_iterator : public boost::iterator_adaptor<child_iterator<I>, I>
80 {
81  public:
83  explicit child_iterator(I x) : child_iterator::iterator_adaptor_(x) { }
84  template <typename U> child_iterator(const child_iterator<U>& u) :
85  child_iterator::iterator_adaptor_(u.base()) { }
86 
87  private:
89 
90  void increment() { pivot(this->base_reference()); ++this->base_reference(); }
91  void decrement() { --this->base_reference(); pivot(this->base_reference()); }
92 };
93 
94 /*************************************************************************************************/
95 
96 template <typename I> // I models FullorderIterator
97 I find_edge(I x, std::size_t edge) { while (x.edge() != edge) ++x; return x; }
98 
99 template <typename I> // I models FullorderIterator
100 I find_edge_reverse(I x, std::size_t edge) { while (x.edge() != edge) --x; return x; }
101 
102 /*************************************************************************************************/
103 
104 template <typename I, std::size_t Edge> // I models FullorderIterator
105 class edge_iterator : public boost::iterator_adaptor<edge_iterator<I, Edge>, I>
106 {
107  public:
109  explicit edge_iterator(I x) : edge_iterator::iterator_adaptor_(find_edge(x, Edge))
110  { }
111  template <typename U> edge_iterator(const edge_iterator<U, Edge>& u) :
112  edge_iterator::iterator_adaptor_(u.base()) { }
113 
114  private:
116 
117  void increment()
118  { this->base_reference() = find_edge(boost::next(this->base()), Edge); }
119 
120  void decrement()
121  { this->base_reference() = find_edge_reverse(boost::prior(this->base()), Edge); }
122 };
123 
124 /*************************************************************************************************/
125 
126 /*
127  I need to establish dereferencable range vs. traversable range.
128 
129  Here [f, l) must be a dereferencable range and p() will not be applied outside that range
130  although the iterators may travel beyond that range.
131 */
132 
133 template < typename I, // I models a Forest
134  typename P> // P models UnaryPredicate of value_type(I)
136  : public boost::iterator_adaptor<filter_fullorder_iterator<I, P>, I>
137 {
138  public:
140 
141  filter_fullorder_iterator(I f, I l, P p) :
142  filter_fullorder_iterator::iterator_adaptor_(skip_forward(f, l, p)),
143  inside_m(true),
144  first_m(f),
145  last_m(l),
146  predicate_m(p)
147  { }
148 
150  filter_fullorder_iterator::iterator_adaptor_(skip_forward(f, l, P())),
151  inside_m(true),
152  first_m(f),
153  last_m(l)
154  { }
155 
157  filter_fullorder_iterator::iterator_adaptor_(x.base()),
158  inside_m(x.inside_m),
159  first_m(x.first_m),
160  last_m(x.last_m),
161  predicate_m(x.predicate_m)
162  { }
163 
164  P predicate() const { return predicate_m; }
165 
166  std::size_t edge() const { return this->base().edge(); }
167  std::size_t& edge() { return this->base_reference().edge(); }
168 
169  bool equal_node(const filter_fullorder_iterator& y) const { return this->base().equal_node(y.base()); }
170 
171  private:
173 
174  void increment()
175  {
176  I i = this->base();
177 
178  if (i == last_m) inside_m = false;
179  ++i;
180  if (i == first_m) inside_m = true;
181  if (inside_m) i = skip_forward(i, last_m, predicate_m);
182  this->base_reference() = i;
183  }
184 
185  static I skip_forward(I f, I l, P p)
186  // Precondition: l is on a leading edge
187  {
188  while((f.edge() == forest_leading_edge) && (f != l) && !p(*f)) {
189  f.edge() = forest_trailing_edge;
190  ++f;
191  }
192  return f;
193  }
194 
195  static I skip_backward(I f, I l, P p)
196  // Precondition: f is on a trailing edge
197  {
198  while((l.edge() == forest_trailing_edge) && (f != l) && !p(*l)) {
199  l.edge() = forest_leading_edge;
200  --l;
201  }
202  return l;
203  }
204 
205  void decrement()
206  {
207  I i = this->base();
208 
209  if (i == first_m) inside_m = false;
210  --i;
211  if (i == last_m) inside_m = true;
212  if (inside_m) i = skip_backward(first_m, i, predicate_m);
213  this->base_reference() = i;
214  }
215 
216  bool inside_m;
217  I first_m;
218  I last_m;
219  P predicate_m;
220 };
221 
222 /*************************************************************************************************/
223 
224 /*
225  REVISIT (sparent) : This is an interesting case - an edge is a property of an iterator but it
226  is determined by examining a vertex in the graph. Here we need to examine the prior vertex
227  to determine the edge. If the range is empty (or we are at the "end" of the range) then this
228  examination is questionable.
229 
230  We let it go, because we know the forest structure is an infinite loop through the root. One
231  answer to this would be to construct a reverse iterator which was not "off by one" for forest -
232  but that might break people who assume base() is off by one for a reverse iterator, and it still
233  assumes a root().
234 */
235 
236 template <typename I> // I models a FullorderIterator
237 class reverse_fullorder_iterator : public boost::iterator_facade<reverse_fullorder_iterator<I>,
238  typename boost::iterator_value<I>::type, std::bidirectional_iterator_tag,
239  typename boost::iterator_reference<I>::type>
240 {
241  typedef typename boost::iterator_facade<reverse_fullorder_iterator<I>,
242  typename boost::iterator_value<I>::type, std::bidirectional_iterator_tag,
243  typename boost::iterator_reference<I>::type>
244  inherited_t;
245  public:
246  typedef I iterator_type;
247  typedef typename inherited_t::reference reference;
248 
250  reverse_fullorder_iterator(I x) : base_m(--x), edge_m(forest_leading_edge - base_m.edge())
251  { }
253  base_m(x.base()), edge_m(x.edge_m)
254  { }
255 
256  iterator_type base() const { return boost::next(base_m); }
257 
258  std::size_t edge() const { return edge_m; }
259  std::size_t& edge() { return edge_m; }
260 
262  { return base_m.equal_node(y.base_m); }
263 
264  private:
266 
267  void increment()
268  {
269  base_m.edge() = forest_leading_edge - edge_m;
270  --base_m;
271  edge_m = forest_leading_edge - base_m.edge();
272  }
273  void decrement()
274  {
275  base_m.edge() = forest_leading_edge - edge_m;
276  ++base_m;
277  edge_m = forest_leading_edge - base_m.edge();
278  }
279  reference dereference() const { return *base_m; }
280 
281  bool equal(const reverse_fullorder_iterator& y) const
282  { return (base_m == y.base_m) && (edge_m == y.edge_m); }
283 
284  I base_m;
285  std::size_t edge_m;
286 };
287 
288 /*************************************************************************************************/
289 
290 template <typename I> // I models FullorderIterator
291 class depth_fullorder_iterator : public boost::iterator_adaptor<depth_fullorder_iterator<I>, I>
292 {
293  public:
294  typedef typename boost::iterator_adaptor<depth_fullorder_iterator<I>, I>::difference_type difference_type;
295 
298  depth_fullorder_iterator::iterator_adaptor_(x),
299  depth_m(d)
300  { }
301  template <typename U> depth_fullorder_iterator(const depth_fullorder_iterator<U>& x) :
302  depth_fullorder_iterator::iterator_adaptor_(x.base()),
303  depth_m(x.depth_m)
304  { }
305 
306  difference_type depth() const { return depth_m; }
307  std::size_t edge() const { return this->base().edge(); }
308  std::size_t& edge() { return this->base_reference().edge(); }
309  bool equal_node(depth_fullorder_iterator const& y) const { return this->base().equal_node(y.base()); }
310 
311  private:
313 
314  void increment()
315  {
316  std::size_t old_edge(edge());
317  ++this->base_reference();
318  if (old_edge == edge()) depth_m += difference_type(old_edge << 1) - 1;
319  }
320  void decrement()
321  {
322  bool old_edge(edge());
323  --this->base_reference();
324  if (old_edge == edge()) depth_m -= difference_type(old_edge << 1) - 1;
325  }
326 
327  difference_type depth_m;
328 };
329 
330 /*************************************************************************************************/
331 
332 template <typename Forest> class child_adaptor;
333 template <typename T> class forest;
334 template <typename T> void swap(forest<T>&, forest<T>&);
335 
336 /*************************************************************************************************/
337 
338 #if !defined(ADOBE_NO_DOCUMENTATION)
339 namespace implementation {
340 
341 template <typename D> // derived class
342 struct node_base
343 {
344  enum next_prior_t
345  {
346  prior_s,
347  next_s
348  };
349 
350  typedef D* node_ptr;
351  typedef node_ptr& reference;
352 
353  node_base()
354  {
355  // leading is 1, trailing is 0
356  nodes_m[forest_leading_edge][std::size_t(next_s)] = static_cast<node_ptr>(this);
357  nodes_m[forest_trailing_edge][std::size_t(prior_s)] = static_cast<node_ptr>(this);
358  }
359 
360  node_ptr& link(std::size_t edge, next_prior_t link)
361  { return nodes_m[edge][std::size_t(link)]; }
362 
363  node_ptr link(std::size_t edge, next_prior_t link) const
364  { return nodes_m[edge][std::size_t(link)]; }
365 
366  node_ptr nodes_m[2][2];
367 };
368 
369 template <typename T> // T models Regular
370 struct node : public node_base<node<T> >
371 {
372  typedef T value_type;
373 
374  explicit node(const value_type& data) : data_m(data) { }
375 
376  value_type data_m;
377 };
378 
379 /*************************************************************************************************/
380 
381 template <typename T> class forest_const_iterator;
382 
383 template <typename T> // T is value_type
384 class forest_iterator : public boost::iterator_facade<forest_iterator<T>,
385  T,
386  std::bidirectional_iterator_tag>
387 {
388  typedef boost::iterator_facade<forest_iterator<T>,
389  T,
390  std::bidirectional_iterator_tag> inherited_t;
391 public:
392  typedef typename inherited_t::reference reference;
393  typedef typename inherited_t::difference_type difference_type;
394  typedef typename inherited_t::value_type value_type;
395 
396  forest_iterator() :
397  node_m(0), edge_m(forest_leading_edge) { }
398 
399  forest_iterator(const forest_iterator& x) :
400  node_m(x.node_m), edge_m(x.edge_m) { }
401 
402  std::size_t edge() const { return edge_m; }
403  std::size_t& edge() { return edge_m; }
404  bool equal_node(forest_iterator const& y) const { return node_m == y.node_m; }
405 
406 private:
407  friend class adobe::forest<value_type>;
408  friend class boost::iterator_core_access;
409  template <typename> friend class forest_iterator;
410  template <typename> friend class forest_const_iterator;
411  friend struct unsafe::set_next_fn<forest_iterator>;
412 
413  typedef node<T> node_t;
414 
415  reference dereference() const { return node_m->data_m; }
416 
417  void increment()
418  {
419  node_t* next(node_m->link(edge_m, node_t::next_s));
420 
421  if (edge_m) edge_m = std::size_t(next != node_m);
422  else edge_m = std::size_t(next->link(forest_leading_edge, node_t::prior_s) == node_m);
423 
424  node_m = next;
425  }
426 
427  void decrement()
428  {
429  node_t* next(node_m->link(edge_m, node_t::prior_s));
430 
431  if (edge_m) edge_m = std::size_t(next->link(forest_trailing_edge, node_t::next_s) != node_m);
432  else edge_m = std::size_t(next == node_m);
433 
434  node_m = next;
435  }
436 
437  bool equal(const forest_iterator& y) const
438  { return (node_m == y.node_m) && (edge_m == y.edge_m); }
439 
440  node_t* node_m;
441  std::size_t edge_m;
442 
443  forest_iterator(node_t* node, std::size_t edge) :
444  node_m(node), edge_m(edge) { }
445 };
446 
447 
448 /*************************************************************************************************/
449 
450 template <typename T> // T is value_type
451 class forest_const_iterator : public boost::iterator_facade<forest_const_iterator<T>,
452  const T,
453  std::bidirectional_iterator_tag>
454 {
455  typedef boost::iterator_facade<forest_const_iterator<T>,
456  const T,
457  std::bidirectional_iterator_tag> inherited_t;
458 public:
459  typedef typename inherited_t::reference reference;
460  typedef typename inherited_t::difference_type difference_type;
461  typedef typename inherited_t::value_type value_type;
462 
463  forest_const_iterator() :
464  node_m(0), edge_m(forest_leading_edge) { }
465 
466  forest_const_iterator(const forest_const_iterator& x) :
467  node_m(x.node_m), edge_m(x.edge_m) { }
468 
469  forest_const_iterator(const forest_iterator<T>& x) :
470  node_m(x.node_m), edge_m(x.edge_m) { }
471 
472  std::size_t edge() const { return edge_m; }
473  std::size_t& edge() { return edge_m; }
474  bool equal_node(forest_const_iterator const& y) const { return node_m == y.node_m; }
475 
476 private:
477  friend class adobe::forest<value_type>;
478  friend class boost::iterator_core_access;
479  template <typename> friend class forest_const_iterator;
480  friend struct unsafe::set_next_fn<forest_const_iterator>;
481 
482  typedef const node<T> node_t;
483 
484  reference dereference() const { return node_m->data_m; }
485 
486  void increment()
487  {
488  node_t* next(node_m->link(edge_m, node_t::next_s));
489 
490  if (edge_m) edge_m = std::size_t(next != node_m);
491  else edge_m = std::size_t(next->link(forest_leading_edge, node_t::prior_s) == node_m);
492 
493  node_m = next;
494  }
495 
496  void decrement()
497  {
498  node_t* next(node_m->link(edge_m, node_t::prior_s));
499 
500  if (edge_m) edge_m = std::size_t(next->link(forest_trailing_edge, node_t::next_s) != node_m);
501  else edge_m = std::size_t(next == node_m);
502 
503  node_m = next;
504  }
505 
506  bool equal(const forest_const_iterator& y) const
507  { return (node_m == y.node_m) && (edge_m == y.edge_m); }
508 
509  node_t* node_m;
510  std::size_t edge_m;
511 
512  forest_const_iterator(node_t* node, std::size_t edge) :
513  node_m(node), edge_m(edge) { }
514 };
515 
516 
517 /*************************************************************************************************/
518 
519 } // namespace implementation
520 #endif
521 
522 /*************************************************************************************************/
523 
524 namespace unsafe {
525 
526 template <typename T> // T is node<T>
527 struct set_next_fn<implementation::forest_iterator<T> >
528 {
529  void operator()(implementation::forest_iterator<T> x, implementation::forest_iterator<T> y) const
530  {
531  typedef typename implementation::node<T> node_t;
532 
533  x.node_m->link(x.edge(), node_t::next_s) = y.node_m;
534  y.node_m->link(y.edge(), node_t::prior_s) = x.node_m;
535  }
536 };
537 
538 } // namespace unsafe
539 
540 /*************************************************************************************************/
541 
542 template <typename T>
543 class forest
544 {
545 private:
546  typedef implementation::node<T> node_t;
547  friend class child_adaptor<forest<T> >;
548 public:
549  // types
550  typedef T& reference;
551  typedef const T& const_reference;
552  typedef implementation::forest_iterator<T> iterator;
553  typedef implementation::forest_const_iterator<T> const_iterator;
554  typedef std::size_t size_type;
555  typedef std::ptrdiff_t difference_type;
556  typedef T value_type;
557  typedef T* pointer;
558  typedef const T* const_pointer;
561 
563 /* qualification needed since: A name N used in a class S shall refer to the same declaration
564  in its context and when re-evaluated in the completed scope of
565  S. */
566 
568  typedef std::reverse_iterator<child_iterator> reverse_child_iterator;
569 
574 
575 #if !defined(ADOBE_NO_DOCUMENTATION)
576  forest();
577  ~forest() { clear(); }
578 
579  forest(const forest&);
580  forest& operator=(forest x) { this->swap(x); return *this; }
581 
582  void swap(forest&);
583 #endif
584 
585  size_type size() const;
586  size_type size();
587  size_type max_size() const { return size_type(-1); }
588  bool size_valid() const { return size_m != 0 || empty(); }
589  bool empty() const { return begin() == end(); } // Don't test size which may be expensive
590 
591  // iterators
592  iterator root() { return iterator(tail(), forest_leading_edge); }
593 
594  iterator begin() { return ++root(); }
595  iterator end() { return iterator(tail(), forest_trailing_edge); }
598 
603 
604  reference front() { assert(!empty()); return *begin(); }
605  const_reference front() const { assert(!empty()); return *begin(); }
606  reference back() { assert(!empty()); return *(--end()); }
607  const_reference back() const { assert(!empty()); return *(--end()); }
608 
609  // modifiers
610  void clear()
611  {
612  erase(begin(), end());
613  assert(empty()); // Make sure our erase is correct
614  }
615 
616  iterator erase(const iterator& position);
617  iterator erase(const iterator& first, const iterator& last);
618 
619  iterator insert(const iterator& position, const T& x)
620  {
621  iterator result(new node_t(x), true);
622 
623  if (size_valid()) ++size_m;
624 
625  unsafe::set_next(boost::prior(position), result);
626  unsafe::set_next(boost::next(result), position);
627 
628  return result;
629  }
630 
631  void push_front(const T& x) { insert(begin(), x); }
632  void push_back(const T& x) { insert(end(), x); }
633  void pop_front() { assert(!empty()); erase(begin()); }
634  void pop_back() { assert(!empty()); erase(--end()); }
635 
637 
638  iterator splice(iterator position, forest<T>& x);
639  iterator splice(iterator position, forest<T>& x, iterator i);
640  iterator splice(iterator position, forest<T>& x, child_iterator first, child_iterator last);
642 
644  void reverse(child_iterator first, child_iterator last);
645 
646 private:
647 #if !defined(ADOBE_NO_DOCUMENTATION)
648 
649  friend class implementation::forest_iterator<value_type>;
650  friend class implementation::forest_const_iterator<value_type>;
651  friend struct unsafe::set_next_fn<iterator>;
652 
653 
654 #if 0
655  struct node_base
656  {
657  enum next_prior_t
658  {
659  prior_s,
660  next_s
661  };
662 
663  typedef node* node_ptr;
664  typedef node_ptr& reference;
665 
666  node_base()
667  {
668  // leading is 1, trailing is 0
669  nodes_m[forest_leading_edge][std::size_t(next_s)] = static_cast<node*>(this);
670  nodes_m[forest_trailing_edge][std::size_t(prior_s)] = static_cast<node*>(this);
671  }
672 
673  node_ptr& link(std::size_t edge, next_prior_t link)
674  { return nodes_m[edge][std::size_t(link)]; }
675 
676  node_ptr link(std::size_t edge, next_prior_t link) const
677  { return nodes_m[edge][std::size_t(link)]; }
678 
679  node_ptr nodes_m[2][2];
680  };
681 
682  struct node : public node_base
683  {
684  explicit node(const value_type& data) : data_m(data) { }
685 
686  value_type data_m;
687  };
688 
689 #endif
690 
691  size_type size_m;
692  implementation::node_base<node_t> tail_m;
693 
694  node_t* tail() { return static_cast<node_t*>(&tail_m); }
695  const node_t* tail() const { return static_cast<const node_t*>(&tail_m); }
696 #endif
697 };
698 
699 /*************************************************************************************************/
700 
701 template <typename T>
702 bool operator==(const forest<T>& x, const forest<T>& y)
703 {
704  if (x.size() != y.size()) return false;
705 
706  for (typename forest<T>::const_iterator first(x.begin()), last(x.end()), pos(y.begin());
707  first != last; ++first, ++pos)
708  {
709  if (first.edge() != pos.edge()) return false;
710  if (first.edge() && (*first != *pos)) return false;
711  }
712 
713  return true;
714 }
715 
716 /*************************************************************************************************/
717 
718 template <typename T>
719 bool operator!=(const forest<T>& x, const forest<T>& y)
720 { return !(x == y); }
721 
722 /*************************************************************************************************/
723 
724 namespace unsafe {
725 
726 template <typename I> // I models a FullorderIterator
728 {
729  void operator()(child_iterator<I> x, child_iterator<I> y)
730  {
731  unsafe::set_next(pivot_of(x.base()), y.base());
732  }
733 };
734 
735 } // namespace unsafe
736 
737 /*************************************************************************************************/
738 
739 #if !defined(ADOBE_NO_DOCUMENTATION)
740 
741 template <typename T>
742 forest<T>::forest() :
743  size_m(0)
744 {
745  unsafe::set_next(end(), root());
746 }
747 
748 /*************************************************************************************************/
749 
750 template <typename T>
751 forest<T>::forest(const forest& x) :
752  size_m(0)
753 {
754  unsafe::set_next(end(), root());
755 
756  insert(begin(), const_child_iterator(x.begin()), const_child_iterator(x.end()));
757 }
758 
759 /*************************************************************************************************/
760 
761 template <typename T>
762 void forest<T>::swap(forest& tree)
763 {
764  size_type old_size(size_valid() ? 0 : size());
765  iterator last(splice(end(), tree));
766  tree.splice(tree.end(), *this, child_iterator(begin()), child_iterator(last), old_size);
767 }
768 
769 #endif
770 
771 /*************************************************************************************************/
772 
773 template <typename T>
775 {
776  if (!size_valid())
777  {
778  const_preorder_iterator first(begin());
779  const_preorder_iterator last(end());
780 
781  size_m = size_type(std::distance(first, last));
782  }
783 
784  return size_m;
785 }
786 
787 /*************************************************************************************************/
788 
789 template <typename T>
791 {
792  if (size_valid()) return size_m;
793 
794  const_preorder_iterator first(begin());
795  const_preorder_iterator last(end());
796 
797  return size_type(std::distance(first, last));
798 }
799 
800 /*************************************************************************************************/
801 
802 template <typename T>
803 typename forest<T>::iterator forest<T>::erase(const iterator& first, const iterator& last)
804 {
805  difference_type stack_depth(0);
806  iterator position(first);
807 
808  while (position != last)
809  {
810  if (position.edge() == forest_leading_edge)
811  {
812  ++stack_depth;
813  ++position;
814  }
815  else
816  {
817  if (stack_depth > 0) position = erase(position);
818  else ++position;
819  stack_depth = std::max<difference_type>(0, stack_depth - 1);
820  }
821  }
822  return last;
823 }
824 
825 /*************************************************************************************************/
826 
827 template <typename T>
829 { x.swap(y); }
830 
831 /*************************************************************************************************/
832 
833 template <typename T>
835 {
836  /*
837  NOTE (sparent) : After the first call to set_next() the invariants of the forest are
838  violated and we can't determing leading/trailing if we navigate from the effected node.
839  So we gather all the iterators up front then do the set_next calls.
840  */
841 
842  if (size_valid()) --size_m;
843 
844  iterator leading_prior(boost::prior(leading_of(position)));
845  iterator leading_next(boost::next(leading_of(position)));
846  iterator trailing_prior(boost::prior(trailing_of(position)));
847  iterator trailing_next(boost::next(trailing_of(position)));
848 
849  if (has_children(position))
850  {
851  unsafe::set_next(leading_prior, leading_next);
852  unsafe::set_next(trailing_prior, trailing_next);
853  }
854  else
855  {
856  unsafe::set_next(leading_prior, trailing_next);
857  }
858 
859  delete position.node_m;
860 
861  return position.edge() ? boost::next(leading_prior) : trailing_next;
862 }
863 
864 /*************************************************************************************************/
865 
866 template <typename T>
868 {
869  return splice(position, x, child_iterator(x.begin()), child_iterator(x.end()),
870  x.size_valid() ? x.size() : 0);
871 }
872 
873 /*************************************************************************************************/
874 
875 template <typename T>
877 {
878  i.edge() = forest_leading_edge;
879  return splice(position, x, child_iterator(i), ++child_iterator(i), has_children(i) ? 0 : 1);
880 }
881 
882 /*************************************************************************************************/
883 
884 template <typename T>
887 {
888  for (const_iterator first(f.base()), last(l.base()); first != last; ++first, ++pos)
889  {
890  if (first.edge()) pos = insert(pos, *first);
891  }
892 
893  return pos;
894 }
895 
896 /*************************************************************************************************/
897 
898 template <typename T>
901 {
902  if (first == last || first.base() == pos) return pos;
903 
904  if (&x != this)
905  {
906  if (count)
907  {
908  if (size_valid()) size_m += count;
909  if (x.size_valid()) x.size_m -= count;
910  }
911  else
912  {
913  size_m = 0;
914  x.size_m = 0;
915  }
916  }
917 
918  iterator back(boost::prior(last.base()));
919 
920  unsafe::set_next(boost::prior(first), last);
921 
922  unsafe::set_next(boost::prior(pos), first.base());
923  unsafe::set_next(back, pos);
924 
925  return first.base();
926 }
927 
928 /*************************************************************************************************/
929 
930 template <typename T>
932  child_iterator first, child_iterator last)
933 { return splice(pos, x, first, last, 0); }
934 
935 /*************************************************************************************************/
936 
937 template <typename T>
939  const T& x)
940 {
941  iterator result(insert(last.base(), x));
942  if (first == last) return result;
943  splice(trailing_of(result), *this, first, child_iterator(result));
944  return result;
945 }
946 
947 /*************************************************************************************************/
948 
949 template <typename T>
951 {
952  iterator prior(first.base());
953  --prior;
954  first = unsafe::reverse_nodes(first, last);
955  unsafe::set_next(prior, first.base());
956 }
957 
958 /*************************************************************************************************/
959 
960 template <typename Forest>
961 class child_adaptor
962 {
963 public:
964  typedef Forest forest_type;
965  typedef typename Forest::value_type value_type;
966  typedef typename Forest::iterator iterator_type;
967  typedef typename Forest::reference reference;
968  typedef typename Forest::const_reference const_reference;
969  typedef typename Forest::difference_type difference_type;
970  typedef typename Forest::child_iterator iterator;
971 
973  forest_m(f), iterator_m(i)
974  { }
975 
976  iterator& back() { return *(--child_end(iterator_m)); }
977  iterator& front() { return *(child_begin(iterator_m)); }
978 
979  void push_back(const value_type& x) { forest_m.insert(child_end(iterator_m).base(), x); }
980  void push_front(const value_type& x) { forest_m.insert(child_begin(iterator_m).base(), x); }
981 
982  void pop_back() { forest_m.erase(--child_end(iterator_m).base()); }
983  void pop_front() { forest_m.erase(child_begin(iterator_m).base()); }
984 
985 private:
986  child_adaptor(); // not defined
987 
988  forest_type& forest_m;
989  iterator_type& iterator_m;
990 };
991 
992 /*************************************************************************************************/
993 
994 template <typename I> // I models FullorderIterator
996 { return child_iterator<I>(boost::next(leading_of(x))); }
997 
998 /*************************************************************************************************/
999 
1000 template <typename I> // I models FullorderIterator
1002 { return child_iterator<I>(trailing_of(x)); }
1003 
1004 /*************************************************************************************************/
1005 
1006 /*
1007  NOTE (fbrereto) : The Doxygen documentation is inline for the functions below because their
1008  signatures are particularly prone to translation error.
1009 */
1010 
1021 template <typename R, typename P> // R models FullorderRange
1022 inline std::pair<filter_fullorder_iterator<typename boost::range_iterator<R>::type, P>,
1023  filter_fullorder_iterator<typename boost::range_iterator<R>::type, P> >
1024 filter_fullorder_range(R& x, P p)
1025 {
1027 
1028  return std::make_pair(iterator(boost::begin(x), boost::end(x), p), iterator(boost::end(x), boost::end(x), p));
1029 }
1030 
1041 template <typename R, typename P> // R models FullorderRange
1042 inline std::pair<filter_fullorder_iterator<typename boost::range_const_iterator<R>::type, P>,
1044 filter_fullorder_range(const R& x, P p)
1045 {
1047 
1048  return std::make_pair(iterator(p, boost::begin(x), boost::end(x)), iterator(p, boost::end(x), boost::end(x)));
1049 }
1050 
1051 /*************************************************************************************************/
1052 
1053 /*
1054  REVISIT (sparent) : There should be some way to generalize this into a make_range - which is
1055  specialized.
1056 
1057  One option -
1058 
1059  reverse_range(R& x)
1060 
1061  Hmmm - maybe reverse_fullorder_iterator should be a specialization of std::reverse_iterator?
1062 */
1063 
1073 template <typename R> // R models FullorderRange
1074 inline std::pair<reverse_fullorder_iterator<typename boost::range_iterator<R>::type>,
1076  reverse_fullorder_range(R& x)
1077 {
1079 
1080  return std::make_pair(iterator(boost::end(x)), iterator(boost::begin(x)));
1081 }
1082 
1092 template <typename R> // R models FullorderRange
1093 inline std::pair<reverse_fullorder_iterator<typename boost::range_const_iterator<R>::type>,
1095  reverse_fullorder_range(const R& x)
1096 {
1098 
1099  return std::make_pair(iterator(boost::end(x)), iterator(boost::begin(x)));
1100 }
1101 
1102 
1103 /*************************************************************************************************/
1104 
1114 template <typename R> // R models FullorderRange
1115 inline std::pair<depth_fullorder_iterator<typename boost::range_iterator<R>::type>,
1117  depth_range(R& x)
1118 {
1120 
1121  return std::make_pair(iterator(boost::begin(x)), iterator(boost::end(x)));
1122 }
1123 
1133 template <typename R> // R models FullorderRange
1134 inline std::pair<depth_fullorder_iterator<typename boost::range_const_iterator<R>::type>,
1136  depth_range(const R& x)
1137 {
1139 
1140  return std::make_pair(iterator(boost::begin(x)), iterator(boost::end(x)));
1141 }
1142 
1143 /*************************************************************************************************/
1144 
1154 template <typename R> // R models FullorderRange
1155 inline std::pair<edge_iterator<typename boost::range_iterator<R>::type, forest_trailing_edge>,
1157  postorder_range(R& x)
1158 {
1160 
1161  return std::make_pair(iterator(boost::begin(x)), iterator(boost::end(x)));
1162 }
1163 
1173 template <typename R> // R models FullorderRange
1174 inline std::pair<edge_iterator<typename boost::range_const_iterator<R>::type, forest_trailing_edge>,
1176  postorder_range(const R& x)
1177 {
1179 
1180  return std::make_pair(iterator(boost::begin(x)), iterator(boost::end(x)));
1181 }
1182 
1183 /*************************************************************************************************/
1184 
1194 template <typename R> // R models FullorderRange
1195 inline std::pair<edge_iterator<typename boost::range_iterator<R>::type, forest_leading_edge>,
1197  preorder_range(R& x)
1198 {
1200 
1201  return std::make_pair(iterator(boost::begin(x)), iterator(boost::end(x)));
1202 }
1203 
1213 template <typename R> // R models FullorderRange
1214 inline std::pair<edge_iterator<typename boost::range_const_iterator<R>::type, forest_leading_edge>,
1216  preorder_range(const R& x)
1217 {
1219 
1220  return std::make_pair(iterator(boost::begin(x)), iterator(boost::end(x)));
1221 }
1222 
1223 /*************************************************************************************************/
1224 
1225 } // namespace adobe
1226 
1227 /*************************************************************************************************/
1228 
1229 #endif
1230 
1231 /*************************************************************************************************/

Copyright © 2006-2007 Adobe Systems Incorporated.

Use of this website signifies your agreement to the Terms of Use and Online Privacy Policy.

Search powered by Google