    // @(#)root/tree:$Name:  $:$Id: TChainIndex.cxx,v 1.3 2005/06/28 16:49:45 brun Exp $
    // Author: Marek Biskup   07/06/2005

    /*************************************************************************
     * Copyright (C) 1995-2004, Rene Brun and Fons Rademakers.               *
     * All rights reserved.                                                  *
     *                                                                       *
     * For the licensing terms see $ROOTSYS/LICENSE.                         *
     * For the list of contributors see $ROOTSYS/README/CREDITS.             *
     *************************************************************************/

    //////////////////////////////////////////////////////////////////////////
    //
    // A Chain Index
    //
    //////////////////////////////////////////////////////////////////////////

    #include "TChainIndex.h"
    #include "TChain.h"
    #include "TError.h"

    ClassImp(TChainIndex)

    //______________________________________________________________________________
     TChainIndex::TChainIndex(): TVirtualIndex()
    {
    // Default constructor for TChainIndex

       fTree = 0;
       fMajorFormulaParent = fMinorFormulaParent = 0;
    }

    //______________________________________________________________________________
     TChainIndex::TChainIndex(const TTree *T, const char *majorname, const char *minorname)
               : TVirtualIndex()
    {
       // Normal constructor for TChainIndex. See TTreeIndex::TTreeIndex for the description of the
       // parameters.
       // The tree must be a TChain.
       // All the index values in the first tree of the chain must be
       // less then any index value in the second one, and so on.
       // If any of those requirements isn't met the object becomes a zombie.
       // If some subtrees don't have indices the indices are created and stored inside this
       // TChainIndex.

       fTree = 0;
       fMajorFormulaParent = fMinorFormulaParent = 0;

       TChain *chain = dynamic_cast<TChain*>(const_cast<TTree*>(T));
       if (!chain) {
          MakeZombie();
          Error("TChainIndex", "Cannot create a TChainIndex."
                " The Tree passed as an argument is not a TChain");
          return;
       }

       fTree               = (TTree*)T;
       fMajorName          = majorname;
       fMinorName          = minorname;
       Int_t i = 0;

       // Go through all the trees and check if they have indeces. If not then build them.
       for (i = 0; i < chain->GetNtrees(); i++) {
          ChainIndexEntry_t entry;
          chain->LoadTree((chain->GetTreeOffset())[i]);
          TVirtualIndex *index = chain->GetTree()->GetTreeIndex();
          entry.fTreeIndex = 0;
          if (!index) {
             chain->GetTree()->BuildIndex(majorname, minorname);
             index = chain->GetTree()->GetTreeIndex();
             chain->GetTree()->SetTreeIndex(0);
             entry.fTreeIndex = index;
          }
          if (!index || index->IsZombie() || index->GetN() == 0) {
             DeleteIndices();
             MakeZombie();
             Error("TChainIndex", "Error creating a tree index on a tree in the chain");
          }
          Assert(dynamic_cast<TTreeIndex*>(index));
          entry.fMinIndexValue = dynamic_cast<TTreeIndex*>(index)->GetIndexValues()[0];
          entry.fMaxIndexValue = dynamic_cast<TTreeIndex*>(index)->GetIndexValues()[index->GetN() - 1];

          fEntries.push_back(entry);
       }
       // Check if the indices of different trees are in order. If not then return an error.
       for (i = 0; i < Int_t(fEntries.size() - 1); i++) {
          if (fEntries[i].fMaxIndexValue > fEntries[i+1].fMinIndexValue) {
             DeleteIndices();
             MakeZombie();
             Error("TChainIndex", "The indices in files of this chain aren't sorted.");
          }
       }
    }

    //______________________________________________________________________________
     void TChainIndex::DeleteIndices()
    {
       // Delete all the indices which were built by this object
       for (unsigned int i = 0; i < fEntries.size(); i++) {
          if (fEntries[i].fTreeIndex) {
             if (fTree->GetTree()->GetTreeIndex() == fEntries[i].fTreeIndex) {
                fTree->GetTree()->SetTreeIndex(0);
             }
             SafeDelete(fEntries[i].fTreeIndex);
          }
       }
    }

    //______________________________________________________________________________
     TChainIndex::~TChainIndex()
    {
       // The destructor.
       if (fTree && fTree->GetTreeIndex() == this)
          fTree->SetTreeIndex(0);
       DeleteIndices();
    }

    //______________________________________________________________________________
    std::pair<TVirtualIndex*, Int_t> TChainIndex::GetSubTreeIndex(Int_t major, Int_t minor) const
    {
       // returns a TVirtualIndex for a tree which holds the entry with the specified
       // major and minor values and the number of that tree.
       // If the index for that tree was created by this object it's set to the tree.
       // The tree index should be later released using ReleaseSubTreeIndex();

       using namespace std;
       if (fEntries.size() == 0) {
          Warning("GetSubTreeIndex", "No subindices in the chain. The chain is probably empty");
          return make_pair(static_cast<TVirtualIndex*>(0), 0);
       }

       Long64_t indexValue = (Long64_t(major) << 31) + minor;

       if (indexValue < fEntries[0].fMinIndexValue) {
          Warning("GetSubTreeIndex", "The index value is less than the smallest index values in subtrees");
          return make_pair(static_cast<TVirtualIndex*>(0), 0);
       }

       Int_t treeNo = fEntries.size() - 1;
       for (unsigned int i = 0; i < fEntries.size() - 1; i++)
          if (indexValue < fEntries[i+1].fMinIndexValue) {
             treeNo = i;
             break;
          }
       TChain* chain = dynamic_cast<TChain*> (fTree);
       Assert(chain);
       chain->LoadTree(chain->GetTreeOffset()[treeNo]);
       TVirtualIndex* index =  fTree->GetTree()->GetTreeIndex();
       if (index)
          return make_pair(static_cast<TVirtualIndex*>(index), treeNo);
       else {
          index = fEntries[treeNo].fTreeIndex;
          if (!index) {
             Warning("GetSubTreeIndex", "The tree has no index and the chain index"
                      " doesn't store an index for that tree");
             return make_pair(static_cast<TVirtualIndex*>(0), 0);
          }
          else {
             fTree->GetTree()->SetTreeIndex(index);
             return make_pair(static_cast<TVirtualIndex*>(index), treeNo);
          }
       }
    }

    //______________________________________________________________________________
     void TChainIndex::ReleaseSubTreeIndex(TVirtualIndex* index, int treeNo) const
    {
       // Releases the tree index got using GetSubTreeIndex. If the index was
       // created by this object it is removed from the current tree, so that it isn't
       // deleted in its destructor.

       if (fEntries[treeNo].fTreeIndex == index) {
          Assert(fTree->GetTree()->GetTreeIndex() == index);
          fTree->GetTree()->SetTreeIndex(0);
       }
    }

    //______________________________________________________________________________
     Int_t TChainIndex::GetEntryNumberFriend(const TTree *T)
    {
       // see TTreeIndex::GetEntryNumberFriend for description

       if (!T) return -3;
       GetMajorFormulaParent(T);
       GetMinorFormulaParent(T);
       if (!fMajorFormulaParent || !fMinorFormulaParent) return -1;
       if (!fMajorFormulaParent->GetNdim() || !fMinorFormulaParent->GetNdim()) {
          // The Tree Index in the friend has a pair majorname,minorname
          // not available in the parent Tree T.
          // if the friend Tree has less entries than the parent, this is an error
          Int_t pentry = T->GetReadEntry();
          if (pentry >= (Int_t)fTree->GetEntries()) return -2;
          // otherwise we ignore the Tree Index and return the entry number
          // in the parent Tree.
          return pentry;
       }

       // majorname, minorname exist in the parent Tree
       // we find the current values pair majorv,minorv in the parent Tree
       Double_t majord = fMajorFormulaParent->EvalInstance();
       Double_t minord = fMinorFormulaParent->EvalInstance();
       Long64_t majorv = (Long64_t)majord;
       Long64_t minorv = (Long64_t)minord;
       // we check if this pair exist in the index.
       // if yes, we return the corresponding entry number
       // if not the function returns -1
       return fTree->GetEntryNumberWithIndex(majorv,minorv);
    }

    //______________________________________________________________________________
     Long64_t TChainIndex::GetEntryNumberWithBestIndex(Int_t major, Int_t minor) const
    {
       // See TTreeIndex::GetEntryNumberWithBestIndex for details.

       std::pair<TVirtualIndex*, Int_t> indexAndNumber = GetSubTreeIndex(major, minor);
       if (!indexAndNumber.first) {
          Error("GetEntryNumberWithBestIndex","no index found");
          return -1;
       }
       else {
          Long64_t rv = indexAndNumber.first->GetEntryNumberWithBestIndex(major, minor);
          ReleaseSubTreeIndex(indexAndNumber.first, indexAndNumber.second);
          TChain* chain = dynamic_cast<TChain*> (fTree);
          Assert(chain);
          return rv + chain->GetTreeOffset()[indexAndNumber.second];
       }
    }

    //______________________________________________________________________________
     Long64_t TChainIndex::GetEntryNumberWithIndex(Int_t major, Int_t minor) const
    {
       // Returns the entry number with given index values.
       // See TTreeIndex::GetEntryNumberWithIndex for details.

       std::pair<TVirtualIndex*, Int_t> indexAndNumber = GetSubTreeIndex(major, minor);
       if (!indexAndNumber.first) {
          Error("GetEntryNumberWithIndex","no index found");
          return -1;
       }
       else {
          Long64_t rv = indexAndNumber.first->GetEntryNumberWithBestIndex(major, minor);
          ReleaseSubTreeIndex(indexAndNumber.first, indexAndNumber.second);
          TChain* chain = dynamic_cast<TChain*> (fTree);
          Assert(chain);
          return rv + chain->GetTreeOffset()[indexAndNumber.second];
       }
    }

    //______________________________________________________________________________
     TTreeFormula *TChainIndex::GetMajorFormulaParent(const TTree *T)
    {
       // return a pointer to the TreeFormula corresponding to the majorname in parent tree T

       if (!fMajorFormulaParent) {
          fMajorFormulaParent = new TTreeFormula("MajorP",fMajorName.Data(),(TTree*)T);
          fMajorFormulaParent->SetQuickLoad(kTRUE);
       }
       if (fMajorFormulaParent->GetTree() != T) {
          fMajorFormulaParent->SetTree((TTree*)T);
          fMajorFormulaParent->UpdateFormulaLeaves();
       }
       return fMajorFormulaParent;
    }

    //______________________________________________________________________________
     TTreeFormula *TChainIndex::GetMinorFormulaParent(const TTree *T)
    {
       // return a pointer to the TreeFormula corresponding to the minorname in parent tree T

       if (!fMinorFormulaParent) {
          fMinorFormulaParent = new TTreeFormula("MinorP",fMinorName.Data(),(TTree*)T);
          fMinorFormulaParent->SetQuickLoad(kTRUE);
       }
       if (fMinorFormulaParent->GetTree() != T) {
          fMinorFormulaParent->SetTree((TTree*)T);
          fMinorFormulaParent->UpdateFormulaLeaves();
       }

       return fMinorFormulaParent;
    }

    //______________________________________________________________________________
     void TChainIndex::UpdateFormulaLeaves()
    {
       // Updates the parent formulae.
       // Called by TChain::LoadTree when the parent chain changes it's tree.
       if (fMajorFormulaParent) { fMajorFormulaParent->UpdateFormulaLeaves();}
       if (fMinorFormulaParent) { fMinorFormulaParent->UpdateFormulaLeaves();}
    }

    //______________________________________________________________________________
     void TChainIndex::SetTree(const TTree *T)
    {
       // See TTreeIndex::SetTree.
       // Used only by the streamer.
       Assert(fTree == 0 || fTree == T);
    }