GrateSort source(исходный модуль)

GrateSort source(исходный модуль)
© Copyright chillugy@omsk.net.ru (2004)

#define AND &&
#define OR ||
#define Forever for(;;)
#define BEGIN for(;;){
#define END break;}
#define NIL ""
#define NN dec << ' ' << __LINE__ << endl
#define NNN dec << ' ' << __FILE__ << ' ' << __LINE__ << endl
typedef void __fastcall (*GSSwap)(void* elem1, void* elem2);
typedef int __fastcall (*GSCompare)(void* elem1, void* elem2);
typedef void* __fastcall (*GSPointer)(void* Array, const int index);
typedef void* __fastcall (*GSInc)(void* elem);
typedef void* __fastcall (*GSDec)(void* elem);
typedef void* __fastcall (*GSIncH)(void* elem, int h);
typedef void* __fastcall (*GSDecH)(void* elem, int h);
typedef void* (*GSCreate)();
typedef void __fastcall (*GSDelete)(void* elem);
typedef void __fastcall (*GSCopy)(void* Dst, void* Src);
class GSStackItem
{
public:
void* Array;
int n;
};
class GSStack
{
public:
GSStackItem* Top;
void* pNew;
static const int Limit1;
static const int Limit2;
GSDelete gsDelete;
GSStackItem* array;
__fastcall GSStack(const int total, GSCreate, GSDelete);
~GSStack();
void destroy();
};
class GSFuncs
{
public:
GSSwap pSwap;
GSCompare pCompare;
GSPointer pPointer;
GSInc pInc;
GSDec pDec;
GSIncH pIncH;
GSDecH pDecH;
GSCreate pCreate;
GSDelete pDelete;
GSCopy pCopy;
};
void __fastcall GrateSort1(const int n, void* Array, GSFuncs*);
void __fastcall ShellMethod(const int n, void* Array, GSFuncs*);
void __fastcall SimpleInserts(const int n, void* Array, GSFuncs*);
void __fastcall BackInserts(const int n, void* Array, GSFuncs*);
void __fastcall BinaryInserts(const int n, void* Array, GSFuncs*);
int __fastcall UpLog2(const int);
int __fastcall UpLog2(const int theN)
{
int N;
asm
{
push ebx
push ecx
mov ebx,theN
or ebx,ebx
jns ULPlus
db 15,11 // ud2
ULPlus:
bsr ecx,ebx
bsf edx,ebx
cmp ecx,edx
je ULE
inc ecx
ULE:
mov N,ecx
//ULExit:
pop ecx
pop ebx
}
return N;
}
const int GSStack::Limit1 = 10;
const int GSStack::Limit2 = 12;
static void __fastcall InsertUp(const int n, void* Array, const int index,
GSFuncs* pFuncs);
static void __fastcall InsertDown(const int n, void* Array, const int index,
GSFuncs* pFuncs);
__fastcall GSStack::GSStack(const int total, GSCreate theCreate,
GSDelete theDelete)// : Limit1(10), Limit2(12)
{
gsDelete = theDelete;
array = new GSStackItem[total];
Top = array;
pNew = (*theCreate)();
}
GSStack::~GSStack()
{
destroy();
}
void GSStack::destroy()
{
delete[] array; array = NULL;
(*gsDelete)(pNew); pNew = NULL;
}
void __fastcall GrateSort1(const int n, void* Array, GSFuncs* pFuncs)
{
if (n <= 1) return;
int StackSize = UpLog2(n);
GSStack gsStack(StackSize, pFuncs->pCreate, pFuncs->pDelete);
gsStack.Top->Array = Array;
gsStack.Top->n = n;
/*GSStack::pNew = (*pFuncs->pCreate)();*/
bool bCheck = true;
Forever {
if (gsStack.Top->n < gsStack.Limit1)
{
SimpleInserts(gsStack.Top->n, gsStack.Top->Array, pFuncs);
if (gsStack.Top <= gsStack.array)
{
gsStack.Top = NULL; break;
}
gsStack.Top--; continue;
}
if (gsStack.Top->n < gsStack.Limit2)
{
ShellMethod(gsStack.Top->n, gsStack.Top->Array, pFuncs);
if (gsStack.Top <= gsStack.array)
{
gsStack.Top = NULL; break;
}
}
int ln, rn;
ln = gsStack.Top->n / 2; rn = gsStack.Top->n - ln;
// LeftArray[0:ln - 1], RightArray[ln:n - 1]
// li = ln - 1 - i; 0..ln-1 <=> ln-1..0
// ri = i - ln; 0..rn - 1 <=> ln..n - 1
int I;
if ((rn > ln) AND ((rn % 2) == 1))
{
// i -> (2i+1, {2i+2}) 2i+2 is missing
int i = (rn - 1) / 2 + ln;
void* pI = (*pFuncs->pPointer)(gsStack.Top->Array, i);
void* pJ = (*pFuncs->pPointer)(gsStack.Top->Array, gsStack.Top->n - 1);
if ((*pFuncs->pCompare)(pI, pJ) == 1) (*pFuncs->pSwap)(pI, pJ);
}
I = (ln - 1) / 2; // the current index
// rI = I + ln; lI = ln - 1 - I;
void* ArrayDown = (*pFuncs->pPointer)(gsStack.Top->Array, ln);
Forever
{
void* pIUp = (*pFuncs->pPointer)(gsStack.Top->Array, ln - 1 - I);
void* pIDown = (*pFuncs->pPointer)(ArrayDown, I);
Forever
{
InsertDown(rn, ArrayDown, I, pFuncs);
InsertUp(ln, gsStack.Top->Array, I, pFuncs);
if ((*pFuncs->pCompare)(pIUp, pIDown) == 1)
{
(*pFuncs->pSwap)(pIUp, pIDown); continue;
}
break;
}
if (I == 0) break;
I--;
}
{
// To check up both half
for (int ii = 0;ii < ln;ii++)
{
int ii2 = 2*ii + 1;
if (ii2 >= ln) continue;
void* pii = (*pFuncs->pPointer)(gsStack.Top->Array, ln - 1 - ii);
void* pii2 = (*pFuncs->pPointer)(gsStack.Top->Array, ln - 1 - ii2);
if ((*pFuncs->pCompare)(pii, pii2) == -1)
{
bCheck = false;
}
int ii3 = 2*ii + 2;
if (ii3 >= ln) continue;
void* pii3 = (*pFuncs->pPointer)(gsStack.Top->Array, ln - 1 - ii3);
if ((*pFuncs->pCompare)(pii, pii3) == -1)
{
bCheck = false;
}
}
for (int ii = 0;ii < rn;ii++)
{
int ii2 = 2*ii + 1;
if (ii2 >= rn) continue;
void* pii = (*pFuncs->pPointer)(ArrayDown, ii);
void* pii2 = (*pFuncs->pPointer)(ArrayDown, ii2);
if ((*pFuncs->pCompare)(pii, pii2) == 1)
{
bCheck = false;
}
int ii3 = 2*ii + 2;
if (ii3 >= rn) continue;
void* pii3 = (*pFuncs->pPointer)(ArrayDown, ii3);
if ((*pFuncs->pCompare)(pii, pii3) == 1)
{
bCheck = false;
}
}
if (!bCheck)
{
throw Exception("GrateSort1");
}
}
if (!bCheck) break;
gsStack.Top->n = ln;
void* Array2 = (*pFuncs->pPointer)(gsStack.Top->Array, ln);
gsStack.Top++;
gsStack.Top->Array = Array2;
gsStack.Top->n = rn;
}
gsStack.destroy();
}
void __fastcall ShellMethod(const int n, void* Array, GSFuncs* pFuncs)
{
if (n < GSStack::Limit1)
{
SimpleInserts(n, Array, pFuncs); return;
}
int h = 1;
Forever {
if (h > n) break;
h = h * 3 + 1;
}
h = h / 3;
void* pNew = (*pFuncs->pCreate)();
void* pI;
void* pJ;
void* pII;
Forever
{
for (int offset = 0;offset < h;offset++)
{
// Сортировка обратными вставками с шагом h и смещением offset
pI = (*pFuncs->pPointer)(Array, offset);
for (int i = offset + h;i < n;i += h)
{
pJ = pI;
pI = (*pFuncs->pIncH)(pI, h);
pII = pI;
for (int j = i - h;j >= offset;j -= h)
{
if ((*pFuncs->pCompare)(pII, pJ) == -1)
{
(*pFuncs->pSwap)(pII, pJ);
pII = (*pFuncs->pDecH)(pII, h);
if (j > offset) pJ = (*pFuncs->pDecH)(pJ, h);
continue;
}
break;
}
}
}
h = h / 3;
if (h == 1)
{
BackInserts(n, Array, pFuncs);
break;
}
}
(*pFuncs->pDelete)(pNew);
}
void __fastcall SimpleInserts(const int n, void* Array, GSFuncs* pFuncs)
{
if (n < 0) throw Exception("GS3");
if (n == 0) return;
if (n == 1) return;
if (n == 2)
{
void* p2 = (*pFuncs->pPointer)(Array, 1);
if ((*pFuncs->pCompare)(Array, p2) == -1) (*pFuncs->pSwap)(Array, p2);
return;
}
void* pI = Array;
void* pJ;
void* pNew = (*pFuncs->pCreate)();
void* pII;
void* pJJ;
int shift; // = 0;
for (int i = 1;i < n;i++)
{
char* cI1 = (char*)pI;
pI = (*pFuncs->pInc)(pI);
char* cI2 = (char*)pI;
shift = cI2 - cI1;
pJ = Array;
for (int j = 0;j < i;j++)
{
if ((*pFuncs->pCompare)(pI, pJ) == -1)
{
(*pFuncs->pCopy)(pNew, pI);
pII = pI;
pJJ = pII;
for (int jj = i;jj > j;jj--)
{
pJJ = (*pFuncs->pDec)(pJJ);
(*pFuncs->pCopy)(pII, pJJ);
pII = (*pFuncs->pDec)(pII);
}
(*pFuncs->pCopy)(pJ, pNew);
break;
}
pJ = (*pFuncs->pInc)(pJ);
}
}
(*pFuncs->pDelete)(pNew);
}
void __fastcall BackInserts(const int n, void* Array, GSFuncs* pFuncs)
{
if (n < 0) throw Exception("GS4");
if (n == 0) return;
if (n == 1) return;
if (n == 2)
{
void* p2 = (*pFuncs->pPointer)(Array, 1);
if ((*pFuncs->pCompare)(Array, p2) == -1) (*pFuncs->pSwap)(Array, p2);
return;
}
void* pI = Array;
void* pJ;
void* pII;
for (int i = 1;i < n;i++)
{
pJ = pI;
pI = (*pFuncs->pInc)(pI);
pII = pI;
for (int j = i - 1;j >= 0;j--)
{
if ((*pFuncs->pCompare)(pII, pJ) == -1) // pJ, pII
{
(*pFuncs->pSwap)(pJ, pII);
pII = (*pFuncs->pDec)(pII);
if (j > 0) pJ = (*pFuncs->pDec)(pJ);
continue;
}
break;
}
}
}
void __fastcall InsertDown(const int n, void* Array, const int index,
GSFuncs* pFuncs)
{
int index2, index3;
index2 = 2 * index + 1;
if (index2 >= n) return;
void* pI = (*pFuncs->pPointer)(Array, index);
index3 = 2 * index + 2;
void* pI2 = (*pFuncs->pPointer)(Array, index2);
if (index3 >= n)
{ // only index2
if ((*pFuncs->pCompare)(pI, pI2) == 1)
{
(*pFuncs->pSwap)(pI, pI2);
InsertDown(n, Array, index2, pFuncs);
}
return;
}
void* pI3 = (*pFuncs->pPointer)(Array, index3);
if ((*pFuncs->pCompare)(pI2, pI3) == 1) // *pI2 > *pI3
{
// use pI3
if ((*pFuncs->pCompare)(pI, pI3) == 1)
{
(*pFuncs->pSwap)(pI, pI3);
InsertDown(n, Array, index3, pFuncs);
}
return;
}
else
{
// use pI2
if ((*pFuncs->pCompare)(pI, pI2) == 1)
{
(*pFuncs->pSwap)(pI, pI2);
InsertDown(n, Array, index2, pFuncs);
}
}
}
void __fastcall InsertUp(const int n, void* Array, const int index,
GSFuncs* pFuncs)
{
int index2, index3;
index2 = 2 * index + 1;
if (index2 >= n) return;
void* pI = (*pFuncs->pPointer)(Array, n - 1 - index);
index3 = 2 * index + 2;
void* pI2 = (*pFuncs->pPointer)(Array, n - 1 - index2);
if (index3 >= n)
{ // only index2
if ((*pFuncs->pCompare)(pI, pI2) == -1)
{
(*pFuncs->pSwap)(pI, pI2);
InsertUp(n, Array, index2, pFuncs);
}
return;
}
void* pI3 = (*pFuncs->pPointer)(Array, n - 1 - index3);
if ((*pFuncs->pCompare)(pI2, pI3) == -1) // *pI2 < *pI3
{
// use pI3
if ((*pFuncs->pCompare)(pI, pI3) == -1)
{
(*pFuncs->pSwap)(pI, pI3);
InsertUp(n, Array, index3, pFuncs);
}
return;
}
else
{
// use pI2
if ((*pFuncs->pCompare)(pI, pI2) == -1)
{
(*pFuncs->pSwap)(pI, pI2);
InsertUp(n, Array, index2, pFuncs);
}
}
}

Используются технологии uCoz