import java.awt.Point;
import java.util.LinkedList;

/**
 *
 * @author Peterc Cappello
 */
public class Math 
{    
    public static void printStack( LinkedList<Point> stack )
    {
        Point[] stackAsArray = stack.toArray( new Point[0] );
        for ( int i = stackAsArray.length - 1; i >=  0; i-- )
        {
            System.out.println( "Level " + ( stackAsArray.length - 1 - i ) + " arguments: " + stackAsArray[ i ].x + " " + stackAsArray[ i ].y );
        }
        System.out.println("");
    }
    
    /**
     * Uses Euclid algorithm to compute the greatest common divisor of 2 integers.
     * @param i One of the 2 integers.
     * @param j The other of the 2 integers.
     * @return the greatest common divisor of i and j.
     */
    public static int gcd( int i, int j ) { return j == 0 ? i : gcd( j, i % j ); }
    
    /**
     * Uses Euclid algorithm to compute the greatest common divisor of 2 integers.
     * @param i One of the 2 integers.
     * @param j The other of the 2 integers.
     * @param stack A representation of the call stack.
     * @return the greatest common divisor of i and j.
     */
    public static int instrumentedGcd( int i, int j,  LinkedList<Point> stack )
    {
        if ( j == 0 )
        {
            System.out.println("Base case encountered ...");
            printStack( stack );
            return i;
        }
        
        System.out.println("Pushing ...");
        stack.push(new Point( j, i % j ) );
        printStack( stack );
        
        int value = instrumentedGcd( j, i % j, stack );
        
        System.out.println("Popping ...");
        stack.pop();
        printStack( stack );
        
        return value;
    }
    
    private static LinkedList<Point> call( int i, int j )
    {
        LinkedList<Point> stack = new LinkedList<>();
        stack.add( new Point( i, j ) );
        printStack( stack );
        return stack;
    }
    
    public static void main( String[] args )
    {
        System.out.println("gcd( 25, 5 ): " + instrumentedGcd( 25, 5, call( 25, 5 ) ) );
        System.out.println("gcd( 16, 14 ): " + instrumentedGcd( 16, 14, call( 16, 14 ) ) );
        System.out.println("gcd( 70, 42 ): " + instrumentedGcd( 70, 42, call( 70, 42 )  ) );
        System.out.println("gcd( -42, -70 ): " + instrumentedGcd( -42, -70, call( -42, -70 )  ) );
        System.out.println("gcd( 1024*3, 512*5 ): " + instrumentedGcd( 1024*3, 512*5, call( 1024*3, 512*5 )  ) );
    }
}