Logo ROOT   6.14/05
Reference Guide
TTableSorter.h
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 #ifndef ROOT_TTableSorter
12 #define ROOT_TTableSorter
13 
14 #include "TNamed.h"
15 #include "TTableDescriptor.h"
16 
17 ////////////////////////////////////////////////////////////////////////////////////////
18 //
19 // TTableSorter - Is an "observer" class to sort the TTable objects
20 // The class provides an interface to the standard "C/C++"
21 //
22 // qsort and bsearch subroutine (for further information see your local C/C++ docs)
23 // ===== =======
24 //
25 // - This class DOESN'T change / touch the "host" table itself
26 // For any TTable object one can create as many different "sorter"
27 // as one finds useful for one's code
28 // - Any instance of this class is meaningful as long as the "host" object
29 // "TTable" does exist and is not changed
30 // - Any attempt to access this TTableSorter after the "host" object deleted
31 // causes the program abnormal termination
32 // - Any attempt to access this TTableSorter after the "host" object been changed
33 // causes an unpredictable result
34 // - Any instance (object) of this class is NOT deleted "by automatic" just
35 // the "host object "TTable" deleted. It is the responsibility of the user's code
36 // keeping TTableSorter and the the "host" TTable objects consistent.
37 //
38 ////////////////////////////////////////////////////////////////////////////////////////
39 
40 
41 class table_head_st;
42 
43 typedef Int_t (*COMPAREMETHOD)(const void **, const void **);
44 typedef Int_t (*SEARCHMETHOD) (const void *, const void **);
45 
46 class TTableSorter : public TNamed {
47 private:
48  union { Char_t fChar;
53  } fValue;
54 
55  TTableSorter(const TTableSorter&); // Not implemented.
56  TTableSorter &operator=(const TTableSorter&); // Not implemented.
57 
58 protected:
59  // enum EColumnType {kNAN, kFloat, kInt, kLong, kShort, kDouble, kUInt
60  // ,kULong, kUShort, kUChar, kChar };
61  void **fSortIndex; // Array of pointers to columns of the sorted table
62  Int_t fLastFound; // The index of the last found index within fSortIndex
63  Int_t fFirstRow; // first row of the table to be sorted
64  Int_t fNumberOfRows; // number of rows of the table to be sorted
67  Int_t fColSize; // The size of the selected column in bytes
68  Int_t *fIndexArray; // "parsed" indecis
69  Int_t fColDimensions;// The number of the dimensions for array (=-1 means it is a "simple" array)
70  const Char_t *fsimpleArray; // Pointer to the "simple" array;
71  const TTable *fParentTable; //!- the back pointer to the sorted table
72  SEARCHMETHOD fSearchMethod; // Function selected to search values
73  COMPAREMETHOD fCompareMethod; // Function to sort the original array
74  TTable::EColumnType fColType; // data type of the selected column
75  Long_t fParentRowSize; // To be filled from TTable::GetRowSize() method
76  const char *fFirstParentRow; //! pointer to the internal array of TTable object;
77 
78  static int CompareFloat_t (const void **, const void **);
79  static int CompareInt_t (const void **, const void **);
80  static int CompareLong_t (const void **, const void **);
81  static int CompareULong_t (const void **, const void **);
82  static int CompareUInt_t (const void **, const void **);
83  static int CompareShort_t (const void **, const void **);
84  static int CompareDouble_t (const void **, const void **);
85  static int CompareUShort_t (const void **, const void **);
86  static int CompareUChar_t (const void **, const void **);
87  static int CompareChar_t (const void **, const void **);
88  static int CompareBool_t (const void **, const void **);
89 
90  Int_t BSearch(const void *value) const;
91 
92  Int_t BSearch(Float_t value ) const;
93  Int_t BSearch(Int_t value ) const;
94  Int_t BSearch(ULong_t value ) const;
95  Int_t BSearch(Long_t value ) const;
96  Int_t BSearch(UInt_t value ) const;
97  Int_t BSearch(Short_t value ) const;
98  Int_t BSearch(Double_t value ) const;
99  Int_t BSearch(UShort_t value ) const;
100  Int_t BSearch(UChar_t value ) const;
101  Int_t BSearch(Char_t value ) const;
102  Int_t BSearch(Bool_t value ) const;
103 
104  // Int_t BSearch(const Char_t *value) const;
105  // Int_t BSearch(TString &value) ;
106 
108  Long_t GetRowSize();
109  void QSort();
110  void LearnTable();
111 
112  static int SearchFloat_t (const void *, const void **);
113  static int SearchInt_t (const void *, const void **);
114  static int SearchULong_t (const void *, const void **);
115  static int SearchLong_t (const void *, const void **);
116  static int SearchUInt_t (const void *, const void **);
117  static int SearchShort_t (const void *, const void **);
118  static int SearchDouble_t (const void *, const void **);
119  static int SearchUShort_t (const void *, const void **);
120  static int SearchUChar_t (const void *, const void **);
121  static int SearchChar_t (const void *, const void **);
122  static int SearchBool_t (const void *, const void **);
123 
124  Int_t SelectSearch(Float_t value ) const;
125  Int_t SelectSearch(Int_t value ) const;
126  Int_t SelectSearch(ULong_t value ) const;
127  Int_t SelectSearch(Long_t value ) const;
128  Int_t SelectSearch(UInt_t value ) const;
129  Int_t SelectSearch(Short_t value ) const;
130  Int_t SelectSearch(Double_t value ) const;
131  Int_t SelectSearch(UShort_t value ) const;
132  Int_t SelectSearch(UChar_t value ) const;
133  Int_t SelectSearch(Char_t value ) const;
134  Int_t SelectSearch(Bool_t value ) const;
135 
136  void SetSearchMethod();
137  void SetSimpleArray(Int_t arraySize, Int_t firstRow,Int_t numberRows);
138  void BuildSorter(TString &colName, Int_t firstRow, Int_t numberRows);
139  const char *At(Int_t i) const;
140 
141 public:
142  TTableSorter();
143  TTableSorter(const TTable &table, TString &colName, Int_t firstRow=0,Int_t numbeRows=0);
144  TTableSorter(const TTable *table, TString &colName, Int_t firstRow=0,Int_t numbeRows=0);
145 
146  TTableSorter(const TTable &table, SEARCHMETHOD search, COMPAREMETHOD compare, Int_t firstRow=0,Int_t numbeRows=0);
147  TTableSorter(const TTable *table, SEARCHMETHOD search, COMPAREMETHOD compare, Int_t firstRow=0,Int_t numbeRows=0);
148 
149  TTableSorter(const Float_t *simpleArray, Int_t arraySize, Int_t firstRow=0,Int_t numberRows=0);
150  TTableSorter(const Double_t *simpleArray, Int_t arraySize, Int_t firstRow=0,Int_t numberRows=0);
151  TTableSorter(const Long_t *simpleArray, Int_t arraySize, Int_t firstRow=0,Int_t numberRows=0);
152  virtual ~TTableSorter();
153 
154  virtual Int_t CountKey(const void *key, Int_t firstIndx=0,Bool_t bSearch=kTRUE,Int_t *firstRow=0) const;
155  virtual Int_t CountKeys() const;
156  virtual Int_t FindFirstKey(const void *key) const;
157 
158  Int_t BinarySearch(Float_t value ) const;
159  Int_t BinarySearch(Int_t value ) const;
160  Int_t BinarySearch(ULong_t value ) const;
161  Int_t BinarySearch(Long_t value ) const;
162  Int_t BinarySearch(UInt_t value ) const;
163  Int_t BinarySearch(Short_t value ) const;
164  Int_t BinarySearch(Double_t value ) const;
165  Int_t BinarySearch(UShort_t value ) const;
166  Int_t BinarySearch(UChar_t value ) const;
167  Int_t BinarySearch(Char_t value ) const;
168  Int_t BinarySearch(Bool_t value ) const;
169 
170  virtual const char *GetColumnName() const { return fColName.Data();}
171  Int_t GetIndex(UInt_t sortedIndex) const;
172  virtual const void *GetKeyAddress(Int_t indx) { return (fSortIndex && indx >= 0) ?fSortIndex[indx]:(void *)(-1);}
173  virtual Int_t GetLastFound() const { return fLastFound; }
174  virtual const char *GetTableName() const;
175  virtual const char *GetTableTitle() const;
176  virtual const char *GetTableType() const;
177  virtual TTable *GetTable() const;
178  virtual Int_t GetNRows() const { return fNumberOfRows;}
179  virtual Int_t GetFirstRow() const { return fFirstRow;}
180 
181  Int_t operator[](Int_t value) const;
182  Int_t operator[](Long_t value) const;
183  Int_t operator[](Double_t value) const;
184  Int_t operator[](void *value) const;
185  // Int_t operator[](const Char_t *value) const;
186  // Int_t operator[](TString &value) const { return BSearch(value); } // to be implemented
187 
188  Int_t operator()(Float_t value);
189  Int_t operator()(Int_t value);
190  Int_t operator()(Long_t value);
191  Int_t operator()(Double_t value);
192  // Int_t operator()(const Char_t *value) { return BinarySearch(*value); } // to be implemented
193  // Int_t operator()(TString &value) { return *this(value.Data()); } // to be implemented
194 
195  ClassDef(TTableSorter,0) // Is an "observer" class to sort the TTable objects
196 };
197 
198 inline const char *TTableSorter::At(Int_t i) const {return fFirstParentRow + i*fParentRowSize;}
200 
201 inline Int_t TTableSorter::operator[](Int_t value) const { return BSearch(value); }
202 inline Int_t TTableSorter::operator[](Long_t value) const { return BSearch(value); }
203 inline Int_t TTableSorter::operator[](Double_t value) const { return BSearch(value); }
204 inline Int_t TTableSorter::operator[](void *value) const { return BSearch(value); }
205 
206 inline Int_t TTableSorter::operator()(Float_t value) { return BinarySearch(value); }
207 inline Int_t TTableSorter::operator()(Int_t value) { return BinarySearch(value); }
208 inline Int_t TTableSorter::operator()(Long_t value) { return BinarySearch(value); }
209 inline Int_t TTableSorter::operator()(Double_t value) { return BinarySearch(value); }
210 
211 #endif
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 TTable * GetTable() const
to be documented
static int SearchShort_t(const void *, const void **)
static int CompareBool_t(const void **, const void **)
static int SearchLong_t(const void *, const void **)
Int_t fColSize
Definition: TTableSorter.h:67
static int CompareULong_t(const void **, const void **)
float Float_t
Definition: RtypesCore.h:53
Int_t fColOffset
Definition: TTableSorter.h:66
unsigned short UShort_t
Definition: RtypesCore.h:36
TString fColName
Definition: TTableSorter.h:65
static int CompareFloat_t(const void **, const void **)
pointer to the internal array of TTable object;
const char * fFirstParentRow
Definition: TTableSorter.h:76
static int CompareInt_t(const void **, const void **)
Float_t fFloat
Definition: TTableSorter.h:51
Int_t SelectSearch(Float_t value) const
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:131
virtual Int_t GetFirstRow() const
Definition: TTableSorter.h:179
int Int_t
Definition: RtypesCore.h:41
static int CompareShort_t(const void **, const void **)
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...
Int_t BSearch(const void *value) const
to be documented
static int SearchUChar_t(const void *, const void **)
COMPAREMETHOD fCompareMethod
Definition: TTableSorter.h:73
virtual Int_t CountKeys() const
Counts the number of different key values.
Long_t GetRowSize()
Definition: TTableSorter.h:199
const Char_t * fsimpleArray
Definition: TTableSorter.h:70
Double_t fDouble
Definition: TTableSorter.h:52
#define ClassDef(name, id)
Definition: Rtypes.h:320
virtual const char * GetTableType() const
to be documented
static int SearchULong_t(const void *, const void **)
The TNamed class is the base class for all named ROOT classes.
Definition: TNamed.h:29
Int_t operator[](Int_t value) const
Definition: TTableSorter.h:201
Int_t fFirstRow
Definition: TTableSorter.h:63
static int CompareUShort_t(const void **, const void **)
virtual const void * GetKeyAddress(Int_t indx)
Definition: TTableSorter.h:172
static int CompareChar_t(const void **, const void **)
static int CompareUInt_t(const void **, const void **)
Char_t fChar
Definition: TTableSorter.h:48
EColumnType
Definition: TTable.h:82
static int SearchBool_t(const void *, const void **)
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 BuildSorter(TString &colName, Int_t firstRow, Int_t numberRows)
BuildSorter backs TTableSorter ctor.
void QSort()
Call the standard C run-time library "qsort" function.
static int SearchUInt_t(const void *, const void **)
static int SearchChar_t(const void *, const void **)
static int CompareUChar_t(const void **, const void **)
Int_t BinarySearch(Float_t value) const
Long_t fParentRowSize
Definition: TTableSorter.h:75
union TTableSorter::@126 fValue
TTableSorter & operator=(const TTableSorter &)
unsigned int UInt_t
Definition: RtypesCore.h:42
Int_t operator()(Float_t value)
Definition: TTableSorter.h:206
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
static int CompareDouble_t(const void **, const void **)
static int SearchInt_t(const void *, const void **)
long Long_t
Definition: RtypesCore.h:50
static int SearchUShort_t(const void *, const void **)
Int_t fLastFound
Definition: TTableSorter.h:62
SEARCHMETHOD fSearchMethod
Definition: TTableSorter.h:72
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
unsigned long ULong_t
Definition: RtypesCore.h:51
static int SearchFloat_t(const void *, const void **)
Int_t * fIndexArray
Definition: TTableSorter.h:68
Definition: TTable.h:48
char Char_t
Definition: RtypesCore.h:29
TTable::EColumnType fColType
Definition: TTableSorter.h:74
virtual const char * GetColumnName() const
Definition: TTableSorter.h:170
static int CompareLong_t(const void **, const void **)
virtual ~TTableSorter()
to be documented
unsigned char UChar_t
Definition: RtypesCore.h:34
Long_t fLong
Definition: TTableSorter.h:50
static int SearchDouble_t(const void *, const void **)
void SetSimpleArray(Int_t arraySize, Int_t firstRow, Int_t numberRows)
Set some common parameteres for the "simple" arrays.
const Bool_t kTRUE
Definition: RtypesCore.h:87
virtual const char * GetTableName() const
to be documented
virtual const char * GetTableTitle() const
to be documented
const char * Data() const
Definition: TString.h:364