void Tree4::_ComputeSize( const Configuration& config )
{
  int h;

  _k = config.GetInt( "k" );
  _n = config.GetInt( "n" );

  assert( _k == 4 && _n == 3 );
  
  gK = _k; gN = _n;
  
  _sources = powi( _k, _n );
  _dests   = powi( _k, _n );
  
  _speedup = new int[_n];
  _speedup[0] = _k;
  _speedup[1] = _k / 2;
  _speedup[2] = _k / 4;

  _size = 0;
  for ( h = 0; h < _n; ++h ) 
    _size += _speedup[h] * powi( _k, h );

  _channels = 2                  // Two Channels per Connection
    * _speedup[1] * powi( _k, 1) // Number of Middle Routers
    * ( 2 * _k );                // Connectivity of Middle Routers
}

void BezierBoundarySolver::Solve(BoundaryProblem *pProblem)
{
    //double time = Tic();
    BezierBoundaryProblem* bezierProblem = (BezierBoundaryProblem*)pProblem;

    //find the distance between the start and finish
    double dist = sqrt(powi(pProblem->m_dGoalPose[0],2) + powi(pProblem->m_dGoalPose[1],2));
    bezierProblem->m_dSegLength = dist/g_nAggressivenessDivisor;
    //first get the guess bezier
    if(bezierProblem->m_bSolved == false){

    }

    bezierProblem->m_dSegLength = std::max(1e-2,std::min(bezierProblem->m_dSegLength,dist/2));

    bezierProblem->m_dParams = Eigen::Vector4d(bezierProblem->m_dSegLength,bezierProblem->m_dSegLength,bezierProblem->m_dSegLength,bezierProblem->m_dSegLength);
    _Get5thOrderBezier(bezierProblem,bezierProblem->m_dParams);

    //and now sample it
    _Sample5thOrderBezier(bezierProblem);

    //now iterate to reduce curvature
    if(bezierProblem->m_bSolved == false){
        //_IterateCurvatureReduction(bezierProblem,bezierProblem->m_dParams);
        //_IterateCurvatureReduction(bezierProblem,bezierProblem->m_dParams);
    }

    //indicate that the problem has been solved
    bezierProblem->m_bSolved = true;

    //dout("2D solve with goal " << bezierProblem->m_dGoalPose.transpose() <<" took " << Toc(time) << " seconds.");
}

/**
 * Alloue l'espace mémoire nécessaire à la matrice.
 * Initialise toutes les cases à 0 sauf la plaque interne.
 * */
MAT init() {
    // Allouer la place pour la matrice
	mat =  malloc(sizeof(float) * TAILLE_MATRICE * TAILLE_MATRICE);
    // Initialisation de la matrice à 0 partout
    for (int i =0; i<TAILLE_MATRICE; i++) {
        for (int j=0; j<TAILLE_MATRICE; j++) {
            mat[i] = (float *) malloc(sizeof(float) * TAILLE_MATRICE);
            mat[i][j] = 0;
        }
    }
    
    // Initialisation de la zone chauffée initialement
    int idMin =  powi(2,n-1) - powi(2,n-4);
    int idMax = powi(2,n-1) + powi(2,n-4);
    /*printf("id min : %d,  ",idMin);
    printf("id max : %d\n",idMax);*/
    for (int i =  idMin ; i < idMax  ; i++) {
        for (int j =  idMin  ; j <  idMax ; j++) {
            mat[i][j] = TEMP_CHAUD;
        }
    }
    
    //~ mat[TAILLE_MATRICE/2][TAILLE_MATRICE/2] = TEMP_CHAUD;
    current = mat;

	return mat;
}

bool itstr(char *buffer, int buffer_len, int n, int z, int lz) {
    if (z > 1 && z <= sizeof(tokenChars)) {
        int k;
        int size, i, s;
        int pointer = 0;

        s = logi(n, z);

        if (lz > s)
            size = lz;
        else
            size = s;

        if (buffer_len < size) {
            return false;
        }

        for (i = lz - s; i > 0; i--) {
            buffer[pointer++] = '0';
        }

        for (i = s - 1; i >= 0; i--) {
            k = n / powi(z, i);
            buffer[pointer++] = tokenChars[k];
            n -= k * powi(z, i);
        }

        buffer[pointer] = 0;

        return true;
    }

    return false;
}

void FlatFlyOnChip::_ComputeSize( const Configuration &config )
{
  _k = config.GetInt( "k" );	// # of routers per dimension
  _n = config.GetInt( "n" );	// dimension
  _c = config.GetInt( "c" );    //concentration, may be different from k
  _r = _c + (_k-1)*_n ;		// total radix of the switch  ( # of inputs/outputs)

  //how many routers in the x or y direction
  _xcount = config.GetInt("x");
  _ycount = config.GetInt("y");
  assert(_xcount == _ycount);
  //configuration of hohw many clients in X and Y per router
  _xrouter = config.GetInt("xr");
  _yrouter = config.GetInt("yr");
  assert(_xrouter == _yrouter);
  gK = _k; 
  gN = _n;
  gC = _c;
  
  assert(_c == _xrouter*_yrouter);

  _sources = powi( _k, _n )*_c;   //network size
  _dests   = powi( _k, _n )*_c;

  _num_of_switch = _sources / _c;
  _channels = _num_of_switch * (_r - _c); 
  _size = _num_of_switch;

}

void badd(int b, int x)
{
	int m=0;
	//printf("%f", pow (t,d));
	
	while ( powi(b,m) <= x) //x<(int)pow(b,n+1))
	{
		m++;
		//printf("%i %li\n",m, powi(b,m));
	}
	int N=m-1;
	
	while (N>=0)
	{
		//printf("\nN=%i\n",N);
		if (powi(b,N)<=x)
		{
			int s=0;
			while ( s*powi(b,N) <= x) //x<(int)pow(b,n+1))
			{
				s++;
				//printf("%i %li\n",m, powi(b,m));
			}
			printf("%i", s-1);
			x=x-(s-1)*powi(b,N);
			N--;
		}
		else
		{
			printf("0");
			N--;
		
		}
	}
}

void BezierBoundarySolver::_Get5thOrderBezier(BezierBoundaryProblem *pProblem,const Eigen::Vector4d& params)
{
    //the order of the bezier
    const double n = 5.0;

    //calculate the offsets
    const double a1 = params[0];
    const double b1 = params[1];
    const double a2 = params[2];
    const double b2 = params[3];

    //create the handle x and y arrays

    pProblem->m_xVals = Eigen::VectorXd(n+1);
    pProblem->m_yVals = Eigen::VectorXd(n+1);

    const double kInit = pProblem->m_dStartPose[3] / pProblem->m_dAggressiveness;
    const double tGoal = pProblem->m_dGoalPose[2];
    const double kGoal = pProblem->m_dGoalPose[3] / pProblem->m_dAggressiveness;
    //dout("Getting b-curve with goal curvature of " << kGoal);

    //here we're assuming that tInit is always 0
    //so create a rotation matrix for the end goal
    Eigen::Matrix2d Rgoal;
    const double ct = cos(tGoal);
    const double st = sin(tGoal);
    Rgoal << ct, -st,
             st, ct;

    //set the starting point
    pProblem->m_xVals[0] = pProblem->m_yVals[0] = 0;

    //offset the second point knowing that tInit = 0
    pProblem->m_xVals[1] = a1;
    pProblem->m_yVals[1] = 0;

    //offset the third point using the initial curvature
    double h = kInit*powi(a1,2)*(n/(n+1));
    pProblem->m_xVals[2] = pProblem->m_xVals[1] + b1;
    pProblem->m_yVals[2] = pProblem->m_yVals[1] + h;

    //and now set the end points
    pProblem->m_xVals[5] = pProblem->m_dGoalPose[0];
    pProblem->m_yVals[5] = pProblem->m_dGoalPose[1];

    //calculate the offset
    Eigen::Vector2d offset(-a2,0);
    offset = Rgoal * offset;
    pProblem->m_xVals[4] = pProblem->m_xVals[5] + offset[0];
    pProblem->m_yVals[4] = pProblem->m_yVals[5] + offset[1];

    //calculate the final point using last curvature
    h = kGoal*powi(a2,2)*(n/(n+1.0));
    offset << -b2, -h;
    offset = Rgoal * offset;
    pProblem->m_xVals[3] = pProblem->m_xVals[4] + offset[0];
    pProblem->m_yVals[3] = pProblem->m_yVals[4] + offset[1];

}

int QTree::_OutputIndex( int height, int pos, int port )
{
  assert( height >= 0 && height < powi( _k,_n-1 ) );
  int c = _channels / 2;
  for ( int h = 0; h < height; h++) 
    c += powi( _k, h+1 );
  return ( c + _k * pos + port );
}

CMeshX2::CMeshX2( const Configuration &config, const string & name )
    : Network( config, name )
{

    _subMesh[0] = new CMesh( config, name );
    _subMesh[1] = new CMesh( config, name );

    int k = config.GetInt( "k" ) ;
    int n = config.GetInt( "n" ) ;
    int c = config.GetInt( "c" ) ;


    gK = _k = k ;
    gN = _n = n ;
    gC = _c = c ;

    _sources  = _c * powi( _k, _n); // Source nodes in network
    _dests    = _c * powi( _k, _n); // Destination nodes in network
    _size     = powi( _k, _n);      // Number of routers in network
    _channels = 0;

    _f_read_history = new int[_sources];
    _c_read_history = new int[_dests];

    for (int i = 0; i < _size; i++) {
        _f_read_history[i] = 0;
        _c_read_history[i] = 0;
    }

    _subNetAssignment[Flit::READ_REQUEST]
        = config.GetInt( "read_request_subnet" );
    assert( _subNetAssignment[Flit::READ_REQUEST] == 0 ||
            _subNetAssignment[Flit::READ_REQUEST] == 1);

    _subNetAssignment[Flit::READ_REPLY]
        = config.GetInt( "read_reply_subnet" );
    assert( _subNetAssignment[Flit::READ_REPLY] == 0 ||
            _subNetAssignment[Flit::READ_REPLY] == 1 );

    _subNetAssignment[Flit::WRITE_REQUEST]
        = config.GetInt( "write_request_subnet" );
    assert( _subNetAssignment[Flit::WRITE_REQUEST] == 0 ||
            _subNetAssignment[Flit::WRITE_REQUEST] == 1);

    _subNetAssignment[Flit::WRITE_REPLY]
        = config.GetInt( "write_reply_subnet" );
    assert( _subNetAssignment[Flit::WRITE_REPLY] == 0 ||
            _subNetAssignment[Flit::WRITE_REPLY] == 1 );

}

void MECS::_ComputeSize( const Configuration &config ) {
  _k = config.GetInt( "k" );	// # of routers per dimension
  _n = config.GetInt( "n" );	// dimension
  _c = config.GetInt( "c" );    //concentration, may be different from k

  xcount = config.GetInt("x");  //how many routers in the x or y direction
  ycount = config.GetInt("y");

  xrouter = config.GetInt("xr");  //configuration of hohw many clients in X and Y per router
  yrouter = config.GetInt("yr");


  //only support this configuration right now
  //need to extend to 256 nodes
  assert(_k ==4 && _n ==2 && _c == 4);

  _r = _c+4; //, chanenls are combined pior to entering the router
  gK = _k; 
  gN = _n;
  gC = _c;

  //standard traffic pattern shennanigin
  string fn;
  config.GetStr( "traffic", fn, "none" );
  if(fn.compare("neighbor")==0 || fn.compare("tornado")==0){
    realgk = 8;
    realgn = 2;
  } else {
    realgk = _k;
    realgn = _n;
  }

  _sources = powi( _k, _n )*_c;   //network size
  _dests   = powi( _k, _n )*_c;

  _num_of_switch = _sources / _c;
  //k-1 channels  per dimension per router, 
  //add 4 channels go from forwarder to the routers
  //yes, some of the channels will be forever idle in the corner routers
  _channels = _num_of_switch * ((_k-1)*_n+4);
  _channels_per_router =  ((_k-1)*_n+4);
  _size = _num_of_switch;

  cout<<"MECS"<<endl;
  cout<<"Number of sources "<<_sources<<endl;
  cout<<"Number of routers "<<_num_of_switch<<endl;
  cout<<"NUmber of channels "<<_channels<<endl;

}

void KNFly::_ComputeSize( const Configuration &config )
{
  _k = config.GetInt( "k" );
  _n = config.GetInt( "n" );

  gK = _k; gN = _n;

  _nodes = powi( _k, _n );

  // n stages of k^(n-1) k x k switches
  _size     = _n*powi( _k, _n-1 );

  // n-1 sets of wiring between the stages
  _channels = (_n-1)*_nodes;
}

int QTree::_RouterIndex( int height, int pos ) 
{
  int r = 0;
  for ( int h = 0; h < height; h++ ) 
    r += powi( _k, h );
  return (r + pos);
}

long long int powi(long long int basis, long long int exp)
{
	if (exp>0)
		return powi(basis,exp-1)*basis;
	else
		return 1;
}

int main(int argc, char *argv[]) {
	FILE *fp;
	char c;
	int j, n[13];

	if (argc != 2) {
		printf("Usage: %s [FILE]\n", argv[0]);
		return 1;
	}
	fp = fopen(*++argv, "r");
	while ((c = getc(fp)) != EOF) {
		int i = 0, u = 0;
		while (c != '\n' && c != EOF) {
			n[i++] = c - '0';
			c = getc(fp);
		}
		for (j = 0; j < powi(3, i - 1); j++) {
			if (ugly(j, i, n))
				u++;
		}

		printf("%d\n", u);
	}
	return 0;
}

void findNandK(){
    countAidx = countBidx = 1;
    for(T = B,i = 0; T != 1; i++)
        if(!(T%primes[i])){
            countB[countBidx] = 0;
            while(!(T%primes[i])){
                T/=primes[i];
                countB[countBidx]++;
            }
            factB[countBidx++] = primes[i];
        }
    if(countBidx-1){ 
        for(T = A,i = 0; T != 1; i++)
            if(!(T%primes[i])){
                countA[countAidx] = 0;
                while(!(T%primes[i])){
                    T/=primes[i];
                    countA[countAidx]++;
                }
                factA[countAidx++] = primes[i];
            }    
        k = countA[1];
        for(i = countAidx-1; i; i--) k = gcdT[k][countA[i]];
        for(i = countBidx-1; i; i--) k = gcdT[k][countB[i]];
    }
    N = 1;
    for(i = countBidx-1; i; i--) N *= powi(factB[i], countB[i] / k);
}

void shadowInit(BoardData3d *bd3d, renderdata *prd)
{
	int i;
	GLint stencilBits;

	if (bd3d->shadowsInitialised)
		return;

	/* Darkness as percentage of ambient light */
	prd->dimness = ((prd->lightLevels[1] / 100.0f) * (100 - prd->shadowDarkness)) / 100;

	for (i = 0; i < NUM_OCC; i++)
		bd3d->Occluders[i].handle = 0;

	/* Check the stencil buffer is present */
	glGetIntegerv(GL_STENCIL_BITS, &stencilBits);
	if (!stencilBits)
	{
		g_print("No stencil buffer - no shadows\n");
		return;
	}
	midStencilVal = powi(2, stencilBits - 1);
	glClearStencil(midStencilVal);

	bd3d->shadowsInitialised = TRUE;
}

//=============================================================^M
// UGAL : find random node for load balancing
//=============================================================^M
int find_ran_intm (int src, int dest) {
  int _dim   = gN;
  int _dim_size;
  int _ran_dest = 0;
  int debug = 0;
  
  if (debug) 
    cout << " INTM node for  src: " << src << " dest: " <<dest << endl;
  
  src = (int) (src / gC);
  dest = (int) (dest / gC);
  
  _ran_dest = RandomInt(gC - 1);
  if (debug) cout << " ............ _ran_dest : " << _ran_dest << endl;
  for (int d=0;d < _dim; d++) {
    
    _dim_size = powi(gK, d)*gC;
    if ((src % gK) ==  (dest % gK)) {
      _ran_dest += (src % gK) * _dim_size;
      if (debug) 
	cout << "    share same dimension : " << d << " int node : " << _ran_dest << " src ID : " << src % gK << endl;
    } else {
      // src and dest are in the same dimension "d" + 1
      // ==> thus generate a random destination within
      _ran_dest += RandomInt(gK - 1) * _dim_size;
      if (debug) 
	cout << "    different  dimension : " << d << " int node : " << _ran_dest << " _dim_size: " << _dim_size << endl;
    }
    src = (int) (src / gK);
    dest = (int) (dest / gK);
  }
  
  if (debug) cout << " intermediate destination NODE: " << _ran_dest << endl;
  return _ran_dest;
}

//=============================================================^M
// UGAL : calculate distance (hop cnt)  between src and destination
//=============================================================^M
int find_distance (int src, int dest) {
  int dist = 0;
  int _dim   = gN;
  int _dim_size;
  
  int src_tmp= (int) src / gC;
  int dest_tmp = (int) dest / gC;
  int src_id, dest_id;
  
  //  cout << " HOP CNT between  src: " << src << " dest: " << dest;
  for (int d=0;d < _dim; d++) {
    _dim_size = powi(gK, d )*gC;
    //if ((int)(src / _dim_size) !=  (int)(dest / _dim_size))
    //   dist++;
    src_id = src_tmp % gK;
    dest_id = dest_tmp % gK;
    if (src_id !=  dest_id)
      dist++;
    src_tmp = (int) (src_tmp / gK);
    dest_tmp = (int) (dest_tmp / gK);
  }
  
  //  cout << " : " << dist << endl;
  
  return dist;
}

int flatfly_outport_yx(int dest, int rID) {
  int dest_rID;
  int _dim   = gN;
  int output = -1, dID, sID;
  
  dest_rID = (int) (dest / gC);
  
  if(dest_rID==rID){
    return dest  - rID*gC;
  }

  for (int d=_dim-1;d >= 0; d--) {
    int power = powi(gK,d);
    dID = int(dest_rID / power);
    sID = int(rID / power);
    if ( dID != sID ) {
      output = gC + ((gK-1)*d) - 1;
      if (dID > sID) {
	output += dID;
      } else {
	output += dID + 1;
      }
      return output;
    }
    dest_rID = (int) (dest_rID %power);
    rID      = (int) (rID %power);
  }
  if (output == -1) {
    cout << " ERROR ---- FLATFLY_OUTPORT function : output not found yx" << endl;
    exit(-1);
  }
  return -1;
}

void FatTree::_ComputeSize(const Configuration& config) {

  _k = config.GetInt("k");
  _n = config.GetInt("n");

  gK = _k;
  gN = _n;

  _nodes = powi(_k, _n);

  //levels * routers_per_level
  _size = _n * powi(_k, _n - 1);

  //(channels per level = k*routers_per_level* up/down) * (levels-1)
  _channels = (2 * _k * powi(_k, _n - 1)) * (_n - 1);

}