User’s Guide, Chapter 21: Ordering and Sorting of Stream Elements

Inside a stream, each object has a position and thus an order in the Stream. Up until now we’ve seen two different ways to describe the position of an element (such as a Note) in a stream. The first is the index of the object in the stream (a number in square brackets) and the second is the offset.

Let’s take a simple Stream:

from music21 import *
s = stream.Measure()
ts1 = meter.TimeSignature('3/4')
s.insert(0, ts1)
s.insert(0, key.KeySignature(2))
s.insert(0, clef.TrebleClef())
s.insert(0, note.Note('C#4'))
s.insert(1, note.Note('D#4'))

We have inserted three elements that take up no space (a TimeSignature, KeySignature, and a Clef) and two elements that take up 1.0 quarter notes (the default length of a Note object). You might notice that the signatures and clef were inserted in a strange order. Don’t worry, we’ll get to that in a bit.

In addition to inserting elements at particular places in a Stream, we can append an element to the end of the Stream:

e = note.Note('E4')
s.append(e)
s.show()
../_images/usersGuide_21_sorting_5_0.png

Now we’re pretty sure that the C# will be the fourth element in the Stream, which is referred to as [3] and the D# will be the fifth, or [4]

s[3]
 <music21.note.Note C#>
s[4]
 <music21.note.Note D#>

The E will be [5] but we can also get it by saying it’s the last element, or [-1]

s[-1]
 <music21.note.Note E>

The other way to describe the position of an element is by its offset.

e.offset
 2.0

You may recall from previous discussions that the offset of an element is its position within the last referenced Stream it was attached to. Thus, if you want to know the offset of an element within a particular Stream, it is always safer to use one the following methods: .getOffsetBySite(stream):

e.getOffsetBySite(s)
 2.0

Or to call stream.elementOffset(element). This is a little bit faster so it’s what we use internally. It will always give the same result if e is in s, but if e might not be in s but be derived from an element in s then .getOffsetBySite will trace the .derivation.chain() to find it.

s.elementOffset(e)
 2.0

If you want to find all the elements at a particular offset, call .getElementsByOffset on the Stream. Note that if any elements are found it returns a StreamIterator, so you will need to use the square bracket index to reference it:

s.getElementsByOffset(2.0)[0]
 <music21.note.Note E>

This description might seem a bit obnoxious, but it is necessary because you can get multiple elements back, such as with an offset range:

y = s.getElementsByOffset(1.0, 3.0)
(y[0], y[1])
 (<music21.note.Note D#>, <music21.note.Note E>)

At this point, you might think that you know everything about how elements are positioned in a Stream, but there are a few more points that are important and point to the power of music21. Let’s show the Stream as a text file:

s.show('text')
 {0.0} <music21.clef.TrebleClef>
 {0.0} <music21.key.KeySignature of 2 sharps>
 {0.0} <music21.meter.TimeSignature 3/4>
 {0.0} <music21.note.Note C#>
 {1.0} <music21.note.Note D#>
 {2.0} <music21.note.Note E>

Something has happened: the TrebleClef object which was inserted third has now become the first element of the Stream. The KeySignature and TimeSignature objects have also switched position. Now all three are in the order we’d expect to see them in a score:

(s[0], s[1], s[2])
 (<music21.clef.TrebleClef>,
  <music21.key.KeySignature of 2 sharps>,
  <music21.meter.TimeSignature 3/4>)

Even though they have the same .offset, each of these objects knows its place in the Stream, because of something called .classSortOrder. Each Class and each instance of the class has a default sort order so that if it is at the same offset as a member of a different class, one will sort before the other:

(s[0].classSortOrder, s[1].classSortOrder, s[2].classSortOrder)
 (0, 2, 4)

In fact, classSortOrder is present not just on objects but on classes:

(clef.Clef.classSortOrder, key.KeySignature.classSortOrder, meter.TimeSignature.classSortOrder)
 (0, 2, 4)

Notes have a higher classSortOrder and thus sort even later, hence why the C# appears after the clefs and signatures:

(note.Note.classSortOrder, base.Music21Object.classSortOrder)
 (20, 20)

There are a few elements that sort even lower than Clefs because they usually refer to the area of the composition that precedes the clef:

(bar.Barline.classSortOrder, instrument.Instrument.classSortOrder, metadata.Metadata.classSortOrder)
 (-5, -25, -30)

The numbers are actually completely arbitrary (it could be -6.432 instead of -5), only the order of numbers (-25 is less than -5) matters.

If we put a second TimeSignature into the stream at offset 0 (like some pieces do with multiple interpretations for meter), it will have a tie for its .offset and .classSortOrder. Which one will come first? It’s the first one inserted:

ts2 = meter.TimeSignature('6/8')
s.insert(0, ts2)
s.show('text')
 {0.0} <music21.clef.TrebleClef>
 {0.0} <music21.key.KeySignature of 2 sharps>
 {0.0} <music21.meter.TimeSignature 3/4>
 {0.0} <music21.meter.TimeSignature 6/8>
 {0.0} <music21.note.Note C#>
 {1.0} <music21.note.Note D#>
 {2.0} <music21.note.Note E>

If we wanted to make sure that the two TimeSignatures appeared in a particular order regardless of when they were inserted, there is one way to do so: set the .priority attribute on the TimeSignature. Every Music21Object has a priority attribute, and the default is 0. Negative numbers make an element sort before a default element. Positive numbers sort after.

Let us insert two more notes into the stream, at offsets 1 and 2, but we’ll make the note at offset 1 come before the D# and the one at offset 2 come after the E, so we have a chromatic scale fragment:

d = note.Note('D')
d.priority = -10
eis = note.Note('E#')
eis.priority = 10
s.insert(1.0, d)
s.insert(2.0, eis)
s.show('text')
 {0.0} <music21.clef.TrebleClef>
 {0.0} <music21.key.KeySignature of 2 sharps>
 {0.0} <music21.meter.TimeSignature 3/4>
 {0.0} <music21.meter.TimeSignature 6/8>
 {0.0} <music21.note.Note C#>
 {1.0} <music21.note.Note D>
 {1.0} <music21.note.Note D#>
 {2.0} <music21.note.Note E>
 {2.0} <music21.note.Note E#>

Some things to note about priority:

  1. Priority changes immediately affect the sorting of the Stream (in v.3 or above). Before that if you wanted to change the priority of an object, you’d need to remove it and then reinsert it.
d.priority = 20
s.remove(d)
s.insert(1.0, d)
s.show('text')
 {0.0} <music21.clef.TrebleClef>
 {0.0} <music21.key.KeySignature of 2 sharps>
 {0.0} <music21.meter.TimeSignature 3/4>
 {0.0} <music21.meter.TimeSignature 6/8>
 {0.0} <music21.note.Note C#>
 {1.0} <music21.note.Note D#>
 {1.0} <music21.note.Note D>
 {2.0} <music21.note.Note E>
 {2.0} <music21.note.Note E#>
  1. Priority is currently a global property that affects all Streams that an object is in. This is behavior that may change in later versions.
  2. Priority overrides classSortOrder. So if we wanted to move the 6/8 TimeSignature (ts2) to sort before the 3/4 (ts1), it is not enough to shift the priority of ts2 and reinsert it:
ts2.priority = -5
s.remove(ts2)
s.insert(0.0, ts2)
s.show('text')
 {0.0} <music21.meter.TimeSignature 6/8>
 {0.0} <music21.clef.TrebleClef>
 {0.0} <music21.key.KeySignature of 2 sharps>
 {0.0} <music21.meter.TimeSignature 3/4>
 {0.0} <music21.note.Note C#>
 {1.0} <music21.note.Note D#>
 {1.0} <music21.note.Note D>
 {2.0} <music21.note.Note E>
 {2.0} <music21.note.Note E#>

Now the 6/8 TimeSignature appears before the clef and key signature. A fix for this would involve assigning some priority to each object connected to its sort order:

for el in s.getElementsByOffset(0.0):
    el.priority = el.classSortOrder

ts2.priority = 3 # between KeySignature (priority = 2) and TimeSignature (priority = 4)
s.show('text')
 {0.0} <music21.clef.TrebleClef>
 {0.0} <music21.key.KeySignature of 2 sharps>
 {0.0} <music21.meter.TimeSignature 6/8>
 {0.0} <music21.meter.TimeSignature 3/4>
 {0.0} <music21.note.Note C#>
 {1.0} <music21.note.Note D#>
 {1.0} <music21.note.Note D>
 {2.0} <music21.note.Note E>
 {2.0} <music21.note.Note E#>

Behind the scenes:

How does sorting actually work? Music21 uses six attributes to determine which elements go before or after each other. The six-element tuple that determines sort order can be accessed on any Music21Object by calling the method .sortTuple():

ts1.sortTuple()
 SortTuple(atEnd=0, offset=0.0, priority=4, classSortOrder=4, isNotGrace=1, insertIndex=0)
ts2.sortTuple()
 SortTuple(atEnd=0, offset=0.0, priority=3, classSortOrder=4, isNotGrace=1, insertIndex=148)

A SortTuple is a lightweight class derived from the NamedTuple object that can be compared using the > and < operators. Each of the elements is compared from left to right; if there is a tie on one attribute then the next one becomes important:

ts1.sortTuple() > ts2.sortTuple()
 True

SortTuples live in their own module music21.sorting and have a few cool features. Since the main point of comparison is offset, SortTuples can compare against plain integers or floats or Fractions by comparing their offsets (and atEnd, which we’ll get to in a second).

st = sorting.SortTuple(atEnd=0, offset=10.0, priority=1, classSortOrder=4, isNotGrace=1, insertIndex=5)
st > 8.0
 True

Because they can be unwieldly to display, SortTuples have a .shortRepr() call which summarizes the main information in them: the offset, the priority, the classSortOrder, and the insertIndex.

st.shortRepr()
 '10.0 <1.4.5>'

In this case, the third element, priority, decides the order. The first attribute, atEnd, is 0 for normal elements, and 1 for an element stored at the end of a Stream. Let’s add a courtesy KeySignature change at the end of s:

ks2 = key.KeySignature(-3)
s.storeAtEnd(ks2)
ks2.sortTuple()
 SortTuple(atEnd=1, offset=0.0, priority=0, classSortOrder=2, isNotGrace=1, insertIndex=154)

Putting a rightBarline on a Measure has the same effect:

rb = bar.Barline('double')
s.rightBarline = rb
rb.sortTuple()
 SortTuple(atEnd=1, offset=0.0, priority=0, classSortOrder=-5, isNotGrace=1, insertIndex=155)
rb.sortTuple().shortRepr()
 'End <0.-5.155>'

The next three attributes (offset, priority, classSortOrder) have been described. isNotGrace is 0 if the note is a grace note, 1 (default) if it is any other note or not a note. Grace notes sort before other notes at the same offset and priority. The last attribute is an ever increasing index of the number of elements that have had SiteReferences added to it.

(Advanced topic: the order that elements were inserted is used in order to make sure that elements do not shift around willy-nilly, but it’s not something to use often or to rely on for complex calculations. For this reason, we have not exposed it as something easy to get, but if you need to access it, here’s the formula:)

(ts1.sites.siteDict[id(s)].globalSiteIndex, ts2.sites.siteDict[id(s)].globalSiteIndex)
 (0, 148)

Streams have an attribute to cache whether they have been sorted, so that .sort() only needs to be called when a change has been made that alters the sort order.

s.isSorted
 False

Calling a command that needs a particular order (.show(), .getElementsByClass(), [x], etc.) automatically sorts the Stream:

s[0]
s.isSorted
 True

There is one more way that elements in a Stream can be returned, for advanced uses only. Each Stream has an autoSort property. By default it is On. But if you turn it off, then elements are returned in the order they are added regardless of offset, priority, or classSortOrder. Here is an example of that:

s.autoSort = False
ts1.setOffsetBySite(s, 20.0)
s.show('text')
 {0.0} <music21.clef.TrebleClef>
 {0.0} <music21.key.KeySignature of 2 sharps>
 {0.0} <music21.meter.TimeSignature 6/8>
 {20.0} <music21.meter.TimeSignature 3/4>
 {0.0} <music21.note.Note C#>
 {1.0} <music21.note.Note D#>
 {1.0} <music21.note.Note D>
 {2.0} <music21.note.Note E>
 {2.0} <music21.note.Note E#>
 {20.0} <music21.bar.Barline style=double>
 {20.0} <music21.key.KeySignature of 3 flats>

The setting autoSort = False can speed up some operations if you already know that all the notes are in order. Inside the stream/core.py module you’ll see some even faster operations such as _insertCore() and _appendCore() which are even faster and which we use when translating from one format to another. After running an _insertCore() operation, the Stream is in an unusuable state until core.elementsChanged() is run, which lets the Stream ruminate over its new state as if a normal insert() or append() operation has been done. Mixing _insertCore() and _appendCore() commands without running _elementsChanged() is likely to have disasterous consequences. Use one or the other.

If you want to get back to the sorted state, just turn autoSort = True:

s.autoSort = True
s.isSorted = False
s.show('text')
 {0.0} <music21.clef.TrebleClef>
 {0.0} <music21.key.KeySignature of 2 sharps>
 {0.0} <music21.meter.TimeSignature 6/8>
 {0.0} <music21.note.Note C#>
 {1.0} <music21.note.Note D#>
 {1.0} <music21.note.Note D>
 {2.0} <music21.note.Note E>
 {2.0} <music21.note.Note E#>
 {20.0} <music21.meter.TimeSignature 3/4>
 {20.0} <music21.bar.Barline style=double>
 {20.0} <music21.key.KeySignature of 3 flats>

Note that this is a destructive operation. Turning autoSort back to False won’t get you back the earlier order:

s.autoSort = False
s.show('text')
 {0.0} <music21.clef.TrebleClef>
 {0.0} <music21.key.KeySignature of 2 sharps>
 {0.0} <music21.meter.TimeSignature 6/8>
 {0.0} <music21.note.Note C#>
 {1.0} <music21.note.Note D#>
 {1.0} <music21.note.Note D>
 {2.0} <music21.note.Note E>
 {2.0} <music21.note.Note E#>
 {20.0} <music21.meter.TimeSignature 3/4>
 {20.0} <music21.bar.Barline style=double>
 {20.0} <music21.key.KeySignature of 3 flats>

Now that you’ve gotten everything sorted out, let’s move on to Chapter 22: Graphing Music21 Streams