Logo ROOT   6.08/07
Reference Guide
TTableSorter.cxx
Go to the documentation of this file.
1 // @(#)root/table:$Id$
2 // Author: Valery Fine 26/01/99 (E-mail: fine@bnl.gov)
3 
4 /*************************************************************************
5  * Copyright (C) 1995-2000, Rene Brun and Fons Rademakers. *
6  * All rights reserved. *
7  * *
8  * For the licensing terms see $ROOTSYS/LICENSE. *
9  * For the list of contributors see $ROOTSYS/README/CREDITS. *
10  *************************************************************************/
11 
12 
13 #include <stdlib.h>
14 #include "TTableSorter.h"
15 #include "TTable.h"
16 #include "TClass.h"
17 #include "TDataMember.h"
18 #include "TDataType.h"
19 #include "TMemberInspector.h"
20 extern "C" {
21  typedef Int_t (*CALLQSORT) (const void *, const void *);
22 }
23 
24 /////////////////////////////////////////////////////////////////////////////////////////
25 //
26 // TTableSorter - Is an "observer" class to sort the TTable objects
27 // The class provides an interface to the standard "C/C++"
28 //
29 // qsort and bsearch subroutines (for further information see your local C/C++ docs)
30 // ===== =======
31 //
32 // - This class DOESN'T change / touch the "host" table itself
33 // For any TTable object one can create as many different "sorter"
34 // as one finds useful for one's code
35 // - Any instance of this class is meaningful as long as the "host" object
36 // "TTable" does exist and is not changed
37 // - Any attempt to access this TTableSorter after the "host" object deleted
38 // causes the program abnormal termination
39 // - Any attempt to access this TTableSorter after the "host" object been changed
40 // causes an unpredictable result
41 // - Any instance (object) of this class is NOT deleted "by automatic" just
42 // the "host object "TTable" deleted. It is the responsibility of the user's code
43 // keeping TTableSorter and the the "host" TTable objects consistent.
44 //
45 // "To do" list
46 //
47 // 1. A separate method to provide lexicographical sort if the "sorted" column is a kind of array
48 //
49 // Usage:
50 // 1. Create an instance of the sorter for the selected column of your table
51 //
52 // new TTableSorter(TTable &table, TString &colName,Int_t firstRow,Int_t numberRows)
53 //
54 // All sort actions are performed within TTableSorter ctor.
55 // This means one needs no extra effort to SORT table. "Sorter" contains
56 // the "sorted index array" as soon as you create the sorter
57 //
58 // TTableSorter sorter(MyTable,"id",20, 34);
59 // - Creates a sorter for MyTable column "id" ordering
60 // its 34 rows from 20 row with standard "C" qsort subroutine
61 //
62 // 2. You may use this instance to search any "id" value with operator []
63 // to get the table row index as follows:
64 //
65 // Int_t id = 5;
66 // Int_t index = sorter[id]; // Look for the row index with id = 5
67 // // using the standard "C" "bsearch" binary search
68 // // subroutine
69 // Int_t index = sorter(id); // Look for the row index with id "nearest" to 5
70 // // using the internal "BinarySearch" method
71 //
72 // 3. Some useful methods of this class:
73 //
74 // 3.1. CountKeys()
75 // 3.2 CountKey(const void *key, Int_t firstIndx=0,Bool_t bSearch=kTRUE,Int_t *firstRow=0)
76 // 3.3. FindFirstKey(const void *key)
77 // 3.4. GetIndex(UInt_t sortedIndex)
78 //
79 /////////////////////////////////////////////////////////////////////////////////////////
80 
81 
83 
84 //_____________________________________________________________________________
85 //TTableSorter::TTableSorter() : fsimpleArray(0),fParentTable(*((const TTable *)0))
86 TTableSorter::TTableSorter() : fsimpleArray(0),fParentTable(0)
87 {
88  // default ctor for RootCint dictionary
89  fLastFound = -1;
90  fFirstRow = 0;
91  fSortIndex = 0;
92  fSearchMethod = 0;
93  fNumberOfRows = 0;
94  fColType = TTable::kNAN;
95  fsimpleArray = 0;
96  fParentRowSize = 0;
97  fFirstParentRow = 0;
98  fCompareMethod = 0;
99  fIndexArray = 0;
100  fColDimensions = 0;
101  fColOffset = 0;
102  fColSize = 0;
103 }
104 
105 ////////////////////////////////////////////////////////////////////////////////
106 ///
107 /// TTableSorter ctor sorts the input table along its column defined with colName
108 ///
109 /// - colName - may be followed by the square brackets with integer number inside,
110 /// if that columm is an array (for example "phys[3]").
111 /// NO expression inside of [], only a single integer number allowed !
112 /// - firstRow - the first table row to sort from (=0 by default)
113 /// - numberRows - the number of the table rows to sort (=0 by default)
114 /// = 0 means sort all rows from the "firstRow" by the end of table
115 ///
116 
117 TTableSorter::TTableSorter(const TTable &table, TString &colName,Int_t firstRow
118  ,Int_t numberRows):fsimpleArray(0),fParentTable(&table)
119 {
120  fCompareMethod = 0;
121  fSearchMethod = 0;
122 
123  BuildSorter(colName, firstRow, numberRows);
124 }
125 
126 ////////////////////////////////////////////////////////////////////////////////
127 ///
128 /// TTableSorter ctor sorts the input table along its column defined with colName
129 ///
130 /// - colName - may be followed by the square brackets with integer number inside,
131 /// if that columm is an array (for example "phys[3]").
132 /// NO expression inside of [], only a single integer number allowed !
133 /// - firstRow - the first table row to sort from (=0 by default)
134 /// - numberRows - the number of the table rows to sort (=0 by default)
135 /// = 0 means sort all rows from the "firstRow" by the end of table
136 ///
137 
138 TTableSorter::TTableSorter(const TTable *table, TString &colName,Int_t firstRow
139  ,Int_t numberRows):fsimpleArray(0),fParentTable(table)
140 {
141  fCompareMethod = 0;
142  fSearchMethod = 0;
143 
144  BuildSorter(colName, firstRow, numberRows);
145 }
146 ////////////////////////////////////////////////////////////////////////////////
147 ///
148 /// TTableSorter ctor sorts the input table according the function "search"
149 ///
150 /// - search - the function to compare the "key" and the table rows during sorting
151 /// typedef Int_t (*SEARCHMETHOD) (const void *, const void **);
152 ///
153 /// - compare - the function to compare two table rows during searching
154 /// typedef Int_t (*COMPAREMETHOD)(const void **, const void **);
155 ///
156 /// - firstRow - the first table row to sort from (=0 by default)
157 /// - numberRows - the number of the table rows to sort (=0 by default)
158 /// = 0 means sort all rows from the "firstRow" by the end of table
159 /// Note: This is a base class. If one fears it is not safe
160 /// ----- to allow "void *" one may potect the end-user code
161 /// providing a derived class with the appropriated type
162 /// of the parameters.
163 ///
164 
166  COMPAREMETHOD compare, Int_t firstRow,Int_t numberRows)
167  :fsimpleArray(0),fParentTable(&table)
168 {
170  fSearchMethod = search;
171  TString colName = "user's defined";
172  BuildSorter(colName, firstRow, numberRows);
173 }
174 ////////////////////////////////////////////////////////////////////////////////
175 ///
176 /// TTableSorter ctor sorts the input table according the function "search"
177 ///
178 /// - search - the function to compare the "key" and the table rows during sorting
179 /// typedef Int_t (*SEARCHMETHOD) (const void *, const void **);
180 ///
181 /// - compare - the function to compare two table rows during searching
182 /// typedef Int_t (*COMPAREMETHOD)(const void **, const void **);
183 ///
184 /// - firstRow - the first table row to sort from (=0 by default)
185 /// - numberRows - the number of the table rows to sort (=0 by default)
186 /// = 0 means sort all rows from the "firstRow" by the end of table
187 /// Note: This is a base class. If one fears it is not safe
188 /// ----- to allow "void *" one may potect the end-user code
189 /// providing a derived class with the appropriated type
190 /// of the parameters.
191 ///
192 
194  COMPAREMETHOD compare, Int_t firstRow,Int_t numberRows)
195  :fsimpleArray(0),fParentTable(table)
196 {
198  fSearchMethod = search;
199  TString colName = "user's defined";
200  BuildSorter(colName, firstRow, numberRows);
201 }
202 
203 ////////////////////////////////////////////////////////////////////////////////
204 ///
205 /// BuildSorter backs TTableSorter ctor
206 ///
207 /// - colName - may be followed by the square brackets with integer number inside,
208 /// if that columm is an array (for example "phys[3]").
209 /// NO expression inside of [], only a single integer number allowed !
210 /// - firstRow - the first table row to sort from (=0 by default)
211 /// - numberRows - the number of the table rows to sort (=0 by default)
212 /// = 0 means sort all rows from the "firstRow" by the end of table
213 ///
214 
215 void TTableSorter::BuildSorter(TString &colName, Int_t firstRow, Int_t numberRows)
216 {
217  assert(fParentTable!=0);
218 
219  fLastFound = -1;
220  fNumberOfRows = 0;
222  fsimpleArray = 0;
223  //yf fCompareMethod = 0;
224  fSortIndex = 0;
225  //yf fSearchMethod = 0;
226  fColDimensions = 0;
227  fColOffset = 0;
228 
229  // Generate new object name
231  n += ".";
232  n += colName;
233  SetName(n);
234 
235  Char_t *name = (Char_t *) colName.Data();
236  if (!(name || strlen(colName.Data()))) { MakeZombie(); delete [] name; return; }
237  name = StrDup(colName.Data());
238 
239  // check bounds:
240  if (firstRow > fParentTable->GetNRows()) { MakeZombie(); delete [] name; return; }
241  fFirstRow = firstRow;
242 
244  if (numberRows > 0) fNumberOfRows = TMath::Min(numberRows,fNumberOfRows);
246  fFirstParentRow= (const char *)fParentTable->GetArray();
247 
248  // Allocate index array
249  if (fNumberOfRows <=0 ) { MakeZombie(); delete [] name; return; }
250  fSortIndex = new void*[fNumberOfRows];
251 
252  // define dimensions if any;
253  // count the open "["
254  Char_t *br = name - 1;
255  while((br = strchr(br+1,'['))) {
256  if (!fColDimensions) *br = 0;
257  fColDimensions++;
258  }
259 
260  // Define the column name
261  fColName = name;
262  delete [] name;
263 
264  fIndexArray = 0;
265  if (fColDimensions) {
267  memset(fIndexArray,0,fColDimensions*sizeof(Int_t));
268  // Define the index
269  const char *openBracket = colName.Data()-1;
270  const char *closeBracket = colName.Data()-1;
271  for (Int_t i=0; i< fColDimensions; i++) {
272  openBracket = strchr(openBracket+1, '[');
273  closeBracket = strchr(closeBracket+1,']');
274  if (closeBracket > openBracket)
275  fIndexArray[i] = atoi(openBracket+1);
276  else {
277  Error("TTable ctor", "Wrong parethethis <%s>",colName.Data());
278  MakeZombie();
279  return;
280  }
281  }
282  }
283  if (colName != "user's defined") {
284  LearnTable();
285  SetSearchMethod();
286  }
287  if (!FillIndexArray()) QSort();
288 }
289 
290 ////////////////////////////////////////////////////////////////////////////////
291 ///
292 /// TTableSorter ctor sort the input "simpleArray"
293 ///
294 /// - arraySize - the size of the full array
295 /// - firstRow - the first table row to sort from (=0 by default)
296 /// - numberRows - the number of the table rows to sort (=0 by default)
297 /// = 0 means sort all rows from the "firstRow" by the end of table
298 ///
299 
300 TTableSorter::TTableSorter(const Float_t *simpleArray, Int_t arraySize, Int_t firstRow
301  ,Int_t numberRows)
302  :fsimpleArray((const Char_t*)simpleArray)
303  ,fParentTable(0)
304 {
305  fLastFound = -1;
306 
307  SetSimpleArray(arraySize,firstRow,numberRows);
308  if (!fsimpleArray) { MakeZombie(); return; }
309 
310  // LearnTable();
311 
312  fColName = "Float";
314  fColSize = sizeof(Float_t);
316 
317  // FillIndexArray();
318 
320  Bool_t isPreSorted = kTRUE;
321  Float_t sample = *p;
322  for (Int_t i=0; i < fNumberOfRows;i++,p++) {
323  fSortIndex[i-fFirstRow] = p;
324  if ( isPreSorted) {
325  if (sample > *p) isPreSorted = kFALSE;
326  else sample = *p;
327  }
328  }
329 
330  SetSearchMethod();
331  if (!isPreSorted) QSort();
332 }
333 
334 ////////////////////////////////////////////////////////////////////////////////
335 ///
336 /// TTableSorter ctor sort the input "simpleArray"
337 ///
338 /// - arraySize - the size of the full array
339 /// - firstRow - the first table row to sort from (=0 by default)
340 /// - numberRows - the number of the table rows to sort (=0 by default)
341 /// = 0 means sort all rows from the "firstRow" by the end of table
342 ///
343 
344 TTableSorter::TTableSorter(const Double_t *simpleArray, Int_t arraySize, Int_t firstRow
345  ,Int_t numberRows)
346  :fsimpleArray((const Char_t*)simpleArray)
347  ,fParentTable(0)
348 {
349  fLastFound = -1;
350 
351  SetSimpleArray(arraySize,firstRow,numberRows);
352  if (!fsimpleArray) {MakeZombie(); return; }
353 
354  // LearnTable();
355 
356  fColName = "Double";
358  fColSize = sizeof(Double_t);
360 
361  // FillIndexArray();
362 
363  Double_t *p = ((Double_t *)simpleArray) + fFirstRow;
364  Bool_t isPreSorted = kTRUE;
365  Double_t sample = *p;
366  for (Int_t i=0; i < fNumberOfRows;i++,p++) {
367  fSortIndex[i-fFirstRow] = p;
368  if ( isPreSorted) {
369  if (sample > *p) isPreSorted = kFALSE;
370  else sample = *p;
371  }
372  }
373 
374  SetSearchMethod();
375  if (!isPreSorted) QSort();
376 }
377 
378 ////////////////////////////////////////////////////////////////////////////////
379 ///
380 /// TTableSorter ctor sort the input "simpleArray"
381 ///
382 /// - arraySize - the sie of the full array
383 /// - firstRow - the first table row to sort from (=0 by default)
384 /// - numberRows - the number of the table rows to sort (=0 by default)
385 /// = 0 means sort all rows from the "firstRow" by the end of table
386 ///
387 
388 TTableSorter::TTableSorter(const Long_t *simpleArray, Int_t arraySize, Int_t firstRow
389  ,Int_t numberRows)
390  :fsimpleArray((const Char_t*)simpleArray)
391  ,fParentTable(0)
392 {
393  fLastFound = -1;
394 
395  SetSimpleArray(arraySize,firstRow,numberRows);
396  if (!simpleArray) { MakeZombie(); return; }
397 
398  // LearnTable();
399 
400  fColName = "Long";
402  fColSize = sizeof(Long_t);
404 
405  // FillIndexArray();
406 
407  Long_t *p = ((Long_t *)simpleArray) + fFirstRow;
408  Bool_t isPreSorted = kTRUE;
409  Long_t sample = *p;
410  for (Int_t i=0; i < fNumberOfRows;i++,p++) {
411  fSortIndex[i-fFirstRow] = p;
412  if ( isPreSorted) {
413  if (sample > *p) isPreSorted = kFALSE;
414  else sample = *p;
415  }
416  }
417  SetSearchMethod();
418  if (!isPreSorted) QSort();
419 
420 }
421 
422 ////////////////////////////////////////////////////////////////////////////////
423 /// Set some common parameteres for the "simple" arrays
424 
425 void TTableSorter::SetSimpleArray(Int_t arraySize, Int_t firstRow,Int_t numberRows)
426 {
427  SetName("Array");
428 
429  fSortIndex = 0;
430  fSearchMethod = 0;
431  fColDimensions = 0;
432  delete [] fIndexArray;
433  fIndexArray = 0;
434  fColOffset = 0;
435 
436  // check bounds:
437  if (firstRow > arraySize) return;
438  fFirstRow = firstRow;
439 
440  fNumberOfRows = arraySize - fFirstRow;
441  if (numberRows > 0) fNumberOfRows = TMath::Min(numberRows,fNumberOfRows);
442 
443  // Allocate index array
444  delete [] fSortIndex;
445  if (fNumberOfRows > 0) fSortIndex = new void*[fNumberOfRows];
446 }
447 
448 ////////////////////////////////////////////////////////////////////////////////
449 ///to be documented
450 
452 {
453  delete [] fSortIndex; fSortIndex = 0; fNumberOfRows=0;
454  delete [] fIndexArray;
455 }
456 
457 //_____________________________________________________________________________
458 //______________________________________________________________________________
459 //*-*-*-*-*-*-*Binary search in an array of n values to locate value*-*-*-*-*-*-*
460 //*-* ==================================================
461 //*-* If match is found, the function returns the position (index) of the element.
462 //*-* If no match found, the function gives the index of the nearest element
463 //*-* smaller than key value.
464 //*-* Note: The function returns the negative result if the key value
465 //*-* ---- is smaller any table value.
466 //*-*
467 //*-* This method is based on TMath::BinarySearch
468 //*-*
469 //*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*
470 
471 #define BINARYSEARCH(valuetype) Int_t TTableSorter::BinarySearch(valuetype value) const {\
472  switch (fColType) { \
473  case TTable::kFloat: \
474  return SelectSearch(Float_t(value)); \
475  case TTable::kInt : \
476  return SelectSearch(Int_t(value)); \
477  case TTable::kLong : \
478  return SelectSearch(Long_t(value)); \
479  case TTable::kShort : \
480  return SelectSearch(Short_t(value)); \
481  case TTable::kDouble : \
482  return SelectSearch(Double_t(value)); \
483  case TTable::kUInt: \
484  return SelectSearch(UInt_t(value)); \
485  case TTable::kULong : \
486  return SelectSearch(ULong_t(value)); \
487  case TTable::kUShort: \
488  return SelectSearch(UShort_t(value)); \
489  case TTable::kBool: \
490  return SelectSearch(Bool_t(value)); \
491  case TTable::kUChar: \
492  return SelectSearch(UChar_t(value)); \
493  case TTable::kChar: \
494  return SelectSearch(Char_t(value)); \
495  default: \
496  return -1; \
497  break; \
498  }; \
499 } \
500 Int_t TTableSorter::BSearch(valuetype value) const{ \
501  union { Bool_t Bool; \
502  Char_t Char; \
503  UChar_t UChar; \
504  Short_t Short; \
505  UShort_t UShort; \
506  Int_t Int; \
507  UInt_t UInt; \
508  Long_t Long; \
509  ULong_t ULong; \
510  Float_t Float; \
511  Double_t Double; \
512  } value_; \
513  \
514  switch (fColType) { \
515  case TTable::kFloat: \
516  value_.Float = Float_t(value); break; \
517  case TTable::kInt : \
518  value_.Int = Int_t(value); break; \
519  case TTable::kLong : \
520  value_.Long = Long_t(value); break; \
521  case TTable::kShort : \
522  value_.Short = Short_t(value); break; \
523  case TTable::kDouble : \
524  value_.Double= Double_t(value);break; \
525  case TTable::kUInt: \
526  value_.UInt = UInt_t(value); break; \
527  case TTable::kULong : \
528  value_.ULong = ULong_t(value); break; \
529  case TTable::kUShort: \
530  value_.UShort= UShort_t(value);break; \
531  case TTable::kUChar: \
532  value_.UChar = UChar_t(value); break; \
533  case TTable::kChar: \
534  value_.Char = Char_t(value); break; \
535  case TTable::kBool: \
536  value_.Bool = Bool_t(value); break; \
537  default: \
538  return -1; \
539  break; \
540  }; \
541  return BSearch(&value_); \
542 } \
543 Int_t TTableSorter::SelectSearch(valuetype value) const { \
544  valuetype **array = (valuetype **)fSortIndex; \
545  Int_t nabove, nbelow, middle; \
546  nabove = fNumberOfRows+1; \
547  nbelow = 0; \
548  while(nabove-nbelow > 1) { \
549  middle = (nabove+nbelow)/2; \
550  if (value == *array[middle-1]) { nbelow = middle; break; } \
551  if (value < *array[middle-1]) nabove = middle; \
552  else nbelow = middle; \
553  } \
554  nbelow--; \
555  ((TTableSorter *)this)->fLastFound = nbelow; \
556  if (nbelow < 0) return nbelow; \
557  return GetIndex(nbelow); \
558 }
559 
560 #define COMPAREFLOATVALUES(valuetype) \
561 int TTableSorter::Search##valuetype (const void *elem1, const void **elem2) { \
562  valuetype *value1 = (valuetype *)(elem1); \
563  valuetype *value2 = (valuetype *)(*elem2); \
564  valuetype diff = *value1-*value2; \
565  Int_t res = 0; \
566  if (diff > 0) res = 1; \
567  else if (diff < 0) res = -1; \
568  return res; \
569 } \
570 int TTableSorter::Compare##valuetype (const void **elem1, const void **elem2) {\
571  valuetype *value1 = (valuetype *)(*elem1); \
572  valuetype *value2 = (valuetype *)(*elem2); \
573  valuetype diff = *value1-*value2; \
574  Int_t res = 0; \
575  if (diff > 0 ) res = 1; \
576  else if (diff < 0) res = -1; \
577  if (res) return res; \
578  return int(value1-value2); \
579 } \
580 BINARYSEARCH(valuetype)
581 
582 ////////////////////////////////////////////////////////////////////////////////
583 
584 #define COMPAREVALUES(valuetype) \
585 int TTableSorter::Search##valuetype (const void *elem1, const void **elem2) { \
586  valuetype *value1 = (valuetype *)(elem1); \
587  valuetype *value2 = (valuetype *)(*elem2); \
588  return int(*value1-*value2); \
589 } \
590 int TTableSorter::Compare##valuetype (const void **elem1, const void **elem2) { \
591  valuetype *value1 = (valuetype *)(*elem1); \
592  valuetype *value2 = (valuetype *)(*elem2); \
593  valuetype diff = *value1-*value2; \
594  if (diff ) return diff; \
595  return int(value1-value2); \
596 } \
597 BINARYSEARCH(valuetype)
598 
610 
611 #define COMPAREORDER(valuetype) Compare##valuetype
612 #define SEARCHORDER(valuetype) Search##valuetype
613 
614 ////////////////////////////////////////////////////////////////////////////////
615 ///to be documented
616 
617 Int_t TTableSorter::BSearch(const void *value) const
618 {
619  Int_t index = -1;
620  if (fSearchMethod) {
621  void **p = (void **)::bsearch((void *) value, // Object to search for
622  fSortIndex, // Pointer to base of search data
623  fNumberOfRows, // Number of elements
624  sizeof(void *), // Width of elements
626  ((TTableSorter *)this)->fLastFound = -1;
627  if (p) {
628  const Char_t *res = (const Char_t *)(*p);
629  ((TTableSorter *)this)->fLastFound = ((Char_t *)p - (Char_t *)fSortIndex)/sizeof(void *);
630  // calculate index:
631  if (!fsimpleArray)
632  index = fFirstRow + (res - (At(fFirstRow)+ fColOffset))/fParentRowSize;
633  else
634  index = ULong_t(res) - ULong_t(fsimpleArray)/fColSize;
635  }
636  }
637  return index;
638 }
639 
640 ////////////////////////////////////////////////////////////////////////////////
641 /// returns the original index of the row by its sorted index
642 
644 {
645  Int_t indx = -1;
646  if (sortedIndex < UInt_t(fNumberOfRows) ) {
647  void *p = fSortIndex[sortedIndex];
648  if (p) {
649  const Char_t *res = (const Char_t *)p;
650  // calculate index:
651  if (!fsimpleArray)
652  indx = fFirstRow + (res - (At(fFirstRow) + fColOffset))/fParentRowSize;
653  else
654  indx = (ULong_t(res) - ULong_t(fsimpleArray))/fColSize;
655  }
656  }
657  return indx;
658 }
659 
660 #if 0
661 ////////////////////////////////////////////////////////////////////////////////
662 ///to be documented
663 
664 int TTableSorter::CompareUChar (const void *elem1, const void *elem2)
665 {
666  UChar_t *value1 = (UChar_t *)(*elem1);
667  UChar_t *value2 = (UChar_t *)(*elem2);
668  COMPAREVALUES(value1,value2)
669 }
670 
671 ////////////////////////////////////////////////////////////////////////////////
672 ///to be documented
673 
674 int TTableSorter::CompareChar (const void *elem1, const void *elem2)
675 {
676  Char_t *value1 = (Char_t *)(*elem1);
677  Char_t *value2 = (Char_t *)(*elem2);
678  COMPAREVALUES(value1,value2)
679 }
680 #endif
681 
682 ////////////////////////////////////////////////////////////////////////////////
683 ///
684 /// CountKey counts the number of rows with the key value equal "key"
685 ///
686 /// key - it is a POINTER to the key value
687 /// fistIndx - the first index within sorted array to star search
688 /// = 0 by default
689 /// bSearch = kTRUE - binary search (by default) is used otherwise linear one
690 ///
691 
692 Int_t TTableSorter::CountKey(const void *key, Int_t firstIndx, Bool_t bSearch, Int_t *firstRow) const
693 {
694  Int_t count = 0;
695  if (firstRow) *firstRow = -1;
696  if (fSearchMethod) {
697  Int_t indx = firstIndx;
698  Int_t nRows = GetNRows();
699  if (!bSearch) {
700  while ( indx < nRows && fSearchMethod(key,(const void **)&fSortIndex[indx])){indx++;}
701  // Remember the first row been asked:
702  } else {
703  indx = FindFirstKey(key);
704  if (indx >= 0 ) { // Key was found let's count it
705  count = TMath::Max(0,GetLastFound() - indx + 1);
706  indx = TMath::Max(GetLastFound()+1,firstIndx);
707  // Forward pass
708  }
709  }
710  if (indx >= 0) {
711  while ( indx < nRows &&!fSearchMethod(key,(const void **)&fSortIndex[indx])){indx++; count++;}
712  if (firstRow && count) *firstRow = indx-count;
713  }
714  }
715  return count;
716 }
717 
718 ////////////////////////////////////////////////////////////////////////////////
719 ///
720 /// Counts the number of different key values
721 ///
722 
724 {
725  Int_t count = 0;
726  if (fSortIndex && fSortIndex[0]) {
727  void *key = fSortIndex[0];
728  Int_t indx = 0;
729  while (indx < GetNRows()){
730  indx += CountKey(key,indx,kFALSE);
731  count++;
732  key = fSortIndex[indx];
733  }
734  }
735  return count;
736 }
737 
738 ////////////////////////////////////////////////////////////////////////////////
739 ///////////////////////////////////////////////////////////////
740 /// File the array of the pointers and check whether
741 /// the original table has been sorted to avoid an extra job.
742 ///
743 /// Return: kTRUE - the table has been sorted
744 /// kFALSE - otherwise
745 ///////////////////////////////////////////////////////////////
746 
748  assert(fSortIndex!=0);
749  const char *row = At(fFirstRow) + fColOffset;
750  Bool_t isPreSorted = kTRUE;
751  const void *sample = row;
752  for (Int_t i=fFirstRow; i < fFirstRow+fNumberOfRows;i++,row += fParentRowSize) {
753  fSortIndex[i-fFirstRow] = (char *)row;
754  if ( isPreSorted) {
755  void *ptr = &row;
756  if (fCompareMethod(&sample,(const void **)ptr)>0) isPreSorted = kFALSE;
757  else sample = row;
758  }
759  }
760  return isPreSorted;
761 }
762 
763 ////////////////////////////////////////////////////////////////////////////////
764 ///
765 /// Looks for the first index of the "key"
766 /// within SORTED table AFTER sorting
767 ///
768 /// Returns: = -1 if the "key" was not found
769 ///
770 /// Note: This method has no sense for
771 /// ==== the float and double key
772 ///
773 /// To get the index within the original
774 /// unsorted table the GetIndex() method
775 /// may be used like this:
776 /// GetIndex(FindFirstKey(key))
777 ///
778 
779 Int_t TTableSorter::FindFirstKey(const void *key) const
780 {
781  Int_t indx = -1;
782  if (BSearch(key)>=0) {
783  indx = GetLastFound();
784  if (indx >=0)
785  while (indx > 0 && !fSearchMethod(key,(const void **)&fSortIndex[indx-1])) indx--;
786  }
787  return indx;
788 }
789 
790 ////////////////////////////////////////////////////////////////////////////////
791 ///to be documented
792 
793 const char * TTableSorter::GetTableName() const
794 {
795  return fParentTable ? fParentTable->GetName():"";
796 }
797 
798 ////////////////////////////////////////////////////////////////////////////////
799 ///to be documented
800 
801 const char * TTableSorter::GetTableTitle() const
802 {
803  return fParentTable ? fParentTable->GetTitle():"";
804 }
805 
806  ///////////////////////////////////////////////////////////////////////////////
807  ///to be documented
808 
809 const char * TTableSorter::GetTableType() const
810 {
811  return fParentTable ? fParentTable->GetType():"";
812 }
813 
814 ////////////////////////////////////////////////////////////////////////////////
815 ///to be documented
816 
818 {
819  return (TTable *)fParentTable;
820 }
821 
822 ////////////////////////////////////////////////////////////////////////////////
823 /// Select search function at once
824 
826 {
827  if (!fSearchMethod) {
828  switch (fColType) {
829  case TTable::kFloat:
832  break;
833  case TTable::kInt :
836  break;
837  case TTable::kLong :
840  break;
841  case TTable::kShort :
844  break;
845  case TTable::kDouble :
848  break;
849  case TTable::kUInt:
852  break;
853  case TTable::kULong :
856  break;
857  case TTable::kUShort:
860  break;
861  case TTable::kUChar:
864  break;
865  case TTable::kChar:
868  break;
869  case TTable::kBool:
872  break;
873  default:
874  break;
875 
876  };
877  }
878 }
879 
880 ////////////////////////////////////////////////////////////////////////////////
881 /// Call the standard C run-time library "qsort" function
882 ///
883 
885  if (fCompareMethod)
886  ::qsort(fSortIndex, //Start of target array
887  fNumberOfRows, //Array size in elements
888  sizeof(void *), //Element size in bytes
890 }
891 
892 ////////////////////////////////////////////////////////////////////////////////
893 ///
894 /// LearnTable() allows the TTableSorter to learn the structure of the
895 /// tables used to fill the ntuple.
896 /// table - the name of the table
897 /// buildTree - if kTRUE, then add TBranches to the TTree for each table
898 /// column (default=kFALSE)
899 ///
900 
902 {
903  TClass *classPtr = fParentTable->GetRowClass();
904  if (!classPtr) return;
905 
906  if (!classPtr->GetListOfRealData()) classPtr->BuildRealData();
907  if (!(classPtr->GetNdata())) return;
908 
909  const Char_t *types;
910  Char_t *varname;
911 
912  TIter next(classPtr->GetListOfDataMembers());
913  TDataMember *member = 0;
914  while ( (member = (TDataMember *) next()) ) {
915  varname = (Char_t *) member->GetName();
916 
917  if (strcmp(varname,fColName.Data())) continue;
918 
919  TDataType *memberType = member->GetDataType();
920  types = memberType->GetTypeName();
921  SetTitle(types);
922  if (!strcmp("float", types))
924  else if (!strcmp("int", types))
926  else if (!strcmp("long", types))
928  else if (!strcmp("short", types))
930  else if (!strcmp("double", types))
932  else if (!strcmp("unsigned int", types))
934  else if (!strcmp("unsigned long", types))
936  else if (!strcmp("unsigned short", types))
938  else if (!strcmp("unsigned char", types))
940  else if (!strcmp("char", types))
942  else if (!strcmp("bool", types))
944 
945  if (fColType != TTable::kNAN) {
946  Int_t dim = 0;
947  Int_t globalIndex = 0;
948  if ( (dim = member->GetArrayDim()) ) {
949  // Check dimensions
950  if (dim != fColDimensions) {
951  Error("LearnTable","Wrong dimension");
952  TTable *t = (TTable *)fParentTable;
953  t->Print();
954  return;
955  }
956  // Calculate the global index
957  for( Int_t indx=0; indx < fColDimensions; indx++ ){
958  globalIndex *= member->GetMaxIndex(indx);
959  globalIndex += fIndexArray[indx];
960  }
961  }
962  fColSize = memberType->Size();
963  fColOffset = member->GetOffset() + memberType->Size() * globalIndex;
964  }
965  break;
966  }
967 }
968 
969 #undef COMPAREVALUES
970 #undef COMPAREORDER
971 #undef COMPAREFLOATVALUES
972 #undef BINARYSEARCH
Int_t GetIndex(UInt_t sortedIndex) const
returns the original index of the row by its sorted index
void LearnTable()
LearnTable() allows the TTableSorter to learn the structure of the tables used to fill the ntuple...
virtual const char * GetName() const
Returns name of object.
Definition: TNamed.h:51
Int_t GetNdata()
Return the number of data members of this class Note that in case the list of data members is not yet...
Definition: TClass.cxx:4323
virtual TTable * GetTable() const
to be documented
static TDataType * GetDataType(EDataType type)
Given a EDataType type, get the TDataType* that represents it.
Definition: TDataType.cxx:440
TString GetTypeName()
Get basic type of typedef, e,g.
Definition: TDataType.cxx:149
Int_t fColSize
Definition: TTableSorter.h:67
float Float_t
Definition: RtypesCore.h:53
All ROOT classes may have RTTI (run time type identification) support added.
Definition: TDataMember.h:33
Int_t fColOffset
Definition: TTableSorter.h:66
unsigned short UShort_t
Definition: RtypesCore.h:36
virtual void SetName(const char *name)
Set the name of the TNamed.
Definition: TNamed.cxx:131
TString fColName
Definition: TTableSorter.h:65
const char * fFirstParentRow
Definition: TTableSorter.h:76
virtual TClass * GetRowClass() const
to be documented
Definition: TTable.cxx:1379
#define COMPAREVALUES(valuetype)
int compare(double v1, double v2, const std::string &name="", double scale=1.0)
TList * GetListOfDataMembers(Bool_t load=kTRUE)
Return list containing the TDataMembers of a class.
Definition: TClass.cxx:3570
virtual Int_t CountKey(const void *key, Int_t firstIndx=0, Bool_t bSearch=kTRUE, Int_t *firstRow=0) const
CountKey counts the number of rows with the key value equal "key".
Int_t fNumberOfRows
Definition: TTableSorter.h:64
Basic string class.
Definition: TString.h:137
Short_t Min(Short_t a, Short_t b)
Definition: TMathBase.h:170
int Int_t
Definition: RtypesCore.h:41
bool Bool_t
Definition: RtypesCore.h:59
Bool_t FillIndexArray()
File the array of the pointers and check whether the original table has been sorted to avoid an extra...
const Bool_t kFALSE
Definition: Rtypes.h:92
Int_t BSearch(const void *value) const
to be documented
COMPAREMETHOD fCompareMethod
Definition: TTableSorter.h:73
virtual const Char_t * GetType() const
Returns the type of the wrapped C-structure kept as the TNamed title.
Definition: TTable.cxx:1449
#define SEARCHORDER(valuetype)
virtual Int_t CountKeys() const
Counts the number of different key values.
const Char_t * fsimpleArray
Definition: TTableSorter.h:70
virtual Char_t * Print(Char_t *buf, Int_t n) const
Create IDL table defintion (to be used for XDF I/O)
Definition: TTable.cxx:1553
#define COMPAREFLOATVALUES(valuetype)
Int_t(* CALLQSORT)(const void *, const void *)
virtual const char * GetTableType() const
to be documented
Int_t fFirstRow
Definition: TTableSorter.h:63
Int_t fColDimensions
Definition: TTableSorter.h:69
Int_t(* SEARCHMETHOD)(const void *, const void **)
Definition: TTableSorter.h:44
void SetSearchMethod()
Select search function at once.
const TTable * fParentTable
Definition: TTableSorter.h:71
virtual Int_t GetLastFound() const
Definition: TTableSorter.h:173
void BuildRealData(void *pointer=0, Bool_t isTransient=kFALSE)
Build a full list of persistent data members.
Definition: TClass.cxx:1951
#define COMPAREORDER(valuetype)
void BuildSorter(TString &colName, Int_t firstRow, Int_t numberRows)
BuildSorter backs TTableSorter ctor.
void QSort()
Call the standard C run-time library "qsort" function.
Long_t fParentRowSize
Definition: TTableSorter.h:75
Basic data type descriptor (datatype information is obtained from CINT).
Definition: TDataType.h:46
unsigned int UInt_t
Definition: RtypesCore.h:42
virtual void Error(const char *method, const char *msgfmt,...) const
Issue error message.
Definition: TObject.cxx:925
virtual Int_t FindFirstKey(const void *key) const
Looks for the first index of the "key" within SORTED table AFTER sorting.
virtual Int_t GetNRows() const
Definition: TTableSorter.h:178
short Short_t
Definition: RtypesCore.h:35
The ROOT global object gROOT contains a list of all defined classes.
Definition: TClass.h:81
void * GetArray() const
Definition: TTable.h:284
char * StrDup(const char *str)
Duplicate the string str.
Definition: TString.cxx:2514
long Long_t
Definition: RtypesCore.h:50
Int_t fLastFound
Definition: TTableSorter.h:62
SEARCHMETHOD fSearchMethod
Definition: TTableSorter.h:72
#define ClassImp(name)
Definition: Rtypes.h:279
void ** fSortIndex
Definition: TTableSorter.h:61
double Double_t
Definition: RtypesCore.h:55
const char * At(Int_t i) const
Definition: TTableSorter.h:198
Int_t(* COMPAREMETHOD)(const void **, const void **)
Definition: TTableSorter.h:43
TList * GetListOfRealData() const
Definition: TClass.h:405
unsigned long ULong_t
Definition: RtypesCore.h:51
Int_t * fIndexArray
Definition: TTableSorter.h:68
Definition: TTable.h:52
char Char_t
Definition: RtypesCore.h:29
Short_t Max(Short_t a, Short_t b)
Definition: TMathBase.h:202
TTable::EColumnType fColType
Definition: TTableSorter.h:74
virtual Long_t GetNRows() const
Returns the number of the used rows for the wrapped table.
Definition: TTable.cxx:1392
void MakeZombie()
Definition: TObject.h:47
Int_t Size() const
Get size of basic typedef&#39;ed type.
Definition: TDataType.cxx:366
virtual Long_t GetRowSize() const
Returns the size (in bytes) of one table row.
Definition: TTable.cxx:1399
virtual ~TTableSorter()
to be documented
unsigned char UChar_t
Definition: RtypesCore.h:34
void SetSimpleArray(Int_t arraySize, Int_t firstRow, Int_t numberRows)
Set some common parameteres for the "simple" arrays.
const Bool_t kTRUE
Definition: Rtypes.h:91
virtual void SetTitle(const char *title="")
Set the title of the TNamed.
Definition: TNamed.cxx:155
const Int_t n
Definition: legend1.C:16
virtual const char * GetTableName() const
to be documented
char name[80]
Definition: TGX11.cxx:109
virtual const char * GetTableTitle() const
to be documented
virtual const char * GetTitle() const
Returns title of object.
Definition: TNamed.h:52
const char * Data() const
Definition: TString.h:349