Moving the classes that belong to the following libraries: STEERBase, ESD, CDB, AOD...
[u/mrichter/AliRoot.git] / STEER / STEERBase / AliRefArray.h
1 #ifndef ALIREFARRAY_H
2 #define ALIREFARRAY_H
3 //_________________________________________________________________________
4 // 
5 //        Class for association of multiple UInt_t labels to array of UInt_t
6 //
7 // The use-case: reference from the clusterID to (multiple) trackID's using this cluster
8 // 
9 // ATTENTION: the references are provided as UInt_t, but maximum value should not exceed MAX_INT-1 (no check is done)
10 //
11 // Author: ruben.shahoyan@cern.ch
12 //_________________________________________________________________________
13
14 #include "TObject.h"
15
16 class AliRefArray : public TObject {
17  public:
18   AliRefArray();
19   AliRefArray(UInt_t nelem, UInt_t depth=0);
20   AliRefArray(const AliRefArray& src);
21   AliRefArray& operator=(const AliRefArray& src);
22   virtual ~AliRefArray();
23   //
24   UInt_t GetNElems()                                             const {return fNElems;}
25   void   Expand(UInt_t size=0);
26   Bool_t IsReferred(UInt_t from, UInt_t to)                      const;
27   Bool_t HasReference(UInt_t from)                               const {return (from>=fNElems||!fElems[from]) ? kFALSE:kTRUE;}
28   void   AddReference(UInt_t from, UInt_t to);
29   void   AddReferences(UInt_t from, UInt_t* refs, UInt_t nref);
30   UInt_t GetReferences(UInt_t from, UInt_t* refs, UInt_t maxRef) const;
31   Int_t  GetReference(UInt_t from, UInt_t which)                 const;
32   void   Reset();
33   void   Print(Option_t* opt="")                                 const;
34   void   Compactify();
35   //
36  protected:
37   void   ExpandReferences(Int_t addSize);
38   //
39  protected:
40   UInt_t        fNElems;               //   number of referrer elements
41   UInt_t        fRefSize;              //   current size of all references
42   Int_t*        fElems;                //[fNElems] array of referrers
43   UInt_t*       fRefInd;               //[fRefSize] indices of next referred node
44   UInt_t*       fRefBuff;              //[fRefSize] buffer of entries for referred nodes
45   ClassDef(AliRefArray,1)
46   //
47 };
48
49 //____________________________________________________________________
50 inline Bool_t AliRefArray::IsReferred(UInt_t from, UInt_t to)  const
51 {
52   // check if the cluster "to" is mentioned in the references of the cluster "from"
53   Int_t ref;
54   if (from>=fNElems || !(ref=fElems[from])) return kFALSE;
55   if (ref<0) {return (ref+int(to))==-1;}   // negative means just 1 reference: -(ref+1) is stored
56   to++;
57   do { if (fRefBuff[ref]==to) return kTRUE; } while((ref=fRefInd[ref])); // search intil no references left
58   return kFALSE;
59 }
60
61 //____________________________________________________________________
62 inline UInt_t AliRefArray::GetReferences(UInt_t from, UInt_t* refs, UInt_t maxRef) const
63 {
64   // extract max maxRef references for node "from" to user provided array refs
65   Int_t ref;
66   UInt_t nrefs=0;
67   if (from>=fNElems || !(ref=fElems[from])) return 0; // no references
68   if (ref<0) {refs[0] = -(1+ref); return 1;}  // just 1 reference
69   do { refs[nrefs++]=fRefBuff[ref]-1; } while((ref=(int)fRefInd[ref]) && nrefs<maxRef); // search intil no references left
70   return nrefs;
71 }
72
73 //____________________________________________________________________
74 inline Int_t AliRefArray::GetReference(UInt_t from, UInt_t which) const
75 {
76   // returns reference number which (if n/a: -1)
77   Int_t ref;
78   if (from>=fNElems || !(ref=fElems[from])) return -1; // no references
79   if (ref<0) return which ? -1 : -(1+ref);             // just 1 reference
80   int ref1 = ref;
81   while(which && (ref1=(int)fRefInd[ref])) {ref=ref1;which--;} // search intil no references left
82   return which ? -1 : fRefBuff[ref]-1;
83 }
84
85 //____________________________________________________________________
86 inline void AliRefArray::AddReference(UInt_t from, UInt_t to)
87 {
88   // add node "to" to the references of "from"
89   if (from>=fNElems) Expand(from+1);
90   int &ref0 = fElems[from];
91   if (!ref0) {ref0 = -(++to); return;}         // 1st reference, save in situ
92   //
93   int chk = ref0>0 ? 1:2; // if <0 (just 1 ref.before) need to transfer both to index array
94   if (!fRefInd || int(fRefInd[0])>(int(fRefSize)-chk)) ExpandReferences( fRefSize );
95   UInt_t &freeSlot = fRefInd[0];
96   Int_t ref = fElems[from];
97   if (ref<0) { fRefInd[freeSlot]=0; fRefBuff[freeSlot] = -ref; ref = fElems[from] = freeSlot++; }
98   //
99   while(fRefInd[ref]) ref=fRefInd[ref]; // find last index of last entry for cluster from
100   fRefBuff[freeSlot] = ++to;
101   fRefInd[ref] = freeSlot++;            // register it in the indices
102 }
103
104
105 //____________________________________________________________________
106 inline void AliRefArray::Compactify()
107 {
108   // prepare for storing with minimal space usage
109   if (fRefInd && fRefSize>fRefInd[0]) fRefSize = fRefInd[0];
110 }
111   
112 #endif