/*-----------------------------------------------------------------
 * NOTE:
 *   The attribute compatibility check (methods CompatibleNode
 *   and CompatibleEdge of ARGraph) is always performed
 *   applying the method to g1, and passing the attribute of
 *   g1 as first argument, and the attribute of g2 as second
 *   argument. This may be important if the compatibility
 *   criterion is not symmetric.
 -----------------------------------------------------------------*/

/*---------------------------------------------------------
 *   IMPLEMENTATION NOTES:
 * The six vectors core_1, core_2, in_1, in_2, out_1, out_2,
 * are shared among the instances of this class; they are
 * owned by the instance with core_len==0 (the root of the SSR).
 * In the vectors in_* and out_* there is a value indicating
 * the level at which the corresponding node became a member
 * of the core or of Tin (for in_*) or Tout (for out_*),
 * or 0 if the node does not belong to the set.
 * This information is used for backtracking.
 * The fields t1out_len etc. also count the nodes in core.
 * The true t1out_len is t1out_len-core_len!
 ---------------------------------------------------------*/

package netmatch.algorithm;

public class VF2MonoState {
  private int core_len, orig_core_len, added_node1;
  private int t1both_len, t2both_len, t1in_len, t1out_len, t2in_len, t2out_len;// Core nodes are also counted by these...
  private int[] core_1, core_2, in_1, in_2, out_1, out_2;
  private Graph g1, g2;
  private int n1, n2;

  /**
   * Constructor. Makes an empty state.
   * If sortNodes is true, computes an initial ordering
   * for the nodes based on the frequency of their valence.
   */
  public VF2MonoState(Graph ag1, Graph ag2) {
    g1 = ag1;
    g2 = ag2;
    n1 = g1.NodeCount();
    n2 = g2.NodeCount();
    core_len = orig_core_len = 0;
    t1both_len = t1in_len = t1out_len = 0;
    t2both_len = t2in_len = t2out_len = 0;
    added_node1 = Common.NULL_NODE;
    core_1 = new int[n1];
    core_2 = new int[n2];
    in_1 = new int[n1];
    in_2 = new int[n2];
    out_1 = new int[n1];
    out_2 = new int[n2];
    int i;
    for(i = 0;i < n1;i++) {
      core_1[i] = Common.NULL_NODE;
      in_1[i] = 0;
      out_1[i] = 0;
    }
    for(i = 0;i < n2;i++) {
      core_2[i] = Common.NULL_NODE;
      in_2[i] = 0;
      out_2[i] = 0;
    }
  }

  /** Copy constructor. */
  public VF2MonoState(VF2MonoState state) {
    g1 = state.g1;
    g2 = state.g2;
    n1 = state.n1;
    n2 = state.n2;
    core_len = orig_core_len = state.core_len;
    t1in_len = state.t1in_len;
    t1out_len = state.t1out_len;
    t1both_len = state.t1both_len;
    t2in_len = state.t2in_len;
    t2out_len = state.t2out_len;
    t2both_len = state.t2both_len;
    added_node1 = Common.NULL_NODE;
    core_1 = state.core_1;
    core_2 = state.core_2;
    in_1 = state.in_1;
    in_2 = state.in_2;
    out_1 = state.out_1;
    out_2 = state.out_2;
  }

  public Graph GetGraph1() {
    return g1;
  }

  public Graph GetGraph2() {
    return g2;
  }

  public boolean IsGoal() {
    return core_len == n1;
  }

  public boolean IsDead() {
    return n1 > n2 || t1both_len > t2both_len || t1out_len > t2out_len || t1in_len > t2in_len;
  }

  public int CoreLen() {
    return core_len;
  }

  /**
   * Puts in pn1, pn2 the next pair of nodes to be tried. prev_n1
   * and prev_n2 must be the last nodes, or NULL_NODE (default) to start
   * from the first pair. Returns false if no more pairs are available.
   */
  public boolean NextPair(myInteger pn1, myInteger pn2, int prev_n1, int prev_n2) {
    if(prev_n1 == Common.NULL_NODE)
      prev_n1 = 0;
    if(prev_n2 == Common.NULL_NODE)
      prev_n2 = 0;
    else
      prev_n2++;
    if(t1both_len > core_len && t2both_len > core_len) {
      while(prev_n1 < n1 && (core_1[prev_n1] != Common.NULL_NODE || out_1[prev_n1] == 0 || in_1[prev_n1] == 0)) {
        prev_n1++;
        prev_n2 = 0;
      }
    }
    else if(t1out_len > core_len && t2out_len > core_len) {
      while(prev_n1 < n1 && (core_1[prev_n1] != Common.NULL_NODE || out_1[prev_n1] == 0)) {
        prev_n1++;
        prev_n2 = 0;
      }
    }
    else if(t1in_len > core_len && t2in_len > core_len) {
      while(prev_n1 < n1 && (core_1[prev_n1] != Common.NULL_NODE || in_1[prev_n1] == 0)) {
        prev_n1++;
        prev_n2 = 0;
      }
    }
    /*else if(prev_n1 == 0 && order != null) {
      int i = 0;
      while(i < n1 && core_1[prev_n1 = order[i]] != Common.NULL_NODE)
        i++;
      if(i == n1)
        prev_n1 = n1;
    }*/
    else {
      while(prev_n1 < n1 && core_1[prev_n1] != Common.NULL_NODE) {
        prev_n1++;
        prev_n2 = 0;
      }
    }
    if(t1both_len > core_len && t2both_len > core_len) {
      while(prev_n2 < n2 && (core_2[prev_n2] != Common.NULL_NODE || out_2[prev_n2] == 0 || in_2[prev_n2] == 0))
        prev_n2++;
    }
    else if(t1out_len > core_len && t2out_len > core_len) {
      while(prev_n2 < n2 && (core_2[prev_n2] != Common.NULL_NODE || out_2[prev_n2] == 0))
        prev_n2++;
    }
    else if(t1in_len > core_len && t2in_len > core_len) {
      while(prev_n2 < n2 && (core_2[prev_n2] != Common.NULL_NODE || in_2[prev_n2] == 0))
        prev_n2++;
    }
    else {
      while(prev_n2 < n2 && core_2[prev_n2] != Common.NULL_NODE)
        prev_n2++;
    }
    if(prev_n1 < n1 && prev_n2 < n2) {
      pn1.setValue(prev_n1);
      pn2.setValue(prev_n2);
      return true;
    }
    return false;
  }

  /**
   * Returns true if (node1, node2) can be added to the state
   * The attribute compatibility check (methods CompatibleNode
   * and CompatibleEdge of Graph) is always performed
   * applying the method to g1, and passing the attribute of
   * g1 as first argument, and the attribute of g2 as second
   * argument. This may be important if the compatibility
   * criterion is not symmetric.
   */
  public boolean IsFeasiblePair(int node1, int node2) throws Exception {
    if(node1 < n1 && node2 < n2 && core_1[node1] == Common.NULL_NODE && core_2[node2] == Common.NULL_NODE) {
      if(!g1.CompatibleNode(g1.GetNodeAttr(node1), g2.GetNodeAttr(node2)))
        return false;

      int i, other1, other2;
      Object attr1 = null;
      int termout1 = 0, termout2 = 0, termin1 = 0, termin2 = 0, new1 = 0, new2 = 0;

      // Check the 'out' edges of node1
      for(i = 0;i < g1.OutEdgeCount(node1);i++) {
        other1 = g1.GetOutEdge(node1, i, attr1);
        attr1 = g1.GetOutEdge2(node1, i);
        if(core_1[other1] != Common.NULL_NODE) {
          other2 = core_1[other1];
          if(!g2.HasEdge(node2, other2) || !g1.CompatibleEdge(attr1, g2.GetEdgeAttr(node2, other2)))
            return false;
        }
        else {
          if(in_1[other1] != 0)
            termin1++;
          if(out_1[other1] != 0)
            termout1++;
          if(in_1[other1] == 0 && out_1[other1] == 0)
            new1++;
        }
      }

      // Check the 'in' edges of node1
      for(i = 0;i < g1.InEdgeCount(node1);i++) {
        other1 = g1.GetInEdge(node1, i, attr1);
        attr1 = g1.GetInEdge2(node1, i);
        if(core_1[other1] != Common.NULL_NODE) {
          other2 = core_1[other1];
          if(!g2.HasEdge(other2, node2) || !g1.CompatibleEdge(attr1, g2.GetEdgeAttr(other2, node2)))
            return false;
        }
        else {
          if(in_1[other1] != 0)
            termin1++;
          if(out_1[other1] != 0)
            termout1++;
          if(in_1[other1] == 0 && out_1[other1] == 0)
            new1++;
        }
      }

      // Check the 'out' edges of node2
      for(i = 0;i < g2.OutEdgeCount(node2);i++) {
        other2 = g2.GetOutEdge(node2, i);
        if(core_2[other2] != Common.NULL_NODE) {/* Do nothing */
        }
        else {
          if(in_2[other2] != 0)
            termin2++;
          if(out_2[other2] != 0)
            termout2++;
          if(in_2[other2] == 0 && out_2[other2] == 0)
            new2++;
        }
      }

      // Check the 'in' edges of node2
      for(i = 0;i < g2.InEdgeCount(node2);i++) {
        other2 = g2.GetInEdge(node2, i);
        if(core_2[other2] != Common.NULL_NODE) {/* Do nothing */
        }
        else {
          if(in_2[other2] != 0)
            termin2++;
          if(out_2[other2] != 0)
            termout2++;
          if(in_2[other2] == 0 && out_2[other2] == 0)
            new2++;
        }
      }
      return termin1 <= termin2 && termout1 <= termout2 && (termin1 + termout1 + new1) <= (termin2 + termout2 + new2);
    }
    else
      throw new Exception("Exception in VF2MonoState. IsfeasiblePair condition false:\nnode1 < n1 && node2 < n2 && core_1[node1] == NULL_NODE && core_2[node2] == NULL_NODE");
  }

  /**
   * Adds a pair to the Core set of the state.
   * Precondition: the pair must be feasible.
   */
  public void AddPair(int node1, int node2) throws Exception {
    if(node1 < n1 && node2 < n2 && core_len < n1 && core_len < n2) {
      core_len++;
      added_node1 = node1;
      if(in_1[node1] == 0) {
        in_1[node1] = core_len;
        t1in_len++;
        if(out_1[node1] != 0)
          t1both_len++;
      }
      if(out_1[node1] == 0) {
        out_1[node1] = core_len;
        t1out_len++;
        if(in_1[node1] != 0)
          t1both_len++;
      }
      if(in_2[node2] == 0) {
        in_2[node2] = core_len;
        t2in_len++;
        if(out_2[node2] != 0)
          t2both_len++;
      }
      if(out_2[node2] == 0) {
        out_2[node2] = core_len;
        t2out_len++;
        if(in_2[node2] != 0)
          t2both_len++;
      }
      core_1[node1] = node2;
      core_2[node2] = node1;
      int i, other;
      for(i = 0;i < g1.InEdgeCount(node1);i++) {
        other = g1.GetInEdge(node1, i);
        if(in_1[other] == 0) {
          in_1[other] = core_len;
          t1in_len++;
          if(out_1[other] != 0)
            t1both_len++;
        }
      }
      for(i = 0;i < g1.OutEdgeCount(node1);i++) {
        other = g1.GetOutEdge(node1, i);
        if(out_1[other] == 0) {
          out_1[other] = core_len;
          t1out_len++;
          if(in_1[other] != 0)
            t1both_len++;
        }
      }
      for(i = 0;i < g2.InEdgeCount(node2);i++) {
        other = g2.GetInEdge(node2, i);
        if(in_2[other] == 0) {
          in_2[other] = core_len;
          t2in_len++;
          if(out_2[other] != 0)
            t2both_len++;
        }
      }
      for(i = 0;i < g2.OutEdgeCount(node2);i++) {
        other = g2.GetOutEdge(node2, i);
        if(out_2[other] == 0) {
          out_2[other] = core_len;
          t2out_len++;
          if(in_2[other] != 0)
            t2both_len++;
        }
      }
    }
    else
      throw new Exception();
  }

  /**
   * Reads the core set of the state into the arrays c1 and c2.
   * The i-th pair of the mapping is (c1[i], c2[i])
   */
  public void GetCoreSet(int c1[], int c2[]) {
    int i, j;
    for(i = 0, j = 0;i < n1;i++)
      if(core_1[i] != Common.NULL_NODE) {
        c1[j] = i;
        c2[j] = core_1[i];
        j++;
      }
  }

  /** Clones a VF2MonoState, allocating with new the clone. */
  public VF2MonoState Clone() {
    return new VF2MonoState(this);
  }

  /**
   * Undoes the changes to the shared vectors made by the current state.
   * Assumes that at most one AddPair has been performed.
   */
  public void BackTrack() throws Exception {
    if(core_len - orig_core_len <= 1 && added_node1 != Common.NULL_NODE) {
      if(orig_core_len < core_len) {
        int i, node2;
        if(in_1[added_node1] == core_len)
          in_1[added_node1] = 0;
        for(i = 0;i < g1.InEdgeCount(added_node1);i++) {
          int other = g1.GetInEdge(added_node1, i);
          if(in_1[other] == core_len)
            in_1[other] = 0;
        }
        if(out_1[added_node1] == core_len)
          out_1[added_node1] = 0;
        for(i = 0;i < g1.OutEdgeCount(added_node1);i++) {
          int other = g1.GetOutEdge(added_node1, i);
          if(out_1[other] == core_len)
            out_1[other] = 0;
        }
        node2 = core_1[added_node1];
        if(in_2[node2] == core_len)
          in_2[node2] = 0;
        for(i = 0;i < g2.InEdgeCount(node2);i++) {
          int other = g2.GetInEdge(node2, i);
          if(in_2[other] == core_len)
            in_2[other] = 0;
        }
        if(out_2[node2] == core_len)
          out_2[node2] = 0;
        for(i = 0;i < g2.OutEdgeCount(node2);i++) {
          int other = g2.GetOutEdge(node2, i);
          if(out_2[other] == core_len)
            out_2[other] = 0;
        }
        core_1[added_node1] = Common.NULL_NODE;
        core_2[node2] = Common.NULL_NODE;
        core_len = orig_core_len;
        added_node1 = Common.NULL_NODE;
      }
    }
    else
      throw new Exception();
  }
}