/*
* Veletlen.java
* különböző eloszlású véletlenszámok generálója, determinisztikussá tehető
* by pts@fazekas.hu at Sat Apr 7 12:10:32 CEST 2001, mayor update at Sun Apr 22 13:00:49 CEST 2001
* további doksi: a README-ben és e file legkülső class-ának fejkommentjében
*
* Kincskereső Kisgömböc (C) Early May 2001 by eNTitánok (Rév Szilvia,
* Szabó Péter <pts@inf.bme.hu>, Szurdi Miklós, Weizengruber Attila).
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* 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 General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*/
package eNTitanok.util;
import eNTitanok.util.Sor;
import java.util.Random;
/**
* Egy olyan (pszeudo)véletlenszám-generátor, amely determinisztikussá
* tehető, azaz megmondható neki, hogy a következő néhány ,,véletlenszám''
* mi legyen. Ezeket a fix számokat az ún. determinizáló sorból veszi. Egyetlen
* generátorhoz egyetlen determinizáló sor tartozik, ami kezdetben üres.
*
* <P>A generált véletlenszámok 0 és N-1 közé eső int-ek, ahol N a
* kovetkezo() hívás paramétere.
* @see java.util.Random
*/
public class Veletlen {
/**
* A determinizáló sor.
*/
protected Sor kovetkezo;
/**
* Pontosan akkor `true', ha a generált számokat kizárólag a determinizáló
* sorból szabad venni.
*/
protected boolean csakDet;
/**
* Akkor váltódik ki, ha véletlenszámot kell generálni, `csakDet' igaz,
* továbbá `kovetkezo' üres.
*/
public static class CsakDetException extends Error {};
/**
* Akkor váltódik ki, ha a `kovetkezo'-ben szereplő szám nem esik a megadott
* határok közé.
*/
public static class DetHatarException extends Error {
public DetHatarException(String s) { super(s); }
public DetHatarException(int also, int x, int felso) { super(also+" <= "+x+" < "+felso+" kene"); }
public DetHatarException() { super(); }
};
/**
* A használt pszeudovéletlenszám-generátor.
*/
protected Random random;
/**
* Egy új véletlenszám-generátort hoz létre, amely a Java alapértelmezés
* szerinti véletlenszám-generátorát használja.
* @see java.util.Random
*/
public Veletlen() { this(new Random(), false); }
/**
* Egy új véletlenszám-generátort hoz létre, amely a megadott
* véletlenszám-generátort használja, és a megadott számú determinizáló
* sort kezel.
*/
public Veletlen(Random random, boolean csakDet) {
this.random=random==null?new Random():random;
this.csakDet=csakDet;
kovetkezo=new Sor();
}
/**
* Új értéket fűz a determinizáló sor végéhez.
*/
public void sorba(int ujertek) {
kovetkezo.vegehezFuz(new Integer(ujertek));
osszeg+=ujertek;
}
/**
* <U>aasdasd</U>-nál nagyobb-egyenlő, de <I>b</I>-nél kisebb véletlenszámot vesz
* ki `kovetkezo' elejéről. Kiváltja a megfelelő kivételeket. `null'-t ad
* vissza, ha `kovetkezo' üres volt.
*/
protected synchronized Integer csakDetet(int a, int b) {
// System.out.println(kovetkezo.length()+"L"); // DBG
Integer i=((Integer)kovetkezo.elsoTorol());
if (i==null) {
if (csakDet) throw new CsakDetException();
} else {
int iv=i.intValue();
if (iv<a || iv>=b) throw new DetHatarException(a,iv,b);
}
return i;
}
/**
* 0 és <I>n-1</I> közötti, egyenletes eloszlású, egész értékű
* ,,véletlenszámot'' generál (a határokat is beleértve),
* az értéket a megadott determinisztikus sorból véve, ha az nem üres.
* @param n ennél határozottan kisebb lesz a generált szám. Ne legyen
* nagyobb Integer.MAX_VALUE/2-nél!
*/
public int egyenletes(int n) {
Integer i=csakDetet(0, n);
if (i!=null) return i.intValue();
int r=random.nextInt();
return (r<0?n-r:r)%n;
}
/**
* <I>a</I> és <I>b-1</I> közötti, egyenletes eloszlású, egész értékű
* ,,véletlenszámot'' generál (a határokat is beleértve),
* az értéket a megadott determinisztikus sorból véve, ha az nem üres.
* @param n ennél határozottan kisebb lesz a generált szám. Ne legyen
* nagyobb Integer.MAX_VALUE/2-nél!
*/
public int egyenletes(int a, int b) {
Integer i=csakDetet(a, b);
if (i!=null) return i.intValue();
int r=random.nextInt();
return (r<0?(b-a)-r:r)%(b-a)+a;
}
/**
* Poisson-eloszlású (<I>lambda</I> paraméterrel), egész értékű
* ,,véletlenszámot'' generál. Az átlagos futásidő <I>lambda</I>-val
* arányos. Várható érték: <I>lambda</I>. Szórás: <I>sqrt(lambda)</I>.
* Csak felso-nél kisebb (nemnegatív) számot ad vissza.
* Minimum: 0. Maximum: amennyi belefér.
* <P>See Knuth, ACP, Section 3.4.1 Paragraph F.
*/
public int poisson(double lambda, int felso) {
if (lambda<=0.0) throw new ArithmeticException();
Integer i=csakDetet(0, Integer.MAX_VALUE);
if (i!=null) return i.intValue();
double hatar=Math.exp(-lambda);
double szorzat=1;
int n;
do {
for (n=-1;szorzat>hatar;n++) szorzat*=random.nextDouble();
} while (n<0 || n>=felso);
return n;
}
/**
* Csakúgy, mint kétparaméteres változata, de a felső határ
* <code>Integer.MAX_VALUE</code>.
*/
public int poisson(double lambda) {
return poisson(lambda, Integer.MAX_VALUE);
}
/**
* Exponenciális eloszlású (<I>lambda</I> paraméterrel) ,,véletlenszám''
* kerekített (<code>Math.round()</code>), egész értékét generálja.
* Csak felso-nél kisebb (nemnegatív) számot ad vissza.
* A futásidő O(1). Várható érték: <I>1/lambda</I>.
* Szórás: <I>1/lambda</I>. Minimum: 0. Maximum: amennyi belefér.
* @see java.lang.Math#round
*/
public int exponencialis(double lambda, int felso) {
if (lambda<=0.0 || felso<1) throw new ArithmeticException();
Integer i=csakDetet(0, felso);
if (i!=null) return i.intValue();
int n;
do {
n=Math.round((float)(-Math.log(random.nextDouble())/lambda));
} while (n<0 || n>=felso);
return n;
}
/**
* Csakúgy, mint kétparaméteres változata, de a felső határ
* <code>Integer.MAX_VALUE</code>.
*/
public int exponencialis(double lambda) {
return exponencialis(lambda, Integer.MAX_VALUE);
}
/**
* Normális (Gauss-)eloszlású (<I>m</I> várható értékű, <I>sigma</I>
* szórású) ,,véletlenszám''
* kerekített (<code>Math.round()</code>), egész értékét generálja.
* Csak `felso'-nél kisebb számot ad vissza.
* Csak `also'-nél nagyobb-egyenlo számot ad vissza.
* A futásidő JRE-függő.
* @see java.lang.Math#round
*/
public int normalis(double m, double sigma, int also, int felso) {
if (sigma<=0.0 || felso<1) throw new ArithmeticException();
Integer i=csakDetet(also, felso);
if (i!=null) return i.intValue();
int n;
do {
// n=Math.round((float)((random.nextGaussian()-m)/sigma));
n=Math.round((float)(random.nextGaussian()*sigma+m));
// System.err.println(n); // DEBUG
} while (n<also || n>=felso);
return n;
}
/**
* Csakúgy, mint háromparaméteres változata, de a felső határ
* <code>Integer.MAX_VALUE</code>.
*/
public int normalis(double m, double sigma) {
return normalis(m, sigma, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
/**
* Csakúgy, mint kétraméteres változata, de standard normális eloszlás
* szerint generál (<I>m=0, sigma=1</I>).
*/
public int normalis() {
return normalis(0, 1, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
/**
* @return a használt véletlenszám-generátor
*/
public Random getRandom() { return random; }
/**
* @return az utolsónak előírt veletlenszam (0, ha nincs)
*/
public int getUtolso() {
if (kovetkezo.isUres()) return 0;
return ((Integer)kovetkezo.utolso()).intValue();
}
/**
* Az eddig sorba() helyezettek összege.
*/
private int osszeg=0;
/**
* Új értéket fűz a determinizáló sor végéhez, de kivonja belőle az utolsó
* elemet.
*/
public void sorbaDelta(int ujertek) {
// System.err.println(kovetkezo.length()+" uj="+ujertek+" ut="+osszeg); // DBG
// System.err.println("EGESZ:"+kovetkezo.dump());
kovetkezo.vegehezFuz(new Integer(ujertek-osszeg));
osszeg=ujertek;
}
// Most a belső osztályok következnek. Azért nem külön .java file-ba raktam
// őket, mert kényelmesebb együtt kezelni és látni őket, erős köztük a
// kohézió (no meg encapsulation).
/**
* Az őt megvalósító objektumok képesek <code>int</code> típusú
* véletlenszámokat generálni. Az intervallum és az eloszlás tetszőleges.
*/
public static interface Generalo {
/**
* Generálja a következő véletlenszámot.
*/
public int general();
/**
* Új elemet helyez el a véletlensorba.
*/
public void sorba(int ujertek);
/**
* Új értéket fűz a determinizáló sor végéhez, de kivonja belőle az utolsó
* elemet.
*/
public void sorbaDelta(int ujertek);
}
/**
* <I>[a,b)</I>-n egyenletes eloszlású számokat generál.
*/
public static class Egyenletes extends Veletlen implements Generalo {
/**
* Alsó határ, belelértendő az intervallumba.
*/
protected int a;
/**
* Felső határ, nem tartozik az intervallumhoz.
*/
protected int b;
/**
* @see Veletlen#Veletlen
*/
public Egyenletes(Random random, boolean csakDet, int a, int b) {
super(random, csakDet);
this.a=a; this.b=b;
}
public Egyenletes(int a, int b) {
super();
this.a=a; this.b=b;
}
/**
* Átállítja a felső határt.
*/
public void setB(int b) { this.b=b; }
/**
* Generálja a következő véletlenszámot.
*/
public int general() {
return this.egyenletes(a, b);
}
} /// class Egyenletes
/**
* <I>[d,b+d)</I>-n <I>lambda</I> paraméterű, Poisson-eloszlású számoknál
* $d$-vel nagyobb számokat generál.
*/
public static class Poisson extends Veletlen implements Generalo {
/**
* Alsó határ, eltolás, belelértendő az intervallumba.
*/
protected int d;
/**
* Felső határ (eltolás nélkül), nem tartozik az intervallumhoz.
*/
protected int b;
/**
* Az eloszlás paramétere. (Egyben várható értéke és szórásnégyzete.)
*/
protected double lambda;
/**
* @see Veletlen#Veletlen
*/
public Poisson(Random random, boolean csakDet, int b, int d, double lambda) {
super(random, csakDet);
this.b=b; this.d=d; this.lambda=lambda;
}
public Poisson(int b, int d) {
super();
this.b=b; this.d=d; this.lambda=lambda;
}
/**
* Generálja a következő véletlenszámot.
*/
public int general() {
return d+this.poisson(lambda, b);
}
} /// class Poisson
/**
* <I>[d,b+d)</I>-n <I>lambda</I> paraméterű, exponencialis eloszlású
* számok egészre kerekítettjeinél
* $d$-vel nagyobb számokat generál.
*/
public static class Exponencialis extends Veletlen implements Generalo {
/**
* Alsó határ, eltolás, belelértendő az intervallumba.
*/
protected int d;
/**
* Felső határ (eltolás nélkül), nem tartozik az intervallumhoz.
*/
protected int b;
/**
* Az eloszlás paramétere. (Egyben várható értékének és szórásának is
* reciproka.)
*/
protected double lambda;
/**
* @see Veletlen#Veletlen
*/
public Exponencialis(Random random, boolean csakDet, int b, int d, double lambda) {
super(random, csakDet);
this.b=b; this.d=d; this.lambda=lambda;
}
public Exponencialis(int b, int d) {
super();
this.b=b; this.d=d; this.lambda=lambda;
}
/**
* Generálja a következő véletlenszámot.
*/
public int general() {
return d+this.exponencialis(lambda, b);
}
} /// class Exponencialis
/**
* <I>[a,b)</I>-n <I>m</I> várható értékű, <I>sigma</I> szórású,
* normális eloszlású számok egészre kerekítettjeinél
* $d$-vel nagyobb számokat generál.
*/
public static class Normalis extends Veletlen implements Generalo {
/**
* Alsó határ, belelértendő az intervallumba.
*/
protected int a;
/**
* Felső határ, nem tartozik az intervallumhoz.
*/
protected int b;
/**
* Az eloszlás egyik paramétere, egyben várható értéke.
*/
protected double m;
/**
* Az eloszlás másik paramétere, egyben szórása.
*/
protected double sigma;
/**
* @see Veletlen#Veletlen
*/
public Normalis(Random random, boolean csakDet, int a, int b, double m, double sigma) {
super(random, csakDet);
this.b=b; this.a=a; this.m=m; this.sigma=sigma;
}
public Normalis(int a, int b) {
super();
this.b=b; this.a=a; this.m=m; this.sigma=sigma;
}
/**
* Generálja a következő véletlenszámot.
*/
public int general() {
// System.err.println("DDD"); // DEBUG
int i=this.normalis(m, sigma, a, b);
// System.err.println("Gen."); // DEBUG
return i;
}
} /// class Normalis
/**
* A megadott diszkrét, véges eloszlású, nemnegatív értékű számokat
* generál.
*/
public static class Veges extends Veletlen implements Generalo {
/**
* `eloszlas' elemeinek összege. Bele kell, hogy férjen az int-be.
*/
protected int osszeg;
/**
* Az eloszlás. Nemnegatív gyakoriságértékek, melyek összege pozitív.
* Az `i' kimenetel valószínűsége: <I>eloszlas[i]/osszeg</I>.
*/
protected int[] eloszlas;
/**
* Segédfüggvény pl. `osszeg' kiszámítására.
*/
private synchronized void osszegez(int eloszlas[]) {
if (eloszlas==null || eloszlas.length==0) throw new ArithmeticException();
this.eloszlas=eloszlas;
osszeg=0;
for (int i=eloszlas.length-1;i>=0;i--) osszeg+=eloszlas[i];
if (osszeg<1) throw new ArithmeticException();
}
/**
* @see Veletlen#Veletlen
*/
public Veges(Random random, boolean csakDet, int eloszlas[]) {
super(random, csakDet);
this.eloszlas=eloszlas; osszegez(eloszlas);
}
public Veges(int eloszlas[]) {
super();
this.eloszlas=eloszlas; osszegez(eloszlas);
}
/**
* Generálja a következő véletlenszámot.
*/
public int general() {
Integer ii=this.csakDetet(0, eloszlas.length);
if (ii!=null) return ii.intValue();
int n=this.egyenletes(osszeg);
int i;
for (i=eloszlas.length-1;i>=0;i--)
if (0>(n-=eloszlas[i])) return i;
throw new ArithmeticException(); /* notreached */
}
} /// class Veges
} /// class Veletlen