Spis treści:

Kategoria:C#


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:

Aplikacja z prostym drzewem w WPF
Aplikacja WPF z prostym drzewem otrzymanym po konwersji.

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#

, 2013-12-20

Brak komentarzy - bądź pierwszy

Dodaj komentarz
Wyślij
Ostatnie komentarze
Dzieki za rozjasnienie zagadnienia upsert. wlasnie sie ucze programowania :).
Co się stanie gdy spróbuję wyszukać:
SELECT * FROM NV_Airport WHERE Code='SVO'
SELECT * FROM V_Airport WHERE Code=N'SVO'
(odwrotnie są te N-ki)
Będzie konwersja czy nie znajdzie żadnego rekordu?