broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(d):
    roots=[x for x in d['order'] if d['parents'].get(x)==d['parent']]
    key=lambda x:(False,(d['labels'].get(x) or '').casefold())
    ordered=sorted(roots,key=key,reverse=d['descending'])
    blocks={r:[x for x in d['order'] if x==r or r in d['ancestors'].get(x,[])] for r in roots}
    closure={x for block in blocks.values() for x in block}
    first=min((d['order'].index(x) for x in closure),default=len(d['order']))
    prefix=[x for x in d['order'][:first] if x not in closure]
    suffix=[x for x in d['order'][first:] if x not in closure]
    result=prefix+[x for r in ordered for x in blocks[r]]+suffix
    positions={x:i+1 for i,x in enumerate(ordered)}
    return [result,positions,d['focus'],d['selected'],d['expanded']]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {1: [('ascending', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'a', 'z', 'zz', 'zzz', 'b', 'q'], {'a': 1, 'z': 2, 'b': 3}, 'z', ['zzz'], ['r', 'z']]), ('descending', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': True, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('stable tie', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'SAME', 'a': 'same', 'b': 'other'}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('case fold', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'Straße', 'a': 'STRASSE', 'b': 'other'}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('empty siblings', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'absent', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {}, 'z', ['zzz'], ['r', 'z']]), ('empty label', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': '', 'a': 'X1', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {'z': 1, 'a': 2, 'b': 3}, 'z', ['zzz'], ['r', 'z']])], 2: [('ascending', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'a', 'z', 'zz', 'zzz', 'b', 'q'], {'a': 1, 'z': 2, 'b': 3}, 'z', ['zzz'], ['r', 'z']]), ('descending', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': True, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('stable tie', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'SAME', 'a': 'same', 'b': 'other'}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('case fold', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'Straße', 'a': 'STRASSE', 'b': 'other'}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('empty siblings', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'absent', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {}, 'z', ['zzz'], ['r', 'z']]), ('empty label', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': '', 'a': 'X2', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {'z': 1, 'a': 2, 'b': 3}, 'z', ['zzz'], ['r', 'z']])], 3: [('ascending', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'a', 'z', 'zz', 'zzz', 'b', 'q'], {'a': 1, 'z': 2, 'b': 3}, 'z', ['zzz'], ['r', 'z']]), ('descending', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': True, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('stable tie', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'SAME', 'a': 'same', 'b': 'other'}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('case fold', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'Straße', 'a': 'STRASSE', 'b': 'other'}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('empty siblings', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'absent', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {}, 'z', ['zzz'], ['r', 'z']]), ('empty label', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': '', 'a': 'X3', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {'z': 1, 'a': 2, 'b': 3}, 'z', ['zzz'], ['r', 'z']])], 4: [('ascending', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'a', 'z', 'zz', 'zzz', 'b', 'q'], {'a': 1, 'z': 2, 'b': 3}, 'z', ['zzz'], ['r', 'z']]), ('descending', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': True, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('stable tie', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'SAME', 'a': 'same', 'b': 'other'}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('case fold', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'Straße', 'a': 'STRASSE', 'b': 'other'}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('empty siblings', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'absent', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {}, 'z', ['zzz'], ['r', 'z']]), ('empty label', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': '', 'a': 'X4', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {'z': 1, 'a': 2, 'b': 3}, 'z', ['zzz'], ['r', 'z']])], 5: [('ascending', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'a', 'z', 'zz', 'zzz', 'b', 'q'], {'a': 1, 'z': 2, 'b': 3}, 'z', ['zzz'], ['r', 'z']]), ('descending', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': True, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('stable tie', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'SAME', 'a': 'same', 'b': 'other'}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('case fold', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'Straße', 'a': 'STRASSE', 'b': 'other'}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('empty siblings', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'absent', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {}, 'z', ['zzz'], ['r', 'z']]), ('empty label', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': '', 'a': 'X5', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {'z': 1, 'a': 2, 'b': 3}, 'z', ['zzz'], ['r', 'z']])]}
for label, data, expected in cases[N]:
    check(label, solve(data), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(d):
    roots=[x for x in d['order'] if d['parents'].get(x)==d['parent']]
    key=lambda x:(d['labels'].get(x) is not None,(d['labels'].get(x) or '').casefold())
    ordered=sorted(roots,key=key,reverse=d['descending'])
    blocks={r:[x for x in d['order'] if x==r or r in d['ancestors'].get(x,[])] for r in roots}
    closure={x for block in blocks.values() for x in block}
    first=min((d['order'].index(x) for x in closure),default=len(d['order']))
    prefix=[x for x in d['order'][:first] if x not in closure]
    suffix=[x for x in d['order'][first:] if x not in closure]
    result=prefix+[x for r in ordered for x in blocks[r]]+suffix
    positions={x:i+1 for i,x in enumerate(ordered)}
    return [result,positions,d['focus'],d['selected'],d['expanded']]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {1: [('ascending', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'a', 'z', 'zz', 'zzz', 'b', 'q'], {'a': 1, 'z': 2, 'b': 3}, 'z', ['zzz'], ['r', 'z']]), ('descending', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': True, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('stable tie', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'SAME', 'a': 'same', 'b': 'other'}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('case fold', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'Straße', 'a': 'STRASSE', 'b': 'other'}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('empty siblings', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'absent', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {}, 'z', ['zzz'], ['r', 'z']]), ('empty label', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': '', 'a': 'X1', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {'z': 1, 'a': 2, 'b': 3}, 'z', ['zzz'], ['r', 'z']])], 2: [('ascending', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'a', 'z', 'zz', 'zzz', 'b', 'q'], {'a': 1, 'z': 2, 'b': 3}, 'z', ['zzz'], ['r', 'z']]), ('descending', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': True, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('stable tie', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'SAME', 'a': 'same', 'b': 'other'}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('case fold', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'Straße', 'a': 'STRASSE', 'b': 'other'}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('empty siblings', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'absent', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {}, 'z', ['zzz'], ['r', 'z']]), ('empty label', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': '', 'a': 'X2', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {'z': 1, 'a': 2, 'b': 3}, 'z', ['zzz'], ['r', 'z']])], 3: [('ascending', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'a', 'z', 'zz', 'zzz', 'b', 'q'], {'a': 1, 'z': 2, 'b': 3}, 'z', ['zzz'], ['r', 'z']]), ('descending', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': True, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('stable tie', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'SAME', 'a': 'same', 'b': 'other'}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('case fold', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'Straße', 'a': 'STRASSE', 'b': 'other'}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('empty siblings', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'absent', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {}, 'z', ['zzz'], ['r', 'z']]), ('empty label', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': '', 'a': 'X3', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {'z': 1, 'a': 2, 'b': 3}, 'z', ['zzz'], ['r', 'z']])], 4: [('ascending', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'a', 'z', 'zz', 'zzz', 'b', 'q'], {'a': 1, 'z': 2, 'b': 3}, 'z', ['zzz'], ['r', 'z']]), ('descending', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': True, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('stable tie', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'SAME', 'a': 'same', 'b': 'other'}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('case fold', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'Straße', 'a': 'STRASSE', 'b': 'other'}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('empty siblings', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'absent', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {}, 'z', ['zzz'], ['r', 'z']]), ('empty label', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': '', 'a': 'X4', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {'z': 1, 'a': 2, 'b': 3}, 'z', ['zzz'], ['r', 'z']])], 5: [('ascending', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'a', 'z', 'zz', 'zzz', 'b', 'q'], {'a': 1, 'z': 2, 'b': 3}, 'z', ['zzz'], ['r', 'z']]), ('descending', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': True, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('stable tie', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'SAME', 'a': 'same', 'b': 'other'}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('case fold', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'Straße', 'a': 'STRASSE', 'b': 'other'}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('empty siblings', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'absent', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {}, 'z', ['zzz'], ['r', 'z']]), ('empty label', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': '', 'a': 'X5', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {'z': 1, 'a': 2, 'b': 3}, 'z', ['zzz'], ['r', 'z']])]}
for label, data, expected in cases[N]:
    check(label, solve(data), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

prompt:
Unlabelled sibling sorts before labelled siblings produces the wrong hierarchical widget state in a regression fixture.

Only direct children of the target parent are sorted by casefolded display label, with original order retained on ties; each child subtree moves as one block. Missing labels sort last in ascending order; descending reverses the complete comparison order. Focus, selection and expansion remain ID-based; sibling positions are recomputed from sorted roots.

split: open-access


broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(d):
    roots=[x for x in d['order'] if d['parents'].get(x)==d['parent']]
    key=lambda x:(d['labels'].get(x) is None,d['labels'].get(x) or '')
    ordered=sorted(roots,key=key,reverse=d['descending'])
    blocks={r:[x for x in d['order'] if x==r or r in d['ancestors'].get(x,[])] for r in roots}
    closure={x for block in blocks.values() for x in block}
    first=min((d['order'].index(x) for x in closure),default=len(d['order']))
    prefix=[x for x in d['order'][:first] if x not in closure]
    suffix=[x for x in d['order'][first:] if x not in closure]
    result=prefix+[x for r in ordered for x in blocks[r]]+suffix
    positions={x:i+1 for i,x in enumerate(ordered)}
    return [result,positions,d['focus'],d['selected'],d['expanded']]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {1: [('ascending', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'a', 'z', 'zz', 'zzz', 'b', 'q'], {'a': 1, 'z': 2, 'b': 3}, 'z', ['zzz'], ['r', 'z']]), ('descending', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': True, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('stable tie', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'SAME', 'a': 'same', 'b': 'other'}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('case fold', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'Straße', 'a': 'STRASSE', 'b': 'other'}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('empty siblings', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'absent', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {}, 'z', ['zzz'], ['r', 'z']]), ('empty label', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': '', 'a': 'X1', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {'z': 1, 'a': 2, 'b': 3}, 'z', ['zzz'], ['r', 'z']])], 2: [('ascending', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'a', 'z', 'zz', 'zzz', 'b', 'q'], {'a': 1, 'z': 2, 'b': 3}, 'z', ['zzz'], ['r', 'z']]), ('descending', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': True, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('stable tie', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'SAME', 'a': 'same', 'b': 'other'}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('case fold', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'Straße', 'a': 'STRASSE', 'b': 'other'}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('empty siblings', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'absent', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {}, 'z', ['zzz'], ['r', 'z']]), ('empty label', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': '', 'a': 'X2', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {'z': 1, 'a': 2, 'b': 3}, 'z', ['zzz'], ['r', 'z']])], 3: [('ascending', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'a', 'z', 'zz', 'zzz', 'b', 'q'], {'a': 1, 'z': 2, 'b': 3}, 'z', ['zzz'], ['r', 'z']]), ('descending', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': True, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('stable tie', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'SAME', 'a': 'same', 'b': 'other'}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('case fold', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'Straße', 'a': 'STRASSE', 'b': 'other'}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('empty siblings', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'absent', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {}, 'z', ['zzz'], ['r', 'z']]), ('empty label', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': '', 'a': 'X3', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {'z': 1, 'a': 2, 'b': 3}, 'z', ['zzz'], ['r', 'z']])], 4: [('ascending', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'a', 'z', 'zz', 'zzz', 'b', 'q'], {'a': 1, 'z': 2, 'b': 3}, 'z', ['zzz'], ['r', 'z']]), ('descending', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': True, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('stable tie', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'SAME', 'a': 'same', 'b': 'other'}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('case fold', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'Straße', 'a': 'STRASSE', 'b': 'other'}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('empty siblings', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'absent', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {}, 'z', ['zzz'], ['r', 'z']]), ('empty label', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': '', 'a': 'X4', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {'z': 1, 'a': 2, 'b': 3}, 'z', ['zzz'], ['r', 'z']])], 5: [('ascending', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'a', 'z', 'zz', 'zzz', 'b', 'q'], {'a': 1, 'z': 2, 'b': 3}, 'z', ['zzz'], ['r', 'z']]), ('descending', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': True, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('stable tie', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'SAME', 'a': 'same', 'b': 'other'}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('case fold', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'Straße', 'a': 'STRASSE', 'b': 'other'}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('empty siblings', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'absent', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {}, 'z', ['zzz'], ['r', 'z']]), ('empty label', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': '', 'a': 'X5', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {'z': 1, 'a': 2, 'b': 3}, 'z', ['zzz'], ['r', 'z']])]}
for label, data, expected in cases[N]:
    check(label, solve(data), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

meaning: Fixture-count band, not measured model difficulty

deps: stdlib

source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(d):
    roots=[x for x in d['order'] if d['parents'].get(x)==d['parent']]
    key=lambda x:(d['labels'].get(x) is None,(d['labels'].get(x) or '').lower())
    ordered=sorted(roots,key=key,reverse=d['descending'])
    blocks={r:[x for x in d['order'] if x==r or r in d['ancestors'].get(x,[])] for r in roots}
    closure={x for block in blocks.values() for x in block}
    first=min((d['order'].index(x) for x in closure),default=len(d['order']))
    prefix=[x for x in d['order'][:first] if x not in closure]
    suffix=[x for x in d['order'][first:] if x not in closure]
    result=prefix+[x for r in ordered for x in blocks[r]]+suffix
    positions={x:i+1 for i,x in enumerate(ordered)}
    return [result,positions,d['focus'],d['selected'],d['expanded']]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {1: [('ascending', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'a', 'z', 'zz', 'zzz', 'b', 'q'], {'a': 1, 'z': 2, 'b': 3}, 'z', ['zzz'], ['r', 'z']]), ('descending', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': True, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('stable tie', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'SAME', 'a': 'same', 'b': 'other'}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('case fold', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'Straße', 'a': 'STRASSE', 'b': 'other'}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('empty siblings', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'absent', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {}, 'z', ['zzz'], ['r', 'z']]), ('empty label', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': '', 'a': 'X1', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {'z': 1, 'a': 2, 'b': 3}, 'z', ['zzz'], ['r', 'z']])], 2: [('ascending', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'a', 'z', 'zz', 'zzz', 'b', 'q'], {'a': 1, 'z': 2, 'b': 3}, 'z', ['zzz'], ['r', 'z']]), ('descending', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': True, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('stable tie', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'SAME', 'a': 'same', 'b': 'other'}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('case fold', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'Straße', 'a': 'STRASSE', 'b': 'other'}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('empty siblings', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'absent', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {}, 'z', ['zzz'], ['r', 'z']]), ('empty label', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': '', 'a': 'X2', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {'z': 1, 'a': 2, 'b': 3}, 'z', ['zzz'], ['r', 'z']])], 3: [('ascending', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'a', 'z', 'zz', 'zzz', 'b', 'q'], {'a': 1, 'z': 2, 'b': 3}, 'z', ['zzz'], ['r', 'z']]), ('descending', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': True, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('stable tie', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'SAME', 'a': 'same', 'b': 'other'}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('case fold', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'Straße', 'a': 'STRASSE', 'b': 'other'}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('empty siblings', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'absent', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {}, 'z', ['zzz'], ['r', 'z']]), ('empty label', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': '', 'a': 'X3', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {'z': 1, 'a': 2, 'b': 3}, 'z', ['zzz'], ['r', 'z']])], 4: [('ascending', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'a', 'z', 'zz', 'zzz', 'b', 'q'], {'a': 1, 'z': 2, 'b': 3}, 'z', ['zzz'], ['r', 'z']]), ('descending', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': True, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('stable tie', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'SAME', 'a': 'same', 'b': 'other'}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('case fold', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'Straße', 'a': 'STRASSE', 'b': 'other'}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('empty siblings', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'absent', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {}, 'z', ['zzz'], ['r', 'z']]), ('empty label', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': '', 'a': 'X4', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {'z': 1, 'a': 2, 'b': 3}, 'z', ['zzz'], ['r', 'z']])], 5: [('ascending', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'a', 'z', 'zz', 'zzz', 'b', 'q'], {'a': 1, 'z': 2, 'b': 3}, 'z', ['zzz'], ['r', 'z']]), ('descending', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': True, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('stable tie', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'SAME', 'a': 'same', 'b': 'other'}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('case fold', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'Straße', 'a': 'STRASSE', 'b': 'other'}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('empty siblings', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'absent', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {}, 'z', ['zzz'], ['r', 'z']]), ('empty label', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': '', 'a': 'X5', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {'z': 1, 'a': 2, 'b': 3}, 'z', ['zzz'], ['r', 'z']])]}
for label, data, expected in cases[N]:
    check(label, solve(data), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

prompt:
Sibling label comparison ignores stipulated casefold equivalence produces the wrong hierarchical widget state in a regression fixture.

Only direct children of the target parent are sorted by casefolded display label, with original order retained on ties; each child subtree moves as one block. Missing labels sort last in ascending order; descending reverses the complete comparison order. Focus, selection and expansion remain ID-based; sibling positions are recomputed from sorted roots.

split: open-access