package etomica.graph.operations;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

import etomica.graph.model.Graph;
import etomica.graph.property.Property;

/**
 * Returns a set of graphs with each one corresponding to a graph in the
 * original set.  The graph in the returned set is the "greatest" isomorph of
 * the original graph (according to Graph.compareTo).  The graph in the
 * returned set may just be a copy of the original graph.
 *
 * @author Andrew Schultz
 */
public class MaxIsomorph implements Unary {

  public Set<Graph> apply(Set<Graph> argument, Parameters params) {
    assert (params == null || params instanceof MaxIsomorphParameters);
    Set<Graph> result = new HashSet<Graph>();
    for (Graph g : argument) {
      Graph newGraph = apply(g, (MaxIsomorphParameters)params);
      if (newGraph != null) {
        result.add(newGraph);
      }
    }
    return result;
  }

  public Graph apply(Graph g, MaxIsomorphParameters params) {
    Graph result = params.prop.check(g) ? g.copy() : null;
    if (g.nodeCount() < 2) {
      if (result == null) {
        throw new RuntimeException("no happy graph for "+g);
      }
      return result;
    }
    byte nodeCount = g.nodeCount();
    byte[] labels = new byte[nodeCount];
    for (byte i=0; i<labels.length; i++) {
      labels[i] = i;
    }
    
    Relabel relabel = new Relabel();
    RelabelParameters rp = new RelabelParameters(labels);
    // swaps is the number of times we have swapped node i since the last time we swapped node i-1
    // we'll need to swap nodeCount-1-i times
    // 0 1 2 3 4
    // 0 1 2 4 3
    // 0 1 3 2 4
    // 0 1 3 4 2
    // 0 1 4 2 3
    // 0 1 4 3 2
    // 0 2 1 3 4
    // ...
    // 0 3 1 2 4
    // ...
    // 0 4 1 2 3
    // ...
    // 1 0 2 3 4
    // ...
    // 2 0 1 3 4
    // ...
    // 3 0 1 2 4
    // ...
    // 4 0 1 2 3
    // ...
    byte[] swaps = new byte[nodeCount-1];
    while (true) {
      boolean success = false;
      for (byte iNode = (byte)(nodeCount-2); iNode>-1; iNode--) {
        if (swaps[iNode] < nodeCount-iNode-1) {
          byte tmp = labels[iNode];
          byte minMax = nodeCount;
          byte swapNode = -1;
          // we want to swap with the node at a higher index with the next highest value...
          // we'll have to find it
          for (byte jNode=(byte)(iNode+1); jNode<nodeCount; jNode++) {
            if (labels[jNode] > tmp && labels[jNode] < minMax) {
              minMax = labels[jNode];
              swapNode = jNode;
            }
          }
          if (swapNode > -1) {
            labels[iNode] = labels[swapNode];
            labels[swapNode] = tmp;
            swaps[iNode]++;
            for (byte jNode = (byte)(iNode+1); jNode<(byte)(nodeCount-1); jNode++) {
              swaps[jNode] = 0;
            }
            //sort everything above iNode
            if (iNode+1 < nodeCount-1) {
              Arrays.sort(labels, iNode+1, nodeCount);
            }
            success = true;
            break;
          }
        }
      }
      if (!success) {
        if (result == null) {
          throw new RuntimeException("no happy graph for "+g);
        }
        return result;
      }
      Graph pg = relabel.apply(g, rp);
      if (params.prop.check(pg) && (result == null || pg.compareTo(result) > 0)) {
        result = pg;
      }
    }
  }
  
  /**
   * Parameters class for MaxIsomorph which defines a graph property to select
   * for.  The maximum isomorph with this property will be returned.
   */
  public static class MaxIsomorphParameters implements Parameters {
    public final Property prop;
    public MaxIsomorphParameters(Property prop) {
      this.prop = prop;
    }
  }

  /**
   * Parameters instance which does not filter out any graph property.
   */
  public static final MaxIsomorphParameters PARAM_ALL = new MaxIsomorphParameters(new Property() {
    public boolean check(Graph graph) {return true;}
  });
}

@@ -136,16 +136,69 @@
 .Graph;%0A
+import etomica.graph.operations.GraphOp.GraphOpNull;%0A
 import e
@@ -1064,40 +1064,90 @@
 ams.
-prop.check(g) ? g.copy() : null;
+graphOp.apply(g);%0A    if (!params.prop.check(result)) %7B%0A      result = null;%0A    %7D
 %0A   
@@ -3326,16 +3326,37 @@
 ph pg = 
+params.graphOp.apply(
 relabel.
@@ -3367,16 +3367,17 @@
 y(g, rp)
+)
 ;%0A      
@@ -3492,18 +3492,16 @@
   %7D%0A  %7D%0A
-  
 %0A  /**%0A 
@@ -3563,35 +3563,143 @@
 aph 
-property to select%0A   * for
+operation and%0A   * property to select for.  After each relabel, the operation will act%0A   * on the graph and the property will be check
 .  T
@@ -3722,17 +3722,22 @@
 rph 
+%0A   * 
 with th
-is
+e
  pro
@@ -3734,32 +3734,42 @@
 th the property 
+satisfied 
 will be returned
@@ -3872,24 +3872,58 @@
 perty prop;%0A
+    public final GraphOp graphOp;%0A
     public M
@@ -3943,16 +3943,33 @@
 ameters(
+GraphOp graphOp, 
 Property
@@ -4001,29 +4001,181 @@
 = prop;%0A    
-%7D%0A  %7D
+  this.graphOp = graphOp;%0A    %7D%0A  %7D%0A%0A  public static final Property PROPERTY_ALL = new Property() %7B%0A    public boolean check(Graph graph) %7Breturn true;%7D%0A  %7D;
 %0A%0A  /**%0A   *
@@ -4337,77 +4337,157 @@
 new 
-Property() %7B%0A    public boolean check(Graph graph) %7Breturn true;%7D%0A  %7D
+GraphOpNull(), PROPERTY_ALL);%0A%0A  public static final MaxIsomorphParameters PARAM_ROOTY = new MaxIsomorphParameters(new GraphOpMaxRoot(), PROPERTY_ALL
 );%0A%7D

add ability to perform an operation for each relabeled graph