/*
 * 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 <windows.h>
#include "capiglobal.h"
#include "BinTree.h"
#include "AVLTree.h"
#include "HashAVLTree.h"

/**	哈希AVL樹的創建函數

	@param	UINT uBucketCount - 哈希AVL樹中BUCKET數量	
	@return	HASHAVLTREE * - 失敗返回NULL,成功返回創建的哈希AVL樹指針	
*/
HASHAVLTREE *HashAVLTree_Create(UINT uBucketCount)
{
    HASHAVLTREE	*pTree;
    
    if ( uBucketCount == 0 )
    {
        return NULL;
    }
    
    pTree = (HASHAVLTREE *)malloc( sizeof(HASHAVLTREE) );
    if ( pTree == NULL )
    {
        return NULL;
    }
    
    pTree->uNodeCount = 0;
    pTree->uBucketCount = uBucketCount;
    
    pTree->ppBucket = (AVLTREENODE **)malloc( uBucketCount 
        * sizeof(AVLTREENODE *));
    
    if (pTree->ppBucket == NULL)
    {
        free( pTree );
        return NULL;
    }
    
    memset(pTree->ppBucket, 0, uBucketCount * sizeof(AVLTREENODE *));
    
    pTree->pCurEntry = NULL;
    pTree->uCurBucketNo = 0;
    
    return pTree;
}

/**	哈希AVL樹的釋放函數
        將哈希AVL樹中所有數據和節點及整個哈希AVL樹整體釋放掉

	@param	HASHAVLTREE *pHashAVLTree - 要釋放的哈希AVL樹指針	
	@param	DESTROYFUNC DestroyFunc - 數據釋放回調函數	
	@return	void - 無	
*/
void HashAVLTree_Destroy(HASHAVLTREE *pHashAVLTree, DESTROYFUNC DestroyFunc)
{
    AVLTREENODE **ppBucket;
    AVLTREENODE  *pNode;
    UINT i;
    
    if ( pHashAVLTree == NULL )
    {
        return;
    }
    ppBucket = pHashAVLTree->ppBucket;
    for ( i = 0; i < pHashAVLTree->uBucketCount; i++ ) 
    {
        pNode = ppBucket[i];
        BinTreeBaseNode_Destroy(pNode, DestroyFunc);
    }
    free(ppBucket);
    
    /* 將ppbucket設成空指針以避免哈希表被重新使用時造成內存泄漏 */
    pHashAVLTree->ppBucket = NULL;
    
    free( pHashAVLTree );    
}


/**	哈希AVL樹的插入函數

	@param	HASHAVLTREE *pHashAVLTree - 哈希AVL樹指針	
	@param	void *pData - 要插入的數據指針	
	@param	HASHFUNC HashFunc - 哈希函數	
	@param	COMPAREFUNC CompareFunc - 數據比較回調函數	
	@return	INT - 失敗返回CAPI_FAILED,成功返回CAPI_SUCCESS.	
*/
INT HashAVLTree_Insert(HASHAVLTREE *pHashAVLTree, void *pData, 
                       HASHFUNC HashFunc, COMPAREFUNC CompareFunc)
{
    UINT	uIndex;
    
    if ( pHashAVLTree == NULL || pData == NULL || HashFunc == NULL )
    {
        return CAPI_FAILED;
    }
    
    uIndex = (*HashFunc)( pData, pHashAVLTree->uBucketCount );
    
    /* 將新節點插入到鏈表的頭部 */
    AVLTreeNode_Insert(&((pHashAVLTree->ppBucket)[uIndex]), pData, CompareFunc);
    
    pHashAVLTree->uNodeCount += 1;
    
    return CAPI_SUCCESS;
}

/**	哈希AVL樹的節點刪除函數

	@param	HASHAVLTREE *pHashAVLTree - 哈希AVL樹指針	
	@param	void *pData - 數據指針	
	@param	HASHFUNC HashFunc - 哈希函數	
	@param	COMPAREFUNC CompareFunc - 數據比較回調函數	
	@param	DESTROYFUNC DestroyFunc - 數據釋放回調函數	
	@return	INT - 失敗返回CAPI_FAILED,成功返回CAPI_SUCCESS.	
*/
INT HashAVLTree_Delete(HASHAVLTREE *pHashAVLTree, void *pData, 
                      HASHFUNC HashFunc, 
                      COMPAREFUNC CompareFunc,
                      DESTROYFUNC DestroyFunc)
{
    UINT	    uIndex;
    
    if ( pHashAVLTree == NULL || pData == NULL || HashFunc == NULL 
        || CompareFunc == NULL )
    {
        return CAPI_FAILED;
    }
    
    uIndex = (*HashFunc)( pData, pHashAVLTree->uBucketCount );

    if ( AVLTreeNode_Delete(&((pHashAVLTree->ppBucket)[uIndex]), pData, 
        CompareFunc, DestroyFunc) != CAPI_NOT_FOUND )
    {
        pHashAVLTree->uNodeCount -= 1;
    }

    return CAPI_SUCCESS;
}

/**	哈希AVL樹的查找函數

	@param	HASHAVLTREE *pHashAVLTree - 哈希AVL樹指針	
	@param	void *pData - 要查找的數據指針	
	@param	HASHFUNC HashFunc - 哈希函數	
	@param	COMPAREFUNC CompareFunc - 數據比較回調函數	
	@return	void * - 失敗返回NULL，成功返回找到的節點中的數據指針	
*/
void * HashAVLTree_Find(HASHAVLTREE *pHashAVLTree, void *pData, 
                       HASHFUNC HashFunc, 
                       COMPAREFUNC CompareFunc )
{
    UINT            uIndex;
    AVLTREENODE *   pNode;
    
    if ( pHashAVLTree == NULL || HashFunc == NULL || CompareFunc == NULL )
    {
        return NULL;
    }
    
    uIndex = (*HashFunc)( pData, pHashAVLTree->uBucketCount );
    pNode = (pHashAVLTree->ppBucket)[uIndex];

    return BinTree_Find(pNode, pData, CompareFunc);
}


/**	哈希AVL樹的逐個節點遍歷開始函數

	@param	HASHAVLTREE *pHashAVLTree - 哈希AVL樹指針	
	@return	void - 無	
*/
void HashAVLTree_EnumBegin(HASHAVLTREE *pHashAVLTree)
{
    AVLTREENODE *pCursor;

    pHashAVLTree->uCurBucketNo = 0;
    pCursor = pHashAVLTree->ppBucket[0];
    
    if ( pCursor != NULL )
    {
        while ( pCursor->pLeft != NULL )
        {
            pCursor = pCursor->pLeft;
        }
    }
    pHashAVLTree->pCurEntry = pCursor;
}

/**	哈希AVL樹的逐個節點遍歷函數

	@param	HASHAVLTREE *pHashAVLTree - 哈希AVL樹指針	
	@return	void * - 返回遍歷的節點數據指針，如果遍歷完則返回NULL.	
*/
void *HashAVLTree_EnumNext(HASHAVLTREE *pHashAVLTree)
{
    void *pData;
    AVLTREENODE *pCursor;
    
    pCursor = pHashAVLTree->pCurEntry;
    while ( pCursor == NULL )
    {
        pHashAVLTree->uCurBucketNo += 1;
        if ( pHashAVLTree->uCurBucketNo >= pHashAVLTree->uBucketCount )
        {
            return NULL;
        }
        pCursor = pHashAVLTree->ppBucket[pHashAVLTree->uCurBucketNo];
    }
    
    if ( pCursor == NULL )
    {
        return NULL;
    }

    while ( pCursor->pLeft != NULL )
    {
        pCursor = pCursor->pLeft;
    }

    pData = pCursor->pData;
    
    if ( pCursor->pRight != NULL )
    {
        pCursor = pCursor->pRight;
        while ( pCursor->pLeft != NULL )
        {
            pCursor = pCursor->pLeft;
        }
    }
    else
    {
        AVLTREENODE *pParent = pCursor->pParent;
        while ( pParent != NULL && pParent->pRight == pCursor )
        {
            pCursor = pParent;
            pParent = pParent->pParent;
        }
        pCursor = pParent;
    }
    pHashAVLTree->pCurEntry = pCursor;
    
    return pData;    
}