// Recursive version of triangles.
// Recursion (in the sense of a function that calls itself) is a valid
// implementation method for Sierpinski's triangle because 1. there is no
// redundancy caused by the multiple recursive calls and 2. the depth 
// of recursion is proportional to log(n), which is negligible.

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

public class triangles extends JFrame
{

    private int width;
    private int height;
    private Graphics display;

    // constructor
    public triangles(int x, int y) 
    { width=x; height=y;
      this.setBounds(0,0,width,height);
      setVisible(true);
      this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
      display = this.getGraphics();  
      display.setColor(Color.white);
      display.fillRect(0,0,width,height);
      try { Thread.sleep(500); } catch (Exception e) {} // synch

      triangle();
      //triangle(x/2,24,8,y-8,x-8,y-8);  // draw triangle
    }

    protected void triangle()
    {
        int x1= width/2, y1=30, x2= 8, y2=height-8;
        int x3 = width-8, y3 = height-8;
        stackframe tos = new stackframe(x1,y1,x2,y2,x3,y3,null);
        while (tos!=null) // while top of stack not empty
            {
                // take info from top stack frame
                x1 = tos.x1; y1=tos.y1; x2=tos.x2; y2=tos.y2;
                x3=tos.x3; y3=tos.y3;
                tos = tos.next; // pop top stack frame
                // draw triangle
                display.setColor(Color.red);
                display.drawLine(x1,y1,x2,y2); // top to lower left
                display.drawLine(x2,y2,x3,y3); // base
                display.drawLine(x3,y3,x1,y1);
                // determine if triangle is large enough to divide...
                if (Math.abs(x3-x2)>4)
                    {
                       // calculate three midpoints:
                       int lx = (x1+x2)/2, ly = (y1+y2)/2;
                       int bx = (x3+x2)/2, by = (y3+y2)/2;
                       int rx = (x1+x3)/2, ry = (y1+y3)/2;
                       // push three smaller triangles on the stack
                       tos = new stackframe(lx,ly,x2,y2,bx,by,tos); // left
                       tos = new stackframe(rx,ry,bx,by,x3,y3,tos);
                       tos = new stackframe(x1,y1,lx,ly,rx,ry,tos); //top
                    }
                //try {Thread.sleep(10);} catch(Exception ee){}
            }// while
    }//triangle

    class stackframe
    {
        int x1, y1, x2, y2, x3, y3;
        stackframe next;
        public stackframe(int a,int b,int c, int d, int e, int f, stackframe n)
        {
            x1=a; y1=b; x2=c; y2=d; x3=e; y3=f;  next = n;
        }
    }
    // empty stack: stackframe stack = null;
    // stack = new stackframe(a,b,c,d,e,f,stack); // push
    // stack = stack.next // pop

    protected void triangle(int x1,int y1,int x2,int y2,int x3,int y3)
    {
	display.setColor(Color.blue);
	display.drawLine(x1,y1,x2,y2);  // top
	display.drawLine(x2,y2,x3,y3);  // left base
	display.drawLine(x3,y3,x1,y1);  // right base

	int lx = (x1+x2)/2;
	int ly = (y1+y2)/2;
	int rx = (x1+x3)/2;
	int ry = (y1+y3)/2;
	int bx = x1;
	int by = y2;
	if (Math.abs(lx-rx)>=4)
	{
            try { Thread.sleep(10); } catch (Exception e) {} // synch
	    triangle(x1,y1,lx,ly,rx,ry);
	    triangle(lx,ly,x2,y2,bx,by);
	    triangle(rx,ry,bx,by,x3,y3);
	}
    }

    public void paint(Graphics g) {} // override autopaint method

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