STEER/AliRefArray.h

   1 #ifndef ALIREFARRAY_H
   2
   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] forbidden partners on L1
  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 || fRefInd[0]>(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]+1)) fRefSize = fRefInd[0]+1;
 110 }
 111
 112 #endif