variable_set.c

Go to the documentation of this file.

#include "variable_set.h"

#include "defines.h"

#include <string.h>
#include <math.h>


/*private function of adding a var to vs*/

void AddVariableInt(unsigned int varid,unsigned int p,Tvariable_set *vs);

void AddVariableInt(unsigned int varid,unsigned int p,Tvariable_set *vs)
{  
  signed int j;
  unsigned int s;

  if (vs->nvars==vs->maxvars)
    {
      MEM_DUP(vs->var_id,vs->maxvars,unsigned int);
      MEM_EXPAND(vs->power,vs->maxvars,unsigned int);
    }
  
  vs->var_id[vs->nvars]=varid;
  vs->power[vs->nvars]=p;
  vs->nvars++;

  /* Keep variables in order from lower to upper ID */
  j=vs->nvars-1;
  while((j>0)&&(vs->var_id[j-1]>vs->var_id[j]))
    {
      s=vs->var_id[j-1];
      vs->var_id[j-1]=vs->var_id[j];
      vs->var_id[j]=s;

      s=vs->power[j-1];
      vs->power[j-1]=vs->power[j];
      vs->power[j]=s;

      j--;
    }
}

void InitVarSet(Tvariable_set *vs)
{
  vs->nvars=0;
  vs->maxvars=INIT_NUM_VARIABLES;
  NEW(vs->var_id,vs->maxvars,unsigned int);
  NEW(vs->power,vs->maxvars,unsigned int);
}

void ResetVarSet(Tvariable_set *vs)
{
  vs->nvars=0;
}

void CopyVarSet(Tvariable_set *vs_dst,Tvariable_set *vs_orig)
{
  vs_dst->nvars=vs_orig->nvars;

  vs_dst->maxvars=vs_orig->maxvars; /*space for vars to be copied + some extra space for growing */

  NEW(vs_dst->var_id,vs_dst->maxvars,unsigned int);
  NEW(vs_dst->power,vs_dst->maxvars,unsigned int);

  memcpy(vs_dst->var_id,vs_orig->var_id,vs_dst->nvars*sizeof(unsigned int));
  memcpy(vs_dst->power,vs_orig->power,vs_dst->nvars*sizeof(unsigned int));
}

void ShiftVarIndexes(unsigned int nv,Tvariable_set *vs)
{
  unsigned int i;

  for(i=0;i<vs->nvars;i++)
    {
      if (vs->var_id[i]==nv)
        Error("Remove the variable before shifting the var indexes for the remaining vars");
      if (vs->var_id[i]>nv)
        vs->var_id[i]--;
    }
}

unsigned int CmpVarSet(Tvariable_set *vs1,Tvariable_set *vs2)
{
  unsigned int r;
  unsigned int i;

  if (vs1->nvars>vs2->nvars)
    r=2;
  else
    {
      if (vs2->nvars>vs1->nvars)
        r=1;
      else
        {
          i=0;
          while((i<vs1->nvars)&&
                (vs1->var_id[i]==vs2->var_id[i])&&
                (vs1->power[i]==vs2->power[i])) 
            i++;
  
          if (i==vs1->nvars)
            r=0;
          else
            {
              if (vs1->power[i]>vs2->power[i])
                r=2;
              else
                {
                  if (vs2->power[i]>vs1->power[i])
                    r=1;
                  else
                    {
                      if (vs1->var_id[i]>vs2->var_id[i])
                        r=1;
                      else
                        r=2;
                    }
                }
            }
        }
    }
  return(r);
}

boolean EmptyVarSet(Tvariable_set *vs)
{
  return(vs->nvars==0);
}

unsigned int GetPlaceinSet(unsigned int id,Tvariable_set *vs)
{ 
  boolean found=FALSE;
  unsigned int i;

  i=0;
  while((i<vs->nvars)&&(!found))
    {
      found=(id==vs->var_id[i]);
      if (!found) i++;
    }
    
  if (found)
    return(i);
  else
    return(NO_UINT); 
}

boolean VarIncluded(unsigned int id,Tvariable_set *vs)
{ 
  return((boolean)(GetPlaceinSet(id,vs)!=NO_UINT));
}

boolean Included(unsigned int id,unsigned int p,Tvariable_set *vs)
{
  boolean found=FALSE;
  unsigned int i;

  i=0;
  while((i<vs->nvars)&&(!found))
    {
      found=((id==vs->var_id[i])&&(p==vs->power[i]));
      if (!found) i++;
    }
  
  return(found);
}

/*True if they share a variable with the SAME exponent */
boolean VarSetIntersect(Tvariable_set *vs1,Tvariable_set *vs2)
{
  boolean found=FALSE;
  unsigned int i;
  
  i=0;
  while((i<vs1->nvars)&&(!found))
    {
      found=Included(vs1->var_id[i],vs1->power[i],vs2);
      if (!found) i++;
    }
  return(found);
}

/* result of vs1 \ vs2  (variables with different exponent are taken as different) */
/* observe that this operation is NOT inverse of the UnionVarSet */
void SubstractVarSet(Tvariable_set *vs1,Tvariable_set *vs2,Tvariable_set *v_out) 
{
  Tvariable_set v_aux;  
  unsigned int i;

  InitVarSet(&v_aux);

  for(i=0;i<vs1->nvars;i++)
    {
      if (!Included(vs1->var_id[i],vs1->power[i],vs2))
        AddVariableInt(vs1->var_id[i],vs1->power[i],&v_aux);
    }
  if ((v_out==vs1)||(v_out==vs2))
    DeleteVarSet(v_out);

  CopyVarSet(v_out,&v_aux);  

  DeleteVarSet(&v_aux);
}

/*result of v1+v2 : we want to keep all the variables and the maximum of the exponents
  in v1,v2 */
void UnionVarSet(Tvariable_set *vs1,Tvariable_set *vs2,Tvariable_set *v_out)
{
  Tvariable_set v_aux;
  unsigned int i,j,n;
  boolean found;

  CopyVarSet(&v_aux,vs1);
  n=v_aux.nvars;

  for(i=0;i<vs2->nvars;i++)
    {
      found=FALSE;
      j=0;
      while((j<n)&&(!found))
        {
          if (vs2->var_id[i]==v_aux.var_id[j])
              found=TRUE;
          else
            j++;
        }
      if (found)
        {
          if (vs2->power[i]>v_aux.power[j])
            v_aux.power[j]=vs2->power[i]; /*we keep the maximum order for this variable*/
        }
      else
        AddVariableInt(vs2->var_id[i],vs2->power[i],&v_aux);
    }

  if ((v_out==vs1)||(v_out==vs2))
    DeleteVarSet(v_out);

  CopyVarSet(v_out,&v_aux);  

  DeleteVarSet(&v_aux);
}

/*If already in the set, we just increse the exponent. We implement: (var_set)*x^p */
void AddVariable2Set(unsigned int varid,unsigned int p,Tvariable_set *vs)
{
  boolean found=FALSE;
  unsigned int i;

  i=0;
  while((i<vs->nvars)&&(!found))
    {
      found=(varid==vs->var_id[i]);
      if (!found) i++;
    }
  if (found)
    vs->power[i]+=p;
  else   
    AddVariableInt(varid,p,vs);
}

/*Independent of the exponent*/
void RemoveVariableFromSet(unsigned int varid,Tvariable_set *vs)
{
  boolean found=FALSE;
  unsigned int i,j;

  i=0;
  while((i<vs->nvars)&&(!found))
    {
      found=(varid==vs->var_id[i]);
      if (!found) i++;
    }
  if (found)
    {
      for(j=i+1;j<vs->nvars;j++)
        {
          vs->var_id[j-1]=vs->var_id[j];
          vs->power[j-1]=vs->power[j];
        }
      vs->nvars--;
    }
}

unsigned int VarSetOrder(Tvariable_set *vs)
{
  unsigned int i,o;
  
  o=0;
  for(i=0;i<vs->nvars;i++)
    o+=vs->power[i];
    
/*
  o=0;
  for(i=0;i<vs->nvars;i++)
    {
      if (vs->power[i]>o)
        o=vs->power[i];
    }
*/
  return(o);
}

unsigned int VariableSetSize(Tvariable_set *vs)
{
  return(vs->nvars);
}

unsigned int GetVariableN(unsigned int n,Tvariable_set *vs)
{
  if (n<vs->nvars)
    return(vs->var_id[n]);
  else
    {
      Error("Requested an element not included in VarSet");
      return(0);
    }
}

unsigned int *GetVariables(Tvariable_set *vs)
{
  return(vs->var_id);
}

unsigned int GetVariablePowerN(unsigned int n,Tvariable_set *vs)
{
  if (n<vs->nvars)
    return(vs->power[n]);
  else
    {
      Error("Requested an element not included in VarSet");
      return(0);
    }
}

unsigned int *GetPowers(Tvariable_set *vs)
{
  return(vs->power);
}

double EvaluateVarSet(double *varValues,Tvariable_set *vs)
{
  double f;
  unsigned int i;

  if (vs->nvars==0)
    Error("Should not evalute empty var sets");

  f=1.0;
  for(i=0;i<vs->nvars;i++)
    {
      if (vs->power[i]==1)
        f*=varValues[vs->var_id[i]];
      else
        f*=pow(varValues[vs->var_id[i]],(double)(vs->power[i]));
    }

  return(f);
}

void EvaluateVarSetInt(Tinterval *varValues,Tinterval *i_out,Tvariable_set *vs)
{
  unsigned int i;
  Tinterval i_aux;

  if (vs->nvars==0)
    Error("Should not evalute empty var sets");
  
  NewInterval(1,1,i_out);
  for(i=0;i<vs->nvars;i++)
    {
      if (vs->power[i]==1)
        IntervalProduct(i_out,&(varValues[vs->var_id[i]]),i_out);
      else
        {
          IntervalPow(&(varValues[vs->var_id[i]]),vs->power[i],&i_aux);
          IntervalProduct(i_out,&i_aux,i_out);
        }
    }
}

unsigned int DeriveVarSet(unsigned int nv,Tvariable_set *dvs,Tvariable_set *vs)
{
  unsigned int i,p; 

  dvs->maxvars=vs->maxvars; 

  NEW(dvs->var_id,dvs->maxvars,unsigned int);
  NEW(dvs->power,dvs->maxvars,unsigned int);

  dvs->nvars=0;
  p=0;
  for(i=0;i<vs->nvars;i++)
    {
      if (vs->var_id[i]==nv)
        {
          p=vs->power[i];
          if (vs->power[i]>1)
            {
              dvs->var_id[dvs->nvars]=vs->var_id[i];
              dvs->power[dvs->nvars]=p-1;
              dvs->nvars++;
            }
        }
      else
        {
          dvs->var_id[dvs->nvars]=vs->var_id[i];
          dvs->power[dvs->nvars]=vs->power[i];
          dvs->nvars++;
        }
    }
  return(p);
}

void PrintVarSet(FILE *f,char **varNames,Tvariable_set *vs)
{
  unsigned int i; 

  if (vs->nvars>0)
    {
      for(i=0;i<vs->nvars;i++)
        {
          if (i>0) fprintf(f,"*");

          if (varNames!=NULL)
            { 
              char *n;

              n=varNames[vs->var_id[i]];
              PRINT_VARIABLE_NAME(f,n);
            }
          else
            fprintf(f,"v_%u",vs->var_id[i]);

          if (vs->power[i]>1)
            fprintf(f,"^%d",vs->power[i]);
        }
    }
}

void DeleteVarSet(Tvariable_set *vs)
{
  free(vs->var_id);
  free(vs->power);
}