package test4;

import java.util.List;

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

	/**
	 * Returns the string formed by repeating the specified string n times; each
	 * repetition of s is separated by a comma followed by space.
	 * 
	 * <pre>
	 * repeat("cat", 1) returns the string equal to "cat"
	 * repeat("rat", 2) returns the string equal to "rat, rat"
	 * repeat("la", 3)  returns the string equal to "la, la, la"
	 * </pre>
	 * 
	 * @param s
	 *            the string to be repeated
	 * @param n
	 *            the number of times to repeat s
	 * @return the string formed by repeating the specified string n times
	 * @pre. n is greater than zero
	 */
	public static String repeat(String s, int n) {
		if (n == 1) {
			return s;
		}
		return s + ", " + repeat(s, n - 1);
	}
	
	
	/**
	 * Returns true if the specified string is a palindrome. A palindrome
	 * is a string that is spelled the same backwards and forwards. The
	 * empty string is a palindrome.
	 * 
	 * <pre>
	 * isPalindrome("a")      returns true
	 * isPalindrome("at")     returns false
	 * isPalindrome("tat")    returns true
	 * isPalindrome("refer")  returns true
	 * isPalindrome("refers") returns false
	 * </pre>
	 * 
	 * @param s a string 
	 * @return true if the specified string is a palindrome, and false otherwise
	 */ 
	public static boolean isPalindrome(String s) {
		if (s.length() < 2) {
			return true;
		}
		char first = s.charAt(0);
		char last = s.charAt(s.length() - 1);
		if (first == last) {
			return isPalindrome(s.substring(1, s.length() - 1));
		}
		return false;
	}
	
	
	
	/**
     * Re-orders the elements of the argument list t so that
     * all of the negative elements of t are in the front part
     * of the list and all of the positive elements of t are
     * in the back part of the list. If the list contains zero
     * or one elements then the list is not modified. There is
     * no guarantee of the ordering of the positive elements
     * or of the negative elements.
     * 
     * <p>
     * Zero is considered to be a positive number for the purposes
     * of this method.
     * 
     * <p>
     * For example, a possible solution results in the following: 
     * </p>
     * 
     * <pre>
     * if t is []                    then partition(t) makes t []
     * if t is [1]                   then partition(t) makes t [1] 
     * if t is [-1, 2]               then partition(t) makes t [-1, 2]
     * if t is [2, -1]               then partition(t) makes t [-1, 2]
     * if t is [8, -2, 1]            then partition(t) makes t [-2, 1, 8]  
     * if t is [1, -5, -9, 4]        then partition(t) makes t [-5, -9, 4, 1] 
     * if t is [-3, 7, -1, 3, -5]    then partition(t) makes t [-3, -1, -5, 7, 3]
     * </pre>
     * 
     * @param t a list of integers
     */
    public static void partition(List<Integer> t) {
        if (t.size() < 2) {
            return;
        }
        int first = t.get(0);
        if (first < 0) {
            Test4A.partition(t.subList(1, t.size()));
        }
        else {
            t.add(first);
            t.remove(0);
            Test4A.partition(t.subList(0, t.size() - 1));
        }
    }
    
    
    /**
     * Returns the index of the element equal to zero in the
     * specified sorted list. The list t may be sorted in either
     * ascending or descending order. The list t is not modified
     * by this method.
     * 
     * <p>
     * The computational complexity of the method is O(log n) where
     * n is the size of the list t.
     * 
     * @param t a sorted list
     * @return the index of the element equal to zero
     * @pre. the list is sorted in either ascending or descending order
     * and the list contains zero
     */
    public static int findZero(List<Integer> t) {
    	int i = t.size() / 2;
    	int mid = t.get(i);
    	if (mid == 0) {
    		return i;
    	}
    	int first = t.get(0);
    	if (first >= 0 && mid < 0 || first <= 0 && mid > 0) {
    		return findZero(t.subList(0, i));
    	}
    	return i + 1 + findZero(t.subList(i + 1, t.size()));
    }
    
    
}