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 /// \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     AliFatal("cannot build a segmenttree with less than 2 values !");
  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 }