Considere a seguinte matriz de objetos:
[
{v: 'a'},
{v: 'b'},
{v: 'c', ptr: 'b'},
{v: 'd', ptr: 'a'},
{v: 'e'},
]
Alguns dos objetos contêm uma ptrpropriedade, referenciando o vvalor da propriedade de um objeto que deve preceder diretamente. Dois objetos nunca tentarão preceder diretamente o mesmo objeto e nunca haverá um loop (por exemplo, a->b->c->a) no array.
Portanto, aqui estão dois possíveis rearranjos válidos dos objetos:
[
{v: 'e'},
{v: 'd', ptr: 'a'},
{v: 'a'},
{v: 'c', ptr: 'b'},
{v: 'b'},
]
[
{v: 'c', ptr: 'b'},
{v: 'b'},
{v: 'd', ptr: 'a'},
{v: 'a'},
{v: 'e'}
]
Não importa onde os objetos aparecem na saída, se não houver nenhuma ptrpropriedade que faça referência a eles. Tudo o que importa é que certos objetos precedam diretamente outros onde a ptrpropriedade o solicita.
Qual é um algoritmo razoavelmente eficiente para realizar esse tipo de rearranjo?
Embora seja garantido que os dados não contenham loops, o rearranjo deve ter cuidado para não entrar em um loop infinito onde fica reorganizando os objetos para sempre.
Observe que, embora esses exemplos usem strings para ve ptr, o aplicativo real envolverá elementos DOM como valores para ve ptrreferências. Portanto, a solução só deve ser capaz de comparar propriedades ve ptrigualdade.