Estoy tratando de ejecutar una migración de base de datos y me encontré con un problema cronológico. No puedo cambiar el comportamiento, así que tengo que lidiar con eso de alguna manera.
Supongamos que tengo la siguiente matriz,
const arr = [ { model: 'modelE', associations: ['modelA'], order: 1 }, { model: 'modelA', associations: [ 'modelB' ], order: 2 }, { model: 'modelB', associations: [], order: 3 }, { model: 'modelC', associations: ['modelA', 'modelB'], order: 4 }, { model: 'modelD', associations: ['modelA'], order: 5 }, { model: 'modelF', associations: [], order: 6 }, ]Como sabemos, tenemos que crear estas tablas en orden, de lo contrario no se pueden crear las claves foráneas y, por lo tanto, arrojará un error.
En este caso, tenemos modelE , modelC y modelD que dependen de modelA , pero modelA depende de modelB , por lo que modelB debe ser el primer elemento de esta matriz, porque tiene que ser la primera tabla que se cree.
La matriz resultante debería verse así:
const arr = [ { model: 'modelB', associations: [], order: 1 }, { model: 'modelF', associations: [], order: 2 }, { model: 'modelA', associations: [ 'modelB' ], order: 3 }, { model: 'modelC', associations: ['modelA', 'modelB'], order: 4 }, { model: 'modelE', associations: ['modelC'], order: 5 }, { model: 'modelD', associations: ['modelA'], order: 6 }, ] ¿Hay una manera efectiva de hacer esto? Todo lo que puedo pensar es ejecutar una función de sort con arr.find s dentro. No estoy seguro de si esto es demasiado eficaz o incluso legible.
const sortArrayByDependency = (arr) => { const sorted = []; const foundSet = new Set(); const maxLoop = arr.length; let loopCount = 0; while(arr.length > 0 && loopCount < maxLoop) { loopCount += 1; const first = arr.shift(); if(first.associations.every(ele => foundSet.has(ele))){ sorted.push({...first, order: sorted.length + 1 }); foundSet.add(first.model) } else { arr.push(first) } } return sorted; } const arr = [ { model: 'modelB', associations: [], order: 1 }, { model: 'modelF', associations: [], order: 2 }, { model: 'modelA', associations: [ 'modelB' ], order: 3 }, { model: 'modelC', associations: ['modelA', 'modelB'], order: 4 }, { model: 'modelE', associations: ['modelC'], order: 5 }, { model: 'modelD', associations: ['modelA'], order: 6 }, ] console.log(sortArrayByDependency(arr))Está buscando un ordenamiento topológico .
Puede usar un algoritmo de profundidad primero para eso:
function topoSort(arr) { const visited = new Set; const map = new Map(arr.map(({model, associations}) => [model, associations])); function dfs(models) { for (let model of models) { if (visited.has(model)) continue; dfs(map.get(model)); visited.add(model); } } dfs([...map.keys()]); return Array.from(visited, (model, i) => ({model, associations: map.get(model), order: i+1}) ); } const arr = [ { model: 'modelE', associations: ['modelA'], order: 1 }, { model: 'modelA', associations: [ 'modelB' ], order: 2 }, { model: 'modelB', associations: [], order: 3 }, { model: 'modelC', associations: ['modelA', 'modelB'], order: 4 }, { model: 'modelD', associations: ['modelA'], order: 5 }, { model: 'modelF', associations: [], order: 6 }, ] const result = topoSort(arr); console.log(...result);