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/30 11:05:43 UTC
svn commit: r1477515 - 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: Tue Apr 30 09:05:43 2013
New Revision: 1477515
URL: http://svn.apache.org/r1477515
Log:
[COLLECTIONS-456] Added additional overrides for providing an Equator, as well as for CharSequences.
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=1477515&r1=1477514&r2=1477515&view=diff
==============================================================================
--- commons/proper/collections/trunk/src/changes/changes.xml (original)
+++ commons/proper/collections/trunk/src/changes/changes.xml Tue Apr 30 09:05:43 2013
@@ -22,11 +22,12 @@
<body>
<release version="4.0" date="TBA" description="Next release">
- <action issue="COLLECTIONS-458" dev="tn" type="delete">
- AbstractUntypedCollectionDecorator<E, D> is not used.
+ <action issue="COLLECTIONS-458" dev="sebb" type="remove">
+ "AbstractUntypedCollectionDecorator<E, D>" is not used.
</action>
<action issue="COLLECTIONS-456" dev="tn" type="add">
- Added method "ListUtils#longestCommonSubsequence(List, List)".
+ Added methods "ListUtils#longestCommonSubsequence(...)" to get the longest common subsequence
+ of arbitrary lists or CharSequences.
</action>
<action issue="COLLECTIONS-454" dev="tn" type="update">
An iterator over a "Flat3Map#entrySet()" will now return
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=1477515&r1=1477514&r2=1477515&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 Tue Apr 30 09:05:43 2013
@@ -25,6 +25,8 @@ import java.util.Iterator;
import java.util.List;
import org.apache.commons.collections4.bag.HashBag;
+import org.apache.commons.collections4.functors.DefaultEquator;
+import org.apache.commons.collections4.functors.Equator;
import org.apache.commons.collections4.list.FixedSizeList;
import org.apache.commons.collections4.list.LazyList;
import org.apache.commons.collections4.list.PredicatedList;
@@ -520,26 +522,67 @@ public class ListUtils {
/**
* Returns the longest common subsequence (LCS) of two sequences (lists).
*
- * @param <T> the element type
+ * @param <E> 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) {
+ public static <E> List<E> longestCommonSubsequence(final List<E> a, final List<E> b) {
+ return longestCommonSubsequence( a, b, DefaultEquator.defaultEquator() );
+ }
+
+ /**
+ * Returns the longest common subsequence (LCS) of two sequences (lists).
+ *
+ * @param <E> the element type
+ * @param a the first list
+ * @param b the second list
+ * @return the longest common subsequence
+ * @throws IllegalArgumentException if either list or the equator is {@code null}
+ * @since 4.0
+ */
+ public static <E> List<E> longestCommonSubsequence(final List<E> a, final List<E> b, final Equator<? super E> equator) {
if (a == null || b == null) {
throw new IllegalArgumentException("List must not be null");
}
+ if (equator == null) {
+ throw new IllegalArgumentException("Equator 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>();
+ final SequencesComparator<E> comparator = new SequencesComparator<E>(a, b, equator);
+ final EditScript<E> script = comparator.getScript();
+ final LcsVisitor<E> visitor = new LcsVisitor<E>();
script.visit(visitor);
return visitor.getSubSequence();
}
/**
+ * Returns the longest common subsequence (LCS) of two {@link CharSequence} objects.
+ * <p>
+ * This is a convenience method for using {@link #longestCommonSubsequence(List, List)}
+ * with {@link CharSequence} instances.
+ *
+ * @param a the first sequence
+ * @param b the second sequence
+ * @return the longest common subsequence as {@link String}
+ * @throws IllegalArgumentException if either sequence is {@code null}
+ * @since 4.0
+ */
+ public static String longestCommonSubsequence(final CharSequence a, final CharSequence b) {
+ if (a == null || b == null) {
+ throw new IllegalArgumentException("CharSequence must not be null");
+ }
+ final List<Character> lcs = longestCommonSubsequence(new CharSequenceAsList( a ), new CharSequenceAsList( b ));
+ final StringBuilder sb = new StringBuilder();
+ for ( Character ch : lcs ) {
+ sb.append(ch);
+ }
+ return sb.toString();
+ }
+
+ /**
* A helper class used to construct the longest common subsequence.
*/
private static final class LcsVisitor<E> implements CommandVisitor<E> {
@@ -562,6 +605,29 @@ public class ListUtils {
}
}
+ /**
+ * A simple wrapper to use a CharSequence as List.
+ */
+ private static final class CharSequenceAsList extends AbstractList<Character> {
+
+ private final CharSequence sequence;
+
+ public CharSequenceAsList(final CharSequence sequence) {
+ this.sequence = sequence;
+ }
+
+ @Override
+ public Character get( int index ) {
+ return sequence.charAt( index );
+ }
+
+ @Override
+ public int size() {
+ return sequence.length();
+ }
+
+ }
+
//-----------------------------------------------------------------------
/**
* Returns consecutive {@link List#subList(int, int) sublists} of a
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=1477515&r1=1477514&r2=1477515&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 Tue Apr 30 09:05:43 2013
@@ -31,7 +31,6 @@ 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.
@@ -315,7 +314,7 @@ public class ListUtilsTest extends BulkT
public void testLongestCommonSubsequence() {
try {
- ListUtils.longestCommonSubsequence(null, null);
+ ListUtils.longestCommonSubsequence((List<?>) null, null);
fail("failed to check for null argument");
} catch (final IllegalArgumentException e) {}
@@ -351,7 +350,44 @@ public class ListUtilsTest extends BulkT
assertTrue(lcs.isEmpty());
}
-
+
+ public void testLongestCommonSubsequenceWithString() {
+
+ try {
+ ListUtils.longestCommonSubsequence((String) null, null);
+ fail("failed to check for null argument");
+ } catch (final IllegalArgumentException e) {}
+
+ try {
+ ListUtils.longestCommonSubsequence("A", null);
+ fail("failed to check for null argument");
+ } catch (final IllegalArgumentException e) {}
+
+ try {
+ ListUtils.longestCommonSubsequence(null, "A");
+ fail("failed to check for null argument");
+ } catch (final IllegalArgumentException e) {}
+
+ String lcs = ListUtils.longestCommonSubsequence("", "");
+ assertTrue(lcs.isEmpty());
+
+ String banana = "BANANA";
+ String ananas = "ANANAS";
+ lcs = ListUtils.longestCommonSubsequence(banana, ananas);
+
+ assertEquals("ANANA", lcs);
+
+ String atana = "ATANA";
+ lcs = ListUtils.longestCommonSubsequence(banana, atana);
+
+ assertEquals("AANA", lcs);
+
+ String zorro = "ZORRO";
+ lcs = ListUtils.longestCommonSubsequence(banana, zorro);
+
+ assertTrue(lcs.isEmpty());
+ }
+
public void testPartition() {
final List<Integer> strings = new ArrayList<Integer>();
for (int i = 0; i <= 6; i++) {