commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From t.@apache.org
Subject svn commit: r1469577 - 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
Date Thu, 18 Apr 2013 21:06:40 GMT
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);
+    }
+    
 }



Mime
View raw message