/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.apache.commons.collections4.bloomfilter;

import static org.junit.jupiter.api.Assertions.assertArrayEquals;
import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertFalse;
import static org.junit.jupiter.api.Assertions.assertNotEquals;
import static org.junit.jupiter.api.Assertions.assertNotSame;
import static org.junit.jupiter.api.Assertions.assertThrows;
import static org.junit.jupiter.api.Assertions.assertTrue;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.BitSet;
import java.util.List;

import org.junit.jupiter.api.Test;

/**
 * Tests standard methods in the {@link BloomFilter} interface.
 */
public abstract class AbstractBloomFilterTest<T extends BloomFilter> {

    /**
     * Test fixture class returns the value as the only value.
     */
    public static class BadHasher implements Hasher {

        IndexExtractor extractor;

        public BadHasher(final int value) {
            this.extractor = IndexExtractor.fromIndexArray(value);
        }

        @Override
        public IndexExtractor indices(final Shape shape) {
            return extractor;
        }
    }

    private void assertFailedIndexExtractorConstructor(final Shape shape, final int[] values) {
        final IndexExtractor indices = IndexExtractor.fromIndexArray(values);
        assertThrows(IllegalArgumentException.class, () -> createFilter(shape, indices));
    }

    private void assertIndexExtractorMerge(final Shape shape, final int[] values, final int[] expected) {
        final IndexExtractor indices = IndexExtractor.fromIndexArray(values);
        final BloomFilter filter = createFilter(shape, indices);
        final List<Integer> lst = new ArrayList<>();
        filter.processIndices(x -> {
            lst.add(x);
            return true;
        });
        assertEquals(expected.length, lst.size());
        for (final int value : expected) {
            assertTrue(lst.contains(Integer.valueOf(value)), "Missing " + value);
        }
    }

    /**
     * Creates an empty version of the BloomFilter implementation we are testing.
     *
     * @param shape the shape of the filter.
     * @return a BloomFilter implementation.
     */
    protected abstract T createEmptyFilter(Shape shape);

    /**
     * Creates the BloomFilter implementation we are testing.
     *
     * @param shape the shape of the filter.
     * @param extractor A BitMap extractor to build the filter with.
     * @return a BloomFilter implementation.
     */
    protected final T createFilter(final Shape shape, final BitMapExtractor extractor) {
        final T bf = createEmptyFilter(shape);
        bf.merge(extractor);
        return bf;
    }

    /**
     * Creates the BloomFilter implementation we are testing.
     *
     * @param shape the shape of the filter.
     * @param hasher the hasher to use to create the filter.
     * @return a BloomFilter implementation.
     */
    protected final T createFilter(final Shape shape, final Hasher hasher) {
        final T bf = createEmptyFilter(shape);
        bf.merge(hasher);
        return bf;
    }

    /**
     * Creates the BloomFilter implementation we are testing.
     *
     * @param shape the shape of the filter.
     * @param extractor An Index extractor to build the filter with.
     * @return a BloomFilter implementation.
     */
    protected final T createFilter(final Shape shape, final IndexExtractor extractor) {
        final T bf = createEmptyFilter(shape);
        bf.merge(extractor);
        return bf;
    }

    /**
     * The shape of the Bloom filters for testing.
     * <ul>
     *  <li>Hash functions (k) = 17
     *  <li>Number of bits (m) = 72
     * </ul>
     * @return the testing shape.
     */
    protected Shape getTestShape() {
        return Shape.fromKM(17, 72);
    }

    /**
     * Tests that asBitMapArray works correctly.
     */
    @Test
    public final void testAsBitMapArray() {

        // test when multiple long values are returned.
        final IncrementingHasher hasher = new IncrementingHasher(63, 1);
        final BloomFilter bf = createFilter(Shape.fromKM(2, 72), hasher);
        final long[] lb = bf.asBitMapArray();
        assertEquals(2, lb.length);
        assertEquals(0x8000000000000000L, lb[0]);
        assertEquals(0x1, lb[1]);
    }

    @Test
    public void testBitMapExtractorSize() {
        final int[] idx = new int[1];
        createFilter(getTestShape(), TestingHashers.FROM1).processBitMaps(i -> {
            idx[0]++;
            return true;
        });
        assertEquals(BitMaps.numberOfBitMaps(getTestShape()), idx[0]);

        idx[0] = 0;
        createEmptyFilter(getTestShape()).processBitMaps(i -> {
            idx[0]++;
            return true;
        });
        assertEquals(BitMaps.numberOfBitMaps(getTestShape()), idx[0]);
    }

    @Test
    public void testCardinalityAndIsEmpty() {
        testCardinalityAndIsEmpty(createEmptyFilter(getTestShape()));
    }

    /**
     * Tests cardinality and isEmpty. Bloom filter must be able to accept multiple
     * IndexExtractor merges until all the bits are populated.
     *
     * @param bf The Bloom filter to test.
     */
    protected void testCardinalityAndIsEmpty(final BloomFilter bf) {
        assertTrue(bf.isEmpty());
        assertEquals(0, bf.cardinality());
        for (int i = 0; i < getTestShape().getNumberOfBits(); i++) {
            bf.merge(IndexExtractor.fromIndexArray(i));
            assertFalse(bf.isEmpty(), "Wrong value at " + i);
            assertEquals(i + 1, bf.cardinality(), "Wrong value at " + i);
        }

        // check operations in reverse order
        bf.clear();
        assertEquals(0, bf.cardinality());
        assertTrue(bf.isEmpty());
        for (int i = 0; i < getTestShape().getNumberOfBits(); i++) {
            bf.merge(IndexExtractor.fromIndexArray(i));
            assertEquals(i + 1, bf.cardinality(), "Wrong value at " + i);
            assertFalse(bf.isEmpty(), "Wrong value at " + i);
        }
    }

    @Test
    public void testClear() {
        final BloomFilter bf1 = createFilter(getTestShape(), TestingHashers.FROM1);
        assertNotEquals(0, bf1.cardinality());
        bf1.clear();
        assertEquals(0, bf1.cardinality());
    }

    @Test
    public final void testContains() {
        BloomFilter bf1 = createFilter(getTestShape(), TestingHashers.FROM1);
        final BloomFilter bf2 = TestingHashers.populateFromHashersFrom1AndFrom11(createEmptyFilter(getTestShape()));

        assertTrue(bf1.contains(bf1), "BF1 Should contain itself");
        assertTrue(bf2.contains(bf2), "BF2 Should contain itself");
        assertFalse(bf1.contains(bf2), "BF1 should not contain BF2");
        assertTrue(bf2.contains(bf1), "BF2 should contain BF1");

        assertTrue(bf2.contains(new IncrementingHasher(1, 1)), "BF2 Should contain this hasher");
        assertFalse(bf2.contains(new IncrementingHasher(1, 3)), "BF2 Should not contain this hasher");

        IndexExtractor indexExtractor = new IncrementingHasher(1, 1).indices(getTestShape());
        assertTrue(bf2.contains(indexExtractor), "BF2 Should contain this hasher");
        indexExtractor = new IncrementingHasher(1, 3).indices(getTestShape());
        assertFalse(bf2.contains(indexExtractor), "BF2 Should not contain this hasher");

        BitMapExtractor bitMapExtractor = BitMapExtractor.fromIndexExtractor(new IncrementingHasher(1, 1).indices(getTestShape()),
                getTestShape().getNumberOfBits());
        assertTrue(bf2.contains(bitMapExtractor), "BF2 Should contain this hasher");
        bitMapExtractor = BitMapExtractor.fromIndexExtractor(new IncrementingHasher(1, 3).indices(getTestShape()), getTestShape().getNumberOfBits());
        assertFalse(bf2.contains(bitMapExtractor), "BF2 Should not contain this hasher");

        // Test different lengths
        bf1 = createFilter(getTestShape(), TestingHashers.FROM1);
        final BloomFilter bf3 = createFilter(Shape.fromKM(getTestShape().getNumberOfHashFunctions(), Long.SIZE - 1), TestingHashers.FROM1);
        assertTrue(bf1.contains(bf3));
        assertTrue(bf3.contains(bf1));

        final BloomFilter bf4 = TestingHashers.populateRange(createEmptyFilter(Shape.fromKM(getTestShape().getNumberOfHashFunctions(), Long.SIZE - 1)), 1,
                11 + getTestShape().getNumberOfHashFunctions());

        assertFalse(bf1.contains(bf4));
        assertTrue(bf4.contains(bf1));
    }

    @Test
    public void testCopy() {
        testCopy(true);
    }

    protected void testCopy(final boolean assertClass) {
        final BloomFilter bf1 = createFilter(getTestShape(), TestingHashers.FROM1);
        assertNotEquals(0, bf1.cardinality());
        final BloomFilter copy = bf1.copy();
        assertNotSame(bf1, copy);
        assertArrayEquals(bf1.asBitMapArray(), copy.asBitMapArray());
        assertArrayEquals(bf1.asIndexArray(), copy.asIndexArray());
        assertEquals(bf1.cardinality(), copy.cardinality());
        assertEquals(bf1.characteristics(), copy.characteristics());
        assertEquals(bf1.estimateN(), copy.estimateN());
        if (assertClass) {
            assertEquals(bf1.getClass(), copy.getClass());
        }
        assertEquals(bf1.getShape(), copy.getShape());
        assertEquals(bf1.isEmpty(), copy.isEmpty());
        assertEquals(bf1.isFull(), copy.isFull());
    }

    @Test
    public void testEmptyAfterMergeWithNothing() {
        // test the case where is empty after merge
        // in this case the internal cardinality == -1
        final BloomFilter bf = createEmptyFilter(getTestShape());
        bf.merge(IndexExtractor.fromIndexArray());
        assertTrue(bf.isEmpty());
    }

    /**
     * Tests that the estimated intersection calculations are correct.
     */
    @Test
    public final void testEstimateIntersection() {
        final BloomFilter bf = createFilter(getTestShape(), TestingHashers.FROM1);
        final BloomFilter bf2 = TestingHashers.populateFromHashersFrom1AndFrom11(createEmptyFilter(getTestShape()));

        final BloomFilter bf3 = TestingHashers.populateEntireFilter(createEmptyFilter(getTestShape()));

        assertEquals(1, bf.estimateIntersection(bf2));
        assertEquals(1, bf2.estimateIntersection(bf));
        assertEquals(1, bf.estimateIntersection(bf3));
        assertEquals(1, bf2.estimateIntersection(bf));
        assertEquals(2, bf3.estimateIntersection(bf2));

        final BloomFilter bf4 = createEmptyFilter(getTestShape());

        assertEquals(0, bf.estimateIntersection(bf4));
        assertEquals(0, bf4.estimateIntersection(bf));

        final int midPoint = getTestShape().getNumberOfBits() / 2;
        final BloomFilter bf5 = TestingHashers.populateRange(createEmptyFilter(getTestShape()), 0, midPoint);
        final BloomFilter bf6 = TestingHashers.populateRange(createEmptyFilter(getTestShape()), midPoint + 1, getTestShape().getNumberOfBits() - 1);
        assertThrows(IllegalArgumentException.class, () -> bf5.estimateIntersection(bf6));

        // infinite with infinite
        assertEquals(Integer.MAX_VALUE, bf3.estimateIntersection(bf3));
    }

    /**
     * Tests that the size estimate is correctly calculated.
     */
    @Test
    public final void testEstimateN() {
        // build a filter
        BloomFilter filter1 = createFilter(getTestShape(), TestingHashers.FROM1);
        assertEquals(1, filter1.estimateN());

        // the data provided above do not generate an estimate that is equivalent to the
        // actual.
        filter1.merge(new IncrementingHasher(4, 1));
        assertEquals(1, filter1.estimateN());

        filter1.merge(new IncrementingHasher(17, 1));

        assertEquals(3, filter1.estimateN());

        filter1 = TestingHashers.populateEntireFilter(createEmptyFilter(getTestShape()));
        assertEquals(Integer.MAX_VALUE, filter1.estimateN());
    }

    /**
     * Tests that the estimated union calculations are correct.
     */
    @Test
    public final void testEstimateUnion() {
        final BloomFilter bf = createFilter(getTestShape(), TestingHashers.FROM1);
        final BloomFilter bf2 = createFilter(getTestShape(), TestingHashers.FROM11);

        assertEquals(2, bf.estimateUnion(bf2));
        assertEquals(2, bf2.estimateUnion(bf));

        final BloomFilter bf3 = createEmptyFilter(getTestShape());

        assertEquals(1, bf.estimateUnion(bf3));
        assertEquals(1, bf3.estimateUnion(bf));
    }

    @Test
    public void testIndexExtractorMerge() {
        final Shape shape = Shape.fromKM(5, 10);

        assertIndexExtractorMerge(shape, new int[] {0, 2, 4, 6, 8}, new int[] {0, 2, 4, 6, 8});
        // test duplicate values
        assertIndexExtractorMerge(shape, new int[] {0, 2, 4, 2, 8}, new int[] {0, 2, 4, 8});
        // test negative values
        assertFailedIndexExtractorConstructor(shape, new int[] {0, 2, 4, -2, 8});
        // test index too large
        assertFailedIndexExtractorConstructor(shape, new int[] {0, 2, 4, 12, 8});
        // test no indices
        assertIndexExtractorMerge(shape, new int[0], new int[0]);
    }

    /**
     * Tests that isFull() returns the proper values.
     */
    @Test
    public final void testIsFull() {

        // create empty filter
        BloomFilter filter = createEmptyFilter(getTestShape());
        assertFalse(filter.isFull(), "Should not be full");

        filter = TestingHashers.populateEntireFilter(filter);
        assertTrue(filter.isFull(), "Should be full");

        filter = createFilter(getTestShape(), new IncrementingHasher(1, 3));
        assertFalse(filter.isFull(), "Should not be full");
    }

    /**
     * Tests that merging bloom filters works as expected with a generic BloomFilter.
     */
    @Test
    public final void testMerge() {

        final BloomFilter bf1 = createFilter(getTestShape(), TestingHashers.FROM1);
        final BloomFilter bf2 = createFilter(getTestShape(), TestingHashers.FROM11);
        final BloomFilter bf3 = bf1.copy();
        bf3.merge(bf2);

        // test with BloomFilter

        final long[] bf1Val = bf1.asBitMapArray();
        final long[] bf2Val = bf2.asBitMapArray();
        for (int i = 0; i < bf1Val.length; i++) {
            bf1Val[i] |= bf2Val[i];
        }
        bf1.merge(bf2);

        final long[] bf1New = bf1.asBitMapArray();
        for (int i = 0; i < bf1Val.length; i++) {
            assertEquals(bf1Val[i], bf1New[i], "Bad value at " + i);
        }

        assertTrue(bf1.contains(bf2), "Should contain bf2");
        assertTrue(bf1.contains(bf3), "Should contain bf3");

        // test with hasher

        final BloomFilter bf4 = createFilter(getTestShape(), TestingHashers.FROM1);
        bf4.merge(TestingHashers.FROM11);

        assertTrue(bf4.contains(bf2), "Should contain Bf2");
        assertTrue(bf4.contains(bf3), "Should contain Bf3");

        // test with hasher returning numbers out of range
        assertThrows(IllegalArgumentException.class,
                () -> bf1.merge(new BadHasher(bf1.getShape().getNumberOfBits())));
        assertThrows(IllegalArgumentException.class, () -> bf1.merge(new BadHasher(-1)));

        // test error when bloom filter returns values out of range
        final Shape s = Shape.fromKM(getTestShape().getNumberOfHashFunctions(), getTestShape().getNumberOfBits() * 3);
        final Hasher h = new IncrementingHasher(getTestShape().getNumberOfBits() * 2, 1);
        final BloomFilter bf5 = new SimpleBloomFilter(s);
        bf5.merge(h);
        assertThrows(IllegalArgumentException.class, () -> bf1.merge(bf5));

        final BloomFilter bf6 = new SparseBloomFilter(s);
        bf6.merge(h);
        assertThrows(IllegalArgumentException.class, () -> bf1.merge(bf6));
    }

    @Test
    public void testMergeWithBadHasher() {
        // value too large
        final BloomFilter f = createEmptyFilter(getTestShape());
        assertThrows(IllegalArgumentException.class,
                () -> f.merge(new BadHasher(getTestShape().getNumberOfBits())));
        // negative value
        final BloomFilter f2 = createEmptyFilter(getTestShape());
        assertThrows(IllegalArgumentException.class, () -> f2.merge(new BadHasher(-1)));
    }

    @Test
    public void testMergeWithBitMapExtractor() {
        final int bitMapCount = BitMaps.numberOfBitMaps(getTestShape());
        for (int i = 0; i < 5; i++) {
            final long[] values = new long[bitMapCount];
            for (final int idx : DefaultIndexExtractorTest.generateIntArray(getTestShape().getNumberOfHashFunctions(), getTestShape().getNumberOfBits())) {
                BitMaps.set(values, idx);
            }
            final BloomFilter f = createFilter(getTestShape(), BitMapExtractor.fromBitMapArray(values));
            final List<Long> lst = new ArrayList<>();
            for (final long l : values) {
                lst.add(l);
            }
            assertTrue(f.processBitMaps(l -> lst.remove(Long.valueOf(l))));
            assertTrue(lst.isEmpty());
        }
        // values too large
        final long[] values = new long[bitMapCount];
        Arrays.fill(values, Long.MAX_VALUE);
        final BitMapExtractor badExtractor = BitMapExtractor.fromBitMapArray(values);
        final BloomFilter bf = createEmptyFilter(getTestShape());
        assertThrows(IllegalArgumentException.class, () -> bf.merge(badExtractor));

        // test where merged bits exceed expected bits but both bitmaps are the same length.
        final BitMapExtractor badExtractor2 = BitMapExtractor.fromBitMapArray(0x80_00_00_00_00_00_00_00L);
        final BloomFilter bf2 = createEmptyFilter(Shape.fromKM(3, 32));
        assertThrows(IllegalArgumentException.class, () -> bf2.merge(badExtractor2));
    }

    @Test
    public void testMergeWithHasher() {
        for (int i = 0; i < 5; i++) {
            final BloomFilter f = createEmptyFilter(getTestShape());
            final int[] expected = DefaultIndexExtractorTest.generateIntArray(getTestShape().getNumberOfHashFunctions(), getTestShape().getNumberOfBits());
            final Hasher hasher = new ArrayHasher(expected);
            f.merge(hasher);
            // create sorted unique array of expected values
            assertArrayEquals(DefaultIndexExtractorTest.unique(expected), f.asIndexArray());
        }
    }

    @Test
    public void testMergeWithIndexExtractor() {
        for (int i = 0; i < 5; i++) {
            final int[] values = DefaultIndexExtractorTest.generateIntArray(getTestShape().getNumberOfHashFunctions(), getTestShape().getNumberOfBits());
            final BloomFilter f = createFilter(getTestShape(), IndexExtractor.fromIndexArray(values));
            final BitSet uniqueValues = DefaultIndexExtractorTest.uniqueSet(values);
            assertTrue(f.processIndices(idx -> {
                final boolean result = uniqueValues.get(idx);
                uniqueValues.clear(idx);
                return result;
            }));
            assertTrue(uniqueValues.isEmpty());
        }
        // value to large
        final BloomFilter f1 = createEmptyFilter(getTestShape());
        assertThrows(IllegalArgumentException.class,
                () -> f1.merge(IndexExtractor.fromIndexArray(getTestShape().getNumberOfBits())));
        // negative value
        final BloomFilter f2 = createEmptyFilter(getTestShape());
        assertThrows(IllegalArgumentException.class,
                () -> f2.merge(IndexExtractor.fromIndexArray(-1)));
    }

    @Test
    public final void testNegativeIntersection() {
        final IndexExtractor p1 = IndexExtractor.fromIndexArray(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 20, 26, 28, 30, 32, 34, 35, 36, 37, 39, 40, 41, 42, 43, 45, 46, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71);
        final IndexExtractor p2 = IndexExtractor.fromIndexArray(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27);

        final BloomFilter filter1 = createEmptyFilter(Shape.fromKM(17, 72));
        filter1.merge(p1);
        final BloomFilter filter2 = createEmptyFilter(Shape.fromKM(17, 72));
        filter2.merge(p2);
        assertEquals(0, filter1.estimateIntersection(filter2));
    }
}
