javascript - Cómo filtrar múltiples propiedades de un array padre-hijo que podría tener varios niveles de árbol
TL;DR; Para hacerlo simple, ¿cómo puedo filtrar múltiples propiedades de un array padre-hijo que podría tener varios niveles de profundidad en el árbol? Esto es para una biblioteca de datagrid de código abierto utilizada por varios cientos de usuarios.
Así que tengo un array de referencias padre/hijo, los hijos también pueden tener hijos a su vez y así sucesivamente, no hay límite en la profundidad del nivel del árbol. Además, necesito poder filtrar no solo por la propiedad que tiene la estructura del árbol, sino por cualquier propiedad(s), que son columnas en una cuadrícula, de ese array.
Por ejemplo, tengo este arreglo, que está representando una lista del explorador de archivos
const myFiles = [
{id: 11, file: "Music", parentId: null },
{id: 12, file: "mp3", parentId: 11 },
{id: 14, file: "pop", parentId: 12 },
{id: 15, file: "theme.mp3", dateModified: "2015-03-01", size: 85, parentId: 14, },
{id: 16, file: "rock", parentId: 12 },
{id: 17, file: "soft.mp3", dateModified: "2015-05-13", size: 98, parentId: 16, },
{id: 18, file: "else.txt", dateModified: "2015-03-03", size: 90, parentId: null, },
{id: 21, file: "Documents", parentId: null, },
{id: 2, file: "txt", parentId: 21 },
{id: 3, file: "todo.txt", dateModified: "2015-05-12", size: 0.7, parentId: 2, },
{id: 4, file: "pdf", parentId: 21 },
{id: 22, file: "map2.pdf", dateModified: "2015-05-21", size: 2.9, parentId: 4 },
{id: 5, file: "map.pdf", dateModified: "2015-05-21", size: 3.1, parentId: 4, },
{id: 6, file: "internet-bill.pdf", dateModified: "2015-05-12", size: 1.4, parentId: 4, },
{id: 7, file: "xls", parentId: 21 },
{id: 8, file: "compilation.xls", dateModified: "2014-10-02", size: 2.3, parentId: 7, },
{id: 9, file: "misc", parentId: 21 },
{id: 10, file: "something.txt", dateModified: "2015-02-26", size: 0.4, parentId: 9, },
]
La matriz parece plana, pero en realidad, es una estructura de vista en árbol que se representa en un datagrid como se muestra a continuación.
Lo que encontré que funciona parcialmente es recorrer todo el array y agregar la lista completa de archivos que cada elemento puede tener, incluyendo a sí mismo. Por ejemplo, si Documents tiene un hijo PDF que a su vez tiene un hijo Map.pdf, entonces el mapeo del árbol se puede representar como ["Documents", "PDF", "map.pdf"] y lo almacenamos en el objeto padre; luego, en el siguiente hijo, almacenamos ["PDF", "map.pdf"] y finalmente, en el último hijo, almacenamos ["map.pdf"] así.
{id: 21, file: "Documents", parentId: null, treeMap: ["Documents", "PDF", "map.pdf"] }
{id: 4, file: "pdf", parentId: 21, treeMap: ["PDF", "map.pdf"] }
{id: 5, file: "map.pdf", dateModified: "2015-05-21", size: 3.1, parentId: 4, treeMap: ["map.pdf"] }
y este es el método que me permite hacer eso
export function modifyDatasetToAddTreeMapping(items: any[], treeViewColumn: Column, dataView: any) {
for (let i = 0; i < items.length; i++) {
items[i]['treeMap'] = [items[i][treeViewColumn.id]];
let item = items[i];
if (item['parentId'] !== null) {
let parent = dataView.getItemById(item['parentId']);
while (parent) {
parent['treeMap'] = dedupePrimitiveArray(parent['treeMap'].concat(item['treeMap']));
item = parent;
parent = dataView.getItemById(item['parentId']);
}
}
}
}
export function dedupePrimitiveArray(inputArray: Array<number | string>): Array<number | string> {
const seen = {};
const out = [];
const len = inputArray.length;
let j = 0;
for (let i = 0; i < len; i++) {
const item = inputArray[i];
if (seen[item] !== 1) {
seen[item] = 1;
out[j++] = item;
}
}
return out;
}
Luego la librería de datagrid utiliza el método Filter que puedo usar de esta manera, donde columnFilters es un objeto que contiene 1 o más filtros, por ejemplo const columnFilters={ file: 'map', size: '>3' }
El datagrid es una biblioteca (SlickGrid) y usa el método filter así: dataView.setFilter(treeFilter);
function treeFilter(dataView: any, item: any) {
const columnFilters = { file: this.searchString.toLowerCase(), size: 2 };
let filterCount = 0;
if (item[parentPropName] !== null) {
let parent = dataView.getItemById(item['parentId']);
while (parent) {
if (parent.__collapsed) {
return false;
}
parent = dataView.getItemById(parent['parentId']);
}
}
for (const columnId in columnFilters) {
if (columnId !== undefined && columnFilters[columnId] !== '') {
filterCount++;
if (item.treeMap === undefined || !item.treeMap.find((itm: string) => itm.endsWith(columnFilters[columnId]))) {
return false;
}
}
}
return true;
}
Con la llamada a modifyDatasetToAddTreeMapping() funciona bien si quiero filtrar por la columna Archivo, pero si agrego más filtros de columna, no funciona como se espera. Por ejemplo, si miras la segunda captura de pantalla, verás que ingresé "map" y eso mostrará "Documents > PDF > map.pdf" y eso está genial, pero si agrego un tamaño de archivo menor a 3Mb no debería mostrar "map.pdf" y como ese archivo no se muestra y "Documents > PDF" no contiene la palabra "map", entonces no debería mostrarse nada, así que como puedes ver el filtro no se está comportando como debería.
Entonces, con la implementación actual, tengo 2 problemas: 1. no se comporta correctamente cuando un nodo del árbol no se muestra, el padre de este no debería mostrarse 2. tener que llamar a modifyDatasetToAddTreeMapping() es una llamada adicional que podría no ser necesaria 3. también modifica el array de origen, podría clonar profundamente el array pero eso sería otro gasto adicional en rendimiento
Esto podría ser posible mediante recursión, después de convertir a una estructura jerárquica (árbol), pero no puedo averiguar el mejor algoritmo para hacer esto si es con recursión, ¿no es costoso siempre profundizar en el árbol para encontrar elementos?
Por último, la intención es usar esto con SlickGrid, que podría tener 10.000 o incluso 50.000 filas, por lo que tiene que ser rápido. Puedes ver esta demostración de SlickGrid, pero su implementación del filtrado no es correcta, además encontré el método para agregar el mapeo en esta otra respuesta de SO.
NOTA: También me gustaría señalar que una resolución a este problema beneficiará posiblemente a unos pocos cientos (o miles) de usuarios, ya que se implementará en Angular-Slickgrid y Aurelia-Slickgrid, que son ambas bibliotecas de código abierto y son utilizadas por al menos más de 300 usuarios.
Filtrar con la palabra "mapa" no debería devolver nada aquí, ya que ninguno de los nodos/hijos tiene ese texto.
EDITAR
El mejor código sería enchufar cualquier código que haga el trabajo en un filter de JS normal, lo que significa que la solución final sería un método myFilter que sería un método de callback de filter. La razón por la que estoy atascado con esto es porque uso una librería externa SlickGrid y tengo que usar lo que esa librería tiene disponible como métodos públicos expuestos.
function myFilter(item, args) {
const columnFilters = args.columnFilters;
// iterate through each items of the dataset
// return true/false on each item
}
// to be used as a drop in
dataView.setFilterArgs({ columnFilters: this._columnFilters });
dataView.setFilter(myFilter.bind(this));
Si tengo const columnFilters={ file: "map", size: "<3.2" };, el resultado esperado del arreglo sería de 4 líneas
// result
[
{id: 21, file: "Documents", parentId: null },
{id: 4, file: "pdf", parentId: 21, },
{id: 22, file: "map2.pdf", dateModified: "2015-05-21", size: 2.9, parentId: 4 },
{id: 5, file: "map.pdf", dateModified: "2015-05-21", size: 3.1, parentId: 4, }
]
Si tengo const columnFilters={ file: "map", size: "<3" };, el resultado esperado del arreglo sería 3 líneas
// result
[
{id: 21, file: "Documents", parentId: null },
{id: 4, file: "pdf", parentId: 21, },
{id: 22, file: "map2.pdf", dateModified: "2015-05-21", size: 2.9, parentId: 4 },
]
y finalmente, si tengo const columnFilters={ file: "map", size: ">3" };, entonces el resultado esperado sería un arreglo vacío porque ninguno de los archivos cumple con esa condición de carácter y de tamaño de archivo.
EDICIÓN 2
Según la respuesta de @AlexL, está empezando a funcionar. Solo un par de ajustes, pero ya parece muy prometedor
EDICIÓN 3
Gracias al increíble trabajo de Alex, su respuesta me ayudó a integrar esto en mi biblioteca de código abierto. Ahora tengo 2 demostraciones en vivo con referencia Padre/Hijo (conjunto de datos plano) y con un conjunto de datos jerárquico (conjunto de datos en árbol). Ojalá pudiera votar más de una vez :)
Respuesta #1
Tengo una forma de hacerlo. Debería ser bastante eficiente, pero también podríamos querer reemplazar map y reduce, etc., por los buenos y viejos bucles for para optimizar aún más la velocidad (he visto varios blogs y artículos comparando la velocidad de forEach, map, etc., con los bucles for y parece que los bucles for ganan)
Aquí hay una demostración (también aquí: https://codepen.io/Alexander9111/pen/abvojzN):
const myFiles = [
{ id: 11, file: "Music", parentId: null },
{ id: 12, file: "mp3", parentId: 11 },
{ id: 14, file: "pop", parentId: 12 },
{ id: 15, file: "theme.mp3", dateModified: "2015-03-01", size: 85, parentId: 14 },
{ id: 16, file: "rock", parentId: 12 },
{ id: 17, file: "soft.mp3", dateModified: "2015-05-13", size: 98, parentId: 16 },
{ id: 18, file: "else.txt", dateModified: "2015-03-03", size: 90, parentId: null },
{ id: 21, file: "Documents", parentId: null },
{ id: 2, file: "txt", parentId: 21 },
{ id: 3, file: "todo.txt", dateModified: "2015-05-12", size: 0.7, parentId: 2 },
{ id: 4, file: "pdf", parentId: 21 },
{ id: 22, file: "map2.pdf", dateModified: "2015-05-21", size: 2.9, parentId: 4 },
{ id: 5, file: "map.pdf", dateModified: "2015-05-21", size: 3.1, parentId: 4 },
{ id: 6, file: "internet-bill.pdf", dateModified: "2015-05-12", size: 1.4, parentId: 4 },
{ id: 7, file: "xls", parentId: 21 },
{ id: 8, file: "compilation.xls", dateModified: "2014-10-02", size: 2.3, parentId: 7 },
{ id: 9, file: "misc", parentId: 21 },
{ id: 10, file: "something.txt", dateModified: "2015-02-26", size: 0.4, parentId: 9 }
];
//example how to use the "<3" string - better way than using eval():
const columnFilters = { file: "map", size: "<3.2" }; //, size: "<3"
const isSizeValid = Function("return " + myFiles[11].size + "<3")();
//console.log(isSizeValid);
const myObj = myFiles.reduce((aggObj, child) => {
aggObj[child.id] = child;
//the filtered data is used again as each subsequent letter is typed
//we need to delete the ._used property, otherwise the logic below
//in the while loop (which checks for parents) doesn't work:
delete aggObj[child.id]._used;
return aggObj;
}, {});
function filterMyFiles(myArray, columnFilters){
const filteredChildren = myArray.filter(a => {
for (let key in columnFilters){
//console.log(key)
if (a.hasOwnProperty(key)){
const strContains = String(a[key]).includes(columnFilters[key]);
const re = /(?:(?:^|[-+<>=_*/])(?:\s*-?\d+(\.\d+)?(?:[eE][+-<>=]?\d+)?\s*))+$/;
const comparison = re.test(columnFilters[key]) && Function("return " + a[key] + columnFilters[key])();
if (strContains || comparison){
//don't return true as need to check other keys in columnFilters
}else{
//console.log('false', a)
return false;
}
} else{
return false;
}
}
//console.log('true', a)
return true;
})
return filteredChildren;
}
const initFiltered = filterMyFiles(myFiles, columnFilters);
const finalWithParents = initFiltered.map(child => {
const childWithParents = [child];
let parent = myObj[child.parentId];
while (parent){
//console.log('parent', parent)
parent._used || childWithParents.unshift(parent)
myObj[parent.id]._used = true;
parent = myObj[parent.parentId] || false;
}
return childWithParents;
}).flat();
console.log(finalWithParents).as-console-wrapper { max-height: 100% !important; top: 0; }Básicamente configura un objeto para usarlo más tarde para encontrar todos los padres.
Luego haz un filtro (es decir, una iteración del arreglo) y filtra aquellos que cumplan con las condiciones en el objeto columnFilters.
Luego mapea (es decir, una iteración) sobre este arreglo filtrado y encuentra cada padre usando el objeto creado al inicio (así que iteraciones anidadas hasta una profundidad N).
aplana el array con .flat() (se asume una iteración final) y luego hemos terminado.
Si tienen alguna pregunta, háganmelo saber.
Actualización - Enfoque de bucle for además de intentar reducir las iteraciones sobre el arreglo
Corta un par de iteraciones :) (https://codepen.io/Alexander9111/pen/MWagdVz):
const myFiles = [
{ id: 11, file: "Music", parentId: null },
{ id: 12, file: "mp3", parentId: 11 },
{ id: 14, file: "pop", parentId: 12 },
{ id: 15, file: "theme.mp3", dateModified: "2015-03-01", size: 85, parentId: 14 },
{ id: 16, file: "rock", parentId: 12 },
{ id: 17, file: "soft.mp3", dateModified: "2015-05-13", size: 98, parentId: 16 },
{ id: 18, file: "else.txt", dateModified: "2015-03-03", size: 90, parentId: null },
{ id: 21, file: "Documents", parentId: null },
{ id: 2, file: "txt", parentId: 21 },
{ id: 3, file: "todo.txt", dateModified: "2015-05-12", size: 0.7, parentId: 2 },
{ id: 4, file: "pdf", parentId: 21 },
{ id: 22, file: "map2.pdf", dateModified: "2015-05-21", size: 2.9, parentId: 4 },
{ id: 5, file: "map.pdf", dateModified: "2015-05-21", size: 3.1, parentId: 4 },
{ id: 6, file: "internet-bill.pdf", dateModified: "2015-05-12", size: 1.4, parentId: 4 },
{ id: 7, file: "xls", parentId: 21 },
{ id: 8, file: "compilation.xls", dateModified: "2014-10-02", size: 2.3, parentId: 7 },
{ id: 9, file: "misc", parentId: 21 },
{ id: 10, file: "something.txt", dateModified: "2015-02-26", size: 0.4, parentId: 9 }
];
const columnFilters = { file: "map", size: "<3.2" };
console.log(customLocalFilter(myFiles, columnFilters));
function customLocalFilter(array, filters){
const myObj = {};
for (let i = 0; i < myFiles.length; i++) {
myObj[myFiles[i].id] = myFiles[i];
//the filtered data is used again as each subsequent letter is typed
//we need to delete the ._used property, otherwise the logic below
//in the while loop (which checks for parents) doesn't work:
delete myObj[myFiles[i].id]._used;
}
const filteredChildrenAndParents = [];
for (let i = 0; i < myFiles.length; i++) {
const a = myFiles[i];
let matchFilter = true;
for (let key in columnFilters) {
if (a.hasOwnProperty(key)) {
const strContains = String(a[key]).includes(columnFilters[key]);
const re = /(?:(?:^|[-+<>!=_*/])(?:\s*-?\d+(\.\d+)?(?:[eE][+-<>!=]?\d+)?\s*))+$/;
const comparison =
re.test(columnFilters[key]) &&
Function("return " + a[key] + columnFilters[key])();
if (strContains || comparison) {
//don't return true as need to check other keys in columnFilters
} else {
matchFilter = false;
continue;
}
} else {
matchFilter = false;
continue;
}
}
if (matchFilter) {
const len = filteredChildrenAndParents.length;
filteredChildrenAndParents.splice(len, 0, a);
let parent = myObj[a.parentId] || false;
while (parent) {
//only add parent if not already added:
parent._used || filteredChildrenAndParents.splice(len, 0, parent);
//mark each parent as used so not used again:
myObj[parent.id]._used = true;
//try to find parent of the current parent, if exists:
parent = myObj[parent.parentId] || false;
}
}
}
return filteredChildrenAndParents;
}.as-console-wrapper { max-height: 100% !important; top: 0; }