#ifndef __INSANE_LINKED_LIST_CLASS_HEADER__
#define __INSANE_LINKED_LIST_CLASS_HEADER__

template <class T>
class insaneNode
{
public:
	T		data;
	insaneNode<T>	*next;
	insaneNode<T>	*back;
	
	insaneNode()
	{
		next=back=NULL;
	}
	
	insaneNode(T d)
	{
		data=d;
		next=back=NULL;
	}
	
	T GetData()
	{
		return data;
	}

	void SetData(T d)
	{
		data=d;
	}
};

template <class T>
class insaneLinkedList
{
public:
	insaneLinkedList()
	{
		head=tail=spot=NULL;
		length=0;
		place=-1;
	}
	~insaneLinkedList()
	{
		MoveFirst();
		for(int i=0;i<length;i++)
		{
			Remove();
		}
	}
	
	void Insert(T data)
	{
		insaneNode<T> *p;
		p=new insaneNode<T>;
		
		p->SetData(data);
		p->next=NULL;
		p->back=NULL;
		
		if(spot==NULL)
		{
			head=tail=p;
		}
		else
		{
			if(spot->next)
			{
				spot->next->back=p;
				p->next=spot->next;
				spot->next=p;
				p->back=spot;
			}
			else
			{
				p->back=spot;
				spot->next=p;
				tail=p;
			}
		}
		
		spot=p;
		
		length++;
		place++;
	}
	
	insaneNode<T> *MoveFirst()
	{
		spot=head;
		place=0;
		return spot;
	}
	
	insaneNode<T> *MoveLast()
	{
		spot=tail;
		place=length-1;
		return spot;
	}
	
	insaneNode<T> *MoveNext()
	{
		if(spot->next)
		{
			spot=spot->next;
			place++;
		}
		return spot;
	}
	
	insaneNode<T> *MoveBack()
	{
		if(spot->back)
		{
			spot=spot->back;
			place--;
		}
		return spot;
	}
	
	insaneNode<T> *MoveTo(int who)
	{
		return FindX(who);
	}
	
	insaneNode<T> *This()
	{
		return spot;
	}
	
	insaneNode<T> *Find(T d)
	{
		if(MoveFirst())
		{
			do
			{
				if(This()->data==d)
				{
					spot=This();
					return spot;
				}
			} while(MoveNext()->next);
			if(This()->data==d)
			{
				spot=This();
				return spot;
			}
		}
		
		return NULL;
	}
	
	insaneNode<T> *FindX(int who)
	{
		if(length>0)
		{
			int p=place;

			if(p==who) return spot;
			if(p>who)
			{
				for(int i=0;i<(p-who);i++)
				{
					MoveBack();
				}
				return spot;
			}
			else
			{
				for(int i=0;i<(who-p);i++)
				{
					MoveNext();
				}
				return spot;
			}
		}
		
		return NULL;
	}
	
	void Remove()
	{
		if(spot->back)
		{
			spot->back->next=spot->next;
			if(spot->next)
			{
				spot->next->back=spot->back;
				spot=spot->next;
			}
			else
			{
				tail=spot->back;
				spot=spot->back;
			}
		}
		else
		{
			if(spot->next)
			{
				spot->next->back=NULL;
				head=spot->next;
				spot=spot->next;
			}
			else
			{
				head=tail=spot=NULL;
			}
		}
		
		length--;
	}
	
	int GetLength()
	{
		return length;
	}
	
	int GetPlace()
	{
		return place;
	}
private:
	insaneNode<T>	*head;
	insaneNode<T>	*tail;
	insaneNode<T>	*spot;					// [X MARKS THE SPOT! :]

	int		length;
	int		place;
};

#endif