package algs11;

import java.util.Arrays;
import stdlib.*;

/**
 * This is a skeleton file for your homework. Edit the sections marked TODO. You
 * may also edit the function "main" to test your code.
 *
 * You must not change the declaration of any method. This will be true of every
 * skeleton file I give you.
 *
 * For example, you will get zero points if you change the line
 * 
 * <pre>
 *     public static double minValue (double[] list) {
 * </pre>
 * 
 * to something like
 * 
 * <pre>
 *     public static void minValue (double[] list) {
 * </pre>
 * 
 * or
 * 
 * <pre>
 *     public static double minValue (double[] list, int i) {
 * </pre>
 * 
 * Each of the functions below is meant to be SELF CONTAINED. This means that
 * you should use no other functions or classes. You should not use any HashSets
 * or ArrayLists, or anything else! In addition, each of your functions should
 * go through the argument array at most once. The only exception to this
 * removeDuplicates, which is allowed to call numUnique and then go through the
 * array once after that.
 */
public class MyFirstHomeworkFor300PartTwo {

	/**
	 * allSame returns true if all of the elements in list have the same value.
	 * allSame returns false if any two elements in list have different values. The
	 * array may be empty and it may contain duplicate values.
	 *
	 * Your solution should contain at most one loop. You may not use recursion.
	 * Your solution must not call any other functions. Here are some examples
	 * (using "==" informally):
	 *
	 * <pre>
	 *     true  == allSame(new double[] { })
	 *     true  == allSame(new double[] { 11 })
	 *     true  == allSame(new double[] { 11, 11, 11, 11 })
	 *     false == allSame(new double[] { 11, 11, 11, 22 })
	 *     false == allSame(new double[] { 11, 11, 22, 11 })
	 *     true  == allSame(new double[] { 22, 22, 22, 22 })
	 * </pre>
	 */
	public static boolean allSame(double[] list) {
		return StdRandom.bernoulli(); //TODO: fix this
	}

	/**
	 * numUnique returns the number of unique values in a sorted array of doubles.
	 * The array may be empty and it may contain duplicate values. Assume that the
	 * list array is sorted.
	 *
	 * Your solution should contain at most one loop. You may not use recursion.
	 * Your solution must not call any other functions. Here are some examples
	 * (using "==" informally):
	 *
	 * <pre>
	 *     0 == numUnique(new double[] { })
	 *     1 == numUnique(new double[] { 11 })
	 *     1 == numUnique(new double[] { 11, 11, 11, 11 })
	 *     8 == numUnique(new double[] { 11, 11, 11, 11, 22, 33, 44, 44, 44, 44, 44, 55, 55, 66, 77, 88, 88 })
	 *     8 == numUnique(new double[] { 11, 22, 33, 44, 44, 44, 44, 44, 55, 55, 66, 77, 88 })
	 * </pre>
	 */
	public static int numUnique(double[] list) {
		return StdRandom.uniform (100); //TODO: fix this
	}

	/**
	 * removeDuplicates returns a new array containing the unique values in the
	 * sorted argument array, in the same order that they were found in the original
	 * array. There should not be any extra space in the array --- there should be
	 * exactly one space for each unique element (Hint: numUnique tells you how big
	 * the array should be).
	 * 
	 * Assume that the list array is sorted, as you did for numUnique.
	 *
	 * Your solution should contain at most one loop. You may not use recursion.
	 * Your solution must not call any other functions, except numUnique. Here are
	 * some examples (using "==" informally):
	 *
	 * <pre>
	 *   new double[] { }
	 *     == removeDuplicates(new double[] { })
	 *   new double[] { 11 }
	 *     == removeDuplicates(new double[] { 11 })
	 *     == removeDuplicates(new double[] { 11, 11, 11, 11 })
	 *   new double[] { 11, 22, 33, 44, 55, 66, 77, 88 }
	 *     == removeDuplicates(new double[] { 11, 11, 11, 11, 22, 33, 44, 44, 44, 44, 44, 55, 55, 66, 77, 88, 88 })
	 *     == removeDuplicates(new double[] { 11, 22, 33, 44, 44, 44, 44, 44, 55, 55, 66, 77, 88 })
	 * </pre>
	 */
	public static double[] removeDuplicates(double[] list) {
		int resultLength = numUnique(list);
		double[] result = new double[resultLength];
		// TODO: fix this
		return result;
	}

	/*
	 * A main function for debugging -- change the name to "main" to run it (and
	 * rename the existing main method to something else). Change the test as
	 * appropriate.
	 */
	public static void main2(String[] args) {
		Trace.drawStepsOfMethod("removeDuplicates");
		Trace.run();
		testRemoveDuplicates("11 21 31 41", "11 21 31 41");
		testRemoveDuplicates("11 21", "11 11 21");
	}

	/**
	 * A test program, using private helper functions. See below. To make typing
	 * tests a little easier, I've written a function to convert strings to arrays.
	 * See below.
	 */
	public static void main(String[] args) {
		testAllSame(true, "11 11 11 11");
		testAllSame(true, "5 5 5");
		testAllSame(false, "11 5 11 11");
		testAllSame(false, "11 11 5 11");
		testAllSame(false, "11 11 11 5");
		testAllSame(false, "5 11 11 11");
		testAllSame(false, "11 5 5 11 11");
		testAllSame(false, "11 11 5 5 11");
		testAllSame(false, "11 11 5 11 5");
		testAllSame(false, "5 5 11 11 11");
		testAllSame(false, "11 11 11 5 5");
		testAllSame(true, "11");
		testAllSame(true, "2");
		testAllSame(true, "");

		// for numUnique: array must be sorted
		testNumUnique(4, "11 21 21 21 31 41 41 41 41");
		testNumUnique(1, "11 11 11 11");
		testNumUnique(4, "11 21 31 41");
		testNumUnique(4, "11 11 11 21 31 31 31 31 41");
		testNumUnique(4, "11 11 21 21 21 31 31 41 41 41 41");
		testNumUnique(8, "11 11 11 11 21 31 41 41 41 41 41 51 51 61 71 81 81");
		testNumUnique(8, "11 21 31 41 41 41 41 41 51 51 61 71 81");
		testNumUnique(7, "11 11 11 11 21 31 41 41 41 41 41 51 51 61 71");
		testNumUnique(7, "11 21 31 41 41 41 41 41 51 51 61 71");
		testNumUnique(8, "-81 -81 -81 -81 -71 -61 -51 -51 -51 -51 -41 -41 -31 -21 -11 -11 -11");
		testNumUnique(3, "-11 -11 -11 0 0 11 11 11");
		testNumUnique(2, "0 11 11 11");
		testNumUnique(2, "-Infinity 11 11 11");
		testNumUnique(2, "11 11 11 Infinity");
		testNumUnique(1, "11 11");
		testNumUnique(1, "11");
		testNumUnique(0, "");

		// for removeDuplicates: array must be sorted
		testRemoveDuplicates("11", "11 11 11 11");
		testRemoveDuplicates("11 21", "11 11 21");
		testRemoveDuplicates("11 21 31 41", "11 21 31 41");
		testRemoveDuplicates("11 21 31 41", "11 11 11 21 31 31 31 31 41");
		testRemoveDuplicates("11 21 31 41", "11 21 21 21 31 41 41 41 41");
		testRemoveDuplicates("11 21 31 41", "11 11 21 21 21 31 31 41 41 41 41");
		testRemoveDuplicates("11 21 31 41 51 61 71 81", "11 11 11 11 21 31 41 41 41 41 41 51 51 61 71 81 81");
		testRemoveDuplicates("11 21 31 41 51 61 71 81", "11 21 31 41 41 41 41 41 51 51 61 71 81");
		testRemoveDuplicates("11 21 31 41 51 61 71", "11 11 11 11 21 31 41 41 41 41 41 51 51 61 71");
		testRemoveDuplicates("11 21 31 41 51 61 71", "11 21 31 41 41 41 41 41 51 51 61 71");
		testRemoveDuplicates("-81 -71 -61 -51 -41 -31 -21 -11", "-81 -81 -81 -81 -71 -61 -51 -51 -51 -51 -41 -41 -31 -21 -11 -11 -11");
		testRemoveDuplicates("-11 0 11", "-11 -11 -11 0 0 11 11 11");
		testRemoveDuplicates("0 11", "0 11 11 11");
		testRemoveDuplicates("-Infinity 11", "-Infinity 11 11 11");
		testRemoveDuplicates("Infinity 11", "Infinity 11 11 11");
		testRemoveDuplicates("11", "11 11");
		testRemoveDuplicates("11", "11");
		testRemoveDuplicates("", "");
		StdOut.println("Finished tests");
	}

	private static void testAllSame(boolean expected, String list) {
		double[] aList = doublesFromString(list);
		boolean actual = allSame(aList);
		if (!Arrays.equals(aList, doublesFromString(list))) {
			StdOut.format("Failed allSame([%s]): Array modified\n", list);
		}
		if (expected != actual) {
			StdOut.format("Failed allSame([%s]): Expecting (%b) Actual (%b)\n", list, expected, actual);
		}
	}

	private static void testNumUnique(int expected, String list) {
		double[] aList = doublesFromString(list);
		int actual = numUnique(aList);
		if (!Arrays.equals(aList, doublesFromString(list))) {
			StdOut.format("Failed numUnique([%s]): Array modified\n", list);
		}
		if (expected != actual) {
			StdOut.format("Failed numUnique([%s]): Expecting (%d) Actual (%d)\n", list, expected, actual);
		}
	}

	private static void testRemoveDuplicates(String expected, String list) {
		double[] aList = doublesFromString(list);
		double[] actual = removeDuplicates(aList);
		if (!Arrays.equals(aList, doublesFromString(list))) {
			StdOut.format("Failed removeDuplicates([%s]): Array modified\n", list);
		}
		double[] aExpected = doublesFromString(expected);
		// != does not do what we want on arrays
		if (!Arrays.equals(aExpected, actual)) {
			StdOut.format("Failed removeDuplicates([%s]): Expecting (%s) Actual (%s)\n", list,
					Arrays.toString(aExpected), Arrays.toString(actual));
		}
	}

	/* A utility function to create an array of doubles from a string. */
	// The string should include a list of numbers, separated by single spaces.
	private static double[] doublesFromString(String s) {
		if ("".equals(s))
			return new double[0]; // empty array is a special case
		String[] nums = s.split(" ");
		double[] result = new double[nums.length];
		for (int i = nums.length - 1; i >= 0; i--) {
			try {
				result[i] = Double.parseDouble(nums[i]);
			} catch (NumberFormatException e) {
				throw new IllegalArgumentException(
						String.format("Bad argument \"%s\": could not parse \"%s\" as a double", s, nums[i]));
			}
		}
		return result;
	}
}