fftdemo.java

源码为科学出版社出版的英文<java设计模式>(影印版)所用的所有例子程序

import java.awt.*;
import java.awt.event.*;

public class FFTDemo extends Frame
   implements ActionListener, WindowListener
{
  final int maxDim = 1024;
  
  int width =400, height =300;
  Button b;
  Complex x[];
  drawPanel pdraw;
//-------------------------------------------
  public FFTDemo()
  {
     super("FFT");
     setLayout(new BorderLayout());
     addWindowListener(this);

     b = new Button("FFT");
     Panel p = new Panel();
     add("South", p);
     p.add(b);
     b.addActionListener(this);
     
     x = new Complex[maxDim];
     for (int i=0; i < maxDim; i++) 
        {
        x[i]=new Complex(0.0f, 0.0f);
        }
     for (int j=50; j < 250; j+=50) {
     
     for (int i=0; i < maxDim; i++) 
        {
        float arg =(float)(j*i * Math.PI/maxDim);
        x[i].setReal(x[i].getReal() + (float)Math.cos(arg));
        }
     }
    pdraw = new drawPanel(x);
    add("Center", pdraw);
    setBounds(100,100, width, height);
    setVisible(true);
  }
  //-------------------------------------
  public void actionPerformed(ActionEvent e)
  {
     FFT fft = new FFT(x);
     fft.Execute();
     pdraw.repaint();
  }
  //-------------------------------------
  static public void main(String argv[])
  {
     new FFTDemo();
  }
  //-------------------------------------
  public void windowClosing(WindowEvent wEvt)
   {
    System.exit(0);   //exit on System exit box clicked
   }
   public void windowClosed(WindowEvent wEvt){}
   public void windowOpened(WindowEvent wEvt){}
   public void windowIconified(WindowEvent wEvt){}
   public void windowDeiconified(WindowEvent wEvt){}
   public void windowActivated(WindowEvent wEvt){}
   public void windowDeactivated(WindowEvent wEvt){}
   
}
//=======================================
class Complex
{
   float real;
   float imag;
//---------------------------------
   public Complex(float r, float i)
   {
   real = r;                              
   imag = i;
   }
//---------------------------------
   public void setReal(float r)
   {
      real = r;
   }
//---------------------------------
   public void setImag(float i)
   {
      imag= i;
   }
//---------------------------------
   public float getReal()
   {
      return real;
   }
//---------------------------------
   public float getImag()
   {
      return imag;
   }
}
//==========================================
class FFT
{
 Complex x[];
 boolean inverse = false;
 int n;     //size of complex array
 int n2;    //half of array size
 int nu;    //log2 of array size
 
   public FFT(Complex[] xarray)
   {
      x = xarray;
      n = x.length;
      n2 = n/2;
   }
   //---------------------------
   public void Execute()
   {
      Cocoon cocoon = new Cocoon();
      Butterfly butterfly;
   float cosy = 0;
   float siny = 0;
   int i, j;
   
   nu = getLogn();
   bit_invert_swap(nu);
   float deltay = (float)Math.PI ;
   int celnum = n / 2;
   int pairnum = 1;
   int celdis = 1;
   //each pass after the first starts here
   while (celnum > 0) 
      {
      int celloff = 0;
      float y = 0;
      for (int p =0; p< pairnum; p++) 
         {
         i= celloff;
         j= i + celdis;
         //get a Butterfly class depending on
         //whether angle y is zero or not
         butterfly = cocoon.getButterfly(y);
         for (int celcnt =0; celcnt <celnum; celcnt++) 
            {
            butterfly.Execute(x[i], x[j]); 
            i+= celdis+celdis;
            j = i + celdis;
            } //for celcnt
         y += deltay;
         celloff++;
         }// next p

   //pass done - change cell dist and number of cells
      celnum /= 2;   //half as many cells
      celdis *= 2;   //twice as far apart
      pairnum *=2;   //twice as may pairs
      deltay /= 2;   //half as big an increment
      }  //end while

   }
   //---------------------------
   private int getLogn()
   {
   //calculate NU = log2(size)
   int nu = 0;
   int n1 = n2;
   
   while (n1 >= 1) 
      {
      nu++;    //count number of shifts
      n1 >>=1; //to get to 1
      }
   return nu;
   }
   //----------------------------
   private int bitinvert(int i, int nu)
   {
      //bit invert i through nu bits
      int k = 0;
      for (int j =0; j < nu; j++) 
         {
         k <<=1;
         if ( (i & 1) != 0) 
           k++;
         i >>= 1;
         }
      return k;
   }
   //------------------------------
   private void bit_invert_swap(int nu)
   {
      for (int i =0; i < n; i++) 
         {
         int k = bitinvert(i, nu);
         if (k > i) 
           {
            Complex t = x[i];
            x[i] = x[k];
            x[k] = t;
            }
         }
   }
   //-----------------------------
}
//====================================
class drawPanel extends Panel
{
   Complex x[];
   float ymin, ymax;
   float hscale, vscale;
   int ytop, ybot;
   public drawPanel(Complex xa[])
   {
      x = xa;
      ymin = 1e9F;
      ymax = -1e9F;
   }
     //--------------------------------------
  public void paint(Graphics g)
  {
    
     ymin = 1e9F;
      ymax = -1e9F;
   
     for (int i=0; i< x.length; i++) 
      {
       if (x[i].getReal() > ymax) ymax =x[i].getReal();
       if (x[i].getReal() < ymin) ymin =x[i].getReal();
      }
     
   Dimension d = getSize();
   hscale = (float)d.width/x.length;
   vscale = 0.9f*((float)(d.height))/(ymax - ymin);

   ytop = (int)(d.height*0.95);
   ybot =0;// (int)(d.height*0.05);
   

   int x0 = calcx(0);
   int y0 = calcy(x[0].getReal());
   for (int i = 1; i < x.length; i++) 
      {
      int x1 = calcx(i);
      int y1 = calcy(x[i].getReal());
      
      g.drawLine(x0, y0, x1, y1);
      x0 = x1;
      y0 = y1;
      }
   }
  //-------------------------------------
  private int calcx(int i)
  {
     return (int) (i*hscale);
  }
    //-------------------------------------
  private int calcy(float y)
  {
     return ytop- (int)((y - ymin)*vscale)+ybot;
  }
}
//=============================================
class Cocoon
{
   public Butterfly getButterfly(float y)
   {
      if (y !=0)
         return new trigButterfly(y);
      else
         return new addButterfly(y);
   }
}
//=============================================
class addButterfly extends Butterfly
{
   float oldr1, oldi1;

   public addButterfly(float angle)
   {
   }
   public void Execute(Complex xi, Complex xj)
   {
     oldr1 = xi.getReal();
     oldi1 = xi.getImag();
     xi.setReal(oldr1 + xj.getReal());
     xj.setReal(oldr1 - xj.getReal());
     xi.setImag(oldi1 + xj.getImag());
     xj.setImag(oldi1 - xj.getImag());
   }
}
//=============================================
class trigButterfly extends Butterfly
{
   float y;
   float oldr1, oldi1;
   float cosy, siny;
   float r2cosy, r2siny, i2cosy, i2siny;
   
   public trigButterfly(float angle)
   {
      y = angle;
      cosy = (float) Math.cos(y);
      siny = (float)Math.sin(y);
 
   }
   public void Execute(Complex xi, Complex xj)
   {
      oldr1 = xi.getReal();
      oldi1 = xi.getImag();
      r2cosy = xj.getReal() * cosy;
      r2siny = xj.getReal() * siny;
      i2cosy = xj.getImag()*cosy;
      i2siny = xj.getImag()*siny;
      xi.setReal(oldr1 + r2cosy +i2siny);
      xi.setImag(oldi1 - r2siny +i2cosy);
      xj.setReal(oldr1 - r2cosy - i2siny);
      xj.setImag(oldi1 + r2siny - i2cosy);  
   }

}
//=============================================
abstract class Butterfly
{
   float y;
   public Butterfly()
   {
   }
   public Butterfly(float angle)
   {
      y = angle;
   }
   abstract public void Execute(Complex x, Complex y);
}