[jira] Created: (COLLECTIONS-296) Introduce SortedUtils.merge() for merging sorted collections

classic Classic list List threaded Threaded
7 messages Options
Reply | Threaded
Open this post in threaded view
|

[jira] Created: (COLLECTIONS-296) Introduce SortedUtils.merge() for merging sorted collections

JIRA jira@apache.org
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.

Reply | Threaded
Open this post in threaded view
|

[jira] Updated: (COLLECTIONS-296) Introduce SortedUtils.merge() for merging sorted collections

JIRA jira@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.

Reply | Threaded
Open this post in threaded view
|

[jira] Commented: (COLLECTIONS-296) Introduce SortedUtils.merge() for merging sorted collections

JIRA jira@apache.org
In reply to this post by JIRA jira@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.

Reply | Threaded
Open this post in threaded view
|

[jira] Issue Comment Edited: (COLLECTIONS-296) Introduce SortedUtils.merge() for merging sorted collections

JIRA jira@apache.org
In reply to this post by JIRA jira@apache.org

    [ https://issues.apache.org/jira/browse/COLLECTIONS-296?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12597924#action_12597924 ]

[hidden email] 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: [hidden email]):
    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.

Reply | Threaded
Open this post in threaded view
|

[jira] Commented: (COLLECTIONS-296) Introduce SortedUtils.merge() for merging sorted collections

JIRA jira@apache.org
In reply to this post by JIRA jira@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.

Reply | Threaded
Open this post in threaded view
|

[jira] Commented: (COLLECTIONS-296) Introduce SortedUtils.merge() for merging sorted collections

JIRA jira@apache.org
In reply to this post by JIRA jira@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.

Reply | Threaded
Open this post in threaded view
|

[jira] Commented: (COLLECTIONS-296) Introduce SortedUtils.merge() for merging sorted collections

JIRA jira@apache.org
In reply to this post by JIRA jira@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.