#ifndef LIST
#define LIST
template<class Type>class List;

template<class Type>class ListNode
{
	friend class List<Type>;
    public:
		ListNode(Type d,ListNode<Type> *pos)
		{
			data =d;
			next=pos;
		}
		
	private:
		Type data;
		ListNode * next;
};

template<class Type> class List
{
    public:
		List()
		{		
			front=new ListNode<Type>(0,NULL);
			length=0;
		}
		~List()
		{		
			delete front; 
		}
		void Insert(Type a );
		void Delete();
		void empty()
		{
			while (length) Delete();
		}
		Type GetTop()
		{ 
			return front->next->data;
		}
		int Search(Type a,int low,int high);
		Type Find(int i);
		int length;
	private:
		ListNode<Type> *front;
		
};

template<class Type>void List<Type>::Insert(Type a)
{	
	ListNode<Type> *p=front;
	for(int j=0;j<length;j++)
	{
		p=p->next ;
	}
	p->next=new ListNode<Type>(a,NULL);
	length++;
	
}

template<class Type> void List<Type>::Delete()
{	
	ListNode<Type> *p=front->next;
	front->next=p->next;
	length--;
	delete p;
}

template<class Type> int List<Type>::Search ( Type a,int low,int high)
{

     int mid=-1;
	if(low<=high)
	{
		mid=(low+high)/2;
	
	if(Find(mid)<a)
		mid=Search(a,mid+1,high);
	else if(Find(mid)>a)
	       mid=Search(a,low,mid-1);

	}
	return mid;
}
template<class Type> Type List<Type>::Find(int i)
{
	if(i>length)
		return 0;
	ListNode<Type> *p=front;
	for(int j=0;j<i;j++)
	{
		p=p->next ;
	}
	return p->data ;
}
class TreeNode 
{
public :
	TreeNode(CString n)
	{
		name=n;
	}
	List<TreeNode*> list;
	CString name;
};
#endif