/*==============================================================================
| 
|  NAME     
|
|     ppFactor.h
|
|  DESCRIPTION   
|
|     Header for integer factoring classes.
|
|  LEGAL
|
|     Primpoly Version 9.1 - A Program for Computing Primitive Polynomials.
|     Copyright (C) 1999-2008 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;  version 2
|     of the License.
|     
|     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, write to the Free Software
|     Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
|     
|     The author's address is artifex@seanerikoconnor.freeservers.com
|
==============================================================================*/

#ifndef __PPFACTOR_H__
#define __PPFACTOR_H__

// TODO exception type.

/*=============================================================================
 |
 | NAME
 |
 |     PrimeFactor
 |
 | DESCRIPTION
 |
 |     Class to neatly package up unique prime factors to powers.
 |
 +============================================================================*/

template <typename IntType>
class PrimeFactor
{
    public:
        PrimeFactor( IntType prime = 0, uint count = 0 )
            : prime_( prime )
            , count_( count )
        {
        } ;

        ~PrimeFactor()
        {
        } ;

        PrimeFactor( const PrimeFactor & factor )
            : prime_( factor.prime_ )
            , count_( factor.count_ )
        {
        }

        PrimeFactor & operator=( const PrimeFactor & factor )
        {
            if (this == &factor)
                return *this ;

            prime_ = factor.prime_ ;
            count_ = factor.count_ ;
			
			return *this ;
        } ;

    public:
        IntType prime_ ;
        uint    count_ ;
} ;

/*=============================================================================
 |
 | NAME
 |
 |     CompareFactor
 |
 | DESCRIPTION
 |
 |     Class to sort unique prime factors to powers into order by prime size.
 |
 +============================================================================*/

template <typename IntType>
class CompareFactor
{
    public:
        bool operator()( const PrimeFactor<IntType> & s1, const PrimeFactor<IntType> & s2 )
        {
            return s1.prime_ < s2.prime_ ;
        }
} ;



/*=============================================================================
 |
 | NAME
 |
 |     CompareFactor
 |
 | DESCRIPTION
 |                                                  0     e
 |     Class to check for unit factors of the form p  or 1 = 1
 |
 +============================================================================*/

template <typename IntType>
class Unit
{
    public:
        bool operator()( const PrimeFactor<IntType> & s )
        {
            return s.count_ == 0 || s.prime_ == static_cast<IntType>( 1u ) ;
        }
} ;



/*=============================================================================
|
| NAME
|
|     Factor
|
| DESCRIPTION
|
|     Class for single and multiprecision factoring.
|
|     BigInt n ;
|
|     Factor fact( n )        Factor n into primes.
|     int numDistinctFactors = fact.num() ;
|     BigInt primeFactor = fact[ i ] ;
|
| NOTES
|
|     The member functions and friends are documented in detail ppBigInt.cpp
|
+============================================================================*/

enum FactoringAlgorithm 
{ 
    Automatic, 
    TrialDivisionAlgorithm, 
    PollardRhoAlgorithm, 
    FactorTable
} ;

// We need both single precision and multi-precision factoring, so use
// a template with an integer type.
template <typename IntType>
class Factor
{
    // TODO:  create exception type for out of range conditions.
    public:

		// Factor n into distinct primes.  Default constructor factors nothing.
        Factor( const IntType n = 1u, FactoringAlgorithm type = Automatic ) ;

       ~Factor() ;
	   
        // Copy constructor.
        Factor( const Factor<IntType> & f ) ;
		
        // Assignment operator.
        Factor<IntType> & operator=( const Factor<IntType> & g ) ;

	    // Return the number of distinct factors.
		uint num() const ;

        // Return the ith prime factor.
        // TODO range check.
        // throws out_of_range exception
		IntType operator[]( uint i ) const ;

        // Return the count for the ith prime factor.
        IntType count( uint i ) const ;
        
        // Euler Phi function of n.
        IntType EulerPhi() ;

        // True if p  | (p - 1).
        //          i
        bool skip_test( int p, int i ) const ;

        // Factoring with tables.
        bool factorTable() ;

        //                                     ---
        // Factoring by trial division up to \/ n
        void trialDivision() ;

        // Fast probabilistic factoring method.
        bool PollardRho( const IntType & c = static_cast<IntType>( 2u )) ;

    public:
        Statistics statistics_ ;

    private:
        // The unfactored remainder.
        IntType n_ ;

		// Total number of distinct factors.
		uint             numFactors_ ;

        // Array of distinct prime factors of n with their multiplicities.
		vector< PrimeFactor<IntType> > factor_ ;
} ;

// True if n is likely to be prime.  Tests on a random integer x.
template <typename IntType>
bool is_probably_prime( const IntType & n, const IntType & x ) ;

// True if n is probabilistically prime.
template <typename IntType>
bool is_almost_surely_prime( const IntType & n ) ;

#endif // __PPFACTOR_H__