You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@commons.apache.org by "Julius Davies (JIRA)" <ji...@apache.org> on 2008/05/17 06:49:56 UTC
[jira] Created: (COLLECTIONS-296) Introduce SortedUtils.merge() for
merging sorted collections
Introduce SortedUtils.merge() for merging sorted collections
------------------------------------------------------------
Key: COLLECTIONS-296
URL: https://issues.apache.org/jira/browse/COLLECTIONS-296
Project: Commons Collections
Issue Type: New Feature
Components: Core
Reporter: Julius Davies
Priority: Minor
Attachments: SortedUtils.patch
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(n) 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);
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (COLLECTIONS-296) Introduce SortedUtils.merge() for
merging sorted collections
Posted by "Julius Davies (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/COLLECTIONS-296?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Julius Davies updated COLLECTIONS-296:
--------------------------------------
Attachment: SortedUtils.patch
Here's a possible implementation with JUnit.
> Introduce SortedUtils.merge() for merging sorted collections
> ------------------------------------------------------------
>
> Key: COLLECTIONS-296
> URL: https://issues.apache.org/jira/browse/COLLECTIONS-296
> Project: Commons Collections
> Issue Type: New Feature
> Components: Core
> Reporter: Julius Davies
> Priority: Minor
> Attachments: SortedUtils.patch
>
>
> 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(n) 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);
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (COLLECTIONS-296) Introduce SortedUtils.merge()
for merging sorted collections
Posted by "Julien Aymé (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/COLLECTIONS-296?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12598300#action_12598300 ]
Julien Aymé commented on COLLECTIONS-296:
-----------------------------------------
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:
{code}
**
* 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);
{code}
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.
> Introduce SortedUtils.merge() for merging sorted collections
> ------------------------------------------------------------
>
> Key: COLLECTIONS-296
> URL: https://issues.apache.org/jira/browse/COLLECTIONS-296
> Project: Commons Collections
> Issue Type: New Feature
> Components: Core
> Reporter: Julius Davies
> Priority: Minor
> Attachments: SortedUtils.patch
>
>
> 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(n) 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);
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (COLLECTIONS-296) Introduce SortedUtils.merge()
for merging sorted collections
Posted by "Julius Davies (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/COLLECTIONS-296?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12598173#action_12598173 ]
Julius Davies commented on COLLECTIONS-296:
-------------------------------------------
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!
> Introduce SortedUtils.merge() for merging sorted collections
> ------------------------------------------------------------
>
> Key: COLLECTIONS-296
> URL: https://issues.apache.org/jira/browse/COLLECTIONS-296
> Project: Commons Collections
> Issue Type: New Feature
> Components: Core
> Reporter: Julius Davies
> Priority: Minor
> Attachments: SortedUtils.patch
>
>
> 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(n) 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);
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Issue Comment Edited: (COLLECTIONS-296) Introduce
SortedUtils.merge() for merging sorted collections
Posted by "Julien Aymé (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/COLLECTIONS-296?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12597924#action_12597924 ]
julien.ayme@gmail.com edited comment on COLLECTIONS-296 at 5/19/08 4:36 AM:
------------------------------------------------------------------
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:
{code}
/**
* 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) {
...
{code}
was (Author: julien.ayme@gmail.com):
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:
{code}
/**
* 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
{code}
> Introduce SortedUtils.merge() for merging sorted collections
> ------------------------------------------------------------
>
> Key: COLLECTIONS-296
> URL: https://issues.apache.org/jira/browse/COLLECTIONS-296
> Project: Commons Collections
> Issue Type: New Feature
> Components: Core
> Reporter: Julius Davies
> Priority: Minor
> Attachments: SortedUtils.patch
>
>
> 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(n) 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);
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (COLLECTIONS-296) Introduce SortedUtils.merge()
for merging sorted collections
Posted by "Julius Davies (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/COLLECTIONS-296?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12598778#action_12598778 ]
Julius Davies commented on COLLECTIONS-296:
-------------------------------------------
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]
> Introduce SortedUtils.merge() for merging sorted collections
> ------------------------------------------------------------
>
> Key: COLLECTIONS-296
> URL: https://issues.apache.org/jira/browse/COLLECTIONS-296
> Project: Commons Collections
> Issue Type: New Feature
> Components: Core
> Reporter: Julius Davies
> Priority: Minor
> Attachments: SortedUtils.patch
>
>
> 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(n) 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);
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (COLLECTIONS-296) Introduce SortedUtils.merge()
for merging sorted collections
Posted by "Julien Aymé (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/COLLECTIONS-296?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12597924#action_12597924 ]
Julien Aymé commented on COLLECTIONS-296:
-----------------------------------------
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:
{code}
/**
* 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
{code}
> Introduce SortedUtils.merge() for merging sorted collections
> ------------------------------------------------------------
>
> Key: COLLECTIONS-296
> URL: https://issues.apache.org/jira/browse/COLLECTIONS-296
> Project: Commons Collections
> Issue Type: New Feature
> Components: Core
> Reporter: Julius Davies
> Priority: Minor
> Attachments: SortedUtils.patch
>
>
> 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(n) 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);
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.