music21.timespans.core¶
These are the lowest level tools for working with self-balancing AVL trees.
There’s an overhead to creating an AVL tree, but for a large score it is absolutely balanced by having O(log n) search times.
AVLNode¶
-
class
music21.timespans.core.
AVLNode
(position, payload=None)¶ An AVL Tree Node, not specialized in any way, just contains positions.
>>> position = 1.0 >>> node = timespans.core.AVLNode(position) >>> node <Node: Start:1.0 Height:0 L:None R:None> >>> n2 = timespans.core.AVLNode(2.0) >>> node.rightChild = n2 >>> node.update() >>> node <Node: Start:1.0 Height:1 L:None R:0>
Nodes can rebalance themselves, but they work best in a Tree...
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.
AVLNode
bases
AVLNode
methods
-
AVLNode.
debug
()¶ Get a debug of the Node:
>>> score = timespans.makeExampleScore() >>> tree = timespans.streamToTimespanTree(score, flatten=True, ... classList=(note.Note, chord.Chord)) >>> rn = tree.rootNode >>> 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}>
-
AVLNode.
moveAttributes
(other)¶ move attributes from this node to another in case “removal” actually means substituting one node for another in the tree.
Subclass this in derived classes
Do not copy anything about height, balance, left or right children, etc. By default just moves position and payload.
-
AVLNode.
rebalance
()¶ Rebalances the subtree rooted on this node.
Returns the new central node.
-
AVLNode.
rotateLeftLeft
()¶ Rotates a node left twice.
Used during tree rebalancing.
Returns a node, the new central node.
-
AVLNode.
rotateLeftRight
()¶ Rotates a node right twice.
Used during tree rebalancing.
Returns a node, the new central node.
-
AVLNode.
rotateRightLeft
()¶ Rotates a node right, then left.
Used during tree rebalancing.
Returns a node, the new central node.
-
AVLNode.
rotateRightRight
()¶ Rotates a node left, then right.
Used during tree rebalancing.
Returns a node, the new central node.
-
AVLNode.
update
()¶ Updates the height and balance attributes of the nodes.
Must be called whenever .leftChild or .rightChild are changed.
Used for the next balancing operation – does not rebalance itself
Returns None
AVLNode
instance variables
-
AVLNode.
balance
¶ Returns the current state of the difference in heights of the two subtrees rooted on this node.
This attribute is used to help balance the AVL tree.
>>> score = timespans.makeExampleScore() >>> tree = timespans.streamToTimespanTree(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
You should never see a balance other than 1, -1, or 0. If you do then something has gone wrong.
-
AVLNode.
height
¶ The height of the subtree rooted on this node.
This property is used to help balance the AVL tree.
>>> score = timespans.makeExampleScore() >>> tree = timespans.streamToTimespanTree(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
Once you hit a height of zero, then the next child on either size should be None
>>> print(tree.rootNode.rightChild.rightChild.rightChild.rightChild) None
-
AVLNode.
leftChild
¶ The left child of this node.
After setting the left child you need to do a node update. with node.update()
>>> score = timespans.makeExampleScore() >>> tree = timespans.streamToTimespanTree(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}>
-
AVLNode.
position
¶ The position of this node.
>>> score = timespans.makeExampleScore() >>> tree = timespans.streamToTimespanTree(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.position 3.0
>>> tree.rootNode.leftChild.position 1.0
>>> tree.rootNode.rightChild.position 5.0
-
AVLNode.
rightChild
¶ The right child of this node.
After setting the right child you need to do a node update. with node.update()
>>> score = timespans.makeExampleScore() >>> tree = timespans.streamToTimespanTree(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}>
AVLTree¶
-
class
music21.timespans.core.
AVLTree
¶ Data structure for working with timespans.node.AVLNode objects.
To be subclassed in order to do anything useful with music21 objects.
AVLTree
methods
-
AVLTree.
debug
()¶ Gets string representation of the timespan collection.
Useful only for debugging its internal node structure.
>>> tsList = [(0,2), (0,9), (1,1), (2,3), (3,4), (4,9), (5,6), (5,8), (6,8), (7,7)] >>> tss = [timespans.spans.Timespan(x, y) for x, y in tsList] >>> tree = timespans.trees.TimespanTree() >>> tree.insert(tss)
>>> print(tree.debug()) <Node: Start:3.0 Indices:(0:4:5:10) Length:{1}> L: <Node: Start:1.0 Indices:(0:2:3:4) Length:{1}> L: <Node: Start:0.0 Indices:(0:0:2:2) Length:{2}> R: <Node: Start:2.0 Indices:(3:3:4:4) Length:{1}> R: <Node: Start:5.0 Indices:(5:6:8:10) Length:{2}> L: <Node: Start:4.0 Indices:(5:5:6:6) Length:{1}> R: <Node: Start:6.0 Indices:(8:8:9:10) Length:{1}> R: <Node: Start:7.0 Indices:(9:9:10:10) Length:{1}>
-
AVLTree.
getNodeAfter
(position)¶ Gets the first node after position.
>>> score = corpus.parse('bwv66.6') >>> tree = score.asTimespans() >>> n1 = tree.getNodeAfter(0.5) >>> n1 <Node: Start:1.0 Indices:(7:7:11:11) Length:{4}> >>> n2 = tree.getNodeAfter(0.6) >>> n2 is n1 True
-
AVLTree.
getNodeBefore
(position)¶ Finds the node immediately before position.
>>> score = corpus.parse('bwv66.6') >>> tree = score.asTimespans() >>> tree.getNodeBefore(100) # last node in piece <Node: Start:35.0 Indices:(161:161:165:165) Length:{4}>
-
AVLTree.
getNodeByPosition
(position)¶ Searches for a node whose position is position in the subtree rooted on node.
Used internally by TimespanTree.
Returns a Node object or None
-
AVLTree.
getPositionAfter
(position)¶ Gets start position after position.
>>> score = corpus.parse('bwv66.6') >>> tree = score.asTimespans() >>> tree.getPositionAfter(0.5) 1.0
Returns None if no succeeding position exists.
>>> tree.getPositionAfter(35) is None True
Generally speaking, negative positions will usually return 0.0
>>> tree.getPositionAfter(-999) 0.0
-
AVLTree.
getPositionBefore
(position)¶ Gets the start position immediately preceding position in this position-tree.
>>> score = corpus.parse('bwv66.6') >>> tree = score.asTimespans() >>> tree.getPositionBefore(100) 35.0
Return None if no preceding position exists.
>>> tree.getPositionBefore(0) is None True
-
AVLTree.
insertAtPosition
(position)¶ creates a new node at position and sets the rootNode appropriately
>>> avl = timespans.core.AVLTree() >>> avl.insertAtPosition(20) >>> avl.rootNode <Node: Start:20 Height:0 L:None R:None>
>>> avl.insertAtPosition(10) >>> avl.rootNode <Node: Start:20 Height:1 L:0 R:None>
>>> avl.insertAtPosition(5) >>> avl.rootNode <Node: Start:10 Height:1 L:0 R:0>
>>> avl.insertAtPosition(30) >>> avl.rootNode <Node: Start:10 Height:2 L:0 R:1> >>> avl.rootNode.leftChild <Node: Start:5 Height:0 L:None R:None> >>> avl.rootNode.rightChild <Node: Start:20 Height:1 L:None R:0>
>>> avl.rootNode.rightChild.rightChild <Node: Start:30 Height:0 L:None R:None>
-
AVLTree.
removeNode
(position)¶ Removes a node at position in the subtree rooted on node.
Used internally by TimespanTree.
>>> avl = timespans.core.AVLTree() >>> avl.insertAtPosition(20) >>> avl.insertAtPosition(10) >>> avl.insertAtPosition(5) >>> avl.insertAtPosition(30) >>> avl.rootNode <Node: Start:10 Height:2 L:0 R:1>
Remove node at 30
>>> avl.removeNode(30) >>> avl.rootNode <Node: Start:10 Height:1 L:0 R:0>
Removing a node eliminates its payload:
>>> ten = avl.getNodeByPosition(10) >>> ten.payload = 'ten' >>> twenty = avl.getNodeByPosition(20) >>> twenty.payload = 'twenty'
>>> avl.removeNode(10) >>> avl.rootNode <Node: Start:20 Height:1 L:0 R:None> >>> avl.rootNode.payload 'twenty'
Removing a non-existent node does nothing.
>>> avl.removeNode(9.5) >>> avl.rootNode <Node: Start:20 Height:1 L:0 R:None>
>>> for n in avl: ... print(n, n.payload) <Node: Start:5 Height:0 L:None R:None> None <Node: Start:20 Height:1 L:0 R:None> twenty