The goal of this assignment is to practice reading, understanding, and testing unfamiliar code. But first… Last week, you implemented the Suppose, instead, that we wanted our coin game classes to keep track of whose turn it is, to enforce the order of play (perhaps by requiring each move to specify who is playing it), and to be able to tell us who has won when the game is over. For this exercise, you will consider how to modify the interface design to support these new features. You need not implement this new interface. Ann has a lot of books. So many books, in fact, that she has to store them in several places: Her desk has a mere 3 shelf-feet of book capacity. In the living room, she can store an additional 18 shelf-feet of books. Books that don’t fit on either bookshelf are relegated to the attic. Like any good computer scientist, Ann is lazy, so she wants to minimize trips from her desk to the living room, and moreso minimize trips to the attic. Thus, Ann would like to keep the books that she’s most likely to use soon on her desk, with less likely books in the living room, and the least likely books of all in the attic. When Ann wants a book that is already by her desk, she can access it quickly, but if the book is in the living room, she needs to go fetch it. To make room on her desk, she must return a book to the living room. (We won’t worry about the attic from here on out, though the situation is similar. And then there’s the storage unit…) And when this happens, Ann needs to figure out which book to evict from her desk to make room for the next book that she requires. Optimally, she would always evict the book that she’ll need again furthest in the future, but that’s difficult to predict, so instead Ann is considering a number of different book management policies: She might choose to evict the book that has been on her desk the longest. (She calls this the FIFO policy.) Or, she might choose to evict the book that she has looked at least recently. (This is the LRU policy.) She is also considering a variation of the FIFO policy where instead of evicting the oldest book, she gives it a second chance, and only evicts it if it reaches the head of the queue again without being used. (This is the Clockpolicy, and don’t worry if you don’t understand it just yet.) To try out the different book caching policies, Ann coded them up as Java classes that implement a Ann is rather impatient, so the Ann implemented all three policies, as classes Now Ann needs your help. She’s currently working on reimplementing the Read and understand the Download the Implement the Write tests for Ann’s implementation of All code for this problem set should be placed in the Software Archeology
2 An Interface Design Exercise
CoinGame interface with two different sets of rules. As designed, the interface says nothing about players or turns—it merely tracks the state of the game from move to move, and it’s totally oblivious towho takes each turn.
CoinGame interface to support keeping track of players, turns, and the winner. The interface should support an arbitrary number of players (two or more).3 Too Many Books
ReplacementPolicy interface. The interface is generic, with a type parameter K that stands for whatever kind of items it’s being used to manage—in this case, books (or some way to refer to them, such as titles or ISBNs). The interface declares only three methods:
int capacity() returns the capacity of the cache—that is, the number of books she can fit on her desk.1int size() returns the size of the cache—that is, the number of books on her desk currently.K require(K) is where all the action happens. It takes the name of an item—the book that Ann wants to read next, whether on her desk or in the living room—and returns the item to evict, if necessary, to make room. If the requested item is already in the cache, or if the cache isn’t full yet, then this method returns null.require(K) method must run in worst-case capacity()3.1 Disaster!
FIFOQueue, LRUQueue, and Clock, but then disaster struck. She lost the source code and tests for LRUQueue, but not the compiled Java .class file. She lost the source code and .class file forFIFOQueue, but not the tests. The Clock code, fortunately, is safe, and the Javadoc output for all three classes survived as well; both may be handy as a reference.LRUQueue class. To speed things up, she’d like you to implement the FIFOQueue class and to write tests for her LRUQueue class. Since the LRUQueue.class object file survived the disaster, you will be able to run your tests on that code (though like I said, the source isn’t available). Once you have a good number of tests, Ann will use your test suite to validate her new LRUQueue implementation, and hopefully your tests will catch any bugs.3.2 Your Task
Clock and ClockTest classes. You don’t need to write anything, but you may find the knowledge handy later. (Note that Clock is implemented using low-level arrays, but you are free to use classes from theJava Collections framework such as LinkedList and HashSet for your code.)pset04.jar JAR file containing the compiled LRUQueue class and add it to your project’s classpath. (How to do this will depend on your IDE, and help will be available on Piazza.)FIFOQueue class, as documented here. The class should have one constructor, FIFOQueue(int), which takes the capacity of the queue (i.e., how many items can fit at once). The minimum allowed capacity is 1, so any smaller argument should result in an IllegalArgumentException being thrown. FIFOQueueTest contains an example, and you should add more tests there as you see fit.LRUQueue (as documented here) in a JUnit 4 test class LRUQueueTest. Run your tests against the provided binary implementation of LRUQueue—all of them should pass. Be sure to write sufficient tests that you will catch any plausible bugs that Ann might write. Your tests will be run against several buggy LRUQueue implementations, and you will be graded on how many bugs your tests catch—but they also need to pass when class under testing is correct.edu.neu.ccs.cs3500.pset04 package.
