context: using System;
  using System.Collections;
  using System.Collections.Generic;
  using System.Linq;
  using System.Security.Cryptography;
  using System.Text;
  
  namespace Java2Dotnet.Spider.Common
  {
  	public class BloomFilter
  	{
  		private readonly BitArray _bitset;
  		private readonly int _bitSetSize;
  		private readonly double _bitsPerElement;
  		private readonly int _expectedNumberOfFilterElements; // expected (maximum) number of elements to be added
  		private int _numberOfAddedElements; // number of elements actually added to the Bloom filter
  		private readonly int _k; // number of hash functions
  
  		static readonly Encoding Charset = Encoding.UTF8; // encoding used for storing hash values as strings
  
  		/// <summary>
  		/// The digest method is reused between instances
  		/// </summary>
  		/// <remarks>MD5 gives good enough accuracy in most circumstances. Change to SHA1 if it's needed</remarks>
  		static readonly KeyedHashAlgorithm DigestFunction = new HMACSHA1();
  
  		/// <summary>
  		/// Constructs an empty Bloom filter. The total length of the Bloom filter will be
  		/// c*n.
  		/// </summary>
  		/// <param name="c">is the number of bits used per element.</param>
  		/// <param name="n">is the expected number of elements the filter will contain.</param>
  		/// <param name="k">is the number of hash functions used.</param>
  		public BloomFilter(double c, int n, int k)
  		{
  			_expectedNumberOfFilterElements = n;
  			_k = k;
  			_bitsPerElement = c;
  			_bitSetSize = (int)Math.Ceiling(c * n);
  			_numberOfAddedElements = 0;
  			_bitset = new BitArray(_bitSetSize);
  		}
  
  		/// <summary>
  		/// Constructs an empty Bloom filter. The optimal number of hash functions (k) is estimated from the total size of the Bloom
  		/// and the number of expected elements.
  		/// </summary>
  		/// <param name="bitSetSize">defines how many bits should be used in total for the filter.</param>
  		/// <param name="expectedNumberOElements">defines the maximum number of elements the filter is expected to contain.</param>
  		public BloomFilter(int bitSetSize, int expectedNumberOElements)
  			: this(
  				bitSetSize / (double)expectedNumberOElements,
  				expectedNumberOElements,
  				(int)Math.Round((bitSetSize / (double)expectedNumberOElements) * Math.Log(2.0))
  			  )
  		{ }
  
  		/// <summary>
  		/// Constructs an empty Bloom filter with a given false positive probability. The number of bits per
  		/// element and the number of hash functions is estimated
  		/// to match the false positive probability.
  		/// </summary>
  		/// <param name="falsePositiveProbability">is the desired false positive probability.</param>
  		/// <param name="expectedNumberOfElements">is the expected number of elements in the Bloom filter.</param>
  		public BloomFilter(double falsePositiveProbability, int expectedNumberOfElements)
  			: this(
  				Math.Ceiling(-(Math.Log(falsePositiveProbability) / Math.Log(2))) / Math.Log(2), // c = k / ln(2)
  				expectedNumberOfElements,
  				(int)Math.Ceiling(-(Math.Log(falsePositiveProbability) / Math.Log(2))) // k = ceil(-log_2(false prob.))
  			  )
  		{ }
  
  		/// <summary>
  		/// Construct a new Bloom filter based on existing Bloom filter data.
  		/// </summary>
  		/// <param name="bitSetSize">defines how many bits should be used for the filter.</param>
  		/// <param name="expectedNumberOfFilterElements">defines the maximum number of elements the filter is expected to contain.</param>
  		/// <param name="actualNumberOfFilterElements">specifies how many elements have been inserted into the <code>filterData</code> BitArray.</param>
  		/// <param name="filterData">a BitArray representing an existing Bloom filter.</param>
  		public BloomFilter(int bitSetSize, int expectedNumberOfFilterElements, int actualNumberOfFilterElements, BitArray filterData)
  			: this(bitSetSize, expectedNumberOfFilterElements)
  		{
  			_bitset = filterData;
  			_numberOfAddedElements = actualNumberOfFilterElements;
  		}
  
  		/// <summary>
  		/// Generates a digest based on the contents of a string.
  		/// </summary>
  		/// <param name="val">specifies the input data.</param>
  		/// <param name="charset">specifies the encoding of the input data.</param>
  		/// <returns>digest as long.</returns>
  		public static int CreateHash(string val, Encoding charset)
  		{
  			return CreateHash(charset.GetBytes(val));
  		}
  
  		/// <summary>
  		/// Generates a digest based on the contents of a string.
  		/// </summary>
  		/// <param name="val">specifies the input data. The encoding is expected to be UTF-8.</param>
  		/// <returns>digest as long.</returns>
  		public static int CreateHash(string val)
  		{
  			return CreateHash(val, Charset);
  		}
  
  		/// <summary>
  		/// Generates a digest based on the contents of an array of bytes.
  		/// </summary>
  		/// <param name="data">specifies input data.</param>
  		/// <returns>digest as long.</returns>
  		public static int CreateHash(byte[] data)
  		{
  			return CreateHashes(data, 1)[0];
  		}
  
  		/// <summary>
  		/// Generates digests based on the contents of an array of bytes and splits the result into 4-byte int's and store them in an array. The
  		/// digest function is called until the required number of int's are produced. For each call to digest a salt
  		/// is prepended to the data. The salt is increased by 1 for each call.
  		/// </summary>
  		/// <param name="data">specifies input data</param>
  		/// <param name="hashes">number of hashes/int's to produce</param>
  		/// <returns>array of int-sized hashes</returns>
  		public static int[] CreateHashes(byte[] data, int hashes)
  		{
  			int[] result = new int[hashes];
  
  			int k = 0;
  			byte[] salt = new byte[1];
  			while (k < hashes)
  			{
  				byte[] digest;
  				lock (DigestFunction)
  				{
  					DigestFunction.Key = salt;
  					salt[0]++;
  					digest = DigestFunction.ComputeHash(data);
  				}
  
  				for (int i = 0; i < digest.Length / 4 && k < hashes; i++)
  				{
  					int h = 0;
  					for (int j = (i * 4); j < (i * 4) + 4; j++)
  					{
  						h <<= 8;
  						h |= digest[j] & 0xFF;
  					}
  					result[k] = h;
  					k++;
  				}
  			}
  			return result;
  		}
  
  		/// <summary>
  		/// Compares the contents of two instances to see if they are equal.
  		/// </summary>
  		/// <param name="obj">is the object to compare to.</param>
  		/// <returns>True if the contents of the objects are equal.</returns>
  		public override bool Equals(object obj)
  		{
  			if (obj == null)
  			{
  				return false;
  			}
  			if (GetType() != obj.GetType())
  			{
  				return false;
  			}
  			BloomFilter other = (BloomFilter)obj;
  			if (_expectedNumberOfFilterElements != other._expectedNumberOfFilterElements)
  			{
  				return false;
  			}
  			if (_k != other._k)
  			{
  				return false;
  			}
  			if (_bitSetSize != other._bitSetSize)
  			{
  				return false;
  			}
  			if (_bitset != other._bitset && (_bitset == null || !ObjectUtils.Equals(_bitset, other._bitset)))
  			{
  				return false;
  			}
  			return true;
  		}
  
  		/// <summary>
  		/// Calculates a hash code for this class.
  		/// <remarks>performance concerns : note that we read all the bits of bitset to compute the hash</remarks>
  		/// <returns>hash code representing the contents of an instance of this class.</returns>
  		/// </summary>
  		public override int GetHashCode()
  		{
  			int hash = 7;
  			hash = 61 * hash + (_bitset != null ? ObjectUtils.HashBytes(_bitset) : 0);
  			hash = 61 * hash + _expectedNumberOfFilterElements;
  			hash = 61 * hash + _bitSetSize;
  			hash = 61 * hash + _k;
  			return hash;
  		}
  
  
  		/// <summary>
  		/// Calculates the expected probability of false positives based on
  		/// the number of expected filter elements and the size of the Bloom filter.
  		/// <br /><br />
  		/// The value returned by this method is the <i>expected</i> rate of false
  		/// positives, assuming the number of inserted elements equals the number of
  		/// expected elements. If the number of elements in the Bloom filter is less
  		/// than the expected value, the true probability of false positives will be lower.
  		/// </summary>
  		/// <returns>expected probability of false positives.</returns>
  		public double ExpectedFalsePositiveProbability()
  		{
  			return GetFalsePositiveProbability(_expectedNumberOfFilterElements);
  		}
  
  		/// <summary>
  		/// Calculate the probability of a false positive given the specified
  		/// number of inserted elements.
  		/// </summary>
  		/// <param name="numberOfElements">number of inserted elements.</param>
  		/// <returns>probability of a false positive.</returns>
  		public double GetFalsePositiveProbability(double numberOfElements)
  		{
  			// (1 - e^(-k * n / m)) ^ k
  
gt: 			return Math.Pow((1 - Math.Exp(-_k * numberOfElements