#ifndef LIST_H
#define LIST_H

#include <iostream>
#include <string>
#include <cstdlib>
#include <ctime>

#include "Node.h"

using namespace std ;

template <typename _type>
class List
{
public:
	List () ;
	~List() ;

	bool isEmpty () const ;

	 void InsertAtEnd () ;
	 void InsertAtBegin () ;
	 void RemoveFromFirst () ;
	 void RemoveFromLast () ;
	 void InsertAt (_type ) ;
	 void RemoveAt (_type ) ;
	 void Sort () ;
	 void print () ;

	

private:
	Node<_type> *first_ptr ;
	Node<_type> *last_ptr ;
	
	// function 
	Node<_type> GetNode () ;
	
};



template <typename _type>
List<_type>::List ()
{
	first_ptr = 0 ;
	last_ptr = 0 ;
}

template <typename _type>
List<_type>::~List ()
{
	Node<_type> *temp , *ptr = first_ptr ;
	if (!isEmpty())
	{
		while(ptr)
		{
			temp = ptr ; 
			ptr = ptr->next ;

			delete temp ;
		}
	}
}

template <typename _type>
bool List<_type>::isEmpty() const 
{
	if (first_ptr == 0 )
	{
		return true ;
	}

	return false ;
}


template <typename _type>
Node<_type> List<_type>::GetNode() 
{
	Node<_type> node (0) ;

	node.data = 1  + rand() % 100 ;
	node.next = 0 ;

	return node ;
}



template <typename _type>
void List<_type>::InsertAtEnd() 
{
	
	if ( isEmpty() )
	{
		srand(time(0)) ;
		Node<_type> *_new = new Node<_type>(0) ;

		_new->data = 1 + rand() % 100 ;
		_new->next = 0 ;


		first_ptr = _new ;
		last_ptr = _new ;
	} 
	else
	{
		Node<_type> *_new  = new Node<_type>(0);
		_new->data = 1 + rand() % 100  ;
		_new->next = 0 ;

		last_ptr->next = _new ;
		last_ptr = last_ptr->next ; 
	}

}

template <typename _type> 
void List<_type>::print() 
{
	if (isEmpty())
	{
		cout << "List is Empty !!! " << endl ;
	}
	else
	{
		Node<_type> *p = first_ptr;

		while (p != 0)
		{
			cout << p->GetData() << endl ;
			p = p->next ;
		}
	}
}


template <typename _type>
void List<_type>::InsertAtBegin() 
{
	
	if ( isEmpty())
	{
		srand(time(0)) ;
		Node<_type> *ptr = new Node<_type> (0) ;

		ptr->data = 1 + rand() % 100 ;
		ptr->next = 0 ;

		first_ptr = ptr ;
		last_ptr = ptr ;
	} 
	else
	{
		Node<_type> *ptr = new Node<_type> (0) ;

		ptr->data = 1 + rand() % 100 ;
		ptr->next = first_ptr ;

		first_ptr = ptr ;

	}


}

template <typename _type> 
void List<_type>::RemoveFromFirst()
{
	if (isEmpty())
	{
		cout << "List is Empty !!! " << endl ;
	}
	else
	{
		
		
		if ( first_ptr == last_ptr )
		{
			first_ptr = last_ptr = 0 ;
		} 
		else
		{
			Node<_type> *p = first_ptr ;

			first_ptr = first_ptr->next ;

			delete p  ;
		}

		
	}
}

template <typename _type>
void List<_type>::RemoveFromLast() 
{
	Node<_type> *temp = last_ptr ;
	Node<_type> *ptr = first_ptr ;
	if ( first_ptr == last_ptr)
	{
		first_ptr = last_ptr = 0 ;
	} 
	else
	{
		Node<_type> *temp = last_ptr ;
		Node<_type> *ptr = first_ptr ;
		
		while (ptr->next != last_ptr )
		{
			ptr = ptr->next ;
		}

		
		
		last_ptr = ptr ;
		last_ptr->next = 0 ;

	}


	delete temp ;
}


template <typename _type>
void List<_type>::InsertAt( _type  _value) 
{
	srand(time(0)) ;
	Node<_type> *ptr = first_ptr ;
	Node<_type> *temp = new Node<_type> (0) ;

	temp->data = 1 + rand() % 100 ;
	temp->next = 0 ;

	while (ptr->GetData() != _value )
	{
		ptr = ptr->next ;
	}

	temp->next = ptr->next ;
	ptr->next = temp ;


}


template <typename _type>
void List<_type>::RemoveAt(_type _value ) 
{
	if (isEmpty())
	{
		cout << " List is Empty !!! " << endl ;
	} 
	else
	{
		if (first_ptr == last_ptr )
		{
			first_ptr = last_ptr = 0 ;
		} 
		else
		{
			
			if ( first_ptr->GetData() == _value)
			{
				RemoveFromFirst() ;
			}
			else
			{
				Node<_type> *ptr = first_ptr ;
				Node<_type> *temp = 0 ;
				while (ptr->next->GetData () != _value ) 
				{
					ptr = ptr->next ;

				}

				temp = ptr->next ;

				ptr->next = temp->next ;

				delete temp ;
			}

		}
	}


}



template <typename _type>
void List<_type>::Sort() 
{
	if (isEmpty())
	{
		cout << "List is Empty !!! " << endl ;
	}
	else
	{
		Node<_type> *ptr1 , *ptr2;
		_type temp ;
		for (ptr1 = first_ptr ; ptr1->next != 0 ; ptr1 = ptr1->next )
		{
			for (ptr2 = ptr1->next ; ptr2 != 0 ; ptr2 = ptr2->next)
			{
				if (ptr1->GetData() > ptr2->GetData())
				{
					temp = ptr1->GetData() ; 
					ptr1->data = ptr2->data ;
					ptr2->data  = temp ;
				}
			}
		}
	}

}

#endif