1 /*************** Csort H Declares Source Code File (.H) ****************/ 2 /* Name: CSORT.H Version 1.2 */ 3 /* */ 4 /* (C) Copyright to the author Olivier BERTRAND 2000-2012 */ 5 /* */ 6 /* This file contains the CSORT class declares (not 64-bits ready) */ 7 /* */ 8 /* Note on use of this class: This class is meant to be used as a */ 9 /* base class by the calling class. This is because the comparison */ 10 /* routine must belong to both CSORT and the calling class. */ 11 /* This avoids to pass explicitly to it the calling "this" pointer. */ 12 /***********************************************************************/ 13 #if !defined(CSORT_DEFINED) 14 #define CSORT_DEFINED 15 16 #include <math.h> /* Required for log function */ 17 #undef DOMAIN // Was defined in math.h 18 19 /***********************************************************************/ 20 /* Constant and external definitions. */ 21 /***********************************************************************/ 22 #define THRESH 4 /* Threshold for insertion (was 4) */ 23 #define MTHRESH 6 /* Threshold for median */ 24 25 //extern FILE *debug; /* Debug file */ 26 27 typedef int* const CPINT; 28 29 /***********************************************************************/ 30 /* This is the CSORT base class declaration. */ 31 /***********************************************************************/ 32 class DllExport CSORT { 33 public: 34 // Constructor 35 CSORT(bool cns, int th = THRESH, int mth = MTHRESH); ~CSORT()36 virtual ~CSORT() {} 37 protected: 38 // Implementation 39 /*********************************************************************/ 40 /* qsortx/qstx are NOT conservative but use less storage space. */ 41 /* qsortc/qstc ARE conservative but use more storage space. */ 42 /*********************************************************************/ 43 int Qsortx(void); /* Index quick/insert sort */ 44 void Qstx(int *base, int *max); /* Preliminary quick sort */ 45 int Qsortc(void); /* Conservative q/ins sort */ 46 void Qstc(int *base, int *max); /* Preliminary quick sort */ 47 void Istc(int *base, int *hi, int *max); /* Insertion sort routine */ 48 49 public: 50 // Methods 51 int Qsort(PGLOBAL g, int n); /* Sort calling routine */ 52 //virtual void Printf(PGLOBAL g, FILE *f, uint n); 53 //virtual void Prints(PGLOBAL g, char *ps, uint z); 54 #ifdef DEBTRACE GetNcmp(void)55 int GetNcmp(void) {return num_comp;} 56 #endif 57 58 protected: 59 // Overridable 60 virtual int Qcompare(int *, int *) = 0; /* Item compare routine */ 61 #ifdef DEBTRACE 62 virtual void DebugSort(int ph, int n, int *base, int *mid, int *tmp); 63 #endif 64 65 public: 66 // Utility SetCmpNum(void)67 static void SetCmpNum(void) 68 {for (int i = 1; i < 1000; i++) Cpn[i] = Cmpnum(i); Limit = 1000;} 69 protected: Cmpnum(int n)70 static size_t Cmpnum(int n) 71 #if defined(AIX) 72 {return (n < Limit) ? Cpn[n] 73 : (size_t)round(1.0 + (double)n * (log2((double)n) - 1.0));} 74 #else // !AIX 75 {return (n < Limit) ? Cpn[n] 76 : (size_t)(1.5 + (double)n * (log((double)n)/Lg2 - 1.0));} 77 #endif // !AIX 78 79 80 // Members 81 static int Limit; /* Size of precalculated array */ 82 static size_t Cpn[1000]; /* Precalculated cmpnum values */ 83 static double Lg2; /* Precalculated log(2) value */ 84 PGLOBAL G; 85 PDBUSER Dup; /* Used for progress info */ 86 bool Cons; /* true for conservative sort */ 87 int Thresh; /* Threshold for using qsort */ 88 int Mthresh; /* Threshold for median find */ 89 int Nitem; /* Number of items to sort */ 90 MBLOCK Index; /* Index allocation block */ 91 MBLOCK Offset; /* Offset allocation block */ 92 CPINT &Pex; /* Reference to sort index */ 93 CPINT &Pof; /* Reference to offset array */ 94 int *Swix; /* Pointer on EQ/GT work area */ 95 int Savmax; /* Saved ProgMax value */ 96 int Savcur; /* Saved ProgCur value */ 97 LPCSTR Savstep; /* Saved progress step */ 98 #ifdef DEBTRACE 99 int num_comp; /* Number of quick sort calls */ 100 #endif 101 }; // end of class CSORT 102 103 #endif // CSORT_DEFINED 104 105