#ifndef CHAIN_H
#define CHAIN_H

#include 
#include "Exception.h"

template
class  ChainNode;

template
class ChainIterator;

template
class Chain
{
    friend class ChainIterator;
public:
    Chain(){head = 0;}
    ~Chain();
    bool isEmpty() const { return head == 0;}
    int Length() const;
    bool Find(int k,T& x) const;
    int Search(const T& x) const;
    Chain& Delete(int pos,T& x);
    Chain& Insert(int pos,const T& x);
    Chain& add(const T& x);     //在链表的尾部添加一个元素
    void clear();                  //清楚链表中的元素
    T& get(int x);              //获取在x位置的元素
    void print();
private:
    ChainNode *head;
};

template
class ChainNode{
    friend class Chain;
    friend class ChainIterator;
private:
    T data;
    ChainNode *next;
};

/**链表遍历器**/
template
class ChainIterator{
public:
    T* initialize(const Chain& c){
        location = c.head;

        if(location)
            return &(location->data);
        else
            return 0;
    }

    T* Next(){
        location = location->next;
        if(location)
            return &(location->data);
        else
            return 0;
    }

private:
    ChainNode *location;
};

template
int Chain::Length() const
{
    ChainNode *current = head;

    int i  = 0;
    while(current){
        i++;
        current = current->next;
    }

    return i;
}

template
bool Chain::Find(int k, T &x) const
{
    ChainNode* current = head;
    int index = 1;

    while(index < k && current){
        current = current->next;
        index++;
    }

    if(current){
        x = current->data;
        return true;
    }

    return false;
}

template
int Chain::Search(const T &x) const
{
    ChainNode *current = head;
    int index = 1;

    while(current && current->data != x){
        current = current->next;
        index++;
    }

    if(current){
        return index;
    }

    return -1;
}

template
Chain& Chain::Delete(int pos, T &x)
{
    if(pos <= 0 || pos > Length())
        throw OutOfBounds();

    ChainNode* p = head;

    if(pos == 1){
        head = head->next;
    }else{
        ChainNode* q = head;

        for(int i = 1;i < pos-1 && q;i++)
            q = q->next;

        if(!q || !q->next)
            throw OutOfBounds();
        p = q->next;
        q->next = p->next;
    }

    x = p->data;
    delete p;

    return *this;
}

template
Chain& Chain::Insert(int pos, const T &x)   //在第pos个元素之后添加一个元素x
{
    if(pos < 0 || pos > Length())
        throw OutOfBounds();

    ChainNode* p = head;
    for(int i = 1;i < pos && p; i++)
        p = p->next;

    if(pos > 0 && !p)
        throw OutOfBounds();

    ChainNode* temp = new ChainNode();
     temp->data = x;
     if(pos){
         temp->next = p->next;
         p->next = temp;
     }else{
        temp->next = head;
        head = temp;
     }

    return *this;
}

template
void Chain::print()
{
    ChainNode* p = head;

    while(p){
        std::cout << p->data << "   ";
        p = p->next;
    }

    std::cout << std::endl;
}

template
Chain::~Chain()
{
    while(head){
        ChainNode* temp = head;
        head = head->next;
        delete temp;
    }

    head = 0;
}

template
Chain& Chain::add(const T &x)
{
    ChainNode *added = new ChainNode();
    added->data = x;
    added->next = 0;

    ChainNode *current = head;
    ChainNode *temp = current;

    while(current){
        temp = current;
        current = current->next;
    }

    if(temp){
        temp->next = added;
    }else{
        head = added;
    }

    return *this;
}

template
void Chain::clear()
{
    ChainNode *temp;

    while(head){
        temp = head->next;
        delete head;
        head = temp;
    }

    head = 0;
}

template
T& Chain::get(int x)
{
    if(x < 0)
        throw OutOfBounds();

    ChainNode *current = head;

    for(int i = 0; i < x &&  current; i++){
        current = current->next;
    }

    if(!current)
        throw OutOfBounds();

    return current->data;
}

#endif // CHAIN_H