2.4. The staff objects collection

2.4.1. Objectives

Music has two dimensions, the horizontal one, the melody, and the vertical one, the harmony. And none of them is maintained in the ImoDocument tree (or ImoScore tree).

Traversing the ImoScore tree following a melody line is not difficult, as the tree is organized by instruments. Therefore it is enough to traverse each instrument children nodes in sequence (breadth-first tree traversing), taking nodes that represent notes and rests.

But traversing the tree following the vertical dimension of music (all notes and rests ordered by time, without segregating by instrument and voice) is impractical. Consider that:

1. The traversing criteria is the absolute time (from minor to higher) at which the musical event that each tree node represents, will take place.
2. Time is not an explicit data of the representation, although once the tree is built, time can be computed and added to the nodes.
3. Even if time is added as an explicit information to each node, there will be no clear path to traverse the nodes in the tree. The only way to traverse music by time, we will have to traverse the hole tree, collect all the nodes representing musical events (notes and rests), and sort this nodes collection by time. And then traverse the resulting collection.

Therefore, we can foresee that for those tasks that will require traversing the score in its vertical dimension, using the ImoScore tree will impose performance penalties. So, if traversing music in is vertical dimension is going to be a frequent task, it is better to precompute time, sort the nodes by time and save the resulting set. This is basically the idea behind the staff objects collection: a collection of nodes ordered by time.

The need for having this auxiliary staff objects collection did not come from musical tasks (play back, harmonic analysis, etc.) for which only musical events (notes and rests) are necessary. Also, for these tasks the cost of creating on demand this ordered collection of notes and rests would probably not cause any performance issue.

The need to create this auxiliary representation comes from rendering, that is, the algorithms for building a bitmap with the engraved score. For rendering music, both music dimensions has to be taken into account at the same time. For instance, notes, rests and other elements in one staff must satisfy the constrains imposed by music engraving rules (i.e. spacing between notes must be proportional to note duration) and, at the same time, must be vertically aligned with notes, rests, and other elements in saves for other instruments. Therefore, for rendering related tasks it is important not having to deal with two representations: the tree for horizontal traversing and the staff objects collection for vertical traversing. Also, We need to take into account not only musical events (notes and rests) but also all other musical symbols that do not take time has to be rendered between two notes and rests, such as clefs or barlines.

Therefore, the main objective of the staff objects collection auxiliary representation is to have an adequate representation for traversing all music objects either:

• Following the music horizontal dimension (time): all notes, rest and the remaining staff objects in one voice, traversed by time and vertical alignment position order.
• Following the music vertical dimension: all notes, rest and the remaining staff objects ordered by time and vertical alignment position order, without further consideration for any other issue (instrument, voice, etc.).

It should also facilitate:

• Traversing the score by instrument, to facilitate processing of selected instruments.
• Traversing the score by staff, to facilitate processing of selected staves.

Once we have a clearer idea of the needs lets develop the details.

2.4.2. Needed information and structure

To get a clearer picture of the kind of need representation let’s use the score shown in following picture and let’s identify the information needed to satisfy our objectives. I have created this score attending not to its musical content but for illustrating different issues; therefore, it has unusual content, such as two consecutive clef changes:

Figure. Sample score to illustrate the information needed

In LDP this score could be represented as (I have numbered the staff objects for later reference):

(score (vers 1.6)
   (instrument
      (musicData
         (clef G)                       #0
         (key D)                        #1
         (time 2 4)                     #2
         (n d5 h v1 (stem up))          #3

         (goBack h)
         (n d4 e g+ v2 (stem down))     #4
         (n f4 e g- v2 (stem down))     #5
         (n a4 q v2 (stem down))        #6
         (barline)                      #7
      )
   )

   (instrument (staves 2)
      (musicData
         (clef G p1)        #8
         (clef F4 p2)       #9
         (key D)            #10
         (time 2 4)         #11
         (n f4 q. p1)       #12
         (clef F4 p1)       #13
         (n a3 e)           #14

         (goBack h)
         (n c3 q p2)        #15
         (n c3 e)           #16
         (clef G p2)        #17
         (clef F p2)        #18
         (n c3 e)           #19
         (barline)          #20
      )
   )
)

Now consider how to transform the LDP tree into the rendered score. Let’s ignore all the details, just think on how to re-order tree nodes to resemble the score layout. First, we realize that the rendered score is similar to a table: each voice is a row and the different vertical alignment lines are the columns of this table:

Figure. Pseudo-columns. Time is in arbitrary units (duration of a 256th note)

Let’s create a table, that mimics the score layout:

The first thing we observe is the need to duplicate certain objects (i.e. keys, clefs, time signatures, barlines) as the object is defined in LDP source code only once but it applies to more than one voice.

A table like this one satisfies our objectives:

• It is easy to traverse events by time: just traverse the table by columns, one after the other.
• It is easy to traverse events by voice: just traverse the table by rows.
• It is easy to select/exclude events for an instrument: just select/ignore certain rows.

A table like the one presented is the base for Lomse ‘staff objects collection’ table, but some changes are needed:

• Instead of voices, Lomse introduce the concept of lines (rows). A line is similar to a voice but chords are allowed as part of a voice. This might sound odd to a musician, as a chord, by definition, is created only when several voices are involved. But the underlying idea in the line concept is to allow for a double treatment of chords in polyphonic instruments (i.e. piano): either as musical event created by simultaneous different voices, or as a single musical event produced by a single instrument.
• Second, notice that the table of our example can not be built just by assigning time and voice to the objects. In some cases, we have used knowledge about score layouting rules. For instance, object #13 (clef F) is placed in time 96 but, how do we decide in which of the columns for time 96? We have used knowledge about clefs layouting (i.e. in a clef change, the clef should be placed immediately before the first coming note) to decide to place the clef in the second column for time 96. As engraving knowledge is not the responsibility of the internal representation builder, our table can not include information about the vertical column, only about time and objects order.

Taking these issues into account, the only table that we can build without using engraving knowledge is a table with a column per time value, such as the following one:

And this table is the basis for the staff objects collection table. In next sections we will see the algorithm for generating the table and how the table is implemented.

2.4.3. Algorithm to create the table

The starting point is the internal model tree, obtained when LDP code is compiled. To get the table, the algorithm is simple. It is just three steps:

1. For each node, determine measure, time, line and staff. The algorithm for assigning line to each node is presented later in Algorithm to assign line.
2. Convert the tree into a table, adding also columns for measure, time, line and staff. Do not add entries for goBack/goFwd nodes.
3. Sort the resulting table by time, line and staff, but keep precedence (stable sort).

Done. The resulting table satisfies our initial objectives.

Let’s see how this algorithm works with the score of our example. In the following picture I show the internal tree (simplified) for our example. I have labeled nodes with the number we assigned to each element in the LDP source code:

score -+- instr0 -+- #0  (clef G)
       |          +- #1  (key D)
       |          +- #2  (time 2 4)
       |          +- #3  (n d5 h v1)
       |          +-     (goBack h)
       |          +- #4  (n d4 e g+ v2)
       |          +- #5  (n f4 e g- v2)
       |          +- #6  (n a4 q v2)
       |          +- #7  (barline)
       |
       +- instr1 -+- #8  (clef G p1)
                  +- #9  (clef F4 p2)
                  +- #10 (key D)
                  +- #11 (time 2 4)
                  +- #12 (n f4 q. p1)
                  +- #13 (clef F4 p1)
                  +- #14 (n a3 e)
                  +-     (goBack h)
                  +- #15 (n c3 q p2)
                  +- #16 (n c3 e)
                  +- #17 (clef G p2)
                  +- #18 (clef F p2)
                  +- #19 (n c3 e)
                  +- #20 (barline)

To convert the tree into the table, we start traversing the tree. First, we set a counter to keep current time. whenever we start traversing a new instrument, the time counter is reset to zero. goFwd and goBack notes, also increments/decrements the time counter. Notes and rests increment the counter by note/rest duration. All other nodes do not change the counter value. As we traverse the tree, time is assigned to each node (just take current time counter value).

Also, while traversing nodes, the line or lines to assign to the node are computed (remember that some objects, such as key signatures, need to be duplicated in several lines). The algorithm for assigning lines is described later. Finally, once all the information for a node is collected, as many rows as assigned lines for the node are created in the table. To illustrate the process, first I have added the collected information to each node:

score -+- instr0 -+- #0  (clef G)        bar0, t0,   line0, staff0
       |          |                      bar0, t0,   line1, staff0
       |          +- #1  (key D)         bar0, t0,   line0, staff0
       |          |                      bar0, t0,   line1, staff0
       |          +- #2  (time 2 4)      bar0, t0,   line0, staff0
       |          |                      bar0, t0,   line1, staff0
       |          +- #3  (n d5 h v1)     bar0, t0,   line0, staff0  t=t+128
       |          +-     (goBack h)      t=t-128
       |          +- #4  (n d4 e g+ v2)  bar0, t0,   line1, staff0  t=t+32
       |          +- #5  (n f4 e g- v2)  bar0, t32,  line1, staff0  t=t+32
       |          +- #6  (n a4 q v2)     bar0, t64,  line1, staff0  t=t+64
       |          +- #7  (barline)       bar0, t128, line0, staff0
       |                                 bar0, t128, line1, staff0
       |
       +- instr1 -+- #8  (clef G p1)     bar0, t0,   line2, staff0
                  +- #9  (clef F4 p2)    bar0, t0,   line3, staff1
                  +- #10 (key D)         bar0, t0,   line2, staff0
                  |                      bar0, t0,   line3, staff1
                  +- #11 (time 2 4)      bar0, t0,   line2, staff0
                  +- #11 (time 2 4)      bar0, t0,   line3, staff1
                  +- #12 (n f4 q. p1)    bar0, t0,   line2, staff0  t=t+96
                  +- #13 (clef F4 p1)    bar0, t96,  line2, staff0
                  +- #14 (n a3 e)        bar0, t96,  line2, staff0  t=t+32
                  +-     (goBack h)      t=t-128
                  +- #15 (n c3 q p2)     bar0, t0,   line3, staff1  t=t+64
                  +- #16 (n c3 e)        bar0, t64,  line3, staff1  t=t+32
                  +- #17 (clef G p2)     bar0, t96,  line3, staff1
                  +- #18 (clef F p2)     bar0, t96,  line3, staff1
                  +- #19 (n c3 e)        bar0, t96,  line3, staff1  t=t+32
                  +- #20 (barline)       bar0, t128, line2, staff0
                                         bar0, t128, line3, staff1

And now transform the tree into a table, duplicating those nodes that apply to several lines, and removing nodes goBack/goFwd:

instr0   #0  (clef G)        bar0       t0         line0       staff0
instr0   #0  (clef G)        bar0       t0         line1       staff0
instr0   #1  (key D)         bar0       t0         line0       staff0
instr0   #1  (key D)         bar0       t0         line1       staff0
instr0   #2  (time 2 4)      bar0       t0         line0       staff0
instr0   #2  (time 2 4)      bar0       t0         line1       staff0
instr0   #3  (n d5 h v1)     bar0       t0         line0       staff0
instr0   #4  (n d4 e g+ v2)  bar0       t0         line1       staff0
instr0   #5  (n f4 e g- v2)  bar0       t32        line1       staff0
instr0   #6  (n a4 q v2)     bar0       t64        line1       staff0
instr0   #7  (barline)       bar0       t128       line0       staff0
instr0   #7  (barline)       bar0       t128       line1       staff0
instr1   #8  (clef G p1)     bar0       t0         line2       staff0
instr1   #9  (clef F4 p2)    bar0       t0         line3       staff1
instr1   #10 (key D)         bar0       t0         line2       staff0
instr1   #10 (key D)         bar0       t0         line3       staff1
instr1   #11 (time 2 4)      bar0       t0         line2       staff0
instr1   #11 (time 2 4)      bar0       t0         line3       staff1
instr1   #12 (n f4 q. p1)    bar0       t0         line2       staff0
instr1   #13 (clef F4 p1)    bar0       t96        line2       staff0
instr1   #14 (n a3 e)        bar0       t96        line2       staff0
instr1   #15 (n c3 q p2)     bar0       t0         line3       staff1
instr1   #16 (n c3 e)        bar0       t64        line3       staff1
instr1   #17 (clef G p2)     bar0       t96        line3       staff1
instr1   #18 (clef F p2)     bar0       t96        line3       staff1
instr1   #19 (n c3 e)        bar0       t96        line3       staff1
instr1   #20 (barline)       bar0       t128       line2       staff0
instr1   #20 (barline)       bar0       t128       line3       staff1

Finally. sort by time, line and staff, but keep precedence (stable sort):

instr0   #0  (clef G)        bar0       t0         line0       staff0
instr0   #1  (key D)         bar0       t0         line0       staff0
instr0   #2  (time 2 4)      bar0       t0         line0       staff0
instr0   #3  (n d5 h v1)     bar0       t0         line0       staff0
instr0   #0  (clef G)        bar0       t0         line1       staff0
instr0   #1  (key D)         bar0       t0         line1       staff0
instr0   #2  (time 2 4)      bar0       t0         line1       staff0
instr0   #4  (n d4 e g+ v2)  bar0       t0         line1       staff0
instr1   #8  (clef G p1)     bar0       t0         line2       staff0
instr1   #10 (key D)         bar0       t0         line2       staff0
instr1   #11 (time 2 4)      bar0       t0         line2       staff0
instr1   #12 (n f4 q. p1)    bar0       t0         line2       staff0
instr1   #9  (clef F4 p2)    bar0       t0         line3       staff1
instr1   #10 (key D)         bar0       t0         line3       staff1
instr1   #11 (time 2 4)      bar0       t0         line3       staff1
instr1   #15 (n c3 q p2)     bar0       t0         line3       staff1
instr0   #5  (n f4 e g- v2)  bar0       t32        line1       staff0
instr0   #6  (n a4 q v2)     bar0       t64        line1       staff0
instr1   #16 (n c3 e)        bar0       t64        line3       staff1
instr1   #13 (clef F4 p1)    bar0       t96        line2       staff0
instr1   #14 (n a3 e)        bar0       t96        line2       staff0
instr1   #17 (clef G p2)     bar0       t96        line3       staff1
instr1   #18 (clef F p2)     bar0       t96        line3       staff1
instr1   #19 (n c3 e)        bar0       t96        line3       staff1
instr0   #7  (barline)       bar0       t128       line0       staff0
instr0   #7  (barline)       bar0       t128       line1       staff0
instr1   #20 (barline)       bar0       t128       line2       staff0
instr1   #20 (barline)       bar0       t128       line3       staff1

Done. The obtained table is the staff object collection auxiliary representation.

The staff object collection plays a fundamental role in the layout algorithms. It is fundamental to have staff objects orderer in the same order in which they will be rendered. In practice, keeping the table ordered is one of the key issues; pay attention to this when adding more features to the library. Some ordering issues:

1. In multi-metric music, bar number is not a meaningful data for sorting entries, as measures are interlaced. Therefore, measure number must not be taken into account for table ordering.
2. To deal with multi-metric music, time has to be absolute, that is, it has to be referred to start of score, not to start of measure. Again, this is due to the fact that in multi-metric music, measure number is not meaningful.
3. As time is absolute, all barlines have the same time than the objects immediately after the barline. In consequence, the sort process must ensure that barlines go before any other object at the same time. But it is not that simple: spacers and other objects, different from notes and rests, that could precede a barline should go before the barline. In fact:
   • Barlines must go before notes/rest at same time, but in other lines.
   • But not before any other object, in the same line, defined before the barline.

2.4.4. Algorithm to assign line

First, let’s see the constraints and invariants:

• The musical voice is an explicit information, present only in notes and rests.
• Any instrument has at least one musical voice.
• For each voice there is exactly one line.
• Musical symbols without voice (that is, other than notes and rests) need to be assigned also at least one line. Notice that this forces that, at least, there is a different line for each staff as some objects (i.e. key signature) are repeated on each staff.

With this information, the rules defining the algorithm to assign line to a musical symbol are simple:

• For each staff create a default line. This line is assigned to all events without voice (i.e. clefs).
• The voice for the first note/rest placed on a staff is assigned to the default line for that staff.
• Any other musical voice originates a new line.
• Multi-shaped objects, that is, objects that must be rendered in all staves (i.e. key signature) are repeated and assigned to the default line on each staff.

2.4.5. Implementation: Involved objects

Class ColStaffObjs represents the table. It encapsulates the staff objects collection for a score. It contains a vector of ColStaffObjsEntry objects. Each object represent an entry in the staff objects collection.

The algorithm to create the table is encapsulated in class ColStaffObjsBuilder.

And the algorithm assign line number to voices/staves is encapsulated in class StaffVoiceLineTable.