#ifndef SLIST_H
#define SLIST_H

#include <cassert>

template<class T>
class Node
{
public:
    T data;
    Node<T> *next;
    Node() : data(T()), next(0) {}
    Node(const T &initdata) : data(initdata), next(0) {}
    Node(const T &initdata, Node<T> *p) : data(initdata), next(p) {}
};

template<class T>
class SList
{
protected:
    int m_nCount;
    Node<T> *m_pHead;

public:
    SList();
    SList(const T &initdata);
    ~SList();

public:
    int   IsEmpty() const;
    int   GetCount() const;
    int   InsertBefore(const int pos, const T data);
    int   InsertAfter(const int pos, const T data);
    int   AddHead(const T data);
    int   AddTail(const T data);
    void  RemoveAt(const int pos);
    void  RemoveHead();
    void  RemoveTail();
    void  RemoveAll();
    T&    GetTail();
    T     GetTail() const;
    T&    GetHead();
    T     GetHead() const;
    T&    GetAt(const int pos);
    T     GetAt(const int pos) const;
    void  SetAt(const int pos, T data);
    int   Find(const T data) const;
};



template<class T>
SList<T>::SList():m_nCount(0), m_pHead(0)
{
}

template<class T>
SList<T>::SList(const T &initdata):m_nCount(0), m_pHead(0)
{
    AddHead(initdata);
}

template<class T>
SList<T>::~SList()
{
    RemoveAll();
}

template<class T>
int SList<T>::IsEmpty() const
{
    return 0 == m_nCount;
}

template<class T>
int SList<T>::AddHead(const T data)
{
    Node<T> *pNewNode;

    pNewNode = new Node<T>;
    if (0 == pNewNode)
        return 0;

    pNewNode->data = data;
    pNewNode->next = m_pHead;

    m_pHead = pNewNode;
    ++m_nCount;

    return 1;
}

template<class T>
int SList<T>::AddTail(const T data)
{
    return InsertAfter(GetCount(), data);
}

// if success, return the position of the new node.
// if fail, return 0.
template<class T>
int SList<T>::InsertBefore(const int pos, const T data)
{
    int i;
    int nRetPos;
    Node<T> *pTmpNode1;
    Node<T> *pTmpNode2;
    Node<T> *pNewNode;

    pNewNode = new Node<T>;
    if (0 == pNewNode)
    {
        nRetPos = 0;
        return nRetPos;
    }

    pNewNode->data = data;

    // if the list is empty, replace the head node with the new node.
    if (0 == m_pHead)
    {
        pNewNode->next = 0;
        m_pHead = pNewNode;
        nRetPos = 1;
		m_nCount++;
        return nRetPos;
    }

    // is pos range valid?
    assert(1 <= pos && pos <= m_nCount);

    // insert before head node?
    if (1 == pos)
    {
        pNewNode->next = m_pHead;
        m_pHead = pNewNode;
        nRetPos = 1;
        m_nCount++;
		return nRetPos;
    }

    // if the list is not empty and is not inserted before head node,
    // seek to the pos of the list and insert the new node before it.
    pTmpNode1 = m_pHead;
    for (i = 1; i < pos; ++i)
    {
        pTmpNode2 = pTmpNode1;
        pTmpNode1 = pTmpNode1->next;
    }
    pNewNode->next = pTmpNode1;
    pTmpNode2->next = pNewNode;

    nRetPos = pos;
	m_nCount++;
	return nRetPos;
}

// if success, return the position of the new node.
// if fail, return 0.
template<class T>
int SList<T>::InsertAfter(const int pos, const T data)
{
    int i;
    int nRetPos;
    Node<T> *pTmpNode;
    Node<T> *pNewNode;

    pNewNode = new Node<T>;
    if (0 == pNewNode)
    {
        nRetPos = 0;
		return nRetPos;
    }

    pNewNode->data = data;

    // if the list is empty, replace the head node with the new node.
    if (0 == m_pHead)
    {
        pNewNode->next = 0;
        m_pHead = pNewNode;
        nRetPos = 1;
		m_nCount++;
		return nRetPos;
    }

    // is pos range valid?
    assert(1 <= pos && pos <= m_nCount);
	
    // if the list is not empty,
    // seek to the pos of the list and insert the new node after it.
    pTmpNode = m_pHead;
    for (i = 1; i < pos; ++i)
    {
        pTmpNode = pTmpNode->next;
    }
    pNewNode->next = pTmpNode->next;
    pTmpNode->next = pNewNode;

    nRetPos = pos + 1;
	m_nCount++;
	return nRetPos;

}

template<class T>
int SList<T>::GetCount() const
{
    return m_nCount;
}

template<class T>
void SList<T>::RemoveAt(const int pos)
{
    assert(1 <= pos && pos <= m_nCount);

    int i;
    Node<T> *pTmpNode1;
    Node<T> *pTmpNode2;

    pTmpNode1 = m_pHead;

    // head node?
    if (1 == pos)
    {
        m_pHead = m_pHead->next;
    }
	else
	{
		for (i = 1; i < pos; ++i)
		{
			// we will get the previous node of the target node after
			// the for loop finished, and it would be stored into pTmpNode2
			pTmpNode2 = pTmpNode1;
			pTmpNode1 = pTmpNode1->next;
		}
		pTmpNode2->next = pTmpNode1->next;

	}
	    	
	delete pTmpNode1;
    --m_nCount;
}

template<class T>
void SList<T>::RemoveHead()
{
    assert(0 != m_nCount);
    RemoveAt(1);
}

template<class T>
void SList<T>::RemoveTail()
{
    assert(0 != m_nCount);
    RemoveAt(m_nCount);
}

template<class T>
void SList<T>::RemoveAll()
{
    int i;
    //int m_nCount;
    Node<T> *pTmpNode;

    //m_nCount = m_nCount;
    for (i = 0; i < m_nCount; ++i)
    {
        pTmpNode = m_pHead->next;
        delete m_pHead;
        m_pHead = pTmpNode;
    }

    m_nCount = 0;
}

template<class T>
T& SList<T>::GetTail()
{
    assert(0 != m_nCount);

    int i;
    Node<T> *pTmpNode = m_pHead;

    for (i = 1; i < m_nCount; ++i)
    {
        pTmpNode = pTmpNode->next;
    }

    return pTmpNode->data;
}

template<class T>
T SList<T>::GetTail() const
{
    assert(0 != m_nCount);

    int i;
    Node<T> *pTmpNode = m_pHead;

    for (i = 1; i < m_nCount; ++i)
    {
        pTmpNode = pTmpNode->next;
    }

    return pTmpNode->data;
}

template<class T>
T& SList<T>::GetHead()
{
    assert(0 != m_nCount);
    return m_pHead->data;
}

template<class T>
T SList<T>::GetHead() const
{
    assert(0 != m_nCount);
    return m_pHead->data;
}

template<class T>
T& SList<T>::GetAt(const int pos)
{
    assert(1 <= pos && pos <= m_nCount);

    int i;
    Node<T> *pTmpNode = m_pHead;

    for (i = 1; i < pos; ++i)
    {
        pTmpNode = pTmpNode->next;
    }

    return pTmpNode->data;
}

template<class T>
T SList<T>::GetAt(const int pos) const
{
    assert(1 <= pos && pos <= m_nCount);

    int i;
    Node<T> *pTmpNode = m_pHead;

    for (i = 1; i < pos; ++i)
    {
        pTmpNode = pTmpNode->next;
    }

    return pTmpNode->data;
}

template<class T>
void SList<T>::SetAt(const int pos, T data)
{
    assert(1 <= pos && pos <= m_nCount);

    int i;
    Node<T> *pTmpNode = m_pHead;

    for (i = 1; i < pos; ++i)
    {
        pTmpNode = pTmpNode->next;
    }
    pTmpNode->data = data;
}

template<class T>
int SList<T>::Find(const T data) const
{
    int i;
    int m_nCount;
    Node<T> *pTmpNode = m_pHead;

    m_nCount = m_nCount;
    for (i = 0; i < m_nCount; ++i)
    {
        if (data == pTmpNode->data)
            return i + 1;
        pTmpNode = pTmpNode->next;
    }

    return 0;
}

#endif//SLIST_H