/*********************************************************
 *                                                       *
 *               Fractal Generating Applet               *
 *                                                       *
 *********************************************************/
 
 /*  DiBiano, Robert J.
  *  Fractal Generating Applet
  *  11/8/2002
  *
  *  Purpose: graphically show what root complex numbers converge to with Newton's method.
  *
  *  The applet can recive non default varibale values from the calling web page through 
  *    the use of the param command as shown in this sample applet call:
  *
  *    <applet code="atractor.class" width="???" height="???">
  *    <param name=??? value=???>
  *    </applet>
  *
  *    Valid Parameters:
  *    - width and height are in pixels, name and value are strings, quotes are optional though
  *    - polynomial is the polynomial
  *    - xMin,xMax,yMin,yMax are bounds of graph
  *    - lowIter: if it converges in this many or less will look a shade darker
  *    - highIter: if it takes this many or more to converge, graph will be a shade lighter
  *
  *
  *  Changes Log:
  *
  *    11/08/2002 - changes log started
  *    11/21/2002 - formula for yStepSize was wrong (was same as for xStepSize) so I fixed it.
  *    12/17/2003 - was displaying upside down(fixed I tihnk), added interface for end user to 
  *      type in the function to use and various other data.  No error checking right now.
  *
  *
  *  Known Issues:  The program is still in it's early stages, so error checking may not exist
  *      for everything.
  *  - not sure it can handle negative height and width input
  *  - polynomial can only be in standard form (Ax^B + Cx^D + ...) and only integer coefficients
  *  - class polynomial is a hunk of junk; string input has to be redone minimally (so floats 
  *      work), internal representation (and therefore derivative method) could stand to be 
  *      totally re worked, it would also be nice to handle stuff in factored form or functions 
  *      other than simple powers.
  *  - xMin, xMax, yMin, yMax also can only be integers if brought from outside b/c we use
  *      parseInt to parse them, browsers don't support the java version that that has 
  *      parseDouble yet.
  *  - Our test for convergence does not actually work in some cases it seems.  Things like x^5
  *      show up as having many different roots b/c roots are badly calculated after a false 
  *      convergence detection flag is raised.  There may be other problems obscured by this
  *      one.
  *  - only the first 10 roots get unique colors, eventually want to generate random colors
  *      beyond this.
  *
  */

import java.applet.*;
import java.awt.*;
import java.lang.Math;

public class atractor extends Applet
{
String polyString="x^3-1";                      //  polynomial to do Newton's method on
polynomial equation;                            //  wrapper class for polynomial
polynomial derivative;                          //  d(polynomial)/dx
int width=100, height=100;                      //  image width and height in pixels
double xMin=-1, xMax=1, yMin=-1, yMax=1;        //  graph bounds
double xStepSize=(xMax-xMin)/(width-1);         //  x step size between pixels
double yStepSize=(yMax-yMin)/(height-1);        //  y step size between pixels
double error=Math.min(xStepSize,yStepSize)/100; //  max error for several things
int lowIter=0, highIter=0;
Font font=new Font("Courier", Font.PLAIN, 20);
Font bigFont=new Font("Courier", Font.BOLD, 25);

boolean fractalDrawn=false;                     //  is fractal drawn once yet?
int maxRoots=10;                                //  max number of individual roots displayable
complex roots[]=new complex[maxRoots];          //  roots of our equation
Color colors[]=new Color[maxRoots+1];           //  colors for each root
Image offScrImage;                              //  an offscreen scratch pad to hold the image
Graphics offScrGC;                              //  the graphics context used to draw on the pad
Button b1;
TextField tPolynomial,tXMin,tXMax,tYMin,tYMax,tLowIter,tHighIter;

public void init()
  {
  String parameter;                             //  holds external data fed into applet

  for (int x=0; x<maxRoots; x+=1)               //  initalize roots
    {
    roots[x]=new complex();
    }

  colors[0]=Color.red;                         //  need to work on this section, so that we can
  colors[1]=Color.yellow;                      //  vary maxRoots; will need Random colors for
  colors[2]=Color.blue;                        //  the 11th root and beyond
  colors[3]=Color.orange;
  colors[4]=Color.green;
  colors[5]=Color.magenta;
  colors[6]=Color.black;
  colors[7]=Color.cyan;
  colors[8]=Color.pink;
  colors[9]=Color.gray;
  colors[maxRoots]=Color.lightGray;             //  color of overflow roots

  width=getSize().width;                        //  set width and height to values of window in
  height=width;                      //    viewer displaying the applet

  offScrImage=createImage(width,height);        //  create offscreen image
  offScrGC=offScrImage.getGraphics();           //  give it a graphics context

  //  applet can recive non default graph boundaries from outside
  parameter=getParameter("polynomial");
  if (parameter!=null) polyString=new String(parameter);
  equation=new polynomial(polyString);
  derivative=equation.derivative();

  parameter=getParameter("xMin");
  if (parameter!=null) xMin=Integer.parseInt(parameter);

  parameter=getParameter("xMax");
  if (parameter!=null) xMax=Integer.parseInt(parameter);

  parameter=getParameter("yMin");
  if (parameter!=null) yMin=Integer.parseInt(parameter);

  parameter=getParameter("yMax");
  if (parameter!=null) yMax=Integer.parseInt(parameter);

  parameter=getParameter("lowIter");
  if (parameter!=null) lowIter=Integer.parseInt(parameter);

  parameter=getParameter("highIter");
  if (parameter!=null) highIter=Integer.parseInt(parameter);

  xStepSize=(xMax-xMin)/(width-1);              //  recalculate step sizes
  yStepSize=(yMax-yMin)/(height-1);
  error=Math.min(xStepSize,yStepSize)/100;      //  recalculate error

  setLayout(null);

  b1=new Button("Draw Fractal");
  b1.setLocation(3,width+40);
  b1.setSize(90,25);
  add(b1);

  tPolynomial = new TextField(polyString,20); 
  add(tPolynomial);
  tPolynomial.setLocation(98,width+40);
  tPolynomial.setSize(190,20);

  tXMin = new TextField(""+(int)xMin,3); 
  add(tXMin);
  tXMin.setLocation(360,width+40);
  tXMin.setSize(30,20);

  tXMax = new TextField(""+(int)xMax,3); 
  add(tXMax);
  tXMax.setLocation(360,width+60);
  tXMax.setSize(30,20);

  tYMin = new TextField(""+(int)yMin,3); 
  add(tYMin);
  tYMin.setLocation(465,width+40);
  tYMin.setSize(30,20);

  tYMax = new TextField(""+(int)yMax,3); 
  add(tYMax);
  tYMax.setLocation(465,width+60);
  tYMax.setSize(30,20);

  tLowIter = new TextField(""+lowIter,3); 
  add(tLowIter);
  tLowIter.setLocation(266,width+85);
  tLowIter.setSize(30,20);

  tHighIter = new TextField(""+highIter,3);
  add(tHighIter);
  tHighIter.setLocation(337,width+105);
  tHighIter.setSize(30,20);
  

  }  //  END of init

public boolean action(Event event, Object event_object)
  {
  if (event_object.equals("Draw Fractal"))
    {
    polyString=tPolynomial.getText();
    equation=new polynomial(polyString);
    derivative=equation.derivative();
    xMin=Integer.parseInt(tXMin.getText());
    xMax=Integer.parseInt(tXMax.getText());
    yMin=Integer.parseInt(tYMin.getText());
    yMax=Integer.parseInt(tYMax.getText());
    lowIter=Integer.parseInt(tLowIter.getText());
    highIter=Integer.parseInt(tHighIter.getText());
    xStepSize=(xMax-xMin)/(width-1);              //  recalculate step sizes
    yStepSize=(yMax-yMin)/(height-1);
    error=Math.min(xStepSize,yStepSize)/100;      //  recalculate error
    fractalDrawn=false;
    repaint();
    }
  return true;
  }

public void paint(Graphics g)
  {
  int xPixel,yPixel;                            //  mark where we are drawing
  int iteration;                                //  what iteration of Newton's method we are on
  double xValue,yValue;                         //  graph coordinates of where we are drawing
  complex x=new complex(), oldx=new complex();  //  hold Xi and Xi-1
  complex fx=new complex();                     //  holds calculated f(x)
  boolean converged, rootFound;            //  if it converged, and if the root was in our table
  int root, numRoots=0;             //  the current root on our table, and the total roots in it
  Color temp;                                   //  holds color so we can lighten/darken it
  boolean shaded=(lowIter!=0) || (highIter!=0); //  if both are 0, shading is disabled & skipped

  g.setFont(bigFont);
  g.drawString("Newton's method to converge to roots",3,width+20);
  g.setFont(font);
  g.drawString("xMin",305,width+55);
  g.drawString("xMax",305,width+75);
  g.drawString("yMin",410,width+55);
  g.drawString("yMax",410,width+75);
  g.drawString("Darken convergence in    or less steps",3,width+100);
  g.drawString("Don't Darken convergence in    or more steps",3,width+120);

  if (!fractalDrawn)                            //  draw fractal
    {
    //  draw the fractal on the offscreen image using it's graphics context
    //    at the same time display the fractal as it is generated:
    for (xPixel=0; xPixel<width; xPixel+=1)     //  do Newton's method for every pixel
      {
      xValue=xMin+xPixel*xStepSize;
      for(yPixel=0; yPixel<height; yPixel+=1)
        {
        yValue=yMax-yPixel*yStepSize;
        x.setEqual(xValue, yValue);
        converged=false;
        for(iteration=1; iteration<70; iteration+=1)             //  Newton's method to 70 steps
          {
          oldx.setEqual(x);                                      //  save Xn-1
          //fx.setEqual(x.pow(5).subtract(1));                   //  calculate f(x)
          //x.setEqual(x.subtract(fx.divide(x.pow(4).multiply(5)))); //  calc Xn
          fx.setEqual(equation.evaluateAt(x));                   //  calculate f(x)
          x.setEqual(x.subtract(fx.divide(derivative.evaluateAt(x))));  //  calc Xn
          if (x.isNear(error,oldx) && fx.isNear(error,0))        //  break if it converges
            {
            converged=true;
            break;
            }
          }  //  End of Newton's method
        if (converged)         //  check if it converged to a root, and fill the pixel if it did
          {
          rootFound=false;
          for (root=0; root<numRoots; root+=1)     //  see if it converged to an existing root
            {
            if (x.isNear(2*error, roots[root]))
              {
              rootFound=true;
              break;
              }
            }
          if (!rootFound)                          //  if not, add our new root to the list
            {
            if (numRoots<maxRoots)
              {
              roots[numRoots].setEqual(x);
              numRoots+=1;
              }
            }
          temp=colors[root];
          if (shaded)
            {
            temp=temp.darker();
            if (iteration<=lowIter) temp=temp.darker();
            if (iteration>=highIter) temp=temp.brighter();
            }
          offScrGC.setColor(temp);         //  set to correct color
          g.setColor(temp);
          offScrGC.drawLine(xPixel,yPixel,xPixel,yPixel);  //  plot the point
          g.drawLine(xPixel,yPixel,xPixel,yPixel);
          }  //  End of if (converged)
        }
      }  //  End of 2 loops to iterate through every pixel
    fractalDrawn=true;
    }  //  End of draw fractal
  else
    {
    //  stick our prefabricated fractal onto the applets graphics context,
    //    this way we dont need to re-generate the fractal in order to re display it
    g.drawImage(offScrImage,0,0,width,height,this);
    }
  }  //  END of paint

}// END of class atractor

//----------------------------------------------------------------------------------------------

class complex                               //  implements complex numbers, needs java.lang.Math
  {
  private double realPart;
  private double imaginaryPart;

  public complex(double realPart, double imaginaryPart)     //  constructor
    {
    this.realPart=realPart;
    this.imaginaryPart=imaginaryPart;
    }

  public complex()                                          //  constructor
    {
    this.realPart=0;
    this.imaginaryPart=0;
    }

  void setEqual(complex other)                              //  = operator
    {
    this.realPart=other.realPart;
    this.imaginaryPart=other.imaginaryPart;
    }

  void setEqual(double realPart, double imaginaryPart)      //  = operator
    {
    this.realPart=realPart;
    this.imaginaryPart=imaginaryPart;
    }

  complex add(complex other)                                //  + operator
    {
    complex answer=new complex();
    answer.realPart=this.realPart+other.realPart;
    answer.imaginaryPart=this.imaginaryPart+other.imaginaryPart;
    return answer;
    }

  complex add(double other)                                //  + operator
    {
    complex answer=new complex();
    answer.realPart=this.realPart+other;
    answer.imaginaryPart=this.imaginaryPart;
    return answer;
    }

  complex subtract(complex other)                           //  - operator
    {
    complex answer=new complex();
    answer.realPart=this.realPart-other.realPart;
    answer.imaginaryPart=this.imaginaryPart-other.imaginaryPart;
    return answer;
    }

  complex subtract(double other)                            //  - operator
    {
    complex answer=new complex();
    answer.realPart=this.realPart-other;
    answer.imaginaryPart=this.imaginaryPart;
    return answer;
    }

  complex multiply(complex other)                           //  * operator
    {
    complex answer=new complex();
    answer.realPart=this.realPart*other.realPart-this.imaginaryPart*other.imaginaryPart;
    answer.imaginaryPart=this.realPart*other.imaginaryPart+this.imaginaryPart*other.realPart;
    return answer;
    }

  complex multiply(double other)                            //  * operator
    {
    complex answer=new complex();
    answer.realPart=this.realPart*other;
    answer.imaginaryPart=this.imaginaryPart*other;
    return answer;
    }

  complex divide(complex other)                            //  / operator
    {
    complex answer=new complex();
    answer.realPart=(this.realPart*other.realPart+this.imaginaryPart*other.imaginaryPart)/
        (other.realPart*other.realPart+other.imaginaryPart*other.imaginaryPart);
    answer.imaginaryPart=(this.imaginaryPart*other.realPart-this.realPart*other.imaginaryPart)/
        (other.realPart*other.realPart+other.imaginaryPart*other.imaginaryPart);
    return answer;
    }

  complex divide(double other)                             //  / operator
    {
    complex answer=new complex();
    answer.realPart=this.realPart/other;
    answer.imaginaryPart=this.imaginaryPart/other;
    return answer;
    }

  complex pow(int n)                                      //  raises to the nth power
    {
    if (n>1) return this.multiply(this.pow(n-1));
    if (n==1) return this;
    complex one = new complex(1,0);
    if (n==0) return one;
    return one.divide(this.pow(-n));
    }

  public String toString()                                 //  automatic string conversion
    {
    String s;
    s = realPart + "+" + imaginaryPart + "i";
    return s;
    }

  public boolean isNear(double range, complex other) //true if #'s are within range of each other
    {
    double distance=Math.sqrt((this.realPart-other.realPart)*(this.realPart-other.realPart)+
        (this.imaginaryPart-other.imaginaryPart)*(this.imaginaryPart-other.imaginaryPart));
    if (distance<=range) return true;
    return false;
    }

  public boolean isNear(double range, double other) // true if #'s are within range of each other
    {
    double distance=Math.sqrt((this.realPart-other)*(this.realPart-other)+
        this.imaginaryPart*this.imaginaryPart);
    if (distance<=range) return true;
    return false;
    }

  }  //  End of class complex

//----------------------------------------------------------------------------------------------

class polynomial     //  class to hold a polynomial in standard form only, NOT especially robust
  {
  private int maxTerms=10;
  private String equation;
  private int terms;
  private int multipliers[]=new int[maxTerms];
  private int coefficients[]=new int[maxTerms];
  
  private boolean isANumber(char c)
    {
    return c>='0' && c<='9';
    }

  private boolean isValid(char c)
    {
    return isANumber(c) || c=='x' || c=='X' || c=='^' || c=='+' || c=='-';
    }

  public polynomial(String s)               //  constructor
    {
    int x,length;
    char c;
    boolean working;                        //  are we working on a term?

    equation=s;
    equation.trim();
    equation.toLowerCase();
    equation+=' ';
    length=equation.length();
    terms=0;                                //  # of terms and location of unfinished term
    working=false;

    for (x=0;x<length;x+=1)                 //  traverse eqation
      {
      if (isValid(equation.charAt(x)))             //  will traverse valid chars
        {
        if (equation.charAt(x) != '^')             //  valid term found
          {
          multipliers[terms]=1;              //  default values
          coefficients[terms]=0;
          while (equation.charAt(x)=='+' || equation.charAt(x)=='-')
            {
            if (equation.charAt(x)=='-') multipliers[terms]=-multipliers[terms];
            x+=1;
            }
          if (isANumber(equation.charAt(x)))
            {
            multipliers[terms]*=(int)equation.charAt(x)-48;
            x+=1;
            }
          while (isANumber(equation.charAt(x)))
            {
            multipliers[terms]*=10;
            if (multipliers[terms]>=0) multipliers[terms]+=(int)equation.charAt(x)-48;
            else multipliers[terms]-=(int)equation.charAt(x)-48;
            x+=1;
            }
          if (equation.charAt(x)=='x' || equation.charAt(x)=='X')  //  stuff past a 'x'
            {
            x+=1;
            coefficients[terms]=1;
            if (equation.charAt(x)=='^')           //  stuff past a '^'
              {
              x+=1;
              while (equation.charAt(x)=='+' || equation.charAt(x)=='-')
                {
                if (equation.charAt(x)=='-') coefficients[terms]=-coefficients[terms];
                x+=1;
                }
              if (isANumber(equation.charAt(x)))
                {
                coefficients[terms]*=(int)equation.charAt(x)-48;
                x+=1;
                }
              while (isANumber(equation.charAt(x)))
                {
                coefficients[terms]*=10;
                if (coefficients[terms]>=0) coefficients[terms]+=(int)equation.charAt(x)-48;
                else coefficients[terms]-=(int)equation.charAt(x)-48;
                x+=1;
                }
              }  //  End of stuff past a '^'
            }  //  End of stuff past a 'x'

          terms+=1;                         //  term finished
          x-=1;                             //  go back on char b/c loop will advance by one
          }  //  End of valid term
        }  //  End of traverse valid chars
      }  //  End of traverse eqation
    }                                       //  End of constructor


  public String toString()                  //  automatic string conversion
    {
    int x;
    String s="";
    for (x=0;x<terms;x+=1)
      {
      s+="+" + multipliers[x] + "X^" + coefficients[x];
      }
    return s;
    }

  complex evaluateAt(complex c)             //  evaluates polynomial at x
    {
    complex answer=new complex();
    int x;

    for (x=0;x<terms;x+=1)
      {
      answer.setEqual(answer.add(c.pow(coefficients[x]).multiply((double)multipliers[x])));
      }
    return answer;
    }

  polynomial derivative()                    //  new polynomial that is derivative of this one
    {
    String s="";
    int x, newMult, newCoeff;

    for (x=0;x<terms;x+=1)
      {
      if (multipliers[x]!=0 && coefficients[x]!=0)
        {
        newMult=multipliers[x]*coefficients[x];
        newCoeff=coefficients[x]-1;
        s = s + "+" + newMult + "x^" + newCoeff;
        }
      }
    return new polynomial(s);
    }

  }  //  End of class polynomial

//----------------------------------------------------------------------------------------------