source: branches/Parameter-less Population Pyramid/ParameterlessPopulationPyramid.Test/EnumerableBoolEqualityComparerTest.cs @ 11667

using System;
using Microsoft.VisualStudio.TestTools.UnitTesting;
using HeuristicLab.Random;
using System.Collections.Generic;
using HeuristicLab.Algorithms.ParameterlessPopulationPyramid;
using System.Linq;

namespace ParameterlessPopulationPyramid.Test {
  [TestClass]
  public class EnumerableBoolEqualityComparerTest {
    private static EnumerableBoolEqualityComparer compare = new EnumerableBoolEqualityComparer();
    MersenneTwister rand = new MersenneTwister();

    private void randFill(IList<bool> data, MersenneTwister rand) {
      for (int i = 0; i < data.Count; i++) {
        data[i] = rand.Next(2) == 1;
      }
    }
    [TestMethod]
    public void EnumerableBoolEqualsTest() {
      bool[] array = new bool[10];
      // Referencially equal
      randFill(array, rand);
      Assert.IsTrue(compare.Equals(array, array));
      
      // Clones equal
      var another = (bool[])array.Clone();
      Assert.IsTrue(compare.Equals(array, another));
      
      // Flipping a bit makes unequal
      int flip = rand.Next(array.Length-1);
      another[flip] = !another[flip];
      Assert.IsFalse(compare.Equals(array, another));

      // Equality doesn't depend on container
      List<bool> list = new List<bool>(array);
      Assert.IsTrue(compare.Equals(list, array));
      Assert.IsFalse(compare.Equals(list, another));
    }

    [TestMethod]
    public void EnumerableBoolHashCollisionTest() {
      int collisions = 0;

      bool[] array = new bool[100];
      randFill(array, rand);
      int original = compare.GetHashCode(array);
      
      bool[] another = (bool[])array.Clone();
      // Perform random walk around string checking for hash collisions
      for (int i = 0; i < array.Length * array.Length; i++) {
        int flip = rand.Next(array.Length - 1);
        another[flip] = !another[flip];
        int hash = compare.GetHashCode(another);
        if (hash == original) {
          // unequal sequences with same hash value
          if (!array.SequenceEqual(another)) collisions++;
        } else {
          // unequal hash should mean unequal sequence
          Assert.IsFalse(array.SequenceEqual(another));
        }
        // Keep the walk from getting too far afield
        if (i % array.Length == 0) {
          another = (bool[])array.Clone();
        }
      }
      // A very lose upper bound, this only fails if you get more than sqrt(N) collisions per attempt 
      Assert.IsTrue(collisions < array.Length);
    }

    [TestMethod]
    public void EnumerableBoolHashSetTest() {
      HashSet<bool[]> set = new HashSet<bool[]>(compare);
      bool[] array = new bool[40];
      randFill(array, rand);
      set.Add(array);

      // Same object not added
      set.Add(array);
      Assert.AreEqual(1, set.Count);

      // Copy of object not allowed
      var another = (bool[])array.Clone();
      set.Add(another);
      Assert.AreEqual(1, set.Count);

      // Flipping a bit makes unequal
      int flip = rand.Next(array.Length - 1);
      another[flip] = !another[flip];
      set.Add(another);
      Assert.AreEqual(2, set.Count);

      // Add random solutions which are 1 bit different from array to the set
      set.Clear();
      List<bool[]> added = new List<bool[]>();
      for (int i = 0; i < array.Length * 10; i++) {
        // flip a bit at random
        another = (bool[])array.Clone();
        flip = rand.Next(array.Length - 1);
        another[flip] = !another[flip];
        bool unique = set.Add(another);
        bool actuallyUnique = true;
        foreach (var previous in added) {
          if (previous.SequenceEqual(another)) {
            actuallyUnique = false;
          }
        }
        Assert.AreEqual(actuallyUnique, unique);
        if (actuallyUnique) {
          added.Add(another);
        }
      }
    }
  }
}