// @(#)root/tmva $Id$    
// 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 <Andreas.Hocker@cern.ch> - CERN, Switzerland              *
 *      Joerg Stelzer   <Joerg.Stelzer@cern.ch>  - CERN, Switzerland              *
 *      Helge Voss      <Helge.Voss@cern.ch>     - MPI-K Heidelberg, Germany      *
 *      Kai Voss        <Kai.Voss@cern.ch>       - 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 <vector>
#include <queue>
#ifndef ROOT_time
#include "time.h"
#endif

#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
#ifndef ROOT_TMVA_VariableInfo
#include "TMVA/VariableInfo.h"
#endif

class TString;
class TTree;

// -----------------------------------------------------------------------------
// the binary search tree

namespace TMVA {

   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( UInt_t ) const { return new BinarySearchTreeNode(); }
      virtual BinaryTree* CreateTree() const { return new BinarySearchTree(); }
      static BinarySearchTree* CreateFromXML(void* node, UInt_t tmva_Version_Code = TMVA_VERSION_CODE);
      virtual const char* ClassName() const { return "BinarySearchTree"; }

      // 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;

      //get sum of weights of the nodes of given type;
      Double_t GetSumOfWeights( Int_t theType ) const;
    
      //set the periode (number of variables)
      void SetPeriode( Int_t p )      { fPeriod = p; }

      // return periode (number of variables)
      UInt_t  GetPeriode( void ) const { return fPeriod; }

      // counts events (weights) within a given volume 
      Double_t SearchVolume( Volume*, std::vector<const TMVA::BinarySearchTreeNode*>* events = 0 );
    
      // Create the search tree from the event collection 
      // using ONLY the variables specified in "theVars"
      Double_t Fill( const std::vector<TMVA::Event*>& events, const std::vector<Int_t>& 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( const std::vector<TMVA::Event*>& events, 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<const TMVA::BinarySearchTreeNode*>* events = 0, Int_t = -1);

      // access to RMS for each variable
      Float_t RMS(UInt_t var ) { return fRMS[0][var]; } // attention! class 0 is taken as signal!

      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<Float_t>&, Volume* ) const;
      //
      void     DestroyNode ( BinarySearchTreeNode* );


      void     NormalizeTree( std::vector< std::pair< Double_t, const TMVA::Event* > >::iterator, 
                              std::vector< std::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<const TMVA::BinarySearchTreeNode*>* 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<Float_t>        fMeans[2];    // mean for signal and background for each variable
      std::vector<Float_t>        fRMS[2];      // RMS for signal and background for each variable
      std::vector<Float_t>        fMin[2];      // RMS for signal and background for each variable
      std::vector<Float_t>        fMax[2];      // RMS for signal and background for each variable
      std::vector<Double_t>       fSum[2];      // Sum for signal and background for each variable
      std::vector<Double_t>       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<Double_t,const TMVA::Event*> > fNormalizeTreeTable;
      
      ClassDef(BinarySearchTree,0) // Binary search tree including volume search method  
   };
  
} // namespace TMVA

#endif
 BinarySearchTree.h:1
 BinarySearchTree.h:2
 BinarySearchTree.h:3
 BinarySearchTree.h:4
 BinarySearchTree.h:5
 BinarySearchTree.h:6
 BinarySearchTree.h:7
 BinarySearchTree.h:8
 BinarySearchTree.h:9
 BinarySearchTree.h:10
 BinarySearchTree.h:11
 BinarySearchTree.h:12
 BinarySearchTree.h:13
 BinarySearchTree.h:14
 BinarySearchTree.h:15
 BinarySearchTree.h:16
 BinarySearchTree.h:17
 BinarySearchTree.h:18
 BinarySearchTree.h:19
 BinarySearchTree.h:20
 BinarySearchTree.h:21
 BinarySearchTree.h:22
 BinarySearchTree.h:23
 BinarySearchTree.h:24
 BinarySearchTree.h:25
 BinarySearchTree.h:26
 BinarySearchTree.h:27
 BinarySearchTree.h:28
 BinarySearchTree.h:29
 BinarySearchTree.h:30
 BinarySearchTree.h:31
 BinarySearchTree.h:32
 BinarySearchTree.h:33
 BinarySearchTree.h:34
 BinarySearchTree.h:35
 BinarySearchTree.h:36
 BinarySearchTree.h:37
 BinarySearchTree.h:38
 BinarySearchTree.h:39
 BinarySearchTree.h:40
 BinarySearchTree.h:41
 BinarySearchTree.h:42
 BinarySearchTree.h:43
 BinarySearchTree.h:44
 BinarySearchTree.h:45
 BinarySearchTree.h:46
 BinarySearchTree.h:47
 BinarySearchTree.h:48
 BinarySearchTree.h:49
 BinarySearchTree.h:50
 BinarySearchTree.h:51
 BinarySearchTree.h:52
 BinarySearchTree.h:53
 BinarySearchTree.h:54
 BinarySearchTree.h:55
 BinarySearchTree.h:56
 BinarySearchTree.h:57
 BinarySearchTree.h:58
 BinarySearchTree.h:59
 BinarySearchTree.h:60
 BinarySearchTree.h:61
 BinarySearchTree.h:62
 BinarySearchTree.h:63
 BinarySearchTree.h:64
 BinarySearchTree.h:65
 BinarySearchTree.h:66
 BinarySearchTree.h:67
 BinarySearchTree.h:68
 BinarySearchTree.h:69
 BinarySearchTree.h:70
 BinarySearchTree.h:71
 BinarySearchTree.h:72
 BinarySearchTree.h:73
 BinarySearchTree.h:74
 BinarySearchTree.h:75
 BinarySearchTree.h:76
 BinarySearchTree.h:77
 BinarySearchTree.h:78
 BinarySearchTree.h:79
 BinarySearchTree.h:80
 BinarySearchTree.h:81
 BinarySearchTree.h:82
 BinarySearchTree.h:83
 BinarySearchTree.h:84
 BinarySearchTree.h:85
 BinarySearchTree.h:86
 BinarySearchTree.h:87
 BinarySearchTree.h:88
 BinarySearchTree.h:89
 BinarySearchTree.h:90
 BinarySearchTree.h:91
 BinarySearchTree.h:92
 BinarySearchTree.h:93
 BinarySearchTree.h:94
 BinarySearchTree.h:95
 BinarySearchTree.h:96
 BinarySearchTree.h:97
 BinarySearchTree.h:98
 BinarySearchTree.h:99
 BinarySearchTree.h:100
 BinarySearchTree.h:101
 BinarySearchTree.h:102
 BinarySearchTree.h:103
 BinarySearchTree.h:104
 BinarySearchTree.h:105
 BinarySearchTree.h:106
 BinarySearchTree.h:107
 BinarySearchTree.h:108
 BinarySearchTree.h:109
 BinarySearchTree.h:110
 BinarySearchTree.h:111
 BinarySearchTree.h:112
 BinarySearchTree.h:113
 BinarySearchTree.h:114
 BinarySearchTree.h:115
 BinarySearchTree.h:116
 BinarySearchTree.h:117
 BinarySearchTree.h:118
 BinarySearchTree.h:119
 BinarySearchTree.h:120
 BinarySearchTree.h:121
 BinarySearchTree.h:122
 BinarySearchTree.h:123
 BinarySearchTree.h:124
 BinarySearchTree.h:125
 BinarySearchTree.h:126
 BinarySearchTree.h:127
 BinarySearchTree.h:128
 BinarySearchTree.h:129
 BinarySearchTree.h:130
 BinarySearchTree.h:131
 BinarySearchTree.h:132
 BinarySearchTree.h:133
 BinarySearchTree.h:134
 BinarySearchTree.h:135
 BinarySearchTree.h:136
 BinarySearchTree.h:137
 BinarySearchTree.h:138
 BinarySearchTree.h:139
 BinarySearchTree.h:140
 BinarySearchTree.h:141
 BinarySearchTree.h:142
 BinarySearchTree.h:143
 BinarySearchTree.h:144
 BinarySearchTree.h:145
 BinarySearchTree.h:146
 BinarySearchTree.h:147
 BinarySearchTree.h:148
 BinarySearchTree.h:149
 BinarySearchTree.h:150
 BinarySearchTree.h:151
 BinarySearchTree.h:152
 BinarySearchTree.h:153
 BinarySearchTree.h:154
 BinarySearchTree.h:155
 BinarySearchTree.h:156
 BinarySearchTree.h:157
 BinarySearchTree.h:158
 BinarySearchTree.h:159
 BinarySearchTree.h:160
 BinarySearchTree.h:161
 BinarySearchTree.h:162
 BinarySearchTree.h:163
 BinarySearchTree.h:164
 BinarySearchTree.h:165
 BinarySearchTree.h:166
 BinarySearchTree.h:167
 BinarySearchTree.h:168
 BinarySearchTree.h:169
 BinarySearchTree.h:170
 BinarySearchTree.h:171
 BinarySearchTree.h:172
 BinarySearchTree.h:173
 BinarySearchTree.h:174
 BinarySearchTree.h:175
 BinarySearchTree.h:176
 BinarySearchTree.h:177
 BinarySearchTree.h:178
 BinarySearchTree.h:179
 BinarySearchTree.h:180
 BinarySearchTree.h:181
 BinarySearchTree.h:182
 BinarySearchTree.h:183
 BinarySearchTree.h:184