Intranet: Algoritmen I

Zowel Linux als Windows gebruiken hiërarchische bestandssystemen. In deze reeks maken we een eenvoudig bestanssysteem in C++, als toepassing op boomstructuren.

Er zijn twee soorten knopen: bestanden en mappen. Elke knoop heeft een naam en elke knoop (behalve de 'wortel' of 'root') heeft een ouder (=map). Een map kan een lijst kindknopen bevatten (zowel bestanden als 'submappen').

Maak klassen Knoop, Map en Bestand. Sla de kindknopen op in een vector van knooppointers, en de ouders als mappointers. We spreken af dat een boomwortel als ouder 0 (NULL) heeft. De naam wordt aan de constructor(en) meegegeven. De ouder is by default null, maar kan gewijzigd worden bij het toevoegen aan een map (zie verder).

Voor de eenvoud heeft een bestand een inhoud van het type std::string (maar daar gaan we niet veel mee doen in deze oefening).

Om snel te kunnen navigeren in de boomstructuur wordt de ouder-kind-informatie dubbel bijgehouden: zowel in ouder- als in kindpointers. Dat is natuurlijk potentieel gevaarlijk. Wat als een bestand beweert in een map te zitten, maar de map denkt daar anders over?
Om de consistentie af te dwingen kun je er bv. voor zorgen dat setOuder niet publiek is, maar enkel door Map opgeroepen kan worden (bij het toevoegen van een kindknoop).

Merk op dat de klassen Knoop en Folder elkaar moeten kennen (resp. voor ouder- en kind-pointers). Je zult merken dat dergelijke circulaire relatie in C++ niet zo makkelijk te implementeren is, omdat, in tegenstelling tot Java, de volgorde van declaraties/definities in C++ van belang is (behalve binnen een klasse). Je zult forward declaraties nodig hebben, en niet alle methodes zullen inline gedefinieerd kunnen worden.

Functionaliteit

Ter illustratie: het testprogramma bestandsystest.cpp zou deze output moeten genereren.

opm.

voor alle onderstaande opgaven mag je hulpmethodes maken, liefst private of protected).

maak waar mogelijk de methodes const!

Maak een (virtuele) logische methode is_map(). Die kan handig door andere methodes gebruikt worden, omdat je in C++ geen instanceof hebt (tenzij je gebruik maakt van RTTI).

Maak een methode get_dirnaam() die de naam van de knoop teruggeeft, gevolgd door een schuine streep ('/') indien de knoop een map is.

Maak in Knoop een methode get_padnaam() die de volledige padnaam teruggeeft, gescheiden met schuine streepjes ('/'). Probeer dit op een elegante manier te implementeren.

Maak in Map een methode schrijf_lijst() die de 'dirnamen' van de kindknopen uitschrijft (zoals in de commando's 'ls' of 'dir').

Maak in Map een methode schrijf_boom() die recursief de 'dirnamen' van alle kindknopen uitschrijft. Per niveau worden er twee spaties ingesprongen. Hoe heet deze manier van doorlopen van de boom?

Bezoekers

Er bestaan verschillende manieren om een boom te doorlopen (bv. pre-order, post-order, level-order). Wat er precies moet gebeuren met elke 'bezochte' knoop varieert van toepassing tot toepassing (bv. uitschrijven, tellen, ...). We kunnen de methode schrijf_boom veralgemenen tot een methode bezoek_preorder waaraan we een functie of functie-object meegeven dat 'iets doet' met de bezochte knopen. Dit is een toepassing van het visitor design pattern.

Er zijn in C++ drie manieren om functies/functie-objecten als parameter te gebruiken:

zoals in C, met function-pointers
zoals in Java, op de object-geöriënteerde manier, als een instantie van een klasse die een bepaalde interface (of abstracte klasse) implementeert (denk bv. aan ActionHandler in Java Swing)
via templates

Alle hebben ze voor- en nadelen.

Maak in Knoop een geparametrizeerde recursieve methode bezoek_preorder(bezoeker), waarbij bezoeker van het type BEZOEKER (template-parameter) is. Bezoek eerst de 'huidige knoop', en behandel dan (indien de knoop een map is) de kindknopen.
Opgelet: template-methodes kunnen niet virtual zijn!!

Test bv. uit met een bezoekerfunctie zoals

void schrijf_knoop(Knoop *knoop)
{
    cout << knoop->get_dirnaam() << " ";
}

Hoe kun je deze methode gebruiken om het aantal knopen in een (deel)boom te tellen?

Pre-order en post-order zijn eigenlijk twee varianten van diepte-eerst doorlopen. Level-order komt overeen met breedte-eerst doorlopen. Dit wordt later nog besproken bij grafen.

Maak een methode bezoek_diepte_eerst(bezoeker) waarbij bezoeker een pointer naar (een afgeleide van) KnoopBezoeker is, met

struct KnoopBezoeker
{
    virtual void pre (Knoop *n, int niveau) = 0;
    virtual void post(Knoop *n, int niveau) = 0;
};

Vóór het behandelen van de kindknopen wordt de pre-actie toegepast, en ná het behandelen de post-actie. Opgelet: ook voor gewone bestanden (niet-mappen) worden deze methodes toegepast!
De parameter niveau geeft de diepte van de bezochte knoop aan, relatief t.o.v. de oorspronkelijke knoop waarop de methode opgeroepen werd (die heeft dus niveau nul).

Maak een knoopbezoeker die de knopen in post-order uitschrijft, telkens met vermelding van niveau.

Maak een knoopbezoeker die de diepte van de (deel)boom bepaalt.

De knopen worden aangemaakt in het hoofdprogramma en pointers ernaar toegevoegd aan mappen. De vraag stelt zich of de boom de knopen moet dealloceren (deleten). Dat is een kwestie van afspraak. In principe kan de boom niet weten hoe de knopen gemaakt zijn: dat kan dynamisch (met new) of statisch (gewone lokale variabele). In het eerste geval moet er gedelete worden, in het tweede geval juist niet. Het zou dus meest voor de hand liggen dat de gebruiker (hoofdprogramma) de boom(wortel) kan vragen om (recursief) al zijn knopen te deleten. Kun je dit verwezenlijken met bezoek_diepte_eerst??

R. Stoop 22/03/2010