// @(#)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:                                                                   *
 *      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         *
 *                                                                                *
 * 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)                                          *
 *                                                                                *
 **********************************************************************************/

//////////////////////////////////////////////////////////////////////////
//                                                                      //
// BinarySearchTree                                                     //
//                                                                      //
// A simple Binary search tree including a volume search method         //
//                                                                      //
//////////////////////////////////////////////////////////////////////////

#include <stdexcept>
#include <cstdlib>
#include <queue>
#include <algorithm>

// #if ROOT_VERSION_CODE >= 364802
// #ifndef ROOT_TMathBase
// #include "TMathBase.h"
// #endif
// #else
// #ifndef ROOT_TMath
#include "TMath.h"
// #endif
// #endif

#include "TMatrixDBase.h"
#include "TObjString.h"
#include "TTree.h"

#ifndef ROOT_TMVA_MsgLogger
#include "TMVA/MsgLogger.h"
#endif
#ifndef ROOT_TMVA_MethodBase
#include "TMVA/MethodBase.h"
#endif
#ifndef ROOT_TMVA_Tools
#include "TMVA/Tools.h"
#endif
#ifndef ROOT_TMVA_Event
#include "TMVA/Event.h"
#endif
#ifndef ROOT_TMVA_BinarySearchTree
#include "TMVA/BinarySearchTree.h"
#endif

ClassImp(TMVA::BinarySearchTree)

//_______________________________________________________________________
TMVA::BinarySearchTree::BinarySearchTree( void ) :
   BinaryTree(),
   fPeriod      ( 1 ),
   fCurrentDepth( 0 ),
   fStatisticsIsValid( kFALSE ),
   fSumOfWeights( 0 ),
   fCanNormalize( kFALSE )
{
   // default constructor
   fNEventsW[0]=fNEventsW[1]=0.;
}

//_______________________________________________________________________
TMVA::BinarySearchTree::BinarySearchTree( const BinarySearchTree &b)
   : BinaryTree(), 
     fPeriod      ( b.fPeriod ),
     fCurrentDepth( 0 ),
     fStatisticsIsValid( kFALSE ),
     fSumOfWeights( b.fSumOfWeights ),
     fCanNormalize( kFALSE )
{
   // copy constructor that creates a true copy, i.e. a completely independent tree 
   fNEventsW[0]=fNEventsW[1]=0.;
   Log() << kFATAL << " Copy constructor not implemented yet " << Endl;
}

//_______________________________________________________________________
TMVA::BinarySearchTree::~BinarySearchTree( void ) 
{
   // destructor

   for(std::vector< std::pair<Double_t, const TMVA::Event*> >::iterator pIt = fNormalizeTreeTable.begin();
       pIt != fNormalizeTreeTable.end(); pIt++) {
      delete pIt->second;
   }
}

//_______________________________________________________________________
TMVA::BinarySearchTree* TMVA::BinarySearchTree::CreateFromXML(void* node, UInt_t tmva_Version_Code ) {
   // re-create a new tree (decision tree or search tree) from XML
   std::string type("");
   gTools().ReadAttr(node,"type", type);
   BinarySearchTree* bt = new BinarySearchTree();
   bt->ReadXML( node, tmva_Version_Code );
   return bt;
}

//_______________________________________________________________________
void TMVA::BinarySearchTree::Insert( const Event* event ) 
{
   // insert a new "event" in the binary tree
   fCurrentDepth=0;
   fStatisticsIsValid = kFALSE;

   if (this->GetRoot() == NULL) {           // If the list is empty...
      this->SetRoot( new BinarySearchTreeNode(event)); //Make the new node the root.
      // have to use "s" for start as "r" for "root" would be the same as "r" for "right"
      this->GetRoot()->SetPos('s'); 
      this->GetRoot()->SetDepth(0);
      fNNodes = 1;
      fSumOfWeights = event->GetWeight();
      ((BinarySearchTreeNode*)this->GetRoot())->SetSelector((UInt_t)0);
      this->SetPeriode(event->GetNVariables());
   }
   else {
      // sanity check:
      if (event->GetNVariables() != (UInt_t)this->GetPeriode()) {
         Log() << kFATAL << "<Insert> event vector length != Periode specified in Binary Tree" << Endl
               << "--- event size: " << event->GetNVariables() << " Periode: " << this->GetPeriode() << Endl
               << "--- and all this when trying filling the "<<fNNodes+1<<"th Node" << Endl;
      }
      // insert a new node at the propper position  
      this->Insert(event, this->GetRoot()); 
   }

   // normalise the tree to speed up searches
   if (fCanNormalize) fNormalizeTreeTable.push_back( std::make_pair(0.0,new const Event(*event)) );
}

//_______________________________________________________________________
void TMVA::BinarySearchTree::Insert( const Event *event, 
                                     Node *node ) 
{
   // private internal function to insert a event (node) at the proper position
   fCurrentDepth++;
   fStatisticsIsValid = kFALSE;

   if (node->GoesLeft(*event)){    // If the adding item is less than the current node's data...
      if (node->GetLeft() != NULL){            // If there is a left node...
         // Add the new event to the left node
         this->Insert(event, node->GetLeft());
      } 
      else {                             // If there is not a left node...
         // Make the new node for the new event
         BinarySearchTreeNode* current = new BinarySearchTreeNode(event); 
         fNNodes++;
         fSumOfWeights += event->GetWeight();
         current->SetSelector(fCurrentDepth%((Int_t)event->GetNVariables()));
         current->SetParent(node);          // Set the new node's previous node.
         current->SetPos('l');
         current->SetDepth( node->GetDepth() + 1 );
         node->SetLeft(current);            // Make it the left node of the current one.
      }  
   } 
   else if (node->GoesRight(*event)) { // If the adding item is less than or equal to the current node's data...
      if (node->GetRight() != NULL) {              // If there is a right node...
         // Add the new node to it.
         this->Insert(event, node->GetRight()); 
      } 
      else {                                 // If there is not a right node...
         // Make the new node.
         BinarySearchTreeNode* current = new BinarySearchTreeNode(event);   
         fNNodes++;
         fSumOfWeights += event->GetWeight();
         current->SetSelector(fCurrentDepth%((Int_t)event->GetNVariables()));
         current->SetParent(node);              // Set the new node's previous node.
         current->SetPos('r');
         current->SetDepth( node->GetDepth() + 1 );
         node->SetRight(current);               // Make it the left node of the current one.
      }
   } 
   else Log() << kFATAL << "<Insert> neither left nor right :)" << Endl;
}

//_______________________________________________________________________
TMVA::BinarySearchTreeNode* TMVA::BinarySearchTree::Search( Event* event ) const 
{ 
   //search the tree to find the node matching "event"
   return this->Search( event, this->GetRoot() );
}

//_______________________________________________________________________
TMVA::BinarySearchTreeNode* TMVA::BinarySearchTree::Search(Event* event, Node* node) const 
{ 
   // Private, recursive, function for searching.
   if (node != NULL) {               // If the node is not NULL...
      // If we have found the node...
      if (((BinarySearchTreeNode*)(node))->EqualsMe(*event)) 
         return (BinarySearchTreeNode*)node;                  // Return it
      if (node->GoesLeft(*event))      // If the node's data is greater than the search item...
         return this->Search(event, node->GetLeft());  //Search the left node.
      else                          //If the node's data is less than the search item...
         return this->Search(event, node->GetRight()); //Search the right node.
   }
   else return NULL; //If the node is NULL, return NULL.
}

//_______________________________________________________________________
Double_t TMVA::BinarySearchTree::GetSumOfWeights( void ) const
{
   //return the sum of event (node) weights
   if (fSumOfWeights <= 0) {
      Log() << kWARNING << "you asked for the SumOfWeights, which is not filled yet"
            << " I call CalcStatistics which hopefully fixes things" 
            << Endl;
   }
   if (fSumOfWeights <= 0) Log() << kFATAL << " Zero events in your Search Tree" <<Endl;

   return fSumOfWeights;
}

//_______________________________________________________________________
Double_t TMVA::BinarySearchTree::GetSumOfWeights( Int_t theType ) const
{
   //return the sum of event (node) weights
   if (fSumOfWeights <= 0) {
      Log() << kWARNING << "you asked for the SumOfWeights, which is not filled yet"
              << " I call CalcStatistics which hopefully fixes things" 
              << Endl;
   }
   if (fSumOfWeights <= 0) Log() << kFATAL << " Zero events in your Search Tree" <<Endl;

   return fNEventsW[ ( theType == Types::kSignal) ? 0 : 1  ];
}

//_______________________________________________________________________
Double_t TMVA::BinarySearchTree::Fill( const std::vector<Event*>& events, const std::vector<Int_t>& theVars, 
                                       Int_t theType )
{
   // create the search tree from the event collection 
   // using ONLY the variables specified in "theVars"
   fPeriod = theVars.size();
   return Fill(events, theType);
}

//_______________________________________________________________________
Double_t TMVA::BinarySearchTree::Fill( const std::vector<Event*>& events, Int_t theType )
{
   // create the search tree from the events in a TTree
   // using ALL the variables specified included in the Event
   UInt_t n=events.size();
  
   UInt_t nevents = 0;
   if (fSumOfWeights != 0) {
      Log() << kWARNING 
              << "You are filling a search three that is not empty.. "
              << " do you know what you are doing?"
              << Endl;
   }
   for (UInt_t ievt=0; ievt<n; ievt++) {
      // insert event into binary tree
      if (theType == -1 || (Int_t(events[ievt]->GetClass()) == theType) ) {
         this->Insert( events[ievt] );
         nevents++;
         fSumOfWeights += events[ievt]->GetWeight();
      }
   } // end of event loop
   CalcStatistics(0);

   return fSumOfWeights;
}

//_______________________________________________________________________
void TMVA::BinarySearchTree::NormalizeTree ( std::vector< std::pair<Double_t, const TMVA::Event*> >::iterator leftBound, 
                                             std::vector< std::pair<Double_t, const TMVA::Event*> >::iterator rightBound, 
                                             UInt_t actDim )
{

   // normalises the binary-search tree to reduce the branch length and hence speed up the 
   // search procedure (on average)
   if (leftBound == rightBound) return;
   
   if (actDim == fPeriod)  actDim = 0;
   for (std::vector< std::pair<Double_t, const TMVA::Event*> >::iterator i=leftBound; i!=rightBound; i++) {
      i->first = i->second->GetValue( actDim );
   }
   
   std::sort( leftBound, rightBound );
   
   std::vector< std::pair<Double_t, const TMVA::Event*> >::iterator leftTemp  = leftBound;
   std::vector< std::pair<Double_t, const TMVA::Event*> >::iterator rightTemp = rightBound;
  
   // meet in the middle
   while (true) {
      rightTemp--; 
      if (rightTemp == leftTemp ) {
         break;
      }
      leftTemp++;  
      if (leftTemp  == rightTemp) {
         break;
      }
   }
  
   std::vector< std::pair<Double_t, const TMVA::Event*> >::iterator mid     = leftTemp;
   std::vector< std::pair<Double_t, const TMVA::Event*> >::iterator midTemp = mid;

   if (mid!=leftBound) midTemp--;

   while (mid != leftBound && mid->second->GetValue( actDim ) == midTemp->second->GetValue( actDim ))  {
      mid--; 
      midTemp--;
   }

   Insert( mid->second );

   //    Print(std::cout);
   //    std::cout << std::endl << std::endl;

   NormalizeTree( leftBound, mid, actDim+1 );
   mid++;
   //    Print(std::cout);
   //    std::cout << std::endl << std::endl;
   NormalizeTree( mid, rightBound, actDim+1 );


   return;  
}

//_______________________________________________________________________
void TMVA::BinarySearchTree::NormalizeTree()
{
   // Normalisation of tree
   SetNormalize( kFALSE );
   Clear( NULL );
   this->SetRoot(NULL);
   NormalizeTree( fNormalizeTreeTable.begin(), fNormalizeTreeTable.end(), 0 ); 
}

//_______________________________________________________________________
void TMVA::BinarySearchTree::Clear( Node* n )
{
   // clear nodes
   BinarySearchTreeNode* currentNode = (BinarySearchTreeNode*)(n == NULL ? this->GetRoot() : n);

   if (currentNode->GetLeft()  != 0) Clear( currentNode->GetLeft()  );
   if (currentNode->GetRight() != 0) Clear( currentNode->GetRight() );
   
   if (n != NULL) delete n;

   return;
}

//_______________________________________________________________________
Double_t TMVA::BinarySearchTree::SearchVolume( Volume* volume, 
                                               std::vector<const BinarySearchTreeNode*>* events )
{
   // search the whole tree and add up all weigths of events that 
   // lie within the given voluem
   return SearchVolume( this->GetRoot(), volume, 0, events );
}

//_______________________________________________________________________
Double_t TMVA::BinarySearchTree::SearchVolume( Node* t, Volume* volume, Int_t depth, 
                                               std::vector<const BinarySearchTreeNode*>* events )
{
   // recursively walk through the daughter nodes and add up all weigths of events that 
   // lie within the given volume

   if (t==NULL) return 0;  // Are we at an outer leave?
   
   BinarySearchTreeNode* st = (BinarySearchTreeNode*)t;

   Double_t count = 0.0;
   if (InVolume( st->GetEventV(), volume )) {
      count += st->GetWeight();
      if (NULL != events) events->push_back( st );
   }
   if (st->GetLeft()==NULL && st->GetRight()==NULL) {
      
      return count;  // Are we at an outer leave?
   }

   Bool_t tl, tr;
   Int_t  d = depth%this->GetPeriode();
   if (d != st->GetSelector()) {
      Log() << kFATAL << "<SearchVolume> selector in Searchvolume " 
              << d << " != " << "node "<< st->GetSelector() << Endl;
   }
   tl = (*(volume->fLower))[d] <  st->GetEventV()[d];  // Should we descend left?
   tr = (*(volume->fUpper))[d] >= st->GetEventV()[d];  // Should we descend right?

   if (tl) count += SearchVolume( st->GetLeft(),  volume, (depth+1), events );
   if (tr) count += SearchVolume( st->GetRight(), volume, (depth+1), events );

   return count;
}

Bool_t TMVA::BinarySearchTree::InVolume(const std::vector<Float_t>& event, Volume* volume ) const 
{
   // test if the data points are in the given volume

   Bool_t result = false;
   for (UInt_t ivar=0; ivar< fPeriod; ivar++) {
      result = ( (*(volume->fLower))[ivar] <  event[ivar] &&
                 (*(volume->fUpper))[ivar] >= event[ivar] );
      if (!result) break;
   }
   return result;
}

//_______________________________________________________________________
void TMVA::BinarySearchTree::CalcStatistics( Node* n )
{
   // calculate basic statistics (mean, rms for each variable)
   if (fStatisticsIsValid) return;

   BinarySearchTreeNode * currentNode = (BinarySearchTreeNode*)n;

   // default, start at the tree top, then descend recursively
   if (n == NULL) {
      fSumOfWeights = 0;
      for (Int_t sb=0; sb<2; sb++) {
         fNEventsW[sb]  = 0;
         fMeans[sb]     = std::vector<Float_t>(fPeriod);
         fRMS[sb]       = std::vector<Float_t>(fPeriod);
         fMin[sb]       = std::vector<Float_t>(fPeriod);
         fMax[sb]       = std::vector<Float_t>(fPeriod);
         fSum[sb]       = std::vector<Double_t>(fPeriod);
         fSumSq[sb]     = std::vector<Double_t>(fPeriod);
         for (UInt_t j=0; j<fPeriod; j++) {
            fMeans[sb][j] = fRMS[sb][j] = fSum[sb][j] = fSumSq[sb][j] = 0;
            fMin[sb][j] =  FLT_MAX;
            fMax[sb][j] = -FLT_MAX; 
         }
      }
      currentNode = (BinarySearchTreeNode*) this->GetRoot();
      if (currentNode == NULL) return; // no root-node
   }
      
   const std::vector<Float_t> & evtVec = currentNode->GetEventV();
   Double_t                     weight = currentNode->GetWeight();
//    Int_t                        type   = currentNode->IsSignal(); 
//   Int_t                        type   = currentNode->IsSignal() ? 0 : 1; 
   Int_t                        type   = Int_t(currentNode->GetClass())== Types::kSignal ? 0 : 1; 

   fNEventsW[type] += weight;
   fSumOfWeights   += weight;

   for (UInt_t j=0; j<fPeriod; j++) {
      Float_t val = evtVec[j];
      fSum[type][j]   += val*weight;
      fSumSq[type][j] += val*val*weight;
      if (val < fMin[type][j]) fMin[type][j] = val; 
      if (val > fMax[type][j]) fMax[type][j] = val; 
   }
   
   if ( (currentNode->GetLeft()  != NULL) ) CalcStatistics( currentNode->GetLeft() ); 
   if ( (currentNode->GetRight() != NULL) ) CalcStatistics( currentNode->GetRight() ); 

   if (n == NULL) { // i.e. the root node
      for (Int_t sb=0; sb<2; sb++) {
         for (UInt_t j=0; j<fPeriod; j++) {
            if (fNEventsW[sb] == 0) { fMeans[sb][j] = fRMS[sb][j] = 0; continue; }
            fMeans[sb][j] = fSum[sb][j]/fNEventsW[sb];
            fRMS[sb][j]   = TMath::Sqrt(fSumSq[sb][j]/fNEventsW[sb] - fMeans[sb][j]*fMeans[sb][j]);
         }
      }
      fStatisticsIsValid = kTRUE;
   }
   
   return;
}

Int_t TMVA::BinarySearchTree::SearchVolumeWithMaxLimit( Volume *volume, std::vector<const BinarySearchTreeNode*>* events,
                                                        Int_t max_points )
{
   // recursively walk through the daughter nodes and add up all weigths of events that 
   // lie within the given volume a maximum number of events can be given
   if (this->GetRoot() == NULL) return 0;  // Are we at an outer leave?

   std::queue< std::pair< const BinarySearchTreeNode*, Int_t > > queue;
   std::pair< const BinarySearchTreeNode*, Int_t > st = std::make_pair( (const BinarySearchTreeNode*)this->GetRoot(), 0 );
   queue.push( st );

   Int_t count = 0;
   
   while ( !queue.empty() ) {
      st = queue.front(); queue.pop();
      
      if (count == max_points)
         return count;

      if (InVolume( st.first->GetEventV(), volume )) {
         count++;
         if (NULL != events) events->push_back( st.first );
      }

      Bool_t tl, tr;
      Int_t d = st.second;
      if ( d == Int_t(this->GetPeriode()) ) d = 0;

      if (d != st.first->GetSelector()) {
         Log() << kFATAL << "<SearchVolume> selector in Searchvolume "
                 << d << " != " << "node "<< st.first->GetSelector() << Endl;
      }

      tl = (*(volume->fLower))[d] <  st.first->GetEventV()[d] && st.first->GetLeft()  != NULL;  // Should we descend left?
      tr = (*(volume->fUpper))[d] >= st.first->GetEventV()[d] && st.first->GetRight() != NULL;  // Should we descend right?

      if (tl) queue.push( std::make_pair( (const BinarySearchTreeNode*)st.first->GetLeft(), d+1 ) );
      if (tr) queue.push( std::make_pair( (const BinarySearchTreeNode*)st.first->GetRight(), d+1 ) );
   }

   return count;
}
 BinarySearchTree.cxx:1
 BinarySearchTree.cxx:2
 BinarySearchTree.cxx:3
 BinarySearchTree.cxx:4
 BinarySearchTree.cxx:5
 BinarySearchTree.cxx:6
 BinarySearchTree.cxx:7
 BinarySearchTree.cxx:8
 BinarySearchTree.cxx:9
 BinarySearchTree.cxx:10
 BinarySearchTree.cxx:11
 BinarySearchTree.cxx:12
 BinarySearchTree.cxx:13
 BinarySearchTree.cxx:14
 BinarySearchTree.cxx:15
 BinarySearchTree.cxx:16
 BinarySearchTree.cxx:17
 BinarySearchTree.cxx:18
 BinarySearchTree.cxx:19
 BinarySearchTree.cxx:20
 BinarySearchTree.cxx:21
 BinarySearchTree.cxx:22
 BinarySearchTree.cxx:23
 BinarySearchTree.cxx:24
 BinarySearchTree.cxx:25
 BinarySearchTree.cxx:26
 BinarySearchTree.cxx:27
 BinarySearchTree.cxx:28
 BinarySearchTree.cxx:29
 BinarySearchTree.cxx:30
 BinarySearchTree.cxx:31
 BinarySearchTree.cxx:32
 BinarySearchTree.cxx:33
 BinarySearchTree.cxx:34
 BinarySearchTree.cxx:35
 BinarySearchTree.cxx:36
 BinarySearchTree.cxx:37
 BinarySearchTree.cxx:38
 BinarySearchTree.cxx:39
 BinarySearchTree.cxx:40
 BinarySearchTree.cxx:41
 BinarySearchTree.cxx:42
 BinarySearchTree.cxx:43
 BinarySearchTree.cxx:44
 BinarySearchTree.cxx:45
 BinarySearchTree.cxx:46
 BinarySearchTree.cxx:47
 BinarySearchTree.cxx:48
 BinarySearchTree.cxx:49
 BinarySearchTree.cxx:50
 BinarySearchTree.cxx:51
 BinarySearchTree.cxx:52
 BinarySearchTree.cxx:53
 BinarySearchTree.cxx:54
 BinarySearchTree.cxx:55
 BinarySearchTree.cxx:56
 BinarySearchTree.cxx:57
 BinarySearchTree.cxx:58
 BinarySearchTree.cxx:59
 BinarySearchTree.cxx:60
 BinarySearchTree.cxx:61
 BinarySearchTree.cxx:62
 BinarySearchTree.cxx:63
 BinarySearchTree.cxx:64
 BinarySearchTree.cxx:65
 BinarySearchTree.cxx:66
 BinarySearchTree.cxx:67
 BinarySearchTree.cxx:68
 BinarySearchTree.cxx:69
 BinarySearchTree.cxx:70
 BinarySearchTree.cxx:71
 BinarySearchTree.cxx:72
 BinarySearchTree.cxx:73
 BinarySearchTree.cxx:74
 BinarySearchTree.cxx:75
 BinarySearchTree.cxx:76
 BinarySearchTree.cxx:77
 BinarySearchTree.cxx:78
 BinarySearchTree.cxx:79
 BinarySearchTree.cxx:80
 BinarySearchTree.cxx:81
 BinarySearchTree.cxx:82
 BinarySearchTree.cxx:83
 BinarySearchTree.cxx:84
 BinarySearchTree.cxx:85
 BinarySearchTree.cxx:86
 BinarySearchTree.cxx:87
 BinarySearchTree.cxx:88
 BinarySearchTree.cxx:89
 BinarySearchTree.cxx:90
 BinarySearchTree.cxx:91
 BinarySearchTree.cxx:92
 BinarySearchTree.cxx:93
 BinarySearchTree.cxx:94
 BinarySearchTree.cxx:95
 BinarySearchTree.cxx:96
 BinarySearchTree.cxx:97
 BinarySearchTree.cxx:98
 BinarySearchTree.cxx:99
 BinarySearchTree.cxx:100
 BinarySearchTree.cxx:101
 BinarySearchTree.cxx:102
 BinarySearchTree.cxx:103
 BinarySearchTree.cxx:104
 BinarySearchTree.cxx:105
 BinarySearchTree.cxx:106
 BinarySearchTree.cxx:107
 BinarySearchTree.cxx:108
 BinarySearchTree.cxx:109
 BinarySearchTree.cxx:110
 BinarySearchTree.cxx:111
 BinarySearchTree.cxx:112
 BinarySearchTree.cxx:113
 BinarySearchTree.cxx:114
 BinarySearchTree.cxx:115
 BinarySearchTree.cxx:116
 BinarySearchTree.cxx:117
 BinarySearchTree.cxx:118
 BinarySearchTree.cxx:119
 BinarySearchTree.cxx:120
 BinarySearchTree.cxx:121
 BinarySearchTree.cxx:122
 BinarySearchTree.cxx:123
 BinarySearchTree.cxx:124
 BinarySearchTree.cxx:125
 BinarySearchTree.cxx:126
 BinarySearchTree.cxx:127
 BinarySearchTree.cxx:128
 BinarySearchTree.cxx:129
 BinarySearchTree.cxx:130
 BinarySearchTree.cxx:131
 BinarySearchTree.cxx:132
 BinarySearchTree.cxx:133
 BinarySearchTree.cxx:134
 BinarySearchTree.cxx:135
 BinarySearchTree.cxx:136
 BinarySearchTree.cxx:137
 BinarySearchTree.cxx:138
 BinarySearchTree.cxx:139
 BinarySearchTree.cxx:140
 BinarySearchTree.cxx:141
 BinarySearchTree.cxx:142
 BinarySearchTree.cxx:143
 BinarySearchTree.cxx:144
 BinarySearchTree.cxx:145
 BinarySearchTree.cxx:146
 BinarySearchTree.cxx:147
 BinarySearchTree.cxx:148
 BinarySearchTree.cxx:149
 BinarySearchTree.cxx:150
 BinarySearchTree.cxx:151
 BinarySearchTree.cxx:152
 BinarySearchTree.cxx:153
 BinarySearchTree.cxx:154
 BinarySearchTree.cxx:155
 BinarySearchTree.cxx:156
 BinarySearchTree.cxx:157
 BinarySearchTree.cxx:158
 BinarySearchTree.cxx:159
 BinarySearchTree.cxx:160
 BinarySearchTree.cxx:161
 BinarySearchTree.cxx:162
 BinarySearchTree.cxx:163
 BinarySearchTree.cxx:164
 BinarySearchTree.cxx:165
 BinarySearchTree.cxx:166
 BinarySearchTree.cxx:167
 BinarySearchTree.cxx:168
 BinarySearchTree.cxx:169
 BinarySearchTree.cxx:170
 BinarySearchTree.cxx:171
 BinarySearchTree.cxx:172
 BinarySearchTree.cxx:173
 BinarySearchTree.cxx:174
 BinarySearchTree.cxx:175
 BinarySearchTree.cxx:176
 BinarySearchTree.cxx:177
 BinarySearchTree.cxx:178
 BinarySearchTree.cxx:179
 BinarySearchTree.cxx:180
 BinarySearchTree.cxx:181
 BinarySearchTree.cxx:182
 BinarySearchTree.cxx:183
 BinarySearchTree.cxx:184
 BinarySearchTree.cxx:185
 BinarySearchTree.cxx:186
 BinarySearchTree.cxx:187
 BinarySearchTree.cxx:188
 BinarySearchTree.cxx:189
 BinarySearchTree.cxx:190
 BinarySearchTree.cxx:191
 BinarySearchTree.cxx:192
 BinarySearchTree.cxx:193
 BinarySearchTree.cxx:194
 BinarySearchTree.cxx:195
 BinarySearchTree.cxx:196
 BinarySearchTree.cxx:197
 BinarySearchTree.cxx:198
 BinarySearchTree.cxx:199
 BinarySearchTree.cxx:200
 BinarySearchTree.cxx:201
 BinarySearchTree.cxx:202
 BinarySearchTree.cxx:203
 BinarySearchTree.cxx:204
 BinarySearchTree.cxx:205
 BinarySearchTree.cxx:206
 BinarySearchTree.cxx:207
 BinarySearchTree.cxx:208
 BinarySearchTree.cxx:209
 BinarySearchTree.cxx:210
 BinarySearchTree.cxx:211
 BinarySearchTree.cxx:212
 BinarySearchTree.cxx:213
 BinarySearchTree.cxx:214
 BinarySearchTree.cxx:215
 BinarySearchTree.cxx:216
 BinarySearchTree.cxx:217
 BinarySearchTree.cxx:218
 BinarySearchTree.cxx:219
 BinarySearchTree.cxx:220
 BinarySearchTree.cxx:221
 BinarySearchTree.cxx:222
 BinarySearchTree.cxx:223
 BinarySearchTree.cxx:224
 BinarySearchTree.cxx:225
 BinarySearchTree.cxx:226
 BinarySearchTree.cxx:227
 BinarySearchTree.cxx:228
 BinarySearchTree.cxx:229
 BinarySearchTree.cxx:230
 BinarySearchTree.cxx:231
 BinarySearchTree.cxx:232
 BinarySearchTree.cxx:233
 BinarySearchTree.cxx:234
 BinarySearchTree.cxx:235
 BinarySearchTree.cxx:236
 BinarySearchTree.cxx:237
 BinarySearchTree.cxx:238
 BinarySearchTree.cxx:239
 BinarySearchTree.cxx:240
 BinarySearchTree.cxx:241
 BinarySearchTree.cxx:242
 BinarySearchTree.cxx:243
 BinarySearchTree.cxx:244
 BinarySearchTree.cxx:245
 BinarySearchTree.cxx:246
 BinarySearchTree.cxx:247
 BinarySearchTree.cxx:248
 BinarySearchTree.cxx:249
 BinarySearchTree.cxx:250
 BinarySearchTree.cxx:251
 BinarySearchTree.cxx:252
 BinarySearchTree.cxx:253
 BinarySearchTree.cxx:254
 BinarySearchTree.cxx:255
 BinarySearchTree.cxx:256
 BinarySearchTree.cxx:257
 BinarySearchTree.cxx:258
 BinarySearchTree.cxx:259
 BinarySearchTree.cxx:260
 BinarySearchTree.cxx:261
 BinarySearchTree.cxx:262
 BinarySearchTree.cxx:263
 BinarySearchTree.cxx:264
 BinarySearchTree.cxx:265
 BinarySearchTree.cxx:266
 BinarySearchTree.cxx:267
 BinarySearchTree.cxx:268
 BinarySearchTree.cxx:269
 BinarySearchTree.cxx:270
 BinarySearchTree.cxx:271
 BinarySearchTree.cxx:272
 BinarySearchTree.cxx:273
 BinarySearchTree.cxx:274
 BinarySearchTree.cxx:275
 BinarySearchTree.cxx:276
 BinarySearchTree.cxx:277
 BinarySearchTree.cxx:278
 BinarySearchTree.cxx:279
 BinarySearchTree.cxx:280
 BinarySearchTree.cxx:281
 BinarySearchTree.cxx:282
 BinarySearchTree.cxx:283
 BinarySearchTree.cxx:284
 BinarySearchTree.cxx:285
 BinarySearchTree.cxx:286
 BinarySearchTree.cxx:287
 BinarySearchTree.cxx:288
 BinarySearchTree.cxx:289
 BinarySearchTree.cxx:290
 BinarySearchTree.cxx:291
 BinarySearchTree.cxx:292
 BinarySearchTree.cxx:293
 BinarySearchTree.cxx:294
 BinarySearchTree.cxx:295
 BinarySearchTree.cxx:296
 BinarySearchTree.cxx:297
 BinarySearchTree.cxx:298
 BinarySearchTree.cxx:299
 BinarySearchTree.cxx:300
 BinarySearchTree.cxx:301
 BinarySearchTree.cxx:302
 BinarySearchTree.cxx:303
 BinarySearchTree.cxx:304
 BinarySearchTree.cxx:305
 BinarySearchTree.cxx:306
 BinarySearchTree.cxx:307
 BinarySearchTree.cxx:308
 BinarySearchTree.cxx:309
 BinarySearchTree.cxx:310
 BinarySearchTree.cxx:311
 BinarySearchTree.cxx:312
 BinarySearchTree.cxx:313
 BinarySearchTree.cxx:314
 BinarySearchTree.cxx:315
 BinarySearchTree.cxx:316
 BinarySearchTree.cxx:317
 BinarySearchTree.cxx:318
 BinarySearchTree.cxx:319
 BinarySearchTree.cxx:320
 BinarySearchTree.cxx:321
 BinarySearchTree.cxx:322
 BinarySearchTree.cxx:323
 BinarySearchTree.cxx:324
 BinarySearchTree.cxx:325
 BinarySearchTree.cxx:326
 BinarySearchTree.cxx:327
 BinarySearchTree.cxx:328
 BinarySearchTree.cxx:329
 BinarySearchTree.cxx:330
 BinarySearchTree.cxx:331
 BinarySearchTree.cxx:332
 BinarySearchTree.cxx:333
 BinarySearchTree.cxx:334
 BinarySearchTree.cxx:335
 BinarySearchTree.cxx:336
 BinarySearchTree.cxx:337
 BinarySearchTree.cxx:338
 BinarySearchTree.cxx:339
 BinarySearchTree.cxx:340
 BinarySearchTree.cxx:341
 BinarySearchTree.cxx:342
 BinarySearchTree.cxx:343
 BinarySearchTree.cxx:344
 BinarySearchTree.cxx:345
 BinarySearchTree.cxx:346
 BinarySearchTree.cxx:347
 BinarySearchTree.cxx:348
 BinarySearchTree.cxx:349
 BinarySearchTree.cxx:350
 BinarySearchTree.cxx:351
 BinarySearchTree.cxx:352
 BinarySearchTree.cxx:353
 BinarySearchTree.cxx:354
 BinarySearchTree.cxx:355
 BinarySearchTree.cxx:356
 BinarySearchTree.cxx:357
 BinarySearchTree.cxx:358
 BinarySearchTree.cxx:359
 BinarySearchTree.cxx:360
 BinarySearchTree.cxx:361
 BinarySearchTree.cxx:362
 BinarySearchTree.cxx:363
 BinarySearchTree.cxx:364
 BinarySearchTree.cxx:365
 BinarySearchTree.cxx:366
 BinarySearchTree.cxx:367
 BinarySearchTree.cxx:368
 BinarySearchTree.cxx:369
 BinarySearchTree.cxx:370
 BinarySearchTree.cxx:371
 BinarySearchTree.cxx:372
 BinarySearchTree.cxx:373
 BinarySearchTree.cxx:374
 BinarySearchTree.cxx:375
 BinarySearchTree.cxx:376
 BinarySearchTree.cxx:377
 BinarySearchTree.cxx:378
 BinarySearchTree.cxx:379
 BinarySearchTree.cxx:380
 BinarySearchTree.cxx:381
 BinarySearchTree.cxx:382
 BinarySearchTree.cxx:383
 BinarySearchTree.cxx:384
 BinarySearchTree.cxx:385
 BinarySearchTree.cxx:386
 BinarySearchTree.cxx:387
 BinarySearchTree.cxx:388
 BinarySearchTree.cxx:389
 BinarySearchTree.cxx:390
 BinarySearchTree.cxx:391
 BinarySearchTree.cxx:392
 BinarySearchTree.cxx:393
 BinarySearchTree.cxx:394
 BinarySearchTree.cxx:395
 BinarySearchTree.cxx:396
 BinarySearchTree.cxx:397
 BinarySearchTree.cxx:398
 BinarySearchTree.cxx:399
 BinarySearchTree.cxx:400
 BinarySearchTree.cxx:401
 BinarySearchTree.cxx:402
 BinarySearchTree.cxx:403
 BinarySearchTree.cxx:404
 BinarySearchTree.cxx:405
 BinarySearchTree.cxx:406
 BinarySearchTree.cxx:407
 BinarySearchTree.cxx:408
 BinarySearchTree.cxx:409
 BinarySearchTree.cxx:410
 BinarySearchTree.cxx:411
 BinarySearchTree.cxx:412
 BinarySearchTree.cxx:413
 BinarySearchTree.cxx:414
 BinarySearchTree.cxx:415
 BinarySearchTree.cxx:416
 BinarySearchTree.cxx:417
 BinarySearchTree.cxx:418
 BinarySearchTree.cxx:419
 BinarySearchTree.cxx:420
 BinarySearchTree.cxx:421
 BinarySearchTree.cxx:422
 BinarySearchTree.cxx:423
 BinarySearchTree.cxx:424
 BinarySearchTree.cxx:425
 BinarySearchTree.cxx:426
 BinarySearchTree.cxx:427
 BinarySearchTree.cxx:428
 BinarySearchTree.cxx:429
 BinarySearchTree.cxx:430
 BinarySearchTree.cxx:431
 BinarySearchTree.cxx:432
 BinarySearchTree.cxx:433
 BinarySearchTree.cxx:434
 BinarySearchTree.cxx:435
 BinarySearchTree.cxx:436
 BinarySearchTree.cxx:437
 BinarySearchTree.cxx:438
 BinarySearchTree.cxx:439
 BinarySearchTree.cxx:440
 BinarySearchTree.cxx:441
 BinarySearchTree.cxx:442
 BinarySearchTree.cxx:443
 BinarySearchTree.cxx:444
 BinarySearchTree.cxx:445
 BinarySearchTree.cxx:446
 BinarySearchTree.cxx:447
 BinarySearchTree.cxx:448
 BinarySearchTree.cxx:449
 BinarySearchTree.cxx:450
 BinarySearchTree.cxx:451
 BinarySearchTree.cxx:452
 BinarySearchTree.cxx:453
 BinarySearchTree.cxx:454
 BinarySearchTree.cxx:455
 BinarySearchTree.cxx:456
 BinarySearchTree.cxx:457
 BinarySearchTree.cxx:458
 BinarySearchTree.cxx:459
 BinarySearchTree.cxx:460
 BinarySearchTree.cxx:461
 BinarySearchTree.cxx:462
 BinarySearchTree.cxx:463
 BinarySearchTree.cxx:464
 BinarySearchTree.cxx:465
 BinarySearchTree.cxx:466
 BinarySearchTree.cxx:467
 BinarySearchTree.cxx:468
 BinarySearchTree.cxx:469
 BinarySearchTree.cxx:470
 BinarySearchTree.cxx:471
 BinarySearchTree.cxx:472
 BinarySearchTree.cxx:473
 BinarySearchTree.cxx:474
 BinarySearchTree.cxx:475
 BinarySearchTree.cxx:476
 BinarySearchTree.cxx:477
 BinarySearchTree.cxx:478
 BinarySearchTree.cxx:479
 BinarySearchTree.cxx:480
 BinarySearchTree.cxx:481
 BinarySearchTree.cxx:482
 BinarySearchTree.cxx:483
 BinarySearchTree.cxx:484
 BinarySearchTree.cxx:485
 BinarySearchTree.cxx:486
 BinarySearchTree.cxx:487
 BinarySearchTree.cxx:488
 BinarySearchTree.cxx:489
 BinarySearchTree.cxx:490
 BinarySearchTree.cxx:491
 BinarySearchTree.cxx:492
 BinarySearchTree.cxx:493
 BinarySearchTree.cxx:494
 BinarySearchTree.cxx:495
 BinarySearchTree.cxx:496
 BinarySearchTree.cxx:497
 BinarySearchTree.cxx:498
 BinarySearchTree.cxx:499
 BinarySearchTree.cxx:500
 BinarySearchTree.cxx:501
 BinarySearchTree.cxx:502
 BinarySearchTree.cxx:503
 BinarySearchTree.cxx:504
 BinarySearchTree.cxx:505
 BinarySearchTree.cxx:506
 BinarySearchTree.cxx:507
 BinarySearchTree.cxx:508
 BinarySearchTree.cxx:509
 BinarySearchTree.cxx:510
 BinarySearchTree.cxx:511
 BinarySearchTree.cxx:512
 BinarySearchTree.cxx:513
 BinarySearchTree.cxx:514
 BinarySearchTree.cxx:515
 BinarySearchTree.cxx:516
 BinarySearchTree.cxx:517
 BinarySearchTree.cxx:518
 BinarySearchTree.cxx:519
 BinarySearchTree.cxx:520
 BinarySearchTree.cxx:521
 BinarySearchTree.cxx:522
 BinarySearchTree.cxx:523
 BinarySearchTree.cxx:524
 BinarySearchTree.cxx:525
 BinarySearchTree.cxx:526
 BinarySearchTree.cxx:527
 BinarySearchTree.cxx:528
 BinarySearchTree.cxx:529
 BinarySearchTree.cxx:530
 BinarySearchTree.cxx:531
 BinarySearchTree.cxx:532