herwig is hosted by Hepforge, IPPP Durham
Herwig 7.3.0
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
16namespace exsample {
17
20 template<class Value>
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
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
115
118
120
121 public:
122
124
125
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
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
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
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
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
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
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());
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());
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
const binary_tree & node() const
return reference to the node
Definition: binary_tree.h:316
bool operator==(const const_iterator &x) const
comparison
Definition: binary_tree.h:293
const_iterator(const binary_tree *p, std::size_t end=0)
constructor taking pointee
Definition: binary_tree.h:278
std::size_t pre_begin
the distance from begin() (if below begin())
Definition: binary_tree.h:366
int difference_type
define the difference type
Definition: binary_tree.h:256
bool operator!=(const const_iterator &x) const
comparison
Definition: binary_tree.h:300
const_iterator()
default constructor
Definition: binary_tree.h:275
const_iterator(const iterator &x)
conversion from iterator
Definition: binary_tree.h:282
const binary_tree * pointee
the node pointed to
Definition: binary_tree.h:360
const Value value_type
define the value type
Definition: binary_tree.h:259
pointer operator->() const
indirection
Definition: binary_tree.h:313
const value_type * pointer
define the pointer type
Definition: binary_tree.h:265
reference operator*() const
dereference
Definition: binary_tree.h:310
const value_type & reference
define the reference type
Definition: binary_tree.h:262
const_iterator & operator--()
pre-decrement
Definition: binary_tree.h:333
const_iterator operator++(int)
post-increment
Definition: binary_tree.h:342
std::size_t post_end
the distance from –end() (if above –end())
Definition: binary_tree.h:363
const_iterator & operator++()
pre-increment
Definition: binary_tree.h:324
const_iterator operator--(int)
post-decrement
Definition: binary_tree.h:349
std::bidirectional_iterator_tag iterator_category
define the iterator category
Definition: binary_tree.h:253
binary_tree * get() const
return raw pointer to the element pointed to
Definition: binary_tree.h:169
iterator & operator++()
pre-increment
Definition: binary_tree.h:175
std::size_t post_end
the distance from –end() (if above –end())
Definition: binary_tree.h:217
bool operator!=(const iterator &x) const
comparison
Definition: binary_tree.h:148
iterator(binary_tree *p, std::size_t end=0)
constructor taking pointee
Definition: binary_tree.h:130
iterator()
default constructor
Definition: binary_tree.h:127
value_type * pointer
define the pointer type
Definition: binary_tree.h:117
reference operator*()
dereference
Definition: binary_tree.h:158
pointer operator->()
indirection
Definition: binary_tree.h:161
iterator operator--(int)
post-decrement
Definition: binary_tree.h:200
Value value_type
define the value type
Definition: binary_tree.h:111
int difference_type
define the difference_type
Definition: binary_tree.h:108
std::bidirectional_iterator_tag iterator_category
define the iterator category
Definition: binary_tree.h:105
iterator operator++(int)
post-increment
Definition: binary_tree.h:193
std::size_t pre_begin
the distance from begin() (if below begin())
Definition: binary_tree.h:220
binary_tree & node()
return reference to the node
Definition: binary_tree.h:164
binary_tree * pointee
the node pointed to
Definition: binary_tree.h:214
bool operator==(const iterator &x) const
comparison
Definition: binary_tree.h:141
iterator & operator--()
pre-decrement
Definition: binary_tree.h:184
value_type & reference
define the reference type
Definition: binary_tree.h:114
binary_tree represents a binary tree with the ability to ‘cascade’ visitor objects down the tree
Definition: binary_tree.h:21
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
const binary_tree * right_most() const
return the right-most leaf
Definition: binary_tree.h:423
void clear()
clear this node
Definition: binary_tree.h:439
const binary_tree & parent() const
return the parent of this node
Definition: binary_tree.h:845
iterator global_begin()
return global begin iterator
Definition: binary_tree.h:231
binary_tree(const binary_tree &x)
binary_tree has a strict ownership; on copying binary trees ownership is transferred
Definition: binary_tree.h:55
binary_tree & parent()
return the parent of this node
Definition: binary_tree.h:842
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
const value_type & value() const
return the value held by this node
Definition: binary_tree.h:641
binary_tree * left_most()
return the left-most leaf
Definition: binary_tree.h:405
iterator begin()
return begin iterator
Definition: binary_tree.h:225
bool root() const
return true, if this is the root node
Definition: binary_tree.h:644
binary_tree(const value_type &thevalue, binary_tree *theparent=0)
construct giving key/cell and parent
Definition: binary_tree.h:46
const_iterator end() const
return end const_iterator
Definition: binary_tree.h:374
const binary_tree & right_child() const
return the right child of this node
Definition: binary_tree.h:857
const_iterator begin() const
return begin const_iterator
Definition: binary_tree.h:371
bool leaf() const
return true, if this node has got children
Definition: binary_tree.h:647
binary_tree * right_neighbour() const
get the right neighbour
Definition: binary_tree.h:402
binary_tree * left_neighbour() const
get the left neighbour
Definition: binary_tree.h:399
value_type & value()
return the value held by this node
Definition: binary_tree.h:638
const binary_tree * left_most() const
return the left-most leaf
Definition: binary_tree.h:417
void generate(Generator generator)
succesively split using a generator
Definition: binary_tree.h:622
std::unique_ptr< value_type > value_
the cell held by this node
Definition: binary_tree.h:867
iterator global_end()
return global end iterator
Definition: binary_tree.h:238
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
std::pair< binary_tree *, binary_tree * > neighbours_
the left and right neighbours of this node
Definition: binary_tree.h:429
void put(OStream &os) const
put to ostream
Definition: binary_tree.h:765
std::pair< std::unique_ptr< binary_tree >, std::unique_ptr< binary_tree > > children_
the children of this node
Definition: binary_tree.h:871
binary_tree * right_most()
return the right-most leaf
Definition: binary_tree.h:411
binary_tree()
default constructor
Definition: binary_tree.h:39
void get(IStream &is)
get from istream
Definition: binary_tree.h:788
iterator end()
return end iterator
Definition: binary_tree.h:228
const_iterator global_end() const
return global end iterator
Definition: binary_tree.h:384
const_iterator global_begin() const
return global begin iterator
Definition: binary_tree.h:377
binary_tree & left_child()
return the left child of this node
Definition: binary_tree.h:848
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
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
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
void cascade(Visitor visitor) const
forward propagate a visitor to all children nodes
Definition: binary_tree.h:611
iterator select(const Selector &selector)
select using a selector
Definition: binary_tree.h:486
std::pair< iterator, iterator > split(std::pair< value_type, value_type > children)
split this node
Definition: binary_tree.h:454
void left_neighbour(binary_tree *n)
set the left neighbour
Definition: binary_tree.h:393
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
const binary_tree & left_child() const
return the left child of this node
Definition: binary_tree.h:851
binary_tree & right_child()
return the right child of this node
Definition: binary_tree.h:854
bool empty() const
return true, if this node is empty
Definition: binary_tree.h:436
Value value_type
define the object type
Definition: binary_tree.h:29
void right_neighbour(binary_tree *n)
set the right neighbour
Definition: binary_tree.h:396
A generator for plain sampling and integrating.
Definition: generator.h:27
double generate(SlaveStatistics &)
generate an event, returning the sign of the weight
bool split()
check for and possibly split the last selected cell
ostream & right(ostream &os)
ostream & left(ostream &os)
generator reading binary tree from istream
Definition: binary_tree.h:701
istream_generator(IStream &is)
construct from istream reference
Definition: binary_tree.h:704
IStream * is_
pointer to the istream used
Definition: binary_tree.h:753
istream_generator(const istream_generator &x)
copy constructor
Definition: binary_tree.h:708
bool split()
read children nodes
Definition: binary_tree.h:723
std::string tag_
temporary storage for tags
Definition: binary_tree.h:759
void initialize_leaf(const value_type &)
initialize a leaf
Definition: binary_tree.h:748
std::pair< value_type, value_type > children_
the children currently handled
Definition: binary_tree.h:756
value_type root()
read the root node
Definition: binary_tree.h:712
std::pair< value_type, value_type > generate(const value_type &)
return the children generated
Definition: binary_tree.h:743
forward visitor writing out the tree to given ostream
Definition: binary_tree.h:658
ostream_visitor(OStream &os)
construct from ostream reference
Definition: binary_tree.h:661
OStream * os_
pointer to the ostream to write to
Definition: binary_tree.h:692
void visit(const value_type &)
visit a leaf node
Definition: binary_tree.h:664
void visit(const value_type &parent, const value_type &left, const value_type &right)
visit a branching
Definition: binary_tree.h:670
bool first_time_
whether we are at the or not
Definition: binary_tree.h:695
Fixed-size, packed vector of bools.
Definition: utility.h:55
void bit(unsigned long k, bool value)
set the k'th bit
Definition: utility.h:96
static void separator(OStream &os)
put the separator to the ostream
Definition: utility.h:24