#ifndef CIRCULARCHAIN_H
#define CIRCULARCHAIN_H

#include "Exception.h"
#include 

using namespace std;

template
class Chain;

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

template
class Chain{
public:
    Chain(){
        head = new ChainNode();
        head->data = NULL;
        head->next = head;
    }

    ~Chain();
    int Length();
    bool isEmpty(){return head->next == head;}
    bool Find(int k,T& x) const;
    int Search(const T& x);
    Chain& Delete(int k,T& x);
    Chain& Insert(int k,const T& x);
    void print();
private:
    ChainNode* head;
};

template
Chain::~Chain()
{
    if(head->next == head)
        return;

    ChainNode* current = head->next;

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

template
int Chain::Length()
{
    int index = 0;
    ChainNode *current = head;
    while(current->next !=  head){
        index++;
        current = current->next;
    }

    return index;
}

template
bool Chain::Find(int k, T &x) const
{
    if(k < 1)
        throw OutOfBounds();

    if(head->next == head)
        throw OutOfBounds();

   ChainNode* current = head->next;
    for(int i = 1;i < k && current  != head; i++){
        current = current->next;
    }

    if(current == head)
        return false;

    x = current->data;
    return true;
}

template
int Chain::Search(const T &x)
{
    if(head->next == head)
        return -1;

    ChainNode* current = head->next;

    int index = 1;

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

    if(current == head)
       return -1;

    return index;
}

template
Chain& Chain::Delete(int k, T &x)
{
    if(k < 1 || head->next == head)
        throw OutOfBounds();

    ChainNode* p = head->next;

    ChainNode* q = head;

    for(int i = 1;i < k && p != head; i++){
        q = p;
        p = p->next;
    }

    if(p == head)
        throw OutOfBounds();

    q->next = p->next;
    x = p->data;

    delete p;

    return *this;
}

template
Chain& Chain::Insert(int k, const T &x)
{
    if(k < 0)
            throw OutOfBounds();

        if(k > 0 && head->next == head)
            throw OutOfBounds();

        ChainNode* temp = new ChainNode();
        temp->data = x;

        ChainNode* p = head;

        int i;
        for(i = 0;i < k && p->next != head;i++){
            p = p->next;
        }

        if(i < k-1)
            throw OutOfBounds();

        if(k == 0){
            temp->next = head->next;
            head->next = temp;
        }else{
            temp->next = p->next;
            p->next = temp;
        }

        return *this;
}

template
void Chain::print()
{
    if(head->next == head)
        return;

    ChainNode* current = head->next;
    while(current != head){
        std::cout << current->data << " ";
        current = current->next;
    }

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

#endif // CIRCULARCHAIN_H