/* 雙向結(jié)點(diǎn)
 * QA Pass
 */

#ifndef DOUBLY_LINKED_NODE_CLASS
#define DOUBLY_LINKED_NODE_CLASS

#include <stdlib.h>

template <class T>
class DNode
{
    private:
    	// 指向左、右結(jié)點(diǎn)的指針
        DNode<T> *left;
        DNode<T> *right;
    public: 
    	// data 為公有成員 
        T data;
        
		// 構(gòu)造函數(shù)
        DNode(void); 
        DNode (const T& item);
        
        
        // 改變表的方法
        void InsertRight(DNode<T> *p);
        void InsertLeft(DNode<T> *p);
        DNode<T> *DeleteNode(void);
        
        
        // 取得指向左、右方向結(jié)點(diǎn)的指針
        DNode<T> *NextNodeRight(void) const;
        DNode<T> *NextNodeLeft(void) const;
};

// 創(chuàng)建空表并保留數(shù)據(jù)未定義，用于 header
template <class T>
DNode<T>::DNode(void)
{
	// 初始化結(jié)點(diǎn)使其指向自身
    left = right = this;
}

// 創(chuàng)建空表并初始化數(shù)據(jù)
template <class T>
DNode<T>::DNode(const T& item)
{
	// 建立一個(gè)指向自身的結(jié)點(diǎn)并初始化 data 域
    left = right = this;
    data = item;
}
        
// 將結(jié)點(diǎn) p 插入到雙向鏈表中當(dāng)前結(jié)點(diǎn)的右邊
template <class T>
void DNode<T>::InsertRight(DNode<T> *p)
{
	// 將 p 和當(dāng)前結(jié)點(diǎn)的右后繼結(jié)點(diǎn)相連
    p->right = right;
	right->left = p;
	
 	// 將 p 的左邊和當(dāng)前結(jié)點(diǎn)相連
    p->left = this;
    right = p;
}

// 將結(jié)點(diǎn) p 插入到當(dāng)前結(jié)點(diǎn)左邊
template <class T>
void DNode<T>::InsertLeft(DNode<T> *p)
{
	// 將 p 和當(dāng)前結(jié)點(diǎn)的左后繼結(jié)點(diǎn)相連
    p->left = left;
    left->right = p;
    
 	// 將 p 的右邊和當(dāng)前結(jié)點(diǎn)相連
    p->right = this;
    left = p;
}

// 從鏈表中刪除當(dāng)前結(jié)點(diǎn)并返回其地址
template <class T>
DNode<T> *DNode<T>::DeleteNode(void)
{
	// 左邊的結(jié)點(diǎn)必須鏈接到當(dāng)前結(jié)點(diǎn)的右邊
    left->right = right;
    
	// 右邊的結(jié)點(diǎn)必須鏈接到當(dāng)前結(jié)點(diǎn)的左邊
    right->left = left;
    
    // 返回當(dāng)前結(jié)點(diǎn)的指針
    return this;
}

// 返回指向右邊結(jié)點(diǎn)的指針
template <class T>
DNode<T> *DNode<T>::NextNodeRight(void) const
{
    return right;
}

// 返回指向左邊結(jié)點(diǎn)的指針
template <class T>
DNode<T> *DNode<T>::NextNodeLeft(void) const
{
    return left;
}

#endif	// DOUBLY_LINKED_NODE_CLASS