Wanneer een bestand over het Internet verstuurd wordt, dan wordt het aan de kant van de verzender eerst door een splitter opgedeeld in kleinere segmenten. Die segmenten worden pakketten genoemd. Alle pakketten worden daarna individueel over het Internet verstuurd naar dezelfde ontvanger. Als de ontvanger alle pakketten van het bestand heeft ontvangen, dan gebruikt hij een assembler om het originele bestand te reconstrueren.
Het Internet gebruikt packet switching1 om de route van de pakketten doorheen het netwerk te bepalen. Daarbij is het vaak wenselijk dat de pakketten van hetzelfde bestand verschillende routes volgen om opstopping te voorkomen. Als gevolg daarvan bereiken die pakketten de ontvanger niet noodzakelijk in hun originele volgorde.
Bovendien is het Internet niet feilloos en gebeurt het wel eens dat pakketten hun bestemming nooit of pas zeer laat bereiken.
Opgave
In deze opgave moet je een klasse Assembler implementeren die boodschappen kan reconstrueren op basis van binnengekomen pakketten. Bij het aanmaken van objecten van de klasse Assembler moet de locatie van een tekstbestand doorgegeven worden dat alle binnengekomen pakketten bevat. Zo een tekstbestand ziet er bijvoorbeeld als volgt uit:
6220 1 10 Because he's the hero Gotham deserves, 6220 9 10 5181 5 7 in time, like tears in rain. Time to die. 6220 3 10 So we'll hunt him. 6220 5 10 Because he's not a hero. 5181 6 7 5181 2 7 shoulder of Orion. I watched C-beams 5181 4 7 Gate. All those moments will be lost 6220 6 10 He's a silent guardian. 5181 3 7 glitter in the dark near the Tannhäuser 6220 7 10 A watchful protector. 5181 1 7 believe. Attack ships on fire off the 6220 0 10 We have to chase him. 5181 0 7 I've seen things you people wouldn't 6220 4 10 Because he can take it. 6220 2 10 but not the one it needs right now. 6220 8 10 A Dark Knight.
Elke regel van het tekstbestand stelt één enkel pakket voor en bestaat uit vier informatievelden die van elkaar gescheiden worden door tabs:
-
unieke code $$m \in \mathbb{N}$$ van de boodschap waaruit het pakket komt
-
volgnummer $$i \in \mathbb{N}$$ van het pakket; bij het opdelen van een boodschap worden pakketten opeenvolgend genummerd: het eerste pakket heeft volgnummer 0 en het laatste pakket heeft volgnummer $$p - 1$$
-
aantal pakketten $$p \in \mathbb{N}_0$$ waarin de boodschap werd opgedeeld
-
tekstfragment (string) dat zelf geen tabs bevat
De pakketten van eenzelfde boodschap komen in willekeurige volgorde voor en het tekstbestand moet niet noodzakelijk alle pakketten van die boodschap bevatten. Hetzelfde pakket komt echter nooit meerdere keren voor. De klasse Assembler moet minstens de volgende methoden ondersteunen:
-
Een methode isVolledig waaraan een getal $$m \in \mathbb{N}$$ moet doorgegeven worden. De methode moet een Booleaanse waarde teruggeven die aangeeft of alle pakketten van de boodschap met unieke code $$m$$ zijn binnengekomen.
-
Een methode volledigeBoodschappen waaraan geen argumenten kunnen doorgegeven worden. De methode moet een verzameling teruggeven met de unieke codes van alle boodschappen waarvan alle pakketten zijn binnengekomen.
-
Een methode onvolledigeBoodschappen waaraan geen argumenten kunnen doorgegeven worden. De methode moet een dictionary teruggeven waarvan de sleutels gevormd worden door de unieke codes van alle boodschappen waarvan niet alle pakketten zijn binnengekomen. Elke sleutel $$m$$ moet afgebeeld worden op een tuple $$(c_m, p_m)$$. De waarde $$c_m$$ geeft aan hoeveel pakketten van de boodschap met unieke code $$m$$ zijn binnengekomen. De waarde $$p_m$$ geeft aan in hoeveel pakketten de boodschap met unieke code $$m$$ werd opgedeeld.
-
Een methode boodschap waaraan een getal $$m \in \mathbb{N}$$ moet doorgegeven worden. Indien niet alle pakketten van de boodschap met unieke code $$m$$ zijn binnengekomen, dan moet een AssertionError opgeworpen worden met de boodschap onvolledige boodschap. Anders moet de methode een string teruggeven die de binnengekomen pakketten van de boodschap in hun oorspronkelijke volgorde weergeeft. Hierbij staat elk pakket op een afzonderlijke regel, die het volgnummer van het pakket bevat, gevolgd door een punt (.), een spatie en het tekstfragment van het pakket.
Voorbeeld
Bij onderstaande voorbeeldsessie gaan we ervan uit dat de tesktbestanden pakketten_01.txt2 en pakketten_02.txt3 zich in de huidige directory bevinden.
>>> assembler = Assembler('pakketten_01.txt')
>>> assembler.isVolledig(6220)
True
>>> assembler.isVolledig(5181)
True
>>> assembler.isVolledig(1234)
False
>>> assembler.volledigeBoodschappen()
{6220, 5181}
>>> assembler.onvolledigeBoodschappen()
{}
>>> print(assembler.boodschap(6220))
0. We have to chase him.
1. Because he's the hero Gotham deserves,
2. but not the one it needs right now.
3. So we'll hunt him.
4. Because he can take it.
5. Because he's not a hero.
6. He's a silent guardian.
7. A watchful protector.
8. A Dark Knight.
9.
>>> print(assembler.boodschap(5181))
0. I've seen things you people wouldn't
1. believe. Attack ships on fire off the
2. shoulder of Orion. I watched C-beams
3. glitter in the dark near the Tannhäuser
4. Gate. All those moments will be lost
5. in time, like tears in rain. Time to die.
6.
>>> assembler.boodschap(1234)
Traceback (most recent call last):
AssertionError: onvolledige boodschap
>>> assembler = Assembler('pakketten_02.txt')
>>> assembler.isVolledig(2997)
True
>>> assembler.isVolledig(1938)
False
>>> assembler.isVolledig(1234)
False
>>> assembler.volledigeBoodschappen()
{9949, 6450, 7469, 2997}
>>> assembler.onvolledigeBoodschappen()
{1938: (13, 17)}
>>> print(assembler.boodschap(2997))
0. Did you ever hear the tragedy of Darth
1. Plagueis the Wise? I thought not. It's not a
2. story the Jedi would tell you. It's a Sith
3. legend. Darth Plagueis was a Dark Lord of the
4. Sith so powerful and so wise, he could use the
5. Force to influence the midichlorians to
6. create life...He had such a knowledge of the
7. dark side that he could even keep the once he
8. cared about from dying. The dark side of the
9. Force is a pathway to many abilities some
10. consider to be unnatural. He became so
11. powerful...The only thing he was afraid of was
12. losing his power. Which eventually, of course,
13. he did. Unfortunately, he taught his
14. apprentice everything he knew, then his
15. apprentice killed him in his sleep. Ironic,
16. he could have others from death, but not
17. himself.
18.
>>> assembler.boodschap(1938)
Traceback (most recent call last):
AssertionError: onvolledige boodschap
>>> assembler.boodschap(1234)
Traceback (most recent call last):
AssertionError: onvolledige boodschap