środa, 2 marca 2011

Zagadka

Jak ten młody leszcz dałem się ostatnio nabrać na TreeSet w Javie. Oto zagadka:
chciałem sobie posortować liście na podstawie ich koloru, użyłem TreeSet'a, jaki będzie wynik funkcji shouldTestTreeSet(), jaka będzie kolejność liści?

class Leaf{
   
    int color;
    int size;
   
    public Leaf(int color, int size) {
        this.color = color;
        this.size = size;
    }

    @Override
    public boolean equals(Object obj) {
        if (obj == this) return true;
        if (!(obj instanceof Leaf)) return false;
        Leaf leaf = (Leaf) obj;
        return new EqualsBuilder().append(this.color, leaf.color)
            .append(this.size, leaf.size).isEquals();
    }
   
    @Override
    public int hashCode() {
        return new HashCodeBuilder().append(color).append(size).toHashCode();
    }
   
    @Override
    public String toString() {

        return String.valueOf(color + " " +size);
    }
}

class LeafComparator implements Comparator<Leaf>{

    @Override
    public int compare(Leaf o1, Leaf o2) {
       
        return Ints.compare(o1.color, o2.color);
    }
}

public class TreeSetTest {

    public void shouldTestTreeSet() {

        Leaf leaf = new Leaf(1,1);
        Leaf leaf2 = new Leaf(1,2);
        Leaf leaf3 = new Leaf(1,3);

        Set<Leaf> tree = new TreeSet<Leaf>(new LeafComparator());
       
        tree.add(leaf3);
        tree.add(leaf);
        tree.add(leaf2);

        System.out.println(tree);
    }
}

8 komentarzy:

  1. leaf3, ponieważ metoda 'equals' jest źle zaimplementowana -- zawsze zwraca true.

    OdpowiedzUsuń
  2. W equals robisz porównanie obj z obj zamiast z obiektem, na którym wywołano equals :)

    OdpowiedzUsuń
  3. Ok, pierwszy babol wypatrzony - nawet szybko. Ale zagadka się nie kończy, co w przypadku jeśli equals będzie poprawnie zaimplementowane?

    OdpowiedzUsuń
  4. Porównywany jest tylko color, a różnią się size'em?

    OdpowiedzUsuń
  5. No tak, to widać na pierwszy rzut oka, pytanie co się dzieje w takim przypadku. Pełnoprawną odpowiedzią jest dopiero taka, która będzie miała dołączone poprawne uzasadnienie. Czekamy dalej...

    OdpowiedzUsuń
  6. leaf3, ponieważ metoda 'compare' porównuje jedynie color. O ile kontrakt dla Set (z wykorzystaniem equals()) zostanie teraz spełniony, to w TreeSet następuje ponowna weryfikacja w oparciu o compare() co w wypadku obecnego porównania skutkuje takim samym wynikiem jak poprzednia 'błędna' implementacja equals().

    OdpowiedzUsuń
  7. And the winner is msi! Ogólnie w przypadku TreeSet'a dla tego przykładu możemy olać metodę equals i jej w ogóle nie implementować, bo TreeSet używa compare, lub comapreTo, które to muszą być zgodne z equals. Czyli jeśli x.compare(y) == 0, to x.eqals(y) == true. Jak dla mnie słowo zgodne, powinno być czerwonym boldem w dokumentacji, bo dałem się równo nabrać.

    OdpowiedzUsuń