Budowanie drzew w C#

Pomost pomiędzy strukturami płaskimi i hierarchicznymi

Hierarchie, biorąc pod uwagę obszar programowania, pojawiają się w bardzo wielu miejscach. Hierarchie są bowiem bardzo wygodne i przejrzyste. Mamy przecież strukturę pracowników, w której jest szef, potem pomniejsi kierownicy, a na dole zwykli szeregowi, od czarnej roboty. Mamy hierarchie czasowe z latami na najwyższym poziomie, kwartałami, miesiącami i dniami. Mamy jednostki organizacyjne i samorządowe. Mamy związki sportowe krajowe, wojewódzkie i regionalne. Mamy produkty, kategorie produktów i być może jeszcze inne parametry podziału sprzedawanych towarów.

Jest z drugiej strony potrzeba przechowywania takich struktur. Zdecydowana większość danych biznesowych przechowywana jest w jakiejś bazie danych, a zdecydowana większość tych baz danych jest relacyjna. Są wprawdzie bazy nierelacyjne, zdecydowanie bardziej hierarchiczne, ale suma wad i zalet nie jest wystarczająca. Bazy nierelacyjne przegrywają w kategorii popularności z bazami relacyjnymi. I tu pojawia się rozważany dzisiaj problem. Problem konwersji pomiędzy płaską listą rekordów pobieranych z relacyjnej bazy danych a drzewiastą strukturą, której obsługa przez proceduralne i obiektowe języki programowania jest znacznie wygodniejsza.

Tradycyjna reprezentacja drzew w relacyjnej bazie danych

Dane w bazie relacyjnej są umieszczone w tabelach. Tabela ma wiersze i kolumny. Jedna z kolumn, czasem kilka, definiują klucz główny. Wartości z kolumn klucza głównego dla rekordu jednoznacznie wskazują konkretny rekord. Inny obiekt, chcąc wskazać swojego rodzica, wskazują na ten klucz główny inną kolumną (innymi kolumnami w przypadku klucza złożonego). Taka relacja przybiera w wielu przypadkach następującą postać:

Struktura reprezentuje następujące drzewo:

Prezes
    Kierownik
        Pracownik A
        Pracownik B
    Szef
        Pracownik C
        Pracownik D

Zadaniem przedstawionych dzisiaj algorytmów będzie skonwertowanie reprezentacji płaskiej, listowej, bazodanowej na reprezentację drzewiastą, hierarchiczną.

Bazowa klasa drzewa

Rozwiązanie końcowe będzie dość złożone i uniwersalne. Na początek jednak posłużę się klasą, która będzie reprezentowała hipotetyczne drzewo. Nie będzie tam danych, a jedynym celem struktury będzie reprezentowanie relacji rodzic-dziecko. Przyjrzyjmy się klasie:

public class TreeNode<T>
{
    public TreeNode()
    {
        Items = new List<TreeNode<T>>();
    }

    public List<TreeNode<T>> Items { get; set; }
}

Klasa będzie oczywiście na tyle ogólna, żeby dało się przy jej pomocy opisywać różne typy. Każdy obiekt będzie zawierał listę potomków, każdy z tych potomków, sam będący przecież drzewem, znów może zawierać listę potomków. Takie drzewo wewnętrzne nazywa się również poddrzewem i taką nazwę będę stosował. Element główny, nie mający rodzica, konsekwentnie nazywany będzie drzewem lub drzewem głównym.

Przypuśćmy ponadto, że mamy do czynienia z jakąś strukturą gatunków zwierząt w postaci listy następujących obiektów:

public class Species
{
    public int ID { get; set; }
    public int ParentID { get; set; }
    public string Name { get; set; }
}

Załóżmy też, że pobraliśmy z bazy lub innego źródła następujące rekordy:

List<Species> species= new List<Species>()
{
    new Species(){ID = 1, ParentID = 0, Name = "Ssaki"},
    new Species(){ID = 2, ParentID = 1, Name = "Gryzonie"},
    new Species(){ID = 3, ParentID = 1, Name = "Torbacze"},
    new Species(){ID = 4, ParentID = 2, Name = "Kapibary"},
    new Species(){ID = 5, ParentID = 0, Name = "Ryby"},
    new Species(){ID = 6, ParentID = 5, Name = "Dorszowate"},
    new Species(){ID = 7, ParentID = 0, Name = "Ptaki"},
};

Przedstawioną listę należy teraz skonwertować do postaci drzewa. Mamy już bazową klasę drzewa i to jej zechcemy użyć. Poza kolekcją, którą już mamy potrzebujemy jeszcze kilku pól dodatkowych. Zastosujemy więc proste dziedziczenie:

class SpeciesNode : TreeNode<SpeciesNode>
{
    public int ID { get; set; }
    public string Name { get; set; }
}

Myślę, że do tego momentu wszystko jest jasne. Mamy klasę wykorzystywaną w strukturze płaskiej, z identyfikatorem rodzica, oraz klasę reprezentującą element drzewa, bez tego identyfikatora. Zrobiłem to celowo żeby pokazać, że klasy te mogą się od siebie różnić. Klasa elementu drzewa tworzona jest poprzez dodanie tylko tych elementów, które w tym drzewie rzeczywiście będą potrzebne.

Teraz można łatwo zdefiniować zadanie. Potrzebujemy funkcji GetTree:

IEnumerable result = GetTree(species, ???);

Funkcja powinna być jak najprostsza, ale też wystarczająco elastyczna. Tak, aby dało się konwertować nie tylko gatunki zwierząt.

Ogólna funkcja konwertująca

Jeden z parametrów jest z pewnością potrzebny - lista rekordów z gatunkami. Można oczywiście zastosować metodę rozszerzającą, ale ten parametr również tam będzie. Może w nieco zakamuflowany sposób, ale będzie. Co z resztą parametrów? Z pewnością będziemy potrzebować informacji o właściwości, która będzie kluczem głównym. Nie zawsze jest to właściwość ID i nie zawsze jest typu int. Jeżeli będzie się zmieniał klucz główny, zmieniać się będzie również klucz obcy, identyfikator rodzica. Mamy zatem kolejny argument. W końcu, zmieniać się może typ wyjściowy. Często chcemy aby reprezentacja rekordu w bazie danych nie była identyczna z rekordem w drzewie. Wymagana jest zatem jakaś konwersja pomiędzy tymi rekordami. Wobec powyższych rozważań otrzymujemy dość ogólną postać:

IEnumerable result = GetTree(IEnumerable, idProperty, parentIdProperty, typeConverter);

Taką wieloargumentowa funkcja mogłaby przyjąć postać podobną do napisanej poniżej:

static IEnumerable<NODE> GetTree<T, KEY, NODE>(
    IEnumerable<T> collection,
    Func<T, KEY> keySelector,
    Func<T, KEY> parentSelector,
    Func<T, NODE> converter)
    where NODE : TreeNode<NODE>
{
    Dictionary<KEY, NODE> lookup = new Dictionary<KEY, NODE>();
    List<NODE> result = new List<NODE>();

    foreach (var item in collection)
        lookup.Add(keySelector(item), converter(item));

    foreach (var item in collection)
    {
        NODE parentNode = null;
        lookup.TryGetValue(parentSelector(item), out parentNode);
        if (parentNode != null)
            parentNode.Items.Add(lookup[keySelector(item)]);
        else
            result.Add(lookup[keySelector(item)]);
    }

    return result;
}

Algorytm polega na utworzeniu tablicy z haszowaniem, gdzie kluczem jest identyfikator rekordu a wartością obiekt kolekcji po konwersji. W drugim przebiegu badane są wskazania na rodzica, gdzie mamy dwie możliwości. Jeżeli wskazanie pokrywa się z jakimś kluczem głównym, obiekt jest dzieckiem obiektu z tym właśnie kluczem. Jeżeli nie odnaleziono klucza, przyjmujemy, że jest to jeden z korzeni.

Wywołanie metody nie jest szczególnie trudne:

var result = GetTree(species, a => a.ID, a => a.ParentID, a => new SpeciesNode() { ID = a.ID, Name = a.Name });

W wielu przypadkach takie wywołanie można uprościć i tym zajmiemy się w dalszej części artykułu.

Upraszczanie funkcji do konwersji na drzewo

Cztery parametry, co pokazuje doświadczenie, sprawiają, że wywołania metod nie są zwykle czytelne. O ile trzy początkowe są krótkieW rozwiązaniu przyjęto zgodność typów identyfikatora i identyfikatora rodzica. Zdarza się, że identyfikator rodzica przyjmuje wartość NULL, co wprowadza drobne rozbieżności. W takim przypadku można skonwertować wartość typu prostego T na odpowiednik Nullable. Można też skonwertować wartość NULL na wartość typu prostego, przyjmując za identyfikator rodzica wartość nieistniejącą w zbiorze identyfikatorów: zwykle będzie to 0, int.MaxValue, int.MinValue., to nie można tego powiedzieć o czwartym.W wielu przypadkach najtrudniejszą i najbardziej złożoną funkcją przekazywaną w postaci parametru metody konwertującej drzewo będzie funkcja konwertująca.

Pomijanie funkcji konwertującej

Jeżeli obiekt w drzewie ma być tego samego typu lub wręcz tym samym obiektem, można sobie całe wywołanie nieco uprościć. Skorzystamy oczywiście z typów, które już mamy i funkcji, którą również mamy. Nasz obiekt będzie konwertowany na bardzo ogólny typ:

class GenericNode<T> : TreeNode<GenericNode<T>>
{
    public T Value { get; set; }
}

We właściwości Value klasy GenericNode<T> znajdzie się typ, który był wcześniej konwertowany. Typem listy potomków będzie natomiast sam typGenericNode<T>. Sama metoda konwertująca może być przeciążona w następujący sposób:

static IEnumerable<GenericNode<T>> GetTree<T, KEY>(
    IEnumerable<T> collection,
    Func<T, KEY> keySelector,
    Func<T, KEY> parentSelector)
{
    return GetTree(collection, keySelector, parentSelector, a => new GenericNode<T>() { Value = a });
}

Dzięki takiemu rozwiązaniu możliwe jest wywołanie bez konwersji:

var generic = GetTree(species, a => a.ID, a => a.ParentID);

Tracimy elastyczność, ale zyskujemy prostotę. Można pójść o krok dalej, i pozbyć się kolejnych parametrów.

Wykrywanie kolumny klucza i wskazania na rodzica za podstawie atrybutów

Przetwarzanie typów, na które nie mamy wpływu pociąga za sobą szereg ograniczeń. Jeżeli jednak typy są nasze, możemy przyjąć pewną konwencję i takie kolumny oznaczyć bezpośrednio w obiekcie. Popatrzmy na kolejny listing i sposób oznaczenia kolumn:

class KeyAttribute : Attribute
{
}

class ParentAttribute : Attribute
{
}

public class Species
{
    [Key]
    public int ID { get; set; }
    [Parent]
    public int ParentID { get; set; }
    public string Name { get; set; }
}

Teraz wystarczy tylko odpowiednio przebadać typ i pobrać z niego odpowiednie właściwości. Popatrzmy na przykładowe rozwiązanie:

static IEnumerable<NODE> GetTree<T, NODE>(
    IEnumerable<T> collection,
    Func<T, NODE> converter)
    where NODE : TreeNode<NODE>
{
    PropertyInfo keyProperty = null, parentProperty = null;
    try
    {
        keyProperty = typeof(T).GetProperties().Where(a => a.GetCustomAttribute<KeyAttribute>() != null).Single();
        parentProperty = typeof(T).GetProperties().Where(a => a.GetCustomAttribute<ParentAttribute>() != null).Single();
    }
    catch
    {
        throw new ConfigurationErrorsException(string.Format("KeyAttribute and ParentAttribute not found on type {0}. Composite keys are not supported.", typeof(T)));
    }

    return GetTree(collection, a => keyProperty.GetValue(a), a => parentProperty.GetValue(a), converter);
}

Pokazana metoda pozwala na rozpoznanie tylko kluczy składających się z pojedynczych kolumn (nie da się zdefiniować klucza na dwóch i więcej kolumnach), ale jest to w większości przypadków rozwiązanie wystarczające. Jeżeli chcemy skorzystać z domyślnego konwertera typów, możemy to zrobić w sposób następujący:

static IEnumerable<GenericNode<T>> GetTree<T>(IEnumerable<T> collection)
{
    return GetTree(collection, a => new GenericNode<T>() { Value = a });
}

Teraz konwersje mogą być wywoływane w następujący sposób:

var dynamicConverted = GetTree(species, a => new SpeciesNode() { ID = a.ID, Name = a.Name });
var dynamic = GetTree(species);

Można oczywiście zastosować inne rozwiązania i konwencje. Można przyjąć, że kolumna klucza jest automatycznie wybierana jeżeli jest to ID lub Id a kolumna wskazująca na rodzica ParentID lub ParentId. Można wyjść od drugiej strony i odnaleźć kolumnę ParentX oraz będącą w relacji kolumnę klucza X (np ParentID i ID, ParentCode i Code). Takie dopasowania szablonów, przy konsekwentnym stosowaniu, doprowadzają do bardzo przejrzystego kodu źródłowego.

Zamiast atrybutów można również użyć interfejsu i tam zdefiniować co jest kluczem, co wskazaniem na rodzica, a co kolekcją.

Konwersja w drugą stronę

Struktura drzewiasta ma dwie właściwości, o których trzeba wspomnieć:

1. Pozwala na szybki dostęp do podstawowych operacji na danych hierarchicznych: rozwijanie i wyświetlanie węzłów konkretnego rodzica, przeglądanie węzła w porządku definiowanym przez drzewo, to jest od rodzica do dzieci (preorder) oraz od dzieci do rodzica (postorder).
2. Tworzy problem konwersji pokazanych struktur do modelu relacyjnego. Możemy pobrać dane w postaci listy z bazy, skonwertować na drzewo, być może coś pozmieniać. Trzeba to potem zapisać.

Pierwszy punkt jest dobry i nie wymaga wyjaśnień. Jak się wkrótce okaże, drugi punkt, przy odpowiednich technikach, również okaże się zaletą. Nie jest to widoczne na pierwszy rzut oka, ale szybko wychodzi na wierzch podczas próby synchronizacji drzew połączonych relacjami w bazie.

Kategoria:C#