herwig is hosted by Hepforge, IPPP Durham
Herwig  7.2.1
binary_tree.h
1 // -*- C++ -*-
2 //
3 // binary_tree.h is part of ExSample -- A Library for Sampling Sudakov-Type Distributions
4 //
5 // Copyright (C) 2008-2019 Simon Platzer -- simon.plaetzer@desy.de, The Herwig Collaboration
6 //
7 // ExSample is licenced under version 3 of the GPL, see COPYING for details.
8 // Please respect the MCnet academic guidelines, see GUIDELINES for details.
9 //
10 //
11 #ifndef EXSAMPLE_binary_tree_h_included
12 #define EXSAMPLE_binary_tree_h_included
13 
14 #include "utility.h"
15 
16 namespace exsample {
17 
20  template<class Value>
21  class binary_tree {
22 
23  public:
24 
26 
27 
29  typedef Value value_type;
30 
32 
33  public:
34 
36 
37 
40  : neighbours_(),
41  parent_(), value_(),
42  children_()
43  { }
44 
46  binary_tree(const value_type& thevalue,
47  binary_tree * theparent = 0)
48  : neighbours_(), parent_(theparent),
49  value_(new value_type(thevalue)),
50  children_()
51  { }
52 
57  parent_(x.parent_), value_(),
58  children_() {
59  assert(x.root());
60  binary_tree& nc_x = const_cast<binary_tree&>(x);
61  value_.swap(nc_x.value_);
62  children_.first.swap(nc_x.children_.first);
63  children_.second.swap(nc_x.children_.second);
64  nc_x.parent_ = 0;
65  nc_x.neighbours_.first = 0;
66  nc_x.neighbours_.second = 0;
67  }
68 
72  if (this == &x)
73  return *this;
74  assert(x.root());
75  binary_tree& nc_x = const_cast<binary_tree&>(x);
76  value_.swap(nc_x.value_);
77  children_.first.swap(nc_x.children_.first);
78  children_.second.swap(nc_x.children_.second);
80  parent_ = x.parent_;
81  nc_x.parent_ = 0;
82  nc_x.neighbours_.first = 0;
83  nc_x.neighbours_.second = 0;
84  return *this;
85  }
86 
88 
90 
91 
92  public:
93 
94  class const_iterator;
95 
97  class iterator {
98 
99  public:
100 
102 
103 
105  typedef std::bidirectional_iterator_tag iterator_category;
106 
108  typedef int difference_type;
109 
111  typedef Value value_type;
112 
114  typedef value_type& reference;
115 
117  typedef value_type * pointer;
118 
120 
121  public:
122 
124 
125 
127  iterator() : pointee(0), post_end(0), pre_begin(0) { }
128 
130  iterator(binary_tree * p, std::size_t end = 0)
131  : pointee(p), post_end(end), pre_begin(0) { }
132 
133  //@
134 
135  public:
136 
138 
139 
141  bool operator==(const iterator& x) const {
142  return ((pointee == x.pointee) &&
143  (post_end == x.post_end) &&
144  (pre_begin == x.pre_begin));
145  }
146 
148  bool operator!=(const iterator& x) const { return !(*this == x); }
149 
151 
152  public:
153 
155 
156 
158  reference operator*() { return pointee->value(); }
159 
161  pointer operator->() { return &**this; }
162 
164  binary_tree& node() { return *pointee; }
165 
167 
169  binary_tree * get() const { return pointee; }
170 
172 
173 
176  if (post_end) { ++post_end; return *this; }
177  if (pre_begin) { --pre_begin; return *this; }
178  if(!(pointee->right_neighbour())) { post_end = 1; return *this; }
180  return *this;
181  }
182 
185  if (post_end) { --post_end; return *this; }
186  if (pre_begin) { ++pre_begin; return *this; }
187  if(!(pointee->left_neighbour())) { pre_begin = 1; return *this; }
189  return *this;
190  }
191 
194  iterator tmp = *this;
195  ++(*this);
196  return tmp;
197  }
198 
201  iterator tmp = *this;
202  --(*this);
203  return tmp;
204  }
205 
207 
208  private:
209 
211  friend class const_iterator;
212 
215 
217  std::size_t post_end;
218 
220  std::size_t pre_begin;
221 
222  };
223 
225  iterator begin() { return iterator(left_most()); }
226 
228  iterator end() { return iterator(right_most(),1); }
229 
232  if (!root())
233  return parent().global_begin();
234  return iterator(left_most());
235  }
236 
239  if (!root())
240  return parent().global_end();
241  return iterator(right_most(),1);
242  }
243 
246 
247  public:
248 
250 
251 
253  typedef std::bidirectional_iterator_tag iterator_category;
254 
256  typedef int difference_type;
257 
259  typedef const Value value_type;
260 
262  typedef const value_type& reference;
263 
265  typedef const value_type * pointer;
266 
268 
269  public:
270 
272 
273 
276 
278  const_iterator(const binary_tree * p, std::size_t end = 0)
279  : pointee(p), post_end(end), pre_begin(0) { }
280 
284 
286 
287  public:
288 
290 
291 
293  bool operator==(const const_iterator& x) const {
294  return ((pointee == x.pointee) &&
295  (post_end == x.post_end) &&
296  (pre_begin == x.pre_begin));
297  }
298 
300  bool operator!=(const const_iterator& x) const { return !(*this == x); }
301 
303 
304  public:
305 
307 
308 
310  reference operator*() const { return pointee->value(); }
311 
313  pointer operator->() const { return &**this; }
314 
316  const binary_tree& node() const { return *pointee; }
317 
319 
321 
322 
325  if (post_end) { ++post_end; return *this; }
326  if (pre_begin) { --pre_begin; return *this; }
327  if(!(pointee->right_neighbour())) { post_end = 1; return *this; }
329  return *this;
330  }
331 
334  if (post_end) { --post_end; return *this; }
335  if (pre_begin) { ++pre_begin; return *this; }
336  if(!(pointee->left_neighbour())) { pre_begin = 1; return *this; }
338  return *this;
339  }
340 
343  const_iterator tmp = *this;
344  ++(*this);
345  return tmp;
346  }
347 
350  const_iterator tmp = *this;
351  --(*this);
352  return tmp;
353  }
354 
356 
357  private:
358 
361 
363  std::size_t post_end;
364 
366  std::size_t pre_begin;
367 
368  };
369 
372 
374  const_iterator end() const { return const_iterator(right_most(),1); }
375 
378  if (!root())
379  return parent().global_begin();
380  return iterator(left_most());
381  }
382 
385  if (!root())
386  return parent().global_end();
387  return iterator(right_most(),1);
388  }
389 
390  private:
391 
393  void left_neighbour(binary_tree * n) { neighbours_.first = n; }
394 
396  void right_neighbour(binary_tree * n) { neighbours_.second = n; }
397 
399  binary_tree * left_neighbour() const { return neighbours_.first; }
400 
402  binary_tree * right_neighbour() const { return neighbours_.second; }
403 
406  if(leaf()) return this;
407  return left_child().left_most();
408  }
409 
412  if(leaf()) return this;
413  return right_child().right_most();
414  }
415 
417  const binary_tree * left_most() const {
418  if(leaf()) return this;
419  return left_child().left_most();
420  }
421 
423  const binary_tree * right_most() const {
424  if(leaf()) return this;
425  return right_child().right_most();
426  }
427 
429  std::pair<binary_tree*,binary_tree*> neighbours_;
430 
432 
433  public:
434 
436  bool empty() const { return root() && leaf() && !value_; }
437 
439  void clear() {
440  neighbours_ = std::make_pair<binary_tree*,binary_tree*>(0,0);
441  parent_ = 0;
442  value_.reset(0);
443  if (!leaf()) {
444  left_child().clear();
445  right_child().clear();
446  }
447  children_.first.reset(0);
448  children_.second.reset(0);
449  }
450 
451  public:
452 
454  std::pair<iterator,iterator> split(std::pair<value_type,value_type> children) {
455 
456  assert(leaf());
457 
458  children_.first.reset(new binary_tree(children.first,this));
459  children_.second.reset(new binary_tree(children.second,this));
460 
461  children_.first->left_neighbour(neighbours_.first);
462  children_.first->right_neighbour(children_.second.get());
463  children_.second->left_neighbour(children_.first.get());
464  children_.second->right_neighbour(neighbours_.second);
465 
466  // adjust original neighbours
467 
468  if(neighbours_.first) {
469  neighbours_.first->right_neighbour(children_.first.get());
470  }
471 
472  if (neighbours_.second) {
473  neighbours_.second->left_neighbour(children_.second.get());
474  }
475 
476  neighbours_.first = 0; neighbours_.second = 0;
477 
478  return std::make_pair(iterator(children_.first.get()),iterator(children_.second.get()));
479 
480  }
481 
482  public:
483 
485  template<class Selector>
486  iterator select(const Selector& selector) {
487 
488  if(leaf()) {
489  bool use = selector.use(value());
490  if (use) return iterator(this);
491  return global_end();
492  }
493 
494  std::pair<bool,bool> which(selector.use(value(),left_child().value(),right_child().value()));
495 
496  assert(!which.first || !which.second);
497 
498  if (!which.first && !which.second) {
499  return global_end();
500  }
501 
502  if (which.first) {
503  return left_child().select(selector);
504  }
505  else {
506  return right_child().select(selector);
507  }
508 
509  return global_end();
510 
511  }
512 
515  template<class Selector, unsigned long bits>
516  void subtree_hash(const Selector& selector, bit_container<bits>& bhash) {
517  bhash = bit_container<bits>();
518  unsigned long pos = 0;
519  do_subtree_hash<Selector,bits>(selector,bhash,pos);
520  }
521 
524  template<class Accessor, class BinaryOp>
525  typename BinaryOp::result_type accumulate(const Accessor& acc,
526  BinaryOp binary_op) const {
527 
528  if (!leaf()) {
529  return
530  binary_op(left_child().accumulate(acc,binary_op),
531  right_child().accumulate(acc,binary_op));
532  }
533 
534  return acc.get(value(),true);
535 
536  }
537 
540  template<class Selector, class Accessor, class BinaryOp>
541  typename BinaryOp::result_type accumulate(const Selector& selector,
542  const Accessor& acc,
543  BinaryOp binary_op) const {
544 
545  if (!leaf()) {
546  std::pair<bool,bool> which(selector.use(value(),left_child().value(),right_child().value()));
547  assert(which.first || which.second);
548  if (which.first && which.second) {
549  return
550  binary_op(left_child().accumulate(selector,acc,binary_op),
551  right_child().accumulate(selector,acc,binary_op));
552  } else if (which.first) {
553  return left_child().accumulate(selector,acc,binary_op);
554  } else if (which.second) {
555  return right_child().accumulate(selector,acc,binary_op);
556  }
557  }
558 
559  return acc.get(value(),true);
560 
561  }
562 
566  template<class Accessor, class BinaryOp>
567  typename BinaryOp::result_type tree_accumulate(const Accessor& acc,
568  BinaryOp binary_op) {
569 
570  if (!leaf()) {
571  acc.set(value()) =
572  binary_op(left_child().tree_accumulate(acc,binary_op),
573  right_child().tree_accumulate(acc,binary_op));
574  return acc.get(value(),false);
575  }
576 
577  acc.set(value()) = acc.get(value(),true);
578  return acc.get(value(),true);
579 
580  }
581 
584  template<class Selector, class Accessor, class BinaryOp>
585  typename BinaryOp::result_type tree_accumulate(const Selector& selector,
586  const Accessor& acc,
587  BinaryOp binary_op) {
588 
589  if (!leaf()) {
590  std::pair<bool,bool> which(selector.use(value(),left_child().value(),right_child().value()));
591  assert(which.first || which.second);
592  if (which.first && which.second) {
593  acc.set(value()) =
594  binary_op(left_child().tree_accumulate(selector,acc,binary_op),
595  right_child().tree_accumulate(selector,acc,binary_op));
596  } else if (which.first) {
597  acc.set(value()) = left_child().tree_accumulate(selector,acc,binary_op);
598  } else if (which.second) {
599  acc.set(value()) = right_child().tree_accumulate(selector,acc,binary_op);
600  }
601  return acc.get(value(),false);
602  }
603 
604  acc.set(value()) = acc.get(value(),true);
605  return acc.get(value(),true);
606 
607  }
608 
610  template<class Visitor>
611  void cascade(Visitor visitor) const {
612  if (leaf()) {
613  visitor.visit(value());
614  return;
615  } else visitor.visit(value(),left_child().value(),right_child().value());
616  left_child().cascade(visitor);
617  right_child().cascade(visitor);
618  }
619 
621  template<class Generator>
622  void generate(Generator generator) {
623  if (root())
624  value_.reset(new value_type(generator.root()));
625  if (generator.split()) {
626  std::pair<iterator,iterator> ch = split(generator.generate(value()));
627  ch.first.node().generate(generator);
628  ch.second.node().generate(generator);
629  }
630  }
631 
632  public:
633 
635 
636 
638  value_type& value() { return *value_; }
639 
641  const value_type& value() const { return *value_; }
642 
644  bool root() const { return !parent_; }
645 
647  bool leaf() const { return !(children_.first.get() && children_.second.get()); }
648 
650 
651  public:
652 
654 
655 
657  template<class OStream>
659 
661  explicit ostream_visitor(OStream& os) : os_(&os), first_time_(true) {}
662 
664  void visit(const value_type&) {
665  (*os_) << "end_branch";
667  }
668 
670  void visit(const value_type& parent,
671  const value_type& left, const value_type& right) {
672  if (first_time_) {
673  (*os_) << "root_node";
675  parent.put(*os_);
676  first_time_ = false;
677  }
678 
679  (*os_) << "left_child";
681  left.put(*os_);
682 
683  (*os_) << "right_child";
685  right.put(*os_);
686 
687  }
688 
689  private:
690 
692  OStream* os_;
693 
696 
697  };
698 
700  template<class IStream>
702 
704  explicit istream_generator(IStream& is)
705  : is_(&is), children_(), tag_("") {}
706 
709  : is_(x.is_), children_(), tag_("") {}
710 
712  value_type root() {
713 
714  *is_ >> tag_;
715  assert(tag_ == "root_node");
716  value_type rnode;
717  rnode.get(*is_);
718 
719  return rnode;
720  }
721 
723  bool split() {
724 
725  *is_ >> tag_;
726 
727  if (tag_ == "end_branch") {
728  return false;
729  }
730 
731  assert (tag_ == "left_child");
732  children_.first.get(*is_);
733 
734  *is_ >> tag_;
735  assert(tag_ == "right_child");
736  children_.second.get(*is_);
737 
738  return true;
739 
740  }
741 
743  std::pair<value_type,value_type> generate(const value_type&) {
744  return children_;
745  }
746 
748  void initialize_leaf(const value_type&) {}
749 
750  private:
751 
753  IStream* is_;
754 
756  std::pair<value_type,value_type> children_;
757 
759  std::string tag_;
760 
761  };
762 
764  template<class OStream>
765  void put(OStream& os) const {
766 
767  if (empty()) {
768  os << "empty";
770  return;
771  } else if (root() && leaf()) {
772  os << "root_only";
774  value().put(os);
775  return;
776  } else {
777  os << "non_empty";
779  }
780 
781  assert(root());
782  cascade(ostream_visitor<OStream>(os));
783 
784  }
785 
787  template<class IStream>
788  void get(IStream& is) {
789 
790  std::string state;
791  is >> state;
792 
793  if (state == "empty") {
794  return;
795  }
796  if (state == "root_only") {
797  value_.reset(new value_type());
798  value().get(is);
799  return;
800  }
801 
802  assert(empty());
803  generate(istream_generator<IStream>(is));
804 
805  }
806 
808 
809 
810  private:
811 
813  template<class Selector, unsigned long bits>
814  void do_subtree_hash(const Selector& selector,
815  bit_container<bits>& current,
816  unsigned long& position,
817  bool selected = true) const {
818 
819  if (!leaf()) {
820 
821  std::pair<bool,bool> which(false,false);
822  if (selected)
823  which = selector.use(value(),left_child().value(),right_child().value());
824 
825  current.bit(position,which.first);
826  current.bit(position+1,which.second);
827 
828  position += 2;
829 
830  left_child().do_subtree_hash(selector,current,position,which.first && selected);
831  right_child().do_subtree_hash(selector,current,position,which.second && selected);
832  }
833 
834  }
835 
836  private:
837 
839 
840 
842  binary_tree& parent() { assert(parent_); return *parent_; }
843 
845  const binary_tree& parent() const { assert(parent_); return *parent_; }
846 
848  binary_tree& left_child() { assert(children_.first.get()); return *children_.first; }
849 
851  const binary_tree& left_child() const { assert(children_.first.get()); return *children_.first; }
852 
854  binary_tree& right_child() { assert(children_.second.get()); return *children_.second; }
855 
857  const binary_tree& right_child() const { assert(children_.second.get()); return *children_.second; }
858 
860 
861  private:
862 
865 
867  std::unique_ptr<value_type> value_;
868 
870  std::pair<std::unique_ptr<binary_tree>,
871  std::unique_ptr<binary_tree> > children_;
872 
873  };
874 
875 }
876 
877 #endif // EXSAMPLE_binary_tree_h_included
std::unique_ptr< value_type > value_
the cell held by this node
Definition: binary_tree.h:867
const_iterator & operator++()
pre-increment
Definition: binary_tree.h:324
void bit(unsigned long k, bool value)
set the k&#39;th bit
Definition: utility.h:96
binary_tree * left_neighbour() const
get the left neighbour
Definition: binary_tree.h:399
std::pair< binary_tree *, binary_tree * > neighbours_
the left and right neighbours of this node
Definition: binary_tree.h:429
std::size_t post_end
the distance from –end() (if above –end())
Definition: binary_tree.h:363
value_type & reference
define the reference type
Definition: binary_tree.h:114
binary_tree * right_most()
return the right-most leaf
Definition: binary_tree.h:411
forward visitor writing out the tree to given ostream
Definition: binary_tree.h:658
binary_tree represents a binary tree with the ability to `cascade&#39; visitor objects down the tree ...
Definition: binary_tree.h:21
reference operator*() const
dereference
Definition: binary_tree.h:310
std::bidirectional_iterator_tag iterator_category
define the iterator category
Definition: binary_tree.h:253
static void separator(OStream &os)
put the separator to the ostream
Definition: utility.h:24
Fixed-size, packed vector of bools.
Definition: utility.h:55
pointer operator->()
indirection
Definition: binary_tree.h:161
binary_tree(const binary_tree &x)
binary_tree has a strict ownership; on copying binary trees ownership is transferred ...
Definition: binary_tree.h:55
const binary_tree * pointee
the node pointed to
Definition: binary_tree.h:360
istream_generator(const istream_generator &x)
copy constructor
Definition: binary_tree.h:708
const value_type & value() const
return the value held by this node
Definition: binary_tree.h:641
BinaryOp::result_type accumulate(const Accessor &acc, BinaryOp binary_op) const
accumulate values using a binary function and accessor object
Definition: binary_tree.h:525
reference operator*()
dereference
Definition: binary_tree.h:158
binary_tree & node()
return reference to the node
Definition: binary_tree.h:164
const_iterator(const iterator &x)
conversion from iterator
Definition: binary_tree.h:282
value_type * pointer
define the pointer type
Definition: binary_tree.h:117
const binary_tree & right_child() const
return the right child of this node
Definition: binary_tree.h:857
BinaryOp::result_type tree_accumulate(const Accessor &acc, BinaryOp binary_op)
accumulate values using a binary function and accessor object, storing intermediate values in nodes ...
Definition: binary_tree.h:567
binary_tree * parent_
the parent of this node
Definition: binary_tree.h:864
friend class const_iterator
friend for conversion
Definition: binary_tree.h:211
void right_neighbour(binary_tree *n)
set the right neighbour
Definition: binary_tree.h:396
void clear()
clear this node
Definition: binary_tree.h:439
std::pair< iterator, iterator > split(std::pair< value_type, value_type > children)
split this node
Definition: binary_tree.h:454
void visit(const value_type &parent, const value_type &left, const value_type &right)
visit a branching
Definition: binary_tree.h:670
iterator(binary_tree *p, std::size_t end=0)
constructor taking pointee
Definition: binary_tree.h:130
binary_tree()
default constructor
Definition: binary_tree.h:39
const_iterator & operator--()
pre-decrement
Definition: binary_tree.h:333
ostream_visitor(OStream &os)
construct from ostream reference
Definition: binary_tree.h:661
const binary_tree & node() const
return reference to the node
Definition: binary_tree.h:316
binary_tree * pointee
the node pointed to
Definition: binary_tree.h:214
const_iterator operator++(int)
post-increment
Definition: binary_tree.h:342
void generate(Generator generator)
succesively split using a generator
Definition: binary_tree.h:622
const_iterator()
default constructor
Definition: binary_tree.h:275
bool operator!=(const iterator &x) const
comparison
Definition: binary_tree.h:148
binary_tree & right_child()
return the right child of this node
Definition: binary_tree.h:854
const_iterator(const binary_tree *p, std::size_t end=0)
constructor taking pointee
Definition: binary_tree.h:278
iterator global_end()
return global end iterator
Definition: binary_tree.h:238
std::pair< std::unique_ptr< binary_tree >, std::unique_ptr< binary_tree > > children_
the children of this node
Definition: binary_tree.h:871
const_iterator global_end() const
return global end iterator
Definition: binary_tree.h:384
value_type & value()
return the value held by this node
Definition: binary_tree.h:638
iterator select(const Selector &selector)
select using a selector
Definition: binary_tree.h:486
std::pair< value_type, value_type > generate(const value_type &)
return the children generated
Definition: binary_tree.h:743
A generator for plain sampling and integrating.
Definition: generator.h:27
const value_type & reference
define the reference type
Definition: binary_tree.h:262
int difference_type
define the difference_type
Definition: binary_tree.h:108
void do_subtree_hash(const Selector &selector, bit_container< bits > &current, unsigned long &position, bool selected=true) const
calculate hash value
Definition: binary_tree.h:814
std::pair< value_type, value_type > children_
the children currently handled
Definition: binary_tree.h:756
const binary_tree & left_child() const
return the left child of this node
Definition: binary_tree.h:851
generator reading binary tree from istream
Definition: binary_tree.h:701
std::size_t pre_begin
the distance from begin() (if below begin())
Definition: binary_tree.h:366
binary_tree * right_neighbour() const
get the right neighbour
Definition: binary_tree.h:402
value_type root()
read the root node
Definition: binary_tree.h:712
void left_neighbour(binary_tree *n)
set the left neighbour
Definition: binary_tree.h:393
iterator & operator++()
pre-increment
Definition: binary_tree.h:175
bool operator!=(const const_iterator &x) const
comparison
Definition: binary_tree.h:300
binary_tree & parent()
return the parent of this node
Definition: binary_tree.h:842
iterator begin()
return begin iterator
Definition: binary_tree.h:225
istream_generator(IStream &is)
construct from istream reference
Definition: binary_tree.h:704
void subtree_hash(const Selector &selector, bit_container< bits > &bhash)
generate a hash value for the sub-tree selected by the given selector object
Definition: binary_tree.h:516
iterator end()
return end iterator
Definition: binary_tree.h:228
iterator operator++(int)
post-increment
Definition: binary_tree.h:193
void initialize_leaf(const value_type &)
initialize a leaf
Definition: binary_tree.h:748
bool first_time_
whether we are at the or not
Definition: binary_tree.h:695
void cascade(Visitor visitor) const
forward propagate a visitor to all children nodes
Definition: binary_tree.h:611
const value_type * pointer
define the pointer type
Definition: binary_tree.h:265
binary_tree(const value_type &thevalue, binary_tree *theparent=0)
construct giving key/cell and parent
Definition: binary_tree.h:46
binary_tree & operator=(const binary_tree &x)
binary_tree has a strict ownership; on copying binary trees ownership is transferred ...
Definition: binary_tree.h:71
const binary_tree & parent() const
return the parent of this node
Definition: binary_tree.h:845
binary_tree & left_child()
return the left child of this node
Definition: binary_tree.h:848
void put(OStream &os) const
put to ostream
Definition: binary_tree.h:765
bool root() const
return true, if this is the root node
Definition: binary_tree.h:644
bool split()
read children nodes
Definition: binary_tree.h:723
binary_tree * left_most()
return the left-most leaf
Definition: binary_tree.h:405
const binary_tree * right_most() const
return the right-most leaf
Definition: binary_tree.h:423
const_iterator begin() const
return begin const_iterator
Definition: binary_tree.h:371
pointer operator->() const
indirection
Definition: binary_tree.h:313
bool empty() const
return true, if this node is empty
Definition: binary_tree.h:436
std::string tag_
temporary storage for tags
Definition: binary_tree.h:759
Value value_type
define the value type
Definition: binary_tree.h:111
bool operator==(const iterator &x) const
comparison
Definition: binary_tree.h:141
iterator & operator--()
pre-decrement
Definition: binary_tree.h:184
const binary_tree * left_most() const
return the left-most leaf
Definition: binary_tree.h:417
const_iterator end() const
return end const_iterator
Definition: binary_tree.h:374
IStream * is_
pointer to the istream used
Definition: binary_tree.h:753
const_iterator global_begin() const
return global begin iterator
Definition: binary_tree.h:377
bool operator==(const const_iterator &x) const
comparison
Definition: binary_tree.h:293
BinaryOp::result_type accumulate(const Selector &selector, const Accessor &acc, BinaryOp binary_op) const
accumulate values only from branches matching a Selector
Definition: binary_tree.h:541
std::bidirectional_iterator_tag iterator_category
define the iterator category
Definition: binary_tree.h:105
iterator operator--(int)
post-decrement
Definition: binary_tree.h:200
iterator global_begin()
return global begin iterator
Definition: binary_tree.h:231
bool leaf() const
return true, if this node has got children
Definition: binary_tree.h:647
Value value_type
define the object type
Definition: binary_tree.h:29
BinaryOp::result_type tree_accumulate(const Selector &selector, const Accessor &acc, BinaryOp binary_op)
accumulate values only from branches matching a Selector
Definition: binary_tree.h:585
std::size_t pre_begin
the distance from begin() (if below begin())
Definition: binary_tree.h:220
const Value value_type
define the value type
Definition: binary_tree.h:259
std::size_t post_end
the distance from –end() (if above –end())
Definition: binary_tree.h:217
const_iterator operator--(int)
post-decrement
Definition: binary_tree.h:349
void visit(const value_type &)
visit a leaf node
Definition: binary_tree.h:664
iterator()
default constructor
Definition: binary_tree.h:127
int difference_type
define the difference type
Definition: binary_tree.h:256
OStream * os_
pointer to the ostream to write to
Definition: binary_tree.h:692