// @(#):$Id$
// Author: Andrei Gheata   01/03/11

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

////////////////////////////////////////////////////////////////////////////
//
// TGeoBranchArray - An array of daughter indices making a geometry path.
//   Can be used to backup/restore a state. To setup an object of this type,
// one should use:
//   TGeoBranchArray *array = new TGeoBranchArray(level);
//   array->InitFromNavigator(nav); (To initialize from current navigator state)
// The navigator can be updated to reflect this path array:
//   array->UpdateNavigator();
//
/////////////////////////////////////////////////////////////////////////////

#include "TGeoBranchArray.h"

#include "TMath.h"
#include "TThread.h"
#include "TString.h"
#include "TGeoMatrix.h"
#include "TGeoNavigator.h"
#include "TGeoCache.h"
#include "TGeoManager.h"

ClassImp(TGeoBranchArray)

//______________________________________________________________________________
TGeoBranchArray::TGeoBranchArray(Int_t level)
                :fLevel(level),
                 fMaxLevel(0),
                 fArray(NULL),
                 fMatrix(NULL),
                 fClient(NULL)
{
// Constructor. Alocates the array with a size given by level.
   fMaxLevel = (fLevel+1 > 10) ? fLevel+1:10;
   fArray = new TGeoNode*[fMaxLevel];
   fMatrix = new TGeoHMatrix();
}

//______________________________________________________________________________
TGeoBranchArray::~TGeoBranchArray()
{
// Destructor.
   delete [] fArray;
   delete fMatrix;
}

//______________________________________________________________________________
TGeoBranchArray::TGeoBranchArray(const TGeoBranchArray&  other)
                :TObject(other),
                 fLevel(other.fLevel),
                 fMaxLevel(other.fMaxLevel),
                 fArray(NULL),
                 fMatrix(NULL),
                 fClient(other.fClient)
{
// Copy constructor.
   if (fMaxLevel) {
      fArray = new TGeoNode*[fMaxLevel];
      if (fLevel+1) memcpy(fArray, other.fArray, (fLevel+1)*sizeof(TGeoNode*));
   }
   if (other.fMatrix) fMatrix = new TGeoHMatrix(*(other.fMatrix));
}

//______________________________________________________________________________
TGeoBranchArray& TGeoBranchArray::operator=(const TGeoBranchArray& other)
{
// Assignment.
   if (&other == this) return *this;
//   TThread::Lock();
   TObject::operator=(other);
   // Check if the array exists and has to be resized
   if (fArray) {
      if (fMaxLevel<other.fLevel+1) {
         fMaxLevel = other.fMaxLevel;
         delete [] fArray;
         fArray = new TGeoNode*[fMaxLevel];
      }
   } else {
      fMaxLevel = other.fMaxLevel;
      fArray = new TGeoNode*[fMaxLevel];
   }
   fLevel = other.fLevel;
   if (fLevel+1) memcpy(fArray, other.fArray, (fLevel+1)*sizeof(TGeoNode*));
   if (other.fMatrix) {
      if (!fMatrix) fMatrix = new TGeoHMatrix();
      fMatrix->CopyFrom(other.fMatrix);
   }
   fClient = other.fClient;
//   TThread::UnLock();
   return *this;
}

//______________________________________________________________________________
void TGeoBranchArray::AddLevel(Int_t dindex)
{
// Add and extra daughter to the current path array. No validity check performed !
   if (fLevel<=0) {
      Error("AddLevel", "You must initialize from navigator or copy from another branch array first.");
      return;
   }
   fLevel++;
   if (fLevel+1>fMaxLevel) {
      TGeoNode **array = new TGeoNode*[fLevel+1];
      memcpy(array, fArray, fLevel*sizeof(TGeoNode*));
      delete [] fArray;
      fArray = array;
   }
   fArray[fLevel] = fArray[fLevel-1]->GetVolume()->GetNode(dindex);
}

//______________________________________________________________________________
Bool_t TGeoBranchArray::operator ==(const TGeoBranchArray& other) const
{
// Is equal operator.
   Int_t value = Compare(&other);
   if (value==0) return kTRUE;
   return kFALSE;
}

//______________________________________________________________________________
Bool_t TGeoBranchArray::operator !=(const TGeoBranchArray& other) const
{
// Not equal operator.
   Int_t value = Compare(&other);
   if (value!=0) return kTRUE;
   return kFALSE;
}

//______________________________________________________________________________
Bool_t TGeoBranchArray::operator >(const TGeoBranchArray& other) const
{
// Is equal operator.
   Int_t value = Compare(&other);
   if (value>0) return kTRUE;
   return kFALSE;
}

//______________________________________________________________________________
Bool_t TGeoBranchArray::operator <(const TGeoBranchArray& other) const
{
// Is equal operator.
   Int_t value = Compare(&other);
   if (value<0) return kTRUE;
   return kFALSE;
}

//______________________________________________________________________________
Bool_t TGeoBranchArray::operator >=(const TGeoBranchArray& other) const
{
// Is equal operator.
   Int_t value = Compare(&other);
   if (value>=0) return kTRUE;
   return kFALSE;
}

//______________________________________________________________________________
Bool_t TGeoBranchArray::operator <=(const TGeoBranchArray& other) const
{
// Is equal operator.
   Int_t value = Compare(&other);
   if (value<=0) return kTRUE;
   return kFALSE;
}

//______________________________________________________________________________
Long64_t TGeoBranchArray::BinarySearch(Long64_t n, const TGeoBranchArray **array, TGeoBranchArray *value)
{
// Binary search in an array of n pointers to branch arrays, to locate value.
// Returns element index or index of nearest element smaller than value
   Long64_t nabove, nbelow, middle;
   const TGeoBranchArray *pind;
   nabove = n+1;
   nbelow = 0;
   while(nabove-nbelow > 1) {
      middle = (nabove+nbelow)/2;
      pind = array[middle-1];
      if (*value == *pind) return middle-1;
      if (*value  < *pind) nabove = middle;
      else                          nbelow = middle;
   }
   return nbelow-1;
}

//______________________________________________________________________________
Int_t TGeoBranchArray::Compare(const TObject *obj) const
{
// Compare with other object of same type. Returns -1 if this is smaller (first
// smaller array value prevails), 0 if equal (size and values) and 1 if this is
// larger.
   Int_t i;
   TGeoBranchArray *other = (TGeoBranchArray*)obj;
   Int_t otherLevel = other->GetLevel();
   Int_t maxLevel = TMath::Min(fLevel, otherLevel);
   TGeoNode **otherArray = other->GetArray();
   for (i=0; i<maxLevel+1; i++) {
      if (fArray[i]==otherArray[i]) continue;
      if ((Long64_t)fArray[i]<(Long64_t)otherArray[i]) return -1;
      return 1;
   }
   if (fLevel==otherLevel) return 0;
   if (fLevel<otherLevel) return -1;
   return 1;
}

//______________________________________________________________________________
void TGeoBranchArray::CleanMatrix()
{
// Garbage collect the stored matrix.
   delete fMatrix; fMatrix = 0;
}

//______________________________________________________________________________
void TGeoBranchArray::Init(TGeoNode **branch, TGeoMatrix *global, Int_t level)
{
// Init the branch array from an array of nodes, the global matrix for the path and
// the level.
   if (!fMatrix) fMatrix = new TGeoHMatrix();
   fMatrix->CopyFrom(global);
   if (!fArray || level+1>fMaxLevel) {
      delete [] fArray;
      fMaxLevel = level+1;
      fArray = new TGeoNode*[fMaxLevel];
   }
   fLevel = level;
   memcpy(fArray, branch, (fLevel+1)*sizeof(TGeoNode*));
}

//______________________________________________________________________________
void TGeoBranchArray::InitFromNavigator(TGeoNavigator *nav)
{
// Init the branch array from current navigator state.
   TGeoNodeCache *cache = nav->GetCache();
   const TGeoNode **branch = (const TGeoNode**)cache->GetBranch();
   Int_t level = cache->GetLevel();
   if (!fMatrix) fMatrix = new TGeoHMatrix();
   fMatrix->CopyFrom(cache->GetCurrentMatrix());
   if (!fArray || level+1>fMaxLevel) {
      delete [] fArray;
      fMaxLevel = level+1;
      fArray = new TGeoNode*[fMaxLevel];
   }
   fLevel = level;
   memcpy(fArray, branch, (fLevel+1)*sizeof(TGeoNode*));
   if (nav->IsOutside()) fLevel = -1;
}

//______________________________________________________________________________
void TGeoBranchArray::GetPath(TString &path) const
{
// Fill path pointed by the array.
   path = "";
   if (!fArray) return;
   for (Int_t i=0; i<fLevel+1; i++) {
      path += "/";
      path += fArray[i]->GetName();
   }
}

//______________________________________________________________________________
void TGeoBranchArray::Print(Option_t *) const
{
// Print branch information
   TString path;
   GetPath(path);
   printf("branch:    %s\n", path.Data());
}

//______________________________________________________________________________
void TGeoBranchArray::Sort(Int_t n, TGeoBranchArray **array, Int_t *index, Bool_t down)
{
// Sorting of an array of branch array pointers.
   for (Int_t i=0; i<n; i++) index[i] = i;
   if (down)
      std::sort(index, index + n, compareBAdesc(array));
   else
      std::sort(index, index + n, compareBAasc(array));
}

//______________________________________________________________________________
void TGeoBranchArray::UpdateNavigator(TGeoNavigator *nav) const
{
// Update the navigator to reflect the branch.
   nav->CdTop();
   if (fLevel<0) {nav->SetOutside(kTRUE); return;}
   for (Int_t i=1; i<fLevel+1; i++) nav->CdDown(fArray[i]);
}
 TGeoBranchArray.cxx:1
 TGeoBranchArray.cxx:2
 TGeoBranchArray.cxx:3
 TGeoBranchArray.cxx:4
 TGeoBranchArray.cxx:5
 TGeoBranchArray.cxx:6
 TGeoBranchArray.cxx:7
 TGeoBranchArray.cxx:8
 TGeoBranchArray.cxx:9
 TGeoBranchArray.cxx:10
 TGeoBranchArray.cxx:11
 TGeoBranchArray.cxx:12
 TGeoBranchArray.cxx:13
 TGeoBranchArray.cxx:14
 TGeoBranchArray.cxx:15
 TGeoBranchArray.cxx:16
 TGeoBranchArray.cxx:17
 TGeoBranchArray.cxx:18
 TGeoBranchArray.cxx:19
 TGeoBranchArray.cxx:20
 TGeoBranchArray.cxx:21
 TGeoBranchArray.cxx:22
 TGeoBranchArray.cxx:23
 TGeoBranchArray.cxx:24
 TGeoBranchArray.cxx:25
 TGeoBranchArray.cxx:26
 TGeoBranchArray.cxx:27
 TGeoBranchArray.cxx:28
 TGeoBranchArray.cxx:29
 TGeoBranchArray.cxx:30
 TGeoBranchArray.cxx:31
 TGeoBranchArray.cxx:32
 TGeoBranchArray.cxx:33
 TGeoBranchArray.cxx:34
 TGeoBranchArray.cxx:35
 TGeoBranchArray.cxx:36
 TGeoBranchArray.cxx:37
 TGeoBranchArray.cxx:38
 TGeoBranchArray.cxx:39
 TGeoBranchArray.cxx:40
 TGeoBranchArray.cxx:41
 TGeoBranchArray.cxx:42
 TGeoBranchArray.cxx:43
 TGeoBranchArray.cxx:44
 TGeoBranchArray.cxx:45
 TGeoBranchArray.cxx:46
 TGeoBranchArray.cxx:47
 TGeoBranchArray.cxx:48
 TGeoBranchArray.cxx:49
 TGeoBranchArray.cxx:50
 TGeoBranchArray.cxx:51
 TGeoBranchArray.cxx:52
 TGeoBranchArray.cxx:53
 TGeoBranchArray.cxx:54
 TGeoBranchArray.cxx:55
 TGeoBranchArray.cxx:56
 TGeoBranchArray.cxx:57
 TGeoBranchArray.cxx:58
 TGeoBranchArray.cxx:59
 TGeoBranchArray.cxx:60
 TGeoBranchArray.cxx:61
 TGeoBranchArray.cxx:62
 TGeoBranchArray.cxx:63
 TGeoBranchArray.cxx:64
 TGeoBranchArray.cxx:65
 TGeoBranchArray.cxx:66
 TGeoBranchArray.cxx:67
 TGeoBranchArray.cxx:68
 TGeoBranchArray.cxx:69
 TGeoBranchArray.cxx:70
 TGeoBranchArray.cxx:71
 TGeoBranchArray.cxx:72
 TGeoBranchArray.cxx:73
 TGeoBranchArray.cxx:74
 TGeoBranchArray.cxx:75
 TGeoBranchArray.cxx:76
 TGeoBranchArray.cxx:77
 TGeoBranchArray.cxx:78
 TGeoBranchArray.cxx:79
 TGeoBranchArray.cxx:80
 TGeoBranchArray.cxx:81
 TGeoBranchArray.cxx:82
 TGeoBranchArray.cxx:83
 TGeoBranchArray.cxx:84
 TGeoBranchArray.cxx:85
 TGeoBranchArray.cxx:86
 TGeoBranchArray.cxx:87
 TGeoBranchArray.cxx:88
 TGeoBranchArray.cxx:89
 TGeoBranchArray.cxx:90
 TGeoBranchArray.cxx:91
 TGeoBranchArray.cxx:92
 TGeoBranchArray.cxx:93
 TGeoBranchArray.cxx:94
 TGeoBranchArray.cxx:95
 TGeoBranchArray.cxx:96
 TGeoBranchArray.cxx:97
 TGeoBranchArray.cxx:98
 TGeoBranchArray.cxx:99
 TGeoBranchArray.cxx:100
 TGeoBranchArray.cxx:101
 TGeoBranchArray.cxx:102
 TGeoBranchArray.cxx:103
 TGeoBranchArray.cxx:104
 TGeoBranchArray.cxx:105
 TGeoBranchArray.cxx:106
 TGeoBranchArray.cxx:107
 TGeoBranchArray.cxx:108
 TGeoBranchArray.cxx:109
 TGeoBranchArray.cxx:110
 TGeoBranchArray.cxx:111
 TGeoBranchArray.cxx:112
 TGeoBranchArray.cxx:113
 TGeoBranchArray.cxx:114
 TGeoBranchArray.cxx:115
 TGeoBranchArray.cxx:116
 TGeoBranchArray.cxx:117
 TGeoBranchArray.cxx:118
 TGeoBranchArray.cxx:119
 TGeoBranchArray.cxx:120
 TGeoBranchArray.cxx:121
 TGeoBranchArray.cxx:122
 TGeoBranchArray.cxx:123
 TGeoBranchArray.cxx:124
 TGeoBranchArray.cxx:125
 TGeoBranchArray.cxx:126
 TGeoBranchArray.cxx:127
 TGeoBranchArray.cxx:128
 TGeoBranchArray.cxx:129
 TGeoBranchArray.cxx:130
 TGeoBranchArray.cxx:131
 TGeoBranchArray.cxx:132
 TGeoBranchArray.cxx:133
 TGeoBranchArray.cxx:134
 TGeoBranchArray.cxx:135
 TGeoBranchArray.cxx:136
 TGeoBranchArray.cxx:137
 TGeoBranchArray.cxx:138
 TGeoBranchArray.cxx:139
 TGeoBranchArray.cxx:140
 TGeoBranchArray.cxx:141
 TGeoBranchArray.cxx:142
 TGeoBranchArray.cxx:143
 TGeoBranchArray.cxx:144
 TGeoBranchArray.cxx:145
 TGeoBranchArray.cxx:146
 TGeoBranchArray.cxx:147
 TGeoBranchArray.cxx:148
 TGeoBranchArray.cxx:149
 TGeoBranchArray.cxx:150
 TGeoBranchArray.cxx:151
 TGeoBranchArray.cxx:152
 TGeoBranchArray.cxx:153
 TGeoBranchArray.cxx:154
 TGeoBranchArray.cxx:155
 TGeoBranchArray.cxx:156
 TGeoBranchArray.cxx:157
 TGeoBranchArray.cxx:158
 TGeoBranchArray.cxx:159
 TGeoBranchArray.cxx:160
 TGeoBranchArray.cxx:161
 TGeoBranchArray.cxx:162
 TGeoBranchArray.cxx:163
 TGeoBranchArray.cxx:164
 TGeoBranchArray.cxx:165
 TGeoBranchArray.cxx:166
 TGeoBranchArray.cxx:167
 TGeoBranchArray.cxx:168
 TGeoBranchArray.cxx:169
 TGeoBranchArray.cxx:170
 TGeoBranchArray.cxx:171
 TGeoBranchArray.cxx:172
 TGeoBranchArray.cxx:173
 TGeoBranchArray.cxx:174
 TGeoBranchArray.cxx:175
 TGeoBranchArray.cxx:176
 TGeoBranchArray.cxx:177
 TGeoBranchArray.cxx:178
 TGeoBranchArray.cxx:179
 TGeoBranchArray.cxx:180
 TGeoBranchArray.cxx:181
 TGeoBranchArray.cxx:182
 TGeoBranchArray.cxx:183
 TGeoBranchArray.cxx:184
 TGeoBranchArray.cxx:185
 TGeoBranchArray.cxx:186
 TGeoBranchArray.cxx:187
 TGeoBranchArray.cxx:188
 TGeoBranchArray.cxx:189
 TGeoBranchArray.cxx:190
 TGeoBranchArray.cxx:191
 TGeoBranchArray.cxx:192
 TGeoBranchArray.cxx:193
 TGeoBranchArray.cxx:194
 TGeoBranchArray.cxx:195
 TGeoBranchArray.cxx:196
 TGeoBranchArray.cxx:197
 TGeoBranchArray.cxx:198
 TGeoBranchArray.cxx:199
 TGeoBranchArray.cxx:200
 TGeoBranchArray.cxx:201
 TGeoBranchArray.cxx:202
 TGeoBranchArray.cxx:203
 TGeoBranchArray.cxx:204
 TGeoBranchArray.cxx:205
 TGeoBranchArray.cxx:206
 TGeoBranchArray.cxx:207
 TGeoBranchArray.cxx:208
 TGeoBranchArray.cxx:209
 TGeoBranchArray.cxx:210
 TGeoBranchArray.cxx:211
 TGeoBranchArray.cxx:212
 TGeoBranchArray.cxx:213
 TGeoBranchArray.cxx:214
 TGeoBranchArray.cxx:215
 TGeoBranchArray.cxx:216
 TGeoBranchArray.cxx:217
 TGeoBranchArray.cxx:218
 TGeoBranchArray.cxx:219
 TGeoBranchArray.cxx:220
 TGeoBranchArray.cxx:221
 TGeoBranchArray.cxx:222
 TGeoBranchArray.cxx:223
 TGeoBranchArray.cxx:224
 TGeoBranchArray.cxx:225
 TGeoBranchArray.cxx:226
 TGeoBranchArray.cxx:227
 TGeoBranchArray.cxx:228
 TGeoBranchArray.cxx:229
 TGeoBranchArray.cxx:230
 TGeoBranchArray.cxx:231
 TGeoBranchArray.cxx:232
 TGeoBranchArray.cxx:233
 TGeoBranchArray.cxx:234
 TGeoBranchArray.cxx:235
 TGeoBranchArray.cxx:236
 TGeoBranchArray.cxx:237
 TGeoBranchArray.cxx:238
 TGeoBranchArray.cxx:239
 TGeoBranchArray.cxx:240
 TGeoBranchArray.cxx:241
 TGeoBranchArray.cxx:242
 TGeoBranchArray.cxx:243
 TGeoBranchArray.cxx:244
 TGeoBranchArray.cxx:245
 TGeoBranchArray.cxx:246
 TGeoBranchArray.cxx:247
 TGeoBranchArray.cxx:248
 TGeoBranchArray.cxx:249
 TGeoBranchArray.cxx:250
 TGeoBranchArray.cxx:251
 TGeoBranchArray.cxx:252
 TGeoBranchArray.cxx:253
 TGeoBranchArray.cxx:254
 TGeoBranchArray.cxx:255
 TGeoBranchArray.cxx:256
 TGeoBranchArray.cxx:257
 TGeoBranchArray.cxx:258
 TGeoBranchArray.cxx:259
 TGeoBranchArray.cxx:260
 TGeoBranchArray.cxx:261
 TGeoBranchArray.cxx:262
 TGeoBranchArray.cxx:263
 TGeoBranchArray.cxx:264
 TGeoBranchArray.cxx:265
 TGeoBranchArray.cxx:266
 TGeoBranchArray.cxx:267
 TGeoBranchArray.cxx:268
 TGeoBranchArray.cxx:269
 TGeoBranchArray.cxx:270
 TGeoBranchArray.cxx:271
 TGeoBranchArray.cxx:272
 TGeoBranchArray.cxx:273
 TGeoBranchArray.cxx:274
 TGeoBranchArray.cxx:275
 TGeoBranchArray.cxx:276
 TGeoBranchArray.cxx:277
 TGeoBranchArray.cxx:278
 TGeoBranchArray.cxx:279
 TGeoBranchArray.cxx:280
 TGeoBranchArray.cxx:281
 TGeoBranchArray.cxx:282
 TGeoBranchArray.cxx:283
 TGeoBranchArray.cxx:284
 TGeoBranchArray.cxx:285
 TGeoBranchArray.cxx:286
 TGeoBranchArray.cxx:287
 TGeoBranchArray.cxx:288
 TGeoBranchArray.cxx:289
 TGeoBranchArray.cxx:290
 TGeoBranchArray.cxx:291
 TGeoBranchArray.cxx:292
 TGeoBranchArray.cxx:293
 TGeoBranchArray.cxx:294
 TGeoBranchArray.cxx:295
 TGeoBranchArray.cxx:296
 TGeoBranchArray.cxx:297