content: /*
  * 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 com.clearspring.analytics.stream.membership;
  
  import java.io.IOException;
  
  import java.util.HashSet;
  import java.util.Iterator;
  import java.util.Set;
  
  import org.junit.Test;
  
  import static org.junit.Assert.assertEquals;
  import static org.junit.Assert.assertFalse;
  import static org.junit.Assert.assertTrue;
  
  public class FilterTest {
  
      public void testManyHashes(Iterator<String> keys) {
          int MAX_HASH_COUNT = 128;
          Set<Integer> hashes = new HashSet<Integer>();
          int collisions = 0;
          while (keys.hasNext()) {
              hashes.clear();
              for (int hashIndex : Filter.getHashBuckets(keys.next(), MAX_HASH_COUNT, 1024 * 1024)) {
                  hashes.add(hashIndex);
              }
              collisions += (MAX_HASH_COUNT - hashes.size());
          }
          assertTrue("Collisions: " + collisions, collisions <= 100);
      }
  
      @Test
      public void testManyRandom() {
          testManyHashes(randomKeys());
      }
  
      // used by filter subclass tests
  
      static final double MAX_FAILURE_RATE = 0.1;
      public static final BloomCalculations.BloomSpecification spec = BloomCalculations.computeBucketsAndK(MAX_FAILURE_RATE);
      static final int ELEMENTS = 10000;
  
      static final ResetableIterator<String> intKeys() {
          return new KeyGenerator.IntGenerator(ELEMENTS);
      }
  
      static final ResetableIterator<String> randomKeys() {
          return new KeyGenerator.RandomStringGenerator(314159, ELEMENTS);
      }
  
      static final ResetableIterator<String> randomKeys2() {
          return new KeyGenerator.RandomStringGenerator(271828, ELEMENTS);
      }
  
      public static void testFalsePositives(Filter f, ResetableIterator<String> keys, ResetableIterator<String> otherkeys) {
          assertEquals(keys.size(), otherkeys.size());
  
          while (keys.hasNext()) {
              f.add(keys.next());
          }
  
          int fp = 0;
          while (otherkeys.hasNext()) {
              if (f.isPresent(otherkeys.next())) {
                  fp++;
              }
          }
  
          double fp_ratio = fp / (keys.size() * BloomCalculations.probs[spec.bucketsPerElement][spec.K]);
          assertTrue("FP ratio: " + fp_ratio, fp_ratio < 1.03);
      }
  
      public static Filter testSerialize(Filter f) throws IOException {
          f.add("a");
          DataOutputBuffer out = new DataOutputBuffer();
          f.getSerializer().serialize(f, out);
  
          DataInputBuffer in = new DataInputBuffer();
          in.reset(out.getData(), out.getLength());
          Filter f2 = f.getSerializer().deserialize(in);
  
          assertTrue(f2.isPresent("a"));
          assertFalse(f2.isPresent("b"));
          return f2;
      }
  
  }
  