package umontreal.iro.lecuyer.hups; 
import umontreal.iro.lecuyer.util.PrintfFormat;
import umontreal.iro.lecuyer.rng.*;
import cern.colt.list.*;

/* *
 * Title:        

 * Description:  

 * Copyright:    Copyright (c) 

 * Company:      

 * @author
 * @version 1.0
 */


/**
 * This class creates a point set based upon
 * a linear congruential sequence in the finite field
 *  
 * F2w[z]/P(z).
 * The recurrence is
 * 

 * 
 * 

 * qn(z) = zsqn-1(z) mod P(z)
 * 

 * where 
 * P(z)∈F2w[z] has degree r and
 * 
 * qn(z) = qn, 1zr-1 +  ...  + qn, r∈F2w[z]/P(z).
 * The parameter s is
 * called the stepping parameter of the recurrence.
 * The polynomial P(z) is not necessarily the characteristic polynomial
 * of this recurrence, but it can still be used to store the parameters of
 *  the recurrence.
 * In the implementation, it is stored in an object of the class
 *  {@link umontreal.iro.lecuyer.hups.F2wStructure F2wStructure}.  See the description
 * of this class for more details on how the polynomial
 * is stored.
 * 
 * 

 * Let 
 * x = (x(0),…, x(p-1))∈F2p be a p-bit vector.
 * Let us define the function 
 * φ(x) = ∑i=1p2-ix(i-1).
 * The point set in t dimensions produced by this class is
 * 

 * 
 * 

 * {(φ(y0), φ(y1),…, φ(yt-1) : (q0, 1,…,q0, r-1)∈F2rw}
 * 

 * where 
 * yn = (qn, 1,…,qn, r),
 *  
 * qn, i
 *  is the representation of qn, i under the polynomial basis of
 * 
 * F2w over
 *  
 * F2.
 * 
 */
public class F2wCycleBasedPolyLCG extends CycleBasedPointSetBase2  {

   private F2wStructure param;


   /**
    * Constructs a point set with 2rw points.  See the description of the class
    *  {@link umontreal.iro.lecuyer.hups.F2wStructure F2wStructure}
    *  for the meaning of the parameters.
    * 
    */
   public F2wCycleBasedPolyLCG (int w, int r, int modQ, int step, int nbcoeff,
                                int coeff[], int nocoeff[]) 
    /* *
     * Constructs and stores the set of cycles for an LCG with
     *    modulus n and multiplier a.
     *   If pgcd(a, n) = 1, this constructs a full-period LCG which has two
     *   cycles, one containing 0 and one, the LCG period.
     *
     * @param n required number of points and modulo of the LCG
     *
     *    @param a generator a of the LCG
     *
     *
     */
   {
      param = new F2wStructure (w, r, modQ, step, nbcoeff, coeff, nocoeff);
      numBits = param.numBits;
      normFactor = param.normFactor;
      EpsilonHalf = param.EpsilonHalf;
      fillCyclesPolyLCG ();
   }


   /**
    * Constructs a point set after reading its parameters from
    *    file filename; the parameters are located at line numbered no
    *    of filename. The available files are listed in the description of class
    * {@link umontreal.iro.lecuyer.hups.F2wStructure F2wStructure}.
    * 
    */
   public F2wCycleBasedPolyLCG (String filename, int no) 
   {
      param = new F2wStructure (filename, no);
      numBits = param.numBits;
      normFactor = param.normFactor;
      fillCyclesPolyLCG ();
   }



   public String toString ()
   {
       String s = "F2wCycleBasedPolyLCG:" + PrintfFormat.NEWLINE;
       return s + param.toString ();
   }

   private void fillCyclesPolyLCG ()
   {
      int n = 1 << param.getLog2N();
      int i;
      int mask1 = (1 << (31 - param.r * param.w)) - 1;
      int mask2 = ~mask1;
      RandomStream random = new MRG32k3a();
      IntArrayList c;             // Array used to store the current cycle.
      int currentState;           // The state currently visited.

      boolean stateVisited[] = new boolean[n];
      // Indicates which states have been visited so far.
      for (i = 0; i < n; i++)
         stateVisited[i] = false;
      int startState = 0;  // First state of the cycle currently considered.
      numPoints = 0;
      while (startState < n) {
         stateVisited[startState] = true;
         c = new IntArrayList ();
         param.state = startState << param.S;
         c.add (param.state);
         // c.add ((state & mask2) | (mask1 &
         // (random.nextInt(0,2147483647))));
         param.output = param.F2wPolyLCG ();
         // Warning: watch for overflow !!!
         while (param.state != (startState << param.S)) {
            stateVisited[param.state >> param.S] = true;
            // c.add ((param.state&mask2) | (mask1 &
            // (random.nextInt(0,2147483647))));
            c.add (param.state);
            param.output = param.F2wPolyLCG ();
         }
         addCycle (c);
         for (i = startState + 1; i < n; i++)
            if (stateVisited[i] == false)
               break;
         startState = i;
      }
   }
}