public class BirdList {

	private Node head;
	
	public BirdList()
	{
		head = null;
	}
	
	// --- INSERT METHODS --- //
	public void insert(String n)
	{
		if (head == null) {
			insertFirst(n);
			return;
		}
		if (find(n)) {
			int pos = findIndex(n);
			int start = 0;
			Node ref = head;
			while (start < pos) {
				ref = ref.next;
				start++;
			}
			ref.frequency++;
		}
		else insertLast(n);
	}
	
	public void insertFirst(String n)
	{
		Node newNode = new Node(n);
		newNode.next = head;
		head = newNode;
	}
	
	public void insertLast(String n)
	{
		Node newNode = new Node(n);
		if (head == null)
			head = newNode;
		else if (head.next == null)
			head.next = newNode;
		else {
			Node ref = head;
			while (ref.next != null)
			{
				ref = ref.next;
			}
			ref.next = newNode;
		}
	}
	
	// --- Size Method --- //
	public int getSize()
	{
		Node ref = head;
		int size = 0;
		while (ref != null)
		{
			size++;
			ref = ref.next;
		}
		return size;
	}
	
	// --- FIND METHODS --- //
	public boolean find(String n) // Returns true if name is found in list
	{
		Node ref = head;
		while (ref != null)
		{
			if (ref.name.equals(n))
				return true;
			ref = ref.next;
		}
		return false;
	}
	
	public int findIndex(String n)
	{
		int index = -1;
		if (!find(n))
			return index;
		else {
			Node ref = head;
			index = 0;
			while (ref != null) {

				if (ref.name.equals(n))
					break;
				index ++;
				ref = ref.next;
			}
			return index;
		}
	}
	
	// --- SORT METHODS --- //
	public void sort()
	{
		for (Node ref = head; ref != null; ref = ref.next) {
			for (Node ref2 = ref.next; ref2 != null; ref2 = ref2.next) {
				if (ref.frequency < ref2.frequency) {
					String tempName = ref.name;
					int tempFreq = ref.frequency;
					ref.name = ref2.name;
					ref.frequency = ref2.frequency;
					ref2.name = tempName;
					ref2.frequency = tempFreq;
				}
			}
		}
	}
	public void remove(String n)
	{
		if (find(n))
		{
			Node ref = head;
			Node prev = head;
			while (!ref.name.equals(n)) {
				prev = ref;
				ref = ref.next;
			}
			if (ref == head)
				head = head.next;
			prev.next = ref.next;
		}
	}
	
	
	
	// --- PRINT METHODS --- ///
	public void printList()
	{
		Node ref = head;
		while (ref != null)
		{
			System.out.println(ref.name + ": " + ref.frequency);
			ref = ref.next;
		}
	}
	
	class Node {
		private String name;
		private int frequency;
		private Node next;

		public Node(String n) {
			this.name = n;
			this.frequency = 1;
			next = null;
		}
	}
}