Adding more bins in QA (Alis)
[u/mrichter/AliRoot.git] / MUON / AliMUONSegmentTree.cxx
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 using std::cout;
36 using std::endl;
37 /// \cond CLASSIMP
38 ClassImp(AliMUONSegmentTree)
39 /// \endcond
40
41 //_____________________________________________________________________________
42 AliMUONSegmentTree::AliMUONSegmentTree(const TArrayD& values)
43 : fRoot(0x0), fStack()
44 {
45   /// Values should be sorted and have at least 2 elements.
46   
47   fStack.SetOwner(kTRUE);
48   
49   if ( values.GetSize() < 2 ) 
50   {
51     AliFatal("cannot build a segmenttree with less than 2 values !");
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 }