package org.semanticweb.elk.justifications;

import java.util.Collection;
import java.util.HashSet;
import java.util.Set;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

/**
 * A set enhanced with a Bloom filter to quickly check containment of elements.
 * As common with Bloom filters, removal of elements is not supported.
 * 
 * @see Set#contains(Object)
 * @see Set#containsAll(Collection)
 * 
 * @author Yevgeny Kazakov
 *
 * @param <E>
 *            the type of elements maintained by this set
 */
class BloomHashSet<E> extends HashSet<E> {

	private static final long serialVersionUID = -4655731436488514715L;

	private static final Logger LOGGER_ = LoggerFactory
			.getLogger(BloomHashSet.class);

	private static final boolean COLLECT_STATS_ = true;

	private static int STATS_CONTAINS_ALL_COUNT_ = 0,
			STATS_CONTAINS_ALL_FILTERED_ = 0;

	private static final short SHIFT_ = 6;

	private static final int MASK_ = (1 << SHIFT_) - 1;

	private long filter_ = 0L;

	public BloomHashSet() {
		super();
	}

	public BloomHashSet(int initialCapacity) {
		super(initialCapacity);
	}

	public BloomHashSet(Collection<? extends E> c) {
		this(c.size());
		addAll(c);
	}

	@Override
	public boolean add(E e) {
		boolean success = super.add(e);
		if (success) {
			int hash = e.hashCode();
			filter_ |= 1 << (hash & MASK_);
			hash >>= SHIFT_;
			filter_ |= 1 << (hash & MASK_);
			hash >>= SHIFT_;
			filter_ |= 1 << (hash & MASK_);
		}
		return success;
	}

	@Override
	public boolean contains(Object o) {
		int hash = o.hashCode();
		long mask = 1 << (hash & MASK_);
		hash >>= SHIFT_;
		mask |= 1 << (hash & MASK_);
		hash >>= SHIFT_;
		mask |= 1 << (hash & MASK_);
		if ((filter_ & mask) != mask) {
			return false;
		}
		// else
		return super.contains(o);
	}

	@Override
	public boolean remove(Object o) {
		throw new UnsupportedOperationException(
				"Removal of elements not supported");
	}

	@Override
	public void clear() {
		super.clear();
		filter_ = 0;
	}

	@Override
	public boolean containsAll(Collection<?> c) {
		if (COLLECT_STATS_) {
			STATS_CONTAINS_ALL_COUNT_++;
		}
		if (c instanceof BloomHashSet<?>) {
			long otherFilter = ((BloomHashSet<?>) c).filter_;
			if ((filter_ & otherFilter) != otherFilter) {
				if (COLLECT_STATS_) {
					STATS_CONTAINS_ALL_FILTERED_++;
				}
				return false;
			}
		}
		for (Object e : c)
			// no need to apply filter for contains test
			if (!super.contains(e))
				return false;
		return true;
	}

	public static void printStatistics() {

		if (LOGGER_.isDebugEnabled()) {
			if (STATS_CONTAINS_ALL_COUNT_ != 0) {
				float containsAllSuccessRatio = (float) STATS_CONTAINS_ALL_FILTERED_
						/ STATS_CONTAINS_ALL_COUNT_;
				LOGGER_.debug(
						"{} out of {} ({}%) containsAll(Collection) tests filtered",
						STATS_CONTAINS_ALL_FILTERED_, STATS_CONTAINS_ALL_COUNT_,
						String.format("%.2f", containsAllSuccessRatio * 100));
			}
		}
	}

	public static void resetStatistics() {
		STATS_CONTAINS_ALL_COUNT_ = 0;
		STATS_CONTAINS_ALL_FILTERED_ = 0;
	}

}

@@ -237,37 +237,124 @@
 eck 
-containment of elements.%0A * A
+set inclusion. The Bloom%0A * filter uses just one hash function; containment of elements is not optimized.%0A * As it i
 s co
@@ -980,17 +980,54 @@
 FT_ = 6;
-%0A
+ // 2%5E6 = 64%0A%0A%09// = 11..1 SHIFT_ times
 %0A%09privat
@@ -1397,505 +1397,68 @@
 %0A%09%09%09
-int hash = e.hashCode();%0A%09%09%09filter_ %7C= 1 %3C%3C (hash & MASK_);%0A%09%09%09hash %3E%3E= SHIFT_;%0A%09%09%09filter_ %7C= 1 %3C%3C (hash & MASK_);%0A%09%09%09hash %3E%3E= SHIFT_;%0A%09%09%09filter_ %7C= 1 %3C%3C (hash & MASK_);%0A%09%09%7D%0A%09%09return success;%0A%09%7D%0A%0A%09@Override%0A%09public boolean contains(Object o) %7B%0A%09%09int hash = o.hashCode();%0A%09%09long mask = 1 %3C%3C (hash & MASK_);%0A%09%09hash %3E%3E= SHIFT_;%0A%09%09mask %7C= 1 %3C%3C (hash & MASK_);%0A%09%09hash %3E%3E= SHIFT_;%0A%09%09mask %7C= 1 %3C%3C (hash & MASK_);%0A%09%09if ((filter_ & mask) != mask) %7B%0A%09%09%09return false;%0A%09%09%7D%0A%09%09// else%0A%09%09return super.contains(o)
+filter_ %7C= 1 %3C%3C (e.hashCode() & MASK_);%0A%09%09%7D%0A%09%09return success
 ;%0A%09%7D
@@ -2024,133 +2024,35 @@
 %7D%0A%09%09
-for (Object e : c)%0A%09%09%09// no need to apply filter for contains test%0A%09%09%09if (!super.contains(e))%0A%09%09%09%09return false;%0A%09%09return true
+return super.containsAll(c)
 ;%0A%09%7D

Simplify Bloom filter used in the custom HashSet