// @(#)root/tmva $Id: BinarySearchTree.h 23334 2008-04-19 18:38:57Z brun $ // Author: Andreas Hoecker, Joerg Stelzer, Helge Voss, Kai Voss /********************************************************************************** * Project: TMVA - a Root-integrated toolkit for multivariate data analysis * * Package: TMVA * * Class : BinarySearchTree * * Web : http://tmva.sourceforge.net * * * * Description: * * BinarySearchTree incl. volume Search method * * * * Authors (alphabetical): * * Andreas Hoecker - CERN, Switzerland * * Helge Voss - MPI-K Heidelberg, Germany * * Kai Voss - U. of Victoria, Canada * * * * Copyright (c) 2005: * * CERN, Switzerland * * U. of Victoria, Canada * * MPI-K Heidelberg, Germany * * LAPP, Annecy, France * * * * Redistribution and use in source and binary forms, with or without * * modification, are permitted according to the terms listed in LICENSE * * (http://tmva.sourceforge.net/LICENSE) * **********************************************************************************/ #ifndef ROOT_TMVA_BinarySearchTree #define ROOT_TMVA_BinarySearchTree ////////////////////////////////////////////////////////////////////////// // // // BinarySearchTree // // // // A simple Binary search tree including volume search method // // // ////////////////////////////////////////////////////////////////////////// #include "Riostream.h" #include #include #include "time.h" #ifndef ROOT_TMVA_Volume #include "TMVA/Volume.h" #endif #ifndef ROOT_TMVA_BinaryTree #include "TMVA/BinaryTree.h" #endif #ifndef ROOT_TMVA_BinarySearchTreeNode #include "TMVA/BinarySearchTreeNode.h" #endif class TString; class TTree; // ----------------------------------------------------------------------------- // the binary search tree using std::vector; using std::queue; namespace TMVA { class DataSet; class Event; class MethodBase; class BinarySearchTree : public BinaryTree { public: // constructor BinarySearchTree( void ); // copy constructor BinarySearchTree (const BinarySearchTree &b); // destructor virtual ~BinarySearchTree( void ); virtual Node * CreateNode() { return new BinarySearchTreeNode(); } virtual Node * CreateNode(const std::vector * vI) { TMVA::Event *ev = new TMVA::Event(*vI, kFALSE); return new BinarySearchTreeNode(ev); } // Searches for a node with the specified data // by calling the private, recursive, function for searching BinarySearchTreeNode* Search( Event * event ) const; // Adds an item to the tree, void Insert( const Event * ); //get sum of weights of the nodes; Double_t GetSumOfWeights( void ) const; //set the periode (number of variables) inline void SetPeriode( Int_t p ) { fPeriod = p; } // return periode (number of variables) inline UInt_t GetPeriode( void ) const { return fPeriod; } // counts events (weights) within a given volume Double_t SearchVolume( Volume*, std::vector* events = 0 ); // create the search tree from the events in a TTree // using the variables specified in the calling Method Double_t Fill( const TMVA::MethodBase& callingMethod, TTree* theTree, Int_t theType ); // Create the search tree from the event collection // using ONLY the variables specified in "theVars" Double_t Fill( vector, vector theVars, Int_t theType = -1 ); // create the search tree from the events in a TTree // using ALL the variables specified included in the Event Double_t Fill( vector theTree, Int_t theType = -1 ); void NormalizeTree (); void CalcStatistics( TMVA::Node* n = 0 ); void Clear ( TMVA::Node* n = 0 ); // access to mean for signal and background for each variable Float_t Mean(Types::ESBType sb, UInt_t var ) { return fMeans[sb==Types::kSignal?0:1][var]; } // access to RMS for signal and background for each variable Float_t RMS(Types::ESBType sb, UInt_t var ) { return fRMS[sb==Types::kSignal?0:1][var]; } // access to Minimum for signal and background for each variable Float_t Min(Types::ESBType sb, UInt_t var ) { return fMin[sb==Types::kSignal?0:1][var]; } // access to Maximum for signal and background for each variable Float_t Max(Types::ESBType sb, UInt_t var ) { return fMax[sb==Types::kSignal?0:1][var]; } Int_t SearchVolumeWithMaxLimit( TMVA::Volume*, std::vector* events = 0, Int_t = -1); void SetNormalize( Bool_t norm ) { fCanNormalize = norm; } private: // add a new node to the tree (as daughter) void Insert( const Event*, Node* ); // recursively search the nodes for Event BinarySearchTreeNode* Search( Event*, Node *) const ; //check of Event variables lie with the volumde Bool_t InVolume (const std::vector&, Volume* ) const; // void NormalizeTree( vector< pair< Double_t, const TMVA::Event* > >::iterator, vector< pair< Double_t, const TMVA::Event* > >::iterator, UInt_t ); // recursive search through daughter nodes in weight counting Double_t SearchVolume( Node*, Volume*, Int_t, std::vector* events ); UInt_t fPeriod; // periode (number of event variables) UInt_t fCurrentDepth; // internal variable, counting the depth of the tree during insertion Bool_t fStatisticsIsValid; // flag if last stat calculation is still valid, set to false if new node is insert std::vector fMeans[2]; // mean for signal and background for each variable std::vector fRMS[2]; // RMS for signal and background for each variable std::vector fMin[2]; // RMS for signal and background for each variable std::vector fMax[2]; // RMS for signal and background for each variable std::vector fSum[2]; // Sum for signal and background for each variable std::vector fSumSq[2]; // Squared Sum for signal and background for each variable Double_t fNEventsW[2]; // Number of events per class, taking into account event weights Double_t fSumOfWeights;// Total number of events (weigthed) counted during filling // should be the same as fNEventsW[0]+fNEventsW[1].. used as a check Bool_t fCanNormalize; // the tree can be normalised std::vector< std::pair > fNormalizeTreeTable; ClassDef(BinarySearchTree,0) // Binary search tree including volume search method }; } // namespace TMVA #endif