##=== Zadanie Genealogia Wirusów ===

Biolog zajmujący się klasyfikowaniem wirusów potrzebuje klasy do manipulowania informacjami o ich genealogii. Nowy wirus powstaje przez mutację jakiegoś znanego wirusa. Może też powstać przez zmutowanie połączenia więcej niż jednego wirusa. Genealogia wirusa jest grafem skierowanym acyklicznym o jednym źródle, które reprezentuje wirusa macierzystego. Wierzchołek grafu odpowiada konkretnej mutacji wirusa. Krawędź łączy wirusa z bezpośrednio otrzymaną z niego mutacją.

Należy zaimplementować szablon klasy, która reprezentuje taki graf.

template <typename Virus> VirusGenealogy;

Klasa Virus reprezentuje informacje o wirusie. Jej implementacja zostanie dostarczona w stosownym czasie (w trakcie testów).

###Klasa VirusGenealogy powinna udostępniać następujący interfejs.

// Tworzy nową genealogię. Tworzy także węzeł wirusa macierzystego o identyfikatorze stem_id.

VirusGenealogy(Virus::id_type const &stem_id);

// Zwraca identyfikator wirusa macierzystego.

Virus::id_type get_stem_id() const;

// Zwraca iterator pozwalający przeglądać listę identyfikatorów bezpośrednich następników wirusa o podanym identyfikatorze. Zgłasza wyjątek VirusNotFound, jeśli dany wirus nie istnieje. Iterator musi spełniać koncept bidirectional_iterator oraz typeid(*v.get_children_begin()) == typeid(const Virus &).

VirusGenealogy<Virus>::children_iterator get_children_begin(Virus::id_type const &id) const;

// Iterator wskazujący na element za końcem wyżej wspomnianej listy. Zgłasza wyjątek VirusNotFound, jeśli dany wirus nie istnieje.

VirusGenealogy<Virus>::children_iterator get_children_end(Virus::id_type const &id) const;

// Zwraca listę identyfikatorów bezpośrednich poprzedników wirusa o podanym identyfikatorze. Zgłasza wyjątek VirusNotFound, jeśli dany wirus nie istnieje.

std::vector<Virus::id_type> get_parents(Virus::id_type const &id) const;

// Sprawdza, czy wirus o podanym identyfikatorze istnieje.

bool exists(Virus::id_type const &id) const;

// Zwraca referencję do obiektu reprezentującego wirus o podanym identyfikatorze. Zgłasza wyjątek VirusNotFound, jeśli żądany wirus nie istnieje.

const Virus& operator[](Virus::id_type const &id) const;

// Tworzy węzeł reprezentujący nowy wirus o identyfikatorze id powstały z wirusów o podanym identyfikatorze parent_id lub podanych identyfikatorach parent_ids. Zgłasza wyjątek VirusAlreadyCreated, jeśli wirus o identyfikatorze id już istnieje. Zgłasza wyjątek VirusNotFound, jeśli któryś z wyspecyfikowanych poprzedników nie istnieje.

void create(Virus::id_type const &id, Virus::id_type const &parent_id);

void create(Virus::id_type const &id, std::vector<Virus::id_type> const &parent_ids);

// Dodaje nową krawędź w grafie genealogii. Zgłasza wyjątek VirusNotFound, jeśli któryś z podanych wirusów nie istnieje.

void connect(Virus::id_type const &child_id, virus::id_type const &parent_id);

// Usuwa wirus o podanym identyfikatorze. Zgłasza wyjątek VirusNotFound, jeśli żądany wirus nie istnieje. Zgłasza wyjątek TriedToRemoveStemVirus przy próbie usunięcia wirusa macierzystego.

void remove(Virus::id_type const &id);

Zakładamy, że:

• klasa Virus ma konstruktor przyjmujący argument typu Virus::id_type;
• klasa Virus ma metodę Virus::id_type get_id() const;
• typ Virus::id_type ma konstruktor bezargumentowy, konstruktor kopiujący, operator przypisania;
• wartości typu Virus::id_type tworzą porządek liniowy i można je porównywać za pomocą operatorów <=>, ==, !=, <=, >=, <, >.

Ponadto:

• wszystkie metody klasy VirusGenealogy powinny gwarantować silną odporność na wyjątki, a tam, gdzie to jest możliwe i pożądane, powinny być no-throw;
• próba użycia konstruktora kopiującego lub operatora przypisania dla obiektów klasy VirusGenealogy powinna zakończyć się błędem kompilacji;
• zachowanie obiektu typu VirusGenealogy po utworzeniu cyklu pozostaje niezdefiniowane – nie trzeba wykrywać takiej sytuacji;
• wyjątki VirusAlreadyCreated, VirusNotFound oraz TriedToRemoveStemVirus powinny być zdefiniowane poza klasą VirusGenealogy i powinny publicznie dziedziczyć po std::exception;
• wyszukiwanie wirusów powinno być szybsze niż liniowe.

Zarządzanie pamięcią powinno być zrealizowane za pomocą sprytnych wskaźników z biblioteki standardowej.

##== Przykład użycia ==

Przykład użycia znajduje się w pliku virus_example.cc. Powinien wypisać na standardowe wyjście:

VirusNotFound

VirusAlreadyCreated

TriedToRemoveStemVirus

##== Ustalenia techniczne ==

Rozwiązanie będzie kompilowane poleceniem

g++ -Wall -Wextra -O2 -std=c++20 *.cc

Będziemy sprawdzać poprawność zarządzania pamięcią za pomocą valgrinda.

Jako rozwiązanie należy dostarczyć plik virus_genealogy.h, który należy umieścić w repozytorium w katalogu

grupaN/zadanie5/ab123456+cd123456

lub

grupaN/zadanie5/ab123456+cd123456+ef123456

gdzie N jest numerem grupy, a ab123456, cd123456, ef123456 są identyfikatorami członków zespołu umieszczającego to rozwiązanie. Katalog z rozwiązaniem nie powinien zawierać innych plików. Nie wolno umieszczać w repozytorium plików dużych, binarnych, tymczasowych (np. *.o) ani innych zbędnych.