1 /**************************************************************************
2 * Copyright(c) 1998-1999, ALICE Experiment at CERN, All rights reserved. *
4 * Author: The ALICE Off-line Project. *
5 * Contributors are mentioned in the code where appropriate. *
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 **************************************************************************/
19 /// \class AliMUONSegmentTree
21 /// Implementation of a segment tree, which is used to make contour
22 /// merging (see AliMUONContourMaker)
24 /// \author Laurent Aphecetche, Subatech
27 #include "AliMUONSegmentTree.h"
30 #include "AliMUONNode.h"
31 #include "Riostream.h"
36 ClassImp(AliMUONSegmentTree)
39 //_____________________________________________________________________________
40 AliMUONSegmentTree::AliMUONSegmentTree(const TArrayD& values)
41 : fRoot(0x0), fStack()
43 /// Values should be sorted and have at least 2 elements.
45 fStack.SetOwner(kTRUE);
47 if ( values.GetSize() < 2 )
49 AliError("cannot build a segmenttree with less than 2 values !");
50 TObject* forceACrash(0x0);
54 fRoot = Build(values,0,values.GetSize()-1);
57 //_____________________________________________________________________________
58 AliMUONSegmentTree::~AliMUONSegmentTree()
64 //_____________________________________________________________________________
66 AliMUONSegmentTree::Build(const TArrayD& values, Int_t i, Int_t j)
68 /// Build the segment tree from a list of values
70 double midpoint(TMath::Sqrt(-1.0));
73 if ( mid != i && mid != j ) midpoint = values[mid];
75 AliMUONNode* node = new AliMUONNode(values[i],values[j],midpoint);
77 if ( j - i == 1 ) return node;
79 node->LeftNode(Build(values,i,(i+j)/2));
80 node->RightNode(Build(values,(i+j)/2,j));
85 //_____________________________________________________________________________
87 AliMUONSegmentTree::Contribution(double b, double e)
89 /// Compute the contribution of edge (b,e)
90 fRoot->Contribution(b,e,fStack);
93 //_____________________________________________________________________________
95 AliMUONSegmentTree::InsertInterval(double b, double e)
97 /// Insert interval (b,e)
98 fRoot->InsertInterval(b,e,fStack);
101 //_____________________________________________________________________________
103 AliMUONSegmentTree::DeleteInterval(double b, double e)
105 /// Delete interval (b,e)
106 fRoot->DeleteInterval(b,e,fStack);
109 //_____________________________________________________________________________
111 AliMUONSegmentTree::Print(Option_t*) const
117 cout << "Empty binary tree" << endl;