[11939] | 1 | #region License Information
|
---|
| 2 | /* HeuristicLab
|
---|
[16140] | 3 | * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
|
---|
[11939] | 4 | *
|
---|
| 5 | * This file is part of HeuristicLab.
|
---|
| 6 | *
|
---|
| 7 | * HeuristicLab is free software: you can redistribute it and/or modify
|
---|
| 8 | * it under the terms of the GNU General Public License as published by
|
---|
| 9 | * the Free Software Foundation, either version 3 of the License, or
|
---|
| 10 | * (at your option) any later version.
|
---|
| 11 | *
|
---|
| 12 | * HeuristicLab is distributed in the hope that it will be useful,
|
---|
| 13 | * but WITHOUT ANY WARRANTY; without even the implied warranty of
|
---|
| 14 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
---|
| 15 | * GNU General Public License for more details.
|
---|
| 16 | *
|
---|
| 17 | * You should have received a copy of the GNU General Public License
|
---|
| 18 | * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
|
---|
| 19 | */
|
---|
| 20 | #endregion
|
---|
| 21 |
|
---|
[11667] | 22 | using System.Collections.Generic;
|
---|
[11939] | 23 | using System.Linq;
|
---|
[11667] | 24 | using HeuristicLab.Algorithms.ParameterlessPopulationPyramid;
|
---|
[11939] | 25 | using HeuristicLab.Random;
|
---|
| 26 | using Microsoft.VisualStudio.TestTools.UnitTesting;
|
---|
[11667] | 27 |
|
---|
| 28 | namespace ParameterlessPopulationPyramid.Test {
|
---|
| 29 | [TestClass]
|
---|
| 30 | public class EnumerableBoolEqualityComparerTest {
|
---|
| 31 | private static EnumerableBoolEqualityComparer compare = new EnumerableBoolEqualityComparer();
|
---|
| 32 | MersenneTwister rand = new MersenneTwister();
|
---|
| 33 |
|
---|
| 34 | private void randFill(IList<bool> data, MersenneTwister rand) {
|
---|
| 35 | for (int i = 0; i < data.Count; i++) {
|
---|
| 36 | data[i] = rand.Next(2) == 1;
|
---|
| 37 | }
|
---|
| 38 | }
|
---|
| 39 | [TestMethod]
|
---|
[11939] | 40 | [TestProperty("Time", "short")]
|
---|
| 41 | [TestCategory("Algorithms.ParameterlessPopulationPyramid")]
|
---|
[11667] | 42 | public void EnumerableBoolEqualsTest() {
|
---|
| 43 | bool[] array = new bool[10];
|
---|
| 44 | // Referencially equal
|
---|
| 45 | randFill(array, rand);
|
---|
| 46 | Assert.IsTrue(compare.Equals(array, array));
|
---|
[11939] | 47 |
|
---|
[11667] | 48 | // Clones equal
|
---|
| 49 | var another = (bool[])array.Clone();
|
---|
| 50 | Assert.IsTrue(compare.Equals(array, another));
|
---|
[11939] | 51 |
|
---|
[11667] | 52 | // Flipping a bit makes unequal
|
---|
[11939] | 53 | int flip = rand.Next(array.Length - 1);
|
---|
[11667] | 54 | another[flip] = !another[flip];
|
---|
| 55 | Assert.IsFalse(compare.Equals(array, another));
|
---|
| 56 |
|
---|
| 57 | // Equality doesn't depend on container
|
---|
| 58 | List<bool> list = new List<bool>(array);
|
---|
| 59 | Assert.IsTrue(compare.Equals(list, array));
|
---|
| 60 | Assert.IsFalse(compare.Equals(list, another));
|
---|
| 61 | }
|
---|
| 62 |
|
---|
| 63 | [TestMethod]
|
---|
[11939] | 64 | [TestProperty("Time", "short")]
|
---|
| 65 | [TestCategory("Algorithms.ParameterlessPopulationPyramid")]
|
---|
[11667] | 66 | public void EnumerableBoolHashCollisionTest() {
|
---|
| 67 | int collisions = 0;
|
---|
| 68 |
|
---|
| 69 | bool[] array = new bool[100];
|
---|
| 70 | randFill(array, rand);
|
---|
| 71 | int original = compare.GetHashCode(array);
|
---|
[11939] | 72 |
|
---|
[11667] | 73 | bool[] another = (bool[])array.Clone();
|
---|
| 74 | // Perform random walk around string checking for hash collisions
|
---|
| 75 | for (int i = 0; i < array.Length * array.Length; i++) {
|
---|
| 76 | int flip = rand.Next(array.Length - 1);
|
---|
| 77 | another[flip] = !another[flip];
|
---|
| 78 | int hash = compare.GetHashCode(another);
|
---|
| 79 | if (hash == original) {
|
---|
| 80 | // unequal sequences with same hash value
|
---|
| 81 | if (!array.SequenceEqual(another)) collisions++;
|
---|
| 82 | } else {
|
---|
| 83 | // unequal hash should mean unequal sequence
|
---|
| 84 | Assert.IsFalse(array.SequenceEqual(another));
|
---|
| 85 | }
|
---|
| 86 | // Keep the walk from getting too far afield
|
---|
| 87 | if (i % array.Length == 0) {
|
---|
| 88 | another = (bool[])array.Clone();
|
---|
| 89 | }
|
---|
| 90 | }
|
---|
| 91 | // A very lose upper bound, this only fails if you get more than sqrt(N) collisions per attempt
|
---|
| 92 | Assert.IsTrue(collisions < array.Length);
|
---|
| 93 | }
|
---|
| 94 |
|
---|
| 95 | [TestMethod]
|
---|
[11939] | 96 | [TestProperty("Time", "short")]
|
---|
| 97 | [TestCategory("Algorithms.ParameterlessPopulationPyramid")]
|
---|
[11667] | 98 | public void EnumerableBoolHashSetTest() {
|
---|
| 99 | HashSet<bool[]> set = new HashSet<bool[]>(compare);
|
---|
| 100 | bool[] array = new bool[40];
|
---|
| 101 | randFill(array, rand);
|
---|
| 102 | set.Add(array);
|
---|
| 103 |
|
---|
| 104 | // Same object not added
|
---|
| 105 | set.Add(array);
|
---|
| 106 | Assert.AreEqual(1, set.Count);
|
---|
| 107 |
|
---|
| 108 | // Copy of object not allowed
|
---|
| 109 | var another = (bool[])array.Clone();
|
---|
| 110 | set.Add(another);
|
---|
| 111 | Assert.AreEqual(1, set.Count);
|
---|
| 112 |
|
---|
| 113 | // Flipping a bit makes unequal
|
---|
| 114 | int flip = rand.Next(array.Length - 1);
|
---|
| 115 | another[flip] = !another[flip];
|
---|
| 116 | set.Add(another);
|
---|
| 117 | Assert.AreEqual(2, set.Count);
|
---|
| 118 |
|
---|
| 119 | // Add random solutions which are 1 bit different from array to the set
|
---|
| 120 | set.Clear();
|
---|
| 121 | List<bool[]> added = new List<bool[]>();
|
---|
| 122 | for (int i = 0; i < array.Length * 10; i++) {
|
---|
| 123 | // flip a bit at random
|
---|
| 124 | another = (bool[])array.Clone();
|
---|
| 125 | flip = rand.Next(array.Length - 1);
|
---|
| 126 | another[flip] = !another[flip];
|
---|
| 127 | bool unique = set.Add(another);
|
---|
| 128 | bool actuallyUnique = true;
|
---|
| 129 | foreach (var previous in added) {
|
---|
| 130 | if (previous.SequenceEqual(another)) {
|
---|
| 131 | actuallyUnique = false;
|
---|
| 132 | }
|
---|
| 133 | }
|
---|
| 134 | Assert.AreEqual(actuallyUnique, unique);
|
---|
| 135 | if (actuallyUnique) {
|
---|
| 136 | added.Add(another);
|
---|
| 137 | }
|
---|
| 138 | }
|
---|
| 139 | }
|
---|
| 140 | }
|
---|
| 141 | }
|
---|