You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by tn...@apache.org on 2013/04/29 22:08:47 UTC
svn commit: r1477312 - in /commons/proper/collections/trunk/src:
changes/changes.xml main/java/org/apache/commons/collections4/ListUtils.java
test/java/org/apache/commons/collections4/ListUtilsTest.java
Author: tn
Date: Mon Apr 29 20:08:46 2013
New Revision: 1477312
URL: http://svn.apache.org/r1477312
Log:
[COLLECTIONS-456] Added ListUtils.longestCommonSubsequence(List, List).
Modified:
commons/proper/collections/trunk/src/changes/changes.xml
commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/ListUtils.java
commons/proper/collections/trunk/src/test/java/org/apache/commons/collections4/ListUtilsTest.java
Modified: commons/proper/collections/trunk/src/changes/changes.xml
URL: http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/changes/changes.xml?rev=1477312&r1=1477311&r2=1477312&view=diff
==============================================================================
--- commons/proper/collections/trunk/src/changes/changes.xml (original)
+++ commons/proper/collections/trunk/src/changes/changes.xml Mon Apr 29 20:08:46 2013
@@ -22,6 +22,9 @@
<body>
<release version="4.0" date="TBA" description="Next release">
+ <action issue="COLLECTIONS-456" dev="tn" type="add">
+ Added method "ListUtils#longestCommonSubsequence(List, List)".
+ </action>
<action issue="COLLECTIONS-454" dev="tn" type="update">
An iterator over a "Flat3Map#entrySet()" will now return
independent Map.Entry objects that will not change anymore when
@@ -135,7 +138,7 @@
</action>
<action issue="COLLECTIONS-404" dev="luc" type="add" due-to="Jordane Sarda">
Added an implementation of Eugene Myers difference algorithm in package
- o.a.c.c.comparators.sequence.
+ o.a.c.c.sequence.
</action>
<action issue="COLLECTIONS-400" dev="tn" type="fix" due-to="Shin Hwei Tan">
Added missing null check in "CollectionUtils#addIgnoreNull(Collection, Object)".
Modified: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/ListUtils.java
URL: http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/ListUtils.java?rev=1477312&r1=1477311&r2=1477312&view=diff
==============================================================================
--- commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/ListUtils.java (original)
+++ commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/ListUtils.java Mon Apr 29 20:08:46 2013
@@ -30,6 +30,9 @@ import org.apache.commons.collections4.l
import org.apache.commons.collections4.list.PredicatedList;
import org.apache.commons.collections4.list.TransformedList;
import org.apache.commons.collections4.list.UnmodifiableList;
+import org.apache.commons.collections4.sequence.CommandVisitor;
+import org.apache.commons.collections4.sequence.EditScript;
+import org.apache.commons.collections4.sequence.SequencesComparator;
/**
* Provides utility methods and decorators for {@link List} instances.
@@ -489,6 +492,7 @@ public class ListUtils {
return FixedSizeList.fixedSizeList(list);
}
+ //-----------------------------------------------------------------------
/**
* Finds the first index in the given List which matches the given predicate.
* <p>
@@ -512,6 +516,53 @@ public class ListUtils {
return -1;
}
+ //-----------------------------------------------------------------------
+ /**
+ * Returns the longest common subsequence (LCS) of two sequences (lists).
+ *
+ * @param <T> the element type
+ * @param a the first list
+ * @param b the second list
+ * @return the longest common subsequence
+ * @throws IllegalArgumentException if either list is {@code null}
+ * @since 4.0
+ */
+ public static <T> List<T> longestCommonSubsequence(final List<T> a, final List<T> b) {
+ if (a == null || b == null) {
+ throw new IllegalArgumentException("List must not be null");
+ }
+
+ final SequencesComparator<T> comparator = new SequencesComparator<T>(a, b);
+ final EditScript<T> script = comparator.getScript();
+ final LcsVisitor<T> visitor = new LcsVisitor<T>();
+ script.visit(visitor);
+ return visitor.getSubSequence();
+ }
+
+ /**
+ * A helper class used to construct the longest common subsequence.
+ */
+ private static final class LcsVisitor<E> implements CommandVisitor<E> {
+ private ArrayList<E> sequence;
+
+ public LcsVisitor() {
+ sequence = new ArrayList<E>();
+ }
+
+ public void visitInsertCommand(final E object) {}
+
+ public void visitDeleteCommand(final E object) {}
+
+ public void visitKeepCommand(final E object) {
+ sequence.add(object);
+ }
+
+ public List<E> getSubSequence() {
+ return sequence;
+ }
+ }
+
+ //-----------------------------------------------------------------------
/**
* Returns consecutive {@link List#subList(int, int) sublists} of a
* list, each of the same size (the final list may be smaller). For example,
Modified: commons/proper/collections/trunk/src/test/java/org/apache/commons/collections4/ListUtilsTest.java
URL: http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/test/java/org/apache/commons/collections4/ListUtilsTest.java?rev=1477312&r1=1477311&r2=1477312&view=diff
==============================================================================
--- commons/proper/collections/trunk/src/test/java/org/apache/commons/collections4/ListUtilsTest.java (original)
+++ commons/proper/collections/trunk/src/test/java/org/apache/commons/collections4/ListUtilsTest.java Mon Apr 29 20:08:46 2013
@@ -31,6 +31,7 @@ import org.apache.commons.collections4.L
import org.apache.commons.collections4.Predicate;
import org.apache.commons.collections4.functors.EqualPredicate;
import org.apache.commons.collections4.list.PredicatedList;
+import org.junit.Assert;
/**
* Tests for ListUtils.
@@ -311,6 +312,46 @@ public class ListUtilsTest extends BulkT
assertEquals(ListUtils.indexOf(fullList, null), -1);
}
+ public void testLongestCommonSubsequence() {
+
+ try {
+ ListUtils.longestCommonSubsequence(null, null);
+ fail("failed to check for null argument");
+ } catch (final IllegalArgumentException e) {}
+
+ try {
+ ListUtils.longestCommonSubsequence(Arrays.asList('A'), null);
+ fail("failed to check for null argument");
+ } catch (final IllegalArgumentException e) {}
+
+ try {
+ ListUtils.longestCommonSubsequence(null, Arrays.asList('A'));
+ fail("failed to check for null argument");
+ } catch (final IllegalArgumentException e) {}
+
+ @SuppressWarnings("unchecked")
+ List<Character> lcs = ListUtils.longestCommonSubsequence(Collections.EMPTY_LIST, Collections.EMPTY_LIST);
+ assertTrue(lcs.isEmpty());
+
+ List<Character> list1 = Arrays.asList('B', 'A', 'N', 'A', 'N', 'A');
+ List<Character> list2 = Arrays.asList('A', 'N', 'A', 'N', 'A', 'S');
+ lcs = ListUtils.longestCommonSubsequence(list1, list2);
+
+ List<Character> expected = Arrays.asList('A', 'N', 'A', 'N', 'A');
+ assertEquals(expected, lcs);
+
+ List<Character> list3 = Arrays.asList('A', 'T', 'A', 'N', 'A');
+ lcs = ListUtils.longestCommonSubsequence(list1, list3);
+
+ expected = Arrays.asList('A', 'A', 'N', 'A');
+ assertEquals(expected, lcs);
+
+ List<Character> listZorro = Arrays.asList('Z', 'O', 'R', 'R', 'O');
+ lcs = ListUtils.longestCommonSubsequence(list1, listZorro);
+
+ assertTrue(lcs.isEmpty());
+ }
+
public void testPartition() {
final List<Integer> strings = new ArrayList<Integer>();
for (int i = 0; i <= 6; i++) {