Podczas pracy z projektami Javowymi często zdarza się sytuacja, w której musimy posortować daną kolekcję według określonego kryterium. Wtedy z pomocą przychodzą nam dwa interfejsy: Comparable oraz Comparator. W tym wpisie omówię kwestię sortowania kolekcji w Javie, wyjaśnię czym różni się sortowanie przy pomocy interfejsu Comparable od sortowania z wykorzystaniem interfejsu Comparator i w jaki sposób z nich korzystać. Pokażę też dwie kolekcje, których działanie opiera się na zachowaniu odpowiedniej kolejności elementów: TreeSet oraz TreeMap.
Sortowanie w kolekcjach
Kiedy mówimy o sortowaniu danej kolekcji, to najczęściej chodzi nam o skorzystanie z metody sort lub reverse, które są dostępne w klasie Collections, w paczce java.util. Metoda sort sortuje daną kolekcję rosnąco według jakiegoś kryterium, natomiast metoda reverse odwraca kolejność elementów w kolekcji.
Przyjrzyjmy się tym metodom na prostym przykładzie listy Integerów:
List<Integer> prices = Arrays.asList(1, 5, 32, 76, 3, 21, 7, 333, 43, 221);
System.out.println("Nieposortowane: " + prices);
Collections.sort(prices);
System.out.println("Posortowane rosnąco: " + prices);
Collections.reverse(prices);
System.out.println("Posortowane malejąco: " + prices);
Tworzymy listę liczb całkowitych, wypisujemy na ekran najpierw nieposortowane liczby, następnie korzystamy z metody sort i wypisujemy elementy kolekcji na ekran – będą one posortowane rosnąco. Następnie wywołujemy metodę reverse i znowu wypisujemy liczby na ekran. Tym razem będą one posortowane malejąco:
Nieposortowane: [1, 5, 32, 76, 3, 21, 7, 333, 43, 221] Posortowane rosnąco: [1, 3, 5, 7, 21, 32, 43, 76, 221, 333] Posortowane malejąco: [333, 221, 76, 43, 32, 21, 7, 5, 3, 1]
Oczywiście tyczy się to nie tylko liczb całkowitych, ale również Stringów i ogólnie tak zwanych wrapperów typów prymitywnych, czyli klas typu Integer, Double, Long, Float, etc. W ten sposób możemy również sortować kolekcję przechowującą typy enumowe.
Z pomocy metod sort i reverse możemy skorzystać w każdej kolekcji, która implementuje interfejs List.
Sortowanie obiektów
Sortowanie obiektów, podobnie jak w przypadku nadpisywania metody equals, jest subiektywne. To od nas zależy według czego będziemy dany obiekt sortować. Możemy bowiem zdecydować się na posortowanie po wartości jednego lub więcej pól. Spójrzmy na przykład akcji na giełdzie:
public class Stock {
private String name;
private String symbol;
private double price;
public Stock(String name, String symbol, double price) {
this.name = name;
this.symbol = symbol;
this.price = price;
}
public String getName() {
return name;
}
public String getSymbol() {
return symbol;
}
public double getPrice() {
return price;
}
@Override
public String toString() {
return "Stock{" +
"name='" + name + '\'' +
", symbol='" + symbol + '\'' +
", price=" + price +
'}';
}
}
Klasa posiada trzy pola prywatne, konstruktor, gettery oraz metodę toString, która pozwoli na ładniejsze formatowanie wyświetlanych obiektów tej klasy na standardowym wyjściu.
Gdybyśmy teraz stworzyli kolekcje przechowującą elementy typu Stock i spróbowali na niej wywołać metodę sort, to niestety w linii 11 otrzymamy błąd kompilacji:
Stock stock1 = new Stock("cd projekt blue", "cdp", 15.78);
Stock stock2 = new Stock("amazon", "amz", 5.23);
Stock stock3 = new Stock("microsoft", "mst", 157.65);
Stock stock4 = new Stock("google", "ggl", 7.08);
Stock stock5 = new Stock("apple", "apl", 66.43);
List<Stock> stockList = Arrays.asList(stock1, stock2, stock3, stock4, stock5);
stockList.forEach(System.out::println);
Collections.sort(stockList);
Nie powinno nas to dziwić: w końcu według jakiego kryterium ta kolekcja miałaby być posortowana? Klasa Stock posiada 4 pola, tak naprawdę możemy sortować listę po każdym z tych pól i w każdym przypadku będzie miało to merytoryczny sens.
Zatem co zrobić? Tutaj pomoże nam właśnie interfejs Comparable.
Interfejs Comparable
W interfejsie Comparable znajduje się deklaracja metody compareTo:
public int compareTo(T o);
Załóżmy, że porównujemy obiekty A i B tego samego typu i na obiekcie A wywołujemy metodę compareTo: A.compareTo(B).
Z opisu metody wynika, że implementacja metody compareTo powinna zwrócić:
- wartość mniejszą od 0, gdy porównywany obiekt
Auznamy za „mniejszy” od obiektuB, - wartość większą od 0, gdy porównywany obiekt
Auznamy za „większy” od obiektuB, - wartość równą 0, gdy obiekt
Auznamy za równy obiektowiB.
Zaimplementujmy zatem metodę compareTo w klasie Stock. Załóżmy, że chcemy sortować akcje według ich ceny.
Najpierw dodajemy odpowiednią frazę do deklaracji klasy:
public class Stock implements Comparable<Stock> {
Teraz czas na implementację metody compareTo. Można to zrobić na kilka sposobów. Najbardziej oczywisty to coś w rodzaju:
@Override
public int compareTo(Stock o) {
if(this.getPrice() < o.getPrice()) return -1;
if(this.getPrice() > o.getPrice()) return 1;
else return 0;
}
Taki zapis można nieco uprościć wykorzystując różnicę matematyczną (z dodatkiem rzutowania w tym konkretnym przypadku):
@Override
public int compareTo(Stock o) {
return (int) (this.getPrice() - o.getPrice());
}
Kolejnym sposobem jest skorzystanie z metody compare dostępnej w każdym wrapperze typów prymitywnych, o których wspominałem wcześniej. W tym przypadku możemy skorzystać z metody statycznej dostępnej w klasie Double:
@Override
public int compareTo(Stock o) {
return Double.compare(this.getPrice(), o.getPrice());
}
Skoro mamy już implementację interfejsu Comparable, to możemy teraz sprawdzić czy zadziała nam sortowanie z metodą sort(tam gdzie poprzednio mieliśmy błąd kompilacji):
Stock{name='amazon', symbol='amz', price=5.23}
Stock{name='google', symbol='ggl', price=7.08}
Stock{name='cd projekt blue', symbol='cdp', price=15.78}
Stock{name='apple', symbol='apl', price=66.43}
Stock{name='microsoft', symbol='mst', price=157.65}
Jak widać wszystko działa jak należy: obiekty są posortowane rosnąco według ceny.
Sortowanie po wielu polach
Jednak co zrobić w sytuacji, gdy akcje będą miały taką samą cenę i wtedy w drugiej kolejności chcielibyśmy posortować je według kolejności alfabetycznej po nazwach? A co jeśli nazwy również będą takie same (to się pewnie nie zdarzy na prawdziwej giełdzie :P) i wówczas chcielibyśmy je posortować po symbolach? Nie ma problemu, musimy po prostu dodać do implementacji metody compareTo stosowną logikę:
@Override
public int compareTo(Stock o) {
int compareResult = Double.compare(this.getPrice(), o.getPrice());
if(compareResult == 0){
compareResult = this.getName().compareToIgnoreCase(o.getName());
}
if(compareResult == 0){
compareResult = this.getSymbol().compareToIgnoreCase(o.getSymbol());
}
return compareResult;
}
Najpierw porównujemy cenę i wynik przypisujemy do zmiennej compareResult. Następnie sprawdzamy czy compareResult jest równa 0. Jeśli tak, to oznacza to, że obydwa obiekty mają taką samą cenę, więc chcemy je następnie porównać po nazwie. Porównujemy je zatem po nazwie (tym razem korzystając z metody dostępnej w klasie String: compareToIgnoreCase, która dokona porównania bez względu na wielkość znaków) i ponownie sprawdzamy czy compareResult jest równa 0. Jeśli tak, to zarówno cena, jak i nazwa akcji jest taka sama. Musimy zatem dokonać trzeciego porównania, tym razem symboli. Są one typu String, więc ponownie korzystamy z metody compareToIgnoreCase. Na końcu zwracamy wartość zmiennej compareResult.
W rezultacie, przy drobnej zmianie wartości naszych przykładowych obiektów (tak aby zarówno ceny, jak i nazwy akcji się powtarzały):
Stock stock1 = new Stock("cd projekt blue", "cdp", 5.23);
Stock stock2 = new Stock("amazon", "amz", 5.23);
Stock stock3 = new Stock("amazon", "aat", 5.23);
Stock stock4 = new Stock("google", "ggl", 7.08);
Stock stock5 = new Stock("apple", "apl", 7.08);
otrzymujemy kolekcję akcji poprawnie posortowaną najpierw po cenie, następnie po nazwie i na końcu po symbolu.
CompareToBuilder
Przyszedł czas na poznanie pewnego ułatwienia. Jest nim klasa CompareToBuilder, dzięki której możemy w bardzo prosty sposób zaimplementować metodę compareTo. Klasa ta znajduje się w paczce org.apache.commons.lang3.builder, więc żeby móc z niej skorzystać, należy dodać odpowiednią zależność do pliku pom.xml. Jak się można domyślić, klasa ta jest implementacją wzorca projektowego Builder.
Spójrzmy teraz w jaki sposób prezentowałaby się metoda compareTo, gdybyśmy chcieli ją zaimplementować przy użyciu CompareToBuildera, mając te same wymagania co w powyższym przykładzie (sortowanie po cenie, nazwie i symbolu):
@Override
public int compareTo(Stock o) {
return new CompareToBuilder()
.append(this.getPrice(), o.getPrice())
.append(this.getName(), o.getName())
.append(this.getSymbol(), o.getSymbol())
.build();
}
Moim zdaniem wygląda świetnie: prosto i przede wszystkim przejrzyście. Wykonujemy tutaj dość powszechne chainowanie metod. Korzystamy z konstruktora, aby utworzyć obiekt typu CompareToBuilder, używamy metod append, aby dodać kolejne pola według których chcemy sortować obiekty (może to być jedno lub więcej pól) i na końcu wywołujemy metodę build. Całą resztę załatwia za nas CompareToBuilder.
Klasa Comparator
Kolejnym sposobem na sortowanie obiektów w kolekcji jest skorzystanie z interfejsu Comparator. Możemy to zrobić tworząc odrębną klasę, na przykład StockComparator:
public class StockComparator implements Comparator<Stock> {
@Override
public int compare(Stock o1, Stock o2) {
return new CompareToBuilder()
.append(o1.getPrice(), o2.getPrice())
.append(o1.getName(), o2.getName())
.append(o1.getSymbol(), o2.getSymbol())
.build();
}
}
Jest to dość prosta implementacja: tworzymy nową klasę, implementujemy interfejs Comparator (który przyjmuje typ generyczny – podajemy tam oczywiście klasę Stock) i nadpisujemy metodę compare, której sposób działania powinien być identyczny jak metody compareTo z interfejsu Comparable – zatem tu również możemy skorzystać z klasy CompareToBuilder.
Teraz podczas sortowania możemy podać instancję klasy StockComparator jako drugi argument metody sort:
Collections.sort(stockList, new StockComparator());
Możemy również utworzyć instancję klasy typu Comparator jako anonimową klasę wewnętrzną, czyli w żądanym miejscu w kodzie tworzymy od razu instancję oraz definicję całej klasy. Tak utworzoną instancję przekazujemy następnie do metody sort i w pętli wypisujemy elementy kolekcji stockList na ekran:
Comparator<Stock> stockComparator = new Comparator<Stock>() {
@Override
public int compare(Stock o1, Stock o2) {
return new CompareToBuilder()
.append(o1.getPrice(), o2.getPrice())
.append(o1.getName(), o2.getName())
.append(o1.getSymbol(), o2.getSymbol())
.build();
}
};
Collections.sort(stockList, stockComparator);
stockList.forEach(System.out::println);
Comparator jest interfejsem funkcjonalnym, więc możemy skorzystać z wyrażenia lambda, aby jeszcze bardziej skrócić ten zapis:
Comparator<Stock> stockComparator = (o1, o2) -> new CompareToBuilder()
.append(o1.getPrice(), o2.getPrice())
.append(o1.getName(), o2.getName())
.append(o1.getSymbol(), o2.getSymbol())
.build();
Kolejną możliwością, jaką daje nam Java 8 i jej nowsze wersje, jest użycie Comparatora w metodzie interfejsu Stream – sorted:
List<Stock> sortedStocks = stockList.stream()
.sorted(stockComparator)
.collect(Collectors.toList());
sortedStocks.forEach(System.out::println);
Jeśli jesteśmy przy strumieniach, to warto poznać dwie przydatne metody z interfejsu Comparator: comparing i thenComparing. Możemy z nich skorzystać używając wywoływań łańcuchowych oraz referencji metod, a wszystko to w obrębie metody stream.sorted:
List<Stock> sortedStocks = stockList.stream()
.sorted(Comparator
.comparing(Stock::getPrice)
.thenComparing(Stock::getName)
.thenComparing(Stock::getSymbol))
.collect(Collectors.toList());
W przypadku Comparatora możemy również skorzystać z metody sort dostępnej bezpośrednio w interfejsie List – jest to alternatywa dla metody Collections.sort, która jako argument przyjmuje właśnie klasę typu Comparator:
stockList.sort(stockComparator);
Kiedy korzystać z klasy typu Comparator?
Klasa typu Comparator będzie szczególnie pomocna gdy:
- nie mamy bezpośredniego dostępu do klasy, której wartości pól chcemy porównywać, i w związku z tym nie jesteśmy w stanie dodać do niej metody
compareTo. Wówczas możemy utworzyć osobną klasę typuComparatorlub utworzyć anonimową klasę wewnętrzną w stosownym miejscu, - mamy dostęp do klasy, ale implementuje ona już interfejs Comparable, a my musimy posortować obiekty tej klasy według innego kryterium.
TreeSet i TreeMap
W Javie istnieją również dwie kolekcje, których działanie opiera się między innymi na sortowaniu elementów: TreeSet oraz TreeMap.
TreeSet
Kolekcja TreeSet to zbiór, który implementuje interfejs SortedSet. Elementy tej kolekcji będą sortowane według ich naturalnej kolejności (np. w przypadku elementów typu Integer, będą one uporządkowane rosnąco) lub w kolejności podanej przy tworzeniu zbioru. Mamy dwie możliwości określenia kolejności sortowania elementów:
- jeśli klasa, z której instancji są złożone elementy zbioru, implementuje interfejs Comparable , to elementy tego zbioru zostaną posortowane według kolejności określonej przez metodę
compareTow rzeczonej klasie, - przy deklaracji zbioru możemy w konstruktorze podać klasę typu Comparator i wtedy elementy zbioru będą posortowane zgodnie z logiką określoną w zaimplementowanej metodzie
compare.
Przykład tych dwóch implementacji kolekcji TreeSet:
Bez Comparatora w konstruktorze – w tym przypadku klasa Stock musi implementowac interfejs Comparable i nadpisywać metodę compareTo:
TreeSet<Stock> stockTreeSet1 = new TreeSet<>(); stockTreeSet1.add(stock1); stockTreeSet1.add(stock2); stockTreeSet1.add(stock3); stockTreeSet1.add(stock4); stockTreeSet1.add(stock5); stockTreeSet1.forEach(System.out::println);
Oraz z przekazaną instancją klasy typu Comparator w konstruktorze (korzystamy z utworzonej wcześniej instancji klasy typu Comparator i przekazujemy ją w konstruktorze):
TreeSet<Stock> stockTreeSet2 = new TreeSet<>(stockComparator); stockTreeSet2.add(stock1); stockTreeSet2.add(stock2); stockTreeSet2.add(stock3); stockTreeSet2.add(stock4); stockTreeSet2.add(stock5); stockTreeSet2.forEach(System.out::println);
TreeMap
Dość podobnie sprawy mają się w przypadku kolekcji TreeMap. Jest to mapa implementująca interfejs SortedMap. Jej klucze sortowane są według naturalnej kolejności, chyba że kluczami są obiekty klasy, która implementuje interfejs Comparable lub jeśli przy deklaracji mapy, w konstruktorze podamy Comparator:
TreeMap<Stock, String> stockStringTreeMap = new TreeMap<>(stockComparator); stockStringTreeMap.put(stock1, "stock 1"); stockStringTreeMap.put(stock2, "stock 2"); stockStringTreeMap.put(stock3, "stock 3"); stockStringTreeMap.put(stock4, "stock 4"); stockStringTreeMap.put(stock5, "stock 5"); stockStringTreeMap.keySet().forEach(System.out::println);
Podsumowanie
Jak wynika z powyższego wpisu – jest wiele różnych sposobów na sortowanie elementów kolekcji w Javie. To jakiego wyboru dokonamy, będzie najczęściej determinowane przez projekt w którym pracujemy, obiekty z jakimi mamy do czynienia, wydajność danego rozwiązania lub jeszcze inne czynniki. Najważniejsze żeby zdawać sobie sprawę z wachlarza dostępnych rozwiązań. Wówczas nic nie będzie nas w stanie zaskoczyć.
Kod z przykładami do powyższego wpisu znajdziesz na githubie.