练习Linked list的使用方法，代写实现一个简易的浏览图像的程序。
Goals
The goals of this assignment are to:
- Understand, implement, and use linked chains of nodes.
- Write classes that implement Java interfaces.
- Gain experience working with Java references.
- Implement exceptions and understand the difference between checked and unchecked exception.
Description
In this assignment, your goal is to build an image viewer application with cache (i.e. CacheImageApp).
Computer networks are integral to all aspects of our lives. We routinely use these networks without giving a second thought to how a web of interconnected machines successfully conveys our information and that of millions of others. For this assignment, we’ll explore how computer networks ensure successful data transmission. Specifically, this program will simulate the transmission of an image over a computer network. You’ll be coding the receiver (i.e. SingleImageReceiver) that gets information packets from a simulated network and reconstructs an image file. We’ve already coded the image file’s sender and network simulator.
To transmit an image file, it is divided into numerous small data packets that are sent across the network. The reality is that networks are complicated and not very reliable. Packets might be lost or duplicated (to make life easier, packets are not corrupted in this assignment), and if that wasn’t enough, they arrive at the receiver out of order! To address this, a sequence number is given to each packet. This simple approach can be used to determine if there are any missing or duplicate packets, and also to arrange the received packets in the correct order to properly reconstruct the file.
As the receiver, your job is to collect all these packets, remove duplicates, request any that are missing, and put them in order by sequence number so that the image can be opened without errors. For missing packets, you’ll need to request re-transmission. The packets are stored in a singly-linked list with a header node but without a tail node. The data item for each node is one packet. If you’ve done your job well, you will have reconstructed the entire file as a complete and properly sequenced chain of packets so that it can be opened by our image viewer for you to see the picture. The following figure illustrates this process.
But sometimes an image file may be very large or the network may be very slow. And you may wish to request the same image many times. As it is really time-consuming to receive and reconstruct an image in this way again and again, your program will address this issue by using a cache. In computing, a cache is hardware or software that stores data so future requests for that data can be served faster.
What you need to do is first check whether the image is already in the cache when you want to receive an image file. If the image’s linked list is already in the cache, you don’t need to receive and reconstruct it again. If the image chain is not in the cache of image linked lists, you will receive it, and store its name and linked list in the cache. The following is the structure of the cache.
Specifications
Important Classes
PacketLinkedList Class
This class stores a sequence of packets and and is used to reconstruct the image file. It implements the methods defined in ListADT interface. Note: The ListADT interface in this program extends Iterable, so your list classes must also implement methods in Java’s java.lang.Iterable interface.
Iterating over lists is done with a PacketLinkedListIterator object (See next class description). The data structure used to create its iterator is a singly-linked chain of Listnode objects, where the Listnode sent to create the Iterator is the header node. There is no tail reference.
PacketLinkedListIterator Class
Instances of this class are used to iterate through a PacketLinkedList object. The iterator has direct access to the PacketLinkedList’s chain of nodes.
It’s constructor accepts a Listnode (that is a header node). It implements the methods defined in Java’s java.lang.Iterator interface, but it does not support the remove() operation.
SingleImageReceiver Class
Instances of the class simulate a receiver for a single image by maintaining an image buffer, which is a linked list of packets of the transmitted image file. It collects packets from our InputDriver and reconstructs and stores the image file packets.
The reconstructFile() method gets packets from the InputDriver queue. To get incoming packets, call the askForNextPacket() method until your receiver receives End-of-Streaming Notification (see the section below for details).
For best results, develop your program incrementally.
Initially, accept the packets in the order received and add them to the image buffer without any additional processing (e.g., do not yet remove duplicates or reorder). Once you are able to collect packets until the End-of-Streaming notification, then work on adding code to remove duplicates and place data items in the correct order.
Thus, at the start, packets from the InputDriver can be listed as 1, 2, 5, 4. This means you’ll get four packets in the order shown with sequence numbers 1, 2, 5 and 4 respectively. Another example of packets coming from the InputDriver is 1, 2, 1, 1, 3, 6, 5, 7. As you can see, packet 1 has duplicates. If these were put in order with duplicates removed into the image buffer you’d have 1 -> 2 -> 3 -> 5 -> 6 -> 7. The desired sequence starts from number 1 (one) and increases by one for every subsequent packet in image transmission. In this example, packet 4 is missing, so you need to ask for retransmitting for it.
We’ve provided displayList to help with your debugging, but you will still be graded on it working as specified (Note: there is a whitespace after each comma in the format. You should strictly follow this format as we TAs will grade this part very strict). Once you’ve correctly implemented the receiver image viewer, you must comment out the displayList call since it is just for debugging.
CacheImageApp Class
This is the main class that starts the program execution and simulates an image viewer application with a cache. The main method creates an instance of this class (to minimize the use of static methods). Users can choose to quit or receive an image file in the console.
The retrieveImage method first checks whether the image is in the cache. If it is in the cache, you don’t need to receive and reconstruct it again. Instead, you get its packetLinkedList from the cache (i.e. cachePacketLinkedList). Otherwise, you should create a SingleImageReceiver object to receive this image and then store its name and list in the cache.
Once you believe you’re correctly processing the packets, you can try to open the image file to display it. We suggest you don’t try opening the image until you’re getting close to a working program (comment out the call to openImage in the main method). The openImage method you code uses a method with the same name in our ImageDriver class, and that method will display the image in a window frame for you to see. If you give our openImage method an image file that has not been properly reconstructed, then it will throw an exception. In this case, you can use displayList() method to debug.
Two Challenges of Reconstruction
Duplicate Packets
In the normal transmission of packets it is typical that duplicate packets are received (having the same sequence number). There are two main reasons of duplicate packets:
- Receiver detects that the packet is damaged and asks for re-transmission.
- Sender thinks a packet might be lost and re-sends it, but the original arrives late.
When receiver finds there are duplicate packets, it typically keeps the first to arrive and discards any that arrive later. Therefore, in this assignment, you should only keep the first one.
Missing Packets
Packets occasionally do get lost in the transmission through a network. In this assignment, you’ll detect whether there are any missing packets after receiving a special End-of-Streaming Notification Packet. Once you have received this special packet, then you can determine how many packets were supposed to be received and determine if any are missing. Call askForMissingPacket(int seq) by specifying the sequence number of which packet is missing notifying the sender to resend the missing packet. These re-transmitted packets can still be duplicated, and possibly missing so you’ll need to repeat the packet processing until you have all necessary packets.
End-of-Streaming Notification
The last packet in a file transmission is a special packet called “End-of-Streaming Notification”. The network protocol needs this special packet so the receiver can determine when to end the current data transmission. It is like an EOF (End-Of-File) marker used with file I/O.
For example, an image file is divided into 32 packets. As a receiver, you don’t know how many packets are incoming until the sender sends this special packet. This packet contains no data and has a negative sequence number, which corresponds to the total number of packets for the image file. For this example, the special End-of-Streaming Notification would have a sequence number of -32. This packet is not added to the image buffer. Instead, it is used to determine how many packets should have been received. Use this number to determine if any packets are missing. For instance, if your image buffer only has packet sequences 1 to 30, you’ll know the last two were lost in transmission.
The End-of-Streaming Notification might also be lost. If the InputDriver returns null when calling askForNextPacket() that means there are no moreincoming packets. If you have not obtained the End-of-Streaming Notification then it was lost. You’ll need to call askForMissingPacket(int seq) but using the special sequence number 0 to have the End-of-Streaming Notification re-transmitted. Be careful to only ask for this to be re-transmitted when there are no more incoming packets. If you ask for re-transmission when there are packets remaining to be processed, a RuntimeException is thrown.
Input/Output
As for Input, this program requires no command-line argument. Instead, it requires console input (input that user types at keyboard). You don’t need to download any image files as we’ve provided the InputDriver class that you’ll use to get packets for the image file through a simulated network. There are nine “secret images” as the samples you can use with this program, which are named in this form “secretN.jpg” (where N = 0, 1, .., 8). On Eclipse, you would start the program by running the CacheImageApp java program in your Program 2 project files.
As for Output, we’ve provided the ImageDriver class that displays the image if you provide it with a complete and correctly reconstructed image buffer (PacketLinkedList). This class uses your PacketLinkedListIterator to access the image file your program reconstructs so this iterator class must be correctly implemented beforehand. The ImageDriver is used by the CacheImageApp class’s openImage() method.
The following is a sample Input/Output sequence:.
Enter 0 to quit or image filename: secret0.jpg
Retrieve Image = secret0.jpg
Loading image from buffer...
Enter 0 to quit or image filename: secret8.jpg
Retrieve Image = secret8.jpg
Loading image from buffer...
Enter 0 to quit or image filename: secret8.jpg
Retrieve Image = secret8.jpg
Loading image from buffer...
Enter 0 to quit or image filename: 0
Program End.
You will need to complete the program to see the images.
Note all the image files are automatically obtained by our InputDriver program. Duplicate packets are possible for each of these files.
- secret 0 - 1: small images with no missing packets.
- secret 2 - 3: median images with no missing packets
- secret 4 - 6: median images with missing packets
- secret 7 - 8: large images with missing packets, which should only be used when your program works for the other images.
Program Flow
The main method of the program constructs a CacheImageApp object and waits for user’s console inputs.
- If the user inputs “0”, the program terminates.
- If the user inputs a valid image name, the program
- calls retrieveImage method to get the linked list for this image. If the image is in the cache, it returns its packetLinkedList from the cache. Otherwise, a SingleImageReceiver object is created to receive the image and then store it in the cache.
- calls openImage method to open the image file and display the image if source file is not damaged; otherwise, it should throw the appropriate exception, which will crash the main program. (You may still be able to see the corrupted image in the viewer frame if the damaged part is not the header even though the program crashes.)3. continues the main menu loop to wait for additional input
- If the user inputs an invalid image name, the program
- display the appropriate message (see samples)
- continues the main menu loop to wait for another input to process.