X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/blobdiff_plain/ff6cb26262ba25fefdf1265628265a75d790ebd6..200986a368bbbbb5df459d43cbc7f5ef3d7678db:/contrib/psg/src/peersim/util/WeightedRandPerm.java

diff --git a/contrib/psg/src/peersim/util/WeightedRandPerm.java b/contrib/psg/src/peersim/util/WeightedRandPerm.java
new file mode 100644
index 0000000000..80c8928900
--- /dev/null
+++ b/contrib/psg/src/peersim/util/WeightedRandPerm.java
@@ -0,0 +1,194 @@
+/*
+ * Copyright (c) 2003-2005 The BISON Project
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License version 2 as
+ * published by the Free Software Foundation.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+ *
+ */
+		
+package peersim.util;
+
+import java.util.NoSuchElementException;
+import java.util.Random;
+
+/**
+* This class provides a weighted random permutation of indexes.
+* Useful for weighted random sampling without replacement.
+* The next sample is taken according to the weights given as a parameter
+* to {@link #reset(int)}.
+* The weights work as follows.
+* The first sample is drawn according to the probability distribution
+* defined by the (normalized) weights.
+* After this the remaining k-1 elements and the associated k-1
+* (re-normalized) weights
+* define a new probability distribution, according to which the 2nd element
+* is drawn, and so on.
+*/
+public class WeightedRandPerm implements IndexIterator {
+
+
+// ======================= private fields ============================
+// ===================================================================
+
+/** Holds the weights that are used to initialize the permutation */
+private final double[] w;
+
+/** Holds the sum of the weights until the given index, inclusive. */
+private final double[] wsum;
+
+private int[] buffer = null;
+
+/** Working array for calculating the permutation */ 
+private double[] weights = null;
+
+private int len = 0;
+
+private int pointer = 0;
+
+private double sum = 0.0;
+
+private final Random r;
+
+
+// ======================= initialization ============================
+// ===================================================================
+
+
+/** Set the source of randomness to use and the weights. You need to call
+* {@link #reset} to fully initialize the object.
+* @param r source of randomness
+* @param weights The array that holds the weights for the calculation of the
+* permutation. The length of the array will be an upper bound on the
+* parameter {@link #reset} accepts. If {@link #reset} is called with a
+* parameter less than the length of weights, the prefix of the same length
+* is used.
+* The vector elements must be positive, that is, zero is not accepted either.
+*/
+public WeightedRandPerm( Random r, double[] weights ) {
+
+	this.r=r;
+	w = weights.clone();
+	wsum = weights.clone();;
+	this.weights = new double[w.length];
+	buffer = new int[w.length];
+	
+	for(int i=0; i<w.length; ++i)
+	{
+		if( w[i] <= 0.0 ) throw new IllegalArgumentException(
+			"weights should be positive: w["+i+"]="+w[i]);
+	}
+	
+	for(int i=1; i<w.length; ++i) wsum[i]+=wsum[i-1];
+}
+
+
+// ======================= public methods ============================
+// ===================================================================
+
+
+/**
+* It initiates a random weighted permutation of the integeres from 0 to k-1.
+* It does not actually calculate the permutation.
+* The permutation can be read using method {@link #next}.
+* If the previous permutation was of the same length, it is more efficient.
+* The weights set at construction time work as follows.
+* The first sample is drawn according to the probability distribution
+* defined by the (normalized) weights.
+* After this the remaining k-1 elements and the associated k-1
+* (re-normalized) weights
+* define a new probability distribution, according to which the 2nd element
+* is drawn, and so on.
+* @param k the set is defined as 0,...,k-1
+*/
+public void reset(int k) {
+	
+	if( k<0 || k>w.length )
+		throw new IllegalArgumentException(
+			"k should be non-negative and <= "+w.length);
+	
+	pointer = k;
+	sum = wsum[k-1];
+	
+	if( k != len )
+	{
+		// we need to initialize weights and buffer
+		for(int i=0; i<k; ++i)
+		{
+			weights[i]=w[i];
+			buffer[i]=i;
+		}
+		len=k;
+	}
+}
+
+// -------------------------------------------------------------------
+
+/**
+* The first sample is drawn according to the probability distribution
+* defined by the (normalized) weights.
+* After this the remaining k-1 elements and the associated k-1
+* (re-normalized) weights
+* define a new probability distribution, according to which the 2nd element
+* is drawn, and so on.
+* @see #reset
+*/
+public int next() {
+	
+	if( pointer < 1 ) throw new NoSuchElementException();
+	
+	double d = sum*r.nextDouble();
+	int i = pointer;
+	double tmp = weights[i-1];
+	while( tmp < d && i>1 ) tmp += weights[--i-1];
+	
+	// now i-1 is the selected element, we shift it to next position
+	int a = buffer[i-1];
+	double b = weights[i-1];
+	buffer[i-1] = buffer[pointer-1];
+	weights[i-1] = weights[pointer-1];
+	buffer[pointer-1] = a;
+	weights[pointer-1] = b;
+	sum -= b;
+	
+	return buffer[--pointer];
+}
+
+// -------------------------------------------------------------------
+
+public boolean hasNext() { return pointer > 0; }
+
+// -------------------------------------------------------------------
+
+/*
+public static void main( String pars[] ) throws Exception {
+	
+
+	int k = pars.length;
+	double w[] = new double[k];
+	for(int i=0; i<k; ++i) w[i] = Double.parseDouble(pars[i]);
+	
+	WeightedRandPerm rp = new WeightedRandPerm(new Random(),w);
+	rp.reset(k);
+	for(int i=0; i<1000; ++i)
+	{
+		if(i%2==0) rp.reset(k);
+		if(i%2==1) rp.reset(k-1);
+		while(rp.hasNext()) System.out.print(rp.next()+" ");
+		System.out.println();
+	}
+	
+	System.out.println();
+}
+*/
+}
+