import javax.swing.*;
import java.awt.*;

/** Demo for recursion, CS100J, Spring 2006 */
public class Demo extends Turtle {
    int d= 20; // size of line between hilberts
    int ms= 500; // time to wait after drawing
    
    /** Precondition: The turtle faces east [or west].
     Draw a Hilbert space-filling curve of order n
     north/east [or south/west]
     of the current turtle position.
     End up facing east [or west]*/
    public void hilbert0(int n) {
        pause(ms);
        if (n == 0) return;
        addAngle(90);      // Face north         [or south]
        hilbert1(n-1);     
        move(d);           // Line heading north [or south]
        addAngle(-90);     // Face east          [or west]
        hilbert0(n-1);
        move(d);           // Line heading east  [or west]
        hilbert0(n-1);
        addAngle(-90);     // Face south         [or north]
        move(d);           // Line heading south [or north]
        hilbert1(n-1);
        addAngle(90);      // Face east          [or west]
        
    }
    
    /** Precondition: The turtle faces north [or south]
     Draw a Hilbert space-filling curve of order n
     north/east [or south/west]
     of the current turtle position.
     End up facing north [or south]*/
    public void hilbert1(int n) {
        pause(ms);
        if (n == 0) return;
        addAngle(-90);     // Face east           [or west]
        hilbert0(n-1);
        move(d);           // Line heading east   [or west]
        addAngle(90);      // Face north          [or south]
        hilbert1(n-1);
        move(d);           // Line heading north  [or south]
        hilbert1(n-1);     
        addAngle(90);      // Face west           [or east]
        move(d);           // Line heading west   [or east]
        hilbert0(n-1);
        addAngle(-90);     // Face north          [or south]
    }
    
    /** Draw a Hilbert space-filling curve of depth n.
     Each line is d units long.
     Wait ms milliseconds at each recursive call */
    public void doAHilbert(int n, int d, int ms) {
        this.d= d;
        this.ms= ms;
        int SIZE= 512;
        double max= Math.pow(2, n);
        clear();
        moveTo(5, getHeight()-5, 0);
        System.out.println("Hilbert " + n + "-curve. Line length " + d);
        hilbert0(n);
    }
    
    /** = !n  (for n>=0) */
    public static int fact(int n) {
        return 0;
    }
    
    
    
    
    /** = s but with its blanks removed */
    public static String deblank(String s) {
        if (s.length() == 0)
            return s;
        // s has at least on char.
        if (s.charAt(0) == ' ')
            return deblank(s.substring(1)) ;
        
        // first char of s is not blank
        return s.charAt(0) + deblank(s.substring(1));
    }
    
    /** = Òs is a palindromeÓ */
    public static boolean isPal(String s) {
        if (s.length() <= 1)
            return true;
        
        return /* first and last chars are the same &&
                  what's between is a palindrome */
               s.charAt(0) == s.charAt(s.length()-1) &&
               isPal(s.substring(1,s.length()-1));
    }
    
    /** Sort b[h..k] (using Quicksort) */
    public static void qsort(int[] b, int h, int k) {
        if (k+1-h <= 1) {
            return;
        }
        // { b[h..k] has at least 2 elements }
        int j= partition(b, h, k);
        // Sort b[h..j-1]
        qsort(b, h, j-1);
              
        // Sort b[j+1..k]
        qsort(b, j+1, k);
    }
    
    /** Let x be the value initially in b[h].
     Permute b[h..k] and return integer j satisfying R:<br><br>
     
     b[h..j-1] <= b[j] = x <= b[j+1..k]
     */
    public static int partition(int[] b, int h, int k) {
        // {Q: Let x be the value initially in b[h]}
        int j;
        // Truthify R1: b[h+1..j] <= b[h] = x <= b[j+1..k];
        int i= h+1; j= k;
        // {inv P: b[h+1..i-1] <= b[h] = x <= b[j+1..k]}
        while (i <= j) {
            if (b[i] < b[h]) i= i+1;
            else if (b[j] > b[h]) j= j-1;
            else {// {b[j] < x < b[i]}
                int t1= b[i]; b[i]= b[j]; b[j]= t1;
                i= i+1; j= j-1;
            }
        }
        int t= b[h]; b[h]= b[j]; b[j]= t;
        // {R}
        return j;
    }
    
    /** = array b, as in an array initializer */
    public static String toString(int[] b) {
        String res= "{";
        
        // inv: res contains b[0..k-1]
        for (int k= 0; k != b.length; k= k+1) {
            if (k != 0) res= res + ", ";
            res= res + b[k];
        }
        return res + "}";
    }
    
    
}