public class Entity implements Comparable<Entity> {

  public static Logger log = Logger.getLogger(Entity.class);
  
  /** final score of this entity */
  public static final String SCORE = "Score";
  /** a name for the weight of string length */
  public static final String NAME_LENGTH = "Length";
  public static final String RELATION_SEPARATOR = "::";
  
  /** unknown correctness */
  public static final int UNKNOWN_CORRECT = -1;
  /** incorrect */
  public static final int INCORRECT = 0; 
  /** first correct */
  public static final int FIRST_CORRECT = 1;
  /** duplicated correct (synonym) */
  public static final int DUP_CORRECT = 2; 
  /** total # of types of correctness (ignoring the unknown) */
  public static final int NUM_CORRECT_TYPES = 3;  
  
  // a storage for weights
  private Map<String, Double> weightMap = null;
  // the canonical name of this entity
  private String[] names;
  // correctness of the entity (assigned by evaluator)
  private int correct = UNKNOWN_CORRECT;
  // total length of names
  private int length = 0;
  // is this a seed entity?
  private boolean isSeed = false;
  
  public static String[] splitRelation(String name) {
    return name.split(Pattern.quote(RELATION_SEPARATOR));
  }
  
  public Entity(Entity entity) {
    if (entity == null) return;
    setNames(entity.getNames());
    setSeed(entity.isSeed());
    setCorrect(entity.getCorrect());
  }
  
  public static Entity parseEntity(String name) {
      String[] names = splitRelation(name);
      switch (names.length) {
      case 1: return new Entity(names[0]);
      case 2: return new Entity(names[0],names[1]);
      }
      log.error("Bad entity string '"+name+"': Entities for parsing should have zero or one instance of the relation delimiter '"+RELATION_SEPARATOR+"'.");
      
      return null;
  }
  
  public Entity(String name) {
      if (name.contains(RELATION_SEPARATOR) && !GlobalVar.getGlobalVar().getExplicitRelations()) {
          log.warn(name+": Creating a relation using the Entity(String) constructor has been disabled. Use Entity.parseEntity(String) instead.");
      }
    setNames(new String[] {name});
  }
  
  public Entity(String name1, String name2) {
    setNames(new String[] {name1, name2});
  }
  
  public Entity(EntityLiteral content) {
      if (content.arg2 == null) setNames(new String[]{content.arg1});
      else setNames(new String[]{content.arg1,content.arg2});
}

public void addWeight(Object feature, double weight) {
    setWeight(feature, getWeight(feature) + weight);
  }
  
  public void clear() {
    if (weightMap != null)
      weightMap.clear();
  }
  
  /**
   * Compare in the order of:
   * 1) descending score
   * 2) ascending length
   * 3) ascending string
   */
  public int compareTo(Entity entity) {
    int result1 = Double.compare(entity.getScore(), getScore());
    if (result1 == 0) {
      int result2 = Double.compare(length(), entity.length());
      return (result2 == 0) ? getName().toString().compareTo(entity.getName().toString()) : result2;
    } else return result1;
  }
  
  public boolean containsFeature(Object feature) {
    return weightMap != null && weightMap.containsKey(feature.toString());
  }
  
  @Override
  public boolean equals(Object obj) {
    if (this == obj) return true;
    if (obj == null) return false;
    if (getClass() != obj.getClass())
      return false;
    final Entity other = (Entity) obj;
    if (!Arrays.equals(names, other.names))
      return false;
    return true;
  }
  
  public int getCorrect() {
    return correct;
  }

  public String getCorrectMarker() {
    switch (correct) {
      case 0: return "-";
      case 1: return "+";
      case 2: return "*";
      default: return "";
    }
  }
  
  public EntityLiteral getName() {
    if (names == null) return null;
    return new EntityLiteral(names);
  }
  
  public String[] getNames() {
    return names;
  }
  
  public String getOriginal() {
    if (names == null) return null;
    String s1 = Originator.getOriginal(names[0]);
    if (names.length == 1) return s1;
    String s2 = Originator.getOriginal(names[1]);
    return s1 + RELATION_SEPARATOR + s2;
  }
  
  public String[] getOriginals() {
    if (names == null) return null;
    String[] array = new String[names.length];
    for (int i = 0; i < names.length; i++)
      array[i] = Originator.getOriginal(names[i]);
    return array;
  }
  
  public double getScore() {
    return getWeight(SCORE);
  }
  
  public double getWeight(Object feature) {
    if (feature == null) return 0;
    if (feature.equals(NAME_LENGTH)) return length();
    if (weightMap == null) return 0;
    Double weight = weightMap.get(feature.toString());
    return weight == null ? 0 : weight;
  }
  
  @Override
  public int hashCode() {
    return 31 + Arrays.hashCode(names);
  }

  /*public boolean isBad() {
    return names == null;
  }*/
  
  public boolean isCorrect() {
    return correct > 0;
  }
  
  public boolean isIncorrect() {
    return correct == INCORRECT;
  }
  
  public boolean isRelational() {
    return names != null && names.length > 1;
  }
  
  public boolean isSeed() {
    return isSeed;
  }

  public int length() {
    return length;
  }

  /**
   * Add all weights of the input entity
   * @param entity
   */
  public void merge(Entity entity) {
    if (entity.weightMap == null) return;
    for (Map.Entry<String, Double> entry : entity.weightMap.entrySet()) {
      String key = entry.getKey();
      addWeight(key, entry.getValue());
    }
  }

  public boolean remove(Object feature) {
    if (weightMap == null) return false;
    return (weightMap.remove(feature.toString()) != null);
  }

  public void setCorrect(int correct) {
    this.correct = correct;
  }
  
  public void setScore(double score) {
    setWeight(SCORE, score);
  }

  public void setSeed(boolean isSeed) {
    this.isSeed = isSeed;
  }

  public void setWeight(Object feature, double weight) {
    if (weightMap == null)
      weightMap = new HashMap<String, Double>();
    weightMap.put(StringFactory.get(feature.toString()), weight);
  }

  @Override
  public String toString() {
    return toString(null);
  }
  
  public String toString(Object feature) {
//    final int NUM_ORIGINALS = 3;
    final int NUM_DECIMAL = 6;
    
    Set<Object> features = new TreeSet<Object>();
    if (weightMap != null) {
      if (feature == null) {
        features.addAll(weightMap.keySet());
        features.remove(Entity.SCORE);
      } else features.add(feature);
    }
    StringBuffer buf = new StringBuffer();
    for (Object f : features) {
      String weightStr = Helper.formatNumber(getWeight(f), NUM_DECIMAL);
      buf.append(f).append(":").append(weightStr).append("\t");
    }
    String scoreStr = Helper.formatNumber(getScore(), NUM_DECIMAL);
    buf.append(scoreStr).append(" ").append(getCorrectMarker());
    String originals = getOriginal();
//    String originals = isRelational() ? getOriginal() : Originator.getOriginals(getName(), NUM_ORIGINALS);
    buf.append(originals);

    return buf.toString();
  }

  // TODO: change from String to SID?
  private void setNames(String[] inputs) {
    if (inputs == null) return;
    length = 0;
    String[] names = new String[inputs.length];
    for (int i = 0; i < inputs.length; i++) {
//      String name = WrapperFactory.tidy(inputs[i]);
      String name = inputs[i];
      if (Helper.empty(name)) return;
      names[i] = StringFactory.get(name);
      length += name.length();
    }
    this.names = names;
  }
} public class EntityList implements Iterable<Entity>, Comparable<EntityList>, Serializable {
  
  public static Logger log = Logger.getLogger(EntityList.class);
  public static GlobalVar gv = GlobalVar.getGlobalVar();
  
  public static final int MAX_SIZE = Cache.DEFAULT_MAX_SIZE;
  public static final double DELTA = 1e-8;
  public static final double OUTLIER_LENGTH_THRESHOLD = 1e-4;
  public static final double DEFAULT_LENGTH_RATIO = 0.1;  // 0.3
  
  public static final double THRESH = 0.1;  // precision at threshold
  public static final int RANK = 100; // precision at rank
  
  private static final long serialVersionUID = 7211782411429869181L;
  
  protected Map<EntityLiteral, Entity> entityMap;
  protected List<Entity> entityList;
  private EvalResult evalResult;
  private double listWeight;
  private int maxEntities;
  
  public EntityList() {
    entityMap = new HashMap<EntityLiteral, Entity>();
    entityList = new ArrayList<Entity>();
    setMaxEntities(WrapperFactory.MAX_CONTENTS_ALLOWED);
  }
  
  public EntityList(Collection<String> entityNames) {
    this();
    addAll(entityNames);
  }
  
  public EntityList(EntityList entityList) {
    this();
    addAll(entityList);
  }
  
  public EntityList(List<Entity> entityList) {
    this();
    addAll(entityList);
  }
  
  public EntityList(Set<Entity> entityList) {
    this();
    addAll(entityList);
  }
  
  /**
   * Remove all entities with a feature that is less than minValue
   * @param feature
   * @param minValue
   */
  public int absoluteFilter(Object feature, double minValue) {
    if (feature == null) return 0;
    boolean[] toRemove = new boolean[size()];
    for (int i = 0; i < size(); i++)
      if (get(i).getWeight(feature) < minValue)
        toRemove[i] = true;

    int numRemoved = remove(toRemove);
    if (numRemoved > 0)
      log.debug(numRemoved + " entities having " + feature + " < " + Helper.formatNumber(minValue, 5) + 
                " were filtered and " + size() + " remaining!");
    return numRemoved;
  }
  
  public Entity add(Entity entity) {
    if (entity == null) return null;
//    if (entity.isBad()) return;
    Entity e = get(entity);
    if (e == entity) return entity;
    
    // overwrites any existing entity
    if (e == null) {
      entityList.add(entity);
    } else {
      int index = entityList.indexOf(entity);
      if (index < 0) {
          log.error(entity.toString()+" not in entityList, but get("+entity.toString()+") returned "+e.toString()+", not entity or null");
      }
      entityList.set(index, entity);
    }
    entityMap.put(entity.getName(), entity);
    evalResult = null;
    return entity;
  }
  
  /**
   * Reduce the size of this list by the following procedure:
   * 1) sort this list by input 'feature' in descending order
   * 2) remove entities ranked lower than or equal to r
   * 3) reduce weight of entities above r by the weight of entity at r
   * where r is the half of MAX_SIZE
   * @param feature
   */
  public void reduceSize(Object feature) {
    if (size() <= MAX_SIZE) return;
    final int SIZE = (int) (MAX_SIZE * 0.5);
    log.info("Number of entities exceeds " + MAX_SIZE + ", reducing it to " + SIZE + "...");
    sortBy(feature, false);
    double midWeight = get(SIZE).getWeight(feature);
    
    for (int i = size()-1; i >= 0; i--) {
      if (i >= SIZE) remove(i);
      else get(i).addWeight(feature, -midWeight);
    }
  }
  
  public Entity add(String name) {
    if (Helper.empty(name)) return null;
//    Entity e1 = new Entity(name);
//    if (e1.isBad()) return null;
//    Entity e2 = get(e1);
//    if (e2 != null) return e2;
//    add(e1);
    Entity e = get(new EntityLiteral(name));
    if (e != null) return e;
    return add(new Entity(name));
  }
  
  public void addAll(Collection<String> names) {
    if (names == null) return;
    for (String name : names)
      add(name);
  }
  
  public void addAll(EntityList entities) {
    if (entities == null) return;
    for (Entity entity : entities)
      add(entity);
    addWeight(entities.getListWeight());
  }
  
  public void addAll(List<Entity> entities) {
    if (entities == null) return;
    for (Entity entity : entities)
      add(entity);
  }
  
  public void addAll(Set<Entity> entities) {
    if (entities == null) return;
    for (Entity entity : entities)
      add(entity);
  }
  
  /**
   * Add a weight to this entity list
   * @param weight
   */
  public void addWeight(double weight) {
    setListWeight(getListWeight() + weight);
  }
  
  /**
   * Add a weight to every entity in this list
   * @param feature
   * @param weight
   */
  public void addWeight(Object feature, double weight) {
    for (Entity entity : entityList)
      entity.addWeight(feature, weight);
  }
  
  public void assignScore(Object feature, boolean hasNoisySeeds) {
    if (feature == null) return;
    
    double maxScore = Double.NEGATIVE_INFINITY;
    double minScore = Double.POSITIVE_INFINITY;
    double weight;
    
    for (Entity entity : entityList) {
      weight = entity.getWeight(feature);
      maxScore = Math.max(weight, maxScore);
      minScore = Math.min(weight, minScore);
    }
    
    // prevents maxScore equals to minScore
    minScore -= DELTA;
    for (Entity entity : entityList) {
      weight = entity.getWeight(feature);
      if (!hasNoisySeeds && entity.isSeed()) // 2008-11-27
        weight = maxScore + weight * DELTA;
      weight = (weight - minScore) / (maxScore + Math.abs(maxScore) * DELTA - minScore);
      entity.setScore(weight);
    }
//    sortBy(Entity.SCORE, false);
  }
  
  public int averageFilter(Object feature) {
    double avg = this.getAverage(feature);
    return absoluteFilter(feature, avg);
  }
  
  public void clear() {
    entityMap.clear();
    entityList.clear();
    evalResult = null;
  }
  
  public int compareTo(EntityList entityList) {
    return Double.compare(entityList.getListWeight(), getListWeight());
  }
  
  public boolean contains(Entity entity) {
    return entityMap.containsKey(entity.getName());
  }
  
//  public boolean contains(String s) {
//    return entityMap.containsKey(s);
//  }
  
  public boolean contains(EntityLiteral e) {
      return entityMap.containsKey(e);
  }
  
  public boolean containsFeature(Object feature) {
    for (Entity entity : this)
      if (!entity.containsFeature(feature))
        return false;
    return true;
  }
  
  public int count(Object feature, double minValue) {
    int count = 0;
    for (Entity entity : this)
      if (entity.getWeight(feature) >= minValue)
        count++;
    return count;
  }
  
  /**
   * For every entity x that is contained by both lists, create a new entity x 
   * having such weight: r*w1 + (1-r)*w2, where w1 and w2 are the weights of an 
   * entity in *this* list and in the input list respectively.
   * @param entityList Input list
   * @param feature
   * @param ratio The proportion of weights taken from weight1 and weight2 for the new entity x.
   * @return A new list of intersected entities
   */
  public EntityList intersect(EntityList entityList, Object feature, double ratio) {
    if (ratio < 0 || ratio > 1)
      throw new IllegalArgumentException("Ratio must be between 0 and 1 (inclusively)");
    EntityList list = new EntityList();
    for (Entity e1 : this) {
      Entity e2 = entityList.get(e1);
      if (e2 == null) continue;
      
      // compute weight and score
      double weight = ratio * e1.getWeight(feature) + (1-ratio) * e2.getWeight(feature);
      if (weight <= 0) continue;
      double score = ratio * e1.getScore() + (1-ratio) * e2.getScore();
      if (score <= 0) continue;
      
      // assign weight and score
      Entity entity = new Entity(e1);
      entity.setWeight(feature, weight);
      entity.setScore(score);
      list.add(entity);
    }
    return list;
  }
  
  @Override
  public boolean equals(Object obj) {
    if (this == obj) return true;
    if (obj == null) return false;
    if (getClass() != obj.getClass())
      return false;
    final EntityList other = (EntityList) obj;
    if (entityMap == null) {
      if (other.entityMap != null)
        return false;
    } else if (!entityMap.keySet().equals(other.entityMap.keySet()))
      return false;
    return true;
  }
  
  /**
   * Computes the Euclidean Distance between entities of this class and the input entities
   * @param entities
   * @param feature
   * @return Euclidean distance
   */
  public double euclideanDistance(EntityList entities, Object feature) {
    Set<Entity> set = new HashSet<Entity>();
    set.addAll(this.getEntities());
    set.addAll(entities.getEntities());
    double sum = 0;
    for (Entity entity : set) {
      Entity e1 = this.get(entity);
      double w1 = (e1 == null) ? 0 : e1.getWeight(feature);
      Entity e2 = entities.get(entity);
      double w2 = (e2 == null) ? 0 : e2.getWeight(feature);
      sum += Math.pow(w1 - w2, 2);
    }
    return Math.sqrt(sum);
  }
  
  /**
   * Use for breaking ties between entities having the same score
   * @param feature
   */
  public void scoreByLength() {
    // calculate average length
    if (isEmpty()) return;
    double avg = getSumLength() / size();

    // calculate standard deviation
    double std = 0;
    for (Entity entity : this)
      std += Math.pow(entity.length() - avg, 2);
    std = Math.sqrt(std / size());
    if (std == 0) return;

    log.info("Diminishing entities with abnormal length (avg: " + Helper.formatNumber(avg, 2) + 
             ", std: " + Helper.formatNumber(std, 2) + ")...");
    
    // assign probability
    for (int i = 0; i < size(); i++) {
      Entity entity = get(i);
      double p = Helper.getPDF(entity.length(), avg, std);
      
      if (p < OUTLIER_LENGTH_THRESHOLD) {
        log.debug("Diminishing \"" + entity.getName() + "\": " + p);
        entity.setScore(0);
      } else {
        // add a very tiny weight to break any tie
        entity.addWeight(Entity.SCORE, p * DELTA);
      }
    }
  }
  
  public void sortByScore() {
    sortBy(Entity.SCORE, false);
  }
  
  /**
   * Filter out relational entities based on the type of relation
   * @param type 0: Many to Many, 1: One to Many, 2: Many to One, 3: One to One
   */
  public void filterRelation(int type) {
    if (!isRelational() || type == 0) return;
    boolean[] toRemove = new boolean[size()];
    Set<String> set = new HashSet<String>();
    
    for (int i = 0; i < size(); i++) {
      String[] names = get(i).getNames();
      
      if (type == 1 || type == 2) {
        String s = (type == 1) ? names[0] : names[1];
        toRemove[i] = !set.add(s);
      } else if (type == 3) {
        toRemove[i] = !set.add(names[0]) || !set.add(names[1]);
      }
    }
    int numRemoved = remove(toRemove);
    if (numRemoved > 0) {
      String s = null;
      switch (type) {
        case 1: s = "One to Many"; break;
        case 2: s = "Many to One"; break;
        case 3: s = "One to One"; break;
      }
      log.info(numRemoved + " entities were removed: relational type of " + type + " (" + s + ")");
    }
  }
  
  public Entity get(Entity entity) {
    return entityMap.get(entity.getName());
  }
  
  public Entity get(int i) {
    return entityList.get(i);
  }
  
  public Entity get(EntityLiteral name) {
      return entityMap.get(name);
  }
  
//  public Entity get(String name) {
//    return entityMap.get(name);
//  }
  
  public double getAverage(Object feature) {
    double sum = this.getSumWeights(feature);
    return sum / this.size();
  }
  
  public List<Entity> getEntities() {
    return entityList;
  }
  
  /**
   * Gather entities containing the input feature
   * @param feature
   * @return
   */
  public EntityList getEntities(Object feature) {
    return getEntities(feature, Double.MIN_VALUE);
  }
  
  /**
   * Gather entities with the input feature having at least some input weight
   * @param feature
   * @param weight
   * @return an EntityList of entities with a feature of at least some weight
   */
  public EntityList getEntities(Object feature, double weight) {
    EntityList list = new EntityList();
    for (Entity entity : this)
      if (entity.containsFeature(feature) && 
          entity.getWeight(feature) >= weight)
        list.add(entity);
    return list;
  }
  
  public List<EntityLiteral> getEntityLiterals() {
      List<EntityLiteral> list = new ArrayList<EntityLiteral>();
      for (Entity entity : entityList)
        list.add(entity.getName());
      return list;
    }
  public List<String[]> getEntityNames() {
    List<String[]> list = new ArrayList<String[]>();
    for (Entity entity : entityList)
      list.add(entity.getNames());
    return list;
  }
  
  public EvalResult getEvalResult() {
    return evalResult;
  }

  public double getListWeight() {
    return listWeight;
  }
  
  public int getMaxEntities() {
    return maxEntities;
  }
  
  public Double getMaxWeight(Object feature) {
    Double maxWeight = null;
    for (Entity entity : entityList) {
      double weight = entity.getWeight(feature);
      if (maxWeight == null) maxWeight = weight;
      else maxWeight = Math.max(weight, maxWeight);
    }
    return maxWeight;
  }
  
  public Integer getMinStringLength() {
    Integer min = null;
    for (Entity entity : this) {
      String[] names = entity.getNames();
      for (String name : names) {
        if (min == null) min = name.length();
        else min = Math.min(name.length(), min);
      }
    }
    return min;
  }
  
  /**
   * Returns the counts of incorrect (0), correct (1), and synonym (2) entities
   * @param threshold count only the entities having
   * 1) a rank higher than threshold (if threshold is at least one), or
   * 2) scores above threshold (if threshold is less than one)
   * @return an array of counts, indexed by the 'correctness' integer (see above)
   */
  public int[] getCorrectness(double threshold) {
    boolean isRank = (threshold >= 1);
    int[] counters = new int[Entity.NUM_CORRECT_TYPES];
    if (threshold <= 0) return counters;
    for (Entity entity : this) {
      if (isRank) {
        if (counters[Entity.INCORRECT] + counters[Entity.FIRST_CORRECT] == threshold) break;
      } else if (entity.getScore() < threshold) break;
      int correctness = entity.getCorrect();
      if (correctness == Entity.UNKNOWN_CORRECT) {
        log.warn("Found an entity with unknown correctness!");
        continue;
      }
      else counters[correctness]++;
    }
    return counters;
  }
  
  public double getPrecision(double threshold, int[] counters) {
    if (counters == null)
      counters = getCorrectness(threshold);
    int total = counters[Entity.INCORRECT] + counters[Entity.FIRST_CORRECT];
    return (total == 0) ? 0 : (double) counters[Entity.FIRST_CORRECT] / total;
  }
  
  public double getRecall(double threshold, int[] counters) {
    int numTrue = evalResult.numGoldEntity;
    if (numTrue <= 0) return 0;
    if (counters == null)
      counters = getCorrectness(threshold);
    return (double) counters[Entity.FIRST_CORRECT] / numTrue;
  }
  
  public double getF1(double threshold, int[] counters) {
    if (counters == null)
      counters = getCorrectness(threshold);
    double p = getPrecision(threshold, counters);
    double r = getRecall(threshold, counters);
    return (p+r == 0) ? 0 : (2*p*r) / (p+r);
  }
  
  public double getSumLength() {
    double sum = 0;
    for (Entity entity : this)
      sum += entity.length();
    return sum;
  }
  
  public double getSumOfLogWeights(Object feature) {
    double sum = 0;
    boolean isLogRanker = Ranker.isLogRanker(feature);
    for (Entity entity : entityList) {
      double weight = entity.getWeight(feature);
      sum += isLogRanker ? weight : Math.log(weight);
    }
    return sum;
  }
  
  public double getSumWeights(Object feature) {
    double sum = 0;
    for (Entity entity : entityList)
      sum += entity.getWeight(feature);
    return sum;
  }
  
  /**
   * Returns top entities
   * 1) having at least minEntities and at most maxEntities
   * 2) where each feature weight is at least the input threshold
   * @param feature
   * @param threshold
//   * @param minEntities
   * @param maxEntities
   * @return a sorted EntityList object
   */
//  public EntityList getTopEntities(Object feature, double threshold, int minEntities, int maxEntities) {
  public EntityList getTopEntities(Object feature, double threshold, int maxEntities) {
    EntityList list = this.getEntities(feature, threshold);
    /*if (list.size() < minEntities) {
      list = new EntityList(this);
      list.sortBy(feature, false);
      return list.subList(0, minEntities);
    } else {*/
      list.sortBy(feature, false);
      if (list.size() > maxEntities)
        return list.subList(0, maxEntities);
      else return list;
//    }
  }
  
  @Override
  public int hashCode() {
    return 31 + (entityMap == null ? 0 : entityMap.hashCode());
  }

  public boolean hasSpace() {
    for (Entity entity : this)
      if (entity.getName().toString().contains(" "))
        return true;
    return false;
  }
  
  /**
   * Preserves the order of the EntityList in this object
   * Retains weights of the entities in this object
   * @param entityList
   * @return overlapping entities of the input list and this class
   */
  public EntityList intersect(EntityList entityList) {
    EntityList list = new EntityList();
    for (Entity entity : this)
      if (entityList.contains(entity))
        list.add(entity);
    return list;
  }
  
  public boolean isEmpty() {
    return size() == 0;
  }
  
  public boolean isIntersected(EntityList entityList) {
    EntityList smaller = entityList, larger = this;
    if (this.size() < entityList.size()) {
      smaller = this;
      larger = entityList;
    }
    for (Entity entity : smaller)
      if (larger.contains(entity))
        return true;
    return false;
  }
  
  public boolean isRelational() {
    for (Entity entity : this)
      if (!entity.isRelational())
        return false;
    return true;
  }
  
  public Iterator<Entity> iterator() {
    return entityList.iterator();
  }
  
  public void merge(Entity entity) {
    Entity e = get(entity);
    if (e == null) add(entity);
    else e.merge(entity);
  }
  
  public void merge(EntityList entityList) {
    for (Entity entity : entityList)
      merge(entity);
  }
  
  public void normalize(Object feature) {
    double sum = getSumWeights(feature);
    if (sum == 0) return;
    for (Entity entity : this) {
      double weight = entity.getWeight(feature);
      if (weight < 0) {
        log.warn("Warn: " + entity.getName() + " contains negative weight of " + weight + " for feature: " + feature);
        continue;
      }
      entity.setWeight(feature, weight/sum);
    }
  }
  
  public void clearWeight(Object feature) {
    if (feature == null) return;
    for (Entity entity : this)
      entity.remove(feature);
  }

  public EntityList product(EntityList entityList, Object feature) {
    EntityList list = new EntityList();
    for (Entity e1 : this) {
      Entity e2 = entityList.get(e1);
      if (e2 == null) continue;
      double weight = e1.getWeight(feature) * e2.getWeight(feature);
      if (weight <= 0) continue;
      Entity entity = new Entity(e1);
      entity.setWeight(feature, weight);
      list.add(entity);
    }
    return list;
  }
  
  public int relativeFilter(Object feature, double ratio) {
    if (feature == null || ratio <= 0) return 0;
    Double maxWeight = getMaxWeight(feature);
    if (maxWeight == null) return 0;
    return absoluteFilter(feature, maxWeight * ratio);
  }
  
  /**
   * remove those marked entities
   * @param toRemove
   */
  public int remove(boolean[] toRemove) {
    if (toRemove == null) return 0;
    int size = Math.min(entityList.size(), toRemove.length);
    int offset = 0;
    
    for (int i = 0; i < size; i++) {
      if (!toRemove[i]) continue;
//      log.debug("Removing: " + entityList.get(i-offset).getName());
      remove(i-offset);
      offset++;
    }
    return offset;
  }
  
  public void remove(Entity entity) {
    if (entity == null) return;
    entityList.remove(entity);
    entityMap.remove(entity.getName());
  }
  
  public Entity remove(int i) {
    Entity entity = entityList.remove(i);
    entityMap.remove(entity.getName());
    return entity;
  }
  
  public void remove(Object feature) {
    for (Entity entity : this)
      entity.remove(feature);
  }
  
  public void remove(String entity) {
    if (entity == null) return;
    entityList.remove(entity);
    entityMap.remove(entity);
  }
  
  public void removeAll(EntityList list) {
    if (list == null) return;
    for (Entity entity : list)
      this.remove(entity);
  }
  
  public int removeAll(Object feature) {
    int sum = 0;
    for (Entity entity : entityList)
      sum += entity.remove(feature) ? 1 : 0;
    return sum;
  }
  
  public void removeContains(String superStr) {
    if (superStr == null) return;
    boolean[] toRemove = new boolean[this.size()];
    for (int i = 0; i < this.size(); i++) {
      String s = this.get(i).getName().toString();
      toRemove[i] = superStr.contains(s);
    }
    remove(toRemove);
  }

  public void setEvalResult(EvalResult evalResult) {
    this.evalResult = evalResult;
  }

  /**
   * Set the weight of this entity list
   * @param weight
   */
  public void setListWeight(double weight) {
    this.listWeight = weight;
  }
  
  public void setMaxEntities(int maxEntitiesInXML) {
    this.maxEntities = maxEntitiesInXML;
  }
  
  /**
   * Set weight to all entities in this list
   * @param feature
   * @param weight
   */
  public void setWeight(Object feature, double weight) {
    for (Entity entity : this)
      entity.setWeight(feature, weight);
  }
  
  public void shrink(Object feature, double shrinkPower) {
    shrink(feature, shrinkPower, DEFAULT_LENGTH_RATIO);
  }
  
  /**
   * Collapse a sorted list of entities, from top to bottom
   * Reduce the number of entities to maxEntities
   * @param byNameLength true to pre-sort by string length, otherwise by score, then collapse!
   * @param entityList
   * @return
   */
  public void shrink(Object feature, double shrinkPower, double lengthRatio) {
    log.info("Shrinking list with a shrinking power of " + shrinkPower + 
             " and length ratio of " + lengthRatio + "...");
    if (size() <= 1) return;
//    boolean[] toRemove = new boolean[size()];
    String hasSpace = hasSpace() ? " " : "";
    sortByNameLength(false);
    
    for (int i = 0; i < size(); i++) {
      Entity e1 = get(i);
      String name1 = e1.getName().toString();
      double w1 = e1.getWeight(feature);
      
      for (int j = i+1; j < size(); j++) {
//        if (toRemove[j]) continue;
        Entity e2 = get(j);
        double w2 = e2.getWeight(feature);
        if (w2 == 0) continue;
        String name2 = e2.getName().toString();

        if (name1.length() <= name2.length()) continue;
        if (w1 * shrinkPower <= w2) continue;
        double z = (double) name2.length() / name1.length();
        if (z < lengthRatio) continue;
        
        if (name1.startsWith(name2 + hasSpace) || 
            name1.endsWith(hasSpace + name2)) {
          log.debug(name1 + " (" + feature + ": " + Helper.formatNumber(w1, 5) + ") ===> " + 
                    name2 + " (" + feature + ": " + Helper.formatNumber(w2, 5) + ")");
          if (w2 > w1) {
            // assign first entity the weight of second entity
            e1.setWeight(feature, w2);
            e2.setWeight(feature, 0);
          }
//          toRemove[j] = true;
        }
      }
    }
    /*int numRemoved = remove(toRemove);
    if (numRemoved > 0)
      log.info(numRemoved + " entities were shrunk and " + size() + " remaining!");*/
    sortBy(feature, false);
  }
  
  public void shuffle(Random random) {
    if (random == null) return;
    Collections.shuffle(entityList, random);
  }
  
  public int size() {
    return entityList.size();
  }

  public void sort() {
    sortBy(Entity.SCORE, false);
  }

  public void sortBy(final Object feature, final boolean ascending) {
    Comparator<Entity> c = new Comparator<Entity>() {
      public int compare(Entity e1, Entity e2) {
        double w1 = e1.getWeight(feature), w2 = e2.getWeight(feature);
        if (ascending) return Double.compare(w1, w2);
        else return Double.compare(w2, w1);
      }
    };
    sortBy(c, feature, ascending);
  }
  
  public void sortByNameLength(final boolean ascending) {
    sortBy(Entity.NAME_LENGTH, ascending);
  }
  
  public EntityList subList(int fromIndex, int toIndex) {
    EntityList subList = new EntityList();
    toIndex = Math.min(toIndex, entityList.size());
    for (int i = fromIndex; i < toIndex; i++)
      subList.add(entityList.get(i));
    return subList;
  }
  
  public String toDetails(int numTop) {
    return toDetails(numTop, null);
  }
  
  public String getOneLineStat() {
    StringBuffer buf = new StringBuffer("[ ");
    String map = Helper.formatNumber(evalResult.meanAvgPrecision*100, 2);
    buf.append("MAP: ").append(map).append(", ");
    
    String pRank = Helper.formatNumber(getPrecision(RANK, null)*100, 2);
    buf.append("P@" + RANK + ": ").append(pRank).append(", ");
    
    int[] counters = getCorrectness(THRESH);
    int num = counters[Entity.FIRST_CORRECT] + counters[Entity.INCORRECT];
    double p = getPrecision(THRESH, counters), r = getRecall(THRESH, counters);
    String pStr = Helper.formatNumber(p*100, 2), rStr = Helper.formatNumber(r*100, 2);
    String f1Str = Helper.formatNumber(getF1(THRESH, counters)*100, 2);
    buf.append("F1@" + THRESH + ": ").append(f1Str).append(" ");
    buf.append("(P:").append(pStr).append(", ");
    buf.append("R:").append(rStr).append(", ");
    buf.append("#:").append(num).append(")");
    return buf.append(" ]").toString();
  }
  
  public String toDetails(int numTop, Object feature) {
    final int LINE_WIDTH = 80;
    numTop = Math.min(numTop, entityList.size());
    
//    StringBuffer buf = new StringBuffer("\n");
    StringBuffer buf = new StringBuffer();
    String title = "[ Listing " + numTop + " out of " + entityList.size() + " Entities ]";
    buf.append("\t").append(Helper.center(title, '-', 80)).append("\n");
    for (int i = 0; i < numTop; i++) {
      Entity entity = entityList.get(i);
      buf.append(i+1).append(".\t");
      buf.append(entity.toString(feature)).append("\n");
    }
    buf.append("\t");
    if (evalResult != null) {
      buf.append(Helper.center(getOneLineStat(), '-', LINE_WIDTH));
    } else {
      buf.append(Helper.repeat('-', LINE_WIDTH));
    }
    return buf.toString();
  }

  /**
   * Returns a list of entities sorted in score order
   */
  public String toString() {
    Set<Entity> entities = new TreeSet<Entity>();
    entities.addAll(getEntities());
    
    StringBuffer buf = new StringBuffer();
    for (Entity entity : entities) {
      if (buf.length() > 0) buf.append(", ");
      buf.append(entity.getCorrectMarker()).append(entity.getName());
    }
    return buf.toString();
  }
  
  public String toXML() {
    return XMLUtil.document2String(toXMLElement(null));
  }
  
  public Element toXMLElement(Document document) {
    XMLUtil xml = new XMLUtil(document);
    Element entitiesNode = xml.createElement("entities", null);
    xml.createAttrsFor(entitiesNode, new Object[]{
        "numEntities", entityList.size(),
    });
    int rank = 1;
    for (Entity entity : entityList) {
      // reduce the amount of garbage saved to the disk
      if (rank > maxEntities) break;
      
      List<Object> pairs = Ranker.toFeatureValuePairs(entity);
      pairs.add("rank"); pairs.add(rank++);
      pairs.add("score"); pairs.add(entity.getScore());
      if (entity.getCorrect() != -1) {
        pairs.add("correct"); pairs.add(entity.getCorrect());
      }
      Element entityNode = xml.createElementBelow(entitiesNode, "entity", entity.getOriginal());
      xml.createAttrsFor(entityNode, pairs.toArray(new Object[pairs.size()]));
    }
    return entitiesNode;
  }

  public void transferWeight(Object from, Object to) {
    for (Entity entity : this)
      entity.setWeight(to, entity.getWeight(from));
  }

  private void sortBy(Comparator<Entity> c, Object feature, boolean ascending) {
    log.debug("Sorting entities by " + feature + " in " + (ascending ? "a" : "de") + "scending order...");
    Collections.sort(entityList, c);
  }

    public Entity add(EntityLiteral content) {
        Entity e = new Entity(content);
        return add(e);
    }
} public class GoogleSets extends SetExpander {
  
  public static final Pattern EXTRACTION_PAT = Pattern.compile("\">([^<>]+)</a></font></center></td></tr>");
  public static final String GOOGLE_SET_URL = "http://labs.google.com/sets?hl=en&btn=";
  public static final String LARGE_SET = "Large+Set"; // returns about 50 entities
  public static final String SMALL_SET = "Small"; // returns about 15 entities
//  public static final Feature FEATURE = Feature.GSW;
  public static final String FEATURE = "GSW";
  public static final int NUM_MAX_RETRY = 3;
  public static final long WAIT_TIME = 3000;
  public static Logger log = Logger.getLogger(GoogleSets.class);
  
  private static final long serialVersionUID = -3457290506126642298L;
  private boolean isLargeSet;
  
  public GoogleSets() {
    super();
    setLargeSet(true);
  }
  
  public boolean expand(EntityList seeds) {
//    numNewEntities = 0;
    numLastEntities = 0;

    if (seeds.isEmpty()) {
      log.error("Need at least one seed!");
      return false;
    }
    setStartTime();
    log.info(this.getClass().getSimpleName() + " is expanding " + seeds.toString() + "...");
    String document = getResultPage(seeds.getEntityLiterals());
    if (document == null) {
      setEndTime();
      return false;
    }
//    numNewEntities = getNumEntities();
    extractEntities(document);
//    numNewEntities = getNumEntities() - numNewEntities;
    setSeeds(seeds);
    entityList.assignScore(FEATURE, hasNoisySeeds());
    entityList.sortByScore();
    setEndTime();
    return true;
  }
  
  public static URL getQueryURL(Collection<String> seeds, boolean isLargeSet) {
    String base = GOOGLE_SET_URL + (isLargeSet ? LARGE_SET : SMALL_SET);
    StringBuffer buf = new StringBuffer(base);
    if (seeds.size() == 0) {
      log.error("No seeds to expand!");
      return null;
    }

    int i = 1;
    for (String seed : seeds)
      buf.append("&q").append(i++).append("=").append(Helper.encodeURLString(seed));
    URL url = null;
    try {
      url = new URL(buf.toString());
    } catch (MalformedURLException e) {
      log.error("Malformed URL: " + buf.toString());
      return null;
    }
    return url;
  }

  public boolean isLargeSet() {
    return isLargeSet;
  }

  public void setLargeSet(boolean useLargeSet) {
    this.isLargeSet = useLargeSet;
  }
  
  /**
   * @return expansion results in XML format
   */
  public Element toXMLElement() {
    XMLUtil xml = new XMLUtil();

    // response node is the top node
    Element responseNode = xml.createElement("response", null);
    xml.createAttrsFor(responseNode, new Object[]{
        "elapsedTimeInMS", getElapsedTime()
    });

    // setting node
    Element settingNode = xml.createElement("setting", null);
    Element seedsNode = xml.createElementBelow(settingNode, "seeds", null);
    for (Entity seed : lastSeeds)
      xml.createElementBelow(seedsNode, "seed", seed.getName().toString());

    responseNode.appendChild(settingNode);
    responseNode.appendChild(entityList.toXMLElement(xml.getDocument()));
    return responseNode;
  }

  private void extractEntities(String document) {
    Matcher m = EXTRACTION_PAT.matcher(document);
    List<String> contentList = new ArrayList<String>();
    while (m.find()) {
      String content = m.group(1).toLowerCase().trim();
      if (content.length() > 0)
        contentList.add(content);
    }
    for (int i = 0; i < contentList.size(); i++) {
      EntityLiteral content = new EntityLiteral(contentList.get(i));
      Entity entity = entityList.get(content);
      if (entity == null)
        entity = entityList.add(content);
      double weight = 1 - (double) i / contentList.size();
      entity.addWeight(FEATURE, weight);
      if (!hasNoisySeeds() && lastSeeds.contains(content))
        entity.setSeed(true);
    }
    numLastEntities = new HashSet<String>(contentList).size();
//    entityList.addAssignedFeature(FEATURE);
  }

  private String getResultPage(Collection<EntityLiteral> eseeds) {
      Collection<String> seeds = new TreeSet<String>();
      for (EntityLiteral e : eseeds) seeds.add(e.toString());
//  }
//  
//  private String getResultPage(Collection<String> seeds) {
    URL url = getQueryURL(seeds, isLargeSet());
    if (url == null) return null;
    String className = this.getClass().getSimpleName();
    log.debug(className + " is fetching: " + url);
    String document = null;
    WebManager webManager = new WebManager();
    for (int numRetries = 0; numRetries < NUM_MAX_RETRY; numRetries++) {
      document = webManager.get(url);
      if (document == null) {
        log.error("[Attempt: " + (numRetries+1) + "/" + NUM_MAX_RETRY + "] " + 
                  className + " failed to connect to Google Sets!");
        log.error("Sleeping for " + WAIT_TIME + " milliseconds...");
        try {
          Thread.sleep(WAIT_TIME);
        } catch (InterruptedException e) {}
      } else break;
    }
    return document;
  }
}
 public class Seal extends Pinniped {
  
  /********************** Parameters **************************/
  public static boolean readSerializedDocs = true;
  public static boolean writeSerializedDocs = false;
  /************************************************************/

  public static Logger log = Logger.getLogger(Seal.class);
  public static GlobalVar gv = GlobalVar.getGlobalVar();
  
  public static final String SERIAL_DIR = "cache";
  public static final String SERIAL_FILENAME_EXT = ".ser";

  private Graph graph;
  private Ranker ranker;
  private DocumentSet lastDocs;
  private WrapperFactory wrapperFactory;
  private String extractLangID;
  private String fetchLangID;
  private double logWrapperLength;
  private boolean disableWalk;
  private int numLastWrappers;
  private int numPastWrappers;
  private int numPastDocs;
  private int numResults;
  private int engine;

  public static DocumentSet fetch(EntityList seeds, String hint, String langID, 
                                  int numResults, int engine) {
    log.info("Retrieving webpages using " + seeds.size() + " queries: {" + seeds + "}");
    if (!Helper.empty(hint))
      log.info("\tand a hint: " + hint);
    
    WebFetcher webFetcher = new WebFetcher();
    webFetcher.setLangID(langID);
    webFetcher.setNumResults(numResults);
    webFetcher.setUseEngine(engine);
    DocumentSet documents = webFetcher.fetchDocuments(seeds, hint);
//    DocumentSet documents = webFetcher.fetchDocuments(seeds, hint);
    int numUrlsToFetch = webFetcher.getSnippets().size();
    int numUrlsFetched = documents.size();
    
    // output the percentage of URLs fetched
    double pctPageRetrieved = (numUrlsToFetch == 0) ? 0 : (double) numUrlsFetched / numUrlsToFetch;
    log.info("Number of webpages retrieved: " + numUrlsFetched + " out of " + numUrlsToFetch + 
             " (" + Helper.formatNumber(pctPageRetrieved*100, 1) + "%)");
    return documents;
  }
  
  public static void main(String args[]) {
    long startTime = System.currentTimeMillis();

    // parse the command line argument
    if (args.length == 0) {
      log.error("Incorrect arguments in the command line");
      log.info("Usage 1: java " + Seal.class.getName() + " seed_file [hint_file]");
      log.info("Usage 2: java " + Seal.class.getName() + " seed_1 seed_2 ...");
      return;
    }

    File seedFile = new File(args[0]);
    String[] seedArr;
    String hint = null;
    if (seedFile.exists()) {
      seedArr = Helper.readFile(seedFile).split("\n");
      if (args.length >= 2) {
        File hintFile = Helper.toFileOrDie(args[1]);
        hint = Helper.readFile(hintFile).replaceAll("[\r\n]+", " ");
      }
    } else {
      for (int i = 0; i < args.length; i++)
        args[i] = args[i].replace('_', ' ');
      seedArr = args;
    }
    EntityList seeds = new EntityList();
    for (String s : seedArr) seeds.add(Entity.parseEntity(s));
    
    Seal seal = new Seal();
    seal.expand(seeds, seeds, hint);
    seal.save();//Results();
    
    log.info(seal.getEntityList().toDetails(100, seal.getFeature()));
    Helper.printMemoryUsed();
    Helper.printElapsedTime(startTime);
  }
  
  private static File getSerialFile(EntityList seeds, String hint) {
    final int prime = 31;
    int result = 1;
    result = prime * result + ((seeds == null) ? 0 : seeds.hashCode());
    result = prime * result + ((hint == null) ? 0 : hint.hashCode());
    String filename = Integer.toString(Math.abs(result)) + SERIAL_FILENAME_EXT;
    return new File(SERIAL_DIR, filename);
  }
  
  public Seal() {
    super();
    wrapperFactory = new WrapperFactory();
    loadStopwords(gv.getStopwordsList());
    
    // initialize some parameters
    setLangID(gv.getLangID());
    setFeature(gv.getFeature());
    setEngine(gv.getUseEngine());
    setNumResults(gv.getNumResults());
    setMinContextLength(gv.getMinContextLength());
    setMinSeedsBracketed(gv.getMinSeedsBracketed());
    URLBlackLister.setListFile(gv.getUrlBlackList());
  }
  
  public Seal(String langID) {
    this();
    setLangID(langID);
  }
  
  public void addStopword(String stopword, boolean isUnigram) {
    wrapperFactory.addStopword(stopword, isUnigram);
  }
  
  public void addStopwords(Collection<String> stopwords, boolean isUnigram) {
    wrapperFactory.addStopwords(stopwords, isUnigram);
  }
  
  /**
   * reset for a totally new round of expansion/bootstrapping
   */
  public void clear() {
    super.clear();
    ranker.clear();
    lastDocs = null;
  }
  
  public boolean expand(EntityList seeds) {
    return expand(seeds, seeds, null);
  }
  
  public boolean expand(EntityList seeds, DocumentSet documents) {
    numLastEntities = 0;
    numLastWrappers = 0;

    this.lastDocs = documents;
    
    if (seeds == null || seeds.isEmpty()) {
      log.error("Error: Need at least one wrapper seed!");
      return false;
    } else if (documents == null || documents.size() == 0) {
      log.error("Error: No webpages provided for set expansion!");
      return false;
    }
    
    // output expansion information
    String className = this.getClass().getSimpleName();
    log.info(className + " is bracketing " + PairedTrie.toMinTypeStr(getMinSeedsBracketed()) + " of the " + seeds.size() + " wrapper seeds:");
    log.info("{" + seeds + "}");
    
    setStartTime();
    // associate wrappers with documents
    extract(seeds, documents);
    
    if (numPastWrappers > 0)
        log.info("Estimated List Quality: " + Helper.formatNumber(getListQuality(), 3));
    else log.info("No results!");
    
    // load documents into the ranker
    rank(seeds, documents);
    
    entityList.assignScore(getFeature(), hasNoisySeeds());
    entityList.scoreByLength(); // break any ties
    entityList.sortByScore();

    setSeeds(seeds);  // must be after rank()
    setEndTime();
    return true;
  }
  
  public boolean expand(EntityList wrapperSeeds, EntityList pageSeeds, String hint) {
    return expand(wrapperSeeds, readDocuments(pageSeeds, hint));
  }
  
  public int getEngine() {
    return engine;
  }
  
  public String getExtractLangID() {
    return extractLangID;
  }
  
  public Feature getFeature() {
    return getRanker().getRankerID();
  }

  public String getFetchLangID() {
    return fetchLangID;
  }

  public Graph getGraph() {
    return graph;
  }

  public DocumentSet getLastDocs() {
    return lastDocs;
  }

  public double getListQuality() {
    return logWrapperLength / numPastWrappers;
  }

  public int getMinContextLength() {
    return wrapperFactory.getMinContextLength();
  }

  public int getMinSeedsBracketed() {
    return wrapperFactory.getMinSeedsBracketed();
  }

  public int getNumLastWrappers() {
    return numLastWrappers;
  }

  public int getNumPastDocs() {
    return numPastDocs;
  }

  public int getNumPastWrappers() {
    return numPastWrappers;
  }
  
  public int getNumResults() {
    return numResults;
  }

  public Ranker getRanker() {
    return ranker;
  }

  public boolean isDisableWalk() {
    return disableWalk;
  }

  public void loadStopwords(File stopwordsFile) {
    wrapperFactory.loadStopwords(stopwordsFile);
  }

  public void setDisableWalk(boolean disableWalk) {
    this.disableWalk = disableWalk;
  }

  public void setEngine(int useEngine) {
    this.engine = useEngine;
  }

  public void setExtractLangID(String extractLangID) {
    this.extractLangID = extractLangID;
  }
  
  public void setFeature(Feature feature) {
    this.ranker = Ranker.toRanker(feature);
  }
  
  public void setFetchLangID(String fetchLangID) {
    this.fetchLangID = fetchLangID;
  }

  public void setLangID(String langID) {
    extractLangID = langID;
    fetchLangID = langID;
  }

  public void setMinContextLength(int minContextLength) {
    wrapperFactory.setMinContextLength(minContextLength);
  }

  public void setMinSeedsBracketed(int minSeedsBracketed) {
    wrapperFactory.setMinSeedsBracketed(minSeedsBracketed);
  }

  public void setNumResults(int numResults) {
    this.numResults = numResults;
  }

  public Element toXMLElement() {
    return toXMLElement(null);
  }

  /**
   * @return expansion results in XML format
   */
  public Element toXMLElement(org.w3c.dom.Document document) {
    XMLUtil xml = new XMLUtil(document);

    // response node is the top node
    Element responseNode = xml.createElement("response", null);
    xml.createAttrsFor(responseNode, new Object[]{
        "elapsedTimeInMS", getElapsedTime()
    });

    // setting node
    Element settingNode = xml.createElement("setting", null);
    Element seedsNode = xml.createElementBelow(settingNode, "seeds", null);
    for (Entity seed : lastSeeds)
      xml.createElementBelow(seedsNode, "seed", seed.getOriginal());
//    xml.createElementBelow(settingNode, "hint", hint == null ? "" : hint);
    xml.createElementBelow(settingNode, "extract-language", extractLangID);
    xml.createElementBelow(settingNode, "fetch-language", fetchLangID);

    responseNode.appendChild(settingNode);
//    responseNode.appendChild(pastDocs.toXMLElement(xml.getDocument()));
    responseNode.appendChild(entityList.toXMLElement(xml.getDocument()));       
    if (gv.getWrapperSaving()==1) {
        // save the wrappers in this xml node  
        WrapperSaver wrapperSaver = new WrapperSaver();
        responseNode.appendChild(wrapperSaver.toXMLElement(xml.getDocument(),lastDocs,entityList,lastSeeds));
    }
    return responseNode;
  }

  private void addSeedsToRanker(EntityList seeds, Ranker ranker) {
    if (seeds == null || ranker == null) return;
    
    if (pastSeeds.isEmpty()) {
      // no seeds have been given before
      if (seeds.containsFeature(getFeature())) {
        log.info("Using seed weights from input seeds...");
        ranker.addSeeds(seeds, getFeature());
      } else {
        log.info("Seeds are missing " + getFeature() + " weights, using uniform weights...");
        ranker.addUniformSeeds(seeds);
      }
    } else {
      // there are some previously expanded seeds
      log.info("Using seed weights from previously expanded entities...");
      
      // constructs a union of current seeds and past seeds
      EntityList newSeeds = new EntityList();
      newSeeds.addAll(seeds);
      newSeeds.addAll(pastSeeds);
      
      // the weights of those seeds come from their corresponding entities in last expansion
      ranker.addSeeds(entityList.intersect(newSeeds), getFeature());
    }
  }

  private Set<EntityLiteral> extract(EntityList seeds, DocumentSet documents) {
    // configure wrapper factory
    wrapperFactory.setSeeds(seeds);
    wrapperFactory.setLangID(extractLangID);
    wrapperFactory.setFeature(getFeature());
    
    int prevPercent = -1;
    Set<EntityLiteral> contents = new HashSet<EntityLiteral>();
    
    for (int i = 0; i < documents.size(); i++) {
      Document document = documents.get(i);
      
      // progress bar
      int percent = (int) ((double)(i+1)/documents.size()*100);
      if (percent != prevPercent) {
        log.info("Extracting from " + (i+1) + "/" + documents.size() + " (" + percent + "%) documents...");
        prevPercent = percent;
      }

      if (document.isEmpty()) continue;
      Set<Wrapper> wrappers = wrapperFactory.build(document);
      if (wrappers.isEmpty()) continue;

      numLastWrappers += wrappers.size();
      numPastWrappers += wrappers.size();
      document.addWrappers(wrappers);

      for (Wrapper wrapper : wrappers) {
        logWrapperLength += wrapper.getNumCommonTypes() * Math.log(wrapper.getContextLength());
        contents.addAll(wrapper.getContents());
      }
    }
    numPastDocs += documents.size();
    numLastEntities = contents.size();
    return contents;
  }

  /**
   * assigns scores to each entity and document based on the scoring method
   */
  private boolean rank(EntityList seeds, DocumentSet documents) {
    if (ranker == null) {
      log.error("Error: Feature is not specified!");
      return false;
    }
    
    // get the graph (added 12/10/2008)
    if (ranker instanceof GraphRanker) {
      graph = ((GraphRanker) ranker).getGraph();
      if (disableWalk) {
        graph.load(documents);
        return true;
      }
    }
    
    // PageRank starts from all nodes with uniform weights, so no need seeds
    if (!(ranker instanceof PageRanker))
      addSeedsToRanker(seeds, ranker);

    log.info("Ranking entities by " + getFeature() + " (" + ranker.getDescription() + ")" + 
             " and " + ranker.getSeedDist().size() + " seeds...");
    
    ranker.load(entityList, documents);
    return true;
  }

  private DocumentSet readDocuments(EntityList seeds, String hint) {
    if (Helper.empty(seeds)) return null;
    
    File serialFile = getSerialFile(seeds, hint);
    DocumentSet documents = null;

    if (readSerializedDocs && serialFile.exists()) {
      // documents exist in cache as serialized object
      documents = Helper.loadSerialized(serialFile, lastDocs.getClass());
      log.info("Successfully loaded " + documents.size() + " webpages!");
    } else {
      // download documents from the web
      documents = fetch(seeds, hint, fetchLangID, numResults, engine);
      if (writeSerializedDocs)
        Helper.saveSerialized(documents, serialFile, true);
    }
    return documents;
  }
}
 public abstract class SetExpander {

  public static final String XML_EXT = ".xml";
  public static Logger log = Logger.getLogger(SetExpander.class);
  public static GlobalVar gv = GlobalVar.getGlobalVar();
  
  private File resultDir;
  
  protected EntityList lastSeeds;
  protected EntityList pastSeeds;
  protected EntityList entityList;
//  protected int numNewEntities = 0;
  protected int numLastEntities = 0;
  protected long startTime = 0;
  protected long endTime = 0;
  protected boolean hasNoisySeeds;
//  protected String langID;
//  protected Feature feature;

  public SetExpander() {
    lastSeeds = new EntityList();
    pastSeeds = new EntityList();
    entityList = new EntityList();
    setHasNoisySeeds(gv.hasNoisySeeds());
    setResultDir(gv.getResultDir());
//    setLangID(gv.getLangID());
//    setFeature(gv.getFeature());
  }
  
  /**
   * A dummy method
   * @param feature
   * @return true
   */
  public boolean assignWeights(Feature feature) {
    return true;
  }

  public void clear() {
    lastSeeds.clear();
    pastSeeds.clear();
    entityList.clear();
  }
  
  /*public void clearPastSeeds() {
    pastSeeds.clear();
  }*/

  public abstract boolean expand(EntityList seeds);
  
  public long getElapsedTime() {
    return (startTime > endTime) ? 0 : endTime - startTime; // in milliseconds
  }
  
  public List<Entity> getEntities() {
    return getEntityList().getEntities();
  }

//  public Entity getEntity(String name) {
//    return entityList.get(name);
//  }
  
  public EntityList getEntityList() {
    /*if (entityList.size() > 1 && entityList.getSortByFeature() == null) {
      log.warn("Entities have not been assigned weights! They are randomly ordered.");
      log.warn("Please use SetExpander.assignWeights(ScoringMethod feature)");
    }*/
    return entityList;
  }
  
  /*public Feature getFeature() {
    return feature;
  }*/
  
  public EntityList getPastSeeds() {
    return pastSeeds;
  }
  
  /*public String getLangID() {
    return langID;
  }*/
  
  public EntityList getLastSeeds() {
    return lastSeeds;
  }
  
  public int getNumEntities() {
    return entityList.size();
  }
  
  public int getNumLastEntities() {
    return numLastEntities;
  }
  
  /*public int getNumNewEntities() {
    return numNewEntities;
  }*/

  public File getResultDir() {
    return resultDir;
  }
  
  public boolean hasNoisySeeds() {
    return hasNoisySeeds;
  }

  public boolean isEmpty() {
    return entityList.isEmpty();
  }
  
  /**
   * Constructs a file name, allowing user to specify what should be included in the name
   * @param anything any String
   * @param useNumEntities true to include number of extracted entities
   * @param useSeeds true to include current seeds only (not seeds used in past rounds)
   * @return a file name String
   */
  public String makeFileName(String anything, boolean useNumEntities, boolean useSeeds) {
    StringBuffer buf = new StringBuffer();
//    Object feature = entityList.getSortByFeature();
//    if (feature != null)
//      buf.append(feature.toString().toLowerCase()).append(".");
    if (anything != null)
      buf.append(anything).append(".");
    if (useNumEntities)
      buf.append(entityList.size()).append(".");
    if (useSeeds)
      buf.append(Math.abs(lastSeeds.hashCode())).append(".");
    if (buf.length() == 0)
      return null;
    return buf.substring(0, buf.length()-1);
  }

  
  public void save() {
      saveResults();
      saveWrappers();
  }
  /**
   * Saves results in XML format using an automatic generated file name
   * @return saved file
   */
  public File saveResults() {
    return saveResults(makeFileName(null, true, true));
  }
  
  public File saveResults(File file) {
    if (file == null) return null;
    String xmlResult = toXML();
    if (xmlResult == null) return null;
    Helper.createDir(file.getParentFile());
    log.info("Saving results XML to: " + file);
    file.delete();
    Helper.writeToFile(file, xmlResult);
    return file;
  }
  

  /**
   * Saves results in XML format using a user specified file name
   * @param filename Name of the output file (without extension)
   * @return saved file
   */
  public File saveResults(String filename) {
    if (filename == null) return null;
    if (resultDir == null) return null;
    File resultFile = new File(resultDir, filename + XML_EXT);
    return saveResults(resultFile);
  }
  

  public void saveWrappers() {
      if (gv.getWrapperSaving()==2) {
          WrapperSaver wrapperSaver = new WrapperSaver();
          wrapperSaver.saveAsDocuments(gv.getSavedWrapperDir(),this.getLastDocs(),entityList,lastSeeds);
      }
  }

  /*public void setFeature(Feature feature) {
    this.feature = feature;
  }*/

  public void setHasNoisySeeds(boolean hasNoisySeeds) {
    this.hasNoisySeeds = hasNoisySeeds;
  }

  /*public void setLangID(String langID) {
    this.langID = langID;
  }*/

  public void setResultDir(File resultDir) {
    this.resultDir = resultDir;
  }

  public String toXML() {
    return XMLUtil.document2String(toXMLElement());
  }

  protected void setEndTime() {
    endTime = System.currentTimeMillis();
  }

  /**
   * Set the seeds for immediate expansion
   * @param seeds
   * @return
   */
  protected EntityList setSeeds(EntityList seeds) {
    if (seeds == null) return null;
    
    // set the 'isSeed' status of all seeds
    for (Entity entity : seeds)
      entity.setSeed(true);
    
    // add seeds to last seeds
    lastSeeds.clear();
    lastSeeds.addAll(seeds);
    
    // add seeds to global seeds
    pastSeeds.addAll(seeds);
    
    return lastSeeds;
  }

  protected void setStartTime() {
    startTime = System.currentTimeMillis();
  }

  protected abstract Element toXMLElement();
  
  public boolean expand(EntityList seeds, DocumentSet documents) {
      throw new UnsupportedOperationException("Not implemented in "+this.getClass().getCanonicalName());
  }
  public DocumentSet getLastDocs() {
      throw new UnsupportedOperationException("Not implemented in "+this.getClass().getCanonicalName());
  }
  public Ranker getRanker() { log.warn(this.getClass().getCanonicalName()+" does not have a ranker."); return null; }
}
 public class WebManager {

  public static Logger log = Logger.getLogger(WebManager.class);
  public static GlobalVar gv = GlobalVar.getGlobalVar();
  
  public static final String URL_VAR = "%URL%";
  public static final String CACHE_HEADER = "<!-- Downloaded from: " + URL_VAR + " -->\n";
  public static final String CACHE_FILE_EXT = ".html";
  public static final int NUM_CACHE_BINS = 1024;
  
  // the unix timestamp when www.google.com was last accessed
  private static long lastHitGoogle = 0;
  // true to enable downloading web documents; false otherwise
    private static boolean isFetchFromWeb = true;
  // true to enable reading from the cache; false otherwise
  private static boolean isReadFromCache = true;
  // true to enable writing to the cache; false otherwise
  private static boolean isWriteToCache = true;
  
  private File cacheDir;
  private int numUrlFromCache = 0;
  private int numUrlFromWeb = 0;
  private int timeOutInMS;
  private int maxDocSizeInKB;
  
  public static boolean isFetchFromWeb() {
    return isFetchFromWeb;
  }
  
  public static boolean isReadFromCache() {
    return isReadFromCache;
  }
  
  public static boolean isWriteToCache() {
    return isWriteToCache;
  }
  
  /**
   * Read cache from the input URL
   * @param url
   * @return cached document
   */
  public static String readFromCache(URL url, File cacheDir) {
    if (url == null || !isReadFromCache())
      return null;
    String document = null;
    File cacheFile = loadCachedFile(url, cacheDir, false);
    if (cacheFile != null && cacheFile.isFile()) {
      document = Helper.readFile(cacheFile);
      // no permission to read the document?
      if (document == null) return null;
      // remove empty cache file
      if (document.length() == 0) {
        cacheFile.delete();
        return null;
      }
      // remove error Yahoo! page
      if (document.contains("service temporarily unavailable [C:28]")) {
        cacheFile.delete();
        return null;
      }
      log.debug("Found Cache: " + cacheFile);
      // get rid of "page source" on the top of every cached document
      document = removeCacheHeader(document);
    }
    return document;
  }
  
  public static void setFetchFromWeb(boolean isFetchFromWeb) {
      WebManager.isFetchFromWeb = isFetchFromWeb;
      log.info("isFetchFromWeb set to " + WebManager.isFetchFromWeb);
  }
  
  public static void setReadFromCache(boolean isReadFromCache) {
    WebManager.isReadFromCache = isReadFromCache;
  }

  public static void setWriteToCache(boolean isWriteToCache) {
    WebManager.isWriteToCache = isWriteToCache;
  }
  
  public static void writeToCache(URL url, String document, File cacheDir) {
    if (document == null || url == null || !isWriteToCache())
      return;
    File cacheFile = loadCachedFile(url, cacheDir, true);
    if (cacheFile == null)
      return;
    long documentSize = Math.round(Helper.getStringSize(document) / 1024.0);
    log.debug("To Cache: " + cacheFile + " (" + documentSize + "KB)");
    // add a "page source" on the top of every cached document
    document = CACHE_HEADER.replace(URL_VAR, url.toString()) + document;
    Helper.writeToFile(cacheFile, document);
  }
  
  /**
   * Finds the corresponding cached file for the input "url".
   * @param url
   * @param makeDir True to create cache dir if it does not exist
   * @return cached file
   */
  private static File loadCachedFile(URL url, File cacheDir, boolean makeDir) {
    if (url == null || cacheDir == null)
      return null;
    int urlHash = Math.abs(url.toString().hashCode());
    String cacheDirName = String.valueOf(urlHash % NUM_CACHE_BINS);
    File newCacheDir = new File(cacheDir, cacheDirName);
    if (makeDir)
      Helper.createDir(newCacheDir);
    String urlFileName = cacheDirName + "." + urlHash + CACHE_FILE_EXT;
    return new File(newCacheDir, urlFileName);
  }
  
  /**
   * Tries to read "urls" from cache. If an URL is not found in cache, it will be inserted into "uncachedURLs". 
   * @param urls List of URLs to retrieve from cache
   * @param uncachedURLs List of URLs not found in cache
   * @return corresponding cached documents of the input "urls"
   */
  private static List<String> readFromCache(List<URL> urls, List<URL> uncachedURLs, File cacheDir) {
    if (urls == null || uncachedURLs == null)
      return null;
    List<String> documents = new ArrayList<String>(urls.size());
    if (urls.size() == 0)
      return documents;
//    log.debug("Reading " + urls.size() + " URLs from cache...");
    for (URL url : urls) {
      String document = readFromCache(url, cacheDir);
      /*final String userDirName0 = "/usr0/", userDirName1 = "/usr1/";
      if (document == null && cacheDir.toString().contains(userDirName0)) {
        File alterFile = new File(cacheDir.toString().replace(userDirName0, userDirName1));
        document = readFromCache(url, alterFile);
      }*/
      documents.add(document);
      if (document == null)
        uncachedURLs.add(url);
    }
    return documents;
  }

    // wwc: made public
  public static String removeCacheHeader(String document) {
    final String prefix = CACHE_HEADER.substring(0, CACHE_HEADER.indexOf(URL_VAR));
    if (document.startsWith(prefix)) {
      int endIndex = document.indexOf("\n");
      if (endIndex != -1)
        return document.substring(endIndex+1);
    }
    return document;
  }

  private static void sleep(List<URL> uncachedURLs) {
    if (!GoogleWebSearcher.containsGoogleURL(uncachedURLs))
      return;
    long elapsedTime;
    while ((elapsedTime = System.currentTimeMillis() - lastHitGoogle) < gv.getGoogleHitGapInMS()) {
      long sleepTime = gv.getGoogleHitGapInMS() - elapsedTime;
      String sleepTimeStr = Helper.formatNumber(sleepTime/1000.0, 2);
      log.info("Just hit Google, sleeping for " + sleepTimeStr + " seconds to prevent being blocked...");
      try { Thread.sleep(sleepTime); }
      catch (InterruptedException e) {}
    }
    lastHitGoogle = System.currentTimeMillis();
  }

  private static void writeToCache(List<URL> urls, List<String> documents, File cacheDir) {
    if (urls == null || documents == null || !isWriteToCache())
      return;
    int size = Math.min(urls.size(), documents.size());
    if (size == 0)
      return;
    log.debug("Writing " + size + " URLs to cache...");
    for (int i = 0; i < size; i++)
      writeToCache(urls.get(i), documents.get(i), cacheDir);
  }

  public WebManager() {
    setCacheDir(gv.getCacheDir());
    setTimeOutInMS(gv.getTimeOutInMS());
    setMaxDocSizeInKB(gv.getMaxDocSizeInKB());
    setFetchFromWeb(gv.getIsFetchFromWeb());
  }

  /**
   * Attempts to retrieve documents from the cache. If not found in cache, 
   * it will download the document from the Internet.
   * @param urls
   * @return retrieved documents
   */
  public List<String> get(List<URL> urls) {
    if (urls == null) return null;
    List<URL> uncachedURLs = new ArrayList<URL>();
    List<String> documents = readFromCache(urls, uncachedURLs, cacheDir);
    numUrlFromCache = urls.size()-uncachedURLs.size();
    numUrlFromWeb = uncachedURLs.size();
    log.info("Fetching " + numUrlFromCache + " webpages from cache and up to " + numUrlFromWeb + " webpages from the Internet");
    
    List<String> uncachedDocs;
    if (!isFetchFromWeb()) {
      log.warn("Not downloading from the Web: Fetching has been disabled!");
      uncachedDocs = Arrays.asList(new String[uncachedURLs.size()]);
    } else {
      log.info("Downloading URLs from Web");
      sleep(uncachedURLs);  // prevent blocking by Google
      uncachedDocs = MultiThreadFetcher.fetch(uncachedURLs, timeOutInMS, maxDocSizeInKB);
    }
    
    // converts search engine's cached pages back to their original format 
    for (int i = 0; i < uncachedDocs.size(); i++) {
      URL url = uncachedURLs.get(i);
      String doc = uncachedDocs.get(i);
      if (GoogleWebSearcher.isBlockedByGoogle(doc, url))
        System.exit(1);
      doc = CacheRecoverer.recover(url, doc);
      uncachedDocs.set(i, doc);
    }

    writeToCache(uncachedURLs, uncachedDocs, cacheDir);
    int j = 0;
    for (int i = 0; i < documents.size(); i++)
      if (documents.get(i) == null)
        documents.set(i, uncachedDocs.get(j++));
    return documents;
  }

  /**
   * Attempts to retrieve a document from the cache. If not found in cache, 
   * it will download the document from the Internet.
   * @param url
   * @return retrieved documents
   */
  public String get(URL url) {
    if (url == null) return null;
    List<URL> urls = new ArrayList<URL>();
    urls.add(url);
    return get(urls).get(0);
  }

  public File getCacheDir() {
    return cacheDir;
  }

  public int getMaxDocSizeInKB() {
    return maxDocSizeInKB;
  }

  public int getNumUrlFromCache() {
    return numUrlFromCache;
  }

  public int getNumUrlFromWeb() {
    return numUrlFromWeb;
  }

  public int getTimeOutInMS() {
    return timeOutInMS;
  }

  public void setCacheDir(File cacheDir) {
    this.cacheDir = cacheDir;
  }

  public void setMaxDocSizeInKB(int maxDocSizeInKB) {
    this.maxDocSizeInKB = maxDocSizeInKB;
  }

  public void setTimeOutInMS(int timeOutInMS) {
    this.timeOutInMS = timeOutInMS;
  }
}
 public static enum Feature { ETF, EDF, EWF, WLW, BSW, PRW, GWW}
 public class GlobalVar {
  
  public static final String PROP_ENV_NAME = "SEAL_PROP";
  public static final String PROP_FILE_PATH = "seal.properties";
  public static final String COMMA_REGEXP = "\\s*,\\s*";
  public static final String CLUEWEB_TMP_DIR="clueweb.tmpdir";
  public static final String CLUEWEB_HEADER_TIMEOUT_MS = "clueweb.headerTimeout";
  public static final String CLUEWEB_TIMEOUT_NUMTRIALS = "clueweb.numtrials";
  public static final String CLUEWEB_TIMEOUT_REPORTING_MS = "clueweb.timeoutReporting";
  public static Logger log = Logger.getLogger(GlobalVar.class);
  
  private static GlobalVar gv = null;
  private static Properties prop = null;
  
  // Basic parameters
  private static String langID;
  private static Feature feature;
  private static boolean hasNoisySeeds;
  private static int useEngine;
  private static String yahooAPIKey;
  private static String yahooBossKey;
  private static long googleHitGapInMS;
  private static File resultDir;
  private static int minSeedsBracketed;
  private static String bingAPIKey;
  private static String googleCustomAPIKey;
  private static  String setExpander;

  // Fetching parameters
  private static int numResults;
  private static int numSubSeeds;
  
  // OfflineSeal and WrapperSavingAsia parameters
    private static boolean isFetchFromWeb; //wwc - keeps WebManager from getting stuff from web
    private static File localDir; //wwc - files that will be searched by the OfflineSearcher
    private static File indexDir; //wwc - index of files in localDir
    private static File localRoot; //wwc - set if files are indexed relative to some root directory
    private static File savedWrapperDir; //wwc - stores wrappers generated by OfflineSeal or WrapperSavingAsia
    private static int wrapperSaving; //wwc - policy on wrapper saving, 2 means save to savedWrapperDir

  // Optimization parameters
  private static int wrapperLevel;
  private static int minContextLength;
  private static int maxDocSizeInKB;
  private static int timeOutInMS;
  private static File cacheDir;
  private static File urlBlackList;
  private static File stopwordsList;
  
  // Iterative expansion parameters
  private static SeedingPolicy policy;
  private static int numExpansions;
  private static int numTrueSeeds;
  private static int numPossibleSeeds;
  
  // Bilingual
  private static String langID2;
  
  // Experiments parameters
  private static List<Feature> expFeatures;
  private static List<String> expDatasets;
  private static File evalDir;
  private static File dataDir;
  private static int numTrials;

  // Question Answering parameters
  private static int topSystem;
  private static boolean useGoogleSets;
  private static double ephyraThreshold;
  private static double sealThreshold;
  private static double interThreshold;
  private static double unionThreshold;
  private static double method1Threshold;
  

  private static boolean explicitRelations;
  private static boolean storeContentWeights;
  
  // ClueWeb parameters
  private static boolean cluewebKeepResponseFile;
  private static boolean cluewebKeepQueryFile;
  private static boolean cluewebMemoryManagement;
  private static boolean multiquery;
  /**
   * Looks for a GlobalVar in the following order:
   * 1) System environment: PROP_ENV_NAME
   * 2) Fixed location: PROP_FILE_PATH
   * @return
   */
  public static GlobalVar getGlobalVar() {
    if (gv != null) return gv;
    gv = new GlobalVar();
    String propFilePath = System.getenv(PROP_ENV_NAME);
    if (propFilePath == null) {
      propFilePath = System.getProperty(PROP_FILE_PATH,PROP_FILE_PATH);
    }
    gv.load(propFilePath);
    return gv;
  }

  public void load(String propFilePath) {
      File propFile = new File(propFilePath);
      log.debug("Loading seal.properties from "+propFilePath);
      prop = Helper.loadPropertiesFile(propFile);
      if (prop == null) {
        log.fatal("Missing \"" + PROP_FILE_PATH + "\" in your classpath!");
        System.exit(1);
      }
      //merge any command-line overrides
      Properties sysprop = System.getProperties();
      prop.putAll(sysprop); // this is messy(noisy) but easy
      
      gv.load(prop);
  }




  
  /**
   * Merges the input properties with the previously loaded properties.
   * Input property names overwrite the loaded property names.
   * @param in the input properties
   */
  public void merge(Properties in) {
    if (prop != null)
      prop.putAll(in);
    else prop = in;
    load(prop);
  }
  
  private static String getProperty(String key, String defaultValue) {
    if (prop == null) {
      log.warn("Properties file not found! Using default: \"" + defaultValue + 
               "\" for the property name: \"" + key + "\"");
      return defaultValue;
    }
    String value = prop.getProperty(key);
    if (value == null || value.trim().length() == 0) {
      log.warn("Missing or invalid property name: \"" + key + "\", using default: \"" + defaultValue + "\"");
      value = defaultValue;
    }
    return value;
  }
  
  private static void setProperties(Properties prop) {
    GlobalVar.prop = prop;
  }
  
  private static List<Feature> toFeatures(String in) {
    if (in == null) return null;
    String[] array = in.split(COMMA_REGEXP);
    List<Feature> list = new ArrayList<Feature>();
    for (String s : array) {
      Feature feature = Feature.valueOf(s.trim());
      if (feature != null)
        list.add(feature);
    }
    return list;
  }
  
  private static List<String> toStrings(String in) {
    if (in == null) return null;
    String[] array = in.split(COMMA_REGEXP);
    List<String> list = new ArrayList<String>();
    for (String s : array) {
      s = s.toLowerCase().trim();
      if (s.length() > 0)
        list.add(s);
    }
    return list;
  }
  
  private static File toFile(String in) {
    return in == null ? null : new File(in);
  }
  
  public void load(Properties prop) {
    setProperties(prop);
    
    // expansion parameters
    wrapperLevel = Integer.parseInt(getProperty("wrapperLevel", "0"));
    minSeedsBracketed = Integer.parseInt(getProperty("minSeedsBracketed", "0"));
    minContextLength = Integer.parseInt(getProperty("minContextLength", "1"));
    maxDocSizeInKB = Integer.parseInt(getProperty("maxDocSizeInKB", "512"));
    
    langID = getProperty("langID", "un");
    langID2 = getProperty("langID2", "un");
    yahooAPIKey = getProperty("yahooAPIKey", "");
    yahooBossKey = getProperty("yahooBossKey", "");
    bingAPIKey = getProperty("bingAPIKey","");
    googleCustomAPIKey = getProperty("googleCustomAPIKey","");
    numResults = Integer.parseInt(getProperty("numResults", "100"));
    numSubSeeds = Integer.parseInt(getProperty("numSubSeeds", "0"));
    timeOutInMS = Integer.parseInt(getProperty("timeOutInMS", "10000")); // 10 sec.
    isFetchFromWeb = Boolean.parseBoolean(getProperty("isFetchFromWeb", "true")); // wwc
    hasNoisySeeds = Boolean.parseBoolean(getProperty("hasNoisySeeds", "false"));
    useGoogleSets = Boolean.parseBoolean(getProperty("useGoogleSets", "false"));
    setExpander = getProperty("setExpander",
            useGoogleSets ?
            "com.rcwang.seal.expand.GoogleSets" : 
            "com.rcwang.seal.expand.Seal");
    useEngine = Integer.parseInt(getProperty("useEngine", "6"));
    cacheDir = toFile(getProperty("cacheDir", "cache"));
    localDir = toFile(getProperty("localDir", "local"));
    indexDir = toFile(getProperty("indexDir", "index")); // wwc
    localRoot = toFile(getProperty("localRoot", null)); // wwc
    savedWrapperDir = toFile(getProperty("savedWrapperDir", "wrapper")); // wwc
    wrapperSaving = Integer.parseInt(getProperty("wrapperSaving", "0")); // wwc
    resultDir = toFile(getProperty("resultDir", null));
    feature = Feature.valueOf(getProperty("feature", "WLW"));
    policy = SeedingPolicy.valueOf(getProperty("policy", "ISS_UNSUPERVISED"));
    numTrueSeeds = Integer.parseInt(getProperty("numTrueSeeds", "2"));
    numPossibleSeeds = Integer.parseInt(getProperty("numPossibleSeeds", "0"));
    // every hit to Google must be at least x milliseconds in between
    googleHitGapInMS = Long.parseLong(getProperty("googleHitGapInMS", "5000"));
    expFeatures = toFeatures(getProperty("expFeatures", null));
    expDatasets = toStrings(getProperty("expDatasets", null));
    urlBlackList = toFile(getProperty("urlBlackList", null));
    stopwordsList = toFile(getProperty("stopwordsList", null));
    
    // evaluation parameters
    evalDir = new File(getProperty("evalDir", "eval"));
    dataDir = new File(getProperty("dataDir", "data"));
    numTrials = Integer.parseInt(getProperty("numTrials", "0"));
    numExpansions = Integer.parseInt(getProperty("numExpansions", "0"));
    
    // qa
    topSystem = Integer.parseInt(getProperty("topSystem", "0"));
    ephyraThreshold = Double.parseDouble(getProperty("ephyraThreshold", "0"));
    sealThreshold = Double.parseDouble(getProperty("sealThreshold", "0"));
    interThreshold = Double.parseDouble(getProperty("interThreshold", "0"));
    unionThreshold = Double.parseDouble(getProperty("unionThreshold", "0"));
    method1Threshold = Double.parseDouble(getProperty("method1Threshold", "0"));
    
    // are all relations created using Entity(String,String) constructor?
    explicitRelations = Boolean.parseBoolean(getProperty("explicitRelations","false"));
    
    // should individual content weights be stored in addition to aggregated weights?
    // (for NELL scoring)
    storeContentWeights = Boolean.parseBoolean(getProperty("storeContentWeights","false"));
    
    // clueweb
    cluewebKeepQueryFile    = Boolean.parseBoolean(getProperty("cluewebKeepQueryFile","false"));
    cluewebKeepResponseFile = Boolean.parseBoolean(getProperty("cluewebKeepResponseFile","false"));
    cluewebMemoryManagement = Boolean.parseBoolean(getProperty("cluewebMemoryManagement","true"));
    multiquery = Boolean.parseBoolean(getProperty("multiquery","false"));
  }
  
  public Properties getProperties() { return prop; }
  
  public File getCacheDir() { return cacheDir; }
  public void setCacheDir(File cacheDir) { GlobalVar.cacheDir = cacheDir; }
  
  public File getIndexDir() { return indexDir; } //wwc
  public void setIndexDir(File indexDir) { GlobalVar.indexDir = indexDir; } //wwc

  public File getLocalDir() { return localDir; } //wwc
  public void setLocalDir(File localDir) { GlobalVar.localDir = localDir; } //wwc

  public File getLocalRoot() { return localRoot; } //wwc
  public void setRootOfIndexedFiles(File localRoot) { GlobalVar.localRoot = localRoot; } //wwc

  public File getSavedWrapperDir() { return savedWrapperDir; } //wwc
  public void setSavedWrapperDir(File savedWrapperDir) { GlobalVar.savedWrapperDir = savedWrapperDir; } //wwc

  public int getWrapperSaving() { return wrapperSaving; } //wwc
  public void setWrapperSaving(int wrapperSaving) { GlobalVar.wrapperSaving = wrapperSaving; } //wwc

  public File getDataDir() { return dataDir; }
  public void setDataDir(File dataDir) { GlobalVar.dataDir = dataDir; }
  
  public File getEvalDir() { return evalDir; }
  public void setEvalDir(File evalDir) { GlobalVar.evalDir = evalDir; }
  
  public String getLangID() { return langID; }
  public void setLangID(String langID) { GlobalVar.langID = langID; }
  
  public int getMaxDocSizeInKB() { return maxDocSizeInKB; }
  public void setMaxDocSizeInKB(int maxDocSizeInKB) { GlobalVar.maxDocSizeInKB = maxDocSizeInKB; }
  
  public int getMinContextLength() { return minContextLength; }
  public void setMinContextLength(int minContextLength) { GlobalVar.minContextLength = minContextLength; }
  
  public int getMinSeedsBracketed() { return minSeedsBracketed; }
  public void setMinSeedsBracketed(int minSeedsBracketed) { GlobalVar.minSeedsBracketed = minSeedsBracketed; }
  
  public int getNumExpansions() { return numExpansions; }
  public void setNumExpansions(int numExpansions) { GlobalVar.numExpansions = numExpansions; }
  
  public int getNumResults() { return numResults; }
  public void setNumResults(int numResults) { GlobalVar.numResults = numResults; }
  
  public int getNumSubSeeds() { return numSubSeeds; }
  public void setNumSubSeeds(int numSubSeeds) { GlobalVar.numSubSeeds = numSubSeeds; }
  
  public int getNumTrials() { return numTrials; }
  public void setNumTrials(int numTrials) { GlobalVar.numTrials = numTrials; }

  public File getResultDir() { return resultDir; }
  public void setResultDir(File resultDir) { GlobalVar.resultDir = resultDir; }
  
  public File getStopwordsList() { return stopwordsList; }
  public void setStopwordsList(File stopwordsList) { GlobalVar.stopwordsList = stopwordsList; }
  
  public int getTimeOutInMS() { return timeOutInMS; }
  public void setTimeOutInMS(int timeOutInMS) { GlobalVar.timeOutInMS = timeOutInMS; }
  
  public File getUrlBlackList() { return urlBlackList; }
  public void setUrlBlackList(File urlBlackList) { GlobalVar.urlBlackList = urlBlackList; }
  
  public String getYahooAPIKey() { return yahooAPIKey; }
  public void setYahooAPIKey(String yahooAPIKey) { GlobalVar.yahooAPIKey = yahooAPIKey; }
  
  public boolean getIsFetchFromWeb() { return isFetchFromWeb; } //wwc
  public void setIsFetchFromWeb(boolean isFetchFromWeb) { GlobalVar.isFetchFromWeb = isFetchFromWeb; } //wwc

  public boolean hasNoisySeeds() { return hasNoisySeeds; }
  public void setHasNoisySeeds(boolean hasNoisySeeds) { GlobalVar.hasNoisySeeds = hasNoisySeeds; }

  public Feature getFeature() { return feature; }
  public void setFeature(Feature feature) { GlobalVar.feature = feature; }
  
  public SeedingPolicy getPolicy() { return policy; }
  public void setPolicy(SeedingPolicy policy) { GlobalVar.policy = policy; }

  public int getNumPossibleSeeds() { return numPossibleSeeds; }
  public void setNumPossibleSeeds(int numPossibleSeeds) { GlobalVar.numPossibleSeeds = numPossibleSeeds; }

  public int getNumTrueSeeds() { return numTrueSeeds; }
  public void setNumTrueSeeds(int numTrueSeeds) { GlobalVar.numTrueSeeds = numTrueSeeds; }

  public List<Feature> getExpFeatures() { return expFeatures; }
  public void setExpFeatures(List<Feature> expFeatures) { GlobalVar.expFeatures = expFeatures; }

  public List<String> getExpDatasets() { return expDatasets; }
  public void setExpDatasets(List<String> expDatasets) { GlobalVar.expDatasets = expDatasets; }

  public long getGoogleHitGapInMS() { return googleHitGapInMS; }
  public void setGoogleHitGapInMS(long googleHitGap) { GlobalVar.googleHitGapInMS = googleHitGap; }

  public int getTopSystem() { return topSystem; }
  public void setTopSystem(int topSystem) { GlobalVar.topSystem = topSystem; }

  public double getEphyraThreshold() { return ephyraThreshold; }
  public void setEphyraThreshold(double ephyraThreshold) { GlobalVar.ephyraThreshold = ephyraThreshold; }

  public double getSealThreshold() { return sealThreshold; }
  public void setSealThreshold(double sealThreshold) { GlobalVar.sealThreshold = sealThreshold; }

  public double getInterThreshold() { return interThreshold; }
  public void setInterThreshold(double interThreshold) { GlobalVar.interThreshold = interThreshold; }

  public double getUnionThreshold() { return unionThreshold; }
  public void setUnionThreshold(double unionThreshold) { GlobalVar.unionThreshold = unionThreshold; }

  public double getMethod1Threshold() { return method1Threshold; }
  public void setMethod1Threshold(double method1Threshold) { GlobalVar.method1Threshold = method1Threshold; }

  public boolean isUseGoogleSets() { return useGoogleSets; }
  public void setUseGoogleSets(boolean useGoogleSets) {GlobalVar.useGoogleSets = useGoogleSets; }

  public String getLangID2() { return langID2; }
  public void setLangID2(String langID2) { GlobalVar.langID2 = langID2; }

  public int getUseEngine() { return useEngine; }
  public void setUseEngine(int useEngine) { GlobalVar.useEngine = useEngine; }

  public int getWrapperLevel() { return wrapperLevel; }
  public void setWrapperLevel(int wrapperLevel) { GlobalVar.wrapperLevel = wrapperLevel; }

  public String getYahooBossKey() { return yahooBossKey; }
  public void setYahooBossKey(String yahooBossKey) { GlobalVar.yahooBossKey = yahooBossKey; }

  public boolean getExplicitRelations() { return explicitRelations; }
  public boolean isStoreContentWeights() { return storeContentWeights; }

  public String getBingAPIKey() { return bingAPIKey; }
  public void setBingAPIKey(String k) { GlobalVar.bingAPIKey = k; }

  public String getGoogleCustomAPIKey() { return googleCustomAPIKey; }
  public void setGoogleCustomAPIKey(String k) { GlobalVar.googleCustomAPIKey = k; }
  
  public boolean getClueWebMemoryManagement() { return cluewebMemoryManagement; }
  public void setClueWebMemoryManagement(boolean b) { cluewebMemoryManagement = b; }
  
  public boolean getClueWebKeepResponseFile() { return cluewebKeepResponseFile; }
  public void setClueWebKeepResponseFile(boolean b) { cluewebKeepResponseFile = b; }
  
  public boolean getClueWebKeepQueryFile() { return cluewebKeepQueryFile; }
  public void setClueWebKeepQueryFile(boolean b) { cluewebKeepQueryFile = b; }
  
  public boolean isMultiquery() { return multiquery; }
  public void setMultiquery(boolean b) { multiquery = b; }




  public String getSetExpander() { return setExpander; }




 }
 public class Helper {
  
  public static Logger log = Logger.getLogger(Helper.class);
  
  public static final String UNICODE = "UTF-8";
  public static final String COMMON_ENCODING = "ISO-8859-1";
  public static final String DATE_FORMAT = "yyyy-MM-dd";  // must match below
  public static final String DATE_PATTERN = "\\d+{4}-\\d+{2}-\\d+{2}";  // must match above
  public static final String TIME_FORMAT = "h:mm:ss aa";
  public static final String DATE_TIME_FORMAT = DATE_FORMAT + " " + TIME_FORMAT;
  public static final NumberFormat NUM_FORMAT = NumberFormat.getInstance();
  
  public static String repeat(char c, int n) {
    StringBuffer buf = new StringBuffer();
    for (; n > 0; n--)
      buf.append(c);
    return buf.toString();
  }
  
  public static String center(String s, char filler, int width) {
    if (s.length() >= width) return s;
    int numFillers = (width - s.length()) / 2;
    return repeat(filler, numFillers) + s + repeat(filler, numFillers);
  }
  
  public static String addQuote(String s) {
    s = s.trim();
    if (!s.startsWith("\""))
      s = "\"" + s;
    if (!s.endsWith("\""))
      s += "\"";
    return s;
  }
  
  public static double getPDF(double x, double avg, double std) {
    double diff = x - avg;
    double exp = Math.exp(-0.5 * Math.pow(diff / std, 2));
    return exp / (std * Math.sqrt(2 * Math.PI));
  }
  
  public static String addQuote(String[] ss) {
    StringBuffer buf = new StringBuffer();
    for (String s : ss)
      buf.append(buf.length() > 0 ? " " : "").append(addQuote(s));
    return buf.toString();
  }
  
  public static File createDir(File dir) {
    if (dir != null && !dir.isDirectory()) {
      log.info("Creating directory: " + dir.getAbsolutePath());
      if (!dir.mkdirs())
          log.error("Could not create requested directories for "+dir.getAbsolutePath());
    }
    return dir;
  }
  
  public static File createTempFile (String content) {
    File temp = null;
    try {
      temp = File.createTempFile("tmp", null);
    } catch (IOException ioe) {
      log.error("Error creating temp file: " + ioe);
      return null;
    }
    temp.deleteOnExit();
    writeToFile(temp, content, "UTF-8", false);
    return temp;
  }
  
  public static String decodeURLString(String s) {
    if (s == null) return null;
    try {
      return URLDecoder.decode(s, UNICODE);
    } catch (UnsupportedEncodingException e) {
      log.error(e.toString());
      return null;
    }
  }
  
  public static void die(String s) {
    System.err.println("[FATAL] " + s);
    System.exit(1);
  }
  
  public static boolean empty(EntityList entityList) {
    return entityList == null || entityList.isEmpty();
  }
  
  public static boolean empty(String s) {
    return s == null || s.trim().length() == 0;
  }
  
  // encode the query and formulate the query URL
  public static String encodeURLString(String s) {
    if (s == null) return null;
    try {
      return URLEncoder.encode(s, UNICODE);
    } catch (UnsupportedEncodingException e) {
      log.error(e.toString());
      return null;
    }
  }
  
  /**
   * Returns the String bounded by "left" and "after" in String s
   * @param s
   * @param left
   * @param right
   * @return the bounded String
   */
  public static String extract(String s, String left, String right) {
    int leftOffset, rightOffset;
    if (left == null) {
      leftOffset = 0;
      left = "";
    } else {
      leftOffset = s.indexOf(left);
      if (leftOffset == -1)
        return null;
    }
    if (right == null) {
      rightOffset = s.length();
    } else {
      rightOffset = s.indexOf(right, leftOffset + left.length());
      if (rightOffset == -1)
        return null;
    }
    return s.substring(leftOffset + left.length(), rightOffset);
  }

  public static String formatNumber(double number, int decimal) {
    NUM_FORMAT.setMaximumFractionDigits(decimal);
    NUM_FORMAT.setMinimumFractionDigits(decimal);
    return NUM_FORMAT.format(number).replace(",", "");
  }
  
  public static int getStringSize(String s) {
    int docSize = -1;
    try {
      docSize = s.getBytes("US-ASCII").length;
    } catch (UnsupportedEncodingException e) {
      e.printStackTrace();
    }
    return docSize;
  }
  
  /***
   * Creates a unique ID based on the current date and time
   * @return a unique ID
   */
  public static String getUniqueID () {
    Calendar cal = Calendar.getInstance(TimeZone.getDefault());
    SimpleDateFormat sdf = new SimpleDateFormat("MMdd-HHmmss");
    sdf.setTimeZone(TimeZone.getDefault());
    return sdf.format(cal.getTime());
  }
  
  public static Properties loadPropertiesFile(File propFile) {
    if (propFile == null)
      return null;
    Properties props = new Properties();
    InputStream in;
    try {
      in = readFileToStream(propFile);
      if (in != null) {
        props.load(in);
        in.close();
      }
    } catch (FileNotFoundException e) {
      log.error("Properties file not found: " + e);
      return null;
    } catch (IOException e) {
      log.error("Read properties file error: " + e);
      return null;
    }
    return props;
  }
  
  public static <T> T loadSerialized(File file, Class<? extends T> c) {
    log.info("Loading serialized object from: " + file);
    FileInputStream fis = null;
    ObjectInputStream in = null;
    T object = null;
    try {
      fis = new FileInputStream(file);
      in = new ObjectInputStream(fis);
      object = c.cast(in.readObject());
      in.close();
    } catch(IOException ex) {
      ex.printStackTrace();
    } catch(ClassNotFoundException ex) {
      ex.printStackTrace();
    }
    return object;
  }

  public static double log2(double d) {
    return Math.log(d) / Math.log(2);
  }
  
  public static String merge(String[] strList, String delimiter) {
    StringBuffer buf = new StringBuffer();
    for (String s : strList) {
      if (buf.length() > 0)
        buf.append(delimiter);
      buf.append(s);
    }
    return buf.toString();
  }
  
  public static void printElapsedTime(long startTime) {
    log.info("Elapsed time: " + (System.currentTimeMillis() - startTime) / 1000.0 + " seconds");
  }
  
  public static void printDebugInfo() {
    log.info("Originator Size: " + Originator.size() + " (" + Originator.getNumStrings() + ")");
    log.info("String     Size: " + StringFactory.getStrSize());
    log.info("String ID  Size: " + StringFactory.getIDSize());
    Helper.printMemoryUsed();
  }
  
  public static void printMemoryUsed() {
    for (int i = 0; i < 3; i++) System.gc();
    long memSize = Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory();
    String memSizeStr = Helper.formatNumber((double) memSize / 1024 / 1024, 2);
    log.info(" Memory used: " + memSizeStr + "MB");
  }
  
  public static String readFile(File f) {
    return readFile(f, "UTF-8", false);
  }

  /**
   * Reads in a file, if not found, search on the class path
   * @param file the input file
   * @param charset the character set
   * @param binary is the file binary or text (non-binary)?
   * @return the content of the file
   */
  public static String readFile(File file, String charset, boolean binary) {
    if (file == null || charset == null)
      return null;
    InputStream in = readFileToStream(file);
    if (in == null)
      return null;
    StringBuffer buf = new StringBuffer();
    try {
      BufferedReader bReader = new BufferedReader(new InputStreamReader(in, charset));
      if (!binary) {
        String line;
        while ((line = bReader.readLine()) != null)
          buf.append(line).append("\n");
      } else {
        char[] c = new char[(int) file.length()];
        bReader.read(c);
        buf.append(c);
      }
      bReader.close();
    } catch (Exception e) {
      log.error("Could not read \"" + file + "\": " + e);
      return null;
    }
    String result = buf.toString();
    // get rid of BOM (byte order marker) from UTF-8 file
    if (result.length() > 0 && result.charAt(0) == 65279)
      result = result.substring(1);
    return result;
  }
  
  public static InputStream readFileToStream(File in) {
    if (in == null) return null;
    InputStream s = null;
    try {
      if (in.exists()) // if file exist locally
        s = new FileInputStream(in);
      if (s == null) // if file exist somewhere on the class path
        s = ClassLoader.getSystemResourceAsStream(in.getPath());
      if (s == null) { // if file still could not be found
        log.error("Could not find \"" + in + "\" locally ("+in.getAbsolutePath()+") or on classpath");
        return null;
      }
    } catch (Exception e) {
      log.error("Could not read \"" + in + "\": " + e);
      return null;
    }
    return s;
  }
  
  public static void recursivelyRemove(File f) {
    if (f == null || !f.exists()) return;
    if (f.isDirectory()) {
      File[] files = f.listFiles();
      for (File file : files)
        recursivelyRemove(file);
    }
    String type = f.isDirectory() ? "directory" : "file";
    boolean deleted = f.delete();
    if (!deleted)
      log.error("Cannot delete the " + type + ": " + f);
    else log.debug("Successfully deleted the " + type + ": " + f);
  }
  
  public static String removeQuote(String s) {
    if (s == null) return null;
    s = s.trim();
    if (s.startsWith("\"") && s.endsWith("\""))
      s = s.substring(1, s.length()-1);
    return s;
  }
  
  public static void saveSerialized(Object object, File file, boolean overwrite) {
    if (!overwrite && file.exists()) {
      log.info("Serialized file " + file + " already exists! Skip saving...");
      return;
    }
    log.info("Saving serialized object to: " + file);
    if (file.getParentFile() != null)
      Helper.createDir(file.getParentFile());
    FileOutputStream fos = null;
    ObjectOutputStream out = null;
    try {
      fos = new FileOutputStream(file);
      out = new ObjectOutputStream(fos);
      out.writeObject(object);
      out.close();
    } catch(IOException ex) {
      ex.printStackTrace();
    }
  }

  public static void sortByLength(List<String> list, final boolean ascending) {
    Comparator<String> c = new Comparator<String>() {
      public int compare(String e1, String e2) {
        int length1 = e1.length();
        int length2 = e2.length();
        if (ascending)
          return Double.compare(length1, length2);
        else return Double.compare(length2, length1);
      }
    };
    Collections.sort(list, c);
  }
  
  /**
   * Converts an integer to a binary array with a specified max size
   * input: 11, output: [1011]
   * @param integer
   * @param size
   * @return
   */
  public static boolean[] toBinaryArray(int integer, int size) {
    boolean[] b = new boolean[size];
    String s = Integer.toBinaryString(integer);
    if (s.length() > b.length)
      s = s.substring(s.length()-b.length);
    // algorithm bug fixed kmr jan 2012
    // the 1s place is at the end of the string, so start there
    for (int i = s.length()-1; i >=0; i--)
      // the 1s element is at b[0] so start there
      b[s.length()-1-i] = (s.charAt(i) == '1');
    return b;
  }

  public static String toFileName(String s) {
    return s.replaceAll("[\\/:\\*?\"<>|\\s]+", "_");
  }

  public static File toFileOrDie(String filename) {
    if (filename == null)
      die("Could not find the file: " + filename);
    File file = new File(filename);
    if (!file.exists())
      die("Could not find the file: " + filename);
    return file;
  }

  public static String toReadableString(Collection<String> list) {
    Set<String> seeds = new TreeSet<String>();
    if (list != null)
      seeds.addAll(list);
    StringBuffer buf = new StringBuffer();
    buf.append("{");
    for (String seed : seeds) {
      if (buf.length() > 1)
        buf.append(", ");
      buf.append(seed);
    }
    buf.append("}");
    return buf.toString();
  }

  public static String toReadableDouble(Collection<Double> doubles) {
    StringBuffer buf = new StringBuffer();
    buf.append("{");
    for (Double d : doubles) {
      if (buf.length() > 1)
        buf.append(", ");
      buf.append(Helper.formatNumber(d, 5));
    }
    buf.append("}");
    return buf.toString();
  }
  
  public static String toReadableTime(Long timestamp, String format) {
    SimpleDateFormat sdf = new SimpleDateFormat(format);
    sdf.setTimeZone(TimeZone.getDefault());
    if (timestamp == null)
      timestamp = System.currentTimeMillis();
    return sdf.format(new Date(timestamp));
  }

  public static String toSeedsFileName(Collection<String> seedList) {
    Set<String> seeds = new TreeSet<String>();
    if (seedList != null)
      seeds.addAll(seedList);
    StringBuffer buf = new StringBuffer();
    for (String seed : seeds) {
      if (buf.length() > 0)
        buf.append("+");
      buf.append(seed);
    }
    return toFileName(buf.toString());
  }
  
  /**
   * Converts a String array to a Collection of Unicode
   * @param strs
   * @return
   */
  public static Set<String> toUnicode(Collection<String> strs) {
    Set<String> set = new HashSet<String>();
    if (strs == null) return set;
    for (String s : strs) {
      s = toUnicode(s);
      if (!empty(s))
        set.add(s.toLowerCase());  // added 04/21/2008
    }
    return set;
  }

  /**
   * Converts a string to unicode
   * @param s
   * @return
   */
  public static String toUnicode(String s) {
    if (s == null) return null;
    try {
      s = new String(s.getBytes(COMMON_ENCODING), UNICODE);
    } catch (UnsupportedEncodingException e) {
      log.error(e);
    }
    return s.trim();
  }

  public static URL toURL(String s) {
    try {
      return new URL(s);
    } catch (MalformedURLException e) {
      return null;
    }
  }

  public static void writeToFile(File out, String content) {
    writeToFile(out, content, UNICODE, false);
  }

  public static void writeToFile(File out, String content, boolean append) {
    writeToFile(out, content, UNICODE, append);
  }
  
  public static void writeToFile(File out, String content, String charset, boolean append) {
    if (out == null || content == null) return;
    try {
      BufferedWriter bWriter = new BufferedWriter(new OutputStreamWriter(new FileOutputStream(out, append), charset));
      bWriter.write(content);
      bWriter.close();
    } catch (IOException e) {
      log.error("Writing to " + out + ": " + e);
    }
  }

public static Object toReadableString(Set<EntityLiteral> contents) {
        Set<EntityLiteral> seeds = new TreeSet<EntityLiteral>();
        if (contents != null)
          seeds.addAll(contents);
        StringBuffer buf = new StringBuffer();
        buf.append("{");
        for (EntityLiteral seed : seeds) {
          if (buf.length() > 1)
            buf.append(", ");
          buf.append(seed.toString());
        }
        buf.append("}");
        return buf.toString();
      }
}
 public class StringFactory {

  public static class SID implements Iterable<String> {
    
    String[] array;
    
    public SID(List<String> strs) {
      array = strs.toArray(new String[strs.size()]);
    }

    public SID(SID id) {
      this(id.array);
    }

    public SID(String[] array) {
      this.array = array.clone();
    }
    
    public void append(SID sid) {
      append(sid.array);
    }
    
    public void append(String s) {
      append(StringFactory.toID(s));
    }
    
    public void append(String[] array) {
      String[] array2 = new String[this.array.length+array.length];
      System.arraycopy(this.array, 0, array2, 0, this.array.length);
      System.arraycopy(array, 0, array2, this.array.length, array.length);
      this.array = array2;
    }
    
    @Override
    public boolean equals(Object obj) {
      if (this == obj) return true;
      if (obj == null) return false;
      if (getClass() != obj.getClass()) return false;
      final SID other = (SID) obj;
      if (!Arrays.equals(array, other.array))
        return false;
      return true;
    }
    
    @Override
    public int hashCode() {
      return 31 + Arrays.hashCode(array);
    }
    
    public Iterator<String> iterator() {
      return Arrays.asList(array).iterator();
    }
    
    public int length() {
      int length = 0;
      for (String s : this)
        length += s.length();
      return length;
    }

    @Override
    public String toString() {
      return StringFactory.toName(this);
    }
    
    public EntityLiteral toLiteral() { return new EntityLiteral(StringFactory.toName(this)); }
    
    public SID toLower() {
    	return StringFactory.toID(new EntityLiteral(StringFactory.toName(this).toLowerCase()));
    }
  }
  public static class RSID extends SID {
      int boundary;

      public RSID(List<String> strs) { super(strs); }
      public RSID(SID id) { super(id); }
      public RSID(String[] array) { super(array); }
      
      public RSID(SID a1, SID a2) {
          super(a1); 
          boundary = a1.array.length;
          super.append(a2);
      }
      
      public EntityLiteral toLiteral() {
          return new EntityLiteral(
                  StringFactory.toName(Arrays.copyOfRange(this.array, 0, boundary)),
                  StringFactory.toName(Arrays.copyOfRange(this.array, boundary, this.array.length))
          );
      }
  }
  
  /*public static class SID extends ArrayList<String> {
    private static final long serialVersionUID = -746676179936368932L;
    
    public SID() {
      super();
    }
    
    public SID(SID id) {
      this();
      this.addAll(id);
    }
    
    public void append(SID id) {
      this.addAll(id);
    }
    
    public int length() {
      int length = 0;
      for (String s : this)
        length += s.length();
      return length;
    }
    
    @Override
    public String toString() {
      return StringFactory.toName(this);
    }
  }*/
  
  public static final boolean DISABLE_CACHE = false; // reduces memory for small runs
  private static Map<String, String> strMap = new Cache<String, String>();
  private static Map<SID, SID> sidMap = new Cache<SID, SID>();
  private static StringBuffer buf = new StringBuffer();
  private static String delimiter = " ";  // space
  
  public static void clear() {
    strMap.clear();
    sidMap.clear();
  }
  
  public static SID get(SID sid) {
    if (DISABLE_CACHE) return sid;
    SID sid2 = sidMap.get(sid);
    if (sid2 == null) {
      sidMap.put(sid, sid);
      return sid;
    } else return sid2;
  }
  
  public static String get(String s) {
    if (DISABLE_CACHE) return s;
    String s2 = strMap.get(s);
    if (s2 == null) {
      strMap.put(s, s);
      return s;
    } else return s2;
  }
  
  public static String getDelimiter() {
    return delimiter;
  }
  
  public static int getIDSize() {
    return sidMap.size();
  }
  
  public static int getStrSize() {
    return strMap.size();
  }
  
  public static void main(String args[]) {
    String[] tests = new String[] {
        "",
        " ",
        "  ",
        ".",
        ". ",
        " .",
        "..",
    };
    
    boolean failed = false;
    for (String test : tests) {
      SID id = StringFactory.toID(test);
      String s = StringFactory.toName(id);
      if (!test.equals(s)) {
        failed = true;
        break;
      }
    }
    
    if (failed)
      System.out.println("FAILURE!!!");
    else System.out.println("SUCCESS!!!");
  }
  
  public static void setDelimiter(String delimiter) {
    StringFactory.delimiter = delimiter;
  }
  
  /**
   * Sort by alphabetical order
   * @param idSet
   * @return
   */
  public static List<SID> sortIDs(Set<SID> idSet) {
    Map<String, SID> strIDMap = new HashMap<String, SID>();
    for (SID id : idSet)
      strIDMap.put(toName(id), id);
    List<String> strList = new ArrayList<String>(strIDMap.keySet());
    Collections.sort(strList);
    List<SID> resultList = new ArrayList<SID>();
    for (String str : strList)
      resultList.add(get(strIDMap.get(str)));
    return resultList;
  }
  
  /**
   * Splits a String
   * @param name
   * @return a new List
   */
  public static SID toID(String name) {
    if (name == null) return null;
    List<String> ids = new ArrayList<String>();
    int index = 0, prevIndex = 0;
    if (name.length() > 0) {
      while ((index = name.indexOf(delimiter, prevIndex)) != -1) {
        ids.add(get(name.substring(prevIndex, index)));
        prevIndex = index + delimiter.length();
        if (prevIndex == name.length())
          break;
      }
    }
    if (prevIndex > name.length())
      System.err.println("Something is wrong!!!");
    else if (prevIndex == name.length())
      ids.add(get(""));
    else if (index == -1)
      ids.add(get(name.substring(prevIndex)));
    return get(new SID(ids));
  }
  
  public static SID toID(EntityLiteral name) {
      if (name == null) return null;
      if (name.arg2 == null) return toID(name.arg1);
      SID id1 = toID(name.arg1);
      SID id2 = toID(name.arg2);
      return new RSID(id1,id2);
  }
  
  
  public static String toName(SID id) {
      if (id == null) return null;
      return toName(id.array);
  }
  /**
   * Combines a list of Strings
   * @param id
   * @return a new String
   */
  public static String toName(String ... id) {
    if (id == null) return null;
    buf.setLength(0);
    for (Object o : id) {
      if (buf.length() > 0)
        buf.append(delimiter);
      buf.append(o);
    }
    return buf.toString();
  }

  public static Set<String> toNames(Set<SID> idSet) {
    Set<String> names = new HashSet<String>();
    for (SID id : idSet)
      names.add(toName(id));
    return names;
  }
}

import java.io.File;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.Set;
import java.util.regex.Pattern;
import org.apache.log4j.Logger;
import com.rcwang.seal.expand.Entity;
import com.rcwang.seal.expand.EntityList;
import com.rcwang.seal.expand.GoogleSets;
import com.rcwang.seal.expand.Seal;
import com.rcwang.seal.expand.SetExpander;
import com.rcwang.seal.fetch.WebManager;
import com.rcwang.seal.rank.Ranker.Feature;
import com.rcwang.seal.util.GlobalVar;
import com.rcwang.seal.util.Helper;
import com.rcwang.seal.util.StringFactory;

        case SEAL: resultsList = sealResults; break;
        case INTERSECT: resultsList = ItemWeight.intersect(ephyraXML.getAnswers(), sealResults); break;
        case UNION: resultsList = ItemWeight.union(ephyraXML.getAnswers(), sealResults, DEFAULT_WEIGHT); break;
        case METHOD1: resultsList = ItemWeight.union(ephyraXML.getAnswers(), sealResults, 1.0);
        default: log.error("Unknown hybrid method: " + method);
      }
      checkAnswer(resultsList, stat);
    }
    return stats;
  }
  
  public int getNumTrueAnswers(String trecID) {
    List<Pattern> patternList = qidPatternMap.get(trecID);
    return (patternList == null) ? 0 : patternList.size();
  }
  
  public Set<String> getQIDs() {
    return qidPatternMap.keySet();
  }
  
  public List<Pattern> getTrueAnswerPatterns(String trecID) {
    return qidPatternMap.get(trecID);
  }
  
  public List<String> getTrueAnswers(String trecID) {
    return qidAnswerMap.get(trecID);
  }
  
  public Set<String> loadAnswerPatterns(File file) {
    String content = Helper.readFile(file);
    String[] lines = content.split("\n");
    Set<String> qids = new LinkedHashSet<String>();
    for (String line : lines) {
      String[] pairs = line.split("\\s+", 2);
      if (pairs.length != 2)
        continue;
      String qid = pairs[0];
      // fix the dot problem in the trec pattern list
//      pairs[1] = pairs[1].replaceAll("\\.", "\\.");
      Pattern p = Pattern.compile("(?i)" + pairs[1]);
      List<Pattern> patternList = qidPatternMap.get(qid);
      if (patternList == null) {
        patternList = new ArrayList<Pattern>();
        qidPatternMap.put(qid, patternList);
      }
      patternList.add(p);
      qids.add(qid);
    }
    return qids;
  }
  
  public Set<String> loadAnswers(int trecID) {
    inputLoader.load(getInputFile(trecID));
    loadAnswerStrings(getAnsFile(trecID));
    return loadAnswerPatterns(getAnsPatternFile(trecID));
  }
  
  public Set<String> loadAnswerStrings(File file) {
    String content = Helper.readFile(file);
    String[] lines = content.split("\n");
    String qid = null;
    String s = "# ", q = "Q:";
    Set<String> qids = new LinkedHashSet<String>();
    for (String line : lines) {
      line = line.trim();
      if (line.startsWith(s)) {
        qid = line.substring(s.length()).trim();
        continue;
      } else if (line.startsWith(q) || line.length() == 0) {
        continue;
      }
      List<String> answerList = qidAnswerMap.get(qid);
      if (answerList == null) {
        answerList = new ArrayList<String>();
        qidAnswerMap.put(qid, answerList);
      }
      String[] e = line.split(","); // added 02/19/2008
      answerList.add(e[0].trim());  // added 02/19/2008
//      answerList.add(line);
      qids.add(qid);
    }
    return qids;
  }

  private void checkAnswer(List<ItemWeight> results, Stat stat) {
    List<Pattern> patterns = getTrueAnswerPatterns(stat.getQID());
    // get a temp list of patterns since we will remove its entries
    List<Pattern> tempPatterns = new ArrayList<Pattern>(patterns);
    
    for (ItemWeight iw : results) {
      String entity = iw.getItem();
      if (entity == null) continue;
      boolean isCorrect = false;
      for (Iterator<Pattern> i = tempPatterns.iterator(); i.hasNext();) {
        Pattern p = i.next();
        if (p.matcher(entity).matches()) {
          // if matches, remove the pattern so it will not match others
          i.remove();
          isCorrect = true;
          break;
        }
      }
      stat.addAnswer(iw, isCorrect);
    }
  }
  
  private List<ItemWeight> expand(List<ItemWeight> seedWeights, List<ItemWeight> ansWeights, List<String> hints, String id) {
    if (seedWeights.isEmpty() || ansWeights.isEmpty())
      return new ArrayList<ItemWeight>();
    EntityList seeds = new EntityList(ItemWeight.toItemList(seedWeights));
    EntityList ans = new EntityList(ItemWeight.toItemList(ansWeights));
    
    if (useGoogleSets) {
      gSets.expand(seeds);
    } else {
      seal.setFeature(rankingMethod);
      seal.expand(ans, seeds, toString(hints, hintsQuoted));
//      seal.assignWeights(rankingMethod);
    }
    

    SetExpander expander = useGoogleSets ? gSets : seal;
