public static class EntityLiteral implements Comparable<EntityLiteral> {
    public String arg1;
    public String arg2;
    public EntityLiteral(String arg1) { this.arg1=StringFactory.get(arg1); }
    public EntityLiteral(String arg1, String arg2) { this(arg1); this.arg2 = StringFactory.get(arg2); }
    public EntityLiteral(String ... names) {
        if (names.length > 0) this.arg1=StringFactory.get(names[0]);
        if (names.length > 1) this.arg2 = StringFactory.get(names[1]);
        if (names.length > 2) log.warn("Attempt to create entity literal with more than two strings:" + names);
    }
  public String toString() { 
        StringBuilder sb = new StringBuilder(arg1);
        if (arg2!= null) sb.append(Entity.RELATION_SEPARATOR).append(arg2);
        return sb.toString();
    }
  final public boolean equals(Object o) {
      if (! (o instanceof EntityLiteral)) return false;
      EntityLiteral e = (EntityLiteral) o;
      return arg1 == e.arg1 && arg2 == e.arg2; 
  }
  final public int hashCode() { 
      int a1 = arg1.hashCode();
      if (arg2!=null) return a1 ^ arg2.hashCode();
      return a1;
  }
  final public int compareTo(EntityLiteral e) {
      return this.toString().compareTo(e.toString());
  }
}
 public class Document implements Comparable<Document>, Serializable {
  public static Logger log = Logger.getLogger(Document.class);
  private static final long serialVersionUID = -1407914809895275301L;
  
  private Set<Wrapper> wrappers;
  private Set<EntityLiteral> extractions;
  private Snippet snippet;
  private String text;
  private URL url;
  private double weight = 0;
  
  public Document(String text, URL url) {
    setText(text);
    setURL(url);
    wrappers = new HashSet<Wrapper>();
    extractions = new HashSet<EntityLiteral>();
  }
  
  public void addWrapper(Wrapper wrapper) {
    if (wrapper == null || wrapper.getContents().isEmpty()) return;
    wrapper.setURL(url);
    wrappers.add(wrapper);
    extractions.addAll(wrapper.getContents());
  }
  
  public void addWrappers(Set<Wrapper> wrappers) {
    for (Wrapper wrapper : wrappers)
      addWrapper(wrapper);
  }
  
  public void clearExtractions() {
    extractions.clear();
  }
  
  public void clearWrappers() {
    wrappers.clear();
  }
  
  public int compareTo(Document doc2) {
    return Double.compare(doc2.weight, weight);
  }
  
  @Override
  public boolean equals(Object obj) {
    if (this == obj) return true;
    if (obj == null) return false;
    if (getClass() != obj.getClass()) return false;
    final Document other = (Document) obj;
    if (url == null) {
      if (other.url != null) return false;
    } else if (!url.toString().equals(other.url.toString()))
      return false;
    return true;
  }
  
  public Set<EntityLiteral> getExtractions() {
    return extractions;
  }

  public Snippet getSnippet() {
    return snippet;
  }

  public String getText() {
    return text;
  }

  public URL getURL() {
    return url;
  }

  public double getWeight() {
    return weight;
  }
  
  public Set<Wrapper> getWrappers() {
    return wrappers;
  }

  @Override
  public int hashCode() {
    return 31 + (url == null ? 0 : url.toString().hashCode());  // added 01/27/2009
  }

  public boolean isEmpty() {
    return text == null || text.trim().length() == 0;
  }

  public int length() {
    return getText().length();
  }

  protected void merge(Document document) {
    if (document == null) return;
    if (!this.equals(document)) {
      log.warn("Documents cannot be merged since they are not equal!");
      return;
    }
    addWrappers(document.getWrappers());
    setSnippet(document.getSnippet());
    setURL(document.getURL());
  }

  public void setSnippet(Snippet snippet) {
    if (this.snippet == null)
      this.snippet = snippet;
    else if (snippet != null)
      this.snippet.merge(snippet);
  }
  
  public void setText(String text) {
    this.text = text;
  }

  public void setURL(URL url) {
    if (url == null) return;
    
    if (this.url == null) {
      this.url = url;
    } else if (this.url.toString().length() > url.toString().length()) {
      // prefer shorter URL
      this.url = url;
    }
    
    /*if (this.url == null || 
        url != null && url.toString().length() < this.url.toString().length())
      this.url = url;*/
  }

  public void setWeight(double weight) {
    this.weight = weight;
  }
} public class DocumentSet implements Iterable<Document>, Serializable {
  
  public static final double DELTA = 1e-10;
  public static final int DEFAULT_MAX_DOCS_IN_XML = 5;
  
  private static final long serialVersionUID = 7211782411429869181L;
  private Map<Document, Document> docMap;
  private List<Document> docList;
  private Set<EntityLiteral> extractions;
  private Set<Wrapper> wrappers;
  private Feature scoredByFeature;
  private int maxDocsInXML;
  
  public DocumentSet() {
    setMaxDocsInXML(DEFAULT_MAX_DOCS_IN_XML);
    docMap = new HashMap<Document, Document>();
    docList = new ArrayList<Document>();
    extractions = new HashSet<EntityLiteral>();
    wrappers = new HashSet<Wrapper>();
  }
  
  public DocumentSet(DocumentSet documents) {
    this();
    addAll(documents);
  }
  
  public void add(Document document) {
    if (document == null) return;
    Document doc = docMap.get(document);
    if (doc == document) return;
    if (doc == null) {
      docMap.put(document, document);
      docList.add(document);
    } else {
      doc.merge(document);
    }
    wrappers.addAll(document.getWrappers());
    extractions.addAll(document.getExtractions());
  }
  
  public void addAll(DocumentSet documents) {
    if (documents == null) return;
    for (Document document : documents)
      add(document);
  }
  
  public void assignScore(Feature feature) {
    scoredByFeature = feature;
    if (docList.size() == 0) return;
    sort();
    double maxScore = docList.get(0).getWeight() + DELTA;
    double minScore = docList.get(docList.size()-1).getWeight() - DELTA;
    for (Document document : docList) {
      double weight = (document.getWeight() - minScore) / (maxScore - minScore);
      document.setWeight(weight);
    }
  }
  
  public void clear() {
    docMap.clear();
    docList.clear();
    extractions.clear();
    wrappers.clear();
  }
  
  public void clearExtractions() {
    for (Document document : this)
      document.clearExtractions();
    extractions.clear();
  }
  
  public void clearStats() {
    clearWrappers();
    clearExtractions();
  }
  
  /*public double getConfidence() {
    double w = 0;
    for (Document document : this) {
      if (document.length() == 0) continue;
      int sum = 0;
      for (Wrapper wrapper : document.getWrappers())
        sum += wrapper.length() * wrapper.getNumCommonTypes();
      w += (double) sum / document.length();
    }
    w = w / this.size();
    return w;
  }*/
  
  public void clearWrappers() {
    for (Document document : this)
      document.clearWrappers();
    wrappers.clear();
  }
  
  public Document get(int i) {
    return docList.get(i);
  }
  
  public double getContentQuality() {
    int numWrappers = getNumWrappers();
    if (numWrappers == 0) return 0;
    return getSumWrapperLength() / numWrappers;
  }
  
  public Set<EntityLiteral> getExtractions() {
    return extractions;
  }
  
  public int getMaxDocsInXML() {
    return maxDocsInXML;
  }
  
  public int getNumExtractions() {
    return getExtractions().size();
  }
  
  public int getNumWrappers() {
    return getWrappers().size();
  }
  
  public int getSumDocLength() {
    int sum = 0;
    for (Document document : this)
      sum += document.length();
    return sum;
  }
  
  public double getSumWrapperLength() {
    double sum = 0;
    for (Document document : this)
      for (Wrapper wrapper : document.getWrappers())
        sum += Math.log(wrapper.getContextLength()) * wrapper.getNumCommonTypes();
    return sum;
  }
  
  public Set<Wrapper> getWrappers() {
    return wrappers;
  }

  public Iterator<Document> iterator() {
    return docList.iterator();
  }
  
  public void setMaxDocsInXML(int numTopDocsInXML) {
    this.maxDocsInXML = numTopDocsInXML;
  }
  
  public int size() {
    return docList.size();
  }
  
  public void sort() {
    Collections.sort(docList);
  }
  
  public DocumentSet subList(int fromIndex, int toIndex) {
    DocumentSet docSet = new DocumentSet();
    docSet.docList = docList.subList(fromIndex, toIndex);
    for (Document document : docList)
      docSet.docMap.put(document, document);
    return docSet;
  }

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

  public Element toXMLElement(org.w3c.dom.Document document) {
    XMLUtil xml = new XMLUtil(document);
    Element documentsNode = xml.createElement("documents", null);
    xml.createAttrsFor(documentsNode, new Object[]{
        "numDocuments", docList.size(),
        "scoredBy", scoredByFeature,
    });

    for (int i = 0; i < Math.min(docList.size(), maxDocsInXML); i++) {
      Document doc = docList.get(i);
      if (doc.getWeight() == 0) continue;
      Element documentNode = xml.createElementBelow(documentsNode, "document", null);
      xml.createAttrsFor(documentNode, new Object[]{
          "rank", i+1,
          "weight", doc.getWeight(),
      });
      String title = doc.getSnippet().getTitle().toString();
      String urlStr = doc.getSnippet().getPageURL().toString();
      xml.createElementBelow(documentNode, "title", title);
      xml.createElementBelow(documentNode, "url", urlStr);
    }
    return documentsNode;
  }

  protected Feature getScoredByFeature() {
    return scoredByFeature;
  }
} public class URLBlackLister {
  
  // these are good host names and should never be blocked
  private static final List<String> GOOD_HOSTS = Arrays.asList(new String[] {
      YahooAPISearcher.HOST, GoogleWebSearcher.HOST, GoogleAPISearcher.HOST
  });
  private static Set<String> oldURLs = new HashSet<String>();  // URLs in the initial file
  private static Set<String> newURLs = new HashSet<String>();  // URLs that will be saved later
  private static Logger log = Logger.getLogger(URLBlackLister.class);
  private static File listFile = null;
  
  /**
   * Adds a URL to the black list
   * @param url
   */
  public static void addToList(URL url) {
    addToList(url, false);
  }
  
  /**
   * Adds a URL (or its host) to the black list
   * @param url the url to be added
   * @param addHost true to add only the host of this url
   */
  public static synchronized void addToList(URL url, boolean addHost) {
    if (url == null || !addHost && isListed(url))
      return;
    if (GOOD_HOSTS.contains(url.getHost()))
      return;
    String urlStr;
    if (addHost) {
      urlStr = toHostPattern(url);
      if (oldURLs.contains(urlStr) || newURLs.contains(urlStr))
        return;
      // remove all new URLs that is under this host
      String host = url.getProtocol() + "://" + url.getHost();
      for (Iterator<String> i = newURLs.iterator(); i.hasNext();)
        if (i.next().startsWith(host))
          i.remove();
    } else {
      urlStr = url.toString();
    }
//    log.debug("Black listing: " + urlStr);
    newURLs.add(urlStr);
  }
  
  public static File getListFile() {
    return listFile;
  }
  
  /**
   * Checks to see if an URL (or its host) is black listed already
   * @param url
   * @return true if an URL (or its host) is black listed
   */
  public static boolean isListed(URL url) {
    if (url == null) return false;
    String urlStr = url.toString();
    if (oldURLs.contains(urlStr) || newURLs.contains(urlStr)) {
      log.debug("Found bad URL: " + url);
      return true;
    }
    String host = toHostPattern(url);
    if (oldURLs.contains(host) || newURLs.contains(host)) {
      log.debug("Found bad host: " + url.getHost());
      return true;
    }
    return false;
  }
  
  public static void main(String args[]) throws MalformedURLException {
    URLBlackLister.setListFile(new File("filteredURLs.txt"));
    URL url = new URL("http://www.aspacepragmatism.com/2006/12/why-nasa-why-private-spaces.html");
    URLBlackLister.addToList(url, false);
    URLBlackLister.isListed(url);
    URLBlackLister.saveList();
    url = new URL("http://www.aspacepragmatism.com/abcd.html");
    URLBlackLister.addToList(url, true);
    URLBlackLister.isListed(url);
    URLBlackLister.saveList();
  }
  
  public static void saveList() {
    if (listFile != null)
      saveList(listFile);
  }
  
  /**
   * Saves black listed URLs to file by appending to the end of initial list file
   * @param listFile
   */
  public static synchronized void saveList(File listFile) {
    if (newURLs.isEmpty()) return;
    BufferedWriter out = null;
    try {
      out = new BufferedWriter(new FileWriter(listFile, true));
      for (String urlStr : newURLs) {
        out.write(urlStr);
        out.newLine();
      }
      log.debug("Saved " + newURLs.size() + " bad URLs to: " + listFile);
      oldURLs.addAll(newURLs);
      newURLs.clear();
    } catch (IOException e) {
      log.error(e.toString());
    } finally {
      try {
        if (out != null) {
          out.close();
          out = null;
        }
      } catch (IOException e) {}
    }
  }
  
  /**
   * Loads a list of URLs into the black list
   * Caution: Only ONE list can be loaded for the lifetime of this class!
   * @param file
   */
  public static void setListFile(File file) {
    if (file == null) {
//      log.error("Cannot use black list: list file is null!");
      return;
    }
    if (file.equals(listFile)) {
      return;
    } else if (listFile != null) {
      log.error("A black list has already been set: " + listFile);
      return;
    }
    log.info("Using black list: " + file);
    if (file.exists()) {
      Set<String> urls = new HashSet<String>();
      BufferedReader bReader = null;
      try {
        String line;
        bReader = new BufferedReader(new FileReader(file));
        while ((line = bReader.readLine()) != null)
          urls.add(line.trim());
      } catch (IOException e) {
        log.error(e.toString());
      } finally {
        try {
          if (bReader != null) {
            bReader.close();
            bReader = null;
          }
        } catch (IOException e) {}
      }
      oldURLs.addAll(urls);
    }
    listFile = file;
  }
  
  private static String toHostPattern(URL url) {
    return url.getProtocol() + "://" + url.getHost() + "/**";
  }
}
 public class WebFetcher {
    public static Logger log = Logger.getLogger(WebFetcher.class);
    public static GlobalVar gv = GlobalVar.getGlobalVar();

    // true to add quotation marks around queries
    public static final boolean DEFAULT_QUOTE_SEED = true;
    // true to fetch search engine's cache
    // CAUTION: IP address *will* be blocked by Google after a few queries
    public static final boolean DEFAULT_FETCH_ENGINE_CACHE = false;
    // true to remove duplicate documents (slower)
    public static final boolean DEFAULT_REMOVE_DUPLICATE_DOCS = false;
    // true to annotate the query in snippet's title and summary (slower)
    public static final boolean DEFAULT_ANNOTATE_QUERY = false;
    // total number of searchers (update getSearcher() if more engines are added)
    public static final int NUM_SEARCHERS = 5;
    public static final int ENGINE_BING_API = 4;
    public static final int ENGINE_CLUEWEB = 3;
    public static final int ENGINE_GOOGLE_WEB = 2;
    public static final int ENGINE_GOOGLE_API = 1;
    public static final int ENGINE_YAHOO_API = 0;

    private Set<Snippet> snippets;
    private String langID;
    private int numSubSeeds;
    private int numResults;
    private boolean[] useEngine;
    private boolean annotateQuery;
    private boolean fetchSearchEngineCache;
    private boolean removeDuplicateDocument;
    private boolean quoteSeed;

    public WebFetcher() {
        snippets = new HashSet<Snippet>();
        setQuoteSeed(DEFAULT_QUOTE_SEED);
        setAnnotateQuery(DEFAULT_ANNOTATE_QUERY);
        setFetchSearchEngineCache(DEFAULT_FETCH_ENGINE_CACHE);
        setRemoveDuplicateDocument(DEFAULT_REMOVE_DUPLICATE_DOCS);

        setUseEngine(gv.getUseEngine());
        setLangID(gv.getLangID());
        setNumSubSeeds(gv.getNumSubSeeds());
        setNumResults(gv.getNumResults());
    }


    public DocumentSet fetchDocuments(EntityList seeds, String hint) {
        // retrieve snippets
        DocumentSet documents = new DocumentSet();
        if (seeds == null || seeds.isEmpty())
            return documents;
        Set<Snippet> snippets = fetchSnippets(seeds, hint);
        return fetchDocuments(snippets,documents);
    }
    


    /**
     * Queries search engines and crawls the web
     * @param seeds
     * @param hint
     * @return crawled web pages
     */
    public DocumentSet fetchDocuments(Collection<String> seeds, String hint) {
        // retrieve snippets
        DocumentSet documents = new DocumentSet();
        if (seeds == null || seeds.isEmpty())
            return documents;
        Set<Snippet> snippets = fetchSnippets(seeds, hint);
        return fetchDocuments(snippets,documents);
    }
    public DocumentSet fetchDocuments(Set<Snippet> snippets,DocumentSet documents) {
        if (this.useEngine[ENGINE_CLUEWEB]) {
            documents.addAll(ClueWebSearcher.getLastRun().getDocuments());
        }
        List<URL> urls = new ArrayList<URL>();
        List<Snippet> snippetList = new ArrayList<Snippet>(snippets);
        for (Snippet snippet : snippetList) {
            if (fetchSearchEngineCache && snippet.getCacheURL() != null)
                urls.add(snippet.getCacheURL());
            else urls.add(snippet.getPageURL());
        }
        WebManager webManager = new WebManager();
        webManager.setTimeOutInMS(0);  // use auto timeout
        List<String> webpages = webManager.get(urls);
        Set<Integer> docHashSet = new HashSet<Integer>();

        for (int i = 0; i < urls.size(); i++) {
            String webpage = webpages.get(i);
            URL url = urls.get(i);
            if (webpage == null || url == null)
                continue;

            if (removeDuplicateDocument) {
                int fingerPrint = webpage.toLowerCase().replaceAll("\\W+", "").hashCode();
                if (docHashSet.contains(fingerPrint)) {
                    log.info("Found a duplicate document: " + url);
                    continue;
                }
                docHashSet.add(fingerPrint);
            }

            Document document = new Document(webpage, url);
            document.setSnippet(snippetList.get(i));
            documents.add(document);
        }
        return documents;
    }


    public Set<Snippet> fetchSnippets(EntityList seeds, String hint) {
        snippets.clear();
        if (seeds == null || seeds.isEmpty())
            return snippets;

        int numSeeds = (numSubSeeds <= 0) ? seeds.size() : Math.min(numSubSeeds, seeds.size());
        ComboMaker<Entity> comboMaker = new ComboMaker<Entity>();
        List<List<Entity>> subSeedsList = comboMaker.make(seeds.getEntities(), numSeeds);

        List<Thread> threadList = new ArrayList<Thread>();
        List<WebSearcher> searcherList = new ArrayList<WebSearcher>();
        for (int i = 0; i < subSeedsList.size(); i++)
            fetchSnippetsInThread(new EntityList(subSeedsList.get(i)).getEntityNames(), i, hint, threadList, searcherList);

        joinSnippetThreads(threadList,searcherList);
        return snippets;
    }
    /**
     * Aggressively fetch snippets
     * @param seeds
     * @param hint
     */
    public Set<Snippet> fetchSnippets(Collection<String> seeds, String hint) {
        return fetchSnippets(new EntityList(seeds),hint);
//        snippets.clear();
//        if (seeds == null || seeds.isEmpty())
//            return snippets;
//
//        int numSeeds = (numSubSeeds <= 0) ? seeds.size() : Math.min(numSubSeeds, seeds.size());
//        ComboMaker<String> comboMaker = new ComboMaker<String>();
//        List<List<String>> subSeedsList = comboMaker.make(seeds, numSeeds);
//
//        List<Thread> threadList = new ArrayList<Thread>();
//        List<WebSearcher> searcherList = new ArrayList<WebSearcher>();
//        for (int i = 0; i < subSeedsList.size(); i++)
//            fetchSnippetsInThread(new EntityList(subSeedsList.get(i)).getEntityNames(), i, hint, threadList, searcherList);
//
//        joinSnippetThreads(threadList,searcherList);
//        return snippets;
    }
    
    private void joinSnippetThreads(List<Thread> threadList, List<WebSearcher> searcherList) {
        try {
            // wait for the threads to finish
            for (int i = 0; i < threadList.size(); i++) {
                Thread searchThread = threadList.get(i);
                if (searchThread == null) continue;
                searchThread.join();
                WebSearcher searcher = searcherList.get(i);
                snippets.addAll(searcher.getSnippets());
            }
        } catch (InterruptedException ie) {}
    }

    public String getLangID() {
        return langID;
    }

    public int getNumResults() {
        return numResults;
    }

    public int getNumSubSeeds() {
        return numSubSeeds;
    }

    public Set<Snippet> getSnippets() {
        return snippets;
    }

    public boolean[] getUseEngine() {
        return useEngine;
    }

    public boolean isAnnotateQuery() {
        return annotateQuery;
    }

    public boolean isFetchSearchEngineCache() {
        return fetchSearchEngineCache;
    }

    public boolean isQuoteSeed() {
        return quoteSeed;
    }

    public boolean isRemoveDuplicateDocument() {
        return removeDuplicateDocument;
    }

    public void setAnnotateQuery(boolean annotateQuery) {
        this.annotateQuery = annotateQuery;
    }

    public void setFetchSearchEngineCache(boolean fetchSearchEngineCache) {
        this.fetchSearchEngineCache = fetchSearchEngineCache;
    }

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

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

    public void setNumSubSeeds(int numSubSeeds) {
        this.numSubSeeds = numSubSeeds;
    }

    public void setQuoteSeed(boolean addQuote) {
        this.quoteSeed = addQuote;
    }

    public void setRemoveDuplicateDocument(boolean removeDuplicateDocument) {
        this.removeDuplicateDocument = removeDuplicateDocument;
    }

    public void setUseEngine(int engine) {
        this.useEngine = Helper.toBinaryArray(engine, NUM_SEARCHERS);
        if (log.isDebugEnabled()) {
            StringBuilder sb = new StringBuilder("Using engines: ");
            StringBuilder sb2 = new StringBuilder("(others: ");
            String[] engines = new String[] {"Yahoo API","Google API","Google Web","Clue Web","Bing API"};
            for (int i=0; i<this.useEngine.length; i++) {
                if (this.useEngine[i]) sb.append(engines[i]).append(" ");
                else sb2.append(engines[i]).append(" ");
            }
            log.debug(sb.toString()+sb2.toString()+")");
        }
    }

    private void fetchSnippetsInThread(List<String[]> seeds, int index, String hint, 
            List<Thread> threadList, 
            List<WebSearcher> searcherList) {
        // create searcher threads
        for (int i = 0; i < NUM_SEARCHERS; i++) {
            WebSearcher searcher = getSearcher(i);
            if (searcher == null) continue;

            // add queries into the searcher
            for (String[] seed : seeds) {
                for (String s : seed)
                    searcher.addQuery(s, quoteSeed);
            }
            // configures the searcher
            searcher.addQuery(hint);
            searcher.setLangID(langID);
            searcher.setNumResults(numResults);
            searcher.setAnnotateQuery(annotateQuery);
            searcher.setIndex(index);

            Thread searchThread = new Thread(searcher);
            searchThread.start();
            threadList.add(searchThread);
            searcherList.add(searcher);
        }
    }

    // update NUM_SEARCHERS if more engines are added
    private WebSearcher getSearcher(int i) {
        if (!useEngine[i]) return null;
        switch (i) {
        case ENGINE_YAHOO_API: return new YahooAPISearcher();
        case ENGINE_GOOGLE_API: return new GoogleCustomAPISearcher();//GoogleAPISearcher();
        case ENGINE_GOOGLE_WEB: return new GoogleWebSearcher();
        case ENGINE_CLUEWEB: return ClueWebSearcher.getSearcher();
        case ENGINE_BING_API: return new BingAPISearcher();
        default: 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 class Snippet {

  public static Logger log = Logger.getLogger(Snippet.class);
  public static final String EXCERPT_DELIMITER = "...";
  
  private Set<Excerpt> excerpts;
  private Excerpt title;
  private String mimeType;
  private URL pageURL;
  private URL cacheURL;
  private long lastModified;
  private int rank = Integer.MAX_VALUE;
  private int cacheSize = 0;
  private int hashCode = 0;
  private int index = 0;
  
  /**
   * Removes "www" from the host name
   * @param urlStr
   * @return
   */
  private static String normalizeHost(String urlStr) {
    if (urlStr == null) return null;
    final String k = "://www";
    int p = urlStr.toLowerCase().indexOf(k);
    if (p != -1) {
      int q = urlStr.indexOf(".", p+k.length());
      if (q != -1)
        return urlStr.substring(0, p+3) + urlStr.substring(q+1);
    }
    return urlStr;
  }
  
  public Snippet() {
    excerpts = new HashSet<Excerpt>();
  }
  
  public void addExcerpt(Excerpt excerpt) {
    excerpts.add(excerpt);
    excerpt.setSnippet(this);
  }

  @Override
  public boolean equals(Object obj) {
    if (this == obj) return true;
    if (obj == null) return false;
    if (getClass() != obj.getClass()) return false;
    final Snippet other = (Snippet) obj;
    if (hashCode != other.hashCode)
      return false;
    return true;
  }

  public int getCacheSize() {
    return cacheSize;
  }

  public URL getCacheURL() {
    return cacheURL;
  }

  public Set<Excerpt> getExcerpts() {
    return excerpts;
  }

  public long getLastModified() {
    return lastModified;
  }

  public String getMimeType() {
    return mimeType;
  }

  public URL getPageURL() {
    return pageURL;
  }

  public int getRank() {
    return rank;
  }

  public Excerpt getTitle() {
    return title;
  }
  
  @Override
  public int hashCode() {
    return hashCode;
  }
  
  public void merge(Snippet snippet) {
    if (snippet == null) return;
    setRank(snippet.getRank());
    setTitle(snippet.getTitle().toString());
    setPageURL(snippet.getPageURL().toString());
    URL cacheURL = snippet.getCacheURL();
    if (cacheURL != null)
      setCacheURL(cacheURL.toString());
    excerpts.addAll(snippet.getExcerpts());
  }

  public void setCacheSize(int cacheSize) {
    this.cacheSize = cacheSize;
  }

  public void setCacheURL(String s) {
    if (s == null || s.length() == 0) return;
    // prefer shorter URL
    if (cacheURL != null && cacheURL.toString().length() <= s.length())
      return;
    try {
      cacheURL = new URL(s);
    } catch (MalformedURLException e) {
      log.error(e);
    }
  }

  public void setLastModified(long lastModified) {
    this.lastModified = lastModified;
  }

  public void setMimeType(String mimeType) {
    this.mimeType = mimeType;
  }

  public void setPageURL(String s) {
    if (s == null || s.length() == 0) return;
    // prefer shorter URL
    if (pageURL != null && pageURL.toString().length() <= s.length())
      return;
    try {
      pageURL = new URL(s);
    } catch (MalformedURLException e) {
      log.error(e);
    }
    hashCode = normalizeHost(s).hashCode();
  }

  public void setRank(int rank) {
    this.rank = Math.min(rank, this.rank);
  }
  
  public void setSummary(String summary) {
    if (summary == null || summary.length() == 0) return;
    summary = XMLUtil.removeXMLTags(summary);
    summary = XMLUtil.unescapeXMLEntities(summary);
    summary = summary.replaceAll("[ ]+", " ").trim();
    String[] excerpts = summary.split(Pattern.quote(EXCERPT_DELIMITER));
    for (String excerptStr : excerpts)
      if (excerptStr.trim().length() > 0)
        addExcerpt(new Excerpt(excerptStr.trim()));
  }

  public void setTitle(String title) {
    if (title == null || title.length() == 0) return;
    title = XMLUtil.removeXMLTags(title);
    title = XMLUtil.unescapeXMLEntities(title);
    title = title.replaceAll("[ ]+", " ").trim();
    if (title.endsWith(EXCERPT_DELIMITER))
      title = title.substring(0, title.length()-EXCERPT_DELIMITER.length());
    // prefer longer titles
    if (this.title != null && this.title.getText().length() >= title.length())
      return;
    this.title = new Excerpt(title);
    this.title.setSnippet(this);
  }

  public String toString() {
    StringBuffer buf = new StringBuffer();
    buf.append("[").append(rank).append("] Title: ").append(title).append("\n");
    if (excerpts.size() > 0) {
      buf.append("\tBody:\n");
      for (Excerpt excerpt : excerpts)
        buf.append("\t\t").append(excerpt).append("\n");
    }
    buf.append("\tPage URL: ").append(pageURL).append("\n");
    if (cacheURL != null)
      buf.append("\tCache URL: ").append(cacheURL).append("");
    return buf.toString();
  }

  public int getIndex() {
    return index;
  }

  public void setIndex(int index) {
    this.index = index;
  }
} public class OfflineSearcher {
    public static Logger log = Logger.getLogger(OfflineSearcher.class);

    private Set<String> queries = new TreeSet<String>();
    private Analyzer analyzer = new StandardAnalyzer(Version.LUCENE_30);

    private int numResults = 100;
    private Searcher searcher;
    private File rootOfIndexedFiles;


    public OfflineSearcher(File indexDir,File rootOfIndexedFiles) {
        try {
            this.rootOfIndexedFiles = rootOfIndexedFiles;
            log.info("indexDir is '" + indexDir + "'");
            if (rootOfIndexedFiles!=null) {
                log.info("paths to file names in the index are relative to '" + rootOfIndexedFiles + "'");
            } else {
                log.info("paths to files in index are absolute");
            }
            IndexReader reader = IndexReader.open(FSDirectory.open(indexDir), true); // only searching, so read-only=true
            searcher = new IndexSearcher(reader);
            if (searcher==null) {
                log.error("can't open indexSearcher for "+indexDir);
            }
        } catch (IOException ex) {
            log.error(" caught IOException opening indexDir "+indexDir+" with message: " + ex.getMessage());
        }
    } 
        
    public void setNumResults(int numResults) {
        this.numResults = numResults;
    }
    public void setLangID(String langID) {
        log.warn("Language id '"+langID+"' ignored, assuming English");
    }
    public void setUseEngine(int engine) {
        log.warn("Web search engine "+engine+" ignored, will search cache");
    }

    public DocumentSet fetchDocuments(Collection<String>seeds, String hint) {
        DocumentSet documents = new DocumentSet();
        try {
            // build the query string
            StringBuffer line = new StringBuffer("");
            for (String seed : seeds) {
                if (line.length()>0) line.append(" ");
                line.append("\"" + seed + "\"");
            }
            log.info("query line: '"+line+"'");
            if (hint!=null && hint.length()>0) {
                log.warn("ignored hint "+hint);
            }

            // submit query to lucene
            QueryParser parser = new QueryParser(Version.LUCENE_30, "contents", analyzer);
            Query query = parser.parse(line.toString());
            TopScoreDocCollector collector = TopScoreDocCollector.create(numResults, false);
            searcher.search(query, collector);
            log.info(collector.getTotalHits() + " matching documents");
            ScoreDoc[] hits = collector.topDocs().scoreDocs;

            // retrieve the matching documents
            for (int i = 0; i < hits.length && i<numResults; i++) {
                org.apache.lucene.document.Document doc = searcher.doc(hits[i].doc);
                String docLoc = doc.get("url");
                log.debug("page is at docloc: "+docLoc);
                File cacheFile;
                URL cacheFileURL;
                if (rootOfIndexedFiles!=null) {
                    cacheFile = new File(rootOfIndexedFiles,docLoc);
                    cacheFileURL = new URL("file://" + rootOfIndexedFiles + "/" + docLoc);
                } else {
                    cacheFile = new File(docLoc);                    
                    cacheFileURL = new URL("file://" + docLoc);
                }
                log.debug("found page in cache at "+docLoc + " file "+cacheFile);
                String cachedPage = Helper.readFile(cacheFile);
                if (cachedPage!=null) {
                    cachedPage = WebManager.removeCacheHeader(cachedPage);
                    Document d = new Document(cachedPage,cacheFileURL);
                    d.setWeight(hits[i].score);
                    documents.add(d);
                } else {
                    log.error("can't uncache file "+cacheFile+" from loc "+docLoc+" root "+rootOfIndexedFiles);
                }
            }
        } catch (IOException ex) {
            log.error(" caught IOException in OfflineSearcher with message: " + ex.getMessage());
        } catch (ParseException ex) {
            log.error(" caught query parse exception in OfflineSearcher with message: " + ex.getMessage());
        }
        return documents;
    }

    public static void main(String args[])  {
        String[] seedArr;
        for (int i = 0; i < args.length; i++)
            args[i] = args[i].replace('_', ' ');
        seedArr = args;
        GlobalVar gv = GlobalVar.getGlobalVar();
        OfflineSearcher searcher = new OfflineSearcher(gv.getIndexDir(), gv.getLocalRoot());
        DocumentSet documents = searcher.fetchDocuments(Arrays.asList(seedArr), null);
        System.out.println("retrieved: "+documents.size()+" documents");
        for (Document doc : documents) {
            System.out.println(".\t"+doc.getWeight()+"\t"+doc.getURL());
        }
    }
} public class Graph {

  public static class EdgeSet extends HashSet<String> {
    private static final long serialVersionUID = -6915613233385980502L;
  }
  
  public static class Node {
    public static final String SEPERATOR = ":";
    private SID id;
    private String type;
    private double weight;
    
    public Node(String name, String type) {
      id = StringFactory.toID(name);
      this.type = StringFactory.get(type);
    }    
    public Node(EntityLiteral name, String type) {
        id = StringFactory.toID(name);
        this.type = StringFactory.get(type);
      }
    
    @Override
    public boolean equals(Object obj) {
      if (this == obj) return true;
      if (obj == null) return false;
      if (getClass() != obj.getClass()) return false;
      final Node other = (Node) obj;
      if (id == null) {
        if (other.id != null) return false;
      } else if (!id.equals(other.id)) return false;
      return true;
    }
    
    public SID getID() {
      return id;
    }
    
    public String getName() {
      return StringFactory.toName(id);
    }
    
    public EntityLiteral getLiteral() {
      return id.toLiteral();
    }
    
    public String getType() {
      return type;
    }

    public double getWeight() {
      return weight;
    }

    @Override
    public int hashCode() {
      return 31 + ((id == null) ? 0 : id.hashCode());
    }

    public void setWeight(double weight) {
      this.weight = weight;
    }

    public String toString() {
      return getType() + SEPERATOR + getName();
    }
  }
  
  public static class NodeSet extends HashSet<Node> {
    private static final long serialVersionUID = -524577615563801077L;
  }
  
  public static final String CONTENT_NODE_NAME = "content";
  public static final String DOCUMENT_NODE_NAME = "document";
  public static final String WRAPPER_NODE_NAME = "wrapper";
  public static final String CONTAIN_EDGE_LABEL = "contain";
  public static final String EXTRACT_EDGE_LABEL = "extract";
  public static final String DERIVE_EDGE_LABEL = "derive";
  public static final String INVERSE_EDGE_LABEL_SUFFIX = "By";

  private Map<Node, EdgeSet> edgeMap; // node --> edges
  private Map<SID, NodeSet> nodeMap;  // edge --> nodes
  private Map<SID, Node> allNodeMap;  // id --> node
//  private NodeSet allNodes;
  
  public static String inverse(String edgeLabel) {
    return edgeLabel + INVERSE_EDGE_LABEL_SUFFIX;
  }
  
  public static void sortByWeight(List<Node> list, final boolean ascending) {
    Comparator<Node> c = new Comparator<Node>() {
      public int compare(Node e1, Node e2) {
        double w1 = e1.getWeight(), w2 = e2.getWeight();
        return ascending ? Double.compare(w1, w2) : Double.compare(w2, w1);
      }
    };
    Collections.sort(list, c);
  }
  
  public Graph() {
    edgeMap = new HashMap<Node, EdgeSet>();
    nodeMap = new HashMap<SID, NodeSet>();
//    allNodes = new NodeSet();
    allNodeMap = new HashMap<SID, Node>();
  }
  
  public void add(Node fromNode, String edgeLabel, Node toNode) {
    edgeLabel = StringFactory.get(edgeLabel);
    EdgeSet edgeSet = getEdges(fromNode);
    if (edgeSet == null) {
      edgeSet = new EdgeSet();
      edgeMap.put(fromNode, edgeSet);
    }
    edgeSet.add(edgeLabel);

    NodeSet nodeSet = followEdge(fromNode, edgeLabel);
    if (nodeSet == null) {
      nodeSet = new NodeSet();
      SID id = getFromEdgeID(fromNode, edgeLabel);
      nodeMap.put(id, nodeSet);
    }
    nodeSet.add(toNode);
//    allNodes.add(fromNode);
//    allNodes.add(toNode);
    allNodeMap.put(fromNode.getID(), fromNode);
    allNodeMap.put(toNode.getID(), toNode);
  }
  
  public void addBidirect(Node fromNode, String edgeLabel, Node toNode) {
    add(fromNode, edgeLabel, toNode);
    add(toNode, inverse(edgeLabel), fromNode);
  }
  
  public void assignWeights(SparseVector sv) {
    for (Node node : allNodeMap.values()) {
      Cell cell = sv.get(node.getID());
      if (cell == null) continue;
      node.setWeight(cell.value);
    }
  }
  
  public void clear() {
    edgeMap.clear();
    nodeMap.clear();
//    allNodes.clear();
    allNodeMap.clear();
  }
  
  public NodeSet followEdge(Node fromNode, String edgeLabel) {
    SID edgeID = getFromEdgeID(fromNode, edgeLabel);
    return nodeMap.get(edgeID);
  }
  
  public Collection<Node> getAllNodes() {
    return allNodeMap.values();
  }
  
  public EdgeSet getEdges(Node fromNode) {
    return edgeMap.get(fromNode);
  }
  
  public Node getNode(SID id) {
    return allNodeMap.get(id);
  }
  
  /*public NodeSet getAllNodes() {
    return allNodes;
  }*/
  
  public void load(DocumentSet documentSet) {
    for (Document document : documentSet) {
      String urlStr = document.getURL().toString();
      Node documentNode = new Node(urlStr, DOCUMENT_NODE_NAME);
      
      for (Wrapper wrapper : document.getWrappers()) {
        Node wrapperNode = new Node(wrapper.toString(), WRAPPER_NODE_NAME);
        addBidirect(documentNode, CONTAIN_EDGE_LABEL, wrapperNode);

        for (EntityLiteral content : wrapper.getContents()) {
          Node contentNode = new Node(content, CONTENT_NODE_NAME);
          addBidirect(wrapperNode, EXTRACT_EDGE_LABEL, contentNode);
          addBidirect(documentNode, CONTAIN_EDGE_LABEL, contentNode);
        }
      }
    }
  }

  public String toString() {
    List<Node> nodeList = new ArrayList<Node>(getAllNodes());
    sortByWeight(nodeList, false);
    StringBuffer buf = new StringBuffer();
    
    for (Node fromNode : nodeList) {
      double w = fromNode.getWeight();
      if (w != 0) buf.append(w).append("\t");
      
      String type = fromNode.getType();
      if (type.equals(Graph.CONTENT_NODE_NAME)) {
        String s = Originator.getOriginal(fromNode.getName());
        buf.append(type).append(Node.SEPERATOR).append(s);
      } else buf.append(fromNode);
      buf.append("\t");
      EdgeSet edgeSet = getEdges(fromNode);
      
      for (String edgeLabel : edgeSet) {
        NodeSet toNodes = followEdge(fromNode, edgeLabel);
        
        for (Node toNode : toNodes)
          buf.append(toNode).append("\t");
      }
      buf.setCharAt(buf.length()-1, '\n');
    }
    return buf.toString();
  }
  
  private SID getFromEdgeID(Node fromNode, String edgeLabel) {
    SID edgeID = new SID(fromNode.id);
    edgeID.append(StringFactory.get(edgeLabel));
    return edgeID;
  }
  
}
 public abstract class GraphRanker extends Ranker {

  public static final double DEFAULT_CONVERGE_THRESHOLD = 1e-3;
  public static final int DEFAULT_NUM_ITERATION = 50;
  public static final boolean DEFAULT_DISABLE_WALK = false;
  public static final int NUM_ITER_TO_OUTPUT_LEVEL = 10;
  
  public static Logger log = Logger.getLogger(GraphRanker.class);
  
  private Graph graph;
  private int numIteration;
  private double damper;
  private double convergeThreshold;
  private boolean useRelation;
  private boolean useRestart;
  private boolean disableWalk;

  public static Graph toGraph(DocumentSet documentSet) {
    Graph graph = new Graph();
    graph.load(documentSet);
    return graph;
  }
  
  public GraphRanker() {
    super();
    graph = new Graph();
    setNumIteration(DEFAULT_NUM_ITERATION);
    setConvergeThreshold(DEFAULT_CONVERGE_THRESHOLD);
    setDisableWalk(DEFAULT_DISABLE_WALK);
  }
  
  public void clear() {
    super.clear();
    graph.clear();
  }
  
  public double getConvergeThreshold() {
    return convergeThreshold;
  }

  public double getDamper() {
    return damper;
  }

  public Graph getGraph() {
    return graph;
  }
  
  public int getNumIteration() {
    return numIteration;
  }

  public boolean isDisableWalk() {
    return disableWalk;
  }

  public boolean isUseRelation() {
    return useRelation;
  }
  
  public boolean isUseRestart() {
    return useRestart;
  }

  public void load(EntityList entities, DocumentSet documentSet) {
    // load documents into graph
    graph.load(documentSet);
    
    if (disableWalk) return;
    
    // build transition matrix from graph
    SparseMatrix matrix = makeMatrix(graph);
    
    // make initial state vector
    SparseVector stateVector = makeInitVector(matrix.getColumnIDs());
    
    Set<SID> startNodes = stateVector.keySet();
    entities.clearWeight(getRankerID());
    
    for (int numIter = 0; numIter < numIteration; numIter++) {
      SparseVector sv = MatrixUtil.dotProduct(matrix, stateVector.normalize());
      if (damper < 1) {
        for (Entry<SID, Cell> entry : sv.entrySet()) {
          Cell cell = entry.getValue();
      	  double prevalue = cell.value;
          cell.value *= damper;
          if (useRestart) {
            if (startNodes.contains(entry.getKey()))
              cell.value += (1-damper) / startNodes.size();
          } else cell.value += (1-damper) / sv.size();
          log.debug(String.format("gww\t%d\t%s\t%g\t%g",numIter,entry.getKey().toLiteral().toString(),prevalue,cell.value));
        }
      }
      double euclidDistScore = MatrixUtil.euclideanDistance(sv, stateVector);
      stateVector = sv;
      if (euclidDistScore < convergeThreshold) {
        log.info("[Level " + numIter + "] Converged!!!");
        break;
      }
      if (numIter != 0 && numIter % NUM_ITER_TO_OUTPUT_LEVEL == 0)
        log.info("[Level " + numIter + "] " + euclidDistScore);
    }
    
    // insert weights into each node of the graph
    graph.assignWeights(stateVector);
    
    // transfer weights from state vector to entity list
    transferWeights(stateVector, entities, Graph.CONTENT_NODE_NAME);
  }

  public void setConvergeThreshold(double convergeThreshold) {
    this.convergeThreshold = convergeThreshold;
  }

  public void setDamper(double damper) {
    this.damper = damper;
  }
  
  public void setDisableWalk(boolean disableWalk) {
    this.disableWalk = disableWalk;
  }
  
  public void setNumIteration(int numIteration) {
    this.numIteration = numIteration;
  }

  public void setUseRelation(boolean useRelation) {
    this.useRelation = useRelation;
  }

  public void setUseRestart(boolean useRestart) {
    this.useRestart = useRestart;
  }

  private SparseVector makeInitVector(Set<SID> ids) {
    SparseVector stateVector = new SparseVector();
    if (seedDist.isEmpty()) {
      // if no seeds specified, start from all nodes
      for (SID id : ids)
        stateVector.put(id, 1.0);
    } else {
      // assign probabilities to seeds in state vector
      for (Entry<SID, Cell> entry : seedDist) {
    	
        SID id = entry.getKey();
        stateVector.put(id.toLower(), seedDist.getProbability(id));
      }
    }
    return stateVector;
  }
  
  private SparseMatrix makeMatrix(Graph graph) {
    SparseMatrix matrix = new SparseMatrix();
    NodeSet toNodeSet = new NodeSet();
    
    // start making transition matrix    
    for (Node fromNode : graph.getAllNodes()) {
      if (fromNode == null) {
        log.error("Node " + fromNode + " is null!");
        continue;
      }
      toNodeSet.clear();
      EdgeSet edgeSet = graph.getEdges(fromNode);
      double linkProb = 1.0 / edgeSet.size();
      
      for (String edgeLabel : edgeSet) {
        NodeSet toNodes = graph.followEdge(fromNode, edgeLabel);
        if (useRelation) {
          updateMatrix(matrix, fromNode, toNodes, edgeLabel, linkProb);
        } else {
          toNodeSet.addAll(toNodes);
        }
      }
      if (!useRelation)
        updateMatrix(matrix, fromNode, toNodeSet, null, linkProb);
    }
    return matrix;
  }

  private void transferWeights(SparseVector from, EntityList to, String type) {
    for (Entry<SID, Cell> entry : from) {
      SID id = entry.getKey();
      Node node = graph.getNode(id);
      if (node == null) continue;
      if (!node.getType().equals(type)) continue;
      EntityLiteral s  = id.toLiteral();
      double w = entry.getValue().value;
      Entity entity = to.add(s);
      if (entity == null) continue;
      entity.setWeight(getRankerID(), w);
    }
  }

  private void updateMatrix(SparseMatrix matrix, Node fromNode, NodeSet toNodes, 
                            String linkLabel, double linkProb) {
    double nodeProb = 1.0 / toNodes.size();
    for (Node toNode : toNodes)
      matrix.add(fromNode.getID(), toNode.getID(), linkProb * nodeProb);
  }
}
 public class PageRanker extends GraphRanker {
  
  public static final String DESCRIPTION = "PageRank";
  public static final boolean USE_RESTART = false;
  public static final boolean USE_RELATION = false;
  public static final double DAMPER = 0.85;
  
  public PageRanker() {
    super();
    setDescription(DESCRIPTION);
    setUseRestart(USE_RESTART);
    setUseRelation(USE_RELATION);
    setDamper(DAMPER);
  }
  
  /*public void reset() {
    super.clear();
    setUseRestart(USE_RESTART);
    setUseRelation(USE_RELATION);
    setDamper(DAMPER);
  }*/
}
 public abstract class Ranker {
  
  public static enum Feature { ETF, EDF, EWF, WLW, BSW, PRW, GWW}

  // list of rankers that assign log weights
  public static final Feature[] LOG_RANKERS = new Feature[] { Feature.BSW };
  
  public static Logger log = Logger.getLogger(Ranker.class);
  
  private Feature rankerID;
  protected DocumentSet documentSet;
  protected Distribution seedDist;
//  protected Distribution entityDist;
  protected String description;
  protected boolean dataModified;
  
  public static String describe(Feature feature) {
    Ranker ranker = toRanker(feature);
    if (ranker == null) return null;
    return ranker.getDescription();
  }
  
  public static boolean isLogRanker(Object feature) {
    return Arrays.asList(LOG_RANKERS).contains(feature);
  }
  
  public static List<Object> toFeatureValuePairs(Entity entity) {
    List<Object> list = new ArrayList<Object>();
    for (Feature feature : Feature.values()) {
      if (entity.containsFeature(feature)) {
        list.add(feature);
        list.add(entity.getWeight(feature));
      }
    }
    return list;
  }
  
  public static Ranker toRanker(Feature feature) {
    Ranker ranker = null;
    switch(feature) {
      case ETF: ranker = new TermFreqRanker(); break;
      case EDF: ranker = new DocFreqRanker(); break;
      case EWF: ranker = new WrapperFreqRanker(); break;
      case WLW: ranker = new WrapperLengthRanker(); break;
      case PRW: ranker = new PageRanker(); break;
      case GWW: ranker = new GraphWalkRanker(); break;
      case BSW: ranker = new BayesianRanker(); break;
      default: log.error("Unsupported ranker: " + feature);
    }
    if (ranker != null)
      ranker.setRankerID(feature); 
    return ranker;
  }
  
  protected static int getHashCode(Object o1, Object o2, Object o3) {
    final int prime = 31;
    int result = 1;
    result = prime * result + ((o1 == null) ? 0 : o1.hashCode());
    result = prime * result + ((o2 == null) ? 0 : o2.hashCode());
    result = prime * result + ((o3 == null) ? 0 : o3.hashCode());
    return result;
  }
  
  public Ranker() {
//    entityDist = new Distribution();
    seedDist = new Distribution();
  }
  
  public void addSeed(EntityLiteral seed, double weight) {
    seedDist.add(StringFactory.toID(seed), weight);
  }
  
  public void addSeeds(EntityList seeds, Object feature) {
    if (seeds == null || feature == null) return;
    for (Entity seed : seeds)
      addSeed(seed.getName(), seed.getWeight(feature));
  }
  
  public void addUniformSeeds(EntityList seeds) {
    if (seeds == null) return;
    for (Entity seed : seeds)
      addSeed(seed.getName(), 1);
  }
  
  /*public void assignWeights(EntityList entityList, DocumentSet documents) {
    Double weight;
    for (Entity entity : entityList) {
      weight = getRecommendedWeight(entity.getName());
      if (weight != null)
        entity.setWeight(getRankerID(), weight);
    }
    
    for (Document document : documents) {
      if (this instanceof GraphRanker) {
        // this ranker is a GraphRanker
        String urlStr = document.getURL().toString();
        weight = getProbability(urlStr);
      } else {
        // otherwise sum up weights of entities contained by this document
        weight = (double) 0;
        for (String content : document.getExtractions()) {
          Entity e = entityList.get(content);
          weight += (e == null) ? 0 : e.getWeight(getRankerID());
        }
      }
      document.setWeight(weight == null ? 0 : weight);
    }
  }*/

  public void clear() {
    seedDist.clear();
//    entityDist.clear();
  }
  
  public String getDescription() {
    return description;
  }
  
  /*public Double getProbability(String item) {
    return entityDist.getProbability(item);
  }*/
  
  public Feature getRankerID() {
    return rankerID;
  }
  
  /*public Double getRecommendedWeight(String item) {
    if (isLogRanker())
      return getWeight(item);
    return getProbability(item);
  }*/
  
  public Distribution getSeedDist() {
    return seedDist;
  }

  /*public Double getWeight(String item) {
    return entityDist.getWeight(item);
  }*/

  public boolean isLogRanker() {
    return isLogRanker(getRankerID());
  }
  
  public abstract void load(EntityList entities, DocumentSet documentSet);

  private void setRankerID(Feature rankerID) {
    this.rankerID = rankerID;
  }

  protected void setDescription(String description) {
    this.description = description;
  }
}
 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 PairedTrie {
  
  public static Logger log = Logger.getLogger(PairedTrie.class);
  public static final int BRACKET_MOST_WEIGHT = -2;
  public static final int BRACKET_MOST_SEEDS = -1;
  public static final int BRACKET_ALL_SEEDS = 0;
  public static final double DEFAULT_MAX_WEIGHT_RATIO = 1;  // 0.5
  public static final int MIN_TYPES = 2;  // minimum number of seeds
  public static final int MIN_LENGTH = 1; // minimum context (left or right) length
  public static final double MIN_WEIGHT = 0;  // minimum weight
  
  private Trie leftTrie, rightTrie;
  private StringBuffer reverseBuf;
  private List<Entity> entities;
  private List<MiddleContext> mcList;
  private Set<Entity> entitySet;
  private Map<MiddleContext, Set<Entity>> middleEntityMap;
  private MiddleContext middleContext;
  private Object feature;
  private double maxWeightRatio;
  
  public static void main(String args[]) {
    PairedTrie pTrie = new PairedTrie();
    pTrie.add("ef", "at", new Entity("1"));
    pTrie.add("ef", "aq", new Entity("2"));
    pTrie.add("uf", "at", new Entity("2"));
    Set<Wrapper> wrappers = pTrie.getWrappers(2, 1, 0);
    for (Wrapper wrapper : wrappers)
      log.info(wrapper);
  }
  
  public static String toMinTypeStr(int minType) {
    if (minType == BRACKET_MOST_WEIGHT)
      return "most weight";
    else if (minType == BRACKET_MOST_SEEDS)
      return "most seeds";
    else if (minType == BRACKET_ALL_SEEDS)
      return "all seeds";
    else if (minType > 0)
      return "at least " + minType + " seeds";
    else return "<unknown seeds>";
  }
  
  public PairedTrie() {
    leftTrie = new Trie();
    leftTrie.setPairedTrie(this);
    rightTrie = new Trie();
    rightTrie.setPairedTrie(this);
    reverseBuf = new StringBuffer();
    entities = new ArrayList<Entity>();
    mcList = new ArrayList<MiddleContext>();
    entitySet = new HashSet<Entity>();
    middleEntityMap = new HashMap<MiddleContext, Set<Entity>>();
    setMaxWeightRatio(DEFAULT_MAX_WEIGHT_RATIO);
  }
  
  public void add(String left, MiddleContext middle, String right, Entity entity) {
    add(left, right, entity);
    if (middle != null)
      mcList.add(middle);
  }
  
  public void add(String left, String right, Entity entity) {
    leftTrie.add(reverse(left), entities.size());
    rightTrie.add(right, entities.size());
    entities.add(entity);
  }
  
  public void clear() {
    leftTrie.clear();
    rightTrie.clear();
    reverseBuf.setLength(0);
    entities.clear();
    mcList.clear();
    entitySet.clear();
    middleEntityMap.clear();
    middleContext = null;
  }
  
  public Object getFeature() {
    return feature;
  }
  
  public Trie getLeftTrie() {
    return leftTrie;
  }
  
  public double getMaxWeightRatio() {
    return maxWeightRatio;
  }
  
  public Trie getRightTrie() {
    return rightTrie;
  }

  /**
   * retrieves longest common left and right context (LCC)
   * @param minType min. number of seeds each LCC should bracket
   * @return a set of Context objects
   */
  public Set<Wrapper> getWrappers(int minType, int minLength, double minWeight) {
    if (minType == BRACKET_MOST_WEIGHT && feature == null) {
      log.error("Error: Feature must be specified when minType is " + BRACKET_MOST_WEIGHT);
      log.error("Using minType of " + BRACKET_MOST_SEEDS + "...");
      minType = BRACKET_MOST_SEEDS;
    }
    minLength = Math.max(minLength, MIN_LENGTH);
    minWeight = Math.max(minWeight, MIN_WEIGHT);
    Set<Wrapper> wrappers = new HashSet<Wrapper>();
    
    if (minType == BRACKET_MOST_WEIGHT) {
      // contexts that bracket the most seed weights
      double maxWeight = getMaxWeight(MIN_TYPES, minLength);
      if (maxWeight < minWeight) return wrappers;
      minWeight = maxWeight * maxWeightRatio;
      
    } else if (minType == BRACKET_MOST_SEEDS) {
      // contexts that bracket the most seed types
      minType = (int) getMaxType(MIN_TYPES, minLength);
      if (minType < MIN_TYPES) return wrappers;
      
    } else if (minType == BRACKET_ALL_SEEDS) {
      // contexts that bracket exactly the input seeds
      minType = new HashSet<Entity>(entities).size();
      if (minType < MIN_TYPES) return wrappers;
    }
    minType = Math.max(minType, MIN_TYPES);
    
//    log.info("MinType: " + minType + " MinLength: " + minLength + " MinWeight: " + minWeight);
//    log.debug(this);
    
    // get longest contexts of the left and right tries
    getWrappers(leftTrie, rightTrie, true, minType, minLength, minWeight, wrappers);
    getWrappers(rightTrie, leftTrie, false, minType, minLength, minWeight, wrappers);
    return wrappers;
  }
  
  public boolean isEmpty() {
    return leftTrie.isEmpty() || rightTrie.isEmpty();
  }
  
  public boolean isRelational() {
    return !mcList.isEmpty();
  }
  
  /**
   * Features is only used for minNumType of -2
   * @param feature
   */
  public void setFeature(Object feature) {
    this.feature = feature;
  }
  
  public void setMaxWeightRatio(double maxWeightRatio) {
    this.maxWeightRatio = maxWeightRatio;
  }
  
  @Override
  public String toString() {
    StringBuffer buf = new StringBuffer();
    buf.append(Helper.center("[ List of Seed Occurrences ]", '-', 80)).append("\n");
    for (int i = 0; i < entities.size(); i++)
      buf.append(i).append(". ").append(entities.get(i).getName()).append(", ");
    buf.append("\n");
    if (!mcList.isEmpty()) {
      buf.append(Helper.center("[ Middle Contexts ]", '-', 80)).append("\n");
      for (int i = 0; i < mcList.size(); i++)
        buf.append(i).append(". ").append(mcList.get(i)).append("\n");
    }
    buf.append(Helper.center("[ Left Trie ]", '-', 80)).append("\n");
    buf.append(leftTrie.toString());
    buf.append(Helper.center("[ Right Trie ]", '-', 80)).append("\n");
    buf.append(rightTrie.toString());
    return buf.toString();
  }
  
  private double getMax(boolean isMaxWeight, int minType, int minLength) {
    double max = -1;
    for (TrieNode lNode : leftTrie.getTopNodes(minLength)) {
      if (lNode.ids.size() < MIN_TYPES) continue;
      
      for (TrieNode rNode : rightTrie.getTopNodes(minLength)) {
        if (rNode.ids.size() < MIN_TYPES) continue;
        Set<Entity> entities = getCommons(lNode.ids, rNode.ids);
        if (entities.size() < minType) continue;
        double w = isMaxWeight ? sumWeight(entities) : entities.size();
        max = Math.max(w, max);
      }
    }
    return max;
  }
  
  private double getMaxType(int minType, int minLength) {
    return getMax(false, minType, minLength);
  }
  
  private double getMaxWeight(int minType, int minLength) {
    return getMax(true, minType, minLength);
  }

  private void getWrappers(Trie trie1, Trie trie2, boolean trie1AtLeft,
                           int minType, int minLength, double minWeight, Set<Wrapper> wrappers) {
    
    // get top nodes in trie2 that have at least minLength
    List<TrieNode> topNodes = trie2.getTopNodes(minLength);
    
    // find deepest nodes in trie1 that matches the top nodes in trie2
    List<TextNode> textNodes1 = trie1.getDeepestNodes(minType, minLength, minWeight, topNodes);
    
    // a list that will only contain one trie node
    List<TrieNode> aList = new ArrayList<TrieNode>();
    
    for (TextNode textNode1 : textNodes1) {
      aList.clear();
      aList.add(textNode1.node);
      
      // find deepest nodes in trie2 that matches the deepest node in trie1
      List<TextNode> textNodes2 = trie2.getDeepestNodes(minType, minLength, minWeight, aList);
      
      for (TextNode textNode2 : textNodes2) {
        
        // constructs a Wrapper using contexts from trie1 and trie2
        String left = trie1AtLeft ? textNode1.text : textNode2.text;
        String right = trie1AtLeft ? textNode2.text : textNode1.text;
        
        // if is relational, middleContext will be set by the following
        Set<Entity> commons = getCommons(textNode1.node.ids, textNode2.node.ids);
        Wrapper wrapper = new Wrapper(reverse(left), middleContext, right);
        if (wrappers.add(wrapper))
          wrapper.setSeeds(commons);
      }
    }
  }

  private String reverse(String s) {
    reverseBuf.setLength(0);
    return reverseBuf.append(s).reverse().toString();
  }
  
  // intersects ids1 and ids2
  protected Set<Entity> getCommons(Collection<Integer> ids1, Collection<Integer> ids2) {
    middleContext = null;
    
    if (!isRelational()) {
      entitySet.clear();
      for (int id : ids1)
        if (ids2.contains(id))
          entitySet.add(entities.get(id));
      return entitySet;
    }
    
    middleEntityMap.clear();
    int maxCount = 0;
    
    for (int id : ids1) {
      if (!ids2.contains(id)) continue;
      MiddleContext mc = mcList.get(id);
      Set<Entity> entitySet = middleEntityMap.get(mc);
      if (entitySet == null) {
        entitySet = new HashSet<Entity>();
        middleEntityMap.put(mc, entitySet);
      }
      entitySet.add(entities.get(id));
      if (entitySet.size() > maxCount) {
        maxCount = entitySet.size();
        middleContext = mc;
      }
    }
    Set<Entity> commons = middleEntityMap.get(middleContext);
    if (commons == null) return new TreeSet<Entity>();
    return commons;
  }

  protected double sumWeight(Collection<Entity> entities) {
    double w = 0;
    for (Entity entity : entities)
      w += entity.getWeight(feature);
    return w;
  }
}
 public class XMLUtil {
  static public Exception exception = null;
  static private DocumentBuilderFactory dbf = DocumentBuilderFactory.newInstance();
  static private DocumentBuilder parser = null;
  
  /**
   *  XSL transform (identity) to create text from Document.
   */
  static private Transformer identityTransformer;
  
  private Document document;
  
  static {
    // XML initialization
    try {
      dbf = DocumentBuilderFactory.newInstance();
      parser = dbf.newDocumentBuilder();
    } catch (ParserConfigurationException x) {
      x.printStackTrace();
    }
  }

  static {
    TransformerFactory transformerFactory = TransformerFactory.newInstance();
    try {
      identityTransformer = transformerFactory.newTransformer();
    } catch (TransformerConfigurationException e) {
      e.printStackTrace();
    }
  }

  static public Document cloneDocument(Document document) {
    if (document == null) return null;
    Document result = newDocument();
    try {
      identityTransformer.transform(new DOMSource( document), new DOMResult( result));
    } catch (TransformerException e) {
      e.printStackTrace();
    }
    return result;
  }

  static public String document2String(Node document) {
    if (document == null) return null;

    StringWriter stringWriter = new StringWriter();
    try {
      identityTransformer.transform(new DOMSource( document), new StreamResult( stringWriter));
    } catch (TransformerException e) {
      e.printStackTrace();
    }
    return stringWriter.toString();
  }

  /**
   * Escapes special HTML entities
   * @param text
   * @return text with HTML entities escaped
   */
  public static String escapeXMLEntities(String text) {
    if (text == null)
      return null;
    text = text.replace("&", "&amp;");
    text = text.replace("\"", "&quot;");
    text = text.replace("<", "&lt;");
    text = text.replace(">", "&gt;");
    text = text.replace("'", "&#039;");
    return text;
  }
  
  /**
   *  Returns first node at the bottom of path from node.
   * If element begins with '@', indicates an attribute, eg "@id"
   * The '#text' element indicates that the node has a single text child.
   * @param node    Node to apply path to
   * @param path    Path to apply
   * @return        Node at bottom of path, or null
   */
  static public Node extractNode(Node node, String path) {
    if (node == null) return null;
    NodeList list = node.getChildNodes();
    if (path.equals("#text"))
      return  node.getFirstChild();
    else if (path.charAt(0) == '@')
      return node.getAttributes().getNamedItem( path.substring(1));
    else for (int j = 0; j < list.getLength(); j++)
      if (list.item(j).getNodeType() == Node.ELEMENT_NODE &&
          list.item(j).getNodeName().equals( path))
        return list.item(j);

    return null;
  }

  /**
   *  Returns all nodes at the bottom of path from node.
   * If element begins with '@', indicates an attribute, eg "@id"
   * The '#text' element indicates that the node has a single text child.
   * @param node    Node to apply path to
   * @param path    Path to apply
   * @return        All Nodes at bottom of path. List may be empty, but not null.
   */
  static public List<Node> extractNodes(Node node, String path) {
    if (node == null) return new ArrayList<Node>();
    List<Node> result = new ArrayList<Node>();
    NodeList list = node.getChildNodes();
    if (path.equals("#text"))
      result.add( node.getFirstChild());
    else if (path.charAt(0) == '@')
      result.add(node.getAttributes().getNamedItem( path.substring(1)));
    else for (int j = 0; j < list.getLength(); j++)
      if (list.item(j).getNodeType() == Node.ELEMENT_NODE &&
          list.item(j).getNodeName().equals( path))
        result.add( list.item(j));
    return result;
  }
  
  /**
   *  Returns first node at the bottom of path from node.
   * If element begins with '@', indicates an attribute, eg "@id"
   * The '#text' element indicates that the node has a single text child.
   * @param node    Node to apply path to
   * @param path    Path to apply
   * @return        Node at bottom of path, or null
   */
  static public Node extractPath(Node node, String[] path) {
    for (int i = 0; i < path.length; i++)
      node = extractNode( node, path[i]);
    return node;
  }

  /**
   *  Returns all nodes at the bottom of path from node.
   * If element begins with '@', indicates an attribute, eg "@id"
   * The '#text' element indicates that the node has a single text child.
   * @param node    Node to apply path to
   * @param path    Path to apply
   * @return        All nodes at bottom of path. List may be empty but not null.
   */
  static public List<Node> extractPaths(Node node, String[] path) {
    List<Node> result = new ArrayList<Node>();
    result.add( node);
    for (int i = 0; i < path.length; i++) {
      List<Node> children = new ArrayList<Node>();
      for (int j = 0; j < result.size(); j++)
        children.addAll( extractNodes((Node) result.get(j), path[i]));
      result = children;
    }
    return result;
  }

  static public Document newDocument() {
    return parser.newDocument();
  }

  static public Document parse(String text) {
    Document document = null;
    exception = null;
    try {
      document = riskyParse( text);
    } catch (Exception e) {
      exception = e;
    }
    return document;
  }

  public static String removeXMLTags(String in) {
    return in.replaceAll("<[^<>]+>", "");
  }

  public static synchronized Document riskyParse(String text) throws Exception {
    InputSource is = new InputSource(new StringReader( text));
    return parser.parse(is);
  }

  /**
   * Unescapes special HTML entities
   * @param s
   * @return text with HTML entities escaped
   */
  public static String unescapeXMLEntities(String s) {
    if (s == null) return null;
    // handles common HTML entities
    s = s.replaceAll("(?i)&amp;", "&");
    s = s.replaceAll("(?i)&gt;", ">");
    s = s.replaceAll("(?i)&lt;", "<");
    s = s.replaceAll("(?i)&quot;", "\"");
    s = s.replaceAll("(?i)&nbsp;", " ");
    s = s.replaceAll("(?i)&apos;", "'");
    s = s.replaceAll("(?i)&middot;", "·");

    // handles characters represented by (hexa)decimals
    StringBuffer sb = new StringBuffer();
    Matcher m = Pattern.compile("(?i)&#x?(\\d+);").matcher(s);
    while(m.find()) {
      int radix = m.group(0).toLowerCase().contains("x") ? 16 : 10;
      char c = (char)Integer.valueOf(m.group(1), radix).intValue();
      String rep = Character.toString(c);
      switch(c) {
      case '\\': rep = "\\\\"; break;
      case '$': rep = "\\$"; break;
      }
      m.appendReplacement(sb, rep);
    }
    m.appendTail(sb);
    return sb.toString();
  }

  public XMLUtil() {
    this(null);
  }
  
  public XMLUtil(Document document) {
    this.document = (document == null) ? newDocument() : document;
  }
  
  public Attr[] createAttrsFor(Element element, Object[] keyValuePairs) {
    int numAttrs = keyValuePairs.length / 2;
    Attr[] attrs = new Attr[numAttrs];
    for (int i = 0; i < numAttrs; i++) {
      Object keyObj = keyValuePairs[i*2];
      Object valueObj = keyValuePairs[i*2+1];
      if (keyObj == null || valueObj == null)
        continue;
      attrs[i] = document.createAttribute(keyObj.toString());
      attrs[i].setNodeValue(valueObj.toString());
    }
    for (Attr attr : attrs)
      if (attr != null)
        element.setAttributeNode(attr);
    return attrs;
  }

  /**
   *  Creates a new element with given text: <element>text</element>
   * @param element  Name of new element tag
   * @param text     Text that element tag should contain
   * @return new element node. (not actually added to document yet)
   */
  public Element createElement(String element, String text) {
    Element node = document.createElement( element);
    if (text != null) {
      Node textNode = document.createTextNode( text);
      node.insertBefore( textNode, null);
    }
    return node;
  }
  
  public Element createElementBelow(Element parentNode, String element, String text) {
    Element childNode = createElement(element, text);
    parentNode.insertBefore(childNode, null);
    return childNode;
  }

  /**
   *  Creates a new element path with given text: <element1><element2>text</element2></element1>
   * @param path     Path of new element tags
   * @param text     Text that element tag should contain
   * @return Array of new element nodes. First node is top node, last is text node.
   */
  public Element[] createPath(String[] path, String text) {
    Element[] elements = new Element[ path.length];
    for (int i = 0; i < path.length; i++)
      elements[i] = document.createElement( path[i]);
    Node textNode = document.createTextNode( text);
    for (int i = 0; i < path.length - 1; i++)
      elements[i].insertBefore( elements[i+1], null);
    elements[ path.length - 1].insertBefore( textNode, null);
    return elements;
  }
  
  public Document getDocument() {
    return document;
  }
}

import java.io.File;
import java.util.Arrays;
import java.util.ArrayList;
import java.util.Collection;
import java.util.TreeSet;
import java.util.HashSet;
import java.util.Set;
import java.net.URL;
import org.apache.log4j.Logger;
import org.w3c.dom.Element;
import com.rcwang.seal.expand.Wrapper.EntityLiteral;
import com.rcwang.seal.fetch.Document;
import com.rcwang.seal.fetch.DocumentSet;
import com.rcwang.seal.fetch.URLBlackLister;
import com.rcwang.seal.fetch.WebFetcher;
import com.rcwang.seal.fetch.WebManager;
import com.rcwang.seal.fetch.Snippet;
import com.rcwang.seal.fetch.OfflineSearcher;
import com.rcwang.seal.rank.Graph;
import com.rcwang.seal.rank.GraphRanker;
import com.rcwang.seal.rank.PageRanker;
import com.rcwang.seal.rank.Ranker;
import com.rcwang.seal.rank.Ranker.Feature;
import com.rcwang.seal.util.GlobalVar;
import com.rcwang.seal.util.Helper;
import com.rcwang.seal.util.PairedTrie;
import com.rcwang.seal.util.XMLUtil;

/**************************************************************************
 * Developed by Language Technologies Institute, Carnegie Mellon University
 * Written by Richard Wang (rcwang#cs,cmu,edu)
 *
 * and William Cohen (wcohen@cs.cmu.edu)
 *
 **************************************************************************/
package com.rcwang.seal.expand;





/** Like Seal, but uses lucene to search an indexed cache **/
public class OfflineSeal extends Pinniped {
  

    /********************** Parameters **************************/
    public static boolean readSerializedDocs = true;
    public static boolean writeSerializedDocs = false;
    /************************************************************/

    public static Logger log = Logger.getLogger(OfflineSeal.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 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 " + OfflineSeal.class.getName() + " seed_file [hint_file]");
            log.info("Usage 2: java " + OfflineSeal.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(Arrays.asList(seedArr));
    
        OfflineSeal seal = new OfflineSeal();
        seal.expand(seeds, seeds, hint);
//        seal.saveResults();
//        seal.saveWrappers();
        seal.save(); // rolled results and wrappers into SetExpander, kmr 5/11/2012
        
        System.out.println(seal.getEntityList().toDetails(100, seal.getFeature()));
        Helper.printMemoryUsed();
        Helper.printElapsedTime(startTime);
    }
  
    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);
    
        OfflineSearcher offlineSearcher = new OfflineSearcher(gv.getIndexDir(),gv.getLocalRoot());
        offlineSearcher.setLangID(langID);
        offlineSearcher.setNumResults(gv.getNumResults());
        offlineSearcher.setUseEngine(engine);
        // this ignores relational separators, since it doesn't call
        // the Entity.splitRelation method....
        // DocumentSet documents = offlineSearcher.fetchDocuments(seeds.getEntityNames(), hint);
        ArrayList<String> seedStrings = new ArrayList<String>();
        // add queries into the searcher
        for (String[] seed : seeds.getEntityNames()) {
            for (String s : seed)
                seedStrings.add(s);
        }
        DocumentSet documents = offlineSearcher.fetchDocuments(seedStrings, hint);
        int numUrlsFetched = documents.size();
    
        // output the percentage of URLs fetched
        log.info("Number of webpages retrieved from cache: " + numUrlsFetched);
        return documents;
    }
  

    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 OfflineSeal() {
        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 OfflineSeal(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);
    
        // list quality
        log.info("Estimated List Quality: " + Helper.formatNumber(getListQuality(), 3));
    
        // 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) {
