Repository: commons-text Updated Branches: refs/heads/master b8ab576f3 -> 804e4599b
TEXT-105: Typo in LongestCommonSubsequence#logestCommonSubsequence Deprecate method and add method with correct spelling. Project: http://git-wip-us.apache.org/repos/asf/commons-text/repo Commit: http://git-wip-us.apache.org/repos/asf/commons-text/commit/804e4599 Tree: http://git-wip-us.apache.org/repos/asf/commons-text/tree/804e4599 Diff: http://git-wip-us.apache.org/repos/asf/commons-text/diff/804e4599 Branch: refs/heads/master Commit: 804e4599bd63e4bb14c905613711eac8829e54fb Parents: b8ab576 Author: Pascal Schumacher <pascalschumac...@gmx.net> Authored: Fri Oct 20 18:00:13 2017 +0200 Committer: Pascal Schumacher <pascalschumac...@gmx.net> Committed: Fri Oct 20 18:06:13 2017 +0200 ---------------------------------------------------------------------- src/changes/changes.xml | 1 + .../similarity/LongestCommonSubsequence.java | 86 +++++++++++++------- .../LongestCommonSubsequenceTest.java | 42 +++++++++- 3 files changed, 97 insertions(+), 32 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/commons-text/blob/804e4599/src/changes/changes.xml ---------------------------------------------------------------------- diff --git a/src/changes/changes.xml b/src/changes/changes.xml index 52bac95..fdd2ccc 100644 --- a/src/changes/changes.xml +++ b/src/changes/changes.xml @@ -60,6 +60,7 @@ The <action> type attribute can be add,update,fix,remove. <action issue="TEXT-67" type="update" dev="kinow">NumericEntityUnescaper.options - fix TODO</action> <action issue="TEXT-84" type="update" dev="djones">RandomStringGenerator claims to be immutable, but isn't</action> <action issue="TEXT-102" type="add" dev="ggregory">Add StrLookup.resourceBundleLookup(ResourceBundle)</action> + <action issue="TEXT-105" type="fix" dev="pschumacher" due-to="Abrasha">Typo in LongestCommonSubsequence#logestCommonSubsequence</action> </release> <release version="1.1" date="2017-05-23" description="Release 1.1"> http://git-wip-us.apache.org/repos/asf/commons-text/blob/804e4599/src/main/java/org/apache/commons/text/similarity/LongestCommonSubsequence.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/text/similarity/LongestCommonSubsequence.java b/src/main/java/org/apache/commons/text/similarity/LongestCommonSubsequence.java index eb94217..a3c80e8 100644 --- a/src/main/java/org/apache/commons/text/similarity/LongestCommonSubsequence.java +++ b/src/main/java/org/apache/commons/text/similarity/LongestCommonSubsequence.java @@ -43,7 +43,7 @@ package org.apache.commons.text.similarity; public class LongestCommonSubsequence implements SimilarityScore<Integer> { /** - * Calculates longestCommonSubsequence similarity score of two <code>CharSequence</code>'s passed as + * Calculates longest common subsequence similarity score of two <code>CharSequence</code>'s passed as * input. * * @param left first character sequence @@ -62,13 +62,10 @@ public class LongestCommonSubsequence implements SimilarityScore<Integer> { } /** - * - * Computes the longestCommonSubsequence between the two <code>CharSequence</code>'s passed as - * input. + * Computes the longest common subsequence between the two <code>CharSequence</code>'s passed as input. * * <p> - * Note, a substring and - * subsequence are not necessarily the same thing. Indeed, <code>abcxyzqrs</code> and + * Note, a substring and subsequence are not necessarily the same thing. Indeed, <code>abcxyzqrs</code> and * <code>xyzghfm</code> have both the same common substring and subsequence, namely <code>xyz</code>. However, * <code>axbyczqrs</code> and <code>abcxyzqtv</code> have the longest common subsequence <code>xyzq</code> because a * subsequence need not have adjacent characters. @@ -82,35 +79,66 @@ public class LongestCommonSubsequence implements SimilarityScore<Integer> { * * @param left first character sequence * @param right second character sequence - * @return lcsLengthArray + * @return the longest common subsequence found * @throws IllegalArgumentException * if either String input {@code null} + * @deprecated Deprecated as of 1.2 due to a typo in the method name. + * Use {@link #longestCommonSubsequence(CharSequence, CharSequence)} instead. + * This method will be removed in 2.0. */ + @Deprecated public CharSequence logestCommonSubsequence(final CharSequence left, final CharSequence right) { - // Quick return - if (left == null || right == null) { - throw new IllegalArgumentException("Inputs must not be null"); - } - final StringBuilder longestCommonSubstringArray = new StringBuilder(Math.max(left.length(), right.length())); - final int[][] lcsLengthArray = longestCommonSubstringLengthArray(left, right); - int i = left.length() - 1; - int j = right.length() - 1; - int k = lcsLengthArray[left.length()][right.length()] - 1; - while (k >= 0) { - if (left.charAt(i) == right.charAt(j)) { - longestCommonSubstringArray.append(left.charAt(i)); - i = i - 1; - j = j - 1; - k = k - 1; - } else if (lcsLengthArray[i + 1][j] < lcsLengthArray[i][j + 1]) { - i = i - 1; - } else { - j = j - 1; - } - } - return longestCommonSubstringArray.reverse().toString(); + return longestCommonSubsequence(left, right); } + /** + * Computes the longest common subsequence between the two <code>CharSequence</code>'s passed as + * input. + * + * <p> + * Note, a substring and subsequence are not necessarily the same thing. Indeed, <code>abcxyzqrs</code> and + * <code>xyzghfm</code> have both the same common substring and subsequence, namely <code>xyz</code>. However, + * <code>axbyczqrs</code> and <code>abcxyzqtv</code> have the longest common subsequence <code>xyzq</code> because a + * subsequence need not have adjacent characters. + * </p> + * + * <p> + * For reference, we give the definition of a subsequence for the reader: a <i>subsequence</i> is a sequence that + * can be derived from another sequence by deleting some elements without changing the order of the remaining + * elements. + * </p> + * + * @param left first character sequence + * @param right second character sequence + * @return the longest common subsequence found + * @throws IllegalArgumentException + * if either String input {@code null} + */ + public CharSequence longestCommonSubsequence(final CharSequence left, final CharSequence right) { + // Quick return + if (left == null || right == null) { + throw new IllegalArgumentException("Inputs must not be null"); + } + final StringBuilder longestCommonSubstringArray = new StringBuilder(Math.max(left.length(), right.length())); + final int[][] lcsLengthArray = longestCommonSubstringLengthArray(left, right); + int i = left.length() - 1; + int j = right.length() - 1; + int k = lcsLengthArray[left.length()][right.length()] - 1; + while (k >= 0) { + if (left.charAt(i) == right.charAt(j)) { + longestCommonSubstringArray.append(left.charAt(i)); + i = i - 1; + j = j - 1; + k = k - 1; + } else if (lcsLengthArray[i + 1][j] < lcsLengthArray[i][j + 1]) { + i = i - 1; + } else { + j = j - 1; + } + } + return longestCommonSubstringArray.reverse().toString(); + } + /** * * Computes the lcsLengthArray for the sake of doing the actual lcs calculation. This is the http://git-wip-us.apache.org/repos/asf/commons-text/blob/804e4599/src/test/java/org/apache/commons/text/similarity/LongestCommonSubsequenceTest.java ---------------------------------------------------------------------- diff --git a/src/test/java/org/apache/commons/text/similarity/LongestCommonSubsequenceTest.java b/src/test/java/org/apache/commons/text/similarity/LongestCommonSubsequenceTest.java index 8019599..c8ad6a4 100644 --- a/src/test/java/org/apache/commons/text/similarity/LongestCommonSubsequenceTest.java +++ b/src/test/java/org/apache/commons/text/similarity/LongestCommonSubsequenceTest.java @@ -67,6 +67,39 @@ public class LongestCommonSubsequenceTest { @Test public void testLongestCommonSubsequence() { + assertEquals("", subject.longestCommonSubsequence("", "")); + assertEquals("", subject.longestCommonSubsequence("left", "")); + assertEquals("", subject.longestCommonSubsequence("", "right")); + assertEquals("fog", subject.longestCommonSubsequence("frog", "fog")); + assertEquals("", subject.longestCommonSubsequence("fly", "ant")); + assertEquals("h", subject.longestCommonSubsequence("elephant", "hippo")); + assertEquals("ABC Corp", subject.longestCommonSubsequence("ABC Corporation", "ABC Corp")); + assertEquals("D H Enterprises Inc", subject.longestCommonSubsequence("D N H Enterprises Inc", "D & H Enterprises, Inc.")); + assertEquals("My Gym Childrens Fitness", subject.longestCommonSubsequence("My Gym Children's Fitness Center", "My Gym. Childrens Fitness")); + assertEquals("PENNSYLVNIA", subject.longestCommonSubsequence("PENNSYLVANIA", "PENNCISYLVNIA")); + assertEquals("t", subject.longestCommonSubsequence("left", "right")); + assertEquals("tttt", subject.longestCommonSubsequence("leettteft", "ritttght")); + assertEquals("the same string", subject.longestCommonSubsequence("the same string", "the same string")); + } + + @Test(expected = IllegalArgumentException.class) + public void testGettingLongestCommonSubsequenceNullNull() throws Exception { + subject.longestCommonSubsequence(null, null); + } + + @Test(expected = IllegalArgumentException.class) + public void testGettingLongestCommonSubsequenceStringNull() throws Exception { + subject.longestCommonSubsequence(" ", null); + } + + @Test(expected = IllegalArgumentException.class) + public void testGettingLongestCommonSubsequenceNullString() throws Exception { + subject.longestCommonSubsequence(null, "right"); + } + + @Test + @Deprecated + public void testLogestCommonSubsequence() { assertEquals("", subject.logestCommonSubsequence("", "")); assertEquals("", subject.logestCommonSubsequence("left", "")); assertEquals("", subject.logestCommonSubsequence("", "right")); @@ -83,17 +116,20 @@ public class LongestCommonSubsequenceTest { } @Test(expected = IllegalArgumentException.class) - public void testGettingLongestCommonSubsequenceNullNull() throws Exception { + @Deprecated + public void testGettingLogestCommonSubsequenceNullNull() throws Exception { subject.logestCommonSubsequence(null, null); } @Test(expected = IllegalArgumentException.class) - public void testGettingLongestCommonSubsequenceStringNull() throws Exception { + @Deprecated + public void testGettingLogestCommonSubsequenceStringNull() throws Exception { subject.logestCommonSubsequence(" ", null); } @Test(expected = IllegalArgumentException.class) - public void testGettingLongestCommonSubsequenceNullString() throws Exception { + @Deprecated + public void testGettingLogestCommonSubsequenceNullString() throws Exception { subject.logestCommonSubsequence(null, "right"); } }
