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:
- A recursive algorithm must call itself, recursively.
- A recursive algorithm must have a base case.
- A recursive algorithm must change its state and move toward the base case.
For example findNodeRecursive(name, node)
:
- If property
full
of node equals name, return node. (Base case: Found) - If property
type
of node is not"dir"
, return null. (Base case: Cannot be inside) - For each element childNode of property
children
of node: (Moving toward some base case)- Let result be the result of the call
findNodeRecursive(name, childNode)
. (Recursive call) - If result is not null, return result. (Base case: Found in
children
)
- Let result be the result of the call
- 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)
.