Make the Scan method public
[u/mrichter/AliRoot.git] / MUON / AliMUONSegmentTree.cxx
CommitLineData
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
b80faac0 35using std::cout;
36using std::endl;
0b936dc0 37/// \cond CLASSIMP
38ClassImp(AliMUONSegmentTree)
39/// \endcond
40
41//_____________________________________________________________________________
42AliMUONSegmentTree::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 {
fc2293be 51 AliFatal("cannot build a segmenttree with less than 2 values !");
0b936dc0 52 }
53
54 fRoot = Build(values,0,values.GetSize()-1);
55}
56
57//_____________________________________________________________________________
58AliMUONSegmentTree::~AliMUONSegmentTree()
59{
60 /// dtor
61 delete fRoot;
62}
63
64//_____________________________________________________________________________
65AliMUONNode*
66AliMUONSegmentTree::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//_____________________________________________________________________________
86void
87AliMUONSegmentTree::Contribution(double b, double e)
88{
89 /// Compute the contribution of edge (b,e)
90 fRoot->Contribution(b,e,fStack);
91}
92
93//_____________________________________________________________________________
94void
95AliMUONSegmentTree::InsertInterval(double b, double e)
96{
97 /// Insert interval (b,e)
98 fRoot->InsertInterval(b,e,fStack);
99}
100
101//_____________________________________________________________________________
102void
103AliMUONSegmentTree::DeleteInterval(double b, double e)
104{
105 /// Delete interval (b,e)
106 fRoot->DeleteInterval(b,e,fStack);
107}
108
109//_____________________________________________________________________________
110void
111AliMUONSegmentTree::Print(Option_t*) const
112{
113 /// Printout
114 if (fRoot)
115 fRoot->Print();
116 else
117 cout << "Empty binary tree" << endl;
118}