.. _usersGuide_21_sorting:

.. WARNING: DO NOT EDIT THIS FILE:
   AUTOMATICALLY GENERATED.
   PLEASE EDIT THE .py FILE DIRECTLY.


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
:class:`~music21.stream.Stream`. Up until now we've seen two different
ways to describe the position of an element (such as a
:class:`~music21.note.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:

.. code:: python

    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:

.. code:: python

    e = note.Note('E4')
    s.append(e)
    s.show()




.. image:: 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]``

.. code:: python

    s[3]




.. parsed-literal::
   :class: ipython-result

    <music21.note.Note C#>



.. code:: python

    s[4]




.. parsed-literal::
   :class: ipython-result

    <music21.note.Note D#>



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

.. code:: python

    s[-1]




.. parsed-literal::
   :class: ipython-result

    <music21.note.Note E>



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

.. code:: python

    e.offset




.. parsed-literal::
   :class: ipython-result

    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 the method
``.getOffsetBySite(stream)``:

.. code:: python

    e.getOffsetBySite(s)




.. parsed-literal::
   :class: ipython-result

    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 new Stream, so you will need to use the square
bracket index to reference it:

.. code:: python

    s.getElementsByOffset(2.0)[0]




.. parsed-literal::
   :class: ipython-result

    <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:

.. code:: python

    y = s.getElementsByOffset(1.0, 3.0)
    (y[0], y[1])




.. parsed-literal::
   :class: ipython-result

    (<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:

.. code:: python

    s.show('text')


.. parsed-literal::
   :class: ipython-result

    {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:

.. code:: python

    (s[0], s[1], s[2])




.. parsed-literal::
   :class: ipython-result

    (<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:

.. code:: python

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




.. parsed-literal::
   :class: ipython-result

    (0, 2, 4)



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

.. code:: python

    (clef.Clef.classSortOrder, key.KeySignature.classSortOrder, meter.TimeSignature.classSortOrder)




.. parsed-literal::
   :class: ipython-result

    (0, 2, 4)



Notes sort even higher, hence why the C# appears after the clefs and
signatures:

.. code:: python

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




.. parsed-literal::
   :class: ipython-result

    (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:

.. code:: python

    (bar.Barline.classSortOrder, instrument.Instrument.classSortOrder, metadata.Metadata.classSortOrder)




.. parsed-literal::
   :class: ipython-result

    (-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:

.. code:: python

    ts2 = meter.TimeSignature('6/8')
    s.insert(0, ts2)
    s.show('text')


.. parsed-literal::
   :class: ipython-result

    {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:

.. code:: python

    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')


.. parsed-literal::
   :class: ipython-result

    {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#>


Three things to note about priority:

(1) Priority changes do not immediately affect the sorting of the
    Stream, so if you want to change the priority of an object, you'll
    need to remove it and then reinsert it.

.. code:: python

    d.priority = 20
    s.remove(d)
    s.insert(1.0, d)
    s.show('text')


.. parsed-literal::
   :class: ipython-result

    {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#>


(2) Priority is currently a global property that affects all Streams
    that an object is in. This is behavior that may change in later
    versions.

(3) 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:

.. code:: python

    ts2.priority = -5
    s.remove(ts2)
    s.insert(0.0, ts2)
    s.show('text')


.. parsed-literal::
   :class: ipython-result

    {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 it's appearing before the clef and key signature. A fix for this
would involve assigning some priority to each object at offset 0.0 and
then forcing a re-sorting:

.. code:: python

    for el in s.getElementsByOffset(0.0):
        el.priority = el.classSortOrder
    
    ts2.priority = 3 # between KeySignature (priority = 2) and TimeSignature (priority = 4)
    s.isSorted = False
    s.show('text')


.. parsed-literal::
   :class: ipython-result

    {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()``:

.. code:: python

    ts1.sortTuple()




.. parsed-literal::
   :class: ipython-result

    SortTuple(atEnd=0, offset=0.0, priority=4, classSortOrder=4, isNotGrace=1, insertIndex=0)



.. code:: python

    ts2.sortTuple()




.. parsed-literal::
   :class: ipython-result

    SortTuple(atEnd=0, offset=0.0, priority=3, classSortOrder=4, isNotGrace=1, insertIndex=124)



A ``SortTuple`` is a lightweight ``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:

.. code:: python

    ts1.sortTuple() > ts2.sortTuple()




.. parsed-literal::
   :class: ipython-result

    True



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``:

.. code:: python

    ks2 = key.KeySignature(-3)
    s.storeAtEnd(ks2)
    ks2.sortTuple()




.. parsed-literal::
   :class: ipython-result

    SortTuple(atEnd=1, offset=0.0, priority=0, classSortOrder=2, isNotGrace=1, insertIndex=130)



Putting a rightBarline on a Measure has the same effect:

.. code:: python

    rb = bar.Barline('double')
    s.rightBarline = rb
    rb.sortTuple()




.. parsed-literal::
   :class: ipython-result

    SortTuple(atEnd=1, offset=0.0, priority=0, classSortOrder=-5, isNotGrace=1, insertIndex=131)



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. 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:)

.. code:: python

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




.. parsed-literal::
   :class: ipython-result

    (0, 124)



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.

.. code:: python

    s.isSorted




.. parsed-literal::
   :class: ipython-result

    False



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

.. code:: python

    s[0]
    s.isSorted




.. parsed-literal::
   :class: ipython-result

    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:

.. code:: python

    s.autoSort = False
    ts1.setOffsetBySite(s, 20.0)
    s.show('text')


.. parsed-literal::
   :class: ipython-result

    {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.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
``_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``:

.. code:: python

    s.autoSort = True
    s.isSorted = False
    s.show('text')


.. parsed-literal::
   :class: ipython-result

    {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:

.. code:: python

    s.autoSort = False
    s.show('text')


.. parsed-literal::
   :class: ipython-result

    {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>
