source: liacs/da/opdr2b/README@ 9

Beste allemaal,

Bij de tweede programmeeropdracht Datastructuren, najaar 2007 (Implementatie
en toepassing van de Trie) hebben jullie al een hele beschrijving op papier
gekregen, de officiele opdrachtspecificatie.
Voor onderdeel 2A van de opdracht moet je bestanden `trie.cc' en `trie.h'
maken die de Trie implementeren. Om te kunnen testen of die een beetje doen
wat je mag verwachten, is er een aantal testbestanden beschikbaar. De werking
daarvan zullen we hier uitleggen.
Aan het eind maken we ook nog een paar kleine opmerkingen over onderdeel 2B.

We beseffen dat het een heel verhaal is, net als de opdrachtspecificatie zelf,
maar het is toch verstandig om het door te lezen. Je kunt er meer tijd mee
uitsparen dan dat het lezen je kost.

********************************************************************************

* Er zijn 12 testbestanden voor onderdeel 2A:
    general0.h    -> hernoemen tot general.h
    showlist0.h   -> hernoemen tot showlist.h
    showlist0.cc  -> hernoemen tot showlist.cc
    leestekst0.h  -> hernoemen tot leestekst.h
    leestekst0.cc -> hernoemen tot leestekst.cc
    testtrie0.cc  -> hernoemen tot testtrie.cc
    Makefile0     -> hernoemen tot Makefile
    test0.dat     -> hernoemen tot test.dat
    test1.inv
    test1.con
    test2.inv
    test2.con
  De reden dat we 0-versies in het pakketje hebben gestopt, die jullie dan
  weer moeten hernoemen, is om ongewenste overschrijvingen te voorkomen bij
  het uitpakken van het pakketje. Je weet bijvoorbeeld maar nooit of jullie
  zelf ook al een bestand `testtrie.cc' hebben geschreven.

* Het belangrijkste bestand is `testtrie.cc'
  Dit programma biedt de gebruiker een menu aan waarin de verschillende
  methodes van de Trie aangeroepen kunnen worden. In het testprogramma is
  gekozen voor integers als informatieveld.

* Bij de methode GotoNode is het handig om te weten dat dan naar de knoop
  gegaan wordt die de laatste keer met GetNode verkregen is, tenzij deze
  knoop inmiddels met RemoveChild verwijderd is.

* Naast het aanroepen van de standaard methodes zijn er nog drie andere
  opties in het menu: `Show', `Show (2)' en `Opnieuw beginnen'. Deze laatste
  optie houdt in dat je opnieuw begint met een lege Trie. De andere twee
  opties zullen we wat uitgebreider toelichten.

* Allereerst: in principe doen `Show' en `Show (2)' exact hetzelfde.
  Alleen bij de automatische Test (zie daarover verderop) zijn ze een
  beetje verschillend, maar daar hoeven jullie niet over in te zitten.

* Tijdens het testen van het programma is het prettig als je de Trie die
  je in de loop van de tijd hebt opgebouwd, kunt afbeelden op het scherm.
  Daarvoor is de optie `Show' aanwezig.
  De optie maakt gebruik van een datastructuur die in `showlist.cc' en
  `showlist.h' is ge-implementeerd.
  Om de werking van de optie `Show' te demonstreren, bekijk de volgende
  uitvoer van de methode:
   0,
   0,a               1,b   2,c   3,d
   6,a   4,b         5,a   8*a
         9,a   7,c
        10,a
  Op het eerste niveau staat de wortel. Op het volgende niveau staan de
  kinderen van de wortel. In het voorbeeld zijn dit er vier. Bij deze
  kinderen stelt het getal voor de komma de waarde van het infoveld voor,
  het karakter na de komma geeft de tak aan via welke de knoop bereikt kan
  worden, de vader-tak zogezegd.
  Het eerste kind van de wortel heeft dus een infoveld 0 en kan vanuit
  de wortel bereikt worden via de tak `a', het tweede kind heeft een
  infoveld 1 en kan vanuit de wortel bereikt worden via de tak `b',
  enzovoort.

  De kinderen van een knoop x0 staan een niveau lager dan x0 zelf.
  Het eerste kind staat onmiddellijk onder x0; het tweede kind staat daar
  rechts van, het derde kind daar weer rechts van, enz. totdat je voorbij
  de broer van x0 loopt. De kinderen van `0,a' zijn dus `6,a' en `4,b'.
  Ofwel van de knoop `0,a' gaan uit: een tak `a' die eindigt in een knoop
  met infoveld 6 en tak `b' die eindigt in een knoop met infoveld 4.
  De knoop `6,a' heeft zelf geen kinderen, maar knoop `4,b' heeft weer
  twee kinderen: `9,a' en `7,c'. 

  Om het allemaal van de andere kant te bekijken: `10,a' is een kind van
  `9,a', `9,a' is een kind van `4,b', `4,b' is een kind van `0,a' en 
  `0,a' is ten slotte een kind van de wortel van de Trie.

  Omdat de wortel geen vader-tak heeft, zul je daar na de komma nooit een
  karakter zien staan (d.w.z.: er staat een spatie).

  Bij een (1) knoop in de Trie worden infoveld en karakter niet door een
  komma gescheiden, maar door een sterretje `*'. Dit betekent dat deze knoop
  de huidige knoop is, d.w.z.: hier bevindt zich het venster van de Trie.

  Niet geheel toevallig komt het gegeven voorbeeld overeen met de Trie in
  Figuur 1 van de opdrachtspecificatie. Alleen de wortel, die in de
  specificatie geen infoveld heeft, heeft hier een infoveld 0.

  Uiteraard is deze vorm van presenteren slechts overzichtelijk bij een
  beperkt aantal knopen. Als je te veel knopen hebt, kan een niveau meerdere
  regels beslaan en is het niet meer eenvoudig na te gaan hoe de vader-kind
  relaties lopen.

  N.B.: de optie `Show' maakt gebruik van een heleboel methodes van de Trie.
  Het is dus mogelijk dat ze pas werkt als je voor al die methodes een
  fatsoenlijke implementatie hebt.

* `testtrie.cc' maakt gebruik van enkele algemene constantes in `general.h'.
  Desgewenst kun je deze constantes ook in je eigen implementatie van de
  Trie gebruiken.

* Om `testtrie.cc' te compileren is er `Makefile'. Het compileren begint
  met het commando `make'. Vervolgens kun je het testprogramma aanroepen met
  `Test'

* De default is dat je je Trie interactief test. Dat kun je zien in het
  bestand `test.dat', waarin de variabele `InterActief' op 1 staat.
  Het is aan te raden om eerst op deze wijze een tijdje met het
  testprogramma te spelen en de verschillende opties uit te proberen.

* Als je het na een tijdje zat bent om steeds maar weer zelf menukeuzes
  en karakters in te typen, kun je `InterActief' op 0 zetten. Daarmee kies
  je voor een automatische Test.
  Bij de automatische Test wordt de invoer uit een bestand gelezen, in het
  bijzonder uit het bestand dat op de volgende regel staat (in principe is
  dat `test1.inv'). Verder wordt de uitvoer behalve naar het scherm ook voor
  een deel naar een bestand (`test1.uit') geschreven.
  Met behulp van `test1.inv' wordt de Trie uit ons voorbeeld, die uit
  Figuur 1 van de opdrachtspecificatie dus, opgebouwd en afgebeeld.

* Als dan de parameter `Controleren=0', gebeurt er niets met het
  uitvoerbestand `test1.uit'.

* Met `Controleren=1' wordt echter gekeken of het uitvoerbestand gelijk is
  aan het controlebestand `test1.con'. Zo ja, dan wordt er `GELIJK' op
  het scherm afgedrukt. Zo nee, dan wordt aangegeven waar het verschil zit.

* Om de implementatie van de Trie nog wat serieuzer te testen, is er ten
  slotte nog een tweede testinstantie meegegeven, bestaande uit `test2.inv'
  en `test2.con'. Als je in `test.dat' de naam van het invoerbestand even
  aanpast, kun je het testprogramma voor deze instantie draaien.
  Ook dit is echter geen ultieme test. Het kan best zijn je ook bij
  `test2.inv' GELIJK krijgt, terwijl de corrector nog fouten in je code
  ontdekt. Er kunnen bijvoorbeeld instanties zijn waar jullie implementatie
  de mist mee ingaat, en waar we van tevoren niet aan gedacht hebben.

* We raden je aan om niet te snel tot de automatische Test over te gaan.
  Zorg er eerst voor dat je weet wat alle opties in het menu doen.
  Zorg er vervolgens voor dat je begrijpt wat er zoal in `test1.uit'
  geschreven wordt.
  Als je zover bent, is het gemakkelijker om eventuele foutmeldingen te
  begrijpen.

* Overigens: de code van een aantal bestanden is een beetje versleuteld,
  omdat het eigenlijk niet de bedoeling is dat jullie daarin gaan kijken.
  Ze zijn puur bedoeld om te gebruiken.

* In principe zou het testprogramma (en ook de automatische Test) op ieder
  platform moet werken, dus bijvoorbeeld ook met Visual C++.

********************************************************************************

Om dubbele include-s te voorkomen is het in het algemeen aan te raden om je
code in `trie.h' en `trie.cc' te omgeven met een `ifndef'-constructie, dus
iets in de trant van:
  #ifndef TrieHVar
  #define TrieHVar

    ... code ...

  #endif
  
********************************************************************************

Het heeft geen zin om een implementatie van de Trie in te leveren die niet
door de automatische Test komt. Die krijg je linea recta terug. Vooralsnog
gaan we er namelijk vanuit dat er geen fouten in de automatische Test zitten.
Denk je dat er toch fouten in de testprogramma's of de testinstanties zitten,
dan kun je dit aankaarten bij Robert Brijder.

Wanneer je denkt dat je implementatie van de Trie goed is, kun je haar
electronisch inleveren bij de corrector, Ruben van Bodegom. In de opdracht-
specificatie staat aangegeven hoe je dat precies moet / kunt doen.

********************************************************************************

Het is de bedoeling dat je implementatie van de Trie gebruik maakt van
templates om verschillende types informatieveld mogelijk te maken.

Een neveneffect daarvan is dat je, bij gebruik van de Trie in een bepaalde
toepassing (ZLW compressie en decompressie bijvoorbeeld) de complete code
(`trie.cc' dus) moet includen in je programma van die toepassing.
Wanneer je gewoon de Trie los compileert naar een bestand `trie.o' en je
probeert dat te linken met een object bestand waarin variabelen van type
`Trie<int>' gebruikt worden, krijg je allemaal foutmeldingen.

********************************************************************************

* Er zijn 2 testbestanden voor onderdeel 2B:
    testzlw.in
    testzlw3.in
  Het eerste bestand is gewoon het voorbeeldbestand uit de opdracht-
  specificatie, het tweede bestand is een iets groter bestand. Na comprimeren
  en decomprimeren van deze bestanden, moet je exact dezelfde bestanden
  weer teruggekregen hebben.
  Uiteraard testen jullie je compressie- en decompressie ook nog met echt
  grote tekstbestanden.
  
* Wanneer je een origineel bestand vergelijkt met het uiteindelijke bestand,
  is het verstandig om ze niet alleen in een editor te bekijken, maar ook
  even naar de groottes van de beide bestanden te kijken. Sommige verschillen
  (spaties, End-of-Lines) zie je namelijk niet altijd in een editor, terwijl
  ze wel tot uiting kunnen komen in de bestandsgrootte.