libsingular4-dev-common 1:4.1.0-p3+ds-2build1 / usr / include / singular / factory / factory.h

/* 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 <stdint.h>
#ifdef HAVE_OMALLOC
#include <omalloc/omallocClass.h>
#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 factoryVersion[];
extern const char factoryConfiguration[];


/* stuff included from ./cf_primes.h */


int cf_getPrime( int i );

int cf_getNumPrimes();

int cf_getSmallPrime( int i );

int cf_getNumSmallPrimes();

int cf_getBigPrime( int i );

int cf_getNumBigPrimes();


/* stuff included from ./cf_defs.h */


#define LEVELBASE -1000000
#define LEVELTRANS -500000
#define LEVELQUOT 1000000
#define LEVELEXPR 1000001

#define UndefinedDomain 32000
#define GaloisFieldDomain 4
#define FiniteFieldDomain 3
#define RationalDomain 2
#define IntegerDomain 1

/// 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;


/* stuff included from ./variable.h */


class CanonicalForm;

/**
 * factory's class for variables
**/
class 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 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 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 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 CanonicalForm
#ifdef HAVE_OMALLOC
       : public omallocClass
#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 bool operator == ( const CanonicalForm&, const CanonicalForm& );
    friend bool operator != ( const CanonicalForm&, const CanonicalForm& );
    friend bool operator > ( const CanonicalForm&, const CanonicalForm& );
    friend bool operator < ( const CanonicalForm&, const CanonicalForm& );

    // arithmetic operators
    friend CF_NO_INLINE CanonicalForm operator - ( const CanonicalForm& );

    friend void divrem ( const CanonicalForm&, const CanonicalForm&, CanonicalForm&, CanonicalForm& );
    friend bool divremt ( const CanonicalForm&, const CanonicalForm&, CanonicalForm&, CanonicalForm& );
    friend bool tryDivremt ( const CanonicalForm&, const CanonicalForm&, CanonicalForm&, CanonicalForm&, const CanonicalForm&, bool& );

    friend CanonicalForm bgcd ( const CanonicalForm &, const CanonicalForm & );
    friend CanonicalForm bextgcd ( const CanonicalForm &, const CanonicalForm &, CanonicalForm &, CanonicalForm & );

    // input/output
#ifndef NOSTREAMIO
   void print( OSTREAM&, char * ) const;
   void print( OSTREAM& ) const;
   friend OSTREAM& operator << ( OSTREAM&, const CanonicalForm& );
   friend ISTREAM& operator >> ( ISTREAM&, CanonicalForm& );
#endif /* NOSTREAMIO */

    // obsolete methods
    CanonicalForm genZero() const;
    CanonicalForm genOne() const;

    friend class CFIterator;
};

CF_INLINE CanonicalForm
operator + ( const CanonicalForm&, const CanonicalForm& );

CF_NO_INLINE CanonicalForm
operator - ( const CanonicalForm&, const CanonicalForm& );

CF_INLINE CanonicalForm
operator * ( const CanonicalForm&, const CanonicalForm& );

CF_NO_INLINE CanonicalForm
operator / ( const CanonicalForm&, const CanonicalForm& );

CF_NO_INLINE CanonicalForm
operator % ( const CanonicalForm&, const CanonicalForm& );

CF_NO_INLINE CanonicalForm
div ( const CanonicalForm&, const CanonicalForm& );

CF_NO_INLINE CanonicalForm
mod ( const CanonicalForm&, const CanonicalForm& );


//{{{ function declarations from canonicalform.cc
CanonicalForm blcm ( const CanonicalForm & f, const CanonicalForm & g );

CanonicalForm power ( const CanonicalForm & f, int n );

CanonicalForm power ( const Variable & v, int n );
//}}}

//{{{ function declarations from cf_gcd.cc
CanonicalForm gcd ( const CanonicalForm&, const CanonicalForm& );

CanonicalForm gcd_poly ( const CanonicalForm & f, const CanonicalForm & g );

CanonicalForm lcm ( const CanonicalForm&, const CanonicalForm& );

CanonicalForm pp ( const CanonicalForm& );

CanonicalForm content ( const CanonicalForm& );

CanonicalForm content ( const CanonicalForm&, const Variable& );

CanonicalForm icontent ( const CanonicalForm & f );

CanonicalForm vcontent ( const CanonicalForm & f, const Variable & x );
//}}}

//{{{ function declarations from cf_ops.cc
CanonicalForm swapvar ( const CanonicalForm &, const Variable &, const Variable & );

CanonicalForm 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 );

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 setCharacteristic( int c ); // -> Fp && Q
void setCharacteristic( int c, int n ); // -> PrimePower
void setCharacteristic( int c, int n, char name ); // -> GF(q)

int getCharacteristic();
int getGFDegree();
CanonicalForm getGFGenerator();

void On( int );
void Off( int );
bool 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 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 chineseRemainder ( const CanonicalForm & x1, const CanonicalForm & q1, const CanonicalForm & x2, const CanonicalForm & q2, CanonicalForm & xnew, CanonicalForm & qnew );

void chineseRemainder ( const CFArray & x, const CFArray & q, CanonicalForm & xnew, CanonicalForm & qnew );

void chineseRemainderCached(CFArray &a, CFArray &n, CanonicalForm &xnew, CanonicalForm &prod, CFArray &inv);


CanonicalForm Farey ( const CanonicalForm & f, const CanonicalForm & q );
//}}}

//{{{ function declarations from cf_factor.cc
extern int singular_homog_flag;

bool isPurePoly(const CanonicalForm & f);

bool isPurePoly_m(const CanonicalForm & f);

CFFList factorize ( const CanonicalForm & f, bool issqrfree = false );

CFFList factorize ( const CanonicalForm & f, const Variable & alpha );

CFFList 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 determinant ( const CFMatrix & M, int n );
//}}}

//{{{ function declarations from cf_resultant.cc
CFArray subResChain ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x );

CanonicalForm 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 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 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 */


#ifdef HAVE_NTL

/**
 *
 * 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
**/

CFMatrix* cf_LLL(CFMatrix& A);

#endif


/* stuff included from ./singext.h */


void gmp_numerator ( const CanonicalForm & f, mpz_ptr result );

void gmp_denominator ( const CanonicalForm & f, mpz_ptr result );

int gf_value (const CanonicalForm & f );

CanonicalForm make_cf ( const mpz_ptr n );

CanonicalForm 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 ipower ( int b, int n );
void factoryError_intern(const char *s);
extern 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 probIrredTest (const CanonicalForm& F, ///< [in] some poly over Z/p
                   double error            ///< [in] 0 < error < 1
                  );


/* stuff included from ./facAbsFact.h */

#ifdef HAVE_NTL
/// 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 absFactorize (const CanonicalForm& G ///<[in] poly over Q
                      );
#endif

/* 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
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 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
extgcd ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & a, CanonicalForm & b );


#endif /* ! INCL_FACTORY_H */