/* BPlusTree.h
B+樹定義文件，本程序實行一個簡單的B+樹
Definition (from http://www.seanster.com/BplusTree/BplusTree.html): 
(1) A B+ tree of order v consists of a root, internal nodes and leaves. 
(2) The root my be either leaf or node with two or more children. 
(3) Internal nodes contain between v and 2v keys, and a node with k keys has k + 1 children. 
(4) Leaves are always on the same level. 
(5) If a leaf is a primary index, it consists of a bucket of records, sorted by search key. If it is a secondary index, it will have many short records consisting of a key and a pointer to the actual record.
(1) 一個v階的B+樹由根結點、內部結點和葉子結點組成。
(2) 根結點可以是葉子結點，也可以是有兩個或更多子樹的內部結點。
(3) 每個內部結點包含v - 2v個鍵。如果一個內部結點包含k個鍵，則有且只有k+1個指向子樹的指針。
(4) 葉子結點總是在樹的同一層上。
(5) 如果葉子結點是主索引，它包含一組按鍵值排序的記錄；如果葉子結點是從索引，它包含一組短記錄，每個短記錄包含一個鍵以及指向實際記錄的指針。
(6) 內部結點的鍵值和葉子結點的數據值都是從小到大排序的。
(7) 在中間結點中，每個鍵的左子樹中的所有的鍵都小于這個鍵，每個鍵的右子樹中的所有的鍵都大于等于這個鍵。
*/

/* B+ 樹的階，即內部結點中鍵的最小數目v。 
   也有些人把階定義為內部結點中鍵的最大數目，即2v。 
   一般而言，葉子結點中最大數據個數和內部結點中最大鍵個數是一樣的，也是2v。(我想這樣做的目的是為了把內部結點和葉子結點統一到同一個結構中吧)
*/ 
#define ORDER_V 2    /* 為簡單起見，把v固定為2，實際的B+樹v值應該是可配的 */
#define MAXNUM_KEY (ORDER_V * 2)    /* 內部結點中最多鍵個數，為2v */
#define MAXNUM_POINTER (MAXNUM_KEY + 1)    /* 內部結點中最多指向子樹的指針個數，為2v */
#define MAXNUM_DATA (ORDER_V * 2)    /* 葉子結點中最多數據個數，為2v */
/* 鍵值的類型*/
typedef int KEY_TYPE;    /* 為簡單起見，定義為int類型，實際的B+樹鍵值類型應該是可配的 */
/*備注： 為簡單起見，葉子結點的數據也只存儲鍵值*/
/* 結點類型 */
enum NODE_TYPE
{
NODE_TYPE_ROOT     = 1,    // 根結點
NODE_TYPE_INTERNAL = 2,    // 內部結點
NODE_TYPE_LEAF     = 3,    // 葉子結點
};
#define NULL 0
#define INVALID 0
#define FLAG_LEFT 1
#define FLAG_RIGHT 2
/* 結點數據結構，為內部結點和葉子結點的父類 */
class CNode
{
public:
    CNode();
    virtual ~CNode();
    
    //獲取和設置結點類型
    NODE_TYPE GetType() { return m_Type; }
    void SetType(NODE_TYPE type) {m_Type = type;}
    // 獲取和設置有效數據個數
    int GetCount() { return m_Count;}
    void SetCount(int i) { m_Count = i; }
    // 獲取和設置某個元素，對中間結點指鍵，對葉子結點指數據
    virtual KEY_TYPE GetElement(int i) {return 0;}
    virtual void SetElement(int i, KEY_TYPE value) { }
    
    // 獲取和設置某個指針，對中間結點指指針，對葉子結點無意義
    virtual CNode* GetPointer(int i) {return NULL;}
    virtual void SetPointer(int i, CNode* pointer) { }
    // 獲取和設置父結點
    CNode* GetFather() { return m_pFather;}
    void SetFather(CNode* father) { m_pFather = father; }
    // 獲取一個最近的兄弟結點
    CNode* GetBrother(int& flag);
    // 刪除結點
    void DeleteChildren();
protected:
    
    NODE_TYPE m_Type;    // 結點類型，取值為NODE_TYPE類型
    int m_Count;    // 有效數據個數，對中間結點指鍵個數，對葉子結點指數據個數
    CNode* m_pFather;     // 指向父結點的指針，標準B+樹中并沒有該指針，加上是為了更快地實現結點分裂和旋轉等操作
};
/* 內部結點數據結構 */
class CInternalNode : public CNode
{
public:
    CInternalNode();
    virtual ~CInternalNode();
    // 獲取和設置鍵值，對用戶來說，數字從1開始
    KEY_TYPE GetElement(int i) 
    { 
        if ((i > 0 ) && (i <= MAXNUM_KEY))
        {
            return m_Keys[i - 1];
        }
        else
        {
            return INVALID;
        }
    }
    void SetElement(int i, KEY_TYPE key)
    {
        if ((i > 0 ) && (i <= MAXNUM_KEY))
        {
            m_Keys[i - 1] = key;
        }
    }
    // 獲取和設置指針，對用戶來說，數字從1開始
    CNode* GetPointer(int i) 
    { 
        if ((i > 0 ) && (i <= MAXNUM_POINTER))
        {
            return m_Pointers[i - 1];
        }
        else
        {
            return NULL;
        }
    }
    void SetPointer(int i, CNode* pointer)
    {
        if ((i > 0 ) && (i <= MAXNUM_POINTER))
        {
            m_Pointers[i - 1] = pointer;
        }
    }
    // 插入鍵
    bool Insert(KEY_TYPE value, CNode* pNode);
    // 刪除鍵
    bool Delete(KEY_TYPE value);
    // 分裂結點
    KEY_TYPE Split(CInternalNode* pNode, KEY_TYPE key);
    // 結合結點
    bool Combine(CNode* pNode);
    // 從另一結點移一個元素到本結點
    bool MoveOneElement(CNode* pNode);
protected:
    KEY_TYPE m_Keys[MAXNUM_KEY];           // 鍵數組
    CNode* m_Pointers[MAXNUM_POINTER];     // 指針數組
};
/* 葉子結點數據結構 */
class CLeafNode : public CNode
{
public:
    CLeafNode();
    virtual ~CLeafNode();
    // 獲取和設置數據
    KEY_TYPE GetElement(int i)
    {
        if ((i > 0 ) && (i <= MAXNUM_DATA))
        {
            return m_Datas[i - 1];
        }
        else
        {
            return INVALID;
        }
    }
    void SetElement(int i, KEY_TYPE data)
    {
        if ((i > 0 ) && (i <= MAXNUM_DATA))
        {
            m_Datas[i - 1] = data;
        }
    }
    // 獲取和設置指針，對葉子結點無意義，只是實行父類的虛函數
    CNode* GetPointer(int i) 
    { 
        return NULL;
    }
    
    // 插入數據
    bool Insert(KEY_TYPE value);
    // 刪除數據
    bool Delete(KEY_TYPE value);
    // 分裂結點
    KEY_TYPE Split(CNode* pNode);
    // 結合結點
    bool Combine(CNode* pNode);
public:
    // 以下兩個變量用于實現雙向鏈表
    CLeafNode* m_pPrevNode;                 // 前一個結點 
    CLeafNode* m_pNextNode;                 // 后一個結點 
    
protected:
    KEY_TYPE m_Datas[MAXNUM_DATA];    // 數據數組
};
/* B+樹數據結構 */ 
class BPlusTree
{
public:
   
    BPlusTree();
    virtual ~BPlusTree();
    // 查找指定的數據
    bool Search(KEY_TYPE data, char* sPath);
    // 插入指定的數據
    bool Insert(KEY_TYPE data);
    // 刪除指定的數據
    bool Delete(KEY_TYPE data);
    // 清除樹
    void ClearTree();
    // 打印樹
    void PrintTree();
    // 旋轉樹
    BPlusTree* RotateTree();
    // 檢查樹是否滿足B+樹的定義
    bool CheckTree();
    void PrintNode(CNode* pNode);
    // 遞歸檢查結點及其子樹是否滿足B+樹的定義
    bool CheckNode(CNode* pNode);
    // 獲取和設置根結點
    CNode* GetRoot()
    {
        return m_Root;
    }
    void SetRoot(CNode* root)
    {
        m_Root = root;
    }
    // 獲取和設置深度
    int GetDepth()
    {
        return m_Depth;
    }
    void SetDepth(int depth)
    {
        m_Depth = depth;
    }
    
    // 深度加一
    void IncDepth()
    {
        m_Depth = m_Depth + 1;
    }
    // 深度減一
    void DecDepth()
    {
        if (m_Depth > 0)
        {
            m_Depth = m_Depth - 1;
        }
    }
public:
    // 以下兩個變量用于實現雙向鏈表
    CLeafNode* m_pLeafHead;                 // 頭結點 
    CLeafNode* m_pLeafTail;                   // 尾結點
protected:
    // 為插入而查找葉子結點
    CLeafNode* SearchLeafNode(KEY_TYPE data);
    //插入鍵到中間結點
    bool InsertInternalNode(CInternalNode* pNode, KEY_TYPE key, CNode* pRightSon);
    // 在中間結點中刪除鍵
    bool DeleteInternalNode(CInternalNode* pNode, KEY_TYPE key);
    
    CNode* m_Root;    // 根結點
    int m_Depth;      // 樹的深度
};
/* end of BPlusTree.h */