CS 61B – Summer 2005 – Project 2 (spec version 2.0)

“CD Database”

Due: July 22, 2005 5pm

Overview

This project will give you practice with Linked List data structures and sorting algorithms. You will be building a small database, and will make use of database indexes in order to speed up certain operations.

First, copy the project files into your directory:

> mkdir proj2

> cd proj2

> cp $master/proj/proj2/* .

Part 1 – Linked Song database (30 points)

For the first part of this project, you will build a basic database that will store Songs. A Song has three components: an Artist, a Title, and a Year.

  • Artist: A String representing the band or musician (Elvis, The Beatles, Beck, Mozart, etc.)
  • Title: A String representing the title of the song
  • Year: The year the song was written

You must define a class that represents songs. Your class will implement the Song interface in $master/proj2/cs61b/Song.java.

You will define a class that represents your song database, and it will implement the following interface:

package cs61b;

public interface SongDB {

public void addSong(Song a);

public void remSong(Song a);

public Song[] getByArtist(String artist);

public Song[] getByTitle(String title);

public Song[] getByYear(int year);

public Song[] getByArtistRange(String start, String finish);

public Song[] getByTitleRange(String start, String finish);

public Song[] getByYearRange(int start, int finish);

public void printByArtist(PrintWriter out);

public void printByTitle(PrintWriter out);

public void printByYear(PrintWriter out);

}

There are comments in the SongDB interface that explain what each method should do in detail.

For Part 1, you must store the Songs for your database in the heap. Your database will keep three sorted linked lists—one for each searchable category (Artist, Title, year). You should keep your linked lists sorted. Sorted linked lists will increase the performance of getByArtistRange(), getByTitleRange(), and getByYearRange() and make them easier to write.

Hint: getByArtist(), getByTitle(), and getByYear() are trivial, since you can have them call getByArtistRange(), getByTitleRange(), and getByYearRange().

Part 2 – Music playlist (15 points)

iPods and other mp3 players have playlists. A playlist is a list of songs that will be played in a particular order, one right after the other. Users can add songs to the playlist, remove songs from the playlist, and get songs off of it. If songs A, B, and C are added to the playlist (in that order), then the first song that getNextSong() should return is A, followed by B, followed by C). For part 2 of this project, you will have your database class implement the PlayList interface. It is given here:

package cs61b;

public interface Playlist {

public void addSongToPlaylist(Song s);

public void remSongFromPlaylist(Song s);

public Song getNextSong();

public int length();

public boolean isEmpty();

public void shufflePlaylist();

}

Please see $master/proj/proj2/cs61b/Playlist.java for detailed method descriptions. There is a file in $master/proj/proj2 called Shuffle.java for information on how to implement shuffling of array values.

You should create an array of references to Song objects in order to support the Playlist feature of our database. You are free to use the ArrayList class if you want, or you can simply use Song[]. Your database only needs to support one playlist.

Part 3 – Sortable playlist (40 points) (start after the sorting lectures)

We will now extend the notion of the Playlist by having a sortable playlist. This allows the user to sort their playlist by artist, by title, or by year. To make use of the appropriate functions, your database should implement the SortablePlaylist interface:

package cs61b;

public interface SortablePlaylist extends Playlist {

public void sortByArtist();

public void sortByTitle();

public void sortByYear();

}

For part 3, you must implement your sorting methods using two different algorithms: quicksort and mergesort. You can define two different classes: QSortSongDb and MSortSongDb, each of which provide their own sortByArtist(), sortByTitle(), and sortByYear() methods. Recall from lecture that abstract classes can be used to avoid having to rewrite code over and over again. So you could define and abstract class that implements the Playlist and SongDB interfaces. That class could have two concrete subclasses—one for each sorting algorithm.

Part 4 – Testing strategy and test cases (15 points)

To test each of the parts of your database above, you should write testing code. You should at least have a test for each feature of the database (adding a song, removing a song, finding a song, etc). Think through how you might extend your database class to enable easier testing.

A popular method of testing a new feature is to first write a small program that makes use of that feature. Write this program first (it won’t compile yet, of course). Now go about implementing the appropriate feature. Now you can run your testing program against the new feature to test its correctness. You will find that by first writing code that makes use of your new feature, you can think more clearly about what should go into the feature.

For part 4, you must provide code that tests each of the methods in the interfaces we have provided to you. So when you create a class that implements the SongDB interface, you should have code that tests the addSong() method, the remSong() method, etc.

To receive full credit for part 4, you must test each of the methods in the interfaces we have provided you, and your tests must be diverse enough to catch a variety of errors. As explained at the end of this document, you will provide both testing code (in the form of Java source files) as well as a description of these tests in a file called writeup.txt.

Song Source

The source of songs to our database comes from files that are in the “CDDB” format. There is one album per file, and the file’s name is a special function of its contents called a hash function. There are 13 files in the $master/proj2/songs directory. Each file contains information about one Album, which contains multiple songs.

We have provided a class called FileSongSource for you that implements the SongSource interface shown here:

package cs61b;

import java.io.*;

public interface SongSource {

public boolean hasNext() throws FileNotFoundException, IOException;

public Song next() throws FileNotFoundException, IOException;

}

FileSongSource is a class that implements this interface. It has a single constructor of the following form:

public FileSongSource(String directory);

directory is a string that contains the name of a directory on the filesystem. This directory should contain the song files (and ONLY the song files). Here is an example:

SongSource ss = new FileSongSource(“$master/proj/proj2/songs”);

This will create a SongSource called ss that provides all the songs from the $master/proj/proj2/songs directory. The following code prints out all of the songs in that directory:

SongSource ss = new FileSongSource(“$master/proj/proj2/songs”);

while (ss.hasNext()) {

System.out.println( (Song) ss.next() );

}

About halfway through the project we will publish additional songs for you to test your program with.

FileSongSource has a main() method that will print out all the songs in a directory:

> cd proj2/

> javac –g cs61b/FileSongSource.java

> java cs61b.FileSongSource ~/proj2/songs/

will print out all the songs in the ~/proj2/songs/ directory.

Part 5 – README file (20 points)

This file should include the information listed below, answering all the questions in each category.

  • An explanation of how you split the work for this assignment between members of your partnership, and why you split it this way. Also indicate the number of points that should be awarded to each partner if you were to distribute 10 extra bonus points for your project between members of your partnership.
  • A description of the overall organization of your program—the names of your classes and which interfaces they implement. Diagrams will be useful here to show the correspondence between an abstract song database and your song database implementation. This description should contain enough detail for another CS 61B student to understand clearly how the corresponding code would work.
  • A description of any other files you're submitting.
  • An explanation of how you addressed efficiency concerns in your program:
  • What alternatives did you consider?
  • Why did you accept or reject them? (In particular, you should explain each choice of an array/ArrayList over a linked list and vice-versa.)
  • How much memory do your data structures consume when processing typical examples? (You can give big-Oh or big-theta estimates.)
  • How fast do your algorithms work on those examples? (Again, provide big-Oh estimates.)
  • In retrospect, what bad choices did you make and how would you have made them differently?
  • A description of your debugging output facility and how to enable it.
  • An explanation of the process by which you constructed a working program:
  • What did you code and test first, and what did you postpone?
  • Why did you build the program in this sequence?
  • What test cases did you use for each of your classes, and how did you choose them? (For this question, we will look at your Part 4)

Evaluate the evidence of the correctness of your code that your program construction process produced, and indicate what if anything you should have done differently to construct your program. Also describe and explain any bugs that remain; a bug you admit to will cost you fewer points than a bug you don't mention.

In general, comments in your code will describe information specific to the corresponding class, while the README file contains information that relates classes and describes and provides rationale for design and implementation decisions. However, your README file should be written to be read on its own without a copy of the program code at hand, so there may be some information duplicated in writeup and code.

We encourage you to build the README file as you design, code, and test rather than putting it off until the end.

Project Results

Part 1: You must write classes that correctly implement the Song and SongDB interfaces.

Part 2: Write classes (or modify your classes) so that you support the Playlist interface.

Part 3: Write a MSortSongDB and QSortSongDB class that support the SortablePlaylist interface. The first should sort using merge sort, the second should sort based on Quicksort. (Save this until after July 13, when we cover sorting).

Part 4: For this part, you need to include two different things. The first thing you need to include is your testing code. This will take the form of Java source files. You also need to include a file called writeup.txt that explains how to run your test cases, which cases you chose, and why. Basically, for each feature you wish to test, list the cases you think are important to test for (i.e., operations on an empty database, operations on a database with one song, etc).

Submitting your solution

Make sure that your program compiles and runs on the lab machines. Change into your project 2 directory:

> cd

> cd proj2

Make sure that the interfaces we provided are in this directory, as well as the abstract and concrete classes that you’ve written. Include the testing code that you’ve written, and the writeup.txt file. Submit the homework electronically via:

> submit pj2

After submitting, if you find a bug in your program, you can submit again. We will look at the last solution you submit (unless you tell us otherwise).

In the upcoming weeks, we will be taking up some of the project in the labs (such as testing, for example)

Good luck, and please make use of the class newsgroup for discussion on Java concepts, compiler issues, and other issues that come up during your project. Remember the no-code rule though. You can only show/get code from your project partner. Get in touch with us via or come to your TAs office hours if you run into trouble. We are here to help! Thanks.