how to delete objects by recursion?-CodePudding

I ran into a problem that I don’t know how to correctly compose a recursive function. the logic is such that if you delete an item in the application, then all items whose parentId is equal to the id of the item that decided to delete are deleted, and so on. I hope I explained well, I will be very grateful for the help!

const arr = [
    {title: 'one', id: 1, parentId: null},
    {title: 'two', id: 2, parentId: 1},
    {title: 'three', id: 3, parentId: null},
    {title: 'four', id: 4, parentId: 2},
    {title: 'five', id: 5, parentId: 2},
    {title: 'six', id: 6, parentId: 5},
    {title: 'seven', id: 7, parentId: 3},
]
// if we decide to remove "one", the result will be
[
    {title: 'three', id: 3, parentId: null},
    {title: 'seven', id: 7, parentId: 3},
]

I'm stuck on a version that removes subtasks with only one parentId level

const deleteFunc = (array, value) => {
    array = array.filter(item => item.id !== value);
  const findSubTask = array.filter((item) => item.parentId === value);
  array = array.filter(item => item.id !== findSubTask[0].id);

  const findSecondSubTask = array.find(
    (key) => key.parentId === findSubTask[0].id,
  );

  if (findSecondSubTask) {
    return deleteFunc(array, findSubTask[0].id);
  }
  return array;
};

console.log(deleteFunc(arr, 1));

CodePudding user response：

Get the IDs of all the descendants of the starting element using a recursive function. Then remove them.

const arr = [
    {title: 'one', id: 1, parentId: null},
    {title: 'two', id: 2, parentId: 1},
    {title: 'three', id: 3, parentId: null},
    {title: 'four', id: 4, parentId: 2},
    {title: 'five', id: 5, parentId: 2},
    {title: 'six', id: 6, parentId: 5},
    {title: 'seven', id: 7, parentId: 3},
];

function getDescendantIds(id, arr) {
  let result = [id];
  arr.forEach(el => {
    if (el.parentId == id) {
      result = result.concat(getDescendantIds(el.id, arr));
    }
  });
  return result;
}

function removeTitleAndDescendants(title, arr) {
  let start = arr.find(el => el.title == title);
  if (start) {
    let allIds = new Set(getDescendantIds(start.id, arr));
    return arr.filter(el => !allIds.has(el.id));
  }
  return [...arr];
}

let result = removeTitleAndDescendants("one", arr);
console.log(result);

console.config({
    maxEntries: Infinity
});

CodePudding user response：

There are definitely a number of approaches to this question. You could go ahead and keep a dictionary that will map parent IDs -> Items, so that you could easily perform what you're triyng to do here in a an efficient manner.

Despite that, if we are looking specifically for a javascript solution, I'd try something along the lines of:

const arr = [
    {title: 'one', id: 1, parentId: null},
    {title: 'two', id: 2, parentId: 1},
    {title: 'three', id: 3, parentId: null},
    {title: 'four', id: 4, parentId: 2},
    {title: 'five', id: 5, parentId: 2},
    {title: 'six', id: 6, parentId: 5},
    {title: 'seven', id: 7, parentId: 3},
]

function deleteFromList(titleToDelete) {
  deletedList = [];
  itemToDeleteIdx = arr.indexOf(i=>i.title === titleToDelete);
  if(itemToDeleteIdx !== -1){
  deletedList.push(arr[itemToDeleteIdx]);
  arr.splice(itemToDeleteIdx, 1);
  return deleteRecursive(deleteRecursive[0].parentId, deletedList);
  } else {
  return [];
  }
}

function deleteRecursive(parentIdToDelete, deletedItemsList){
  itemToDeleteIdx = arr.indexOf(i=>i.parentId === parentIdToDelete);
  if(itemToDeleteIdx !== -1){
    deletedItemsList.push(arr[itemToDeleteIdx]);
    arr.splice(itemToDeleteIdx, 1); 
    return deleteRecursive(parentIdToDelete, deletedItemsList)
  }
  else {
    return deletedItemsList;
  }
}

console.log(deleteFromList('three'))

Obviously it's missing a lot of validations and corner cases, but that's the main flow of things.

CodePudding user response：

The function you see below takes an array of item ids you want to delete so at the beginning you give an array with the id of the item you want to delete. then it does two simple tasks: delete items in the passed array, find the ids of all items which has the previous item as their parentId and add them to an array you pass to the next call and so on.

function deleteItems(arrIds) {

  if(arrIds.length === 0) return;

  arr = arr.filter((item) => !arrIds.includes(item.id));
  const newIds = [];
  arr.forEach((item) => {
    if(arrIds.includes(item.parentId)) newIds.push(item.id);
  })
  deleteItems(newIds);
};

deleteItems([1]);

CodePudding user response：

Let's convert to a tree:

const arr = [
    {title: 'one', id: 1, parentId: null},
    {title: 'two', id: 2, parentId: 1},
    {title: 'three', id: 3, parentId: null},
    {title: 'four', id: 4, parentId: 2},
    {title: 'five', id: 5, parentId: 2},
    {title: 'six', id: 6, parentId: 5},
    {title: 'seven', id: 7, parentId: 3},
];

var grouped = arr.reduce(function(agg, item) {
  agg[item.id] = item
  return agg;
}, {})

arr.forEach(function(item) {
  if (item.parentId) {
    grouped[item.parentId].children ??= []
    grouped[item.parentId].children.push(item.id)
  }
})

// this is our tree
console.log(grouped)

// now we can:
function get_children_deep(tree, id) {
  var result = [];
  function iterate(tree, id) {
    var obj = tree[id];
    (obj.children || []).forEach(function(child_id) {
      result.push(child_id);
      iterate(tree, child_id);
    })
  }
  iterate(tree, id)
  return result;
}


console.log("all descendants of 1: "   get_children_deep(grouped, 1))

.as-console-wrapper {max-height: 100% !important}

So based on that, here's the solution of deleting item and children by title. recursively.

const arr = [
    {title: 'one', id: 1, parentId: null},
    {title: 'two', id: 2, parentId: 1},
    {title: 'three', id: 3, parentId: null},
    {title: 'four', id: 4, parentId: 2},
    {title: 'five', id: 5, parentId: 2},
    {title: 'six', id: 6, parentId: 5},
    {title: 'seven', id: 7, parentId: 3},
];

console.log(delete_by_title(arr, "one"));


function delete_by_title(arr, title) {

  var grouped = arr.reduce(function(agg, item) {
    agg[item.id] = item
    return agg;
  }, {})

  arr.forEach(function(item) {
    if (item.parentId) {
      grouped[item.parentId].children ??= []
      grouped[item.parentId].children.push(item.id)
    }
  })


  function get_children_deep(tree, id) {
    var result = [];

    function iterate(tree, id) {
      var obj = tree[id];
      (obj.children || []).forEach(function(child_id) {
        result.push(child_id);
        iterate(tree, child_id);
      })
    }
    iterate(tree, id)
    return result;
  }

  function id_by_title(arr, title) {
    return arr.find(function(item) {
      return item.title == title
    }).id;
  }

  var id = id_by_title(arr, title)
  var to_delete = get_children_deep(grouped, id)
  to_delete.push(id)

  to_delete.forEach(function(id) {
    delete grouped[id]
  })

  return Object.values(grouped);
}

CodePudding user response：

if you want to return them then the below should do the trick

const arr = [
    {title: 'one', id: 1, parentId: null},
    {title: 'two', id: 2, parentId: 1},
    {title: 'three', id: 3, parentId: null},
    {title: 'four', id: 4, parentId: 2},
    {title: 'five', id: 5, parentId: 2},
    {title: 'six', id: 6, parentId: 5},
    {title: 'seven', id: 7, parentId: 3},
]

const deleteId = (val) => {
const resultArray = [];
const index = arr.findIndex((n) => n.id === val);
for(let i =0; i < arr.length; i  )
{
  if(arr[i].id === val || arr[i].parentId === arr[index].id)
  {
  resultArray.push(arr[i]);
  }
}
return resultArray;
}

const result = deleteId(1);

console.log(result);

CodePudding user response：

Essentially the same idea as @Barmar, but done in a different way :)

const arr = [
    {title: 'one', id: 1, parentId: null},
    {title: 'two', id: 2, parentId: 1},
    {title: 'three', id: 3, parentId: null},
    {title: 'four', id: 4, parentId: 2},
    {title: 'five', id: 5, parentId: 2},
    {title: 'six', id: 6, parentId: 5},
    {title: 'seven', id: 7, parentId: 3},
];

function cascadingDelete(arr, title) {
    const index = arr.findIndex((e) => e.title === title);
    
    const indices = [index].concat((function walk(parentId) {
        const children = arr.filter((e) => e.parentId === parentId);
        const indices = children.map((c) => arr.indexOf(c));
        return indices.concat(children.map((c) => walk(c.id)));
    })(arr[index].id)).flat(Infinity);
    
    return arr.filter((_, i) => !indices.includes(i));
}

console.log(cascadingDelete(arr, "one"));