O sortowaniu kolekcji typów generycznych słów kilka

Dzisiaj zaprezentuję dostępne na platformie .NET mechanizmy służące do sortowania kolekcji typów generycznych. Jako przykładowej kolekcji użyjemy klasy List<T>.
Na początek weźmy pod lupę metodę Sort() klasy List<T> oraz jej przeciążone wersje:
1. Bezparametrowa Sort() – do sortowania wykorzystuje interfejs IComparable<T>
2. Sort(IComparer<T> comparer) – wykorzystująca interfejs IComparer<T>
3. Sort(int index, int count, IComparer<T> comparer) – jak poprzednia, ale pozwala sortować wybrane fragmenty listy.
4. Sort(Comparison<T> comparison) – używająca mechanizmu delegacji
Dla przykładu użyjemy klasy zawierającej informacje o filmie:
public class Movie { private int _id; private string _title; private string _director; private int _year; private string _genre; public int ID { get { return _id; } set { _id = value; } } public string Title { get { return _title; } set { _title = value; } } public string Director { get { return _director; } set { _director = value; } } public string Genre { get { return _genre; } set { _genre = value; } } public int Year { get { return _year; } set { _year = value; } } public Movie(int id, string title, string director, string genre, int year) { _id = id; _title = title; _director = director; _genre = genre; _year = year; } public override string ToString() { return string.Format("ID: {0}, Name: {1}, Director: {2}, Genre: {3}, Year: {4}", _id, _title, _director, _genre, _year); } }
Utworzymy również kolekcję filmów:
var movies = new List(); movies.Add(new Movie(1, "Szeregowiec Ryan", "Steven Spielberg", "Dramat", 1998)); movies.Add(new Movie(2, "Patriota", "Roland Emmerich", "Akcja", 2000)); movies.Add(new Movie(3, "Forest Gump", "Robert Zemeckis", "Komedia", 1994)); movies.Add(new Movie(4, "Regulamin zabijania", "William Friedkin", "Thriller", 2000))
Teraz w celu posortowania kolekcji wywołamy metodę Sort() bez żadnych parametrów:
movies.Sort();
Niestety po uruchomieniu programu otrzymamy informację o wystąpieniu wyjątku InvalidOperationException z komunikatem: „Failed to compare two elements in the array”. Wyjątek ten został zgłoszony, ponieważ nasza klasa nie implementuje interfejsu IComparable, wymaganego przez metodę Sort(). Przez to kompilator nie ma pojęcia, w jaki sposób (po których polach) ma posortować nasze obiekty. Aby kolekcja obiektów naszej klasy dała się posortować, musimy samodzielnie zaimplementować interfejs IComparable. Wszystkie typy proste np. int i string mają wbudowaną implementację tego interfejsu. Należy on do przestrzeni nazw System a jego jedyną składową jest metoda CompareTo():
public int CompareTo(Movie other)
Metoda ta zwraca wartość typu int według poniższego schematu:
Zwracana wartość | Warunek |
Liczba mniejsza od zera | Obiekt bieżący < other |
Zero | Obiekt bieżący = other |
Liczba większa od zera | Obiekt bieżący > other |
Obiekt w nawiasie (other) jest porównywany z bieżącym obiektem klasy (this) implementującej metodę CompareTo(). Zwracana wartość całkowita reprezentuje wynik porównania. Poniżej zmiany, które należy wprowadzić do naszej klasy:
public class Movie : IComparable<Movie> { [...] public int CompareTo(Movie other) { if (this.ID > other.ID) return 1; else if (this.ID < other.ID) return -1; else return 0; } [...] }
Po zaimplementowaniu interfejsu możemy już wykorzystywać bezparametrową metodę Sort naszej listy.
movies.Sort();
Pokazane rozwiązanie umożliwia nam sortowanie elementów według wartości wybranego na stałe wcześniej pola. Aby zmienić sposób sortowania, należy dokonać zmiany w kodzie metody CompareTo, uwzględniając nowe pole, po którym będzie sortowali. Następnie ponownie skompilujemy program, aby zmiany zostały uwzględnione.
Bardziej realistyczne i elastyczne podejście pozwoli nam na sortowanie elementów według wielu pól. W tym celu możemy wykorzystać interfejs IComparer do utworzenia klas porównujących dwa obiekty naszej klasy lub delegację Comparison<T>.
Interfejs IComparer należy do przestrzeni nazw System.Collections.Generic. Przypomina trochę interfejs IComparable. Również udostępnia tylko jedną składową, ale za to dwuargumentową metodę Compare(). Metoda ta zwraca wartość -1, 0 lub 1 w zależności od tego, czy pierwszy obiekt jest odpowiednio mniejszy, równy lub większy od drugiego. Składnia tej metody jest następująca:
public int Compare(Movie x, Movie y)
Sortowanie kolekcji za pomocą interfejsu IComparer wymaga od nas utworzenia odrębnej klasy, która po tym interfejsie będzie dziedziczyła:
public class MovieCompareByTitle : IComparer<Movie> { public int Compare(Movie x, Movie y) { return string.Compare(x.Title, y.Title); } }
Wywołanie metody sort:
movies.Sort(new MovieCompareByTitle());
lub
movies.Sort(2, 2, new MovieCompareByTitle());
Drugi sposób posortuje tylko 2 kolejne elementy naszej listy począwszy od elementu trzeciego.
Analogicznie możemy utworzyć klasy do sortowania po pozostałych polach klasy Movie. Ich kod jest dostępny w przykładowej aplikacji.
Pozostał już tylko do omówienia ostatni sposób sortowania, który wykorzystuje mechanizm delegacji, mianowicie: Comparison<T>. Reprezentuje on metodę, która porównuje dwa obiekty tego samego typu, a jej składnia wygląda następująco:
public delegate int Comparison<in T>(T x, T y)
Do posortowania możemy wykorzystać:
1. metodę anonimową, gdzie treść umieszczana jest bezpośrednio w wywołaniu innej metody
movies.Sort(delegate(Movie x, Movie y) { return x.Genre.CompareTo(y.Genre); });
2. metodę zdefiniowaną w innym miejscu naszego kodu
movies.Sort(CompareByDirector); [...] private static int CompareByDirector(Movie x, Movie y) { return x.Director.CompareTo(y.Director); } [...]
3. metodę anonimową, gdzie delegacja umieszczona jest bezpośrednio w kodzie naszej klasy Movie
public class Movie : IComparable<Movie> { [...] public static Comparison<Movie> TitleComparison = delegate(Movie x, Movie y) { return x.Title.CompareTo(y.Title); }; [...] } [...] movies.Sort(Movie.TitleComparison); [...]
4. metodę utworzoną w ciele klasy Movie o sygnaturze odpowiadajcej delegacji Comparision<T>:
public class Movie : IComparable<Movie> { [...] public static int DirectorComparison(Movie x, Movie y) { return x.Director.CompareTo(y.Director); } [...] } [...] movies.Sort(Movie.DirectorComparison); [...]
Warto zauważyć, że dwie ostatnie metody (klasy Movie) nie odwołują się do żadnych składowych obiektu, więc można je zadeklarować jako statyczne.
Platforma .NET oddaje w nasze ręce kilka mechanizmów umożliwiających sortowanie naszych własnych klas. To, który sposób wybierzemy, zależy już od tylko nas i specyfiki projektu, nad którym aktualnie pracujemy.
Przykładowy kod zamieszczam do pobrania poniżej.
Trackbacks/Pingbacks
[…] jednym z poprzednich wpisów (link) pokazałem Wam mechanizmy platformy .NET służące do sortowania kolekcji typów generycznych. […]