//
// CList.hpp
// Lesson3
//
// Created by ShenJun on 2017/1/17.
// Copyright © 2017年 ShenJun. All rights reserved.
//

#ifndef CList_hpp
#define CList_hpp

#include <stdio.h>

template <class T> class CList
{
public:
CList() : m_pHead(NULL), m_pEnd(NULL), m_nSize(0){}
~CList(){ clear(); }
private:
struct Node
{
Node(const T& element) : pNext(NULL), pFront(NULL), element(element){}
Node *pNext;
Node *pFront;
T element;
};
public:
class Iterator
{
public:
Iterator() : pCurrent(NULL){}
Iterator(Node* pNode) : pCurrent(pNode){}
Iterator(Iterator& other) : pCurrent(other) {}

public:
Iterator& operator ++() // ++p
{
pCurrent = pCurrent->pNext;
return *this; // 当前对象
}
Iterator& operator --() // --p
{
pCurrent = pCurrent->pFront;
return *this;
}
bool operator ==(const Iterator& other)
{
return pCurrent == other.pCurrent;
}
bool operator !=(const Iterator& other)
{
return pCurrent != other.pCurrent;
}
Iterator& operator +=(int nOffset)
{
if(nOffset > 0)
{
while (nOffset-- && this->pCurrent != NULL) {
++(*this);
}
}
else
{
while (nOffset++ && this->pCurrent != NULL) {
--(*this);
}
}
}
Iterator& operator -=(int nOffset)
{
return *this += (-nOffset);
}
Iterator& operator +(int nOffset)
{
Iterator temp = *this;
return temp+=nOffset;
}
Iterator& operator -(int nOffset)
{
Iterator temp = *this;
return temp+=-nOffset;
}
Iterator operator=(const Iterator& other)
{
this->pCurrent = other.pCurrent;
return *this;
}
T& operator *() const
{
return pCurrent->element;
}
T* operator ->()
{
return &(pCurrent->element);
}
private:
Node* pCurrent;
friend class CList;
};
public:
Iterator begin()
{
return Iterator(m_pHead);
}
Iterator end()
{
return Iterator(NULL);
}
Iterator getLast()
{
return Iterator(m_pEnd);
}
// 从前面插入
void insert_front(const Iterator& other, const T& element)
{
Node* pNode = new Node(element);
if(other.pCurrent != m_pHead)
{
pNode->pFront = other.pCurrent->pFront;
pNode->pNext = other.pCurrent;
other.pCurrent->pFront->pNext= pNode;
other.pCurrent->pFront = pNode;
}
else
{
pNode->pFront = NULL;
pNode->pNext = other.pCurrent;
other.pCurrent->pFront = pNode;
m_pHead = pNode;
}
m_nSize++;
}
// 从后面插
void insert_back(const Iterator& other, const T& element)
{
Node* pNode = new Node(element);
if(other.pCurrent != m_pEnd)
{
pNode->pFront = other.pCurrent;
pNode->pNext = other.pCurrent->pNext;
other.pCurrent->pNext->pFront= pNode;
other.pCurrent->pNext = pNode;
}
else
{
pNode->pFront = other.pCurrent;
pNode->pNext = NULL;
other.pCurrent->pNext = pNode;
m_pEnd = pNode;
}
m_nSize++;
}
// 删除
Iterator erase(Iterator& other)
{
Iterator it(other);
++it;
if(other.pCurrent == m_pHead)
{
other.pCurrent = other.pCurrent->pNext;
m_pHead = other.pCurrent;
m_pHead->pFront = NULL;
}
else if(other.pCurrent == m_pEnd)
{
m_pEnd = m_pEnd->pFront;
m_pEnd->pNext = NULL;
}
else
{
other.pCurrent->pFront->pNext = other.pCurrent->pNext;
other.pCurrent->pNext->pFront = other.pCurrent->pFront;
}
delete other.pCurrent;
other.pCurrent = NULL;
m_nSize --;
return it;
}
public:
int size()
{
return m_nSize;
}
bool isEmpty()
{
return m_nSize == 0 ? true : false;
}
void push_back(const T& element)
{
Node* pNode = new Node(element);
if(m_pHead != NULL)
{
pNode->pFront = m_pEnd;
m_pEnd->pNext = pNode;
m_pEnd = pNode;
}
else
{
m_pHead = m_pEnd = pNode;
}
m_nSize++;
}
void push_front(const T& element)
{
Node* pNode = new Node(element);
if(m_pHead != NULL)
{
pNode->pNext = m_pHead;
m_pHead->pFront = pNode;
m_pHead = pNode;
}
else
{
m_pHead = m_pEnd = pNode;
}
m_nSize++;
}
T& pop()
{
T element;
if(m_pHead == NULL) return element;
Node* pNode = m_pHead;
element = pNode->element;
Node *pTmp = m_pHead;
pTmp = pTmp->pNext;
m_pHead = pTmp;
if(pTmp != NULL)
{
pTmp->pFront = NULL;
}
delete pNode;
return element;
}
void insertAt(int nIndex, const T& element)
{
Node* pNode = new Node(element);
if(m_pHead == NULL || nIndex == 0)
{
push_front(element);
return;
}
if(nIndex >= m_nSize)
{
push_back(element);
return;
}
Node* pTmp = m_pHead;
int nCount = 0;
while (nCount < nIndex) {
nCount++;
pTmp = pTmp->pNext;
}
// printf("inset tmp element : %d", pTmp->element);
pNode->pFront = pTmp->pFront;
pNode->pNext = pTmp;
pTmp->pFront->pNext = pNode;
pTmp->pFront = pNode;
m_nSize ++;
}
void eraseAt(int nIndex)
{
if(m_pHead == NULL) return;
if(nIndex >= m_nSize) return;
// 删除第一个节点 需要改变头指针的位置
if(nIndex == 0)
{
Node* pTmp = m_pHead;
// 只有一个节点
if(m_nSize == 1)
{
m_pHead = m_pEnd = NULL;
}
else
{
m_pHead = m_pHead->pNext;
m_pHead->pFront = NULL;
}
delete pTmp;
m_nSize--;
return;
}
// 删除最后一个节点 需要改变尾部指针的位置
if(nIndex == m_nSize - 1)
{
Node* pTmp = m_pEnd;
m_pEnd = m_pEnd->pFront;
m_pEnd->pNext = NULL;
m_nSize--;
delete pTmp;
return;
}
int nCount = 0;
Node* pTmp = m_pHead;
while (nCount < nIndex) {
pTmp = pTmp->pNext;
nCount++;
}
pTmp->pFront->pNext = pTmp->pNext;
pTmp->pNext->pFront = pTmp->pFront;
delete pTmp;
m_nSize--;
}
T getAt(int nIndex)
{
T element;
if(nIndex >= m_nSize) return element;
if(m_pHead == NULL) return element;
int nCount = 0;
Node* pTmp = m_pHead;
while(nCount < nIndex)
{
pTmp = pTmp->pNext;
nCount++;
}
if(pTmp == NULL)
{
printf("pTmp = NULL %d\n", nIndex);
}
else
{
element = pTmp->element;
}
return element;
}
void clear()
{
if(m_pHead == NULL) return;
Node* pNode = m_pHead;
while (pNode != NULL) {
Node* pTmp = pNode;
pNode = pNode->pNext;
delete pTmp;
}
m_pHead->pNext = NULL;
m_pEnd->pFront = NULL;
m_pHead = m_pEnd = NULL;

m_nSize = 0;
}
private:
Node *m_pHead;
Node *m_pEnd;
int m_nSize;


};

#endif /* CList_hpp */