///////////////////////////////////////////////////////
//   模块名： 双向链表模板实现   
//   研究者： 长寿梦
//   最后更新：2010-05-05 
//////////////////////////////////////////////////////
#ifndef   DLIST_H   
#define   DLIST_H   

#include   <assert.h>   
#include   <iostream.h>   

template   <class   T>   class   CDList; 
  
//一：节点类
template   <class   T>   
class   CDListNode   
{   
  public:   
      friend   CDList<T>;//节点的友元是链表
  private:   
      T   data;   //数据域 
      CDListNode<T>   *   previous; //前一个  
      CDListNode<T>   *   next;  //下一个 
}; 
  
//二：链表类
template   <class   T>   
class   CDList   
{   
  private:   
      CDListNode<T>   *   m_phead;  //头
      CDListNode<T>   *   m_ptail;   //尾
      int m_count; //节点个数  
      
  public:   
      void   show(void);   
      CDList();   
      ~CDList();   
      
      //   Head/Tail   Access   Methods   
      T   &   GetHead(void)   const;     
      T   &   GetTail(void)   const;   
      
      //   Operations   Methods   
      void   RemoveHead(void);     
      void   RemoveTail(void); 
      void   RemoveAll(void);  
      int   AddHead(const   T   &   NewNode);     
      int   AddTail(const   T   &   NewNode);   
          
      
      //   Iteration   Methods   
      int   GetHeadPosition(void)   const;   
      int   GetTailPosition(void)   const;   
      T   &   GetNext(int   position)   const;     
      T   &   GetPrev(int   position)   const;     
      
      //   Retrieval/Modification   Methods   
      T   &   GetAt(int   position)   const;     
      void   SetAt(int   pos,   const   T   &   newElement);   
      void   RemoveAt(int   position);   
      
      //   Insertion   Methods   
      int   InsertBefore(int   position,const   T   &   newElement);   
      int   InsertAfter(int   position,   const   T   &   newElement);   
      
      //   Searching   Methods   
      int   Find(const   T   &   searchValue,   int   startAfter   =   1)   const;   
      
      //   Status   Methods   
      int   GetCount(void)   const;   
      int   GetSize(void)   const;   
      bool   IsEmpty(void)   const;   
};   

//////////////////////////////////////////////////////////////////////   
//实现部分代码
//////////////////

//1.构造：初始化列表
template   <class   T>   
CDList<T>::CDList():m_phead(NULL),   m_ptail(NULL),   m_count(0)   
{   
}   
//2.析构
template   <class   T>   
CDList<T>::~CDList()   
{   
    RemoveAll();   
}   

//3.   获取头结点的值   
template   <class   T>   
T   &   CDList<T>::GetHead(void)   const   
{   
    assert(m_phead   !=   NULL);   
    return   m_phead->data;   
}   

//4.   获取尾结点的值   
template   <class   T>   
T   &   CDList<T>::GetTail(void)   const   
{   
    assert(m_ptail   !=   NULL);   
    return   m_ptail->data;   
}   

// 5.  删除头结点   
template   <class   T>   
void   CDList<T>::RemoveHead(void)   
{   
    if(m_phead   !=   NULL)   //   链表不为空   
    {   
        CDListNode<T>   *pRemove;   
        pRemove=m_phead;
        if(pRemove->next   ==   NULL)   // 只有一个结点   
            m_phead   =   m_ptail   =   NULL;   
        else   
        {   
            m_phead   =   m_phead->next;   
            m_phead->previous   =   NULL;   
        }   
        
        delete   pRemove;//回收资源   
        m_count--;   
    }   
}   

// 6.  删除尾结点   
template   <class   T>   
void   CDList<T>::RemoveTail(void)   
{   
    if(m_ptail   !=   NULL)   //   链表不为空   
    {   
        CDListNode<T>   *pRemove;   
        pRemove   =   m_ptail;   
        
        if(pRemove->previous   ==   NULL)   //   只有一个结点   
            m_phead   =   m_ptail   =   NULL;   
        else   
        {   
            m_ptail   =   m_ptail->previous;   
            m_ptail->next   =   NULL;   
        }   
        
        delete   pRemove;   
        m_count--;   
    }   
}   

//7.  从链表头部插入结点   
template   <class   T>   
int   CDList<T>::AddHead(const   T   &   NewNode)   
{   
    CDListNode<T>   *p;   
    p   =   new   CDListNode<T>;   
    p->data   =   NewNode;   
    p->previous   =   NULL;   
    
    if(m_phead   ==   NULL)   //   链表为空   
    {   
        p->next   =   NULL;   
        m_ptail   =   p;   
    }   
    else   
    {   
        p->next   =   m_phead;   
        m_phead->previous   =   p;   
    }   
    m_phead   =   p;   
    m_count++;   
    
    return   1;   
}   

// 8.  从链表尾部插入结点   
template   <class   T>   
int   CDList<T>::AddTail(const   T   &   NewNode)   
{   
    CDListNode<T>   *p;   
    p   =   new   CDListNode<T>;   
    p->data   =   NewNode;   
    
    p->next   =   NULL;   
    if(m_ptail   ==   NULL) //   链表为空   
    {   
        p->previous   =   NULL;   
        m_phead   =   p;   
    }   
    else   
    {   
        p->previous   =   m_ptail;   
        m_ptail->next   =   p;   
    }   
    m_ptail   =   p;   
    m_count++;   
    
    return   m_count;   
}   

//9.   删除所有结点   
template   <class   T>   
void   CDList<T>::RemoveAll(void)   
{   
    CDListNode<T>   *p   =   m_phead;   
    while   (m_phead   !=   NULL)   
    {   
        m_phead   =   m_phead->next;   
        delete   p;   
        p   =   m_phead;   
        m_count--;   
    }   
    m_ptail   =   NULL;   
}     

// 10.  获取头结点位置   
template   <class   T>   
int   CDList<T>::GetHeadPosition(void)   const   
{   
    
    return   (m_count!=0)   ?   1   :   0;   
}   

//  11. 获取尾结点位置   
template   <class   T>   
int   CDList<T>::GetTailPosition(void)   const   
{   
    return   m_count;   
}   

// 12. 获取某结点的后一个结点值   
template   <class   T>   
T   &   CDList<T>::GetNext(int   position)   const   
{   
    return   GetAt(position+1);   
}     

// 13.  获取某结点的前一个结点值   
template   <class   T>   
T   &   CDList<T>::GetPrev(int   position)   const   
{   
    return   GetAt(position-1);   
}   

//14.  获取结点值   
template   <class   T>   
T   &   CDList<T>::GetAt(int   position)   const   
{   
    assert((position>0)   &&   (position<=m_count));   
    
    CDListNode<T>   *p   =   m_phead;   
    for(int   i=1;i<position;i++)   //   定位结点   
    {   
        p   =   p->next;   
    }   
    return   p->data;   
}   

//15.  修改结点值   
template   <class   T>   
void   CDList<T>::SetAt(int   pos,   const   T   &   newElement)   
{   
    assert((pos>0)   &&   (pos<=m_count));   
    
    CDListNode<T>   *p   =   m_phead;   
    for(int   i=1;   i<pos;   i++)   
    {   
        p   =   p->next;   
    }   
    p->data   =   newElement;   
}   

// 16.  删除结点   
template   <class   T>   
void   CDList<T>::RemoveAt(int   position)   
{   
    assert((position>0)   &&   (position<=m_count));   
    
    CDListNode<T>   *pRemove   =   m_phead;   
    for   (int   i=1;   i<position;   i++)   //   定位结点   
    {   
        pRemove   =   pRemove->next;   
    }   
    
    if   (pRemove->previous   ==   NULL)   //   如果是头结点   
    {   
        RemoveHead();   
        return;   
    }   
    
    if   (pRemove->next   ==   NULL)   //   如果是尾结点   
    {   
        RemoveTail();   
        return;   
    }   
    
    CDListNode<T>   *p;   
    p   =   pRemove->previous;   
    p->next   =   pRemove->next;   
    pRemove->next->previous   =   p;   
    
    delete   pRemove;   
    m_count--;   
}   

//17.  在某个结点之前插入新结点   
template   <class   T>   
int   CDList<T>::InsertBefore(int   position,   const   T   &   newElement)   
{   
    assert((position>0)   &&   (position<=m_count));   
    
    CDListNode<T>   *p   =   m_phead;   
    for   (int   i=1;   i<position;   i++)   //   定位结点   
    {   
        p   =   p->next;   
    }   
    
    //   在头结点前插入新结点   
    if   (p->previous   ==   NULL)   return   AddHead(newElement);   
    
    CDListNode<T>   *pNewNode;   
    pNewNode   =   new   CDListNode<T>;   
    pNewNode->data   =   newElement;   
    
    pNewNode->previous   =   p->previous;   
    pNewNode->next   =   p;   
    p->previous->next   =   pNewNode;   
    p->previous   =   pNewNode;   
    
    m_count++;   
    return   i;   
}   

// 18.  在某个结点之后插入新结点   
template   <class   T>   
int   CDList<T>::InsertAfter(int   position,   const   T   &   newElement   )   
{   
    assert((position>0)   &&   (position<=m_count));   
    
    CDListNode<T>   *p   =   m_phead;   
    for(int   i=1;   i<position;   i++)   //   定位结点   
    {   
        p   =   p->next;   
    }   
    
    //   在尾结点后插入新结点   
    if   (p->next   ==   NULL)   return   AddTail(newElement);   
    
    CDListNode<T>   *pNewNode;   
    pNewNode   =   new   CDListNode<T>;   
    pNewNode->data   =   newElement;   
    
    pNewNode->previous   =   p;   
    pNewNode->next   =   p->next;   
    p->next->previous   =   pNewNode;   
    p->next   =   pNewNode;   
    
    m_count++;   
    return   i+1;   
}   

// 19.  在链表中查找结点   
template   <class   T>   
int   CDList<T>::Find(const   T   &   searchValue,   int   startAfter)   const   
{   
    assert((startAfter>0)   &&   (startAfter<=m_count));   
    
    CDListNode<T>   *p   =   m_phead;   
    int   i;   
    
    //   从startAfter所指的结点向后查找   
    for(i=1;   i<startAfter;   i++)   p=p->next;   
    
    while   (p   !=   NULL)   
    {   
        //   返回结点在链表中的位置，第一个结点为1   
        if   (p->data   ==   searchValue)   return   i+1;     
        p   =   p->next;   
        i++;   
    }   
    
    return   0;   //   没有找到   
}   

//20.   获取链表结点个数   
template   <class   T>   
int   CDList<T>::GetCount(void)   const   
{   
    return   m_count;   
}   

//21.   获取链表结点个数   
template   <class   T>   
int   CDList<T>::GetSize(void)   const   
{   
    return   m_count;   
}   

// 22. 判断链表是否为空   
template   <class   T>   
bool   CDList<T>::IsEmpty(void)   const   
{   
    return   (m_count   ==   0)   ?   true   :   false;   
}   

 //23. 显示链表结点元素    优点之一
template   <class   T>   
void   CDList<T>::show(void)   
{   
    CDListNode<T>   *p;   
    
    cout<<"当前链表共有结点："<<GetCount()<<"个";   
    cout<<endl<<"结点顺序列表如下：";   
    p   =   m_phead;   
    while(p   !=   NULL)   
    {   
        cout<<"     "<<   p->data;   
        p   =   p->next;   
    }   
    
    cout<<endl<<"结点逆序列表如下：";   
    p   =   m_ptail;   
    while   (p   !=   NULL)   
    {   
        cout<<"     "<<   p->data;   
        p   =   p->previous;   
    }   
    cout<<endl<<endl;   
}   

#endif