#ifndef __FFT_H__

/*=============================================================================
|
| NAME
|  
|      FFT.h
|
| DESCRIPTION
|  
|      This program does an in-place one dimensional complex discrete
|      Fourier transform.  It uses an FFT algorithm for a number of 
|      input points which is a power of two.
|    
| AUTHOR
|
|      Sean O'Connor   19 November 2005
|
| LEGAL
|
|     FFT Version 1.2 - An FFT utility library in C++.
|     Copyright (C) 2005-2009 by Sean Erik O'Connor.  All Rights Reserved.
|
|     This program is free software: you can redistribute it and/or modify
|     it under the terms of the GNU General Public License as published by
|     the Free Software Foundation, either version 3 of the License, or
|     (at your option) any later version.
|
|     This program is distributed in the hope that it will be useful,
|     but WITHOUT ANY WARRANTY; without even the implied warranty of
|     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
|     GNU General Public License for more details.
|
|     You should have received a copy of the GNU General Public License
|     along with this program.  If not, see <http://www.gnu.org/licenses/>.
|     
|     The author's address is artificer!AT!seanerikoconnor!DOT!freeservers!DOT!com
|     with !DOT! replaced by . and the !AT! replaced by @
|
+============================================================================*/

/*
 *  We must set the size of the sine and cosine table used in the FFT.
 *  The table is called starting_multiplier.
 *     
 *  Suppose MAX is the largest number of points we would ever transform.  We set
 *
 *      MAX_TABLE_SIZE  =  LOG ( MAX ) - 1
 *                            2
 *
 *  to be the size of the table.  This table can now be used by the FFT for 
 *  any number of points from 2 up to MAX.
 *
 *  For example, if MAX_TABLE_SIZE = 14, then we can transform anywhere from 
 *  2 to 2 ^ 15 = 32,768 points, using the same sine and cosine table.
 *
 */
const int    MAX_TABLE_SIZE = 13 ;



// Derive the FFT class from an STL vector of double precision types.
// Thus we get the vector's data manipulation attributes and
// we can substitute FFT objects into an existing software
// framework which uses vector objects in containers.
// But extend the class by adding a Fourier Transform capability.
//
class FastFourierTransform 
      : public vector< complex<double> > // Need spaces between angle brackets to satisfy compiler.
{
    public:
        // Default constructor.
        FastFourierTransform() ;
        
        // Destructor.
        ~FastFourierTransform() ;

        // Copy constructor ;
        FastFourierTransform( const FastFourierTransform & transform ) ;

        // Assignment operator.
        FastFourierTransform & operator=( const FastFourierTransform & transform ) ;

        // Fast Fourier transform capability.
        void fft( bool direction = true ) ;

    // Maybe these should be private to be safe!
    protected:
        bool direction ;

    private:
        // Table of sines and cosines whose values are created the first 
        // time any object calls the fft() member function and which are
        // shared among all subsequent objects.
        static complex<double> starting_multiplier[ MAX_TABLE_SIZE ] ;
        static bool called_already ;
		static const double PI ;
		
		// Helper function used by FFT member function only.
        static int reverse_bits( int n, int num_bits ) ;
} ;


/*=============================================================================
|
| NAME
|  
|     FastFourierTransformException
|
| DESCRIPTION
|  
|     Helper class for recording data thrown by FastFourierTransform.
|
| BUGS
|
+============================================================================*/
       
class FastFourierTransformException : public runtime_error
{
    public:
        // This form will be used most often in a throw.
        FastFourierTransformException( const string & description )
			: runtime_error( description )
        {
        } ;

        // Throw with no error message.
        FastFourierTransformException()
			: runtime_error( "FFT exception:  " )
        {
        } ; 

} ; // end class FastFourierTransformException


#endif // __FFT_H__