Java Help - Custom array list not sorting with Collections.sort() + SSCCE

Author

Custom array list not sorting with Collections.sort() + SSCCE

Karsten Wutzke

2008-03-13, 8:03 pm

Hello all!

I've written a custom array list that simply denies adding null
elements and duplicates. I build lists with string, which at some
point need to get sorted alphanumerically (using Collections.sort).

However, when using the custom list with Collections.sort, the list is
*not* sorted, but standard array list is...

Does anyone know why it is not sorted?

Here's a SSCCE:

import java.util.*;

/**
* An array list that does not allow duplicate and null elements.
*
* @author kw
*
* @param <E>
*/
public class NoDupesNoNullsArrayList<E> extends ArrayList<E>
{
public static void main(String[] strArgs)
{
String[] strs = {"one", "two", "three", "four", "five", "six",
"seven", "eight", "nine", "ten", "ten", "ten"};

System.out.println("Number of strings: " + strs.length);

List<String> lsNormal = new ArrayList<String>();
List<String> lsCustom = new NoDupesNoNullsArrayList<String>();

//some manual null adds to show the custom list should work
lsCustom.add(null);
lsCustom.add(null);
lsCustom.add(null);
lsCustom.add(null);
lsCustom.add(null);
lsCustom.add(null);

//add all
for ( String str : strs )
{
lsNormal.add(str);
lsCustom.add(str);
}

System.out.println("Number of list entries: normal = " +
lsNormal.size() + ", custom = " + lsCustom.size());

//now do standard alphanumeric sort
Collections.sort(lsNormal);
Collections.sort(lsCustom);

//result should be: eight, five, four, nine, one, seven, six, ten,
three, two

System.out.println();
System.out.print("Normal: ");

//print normal sorted
for ( String str : lsNormal )
{
System.out.print(str + ", ");
}

System.out.println();
System.out.print("Custom: ");

//print custom sorted
for ( String str : lsCustom )
{
System.out.print(str + ", ");
}

}

public NoDupesNoNullsArrayList()
{
super();
}

public NoDupesNoNullsArrayList(Collection<? extends E> cln)
{
super(cln);
}

public NoDupesNoNullsArrayList(int initialCapacity)
{
super(initialCapacity);
}

@Override
public boolean add(E elem)
{
if ( elem == null )
{
return false;
}

if ( contains(elem) )
{
return false;
}

return super.add(elem);
}

@Override
public void add(int index, E elem)
{
if ( elem == null )
{
return;
}

if ( contains(elem) )
{
return;
}

super.add(index, elem);
}

@Override
public boolean addAll(Collection<? extends E> cln)
{
return addAll(size(), cln);
}

@Override
public boolean addAll(int index, Collection<? extends E> cln)
{
if ( cln == this )
{
throw new IllegalArgumentException("Collection is this!");
}

if ( cln == null || containsAll(cln) )
{
return false;
}

//build list without dupes (always, no case as in NoNulls... lists)
ArrayList<E> al = new ArrayList<E>(cln.size());

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

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

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

cln = al;

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

@Override
public E set(int index, E elem)
{
if ( elem == null )
{
return null;
}

if ( contains(elem) )
{
return null;
}

return super.set(index, elem);
}

}

It might not appear THAT short, just don't care too much about the
array list implementation...

Any ideas?

Karsten

Steven Simpson

2008-03-13, 8:03 pm

Karsten Wutzke wrote:
> I've written a custom array list that simply denies adding null
> elements and duplicates. I build lists with string, which at some
> point need to get sorted alphanumerically (using Collections.sort).
>
> However, when using the custom list with Collections.sort, the list is
> *not* sorted, but standard array list is...
>

Temporarily make all occurrances of either/both of these tests throw
some RuntimeException, instead of returning false or null:

> if ( elem == null ) ...
> if ( contains(elem) ) ...
>

You'll have to change your test data so the exceptions aren't thrown
before you've called sort().

You should find that the sort algorithm at some point tries to
insert/set a duplicate, and where in the JDK source code it does this.
Have a look to see how it responds to a failed insert/set operation.

Perhaps an alternative would be to define a new List implementation
which wraps a list, and checks for duplicates. Then you could pass the
wrapped list to sort().

List<String> myData = new ArrayList<String>();
List<String> guard = new NoDupesNoNullsList<String>(myData);
guard.addAll(Arrays.asList(...));
Collections.sort(myData);

--
ss at comp dot lancs dot ac dot uk |

Roedy Green

2008-03-13, 10:25 pm

On Thu, 13 Mar 2008 15:08:54 -0700 (PDT), Karsten Wutzke
<kwutzke@web.de> wrote, quoted or indirectly quoted someone who said :

>List<String> lsCustom = new NoDupesNoNullsArrayList<String>();

There is nothing that says that for a short time during a sort you
don't have nulls or dups. It has to exchange elements. This means for
a short time you will have a dup.
--

Roedy Green Canadian Mind Products
The Java Glossary
http://mindprod.com

Roedy Green

2008-03-13, 10:25 pm

On Fri, 14 Mar 2008 01:08:25 GMT, Roedy Green
<see_website@mindprod.com.invalid> wrote, quoted or indirectly quoted
someone who said :

>There is nothing that says that for a short time during a sort you
>don't have nulls or dups. It has to exchange elements. This means for
>a short time you will have a dup.

To see what I mean, try writing a code snippet that exchanges two
elements in a List without temporarily having a null or a duplicate.
--

Roedy Green Canadian Mind Products
The Java Glossary
http://mindprod.com

Karsten Wutzke

2008-03-15, 5:15 am

On 14 Mrz., 02:09, Roedy Green <see_webs...@mindprod.com.invalid>
wrote:
> On Fri, 14 Mar 2008 01:08:25 GMT, Roedy Green
> <see_webs...@mindprod.com.invalid> wrote, quoted or indirectly quoted
> someone who said :
>
>
> To see what I mean, try writing a code snippet that exchanges two
> elements in a List without temporarily having a null or a duplicate.
> --
>

As I ponder about this issue it makes more and more sense, no need to
try... it's the A and B (register) swap problem... you need a temp/
dupe var.

I'll have to use this as a "guard collection" only, sorting is rarely
needed, though such a list now is somewhat more useless.

Karsten

Roedy Green

2008-03-15, 7:37 pm

On Sat, 15 Mar 2008 01:55:59 -0700 (PDT), Karsten Wutzke
<kwutzke@web.de> wrote, quoted or indirectly quoted someone who said :

>As I ponder about this issue it makes more and more sense, no need to
>try... it's the A and B (register) swap problem... you need a temp/
>dupe var.

I think even with a temp, you still have the problem.
--

Roedy Green Canadian Mind Products
The Java Glossary
http://mindprod.com

Sponsored Links