package test4;

import java.util.List;

public class Test4D {
	private Test4D() {
		// empty by design
	}

	/**
	 * Returns the sum of the integer values between start and end (including
	 * start and end). For example:
	 * 
	 * <pre>
	 * sum(5, 5)       returns 5
	 * sum(0, 1)       returns 1   (0 + 1)
	 * sum(0, 2)       returns 3   (0 + 1 + 2)
	 * sum(3, 6)       returns 18  (3 + 4 + 5 + 6)
	 * sum(-100, 101)  returns 101 (-100 + -99 + ... + 99 + 100 + 101)
	 * </pre>
	 * 
	 * @param start
	 *            the number to start the sum at
	 * @param end
	 *            the number to end the sum at
	 * @return the sum of the values from start to end
	 * @pre. start is less than or equal to end
	 */
	public static int sum(int start, int end) {
		if (start == end) {
			return start;
		}
		return start + sum(start + 1, end);
	}
	
	
	/**
	 * Returns true if the specified list is sorted in ascending
	 * order and false otherwise. The empty list is sorted. 
	 * This method does not modify the list t.
	 * For example:
	 * 
	 * <pre>
	 * t             isSorted(t)
	 * -------------------------
	 * []              true
	 * [-5]            true
	 * [8, 9]          true
	 * [1, 2, 3]       true
	 * [1, 1, 5]       true
	 * 
	 * [10, 4]         false
	 * [1, 2, 3, 1]    false
	 * </pre>
	 * 
	 * @param t a list
	 * @return true if the specified list is sorted in ascending
	 * order and false otherwise
	 */
	public static boolean isSorted(List<Integer> t) {
		if (t.size() < 2) {
			return true;
		}
		int first = t.get(0);
		int second = t.get(1);
		if (first <= second) {
			return isSorted(t.subList(1, t.size()));
		}
		return false;
	}
	
	
	/**
	 * Moves the first element <code>f</code> of <code>t</code> down the list
	 * until it reaches the first location in the list where the next element is
	 * greater than or equal to <code>f</code>. For example:
	 *
	 * <pre>
	 * if t is equal to        then moveFirstDown(t) makes t equal to
	 * --------------------------------------------------------------------
	 * []                      []
	 * [1]                     [1]
	 * [-1, 2]                 [-1, 2]
	 * [1, -2, 8]              [-2, 1, 8]
	 * [4, -5, -9, 4]          [-5, -9, 4, 4]
	 * [9, 1, 3, 2, 4]         [1, 3, 2, 4, 9]
	 * </pre>
	 *
	 * @param t
	 *            the list to move the first element of
	 */
	public static void moveFirstDown(List<Integer> t) {
		if (t.size() <= 1) {
			return;
		}
		int first = t.get(0);
		int second = t.get(1);
		if (first > second) {
			t.set(0, second);
			t.set(1, first);
			moveFirstDown(t.subList(1, t.size()));
		}
	}
	
	

	/**
	 * Returns the location of Waldo given two guesses of Waldo's location.
	 * Waldo's location is an integer value somewhere between
	 * Integer.MIN_VALUE and Integer.MAX_VALUE. Only Waldo knows
	 * Waldo's location, and Waldo is not willing to give his exact
	 * location to anyone; however, Waldo is willing to tell a 
	 * client which of two guesses is closer to his location (see the closer method
	 * in the Waldo class).
	 * 
	 * <p>
	 * This method can find Waldo's location using 32 or fewer recursive calls
	 * (i.e., it does not check every possible location for Waldo).
	 * 
	 * @param waldo a reference to a Waldo object
	 * @param locA a guess of Waldo's location
	 * @param locB a guess of Waldo's location
	 * @return Waldo's exact location
	 * @pre. locA is less than or equal to locB
	 */
	public static int wheresWaldo(Waldo waldo, int locA, int locB) {
		if (locA == locB) {
			return locA;
		}
		int mid = locA + (int) ((0L + locB - locA) / 2);
		// next 2 lines may overflow
		//int mid = loc1 + (loc2 - loc1) / 2);
		//int mid = (loc1 + loc2) / 2;
		int closer = waldo.closer(locA, locB);
		if (closer == -1) {
			return wheresWaldo(waldo, locA, mid);
		}
		else if (closer == 1) {
			return wheresWaldo(waldo, mid + 1, locB);
		}
		return mid;
	}
}