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
27typedef int* const CPINT;
28
29/***********************************************************************/
30/* This is the CSORT base class declaration. */
31/***********************************************************************/
32class DllExport CSORT {
33 public:
34 // Constructor
35 CSORT(bool cns, int th = THRESH, int mth = MTHRESH);
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
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
67 static void SetCmpNum(void)
68 {for (int i = 1; i < 1000; i++) Cpn[i] = Cmpnum(i); Limit = 1000;}
69 protected:
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