/********************************************************************
  created:  2008/06/12
  filename: DoubleList.h
  author:   happymouse

  version:  v1.0.0.0
*********************************************************************/
#pragma once

#include <cassert>

// Double list node template class
template<typename T>
class CDoubleListNode
{
public:
    // Data
    T m_data;
    // Next data
    CDoubleListNode<T> *m_pNext;
    // Prior data
    CDoubleListNode<T> *m_pPrior;
    // Constructor
    CDoubleListNode(){}
    // Constructor
    CDoubleListNode(const T& data): m_data(data){}
};

// Double list template class
template<typename T>
class CDoubleList
{
private:
    // List count
    int m_nCount;
    
    // Head data node pointer
    CDoubleListNode<T> *m_pHeadNode;
    
    // Head data node
    CDoubleListNode<T> m_HeadNode;
    
    // Get node at index.(0 is the head node)
    CDoubleListNode<T> * GetAt(const int& nIndex)
    {
        assert(nIndex >= 0 && nIndex <= m_nCount);
        CDoubleListNode<T> * _pRet = m_pHeadNode;
        for (int i = 0; i < nIndex; i++)
        {
            _pRet = _pRet->m_pNext;
        }
        return _pRet;
    }
    
    // Clear list
    void Clear()
    {
        while (m_nCount > 0)
        {
            RemoveAt(1);
        }
    }
public:
    // Constructor
    CDoubleList()
        :m_nCount(0)
    {
        m_pHeadNode = m_HeadNode.m_pNext = m_HeadNode.m_pPrior = &m_HeadNode;
    }
    
    // Destructor
    virtual ~CDoubleList()
    {
        Clear();
    }
    
    // Remove node at index. (index start at 1)
    bool RemoveAt(const int& nIndex)
    {
        assert(nIndex >= 0 && nIndex <= m_nCount);
        CDoubleListNode<T> * _pDeleteNode = GetAt(nIndex);
        CDoubleListNode<T> * _pNode = _pDeleteNode->m_pNext;
        _pDeleteNode->m_pPrior->m_pNext = _pDeleteNode->m_pNext;
        _pNode->m_pPrior = _pDeleteNode->m_pPrior;
        delete _pDeleteNode;
        m_nCount--;
        return true;
    }
    
    // Get count of list
    int GetCount()
    {
        return m_nCount;
    }
    
    // Insert a data into head of list
    bool InsertHead(const T& data)
    {
        return InsertAfter(0, data);
    }
    
    // Insert a data into list before a index.(index start at 1)
    bool InsertBefore(const int &nIndex, const T& data)
    {
        assert(nIndex > 0 && nIndex <= m_nCount);
        CDoubleListNode<T> * _pNewNode = new CDoubleListNode<T>(data);
        assert(NULL != _pNewNode);
        if (NULL == _pNewNode)
        {
            return false;
        }
        CDoubleListNode<T> * _pNode = GetAt(nIndex);
        _pNewNode->m_pNext = _pNode;
        _pNewNode->m_pPrior = _pNode->m_pPrior;
        _pNewNode->m_pPrior->m_pNext = _pNewNode;
        _pNode->m_pPrior = _pNewNode;
        m_nCount++;
        return true;
    }
    
    // Insert a data info tail of list
    bool InsertTail(const T& data)
    {
        return InsertAfter(m_nCount, data);
    }
    
    // Insert a data into list after a index.(index start at 1)
    bool InsertAfter(const int &nIndex, const T& data)
    {
        assert(nIndex >= 0 && nIndex <= m_nCount);
        CDoubleListNode<T> * _pNewNode = new CDoubleListNode<T>(data);
        assert(NULL != _pNewNode);
        if (NULL == _pNewNode)
        {
            return false;
        }
        CDoubleListNode<T> * _pNode = GetAt(nIndex);
        _pNewNode->m_pNext = _pNode->m_pNext;
        _pNewNode->m_pPrior = _pNode;
        _pNewNode->m_pNext->m_pPrior = _pNewNode;
        _pNode->m_pNext = _pNewNode;
        m_nCount++;
        return true;
    }
    
    // Get node at index. (index start at 1)
    CDoubleListNode<T> * operator[](const int &nIndex)
    {
        return GetAt(nIndex);
    }
};