// CList.h
#pragma once
#include <iostream>
using namespace std;

struct __POSITION { };
typedef __POSITION* POSITION;

typedef void (*PRINT) (void*);

template<typename TYPE, typename ARG_TYPE = const TYPE&>
class CList
{
protected:
    struct CNode
    {
        CNode* pNext;
        CNode* pPrev;
        TYPE data;
    };
public:
    // Construction
    CList() : m_pHead(nullptr), m_pTail(nullptr), m_nCount(0) { }

    // Attributes (head and tail)
        // count of elements
    int GetCount() const { return m_nCount; }
    bool IsEmpty() const { return m_nCount <= 0; }

    // peek at head or tail
    TYPE& GetHead() { return m_pHead->data; }
    const TYPE& GetHead() const { return m_pHead->data; }
    TYPE& GetTail() { return m_pTail->data; }
    const TYPE& GetTail() const { return m_pTail->data; }

    // Operations
        // get head or tail (and remove it) - don't call on empty list !
    void RemoveHead();
    void RemoveTail();

    // add before head or after tail
    POSITION AddHead(ARG_TYPE newElement);
    POSITION AddTail(ARG_TYPE newElement);

    // add another list of elements before head or after tail
    void AddHead(CList* pNewList);
    void AddTail(CList* pNewList);

    // remove all elements
    void RemoveAll();

    // iteration
    POSITION GetHeadPosition() const { return (POSITION)m_pHead; }
    POSITION GetTailPosition() const { return (POSITION)m_pTail; }
    TYPE& GetNext(POSITION& rPosition); 
    const TYPE& GetNext(POSITION& rPosition) const; // return *Position++
    TYPE& GetPrev(POSITION& rPosition);
    const TYPE& GetPrev(POSITION& rPosition) const; // return *Position--

    // getting/modifying an element at a given position
    TYPE& GetAt(POSITION position);
    const TYPE& GetAt(POSITION position) const;
    void SetAt(POSITION pos, ARG_TYPE newElement);
    void RemoveAt(POSITION position);
    void Remove(CList<TYPE, ARG_TYPE>& list, ARG_TYPE arg, bool bDelSame = false);

    // inserting before or after a given position
    POSITION InsertBefore(POSITION position, ARG_TYPE newElement);
    POSITION InsertAfter(POSITION position, ARG_TYPE newElement);

    // helper functions (note: O(n) speed)
    POSITION Find(ARG_TYPE searchValue, POSITION startAfter = nullptr) const;
    // defaults to starting at the HEAD, return NULL if not found
    POSITION FindIndex(int nIndex) const;
    void Print(int s, int e) const;
    // get the 'nIndex'th element (may return NULL)
// Implementation
protected:
    CNode* m_pHead;
    CNode* m_pTail;
    int m_nCount;
    CNode* NewNode(ARG_TYPE newElement)
    {
        CNode* p = new CNode;
        if (p == nullptr) return nullptr;
        p->pPrev = p->pNext = nullptr;
        p->data = newElement;
        return p;
    }
public:
    ~CList() { 
        cout << "CList has been destroy\n";
        RemoveAll(); 
    }
};


template<class TYPE, class ARG_TYPE>
inline void CList<TYPE, ARG_TYPE>::RemoveHead()
{
    if (m_pHead == nullptr) return;
    else {
        CNode* p = m_pHead;
        m_pHead = m_pHead->pNext;
        m_pHead->pPrev = nullptr;
        delete p;
    }
}

template<class TYPE, class ARG_TYPE>
inline void CList<TYPE, ARG_TYPE>::RemoveTail()
{
    if (m_pTail == nullptr) return;
    else {
        CNode* p = m_pTail;
        m_pTail = m_pTail->pPrev;
        m_pTail->pNext = nullptr;
        delete p;
    }
} 

template<class TYPE, class ARG_TYPE>
inline POSITION CList<TYPE, ARG_TYPE>::AddHead(ARG_TYPE newElement)
{
    CNode* p = NewNode(newElement);
    if(IsEmpty()) m_pHead = m_pTail = p;
    else 
    {
        p->pNext = m_pHead;
        p->pNext->pPrev = p;
        m_pHead = p;
    }
    m_nCount++;
    return (POSITION)p;
}

template<class TYPE, class ARG_TYPE>
inline POSITION CList<TYPE, ARG_TYPE>::AddTail(ARG_TYPE newElement)
{
    CNode* p = NewNode(newElement);
    if (IsEmpty()) m_pHead = m_pTail = p;
    else
    {
        p->pPrev = m_pTail;
        p->pPrev->pNext = p;
        m_pTail = p;
    }
    m_nCount++;
    return (POSITION)p;
}

template<class TYPE, class ARG_TYPE>
inline void CList<TYPE, ARG_TYPE>::AddHead(CList* pNewList)
{
    if (pNewList->IsEmpty()) return;
    for (auto p = pNewList->GetTailPosition(); p != nullptr; pNewList->GetPrev(p))
    {
        CNode* q = NewNode(pNewList->GetAt(p));
        if (q == nullptr) return;
        q->data = ((CNode*)p)->data;
        AddHead(q->data);
    }

}

template<class TYPE, class ARG_TYPE>
inline void CList<TYPE, ARG_TYPE>::AddTail(CList* pNewList)
{
    if (pNewList == nullptr) return;
    for (auto p = pNewList->GetHeadPosition(); p != nullptr; pNewList->GetNext(p))
    {
        CNode* q = NewNode(pNewList->GetAt(p));
        if (!q) return;
        q->data = ((CNode*)p)->data;
        AddTail(q->data);
    }
}

template<class TYPE, class ARG_TYPE>
inline void CList<TYPE, ARG_TYPE>::RemoveAll()
{
    if (!IsEmpty()) RemoveHead();
    m_nCount = 0;
    m_pHead = m_pTail = nullptr;
}

template<class TYPE, class ARG_TYPE>
inline TYPE& CList<TYPE, ARG_TYPE>::GetNext(POSITION& rPosition)
{
    TYPE& t = ((CNode*)rPosition)->data;
    rPosition = (POSITION)(((CNode*)rPosition)->pNext);
    return t;
}

template<class TYPE, class ARG_TYPE>
inline const TYPE& CList<TYPE, ARG_TYPE>::GetNext(POSITION& rPosition) const
{
    TYPE& t = ((CNode*)rPosition)->data;
    rPosition = (POSITION)((CNode*)rPosition)->pNext;
    return t;
}

template<class TYPE, class ARG_TYPE>
inline TYPE& CList<TYPE, ARG_TYPE>::GetPrev(POSITION& rPosition)
{
    TYPE& t = ((CNode*)rPosition)->data;
    rPosition = (POSITION)((CNode*)rPosition)->pPrev;
    return t;
}

template<class TYPE, class ARG_TYPE>
inline const TYPE& CList<TYPE, ARG_TYPE>::GetPrev(POSITION& rPosition) const
{
    TYPE& t = ((CNode*)rPosition)->data;
    rPosition = ((CNode*)rPosition)->pPrev;
    return t;
}

template<class TYPE, class ARG_TYPE>
inline TYPE& CList<TYPE, ARG_TYPE>::GetAt(POSITION position)
{
    return ((CNode*)position)->data;
}

template<class TYPE, class ARG_TYPE>
inline const TYPE& CList<TYPE, ARG_TYPE>::GetAt(POSITION position) const
{
    return ((CNode*)position)->data;
}

template<class TYPE, class ARG_TYPE>
inline void CList<TYPE, ARG_TYPE>::SetAt(POSITION pos, ARG_TYPE newElement)
{
    ((CNode*)pos)->data = newElement;
}

template<class TYPE, class ARG_TYPE>
inline void CList<TYPE, ARG_TYPE>::RemoveAt(POSITION position)
{
    if (IsEmpty()) return;
    CNode* p = (CNode*)position;
    if (p == nullptr) return;
    if (p == m_pHead) {
        m_pHead = m_pHead->pNext;
        m_pHead->pPrev = nullptr;
    }
    else if (p == m_pTail) {
        m_pTail = m_pTail->pPrev;
        m_pTail->pNext = nullptr;
    }
    else {
        p->pNext->pPrev = p->pPrev;
        p->pPrev->pNext = p->pNext;
    }
    delete p;
}

template<typename TYPE, typename ARG_TYPE>
void CList<TYPE, ARG_TYPE>::Remove(CList<TYPE, ARG_TYPE>& list, ARG_TYPE arg, bool bDelSame) {
    POSITION p = list.GetHeadPosition();
    while (p) {
        auto q = p;
        list.GetNext(p);
        if (list.GetAt(q) == arg) {
            list.RemoveAt(q);
            if (!bDelSame) return;
        }
    }
}

template<class TYPE, class ARG_TYPE>
inline POSITION CList<TYPE, ARG_TYPE>::InsertBefore(POSITION position, ARG_TYPE newElement)
{
    CNode* p = (CNode*)position;
    CNode* q = NewNode(newElement);
    if (p == nullptr || p == m_pHead) 
        AddHead(newElement);
    else {
        q->pNext = p;
        q->pPrev = p->pPrev;
        p->pPrev->pNext = q;
        p->pPrev = q;
        m_nCount++;
    }
    return (POSITION)p;
}

template<class TYPE, class ARG_TYPE>
inline POSITION CList<TYPE, ARG_TYPE>::InsertAfter(POSITION position, ARG_TYPE newElement)
{
    CNode* p = (CNode*)position;
    CNode* q = NewNode(newElement);
    if (p == nullptr || p == m_pTail)
        AddTail(newElement);
    else {
        q->pNext = p->pNext;
        q->pPrev = p;
        p->pNext->pPrev = q;
        p->pNext = q;
        m_nCount++;
    }
    return (POSITION)p;
}

#include <iostream>
template<class TYPE, class ARG_TYPE>
inline POSITION CList<TYPE, ARG_TYPE>::Find(ARG_TYPE searchValue, POSITION startAfter) const
{
    int cnt = 0;
    POSITION p = nullptr;
    startAfter == nullptr ? p = GetHeadPosition() : p = startAfter;
    p = GetHeadPosition();
    while (p) {
        if (GetAt(p) == searchValue)
            cnt++;
        GetNext(p);
    }
    std::cout << "找到" << cnt << "个" << "[ " << searchValue << " ]";
    return p;
}

template<class TYPE, class ARG_TYPE>
inline POSITION CList<TYPE, ARG_TYPE>::FindIndex(int nIndex) const
{
    if (nIndex < 0) return (POSITION)m_pHead;
    if (nIndex >= m_nCount) return (POSITION)m_pTail;
    POSITION p = GetHeadPosition();
    for (int i = 0; i < nIndex; i++, GetNext(p));
    return (POSITION)p;
}


template<class TYPE, class ARG_TYPE>
inline void CList<TYPE, ARG_TYPE>::Print(int s, int e) const
{
    if (s <= 0) s = 0;
    if (e >= m_nCount) e = m_nCount;
    for (int i = s; i < e; i++)
        cout << ((CNode*)FindIndex(i))->data << " ";
    cout << endl;
}
// test.h
#include "Clist.h"
#include <iostream>

void print(void* p) {
    if (p == nullptr) return;
    std::cout << *(int*)p << " ";
}

int main() {
    CList<int, const int&> l, l1;

    l.AddHead(1);

    l.AddHead(2);

    l.AddHead(3); 

    l.AddTail(4);

    l.AddTail(5);

    l.AddTail(6);

    l1.AddTail(9);

    l1.AddTail(9);

    l1.AddTail(7);

    l1.AddTail(9);

    l.AddTail(&l1);
    l.AddHead(&l1);
    l.Print(0, l.GetCount());

    POSITION p = l.GetHeadPosition();
    for (int i = 0; i < 3; i++) {
        l.InsertAfter(p, i);
    } 

    p = l.GetHeadPosition();
    for (int i = 0; i < 3; i++) {
        l.InsertBefore(p, i);
    } 

    l.Print(0, l.GetCount());

    l.Print(2, 5);
    return 0; 
}