package test4;

import java.util.List;

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

	/**
	 * Returns the string formed by repeating each character in
	 * the specified string. For example:
	 * 
	 * <pre>
	 * doubler("")     returns the string equal to ""
	 * doubler("a")    returns the string equal to "aa"
	 * doubler("xy")   returns the string equal to "xxyy"
	 * doubler("big")  returns the string equal to "bbiigg"
	 * doubler("EECS") returns the string equal to "EEEECCSS"
	 * </pre>
	 * 
	 * @param s a string
	 * @return the string formed by repeating each character in
	 * the specified string
	 */
	public static String doubler(String s) {
		if (s.isEmpty()) {
			return s;
		}
		return "" + s.charAt(0) + s.charAt(0) + doubler(s.substring(1));
	}

	/**
	 * Returns a string where the case of each letter is flipped compared to the
	 * corresponding letter in s. The empty string is returned if s is equal
	 * to the empty string. For example:
	 * 
	 * <pre>
	 * flipCase("")           returns the string equal to ""
	 * flipCase("a")          returns the string equal to "A"
	 * flipCase("A")          returns the string equal to "a"
	 * flipCase("abCd")       returns the string equal to "ABcD"
	 * flipCase("CAMELcASE")  returns the string equal to "camelCase"
	 * </pre>
	 * 
	 * @param s
	 *            a string consisting of English letter characters
	 * @return a string where the case of each letter is flipped compared to the
	 *         corresponding letter in s
	 */
	public static String flipCase(String s) {
		if (s.length() == 0) {
			return "";
		}
		char c = s.charAt(0);
		if (Character.isLowerCase(c)) {
			return Character.toUpperCase(c) + Test4C.flipCase(s.substring(1));
		}
		return Character.toLowerCase(c) + Test4C.flipCase(s.substring(1));
	}

	
	/**
	 * Sorts the elements of the list t so that the elements are
	 * in ascending order. A precondition of this method is that t
	 * must be already sorted in ascending order except that adjacent
	 * pairs of elements in t may be out of order. Consider the following
	 * almost sorted lists:
	 * 
	 * <pre>
	 * [1, 0]                1, 0 is out of order
	 * [0, 2, 1]             2, 1 is out of order
	 * [0, 2, 1, 3]          2, 1 is out of order
	 * [0, 2, 1, 4, 3]       2, 1 and 4, 3 are out of order
	 * [0, 1, 3, 2, 4]       3, 2 is out of order
	 * </pre>
	 * 
	 * <p>
	 * This method switches the positions of the out-of-order 
	 * adjacent elements thus repairing the list so that it is
	 * in sorted order.
	 * 
	 * @param t a list of almost sorted elements
	 * @pre. t is sorted in ascending order except that adjacent
	 * pairs of elements may be out of order
	 */
	public static void repair(List<Integer> t) {
		if (t.size() < 2) {
			return;
		}
		int first = t.get(0);
		int second = t.get(1);
		if (first > second) {
			t.set(0, second);
			t.set(1, first);
			repair(t.subList(2, t.size()));
		}
		else {
			repair(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;
	}
	
}