package AssignmentThree;

import java.util.Arrays;

public class SinglyLinkedList
{
	public SinglyLinkedList()
	{
		mFront = null;
	}

	public void appendFront(String word)
	{
		Node newNode = new Node(word);
		newNode.mNext = mFront;
		mFront = newNode;
	}

	public void appendRear(String word)
	{
		Node newNode = new Node(word);

		if(mFront == null) mFront = newNode;
		else
		{
			Node current = mFront;
			while(current.mNext != null) current = current.mNext;

			current.mNext = newNode;
		}
	}

	public void insertBefore(String marker, String word)
	{
		Node newNode = new Node(word);

		Node previous = null, current = mFront;

		while(current != null)
		{
			if(current.mWord.equals(marker))
			{
				if(previous == null) appendFront(word);
				else
				{
					newNode.mNext = previous.mNext;
					previous.mNext = newNode;
				}
				break;
			}

			previous = current;
			current = current.mNext;
		}
	}

	public void insertAfter(String marker, String word)
	{
		Node newNode = new Node(word);

		Node current = mFront;

		while(current != null)
		{
			if(current.mWord.equals(marker))
			{
				newNode.mNext = current.mNext;
				current.mNext = newNode;
				break;
			}
			current = current.mNext;
		}
	}

	public boolean isPresent(String word)
	{
		Node current = mFront;

		while(current != null)
		{
			if(current.mWord.equals(word)) return true;
			current = current.mNext;
		}

		return false;
	}

	public void remove(String word)
	{
		Node previous = null, current = mFront;

		while(current != null)
		{
			if(current.mWord.equals(word))
			{
				if(current == mFront)
				{
					mFront = mFront.mNext;
				}
				else
				{
					previous.mNext = current.mNext;
				}
				break;
			}
			else
			{
				previous = current;
				current = current.mNext;
			}
		}
	}

	public void print()
	{
		System.out.println("\nUnsorted List");

		Node current = mFront;
		while(current != null)
		{
			System.out.print(current.mWord + " ");
			current = current.mNext;
		}

		System.out.println();
	}

	public void sortAndPrint()
	{
		System.out.println("\nSorted List");

		int count = getCount();
		if(count == 0) return;

		String[] words = new String[count];
		Node current = mFront;
		int index = 0;

		while(current != null)
		{
			words[index++] = current.mWord;
			current = current.mNext;
		}

		Arrays.sort(words);

		for(String word : words) System.out.print(word + " ");
		System.out.println();
	}

	private int getCount()
	{
		int count = 0;
		Node current = mFront;

		while(current != null)
		{
			++count;
			current =current.mNext;
		}

		return count;
	}

	private class Node
	{
		public Node(String word)
		{
			mWord = word;
			mNext = null;
		}

		private String mWord;
		private Node mNext;
	}

	private Node mFront;

}