Copying collection without duplicates

[Karsten Wutzke]

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

 

[Roedy Green]

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.

 

[Danno]

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);

 

[Karsten Wutzke]

Yep!

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

Hmm how does this skip duplicates?

Karsten

 

[Patricia Shanahan]

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

 

[Daniel Dyer]

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.

 

[Patricia Shanahan]

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

 

[Danno]

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



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