CS61B Project 1 A Music Database Due: Sunday, September 20 at 5pm. (Note: this is two days later than on the original course syllabus.) This is a team project. You may work in teams of 2 or 3 students total. No teams of 1 or teams of 4 or more are allowed. Getting started: You will find the code for this assignment in $master/hw/pj1/. Start by copying it into your own pj1 directory. The files in the pj1 directory contain a partial implementation of a database program for keeping track of a collection of musical CDs (or records, or cassette tapes, or whatever). The program already has some basic functionaliyt, but some of the commands are unimplemented and others are not as fast or as usable as they could be. Your job is to upgrade the implementation in several ways. The program is organized into the following classes: MusicSearch -- does all of the I/O for the database engine, and uses the MusicDB and the RecordsParser classes. MusicDB -- stores the database and provides methods to add to and search in the database. RecordsParser -- used for reading record/CD descriptions out of an input file. Album -- Not an abstract data type; all the fields are public, and there are no methods or enforced invariants. These objects contain all of the fields necessary to represent an album. Song -- Not an abstract data type; all the fields are public, and there are no methods or enforced invariants. These objects contain all of the fields necessary to represent a song. List and ListEnum -- these two classes work together to provides the List functionality. They make use of a ListNode type. TestHelper -- from the Arnow and Weiss book, this is used to provide a function that helps with testing. records.in and onerec.in are examples of input files. Feel free to make up more input files with your own CD collection or other things. Part I: Lists to Vectors ------------------------ The MusicDB.java file contains is the primary class for implementing the database. It uses several other classes, including a List class for storing all of the albums in the database. In this step, you are to do three things: 1) Replace the List representation by a vector representation. 2) Replace the title search (for looking up an album by the album title) with one that has the same specification, but works in O(log n) time, where n is the numer of albums in the database. To do this using the Vector representation, you will need to arrange to keep the Vector in sorted order by album title and and use binary search to lookup the title. 3) Modify the addAlbum operation so that it does not add duplicate albums to the database. /** Adds an album to the database. If an album by the same title * already exists, then the new album should replace the one * currently in the datbase. * @param album is an album to be added to the database, which is * assumed non-null. */ Be sure to update the comment when you update the method. All of the other methods should work as in the original specification. Part II: Adding new search methods ---------------------------------- Two of the methods in MusicDB.java are unimplemented. /** Finds the album with the given artist. * @param artist is the name of an artist for which to search. * @return the List of Albums by the given artist or an * empty List if there is no album by the given artist * in the database. */ public List albumsByArtist(String artist) { ... } /** Finds all albums that contain the given song title. * @param title is the song title for which to search. * @return a list of albums containing title or an * empry List if there is no album containing the given song. */ public List albumsWithSong(String title) { ... } Provide implementations for these using the Vector implementation from Part I. Your implementation of artist search must work in O(n) time, where n is the number of albums in the database. Your implementation of song title search must work in O(n*m) time, where n is the number of albums and m is the maximum number of songs in any album in the database. (Note: there are ways of making these operations more efficient, but no additional credit will be earned on this assignment for making them more efficient. We will revisit this problem later in the semester.) Part III: Improving Usability ----------------------------- Modify the database program so that it will accept partial album or song title and is case insensitive. For example, if there is an album with the title: the very best of the lovin' spoonful in the database, then the user can find it by search for: the very best of The VERY BEST of And many other substrings that are a prefix and/or different capitalization of the full title. (A prefix means that the partial title must start at the beginning -- it cannot be a substring from the middle of the title.) Note that search for some strings, such as "the best of" may yield many. Part IV: Testing ---------------- The List class contains some test code in the main function. Add a main function to the MusicDB class to test the MusicDB implementation. Organize your tests cases into some logical groups so they are easy to understand. (Be sure to read the chapter in the book and the lecture notes on this topic if you haven't already done so.) FINAL COMMENTS -------------- First, some some comments on I/O and testing: We have not provided test code for the I/O classes, nor is this interface very robust in the face of errors in your database file. The reason is that it is difficult to write test cases that do not crash the program until we have a more sophisticated understanding of exceptions in Java. For now, all of the exceptions are in the MusicSearch class, and they are not handled in any specific way, except using the "throws IOException" clause in the method signature, as you have seen in the book. Second, what you should modify: Most of your changes should go in the MusicDB file (or in other files that you add to the project). You should not need to modify the basic Albums, Song, or List classes, not should you modify the I/O code in MusicSearch. None of the signatures of any method should change: if you do so, your project risks receiving zero points, since it will not work with our test code. You should, however, update any of the leading comments for methods when we asked you to modify their behavior. TURNING IN YOUR ASSIGNMENT -------------------------- Turn in your assignment using the submit program as in the homework assignments. Only 1 member of each team should submit the solution. The submit program will ask you for the logins of your partners. Your solution must contain all the files in the original pj1 directory. The submit program will complain if any of these are missing. In addition, you must supply a README.grader file that includes: * Names and logins of all team members partners. (The submit program keeps track of this, but include the names here in case there is any confusion regarding your submission.) * A description of what the major tasks were in your project solution and how the work was broken up between partners. All members of the team should be familiar with the entire solution, just as all members of a product team will ultimately be responsible for fixing problems with a product in industry. Grades are assigned to teams, not individuals, so all members of a project team will normally receive the same grade, even if the works is not balanced. * A description of the project itself, including any known problems with your solution or things you think the readers should know to help in assigning partial credit. * A descipription of how the test cases for the MusicDB class are broken down. Your submission may also include other files (in particular .java files) that are needed for your solution. Before submitting, be sure to clean up your directory. Do not leave any extra .java files around that are not needed in your solution, as this will only cause more work for the graders and result in a lower your grade.