Comparable

Sissejuhatus

Kui Java peab sorteerima objektide kogumit, peab ta teadma, millises järjekorras elemendid paiknevad. Primitiivsete tüüpide ja String-i puhul on see järjekord juba defineeritud, kuid oma klasside puhul tuleb see selgesõnaliselt määrata.

Javas on selle jaoks kaks mehhanismi:

• Comparable liides, mille kaudu seda rakendav klass määrab ära, kuidas järjestamist läbi viia.
• Comparator liides, mis seab reeglid järjestamiseks ilma klassi muutmata.

Comparable<T> liides võimaldab klassil kirjeldada oma loomuliku järjestuse - vaikimisi reegli, mille alusel selle eksemplare võrreldakse ja sorteeritakse. Kui klass implementeerib Comparable-i, töötavad sellised mehhanismid nagu Collections.sort(), Arrays.sort() ning sorteeritud kogumid (TreeSet, TreeMap) sellega automaatselt, ilma täiendava konfiguratsioonita.

Omadus	Comparable	Comparator
Kus asub loogika	Klassis endas	Eraldi objektis
Meetod	compareTo(T other)	compare(T a, T b)
Mitu järjestust	Ainult üks	Nii palju kui vaja
Klassi muutmine	Vajalik	Pole vajalik
Sobib	Loomuliku järjestuse määramiseks	Alternatiivseks ja paindlikuks järjestamiseks

compareTo() meetod ja selle leping

Comparable<T> liides sisaldab ühte meetodit, milleks on compareTo(T other):

public interface Comparable<T> {
    int compareTo(T other);
}

Meetodi compareTo tagastusväärtus määrab objektide omavahelise järjestuse:

• negatiivne arv — this tuleb järjestuses enne other-it
• 0 — this ja other on järjestuse mõttes võrdsed
• positiivne arv — this tuleb järjestuses pärast other-it

Oluline ei ole konkreetne arvuline väärtus, vaid selle märk (negatiivne, null või positiivne).

Samas compareTo() peab järgima kindlat lepingut, mis defineerib ära, kuidas objektide võrdlus peab toimima. Java ametlikus dokumentatsioonis on see kirjutatud järgnevalt:

Sisuliselt see tähendab, et:

• Kui a.compareTo(b) < 0, siis b.compareTo(a) peab olema positiivne arv (antisümmeetria).
• Kui a.compareTo(b) == 0, siis b.compareTo(a) peab samuti tagastama 0.
• Kui a.compareTo(b) < 0 ja b.compareTo(c) < 0, siis a.compareTo(c) peab samuti olema negatiivne (transitiivsus).

Nende reeglite rikkumine võib põhjustada ettearvamatut käitumist sorteerimisalgoritmides ja sorteeritud kogumites.

check_circlenõuanne

Soovitatav on, et compareTo() oleks kooskõlas equals()-iga: kui a.compareTo(b) == 0, siis a.equals(b) peaks samuti olema true. Sorteeritud kogumid, näiteks TreeSet, kasutavad elementide võrdsuse määramiseks compareTo()-meetodit, mitte equals()-i. Kui need kaks ei ole kooskõlas, võivad tekkida raskesti märgatavad vead (nt elementide ootamatu „kadumine“ kogumist).

Lihtne näide

Alljärgnevas näites määrab Product oma loomuliku järjestuse hinna alusel:

class Product implements Comparable<Product> {
    private String name;
    private double price;

    public Product(String name, double price) {
        this.name = name;
        this.price = price;
    }

    public String getName()  { return name; }
    public double getPrice() { return price; }

    @Override
    public int compareTo(Product other) {
        // cheapest first
        if (this.price < other.price) {
            return -1;
        } else if (this.price > other.price) {
            return 1;
        } else {
            return 0;
        }
    }
}

Antud näite puhul on eelnevalt mainitud leping täidetud järgnevalt. Meetod:

• tagastab negatiivse arvu, kui this on odavam,
• positiivse arvu, kui this on kallim,
• 0, kui hinnad on võrdsed.

warninghoiatus

Praktikas kasutatakse turvalisemaid võtteid võrdluse läbi viimiseks, kuid antud näide seletab põhilist töö põhimõtet.

Kasutamine:

List<Product> products = new ArrayList<>();
products.add(new Product("Keyboard", 49.99));
products.add(new Product("Monitor",  299.99));
products.add(new Product("Mouse",    29.99));

Collections.sort(products);

for (Product p : products) {
    System.out.println(p.getName() + " - " + p.getPrice());
}

// Mouse    - 29.99
// Keyboard - 49.99
// Monitor  - 299.99

Kuna Product implementeerib Comparable liidest, oskab Collections.sort() elemente sorteerida ilma täiendava Comparator-ita.

Turvalised võrdlusabifunktsioonid

Eelmises näites kasutasime käsitsi if/else loogikat hindade võrdlemiseks. Kuigi see on korrektne ja selge, on olemas lühemad ning töökindlamad alternatiivid.

Levinud anti-pattern on võrdlustulemuse arvutamine lahutamise teel:

@Override
public int compareTo(Product other) {
    return (int)(this.price - other.price); // Wrong
}

See lähenemine on problemaatiline mitmel põhjusel:

• Täpsuskadu: double-väärtuste lahutamisel võib tulemus olla murdarv (nt 1.9 - 1.1 = 0.8), mis int-iks teisendamisel muutub 0-ks. Objektid loetakse võrdselt järjestatuks, kuigi nad ei ole võrdsed.
• Ületäitumisoht: täisarvude puhul (this.id - other.id) võib lahutamine suurte väärtuste korral ületäituda ning anda vale märgiga tulemuse.

Soovitatav on kasutada vastava tüübi staatilisi võrdlusmeetodeid:

@Override
public int compareTo(Product other) {
    return Double.compare(this.price, other.price);
}

Need meetodid tagavad korrektse märgi, arvestavad erijuhtumitega ning vastavad Comparable-lepingu nõuetele.

Standardteek pakub võrdlusabimeetodeid enamiku primitiivtüüpide jaoks:

Tüüp	Meetod
int	Integer.compare(a, b)
long	Long.compare(a, b)
double	Double.compare(a, b)
String	a.compareTo(b) (juba implementeeritud)

Sorteerimine mitme välja järgi

Võimalik on ka olukord, kus on vaja objekte võrrelda mitme erineva tunnuse järgi. Kui esmane võrdlusväli on võrdne, tuleb kasutada teisi välju nn. tie-breaker’ina ehk otsustada, mida teha viigiolukorras.

class Product implements Comparable<Product> {
    private String name;
    private double price;

    // ...

    @Override
    public int compareTo(Product other) {
        int byPrice = Double.compare(this.price, other.price);
        if (byPrice != 0) return byPrice;
        return this.name.compareTo(other.name); // tiebreak by name
    }
}

Loogika:

1. Kõigepealt võrreldakse hinda.
2. Kui hinnad erinevad, tagastatakse see tulemus.
3. Kui hinnad on võrdsed, võrreldakse nime.

Selline lähenemine tagab deterministliku ja transitiivse järjestuse ka siis, kui mitmel objektil on sama põhiväärtus.