package de.fzi.wim.guibase.graphview.layout;
   
   import java.util.Map;
   import java.util.HashMap;
   import java.util.Collection;
   import java.util.Iterator;
   
   import de.fzi.wim.guibase.graphview.graph.*;
   
  /***
   * The layout strategy that models edges as springs. This algorithm is a refactoring of the graph layout algorithm originally implemented
   * in the <a href="http://www.touchgraph.com/">TouchGraph</a> library.
   */
  public class SpringLayoutStrategy implements LayoutStrategy {
      /*** Specifies how long a node remains in a special state after it is inserted into the graph. */
      protected static final long TIME_NODE_REMAINS_CHANGED=200;
  
      /*** The graph being manipulated by this strategy. */
      protected Graph m_graph;
      /*** The the graph manager. */
      protected GraphManager m_graphManager;
      /*** The damper value. A low damper value causes the graph to move slowly. A value of 1 means no damping. */
      protected double m_damper=0.0;
      /*** The maximum motion value after the last move. Used to see when the graph is stabilizinh. */
      protected double m_maxMotion=0;
      /*** The motion ration after the last move. */
      protected double m_motionRatio=0;
      /*** Then dampoing is true, the damper value decreases. */
      protected boolean m_damping=true;
      /*** The rigidity has the same effect as the damper, except that it is a constant. */
      protected double m_rigidity=1;
  
      /***
       * Creates an instance of this class.
       *
       * @param graph                         the graph that is active
       */
      public SpringLayoutStrategy(Graph graph) {
          m_graph=graph;
          m_graphManager=new GraphManager();
      }
      /***
       * Returns the graph of the strategy.
       *
       * @return                              the graph of the strategy
       */
      public Graph getGraph() {
          return m_graph;
      }
      /***
       * Notifies the strategy that elements were inserted into the graph.
       *
       * @param nodes                         the inserted nodes (may be <code>null</code>)
       * @param edges                         the inserted edges (may be <code>null</code>)
       */
      public void elementsAdded(Collection nodes,Collection edges) {
          m_graphManager.elementsAdded(nodes,edges);
      }
      /***
       * Notifies the strategy that elements were removed from the graph.
       *
       * @param nodes                         the removed nodes (may be <code>null</code>)
       * @param edges                         the removed edges (may be <code>null</code>)
       */
      public void elementsRemoved(Collection nodes,Collection edges) {
          m_graphManager.elementsRemoved(nodes,edges);
      }
      /***
       * Called when the graph is completely changed.
       */
      public void graphContentsChanged() {
          m_graphManager.graphContentsChanged();
      }
      /***
       * Notifies the strategy that the graph has changed due to an event that is not caused by
       * the strategy itself.
       */
      public void notifyGraphLayoutUpdated() {
          m_damping=true;
          m_damper=1.0;
      }
      /***
       * Executes one step in the layout.
       */
      public void executeGraphLayoutStep() {
          for (int i=0;i<10;i++) {
              relaxEdges();
              adjustNodePairs();
              moveNodes();
              damp();
          }
      }
      /***
       * Returns <code>true</code> if more steps in the layout should be executed.
       *
       * @return                              <code>true</code> if more steps should be executed
       */
      public boolean shouldExecuteStep() {
          return !(m_damper<0.1 && m_damping && m_maxMotion<0.001);
     }
     /***
      * Relaxes the edges.
      */
     protected void relaxEdges() {
         Iterator edges=m_graph.getEdges().iterator();
         while (edges.hasNext()) {
             Edge edge=(Edge)edges.next();
             Node from=edge.getFrom();
             Node to=edge.getTo();
             double deltaX=to.getX()-from.getX();
             double deltaY=to.getY()-from.getY();
             double currentLength=Math.sqrt(deltaX*deltaX+deltaY*deltaY);
             double factor=m_rigidity*currentLength/(edge.getLength()*100.0);
             double dx=deltaX*factor;
             double dy=deltaY*factor;
             // Edges pull directly in proportion to the distance between the nodes. This is good,
             // because we want the edges to be stretchy.  The edges are ideal rubberbands.
             // They don't become springs when they are too short.  That only causes the graph to oscillate.
             applyDelta(from,m_graphManager.getNodeMovement(from),dx,dy);
             applyDelta(to,m_graphManager.getNodeMovement(to),-dx,-dy);
         }
     }
     /***
      * Adjusts the pairs of nodes.
      */
     private void adjustNodePairs() {
         SubGraph currentSubGraph=m_graphManager.getFirstSubGraph();
         while (currentSubGraph!=null) {
             NodeMovement node1Movement=currentSubGraph.getFirstNodeMovement();
             while (node1Movement!=null) {
                 Node node1=node1Movement.m_node;
                 NodeMovement node2Movement=currentSubGraph.getFirstNodeMovement();
                 while (node2Movement!=null) {
                     Node node2=node2Movement.m_node;
                     if (node1!=node2) {
                         double dx=0;
                         double dy=0;
                         double deltaX=node1.getX()-node2.getX();
                         double deltaY=node1.getY()-node2.getY();
                         double currentLengthSquared=deltaX*deltaX+deltaY*deltaY; //so it's length squared
                         if (Math.abs(currentLengthSquared)<0.1) {
                             dx=Math.random(); //If two nodes are right on top of each other, randomly separate
                             dy=Math.random();
                         }
                         else if (currentLengthSquared<600*600) {    // 600, because we don't want deleted nodes to fly too far away
                             dx=deltaX/currentLengthSquared;         // If it was sqrt(len) then a single node surrounded by many others will
                             dy=deltaY/currentLengthSquared;         // always look like a circle.  This might look good at first, but I think
                                                                     // it makes large graphs look ugly+it contributes to oscillation.  A
                                                                     // linear function does not fall off fast enough, so you get rough edges
                                                                     // in the 'force field'
                         }
                         double factor=100.0*node1.getRepulsion()*node2.getRepulsion()*m_rigidity;
                         dx*=factor;
                         dy*=factor;
                         applyDelta(node1,node1Movement,dx,dy);
                         applyDelta(node2,node2Movement,-dx,-dy);
                     }
                     node2Movement=(NodeMovement)node2Movement.m_next;
                 }
                 node1Movement=(NodeMovement)node1Movement.m_next;
             }
             currentSubGraph=(SubGraph)currentSubGraph.m_next;
         }
     }
     /***
      * Moves nodes for the computed delta.
      */
     protected void moveNodes() {
         double lastMaxMotion=m_maxMotion;
         m_maxMotion=0;
         Iterator iterator=m_graph.getNodes().iterator();
         while (iterator.hasNext()) {
             Node node=(Node)iterator.next();
             NodeMovement movement=m_graphManager.getNodeMovement(node);
             double dx=movement.m_dx;
             double dy=movement.m_dy;
             dx*=m_damper;   // The damper slows things down.  It cuts down jiggling at the last moment, and optimizes
             dy*=m_damper;   // layout.  As an experiment, get rid of the damper in these lines, and make a
                             // long straight line of nodes.  It wiggles too much and doesn't straighten out.
             // Slow down, but don't stop.  Nodes in motion store momentum.  This helps when the force
             // on a node is very low, but you still want to get optimal layout.
             movement.m_dx=dx/2;
             movement.m_dy=dy/2;
             if (!node.isFixed()) {
                 double distanceMoved=Math.sqrt(dx*dx+dy*dy);
                 // Don't move faster then 30 units at a time. Important in order toprevent severed nodes from flying away.
                 double x=node.getX()+Math.max(-30,Math.min(30,dx));
                 double y=node.getY()+Math.max(-30,Math.min(30,dy));
                 node.setLocation(x,y);
                 m_maxMotion=Math.max(distanceMoved,m_maxMotion);
             }
             if (movement.m_justChanged) {
                 if (System.currentTimeMillis()>movement.m_timeWhenNodeBecomesNormal)
                     movement.m_justChanged=false;
             }
         }
         if (m_maxMotion>0)
             m_motionRatio=lastMaxMotion/m_maxMotion-1; //subtract 1 to make a positive value mean that things are moving faster
         else
             m_motionRatio=0;
     }
     /***
      * Applies a delta to a node.
      *
      * @param node                      the node to which the delta is added
      * @param nodeMovement              the node movement
      * @param dx                        delta in the X direction
      * @param dy                        delta in the Y direction
      */
     protected void applyDelta(Node node,NodeMovement nodeMovement,double dx,double dy) {
         if (nodeMovement.m_justChanged) {
             nodeMovement.m_dx+=dx/10;
             nodeMovement.m_dy+=dy/10;
         }
         else {
             nodeMovement.m_dx+=dx;
             nodeMovement.m_dy+=dy;
         }
     }
     /***
      * Turns damping off.
      */
     public void stopDamper() {
         m_damping=false;
         m_damper=1.0;
     }
     /***
      * Stabilizes the graph gently, by setting the damper to a low value.
      */
     public void stopMotion() {
         m_damping=true;
         if (m_damper>0.3)
             m_damper=0.3;
         else
             m_damper=0;
     }
     /***
      * Applies the damping.
      */
     public void damp() {
         if (m_damping) {
             // This is important.  Only damp when the graph starts to move faster
             // When there is noise, you damp roughly half the time. (Which is a lot)
             // If things are slowing down, then you can let them do so on their own,
             // without damping.
             if (m_motionRatio<=0.001) {
                 //If max motion<0.2, damp away
                 //If by the time the damper has ticked down to 0.9, maxMotion is still>1, damp away
                 //We never want the damper to be negative though
                 if ((m_maxMotion<0.2 || (m_maxMotion>1 && m_damper<0.9)) && m_damper > 0.01)
                     m_damper-=0.01;
                 //If we've slowed down significanly, damp more aggresively (then the line two below)
                 else if (m_maxMotion<0.4 && m_damper > 0.003)
                     m_damper-=0.003;
                 //If max motion is pretty high, and we just started damping, then only damp slightly
                 else if(m_damper>0.0001)
                     m_damper -=0.0001;
             }
         }
         if(m_maxMotion<0.001 && m_damping)
             m_damper=0;
     }
 
     /***
      * The abstract list node.
      */
     protected static class ListNode {
         public ListNode m_next;
         public ListNode m_previous;
         public ListOfNodes m_list;
     }
 
     /***
      * The list.
      */
     protected static class ListOfNodes {
         public ListNode m_head;
         public ListNode m_tail;
         public int m_size;
 
         public void add(ListNode node) {
             if (m_head==null) {
                 m_head=node;
                 m_tail=node;
                 node.m_previous=node.m_next=null;
             }
             else {
                 m_tail.m_next=node;
                 node.m_previous=m_tail;
                 node.m_next=null;
                 m_tail=node;
             }
             node.m_list=this;
         }
         public void remove(ListNode node) {
             if (m_head==node)
                 m_head=node.m_next;
             else
                 node.m_previous.m_next=node.m_next;
             if (m_tail==node)
                 m_tail=node.m_previous;
             else
                 node.m_next.m_previous=node.m_previous;
             node.m_next=node.m_previous=null;
             node.m_list=null;
         }
         public void clear() {
             m_head=m_tail=null;
             m_size=0;
         }
         public void mergeWith(ListOfNodes other) {
             if (m_tail==null) {
                 m_head=other.m_head;
                 m_tail=other.m_head;
             }
             else if (other.m_head!=null) {
                 m_tail.m_next=other.m_head;
                 other.m_head.m_previous=m_tail;
                 m_tail=other.m_tail;
             }
             ListNode pointer=other.m_head;
             while (pointer!=null) {
                 pointer.m_list=this;
                 pointer=pointer.m_next;
             }
             m_size+=other.m_size;
             other.m_head=other.m_tail=null;
             other.m_size=0;
         }
     }
 
     /***
      * Contains information about the node movement.
      */
     protected static class NodeMovement extends ListNode {
         public Node m_node;
         public double m_dx=0.0;
         public double m_dy=0.0;
         public boolean m_justChanged=false;
         public long m_timeWhenNodeBecomesNormal;
 
         public NodeMovement(Node node) {
             m_node=node;
         }
         public SubGraph getSubGraph() {
             return ((SubGraphList)m_list).m_subGraph;
         }
     }
 
     /***
      * Contains information about the subgraphs in the overall graph.
      */
     protected class GraphManager extends ListOfNodes {
         /*** The node movement objects indexed by the node. */
         protected Map m_nodeMovement;
 
         public GraphManager() {
             m_nodeMovement=new HashMap();
         }
         public SubGraph getFirstSubGraph() {
             return (SubGraph)m_head;
         }
         public NodeMovement getNodeMovement(Node node) {
             return (NodeMovement)m_nodeMovement.get(node);
         }
         public void nodeChanged(Node node) {
             NodeMovement nodeMovement=getNodeMovement(node);
             if (nodeMovement!=null) {
                 nodeMovement.m_justChanged=true;
                 nodeMovement.m_timeWhenNodeBecomesNormal=System.currentTimeMillis()+TIME_NODE_REMAINS_CHANGED;
             }
         }
         public void addNode(Node node) {
             if (!m_nodeMovement.containsKey(node)) {
                 NodeMovement nodeMovement=new NodeMovement(node);
                 m_nodeMovement.put(node,nodeMovement);
                 add(new SubGraph(nodeMovement));
             }
             nodeChanged(node);
         }
         public void addEdge(Edge edge) {
             NodeMovement nodeMovement1=getNodeMovement(edge.getFrom());
             NodeMovement nodeMovement2=getNodeMovement(edge.getTo());
             if (nodeMovement1.getSubGraph()!=nodeMovement2.getSubGraph())
                 mergeSubGraphs(nodeMovement1.getSubGraph(),nodeMovement2.getSubGraph());
         }
         public void graphContentsChanged() {
             m_nodeMovement.clear();
             clear();
             Iterator nodes=m_graph.getNodes().iterator();
             while (nodes.hasNext()) {
                 Node node=(Node)nodes.next();
                 addNode(node);
             }
             Iterator edges=m_graph.getEdges().iterator();
             while (edges.hasNext()) {
                 Edge edge=(Edge)edges.next();
                 addEdge(edge);
             }
         }
         public void elementsAdded(Collection nodes,Collection edges) {
             if (nodes!=null) {
                 Iterator iterator=nodes.iterator();
                 while (iterator.hasNext()) {
                     Node node=(Node)iterator.next();
                     addNode(node);
                 }
             }
             if (edges!=null) {
                 Iterator iterator=edges.iterator();
                 while (iterator.hasNext()) {
                     Edge edge=(Edge)iterator.next();
                     addEdge(edge);
                 }
             }
         }
         public void elementsRemoved(Collection nodes,Collection edges) {
             if (nodes!=null) {
                 Iterator iterator=nodes.iterator();
                 while (iterator.hasNext()) {
                     Node node=(Node)iterator.next();
                     m_nodeMovement.remove(node);
                 }
             }
             if (nodes!=null || edges!=null) {
                 m_head=m_tail=null;
                 Iterator iterator=m_nodeMovement.values().iterator();
                 while (iterator.hasNext()) {
                     NodeMovement nodeMovement=(NodeMovement)iterator.next();
                     add(new SubGraph(nodeMovement));
                 }
                 if (edges!=null) {
                     iterator=edges.iterator();
                     while (iterator.hasNext()) {
                         Edge edge=(Edge)iterator.next();
                         nodeChanged(edge.getFrom());
                         nodeChanged(edge.getTo());
                     }
                 }
                 iterator=m_graph.getEdges().iterator();
                 while (iterator.hasNext()) {
                     Edge edge=(Edge)iterator.next();
                     addNode(edge.getFrom());
                     addNode(edge.getTo());
                     addEdge(edge);
                 }
             }
         }
         public void mergeSubGraphs(SubGraph subGraph1,SubGraph subGraph2) {
             if (subGraph1.getSize()<subGraph2.getSize()) {
                 subGraph2.mergeWith(subGraph1);
                 remove(subGraph1);
             }
             else {
                 subGraph1.mergeWith(subGraph2);
                 remove(subGraph2);
             }
         }
     }
 
     /***
      * Information about a subgraph.
      */
     protected static class SubGraph extends ListNode {
         protected SubGraphList m_nodes;
 
         public SubGraph(NodeMovement nodeMovement) {
             m_nodes=new SubGraphList(this);
             m_nodes.add(nodeMovement);
             nodeMovement.m_list=m_nodes;
         }
         public NodeMovement getFirstNodeMovement() {
             return (NodeMovement)m_nodes.m_head;
         }
         public void mergeWith(SubGraph subGraph) {
             m_nodes.mergeWith(subGraph.m_nodes);
         }
         public void removeNodeMovement(NodeMovement nodeMovement) {
             m_nodes.remove(nodeMovement);
         }
         public int getSize() {
             return m_nodes.m_size;
         }
     }
 
     protected static class SubGraphList extends ListOfNodes {
         public SubGraph m_subGraph;
 
         public SubGraphList(SubGraph subGraph) {
             m_subGraph=subGraph;
         }
     }
 }