// Implements a music rack for a music library as an // ordered collection of songs stored in an array. // All public methods must ensure that the ordering is maintained. // public class MusicRack { private Song[] songList; private int numSongs; // Create an empty music rack that holds at most one song. public MusicRack() { songList = new Song[1]; numSongs = 0; } // Insert song into the array of songs based on the // required criteria public void insert(Song newSong) { // NOTE: There can only be one insert method, because the objects // must always have the songs in the same ordering. // To pick the ordering type uncomment only ONE of the following methods. // That uncommented method is the one that insert will call. // In effect, when the main method in MusicLibrary class calls // insert, it calls the uncommented method below. The main method // in MusicLibrary cannot call these insert methods below // because they are defined with the keywork private (not public) insertInIncreasingChartPosition(newSong); // insertInArtistOrder(newSong); } // Steps for insert (some step may be unnecessary for some insert methods): // 1. Make the array big enough to insert the item, if needed. // 2. Find at what position to put it. // 3. Make room for the item at that position (shift right). // 4. Put the item in the array. // 5. Update the number of items. // PRECONDITION: Songs are in increasing order based on the songs's // chart position // Insert Example 3: Insert song in order based on the chart // position (increasing order - lowest to highest). If there are // songs with the same chart position, inserts newSong BEFORE them. // How would you put newSong AFTER songs with the same chart position? private void insertInIncreasingChartPosition(Song newSong) { // Search for the location to insert (insertIndex) boolean found = false; int insertIndex = 0; while (insertIndex < numSongs && !found) { // Note: !found is same as (found == false) if (newSong.getWeeksOnChart() <= songList[insertIndex].getWeeksOnChart()) { // newSong should come just before songList[insertIndex] // because it is "smaller or equal" found = true; } else { insertIndex++; // keep looking } } // When exit while loop, based on the while condition, it must be // the case that // insertIndex >= numSongs || found (by de Morgan's law) // insertIndex == numSongs || found (because exit loop as soon as // insertIndex == numSongs) // (insertIndex == numSongs && !found) || // (found && insertIndex < numSongs) (because body is if/else) // Before we insert the song we need to check if the array is // is full and double its size if needed. if (numSongs == songList.length) { // array is full doubleLength(); } // insertIndex is where we need to insert. // Shift everything from this index to the last song's position // towards the end of the array, starting with the last song for (int from = numSongs-1; from >= insertIndex; from--) { int to = from+1; songList[to] = songList[from]; // copy from songList[from] // to songList[from+1] } // insert new song songList[insertIndex] = newSong; numSongs++; } // PRECONDITION: Songs are in lexicographical order based on ARTIST name. // Insert Example 4: Insert song in lexicographical order based on ARTIST name // If there are duplicate artist, inserts BEFORE the duplicate. // // Lexicographical order is alphabetical order as long as all the names // have capital and lower case letters at the same positions in the names, // e.g., all upper case, or all initial capital only. // // How do we compare strings for lexicographical order? // Use compareTo(), see below. private void insertInArtistOrder(Song newSong) { // Search for the location to insert (index) boolean found = false; int insertIndex = 0; // Example: s1.compareTo(s2) (s1, s2 are strings) // compareTo returns a negative int, if s1 comes before s2 lexicographically // (i.e. s1 is "less than" s2) // compareTo returns 0 if s1 is "equal" s2 // compareTo returns a positive int. if s1 comes after s2 lexicographically // (i.e. s1 is "greater than" s2) while (insertIndex < numSongs && !found) { if (newSong.getArtist().compareTo( songList[insertIndex].getArtist()) <= 0) { // newSong artist should come before songList[insertIndex] found = true; } else { insertIndex++; // keep looking } } if (numSongs == songList.length) { // is the array full? doubleLength(); } // insertIndex is where we need to insert // Shift everything from this index to the last song's position // towards the end of the array, starting from the last song for (int from = numSongs-1; from >= insertIndex; from--) { songList[from+1] = songList[from]; } // insert new song songList[insertIndex] = newSong; numSongs++; } // Remove Example 2: Remove first occurrence of a song that has been on // the charts more than the given number of weeks, if there are any. public void remove(int weeks) { // Another way to find a song int indexToRemove = 0; while (indexToRemove < numSongs //Must be first of two conditions. why? && !(songList[indexToRemove].getWeeksOnChart() > weeks)) { indexToRemove++; } // exit while when (indexToRemove == numSongs && not found song) || // (found it at indexToRemove && indexToRemove < numSongs) if (indexToRemove < numSongs) { // Found a song at indexToRemove, so shift songs // towards the beginning of the array for (int from = indexToRemove + 1; from < numSongs; from++) { int to = from -1; songList[to] = songList[from]; } songList[numSongs-1] = null; // optional numSongs--; } } // Remove Example 3: Remove first occurrence of a song that matches // the given title, if any. public void remove(String title) { // Find a song to remove boolean found = false; int indexToRemove = 0; while (indexToRemove < numSongs && !found) { if (songList[indexToRemove].getTitle().equals(title)) { // NOTE .equals found = true; } else { // NOTE: else is required. Why? // not what we want, so keep looking indexToRemove++; } } if (indexToRemove < numSongs) { // Found a song at index to remove, so shift songs // towards the beginning of the array for (int from = indexToRemove + 1; from < numSongs; from++) { songList[from-1] = songList[from]; } songList[numSongs-1] = null; // optional numSongs--; } } // Filter Example 1: Creates and returns a new music rack that // contains only those songs of this music rack that are currently // at a chart position no more than the given chart position. public MusicRack filter(int chartPosition) { // NOTE: newMusicRack is a collection (not an array)!! MusicRack newMusicRack = new MusicRack(); for (int i = 0; i < numSongs; i++) { if (songList[i].getChartPosition() <= chartPosition) { // found a song we need in the new collection newMusicRack.insertAtEnd(songList[i]); // NOTE: Be sure to insert in newMusicRack!! // insertAtEnd will do all the hard part, doubling // the newMusicRack's songList array and keeping // track of the number of song on its music rack } } return newMusicRack; } // Filter Example 2: Creates and returns a new music rack that // contains only those songs of this music rack that the artist contains // the given word. HINT: Look at the Java API to see if there is a // method that will help us here. public MusicRack filter(String word) { MusicRack newMusicRack = new MusicRack(); for (int i = 0; i < numSongs; i++) { if (songList[i].getArtist().indexOf(word) != -1) { // if indexOf is >= 0 then word is in the artist's name newMusicRack.insertAtEnd(songList[i]); // Note: Be sure to insert in newMusicRack!! } } return newMusicRack; } // Returns a String representation of the entire music rack public String toString() { String result = "NumSongs = " + numSongs + " / Length = " + songList.length + "\n"; for (int i=0; i < numSongs; i++) { result += ("songList[" + i + "] = <" + songList[i] + ">\n"); } return result; } // HELPER METHODS: // Insert song in the next available // position at the end of the array. // Helper method for the filter methods // This method is private because there can only be one insert // method to ensure the correct ordering of the songs private void insertAtEnd(Song newSong) { // NOTE: If array is full when this method is called, // use the private method doubleLength() to resize // the array to twice its original size before inserting if (songList.length == numSongs) { // is the array full? doubleLength(); } songList[numSongs] = newSong; numSongs++; // Keep numSongs consistent with the data } // A helper method that doubles the length of the array that holds songs // Use this method only if the array is full before you do an insert private void doubleLength() { Song[] newarray = new Song[songList.length * 2]; for (int i = 0; i < numSongs; i++) { newarray[i] = songList[i]; } songList = newarray; } }