/*************************************************************************

"FreePastry" Peer-to-Peer Application Development Substrate 

Copyright 2002, Rice University. All rights reserved.

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are
met:

- Redistributions of source code must retain the above copyright
notice, this list of conditions and the following disclaimer.

- Redistributions in binary form must reproduce the above copyright
notice, this list of conditions and the following disclaimer in the
documentation and/or other materials provided with the distribution.

- Neither  the name  of Rice  University (RICE) nor  the names  of its
contributors may be  used to endorse or promote  products derived from
this software without specific prior written permission.

This software is provided by RICE and the contributors on an "as is"
basis, without any representations or warranties of any kind, express
or implied including, but not limited to, representations or
warranties of non-infringement, merchantability or fitness for a
particular purpose. In no event shall RICE or contributors be liable
for any direct, indirect, incidental, special, exemplary, or
consequential damages (including, but not limited to, procurement of
substitute goods or services; loss of use, data, or profits; or
business interruption) however caused and on any theory of liability,
whether in contract, strict liability, or tort (including negligence
or otherwise) arising in any way out of the use of this software, even
if advised of the possibility of such damage.

********************************************************************************/

package rice.p2p.util;

import java.io.*;
import java.math.*;
import java.util.*;

import rice.environment.random.RandomSource;
import rice.environment.random.simple.SimpleRandomSource;

/**
 * @(#) BloomFilter.java Class which is an implementation of a bloom filter.
 * This class takes in the size which the underlying bit set should be, as well
 * as the number of hash functions which should be used. The hash functions are
 * parametrized by pre-pending and post-pending input elements with randomly
 * generates byte arrays. Thus, if the user requests two hash functions be used,
 * two random byte arrays will be generated (B_1 and B_2) and the hash functions
 * will be h_1(x) = h(B_1 || x || B_1) h_2(x) = h(B_2 || x || B_2) where h(y) is
 * the real hash function (say SHA-1). Note that the randomly generated byte
 * arrays must also be sent across the wire.
 *
 * @version $Id: BloomFilter.java,v 1.5 2005/06/24 22:49:20 jeffh Exp $
 * @author Alan Mislove
 */
public class BloomFilter implements Serializable {

  /**
   * The parameters to the hash functions for this bloom filter
   */
  protected int[] parameters;

  /**
   * The length of the set to use
   */
  protected int length;

  /**
   * The underlying bitset representation for this bloom filter
   */
  protected BitSet set;

  // cant parameterize, because object is serializable
  /**
   * The length of the random byte arrays which are generated
   */
  public static int PARAMETER_LENGTH = 4;

  /**
   * Constructor which takes the number of hash functions to use and the length
   * of the set to use.
   *
   * @param num The number of hash functions to use
   * @param length The length of the underlying bit set
   */
  public BloomFilter(int num, int length) {
    RandomSource rand = new SimpleRandomSource();
    this.length = length;
    this.set = new BitSet(length);
    this.parameters = new int[num];

    for (int i = 0; i < parameters.length; i++) {
      this.parameters[i] = MathUtils.randomInt(rand);
    }
  }

  /**
   * Method which returns what the internal bit set looks like as a string
   *
   * @return The internal bit set as a string
   */
  public String getBitSet() {
    StringBuffer buffer = new StringBuffer();
    buffer.append("[BloomFilter ");
    for (int i = 0; i < length; i++) {
      if (set.get(i)) {
        buffer.append("1");
      } else {
        buffer.append("0");
      }
    }

    buffer.append("]");

    return buffer.toString();
  }

  /**
   * Method which adds an element to this bloom filter. This is done by
   * computing h_1(x), h_2(x), ... and then setting bits (h_1(x) % length),
   * (h_2(x) % length) and so forth.
   *
   * @param array The element to add
   */
  public void add(byte[] array) {
    for (int i = 0; i < parameters.length; i++) {
      set.set(hash(array, i));
    }
  }

  /**
   * Method which returns whether or not an element *may* be in the set.
   * Specifically, if this method returns false, the element is definately not
   * in the set. Otherwise, if true is returned, the element may be in the set,
   * but it is not guaranteed.
   *
   * @param array The element to check for
   * @return DESCRIBE THE RETURN VALUE
   */
  public boolean check(byte[] array) {
    for (int i = 0; i < parameters.length; i++) {
      if (!set.get(hash(array, i))) {
        return false;
      }
    }

    return true;
  }

  /**
   * Internal method which hashes the input argument using the ith hash
   * function, and then mods the result by length.
   *
   * @param array The element to hash
   * @param i The hash function to use
   * @return DESCRIBE THE RETURN VALUE
   */
  protected int hash(byte[] array, int i) {
    if (length <= 0) {
      return 0;
    } else {
      return MathUtils.mod(doHash(array, parameters[i]), length);
    }
  }

  /**
   * Method which performs a dumb hash of the provided array and the seed value.
   *
   * @param array The input array
   * @param seed DESCRIBE THE PARAMETER
   * @return The result, which is guaranteed to be 0..length
   */
  protected int doHash(byte[] array, int seed) {
    int result = 0;
    byte[] tmp = new byte[4];

    for (int i = 0; i < array.length; i += 4) {
      System.arraycopy(array, i, tmp, 0, ((array.length - i < 4) ? (array.length - i) : 4));
      result += (result * seed) + MathUtils.byteArrayToInt(tmp);
    }

    return result;
  }
}
