factory.h

Go to the documentation of this file.

/* factory.h automatically generated by makeheader from factory.template */
/* emacs edit mode for this file is -*- C++ -*- */
 
#ifndef INCL_FACTORY_H
#define INCL_FACTORY_H
 
/* factory.template is a template to generate `factory.h' */
 
/**
*
* @file factory.h
*
* `factory.h' is the user interface to Factory.  Created
* automatically by `makeheader', it collects all important
* declarations from all important Factory header files into one
* overall header file leaving out all boring Factory internal
* stuff.  See `./bin/makeheader' for an explanation of the syntax
* of this file.
*
* Note: In this file the order of "includes" matters (since this
* are not real includes)!  In general, files at the end depend
* on files at the beginning.
*
**/
 
#include "factory/factoryconf.h"
#include "factory/globaldefs.h"
#include <stdint.h>
#include "factory/si_log2.h"
#ifdef HAVE_OMALLOC
#include "omalloc/omalloc.h"
#ifndef XMEMORY_H
#include "omalloc/omallocClass.h"
#endif
#endif
 
#ifndef NOSTREAMIO
#  ifdef HAVE_IOSTREAM
#    include <iostream>
#    define OSTREAM std::ostream
#    define ISTREAM std::istream
#  elif defined(HAVE_IOSTREAM_H)
#    include <iostream.h>
#    define OSTREAM ostream
#    define ISTREAM istream
#  endif
#endif /* ! NOSTREAMIO */
 
#include "factory/cf_gmp.h"
 
#include "factory/templates/ftmpl_array.h"
#include "factory/templates/ftmpl_afactor.h"
#include "factory/templates/ftmpl_factor.h"
#include "factory/templates/ftmpl_list.h"
#include "factory/templates/ftmpl_matrix.h"
 
/* stuff included from ./cf_globals.h */
 
 
extern const char factoryConfiguration[];
 
 
/* stuff included from ./cf_primes.h */
 
 
int FACTORY_PUBLIC cf_getPrime( int i );
 
int FACTORY_PUBLIC cf_getNumPrimes();
 
int FACTORY_PUBLIC cf_getSmallPrime( int i );
 
int FACTORY_PUBLIC cf_getNumSmallPrimes();
 
int FACTORY_PUBLIC cf_getBigPrime( int i );
 
int FACTORY_PUBLIC cf_getNumBigPrimes();
 
 
/* stuff included from ./cf_defs.h */
 
 
#define LEVELBASE -1000000
#define LEVELTRANS -500000
#define LEVELQUOT 1000000
#define LEVELEXPR 1000001
 
/// set to 1 for computations over Q
static const int SW_RATIONAL = 0;
/// set to 1 for symmetric representation over F_q
static const int SW_SYMMETRIC_FF = 1;
/// set to 1 to use EZGCD over Z
static const int SW_USE_EZGCD = 2;
/// set to 1 to use EZGCD over F_q
static const int SW_USE_EZGCD_P = 3;
/// set to 1 to sort factors in a factorization
static const int SW_USE_NTL_SORT=4;
/// set to 1 to use modular gcd over Z
static const int SW_USE_CHINREM_GCD=5;
/// set to 1 to use Encarnacion GCD over Q(a)
static const int SW_USE_QGCD=6;
/// set to 1 to use modular GCD over F_q
static const int SW_USE_FF_MOD_GCD=7;
/// set to 1 to use Flints gcd over F_p
static const int SW_USE_FL_GCD_P=8;
/// set to 1 to use Flints gcd over Q/Z
static const int SW_USE_FL_GCD_0=9;
/// set to 1 to use Factorys Berlekamp alg.
static const int SW_BERLEKAMP=10;
 
static const int SW_FAC_QUADRATICLIFT=11;
/// set to 1 to prefer flints multivariate factorization over Z/p
static const int SW_USE_FL_FAC_P=12;
/// set to 1 to prefer flints multivariate factorization over Z/p
static const int SW_USE_FL_FAC_0=13;
/// set to 1 to prefer flints multivariate factorization over Z/p(a)
static const int SW_USE_FL_FAC_0A=14;
 
/* stuff included from ./variable.h */
 
 
class CanonicalForm;
 
/**
 * factory's class for variables
**/
class FACTORY_PUBLIC Variable
{
private:
    int _level;
    Variable( int l, bool flag );
public:
    Variable() : _level(LEVELBASE) {}
    Variable( int l );
    Variable( char name );
    Variable( int l, char name );
    Variable( const Variable & v ) : _level(v._level) {}
    ~Variable() {};
    Variable& operator= ( const Variable & v )
    {
        _level = v._level;
        return *this;
    }
    int level() const { return _level; }
    char name() const;
    static Variable highest() { return Variable( LEVELQUOT-1 ); }
    Variable next() const { return Variable( _level+1 ); }
    friend bool operator == ( const Variable & lhs, const Variable & rhs )
    {
        return lhs._level == rhs._level;
    }
    friend bool operator != ( const Variable & lhs, const Variable & rhs )
    {
        return lhs._level != rhs._level;
    }
    friend bool operator > ( const Variable & lhs, const Variable & rhs )
    {
        return lhs._level > rhs._level;
    }
    friend bool operator < ( const Variable & lhs, const Variable & rhs )
    {
        return lhs._level < rhs._level;
    }
    friend bool operator >= ( const Variable & lhs, const Variable & rhs )
    {
        return lhs._level >= rhs._level;
    }
    friend bool operator <= ( const Variable & lhs, const Variable & rhs )
    {
        return lhs._level <= rhs._level;
    }
#ifndef NOSTREAMIO
   friend OSTREAM & operator << ( OSTREAM & os, const Variable & v );
#endif /* NOSTREAMIO */
    friend void swap_levels();
    /** returns a symbolic root of polynomial with name @a name.
     *  Use it to define algebraic variables
     *  @note: algebraic variables have a level < 0
    **/
    friend Variable FACTORY_PUBLIC rootOf( const CanonicalForm &, char name );
};
 
/** returns a symbolic root of polynomial with name @a name
 *  Use it to define algebraic variables
 *  @note: algebraic variables have a level < 0
**/
Variable FACTORY_PUBLIC rootOf( const CanonicalForm &, char name = '@' );
 
inline int level( const Variable & v ) { return v.level(); }
inline char name( const Variable & v ) { return v.name(); }
 
void setReduce( const Variable & alpha, bool reduce );
void setMipo ( const Variable & alpha, const CanonicalForm & mipo);
CanonicalForm getMipo( const Variable & alpha, const Variable & x );
bool hasMipo( const Variable & alpha );
 
char getDefaultVarName();
char getDefaultExtName();
 
void FACTORY_PUBLIC prune (Variable& alpha);
void prune1 (const Variable& alpha);
int ExtensionLevel();
 
 
/* stuff included from ./canonicalform.h */
 
 
#undef CF_INLINE
#define CF_INLINE
#undef CF_NO_INLINE
#define CF_NO_INLINE
 
 
class InternalCF;
 
inline int is_imm ( const InternalCF * const ptr )
{
    // returns 0 if ptr is not immediate
    return ( ((int)((intptr_t)ptr)) & 3 );
}
 
 
/**
 * factory's main class
 *
 * a CanonicalForm can represent a polynomial over or a constant in F_p,
 * F_p(alpha), GF (F_p[t]/(Conway polynomial)), Z, or Q
 *
 * @sa int_poly.h, variable.h, ffops.h, gfops.h, imm.h, int_int.h, int_rat.h
**/
class FACTORY_PUBLIC CanonicalForm
#ifdef HAVE_OMALLOC
#ifndef XMEMORY_H
       : public omallocClass
#endif
#endif
{
private:
    InternalCF *value;
public:
    // constructors, destructors, selectors
    CF_INLINE CanonicalForm();
    CF_INLINE CanonicalForm( const CanonicalForm& );
    CF_INLINE CanonicalForm( InternalCF* );
    CF_INLINE CanonicalForm( const int );
    CF_INLINE CanonicalForm( const long );
    CF_INLINE CanonicalForm( const Variable & );
    CF_INLINE CanonicalForm( const Variable &, int );
    CanonicalForm( const char *, const int base=10 ); // use with caution - does only handle integers !!!
 
    CF_NO_INLINE ~CanonicalForm();
 
    InternalCF* getval() const; // use with caution !!!
 
    CanonicalForm deepCopy() const;
 
    void mpzval(mpz_t val) const;
    // predicates
    CF_NO_INLINE bool isOne() const;
    CF_NO_INLINE bool isZero() const;
    inline bool isImm() const { return is_imm( value ); };
 
    bool inZ() const;
    bool inQ() const;
    bool inFF() const;
    bool inGF() const;
    bool inBaseDomain() const;
    bool inExtension() const;
    bool inCoeffDomain() const;
    bool inPolyDomain() const;
    bool inQuotDomain() const;
 
    bool isFFinGF() const;
    bool isUnivariate() const;
    bool isHomogeneous() const;
 
    // conversion functions
    long intval() const;
    CanonicalForm mapinto () const;
 
    CanonicalForm lc () const;
    CanonicalForm Lc () const;
    CanonicalForm LC () const;
    CanonicalForm LC ( const Variable & v ) const;
 
    int degree () const;
    int degree ( const Variable & v ) const;
 
    CanonicalForm tailcoeff () const;
    CanonicalForm tailcoeff ( const Variable & v ) const;
    int taildegree () const;
 
    int level () const;
    Variable mvar () const;
 
    CanonicalForm num () const;
    CanonicalForm den () const;
 
    // assignment operators
    CF_NO_INLINE CanonicalForm& operator = ( const CanonicalForm& );
    CF_NO_INLINE CanonicalForm& operator = ( const long );
 
    CanonicalForm& operator += ( const CanonicalForm& );
    CanonicalForm& operator -= ( const CanonicalForm& );
    CanonicalForm& operator *= ( const CanonicalForm& );
    CanonicalForm& operator /= ( const CanonicalForm& );
    CanonicalForm& operator %= ( const CanonicalForm& );
    CanonicalForm& div ( const CanonicalForm& );
    CanonicalForm& tryDiv (const CanonicalForm&, const CanonicalForm&, bool& );
    CanonicalForm& mod ( const CanonicalForm& );
 
    // evaluation operators
    CanonicalForm operator () ( const CanonicalForm & f ) const;
    CanonicalForm operator () ( const CanonicalForm & f, const Variable & v ) const;
 
    CanonicalForm operator [] ( int i ) const;
 
    CanonicalForm deriv() const;
    CanonicalForm deriv( const Variable & x ) const;
 
    int sign() const;
    CanonicalForm sqrt() const;
    int ilog2() const;
 
    // comparison operators
    friend FACTORY_PUBLIC bool operator == ( const CanonicalForm&, const CanonicalForm& );
    friend FACTORY_PUBLIC bool operator != ( const CanonicalForm&, const CanonicalForm& );
    friend FACTORY_PUBLIC bool operator > ( const CanonicalForm&, const CanonicalForm& );
    friend FACTORY_PUBLIC bool operator < ( const CanonicalForm&, const CanonicalForm& );
 
    // arithmetic operators
    friend CF_NO_INLINE FACTORY_PUBLIC CanonicalForm operator - ( const CanonicalForm& );
 
    friend FACTORY_PUBLIC void divrem ( const CanonicalForm&, const CanonicalForm&, CanonicalForm&, CanonicalForm& );
    friend FACTORY_PUBLIC bool divremt ( const CanonicalForm&, const CanonicalForm&, CanonicalForm&, CanonicalForm& );
    friend FACTORY_PUBLIC bool tryDivremt ( const CanonicalForm&, const CanonicalForm&, CanonicalForm&, CanonicalForm&, const CanonicalForm&, bool& );
 
    friend FACTORY_PUBLIC CanonicalForm bgcd ( const CanonicalForm &, const CanonicalForm & );
    friend FACTORY_PUBLIC CanonicalForm bextgcd ( const CanonicalForm &, const CanonicalForm &, CanonicalForm &, CanonicalForm & );
 
    // input/output
#ifndef NOSTREAMIO
   void print( OSTREAM&, char * ) const;
   void print( OSTREAM& ) const;
   friend FACTORY_PUBLIC OSTREAM& operator << ( OSTREAM&, const CanonicalForm& );
   friend FACTORY_PUBLIC ISTREAM& operator >> ( ISTREAM&, CanonicalForm& );
#endif /* NOSTREAMIO */
 
    // obsolete methods
    CanonicalForm genZero() const;
    CanonicalForm genOne() const;
 
    friend class CFIterator;
};
 
CF_INLINE FACTORY_PUBLIC CanonicalForm
operator + ( const CanonicalForm&, const CanonicalForm& );
 
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm
operator - ( const CanonicalForm&, const CanonicalForm& );
 
CF_INLINE FACTORY_PUBLIC CanonicalForm
operator * ( const CanonicalForm&, const CanonicalForm& );
 
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm
operator / ( const CanonicalForm&, const CanonicalForm& );
 
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm
operator % ( const CanonicalForm&, const CanonicalForm& );
 
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm
div ( const CanonicalForm&, const CanonicalForm& );
 
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm
mod ( const CanonicalForm&, const CanonicalForm& );
 
 
//{{{ function declarations from canonicalform.cc
CanonicalForm FACTORY_PUBLIC blcm ( const CanonicalForm & f, const CanonicalForm & g );
 
CanonicalForm FACTORY_PUBLIC power ( const CanonicalForm & f, int n );
 
CanonicalForm FACTORY_PUBLIC power ( const Variable & v, int n );
//}}}
 
//{{{ function declarations from cf_gcd.cc
CanonicalForm FACTORY_PUBLIC gcd ( const CanonicalForm&, const CanonicalForm& );
 
CanonicalForm FACTORY_PUBLIC gcd_poly ( const CanonicalForm & f, const CanonicalForm & g );
 
CanonicalForm FACTORY_PUBLIC lcm ( const CanonicalForm&, const CanonicalForm& );
 
CanonicalForm FACTORY_PUBLIC pp ( const CanonicalForm& );
 
CanonicalForm FACTORY_PUBLIC content ( const CanonicalForm& );
 
CanonicalForm FACTORY_PUBLIC content ( const CanonicalForm&, const Variable& );
 
CanonicalForm FACTORY_PUBLIC icontent ( const CanonicalForm & f );
 
CanonicalForm FACTORY_PUBLIC vcontent ( const CanonicalForm & f, const Variable & x );
//}}}
 
//{{{ function declarations from cf_ops.cc
CanonicalForm FACTORY_PUBLIC swapvar ( const CanonicalForm &, const Variable &, const Variable & );
 
CanonicalForm FACTORY_PUBLIC replacevar ( const CanonicalForm &, const Variable &, const Variable & );
 
int getNumVars( const CanonicalForm & f );
 
CanonicalForm getVars( const CanonicalForm & f );
 
CanonicalForm apply ( const CanonicalForm & f, void (*mf)( CanonicalForm &, int & ) );
 
CanonicalForm mapdomain ( const CanonicalForm & f, CanonicalForm (*mf)( const CanonicalForm & ) );
 
int * degrees ( const CanonicalForm & f, int * degs = 0 );
 
int totaldegree ( const CanonicalForm & f );
 
int totaldegree ( const CanonicalForm & f, const Variable & v1, const Variable & v2 );
 
int size ( const CanonicalForm & f, const Variable & v );
 
int size ( const CanonicalForm & f );
 
int size_maxexp ( const CanonicalForm & f, int& maxexp );
 
CanonicalForm reduce ( const CanonicalForm& f, const CanonicalForm & M);
 
bool hasFirstAlgVar( const CanonicalForm & f, Variable & a);
 
CanonicalForm leftShift (const CanonicalForm& F, int n);
//}}}
 
//{{{ inline functions corresponding to CanonicalForm methods
//{{{ docu
//
// - inline functions corresponding to CanonicalForm methods.
//
// These function exist for convenience only and because it is
// more beautiful to write 'degree( f )' than 'f.degree()'.
//
//}}}
inline CanonicalForm
lc ( const CanonicalForm & f ) { return f.lc(); }
 
inline CanonicalForm
Lc ( const CanonicalForm & f ) { return f.Lc(); }
 
inline CanonicalForm
LC ( const CanonicalForm & f ) { return f.LC(); }
 
inline CanonicalForm
LC ( const CanonicalForm & f, const Variable & v ) { return f.LC( v ); }
 
inline int
degree ( const CanonicalForm & f ) { return f.degree(); }
 
inline int
degree ( const CanonicalForm & f, const Variable & v ) { return f.degree( v ); }
 
inline int
taildegree ( const CanonicalForm & f ) { return f.taildegree(); }
 
inline CanonicalForm
tailcoeff ( const CanonicalForm & f ) { return f.tailcoeff(); }
 
inline CanonicalForm
tailcoeff (const CanonicalForm& f, const Variable& v) { return f.tailcoeff(v); }
 
inline int
level ( const CanonicalForm & f ) { return f.level(); }
 
inline Variable
mvar ( const CanonicalForm & f ) { return f.mvar(); }
 
inline CanonicalForm
num ( const CanonicalForm & f ) { return f.num(); }
 
inline CanonicalForm
den ( const CanonicalForm & f ) { return f.den(); }
 
inline int
sign ( const CanonicalForm & a ) { return a.sign(); }
 
inline CanonicalForm
deriv ( const CanonicalForm & f, const Variable & x ) { return f.deriv( x ); }
 
inline CanonicalForm
sqrt ( const CanonicalForm & a ) { return a.sqrt(); }
 
inline int
ilog2 ( const CanonicalForm & a ) { return a.ilog2(); }
 
inline CanonicalForm
mapinto ( const CanonicalForm & f ) { return f.mapinto(); }
//}}}
 
//{{{ inline functions
inline CanonicalForm
head ( const CanonicalForm & f )
{
    if ( f.level() > 0 )
        return power( f.mvar(), f.degree() ) * f.LC();
    else
        return f;
}
 
inline int
headdegree ( const CanonicalForm & f ) { return totaldegree( head( f ) ); }
 
 
//}}}
 
//{{{ other function declarations
void FACTORY_PUBLIC setCharacteristic( int c ); // -> Fp && Q
void setCharacteristic( int c, int n ); // -> PrimePower
void setCharacteristic( int c, int n, char name ); // -> GF(q)
 
int FACTORY_PUBLIC getCharacteristic();
int getGFDegree();
CanonicalForm getGFGenerator();
 
void FACTORY_PUBLIC On( int );
void FACTORY_PUBLIC Off( int );
bool FACTORY_PUBLIC isOn( int );
//}}}
 
//{{{ type definitions
typedef AFactor<CanonicalForm> CFAFactor;
typedef List <CFAFactor> CFAFList;
typedef ListIterator<CFAFactor> CFAFListIterator;
typedef Factor<CanonicalForm> CFFactor;
typedef List<CFFactor> CFFList;
typedef ListIterator<CFFactor> CFFListIterator;
typedef List<CanonicalForm> CFList;
typedef ListIterator<CanonicalForm> CFListIterator;
typedef Array<CanonicalForm> CFArray;
typedef Matrix<CanonicalForm> CFMatrix;
typedef List<CFList> ListCFList;
typedef ListIterator<CFList> ListCFListIterator ;
typedef List<int> IntList;
typedef ListIterator<int> IntListIterator;
typedef List<Variable> Varlist;
typedef ListIterator<Variable> VarlistIterator;
typedef Array<int> Intarray;
//}}}
 
 
/* stuff included from ./cf_algorithm.h */
 
 
//{{{ function declarations from cf_algorithm.cc
CanonicalForm psr ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x );
 
CanonicalForm psq ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x );
 
void psqr ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & q, CanonicalForm & r, const Variable & x );
 
CanonicalForm FACTORY_PUBLIC bCommonDen ( const CanonicalForm & f );
 
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g );
 
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm& quot );
 
bool tryFdivides ( const CanonicalForm & f, const CanonicalForm & g, const CanonicalForm& M, bool& fail );
 
CanonicalForm maxNorm ( const CanonicalForm & f );
 
CanonicalForm euclideanNorm ( const CanonicalForm & f );
//}}}
 
//{{{ function declarations from cf_chinese.cc
void FACTORY_PUBLIC chineseRemainder ( const CanonicalForm & x1, const CanonicalForm & q1, const CanonicalForm & x2, const CanonicalForm & q2, CanonicalForm & xnew, CanonicalForm & qnew );
 
void FACTORY_PUBLIC chineseRemainder ( const CFArray & x, const CFArray & q, CanonicalForm & xnew, CanonicalForm & qnew );
 
void FACTORY_PUBLIC chineseRemainderCached ( const CanonicalForm & x1, const CanonicalForm & q1, const CanonicalForm & x2, const CanonicalForm & q2, CanonicalForm & xnew, CanonicalForm & qnew, CFArray &inv );
void FACTORY_PUBLIC chineseRemainderCached(const CFArray &a, const CFArray &n, CanonicalForm &xnew, CanonicalForm &prod, CFArray &inv);
 
 
CanonicalForm Farey ( const CanonicalForm & f, const CanonicalForm & q );
//}}}
 
//{{{ function declarations from cf_factor.cc
EXTERN_VAR int singular_homog_flag;
 
bool isPurePoly(const CanonicalForm & f);
 
bool isPurePoly_m(const CanonicalForm & f);
 
CFFList FACTORY_PUBLIC factorize ( const CanonicalForm & f, bool issqrfree = false );
 
CFFList FACTORY_PUBLIC factorize ( const CanonicalForm & f, const Variable & alpha );
 
CFFList FACTORY_PUBLIC sqrFree ( const CanonicalForm & f, bool sort= false );
 
CanonicalForm homogenize( const CanonicalForm & f, const Variable & x);
CanonicalForm homogenize( const CanonicalForm & f, const Variable & x,
                                const Variable & v1, const Variable & v2);
Variable get_max_degree_Variable(const CanonicalForm & f);
CFList get_Terms( const CanonicalForm & f );
void getTerms( const CanonicalForm & f, const CanonicalForm & t, CFList & result );
 
 
//}}}
 
//{{{ function declarations from cf_linsys.cc
bool linearSystemSolve ( CFMatrix & M );
 
CanonicalForm FACTORY_PUBLIC determinant ( const CFMatrix & M, int n );
//}}}
 
//{{{ function declarations from cf_resultant.cc
CFArray subResChain ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x );
 
CanonicalForm FACTORY_PUBLIC resultant ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x );
//}}}
 
/** inline CanonicalForm abs ( const CanonicalForm & f )
 *
 * abs() - return absolute value of `f'.
 *
 * The absolute value is defined in terms of the function
 * `sign()'.  If it reports negative sign for `f' than -`f' is
 * returned, otherwise `f'.
 *
 * This behaviour is most useful for integers and rationals.  But
 * it may be used to sign-normalize the leading coefficient of
 * arbitrary polynomials, too.
 *
 * Type info:
 * ----------
 * f: CurrentPP
 *
**/
inline CanonicalForm
abs ( const CanonicalForm & f )
{
    // it is not only more general to use `sign()' instead of a
    // direct comparison `f < 0', it is faster, too
    if ( sign( f ) < 0 )
        return -f;
    else
        return f;
}
//}}}
 
 
/* stuff included from ./cf_eval.h */
 
 
/**
 * class to evaluate a polynomial at points
**/
class Evaluation
{
protected:
    CFArray values;
public:
    Evaluation() : values() {}
    Evaluation( int min0, int max0 ) : values( min0, max0 ) {}
    Evaluation( const Evaluation & e ) : values( e.values ) {}
    virtual ~Evaluation() {}
    Evaluation& operator= ( const Evaluation & e );
    int min() const { return values.min(); }
    int max() const { return values.max(); }
    CanonicalForm operator[] ( int i ) const { return values[i]; }
    CanonicalForm operator[] ( const Variable & v ) const { return operator[](v.level()); }
    CanonicalForm operator() ( const CanonicalForm& f ) const;
    CanonicalForm operator() ( const CanonicalForm & f, int i, int j ) const;
    void setValue (int i, const CanonicalForm& f);
    virtual void nextpoint();
#ifndef NOSTREAMIO
    friend OSTREAM& operator<< ( OSTREAM& s, const Evaluation &e );
#endif /* NOSTREAMIO */
};
 
 
/* stuff included from ./cf_generator.h */
 
 
/**
 * virtual class for generators
**/
class CFGenerator
{
public:
    CFGenerator() {}
    virtual ~CFGenerator() {}
    virtual bool hasItems() const { return false; }
    virtual void reset() {};
    virtual CanonicalForm item() const { return 0; }
    virtual void next() {};
    virtual CFGenerator * clone() const { return new CFGenerator();}
};
 
/**
 * generate integers starting from 0
**/
class IntGenerator : public CFGenerator
{
private:
    int current;
public:
    IntGenerator() : current(0) {}
    ~IntGenerator() {}
    bool hasItems() const;
    void reset() { current = 0; }
    CanonicalForm item() const;
    void next();
    void operator++ () { next(); }
    void operator++ ( int ) { next(); }
    CFGenerator * clone() const;
};
 
/**
 * generate all elements in F_p starting from 0
**/
class FFGenerator : public CFGenerator
{
private:
    int current;
public:
    FFGenerator() : current(0) {}
    ~FFGenerator() {}
    bool hasItems() const;
    void reset() { current = 0; }
    CanonicalForm item() const;
    void next();
    void operator++ () { next(); }
    void operator++ ( int ) { next(); }
    CFGenerator * clone() const;
};
 
/**
 * generate all elements in GF starting from 0
**/
class GFGenerator : public CFGenerator
{
private:
    int current;
public:
    GFGenerator();
    ~GFGenerator() {}
    bool hasItems() const;
    void reset();
    CanonicalForm item() const;
    void next();
    void operator++ () { next(); }
    void operator++ ( int ) { next(); }
    CFGenerator * clone() const;
};
 
/**
 * generate all elements in F_p(alpha) starting from 0
**/
class AlgExtGenerator: public CFGenerator
{
private:
    Variable algext;
    FFGenerator **gensf;
    GFGenerator **gensg;
    int n;
    bool nomoreitems;
    AlgExtGenerator();
    AlgExtGenerator( const AlgExtGenerator & );
    AlgExtGenerator& operator= ( const AlgExtGenerator & );
public:
    AlgExtGenerator( const Variable & a );
    ~AlgExtGenerator();
 
    bool hasItems() const { return ! nomoreitems; }
    void reset();
    CanonicalForm item() const;
    void next();
    void operator++ () { next(); }
    void operator++ ( int ) { next(); }
    CFGenerator * clone() const;
};
 
class CFGenFactory
{
public:
    static CFGenerator* generate();
};
 
 
/* stuff included from ./cf_iter.h */
 
 
#undef CF_INLINE
#define CF_INLINE
#undef CF_NO_INLINE
#define CF_NO_INLINE
 
 
class term;
typedef term * termList;
 
/**
 * class to iterate through CanonicalForm's
 *
 * @note a (multivariate) polynomial is viewed as a univariate poly in its main
 *       variable
**/
class FACTORY_PUBLIC CFIterator {
private:
    CanonicalForm data;
    termList cursor;
    bool ispoly, hasterms;
public:
    CFIterator ();
    CFIterator ( const CFIterator& );
    CFIterator ( const CanonicalForm& );
    CFIterator ( const CanonicalForm&, const Variable& );
 
    ~CFIterator ();
 
    CFIterator& operator= ( const CFIterator& );
    CFIterator& operator= ( const CanonicalForm& );
 
    CF_NO_INLINE CFIterator& operator++ ();
    CF_NO_INLINE CFIterator& operator++ ( int );
    CF_NO_INLINE int hasTerms () const;       ///< check if iterator has reached
                                              ///< the end of CanonicalForm
    CF_NO_INLINE CanonicalForm coeff () const;///< get the current coefficient
    CF_NO_INLINE int exp () const;            ///< get the current exponent
};
 
 
/* stuff included from ./cf_random.h */
 
 
/**
 * virtual class for random element generation
**/
class CFRandom {
public:
    virtual ~CFRandom() {}
    virtual CanonicalForm generate() const { return 0; }
    virtual CFRandom * clone() const { return new CFRandom(); }
};
 
/**
 * generate random elements in GF
**/
class GFRandom : public CFRandom
{
public:
    GFRandom() {};
    ~GFRandom() {}
    CanonicalForm generate() const;
    CFRandom * clone() const;
};
 
/**
 * generate random elements in F_p
**/
class FFRandom : public CFRandom
{
public:
    FFRandom() {}
    ~FFRandom() {}
    CanonicalForm generate() const;
    CFRandom * clone() const;
};
 
/**
 * generate random integers
**/
class IntRandom : public CFRandom
{
private:
    int max;
public:
    IntRandom();
    IntRandom( int m );
    ~IntRandom();
    CanonicalForm generate() const;
    CFRandom * clone() const;
};
 
/**
 * generate random elements in F_p(alpha)
**/
class AlgExtRandomF : public CFRandom {
private:
    Variable algext;
    CFRandom * gen;
    int n;
    AlgExtRandomF();
    AlgExtRandomF( const Variable & v, CFRandom * g, int nn );
    AlgExtRandomF& operator= ( const AlgExtRandomF & );
public:
    AlgExtRandomF( const AlgExtRandomF & );
    AlgExtRandomF( const Variable & v );
    AlgExtRandomF( const Variable & v1, const Variable & v2 );
    ~AlgExtRandomF();
    CanonicalForm generate() const;
    CFRandom * clone() const;
};
 
class CFRandomFactory {
public:
    static CFRandom * generate();
};
 
/// random integers with abs less than n
int factoryrandom( int n );
 
/// random seed initializer
void FACTORY_PUBLIC factoryseed( int s );
 
 
/* stuff included from ./fac_util.h */
 
 
/**
 * class to do operations mod p^k for int's p and k
**/
class modpk
{
private:
    CanonicalForm pk;
    CanonicalForm pkhalf;
    int p;
    int k;
public:
    modpk();
    modpk( int q, int l );
    modpk( const modpk & m );
    modpk& operator= ( const modpk& m );
    ~modpk() {}
    int getp() const { return p; }
    int getk() const { return k; }
    CanonicalForm inverse( const CanonicalForm & f, bool symmetric = true ) const;
    CanonicalForm getpk() const { return pk; }
    CanonicalForm operator() ( const CanonicalForm & f, bool symmetric = true ) const;
};
 
 
CanonicalForm replaceLc( const CanonicalForm & f, const CanonicalForm & c );
 
 
/* stuff included from ./cf_map.h */
 
 
/** class MapPair
 *
 * class MapPair - stores one mapping pair (Variable -> CanonicalForm).
 *
 * This class is only used to store such pairs.  It has no
 * methods to transform a CanonicalForm as the class CFMap has.
 *
 * V, S: the pair (V -> S)
 *
**/
/** inline method
 *
 * Variable var () const
 * CanonicalForm subst () const
 *
 * var(), subst() - selectors, return V and P, resp.
 *
**/
class MapPair
{
private:
    Variable V;
    CanonicalForm S;
public:
    MapPair ( const Variable & v, const CanonicalForm & s ) : V(v), S(s) {}
    MapPair () : V(), S(1) {}
    MapPair ( const MapPair & p ) : V(p.V), S(p.S) {}
    ~MapPair () {}
    MapPair & operator = ( const MapPair & p );
    Variable var () const { return V; }
    CanonicalForm subst () const { return S; }
#ifndef NOSTREAMIO
    void print( OSTREAM&) const;
    friend OSTREAM & operator << ( OSTREAM & s, const MapPair & p );
#endif /* NOSTREAMIO */
};
 
typedef List<MapPair> MPList;
typedef ListIterator<MapPair> MPListIterator;
 
/** class CFMap
 *
 * class CFMap - class to map canonical forms.
 *
 * Use an object of class CFMap to insert 'values' into canonical
 * form.  Such a mapping is defined by a list of MapPairs (V -> S)
 * describing which canonical form S to insert for variable V.
 * Hereby, the substituted canonical forms are not subject to
 * further substitutions.
 *
 * P: list of MapPairs, sorted by level in descending order
 *
**/
class CFMap
{
private:
  MPList P;
public:
  CFMap () {}
  CFMap ( const CanonicalForm & s ) : P( MapPair( Variable(), s ) ) {}
  CFMap ( const Variable & v ) : P( MapPair( v, 1 ) ) {}
  CFMap ( const Variable & v, const CanonicalForm & s ) : P( MapPair( v, s ) ) {}
  ~CFMap () {}
  CFMap ( const CFList & L );
  CFMap ( const CFMap & m ) : P( m.P ) {}
  CFMap & operator = ( const CFMap & m );
  void newpair ( const Variable & v, const CanonicalForm & s );
  CanonicalForm operator () ( const CanonicalForm & f ) const;
#ifndef NOSTREAMIO
  friend OSTREAM & operator << ( OSTREAM & s, const CFMap & m );
#endif /* NOSTREAMIO */
};
 
CanonicalForm compress ( const CanonicalForm & f, CFMap & m );
void compress ( const CFArray & a, CFMap & M, CFMap & N );
void compress ( const CanonicalForm & f, const CanonicalForm & g, CFMap & M, CFMap & N );
 
 
/* stuff included from ./cf_reval.h */
 
 
/**
 * class to generate random evaluation points
 *
 * @sa cf_eval.h
**/
class REvaluation : public Evaluation
{
protected: // neeeded in FFREvaluation
    CFRandom * gen;
public:
    REvaluation() : Evaluation(), gen(0) {}
    REvaluation( int min0, int max0, const CFRandom & sample ) : Evaluation( min0, max0 ), gen( sample.clone() ) {}
    REvaluation( const REvaluation & e );
    ~REvaluation();
    REvaluation& operator= ( const REvaluation & e );
    void nextpoint();
    void nextpoint(int n);
};
 
 
/* stuff included from ./fac_sqrfree.h */
 
 
/* stuff included from ./gfops.h */
 
 
long gf_gf2ff ( long a );
int gf_gf2ff ( int a );
 
bool gf_isff ( long a );
bool gf_isff ( int a );
 
 
/* stuff included from ./cf_hnf.h */
 
 
/**
 *
 * The input matrix A is square matrix of integers
 * output: the Hermite Normal Form of A; that is,
 * the unique m x m matrix whose rows span L, such that
 *
 * - lower triangular,
 * - the diagonal entries are positive,
 * - any entry below the diagonal is a non-negative number
 *   strictly less than the diagonal entry in its column.
 *
 * @note: uses NTL
 *
**/
 
CFMatrix* cf_HNF(CFMatrix& A);
 
/**
 * performs LLL reduction.
 *
 * B is an m x n matrix, viewed as m rows of n-vectors.  m may be less
 * than, equal to, or greater than n, and the rows need not be
 * linearly independent.  B is transformed into an LLL-reduced basis,
 * and the return value is the rank r of B.  The first m-r rows of B
 * are zero.
 *
 * More specifically, elementary row transformations are performed on
 * B so that the non-zero rows of new-B form an LLL-reduced basis
 * for the lattice spanned by the rows of old-B.
 * The default reduction parameter is delta=3/4, which means
 * that the squared length of the first non-zero basis vector
 * is no more than 2^{r-1} times that of the shortest vector in
 * the lattice.
 *
 * @note: uses NTL or FLINT
**/
 
CFMatrix* cf_LLL(CFMatrix& A);
 
 
/* stuff included from ./singext.h */
 
 
void FACTORY_PUBLIC gmp_numerator ( const CanonicalForm & f, mpz_ptr result );
 
void FACTORY_PUBLIC gmp_denominator ( const CanonicalForm & f, mpz_ptr result );
 
int gf_value (const CanonicalForm & f );
 
CanonicalForm FACTORY_PUBLIC make_cf ( const mpz_ptr n );
 
CanonicalForm FACTORY_PUBLIC make_cf ( const mpz_ptr n, const mpz_ptr d, bool normalize );
 
CanonicalForm make_cf_from_gf ( const int z );
 
 
/* stuff included from ./cf_util.h */
 
int igcd (int a, int b);
int FACTORY_PUBLIC ipower ( int b, int n );
void factoryError_intern(const char *s);
EXTERN_VAR void (*factoryError)(const char *s);
 
/* stuff included from ./facIrredTest.h */
 
 
/// given some error probIrredTest detects irreducibility or reducibility of F
/// with confidence level 1-error
///
/// @return probIrredTest returns 1 for irreducibility, -1 for reducibility
///         or 0 if the test is not applicable
int FACTORY_PUBLIC probIrredTest (const CanonicalForm& F, ///< [in] some poly over Z/p
                   double error            ///< [in] 0 < error < 1
                  );
 
 
/* stuff included from ./facAbsFact.h */
 
/// absolute factorization of a multivariate poly over Q
///
/// @return absFactorize returns a list whose entries contain three
///         entities:
///         an absolute irreducible factor, an irreducible univariate polynomial
///         that defines the minimal field extension over which the irreducible
///         factor is defined (note: in case the factor is already defined over
///         Q[t]/(t), 1 is returned), and the multiplicity of the
///         absolute irreducible factor
CFAFList FACTORY_PUBLIC absFactorize (const CanonicalForm& G ///<[in] poly over Q
                      );
 
/* stuff included from ./cfModResultant.h */
 
/// modular resultant algorihtm over Z
///
/// @return @a resultantZ returns the resultant of A and B wrt. x
CanonicalForm
resultantZ (const CanonicalForm& A, ///<[in] some poly
            const CanonicalForm& B, ///<[in] some poly
            const Variable& x,      ///<[in] some polynomial variable
            bool prob= true         ///<[in] if true use probabilistic algorithm
           );
 
/* stuff included from ./facAlgFunc.h */
 
 
/// factorize a polynomial @a f that is irreducible over the ground field modulo
/// an extension given by an irreducible characteristic set @a as, @a f is
/// assumed to be integral, i.e. \f$ f\in K[x_1,\ldots,x_n]/(as) \f$, and each
/// element of @a as is assumed to be integral as well. \f$ K \f$ must be either
/// \f$ F_p \f$ or \f$ Q \f$.
///
/// @return the returned factors are not necessarily monic but only primitive
/// and the product of the factors equals @a f up to a unit.
CFFList facAlgFunc2 (const CanonicalForm & f,///<[in] univariate poly
                     const CFList & as       ///<[in] irreducible characteristic
                                             ///< set
                    );
 
/// factorize a polynomial @a f modulo an extension given by an irreducible
/// characteristic set as, @a f is assumed to be integral, i.e.
/// \f$ f\in K[x_1,\ldots,x_n]/(as) \f$, and each element of @a as is assumed to
/// be integral as well. \f$ K \f$ must be either \f$ F_p \f$ or \f$ Q \f$.
///
/// @return the returned factors are not necessarily monic but only primitive
/// and the product of the factors equals @a f up to a unit.
CFFList facAlgFunc (const CanonicalForm & f, ///<[in] univariate poly
                    const CFList & as        ///<[in] irreducible characteristic
                                             ///< set
                   );
 
/* stuff included from ./cfCharSetsUtil.h */
 
/**
 * class to store factors that get removed during char set computation
**/
class StoreFactors
{
  public:
    CFList FS1; ///< factors that were removed
    CFList FS2; ///< candidate factors that might get removed
    inline StoreFactors& operator= (const StoreFactors& value)
    {
      if ( this != &value )
      {
        FS1 = value.FS1;
        FS2 = value.FS2;
      }
      return *this;
    }
};
 
CanonicalForm
Prem (const CanonicalForm& F, const CanonicalForm& G);
 
 
/* stuff included from ./cfCharSets.h */
 
 
/// basic set in the sense of Wang a.k.a. minimal ascending set in the sense of
/// Greuel/Pfister
CFList
basicSet (const CFList& PS);
 
/// characteristic set
CFList
charSet (const CFList& PS);
 
/// modified medial set
CFList
modCharSet (const CFList& PS, StoreFactors& StoredFactors,
            bool removeContents= true);
 
CFList
modCharSet (const CFList& PS, bool removeContents);
 
CFList
charSetViaCharSetN (const CFList& PS);
 
CFList
charSetN (const CFList &PS);
 
/// modified characteristic set, i.e. a characteristic set with certain
/// factors removed
CFList
charSetViaModCharSet (const CFList& PS, StoreFactors& StoredFactors,
                      bool removeContents= true);
 
/// modified characteristic set, i.e. a characteristic set with certain
/// factors removed
CFList
charSetViaModCharSet (const CFList& PS, bool removeContents= true);
 
/// characteristic series
ListCFList
charSeries (const CFList& L);
 
/// irreducible characteristic series
ListCFList FACTORY_PUBLIC
irrCharSeries (const CFList & PS);
 
// the next three give you a heuristically optimal reorderd list of the
// variables. For internal and external (e.g. Singular/Macaulay2) library use.
// This is really experimental!
// See the comments in reorder.cc.
//
// this gives you a heuristically optimal ordering for the ring variables
// if you use the irreducible characteristic series.
Varlist neworder (const CFList & PolyList);
 
// the same as neworder(...) only returning a list of CanonicalForm 's
// (i.e. the variables as CanonicalForms)
CFList newordercf (const CFList & PolyList);
 
// the same as neworder(...) only returning a list of int 's (i.e. the levels)
IntList FACTORY_PUBLIC neworderint (const CFList & PolyList);
 
// for library internal use only:
// next function reorders the variables in PS:
// a code segment to use:
// ...
// #include "tmpl_inst.h" // for typedef's
// CFList PS= <setup-your-list-of-CanonicalForms>;
// Varlist betterorder= neworder(PS);
// PS= reorder(betterorder,PS); // reorder variables in PS from oldorder
//                                 to betterorder
// ListCFList Q= IrrCharSeries( PS );
// Q= reorder(betterorder,Q);   // revert ordering to oldorder
//
CFList reorder (const Varlist & betterorder, const CFList & PS);
CFFList reorder (const Varlist & betterorder, const CFFList & PS);
ListCFList reorder (const Varlist & betterorder, const ListCFList & Q);
 
/* stuff included from ./cfUnivarGcd.h */
 
CanonicalForm FACTORY_PUBLIC
extgcd ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & a, CanonicalForm & b );
 
 
#endif /* ! INCL_FACTORY_H */