You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucenenet.apache.org by mh...@apache.org on 2013/09/24 20:32:47 UTC
[11/50] [abbrv] git commit: Port: unit tests. more from util namespace
Port: unit tests. more from util namespace
Project: http://git-wip-us.apache.org/repos/asf/lucenenet/repo
Commit: http://git-wip-us.apache.org/repos/asf/lucenenet/commit/14f5ae0c
Tree: http://git-wip-us.apache.org/repos/asf/lucenenet/tree/14f5ae0c
Diff: http://git-wip-us.apache.org/repos/asf/lucenenet/diff/14f5ae0c
Branch: refs/heads/branch_4x
Commit: 14f5ae0cf2d381cca82e7fb8d47a47524f9b16d9
Parents: d9635bf
Author: James Blair <jm...@gmail.com>
Authored: Tue Jul 16 17:32:28 2013 -0400
Committer: James Blair <jm...@gmail.com>
Committed: Tue Jul 16 17:32:28 2013 -0400
----------------------------------------------------------------------
test/core/Util/Automaton/TestBasicOperations.cs | 160 ++++++++
.../Util/Automaton/TestCompiledAutomaton.cs | 127 ++++++
test/core/Util/Automaton/TestDeterminism.cs | 69 ++++
.../Util/Automaton/TestDeterminizeLexicon.cs | 51 +++
.../Util/Automaton/TestLevenshteinAutomata.cs | 394 +++++++++++++++++++
test/core/Util/Automaton/TestMinimize.cs | 51 +++
.../Util/Automaton/TestSpecialOperations.cs | 38 ++
test/core/Util/Automaton/TestUTF32ToUTF8.cs | 271 +++++++++++++
test/core/Util/TestWeakIdentityMap.cs | 276 +++++++++++++
9 files changed, 1437 insertions(+)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/lucenenet/blob/14f5ae0c/test/core/Util/Automaton/TestBasicOperations.cs
----------------------------------------------------------------------
diff --git a/test/core/Util/Automaton/TestBasicOperations.cs b/test/core/Util/Automaton/TestBasicOperations.cs
new file mode 100644
index 0000000..8db8744
--- /dev/null
+++ b/test/core/Util/Automaton/TestBasicOperations.cs
@@ -0,0 +1,160 @@
+using System;
+using System.Collections.Generic;
+using System.Linq;
+using Lucene.Net.Support;
+using Lucene.Net.Util;
+using Lucene.Net.Util.Automaton;
+using NUnit.Framework;
+
+namespace Lucene.Net.Test.Util.Automaton
+{
+ [TestFixture]
+ public class TestBasicOperations : LuceneTestCase
+ {
+ [Test]
+ public void TestStringUnion()
+ {
+ var strings = new List<BytesRef>();
+ for (int i = RandomInts.randomIntBetween(new Random(), 0, 1000); --i >= 0; )
+ {
+ strings.Add(new BytesRef(_TestUtil.RandomUnicodeString(new Random())));
+ }
+
+ strings.Sort();
+ //Collections.Sort(strings);
+ var union = BasicAutomata.MakeStringUnion(strings);
+ Assert.IsTrue(union.Deterministic);
+ Assert.IsTrue(BasicOperations.SameLanguage(union, NaiveUnion(strings)));
+ }
+
+ private static Lucene.Net.Util.Automaton.Automaton NaiveUnion(List<BytesRef> strings)
+ {
+ var eachIndividual = new Lucene.Net.Util.Automaton.Automaton[strings.Count];
+ int i = 0;
+ foreach (var bref in strings)
+ {
+ eachIndividual[i++] = BasicAutomata.MakeString(bref.Utf8ToString());
+ }
+ return BasicOperations.Union(eachIndividual.ToList());
+ }
+
+ /** Test optimization to Concatenate() */
+ [Test]
+ public void TestSingletonConcatenate()
+ {
+ var singleton = BasicAutomata.MakeString("prefix");
+ var expandedSingleton = singleton.CloneExpanded();
+ var other = BasicAutomata.MakeCharRange('5', '7');
+ var concat = BasicOperations.Concatenate(singleton, other);
+ Assert.IsTrue(concat.Deterministic);
+ Assert.IsTrue(BasicOperations.SameLanguage(BasicOperations.Concatenate(expandedSingleton, other), concat));
+ }
+
+ /** Test optimization to Concatenate() to an NFA */
+ [Test]
+ public void TestSingletonNFAConcatenate()
+ {
+ var singleton = BasicAutomata.MakeString("prefix");
+ var expandedSingleton = singleton.CloneExpanded();
+ // an NFA (two transitions for 't' from initial state)
+ var nfa = BasicOperations.Union(BasicAutomata.MakeString("this"),
+ BasicAutomata.MakeString("three"));
+ var concat = BasicOperations.Concatenate(singleton, nfa);
+ Assert.IsFalse(concat.Deterministic);
+ Assert.IsTrue(BasicOperations.SameLanguage(BasicOperations.Concatenate(expandedSingleton, nfa), concat));
+ }
+
+ /** Test optimization to Concatenate() with empty String */
+ [Test]
+ public void TestEmptySingletonConcatenate()
+ {
+ var singleton = BasicAutomata.MakeString("");
+ var expandedSingleton = singleton.CloneExpanded();
+ var other = BasicAutomata.MakeCharRange('5', '7');
+ var concat1 = BasicOperations.Concatenate(expandedSingleton, other);
+ var concat2 = BasicOperations.Concatenate(singleton, other);
+ Assert.IsTrue(concat2.Deterministic);
+ Assert.IsTrue(BasicOperations.SameLanguage(concat1, concat2));
+ Assert.IsTrue(BasicOperations.SameLanguage(other, concat1));
+ Assert.IsTrue(BasicOperations.SameLanguage(other, concat2));
+ }
+
+ /** Test concatenation with empty language returns empty */
+ [Test]
+ public void TestEmptyLanguageConcatenate()
+ {
+ var a = BasicAutomata.MakeString("a");
+ var concat = BasicOperations.Concatenate(a, BasicAutomata.MakeEmpty());
+ Assert.IsTrue(BasicOperations.IsEmpty(concat));
+ }
+
+ /** Test optimization to Concatenate() with empty String to an NFA */
+ [Test]
+ public void TestEmptySingletonNFAConcatenate()
+ {
+ var singleton = BasicAutomata.MakeString("");
+ var expandedSingleton = singleton.CloneExpanded();
+ // an NFA (two transitions for 't' from initial state)
+ var nfa = BasicOperations.Union(BasicAutomata.MakeString("this"),
+ BasicAutomata.MakeString("three"));
+ var concat1 = BasicOperations.Concatenate(expandedSingleton, nfa);
+ var concat2 = BasicOperations.Concatenate(singleton, nfa);
+ Assert.IsFalse(concat2.Deterministic);
+ Assert.IsTrue(BasicOperations.SameLanguage(concat1, concat2));
+ Assert.IsTrue(BasicOperations.SameLanguage(nfa, concat1));
+ Assert.IsTrue(BasicOperations.SameLanguage(nfa, concat2));
+ }
+
+ /** Test singletons work correctly */
+ [Test]
+ public void TestSingleton()
+ {
+ var singleton = BasicAutomata.MakeString("foobar");
+ var expandedSingleton = singleton.CloneExpanded();
+ Assert.IsTrue(BasicOperations.SameLanguage(singleton, expandedSingleton));
+
+ singleton = BasicAutomata.MakeString("\ud801\udc1c");
+ expandedSingleton = singleton.CloneExpanded();
+ Assert.IsTrue(BasicOperations.SameLanguage(singleton, expandedSingleton));
+ }
+
+ [Test]
+ public void TestGetRandomAcceptedString()
+ {
+ int ITER1 = AtLeast(100);
+ int ITER2 = AtLeast(100);
+ for (var i = 0; i < ITER1; i++)
+ {
+
+ var re = new RegExp(AutomatonTestUtil.randomRegexp(new Random()), RegExp.NONE);
+ var a = re.ToAutomaton();
+ Assert.IsFalse(BasicOperations.IsEmpty(a));
+
+ AutomatonTestUtil.RandomAcceptedStrings rx = new AutomatonTestUtil.RandomAcceptedStrings(a);
+ for (var j = 0; j < ITER2; j++)
+ {
+ int[] acc = null;
+ try
+ {
+ acc = rx.GetRandomAcceptedString(new Random());
+ String s = UnicodeUtil.NewString(acc, 0, acc.Length);
+ Assert.IsTrue(BasicOperations.Run(a, s));
+ }
+ catch (Exception e)
+ {
+ Console.WriteLine("regexp: " + re);
+ if (acc != null)
+ {
+ Console.WriteLine("fail acc re=" + re + " count=" + acc.Length);
+ for (int k = 0; k < acc.Length; k++)
+ {
+ Console.WriteLine(" " + Integer.ToHexString(acc[k]));
+ }
+ }
+ throw;
+ }
+ }
+ }
+ }
+ }
+}
http://git-wip-us.apache.org/repos/asf/lucenenet/blob/14f5ae0c/test/core/Util/Automaton/TestCompiledAutomaton.cs
----------------------------------------------------------------------
diff --git a/test/core/Util/Automaton/TestCompiledAutomaton.cs b/test/core/Util/Automaton/TestCompiledAutomaton.cs
new file mode 100644
index 0000000..b2ea288
--- /dev/null
+++ b/test/core/Util/Automaton/TestCompiledAutomaton.cs
@@ -0,0 +1,127 @@
+using System;
+using System.Collections.Generic;
+using System.Linq;
+using Lucene.Net.Support;
+using Lucene.Net.Util;
+using Lucene.Net.Util.Automaton;
+using NUnit.Framework;
+
+namespace Lucene.Net.Test.Util.Automaton
+{
+ [TestFixture]
+ public class TestCompiledAutomaton : LuceneTestCase
+ {
+ private CompiledAutomaton Build(params string[] strings)
+ {
+ var terms = strings.Select(s => new BytesRef(s)).ToList();
+ terms.Sort();
+ //Collections.sort(terms);
+ var a = DaciukMihovAutomatonBuilder.Build(terms);
+ return new CompiledAutomaton(a, true, false);
+ }
+
+ private void TestFloor(CompiledAutomaton c, string input, string expected)
+ {
+ var b = new BytesRef(input);
+ var result = c.Floor(b, b);
+ if (expected == null)
+ {
+ assertNull(result);
+ }
+ else
+ {
+ assertNotNull(result);
+ assertEquals("actual=" + result.Utf8ToString() + " vs expected=" + expected + " (input=" + input + ")",
+ result, new BytesRef(expected));
+ }
+ }
+
+ private void TestTerms(string[] terms)
+ {
+ var c = Build(terms);
+ var termBytes = new BytesRef[terms.Length];
+ for (var idx = 0; idx < terms.Length; idx++)
+ {
+ termBytes[idx] = new BytesRef(terms[idx]);
+ }
+ termBytes.ToList().Sort();
+ //Arrays.sort(termBytes);
+
+ if (VERBOSE)
+ {
+ Console.WriteLine("\nTEST: terms in unicode order");
+ foreach (var t in termBytes)
+ {
+ Console.WriteLine(" " + t.Utf8ToString());
+ }
+ //System.out.println(c.utf8.toDot());
+ }
+
+ for (var iter = 0; iter < 100 * RANDOM_MULTIPLIER; iter++)
+ {
+ var s = new Random().Next(10) == 1 ? terms[new Random().Next(terms.Length)] : RandomString();
+ if (VERBOSE)
+ {
+ Console.WriteLine("\nTEST: floor(" + s + ")");
+ }
+ int loc = Arrays.BinarySearch(termBytes, new BytesRef(s));
+ string expected;
+ if (loc >= 0)
+ {
+ expected = s;
+ }
+ else
+ {
+ // term doesn't exist
+ loc = -(loc + 1);
+ if (loc == 0)
+ {
+ expected = null;
+ }
+ else
+ {
+ expected = termBytes[loc - 1].Utf8ToString();
+ }
+ }
+ if (VERBOSE)
+ {
+ Console.WriteLine(" expected=" + expected);
+ }
+ TestFloor(c, s, expected);
+ }
+ }
+
+ [Test]
+ public void TestRandom()
+ {
+ int numTerms = AtLeast(400);
+ var terms = new HashSet<string>();
+ while (terms.Count != numTerms)
+ {
+ terms.Add(RandomString());
+ }
+ TestTerms(terms.ToArray());
+ }
+
+ private string RandomString()
+ {
+ // return _TestUtil.randomSimpleString(random);
+ return _TestUtil.RandomRealisticUnicodeString(new Random());
+ }
+
+ [Test]
+ public void TestBasic()
+ {
+ var c = Build("fob", "foo", "goo");
+ TestFloor(c, "goo", "goo");
+ TestFloor(c, "ga", "foo");
+ TestFloor(c, "g", "foo");
+ TestFloor(c, "foc", "fob");
+ TestFloor(c, "foz", "foo");
+ TestFloor(c, "f", null);
+ TestFloor(c, "", null);
+ TestFloor(c, "aa", null);
+ TestFloor(c, "zzz", "goo");
+ }
+ }
+}
http://git-wip-us.apache.org/repos/asf/lucenenet/blob/14f5ae0c/test/core/Util/Automaton/TestDeterminism.cs
----------------------------------------------------------------------
diff --git a/test/core/Util/Automaton/TestDeterminism.cs b/test/core/Util/Automaton/TestDeterminism.cs
new file mode 100644
index 0000000..9106b6c
--- /dev/null
+++ b/test/core/Util/Automaton/TestDeterminism.cs
@@ -0,0 +1,69 @@
+using System;
+using Lucene.Net.Util;
+using Lucene.Net.Util.Automaton;
+using NUnit.Framework;
+
+namespace Lucene.Net.Test.Util.Automaton
+{
+ [TestFixture]
+ public class TestDeterminism : LuceneTestCase
+ {
+ /** Test a bunch of random regular expressions */
+ [Test]
+ public void TestRegexps()
+ {
+ int num = AtLeast(500);
+ for (var i = 0; i < num; i++)
+ AssertAutomaton(new RegExp(AutomatonTestUtil.RandomRegexp(new Random()), RegExp.NONE).ToAutomaton());
+ }
+
+ /** Test against a simple, unoptimized det */
+ [Test]
+ public void TestAgainstSimple()
+ {
+ int num = AtLeast(200);
+ for (var i = 0; i < num; i++)
+ {
+ var a = AutomatonTestUtil.RandomAutomaton(new Random());
+ var b = a.Clone();
+ AutomatonTestUtil.DeterminizeSimple(a);
+ b.Deterministic = false; // force det
+ b.Determinize();
+ // TODO: more verifications possible?
+ Assert.IsTrue(BasicOperations.SameLanguage(a, b));
+ }
+ }
+
+ private static void AssertAutomaton(Lucene.Net.Util.Automaton.Automaton a)
+ {
+ var clone = a.Clone();
+ // complement(complement(a)) = a
+ var equivalent = BasicOperations.Complement(BasicOperations.Complement(a));
+ Assert.IsTrue(BasicOperations.SameLanguage(a, equivalent));
+
+ // a union a = a
+ equivalent = BasicOperations.Union(a, clone);
+ Assert.IsTrue(BasicOperations.SameLanguage(a, equivalent));
+
+ // a intersect a = a
+ equivalent = BasicOperations.Intersection(a, clone);
+ Assert.IsTrue(BasicOperations.SameLanguage(a, equivalent));
+
+ // a minus a = empty
+ var empty = BasicOperations.Minus(a, clone);
+ Assert.IsTrue(BasicOperations.IsEmpty(empty));
+
+ // as long as don't accept the empty string
+ // then optional(a) - empty = a
+ if (!BasicOperations.Run(a, ""))
+ {
+ //System.out.println("Test " + a);
+ var optional = BasicOperations.Optional(a);
+ //System.out.println("optional " + optional);
+ equivalent = BasicOperations.Minus(optional, BasicAutomata.MakeEmptyString());
+ //System.out.println("equiv " + equivalent);
+ Assert.IsTrue(BasicOperations.SameLanguage(a, equivalent));
+ }
+ }
+ }
+}
http://git-wip-us.apache.org/repos/asf/lucenenet/blob/14f5ae0c/test/core/Util/Automaton/TestDeterminizeLexicon.cs
----------------------------------------------------------------------
diff --git a/test/core/Util/Automaton/TestDeterminizeLexicon.cs b/test/core/Util/Automaton/TestDeterminizeLexicon.cs
new file mode 100644
index 0000000..a8c11af
--- /dev/null
+++ b/test/core/Util/Automaton/TestDeterminizeLexicon.cs
@@ -0,0 +1,51 @@
+using System;
+using System.Collections.Generic;
+using Lucene.Net.Support;
+using Lucene.Net.Util;
+using Lucene.Net.Util.Automaton;
+using NUnit.Framework;
+
+namespace Lucene.Net.Test.Util.Automaton
+{
+ [TestFixture]
+ public class TestDeterminizeLexicon : LuceneTestCase
+ {
+ private List<Lucene.Net.Util.Automaton.Automaton> automata = new List<Lucene.Net.Util.Automaton.Automaton>();
+ private List<string> terms = new List<string>();
+
+ public void testLexicon()
+ {
+ int num = AtLeast(1);
+ for (var i = 0; i < num; i++)
+ {
+ automata.Clear();
+ terms.Clear();
+ for (var j = 0; j < 5000; j++)
+ {
+ string randomString = _TestUtil.RandomUnicodeString(new Random());
+ terms.Add(randomString);
+ automata.Add(BasicAutomata.MakeString(randomString));
+ }
+ assertLexicon();
+ }
+ }
+
+ public void assertLexicon()
+ {
+ Collections.Shuffle(automata, new Random());
+ var lex = BasicOperations.Union(automata);
+ lex.Determinize();
+ assertTrue(SpecialOperations.IsFinite(lex));
+ foreach (var s in terms)
+ {
+ assertTrue(BasicOperations.Run(lex, s));
+ }
+ var lexByte = new ByteRunAutomaton(lex);
+ foreach (var s in terms)
+ {
+ var bytes = s.GetBytes("UTF-8");
+ assertTrue(lexByte.Run(bytes, 0, bytes.Length));
+ }
+ }
+ }
+}
http://git-wip-us.apache.org/repos/asf/lucenenet/blob/14f5ae0c/test/core/Util/Automaton/TestLevenshteinAutomata.cs
----------------------------------------------------------------------
diff --git a/test/core/Util/Automaton/TestLevenshteinAutomata.cs b/test/core/Util/Automaton/TestLevenshteinAutomata.cs
new file mode 100644
index 0000000..b325325
--- /dev/null
+++ b/test/core/Util/Automaton/TestLevenshteinAutomata.cs
@@ -0,0 +1,394 @@
+using System;
+using System.Collections.Generic;
+using System.Text;
+using Lucene.Net.Util;
+using Lucene.Net.Util.Automaton;
+using NUnit.Framework;
+
+namespace Lucene.Net.Test.Util.Automaton
+{
+ [TestFixture]
+ public class TestLevenshteinAutomata : LuceneTestCase
+ {
+ [Test]
+ public void TestLev0()
+ {
+ AssertLev("", 0);
+ AssertCharVectors(0);
+ }
+
+ [Test]
+ public void TestLev1()
+ {
+ AssertLev("", 1);
+ AssertCharVectors(1);
+ }
+
+ [Test]
+ public void TestLev2()
+ {
+ AssertLev("", 2);
+ AssertCharVectors(2);
+ }
+
+ // LUCENE-3094
+ [Test]
+ public void TestNoWastedStates()
+ {
+ AutomatonTestUtil.assertNoDetachedStates(new LevenshteinAutomata("abc", false).ToAutomaton(1));
+ }
+
+ /**
+ * Tests all possible characteristic vectors for some n
+ * This exhaustively tests the parametric transitions tables.
+ */
+ private void AssertCharVectors(int n)
+ {
+ var k = 2 * n + 1;
+ // use k + 2 as the exponent: the formula generates different transitions
+ // for w, w-1, w-2
+ var limit = (int)Math.Pow(2, k + 2);
+ for (var i = 0; i < limit; i++)
+ {
+ String encoded = Integer.toString(i, 2);
+ AssertLev(encoded, n);
+ }
+ }
+
+ /**
+ * Builds a DFA for some string, and checks all Lev automata
+ * up to some maximum distance.
+ */
+ private void AssertLev(String s, int maxDistance)
+ {
+ var builder = new LevenshteinAutomata(s, false);
+ var tbuilder = new LevenshteinAutomata(s, true);
+ var automata = new Lucene.Net.Util.Automaton.Automaton[maxDistance + 1];
+ var tautomata = new Lucene.Net.Util.Automaton.Automaton[maxDistance + 1];
+ for (var n = 0; n < automata.Length; n++)
+ {
+ automata[n] = builder.ToAutomaton(n);
+ tautomata[n] = tbuilder.ToAutomaton(n);
+ Assert.IsNotNull(automata[n]);
+ Assert.IsNotNull(tautomata[n]);
+ Assert.IsTrue(automata[n].Deterministic);
+ Assert.IsTrue(tautomata[n].Deterministic);
+ Assert.IsTrue(SpecialOperations.IsFinite(automata[n]));
+ Assert.IsTrue(SpecialOperations.IsFinite(tautomata[n]));
+ AutomatonTestUtil.assertNoDetachedStates(automata[n]);
+ AutomatonTestUtil.assertNoDetachedStates(tautomata[n]);
+ // check that the dfa for n-1 accepts a subset of the dfa for n
+ if (n > 0)
+ {
+ Assert.IsTrue(automata[n - 1].SubsetOf(automata[n]));
+ Assert.IsTrue(automata[n - 1].SubsetOf(tautomata[n]));
+ Assert.IsTrue(tautomata[n - 1].SubsetOf(automata[n]));
+ Assert.IsTrue(tautomata[n - 1].SubsetOf(tautomata[n]));
+ Assert.AreNotSame(automata[n - 1], automata[n]);
+ }
+ // check that Lev(N) is a subset of LevT(N)
+ Assert.IsTrue(automata[n].SubsetOf(tautomata[n]));
+ // special checks for specific n
+ switch (n)
+ {
+ case 0:
+ // easy, matches the string itself
+ Assert.IsTrue(BasicOperations.SameLanguage(BasicAutomata.MakeString(s), automata[0]));
+ Assert.IsTrue(BasicOperations.SameLanguage(BasicAutomata.MakeString(s), tautomata[0]));
+ break;
+ case 1:
+ // generate a lev1 naively, and check the accepted lang is the same.
+ Assert.IsTrue(BasicOperations.SameLanguage(NaiveLev1(s), automata[1]));
+ Assert.IsTrue(BasicOperations.SameLanguage(NaiveLev1T(s), tautomata[1]));
+ break;
+ default:
+ AssertBruteForce(s, automata[n], n);
+ AssertBruteForceT(s, tautomata[n], n);
+ break;
+ }
+ }
+ }
+
+ private Lucene.Net.Util.Automaton.Automaton NaiveLev1(String s)
+ {
+ var a = BasicAutomata.MakeString(s);
+ a = BasicOperations.Union(a, InsertionsOf(s));
+ MinimizationOperations.Minimize(a);
+ a = BasicOperations.Union(a, DeletionsOf(s));
+ MinimizationOperations.Minimize(a);
+ a = BasicOperations.Union(a, SubstitutionsOf(s));
+ MinimizationOperations.Minimize(a);
+
+ return a;
+ }
+
+ private Lucene.Net.Util.Automaton.Automaton NaiveLev1T(String s)
+ {
+ var a = NaiveLev1(s);
+ a = BasicOperations.Union(a, TranspositionsOf(s));
+ MinimizationOperations.Minimize(a);
+ return a;
+ }
+
+ private Lucene.Net.Util.Automaton.Automaton InsertionsOf(String s)
+ {
+ var list = new List<Lucene.Net.Util.Automaton.Automaton>();
+
+ for (var i = 0; i <= s.Length; i++)
+ {
+ var a = BasicAutomata.MakeString(s.Substring(0, i));
+ a = BasicOperations.Concatenate(a, BasicAutomata.MakeAnyChar());
+ a = BasicOperations.Concatenate(a, BasicAutomata.MakeString(s
+ .Substring(i)));
+ list.Add(a);
+ }
+
+ var automaton = BasicOperations.Union(list);
+ MinimizationOperations.Minimize(automaton);
+ return automaton;
+ }
+
+ private Lucene.Net.Util.Automaton.Automaton DeletionsOf(String s)
+ {
+ var list = new List<Lucene.Net.Util.Automaton.Automaton>();
+
+ for (var i = 0; i < s.Length; i++)
+ {
+ var a = BasicAutomata.MakeString(s.Substring(0, i));
+ a = BasicOperations.Concatenate(a, BasicAutomata.MakeString(s
+ .Substring(i + 1)));
+ a.ExpandSingleton();
+ list.Add(a);
+ }
+
+ var automaton = BasicOperations.Union(list);
+ MinimizationOperations.Minimize(automaton);
+ return automaton;
+ }
+
+ private Lucene.Net.Util.Automaton.Automaton SubstitutionsOf(String s)
+ {
+ var list = new List<Lucene.Net.Util.Automaton.Automaton>();
+
+ for (var i = 0; i < s.Length; i++)
+ {
+ var a = BasicAutomata.MakeString(s.Substring(0, i));
+ a = BasicOperations.Concatenate(a, BasicAutomata.MakeAnyChar());
+ a = BasicOperations.Concatenate(a, BasicAutomata.MakeString(s
+ .Substring(i + 1)));
+ list.Add(a);
+ }
+
+ var automaton = BasicOperations.Union(list);
+ MinimizationOperations.Minimize(automaton);
+ return automaton;
+ }
+
+ private Lucene.Net.Util.Automaton.Automaton TranspositionsOf(String s)
+ {
+ if (s.Length < 2)
+ return BasicAutomata.MakeEmpty();
+ var list = new List<Lucene.Net.Util.Automaton.Automaton>();
+ for (var i = 0; i < s.Length - 1; i++)
+ {
+ var sb = new StringBuilder();
+ sb.Append(s.Substring(0, i));
+ sb.Append(s[i + 1]);
+ sb.Append(s[i]);
+ sb.Append(s.Substring(i + 2, s.Length));
+ var st = sb.ToString();
+ if (!st.Equals(s))
+ list.Add(BasicAutomata.MakeString(st));
+ }
+ var a = BasicOperations.Union(list);
+ MinimizationOperations.Minimize(a);
+ return a;
+ }
+
+ private void AssertBruteForce(String input, Lucene.Net.Util.Automaton.Automaton dfa, int distance)
+ {
+ var ra = new CharacterRunAutomaton(dfa);
+ var maxLen = input.Length + distance + 1;
+ var maxNum = (int)Math.Pow(2, maxLen);
+ for (var i = 0; i < maxNum; i++)
+ {
+ String encoded = Integer.toString(i, 2);
+ var accepts = ra.Run(encoded);
+ if (accepts)
+ {
+ Assert.IsTrue(GetDistance(input, encoded) <= distance);
+ }
+ else
+ {
+ Assert.IsTrue(GetDistance(input, encoded) > distance);
+ }
+ }
+ }
+
+ private void AssertBruteForceT(String input, Lucene.Net.Util.Automaton.Automaton dfa, int distance)
+ {
+ var ra = new CharacterRunAutomaton(dfa);
+ var maxLen = input.Length + distance + 1;
+ var maxNum = (int)Math.Pow(2, maxLen);
+ for (var i = 0; i < maxNum; i++)
+ {
+ String encoded = Integer.toString(i, 2);
+ var accepts = ra.Run(encoded);
+ if (accepts)
+ {
+ Assert.IsTrue(GetTDistance(input, encoded) <= distance);
+ }
+ else
+ {
+ Assert.IsTrue(GetTDistance(input, encoded) > distance);
+ }
+ }
+ }
+
+ //*****************************
+ // Compute Levenshtein distance: see org.apache.commons.lang.StringUtils#getLevenshteinDistance(String, String)
+ //*****************************
+ private int GetDistance(String target, String other)
+ {
+ char[] sa;
+ int n;
+ int[] p; //'previous' cost array, horizontally
+ int[] d; // cost array, horizontally
+ int[] _d; //placeholder to assist in swapping p and d
+
+ /*
+ The difference between this impl. and the previous is that, rather
+ than creating and retaining a matrix of size s.length()+1 by t.length()+1,
+ we maintain two single-dimensional arrays of length s.length()+1. The first, d,
+ is the 'current working' distance array that maintains the newest distance cost
+ counts as we iterate through the characters of String s. Each time we increment
+ the index of String t we are comparing, d is copied to p, the second int[]. Doing so
+ allows us to retain the previous cost counts as required by the algorithm (taking
+ the minimum of the cost count to the left, up one, and diagonally up and to the left
+ of the current cost count being calculated). (Note that the arrays aren't really
+ copied anymore, just switched...this is clearly much better than cloning an array
+ or doing a System.arraycopy() each time through the outer loop.)
+
+ Effectively, the difference between the two implementations is this one does not
+ cause an out of memory condition when calculating the LD over two very large strings.
+ */
+
+ sa = target.ToCharArray();
+ n = sa.Length;
+ p = new int[n + 1];
+ d = new int[n + 1];
+
+ var m = other.Length;
+ if (n == 0 || m == 0)
+ {
+ if (n == m)
+ {
+ return 0;
+ }
+ else
+ {
+ return Math.Max(n, m);
+ }
+ }
+
+
+ // indexes into strings s and t
+ int i; // iterates through s
+ int j; // iterates through t
+
+ char t_j; // jth character of t
+
+ int cost; // cost
+
+ for (i = 0; i <= n; i++)
+ {
+ p[i] = i;
+ }
+
+ for (j = 1; j <= m; j++)
+ {
+ t_j = other[j - 1];
+ d[0] = j;
+
+ for (i = 1; i <= n; i++)
+ {
+ cost = sa[i - 1] == t_j ? 0 : 1;
+ // minimum of cell to the left+1, to the top+1, diagonally left and up +cost
+ d[i] = Math.Min(Math.Min(d[i - 1] + 1, p[i] + 1), p[i - 1] + cost);
+ }
+
+ // copy current distance counts to 'previous row' distance counts
+ _d = p;
+ p = d;
+ d = _d;
+ }
+
+ // our last action in the above loop was to switch d and p, so p now
+ // actually has the most recent cost counts
+ return Math.Abs(p[n]);
+ }
+
+ private int GetTDistance(String target, String other)
+ {
+ char[] sa;
+ int n;
+ int[,] d; // cost array
+
+ sa = target.ToCharArray();
+ n = sa.Length;
+ int m = other.Length;
+ d = new int[n + 1, m + 1];
+
+ if (n == 0 || m == 0)
+ {
+ if (n == m)
+ {
+ return 0;
+ }
+ else
+ {
+ return Math.Max(n, m);
+ }
+ }
+
+ // indexes into strings s and t
+ int i; // iterates through s
+ int j; // iterates through t
+
+ char t_j; // jth character of t
+
+ int cost; // cost
+
+ for (i = 0; i <= n; i++)
+ {
+ d[i,0] = i;
+ }
+
+ for (j = 0; j <= m; j++)
+ {
+ d[0,j] = j;
+ }
+
+ for (j = 1; j <= m; j++)
+ {
+ t_j = other[j - 1];
+
+ for (i = 1; i <= n; i++)
+ {
+ cost = sa[i - 1] == t_j ? 0 : 1;
+ // minimum of cell to the left+1, to the top+1, diagonally left and up +cost
+ d[i,j] = Math.Min(Math.Min(d[i - 1,j] + 1, d[i,j - 1] + 1), d[i - 1,j - 1] + cost);
+ // transposition
+ if (i > 1 && j > 1 && target[i - 1] == other[j - 2] && target[i - 2] == other[j - 1])
+ {
+ d[i,j] = Math.Min(d[i,j], d[i - 2,j - 2] + cost);
+ }
+ }
+ }
+
+ // our last action in the above loop was to switch d and p, so p now
+ // actually has the most recent cost counts
+ return Math.Abs(d[n,m]);
+ }
+ }
+}
http://git-wip-us.apache.org/repos/asf/lucenenet/blob/14f5ae0c/test/core/Util/Automaton/TestMinimize.cs
----------------------------------------------------------------------
diff --git a/test/core/Util/Automaton/TestMinimize.cs b/test/core/Util/Automaton/TestMinimize.cs
new file mode 100644
index 0000000..c3aff35
--- /dev/null
+++ b/test/core/Util/Automaton/TestMinimize.cs
@@ -0,0 +1,51 @@
+using System;
+using Lucene.Net.Util;
+using Lucene.Net.Util.Automaton;
+using NUnit.Framework;
+
+namespace Lucene.Net.Test.Util.Automaton
+{
+ [TestFixture]
+ public class TestMinimize : LuceneTestCase
+ {
+ /** the minimal and non-minimal are compared to ensure they are the same. */
+ [Test]
+ public void Test()
+ {
+ int num = AtLeast(200);
+ for (var i = 0; i < num; i++)
+ {
+ var a = AutomatonTestUtil.RandomAutomaton(new Random());
+ var b = a.Clone();
+ MinimizationOperations.Minimize(b);
+ Assert.IsTrue(BasicOperations.SameLanguage(a, b));
+ }
+ }
+
+ /** compare minimized against minimized with a slower, simple impl.
+ * we check not only that they are the same, but that #states/#transitions
+ * are the same. */
+ [Test]
+ public void TestAgainstBrzozowski()
+ {
+ int num = AtLeast(200);
+ for (var i = 0; i < num; i++)
+ {
+ var a = AutomatonTestUtil.RandomAutomaton(new Random());
+ AutomatonTestUtil.MinimizeSimple(a);
+ var b = a.Clone();
+ MinimizationOperations.Minimize(b);
+ Assert.IsTrue(BasicOperations.SameLanguage(a, b));
+ Assert.Equals(a.GetNumberOfStates(), b.GetNumberOfStates());
+ Assert.Equals(a.GetNumberOfTransitions(), b.GetNumberOfTransitions());
+ }
+ }
+
+ /** n^2 space usage in Hopcroft minimization? */
+ [Test]
+ public void TestMinimizeHuge()
+ {
+ new RegExp("+-*(A|.....|BC)*]", RegExp.NONE).ToAutomaton();
+ }
+ }
+}
http://git-wip-us.apache.org/repos/asf/lucenenet/blob/14f5ae0c/test/core/Util/Automaton/TestSpecialOperations.cs
----------------------------------------------------------------------
diff --git a/test/core/Util/Automaton/TestSpecialOperations.cs b/test/core/Util/Automaton/TestSpecialOperations.cs
new file mode 100644
index 0000000..29f8efc
--- /dev/null
+++ b/test/core/Util/Automaton/TestSpecialOperations.cs
@@ -0,0 +1,38 @@
+using System;
+using Lucene.Net.Util;
+using Lucene.Net.Util.Automaton;
+using NUnit.Framework;
+
+namespace Lucene.Net.Test.Util.Automaton
+{
+ [TestFixture]
+ public class TestSpecialOperations : LuceneTestCase
+ {
+ [Test]
+ public void TestIsFinite()
+ {
+ int num = AtLeast(200);
+ for (var i = 0; i < num; i++)
+ {
+ var a = AutomatonTestUtil.randomAutomaton(new Random());
+ var b = a.clone();
+ Assert.Equals(AutomatonTestUtil.isFiniteSlow(a), SpecialOperations.IsFinite(b));
+ }
+ }
+
+ [Test]
+ public void TestFiniteStrings()
+ {
+ var a = BasicOperations.Union(BasicAutomata.MakeString("dog"), BasicAutomata.MakeString("duck"));
+ MinimizationOperations.Minimize(a);
+ var strings = SpecialOperations.GetFiniteStrings(a, -1);
+ assertEquals(2, strings.Count);
+ var dog = new IntsRef();
+ Util.ToIntsRef(new BytesRef("dog"), dog);
+ assertTrue(strings.Contains(dog));
+ var duck = new IntsRef();
+ Util.ToIntsRef(new BytesRef("duck"), duck);
+ assertTrue(strings.Contains(duck));
+ }
+ }
+}
http://git-wip-us.apache.org/repos/asf/lucenenet/blob/14f5ae0c/test/core/Util/Automaton/TestUTF32ToUTF8.cs
----------------------------------------------------------------------
diff --git a/test/core/Util/Automaton/TestUTF32ToUTF8.cs b/test/core/Util/Automaton/TestUTF32ToUTF8.cs
new file mode 100644
index 0000000..b2bdaca
--- /dev/null
+++ b/test/core/Util/Automaton/TestUTF32ToUTF8.cs
@@ -0,0 +1,271 @@
+using System;
+using Lucene.Net.Support;
+using Lucene.Net.Test.Support;
+using Lucene.Net.Util;
+using Lucene.Net.Util.Automaton;
+using NUnit.Framework;
+
+namespace Lucene.Net.Test.Util.Automaton
+{
+ [TestFixture]
+ public class TestUTF32ToUTF8 : LuceneTestCase
+ {
+ [SetUp]
+ public override void SetUp()
+ {
+ base.SetUp();
+ }
+
+ private static readonly int MAX_UNICODE = 0x10FFFF;
+
+ internal readonly BytesRef b = new BytesRef(4);
+
+ private bool Matches(ByteRunAutomaton a, int code)
+ {
+ char[] chars = Character.ToChars(code);
+ UnicodeUtil.UTF16toUTF8(chars, 0, chars.Length, b);
+ return a.Run(b.bytes, 0, b.length);
+ }
+
+ private void TestOne(Random r, ByteRunAutomaton a, int startCode, int endCode, int iters)
+ {
+
+ // Verify correct ints are accepted
+ int nonSurrogateCount;
+ bool ovSurStart;
+ if (endCode < UnicodeUtil.UNI_SUR_HIGH_START ||
+ startCode > UnicodeUtil.UNI_SUR_LOW_END)
+ {
+ // no overlap w/ surrogates
+ nonSurrogateCount = endCode - startCode + 1;
+ ovSurStart = false;
+ }
+ else if (IsSurrogate(startCode))
+ {
+ // start of range overlaps surrogates
+ nonSurrogateCount = endCode - startCode + 1 - (UnicodeUtil.UNI_SUR_LOW_END - startCode + 1);
+ ovSurStart = false;
+ }
+ else if (IsSurrogate(endCode))
+ {
+ // end of range overlaps surrogates
+ ovSurStart = true;
+ nonSurrogateCount = endCode - startCode + 1 - (endCode - UnicodeUtil.UNI_SUR_HIGH_START + 1);
+ }
+ else
+ {
+ // range completely subsumes surrogates
+ ovSurStart = true;
+ nonSurrogateCount = endCode - startCode + 1 - (UnicodeUtil.UNI_SUR_LOW_END - UnicodeUtil.UNI_SUR_HIGH_START + 1);
+ }
+
+ //assert nonSurrogateCount > 0;
+
+ for (var iter = 0; iter < iters; iter++)
+ {
+ // pick random code point in-range
+
+ int code = startCode + r.Next(nonSurrogateCount);
+ if (IsSurrogate(code))
+ {
+ if (ovSurStart)
+ {
+ code = UnicodeUtil.UNI_SUR_LOW_END + 1 + (code - UnicodeUtil.UNI_SUR_HIGH_START);
+ }
+ else
+ {
+ code = UnicodeUtil.UNI_SUR_LOW_END + 1 + (code - startCode);
+ }
+ }
+
+ //assert code >= startCode && code <= endCode: "code=" + code + " start=" + startCode + " end=" + endCode;
+ //assert !IsSurrogate(code);
+
+ assertTrue("DFA for range " + startCode + "-" + endCode + " failed to match code=" + code,
+ Matches(a, code));
+ }
+
+ // Verify invalid ints are not accepted
+ var invalidRange = MAX_UNICODE - (endCode - startCode + 1);
+ if (invalidRange > 0)
+ {
+ for (var iter = 0; iter < iters; iter++)
+ {
+ int x = _TestUtil.NextInt(r, 0, invalidRange - 1);
+ int code;
+ if (x >= startCode)
+ {
+ code = endCode + 1 + x - startCode;
+ }
+ else
+ {
+ code = x;
+ }
+ if ((code >= UnicodeUtil.UNI_SUR_HIGH_START && code <= UnicodeUtil.UNI_SUR_HIGH_END) |
+ (code >= UnicodeUtil.UNI_SUR_LOW_START && code <= UnicodeUtil.UNI_SUR_LOW_END))
+ {
+ iter--;
+ continue;
+ }
+ Assert.IsFalse(Matches(a, code), "DFA for range " + startCode + "-" + endCode + " matched invalid code=" + code);
+
+ }
+ }
+ }
+
+ // Evenly picks random code point from the 4 "buckets"
+ // (bucket = same #bytes when encoded to utf8)
+ private int GetCodeStart(Random r)
+ {
+ switch (r.Next(4))
+ {
+ case 0:
+ return _TestUtil.NextInt(r, 0, 128);
+ case 1:
+ return _TestUtil.NextInt(r, 128, 2048);
+ case 2:
+ return _TestUtil.NextInt(r, 2048, 65536);
+ default:
+ return _TestUtil.NextInt(r, 65536, 1 + MAX_UNICODE);
+ }
+ }
+
+ private static bool IsSurrogate(int code)
+ {
+ return code >= UnicodeUtil.UNI_SUR_HIGH_START && code <= UnicodeUtil.UNI_SUR_LOW_END;
+ }
+
+ [Test]
+ public void TestRandomRanges()
+ {
+ var r = new Random();
+ int ITERS = AtLeast(10);
+ int ITERS_PER_DFA = AtLeast(100);
+ for (int iter = 0; iter < ITERS; iter++)
+ {
+ int x1 = GetCodeStart(r);
+ int x2 = GetCodeStart(r);
+ int startCode, endCode;
+
+ if (x1 < x2)
+ {
+ startCode = x1;
+ endCode = x2;
+ }
+ else
+ {
+ startCode = x2;
+ endCode = x1;
+ }
+
+ if (IsSurrogate(startCode) && IsSurrogate(endCode))
+ {
+ iter--;
+ continue;
+ }
+
+ var a = new Lucene.Net.Util.Automaton.Automaton();
+ var end = new State {Accept = true};
+ a.InitialState.AddTransition(new Transition(startCode, endCode, end));
+ a.Deterministic = true;
+
+ TestOne(r, new ByteRunAutomaton(a), startCode, endCode, ITERS_PER_DFA);
+ }
+ }
+
+ [Test]
+ public void TestSpecialCase()
+ {
+ var re = new RegExp(".?");
+ var automaton = re.ToAutomaton();
+ var cra = new CharacterRunAutomaton(automaton);
+ var bra = new ByteRunAutomaton(automaton);
+ // make sure character dfa accepts empty string
+ assertTrue(cra.IsAccept(cra.InitialState));
+ assertTrue(cra.Run(""));
+ assertTrue(cra.Run(new char[0], 0, 0));
+
+ // make sure byte dfa accepts empty string
+ assertTrue(bra.IsAccept(bra.InitialState));
+ assertTrue(bra.Run(new sbyte[0], 0, 0));
+ }
+
+ [Test]
+ public void TestSpecialCase2()
+ {
+ var re = new RegExp(".+\u0775");
+ var input = "\ufadc\ufffd\ub80b\uda5a\udc68\uf234\u0056\uda5b\udcc1\ufffd\ufffd\u0775";
+ var automaton = re.ToAutomaton();
+ var cra = new CharacterRunAutomaton(automaton);
+ var bra = new ByteRunAutomaton(automaton);
+
+ assertTrue(cra.Run(input));
+
+ byte[] bytes = input.GetBytes("UTF-8");
+ assertTrue(bra.Run(bytes, 0, bytes.Length)); // this one fails!
+ }
+
+ [Test]
+ public void TestSpecialCase3()
+ {
+ var re = new RegExp("(\\鯺)*(.)*\\Ӕ");
+ var input = "\u5cfd\ufffd\ub2f7\u0033\ue304\u51d7\u3692\udb50\udfb3\u0576\udae2\udc62\u0053\u0449\u04d4";
+ var automaton = re.ToAutomaton();
+ var cra = new CharacterRunAutomaton(automaton);
+ var bra = new ByteRunAutomaton(automaton);
+
+ assertTrue(cra.Run(input));
+
+ byte[] bytes = input.GetBytes("UTF-8");
+ assertTrue(bra.Run(bytes, 0, bytes.Length));
+ }
+
+ [Test]
+ public void TestRandomRegexes()
+ {
+ int num = AtLeast(250);
+ for (var i = 0; i < num; i++)
+ {
+ AssertAutomaton(new RegExp(AutomatonTestUtil.randomRegexp(new Random()), RegExp.NONE).ToAutomaton());
+ }
+ }
+
+ private void AssertAutomaton(Lucene.Net.Util.Automaton.Automaton automaton)
+ {
+ var cra = new CharacterRunAutomaton(automaton);
+ var bra = new ByteRunAutomaton(automaton);
+ AutomatonTestUtil.RandomAcceptedStrings ras = new AutomatonTestUtil.RandomAcceptedStrings(automaton);
+
+ int num = AtLeast(1000);
+ for (int i = 0; i < num; i++)
+ {
+ string str;
+ if (new Random().NextBool())
+ {
+ // likely not accepted
+ str = _TestUtil.RandomUnicodeString(new Random());
+ }
+ else
+ {
+ // will be accepted
+ int[] codepoints = ras.GetRandomAcceptedString(new Random());
+ try
+ {
+ str = UnicodeUtil.NewString(codepoints, 0, codepoints.Length);
+ }
+ catch (Exception e)
+ {
+ Console.WriteLine(codepoints.Length + " codepoints:");
+ for (int j = 0; j < codepoints.Length; j++)
+ {
+ Console.WriteLine(" " + Integer.toHexString(codepoints[j]));
+ }
+ throw e;
+ }
+ }
+ var bytes = str.GetBytes("UTF-8");
+ assertEquals(cra.Run(str), bra.Run(bytes, 0, bytes.Length));
+ }
+ }
+ }
+}
http://git-wip-us.apache.org/repos/asf/lucenenet/blob/14f5ae0c/test/core/Util/TestWeakIdentityMap.cs
----------------------------------------------------------------------
diff --git a/test/core/Util/TestWeakIdentityMap.cs b/test/core/Util/TestWeakIdentityMap.cs
new file mode 100644
index 0000000..2aed402
--- /dev/null
+++ b/test/core/Util/TestWeakIdentityMap.cs
@@ -0,0 +1,276 @@
+using System;
+using System.Threading;
+using Lucene.Net.Support;
+using Lucene.Net.Test.Support;
+using Lucene.Net.Util;
+using NUnit.Framework;
+
+namespace Lucene.Net.Test.Util
+{
+ [TestFixture]
+ public class TestWeakIdentityMap : LuceneTestCase
+ {
+ [Test]
+ public void TestSimpleHashMap()
+ {
+ WeakIdentityMap<string, string> map =
+ WeakIdentityMap<string, string>.NewHashMap(new Random().NextBool());
+ // we keep strong references to the keys,
+ // so WeakIdentityMap will not forget about them:
+ string key1 = "foo";
+ string key2 = "foo";
+ string key3 = "foo";
+
+ Assert.AreNotSame(key1, key2);
+ Assert.AreEqual(key1, key2);
+ Assert.AreNotSame(key1, key3);
+ Assert.AreEqual(key1, key3);
+ Assert.AreNotSame(key2, key3);
+ Assert.AreEqual(key2, key3);
+
+ // try null key & check its iterator also return null:
+ map[null] = "null";
+ {
+ var it = map.Keys.GetEnumerator();
+ Assert.IsTrue(it.MoveNext());
+ Assert.IsNull(it.Current);
+ Assert.IsFalse(it.MoveNext());
+ Assert.IsFalse(it.MoveNext());
+ }
+ // 2 more keys:
+ map[key1] = "bar1";
+ map[key2] = "bar2";
+
+ Assert.AreEqual(3, map.Size);
+
+ Assert.AreEqual("bar1", map[key1]);
+ Assert.AreEqual("bar2", map[key2]);
+ Assert.AreEqual(null, map[key3]);
+ Assert.AreEqual("null", map[null]);
+
+ Assert.IsTrue(map.ContainsKey(key1));
+ Assert.IsTrue(map.ContainsKey(key2));
+ Assert.IsFalse(map.ContainsKey(key3));
+ Assert.IsTrue(map.ContainsKey(null));
+
+ // repeat and check that we have no double entries
+ map[key1] = "bar1";
+ map[key2] = "bar2";
+ map[null] = null;
+
+ Assert.AreEqual(3, map.Size);
+
+ Assert.AreEqual("bar1", map[key1]);
+ Assert.AreEqual("bar2", map[key2]);
+ Assert.AreEqual(null, map[key3]);
+ Assert.AreEqual("null", map[null]);
+
+ Assert.IsTrue(map.ContainsKey(key1));
+ Assert.IsTrue(map.ContainsKey(key2));
+ Assert.IsFalse(map.ContainsKey(key3));
+ Assert.IsTrue(map.ContainsKey(null));
+
+ map.Remove(null);
+ Assert.AreEqual(2, map.Size);
+ map.Remove(key1);
+ Assert.AreEqual(1, map.Size);
+ map[key1] = "bar1";
+ map[key2] = "bar2";
+ map[key3] = "bar3";
+ Assert.AreEqual(3, map.Size);
+
+ int c = 0, keysAssigned = 0;
+ for (var enumerator = map.Keys.GetEnumerator(); enumerator.MoveNext(); )
+ {
+ Assert.IsTrue(enumerator.MoveNext()); // try again, should return same result!
+ var k = enumerator.Current;
+ Assert.IsTrue(k == key1 || k == key2 | k == key3);
+ keysAssigned += (k == key1) ? 1 : ((k == key2) ? 2 : 4);
+ c++;
+ }
+ Assert.AreEqual(3, c);
+ Assert.AreEqual(1 + 2 + 4, keysAssigned, "all keys must have been seen");
+
+ c = 0;
+ for (var enumerator = map.Values.GetEnumerator(); enumerator.MoveNext(); )
+ {
+ var v = enumerator.Current;
+ Assert.IsTrue(v.StartsWith("bar"));
+ c++;
+ }
+ Assert.AreEqual(3, c);
+
+ // clear strong refs
+ key1 = key2 = key3 = null;
+
+ // check that GC does not cause problems in reap() method, wait 1 second and let GC work:
+ int size = map.Size;
+ for (int i = 0; size > 0 && i < 10; i++) try
+ {
+ GC.WaitForPendingFinalizers();
+ GC.Collect();
+ int newSize = map.Size;
+ Assert.IsTrue(size >= newSize, "previousSize(" + size + ")>=newSize(" + newSize + ")");
+ size = newSize;
+ Thread.Sleep(TimeSpan.FromMilliseconds(100L));
+ c = 0;
+ for (var enumerator = map.Keys.GetEnumerator(); enumerator.MoveNext(); )
+ {
+ assertNotNull(enumerator.Current);
+ c++;
+ }
+ newSize = map.Size;
+ Assert.IsTrue(size >= c, "previousSize(" + size + ")>=iteratorSize(" + c + ")");
+ Assert.IsTrue(c >= newSize, "iteratorSize(" + c + ")>=newSize(" + newSize + ")");
+ size = newSize;
+ }
+ catch (ThreadInterruptedException ie) { }
+
+ map.Clear();
+ Assert.AreEqual(0, map.Size);
+ Assert.IsTrue(map.IsEmpty);
+
+ var enumerator2 = map.Keys.GetEnumerator();
+ Assert.IsFalse(enumerator2.MoveNext());
+ try
+ {
+ var current = enumerator2.Current;
+ Fail("Should throw InvalidOperationException");
+ }
+ catch (InvalidOperationException nse)
+ {
+ }
+
+ key1 = "foo";
+ key2 = "foo";
+ map[key1] = "bar1";
+ map[key2] = "bar2";
+ Assert.AreEqual(2, map.Size);
+
+ map.Clear();
+ Assert.AreEqual(0, map.Size);
+ Assert.IsTrue(map.IsEmpty);
+ }
+
+ private sealed class AnonymousThreadClass : ThreadClass
+ {
+ private readonly Random rnd;
+ private readonly WeakIdentityMap<object, int> map;
+ private readonly int keyCount;
+ private readonly AtomicReferenceArray<object> keys;
+
+ public AnonymousThreadClass(Random rnd, WeakIdentityMap<object, int> map, AtomicReferenceArray<object> keys, int keyCount)
+ {
+ this.rnd = rnd;
+ this.map = map;
+ this.keyCount = keyCount;
+ this.keys = keys;
+ }
+
+ public override void Run()
+ {
+ int count = AtLeast(rnd, 10000);
+ for (int i = 0; i < count; i++)
+ {
+ int j = rnd.Next(keyCount);
+ switch (rnd.Next(5))
+ {
+ case 0:
+ map[keys[j]] = j;
+ break;
+ case 1:
+ int v = map[keys[j]];
+ if (v != null)
+ {
+ Assert.AreEqual(j, v);
+ }
+ break;
+ case 2:
+ map.Remove(keys[j]);
+ break;
+ case 3:
+ // renew key, the old one will be GCed at some time:
+ keys.Set(j, new object());
+ break;
+ case 4:
+ // check iterator still working
+ for (var it = map.Keys.GetEnumerator(); it.MoveNext(); )
+ {
+ Assert.IsNotNull(it.Current);
+ }
+ break;
+ default:
+ Fail("Should not get here.");
+ break;
+ }
+ }
+ }
+ }
+
+ [Test]
+ public void TestConcurrentHashMap()
+ {
+ // don't make threadCount and keyCount random, otherwise easily OOMs or fails otherwise:
+ int threadCount = 8, keyCount = 1024;
+ ExecutorService exec = Executors.newFixedThreadPool(threadCount, new NamedThreadFactory("TestConcurrentHashMap"));
+ WeakIdentityMap<object, int> map =
+ WeakIdentityMap<object, int>.NewConcurrentHashMap(new Random().NextBool());
+ // we keep strong references to the keys,
+ // so WeakIdentityMap will not forget about them:
+ AtomicReferenceArray<object> keys = new AtomicReferenceArray<object>(keyCount);
+ for (int j = 0; j < keyCount; j++)
+ {
+ keys.Set(j, new object());
+ }
+
+ try
+ {
+ for (int t = 0; t < threadCount; t++)
+ {
+ Random rnd = new Random(new Random().Next());
+ exec.execute(new AnonymousThreadClass());
+ }
+ }
+ finally
+ {
+ exec.Shutdown();
+ while (!exec.AwaitTermination(1000L, TimeUnit.Milliseconds)) ;
+ }
+
+ // clear strong refs
+ for (int j = 0; j < keyCount; j++)
+ {
+ keys.Set(j, null);
+ }
+
+ // check that GC does not cause problems in reap() method:
+ int size = map.Size;
+ for (int i = 0; size > 0 && i < 10; i++)
+ {
+ try
+ {
+ GC.WaitForPendingFinalizers();
+ GC.Collect();
+ int newSize = map.Size;
+ Assert.IsTrue(size >= newSize, "previousSize(" + size + ")>=newSize(" + newSize + ")");
+ size = newSize;
+ Thread.Sleep(TimeSpan.FromMilliseconds(100L));
+ int c = 0;
+ for (var it = map.Keys.GetEnumerator(); it.MoveNext();)
+ {
+ assertNotNull(it.Current);
+ c++;
+ }
+ newSize = map.Size;
+ Assert.IsTrue(size >= c, "previousSize(" + size + ")>=iteratorSize(" + c + ")");
+ Assert.IsTrue(c >= newSize, "iteratorSize(" + c + ")>=newSize(" + newSize + ")");
+ size = newSize;
+ }
+ catch (ThreadInterruptedException ie)
+ {
+
+ }
+ }
+ }
+ }
+}