// A program that demonstrates several recursive algorithms implemented
// in Java. In particular, this program demonstrates algorithms that...
//   o Find zeros of functions
//   o Generate a random palindrome
//   o Generate a "map" of a random land mass

// History
//
//   January 2007 -- Created by Doug Baldwin as a prototype for a
//     CSci 240 lab exercise.




import java.util.Random;
import javax.swing.JFrame;




class RecursionDemo {
    
    
    
    
    // Find a zero of a function, f, between x1 and x2. This will return a
    // value x such that f(x) is within tolerance tol of 0, i.e., -tol < f(x) < tol.
    // This uses a recursive implementation of the standard bisection method,
    // i.e., evaluate f at the point midway between x1 and x2, and then recursively
    // look for a zero in either the left or right half of the [x1,x2] interval,
    // according to how the sign of f at the midpoint compares to the signs of
    // f(x1) and f(x2) -- unless the value at the midpoint is within the tolerance
    // of 0, in which case the search for a zero is finished.
    //
    // Precondition: the sign of f(x1) differs from the sign of f(x2).
    
    public static double findZero( double x1, double x2, Function f, double tol ) {
        
        double mid = ( x1 + x2 ) / 2.0;
        double fMid = f.value( mid );
        
        if (  -tol < fMid  &&  fMid < tol  ) {
            return mid;
        }
        else if (  Math.signum(fMid) != Math.signum( f.value(x1) )  ) {
            return findZero( x1, mid, f, tol );
        }
        else {
            return findZero( mid, x2, f, tol );
        }
    }
    
    
    
    
    // Generate a random palindrome of length n. This function is based on the
    // recursive insight that a palindrome of length 0 is the empty
    // string, a palindrome of length 1 is any single character, and
    // a palindrome of length n > 1 is a palindrome of length n-2 with
    // the same character appended to its front and back. To pick characters
    // randomly, I draw them randomly from an "alphabet" string.
    
    public static String makePalindrome( int n ) {
        
        final String alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
        
        
        // Set up a random number generator in case one is needed to generate
        // the palindrome. In order to avoid having generators with the same
        // seed, and thus same "random" numbers, on consecutive calls to this
        // function, I seed the generator with a combination of a time-dependent
        // number that changes as rapidly as possible, and the length of the
        // palindrome.
        
        Random generator = new Random( System.nanoTime() + n );
        
        
        // Really generate the palindrome:
        
        if ( n <= 0 ) {
            return "";
        }
        else if ( n == 1 ) {
            int charIndex = generator.nextInt( alphabet.length() );
            return alphabet.substring( charIndex, charIndex+1 );
        }
        else {
            int charIndex = generator.nextInt( alphabet.length() );
            char character = alphabet.charAt( charIndex );
            return character + makePalindrome( n - 2 ) + character;
        }
    }

    
    
    
    // The main method. This simply demonstrates each algorithm in turn.
    
    public static void main (String args[]) {
        
        
        // Find zeros of some functions:

        Function f1 = new Quadratic( 1.0, 0.0, -1.0 );      // x^2 - 1, has zeros at -1 and 1
        Function f2 = new SineFunction();                   // sin(x), has zeros at multiples of Pi
        
        System.out.println( "Some zeros of some functions:" );
        System.out.println(   "\tFor " + f1 + " between 0 and 2 (should be 1): "
                            + findZero( 0.0, 2.0, f1, 0.001 ) );
        System.out.println(   "\tFor " + f1 + " between -2 and 0 (should be -1): "
                            + findZero( -2.0, 0.0, f1, 0.001 ) );
        System.out.println(   "\tFor " + f2 + " between 3 and 4 (should be about 3.14): "
                            + findZero( 3.0, 4.0, f2, 0.001 ) );
        System.out.println(   "\tFor " + f2 + " between 6 and 7 (should be about 6.28): "
                            + findZero( 6.0, 7.0, f2, 0.001 ) );
        System.out.println( "\tFor " + f2 + " between 1 and 10 (should be either 3.14, 6.28, or 9.42): "
                            + findZero( 1.0, 10.0, f2, 0.001 ) );
        
        // Demonstrate some random palindromes:
        
        System.out.println();
        System.out.println( "Some random palindromes:" );
        System.out.println( "\tLength 1: " + makePalindrome( 1 ) );
        System.out.println( "\tLength 5: " + makePalindrome( 5 ) );
        System.out.println( "\tLength 8: " + makePalindrome( 8 ) );
        
        
        // Draw a map of a random landmass. Most of the work is really
        // done in the "IslandCanvas" class:
        
        final int islandSize = 257;                     // The height and width of the map, in pixels
        
        JFrame islandWindow = new JFrame( "Map" );
        islandWindow.setSize( islandSize, islandSize );
        islandWindow.setDefaultCloseOperation( JFrame.EXIT_ON_CLOSE );
        IslandCanvas canvas = new IslandCanvas( islandSize );
        islandWindow.add( canvas );
        islandWindow.setVisible( true );
    }
}