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

#ifndef ROOT_TGeoBranchArray
#define ROOT_TGeoBranchArray

#ifndef ROOT_TObject
#include "TObject.h"
#endif

#ifndef ROOT_TGeoMatrix
#include "TGeoMatrix.h"
#endif

////////////////////////////////////////////////////////////////////////////
//                                                                        //
// TGeoBranchArray - An array of daughter indices making a geometry path. //
//   Can be used to backup/restore a state. Allocated contiguously in     //
//   memory.                                                              //
//                                                                        //
////////////////////////////////////////////////////////////////////////////

class TGeoNavigator;
class TGeoNode;

class TGeoBranchArray : public TObject
{
protected:
   Int_t             fLevel;          // Branch depth
   Int_t             fMaxLevel;       // Array length
   TGeoHMatrix       fMatrix;         // Global matrix (owned)
   TGeoNode        **fArray;          //![fMaxLevel+1] Array of nodes
   TGeoNode         *fRealArray[1];   // Beginning address of the array of nodes

private:
   TGeoBranchArray(Int_t level);                       // not allowed
   TGeoBranchArray(const TGeoBranchArray&);            // not allowed
public:
   enum EGeoBATypes {
      kBASelfAlloc =  BIT(14)             // does self allocation or not
   };   
   // This replaces the dummy constructor to make sure that I/O can be
   // performed while the user is only allowed to use the static maker
   TGeoBranchArray(TRootIOCtor*) : TObject(), fLevel(0), fMaxLevel(0), fMatrix(), fArray(0) {}

   // The static maker to be use to create an instance of the branch array
   static TGeoBranchArray *MakeInstance(size_t maxlevel);

   // The static maker to be use to create an instance of the branch array
   static TGeoBranchArray *MakeInstanceAt(size_t maxlevel, void *addr);

   // The equivalent of the copy constructor
   static TGeoBranchArray *MakeCopy(const TGeoBranchArray &other);

   // The equivalent of the copy constructor
   static TGeoBranchArray *MakeCopyAt(const TGeoBranchArray &other, void *addr);

   // The equivalent of the destructor
   static void             ReleaseInstance(TGeoBranchArray *obj);

   // Assignment allowed
   TGeoBranchArray& operator=(const TGeoBranchArray&);

   // Fast copy based on memcpy to destination array
   void                    CopyTo(TGeoBranchArray *dest);
   
   // Equivalent of sizeof function
   static size_t SizeOf(size_t maxlevel)
      { return (sizeof(TGeoBranchArray)+sizeof(TGeoBranchArray*)*(maxlevel)); }

   // Equivalent of sizeof function
   static size_t SizeOfInstance(size_t maxlevel)
      { return (sizeof(TGeoBranchArray)+sizeof(TGeoBranchArray*)*(maxlevel)); }

   inline size_t SizeOf() const
      { return (sizeof(TGeoBranchArray)+sizeof(TGeoBranchArray*)*(fMaxLevel)); }
   
   // The data start should point to the address of the first data member,
   // after the virtual table
   void       *DataStart() const {return (void*)&fLevel;}

   // The actual size of the data for an instance, excluding the virtual table
   size_t      DataSize() const {return SizeOf()-size_t(&fLevel)+(size_t)this;}

   // Update the internal addresses of n contiguous branch array objects, starting
   // with this one
   void UpdateArray(size_t nobj);

   // Destructor. Release instance to be called instead
   virtual ~TGeoBranchArray() {}

   Bool_t operator ==(const TGeoBranchArray& other) const;
   Bool_t operator !=(const TGeoBranchArray& other) const;
   Bool_t operator >(const TGeoBranchArray& other) const;
   Bool_t operator <(const TGeoBranchArray& other) const;
   Bool_t operator >=(const TGeoBranchArray& other) const;
   Bool_t operator <=(const TGeoBranchArray& other) const;

   void              AddLevel(Int_t dindex);
   static Long64_t   BinarySearch(Long64_t n, const TGeoBranchArray **array, TGeoBranchArray *value);
   virtual Int_t     Compare(const TObject *obj) const;
   void              CleanMatrix();
   TGeoNode        **GetArray() const    {return fArray;}
   size_t            GetLevel() const    {return fLevel;}
   size_t            GetMaxLevel() const {return fMaxLevel;}
   const TGeoHMatrix  
                    *GetMatrix() const  {return &fMatrix;}
   TGeoNode         *GetNode(Int_t level) const {return fArray[level];}
   TGeoNode         *GetCurrentNode() const {return fArray[fLevel];}
   void              GetPath(TString &path) const;
   void              Init(TGeoNode **branch, TGeoMatrix *global, Int_t level);
   void              InitFromNavigator(TGeoNavigator *nav);
   virtual Bool_t    IsSortable() const {return kTRUE;}
   Bool_t            IsOutside() const {return (fLevel<0)?kTRUE:kFALSE;}
   virtual void      Print(Option_t *option="") const;
   static void       Sort(Int_t n, TGeoBranchArray **array, Int_t *index, Bool_t down=kTRUE);
   void              UpdateNavigator(TGeoNavigator *nav) const;
   
   ClassDef(TGeoBranchArray, 4)
};

struct compareBAasc {
   compareBAasc(TGeoBranchArray **d) : fData(d) {}
   bool operator ()(Int_t i1, Int_t i2) {return **(fData+i1) < **(fData+i2);}
   TGeoBranchArray **fData;
};

struct compareBAdesc {
   compareBAdesc(TGeoBranchArray **d) : fData(d) {}
   bool operator ()(Int_t i1, Int_t i2) {return **(fData+i1) > **(fData+i2);}
   TGeoBranchArray **fData;
};

#endif
 TGeoBranchArray.h:1
 TGeoBranchArray.h:2
 TGeoBranchArray.h:3
 TGeoBranchArray.h:4
 TGeoBranchArray.h:5
 TGeoBranchArray.h:6
 TGeoBranchArray.h:7
 TGeoBranchArray.h:8
 TGeoBranchArray.h:9
 TGeoBranchArray.h:10
 TGeoBranchArray.h:11
 TGeoBranchArray.h:12
 TGeoBranchArray.h:13
 TGeoBranchArray.h:14
 TGeoBranchArray.h:15
 TGeoBranchArray.h:16
 TGeoBranchArray.h:17
 TGeoBranchArray.h:18
 TGeoBranchArray.h:19
 TGeoBranchArray.h:20
 TGeoBranchArray.h:21
 TGeoBranchArray.h:22
 TGeoBranchArray.h:23
 TGeoBranchArray.h:24
 TGeoBranchArray.h:25
 TGeoBranchArray.h:26
 TGeoBranchArray.h:27
 TGeoBranchArray.h:28
 TGeoBranchArray.h:29
 TGeoBranchArray.h:30
 TGeoBranchArray.h:31
 TGeoBranchArray.h:32
 TGeoBranchArray.h:33
 TGeoBranchArray.h:34
 TGeoBranchArray.h:35
 TGeoBranchArray.h:36
 TGeoBranchArray.h:37
 TGeoBranchArray.h:38
 TGeoBranchArray.h:39
 TGeoBranchArray.h:40
 TGeoBranchArray.h:41
 TGeoBranchArray.h:42
 TGeoBranchArray.h:43
 TGeoBranchArray.h:44
 TGeoBranchArray.h:45
 TGeoBranchArray.h:46
 TGeoBranchArray.h:47
 TGeoBranchArray.h:48
 TGeoBranchArray.h:49
 TGeoBranchArray.h:50
 TGeoBranchArray.h:51
 TGeoBranchArray.h:52
 TGeoBranchArray.h:53
 TGeoBranchArray.h:54
 TGeoBranchArray.h:55
 TGeoBranchArray.h:56
 TGeoBranchArray.h:57
 TGeoBranchArray.h:58
 TGeoBranchArray.h:59
 TGeoBranchArray.h:60
 TGeoBranchArray.h:61
 TGeoBranchArray.h:62
 TGeoBranchArray.h:63
 TGeoBranchArray.h:64
 TGeoBranchArray.h:65
 TGeoBranchArray.h:66
 TGeoBranchArray.h:67
 TGeoBranchArray.h:68
 TGeoBranchArray.h:69
 TGeoBranchArray.h:70
 TGeoBranchArray.h:71
 TGeoBranchArray.h:72
 TGeoBranchArray.h:73
 TGeoBranchArray.h:74
 TGeoBranchArray.h:75
 TGeoBranchArray.h:76
 TGeoBranchArray.h:77
 TGeoBranchArray.h:78
 TGeoBranchArray.h:79
 TGeoBranchArray.h:80
 TGeoBranchArray.h:81
 TGeoBranchArray.h:82
 TGeoBranchArray.h:83
 TGeoBranchArray.h:84
 TGeoBranchArray.h:85
 TGeoBranchArray.h:86
 TGeoBranchArray.h:87
 TGeoBranchArray.h:88
 TGeoBranchArray.h:89
 TGeoBranchArray.h:90
 TGeoBranchArray.h:91
 TGeoBranchArray.h:92
 TGeoBranchArray.h:93
 TGeoBranchArray.h:94
 TGeoBranchArray.h:95
 TGeoBranchArray.h:96
 TGeoBranchArray.h:97
 TGeoBranchArray.h:98
 TGeoBranchArray.h:99
 TGeoBranchArray.h:100
 TGeoBranchArray.h:101
 TGeoBranchArray.h:102
 TGeoBranchArray.h:103
 TGeoBranchArray.h:104
 TGeoBranchArray.h:105
 TGeoBranchArray.h:106
 TGeoBranchArray.h:107
 TGeoBranchArray.h:108
 TGeoBranchArray.h:109
 TGeoBranchArray.h:110
 TGeoBranchArray.h:111
 TGeoBranchArray.h:112
 TGeoBranchArray.h:113
 TGeoBranchArray.h:114
 TGeoBranchArray.h:115
 TGeoBranchArray.h:116
 TGeoBranchArray.h:117
 TGeoBranchArray.h:118
 TGeoBranchArray.h:119
 TGeoBranchArray.h:120
 TGeoBranchArray.h:121
 TGeoBranchArray.h:122
 TGeoBranchArray.h:123
 TGeoBranchArray.h:124
 TGeoBranchArray.h:125
 TGeoBranchArray.h:126
 TGeoBranchArray.h:127
 TGeoBranchArray.h:128
 TGeoBranchArray.h:129
 TGeoBranchArray.h:130
 TGeoBranchArray.h:131
 TGeoBranchArray.h:132
 TGeoBranchArray.h:133
 TGeoBranchArray.h:134
 TGeoBranchArray.h:135
 TGeoBranchArray.h:136
 TGeoBranchArray.h:137
 TGeoBranchArray.h:138
 TGeoBranchArray.h:139
 TGeoBranchArray.h:140
 TGeoBranchArray.h:141
 TGeoBranchArray.h:142