/*
Copyright Paul James Mutton, 2001-2004, http://www.jibble.org/

This file is part of PieSpy.

This software is dual-licensed, allowing you to choose between the GNU
General Public License (GPL) and the www.jibble.org Commercial License.
Since the GPL may be too restrictive for use in a proprietary application,
a commercial license is also provided. Full license information can be
found at http://www.jibble.org/licenses/

$Author: stremler $
$Id: Graph.java,v 1.10 2005/06/11 20:54:23 stremler Exp $

*/

package org.jibble.socnet;

import java.util.*;
import java.io.*;
import java.awt.*;
import java.awt.image.*;
import java.text.*;
import javax.imageio.ImageIO;

/**
 * The Graph stores the Nodes and Edges, and InferenceHeurisics to allow
 * the structure of the graph to be modified.
 */
public class Graph implements java.io.Serializable {

    public Graph(String label, Configuration config) {
        _label = label;
        this.config = config;

        // The NumberFormat used to format frame numbers in filenames.
        _nf = NumberFormat.getIntegerInstance();
        _nf.setMinimumIntegerDigits(8);
        _nf.setGroupingUsed(false);

        // Add InferenceHeuristics. These are processed in this order.
        _heuristics.add(new DirectAddressingInferenceHeuristic(this, config));
        _heuristics.add(new IndirectAddressingInferenceHeuristic(this, config));
        _heuristics.add(new AdjacencyInferenceHeuristic(this, config));
        _heuristics.add(new BinarySequenceInferenceHeuristic(this, config));

    }

    // Pass a message through the list of InferenceHeuristics.
    public void infer(String nick, String message) {
        if (config.ignoreSet.contains(nick.toLowerCase())) {
            return;
        }

        for (int i = 0; i < _heuristics.size(); i++) {
            InferenceHeuristic heuristic =
                (InferenceHeuristic)_heuristics.get(i);
            heuristic.infer(nick, message);
        }
    }

    // Add a Node to the Graph.
    public void addNode(Node node) {

        // Only add the Node to the HashMap if it's not already in there.
        if (_nodes.containsKey(node)) {
            node = (Node) _nodes.get(node);
        }
        else {
            _nodes.put(node, node);
        }

        // Increment the weight of the Node.
        node.setWeight(node.getWeight() + 1);
    }

    // Add an Edge to the Graph. Increment the weighting if it already exists.
    public boolean addEdge(Node source, Node target, double weight) {
        // Do not add self-edges or weights that are not positive.
        if (source.equals(target) || weight <= 0) {
            return false;
        }

        // Ensure both Nodes are in the Graph first.
        addNode(source);
        addNode(target);

        // Add the Edge to the HashMap, or find the existing entry.
        Edge edge = new Edge(source, target);
        if (_edges.containsKey(edge)) {
            edge = (Edge) _edges.get(edge);
        }
        else {
            source = (Node) _nodes.get(source);
            target = (Node) _nodes.get(target);
            edge = new Edge(source, target);
            _edges.put(edge, edge);
        }
        // Increment the edge weight.
        edge.setWeight(edge.getWeight() + weight);

        // The graph has changed.
        makeNextImage();
        return true;
    }

    // Remove a Node from the Graph, along with all of its emanating Edges.
    public boolean removeNode(Node node) {
        if (_nodes.containsKey(node)) {
            // Remove the Node from the HashMap.
            _nodes.remove(node);

            // Remove all Edges that connect to the removed Node.
            Iterator edgeIt = _edges.keySet().iterator();
            while (edgeIt.hasNext()) {
                Edge edge = (Edge) edgeIt.next();
                if (  edge.getSource().equals(node)
                   || edge.getTarget().equals(node) ) {
                    edgeIt.remove();
                }
            }
            return true;
        }
        return false;
    }

    // Merges oldNode and newNode by:
    // 1) Removing newNode from the Graph and removing all emanating Edges.
    // 2) Renaming the nick of oldNode to match the nick of newNode.
    public void mergeNode(Node oldNode, Node newNode) {
        if (!this.contains(oldNode)) {
            // If the oldNode is not in this Graph, we needn't do anything.
            return;
        }

        // Get the nick that we want to change to.
        String nick = newNode.toString();

        // Remove the newNode from the Graph (and any emanating Edges).
        // Warning: Some nick changes only differ in case, so make sure
        // we're not inadvertantly removing oldNick, too!
        if (!newNode.equals(oldNode)) {
            removeNode(newNode);
        }

        // Important: HashMap keys are allocated to locations based on their
        // hashCode values when they are added. Such keys should ideally be
        // immutable, as they are assumed to return the same hashCode every
        // time.
        // Changing the nick of a Node object causes this contract to be
        // broken, which allows the HashMap to store duplicate Node keys.
        // This makes it necessary to rename a Node by first removing it
        // from the HashMap, then changing its nick, before finally putting
        // it back into the HashMap.
        // Likewise, the hashCode method for Edge depends on the hashCode
        // of its two Nodes, so all Edges emanating from the Node must
        // be removed from the HashMap before the Node is renamed. These must
        // then be put back into the HashMap after the Node has been renamed.

        // Create a List of Edges that will be affected by renaming oldNode.
        Iterator edgeIt = _edges.keySet().iterator();
        LinkedList changedEdges = new LinkedList();
        while (edgeIt.hasNext()) {
            Edge edge = (Edge) edgeIt.next();
            if (  edge.getSource().equals(oldNode)
               || edge.getTarget().equals(oldNode)) {
                changedEdges.add(edge);
            }
        }

        // Remove all affected edges from the HashMap.
        Iterator changedIt = changedEdges.iterator();
        while (changedIt.hasNext()) {
            Edge edge = (Edge) changedIt.next();
            _edges.remove(edge);
        }

        // Remove, rename and replace the oldNode in the HashMap.
        oldNode = get(oldNode);
        _nodes.remove(oldNode);
        oldNode.setNick(nick);
        _nodes.put(oldNode, oldNode);

        // Put all the affected edges back into the HashMap.
        changedIt = changedEdges.iterator();
        while (changedIt.hasNext()) {
            Edge edge = (Edge) changedIt.next();
            _edges.put(edge, edge);
        }

        if (getConnectedNodes().contains(oldNode)) {
            // The changed node is in the graph, so it needs redrawing.
            makeNextImage();
        }

    }

    // Return true if the Graph contains the Node.
    // (This does not necessarily imply that the Node is visible).
    public boolean contains(Node node) {
        return _nodes.containsKey(node);
    }

    // Return true if the Graph contains the Edge.
    public boolean contains(Edge edge) {
        return _edges.containsKey(edge);
    }

    // Return the Graph's Node that has the same nick as the supplied Node.
    public Node get(Node node) {
        return (Node) _nodes.get(node);
    }

    // Return the Graph's Edge that matched the supplied Edge.
    public Edge get(Edge edge) {
        return (Edge) _edges.get(edge);
    }

    public String toString() {
        return "Graph: "+_nodes.size()+" nodes and "+_edges.size()+" edges.";
    }

    public String toString2() {
        return "Nodes:\n" + _nodes + "\nEdges:\n" + _edges;
    }

    // Apply the temporal decay to the Graph.
    public void decay(double amount) {

        // Decrease all Edge weightings and remove non-positive Edges.
        Iterator edgeIt = _edges.keySet().iterator();
        while (edgeIt.hasNext()) {
            Edge edge = (Edge) edgeIt.next();
            edge.setWeight(edge.getWeight() - amount);
            if (edge.getWeight() <= 0) {
                edgeIt.remove();
            }
        }

        // Decrease all Node weightings, but do not allow them to be negative.
        Iterator nodeIt = _nodes.keySet().iterator();
        while (nodeIt.hasNext()) {
            Node node = (Node) nodeIt.next();
            node.setWeight(node.getWeight() - amount);
            if (node.getWeight() < 0) {
                node.setWeight(0);
            }
        }

    }

    // Returns the set of all Nodes that have emanating Edges.
    // This therefore returns all Nodes that will be visible in the drawing.
    private HashSet getConnectedNodes() {
        HashSet connectedNodes = new HashSet();
        Iterator edgeIt = _edges.keySet().iterator();
        while (edgeIt.hasNext()) {
            Edge edge = (Edge) edgeIt.next();
            connectedNodes.add(edge.getSource());
            connectedNodes.add(edge.getTarget());
        }
        return connectedNodes;
    }

    // Applies the spring embedder.
    public void doLayout(int iterations) {

        // For performance, copy each set into an array.
        HashSet visibleNodes = getConnectedNodes();
        Node[] nodes =
            (Node[]) visibleNodes.toArray(new Node[visibleNodes.size()]);
        Edge[] edges =
            (Edge[]) _edges.keySet().toArray(new Edge[_edges.size()]);

        double k = config.k;
        double c = config.c;
	// Repulsive forces between nodes that are further apart than this are
	// ignored.
	double maxRepulsiveForceDistance = config.maxRepulsiveForceDistance;
	double maxRepulsiveForceDistanceSquared = 
               maxRepulsiveForceDistance * maxRepulsiveForceDistance;

        // For each iteration...
        for (int it = 0; it < iterations; it++) {

            // Calculate forces acting on nodes due to node-node repulsions...
            for (int a = 0; a < nodes.length; a++) {
                for (int b = a + 1; b < nodes.length; b++) {
                    Node nodeA = nodes[a];
                    Node nodeB = nodes[b];

                    double deltaX = nodeB.getX() - nodeA.getX();
                    double deltaY = nodeB.getY() - nodeA.getY();

                    double distanceSquared = deltaX * deltaX + deltaY * deltaY;

                    if (distanceSquared < 0.01) {
                        deltaX = Math.random() / 10 + 0.1;
                        deltaY = Math.random() / 10 + 0.1;
                        distanceSquared = deltaX * deltaX + deltaY * deltaY;
                    }

                    //double distance = Math.sqrt(distanceSquared);

                    if (distanceSquared < maxRepulsiveForceDistanceSquared) {
                    //if (distance < maxRepulsiveForceDistance) 
                        //double repulsiveForce = (k * k / distance);
                        double repulsiveForce = (k * k / distanceSquared);

                        nodeB.setFX(nodeB.getFX() + (repulsiveForce * deltaX));
                        nodeB.setFY(nodeB.getFY() + (repulsiveForce * deltaY));
                        nodeA.setFX(nodeA.getFX() - (repulsiveForce * deltaX));
                        nodeA.setFY(nodeA.getFY() - (repulsiveForce * deltaY));

          // nodeB.setFX(nodeB.getFX() + (repulsiveForce * deltaX / distance));
          // nodeB.setFY(nodeB.getFY() + (repulsiveForce * deltaY / distance));
          // nodeA.setFX(nodeA.getFX() - (repulsiveForce * deltaX / distance));
          // nodeA.setFY(nodeA.getFY() - (repulsiveForce * deltaY / distance));
                    }//if
                }//for
            }//for

            // Calculate forces acting on nodes due to edge attractions.
            for (int e = 0; e < edges.length; e++) {
                Edge edge = edges[e];
                Node nodeA = edge.getSource();
                Node nodeB = edge.getTarget();

                double deltaX = nodeB.getX() - nodeA.getX();
                double deltaY = nodeB.getY() - nodeA.getY();

                double distanceSquared = deltaX * deltaX + deltaY * deltaY;

                // Avoid division by zero error or Nodes flying off to
                // infinity.  Pretend there is an arbitrary distance between
                // the Nodes.
                if (distanceSquared < 0.01) {
                    deltaX = Math.random() / 10 + 0.1;
                    deltaY = Math.random() / 10 + 0.1;
                    distanceSquared = deltaX * deltaX + deltaY * deltaY;
                }

                double distance = Math.sqrt(distanceSquared);

                if (distance >  maxRepulsiveForceDistance) {
                    distance = maxRepulsiveForceDistance;
                }

                distanceSquared = distance * distance;

                double attractiveForce = (distanceSquared - k * k) / k;

                // Make edges stronger if people know each other.
                double weight = edge.getWeight();
                if (weight < 1) {
                    weight = 1;
                }
                attractiveForce *= (Math.log(weight) * 0.5) + 1;

                nodeB.setFX(nodeB.getFX() - attractiveForce * deltaX / distance);
                nodeB.setFY(nodeB.getFY() - attractiveForce * deltaY / distance);
                nodeA.setFX(nodeA.getFX() + attractiveForce * deltaX / distance);
                nodeA.setFY(nodeA.getFY() + attractiveForce * deltaY / distance);

            }

            // Now move each node to its new location...
            for (int a = 0; a < nodes.length; a++) {
                Node node = nodes[a];

                double xMovement = c * node.getFX();
                double yMovement = c * node.getFY();

                // Limit movement values to stop nodes flying into oblivion.
                double max = config.maxNodeMovement;
                if (xMovement > max) {
                    xMovement = max;
                }
                else if (xMovement < -max) {
                    xMovement = -max;
                }
                if (yMovement > max) {
                    yMovement = max;
                }
                else if (yMovement < -max) {
                    yMovement = -max;
                }

                node.setX(node.getX() + xMovement);
                node.setY(node.getY() + yMovement);

                // Reset the forces
                node.setFX(0);
                node.setFY(0);
            }

        }

    }

    // Work out the drawing boundaries...
    public void calcBounds(int width, int height) {

        minX = Double.POSITIVE_INFINITY;
        maxX = Double.NEGATIVE_INFINITY;
        minY = Double.POSITIVE_INFINITY;
        maxY = Double.NEGATIVE_INFINITY;
        maxWeight = 0;

        HashSet nodes = getConnectedNodes();
        Iterator nodeIt = nodes.iterator();
        while (nodeIt.hasNext()) {
            Node node = (Node) nodeIt.next();

            if (node.getX() > maxX) {
                maxX = node.getX();
            }
            if (node.getX() < minX) {
                minX = node.getX();
            }
            if (node.getY() > maxY) {
                maxY = node.getY();
            }
            if (node.getY() < minY) {
                minY = node.getY();
            }
        }

        // Increase size if too small.
        double minSize = config.minDiagramSize;
        if (maxX - minX < minSize) {
            double midX = (maxX + minX) / 2;
            minX = midX - (minSize / 2);
            maxX = midX + (minSize / 2);
        }
        if (maxY - minY < minSize) {
            double midY = (maxY + minY) / 2;
            minY = midY - (minSize / 2);
            maxY = midY + (minSize / 2);
        }

        // Work out the maximum weight.
        Iterator edgeIt = _edges.keySet().iterator();
        while (edgeIt.hasNext()) {
            Edge edge = (Edge) edgeIt.next();
            if (edge.getWeight() > maxWeight) {
                maxWeight = edge.getWeight();
            }
        }

        // Jibble the boundaries to maintain the aspect ratio.
        double xyRatio = ((maxX - minX) / (maxY - minY)) / (width / height);
        if (xyRatio > 1) {
            // diagram is wider than it is high.
            double dy = maxY - minY;
            dy = dy * xyRatio - dy;
            minY = minY - dy / 2;
            maxY = maxY + dy / 2;
        }
        else if (xyRatio < 1) {
            // Diagram is higher than it is wide.
            double dx = maxX - minX;
            dx = dx / xyRatio - dx;
            minX = minX - dx / 2;
            maxX = maxX + dx / 2;
        }

    }

    public BufferedImage drawImage( int width,
                                    int height,
                                    int borderSize,
                                    int nodeRadius,
                                    double edgeThreshold,
                                    boolean showEdges ) {

        HashSet nodes = getConnectedNodes();

        // Now actually draw the thing...

        BufferedImage image =
            new BufferedImage(width, height, BufferedImage.TYPE_INT_ARGB);
        Graphics2D g = image.createGraphics();

        g.setColor(config.backgroundColor);
        g.fillRect(1, 1, width - 2, height - 2);

        g.setRenderingHint( RenderingHints.KEY_ANTIALIASING,
                            RenderingHints.VALUE_ANTIALIAS_ON );

        g.setColor(config.borderColor);
        g.drawRect(0, 0, width - 1, height - 1);

        width = width - borderSize * 3;  // note the 3 (gives more border on right side)
        height = height - borderSize * 2;

        g.setColor(config.channelColor);
        g.setFont(new Font("SansSerif", Font.BOLD, 64));
        g.drawString(_label, borderSize + 20, 80);

        g.setColor(config.titleColor);
        g.setFont(new Font("SansSerif", Font.BOLD, 18));
        g.drawString("A Social Network Diagram for an IRC Channel",
                     borderSize, borderSize - nodeRadius - 15);
        g.drawString(_caption, borderSize, height + borderSize * 2 - 5 - 50);
        g.setFont(new Font("SansSerif", Font.PLAIN, 12));
g.drawString( "Image found on http://www.stremler.net/IRC/", borderSize, height + borderSize * 2 - 5 - 45 );// XXX new and testing
        g.drawString( "Generated by " + config.nick
                    + " on " + config.server
                    + " using " + SocialNetworkBot.VERSION,
                     borderSize,
                     height + borderSize * 2 - 5 - 30);
        g.drawString( 
        "Blue edge thickness and shortness represents strength of relationship",
        borderSize, height + borderSize * 2 - 5 - 15);
        g.drawString(
        "http://www.jibble.org/piespy/ - This frame was drawn at " + new Date(),
        borderSize, height + borderSize * 2 - 5);
// XXX Mark for local ?

        // Draw all edges...
        Iterator edgeIt = _edges.keySet().iterator();
        while (edgeIt.hasNext()) {
            Edge edge = (Edge) edgeIt.next();

            if (edge.getWeight() < edgeThreshold) {
                continue;
            }

            double weight = edge.getWeight();

// parameters: source, target, maxX, maxY, minX, minY, borderSize
            Node nodeA = edge.getSource();
            Node nodeB = edge.getTarget();
            int x1, x2, y1, y2;
            x1 = x2 = y1 = y2 = borderSize;
            x1 += (int) (width  * (nodeA.getX() - minX) / (maxX - minX));
            y1 += (int) (height * (nodeA.getY() - minY) / (maxY - minY));
            x2 += (int) (width  * (nodeB.getX() - minX) / (maxX - minX));
            y2 += (int) (height * (nodeB.getY() - minY) / (maxY - minY));
            //
//            int x1 = (int) (width  * (nodeA.getX() - minX) / (maxX - minX)) + borderSize;
//            int y1 = (int) (height * (nodeA.getY() - minY) / (maxY - minY)) + borderSize;
//            int x2 = (int) (width  * (nodeB.getX() - minX) / (maxX - minX)) + borderSize;
//            int y2 = (int) (height * (nodeB.getY() - minY) / (maxY - minY)) + borderSize;
            g.setStroke(new BasicStroke((float) (Math.log(weight + 1) * 0.5) + 1));
            int alpha = 102 + (int) (153 * weight / maxWeight);
            g.setColor(new Color(config.edgeColor.getRed(),
                                 config.edgeColor.getGreen(),
                                 config.edgeColor.getBlue(), alpha) );
            if (showEdges) {
                g.drawLine(x1, y1, x2, y2);
            }
// XXX here we can plug in the line-drawing hack...
//     1/3 on each each for "kick", middle 1/3 for change-nick ?
// Perhaps make the "draw an edge" bit a pluggable strategy?
        }

        // Draw all nodes...
        g.setStroke(new BasicStroke(2.0f));
        g.setFont(new Font("SansSerif", Font.PLAIN, 10));
        Iterator nodeIt = nodes.iterator();
        while (nodeIt.hasNext()) {
            Node node = (Node) nodeIt.next();
            int x1 = (int) (width * (node.getX() - minX) / (maxX - minX)) + borderSize;
            int y1 = (int) (height * (node.getY() - minY) / (maxY - minY)) + borderSize;
          //int newNodeRadius = (int) Math.log((node.getWeight() + 1) / 10) + nodeRadius;
            g.setColor(config.nodeColor);
            g.fillOval(x1 - nodeRadius, y1 - nodeRadius,
                       nodeRadius * 2 , nodeRadius * 2 );
            g.setColor(config.edgeColor);
            g.drawOval(x1 - nodeRadius, y1 - nodeRadius,
                       nodeRadius * 2 , nodeRadius * 2 );
          //g.setColor(Color.white);
          //g.drawString(node.toString(), x1 + nodeRadius + 1, y1 - nodeRadius);
          //g.drawString(node.toString(), x1 + nodeRadius - 1, y1 - nodeRadius);
          //g.drawString(node.toString(), x1 + nodeRadius, y1 - nodeRadius + 1);
          //g.drawString(node.toString(), x1 + nodeRadius, y1 - nodeRadius - 1);
            g.setColor(config.labelColor);
            g.drawString(node.toString(), x1 + nodeRadius, y1 - nodeRadius);
        }

        return image;
    }

    public int getFrameCount() {
        return _frameCount;
    }

    public String getLabel() {
        return _label;
    }

    public void setCaption(String caption) {
        _caption = caption;
    }

    public void setLastFile(File file) {
        _lastFile = file;
    }

    public File getLastFile() {
        return _lastFile;
    }

    public void makeNextImage() {
        _frameCount++;
        String strippedChannel = _label.toLowerCase().substring(1);

        File dir = new File(config.outputDirectory, strippedChannel);
        dir.mkdir();

        doLayout(config.springEmbedderIterations);
        calcBounds(config.outputWidth, config.outputHeight);

        try {
            BufferedImage image = drawImage(config.outputWidth, config.outputHeight, config.borderSize, config.nodeRadius, config.edgeThreshold, config.showEdges);

            // Write the archive image.
            File file = new File(dir, strippedChannel + "-" + _nf.format(_frameCount) + ".png");
            if (config.createArchive) {
                ImageIO.write(image, "png", file);
                _lastFile = file;
            }

            // Also save an image as channel-current.png.
            File current = new File(dir, strippedChannel + "-current.png");
            if (config.createCurrent) {
                ImageIO.write(image, "png", current);
                if (!config.createArchive) {
                    _lastFile = file;
                }
            }

            // Also serialize the graph object for later retrieval.
            if (config.createRestorePoints) {
                writeGraph();
            }

        }
        catch (Exception e) {
            System.out.println("PieSpy has gone wibbly: " + e);
            e.printStackTrace();
        }

        // Apply the temporal decay after each frame is created.
        decay(config.temporalDecayAmount);
    }

    // Serialize this Graph and write it to a File.
    public void writeGraph() {
        try {
            String strippedChannel = _label.toLowerCase().substring(1);
            File dir = new File(config.outputDirectory, strippedChannel);
            File file = new File(dir, strippedChannel + "-restore.dat");
            ObjectOutputStream oos =
                new ObjectOutputStream(new FileOutputStream(file));
            oos.writeObject(SocialNetworkBot.VERSION);
            oos.writeObject(this);
            oos.flush();
            oos.close();
        }
        catch (Exception e) {
            // Do nothing?
        }
    }

    private String _label;
    private String _caption = "";
    private HashMap _nodes = new HashMap();
    private HashMap _edges = new HashMap();

    private double minX = Double.POSITIVE_INFINITY;
    private double maxX = Double.NEGATIVE_INFINITY;
    private double minY = Double.POSITIVE_INFINITY;
    private double maxY = Double.NEGATIVE_INFINITY;
    private double maxWeight = 0;

    private Configuration config;
    private int _frameCount = 0;
    private File _lastFile = null;

    private ArrayList _heuristics = new ArrayList();

    private NumberFormat _nf;

}