Home > OS >  How to modify a nested parent-object child-array data-structure by its `full` property value
How to modify a nested parent-object child-array data-structure by its `full` property value

Time:06-16

I have This object:

var tree = {
  name: "Documents",
  type: "dir",
  full: "/home/adityam/Documents",
  children: [
    {
      name: "file.txt",
      type: "file",
      full: "/home/adityam/Documents/file.txt",
    },
    {
      name: "anotherFolder",
      type: "dir",
      full: "/home/adityam/Documents/anotherFolder",
      children: [...]
    }
  ]
}

now the elements in this object might not be same on every user's computer because these are dynamically generated.

now i have a element somewhere inside this object like this:

var element = {
  name: "anotherFolder",
  type: "dir",
  full: "/home/adityam/Documents/anotherFolder",
  children: [...]
}

and i want to change the property "children" of this element, how do i do it?

also one thing to note that the element i have, is always bound to exist in the object, which means there's no way that element won't be inside that object.

tho every object has a structure:

var tree = {
  name: "Some Folder Name",
  type: "dir",
  full: "full path of the element",
  children: [...]
}

if the property type is dir then the element will have a children property, which might be a empty array or a array containing more elements like these.

CodePudding user response:

Searching for the node

Recursion!

You can find a reference for such a tree node with a recursive (search) function:

All recursive algorithms must obey three important laws:

  1. A recursive algorithm must call itself, recursively.
  2. A recursive algorithm must have a base case.
  3. A recursive algorithm must change its state and move toward the base case.

For example findNodeRecursive(name, node):

  1. If property full of node equals name, return node. (Base case: Found)
  2. If property type of node is not "dir", return null. (Base case: Cannot be inside)
  3. For each element childNode of property children of node: (Moving toward some base case)
    1. Let result be the result of the call findNodeRecursive(name, childNode). (Recursive call)
    2. If result is not null, return result. (Base case: Found in children)
  4. Return null. (Base case: Not found)

// Implementation of the algorithm above
function findNodeRecursive(fullName, node) {
  if (node.full === fullName) return node;
  if (node.type !== "dir") return null;
  
  for (const childNode of node.children) {
    const result = findNodeRecursive(fullName, childNode);
    if (result !== null) return result;
  }
  
  return null;
}

const tree = {
  name: "Documents",
  type: "dir",
  full: "/home/adityam/Documents",
  children: [
    {
      name: "file.txt",
      type: "file",
      full: "/home/adityam/Documents/file.txt",
    },
    {
      name: "anotherFolder",
      type: "dir",
      full: "/home/adityam/Documents/anotherFolder",
      children: []
    }
  ]
};

console.log(findNodeRecursive("/home/adityam/Documents/anotherFolder", tree));

Iteratively

There is also an iterative solution, which requires flattening the tree to a flat array, and then search for the node by its name.

Flattening can be done in multiple ways, either recursively again, or iteratively.

function findNodeIterative(name, node) {
  const nodes = [node];
  
  // Iterative flattening
  for (let i = 0; i < nodes.length;   i) {
    if (nodes[i].children) nodes.push(...nodes[i].children);
  }
  
  return nodes.find(n => n.full === name);
}

const tree = {
  name: "Documents",
  type: "dir",
  full: "/home/adityam/Documents",
  children: [
    {
      name: "file.txt",
      type: "file",
      full: "/home/adityam/Documents/file.txt",
    },
    {
      name: "anotherFolder",
      type: "dir",
      full: "/home/adityam/Documents/anotherFolder",
      children: []
    }
  ]
};

console.log(findNodeIterative("/home/adityam/Documents/anotherFolder", tree));

Modifying children

The value of children is an array. If you want to modify this array, you can use one of its mutating methods, for example Array.splice().

// Reference found with some function, for example the above findByName()
const node = {
  name: "anotherFolder",
  type: "dir",
  full: "/home/adityam/Documents/anotherFolder",
  children: []
};

const nodesToAdd = [
  {
    name: "someFile.txt",
    type: "file",
    full: "/home/adityam/Documents/anotherFolder/someFile.txt"
  },
  {
    name: "someFolder",
    type: "dir",
    full: "/home/adityam/Documents/anotherFolder/someFolder",
    children: []
  }
];

console.log("Before modifying:\nNode:", node);
node.children.splice(0, 0, ...nodesToAdd);
console.log("After modifying:\nNode:", node);
.as-console-wrapper{max-height:unset!important;top:0}

CodePudding user response:

explanation in progress

function recursivelyFindArrayItemByProperties(type, finder) {
  const { arrKey, props } = finder;

  if (Array.isArray(type)) {
    type
      // find will exit early.
      .find(item =>
        !!recursivelyFindArrayItemByProperties(item, finder)
      );
  } else if (type && ('object' === typeof type)) {
    if (
      Object
        .entries(props)
        .every(([key, value]) => type[key] === value)
    ) {
      finder.match = type;
    } else {
      recursivelyFindArrayItemByProperties(type[arrKey], finder);
    }    
  }
  return finder.match;
}

const tree = {
  name: "Documents",
  type: "dir",
  full: "/home/adityam/Documents",
  children: [{
    name: "file.txt",
    type: "file",
    full: "/home/adityam/Documents/file.txt",
  }, {
    name: "anotherFolder",
    type: "dir",
    full: "/home/adityam/Documents/anotherFolder",
    children: [{
      name: "fooBar.txt",
      type: "file",
      full: "/home/adityam/Documents/fooBar.txt",
    }, {
      name: "bazBiz.txt",
      type: "file",
      full: "/home/adityam/Documents/bazBiz.txt",
    }],
  }],
};

console.log(
  'found by ... { full: "/home/adityam/Documents/fooBar.txt" } ... ',
  recursivelyFindArrayItemByProperties(tree, {
    arrKey: 'children',
    props: {
      full: "/home/adityam/Documents/fooBar.txt",
    },
  })
);
console.log(
  'found by ... { full: "/home/adityam/Documents/bazBiz.txt" } ... ',
  recursivelyFindArrayItemByProperties(tree, {
    arrKey: 'children',
    props: {
      full: "/home/adityam/Documents/bazBiz.txt",
    },
  })
);

console.log(
  '\nfound by ... { full: "/home/adityam/Documents/file.txt" } ... ',
  recursivelyFindArrayItemByProperties(tree, {
    arrKey: 'children',
    props: {
      full: "/home/adityam/Documents/file.txt",
    },
  })
);

console.log(
  '\nfound by ... { full: "/home/adityam/Documents/anotherFolder" } ... ',
  recursivelyFindArrayItemByProperties(tree, {
    arrKey: 'children',
    props: {
      full: "/home/adityam/Documents/anotherFolder",
    },
  })
);
console.log(
  'found by ... { full: "/home/adityam/Documents" } ... ',
  recursivelyFindArrayItemByProperties(tree, {
    arrKey: 'children',
    props: {
      full: "/home/adityam/Documents",
    },
  })
);

console.log(
  '\nfound by ... { name: "anotherFolder", type: "dir" } ... ',
  recursivelyFindArrayItemByProperties(tree, {
    arrKey: 'children',
    props: {
      name: "anotherFolder",
      type: "dir",
      // full: "/home/adityam/Documents/anotherFolder",
    },
  })
);
console.log(
  'found by ... { name: "Documents", type: "dir" } ... ',
  recursivelyFindArrayItemByProperties(tree, {
    arrKey: 'children',
    props: {
      name: "Documents",
      type: "dir",
      // full: "/home/adityam/Documents",
    },
  })
);
.as-console-wrapper { min-height: 100%!important; top: 0; }

CodePudding user response:

As others have already answered, I will post the answer that I wrote earlier, but would usually not post until the OP showed an attempt.


I think we're best off breaking apart the tree navigation code from the code that checks if we're at the right node and from the code that modifies a node.

Since I don't know what sort of modification you are interested in performing, I just add a notice property to the object, but you can use any function that returns a new version of the object, whether an altered clone, a reference to a mutated original, or something else entirely. Here's an example:

const modifyNode = (pred, fn) => (node, _, __,
  {children = [], ...rest} = node, 
  kids = children .map (modifyNode (pred, fn))
) => pred (node)
  ? fn (node)
  : {...rest, ...(kids .length ? {children: kids} : {})}

const modifyByPath = (path) => modifyNode (
  (node) => node.full === path, 
  (node) => ({...node, notice: '*** this was modified ***'})
)


var tree = {name: "Documents", type: "dir", full: "/home/adityam/Documents", children: [{name: "file.txt", type: "file", full: "/home/adityam/Documents/file.txt", }, {name: "anotherFolder", type: "dir",full: "/home/adityam/Documents/anotherFolder", children: [/* ... */]}]}

console .log (modifyByPath ('/home/adityam/Documents/anotherFolder') (tree))
.as-console-wrapper {max-height: 100% !important; top: 0}

We have a utility function modifyNode that accepts a predicate function to test whether we've hit the right node and a modification function that takes a node and returns a node, replaced or altered as desired. It returns a function that takes a node recursively configured with children arrays of objects (themselves with the same structure) and returns an altered version of your tree with every matching node replaced with the result of calling your modification function.

Our main function, modifyByPath, accepts a full path name and calls modifyNode with a simple test predicate and a dummy modification function, which returns a function that does our main work. We will call it like modifyByPath (path) (tree).

  • Related