lucenenet-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From mhern...@apache.org
Subject [11/50] [abbrv] git commit: Port: unit tests. more from util namespace
Date Tue, 24 Sep 2013 18:32:47 GMT
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 <jmblair7@gmail.com>
Authored: Tue Jul 16 17:32:28 2013 -0400
Committer: James Blair <jmblair7@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)
+                {
+
+                }
+            }
+        }
+    }
+}


Mime
View raw message