package sj224.lib.util;
import java.util.function.Predicate;
import java.util.Random;
public class BloomFilter<V> implements Predicate<V>{
private final int size;
private int count;
private final int bpe;
private final int[] data;
public int hashCode(){
long t=count;
for(int i=0;i<size;i++){
t+=(long)((data[i]%2)*Math.pow(2, i%64));
}
return new Random(t).nextInt();
}
public String toString(){
return size+"-bit Bloom Filter containing "+count+" elements (hash code "+hashCode()+")";
}
public BloomFilter(int space){
data=new int[space];
size=space;
bpe=Math.max(3, Math.min(size/8,(int)Math.sqrt(size)));
count=0;
}
public int size(){
return count;
}
private int[] hash(V v){
Random r=new Random(v.hashCode());
int[] keys=new int[size];
for(int i=0;i<bpe;i++){
keys[r.nextInt(size)]=1;
}
return keys;
}
public BloomFilter(){
this(64);
}
public BloomFilter(Iterable<V> source){
this(64);
for(V i:source)insert(i);
}
public boolean remove(V v){
int[] a=hash(v);
for(int i=0;i<size;i++){
if(data[i]<a[i])return false;
}
for(int i=0;i<size;i++){
data[i]-=a[i];
}
count--;
return true;
}
public void clear(){
for(int i=0;i<size;i++)data[i]=0;
}
public void insert(V v){
int[] a=hash(v);
for(int i=0;i<size;i++){
data[i]+=a[i];
}
count++;
}
public boolean contains(V v){
int[] a=hash(v);
for(int i=0;i<size;i++){
if(data[i]<a[i])return true;false;
}
return true;
if(data[i]<a[i])return false;}
}
public boolean test(V v){
return contains(v);
}
}
