Konwersja listy na drzewo
Pomiędzy światem relacyjnym, a obiektowym
Wiele obiektów świata rzeczywistego może być pokazanych w sposób hierarchiczny. Na świecie są kontynenty zawierające państwa, państwa podzielone na stany, landy, województwa lub jeszcze coś innego, nasze województwa dzielą się na powiaty, gminy. W strukturze firmy mamy głównego kierownika, kierowników działów, kierowników brygad i zwykłych pracowników. W sklepie mamy działy, grupy produktów i produkty. Raport może być pokazany z podziałem na rok, na kwartały, miesiące, dni. Te wszystkie hierarchie muszą być w jakiś sposób przetwarzane. Dane reprezentujące te hierarchie muszą być gdzieś zapisane. W złożonych systemach jest to najczęściej relacyjna baza danych i jej tabele, niekoniecznie przypominające strukturę drzewa. Z drugiej strony, obiektowej, bardziej naturalną reprezentacją drzew są obiekty z listami swoich potomków. Takie reprezentacje można w bajecznie prosty sposób powiązać z gotowymi kontrolkami reprezentującymi drzewa i cieszyć się szybkim efektem w postaci bajkowego interfejsu użytkownika. Niektóre typy aplikacji wymagają wielokrotnych konwersji pomiędzy dwoma typami list, a to z kolei sugeruje napisanie pewnej ogólnej metody lub klasy. Tym zajmę się dziś.
Różne rodzaje struktur wejściowych
Przymierzając się do, wydawać by się mogło, prostej konwersji można dojść do pewnego przerażającego wniosku - istnieje dużo różnych sposobów reprezentacji drzew, różne typy kluczy, różne sposoby nazywania kolekcji i właściwości. Jeżeli klasa lub metoda ma być uniwersalna, wszystko to musi być uwzględnione w algorytmie. Przeanalizujmy po kolei wszystkie elastyczne
komponenty.
- Typ obiektu wejściowego i wyjściowego
- Typ obiektu wejściowego może się różnić od typu obiektu wyjściowego. Typ wejściowy będzie miał najczęściej identyfikator i identyfikator rodzica, który wskazuje na relację. Typ wyjściowy będzie zawierał kolekcję potomków, nieobecną w typie wejściowym. Typy zostaną przekazane techniką typów ogólnych (ang. generic).
- Metoda konwertująca typy
- Obecność dwóch różnych typów pociąga za sobą konieczność konwersji. W pokazanym przykładzie będzie to realizowane przez wyrażenie lambda (funkcję). Da to jednocześnie możliwość wykonania pewnych rzutowań (liczby całkowite na typy wyliczeniowe), ustawienia dodatkowych właściwości i wykonania innych inicjalizacyjnych zadań.
- Różne kolekcje i sposoby dodawania elementów
- W pokazanym dalej przykładzie wykorzystana zostanie funkcja lambda wskazująca kolekcję, ale nie jest to jedyne rozwiązanie. Kolekcja może być rozpoznana dynamicznie, może być oznaczona atrybutem. Można pójść jeszcze dalej i wskazać metodę, która będzie wywoływana podczas wstawiania kolejnego elementu. Można również pomyśleć o pewnym rozszerzeniu i dodaniu referencji do rodzica - to również może być zrealizowane przy pomocy metody.
- Wskazanie wierzchołka drzewa
- Różne obiekty mogą różnie reprezentować relację rodzic - potomek. Identyfikator rodzica może być ustawiony na 0, może tam być NULL, może tam być jeszcze inna specjalna, magiczna wartość. Ta informacja również musi być dostarczona z zewnątrz.
- Właściwość reprezentująca identyfikator (klucz)
- Identyfikator różnych typów może mieć dowolną nazwę i praktycznie dowolny typ. Nie można tego zaszyć wewnątrz klasy tworzącej drzewo.
- Właściwość reprezentująca wskazanie na rodzica
- Wskazanie na rodzica to kolejny przykład pełnej dowolności w zakresie nazwy i typu. Powiem nawet więcej - typ właściwości może być różny od typu klucza (np. para int i int?).
Wszystkie te wymogi uniwersalności sprawiają, że do klasy konwertującej należy przekazać w najlepszym wypadku kilka dodatkowych informacji. Przyjrzyjmy się zatem przykładowej strukturze hierarchicznej, którą będziemy przetwarzać.
Przykład drzewa w postaci listy
Popatrzmy na dwie klasy, które będziemy przetwarzać. Reprezentują one obszary geograficzne tworzące prostą hierarchię:
public class Area { public int ID { get; set; } public int? ParentID { get; set; } public string Name { get; set; } public override string ToString() { return Name; } } public class AreaNode { public int ID { get; set; } public string Name { get; set; } public List<AreaNode> Children { get; set; } public override string ToString() { return Name + (Children.Count > 0 ? " (" + string.Join(", ", Children) + ")" : ""); } }
Klasa Area reprezentuje element listy, natomiast klasa AreaNode reprezentuje obiekt drzewa. Popatrzmy jeszcze na przykładową definicję takiej listy:
List<Area> input = new List<Area>() { new Area(){ID=1, Name="Europa"}, new Area(){ID=2, ParentID=1, Name="Polska"}, new Area(){ID=3, ParentID=2, Name="Podkarpackie"}, new Area(){ID=4, ParentID=3, Name="Rzeszów"}, new Area(){ID=5, Name="Azja"}, new Area(){ID=6, ParentID=5, Name="Laos"}, new Area(){ID=7, ParentID=3, Name="Mielec"}, new Area(){ID=8, ParentID=3, Name="Łańcut"}, new Area(){ID=9, ParentID=3, Name="Sanok"}, new Area(){ID=10, ParentID=5, Name="Wietnam"}, new Area(){ID=11, ParentID=3, Name="Tarnobrzeg"}, new Area(){ID=12, ParentID=3, Name="Kolbuszowa"} };
Podobną listę można oczywiście pobrać bezpośrednio z bazy danych i taka droga będzie pewnie najczęstszym przypadkiem. Przejdźmy do implementacji samej klasy.
Klasa do konwersji listy na drzewo
Na początku wpisu przedstawiłem różne problemy, które wynikają z próby uniwersalnego, ujednoliconego traktowania wszystkich, albo większości, struktur danych. Mając na uwadze wszystkie te rozważania można stworzyć coś na kształt poniższej klasy:
//T - typ wejściowy, element listy //Node - typ wyjściowy, węzeł drzewa public class TreeList<T, Node> { //Lista wejściowa private List<T> InputList { get; set; } //Funkcja konwersji pomiędzy typami private Func<T, Node> Converter { get; set; } //Funkcja wskazująca kolekcję potomków private Func<Node, ICollection<Node>> CollectionSelector { get; set; } public TreeList( List<T> inputList, Func<Node, ICollection<Node>> collectionSelector, Func<T, Node> converter) { InputList = inputList; CollectionSelector = collectionSelector; Converter = converter; } public List<Node> ToTree<Key>( Func<T, bool> rootSelector,//Wskazuje korzeń Func<T, Key> keySelector,//Wskazuje klucz Func<T, Key> parentSelector)//Wskazuje rodzica where Key : IComparable { var nodes = new Dictionary<Key, DictionaryElement>(); List<Node> result = new List<Node>(); //Pierwszy przebieg - przygotowanie słownika foreach (var item in InputList) { var node = Converter(item); var key = keySelector(item); nodes.Add(key, new DictionaryElement() { ListItem = item, TreeItem = node }); } //Drugi przebieg - konstruowanie drzewa foreach (var node in nodes) { if (rootSelector(node.Value.ListItem)) { result.Add(node.Value.TreeItem); } else { var parentKey = parentSelector(node.Value.ListItem); //Pobierz rodzica, wydobądź z niego kolekcję i dodaj do niej węzeł CollectionSelector(nodes[parentKey].TreeItem).Add(node.Value.TreeItem); } } return result; } //Klasa pomocnicza, element słownika private class DictionaryElement { public T ListItem { get; set; } public Node TreeItem { get; set; } } }
Klasa została skromnie skomentowana, zwłaszcza w tych, moim zdaniem, bardziej kluczowych fragmentach. Wspomniałem wcześniej, że część logiki i konfiguracji została przeniesiona poza klasę. Tym bardziej warto przyjrzeć się sposobowi użycia klasy.
Klasa konwertująca drzewa w działaniu
Wywołanie metody klasy może się na pierwszy rzut oka wydać skomplikowane. Popatrzmy na przykład:
var tree = new TreeList<Area, AreaNode>(input, a => a.Children, a => new AreaNode() { ID = a.ID, Name = a.Name, Children = new List<AreaNode>() }); var result = tree.ToTree(a => !a.ParentID.HasValue, a => a.ID, a => a.ParentID.Value);
Gdybyśmy obejrzeli wyniki konwersji otrzymalibyśmy taki oto rezultat:
//result[0] Europa (Polska (Podkarpackie (Rzeszów, Mielec, Łańcut, Sanok, Tarnobrzeg, Kolbuszowa))) //result[1] Azja (Laos, Wietnam)
Nawiasy oznaczają relację zawierania. Warto przyjrzeć się implementacji metody ToString i przekonać się, że drzewo jest zbudowane prawidłowo.
Wydajność rozwiązania
Algorytmy przetwarzające drzewa często opierają się na rekurencji. To prawda, że i ten problem dałoby się rozwiązać przy pomocy funkcji wywołującej samą siebie i dla każdego podelementu wyszukiwać listę jego dzieci. Dla małych list byłoby to nawet rozsądne. Problem w tym, że w żaden sposób nie udałoby się osiągnąć liniowej złożoności całego algorytmu. Aby przekonać się, że pokazany algorytm jest bardzo sprawny, można wykonać pewien test. Potrzebna będzie duża lista reprezentująca drzewo, powiedzmy 100000 elementów. Jak ją wygenerować? Na początek lista dwupoziomowa, płaska:
Random r = new Random(); List<Area> largeTree = new List<Area>(); for (int i = 0; i < 100000; i++) { largeTree.Add(new Area() { ID = i, Name = i.ToString(), ParentID = i < 10 ? null : (int?)r.Next(10) }); }
Taka dwupoziomowa lista reprezentująca drzewo w środowisku testowym wykonywała się około 75 ms. To wyjątkowo mało, biorąc pod uwagę pokaźne rozmiary drzewa. Nie wiem, czy kiedykolwiek będzie potrzeba wczytania takiego drzewa i wyświetlania go w interfejsie użytkownika. Takie ilości danych nie są do opanowania i ogarnięcia przez zwykłego użytkownika. Co ważne, czas konwersji w żaden sposób nie zależy od głębokości drzewa. Gdybyśmy przekazali drzewo podobnych rozmiarów i z większą liczbą poziomów, czas byłby taki sam. Ci, którzy chcą się przekonać, mogą wygenerować sobie bardziej złożoną strukturę:
Random r = new Random(); List<Area> largeMultilevel = new List<Area>(); for (int i = 0; i < 100000; i++) { largeMultilevel.Add(new Area() { ID = i, Name = i.ToString(), ParentID = i < 10 ? null : (int?)r.Next(i) }); }
Czas powinien być porównywalny.
Czy da się coś zrobić z liczbą przekazywanych parametrów? Jest ich dużo - trzy w konstruktorze i trzy w metodzie ToTree. Da się, pod warunkiem, że przyjmiemy pewne ograniczenia. Można zastosować jakiś interfejs, który zapewni jakąś spójność klas. Można założyć, że kolekcja potomków będzie zawsze nosiła nazwę Children, klucz będzie typu int i będzie miał nazwę ID. Wskazanie na rodzica będzie typu int? i będzie nosiło nazwę ParentID. Do dość częste przypadki. Odważnym założeniem byłoby użycie tego samego typu wejściowego i wyjściowego unikając w ten sposób konwersji. Można także przenieść instrukcje (parametry) z konstruktora i metody ToTree do atrybutów, którymi dekorowane będą klasy, ale wymaga ingerencji w te klasy. Można również zastosować pewne konwencje i dynamicznie generować niektóre operacje. Można w końcu połączyć wszystkie te metody i pozwolić na korzystanie z prostszych, być może nawet bezparametrowych funkcji, w pewnych standardowych przypadkach oraz pokazanej w przykładzie dla przypadków niekonwencjonalnych. Pozostawiam to, na dzień dzisiejszy, do samodzielnego opracowania.
Wykorzystanie struktury drzewa w WPF
Drzewiaste struktury z kolekcjami potomków mogą być w prosty sposób wykorzystane w interfejsie użytkownika. Przyjrzyjmy się przykładowej implementacji interfejsu w WPF:
<TreeView x:Name="treeArea"> <TreeView.ItemTemplate> <HierarchicalDataTemplate ItemsSource="{Binding Children}"> <TextBlock Text="{Binding Name}"/> </HierarchicalDataTemplate> </TreeView.ItemTemplate> </TreeView>
Należy pamiętać, aby do kontrolki wstawić otrzymany po konwersji rezultat:
treeArea.ItemsSource = result;
Tak niewielka ilość kodu pozwala na otrzymanie prostego drzewa:
Profesjonalne implementacje wymagałyby jeszcze odpowiedniego stylu. Nie zajmowałem się tym, bo nie jest to tematem wpisu.
Podsumowanie
Pokazana implementacja klasy konwertującej listę na drzewo jest pewnym szablonem. Dla prostych rozwiązań można ją obudować w coś bardziej przystępnego zmniejszając liczbę parametrów, dla bardziej wymyślnych rozwiązań pewnie dodać jeszcze jedną funkcję zależną od postawionych wymagań i sposobu konwersji. Zachęcam też to próby realizacji tego samego zadania w sposób rekurencyjny lub oszacowanie złożoności takiego rekurencyjnego rozwiązania dla różnych wartości głębokości drzew. To bardzo dobre ćwiczenie, wyrabiające właściwy nawyk podczas projektowania różnych rozwiązań.
Kategoria:C#
Brak komentarzy - bądź pierwszy