using Natural order with treeset in java

Question

I am getting an unexpected output for this. Please have a look. I am not able to find the problem. What's wrong with my program? Can anybody explain? I am getting the output

    Joe     Sue     Mike      Clare   Juliet       
    Joe         Mike        Clare        Juliet

objects in TreeSets and TreeMaps and with Collections.sort() for Lists, using the Comparable Interface.

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.List;
import java.util.SortedSet;
import java.util.TreeSet;

class Person implements Comparable<Person> {
    private String name;

    public Person(String name) {
        this.name = name;
    }

    public String toString() {
        return name;
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + ((name == null) ? 0 : name.hashCode());
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        final Person other = (Person) obj;
        if (name == null) {
            if (other.name != null)
                return false;
        } else if (!name.equals(other.name))
            return false;
        return true;
    }

    @Override
    public int compareTo(Person person) {
        int len1 = name.length();
        int len2 = person.name.length();

        if(len1 > len2) {
            return 1;
        }
        else if(len1 < len2) {
            return -1;
        }
        else {
            return 0;
        }
    }
}

public class App {

    public static void main(String[] args) { 

        List<Person> list = new ArrayList<Person>();
        SortedSet<Person> set = new TreeSet<Person>();


//adding  Element
        addElements(list);
        addElements(set);


//sorting element 
        Collections.sort(list);

//displaying result 
        showElements(list);
        System.out.println();
        showElements(set);
    }


//adding element methods

    private static void addElements(Collection<Person> col) {
        col.add(new Person("Joe"));
        col.add(new Person("Sue"));
        col.add(new Person("Juliet"));
        col.add(new Person("Clare"));
        col.add(new Person("Mike"));
    }

    private static void showElements(Collection<Person> col) {
        for(Person element: col) {
            System.out.println(element);
        }
    }

}

@RohitJain look at the code. `TreeSet` is supposed to add the data sorted and `Collections#sort(list)` should sort the elements in `ArrayList`, then OP print both collections and give different results. — Luiggi Mendoza, Mar 07 '14 at 17:18
@sanjaybrandtest1 But you are comparing your Person objects using their lengths name. Since Joe and Sue have the same length for their name, Sue is not added to the set. — Alexis C., Mar 07 '14 at 17:19
Please take more time to format your post in future - your entire code was indented 12 spaces, making it very hard to read. Look at the preview before you hit submit. — Jon Skeet, Mar 07 '14 at 17:19
i am using tree so out put is missiong >>> 'sue' as i mention. — sanjaybrandtest1, Mar 07 '14 at 17:20
@sanjaybrandtest1: I don't know what you mean by "i am not tree" but you're definitely using a `TreeSet`... — Jon Skeet, Mar 07 '14 at 17:21

score 8 · Accepted Answer · edited May 23 '17 at 11:52

You are comparing the persons by the length of their names. And the names "Joe" and "Sue" have the same length. So only one of them can occur in the TreeSet. However, this comparison criterion is not consistent with the implementation of equals!

You should place your Person objects into a list, and sort this list with Collections#sort - preferably, with an own Comparator. Also see https://stackoverflow.com/a/21659849

EDIT: Further explaination:

A Set can contain each element only once. And by the way that you specified your compareTo method, you impled that "Sue" and "Joe" are equal (because their names have equal lengths). So they can not both appear in a Set.

Note: They are not really equal, based on the equals method. But the TreeSet uses the compareTo method, and this compareTo method is currently not consistent with equals. So the Set shows a wrong behavior because of your wrong compareTo method.

EDIT: A possible solution:

If the names have equal lengths, you can compare them alphabetically. This way, the compareTo method becomes consistent with equals: It will return 0 if and only if the names are equal.

@Override
public int compareTo(Person person) {
    int len1 = name.length();
    int len2 = person.name.length();

    if(len1 > len2) {
        return 1;
    }
    else if(len1 < len2) {
        return -1;
    }
    else {
        return name.compareTo(person.name);
    }
}

@sanjaybrandtest1 Is the explaination from Meno Hochschild in http://stackoverflow.com/a/22256605 sufficient? — Marco13, Mar 07 '14 at 17:25

score 1 · Answer 2 · answered Mar 07 '14 at 17:21

1

A SortedSet uses compareTo for evaluation if an element can be added to the Set. Your input contains two names with same length (your comparison criterion), hence one of Joe or Sue must be filtered out (in your case Sue).

answered Mar 07 '14 at 17:21

Meno Hochschild

42,708
7
104
126

@sanjaybrandtest1 Marco13 has already posted a fine answer (was a few seconds quicker). In order to ensure to get all names into your Set you have to change your comparison criterion to get unique names in the context of your compareTo()-method. So just using length is not sufficient. You might compare lexicographically the strings in case of equal lengths in order to return non-zero comparison result. – Meno Hochschild Mar 07 '14 at 17:34

score 0 · Answer 3 · answered Mar 07 '14 at 17:26

The TreeSet documentation talks about having(not mandatory) compareTo implementaion consistent with equals. In your case 'Joe' and 'Sue' are of equal length and as per your compareTo implementation they are same. One workaround would be to compare the hashcode values in compareTo methods if they are of equal length.

using Natural order with treeset in java

3 Answers3

Linked