Probabilistic choice

Given a mapping between items and their required probability of occurrence, generate a million items randomly subject to the given probabilities and compare the target probability of occurrence versus the generated values.

The total of all the probabilities should equal one. (Because floating point arithmetic is involved this is subject to rounding errors).

package NonUnitTest;

class Probabilistic {
    static long TRIALS = 1000000;
    static Expv[] items =
            { new Expv("aleph", 0, 0.0, 0.0), new Expv("beth", 0, 0.0, 0.0),
              new Expv("gimel", 0, 0.0, 0.0),
              new Expv("daleth", 0, 0.0, 0.0), new Expv("he", 0, 0.0, 0.0),
              new Expv("waw", 0, 0.0, 0.0),
              new Expv("zayin", 0, 0.0, 0.0), new Expv("heth", 0, 0.0, 0.0) };

    //~--- METHODS 

    public static void main(String[] args) {
        int i, j;
        double rnum,
                tsum = 0.0;

        for (i = 0, rnum = 5.0; i < 7; i++, rnum += 1.0) {
            items[i].expect = 1.0 / rnum;
            tsum += items[i].expect;
        }

        items[7].expect = 1.0 - tsum;
        items[0].mapping = 1.0 / 5.0;

        for (i = 1; i < 7; i++) {
            items[i].mapping = items[i - 1].mapping + 1.0 / ((double) i + 5.0);
        }

        items[7].mapping = 1.0;

        for (i = 0; i < TRIALS; i++) {
            rnum = Math.random();

            for (j = 0; j < 8; j++) {
                if (rnum < items[j].mapping) {
                    items[j].probcount++;

                    break;
                }
            }
        }

        System.out.printf("Trials: %d\n", TRIALS);
        System.out.printf("Items:          ");

        for (i = 0; i < 8; i++) {
            System.out.printf("%-8s ", items[i].name);
        }

        System.out.printf("\nTarget prob.:   ");

        for (i = 0; i < 8; i++) {
            System.out.printf("%8.6f ", items[i].expect);
        }

        System.out.printf("\nAttained prob.: ");

        for (i = 0; i < 8; i++) {
            System.out.printf("%8.6f ",
                              (double) (items[i].probcount) / (double) TRIALS);
        }

        System.out.printf("\n");
    }

    //~--- INNER CLASSES 

    private static class Expv {
        public double expect;
        public double mapping;
        public String name;
        public int probcount;

        //~--- CONSTRUCTORS 

        public Expv(String name, int probcount, double expect, double mapping) {
            this.name = name;
            this.probcount = probcount;
            this.expect = expect;
            this.mapping = mapping;
        }
    }
}

Knuth Shuffle (aka the Fisher-Yates shuffle)

Create a random permutation of an array.

import java.util.Random;
 
public static final Random gen = new Random();
 
// version for array of ints
public static void shuffle (int[] array) {
    int n = array.length;
    while (n > 1) {
        //decrements after using the value
        int k = gen.nextInt(n--);
        int temp = array[n];
        array[n] = array[k];
        array[k] = temp;
    }
}

// version for array of references
public static void shuffle (Object[] array) {
    int n = array.length;
    while (n > 1) {
        //decrements after using the value
        int k = gen.nextInt(n--); 
        Object temp = array[n];
        array[n] = array[k];
        array[k] = temp;
    }
}

Hamilton Cycle

    public static void HamiltonCycle(int n, int m, boolean directed,
                                     int nodei[], int nodej[], int cycle[]) {
        int i, j, k, stacklen, lensol, stackindex, len, len1, len2, low, up;
        int firstedges[] = new int[n + 2];
        int endnode[] = new int[m + m + 1];
        int stack[] = new int[m + m + 1];
        boolean connect[] = new boolean[n + 1];
        boolean join, skip;

        // set up the forward star representation of the graph
        k = 0;

        for (i = 1; i <= n; i++) {
            firstedges[i] = k + 1;

            for (j = 1; j <= m; j++) {
                if (nodei[j] == i) {
                    k++;

                    endnode[k] = nodej[j];
                }

                if (!directed) {
                    if (nodej[j] == i) {
                        k++;

                        endnode[k] = nodei[j];
                    }
                }
            }
        }

        firstedges[n + 1] = k + 1;

        // initialize
        lensol = 1;
        stacklen = 0;

        // find the next node
        while (true) {
            if (lensol == 1) {
                stack[1] = 1;
                stack[2] = 1;
                stacklen = 2;
            } else {
                len1 = lensol - 1;
                len2 = cycle[len1];

                for (i = 1; i <= n; i++) {
                    connect[i] = false;
                    low = firstedges[len2];
                    up = firstedges[len2 + 1];

                    if (up > low) {
                        up--;

                        for (k = low; k <= up; k++) {
                            if (endnode[k] == i) {
                                connect[i] = true;

                                break;
                            }
                        }
                    }
                }

                for (i = 1; i <= len1; i++) {
                    len = cycle[i];
                    connect[len] = false;
                }

                len = stacklen;
                skip = false;

                if (lensol != n) {
                    for (i = 1; i <= n; i++) {
                        if (connect[i]) {
                            len++;

                            stack[len] = i;
                        }
                    }

                    stack[len + 1] = len - stacklen;
                    stacklen = len + 1;
                } else {
                    for (i = 1; i <= n; i++) {
                        if (connect[i]) {
                            if (!directed) {
                                if (i > cycle[2]) {
                                    stack[len + 1] = len - stacklen;
                                    stacklen = len + 1;
                                    skip = true;

                                    break;
                                }
                            }

                            join = false;
                            low = firstedges[i];
                            up = firstedges[i + 1];

                            if (up > low) {
                                up--;

                                for (k = low; k <= up; k++) {
                                    if (endnode[k] == 1) {
                                        join = true;

                                        break;
                                    }
                                }
                            }

                            if (join) {
                                stacklen += 2;
                                stack[stacklen - 1] = i;
                                stack[stacklen] = 1;
                            } else {
                                stack[len + 1] = len - stacklen;
                                stacklen = len + 1;
                            }

                            skip = true;

                            break;
                        }
                    }

                    if (!skip) {
                        stack[len + 1] = len - stacklen;
                        stacklen = len + 1;
                    }
                }
            }

            // search further
            while (true) {
                stackindex = stack[stacklen];

                stacklen--;

                if (stackindex == 0) {
                    lensol--;

                    if (lensol == 0) {
                        cycle[0] = 1;

                        return;
                    }

                    continue;
                } else {
                    cycle[lensol] = stack[stacklen];
                    stack[stacklen] = stackindex - 1;

                    if (lensol == n) {
                        cycle[0] = 0;

                        return;
                    }

                    lensol++;

                    break;
                }
            }
        }
    }

All Pairs Shortest Paths

Finds the shortest path between all pairs of nodes in mixed graph of n nodes with any given edge lengths.

    public static void allPairsShortestPaths(int n, int dist[][], int big,
                                             int startnode, int endnode,
                                             int path[]) {
        int i, j, k, d, num, node;
        int next[][] = new int[n + 1][n + 1];
        int order[] = new int[n + 1];

        // compute the shortest path distance matrix
        for (i = 1; i <= n; i++) {
            for (j = 1; j <= n; j++) {
                next[i][j] = i;
            }
        }

        for (i = 1; i <= n; i++) {
            for (j = 1; j <= n; j++) {
                if (dist[j][i] < big) {
                    for (k = 1; k <= n; k++) {
                        if (dist[i][k] < big) {
                            d = dist[j][i] + dist[i][k];

                            if (d < dist[j][k]) {
                                dist[j][k] = d;
                                next[j][k] = next[i][k];
                            }
                        }
                    }
                }
            }
        }

        // find the shortest path from startnode to endnode
        if (startnode == 0) {
            return;
        }

        j = endnode;
        num = 1;
        order[num] = endnode;

        while (true) {
            node = next[startnode][j];

            num++;

            order[num] = node;

            if (node == startnode) {
                break;
            }

            j = node;
        }

        for (i = 1; i <= num; i++) {
            path[i] = order[num - i + 1];
        }

        path[0] = num;
    }

Swatch

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.util.LinkedHashMap;
import java.util.Map;

public class Swatch {
    private static final Logger log =
            (Logger) LoggerFactory.getLogger(Swatch.class);

    private String msg = null;
    private long startTime = 0;
    private final Map<String, Long> map = new LinkedHashMap<String, Long>();

    public void output() {
        for (final String msg : map.keySet()) {
            log.info("{} in {} ms", new Object[] { msg, map.get(msg) });
        }
    }

    public void start(final String msg) {
        if (startTime != 0) {
            throw new IllegalStateException("Already started");
        }

        startTime = System.nanoTime() / 1000000;
        this.msg = msg;
    }

    public void stop() {
        if (startTime == 0) {
            throw new IllegalStateException("Not started");
        }

        final long now = System.nanoTime() / 1000000;
        Long n = map.get(msg);

        if (n == null) {
            n = 0l;
        }

        n += (now - startTime);

        map.put(msg, n);

        startTime = 0;
        msg = null;
    }
}

jdkFetch

    public static void jdkFetch(String address) {
        try {
            URL url = new URL(address);
            URLConnection connection = url.openConnection();
            BufferedReader in = new BufferedReader(
                    new InputStreamReader(connection.getInputStream()));
            String inputLine;

            while ((inputLine = in.readLine()) != null) {
                System.out.println(inputLine);
            }

            in.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

writeObject

    public static void writeObject(String filename, Object obj) {
        try {
            FileOutputStream fos =
                    new FileOutputStream("src/com/andalas/ser/" + filename);
            ObjectOutputStream oos = new ObjectOutputStream(fos);

            oos.writeObject(obj);
            oos.flush();
            oos.close();
            fos.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

readObject

    public static Object readObject(String filename) {
        try {
            InputStream fis = FileUtils.class
                    .getResourceAsStream("/com/andalas/ser/" + filename);

            if (fis != null) {
                ObjectInputStream ois = new ObjectInputStream(fis);
                Object object = ois.readObject();

                ois.close();

                return object;
            }
        } catch (IOException e) {
            e.printStackTrace();
        } catch (ClassNotFoundException e) {
            e.printStackTrace();
        }

        return null;
    }

JVM shutdowns detection

Runtime rt = Runtime.getRuntime();
rt.addShutdownHook(new Thread() {
    public void run() {
        // .... your code ....
    }
});