ROOT logo
// @(#)root/table:$Id: TTableSorter.h 27157 2009-01-15 14:05:12Z brun $
// Author: Valery Fine   26/01/99  (E-mail: fine@bnl.gov)

/*************************************************************************
 * Copyright (C) 1995-2000, Rene Brun and Fons Rademakers.               *
 * All rights reserved.                                                  *
 *                                                                       *
 * For the licensing terms see $ROOTSYS/LICENSE.                         *
 * For the list of contributors see $ROOTSYS/README/CREDITS.             *
 *************************************************************************/
#ifndef ROOT_TTableSorter
#define ROOT_TTableSorter

#include "TNamed.h"
#include "TTableDescriptor.h"

////////////////////////////////////////////////////////////////////////////////////////
//
//  TTableSorter  - Is an "observer" class to sort the TTable objects
//                    The class provides an interface to the standard "C/C++"
//
// qsort and bsearch subroutine (for further information see your local C/C++ docs)
// =====     =======
//
//  - This class DOESN'T change / touch the "host" table  itself
//    For any TTable object one can create as many different "sorter"
//    as he/she finds useful for his/her code
//  - Any instance of this class is meaningful as long as the "host" object
//    "TTable" does exist and is not changed
//  - Any attempt to access this TTableSorter after the "host" object deleted
//    causes the program abnormal termination
//  - Any attempt to access this TTableSorter after the "host" object been changed
//    causes an unpredictable result
//  - Any instance (object) of this class is NOT deleted "by automatic" just
//    the "host object "TTable" deleted. It is the responsibility of the user's code
//    keeping TTableSorter and the the "host" TTable objects consistent.
//
////////////////////////////////////////////////////////////////////////////////////////


class table_head_st;

typedef Int_t (*COMPAREMETHOD)(const void **, const void **);
typedef Int_t (*SEARCHMETHOD) (const void *, const void **);

class TTableSorter : public TNamed {
private:
   union {  Char_t   fChar;
   Int_t    fInt;
   Long_t   fLong;
   Float_t  fFloat;
   Double_t fDouble;
   } fValue;

protected:
   //   enum EColumnType {kNAN, kFloat, kInt, kLong, kShort, kDouble, kUInt
   //                           ,kULong, kUShort, kUChar, kChar };
   void    **fSortIndex;    // Array of pointers to columns of the sorted table
   Int_t     fLastFound;    // The index of the last found index within fSortIndex
   Int_t     fFirstRow;     // first row of the table to be sorted
   Int_t     fNumberOfRows; // number of rows of the table to be sorted
   TString   fColName;      //
   Int_t     fColOffset;    //
   Int_t     fColSize;      // The size of the selected column in bytes
   Int_t    *fIndexArray;   // "parsed" indecis
   Int_t     fColDimensions;// The number of the dimensions for array (=-1 means it is a "simple" array)
   const Char_t *fsimpleArray;    // Pointer to the "simple" array;
   const TTable *fParentTable;    //!- the back pointer to the sorted table
   SEARCHMETHOD  fSearchMethod;   // Function selected to search values
   COMPAREMETHOD fCompareMethod;  // Function to sort the original array
   TTable::EColumnType  fColType; // data type of the selected column
   Long_t  fParentRowSize;        // To be filled from TTable::GetRowSize() method
   const char *fFirstParentRow;   //! pointer to the internal array of TTable object;

   static int CompareFloat_t     (const void **, const void **);
   static int CompareInt_t       (const void **, const void **);
   static int CompareLong_t      (const void **, const void **);
   static int CompareULong_t     (const void **, const void **);
   static int CompareUInt_t      (const void **, const void **);
   static int CompareShort_t     (const void **, const void **);
   static int CompareDouble_t    (const void **, const void **);
   static int CompareUShort_t    (const void **, const void **);
   static int CompareUChar_t     (const void **, const void **);
   static int CompareChar_t      (const void **, const void **);
   static int CompareBool_t      (const void **, const void **);

   Int_t  BSearch(const void *value) const;

   Int_t BSearch(Float_t  value ) const;
   Int_t BSearch(Int_t    value ) const;
   Int_t BSearch(ULong_t  value ) const;
   Int_t BSearch(Long_t   value ) const;
   Int_t BSearch(UInt_t   value ) const;
   Int_t BSearch(Short_t  value ) const;
   Int_t BSearch(Double_t value ) const;
   Int_t BSearch(UShort_t value ) const;
   Int_t BSearch(UChar_t  value ) const;
   Int_t BSearch(Char_t   value ) const;
   Int_t BSearch(Bool_t   value ) const;

   //  Int_t BSearch(const Char_t *value) const;
   //  Int_t BSearch(TString &value)     ;

   Bool_t FillIndexArray();
   Long_t GetRowSize();
   void   QSort();
   void   LearnTable();

   static int SearchFloat_t     (const void *, const void **);
   static int SearchInt_t       (const void *, const void **);
   static int SearchULong_t     (const void *, const void **);
   static int SearchLong_t      (const void *, const void **);
   static int SearchUInt_t      (const void *, const void **);
   static int SearchShort_t     (const void *, const void **);
   static int SearchDouble_t    (const void *, const void **);
   static int SearchUShort_t    (const void *, const void **);
   static int SearchUChar_t     (const void *, const void **);
   static int SearchChar_t      (const void *, const void **);
   static int SearchBool_t      (const void *, const void **);

   Int_t SelectSearch(Float_t  value ) const;
   Int_t SelectSearch(Int_t    value ) const;
   Int_t SelectSearch(ULong_t  value ) const;
   Int_t SelectSearch(Long_t   value ) const;
   Int_t SelectSearch(UInt_t   value ) const;
   Int_t SelectSearch(Short_t  value ) const;
   Int_t SelectSearch(Double_t value ) const;
   Int_t SelectSearch(UShort_t value ) const;
   Int_t SelectSearch(UChar_t  value ) const;
   Int_t SelectSearch(Char_t   value ) const;
   Int_t SelectSearch(Bool_t   value ) const;

   void  SetSearchMethod();
   void  SetSimpleArray(Int_t arraySize, Int_t firstRow,Int_t numberRows);
   void  BuildSorter(TString &colName, Int_t firstRow, Int_t numberRows);
   const char *At(Int_t i) const;

public:
   TTableSorter();
   TTableSorter(const TTable &table, TString &colName, Int_t firstRow=0,Int_t numbeRows=0);
   TTableSorter(const TTable *table, TString &colName, Int_t firstRow=0,Int_t numbeRows=0);

   TTableSorter(const TTable &table, SEARCHMETHOD search, COMPAREMETHOD compare, Int_t firstRow=0,Int_t numbeRows=0);
   TTableSorter(const TTable *table, SEARCHMETHOD search, COMPAREMETHOD compare, Int_t firstRow=0,Int_t numbeRows=0);

   TTableSorter(const Float_t  *simpleArray, Int_t arraySize, Int_t firstRow=0,Int_t numberRows=0);
   TTableSorter(const Double_t *simpleArray, Int_t arraySize, Int_t firstRow=0,Int_t numberRows=0);
   TTableSorter(const Long_t   *simpleArray, Int_t arraySize, Int_t firstRow=0,Int_t numberRows=0);
   virtual ~TTableSorter();

   virtual Int_t CountKey(const void *key, Int_t firstIndx=0,Bool_t bSearch=kTRUE,Int_t *firstRow=0) const;
   virtual Int_t CountKeys() const;
   virtual Int_t FindFirstKey(const void *key) const;

   Int_t BinarySearch(Float_t  value ) const;
   Int_t BinarySearch(Int_t    value ) const;
   Int_t BinarySearch(ULong_t  value ) const;
   Int_t BinarySearch(Long_t   value ) const;
   Int_t BinarySearch(UInt_t   value ) const;
   Int_t BinarySearch(Short_t  value ) const;
   Int_t BinarySearch(Double_t value ) const;
   Int_t BinarySearch(UShort_t value ) const;
   Int_t BinarySearch(UChar_t  value ) const;
   Int_t BinarySearch(Char_t   value ) const;
   Int_t BinarySearch(Bool_t   value ) const;

   virtual const char   *GetColumnName() const { return fColName.Data();}
   Int_t     GetIndex(UInt_t sortedIndex) const;
   virtual const void     *GetKeyAddress(Int_t indx) { return (fSortIndex && indx >= 0) ?fSortIndex[indx]:(void *)(-1);}
   virtual       Int_t     GetLastFound()  const { return fLastFound; }
   virtual const char   *GetTableName()  const;
   virtual const char   *GetTableTitle() const;
   virtual const char   *GetTableType()  const;
   virtual       TTable   *GetTable()      const;
   virtual       Int_t     GetNRows()      const { return fNumberOfRows;}
   virtual       Int_t     GetFirstRow()   const { return fFirstRow;}

   Int_t operator[](Int_t value)    const;
   Int_t operator[](Long_t value)   const;
   Int_t operator[](Double_t value) const;
   Int_t operator[](void *value)    const;
   //    Int_t operator[](const Char_t *value) const;
   //    Int_t operator[](TString &value) const { return BSearch(value); }  // to be implemented

   Int_t operator()(Float_t value);
   Int_t operator()(Int_t value);
   Int_t operator()(Long_t value);
   Int_t operator()(Double_t value);
   //    Int_t operator()(const Char_t *value) { return BinarySearch(*value); } // to be implemented
   //    Int_t operator()(TString &value)    { return *this(value.Data());  }   // to be implemented

   ClassDef(TTableSorter,0) // Is an "observer" class to sort the TTable objects
};

inline const char *TTableSorter::At(Int_t i) const {return fFirstParentRow + i*fParentRowSize;}
inline Long_t TTableSorter::GetRowSize() { return fParentRowSize; }

inline Int_t TTableSorter::operator[](Int_t value)    const { return BSearch(value); }
inline Int_t TTableSorter::operator[](Long_t value)   const { return BSearch(value); }
inline Int_t TTableSorter::operator[](Double_t value) const { return BSearch(value); }
inline Int_t TTableSorter::operator[](void *value)    const { return BSearch(value); }

inline Int_t TTableSorter::operator()(Float_t value)  { return BinarySearch(value); }
inline Int_t TTableSorter::operator()(Int_t value)    { return BinarySearch(value); }
inline Int_t TTableSorter::operator()(Long_t value)   { return BinarySearch(value); }
inline Int_t TTableSorter::operator()(Double_t value) { return BinarySearch(value); }

#endif
 TTableSorter.h:1
 TTableSorter.h:2
 TTableSorter.h:3
 TTableSorter.h:4
 TTableSorter.h:5
 TTableSorter.h:6
 TTableSorter.h:7
 TTableSorter.h:8
 TTableSorter.h:9
 TTableSorter.h:10
 TTableSorter.h:11
 TTableSorter.h:12
 TTableSorter.h:13
 TTableSorter.h:14
 TTableSorter.h:15
 TTableSorter.h:16
 TTableSorter.h:17
 TTableSorter.h:18
 TTableSorter.h:19
 TTableSorter.h:20
 TTableSorter.h:21
 TTableSorter.h:22
 TTableSorter.h:23
 TTableSorter.h:24
 TTableSorter.h:25
 TTableSorter.h:26
 TTableSorter.h:27
 TTableSorter.h:28
 TTableSorter.h:29
 TTableSorter.h:30
 TTableSorter.h:31
 TTableSorter.h:32
 TTableSorter.h:33
 TTableSorter.h:34
 TTableSorter.h:35
 TTableSorter.h:36
 TTableSorter.h:37
 TTableSorter.h:38
 TTableSorter.h:39
 TTableSorter.h:40
 TTableSorter.h:41
 TTableSorter.h:42
 TTableSorter.h:43
 TTableSorter.h:44
 TTableSorter.h:45
 TTableSorter.h:46
 TTableSorter.h:47
 TTableSorter.h:48
 TTableSorter.h:49
 TTableSorter.h:50
 TTableSorter.h:51
 TTableSorter.h:52
 TTableSorter.h:53
 TTableSorter.h:54
 TTableSorter.h:55
 TTableSorter.h:56
 TTableSorter.h:57
 TTableSorter.h:58
 TTableSorter.h:59
 TTableSorter.h:60
 TTableSorter.h:61
 TTableSorter.h:62
 TTableSorter.h:63
 TTableSorter.h:64
 TTableSorter.h:65
 TTableSorter.h:66
 TTableSorter.h:67
 TTableSorter.h:68
 TTableSorter.h:69
 TTableSorter.h:70
 TTableSorter.h:71
 TTableSorter.h:72
 TTableSorter.h:73
 TTableSorter.h:74
 TTableSorter.h:75
 TTableSorter.h:76
 TTableSorter.h:77
 TTableSorter.h:78
 TTableSorter.h:79
 TTableSorter.h:80
 TTableSorter.h:81
 TTableSorter.h:82
 TTableSorter.h:83
 TTableSorter.h:84
 TTableSorter.h:85
 TTableSorter.h:86
 TTableSorter.h:87
 TTableSorter.h:88
 TTableSorter.h:89
 TTableSorter.h:90
 TTableSorter.h:91
 TTableSorter.h:92
 TTableSorter.h:93
 TTableSorter.h:94
 TTableSorter.h:95
 TTableSorter.h:96
 TTableSorter.h:97
 TTableSorter.h:98
 TTableSorter.h:99
 TTableSorter.h:100
 TTableSorter.h:101
 TTableSorter.h:102
 TTableSorter.h:103
 TTableSorter.h:104
 TTableSorter.h:105
 TTableSorter.h:106
 TTableSorter.h:107
 TTableSorter.h:108
 TTableSorter.h:109
 TTableSorter.h:110
 TTableSorter.h:111
 TTableSorter.h:112
 TTableSorter.h:113
 TTableSorter.h:114
 TTableSorter.h:115
 TTableSorter.h:116
 TTableSorter.h:117
 TTableSorter.h:118
 TTableSorter.h:119
 TTableSorter.h:120
 TTableSorter.h:121
 TTableSorter.h:122
 TTableSorter.h:123
 TTableSorter.h:124
 TTableSorter.h:125
 TTableSorter.h:126
 TTableSorter.h:127
 TTableSorter.h:128
 TTableSorter.h:129
 TTableSorter.h:130
 TTableSorter.h:131
 TTableSorter.h:132
 TTableSorter.h:133
 TTableSorter.h:134
 TTableSorter.h:135
 TTableSorter.h:136
 TTableSorter.h:137
 TTableSorter.h:138
 TTableSorter.h:139
 TTableSorter.h:140
 TTableSorter.h:141
 TTableSorter.h:142
 TTableSorter.h:143
 TTableSorter.h:144
 TTableSorter.h:145
 TTableSorter.h:146
 TTableSorter.h:147
 TTableSorter.h:148
 TTableSorter.h:149
 TTableSorter.h:150
 TTableSorter.h:151
 TTableSorter.h:152
 TTableSorter.h:153
 TTableSorter.h:154
 TTableSorter.h:155
 TTableSorter.h:156
 TTableSorter.h:157
 TTableSorter.h:158
 TTableSorter.h:159
 TTableSorter.h:160
 TTableSorter.h:161
 TTableSorter.h:162
 TTableSorter.h:163
 TTableSorter.h:164
 TTableSorter.h:165
 TTableSorter.h:166
 TTableSorter.h:167
 TTableSorter.h:168
 TTableSorter.h:169
 TTableSorter.h:170
 TTableSorter.h:171
 TTableSorter.h:172
 TTableSorter.h:173
 TTableSorter.h:174
 TTableSorter.h:175
 TTableSorter.h:176
 TTableSorter.h:177
 TTableSorter.h:178
 TTableSorter.h:179
 TTableSorter.h:180
 TTableSorter.h:181
 TTableSorter.h:182
 TTableSorter.h:183
 TTableSorter.h:184
 TTableSorter.h:185
 TTableSorter.h:186
 TTableSorter.h:187
 TTableSorter.h:188
 TTableSorter.h:189
 TTableSorter.h:190
 TTableSorter.h:191
 TTableSorter.h:192
 TTableSorter.h:193
 TTableSorter.h:194
 TTableSorter.h:195
 TTableSorter.h:196
 TTableSorter.h:197
 TTableSorter.h:198
 TTableSorter.h:199
 TTableSorter.h:200
 TTableSorter.h:201
 TTableSorter.h:202
 TTableSorter.h:203
 TTableSorter.h:204
 TTableSorter.h:205
 TTableSorter.h:206
 TTableSorter.h:207
 TTableSorter.h:208