9a9b.md

Back to questions

9a9b: Transposing tunes

This question was adapted, with permission, from a question originally written by Boris Motik.

Assume you are writing a program that controls a musical synthesizer and that therefore needs to represent the structure of tunes. The purpose of this question is to write some classes and interfaces to represent tunes, to which notes and rests can be added. It should be possible to iterate through a tune using Java's "for-each" construct. Furthermore, it should be possible to transpose a tune: raising or lowering its pitch by a given interval. However, transposition should be performed on-the-fly using something called the decorator pattern. The question is structured as a series of steps that will guide you towards a solution.

Step 1

Create an abstract class, TuneElement, that will represent an element of a tune. A TuneElement can either be a note (a period of music during which a particular tone is heard) or a rest (a period of silence).

A note can be described by the following information:

• note name, which is one of C, C#, D, D#, E, F, F#, G, G#, A, A# or B
• note octave, which is an integer determining the octave of the note
• note value, which can be one of whole, half, quarter, eighth or sixteenth

Together, the note name and the note octave determine the pitch of the note in the scientific pitch notation. For example, the pitch of "middle C" is represented by a note with name C and octave 4. The note value determines the duration of the note.

A rest can be described by a note value, which determines the duration of the rest.

Create concrete classes Note and Rest which extend TuneElement to represent notes and rests. You may wish to introduce enumerations for note names and values.

Step 2

Next, Create an interface called Tune. Implementations of Tune will encapsulate a collection of TuneElement objects, and we would like to be able to iterate over these using Java's "for-each" construct. In other words, given a Tune t, we would like to be able to write (for example):

for(TuneElement e : t) {
  System.out.println(t);
}

For this to work, Tune must extend Java's Iterable interface. Iterable is a generic interface; your Tune interface should extend Iterable with respect to the specific type TuneElement. (See hint at the end.)

Tune should specify two further methods:

// Add an element to the tune
void addTuneElement(TuneElement tuneElement);

// Return a tune derived from the original, transposed up
// three semitones
Tune transpose(int interval);

Step 3

Implement Tune with an abstract class, AbstractTune. AbstractTune should provide concrete implementations of two methods: toString(), overridden from Object, and transpose(), as specified by Tune.

For now, you should make transpose() simply return null. We will rectify this in Step 6.

You should implement toString() by iterating over the AbstractTune object, constructing a string consisting of string representations of tune elements separated by spaces. You may wonder how you can iterate over the tune elements in your abstract tune, since we haven't yet defined a data structure that will represent these elements! The trick is to exploit the fact that AbstractTune implements Tune, which extends Iterable. See the end for a stronger hint.

Turning tune elements into strings will involve overriding toString in your Note and Rest classes (and possibly also in enumerations you may have created). A quarter-length "middle C" note should be represented by the string C4(1/4). A half-length rest should be represented as Rest(1/2). Other notes and rests should be represented similarly. The well-known tune Fr`{e}re-Jaques starting on "middle C" would be represented as a string thus (with some line breaks added):

C4(1/4) D4(1/4) E4(1/4) C4(1/4) C4(1/4) D4(1/4) E4(1/4) C4(1/4)
E4(1/4) F4(1/4) G4(1/2) E4(1/4) F4(1/4) G4(1/2)
G4(1/8) A4(1/8) G4(1/8) F4(1/8) E4(1/4) C4(1/4)
G4(1/8) A4(1/8) G4(1/8) F4(1/8) E4(1/4) C4(1/4)
C4(1/4) G3(1/4) C4(1/4) Rest(1/4) C-4(1/4) G3(1/4) C4(1/4) Rest(1/4)

Step 4

Extend AbstractTune with a concrete class, PhysicalTune. PhysicalTune should use a List of TuneElements to represent the contents of the tune. It should also provide the following methods, required by the Tune and Iterable interfaces respectively:

public void addTuneElement(TuneElement tuneElement);

public Iterator<TuneElement> iterator();

Implementing these methods should be very straightforward. Some hints are given at the end of the question.

Step 5

Now your task is to implement transposition of tunes; that is, raising or lowering all the notes in a tune by a given number of semi-tones. For example, C4 raised one semi-tone becomes C#4; A3 lowered two semi-tones becomes G3; C2 lowered one semi-tone drops down into the previous octave to become B1; A4 raised four semi-tones jumps up to the next octave and becomes C#5.

One way to implement transposition would be for the transpose method to return a copy of a PhysicalTune with each note transposed by a given interval. The problem with this approach is that the original and transposed tunes become totally separate. If we add further notes to the original tune, this will not automatically be reflected in the transposed tune, and vice-versa.

Your task is to represent a transposed tune as a "view" of an existing tune, so that if new notes are added to either the transposed tune or the original tune, the result will be visible to both tunes. This can be achieved by making a transposed tune hold a reference to the original tune from which it is derived. Methods on the transposed tune are then implemented by delegation to the original tune, with appropriate modifications to reflect the process of transposition. Chaining objects together in this way is an example of using the decorator design pattern: we can say that a transposed tune decorates a tune by transposing it.

Write a class TransposedTune that extends AbstractTune. A TransposedTune should have two fields: a Tune representing the tune to be transposed) and an int representing the interval of transposition.

The addTuneElement method of TransposedTune should work by adding an appropriate tune element to the original tune. (See hint at the end.)

The iterator method of TransposedTune should return an instance of a new class, TransposedTuneIterator, which you should create. This class should implement Iterator<TuneElement>. You should work out how to implement the next() method of TransposedTuneIterator: this should retrieve a tune element from the original tune, transpose it and then return it. (See hint at the end.)

Step 6

Now you can implement the transpose method in AbstractTune. This method should return a new TransposedTune.

Step 7

Finally, write a short demo program to illustrate that this is working. Experiment a bit: notice that it is possible to transpose a transposed tune!

In my demo program, I write something like this:

Tune frereJaques = new PhysicalTune();
Tune frereJaquesTransposedUp = frereJaques.transpose(3);
Tune frereJaquesTransposedUpAnotherOctave = frereJaquesTransposedUp.transpose(12);

frereJaques.addTuneElement(new Note(NoteName.C, 4, NoteValue.QUARTER));
frereJaques.addTuneElement(new Note(NoteName.D, 4, NoteValue.QUARTER));
... // Remaining notes in Frere Jaques
frereJaques.addTuneElement(new Note(NoteName.C, 4, NoteValue.QUARTER));
frereJaques.addTuneElement(new Rest(NoteValue.QUARTER));

System.out.println("Frere Jaques:\n  " + frereJaques);
System.out.println("Frere Jaques up three semitones:\n  " + frereJaquesTransposedUp);
System.out.println("Frere Jaques up another octave:\n  " + frereJaquesTransposedUpAnotherOctave);

This leads to the following output (abbreviated a bit):

Frere Jaques:
  C4(1/4) D4(1/4) E4(1/4) C4(1/4) ... C4(1/4) G3(1/4) C4(1/4) Rest(1/4)
Frere Jaques up three semitones:
  D#4(1/4) F4(1/4) G4(1/4) D#4(1/4) ... D#4(1/4) A#3(1/4) D#4(1/4) Rest(1/4)
Frere Jaques up another octave:
  D#5(1/4) F5(1/4) G5(1/4) D#5(1/4) ... D#5(1/4) A#4(1/4) D#5(1/4) Rest(1/4)

Hints:

Step 2. This should do the trick:

interface Tune extends Iterable<TuneElement> { ... }

Step 3. Because AbstractTune implements Tune, which extends Iterable<TuneElement>, any concrete class that extends AbstractTune is guaranteed to provide the functions of an iterator. As a result, in your toString() method, you can iterate over this, the AbstractTune (which at runtime will be an instance of a concrete subclass):

public String toString() {
  ...
  for(TuneElement t : this) {
    ...
  }
}

Step 4. You can implement addTuneElement by simply calling add on the List field that you are using to represent the elements of your tune. You can implement iterator by simply calling iterator on the List field that you are using to represent your tune, and returning its result.

Step 5. To implement addTuneElement, you need to be able to translate a Note into an equivalent Note whose pitch is increased or decreased according to the interval of transposition with which your TransposedTune is configured. To do this, it might help to write two utility methods:

// Uses the octave and note name components of a note to turn the
// note into an absolute pitch value
private static int noteToAbsolutePitch(Note note);

// From an absolute pitch value, works out the corresponding octave
// and note name, and returns a Note comprised of these and the given
// note value
private static Note noteFromAbsolutePitch(int pitch, NoteValue value);

(This assumes that you have used an enumeration, NoteValue, to represent the value of a note. If you have done things differently then you'll need to adapt appropriately.)

The TransposedTuneIterator class can be an inner class (preferred method), or a standard class (fine if you are not too confident with inner classes). (If you wish, and have the know-how, you can make this an anonymous inner class.) This iterator should hold a reference to an object of type Iterator<TuneElement>, which should be obtained from the TransposedTune's original tune:

originalTuneIterator = originalTune.iterator();

TransposedTuneIterator must implement the following methods, required by the Iterator interface:

public boolean hasNext();

public TuneElement next();

public void remove();

You can implement hasNext() and remove() trivially by delegating to the original tune's iterator.

Implementing next() is a little trickier: you should call next() on the original iterator to get the next note, then transpose this note up using noteToAbsolutePitch and noteFromAbsolutePitch, and return the result.