Collections.sort() does not sort my ArrayList

[M Burke]

I wonder why this is not working. I have an ArrayList I extracted from a Set, then I try to sort it in natural order. It's a collection of Strings. What am I missing here?

//forumMap is a TreeMap using a Map reference
Set keys = forumMap.keySet();
ArrayList lKeys = new ArrayList(keys);
Collections.sort(lKeys);
//lKeys is not sorted!

[Steve Luke]

How do you know IKeys is not ordered? Can you show us a bit more of the code, like the place where you test IKeys for order?

[Norm Radder]

What does the compareTo() method look like for the objects being sorted?

[M Burke]

I can see in the Eclipse debugger that the strings are not sorted. The object type is Java String, so I assume I don't need a custom comparer.

The list reads like this...

Inventory
Sales
Energy
Operations
Trucks

And it remains unchanged after the sort()

[Jelle Klap]

Don't declare the TreeMap as a Map, but as a NavigableMap, that way you can retrieve a NavigableSet using the navigableKeySet() method.

Edit: Oh, I'm sorry, you're sorting a List. Nevermind.
[ August 22, 2008: Message edited by: Jelle Klap ]

[Steve Luke]

When you iterate over the list, are they sorted?

[Steve Luke]

When I run similar code (see below) the Strings are sorted inside the Set - as the contract for TreeMap says they should be. Can you post exact code that
1) Generates the Map
2) Gets the List of Entries
3) Iterates over the List
that shows your problem?

public class SortableStrings
{
    public static void main(String[] args)
    {
        TreeMap data = new TreeMap();
        data.put("Fred", "Fred");
        data.put("Adam", "Adam");
        data.put("Mikey", "Mikey");
        data.put("Charlie", "Charlie");
        
        Set keys = data.keySet();
        ArrayList sortMe = new ArrayList(keys);
        Collections.sort(sortMe);
        for(Object o : sortMe) {
            System.out.println(o);
        }
    }
}

[ August 22, 2008: Message edited by: Steve Luke ]

[Campbell Ritchie]

Originally posted by Steve Luke:
When I run similar code (see below) the Strings are sorted inside the Set - as the contract for TreeMap says they should be.

But your code only demonstrates sorting a List. What happens when you print the Set before the Collections.sort call? Of course you are sorting Strings which implement Comparable already.

[Steve Luke]

Originally posted by Campbell Ritchie:
But your code only demonstrates sorting a List. What happens when you print the Set before the Collections.sort call? Of course you are sorting Strings which implement Comparable already.

The Set is pre-sorted in ascending order, because it is coming from a TreeMap which is a SortedMap. The List will be pre-sorted as well, so there would be no need to do the Collections.sort. I ran the test to follow the OP's use-case but still get different results than he suggests in his posts.

Unless I am missing something, the code I provided is just like the code he says he is using.

[M Burke]

Originally posted by Steve Luke:
When I run similar code (see below) the Strings are sorted inside the Set - as the contract for TreeMap says they should be. Can you post exact code that
1) Generates the Map
2) Gets the List of Entries
3) Iterates over the List
that shows your problem?

public class SortableStrings
{
    public static void main(String[] args)
    {
        TreeMap data = new TreeMap();
        data.put("Fred", "Fred");
        data.put("Adam", "Adam");
        data.put("Mikey", "Mikey");
        data.put("Charlie", "Charlie");
        
        Set keys = data.keySet();
        ArrayList sortMe = new ArrayList(keys);
        Collections.sort(sortMe);
        for(Object o : sortMe) {
            System.out.println(o);
        }
    }
}

[ August 22, 2008: Message edited by: Steve Luke ]

Once thing that is different with my TreeMap (forumMap) does not contain a String as the contained type. But the key is a String.

When I construct my map, it looks like this, Forum is a custom object...

forumList = fDAO.refreshForumList(mbJDO);
if(forumList != null){
Iterator ix = forumList.iterator();
while(ix != null && ix.hasNext()){
Forum forum = (Forum) ix.next();
forumMap.put(forum.getStrForumName(), forum);
}
}

[Steve Luke]

Originally posted by M Burke:
Once thing that is different with my TreeMap (forumMap) does not contain a String as the contained type.

Yeah I used a String cause I had to put something in there. Putting new Object() or any other non-null value will have the same effect (tested it with new Object()) because TreeMap is sorted on the keys (and later, you only pull out the keys into the list for sorting again).

Originally posted by M Burke:
But the key is a String.

That would be one of the first things I would double check. When you get the List of Keys, iterate over it displaying the Class of the value in the list.

As stated above, the values will be sorted in the Map. They will be sorted when the keys are pulled outs as a Set, and the Collections.sort will properly sort Strings because String implements Comparable.

I could conceive that the Set could have un-sorted data returned to the List if the Map is still being built while you do
ArrayList lKeys = new ArrayList(keys);
The Set is backed by the original Map, so changes in the Map are reflected in the Set. If these changes happen while the List is iterating the Set you are likely to see inconsistent data.

But the List will be a snap-shot of the Set, and any further changes in the Set (or Map) will not affect the List once it is made, and the Collections.sort will work on that snap shot.

[M Burke]

Originally posted by Steve Luke:


That would be one of the first things I would double check. When you get the List of Keys, iterate over it displaying the Class of the value in the list.

As stated above, the values will be sorted in the Map. They will be sorted when the keys are pulled outs as a Set, and the Collections.sort will properly sort Strings because String implements Comparable.

I could conceive that the Set could have un-sorted data returned to the List if the Map is still being built while you do
ArrayList lKeys = new ArrayList(keys);
The Set is backed by the original Map, so changes in the Map are reflected in the Set. If these changes happen while the List is iterating the Set you are likely to see inconsistent data.

But the List will be a snap-shot of the Set, and any further changes in the Set (or Map) will not affect the List once it is made, and the Collections.sort will work on that snap shot.

I checked to be certain the keys are strings, and they are. I put some extra tests in my code to verify it. When I use a TreeMap that contains Strings as the data, then the sort works. But my TreeMap does npt sort.

When I run this, className is equal to "class java.lang.String"

Set keys = forumMap.keySet();
ArrayList aKeys = new ArrayList();
Iterator ix = keys.iterator();

while(ix != null && ix.hasNext()){
Object obj = ix.next();
Class c = obj.getClass();
String className = c.toString();
String tmp = new String(obj.toString());
aKeys.add(tmp);
}

Collections.sort(aKeys);

There is something about my TreeMap not using Strings as data that is messing thing up.

[Steve Luke]

Originally posted by M Burke:

There is something about my TreeMap not using Strings as data that is messing thing up.

That shouldn't be either. For example, if I use integers, or Person objects (a random immutable class I have sitting around) which I intentionally order in a different manner than the Strings natural ordering then the sort will still work.

The problem must be with the Strings being used as Keys, which are both causing the TreeMap not to sort and the Collection.sort not to work.

The natural order of Strings is case sensitive (example "Fred" comes before "adam" but after "Adam"), so case will influence order. Perhaps toUpperCase or toLowerCase all keys?

[Steve Luke]

When I use a TreeMap that contains Strings as the data

Do you mean if you do:

forumList = fDAO.refreshForumList(mbJDO);
if(forumList != null){
    Iterator ix = forumList.iterator();
    while(ix != null && ix.hasNext()){
        Forum forum = (Forum) ix.next();
        forumMap.put(forum.getStrForumName(), "Any old String");
    }
} 

Then the sorting works - using the same keys as the map that doesn't sort?

[M Burke]

Well, I found the problem. It is sorting, just not as I expected. All the upper case strings sort in front of the lower case strings. So I has to add a compare to the original TreeMap so it sorts without regard to case.

Map forumMap = new TreeMap(new TwoStringComparatorIgnoreCase());

Using this custom class...

public class TwoStringComparatorIgnoreCase implements Comparator {

public int compare( Object object1, Object object2 ) {
return ((String) object1).compareToIgnoreCase((String) object2 );
}

}

[Steve Luke]

Glad to see you got it working. I just wanted to comment about providing information regarding your problem. You had previously posted:

Originally posted by M Burke:
The list reads like this...

Inventory
Sales
Energy
Operations
Trucks

And it remains unchanged after the sort()

If you had shown real results than we would have been able to conclude the Case Sensitivity issue sooner.

So in the future, please provide Real Results when posting your questions.

[Paul Clapham]

Also, that comparator has been available in the standard Java API since Java 1.2. There's a static Comparator variable in the String class named "CASE_INSENSITIVE_ORDER" that you could have used:

Map forumMap = new TreeMap(String.CASE_INSENSITIVE_ORDER);

(Not that writing code that duplicates standard API functions is a bad thing, it does provide useful experience. I'm sure I have done it in the past. But if I found I had done it, I would replace my code with a call to the standard API. The less code I have to maintain, the better.)
[ August 22, 2008: Message edited by: Paul Clapham ]