// @(#)root/tmva $Id$
// Author: Andreas Hoecker, Joerg Stelzer, Helge Voss, Kai Voss, Eckhard von Toerne

/**********************************************************************************
 * Project: TMVA - a Root-integrated toolkit for multivariate data analysis       *
 * Package: TMVA                                                                  *
 * Class  : TMVA::BinaryTree                                                      *
 * Web    : http://tmva.sourceforge.net                                           *
 *                                                                                *
 * Description:                                                                   *
 *      Implementation (see header file for description)                          *
 *                                                                                *
 * Authors (alphabetical):                                                        *
 *      Andreas Hoecker <Andreas.Hocker@cern.ch> - CERN, Switzerland              *
 *      Joerg Stelzer   <stelzer@cern.ch>        - DESY, Germany                  *
 *      Helge Voss      <Helge.Voss@cern.ch>     - MPI-K Heidelberg, Germany      *
 *      Kai Voss        <Kai.Voss@cern.ch>       - U. of Victoria, Canada         *
 *      Eckhard v. Toerne  <evt@uni-bonn.de>          - U of Bonn, Germany        *
 *                                                                                *
 * Copyright (c) 2005-2011:                                                       *
 *      CERN, Switzerland                                                         *
 *      U. of Victoria, Canada                                                    *
 *      MPI-K Heidelberg, Germany                                                 *
 *      U. of Bonn, Germany                                                       *
 *                                                                                *
 * 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)                                          *
 **********************************************************************************/

//////////////////////////////////////////////////////////////////////////
//                                                                      //
// BinaryTree                                                           //
//                                                                      //
// Base class for BinarySearch and Decision Trees                       //
//                                                                      //
//////////////////////////////////////////////////////////////////////////

#include <string>
#include <stdexcept>

#include "TMVA/BinaryTree.h"
#include "TMVA/MsgLogger.h"
#include "TMVA/Event.h"
#include "TMVA/Tools.h"

ClassImp(TMVA::BinaryTree)

//_______________________________________________________________________
TMVA::BinaryTree::BinaryTree( void )
   : fRoot  ( NULL ),
     fNNodes( 0 ),
     fDepth ( 0 )
{
   // constructor for a yet "empty" tree. Needs to be filled afterwards
}

//_______________________________________________________________________
TMVA::BinaryTree::~BinaryTree( void )
{
   //destructor (deletes the nodes and "events" if owned by the tree
   this->DeleteNode( fRoot );
   fRoot=0;
}

//_______________________________________________________________________
void TMVA::BinaryTree::DeleteNode( TMVA::Node* node )
{
   // protected, recursive, function used by the class destructor and when Pruning
   if (node != NULL) { //If the node is not NULL...
      this->DeleteNode(node->GetLeft());  //Delete its left node.
      this->DeleteNode(node->GetRight()); //Delete its right node.

      delete node;                // Delete the node in memory
   }
}

//_______________________________________________________________________
TMVA::Node* TMVA::BinaryTree::GetLeftDaughter( Node *n)
{
   // get left daughter node current node "n"
   return (Node*) n->GetLeft();
}

//_______________________________________________________________________
TMVA::Node* TMVA::BinaryTree::GetRightDaughter( Node *n)
{
   // get right daughter node current node "n"
   return (Node*) n->GetRight();
}

//_______________________________________________________________________
UInt_t TMVA::BinaryTree::CountNodes(TMVA::Node *n)
{
   // return the number of nodes in the tree. (make a new count --> takes time)

   if (n == NULL){ //default, start at the tree top, then descend recursively
      n = (Node*)this->GetRoot();
      if (n == NULL) return 0 ;
   }

   UInt_t countNodes=1;

   if (this->GetLeftDaughter(n) != NULL){
      countNodes += this->CountNodes( this->GetLeftDaughter(n) );
   }
   if (this->GetRightDaughter(n) != NULL) {
      countNodes += this->CountNodes( this->GetRightDaughter(n) );
   }

   return fNNodes = countNodes;
}

//_______________________________________________________________________
void TMVA::BinaryTree::Print(std::ostream & os) const
{
   // recursively print the tree
   this->GetRoot()->PrintRec(os);
   os << "-1" << std::endl;
}

//_______________________________________________________________________
void* TMVA::BinaryTree::AddXMLTo(void* parent) const {
   // add attributes to XML

   void* bdt = gTools().AddChild(parent, "BinaryTree");
   gTools().AddAttr( bdt, "type" , ClassName() );
   this->GetRoot()->AddXMLTo(bdt);
   return bdt;
}

//_______________________________________________________________________
void TMVA::BinaryTree::ReadXML(void* node, UInt_t tmva_Version_Code ) {
   // read attributes from XML

   this->DeleteNode( fRoot );
   fRoot= CreateNode();

   void* trnode = gTools().GetChild(node);
   fRoot->ReadXML(trnode, tmva_Version_Code);

   this->SetTotalTreeDepth();
}


//_______________________________________________________________________
std::ostream& TMVA::operator<< (std::ostream& os, const TMVA::BinaryTree& tree)
{
   // print the tree recursinvely using the << operator
   tree.Print(os);
   return os; // Return the output stream.
}

//_______________________________________________________________________
void TMVA::BinaryTree::Read(std::istream & istr, UInt_t tmva_Version_Code )
{
   // Read the binary tree from an input stream.
   // The input stream format depends on the tree type,
   // it is defined be the node of the tree

   Node * currentNode = GetRoot();
   Node* parent = 0;

   if(currentNode==0) {
      currentNode=CreateNode();
      SetRoot(currentNode);
   }

   while(1) {
      if ( ! currentNode->ReadDataRecord(istr, tmva_Version_Code) ) {
         delete currentNode;
         this->SetTotalTreeDepth();
         return;
      }

      // find parent node
      while( parent!=0 && parent->GetDepth() != currentNode->GetDepth()-1) parent=parent->GetParent();

      if (parent!=0) { // link new node to parent
         currentNode->SetParent(parent);
         if (currentNode->GetPos()=='l') parent->SetLeft(currentNode);
         if (currentNode->GetPos()=='r') parent->SetRight(currentNode);
      }

      parent = currentNode; // latest node read might be parent of new one

      currentNode = CreateNode(); // create a new node to be read next
   }
}

//_______________________________________________________________________
std::istream& TMVA::operator>> (std::istream& istr, TMVA::BinaryTree& tree)
{
   // read the tree from an std::istream
   tree.Read(istr);
   return istr;
}
//_______________________________________________________________________
void TMVA::BinaryTree::SetTotalTreeDepth( Node *n)
{
   // descend a tree to find all its leaf nodes, fill max depth reached in the
   // tree at the same time.

   if (n == NULL){ //default, start at the tree top, then descend recursively
      n = (Node*) this->GetRoot();
      if (n == NULL) {
         Log() << kFATAL << "SetTotalTreeDepth: started with undefined ROOT node" <<Endl;
         return ;
      }
   }
   if (this->GetLeftDaughter(n) != NULL){
      this->SetTotalTreeDepth( this->GetLeftDaughter(n) );
   }
   if (this->GetRightDaughter(n) != NULL) {
      this->SetTotalTreeDepth( this->GetRightDaughter(n) );
   }
   if (n->GetDepth() > this->GetTotalTreeDepth()) this->SetTotalTreeDepth(n->GetDepth());

   return;
}

//_______________________________________________________________________
TMVA::MsgLogger& TMVA::BinaryTree::Log() const {
  TTHREAD_TLS_DECL_ARG(MsgLogger,logger,"BinaryTree");
  return logger;
}
 BinaryTree.cxx:1
 BinaryTree.cxx:2
 BinaryTree.cxx:3
 BinaryTree.cxx:4
 BinaryTree.cxx:5
 BinaryTree.cxx:6
 BinaryTree.cxx:7
 BinaryTree.cxx:8
 BinaryTree.cxx:9
 BinaryTree.cxx:10
 BinaryTree.cxx:11
 BinaryTree.cxx:12
 BinaryTree.cxx:13
 BinaryTree.cxx:14
 BinaryTree.cxx:15
 BinaryTree.cxx:16
 BinaryTree.cxx:17
 BinaryTree.cxx:18
 BinaryTree.cxx:19
 BinaryTree.cxx:20
 BinaryTree.cxx:21
 BinaryTree.cxx:22
 BinaryTree.cxx:23
 BinaryTree.cxx:24
 BinaryTree.cxx:25
 BinaryTree.cxx:26
 BinaryTree.cxx:27
 BinaryTree.cxx:28
 BinaryTree.cxx:29
 BinaryTree.cxx:30
 BinaryTree.cxx:31
 BinaryTree.cxx:32
 BinaryTree.cxx:33
 BinaryTree.cxx:34
 BinaryTree.cxx:35
 BinaryTree.cxx:36
 BinaryTree.cxx:37
 BinaryTree.cxx:38
 BinaryTree.cxx:39
 BinaryTree.cxx:40
 BinaryTree.cxx:41
 BinaryTree.cxx:42
 BinaryTree.cxx:43
 BinaryTree.cxx:44
 BinaryTree.cxx:45
 BinaryTree.cxx:46
 BinaryTree.cxx:47
 BinaryTree.cxx:48
 BinaryTree.cxx:49
 BinaryTree.cxx:50
 BinaryTree.cxx:51
 BinaryTree.cxx:52
 BinaryTree.cxx:53
 BinaryTree.cxx:54
 BinaryTree.cxx:55
 BinaryTree.cxx:56
 BinaryTree.cxx:57
 BinaryTree.cxx:58
 BinaryTree.cxx:59
 BinaryTree.cxx:60
 BinaryTree.cxx:61
 BinaryTree.cxx:62
 BinaryTree.cxx:63
 BinaryTree.cxx:64
 BinaryTree.cxx:65
 BinaryTree.cxx:66
 BinaryTree.cxx:67
 BinaryTree.cxx:68
 BinaryTree.cxx:69
 BinaryTree.cxx:70
 BinaryTree.cxx:71
 BinaryTree.cxx:72
 BinaryTree.cxx:73
 BinaryTree.cxx:74
 BinaryTree.cxx:75
 BinaryTree.cxx:76
 BinaryTree.cxx:77
 BinaryTree.cxx:78
 BinaryTree.cxx:79
 BinaryTree.cxx:80
 BinaryTree.cxx:81
 BinaryTree.cxx:82
 BinaryTree.cxx:83
 BinaryTree.cxx:84
 BinaryTree.cxx:85
 BinaryTree.cxx:86
 BinaryTree.cxx:87
 BinaryTree.cxx:88
 BinaryTree.cxx:89
 BinaryTree.cxx:90
 BinaryTree.cxx:91
 BinaryTree.cxx:92
 BinaryTree.cxx:93
 BinaryTree.cxx:94
 BinaryTree.cxx:95
 BinaryTree.cxx:96
 BinaryTree.cxx:97
 BinaryTree.cxx:98
 BinaryTree.cxx:99
 BinaryTree.cxx:100
 BinaryTree.cxx:101
 BinaryTree.cxx:102
 BinaryTree.cxx:103
 BinaryTree.cxx:104
 BinaryTree.cxx:105
 BinaryTree.cxx:106
 BinaryTree.cxx:107
 BinaryTree.cxx:108
 BinaryTree.cxx:109
 BinaryTree.cxx:110
 BinaryTree.cxx:111
 BinaryTree.cxx:112
 BinaryTree.cxx:113
 BinaryTree.cxx:114
 BinaryTree.cxx:115
 BinaryTree.cxx:116
 BinaryTree.cxx:117
 BinaryTree.cxx:118
 BinaryTree.cxx:119
 BinaryTree.cxx:120
 BinaryTree.cxx:121
 BinaryTree.cxx:122
 BinaryTree.cxx:123
 BinaryTree.cxx:124
 BinaryTree.cxx:125
 BinaryTree.cxx:126
 BinaryTree.cxx:127
 BinaryTree.cxx:128
 BinaryTree.cxx:129
 BinaryTree.cxx:130
 BinaryTree.cxx:131
 BinaryTree.cxx:132
 BinaryTree.cxx:133
 BinaryTree.cxx:134
 BinaryTree.cxx:135
 BinaryTree.cxx:136
 BinaryTree.cxx:137
 BinaryTree.cxx:138
 BinaryTree.cxx:139
 BinaryTree.cxx:140
 BinaryTree.cxx:141
 BinaryTree.cxx:142
 BinaryTree.cxx:143
 BinaryTree.cxx:144
 BinaryTree.cxx:145
 BinaryTree.cxx:146
 BinaryTree.cxx:147
 BinaryTree.cxx:148
 BinaryTree.cxx:149
 BinaryTree.cxx:150
 BinaryTree.cxx:151
 BinaryTree.cxx:152
 BinaryTree.cxx:153
 BinaryTree.cxx:154
 BinaryTree.cxx:155
 BinaryTree.cxx:156
 BinaryTree.cxx:157
 BinaryTree.cxx:158
 BinaryTree.cxx:159
 BinaryTree.cxx:160
 BinaryTree.cxx:161
 BinaryTree.cxx:162
 BinaryTree.cxx:163
 BinaryTree.cxx:164
 BinaryTree.cxx:165
 BinaryTree.cxx:166
 BinaryTree.cxx:167
 BinaryTree.cxx:168
 BinaryTree.cxx:169
 BinaryTree.cxx:170
 BinaryTree.cxx:171
 BinaryTree.cxx:172
 BinaryTree.cxx:173
 BinaryTree.cxx:174
 BinaryTree.cxx:175
 BinaryTree.cxx:176
 BinaryTree.cxx:177
 BinaryTree.cxx:178
 BinaryTree.cxx:179
 BinaryTree.cxx:180
 BinaryTree.cxx:181
 BinaryTree.cxx:182
 BinaryTree.cxx:183
 BinaryTree.cxx:184
 BinaryTree.cxx:185
 BinaryTree.cxx:186
 BinaryTree.cxx:187
 BinaryTree.cxx:188
 BinaryTree.cxx:189
 BinaryTree.cxx:190
 BinaryTree.cxx:191
 BinaryTree.cxx:192
 BinaryTree.cxx:193
 BinaryTree.cxx:194
 BinaryTree.cxx:195
 BinaryTree.cxx:196
 BinaryTree.cxx:197
 BinaryTree.cxx:198
 BinaryTree.cxx:199
 BinaryTree.cxx:200
 BinaryTree.cxx:201
 BinaryTree.cxx:202
 BinaryTree.cxx:203
 BinaryTree.cxx:204
 BinaryTree.cxx:205
 BinaryTree.cxx:206
 BinaryTree.cxx:207
 BinaryTree.cxx:208
 BinaryTree.cxx:209
 BinaryTree.cxx:210
 BinaryTree.cxx:211
 BinaryTree.cxx:212
 BinaryTree.cxx:213
 BinaryTree.cxx:214
 BinaryTree.cxx:215
 BinaryTree.cxx:216
 BinaryTree.cxx:217
 BinaryTree.cxx:218
 BinaryTree.cxx:219
 BinaryTree.cxx:220
 BinaryTree.cxx:221
 BinaryTree.cxx:222
 BinaryTree.cxx:223
 BinaryTree.cxx:224
 BinaryTree.cxx:225
 BinaryTree.cxx:226