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

"FreePastry" Peer-to-Peer Application Development Substrate

Copyright 2002-2007, Rice University. Copyright 2006-2007, Max Planck Institute 
for Software Systems.  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), Max Planck Institute for Software 
Systems (MPI-SWS) 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, MPI-SWS 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, MPI-SWS 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;
import rice.p2p.commonapi.Endpoint;
import rice.p2p.commonapi.rawserialization.*;

/**
 * @(#) 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 3613 2007-02-15 14:45:14Z jstewart $
 *
 * @author Alan Mislove
 */
public class BloomFilter implements Serializable {
  
  // cant parameterize, because object is serializable
  /**
   * The length of the random byte arrays which are generated
   */
  public static int PARAMETER_LENGTH = 4;
  
  /**
   * 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;
  
  /**
   * 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(null);
    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 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
   */
  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
   */
  protected int hash(byte[] array, int i) {
    if (length <= 0)
      return 0;

    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
   * @return The result, which is guaranteed to be 0..length
   */
  protected int doHash(byte[] array, int seed) {
    byte[] tmp = new byte[array.length+4];
    MathUtils.intToByteArray(seed,tmp,0);
    System.arraycopy(array, 0, tmp, 4, array.length);
    
    return MathUtils.simpleHash(tmp);
  }
  
  /**
   * 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();
  }
  
  public void serialize(OutputBuffer buf) throws IOException {
    buf.writeInt(length);
    
    buf.writeInt(parameters.length);
    for(int i = 0; i < parameters.length; i++) {
      buf.writeInt(parameters[i]);
    }
    
    int numBits = set.length();
    buf.writeInt(numBits);
    byte curByte = 0x0;
    for(int i = 0; i < numBits; i++) {
      if (i > 0 && i%8 == 0) {
        buf.writeByte(curByte);        
        curByte = 0x0;
      }
      if (set.get(i))
        curByte |= (0x1 << i%8);
    }
    buf.writeByte(curByte);
  }
  
  public BloomFilter(InputBuffer buf) throws IOException {
    length = buf.readInt();
    
    parameters = new int[buf.readInt()];
    for(int i = 0; i < parameters.length; i++) {
      parameters[i] = buf.readInt(); 
    }

    int numBits = buf.readInt();
    set = new BitSet(numBits);
    
    byte curByte = buf.readByte();
    for (int i = 0; i < numBits; i++) {
      if (((curByte >>> i%8) & 0x1) == 0x1) {
        set.set(i);
      }
      if (i < numBits-1 && i%8 == 7) {
        curByte = buf.readByte(); 
      }
    }    
  }
  
  /**
   * Test serialize/deserialize
   * @param args
   */
  public static void main(String[] args) throws IOException {
    Random rng = new Random();
    for (int i = 0; i < 135; i++) {
      BloomFilter a = new BloomFilter(1, i);

      for (int j = 0; j < i/2; j++) {
        int flip = rng.nextInt(i);        
        a.set.flip(flip);
      }    
      System.out.println("a:"+a.set);
      final ByteArrayOutputStream baos = new ByteArrayOutputStream();
      OutputBuffer obuf = new OutputBuffer() {      
        DataOutputStream dos = new DataOutputStream(baos);        
        public void writeInt(int v) throws IOException {
          dos.writeInt(v);
        }
        public void writeByte(byte v) throws IOException {
          dos.writeByte(v);      
        }      
        public ByteArrayOutputStream getBaos() {return baos;}
        public int bytesRemaining() {throw new RuntimeException("Not Implemented.");}      
        public void writeUTF(String str) throws IOException {throw new RuntimeException("Not Implemented.");}
        public void writeShort(short v) throws IOException {throw new RuntimeException("Not Implemented.");}
        public void writeLong(long v) throws IOException {throw new RuntimeException("Not Implemented.");}
        public void writeFloat(float v) throws IOException {throw new RuntimeException("Not Implemented.");}
        public void writeDouble(double v) throws IOException {throw new RuntimeException("Not Implemented.");}
        public void writeChar(char v) throws IOException {throw new RuntimeException("Not Implemented.");}
        public void writeBoolean(boolean v) throws IOException {throw new RuntimeException("Not Implemented.");}
        public void write(byte[] b, int off, int len) throws IOException {throw new RuntimeException("Not Implemented.");}        
      };
      
      a.serialize(obuf);
      
      final ByteArrayInputStream bais = new ByteArrayInputStream(baos.toByteArray());      
      InputBuffer buf = new InputBuffer() {
        DataInputStream dis = new DataInputStream(bais);
        public int readInt() throws IOException {
          return dis.readInt();
        }
        public byte readByte() throws IOException {
          return dis.readByte();
        }
        public int bytesRemaining() {throw new RuntimeException("Not Implemented.");}
        public String readUTF() throws IOException {throw new RuntimeException("Not Implemented.");}
        public short readShort() throws IOException {throw new RuntimeException("Not Implemented.");}
        public short peakShort() throws IOException {throw new RuntimeException("Not Implemented.");}
        public long readLong() throws IOException {throw new RuntimeException("Not Implemented.");}
        public float readFloat() throws IOException {throw new RuntimeException("Not Implemented.");}
        public double readDouble() throws IOException {throw new RuntimeException("Not Implemented.");}
        public char readChar() throws IOException {throw new RuntimeException("Not Implemented.");}      
        public boolean readBoolean() throws IOException {throw new RuntimeException("Not Implemented.");}
        public int read(byte[] b) throws IOException {throw new RuntimeException("Not Implemented.");}
        public int read(byte[] b, int off, int len) throws IOException {throw new RuntimeException("Not Implemented.");}
      };

      BloomFilter b = new BloomFilter(buf);
      
      if (!b.set.equals(a.set)) {
        System.out.println(i+"a:"+a.set); 
        System.out.println(i+"b:"+b.set); 
        System.out.println(); 
      }
    }
  }
}
