/* BloomUriUniqFilter
   *
   * $Id: BloomUriUniqFilter.java 6891 2010-06-15 22:22:25Z gojomo $
   *
   * Created on June 21, 2005
   *
   * Copyright (C) 2005 Internet Archive.
   *
   * This file is part of the Heritrix web crawler (crawler.archive.org).
  *
  * Heritrix is free software; you can redistribute it and/or modify
  * it under the terms of the GNU Lesser Public License as published by
  * the Free Software Foundation; either version 2.1 of the License, or
  * any later version.
  *
  * Heritrix is distributed in the hope that it will be useful,
  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  * GNU Lesser Public License for more details.
  *
  * You should have received a copy of the GNU Lesser Public License
  * along with Heritrix; if not, write to the Free Software
  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  */
  package org.archive.crawler.util;
  
  import java.io.Serializable;
  import java.util.logging.Logger;
  
  import org.archive.crawler.datamodel.CandidateURI;
  import org.archive.util.BloomFilter;
  import org.archive.util.BloomFilter64bit;
  
  
  /***
   * A MG4J BloomFilter-based implementation of an AlreadySeen list.
   *
   * This implementation performs adequately without blowing out
   * the heap through to very large numbers of URIs. See
   * <a href="http://crawler.archive.org/cgi-bin/wiki.pl?AlreadySeen">AlreadySeen</a>.
   * 
   * It is inherent to Bloom filters that as they get 'saturated', their
   * false-positive rate rises. The default parameters used by this class
   * attempt to maintain a 1-in-4 million (1 in 2^22) false-positive chance
   * through 125 million unique inserts, which creates a filter structure 
   * about 495MB in size. 
   * 
   * You may use the following system properties to tune the size and 
   * false-positive rate of the bloom filter structure used by this class:
   * 
   *  org.archive.crawler.util.BloomUriUniqFilter.expected-size (default 125000000)
   *  org.archive.crawler.util.BloomUriUniqFilter.hash-count (default 22)
   * 
   * The resulting filter will take up approximately...
   * 
   *    1.44 * expected-size * hash-count / 8 
   *    
   * ...bytes. 
   * 
   * The default size is very close to the maximum practical size of the 
   * Bloom filter implementation, BloomFilter32bitSplit, created in the
   * initialize() method, due to integer arithmetic limits. 
   * 
   * If you need a larger filter, you should edit the initialize 
   * method to intantiate a BloomFilter64bit instead.  
   * 
   * @author gojomo
   * @version $Date: 2010-06-15 22:22:25 +0000 (Tue, 15 Jun 2010) $, $Revision: 6891 $
   */
  public class BloomUriUniqFilter extends SetBasedUriUniqFilter
  implements Serializable {
  	private static final long serialVersionUID = 1061526253773091309L;
  
  	private static Logger LOGGER =
          Logger.getLogger(BloomUriUniqFilter.class.getName());
  
      BloomFilter bloom; // package access for testing convenience
      protected int expected_n; // remember bloom contruction param
  
      protected static final String EXPECTED_SIZE_KEY = ".expected-size";
      protected static final String HASH_COUNT_KEY = ".hash-count";
  
      // these defaults create a bloom filter that is
      // 1.44*125mil*22/8 ~= 495MB in size, and at full
      // capacity will give a false contained indication
      // 1/(2^22) ~= 1 in every 4 million probes
      private static final int DEFAULT_EXPECTED_SIZE = 125000000; // 125 million
      private static final int DEFAULT_HASH_COUNT = 22; // 1 in 4 million false pos
  
      /***
       * Default constructor
       */
      public BloomUriUniqFilter() {
          super();
          String ns = System.getProperty(this.getClass().getName() + EXPECTED_SIZE_KEY);
          int n = (ns == null) ? DEFAULT_EXPECTED_SIZE : Integer.parseInt(ns);
          String ds = System.getProperty(this.getClass().getName() + HASH_COUNT_KEY);
          int d = (ds == null) ? DEFAULT_HASH_COUNT : Integer.parseInt(ds);
          initialize(n,d);
     }
 
     /***
      * Constructor.
      *
      * @param n the expected number of elements.
      * @param d the number of hash functions; if the filter adds not more
      * than <code>n</code> elements, false positives will happen with
      * probability 2<sup>-<var>d</var></sup>.
      */
     public BloomUriUniqFilter( final int n, final int d ) {
         super();
         initialize(n, d);
     }
 
     /***
      * Initializer shared by constructors.
      *
      * @param n the expected number of elements.
      * @param d the number of hash functions; if the filter adds not more
      * than <code>n</code> elements, false positives will happen with
      * probability 2<sup>-<var>d</var></sup>.
      */
     protected void initialize(final int n, final int d) {
         this.expected_n = n;
         bloom = new BloomFilter64bit(n,d);
     }
 
     public void forget(String canonical, CandidateURI item) {
         // TODO? could use in-memory exception list of currently-forgotten items
         LOGGER.severe("forget(\""+canonical+"\",CandidateURI) not supported");
     }
 
     
     protected boolean setAdd(CharSequence uri) {
         boolean added = bloom.add(uri);
         // warn if bloom has reached its expected size (and its false-pos
         // rate will now exceed the theoretical/designed level)
         if( added && (count() == expected_n)) {
             LOGGER.warning("Bloom has reached expected limit "+expected_n);
         }
         return added;
     }
 
     protected long setCount() {
         return bloom.size();
     }
 
     protected boolean setRemove(CharSequence uri) {
         throw new UnsupportedOperationException();
     }
 }