KDTree.icc

Go to the documentation of this file.

// @(#)root/mathcore:$Id: IFunction.h 24537 2008-06-25 11:01:23Z moneta $
// Authors: C. Gumpert    09/2011
/**********************************************************************
 *                                                                    *
 * Copyright (c) 2011 , LCG ROOT MathLib Team                         *
 *                                                                    *
 *                                                                    *
 **********************************************************************/
//
// Implementation file for KDTree class
//
 
 
#ifndef KD_TREE_ICC
#define KD_TREE_ICC
 
#ifndef ROOT_Math_KDTree
#error "Do not use KDTree.icc directly. #include \"KDTree.h\" instead."
#endif // ROOT_Math_KDTree
 
// STL include(s)
#include <iostream>
#include <functional>
#include <algorithm>
#include <limits>
 
namespace ROOT
{
   namespace Math
   {
//______________________________________________________________________________
      template<class _DataPoint>
      KDTree<_DataPoint>::KDTree(UInt_t iBucketSize):
         fBucketSize(iBucketSize),
         fIsFrozen(false)
      {
         //standard constructor creates an empty k-d tree
         //
         //Input: iBucketSize - target population for each bin
         //
         //Note: - The actual interpretation of the bucket size as population depends on
         //        the chosen splitting option:
         //        kBinContent - iBucketSize applies to the sum of weights in each bucket
         //        kEffective  - iBucketSize applies to the number of effective entries in each bucket
         //      - As long as the tree has not been frozen, it is ensured that no bucket
         //        contains more than 2 x target population but there is no statement about
         //        the minimum bucket population.
         //        However, given a reasonably large bucket size with respect to characteristic
         //        event weights and sufficient statistics, most of the buckets will have
         //        a population between [0.8 * iBucketSize .. 2 * iBucketSize]
 
         // create dummy terminal node as head
         TerminalNode* pTerminal = new TerminalNode(iBucketSize);
         fHead = new HeadNode(*pTerminal);
         pTerminal->Parent() = fHead;
      }
 
//______________________________________________________________________________
      template<class _DataPoint>
      KDTree<_DataPoint>::KDTree():
         fHead(0),
         fBucketSize(1),
         fIsFrozen(false)
      {
         //private standard constructor creating a not functional tree
         //
         //only used by internal function for creating copies of the tree
      }
 
//______________________________________________________________________________
      template<class _DataPoint>
      KDTree<_DataPoint>::~KDTree()
      {
         //standard destructor deleting all nodes
         //
         //Note: - In case the option SetOWner(true) has been called beforehand and
         //        the tree is not yet frozen, all contained data point objects are
         //        deleted as well.
 
         delete fHead;
      }
 
//______________________________________________________________________________
      template<class _DataPoint>
      inline void KDTree<_DataPoint>::EmptyBins()
      {
         //all buckets are reset
         //
         //This call results in empty buckets but the splitting structure is kept.
         //You can now fill the formerly created binning with 'new' data points.
         //In order to prevent further splitting, you might want to freeze the tree.
         //
         //Note: - In case the option SetOWner(true) has been called beforehand and
         //        the tree is not yet frozen, all contained data point objects are
         //        deleted as well.
 
         for(iterator it = First(); it != End(); ++it)
            it->EmptyBin();
      }
 
//______________________________________________________________________________
      template<class _DataPoint>
      inline typename KDTree<_DataPoint>::iterator KDTree<_DataPoint>::End()
      {
         //return an iterator representing the end of all buckets
         //
         //This function can be used the retrieve a limiter for both sides. It
         //represents the 'one step after the last bin' as well as 'one step before
         //the first bin'. However, you should not try to increment/decrement this
         //iterator.
 
         return iterator(0);
      }
 
//______________________________________________________________________________
      template<class _DataPoint>
      inline const typename KDTree<_DataPoint>::iterator KDTree<_DataPoint>::End() const
      {
         //return an iterator representing the end of all buckets
         //
         //This function can be used the retrieve a limiter for both sides. It
         //represents the 'one step after the last bin' as well as 'one step before
         //the first bin'. However, you should not try to increment/decrement this
         //iterator.
 
         return iterator(0);
      }
 
//______________________________________________________________________________
      template<class _DataPoint>
      inline typename KDTree<_DataPoint>::iterator KDTree<_DataPoint>::First()
      {
         //return an iterator to the first bucket
         //
         //Note: - Buckets are not ordered to any criteria.
 
         BaseNode* pNode = fHead->Parent();
         while(pNode->LeftChild())
            pNode = pNode->LeftChild();
 
         assert(dynamic_cast<BinNode*>(pNode));
         return iterator((BinNode*)pNode);
      }
 
//______________________________________________________________________________
      template<class _DataPoint>
      inline const typename KDTree<_DataPoint>::iterator KDTree<_DataPoint>::First() const
      {
         //return an iterator to the first bucket
         //
         //Note: - Buckets are not ordered to any criteria.
 
         BaseNode* pNode = fHead->Parent();
         while(pNode->LeftChild())
            pNode = pNode->LeftChild();
 
         assert(dynamic_cast<BinNode*>(pNode));
         return iterator((BinNode*)pNode);
      }
 
//______________________________________________________________________________
      template<class _DataPoint>
      void KDTree<_DataPoint>::Freeze()
      {
         //freeze the current tree
         //
         //By calling this function, the current splitting information in the tree is frozen.
         //No further division of buckets into sub-buckets will occur.
         //In addition all point related information are dropped. Therefore nearest neighbor
         //searches or retrieving the data points from a bucket are not possible anymore.
         //Furthermore, no restrictions on the population in each bucket exist if the tree
         //is filled with further points.
         //
         //Note: - Technically it means that all TerminalNodes are converted to BinNodes
         //        resulting in a loss of all information related to individual data points.
 
         // do it only once
         if(!fIsFrozen)
         {
            std::vector<TerminalNode*> vBins;
            // replace all terminal nodes by bin nodes
            for(iterator it = First(); it != End(); ++it)
               vBins.push_back(it.TN());
 
            BinNode* pBin = 0;
            for(typename std::vector<TerminalNode*>::iterator bit = vBins.begin(); bit != vBins.end(); ++bit)
            {
               pBin = (*bit)->ConvertToBinNode();
               (*bit)->GetParentPointer() = pBin;
               pBin->Parent() = (*bit)->Parent();
               delete *bit;
            }
 
            fIsFrozen = true;
         }
      }
 
//______________________________________________________________________________
      template<class _DataPoint>
      void KDTree<_DataPoint>::GetClosestPoints(const _DataPoint& rRef,UInt_t nPoints,
                                                std::vector<std::pair<const _DataPoint*,Double_t> >& vFoundPoints) const
      {
         //returns the nPoints data points closest to the given reference point
         //
         //Input: rRef         - reference point
         //       nPoints      - desired number of closest points (0 < nPoints < total number of points in tree)
         //       vFoundPoints - vector containing all found points
         //
         //vFoundPoints contains the nPoints pairs of:
         // first  = pointer to found data point
         // second = distance between found data point and reference point
         //
         //vFoundPoints is ordered in the sense that the point closest to the reference comes first.
         //
         //Note: - This method works only if the tree has not yet been frozen.
 
         // check bad input and that tree is not frozen yet
         if((nPoints > 0) && (!fIsFrozen))
            fHead->GetClosestPoints(rRef,nPoints,vFoundPoints);
      }
 
//______________________________________________________________________________
      template<class _DataPoint>
      Double_t KDTree<_DataPoint>::GetEffectiveEntries() const
      {
         //returns the total effective entries of the tree
         //
         //Note: - This is not the sum of effective entries of all buckets!
 
         Double_t fSumw = 0;
         Double_t fSumw2 = 0;
         for(iterator it = First(); it != End(); ++it)
         {
            fSumw += it->GetBinContent();
            fSumw2 += it->GetSumw2();
         }
 
         return ((fSumw2) ? fSumw * fSumw / fSumw2 : 0);
      }
 
//______________________________________________________________________________
      template<class _DataPoint>
      UInt_t KDTree<_DataPoint>::GetEntries() const
      {
         //returns the number of filled data points
 
         UInt_t iPoints = 0;
         for(iterator it = First(); it != End(); ++it)
            iPoints += it->GetEntries();
 
         return iPoints;
      }
 
//______________________________________________________________________________
      template<class _DataPoint>
      KDTree<_DataPoint>* KDTree<_DataPoint>::GetFrozenCopy()
      {
         //returns a frozen copy of this k-d tree
         //
         //Note: - The current tree remains unchanged.
         //      - The new tree is owned by the user (-> you should invoke 'delete' if you do not need it anymore)!
 
         KDTree<_DataPoint>* pTree = new KDTree<_DataPoint>();
         pTree->fBucketSize = fBucketSize;
         pTree->fHead = fHead->Clone();
         pTree->fIsFrozen = true;
 
         return pTree;
      }
 
//______________________________________________________________________________
      template<class _DataPoint>
      UInt_t KDTree<_DataPoint>::GetNBins() const
      {
         //returns the number of buckets
 
         UInt_t iBins = 0;
         for(iterator it = First(); it != End(); ++it)
            ++iBins;
 
         return iBins;
      }
 
//______________________________________________________________________________
      template<class _DataPoint>
      void KDTree<_DataPoint>::GetPointsWithinDist(const _DataPoint& rRef,value_type fDist,
                                                   std::vector<const _DataPoint*>& vFoundPoints) const
      {
         //returns all data points within a given distance around the reference point
         //
         //Input: rRef         - reference point
         //       fDist        - radius of sphere around reference point (0 < fDist)
         //       vFoundPoints - vector to store the results
         //
         //vFoundPoints contains the pointers to all data points in the specified sphere.
         //The points are NOT ordered according to their distance.
         //
         //Note - This method works only if the tree has not yet been frozen.
         //     - Distance is defined as euclidean distance in a k-dimensional space.
 
         // valid distance given and tree not frozen yet
         if((fDist > 0) && (!fIsFrozen))
            fHead->GetPointsWithinDist(rRef,fDist,vFoundPoints);
      }
 
//______________________________________________________________________________
      template<class _DataPoint>
      Double_t KDTree<_DataPoint>::GetTotalSumw() const
      {
         //returns the total sum of weights
 
         Double_t fSumw = 0;
         for(iterator it = First(); it != End(); ++it)
            fSumw += it->GetSumw();
 
         return fSumw;
      }
 
//______________________________________________________________________________
      template<class _DataPoint>
      Double_t KDTree<_DataPoint>::GetTotalSumw2() const
      {
         //returns the total sum of weights^2
 
         Double_t fSumw2 = 0;
         for(iterator it = First(); it != End(); ++it)
            fSumw2 += it->GetSumw2();
 
         return fSumw2;
      }
 
//______________________________________________________________________________
      template<class _DataPoint>
      inline typename KDTree<_DataPoint>::iterator KDTree<_DataPoint>::Last()
      {
         //returns an iterator to the last bucket
         //
         //Note: - Buckets are not ordered to any criteria.
 
         BaseNode* pNode = fHead->Parent();
         while(pNode->RightChild())
            pNode = pNode->RightChild();
 
         assert(dynamic_cast<TerminalNode*>(pNode));
         return iterator((TerminalNode*)pNode);
      }
 
//______________________________________________________________________________
      template<class _DataPoint>
      inline const typename KDTree<_DataPoint>::iterator KDTree<_DataPoint>::Last() const
      {
         //returns an iterator to the last bucket
         //
         //Note: - Buckets are not ordered to any criteria.
 
         BaseNode* pNode = fHead->Parent();
         while(pNode->RightChild())
            pNode = pNode->RightChild();
 
         assert(dynamic_cast<BinNode*>(pNode));
         return iterator((BinNode*)pNode);
      }
 
//______________________________________________________________________________
      template<class _DataPoint>
      void KDTree<_DataPoint>::Reset()
      {
         //resets the tree
         //
         //Afterwards the tree is completely empty and all splitting information is lost.
         //
         //Note: - In case the option SetOWner(true) has been called beforehand and
         //        the tree is not yet frozen, all contained data point objects are
         //        deleted as well.
         //      - The 'frozen' status is reset to false. Otherwise you won't be able to
         //        create splittings and the tree would consist of only one large bucket.
 
         // delete current tree
         delete fHead->Parent();
         // create new (and empty) top bucket
         TerminalNode* pTerminal = new TerminalNode(fBucketSize);
         pTerminal->Parent() = fHead;
         fHead->Parent() = pTerminal;
 
         // reset 'freeze' status
         fIsFrozen = false;
      }
 
//______________________________________________________________________________
      template<class _DataPoint>
      void KDTree<_DataPoint>::SetOwner(Bool_t bIsOwner)
      {
         //specifies the ownership of data points
         //
         //Input: bIsOwner - true: data points are located on the heap and the ownership
         //                        is transferred to the tree object
         //                  false: the data points are not owned by the tree
         //
         //Note: - This function has no effect if the tree is already frozen.
 
         if(!fIsFrozen)
         {
            for(iterator it = First(); it != End(); ++it)
               it.TN()->SetOwner(bIsOwner);
         }
      }
 
//______________________________________________________________________________
      template<class _DataPoint>
      void KDTree<_DataPoint>::SetSplitOption(eSplitOption opt)
      {
         //sets the splitting option for the buckets
         //
         //Buckets are split into two sub-buckets if their population reaches twice the
         //given bucket size. The definition of population depends on the chosen splitting
         //option:
         //kBinContent = population is the sum of weights
         //kEffective  = population is the number of effective entries
         //
         //Note: - In principle it possible to change the splitting mode while filling the tree.
         //        However, this should be avoided to ensure an optimal splitting.
         //      - This function has no effect if the tree is already frozen.
 
         if(!fIsFrozen)
         {
            for(iterator it = First(); it != End(); ++it)
               it.TN()->SetSplitOption(opt);
         }
      }
 
//______________________________________________________________________________
      template<class _DataPoint>
      bool KDTree<_DataPoint>::ComparePoints::operator()(const _DataPoint* pFirst,const _DataPoint* pSecond) const
      {
         //compares two points along set axis
         //
         //Uses the internal comparison axis of the ComparePoints object to evaluate:
         //
         // pFirst[Axis] < pSecond[Axis]
         //
         //Note: - The template class _DataPoint has to provide a static function:
         //
         //        static UInt_t _DataPoint::Dimension()
         //
         //        returning the dimensionality of the data point.
         //      - The dimensionality of the two data points is higher than the currently
         //        set comparison axis.
 
         assert(pFirst && pSecond && (fAxis < KDTree<_DataPoint>::Dimension()));
 
         return (pFirst->GetCoordinate(fAxis) < pSecond->GetCoordinate(fAxis));
      }
 
//______________________________________________________________________________
      template<class _DataPoint>
      bool KDTree<_DataPoint>::Cut::operator<(const _DataPoint& rPoint) const
      {
         //comapares a point with the given cut
         //
         // this cut value < rPoint.GetCoordinate(this cut axis)
         //
         //Note: - The template class _DataPoint has to provide a static function:
         //
         //        static UInt_t _DataPoint::Dimension()
         //
         //        returning the dimensionality of the data point.
         //      - The dimensionality of the given data point is higher than the cut
         //        axis.
 
         assert(Dimension() > fAxis);
         return (fCutValue < rPoint.GetCoordinate(fAxis));
      }
 
//______________________________________________________________________________
      template<class _DataPoint>
      bool KDTree<_DataPoint>::Cut::operator>(const _DataPoint& rPoint) const
      {
         //compares a point with the given cut
         //
         // this cut value > rPoint.GetCoordinate(this cut axis)
         //
         //Note: - The template class _DataPoint has to provide a static function:
         //
         //        static UInt_t _DataPoint::Dimension()
         //
         //        returning the dimensionality of the data point.
         //      - The dimensionality of the given data point is higher than the cut
         //        axis.
 
         assert(Dimension() > fAxis);
         return (fCutValue > rPoint.GetCoordinate(fAxis));
      }
 
//______________________________________________________________________________
      template<class _DataPoint>
      KDTree<_DataPoint>::BaseNode::BaseNode(BaseNode* pParent):
         fParent(pParent),
         fLeftChild(0),
         fRightChild(0)
      {
         //standard constructor
      }
 
//______________________________________________________________________________
      template<class _DataPoint>
      KDTree<_DataPoint>::BaseNode::~BaseNode()
      {
         //standard destructor
         //
         //Note: - both children are deleted but no pointer rearrangement is done
         //        -> should not be a problem as long as you do not try to rely on
         //           tree internal information
 
         delete LeftChild();
         delete RightChild();
      }
 
//______________________________________________________________________________
      template<class _DataPoint>
      typename KDTree<_DataPoint>::BaseNode*& KDTree<_DataPoint>::BaseNode::GetParentPointer()
      {
         //returns a reference to the pointer from the parent node to the current node
         //
         //Note: - This should never be called for the head node (as it is the head!)
 
         assert(!IsHeadNode());
 
         if(Parent()->Parent() == this)
            return Parent()->Parent();
         if(Parent()->LeftChild() == this)
            return Parent()->LeftChild();
         if(Parent()->RightChild() == this)
            return Parent()->RightChild();
 
         // should never reach this line
         assert(false);
         return Parent();  // to fix a warning statement
      }
 
//______________________________________________________________________________
      template<class _DataPoint>
      bool KDTree<_DataPoint>::BaseNode::IsLeftChild() const
      {
         //checks whether the current node is a left node
         //
         //Note: - returns false in the case of the head node (which is no child at all)
 
         if(Parent()->IsHeadNode())
            return false;
         else
            return (Parent()->LeftChild() == this);
      }
 
//______________________________________________________________________________
      template<class _DataPoint>
      typename KDTree<_DataPoint>::HeadNode* KDTree<_DataPoint>::HeadNode::Clone()
      {
         //creates an identical copy
         //
         //Note: - The Clone() function is propagated to the whole tree -> the returned
         //        pointer is the head node of a complete new tree.
 
         BaseNode* pParent = Parent()->Clone();
         HeadNode* pHead = new HeadNode(*pParent);
         pParent->Parent() = pHead;
 
         return pHead;
      }
 
//______________________________________________________________________________
      template<class _DataPoint>
      inline void KDTree<_DataPoint>::HeadNode::GetClosestPoints(const _DataPoint& rRef,UInt_t nPoints,
                                                                 std::vector<std::pair<const _DataPoint*,Double_t> >& vFoundPoints) const
      {
         Parent()->GetClosestPoints(rRef,nPoints,vFoundPoints);
      }
 
//______________________________________________________________________________
      template<class _DataPoint>
      inline void KDTree<_DataPoint>::HeadNode::GetPointsWithinDist(const _DataPoint& rRef,value_type fDist,
                                                                    std::vector<const _DataPoint*>& vFoundPoints) const
      {
         Parent()->GetPointsWithinDist(rRef,fDist,vFoundPoints);
      }
 
//______________________________________________________________________________
      template<class _DataPoint>
      KDTree<_DataPoint>::SplitNode::SplitNode(UInt_t iAxis,Double_t fCutValue,BaseNode& rLeft,
                                               BaseNode& rRight,BaseNode* pParent):
         BaseNode(pParent),
         fCut(new Cut(iAxis,fCutValue))
      {
         //standard constructor for spitting node which represents a splitting hyperplane
         //
         //Input: iAxis     - axis on which the split is performed
         //       fCutValue - cut value
         //       rLeft     - left sub-bucket
         //       rRight    - right sub-bucket
         //       pParent   - optional pointer to parent node
         //
         //Note: - As a split node can never be a leaf, always the two child nodes has to
         //        be passed at construction time.
 
         this->LeftChild() = &rLeft;
         this->RightChild() = &rRight;
      }
 
//______________________________________________________________________________
      template<class _DataPoint>
      KDTree<_DataPoint>::SplitNode::~SplitNode()
      {
         // standard destructor
 
         delete fCut;
      }
 
//______________________________________________________________________________
      template<class _DataPoint>
      typename KDTree<_DataPoint>::SplitNode* KDTree<_DataPoint>::SplitNode::Clone()
      {
         //creates a direct copy of this node
         //
         //This also involves the copying of the child nodes.
 
         BaseNode* pLeft = this->LeftChild()->Clone();
         BaseNode* pRight = this->RightChild()->Clone();
 
         SplitNode* pSplit = new SplitNode(fCut->GetAxis(),fCut->GetCutValue(),*pLeft,*pRight);
 
         pLeft->Parent() = pSplit;
         pRight->Parent() = pSplit;
 
         return pSplit;
      }
 
//______________________________________________________________________________
      template<class _DataPoint>
      const typename KDTree<_DataPoint>::BinNode* KDTree<_DataPoint>::SplitNode::FindNode(const _DataPoint& rPoint) const
      {
         //finds bin node containing the given reference point
 
         // pPoint < cut -> left sub tree
         if(*fCut > rPoint)
            return this->LeftChild()->FindNode(rPoint);
         // pPoint >= cut -> right sub tree
         else
            return this->RightChild()->FindNode(rPoint);
      }
 
//______________________________________________________________________________
      template<class _DataPoint>
      void KDTree<_DataPoint>::SplitNode::GetClosestPoints(const _DataPoint& rRef,UInt_t nPoints,
                                                           std::vector<std::pair<const _DataPoint*,Double_t> >& vFoundPoints) const
      {
         //finds the closest points around the given reference point
         //
         //Input: rRef         - reference point
         //       nPoints      - number of points to look for (should be less than the total number of points in the tree)
         //       vFoundPoints - vector in which the result is stored as pair <pointer to found data point,distance to reference point>
         //
         //Note: vFoundPoints is ordered in the sense that the found point closest to the reference point comes first.
 
         // rRef < cut -> left sub tree
         if(*fCut > rRef)
         {
            this->LeftChild()->GetClosestPoints(rRef,nPoints,vFoundPoints);
 
            // number of found points lower than wanted number of points
            // or: sphere with (radius = largest distance between rRef and vFoundPoints) intersects the splitting plane
            // --> look also in right sub bucket
            if((vFoundPoints.size() < nPoints) || (vFoundPoints.back().second > fabs(rRef.GetCoordinate(fCut->GetAxis()) - fCut->GetCutValue())))
               this->RightChild()->GetClosestPoints(rRef,nPoints,vFoundPoints);
         }
         // rRef >= cut -> right sub tree
         else
         {
            this->RightChild()->GetClosestPoints(rRef,nPoints,vFoundPoints);
 
            // number of found points lower than wanted number of points
            // or: sphere with (radius = largest distance between rRef and vFoundPoints) intersects the splitting plane
            // --> look also in left sub bucket
            if((vFoundPoints.size() < nPoints) || (vFoundPoints.back().second > fabs(rRef.GetCoordinate(fCut->GetAxis()) - fCut->GetCutValue())))
               this->LeftChild()->GetClosestPoints(rRef,nPoints,vFoundPoints);
         }
      }
 
//______________________________________________________________________________
      template<class _DataPoint>
      void KDTree<_DataPoint>::SplitNode::GetPointsWithinDist(const _DataPoint& rRef,value_type fDist,
                                                              std::vector<const _DataPoint*>& vFoundPoints) const
      {
         //returns the points within a certain distance around the reference point
         //
         //Input: rRef         - reference point
         //       fDist        - radius of sphere to scan ( > 0)
         //       vFoundPoints - vector in which all found points are stored
         //
         //Note: vFoundPoints ist NOT ordered.
 
         // does the sphere around rRef intersect the splitting plane?
         // no -> check only points in sub bucket which rRef belongs to
         if(fabs(rRef.GetCoordinate(fCut->GetAxis()) - fCut->GetCutValue()) > fDist)
         {
            // rRef < cut -> left sub tree
            if(*fCut > rRef)
               this->LeftChild()->GetPointsWithinDist(rRef,fDist,vFoundPoints);
            // rRef >= cut -> right sub tree
            else
               this->RightChild()->GetPointsWithinDist(rRef,fDist,vFoundPoints);
         }
         // yes -> check points in both sub buckets
         else
         {
            this->RightChild()->GetPointsWithinDist(rRef,fDist,vFoundPoints);
            this->LeftChild()->GetPointsWithinDist(rRef,fDist,vFoundPoints);
         }
      }
 
//______________________________________________________________________________
      template<class _DataPoint>
      inline Bool_t KDTree<_DataPoint>::SplitNode::Insert(const _DataPoint& rPoint)
      {
         //inserts a new data point in the tree
 
         // pPoint < cut -> left sub tree
         if(*fCut > rPoint)
            return this->LeftChild()->Insert(rPoint);
         // pPoint >= cut -> right sub tree
         else
            return this->RightChild()->Insert(rPoint);
      }
 
//______________________________________________________________________________
      template<class _DataPoint>
      void KDTree<_DataPoint>::SplitNode::Print(int iRow) const
      {
         //prints some information about the current node
 
         std::cout << "SplitNode at " << this << " in row " << iRow << std::endl;
         std::cout << "cut on " << fCut->GetCutValue() << " at axis " << fCut->GetAxis() << std::endl;
 
         this->LeftChild()->Print(iRow+1);
         this->RightChild()->Print(iRow+1);
      }
 
//______________________________________________________________________________
      template<class _DataPoint>
      KDTree<_DataPoint>::BinNode::BinNode(BaseNode* pParent):
         BaseNode(pParent),
         fBoundaries(std::vector<tBoundary>(Dimension(),std::make_pair(0,0))),
         fSumw(0),
         fSumw2(0),
         fEntries(0)
      {
         //standard constructor
      }
 
//______________________________________________________________________________
      template<class _DataPoint>
      KDTree<_DataPoint>::BinNode::BinNode(const BinNode& copy):
         BaseNode(),
         fBoundaries(copy.fBoundaries),
         fSumw(copy.fSumw),
         fSumw2(copy.fSumw2),
         fEntries(copy.fEntries)
      {
         //copy constructor
         //
         //Note: - The resulting bin node is NOT connected to any other node
         //        -> it is not part of any tree
 
         this->Parent() = 0;
         this->LeftChild() = 0;
         this->RightChild() = 0;
      }
 
//______________________________________________________________________________
      template<class _DataPoint>
      typename KDTree<_DataPoint>::BinNode* KDTree<_DataPoint>::BinNode::Clone()
      {
         //creates identical copy which is not part of the tree anymore
 
         return new BinNode(*this);
      }
 
//______________________________________________________________________________
      template<class _DataPoint>
      void KDTree<_DataPoint>::BinNode::EmptyBin()
      {
         //resets bin content, sumw, asumw2 and entries
 
         fSumw2 = fSumw = 0;
         fEntries = 0;
      }
 
//______________________________________________________________________________
      template<class _DataPoint>
      typename KDTree<_DataPoint>::BinNode& KDTree<_DataPoint>::BinNode::operator=(const BinNode& rhs)
      {
         //assignment operator
         //
         //Note: - Should not be used because it can lead to inconsistencies with respect
         //        bin boundaries.
 
         fBoundaries = rhs.fBoundaries;
         fSumw = rhs.fSumw;
         fSumw2 = rhs.fSumw2;
         fEntries = rhs.fEntries;
         return *this;
      }
 
//______________________________________________________________________________
      template<class _DataPoint>
      const typename KDTree<_DataPoint>::BinNode* KDTree<_DataPoint>::BinNode::FindNode(const _DataPoint& rPoint) const
      {
         //finds bin node containing the given reference point
 
         if(IsInBin(rPoint))
            return this;
         else
            return 0;
      }
 
//______________________________________________________________________________
      template<class _DataPoint>
      _DataPoint KDTree<_DataPoint>::BinNode::GetBinCenter() const
      {
         //returns the bin center of the current node
         //
         //Note: - The bin center is defined as
         //        coordinate i = 0.5 * (lower bound i + upper bound i)
 
         _DataPoint rPoint;
 
         for(UInt_t k = 0; k < Dimension(); ++k)
            rPoint.SetCoordinate(k,0.5 * (fBoundaries.at(k).first + fBoundaries.at(k).second));
 
         return rPoint;
      }
 
//______________________________________________________________________________
      template<class _DataPoint>
      Double_t KDTree<_DataPoint>::BinNode::GetVolume() const
      {
         //returns the volume of the current bin
         //
         //Note: - The volume is defined as
         //        vol = product over i (upper bound i - lower bound i)
 
         Double_t dVol = 1;
         for(typename std::vector<tBoundary>::const_iterator it = fBoundaries.begin(); it != fBoundaries.end(); ++it)
            dVol *= (it->second - it->first);
 
         return dVol;
      }
 
 
//______________________________________________________________________________
      template<class _DataPoint>
      Bool_t KDTree<_DataPoint>::BinNode::Insert(const _DataPoint& rPoint)
      {
         //inserts a new data point in this bin
 
         if(IsInBin(rPoint))
         {
            ++fEntries;
            fSumw += rPoint.GetWeight();
            fSumw2 += pow(rPoint.GetWeight(),2);
 
            return true;
         }
         else
            return false;
      }
 
//______________________________________________________________________________
      template<class _DataPoint>
      Bool_t KDTree<_DataPoint>::BinNode::IsInBin(const _DataPoint& rPoint) const
      {
         //checks whether the given point is inside the boundaries of this bin
 
         for(UInt_t k = 0; k < Dimension(); ++k)
            if((rPoint.GetCoordinate(k) < fBoundaries.at(k).first) || (fBoundaries.at(k).second < rPoint.GetCoordinate(k)))
               return false;
 
         return true;
      }
 
//______________________________________________________________________________
      template<class _DataPoint>
      void KDTree<_DataPoint>::BinNode::Print(int) const
      {
         //prints some information about this bin node
 
         std::cout << "BinNode at " << this << std::endl;
         std::cout << "containing " << GetEntries() << " entries" << std::endl;
         std::cout << "sumw = " << GetBinContent() << " sumw2 = " << GetSumw2() << " => effective entries = " << GetEffectiveEntries() << std::endl;
         std::cout << "volume = " << GetVolume() << " and bin center at (";
         _DataPoint rBinCenter = GetBinCenter();
         for(UInt_t dim = 0; dim < Dimension(); ++dim)
         {
            std::cout << rBinCenter.GetCoordinate(dim);
            if(dim < Dimension() -1)
               std::cout << ",";
         }
         std::cout << ")" << std::endl;
         std::cout << "boundaries are ";
         for(typename std::vector<tBoundary>::const_iterator it = fBoundaries.begin(); it != fBoundaries.end(); ++it)
            std::cout << "(" << it->first << " ... " << it->second << ") ";
         std::cout << std::endl;
      }
 
//______________________________________________________________________________
      template<class _DataPoint>
      KDTree<_DataPoint>::TerminalNode::TerminalNode(Double_t iBucketSize,BaseNode* pParent):
         BinNode(pParent),
         fOwnData(false),
         fSplitOption(kEffective),
         fBucketSize(iBucketSize),
         fSplitAxis(0)
      {
         //standard constructor
         //
         //Input: iBucketSize - desired bucket size
         //       pParent     - pointer to parent node (optional)
         //
         //Note: - The bucket size has to be positive.
         //      - The standard split option is kEffective.
         //      - By default the data points are not owned by the tree.
 
         assert(fBucketSize > 0);
      }
 
//______________________________________________________________________________
      template<class _DataPoint>
      KDTree<_DataPoint>::TerminalNode::TerminalNode(Double_t iBucketSize,UInt_t iSplitAxis,data_it first,data_it end):
         BinNode(),
         fOwnData(false),
         fSplitOption(kEffective),
         fBucketSize(iBucketSize),
         fSplitAxis(iSplitAxis % Dimension()),
         fDataPoints(std::vector<const _DataPoint*>(first,end))
      {
         //internal constructor used for splitting
         //
         //Input: iBucketSize - desired bucket size
         //       iSplitAxis  - axis for next splitting
         //       first,end   - iterators pointing to the beginning and end of data points
         //                     which are copied to this TerminalNode
 
         // recalculate sumw and sumw2
         for(data_it it = fDataPoints.begin(); it != fDataPoints.end(); ++it)
         {
            this->fSumw += (*it)->GetWeight();
            this->fSumw2 += pow((*it)->GetWeight(),2);
         }
 
         this->fEntries = fDataPoints.size();
      }
 
//______________________________________________________________________________
      template<class _DataPoint>
      KDTree<_DataPoint>::TerminalNode::~TerminalNode()
      {
         //standard destructor
         //
         //Note: - If fOwnData is set, all associated data point objects are deleted
 
         if(fOwnData)
         {
            for(typename std::vector<const _DataPoint*>::iterator it = fDataPoints.begin();
                it != fDataPoints.end(); ++it)
               delete *it;
         }
      }
 
//______________________________________________________________________________
      template<class _DataPoint>
      typename KDTree<_DataPoint>::BinNode* KDTree<_DataPoint>::TerminalNode::ConvertToBinNode()
      {
         //creates a new BinNode with information of the TerminalNode
         //
         //The returned BinNode contains all information of this TerminalNode except the
         //point-related information.
         //
         //Note: - The returned node is not owned by the tree but the user as to take care of it.
 
         UpdateBoundaries();
         BinNode* pBin = new BinNode(*this);
 
         return pBin;
      }
 
//______________________________________________________________________________
      template<class _DataPoint>
      void KDTree<_DataPoint>::TerminalNode::EmptyBin()
      {
         //resets the bin content and removes all data points
         //
         //Note: - If fOwnData is set, all associated data points are deleted.
 
         // delete data points
         if(fOwnData)
         {
            for(typename std::vector<const _DataPoint*>::iterator it = fDataPoints.begin();
                it != fDataPoints.end(); ++it)
               delete *it;
         }
         fDataPoints.clear();
         UpdateBoundaries();
         BinNode::EmptyBin();
      }
//______________________________________________________________________________
      template<class _DataPoint>
#ifdef _AIX
      void KDTree<_DataPoint>::TerminalNode::GetBoundaries() const { }
#else
      const std::vector<typename KDTree<_DataPoint>::TerminalNode::tBoundary>& KDTree<_DataPoint>::TerminalNode::GetBoundaries() const
      {
         //returns the boundaries of this TerminalNode
         //
         //Note: - In a high-dimensional space most of the nodes are bounded only on
         //        one side due to a split. One-sided intervals would result in an
         //        infinite volume of the bin which is not the desired behaviour.
         //        Therefore the following convention is used for determining the
         //        boundaries:
         //        If a node is not restricted along one axis on one/both side(s) due
         //        to a split, the corresponding upper/lower boundary is set to
         //        the minimum/maximum coordinate along this axis of all contained
         //        data points.
         //        This procedure maximises the density in the bins.
 
         const_cast<TerminalNode*>(this)->UpdateBoundaries();
 
         return BinNode::GetBoundaries();
      }
#endif
//______________________________________________________________________________
      template<class _DataPoint>
      void KDTree<_DataPoint>::TerminalNode::GetClosestPoints(const _DataPoint& rRef,UInt_t nPoints,
                                                              std::vector<std::pair<const _DataPoint*,Double_t> >& vFoundPoints) const
      {
         //finds the closest points around the given reference point
         //
         //Input: rRef         - reference point
         //       nPoints      - number of points to look for (should be less than the total number of points in the tree)
         //       vFoundPoints - vector in which the result is stored as pair <pointer to found data point,distance to reference point>
         //
         //Note: vFoundPoints is ordered in the sense that the found point closest to the reference point comes first.
 
         // store maximal distance so far if desired number of points already found
         value_type fMaxDist = (vFoundPoints.size() < nPoints) ? std::numeric_limits<value_type>::max() : vFoundPoints.back().second;
         value_type fDist;
         typedef typename std::vector<std::pair<const _DataPoint*,Double_t> >::iterator t_pit;
 
         // loop over all points and check distances
         for(typename std::vector<const _DataPoint*>::const_iterator it = fDataPoints.begin(); it != fDataPoints.end(); ++it)
         {
            fDist = (*it)->Distance(rRef);
            // fDist < fMaxDist -> insert
            if(fDist < fMaxDist)
            {
               // find position at which the current point should be inserted
               t_pit pit = vFoundPoints.begin();
               while(pit != vFoundPoints.end())
               {
                  if(pit->second > fDist)
                     break;
                  else
                     ++pit;
               }
 
               vFoundPoints.insert(pit,std::make_pair(*it,fDist));
               // truncate vector of found points at nPoints
               if(vFoundPoints.size() > nPoints)
                  vFoundPoints.resize(nPoints);
               // update maximal distance
               fMaxDist = (vFoundPoints.size() < nPoints) ? vFoundPoints.back().second : std::numeric_limits<value_type>::max();
            }
         }
      }
 
//______________________________________________________________________________
      template<class _DataPoint>
      void KDTree<_DataPoint>::TerminalNode::GetPointsWithinDist(const _DataPoint& rRef,value_type fDist,
                                                                 std::vector<const _DataPoint*>& vFoundPoints) const
      {
         //returns the points within a certain distance around the reference point
         //
         //Input: rRef         - reference point
         //       fDist        - radius of sphere to scan ( > 0)
         //       vFoundPoints - vector in which all found points are stored
         //
         //Note: vFoundPoints ist NOT ordered.
 
         // loop over all points and check distances
         for(typename std::vector<const _DataPoint*>::const_iterator it = fDataPoints.begin(); it != fDataPoints.end(); ++it)
         {
            if((*it)->Distance(rRef) <= fDist)
               vFoundPoints.push_back(*it);
         }
      }
 
//______________________________________________________________________________
      template<class _DataPoint>
      Bool_t KDTree<_DataPoint>::TerminalNode::Insert(const _DataPoint& rPoint)
      {
         //inserts a new data point in this bin
         //
         //Note: - If the population of this TerminalNode exceeds the limit of
         //        2 x fBucketSize, the node is split using the Split() function.
 
         // store pointer to data point
         fDataPoints.push_back(&rPoint);
 
         // update weights
         this->fSumw += rPoint.GetWeight();
         this->fSumw2 += pow(rPoint.GetWeight(),2);
         ++this->fEntries;
 
         // split terminal node if necessary
         switch(fSplitOption)
         {
         case kEffective:
            if(this->GetEffectiveEntries() > 2 * fBucketSize)
               Split();
            break;
         case kBinContent:
            if(this->GetSumw() > 2 * fBucketSize)
               Split();
            break;
         default: assert(false);
         }
 
         return true;
      }
 
//______________________________________________________________________________
      template<class _DataPoint>
      void KDTree<_DataPoint>::TerminalNode::Print(int iRow) const
      {
         //prints some information about this TerminalNode
 
         std::cout << "TerminalNode at " << this << " in row " << iRow << std::endl;
         const_cast<TerminalNode*>(this)->UpdateBoundaries();
         BinNode::Print(iRow);
         std::cout << "next split axis: " << fSplitAxis << std::endl << std::endl;
         for(const_data_it it = fDataPoints.begin(); it != fDataPoints.end(); ++it)
         {
            std::cout << "(";
            for(UInt_t i = 0; i < Dimension(); ++i)
            {
               std::cout << (*it)->GetCoordinate(i);
               if(i != Dimension() - 1)
                  std::cout << ",";
            }
            std::cout << "), w = " << (*it)->GetWeight() << std::endl;
         }
 
         std::cout << std::endl;
      }
 
//______________________________________________________________________________
      template<class _DataPoint>
      void KDTree<_DataPoint>::TerminalNode::Split()
      {
         //splits this TerminalNode
         //
         //A new SplitNode containing the split axis and split value is created. It
         //is placed at the current position of this TerminalNode in the tree.
         //The data points in this node are divided into two groups according to
         //the splitting axis and value. From the second half a new TerminalNode is created.
         //
         //Sketch:               SplitNode
         //                     |         |
         //                    ...   current TerminalNode (which is split)
         //
         //                         |
         //                         V
         //
         //                      SplitNode
         //                     |         |
         //                    ...     new SplitNode
         //                           |             |
         //                current TerminalNode   new TerminalNode
         //                (modified)
 
         data_it cut;
         switch(fSplitOption)
         {
         case kEffective: cut = SplitEffectiveEntries(); break;
         case kBinContent: cut = SplitBinContent(); break;
         default: assert(false);
         }
 
         // store split value
         value_type fSplitValue = (*cut)->GetCoordinate(fSplitAxis);
         //create second terminal node with second part of (unsorted vector)
         TerminalNode* pNew = new TerminalNode(fBucketSize,fSplitAxis+1,cut,fDataPoints.end());
         // copy options
         pNew->SetOwner(fOwnData);
         pNew->SetSplitOption(fSplitOption);
 
         // remove the copied elements from this bucket
         fDataPoints.erase(cut,fDataPoints.end());
         // recalculate sumw and sumw2
         this->fSumw = this->fSumw2 = 0;
         for(data_it it = fDataPoints.begin(); it != fDataPoints.end(); ++it)
         {
            this->fSumw += (*it)->GetWeight();
            this->fSumw2 += pow((*it)->GetWeight(),2);
         }
         this->fEntries = fDataPoints.size();
 
         // create new splitting node
         SplitNode* pSplit = new SplitNode(fSplitAxis,fSplitValue,*this,*pNew,this->Parent());
 
         // link new splitting node
         this->GetParentPointer() = pSplit;
 
         // set splitting node as new parent of both terminal nodes
         this->Parent() = pSplit;
         pNew->Parent() = pSplit;
 
         // update boundaries
         this->UpdateBoundaries();
         pNew->UpdateBoundaries();
 
         // change splitting axis
         ++fSplitAxis;
         fSplitAxis = fSplitAxis % Dimension();
      }
 
//______________________________________________________________________________
      template<class _DataPoint>
      typename KDTree<_DataPoint>::TerminalNode::data_it KDTree<_DataPoint>::TerminalNode::SplitEffectiveEntries()
      {
         //splits according to the number of effective entries
         //
         //returns an iterator pointing to the data point at which the vector should be split
         //
         //Note: - The vector containing the data points is partially ordered according to the
         //        coordinates of the current split axis at least until the position of cut.
 
         // function pointer for comparing data points
         typename KDTree<_DataPoint>::ComparePoints cComp;
         cComp.SetAxis(fSplitAxis);
 
         data_it first = fDataPoints.begin();
         data_it cut = first;
         data_it middle;
         UInt_t step = fDataPoints.size();
         Double_t fSumwTemp = 0;
         Double_t fSumw2Temp = 1e-7;
         Double_t fEffective = this->GetEffectiveEntries();
 
         // sort data points along split axis
         // find data point at which the cumulative effective entries reach half of the total effective entries
         while(((fSumwTemp * fSumwTemp)/fSumw2Temp < fEffective/2) && (step > 1))
         {
            middle = first + (++step /= 2);
            std::partial_sort(first,middle,fDataPoints.end(),cComp);
 
            while(((fSumwTemp * fSumwTemp)/fSumw2Temp < fEffective/2) && (cut != middle-1))
            {
               fSumwTemp += (*cut)->GetWeight();
               fSumw2Temp += pow((*cut)->GetWeight(),2);
               ++cut;
            }
            first = middle;
         }
 
         return cut;
      }
 
//______________________________________________________________________________
      template<class _DataPoint>
      typename KDTree<_DataPoint>::TerminalNode::data_it KDTree<_DataPoint>::TerminalNode::SplitBinContent()
      {
         //splits according to the bin content
         //
         //returns an iterator pointing to the data point at which the vector should be split
         //
         //Note: - The vector containing the data points is partially ordered according to the
         //        coordinates of the current split axis at least until the position of cut.
 
         // function pointer for comparing data points
         typename KDTree<_DataPoint>::ComparePoints cComp;
         cComp.SetAxis(fSplitAxis);
 
         data_it first = fDataPoints.begin();
         data_it cut = first;
         data_it middle;
         UInt_t step = fDataPoints.size();
         Double_t fSumwTemp = 0;
         Double_t fBinContent = this->GetSumw();
 
         // sort data points along split axis
         // find data point at which the cumulative effective entries reach half of the total effective entries
         while((fSumwTemp < fBinContent/2) && (step > 1))
         {
            middle = first + (++step /= 2);
            std::partial_sort(first,middle,fDataPoints.end(),cComp);
 
            while((fSumwTemp < fBinContent/2) && (cut != middle-1))
            {
               fSumwTemp += (*cut)->GetWeight();
               ++cut;
            }
            first = middle;
         }
 
         return cut;
      }
 
//______________________________________________________________________________
      template<class _DataPoint>
      void KDTree<_DataPoint>::TerminalNode::UpdateBoundaries()
      {
         //updates the boundaries of this bin and caches them
         //
         //Note: - In a high-dimensional space most of the nodes are bounded only on
         //        one side due to a split. One-sided intervals would result in an
         //        infinite volume of the bin which is not the desired behaviour.
         //        Therefore the following convention is used for determining the
         //        boundaries:
         //        If a node is not restricted along one axis on one/both side(s) due
         //        to a split, the corresponding upper/lower boundary is set to
         //        the minimum/maximum coordinate along this axis of all contained
         //        data points.
         //        This procedure maximises the density in the bins.
 
         const value_type fMAX = 0.4 * std::numeric_limits<value_type>::max();
         const value_type fMIN = -1.0 * fMAX;
 
         this->fBoundaries = std::vector<tBoundary>(Dimension(),std::make_pair(fMIN,fMAX));
 
         //walk back the tree and update bounds
         const BaseNode* pNode = this->Parent();
         const SplitNode* pSplit = 0;
         const Cut* pCut = 0;
         bool bLeft = this->IsLeftChild();
         while(!pNode->IsHeadNode())
         {
            pSplit = dynamic_cast<const SplitNode*>(pNode);
            assert(pSplit);
            pCut = pSplit->GetCut();
            // left subtree -> cut is upper bound
            if(bLeft)
               this->fBoundaries.at(pCut->GetAxis()).second = std::min(pCut->GetCutValue(),this->fBoundaries.at(pCut->GetAxis()).second);
            // right subtree -> cut is lower bound
            else
               this->fBoundaries.at(pCut->GetAxis()).first = std::max(pCut->GetCutValue(),this->fBoundaries.at(pCut->GetAxis()).first);
 
            bLeft = pNode->IsLeftChild();
            pNode = pNode->Parent();
         }
 
         // if there are some data points in this bucket, use their minimum/maximum values to define the open boundaries
         if(fDataPoints.size())
         {
            // loop over bounds and set unspecified values to minimum/maximum coordinate of all points in this bucket
            for(UInt_t dim = 0; dim < this->fBoundaries.size(); ++dim)
            {
               // check lower bound
               if(this->fBoundaries.at(dim).first < 0.8*fMIN)
               {
                  this->fBoundaries.at(dim).first = fMAX;
                  // look for smallest coordinate along axis 'dim'
                  for(typename std::vector<const _DataPoint*>::const_iterator it = fDataPoints.begin();
                      it != fDataPoints.end(); ++it)
                  {
                     if((*it)->GetCoordinate(dim) < this->fBoundaries.at(dim).first)
                        this->fBoundaries.at(dim).first = (*it)->GetCoordinate(dim);
                  }
               }
               // check upper bound
               if(this->fBoundaries.at(dim).second > 0.8*fMAX)
               {
                  this->fBoundaries.at(dim).second = fMIN;
                  // look for biggest coordinate along axis 'dim'
                  for(typename std::vector<const _DataPoint*>::const_iterator it = fDataPoints.begin();
                      it != fDataPoints.end(); ++it)
                  {
                     if((*it)->GetCoordinate(dim) > this->fBoundaries.at(dim).second)
                        this->fBoundaries.at(dim).second = (*it)->GetCoordinate(dim);
                  }
               }
            }
         }
      }
 
//______________________________________________________________________________
      template<class _DataPoint>
      inline typename KDTree<_DataPoint>::iterator& KDTree<_DataPoint>::iterator::operator++()
      {
         //pre-increment operator
 
         fBin = Next();
         return *this;
      }
 
//______________________________________________________________________________
      template<class _DataPoint>
      inline const typename KDTree<_DataPoint>::iterator& KDTree<_DataPoint>::iterator::operator++() const
      {
         //pre-increment operator
 
         fBin = Next();
         return *this;
      }
 
//______________________________________________________________________________
      template<class _DataPoint>
      inline typename KDTree<_DataPoint>::iterator KDTree<_DataPoint>::iterator::operator++(int)
      {
         //post-increment operator
 
         iterator tmp(*this);
         fBin = Next();
         return tmp;
      }
 
//______________________________________________________________________________
      template<class _DataPoint>
      inline const typename KDTree<_DataPoint>::iterator KDTree<_DataPoint>::iterator::operator++(int) const
      {
         //post-increment operator
 
         iterator tmp(*this);
         fBin = Next();
         return tmp;
      }
 
//______________________________________________________________________________
      template<class _DataPoint>
      inline typename KDTree<_DataPoint>::iterator& KDTree<_DataPoint>::iterator::operator--()
      {
         //pre-decrement operator
 
         fBin = Previous();
         return *this;
      }
 
//______________________________________________________________________________
      template<class _DataPoint>
      inline const typename KDTree<_DataPoint>::iterator& KDTree<_DataPoint>::iterator::operator--() const
      {
         //pre-decrement operator
 
         fBin = Previous();
         return *this;
      }
 
//______________________________________________________________________________
      template<class _DataPoint>
      inline typename KDTree<_DataPoint>::iterator KDTree<_DataPoint>::iterator::operator--(int)
      {
         //post-decrement operator
 
         iterator tmp(*this);
         fBin = Previous();
         return tmp;
      }
 
//______________________________________________________________________________
      template<class _DataPoint>
      inline const typename KDTree<_DataPoint>::iterator KDTree<_DataPoint>::iterator::operator--(int) const
      {
         //post-decrement operator
 
         iterator tmp(*this);
         fBin = Previous();
         return tmp;
      }
 
//______________________________________________________________________________
      template<class _DataPoint>
      inline typename KDTree<_DataPoint>::iterator& KDTree<_DataPoint>::iterator::operator=(const typename KDTree<_DataPoint>::iterator& rhs)
      {
         //assignment operator
 
         fBin = rhs.fBin;
         return *this;
      }
 
//______________________________________________________________________________
      template<class _DataPoint>
      typename KDTree<_DataPoint>::BinNode* KDTree<_DataPoint>::iterator::Next() const
      {
         //advance this iterator to the next bin
         //
         //Note: - Check for the end of all bins by comparing to End().
 
         BaseNode* pNode = fBin;
 
         while(!pNode->IsHeadNode())
         {
            if(pNode->IsLeftChild())
            {
               assert(pNode->Parent()->RightChild());
               pNode = pNode->Parent()->RightChild();
               while(pNode->LeftChild())
                  pNode = pNode->LeftChild();
 
               assert(dynamic_cast<BinNode*>(pNode));
               return (BinNode*)pNode;
            }
            else
               pNode = pNode->Parent();
         }
 
         return 0;
      }
 
//______________________________________________________________________________
      template<class _DataPoint>
      typename KDTree<_DataPoint>::BinNode* KDTree<_DataPoint>::iterator::Previous() const
      {
         //decline this iterator to the previous bin
         //
         //Note: - Check for the end of all bins by comparing to End().
 
         BaseNode* pNode = fBin;
 
         while(!pNode->IsHeadNode())
         {
            if(pNode->Parent()->RightChild() == pNode)
            {
               assert(pNode->Parent()->LeftChild());
               pNode = pNode->Parent()->LeftChild();
               while(pNode->RightChild())
                  pNode = pNode->RightChild();
 
               assert(dynamic_cast<BinNode*>(pNode));
               return (BinNode*)pNode;
            }
            else
               pNode = pNode->Parent();
         }
 
         return 0;
      }
 
   }//namespace Math
}//namespace ROOT
 
#endif //KD_TREE_ICC