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 set inclusion. The Bloom
 * filter uses just one hash function; containment of elements is not optimized.
 * As it is 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; // 2^6 = 64

	// = 11..1 SHIFT_ times
	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) {
			filter_ |= 1 << (e.hashCode() & MASK_);
		}
		return success;
	}

	@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;
			}
		}
		return super.containsAll(c);
	}

	public static void logStatistics() {

		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;
	}

}

@@ -902,24 +902,58 @@
 NT_ = 0,%0A%09%09%09
+STATS_CONTAINS_ALL_POSITIVE_ = 0, 
 STATS_CONTAI
@@ -2054,23 +2054,20 @@
 %7D%0A%09%09%7D%0A%09%09
-return 
+if (
 super.co
@@ -2074,24 +2074,138 @@
 ntainsAll(c)
+) %7B%0A%09%09%09if (COLLECT_STATS_) %7B%0A%09%09%09%09STATS_CONTAINS_ALL_POSITIVE_++;%0A%09%09%09%7D%0A%09%09%09return true;%0A%09%09%7D%0A%09%09// else%0A%09%09return false
 ;%0A%09%7D%0A%0A%09publi
@@ -2308,24 +2308,142 @@
 NT_ != 0) %7B%0A
+%09%09%09%09int negativeTests = STATS_CONTAINS_ALL_COUNT_%0A%09%09%09%09%09%09- STATS_CONTAINS_ALL_POSITIVE_;%0A%09%09%09%09if (negativeTests %3E 0) %7B%0A%09
 %09%09%09%09float co
@@ -2509,16 +2509,17 @@
 _%0A%09%09%09%09%09%09
+%09
 / STATS_
@@ -2543,16 +2543,17 @@
 T_;%0A%09%09%09%09
+%09
 LOGGER_.
@@ -2569,57 +2569,53 @@
 %09%09%09%09
+%09
 %22%7B%7D 
-out of %7B%7D (%7B%7D%25) containsAll(Collection) tests
+containsAll tests, %7B%7D negative, %7B%7D (%7B%7D%25)
  fil
@@ -2622,16 +2622,17 @@
 tered%22,%0A
+%09
 %09%09%09%09%09%09ST
@@ -2652,19 +2652,38 @@
 ALL_
-FILTERED_, 
+COUNT_, negativeTests,%0A%09%09%09%09%09%09%09
 STAT
@@ -2701,22 +2701,19 @@
 ALL_
-COUNT_,%0A%09%09%09%09%09%09
+FILTERED_, 
 Stri
@@ -2729,17 +2729,26 @@
 (%22%25.2f%22,
- 
+%0A%09%09%09%09%09%09%09%09%09
 contains
@@ -2772,16 +2772,127 @@
  100));%0A
+%09%09%09%09%7D else %7B%0A%09%09%09%09%09LOGGER_.debug(%22%7B%7D containsAll tests, all positive%22,%0A%09%09%09%09%09%09%09STATS_CONTAINS_ALL_COUNT_);%0A%09%09%09%09%7D%0A
 %09%09%09%7D%0A%09%09%7D

Improve statistics for Bloom filter in the custom hash set