import java.util.HashMap;
import java.util.Map;
import java.util.Random;

/**
 * Simple topology generator. It produces a graph with a given 
 * number of nodes, and connects each node to the 3 nearest ones.
 * 
 * @author Andras
 */
public class Nearest3 {
    private double areaWidth = 600;
    private double areaHeight = 400;
    private int nodes = 50;
    private long seed = 1234;

    public Nearest3() {
    }
    
    public Nearest3(int nodes, long seed) {
        this.nodes = nodes;
        this.seed = seed;
    }

    public int getNodes() {
        return nodes;
    }

    public void setNodes(int nodes) {
        this.nodes = nodes;
    }

    public long getSeed() {
        return seed;
    }

    public void setSeed(long seed) {
        this.seed = seed;
    }

    public double getAreaWidth() {
        return areaWidth;
    }

    public void setAreaWidth(double areaWidth) {
        this.areaWidth = areaWidth;
    }

    public double getAreaHeight() {
        return areaHeight;
    }

    public void setAreaHeight(double areaHeight) {
        this.areaHeight = areaHeight;
    }

    /**
     * Generates a connected graph with the given number of nodes and edges, and 
     * no multiple connections between any two nodes.
     * 
     * @return the node coordinates and edge list in a map
     */
    @SuppressWarnings("unchecked")
    public Map generate() {
        double[] nodeX = new double[nodes];
        double[] nodeY = new double[nodes];

        int[] edgeSrc = new int[3*nodes];
        int[] edgeDest = new int[3*nodes];
        Random random = new Random(seed);
 
        // place nodes
        for (int i = 0; i <nodes; i++) {
            nodeX[i] = Math.floor(random.nextDouble()*areaWidth);
            nodeY[i] = Math.floor(random.nextDouble()*areaHeight);
        }

        // connect each node to 3 nearest ones
        int numEdges = 0;
        for (int i = 0; i <nodes; i++) {
            int j1 = findClosestExcept(i, nodeX, nodeY, new int[] {} );
            if (!containsEdge(i, j1, edgeSrc, edgeDest)) {
                edgeSrc[numEdges] = i;
                edgeDest[numEdges] = j1;
                numEdges++;
            }

            int j2 = findClosestExcept(i, nodeX, nodeY, new int[] { j1 });
            if (!containsEdge(i, j2, edgeSrc, edgeDest)) {
                edgeSrc[numEdges] = i;
                edgeDest[numEdges] = j2;
                numEdges++;
            }

            int j3 = findClosestExcept(i, nodeX, nodeY, new int[] { j1, j2 });
            if (!containsEdge(i, j3, edgeSrc, edgeDest)) {
                edgeSrc[numEdges] = i;
                edgeDest[numEdges] = j3;
                numEdges++;
            }

        }
        
        Map result = new HashMap();
        result.put("nodeX", nodeX);
        result.put("nodeY", nodeY);
        result.put("numEdges", numEdges);
        result.put("edgeSrc", edgeSrc);
        result.put("edgeDest", edgeDest);
        return result;
    }

    private int findClosestExcept(int node, double[] nodeX, double[] nodeY, int[] exceptNodes) {
        int minNode = -1;
        double minDistSqr = Double.MAX_VALUE;
        for (int i=0; i<nodes; i++) {
            if (i==node || contains(exceptNodes, i))
                continue;
            double distSqr = square(nodeX[i]-nodeX[node]) + square(nodeY[i]-nodeY[node]);
            if (distSqr < minDistSqr) {
                minDistSqr = distSqr;
                minNode = i;
            }
        }
        return minNode;
    }
    
    private boolean contains(int[] array, int value) {
        for (int i=0; i<array.length; i++)
            if (array[i] == value)
                return true;
        return false;
    }

    private double square(double d) {
        return d*d;
    }
    
    private boolean containsEdge(int node1, int node2, int[] edgeSrc, int[] edgeDest) {
        for (int i=0; i<edgeSrc.length; i++) {
            if (edgeSrc[i] == node1 && edgeDest[i] == node2)
                return true;
            if (edgeSrc[i] == node2 && edgeDest[i] == node1)
                return true;
        }
        return false;
    }

    public static void main(String[] args) {
        int nodes = args.length>=1 ? Integer.parseInt(args[0]) : 10;
        long seed = args.length>=2 ? Long.parseLong(args[1]) : System.currentTimeMillis();
        Nearest3 nearest3 = new Nearest3(nodes, seed);
        nearest3.generate();
    }
}