// FFTApp.java
import java.awt.*;
import java.awt.event.*;
import java.text.DecimalFormat;

public class FFTApp extends Frame implements ActionListener, FocusListener,
                                             ItemListener
{
   private static DecimalFormat freqFormat = new DecimalFormat("#,##0.##");
   private static DecimalFormat coefFormat = new DecimalFormat("#,##0.######");

   private FFTStarter fs;
   private FFTGraph graph;
   private FFTSpectrum spectrum;
   private boolean runsFromApplet, oneCompleted = false;
   private TextField letterField, sizeField, periodField, coefField,
                     filterField, timeField;
   private Button compute;
   private TextArea resultsArea;
   private char character;
   private int sampleSize, coefficients, numberOfHarmonics;
   private double period, filterFreq = 3000.00;
   private Font font = new Font("Monospaced", Font.PLAIN, 12);
   private Checkbox filterBox, overlayBox, showFFTBox, showNormalBox;
   private Cursor defaultCursor, waitCursor;
   private double[] x, y, yfft;

   public FFTApp(FFTStarter _fs, boolean _runsFromApplet)
   {
      super("Discrete FFT for Letter Bit Patterns");
      fs = _fs;
      runsFromApplet = _runsFromApplet;
      setBackground(SystemColor.control);
      defaultCursor = new Cursor(Cursor.DEFAULT_CURSOR);
      waitCursor = new Cursor(Cursor.WAIT_CURSOR);

      letterField = new TextField(10);
      letterField.addFocusListener(this);
      letterField.setBackground(Color.white);
      letterField.setText("a");
      sizeField = new TextField(10);
      sizeField.addFocusListener(this);
      sizeField.setBackground(Color.white);
      sizeField.setText("128");
      periodField = new TextField(10);
      periodField.addFocusListener(this);
      periodField.setBackground(Color.white);
      periodField.setText("0.01");
      coefField = new TextField(10);
      coefField.addFocusListener(this);
      coefField.setBackground(Color.white);
      coefField.setText("15");
      filterField = new TextField(10);
      filterField.addFocusListener(this);
      filterField.setBackground(Color.white);
      filterField.setText("3000.00");

      Panel inputPanel = new Panel();
      inputPanel.setLayout(new GridBagLayout());
      GridBagConstraints gbc = new GridBagConstraints();

      gbc.insets = new Insets(0, 5, 0, 5);
      gbc.gridwidth = 1;
      gbc.weightx = 0;
      gbc.fill = GridBagConstraints.HORIZONTAL;
      inputPanel.add(new Label("ASCII Character:"), gbc);
      gbc.gridwidth = GridBagConstraints.REMAINDER;
      gbc.weightx = 100;
      gbc.fill = GridBagConstraints.HORIZONTAL;
      inputPanel.add(letterField, gbc);

      gbc.gridwidth = 1;
      gbc.weightx = 0;
      inputPanel.add(new Label("Sample Size (n):"), gbc);
      gbc.gridwidth = GridBagConstraints.REMAINDER;
      gbc.weightx = 100;
      gbc.fill = GridBagConstraints.HORIZONTAL;
      inputPanel.add(sizeField, gbc);

      gbc.gridwidth = 1;
      gbc.weightx = 0;
      inputPanel.add(new Label("Period (sec):"), gbc);
      gbc.gridwidth = GridBagConstraints.REMAINDER;
      gbc.weightx = 100;
      gbc.fill = GridBagConstraints.HORIZONTAL;
      inputPanel.add(periodField, gbc);

      gbc.gridwidth = 1;
      gbc.weightx = 0;
      inputPanel.add(new Label("Coefficients:"), gbc);
      gbc.gridwidth = GridBagConstraints.REMAINDER;
      gbc.weightx = 100;
      gbc.fill = GridBagConstraints.HORIZONTAL;
      inputPanel.add(coefField, gbc);

      gbc.gridwidth = 1;
      gbc.weightx = 0;
      inputPanel.add(new Label("Filter Frequency (Hz): "), gbc);
      gbc.gridwidth = GridBagConstraints.REMAINDER;
      gbc.weightx = 100;
      gbc.fill = GridBagConstraints.HORIZONTAL;
      inputPanel.add(filterField, gbc);

      filterBox = new Checkbox("Apply Filter");
      compute = new Button("Compute");
      compute.addActionListener(this);
      Panel computePanel = new Panel();
      computePanel.setLayout(new FlowLayout());
      computePanel.add(filterBox);
      computePanel.add(compute);

      Panel combinePanel = new Panel();
      combinePanel.setLayout(new BorderLayout());
      combinePanel.add("North", inputPanel);
      combinePanel.add("South", computePanel);

      spectrum = new FFTSpectrum();
      Panel spectrumPanel = new Panel();
      spectrumPanel.setLayout(new GridBagLayout());
      gbc.insets = new Insets(0, 5, 5, 5);
      gbc.gridwidth = GridBagConstraints.REMAINDER;
      gbc.weightx = 100;
      gbc.weighty = 100;
      gbc.fill = GridBagConstraints.BOTH;
      spectrumPanel.add(spectrum, gbc);

      Panel topPanel = new Panel();
      topPanel.setLayout(new GridLayout(1, 2));
      topPanel.add(new Box(combinePanel, "User Input", Box.LEFT));
      topPanel.add(new Box(spectrumPanel, "RMS Amplitude", Box.LEFT));

      resultsArea = new TextArea("", 15, 50, TextArea.SCROLLBARS_BOTH);
      resultsArea.setEditable(false);
      resultsArea.setBackground(Color.white);
      resultsArea.setFont(font);

      Panel resultsPanel = new Panel();
      resultsPanel.setLayout(new GridBagLayout());
      gbc.insets = new Insets(0, 5, 5, 5);
      gbc.gridwidth = GridBagConstraints.REMAINDER;
      gbc.weightx = 100;
      gbc.weighty = 100;
      gbc.fill = GridBagConstraints.BOTH;
      resultsPanel.add(resultsArea, gbc);

      graph = new FFTGraph();
      Panel graphicsPanel = new Panel();
      graphicsPanel.setLayout(new GridBagLayout());
      gbc.insets = new Insets(0, 5, 5, 5);
      gbc.gridwidth = GridBagConstraints.REMAINDER;
      gbc.weightx = 100;
      gbc.weighty = 100;
      gbc.fill = GridBagConstraints.BOTH;
      graphicsPanel.add(graph, gbc);

      Panel midPanel = new Panel();
      midPanel.setLayout(new GridLayout(1, 2));
      midPanel.add(new Box(resultsPanel, "Calculations", Box.LEFT));
      midPanel.add(new Box(graphicsPanel, "Discrete Fourier Decomposition",
                           Box.LEFT));

      timeField = new TextField(10);
      timeField.setEditable(false);
      timeField.setBackground(Color.white);
      Panel timePanel = new Panel();
      timePanel.setLayout(new FlowLayout());
      timePanel.add(new Label("Elapsed Time for Computation:", Label.RIGHT));
      timePanel.add(timeField);

      overlayBox = new Checkbox("Overlay Graphs");
      overlayBox.addItemListener(this);
      showFFTBox = new Checkbox("Show FFT Graph");
      showFFTBox.addItemListener(this);
      showFFTBox.setState(true);
      showNormalBox = new Checkbox("Show Bit Graph");
      showNormalBox.addItemListener(this);
      showNormalBox.setState(true);

      Panel optionsPanel = new Panel();
      optionsPanel.setLayout(new GridBagLayout());
      gbc.insets = new Insets(0, 0, 0, 0);
      gbc.gridwidth = 1;
      gbc.weightx = 0;
      gbc.weighty = 0;
      gbc.fill = GridBagConstraints.NONE;
      optionsPanel.add(overlayBox);
      optionsPanel.add(showFFTBox);
      gbc.gridwidth = GridBagConstraints.REMAINDER;
      optionsPanel.add(showNormalBox);

      Panel bottomPanel = new Panel();
      bottomPanel.setLayout(new GridLayout(1, 2));
      bottomPanel.add(new Box(timePanel, "Benchmark", Box.LEFT));
      bottomPanel.add(new Box(optionsPanel, "Graphing Options", Box.LEFT));

      setLayout(new BorderLayout());
      add("North", topPanel);
      add("Center", midPanel);
      add("South", bottomPanel);

      addWindowListener(new WindowAdapter()
      {
         public void windowClosing(WindowEvent e)
         {
            if (runsFromApplet)
               fs.close();
            else
               System.exit(0);
         }
      });

      validate();
      pack();
      setSize(800, 575);
      Dimension d = Toolkit.getDefaultToolkit().getScreenSize();
      Point p = new Point((int)((d.getWidth() - this.getWidth())/2),
                          (int)((d.getHeight() - this.getHeight())/2));
      setLocation(p);
      setVisible(true);
   }

   public static void computeFFT(int sign, int n, double[] ar, double[] ai)
   {
      double scale = 2.0 / (double)n;
      int i, j;
      for(i = j = 0; i < n; ++i)
      {
         if (j >= i)
         {
            double tempr = ar[j] * scale;
            double tempi = ai[j] * scale;
            ar[j] = ar[i] * scale;
            ai[j] = ai[i] * scale;
            ar[i] = tempr;
            ai[i] = tempi;
         }
         int m = n/2;
         while ((m >= 1) && (j >= m))
         {
            j -= m;
            m /= 2;
         }
         j += m;
      }
      int mmax, istep;
      for(mmax = 1, istep = 2 * mmax; mmax < n; mmax = istep, istep = 2 * mmax)
      {
         double delta = sign * Math.PI / (double)mmax;
         for(int m = 0; m < mmax; ++m)
         {
            double w = m * delta;
            double wr = Math.cos(w);
            double wi = Math.sin(w);
            for(i = m; i < n; i += istep)
            {
               j = i + mmax;
               double tr = wr * ar[j] - wi * ai[j];
               double ti = wr * ai[j] + wi * ar[j];
               ar[j] = ar[i] - tr;
               ai[j] = ai[i] - ti;
               ar[i] += tr;
               ai[i] += ti;
            }
         }
         mmax = istep;
      }
   }

   public static double series(double[] a, double[] b, double x,
                               int n, double period)
   {
      double y = a[0] / 2.0;
      for (int i = 1; i <= n; i++)
         y += a[i] * Math.cos(2 * Math.PI * i / period * x) +
              b[i] * Math.sin(2 * Math.PI * i / period * x);
      return y;
   }

   public static String binaryNumber(int i)
   {
      if (i == 0)
         return "0";
      else if (i == 1)
         return "1";
      else
         return binaryNumber(i / 2) + (i % 2);      
   }

   public static String binary8BitCode(char cc)
   {
      String s = binaryNumber(cc);
      if (s.length() < 8)
      {
         String padding = "";
         for(int i = 0; i < 8 - s.length(); i++)
            padding += "0";
         s = padding + s;
      }
      return s;
   }

   public static double[] makeArrayFromBinary(int size, char cc)
   {
      String s = binary8BitCode(cc);
      double y[] = new double[size];
      for(int i = 0; i < size; i++)
         if (s.charAt((8 * i) / size) == '0')
            y[i] = 0.0;
         else
            y[i] = 1.0;
      return y;
   }

   public static boolean isPowerOfTwo(int x)
   {
      String s = binaryNumber(x);
      for(int i = 1; i < s.length(); i++)
         if (s.charAt(i) != '0')
            return false;
      return true;
   }

   public int getNumberOfHarmonics()
   {
      int coeffs = coefficients;
      if (filterBox.getState())
      {
         coeffs = (int)Math.ceil((filterFreq * period - 2 * Math.PI) / (2 * Math.PI));
         if (coeffs > coefficients)
            coeffs = coefficients;
      }
      return coeffs;
   }

   private boolean isFormValid()
   {    
      if (letterField.getText().trim().length() == 0)
      {
         letterField.selectAll();
         letterField.requestFocus();
         MessageBox mb = new MessageBox(fs, this, "Error",
                                        "ASCII character required.", "exclaim.gif");
         return false;
      }
      else if (letterField.getText().trim().length() > 1)
      {
         letterField.selectAll();
         letterField.requestFocus();
         MessageBox mb = new MessageBox(fs, this, "Error",
                                        "Enter a single ASCII character.",
                                        "exclaim.gif");
         return false;
      }
      else
      {
         character = letterField.getText().trim().charAt(0);
         letterField.setText("" + character);
      }
      if (sizeField.getText().trim().length() > 0)
      {
         try
         {
            sampleSize = Integer.parseInt(sizeField.getText().trim());
            if (!isPowerOfTwo(sampleSize))
            {
               sizeField.selectAll();
               sizeField.requestFocus();
               MessageBox mb = new MessageBox(fs, this, "Error",
                                              "Sample size must be a power of two.",
                                              "exclaim.gif");
               return false;
            }
            else if (sampleSize > 4096)
            {
               sizeField.selectAll();
               sizeField.requestFocus();
               MessageBox mb = new MessageBox(fs, this, "Error",
                                              "Sample size is too large.",
                                              "exclaim.gif");
               return false;
            }
            else
            {
               sizeField.setText(Integer.toString(sampleSize));
            }
         }
         catch (NumberFormatException nfe)
         {
            sizeField.selectAll();
            sizeField.requestFocus();
            MessageBox mb = new MessageBox(fs, this, "Error",
                                           "Invalid numeric format.",
                                           "exclaim.gif");
            return false;
         }
      }
      else
      {
         sizeField.selectAll();
         sizeField.requestFocus();
         MessageBox mb = new MessageBox(fs, this, "Error",
                                        "Sample size required.", "exclaim.gif");
         return false;
      }
      if (periodField.getText().trim().length() > 0)
      {
         try
         {
            period = Double.valueOf(periodField.getText().trim()).doubleValue();
            if (period <= 0)
            {
               periodField.selectAll();
               periodField.requestFocus();
               MessageBox mb = new MessageBox(fs, this, "Error",
                                              "Period must be greater than 0.",
                                              "exclaim.gif");
               return false;
            }
            else
               periodField.setText(Double.toString(period));
         }
         catch (NumberFormatException nfe)
         {
            periodField.selectAll();
            periodField.requestFocus();
            MessageBox mb = new MessageBox(fs, this, "Error",
                                           "Invalid numeric format.",
                                           "exclaim.gif");
            return false;
         }
      }
      else
      {
         periodField.selectAll();
         periodField.requestFocus();
         MessageBox mb = new MessageBox(fs, this, "Error",
                                        "Period required.", "exclaim.gif");
         return false;
      }
      if (coefField.getText().trim().length() > 0)
      {
         try
         {
            coefficients = Integer.parseInt(coefField.getText().trim());
            if (coefficients < 1)
            {
               coefField.selectAll();
               coefField.requestFocus();
               MessageBox mb = new MessageBox(fs, this, "Error",
                                   "Number of coefficients must be at least 1.",
                                   "exclaim.gif");
               return false;
            }
            else
               coefField.setText(Integer.toString(coefficients));
         }
         catch (NumberFormatException nfe)
         {
            coefField.selectAll();
            coefField.requestFocus();
            MessageBox mb = new MessageBox(fs, this, "Error",
                                           "Invalid numeric format.",
                                           "exclaim.gif");
            return false;
         }
      }
      else
      {
         coefField.selectAll();
         coefField.requestFocus();
         MessageBox mb = new MessageBox(fs, this, "Error",
                                        "Number of coefficients required.",
                                        "exclaim.gif");
         return false;
      }
      if (filterBox.getState())
         if (filterField.getText().trim().length() > 0)
         {
            try
            {
               filterFreq = Double.valueOf(filterField.getText().trim()).doubleValue();
               if (filterFreq < 1)
               {
                  filterField.selectAll();
                  filterField.requestFocus();
                  MessageBox mb = new MessageBox(fs, this, "Error",
                                      "Filter frequency must be at least 1.",
                                      "exclaim.gif");
                  return false;
               }
               else
                  filterField.setText(Double.toString(filterFreq));
            }
            catch (NumberFormatException nfe)
            {
               filterField.selectAll();
               filterField.requestFocus();
               MessageBox mb = new MessageBox(fs, this, "Error",
                                              "Invalid numeric format.",
                                              "exclaim.gif");
               return false;
            }
         }
         else
         {
            filterField.selectAll();
            filterField.requestFocus();
            MessageBox mb = new MessageBox(fs, this, "Error",
                                           "Filter frequency required.",
                                           "exclaim.gif");
            return false;
         }
      if (coefficients > sampleSize / 2)
      {
         coefField.selectAll();
         coefField.requestFocus();
         MessageBox mb = new MessageBox(fs, this, "Error",
            "Coefficients must be less than / equal to " +
            "half the sample size (" + sampleSize / 2 + ").",
            "exclaim.gif");
         return false;
      }
      return true;
   }

   private void displayResults(double[] ar, double[] ai)
   {
      StringBuffer result = new StringBuffer();
      result.append("Harmonics for '" + character + "', byte-code " +
                    binary8BitCode(character) + ":\n\n");
      if ((filterBox.getState()) && (numberOfHarmonics < coefficients))
         result.append("WARNING: Harmonics " + (numberOfHarmonics + 1) +
                       " to " + coefficients + " are filtered out.\n\n");
      result.append("   Constant ");
      String coStr, iStr;
      coStr = Integer.toString(coefficients);
      for(int i = 0; i < coStr.length() - 1; i++)
         result.append(" ");
      result.append("c = " + coefFormat.format(ar[0]) + "\n");
      for(int i = 1; i <= coefficients; i++)
      {
         result.append("   Harmonic ");
         iStr = Integer.toString(i);
         for(int j = 0; j < coStr.length() - iStr.length(); j++)
            result.append(" ");
         result.append(i + ": ");
         double freq = (2 * Math.PI * i) / period;
         result.append(coefFormat.format(ar[i]) + " cos(" +
                       freqFormat.format(freq) + " t)");
         if (ai[i] < 0)
            result.append(" - ");
         else
            result.append(" + ");
         result.append(coefFormat.format(Math.abs(ai[i])) + " sin(" +
                       freqFormat.format(freq) + " t)");
         result.append("\n");
      }         
      resultsArea.setText(result.toString());
      resultsArea.setCaretPosition(0);

   }

   private void doComputations()
   {
      x = new double[sampleSize];
      y = new double[sampleSize];
      yfft = new double[sampleSize];
      double[] ar = new double[sampleSize];
      double[] ai = new double[sampleSize];
      y = makeArrayFromBinary(sampleSize, character);
      for(int i = 0; i < sampleSize; i++)
      {
         ar[i] = y[i];
         ai[i] = 0.0;
      }
      computeFFT(1, sampleSize, ar, ai);
      numberOfHarmonics = getNumberOfHarmonics();
      for(int i = 0; i < sampleSize; i++)
         x[i] = ((double)i / (double)sampleSize) * period;
      for(int i = 0; i < sampleSize; i++)
         yfft[i] = series(ar, ai, x[i], numberOfHarmonics, period);
      spectrum.plot(ar, ai, numberOfHarmonics);
      graph.plot(x, y, yfft, overlayBox.getState(),
                 showFFTBox.getState(), showNormalBox.getState());
      displayResults(ar, ai);
      oneCompleted = true;
   }

   public void actionPerformed(ActionEvent ae)
   {
      if (ae.getSource() == compute)
         if (isFormValid())
         {
            setCursor(waitCursor);
            long startTime = System.currentTimeMillis(), time;
            doComputations();
            time = System.currentTimeMillis();
            timeField.setText("" + (time - startTime)/1000f + " s");
            setCursor(defaultCursor);
         }
   }

   public void focusGained(FocusEvent fe)
   {
      if (fe.getSource() == letterField)
         letterField.selectAll();
      else if (fe.getSource() == sizeField)
         sizeField.selectAll();
      else if (fe.getSource() == periodField)
         periodField.selectAll();
      else if (fe.getSource() == coefField)
         coefField.selectAll();
      else if (fe.getSource() == filterField)
         filterField.selectAll();
   }

   public void focusLost(FocusEvent fe)
   {
      if (fe.getSource() == letterField)
         letterField.select(0, 0);
      else if (fe.getSource() == sizeField)
         sizeField.select(0, 0);
      else if (fe.getSource() == periodField)
         periodField.select(0, 0);
      else if (fe.getSource() == coefField)
         coefField.select(0, 0);
      else if (fe.getSource() == filterField)
         filterField.select(0, 0);
   }

   public void itemStateChanged(ItemEvent ie)
   {
      if (oneCompleted)
      {
         graph.plot(x, y, yfft, overlayBox.getState(),
                    showFFTBox.getState(), showNormalBox.getState());
      }
   }

   public static void main(String[] args)
   {
      FFTApp fa = new FFTApp(null, false);
   }

}