using namespace std;
#include "bignum.h"
#include "count.h"
#include "poly.h"
#include "algebra.h"
#include "gen.h"

void powgen::initialize(term& f, expr& E, int pow) {
    q = pow;
    n = E.numterms();
    if (n == 0) {
	Empty = true;
	return;
    }
    Empty = false;
    F0.move(f);
    F.resize(n+2);
    for(int k=1; k<= n; k++) {
	F[k].D = q;
	E.getfirst(F[k].t);
    }
    F[n].D = q;
    F[n+1].D = 0;
    F[n+1].M = 1;
    F[n+1].T = 1;
}

// describing multinomialcoeff * t1^d1 * t2^d2 * ... * tn^dn
// F[k].t = t_k (readonly)
// F[k].D = sum d_j, j>=k
// F[k].T = product tj^dj, j>=k
// F[k].M is the factor of the multinomial coeff for the terms k, k+1, ...
// F[n+1] is used as a sentinel
// F[1] is not maintained (getnext figures it out)
// initialized at the last term (it cycles immediately back to the first)
// getnext sets Empty when it gets back to the last term

void powgen::INC(int k) {
    if(k>n)
	return;
    if(k==1) {
	INC(2);
	return;
    }
    if(F[k].D < q) {
	F[k].D++;
	F[k].M *= q - F[k].D + 1;
	F[k].M /= F[k].D - F[k+1].D;
	term tc;
	tc = F[k].t;
	F[k].T *= tc;
	return;
    }
    INC(k+1);
    F[k].D = F[k+1].D;
    F[k].M = F[k+1].M;
    F[k].T = F[k+1].T;
    return;
}

term& powgen::generate(term &t) {
    assert(!Empty);
    term tc;
    INC(1);
    t = F0;
    tc = F[2].T;
    t *= tc;
    t *= F[2].M;
    tc = F[1].t;
    tc ^= q - F[2].D;
    t *= tc;
    Empty = F[n].D == q;
    return t;
}

// describing t_1 * t_2 * ... * t_n where t_k is the current term
//    from the kth expr E_k
// F[k].j = index of t_k in the terms of E_k
// F[k].numt is the number of terms in E_k
// F[k].t[j] = t_k
// F[k].last indicates that F[i].j == F[i].numt for i<=k
// F[0] is used as a sentinel
// last term corresponds to F[k].j == F[k].numt for all k
// initialized at the last term (it cycles immediately back to the first)
// generate sets Empty when it gets back to the last term

void prodgen::INC(int k) {
    if(k<1)
	return;
    if(F[k].j < F[k].numt) {
	F[k].j++;
	if(F[k].j == F[k].numt)
	    F[k].last = F[k-1].last;
    }
    else {
	INC(k-1);
	F[k].j = 1;
	F[k].last = 1 == F[k].numt;
    }
}

term& prodgen::generate(term &t) {
    assert(!Empty);
    term tc;
    INC(n);
    t = F[1].t[F[1].j];
    for(int k=2; k<=n; k++) {
	tc = F[k].t[F[k].j];
	t *= tc;
    }
    Empty = F[n].last;
    return t;
}

void prodgen::initialize(vector<expr>& E) {
    Empty = false;
    n = E.size();
    if(n == 0) {
	Empty = true;
	return;
    }
    for(int k=0; k<n; k++) {
	if(E[k].empty()) {
	    Empty = true;
	    return;
	}
    }
    F.resize(n+1);
    for(int k=0; k<n; k++) {
	F[k+1].numt = E[k].numterms();
	F[k+1].t.resize(F[k+1].numt+1);
	int i = 0;
	while(!E[k].empty())
	    E[k].getfirst(F[k+1].t[++i]);
	F[k+1].j = F[k+1].numt;
	F[k+1].last = true;
    }
    F[0].last = true;
}