101: Organizacja struktury drzewa.

Ostatnie dwa dni spędziłem na przygotowywaniu kodu odpowiedzialnego za przechowywanie wpisów wewnątrz struktury drzewa. W tym czasie zupełnie zmieniły się założenia z poprzedniego wpisu. Zamiast tworzenia klas ldbEntry i ldbBase, które będą samodzielne odpowiedzialne za wszystkie funkcje bazy danych, postanowiłem rozbić to na mniejsze części, działające na zupełnie innych założeniach.

Jednak od początku. Zanim przystąpiłem do pracy nad pierwotnym projektem rozpisałem sobie założenia, jakie system porządkujący wpisy w strukturę drzewa powinien spełniać:

• umożliwia dodanie wpisu na końcu obecnej linii postów
• dodanie odgałęzienia od obecnego postu
• dodanie wpisu w danej linii zaraz za obecnym postem
• usunięcie wpisu z zachowaniem jego potomków
• usunięcie wpisu wraz z jego potomkami
• prosta nawigacja po strukturze drzewa (ruch w dół i w górę, wskazanie początku i końca gałęzi dla danego wpisu)
• jak najmniejsza złożoność czasowa wszystkich operacji

Pierwszy pomysł wydawał się dość prosty, jednak skuteczny: stworzyć klasę ldbEntry, która będzie przechowywać wszystkie informacje o poście, a w celu ich porządkowania dodać właściwości Predecessor i Parent, które jednoznacznie będą określać położenie wewnątrz drzewa. Dodatkowo należało stworzyć klasę ldbBase, która w vectorze będzie trzymać wszystkie wpisy, a w kopcach indeksy wpisów posortowane w taki sposób, żeby indeksy na kolejnych pozycjach odpowiadały wpisom o coraz większym ID poprzednika (Predecessor) lub przodka (Parent).

Po dłuższym zastanowieniu stwierdziłem, że pomysł ten ma więcej wad niż zalet. Kopce utrudniały dostanie się do pojedynczych wpisów przez właściwość inną niż ID. Niemożliwe było znalezienie następnego postu w linii bez przerzucenia całego vectora lub kopca. Usunięcie wpisu było już w ogóle porażką, ponieważ wymagało to przekierowania następnego wpisu na poprzednika usuwanego postu - czyli znowu trzeba przerzucić cały kopiec. Masakra.

Wymyśliłem jednak nowy sposób przechowywania wpisów, który prawie automatycznie porządkował je w drzewo i umożliwiał prostą nawigację, co oznaczało także proste dodawanie, usuwanie i modyfikację postów. Od razu wziąłem się za testową implementację.

Na czym jednak polega pomysł? Także jest dość prosty: tworzymy klasę Vertex, przechowującą własne ID, wskaźnik na przodka (Vertex* Parent) oraz wskaźniki na wszystkich potomków (std::vector Children). Umożliwia to:

• dodawanie postów w dowolnym miejscu w czasie stałym
• usuwanie postów wraz z potomkami w czasie stałym
• usuwanie postów z zachowaniem potomków w czasie liniowo zależnym od liczby bezpośrednich potomków
• ruch w górę i w dół hierarchii drzewa w czasie stałym
• odnalezienie granic linii postów dla danego wpisu w czasie liniowo zależnym od długości linii
• bezproblemowe przechowanie 10 milionów postów wszerz i wzdłuż (nie sprawdzałem większej ilości, ponieważ wyprodukowanie takiej liczby wymaga pisania stu wpisów dziennie przez blisko 274 lata)

Słowem - cud, miód i orzeszki. Mimo wszystko nie obyło się bez problemów. Odezwał się chyba brak wprawy w implementowaniu tego typu struktur i płynności w operowaniu wskaźnikami. Doprowadziło to do tego, że napisanie niecałych dwustu linii kodu zajęło mi dwa dni. Cóż takiego poszło nie tak?

Inicjalizuj wskaźniki!

TreeVertex* curr;
while (!curr->isLeaf())
{
  curr = curr->getDeeper(0);
}

Znalezienie tego błędu zajęło mi pół godziny. Niezainicjalizowany wskaźnik curr powodował, że ten fragment kodu zapętlał się w nieskończoność.

Uważaj na średniki!

A przynajmniej myśl, kiedy pętlę while zamieniasz w do..while. Przykład:

/* Przed zmianą */
do
{
  cout << curr->getID() << ": ";
  curr->showBranches();
  curr = curr->getDeeper(0);
} while(!curr->isLeaf());

/* Po zmianie */
while(!curr->isLeaf());
{
  cout << curr->getID() << ": ";
  curr->showBranches();
  curr = curr->getDeeper(0);
}

Bezmyślne przekopiowanie warunku pętli wiązało się z przekopiowaniem także średnika. Ponownie - zapętlenie programu w nieskończoność i kolejna godzina szukania problemu.

Pamiętaj o ustawionych strażnikach!

Aby mieć łatwą kontrolę nad liniami postów ustaliłem, że wskaźnik Children[0] będzie odpowiadał za następny post w linii, a pozostałe indeksy w vectorze Children za odgałęzienia. Z racji tego, że rozwidlenia mogą pojawić się nawet na ostatnim poście w linii, indeks 0 był edytowany oddzielnie od pozostałych. W konstruktorze inicjalizowany był na NULL, co oznaczało, że jest liściem - ostatnim postem w linii (nawet jeżeli odgałęziały się od niego inne posty). Z kolei usunięcie danego posta wiązało się z przekierowaniem wskaźnika na przodka w następnym poście i wskaźnika na następny post u przodka. Kod za to odpowiedzialny wyglądał tak:

Parent->setSuccessor(Children[0]);
Children[0]->setParent(Parent);

Druga linijka prowadzi do naruszenia ochrony pamięci w wypadku, gdy dany post jest liściem (Children[0] == NULL).

Sprawdzaj wartości logiczne!

Może to dość oczywiste, jednak zawsze należy zadbać nie tylko o to, by funkcja typu bool zwracała różne wartości logiczne w odpowiednich przypadkach, ale wracała odpowiednie wartości.

bool TreeVertex::isLeaf()
/* returns TRUE if its line successor (Children[0]) is NULL
           FALSE otherwise */
{
  return (bool)Children[0];
}

Oczywiście, funkcja zwraca różne wartości logiczne wtedy kiedy trzeba. Szkoda tylko, że przez moje niedopatrzenie zwraca fałsz, gdy post jest liściem.

Cóż, trwało to dość długo, jednak ostatecznie kod powstał i z dumą mogę ogłosić, że ukończony został pierwszy etap pierwszej fazy projektu, czyli gotowa jest wersja 0.1.1, która mimo wszystko niewiele potrafi. Gdyby ktoś miał ochotę pobawić się istniejącym kodem, to spis wszystkich obsługiwanych komend wyświetla się po wprowadzeniu komendy h.