```#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++.
|
|     This program is free software: you can redistribute it and/or modify
|     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 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__
```