]>
Commit | Line | Data |
---|---|---|
0b936dc0 | 1 | /************************************************************************** |
2 | * Copyright(c) 1998-1999, ALICE Experiment at CERN, All rights reserved. * | |
3 | * * | |
4 | * Author: The ALICE Off-line Project. * | |
5 | * Contributors are mentioned in the code where appropriate. * | |
6 | * * | |
7 | * Permission to use, copy, modify and distribute this software and its * | |
8 | * documentation strictly for non-commercial purposes is hereby granted * | |
9 | * without fee, provided that the above copyright notice appears in all * | |
10 | * copies and that both the copyright notice and this permission notice * | |
11 | * appear in the supporting documentation. The authors make no claims * | |
12 | * about the suitability of this software for any purpose. It is * | |
13 | * provided "as is" without express or implied warranty. * | |
14 | **************************************************************************/ | |
15 | ||
16 | // $Id$ | |
17 | ||
18 | /// | |
19 | /// \class AliMUONSegmentTree | |
20 | /// | |
21 | /// Implementation of a segment tree, which is used to make contour | |
22 | /// merging (see AliMUONContourMaker) | |
23 | /// | |
24 | /// \author Laurent Aphecetche, Subatech | |
25 | /// | |
26 | ||
27 | #include "AliMUONSegmentTree.h" | |
28 | ||
29 | #include "AliLog.h" | |
30 | #include "AliMUONNode.h" | |
31 | #include "Riostream.h" | |
32 | #include "TArrayD.h" | |
33 | #include "TMath.h" | |
34 | ||
35 | /// \cond CLASSIMP | |
36 | ClassImp(AliMUONSegmentTree) | |
37 | /// \endcond | |
38 | ||
39 | //_____________________________________________________________________________ | |
40 | AliMUONSegmentTree::AliMUONSegmentTree(const TArrayD& values) | |
41 | : fRoot(0x0), fStack() | |
42 | { | |
43 | /// Values should be sorted and have at least 2 elements. | |
44 | ||
45 | fStack.SetOwner(kTRUE); | |
46 | ||
47 | if ( values.GetSize() < 2 ) | |
48 | { | |
fc2293be | 49 | AliFatal("cannot build a segmenttree with less than 2 values !"); |
0b936dc0 | 50 | } |
51 | ||
52 | fRoot = Build(values,0,values.GetSize()-1); | |
53 | } | |
54 | ||
55 | //_____________________________________________________________________________ | |
56 | AliMUONSegmentTree::~AliMUONSegmentTree() | |
57 | { | |
58 | /// dtor | |
59 | delete fRoot; | |
60 | } | |
61 | ||
62 | //_____________________________________________________________________________ | |
63 | AliMUONNode* | |
64 | AliMUONSegmentTree::Build(const TArrayD& values, Int_t i, Int_t j) | |
65 | { | |
66 | /// Build the segment tree from a list of values | |
67 | ||
68 | double midpoint(TMath::Sqrt(-1.0)); | |
69 | Int_t mid((i+j)/2); | |
70 | ||
71 | if ( mid != i && mid != j ) midpoint = values[mid]; | |
72 | ||
73 | AliMUONNode* node = new AliMUONNode(values[i],values[j],midpoint); | |
74 | ||
75 | if ( j - i == 1 ) return node; | |
76 | ||
77 | node->LeftNode(Build(values,i,(i+j)/2)); | |
78 | node->RightNode(Build(values,(i+j)/2,j)); | |
79 | ||
80 | return node; | |
81 | } | |
82 | ||
83 | //_____________________________________________________________________________ | |
84 | void | |
85 | AliMUONSegmentTree::Contribution(double b, double e) | |
86 | { | |
87 | /// Compute the contribution of edge (b,e) | |
88 | fRoot->Contribution(b,e,fStack); | |
89 | } | |
90 | ||
91 | //_____________________________________________________________________________ | |
92 | void | |
93 | AliMUONSegmentTree::InsertInterval(double b, double e) | |
94 | { | |
95 | /// Insert interval (b,e) | |
96 | fRoot->InsertInterval(b,e,fStack); | |
97 | } | |
98 | ||
99 | //_____________________________________________________________________________ | |
100 | void | |
101 | AliMUONSegmentTree::DeleteInterval(double b, double e) | |
102 | { | |
103 | /// Delete interval (b,e) | |
104 | fRoot->DeleteInterval(b,e,fStack); | |
105 | } | |
106 | ||
107 | //_____________________________________________________________________________ | |
108 | void | |
109 | AliMUONSegmentTree::Print(Option_t*) const | |
110 | { | |
111 | /// Printout | |
112 | if (fRoot) | |
113 | fRoot->Print(); | |
114 | else | |
115 | cout << "Empty binary tree" << endl; | |
116 | } |