/*
 * Projlet6.java
 *
 * Created on August 17, 2003, 9:00 PM
 */

/**  Programming solution to 1st problem (find minimum) of Proj-let #6.
 */
public class Projlet6_minVal { 
    
    /**************************** 1a *****************************/
    /** Find and return the minimum value in the array.
     * Precondition: values.length > 0
     */
    public static int arrayMin(int[] values) {
        assert values != null: "Array cannot be null";
        assert values.length > 0: "Array cannot be empty";
        int minimum =  minValue(values, 0, values.length-1); 
        return minimum;
    }
    
    /**  Helper function for arrayMin. 
     Find and return the smallest value in the array, between index
     * lo and index hi; both endpoints are included.
     * 
     * Preconditions: values.length >0; 0 <= lo <= hi <= values.length.
     */
    private static int minValue(int[] values, int lo, int hi) {
        assert lo <= hi;
        if (lo >= hi) {
            return values[lo]; //base case -- an array with just one element
        }
        int restOfArrayMin = minValue(values, 0,  hi-1);
        if (restOfArrayMin <= values[hi]) {
            return restOfArrayMin;
        } else {
            return values[hi];
        }
    }
    
    /******************************** 1b ******************************/
    /** Find and return the minimum value in the array of objects.
     *  Precondition: The values are all Comparable and can be compared with each other.
     *  @return null if the array is null or empty.
     */
    public static Object minObject(Object[] values) {
        if (values == null || values.length == 0) {
            return null;
        }
        Comparable minimum =  (Comparable) minObject(values, 0, values.length-1); 
        return minimum;
    }
    
    /**  Helper function for minObject. 
     Find and return the smallest value in the array, between index
     * lo and index hi; both endpoints are included.
     * 
     * Preconditions: values.length >0; 0 <= lo <= hi <= values.length.
     */
    private static Object minObject(Object[] values, int lo, int hi) {
        assert lo <= hi;
        if (lo >= hi) {
            return values[lo]; //base case -- an array with just one element
        }
        Comparable restOfArrayMin = (Comparable) minObject(values, 0,  hi-1);
        if (restOfArrayMin.compareTo(values[hi]) <= 0) {
            return restOfArrayMin;
        } else {
            return values[hi];
        }
    }
    
    
    /** Just for testing.
     * @param args the command line arguments (ignored).
     */
    public static void main(String[] args) {
        assert 100 == arrayMin(new int[] {100});
        assert 100 == arrayMin(new int[] {100, 200});
        assert 100 == arrayMin(new int[] {200, 100});
        assert 3 == arrayMin(new int[] {100, 2000, 4, 3,  20, 99, 999, 99999});
        assert 3 == arrayMin(new int[] {3, 100, 2000, 4,  20, 99, 999, 99999});
        assert 3 == arrayMin(new int[] {100, 2000, 4,  20, 99, 999, 99999, 3});
        System.out.println("random min: " + arrayMin(randomIntArray()));
        System.out.println("random min: " + arrayMin(randomIntArray()));
        System.out.println("random min: " + arrayMin(randomIntArray()));
        System.out.println("random min: " + arrayMin(randomIntArray()));
        
        assert null == minObject(null);
        assert null == minObject(new String[0]);
        assert "lucky".equals(minObject(new String[] {"lucky"}));
        assert "a".equals(minObject(new String[] {"a", "b", "c"})); 
        assert "a".equals(minObject(new String[] {"c", "a", "b"})); 
        assert "a".equals(minObject(new String[] {"c", "a", "b", "c"})); 
        assert !"b".equals(minObject(new String[] {"c", "a", "b", "c"})); 
        System.out.println("random min object: " + minObject(randomIntegerArray()));
        System.out.println("random min object: " + minObject(randomIntegerArray()));
        System.out.println("random min object: " + minObject(randomIntegerArray()));
        
        System.out.println("Tests finished");
    }
    
    /** Generate test data.
       Don't make the arrays too large or the recursion will overflow.
     */
    public static int[] randomIntArray() {
        int asize = 1 + (int) (1000 * Math.random());
        int[] testvalues = new int[asize];
        for (int i = 0; i < asize; i++) {
            testvalues[i] = 50000 - (int) (100000 * Math.random());
        }
        return testvalues;   
    }
    
    /** Generate random test data.
     */
    public static Integer[] randomIntegerArray() {
        int[] ints = randomIntArray();
        int asize = ints.length;
        Integer[] testvalues = new Integer[asize];
        for (int i = 0; i < asize; i++) {
            testvalues[i] = new Integer(ints[i]);
        }
        return testvalues;
    }
            
    
}