Internal data structures for timespan collections.
This is an implementation detail of the TimespanCollection class.
A node in an TimespanCollection.
This class is only used by TimespanCollection, and should not be instantiated by hand. It stores a list of ElementTimespans, as well as various data which describes the internal structure of the tree.
>>> startOffset = 1.0
>>> node = stream.timespanNode.TimespanCollectionNode(startOffset)
>>> node
<Node: Start:1.0 Indices:(-1:-1:-1:-1) Length:{0}>
Please consult the Wikipedia entry on AVL trees (https://en.wikipedia.org/wiki/AVL_tree) for a very detailed description of how this datastructure works.
TimespanCollectionNode read/write properties
The left child of this node.
Setting the left child triggers a node update.
>>> score = stream.timespans.makeExampleScore()
>>> tree = stream.timespans.streamToTimespanCollection(score, flatten=True, classList=(note.Note, chord.Chord))
>>> print(tree._rootNode.debug())
<Node: Start:3.0 Indices:(0:5:6:12) Length:{1}>
L: <Node: Start:1.0 Indices:(0:2:3:5) Length:{1}>
L: <Node: Start:0.0 Indices:(0:0:2:2) Length:{2}>
R: <Node: Start:2.0 Indices:(3:3:5:5) Length:{2}>
R: <Node: Start:5.0 Indices:(6:8:9:12) Length:{1}>
L: <Node: Start:4.0 Indices:(6:6:8:8) Length:{2}>
R: <Node: Start:6.0 Indices:(9:9:11:12) Length:{2}>
R: <Node: Start:7.0 Indices:(11:11:12:12) Length:{1}>
>>> print(tree._rootNode.leftChild.debug())
<Node: Start:1.0 Indices:(0:2:3:5) Length:{1}>
L: <Node: Start:0.0 Indices:(0:0:2:2) Length:{2}>
R: <Node: Start:2.0 Indices:(3:3:5:5) Length:{2}>
The right child of this node.
Setting the right child triggers a node update.
>>> score = stream.timespans.makeExampleScore()
>>> tree = stream.timespans.streamToTimespanCollection(score, flatten=True, classList=(note.Note, chord.Chord))
>>> print(tree._rootNode.debug())
<Node: Start:3.0 Indices:(0:5:6:12) Length:{1}>
L: <Node: Start:1.0 Indices:(0:2:3:5) Length:{1}>
L: <Node: Start:0.0 Indices:(0:0:2:2) Length:{2}>
R: <Node: Start:2.0 Indices:(3:3:5:5) Length:{2}>
R: <Node: Start:5.0 Indices:(6:8:9:12) Length:{1}>
L: <Node: Start:4.0 Indices:(6:6:8:8) Length:{2}>
R: <Node: Start:6.0 Indices:(9:9:11:12) Length:{2}>
R: <Node: Start:7.0 Indices:(11:11:12:12) Length:{1}>
>>> print(tree._rootNode.rightChild.debug())
<Node: Start:5.0 Indices:(6:8:9:12) Length:{1}>
L: <Node: Start:4.0 Indices:(6:6:8:8) Length:{2}>
R: <Node: Start:6.0 Indices:(9:9:11:12) Length:{2}>
R: <Node: Start:7.0 Indices:(11:11:12:12) Length:{1}>
>>> print(tree._rootNode.rightChild.rightChild.debug())
<Node: Start:6.0 Indices:(9:9:11:12) Length:{2}>
R: <Node: Start:7.0 Indices:(11:11:12:12) Length:{1}>
>>> print(tree._rootNode.rightChild.rightChild.rightChild.debug())
<Node: Start:7.0 Indices:(11:11:12:12) Length:{1}>
TimespanCollectionNode methods
Get a debug of the Node:
>>> score = stream.timespans.makeExampleScore()
>>> tree = stream.timespans.streamToTimespanCollection(score, flatten=True, classList=(note.Note, chord.Chord))
>>> rn = tree._rootNode
>>> rn
<Node: Start:3.0 Indices:(0:5:6:12) Length:{1}>
>>> print(rn.debug())
<Node: Start:3.0 Indices:(0:5:6:12) Length:{1}>
L: <Node: Start:1.0 Indices:(0:2:3:5) Length:{1}>
L: <Node: Start:0.0 Indices:(0:0:2:2) Length:{2}>
R: <Node: Start:2.0 Indices:(3:3:5:5) Length:{2}>
R: <Node: Start:5.0 Indices:(6:8:9:12) Length:{1}>
L: <Node: Start:4.0 Indices:(6:6:8:8) Length:{2}>
R: <Node: Start:6.0 Indices:(9:9:11:12) Length:{2}>
R: <Node: Start:7.0 Indices:(11:11:12:12) Length:{1}>
Return a list of the debugging information of the tree (used for _debug): >>> score = stream.timespans.makeExampleScore() >>> tree = stream.timespans.streamToTimespanCollection(score, flatten=True, classList=(note.Note, chord.Chord)) >>> rn = tree._rootNode >>> rn.getDebugPieces() [‘<Node: Start:3.0 Indices:(0:5:6:12) Length:{1}>’,
‘tL: <Node: Start:1.0 Indices:(0:2:3:5) Length:{1}>’, ‘ttL: <Node: Start:0.0 Indices:(0:0:2:2) Length:{2}>’, ‘ttR: <Node: Start:2.0 Indices:(3:3:5:5) Length:{2}>’, ‘tR: <Node: Start:5.0 Indices:(6:8:9:12) Length:{1}>’, ‘ttL: <Node: Start:4.0 Indices:(6:6:8:8) Length:{2}>’, ‘ttR: <Node: Start:6.0 Indices:(9:9:11:12) Length:{2}>’, ‘tttR: <Node: Start:7.0 Indices:(11:11:12:12) Length:{1}>’]
Updates the height and balance attributes of the nodes.
Called automatically when the .leftChild or .rightChild are changed.
Returns None
TimespanCollectionNode instance variables
Gets the difference in heights of the two subtrees rooted on this node.
This attribute is used to help balance the AVL tree.
>>> score = stream.timespans.makeExampleScore()
>>> tree = stream.timespans.streamToTimespanCollection(score, flatten=True, classList=(note.Note, chord.Chord))
>>> print(tree._debug())
<Node: Start:3.0 Indices:(0:5:6:12) Length:{1}>
L: <Node: Start:1.0 Indices:(0:2:3:5) Length:{1}>
L: <Node: Start:0.0 Indices:(0:0:2:2) Length:{2}>
R: <Node: Start:2.0 Indices:(3:3:5:5) Length:{2}>
R: <Node: Start:5.0 Indices:(6:8:9:12) Length:{1}>
L: <Node: Start:4.0 Indices:(6:6:8:8) Length:{2}>
R: <Node: Start:6.0 Indices:(9:9:11:12) Length:{2}>
R: <Node: Start:7.0 Indices:(11:11:12:12) Length:{1}>
This tree has one more depth on the right than on the left
>>> tree._rootNode.balance
1
The leftChild of the rootNote is perfectly balanced, while the rightChild is off by one (acceptable).
>>> tree._rootNode.leftChild.balance
0
>>> tree._rootNode.rightChild.balance
1
The rightChild’s children are also (acceptably) unbalanced:
>>> tree._rootNode.rightChild.leftChild.balance
0
>>> tree._rootNode.rightChild.rightChild.balance
1
The height of the subtree rooted on this node.
This property is used to help balance the AVL tree.
>>> score = stream.timespans.makeExampleScore()
>>> tree = stream.timespans.streamToTimespanCollection(score, flatten=True, classList=(note.Note, chord.Chord))
>>> print(tree._debug())
<Node: Start:3.0 Indices:(0:5:6:12) Length:{1}>
L: <Node: Start:1.0 Indices:(0:2:3:5) Length:{1}>
L: <Node: Start:0.0 Indices:(0:0:2:2) Length:{2}>
R: <Node: Start:2.0 Indices:(3:3:5:5) Length:{2}>
R: <Node: Start:5.0 Indices:(6:8:9:12) Length:{1}>
L: <Node: Start:4.0 Indices:(6:6:8:8) Length:{2}>
R: <Node: Start:6.0 Indices:(9:9:11:12) Length:{2}>
R: <Node: Start:7.0 Indices:(11:11:12:12) Length:{1}>
>>> tree._rootNode.height
3
>>> tree._rootNode.rightChild.height
2
>>> tree._rootNode.rightChild.rightChild.height
1
>>> tree._rootNode.rightChild.rightChild.rightChild.height
0
The timespan start index of only those timespans stored in this node.
The timespan stop index of only those timespans stored in this node.
A list of Timespans starting at this node’s start offset.
Timespans are sorted by their _SortTuple, if they contain an element, and otherwise by their stop offset.
>>> score = stream.timespans.makeExampleScore()
>>> tree = stream.timespans.streamToTimespanCollection(score, flatten=True, classList=(note.Note, chord.Chord))
>>> print(tree._rootNode.debug())
<Node: Start:3.0 Indices:(0:5:6:12) Length:{1}> L: <Node: Start:1.0 Indices:(0:2:3:5) Length:{1}> L: <Node: Start:0.0 Indices:(0:0:2:2) Length:{2}> R: <Node: Start:2.0 Indices:(3:3:5:5) Length:{2}> R: <Node: Start:5.0 Indices:(6:8:9:12) Length:{1}> L: <Node: Start:4.0 Indices:(6:6:8:8) Length:{2}> R: <Node: Start:6.0 Indices:(9:9:11:12) Length:{2}> R: <Node: Start:7.0 Indices:(11:11:12:12) Length:{1}>
>>> tree._rootNode.payload
[<ElementTimespan (3.0 to 4.0) <music21.note.Note F>>]
>>> tree._rootNode.leftChild.payload
[<ElementTimespan (1.0 to 2.0) <music21.note.Note D>>]
>>> for x in tree._rootNode.leftChild.rightChild.payload:
... x ... <ElementTimespan (2.0 to 3.0) <music21.note.Note E>> <ElementTimespan (2.0 to 4.0) <music21.note.Note G>>
>>> tree._rootNode.rightChild.payload
[<ElementTimespan (5.0 to 6.0) <music21.note.Note A>>]
The start offset of this node.
>>> score = stream.timespans.makeExampleScore()
>>> tree = stream.timespans.streamToTimespanCollection(score, flatten=True, classList=(note.Note, chord.Chord))
>>> print(tree._rootNode.debug())
<Node: Start:3.0 Indices:(0:5:6:12) Length:{1}>
L: <Node: Start:1.0 Indices:(0:2:3:5) Length:{1}>
L: <Node: Start:0.0 Indices:(0:0:2:2) Length:{2}>
R: <Node: Start:2.0 Indices:(3:3:5:5) Length:{2}>
R: <Node: Start:5.0 Indices:(6:8:9:12) Length:{1}>
L: <Node: Start:4.0 Indices:(6:6:8:8) Length:{2}>
R: <Node: Start:6.0 Indices:(9:9:11:12) Length:{2}>
R: <Node: Start:7.0 Indices:(11:11:12:12) Length:{1}>
>>> tree._rootNode.startOffset
3.0
>>> tree._rootNode.leftChild.startOffset
1.0
>>> tree._rootNode.rightChild.startOffset
5.0
The highest stop offset of any timespan in any node nof the subtree rooted on this node.
The lowest stop offset of any timespan in any node of the subtree rooted on this node.
The lowest timespan start index of any timespan in any node of the subtree rooted on this node.
The highest timespan stop index of any timespan in any node of the subtree rooted on this node.