import java.util.Random;



/* This class defines a locality based random generator of page references.

 * It generates a random page in the current locality with user defined probability.

 * It changes the locality after certain user defined average number of references.

 * The size of the working set can also be randomly specified with a user defined average.

 */

public class LocalReferenceGenerator extends ReferenceGenerator {

    private Random random;



    /* User defined parameters. */

    private float probLocality; // probability with which a page is chosen from current working set. 

    private float avgWorkingSetSize; // average size of working set.

    private float avgRefsPerLocality; // average number of references generated for the current working set.



    /* Current locality. */

    private int workingSet[];  // set of pages in current locality. 

    private int numRefs; // number of referenes within current locality.

    private int currentRef; // number of refereneces already generated in this locality.



    /* This method creates a new locality.

     * The working set is initialized to a random set of pages.

     * The other locality parameters are set according to user defined parameters.

     */

    private void makeNewLocality () {

	int numLocalPages;



	while ((numLocalPages = (int)(avgWorkingSetSize + 0.5*avgWorkingSetSize*random.nextGaussian())) <= 0);

	workingSet = new int[numLocalPages];

	for (int i=0; i<numLocalPages; i++) {

	    workingSet[i] = Math.abs(random.nextInt()%numPages);

	}



	while ((numRefs = (int)(avgRefsPerLocality + 0.5*avgRefsPerLocality*random.nextGaussian())) <= 0);

	currentRef = 0;

    }



    /* This constructor initializes the random number generator with a random seed.

     */

    public LocalReferenceGenerator (int numPages, float probLocality, float avgWorkingSetSize, float avgRefsPerLocality) {

	super(numPages);

	random = new Random();



	this.probLocality = probLocality;

	this.avgWorkingSetSize = avgWorkingSetSize;

	this.avgRefsPerLocality = avgRefsPerLocality;

    }







    /* This method initializes the seed as specified. 

     */

    public final void init (long seed) {

	random.setSeed(seed);

	makeNewLocality();

    }



    /* This method generates a random reference uniformly distributed between 0 and numPages.

     */ 

    public final int nextReference () {

	int page;

        

	if (probLocality*100000 > (random.nextInt()%100000)) {

	    // local reference. 

	    page = workingSet[Math.abs(random.nextInt()%workingSet.length)];	    

	}

	else {

	    // non local reference.

	    page = Math.abs(random.nextInt()%numPages);

	}

	

	currentRef++;

	if (currentRef == numRefs) {

	    makeNewLocality();

	}



	return page;

    }

}