cfCharSetsUtil.cc File Reference

This file provides utility functions to compute characteristic sets. More...

#include "config.h"
#include "canonicalform.h"
#include "cf_algorithm.h"
#include "cfCharSetsUtil.h"

Go to the source code of this file.

Macros
#define	__ARRAY_INIT__   -1
#define	__INIT_GAP__   3

Functions
int	degpsmax (const CFList &PS, const Variable &x, Intarray &A, Intarray &C)
int	degpsmin (const CFList &PS, const Variable &x, Intarray &A, Intarray &B, Intarray &C, Intarray &D)
int	Tdeg (const CFList &PS, const Variable &x, Intarray &A, Intarray &B, Intarray &C, Intarray &D, Intarray &E, Intarray &F)
int	nr_of_poly (const CFList &PS, const Variable &x, Intarray &G)
int	degord (const Variable &x, const Variable &y, const CFList &PS, Intarray &A, Intarray &B, Intarray &C, Intarray &D, Intarray &E, Intarray &F, Intarray &G)
Variable	get_max_var (const CFList &PS)
CFList	only_in_one (const CFList &PS, const Variable &x)
void	initArray (const int highest_level, Intarray &A, Intarray &B, Intarray &C, Intarray &D, Intarray &E, Intarray &F, Intarray &G)
Varlist	reorderb (const Varlist &difference, const CFList &PS, const int highest_level)
CFList	swapvar (const CFList &PS, const Variable &x, const Variable &y)
	swapvar a whole list of CanonicalForms More...
CFFList	swapvar (const CFFList &PS, const Variable &x, const Variable &y)
bool	lowerRank (const CanonicalForm &F, const CanonicalForm &G, int &ind)
CanonicalForm	lowestRank (const CFList &L)
int	minLevel (const CFList &L)
void	sortListCFList (ListCFList &list)
	sort in descending order of length of elements More...
void	sortCFListByLevel (CFList &list)
	sort in descending order of level of elements More...
bool	isSubset (const CFList &PS, const CFList &Cset)
	is PS a subset of Cset ? More...
void	inplaceUnion (const ListCFList &a, ListCFList &b)
	Union of a and b stored in b. More...
ListCFList	adjoin (const CFList &is, const CFList &qs, const ListCFList &qh)
ListCFList	adjoinb (const CFList &is, const CFList &qs, const ListCFList &qh, const CFList &cs)
void	select (const ListCFList &ppi, int length, ListCFList &ppi1, ListCFList &ppi2)
CanonicalForm	normalize (const CanonicalForm &F)
	normalize a poly, i.e. in char 0 clear denominators, remove integer content in char p divide by leading coeff More...
CanonicalForm	Prem (const CanonicalForm &F, const CanonicalForm &G)
	pseudo remainder of F by G with certain factors of LC (g) cancelled More...
CanonicalForm	Premb (const CanonicalForm &f, const CFList &L)
	pseudo remainder of f by L with faster test for remainder being zero More...
CanonicalForm	Prem (const CanonicalForm &f, const CFList &L)
	pseudo remainder of f by L More...
CFList	uniGcd (const CFList &L)
CFList	initials (const CFList &L)
CFList	factorsOfInitials (const CFList &L)
void	removeContent (CanonicalForm &F, CanonicalForm &cF)
CFList	factorPSet (const CFList &PS)
void	removeFactors (CanonicalForm &r, StoreFactors &StoredFactors, CFList &removedFactors)
CFList	removeContent (const CFList &PS, StoreFactors &StoredFactors)
bool	contractsub (const CFList &cs1, const CFList &cs2)
ListCFList	contract (const ListCFList &cs)

Detailed Description

This file provides utility functions to compute characteristic sets.

Note

some of the code is code from libfac or derived from code from libfac. Libfac is written by M. Messollen. See also COPYING for license information and README for general information on characteristic sets.

Authors

Martin Lee

Definition in file cfCharSetsUtil.cc.

Macro Definition Documentation

__ARRAY_INIT__

#define __ARRAY_INIT__   -1

Definition at line 23 of file cfCharSetsUtil.cc.

__INIT_GAP__

#define __INIT_GAP__   3

Definition at line 257 of file cfCharSetsUtil.cc.

Function Documentation

adjoin()

ListCFList adjoin	(	const CFList &	is,
		const CFList &	qs,
		const ListCFList &	qh
	)

Definition at line 495 of file cfCharSetsUtil.cc.

{
  ListCFList iss, qhi;
  ListCFListIterator j;
  CFList iscopy, itt;
  CFListIterator i;
  int ind, length;
 
  for (i= is; i.hasItem(); i++)
  {
    if (i.getItem().level() > 0)
      iscopy= Union (CFList (i.getItem()), iscopy);
  }
  if (iscopy.isEmpty())
    return iss;
 
  qhi= Difference (qh, qs);
  length= qhi.length();
 
  for (i= iscopy; i.hasItem(); i++)
  {
    itt= Union (qs, CFList (i.getItem()));
    ind= 0;
    if (length > 0)
    {
      for (j= qhi; j.hasItem(); j++)
      {
        if (isSubset (j.getItem(), itt))
          ind= 1;
      }
    }
    if (ind == 0)
      iss.append (itt);
  }
  return iss;
}

adjoinb()

ListCFList adjoinb	(	const CFList &	is,
		const CFList &	qs,
		const ListCFList &	qh,
		const CFList &	cs
	)

Definition at line 533 of file cfCharSetsUtil.cc.

{
  ListCFList iss, qhi;
  ListCFListIterator j;
  CFList iscopy, itt;
  CFListIterator i;
  int ind, length;
 
  for (i= is ; i.hasItem(); i++)
  {
    if (i.getItem().level() > 0)
      iscopy= Union (CFList (i.getItem()), iscopy);
  }
  if (iscopy.isEmpty())
    return iss;
  qhi= Difference (qh, qs);
  length= qhi.length();
  for (i= iscopy; i.hasItem(); i++)
  {
    itt= Union (Union (qs, CFList (i.getItem())), cs);
    ind= 0;
    if (length > 0)
    {
      for (j= qhi; j.hasItem(); j++)
      {
        if (isSubset (j.getItem(), itt))
          ind= 1;
      }
    }
    if (ind == 0)
      iss.append(itt);
  }
  return iss;
}

contract()

ListCFList contract

(

const ListCFList &

cs

)

Definition at line 926 of file cfCharSetsUtil.cc.

{
  ListCFList mem, ts;
  CFList iitem, jitem;
 
  if (cs.length() < 2)
    return cs;
 
  int l= cs.length();
  int ii= 1;
  ListCFListIterator j;
  for (ListCFListIterator i= cs; i.hasItem() && ii < l; i++, ii++)
  {
    iitem= i.getItem();
    if (!find (mem, iitem))
    {
      j= i;
      j++;
      for (; j.hasItem(); j++)
      {
        jitem= j.getItem();
        if (!find (mem, jitem))
        {
          if (contractsub (iitem, jitem))
          {
            ts.append (jitem);
            mem.append (jitem);
          }
          else
          {
            if (contractsub (jitem, iitem))
              ts.append (iitem); // no mem.append (item) because we assume cs does not contain duplicate entries
          }
        }
      }
    }
  }
  return Difference (cs,ts);
}

contractsub()

bool contractsub	(	const CFList &	cs1,
		const CFList &	cs2
	)

Definition at line 904 of file cfCharSetsUtil.cc.

{
  CFListIterator i;
 
  CanonicalForm r;
  for (i= cs1; i.hasItem(); i++)
  {
    if (Prem (i.getItem(), cs2) != 0)
      return false;
  }
 
  CFList is= factorsOfInitials (cs1);
 
  for (i= is; i.hasItem(); i++)
  {
    if (Prem (i.getItem(), cs2) == 0)
      return false;
  }
  return true;
}

degord()

int degord	(	const Variable &	x,
		const Variable &	y,
		const CFList &	PS,
		Intarray &	A,
		Intarray &	B,
		Intarray &	C,
		Intarray &	D,
		Intarray &	E,
		Intarray &	F,
		Intarray &	G
	)

Definition at line 162 of file cfCharSetsUtil.cc.

{
  int xlevel= level(x), ylevel= level(y);
 
  if      (degpsmax(PS,y,A,C) < degpsmax(PS,x,A,C))         return 1;
  else if (degpsmax(PS,x,A,C) < degpsmax(PS,y,A,C) )        return 0;
  else if (C[ylevel] < C[xlevel])                           return 1;
  else if (C[xlevel] < C[ylevel])                           return 0;
  else if (degpsmin(PS,x,A,B,C,D) < degpsmin(PS,y,A,B,C,D)) return 1;
  else if (degpsmin(PS,y,A,B,C,D) < degpsmin(PS,x,A,B,C,D)) return 0;
  else if (D[ylevel] < D[xlevel])                           return 1;
  else if (D[xlevel] < D[ylevel])                           return 0;
  else if (Tdeg(PS,y,A,B,C,D,E,F) < Tdeg(PS,x,A,B,C,D,E,F)) return 1;
  else if (Tdeg(PS,x,A,B,C,D,E,F) < Tdeg(PS,y,A,B,C,D,E,F)) return 0;
  else if (F[ylevel] < F[xlevel])                           return 1;
  else if (F[xlevel] < F[ylevel])                           return 0;
  else if (nr_of_poly(PS,x,G) <= nr_of_poly(PS,y,G))        return 1;
  else return 0;
}

degpsmax()

int degpsmax	(	const CFList &	PS,
		const Variable &	x,
		Intarray &	A,
		Intarray &	C
	)

Definition at line 27 of file cfCharSetsUtil.cc.

{
  int varlevel= level(x);
  if (A[varlevel] != __ARRAY_INIT__)
    return A[varlevel];
  int max= 0, temp, count= 0;
 
  for (CFListIterator i= PS; i.hasItem(); i++)
  {
    temp= degree (i.getItem(), x);
    if (temp > max)
    {
      max= temp;
      count = 0;
    }
    if (temp == max)
      count += max;  // we count the number of polys
  }
  A[varlevel]= max;
  C[varlevel]= count;
  return max;
}

degpsmin()

int degpsmin	(	const CFList &	PS,
		const Variable &	x,
		Intarray &	A,
		Intarray &	B,
		Intarray &	C,
		Intarray &	D
	)

Definition at line 54 of file cfCharSetsUtil.cc.

{
  int varlevel= level(x);
  if (B[varlevel] != __ARRAY_INIT__ )
    return B[varlevel];
  int min= degpsmax (PS, x, A, C), temp, count= 0;
 
  if (min == 0)
  {
    B[varlevel]= min;
    D[varlevel]= min;
    return min;
  }
  else
  {
    for (CFListIterator i= PS; i.hasItem(); i++)
    {
      temp= degree (i.getItem(), x);
      if (temp < min && temp != 0)
      {
        min= temp;
        count= 0;
      }
      if (temp == min)
        count += min; // we count the number of polys
    }
  }
  B[varlevel]= min;
  D[varlevel]= count;
  return min;
}

factorPSet()

CFList factorPSet

(

const CFList &

PS

)

Definition at line 805 of file cfCharSetsUtil.cc.

{
  CFList result;
  CFFList factors;
  CFFListIterator j;
 
  for (CFListIterator i= PS; i. hasItem(); i++)
  {
    factors= factorize (i.getItem());
    if (factors.getFirst().factor().inCoeffDomain())
      factors.removeFirst();
    for (j= factors; j.hasItem(); j++ )
      result= Union (result, CFList (normalize (j.getItem().factor())));
  }
  return result;
}

factorsOfInitials()

CFList factorsOfInitials

(

const CFList &

L

)

Definition at line 755 of file cfCharSetsUtil.cc.

{
  CFList result;
  CFFList factors;
  CanonicalForm tmp;
 
  for (CFListIterator i= L; i.hasItem(); i++)
  {
    factors= factorize (LC (i.getItem()));
    for (CFFListIterator j= factors; j.hasItem(); j++)
    {
      tmp= j.getItem().factor();
      if (!tmp.inCoeffDomain())
        result= Union (result, CFList (normalize (tmp)));
    }
  }
 
  return result;
}

get_max_var()

Variable get_max_var

(

const CFList &

PS

)

Definition at line 196 of file cfCharSetsUtil.cc.

{
  Variable x= PS.getFirst().mvar(), y;
  for (CFListIterator i= PS; i.hasItem(); i++)
  {
    y= i.getItem().mvar();
    if (y > x)
      x= y;
  }
  return x;
}

initArray()

void initArray	(	const int	highest_level,
		Intarray &	A,
		Intarray &	B,
		Intarray &	C,
		Intarray &	D,
		Intarray &	E,
		Intarray &	F,
		Intarray &	G
	)

Definition at line 228 of file cfCharSetsUtil.cc.

{
  for (int i=1 ; i <= highest_level; i ++)
  {
    A[i]= __ARRAY_INIT__;
    B[i]= __ARRAY_INIT__;
    C[i]= __ARRAY_INIT__;
    D[i]= __ARRAY_INIT__;
    E[i]= __ARRAY_INIT__;
    F[i]= __ARRAY_INIT__;
    G[i]= __ARRAY_INIT__;
  }
}

initials()

CFList initials

(

const CFList &

L

)

Definition at line 743 of file cfCharSetsUtil.cc.

{
  CFList result;
  for (CFListIterator iter= L; iter.hasItem(); iter++)
  {
    if (!LC(iter.getItem()).inCoeffDomain())
      result.append (LC (iter.getItem()));
  }
  return result;
}

inplaceUnion()

void inplaceUnion	(	const ListCFList &	a,
		ListCFList &	b
	)

Union of a and b stored in b.

Definition at line 473 of file cfCharSetsUtil.cc.

{
  if (a.isEmpty())
    return;
  if (b.isEmpty())
  {
    b= a;
    return;
  }
 
  ListCFListIterator i;
  CFList elem;
 
  for (i= a; i.hasItem(); i++)
  {
    elem= i.getItem();
    if ((!elem.isEmpty()) && (!find (b, elem)))
      b.insert(elem);
  }
}

isSubset()

bool isSubset	(	const CFList &	PS,
		const CFList &	Cset
	)

is PS a subset of Cset ?

Definition at line 461 of file cfCharSetsUtil.cc.

{
  for (CFListIterator i= PS; i.hasItem(); i++)
  {
    if (!find (Cset, i.getItem()))
      return 0;
  }
  return 1;
}

lowerRank()

bool lowerRank	(	const CanonicalForm &	F,
		const CanonicalForm &	G,
		int &	ind
	)

Definition at line 325 of file cfCharSetsUtil.cc.

{
  int degF, degG, levelF, levelG;
 
  levelF= F.level();
  levelG= G.level();
  if (F.inCoeffDomain())
  {
    if (G.inCoeffDomain())
      ind= 1;
    return true;
  }
  else if (G.inCoeffDomain())
    return false;
  else if (levelF < levelG)
    return true;
  else if (levelF == levelG)
  {
    degF= degree(F);
    degG= degree(G);
    if (degF < degG)
      return true;
    else if (degF == degG)
      return lowerRank (LC (F), LC (G), ind);
    else
      return false;
  }
  return false;
}

lowestRank()

CanonicalForm lowestRank

(

const CFList &

L

)

Definition at line 357 of file cfCharSetsUtil.cc.

{
  CFListIterator i= L;
  CanonicalForm f;
  int ind= 0;
  if (!i.hasItem())
    return f;
 
  f= i.getItem();
  i++;
 
  while (i.hasItem())
  {
    if (lowerRank (i.getItem(), f, ind))
    {
      if (ind)
      {
        if (size (i.getItem()) < size (f))
          f= i.getItem();
        ind= 0;
      }
      else
        f= i.getItem();
    }
    i++;
  }
  return f;
}

minLevel()

int minLevel

(

const CFList &

L

)

Definition at line 386 of file cfCharSetsUtil.cc.

{
  if (L.isEmpty())
    return 0;
  int min= size (L.getFirst());
  return min;
}

normalize()

CanonicalForm normalize

(

const CanonicalForm &

F

)

normalize a poly, i.e. in char 0 clear denominators, remove integer content in char p divide by leading coeff

Definition at line 590 of file cfCharSetsUtil.cc.

{
  if (F.isZero())
    return F;
  if (getCharacteristic() == 0)
  {
    CanonicalForm G;
    bool isRat= isOn (SW_RATIONAL);
    if (!isRat)
      On (SW_RATIONAL);
    G= F;
    G *= bCommonDen (G);
    Off (SW_RATIONAL);
    G /= icontent (G);
    if (isRat)
      On (SW_RATIONAL);
    if (lc(G) < 0)
      G= -G;
    return G;
  }
 
  return F/lc (F);
}

nr_of_poly()

int nr_of_poly	(	const CFList &	PS,
		const Variable &	x,
		Intarray &	G
	)

Definition at line 146 of file cfCharSetsUtil.cc.

{
  int min= 0, varlevel= level(x);
  if (G[varlevel] != __ARRAY_INIT__)
    return G[varlevel];
  for (CFListIterator i= PS; i.hasItem(); i++)
  {
    min += 1;
    if (degree (i.getItem(), x) > 0)
      break;
  }
  G[varlevel]= min;
  return min;
}

only_in_one()

CFList only_in_one	(	const CFList &	PS,
		const Variable &	x
	)

Definition at line 212 of file cfCharSetsUtil.cc.

{
  CFList output;
 
  for (CFListIterator i= PS; i.hasItem(); i++ )
  {
    if (degree (i.getItem(), x) >= 1)
      output.insert (i.getItem());
    if (output.length() >= 2)
      break;
  }
  return output;
}

Prem() [1/2]

CanonicalForm Prem	(	const CanonicalForm &	F,
		const CanonicalForm &	G
	)

pseudo remainder of F by G with certain factors of LC (g) cancelled

Definition at line 616 of file cfCharSetsUtil.cc.

{
  CanonicalForm f, g, l, test, lu, lv, t, retvalue;
  int degF, degG, levelF, levelG;
  bool reord;
  Variable v, vg= G.mvar();
 
  if ( (levelF= F.level()) < (levelG= G.level()))
    return F;
  else
  {
    if ( levelF == levelG )
    {
      f= F;
      g= G;
      reord= false;
      v= F.mvar();
    }
    else
    {
      v= Variable (levelF + 1);
      f= swapvar (F, vg, v);
      g= swapvar (G, vg, v);
      reord= true;
    }
    degG= degree (g, v );
    degF= degree (f, v );
    if (degG <= degF)
    {
      l= LC (g);
      g= g - l*power (v, degG);
    }
    else
      l= 1;
    while ((degG <= degF) && (!f.isZero()))
    {
      test= gcd (l, LC(f));
      lu= l / test;
      lv= LC(f) / test;
      t= g*lv*power (v, degF - degG);
 
      if (degF == 0)
        f= 0;
      else
        f= f - LC (f)*power (v, degF);
 
      f= f*lu - t;
      degF= degree (f, v);
    }
 
    if (reord)
      retvalue= swapvar (f, vg, v);
    else
      retvalue= f;
 
    return retvalue;
  }
}

Prem() [2/2]

CanonicalForm Prem	(	const CanonicalForm &	f,
		const CFList &	L
	)

pseudo remainder of f by L

Definition at line 710 of file cfCharSetsUtil.cc.

{
  CanonicalForm rem= f;
  CFListIterator i= L;
 
  for (i.lastItem(); i.hasItem(); i--)
    rem= normalize (Prem (rem, i.getItem()));
 
  return rem;
}

Premb()

CanonicalForm Premb	(	const CanonicalForm &	f,
		const CFList &	L
	)

pseudo remainder of f by L with faster test for remainder being zero

Definition at line 677 of file cfCharSetsUtil.cc.

{
  CanonicalForm rem= f;
  CFList l= L;
  l.removeFirst();
  CFListIterator i= l;
 
  for (i.lastItem(); i.hasItem(); i--)
    rem= normalize (Prem (rem, i.getItem()));
 
  CanonicalForm tmp= L.getFirst()/content (L.getFirst());
 
  bool isRat= isOn (SW_RATIONAL);
  int ch=getCharacteristic();
  if (ch == 0 && !isRat)
    On (SW_RATIONAL);
  if (fdivides (tmp, rem))
  {
    if (ch == 0 && !isRat)
      Off (SW_RATIONAL);
    return 0;
  }
 
  if (ch == 0 && !isRat)
    Off (SW_RATIONAL);
 
  rem= normalize (Prem (rem, L.getFirst()));
 
  return rem;
}

removeContent() [1/2]

void removeContent	(	CanonicalForm &	F,
		CanonicalForm &	cF
	)

Definition at line 776 of file cfCharSetsUtil.cc.

{
  if (size (F) == 1)
  {
    CanonicalForm tmp= F;
    F= F.mvar();
    cF= tmp/F;
    if (!cF.inCoeffDomain())
      cF= normalize (cF);
    else
      cF= 0;
    F= normalize (F);
 
    return;
  }
 
  cF= content (F);
 
  if (cF.inCoeffDomain())
    cF= 0;
  else
  {
    cF= normalize (cF);
    F /= cF;
    F= normalize (F);
  }
}

removeContent() [2/2]

CFList removeContent	(	const CFList &	PS,
		StoreFactors &	StoredFactors
	)

Definition at line 879 of file cfCharSetsUtil.cc.

{
  CFListIterator i= PS;
  if ((!i.hasItem()) || (PS.getFirst().level() == 0 ))
    return PS;
 
  CFList output;
  CanonicalForm cc,elem;
 
  for (; i.hasItem(); i++)
  {
    elem= i.getItem();
    cc= content (elem, elem.mvar());
    if (cc.level() > 0 )
    {
      output.append (normalize (elem / cc));
      StoredFactors.FS1 = Union (CFList (normalize (cc)), StoredFactors.FS1);
    }
    else
      output.append(normalize (elem));
  }
  return output;
}

removeFactors()

void removeFactors	(	CanonicalForm &	r,
		StoreFactors &	StoredFactors,
		CFList &	removedFactors
	)

Definition at line 823 of file cfCharSetsUtil.cc.

{
  CanonicalForm quot;
  CFList testlist;
  int n= level(r);
  bool divides;
  CFListIterator j;
 
  for (int i=1; i<= n; i++)
    testlist.append (CanonicalForm (Variable (i)));
 
  // remove already removed factors
  for (j= StoredFactors.FS1; j.hasItem(); j++)
  {
    while (fdivides (j.getItem(), r, quot))
    {
      r= quot;
    }
  }
 
  for (j= StoredFactors.FS2; j.hasItem(); j++)
  {
    divides= false;
    if (j.getItem() != r)
    {
      while (fdivides (j.getItem(), r, quot))
      {
        divides= true;
        r= quot;
      }
      if (divides)
        removedFactors= Union (removedFactors, CFList (j.getItem()));
    }
  }
  r= normalize (r);
 
  // remove variables
  for (j= testlist; j.hasItem() && !r.isOne(); j++)
  {
    divides= false;
    if (j.getItem() != r)
    {
      while (fdivides (j.getItem(), r, quot))
      {
        divides= true;
        r= quot;
      }
      if (divides)
        removedFactors= Union (removedFactors, CFList (j.getItem()));
     }
  }
  r= normalize (r);
}

reorderb()

Varlist reorderb	(	const Varlist &	difference,
		const CFList &	PS,
		const int	highest_level
	)

Definition at line 259 of file cfCharSetsUtil.cc.

{
  Intarray A(1, highest_level), B(1, highest_level), C(1, highest_level),
           D(1, highest_level), E(1, highest_level), F(1, highest_level),
           G(1, highest_level);
  initArray (highest_level, A, B, C, D, E, F, G);
  int i= 0, j, n= difference.length(), gap= 1 + __INIT_GAP__;
  Variable temp;
  Array<Variable> v(0, n);
  VarlistIterator J;
 
  for (J= difference; J.hasItem(); J++ )
  {
    v[i]= J.getItem();
    i++;
  }
 
  while (gap <= n)
    gap = __INIT_GAP__ * gap + 1;
  gap /= __INIT_GAP__;
 
  while (gap > 0)
  {
    for (i= gap; i <= n - 1; i++)
    {
      temp= v[i];
      for (j= i - gap; j >=0 ; j -= gap)
      {
        if (degord (v[j], temp, PS, A, B, C, D, E, F, G))
          break;
        v[j + gap]= v[j];
      }
      v[j + gap]= temp;
    }
    gap /= __INIT_GAP__;
  }
  Varlist output;
  for (i= 0; i <= n - 1; i++)
    output.append (v[i]);
  return output;
}

select()

void select	(	const ListCFList &	ppi,
		int	length,
		ListCFList &	ppi1,
		ListCFList &	ppi2
	)

Definition at line 570 of file cfCharSetsUtil.cc.

{
  CFList elem;
  for (ListCFListIterator i= ppi; i.hasItem(); i++)
  {
    elem= i.getItem();
    if (!elem.isEmpty())
    {
      if (length <= elem.length())
        ppi2.append(elem);
      else
        ppi1.append(elem);
    }
  }
}

sortCFListByLevel()

void sortCFListByLevel

(

CFList &

list

)

sort in descending order of level of elements

Definition at line 428 of file cfCharSetsUtil.cc.

{
  int l= 1;
  int k= 1;
  CanonicalForm buf;
  CFListIterator m;
  for (CFListIterator i= list; l <= list.length(); i++, l++)
  {
    for (CFListIterator j= list; k <= list.length() - l; k++)
    {
      m= j;
      m++;
      if ((size (j.getItem()) < size (m.getItem())) ||
          ((size (j.getItem()) == size (m.getItem()))
            && (j.getItem().level() < m.getItem().level())))
      {
        buf= m.getItem();
        m.getItem()= j.getItem();
        j.getItem()= buf;
        j++;
        j.getItem()= m.getItem();
      }
      else
        j++;
    }
    k= 1;
  }
}

sortListCFList()

void sortListCFList

(

ListCFList &

list

)

sort in descending order of length of elements

Definition at line 396 of file cfCharSetsUtil.cc.

{
  int l= 1;
  int k= 1;
  CFList buf;
  ListCFListIterator m;
  for (ListCFListIterator i= list; l <= list.length(); i++, l++)
  {
    for (ListCFListIterator j= list; k <= list.length() - l; k++)
    {
      m= j;
      m++;
      if ((j.getItem().length() < m.getItem().length()) ||
          (j.getItem().length() == m.getItem().length() &&
           minLevel (j.getItem()) > minLevel (m.getItem())))
      {
        buf= m.getItem();
        m.getItem()= j.getItem();
        j.getItem()= buf;
        j++;
        j.getItem()= m.getItem();
      }
      else
        j++;
    }
    k= 1;
  }
}

swapvar() [1/2]

CFFList swapvar	(	const CFFList &	PS,
		const Variable &	x,
		const Variable &	y
	)

Definition at line 314 of file cfCharSetsUtil.cc.

{
  CFFList ps;
 
  for (CFFListIterator i= PS; i.hasItem(); i++)
    ps.append (CFFactor (swapvar (i.getItem().factor(), x, y),
                         i.getItem().exp()));
  return ps;
}

swapvar() [2/2]

CFList swapvar	(	const CFList &	PS,
		const Variable &	x,
		const Variable &	y
	)

swapvar a whole list of CanonicalForms

Definition at line 304 of file cfCharSetsUtil.cc.

{
  CFList ps;
 
  for (CFListIterator i= PS; i.hasItem(); i++)
    ps.append (swapvar (i.getItem(), x, y));
  return ps;
}

Tdeg()

int Tdeg	(	const CFList &	PS,
		const Variable &	x,
		Intarray &	A,
		Intarray &	B,
		Intarray &	C,
		Intarray &	D,
		Intarray &	E,
		Intarray &	F
	)

Definition at line 91 of file cfCharSetsUtil.cc.

{
  int k= degpsmin (PS, x, A, B, C, D), varlevel= level(x), min= 0;
 
  if (E[varlevel] != __ARRAY_INIT__)
    return E [varlevel];
  if (k == 0)
  {
    E[varlevel]= 0;
    F[varlevel]= 0;
  }
  else
  {
    int nopslc= 0;
    CFList LCdegList;
    CanonicalForm elem;
    CFListIterator i;
 
    for (i= PS; i.hasItem(); i++)
    {
      elem= i.getItem();
      if (degree (elem, x) == k)
        LCdegList.append (LC (elem, x));
    }
 
    if (LCdegList.length() > 0)
    {
      CFList TermList;
      int newmin, newnopslc;
 
      min= totaldegree (LCdegList.getFirst());
      TermList= get_Terms (LCdegList.getFirst());
      nopslc= TermList.length();
      for (i= LCdegList; i.hasItem(); i++)
      {
        elem= i.getItem();
        newmin= totaldegree(elem);
        TermList= get_Terms(elem);
        newnopslc= TermList.length();
        if (newmin < min)
          min= newmin;
        if (newnopslc < nopslc)
          nopslc= newnopslc;
      }
 
    }
    E[varlevel]= min;
    F[varlevel]= nopslc;
  }
  return min;
}

uniGcd()

CFList uniGcd

(

const CFList &

L

)

Definition at line 721 of file cfCharSetsUtil.cc.

{
  CFList tmp;
  CanonicalForm g;
  CFListIterator i;
  for (i= L; i.hasItem(); i++)
  {
    if (i.getItem().isUnivariate() && i.getItem().level() == 1)
      tmp.append (i.getItem());
  }
  if (tmp.length() <= 2)
    return L;
  i= tmp;
  g= i.getItem();
  i++;
  g= gcd (g,i.getItem());
  i++;
  for (; i.hasItem(); i++)
    g= gcd (g, i.getItem());
  return Union (Difference (L, tmp), CFList (g));
}