musicdiff.comparison

   1# ------------------------------------------------------------------------------
   2# Purpose:       comparison is a music comparison package for use by musicdiff.
   3#                musicdiff is a package for comparing music scores using music21.
   4#
   5# Authors:       Greg Chapman <gregc@mac.com>
   6#                musicdiff is derived from:
   7#                   https://github.com/fosfrancesco/music-score-diff.git
   8#                   by Francesco Foscarin <foscarin.francesco@gmail.com>
   9#
  10# Copyright:     (c) 2022-2025 Francesco Foscarin, Greg Chapman
  11# License:       MIT, see LICENSE
  12# ------------------------------------------------------------------------------
  13
  14__docformat__ = "google"
  15
  16import copy
  17from collections import namedtuple
  18from difflib import ndiff
  19from pathlib import Path
  20
  21# import typing as t
  22import numpy as np
  23
  24from music21.common import OffsetQL
  25from musicdiff.annotation import AnnScore, AnnNote, AnnVoice, AnnExtra, AnnLyric
  26from musicdiff.annotation import AnnStaffGroup, AnnMetadataItem
  27from musicdiff import M21Utils
  28
  29class EvaluationMetrics:
  30    def __init__(
  31        self,
  32        gt_path: Path,
  33        pred_path: Path,
  34        gt_numsyms: int,
  35        pred_numsyms: int,
  36        omr_edit_distance: int,
  37        edit_distances_dict: dict[str, int],
  38        omr_ned: float
  39    ):
  40        self.gt_path: Path = gt_path
  41        self.pred_path: Path = pred_path
  42        self.gt_numsyms: int = gt_numsyms
  43        self.pred_numsyms: int = pred_numsyms
  44        self.omr_edit_distance: int = omr_edit_distance
  45        self.edit_distances_dict: dict[str, int] = edit_distances_dict
  46        self.omr_ned: float = omr_ned
  47
  48# memoizers to speed up the recursive computation
  49def _memoize_notes_set_distance(func):
  50    def memoizer(original, compare_to):
  51        key = repr(original) + repr(compare_to)
  52        if key not in Comparison._memoizer_mem:
  53            Comparison._memoizer_mem[key] = func(original, compare_to)
  54        return copy.deepcopy(Comparison._memoizer_mem[key])
  55
  56    return memoizer
  57
  58def _memoize_extras_set_distance(func):
  59    def memoizer(original, compare_to):
  60        key = repr(original) + repr(compare_to)
  61        if key not in Comparison._memoizer_mem:
  62            Comparison._memoizer_mem[key] = func(original, compare_to)
  63        return copy.deepcopy(Comparison._memoizer_mem[key])
  64
  65    return memoizer
  66
  67def _memoize_staff_groups_set_distance(func):
  68    def memoizer(original, compare_to):
  69        key = repr(original) + repr(compare_to)
  70        if key not in Comparison._memoizer_mem:
  71            Comparison._memoizer_mem[key] = func(original, compare_to)
  72        return copy.deepcopy(Comparison._memoizer_mem[key])
  73
  74    return memoizer
  75
  76def _memoize_metadata_items_set_distance(func):
  77    def memoizer(original, compare_to):
  78        key = repr(original) + repr(compare_to)
  79        if key not in Comparison._memoizer_mem:
  80            Comparison._memoizer_mem[key] = func(original, compare_to)
  81        return copy.deepcopy(Comparison._memoizer_mem[key])
  82
  83    return memoizer
  84
  85def _memoize_inside_bars_diff_lin(func):
  86    def memoizer(original, compare_to):
  87        key = repr(original) + repr(compare_to)
  88        if key not in Comparison._memoizer_mem:
  89            Comparison._memoizer_mem[key] = func(original, compare_to)
  90        return copy.deepcopy(Comparison._memoizer_mem[key])
  91
  92    return memoizer
  93
  94def _memoize_lyrics_diff_lin(func):
  95    def memoizer(original, compare_to):
  96        key = repr(original) + repr(compare_to)
  97        if key not in Comparison._memoizer_mem:
  98            Comparison._memoizer_mem[key] = func(original, compare_to)
  99        return copy.deepcopy(Comparison._memoizer_mem[key])
 100
 101    return memoizer
 102
 103def _memoize_block_diff_lin(func):
 104    def memoizer(original, compare_to):
 105        key = repr(original) + repr(compare_to)
 106        if key not in Comparison._memoizer_mem:
 107            Comparison._memoizer_mem[key] = func(original, compare_to)
 108        return copy.deepcopy(Comparison._memoizer_mem[key])
 109
 110    return memoizer
 111
 112def _memoize_pitches_lev_diff(func):
 113    def memoizer(original, compare_to, noteNode1, noteNode2, ids):
 114        key = (
 115            repr(original)
 116            + repr(compare_to)
 117            + repr(noteNode1)
 118            + repr(noteNode2)
 119            + repr(ids)
 120        )
 121        if key not in Comparison._memoizer_mem:
 122            Comparison._memoizer_mem[key] = func(original, compare_to, noteNode1, noteNode2, ids)
 123        return copy.deepcopy(Comparison._memoizer_mem[key])
 124
 125    return memoizer
 126
 127def _memoize_beamtuplet_lev_diff(func):
 128    def memoizer(original, compare_to, noteNode1, noteNode2, which):
 129        key = (
 130            repr(original) + repr(compare_to) + repr(noteNode1) + repr(noteNode2) + which
 131        )
 132        if key not in Comparison._memoizer_mem:
 133            Comparison._memoizer_mem[key] = func(original, compare_to, noteNode1, noteNode2, which)
 134        return copy.deepcopy(Comparison._memoizer_mem[key])
 135
 136    return memoizer
 137
 138def _memoize_generic_lev_diff(func):
 139    def memoizer(original, compare_to, noteNode1, noteNode2, which):
 140        key = (
 141            repr(original) + repr(compare_to) + repr(noteNode1) + repr(noteNode2) + which
 142        )
 143        if key not in Comparison._memoizer_mem:
 144            Comparison._memoizer_mem[key] = func(original, compare_to, noteNode1, noteNode2, which)
 145        return copy.deepcopy(Comparison._memoizer_mem[key])
 146
 147    return memoizer
 148
 149class Comparison:
 150    _memoizer_mem: dict = {}
 151
 152    @staticmethod
 153    def _clear_memoizer_caches():
 154        Comparison._memoizer_mem = {}
 155
 156    @staticmethod
 157    def _myers_diff(a_lines, b_lines):
 158        # Myers algorithm for LCS of bars (instead of the recursive algorithm in section 3.2)
 159        # This marks the farthest-right point along each diagonal in the edit
 160        # graph, along with the history that got it there
 161        Frontier = namedtuple("Frontier", ["x", "history"])
 162        frontier = {1: Frontier(0, [])}
 163
 164        a_max = len(a_lines)
 165        b_max = len(b_lines)
 166        for d in range(0, a_max + b_max + 1):
 167            for k in range(-d, d + 1, 2):
 168                # This determines whether our next search point will be going down
 169                # in the edit graph, or to the right.
 170                #
 171                # The intuition for this is that we should go down if we're on the
 172                # left edge (k == -d) to make sure that the left edge is fully
 173                # explored.
 174                #
 175                # If we aren't on the top (k != d), then only go down if going down
 176                # would take us to territory that hasn't sufficiently been explored
 177                # yet.
 178                go_down = k == -d or (k != d and frontier[k - 1].x < frontier[k + 1].x)
 179
 180                # Figure out the starting point of this iteration. The diagonal
 181                # offsets come from the geometry of the edit grid - if you're going
 182                # down, your diagonal is lower, and if you're going right, your
 183                # diagonal is higher.
 184                if go_down:
 185                    old_x, history = frontier[k + 1]
 186                    x = old_x
 187                else:
 188                    old_x, history = frontier[k - 1]
 189                    x = old_x + 1
 190
 191                # We want to avoid modifying the old history, since some other step
 192                # may decide to use it.
 193                history = history[:]
 194                y = x - k
 195
 196                # We start at the invalid point (0, 0) - we should only start building
 197                # up history when we move off of it.
 198                if 1 <= y <= b_max and go_down:
 199                    history.append((1, b_lines[y - 1][1]))  # add comparetostep
 200                elif 1 <= x <= a_max:
 201                    history.append((0, a_lines[x - 1][1]))  # add originalstep
 202
 203                # Chew up as many diagonal moves as we can - these correspond to common lines,
 204                # and they're considered "free" by the algorithm because we want to maximize
 205                # the number of these in the output.
 206                while x < a_max and y < b_max and a_lines[x][0] == b_lines[y][0]:
 207                    x += 1
 208                    y += 1
 209                    history.append((2, a_lines[x - 1][1]))  # add equal step
 210
 211                if x >= a_max and y >= b_max:
 212                    # If we're here, then we've traversed through the bottom-left corner,
 213                    # and are done.
 214                    return np.array(history)
 215
 216                frontier[k] = Frontier(x, history)
 217
 218        assert False, "Could not find edit script"
 219
 220    @staticmethod
 221    def _non_common_subsequences_myers(original, compare_to):
 222        # Both original and compare_to are list of lists, or numpy arrays with 2 columns.
 223        # This is necessary because bars need two representation at the same time.
 224        # One without the id (for comparison), and one with the id (to retrieve the bar
 225        # at the end).
 226
 227        # get the list of operations
 228        op_list = Comparison._myers_diff(
 229            np.array(original, dtype=np.int64), np.array(compare_to, dtype=np.int64)
 230        )[::-1]
 231        # retrieve the non common subsequences
 232        non_common_subsequences = []
 233        non_common_subsequences.append({"original": [], "compare_to": []})
 234        ind = 0
 235        for op in op_list[::-1]:
 236            if op[0] == 2:  # equal
 237                non_common_subsequences.append({"original": [], "compare_to": []})
 238                ind += 1
 239            elif op[0] == 0:  # original step
 240                non_common_subsequences[ind]["original"].append(op[1])
 241            elif op[0] == 1:  # compare to step
 242                non_common_subsequences[ind]["compare_to"].append(op[1])
 243        # remove the empty dict from the list
 244        non_common_subsequences = [
 245            s for s in non_common_subsequences if s != {"original": [], "compare_to": []}
 246        ]
 247        return non_common_subsequences
 248
 249    @staticmethod
 250    def _non_common_subsequences_of_measures(original_m, compare_to_m):
 251        # Take the hash for each measure to run faster comparison
 252        # We need two hashes: one that is independent of the IDs (precomputed_str, for comparison),
 253        # and one that contains the IDs (precomputed_repr, to retrieve the correct measure after
 254        # computation)
 255        original_int = [[o.precomputed_str, o.precomputed_repr] for o in original_m]
 256        compare_to_int = [[c.precomputed_str, c.precomputed_repr] for c in compare_to_m]
 257        ncs = Comparison._non_common_subsequences_myers(original_int, compare_to_int)
 258        # retrieve the original pointers to measures
 259        new_out = []
 260        for e in ncs:
 261            new_out.append({})
 262            for k in e.keys():
 263                new_out[-1][k] = []
 264                for repr_hash in e[k]:
 265                    if k == "original":
 266                        new_out[-1][k].append(
 267                            next(m for m in original_m if m.precomputed_repr == repr_hash)
 268                        )
 269                    else:
 270                        new_out[-1][k].append(
 271                            next(m for m in compare_to_m if m.precomputed_repr == repr_hash)
 272                        )
 273
 274        return new_out
 275
 276    @staticmethod
 277    @_memoize_pitches_lev_diff
 278    def _pitches_levenshtein_diff(
 279        original: list[tuple[str, str, bool]],
 280        compare_to: list[tuple[str, str, bool]],
 281        noteNode1: AnnNote,
 282        noteNode2: AnnNote,
 283        ids: tuple[int, int]
 284    ):
 285        """
 286        Compute the levenshtein distance between two sequences of pitches.
 287        Arguments:
 288            original {list} -- list of pitches
 289            compare_to {list} -- list of pitches
 290            noteNode1 {annotatedNote} --for referencing
 291            noteNode2 {annotatedNote} --for referencing
 292            ids {tuple} -- a tuple of 2 elements with the indices of the notes considered
 293        """
 294        if len(original) == 0 and len(compare_to) == 0:
 295            return [], 0
 296
 297        if len(original) == 0:
 298            op_list, cost = Comparison._pitches_levenshtein_diff(
 299                original, compare_to[1:], noteNode1, noteNode2, (ids[0], ids[1] + 1)
 300            )
 301            op_list.append(
 302                ("inspitch", noteNode1, noteNode2, M21Utils.pitch_size(compare_to[0]), ids)
 303            )
 304            cost += M21Utils.pitch_size(compare_to[0])
 305            return op_list, cost
 306
 307        if len(compare_to) == 0:
 308            op_list, cost = Comparison._pitches_levenshtein_diff(
 309                original[1:], compare_to, noteNode1, noteNode2, (ids[0] + 1, ids[1])
 310            )
 311            op_list.append(
 312                ("delpitch", noteNode1, noteNode2, M21Utils.pitch_size(original[0]), ids)
 313            )
 314            cost += M21Utils.pitch_size(original[0])
 315            return op_list, cost
 316
 317        # compute the cost and the op_list for the many possibilities of recursion
 318        cost_dict = {}
 319        op_list_dict = {}
 320        # del-pitch
 321        op_list_dict["delpitch"], cost_dict["delpitch"] = Comparison._pitches_levenshtein_diff(
 322            original[1:], compare_to, noteNode1, noteNode2, (ids[0] + 1, ids[1])
 323        )
 324        cost_dict["delpitch"] += M21Utils.pitch_size(original[0])
 325        op_list_dict["delpitch"].append(
 326            ("delpitch", noteNode1, noteNode2, M21Utils.pitch_size(original[0]), ids)
 327        )
 328        # ins-pitch
 329        op_list_dict["inspitch"], cost_dict["inspitch"] = Comparison._pitches_levenshtein_diff(
 330            original, compare_to[1:], noteNode1, noteNode2, (ids[0], ids[1] + 1)
 331        )
 332        cost_dict["inspitch"] += M21Utils.pitch_size(compare_to[0])
 333        op_list_dict["inspitch"].append(
 334            ("inspitch", noteNode1, noteNode2, M21Utils.pitch_size(compare_to[0]), ids)
 335        )
 336        # edit-pitch
 337        op_list_dict["editpitch"], cost_dict["editpitch"] = Comparison._pitches_levenshtein_diff(
 338            original[1:], compare_to[1:], noteNode1, noteNode2, (ids[0] + 1, ids[1] + 1)
 339        )
 340        if original[0] == compare_to[0]:  # to avoid perform the pitch_diff
 341            pitch_diff_op_list = []
 342            pitch_diff_cost = 0
 343        else:
 344            pitch_diff_op_list, pitch_diff_cost = Comparison._pitches_diff(
 345                original[0], compare_to[0], noteNode1, noteNode2, (ids[0], ids[1])
 346            )
 347        cost_dict["editpitch"] += pitch_diff_cost
 348        op_list_dict["editpitch"].extend(pitch_diff_op_list)
 349        # compute the minimum of the possibilities
 350        min_key = min(cost_dict, key=lambda k: cost_dict[k])
 351        out = op_list_dict[min_key], cost_dict[min_key]
 352        return out
 353
 354    @staticmethod
 355    def _pitches_diff(pitch1, pitch2, noteNode1, noteNode2, ids):
 356        """
 357        Compute the differences between two pitch (definition from the paper).
 358        a pitch consist of a tuple: pitch name (letter+number), accidental, tie.
 359        param : pitch1. The music_notation_repr tuple of note1
 360        param : pitch2. The music_notation_repr tuple of note2
 361        param : noteNode1. The noteNode where pitch1 belongs
 362        param : noteNode2. The noteNode where pitch2 belongs
 363        param : ids. (id_from_note1,id_from_note2) The indices of the notes in case of a chord
 364        Returns:
 365            [list] -- the list of differences
 366            [int] -- the cost of diff
 367        """
 368        cost = 0
 369        op_list = []
 370        # add for pitch name differences
 371        if pitch1[0] != pitch2[0]:
 372            cost += 1
 373            # TODO: select the note in a more precise way in case of a chord
 374            # rest to note
 375            if (pitch1[0][0] == "R") != (pitch2[0][0] == "R"):  # xor
 376                op_list.append(("pitchtypeedit", noteNode1, noteNode2, 1, ids))
 377            else:  # they are two notes
 378                op_list.append(("pitchnameedit", noteNode1, noteNode2, 1, ids))
 379
 380        # add for the accidentals
 381        if pitch1[1] != pitch2[1]:  # if the accidental is different
 382            if pitch1[1] == "None":
 383                assert pitch2[1] != "None"
 384                cost += 1
 385                op_list.append(("accidentins", noteNode1, noteNode2, 1, ids))
 386            elif pitch2[1] == "None":
 387                assert pitch1[1] != "None"
 388                cost += 1
 389                op_list.append(("accidentdel", noteNode1, noteNode2, 1, ids))
 390            else:  # a different type of alteration is present
 391                cost += 2  # delete then add
 392                op_list.append(("accidentedit", noteNode1, noteNode2, 2, ids))
 393        # add for the ties
 394        if pitch1[2] != pitch2[2]:
 395            # exclusive or. Add if one is tied and not the other.
 396            # probably to revise for chords
 397            cost += 1
 398            if pitch1[2]:
 399                assert not pitch2[2]
 400                op_list.append(("tiedel", noteNode1, noteNode2, 1, ids))
 401            elif pitch2[2]:
 402                assert not pitch1[2]
 403                op_list.append(("tieins", noteNode1, noteNode2, 1, ids))
 404        return op_list, cost
 405
 406    @staticmethod
 407    @_memoize_block_diff_lin
 408    def _block_diff_lin(original, compare_to):
 409        if len(original) == 0 and len(compare_to) == 0:
 410            return [], 0
 411
 412        if len(original) == 0:
 413            op_list, cost = Comparison._block_diff_lin(original, compare_to[1:])
 414            cost += compare_to[0].notation_size()
 415            op_list.append(("insbar", None, compare_to[0], compare_to[0].notation_size()))
 416            return op_list, cost
 417
 418        if len(compare_to) == 0:
 419            op_list, cost = Comparison._block_diff_lin(original[1:], compare_to)
 420            cost += original[0].notation_size()
 421            op_list.append(("delbar", original[0], None, original[0].notation_size()))
 422            return op_list, cost
 423
 424        # compute the cost and the op_list for the many possibilities of recursion
 425        cost_dict = {}
 426        op_list_dict = {}
 427        # del-bar
 428        op_list_dict["delbar"], cost_dict["delbar"] = Comparison._block_diff_lin(
 429            original[1:], compare_to
 430        )
 431        cost_dict["delbar"] += original[0].notation_size()
 432        op_list_dict["delbar"].append(
 433            ("delbar", original[0], None, original[0].notation_size())
 434        )
 435        # ins-bar
 436        op_list_dict["insbar"], cost_dict["insbar"] = Comparison._block_diff_lin(
 437            original, compare_to[1:]
 438        )
 439        cost_dict["insbar"] += compare_to[0].notation_size()
 440        op_list_dict["insbar"].append(
 441            ("insbar", None, compare_to[0], compare_to[0].notation_size())
 442        )
 443        # edit-bar
 444        op_list_dict["editbar"], cost_dict["editbar"] = Comparison._block_diff_lin(
 445            original[1:], compare_to[1:]
 446        )
 447        if (
 448            original[0] == compare_to[0]
 449        ):  # to avoid performing the _voices_coupling_recursive/_notes_set_distance
 450            # if it's not needed
 451            inside_bar_op_list = []
 452            inside_bar_cost = 0
 453        else:
 454            # diff the bar extras (like _notes_set_distance, but with lists of AnnExtras
 455            # instead of lists of AnnNotes)
 456            extras_op_list, extras_cost = Comparison._extras_set_distance(
 457                original[0].extras_list, compare_to[0].extras_list
 458            )
 459
 460            # diff the bar lyrics (with lists of AnnLyrics instead of lists of AnnExtras)
 461            lyrics_op_list, lyrics_cost = Comparison._lyrics_diff_lin(
 462                original[0].lyrics_list, compare_to[0].lyrics_list
 463            )
 464
 465            if original[0].includes_voicing:
 466                # run the voice coupling algorithm, and add to inside_bar_op_list
 467                # and inside_bar_cost
 468                inside_bar_op_list, inside_bar_cost = (
 469                    Comparison._voices_coupling_recursive(
 470                        original[0].voices_list, compare_to[0].voices_list
 471                    )
 472                )
 473            else:
 474                # run the set distance algorithm, and add to inside_bar_op_list
 475                # and inside_bar_cost
 476                inside_bar_op_list, inside_bar_cost = Comparison._notes_set_distance(
 477                    original[0].annot_notes, compare_to[0].annot_notes
 478                )
 479
 480            inside_bar_op_list.extend(extras_op_list)
 481            inside_bar_cost += extras_cost
 482            inside_bar_op_list.extend(lyrics_op_list)
 483            inside_bar_cost += lyrics_cost
 484
 485        cost_dict["editbar"] += inside_bar_cost
 486        op_list_dict["editbar"].extend(inside_bar_op_list)
 487        # compute the minimum of the possibilities
 488        min_key = min(cost_dict, key=lambda k: cost_dict[k])
 489        out = op_list_dict[min_key], cost_dict[min_key]
 490        return out
 491
 492    @staticmethod
 493    @_memoize_lyrics_diff_lin
 494    def _lyrics_diff_lin(original, compare_to):
 495        # original and compare to are two lists of AnnLyric
 496        if len(original) == 0 and len(compare_to) == 0:
 497            return [], 0
 498
 499        if len(original) == 0:
 500            cost = 0
 501            op_list, cost = Comparison._lyrics_diff_lin(original, compare_to[1:])
 502            op_list.append(("lyricins", None, compare_to[0], compare_to[0].notation_size()))
 503            cost += compare_to[0].notation_size()
 504            return op_list, cost
 505
 506        if len(compare_to) == 0:
 507            cost = 0
 508            op_list, cost = Comparison._lyrics_diff_lin(original[1:], compare_to)
 509            op_list.append(("lyricdel", original[0], None, original[0].notation_size()))
 510            cost += original[0].notation_size()
 511            return op_list, cost
 512
 513        # compute the cost and the op_list for the many possibilities of recursion
 514        cost = {}
 515        op_list = {}
 516        # lyricdel
 517        op_list["lyricdel"], cost["lyricdel"] = Comparison._lyrics_diff_lin(
 518            original[1:], compare_to
 519        )
 520        cost["lyricdel"] += original[0].notation_size()
 521        op_list["lyricdel"].append(
 522            ("lyricdel", original[0], None, original[0].notation_size())
 523        )
 524        # lyricins
 525        op_list["lyricins"], cost["lyricins"] = Comparison._lyrics_diff_lin(
 526            original, compare_to[1:]
 527        )
 528        cost["lyricins"] += compare_to[0].notation_size()
 529        op_list["lyricins"].append(
 530            ("lyricins", None, compare_to[0], compare_to[0].notation_size())
 531        )
 532        # lyricsub
 533        op_list["lyricsub"], cost["lyricsub"] = Comparison._lyrics_diff_lin(
 534            original[1:], compare_to[1:]
 535        )
 536        if (
 537            original[0] == compare_to[0]
 538        ):  # avoid call another function if they are equal
 539            lyricsub_op, lyricsub_cost = [], 0
 540        else:
 541            lyricsub_op, lyricsub_cost = (
 542                Comparison._annotated_lyric_diff(original[0], compare_to[0])
 543            )
 544        cost["lyricsub"] += lyricsub_cost
 545        op_list["lyricsub"].extend(lyricsub_op)
 546        # compute the minimum of the possibilities
 547        min_key = min(cost, key=cost.get)
 548        out = op_list[min_key], cost[min_key]
 549        return out
 550
 551    @staticmethod
 552    def _strings_levenshtein_distance(str1: str, str2: str):
 553        counter: dict = {"+": 0, "-": 0}
 554        distance: int = 0
 555        for edit_code in ndiff(str1, str2):
 556            if edit_code[0] == " ":
 557                distance += max(counter.values())
 558                counter = {"+": 0, "-": 0}
 559            else:
 560                counter[edit_code[0]] += 1
 561        distance += max(counter.values())
 562        return distance
 563
 564    @staticmethod
 565    def _areDifferentEnough(off1: OffsetQL | None, off2: OffsetQL | None) -> bool:
 566        if off1 == off2:
 567            return False
 568
 569        # this should never happen, but...
 570        if off1 is None or off2 is None:
 571            if off1 is None and off2 is not None:
 572                return True
 573            if off1 is not None and off2 is None:
 574                return True
 575            return False  # both are None, therefore not different at all
 576
 577        diff: OffsetQL = off1 - off2
 578        if diff < 0:
 579            diff = -diff
 580
 581        if diff > 0.0001:
 582            return True
 583        return False
 584
 585    @staticmethod
 586    def _annotated_extra_diff(annExtra1: AnnExtra, annExtra2: AnnExtra):
 587        """
 588        Compute the differences between two annotated extras.
 589        Each annotated extra consists of three values: content, offset, and duration
 590        """
 591        cost = 0
 592        op_list = []
 593
 594        # add for the content
 595        if annExtra1.content != annExtra2.content:
 596            content_cost: int = (
 597                Comparison._strings_levenshtein_distance(
 598                    annExtra1.content or '',
 599                    annExtra2.content or ''
 600                )
 601            )
 602            cost += content_cost
 603            op_list.append(("extracontentedit", annExtra1, annExtra2, content_cost))
 604
 605        # add for the symbolic (cost 2: delete one symbol, add the other)
 606        if annExtra1.symbolic != annExtra2.symbolic:
 607            cost += 2
 608            op_list.append(("extrasymboledit", annExtra1, annExtra2, 2))
 609
 610        # add for the infodict
 611        if annExtra1.infodict != annExtra2.infodict:
 612            info_cost: int = 0
 613            # handle everything in annExtra1 (whether or not it is in annExtra2)
 614            for k, v in annExtra1.infodict.items():
 615                if k not in annExtra2.infodict:
 616                    # not in annExtra2: delete a symbol
 617                    info_cost += 1
 618                elif v != annExtra2.infodict[k]:
 619                    # different in annExtra2: delete a symbol, add a symbol
 620                    info_cost += 2
 621            # handle everything in annExtra2 that is not in annExtra1
 622            for k in annExtra2.infodict:
 623                if k not in annExtra1.infodict:
 624                    # add a symbol
 625                    info_cost += 1
 626            cost += info_cost
 627            op_list.append(("extrainfoedit", annExtra1, annExtra2, info_cost))
 628
 629        # add for the offset
 630        # Note: offset here is a float, and some file formats have only four
 631        # decimal places of precision.  So we should not compare exactly here.
 632        if Comparison._areDifferentEnough(annExtra1.offset, annExtra2.offset):
 633            cost += 1
 634            op_list.append(("extraoffsetedit", annExtra1, annExtra2, 1))
 635
 636        # add for the duration
 637        # Note: duration here is a float, and some file formats have only four
 638        # decimal places of precision.  So we should not compare exactly here.
 639        if Comparison._areDifferentEnough(annExtra1.duration, annExtra2.duration):
 640            cost += 1
 641            op_list.append(("extradurationedit", annExtra1, annExtra2, 1))
 642
 643        # add for the style
 644        if annExtra1.styledict != annExtra2.styledict:
 645            cost += 1  # someday we might count different items in the styledict
 646            op_list.append(("extrastyleedit", annExtra1, annExtra2, 1))
 647
 648        return op_list, cost
 649
 650    @staticmethod
 651    def _annotated_lyric_diff(annLyric1: AnnLyric, annLyric2: AnnLyric):
 652        """
 653        Compute the differences between two annotated lyrics.
 654        Each annotated lyric consists of five values: lyric, verse_id, offset, duration,
 655        and styledict.
 656        """
 657        cost = 0
 658        op_list = []
 659
 660        # add for the content
 661        if annLyric1.lyric != annLyric2.lyric:
 662            content_cost: int = (
 663                Comparison._strings_levenshtein_distance(annLyric1.lyric, annLyric2.lyric)
 664            )
 665            cost += content_cost
 666            op_list.append(("lyricedit", annLyric1, annLyric2, content_cost))
 667
 668        # add for the number
 669        if annLyric1.number != annLyric2.number:
 670            number_cost: int
 671            if annLyric1.number == 0 or annLyric2.number == 0:
 672                # add or delete number
 673                number_cost = 1
 674            else:
 675                # add and delete number
 676                number_cost = 2
 677            cost += number_cost
 678            op_list.append(("lyricnumedit", annLyric1, annLyric2, number_cost))
 679
 680        # add for the identifier
 681        if annLyric1.identifier != annLyric2.identifier:
 682            # someday we might do a Levenshtein distance of the two ids
 683            id_cost: int
 684            if not annLyric1.identifier or not annLyric1.identifier:
 685                # add or delete identifier
 686                id_cost = 1
 687            else:
 688                # add and delete identifier
 689                id_cost = 2
 690            cost += id_cost
 691            op_list.append(("lyricidedit", annLyric1, annLyric2, id_cost))
 692
 693        # add for the offset
 694        # Note: offset here is a float, and some file formats have only four
 695        # decimal places of precision.  So we should not compare exactly here.
 696        if Comparison._areDifferentEnough(annLyric1.offset, annLyric2.offset):
 697            cost += 1
 698            op_list.append(("lyricoffsetedit", annLyric1, annLyric2, 1))
 699
 700        # add for the style
 701        if annLyric1.styledict != annLyric2.styledict:
 702            cost += 1  # someday we might count different items in the styledict
 703            op_list.append(("lyricstyleedit", annLyric1, annLyric2, 1))
 704
 705        return op_list, cost
 706
 707    @staticmethod
 708    def _annotated_metadata_item_diff(
 709        annMetadataItem1: AnnMetadataItem,
 710        annMetadataItem2: AnnMetadataItem
 711    ):
 712        """
 713        Compute the differences between two annotated metadata items.
 714        Each annotated metadata item has two values: key: str, value: t.Any,
 715        """
 716        cost = 0
 717        op_list = []
 718
 719        # we don't compare items that don't have the same key.
 720        if annMetadataItem1.key != annMetadataItem2.key:
 721            raise ValueError('unexpected comparison of metadata items with different keys')
 722
 723        # add for the value
 724        if annMetadataItem1.value != annMetadataItem2.value:
 725            value_cost: int = (
 726                Comparison._strings_levenshtein_distance(
 727                    str(annMetadataItem1.value),
 728                    str(annMetadataItem2.value)
 729                )
 730            )
 731            cost += value_cost
 732            op_list.append(
 733                ("mditemvalueedit", annMetadataItem1, annMetadataItem2, value_cost)
 734            )
 735
 736        return op_list, cost
 737
 738    @staticmethod
 739    def _annotated_staff_group_diff(annStaffGroup1: AnnStaffGroup, annStaffGroup2: AnnStaffGroup):
 740        """
 741        Compute the differences between two annotated staff groups.
 742        Each annotated staff group consists of five values: name, abbreviation,
 743        symbol, barTogether, part_indices.
 744        """
 745        cost = 0
 746        op_list = []
 747
 748        # add for the name
 749        if annStaffGroup1.name != annStaffGroup2.name:
 750            name_cost: int = (
 751                Comparison._strings_levenshtein_distance(
 752                    annStaffGroup1.name,
 753                    annStaffGroup2.name
 754                )
 755            )
 756            cost += name_cost
 757            op_list.append(("staffgrpnameedit", annStaffGroup1, annStaffGroup2, name_cost))
 758
 759        # add for the abbreviation
 760        if annStaffGroup1.abbreviation != annStaffGroup2.abbreviation:
 761            abbreviation_cost: int = (
 762                Comparison._strings_levenshtein_distance(
 763                    annStaffGroup1.abbreviation,
 764                    annStaffGroup2.abbreviation
 765                )
 766            )
 767            cost += abbreviation_cost
 768            op_list.append((
 769                "staffgrpabbreviationedit",
 770                annStaffGroup1,
 771                annStaffGroup2,
 772                abbreviation_cost
 773            ))
 774
 775        # add for the symbol
 776        if annStaffGroup1.symbol != annStaffGroup2.symbol:
 777            symbol_cost: int
 778            if not annStaffGroup1.symbol or not annStaffGroup2.symbol:
 779                # add or delete symbol
 780                symbol_cost = 1
 781            else:
 782                # add and delete symbol
 783                symbol_cost = 2
 784            cost += symbol_cost
 785            op_list.append(
 786                ("staffgrpsymboledit", annStaffGroup1, annStaffGroup2, symbol_cost)
 787            )
 788
 789        # add for barTogether
 790        if annStaffGroup1.barTogether != annStaffGroup2.barTogether:
 791            barTogether_cost: int = 1
 792            cost += barTogether_cost
 793            op_list.append(
 794                ("staffgrpbartogetheredit", annStaffGroup1, annStaffGroup2, barTogether_cost)
 795            )
 796
 797        # add for partIndices (sorted list of int)
 798        if annStaffGroup1.part_indices != annStaffGroup2.part_indices:
 799            partIndices_cost: int = 0
 800            if annStaffGroup1.part_indices[0] != annStaffGroup2.part_indices[0]:
 801                partIndices_cost += 1  # vertical start
 802            if annStaffGroup1.part_indices[-1] != annStaffGroup2.part_indices[-1]:
 803                partIndices_cost += 1  # vertical height
 804            if partIndices_cost == 0:
 805                # should never get here, but we have to have a cost
 806                partIndices_cost = 1
 807            cost += partIndices_cost
 808            op_list.append(
 809                ("staffgrppartindicesedit", annStaffGroup1, annStaffGroup2, partIndices_cost)
 810            )
 811
 812        return op_list, cost
 813
 814    @staticmethod
 815    @_memoize_inside_bars_diff_lin
 816    def _inside_bars_diff_lin(original, compare_to):
 817        # original and compare to are two lists of annotatedNote
 818        if len(original) == 0 and len(compare_to) == 0:
 819            return [], 0
 820
 821        if len(original) == 0:
 822            cost = 0
 823            op_list, cost = Comparison._inside_bars_diff_lin(original, compare_to[1:])
 824            op_list.append(("noteins", None, compare_to[0], compare_to[0].notation_size()))
 825            cost += compare_to[0].notation_size()
 826            return op_list, cost
 827
 828        if len(compare_to) == 0:
 829            cost = 0
 830            op_list, cost = Comparison._inside_bars_diff_lin(original[1:], compare_to)
 831            op_list.append(("notedel", original[0], None, original[0].notation_size()))
 832            cost += original[0].notation_size()
 833            return op_list, cost
 834
 835        # compute the cost and the op_list for the many possibilities of recursion
 836        cost = {}
 837        op_list = {}
 838        # notedel
 839        op_list["notedel"], cost["notedel"] = Comparison._inside_bars_diff_lin(
 840            original[1:], compare_to
 841        )
 842        cost["notedel"] += original[0].notation_size()
 843        op_list["notedel"].append(
 844            ("notedel", original[0], None, original[0].notation_size())
 845        )
 846        # noteins
 847        op_list["noteins"], cost["noteins"] = Comparison._inside_bars_diff_lin(
 848            original, compare_to[1:]
 849        )
 850        cost["noteins"] += compare_to[0].notation_size()
 851        op_list["noteins"].append(
 852            ("noteins", None, compare_to[0], compare_to[0].notation_size())
 853        )
 854        # notesub
 855        op_list["notesub"], cost["notesub"] = Comparison._inside_bars_diff_lin(
 856            original[1:], compare_to[1:]
 857        )
 858        if (
 859            original[0] == compare_to[0]
 860        ):  # avoid call another function if they are equal
 861            notesub_op, notesub_cost = [], 0
 862        else:
 863            notesub_op, notesub_cost = Comparison._annotated_note_diff(original[0], compare_to[0])
 864        cost["notesub"] += notesub_cost
 865        op_list["notesub"].extend(notesub_op)
 866        # compute the minimum of the possibilities
 867        min_key = min(cost, key=cost.get)
 868        out = op_list[min_key], cost[min_key]
 869        return out
 870
 871    @staticmethod
 872    def _annotated_note_diff(annNote1: AnnNote, annNote2: AnnNote):
 873        """
 874        Compute the differences between two annotated notes.
 875        Each annotated note consist in a 5tuple (pitches, notehead, dots, beamings, tuplets)
 876        where pitches is a list.
 877        Arguments:
 878            noteNode1 {[AnnNote]} -- original AnnNote
 879            noteNode2 {[AnnNote]} -- compare_to AnnNote
 880        """
 881        cost = 0
 882        op_list = []
 883        # add for the pitches
 884        # if they are equal
 885        if annNote1.pitches == annNote2.pitches:
 886            op_list_pitch, cost_pitch = [], 0
 887        else:
 888            # pitches diff is computed using Levenshtein distances (they are already ordered)
 889            op_list_pitch, cost_pitch = Comparison._pitches_levenshtein_diff(
 890                annNote1.pitches, annNote2.pitches, annNote1, annNote2, (0, 0)
 891            )
 892        op_list.extend(op_list_pitch)
 893        cost += cost_pitch
 894        # add for the notehead
 895        if annNote1.note_head != annNote2.note_head:
 896            # delete one note head, add the other (this isn't noteshape, this is
 897            # just quarter-note note head vs half-note note head, etc)
 898            cost += 2
 899            op_list.append(("headedit", annNote1, annNote2, 2))
 900        # add for the dots
 901        if annNote1.dots != annNote2.dots:
 902            # add one for each added (or deleted) dot
 903            dots_diff = abs(annNote1.dots - annNote2.dots)
 904            cost += dots_diff
 905            if annNote1.dots > annNote2.dots:
 906                op_list.append(("dotdel", annNote1, annNote2, dots_diff))
 907            else:
 908                op_list.append(("dotins", annNote1, annNote2, dots_diff))
 909        if annNote1.graceType != annNote2.graceType:
 910            # accented vs unaccented vs not a grace note (delete the wrong, add the right)
 911            cost += 2
 912            op_list.append(("graceedit", annNote1, annNote2, 2))
 913        if annNote1.graceSlash != annNote2.graceSlash:
 914            # add or delete the slash
 915            cost += 1
 916            op_list.append(("graceslashedit", annNote1, annNote2, 1))
 917        # add for the beamings
 918        if annNote1.beamings != annNote2.beamings:
 919            beam_op_list, beam_cost = Comparison._beamtuplet_levenshtein_diff(
 920                annNote1.beamings, annNote2.beamings, annNote1, annNote2, "beam"
 921            )
 922            op_list.extend(beam_op_list)
 923            cost += beam_cost
 924        # add for the tuplet types
 925        if annNote1.tuplets != annNote2.tuplets:
 926            tuplet_op_list, tuplet_cost = Comparison._beamtuplet_levenshtein_diff(
 927                annNote1.tuplets, annNote2.tuplets, annNote1, annNote2, "tuplet"
 928            )
 929            op_list.extend(tuplet_op_list)
 930            cost += tuplet_cost
 931        # add for the tuplet info
 932        if annNote1.tuplet_info != annNote2.tuplet_info:
 933            tuplet_info_op_list, tuplet_info_cost = Comparison._beamtuplet_levenshtein_diff(
 934                annNote1.tuplet_info, annNote2.tuplet_info, annNote1, annNote2, "tuplet"
 935            )
 936            op_list.extend(tuplet_info_op_list)
 937            cost += tuplet_info_cost
 938        # add for the articulations
 939        if annNote1.articulations != annNote2.articulations:
 940            artic_op_list, artic_cost = Comparison._generic_levenshtein_diff(
 941                annNote1.articulations,
 942                annNote2.articulations,
 943                annNote1,
 944                annNote2,
 945                "articulation",
 946            )
 947            op_list.extend(artic_op_list)
 948            cost += artic_cost
 949        # add for the expressions
 950        if annNote1.expressions != annNote2.expressions:
 951            expr_op_list, expr_cost = Comparison._generic_levenshtein_diff(
 952                annNote1.expressions,
 953                annNote2.expressions,
 954                annNote1,
 955                annNote2,
 956                "expression",
 957            )
 958            op_list.extend(expr_op_list)
 959            cost += expr_cost
 960
 961        # add for gap from previous note or start of measure if first note in measure
 962        # (i.e. horizontal position shift)
 963        if annNote1.gap_dur != annNote2.gap_dur:
 964            # in all cases, the edit is a simple horizontal shift of the note
 965            cost += 1
 966            if annNote1.gap_dur == 0:
 967                op_list.append(("insspace", annNote1, annNote2, 1))
 968            elif annNote2.gap_dur == 0:
 969                op_list.append(("delspace", annNote1, annNote2, 1))
 970            else:
 971                # neither is zero
 972                op_list.append(("editspace", annNote1, annNote2, 1))
 973
 974        # add for noteshape
 975        if annNote1.noteshape != annNote2.noteshape:
 976            # always delete existing note shape and add the new one
 977            cost += 2
 978            op_list.append(("editnoteshape", annNote1, annNote2, 2))
 979        # add for noteheadFill
 980        if annNote1.noteheadFill != annNote2.noteheadFill:
 981            # always delete existing note fill and add the new one
 982            cost += 2
 983            op_list.append(("editnoteheadfill", annNote1, annNote2, 2))
 984        # add for noteheadParenthesis (True or False)
 985        if annNote1.noteheadParenthesis != annNote2.noteheadParenthesis:
 986            # always either add or delete parentheses
 987            cost += 1
 988            op_list.append(("editnoteheadparenthesis", annNote1, annNote2, 1))
 989        # add for stemDirection
 990        if annNote1.stemDirection != annNote2.stemDirection:
 991            stemdir_cost: int
 992            if annNote1.stemDirection == 'noStem' or annNote2.stemDirection == 'noStem':
 993                # gonna add a stem
 994                stemdir_cost = 1
 995            else:
 996                # gonna change a stem (add then delete)
 997                stemdir_cost = 2
 998            cost += stemdir_cost
 999            op_list.append(("editstemdirection", annNote1, annNote2, stemdir_cost))
1000        # add for the styledict
1001        if annNote1.styledict != annNote2.styledict:
1002            cost += 1
1003            op_list.append(("editstyle", annNote1, annNote2, 1))
1004
1005        return op_list, cost
1006
1007    @staticmethod
1008    @_memoize_beamtuplet_lev_diff
1009    def _beamtuplet_levenshtein_diff(original, compare_to, note1, note2, which):
1010        """
1011        Compute the levenshtein distance between two sequences of beaming or tuples.
1012        Arguments:
1013            original {list} -- list of strings (start, stop, continue or partial)
1014            compare_to {list} -- list of strings (start, stop, continue or partial)
1015            note1 {AnnNote} -- the note for referencing in the score
1016            note2 {AnnNote} -- the note for referencing in the score
1017            which -- a string: "beam" or "tuplet" depending what we are comparing
1018        """
1019        if which not in ("beam", "tuplet"):
1020            raise ValueError("Argument 'which' must be either 'beam' or 'tuplet'")
1021
1022        if len(original) == 0 and len(compare_to) == 0:
1023            return [], 0
1024
1025        if len(original) == 0:
1026            op_list, cost = Comparison._beamtuplet_levenshtein_diff(
1027                original, compare_to[1:], note1, note2, which
1028            )
1029            op_list.append(("ins" + which, note1, note2, 1))
1030            cost += 1
1031            return op_list, cost
1032
1033        if len(compare_to) == 0:
1034            op_list, cost = Comparison._beamtuplet_levenshtein_diff(
1035                original[1:], compare_to, note1, note2, which
1036            )
1037            op_list.append(("del" + which, note1, note2, 1))
1038            cost += 1
1039            return op_list, cost
1040
1041        # compute the cost and the op_list for the many possibilities of recursion
1042        cost = {}
1043        op_list = {}
1044        # delwhich
1045        op_list["del" + which], cost["del" + which] = Comparison._beamtuplet_levenshtein_diff(
1046            original[1:], compare_to, note1, note2, which
1047        )
1048        cost["del" + which] += 1
1049        op_list["del" + which].append(("del" + which, note1, note2, 1))
1050        # inswhich
1051        op_list["ins" + which], cost["ins" + which] = Comparison._beamtuplet_levenshtein_diff(
1052            original, compare_to[1:], note1, note2, which
1053        )
1054        cost["ins" + which] += 1
1055        op_list["ins" + which].append(("ins" + which, note1, note2, 1))
1056        # editwhich
1057        op_list["edit" + which], cost["edit" + which] = Comparison._beamtuplet_levenshtein_diff(
1058            original[1:], compare_to[1:], note1, note2, which
1059        )
1060        if original[0] == compare_to[0]:
1061            beam_diff_op_list = []
1062            beam_diff_cost = 0
1063        else:
1064            beam_diff_op_list, beam_diff_cost = [("edit" + which, note1, note2, 1)], 1
1065        cost["edit" + which] += beam_diff_cost
1066        op_list["edit" + which].extend(beam_diff_op_list)
1067        # compute the minimum of the possibilities
1068        min_key = min(cost, key=cost.get)
1069        out = op_list[min_key], cost[min_key]
1070        return out
1071
1072    @staticmethod
1073    @_memoize_generic_lev_diff
1074    def _generic_levenshtein_diff(original, compare_to, note1, note2, which):
1075        """
1076        Compute the Levenshtein distance between two generic sequences of symbols
1077        (e.g., articulations).
1078        Arguments:
1079            original {list} -- list of strings
1080            compare_to {list} -- list of strings
1081            note1 {AnnNote} -- the note for referencing in the score
1082            note2 {AnnNote} -- the note for referencing in the score
1083            which -- a string: e.g. "articulation" depending what we are comparing
1084        """
1085        if len(original) == 0 and len(compare_to) == 0:
1086            return [], 0
1087
1088        if len(original) == 0:
1089            op_list, cost = Comparison._generic_levenshtein_diff(
1090                original, compare_to[1:], note1, note2, which
1091            )
1092            op_list.append(("ins" + which, note1, note2, 1))
1093            cost += 1
1094            return op_list, cost
1095
1096        if len(compare_to) == 0:
1097            op_list, cost = Comparison._generic_levenshtein_diff(
1098                original[1:], compare_to, note1, note2, which
1099            )
1100            op_list.append(("del" + which, note1, note2, 1))
1101            cost += 1
1102            return op_list, cost
1103
1104        # compute the cost and the op_list for the many possibilities of recursion
1105        cost = {}
1106        op_list = {}
1107        # delwhich
1108        op_list["del" + which], cost["del" + which] = Comparison._generic_levenshtein_diff(
1109            original[1:], compare_to, note1, note2, which
1110        )
1111        cost["del" + which] += 1
1112        op_list["del" + which].append(("del" + which, note1, note2, 1))
1113        # inswhich
1114        op_list["ins" + which], cost["ins" + which] = Comparison._generic_levenshtein_diff(
1115            original, compare_to[1:], note1, note2, which
1116        )
1117        cost["ins" + which] += 1
1118        op_list["ins" + which].append(("ins" + which, note1, note2, 1))
1119        # editwhich
1120        op_list["edit" + which], cost["edit" + which] = Comparison._generic_levenshtein_diff(
1121            original[1:], compare_to[1:], note1, note2, which
1122        )
1123        if original[0] == compare_to[0]:  # to avoid perform the diff
1124            generic_diff_op_list = []
1125            generic_diff_cost = 0
1126        else:
1127            generic_diff_op_list, generic_diff_cost = (
1128                [("edit" + which, note1, note2, 1)],
1129                1,
1130            )
1131        cost["edit" + which] += generic_diff_cost
1132        op_list["edit" + which].extend(generic_diff_op_list)
1133        # compute the minimum of the possibilities
1134        min_key = min(cost, key=cost.get)
1135        out = op_list[min_key], cost[min_key]
1136        return out
1137
1138    @staticmethod
1139    @_memoize_notes_set_distance
1140    def _notes_set_distance(original: list[AnnNote], compare_to: list[AnnNote]):
1141        """
1142        Gather up pairs of matching notes (using pitch, offset, graceness, and visual duration, in
1143        that order of importance).  If you can't find an exactly matching note, try again without
1144        visual duration.
1145        original [list] -- a list of AnnNote (which are never chords)
1146        compare_to [list] -- a list of AnnNote (which are never chords)
1147        """
1148        paired_notes: list[tuple[AnnNote, AnnNote]] = []
1149        unpaired_orig_notes: list[AnnNote] = []
1150        unpaired_comp_notes: list[AnnNote] = copy.copy(compare_to)
1151
1152        for orig_n in original:
1153            fallback: AnnNote | None = None
1154            fallback_i: int = -1
1155            found_it: bool = False
1156            for i, comp_n in enumerate(unpaired_comp_notes):
1157                if orig_n.pitches[0][0] != comp_n.pitches[0][0]:
1158                    # this pitch comparison (1) assumes the note is not a chord
1159                    # (because we don't do chords when Voicing is not set, and
1160                    # we only call _notes_set_distance when Voicing is not set),
1161                    # and (2) only compares the visual position of the note (we
1162                    # are ignoring the accidental here).  This is so that an
1163                    # accidental change will show up as a pitch edit, not a
1164                    # note remove/insert.
1165                    continue
1166                if Comparison._areDifferentEnough(orig_n.note_offset, comp_n.note_offset):
1167                    continue
1168                if orig_n.note_is_grace != comp_n.note_is_grace:
1169                    continue
1170                if fallback is None:
1171                    fallback = comp_n
1172                    fallback_i = i
1173
1174                if orig_n.note_dur_type != comp_n.note_dur_type:
1175                    continue
1176                if orig_n.note_dur_dots != comp_n.note_dur_dots:
1177                    continue
1178
1179                # found a perfect match
1180                paired_notes.append((orig_n, comp_n))
1181
1182                # remove comp_n from unpaired_comp_notes
1183                unpaired_comp_notes.pop(i)  # remove(comp_n) would sometimes get the wrong one
1184
1185                found_it = True
1186                break
1187
1188            if found_it:
1189                # on to the next original note
1190                continue
1191
1192            # did we find a fallback (matched except for duration)?
1193            if fallback is not None:
1194                paired_notes.append((orig_n, fallback))
1195                unpaired_comp_notes.pop(fallback_i)
1196                continue
1197
1198            # we found nothing
1199            unpaired_orig_notes.append(orig_n)
1200
1201        # compute the cost and the op_list
1202        cost: int = 0
1203        op_list: list = []
1204
1205        # notedel
1206        if unpaired_orig_notes:
1207            for an in unpaired_orig_notes:
1208                cost += an.notation_size()
1209                op_list.append(("notedel", an, None, an.notation_size(), an.note_idx_in_chord))
1210
1211        # noteins
1212        if unpaired_comp_notes:
1213            for an in unpaired_comp_notes:
1214                cost += an.notation_size()
1215                op_list.append(("noteins", None, an, an.notation_size(), an.note_idx_in_chord))
1216
1217        # notesub
1218        if paired_notes:
1219            for ano, anc in paired_notes:
1220                if ano == anc:
1221                    # if equal, avoid _annotated_note_diff call
1222                    notesub_op, notesub_cost = [], 0
1223                else:
1224                    notesub_op, notesub_cost = (
1225                        Comparison._annotated_note_diff(ano, anc)
1226                    )
1227                cost += notesub_cost
1228                op_list.extend(notesub_op)
1229
1230        return op_list, cost
1231
1232    @staticmethod
1233    @_memoize_extras_set_distance
1234    def _extras_set_distance(original: list[AnnExtra], compare_to: list[AnnExtra]):
1235        """
1236        Gather up pairs of matching extras (using kind, offset, and visual duration, in
1237        that order of importance).  If you can't find an exactly matching extra, try again
1238        without visual duration.
1239        original [list] -- a list of AnnExtras
1240        compare_to [list] -- a list of AnnExtras
1241        """
1242        paired_extras: list[tuple[AnnExtra, AnnExtra]] = []
1243        unpaired_orig_extras: list[AnnExtra] = []
1244        unpaired_comp_extras: list[AnnExtra] = copy.copy(compare_to)
1245
1246        for orig_x in original:
1247            fallback: AnnExtra | None = None
1248            fallback_i: int = -1
1249            found_it: bool = False
1250            for i, comp_x in enumerate(unpaired_comp_extras):
1251                # kind and offset are required for pairing
1252                if orig_x.kind != comp_x.kind:
1253                    continue
1254                if Comparison._areDifferentEnough(orig_x.offset, comp_x.offset):
1255                    continue
1256                if fallback is None:
1257                    fallback = comp_x
1258                    fallback_i = i
1259
1260                # duration is preferred for pairing
1261                if Comparison._areDifferentEnough(orig_x.duration, comp_x.duration):
1262                    continue
1263
1264                # there are a few kind-specific elements that are also preferred:
1265                #   'direction'/'ending': content (visible text)
1266                #   'keysig'/'timesig'/'clef': symbolic (there are sometimes two
1267                #       simultaneous keysigs, timesigs, or clefs, and we don't
1268                #       want to confuse which one is which, producing a diff where
1269                #       there actually isn't one)
1270                #   'slur': placements (because there are often two identical slurs
1271                #       whose only difference is 'above' vs 'below', producing a diff
1272                #       where there actually isn't one)
1273                if orig_x.kind in ('direction', 'ending'):
1274                    if orig_x.content != comp_x.content:
1275                        continue
1276                if orig_x.kind == 'clef':
1277                    if orig_x.symbolic != comp_x.symbolic:
1278                        continue
1279                if orig_x.kind in ('keysig', 'timesig'):
1280                    if orig_x.infodict != comp_x.infodict:
1281                        continue
1282                if orig_x.kind == 'slur':
1283                    orig_placement: str = orig_x.styledict.get('placement', '')
1284                    comp_placement: str = comp_x.styledict.get('placement', '')
1285                    if orig_placement != comp_placement:
1286                        continue
1287
1288                # found a perfect match
1289                paired_extras.append((orig_x, comp_x))
1290
1291                # remove comp_n from unpaired_comp_extras
1292                unpaired_comp_extras.pop(i)  # remove(comp_n) would sometimes get the wrong one
1293
1294                found_it = True
1295                break
1296
1297            if found_it:
1298                # on to the next original extra
1299                continue
1300
1301            # did we find a fallback (matched except for duration)?
1302            if fallback is not None:
1303                paired_extras.append((orig_x, fallback))
1304                unpaired_comp_extras.pop(fallback_i)
1305                continue
1306
1307            # we found nothing
1308            unpaired_orig_extras.append(orig_x)
1309
1310        # compute the cost and the op_list
1311        cost: int = 0
1312        op_list: list = []
1313
1314        # extradel
1315        for extra in unpaired_orig_extras:
1316            cost += extra.notation_size()
1317            op_list.append(("extradel", extra, None, extra.notation_size()))
1318
1319        # extrains
1320        for extra in unpaired_comp_extras:
1321            cost += extra.notation_size()
1322            op_list.append(("extrains", None, extra, extra.notation_size()))
1323
1324        # extrasub
1325        if paired_extras:
1326            for extrao, extrac in paired_extras:
1327                if extrao == extrac:
1328                    # if equal, avoid _annotated_extra_diff call
1329                    extrasub_op, extrasub_cost = [], 0
1330                else:
1331                    extrasub_op, extrasub_cost = (
1332                        Comparison._annotated_extra_diff(extrao, extrac)
1333                    )
1334                cost += extrasub_cost
1335                op_list.extend(extrasub_op)
1336
1337        return op_list, cost
1338
1339    @staticmethod
1340    @_memoize_metadata_items_set_distance
1341    def _metadata_items_set_distance(
1342        original: list[AnnMetadataItem],
1343        compare_to: list[AnnMetadataItem]
1344    ):
1345        """
1346        Gather up pairs of matching metadata_items (using key and value).  If you can't find
1347        an exactly matching metadata_item, try again without value.
1348        original [list] -- a list of AnnMetadataItems
1349        compare_to [list] -- a list of AnnMetadataItems
1350        """
1351        paired_metadata_items: list[tuple[AnnMetadataItem, AnnMetadataItem]] = []
1352        unpaired_orig_metadata_items: list[AnnMetadataItem] = []
1353        unpaired_comp_metadata_items: list[AnnMetadataItem] = copy.copy(compare_to)
1354
1355        # first look for perfect matches
1356        for orig_mdi in original:
1357            found_it: bool = False
1358            for i, comp_mdi in enumerate(unpaired_comp_metadata_items):
1359                # key is required for perfect match
1360                if orig_mdi.key != comp_mdi.key:
1361                    continue
1362
1363                # value is required for perfect match
1364                if orig_mdi.value != comp_mdi.value:
1365                    continue
1366
1367                # found a perfect match
1368                paired_metadata_items.append((orig_mdi, comp_mdi))
1369
1370                # remove comp_mdi from unpaired_comp_metadata_items
1371                unpaired_comp_metadata_items.pop(i)
1372
1373                found_it = True
1374                break
1375
1376            if found_it:
1377                # on to the next original metadata_item
1378                continue
1379
1380            # we found no perfect match
1381            unpaired_orig_metadata_items.append(orig_mdi)
1382
1383        # now look among the unpaired remainders for key match only
1384        remove_unpaired_orig_items: list[AnnMetadataItem] = []
1385        for orig_mdi in unpaired_orig_metadata_items:
1386            for comp_idx, comp_mdi in enumerate(unpaired_comp_metadata_items):
1387                # key is required for key-only match
1388                if orig_mdi.key != comp_mdi.key:
1389                    continue
1390
1391                # found a key-only match
1392                paired_metadata_items.append((orig_mdi, comp_mdi))
1393
1394                # remove comp_mdi from unpaired_comp_metadata_items
1395                unpaired_comp_metadata_items.pop(comp_idx)
1396
1397                # make a note of unpaired_orig_metadata_item to remove later
1398                remove_unpaired_orig_items.append(orig_mdi)
1399                break
1400
1401        for remove_mdi in remove_unpaired_orig_items:
1402            unpaired_orig_metadata_items.remove(remove_mdi)
1403
1404        # compute the cost and the op_list
1405        cost: int = 0
1406        op_list: list = []
1407
1408        # mditemdel
1409        for metadata_item in unpaired_orig_metadata_items:
1410            cost += metadata_item.notation_size()
1411            op_list.append(("mditemdel", metadata_item, None, metadata_item.notation_size()))
1412
1413        # mditemins
1414        for metadata_item in unpaired_comp_metadata_items:
1415            cost += metadata_item.notation_size()
1416            op_list.append(("mditemins", None, metadata_item, metadata_item.notation_size()))
1417
1418        # mditemsub
1419        if paired_metadata_items:
1420            for metadata_itemo, metadata_itemc in paired_metadata_items:
1421                if metadata_itemo == metadata_itemc:
1422                    # if equal, avoid _annotated_metadata_item_diff call
1423                    metadata_itemsub_op, metadata_itemsub_cost = [], 0
1424                else:
1425                    metadata_itemsub_op, metadata_itemsub_cost = (
1426                        Comparison._annotated_metadata_item_diff(metadata_itemo, metadata_itemc)
1427                    )
1428                cost += metadata_itemsub_cost
1429                op_list.extend(metadata_itemsub_op)
1430
1431        return op_list, cost
1432
1433    @staticmethod
1434    @_memoize_staff_groups_set_distance
1435    def _staff_groups_set_distance(
1436        original: list[AnnStaffGroup],
1437        compare_to: list[AnnStaffGroup]
1438    ):
1439        """
1440        Gather up pairs of matching staffgroups (using start_index and end_index, in
1441        that order of importance).  If you can't find an exactly matching staffgroup,
1442        try again without end_index.
1443        original [list] -- a list of AnnStaffGroups
1444        compare_to [list] -- a list of AnnStaffGroups
1445        """
1446        paired_staff_groups: list[tuple[AnnStaffGroup, AnnStaffGroup]] = []
1447        unpaired_orig_staff_groups: list[AnnStaffGroup] = []
1448        unpaired_comp_staff_groups: list[AnnStaffGroup] = copy.copy(compare_to)
1449
1450        for orig_sg in original:
1451            fallback: AnnStaffGroup | None = None
1452            fallback_i: int = -1
1453            found_it: bool = False
1454            for i, comp_sg in enumerate(unpaired_comp_staff_groups):
1455                # start index is required for pairing
1456                if orig_sg.part_indices[0] != comp_sg.part_indices[0]:
1457                    continue
1458                if fallback is None:
1459                    fallback = comp_sg
1460                    fallback_i = i
1461
1462                # end index and symbol (brace, bracket, etc) is preferred for pairing
1463                if orig_sg.part_indices[-1] != comp_sg.part_indices[-1]:
1464                    continue
1465                if orig_sg.symbol != comp_sg.symbol:
1466                    continue
1467
1468                # found a perfect match
1469                paired_staff_groups.append((orig_sg, comp_sg))
1470
1471                # remove comp_n from unpaired_comp_staff_groups
1472                unpaired_comp_staff_groups.pop(i)
1473
1474                found_it = True
1475                break
1476
1477            if found_it:
1478                # on to the next original staff_group
1479                continue
1480
1481            # did we find a fallback (matched except for duration)?
1482            if fallback is not None:
1483                paired_staff_groups.append((orig_sg, fallback))
1484                unpaired_comp_staff_groups.pop(fallback_i)
1485                continue
1486
1487            # we found nothing
1488            unpaired_orig_staff_groups.append(orig_sg)
1489
1490        # compute the cost and the op_list
1491        cost: int = 0
1492        op_list: list = []
1493
1494        # staffgrpdel
1495        for staff_group in unpaired_orig_staff_groups:
1496            cost += staff_group.notation_size()
1497            op_list.append(("staffgrpdel", staff_group, None, staff_group.notation_size()))
1498
1499        # staffgrpins
1500        for staff_group in unpaired_comp_staff_groups:
1501            cost += staff_group.notation_size()
1502            op_list.append(("staffgrpins", None, staff_group, staff_group.notation_size()))
1503
1504        # staffgrpsub
1505        if paired_staff_groups:
1506            for staff_groupo, staff_groupc in paired_staff_groups:
1507                if staff_groupo == staff_groupc:
1508                    # if equal, avoid _annotated_staff_group_diff call
1509                    staff_groupsub_op, staff_groupsub_cost = [], 0
1510                else:
1511                    staff_groupsub_op, staff_groupsub_cost = (
1512                        Comparison._annotated_staff_group_diff(staff_groupo, staff_groupc)
1513                    )
1514                cost += staff_groupsub_cost
1515                op_list.extend(staff_groupsub_op)
1516
1517        return op_list, cost
1518
1519    @staticmethod
1520    def _voices_coupling_recursive(original: list[AnnVoice], compare_to: list[AnnVoice]):
1521        """
1522        Compare all the possible voices permutations, considering also deletion and
1523        insertion (equation on office lens).
1524        original [list] -- a list of Voice
1525        compare_to [list] -- a list of Voice
1526        """
1527        if len(original) == 0 and len(compare_to) == 0:  # stop the recursion
1528            return [], 0
1529
1530        if len(original) == 0:
1531            # insertion
1532            op_list, cost = Comparison._voices_coupling_recursive(original, compare_to[1:])
1533            # add for the inserted voice
1534            op_list.append(("voiceins", None, compare_to[0], compare_to[0].notation_size()))
1535            cost += compare_to[0].notation_size()
1536            return op_list, cost
1537
1538        if len(compare_to) == 0:
1539            # deletion
1540            op_list, cost = Comparison._voices_coupling_recursive(original[1:], compare_to)
1541            # add for the deleted voice
1542            op_list.append(("voicedel", original[0], None, original[0].notation_size()))
1543            cost += original[0].notation_size()
1544            return op_list, cost
1545
1546        cost = {}
1547        op_list = {}
1548        # deletion
1549        op_list["voicedel"], cost["voicedel"] = Comparison._voices_coupling_recursive(
1550            original[1:], compare_to
1551        )
1552        op_list["voicedel"].append(
1553            ("voicedel", original[0], None, original[0].notation_size())
1554        )
1555        cost["voicedel"] += original[0].notation_size()
1556        for i, c in enumerate(compare_to):
1557            # substitution
1558            (
1559                op_list["voicesub" + str(i)],
1560                cost["voicesub" + str(i)],
1561            ) = Comparison._voices_coupling_recursive(
1562                original[1:], compare_to[:i] + compare_to[i + 1:]
1563            )
1564            if (
1565                compare_to[0] != original[0]
1566            ):  # add the cost of the sub and the operations from inside_bar_diff
1567                op_list_inside_bar, cost_inside_bar = Comparison._inside_bars_diff_lin(
1568                    original[0].annot_notes, c.annot_notes
1569                )  # compute the distance from original[0] and compare_to[i]
1570                op_list["voicesub" + str(i)].extend(op_list_inside_bar)
1571                cost["voicesub" + str(i)] += cost_inside_bar
1572        # compute the minimum of the possibilities
1573        min_key = min(cost, key=cost.get)
1574        out = op_list[min_key], cost[min_key]
1575        return out
1576
1577    @staticmethod
1578    def annotated_scores_diff(score1: AnnScore, score2: AnnScore) -> tuple[list[tuple], int]:
1579        '''
1580        Compare two annotated scores, computing an operations list and the cost of applying those
1581        operations to the first score to generate the second score.
1582
1583        Args:
1584            score1 (`musicdiff.annotation.AnnScore`): The first annotated score to compare.
1585            score2 (`musicdiff.annotation.AnnScore`): The second annotated score to compare.
1586
1587        Returns:
1588            list[tuple], int: The operations list and the cost
1589        '''
1590        # Clear all memoizer caches, in case we are called again with different scores.
1591        # The cached results are no longer valid.
1592        Comparison._clear_memoizer_caches()
1593
1594        op_list_total: list[tuple] = []
1595        cost_total: int = 0
1596
1597        if score1.n_of_parts == score2.n_of_parts:
1598            n_of_parts = score1.n_of_parts
1599        else:
1600            # The two scores have differing number of parts.  For now, assume that
1601            # the parts are in the same order in both scores, and that the missing
1602            # parts are the ones that should have been at the end of the smaller
1603            # score. In future we could do something like we do with voices, where
1604            # we try all the combinations and compare the most-similar pairs of
1605            # parts, and the rest are considered to be the extra parts (deleted
1606            # from score1, or inserted into score2).
1607            n_of_parts = min(score1.n_of_parts, score2.n_of_parts)
1608            if score1.n_of_parts > score2.n_of_parts:
1609                # score1 has more parts that must be deleted
1610                for part_idx in range(score2.n_of_parts, score1.n_of_parts):
1611                    deleted_part = score1.part_list[part_idx]
1612                    op_list_total.append(
1613                        (
1614                            "delpart",
1615                            deleted_part,
1616                            None,
1617                            deleted_part.notation_size()
1618                        )
1619                    )
1620                    cost_total += deleted_part.notation_size()
1621            else:
1622                # score2 has more parts that must be inserted
1623                for part_idx in range(score1.n_of_parts, score2.n_of_parts):
1624                    inserted_part = score2.part_list[part_idx]
1625                    op_list_total.append(
1626                        (
1627                            "inspart",
1628                            None,
1629                            inserted_part,
1630                            inserted_part.notation_size()
1631                        )
1632                    )
1633                    cost_total += inserted_part.notation_size()
1634
1635        # iterate over parts that exist in both scores
1636        for p_number in range(n_of_parts):
1637            # compute non-common-subseq
1638            ncs = Comparison._non_common_subsequences_of_measures(
1639                score1.part_list[p_number].bar_list,
1640                score2.part_list[p_number].bar_list,
1641            )
1642            # compute blockdiff
1643            for subseq in ncs:
1644                op_list_block, cost_block = Comparison._block_diff_lin(
1645                    subseq["original"], subseq["compare_to"]
1646                )
1647                op_list_total.extend(op_list_block)
1648                cost_total += cost_block
1649
1650        # compare the staff groups
1651        groups_op_list, groups_cost = Comparison._staff_groups_set_distance(
1652            score1.staff_group_list, score2.staff_group_list
1653        )
1654        op_list_total.extend(groups_op_list)
1655        cost_total += groups_cost
1656
1657        # compare the metadata items
1658        mditems_op_list, mditems_cost = Comparison._metadata_items_set_distance(
1659            score1.metadata_items_list, score2.metadata_items_list
1660        )
1661        op_list_total.extend(mditems_op_list)
1662        cost_total += mditems_cost
1663
1664        # Add the cost of any syntax errors in score1 that were fixed during parsing.
1665        # Ignore enough syntax errors to keep OMR-NED <= 1.0, for consistency.
1666        total_syms: int = score1.notation_size() + score2.notation_size()
1667        cost_plus_errors: int = cost_total + score1.num_syntax_errors_fixed
1668        if cost_plus_errors > total_syms:
1669            adjustment: int = cost_plus_errors - total_syms
1670            score1.num_syntax_errors_fixed -= adjustment
1671
1672        cost_total += score1.num_syntax_errors_fixed
1673
1674        return op_list_total, cost_total