/**
 * Copyright (C) 2014-2050 SOUI团队
 * All rights reserved.
 *
 * @file       stree.hpp
 * @brief      树模板--提供对一般的数据类型实现树结构
 * @version    v1.0
 * @author     soui
 * @date       2014-07-13
 *
 * Describe    此类是下拉窗口的父类 只需要派生该类即可
 *
 *              version: 1.0　2003-10-24 实现基本功能
 *                       2.0  2004-12-29 增加两个遍历接口，修改内存释放部分可能存在的bug
 *                       2.1  2006-10-17 为节点增加一个hChildLast数据,以加快在数据插入时的速度
 *                       2.2  2008-10-16 修改一个遍历接口的问题
 *                       2.3  2011-10-17 将数据释放的接口从回调函数改成虚函数
 */
#if !defined(AFX_STREE_H__D2332B4E_2C7E_4357_BE22_EC55BF496C1C__INCLUDED_)
#define AFX_STREE_H__D2332B4E_2C7E_4357_BE22_EC55BF496C1C__INCLUDED_

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

#ifndef SASSERT
#define SASSERT(x)
#endif

// typedef ULONG_PTR HSTREEITEM;
#define STVN_ROOT  ((HSTREENODE)(ULONG_PTR)0xFFFF0000) //=STVN_ROOT
#define STVN_FIRST ((HSTREENODE)(ULONG_PTR)0xFFFF0001) //=STVN_FIRST
#define STVN_LAST  ((HSTREENODE)(ULONG_PTR)0xFFFF0002) //=STVN_LAST
#define STVL_ROOT  ((PSTREELINK)(ULONG_PTR)0xFFFF0000)

/**
 * @class      CSTree 模板类
 * @brief      CSTree 模板类
 *
 * Describe    CSTree 模板类
 */
template <class T>
class CSTree {
    /**
     * @class      _STREENODE
     * @brief      节点结构体
     *
     * Describe    节点结构体
     */
    typedef struct _STREENODE
    {
        struct _STREENODE *hParent;      /**< 父节点 */
        struct _STREENODE *hChildFirst;  /**< 第一个子节点 */
        struct _STREENODE *hChildLast;   /**< 最后一个子节点 */
        struct _STREENODE *hPrevSibling; /**< 兄节点 */
        struct _STREENODE *hNextSibling; /**< 弟节点 */
        T data;                          /**< 数据 */
    } STREENODE, *HSTREENODE;

    /**
     * @class      _STREELINK
     * @brief      树结点的链接
     *
     * Describe    此结构体用于连接树节点
     */
    typedef struct _STREELINK
    {
        HSTREENODE hParent;      /**< 父节点 */
        HSTREENODE hChildFirst;  /**< 第一个子节点 */
        HSTREENODE hChildLast;   /**< 最后一个子节点 */
        HSTREENODE hPrevSibling; /**< 兄节点 */
        HSTREENODE hNextSibling; /**< 弟节点 */
    } STREELINK, *PSTREELINK;

    /**
     * 回调函数
     * @brief    下拉窗口鼠标左键按下事件
     * @param    T *:当前遍历到的结点的数据
     * @param    LPARAM:回调时使用的参数
     * @return   FALSE－继续，TRUE－中断遍历
     *
     * Describe  遍历一个树结点的回调函数原型，
     */
    typedef BOOL (*CBTRAVERSING)(T *, LPARAM);

  public:
    /**
     * CSTree::CSTree
     * @brief    构造函数
     *
     * Describe  构造函数
     */
    CSTree()
    {
        m_hRootFirst = NULL;
        m_hRootLast = NULL;
    }

    /**
     * CSTree::~CSTree
     * @brief    析构函数
     *
     * Describe  析构函数
     */
    virtual ~CSTree()
    {
        DeleteAllItems();
    }

    /**
     * CSTree::DeleteAllItems
     * @brief    删除所有节点
     *
     * Describe  删除所有节点
     */
    void DeleteAllItems()
    {
        if (m_hRootFirst)
        {
            FreeNode(STVN_ROOT);
            m_hRootFirst = NULL;
            m_hRootLast = NULL;
        }
    }

    /**
     * CSTree::GetNextSiblingItem
     * @brief    获取下一个兄弟
     * @param    HSTREEITEM hItem  -- 节点
     * @return   返回HSTREEITEM
     *
     * Describe  获取下一个兄弟
     */
    static HSTREEITEM GetNextSiblingItem(HSTREEITEM hItem)
    {
        PSTREELINK pLink = (PSTREELINK)hItem;
        SASSERT(pLink && pLink != STVL_ROOT);
        return (HSTREEITEM)pLink->hNextSibling;
    }

    /**
     * CSTree::GetPrevSiblingItem
     * @brief    获取上一个兄弟
     * @param    HSTREEITEM hItem  -- 节点
     * @return   返回HSTREEITEM
     *
     * Describe  获取上一个兄弟
     */
    static HSTREEITEM GetPrevSiblingItem(HSTREEITEM hItem)
    {
        PSTREELINK pLink = (PSTREELINK)hItem;
        SASSERT(pLink && pLink != STVL_ROOT);
        return (HSTREEITEM)pLink->hPrevSibling;
    }

    /**
     * CSTree::GetParentItem
     * @brief    获取父结点
     * @param    HSTREEITEM hItem  -- 节点
     * @return   返回HSTREEITEM
     *
     * Describe  获取父结点
     */
    static HSTREEITEM GetParentItem(HSTREEITEM hItem)
    {
        PSTREELINK pLink = (PSTREELINK)hItem;
        SASSERT(pLink && pLink != STVL_ROOT);
        return (HSTREEITEM)pLink->hParent;
    }

    /**
     * CSTree::GetItemLevel
     * @brief    获取结点层数
     * @param    HSTREEITEM hItem  -- 节点
     * @return   返回int
     *
     * Describe  获取结点层数
     */
    static int GetItemLevel(HSTREEITEM hItem)
    {
        int nRet = -1;
        if (hItem == STVI_ROOT)
            hItem = NULL;
        while (hItem)
        {
            nRet++;
            hItem = GetParentItem(hItem);
        }
        return nRet;
    }

    /**
     * GetRootItem
     * @brief    获取指定节点的根节点
     * @param    HSTREEITEM hItem -- 当前节点
     * @return   HSTREEITEM 根节点
     *
     * Describe
     */
    static HSTREEITEM GetRootItem(HSTREEITEM hItem)
    {
        HSTREEITEM hParent = hItem;
        while (GetParentItem(hParent))
        {
            hParent = GetParentItem(hParent);
        }
        return hParent;
    }

    /**
     * CSTree::GetChildItem
     * @brief    获取第一个子结点
     * @param    HSTREEITEM hItem  -- 节点
     * @param    BOOL bFirst       -- 是否第一个节点
     * @return   返回HSTREEITEM
     *
     * Describe  获取第一个子结点
     */
    HSTREEITEM GetChildItem(HSTREEITEM hItem, BOOL bFirst = TRUE) const
    {
        HSTREENODE hsNode = (HSTREENODE)hItem;
        SASSERT(hsNode);
        if (hsNode == STVN_ROOT)
        {
            if (bFirst)
                return (HSTREEITEM)m_hRootFirst;
            else
                return (HSTREEITEM)m_hRootLast;
        }
        else
        {
            if (bFirst)
                return (HSTREEITEM)hsNode->hChildFirst;
            else
                return (HSTREEITEM)hsNode->hChildLast;
        }
    }

    /**
     * CSTree::GetChildrenCount
     * @brief    获取子结点数量
     * @param    HSTREEITEM hItem  -- 节点
     * @return   返回int
     *
     * Describe  获取子结点数量
     */
    int GetChildrenCount(HSTREEITEM hItem) const
    {
        int nRet = 0;
        HSTREEITEM hChild = GetChildItem(hItem);
        while (hChild)
        {
            nRet++;
            hChild = GetNextSiblingItem(hChild);
        }
        return nRet;
    }

    /**
     * CSTree::DeleteItem
     * @brief    删除一个节点，可以被派生类重载
     * @param    HSTREEITEM hItem  -- 节点
     *
     * Describe  删除一个节点，可以被派生类重载
     */
    virtual void DeleteItem(HSTREEITEM hItem)
    {
        HSTREENODE hsNode = (HSTREENODE)hItem;
        SASSERT(hsNode);
        if (hsNode == STVN_ROOT)
        {
            FreeNode(STVN_ROOT);
            m_hRootFirst = NULL;
            m_hRootLast = NULL;
            return;
        }
        STREENODE nodeCopy = *hsNode;
        BOOL bRootFirst = hsNode == m_hRootFirst;
        BOOL bRootLast = hsNode == m_hRootLast;
        FreeNode(hsNode);

        if (nodeCopy.hPrevSibling) // has prevsibling
            nodeCopy.hPrevSibling->hNextSibling = nodeCopy.hNextSibling;
        else if (nodeCopy.hParent) // parent's first child
            nodeCopy.hParent->hChildFirst = nodeCopy.hNextSibling;
        if (nodeCopy.hNextSibling) // update next sibling's previous sibling
            nodeCopy.hNextSibling->hPrevSibling = nodeCopy.hPrevSibling;
        else if (nodeCopy.hParent) // parent's last child
            nodeCopy.hParent->hChildLast = nodeCopy.hPrevSibling;
        // update root item
        if (bRootFirst)
            m_hRootFirst = nodeCopy.hNextSibling;
        if (bRootLast)
            m_hRootLast = nodeCopy.hPrevSibling;
    }

    /**
     * CSTree::DeleteItemEx
     * @brief    删除一个结点分枝，如果该结点的父结点没有其它子节点则一起删除
     * @param    HSTREEITEM hItem  -- 节点
     * @return   返回BOOL
     *
     * Describe  删除一个结点分枝，如果该结点的父结点没有其它子节点则一起删除
     */
    BOOL DeleteItemEx(HSTREEITEM hItem)
    {
        if (GetChildItem(hItem))
            return FALSE;
        while (hItem && !GetChildItem(hItem))
        {
            HSTREEITEM hParent = GetParentItem(hItem);
            DeleteItem(hItem);
            hItem = hParent;
        }
        return TRUE;
    }

    /**
     * CSTree::GetItem
     * @brief    获取结点中保存的数据
     * @param    HSTREEITEM hItem  -- 节点
     * @return   返回T
     *
     * Describe  获取结点中保存的数据
     */
    static T GetItem(HSTREEITEM hItem)
    {
        SASSERT(hItem != STVI_ROOT);
        HSTREENODE hsNode = (HSTREENODE)hItem;
        SASSERT(hsNode);
        return hsNode->data;
    }

    /**
     * CSTree::GetItem
     * @brief    获取结点中保存的数据
     * @param    HSTREEITEM hItem  -- 节点
     * @return   返回T
     *
     * Describe  获取结点中保存的数据
     */
    static T &GetItemRef(HSTREEITEM hItem)
    {
        SASSERT(hItem != STVI_ROOT);
        HSTREENODE hsNode = (HSTREENODE)hItem;
        SASSERT(hsNode);
        return hsNode->data;
    }

    /**
     * CSTree::GetItemPt
     * @brief    获取结点中保存的数据
     * @param    HSTREEITEM hItem  -- 节点
     * @return   返回T*
     *
     * Describe  获取结点中保存的数据
     */
    static T *GetItemPt(HSTREEITEM hItem)
    {
        SASSERT(hItem != STVI_ROOT);
        HSTREENODE hsNode = (HSTREENODE)hItem;
        SASSERT(hsNode);
        return &hsNode->data;
    }

    /**
     * CSTree::InsertItem
     * @brief    插入一个新结点
     * @param    const T &data -- 结点数据
     * @param    HSTREEITEM hParent -- 新结点的父结点
     * @param    HSTREEITEM hInsertAfter -- 新结点的前一个兄弟结点
     * @return   返回HSTREEITEM 新结点的指针
     *
     * Describe  获取结点中保存的数据
     */
    HSTREEITEM InsertItem(const T &data, HSTREEITEM hParent = STVI_ROOT, HSTREEITEM hInsertAfter = STVI_LAST)
    {
        HSTREENODE hParentNode = (HSTREENODE)hParent;
        HSTREENODE hInsertAfterNode = (HSTREENODE)hInsertAfter;
        if (hParentNode == STVN_ROOT)
            hParentNode = NULL;
        SASSERT(hInsertAfter);
        if (hInsertAfterNode != STVN_FIRST && hInsertAfterNode != STVN_LAST)
        {
            if (hInsertAfterNode->hParent != hParentNode)
                return NULL;
            if (hInsertAfterNode->hNextSibling == NULL)
                hInsertAfterNode = STVN_LAST;
        }

        HSTREENODE hInserted = new STREENODE;
        hInserted->data = data;
        hInserted->hParent = hParentNode;
        hInserted->hChildFirst = NULL;
        hInserted->hChildLast = NULL;

        if (hInsertAfterNode == STVN_FIRST)
        {
            hInserted->hPrevSibling = NULL;
            if (hParentNode == NULL) // root
            {
                hInserted->hNextSibling = m_hRootFirst;
                if (m_hRootFirst)
                    m_hRootFirst->hPrevSibling = hInserted;
                m_hRootFirst = hInserted;
                if (m_hRootLast == NULL)
                    m_hRootLast = hInserted;
            }
            else // has parent
            {
                hInserted->hNextSibling = hParentNode->hChildFirst;
                if (hInserted->hNextSibling)
                {
                    hInserted->hNextSibling->hPrevSibling = hInserted;
                    hParentNode->hChildFirst = hInserted;
                }
                else
                {
                    hParentNode->hChildLast = hParentNode->hChildFirst = hInserted;
                }
            }
        }
        else if (hInsertAfterNode == STVN_LAST)
        {
            hInserted->hNextSibling = NULL;
            if (hParentNode == NULL) // root
            {
                hInserted->hPrevSibling = m_hRootLast;
                if (m_hRootLast)
                    m_hRootLast->hNextSibling = hInserted;
                m_hRootLast = hInserted;
                if (!m_hRootFirst)
                    m_hRootFirst = hInserted;
            }
            else
            {
                hInserted->hPrevSibling = hParentNode->hChildLast;
                if (hParentNode->hChildLast)
                {
                    hInserted->hPrevSibling->hNextSibling = hInserted;
                    hParentNode->hChildLast = hInserted;
                }
                else
                {
                    hParentNode->hChildLast = hParentNode->hChildFirst = hInserted;
                }
            }
        }
        else
        {
            HSTREENODE hNextSibling = hInsertAfterNode->hNextSibling;
            hInserted->hPrevSibling = hInsertAfterNode;
            hInserted->hNextSibling = hNextSibling;
            hNextSibling->hPrevSibling = hInsertAfterNode->hNextSibling = hInserted;
        }
        return (HSTREEITEM)hInserted;
    }

    /**
     * CSTree::TraversingRecursion
     * @brief    采用递归方式遍历一个树结点
     * @param    HSTREEITEM hItem -- 起始结点
     * @param    CBTRAVERSING funTraversing -- 执行实际操作的回调函数
     * @param    LPARAM lParam -- 回调时使用的参数
     * @return   返回HSTREEITEM
     *
     * Describe  采用递归方式遍历一个树结点
     */
    HSTREEITEM TraversingRecursion(HSTREEITEM hItem, CBTRAVERSING funTraversing, LPARAM lParam)
    {
        SASSERT(hItem);
        if (hItem != STVI_ROOT)
        {
            if (funTraversing(GetItemPt(hItem), lParam))
                return hItem;
        }
        HSTREEITEM hChild = GetChildItem(hItem);
        while (hChild)
        {
            HSTREEITEM hTmp = GetChildItem(hChild);
            if (hTmp)
            {
                HSTREEITEM hRet = TraversingRecursion(hTmp, funTraversing, lParam);
                if (hRet)
                    return hRet;
            }
            else
            {
                if (funTraversing(GetItemPt(hChild), lParam))
                    return hChild;
            }
            hChild = GetNextSiblingItem(hChild);
        }
        return NULL;
    }

    /**
     * CSTree::TraversingSequence
     * @brief    按顺序方式从指定结点开始查找后面的结点，包括自己的子节点及自己向下的兄弟结点
     * @param    HSTREEITEM hItem -- 起始结点
     * @param    CBTRAVERSING funTraversing -- 执行实际操作的回调函数
     * @param    LPARAM lParam -- 回调时使用的参数
     * @return   返回HSTREEITEM
     *
     * Describe  按顺序方式从指定结点开始查找后面的结点，包括自己的子节点及自己向下的兄弟结点
     */
    HSTREEITEM TraversingSequence(HSTREEITEM hItem, CBTRAVERSING funTraversing, LPARAM lParam)
    {
        if (!m_hRootFirst)
            return NULL;
        if (hItem != STVI_ROOT)
        {
            if (funTraversing(GetItemPt(hItem), lParam))
                return hItem;
        }
        HSTREEITEM hNext = GetNextItem(hItem);
        while (hNext)
        {
            if (funTraversing(GetItemPt(hNext), lParam))
                return hNext;
            hNext = GetNextItem(hNext);
        }
        return NULL;
    }

    /**
     * CSTree::GetRootItem
     * @brief    获取根节点
     * @param    BOOL bFirst -- 是否从根节点
     * @return   返回HSTREEITEM
     *
     * Describe  获取根节点
     */
    HSTREEITEM GetRootItem(BOOL bFirst = TRUE)
    {
        return (HSTREEITEM)(bFirst ? m_hRootFirst : m_hRootLast);
    }

    /**
     * CSTree::GetDesendants
     * @brief    获取结点的子孙结点数
     * @param    HSTREEITEM hItem -- 起始结点
     * @return   返回int
     *
     * Describe  获取结点的子孙结点数
     */
    int GetDesendants(HSTREEITEM hItem)
    {
        int nRet = 0;
        HSTREEITEM hChild = GetChildItem(hItem);
        while (hChild)
        {
            nRet += 1 + GetDesendants(hChild);
            hChild = GetNextSiblingItem(hChild);
        }
        return nRet;
    }

    /**
     * CSTree::GetNextItem
     * @brief    获取当前结点的下一个结点
     * @param    HSTREEITEM hItem -- 当前结点
     * @return   返回HSTREEITEM  当前结点的下一个结点
     *
     * Describe  获取当前结点的下一个结点
     * 如果当前结点有子结点，则返回自己的第一个子结点，
     * 否则如果有向下的兄弟结点，则返回自己向下兄弟结点、
     * 否则搜索自己的父结点的向下兄弟结点
     */
    HSTREEITEM GetNextItem(HSTREEITEM hItem) const
    {
        if (hItem == STVI_ROOT)
            return (HSTREEITEM)m_hRootFirst;

        HSTREEITEM hRet = GetChildItem(hItem);
        if (hRet)
            return hRet;
        HSTREEITEM hParent = hItem;
        while (hParent)
        {
            hRet = GetNextSiblingItem(hParent);
            if (hRet)
                return hRet;
            hParent = GetParentItem(hParent);
        }
        return NULL;
    }

    /**
     * CSTree::GetNextItem
     * @brief    获取当前结点的下一个结点
     * @param    HSTREEITEM hItem -- 当前结点
     * @param    int &nLevel -- 当前结点(hItem)与目标结点(return)的层次关系,
     *                          1-父子关系，0－兄弟关系，-n－子->父的兄弟
     * @return   返回HSTREEITEM  当前结点的下一个结点
     *
     * Describe  获取当前结点的下一个结点
     *           如果当前结点有子结点，则返回自己的第一个子结点，
     *           否则如果有向下的兄弟结点，则返回自己向下兄弟结点、
     *           否则搜索自己的父结点的向下兄弟结点
     */
    HSTREEITEM GetNextItem(HSTREEITEM hItem, int &nLevel) const
    {
        if (hItem == STVI_ROOT)
        {
            nLevel = 1;
            return (HSTREEITEM)m_hRootFirst;
        }

        HSTREEITEM hRet = GetChildItem(hItem);
        if (hRet)
        {
            nLevel = 1;
            return hRet;
        }
        HSTREEITEM hParent = hItem;
        nLevel = 0;
        while (hParent)
        {
            hRet = GetNextSiblingItem(hParent);
            if (hRet)
                return hRet;
            nLevel--;
            hParent = GetParentItem(hParent);
        }
        return NULL;
    }

    void SortChildren(HSTREEITEM hItem, int(__cdecl *funSort)(void *, const void *, const void *), void *pCtx)
    {
        int nChilds = GetChildrenCount(hItem);
        if (nChilds > 1)
        {
            HSTREEITEM *pChilds = new HSTREEITEM[nChilds];
            HSTREEITEM hChild = GetChildItem(hItem);
            pChilds[0] = hChild;
            for (int i = 1; i < nChilds; i++)
            {
                hChild = GetNextSiblingItem(hChild);
                pChilds[i] = hChild;
            }
            //调用qsort排序
            qsort_s(pChilds, nChilds, sizeof(HSTREEITEM), funSort, pCtx);
            //重新整理链表
            for (int i = 0; i < nChilds - 1; i++)
            {
                HSTREENODE node = (HSTREENODE)pChilds[i];
                node->hNextSibling = (HSTREENODE)pChilds[i + 1];
            }
            for (int i = 1; i < nChilds; i++)
            {
                HSTREENODE node = (HSTREENODE)pChilds[i];
                node->hPrevSibling = (HSTREENODE)pChilds[i - 1];
            }
            HSTREENODE node = (HSTREENODE)pChilds[0];
            node->hPrevSibling = NULL;
            node = (HSTREENODE)pChilds[nChilds - 1];
            node->hNextSibling = NULL;
            if (hItem != STVI_ROOT)
            {
                HSTREENODE parent = (HSTREENODE)hItem;
                parent->hChildFirst = (HSTREENODE)pChilds[0];
                parent->hChildLast = (HSTREENODE)pChilds[nChilds - 1];
            }
            else
            {
                m_hRootFirst = (HSTREENODE)pChilds[0];
                m_hRootLast = (HSTREENODE)pChilds[nChilds - 1];
            }
            delete[] pChilds;
        }
        //子节点排序
        HSTREEITEM hChild = GetChildItem(hItem);
        while (hChild)
        {
            HSTREENODE node = (HSTREENODE)hChild;
            if (node->hChildFirst && node->hChildLast && node->hChildFirst != node->hChildLast)
            {
                SortChildren(hChild, funSort, pCtx);
            }
            hChild = GetNextSiblingItem(hChild);
        }
    }

  private:
    /**
     * CSTree::FreeNode
     * @brief    采用后序遍历的方式释放结点占用的空间
     * @param    HSTREENODE hsNode -- 当前结点
     *
     * Describe  采用后序遍历的方式释放结点占用的空间
     */
    void FreeNode(HSTREENODE hsNode)
    {
        SASSERT(hsNode);
        HSTREENODE hSibling = (HSTREENODE)GetChildItem((HSTREEITEM)hsNode);
        while (hSibling)
        {
            HSTREENODE hNextSibling = hSibling->hNextSibling;
            FreeNode(hSibling);
            hSibling = hNextSibling;
        }
        if (hsNode != STVN_ROOT)
        {
            OnNodeFree(hsNode->data);
            delete hsNode;
        }
    }

  protected:
    /**
     * CSTree::OnNodeFree
     * @brief    在派生类中实现数据的释放操作
     * @param    T & data -- 数据
     *
     * Describe  在派生类中实现数据的释放操作
     */
    virtual void OnNodeFree(T &data)
    {
    }

    HSTREENODE m_hRootFirst; /**< 第一个根节点 */
    HSTREENODE m_hRootLast;  /**< 最后一个根节点 */
};

#endif // !defined(AFX_STREE_H__D2332B4E_2C7E_4357_BE22_EC55BF496C1C__INCLUDED_)
