CS21 Fall 2005
Homework 11: CD Database Take 3, using Binary Search Tree
Due: Friday, April 28 before 5:30 pm

You may work with a partner, and you should submit your solution as a single tar file (see the hw 8 assignment for info on using tar).

For this assignment, you will start with your CDInfo.java and CDDBMgr.java files from homework 10, and with my additional hw11 starting point files. You will implement the CD Database assignment using a Binary Search Tree to store the database of CDInfo rather than using a linked list. In addition, you will add two new menu options to your program. 

% cd cs21
% mkdir hw11
% cd hw11
% cp ../hw10/CDInfo.java .
% cp ../hw10/CDDBMgr.java .
% cp ~newhall/public/cs21/hw11/* .
For this assignment, you should start with your CDInfo.java and CDDBMgr.java solutions to homework 10. Modify the CDDBMgr class to read in CD information for the file into a BST of CDInfo objects (change the compareTo method to compare only artist name fields). Also, you will add two new menu options to your program (one is trivial the other requires some BST method writing on your part). See my sample output below as a guide for how the features should be implemented.

Here is more detailed information of what you need to do:

  1. Replace the LinkedList data structure for storing CDInfo objects with a BST data structure (code in CDDMgr). Also, comment out code inside methods that implement menu options on a LinkedList so that the code will compile; you will implement and test these one at a time for the BST database.

  2. Change the CDInfo compareTo method to compare CDInfo objects by the artist's name field only (this will be the key field for ordering CDInfo objects in the BST and for finding a single matching element in the tree)

  3. Implement the insert method of BST class, then try reading in the database file into the BST and print out the results in sorted order (basically you have done menu options 4 and 5 with a bit more work...the BST method printInOrder is already implemented for you). Test your code at this point.

    Since there may be duplicate keys in the BST (multiple entries for the same artist name), you should order BSTNodes such that Nodes in a node's left subtree are strictly less than it, and nodes in its right subtree are greater than OR EQUAL to it (duplicates go right).

  4. Add 2 new options to the menu, and implement and test the first one before you implement and test any of the options from your hw10 solution (in my sample output below these are menu options 6 and 7):

    1. Does the artist exist in the DB.

      If the search succeeds, then print out the single matching CDInfo object that is returned, otherwise print out a message indicating that there is no matching artist in the DB To do this, first implement the find method of the BST class so that returns a ref to the first matching element it finds...you should call the compareTo method on the data fields since you changed it to compare only by artist name).

    2. Print the BST: this option will just call the BST printTree method that is already implemented for you It is primarily for you to see the BST structure that your code is creating. The BST is printed sideways and in mirror image, and each node's depth is printed next to it (d = i). For example: 
      		   root's left child's right child, d = 2
		root's left child node,  d = 1
		   root's left child's left child, d = 2
	  root node, d = 0
		   root's right child's left child, d = 2
		root's right child node  d = 1
		   root's right child's right child, d = 2
  5. Implement menu options 1, 2, and 3, that find all CDInfo objects that match a user given field (title, artist, or date). To do this you will need to modify CDDBMgr methods to invoke BST methods to perform this functionality. And, make sure that you compare artist name and CD titles using the CDInfo method that compares two strings ignoring whitespace and case.

    To the BST class you will need to add methods that do a full traversal of the BST, and that print out matching items as you go (this is slightly different than how you did it in the LinkedList version where the LinkedList class just returned a list of matches and the CDDMgr called the printList method out the answer list to print out the results).

    For example, to the BST class you could add a method named printAllMatchingArtists that takes a String (or a CDInfo ref) with an artist name, and performs a full traversal of the BST printing out the value of any CDInfo nodes with matching artist fields as you go (remember that you will need to re-cast the BSTNode data field to be a ref to a CDInfo object inorder to invoke CDInfo-specific methods on the data field).

  6. Implement code to write out the BST contents to a file after the user selects the "Quit" menu option (think about the order in which you write out BST elements so that if this file is read back into a BST, the BST will be a BST and not a linked list). You want to write out the contents of the BST so that when the file is read in again, it creates a BST that is no worse than the one you finished with in the previous run (i.e. don't go from a ballanced BST at the end of one run of your program to a linked-list at the begining of the next run of your program). If the BST at the end of your program is bad (it is close to a linked-list in structure), it is okay for the next run of your program to start with an equally as bad BST.

    After the call to PerformActions in main returns make a call to a method SaveToFile like this: 

            SaveToFile(cds, args[0] + "_new");
    This is what the shell of this CDDMgr method looks like (note that it makes a call to the writeToFile method of the BST class that you need to implement): 
    

    public static void SaveToFile(BST cds, String outfile) throws IOException {

        // create a new FileWriter object to write data to the
        // file with the name of the outfile String:
        FileWriter f = new FileWriter(new File(outfile));

        // call a BST method that traverses the BST in some order
	// and writes out the data field contents to the passed file
        cds.writeToFile(f);

        // always close the file after you are done writing to it
        f.close();
}
    The BST method that does this traversal and writing needs to know that the data fields are refs to CDInfo objects (i.e. you need to recast the value in the data field of the BSTNode to be a CDInfo object ref before you can invoke its getAlbum or GetArtist methods: 
         CDInfo data = (CDInfo)curr.getData();
     f.write(data.getArtist() + "\n");
     f.write(data.getAlbum() + "\n");
     f.write(String.valueOf(data.getDate()) + "\n");

Sample Output

Here is some sample output from my program (one run with hw11.txt the other with hw11.txt_out): 
% java CDDBMgr hw11.txt

There are 21 CDS. 


****  MENU OPTIONS ****
	1) to see all works by a given artist
	2) to see all albums with a given title
	3) to see all albums released in a give year
	4) to see the complete list
	5) to add a new CD to the collection
	6) to see if an particular artist is in the database
	7) to print out the BST of CDInfo (only do this for small BSTs)
	8) to quit
***********************
Enter your choice: 4

Al Green,    greatest    hits    , 2005
Bob Marley, Survival, 1979
Charles Mingus, Mingus Ah Um, 1959
De La Soul, 3 Feet High and Rising, 1989
De La Soul, De La Soul Is Dead, 1991
James Brown, Get on the Good Foot, 1972
Killdozer , For Ladies Only, 1989
MC5, Kick Out the Jams, 1969
Patti Smith, Horses, 1975
Public Enemy, It Takes a Nation of Millions to Hold Us Back, 1988
Ramones, Greatest Hits, 1990
Sleater-Kinney, Dig Me Out, 1997
Sleater-Kinney, One Beat, 2002
Sly & the Family Stone, Fresh, 1973
Sly & the Family Stone, Greatest hits, 1970
Spot 1019, Spot 1019, 1986
The Fall , The Infotainment Scan, 1993
X, Under the Big Black Sun, 1982
X, More Fun in the New World, 1983
X , Los Angeles, 1980
sly  &  the   family  stone, There's a Riot Goin' On, 1971
-----------------------------------------------
There are 21 CDs

****  MENU OPTIONS ****
	1) to see all works by a given artist
	2) to see all albums with a given title
	3) to see all albums released in a give year
	4) to see the complete list
	5) to add a new CD to the collection
	6) to see if an particular artist is in the database
	7) to print out the BST of CDInfo (only do this for small BSTs)
	8) to quit
***********************
Enter your choice: 7

            Al Green,    greatest    hits    , 2005   d = 3
        Bob Marley, Survival, 1979   d = 2
                Charles Mingus, Mingus Ah Um, 1959   d = 4
            De La Soul, 3 Feet High and Rising, 1989   d = 3
                De La Soul, De La Soul Is Dead, 1991   d = 4
    James Brown, Get on the Good Foot, 1972   d = 1
            Killdozer , For Ladies Only, 1989   d = 3
                MC5, Kick Out the Jams, 1969   d = 4
        Patti Smith, Horses, 1975   d = 2
Public Enemy, It Takes a Nation of Millions to Hold Us Back, 1988   d = 0
            Ramones, Greatest Hits, 1990   d = 3
        Sleater-Kinney, Dig Me Out, 1997   d = 2
            Sleater-Kinney, One Beat, 2002   d = 3
    Sly & the Family Stone, Fresh, 1973   d = 1
                Sly & the Family Stone, Greatest hits, 1970   d = 4
            Spot 1019, Spot 1019, 1986   d = 3
                The Fall , The Infotainment Scan, 1993   d = 4
        X, Under the Big Black Sun, 1982   d = 2
            X, More Fun in the New World, 1983   d = 3
                X , Los Angeles, 1980   d = 4
                    sly  &  the   family  stone, There's a Riot Goin' On, 1971   d = 5
-------------------------------------

****  MENU OPTIONS ****
	1) to see all works by a given artist
	2) to see all albums with a given title
	3) to see all albums released in a give year
	4) to see the complete list
	5) to add a new CD to the collection
	6) to see if an particular artist is in the database
	7) to print out the BST of CDInfo (only do this for small BSTs)
	8) to quit
***********************
Enter your choice: 5

Enter the artist's name: Public Enemy
Enter the album title: Fear of a Black Planet
Enter a release year: 1990

****  MENU OPTIONS ****
	1) to see all works by a given artist
	2) to see all albums with a given title
	3) to see all albums released in a give year
	4) to see the complete list
	5) to add a new CD to the collection
	6) to see if an particular artist is in the database
	7) to print out the BST of CDInfo (only do this for small BSTs)
	8) to quit
***********************
Enter your choice: 7

            Al Green,    greatest    hits    , 2005   d = 3
        Bob Marley, Survival, 1979   d = 2
                Charles Mingus, Mingus Ah Um, 1959   d = 4
            De La Soul, 3 Feet High and Rising, 1989   d = 3
                De La Soul, De La Soul Is Dead, 1991   d = 4
    James Brown, Get on the Good Foot, 1972   d = 1
            Killdozer , For Ladies Only, 1989   d = 3
                MC5, Kick Out the Jams, 1969   d = 4
        Patti Smith, Horses, 1975   d = 2
Public Enemy, It Takes a Nation of Millions to Hold Us Back, 1988   d = 0
                Public Enemy, Fear of a Black Planet, 1990   d = 4
            Ramones, Greatest Hits, 1990   d = 3
        Sleater-Kinney, Dig Me Out, 1997   d = 2
            Sleater-Kinney, One Beat, 2002   d = 3
    Sly & the Family Stone, Fresh, 1973   d = 1
                Sly & the Family Stone, Greatest hits, 1970   d = 4
            Spot 1019, Spot 1019, 1986   d = 3
                The Fall , The Infotainment Scan, 1993   d = 4
        X, Under the Big Black Sun, 1982   d = 2
            X, More Fun in the New World, 1983   d = 3
                X , Los Angeles, 1980   d = 4
                    sly  &  the   family  stone, There's a Riot Goin' On, 1971   d = 5
-------------------------------------

****  MENU OPTIONS ****
	1) to see all works by a given artist
	2) to see all albums with a given title
	3) to see all albums released in a give year
	4) to see the complete list
	5) to add a new CD to the collection
	6) to see if an particular artist is in the database
	7) to print out the BST of CDInfo (only do this for small BSTs)
	8) to quit
***********************
Enter your choice: 4

Al Green,    greatest    hits    , 2005
Bob Marley, Survival, 1979
Charles Mingus, Mingus Ah Um, 1959
De La Soul, 3 Feet High and Rising, 1989
De La Soul, De La Soul Is Dead, 1991
James Brown, Get on the Good Foot, 1972
Killdozer , For Ladies Only, 1989
MC5, Kick Out the Jams, 1969
Patti Smith, Horses, 1975
Public Enemy, It Takes a Nation of Millions to Hold Us Back, 1988
Public Enemy, Fear of a Black Planet, 1990
Ramones, Greatest Hits, 1990
Sleater-Kinney, Dig Me Out, 1997
Sleater-Kinney, One Beat, 2002
Sly & the Family Stone, Fresh, 1973
Sly & the Family Stone, Greatest hits, 1970
Spot 1019, Spot 1019, 1986
The Fall , The Infotainment Scan, 1993
X, Under the Big Black Sun, 1982
X, More Fun in the New World, 1983
X , Los Angeles, 1980
sly  &  the   family  stone, There's a Riot Goin' On, 1971
-----------------------------------------------
There are 22 CDs

****  MENU OPTIONS ****
	1) to see all works by a given artist
	2) to see all albums with a given title
	3) to see all albums released in a give year
	4) to see the complete list
	5) to add a new CD to the collection
	6) to see if an particular artist is in the database
	7) to print out the BST of CDInfo (only do this for small BSTs)
	8) to quit
***********************
Enter your choice: 6

Enter an the artist's name: X
CDs by X do appear in the database, here is one of them:
	X, Under the Big Black Sun, 1982
--------------------------------------------

****  MENU OPTIONS ****
	1) to see all works by a given artist
	2) to see all albums with a given title
	3) to see all albums released in a give year
	4) to see the complete list
	5) to add a new CD to the collection
	6) to see if an particular artist is in the database
	7) to print out the BST of CDInfo (only do this for small BSTs)
	8) to quit
***********************
Enter your choice: 1

Enter the name of the artist: X
CDs by X:
--------------------------------------------
X, Under the Big Black Sun, 1982
X, More Fun in the New World, 1983
X , Los Angeles, 1980
--------------------------------------------

****  MENU OPTIONS ****
	1) to see all works by a given artist
	2) to see all albums with a given title
	3) to see all albums released in a give year
	4) to see the complete list
	5) to add a new CD to the collection
	6) to see if an particular artist is in the database
	7) to print out the BST of CDInfo (only do this for small BSTs)
	8) to quit
***********************
Enter your choice: 2

Enter a CD title: greatest hits
CDs named greatest hits:
--------------------------------------------
Al Green,    greatest    hits    , 2005
Ramones, Greatest Hits, 1990
Sly & the Family Stone, Greatest hits, 1970
--------------------------------------------

****  MENU OPTIONS ****
	1) to see all works by a given artist
	2) to see all albums with a given title
	3) to see all albums released in a give year
	4) to see the complete list
	5) to add a new CD to the collection
	6) to see if an particular artist is in the database
	7) to print out the BST of CDInfo (only do this for small BSTs)
	8) to quit
***********************
Enter your choice: 1

Enter the name of the artist: de la soul
CDs by de la soul:
--------------------------------------------
De La Soul, 3 Feet High and Rising, 1989
De La Soul, De La Soul Is Dead, 1991
--------------------------------------------

****  MENU OPTIONS ****
	1) to see all works by a given artist
	2) to see all albums with a given title
	3) to see all albums released in a give year
	4) to see the complete list
	5) to add a new CD to the collection
	6) to see if an particular artist is in the database
	7) to print out the BST of CDInfo (only do this for small BSTs)
	8) to quit
***********************
Enter your choice: 8

bye, bye

% java CDDBMgr hw11.txt_new 

There are 22 CDS. 


****  MENU OPTIONS ****
	1) to see all works by a given artist
	2) to see all albums with a given title
	3) to see all albums released in a give year
	4) to see the complete list
	5) to add a new CD to the collection
	6) to see if an particular artist is in the database
	7) to print out the BST of CDInfo (only do this for small BSTs)
	8) to quit
***********************
Enter your choice: 4

Al Green,    greatest    hits    , 2005
Bob Marley, Survival, 1979
Charles Mingus, Mingus Ah Um, 1959
De La Soul, 3 Feet High and Rising, 1989
De La Soul, De La Soul Is Dead, 1991
James Brown, Get on the Good Foot, 1972
Killdozer , For Ladies Only, 1989
MC5, Kick Out the Jams, 1969
Patti Smith, Horses, 1975
Public Enemy, It Takes a Nation of Millions to Hold Us Back, 1988
Public Enemy, Fear of a Black Planet, 1990
Ramones, Greatest Hits, 1990
Sleater-Kinney, Dig Me Out, 1997
Sleater-Kinney, One Beat, 2002
Sly & the Family Stone, Fresh, 1973
Sly & the Family Stone, Greatest hits, 1970
Spot 1019, Spot 1019, 1986
The Fall , The Infotainment Scan, 1993
X, Under the Big Black Sun, 1982
X, More Fun in the New World, 1983
X , Los Angeles, 1980
sly  &  the   family  stone, There's a Riot Goin' On, 1971
-----------------------------------------------
There are 22 CDs

****  MENU OPTIONS ****
	1) to see all works by a given artist
	2) to see all albums with a given title
	3) to see all albums released in a give year
	4) to see the complete list
	5) to add a new CD to the collection
	6) to see if an particular artist is in the database
	7) to print out the BST of CDInfo (only do this for small BSTs)
	8) to quit
***********************
Enter your choice: 1

Enter the name of the artist: sly & the family STONE:
CDs by sly & the family STONE:
--------------------------------------------
Sly & the Family Stone, Fresh, 1973
Sly & the Family Stone, Greatest hits, 1970
sly  &  the   family  stone, There's a Riot Goin' On, 1971
--------------------------------------------

****  MENU OPTIONS ****
	1) to see all works by a given artist
	2) to see all albums with a given title
	3) to see all albums released in a give year
	4) to see the complete list
	5) to add a new CD to the collection
	6) to see if an particular artist is in the database
	7) to print out the BST of CDInfo (only do this for small BSTs)
	8) to quit
***********************
Enter your choice: 8

bye, bye