package Week1;
import java.util.HashSet;

/**
 * @author Mark Knichel, The Dining Philosophers, University of Pennsylvania
 *
 * Dining Philosphers' Weekly Question, Week 1
 * 
 * This class has 2 static methods, both for removing duplicates
 * from an array of integers.  The only difference is that one 
 * method uses extra storage to do the removal process, while
 * the other does not use extra storage, but will take longer
 * to run.  There is often a tradeoff between memory used and
 * running time that you should consider when designing algorithms.
 */
public class RemoveDuplicates {
	/**
	 * This function uses extra space (a Hash table) to save time
	 * when removing duplicates.  For more on hash tables, visit
	 * (Wikipedia page)
	 * 
	 * @param array the array to remove duplicates from
	 * @throws NullPointerException - if the argument array is null
	 * @return an array with the same elements as the argument but with all duplicates removed
	 */
	public static int[] removeDuplicates1(int[] array) {
		if(array == null)
			throw new NullPointerException("RemoveDuplicates: Array cannot be null");
		HashSet<Integer> uniqueElements = new HashSet<Integer>();
		
		for(int i : array)
			uniqueElements.add(i);
		
		int[] arrayNoDuplicates = new int[uniqueElements.size()];
		int index = 0;
		for(Integer i : uniqueElements)
			arrayNoDuplicates[index++] = i;
		
		return arrayNoDuplicates;
	}

	/**
	 * This function does not use any extra memory (i.e. a hash table) to remove the duplicates
	 * but it does run a little slower because you have to sort the array.
	 * First the method counts up how many unique elements there are.  Then it creates the
	 * return array with that size.  Then the method loops through the original array.  If 
	 * the item is not a duplicate, add that item to the return array.  Else keep looping.
	 * j keeps track of what index the new non-duplicate element should be placed into
	 * the return array.
	 * 
	 * @param array the array to remove duplicates from
	 * @throws NullPointerException - if the argument array is null
	 * @return an array with the same elements as the argument but with all duplicates removed
	 */
	public static int[] removeDuplicates2(int[] array) {
		if(array == null)
			throw new NullPointerException("RemoveDuplicates: Array cannot be null");
	
		java.util.Arrays.sort(array);
		int uniqueElems = 1;
		for(int i = 1; i < array.length; i++) {
			if(array[i] != array[i-1])
				uniqueElems++;
		}
		
		int[] arrayNoDuplicates = new int[uniqueElems];
		arrayNoDuplicates[0] = array[0];
		int j = 1;
		
		for(int i = 1; i < array.length; i++) {
			if(array[i] != array[i-1])
				arrayNoDuplicates[j++] = array[i];
		}
		
		return arrayNoDuplicates;
	}
}