Author: tn Date: Thu Apr 18 21:06:40 2013 New Revision: 1469577 URL: http://svn.apache.org/r1469577 Log: [COLLECTIONS-296] Added CollectionUtils#merge methods to merge two sorted Collections. Thanks to Julius Davies for the report and patch.
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=1469577&r1=1469576&r2=1469577&view=diff ============================================================================== --- commons/proper/collections/trunk/src/changes/changes.xml (original) +++ commons/proper/collections/trunk/src/changes/changes.xml Thu Apr 18 21:06:40 2013 @@ -22,6 +22,10 @@ <body> <release version="4.0" date="TBA" description="Next release"> + <action issue="COLLECTIONS-296" dev="tn" type="add" due-to="Julius Davies"> + Added methods "CollectionUtils#merge(...)" to merge two sorted Collections + into a sorted List using the standard O(n) merge algorithm. + </action> <action issue="COLLECTIONS-429,COLLECTION-434" dev="tn" type="add" due-to="Adrian Nistor, Mert Guldur"> Added method "CollectionUtils#containsAll(Collection, Collection)" with guaranteed runtime complexity of O(n + m) and space complexity of O(n). This method may yield much 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=1469577&r1=1469576&r2=1469577&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 Thu Apr 18 21:06:40 2013 @@ -19,6 +19,7 @@ package org.apache.commons.collections4; import java.lang.reflect.Array; import java.util.ArrayList; import java.util.Collection; +import java.util.Comparator; import java.util.Enumeration; import java.util.HashMap; import java.util.HashSet; @@ -1440,6 +1441,152 @@ public class CollectionUtils { //----------------------------------------------------------------------- /** + * Merges two sorted Collections, a and b, into a single, sorted List + * such that the natural ordering of the elements is retained. + * <p> + * Uses the standard O(n) merge algorithm for combining two sorted lists. + * + * @param <O> the element type + * @param a the first collection, must not be null + * @param b the second collection, must not be null + * @return a new sorted List, containing the elements of Collection a and b + * @throws IllegalArgumentException if either collection is null + */ + 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); + } + + /** + /** + * Merges two sorted Collections, a and b, into a single, sorted List + * such that the natural ordering of the elements is retained. + * <p> + * Uses the standard O(n) merge algorithm for combining two sorted lists. + * + * @param <O> the element type + * @param a the first collection, must not be null + * @param b the second collection, must not be null + * @param includeDuplicates if {@code true} duplicate elements will be retained, otherwise + * they will be removed in the output collection + * @return a new sorted List, containing the elements of Collection a and b + * @throws IllegalArgumentException if either collection is null + */ + 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); + } + + /** + * Merges two sorted Collections, a and b, into a single, sorted List + * such that the ordering of the elements according to Comparator c is retained. + * <p> + * Uses the standard O(n) merge algorithm for combining two sorted lists. + * + * @param <O> the element type + * @param a the first collection, must not be null + * @param b the second collection, must not be null + * @param c the comparator to use for the merge. + * @return a new sorted List, containing the elements of Collection a and b + * @throws IllegalArgumentException if either collection or the comparator is null + */ + 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); + } + + /** + * Merges two sorted Collections, a and b, into a single, sorted List + * such that the ordering of the elements according to Comparator c is retained. + * <p> + * Uses the standard O(n) merge algorithm for combining two sorted lists. + * + * @param <O> the element type + * @param a the first collection, must not be null + * @param b the second collection, must not be null + * @param c the comparator to use for the merge. + * @param includeDuplicates if {@code true} duplicate elements will be retained, otherwise + * they will be removed in the output collection + * @return a new sorted List, containing the elements of Collection a and b + * @throws IllegalArgumentException if either collection or the comparator is null + */ + public static <O> List<O> merge(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"); + } + if (c == null) { + 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 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; + } + } 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; + } + } + } + + // 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 + */ + 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; + } + } + + //----------------------------------------------------------------------- + /** * Returns a collection containing all the elements in <code>collection</code> * that are also in <code>retain</code>. The cardinality of an element <code>e</code> * in the returned collection is the same as the cardinality of <code>e</code> 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=1469577&r1=1469576&r2=1469577&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 Thu Apr 18 21:06:40 2013 @@ -71,6 +71,16 @@ public class CollectionUtilsTest extends private Collection<Integer> collectionC = null; /** + * Sorted Collection of {@link Integer}s + */ + private Collection<Integer> collectionD = null; + + /** + * Sorted Collection of {@link Integer}s + */ + private Collection<Integer> collectionE = null; + + /** * Collection of {@link Integer}s, bound as {@link Number}s */ private Collection<Number> collectionA2 = null; @@ -96,6 +106,8 @@ public class CollectionUtilsTest extends private Iterable<Number> iterableB2 = null; + private Collection<Integer> emptyCollection = new ArrayList<Integer>(1); + @Before public void setUp() { collectionA = new ArrayList<Integer>(); @@ -134,6 +146,25 @@ public class CollectionUtilsTest extends collectionC2 = new LinkedList<Number>(collectionC); iterableA2 = collectionA2; iterableB2 = collectionB2; + + collectionD = new ArrayList<Integer>(); + collectionD.add(1); + collectionD.add(3); + collectionD.add(3); + collectionD.add(3); + collectionD.add(5); + collectionD.add(7); + collectionD.add(7); + collectionD.add(10); + + collectionE = new ArrayList<Integer>(); + collectionE.add(2); + collectionE.add(4); + collectionE.add(4); + collectionE.add(5); + collectionE.add(6); + collectionE.add(6); + collectionE.add(9); } @Test @@ -1553,4 +1584,65 @@ public class CollectionUtilsTest extends expect(iterator.hasNext()).andReturn(true); expect(iterator.next()).andReturn(t); } + + @Test(expected=IllegalArgumentException.class) + public void mergeException1() { + CollectionUtils.merge(collectionA, null); + } + + @Test(expected=IllegalArgumentException.class) + public void mergeException2() { + CollectionUtils.merge(collectionA, collectionC, null); + } + + @Test + public void testMerge() { + List<Integer> result = CollectionUtils.merge(emptyCollection, emptyCollection); + assertEquals("Merge empty with empty", 0, result.size()); + + result = CollectionUtils.merge(collectionA, emptyCollection); + assertEquals("Merge empty with non-empty", collectionA, result); + + List<Integer> result1 = CollectionUtils.merge(collectionD, collectionE); + List<Integer> result2 = CollectionUtils.merge(collectionE, collectionD); + assertEquals("Merge two lists 1", result1, result2); + + List<Integer> combinedList = new ArrayList<Integer>(); + combinedList.addAll(collectionD); + combinedList.addAll(collectionE); + Collections.sort(combinedList); + + assertEquals("Merge two lists 2", combinedList, result2); + + final Comparator<Integer> reverseComparator = + ComparatorUtils.reversedComparator(ComparatorUtils.<Integer>naturalComparator()); + + result = CollectionUtils.merge(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); + 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); + assertEquals("Merge two lists 1 - ignore duplicates", result1, result2); + + Set<Integer> combinedSet = new HashSet<Integer>(); + combinedSet.addAll(collectionD); + combinedSet.addAll(collectionE); + List<Integer> combinedList = new ArrayList<Integer>(combinedSet); + Collections.sort(combinedList); + + assertEquals("Merge two lists 2 - ignore duplicates", combinedList, result2); + } + }