/**************************************************************************
**  Applet to demonstrate how DE manages the polynomial fitting problem. **
**  This applet was programmed using Suresh Srinivasan's SamplingApplet  **
**  (suresh@thomtech.com) as a basis.                                    **
**  Author: Rainer Storn (Graphics), Mikal Keenan (DE)                   **
**  Date:   Oct. 1996                                                    **
**************************************************************************/


import java.awt.*;         // Import all classes from the java.awt package
                           // AWT is the Abstract Window Toolkit. The AWT
                           // contains all GUI classes: Panels, Labels etc.
import java.applet.Applet; // Provides applet specific behaviour
import java.util.Random;   // Provides random number generators
import java.lang.Double;   // Provides wrapper class for double precision


public class DEApplet extends java.applet.Applet
// Abstract class (only partially implemented methods) which provides the
// layout for the applet. This is a subclass of class java.applet.Applet.
{
  static final java.awt.Color BACKGROUNDCOLOR = Color.lightGray;

  String ProblemIdentifier[]   =
  {
    "T4",
    "T8"
  };

  String StrategyIdentifier[] =
  { "Best1Exp", "Rand1Exp", "RandToBest1Exp", "Best2Exp", "Rand2Exp",
    "Best1Bin", "Rand1Bin", "RandToBest1Bin", "Best2Bin", "Rand2Bin",
  };


  DEOptimizer  Optimizer;
  GraphPanel   Animation;      // Responsible for the graphical animation
  DataPanel    Report;         // Report generations, evaluations, minimum
  ScrollPanel  Sliders;        // Sliders for NP, F and CR
  ControlPanel Buttons;        // Push buttons for start, pause etc.
  StatusPanel  Status;         // Shows the applet's current status


  public void init ()
  // Initialize the applet.
  {
    Optimizer   = new DEOptimizer (this);

	Animation   = new GraphPanel (this);   // Create the graphics panel
	Status      = new StatusPanel (this);  // Create the status panel
	Panel P     = new Panel();             // For buttons, report, sliders
	Buttons     = new ControlPanel (this); // Create button controls panel
	Report      = new DataPanel (this);    // Create report panel
    Sliders     = new ScrollPanel (this);  // Create scrollbar panel
	P.setLayout  (new GridLayout (3, 1));  // P layout manager, 3 rows
	P.add (Buttons);                       // Put button panel in 1st row
	P.add (Report);                        // Put report panel in 2nd row
    P.add (Sliders);                       // Put slider panel in 3rd row

	setLayout    (new BorderLayout ());    // Applet layout manager
	add ("North", P);                      // Put multipanel at the top
	add ("Center", Animation);             // Put animation in the center
	add ("South", Status);                 // Put status at the bottom

	layout();                              // Components compute their size

   	Animation.start();                     // Start the graph thread
  }


  public static void main (String args[])
  // The program starts here as in C and C++
  {
	DEApplet applet = new DEApplet();             // Create the applet
	applet.init();                                // Initialize it

	Frame F = new Frame ("DE-Strategies");        // Applet heading
	F.add ("Center", applet);                     // Center applet in frame
	F.resize (500, 400);                          // Set framesize
	F.pack();                                     // ?
	F.show();                                     // Make it visible

	applet.start();                               // Start the applet
  }


  public double Optimize (DEProblem X)
  {
    return Optimizer.Optimize (X);
  }


  public void Idle ()
  {
    Animation.Idle();
	Report.repaint();
	Sliders.Enable();
	Status.Idle();
  }


  public void Start ()
  {
    Animation.Start();
    Sliders.Disable();
    Status.Running();
  }


  public void Pause ()
  {
	Animation.makeNotReady();                          // Suspend animation
	Sliders.Pause();
	Status.Pause();
  }


  public void Resume ()
  {
	Status.Resume();
	Animation.Resume();
	Sliders.Resume();
  }


  public void Stop ()
  {
	Animation.makeNotReady();                          // Suspend animation
	Sliders.Enable();
	Status.Stop();
  }


  public void Done ()
  {
    Buttons.Done();
    Status.Done();
  }


  public String[] GetProblemIdentifiers ()
  {
    return ProblemIdentifier;
  }


  public String[] GetStrategyIdentifiers ()
  {
    return StrategyIdentifier;
  }


  public void GetParameters (DEControls C)
  {
    Sliders.GetParameters (C);
    Buttons.GetParameters (C);
  }


  public void SetProblem (int Index)
  {
    Animation.SetProblem (Index);
    Idle();
  }


  public DEProblem GetProblem ()
  {
    return Animation.GetProblem();
  }


  public void SetStatus (String Text)
  {
    if (Status != null)
      Status.setText (Text);
  }


  public void Repaint ()
  {
    Report.repaint();                                      // Update report
  }


  public void RefreshImage ()
  {
    Animation.RefreshImage();
  }


  public int GetRefresh ()
  {
    return Sliders.GetRefresh();
  }


  public int GetGeneration ()
  {
    return Animation.GetGeneration();
  }


  public int GetEvaluation ()
  {
    return Animation.GetEvaluation();
  }


  public double GetMinimum ()
  {
    return Animation.GetMinimum();
  }
}


class ControlPanel extends Panel
// Defines the user operated control panel
{
  public final static String StartString  = "Start";
  public final static String StopString   = "Stop";
  public final static String PauseString  = "Pause";
  public final static String ResumeString = "Resume";

  public final static Font ButtonFont = new Font ("Dialog", Font.BOLD, 12);
  public final static Font ChoiceFont = new Font ("Dialog", Font.PLAIN, 12);
  public final static Font ErrorFont  = new Font ("TimesRoman", Font.BOLD, 20);

  DEApplet Parent;

  Button   StartButton;                                 // The start button
  Button   PauseButton;                                 // The pause button

  Choice   ProblemList;                                 // Problem control
  Choice   StrategyList;                                // Strategy control

  int      CurrentProblem  = 1;                         // Problem number
  int      CurrentStrategy = 1;                         // Strategy number


  public ControlPanel (DEApplet App)
  // Control panel onstructor of the control panel. It has applet as an
  // argument and hence could be used for different applets.
  {
	Parent = App;
	setLayout (new FlowLayout (FlowLayout.LEFT, 10, 10)); // "best effort" layout

	StartButton = new Button();                  // Create the start button
	StartButton.setFont (ButtonFont);            // Define its font
	StartButton.setLabel (StartString);          // and its text
	add (StartButton);                           // and make it visible

	PauseButton = new Button();                  // Create the pause button
	PauseButton.setFont (ButtonFont);            // Define its font
	PauseButton.setLabel (PauseString);          // and its text
	add (PauseButton);                           // and make it visible

	ProblemList = new Choice();
	ProblemList.setFont (ChoiceFont);
	String[] Identifier = Parent.GetProblemIdentifiers();
	for (int N = Identifier.length, I = 0;  I < N;  I++)
	  ProblemList.addItem (Identifier[I]);       // Put problems into list
	add (ProblemList);                           // Make the list visible

	StrategyList = new Choice();
	StrategyList.setFont (ChoiceFont);
	Identifier = Parent.GetStrategyIdentifiers();
	for (int N = Identifier.length, I = 0;  I < N;  I++)
	  StrategyList.addItem (Identifier[I]);     // Put strategies into list
	add (StrategyList);                         // Make the list visible

	Reset();                                    // ?
	Parent.Status.Idle();
  }


  public boolean action (Event E, Object O)
  // Handles mouse events for the panel.
  {
    if (E.target instanceof Choice)
    {
      if (E.target.equals (ProblemList))              // Selected a problem
      {
        CurrentProblem = ((Choice) (E.target)).getSelectedIndex();
        Parent.SetProblem (CurrentProblem);
      }
      else if (E.target.equals (StrategyList))       // Selected a strategy
      {
	    CurrentStrategy = ((Choice) (E.target)).getSelectedIndex();
        UserReset();
        Parent.Idle();
      }
    }
    else if (E.target instanceof Button)
    {
      if (StartString.equals ((String) O))
      {
	    StartButton.setLabel (StopString);   // Now animation can only stop
	    PauseButton.enable();                // or pause
	    ProblemList.disable();               // No choices during animation
	    StrategyList.disable();              // No choices during animation
	    Parent.Start();
      }
      else if (PauseString.equals ((String) O))
      {
	    PauseButton.setLabel (ResumeString);  // Show: animation can resume
        Parent.Pause();
      }
      else if (ResumeString.equals ((String) O))
      {
	    PauseButton.setLabel (PauseString);   // Show: animation can pause
	    Parent.Resume();
	  }
      else if (StopString.equals ((String) O))
      {
	    Reset();
        Parent.Stop();
	  }
    }
	repaint();                                         // Redraw everything
	return true;
  }


  private void UserReset ()
  { StartButton.setLabel (StartString);       // Start button shows "start"
	PauseButton.setLabel (PauseString);       // Pause button shows "pause"
	StartButton.enable();
	PauseButton.disable();
  }


  public void GetParameters (DEControls C)
  {
    C.Problem  = CurrentProblem;
    C.Strategy = CurrentStrategy;
  }


  public void Done ()
  {
    Reset();
  }

  public void Reset ()
  // Reset button labels
  {
	UserReset();
	ProblemList.enable();                      // Enable problem selection
	StrategyList.enable();                     // Enable strategy selection
	repaint();                                 // Redraw everything
  }
}// End class ControlPanel


class DataPanel extends Panel
// Defines the output panel which shows the current data
{
  public final static String GenString   = "Generation :  ";
  public final static String EvalString  = "Evaluations:  ";
  public final static String ValueString = "Minimum    :  ";

  public final static Font DataFont = new Font ("Dialog", Font.PLAIN, 10);

  DEApplet Parent;

  Image    OffscreenImage;             // This is where the image is stored
  Graphics OffscreenGraphics;

  private int FontHeight = 10;
  private int Gutter     = 5;
  private int NewLine    = FontHeight + Gutter;

  private int X  = 5;
  private int Y1 = 18;
  private int Y2 = Y1 + NewLine;
  private int Y3 = Y2 + NewLine;

  boolean Initialized = false;


  public DataPanel (DEApplet App)
  // Constructor
  {
	Parent = App;
  }


  public void paint (Graphics G)
  // Paints the current optimization data
  { // Get the values to display
    Dimension Area = size();

    int Width = Area.width;
    int Height = Area.height;

	if (! Initialized)
    {
	  OffscreenImage = createImage (Width, Height);
	  OffscreenGraphics = OffscreenImage.getGraphics();
	  Initialized = true;
	}

	OffscreenGraphics.setColor (DEApplet.BACKGROUNDCOLOR);   // Like applet
	OffscreenGraphics.fill3DRect (0, 0, Width - 1, Height - 1, true); // ?
	OffscreenGraphics.setColor (Color.blue);                 // Text color
	OffscreenGraphics.drawString (GenString    + Parent.GetGeneration(), X, Y1);
	OffscreenGraphics.drawString (EvalString + Parent.GetEvaluation(), X, Y2);
	OffscreenGraphics.drawString (ValueString  + Parent.GetMinimum(),    X, Y3);

	G.drawImage (OffscreenImage, 0, 0, this);     // Display the data panel
  }
}// End class DataPanel


class ScrollPanel extends Panel
// Defines the user operated scroll panel and uses
// the Panel class as "mother".
{
  public final static Font ScrollFont = new Font ("Dialog", Font.PLAIN, 12);

  DEApplet Parent;

  TextField NPText;                       // Text values for the scrollbars
  TextField FText;
  TextField CrText;
  TextField RangeText;

  Scrollbar NPScroller;                   // Scrollbars for NP, F and Cr
  Scrollbar FScroller;
  Scrollbar CrScroller;
  Scrollbar RangeScroller;

  int NP;                                 // The actual control variables

  double F;
  double Cr;
  double Range;

  Double FObj;
  Double CrObj;
  Double RangeObj;


  public ScrollPanel (DEApplet App)
  // Scroll panel constructor. It has applet as an argument and hence could
  // be used for different applets.
  {
	Parent = App;

	NP      = 60;
    F       = 0.8;
    Cr      = 1.0;
    Range   = 100.0;

	Panel NPPanel = new Panel();               // Panel for slider and text
 // Scrollbar's initial value = 50, height = 10 pixels, range 5..200
    NPScroller    = new Scrollbar (Scrollbar.HORIZONTAL,NP,10,5,200);
	NPText        = new TextField (10);        // Create the NP text field
    NPText.setText ("NP: " + String.valueOf (NP)); // Show initial value
    NPPanel.setLayout (new GridLayout (2, 1));     // Slider below the text
	NPPanel.add (NPText);                          // Text above
    NPPanel.add (NPScroller);                      // Scroller below text

	Panel FPanel = new Panel();
	FScroller    = new Scrollbar (Scrollbar.HORIZONTAL, (int) (F*100.),10,0,100);
    FText        = new TextField (10);
    FText.setText ("F: " + FObj.toString (F));
	FPanel.setLayout (new GridLayout (2, 1));
	FPanel.add (FText);
    FPanel.add (FScroller);

	Panel CrPanel = new Panel();
	CrScroller    = new Scrollbar (Scrollbar.HORIZONTAL, (int) (Cr*100.0),10,0,100);
    CrText        = new TextField (10);
    CrText.setText ("Cr: " + CrObj.toString (Cr));
	CrPanel.setLayout (new GridLayout (2, 1));
	CrPanel.add (CrText);
    CrPanel.add (CrScroller);

	Panel RangePanel = new Panel();
	RangeScroller    = new Scrollbar (Scrollbar.HORIZONTAL, (int) (Range),10,1,500);
    RangeText        = new TextField (10);
    RangeText.setText ("Init: " + RangeObj.toString (Range));
	RangePanel.setLayout (new GridLayout (2, 1));
	RangePanel.add (RangeText);
    RangePanel.add (RangeScroller);

    setLayout (new FlowLayout (FlowLayout.LEFT, 10, 10)); // Left justified
    add (RangePanel);                                     // Add subpanels
    add (NPPanel);
    add (FPanel);
    add (CrPanel);
  }


  public boolean handleEvent (Event E)
  // Handles the scrollbar actions. Note: overriding the Scrollbar
  // class's own event handler.
  {
	if (E.target.equals (NPScroller))              // Altered the NP slider
    {
      NP = ((Scrollbar)E.target).getValue();
      NPText.setText ("NP: " + String.valueOf (NP));
	}
    else if (E.target.equals (FScroller))
    {
      F = (double) (((Scrollbar)E.target).getValue ()) * 0.01;
      FText.setText ("F: " + FObj.toString (F));
	}
    else if (E.target.equals (CrScroller))
    {
      Cr = (double) (((Scrollbar)E.target).getValue ()) * 0.01;
      CrText.setText ("Cr: " + CrObj.toString (Cr));
	}
    else if (E.target.equals (RangeScroller))
    {
      Range = (double) (((Scrollbar)E.target).getValue ()) * 1.0;
      RangeText.setText ("Init: " + CrObj.toString (Range));
	}

	repaint();                                         // Redraw everything

	return super.handleEvent (E);    // Propagate message to the superclass
  }


  public void Enable ()
  // Activate all sliders
  {
	NPScroller.enable();
    CrScroller.enable();
    FScroller.enable();
    RangeScroller.enable();
  }


  public void Disable ()
  // Deactivate all sliders
  {
    NPScroller.disable();
    CrScroller.disable();
    FScroller.disable();
    RangeScroller.disable();
  }


  public void Pause ()
  // Activate Cr and F manipulation during pause
  {
    CrScroller.enable();
    FScroller.enable();
  }


  public void Resume ()
  // Deactivate Cr and F manipulation on resume
  {
    CrScroller.disable();
    FScroller.disable();
  }


  public void GetParameters (DEControls C)
  {
    C.NP      = NP;
    C.F       = F;
    C.Cr      = Cr;
    C.Range   = Range;
    C.Refresh = 1;                // Fix
  }


  public int GetRefresh ()
  {
    return 1;                     // Fix
  }
}// End class ScrollPanel


class GraphPanel extends Panel implements Runnable
// Implementation of the interface Runnable
{
  DEApplet    Parent;

  Thread      Action;

  DEProblem   Problem[];
  int         Current = 0;

  boolean     Running = false;
  boolean     ReadyToPaint = true;


  public GraphPanel (DEApplet App)
  // Constructor
  {
	Parent = App;
  }


  public void start ()
  // Start the thread (old version)
  {
	if (Action == null)
    { String[] Identifier = Parent.GetProblemIdentifiers();
      int N = Identifier.length;
	  Problem = new DEProblem[N];
	  Dimension Area = size();
	  for (int I = 0;  I < N;  I++)
      {
		try
        {
		  Class C = Class.forName (Identifier[I]);
		  Problem[I] = (DEProblem) (C.newInstance());
		  Problem[I].Init (Parent, Area);
		  Problem[I].InitGraphics();
		}
		catch (Exception E)
		{
		  // Should we do something here?
		};
	  }

	  Action = new Thread (this);             // Instantiate the new thread
	  Action.start();                         // Start it
	}
  }


  public void stop ()
  // Stop the thread when you leave the applet.                             **
  {
	Action = null;
  }


  public void run ()
  // Let it run! The animation is taking place here!
  {
	while (Action != null)
    {
	  if (! Running)
      {
		repaint();
		Action.suspend();
	  }
	  repaint();
	  Parent.Repaint();

	  try
      {
        Action.sleep (DEProblem.NAPTIME);  // Suspend animation for NAPTIME
      }
      catch (Exception E)
      {
        // In case the sleep command fails
      };

//    ReadyToPaint = false;    ???
	  ReadyToPaint = true;
	  if (Problem[Current].Completed())
	  { makeNotReady();
		Parent.Done();
	  }
	}
  }


  public synchronized void makeReady ()
  {
	Running = true;
  }


  public synchronized void makeNotReady ()
  {
	Running = false;
  }


  // Some helper methods

  public void initialize ()
  {
	ReadyToPaint = true;
	Problem[Current].InitGraphics();
  }


  public void SetProblem (int Index)
  {
    Current = Index;
  }


  public void Idle ()
  {
	initialize();                      // Initialize new drawing
	makeNotReady();                    // Suspend the animation
	repaint();                         // Make it visible
  }


  public void Start ()
  {
	initialize();                      // Reset polynomial to start setting
	makeReady();                       // Wake up the animation
	Action.resume();                   // and get it going
  }


  public void Resume ()
  {
	makeReady();                       // Wake the animation up
	Action.resume();                   // and get it going
  }


  public void RefreshImage ()
  {
    Problem[Current].RefreshImage();
  }


  public DEProblem GetProblem ()
  {
    return Problem[Current];
  }


  public int GetGeneration ()
  {
	return Problem[Current].GetGeneration();
  }


  public int GetEvaluation ()
  {
	return Problem[Current].GetEvaluation();
  }


  public double GetMinimum ()
  {
	return Problem[Current].GetValue();
  }


  public void GetParameters (DEControls C)
  {
    C.D = Problem[Current].GetLength();
  }


  public void update (Graphics G)
  // Overriding update() reduces flicker. The normal update() method clears
  // the screen before it repaints and hence causes flicker. We dont like
  // this and leave out the screen clearing.
  {
	paint (G);
  }


  public void paint (Graphics G)
  {
	if (ReadyToPaint && (Problem[Current].OffscreenGraphics != null))
	  G.drawImage (Problem[Current].OffscreenImage, 0, 0, null);
  }
}


class StatusPanel extends Label
// The little status panel at the bottom of the applet
{
  public final static String RunningString   = "Running...";
  public final static String PausedString    = "Paused...";
  public final static String CompletedString = "Completed...";
  public final static String NullString      = "";

  public final static Font LabelFont = new Font ("Dialog", Font.PLAIN, 10);

  DEApplet Parent;


  public StatusPanel (DEApplet App)
  {
	Parent = App;
	setFont (LabelFont);
  }


  public void Idle ()
  {
	setText (NullString);                          // Status shows nothing
  }


  public void Running ()
  {
	setText (RunningString);                       // Show status "running"
  }


  public void Pause ()
  {
  	setText (PausedString);                        // Show status "paused"
  }


  public void Resume ()
  {
	setText (RunningString);                       // Show status "running"
  }

  public void Stop ()
  {
    setText (NullString);
  }

  public void Done ()
  {
    setText (CompletedString);
  }
}// StatusPanel


class DEControls
// Control variables
{
       int MaxD     = 17;
       int MaxN     = 300;

      long Seed     = 0;

       int Strategy = 1;
       int Problem  = 1;

       int D        = MaxD;
       int NP       = 60;
    double F        = 0.9;
    double Cr       = 1.0;
    double Range    = 100.0;
       int Refresh  = 1;                     // Animation refresh rate
}


class DEOptimizer extends DEControls
// The optimizer
{
  DERandom RNG        = new DERandom();

  DEApplet Parent;

DEStrategy Strategem[];

       int Generation = 0;
       int Evaluation = 0;
       int MinIndex   = 0;

    double Temp[]     = new double [MaxD];
    double Best[]     = new double [MaxD];
    double GenBest[]  = new double [MaxD];
    double Cost[]     = new double [MaxN];
    double MinCost    = Double.MAX_VALUE;

    double P1[][]     = new double [MaxN][MaxD];
    double P2[][]     = new double [MaxN][MaxD];

    double G0[][];
    double G1[][];


  public DEOptimizer (DEApplet App)
  {
	Parent = App;

    String S[] = Parent.GetStrategyIdentifiers();
    Strategem = new DEStrategy [S.length];
    for (int N = S.length, I = 0;  I < N;  I++)
      try
      {
	    Class C = Class.forName ("DE" + S[I]);
	    Strategem[I] = (DEStrategy) C.newInstance();
	    Strategem[I].Init (RNG);
	  }
	  catch (Exception E)
	  {
	    System.err.println (E);  // Fix
	  };
  }


  private void Assign (double[] To, double[] From)
  // (Slow) assignment operator.  Java is Java, C/C++ is C/C++...
  // JGL does it using 'for'.
  {
    int I = D;
    while (0 < I--)
      To[I] = From[I];
  }


  public double Optimize (DEProblem Driver)
  {
    Driver.GetParameters ((DEControls) this).RefreshImage();

    if ((Evaluation = Driver.GetEvaluation()) > 0)              // Optimize
    {
      int Iterations = Refresh;
      while (Iterations-- > 0)
      {
        for (int I = 0;  I < NP;  I++)
        {
          Assign (Temp, G0[I]);

          int R1, R2, R3, R4, R5;

          do R1 = RNG.Next (NP);
          while (R1 == I);

          do R2 = RNG.Next (NP);
          while ((R2 == I) || (R2 == R1));

          do R3 = RNG.Next (NP);
          while ((R3 == I) || (R3 == R1) || (R3 == R2));

          do R4 = RNG.Next (NP);
          while ((R4 == I) || (R4 == R1) || (R4 == R2) || (R4 == R3));

          do R5 = RNG.Next (NP);
          while ((R5 == I) || (R5 == R1) || (R5 == R2) || (R5 == R3) || (R5 == R4));

          Strategem[Strategy].Apply (F, Cr, D, Temp, GenBest,
                                   G0[R1], G0[R2], G0[R3], G0[R4], G0[R5]);

          double TestCost = Driver.Evaluate (Temp, D);

          if (TestCost <= Cost[I])                     // Better solution?
          {
            Assign (G1[I], Temp);
            if ((Cost[I] = TestCost) < MinCost)        // Propagate the new
            {                                          // A new minimum...
              MinCost = TestCost;                      // Reset MinCost
              Assign (Best, Temp);
              MinIndex = I;
            }
          }
          else
            Assign (G1[I], G0[I]);                     // Propagate the old
        }// for

        Assign (GenBest, Best);           // Save current generation's best

        double GX[][] = G0;               // Swap population pointers
        G0 = G1;
        G1 = GX;

        Generation++;
      }// loop
    }
    else                                                      // Initialize
    {
      int I = NP;
      while (--I >= 0)
      {
        double[] X = P1[I];
        int J = D;
        while (--J >= 0)
          X[J] = RNG.Next (Range);
        Cost[I] = Driver.Evaluate (X, D);
      }
      MinCost  = Cost[0];
      MinIndex = 0;
      int J = NP;
      while (--J < 0)
      {
        double X = Cost[J];
        if (X < MinCost)
        {
          MinCost = X;
          MinIndex = J;
        }
      }

      Assign (Best, P1[MinIndex]);
      Assign (GenBest, Best);

      G0 = P1;   // Generation t
      G1 = P2;   // Generation t+1
    }

    Assign (Driver.GetBest(), Best);

    return MinCost;
  }
}


class DERandom extends Random
// Random number generator.
{
  public DERandom ()
  { SetSeed (0);
  }


  public void SetSeed (long Seed)
  { if (Seed == 0)
      Seed = (long) System.currentTimeMillis();
    setSeed (Seed);
  }


  public final int Next (int Max)
  {
    return (int) (nextDouble() * (double) Max);
  }


  public final double Next (double Range)
  {
    return Range * (1.0 - 2.0 * nextDouble());
  }
}


abstract class DEStrategy
{
   protected DERandom RNG;

   protected int I, Counter;

   abstract
   public void Apply (double F, double Cr, int N, double[]X, double[]GenBest,
                double[]R1, double[]R2, double[]R3, double[]R4, double[]R5);

   public void Init (DERandom R)
   { RNG = R;
   }

   protected final void Prepare (int N)
   {
     I = RNG.Next (N);
     Counter = 0;
   }
}


class DEBest1Exp extends DEStrategy
{
  public void Apply (double F, double Cr, int N, double[]X, double[]GenBest,
  double[]R1, double[]R2, double[]R3, double[]R4, double[]R5)
  {
    Prepare (N);
    do
    { X[I] = GenBest[I] + F * (R2[I] - R3[I]);
      I = ++I % N;
    } while ((RNG.nextDouble() < Cr) && (++Counter < N));
  }
}


class DERand1Exp extends DEStrategy
{
  public void Apply (double F, double Cr, int N, double[]X, double[]GenBest,
  double[]R1, double[]R2, double[]R3, double[]R4, double[]R5)
  {
    Prepare (N);
    do
    { X[I] = R1[I] + F * (R2[I] - R3[I]);
      I = ++I % N;
    } while ((RNG.nextDouble() < Cr) && (++Counter < N));
  }
}


class DERandToBest1Exp extends DEStrategy
{
  public void Apply (double F, double Cr, int N, double[]X, double[]GenBest,
  double[]R1, double[]R2, double[]R3, double[]R4, double[]R5)
  {
    Prepare (N);
    do
    { X[I] += F * ((GenBest[I] - X[I]) + (R1[I] - R2[I]));
      I = ++I % N;
    } while ((RNG.nextDouble() < Cr) && (++Counter < N));
  }
}


class DEBest2Exp extends DEStrategy
{
  public void Apply (double F, double Cr, int N, double[]X, double[]GenBest,
  double[]R1, double[]R2, double[]R3, double[]R4, double[]R5)
  {
    Prepare (N);
    do
    { X[I] = GenBest[I] + F * (R1[I] + R2[I] - R3[I] - R4[I]);
      I = ++I % N;
    } while ((RNG.nextDouble() < Cr) && (++Counter < N));
  }
}


class DERand2Exp extends DEStrategy
{
  public void Apply (double F, double Cr, int N, double[]X, double[]GenBest,
  double[]R1, double[]R2, double[]R3, double[]R4, double[]R5)
  {
    Prepare (N);
    do
    { X[I] = R5[I] + F * (R1[I] + R2[I] - R3[I] - R4[I]);
      I = ++I % N;
    } while ((RNG.nextDouble() < Cr) && (++Counter < N));
  }
}


// Essentially the same strategies but with BINOMIAL CrOSSOVER

class DEBest1Bin extends DEStrategy
{
  public void Apply (double F, double Cr, int N, double[]X, double[]GenBest,
  double[]R1, double[]R2, double[]R3, double[]R4, double[]R5)
  {
    Prepare (N);
    while (Counter++ < N)
    { if ((RNG.nextDouble() < Cr) || (Counter == N))
        X[I] = GenBest[I] + F * (R2[I] - R3[I]);
      I = ++I % N;
    }
  }
}


class DERand1Bin extends DEStrategy
{
  public void Apply (double F, double Cr, int N, double[]X, double[]GenBest,
  double[]R1, double[]R2, double[]R3, double[]R4, double[]R5)
  {
    Prepare (N);
    while (Counter++ < N)
    { if ((RNG.nextDouble() < Cr) || (Counter == N))
	    X[I] = R1[I] + F * (R2[I] - R3[I]);
      I = ++I % N;
    }
  }
}


class DERandToBest1Bin extends DEStrategy
{
  public void Apply (double F, double Cr, int N, double[]X, double[]GenBest,
  double[]R1, double[]R2, double[]R3, double[]R4, double[]R5)
  {
    Prepare (N);
    while (Counter++ < N)
    { if ((RNG.nextDouble() < Cr) || (Counter == N))
	    X[I] += F * ((GenBest[I] - X[I]) + (R1[I] - R2[I]));
      I = ++I % N;
    }
  }
}


class DEBest2Bin extends DEStrategy
{
  public void Apply (double F, double Cr, int N, double[]X, double[]GenBest,
  double[]R1, double[]R2, double[]R3, double[]R4, double[]R5)
  {
    Prepare (N);
    while (Counter++ < N)
    { if ((RNG.nextDouble() < Cr) || (Counter == N))
	    X[I] = GenBest[I] + F * (R1[I] + R2[I] - R3[I]- R4[I]);
      I = ++I % N;
    }
  }
}


class DERand2Bin extends DEStrategy
{
  public void Apply (double F, double Cr, int N, double[]X, double[]GenBest,
  double[]R1, double[]R2, double[]R3, double[]R4, double[]R5)
  {
    Prepare (N);
    while (Counter++ < N)
    { if ((RNG.nextDouble() < Cr) || (Counter == N))
	    X[I] = R5[I] + F * (R1[I] + R2[I] - R3[I] - R4[I]);
      I = ++I % N;
    }
  }
}


abstract class DEProblem
// Declares the methods that all subtypes must have.  Not all of them,
// however, are implemented in the abstract class.                                                **
{
  public static final int NAPTIME = 50;

// The axes, and tolerance scheme are computed once and plotted into a
// static image (staticI). The sample data is plotted into a background
// image and copied into the Animation's gc to avoid flicker.

     Image StaticImage = null;              // Portions that do not change
  Graphics StaticGraphics;
     Image OffscreenImage;
  Graphics OffscreenGraphics;

       int Generation;
       int Evaluations;
    double Value;

  DEApplet Parent;

    double Best[];
       int D;


  int X;                                   // Graphics stuff
  int Y;
  int W;
  int H;

  double MinX;                             // Relative coordinates
  double MaxX;
  double MinY;
  double MaxY;

  int    AbsMinX;                            // Absolute coordinates
  int    AbsMaxX;
  int    AbsMinY;
  int    AbsMaxY;

  int    XTics  = 4;                       // Number of tics in X-direction
  int    YTics  = 8;                       // Number of tics in Y-direction


/*
  Description of the graphics screen

             AbsMinX                    AbsMaxX
            ------------------------------------W
           |
  AbsMinY  |     --------------------------
           |    |
           |    |
           |    |     ((AbsMaxX-AbsMinX)/2, (AbsMaxY-AbsMinY)/2)
           |    |      is center of drawing area
           |    |
  AbsMaxY  |    |
           |
           H
*/


  abstract boolean Completed();
  abstract double Evaluate (double[] X, int D);
  abstract void PreparePlot (Graphics G);
  abstract void Plot (Graphics G);

  public void Init (DEApplet App, Dimension Area)
  // Set some parameters
  {
	Parent       = App;

    X            = 0;
    Y            = 0;
	W            = Area.width;      // Absolute width of the graphics area
	H            = Area.height;     // Absolute height of the graphics area

    AbsMinX      = W / 8;           // Compute some variables
    AbsMaxX      = W * 7 / 8;
    AbsMinY      = H / 8;
    AbsMaxY      = H * 7 / 8;

	MinX         = -1.5;            // Mimimum abscissa value
	MaxX         =  1.5;
	MinY         = -3;              // Minimum ordinate value
	MaxY         =  3;
  }


  protected final int AbsX (double X)
  // Transform relative X-values in absolute ones
  {
    return AbsMaxX + (int) (((double)(AbsMinX-AbsMaxX)) * ((MaxX-X)/(MaxX-MinX)));
  }


  protected final int AbsY (double Y)
  // Transform relative Y-values in absolute ones
  {
    return AbsMinY + (int) (((double)(AbsMaxY-AbsMinY)) * ((MaxY-Y)/(MaxY-MinY)));
  }


  public void InitGraphics ()
  // Initializes background graphics, computes the tolerance scheme, etc.                   **
  {
    Evaluations = 0;
    Generation = 0;

	if (StaticImage == null) // Should only need to do this the 1st time around
    {
	  StaticImage = Parent.createImage (W, H);
	  StaticGraphics = StaticImage.getGraphics();
	  StaticGraphics.setColor (DEApplet.BACKGROUNDCOLOR);
	  StaticGraphics.fill3DRect (X, Y, W - 1, H - 1, true);
	  PreparePlot (StaticGraphics);
	}
	OffscreenImage = Parent.createImage (W, H);
	OffscreenGraphics = OffscreenImage.getGraphics();
	OffscreenGraphics.drawImage (StaticImage, 0, 0, null);
  }


  public void RefreshImage()
  {
    OffscreenGraphics.drawImage (StaticImage, 0, 0, null);         // Clear
	Plot (OffscreenGraphics);
  }


  public final DEProblem GetParameters (DEControls C)
  {
    Parent.GetParameters (C);
    C.D = D;
    return this;
  }


  public final int GetGeneration ()
  {
    return Generation;
  }


  public final int GetEvaluation ()
  {
    return Evaluations;
  }


  public final double[] GetBest ()
  {
    return Best;
  }

  public final double GetValue ()
  {
    return Value;
  }

  public final int GetLength ()
  {
    return D;
  }
}


class TNPolynomial extends DEProblem
{
  int EvaluationSamples;
  int PlottingSamples;
  int ToleranceSamples = 300;

  double LowerLimit;


  public boolean Completed ()
  // Runs the evolution.
  {
    Value = Parent.Optimize (this);
    Generation += Parent.GetRefresh();
    return Value <= 1.0e-6;
  }


  public double Evaluate (double Temp[], int D)
  // The actual objective function consists of the sum of squared
  // errors, where an error is the magnitude of deviation of the
  // polynomial at a specific argument value.
  {
    double Y = 0.0;
    double X = -1.0;
    double Z = 0.0, Aux;

    double dX = 2 / ((double) EvaluationSamples);
    for (int I = 0;  I <= EvaluationSamples;  I++, X += dX)
    {
      if ((Z = Polynomial (Temp, X, D)) > 1.0)
      {
        Aux = 1.0 - Z;
        Y += Aux * Aux;
      }
      else if (Z < -1.0)
      {
        Aux = Z - 1.0;
        Y += Aux * Aux;
      }
    }

    Aux = LowerLimit - Z;
    Aux *= Aux;

    if (Polynomial (Temp, -1.2, D) < LowerLimit)
      Y += Aux;

    if (Polynomial (Temp, +1.2, D) < LowerLimit)
      Y += Aux;

    Evaluations++;

    return Y;
  }


  public double Polynomial (double Temp[], double X, int D)
  // Evaluate the current polynomial
  {
    double Y = Temp[0];
    for (int J = 1;  J < D;  J++)
	  Y = X * Y + Temp[J];

    return Y;
  }


  public void Plot (Graphics G)
  // Plots the current polynomial
  {
	G.setColor (Color.black);
    double Coefficient = (MaxX - MinX) / ((double) PlottingSamples);
    double X1 = MinX, X2;
    for (int I = 1;  I <= PlottingSamples;  I++, X1 = X2)
    {
      X2 = MinX + ((double)I) * Coefficient;
	  G.drawLine (AbsX (X1), AbsY (Polynomial (Best, X1, D)),
	               AbsX (X2), AbsY (Polynomial (Best, X2, D)));
    }
  }


  protected void PreparePlot (Graphics Static)
  {
    PlotAxes (StaticGraphics);
    PlotTolerance (StaticGraphics);
  }


  public void PlotAxes (Graphics G)
  // Plot coordinate system in which polynomial will be plotted.
  {
	int TickHeight = 3;

	G.setColor (Color.black);

    int Static0 = AbsY (0.0);
	G.drawLine (AbsX (MinX), Static0, AbsX (MaxX), Static0);      // X axis

 	Static0 = AbsX (0.0);
 	G.drawLine (Static0, AbsY (MinY), Static0, AbsY (MaxY));      // Y axis

    Static0 = AbsY (0.0);
    int BasePos = AbsX (MinX);
    int Static1 = Static0;
    int Static2 = Static0 - TickHeight;

	double Increment = ((double) (AbsMaxX - AbsMinX) / (double) XTics) + 0.25;
	for (int I = 0;  I <= XTics;  I++)                       // X axis tics
	{ int X = BasePos + (int) (I * Increment);
	  G.drawLine (X, Static1, X, Static2);
    }

    BasePos = AbsY (MinY);
    Static0 = AbsX (0.0);
    Static1 = Static0 - 2;
    Static2 = Static0 + 2;

	Increment = ((double) (AbsMaxY - AbsMinY) / (double) YTics);
	for (int I = 0;  I <= YTics;  I++)                       // Y axis tics
	{ int Y = BasePos - (int) (I * Increment);
	  G.drawLine (Static1, Y, Static2, Y);
    }

	G.setFont (new Font ("Helvetica", Font.PLAIN, 10));      // Tic labels

	Static0 = AbsY (0) - 10;
	double X = MinX;

    Increment = (double) (MaxX - MinX) / (double) XTics;
	for (int I = 0;  I <= XTics;  I++, X += Increment)
    {
	  Double DblObj = new Double (X);
	  G.drawString (DblObj.toString(), AbsX (X) - 10, Static0);
	}

	Double DblObj = new Double (MaxY);
	G.drawString (DblObj.toString(), AbsX (0), AbsY (MaxY) - 8);
  }


  protected final double UpperTolerance (double X)
  // Compute the upper part of the tolerance scheme.
  {
    if ((X < -1) || (X > 1))
      return 10;

    if ((X > -1) || (X < 1))
      return 1;

    return 10;
  }


  protected final double LowerTolerance (double X)
  // Computes the lower part of the tolerance scheme.
  {
    if ((X < -1.2) || (X > 1.2))
      return 10;

    if ((X > -1.2) || (X < 1.2))
      return -1;

    return 10;
  }


  public void PlotTolerance (Graphics G)
  // Plot the tolerance scheme
  {
	G.setColor (Color.red);          // Plot upper part of tolerance scheme

    double Coefficient = (MaxX - MinX) / ((double) ToleranceSamples);
    double D1 = MinX, D2;
    for (int I = 1;  I <= ToleranceSamples;  I++, D1 = D2)
    {
      D2 = MinX + ((double) I) * Coefficient;
	  G.drawLine (AbsX (D1), AbsY (UpperTolerance (D1)),
	               AbsX (D2), AbsY (UpperTolerance (D2)));
    }

    D1 = MinX;                       // Plot lower part of tolerance scheme
    for (int I = 1;  I <= ToleranceSamples;  I++, D1 = D2)
    {
      D2 = MinX + ((double) I) * Coefficient;
	  G.drawLine (AbsX (D1), AbsY (LowerTolerance (D1)),
	               AbsX (D2), AbsY (LowerTolerance (D2)));
    }
  }
}


class T4 extends TNPolynomial
// Objective function which uses a tolerance scheme that can
// be fitted by a Chebychev polynomial T4.
{
  public T4 ()
  {
    Best = new double [D = 5];
    LowerLimit = 5.9;
    EvaluationSamples = 60;
    PlottingSamples = 30;
  }
}


class T8 extends TNPolynomial
// Objective function which uses a tolerance scheme that can
// be fitted by a Chebychev polynomial T8.
{
  public T8 ()
  {
    Best = new double [D = 9];
    LowerLimit = 72.661;
    EvaluationSamples = 60;
    PlottingSamples = 60;
  }
}