library: libTable #include "TTableSorter.h"

# TTableSorter

class description - source file - inheritance tree (.pdf)

## class TTableSorter : public TNamed

| Inheritance Chart:
`TObject`
| <- | `TNamed`
| <- | `TTableSorter` |

        protected:

          const char* At(Int_t i) const
                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
                 void BuildSorter(TString& colName, Int_t firstRow, Int_t numberRows)
           static int CompareBool_t(const void**, const void**)
           static int CompareChar_t(const void**, const void**)
           static int CompareDouble_t(const void**, const void**)
           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 CompareShort_t(const void**, const void**)
           static int CompareUChar_t(const void**, const void**)
           static int CompareUInt_t(const void**, const void**)
           static int CompareULong_t(const void**, const void**)
           static int CompareUShort_t(const void**, const void**)
               Bool_t FillIndexArray()
               Long_t GetRowSize()
                 void LearnTable()
                 void QSort()
           static int SearchBool_t(const void*, const void**)
           static int SearchChar_t(const void*, const void**)
           static int SearchDouble_t(const void*, const void**)
           static int SearchFloat_t(const void*, const void**)
           static int SearchInt_t(const void*, const void**)
           static int SearchLong_t(const void*, const void**)
           static int SearchShort_t(const void*, const void**)
           static int SearchUChar_t(const void*, const void**)
           static int SearchUInt_t(const void*, const void**)
           static int SearchULong_t(const void*, const void**)
           static int SearchUShort_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)

        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)
                                TTableSorter(const TTableSorter&)
                        virtual ~TTableSorter()
                          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
                 static TClass* Class()
                  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
          virtual const Text_t* GetColumnName() const
                  virtual Int_t GetFirstRow() const
                          Int_t GetIndex(UInt_t sortedIndex) const
            virtual const void* GetKeyAddress(Int_t indx) const
                  virtual Int_t GetLastFound() const
                  virtual Int_t GetNRows() const
                virtual TTable* GetTable() const
          virtual const Text_t* GetTableName() const
          virtual const Text_t* GetTableTitle() const
          virtual const Text_t* GetTableType() const
                virtual TClass* IsA() const
                          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[](Int_t value) const
                          Int_t operator[](Long_t value) const
                          Int_t operator[](Double_t value) const
                          Int_t operator[](void* value) const
                   virtual void ShowMembers(TMemberInspector& insp, char* parent)
                   virtual void Streamer(TBuffer& b)
                           void StreamerNVirtual(TBuffer& b)

### Data Members

        private:

          TTableSorter:: fValue

        protected:

                       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;

## Class Description

      TTableSorter  - Is an "observer" class to sort the TTable objects
                        The class provides an interface to the standard "C/C++"

     qsort and bsearch subroutines (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.

     "To do" list

      1. A separate method to provide lexicographical sort if the "sorted" column is a kind of array

      Usage:
        1. Create an instance of the sorter for the selected column of your table

            new TTableSorter(TTable &table, TString &colName,Int_t firstRow,Int_t numberRows)

            All sort actions are performed within TTableSorter ctor.
            This means one needs no extra effort to SORT table. "Sorter" contains
            the "sorted index array" as soon as you create the sorter

            TTableSorter sorter(MyTable,"id",20, 34);
              - Creates a sorter for MyTable column "id" ordering
                its 34 rows from 20 row with standard "C" qsort subroutine

        2.  You may use this instance to search any "id" value with operator []
              to get the table row index as follows:

              Int_t id = 5;
              Int_t index =  sorter[id]; // Look for the row index with id = 5
                                         // using the standard "C"  "bsearch" binary search
                                         // subroutine
              Int_t index =  sorter(id); // Look for the row index with id "nearest" to 5
                                         // using the internal "BinarySearch" method

        3. Some useful methods of this class:

            3.1. CountKeys()
            3.2  CountKey(const void *key, Int_t firstIndx=0,Bool_t bSearch=kTRUE,Int_t *firstRow=0)
            3.3. FindFirstKey(const void *key)
            3.4. GetIndex(UInt_t sortedIndex)

TTableSorter() : fsimpleArray(0),fParentTable(0)

     default ctor for RootCint dictionary

TTableSorter(const TTable &table, TString &colName,Int_t firstRow ,Int_t numberRows):fsimpleArray(0),fParentTable(&table)

     TTableSorter ctor sorts the input table along its column defined with colName

        - colName    - may be followed by the square brackets with integer number inside,
                       if that columm is an array (for example "phys[3]").
                       NO expression inside of [], only a single integer number allowed !
        - firstRow   - the first table row to sort from (=0 by default)
        - numberRows - the number of the table rows to sort (=0 by default)
                       = 0 means sort all rows from the "firstRow" by the end of table

TTableSorter(const TTable *table, TString &colName,Int_t firstRow ,Int_t numberRows):fsimpleArray(0),fParentTable(table)

     TTableSorter ctor sorts the input table along its column defined with colName

        - colName    - may be followed by the square brackets with integer number inside,
                       if that columm is an array (for example "phys[3]").
                       NO expression inside of [], only a single integer number allowed !
        - firstRow   - the first table row to sort from (=0 by default)
        - numberRows - the number of the table rows to sort (=0 by default)
                       = 0 means sort all rows from the "firstRow" by the end of table

TTableSorter(const TTable &table, SEARCHMETHOD search, COMPAREMETHOD compare, Int_t firstRow,Int_t numberRows) :fsimpleArray(0),fParentTable(&table)

     TTableSorter ctor sorts the input table according the function "search"

        - search     - the function to compare the "key" and the table rows during sorting
                       typedef Int_t (*SEARCHMETHOD) (const void *, const void **);

        - compare    - the function to compare two table rows during searching
                       typedef Int_t (*COMPAREMETHOD)(const void **, const void **);

        - firstRow   - the first table row to sort from (=0 by default)
        - numberRows - the number of the table rows to sort (=0 by default)
                       = 0 means sort all rows from the "firstRow" by the end of table
      Note:  This is a base class. If one fears it is not safe
      -----  to allow "void *" one may potect the end-user code
             providing a derived class with the appropriated type
             of the parameters.

TTableSorter(const TTable *table, SEARCHMETHOD search, COMPAREMETHOD compare, Int_t firstRow,Int_t numberRows) :fsimpleArray(0),fParentTable(table)

     TTableSorter ctor sorts the input table according the function "search"

        - search     - the function to compare the "key" and the table rows during sorting
                       typedef Int_t (*SEARCHMETHOD) (const void *, const void **);

        - compare    - the function to compare two table rows during searching
                       typedef Int_t (*COMPAREMETHOD)(const void **, const void **);

        - firstRow   - the first table row to sort from (=0 by default)
        - numberRows - the number of the table rows to sort (=0 by default)
                       = 0 means sort all rows from the "firstRow" by the end of table
      Note:  This is a base class. If one fears it is not safe
      -----  to allow "void *" one may potect the end-user code
             providing a derived class with the appropriated type
             of the parameters.

void BuildSorter(TString &colName, Int_t firstRow, Int_t numberRows)

     BuildSorter backs TTableSorter ctor

        - colName    - may be followed by the square brackets with integer number inside,
                       if that columm is an array (for example "phys[3]").
                       NO expression inside of [], only a single integer number allowed !
        - firstRow   - the first table row to sort from (=0 by default)
        - numberRows - the number of the table rows to sort (=0 by default)
                       = 0 means sort all rows from the "firstRow" by the end of table

TTableSorter(const Float_t *simpleArray, Int_t arraySize, Int_t firstRow ,Int_t numberRows) :fsimpleArray((const Char_t*)simpleArray) ,fParentTable(0)

     TTableSorter ctor sort the input "simpleArray"

        - arraySize  - the size of the full array
        - firstRow   - the first table row to sort from (=0 by default)
        - numberRows - the number of the table rows to sort (=0 by default)
                       = 0 means sort all rows from the "firstRow" by the end of table

TTableSorter(const Double_t *simpleArray, Int_t arraySize, Int_t firstRow ,Int_t numberRows) :fsimpleArray((const Char_t*)simpleArray) ,fParentTable(0)

     TTableSorter ctor sort the input "simpleArray"

        - arraySize  - the size of the full array
        - firstRow   - the first table row to sort from (=0 by default)
        - numberRows - the number of the table rows to sort (=0 by default)
                       = 0 means sort all rows from the "firstRow" by the end of table

TTableSorter(const Long_t *simpleArray, Int_t arraySize, Int_t firstRow ,Int_t numberRows) :fsimpleArray((const Char_t*)simpleArray) ,fParentTable(0)

     TTableSorter ctor sort the input "simpleArray"

        - arraySize  - the sie of the full array
        - firstRow   - the first table row to sort from (=0 by default)
        - numberRows - the number of the table rows to sort (=0 by default)
                       = 0 means sort all rows from the "firstRow" by the end of table

void SetSimpleArray(Int_t arraySize, Int_t firstRow,Int_t numberRows)

     Set some common parameteres for the "simple" arrays

~TTableSorter()

Int_t BSearch(valuetype value) const

Int_t SelectSearch(valuetype value) const

Int_t BSearch(const void *value) const

Int_t GetIndex(UInt_t sortedIndex) const

     returns the original index of the row by its sorted index

Int_t CountKey(const void *key, Int_t firstIndx, Bool_t bSearch, Int_t *firstRow) const

      CountKey counts the number of rows with the key value equal "key"

      key      - it is a POINTER to the key value
      fistIndx - the first index within sorted array to star search
                  = 0 by default
      bSearch  = kTRUE - binary search (by default) is used otherwise linear one

Int_t CountKeys() const

     Counts the number of different key values

Bool_t FillIndexArray()

     File the array of the pointers and check whether
     the original table has been sorted to avoid an extra job.

     Return: kTRUE  - the table has been sorted
             kFALSE - otherwise

Int_t FindFirstKey(const void *key) const

     Looks for the first index of the "key"
     within SORTED table AFTER sorting

     Returns: = -1 if the "key" was not found

     Note: This method has no sense for
     ====  the float and double key

           To get the index within the original
           unsorted table the GetIndex() method
           may be used like this:
           GetIndex(FindFirstKey(key))

const Text_t* GetTableName() const

const Text_t* GetTableTitle() const

const Text_t* GetTableType() const

TTable* GetTable() const

void SetSearchMethod()

     Select search function at once

void QSort()

     Call the standard C run-time library "qsort" function

void LearnTable()

      LearnTable() allows the TTableSorter to learn the structure of the
      tables used to fill the ntuple.
      table     - the name of the table
      buildTree - if kTRUE, then add TBranches to the TTree for each table
                  column (default=kFALSE)

### Inline Functions

                      int CompareFloat_t(const void**, const void**)
                      int CompareInt_t(const void**, const void**)
                      int CompareLong_t(const void**, const void**)
                      int CompareULong_t(const void**, const void**)
                      int CompareUInt_t(const void**, const void**)
                      int CompareShort_t(const void**, const void**)
                      int CompareDouble_t(const void**, const void**)
                      int CompareUShort_t(const void**, const void**)
                      int CompareUChar_t(const void**, const void**)
                      int CompareChar_t(const void**, const void**)
                      int CompareBool_t(const void**, const void**)
                    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
                   Long_t GetRowSize()
                      int SearchFloat_t(const void*, const void**)
                      int SearchInt_t(const void*, const void**)
                      int SearchULong_t(const void*, const void**)
                      int SearchLong_t(const void*, const void**)
                      int SearchUInt_t(const void*, const void**)
                      int SearchShort_t(const void*, const void**)
                      int SearchDouble_t(const void*, const void**)
                      int SearchUShort_t(const void*, const void**)
                      int SearchUChar_t(const void*, const void**)
                      int SearchChar_t(const void*, const void**)
                      int SearchBool_t(const void*, const void**)
                    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
              const char* At(Int_t i) 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
            const Text_t* GetColumnName() const
              const void* GetKeyAddress(Int_t indx) const
                    Int_t GetLastFound() const
                    Int_t GetNRows() const
                    Int_t GetFirstRow() const
                    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()(Float_t value)
                    Int_t operator()(Int_t value)
                    Int_t operator()(Long_t value)
                    Int_t operator()(Double_t value)
                  TClass* Class()
                  TClass* IsA() const
                     void ShowMembers(TMemberInspector& insp, char* parent)
                     void Streamer(TBuffer& b)
                     void StreamerNVirtual(TBuffer& b)
             TTableSorter TTableSorter(const TTableSorter&)

Author: Valery Fine 26/01/99 (E-mail: fine@bnl.gov)
Last update: root/star:$Name: $:$Id: TTableSorter.cxx,v 1.4 2005/01/19 18:30:58 brun Exp $