public class Q4Sources { public Q4Sources() { } /** * Add a pipe to the network. The new pipe does not have any connections. * The method should return the id of the new pipe. */ public int add() { // FIXME return -1; } /** * Add a pipe to the network with an incoming connection from an * already existing pipe in the network, if this does not break any * of the network rules: * - pipe fromPipeId must be one that exists in the network (previously * added and not removed); and * - pipe fromPipeId must have at most 2 already existing outgoing * connections. * * If adding the new pipe would break these rules, the method should * not add the pipe, and return -1. Otherwise, the method should update * the network and return the id of the new pipe. */ public int addFrom(int fromPipeId) { // FIXME return -1; } /** * Add a pipe to the network with an outgoing connection to an * already existing pipe in the network, if this does not break any * of the network rules: * - pipe toPipeId must be one that exists in the network (previously * added and not removed); and * - pipe toPipeId must have at most 2 already existing incoming * connections. * * If adding the new pipe would break these rules, the method should * not add the pipe, and return -1. Otherwise, the method should update * the network and return the id of the new pipe. */ public int addTo(int toPipeId) { // FIXME return -1; } /** * Remove a pipe from the network. This also removes all connections to * and from the pipe (but not the pipes it is connected to). * * If the pipeId does not exist in the network (has not been added or * has already been removed) then the method should not do anything. */ public void remove(int pipeId) { // FIXME } /** * Return the number of sources in the network. * * A source is a pipe that has no incoming connections. */ public int nSources() { // FIXME return 0; } /** * Test scaling behaviour: if all operations are (amortised) constant * time, the total time for each size (2^B .. 2^(B + M - 1)) should be * roughly equal. */ static void testScaling() { final int M = 8; final int B = 10; int R = intPow(2, M) * 100; long[] times = new long[M]; // primer for (int i = 0; i < 100; i++) { testCounts1(B + M - 1); } for (int s = 0; s < M; s++) { long t0 = System.nanoTime(); for (int i = 0; i < R; i++) { testCounts1(B + s); } long t1 = System.nanoTime(); times[s] = t1 - t0; R = R / 2; } for (int s = 0; s < M; s++) System.out.println("size " + intPow(2, B + s) + ": time = " + times[s]); long tmax = times[0]; long tmin = times[0]; double sum = times[0]; int nInc = 0; for (int s = 1; s < M; s++) { tmax = max(tmax, times[s]); tmin = min(tmin, times[s]); sum += times[s]; if (times[s] > times[s - 1]) nInc += 1; } double avg = sum/M; double rd1 = ((double)abs(tmax - avg))/avg; double rd2 = ((double)abs(tmax - avg))/avg; System.out.println("max relative difference: " + (max(rd1, rd2) * 100) + "%"); System.out.println("# increasing: " + nInc + " / " + (M - 1)); } public static void main(String[] args) { testScaling(); } };