public class FrequencyBag<T>
{
	// TO DO: Instance Variables
	private FNode head;
	private boolean hasChanged = true;
	private int max;
	//Tracks the number of times add has been called
	private int total;
	/**
	 * Constructor
	 * Constructs an empty frequency bag.
	 */
	public FrequencyBag()
	{
		head = null;
	}
	
	/**
	 * Adds new entry into this frequency bag.
	 * @param aData the data to be added into this frequency bag.
	 */
	public void add(T aData)
	{
		//Add to the start to make add an O(1) operation
		if(!addhelper(head,aData))
		{
			hasChanged = true;
			FNode n =  new FNode(aData,head);
			head = n;
		}
		total++;
	}
	public boolean addhelper(FNode head, T data)
	{
		if(head == null)
		{
			//We haven't found the item in the list, return false
			return false;
		}
		if(head.getObject().equals(data))
		{
			head.add();
			return true;
		}
		return addhelper(head.getNext(),data);
	}
	
	/**
	 * Gets the number of occurrences of aData in this frequency bag.
	 * @param aData the data to be checked for its number of occurrences.
	 * @return the number of occurrences of aData in this frequency bag.
	 */
	public int getFrequencyOf(T aData)
	{
		return getFrequencyOfHelper(head,aData);
	}

	public int getFrequencyOfHelper(FNode<T> node,T data)
	{
		//If we've hit a null node, the object isn't in the list
		if(node == null)
		{
			return 0;
		}
		if(node.getObject().equals(data))
		{
			return node.getFrequency();
		}
		else
		{
			return getFrequencyOfHelper(node.getNext(),data);
		}
	}
	/**
	 * Gets the maximum number of occurrences in this frequency bag.
	 * @return the maximum number of occurrences of an entry in this
	 * frequency bag.
	 */
	public int getMaxFrequency()
	{
		if(hasChanged)
		{
			hasChanged = false;
			max = getMaxFrequencyHelper(head);
			return max;
		}
		else
		{
			return max;
		}
	}
	private int getMaxFrequencyHelper(FNode<T> node)
	{
		if(node == null) //Were at the end
			return 0;
		int nmax = getMaxFrequencyHelper(node.getNext());
		return node.getFrequency() > nmax?node.getFrequency():nmax;
	}
	
	/**
	 * Gets the probability of aData
	 * @param aData the specific data to get its probability.
	 * @return the probability of aData
	 */
	public double getProbabilityOf(T aData)
	{
		return getFrequencyOf(aData)/(total*1.0);
	}

	/**
	 * Empty this bag.
	 */
	public void clear()
	{
		head = null;
		hasChanged = true;
		total = 0;
	}
	
	/**
	 * Gets the number of entries in this bag.
	 * @return the number of entries in this bag.
	 */
	public int size()
	{ 
		return total;
	}
	public class FNode<T>
	{
		private T object = null;
		private int frequency = 1;
		private FNode next = null;

		public FNode()
		{
		}
		public FNode(T obj,FNode n)
		{
			object = obj;
			next = n;
		}
		public void setObject(T obj)
		{
			object = obj;
		}
		public T getObject()
		{
			return object;
		}
		public void add()
		{
			frequency++;
		}
		public int getFrequency()
		{
			return frequency;
		}
		public FNode getNext()
		{
			return next;
		}
		public void setNext(FNode n)
		{
			next = n;
		}
	}
}