/* This program illustrates how to implement a recursive algorithm without
   using recursion.

   Things to watch out for when using recursion:

   1. are the recursive calls creating redundant computation?
   example: int fib(int n) {if (n<2) return 1; else return fib(n-1)+fib(n-2);}

   2. is the depth of recursion (number of nested calls) under control?
   example: int fact(int n) {if (n<2) return 1; else return n*fact(n-1);}

   Neither of the two examples above should use recursion.  

   How about:
        int bif(int n) { if (n<2) return 1; else return n*bif(n/2); }

   Implementing the above function recursively is acceptable.  Why?
*/

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

public class trifract extends JFrame
{
    private int width;  // dimensions of window in pixels
    private int height;
    private Graphics display; // drawing object

    // constructor
    public trifract(int x, int y)// x,y indicate width, height
    { width=x; height=y;
      this.setBounds(0,0,width,height);
      setVisible(true);
      this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
      display = this.getGraphics();  // drawing object
      display.setColor(Color.white);
      display.fillRect(0,0,width,height); // draw solid white rectangle
      try { Thread.sleep(500); } catch (Exception e) {} // synch with system

      drawstuff(); // call other functions that draw shapes
    }

    private void drawstuff()
    {
	/*
	int x = width/2; int y = 50;
	display.setColor(Color.blue); // consult Color class for colors.
	display.drawLine(x,y,width,height);  // draw a line.
	display.drawRect(400,500,60,100); // draw rectangle
	display.setColor(Color.red);      // change color.
	display.fillOval(100,100,250,200); // draw solid oval
	*/
	// consult docs for Graphics class for other drawing operations.

	triangles2();
    }// user-defined drawing function

    void triangles2()  // "recursive" algorithm:
    {
	display.setColor(Color.red); // consult Color class for colors.
	rtriangles(width/2,30,20,height-10,width-20,height-10);
    }
    void rtriangles(int x1, int y1, int x2, int y2, int x3, int y3)
    {
		display.drawLine(x1,y1,x2,y2);
		display.drawLine(x1,y1,x3,y3);
		display.drawLine(x2,y2,x3,y3);
		// determine if recursion continues:
		if (Math.abs(x2-x3)>4)
		    {
			// calculate midpoints
			int lx=(x1+x2)/2, ly=(y1+y2)/2;
			int rx=(x1+x3)/2, ry=(y1+y3)/2;
			int bx=(x3+x2)/2, by=(y3+y2)/2;
			// draw 3 smaller triangles
			rtriangles(x1,y1,lx,ly,rx,ry);
			rtriangles(lx,ly,x2,y2,bx,by);
			rtriangles(rx,ry,bx,by,x3,y3);
			try {Thread.sleep(5); } catch (Exception e) {}
		    }
    }//recursive version

    class Tstack // simple stack class to control "recursion" manually
    {
	int x1, y1, x2, y2, x3, y3;
	Tstack next;  // pointer to next stack frame
	public Tstack(int a, int b, int c, int d, int e, int f, Tstack tail)
	{ x1=a; y1=b; x2=c; y2=d; x3=e; y3=f; next=tail;}
    }
    // empty stack Tstack S = null;
    // push: R = new rstack(a,b,c,d,e,f,R);
    // pop: R = R.next
	
    void triangles()  // non-"recursive" algorithm:
    {
	display.setColor(Color.red); // consult Color class for colors.
	// create stack with initial coordinates
	Tstack S = new Tstack(width/2,30,20,height-10,width-20,height-10,null);
	while (S!=null)
	    {
		// take info from top of stack:
		int x1=S.x1, y1=S.y1, x2=S.x2, y2=S.y2, x3=S.x3, y3=S.y3;
		S = S.next; // pop stack
		// draw triangle
		display.drawLine(x1,y1,x2,y2);
		display.drawLine(x1,y1,x3,y3);
		display.drawLine(x2,y2,x3,y3);
		// determine if recursion continues:
		if (Math.abs(x2-x3)>4)
		    {
			// calculate midpoints
			int lx=(x1+x2)/2, ly=(y1+y2)/2;
			int rx=(x1+x3)/2, ry=(y1+y3)/2;
			int bx=(x3+x2)/2, by=(y3+y2)/2;
			// push 3 triangles on stack
			S = new Tstack(x1,y1,lx,ly,rx,ry,S);
			S = new Tstack(lx,ly,x2,y2,bx,by,S);
			S = new Tstack(rx,ry,bx,by,x3,y3,S);
			try {Thread.sleep(5); } catch (Exception e) {}
		    }
	    }//while stack not empty
    }// triangles

    /* Sometimes, converting a recursive program to a non-recursive one
       is more difficult because the calls can interfering : the result
       of one call can influence how other calls are made.
     */
    

    // the following method is called when the window needs to be repainted:
    public void paint(Graphics g) { } // override autopaint method


    // main must create an instance of trifract class:
    public static void main(String[] args)
    {
	trifract t = new trifract(800,700); // create instance
    }
}//trifract