// FileName: TreeInfo.cpp
// Author:   Anli.wei
// Date:     2005-2-22
// Comment:  定義樹的屬性結構，并實現屬性結構操作的封裝，使用時:
//           1. 應派生CTreeNode類，添加自己需要的屬性。
//           2. 派生CTreeInfo類，重新實現MallocNode和ZeroNode兩個函數
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "TreeInfo.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CTreeInfo::CTreeInfo()
{
    m_pRoot = NULL;
}

CTreeInfo::~CTreeInfo()
{
    if(m_pRoot != NULL)
    {
        RemoveAll();
    }
}

// 在進行操作前，必須首先調用此函數(形成虛擬的根節點)，否則其余的操作不會有效。
// 成功，返回TRUE；失敗，返回FALSE。
BOOL CTreeInfo::InitRoot()  
{
    if(m_pRoot == NULL)
    {
        m_pRoot = MallocNode();
        if(m_pRoot == NULL)
        {
            return FALSE;
        }
        ZeroNode(m_pRoot);
    }
   
    return TRUE;
}

// 獲取當前節點的父節點
// pcNode, 當前節點
// 成功 非NULL， 失敗或沒有 NULL
PTREENODE CTreeInfo::GetParent( PCTREENODE pcNode )const
{
    if( pcNode != NULL )
    {
        return pcNode->pParent;
    }
    else
    {
        return NULL;
    }
}

void CTreeInfo::SetParent( PTREENODE pCur, PCTREENODE pParent) const
{
    _ASSERTE( pCur != NULL);
    
    pCur->pParent = (PTREENODE)pParent;
}

// 獲取當前節點的子節點
// pcNode, 給定的節點; nIndex, 給定的節點的第幾個子節點，缺省為第一個(從0計起)
// 成功 非NULL; 失敗 NULL
PTREENODE CTreeInfo::GetChild( PCTREENODE pcNode, int nIdx /* = 0 */ ) const
{
    _ASSERTE( pcNode != NULL );
	_ASSERTE( nIdx >= 0 );

    if( nIdx >= GetChildCount(pcNode) )
    {
        // 子節點為空的情況已經考慮到，以下處理時不必再考慮
        return NULL;
    }

	PTREENODE pCur = pcNode->pChild;
    // 此時pCur肯定不為NULL,所以不必再次判斷
    for( int i = 0; i < nIdx; ++i )
    {
        pCur = pCur->pNext;
    }

    return pCur;
}

// 置當前節點的子節點
void CTreeInfo::SetChild( PTREENODE pCur, PCTREENODE pChild ) const
{
    _ASSERTE( pCur != NULL);

    pCur->pChild = (PTREENODE)pChild;
}

// 獲取當前節點子節點的數量(不包含孫子節點)
// pcNode, 給定節點
// 返回給定節點的子節點個數 >= 0
int CTreeInfo::GetChildCount( PCTREENODE pcNode ) const
{
    _ASSERTE(pcNode != NULL);

    int nCount = 0;
    for(pcNode = pcNode->pChild; pcNode != NULL; pcNode = pcNode->pNext)
    {
        nCount++;
    }  

    return nCount;
}

// 獲取當前節點的上一個兄弟節點
// 成功 非NULL; 失敗或無 NULL
PTREENODE CTreeInfo::GetPrev( PCTREENODE pcNode )const 
{
    if(pcNode != NULL)
    {
        return pcNode->pPrev;
    }
    else
    {
        return NULL;
    }
}

// 置當前節點的上一個兄弟節點
void CTreeInfo::SetPrev( PTREENODE pCur, PCTREENODE pcPrev ) const
{
    _ASSERTE( pCur != NULL);

    pCur->pPrev = (PTREENODE)pcPrev;
}

// 獲取當前節點的下一個兄弟節點
// 成功 非NULL; 失敗或無 NULL
PTREENODE CTreeInfo::GetNext( PCTREENODE pcNode ) const
{
    if(pcNode != NULL)
    {
        return pcNode->pNext;
    }
    else
    {
        return NULL;
    }
}

// 置當前節點的下一個兄弟節點
void CTreeInfo::SetNext( PTREENODE pCur, PCTREENODE pcNext) const
{
    _ASSERTE( pCur != NULL);

    pCur->pNext = (PTREENODE)pcNext;
}

// 為當前節點添加子節點   
// bLast 如果父節點已經有子節點，用此來表示該子節點是作為父節點的最后一個
// 子節點(TRUE)，還是作為第一個子節點(FALSE)，缺省為TRUE。 
// 成功  TRUE； 失敗 FALSE
BOOL CTreeInfo::AddChild(PTREENODE pParent, PTREENODE pChild, BOOL bLast /* = TRUE */) const
{
    _ASSERTE(pParent != NULL);
    _ASSERTE(pChild != NULL);
    
    // 將子節點的連接節點初始化
    pChild->pParent = pParent;
        
    // 當前節點(pParent)還沒有子節點，此時為它添加第一個子節點
    if(pParent->pChild == NULL)
    {
        pParent->pChild = pChild;
      
        return TRUE;
    }

    // 當前節點(pParent)已經有子節點，此時以標志bLast來判斷是將子節點
    // (pChild)作為pParent的最后一個子節點，還是第一個子節點.
    if(bLast)
    {
        PTREENODE pLast = pParent->pChild;
        while( pLast->pNext != NULL )
		{
			pLast = pLast->pNext;
		}

		pLast->pNext    = pChild;
        pChild->pPrev   = pLast;
    }
    else
    {
        PTREENODE pFirst = pParent->pChild;
        pParent->pChild  = pChild;
        pChild->pNext    = pFirst;
    }

    return TRUE;
}

// 以當前選中節點為基準插入兄弟節點
// pBase:基準節點(在菜單中已經存在的);pBrother:被插入的節點;
// bBefore:被插入的節點的位置(基準節點的前面:TRUE或后面:FALSE)
// 返回：成功 TRUE；失敗 FALSE
BOOL CTreeInfo::InsertInBrothers(PTREENODE pBase, PTREENODE pBrother, BOOL bBefore /* = TRUE */)
{
    _ASSERTE(pBase != NULL);
    _ASSERTE(pBrother != NULL);
    
    // 將子節點的連接節點初始化
    pBrother->pParent = pBase->pParent;
    pBrother->pNext   = NULL;
    pBrother->pPrev   = NULL;

    if(bBefore)
    {
        PTREENODE pOldBefore = pBase->pPrev;
        if(pOldBefore != NULL)
        {
            pOldBefore->pNext = pBrother;
        }
        else
        {
            pBase->pParent->pChild = pBrother;
        }
        pBrother->pPrev = pOldBefore;
        pBrother->pNext = pBase;
        pBase->pPrev    = pBrother;
    }
    else
    {
        PTREENODE pOldAfter = pBase->pNext;
        pBase->pNext        = pBrother;
        pBrother->pPrev     = pBase;
        pBrother->pNext     = pOldAfter;

        if(pOldAfter != NULL)
        {
            pOldAfter->pPrev = pBrother;
        }
    }

    return TRUE;
}

// 在兄弟節點中移動當前節點(改變當前節點在兄弟節點中的順序)
// 當前選中節點,// 移動方向  TRUE 向下；FALSE 向上
// TRUE 成功；FALSE 失敗
BOOL CTreeInfo::MoveInBrothers(PTREENODE pNode, BOOL bDown /* = TRUE */)
{
    _ASSERTE(pNode != NULL);

    PTREENODE pPrev = NULL;
    PTREENODE pNext = NULL;
    if(bDown)
    {
        if(pNode->pNext == NULL)
        {
            // 當前節點無下一個兄弟節點
            return FALSE;
        }

        // 當前節點的上一個兄弟節點（可能為NULL）
        pPrev = pNode->pPrev;
        // 當前節點的下一個兄弟節點（可能為NULL）
        pNext = pNode->pNext;

        pNode->pPrev = pNext;
        pNode->pNext = pNext->pNext;

        if(pNext->pNext != NULL)
        {
            pNext->pNext->pPrev = pNode;
        }

        pNext->pNext  = pNode;
        pNext->pPrev  = pPrev;

        if(pPrev == NULL)
        {
            pNode->pParent->pChild = pNext;      
        }
        else
        {
            pPrev->pNext = pNext;
        }
    }
    else
    {
        if(pNode->pPrev == NULL)
        {
            // 當前節點無上一個兄弟節點
            return FALSE;
        }

        pPrev = pNode->pPrev;
        pNext = pNode->pNext;

        // 當前節點的上一個兄弟節點（可能為NULL）
        pNode->pPrev = pPrev->pPrev;
        // 當前節點的下一個兄弟節點（可能為NULL）
        pNode->pNext = pPrev;
                
        if(pNext != NULL)
        {
            pNext->pPrev = pPrev;
        }