/*
 * Copyright (c) 2000-2008
 * Author: Weiming Zhou
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  
 */

#include <stdlib.h>
#include "CapiGlobal.h"
#include "SortTable.h"
#include "Stack.h"

void SortTable_QuickSort2(SORTTABLE *pTable, UINT uStart, UINT uEnd, 
                        COMPAREFUNC CompareFunc);

void SortTable_QuickSort(SORTTABLE *pTable, UINT uStart, UINT uEnd, 
                        COMPAREFUNC CompareFunc);

void SortTable_QuickSort3(SORTTABLE *pTable, UINT uStart, UINT uEnd, 
                        COMPAREFUNC CompareFunc);

/**	排序表的創(chuàng)建函數(shù)

	@param	UINT uMaxCount - 排序表的最大尺寸	
	@return	SORTTABLE * - 成功返回排序表指針，失敗返回NULL	
*/
SORTTABLE *	SortTable_Create(UINT uMaxCount)
{
    SORTTABLE *pTable;

    if ( uMaxCount == 0 )
    {
        return NULL;
    }

    pTable = (SORTTABLE *)malloc(sizeof(struct SORTTABLE_st));
    if ( pTable != NULL )
    {
        pTable->ppData = (void **)malloc(uMaxCount * sizeof(void *));
        if ( pTable->ppData != NULL )
        {
            pTable->ppData[0] = NULL;
            pTable->uMaxCount = uMaxCount;
            pTable->uCursorCount = 0;
        }
        else
        {
            free( pTable );
            pTable = NULL;
        }
    }
    return pTable;
}

/**	排序表的釋放函數(shù)

	@param	SORTTABLE *pTable - 排序表指針	
	@param	DESTROYFUNC DestroyFunc - 數(shù)據(jù)釋放函數(shù)	
	@return	void - 無	
*/
void SortTable_Destroy( SORTTABLE *pTable, DESTROYFUNC DestroyFunc )
{
    if ( pTable != NULL )
    {
        if ( DestroyFunc != NULL )
        {
            UINT i;
            for ( i = 0; i < pTable->uCursorCount; i++ )
            {
                (*DestroyFunc)( pTable->ppData[i] );
            }
        }
        free( pTable->ppData );
        free( pTable );
    }
}

/**	排序表的添加數(shù)據(jù)函數(shù)，數(shù)據(jù)被添加到表尾部

	@param	SORTTABLE *pTable - 排序表指針	
	@param	void *pData - 加入的數(shù)據(jù)指針	
	@return	INT (by default) - 成功返回CAPI_SUCCESS, 失敗返回CAPI_FAILED	
*/
INT	SortTable_Add( SORTTABLE *pTable, void *pData )
{
    if ( pTable == NULL || pData == NULL 
        || pTable->uCursorCount >= pTable->uMaxCount )
    {
        return CAPI_FAILED;
    }
    pTable->ppData[pTable->uCursorCount] = pData;
    pTable->uCursorCount += 1;
    
    return CAPI_SUCCESS;
}

/**	排序表的二分查找函數(shù)，調(diào)用此函數(shù)前必須對表從小到大排好序

	@param	SORTTABLE *pTable - 排序表指針	
	@param	void *pData - 要查找的匹配數(shù)據(jù)
	@param	COMPAREFUNC CompareFunc - 比較函數(shù)
	@return	void * - 成功返回查到的數(shù)據(jù)，失敗返回NULL
*/
void * SortTable_FindData(SORTTABLE *pTable, void *pData, 
                               COMPAREFUNC CompareFunc)
{
    UINT uLow;
    UINT uHigh;
    UINT uMid;

    if ( pTable == NULL || CompareFunc == NULL || pData == NULL 
        || pTable->uCursorCount == 0 )
    {
        return NULL;
    }

    uLow = 0;
    uHigh = pTable->uCursorCount - 1;
    uMid = 0;
    while ( uLow <= uHigh )
    {
        INT nResult;
        uMid = ( uLow + uHigh ) / 2;
        nResult = (*CompareFunc)( pTable->ppData[uMid], pData );
        if ( nResult > 0 )
        {
            uHigh = uMid - 1;
        }
        else if ( nResult < 0 )
        {
            uLow = uMid + 1;
        }
        else
        {
            /* 已經(jīng)發(fā)現(xiàn)了匹配數(shù)據(jù)，返回 */
            return pTable->ppData[uMid];
        }
    }

    /* 未找到匹配數(shù)據(jù)，返回空指針 */
    return NULL;
}

/**	排序表的二分查找函數(shù)，調(diào)用此函數(shù)前必須對表從小到大排好序

	@param	SORTTABLE *pTable - 排序表指針	
	@param	void *pData - 要查找的匹配數(shù)據(jù)
	@param	COMPAREFUNC CompareFunc - 比較函數(shù)
	@return	void * - 成功返回查到的精確數(shù)據(jù)或剛好比要查找的數(shù)據(jù)大的數(shù)據(jù),
                        失敗返回NULL。
*/
void * SortTable_BlurFind(SORTTABLE *pTable, void *pData, 
                               COMPAREFUNC CompareFunc)
{
    UINT uLow;
    UINT uHigh;
    UINT uMid;

    if ( pTable == NULL || CompareFunc == NULL || pData == NULL 
        || pTable->uCursorCount == 0 )
    {
        return NULL;
    }

    uLow = 0;
    uHigh = pTable->uCursorCount - 1;
    uMid = 0;
    while ( uLow <= uHigh )
    {
        INT nResult;
        uMid = ( uLow + uHigh ) / 2;
        nResult = (*CompareFunc)( pTable->ppData[uMid], pData );
        if ( nResult > 0 )
        {
            uHigh = uMid - 1;
        }
        else if ( nResult < 0 )
        {
            uLow = uMid + 1;
        }
        else
        {
            /* 已經(jīng)發(fā)現(xiàn)了匹配數(shù)據(jù)，返回 */
            return pTable->ppData[uMid];
        }
    }

    /* 未找到匹配數(shù)據(jù)，返回剛好比它大的數(shù)據(jù) */
    return pTable->ppData[uHigh];
}

/**	排序表的按數(shù)組下標(biāo)索引取數(shù)據(jù)函數(shù)

	@param	SORTTABLE *pTable -排序表指針	
	@param	int uId - 數(shù)組下標(biāo)索引	
	@return	void * - 成功返回?cái)?shù)據(jù)指針，如果數(shù)組索引超出排序表當(dāng)前數(shù)據(jù)
                     的范圍則返回NULL
*/
void * SortTable_GetByID( SORTTABLE *pTable, UINT uId )
{
    void    *pData = NULL;

    if ( pTable != NULL )
    {
        if ( uId < pTable->uCursorCount )
        {
            pData = pTable->ppData[uId];
        }
    }
    return pData;
}

/**	排序表的排序函數(shù)

	@param	SORTTABLE *pTable -排序表指針	
	@param	COMPAREFUNC CompareFunc -數(shù)據(jù)比較函數(shù)	
	@return	INT -xxxx	
*/
INT SortTable_Sort(SORTTABLE *pTable, COMPAREFUNC CompareFunc)
{
    SortTable_QuickSort(pTable, 0, 
        pTable->uCursorCount - 1, CompareFunc);
    return CAPI_SUCCESS;
}

/**	排序表的快速排序劈開函數(shù)，將給定范圍數(shù)據(jù)按指定數(shù)據(jù)劈成兩部分，
    一部分全部小于指定數(shù)據(jù)，另一部分全部大于指定數(shù)據(jù)
    指定數(shù)據(jù)取給定范圍排序表中的第一個(gè)數(shù)據(jù)

	@param	SORTTABLE *pTable -排序表指針	
	@param	UINT uStart - 表中開始位置	
	@param	UINT uEnd - 表中結(jié)束位置	
	@param	COMPAREFUNC CompareFunc - 數(shù)據(jù)比較函數(shù)	
	@return	UINT - 指定數(shù)據(jù)在表中的位置，即它的數(shù)組下標(biāo)	
*/
static UINT SortTable_Split(SORTTABLE *pTable, UINT uStart, UINT uEnd,
                     COMPAREFUNC CompareFunc)
{
    void *pSelData;
    UINT uLow;
    UINT uHigh;

    uLow = uStart;
    uHigh = uEnd;

    pSelData = pTable->ppData[uLow];
    while ( uLow < uHigh )
    {
        while ( (*CompareFunc)(pTable->ppData[uHigh], pSelData) > 0 
            && uLow != uHigh )
        {
            --uHigh;
        }
        if ( uHigh != uLow )
        {
            pTable->ppData[uLow] = pTable->ppData[uHigh];
            ++uLow;
        }

        while ( (*CompareFunc)( pTable->ppData[uLow], pSelData ) < 0
            && uLow != uHigh )
        {
             ++uLow;
        }
        if ( uLow != uHigh )
        {
            pTable->ppData[uHigh] = pTable->ppData[uLow];
            --uHigh;
        }
    }
    pTable->ppData[uLow] = pSelData;

    return uLow;
}

/**	快速排序算法的使用棧的非遞歸算法函數(shù)

	@param	SORTTABLE *pTable - 排序表指針	
	@param	UINT uStart - 表中的要排序數(shù)據(jù)區(qū)間的起點(diǎn)，為數(shù)組下標(biāo)	
	@param	UINT uEnd - 表中要排序數(shù)據(jù)區(qū)間的終點(diǎn)，為數(shù)組下標(biāo)	
	@param	COMPAREFUNC CompareFunc - 數(shù)據(jù)比較函數(shù)	
	@return	void - 無 	
*/
void SortTable_QuickSort2(SORTTABLE *pTable, UINT uStart, UINT uEnd, 
                        COMPAREFUNC CompareFunc)
{
    STACK   *pStack;
    UINT    uLow;
    UINT    uHigh;
    UINT    uMid;

    uLow = uStart;
    uHigh = uEnd;

    pStack = Stack_Create(uHigh - uEnd);

    (void)Stack_Push(pStack, (void *)uLow);
    (void)Stack_Push(pStack, (void *)uHigh);

    while ( !Stack_IsEmpty(pStack) )
    {
        uHigh = (UINT)Stack_Pop(pStack);
        uLow = (UINT)Stack_Pop(pStack);
        if ( uLow < uHigh )
        {
            uMid = SortTable_Split(pTable, uLow, uHigh, CompareFunc );
            if ( uMid > uLow )
            {
                (void)Stack_Push(pStack, (void *)uLow );
                (void)Stack_Push(pStack, (void *)(uMid - 1 ));
            }
            if ( uHigh > uMid )
            {
                (void)Stack_Push(pStack, (void *)(uMid + 1) );
                (void)Stack_Push(pStack, (void *)uHigh);
            }
        }
    }
    Stack_Destroy(pStack, NULL);
}

/**	排序表的快速排序函數(shù)，不使用棧調(diào)用的非遞歸算法
    將指定區(qū)間的數(shù)據(jù)用快速排序算法排好

	@param	SORTTABLE *pTable - 排序表指針	
	@param	UINT uStart - 要排序的區(qū)間起點(diǎn)	
	@param	UINT uEnd - 要排序的區(qū)間終點(diǎn)		
	@param	COMPAREFUNC CompareFunc - 數(shù)據(jù)比較函數(shù)	
	@return	void - 無	
*/
void SortTable_QuickSort(SORTTABLE *pTable, UINT uStart, UINT uEnd, 
                        COMPAREFUNC CompareFunc)
{
    UINT   *puStack;
    UINT    uStackTop;
    UINT    uLow;
    UINT    uHigh;
    UINT    uMid;

    if ( uEnd - uStart < 1 )
    {
        return;
    }

    uLow = uStart;
    uHigh = uEnd;

    puStack = (UINT *)malloc((uHigh - uLow + 1) * sizeof(UINT));
    if ( puStack == NULL )
    {
        return;
    }
    uStackTop = 0;

    puStack[uStackTop] = uLow;
    ++uStackTop;
    puStack[uStackTop] = uHigh;
    ++uStackTop;

    while ( uStackTop != 0 )
    {
        --uStackTop;
        uHigh = puStack[uStackTop];

        --uStackTop;
        uLow = puStack[uStackTop];
        
        if ( uLow < uHigh )
        {
            uMid = SortTable_Split(pTable, uLow, uHigh, CompareFunc );
            if ( uMid - uLow > uHigh - uMid )
            {
                puStack[uStackTop] = uLow;
                ++uStackTop;
                puStack[uStackTop] = uMid - 1;
                ++uStackTop;
                if ( uHigh > uMid )
                {
                    puStack[uStackTop] = uMid + 1;
                    ++uStackTop;
                    puStack[uStackTop] = uHigh;
                    ++uStackTop;
                }            
            }
            else
            {
                puStack[uStackTop] = uMid + 1;
                ++uStackTop;
                puStack[uStackTop] = uHigh;
                ++uStackTop;
                if ( uMid > uLow )
                {
                    puStack[uStackTop] = uLow;
                    ++uStackTop;
                    puStack[uStackTop] = uMid - 1;
                    ++uStackTop;
                }
            }

        }
    }
    free( puStack );
}

/**	排序表的快速排序函數(shù)，將指定區(qū)間的數(shù)據(jù)用快速排序算法排好

	@param	SORTTABLE *pTable - 排序表指針	
	@param	UINT uStart - 要排序的區(qū)間起點(diǎn)	
	@param	UINT uEnd - 要排序的區(qū)間終點(diǎn)		
	@param	COMPAREFUNC CompareFunc - 數(shù)據(jù)比較函數(shù)	
	@return	void - 無	
*/
void SortTable_QuickSort3(SORTTABLE *pTable, UINT uStart, UINT uEnd, 
                        COMPAREFUNC CompareFunc)
{
    UINT uMid = SortTable_Split(pTable, uStart, uEnd, CompareFunc );
    if ( uMid > uStart )
    {
        SortTable_QuickSort3(pTable, uStart, uMid - 1, CompareFunc);
    }

    if ( uEnd > uMid )
    {
        SortTable_QuickSort3(pTable, uMid + 1, uEnd, CompareFunc);
    }
}