Author: vive
Date: 2009-02-11 13:53:49 +0000 (Wed, 11 Feb 2009)
New Revision: 25585
Added:
trunk/apps/simsalabim/AggregateCommand.java
trunk/apps/simsalabim/BasicDataSpace.java
trunk/apps/simsalabim/BuildTask.java
trunk/apps/simsalabim/CDataAggregator.java
trunk/apps/simsalabim/CircleKey.java
trunk/apps/simsalabim/Darknet.java
trunk/apps/simsalabim/DarknetNode.java
trunk/apps/simsalabim/DarknetRoute.java
trunk/apps/simsalabim/Data.java
trunk/apps/simsalabim/DataAggregator.java
trunk/apps/simsalabim/DataSpace.java
trunk/apps/simsalabim/EventLogger.java
trunk/apps/simsalabim/Feedback.java
trunk/apps/simsalabim/HBuildTask.java
trunk/apps/simsalabim/HDualStats.java
trunk/apps/simsalabim/HJoinTask.java
trunk/apps/simsalabim/HammingKey.java
trunk/apps/simsalabim/HistDataAggregator.java
trunk/apps/simsalabim/InfoCommand.java
trunk/apps/simsalabim/InfoObject.java
trunk/apps/simsalabim/JoinTask.java
trunk/apps/simsalabim/Key.java
trunk/apps/simsalabim/KeyFactory.java
trunk/apps/simsalabim/LimitedDataSpace.java
trunk/apps/simsalabim/MBuildTask.java
trunk/apps/simsalabim/MJoinTask.java
trunk/apps/simsalabim/Main.java
trunk/apps/simsalabim/MersenneTwister.java
trunk/apps/simsalabim/Node.java
trunk/apps/simsalabim/Person.java
trunk/apps/simsalabim/PopularityDataSpace.java
trunk/apps/simsalabim/PositionKey.java
trunk/apps/simsalabim/RandomEngine.java
trunk/apps/simsalabim/RunTask.java
trunk/apps/simsalabim/Script.java
trunk/apps/simsalabim/ScriptCommand.java
trunk/apps/simsalabim/ScriptCommandType.java
trunk/apps/simsalabim/ScriptException.java
trunk/apps/simsalabim/Settings.java
trunk/apps/simsalabim/SimulationException.java
trunk/apps/simsalabim/Simulator.java
trunk/apps/simsalabim/StringEventLogger.java
trunk/apps/simsalabim/TestSimulator.java
trunk/apps/simsalabim/TreeKey.java
trunk/apps/simsalabim/XorKey.java
trunk/apps/simsalabim/darknet/
trunk/apps/simsalabim/darknet/Darknet.java
trunk/apps/simsalabim/darknet/DarknetNode.java
trunk/apps/simsalabim/darknet/DarknetRoute.java
trunk/apps/simsalabim/darknet/Person.java
trunk/apps/simsalabim/rembre/
trunk/apps/simsalabim/rembre/Rembre.java
trunk/apps/simsalabim/rembre/RembreNode.java
trunk/apps/simsalabim/rembre/RembreRoute.java
trunk/apps/simsalabim/rembre/test.java
trunk/apps/simsalabim/utils/
trunk/apps/simsalabim/utils/Contains.java
trunk/apps/simsalabim/utils/DataStore.java
trunk/apps/simsalabim/utils/Heap.java
trunk/apps/simsalabim/utils/LRUHash.java
trunk/apps/simsalabim/utils/RandTester.java
trunk/apps/simsalabim/utils/RoutingTable.java
Log:
simsalabim: Freenet 0.7 simulator
Added: trunk/apps/simsalabim/AggregateCommand.java
===================================================================
--- trunk/apps/simsalabim/AggregateCommand.java (rev 0)
+++ trunk/apps/simsalabim/AggregateCommand.java 2009-02-11 13:53:49 UTC (rev
25585)
@@ -0,0 +1,58 @@
+package simsalabim;
+
+import java.util.StringTokenizer;
+
+/**
+ * AggregateCommand <aggname> <aggtype> ...
+ *
+ * <aggtype> one of "collector"
+ */
+public class AggregateCommand implements ScriptCommand {
+
+ public static class Type extends ScriptCommandType {
+ public Type() {
+ super("AggregateCommand");
+ }
+
+ public ScriptCommand newCommand(StringTokenizer params)
+ throws ScriptException {
+ return new AggregateCommand(params);
+ }
+ }
+
+ public DataAggregator da;
+
+ public AggregateCommand(StringTokenizer params) throws ScriptException {
+ // first param is name
+ String name = params.nextToken();
+ // next is type
+ String type = params.nextToken();
+
+ if (type.equals("collector")) {
+ if (params.hasMoreTokens()) {
+ da = new CDataAggregator(name,
params.nextToken());
+ } else {
+ da = new CDataAggregator(name);
+ }
+ }
+ if (type.equals("histogram")) {
+ double start = Double.parseDouble(params.nextToken());
+ double step = Double.parseDouble(params.nextToken());
+ double end = Double.parseDouble(params.nextToken());
+ if (params.hasMoreTokens()) {
+ da = new HistDataAggregator(name, start, step,
end, params
+ .nextToken());
+ } else {
+ da = new HistDataAggregator(name, start, step,
end);
+ }
+ } else
+ throw new ScriptException("No agg type as: " + type);
+ }
+
+ public void execute(Simulator god) {
+ god.aggregateNodeData(da);
+
+ da.complete();
+ }
+
+}
Added: trunk/apps/simsalabim/BasicDataSpace.java
===================================================================
--- trunk/apps/simsalabim/BasicDataSpace.java (rev 0)
+++ trunk/apps/simsalabim/BasicDataSpace.java 2009-02-11 13:53:49 UTC (rev
25585)
@@ -0,0 +1,51 @@
+package simsalabim;
+import java.util.*;
+
+public class BasicDataSpace<K extends Key> implements DataSpace<K> {
+
+
+ private HashMap<K, Data<K>> datamap = new HashMap<K, Data<K>>();
+ private Vector<Data<K>> datav = new Vector<Data<K>>();
+
+ private long minsize, sizerange;
+
+ public BasicDataSpace(long minsize, long maxsize) {
+ this.minsize = minsize;
+ this.sizerange = maxsize - minsize;
+ }
+
+
+ public Data<K> newData(Simulator god, K key) {
+ long size = minsize + (long) (god.random().nextDouble() * sizerange);
+ Data<K> d = new Data<K>(god, key, size);
+ datamap.put(key, d);
+ datav.add(d);
+ return d;
+ }
+
+
+ public Data<K> getData(K key) {
+ return datamap.get(key);
+ }
+
+ public Iterator<Data<K>> allData() {
+ return datav.iterator();
+ }
+
+ public int size() {
+ return datav.size();
+ }
+
+ public String info() {
+ return "BasicDataSpace size " + datav.size();
+ }
+
+
+ /**
+ * Currently uniform.
+ */
+ public K chooseKey(RandomEngine re) {
+ return datav.isEmpty() ? null : datav.get(re.choose(datav.size()) -
1).key();
+ }
+
+}
Added: trunk/apps/simsalabim/BuildTask.java
===================================================================
--- trunk/apps/simsalabim/BuildTask.java (rev 0)
+++ trunk/apps/simsalabim/BuildTask.java 2009-02-11 13:53:49 UTC (rev
25585)
@@ -0,0 +1,146 @@
+package simsalabim;
+
+/**
+ * Task which builds a simulates a living network.
+ */
+
+public class BuildTask extends RunTask {
+
+ private double joinRate;
+
+ private double leaveRate;
+
+ private double searchRate;
+
+ private double placeRate;
+
+ private long poolSize;
+
+ private long netSize = 1;
+
+ private long tsearches = 0;
+
+ private long ssearches = 0;
+
+ private long tplaces = 0;
+
+ private long splaces = 0;
+
+ private long tsearchcost = 0;
+
+ private long tplacecost = 0;
+
+ /**
+ * The rates are per node per clocktick. They should be low (the sum of
all
+ * the rates times poolSize should be less than << 1.
+ *
+ * @param runTill
+ * Run until this clockbeat
+ * @param searchRate
+ * The rate at which each active node iniates searches
+ * @param placeRate
+ * The rate at which each active node iniates placings.
+ * @param poolSize
+ * The size of the pool of available nodes.
+ * @param joinRate
+ * The rate at which each inactive node joins.
+ * @param leaveRate
+ * The rate at which each
+ */
+ public BuildTask(long runTill, double searchRate, double placeRate,
+ int poolSize, double joinRate, double leaveRate) {
+
+ super(runTill);
+
+ this.searchRate = searchRate;
+ this.placeRate = placeRate;
+ this.poolSize = poolSize;
+ this.joinRate = joinRate;
+ this.leaveRate = leaveRate;
+
+ }
+
+ /**
+ * String constructor for script. The values should be in the same
order as
+ * above.
+ */
+ public BuildTask(String[] s) throws ScriptException {
+ super(Long.parseLong(s[0]));
+
+ // System.err.println(Main.tabbed(s));
+
+ if (s.length < 6)
+ throw new ScriptException("BuildTask requires six
parameters, not "
+ + s.length);
+
+ this.searchRate = Double.parseDouble(s[1]);
+ this.placeRate = Double.parseDouble(s[2]);
+
+ this.poolSize = Long.parseLong(s[3]);
+ this.joinRate = Double.parseDouble(s[4]);
+ this.leaveRate = Double.parseDouble(s[5]);
+
+ // System.err.println(searchRate + " " + placeRate);
+
+ }
+
+ public void done(long time, EventLogger ev) {
+ ev.message(time, "BuildTask Complete. " + tsearches + "
searches ("
+ + ((float) ssearches) / tsearches + " succ, "
+ + ((double) tsearchcost) / tsearches + "
cost)." + tplaces
+ + " places (" + ((float) splaces) / tplaces + "
succ, "
+ + ((double) tplacecost) / tplaces + " cost).");
+ }
+
+ /**
+ * Calculates the time until a task.
+ */
+ public long timeTillTask(RandomEngine re) {
+ double rate = (poolSize - netSize) * joinRate + netSize
+ * (searchRate + placeRate + leaveRate);
+ // try { Thread.sleep(100); } catch (Exception e) {}
+ // System.err.println("rate: " + rate + " netsize: " + netSize);
+ // Exponentially distributed.
+ return Math.max((long) (Math.log(re.nextDouble()) / (rate *
-1)), 1);
+
+ }
+
+ /**
+ * Calculates the type of task to do after a call to time above.
+ */
+ public int taskType(RandomEngine re) {
+ double norm = (poolSize - netSize) * joinRate + netSize
+ * (searchRate + placeRate + leaveRate);
+
+ double val = re.nextDouble() * norm;
+
+ double joinP = (poolSize - netSize) * joinRate;
+ double searchP = netSize * searchRate;
+ double placeP = netSize * placeRate;
+
+ if (val <= joinP) {
+ netSize++;
+ return JOIN;
+ } else if (val <= searchP + joinP) {
+ return SEARCH;
+ } else if (val <= searchP + joinP + placeP) {
+ return PLACE;
+ } else {
+ netSize--;
+ return LEAVE;
+ }
+ }
+
+ public void feedback(int task, boolean success, double[] cost) {
+ if (task == SEARCH) {
+ tsearches++;
+ ssearches += success ? 1 : 0;
+ tsearchcost += cost[0];
+ } else if (task == PLACE) {
+ tplaces++;
+ splaces += success ? 1 : 0;
+ tplacecost += cost[0];
+ }
+ }
+
+}
Added: trunk/apps/simsalabim/CDataAggregator.java
===================================================================
--- trunk/apps/simsalabim/CDataAggregator.java (rev 0)
+++ trunk/apps/simsalabim/CDataAggregator.java 2009-02-11 13:53:49 UTC (rev
25585)
@@ -0,0 +1,91 @@
+package simsalabim;
+import java.util.Vector;
+import java.util.Enumeration;
+import java.io.PrintStream;
+import java.io.PrintWriter;
+import java.io.FileOutputStream;
+import java.io.IOException;
+
+public class CDataAggregator extends DataAggregator {
+
+ private Vector<Number> datac = new Vector<Number>();
+
+ private PrintStream out;
+ private String fname;
+
+ public CDataAggregator(String name) {
+ super(name);
+ out = System.out;
+ }
+
+ public CDataAggregator(String name, String fname) throws ScriptException {
+ super(name);
+ this.fname = fname;
+ }
+
+
+ public void next(long data) {
+ datac.add(new Long(data));
+ }
+
+ public void next(double data) {
+ datac.add(new Double(data));
+ }
+
+ public Long[] getLongData() {
+ Long[] r = new Long[datac.size()];
+ datac.copyInto(r);
+ return r;
+ }
+
+ public Double[] getDoubleData() {
+ Double[] r = new Double[datac.size()];
+ datac.copyInto(r);
+ return r;
+ }
+
+ public void complete() {
+ PrintStream ps;
+
+ if (fname != null) {
+ try {
+ ps = new PrintStream(new FileOutputStream(fname));
+ } catch (IOException e) {
+ throw new SimulationException("File error : " + e);
+ }
+ } else {
+ ps = this.out;
+ }
+
+ print(ps);
+
+ if (fname != null)
+ ps.close();
+ }
+
+ public void print(PrintStream ps) {
+ ps.println("#Created by Simsalabim. Data: " + name());
+ ps.println("#name: " + name());
+ ps.println("#type: matrix");
+ ps.println("#rows: " + datac.size());
+ ps.println("#columns: 1");
+ for (Enumeration e = datac.elements() ; e.hasMoreElements() ;) {
+ ps.println(e.nextElement().toString());
+ }
+ }
+
+ public void print(PrintWriter pw) {
+ pw.println("#Created by Simsalabim. Data: " + name());
+ pw.println("#name: " + name());
+ pw.println("#type: matrix");
+ pw.println("#rows: " + datac.size());
+ pw.println("#columns: 1");
+
+ for (Enumeration e = datac.elements() ; e.hasMoreElements() ;) {
+ pw.println(e.nextElement().toString());
+ }
+ }
+
+
+
+}
Added: trunk/apps/simsalabim/CircleKey.java
===================================================================
--- trunk/apps/simsalabim/CircleKey.java (rev 0)
+++ trunk/apps/simsalabim/CircleKey.java 2009-02-11 13:53:49 UTC (rev
25585)
@@ -0,0 +1,102 @@
+
+package simsalabim;
+/**
+ * A key which represents a position in a circular [0,1] keyspace
+ *
+ * @author ossa
+ *
+ */
+
+public class CircleKey extends PositionKey<CircleKey> {
+
+ public static KeyFactory<CircleKey> getFactory() {
+ return new KeyFactory<CircleKey>() {
+ public CircleKey newKey(long val) {
+ val &= 0x7FFFFFFFFFFFFFFFl; // makes positive
+ double dv = ((double) val) / ((double)
Long.MAX_VALUE);
+ return new CircleKey(dv);
+ }
+ };
+ }
+
+
+ double r;
+
+ public CircleKey(double r) {
+ this.r = r;
+ }
+
+ /**
+ * Returns a floating point value designating the nodes position in the
+ * keyspace.
+ */
+ public double ident() {
+ return r;
+ }
+
+
+ /**
+ * Key value expressed in it's natural form as a string.
+ */
+ public String stringVal() {
+ return "" + r;
+ }
+
+
+
+ /**
+ * It is a good idea that keys have these.
+ */
+ public int hashCode() {
+ long v = Double.doubleToLongBits(r);
+ return (int)(v ^ (v >>> 32));
+ }
+
+ public double dist(CircleKey pk) {
+ return dist(pk.r);
+ }
+
+ private double dist(double p) {
+ double posb = Math.max(r, p);
+ double poss = Math.min(r, p);
+ return Math.min(posb - poss, 1.0 - posb + poss);
+ }
+
+ public String toString() {
+ return "DNK" + stringVal();
+ }
+
+
+ public static double calcMinPoint(CircleKey[] ck, int size) {
+ double best = Double.MAX_VALUE;
+ for (int i = 0 ; i < ck.length ; i++) {
+ double t = ck[i].r;
+ double sum = 0.0;
+ for (int j = 0 ; j < ck.length ; j++) {
+ double tr = ck[j].r - t;
+ if (tr < 0) {
+ tr += size;
+ }
+ sum += tr;
+ }
+
+ double pos = sum / ck.length + t;
+ if (pos > size)
+ pos -= size;
+
+ double val = squareDist(pos, ck);
+ if (val < best)
+ best = val;
+ }
+ return best;
+ }
+
+ public static double squareDist(double x, CircleKey[] ck) {
+ double sum = 0.0;
+ for (int i = 0 ; i < 0 ; i++) {
+ sum += ck[i].dist(x);
+ }
+ return Math.sqrt(sum);
+ }
+
+}
Added: trunk/apps/simsalabim/Darknet.java
===================================================================
--- trunk/apps/simsalabim/Darknet.java (rev 0)
+++ trunk/apps/simsalabim/Darknet.java 2009-02-11 13:53:49 UTC (rev 25585)
@@ -0,0 +1,842 @@
+package simsalabim;
+import java.util.*;
+import java.io.*;
+/**
+ * Simulates a Darknet using the algorithm described in
+ *
+ */
+
+public class Darknet extends Simulator<DarknetNode, CircleKey> {
+
+ int INITIAL_SWITCHES;
+ int MAINT_SWITCHES;
+ int HTL;
+ int STORE_SIZE;
+ int CACHE_SIZE;
+ int N_BEST;
+ int RAND_STEPS;
+ int OPENNET_MIN_SUCCESS_BETWEEN_DROP_CONNS;
+ float OPENNET_RESET_PATH_FOLDING_PROB;
+ int OPENNET_DROP_MIN_AGE; // Has to be tuned for churn...
+ int OPENNET_MIN_TIME_BEFORE_OFFERS;
+ int OPENNET_MINPEERS;
+ int OPENNET_MAXPEERS;
+ int MAXPEERS; // Max num of online peers for a
node (a person may know more than this)
+ int RANDOM_GROWTH_MODEL; // How to add nodes, growing
from the underlying social network
+ int VARDIST_RESOLUTION; // Resolution of computing
distribution distance for locations
+ float OPENNET_NODES_SWAP_PROB; // Should nodes in opennet eval
swaps?
+ float HYBRID_NODES_SWAP_PROB; // Should hybrid nodes eval
swaps?
+ float LEAVE_PERM_PROB; // Whether to leave permanent or
stay dormant
+
+ float DARKLINKS_ONLY_PROB;
+ float RECACHE_PROB;
+ float RELINK_PROB;
+
+ boolean first_split = false; // Did the network undergo a
first split? Debugging switching.
+
+ HashMap<Integer, Person> people;
+ TreeSet<Person> ts = new TreeSet<Person>();
+ HashMap<Person, DarknetNode> dormant = new HashMap<Person,
DarknetNode>();
+ // For several graph partitions
+ int person_id_offset = 0;
+ Person[] people1;
+ Person[] people2;
+
+ int size;
+ int n_darknet_total;
+ int n_opennet_total;
+ int n_opennet_active;
+ int n_darknet_active;
+
+ /*
+ * Use (load) single graph:
+ *
+ * Use dual graphs (as the Kleinberg model):
+ *
+ * Darknet dual size1 outdeg1 size2 outdeg2 cut
+ * where
+ * size = #nodes
+ * outdeg = #edges (undirected) added to each node in each network
+ * cut = #edges between networks
+ */
+ public Darknet(RandomEngine re, DataSpace ds, Settings st, EventLogger
el,
+ String args) {
+ super(re, ds, st, el);
+ setParameters();
+
+ StringTokenizer stoke = new StringTokenizer(args,", ");
+
+ if (stoke.countTokens() < 1) {
+ throw new RuntimeException("No parameters given.");
+ }
+ people = new HashMap<Integer,Person>();
+
+ String name = stoke.nextToken();
+ if (name.equals("dual")) {
+ if (stoke.countTokens() != 6)
+ throw new RuntimeException("dual graphs: not
enough arguments");
+
+ int size1 = Integer.parseInt(stoke.nextToken());
+ int degree1 = Integer.parseInt(stoke.nextToken());
+ int size2 = Integer.parseInt(stoke.nextToken());
+ int degree2 = Integer.parseInt(stoke.nextToken());
+ Integer startId = Integer.parseInt(stoke.nextToken());
+ int cut = Integer.parseInt(stoke.nextToken());
+ people1 = swgraph(size1, 0, degree1);
+ people2 = swgraph(size2, size1, degree2);
+ joinNetworks(cut);
+ }
+ else if (name.equals("kleinberg")) {
+ if (stoke.countTokens() != 2)
+ throw new RuntimeException("kleinberg: requires
size and degree");
+ people1 = swgraph(Integer.parseInt(stoke.nextToken()),
0, Integer.parseInt(stoke.nextToken()));
+ for(int i=0; i<people1.length; i++) {
+ people.put(new Integer(i), people1[i]);
+ }
+ }
+ else if (name.equals("load")) {
+ try {
+ readGraph(new File(stoke.nextToken()),
Integer.parseInt(stoke.nextToken()));
+ } catch (IOException e) {
+ throw new RuntimeException("Error reading
darknet graph: " + e);
+ }
+ }
+ else if (name.equals("loaddual")) {
+ if (stoke.countTokens() != 5)
+ throw new RuntimeException("loaddual requires:
graph1 startid1 graph2 startid2 cut");
+ try {
+ people1 = readGraph2(false, new
File(stoke.nextToken()), Integer.parseInt(stoke.nextToken()));
+ people2 = readGraph2(false, new
File(stoke.nextToken()), Integer.parseInt(stoke.nextToken()));
+ } catch (IOException e) {
+ throw new RuntimeException("Error reading dual
darknet graphs: " + e);
+ }
+
+ int cut = Integer.parseInt(stoke.nextToken());
+ joinNetworks(cut);
+ } else {
+ throw new RuntimeException("Darknet: options
load,kleinberg,dual");
+ }
+
+ if (RANDOM_GROWTH_MODEL == 1) // All nodes become available
+ for (Person p: people.values())
+ ts.add(p);
+
+ chooseTypes(people); // Pick opennet/darknet/hybrid
nodes
+ System.err.println("Read graph of size " + people.size());
+ System.err.println("Average degree: " + avgDeg());
+
+ logCreation();
+ }
+
+ public float avgDeg() {
+ int n = 0;
+ for (Person p: people.values()) {
+ n += p.degree();
+ }
+
+ return ((float) n / people.size());
+ }
+
+ /**
+ * How many nodes initiate maintenance (swapping) requests
+ */
+ public int maintSize() {
+ return n_darknet_active;
+ }
+
+ /*
+ * Partition the positions of two disjoint networks into [0,0.5] and
[0.5,1]
+ * Ignoring P({pick 0.5}) > 0
+ */
+
+ public void dualSplitPositions() {
+
+ if (!first_split) {
+ first_split = true;
+ System.err.println("WARNING, modifying node locations!");
+ for (Person p: people1) {
+ p.getNode().pos.r = 0.5*re.nextDouble();
+ }
+
+ for (Person p: people2) {
+ p.getNode().pos.r = 0.5 + 0.5*re.nextDouble();
+ }
+ }
+ }
+
+ /*
+ * @return: array of the random cut between networks as (src,dst) pairs
+ */
+ public Person[][] joinNetworks(int cutsize) {
+ for (int i=0; i<people1.length; i++) {
+ Integer id1 = new Integer(i);
+ people.put(new Integer(people1[i].id) ,people1[i]);
+ people1[i].setNetwork(1);
+ }
+ for (int i=0; i<people2.length; i++) {
+ people.put(new Integer(people2[i].id), people2[i]);
+ people2[i].setNetwork(2);
+ }
+
+ Person [][] cut = new Person [cutsize][2];
+
+ for (int i=0; i<cutsize; i++) {
+ boolean found = false;
+ while (!found) {
+ Person src = people1[re.nextInt(people1.length)];
+ Person dst = people2[re.nextInt(people2.length)];
+
+ if (!src.linksTo(dst) && !dst.linksTo(src)) {
+ src.addOut(dst);
+ dst.addOut(src);
+ found = true;
+ cut[i][0] = src;
+ cut[i][1] = dst;
+ }
+ }
+ }
+ return cut;
+ }
+
+ /*
+ * Generate a Kleinberg small-world of size, with a fixed number of
links added to
+ * each node (resulting in a random number of links for nodes)
+ */
+ public Person[] swgraph(int size, int offset, int outdeg) {
+
+ Person [] people = new Person[size];
+ for (int i=0; i<size; i++) {
+ people[i] = new Person(i+offset);
+ }
+
+ for (int i=0; i<size; i++) {
+ Person source = people[i];
+
+ for (int j=0; j<outdeg; j++) {
+ boolean found = false;
+ while (!found) {
+ double u = re.nextDouble();
+ int dist = (int)
Math.floor(Math.exp(u*Math.log(size/2)));
+ int dest = i + ((re.nextDouble() < 0.5) ? -dist :
dist);
+ if (dest < 0) dest = dest + size;
+ if (dest > size-1) dest = dest - size;
+ Person target = people[dest];
+
+ if (!source.linksTo(target) &&
!target.linksTo(source)) {
+ source.addOut(target);
+ target.addOut(source);
+ found = true;
+ }
+ }
+ }
+ }
+ System.err.println("Created ideal Kleinberg graph (w.o. local
connections) of size " + size);
+ return people;
+ }
+
+ protected void setParameters() {
+ // Settings
+ INITIAL_SWITCHES = st.getInt("dnInitialSwitches",100);
+ MAINT_SWITCHES = st.getInt("dnMaintSwitches",100);
+ RAND_STEPS = st.getInt("dnRandSteps",10);
+ HTL = st.getInt("dnHTL",20);
+ STORE_SIZE = st.getInt("dnStoreSize",50);
+ CACHE_SIZE = st.getInt("dnCacheSize",STORE_SIZE);
// Default: same size as store
+ VARDIST_RESOLUTION = st.getInt("varDistResolution", 100);
+ N_BEST = st.getInt("dnNBest",3);
+ MAXPEERS = st.getInt("dnMaxPeers",50);
+ RECACHE_PROB = (float) st.getDouble("dnRecacheProb",0.0);
// Whether to recache data after each successful request
+ RELINK_PROB = (float) st.getDouble("dnRelinkProb",1.0);
+ DARKLINKS_ONLY_PROB = (float)
st.getDouble("dnLinksOnlyProb",1.0);
+ if ((DARKLINKS_ONLY_PROB>1) || (DARKLINKS_ONLY_PROB<0))
+ throw new Error("DARKLINKS_ONLY_PROB (dnLinksOnlyProb) needs
to be in [0,1]");
+
+ OPENNET_NODES_SWAP_PROB = (float) st.getDouble("onSwapProb",
0.0);
+ if (!(OPENNET_NODES_SWAP_PROB==0 ||
(OPENNET_NODES_SWAP_PROB==1)))
+ throw new Error("OPENNET_NODES_SWAP_PROB (onSwapProb) needs
to be 0 or 1");
+
+ HYBRID_NODES_SWAP_PROB = (float) st.getDouble("hnSwapProb",
0.0);
+ if (!(HYBRID_NODES_SWAP_PROB==0 || HYBRID_NODES_SWAP_PROB==1))
+ throw new Error("HYBRID_NODES_SWAP_PROB (hnSwapProb) needs
to be in 0 or 1");
+
+ RANDOM_GROWTH_MODEL = (int) st.getInt("randomGrowth",0);
// Default growth is F2F, else persons with nodes are picked at random
+ if (!(RANDOM_GROWTH_MODEL==0 || RANDOM_GROWTH_MODEL==1))
+
+ LEAVE_PERM_PROB = (float) st.getDouble("dnLeavePermProb",0.1);
+ if ((LEAVE_PERM_PROB>1.0) || (LEAVE_PERM_PROB<0.0))
+ throw new Error("LEAVE_PERM_PROB (dnLeavePermProb) needs to
be in [0,1]");
+
+ // As in the freenet implementation
+ OPENNET_MIN_SUCCESS_BETWEEN_DROP_CONNS =
st.getInt("onMinSuccess",10); // Min successful requests between folding
(Freenet 0.7)
+ OPENNET_RESET_PATH_FOLDING_PROB = (float)
st.getDouble("onResetFoldProb",0.05); // Probability to steal folding reference
(Freenet 0.7)
+ OPENNET_DROP_MIN_AGE = st.getInt("onDropMinAge",30);
// FIXME implement: Min age for node before we can drop it (Freenet 0.7)
+ OPENNET_MIN_TIME_BEFORE_OFFERS =
st.getInt("onMinTimeOffers",30); // FIXME implement: Min age between we give
offers (Freenet 0.7)
+ OPENNET_MINPEERS = st.getInt("onMinPeers",10);
+ OPENNET_MAXPEERS = st.getInt("onMaxPeers",20);
+
+ if (OPENNET_RESET_PATH_FOLDING_PROB > 1 ||
OPENNET_RESET_PATH_FOLDING_PROB < 0)
+ throw new Error("OPENNET_RESET_PATH_FOLDING_PROB
(onResetFoldProb) needs to be in [0,1]");
+ }
+
+ protected void logCreation() {
+ ev.message(time(), "Created Darknet Simulator. SWITCHES: " +
MAINT_SWITCHES +
+ " RANDSTEPS: " + RAND_STEPS + " HTL: "
+ + HTL + " STORESIZE: " + STORE_SIZE + ".");
+ }
+
+ public DarknetNode newNode(int num) {
+
+ Person p;
+
+ if (RANDOM_GROWTH_MODEL==0)
+ p = growNetwork();
+ else
+ p = growNetworkRandom();
+
+ if (p == null)
+ throw new SimulationException("Poplulation smaller than
network wants to be.");
+
+ DarknetNode n;
+ if (!dormant.containsKey(p)) {
+ double r = re.nextDouble();
+ n = new DarknetNode(this, num, p, new CircleKey(r));
+ } else {
+ n = dormant.get(p); //
Zombie
+ dormant.remove(p);
+ }
+
+ return n;
+
+ }
+
+ public CircleKey newKey() {
+ return new CircleKey(re.nextDouble());
+ }
+
+ // Not depending on oldNode (linking to a living node) at the moment...
+ public boolean join(DarknetNode newNode, DarknetNode oldNode, Feedback
fb) {
+ int cost = newNode.join();
+
+ if (newNode.isOpennet()) {
+ opennetBootstrap(newNode, OPENNET_MINPEERS);
+ n_opennet_active++;
+ }
+ else if(newNode.isDarknet()) {
+ n_darknet_active++;
+ } else {
+ throw new RuntimeException("join: Node of unknown type
joins network");
+ }
+
+ size++; // After bootstrap
+ fb.feedback(RunTask.JOIN, true, new double[] {cost});
+ return true;
+ }
+
+ /*
+ * Simulate a seednodes that give connections uniformly at random to a
new opennet peer
+ */
+ public int opennetBootstrap(DarknetNode newNode, int npeers) {
+
+ int found = 0;
+ for (int i = 0; i < npeers && newNode.needsOpennet(); i++) {
+ DarknetNode prospect = chooseOpennetNode();
+ if (prospect == null) {
+ if (i==0) System.err.println("Warning: an opennet node
not able to bootstrap at all, " + n_opennet_active + " active opennet nodes");
+ break; // Unavailable
+ }
+
+ if (prospect.needsOpennet()) {
+ newNode.reLink(prospect);
+ found++;
+ }
+
+ }
+
+ if (found == 0 && newNode.needsOpennet())
+ System.err.println("Warning: an opennet node, darkdegree
" + newNode.neighbors.size() + " not able to connect");
+ return found;
+ }
+
+ public void maintenance(Feedback fb) {
+
+ int succ = 0;
+ int crossing = 0;
+ int crossing_succ = 0;
+ CircleKey pos = null;
+
+ for (int i = 0; i < MAINT_SWITCHES ; i++) {
+ DarknetNode n = (DarknetNode) chooseNode();
+ DarknetNode target = null;
+
+ if (n != null) {
+ pos = n.pos;
+
+ if (n.isDarknet())
+ target = n.makeSwitch();
+ else if (n.isOpennet() && OPENNET_NODES_SWAP_PROB==1)
+ target = n.makeSwitch();
+ }
+
+ if (n!=null && target!=null) {
+ if (pos == target.pos)
+ succ++;
+
+ if (n.person().network() !=
target.person().network()) {
+ crossing++;
+ if (pos == target.pos)
+ crossing_succ++;
+ }
+ }
+
+ }
+ fb.feedback(RunTask.MAINTENANCE, true, new double[]
{MAINT_SWITCHES, succ, crossing, crossing_succ});
+ }
+
+
+ /**
+ * Some statistics about network partitions
+ */
+ public void dualstats(Feedback fb) {
+
+ if (people1==null || people2==null)
+ throw new SimulationException("Attempting dualstats() without
a partition");
+
+ double first,second,complete;
+ first = second = 0;
+
+ for (int i=0; i<people1.length; i++) {
+ if (people1[i].isInNetwork())
+ first++;
+ }
+ for (int i=0; i<people2.length; i++) {
+ if (people2[i].isInNetwork())
+ second++;
+ }
+
+ fb.feedback(RunTask.DUALSTATS, true, new double[]
{first,second,varDist(people1),varDist(people2),varDist(),varDist(people1,people2)});
+ // Total variation distance between uniform and sampling
+ // return new double[]
{first,second,varDist(people1),varDist(people2),varDist(people1,people2))};
+
+ }
+
+ /**
+ * Variation distance (for whole network)
+ */
+ public double varDist() {
+ int[] quant = new int[VARDIST_RESOLUTION];
+ int n = 0;
+
+ for (Person p: people.values()) {
+ if (p.isInNetwork()) {
+ n++;
+ int i = (int)
(p.getNode().pos.ident()*VARDIST_RESOLUTION);
+ quant[i]++;
+ }
+ }
+
+ double vd = 0;
+ for (int i=0; i<VARDIST_RESOLUTION; i++) {
+ double delta = Math.abs(((double)quant[i]/n) -
((double)1/VARDIST_RESOLUTION));
+ vd = vd + delta;
+ }
+
+ vd = vd/2;
+ if ((vd<0) || (vd>1))
+ throw new SimulationException("varDist(): error
computing total variation distance for whole population");
+
+ return vd;
+ }
+
+ /**
+ * Variation distance (for distribution distance vs uniform
distribution)
+ * Counting positions currently in network
+ */
+
+ public double varDist(Person[] population) {
+ int[] quant = new int[VARDIST_RESOLUTION];
+ int n = 0;
+
+ for (Person p: population) {
+ if (p.isInNetwork()) {
+ n++;
+ int i = (int) (p.getNode().pos.ident()*VARDIST_RESOLUTION);
+ quant[i]++;
+ }
+ }
+
+ double vd = 0;
+ for (int i=0; i<VARDIST_RESOLUTION; i++) {
+ double delta = Math.abs(((double)quant[i]/n) -
((double)1/VARDIST_RESOLUTION));
+ vd = vd + delta;
+ }
+
+ vd = vd/2;
+ if ((vd < 0) || (vd>1))
+ throw new SimulationException("varDist(): error computing total
variation distance");
+
+ return vd;
+ }
+
+ /**
+ * Variation distance where one of the networks is seen as the reference
+ */
+
+ public double varDist(Person[] first, Person[] second) {
+ int[] quant1 = new int[VARDIST_RESOLUTION];
+ int[] quant2 = new int[VARDIST_RESOLUTION];
+ int n1=0,n2=0;
+
+ for (Person p: first) {
+ if (p.isInNetwork()) {
+ n1++;
+ int i = (int)
(p.getNode().pos.ident()*VARDIST_RESOLUTION);
+ quant1[i]++;
+ }
+ }
+
+ for (Person p: second) {
+ if (p.isInNetwork()) {
+ n2++;
+ int i = (int)
(p.getNode().pos.ident()*VARDIST_RESOLUTION);
+ quant2[i]++;
+ }
+ }
+
+ double vd = 0;
+ for (int i=0; i<VARDIST_RESOLUTION; i++) {
+ double delta = Math.abs(((double)quant1[i]/n1) -
((double)quant2[i]/n2));
+ vd = vd + delta;
+ }
+
+ vd = vd/2;
+ if ((vd < 0) || (vd>1))
+ throw new SimulationException("varDist(.,.): error
computing mutual variation distance");
+
+ return vd;
+ }
+
+
+ /*
+ * Some statistics about available keys
+ */
+
+ public int[] keystats() {
+ int activeKeys=0,sleepingKeys=0;
+
+ for (Node n: nodes)
+ activeKeys = activeKeys + n.nKeys();
+
+ for (Node n: dormant.values())
+ sleepingKeys = sleepingKeys + n.nKeys();
+
+ return new int[] {activeKeys, sleepingKeys};
+ }
+
+ public Data search(CircleKey k, DarknetNode n, boolean ghost, Feedback
fb) {
+ DarknetRoute route = n.findRoute(k, null);
+ Data d = route.findData(k);
+
+ if (d != null) {
+ if (RECACHE_PROB>0 && re.nextFloat()<RECACHE_PROB)
+ route.storeData(d, false, true);
+ else
+ route.storeData(d, false, false);
+ }
+
+ // Freenet 0.7: path folding happens only on successful requests
+ if (d != null)
+ route.reLink(re, RELINK_PROB,
OPENNET_RESET_PATH_FOLDING_PROB);
+
+ int srcNet = n.person().network(), origNet =
ds.getData(k).sourceNetwork();
+
+ fb.feedback(RunTask.SEARCH, d != null, new double[]
{route.size(), d != null ? route.size() : 0, srcNet, origNet});
+ return d;
+ }
+
+ public boolean place(Data<CircleKey> d, DarknetNode n, Feedback fb) {
+ // Remember source
+ d.sourceNetwork(n.person().network());
+ DarknetRoute route = n.findRoute(d.key(), null);
+
+ route.storeData(d, true, true);
+ // Freenet 0.7: Inserts not leading to path folding
+ // route.reLink(re, RELINK_PROB);
+
+ fb.feedback(RunTask.PLACE, true, new double[] {route.size()});
+ return true;
+ }
+
+ public void leave(DarknetNode dn, Feedback fb, boolean permanent) {
+ size--;
+ if (dn.isOpennet()) {
+ n_opennet_active--;
+ }
+ else if (dn.isDarknet()) {
+ n_darknet_active--;
+ }
+ else
+ throw new RuntimeException("leave(): unknown type");
+
+ // Put node among zombies
+ if (!permanent) {
+ if (dormant.containsKey(dn.person()) ||
dormant.containsValue(dn))
+ throw new SimulationException("Person already with
dormant node, or node already dormant");
+ dormant.put(dn.person(), dn);
+ }
+
+ dn.leave(permanent);
+ shrinkNetwork(dn.person());
+ fb.feedback(RunTask.LEAVE, true, new double[] {1});
+ }
+
+ /**
+ * Does the node leave permanently, or just become dormant?
+ */
+ public boolean leavePermanent(DarknetNode n) {
+ if (LEAVE_PERM_PROB == 1)
+ return true;
+ if (LEAVE_PERM_PROB == 0)
+ return false;
+ if (re.nextDouble() < LEAVE_PERM_PROB)
+ return true;
+ else
+ return false;
+ }
+
+ /*
+ * Pick an opennet node, uniformly at random
+ */
+ public DarknetNode chooseOpennetNode() {
+ if (n_opennet_active == 0)
+ return null;
+ int j = re.nextInt(n_opennet_active);
+ int k = -1;
+
+ for (int i=0; i < size; i++) {
+ if (nodes.get(i).isOpennet())
+ k++;
+
+ if (k==j)
+ return nodes.get(i);
+ }
+
+ throw new SimulationException("chooseOpennetNode(): sampling
error");
+ }
+
+
+ protected void readGraph(File s, int startId) throws IOException {
+ BufferedReader br = new BufferedReader(new FileReader(s));
+ String line;
+ System.err.println("Parsing...");
+ int i = 0;
+ while ((line = br.readLine()) != null) {
+ if (++i % 100000 == 0)
+ System.err.println("Line: " + i);
+ StringTokenizer st = new StringTokenizer(line, "\t");
+ if (st.nextToken().equals("E")) {
+ Integer id1 = new Integer(st.nextToken());
+ Integer id2 = new Integer(st.nextToken());
+
+ Person n1 = people.get(id1);
+ if (n1 == null) {
+ n1 = new Person(id1);
+ people.put(id1, n1);
+ }
+ Person n2 = people.get(id2);
+ if (n2 == null) {
+ n2 = new Person(id2);
+ people.put(id2, n2);
+ }
+
+ // There is duplicate edge protection, and we
are only
+ // interested
+ // in undirected graphs
+ n1.addOut(n2);
+ n2.addOut(n1);
+ }
+ }
+
+ System.err.println("Read " + people.size() + " people into the
network.");
+
+ Person p = people.get(startId);
+ if (p == null)
+ throw new RuntimeException("The starting identity did
not exist");
+ ts.add(p);
+ }
+
+
+ /**
+ * Reads a graph file containing the social network data.
+ * @direct: if true, then reading directly into final set of people
+ * @startId: the id in the graph that a growth process starts with
+ */
+ protected Person[] readGraph2(boolean direct, File s, int startId)
throws IOException {
+ BufferedReader br = new BufferedReader(new FileReader(s));
+ String line;
+ HashMap <Integer,Person> temp = new HashMap<Integer, Person>();
+ HashMap <Integer,Integer> idmap = new HashMap<Integer,
Integer>();
+ Integer start = null;
+
+ System.err.println("Parsing...");
+ int i = 0;
+ while ((line = br.readLine()) != null) {
+ if (++i % 100000 == 0)
+ System.err.println("Line: " + i);
+ StringTokenizer st = new StringTokenizer(line, "\t");
+ if (st.nextToken().equals("E")) {
+ Integer id1raw = new Integer(st.nextToken());
+ Integer id2raw = new Integer(st.nextToken());
+
+ // Fix representation
+ Integer id1 = idmap.get(id1raw);
+ Integer id2 = idmap.get(id2raw);
+ if (id1 == null) {
+ id1 = new Integer(person_id_offset++);
+ idmap.put(id1raw, id1);
+ }
+ if (id2 == null) {
+ id2 = new Integer(person_id_offset++);
+ idmap.put(id2raw, id2);
+ }
+
+ // Node to start from
+ if ((start==null) &&
(startId==id1raw.intValue()))
+ start = id1;
+ if ((start==null) &&
(startId==id2raw.intValue()))
+ start = id2;
+
+ Person n1 = direct ? people.get(id1) :
temp.get(id1);
+ if (n1 == null) {
+ n1 = new Person(id1);
+ if (direct)
+ people.put(id1, n1);
+ else
+ temp.put(id1, n1);
+ }
+ Person n2 = direct ? people.get(id2) :
temp.get(id2);
+ if (n2 == null) {
+ n2 = new Person(id2);
+ if (direct)
+ people.put(id2, n2);
+ else
+ temp.put(id2, n2);
+ }
+
+ // There is duplicate edge protection, and we
are only
+ // interested in undirected graphs
+ n1.addOut(n2);
+ n2.addOut(n1);
+ }
+ }
+
+ System.err.println("Read " + (direct ? people.size() :
temp.size()) + " people into the network.");
+
+ if (start == null)
+ throw new RuntimeException("The starting identity did
not exist");
+ Person p = direct ? people.get(start) : temp.get(start);
+ ts.add(p);
+
+ if (!direct) {
+ Person[] target = new Person[temp.size()];
+ int j = 0;
+ for (Person q: temp.values())
+ target[j++] = q;
+
+ return target;
+ }
+
+ return null;
+ }
+
+ /**
+ *
+ * Distribute opennet/darknode persons over the network
+ */
+
+ private void chooseTypes(HashMap<Integer, Person> people) {
+ System.err.println("Picking darknet nodes with p = " +
DARKLINKS_ONLY_PROB);
+
+ for (Person p : people.values()) {
+ if (re.nextDouble() < DARKLINKS_ONLY_PROB) {
+ p.setDarknet();
+ n_darknet_total++;
+ } else {
+ p.setOpennet();
+ n_opennet_total++;
+ }
+ }
+
+ System.err.println("Picked " + n_darknet_total + " darknet
persons, and " + n_opennet_total + " opennet persons (uniformly random)");
+
+ }
+
+
+ /**
+ * Chooses the next person to join the network.
+ */
+ protected Person growNetwork() {
+ // System.err.println("TS SIZE: " + ts.size());
+ if (ts.isEmpty()) // no more people left
+ return null;
+ Person cand = ts.last();
+ // System.err.println("Score: " + cand.score);
+ ts.remove(cand);
+
+ for (Iterator<Person> it = cand.neighbors() ; it.hasNext() ; )
{
+ Person p = it.next();
+
+ if (ts.contains(p)) {
+ ts.remove(p);
+ p.score++;
+ ts.add(p);
+ } else {
+ p.score++;
+ if (!p.isInNetwork()) {
+ ts.add(p);
+ }
+ }
+ }
+
+ return cand;
+ }
+
+ /**
+ * Chooses the next person, uniformly at random rather than weighted.
+ */
+ protected Person growNetworkRandom() {
+ // System.err.println("TS SIZE: " + ts.size());
+ if (ts.isEmpty())
+ return null;
+
+ int k = re.nextInt(ts.size());
+ int i = 0;
+ for (Iterator<Person> it = ts.iterator(); it.hasNext(); i++) {
+ Person p = it.next();
+ if (i==k) {
+ ts.remove(p);
+ return p;
+ }
+ }
+
+ throw new RuntimeException("growNetworkRandom(): sample
error");
+ }
+
+
+ /**
+ * Takes somebody out of the network.
+ */
+ protected void shrinkNetwork(Person p) {
+ for (Iterator<Person> it = p.neighbors() ; it.hasNext() ; ) {
+ Person n = it.next();
+ if (ts.contains(n)) {
+ ts.remove(n);
+ n.score--;
+ ts.add(n);
+ } else {
+ n.score--;
+ }
+ }
+ ts.add(p);
+ }
+
+}
Added: trunk/apps/simsalabim/DarknetNode.java
===================================================================
--- trunk/apps/simsalabim/DarknetNode.java (rev 0)
+++ trunk/apps/simsalabim/DarknetNode.java 2009-02-11 13:53:49 UTC (rev
25585)
@@ -0,0 +1,504 @@
+package simsalabim;
+import java.util.*;
+import simsalabim.utils.*;
+
+public class DarknetNode extends Node<Darknet, CircleKey> {
+
+ protected LRUHash data;
+ protected LRUHash cache;
+ protected Person user;
+
+ protected CircleKey pos;
+ protected LinkedList<DarknetNode> neighbors;
+ protected HashMap<DarknetNode,Boolean> neighbors_lookup;
+ protected HashMap<DarknetNode,Boolean> open_lookup;
+ protected LinkedList<DarknetNode> openNeighbors;
+
+ private boolean inNetwork = false;
+
+ private int numQueries = 0;
+
+ public DarknetNode(Darknet god, int num, Person user, CircleKey pos) {
+ super(god, num);
+ this.user = user;
+
+ this.pos = pos;
+
+ data = new LRUHash(god.STORE_SIZE);
+ cache = new LRUHash(god.CACHE_SIZE);
+ neighbors = new LinkedList<DarknetNode>();
+ openNeighbors = new LinkedList<DarknetNode>();
+ neighbors_lookup = new HashMap<DarknetNode,Boolean>();
+ open_lookup = new HashMap<DarknetNode,Boolean>();
+ }
+
+ public boolean isOpennet() {
+ return user.isOpennet();
+ }
+
+ public boolean isDarknet() {
+ return user.isDarknet();
+ }
+
+ /**
+ * Need of opennet: always except when all slots filled by darknet peers
+ */
+ public boolean needsOpennet() {
+ if (!isOpennet())
+ throw new SimulationException("DarknetNode asked about opennet
refs without being an opennet node");
+ return neighbors.size() < Math.min(god.OPENNET_MAXPEERS,
god.MAXPEERS);
+ }
+
+ public boolean needsDarknet() {
+ return neighbors.size() < god.MAXPEERS;
+ }
+
+ public DarknetRoute findRoute(CircleKey k, DarknetRoute dnr) {
+
+ if (!inNetwork)
+ throw new Error("Node not in Network routed to: " +
this);
+ if (!isActive())
+ throw new Error("Node that is active routed to: " +
this);
+
+ /*
+ * Routing with
+ * 1) Backtracking
+ * 2) HTL (fixed decrease per node, not probabilistic as in
freenet)
+ *
+ * Cache/Store: when route has completed
+ */
+
+ if (dnr == null)
+ dnr = new DarknetRoute(god.N_BEST, god.HTL);
+
+ dnr.atNode(this, k);
+ numQueries++;
+
+ if (data.contains(k) || cache.contains(k)) //
terminate on success
+ return dnr;
+
+ while (dnr.htl > 0) {
+ double bd = Double.MAX_VALUE;
+ DarknetNode cand = null;
+
+ for (Iterator<DarknetNode> it = neighbors() ;
it.hasNext() ;) {
+ DarknetNode t = it.next();
+ if (dnr.contains(t))
+ continue;
+
+ double cd = t.pos.dist(k);
+
+ if (cd < bd) {
+ bd = cd;
+ cand = t;
+ }
+ }
+
+ if (cand != null) {
+ DarknetRoute branch = cand.findRoute(k, dnr);
+ dnr.atNode(this,k);
+
+ if (branch.findData(k) != null) {
+ if (hasOpennetNeighbor(cand))
+ moveUpOpennet(cand); //
Freenet 0.7: Keep opennet nodes at LRU
+
+ return dnr;
+ }
+ } else {
+ return dnr; // Dead end
+ }
+ }
+
+ return dnr;
+
+ }
+
+ /**
+ * To keep opennet peers sorted in most-recently used
+ */
+ public void moveUpOpennet(DarknetNode on) {
+ if (!hasOpennetNeighbor(on))
+ throw new SimulationException("moveUpOpennet(): Lacking
neighbor");
+
+ openNeighbors.remove(on);
+ openNeighbors.addFirst(on);
+ }
+
+ public int nKeys() { return data.size(); }
+
+ /**
+ * Connect to online darknet nodes up to a limit. With many available,
pick at random.
+ */
+ public void refreshDarknet() {
+ int room = god.MAXPEERS - neighbors.size();
+ if (room == 0)
+ return;
+ if (room < 0)
+ throw new SimulationException("refreshDarknet():
exceeding MAXPEERS");
+
+ int avail = 0;
+ for (Iterator<Person> it = user.neighbors() ; it.hasNext() ; ) {
+ Person p = it.next();
+ if (p.isInNetwork() && !hasDarknetNeighbor(p.getNode())
&& p.getNode().needsDarknet())
+ avail++;
+ }
+ if (avail == 0)
+ return;
+
+ if (avail <= room) {
+ for (Iterator<Person> it = user.neighbors() ;
it.hasNext() ; ) {
+ Person p = it.next();
+ if (p.isInNetwork() &&
!hasDarknetNeighbor(p.getNode()) && p.getNode().needsDarknet()) {
+ makeNeighbors(p.getNode());
+ }
+ }
+ }
+ else {
+ // If more peers available than room, pick randomly
+ for (int i=0; i<room; i++) {
+ int ni = god.random().nextInt(avail-i);
+ int nj = 0;
+ Person p = null;
+
+ for (Iterator<Person> it = user.neighbors();
it.hasNext() ; ) {
+ p = it.next();
+ if (p.isInNetwork() &&
!hasDarknetNeighbor(p.getNode()) && p.getNode().needsDarknet()) {
+ if (nj == ni)
+ break;
+ nj++;
+ }
+ }
+
+ if (ni != nj) throw new
SimulationException("Sample error: picking darknet peer");
+
+ makeNeighbors(p.getNode());
+ }
+ }
+ }
+
+ /**
+ * Drop opennet nodes if we have too many.
+ * Drop policy: LRU wrt. successful requests
+ */
+
+ public void policyOpennet() {
+ if (!isOpennet())
+ throw new SimulationException("Non-opennet node
imposing opennet policy");
+
+ int maxopen = Math.min(god.OPENNET_MAXPEERS, god.MAXPEERS);
+ if (openNeighbors.size() > Math.max(0,
maxopen-neighbors.size())) {
+ int drop = openNeighbors.size() - Math.max(0,
maxopen-neighbors.size());
+
+ for (int i=0; i<drop; i++) {
+ DarknetNode on = openNeighbors.getLast(); //
Freenet 0.7: LRU
+ removeOpenNeighbor(on);
+ }
+ }
+ }
+
+ public int join() {
+ inNetwork = true;
+ user.joinedNetwork(this);
+ refreshDarknet();
+
+ if (this.isDarknet()) {
+ int nsw = Math.min(god.size, god.INITIAL_SWITCHES);
+ for (int i = 0 ; i < nsw ; i++) {
+ makeSwitch();
+ }
+ return nsw * god.RAND_STEPS;
+ }
+
+ return 0;
+ }
+
+ public DarknetNode makeSwitch() {
+
+ if (!this.isDarknet() && !(god.HYBRID_NODES_SWAP_PROB==1 ||
god.OPENNET_NODES_SWAP_PROB==1)) {
+ throw new Error("makeSwitch() forbidden for non-darknet
nodes");
+ }
+
+ DarknetNode n = getRandomNode();
+ if ((n != null) && (n.isDarknet() ||
god.HYBRID_NODES_SWAP_PROB==1 || god.OPENNET_NODES_SWAP_PROB==1)) {
+ double mhVal = Math.min(1, Math.exp((logdist(pos) +
n.logdist(n.pos)
+ - logdist(n.pos)
+ - n.logdist(pos))));
+
+ if (god.random().nextDouble() < mhVal) {
+ CircleKey mp = pos;
+ pos = n.pos;
+ n.pos = mp;
+ }
+ }
+
+ return n;
+
+ }
+
+ public int leave(boolean permanent) {
+ inNetwork = false; //NB: person disappears before node, to
avoid peers reconnecting
+ user.leftNetwork();
+ int n = neighbors.size() + openNeighbors.size();
+
+ for (Iterator<Person> it = user.neighbors() ; it.hasNext() ; ) {
+ Person p = it.next();
+ if (p.isInNetwork()) {
+ removeNeighbor(p.getNode());
+ p.getNode().refreshDarknet();
+ }
+ }
+
+ for (Iterator<DarknetNode> it = openNeighbors.iterator() ;
it.hasNext() ; ) {
+ DarknetNode open = it.next();
+ open.openNeighbors.remove(this);
+ }
+ openNeighbors.clear();
+
+ // Dormant nodes dont remove data
+ if (permanent) {
+ for (Iterator<Data> it = data.data() ; it.hasNext() ;) {
+ it.next().removedFrom(this);
+ }
+
+ for (Iterator<Data> it = cache.data() ; it.hasNext() ;) {
+ it.next().removedFrom(this);
+ }
+ }
+
+ return n;
+ }
+
+ public boolean isSink(CircleKey k) {
+ for (DarknetNode n : neighbors) {
+ if (k.dist(n.pos) < k.dist(pos))
+ return false;
+ }
+ return true;
+ }
+
+ public boolean hasData(CircleKey k) {
+ return data.contains(k) || cache.contains(k);
+ }
+
+ public Data findData(CircleKey k) {
+ Data cached = cache.get(k);
+
+ return (cached != null) ? cached : data.get(k);
+ }
+
+ /**
+ * Always store in cache
+ * @sink: Whether to store in the long-term storage
+ */
+
+ public void storeData(Data<CircleKey> d, boolean sink) {
+ if (sink) {
+ if (!data.contains(d.key()))
+ d.addedTo(this);
+ Data r = data.put(d);
+ if (r != null)
+ r.removedFrom(this);
+ }
+
+ if (!cache.contains(d.key()))
+ d.addedTo(this);
+ Data r = cache.put(d);
+ if (r != null)
+ r.removedFrom(this);
+
+ }
+
+ /**
+ * Stores at this node, and depth generation neighbors.
+ */
+ public void explosiveStore(Data d, int depth) {
+ storeData(d, true); // Default option to put into store/cache
+ if (depth > 0) {
+ for (Iterator<DarknetNode> it = neighbors.iterator() ;
it.hasNext() ;) {
+ it.next().explosiveStore(d, depth - 1);
+ }
+ }
+ }
+
+
+ public Iterator<DarknetNode> neighbors() {
+ return new DoubleIterator<DarknetNode>(neighbors.iterator(),
+ openNeighbors.iterator());
+ }
+
+ public Person person() {
+ return user;
+ }
+
+ // Get random node in the network (to later perform swap attempt)
+ protected DarknetNode getRandomNode() {
+ if (neighbors.size() == 0)
+ return null; // this; using null to cause crash because
this is
+ // bad.
+
+ DarknetNode curr = this;
+ for (int i = 0 ; i < god.RAND_STEPS ; i++) {
+ curr =
curr.neighbors.get(god.random().nextInt(curr.neighbors.size()));
+ }
+ return curr;
+ }
+
+ public boolean hasDarknetNeighbor(DarknetNode dn) {
+ return neighbors_lookup.containsKey(dn);
+ }
+
+ public boolean hasOpennetNeighbor(DarknetNode on) {
+ return open_lookup.containsKey(on);
+ }
+
+ /**
+ * Adding darknet peers may result in dropping opennet peers
+ */
+ protected void makeNeighbors(DarknetNode dn) {
+
+ if (this.needsDarknet() && dn.needsDarknet()) {
+ if (!hasDarknetNeighbor(dn)) {
+ neighbors.add(dn);
+ neighbors_lookup.put(dn, null);
+ if (isOpennet())
+ policyOpennet();
+ }
+
+ if (!dn.hasDarknetNeighbor(this)) {
+ dn.neighbors.add(this);
+ dn.neighbors_lookup.put(this, null);
+ if (dn.isOpennet())
+ dn.policyOpennet();
+ }
+ }
+ }
+
+ /**
+ * Add opennet connection with imposing policy
+ */
+ public void reLink(DarknetNode on) {
+ if (!hasOpennetNeighbor(on) && !hasDarknetNeighbor(on)) {
+ makeOpenNeighbors(on);
+ policyOpennet();
+ on.policyOpennet();
+ }
+ }
+
+ protected void makeOpenNeighbors(DarknetNode on) {
+ if (!hasDarknetNeighbor(on)) { // Protection
against dual darknet/opennet peers
+ if (!hasOpennetNeighbor(on)) {
+ openNeighbors.add(on);
+ open_lookup.put(on, null);
+ }
+
+ if (!on.hasOpennetNeighbor(this)) {
+ on.openNeighbors.add(this);
+ on.open_lookup.put(this, null);
+ }
+ }
+ }
+
+ protected void removeNeighbor(DarknetNode dn) {
+ neighbors.remove(dn);
+ neighbors_lookup.remove(dn);
+ dn.neighbors.remove(this);
+ dn.neighbors_lookup.remove(this);
+ }
+
+ protected void removeOpenNeighbor(DarknetNode on) {
+ openNeighbors.remove(on);
+ open_lookup.remove(on);
+ on.openNeighbors.remove(this);
+ on.open_lookup.remove(this);
+ }
+
+ /**
+ * Calculates the log distance to the neighbors of this node from
newpos. If
+ * a neighbor has position newpos, then it is given my current position.
+ */
+ private double logdist(CircleKey newpos) {
+ double val = 0.0f;
+ for (Iterator<DarknetNode> it = neighbors.iterator() ;
it.hasNext() ;) {
+ DarknetNode dn = it.next();
+ val += Math.log(dn.pos == newpos ? pos.dist(newpos) :
+ dn.pos.dist(newpos));
+ }
+ return val;
+ }
+
+
+ public int fieldnum() {return 7;}
+
+ public String[] fields() {
+ return new
String[]{"Num","Position","DarkDegree","OpenDegree","Queries", "Data",
"LogDist"};
+ }
+
+ public String[] info() {
+ return new String[] {
+ Integer.toString(num), pos.stringVal(),
+ Integer.toString(neighbors.size()),
Integer.toString(openNeighbors.size()),
+ Integer.toString(numQueries),
Integer.toString(data.size()),
+ Double.toString(logdist(pos))
+ };
+ }
+
+ public String toString() {
+ return "DN#" + num + " (" + pos + ")";
+ }
+
+
+ /**
+ * Feeds an aggregator called "LinkDistances" with the keyspace
distance to
+ * each of my long links. Feeds an aggregator called "NodeTraffic" with
the
+ * number of queries that passed me.
+ */
+ public void feedAggregator(DataAggregator da) {
+ super.feedAggregator(da);
+
+ if (da.name().equals("LinkDistances")) {
+ for (DarknetNode n : neighbors)
+ da.next(pos.dist(n.pos));
+ } else if (da.name().equals("NodeTraffic")) {
+ da.next(numQueries);
+ }
+ }
+
+
+
+ private class DoubleIterator<T> implements Iterator<T> {
+
+ private Iterator<T> first;
+ private Iterator<T> second;
+ private boolean f;
+
+ public DoubleIterator(Iterator<T> first, Iterator<T> second) {
+ this.first = first;
+ this.second = second;
+
+ f = first.hasNext();
+ }
+
+ public T next() {
+ if (f) {
+ T r = first.next();
+ f = first.hasNext();
+ return r;
+ } else {
+ return second.next();
+ }
+ }
+
+ public boolean hasNext() {
+ return f || second.hasNext();
+ }
+
+ public void remove() {
+ if (f)
+ first.remove();
+ else
+ second.remove();
+ }
+
+ }
+
+}
Added: trunk/apps/simsalabim/DarknetRoute.java
===================================================================
--- trunk/apps/simsalabim/DarknetRoute.java (rev 0)
+++ trunk/apps/simsalabim/DarknetRoute.java 2009-02-11 13:53:49 UTC (rev
25585)
@@ -0,0 +1,184 @@
+// The representation of a route
+//
+// A route is represented by all the nodes passed from source to
+// destination, and then the sequence of nodes returning to source.
+// This means that backtracking may be an explicit part of a route to the
destination,
+// as well as the path from the target back to the source.
+//
+// Most operations here (such as storage) assume a successful route to work
correctly
+
+package simsalabim;
+import simsalabim.utils.*;
+import java.util.*;
+
+
+public class DarknetRoute implements Iterable<DarknetNode>,
Contains<DarknetNode> {
+
+ LinkedList<DarknetNode> route = new LinkedList<DarknetNode>();
+ HashMap<DarknetNode,Boolean> visited = new
HashMap<DarknetNode,Boolean>(); // Space-Time tradeoff for DarknetNode routing
+
+ double closest = Double.MAX_VALUE;
+ int stepsSince = 0; // Obsolete
+ int htl = 0;
+
+ DarknetNode bestNodes[];
+
+ private int nBest;
+
+ public DarknetRoute(int nBest, int htl) {
+ this.nBest = nBest;
+ this.htl = htl;
+ bestNodes = new DarknetNode[nBest];
+ }
+
+ public void atNode(DarknetNode dn, CircleKey k) {
+ route.add(dn);
+ visited.put(dn,null);
+ htl--; // Another hop for this route
+
+ int n = -1;
+ double md = 0;
+ for (int i = 0 ; i < nBest ; i++) {
+ if (bestNodes[i] == null) {
+ n = i;
+ break;
+ }
+ double cd = k.dist(bestNodes[i].pos);
+ if (cd > md) {
+ n = i;
+ md = cd;
+ }
+ }
+
+ if (n >= 0 && (bestNodes[n] == null ||
+ k.dist(bestNodes[n].pos) > k.dist(dn.pos))) {
+ bestNodes[n] = dn;
+ }
+
+ }
+
+
+ public int size() {
+ return route.size();
+ }
+
+ public Iterator<DarknetNode> iterator() {
+ return route.iterator();
+ }
+
+ public boolean contains(DarknetNode dn) {
+ // return route.contains(dn);
+ return visited.containsKey(dn);
+ }
+
+ public Data findData(CircleKey k) {
+ for (Iterator<DarknetNode> it = route.iterator() ; it.hasNext()
;) {
+ Data d = it.next().findData(k);
+ if (d != null)
+ return d;
+ }
+ return null;
+ }
+
+ //public void storeData(Data d) {
+ // for (Iterator<DarknetNode> it = route.iterator() ; it.hasNext()
;) {
+ // it.next().storeData(d);
+ // }
+ //}
+
+ /**
+ * Store data in the route (always in cache, maybe also permanent)
+ *
+ * @d: data
+ * @sink: to attempt storage in sink
+ * @full: to store in the full (forward) path, else only in the return
path
+ */
+
+ public int storeData(Data<CircleKey> d, boolean sink, boolean full) {
+
+ int nsink = 0;
+
+ LinkedList<DarknetNode> target;
+ if (full)
+ target = route;
+ else
+ target = retpath();
+
+ for (DarknetNode n : target) {
+ if (sink && n.isSink(d.key())) {
+ n.storeData(d, true);
+ nsink++;
+ }
+ else
+ n.storeData(d, false);
+ }
+
+ return nsink;
+ }
+
+ //public void storeBest(Data d) {
+ // for (int i = 0 ; i < nBest ; i++) {
+ // if (bestNodes[i] != null)
+ // bestNodes[i].storeData(d);
+ // }
+ //}
+
+ /**
+ * ASSUMES: a successful query route (source ... dest ... source)
+ *
+ * Returns the return path (dest to source)
+ */
+
+ public LinkedList<DarknetNode> retpath() {
+ LinkedList<DarknetNode> retpath = new LinkedList<DarknetNode>();
+
+ /* Obtain the return path */
+ ListIterator<DarknetNode> li = route.listIterator(route.size());
+ while (li.hasPrevious()) {
+ DarknetNode n = li.previous();
+ if (retpath.contains(n))
+ break;
+ retpath.addFirst(n);
+ }
+ return retpath;
+ }
+
+
+ /**
+ * Relinks nodes open neighbors to one of the best nodes with given
+ * probability, if possible.
+ * ASSUMES: that this DarknetRoute contains WHOLE PATH (source ... dest
... source)
+ */
+ public void reLink(RandomEngine re, float prob, float rewrite_prob) {
+ LinkedList<DarknetNode> retpath = retpath();
+
+ // Each node, when it wants to, may add its own ref to a
back-propagating request
+
+ DarknetNode target = (retpath.getFirst().isOpennet() &&
retpath.getFirst().needsOpennet()) ? retpath.getFirst() : null;
+ ListIterator<DarknetNode> retitr = retpath.listIterator(1);
+ while (retitr.hasNext()) {
+ DarknetNode current = retitr.next();
+ if (!current.isOpennet() || !current.needsOpennet())
+ continue;
+
+ if (target == null) {
+ target = current; // Always seek
connections
+ continue;
+ }
+ else if (re.nextFloat() < rewrite_prob) { // Maybe steal
the reference (as in Freenet 0.7)
+ target = current;
+ }
+ else if (re.nextFloat() < prob) {
+ current.reLink(target);
+
+ // Maybe propagate ref backwards
+ if (current.needsOpennet()) {
+ target = current;
+ } else {
+ target = null;
+ }
+
+ }
+ }
+ }
+}
Added: trunk/apps/simsalabim/Data.java
===================================================================
--- trunk/apps/simsalabim/Data.java (rev 0)
+++ trunk/apps/simsalabim/Data.java 2009-02-11 13:53:49 UTC (rev 25585)
@@ -0,0 +1,113 @@
+package simsalabim;
+
+public class Data<K extends Key> implements InfoObject {
+
+ private long size;
+ private K key;
+
+ private long createTime;
+ private long placeTime = -1;
+ private long deathTime = -1;
+ private long forgetTime = -1;
+
+ private int storeCount = 0;
+ private int retrieveCount = 0;
+
+ // For network partitioning
+ private int sourceNetwork = 0;
+
+ public Data(Simulator god, K key, long size) {
+ this(key, size, god.time());
+ }
+
+ public Data(K key, long size, long createTime) {
+ this.key = key;
+ this.size = size;
+ this.createTime = createTime;
+ }
+
+ public K key() {
+ return key;
+ }
+
+ public long size() {
+ return size;
+ }
+
+ public void addedTo(Node n) {
+ if (deathTime != -1)
+ System.err.println("Added to node although deathtime set " +
this);
+ if (placeTime == -1) {
+ if (storeCount != 0)
+ throw new SimulationException("Storage Count of data object " +
+ "not zero on insert!");
+ placeTime = n.time();
+ }
+ storeCount++;
+ }
+
+ public void removedFrom(Node n) {
+ if (storeCount == 0)
+ throw new SimulationException("Data removed more times than stored"
+ + ". Node: " + n);
+ storeCount--;
+
+ if (storeCount == 0)
+ deathTime = n.time();
+ }
+
+ public void forgotten(long time) {
+ this.forgetTime = time;
+ }
+
+ public void retrieved() {
+ this.retrieveCount++;
+ }
+
+ public int fieldnum() {
+ return 8;
+ }
+
+ public void sourceNetwork(int id) {
+ sourceNetwork = id;
+ }
+
+ public int sourceNetwork() {
+ return sourceNetwork;
+ }
+
+ // Info fields
+ private static final String[] flds = {
+ "Key",
+ "Size",
+ "Created",
+ "Placed",
+ "Died",
+ "Forgotten",
+ "Node Count",
+ "RetrieveCount"
+ };
+
+ public String[] fields() {
+ return flds;
+ }
+
+ public String[] info() {
+ return new String[] {
+ key.stringVal(),
+ Long.toString(size),
+ Long.toString(createTime),
+ Long.toString(placeTime),
+ Long.toString(deathTime),
+ Long.toString(forgetTime),
+ Long.toString(storeCount),
+ Long.toString(retrieveCount)
+ };
+ }
+
+
+ public String toString() {
+ return "D/" + "K:" + key.toString() + "/S:" + size + "/";
+ }
+
+}
Added: trunk/apps/simsalabim/DataAggregator.java
===================================================================
--- trunk/apps/simsalabim/DataAggregator.java (rev 0)
+++ trunk/apps/simsalabim/DataAggregator.java 2009-02-11 13:53:49 UTC (rev
25585)
@@ -0,0 +1,33 @@
+package simsalabim;
+
+/**
+ * Collects data.
+ */
+public abstract class DataAggregator {
+
+ private String name;
+
+ public DataAggregator(String name) {
+ this.name = name;
+ }
+
+ public String name() {
+ return name;
+ }
+
+ public void next(int val) {
+ next((long) val);
+ }
+
+ public abstract void next(long val);
+
+ public void next(float val) {
+ next((double) val);
+ }
+
+ public abstract void next(double val);
+
+ public void complete() {
+ }
+
+}
Added: trunk/apps/simsalabim/DataSpace.java
===================================================================
--- trunk/apps/simsalabim/DataSpace.java (rev 0)
+++ trunk/apps/simsalabim/DataSpace.java 2009-02-11 13:53:49 UTC (rev
25585)
@@ -0,0 +1,20 @@
+package simsalabim;
+import java.util.*;
+
+public interface DataSpace<K extends Key> {
+
+
+ // public Data<K> newData(Simulator<?, K> god, K key);
+ public Data<K> newData(Simulator god, K key);
+
+ public Data<K> getData(K key);
+
+
+ public Iterator<Data<K>> allData();
+
+ public K chooseKey(RandomEngine re);
+
+ public int size();
+
+ public String info();
+}
Added: trunk/apps/simsalabim/EventLogger.java
===================================================================
--- trunk/apps/simsalabim/EventLogger.java (rev 0)
+++ trunk/apps/simsalabim/EventLogger.java 2009-02-11 13:53:49 UTC (rev
25585)
@@ -0,0 +1,40 @@
+package simsalabim;
+
+/**
+ * En efficient system for output from the simulator.
+ */
+public abstract class EventLogger {
+
+ public abstract void nodeJoined(long time, Node n);
+
+ public abstract void nodeJoinError(long time, Node n, int error);
+
+ public abstract void dataPlaced(long time, Data d);
+
+ public abstract void dataPlaceError(long time, Data d, int error);
+
+ public abstract void dataFound(long time, Data d);
+
+ public abstract void dataNotFound(long time, Key k, int error);
+
+ public abstract void dataFindError(long time, Key k, int error);
+
+ public abstract void warning(long time, int error);
+
+ public abstract void message(long time, String message);
+
+ public String error(int errnum) {
+ if (errnum >= errors.length)
+ return "Unknown";
+ else
+ return errors[errnum];
+ }
+
+ private static final String[] errors = { "Boohoo, I lost my mommy.", //
1
+ "Iceage happened.", // 2
+ "Oskar couldn't code to save his life.", // 3
+ "Route established, but could not find data.", // 4
+ "Routing failed." // 5
+ };
+
+}
Added: trunk/apps/simsalabim/Feedback.java
===================================================================
--- trunk/apps/simsalabim/Feedback.java (rev 0)
+++ trunk/apps/simsalabim/Feedback.java 2009-02-11 13:53:49 UTC (rev 25585)
@@ -0,0 +1,20 @@
+package simsalabim;
+
+/**
+ * A simple interface whereby a task can give feedback on it's process for
+ * study.
+ */
+public interface Feedback {
+
+ /**
+ * @param task
+ * The task that has been run (@see RunTask for numbers).
+ * @param success
+ * The success state.
+ * @param cost
+ * The cost of the task (typically the number of nodes
involved)
+ * @see RunTask
+ */
+ public abstract void feedback(int task, boolean success, double[] msg);
+
+}
Added: trunk/apps/simsalabim/HBuildTask.java
===================================================================
--- trunk/apps/simsalabim/HBuildTask.java (rev 0)
+++ trunk/apps/simsalabim/HBuildTask.java 2009-02-11 13:53:49 UTC (rev
25585)
@@ -0,0 +1,231 @@
+package simsalabim;
+
+/**
+ * Task which builds a simulates a living network.
+ */
+
+public class HBuildTask extends RunTask {
+
+ private double joinRate;
+
+ private double leaveRate;
+
+ private double searchRate;
+
+ private double placeRate;
+
+ private double maintRate;
+
+ private long poolSize;
+
+ private long tsearches = 0;
+
+ private long ssearches = 0;
+
+ private long tplaces = 0;
+
+ private long splaces = 0;
+
+ private long tmaint = 0;
+
+ private long smaint = 0;
+
+ private long tjoin = 0;
+
+ private long tleave = 0;
+
+ private long tsearchcost = 0;
+
+ private long ssearchcost = 0;
+
+ private long tplacecost = 0;
+
+ private long splacecost = 0;
+
+ private long tmaintcost = 0;
+
+ private long tdualmaint = 0;
+ private long sdualmaint = 0;
+ private long sroutesteps = 0;
+ private long tlongsearches = 0;
+ private long slongsearches = 0;
+ private long tshortsearches = 0;
+ private long sshortsearches = 0;
+
+ /**
+ * The rates are per node per clocktick. They should be low (the sum of
all
+ * the rates times poolSize should be less than << 1.
+ *
+ * @param runTill
+ * Run until this clockbeat
+ * @param searchRate
+ * The rate at which each active node initiates searches
+ * @param placeRate
+ * The rate at which each active node initiates placings.
+ * @param poolSize
+ * The size of the pool of available nodes.
+ * @param joinRate
+ * The rate at which each inactive node joins.
+ * @param leaveRate
+ * The rate at which each
+ * @param maintRate
+ * The rate at which to run maintenance.
+ */
+ public HBuildTask(long runTill, double searchRate, double placeRate,
+ int poolSize, double joinRate, double leaveRate, double
maintRate) {
+
+ super(runTill);
+
+ this.searchRate = searchRate;
+ this.placeRate = placeRate;
+ this.poolSize = poolSize;
+ this.joinRate = joinRate;
+ this.leaveRate = leaveRate;
+ this.maintRate = maintRate;
+
+ }
+
+ /**
+ * String constructor for script. The values should be in the same
order as
+ * above.
+ */
+ public HBuildTask(String[] s) throws ScriptException {
+ super(Long.parseLong(s[0]));
+
+ // System.err.println(Main.tabbed(s));
+
+ if (s.length < 7)
+ throw new ScriptException("BuildTask requires seven
parameters, not "
+ + s.length);
+
+ this.searchRate = Double.parseDouble(s[1]);
+ this.placeRate = Double.parseDouble(s[2]);
+
+ this.poolSize = Long.parseLong(s[3]);
+ this.joinRate = Double.parseDouble(s[4]);
+ this.leaveRate = Double.parseDouble(s[5]);
+ this.maintRate = Double.parseDouble(s[6]);
+
+ System.err.println("HBuildTask having joinRate " + joinRate + "
and leaveRate " + leaveRate);
+
+ // System.err.println(searchRate + " " + placeRate);
+
+ }
+
+ public void started(long time, EventLogger ev) {
+ ev.message(time, "HBuildTask Started. Poolsize " + poolSize
+ + " join/leave rate: " + joinRate + "/" +
leaveRate
+ + ". Insert/request rate: " + placeRate + "/" +
searchRate
+ + ". Maintenance rate: " + maintRate);
+ }
+
+ public void done(long time, EventLogger ev) {
+ ev.message(time, "HBuildTask Complete. " + tsearches + "
searches ("
+ + ((float) ssearches) / tsearches + " succ, "
+ + ((double) tsearchcost) / tsearches + " cost" + ",
" + ((double)sroutesteps) / ssearches + " costsucc)." + tplaces
+ + " places (" + ((float) splaces) / tplaces + "
succ, "
+ + ((double) tplacecost) / tplaces + " cost)." +
tjoin
+ + " joins, " + tleave + " leave," + tmaint
+ + " maintenance tasks with " + tmaintcost + "
attempts (" + (smaint) + "succ)."
+ + "Dual: " + tdualmaint + " crossed, " + sdualmaint
+ " succeeded."
+ + "[" + ((float) smaint/tmaintcost) + ", " +
((float) sdualmaint/tdualmaint) + "]");
+ ev.message(time, "HBuildTask PARTITION: \t" + tshortsearches +
" " + sshortsearches + " " + tlongsearches + " " + slongsearches + "(" +
((double)sshortsearches/tshortsearches) + "," +
((double)slongsearches/tlongsearches) + ")" );
+ }
+
+ /**
+ * Calculates the time until a task.
+ */
+ public long timeTillTask(Simulator s) {
+ RandomEngine re = s.random();
+
+ long joinLeft = Math.max(0, poolSize - s.netSize());
+ int netSize = s.netSize();
+
+ double rate = joinLeft * joinRate + netSize
+ * (searchRate + placeRate + leaveRate +
maintRate);
+ // try { Thread.sleep(100); } catch (Exception e) {}
+ // System.err.println("rate: " + rate + " netsize: " + netSize);
+
+ long t = Math.max((long) (Math.log(re.nextDouble()) / (rate *
-1)), 1);
+ System.err.print("t = " + t + " rate = " + rate + ", ");
+ return t;
+ }
+
+ /**
+ * Calculates the type of task to do after a call to time above.
+ */
+ public int taskType(Simulator s) {
+ RandomEngine re = s.random();
+ long joinLeft = Math.max(0, poolSize - s.netSize());
+ int netSize = s.netSize();
+ int maintSize = s.maintSize();
+
+ double joinP = joinLeft * joinRate;
+ double leaveP = netSize * leaveRate;
+ double searchP = netSize * searchRate;
+ double placeP = netSize * placeRate;
+ double maintP = maintSize * maintRate;
+
+ double norm = joinP + searchP + placeP + maintP + leaveP;
+ double val = re.nextDouble() * norm;
+
+ if (val <= joinP) {
+ return JOIN;
+ } else if (val <= searchP + joinP) {
+ return SEARCH;
+ } else if (val <= searchP + joinP + placeP) {
+ return PLACE;
+ } else if (val <= searchP + joinP + placeP + maintP) {
+ return MAINTENANCE;
+ } else {
+ return LEAVE;
+ }
+ }
+
+ public void feedback(int task, boolean success, double[] costarr) {
+ int cost = (int) costarr[0];
+
+ if (task == SEARCH) {
+ tsearches++;
+ ssearches += success ? 1 : 0;
+ tsearchcost += cost;
+ sroutesteps += costarr[1];
+
+ int srcNet = (int) costarr[2];
+ int origNet = (int) costarr[3];
+ if (srcNet>0 && origNet>0) {
+ if (srcNet != origNet) {
+ tlongsearches++;
+ slongsearches += success ? 1 : 0;
+ } else {
+ tshortsearches++;
+ sshortsearches += success ? 1 : 0;
+ }
+ }
+
+ } else if (task == PLACE) {
+ tplaces++;
+ splaces += success ? 1 : 0;
+ tplacecost += cost;
+ } else if (task == MAINTENANCE) {
+ tmaint++;
+ tmaintcost += cost;
+ // Handle the case of network partitions
+ if (costarr.length > 3) {
+ smaint += costarr[1];
+ tdualmaint += costarr[2];
+ sdualmaint += costarr[3];
+ }
+ } else if (task == LEAVE) {
+ tleave++;
+ } else if (task == JOIN) {
+ tjoin++;
+ } else if (task == DUALSTATS) {
+
+
+
+ }
+
+ }
+
+}
Added: trunk/apps/simsalabim/HDualStats.java
===================================================================
--- trunk/apps/simsalabim/HDualStats.java (rev 0)
+++ trunk/apps/simsalabim/HDualStats.java 2009-02-11 13:53:49 UTC (rev
25585)
@@ -0,0 +1,58 @@
+package simsalabim;
+
+/**
+ * Print some stats comparing dual networks in a simulator
+ */
+
+public class HDualStats extends RunTask {
+
+ int first, second;
+ static int calls;
+ double varDist1, varDist2, varDistFull, varDistMutual;
+
+ /**
+ * String constructor for script. The values should be in the same
order as
+ * above.
+ */
+ public HDualStats(String[] s) throws ScriptException {
+ super(Long.parseLong(s[0]));
+ calls = 0;
+ first = -1;
+ second = -1;
+ varDist1 = -1;
+ varDist2 = -1;
+ varDistFull = -1;
+ }
+
+ public void done(long time, EventLogger ev) {
+ // ev.message(time, "HDualStats Complete. " + swaps_1 + " and "
+ swaps_2 + "swaps initiated in the networks. Swaps proposed between: " +
cross_swaps + " of which " + cross_swaps_accepted + " were accepted.");
+
+ ev.message(time, calls +
"\tACTIVE1\tACTIVE2\tVARDIST1\tVARDIST2\tVARDISTFULL\tVARDISTMUTUAL");
+ ev.message(time, "\t" + first + "\t" + second + "\t" +varDist1
+"\t" + varDist2 + "\t" + varDistFull);
+
+ }
+
+ /**
+ * Calculates the time until a task.
+ */
+ public long timeTillTask(RandomEngine re) {
+ return 1;
+ }
+
+ /**
+ * Calculates the type of task to do after a call to time above.
+ */
+ public int taskType(RandomEngine re) {
+ return DUALSTATS;
+ }
+
+ public void feedback(int task, boolean success, double[] costarr) {
+ calls++;
+ first = (int) costarr[0];
+ second = (int) costarr[1];
+ varDist1 = costarr[2];
+ varDist2 = costarr[3];
+ varDistFull = costarr[4];
+ varDistMutual = costarr[5];
+ }
+}
Added: trunk/apps/simsalabim/HJoinTask.java
===================================================================
--- trunk/apps/simsalabim/HJoinTask.java (rev 0)
+++ trunk/apps/simsalabim/HJoinTask.java 2009-02-11 13:53:49 UTC (rev
25585)
@@ -0,0 +1,68 @@
+package simsalabim;
+
+/**
+ * Has a node join at every timestep (thus call with number of nodes to join
from the underlying social network)
+ */
+
+public class HJoinTask extends RunTask {
+
+ private double joinRate;
+
+ private double mRate;
+
+ private long tjoins = 0;
+
+ private long tjoincost = 0;
+
+ private long tmaint = 0;
+
+ private long tmaintcost = 0;
+
+ /**
+ * String constructor for script. The values should be in the same
order as
+ * above.
+ */
+ public HJoinTask(String[] s) throws ScriptException {
+ super(Long.parseLong(s[0]));
+
+ if (s.length < 1)
+ throw new ScriptException("JoinTask requires one
parameter, not "
+ + s.length);
+
+ }
+
+ public void done(long time, EventLogger ev) {
+ ev.message(time, "HJoinTask Complete. " + tjoins + " joins ("
+ + ((float) tjoincost) / tjoins + " cost)." +
tmaint
+ + " maintenance.");
+ }
+
+ /**
+ * Calculates the time until a task.
+ */
+ public long timeTillTask(RandomEngine re) {
+ return 1;
+ }
+
+ /**
+ * Calculates the type of task to do after a call to time above.
+ */
+ public int taskType(RandomEngine re) {
+ return JOIN;
+ /* return re.nextDouble() < (joinRate / (joinRate + mRate)) ? JOIN
+ : MAINTENANCE;
+ */
+ }
+
+ public void feedback(int task, boolean success, double[] costarr) {
+ int cost = (int) costarr[0];
+
+ if (task == JOIN) {
+ tjoins++;
+ tjoincost += cost;
+ } else if (task == MAINTENANCE) {
+ tmaint++;
+ tmaintcost += cost;
+ }
+ }
+}
\ No newline at end of file
Added: trunk/apps/simsalabim/HammingKey.java
===================================================================
--- trunk/apps/simsalabim/HammingKey.java (rev 0)
+++ trunk/apps/simsalabim/HammingKey.java 2009-02-11 13:53:49 UTC (rev
25585)
@@ -0,0 +1,65 @@
+package simsalabim;
+
+public class HammingKey extends PositionKey<HammingKey> {
+
+ public static int BITS_USED = 12;
+
+ public static KeyFactory<HammingKey> getFactory() {
+ return new KeyFactory<HammingKey>() {
+ public HammingKey newKey(long val) {
+ return new HammingKey(val);
+ }
+ };
+ }
+
+
+ private int val;
+
+ public HammingKey(long val) {
+ this.val = (int) val;
+ }
+
+ @Override
+ public double dist(HammingKey pk) {
+ int df = pk.val ^ val;
+ int bts = 0;
+ for (int i = 0 ; i < BITS_USED ; i++) {
+ if((df & 1) > 0)
+ bts++;
+ df >>= 1;
+ }
+ return bts / 64.0;
+ }
+
+ public double ident() {
+ return (double) val;
+ }
+
+ public String stringVal() {
+ return "HK" + Long.toHexString(val);
+ }
+
+ public static void main(String[] args) {
+ java.util.Random r = new java.util.Random();
+ HammingKey k1 = new HammingKey(r.nextLong());
+ for (int i = 0 ; i < 10 ; i++) {
+ System.err.println("----");
+ HammingKey k2 = new HammingKey(r.nextLong());
+ System.err.println(toBString(k1.val));
+ System.err.println(toBString(k2.val));
+ System.err.println(toBString(k1.val ^ k2.val));
+ System.err.println(k1.dist(k2));
+ }
+ }
+
+ private static String toBString(long n) {
+ StringBuffer sb = new StringBuffer();
+ for (int i = 0 ; i < 32 ; i++) {
+ sb.append(n & 1);
+ n >>= 1;
+ // System.err.println("t" + n + "\t" +
Integer.toBinaryString(n));
+ }
+ return sb.reverse().toString();
+ }
+
+}
Added: trunk/apps/simsalabim/HistDataAggregator.java
===================================================================
--- trunk/apps/simsalabim/HistDataAggregator.java
(rev 0)
+++ trunk/apps/simsalabim/HistDataAggregator.java 2009-02-11 13:53:49 UTC
(rev 25585)
@@ -0,0 +1,121 @@
+package simsalabim;
+
+import java.util.Vector;
+import java.util.Enumeration;
+import java.io.PrintStream;
+import java.io.PrintWriter;
+import java.io.FileOutputStream;
+import java.io.IOException;
+
+public class HistDataAggregator extends DataAggregator {
+
+ private int[] hist;
+
+ private double start;
+
+ private double step;
+
+ private double end;
+
+ private PrintStream out;
+
+ private String fname;
+
+ public HistDataAggregator(String name, double start, double step,
double end) {
+ super(name);
+ initHist(start, step, end);
+ out = System.out;
+ }
+
+ public HistDataAggregator(String name, double start, double step,
+ double end, String fname) throws ScriptException {
+ super(name);
+ initHist(start, step, end);
+ this.fname = fname;
+ }
+
+ private void initHist(double start, double step, double end) {
+ this.start = start;
+ this.step = step;
+ this.end = end;
+
+ hist = new int[((int) ((end - start) / step))];
+ }
+
+ public void next(long data) {
+ next((double) data);
+ }
+
+ public void next(double data) {
+ if (data < start || data >= end) {
+ System.err.println("WARNING: HIST DATA OUT OF BOUNDS:
!" + start
+ + " < " + data + " < " + end);
+ }
+
+ hist[(int) Math.ceil((data - start) / step) - 1]++; // not so
nice
+ }
+
+ public void complete() {
+ PrintStream ps;
+
+ if (fname != null) {
+ try {
+ ps = new PrintStream(new
FileOutputStream(fname));
+ } catch (IOException e) {
+ throw new SimulationException("File error : " +
e);
+ }
+ } else {
+ ps = this.out;
+ }
+
+ print(ps);
+
+ if (fname != null)
+ ps.close();
+ }
+
+ public void print(PrintStream ps) {
+ ps.println("#Created by Simsalabim. Data: " + name());
+ ps.println("#name: " + name() + "_y");
+ ps.println("#type: matrix");
+ ps.println("#rows: " + hist.length);
+ ps.println("#columns: 1");
+
+ for (int i = 0; i < hist.length; i++) {
+ ps.println(hist[i]);
+ }
+
+ ps.println("#Created by Simsalabim. Data: " + name());
+ ps.println("#name: " + name() + "_x");
+ ps.println("#type: matrix");
+ ps.println("#rows: " + hist.length);
+ ps.println("#columns: 1");
+
+ for (int i = 0; i < hist.length; i++) {
+ ps.println(start + step / 2.0 + i * step);
+ }
+ }
+
+ public void print(PrintWriter pw) {
+ pw.println("#Created by Simsalabim. Data: " + name());
+ pw.println("#name: " + name() + "_y");
+ pw.println("#type: matrix");
+ pw.println("#rows: " + hist.length);
+ pw.println("#columns: 1");
+
+ for (int i = 0; i < hist.length; i++) {
+ pw.println(hist[i]);
+ }
+
+ pw.println("#Created by Simsalabim. Data: " + name());
+ pw.println("#name: " + name() + "_x");
+ pw.println("#type: matrix");
+ pw.println("#rows: " + hist.length);
+ pw.println("#columns: 1");
+
+ for (int i = 0; i < hist.length; i++) {
+ pw.println(start + step / 2.0 + i * step);
+ }
+ }
+
+}
Added: trunk/apps/simsalabim/InfoCommand.java
===================================================================
--- trunk/apps/simsalabim/InfoCommand.java (rev 0)
+++ trunk/apps/simsalabim/InfoCommand.java 2009-02-11 13:53:49 UTC (rev
25585)
@@ -0,0 +1,60 @@
+package simsalabim;
+import java.util.Iterator;
+import java.util.StringTokenizer;
+import java.io.*;
+
+public class InfoCommand implements ScriptCommand {
+
+ String type;
+ String filename;
+
+ public InfoCommand(String[] st) {
+ type = st[0];
+ filename = st[1];
+ }
+
+
+ public void execute(Simulator s) throws ScriptException {
+ try {
+ PrintWriter pw = new PrintWriter("-".equals(filename) ?
System.err : new FileOutputStream(filename));
+ if (type.equals("nodes")) {
+ pw.println("#" + s.info());
+ writeInfo(s.allNodes(), pw);
+ } else if (type.equals("data")) {
+ pw.println("#" + s.ds.info());
+ writeInfo(s.ds.allData(), pw);
+ } else {
+ System.err.println("Can't output data about: "
+ type);
+ }
+ pw.flush();
+ } catch (IOException e) {
+ throw new ScriptException("Error writing info: " + e);
+ }
+ }
+
+
+ public static void writeInfo(Iterator<? extends InfoObject> i,
PrintWriter pw) {
+ if (i.hasNext()) {
+ InfoObject io = i.next();
+
+ pw.println("#" + tabbed(io.fields()));
+ pw.println(tabbed(io.info()));
+
+ while (i.hasNext()) {
+ io = i.next();
+ pw.println(tabbed(io.info()));
+ }
+ }
+ }
+
+ private static String tabbed(String[] s) {
+ if (s.length < 1)
+ return "";
+ StringBuffer sb = new StringBuffer(s[0]);
+ for (int i = 1 ; i < s.length ; i++) {
+ sb.append('\t').append(s[i]);
+ }
+ return sb.toString();
+ }
+
+}
Added: trunk/apps/simsalabim/InfoObject.java
===================================================================
--- trunk/apps/simsalabim/InfoObject.java (rev 0)
+++ trunk/apps/simsalabim/InfoObject.java 2009-02-11 13:53:49 UTC (rev
25585)
@@ -0,0 +1,19 @@
+package simsalabim;
+
+public interface InfoObject {
+
+ /**
+ * The number of fields. Must be the same for all objects of a
particular
+ * type.
+ */
+ public int fieldnum();
+
+ /**
+ * The names of the fields. Must be the same for all objects of a
particular
+ * type.
+ */
+ public String[] fields();
+
+ public String[] info();
+
+}
Added: trunk/apps/simsalabim/JoinTask.java
===================================================================
--- trunk/apps/simsalabim/JoinTask.java (rev 0)
+++ trunk/apps/simsalabim/JoinTask.java 2009-02-11 13:53:49 UTC (rev 25585)
@@ -0,0 +1,65 @@
+package simsalabim;
+
+/**
+ * Has a node join at a given rate.
+ */
+
+public class JoinTask extends RunTask {
+
+ private double joinRate;
+
+ private long tjoins = 0;
+
+ private long tjoincost = 0;
+
+ public JoinTask(long runTill, double joinRate) {
+
+ super(runTill);
+
+ this.joinRate = joinRate;
+ }
+
+ /**
+ * String constructor for script. The values should be in the same
order as
+ * above.
+ */
+ public JoinTask(String[] s) throws ScriptException {
+ super(Long.parseLong(s[0]));
+
+ if (s.length < 2)
+ throw new ScriptException("JoinTask requires two
parameters, not "
+ + s.length);
+ this.joinRate = Double.parseDouble(s[1]);
+
+ }
+
+ public void done(long time, EventLogger ev) {
+ ev.message(time, "JoinTask Complete. " + tjoins + " joins ("
+ + ((float) tjoincost) / tjoins + " cost).");
+ }
+
+ /**
+ * Calculates the time until a task.
+ */
+ public long timeTillTask(RandomEngine re) {
+ return Math
+ .max((long) (Math.log(re.nextDouble()) /
(joinRate * -1)), 1);
+
+ }
+
+ /**
+ * Calculates the type of task to do after a call to time above.
+ */
+ public int taskType(RandomEngine re) {
+ return JOIN;
+ }
+
+ public void feedback(int task, boolean success, double[] costarr) {
+ int cost = (int) costarr[0];
+ if (task == JOIN) {
+ tjoins++;
+ tjoincost += cost;
+ }
+ }
+
+}
Added: trunk/apps/simsalabim/Key.java
===================================================================
--- trunk/apps/simsalabim/Key.java (rev 0)
+++ trunk/apps/simsalabim/Key.java 2009-02-11 13:53:49 UTC (rev 25585)
@@ -0,0 +1,25 @@
+package simsalabim;
+
+/**
+ * A note about keys: Keys are assumed to be identified by reference. Do not
use
+ * two objects for the same key, much code will treat them as different!
+ */
+public interface Key {
+
+ /**
+ * Returns a floating point value designating the nodes position in the
+ * keyspace.
+ */
+ public double ident();
+
+ /**
+ * Key value expressed in it's natural form as a string.
+ */
+ public String stringVal();
+
+ /**
+ * It is a good idea that keys have these.
+ */
+ public int hashCode();
+
+}
Added: trunk/apps/simsalabim/KeyFactory.java
===================================================================
--- trunk/apps/simsalabim/KeyFactory.java (rev 0)
+++ trunk/apps/simsalabim/KeyFactory.java 2009-02-11 13:53:49 UTC (rev
25585)
@@ -0,0 +1,36 @@
+package simsalabim;
+import java.util.Date;
+
+public abstract class KeyFactory<K extends Key> {
+
+ private static RandomEngine re = null;
+
+ /**
+ * Creates keys for a specific architecture.
+ *
+ * @param val
+ * A random long (64 uniform bits).
+ */
+ public abstract K newKey(long val);
+
+ /**
+ * Creates keys for a specific architecture.
+ *
+ * @param re
+ * Entropy source
+ */
+ public K newKey(RandomEngine re) {
+ return newKey(re.nextLong());
+ }
+
+ /**
+ * Creates keys for specific architecture.
+ */
+ public K newKey() {
+ if (re == null)
+ re = new MersenneTwister(new Date());
+ return newKey(re);
+ }
+
+
+}
Added: trunk/apps/simsalabim/LimitedDataSpace.java
===================================================================
--- trunk/apps/simsalabim/LimitedDataSpace.java (rev 0)
+++ trunk/apps/simsalabim/LimitedDataSpace.java 2009-02-11 13:53:49 UTC (rev
25585)
@@ -0,0 +1,74 @@
+package simsalabim;
+import java.util.*;
+
+public class LimitedDataSpace<K extends Key> implements DataSpace<K> {
+
+
+ private HashMap<K, Data<K>> datamap;
+ private Vector<Data<K>> datav;
+ private Vector<Data<K>> forgotten;
+
+ private long minsize, sizerange;
+ private long maxdocs;
+
+ private long currSize = 0;
+
+ public LimitedDataSpace(int maxdocs, long minsize, long maxsize) {
+ this.minsize = minsize;
+ this.sizerange = maxsize - minsize;
+ this.maxdocs = maxdocs;
+
+ datamap = new HashMap<K, Data<K>>();
+ datav = new Vector<Data<K>>(maxdocs);
+ forgotten = new Vector<Data<K>>(maxdocs);
+ }
+
+
+ public Data<K> newData(Simulator god, K key) {
+ long size = minsize + (long) (god.random().nextDouble() *
sizerange);
+ Data<K> d = new Data<K>(god, key, size);
+ datamap.put(key, d);
+ currSize += d.size();
+
+ if (datav.size() < maxdocs) {
+ datav.add(d);
+ } else {
+ int n = god.random().nextInt(datav.size());
+ Data<K> rm = datav.get(n);
+ rm.forgotten(god.time());
+ forgotten.add(rm);
+ datamap.remove(rm.key());
+ currSize -= rm.size();
+ datav.set(n, d);
+ }
+
+ return d;
+ }
+
+
+ public Data<K> getData(K key) {
+ return datamap.get(key);
+ }
+
+ public Iterator<Data<K>> allData() {
+ return datamap.values().iterator();
+ }
+
+ public int size() {
+ return datav.size();
+ }
+
+ public String info() {
+ return "LimitedDataSpace docs: " + datav.size() + " (of " +
maxdocs + ") bytes: " + currSize;
+ }
+
+ /**
+ * Currently uniform.
+ */
+ public K chooseKey(RandomEngine re) {
+ if (datav.isEmpty())
+ return null;
+ return datav.get(re.nextInt(datav.size())).key();
+ }
+
+}
Added: trunk/apps/simsalabim/MBuildTask.java
===================================================================
--- trunk/apps/simsalabim/MBuildTask.java (rev 0)
+++ trunk/apps/simsalabim/MBuildTask.java 2009-02-11 13:53:49 UTC (rev
25585)
@@ -0,0 +1,189 @@
+package simsalabim;
+
+/**
+ * Task which builds a simulates a living network.
+ */
+
+public class MBuildTask extends RunTask {
+
+ private double joinRate;
+
+ private double leaveRate;
+
+ private double searchRate;
+
+ private double placeRate;
+
+ private double maintRate;
+
+ private long poolSize;
+
+ private long tsearches = 0;
+
+ private long ssearches = 0;
+
+ private long tplaces = 0;
+
+ private long splaces = 0;
+
+ private long tmaint = 0;
+
+ private long tjoin = 0;
+
+ private long tleave = 0;
+
+ private long tsearchcost = 0;
+
+ private long ssearchcost = 0;
+
+ private long tplacecost = 0;
+
+ private long splacecost = 0;
+
+ private long tmaintcost = 0;
+
+ /**
+ * The rates are per node per clocktick. They should be low (the sum of
all
+ * the rates times poolSize should be less than << 1.
+ *
+ * @param runTill
+ * Run until this clockbeat
+ * @param searchRate
+ * The rate at which each active node initiates searches
+ * @param placeRate
+ * The rate at which each active node initiates placings.
+ * @param poolSize
+ * The size of the pool of available nodes.
+ * @param joinRate
+ * The rate at which each inactive node joins.
+ * @param leaveRate
+ * The rate at which each
+ * @param maintRate
+ * The rate at which to run maintenance.
+ */
+ public MBuildTask(long runTill, double searchRate, double placeRate,
+ int poolSize, double joinRate, double leaveRate, double
maintRate) {
+
+ super(runTill);
+
+ this.searchRate = searchRate;
+ this.placeRate = placeRate;
+ this.poolSize = poolSize;
+ this.joinRate = joinRate;
+ this.leaveRate = leaveRate;
+ this.maintRate = maintRate;
+
+ }
+
+ /**
+ * String constructor for script. The values should be in the same
order as
+ * above.
+ */
+ public MBuildTask(String[] s) throws ScriptException {
+ super(Long.parseLong(s[0]));
+
+ // System.err.println(Main.tabbed(s));
+
+ if (s.length < 6)
+ throw new ScriptException("BuildTask requires six
parameters, not "
+ + s.length);
+
+ this.searchRate = Double.parseDouble(s[1]);
+ this.placeRate = Double.parseDouble(s[2]);
+
+ this.poolSize = Long.parseLong(s[3]);
+ this.joinRate = Double.parseDouble(s[4]);
+ this.leaveRate = Double.parseDouble(s[5]);
+ this.maintRate = Double.parseDouble(s[6]);
+
+ // System.err.println(searchRate + " " + placeRate);
+
+ }
+
+ public void started(long time, EventLogger ev) {
+ ev.message(time, "BuildTask Started. Poolsize " + poolSize
+ + " join/leave rate: " + joinRate + "/" +
leaveRate
+ + ". Insert/request rate: " + placeRate + "/" +
searchRate
+ + ". Maintenance rate: " + maintRate);
+ }
+
+ public void done(long time, EventLogger ev) {
+ ev.message(time, "BuildTask Complete. " + tsearches + "
searches ("
+ + ((float) ssearches) / tsearches + " succ, "
+ + ((double) tsearchcost) / tsearches + "
cost)." + tplaces
+ + " places (" + ((float) splaces) / tplaces + "
succ, "
+ + ((double) tplacecost) / tplaces + " cost)." +
tjoin
+ + " joins, " + tleave + " leave," + tmaint
+ + " maintenance tasks.");
+ }
+
+ /**
+ * Calculates the time until a task.
+ */
+ public long timeTillTask(Simulator s) {
+ RandomEngine re = s.random();
+
+ long joinLeft = Math.max(0, poolSize - s.netSize());
+ int netSize = s.netSize();
+
+ double rate = joinLeft * joinRate + netSize
+ * (searchRate + placeRate + leaveRate +
maintRate);
+ // try { Thread.sleep(100); } catch (Exception e) {}
+ // System.err.println("rate: " + rate + " netsize: " + netSize);
+ // Exponentially distributed.
+ return Math.max((long) (Math.log(re.nextDouble()) / (rate *
-1)), 1);
+
+ }
+
+ /**
+ * Calculates the type of task to do after a call to time above.
+ */
+ public int taskType(Simulator s) {
+ RandomEngine re = s.random();
+ long joinLeft = Math.max(0, poolSize - s.netSize());
+ int netSize = s.netSize();
+
+ double joinP = joinLeft * joinRate;
+ double leaveP = netSize * leaveRate;
+ double searchP = netSize * searchRate;
+ double placeP = netSize * placeRate;
+ double maintP = netSize * maintRate;
+
+ double norm = joinP + searchP + placeP + maintP + leaveP;
+ double val = re.nextDouble() * norm;
+
+ if (val <= joinP) {
+ return JOIN;
+ } else if (val <= searchP + joinP) {
+ return SEARCH;
+ } else if (val <= searchP + joinP + placeP) {
+ return PLACE;
+ } else if (val <= searchP + joinP + placeP + maintP) {
+ return MAINTENANCE;
+ } else {
+ return LEAVE;
+ }
+ }
+
+ public void feedback(int task, boolean success, double[] costarr) {
+ int cost = (int) costarr[0];
+
+ if (task == SEARCH) {
+ tsearches++;
+ ssearches += success ? 1 : 0;
+ tsearchcost += cost;
+ } else if (task == PLACE) {
+ tplaces++;
+ splaces += success ? 1 : 0;
+ tplacecost += cost;
+ } else if (task == MAINTENANCE) {
+ tmaint++;
+ tmaintcost += cost;
+ } else if (task == LEAVE) {
+ tleave++;
+ } else if (task == JOIN) {
+ tjoin++;
+ }
+ }
+
+}
Added: trunk/apps/simsalabim/MJoinTask.java
===================================================================
--- trunk/apps/simsalabim/MJoinTask.java (rev 0)
+++ trunk/apps/simsalabim/MJoinTask.java 2009-02-11 13:53:49 UTC (rev
25585)
@@ -0,0 +1,78 @@
+package simsalabim;
+
+/**
+ * Has a node join at a given rate, with maintenance procedure inbetween.
+ */
+
+public class MJoinTask extends RunTask {
+
+ private double joinRate;
+
+ private double mRate;
+
+ private long tjoins = 0;
+
+ private long tjoincost = 0;
+
+ private long tmaint = 0;
+
+ private long tmaintcost = 0;
+
+ public MJoinTask(long runTill, double joinRate, double mRate) {
+ super(runTill);
+
+ this.joinRate = joinRate;
+ this.mRate = mRate;
+ }
+
+ /**
+ * String constructor for script. The values should be in the same
order as
+ * above.
+ */
+ public MJoinTask(String[] s) throws ScriptException {
+ super(Long.parseLong(s[0]));
+
+ if (s.length < 2)
+ throw new ScriptException("JoinTask requires two
parameters, not "
+ + s.length);
+ this.joinRate = Double.parseDouble(s[1]);
+ this.mRate = Double.parseDouble(s[2]);
+ }
+
+ public void done(long time, EventLogger ev) {
+ ev.message(time, "MJoinTask Complete. " + tjoins + " joins ("
+ + ((float) tjoincost) / tjoins + " cost)." +
tmaint
+ + " maintenance.");
+ }
+
+ /**
+ * Calculates the time until a task.
+ */
+ public long timeTillTask(RandomEngine re) {
+ return Math.max(
+ (long) (Math.log(re.nextDouble()) / ((joinRate
+ mRate) * -1)),
+ 1);
+
+ }
+
+ /**
+ * Calculates the type of task to do after a call to time above.
+ */
+ public int taskType(RandomEngine re) {
+ return re.nextDouble() < (joinRate / (joinRate + mRate)) ? JOIN
+ : MAINTENANCE;
+ }
+
+ public void feedback(int task, boolean success, double[] costarr) {
+ int cost = (int) costarr[0];
+
+ if (task == JOIN) {
+ tjoins++;
+ tjoincost += cost;
+ } else if (task == MAINTENANCE) {
+ tmaint++;
+ tmaintcost += cost;
+ }
+ }
+
+}
Added: trunk/apps/simsalabim/Main.java
===================================================================
--- trunk/apps/simsalabim/Main.java (rev 0)
+++ trunk/apps/simsalabim/Main.java 2009-02-11 13:53:49 UTC (rev 25585)
@@ -0,0 +1,93 @@
+package simsalabim;
+
+import java.io.*;
+import java.util.*;
+
+/**
+ * The Main run class. The only arguments needed to run is the name of the
+ * script file, and log file (which may be - ). Optionally a PRNG seed.
+ */
+
+public class Main {
+
+ public static void main(String[] args) {
+ if (args.length < 3) {
+ System.err.println("Usage: simsalabim.Main
<scriptfile> <settings> <logfile> [prng seed]");
+ System.exit(1);
+ }
+
+ int seed;
+ if (args.length > 3)
+ seed = Integer.parseInt(args[3]);
+ else
+ seed = (int) (System.currentTimeMillis() % 100000000l);
+
+ System.err.println("Using PRNG seed: " + seed);
+
+ RandomEngine re = new MersenneTwister(seed);
+
+ Settings st = new Settings(args[1]);
+
+ DataSpace ds = createDataSpace(st);
+
+ Script sc;
+ Simulator sim;
+ PrintWriter out;
+
+ try {
+ BufferedReader br = new BufferedReader(new
FileReader(args[0]));
+ sc = new Script(br);
+ if (args[1].equals("-"))
+ out = new PrintWriter(new
OutputStreamWriter(System.out));
+ else
+ out = new PrintWriter(new FileWriter(args[2]));
+ EventLogger ev = new StringEventLogger(out);
+
+ sim = sc.makeSim(re, ds, st, ev);
+
+ long rtime = System.currentTimeMillis();
+
+ ScriptCommand scom;
+ while ((scom = sc.nextCommand()) != null) {
+ System.err.println("Executing command: " +
scom);
+ scom.execute(sim);
+ }
+
+ System.err.println("Simulation ran in: "
+ + (System.currentTimeMillis() - rtime)
+ " ms.");
+
+ } catch (IOException e) {
+ System.err.println("IO Error reading script: " + e);
+ System.exit(1);
+ return; // for compiler
+ } catch (ScriptException e) {
+ System.err.println("Error in script: " +
e.getMessage());
+ System.exit(1);
+ return; // for compiler
+ }
+
+ out.println(sim.info());
+ out.println(ds.info());
+
+ out.flush();
+ out.close();
+ }
+
+ private static DataSpace createDataSpace(Settings st) {
+ String name = st.get("dsType", "PopularityDataSpace");
+ if (name.equals("LimitedDataSpace")) {
+ return new LimitedDataSpace(st.getInt("dsMaxDocs",
10000), st.getInt(
+ "dsMinSize", 1000),
st.getInt("dsMaxSize", 2000));
+ /* /* */
+
+ } else if (name.equals("PopularityDataSpace")) {
+ return new PopularityDataSpace(st.getInt("dsMaxDocs",
10000), st
+ .getDouble("dsPopDecay", 1.0),
+ st.getInt("dsMinSize", 1000),
st.getInt("dsMaxSize", 2000));
+ } else {
+ throw new SimulationException("DataSpace type " + name
+ + " unknown.");
+ }
+ }
+
+}
Added: trunk/apps/simsalabim/MersenneTwister.java
===================================================================
--- trunk/apps/simsalabim/MersenneTwister.java (rev 0)
+++ trunk/apps/simsalabim/MersenneTwister.java 2009-02-11 13:53:49 UTC (rev
25585)
@@ -0,0 +1,329 @@
+/*
+ Copyright 1999 CERN - European Organization for Nuclear Research.
+ Permission to use, copy, modify, distribute and sell this software and its
documentation for any purpose
+ is hereby granted without fee, provided that the above copyright notice
appear in all copies and
+ that both that copyright notice and this permission notice appear in
supporting documentation.
+ CERN makes no representations about the suitability of this software for any
purpose.
+ It is provided "as is" without expressed or implied warranty.
+ */
+// Modified for Simsalabim by oskar
+package simsalabim;
+
+import java.util.*;
+
+/**
+ * MersenneTwister (MT19937) is one of the strongest uniform pseudo-random
+ * number generators known so far; at the same time it is quick. Produces
+ * uniformly distributed <tt>int</tt>'s and <tt>long</tt>'s in the closed
+ * intervals <tt>[Integer.MIN_VALUE,Integer.MAX_VALUE]</tt> and
+ * <tt>[Long.MIN_VALUE,Long.MAX_VALUE]</tt>, respectively, as well as
+ * <tt>float</tt>'s and <tt>double</tt>'s in the open unit intervals
+ * <tt>(0.0f,1.0f)</tt> and <tt>(0.0,1.0)</tt>, respectively. The seed can
+ * be any 32-bit integer except <tt>0</tt>. Shawn J. Cokus commented that
+ * perhaps the seed should preferably be odd.
+ * <p>
+ * <b>Quality:</b> MersenneTwister is designed to pass the k-distribution test.
+ * It has an astronomically large period of 2<sup>19937</sup>-1
(=10<sup>6001</sup>)
+ * and 623-dimensional equidistribution up to 32-bit accuracy. It passes many
+ * stringent statistical tests, including the <A
+ * HREF="http://stat.fsu.edu/~geo/diehard.html";>diehard</A> test of G.
+ * Marsaglia and the load test of P. Hellekalek and S. Wegenkittl.
+ * <p>
+ * <b>Performance:</b> Its speed is comparable to other modern generators (in
+ * particular, as fast as <tt>java.util.Random.nextFloat()</tt>). 2.5 million
+ * calls to <tt>raw()</tt> per second (Pentium Pro 200 Mhz, JDK 1.2, NT). Be
+ * aware, however, that there is a non-negligible amount of overhead required
to
+ * initialize the data structures used by a MersenneTwister. Code like
+ *
+ * <pre>
+ * double sum = 0.0;
+ * for (int i = 0; i < 100000; ++i) {
+ * RandomElement twister = new MersenneTwister(new java.util.Date());
+ * sum += twister.raw();
+ * }
+ * </pre>
+ *
+ * will be wildly inefficient. Consider using
+ *
+ * <pre>
+ * double sum = 0.0;
+ * RandomElement twister = new MersenneTwister(new java.util.Date());
+ * for (int i = 0; i < 100000; ++i) {
+ * sum += twister.raw();
+ * }
+ * </pre>
+ *
+ * instead. This allows the cost of constructing the MersenneTwister object to
+ * be borne only once, rather than once for each iteration in the loop.
+ * <p>
+ * <b>Implementation:</b> After M. Matsumoto and T. Nishimura, "Mersenne
+ * Twister: A 623-Dimensionally Equidistributed Uniform Pseudo-Random Number
+ * Generator", ACM Transactions on Modeling and Computer Simulation, Vol. 8,
No.
+ * 1, January 1998, pp 3--30.
+ * <dt>More info on <A HREF="http://www.math.keio.ac.jp/~matumoto/eindex.html";>
+ * Masumoto's homepage</A>.
+ * <dt>More info on <A
+ * HREF="http://www.ncsa.uiuc.edu/Apps/CMP/RNG/www-rng.html";> Pseudo-random
+ * number generators is on the Web</A>.
+ * <dt>Yet <A HREF="http://nhse.npac.syr.edu/random";> some more info</A>.
+ * <p>
+ * The correctness of this implementation has been verified against the
+ * published output sequence <a
+ *
href="http://www.math.keio.ac.jp/~nisimura/random/real2/mt19937-2.out";>mt19937-2.out</a>
+ * of the C-implementation <a
+ *
href="http://www.math.keio.ac.jp/~nisimura/random/real2/mt19937-2.c";>mt19937-2.c</a>.
+ * (Call <tt>test(1000)</tt> to print the sequence).
+ * <dt> Note that this implementation is <b>not synchronized</b>.
+ * <p>
+ * <b>Details:</b> MersenneTwister is designed with consideration of the flaws
+ * of various existing generators in mind. It is an improved version of TT800,
a
+ * very successful generator. MersenneTwister is based on linear recurrences
+ * modulo 2. Such generators are very fast, have extremely long periods, and
+ * appear quite robust. MersenneTwister produces 32-bit numbers, and every
+ * <tt>k</tt>-dimensional vector of such numbers appears the same number of
+ * times as <tt>k</tt> successive values over the period length, for each
+ * <tt>k <= 623</tt> (except for the zero vector, which appears one time
+ * less). If one looks at only the first <tt>n <= 16</tt> bits of each
+ * number, then the property holds for even larger <tt>k</tt>, as shown in
+ * the following table (taken from the publication cited above): <div
+ * align="center"> <table width="75%" border="1" cellspacing="0"
+ * cellpadding="0">
+ * <tr>
+ * <td width="2%"> <div align="center">n</div> </td>
+ * <td width="6%"> <div align="center">1</div> </td>
+ * <td width="5%"> <div align="center">2</div> </td>
+ * <td width="5%"> <div align="center">3</div> </td>
+ * <td width="5%"> <div align="center">4</div> </td>
+ * <td width="5%"> <div align="center">5</div> </td>
+ * <td width="5%"> <div align="center">6</div> </td>
+ * <td width="5%"> <div align="center">7</div> </td>
+ * <td width="5%"> <div align="center">8</div> </td>
+ * <td width="5%"> <div align="center">9</div> </td>
+ * <td width="5%"> <div align="center">10</div> </td>
+ * <td width="5%"> <div align="center">11</div> </td>
+ * <td width="10%"> <div align="center">12 .. 16</div> </td>
+ * <td width="10%"> <div align="center">17 .. 32</div> </td>
+ * </tr>
+ * <tr>
+ * <td width="2%"> <div align="center">k</div> </td>
+ * <td width="6%"> <div align="center">19937</div> </td>
+ * <td width="5%"> <div align="center">9968</div> </td>
+ * <td width="5%"> <div align="center">6240</div> </td>
+ * <td width="5%"> <div align="center">4984</div> </td>
+ * <td width="5%"> <div align="center">3738</div> </td>
+ * <td width="5%"> <div align="center">3115</div> </td>
+ * <td width="5%"> <div align="center">2493</div> </td>
+ * <td width="5%"> <div align="center">2492</div> </td>
+ * <td width="5%"> <div align="center">1869</div> </td>
+ * <td width="5%"> <div align="center">1869</div> </td>
+ * <td width="5%"> <div align="center">1248</div> </td>
+ * <td width="10%"> <div align="center">1246</div> </td>
+ * <td width="10%"> <div align="center">623</div> </td>
+ * </tr>
+ * </table> </div>
+ * <p>
+ * MersenneTwister generates random numbers in batches of 624 numbers at a
time,
+ * so the caching and pipelining of modern systems is exploited. The generator
+ * is implemented to generate the output by using the fastest arithmetic
+ * operations only: 32-bit additions and bit operations (no division, no
+ * multiplication, no mod). These operations generate sequences of 32 random
+ * bits (<tt>int</tt>'s). <tt>long</tt>'s are formed by concatenating two
+ * 32 bit <tt>int</tt>'s. <tt>float</tt>'s are formed by dividing the
+ * interval <tt>[0.0,1.0]</tt> into 2<sup>32</sup> sub intervals, then
+ * randomly choosing one subinterval. <tt>double</tt>'s are formed by
+ * dividing the interval <tt>[0.0,1.0]</tt> into 2<sup>64</sup> sub
+ * intervals, then randomly choosing one subinterval.
+ * <p>
+ *
+ * @author wolfgang.hoschek at cern.ch
+ * @version 1.0, 09/24/99
+ * @see edu.cornell.lassp.houle.RngPack.Ranmar
+ * @see edu.cornell.lassp.houle.RngPack.Ranlux
+ * @see edu.cornell.lassp.houle.RngPack.Ranecu
+ * @see java.util.Random
+ */
+public class MersenneTwister extends RandomEngine {
+
+ public static void main(String[] agrs) {
+ MersenneTwister mt = new MersenneTwister();
+
+ for (int i = 0; i < 100; i++) {
+ System.err.println(mt.choose(2));
+ }
+ }
+
+ private int mti;
+
+ private int[] mt = new int[N]; /* set initial seeds: N = 624 words */
+
+ /* Period parameters */
+ private static final int N = 624;
+
+ private static final int M = 397;
+
+ private static final int MATRIX_A = 0x9908b0df; /* constant vector a */
+
+ private static final int UPPER_MASK = 0x80000000; /*
+
* most significant w-r
+
* bits
+
*/
+
+ private static final int LOWER_MASK = 0x7fffffff; /*
+
* least significant r
+
* bits
+
*/
+
+ /* for tempering */
+ private static final int TEMPERING_MASK_B = 0x9d2c5680;
+
+ private static final int TEMPERING_MASK_C = 0xefc60000;
+
+ private static final int mag0 = 0x0;
+
+ private static final int mag1 = MATRIX_A;
+
+ // private static final int[] mag01=new int[] {0x0, MATRIX_A};
+ /* mag01[x] = x * MATRIX_A for x=0,1 */
+
+ public static final int DEFAULT_SEED = 4357;
+
+ /**
+ * Constructs and returns a random number generator with a default seed,
+ * which is a <b>constant</b>. Thus using this constructor will yield
+ * generators that always produce exactly the same sequence. This
method is
+ * mainly intended to ease testing and debugging.
+ */
+ public MersenneTwister() {
+ this(DEFAULT_SEED);
+ }
+
+ /**
+ * Constructs and returns a random number generator with the given seed.
+ *
+ * @param seed
+ * should not be 0, in such a case
+ * <tt>MersenneTwister.DEFAULT_SEED</tt> is silently
+ * substituted.
+ */
+ public MersenneTwister(int seed) {
+ setSeed(seed);
+ }
+
+ /**
+ * Constructs and returns a random number generator seeded with the
given
+ * date.
+ *
+ * @param d
+ * typically <tt>new java.util.Date()</tt>
+ */
+ public MersenneTwister(Date d) {
+ this((int) ClockSeed(d));
+ }
+
+ /**
+ * Returns a copy of the receiver; the copy will produce identical
+ * sequences. After this call has returned, the copy and the receiver
have
+ * equal but separate state.
+ *
+ * @return a copy of the receiver.
+ */
+ public Object clone() throws CloneNotSupportedException {
+ MersenneTwister clone = (MersenneTwister) super.clone();
+ clone.mt = (int[]) this.mt.clone();
+ return clone;
+ }
+
+ /**
+ * Generates N words at one time.
+ */
+ protected void nextBlock() {
+ /*
+ * // ******************** OPTIMIZED ********************** //
only
+ * 5-10% faster ? int y;
+ *
+ * int kk; int[] cache = mt; // cached for speed int kkM; int
limit =
+ * N-M; for (kk=0,kkM=kk+M; kk<limit; kk++,kkM++) { y =
+ * (cache[kk]&UPPER_MASK)|(cache[kk+1]&LOWER_MASK); cache[kk] =
+ * cache[kkM] ^ (y >>> 1) ^ ((y & 0x1) == 0 ? mag0 : mag1); }
limit =
+ * N-1; for (kkM=kk+(M-N); kk<limit; kk++,kkM++) { y =
+ * (cache[kk]&UPPER_MASK)|(cache[kk+1]&LOWER_MASK); cache[kk] =
+ * cache[kkM] ^ (y >>> 1) ^ ((y & 0x1) == 0 ? mag0 : mag1); } y
=
+ * (cache[N-1]&UPPER_MASK)|(cache[0]&LOWER_MASK); cache[N-1] =
+ * cache[M-1] ^ (y >>> 1) ^ ((y & 0x1) == 0 ? mag0 : mag1);
+ *
+ * this.mt = cache; this.mti = 0;
+ */
+
+ // ******************** UNOPTIMIZED **********************
+ int y;
+
+ int kk;
+
+ for (kk = 0; kk < N - M; kk++) {
+ y = (mt[kk] & UPPER_MASK) | (mt[kk + 1] & LOWER_MASK);
+ mt[kk] = mt[kk + M] ^ (y >>> 1) ^ ((y & 0x1) == 0 ?
mag0 : mag1);
+ }
+ for (; kk < N - 1; kk++) {
+ y = (mt[kk] & UPPER_MASK) | (mt[kk + 1] & LOWER_MASK);
+ mt[kk] = mt[kk + (M - N)] ^ (y >>> 1)
+ ^ ((y & 0x1) == 0 ? mag0 : mag1);
+ }
+ y = (mt[N - 1] & UPPER_MASK) | (mt[0] & LOWER_MASK);
+ mt[N - 1] = mt[M - 1] ^ (y >>> 1) ^ ((y & 0x1) == 0 ? mag0 :
mag1);
+
+ this.mti = 0;
+
+ }
+
+ /**
+ * Returns a 32 bit uniformly distributed random number in the closed
+ * interval <tt>[Integer.MIN_VALUE,Integer.MAX_VALUE]</tt> (including
+ * <tt>Integer.MIN_VALUE</tt> and <tt>Integer.MAX_VALUE</tt>).
+ */
+ public int nextInt() {
+ /* Each single bit including the sign bit will be random */
+ if (mti == N)
+ nextBlock(); // generate N ints at one time
+
+ int y = mt[mti++];
+ y ^= y >>> 11; // y ^= TEMPERING_SHIFT_U(y );
+ y ^= (y << 7) & TEMPERING_MASK_B; // y ^= TEMPERING_SHIFT_S(y) &
+
// TEMPERING_MASK_B;
+ y ^= (y << 15) & TEMPERING_MASK_C; // y ^= TEMPERING_SHIFT_T(y)
&
+
// TEMPERING_MASK_C;
+ // y &= 0xffffffff; //you may delete this line if word size = 32
+ y ^= y >>> 18; // y ^= TEMPERING_SHIFT_L(y);
+
+ return y;
+ }
+
+ /**
+ * Sets the receiver's seed. This method resets the receiver's entire
+ * internal state.
+ *
+ * @param seed
+ * should not be 0, in such a case
+ * <tt>MersenneTwister.DEFAULT_SEED</tt> is substituted.
+ */
+ protected void setSeed(int seed) {
+ if (seed == 0) {
+ setSeed(DEFAULT_SEED);
+ return;
+ }
+
+ /*
+ * setting initial seeds to mt[N] using the generator Line 25
of Table 1
+ * in [KNUTH 1981, The Art of Computer Programming Vol. 2 (2nd
Ed.),
+ * pp102]
+ */
+
+ this.mt[0] = seed & 0xffffffff;
+ for (mti = 1; mti < N; mti++) {
+ // if (mti<10) System.out.println(mt[mti-1] +":"+ 69069
* mt[mti-1]
+ // +":"+ ((69069 * mt[mti-1]) & 0xffffffff));
+ this.mt[mti] = (69069 * this.mt[mti - 1]) & 0xffffffff;
+ }
+ // System.out.println("init done");
+
+ }
+}
Added: trunk/apps/simsalabim/Node.java
===================================================================
--- trunk/apps/simsalabim/Node.java (rev 0)
+++ trunk/apps/simsalabim/Node.java 2009-02-11 13:53:49 UTC (rev 25585)
@@ -0,0 +1,110 @@
+package simsalabim;
+
+
+public abstract class Node<S extends Simulator, K extends Key> implements
InfoObject {
+
+ protected final S god;
+ protected final int num;
+
+ private boolean active;
+ private int currentNumber;
+
+ protected long lastActivatedTime = -1;
+ protected long lastDeactivatedTime = -1;
+
+ public Node(S god, int num) {
+ this.god = god;
+ this.num = num;
+ }
+
+ public int num() {
+ return num;
+ }
+
+ /**
+ * Returns the simulator to which this node belongs.
+ */
+ public S sim() {
+ return god;
+ }
+
+ /**
+ * Returns the time from this nodes simulator.
+ */
+ public long time() {
+ return god.time();
+ }
+
+
+ public String toString() {
+ return "N/#" + num + "/";
+ }
+
+ public void activate() {
+ active = true;
+ lastActivatedTime = god.time();
+ activated();
+ }
+
+ public void deactivate() {
+ active = false;
+ lastDeactivatedTime = god.time();
+ deactivated();
+ }
+
+ public boolean isActive() {
+ return active;
+ }
+
+ /**
+ * Called when the node is activated. Default does nothing.
+ *
+ */
+ protected void activated() {
+ }
+
+ /**
+ * Called when the node is deactivated. Default does nothing.
+ *
+ */
+ protected void deactivated() {
+ }
+
+ public abstract Data findData(K k);
+
+ public abstract void storeData(Data<K> d, boolean nonvolatile);
+
+ public abstract int nKeys();
+
+ /**
+ * The bottom implementation feeds an agg. called "NodeNumbers" with...
+ */
+ public void feedAggregator(DataAggregator da) {
+ if (da.name().equals("NodeNumbers")) {
+ da.next(num);
+ }
+ }
+
+ /**
+ * Used by simulator to keep track of where the node is the in the
array. Do
+ * not call.
+ *
+ * @param n
+ * The current place.
+ */
+ final void setCurrentNumber(int n) {
+ currentNumber = n;
+ }
+
+ /**
+ * Used by simulator to keep track of where the node is the in the
array. Do
+ * not call.
+ *
+ * @return The current place.
+ */
+ final int getCurrentNumber() {
+ return currentNumber;
+ }
+
+
+}
Added: trunk/apps/simsalabim/Person.java
===================================================================
--- trunk/apps/simsalabim/Person.java (rev 0)
+++ trunk/apps/simsalabim/Person.java 2009-02-11 13:53:49 UTC (rev 25585)
@@ -0,0 +1,102 @@
+package simsalabim;
+import java.util.*;
+
+ /**
+ * Class for a node in social network.
+ */
+class Person implements Comparable<Person> {
+
+ public LinkedList<Person> outN = new LinkedList<Person>();
+ public int id;
+ private boolean does_darknet = false;
+ private boolean does_opennet = false;
+
+ public int netid = 0; // Network partition
+ public int score = 0;
+ private DarknetNode node;
+
+ public Person(int id) {
+ this.id = id;
+ }
+
+ public Iterator<Person> neighbors() {
+ return outN.iterator();
+ }
+
+ public boolean isOpennet() {
+ if (!does_darknet && !does_opennet) throw new SimulationException
("Node " + this + " without type.");
+ return does_opennet;
+ }
+
+ public boolean isDarknet() {
+ if (!does_darknet && !does_opennet) throw new SimulationException
("Node " + this + " without type.");
+ return does_darknet;
+ }
+
+ public int degree() {
+ return outN.size();
+ }
+
+ public int network() {
+ return netid;
+ }
+
+ public void setNetwork(int id) {
+ netid = id;
+ }
+
+ public void setDarknet() {
+ does_darknet = true;
+ }
+
+ public void setOpennet() {
+ does_opennet = true;
+ }
+
+ public void joinedNetwork(DarknetNode node) {
+ this.node = node;
+ }
+
+ public void leftNetwork() {
+ this.node = null;
+ }
+
+ public boolean isInNetwork() {
+ return node != null;
+ }
+
+ public DarknetNode getNode() {
+ return node;
+ }
+
+ public void addOut(Person n) {
+ if (!outN.contains(n))
+ outN.add(n);
+ }
+
+ public boolean linksTo(Person n) {
+ return outN.contains(n);
+ }
+
+ public void removeNeighbor(Person n) {
+ outN.remove(n);
+ }
+
+
+ public int compareTo(Person o) {
+ return ( score > o.score ?
+ 1 :
+ ( score < o.score ?
+ -1 :
+ ( id > o.id ?
+ 1:
+ ( id < o.id ?
+ -1:
+ 0))));
+ }
+
+ public boolean equals(Object o) {
+ return ((Person) o).id == id && ((Person) o).score == score;
+ }
+
+}
Added: trunk/apps/simsalabim/PopularityDataSpace.java
===================================================================
--- trunk/apps/simsalabim/PopularityDataSpace.java
(rev 0)
+++ trunk/apps/simsalabim/PopularityDataSpace.java 2009-02-11 13:53:49 UTC
(rev 25585)
@@ -0,0 +1,113 @@
+package simsalabim;
+
+import java.util.*;
+
+public class PopularityDataSpace<K extends Key> implements DataSpace<K> {
+
+ private ArrayList<Data<K>> data;
+ private HashMap<K, Data<K>> datamap;
+ private double popDecay;
+ private int currSize;
+ private int maxSize;
+
+ private int minDataSize;
+ private int dataSizeRange;
+
+ public PopularityDataSpace(int size, double popDecay, int minSize, int
maxSize) {
+ data = new ArrayList<Data<K>>(size);
+ datamap = new HashMap<K, Data<K>>();
+ this.popDecay = popDecay;
+ this.currSize = 0;
+ this.maxSize = size;
+ this.minDataSize = minSize;
+ this.dataSizeRange = maxSize - minSize;
+ }
+
+ public Iterator<Data<K>> allData() {
+ return data.iterator();
+ }
+
+ public K chooseKey(RandomEngine re) {
+ return currSize == 0 ? null : data.get(getIndex(re)).key();
+ }
+
+ public Data<K> getData(K key) {
+ return datamap.get(key);
+ }
+
+ public String info() {
+ return "PopularityDataSpace docs: " + data.size() + " (of " +
maxSize + ")";
+ }
+
+ /**
+ * Keep min(currSize,maxSize) documents available for search
+ */
+
+ public Data<K> newData(Simulator god, K key) {
+ long datasize = minDataSize + (long) (god.random().nextDouble()
* dataSizeRange);
+ Data<K> d = new Data<K>(god, key, datasize);
+
+ if (currSize < maxSize) {
+ data.add(d);
+ datamap.put(key,d);
+ currSize++;
+ return d;
+ } else {
+ int idx = god.re.nextInt(maxSize);
+ moveDown(idx, god.re,god.time());
+ data.set(idx,d);
+ datamap.put(key, d);
+ return d;
+ }
+ }
+
+ public int size() {
+ return currSize;
+ }
+
+ /**
+ * Sample from the specified popularity (Zipf) distribution
+ */
+
+ private int getIndex(RandomEngine re) {
+
+ // Uniform
+ if (popDecay == 0)
+ return re.nextInt(currSize);
+
+ // Easy distribution
+ if (popDecay > 0.99 && popDecay < 1.01)
+ return (int) Math.pow(currSize + 1, re.nextDouble()) -
1;
+
+ // General case
+ double zsum = 0;
+ for (int i=1; i < currSize; i++) {
+ zsum += (1/Math.pow(i,popDecay));
+ }
+ double r = re.nextDouble();
+ double z = 0;
+ int x = 0;
+
+ while (r > (z/zsum)) {
+ z += 1/Math.pow(++x,popDecay);
+ }
+
+ return x;
+ }
+
+ private void moveDown(int n, RandomEngine re, long time) {
+ moveDown(n, re.nextInt(maxSize) + 1, data.get(n), time);
+ }
+
+ private void moveDown(int n, int m, Data<K> d, long time) {
+ if ((n + m) >= maxSize) {
+ datamap.remove(d.key());
+ d.forgotten(time);
+ } else {
+ Data<K> md = data.get(n + m);
+ data.set(n+m,d);
+ moveDown(n+m,2*m, md, time);
+ }
+ }
+
+}
Added: trunk/apps/simsalabim/PositionKey.java
===================================================================
--- trunk/apps/simsalabim/PositionKey.java (rev 0)
+++ trunk/apps/simsalabim/PositionKey.java 2009-02-11 13:53:49 UTC (rev
25585)
@@ -0,0 +1,13 @@
+package simsalabim;
+/**
+ * A key which represents a position in a circular [0,1] keyspace
+ *
+ * @author ossa
+ *
+ */
+
+public abstract class PositionKey<K extends PositionKey> implements Key {
+
+ public abstract double dist(K pk);
+
+}
Added: trunk/apps/simsalabim/RandomEngine.java
===================================================================
--- trunk/apps/simsalabim/RandomEngine.java (rev 0)
+++ trunk/apps/simsalabim/RandomEngine.java 2009-02-11 13:53:49 UTC (rev
25585)
@@ -0,0 +1,224 @@
+/*
+ Copyright 1999 CERN - European Organization for Nuclear Research.
+ Permission to use, copy, modify, distribute and sell this software and its
documentation for any purpose
+ is hereby granted without fee, provided that the above copyright notice
appear in all copies and
+ that both that copyright notice and this permission notice appear in
supporting documentation.
+ CERN makes no representations about the suitability of this software for any
purpose.
+ It is provided "as is" without expressed or implied warranty.
+ */
+// Modified for Simsalabim by Oskar
+package simsalabim;
+
+import java.util.*;
+
+/**
+ * Abstract base class for uniform pseudo-random number generating engines.
+ * <p>
+ * Most probability distributions are obtained by using a <b>uniform</b>
+ * pseudo-random number generation engine (derived from this class or
+ * {@link edu.cornell.lassp.houle.RngPack.RandomElement}) followed by a
+ * transformation to the desired distribution. Thus, subclasses of this class
+ * are at the core of computational statistics, simulations, Monte Carlo
+ * methods, etc.
+ * <p>
+ * Subclasses produce uniformly distributed <tt>int</tt>'s and <tt>long</tt>'s
+ * in the closed intervals <tt>[Integer.MIN_VALUE,Integer.MAX_VALUE]</tt> and
+ * <tt>[Long.MIN_VALUE,Long.MAX_VALUE]</tt>, respectively, as well as
+ * <tt>float</tt>'s and <tt>double</tt>'s in the open unit intervals
+ * <tt>(0.0f,1.0f)</tt> and <tt>(0.0,1.0)</tt>, respectively.
+ * <p>
+ * Subclasses need to override one single method only: <tt>nextInt()</tt>.
+ * All other methods generating different data types or ranges are usually
+ * layered upon <tt>nextInt()</tt>. <tt>long</tt>'s are formed by
+ * concatenating two 32 bit <tt>int</tt>'s. <tt>float</tt>'s are formed by
+ * dividing the interval <tt>[0.0f,1.0f]</tt> into 2<sup>32</sup> sub
+ * intervals, then randomly choosing one subinterval. <tt>double</tt>'s are
+ * formed by dividing the interval <tt>[0.0,1.0]</tt> into 2<sup>64</sup>
+ * sub intervals, then randomly choosing one subinterval.
+ * <p>
+ * Note that this implementation is <b>not synchronized</b>.
+ *
+ * @author wolfgang.hoschek at cern.ch
+ * @version 1.0, 09/24/99
+ * @see MersenneTwister
+ * @see MersenneTwister64
+ * @see edu.cornell.lassp.houle.RngPack.Ranmar
+ * @see edu.cornell.lassp.houle.RngPack.Ranlux
+ * @see edu.cornell.lassp.houle.RngPack.Ranecu
+ * @see java.util.Random
+ */
+public abstract class RandomEngine {
+ // extends edu.cornell.lassp.houle.RngPack.RandomSeedable implements
+ // cern.colt.function.DoubleFunction, cern.colt.function.IntFunction {
+ /**
+ * Makes this class non instantiable, but still let's others inherit
from
+ * it.
+ */
+ protected RandomEngine() {
+ }
+
+ /**
+ * Equivalent to <tt>raw()</tt>. This has the effect that random engines
+ * can now be used as function objects, returning a random number upon
+ * function evaluation.
+ */
+ public double apply(double dummy) {
+ return raw();
+ }
+
+ /**
+ * Equivalent to <tt>nextInt()</tt>. This has the effect that random
+ * engines can now be used as function objects, returning a random
number
+ * upon function evaluation.
+ */
+ public int apply(int dummy) {
+ return nextInt();
+ }
+
+ /**
+ * Returns a 64 bit uniformly distributed random number in the open unit
+ * interval <code>(0.0,1.0)</code> (excluding 0.0 and 1.0).
+ */
+ public double nextDouble() {
+ double nextDouble;
+
+ do {
+ // -9.223372036854776E18 == (double) Long.MIN_VALUE
+ // 5.421010862427522E-20 == 1 / Math.pow(2,64) == 1 /
((double)
+ // Long.MAX_VALUE - (double) Long.MIN_VALUE);
+ nextDouble = ((double) nextLong() -
-9.223372036854776E18) * 5.421010862427522E-20;
+ }
+ // catch loss of precision of long --> double conversion
+ while (!(nextDouble > 0.0 && nextDouble < 1.0));
+
+ // --> in (0.0,1.0)
+ return nextDouble;
+
+ /*
+ * nextLong == Long.MAX_VALUE --> 1.0 nextLong ==
Long.MIN_VALUE --> 0.0
+ * nextLong == Long.MAX_VALUE-1 --> 1.0 nextLong ==
+ * Long.MAX_VALUE-100000L --> 0.9999999999999946 nextLong ==
+ * Long.MIN_VALUE+1 --> 0.0 nextLong == Long.MIN_VALUE-100000L
-->
+ * 0.9999999999999946 nextLong == 1L --> 0.5 nextLong == -1L
--> 0.5
+ * nextLong == 2L --> 0.5 nextLong == -2L --> 0.5 nextLong ==
2L+100000L
+ * --> 0.5000000000000054 nextLong == -2L-100000L -->
+ * 0.49999999999999456
+ */
+ }
+
+ /**
+ * Returns a 32 bit uniformly distributed random number in the open unit
+ * interval <code>(0.0f,1.0f)</code> (excluding 0.0f and 1.0f).
+ */
+ public float nextFloat() {
+ // catch loss of precision of double --> float conversion
+ float nextFloat;
+ do {
+ nextFloat = (float) raw();
+ } while (nextFloat >= 1.0f);
+
+ // --> in (0.0f,1.0f)
+ return nextFloat;
+ }
+
+ /**
+ * Returns a 32 bit uniformly distributed random number in the closed
+ * interval <tt>[Integer.MIN_VALUE,Integer.MAX_VALUE]</tt> (including
+ * <tt>Integer.MIN_VALUE</tt> and <tt>Integer.MAX_VALUE</tt>);
+ */
+ public abstract int nextInt();
+
+ /**
+ * Returns uniform integer between 0 and i-1
+ */
+ public int nextInt(int i) {
+ return choose(0, i - 1);
+ }
+
+ /**
+ * Returns a 64 bit uniformly distributed random number in the closed
+ * interval <tt>[Long.MIN_VALUE,Long.MAX_VALUE]</tt> (including
+ * <tt>Long.MIN_VALUE</tt> and <tt>Long.MAX_VALUE</tt>).
+ */
+ public long nextLong() {
+ // concatenate two 32-bit strings into one 64-bit string
+ return ((nextInt() & 0xFFFFFFFFL) << 32) | ((nextInt() &
0xFFFFFFFFL));
+ }
+
+ /**
+ * Returns a 32 bit uniformly distributed random number in the open unit
+ * interval <code>(0.0,1.0)</code> (excluding 0.0 and 1.0).
+ */
+ public double raw() {
+ int nextInt;
+ do { // accept anything but zero
+ nextInt = nextInt(); // in
+ //
[Integer.MIN_VALUE,Integer.MAX_VALUE]-interval
+ } while (nextInt == 0);
+
+ // transform to (0.0,1.0)-interval
+ // 2.3283064365386963E-10 == 1.0 / Math.pow(2,32)
+ return (double) (nextInt & 0xFFFFFFFFL) *
2.3283064365386963E-10;
+
+ /*
+ * nextInt == Integer.MAX_VALUE --> 0.49999999976716936 nextInt
==
+ * Integer.MIN_VALUE --> 0.5 nextInt == Integer.MAX_VALUE-1 -->
+ * 0.4999999995343387 nextInt == Integer.MIN_VALUE+1 -->
+ * 0.5000000002328306 nextInt == 1 --> 2.3283064365386963E-10
nextInt ==
+ * -1 --> 0.9999999997671694 nextInt == 2 -->
4.6566128730773926E-10
+ * nextInt == -2 --> 0.9999999995343387
+ */
+ }
+
+ /**
+ *
+ * Return a long integer seed calculated from the date. Equivalent to
<CODE>ClockSeed(new
+ * Date());
+ *
+ * @return a long integer seed
+ *
+ */
+
+ public static long ClockSeed() {
+ return ClockSeed(new Date());
+ }
+
+ /**
+ * @param hi
+ * upper limit of range
+ * @return a random integer in the range 1,2,... ,<STRONG>hi</STRONG>
+ */
+ public int choose(int hi) {
+ return choose(1, hi); // _WH_,
+ // return (int) (1+hi*raw()); // does not yield [1,hi]
+ }
+
+ /**
+ * @param lo
+ * lower limit of range
+ * @param hi
+ * upper limit of range
+ * @return a random integer in the range <STRONG>lo</STRONG>,
<STRONG>lo</STRONG>+1,
+ * ... ,<STRONG>hi</STRONG>
+ */
+
+ public int choose(int lo, int hi) {
+ return (int) ((long) lo + (long) ((1L + (long) hi - (long) lo)
* raw())); // _WH_,
+
// March
+
// 12,1999
+ // return (int) (lo+(hi-lo+1)*raw()); // does not yield [lo,hi]
+ }
+
+ /**
+ *
+ * Return a long integer seed given a date
+ *
+ * @param d
+ * a date
+ * @return a long integer seed
+ *
+ */
+ public static long ClockSeed(Date d) {
+ return d.getTime();
+ }
+}
Added: trunk/apps/simsalabim/RunTask.java
===================================================================
--- trunk/apps/simsalabim/RunTask.java (rev 0)
+++ trunk/apps/simsalabim/RunTask.java 2009-02-11 13:53:49 UTC (rev 25585)
@@ -0,0 +1,159 @@
+package simsalabim;
+
+public abstract class RunTask implements ScriptCommand, Feedback {
+
+ private static final String DELIM;
+ static {
+ StringBuffer sb = new StringBuffer("|");
+ for (int i = 0; i < 78; i++)
+ sb.append('-');
+ sb.append('|');
+ DELIM = sb.toString();
+ }
+
+ public static final int JOIN = 0;
+
+ public static final int SEARCH = 1;
+
+ public static final int PLACE = 2;
+
+ public static final int LEAVE = 3;
+
+ public static final int GSEARCH = 4;
+
+ public static final int MAINTENANCE = 5;
+
+ public static final int VERYUGLYHACK = 6;
+
+ public static final int DUALSTATS = 7;
+
+ public long runTill;
+
+ public RunTask(long runTill) {
+ this.runTill = runTill;
+ }
+
+ /**
+ * Calculates the time until a task. Default version calls with
+ * RandomEngine.
+ */
+ public long timeTillTask(Simulator s) {
+ return timeTillTask(s.random());
+ }
+
+ /**
+ * Calculates the type of task to do after a call to time above. Default
+ * version calls with randomEngine
+ */
+ public int taskType(Simulator s) {
+ return taskType(s.random());
+ }
+
+ /**
+ * This or timeTillTask(Simulator) must be overridden. Default throws
error.
+ */
+ protected long timeTillTask(RandomEngine re) {
+ throw new Error("TimeTillTask unimplemented in " +
this.getClass());
+ }
+
+ /**
+ * This or taskType(Simulator) must be overriden. Default throws error.
+ */
+ protected int taskType(RandomEngine re) {
+ throw new Error("taskType unimplemented in " + this.getClass());
+ }
+
+ /**
+ * Called when this is started.
+ */
+ public void started(long time, EventLogger ev) {
+ }
+
+ /**
+ * Called when this has finished running.
+ */
+ public void done(long time, EventLogger ev) {
+ }
+
+ public long runTill() {
+ return runTill;
+ }
+
+ public final void execute(Simulator s) {
+ long runTill = runTill();
+ long startTime = s.time();
+ long runTime = runTill - s.time();
+
+ DataSpace ds = s.dataspace();
+ int ntasks = 0;
+ long realTime = System.currentTimeMillis();
+ System.err.println("Task " + this);
+ System.err.println(DELIM);
+ started(s.time(), s.log());
+ while (s.time() < runTill) {
+ long col = 80 * (s.time() - startTime) / runTime;
+ s.step(timeTillTask(s));
+
+ long ncol = 80 * (s.time() - startTime) / runTime;
+
+ if (ncol > col)
+ System.err.print("+");
+
+ // System.err.println(time);
+
+ if (s.time() >= runTill)
+ break;
+
+ int t = taskType(s);
+ ntasks++;
+
+ if (t == RunTask.JOIN) {
+ // System.err.println("Join! \t");
+ Node n = s.newNode();
+ // if (nodes.isEmpty()) {
+ // nodes.add(n);
+ // } else {
+ boolean r = s.join(n, s.chooseNode(), this);
+ if (r) {
+ s.addNode(n);
+ n.activate();
+ }
+ // }
+ } else if (t == RunTask.SEARCH || t == RunTask.GSEARCH)
{
+ Node n = s.chooseNode();
+ if (n != null) {
+ Key k = s.chooseKey();
+ if (k != null) {
+ Data d = s.search(k, n, t ==
RunTask.GSEARCH, this);
+ if (d != null)
+ d.retrieved();
+ }
+ }
+ } else if (t == RunTask.PLACE) {
+ Node n = s.chooseNode();
+ if (n != null) {
+ Data<Key> d = ds.newData(s, s.newKey());
+
+ s.place(d, n, this);
+ }
+ } else if (t == RunTask.LEAVE) {
+ // System.err.println("Leave! \t");
+ Node n = s.chooseNode();
+ if (n != null) {
+ // Remove from active
+ s.removeNode(n);
+ s.leave(n, this, s.leavePermanent(n));
+ n.deactivate();
+
+ }
+ } else if (t == RunTask.MAINTENANCE) {
+ s.maintenance(this);
+ } else if (t == RunTask.DUALSTATS) {
+ s.dualstats(this);
+ }
+ }
+ System.err.println();
+ System.err.println("Task " + this + " (with " + ntasks + "
attempted tasks) complete in " + (System.currentTimeMillis() - realTime) +
"ms.");
+ done(s.time(), s.log());
+ }
+}
Added: trunk/apps/simsalabim/Script.java
===================================================================
--- trunk/apps/simsalabim/Script.java (rev 0)
+++ trunk/apps/simsalabim/Script.java 2009-02-11 13:53:49 UTC (rev 25585)
@@ -0,0 +1,108 @@
+package simsalabim;
+import java.io.*;
+import java.util.*;
+import java.lang.reflect.*;
+/**
+ * Scripts that run the simulator. Look at script.txt for the format.
+ */
+public class Script {
+
+ private static HashMap<String, ScriptCommandType> commandTypes = new
HashMap<String, ScriptCommandType>();
+
+ static {
+ commandTypes.put("BuildTask",new
ScriptCommandType("BuildTask"));
+ commandTypes.put("JoinTask",new ScriptCommandType("JoinTask"));
+ commandTypes.put("BlaTask",new ScriptCommandType("BlaTask"));
+ commandTypes.put("NodeAggregate", new AggregateCommand.Type());
+ commandTypes.put("MJoinTask", new
ScriptCommandType("MJoinTask"));
+ commandTypes.put("MBuildTask", new
ScriptCommandType("MBuildTask"));
+ commandTypes.put("InfoCommand", new
ScriptCommandType("InfoCommand"));
+ commandTypes.put("HJoinTask", new
ScriptCommandType("HJoinTask"));
+ commandTypes.put("HBuildTask", new
ScriptCommandType("HBuildTask"));
+ commandTypes.put("HDualStats", new
ScriptCommandType("HDualStats"));
+ }
+
+ private Class simClass;
+ private String simArgs;
+
+ private LinkedList<ScriptCommand> cqueue = new
LinkedList<ScriptCommand>();
+
+ public Script(BufferedReader br) throws IOException, ScriptException {
+ this(readcmds(br));
+ }
+
+
+ public Script(String[] cmds) throws ScriptException {
+ if (cmds.length < 2)
+ throw new ScriptException("Nothing in file");
+ try {
+ int n = cmds[0].indexOf(" ");
+ String cl = n == -1 ? cmds[0] : cmds[0].substring(0, n);
+ simClass = Class.forName(cl);
+
+ if (!Simulator.class.isAssignableFrom(simClass))
+ throw new ScriptException("Class " + cl + " not
a simulator.");
+ simArgs = n == -1 ? cmds[0]: cmds[0].substring(n +
1).trim();
+ } catch (ClassNotFoundException e) {
+ throw new ScriptException("No such simulator class: " +
cmds[0]);
+ }
+ for (int i = 1 ; i < cmds.length ; i++) {
+ StringTokenizer st = new StringTokenizer(cmds[i],"\t ");
+ String cmd = st.nextToken();
+
+ ScriptCommandType ct = commandTypes.get(cmd);
+ if (ct == null)
+ throw new ScriptException("No such command as:
" + cmd);
+
+ cqueue.addLast(ct.newCommand(st));
+ }
+ }
+
+
+
+ public Simulator makeSim(RandomEngine re, DataSpace ds, Settings st,
EventLogger ev) throws ScriptException {
+
+ // Simulator s = new Darknet(re,ds,st,ev,simArgs);
+ // return s;
+
+ try {
+
+ Constructor c = simClass.getConstructor(new Class[]
{RandomEngine.class,
+
DataSpace.class, Settings.class,
+
EventLogger.class, String.class});
+ return (Simulator) c.newInstance(new Object[] {re, ds, st,
ev, simArgs});
+
+ } catch (InvocationTargetException e) {
+ throw new ScriptException("Simulator construction
failed: " + e.getTargetException());
+ } catch (NoSuchMethodException e) {
+ throw new ScriptException("Simulator class missing
constructor.");
+ } catch (InstantiationException e) {
+ throw new ScriptException("Borked: " + e);
+ } catch (IllegalAccessException e) {
+ throw new SimulationException("WTF? : " + e);
+ }
+
+
+ }
+
+ public ScriptCommand nextCommand() {
+ if (cqueue.size() != 0)
+ return cqueue.removeFirst();
+ else
+ return null;
+ }
+
+
+ private static String[] readcmds(BufferedReader br) throws IOException {
+ String l;
+ Vector<String> v = new Vector<String>();
+ while ((l = br.readLine()) != null) {
+ if (!l.trim().equals("") && !l.trim().startsWith("#"))
+ v.add(l);
+ }
+
+ String[] cmds = new String[v.size()];
+ v.copyInto(cmds);
+ return cmds;
+ }
+}
Added: trunk/apps/simsalabim/ScriptCommand.java
===================================================================
--- trunk/apps/simsalabim/ScriptCommand.java (rev 0)
+++ trunk/apps/simsalabim/ScriptCommand.java 2009-02-11 13:53:49 UTC (rev
25585)
@@ -0,0 +1,7 @@
+package simsalabim;
+
+public interface ScriptCommand {
+
+ public void execute(Simulator s) throws ScriptException;
+
+}
Added: trunk/apps/simsalabim/ScriptCommandType.java
===================================================================
--- trunk/apps/simsalabim/ScriptCommandType.java
(rev 0)
+++ trunk/apps/simsalabim/ScriptCommandType.java 2009-02-11 13:53:49 UTC
(rev 25585)
@@ -0,0 +1,49 @@
+package simsalabim;
+
+import java.lang.reflect.*;
+import java.util.StringTokenizer;
+
+public class ScriptCommandType {
+
+ private String name;
+
+ public ScriptCommandType(String name) {
+ this.name = name;
+ }
+
+ public String name() {
+ return name;
+ }
+
+ public ScriptCommand newCommand(StringTokenizer param)
+ throws ScriptException {
+ try {
+ // Reflection is always ugly. Remind me how many times
I have
+ // written this code...
+
+ Class c = Class.forName("simsalabim." + name);
+ int n = param.countTokens();
+ String[] params = new String[n];
+ for (int i = 0; i < n; i++)
+ params[i] = param.nextToken();
+
+ Object o = c.getConstructor(new Class[] {
String[].class })
+ .newInstance(new Object[] { params });
+ return (ScriptCommand) o;
+ } catch (InvocationTargetException e) {
+ Throwable t = e.getTargetException();
+ if (t instanceof ScriptException)
+ throw (ScriptException) t;
+ else if (t instanceof RuntimeException)
+ throw (RuntimeException) t;
+ else
+ throw new ScriptException(e.toString());
+ } catch (Exception e) {
+ // Blanket catches are BAD. Bad Oskar, bad!
+ e.printStackTrace();
+ throw new ScriptException("Failed to construct script
command: "
+ + e);
+ }
+ }
+
+}
Added: trunk/apps/simsalabim/ScriptException.java
===================================================================
--- trunk/apps/simsalabim/ScriptException.java (rev 0)
+++ trunk/apps/simsalabim/ScriptException.java 2009-02-11 13:53:49 UTC (rev
25585)
@@ -0,0 +1,17 @@
+package simsalabim;
+
+/**
+ * Thrown on broken script files.
+ */
+
+public class ScriptException extends Exception {
+
+ public ScriptException(String s) {
+ super(s);
+ }
+
+ public ScriptException() {
+
+ }
+
+}
Added: trunk/apps/simsalabim/Settings.java
===================================================================
--- trunk/apps/simsalabim/Settings.java (rev 0)
+++ trunk/apps/simsalabim/Settings.java 2009-02-11 13:53:49 UTC (rev 25585)
@@ -0,0 +1,93 @@
+package simsalabim;
+import java.util.*;
+import java.io.*;
+
+public class Settings {
+ private HashMap<String, String> hm = new HashMap<String, String>();
+
+ public Settings(String file) {
+ try {
+ BufferedReader br = new BufferedReader(new
FileReader(file));
+
+ String s;
+ while ((s = br.readLine()) != null) {
+ if (!s.trim().startsWith("#") &&
!"".equals(s.trim())) {
+ int j = s.indexOf('=');
+
hm.put(s.substring(0,j).trim(),s.substring(j+1).trim());
+ }
+ }
+ } catch (IOException e) {
+ System.err.println("Exception reading settings: " + e);
+ }
+ }
+
+ /** Creates an empty Settings object. */
+ public Settings() {
+ }
+
+ public boolean isSet(String s) {
+ return hm.containsKey(s);
+ }
+
+ /** Default 0 * */
+ public int getInt(String s) {
+ return getInt(s, 0);
+ }
+
+ public int getInt(String s, int def) {
+ if (!hm.containsKey(s)) {
+ System.err.println("Using default value " + s + " = " +
def);
+ return def;
+ }
+ try {
+ return Integer.parseInt(hm.get(s));
+ } catch (NumberFormatException e) {
+ System.err.println("Numeric setting " + s + "
malformatted.");
+ return def;
+ }
+ }
+
+
+ /** Default 0.0 * */
+ public double getDouble(String s) {
+ return getDouble(s, 0.0);
+ }
+
+ public double getDouble(String s, double def) {
+ if (!hm.containsKey(s)) {
+ System.err.println("Using default value " + s + " = " +
def);
+ return def;
+ }
+ try {
+ return Double.parseDouble(hm.get(s));
+ } catch (NumberFormatException e) {
+ System.err.println("Numeric setting " + s + "
malformatted.");
+ return def;
+ }
+ }
+
+ /** Default null * */
+ public String get(String s) {
+ return hm.get(s);
+ }
+
+ public String get(String s, String def) {
+ String r = hm.get(s);
+ if (r == null) {
+ System.err.println("Using default value " + s + " = " +
def);
+ r = def;
+ }
+ return r;
+ }
+
+
+ /** Lines start with ls * */
+ public String writeOut(String ls) {
+ StringBuffer sb = new StringBuffer();
+ for (String s : hm.keySet()) {
+ sb.append(ls).append(s).append(" =
").append(hm.get(s)).append("\n");
+ }
+ return sb.toString();
+ }
+
+}
Added: trunk/apps/simsalabim/SimulationException.java
===================================================================
--- trunk/apps/simsalabim/SimulationException.java
(rev 0)
+++ trunk/apps/simsalabim/SimulationException.java 2009-02-11 13:53:49 UTC
(rev 25585)
@@ -0,0 +1,15 @@
+package simsalabim;
+
+/**
+ * Exceptions that signify a broken simulation.
+ */
+public class SimulationException extends RuntimeException {
+
+ public SimulationException() {
+ }
+
+ public SimulationException(String s) {
+ super(s);
+ }
+
+}
Added: trunk/apps/simsalabim/Simulator.java
===================================================================
--- trunk/apps/simsalabim/Simulator.java (rev 0)
+++ trunk/apps/simsalabim/Simulator.java 2009-02-11 13:53:49 UTC (rev
25585)
@@ -0,0 +1,192 @@
+package simsalabim;
+
+import java.util.*;
+
+public abstract class Simulator<N extends Node, K extends Key> {
+
+
+ protected RandomEngine re = null;
+
+ private long time = 0;
+ private int nodeNumber = 0;
+
+ protected DataSpace<K> ds;
+ protected ArrayList<N> nodes = new ArrayList<N>();
+ protected EventLogger ev;
+ protected Settings st;
+
+ public Simulator(RandomEngine re, DataSpace<K> ds, Settings st,
EventLogger ev) {
+ this.st = st;
+ this.re = re;
+ this.ds = ds;
+ this.ev = ev;
+ }
+
+ public void dualSplitPositions() {}
+
+ public Simulator(DataSpace<K> ds, EventLogger ev) {
+ this(new MersenneTwister(new Date()), ds, new Settings(), ev);
+ }
+
+ public long time() {
+ return time;
+ }
+
+ public void step(long stime) {
+ time += stime;
+ }
+
+ public RandomEngine random() {
+ return re;
+ }
+
+ public EventLogger log() {
+ return ev;
+ }
+
+ public DataSpace dataspace() {
+ return ds;
+ }
+
+ // To get an active node
+ public N chooseNode() {
+ return nodes.isEmpty() ? null :
nodes.get(re.choose(nodes.size()) - 1);
+ }
+
+ public K chooseKey() {
+ return ds.chooseKey(re);
+ }
+
+ /**
+ * Do NOT call remove on this Iterator.
+ *
+ * @return An iterator of all the nodes.
+ */
+ public Iterator<N> allNodes() {
+ return nodes.iterator();
+ }
+
+ public int netSize() {
+ return nodes.size();
+ }
+
+ public int maintSize() {
+ return nodes.size();
+ }
+
+ public String info() {
+ return "Simulator " + this.getClass().getName() + " at time " +
time + " net size " +
+ nodes.size() + ".";
+ }
+
+ /**
+ * Whether a node should leave permanently or stay dormant. Leave it to
the network.
+ */
+ public abstract boolean leavePermanent(N node);
+
+ public void aggregateNodeData(DataAggregator da) {
+ for (Iterator<N> it = nodes.iterator() ; it.hasNext() ;) {
+ it.next().feedAggregator(da);
+ }
+ }
+
+
+ /**
+ * Creates keys for specific architecture.
+ */
+ public abstract K newKey();
+
+ /**
+ * Creates a new node from a specific architecture.
+ */
+ public N newNode() {
+ N node = newNode(++nodeNumber);
+ return node;
+ }
+
+ protected abstract N newNode(int num);
+
+ public void addNode(N node) {
+ node.setCurrentNumber(nodes.size());
+ nodes.add(node);
+ }
+
+
+ public void removeNode(N n) {
+ int i = n.getCurrentNumber();
+ if (!nodes.get(i).equals(n)) {
+ throw new SimulationException("Node not found in
expected place.");
+ }
+ N l = nodes.remove(nodes.size() - 1);
+ if (l != n) {
+ l.setCurrentNumber(i);
+ nodes.set(i, l);
+ }
+ }
+
+
+ /**
+ * Performs a join for a node from a specific architecture.
+ *
+ * @param newNode
+ * The node joining.
+ * @param oldNode
+ * A node already in the network. Null if no such node
exists.
+ */
+ public abstract boolean join(N newNode, N oldNode, Feedback fb);
+
+
+ /**
+ * Performs a maintenance operation (which can mean anything really) on
a
+ * node.
+ */
+ public abstract void maintenance(Feedback fb);
+
+ /**
+ * Runs a search query for a specific architecture.
+ */
+ public Data search(K k, N n, Feedback fb) {
+ return search(k, n, false, fb);
+ }
+
+ /**
+ * Gets information about the state when running with two joined
networks
+ */
+ public void dualstats(Feedback fb) {
+ }
+
+ /**
+ * Gets information about keys on nodes (both active and passive)
+ */
+ public int[] keystats() {
+ return new int[] {-1,-1};
+ }
+
+
+ /**
+ * Runs a search query for a specific architecture.
+ *
+ * @param ghost
+ * Whether to perform the query in ghost mode. If true, there
+ * will be no side effects on the network.
+ */
+ public abstract Data<K> search(K k, N n, boolean ghost, Feedback fb);
+
+
+ /**
+ * Inserts a piece of data for a specific architecture.
+ */
+ public abstract boolean place(Data<K> d, N n, Feedback fb);
+
+ /**
+ * Tells a node to leave the network. Permanently or temporarily.
+ */
+ public abstract void leave(N n, Feedback fb, boolean permanent);
+
+
+
+ public static void sleep(long millis) {
+ try { Thread.sleep(millis); } catch (InterruptedException e) {}
+ }
+
+}
Added: trunk/apps/simsalabim/StringEventLogger.java
===================================================================
--- trunk/apps/simsalabim/StringEventLogger.java
(rev 0)
+++ trunk/apps/simsalabim/StringEventLogger.java 2009-02-11 13:53:49 UTC
(rev 25585)
@@ -0,0 +1,55 @@
+package simsalabim;
+
+import java.io.PrintWriter;
+
+public class StringEventLogger extends EventLogger {
+
+ public PrintWriter pw;
+
+ public StringEventLogger(PrintWriter pw) {
+ this.pw = pw;
+ }
+
+ public void nodeJoined(long time, Node n) {
+ pw.println(time + "\tNew Node Joined: " + n.toString());
+ }
+
+ public void nodeJoinError(long time, Node n, int error) {
+ pw.println(time + "\tJoin error for node: " + n.toString() + "
error "
+ + error + ": " + error(error));
+ }
+
+ public void dataPlaced(long time, Data d) {
+ pw.println(time + "\tData Placed: " + d.toString());
+ }
+
+ public void dataPlaceError(long time, Data d, int error) {
+ pw.println(time + "\tPlace error for data: " + d.toString() + "
error "
+ + error + ": " + error(error));
+ }
+
+ public void dataFound(long time, Data d) {
+ pw.println(time + "\tData Found: " + d.toString());
+ }
+
+ public void dataNotFound(long time, Key k, int error) {
+ pw.println(time + "\tData Not Found: " + k.toString() + " error
"
+ + error + ": " + error(error));
+ }
+
+ public void dataFindError(long time, Key k, int error) {
+ pw.println(time + "\tFind error for key: " + k.toString() + "
error "
+ + error + ": " + error(error));
+ }
+
+ public void warning(long time, int error) {
+ pw.println(time + "\tWARNING error " + error + ": " +
error(error));
+ pw.flush();
+ }
+
+ public void message(long time, String message) {
+ pw.println(time + "\tMESSAGE: " + message);
+ pw.flush();
+ }
+
+}
Added: trunk/apps/simsalabim/TestSimulator.java
===================================================================
--- trunk/apps/simsalabim/TestSimulator.java (rev 0)
+++ trunk/apps/simsalabim/TestSimulator.java 2009-02-11 13:53:49 UTC (rev
25585)
@@ -0,0 +1,104 @@
+package simsalabim;
+
+public class TestSimulator extends Simulator {
+
+ public TestSimulator(RandomEngine re, DataSpace ds, EventLogger ev,
+ Settings st, String args) {
+ super(re, ds, st, ev);
+ }
+
+ public void maintenance(Feedback fb) {
+ }
+
+ private static class TestKey implements Key {
+
+ long val;
+
+ public TestKey(long val) {
+ this.val = val;
+ }
+
+ public double ident() {
+ return ((double) val) / Long.MAX_VALUE;
+ }
+
+ public String stringVal() {
+ return Long.toString(val);
+ }
+
+ public int hashCode() {
+ return (int) (val ^ (val >>> 32));
+ }
+
+ }
+
+ public Key newKey() {
+ return new TestKey(re.nextLong());
+ }
+
+ private class TestNode extends Node {
+ int searched = 0, placed = 0;
+
+ public TestNode(Simulator god, int num) {
+ super(god, num);
+ }
+
+ public void storeData(Data la, boolean nonvolatile) {
+ }
+
+ public Data findData(Key k) {
+ return ds.getData(k);
+ }
+
+ public int nKeys() {
+ return 0;
+ }
+
+ public int fieldnum() {
+ return 3;
+ }
+
+ public String[] fields() {
+ return new String[] { "Num", "Searched", "Placed" };
+ }
+
+ public String[] info() {
+ return new String[] { Integer.toString(num),
+ Integer.toString(searched),
Integer.toString(placed) };
+ }
+ }
+
+ public boolean leavePermanent(Node n) {
+ return true;
+ }
+
+ public Node newNode(int num) {
+ return new TestNode(this, num);
+ }
+
+ public boolean join(Node newNode, Node oldNode, Feedback fb) {
+ fb.feedback(RunTask.JOIN, true, new double[] {re.choose(20)});
+ return true;
+ }
+
+ public Data search(Key k, Node n, Feedback fb) {
+ return search(k, n, false, fb);
+ }
+
+ public Data search(Key k, Node n, boolean ghost, Feedback fb) {
+ ((TestNode) n).searched++;
+ fb.feedback(RunTask.SEARCH, true, new double[] {re.choose(20)});
+ return ds.getData(k);
+ }
+
+ public boolean place(Data d, Node n, Feedback fb) {
+ ((TestNode) n).placed++;
+ fb.feedback(RunTask.PLACE, true, new double[] {re.choose(20)});
+ d.addedTo(n);
+ return true;
+ }
+
+ public void leave(Node n, Feedback fb, boolean permanent) {
+ fb.feedback(RunTask.LEAVE, true, new double[] {re.choose(20)});
+ }
+}
Added: trunk/apps/simsalabim/TreeKey.java
===================================================================
--- trunk/apps/simsalabim/TreeKey.java (rev 0)
+++ trunk/apps/simsalabim/TreeKey.java 2009-02-11 13:53:49 UTC (rev 25585)
@@ -0,0 +1,40 @@
+package simsalabim;
+
+public class TreeKey extends PositionKey<TreeKey> {
+
+ public static int BITS_USED = 12;
+
+ public static KeyFactory<TreeKey> getFactory() {
+ return new KeyFactory<TreeKey>() {
+ public TreeKey newKey(long val) {
+ return new TreeKey(val);
+ }
+ };
+ }
+
+
+ private int val;
+
+ public TreeKey(long val) {
+ this.val = (int) val;
+ }
+
+ @Override
+ public double dist(TreeKey tk) {
+ int df = tk.val ^ val;
+ for (int i = 64 ; i > 0 ; i--) {
+ if((df & 1) > 0)
+ return i / 64.0;
+ df >>= 1;
+ }
+ return 0.0;
+ }
+
+ public double ident() {
+ return (double) val;
+ }
+
+ public String stringVal() {
+ return "TK" + Long.toHexString(val);
+ }
+}
Added: trunk/apps/simsalabim/XorKey.java
===================================================================
--- trunk/apps/simsalabim/XorKey.java (rev 0)
+++ trunk/apps/simsalabim/XorKey.java 2009-02-11 13:53:49 UTC (rev 25585)
@@ -0,0 +1,47 @@
+package simsalabim;
+/**
+ * A key which does Kademlia style XOR distance, backed by 63 bits for a double
+ *
+ * @author ossa
+ *
+ */
+public class XorKey extends PositionKey<XorKey>{
+
+ public static KeyFactory<XorKey> getFactory() {
+ return new KeyFactory<XorKey>() {
+ public XorKey newKey(long val) {
+ return new XorKey(val);
+ }
+ };
+ }
+
+ private static final long M = 0x7FFFFFFFFFFFFFFFl;
+
+ private long val;
+
+ /**
+ * Creates a key with value val. Will zeroe out the highest order bit.
+ *
+ * @param val
+ */
+ public XorKey(long val) {
+ this.val = val & M; // make sure it is positive.
+ }
+
+
+ @Override
+ public double dist(XorKey pk) {
+ long d = pk.val ^ val;
+ return ((double) d) / (double) Long.MAX_VALUE;
+ }
+
+ public double ident() {
+ return (double) val;
+ }
+
+ public String stringVal() {
+ return "XORK" + Long.toHexString(val);
+ }
+
+
+}
Added: trunk/apps/simsalabim/darknet/Darknet.java
===================================================================
--- trunk/apps/simsalabim/darknet/Darknet.java (rev 0)
+++ trunk/apps/simsalabim/darknet/Darknet.java 2009-02-11 13:53:49 UTC (rev
25585)
@@ -0,0 +1,236 @@
+package simsalabim;
+import java.util.*;
+import java.io.*;
+/**
+ * Simulates a Darknet using the algorithm described in
+ *
+ */
+
+public class Darknet extends Simulator<DarknetNode, CircleKey> {
+
+ int INITIAL_SWITCHES;
+ int MAINT_SWITCHES;
+ int MAX_NO_IMPROVE;
+ int STORE_SIZE;
+ int N_BEST;
+ int RAND_STEPS;
+ float RECACHE_PROB;
+ float RELINK_PROB;
+
+ HashMap<Integer, Person> people;
+ TreeSet<Person> ts = new TreeSet<Person>();
+ int size;
+
+ public Darknet(RandomEngine re, DataSpace ds, EventLogger el, Settings
st, File graph,
+ int startId) {
+ super(re, ds, st, el);
+
+ setParameters();
+ try {
+ readGraph(graph, startId);
+ } catch (IOException e) {
+ throw new RuntimeException("Error reading darknet
graph: " + e);
+ }
+
+ logCreation();
+ }
+
+ public Darknet(RandomEngine re, DataSpace ds, Settings st, EventLogger
el,
+ String args) {
+ super(re, ds, st, el);
+ setParameters();
+
+ StringTokenizer stoke = new StringTokenizer(args,", ");
+
+ if (stoke.countTokens() < 1) {
+ throw new RuntimeException("No darknet graph given.");
+ }
+
+ try {
+ readGraph(new File(stoke.nextToken()),
Integer.parseInt(stoke.nextToken()));
+ } catch (IOException e) {
+ throw new RuntimeException("Error reading darknet
graph: " + e);
+ }
+
+ System.err.println("Read graph of size " + people.size());
+
+ logCreation();
+ }
+
+ private void setParameters() {
+ // Settings
+ INITIAL_SWITCHES = st.getInt("dnInitialSwitches",100);
+ MAINT_SWITCHES = st.getInt("dnMaintSwitches",100);
+ RAND_STEPS = st.getInt("dnRandSteps",5);
+ MAX_NO_IMPROVE = st.getInt("dnMaxNoImprove",20);
+ STORE_SIZE = st.getInt("dnStoreSize",50);
+ N_BEST = st.getInt("dnNBest",3);
+ RECACHE_PROB = (float) st.getDouble("dnRecacheProb",1.0);
+ RELINK_PROB = (float) st.getDouble("dnRelinkProb",1.0);
+ }
+
+ private void logCreation() {
+ ev.message(time(), "Created Darknet Simulator. SWITCHES: " +
MAINT_SWITCHES +
+ " RANDSTEPS: " + RAND_STEPS + " MAX_NO_IMPROVE:
"
+ + MAX_NO_IMPROVE + " STORESIZE: " + STORE_SIZE
+ ".");
+ }
+
+
+ public DarknetNode newNode(int num) {
+
+ double r = re.nextDouble();
+
+ Person p = growNetwork();
+
+ if (p == null)
+ throw new RuntimeException("Poplulation smaller than
network.");
+
+ return new DarknetNode(this, num, p, new CircleKey(r), 0);
+
+ }
+
+ public CircleKey newKey() {
+ return new CircleKey(re.nextDouble());
+ }
+
+ public boolean join(DarknetNode newNode, DarknetNode oldNode, Feedback
fb) {
+ int cost = newNode.join();
+ size++;
+
+ fb.feedback(RunTask.JOIN, true, cost);
+ return true;
+ }
+
+ public void maintenance(Feedback fb) {
+ for (int i = 0; i < MAINT_SWITCHES ; i++) {
+ DarknetNode n = (DarknetNode) chooseNode();
+ if (n != null) {
+ n.makeSwitch();
+ }
+ }
+ fb.feedback(RunTask.MAINTENANCE, true, MAINT_SWITCHES *
RAND_STEPS);
+ }
+
+
+ public Data search(CircleKey k, DarknetNode n, boolean ghost, Feedback
fb) {
+ DarknetRoute route = n.findRoute(k, null, MAX_NO_IMPROVE);
+
+ Data d = route.findData(k);
+
+ if (d != null && re.nextFloat() < RECACHE_PROB) {
+ route.sinkStore(d);
+ }
+ route.reLink(re, RELINK_PROB);
+
+ fb.feedback(RunTask.SEARCH, d != null, route.size());
+ return d;
+ }
+
+ public boolean place(Data<CircleKey> d, DarknetNode n, Feedback fb) {
+ DarknetRoute route = n.findRoute(d.key(), null, MAX_NO_IMPROVE);
+ route.sinkStore(d);
+ route.reLink(re, RELINK_PROB);
+
+ fb.feedback(RunTask.PLACE, true, route.size());
+ return true;
+ }
+
+ public void leave(DarknetNode dn, Feedback fb) {
+ size--;
+ dn.leave();
+ shrinkNetwork(dn.person());
+ fb.feedback(RunTask.LEAVE, true, 1);
+ }
+
+
+
+ /**
+ * Reads a graph file containing the social network data.
+ */
+ protected void readGraph(File s, int startId) throws IOException {
+ BufferedReader br = new BufferedReader(new FileReader(s));
+ String line;
+ people = new HashMap<Integer, Person>();
+ System.err.println("Parsing...");
+ int i = 0;
+ while ((line = br.readLine()) != null) {
+ if (++i % 100000 == 0)
+ System.err.println("Line: " + i);
+ StringTokenizer st = new StringTokenizer(line, "\t");
+ if (st.nextToken().equals("E")) {
+ Integer id1 = new Integer(st.nextToken());
+ Integer id2 = new Integer(st.nextToken());
+
+ Person n1 = people.get(id1);
+ if (n1 == null) {
+ n1 = new Person(id1);
+ people.put(id1, n1);
+ }
+ Person n2 = people.get(id2);
+ if (n2 == null) {
+ n2 = new Person(id2);
+ people.put(id2, n2);
+ }
+
+ // There is duplicate edge protection, and we
are only
+ // interested
+ // in undirected graphs
+ n1.addOut(n2);
+ n2.addOut(n1);
+ }
+ }
+
+ Person p = people.get(startId);
+ if (p == null)
+ throw new RuntimeException("The starting identity did
not exist");
+ ts.add(p);
+ }
+
+
+ /**
+ * Chooses the next person to join the network.
+ */
+ protected Person growNetwork() {
+ // System.err.println("TS SIZE: " + ts.size());
+ if (ts.isEmpty()) // no more people left
+ return null;
+ Person cand = ts.last();
+ // System.err.println("Score: " + cand.score);
+ ts.remove(cand);
+
+ for (Iterator<Person> it = cand.neighbors() ; it.hasNext() ; )
{
+ Person p = it.next();
+
+ if (ts.contains(p)) {
+ ts.remove(p);
+ p.score++;
+ ts.add(p);
+ } else {
+ p.score++;
+ if (!p.isInNetwork()) {
+ ts.add(p);
+ }
+ }
+ }
+
+ return cand;
+ }
+
+ /**
+ * Takes somebody out of the network.
+ */
+ protected void shrinkNetwork(Person p) {
+ for (Iterator<Person> it = p.neighbors() ; it.hasNext() ; ) {
+ Person n = it.next();
+ if (ts.contains(n)) {
+ ts.remove(n);
+ n.score--;
+ ts.add(n);
+ } else {
+ n.score--;
+ }
+ }
+ ts.add(p);
+ }
+
+}
Added: trunk/apps/simsalabim/darknet/DarknetNode.java
===================================================================
--- trunk/apps/simsalabim/darknet/DarknetNode.java
(rev 0)
+++ trunk/apps/simsalabim/darknet/DarknetNode.java 2009-02-11 13:53:49 UTC
(rev 25585)
@@ -0,0 +1,323 @@
+package simsalabim.darknet;
+import simsalabim.*;
+import java.util.*;
+import simsalabim.utils.*;
+
+public class DarknetNode extends Node<Darknet, CircleKey> {
+
+ protected LRUHash data;
+
+ protected Person user;
+
+ protected CircleKey pos;
+ protected LinkedList<DarknetNode> neighbors;
+ protected LinkedList<DarknetNode> openNeighbors;
+ final int nOpen;
+
+ private boolean inNetwork = false;
+
+ private int numQueries = 0;
+
+ public DarknetNode(Darknet god, int num, Person user, CircleKey pos,
+ int nOpen) {
+ super(god, num);
+ this.user = user;
+
+ this.pos = pos;
+ this.nOpen = nOpen;
+
+ data = new LRUHash(god.STORE_SIZE);
+ neighbors = new LinkedList<DarknetNode>();
+ openNeighbors = new LinkedList<DarknetNode>();
+ }
+
+
+
+ public DarknetRoute findRoute(CircleKey k, DarknetRoute dnr,
+ int maxNoImprove) {
+
+ if (!inNetwork)
+ throw new Error("Node not in Network routed to: " +
this);
+ if (!isActive())
+ throw new Error("Node that is active routed to: " +
this);
+
+ /*
+ * This deviates in two ways from true Freenet routing. Firstly
I don't
+ * backtrack, which I should, but which adds complication.
Secondly
+ * Freenet doesn't have a fixed maxSteps, but stops after
taking x steps
+ * without coming closer to the target value.
+ */
+
+ if (dnr == null)
+ dnr = new DarknetRoute(god.N_BEST);
+
+ dnr.atNode(this, k);
+ numQueries++;
+
+ // terminate on success
+ // if (data.contains(k))
+ // return dnr;
+
+ // find next
+ double bd = Double.MAX_VALUE;
+
+ DarknetNode cand = null;
+ for (Iterator<DarknetNode> it = neighbors() ; it.hasNext() ;) {
+ DarknetNode t = it.next();
+
+ if (dnr.contains(t))
+ continue;
+
+ double cd = t.pos.dist(k);
+
+ if (cd < bd) {
+ bd = cd;
+ cand = t;
+ }
+ }
+
+ if (bd < dnr.closest) {
+ dnr.closest = bd;
+ dnr.stepsSince = 0;
+ // dnr.bestNode = cand;
+ } else {
+ dnr.stepsSince++;
+ if (dnr.stepsSince > maxNoImprove)
+ return dnr;
+ }
+
+ if (cand != null)
+ return cand.findRoute(k, dnr, maxNoImprove);
+ else
+ return dnr;
+
+ }
+
+ public int join() {
+ inNetwork = true;
+ user.joinedNetwork(this);
+
+ for (Iterator<Person> it = user.neighbors() ; it.hasNext() ; ) {
+ Person p = it.next();
+ if (p.isInNetwork()) {
+ makeNeighbors(p.getNode());
+ }
+ }
+
+ int nsw = Math.min(god.size, god.INITIAL_SWITCHES);
+
+ for (int i = 0 ; i < nsw ; i++) {
+ makeSwitch();
+ }
+
+ return nsw * god.RAND_STEPS;
+
+ }
+
+ public void makeSwitch() {
+ DarknetNode n = getRandomNode();
+ if (n != null) {
+ double mhVal = Math.min(1, Math.exp((logdist(pos) +
n.logdist(n.pos)
+ - logdist(n.pos)
+ - n.logdist(pos))));
+
+ if (god.random().nextDouble() < mhVal) {
+ CircleKey mp = pos;
+ pos = n.pos;
+ n.pos = mp;
+ }
+ }
+ }
+
+ public int leave() {
+ inNetwork = false;
+ user.leftNetwork();
+ int n = neighbors.size();
+
+ // System.err.println("DN Node leaving network.");
+
+ for (Iterator<Person> it = user.neighbors() ; it.hasNext() ; ) {
+ Person p = it.next();
+ if (p.isInNetwork()) {
+ removeNeighbor(p.getNode());
+ }
+ }
+
+ if (neighbors.size() != 0)
+ throw new RuntimeException("Leaving Darknetnode did not
remove all neighbors.");
+
+ for (Iterator<Data> it = data.data() ; it.hasNext() ;) {
+ it.next().removedFrom(this);
+ }
+
+ return n;
+ }
+
+ public boolean isSink(CircleKey k) {
+ for (DarknetNode n : neighbors) {
+ if (k.dist(n.pos) < k.dist(pos))
+ return false;
+ }
+ return true;
+ }
+
+ public Data findData(CircleKey k) {
+ return data.get(k);
+ }
+
+ public void storeData(Data<CircleKey> d) {
+ d.addedTo(this);
+ Data r = data.put(d);
+ if (r != null)
+ r.removedFrom(this);
+ }
+
+ public void reLink(DarknetNode d) {
+ // THIS HAS NOT BEEN IMPLEMENTED. NEED TO CONSIDER SYMMETRY!
+
+ if (!openNeighbors.contains(d)) {
+ if (openNeighbors.size() >= nOpen)
+ openNeighbors.removeFirst();
+ }
+ }
+
+ /**
+ * Stores at this node, and depth generation neighbors.
+ */
+ public void explosiveStore(Data d, int depth) {
+ storeData(d);
+ if (depth > 0) {
+ for (Iterator<DarknetNode> it = neighbors.iterator() ;
it.hasNext() ;) {
+ it.next().explosiveStore(d, depth - 1);
+ }
+ }
+ }
+
+
+ public Iterator<DarknetNode> neighbors() {
+ return new DoubleIterator<DarknetNode>(neighbors.iterator(),
+ openNeighbors.iterator());
+ }
+
+ public Person person() {
+ return user;
+ }
+
+ protected DarknetNode getRandomNode() {
+ if (neighbors.size() == 0)
+ return null; // this; using null to cause crash because
this is
+ // bad.
+
+ DarknetNode curr = this;
+ for (int i = 0 ; i < god.RAND_STEPS ; i++) {
+ curr =
curr.neighbors.get(god.random().nextInt(curr.neighbors.size()));
+ }
+ return curr;
+ }
+
+
+ protected void makeNeighbors(DarknetNode dn) {
+ if (!neighbors.contains(dn)) {
+ neighbors.add(dn);
+ }
+
+ if (!dn.neighbors.contains(this)) {
+ dn.neighbors.add(this);
+ }
+ }
+
+ protected void removeNeighbor(DarknetNode dn) {
+ neighbors.remove(dn);
+ dn.neighbors.remove(this);
+ }
+
+ /**
+ * Calculates the log distance to the neighbors of this node from
newpos. If
+ * a neighbor has position newpos, then it is given my current position.
+ */
+ private double logdist(CircleKey newpos) {
+ double val = 0.0f;
+ for (Iterator<DarknetNode> it = neighbors.iterator() ;
it.hasNext() ;) {
+ DarknetNode dn = it.next();
+ val += Math.log(dn.pos == newpos ? pos.dist(newpos) :
+ dn.pos.dist(newpos));
+ }
+ return val;
+ }
+
+
+ public int fieldnum() {return 6;}
+
+ public String[] fields() {
+ return new String[]{"Num","Position","Degree","Queries",
"Data", "LogDist"};
+ }
+
+ public String[] info() {
+ return new String[] {
+ Integer.toString(num), pos.stringVal(),
+ Integer.toString(neighbors.size()),
+ Integer.toString(numQueries),
Integer.toString(data.size()),
+ Double.toString(logdist(pos))
+ };
+ }
+
+ public String toString() {
+ return "DN#" + num + " (" + pos + ")";
+ }
+
+
+ /**
+ * Feeds an aggregator called "LinkDistances" with the keyspace
distance to
+ * each of my long links. Feeds an aggregator called "NodeTraffic" with
the
+ * number of queries that passed me.
+ */
+ public void feedAggregator(DataAggregator da) {
+ super.feedAggregator(da);
+
+ if (da.name().equals("LinkDistances")) {
+ for (DarknetNode n : neighbors)
+ da.next(pos.dist(n.pos));
+ } else if (da.name().equals("NodeTraffic")) {
+ da.next(numQueries);
+ }
+ }
+
+
+
+ private class DoubleIterator<T> implements Iterator<T> {
+
+ private Iterator<T> first;
+ private Iterator<T> second;
+ private boolean f;
+
+ public DoubleIterator(Iterator<T> first, Iterator<T> second) {
+ this.first = first;
+ this.second = second;
+
+ f = first.hasNext();
+ }
+
+ public T next() {
+ if (f) {
+ T r = first.next();
+ f = first.hasNext();
+ return r;
+ } else {
+ return second.next();
+ }
+ }
+
+ public boolean hasNext() {
+ return f || second.hasNext();
+ }
+
+ public void remove() {
+ if (f)
+ first.remove();
+ else
+ second.remove();
+ }
+
+ }
+
+}
Added: trunk/apps/simsalabim/darknet/DarknetRoute.java
===================================================================
--- trunk/apps/simsalabim/darknet/DarknetRoute.java
(rev 0)
+++ trunk/apps/simsalabim/darknet/DarknetRoute.java 2009-02-11 13:53:49 UTC
(rev 25585)
@@ -0,0 +1,104 @@
+package simsalabim;
+import simsalabim.*;
+import simsalabim.utils.*;
+import java.util.*;
+
+
+public class DarknetRoute implements Iterable<DarknetNode>,
Contains<DarknetNode> {
+
+ LinkedList<DarknetNode> route = new LinkedList<DarknetNode>();
+
+ double closest = Double.MAX_VALUE;
+ int stepsSince = 0;
+
+ DarknetNode bestNodes[];
+
+ private int nBest;
+
+ public DarknetRoute(int nBest) {
+ this.nBest = nBest;
+ bestNodes = new DarknetNode[nBest];
+ }
+
+ public void atNode(DarknetNode dn, CircleKey k) {
+ route.add(dn);
+
+ int n = -1;
+ double md = 0;
+ for (int i = 0 ; i < nBest ; i++) {
+ if (bestNodes[i] == null) {
+ n = i;
+ break;
+ }
+ double cd = k.dist(bestNodes[i].pos);
+ if (cd > md) {
+ n = i;
+ md = cd;
+ }
+ }
+
+ if (n >= 0 && (bestNodes[n] == null ||
+ k.dist(bestNodes[n].pos) > k.dist(dn.pos))) {
+ bestNodes[n] = dn;
+ }
+
+ }
+
+
+ public int size() {
+ return route.size();
+ }
+
+ public Iterator<DarknetNode> iterator() {
+ return route.iterator();
+ }
+
+ public boolean contains(DarknetNode dn) {
+ return route.contains(dn);
+ }
+
+ public Data findData(CircleKey k) {
+ for (Iterator<DarknetNode> it = route.iterator() ; it.hasNext()
;) {
+ Data d = it.next().findData(k);
+ if (d != null)
+ return d;
+ }
+ return null;
+ }
+
+ public void storeData(Data d) {
+ for (Iterator<DarknetNode> it = route.iterator() ; it.hasNext()
;) {
+ it.next().storeData(d);
+ }
+ }
+
+ public void sinkStore(Data<CircleKey> d) {
+ for (DarknetNode n : route) {
+ if (n.isSink(d.key())) {
+ n.storeData(d);
+ }
+ }
+ }
+
+ public void storeBest(Data d) {
+ for (int i = 0 ; i < nBest ; i++) {
+ if (bestNodes[i] != null)
+ bestNodes[i].storeData(d);
+ }
+ }
+
+
+ /**
+ * Relinks nodes open neighbors to one of the best nodes with given
+ * probability, if possible.
+ */
+ public void reLink(RandomEngine re, float prob) {
+ for (DarknetNode n : route) {
+ if (n.nOpen > 0 && re.nextFloat() < prob) {
+ // THIS IS NOT THIS EASY. I NEED TO FIND AN
OPEN BEST NODE!
+ n.reLink(bestNodes[re.nextInt(nBest)]);
+ }
+ }
+ }
+
+}
Added: trunk/apps/simsalabim/darknet/Person.java
===================================================================
--- trunk/apps/simsalabim/darknet/Person.java (rev 0)
+++ trunk/apps/simsalabim/darknet/Person.java 2009-02-11 13:53:49 UTC (rev
25585)
@@ -0,0 +1,70 @@
+package simsalabim;
+import java.util.*;
+
+ /**
+ * Class for a node in social network.
+ */
+class Person implements Comparable<Person> {
+
+ public LinkedList<Person> outN = new LinkedList<Person>();
+ public int id;
+
+ public int score = 0;
+ private DarknetNode node;
+
+ public Person(int id) {
+ this.id = id;
+ }
+
+ public Iterator<Person> neighbors() {
+ return outN.iterator();
+ }
+
+ public void joinedNetwork(DarknetNode node) {
+ this.node = node;
+ }
+
+ public void leftNetwork() {
+ this.node = null;
+ }
+
+ public boolean isInNetwork() {
+ return node != null;
+ }
+
+ public DarknetNode getNode() {
+ return node;
+ }
+
+
+ public void addOut(Person n) {
+ if (!outN.contains(n))
+ outN.add(n);
+ }
+
+ public boolean linksTo(Person n) {
+ return outN.contains(n);
+ }
+
+ public void removeNeighbor(Person n) {
+ outN.remove(n);
+ }
+
+
+ public int compareTo(Person o) {
+ return ( score > o.score ?
+ 1 :
+ ( score < o.score ?
+ -1 :
+ ( id > o.id ?
+ 1:
+ ( id < o.id ?
+ -1:
+ 0))));
+ }
+
+ public boolean equals(Object o) {
+ return ((Person) o).id == id && ((Person) o).score == score;
+ }
+
+}
Added: trunk/apps/simsalabim/rembre/Rembre.java
===================================================================
--- trunk/apps/simsalabim/rembre/Rembre.java (rev 0)
+++ trunk/apps/simsalabim/rembre/Rembre.java 2009-02-11 13:53:49 UTC (rev
25585)
@@ -0,0 +1,150 @@
+package simsalabim.rembre;
+
+import simsalabim.*;
+import java.lang.reflect.*;
+//import simsalabim.utils.*;
+//import java.util.*;
+
+public class Rembre<K extends PositionKey<K>> extends Simulator<RembreNode<K>,
K> {
+
+ int MAX_STEPS;
+ int MAX_NO_IMPROVE;
+ int RT_SIZE;
+ int DS_SIZE;
+ int DS_BYTES;
+ double UPDATE_PROB;
+ String KEYTYPE;
+
+ private final KeyFactory<K> kf;
+
+ // This isn't threadsafe anyways, but this much we can do...
+ private ThreadLocal<RembreRoute<K>> troute = new
ThreadLocal<RembreRoute<K>>() {
+ protected RembreRoute<K> initialValue() {
+ return new RembreRoute<K>();
+ }
+ };
+
+ public Rembre(RandomEngine re, DataSpace<K> ds, Settings st,
EventLogger ev, String args) {
+ super(re, ds, st, ev);
+ setParams(st);
+ try {
+ Method m =
Class.forName(KEYTYPE).getMethod("getFactory");
+ if (m == null) {
+ throw new SimulationException("rbKeyType must
be a class with a " +
+ "static getFactory()
method.");
+ }
+ kf = (KeyFactory) m.invoke(null, new Object[] {});
+ } catch (Exception e) {
+ e.printStackTrace(System.err);
+ throw new SimulationException("Exception creating
Factory: " + e);
+ }
+ }
+
+ private void setParams(Settings st) {
+ MAX_STEPS = st.getInt("rbMaxSteps",100);
+ MAX_NO_IMPROVE = st.getInt("rbMaxNoImprove",10);
+ RT_SIZE = st.getInt("rbRoutingTableSize",25);
+ DS_SIZE = st.getInt("rbDataStoreSize",100);
+ DS_BYTES = st.getInt("rbDataStoreBytes",10000);
+ UPDATE_PROB = st.getDouble("rbUpdateProb",0.1);
+ KEYTYPE = st.get("rbKeyType","simsalabim.CircleKey");
+ }
+
+
+ @Override
+ public boolean join(RembreNode<K> newNode, RembreNode<K> oldNode,
Feedback fb) {
+ RembreRoute<K> route = troute.get();
+ K k = newNode.pos();
+ route.clear(k);
+ if (oldNode != null) { // all but first
+ oldNode.findRoute(k, route);
+ for (RembreNode<K> n : route) {
+ n.rtTable.addRoute(k, newNode);
+ newNode.rtTable.addRoute(n.pos(),n);
+ }
+ // System.err.println("Route.size(): " + route.size());
+ }
+ // System.err.println("Joined: oldNode " + oldNode + "
route.size(): " +
+ // route.size() +
+ // "route.steps(): " + route.steps);
+ fb.feedback(RunTask.JOIN, true, route.size());
+ return true;
+ }
+
+ @Override
+ public void leave(RembreNode n, Feedback fb) {
+ fb.feedback(RunTask.LEAVE, true, 0);
+ // nothing
+ }
+
+ @Override
+ public void maintenance(Feedback fb) {
+ // nothing...
+
+ }
+
+ @Override
+ public K newKey() {
+ K rk = kf.newKey(re.nextLong());
+ if (rk == null)
+ throw new SimulationException("Keyfactory created null
key.");
+ return rk;
+ }
+
+ @Override
+ public RembreNode<K> newNode(int num) {
+ K pos = newKey();
+ return new RembreNode<K>(this, pos, num);
+ }
+
+ @Override
+ public boolean place(Data<K> d, RembreNode<K> n, Feedback fb) {
+ RembreRoute<K> route = troute.get();
+ route.clear(d.key()); // safety
+ n.findRoute(d.key(), route);
+ updateLinks(route, d.key());
+ route.sinkStore(d);
+ fb.feedback(RunTask.PLACE, true, route.size());
+ // System.err.println("Placed route.size(): " + route.size() +
+ // "route.steps(): " + route.steps);
+ return true;
+ }
+
+ @Override
+ public Data<K> search(K k, RembreNode<K> n, boolean ghost, Feedback fb)
{
+ if (k == null)
+ throw new NullPointerException("Search for null key.");
+ RembreRoute<K> route = troute.get();
+ route.clear(k);
+ n.findRoute(k, route);
+ Data<K> d = route.findData(k);
+ if (d != null) {
+ route.sinkStore(d);
+ updateLinks(route,k);
+ }
+ fb.feedback(RunTask.SEARCH, d != null, route.size());
+ // System.err.println("Searched route.size(): " + route.size() +
+ // "route.steps(): " + route.steps);
+
+ return d;
+ }
+
+ private void updateLinks(RembreRoute<K> route, K k) {
+ // find the closest node in the route
+ RembreNode<K> best = null;
+ double bd = Double.MAX_VALUE;
+ for (RembreNode<K> n : route) {
+ double dist = k.dist(n.pos());
+ if (dist < bd) {
+ bd = dist;
+ best = n;
+ }
+ }
+ for (RembreNode<K> n : route) {
+ if (n != best && re.nextDouble() < UPDATE_PROB) {
+ n.rtTable.addRoute(best.pos(), best);
+ }
+ }
+ }
+
+}
Added: trunk/apps/simsalabim/rembre/RembreNode.java
===================================================================
--- trunk/apps/simsalabim/rembre/RembreNode.java
(rev 0)
+++ trunk/apps/simsalabim/rembre/RembreNode.java 2009-02-11 13:53:49 UTC
(rev 25585)
@@ -0,0 +1,118 @@
+package simsalabim.rembre;
+
+import simsalabim.*;
+import simsalabim.utils.*;
+
+public class RembreNode<K extends PositionKey<K>> extends Node<Rembre, K> {
+
+ private DataStore<K> datastore;
+ private K pos;
+
+ final RoutingTable<K, RembreNode<K>> rtTable;
+
+ private int queries = 0;
+
+ public RembreNode(Rembre god, K pos, int num) {
+ super(god, num);
+ this.pos = pos;
+ this.rtTable = new RoutingTable<K, RembreNode<K>>(god.RT_SIZE,
god.random());
+ this.datastore = new DataStore<K>(this, god.DS_SIZE,
god.DS_BYTES);
+ }
+
+ @Override
+ public Data<K> findData(K k) {
+ if (!isActive()) {
+ throw new Error("Inactive node probed for data.");
+ }
+
+ return datastore.get(k);
+ }
+
+ @Override
+ public void storeData(Data<K> d) {
+ if (!isActive()) {
+ throw new Error("Inactive node asked to store data.");
+ }
+ datastore.put(d);
+ }
+
+
+ void findRoute(K k, RembreRoute<K> route) {
+ if (!isActive()) {
+ System.err.println("Inactive node routed to.");
+ return;
+ }
+ queries++;
+ route.atNode(this);
+ if (datastore.contains(k)) {
+ route.dataFound = true;
+ }
+
+ // System.err.println(god.MAX_STEPS + " route.steps()" +
route.steps);
+
+ while(!route.dataFound && route.steps < god.MAX_STEPS &&
+ route.sni < god.MAX_NO_IMPROVE) {
+ // System.err.println("Route step: " + route.steps);
+ RembreNode<K> next;
+ do {
+ next = rtTable.findRoute(k, route);
+ if (next != null && !next.isActive()) {
+ rtTable.remove(next.pos());
+ }
+ } while (next != null && !next.isActive());
+ if (next == null)
+ return;
+ next.findRoute(k,route);
+ }
+ }
+
+ public boolean isSink(K k) {
+ return !rtTable.canRouteBetter(k, k.dist(pos));
+ }
+
+
+ public K pos() {
+ return pos;
+ }
+
+
+ @Override
+ protected void activated() {
+ // tell data it is back in the network (if any exists)
+ for (Data<K> d : datastore) {
+ d.addedTo(this);
+ }
+ super.activated();
+ }
+
+ @Override
+ protected void deactivated() {
+ // tell data is has been removed
+ for (Data<K> d : datastore) {
+ d.removedFrom(this);
+ }
+ super.deactivated();
+ }
+
+ public int fieldnum() {
+ return 0;
+ }
+
+ public String[] fields() {
+ return new String[]
{"Number","Active","Activated","Deactivated","rtSize","dsSize","dsFill","Queries"};
+ }
+
+ public String[] info() {
+ return new String[] {
+ Integer.toString(this.num),
+ isActive() ? "1" : "0",
+ Long.toString(lastActivatedTime),
+ Long.toString(lastDeactivatedTime),
+ Integer.toString(rtTable.size()),
+ Integer.toString(datastore.size()),
+ Double.toString(datastore.fill()),
+ Integer.toString(queries)
+ };
+ }
+
+}
Added: trunk/apps/simsalabim/rembre/RembreRoute.java
===================================================================
--- trunk/apps/simsalabim/rembre/RembreRoute.java
(rev 0)
+++ trunk/apps/simsalabim/rembre/RembreRoute.java 2009-02-11 13:53:49 UTC
(rev 25585)
@@ -0,0 +1,102 @@
+package simsalabim.rembre;
+import simsalabim.*;
+import simsalabim.utils.Contains;
+import simsalabim.utils.Heap;
+import java.util.*;
+
+public class RembreRoute<K extends PositionKey<K>> implements
Contains<RembreNode<K>>, Iterable<RembreNode<K>> {
+
+ KeyComparator<K> kc = new KeyComparator<K>();
+
+ Collection<RembreNode<K>> route = new HashSet<RembreNode<K>>();
+ Heap<RembreNode<K>> nh = new Heap<RembreNode<K>>(kc);
+
+ double closest = Double.MAX_VALUE;
+ int sni = 0;
+ int steps= 0;
+ K target;
+ boolean dataFound = false;
+
+ public void atNode(RembreNode<K> dn) {
+ route.add(dn);
+ steps++;
+ sni++;
+ if (target == null)
+ throw new NullPointerException("Target is null.");
+ double dist = target.dist(dn.pos());
+ if (dist < closest) {
+ // System.err.println("New best: " + dist + " < " +
closest);
+ sni = 0;
+ closest = dist;
+ }
+ }
+
+ public void clear(K target) {
+ this.dataFound = false;
+ this.target = target;
+ route.clear();
+ kc.setTarget(target);
+ nh.setComparator(kc);
+ closest = Double.MAX_VALUE;
+ sni = 0;
+ steps = 0;
+ }
+
+ public int steps() {
+ return steps;
+ }
+
+ public int size() {
+ return route.size();
+ }
+
+ public Iterator<RembreNode<K>> iterator() {
+ return route.iterator();
+ }
+
+ public boolean contains(RembreNode dn) {
+ return route.contains(dn);
+ }
+
+ public Data<K> findData(K k) {
+ for (Iterator<RembreNode<K>> it = route.iterator() ;
it.hasNext() ;) {
+ Data<K> d = it.next().findData(k);
+ if (d != null)
+ return d;
+ }
+ return null;
+ }
+
+ public void storeData(Data<K> d) {
+ for (Iterator<RembreNode<K>> it = route.iterator() ;
it.hasNext() ;) {
+ it.next().storeData(d);
+ }
+ }
+
+ public void sinkStore(Data<K> d) {
+ for (RembreNode<K> n : route) {
+ if (n.isSink(d.key())) {
+ n.storeData(d);
+ }
+ }
+ }
+
+
+
+ private static class KeyComparator<K extends PositionKey<K>> implements
Comparator<RembreNode<K>> {
+
+ private K target;
+
+ public void setTarget(K target) {
+ this.target = target;
+ }
+
+ public int compare(RembreNode<K> n1, RembreNode<K> n2) {
+ double d = target.dist(n1.pos()) -
target.dist(n2.pos());
+ return d < 0 ? -1 : d == 0 ? 0 : 1;
+ }
+
+ }
+
+}
+
Added: trunk/apps/simsalabim/rembre/test.java
===================================================================
--- trunk/apps/simsalabim/rembre/test.java (rev 0)
+++ trunk/apps/simsalabim/rembre/test.java 2009-02-11 13:53:49 UTC (rev
25585)
@@ -0,0 +1,34 @@
+package simsalabim.rembre;
+
+import java.util.*;
+
+public class test {
+
+ static long M = 0x7FFFFFFFFFFFFFFFl;
+
+ public static void main(String[] args) {
+ Random r = new Random();
+
+ long n1 = r.nextLong();
+
+ int[] ct = new int[10];
+ for (int i = 0; i < 10000; i++) {
+ double val = ((double) (r.nextLong() & M) / (double)
Long.MAX_VALUE);
+ ct[(int) (val * 10)]++;
+ }
+ for (int i = 0; i < 10; i++) {
+ System.err.println(ct[i] + "\t" + (ct[i] / 10000.0));
+ }
+ }
+
+ public static String toBString(long n) {
+ StringBuffer sb = new StringBuffer();
+ for (int i = 0; i < 64; i++) {
+ sb.append(n & 1);
+ n >>= 1;
+ // System.err.println("t" + n + "\t" +
Integer.toBinaryString(n));
+ }
+ return sb.reverse().toString();
+ }
+
+}
Added: trunk/apps/simsalabim/utils/Contains.java
===================================================================
--- trunk/apps/simsalabim/utils/Contains.java (rev 0)
+++ trunk/apps/simsalabim/utils/Contains.java 2009-02-11 13:53:49 UTC (rev
25585)
@@ -0,0 +1,13 @@
+package simsalabim.utils;
+/**
+ * Interface for any class with a boolean contains() methods.
+ *
+ * @author ossa
+ *
+ * @param <T>
+ * The type of object it might contain.
+ */
+public interface Contains<T> {
+
+ public boolean contains(T t);
+}
Added: trunk/apps/simsalabim/utils/DataStore.java
===================================================================
--- trunk/apps/simsalabim/utils/DataStore.java (rev 0)
+++ trunk/apps/simsalabim/utils/DataStore.java 2009-02-11 13:53:49 UTC (rev
25585)
@@ -0,0 +1,201 @@
+package simsalabim.utils;
+import simsalabim.*;
+import java.util.*;
+
+/**
+ * Simple LRU type data storage.
+ */
+public class DataStore<K extends Key> implements Iterable<Data<K>>{
+
+ public static void main(String[] args) {
+ final Random r = new Random();
+
+ Data<Key>[] d = new Data[100];
+ for (int i = 0 ; i < d.length ; i++) {
+ Key k = new Key() {
+ double val = r.nextDouble();
+ public double ident() {
+ return val;
+ }
+ public String stringVal() {
+ return Double.toString(val);
+ }
+ };
+ d[i] = new Data<Key>(k, 100, 0);
+ }
+
+ int[] use = new int[1000];
+ for (int i = 0 ; i < use.length ; i++) {
+ use[i] = r.nextInt(d.length);
+ }
+
+ DataStore<Key> ds = new DataStore<Key>(null, 100,1000);
+
+
+ long time = System.currentTimeMillis();
+ int count = 0;
+ for (int i = 0 ; i < 1000000 ; i++) {
+ ds.put(d[i % d.length]);
+ count += ds.get(d[use[i % use.length]].key()) != null ?
1 : 0;
+ }
+
+
+ System.err.println("Took: " + (System.currentTimeMillis() -
time));
+ System.err.println("Got: " + (((float) count) / 1000000.0));
+
+ }
+
+ private static class DNode<K extends Key> {
+
+ private static int me = 0;
+
+ int num = ++me;
+ Data<K> d;
+ DNode<K> prev;
+ DNode<K> next;
+
+ public String toString() {
+ return "dn " + num;
+ }
+ }
+
+ private class DIterator implements Iterator<Data<K>> {
+ DNode<K> curr;
+
+ public DIterator(DNode<K> first) {
+ curr = first;
+ }
+
+ public boolean hasNext() {
+ return curr != null && curr.next != null;
+ }
+
+ public Data<K> next() {
+ Data<K> r = curr.d;
+ curr = curr.next;
+ return r;
+ }
+
+ public void remove() {
+ throw new Error("DataStore iterator remove not
implemented");
+ }
+ }
+
+ private int maxBytes;
+ private int currBytes = 0;
+
+ private int maxSize;
+ private HashMap<K, DNode<K>> data;
+
+ DNode<K> first;
+ DNode<K> last;
+
+ private Node owner;
+
+ public DataStore(Node owner, int size, int maxBytes) {
+ this.owner = owner;
+ maxSize = size;
+ this.maxBytes = maxBytes;
+ data = new HashMap<K, DNode<K>>(size);
+
+ }
+
+ public void put(Data<K> d) {
+ DNode<K> dn = data.get(d.key());
+ if (dn != null) { // swapdata
+ if (dn.d == d) {
+ bump(dn);
+ return;
+ }
+ currBytes -= dn.d.size();
+ if (owner != null)
+ dn.d.removedFrom(owner);
+ dn.d = d;
+ bump(dn);
+ } else {
+ dn = new DNode<K>();
+ dn.d = d;
+
+ data.put(d.key(), dn);
+
+ if (first == null) {
+ first = dn;
+ last = dn;
+ } else {
+ dn.next = first;
+ first.prev = dn;
+ first = dn;
+ }
+ }
+ if (owner != null)
+ d.addedTo(owner);
+ currBytes += d.size();
+
+
+ while (data.size() > maxSize || currBytes > maxBytes) {
+ // remove oldest
+ data.remove(last.d.key());
+ currBytes -= last.d.size();
+ if (owner != null)
+ last.d.removedFrom(owner);
+ last = last.prev;
+ if (last == null)
+ first = null;
+ else
+ last.next = null;
+ }
+ }
+
+ public Data<K> get(K k) {
+ DNode<K> dn = data.get(k);
+ if (dn == null)
+ return null;
+
+ bump(dn);
+ return dn.d;
+ }
+
+ private void bump(DNode<K> dn) {
+ if (dn.prev != null) {
+
+ dn.prev.next = dn.next;
+
+ if (dn.next == null)
+ last = dn.prev;
+ else
+ dn.next.prev = dn.prev;
+
+
+ dn.prev = null;
+ first.prev = dn;
+ dn.next = first;
+ first = dn;
+ }
+ }
+
+ public boolean contains(K k) {
+ return data.containsKey(k);
+ }
+
+ public Iterator<Data<K>> iterator() {
+ return new DIterator(first);
+ }
+
+ public int size() {
+ return data.size();
+ }
+
+ public double fill() {
+ return currBytes / (double) maxBytes;
+ }
+/*
+ * private int count() { int count = 0; DNode<K> c = first; do {
+ * //System.err.println(c); count++; c = c.next; } while (c != null); return
+ * count; }
+ *
+ * private int bcount() { int count = 0; DNode<K> c = last; do {
+ * //System.err.println(c); count++; c = c.prev; } while (c != null); return
+ * count; }
+ *
+ */
+}
Added: trunk/apps/simsalabim/utils/Heap.java
===================================================================
--- trunk/apps/simsalabim/utils/Heap.java (rev 0)
+++ trunk/apps/simsalabim/utils/Heap.java 2009-02-11 13:53:49 UTC (rev
25585)
@@ -0,0 +1,180 @@
+package simsalabim.utils;
+import java.util.*;
+/**
+ * I can't believe I have to code this.
+ *
+ * @author ossa
+ *
+ */
+
+public class Heap<E> {
+
+ private static Comparator ncomp = new Comparator() {
+ public int compare(Object o1, Object o2) {
+ if (o1 == null)
+ throw new Error("o1 was null.");
+ if (o2 == null)
+ throw new Error("o2 was null");
+ return ((Comparable)o1).compareTo((Comparable) o2);
+ }
+
+ public boolean equals(Object o1, Object o2) {
+ return compare(o1, o2) == 0;
+ }
+ };
+
+ public static void main(String[] args) {
+ Heap<Integer> h = new Heap<Integer>();
+ Random r = new Random();
+ for (int i = 0 ; i < 32 ; i++) {
+ h.add(r.nextInt(1000));
+ }
+
+ for (int i = 0 ; i < 16 ; i++) {
+ System.err.println(h.removeFirst());
+ }
+
+ System.err.println("Adding some more:");
+
+ for (int i = 0 ; i < 16 ; i++) {
+ h.add(r.nextInt(1000));
+ }
+ for (int i = 0 ; i < 33 ; i++) {
+ System.err.println(h.removeFirst());
+ }
+ }
+
+
+ Comparator<? super E> c;
+ Vector<E> heap = new Vector<E>();
+ private int size = 0;
+
+ public Heap(Comparator<? super E> c) {
+ this.c = c;
+ heap.setSize(1);
+ }
+
+ public Heap() {
+ this.c = ncomp;
+ heap.setSize(1);
+ }
+
+
+ public E first() {
+ return heap.get(1);
+ }
+
+ public E removeFirst() {
+ E first = heap.get(1);
+ fill(1);
+ size--;
+ return first;
+ }
+
+ public void add(E e) {
+ replace(1,e);
+ size++;
+ }
+
+ public int size() {
+ return size;
+ }
+
+ /**
+ * Clears heap
+ */
+ public void clear() {
+ heap.clear();
+ heap.setSize(1);
+ size = 0;
+ }
+
+ /**
+ * Clears heap and sets a new comparator.
+ *
+ * @param c
+ */
+ public void setComparator(Comparator<? super E> c) {
+ clear();
+ this.c = c;
+ }
+
+ /**
+ * Fills the spot i with an element from higher in the heap (or set to
null
+ * if leaf).
+ *
+ * @param i
+ */
+ private void fill(int i) {
+ int i1 = i*2;
+ int i2 = i*2 + 1;
+ E p1 = i1 >= heap.size() ? null : heap.get(i1);
+ E p2 = i2 >= heap.size() ? null : heap.get(i2);
+ if (p1 == null && p2 == null) { // leaf
+ heap.set(i,null);
+ } else if (p2 == null || (p1 != null && c.compare(p1, p2) < 0))
{
+ heap.set(i, heap.get(i1));
+ fill(i1);
+ } else {
+ heap.set(i, heap.get(i2));
+ fill(i2);
+ }
+ }
+
+ /**
+ * Add e to the tree, replacing an element at i or below
+ *
+ * @param i
+ * @param e
+ */
+ private void replace(int i, E e) {
+ if (i >= heap.size()) {
+ heap.setSize(i + 1);
+ heap.set(i,e);
+ return;
+ }
+ E n = heap.get(i);
+ if (n == null) {
+ heap.set(i,e);
+ return;
+ }
+ int i1 = i*2;
+ int i2 = i*2 + 1;
+ E p1 = i1 >= heap.size() ? null : heap.get(i1);
+ E p2 = i2 >= heap.size() ? null : heap.get(i2);
+
+ if (c.compare(e, n) < 0) {
+ heap.set(i,e);
+ if (p2 == null || (p1 != null && c.compare(p1, p2) <
0)) {
+ replace(i2,n);
+ } else {
+ replace(i1,n);
+ }
+ } else {
+ if (p2 == null || (p1 != null && c.compare(p1, p2) <
0)) {
+ replace(i1,e);
+ } else {
+ replace(i2,e);
+ }
+ }
+ }
+
+ /**
+ * Moves the element at spot i up to its correct position in the heap.
+ *
+ * @param i
+ */
+ private void moveUp(int i) {
+ int pi = i/2;
+ E n = heap.get(i);
+ E p = heap.get(pi);
+ if (i == 0 || c.compare(n,p) < 0)
+ return;
+ else {
+ heap.set(i, p);
+ heap.set(pi, n);
+ moveUp(pi);
+ }
+ }
+
+}
Added: trunk/apps/simsalabim/utils/LRUHash.java
===================================================================
--- trunk/apps/simsalabim/utils/LRUHash.java (rev 0)
+++ trunk/apps/simsalabim/utils/LRUHash.java 2009-02-11 13:53:49 UTC (rev
25585)
@@ -0,0 +1,174 @@
+package simsalabim.utils;
+import simsalabim.*;
+import java.util.*;
+
+/*
+ * I implement this for the millionth time...
+ */
+
+public class LRUHash {
+
+ public static void main(String[] args) {
+ final Random r = new Random();
+
+ Data[] d = new Data[200];
+ for (int i = 0 ; i < d.length ; i++) {
+ Key k = new Key() {
+ double val = r.nextDouble();
+ public double ident() {
+ return val;
+ }
+ public String stringVal() {
+ return Double.toString(val);
+ }
+ };
+ d[i] = new Data(k, 100, 0);
+ }
+
+ int[] use = new int[1000];
+ for (int i = 0 ; i < use.length ; i++) {
+ use[i] = r.nextInt(d.length);
+ }
+
+ LRUHash ds = new LRUHash(100);
+
+
+ long time = System.currentTimeMillis();
+ int count = 0;
+ for (int i = 0 ; i < 1000000 ; i++) {
+ ds.put(d[i % d.length]);
+ count += ds.get(d[use[i % use.length]].key()) != null ?
1 : 0;
+ }
+
+
+ System.err.println("Took: " + (System.currentTimeMillis() -
time));
+ System.err.println("Got: " + (((float) count) / 1000000.0));
+
+ }
+
+ protected HashMap<Key, DataBucket> data = new HashMap<Key,
DataBucket>();
+
+ protected DataBucket topData;
+ protected DataBucket bottomData;
+
+ protected int maxSize;
+
+ public LRUHash(int maxSize) {
+ this.maxSize = maxSize;
+ }
+
+ public Data get(Key k) {
+ DataBucket db = data.get(k);
+ if (db != null)
+ moveUp(db);
+ return db == null ? null : db.d;
+ }
+
+ public boolean contains(Key k) {
+ return data.containsKey(k);
+ }
+
+ public Data put(Data d) {
+ if (data.containsKey(d.key())) {
+ moveUp(data.get(d.key()));
+ return null;
+ } else {
+ DataBucket db = new DataBucket(d);
+ data.put(d.key(), db);
+
+ addTop(db);
+ return shrinkToSize();
+ }
+ }
+
+ public Data remove(Key k) {
+ DataBucket db = data.get(k);
+ if (db != null) {
+ data.remove(k);
+ removeFromList(db);
+ return db.d;
+ } else
+ return null;
+ }
+
+ public Iterator<Data> data() {
+ return new DataIterator(data.values().iterator());
+ }
+
+ public int size() {
+ return data.size();
+ }
+
+ private void addTop(DataBucket db) {
+ db.below = topData;
+ if (topData != null)
+ topData.above = db;
+ topData = db;
+ if (bottomData == null)
+ bottomData = db;
+ }
+
+ private void removeFromList(DataBucket db) {
+ if (db.above != null) {
+ db.above.below = db.below;
+ } else {
+ topData = db.below;
+ }
+
+ if (db.below != null) {
+ db.below.above = db.above;
+ } else {
+ bottomData = db.above;
+ }
+
+ db.above = null;
+ db.below = null;
+ }
+
+ private void moveUp(DataBucket db) {
+
+ removeFromList(db);
+ addTop(db);
+
+ }
+
+ private Data shrinkToSize() {
+ if (data.size() > maxSize) {
+ DataBucket db = bottomData;
+ data.remove(db.d.key());
+ removeFromList(db);
+ return db.d;
+ } else
+ return null;
+ }
+
+ private class DataBucket {
+ public Data d;
+
+ public DataBucket above;
+ public DataBucket below;
+
+ public DataBucket(Data d) {
+ this.d = d;
+ }
+ }
+
+ private class DataIterator implements Iterator<Data> {
+ Iterator<DataBucket> it;
+ public DataIterator(Iterator<DataBucket> it) {
+ this.it = it;
+ }
+
+ public boolean hasNext() {
+ return it.hasNext();
+ }
+
+ public Data next() {
+ return it.next().d;
+ }
+
+ public void remove() {
+ it.remove();
+ }
+ }
+}
Added: trunk/apps/simsalabim/utils/RandTester.java
===================================================================
--- trunk/apps/simsalabim/utils/RandTester.java (rev 0)
+++ trunk/apps/simsalabim/utils/RandTester.java 2009-02-11 13:53:49 UTC (rev
25585)
@@ -0,0 +1,40 @@
+package simsalabim.utils;
+
+import simsalabim.*;
+import java.util.*;
+
+public class RandTester {
+
+ /**
+ * @param args
+ */
+ public static void main(String[] args) {
+ RandomEngine re = new MersenneTwister((int)
System.currentTimeMillis());
+ int N = 300;
+ int[] f = new int[N];
+ int[] k = new int[N];
+ for (int i = 0 ; i < N ; i++)
+ k[i] = i;
+ HashSet<Integer> hs = new HashSet<Integer>();
+ for (int i = 0 ; i < 100 * N ; i++) {
+ int num = (int) Math.pow(N, re.nextDouble());
+ int lowest = N+1;
+
+ for (int j = 0 ; j < num ; j++) {
+ int idx = j + re.nextInt(N - j);
+ int t = k[j];
+ k[j] = k[idx];
+ k[idx] = t;
+ if (k[j] < lowest)
+ lowest = k[j];
+ }
+ f[lowest]++;
+ hs.clear();
+ }
+
+ StringBuffer sb = new StringBuffer();
+ for (int n : f)
+ sb.append(n).append(" ");
+ System.err.println(sb.toString());
+ }
+}
Added: trunk/apps/simsalabim/utils/RoutingTable.java
===================================================================
--- trunk/apps/simsalabim/utils/RoutingTable.java
(rev 0)
+++ trunk/apps/simsalabim/utils/RoutingTable.java 2009-02-11 13:53:49 UTC
(rev 25585)
@@ -0,0 +1,112 @@
+package simsalabim.utils;
+import simsalabim.*;
+import java.util.*;
+
+public class RoutingTable<K extends PositionKey, N extends Node> {
+
+ private Vector<N> routes;
+ private Vector<K> keys;
+ private int currSize = 0;
+ private int maxSize;
+ private RandomEngine random;
+
+ public RoutingTable(int rtSize, RandomEngine random) {
+ routes = new Vector<N>(rtSize);
+ keys = new Vector<K>(rtSize);
+ maxSize = rtSize;
+ this.random = random;
+ }
+
+ /**
+ * Finds the element with the closest key to k.
+ *
+ * @param k
+ * The key to route for.
+ * @param previous
+ * A collection of nodes to avoid (previously tried). May be
+ * null.
+ * @return The node in the routing table, and not in the previous
+ * collection, or null.
+ */
+ public N findRoute(K k, Contains<N> previous) {
+ double best = Double.MAX_VALUE;
+ N fn = null;
+ for (int i = 0 ; i < currSize ; i++) {
+ K key = keys.get(i);
+ N node = routes.get(i);
+
+ double d = key.dist(k);
+ if (d < best && (previous != null &&
!previous.contains(node))) {
+ fn = routes.get(i);
+ best = d;
+ }
+ }
+ return fn;
+ }
+
+ /**
+ * Adds a route, replacing a random old one if the table is full or if a
+ * previous route exists for the given key.
+ *
+ * @param key
+ * The key to associate the node with.
+ * @param node
+ * The node to add to the routing table.
+ * @return A node which was replaced.
+ */
+ public N addRoute(K key, N node) {
+ int pndx = keys.indexOf(key);
+ if (pndx != -1) {
+ N n = routes.get(pndx);
+ routes.set(pndx, node);
+ return n;
+ } else if (currSize < maxSize) {
+ routes.add(currSize,node);
+ keys.add(currSize, key);
+ currSize++;
+ return null;
+ } else {
+ int ndx = random.nextInt(currSize);
+ N n = routes.get(ndx);
+ routes.set(ndx, node);
+ keys.set(ndx,key);
+ return n;
+ }
+ }
+
+ /**
+ * Removes an element.
+ *
+ * @param k
+ * The key of the element to remove.
+ * @return The element that was removed, or null if no element matching
k
+ * was found.
+ */
+ public N remove(K k) {
+ int ndx = keys.indexOf(k);
+ if (ndx != -1) {
+ currSize--;
+ N n = routes.get(ndx);
+ keys.set(ndx, keys.get(currSize));
+ routes.set(ndx, routes.get(currSize));
+ keys.remove(currSize);
+ routes.remove(currSize);
+ return n;
+ } else
+ return null;
+ }
+
+ public int size() {
+ return routes.size();
+ }
+
+ public boolean canRouteBetter(K k, double dist) {
+ for (int i = 0 ; i < currSize ; i++) {
+ if (k.dist(keys.get(i)) < dist) {
+ return true;
+ }
+ }
+ return false;
+ }
+
+}
