The array gets the sum of all children from bottom to top
I have a javascript array that looks like this:
[
{
used : 24000,
service : service A,
parent : service B,
},
{
used : 450,
service : service B,
parent : service C,
},
...
]
I would like to loop over the array to get the sum of each child service. For example, if a service got A and B as a child, then its used attribute would be its own + the sum of its used child. As a consequence, I need to get the deepest services in the hierarchy first.
Then the end result could be:
[
{
used : 24000,
service : service A,
parent : service B,
},
{
used : 24450, //Sum here has changed
service : service B,
parent : service C,
},
...
]
Last, the top service doesn't always have a null parent ...
I can convert the array to hierarchical if necessary
Does anyone have a good algorithm that can do such a thing (probably in javascript, but the pseudocode is cool too)?
source to share
You can use map
, reduce
and filter
, to do it on multiple lines:
var services = [{
used : 24000,
service : "A",
parent : "B",
}, {
used : 450,
service : "B",
parent : "C",
}, {
used : 150,
service : "C",
}, {
used: 100,
service: "D"
}
]
// Update one service, children first
var _update_service_sums = function(service, services) {
var children = services.filter(s => s.parent === service.service)
children.forEach(c => _update_service_sums(c, services))
service.used_sum = service.used + children.map(c => c.used_sum).reduce((a, b) => a + b, 0);
}
// Update all services
var update_service_sums = function(services) {
var roots = services.filter(s => s.parent === undefined)
roots.forEach(r => _update_service_sums(r, services))
}
update_service_sums(services)
console.log(services)
I didn't want to change the value used
, so you can call the function multiple times in a row.
I am guessing there may be multiple root services and none of them have a parent. If you want to compute used_sum
for other services, you can call directly _update_service_sums(service, services)
.
source to share
This problem reminds me of a lot of addiction. In case of problem building dependencies, you need to schedule jobs based on their dependencies (jobs that should come before them). If you have assignments A, B and C, where A depends on B and C, you should schedule assignments B and C to A. Your problem is not scheduling, but adding numbers from your dependent assignments to your current work. To get the total "used" amount from Service A, you must first calculate the totals for services B and C. Your array is a dependency graph, but instead of scheduling jobs, you calculate the used attribute.
The problem is that your implementation should be very different if your graph is not a tree. From the description of your problem, it sounds like we are dealing with a tree. If we don't, then please let me know in the comments and I can update my answer. If you think of your graph as a dependency tree, then all you have to do is ensure that for every node in the graph, you are evaluating it as children before evaluating it. This can be done using the post-order traversal http://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/... If you can implement a post-order traversal on this dependency graph, you can simply add the values returned by the left size and right traversals to your current amount, and then return a new "custom" attribute for parent use. This is an O (n) algorithm that calculates your values.
source to share