Inital commitHEADmaster

1 files changed, 168 insertions, 0 deletions

diff --git a/projects/project1_frequencyBag/FrequencyBag.java b/projects/project1_frequencyBag/FrequencyBag.java
new file mode 100644
index 0000000..3545ff9
--- /dev/null
+++ b/projects/project1_frequencyBag/FrequencyBag.java
@@ -0,0 +1,168 @@
+
+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;
+		}
+	}
+}