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/28 15:58:37 UTC
svn commit: r1476770 - in /commons/proper/collections/trunk/src:
changes/changes.xml
main/java/org/apache/commons/collections4/CollectionUtils.java
test/java/org/apache/commons/collections4/CollectionUtilsTest.java
Author: tn
Date: Sun Apr 28 13:58:37 2013
New Revision: 1476770
URL: http://svn.apache.org/r1476770
Log:
[COLLECTIONS-296] Renamed CollectionUtils.merge to collate, simplify implementation by using a CollatingIterator.
Modified:
commons/proper/collections/trunk/src/changes/changes.xml
commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/CollectionUtils.java
commons/proper/collections/trunk/src/test/java/org/apache/commons/collections4/CollectionUtilsTest.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=1476770&r1=1476769&r2=1476770&view=diff
==============================================================================
--- commons/proper/collections/trunk/src/changes/changes.xml (original)
+++ commons/proper/collections/trunk/src/changes/changes.xml Sun Apr 28 13:58:37 2013
@@ -298,7 +298,7 @@
Calling "CollectionUtils#sizeIsEmpty(null)" will now return true.
</action>
<action issue="COLLECTIONS-296" dev="tn" type="add" due-to="Julius Davies">
- Added methods "CollectionUtils#merge(...)" to merge two sorted Collections
+ Added methods "CollectionUtils#collate(...)" to merge two sorted Collections
into a sorted List using the standard O(n) merge algorithm.
</action>
<action issue="COLLECTIONS-294" dev="bayard" type="fix" due-to="Benjamin Bentmann">
Modified: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/CollectionUtils.java
URL: http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/CollectionUtils.java?rev=1476770&r1=1476769&r2=1476770&view=diff
==============================================================================
--- commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/CollectionUtils.java (original)
+++ commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/CollectionUtils.java Sun Apr 28 13:58:37 2013
@@ -38,6 +38,7 @@ import org.apache.commons.collections4.c
import org.apache.commons.collections4.collection.UnmodifiableCollection;
import org.apache.commons.collections4.functors.Equator;
import org.apache.commons.collections4.functors.TruePredicate;
+import org.apache.commons.collections4.iterators.CollatingIterator;
import org.apache.commons.collections4.iterators.PermutationIterator;
/**
@@ -1498,9 +1499,9 @@ public class CollectionUtils {
* @throws IllegalArgumentException if either collection is null
* @since 4.0
*/
- public static <O extends Comparable<? super O>> List<O> merge(Collection<? extends O> a,
- Collection<? extends O> b) {
- return merge(a, b, ComparatorUtils.<O>naturalComparator(), true);
+ public static <O extends Comparable<? super O>> List<O> collate(Collection<? extends O> a,
+ Collection<? extends O> b) {
+ return collate(a, b, ComparatorUtils.<O>naturalComparator(), true);
}
/**
@@ -1519,10 +1520,10 @@ public class CollectionUtils {
* @throws IllegalArgumentException if either collection is null
* @since 4.0
*/
- public static <O extends Comparable<? super O>> List<O> merge(final Collection<? extends O> a,
- final Collection<? extends O> b,
- final boolean includeDuplicates) {
- return merge(a, b, ComparatorUtils.<O>naturalComparator(), includeDuplicates);
+ public static <O extends Comparable<? super O>> List<O> collate(final Collection<? extends O> a,
+ final Collection<? extends O> b,
+ final boolean includeDuplicates) {
+ return collate(a, b, ComparatorUtils.<O>naturalComparator(), includeDuplicates);
}
/**
@@ -1539,9 +1540,9 @@ public class CollectionUtils {
* @throws IllegalArgumentException if either collection or the comparator is null
* @since 4.0
*/
- public static <O> List<O> merge(final Collection<? extends O> a, final Collection<? extends O> b,
- final Comparator<? super O> c) {
- return merge(a, b, c, true);
+ public static <O> List<O> collate(final Collection<? extends O> a, final Collection<? extends O> b,
+ final Comparator<? super O> c) {
+ return collate(a, b, c, true);
}
/**
@@ -1560,8 +1561,8 @@ public class CollectionUtils {
* @throws IllegalArgumentException if either collection or the comparator is null
* @since 4.0
*/
- public static <O> List<O> merge(final Collection<? extends O> a, final Collection<? extends O> b,
- final Comparator<? super O> c, final boolean includeDuplicates) {
+ public static <O> List<O> collate(final Collection<? extends O> a, final Collection<? extends O> b,
+ final Comparator<? super O> c, final boolean includeDuplicates) {
if (a == null || b == null) {
throw new IllegalArgumentException("The collections must not be null");
@@ -1570,68 +1571,24 @@ public class CollectionUtils {
throw new IllegalArgumentException("The comparator must not be null");
}
- final List<O> mergedList = new ArrayList<O>(a.size() + b.size());
-
- // if either collection is empty, just return the other one
- if (a.isEmpty() || b.isEmpty()) {
- mergedList.addAll(a.isEmpty() ? b : a);
- return mergedList;
- }
+ final int totalSize = Math.max(1, a.size() + b.size());
+ final Iterator<O> iterator = new CollatingIterator<O>(c, a.iterator(), b.iterator());
+ if (includeDuplicates) {
+ return IteratorUtils.toList(iterator, totalSize);
+ } else {
+ final ArrayList<O> mergedList = new ArrayList<O>(totalSize);
- final Iterator<? extends O> it1 = a.iterator();
- final Iterator<? extends O> it2 = b.iterator();
- O o1 = it1.next();
- O o2 = it2.next();
- O last = null;
- while (true) {
- final int x = c.compare(o1, o2);
- if (x <= 0) {
- last = addItemToList(o1, mergedList, last, includeDuplicates);
- if (it1.hasNext()) {
- o1 = it1.next();
- } else {
- // a is empty, so add current element of b
- last = addItemToList(o2, mergedList, last, includeDuplicates);
- break;
+ O lastItem = null;
+ while (iterator.hasNext()) {
+ final O item = iterator.next();
+ if (lastItem == null || !lastItem.equals(item)) {
+ mergedList.add(item);
}
- } else {
- last = addItemToList(o2, mergedList, last, includeDuplicates);
- if (it2.hasNext()) {
- o2 = it2.next();
- } else {
- // b is empty, so add current element of a
- last = addItemToList(o1, mergedList, last, includeDuplicates);
- break;
- }
+ lastItem = item;
}
- }
-
- // add the remaining elements from the non-empty iterator
- final Iterator<? extends O> it = it1.hasNext() ? it1 : it2;
- while (it.hasNext()) {
- last = addItemToList(it.next(), mergedList, last, includeDuplicates);
- }
-
- return mergedList;
- }
- /**
- * Adds an item to the specified list.
- *
- * @param item the item to add
- * @param list the list to use
- * @param lastItem the last added item, may be null
- * @param includeDuplicates whether duplicate entries are allowed
- * @return the last added item
- * @since 4.0
- */
- private static <E> E addItemToList(final E item, final List<E> list, final E lastItem,
- final boolean includeDuplicates) {
- if (includeDuplicates || lastItem == null || !lastItem.equals(item)) {
- list.add(item);
- return item;
- } else {
- return lastItem;
+ mergedList.trimToSize();
+ return mergedList;
}
}
Modified: commons/proper/collections/trunk/src/test/java/org/apache/commons/collections4/CollectionUtilsTest.java
URL: http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/test/java/org/apache/commons/collections4/CollectionUtilsTest.java?rev=1476770&r1=1476769&r2=1476770&view=diff
==============================================================================
--- commons/proper/collections/trunk/src/test/java/org/apache/commons/collections4/CollectionUtilsTest.java (original)
+++ commons/proper/collections/trunk/src/test/java/org/apache/commons/collections4/CollectionUtilsTest.java Sun Apr 28 13:58:37 2013
@@ -1640,25 +1640,25 @@ public class CollectionUtilsTest extends
}
@Test(expected=IllegalArgumentException.class)
- public void mergeException1() {
- CollectionUtils.merge(collectionA, null);
+ public void collateException1() {
+ CollectionUtils.collate(collectionA, null);
}
@Test(expected=IllegalArgumentException.class)
- public void mergeException2() {
- CollectionUtils.merge(collectionA, collectionC, null);
+ public void collateException2() {
+ CollectionUtils.collate(collectionA, collectionC, null);
}
@Test
- public void testMerge() {
- List<Integer> result = CollectionUtils.merge(emptyCollection, emptyCollection);
+ public void testCollate() {
+ List<Integer> result = CollectionUtils.collate(emptyCollection, emptyCollection);
assertEquals("Merge empty with empty", 0, result.size());
- result = CollectionUtils.merge(collectionA, emptyCollection);
+ result = CollectionUtils.collate(collectionA, emptyCollection);
assertEquals("Merge empty with non-empty", collectionA, result);
- List<Integer> result1 = CollectionUtils.merge(collectionD, collectionE);
- List<Integer> result2 = CollectionUtils.merge(collectionE, collectionD);
+ List<Integer> result1 = CollectionUtils.collate(collectionD, collectionE);
+ List<Integer> result2 = CollectionUtils.collate(collectionE, collectionD);
assertEquals("Merge two lists 1", result1, result2);
List<Integer> combinedList = new ArrayList<Integer>();
@@ -1671,23 +1671,23 @@ public class CollectionUtilsTest extends
final Comparator<Integer> reverseComparator =
ComparatorUtils.reversedComparator(ComparatorUtils.<Integer>naturalComparator());
- result = CollectionUtils.merge(emptyCollection, emptyCollection, reverseComparator);
+ result = CollectionUtils.collate(emptyCollection, emptyCollection, reverseComparator);
assertEquals("Comparator Merge empty with empty", 0, result.size());
Collections.reverse((List<Integer>) collectionD);
Collections.reverse((List<Integer>) collectionE);
Collections.reverse(combinedList);
- result1 = CollectionUtils.merge(collectionD, collectionE, reverseComparator);
- result2 = CollectionUtils.merge(collectionE, collectionD, reverseComparator);
+ result1 = CollectionUtils.collate(collectionD, collectionE, reverseComparator);
+ result2 = CollectionUtils.collate(collectionE, collectionD, reverseComparator);
assertEquals("Comparator Merge two lists 1", result1, result2);
assertEquals("Comparator Merge two lists 2", combinedList, result2);
}
@Test
- public void testMergeIgnoreDuplicates() {
- List<Integer> result1 = CollectionUtils.merge(collectionD, collectionE, false);
- List<Integer> result2 = CollectionUtils.merge(collectionE, collectionD, false);
+ public void testCollateIgnoreDuplicates() {
+ List<Integer> result1 = CollectionUtils.collate(collectionD, collectionE, false);
+ List<Integer> result2 = CollectionUtils.collate(collectionE, collectionD, false);
assertEquals("Merge two lists 1 - ignore duplicates", result1, result2);
Set<Integer> combinedSet = new HashSet<Integer>();