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
– Luiggi Mendoza, Commented Mar 7, 2014 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.
– Alexis C., Commented Mar 7, 2014 at 17:19
@sanjaybrandtest1: I don't know what you mean by "i am not tree" but you're definitely using a TreeSet... — Jon Skeet
– Jon Skeet, Commented Mar 7, 2014 at 17:21

Community · Accepted Answer · 2017-05-23 11:52:09Z

8

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

edited May 23, 2017 at 11:52

CommunityBot

11 silver badge

answered Mar 7, 2014 at 17:19

Marco13

54.8k9 gold badges84 silver badges170 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

sanjaybrandtest1 Over a year ago

can you explain please?

Marco13 Over a year ago

@sanjaybrandtest1 Is the explaination from Meno Hochschild in stackoverflow.com/a/22256605 sufficient?

Marco13 Over a year ago

@sanjaybrandtest1 I added a possible solution in the answer

Meno Hochschild · Accepted Answer · 2014-03-07 17:21:21Z

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 7, 2014 at 17:21

Meno Hochschild

44.3k7 gold badges109 silver badges130 bronze badges

1 Comment

Meno Hochschild Over a year ago

@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.

nitnamby · Accepted Answer · 2014-03-07 17:26:23Z

0

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.

answered Mar 7, 2014 at 17:26

nitnamby

4142 silver badges8 bronze badges

Collectives™ on Stack Overflow

using Natural order with treeset in java

3 Answers 3

3 Comments

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

3 Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related