Single rotation. Assumes that balance is +-2.
(self)
| 159 | return self.drotate() |
| 160 | |
| 161 | def srotate(self): |
| 162 | """Single rotation. Assumes that balance is +-2.""" |
| 163 | # self save save |
| 164 | # save 3 -> 1 self -> 1 self.rot() |
| 165 | # 1 2 2 3 |
| 166 | # |
| 167 | # self save save |
| 168 | # 3 save -> self 1 -> self.rot() 1 |
| 169 | # 2 1 3 2 |
| 170 | |
| 171 | #assert(self.balance != 0) |
| 172 | heavy = self.balance > 0 |
| 173 | light = not heavy |
| 174 | save = self[heavy] |
| 175 | #print("srotate: bal={},{}".format(self.balance, save.balance)) |
| 176 | #self.print_structure() |
| 177 | self[heavy] = save[light] # 2 |
| 178 | #assert(save[light]) |
| 179 | save[light] = self.rotate() # Needed to ensure the 2 and 3 are balanced under new subnode |
| 180 | |
| 181 | # Some intervals may overlap both self.x_center and save.x_center |
| 182 | # Promote those to the new tip of the tree |
| 183 | promotees = [iv for iv in save[light].s_center if save.center_hit(iv)] |
| 184 | if promotees: |
| 185 | for iv in promotees: |
| 186 | save[light] = save[light].remove(iv) # may trigger pruning |
| 187 | # TODO: Use Node.add() here, to simplify future balancing improvements. |
| 188 | # For now, this is the same as augmenting save.s_center, but that may |
| 189 | # change. |
| 190 | save.s_center.update(promotees) |
| 191 | save.refresh_balance() |
| 192 | return save |
| 193 | |
| 194 | def drotate(self): |
| 195 | # First rotation |
no test coverage detected