package project_1;
public class LinkedList<T>  {

	private Node<T> head=null;
	private int size;

	public void print(){
		if(head==null)
			System.out.println("No Nodes");
		else{
			Node<T> pos= head;
			while(pos!=null){
				System.out.println(pos.toString());
				pos=pos.getNext();
			}
		}
	}
	public void clearList(){
		this.head=null;
		this.size=0;
	}

	public boolean add(T data){
		Node<T> newNode = new Node<>(data);
		Node<T> pos=head;
		if(head==null){
			head=newNode;
			++size;
			return true;
		}
		while(pos.getNext()!=null){
			pos=pos.getNext();
		}

		pos.setNext(newNode);
		++size;
		return true;

	}

	public boolean addInsertion(T data){
		Node<T> newNode = new Node<>(data);
		Node<T> pos=head;
		if(head==null){
			head=newNode;
			++size;
			return true;
		}

		if(pos.compare(newNode)>0){
			newNode.setNext(head);
			head=newNode;
			++size;
			return true;
		}

		while(pos.getNext()!=null && pos.getNext().compare(newNode)<0)
			pos=pos.getNext();

		newNode.setNext(pos.getNext());
		pos.setNext(newNode);

		++size;
		return true;


	}
	public boolean addInsertionTime(LinkedList<Course>list,Course data){
		Node<Course> newNode = new Node<>(data);
		Node<Course> pos= list.getHead();
		if(pos==null){
			list.head = newNode;
			++size;
			return true;
		}

		if(pos.getData().getStartTime().compareTo(newNode.getData().getStartTime())>0){
			newNode.setNext(list.head);
			list.head=newNode;
			++size;
			return true;
		}

		while(pos.getNext()!=null && pos.getData().getStartTime().compareTo(newNode.getData().getStartTime())<0)
			pos=pos.getNext();

		newNode.setNext(pos.getNext());
		pos.setNext(newNode);

		++size;
		return true;


	}
	public boolean add(T data,int index){
		Node<T> newNode = new Node<>(data);
		Node<T> pos=head;
		if(index <0 || index > size)
			return false;

		if(index==0){
			++size;
			newNode.setNext(head);
			head=newNode; 
			return true;

		}
		for(int i=0;i<index-1;++i){
			pos=pos.getNext();
		}
		newNode.setNext(pos.getNext());
		pos.setNext(newNode);
		++size;
		return true;

	}

	public boolean delete(int index){
		if(index <0 || index > size)
			return false;
		Node<T> pos=head;
		if(index==0){
			--size;
			head=head.getNext();
			return true;
		}
		for(int i=0;i<index-1;++i){
			pos=pos.getNext();
		}
		--size;
		pos.setNext(pos.getNext().getNext());
		return true;

	}

	public boolean deleteData(T data){

		int index = getIndex(data);
		if(index==-1)
			return false;
		Node<T> pos=head;
		if(index==0){
			--size;
			head=head.getNext();
			return true;
		}
		for(int i=0;i<index-1;++i){
			pos=pos.getNext();
		}
		--size;
		pos.setNext(pos.getNext().getNext());
		return true;


	}

	public int getIndex(T data){
		Node<T> pos=head;
		int index=0;

		while(pos!=null){

			if(pos.equal(data)){
				return index;
			}

			pos=pos.getNext();
			++index;

		}
		return -1;
	}


	public T getIndexData(int index){
		if(index<0 || index>=size)
			return null;
		Node<T> pos= head;
		if(index==0){
			return pos.getData();
		}
		for(int i=0;i<index;++i){
			pos=pos.getNext();
		}
		return pos.getData();
	}


	public static void radixSortID(LinkedList<Student> list){
		LinkedList<Student> [] sortedList = new LinkedList[10];

		for (int i = 0; i < sortedList.length; i++) {
			sortedList[i] = new LinkedList<Student>();
		}

		int maxDigit = noOfMaxDigit(list);
		int index=0,tempValue,m=1;

		for(int counter=1;counter<=maxDigit;++counter){

			for(int i=0;i<sortedList.length;++i){
				sortedList[i].clearList();
			}
			for(int i=0;i<list.getSize();++i){

				tempValue =list.getIndexData(i).getId() % (int)Math.pow(10, counter);
				index=tempValue/ (int)(m*Math.pow(10, counter-1));


				sortedList[index].add(list.getIndexData(i));


			}

			list.clearList();

			for(int i=0;i<sortedList.length;++i){
				for(int j=0;j<sortedList[i].getSize();++j){

					list.add(sortedList[i].getIndexData(j));
				}
			}

		}

	}

	public static void radixSortCourses(LinkedList<Course> list){
		LinkedList<Course> [] sortedList = new LinkedList[10];

		for (int i = 0; i < sortedList.length; i++) {
			sortedList[i] = new LinkedList<Course>();
		}

		int maxDigit = noOfMaxDigitYear(list);
		int index=0,tempValue,m=1;

		for(int counter=1;counter<=maxDigit;++counter){

			for(int i=0;i<sortedList.length;++i){
				sortedList[i].clearList();
			}
			for(int i=0;i<list.getSize();++i){



				tempValue = list.getIndexData(i).getYear() % (int)Math.pow(10, counter);
				index=tempValue/ (int)(m*Math.pow(10, counter-1));


				sortedList[index].add(list.getIndexData(i));


			}

			list.clearList();

			for(int i=0;i<sortedList.length;++i){
				for(int j=0;j<sortedList[i].getSize();++j){

					list.add(sortedList[i].getIndexData(j));
				}
			}

		}

	}

	public  static int noOfMaxDigit(LinkedList<Student> a){
		int maxDigit = 0;
		int digits;

		for(int i=0;i<a.getSize();++i){
			digits=noOfDigits(a.getIndexData(i).getId());

			if(digits>maxDigit)
				maxDigit = digits;
		}
		return maxDigit;
	}
	public static int noOfMaxDigitYear(LinkedList<Course> a){
		int maxDigit = 0;
		int digits;

		for(int i=0;i<a.getSize();++i){

			digits=noOfDigits(a.getIndexData(i).getYear());

			if(digits>maxDigit)
				maxDigit = digits;
		}
		return maxDigit;
	}

	private  static int noOfDigits(int x){
		if(x<10)
			return 1;
		else
			return 1+noOfDigits(x/10);
	}

	public LinkedList<T> merge(LinkedList<T> list1,LinkedList<T> list2){
		LinkedList<T> finalList = new LinkedList<>();

		Node<T>pos1 = list1.getHead();
		Node<T> pos2 = list2.getHead();

		while(pos1 !=null && pos2 != null){

			if(compare(pos1, pos2) < 0){
				finalList.add(pos1.getData());
				pos1 = pos1.getNext();

			}

			else if(compare(pos1, pos2) > 0){
				finalList.add(pos2.getData());
				pos2 = pos2.getNext();
			}

			else {
				finalList.add(pos1.getData());
				pos1 = pos1.getNext();
				pos2 = pos2.getNext();
			}
		}

		if(pos1 != null){
			while(pos1!=null){
				finalList.add(pos1.getData());
				pos1 = pos1.getNext();
			}
			return finalList;
		}
		else if(pos2 != null){
			while(pos2 !=null){
				finalList.add(pos2.getData());
				pos2 = pos2.getNext();
			}
			return finalList;
		}
		else{
			return finalList;
		}


	}

	private int compare(Node<T> data1,Node<T> data2){
		if(data1.getData() instanceof Student && data2.getData() instanceof Student){
			
			return ((Student)data1.getData()).compareTo((Student)data2.getData());
		}
		if(data1.getData() instanceof Course && data2.getData() instanceof Course){
	
			return ((Course)data1.getData()).compareTo((Course)data2.getData());
		}
		return -12222;
	}
	
	
	public void removeDuplicate(LinkedList<T> list){
		Node<T> pos= list.getHead();
		while(pos !=null && pos.getNext()!=null ){
			if(pos.getData() == pos.getNext().getData()){
				list.delete(getIndex(pos.getNext().getData()));
				
			}
			pos=pos.getNext();
		}
	}
	
	
	public boolean isEmpty(){
		return head==null;
	}
	public Node<T> getHead() {
		return head;
	}

	public int getSize() {
		return size;
	}





}
