sh_tree.h

rsa算法打的一个包

// SH_Tree.h: interface for the SH_Tree class.
// 
//////////////////////////////////////////////////////////////////////

#if !defined(AFX_SH_TREE_H__80D8F99D_28F7_4711_839A_A8A4EB304719__INCLUDED_)
#define AFX_SH_TREE_H__80D8F99D_28F7_4711_839A_A8A4EB304719__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

#include "SH_Object.h"

template<class KEY_ARG,class ARG> 
class AFX_EXT_CLASS SH_Tree : public SH_Object  
{
public: 
    typedef struct _SH_TreeNode
    {
        struct _SH_TreeNode * right;
        struct _SH_TreeNode * left;
        int                   balance;
        KEY_ARG               key;
        ARG                   value; 
    }SH_TreeNode;

	SH_Tree();
	virtual ~SH_Tree();

    //Function decl
    BOOL Insert(KEY_ARG key,ARG value);
    VOID Remove(KEY_ARG key,ARG & value);
    BOOL Search(KEY_ARG key,ARG & value);
    BOOL SearchEx(KEY_ARG SearchKey,KEY_ARG & OrigKey,ARG & value);
    int  GetHeight();
    int  NodeCount(SH_TreeNode *pNode);
    int  PreOrder(SH_TreeNode *pNode);
    int  InOrder(SH_TreeNode *pNode);
    int  PostOrder (SH_TreeNode * pNode);
    int  NodeHeight(SH_TreeNode *pNode);
    VOID NodeCheck(SH_TreeNode *pNode);
    VOID RemoveAll();
    int  GetNodeCount();
    int  GetCount();
    BOOL RemoveRoot(KEY_ARG & key,ARG & value);
    
    SH_TreeNode * GetRoot();
    ARG  operator [](KEY_ARG key);

    virtual VOID Destroy(KEY_ARG key,ARG value) {}
    virtual int  KeyCompare(KEY_ARG a,KEY_ARG b);
    virtual BOOL OnTraverse(KEY_ARG key,ARG value){return FALSE;}

protected:
    SH_TreeNode * NodeNew(KEY_ARG key,ARG value);
    SH_TreeNode * NodeRotateLeft(SH_TreeNode *pNode);
    SH_TreeNode * NodeRotateRight(SH_TreeNode *pNode);
    SH_TreeNode * NodeInsert(SH_TreeNode *pNode,KEY_ARG key,ARG value,BOOL *inserted);
    SH_TreeNode * NodeRemove(SH_TreeNode *pNode,KEY_ARG key,ARG & value);
    SH_TreeNode * NodeBalance(SH_TreeNode *pNode);
    SH_TreeNode * NodeRemoveLeftMost(SH_TreeNode  *pNode,SH_TreeNode **leftmost);
    SH_TreeNode * NodeRestoreLeftBalance(SH_TreeNode *pNode,int balance);
    SH_TreeNode * NodeRestoreRightBalance(SH_TreeNode *pNode,int balance);
    SH_TreeNode * NodeSearch (SH_TreeNode * pNode,KEY_ARG key);

private:
    int           m_nCount; 
    SH_TreeNode * m_pRoot;
};
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
template<class KEY_ARG,class ARG>
SH_Tree<KEY_ARG,ARG>::SH_Tree()
{
    m_nCount = 0;
    m_pRoot  = NULL;
}

template<class KEY_ARG,class ARG>
SH_Tree<KEY_ARG,ARG>::~SH_Tree()
{
    RemoveAll();
}


template<class KEY_ARG,class ARG>
int SH_Tree<KEY_ARG,ARG>::KeyCompare(KEY_ARG a,KEY_ARG b)
{
    if(a>b)
        return 1;
    else if(a==b)
        return 0;
    else
        return -1;
}

template<class KEY_ARG,class ARG>
SH_Tree<KEY_ARG,ARG>::SH_TreeNode* SH_Tree<KEY_ARG,ARG>::NodeNew(KEY_ARG key,ARG value)
{
    SH_TreeNode * pNode;

    pNode = new SH_TreeNode;
    ASSERT( pNode != NULL );

    pNode->balance = 0;
    pNode->left    = NULL;
    pNode->right   = NULL;
    pNode->key     = key;
    pNode->value   = value;

    m_nCount++;

    return pNode;
}

template<class KEY_ARG,class ARG>
BOOL SH_Tree<KEY_ARG,ARG>::Insert(KEY_ARG key,ARG value)
{
  BOOL   inserted = FALSE;

  m_pRoot = NodeInsert(m_pRoot,key, value,&inserted);

  return inserted;
}

template<class KEY_ARG,class ARG>
VOID SH_Tree<KEY_ARG,ARG>::Remove(KEY_ARG key,ARG & value)
{
  m_pRoot = NodeRemove (m_pRoot,key,value);
}

template<class KEY_ARG,class ARG>
BOOL SH_Tree<KEY_ARG,ARG>::Search(KEY_ARG key,ARG & value)
{
    SH_TreeNode *pNode;

    value = (ARG)0;

    pNode = NodeSearch (m_pRoot,key);

    if(pNode) 
    {
        value = pNode->value;
        return TRUE;
    }
    return FALSE;
}


template<class KEY_ARG,class ARG>
BOOL SH_Tree<KEY_ARG,ARG>::SearchEx(KEY_ARG SearchKey,KEY_ARG & OrigKey,ARG & value)
{
    SH_TreeNode *pNode;

    pNode = NodeSearch(m_pRoot,SearchKey);

    if (pNode)
    {
        if (orig_key)
            *orig_key = pNode->key;
        if (value)
            *value = pNode->value;
        return TRUE;
    }
    else
        return FALSE;
}


template<class KEY_ARG,class ARG>
int SH_Tree<KEY_ARG,ARG>::GetHeight()
{
    if (m_pRoot)
        return NodeHeight(m_pRoot);
    else
        return 0;
}

template<class KEY_ARG,class ARG>
SH_Tree<KEY_ARG,ARG>::SH_TreeNode* SH_Tree<KEY_ARG,ARG>::NodeInsert(SH_TreeNode *pNode,KEY_ARG key,ARG value,BOOL *inserted)
{
    int  balance;
    int  cmp;

    if (!pNode)
    {
        *inserted = TRUE;
        return NodeNew(key, value);
    }

    cmp = KeyCompare(key,pNode->key);
    if (cmp == 0)
    {
        *inserted = FALSE;
        pNode->value = value;
        return pNode;
    }
    if (cmp < 0)
    {
        if (pNode->left)
        {
            balance = pNode->left->balance;
            pNode->left = NodeInsert(pNode->left,key, value,inserted);

            if ((balance != pNode->left->balance) && pNode->left->balance)
                pNode->balance -= 1;
        }
        else
        {
            *inserted = TRUE;
            pNode->left = NodeNew(key, value);
            pNode->balance -= 1;
        }
    }
    else if (cmp > 0)
    {
        if (pNode->right)
        {
            balance = pNode->right->balance;
            pNode->right = NodeInsert(pNode->right,key, value,inserted);

            if ((balance != pNode->right->balance) && pNode->right->balance)
                pNode->balance += 1;
        }
        else
        {
            *inserted = TRUE;
            pNode->right = NodeNew(key, value);
            pNode->balance += 1;
        }
    }

    if (*inserted)
    {
        if ((pNode->balance < -1) || (pNode->balance > 1))
            pNode = NodeBalance (pNode);
    }

    return pNode;
}

template<class KEY_ARG,class ARG>
SH_Tree<KEY_ARG,ARG>::SH_TreeNode* SH_Tree<KEY_ARG,ARG>::NodeRemove(SH_TreeNode *pNode,KEY_ARG key,ARG & value)
{
    SH_TreeNode * pNewRoot;
    int balance;
    int cmp;

    if (!pNode)
        return NULL;

    cmp = KeyCompare(key, pNode->key);
    if (cmp == 0)
    {
        SH_TreeNode *garbage = NULL;

        garbage = pNode;

        value = garbage->value;

        if (!pNode->right)
        {
            pNode = pNode->left;
        }
        else
        {
            balance = pNode->right->balance;
            pNode->right = NodeRemoveLeftMost (pNode->right, &pNewRoot);
            pNewRoot->left = pNode->left;
            pNewRoot->right = pNode->right;
            pNewRoot->balance = pNode->balance;
            pNode = NodeRestoreRightBalance (pNewRoot, balance);
        }
        Destroy(garbage->key,garbage->value);
        SAFE_DELETE(garbage);

        m_nCount--;
    }
    else if (cmp < 0)
    {
        if (pNode->left)
        {
            balance = pNode->left->balance;
            pNode->left = NodeRemove (pNode->left,key,value);
            pNode = NodeRestoreLeftBalance(pNode, balance);
        }
    }
    else if (cmp > 0)
    {
        if (pNode->right)
        {
            balance = pNode->right->balance;
            pNode->right = NodeRemove(pNode->right,key,value);
            pNode = NodeRestoreRightBalance(pNode, balance);
        }
    }

    return pNode;
}

template<class KEY_ARG,class ARG>
SH_Tree<KEY_ARG,ARG>::SH_TreeNode * SH_Tree<KEY_ARG,ARG>::NodeBalance(SH_TreeNode *pNode)
{
    if (pNode->balance < -1)
    {
        if (pNode->left->balance > 0)
            pNode->left = NodeRotateLeft (pNode->left);
        pNode = NodeRotateRight (pNode);
    }
    else if (pNode->balance > 1)
    {
        if (pNode->right->balance < 0)
            pNode->right = NodeRotateRight (pNode->right);
        pNode = NodeRotateLeft (pNode);
    }

    return pNode;
}

template<class KEY_ARG,class ARG>
SH_Tree<KEY_ARG,ARG>::SH_TreeNode * SH_Tree<KEY_ARG,ARG>::NodeRemoveLeftMost(SH_TreeNode  *pNode,SH_TreeNode **leftmost)
{
    int balance;

    if (!pNode->left)
    {
        *leftmost = pNode;
        return pNode->right;
    }

    balance = pNode->left->balance;
    pNode->left = NodeRemoveLeftMost (pNode->left, leftmost);
    
    return NodeRestoreLeftBalance (pNode, balance);
}

template<class KEY_ARG,class ARG>
SH_Tree<KEY_ARG,ARG>::SH_TreeNode* SH_Tree<KEY_ARG,ARG>::NodeRestoreLeftBalance(SH_TreeNode *pNode,int balance)
{
    if (!pNode->left)
        pNode->balance += 1;
    else if ((pNode->left->balance != balance) &&
       (pNode->left->balance == 0))
    pNode->balance += 1;

    if (pNode->balance > 1)
        return NodeBalance (pNode);
    return pNode;
}

template<class KEY_ARG,class ARG>
SH_Tree<KEY_ARG,ARG>::SH_TreeNode* SH_Tree<KEY_ARG,ARG>::NodeRestoreRightBalance(SH_TreeNode *pNode,int balance)
{
    if (!pNode->right)
        pNode->balance -= 1;
    else if ((pNode->right->balance != balance) &&
        (pNode->right->balance == 0))
    pNode->balance -= 1;

    if (pNode->balance < -1)
        return NodeBalance (pNode);
    return pNode;
}

template<class KEY_ARG,class ARG>
SH_Tree<KEY_ARG,ARG>::SH_TreeNode * SH_Tree<KEY_ARG,ARG>::NodeSearch (SH_TreeNode * pNode,KEY_ARG key)
{
    int cmp;

    if (!pNode)
        return NULL;

    cmp = KeyCompare(key,pNode->key);
    if (cmp == 0)
        return pNode;

    if (cmp < 0)
    {
        if (pNode->left)
            return NodeSearch(pNode->left,key);
    }
    else if (cmp > 0)
    {
        if (pNode->right)
            return NodeSearch (pNode->right,key);
    }
    return NULL;
}

template<class KEY_ARG,class ARG>
int SH_Tree<KEY_ARG,ARG>::NodeCount(SH_TreeNode *pNode)
{
    int count;

    count = 1;

    if (pNode->left)
        count += NodeCount(pNode->left);
    if (pNode->right)
        count += NodeCount (pNode->right);
    
    return count;
}

template<class KEY_ARG,class ARG>
int SH_Tree<KEY_ARG,ARG>::PreOrder(SH_TreeNode *pNode)
{
    if (OnTraverse(pNode->key, pNode->value))
        return TRUE;
    
    if (pNode->left)
    {
        if(PreOrder (pNode->left))
            return TRUE;
    }
    if (pNode->right)
    {
        if(PreOrder(pNode->right))
            return TRUE;
    }
    return FALSE;
}

template<class KEY_ARG,class ARG>
int SH_Tree<KEY_ARG,ARG>::InOrder(SH_TreeNode *pNode)
{
    if (pNode->left)
    {
        if (g_tree_pNode_in_order (pNode->left))
            return TRUE;
    }
    
    if (OnTraverse(pNode->key, pNode->value))
        return TRUE;
    
    if (pNode->right)
    {
        if (InOrder (pNode->right))
            return TRUE;
    }

    return FALSE;
}

template<class KEY_ARG,class ARG>
int SH_Tree<KEY_ARG,ARG>::PostOrder (SH_TreeNode * pNode)
{
    if (pNode->left)
    {
        if (g_tree_pNode_post_order (pNode->left, traverse_func, data))
            return TRUE;
    }
    if (pNode->right)
    {
        if (g_tree_pNode_post_order (pNode->right, traverse_func, data))
            return TRUE;
    }
    if (OnTraverse(pNode->key, pNode->value))
        return TRUE;
    return FALSE;
}

template<class KEY_ARG,class ARG>
int SH_Tree<KEY_ARG,ARG>::NodeHeight(SH_TreeNode *pNode)
{
    int left;
    int right;

    if (pNode)
    {
        left = 0;
        right = 0;

        if (pNode->left)
            left = NodeHeight(pNode->left);

        if (pNode->right)
            right = NodeHeight(pNode->right);

        return (left>right)?(left+1):(right+1);
    }

    return 0;
}

template<class KEY_ARG,class ARG>
SH_Tree<KEY_ARG,ARG>::SH_TreeNode * SH_Tree<KEY_ARG,ARG>::NodeRotateLeft(SH_TreeNode *pNode)
{
    SH_TreeNode *right;
    int a_bal;
    int b_bal;

    right = pNode->right;

    pNode->right = right->left;
    right->left = pNode;

    a_bal = pNode->balance;
    b_bal = right->balance;

    if (b_bal <= 0)
    {
        if (a_bal >= 1)
            right->balance = b_bal - 1;
        else
            right->balance = a_bal + b_bal - 2;
        pNode->balance = a_bal - 1;
    }
    else
    {
        if (a_bal <= b_bal)
            right->balance = a_bal - 2;
        else
            right->balance = b_bal - 1;
        pNode->balance = a_bal - b_bal - 1;
    }
    return right;
}

template<class KEY_ARG,class ARG>
SH_Tree<KEY_ARG,ARG>::SH_TreeNode* SH_Tree<KEY_ARG,ARG>::NodeRotateRight(SH_TreeNode *pNode)
{
    SH_TreeNode *left;
    int a_bal;
    int b_bal;

    left = pNode->left;

    pNode->left = left->right;
    left->right = pNode;

    a_bal = pNode->balance;
    b_bal = left->balance;

    if (b_bal <= 0)
    {
        if (b_bal > a_bal)
            left->balance = b_bal + 1;
        else
            left->balance = a_bal + 2;
        pNode->balance = a_bal - b_bal + 1;
    }
    else
    {
        if (a_bal <= -1)
            left->balance = b_bal + 1;
        else
            left->balance = a_bal + b_bal + 2;
        pNode->balance = a_bal + 1;
    }
    return left;
}

template<class KEY_ARG,class ARG>
VOID SH_Tree<KEY_ARG,ARG>::NodeCheck(SH_TreeNode *pNode)
{
    int left;
    int right;
    int balance;

    if (pNode)
    {
        left_height = 0;
        right_height = 0;

        if (pNode->left)
            left  = NodeHeight (pNode->left);
        if (pNode->right)
            right = NodeHeight (pNode->right);

        balance = right - left;
        if (balance != pNode->balance)
            TRACE("Tree Node Check Failed:%d(%d)\n",balance, pNode->balance);

        if (pNode->left)
            NodeCheck (pNode->left);
        if (pNode->right)
            NodeCheck (pNode->right);
    }
}

template<class KEY_ARG,class ARG>
SH_Tree<KEY_ARG,ARG>::SH_TreeNode * SH_Tree<KEY_ARG,ARG>::GetRoot()
{
    return m_pRoot;
}


template<class KEY_ARG,class ARG>
VOID SH_Tree<KEY_ARG,ARG>::RemoveAll()
{
    ARG     value;
    KEY_ARG key;

    while(RemoveRoot(key,value))
    {
        ;
    }
}

template<class KEY_ARG,class ARG>
BOOL SH_Tree<KEY_ARG,ARG>::RemoveRoot(KEY_ARG & key,ARG & value)
{
    if(!m_pRoot)
        return FALSE;

    m_pRoot = NodeRemove(m_pRoot,m_pRoot->key,value);

    return TRUE;
}

template<class KEY_ARG,class ARG>
ARG SH_Tree<KEY_ARG,ARG>::operator [](KEY_ARG key)
{
    ARG value = (ARG)0;

    if(!Search(key,value))
        ASSERT(FALSE);

    return value;
}

template<class KEY_ARG,class ARG>
int SH_Tree<KEY_ARG,ARG>::GetNodeCount()
{
    int nCount = NodeCount(m_pRoot);

    return nCount;
}

template<class KEY_ARG,class ARG>
int SH_Tree<KEY_ARG,ARG>::GetCount()
{
    return m_nCount;
}
#endif // !defined(AFX_SH_TREE_H__80D8F99D_28F7_4711_839A_A8A4EB304719__INCLUDED_)