commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From t.@apache.org
Subject 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
Date Sun, 28 Apr 2013 13:58:37 GMT
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>();



Mime
View raw message