Queues Solution

Overview




In this project, you’ll exercise your understanding of queues and recursion. You’ll implement an unbounded queue and use your queue implementation to list the entries in a directory tree. You’ll also implement the merge sorting algorithm using queues. This is the first time that we will provide very few public tests and you have to develop the tests yourself to ensure your programs work correctly.




Learning Goals




Implement a generic unbounded queue.




Show understanding of algorithms that use a queue and a Java API class to walk a directory tree. Implement a sorting algorithm based upon queues and recursion.




Practice writing tests yourself to ensure the programs work correctly.




General Information [Common]




Reminder: Copying partial or whole solutions, obtained from other students or elsewhere, is academic dishonesty. Do not share your code with your classmates, and do not use your classmates’ code. If you are confused about what constitutes academic dishonesty you should re-read the course policies. We assume you have read the course policies in detail and by submitting this project you have provided your virtual signature in agreement with these policies.




For some projects, it may be useful for you to write additional java files. Any java file you write MUST be placed in the provided src directory of your Eclipse project.




When submitting your project, be sure to remove all compilation errors. Any compilation errors will cause the autograder to fail to run, and consequently you will receive a zero for your submission. No Exceptions!




In the test directory, we provide several JUnit tests that we refer to as the public tests. We recommend you run the tests often and use them as starting points to test your project. In addition, some of the java files come with their own main functions. You can run them as Java applications to interact with the project.




Be aware that the autograder will use a more comprehensive set of tests (referred to as private tests) to grade your project. These tests are hidden from you. We recommend that you think about possible test cases and add new @Test cases to your public test files as part of your programming discipline. In particular, you should consider:




Do your methods handle edge cases such as integer arguments that may be positive, negative, or zero. Many methods only accept arguments that are in a particular range.




Does your code handle cases such as when an array or list is empty, or has reached full capacity?




More complex tests will be project-specific. To build good test cases, think about ways to exercise methods. Work out the correct result for a call of a method with a given set of parameters by hand, then add it as a test case.




Import Project into Eclipse [Common]




Begin by downloading the starter project and importing it into your workspace. It is very important that you do not rename this project as its name is used during the autograding process. If the project is renamed, your assignment will not be graded, and you will receive a zero.




The imported project may have some compilation errors, but these should not prevent you from getting started. Specif-ically, we may provide JUnit tests for classes that do not yet exist in your code. You can still run the other JUnit tests. After completing your code, the compilation errors should be gone.




The project should normally contain the following root items:




src This is the source folder where all code you are submitting must go. You can change anything you want in this folder (unless otherwise specified), you can add new files, etc.




support This folder contains support code that we encourage you to use (and must be used to pass certain tests). You must not change or add anything in this folder. To help ensure that, we suggest that you set the support folder to be read-only. You can do this by right-clicking on it in the package explorer, choosing Properties from the menu, choosing Resource from the list on the left of the pop-up Properties window, unchecking the Permissions check-box for Owner-Write, and clicking the OK button. A dialog box will show with the title “Confirm recursive changes”, and you should click on the “Yes” button.




test The test folder where all of the public unit tests are available. You can feel free to add your own tests here.




JUnit 4 A library that is used to run the test programs.




JRE System Library This is what allows Java to run; it is the location of the Java System Libraries.




If you are missing any of the above or if errors are present in the project (other than as specifically described below), seek help immediately so you can get started on the project right away.




Problem 1




In this problem, you will implement a generic Queue data structure in Queue.java. Before you start, review the Queue lectures to remind yourself of the important concepts there and implementation details. You are allowed to use code you’ve written for previous assignments.




Requirements. For all three problems in this project, you may NOT use any Java class that implements the Collec-tion interface (e.g. ArrayList, Vector etc.). The list of these classes is included in the API documentation available at: http://docs.oracle.com/javase/8/docs/api/java/util/Collection.html. Notable, do not submit code where you import or use any class from java.util package. Doing so will result in a gdrade of 0.




What to do. Complete the Queue (defined in Queue.java) by correctly implementing the six methods marked by //TODO as well as two constructors, described below. You may implement the queue using either an array or a linked list, so long as it obeys the contract specified in UnboundedQueueInterface. If you use a linked list, a generic Node<T structure is already defined at the bottom of Queue.java. Note that normally each Java file contains only one public class. However, you can define multiple non-public classes (or nested classes) in the same Java file, keeping in mind that such classes are not visible (public) to outside classes. If you use array, you must make it expandable so that its size is unbounded. Please carefully read the comments in UnboundedQueueInterface.java to understand what each method does, what type of Exception each method is expected to throw, and importantly, several operations must be O(1).




The reversed() method should return a new copy of the Queue with the elements in reverse order, but must not modify the current Queue. Depending on how you store the queue elements, there are several implementation choices. If you use an array to store the queue elements, this should be quite simple. If you use a linked list to store the elements, you can use recursion in a similar fashion as the ‘printing a list backward’ example we covered in lectures.




In addition to the usual no-argument constructor, your implementation of Queue must also include a copy constructor. A copy constructor takes a single argument, with a type of the class itself, and returns a copy of the object. In this case, we want you to create what is called a shallow copy of the Queue. A shallow copy will contain a copy of the data structure (the array or the nodes of the linked list) used to hold the elements in the queue. The array itself (or the nodes in linked list) must allocated as a new array (or new nodes), but the values stored in the array elements (or the info values in the linked list nodes) will be identical. Put another way, the copy constructor should copy the references to the elements but not the elements themselves — the elements will be aliased between the original and the copy, but the data structure (the array or the nodes in the linked list) must be new.






Why are there so few tests? When you take upper-level CS classes (get a job in the future), it’s unlikely that comprehensive and ready-made test suites will be given to you to start with. Instead, you’ll need to develop your own tests, including reasoning about what are the necessary test cases, what are the edge cases that must be covered etc. Since you’ve already implemented several ADTs similar to a queue, we’re letting you write most of your own test suite for your Queue – we’ve provided test for the copy constructor, but they depend upon correct implementation of other methods that we haven’t provided tests for. It’s your responsibility to write your own tests for the other methods. If you are experienced with programming, you can eye-ball possible errors and bugs in your programs. But in general you must write some test cases to ensure your programs work correctly under all specified conditions.




Problem 2




Next, in src/filesystem/LevelOrderIterator.java, you will use your Queue to implement an Iterator over Files that will traverse (or walk) a filesystem tree in level order.




The filesystem in thirty seconds. Your computer stores files and directories on disk. The filesystem is a data structure that organizes these two types of nodes. Each node in the filesystem is either a file or a directory; and directories contain zero or more other nodes. If you drew out the content of a particular node, it would fan out in a tree-like structure. On OS X, this is explicit in the Finder:










Given a particular element in the filesystem, we can talk about examining the tree that is rooted at (starts at) that node. In the screenshot above, we’re examining the tree rooted at the src directory. It contains three elements, algorithms, hanoi, and structures. They happen to be all directories, but in practice they could be a mix of directories and files. algorithms and hanoi each contain yet more items, while structures is empty.




What to do. For full credit, correctly implement next() and hasNext() in LevelOrderIterator.java. Your code should systematically iterate through the nodes in a filesystem tree, rooted at a given node. First, it should visit the root node. Then, it should visit each of that node’s children (that is, each node directly connected to the root node). Then it should visit each of those node’s children, and so on. This approach will visit the root node, then all of the nodes one level below it, then all of the nodes one level below those nodes. This is called a level-order traversal. In essence, your code will perform a so called breadth-first search (BFS) of a given tree within the filesystem.




Java represents filesystem nodes using class java.io.File. You’ll want to skim through the API documentation for File. Pay attention to the constructor and the exists(), isDirectory(), and listFiles() methods.




To ensure you traverse the tree in level order, your code will need to visit the nodes in first-in-first-out order, adding children of the current node to a queue of nodes waiting to be visited in order. (Use the Queue you created in Problem 1; DO NOT use java.util.Queue.) When you obtain the children of a node, sort them in lexicographic before enqueueing them. The sorting can be done using Java’s Arrays.sort method. The File class already defines a compareTo method, which Arrays.sort relies on.




A correct level-order traversal of the example tree above, rooted at src, is in the following order:




src




src/algorithms src/hanoi





src/structures




src/algorithms/RecursiveMath.java src/hanoi/ArrayBasedHanoiBoard.java src/hanoi/RecursiveHanoiSolver.java src/hanoi/StackBasedHanoiPeg.java

On OS X, the path separator is a forward slash (/); on Windows it is a backslash (n). Our tests will account for the difference automatically. Please do not attempt to write code that translates path separators based upon the host platform. Use the listFiles() method of File to obtain the contents of directories, and Java will correctly create the File objects representing the contents.




Do not attempt to define methods in LevelOrderIterator recursively. Doing so will result in a depth-first rather than breadth-first traversal of the filesystem (as would using a Stack rather than a Queue).



Problem 3




For this problem, you will complete the code in src/sorting/MergeSorter.java, where you will use your Queue to implement the merge sort algorithm.




Type parameter T. MergeSorter has an unusual type parameter: MergeSorter<T extends Comparable <T. You can treat this as the usual generic type <T; the extra bit (extends Comparable<T) is indicating to the compiler that the generic type extends Comparable<T. This means you can depend upon type T having a compareTo() method. If you want to find out more, check the Comparable API documentation for details.




Merge sort. The merge sort is a popular algorithm for sorting data elements. In this problem, we’ll consider its operation on queues. We’ll consider a queue sorted when the elements are in ascending order, that is, when the front of the queue contains the smallest element, the rear of the queue contains the largest, and every element in between also falls in order.




At a high level, merge sort works by merging two smaller, already sorted queues into a combined sorted queue, hence the name ’merge’. The algorithm works as follows. Suppose you have a merge method that takes two already sorted input queues and newly created output queue (which is initially empty). While there are still elements in either input queues, dequeue one element from the queue whose front element is smaller, and enqueue it into the output queue. Repeat it until there are no more elements in the input queues. When writing a loop to implement this, be sure to check if either input queue is empty to avoid dequeuing from an input queue that’s already empty. The result of the merge method is an output queue that contains all elements from the input queues and keep them in sorted order.




Of course, you don’t generally have the luxury of starting with a pair of sorted queues. Instead, in the beginning you are given a single unsorted queue. To sort it using merge sort, you can use a divide-and-conquer approach. First, divide the single large queue into a pair of smaller queues, each containing about half the elements of the large queue. Specifically, to perform the divide, you can create two output queues (initially empty), then dequeuing the first half of elements from the large queue and adding them to the first output queue, and the second half to the second output queue. Now, call mergeSort recursively on the two output queues, which will get them sorted eventually. Finally comes the conquer step, that is, call the merge method as described above to merge the sorted smaller queues into a sorted large queue. After this, the original unsorted queue (which is passed to mergeSort) will be properly sorted, and this accomplishes what mergeSort is supposed to do. Think about what should be the base case for the mergeSort method (for example, when can you just return right away without doing any work?)




What to do. MergeSorter contains several methods that you must correctly implement. In particular, mergeSort method is a recursive method, so it needs to call itself at some point. It also needs to call divide and merge as described above to solve the problem using a divide-and-conquer approach. divide and merge methods can use loops (or you can implement them recursively as well, though it’s less intuitive than just using loops). DO NOT use Arrays.sort() as that will count as cheating and you will receive a grade of zero for violating the rule.






divide() takes in an input queue and two output queues. As described above, its jobs is to add the first half of the elements from the input queue to the first output queue, and the second half to the second queue. This is an example where the output consists of two objects so they are passed in through arguments, and the return type of this method is void.




merge() takes two input queues, creates a new queue by merging the elements in the input queues, keeping them in order, and returning the newly created queue. This is an example where the output consists of just one object so it is what’s returned by the method.




When comparing two generic type elements e1 and e2, you can’t directly use e1 <= e2, since the elements are objects, not primitive types. Instead, use e1.compareTo(e2). If its result is less than or equal to zero, e1 is less than or equal to e2.




Two hints: First, be sure you understand the base and recursive cases for the mergeSort method. Trial-and-error coding is unlikely to help you solve this problem. Second, you need not declare any class variables (also called instance variables); there is no need to share state between these methods except through their argument lists and return values. Using class variables may lead to hard-to-track-down errors.




Export and Submit [Common]



When you have completed this project, you should export an archive file containing the entire Java project. To do this, click on the queues-student project in the package explorer. Then choose “File ! Export” from the menu. In the window that appears, under “General” choose “Archive File”. Then choose “Next” and enter a destination for the output file. Be sure that the project is named queues-student (otherwise you may be exporting the wrong project!). Save the exported file with the zip extension.







Once you have the zip file ready, you can submit it to the online autograder (Gradescope). Please see the course website and/or documentation explaining how to use the online autograder. If you have any questions please be prompt in asking the course staff before it is too late to submit your solution. If you encounter any errors that look like the autograder failed and not your project, please let the instructors know.






























































































Page 7 of 7