r"""
    Finds what happened to the old groups to form the new groups.

    Args:
        old (set of frozensets): old grouping
        new (set of frozensets): new grouping
        pure (bool): hybrids are separated from pure merges and splits if
            pure is True, otherwise hybrid cases are grouped in merges and
            splits.

    Returns:
        dict: delta: dictionary of changes containing the merges, splits,
            unchanged, and hybrid cases. Except for unchanged, case a subdict
            with new and old keys.  For splits / merges, one of these contains
            nested sequences to indicate what the split / merge is.

    TODO:
        incorporate addition / deletion of elements?

    Notes:
        merges - which old groups were merged into a single new group.
        splits - which old groups were split into multiple new groups.
        hybrid - which old groups had split/merge actions applied.
        unchanged - which old groups are the same as new groups.

    Example:
        >>> # ENABLE_DOCTEST
        >>> from utool.util_alg import *  # NOQA
        >>> import utool as ut
        >>> old = [
        >>>     [20, 21, 22, 23], [1, 2], [12], [13, 14], [3, 4], [5, 6,11],
        >>>     [7], [8, 9], [10], [31, 32], [33, 34, 35], [41, 42, 43, 44, 45]
        >>> ]
        >>> new = [
        >>>   [20, 21], [22, 23], [1, 2], [12, 13, 14], [4], [5, 6, 3], [7, 8],
        >>>   [9, 10, 11], [31, 32, 33, 34, 35],   [41, 42, 43, 44], [45],
        >>> ]
        >>> delta = ut.grouping_delta(old, new)
        >>> assert set(old[0]) in delta['splits']['old']
        >>> assert set(new[3]) in delta['merges']['new']
        >>> assert set(old[1]) in delta['unchanged']
        >>> result = ut.repr4(delta, nl=2, nobr=True, sk=True)
        >>> print(result)
        unchanged: {
            {1, 2},
        },
        splits: {
            old: [{20, 21, 22, 23}, {41, 42, 43, 44, 45}],
            new: [{{20, 21}, {22, 23}}, {{41, 42, 43, 44}, {45}}],
        },
        merges: {
            old: [{{12}, {13, 14}}, {{31, 32}, {33, 34, 35}}],
            new: [{12, 13, 14}, {31, 32, 33, 34, 35}],
        },
        hybrid: {
            old: {{10}, {3, 4}, {5, 6, 11}, {7}, {8, 9}},
            new: {{3, 5, 6}, {4}, {7, 8}, {9, 10, 11}},
            splits: [{{7}}, {{11}, {5, 6}}, {{10}}, {{3}, {4}}, {{8}, {9}}],
            merges: [{{7}, {8}}, {{4}}, {{3}, {5, 6}}, {{10}, {11}, {9}}],
        },


    Example:
        >>> # ENABLE_DOCTEST
        >>> from utool.util_alg import *  # NOQA
        >>> import utool as ut
        >>> old = [
        >>>     [1, 2, 3], [4], [5, 6, 7, 8, 9], [10, 11, 12]
        >>> ]
        >>> new = [
        >>>     [1], [2], [3, 4], [5, 6, 7], [8, 9, 10, 11, 12]
        >>> ]
        >>> # every case here is hybrid
        >>> pure_delta = ut.grouping_delta(old, new, pure=True)
        >>> assert len(ut.flatten(pure_delta['merges'].values())) == 0
        >>> assert len(ut.flatten(pure_delta['splits'].values())) == 0
        >>> delta = ut.grouping_delta(old, new, pure=False)
        >>> delta = ut.order_dict_by(delta, ['unchanged', 'splits', 'merges'])
        >>> result = ut.repr4(delta, nl=2, sk=True)
        >>> print(result)
        {
            unchanged: {},
            splits: [
                [{2}, {3}, {1}],
                [{8, 9}, {5, 6, 7}],
            ],
            merges: [
                [{4}, {3}],
                [{8, 9}, {10, 11, 12}],
            ],
        }

def grouping_delta(old, new, pure=True):
    r"""
    Finds what happened to the old groups to form the new groups.

    Args:
        old (set of frozensets): old grouping
        new (set of frozensets): new grouping
        pure (bool): hybrids are separated from pure merges and splits if
            pure is True, otherwise hybrid cases are grouped in merges and
            splits.

    Returns:
        dict: delta: dictionary of changes containing the merges, splits,
            unchanged, and hybrid cases. Except for unchanged, case a subdict
            with new and old keys.  For splits / merges, one of these contains
            nested sequences to indicate what the split / merge is.

    TODO:
        incorporate addition / deletion of elements?

    Notes:
        merges - which old groups were merged into a single new group.
        splits - which old groups were split into multiple new groups.
        hybrid - which old groups had split/merge actions applied.
        unchanged - which old groups are the same as new groups.

    Example:
        >>> # ENABLE_DOCTEST
        >>> from utool.util_alg import *  # NOQA
        >>> import utool as ut
        >>> old = [
        >>>     [20, 21, 22, 23], [1, 2], [12], [13, 14], [3, 4], [5, 6,11],
        >>>     [7], [8, 9], [10], [31, 32], [33, 34, 35], [41, 42, 43, 44, 45]
        >>> ]
        >>> new = [
        >>>   [20, 21], [22, 23], [1, 2], [12, 13, 14], [4], [5, 6, 3], [7, 8],
        >>>   [9, 10, 11], [31, 32, 33, 34, 35],   [41, 42, 43, 44], [45],
        >>> ]
        >>> delta = ut.grouping_delta(old, new)
        >>> assert set(old[0]) in delta['splits']['old']
        >>> assert set(new[3]) in delta['merges']['new']
        >>> assert set(old[1]) in delta['unchanged']
        >>> result = ut.repr4(delta, nl=2, nobr=True, sk=True)
        >>> print(result)
        unchanged: {
            {1, 2},
        },
        splits: {
            old: [{20, 21, 22, 23}, {41, 42, 43, 44, 45}],
            new: [{{20, 21}, {22, 23}}, {{41, 42, 43, 44}, {45}}],
        },
        merges: {
            old: [{{12}, {13, 14}}, {{31, 32}, {33, 34, 35}}],
            new: [{12, 13, 14}, {31, 32, 33, 34, 35}],
        },
        hybrid: {
            old: {{10}, {3, 4}, {5, 6, 11}, {7}, {8, 9}},
            new: {{3, 5, 6}, {4}, {7, 8}, {9, 10, 11}},
            splits: [{{7}}, {{11}, {5, 6}}, {{10}}, {{3}, {4}}, {{8}, {9}}],
            merges: [{{7}, {8}}, {{4}}, {{3}, {5, 6}}, {{10}, {11}, {9}}],
        },


    Example:
        >>> # ENABLE_DOCTEST
        >>> from utool.util_alg import *  # NOQA
        >>> import utool as ut
        >>> old = [
        >>>     [1, 2, 3], [4], [5, 6, 7, 8, 9], [10, 11, 12]
        >>> ]
        >>> new = [
        >>>     [1], [2], [3, 4], [5, 6, 7], [8, 9, 10, 11, 12]
        >>> ]
        >>> # every case here is hybrid
        >>> pure_delta = ut.grouping_delta(old, new, pure=True)
        >>> assert len(ut.flatten(pure_delta['merges'].values())) == 0
        >>> assert len(ut.flatten(pure_delta['splits'].values())) == 0
        >>> delta = ut.grouping_delta(old, new, pure=False)
        >>> delta = ut.order_dict_by(delta, ['unchanged', 'splits', 'merges'])
        >>> result = ut.repr4(delta, nl=2, sk=True)
        >>> print(result)
        {
            unchanged: {},
            splits: [
                [{2}, {3}, {1}],
                [{8, 9}, {5, 6, 7}],
            ],
            merges: [
                [{4}, {3}],
                [{8, 9}, {10, 11, 12}],
            ],
        }
    """
    import utool as ut
    _old = {frozenset(_group) for _group in old}
    _new = {frozenset(_group) for _group in new}

    _new_items = set(ut.flatten(_new))
    _old_items = set(ut.flatten(_old))
    assert _new_items == _old_items, 'new and old sets must be the same'

    # Find the groups that are exactly the same
    unchanged = _new.intersection(_old)

    new_sets = _new.difference(unchanged)
    old_sets = _old.difference(unchanged)

    # connected compoment lookups
    old_conn = {p: frozenset(ps) for ps in _old for p in ps}
    new_conn = {t: frozenset(ts) for ts in _new for t in ts}

    # How many old sets can be merged into perfect pieces?
    # For each new sets, find if it can be made via merging old sets
    old_merges = []
    new_merges = []
    for ts in new_sets:
        ccs = set([old_conn.get(t, frozenset()) for t in ts])
        if frozenset.union(*ccs) == ts:
            # This is a pure merge
            old_merges.append(ccs)
            new_merges.append(ts)

    # How many oldictions can be split into perfect pieces?
    new_splits = []
    old_splits = []
    for ps in old_sets:
        ccs = set([new_conn.get(p, frozenset()) for p in ps])
        if frozenset.union(*ccs) == ps:
            # This is a pure merge
            new_splits.append(ccs)
            old_splits.append(ps)

    old_merges_flat = ut.flatten(old_merges)
    new_splits_flat = ut.flatten(new_splits)

    old_hybrid = frozenset(map(frozenset, old_sets)).difference(
        set(old_splits + old_merges_flat))

    new_hybrid = frozenset(map(frozenset, new_sets)).difference(
        set(new_merges + new_splits_flat))

    breakup_hybrids = True
    if breakup_hybrids:
        # First split each hybrid
        lookup = {a: n for n, items in enumerate(new_hybrid) for a in items}
        hybrid_splits = []
        for items in old_hybrid:
            nids = ut.take(lookup, items)
            split_part = list(ut.group_items(items, nids).values())
            hybrid_splits.append(set(map(frozenset, split_part)))

        # And then merge them into new groups
        hybrid_merge_parts = ut.flatten(hybrid_splits)
        part_nids = [lookup[next(iter(aids))] for aids in hybrid_merge_parts]
        hybrid_merges = list(map(set, ut.group_items(hybrid_merge_parts,
                                                     part_nids).values()))

    if pure:
        delta = ut.odict()
        delta['unchanged'] = unchanged
        delta['splits'] = ut.odict([
            ('old', old_splits),
            ('new', new_splits),
        ])
        delta['merges'] = ut.odict([
            ('old', old_merges),
            ('new', new_merges),
        ])
        delta['hybrid'] = ut.odict([
            ('old', old_hybrid),
            ('new', new_hybrid),
            ('splits', hybrid_splits),
            ('merges', hybrid_merges),
        ])
    else:
        # Incorporate hybrid partial cases with pure splits and merges
        new_splits2 = [s for s in hybrid_splits if len(s) > 1]
        old_merges2 = [m for m in hybrid_merges if len(m) > 1]
        all_new_splits = new_splits + new_splits2
        all_old_merges = old_merges + old_merges2

        # Don't bother differentiating old and new
        # old_splits2 = [frozenset(ut.flatten(s)) for s in new_splits2]
        # new_merges2 = [frozenset(ut.flatten(m)) for m in old_merges2]
        # all_old_splits = old_splits + old_splits2
        # all_new_merges = new_merges + new_merges2

        splits = all_new_splits
        merges = all_old_merges

        # Sort by split and merge sizes
        splits = ut.sortedby(splits, [len(ut.flatten(_)) for _ in splits])
        merges = ut.sortedby(merges, [len(ut.flatten(_)) for _ in merges])
        splits = [ut.sortedby(_, ut.emap(len, _)) for _ in splits]
        merges = [ut.sortedby(_, ut.emap(len, _)) for _ in merges]

        delta = ut.odict()
        delta['unchanged'] = unchanged
        delta['splits'] = splits
        delta['merges'] = merges
    return delta