Recursive function to add object into deeply nested array of objects adding into wrong object

user_17947523 0
Viewed 633

I have the following object structure

    layout: [
        {
            type: "FOLDER",
            id: "folder0",
            children: [

                {
                    type: "FILE",
                    id: "file0",
                },
                {
                    type: "FOLDER",
                    id: "folder00",
                    children: [
                        {
                            type: "FILE",
                            id: "file7",
                        }
                    ]
                },
                {
                    type: "FOLDER",
                    id: "folder02",
                    children: [
                        {
                            type: "FILE",
                            id: "file8",
                        }
                    ]
                }
            ]
        },

        {
            type: "FOLDER",
            id: "folder2",
            children: [
                {
                    type: "FILE",
                    id: "file4",
                }
            ]
        },
        {
            type: "FOLDER",
            id: "folder1",
            children: [
                {
                    type: "FILE",
                    id: "file2",
                },
                {
                    type: "FILE",
                    id: "file3",
                }
            ]
        },
        {
            type: "FILE",
            id: "file6",
        }


    ]

And I'm using the following code to add/remove/move which I took from this example

export const remove = (arr, index) => [
    // part of the array before the specified index
    ...arr.slice(0, index),
    // part of the array after the specified index
    ...arr.slice(index + 1)
];


export const removeChildFromChildren = (children, splitItemPath) => {
    if (splitItemPath.length === 1) {
        const itemIndex = Number(splitItemPath[0]);
        return remove(children, itemIndex);
    }

    const updatedChildren = [...children];

    const curIndex = Number(splitItemPath.slice(0, 1));

    // Update the specific node's children
    const splitItemChildrenPath = splitItemPath.slice(1);
    const nodeChildren = updatedChildren[curIndex];
    updatedChildren[curIndex] = {
        ...nodeChildren,
        children: removeChildFromChildren(
            nodeChildren.children,
            splitItemChildrenPath
        )
    };

    return updatedChildren;
};

export const insert = (arr, index, newItem) => {
    console.log("insideinsert", arr, index, newItem)
    return [
        // part of the array before the specified index
        ...arr.slice(0, index),
        // inserted item
        newItem,
        // part of the array after the specified index
        ...arr.slice(index)
    ];
}


export const addChildToChildren = (children, splitDropZonePath, item, targetid) => {

    if (splitDropZonePath.length === 1) {
        const dropZoneIndex = Number(splitDropZonePath[0]);
        return insert(children, dropZoneIndex, item);
    }



    const updatedChildren = [...children];
    const curIndex = Number(splitDropZonePath.slice(0, 1));
    const splitItemChildrenPath = splitDropZonePath.slice(1);
    const nodeChildren = updatedChildren[curIndex];
    updatedChildren[curIndex] = {
        ...nodeChildren,
        children: addChildToChildren(
            nodeChildren.children,
            splitItemChildrenPath,
            item
        )
    };
    return updatedChildren;
};

export const handleMoveToDifferentParent = (
    layout,
    splitDropZonePath,
    splitItemPath,
    item,
    targetid
) => {

    const removedfromlayout = removeChildFromChildren(layout, splitItemPath);
    return addChildToChildren(
        removedfromlayout,
        splitDropZonePath,
        item,
        targetid
    );
};

handleMoveToDifferentParent(layout, [0,2], [0,0], file0inobjectform)

But when I call this with the index paths. It moves file0 to folder02 instead of folder00 Is there a easier way to do this? I'm not sure how to insert by id as the index array also determines the order array.

dynamic-arrays multidimensional-array recursion javascript
1 Answers

Given immutable helper splice(a, k, trans) where -

  • a is the input array
  • k is the key (index) to update
  • trans is a function that receives the element at k and returns a replacement value
  • returns a new array with trans(a[k]) inserted at position k. Input a is not modified.
// splice :: ('a array, int, 'a -> 'a) -> 'a array
function splice(a, k, trans) {
  return a.slice(0, k).concat(trans(a[k])).concat(a.slice(k + 1))
}

And immutable helper extract(t, path) where -

  • t is a node from your tree in the shape of { id, type, children? }
  • path is an array of indexes
  • returns [selected, tprime] where selected is the node at the end of path and tprime is a new tree with selected removed from it. The input tree t is not mutated.

This implementation takes special care to follow only a valid path of indexes. extract will throw an error when trying to get the descendant of a FILE or when node.type is neither FOLDER nor FILE -

// extract :: ('a tree, int array) -> ('a, 'a tree)
function extract(t, path) {
  function loop(t, [i, ...path], cont) {
    if (i == null)
      return cont(t, _ => [])
    else switch (t?.type) {
      case "FOLDER":
        return loop(t.children[i], path, (selected, trans) =>
          cont(selected, a => ({ ...a, children: splice(a.children, i, trans) }))
        )
      case "FILE":
        throw Error(`cannot get descendant of file: ${JSON.stringify(t)}`)
      default:
        throw Error(`unsupported type: ${JSON.stringify(t)}`)
    }
  }
  return path.length == 0
    ? [undefined, t]
    : loop(t, path, (selected, trans) => [selected, trans(t)])
}

Given an input tree, mytree, note a root node was added so there is at most one root node -

const mytree = {
  id: "root",
  type: "FOLDER",
  children: [
    {
      id: "foo",
      type: "FOLDER",
      children: [
        { id: "foo1", type: "FILE" },
        { id: "foo2", type: "FILE" }
      ]
    },
    {
      id: "bar",
      type: "FOLDER",
      children: [
        { id: "bar1", type: "FILE" }
      ]
    }
  ]
}

Let's extract foo2 by following the indexes, [0,1]

const [selected, tprime] = extract(mytree, [0,1])
console.log("selected", selected)
console.log("new tree", tprime)

selected {
  id: "foo2",
  type: "FILE"
}

new tree {
  id: "root",
  type: "FOLDER",
  children: [
    {
      id: "foo",
      type: "FOLDER",
      children: [
        { id: "foo1", type: "FILE" }
      ]
    },
    {
      id: "bar",
      type: "FOLDER",
      children: [
        { id: "bar1", type: "FILE" }
      ]
    }
  ]
}

We could extract all of bar by selecting [1] -

const [selected, tprime] = extract(mytree, [1])
console.log("selected", selected)
console.log("new tree", tprime)

selected {
  id: "bar",
  type: "FOLDER",
  children: [
    { id: "bar1", type: "FILE" }
  ]
}

new tree {
  id: "root",
  type: "FOLDER",
  children: [
    {
      id: "foo",
      type: "FOLDER",
      children: [
        { id: "foo1", type: "FILE" },
        { id: "foo2", type: "FILE" }
      ]
    }
  ]
}

In just 26 lines of code, we already solved more than half of the problem. Node insertion is significantly easier and is left as an exercise for the reader -

function insert(t, path, node) {
  //...
}

function move(t, srcPath, destPath) {
  const [selectedNode, newTree] = extract(t, srcPath)
  return insert(newTree, destPath, selectedNode)
}

For a full demonstration of the code in this post, expand the snippet below and verify the result in your own browser -

function splice(a, k, trans) {
  return a.slice(0, k).concat(trans(a[k])).concat(a.slice(k + 1))
}

function extract(t, path) {
  function loop(t, [i, ...path], cont) {
    if (i == null)
      return cont(t, _ => [])
    else switch (t?.type) {
      case "FOLDER":
        return loop(t.children[i], path, (selected, trans) =>
          cont(selected, a => ({ ...a, children: splice(a.children, i, trans) }))
        )
      case "FILE":
        throw Error(`cannot get descendant of file: ${JSON.stringify(t)}`)
      default:
        throw Error(`unsupported type: ${JSON.stringify(t)}`)
    }
  }
  return path.length == 0
    ? [undefined, t]
    : loop(t, path, (selected, trans) => [selected, trans(t)])
}

const t = 
  { id: "root", type: "FOLDER", children: [
    { id: "foo", type: "FOLDER", children: [
      { id: "foo1", type: "FILE" },
      { id: "foo2", type: "FILE" }
    ]},
    { id: "bar", type: "FOLDER", children: [
      { id: "bar1", type: "FILE" }
    ]}
  ]}
  
const [selected, tprime] = extract(t, [0,0])
console.log("selected", selected)
console.log("new tree", tprime)

user_6331830
Related