Introduce SortedUtils.merge() for merging sorted collections

• Key: COLLECTIONS-296
• Type: New Feature
• Status: Open
• Priority: Minor
• Assignee: Unassigned
• Reporter: Julius Davies
• Component/s: Core

Description

Is there any interest in this?

/**

• Returns a new ArrayList where sorted Collection a and sorted Collection b
• are combined such that ordering of the elements according to
• Comparator c is retained. Uses the standard O merge algorithm
• for combining two sorted lists.
  *
• @param a Object to combine with sorted Collection b. Must implement Comparable.
• @param b Sorted Collection to combine with Object a.
• @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 a new sorted ArrayList
  */
  public static ArrayList merge(Collection a, Collection b, Comparator c);

Comments

Here's a possible implementation with JUnit.

[Julien Aymé]

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.
 * <p>
 * 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) {
...

[Julius Davies]

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:

<code>
boolean isSorted(Collection coll);
boolean isSorted(Collection coll, Comparator c);

int binarySearch(List l, Object o);
int binarySearch(List l, Object o, Comparator c);
</code>

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 Aymé]

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.
 * <p>
 * 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.

[Julius Davies]

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]