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     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 }