Line data    Source code

       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           0 :   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           0 :   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         388 :   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        2552 :   if (from>=fNElems || !(ref=fElems[from])) return kFALSE;
      55           0 :   if (ref<0) {return (ref+int(to))==-1;}   // negative means just 1 reference: -(ref+1) is stored
      56           0 :   to++;
      57           0 :   do { if (fRefBuff[ref]==to) return kTRUE; } while((ref=fRefInd[ref])); // search intil no references left
      58           0 :   return kFALSE;
      59         638 : }
      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         420 :   if (from>=fNElems || !(ref=fElems[from])) return 0; // no references
      68         248 :   if (ref<0) {refs[0] = -(1+ref); return 1;}  // just 1 reference
      69           0 :   do { refs[nrefs++]=fRefBuff[ref]-1; } while((ref=(int)fRefInd[ref]) && nrefs<maxRef); // search intil no references left
      70           0 :   return nrefs;
      71         136 : }
      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         864 :   if (from>=fNElems || !(ref=fElems[from])) return -1; // no references
      79        1152 :   if (ref<0) return which ? -1 : -(1+ref);             // just 1 reference
      80             :   int ref1 = ref;
      81           0 :   while(which && (ref1=(int)fRefInd[ref])) {ref=ref1;which--;} // search intil no references left
      82           0 :   return which ? -1 : (Int_t) fRefBuff[ref]-1;
      83         288 : }
      84             : 
      85             : //____________________________________________________________________
      86             : inline void AliRefArray::AddReference(UInt_t from, UInt_t to)
      87             : {
      88             :   // add node "to" to the references of "from"
      89         516 :   if (from>=fNElems) Expand(from+1);
      90         258 :   int &ref0 = fElems[from];
      91         516 :   if (!ref0) {ref0 = -(++to); return;}         // 1st reference, save in situ
      92             :   //
      93           0 :   int chk = ref0>0 ? 1:2; // if <0 (just 1 ref.before) need to transfer both to index array
      94           0 :   if (!fRefInd || int(fRefInd[0])>(int(fRefSize)-chk)) ExpandReferences( fRefSize );
      95           0 :   UInt_t &freeSlot = fRefInd[0];
      96           0 :   Int_t ref = fElems[from];
      97           0 :   if (ref<0) { fRefInd[freeSlot]=0; fRefBuff[freeSlot] = -ref; ref = fElems[from] = freeSlot++; }
      98             :   //
      99           0 :   while(fRefInd[ref]) ref=fRefInd[ref]; // find last index of last entry for cluster from
     100           0 :   fRefBuff[freeSlot] = ++to;
     101           0 :   fRefInd[ref] = freeSlot++;            // register it in the indices
     102         258 : }
     103             : 
     104             : 
     105             : //____________________________________________________________________
     106             : inline void AliRefArray::Compactify()
     107             : {
     108             :   // prepare for storing with minimal space usage
     109           0 :   if (fRefInd && fRefSize>fRefInd[0]) fRefSize = fRefInd[0];
     110           0 : }
     111             :   
     112             : #endif