Open Source Support Tools
Home
|
Just Starting? View the Demo
|
Download Diagnostic Tools
|
Project Search
|
Tags
|
Help
|
About
(JavaScript Disabled)
 
Search Item
 
Summary
  Reported Issue
Title: [COLLECTIONS-296] Introduce SortedUtils.merge() for merging sorted collections
Project: collections
Item Last Modified: Wed, 21 May 2008 13:31:12 -0700 (PDT)
Tags:  
 
Tag This
 
Bookmark This
Bug add arraylist boolean capacity coll collection collections comparator elements empty implement implementation instanceof issorted javadoc junit linkedlist list method methods natural ordering patch proposed public put remove returning sorted src unresolved util
Details
[COLLECTIONS-296] Introduce SortedUtils.merge() for merging sorted collections
Reporter:   Julius Davies
Created:   Fri, 16 May 2008 21:48:50 -0700 (PDT)
Updated:   Wed, 21 May 2008 13:31:12 -0700 (PDT)
Key:   COLLECTIONS-296
Versions:   Not provided
Environment:  
Priority:   4
Status:   Open
Resolution:   Unresolved
Original Link:   http://issues.apache.org/jira/browse/COLLECTIONS-296
Summary:   Introduce SortedUtils.merge() for merging sorted collections
Description:
Is there any interest in this?

<p> /**</p>
<ul>
<li>Returns a new ArrayList where sorted Collection a and sorted Collection b</li>
<li>are combined such that ordering of the elements according to</li>
<li>Comparator c is retained. Uses the standard O<img class="emoticon" src="https://issues.apache.org/jira/images/icons/emoticons/thumbs_down.gif" height="19" width="19" align="absmiddle" alt="" border="0"/> merge algorithm</li>
<li>for combining two sorted lists.
*</li>
<li>@param a Object to combine with sorted Collection b. Must implement Comparable.</li>
<li>@param b Sorted Collection to combine with Object a.</li>
<li>@param c Comparator by which Collection a and Collection b have been sorted, or null</li>
<li>if the Collections are sorted according to their natural ordering.</li>
<li>@return a new sorted ArrayList
*/
public static ArrayList merge(Collection a, Collection b, Comparator c);</li>
</ul>
Comments:
juliusdavies Fri, 16 May 2008 21:49:35 -0700 (PDT)
Here's a possible implementation with JUnit.
julien ayme Mon, 19 May 2008 04:28:40 -0700 (PDT)
This method sounds interesting, but instead of sticking to ArrayList implementation, I would rather add a new parameter which would be the Collection to merge into:

/**
 * Merges the sorted Collections a and b into the empty Collection res
 * and return result.
 * 

 * The collections a and b are combined such that ordering of the elements according to
 * Comparator c is retained. Uses the standard O(n) merge algorithm for combining two sorted lists.
 *
 * @param a The first sorted Collection to merge
 * @param b The secong sorted Collection to merge
 * @param res an empty Collection to merge into
 * @param c Comparator by which Collection a and Collection b have been sorted, or null
 * if the Collections are sorted according to their natural ordering.
 * @return res in which the merge has been done
 */
public static Collection merge(Collection a, Collection b, Collection res, Comparator c) {
...
juliusdavies Mon, 19 May 2008 22:00:02 -0700 (PDT)
Thanks very much for the feedback! I worry that consumer won't properly initialize Collection "res" to the right capacity (a.size() + b.size()). Also, if the consumer wants to put the elements in a different collection, they can always use Collection.addAll() with the ArrayList that's returned.

Here are some more methods I'm thinking of adding:




boolean isSorted(Collection coll);
boolean isSorted(Collection coll, Comparator c);



int binarySearch(List l, Object o);
int binarySearch(List l, Object o, Comparator c);



There's another reason I like returning ArrayList: it can be easily fed into the binarySearch() method I'm thinking of adding. LinkedList can be fed into binarySearch, but it's a bad idea!
julien ayme Tue, 20 May 2008 06:46:24 -0700 (PDT)
You're right about the capacity initialization, I didn't think of it.
What I was thinking of when I proposed to supply the result Collection, was to remove duplicate entries by passing in a LinkedHashSet:
Indeed, one can think that the resulting collection of the merge will not contain dupes (since this is a possible definition of merge).

Maybe this can be specified in the javadoc, or even better, parametrized with a new boolean parameter, like this:



**
 * Merges the sorted Collections a and b.
 * 

 * The collections a and b are combined such that ordering of the elements according to
 * Comparator c is retained. Uses the standard O(n) merge algorithm for combining two sorted lists.
 *
 * @param a The first sorted Collection to merge
 * @param b The second sorted Collection to merge
 * @param c Comparator by which Collection a and Collection b have been sorted, or null
 * if the Collections are sorted according to their natural ordering.
 * @param ignoreDuplicateEntries flag which indicate if the resulting Collection should ignore duplicate entries
 * @return res in which the merge has been done
 */
public static List merge(Collection a, Collection b, Comparator c, boolean ignoreDuplicateEntries);




As for the binarySearch method, there is already a binarySearch in java.util.Collections which check if the list if an instanceof RandomAccess or not before doing the search.
juliusdavies Wed, 21 May 2008 13:31:12 -0700 (PDT)
I think the ignoreDups idea is excellent. I'll submit a newer patch incorporating that later tonight.

Thanks for the java.util.Collections.binarySearch() tip! I've been converting to Object[] and using Arrays.binarySearch() all these years! [blush]
URL: ../../collections/issues/296  •  Email URL