herwig
is hosted by
Hepforge
,
IPPP Durham
Herwig
7.3.0
Sampling
exsample
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
39
binary_tree
()
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
55
binary_tree
(
const
binary_tree
& x)
56
:
neighbours_
(x.
neighbours_
),
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
71
binary_tree
&
operator=
(
const
binary_tree
& x) {
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);
79
neighbours_
= x.
neighbours_
;
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
175
iterator
&
operator++
() {
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
; }
179
pointee
=
pointee
->
right_neighbour
();
180
return
*
this
;
181
}
182
184
iterator
&
operator--
() {
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
; }
188
pointee
=
pointee
->
left_neighbour
();
189
return
*
this
;
190
}
191
193
iterator
operator++
(
int
) {
194
iterator
tmp = *
this
;
195
++(*this);
196
return
tmp;
197
}
198
200
iterator
operator--
(
int
) {
201
iterator
tmp = *
this
;
202
--(*this);
203
return
tmp;
204
}
205
207
208
private
:
209
211
friend
class
const_iterator
;
212
214
binary_tree
*
pointee
;
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
231
iterator
global_begin
() {
232
if
(!
root
())
233
return
parent
().
global_begin
();
234
return
iterator
(
left_most
());
235
}
236
238
iterator
global_end
() {
239
if
(!
root
())
240
return
parent
().
global_end
();
241
return
iterator
(
right_most
(),1);
242
}
243
245
class
const_iterator
{
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
275
const_iterator
() :
pointee
(0),
post_end
(0),
pre_begin
(0) { }
276
278
const_iterator
(
const
binary_tree
* p, std::size_t
end
= 0)
279
:
pointee
(p),
post_end
(
end
),
pre_begin
(0) { }
280
282
const_iterator
(
const
iterator
& x)
283
:
pointee
(x.
pointee
),
post_end
(x.
post_end
),
pre_begin
(x.
pre_begin
) { }
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
324
const_iterator
&
operator++
() {
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
; }
328
pointee
=
pointee
->
right_neighbour
();
329
return
*
this
;
330
}
331
333
const_iterator
&
operator--
() {
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
; }
337
pointee
=
pointee
->
left_neighbour
();
338
return
*
this
;
339
}
340
342
const_iterator
operator++
(
int
) {
343
const_iterator
tmp = *
this
;
344
++(*this);
345
return
tmp;
346
}
347
349
const_iterator
operator--
(
int
) {
350
const_iterator
tmp = *
this
;
351
--(*this);
352
return
tmp;
353
}
354
356
357
private
:
358
360
const
binary_tree
*
pointee
;
361
363
std::size_t
post_end
;
364
366
std::size_t
pre_begin
;
367
368
};
369
371
const_iterator
begin
()
const
{
return
const_iterator
(
left_most
()); }
372
374
const_iterator
end
()
const
{
return
const_iterator
(
right_most
(),1); }
375
377
const_iterator
global_begin
()
const
{
378
if
(!
root
())
379
return
parent
().
global_begin
();
380
return
iterator
(
left_most
());
381
}
382
384
const_iterator
global_end
()
const
{
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
405
binary_tree
*
left_most
() {
406
if
(
leaf
())
return
this
;
407
return
left_child
().
left_most
();
408
}
409
411
binary_tree
*
right_most
() {
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>
658
struct
ostream_visitor
{
659
661
explicit
ostream_visitor
(OStream& os) :
os_
(&os),
first_time_
(true) {}
662
664
void
visit
(
const
value_type
&) {
665
(*os_) <<
"end_branch"
;
666
ostream_traits<OStream>::separator
(*
os_
);
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"
;
674
ostream_traits<OStream>::separator
(*
os_
);
675
parent
.
put
(*
os_
);
676
first_time_
=
false
;
677
}
678
679
(*os_) <<
"left_child"
;
680
ostream_traits<OStream>::separator
(*
os_
);
681
left
.put(*
os_
);
682
683
(*os_) <<
"right_child"
;
684
ostream_traits<OStream>::separator
(*
os_
);
685
right
.put(*
os_
);
686
687
}
688
689
private
:
690
692
OStream*
os_
;
693
695
bool
first_time_
;
696
697
};
698
700
template
<
class
IStream>
701
struct
istream_generator
{
702
704
explicit
istream_generator
(IStream& is)
705
:
is_
(&is),
children_
(),
tag_
(
""
) {}
706
708
istream_generator
(
const
istream_generator
& x)
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"
;
769
ostream_traits<OStream>::separator
(os);
770
return
;
771
}
else
if
(
root
() &&
leaf
()) {
772
os <<
"root_only"
;
773
ostream_traits<OStream>::separator
(os);
774
value
().put(os);
775
return
;
776
}
else
{
777
os <<
"non_empty"
;
778
ostream_traits<OStream>::separator
(os);
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
864
binary_tree
*
parent_
;
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
exsample::binary_tree::const_iterator
const_iterator
Definition:
binary_tree.h:245
exsample::binary_tree::const_iterator::node
const binary_tree & node() const
return reference to the node
Definition:
binary_tree.h:316
exsample::binary_tree::const_iterator::operator==
bool operator==(const const_iterator &x) const
comparison
Definition:
binary_tree.h:293
exsample::binary_tree::const_iterator::const_iterator
const_iterator(const binary_tree *p, std::size_t end=0)
constructor taking pointee
Definition:
binary_tree.h:278
exsample::binary_tree::const_iterator::pre_begin
std::size_t pre_begin
the distance from begin() (if below begin())
Definition:
binary_tree.h:366
exsample::binary_tree::const_iterator::difference_type
int difference_type
define the difference type
Definition:
binary_tree.h:256
exsample::binary_tree::const_iterator::operator!=
bool operator!=(const const_iterator &x) const
comparison
Definition:
binary_tree.h:300
exsample::binary_tree::const_iterator::const_iterator
const_iterator()
default constructor
Definition:
binary_tree.h:275
exsample::binary_tree::const_iterator::const_iterator
const_iterator(const iterator &x)
conversion from iterator
Definition:
binary_tree.h:282
exsample::binary_tree::const_iterator::pointee
const binary_tree * pointee
the node pointed to
Definition:
binary_tree.h:360
exsample::binary_tree::const_iterator::value_type
const Value value_type
define the value type
Definition:
binary_tree.h:259
exsample::binary_tree::const_iterator::operator->
pointer operator->() const
indirection
Definition:
binary_tree.h:313
exsample::binary_tree::const_iterator::pointer
const value_type * pointer
define the pointer type
Definition:
binary_tree.h:265
exsample::binary_tree::const_iterator::operator*
reference operator*() const
dereference
Definition:
binary_tree.h:310
exsample::binary_tree::const_iterator::reference
const value_type & reference
define the reference type
Definition:
binary_tree.h:262
exsample::binary_tree::const_iterator::operator--
const_iterator & operator--()
pre-decrement
Definition:
binary_tree.h:333
exsample::binary_tree::const_iterator::operator++
const_iterator operator++(int)
post-increment
Definition:
binary_tree.h:342
exsample::binary_tree::const_iterator::post_end
std::size_t post_end
the distance from –end() (if above –end())
Definition:
binary_tree.h:363
exsample::binary_tree::const_iterator::operator++
const_iterator & operator++()
pre-increment
Definition:
binary_tree.h:324
exsample::binary_tree::const_iterator::operator--
const_iterator operator--(int)
post-decrement
Definition:
binary_tree.h:349
exsample::binary_tree::const_iterator::iterator_category
std::bidirectional_iterator_tag iterator_category
define the iterator category
Definition:
binary_tree.h:253
exsample::binary_tree::iterator
iterator
Definition:
binary_tree.h:97
exsample::binary_tree::iterator::get
binary_tree * get() const
return raw pointer to the element pointed to
Definition:
binary_tree.h:169
exsample::binary_tree::iterator::operator++
iterator & operator++()
pre-increment
Definition:
binary_tree.h:175
exsample::binary_tree::iterator::post_end
std::size_t post_end
the distance from –end() (if above –end())
Definition:
binary_tree.h:217
exsample::binary_tree::iterator::operator!=
bool operator!=(const iterator &x) const
comparison
Definition:
binary_tree.h:148
exsample::binary_tree::iterator::iterator
iterator(binary_tree *p, std::size_t end=0)
constructor taking pointee
Definition:
binary_tree.h:130
exsample::binary_tree::iterator::iterator
iterator()
default constructor
Definition:
binary_tree.h:127
exsample::binary_tree::iterator::pointer
value_type * pointer
define the pointer type
Definition:
binary_tree.h:117
exsample::binary_tree::iterator::operator*
reference operator*()
dereference
Definition:
binary_tree.h:158
exsample::binary_tree::iterator::operator->
pointer operator->()
indirection
Definition:
binary_tree.h:161
exsample::binary_tree::iterator::operator--
iterator operator--(int)
post-decrement
Definition:
binary_tree.h:200
exsample::binary_tree::iterator::value_type
Value value_type
define the value type
Definition:
binary_tree.h:111
exsample::binary_tree::iterator::difference_type
int difference_type
define the difference_type
Definition:
binary_tree.h:108
exsample::binary_tree::iterator::iterator_category
std::bidirectional_iterator_tag iterator_category
define the iterator category
Definition:
binary_tree.h:105
exsample::binary_tree::iterator::operator++
iterator operator++(int)
post-increment
Definition:
binary_tree.h:193
exsample::binary_tree::iterator::pre_begin
std::size_t pre_begin
the distance from begin() (if below begin())
Definition:
binary_tree.h:220
exsample::binary_tree::iterator::node
binary_tree & node()
return reference to the node
Definition:
binary_tree.h:164
exsample::binary_tree::iterator::pointee
binary_tree * pointee
the node pointed to
Definition:
binary_tree.h:214
exsample::binary_tree::iterator::operator==
bool operator==(const iterator &x) const
comparison
Definition:
binary_tree.h:141
exsample::binary_tree::iterator::operator--
iterator & operator--()
pre-decrement
Definition:
binary_tree.h:184
exsample::binary_tree::iterator::reference
value_type & reference
define the reference type
Definition:
binary_tree.h:114
exsample::binary_tree
binary_tree represents a binary tree with the ability to ‘cascade’ visitor objects down the tree
Definition:
binary_tree.h:21
exsample::binary_tree::tree_accumulate
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
exsample::binary_tree::right_most
const binary_tree * right_most() const
return the right-most leaf
Definition:
binary_tree.h:423
exsample::binary_tree::clear
void clear()
clear this node
Definition:
binary_tree.h:439
exsample::binary_tree::parent
const binary_tree & parent() const
return the parent of this node
Definition:
binary_tree.h:845
exsample::binary_tree::global_begin
iterator global_begin()
return global begin iterator
Definition:
binary_tree.h:231
exsample::binary_tree::binary_tree
binary_tree(const binary_tree &x)
binary_tree has a strict ownership; on copying binary trees ownership is transferred
Definition:
binary_tree.h:55
exsample::binary_tree::parent
binary_tree & parent()
return the parent of this node
Definition:
binary_tree.h:842
exsample::binary_tree::accumulate
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
exsample::binary_tree::value
const value_type & value() const
return the value held by this node
Definition:
binary_tree.h:641
exsample::binary_tree::left_most
binary_tree * left_most()
return the left-most leaf
Definition:
binary_tree.h:405
exsample::binary_tree::begin
iterator begin()
return begin iterator
Definition:
binary_tree.h:225
exsample::binary_tree::root
bool root() const
return true, if this is the root node
Definition:
binary_tree.h:644
exsample::binary_tree::binary_tree
binary_tree(const value_type &thevalue, binary_tree *theparent=0)
construct giving key/cell and parent
Definition:
binary_tree.h:46
exsample::binary_tree::end
const_iterator end() const
return end const_iterator
Definition:
binary_tree.h:374
exsample::binary_tree::right_child
const binary_tree & right_child() const
return the right child of this node
Definition:
binary_tree.h:857
exsample::binary_tree::begin
const_iterator begin() const
return begin const_iterator
Definition:
binary_tree.h:371
exsample::binary_tree::leaf
bool leaf() const
return true, if this node has got children
Definition:
binary_tree.h:647
exsample::binary_tree::right_neighbour
binary_tree * right_neighbour() const
get the right neighbour
Definition:
binary_tree.h:402
exsample::binary_tree::left_neighbour
binary_tree * left_neighbour() const
get the left neighbour
Definition:
binary_tree.h:399
exsample::binary_tree::value
value_type & value()
return the value held by this node
Definition:
binary_tree.h:638
exsample::binary_tree::left_most
const binary_tree * left_most() const
return the left-most leaf
Definition:
binary_tree.h:417
exsample::binary_tree::generate
void generate(Generator generator)
succesively split using a generator
Definition:
binary_tree.h:622
exsample::binary_tree::value_
std::unique_ptr< value_type > value_
the cell held by this node
Definition:
binary_tree.h:867
exsample::binary_tree::global_end
iterator global_end()
return global end iterator
Definition:
binary_tree.h:238
exsample::binary_tree::operator=
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
exsample::binary_tree::neighbours_
std::pair< binary_tree *, binary_tree * > neighbours_
the left and right neighbours of this node
Definition:
binary_tree.h:429
exsample::binary_tree::put
void put(OStream &os) const
put to ostream
Definition:
binary_tree.h:765
exsample::binary_tree::children_
std::pair< std::unique_ptr< binary_tree >, std::unique_ptr< binary_tree > > children_
the children of this node
Definition:
binary_tree.h:871
exsample::binary_tree::right_most
binary_tree * right_most()
return the right-most leaf
Definition:
binary_tree.h:411
exsample::binary_tree::binary_tree
binary_tree()
default constructor
Definition:
binary_tree.h:39
exsample::binary_tree::get
void get(IStream &is)
get from istream
Definition:
binary_tree.h:788
exsample::binary_tree::end
iterator end()
return end iterator
Definition:
binary_tree.h:228
exsample::binary_tree::global_end
const_iterator global_end() const
return global end iterator
Definition:
binary_tree.h:384
exsample::binary_tree::global_begin
const_iterator global_begin() const
return global begin iterator
Definition:
binary_tree.h:377
exsample::binary_tree::left_child
binary_tree & left_child()
return the left child of this node
Definition:
binary_tree.h:848
exsample::binary_tree::accumulate
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
exsample::binary_tree::tree_accumulate
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
exsample::binary_tree::parent_
binary_tree * parent_
the parent of this node
Definition:
binary_tree.h:864
exsample::binary_tree::subtree_hash
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
exsample::binary_tree::cascade
void cascade(Visitor visitor) const
forward propagate a visitor to all children nodes
Definition:
binary_tree.h:611
exsample::binary_tree::select
iterator select(const Selector &selector)
select using a selector
Definition:
binary_tree.h:486
exsample::binary_tree::split
std::pair< iterator, iterator > split(std::pair< value_type, value_type > children)
split this node
Definition:
binary_tree.h:454
exsample::binary_tree::left_neighbour
void left_neighbour(binary_tree *n)
set the left neighbour
Definition:
binary_tree.h:393
exsample::binary_tree::do_subtree_hash
void do_subtree_hash(const Selector &selector, bit_container< bits > ¤t, unsigned long &position, bool selected=true) const
calculate hash value
Definition:
binary_tree.h:814
exsample::binary_tree::left_child
const binary_tree & left_child() const
return the left child of this node
Definition:
binary_tree.h:851
exsample::binary_tree::right_child
binary_tree & right_child()
return the right child of this node
Definition:
binary_tree.h:854
exsample::binary_tree::empty
bool empty() const
return true, if this node is empty
Definition:
binary_tree.h:436
exsample::binary_tree::value_type
Value value_type
define the object type
Definition:
binary_tree.h:29
exsample::binary_tree::right_neighbour
void right_neighbour(binary_tree *n)
set the right neighbour
Definition:
binary_tree.h:396
exsample::generator
A generator for plain sampling and integrating.
Definition:
generator.h:27
exsample::generator::generate
double generate(SlaveStatistics &)
generate an event, returning the sign of the weight
exsample::generator::split
bool split()
check for and possibly split the last selected cell
right
ostream & right(ostream &os)
left
ostream & left(ostream &os)
exsample::binary_tree::istream_generator
generator reading binary tree from istream
Definition:
binary_tree.h:701
exsample::binary_tree::istream_generator::istream_generator
istream_generator(IStream &is)
construct from istream reference
Definition:
binary_tree.h:704
exsample::binary_tree::istream_generator::is_
IStream * is_
pointer to the istream used
Definition:
binary_tree.h:753
exsample::binary_tree::istream_generator::istream_generator
istream_generator(const istream_generator &x)
copy constructor
Definition:
binary_tree.h:708
exsample::binary_tree::istream_generator::split
bool split()
read children nodes
Definition:
binary_tree.h:723
exsample::binary_tree::istream_generator::tag_
std::string tag_
temporary storage for tags
Definition:
binary_tree.h:759
exsample::binary_tree::istream_generator::initialize_leaf
void initialize_leaf(const value_type &)
initialize a leaf
Definition:
binary_tree.h:748
exsample::binary_tree::istream_generator::children_
std::pair< value_type, value_type > children_
the children currently handled
Definition:
binary_tree.h:756
exsample::binary_tree::istream_generator::root
value_type root()
read the root node
Definition:
binary_tree.h:712
exsample::binary_tree::istream_generator::generate
std::pair< value_type, value_type > generate(const value_type &)
return the children generated
Definition:
binary_tree.h:743
exsample::binary_tree::ostream_visitor
forward visitor writing out the tree to given ostream
Definition:
binary_tree.h:658
exsample::binary_tree::ostream_visitor::ostream_visitor
ostream_visitor(OStream &os)
construct from ostream reference
Definition:
binary_tree.h:661
exsample::binary_tree::ostream_visitor::os_
OStream * os_
pointer to the ostream to write to
Definition:
binary_tree.h:692
exsample::binary_tree::ostream_visitor::visit
void visit(const value_type &)
visit a leaf node
Definition:
binary_tree.h:664
exsample::binary_tree::ostream_visitor::visit
void visit(const value_type &parent, const value_type &left, const value_type &right)
visit a branching
Definition:
binary_tree.h:670
exsample::binary_tree::ostream_visitor::first_time_
bool first_time_
whether we are at the or not
Definition:
binary_tree.h:695
exsample::bit_container
Fixed-size, packed vector of bools.
Definition:
utility.h:55
exsample::bit_container::bit
void bit(unsigned long k, bool value)
set the k'th bit
Definition:
utility.h:96
exsample::ostream_traits::separator
static void separator(OStream &os)
put the separator to the ostream
Definition:
utility.h:24
Generated on Thu Jun 20 2024 17:50:53 for Herwig by
1.9.6