1# -*- coding: utf-8 -*- 2# ----------------------------------------------------------------------------- 3# Name: tree/core.py 4# Purpose: Core AVLTree object. To be optimized the hell out of. 5# 6# Authors: Josiah Wolf Oberholtzer 7# Michael Scott Cuthbert 8# 9# Copyright: Copyright © 2013-16 Michael Scott Cuthbert and the music21 10# Project 11# License: BSD, see license.txt 12# ----------------------------------------------------------------------------- 13''' 14These are the lowest level tools for working with self-balancing AVL trees. 15 16There's an overhead to creating an AVL tree, but for a large score it is 17absolutely balanced by having O(log n) search times. 18''' 19from typing import Optional 20 21from music21.exceptions21 import TreeException 22from music21 import common 23 24# ----------------------------------------------------------------------------- 25 26 27class AVLNode(common.SlottedObjectMixin): 28 r''' 29 An AVL Tree Node, not specialized in any way, just contains positions. 30 31 >>> position = 1.0 32 >>> node = tree.core.AVLNode(position) 33 >>> node 34 <AVLNode: Start:1.0 Height:0 L:None R:None> 35 >>> n2 = tree.core.AVLNode(2.0) 36 >>> node.rightChild = n2 37 >>> node.update() 38 >>> node 39 <AVLNode: Start:1.0 Height:1 L:None R:0> 40 41 Nodes can rebalance themselves, but they work best in a Tree... 42 43 Please consult the Wikipedia entry on AVL trees 44 (https://en.wikipedia.org/wiki/AVL_tree) for a very detailed 45 description of how this data structure works. 46 ''' 47 48 # CLASS VARIABLES # 49 50 __slots__ = ( 51 '__weakref__', 52 'balance', 53 'height', 54 'position', 55 'payload', 56 57 'leftChild', 58 'rightChild', 59 ) 60 61 _DOC_ATTR = { 62 'balance': ''' 63 Returns the current state of the difference in heights of the 64 two subtrees rooted on this node. 65 66 This attribute is used to help balance the AVL tree. 67 68 >>> score = tree.makeExampleScore() 69 >>> scoreTree = tree.fromStream.asTimespans(score, flatten=True, 70 ... classList=(note.Note, chord.Chord)) 71 >>> print(scoreTree.debug()) 72 <OffsetNode 3.0 Indices:0,5,6,12 Length:1> 73 L: <OffsetNode 1.0 Indices:0,2,3,5 Length:1> 74 L: <OffsetNode 0.0 Indices:0,0,2,2 Length:2> 75 R: <OffsetNode 2.0 Indices:3,3,5,5 Length:2> 76 R: <OffsetNode 5.0 Indices:6,8,9,12 Length:1> 77 L: <OffsetNode 4.0 Indices:6,6,8,8 Length:2> 78 R: <OffsetNode 6.0 Indices:9,9,11,12 Length:2> 79 R: <OffsetNode 7.0 Indices:11,11,12,12 Length:1> 80 81 82 This tree has one more depth on the right than on the left 83 84 >>> scoreTree.rootNode.balance 85 1 86 87 88 The leftChild of the rootNote is perfectly balanced, while the rightChild is off by 89 one (acceptable). 90 91 >>> scoreTree.rootNode.leftChild.balance 92 0 93 >>> scoreTree.rootNode.rightChild.balance 94 1 95 96 97 The rightChild's children are also (acceptably) unbalanced: 98 99 >>> scoreTree.rootNode.rightChild.leftChild.balance 100 0 101 >>> scoreTree.rootNode.rightChild.rightChild.balance 102 1 103 104 You should never see a balance other than 1, -1, or 0. If you do then 105 something has gone wrong. 106 ''', 107 108 109 'height': r''' 110 The height of the subtree rooted on this node. 111 112 This property is used to help balance the AVL tree. 113 114 >>> score = tree.makeExampleScore() 115 >>> scoreTree = tree.fromStream.asTimespans(score, flatten=True, 116 ... classList=(note.Note, chord.Chord)) 117 >>> print(scoreTree.debug()) 118 <OffsetNode 3.0 Indices:0,5,6,12 Length:1> 119 L: <OffsetNode 1.0 Indices:0,2,3,5 Length:1> 120 L: <OffsetNode 0.0 Indices:0,0,2,2 Length:2> 121 R: <OffsetNode 2.0 Indices:3,3,5,5 Length:2> 122 R: <OffsetNode 5.0 Indices:6,8,9,12 Length:1> 123 L: <OffsetNode 4.0 Indices:6,6,8,8 Length:2> 124 R: <OffsetNode 6.0 Indices:9,9,11,12 Length:2> 125 R: <OffsetNode 7.0 Indices:11,11,12,12 Length:1> 126 127 >>> scoreTree.rootNode.height 128 3 129 130 >>> scoreTree.rootNode.rightChild.height 131 2 132 133 >>> scoreTree.rootNode.rightChild.rightChild.height 134 1 135 136 >>> scoreTree.rootNode.rightChild.rightChild.rightChild.height 137 0 138 139 Once you hit a height of zero, then the next child on either size should be None 140 141 >>> print(scoreTree.rootNode.rightChild.rightChild.rightChild.rightChild) 142 None 143 ''', 144 'payload': r''' 145 The content of the node at this point. Usually a Music21Object. 146 ''', 147 148 'position': r''' 149 The position of this node -- this is often the same as the offset of 150 the node in a containing score, but does not need to be. It could be the .sortTuple 151 152 >>> score = tree.makeExampleScore() 153 >>> scoreTree = tree.fromStream.asTimespans(score, flatten=True, 154 ... classList=(note.Note, chord.Chord)) 155 >>> print(scoreTree.rootNode.debug()) 156 <OffsetNode 3.0 Indices:0,5,6,12 Length:1> 157 L: <OffsetNode 1.0 Indices:0,2,3,5 Length:1> 158 L: <OffsetNode 0.0 Indices:0,0,2,2 Length:2> 159 R: <OffsetNode 2.0 Indices:3,3,5,5 Length:2> 160 R: <OffsetNode 5.0 Indices:6,8,9,12 Length:1> 161 L: <OffsetNode 4.0 Indices:6,6,8,8 Length:2> 162 R: <OffsetNode 6.0 Indices:9,9,11,12 Length:2> 163 R: <OffsetNode 7.0 Indices:11,11,12,12 Length:1> 164 165 >>> scoreTree.rootNode.position 166 3.0 167 168 >>> scoreTree.rootNode.leftChild.position 169 1.0 170 171 >>> scoreTree.rootNode.rightChild.position 172 5.0 173 ''', 174 'leftChild': r''' 175 The left child of this node. 176 177 After setting the left child you need to do a node update. with node.update() 178 179 >>> score = tree.makeExampleScore() 180 >>> scoreTree = tree.fromStream.asTimespans(score, flatten=True, 181 ... classList=(note.Note, chord.Chord)) 182 >>> print(scoreTree.rootNode.debug()) 183 <OffsetNode 3.0 Indices:0,5,6,12 Length:1> 184 L: <OffsetNode 1.0 Indices:0,2,3,5 Length:1> 185 L: <OffsetNode 0.0 Indices:0,0,2,2 Length:2> 186 R: <OffsetNode 2.0 Indices:3,3,5,5 Length:2> 187 R: <OffsetNode 5.0 Indices:6,8,9,12 Length:1> 188 L: <OffsetNode 4.0 Indices:6,6,8,8 Length:2> 189 R: <OffsetNode 6.0 Indices:9,9,11,12 Length:2> 190 R: <OffsetNode 7.0 Indices:11,11,12,12 Length:1> 191 192 >>> print(scoreTree.rootNode.leftChild.debug()) 193 <OffsetNode 1.0 Indices:0,2,3,5 Length:1> 194 L: <OffsetNode 0.0 Indices:0,0,2,2 Length:2> 195 R: <OffsetNode 2.0 Indices:3,3,5,5 Length:2> 196 ''', 197 'rightChild': r''' 198 The right child of this node. 199 200 After setting the right child you need to do a node update. with node.update() 201 202 >>> score = tree.makeExampleScore() 203 >>> scoreTree = tree.fromStream.asTimespans(score, flatten=True, 204 ... classList=(note.Note, chord.Chord)) 205 >>> print(scoreTree.rootNode.debug()) 206 <OffsetNode 3.0 Indices:0,5,6,12 Length:1> 207 L: <OffsetNode 1.0 Indices:0,2,3,5 Length:1> 208 L: <OffsetNode 0.0 Indices:0,0,2,2 Length:2> 209 R: <OffsetNode 2.0 Indices:3,3,5,5 Length:2> 210 R: <OffsetNode 5.0 Indices:6,8,9,12 Length:1> 211 L: <OffsetNode 4.0 Indices:6,6,8,8 Length:2> 212 R: <OffsetNode 6.0 Indices:9,9,11,12 Length:2> 213 R: <OffsetNode 7.0 Indices:11,11,12,12 Length:1> 214 215 >>> print(scoreTree.rootNode.rightChild.debug()) 216 <OffsetNode 5.0 Indices:6,8,9,12 Length:1> 217 L: <OffsetNode 4.0 Indices:6,6,8,8 Length:2> 218 R: <OffsetNode 6.0 Indices:9,9,11,12 Length:2> 219 R: <OffsetNode 7.0 Indices:11,11,12,12 Length:1> 220 221 >>> print(scoreTree.rootNode.rightChild.rightChild.debug()) 222 <OffsetNode 6.0 Indices:9,9,11,12 Length:2> 223 R: <OffsetNode 7.0 Indices:11,11,12,12 Length:1> 224 225 >>> print(scoreTree.rootNode.rightChild.rightChild.rightChild.debug()) 226 <OffsetNode 7.0 Indices:11,11,12,12 Length:1> 227 ''' 228 229 } 230 231 # INITIALIZER # 232 233 def __init__(self, position, payload=None): 234 self.position = position 235 self.payload = payload 236 237 self.balance = 0 238 self.height = 0 239 240 self.leftChild = None 241 self.rightChild = None 242 243 # SPECIAL METHODS # 244 245 def __repr__(self): 246 lcHeight = None 247 if self.leftChild: 248 lcHeight = self.leftChild.height 249 rcHeight = None 250 if self.rightChild: 251 rcHeight = self.rightChild.height 252 253 return '<{}: Start:{} Height:{} L:{} R:{}>'.format( 254 self.__class__.__name__, 255 self.position, 256 self.height, 257 lcHeight, 258 rcHeight 259 ) 260 261 # PRIVATE METHODS # 262 def moveAttributes(self, other): 263 ''' 264 move attributes from this node to another in case "removal" actually 265 means substituting one node for another in the tree. 266 267 Subclass this in derived classes 268 269 Do not copy anything about height, balance, left or right 270 children, etc. By default just moves position and payload. 271 ''' 272 other.position = self.position 273 other.payload = self.payload 274 275 def debug(self): 276 ''' 277 Get a debug of the Node: 278 279 >>> score = tree.makeExampleScore() 280 >>> scoreTree = tree.fromStream.asTimespans(score, flatten=True, 281 ... classList=(note.Note, chord.Chord)) 282 >>> rn = scoreTree.rootNode 283 >>> print(rn.debug()) 284 <OffsetNode 3.0 Indices:0,5,6,12 Length:1> 285 L: <OffsetNode 1.0 Indices:0,2,3,5 Length:1> 286 L: <OffsetNode 0.0 Indices:0,0,2,2 Length:2> 287 R: <OffsetNode 2.0 Indices:3,3,5,5 Length:2> 288 R: <OffsetNode 5.0 Indices:6,8,9,12 Length:1> 289 L: <OffsetNode 4.0 Indices:6,6,8,8 Length:2> 290 R: <OffsetNode 6.0 Indices:9,9,11,12 Length:2> 291 R: <OffsetNode 7.0 Indices:11,11,12,12 Length:1> 292 ''' 293 return '\n'.join(self._getDebugPieces()) 294 295 def _getDebugPieces(self): 296 r''' 297 Return a list of the debugging information of the tree (used for debug): 298 299 Called recursively 300 301 >>> score = tree.makeExampleScore() 302 >>> scoreTree = tree.fromStream.asTimespans(score, flatten=True, 303 ... classList=(note.Note, chord.Chord)) 304 >>> rn = scoreTree.rootNode 305 >>> rn._getDebugPieces() 306 ['<OffsetNode 3.0 Indices:0,5,6,12 Length:1>', 307 '\tL: <OffsetNode 1.0 Indices:0,2,3,5 Length:1>', 308 '\t\tL: <OffsetNode 0.0 Indices:0,0,2,2 Length:2>', 309 '\t\tR: <OffsetNode 2.0 Indices:3,3,5,5 Length:2>', 310 '\tR: <OffsetNode 5.0 Indices:6,8,9,12 Length:1>', 311 '\t\tL: <OffsetNode 4.0 Indices:6,6,8,8 Length:2>', 312 '\t\tR: <OffsetNode 6.0 Indices:9,9,11,12 Length:2>', 313 '\t\t\tR: <OffsetNode 7.0 Indices:11,11,12,12 Length:1>'] 314 ''' 315 result = [] 316 result.append(repr(self)) 317 if self.leftChild: 318 subResult = self.leftChild._getDebugPieces() 319 result.append(f'\tL: {subResult[0]}') 320 result.extend('\t' + x for x in subResult[1:]) 321 if self.rightChild: 322 subResult = self.rightChild._getDebugPieces() 323 result.append(f'\tR: {subResult[0]}') 324 result.extend('\t' + x for x in subResult[1:]) 325 return result 326 327 def update(self): 328 ''' 329 Updates the height and balance attributes of the nodes. 330 331 Must be called whenever .leftChild or .rightChild are changed. 332 333 Used for the next balancing operation -- does not rebalance itself. 334 335 Note that it only looks at its children's height and balance attributes 336 not their children's. So if they are wrong, this will be too. 337 338 Returns None 339 340 We create a score with everything correct. 341 342 >>> score = tree.makeExampleScore() 343 >>> scoreTree = tree.fromStream.asTimespans(score, flatten=True, 344 ... classList=(note.Note, chord.Chord)) 345 >>> n = scoreTree.rootNode 346 >>> n 347 <OffsetNode 3.0 Indices:0,5,6,12 Length:1> 348 >>> n.height, n.balance 349 (3, 1) 350 351 Now let's screw up the height and balance 352 353 >>> n.height = 100 354 >>> n.balance = -2 355 >>> n.height, n.balance 356 (100, -2) 357 358 But we can fix it with `.update()` 359 360 >>> n.update() 361 >>> n.height, n.balance 362 (3, 1) 363 364 Note that if we were to screw up the balance/height of one of the 365 child notes of `n` then this would not fix that node's balance/height. 366 This method assumes that children have the correct information and only 367 updates the information for this node. 368 369 ''' 370 if self.leftChild is not None: 371 leftHeight = self.leftChild.height 372 else: 373 leftHeight = -1 374 375 if self.rightChild is not None: 376 rightHeight = self.rightChild.height 377 else: 378 rightHeight = -1 379 380 self.height = max(leftHeight, rightHeight) + 1 381 self.balance = rightHeight - leftHeight 382 383 def rotateLeftLeft(self): 384 r''' 385 Rotates a node left twice. 386 387 Makes this node the rightChild of 388 the former leftChild and makes the former leftChild's rightChild 389 be the leftChild of this node. 390 391 Used during tree rebalancing. 392 393 Returns the prior leftChild node as the new central node. 394 ''' 395 nextNode = self.leftChild 396 self.leftChild = nextNode.rightChild 397 self.update() 398 nextNode.rightChild = self 399 nextNode.update() 400 401 return nextNode 402 403 def rotateLeftRight(self): 404 r''' 405 Rotates a node left, then right. 406 407 Makes this note the rightChild of the former rightChild of the former leftChild node 408 409 Used during tree rebalancing. 410 411 Returns the former rightChild of the former leftChild node as the new central node. 412 ''' 413 self.leftChild = self.leftChild.rotateRightRight() 414 self.update() 415 nextNode = self.rotateLeftLeft() 416 return nextNode 417 418 def rotateRightLeft(self): 419 r''' 420 Rotates a node right, then left. 421 422 Makes this note the leftChild of the former leftChild of the former rightChild node 423 424 Used during tree rebalancing. 425 426 Returns the former leftChild of the former rightChild node as the new central node. 427 ''' 428 self.rightChild = self.rightChild.rotateLeftLeft() 429 self.update() 430 nextNode = self.rotateRightRight() 431 return nextNode 432 433 def rotateRightRight(self): 434 r''' 435 Rotates a node right twice. 436 437 Makes this node the leftChild of 438 the former rightChild and makes the former rightChild's leftChild 439 be the rightChild of this node. 440 441 Used during tree rebalancing. 442 443 Returns the prior rightChild node as the new central node. 444 ''' 445 nextNode = self.rightChild 446 self.rightChild = nextNode.leftChild 447 self.update() 448 nextNode.leftChild = self 449 nextNode.update() 450 return nextNode 451 452 def rebalance(self): 453 r''' 454 Rebalances the subtree rooted on this node. 455 456 Returns the new central node. 457 ''' 458 node = self 459 if node.balance > 1: 460 if node.rightChild.balance >= 0: 461 node = node.rotateRightRight() 462 else: 463 node = node.rotateRightLeft() 464 elif node.balance < -1: 465 if node.leftChild.balance <= 0: 466 node = node.rotateLeftLeft() 467 else: 468 node = node.rotateLeftRight() 469 if node.balance < -1 or node.balance > 1: 470 raise TreeException( 471 'Somehow Nodes are still not balanced. node.balance %r must be between -1 and 1') 472 473 return node 474 475 476# --------------------------------------------------------------------------- 477 478class AVLTree: 479 r''' 480 Data structure for working with tree.node.AVLNode objects. 481 482 To be subclassed in order to do anything useful with music21 objects. 483 ''' 484 __slots__ = ( 485 '__weakref__', 486 'rootNode', 487 ) 488 nodeClass = AVLNode 489 490 def __init__(self): 491 self.rootNode = None 492 493 def __iter__(self): 494 r''' 495 Iterates through all the nodes in the position tree in left to right order. 496 497 Note that this runs in O(n log n) time in Python, while iterating through 498 a list runs in O(n) time in C, so this isn't something to do on real datasets. 499 500 >>> nodePositions = [0, 2, 4, 6, 8, 10, 12] 501 >>> avl = tree.core.AVLTree() 502 >>> for np in nodePositions: 503 ... avl.createNodeAtPosition(np) 504 >>> for x in avl: 505 ... x 506 <AVLNode: Start:0 Height:0 L:None R:None> 507 <AVLNode: Start:2 Height:1 L:0 R:0> 508 <AVLNode: Start:4 Height:0 L:None R:None> 509 <AVLNode: Start:6 Height:2 L:1 R:1> 510 <AVLNode: Start:8 Height:0 L:None R:None> 511 <AVLNode: Start:10 Height:1 L:0 R:0> 512 <AVLNode: Start:12 Height:0 L:None R:None> 513 514 Note: for this example to be stable, we can't shuffle the nodes, since there are 515 numerous different possible configurations that meet the AVLTree constraints, some 516 of height 2 and some of height 3 517 ''' 518 def recurse(node): 519 if node is not None: 520 if node.leftChild is not None: 521 for n in recurse(node.leftChild): 522 yield n 523 yield node 524 if node.rightChild is not None: 525 for n in recurse(node.rightChild): 526 yield n 527 return recurse(self.rootNode) 528 529 def populateFromSortedList(self, listOfTuples): 530 ''' 531 Populate this tree from a sorted list of two-tuples of (position, payload). 532 533 This is about an order of magnitude faster (3ms vs 21ms for 1000 items; 534 31 vs. 300ms for 10,000 items) than running createNodeAtPosition() 535 for each element in a list if it is 536 already sorted. Thus it should be used when converting a 537 Stream where .isSorted is True into a tree. 538 539 This method assumes that the current tree is empty (or will be wiped) and 540 that listOfTuples is a non-empty 541 list where the first element is a unique position to insert, 542 and the second is the complete payload for that node, and 543 that the positions are strictly increasing in order. 544 545 If any of the conditions is not true, expect to get a dangerously 546 badly sorted tree that will be useless. 547 548 >>> listOfTuples = [(i, str(i)) for i in range(1000)] 549 >>> listOfTuples[10] 550 (10, '10') 551 >>> t = tree.core.AVLTree() 552 >>> t.rootNode is None 553 True 554 >>> t.populateFromSortedList(listOfTuples) 555 >>> t.rootNode 556 <AVLNode: Start:500 Height:9 L:8 R:8> 557 558 >>> n = t.rootNode 559 >>> while n is not None: 560 ... print(n, repr(n.payload)) 561 ... n = n.leftChild 562 <AVLNode: Start:500 Height:9 L:8 R:8> '500' 563 <AVLNode: Start:250 Height:8 L:7 R:7> '250' 564 <AVLNode: Start:125 Height:7 L:6 R:6> '125' 565 <AVLNode: Start:62 Height:6 L:5 R:5> '62' 566 <AVLNode: Start:31 Height:5 L:4 R:4> '31' 567 <AVLNode: Start:15 Height:4 L:3 R:3> '15' 568 <AVLNode: Start:7 Height:3 L:2 R:2> '7' 569 <AVLNode: Start:3 Height:2 L:1 R:1> '3' 570 <AVLNode: Start:1 Height:1 L:0 R:0> '1' 571 <AVLNode: Start:0 Height:0 L:None R:None> '0' 572 ''' 573 def recurse(subListOfTuples) -> Optional[AVLNode]: 574 ''' 575 Divide and conquer. 576 ''' 577 if not subListOfTuples: 578 return None 579 midpoint = len(subListOfTuples) // 2 580 midtuple = subListOfTuples[midpoint] 581 n = NodeClass(midtuple[0], midtuple[1]) 582 n.leftChild = recurse(subListOfTuples[:midpoint]) 583 n.rightChild = recurse(subListOfTuples[midpoint + 1:]) 584 n.update() 585 return n 586 587 NodeClass = self.nodeClass 588 self.rootNode = recurse(listOfTuples) 589 590 def createNodeAtPosition(self, position): 591 ''' 592 creates a new node at position and sets the rootNode 593 appropriately 594 595 >>> avl = tree.core.AVLTree() 596 >>> avl.createNodeAtPosition(20) 597 >>> avl.rootNode 598 <AVLNode: Start:20 Height:0 L:None R:None> 599 600 >>> avl.createNodeAtPosition(10) 601 >>> avl.rootNode 602 <AVLNode: Start:20 Height:1 L:0 R:None> 603 604 >>> avl.createNodeAtPosition(5) 605 >>> avl.rootNode 606 <AVLNode: Start:10 Height:1 L:0 R:0> 607 608 >>> avl.createNodeAtPosition(30) 609 >>> avl.rootNode 610 <AVLNode: Start:10 Height:2 L:0 R:1> 611 >>> avl.rootNode.leftChild 612 <AVLNode: Start:5 Height:0 L:None R:None> 613 >>> avl.rootNode.rightChild 614 <AVLNode: Start:20 Height:1 L:None R:0> 615 616 >>> avl.rootNode.rightChild.rightChild 617 <AVLNode: Start:30 Height:0 L:None R:None> 618 ''' 619 def recurse(node, innerPosition): 620 ''' 621 this recursively finds the right place for the new node 622 and either creates a new node (if it is in the right place) 623 or rebalances the nodes above it and tells those nodes how 624 to set their new roots. 625 ''' 626 if node is None: 627 # if we get to the point where a node does not have a 628 # left or right child, make a new node at this position... 629 return self.nodeClass(innerPosition) 630 631 if innerPosition < node.position: 632 node.leftChild = recurse(node.leftChild, innerPosition) 633 node.update() 634 elif node.position < innerPosition: 635 node.rightChild = recurse(node.rightChild, innerPosition) 636 node.update() 637 if node is not None: 638 return node.rebalance() 639 640 self.rootNode = recurse(self.rootNode, position) 641 642 def debug(self): 643 r''' 644 Gets string representation of the node tree. 645 646 Useful only for debugging its internal node structure. 647 648 >>> tsList = [(0, 2), (0, 9), (1, 1), (2, 3), (3, 4), 649 ... (4, 9), (5, 6), (5, 8), (6, 8), (7, 7)] 650 >>> tss = [tree.spans.Timespan(x, y) for x, y in tsList] 651 >>> tsTree = tree.timespanTree.TimespanTree() 652 >>> tsTree.insert(tss) 653 654 >>> print(tsTree.debug()) 655 <OffsetNode 3.0 Indices:0,4,5,10 Length:1> 656 L: <OffsetNode 1.0 Indices:0,2,3,4 Length:1> 657 L: <OffsetNode 0.0 Indices:0,0,2,2 Length:2> 658 R: <OffsetNode 2.0 Indices:3,3,4,4 Length:1> 659 R: <OffsetNode 5.0 Indices:5,6,8,10 Length:2> 660 L: <OffsetNode 4.0 Indices:5,5,6,6 Length:1> 661 R: <OffsetNode 6.0 Indices:8,8,9,10 Length:1> 662 R: <OffsetNode 7.0 Indices:9,9,10,10 Length:1> 663 ''' 664 if self.rootNode is not None: 665 return self.rootNode.debug() 666 return '' 667 668 def getNodeByPosition(self, position): 669 r''' 670 Searches for a node whose position is `position` in the subtree 671 rooted on `node`. 672 673 Returns a Node object or None 674 ''' 675 def recurse(innerPosition, node): 676 if node is not None: 677 if node.position == innerPosition: 678 return node 679 elif node.leftChild and innerPosition < node.position: 680 return recurse(innerPosition, node.leftChild) 681 elif node.rightChild and node.position < innerPosition: 682 return recurse(innerPosition, node.rightChild) 683 return None 684 685 return recurse(position, self.rootNode) 686 687 def getNodeAfter(self, position): 688 r''' 689 Gets the first node after `position`. 690 691 >>> score = corpus.parse('bwv66.6') 692 >>> scoreTree = score.asTree(flatten=True) 693 >>> node1 = scoreTree.getNodeAfter(0.5) 694 >>> node1 695 <ElementNode: Start:1.0 <0.20...> Indices:(l:0 *25* r:61) Payload:<music21.note.Note A>> 696 >>> node2 = scoreTree.getNodeAfter(0.6) 697 >>> node2 is node1 698 True 699 700 >>> endNode = scoreTree.getNodeAfter(9999) 701 >>> endNode 702 <ElementNode: Start:End <0.-5...> Indices:(l:188 *191* r:195) 703 Payload:<music21.bar.Barline type=final>> 704 705 >>> while endNode is not None: 706 ... print(endNode) 707 ... endNodePosition = endNode.position 708 ... endNode = scoreTree.getNodeAfter(endNodePosition) 709 <ElementNode: Start:End <0.-5...> Indices:(l:188 *191* r:195) 710 Payload:<music21.bar.Barline type=final>> 711 <ElementNode: Start:End <0.-5...> Indices:(l:192 *192* r:193) 712 Payload:<music21.bar.Barline type=final>> 713 <ElementNode: Start:End <0.-5...> Indices:(l:192 *193* r:195) 714 Payload:<music21.bar.Barline type=final>> 715 <ElementNode: Start:End <0.-5...> Indices:(l:194 *194* r:195) 716 Payload:<music21.bar.Barline type=final>> 717 718 >>> note1 = score.flatten().notes[30] 719 720 Works with sortTuple positions as well... 721 722 >>> st = note1.sortTuple() 723 >>> st 724 SortTuple(atEnd=0, offset=6.0, priority=0, classSortOrder=20, isNotGrace=1, insertIndex=...) 725 726 >>> scoreTree.getNodeAfter(st) 727 <ElementNode: Start:6.5 <0.20...> Indices:(l:51 *52* r:53) 728 Payload:<music21.note.Note D>> 729 ''' 730 def recurse(node, innerPosition): 731 if node is None: 732 return None 733 inner_result = None 734 if node.position <= innerPosition and node.rightChild: 735 inner_result = recurse(node.rightChild, innerPosition) 736 elif innerPosition < node.position: 737 inner_result = recurse(node.leftChild, innerPosition) or node 738 return inner_result 739 740 result = recurse(self.rootNode, position) 741 if result is None: 742 return None 743 return result 744 745 def getPositionAfter(self, position): 746 r''' 747 Gets start position after `position`. 748 749 >>> score = corpus.parse('bwv66.6') 750 >>> scoreTree = score.asTree(flatten=True) 751 >>> scoreTree.getPositionAfter(0.5).offset 752 1.0 753 754 Returns None if no succeeding position exists. 755 756 >>> endPosition = scoreTree.getPositionAfter(9999) 757 >>> while endPosition is not None: 758 ... print(endPosition) 759 ... endPosition = scoreTree.getPositionAfter(endPosition) 760 SortTuple(atEnd=1, offset=36.0, priority=0, classSortOrder=-5, ...) 761 SortTuple(atEnd=1, offset=36.0, priority=0, classSortOrder=-5, ...) 762 SortTuple(atEnd=1, offset=36.0, priority=0, classSortOrder=-5, ...) 763 SortTuple(atEnd=1, offset=36.0, priority=0, classSortOrder=-5, ...) 764 765 Generally speaking, negative positions will usually return 0.0 766 767 >>> scoreTree.getPositionAfter(-999).offset 768 0.0 769 770 Unless the Tree is empty in which case, None is returned: 771 772 >>> at = tree.core.AVLTree() 773 >>> at.getPositionAfter(-999) is None 774 True 775 ''' 776 node = self.getNodeAfter(position) 777 if node: 778 return node.position 779 else: 780 return None 781 782 def getNodeBefore(self, position): 783 ''' 784 Finds the node immediately before position. 785 786 >>> score = corpus.parse('bwv66.6') 787 >>> scoreTree = score.asTimespans() 788 789 100 is beyond the end so it will get the last node in piece 790 791 >>> scoreTree.getNodeBefore(100) 792 <OffsetNode 36.0 Indices:191,191,195,195 Length:4> 793 794 >>> scoreTree.getNodeBefore(0) is None 795 True 796 ''' 797 def recurse(node, innerPosition): 798 if node is None: 799 return None 800 innerResult = None 801 if node.position < innerPosition: 802 innerResult = recurse(node.rightChild, innerPosition) or node 803 elif innerPosition <= node.position and node.leftChild: 804 innerResult = recurse(node.leftChild, innerPosition) 805 return innerResult 806 807 result = recurse(self.rootNode, position) 808 if result is None: 809 return None 810 return result 811 812 def getPositionBefore(self, position): 813 r''' 814 Gets the start position immediately preceding `position` in this 815 position-tree. 816 817 >>> score = corpus.parse('bwv66.6') 818 >>> scoreTree = score.asTimespans() 819 >>> scoreTree.getPositionBefore(100) 820 36.0 821 822 Return None if no preceding position exists. 823 824 >>> scoreTree.getPositionBefore(0) is None 825 True 826 ''' 827 node = self.getNodeBefore(position) 828 if node is None: 829 return None 830 return node.position 831 832 def removeNode(self, position): 833 r''' 834 Removes a node at `position` and rebalances the tree 835 836 Used internally by TimespanTree. 837 838 >>> avl = tree.core.AVLTree() 839 >>> avl.createNodeAtPosition(20) 840 >>> avl.createNodeAtPosition(10) 841 >>> avl.createNodeAtPosition(5) 842 >>> avl.createNodeAtPosition(30) 843 >>> avl.rootNode 844 <AVLNode: Start:10 Height:2 L:0 R:1> 845 846 Remove node at 30 847 848 >>> avl.removeNode(30) 849 >>> avl.rootNode 850 <AVLNode: Start:10 Height:1 L:0 R:0> 851 852 Removing a node eliminates its payload: 853 854 >>> ten = avl.getNodeByPosition(10) 855 >>> ten.payload = 'ten' 856 >>> twenty = avl.getNodeByPosition(20) 857 >>> twenty.payload = 'twenty' 858 859 >>> avl.removeNode(10) 860 >>> avl.rootNode 861 <AVLNode: Start:20 Height:1 L:0 R:None> 862 >>> avl.rootNode.payload 863 'twenty' 864 865 Removing a non-existent node does nothing. 866 867 >>> avl.removeNode(9.5) 868 >>> avl.rootNode 869 <AVLNode: Start:20 Height:1 L:0 R:None> 870 871 >>> for n in avl: 872 ... print(n, n.payload) 873 <AVLNode: Start:5 Height:0 L:None R:None> None 874 <AVLNode: Start:20 Height:1 L:0 R:None> twenty 875 ''' 876 def recurseRemove(node, innerPosition): 877 if node is not None: 878 if node.position == innerPosition: 879 # got the right node! 880 if node.leftChild and node.rightChild: 881 nextNode = node.rightChild 882 while nextNode.leftChild: # farthest left child of the right child. 883 nextNode = nextNode.leftChild 884 nextNode.moveAttributes(node) 885 node.rightChild = recurseRemove(node.rightChild, nextNode.position) 886 node.update() 887 else: 888 node = node.leftChild or node.rightChild 889 elif node.position > innerPosition: 890 node.leftChild = recurseRemove(node.leftChild, innerPosition) 891 node.update() 892 elif node.position < innerPosition: 893 node.rightChild = recurseRemove(node.rightChild, innerPosition) 894 node.update() 895 if node is not None: 896 return node.rebalance() 897 898 self.rootNode = recurseRemove(self.rootNode, position) 899 900 901# ------------------------------# 902if __name__ == '__main__': 903 import music21 904 music21.mainTest() 905