Copying collection without duplicates

Discussion in 'Java' started by Karsten Wutzke, Aug 10, 2007.

  1. Hello!

    I have the following method overriding Collection.addAll:

    @Override
    public boolean addAll(int index, Collection<? extends E> cln)
    {
    if ( containsAll(cln) )
    {
    return false;
    }

    //build list without dupes (always)
    ArrayList<E> al = new ArrayList<E>(cln.size());

    Iterator<? extends E> itr = cln.iterator();

    while ( itr.hasNext() )
    {
    E elem = itr.next();

    if ( !contains(elem) )
    {
    al.add(elem);
    }
    }

    cln = al;

    //allows dupes and nulls
    return super.addAll(index, cln);
    }

    Is there any faster way without overriding other methods?

    Karsten
     
    Karsten Wutzke, Aug 10, 2007
    #1
    1. Advertising

  2. Karsten Wutzke

    Roedy Green Guest

    >Is there any faster way without overriding other methods?

    To dedup, sort and then compare elt with prev, in one pass. You can
    then use Iterator.remove or copy non-dups to a new List.
    see http://mindprod.com/products2.html#SORTED
    for sample code.
    --
    Roedy Green Canadian Mind Products
    The Java Glossary
    http://mindprod.com
     
    Roedy Green, Aug 10, 2007
    #2
    1. Advertising

  3. Karsten Wutzke

    Danno Guest

    On Aug 10, 8:30 am, Karsten Wutzke <> wrote:
    > Hello!
    >
    > I have the following method overriding Collection.addAll:
    >
    > @Override
    > public boolean addAll(int index, Collection<? extends E> cln)
    > {
    > if ( containsAll(cln) )
    > {
    > return false;
    > }
    >
    > //build list without dupes (always)
    > ArrayList<E> al = new ArrayList<E>(cln.size());
    >
    > Iterator<? extends E> itr = cln.iterator();
    >
    > while ( itr.hasNext() )
    > {
    > E elem = itr.next();
    >
    > if ( !contains(elem) )
    > {
    > al.add(elem);
    > }
    > }
    >
    > cln = al;
    >
    > //allows dupes and nulls
    > return super.addAll(index, cln);
    >
    > }
    >
    > Is there any faster way without overriding other methods?
    >
    > Karsten


    Yep!

    Set<?> uniqueCollection = new TreeSet(collection);
     
    Danno, Aug 10, 2007
    #3
  4. On 11 Aug., 00:29, Danno <> wrote:
    > On Aug 10, 8:30 am, Karsten Wutzke <> wrote:
    >
    >
    >
    > > Hello!

    >
    > > I have the following method overriding Collection.addAll:

    >
    > > @Override
    > > public boolean addAll(int index, Collection<? extends E> cln)
    > > {
    > > if ( containsAll(cln) )
    > > {
    > > return false;
    > > }

    >
    > > //build list without dupes (always)
    > > ArrayList<E> al = new ArrayList<E>(cln.size());

    >
    > > Iterator<? extends E> itr = cln.iterator();

    >
    > > while ( itr.hasNext() )
    > > {
    > > E elem = itr.next();

    >
    > > if ( !contains(elem) )
    > > {
    > > al.add(elem);
    > > }
    > > }

    >
    > > cln = al;

    >
    > > //allows dupes and nulls
    > > return super.addAll(index, cln);

    >
    > > }

    >
    > > Is there any faster way without overriding other methods?

    >
    > > Karsten

    >
    > Yep!
    >
    > Set<?> uniqueCollection = new TreeSet(collection);


    Hmm how does this skip duplicates?

    Karsten
     
    Karsten Wutzke, Aug 11, 2007
    #4
  5. Karsten Wutzke wrote:
    > On 11 Aug., 00:29, Danno <> wrote:
    >> On Aug 10, 8:30 am, Karsten Wutzke <> wrote:
    >>
    >>
    >>
    >>> Hello!
    >>> I have the following method overriding Collection.addAll:
    >>> @Override
    >>> public boolean addAll(int index, Collection<? extends E> cln)
    >>> {
    >>> if ( containsAll(cln) )
    >>> {
    >>> return false;
    >>> }
    >>> //build list without dupes (always)
    >>> ArrayList<E> al = new ArrayList<E>(cln.size());
    >>> Iterator<? extends E> itr = cln.iterator();
    >>> while ( itr.hasNext() )
    >>> {
    >>> E elem = itr.next();
    >>> if ( !contains(elem) )
    >>> {
    >>> al.add(elem);
    >>> }
    >>> }
    >>> cln = al;
    >>> //allows dupes and nulls
    >>> return super.addAll(index, cln);
    >>> }
    >>> Is there any faster way without overriding other methods?
    >>> Karsten

    >> Yep!
    >>
    >> Set<?> uniqueCollection = new TreeSet(collection);

    >
    > Hmm how does this skip duplicates?


    A set contains no duplicates, so if the collection were the list "A",
    "B", "A" the treeset would contain "A", "B". However, the TreeSet
    iterator is in compareTo order, not the List order.

    If the collection is too large for linear scanning, I would implement
    the no-duplicates list using two data structures, a HashSet for
    determining which elements are eligible for adding, and a List to
    preserve order.

    Patricia
     
    Patricia Shanahan, Aug 11, 2007
    #5
  6. Karsten Wutzke

    Daniel Dyer Guest

    On Sat, 11 Aug 2007 20:01:10 +0100, Patricia Shanahan <> wrote:

    > Karsten Wutzke wrote:
    >> On 11 Aug., 00:29, Danno <> wrote:
    >>> On Aug 10, 8:30 am, Karsten Wutzke <> wrote:


    >>>> Is there any faster way without overriding other methods?
    >>>> Karsten
    >>> Yep!
    >>>
    >>> Set<?> uniqueCollection = new TreeSet(collection);

    >> Hmm how does this skip duplicates?

    >
    > A set contains no duplicates, so if the collection were the list "A",
    > "B", "A" the treeset would contain "A", "B". However, the TreeSet
    > iterator is in compareTo order, not the List order.


    A LinkedHashSet may be preferable if preserving the order is important:

    http://java.sun.com/j2se/1.5.0/docs/api/java/util/LinkedHashSet.html

    Dan.

    --
    Daniel Dyer
    http//www.uncommons.org
     
    Daniel Dyer, Aug 11, 2007
    #6
  7. Daniel Dyer wrote:
    > On Sat, 11 Aug 2007 20:01:10 +0100, Patricia Shanahan <> wrote:
    >
    >> Karsten Wutzke wrote:
    >>> On 11 Aug., 00:29, Danno <> wrote:
    >>>> On Aug 10, 8:30 am, Karsten Wutzke <> wrote:

    >
    >>>>> Is there any faster way without overriding other methods?
    >>>>> Karsten
    >>>> Yep!
    >>>>
    >>>> Set<?> uniqueCollection = new TreeSet(collection);
    >>> Hmm how does this skip duplicates?

    >>
    >> A set contains no duplicates, so if the collection were the list "A",
    >> "B", "A" the treeset would contain "A", "B". However, the TreeSet
    >> iterator is in compareTo order, not the List order.

    >
    > A LinkedHashSet may be preferable if preserving the order is important:
    >
    > http://java.sun.com/j2se/1.5.0/docs/api/java/util/LinkedHashSet.html


    I don't think LinkedHashSet has the ability to addAll at a specified
    index. The following is a quote from the original article:

    > I have the following method overriding Collection.addAll:
    >
    > @Override
    > public boolean addAll(int index, Collection<? extends E> cln)
    > {


    Collection does not have a two argument addAll. List does, so I suspect
    the new class is supposed to implement List.

    Patricia
     
    Patricia Shanahan, Aug 11, 2007
    #7
  8. Karsten Wutzke

    Danno Guest

    On Aug 11, 2:12 pm, Patricia Shanahan <> wrote:
    > Daniel Dyer wrote:
    > > On Sat, 11 Aug 2007 20:01:10 +0100, Patricia Shanahan <> wrote:

    >
    > >> Karsten Wutzke wrote:
    > >>> On 11 Aug., 00:29, Danno <> wrote:
    > >>>> On Aug 10, 8:30 am, Karsten Wutzke <> wrote:

    >
    > >>>>> Is there any faster way without overriding other methods?
    > >>>>> Karsten
    > >>>> Yep!

    >
    > >>>> Set<?> uniqueCollection = new TreeSet(collection);
    > >>> Hmm how does this skip duplicates?

    >
    > >> A set contains no duplicates, so if the collection were the list "A",
    > >> "B", "A" the treeset would contain "A", "B". However, the TreeSet
    > >> iterator is in compareTo order, not the List order.

    >
    > > A LinkedHashSet may be preferable if preserving the order is important:

    >
    > >http://java.sun.com/j2se/1.5.0/docs/api/java/util/LinkedHashSet.html

    >
    > I don't think LinkedHashSet has the ability to addAll at a specified
    > index. The following is a quote from the original article:
    >
    > > I have the following method overriding Collection.addAll:

    >
    > > @Override
    > > public boolean addAll(int index, Collection<? extends E> cln)
    > > {

    >
    > Collection does not have a two argument addAll. List does, so I suspect
    > the new class is supposed to implement List.
    >
    > Patricia


    Very nice Patricia,
    I also found this on commons-collections
    http://commons.apache.org/collectio...e/commons/collections/set/ListOrderedSet.html
     
    Danno, Aug 13, 2007
    #8
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    4
    Views:
    900
    Ingo R. Homann
    Jun 27, 2005
  2. Replies:
    1
    Views:
    440
    Robert M. Gary
    Nov 15, 2005
  3. keithb
    Replies:
    1
    Views:
    450
    Greg Young
    May 8, 2006
  4. Øyvind Isaksen
    Replies:
    1
    Views:
    1,028
    Øyvind Isaksen
    May 18, 2007
  5. Royan
    Replies:
    3
    Views:
    909
    Royan
    Aug 6, 2008
Loading...

Share This Page