]>
Commit | Line | Data |
---|---|---|
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 | { | |
49 | AliError("cannot build a segmenttree with less than 2 values !"); | |
50 | TObject* forceACrash(0x0); | |
51 | forceACrash->Print(); | |
52 | } | |
53 | ||
54 | fRoot = Build(values,0,values.GetSize()-1); | |
55 | } | |
56 | ||
57 | //_____________________________________________________________________________ | |
58 | AliMUONSegmentTree::~AliMUONSegmentTree() | |
59 | { | |
60 | /// dtor | |
61 | delete fRoot; | |
62 | } | |
63 | ||
64 | //_____________________________________________________________________________ | |
65 | AliMUONNode* | |
66 | AliMUONSegmentTree::Build(const TArrayD& values, Int_t i, Int_t j) | |
67 | { | |
68 | /// Build the segment tree from a list of values | |
69 | ||
70 | double midpoint(TMath::Sqrt(-1.0)); | |
71 | Int_t mid((i+j)/2); | |
72 | ||
73 | if ( mid != i && mid != j ) midpoint = values[mid]; | |
74 | ||
75 | AliMUONNode* node = new AliMUONNode(values[i],values[j],midpoint); | |
76 | ||
77 | if ( j - i == 1 ) return node; | |
78 | ||
79 | node->LeftNode(Build(values,i,(i+j)/2)); | |
80 | node->RightNode(Build(values,(i+j)/2,j)); | |
81 | ||
82 | return node; | |
83 | } | |
84 | ||
85 | //_____________________________________________________________________________ | |
86 | void | |
87 | AliMUONSegmentTree::Contribution(double b, double e) | |
88 | { | |
89 | /// Compute the contribution of edge (b,e) | |
90 | fRoot->Contribution(b,e,fStack); | |
91 | } | |
92 | ||
93 | //_____________________________________________________________________________ | |
94 | void | |
95 | AliMUONSegmentTree::InsertInterval(double b, double e) | |
96 | { | |
97 | /// Insert interval (b,e) | |
98 | fRoot->InsertInterval(b,e,fStack); | |
99 | } | |
100 | ||
101 | //_____________________________________________________________________________ | |
102 | void | |
103 | AliMUONSegmentTree::DeleteInterval(double b, double e) | |
104 | { | |
105 | /// Delete interval (b,e) | |
106 | fRoot->DeleteInterval(b,e,fStack); | |
107 | } | |
108 | ||
109 | //_____________________________________________________________________________ | |
110 | void | |
111 | AliMUONSegmentTree::Print(Option_t*) const | |
112 | { | |
113 | /// Printout | |
114 | if (fRoot) | |
115 | fRoot->Print(); | |
116 | else | |
117 | cout << "Empty binary tree" << endl; | |
118 | } |