#include "dimension.h"
#include "buchberger.h"

PolynomialSet radicalOfMonomialIdeal(PolynomialSet const &monomialGenerators)
{
  PolynomialSet temp=monomialGenerators;

  temp.markAndScale(LexicographicTermOrder()); //just to make sure that some term is marked

  PolynomialSet ret;
  for(PolynomialSet::const_iterator i=temp.begin();i!=temp.end();i++)
    {
      IntegerVector e=i->getMarked().m.exponent;
      e=e.supportVector();
      ret.push_back(Polynomial(Term(i->getMarked().c,Monomial(e))));
    }
  return ret;
}

static bool increase(IntegerVector &v, int &numberOfOnes)
{
  int i=0;
  while(i<v.size() && v[i]==1)
    {
      v[i]=0;
      numberOfOnes--;
      i++;
    }
  if(i==v.size())return false;
  v[i]=1;
  numberOfOnes++;
  return true;
}

int krullDimensionOfMonomialIdeal(PolynomialSet const &monomialGenerators)
{
  PolynomialSet temp=radicalOfMonomialIdeal(monomialGenerators);
  minimize(&temp);
  IntegerVectorList vectors;
  for(PolynomialSet::const_iterator i=temp.begin();i!=temp.end();i++)
    vectors.push_back(i->getMarked().m.exponent);

  assert(!vectors.empty());
  int n=vectors.begin()->size();
  IntegerVector subset(n);
  int numberOfOnes=0;
  int dimension=0;

  do
    {
      //  AsciiPrinter(Stderr).printVector(subset);

      if(numberOfOnes>dimension)
	{
	  bool ok=true;
	  for(IntegerVectorList::const_iterator i=vectors.begin();i!=vectors.end();i++)
	    if(i->divides(subset))
	      {
		ok=false;
		break;
	      }
	  if(ok)
	    dimension=numberOfOnes;
	}
    }
  while(increase(subset,numberOfOnes));

  return dimension;
}

int krullDimension(PolynomialSet const &groebnerBasis)
{
  return krullDimensionOfMonomialIdeal(groebnerBasis.markedTermIdeal());
}