Commits

Anonymous committed 8f086e5

Added a dictionary and a hashset to store words that don't work and at what level they are at when they don't work. This speeds up the program significantly with words that have a lot of repetitions.

Comments (0)

Files changed (3)

nunit_spellcheck/TestResult.xml

 <?xml version="1.0" encoding="utf-8" standalone="no"?>
 <!--This file represents the results of running a test suite-->
-<test-results name="C:\sandbox\spellchecker\nunit_spellcheck\spellcheck.nunit" total="17" errors="0" failures="0" not-run="0" inconclusive="0" ignored="0" skipped="0" invalid="0" date="2011-12-31" time="20:53:56">
+<test-results name="C:\sandbox\spellchecker\nunit_spellcheck\spellcheck.nunit" total="17" errors="0" failures="0" not-run="0" inconclusive="0" ignored="0" skipped="0" invalid="0" date="2012-01-03" time="17:33:15">
   <environment nunit-version="2.5.10.11092" clr-version="2.0.50727.5448" os-version="Microsoft Windows NT 6.1.7601 Service Pack 1" platform="Win32NT" cwd="C:\Program Files (x86)\NUnit 2.5.10\bin\net-2.0" machine-name="ANIMUS" user="Charles" user-domain="Animus" />
   <culture-info current-culture="en-US" current-uiculture="en-US" />
-  <test-suite type="Test Project" name="C:\sandbox\spellchecker\nunit_spellcheck\spellcheck.nunit" executed="True" result="Success" success="True" time="0.226" asserts="0">
+  <test-suite type="Test Project" name="C:\sandbox\spellchecker\nunit_spellcheck\spellcheck.nunit" executed="True" result="Success" success="True" time="0.240" asserts="0">
     <results>
-      <test-suite type="Assembly" name="C:\sandbox\spellchecker\nunit_spellcheck\..\spellcheck\spellcheckUnitTests\bin\Release\spellcheckUnitTests.dll" executed="True" result="Success" success="True" time="0.084" asserts="0">
+      <test-suite type="Assembly" name="C:\sandbox\spellchecker\nunit_spellcheck\..\spellcheck\spellcheckUnitTests\bin\Release\spellcheckUnitTests.dll" executed="True" result="Success" success="True" time="0.096" asserts="0">
         <results>
-          <test-suite type="Namespace" name="spellCheckUnitTests" executed="True" result="Success" success="True" time="0.080" asserts="0">
+          <test-suite type="Namespace" name="spellCheckUnitTests" executed="True" result="Success" success="True" time="0.092" asserts="0">
             <results>
-              <test-suite type="TestFixture" name="LetterTreePopulationTests" executed="True" result="Success" success="True" time="0.052" asserts="0">
+              <test-suite type="TestFixture" name="LetterTreePopulationTests" executed="True" result="Success" success="True" time="0.057" asserts="0">
                 <results>
-                  <test-case name="spellCheckUnitTests.LetterTreePopulationTests.PopulateNonOverlappingWordsInTree" executed="True" result="Success" success="True" time="0.033" asserts="9" />
-                  <test-case name="spellCheckUnitTests.LetterTreePopulationTests.PopulateNoWordInTree" executed="True" result="Success" success="True" time="0.000" asserts="1" />
-                  <test-case name="spellCheckUnitTests.LetterTreePopulationTests.PopulateOverlappingWordsInTree" executed="True" result="Success" success="True" time="0.001" asserts="8" />
+                  <test-case name="spellCheckUnitTests.LetterTreePopulationTests.PopulateNonOverlappingWordsInTree" executed="True" result="Success" success="True" time="0.037" asserts="9" />
+                  <test-case name="spellCheckUnitTests.LetterTreePopulationTests.PopulateNoWordInTree" executed="True" result="Success" success="True" time="0.001" asserts="1" />
+                  <test-case name="spellCheckUnitTests.LetterTreePopulationTests.PopulateOverlappingWordsInTree" executed="True" result="Success" success="True" time="0.000" asserts="8" />
                   <test-case name="spellCheckUnitTests.LetterTreePopulationTests.PopulateSameWordInTreeTwice" executed="True" result="Success" success="True" time="0.001" asserts="1" />
-                  <test-case name="spellCheckUnitTests.LetterTreePopulationTests.PopulateSingleWordIsInTree" executed="True" result="Success" success="True" time="0.001" asserts="8" />
-                  <test-case name="spellCheckUnitTests.LetterTreePopulationTests.PopulateSmallerWordUsingSameCharactersAsBiggerWord" executed="True" result="Success" success="True" time="0.002" asserts="15" />
+                  <test-case name="spellCheckUnitTests.LetterTreePopulationTests.PopulateSingleWordIsInTree" executed="True" result="Success" success="True" time="0.002" asserts="8" />
+                  <test-case name="spellCheckUnitTests.LetterTreePopulationTests.PopulateSmallerWordUsingSameCharactersAsBiggerWord" executed="True" result="Success" success="True" time="0.001" asserts="15" />
                 </results>
               </test-suite>
-              <test-suite type="TestFixture" name="LetterTreeSpellCheckTests" executed="True" result="Success" success="True" time="0.025" asserts="0">
+              <test-suite type="TestFixture" name="LetterTreeSpellCheckTests" executed="True" result="Success" success="True" time="0.032" asserts="0">
                 <results>
-                  <test-case name="spellCheckUnitTests.LetterTreeSpellCheckTests.SpellcheckExampleOnWebsite" executed="True" result="Success" success="True" time="0.004" asserts="6" />
+                  <test-case name="spellCheckUnitTests.LetterTreeSpellCheckTests.SpellcheckExampleOnWebsite" executed="True" result="Success" success="True" time="0.007" asserts="6" />
                   <test-case name="spellCheckUnitTests.LetterTreeSpellCheckTests.SpellcheckIncorrectVowel" executed="True" result="Success" success="True" time="0.000" asserts="1" />
-                  <test-case name="spellCheckUnitTests.LetterTreeSpellCheckTests.SpellcheckMismatchedCase" executed="True" result="Success" success="True" time="0.001" asserts="1" />
-                  <test-case name="spellCheckUnitTests.LetterTreeSpellCheckTests.SpellcheckNoSuggestionWord" executed="True" result="Success" success="True" time="0.001" asserts="1" />
-                  <test-case name="spellCheckUnitTests.LetterTreeSpellCheckTests.SpellcheckProperlySpelled" executed="True" result="Success" success="True" time="0.000" asserts="1" />
-                  <test-case name="spellCheckUnitTests.LetterTreeSpellCheckTests.SpellcheckProperlySpelledOneLetterWord" executed="True" result="Success" success="True" time="0.000" asserts="1" />
+                  <test-case name="spellCheckUnitTests.LetterTreeSpellCheckTests.SpellcheckMismatchedCase" executed="True" result="Success" success="True" time="0.000" asserts="1" />
+                  <test-case name="spellCheckUnitTests.LetterTreeSpellCheckTests.SpellcheckNoSuggestionWord" executed="True" result="Success" success="True" time="0.000" asserts="1" />
+                  <test-case name="spellCheckUnitTests.LetterTreeSpellCheckTests.SpellcheckProperlySpelled" executed="True" result="Success" success="True" time="0.001" asserts="1" />
+                  <test-case name="spellCheckUnitTests.LetterTreeSpellCheckTests.SpellcheckProperlySpelledOneLetterWord" executed="True" result="Success" success="True" time="0.001" asserts="1" />
                   <test-case name="spellCheckUnitTests.LetterTreeSpellCheckTests.SpellcheckRepeatedLetters" executed="True" result="Success" success="True" time="0.000" asserts="1" />
                   <test-case name="spellCheckUnitTests.LetterTreeSpellCheckTests.SpellcheckWordsThatHaveMultipleCasings" executed="True" result="Success" success="True" time="0.000" asserts="2" />
-                  <test-case name="spellCheckUnitTests.LetterTreeSpellCheckTests.SpellcheckWordsThatHaveRepeatingCharactersWithMultipleCasings" executed="True" result="Success" success="True" time="0.000" asserts="1" />
-                  <test-case name="spellCheckUnitTests.LetterTreeSpellCheckTests.SpellcheckWordsThatHaveRepeatingVowelsNextToOtherVowels" executed="True" result="Success" success="True" time="0.001" asserts="1" />
+                  <test-case name="spellCheckUnitTests.LetterTreeSpellCheckTests.SpellcheckWordsThatHaveRepeatingCharactersWithMultipleCasings" executed="True" result="Success" success="True" time="0.001" asserts="1" />
+                  <test-case name="spellCheckUnitTests.LetterTreeSpellCheckTests.SpellcheckWordsThatHaveRepeatingVowelsNextToOtherVowels" executed="True" result="Success" success="True" time="0.000" asserts="1" />
                   <test-case name="spellCheckUnitTests.LetterTreeSpellCheckTests.SpellcheckWordsThatNeedBacktrackingToFind" executed="True" result="Success" success="True" time="0.000" asserts="1" />
                 </results>
               </test-suite>

nunit_spellcheck/spellcheck.VisualState.xml

   <ExcludeCategories>false</ExcludeCategories>
   <Nodes>
     <Node UniqueName="[0-1000]C:\sandbox\spellchecker\nunit_spellcheck\spellcheck.nunit" Expanded="true" />
-    <Node UniqueName="[0-1019]C:\sandbox\spellchecker\nunit_spellcheck\..\spellcheck\spellcheckUnitTests\bin\Release\spellcheckUnitTests.dll" Expanded="true" />
-    <Node UniqueName="[0-1020]spellCheckUnitTests" Expanded="true" />
+    <Node UniqueName="[0-1020]C:\sandbox\spellchecker\nunit_spellcheck\..\spellcheck\spellcheckUnitTests\bin\Release\spellcheckUnitTests.dll" Expanded="true" />
+    <Node UniqueName="[0-1021]spellCheckUnitTests" Expanded="true" />
     <Node UniqueName="[0-1000]spellCheckUnitTests.LetterTreePopulationTests" Expanded="true" />
     <Node UniqueName="[0-1007]spellCheckUnitTests.LetterTreeSpellCheckTests" Expanded="true" />
   </Nodes>

spellcheck/spellcheck/LetterTree.cs

         private const string NO_SUGGESTION_TEXT = "NO SUGGESTION";
 
         public Dictionary<char, LetterNode> Tree { get; private set; }
+        public Dictionary<string, HashSet<int>> BadWord { get; private set; }
 
         public LetterTree()
         {
             Tree = new Dictionary<char,LetterNode>();
+            BadWord = new Dictionary<string, HashSet<int>>();
         }
 
         public TraversalData GetRoot()
         public string Spellcheck(string word)
         {
             var root = GetRoot();
-            return Spellcheck(word, root);
+            var newWord = Spellcheck(word, root);
+            BadWord.Clear();
+            return newWord;
         }
 
         // This function is called recursively from within itself and from within
         public string Spellcheck(string word, TraversalData traversal,
                                  bool changingVowel = false, bool changingCase = false)
         {
-            if (traversal.CurrentNode != null)
+            // If a word has been checked from this depth, don't check it again.
+            if (!(BadWord.ContainsKey(word) && BadWord[word].Contains(traversal.Depth)))
             {
-                var currentWord = traversal.CurrentNode.GetWord();
+                if (traversal.CurrentNode != null)
+                {
+                    var currentWord = traversal.CurrentNode.GetWord();
 
-                if (traversal.CurrentNode.End == true && currentWord == word)
-                    return currentWord;
-            }
+                    if (traversal.CurrentNode.End == true && currentWord == word)
+                        return currentWord;
+                }
 
-            var nextLocation = TraverseOneStep(word, traversal);
-            if (traversal.Depth != nextLocation.Depth)
-            {
-                var returnedWord = Spellcheck(word, nextLocation);
+                var nextLocation = TraverseOneStep(word, traversal);
+                if (traversal.Depth != nextLocation.Depth)
+                {
+                    var returnedWord = Spellcheck(word, nextLocation);
 
-                if (returnedWord != NO_SUGGESTION_TEXT)
-                    return returnedWord;
-            }
+                    if (returnedWord != NO_SUGGESTION_TEXT)
+                        return returnedWord;
+                }
 
-            // If a vowel was changed to cause the repeating character,
-            // don't remove the repeated character.
-            if ((traversal.Depth + 1 < word.Length && !IsVowel(word[traversal.Depth + 1]))
-                || !changingVowel)
-            {
-                var processedWord = ProcessRepeatedLetter(word, traversal);
+                // If a vowel was changed to cause the repeating character,
+                // don't remove the repeated character.
+                if ((traversal.Depth + 1 < word.Length && !IsVowel(word[traversal.Depth + 1]))
+                    || !changingVowel)
+                {
+                    var processedWord = ProcessRepeatedLetter(word, traversal);
 
-                if (processedWord != NO_SUGGESTION_TEXT)
-                    return processedWord;
-            }
+                    if (processedWord != NO_SUGGESTION_TEXT)
+                        return processedWord;
+                }
 
-            // If you are still checking vowels, so don't try checking them again.
-            if (!changingVowel)
-            {
-                var changedVowel = CheckForIncorrectVowel(word, traversal, changingCase);
+                // If you are still checking vowels, so don't try checking them again.
+                if (!changingVowel)
+                {
+                    var changedVowel = CheckForIncorrectVowel(word, traversal, changingCase);
 
-                if (changedVowel != NO_SUGGESTION_TEXT)
-                    return changedVowel;
-            }
+                    if (changedVowel != NO_SUGGESTION_TEXT)
+                        return changedVowel;
+                }
 
-            // If you already changed the case, don't try checking it again.
-            if (!changingCase)
-            {
-                var changedCasing = CheckForImproperCasing(word, traversal, changingVowel);
+                // If you already changed the case, don't try checking it again.
+                if (!changingCase)
+                {
+                    var changedCasing = CheckForImproperCasing(word, traversal, changingVowel);
 
-                if (changedCasing != NO_SUGGESTION_TEXT)
-                    return changedCasing;
+                    if (changedCasing != NO_SUGGESTION_TEXT)
+                        return changedCasing;
+                }
+
+                if (!BadWord.ContainsKey(word))
+                    BadWord.Add(word, new HashSet<int>());
+                BadWord[word].Add(traversal.Depth);
             }
             return NO_SUGGESTION_TEXT;
         }
         private string ProcessRepeatedLetter(string word, TraversalData traversal)
         {
             // Strip off the repeating letter and run it through spellcheck again
-            StringBuilder newWord = new StringBuilder(word);
+            StringBuilder newWordBuilder = new StringBuilder(word);
 
-            if (traversal.Depth + 2 < word.Length
-                && word[traversal.Depth + 1] == word[traversal.Depth + 2])
+            while (traversal.Depth + 2 < newWordBuilder.Length
+                && newWordBuilder[traversal.Depth + 1] == newWordBuilder[traversal.Depth + 2])
             {
-                newWord = newWord.Remove(traversal.Depth + 1, 1);
+                newWordBuilder = newWordBuilder.Remove(traversal.Depth + 1, 1);
+
+                string newWord = newWordBuilder.ToString();
 
                 if (traversal.CurrentNode != null)
                 {
-                    if (traversal.CurrentNode.End
-                        && traversal.CurrentNode.GetWord() == newWord.ToString())
-                        return traversal.CurrentNode.GetWord();
+                    var newTraversal = traversal;
+                    newTraversal = TraverseOneStep(newWord, newTraversal);
+                    newTraversal = TraverseOneStep(newWord, newTraversal);
+
+                    if (traversal.Depth + 2 == newTraversal.Depth && newTraversal.CurrentNode.End
+                        && newTraversal.CurrentNode.GetWord() == newWord)
+                        return newTraversal.CurrentNode.GetWord();
                 }
-                var spellCheckedWord = Spellcheck(newWord.ToString(), traversal);
+                var spellcheckReturn = Spellcheck(newWord, traversal);
 
-                if (spellCheckedWord != NO_SUGGESTION_TEXT)
-                    return spellCheckedWord;
-
+                if (spellcheckReturn != NO_SUGGESTION_TEXT)
+                    return spellcheckReturn;
             }
             return NO_SUGGESTION_TEXT;
         }
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.