In order to have an interesting application of arrays, we will use a simple musical note player. First, download and compile the following program: MusicalNotePlayer.java. Run it, listen to the results. Now, look inside that file. You will see a method with this signature:
public static void playNotes(int[] notes, int[] times) throws Exception {
}
Here is a simple explanation of how this works, taken from the header comment in the file:
// Simple demo of a simple musical note player.
// It takes two arrays -- one containing the notes, the other containing the times for each note.
// For the notes, 60 is middle C. 61 is C# (the next note). 62 is D (the note after that).
// Legal note range: 1 to 88 (inclusive)
// For the times, 64 is a typical quarter note, 256 a typical whole note.
// Legal time range: 1 to 256 (inclusive)
// If the "times" array is null, it will play all quarter notes.
You do not need to understand music theory in order to complete this exercise. However, the methods you write here will create arrays of integers which can be used as arguments to the "playNotes" method. So you can hear your results! Fun!
- Write a method with this signature:
public static int[] transpose(int[] notes, int step) {
}
This method makes a song higher-pitched or lower-pitched. This method takes a non-null array of notes (as described above), and another int, the "step", and returns a new array of notes where each note in the resulting "transposed" array equals the corresponding note in the original array plus the (possibly-negative) step. There is this exception, however: in no case shall you transpose so that any notes fall outside of the legal range of [1,88]. In such a case, you should reduce the step's magnitude by just enough to keep the transposed result in range. For example, if the highest note in the incoming array is 80, and the step is +10, then you should reduce the step to +8. Similarly, if the lowest note in the incoming array is 8, and the step is -10, you should change the step to be -7. Be sure to include an appropriate test method! Also, for fun, try transposing the sample song in the MusicalNotePlayer, perhaps as such:
for (int step=0; step < 12; step++)
playNotes(transpose(songNotes,step), songTimes); // a familiar song, now transposed repeatedly
You should hear the song played repeatedly, increasing its pitch by a little bit (one-half step) each time it plays.
- Write a method with this signature:
public static int[] changeTempo(int[] times, double rate) {
}
This method speeds up or slows down a song. This method takes a non-null array of times (as described above), and a double, the "rate" of change, and returns a new array of times where each time in the resulting array equals the corresponding time in the original array times the rate and then rounded back to the nearest int. There is this exception, however: in no case shall you adjust the times so that any times fall outside of the legal range of [1,256]. In such a case, you should adjust the rate's magnitude by just enough to keep the result in range. For example, if the longest time in the incoming array is 128, and the rate is 3, then you should reduce the rate to (256.0/128.0), or 2. Similarly, if the shortest time in the incoming array is 16, and the rate is (1.0/64.0), you should change the rate to be (1.0/16.0). Be sure to include an appropriate test method! Also, for fun, try changing the tempo of the sample song in the MusicalNotePlayer, perhaps as such:
for (double rate=2.0; rate>(1.0/8.0); rate /= 2)
playNotes(songNotes, changeTempo(songTimes, rate)); // a familiar song, now increasingly faster
You should hear the song played repeatedly, playing twice as fast each time it plays.
For the next few problems, we will use a string encoding of song notes and times. Why? Because, even though the above notes-and-times-arrays design works just fine for a computer, it is not a very natural design for humans. To let us mortals enter music into this player, we will support a more human-readable format. The following picture shows the mapping for part of the keyboard (with an explanation to follow):
The numbers on the keys (between 48 and 74 in the figure) are the note values as described above. So #60 is "middle C". The keys are labeled as such: the large "white" keys repeat the pattern ABCDEFG. However, they also have an octave associated with them. The octaves begin on each C note, where middle C is in the 5th octave (and so is written C5). The C one octave below middle C, at note #48, is in the 4th octave, and so is written C4. Now, the smaller "black" keys (blue in the picture) are sharps and flats. Each short key has two labels -- either it is the sharp of the key to its left (written with a "#" character after the key name) or it is a flat of the key to the right (written with a "b" character after the key name). So you can label note #70 as either "A#5" or "Bb5" -- these are the same note.
Now that you understand how notes are encoded, we also have to encode times. This is easier. We will use "w" for a whole note (256), "h" for a half note (128), "q" for a quarter note (64), "e" for an eighth note (32), and "s" for a sixteenth note (16). So "C5q" indicates note 60 with a time of 64.
Finally, we will encode a song as a string of space-separated notes. Here, for example, is a song you may recognize:
String song = "C5q D5q E5q C5q C5q D5q E5q C5q " +
"E5q F5q G5h E5q F5q G5h " +
"G5e A5e G5e F5e E5q C5q G5e A5e G5e F5e E5q C5q " +
"C5q G4q C5h C5q G4q C5h";
And here is a helpful hint: You will probably want to use the "split" method for strings to turn a space-delimited song like above into an array of strings representing each note, like this:
String[] noteStrings = song.split(" ");
- Write a method with this signature:
public static int[] getTimes(String encoding) {
}
This is one of two methods that we will need to decode an encoded string such as the one for the song above. This method takes an encoding, which you can presume is non-null (though not necessarily non-empty!) and is a legal encoding according to the description supplied, and returns an array of the times that should be provided to the playNotes method in order to play the song according to the encoded string. If the string is empty, you should return a non-null array of size zero. Be sure to include an appropriate test method!
- Write a method with this signature:
public static int[] getNotes(String encoding) {
}
This is the other of two methods that we will need to decode an encoded string such as the one for the song above. This method takes an encoding, which you can presume is non-null (though not necessarily non-empty!) and is a legal encoding according to the description supplied, and returns an array of the notes that should be provided to the playNotes method in order to play the song according to the encoded string. If the string is empty, you should return a non-null array of size zero. Be sure to include an appropriate test method!
- Write a method with this signature:
public static void playSong(String encoding) throws Exception {
}
This method should take an encoded string and, using your two decoding methods you just wrote, obtain the times and notes and supply these to playNotes to actually play the encoded song. While you cannot easily automatically test this method, you should provide some sort of auditory testing.
Note: an extra point of bonus will be awarded to students who include interesting songs as part of their test suite. This is not enough to justify entering the entire works of Beethoven, but perhaps enough to motivate some of you to do something interesting here!
As we discussed in class, after the Kth pass of bubblesort, the K largest values are all in their proper place at the top of the array, so we do not have to even check them! The code in the class notes does not include this optimization. Write a method:
public static void fasterBubblesort(int[] a) {
}
This method is the same as the traditional bubblesort method from class, only with the stated optimization.
Write a method:
public static void backwardsInsertionsort(int[] a) {
}
This method is the same as the insertionsort method from class, only it will sort from highest to lowest.
Write a method:
public static void selectionsortForStrings(String[] a) {
}
This method is the same as the selectionsort method from class, only it will sort an array of Strings rather than an array of ints. The tricky part here is that you cannot use "<" or ">" to compare two strings. Instead, you must use the "compareTo" method. If you have two strings, s1 and s2, then instead of testing if (s1 < s2), which is not allowed, you use the result of a call to s1.compareTo(s2). This method returns a negative number if s1 is less than s2, zero if s1 equals s2, and a positive number if s1 is greater than s2.
Write a method:
public static double median(double[] a) {
}
This method takes a non-null and non-empty and possibly unordered array of doubles and returns the median of the values in that array, being careful not to modify the values in the array itself! We call this a non-destructive algorithm. The median of an ordered array with an odd number of elements is the value of the element in the middle. The median of an ordered array with an even number of elements is the average of the two values in the middle. Remember the incoming array is unordered, and remember not to modify the incoming array.