package netmatch.algorithm;

import java.util.Enumeration;
import java.util.Hashtable;

public class exactEdgeComparator implements AttrComparator {
  public boolean compatible(Object o1, Object o2) {// o1 = query - o2 = graph
    Hashtable h1 = (Hashtable)o1;
    Hashtable h2 = (Hashtable)o2;

    /*System.out.println("compare:");
    printHashTable(h1);
    printHashTable(h2);*/

    Hashtable tmp1 = new Hashtable();
    Hashtable tmp2 = new Hashtable(h2);
    for(Enumeration e1 = h1.keys();e1.hasMoreElements();) {
      String key = (String)e1.nextElement();
      myInteger i1 = (myInteger)h1.get(key);
      if(key.startsWith(Common.ANY_LABEL))
        tmp1.put(key, i1);
      else {
        if(h2.containsKey(key)) {
          myInteger i2 = (myInteger)h2.get(key);
          if(i1.great(i2))
            return false;
          tmp2.remove(key);
          if(i2.intValue() - i1.intValue() > 0)
            tmp2.put(key, new myInteger(i2.intValue() - i1.intValue()));
        }
        else
          return false;
      }
    }
    while(!tmp1.isEmpty()) {
      int max = extractMax(tmp1);
      if(!isFeasible(tmp2, max))
        return false;
    }
    return true;
  }

  private int extractMax(Hashtable tmp) {
    int max = 0;
    String key, maxkey = null;
    for(Enumeration e1 = tmp.keys();e1.hasMoreElements();) {
      key = (String)e1.nextElement();
      myInteger i1 = (myInteger)tmp.get(key);
      if(max < i1.intValue()) {
        maxkey = key;
        max = i1.intValue();
      }
    }
    tmp.remove(maxkey);
    return max;
  }

  private boolean isFeasible(Hashtable tmp, int val) {
    int min = Integer.MAX_VALUE;
    String key, minkey = null;
    for(Enumeration e1 = tmp.keys();e1.hasMoreElements();) {
      key = (String)e1.nextElement();
      myInteger i1 = (myInteger)tmp.get(key);
      if(min >= i1.intValue() && i1.intValue() >= val) {
        minkey = key;
        min = i1.intValue();
      }
    }
    if(minkey != null) {
      tmp.remove(minkey);
      return true;
    }
    return false;
  }

  public void printHashTable(Hashtable h) {
    for(Enumeration e1 = h.keys();e1.hasMoreElements();) {
      String key = (String)e1.nextElement();
      myInteger i1 = (myInteger)h.get(key);
      System.out.println(key+" "+i1.toString());
    }
  }
  /*public boolean compatible(Object o1, Object o2) { // o1 = query - o2 = graph
    Hashtable h1 = (Hashtable)o1;
    Hashtable h2 = (Hashtable)o2;
    for(Enumeration e1 = h1.keys();e1.hasMoreElements();) {
      String key = (String)e1.nextElement();
      myInteger i1 = (myInteger)h1.get(key);
      if(h2.containsKey(key)) {
        myInteger i2 = (myInteger)h2.get(key);
        if(i1.great(i2))
          return false;
      }
      else
        return false;
    }
    return true;
  }*/
}