I am working with legacy data in JSON format. The tree represents where boxes are shipped between the product manufacturer, shipper, redistributor, and finally the destination. Right now the JSON tree structure represents the manufacturer to the shipper to - redistributer in a hierarchical manner. However, the final node of the tree, the destination, is part of the redistributer node. This would be easy as I would just have to walk the tree and add an extra node representing the destination. But this structure has nodes that are identical repeated because they represent the destination too.
So, my goal is to merge nodes with identical ids and to add the final destination nodes onto the tree. The algorithm I have handles the first level of the Redistributers where the children are null. However, when a Redistributor node has children my algorithm fails.
Here is the JSON data and code. I am using javascript too. A lot of the nodes are updated by reference. The big PROBLEM I am having with my work is the any leaf nodes that have children are ignored. The algorithm does not recur over children in the leafs nodes.
This is a really odd case of merging and adding nodes to a tree structure. It's been a brain twister for me. Any help is greatly appreciated. THANK YOU!! Here is the stackblitz: https://stackblitz.com/edit/js-f3uhaw?file=index.js
var nodes = [
{
type: 'Manufacturer',
loc_id: '1d7d43bb',
loc_name: 'San Diego',
destination_loc_id: '1d7d43ba',
destination_loc_name: 'Palm Springs',
children: [
{
type: 'Shipper',
loc_id: '1d7d43ba',
loc_name: 'Palm Springs',
destination_loc_id: '755eb7ca',
destination_loc_name: 'Los Angeles',
destination_loc_type: 'Redistributer',
children: [
{
type: 'Redistributer',
loc_id: '755eb7ca',
loc_name: 'Los Angeles',
destination_loc_id: '50f51eb6',
destination_loc_name: 'Bakersfield',
destination_loc_type: 'Distributer',
children: null,
},
{
type: 'Redistributer',
loc_id: '755eb7ca',
loc_name: 'Los Angeles',
destination_loc_id: '755eb7ce',
destination_loc_name: 'Santa Monica',
destination_loc_type: 'Distributer',
children: null,
},
{
type: 'Redistributer',
loc_id: '755eb7ca',
loc_name: 'Los Angeles',
destination_loc_id: '797a3711',
destination_loc_name: 'San Pedro',
loc_type: 'Redistributer',
destination_loc_type: 'Distributer',
children: null,
},
{
type: 'Redistributer',
loc_id: '755eb7ca',
loc_name: 'Los Angeles',
destination_loc_id: 'aecf4289',
destination_loc_name: 'Malibu',
loc_type: 'Redistributer',
destination_loc_type: 'Distributer',
children: null,
},
{
type: 'Redistributer',
loc_id: '755eb7ca',
loc_name: 'Los Angeles',
destination_loc_id: 'aecf4288',
destination_loc_name: 'Long Beach',
loc_type: 'Redistributer',
destination_loc_type: 'Distributer',
children: [
{
type: 'Redistributer',
loc_id: 'aecf4288',
loc_name: 'Long Beach',
destination_loc_id: 'aecf4228',
destination_loc_name: 'Santa Ana',
loc_type: 'Redistributer',
destination_loc_type: 'Distributer',
children: null,
},
],
},
],
},
],
},
];
function preProcessNodes() {
for (var i = 0; i < nodes.length; i++) {
let children = nodes[i].children[0].children;
nodes[i].children[0].children = walkTree(children);
console.log(JSON.stringify(nodes));
}
}
function walkTree(children) {
//merge first child nodes here
children = children.filter((x, i) => x.id === children[i].id);
while (children.length > 1) {
const parent = children[0];
const newNode = {
type: parent.type,
loc_id: parent.loc_id,
loc_name: parent.loc_name,
loc_type: parent.loc_type,
children: [],
};
const childs = [];
for (var j = 0; j < children?.length; j++) {
const child = children[j];
childs.push({
loc_id: child.destination_loc_id,
loc_name: child.destination_loc_name,
type: child.destination_loc_type,
children: null,
});
}
newNode.children = childs;
children
.filter((x, i) => x.id === children[i].id)
.forEach((x) => children.splice(children.indexOf(x), 1));
children.push(newNode);
console.log(children);
walkTree(children);
}
return children;
}
preProcessNodes();
The end result I am trying to output is:
[{
type: 'Manufacturer',
loc_id: '1d7d43bb',
loc_name: 'San Diego',
destination_loc_id: '1d7d43ba',
destination_loc_name: 'Palm Springs',
children: [{
type: 'Shipper',
loc_id: '1d7d43ba',
loc_name: 'Palm Springs',
destination_loc_id: '755eb7ca',
destination_loc_name: 'Los Angeles',
destination_loc_type: 'Redistributer',
children: [{
type: 'Redistributer',
loc_id: '755eb7ca',
loc_name: 'Los Angeles',
children: [{
loc_id: '50f51eb6',
loc_name: 'Bakersfield',
type: 'Distributer',
children: null
},
{
loc_id: '755eb7ce',
loc_name: 'Santa Monica',
type: 'Distributer',
children: null
},
{
loc_id: '797a3711',
loc_name: 'San Pedro',
type: 'Distributer',
children: null,
},
{
loc_id: 'aecf4289',
loc_name: 'Malibu',
loc_type: 'Redistributer',
type: 'Distributer',
children: null
},
{
loc_id: 'aecf4282',
loc_name: 'Long Beach',
loc_type: 'Redistributer',
children: [{
loc_id: 'aecf4283',
loc_name: 'Santa Ana',
loc_type: 'Distributer',
children: null,
}]
}
]
}
]
}]
}]
This approach detects duplicate entries (same loc_id) and deletes them. At the same time as the deletion, a child object for the destination_* fields is added to the correct parent's children array.
const nodes = [{"type":"Manufacturer","loc_id":"1d7d43bb","loc_name":"San Diego","destination_loc_id":"1d7d43ba","destination_loc_name":"Palm Springs","children":[{"type":"Shipper","loc_id":"1d7d43ba","loc_name":"Palm Springs","destination_loc_id":"755eb7ca","destination_loc_name":"Los Angeles","destination_loc_type":"Redistributer","children":[{"type":"Redistributer","loc_id":"755eb7ca","loc_name":"Los Angeles","destination_loc_id":"50f51eb6","destination_loc_name":"Bakersfield","destination_loc_type":"Distributer","children":null},{"type":"Redistributer","loc_id":"755eb7ca","loc_name":"Los Angeles","destination_loc_id":"755eb7caX","destination_loc_name":"Santa Monica","destination_loc_type":"Distributer","children":null},{"type":"Redistributer","loc_id":"755eb7ca","loc_name":"Los Angeles","destination_loc_id":"797a3711","destination_loc_name":"San Pedro","loc_type":"Redistributer","destination_loc_type":"Distributer","children":null},{"type":"Redistributer","loc_id":"755eb7ca","loc_name":"Los Angeles","destination_loc_id":"aecf4289","destination_loc_name":"Malibu","loc_type":"Redistributer","destination_loc_type":"Distributer","children":null},{"type":"Redistributer","loc_id":"755eb7ca","loc_name":"Los Angeles","destination_loc_id":"aecf4288","destination_loc_name":"Long Beach","loc_type":"Redistributer","destination_loc_type":"Distributer","children":[{"type":"Redistributer","loc_id":"aecf4288","loc_name":"Long Beach","destination_loc_id":"aecf4228","destination_loc_name":"Santa Ana","loc_type":"Redistributer","destination_loc_type":"Distributer","children":null}]}]}]}]
const lookup = {}
const f = arr => {
let dropList = [];
arr.forEach((i,index)=>{
let existing = lookup[i.loc_id];
if(!existing) {
lookup[i.loc_id] = i;
}
else {
if(existing.destination_loc_id) {
let child = {
loc_id: existing.destination_loc_id,
loc_name: existing.destination_loc_name,
loc_type: existing.destination_loc_type,
children: null
}
delete existing.destination_loc_id;
delete existing.destination_loc_name;
delete existing.destination_loc_type;
(existing.children??=[]).push(child);
lookup[child.loc_id] = child;
}
dropList.push(index);
let child = {
loc_id: i.destination_loc_id,
loc_name: i.destination_loc_name,
loc_type: i.destination_loc_type,
children: null
};
(existing.children??=[]).push(child);
lookup[child.loc_id] = child;
}
if(i.children) f(i.children)
})
dropList.reverse().forEach(index=>arr.splice(index, 1));
}
f(nodes)
console.log(nodes)