AliRoot Core  ee782a0 (ee782a0)
AliSort.h
Go to the documentation of this file.
1 #ifndef ALISORT_H
2 #define ALISORT_H
3 #include <TClonesArray.h>
4 
5 // fast implementations of sorting for TClonesArray by making
6 // use of element type information directly
7 // created 3.5.2016; sandro.wenzel@cern.ch
8 
9 namespace AliSort {
10 
11 // anonymous namespace to prevent using this helper class from outside
12 namespace {
13  // An *internal* class to gain access to fLast and fKeep of a TClonesArray via inheritance
14  class AliClonesArrayWrapper : public TClonesArray {
15  public:
16  TObjArray *GetKeep() const {return fKeep;}
17  void SetLast(Int_t l) {fLast = l;}
18  void SetSorted(bool b) {fSorted = b;}
19  Int_t GetAbsLastM() const {return this->GetAbsLast();}
20  Int_t GetLowerBound() const {return fLowerBound;}
21  };
22 }
23 
24  // a helper function for the QSortT algorithm
25  template <typename T>
26  inline Int_t ObjCompareT(TObject *a, TObject *b)
27  {
28  if (a == nullptr && b == nullptr) return 0;
29  if (a == nullptr) return 1;
30  if (b == nullptr) return -1;
31  return ((T*)a)->T::Compare(b);
32  }
33 
34  template <typename T>
35  inline void QSortT(TObject **a, Int_t nBs, TObject ***b, Int_t first, Int_t last)
36  {
37  // in contrast to ROOT originals implementation we do not protect for thread safety here
38  // since AliROOT does not use threads
39 
40  static TObject *tmp1, **tmp2;
41  static int i; // "static" to save stack space
42  int j,k;
43 
44  static int depth = 0;
45  if (depth == 0 && nBs > 0) tmp2 = new TObject*[nBs];
46  depth++;
47 
48  while (last - first > 1) {
49  i = first;
50  j = last;
51  for (;;) {
52  while (++i < last && ObjCompareT<T>(a[i], a[first]) < 0) {}
53  while (--j > first && ObjCompareT<T>(a[j], a[first]) > 0) {}
54  if (i >= j) break;
55 
56  tmp1 = a[i]; for(k=0;k<nBs;k++) tmp2[k] = b[k][i];
57  a[i] = a[j]; for(k=0;k<nBs;k++) b[k][i] = b[k][j];
58  a[j] = tmp1; for(k=0;k<nBs;k++) b[k][j] = tmp2[k];
59  }
60  if (j == first) {
61  ++first;
62  continue;
63  }
64  tmp1 = a[first]; for(k=0;k<nBs;k++) tmp2[k] = b[k][first];
65  a[first] = a[j]; for(k=0;k<nBs;k++) b[k][first] = b[k][j];
66  a[j] = tmp1; for(k=0;k<nBs;k++) b[k][j] = tmp2[k];
67  if (j - first < last - (j + 1)) {
68  QSortT<T>(a, nBs, b, first, j);
69  first = j + 1; // QSort(j + 1, last);
70  } else {
71  QSortT<T>(a, nBs, b, j + 1, last);
72  last = j; // QSort(first, j);
73  }
74  }
75  depth--;
76 
77  if (depth == 0 && nBs > 0) delete [] tmp2;
78  }
79 
80  template <typename T>
81  inline void QSortT(TObject **a, TObject **b, Int_t first, Int_t last) { QSortT<T>(a, 1, &b, first, last); }
82 
83  // a fast template replacement for ROOT's TClonesArray Sort
84  // sorts a TClonesArray fast by using information about the type that
85  // the TClonesArray is storing
86  // this implementation is taken from ROOT
87  template <typename T>
88  inline void TClonesArraySort(TClonesArray *a, Int_t upto=kMaxInt){
89  AliClonesArrayWrapper *wrapper = static_cast<AliClonesArrayWrapper *>(a);
90  Int_t nentries = wrapper->GetAbsLastM()+1;
91  if (nentries <= 0 || wrapper->TClonesArray::IsSorted()) return;
92 
93  TObject **rawcontainer = wrapper->GetObjectRef();
94 
95  // this test is a quite expensive runtime test
96  // which is essentially useless for TClonesArray since by definition
97  // all elements have the same type
98 #ifndef NDEBUG
99  for (Int_t i = 0; i < wrapper->TClonesArray::GetSize(); ++i)
100  if (rawcontainer[i]) {
101  if (!((T*)rawcontainer[i])->T::IsSortable()) {
102  // Error("Sort", "objects in array are not sortable");
103  return;
104  }
105  }
106 #endif
107 
108  Int_t lowerbound = wrapper->GetLowerBound();
109 
110  TObject **othercontainer = wrapper->GetKeep()->GetObjectRef();
111  QSortT<T>(rawcontainer, othercontainer, 0, std::min(nentries, upto-lowerbound));
112 
113  wrapper->SetLast(-2);
114  wrapper->SetSorted(kTRUE);
115  }
116 
117 }
118 
119 
120 #endif // ALISORT_H
TBrowser b
Definition: RunAnaESD.C:12
#define TObjArray
Definition: AliSort.h:9
Int_t ObjCompareT(TObject *a, TObject *b)
Definition: AliSort.h:26
void TClonesArraySort(TClonesArray *a, Int_t upto=kMaxInt)
Definition: AliSort.h:88
void QSortT(TObject **a, Int_t nBs, TObject ***b, Int_t first, Int_t last)
Definition: AliSort.h:35