Before a file can be transmitted over the Internet, the sender first needs to pass it through a splitter that chunks it into multiple segments. These segments are called packets. Each packet is then transferred individually across the Internet to the same receiver. If the receiver has collected all packets, it uses an assembler to reconstruct the original file.
The Internet uses packet switching1 to determine the route of the packets through the network. To prevent congestion it is often desirable that packets of the same file follow different routes through the network. As a result, those packets do not necessarily reach the receiver in their original order.
Moreover, the Internet is not flawless and it sometimes happens that packets never reach their destination or arrive late.
Assignment
In this assignment you have to implement a class Assembler that can be used to reconstruct messages from incoming packets. The location of a text file containing all incoming packets must be passed when instantiating new objects of the class Assembler. For example, such a text file could have the following content:
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.
Each line of the text file represents a single packet and contains four information fields that are separated by tabs:
-
unique code $$m \in \mathbb{N}$$ of the message the packet was derived from
-
packet index $$i \in \mathbb{N}$$; in splitting a message, each packed is sequentially indexed: the first packet has index 0 and the last packet has index $$p - 1$$
-
number of packets $$p \in \mathbb{N}_0$$ in which the message was split
-
text fragment (string) that itself does not contain tabs
The packets that originate from the same message may reach the receiver in random order and the text file does not necessarily has to contain all packets of that message. It is guaranteed that the text file never contains duplicate packets. The class Assembler must at least support the following methods:
-
A method isComplete that takes a number $$m \in \mathbb{N}$$. The method must return a Boolean value that indicates whether all packets of the message with unique code $$m$$ have reached the receiver.
-
A method completeMessages that takes no arguments. The method must return the set containing the unique codes of all messages whose packets have all reached the receiver.
-
A method incompleteMessages that takes no arguments. The method must return a dictionary whose keys are the unique codes of all messages whose packets have not all reached the receiver. Each key $$m$$ must be mapped onto a tuple $$(c_m, p_m)$$. The value $$c_m$$ is the number of packets of the message with unique code $$m$$ that have reached the receiver. The value $$p_m$$ is the number of packets into which the message with unique code $$m$$ was split.
-
A method message that takes a number $$m \in \mathbb{N}$$. In case not all packets of the message with unique code $$m$$ have reached the receiver, an AssertionError must be raised with the message incomplete message. Otherwise the method must return a string representation of all incoming packets in their original order. Each packet is on a separate line that contains the packet index, a dot (.), a space and the text fragment of the packet.
Example
In the following interactive session we assume the text files packets_01.txt2 and packets_02.txt3 to be located in the current directory.
>>> assembler = Assembler('packets_01.txt')
>>> assembler.isComplete(6220)
True
>>> assembler.isComplete(5181)
True
>>> assembler.isComplete(1234)
False
>>> assembler.completeMessages()
{6220, 5181}
>>> assembler.incompleteMessages()
{}
>>> print(assembler.message(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.message(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.message(1234)
Traceback (most recent call last):
AssertionError: incomplete message
>>> assembler = Assembler('packets_02.txt')
>>> assembler.isComplete(2997)
True
>>> assembler.isComplete(1938)
False
>>> assembler.isComplete(1234)
False
>>> assembler.completeMessages()
{9949, 6450, 7469, 2997}
>>> assembler.incompleteMessages()
{1938: (13, 17)}
>>> print(assembler.message(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.message(1938)
Traceback (most recent call last):
AssertionError: incomplete message
>>> assembler.message(1234)
Traceback (most recent call last):
AssertionError: incomplete message