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

/* *
 * Title:        

 * Description:  

 * Copyright:    Copyright (c) 

 * Company:      

 * @author
 * @version 1.0
 */


/**
 * This class creates a point set based upon a linear feedback shift register
 *  sequence. The recurrence used to produce the point set is
 * 

 * 
 * 

 * mn = ∑i=1rbimn-i
 * 

 * where 
 * mn∈F2w, n >=  0
 *   and 
 * bi∈F2w.
 * There is a polynomial in 
 * F2w[z]
 *  associated with this recurrence called
 * the characteristic polynomial.  It is
 * 

 * 
 * 

 * P(z) = zr + ∑i=1rbizr-i.
 * 

 * In the implementation, this polynomial is stored in an object
 * F2wStructure.
 * 
 * 

 * 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), φ(ys),…, φ(ys(t-1)) : (v0,…,vr-1)∈F2rw}
 * 

 * where 
 * yn = trunch(vn,vn+1,…),
 * 
 * vn is the representation of mn under the polynomial basis of
 * 
 * F2w over
 *  
 * F2, and
 *  
 * h = w floor(31/w).
 * The parameter s is called the stepping parameter of the recurrence.
 * 
 */
public class F2wCycleBasedLFSR 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 F2wCycleBasedLFSR (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);
      init ();
   }


   /**
    * 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 F2wCycleBasedLFSR (String filename, int no) 
   {
      param = new F2wStructure (filename, no);
      init ();
   }



   private void init ()
   {
      param.initParamLFSR ();
      normFactor = param.normFactor;
      EpsilonHalf = param.EpsilonHalf;
      numBits = param.numBits;
      fillCyclesLFSR ();
   }

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

   private void fillCyclesLFSR ()
   {
      int n = 1 << param.getLog2N ();
      IntArrayList c;             // Array used to store the current cycle.
      int currentState;           // The state currently visited.
      int i;
      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.initF2wLFSR ();
         c.add (param.output);
         param.F2wLFSR ();
         // Warning: watch for overflow !!!
         while (param.state != startState) {
            stateVisited[param.state] = true;
            c.add (param.output);
            param.F2wLFSR ();
         }
         addCycle (c);
         for (i = startState + 1; i < n; i++)
            if (stateVisited[i] == false)
               break;
         startState = i;
      }
   }
}