I could really use some help Debugging a problem. Im trying to build a nested object (tree) from a very unusual array im getting from a backend (dont have access to the BE so i have to work with what i got). I’ve gotten 95 percent of it done but im running into a bug
I know there are many of these flat arrays to nested objects in StackOverFlow, but this array i'm given to work with is way different. It does not have ids or typical properties of a flatten array. The good thing is that I have most of it done.
Here is a basic example of The problem I'm having:
Data:
let stackTest = {
predicates: [
{
primaryTerm: "test1",
level: 1,
condition: 0,
},
{
primaryTerm: "and",
level: 1,
condition: 2,
},
{
primaryTerm: "test2",
level: 1,
condition: 0,
},
{
primaryTerm: "and",
level: 1,
condition: 2,
},
{
primaryTerm: "test3",
level: 2,
condition: 0,
},
{
primaryTerm: "or",
level: 2,
condition: 1,
},
{
primaryTerm: "test4",
level: 2,
condition: 0,
},
{
primaryTerm: "or",
level: 2,
condition: 1,
},
{
primaryTerm: "test5",
level: 3,
condition: 0,
},
{
primaryTerm: "and",
level: 3,
condition: 2,
},
{
primaryTerm: "test5",
level: 3,
condition: 0,
},
]
Desired Function output:
[
{
id: 1,
children: [
{
id: 2,
children: [],
parentId: 1,
level: 1,
primaryTerm: 'test1',
condition: 0
},
{
id: 3,
children: [],
parentId: 1,
primaryTerm: 'test2',
level: 1,
condition: 0
},
{
id: 4,
children: [
{
primaryTerm: 'test3',
level: 2,
condition: 0,
id: 5,
children: [],
parentId: 4
},
{
id: 6,
children: [],
parentId: 4,
primaryTerm: 'test4',
level: 2,
condition: 0
},
{
id: 8,
children: [
{
primaryTerm: 'test5',
level: 3,
condition: 0,
id: 9,
children: [],
parentId: 8
},
{
id: 10,
children: [],
parentId: 8,
primaryTerm: 'test5',
level: 3,
condition: 0
}
],
parentId: 4,
level: 2,
primaryTerm: 'and',
condition: 2
}
],
parentId: 0,
level: 1,
primaryTerm: 'or',
condition: 1
}
],
parentId: 0,
level: 0,
primaryTerm: 'and',
condition: 2
}
]
Desired Tree Representation:
AND
/ | \
Test1 Test2 OR
/ | \
Test3 Test4 AND
| \
Test5 Test6
Actual Function output:
[
{
id: 1,
children: [
{
id: 2,
children: [],
parentId: 1,
level: 1,
primaryTerm: 'test1',
condition: 0
},
{
id: 3,
children: [],
parentId: 1,
primaryTerm: 'test2',
level: 1,
condition: 0
},
{
id: 4,
children: [
{
primaryTerm: 'test3',
level: 2,
condition: 0,
id: 5,
children: [],
parentId: 4
},
{
id: 6,
children: [],
parentId: 4,
primaryTerm: 'test4',
level: 2,
condition: 0
},
{
id: 7,
children: [
{
id: 8,
children: [
{
primaryTerm: 'test5',
level: 3,
condition: 0,
id: 9,
children: [],
parentId: 8
},
{
id: 10,
children: [],
parentId: 8,
primaryTerm: 'test5',
level: 3,
condition: 0
}
],
parentId: 7,
level: 2,
primaryTerm: 'and',
condition: 2
}
],
parentId: 1,
level: 1
}
],
parentId: 0,
level: 1,
primaryTerm: 'or',
condition: 1
}
],
parentId: 0,
level: 0,
primaryTerm: 'and',
condition: 2
}
]
Actual Tree Representation:
AND
/ | \
Test1 Test2 OR
/ | \
Test3 Test4 {} --here is the issue
\
AND
| \
Test5 Test6
The Problem: An extra empty object is being created, this object shouldn't be there at all. not sure why this extra node is being created. I suspect it may have to do with the buildEmptyFlatArr, it may not be properly appending the parentId since that too is messed up. This issue only happens when a nested branch is to the right of the Tree, if the nested branch was to the left of the tree it wouldn't happen.
What i have done so far:
rule: objects that have 'and' / 'or' are considered Logical operators only logical (AND/OR) objects can have children steps
- 1: Initialize the nested obj(tree) to the level of the first predicate:
The functions buildEmptyFlatArr and listToTree handle this
- 2: when we get to the (And/OR) object, give the properties of a logical container to the new nodes where the level of that empty node matches (logicalObject level -1 )
The updatedTreeNode function handles this
- 3: if the following item in the array has the same level as the last logical object, then append the following object to the logical operator from step #2. if the levels differ, append an empty node until you reach the level of that currently looped object.
The updatedTreeNode function handles this
The Code:
let id = 1;
let lastLogical = {};
let lastItemAdded = {};
let initTree;
const buildEmptyFlatArr = (num, branch = false, branchLastValue) => {
let initArr = [];
for (let i = 0; i {
let map = {},
node,
roots = [],
i;
for (i = 0; i {
tree.forEach((item, index) => {
if (logical) {
if (item.level === target.level - 1
) {
let objToMod = item;
if (item.condition === undefined) {
for (const [key, value] of Object.entries(target)) {
if (key === "level") {
objToMod["level"] = target.level - 1;
} else {
objToMod[key] = value;
}
}
}
lastLogical = item;
lastItemAdded = item;
} else if (item.children.length > 0 ) {
lastLogical = item;
updateTreeNode(item.children, target, first, logical);
}
} else if (first) {
if (item.level === target.level) {
let objToMod = item;
for (const [key, value] of Object.entries(target)) {
objToMod[key] = value;
}
lastItemAdded = item;
return;
} else if (item.children !== null && item.children.length > 0) {
updateTreeNode(item.children, target, first, logical);
}
} else if (!first && !logical) {
if (Math.abs(lastLogical.level - target.level) > 1) {
let buildArrayLength = target.level - 1;
let arrToAppend = buildEmptyFlatArr(buildArrayLength, true, target);
let newBranchToAppend = listToTree(arrToAppend);
lastLogical.children = [...lastLogical.children, { ...newBranchToAppend[0] }];
lastItemAdded = item;
lastLogical = item;
} else if (item.level === target.level - 1 && lastLogical === item) {
let objToMod = item;
objToMod.children = [
...objToMod.children,
{ id: id, children: [], parentId: item.id, ...target },
];
id = 1;
lastItemAdded = item;
lastLogical = item
} else {
updateTreeNode(item.children, target);
}
}
});
};
const buildTree = (templateData) => {
templateData.forEach((item, index) => {
if (index === 0) {
let list = buildEmptyFlatArr(item.level);
initTree = listToTree(list);
updateTreeNode(initTree, item, true, false);
} else if (item.condition === 1 || item.condition === 2) {
updateTreeNode(initTree, item, false, true);
} else {
updateTreeNode(initTree, item);
}
});
};
buildTree(templateObj8.predicates);
console.dir(initTree, { depth: null });
EDIT: I did not do a good job asking this question (first question i think) additional example of how the tree is suppose to look like. The initial example i've given is a tree weighted to the right. but the tree should be able to handle a more complex tree like this
second set of Data
let stackTest = {
predicates: [
{
primaryTerm: "test1",
level: 3,
condition: 0,
},
{
primaryTerm: "and",
level: 3,
condition: 2,
},
{
primaryTerm: "test2",
level: 3,
condition: 0,
},
{
primaryTerm: "and",
level: 1,
condition: 2,
},
{
primaryTerm: "test3",
level: 2,
condition: 0,
},
{
primaryTerm: "or",
level: 2,
condition: 1,
},
{
primaryTerm: "test4",
level: 2,
condition: 0,
},
{
primaryTerm: "or",
level: 2,
condition: 1,
},
{
primaryTerm: "test5",
level: 3,
condition: 0,
},
{
primaryTerm: "and",
level: 3,
condition: 2,
},
{
primaryTerm: "test5",
level: 3,
condition: 0,
},
{
primaryTerm: "and",
level: 1,
condition: 2,
},
{
primaryTerm: "test6",
level: 2,
condition: 0,
},
{
primaryTerm: "or",
level: 2,
condition: 1,
},
{
primaryTerm: "test7",
level: 2,
condition: 0,
},
]
current output of my code
[
{
id: 1,
children: [
{
id: 2,
children: [
{
id: 3,
children: [
{
id: 4,
children: [],
parentId: 3,
level: 3,
primaryTerm: 'test1',
condition: 0
},
{
id: 5,
children: [],
parentId: 3,
primaryTerm: 'test2',
level: 3,
condition: 0
}
],
parentId: 2,
level: 2,
primaryTerm: 'and',
condition: 2
}
],
parentId: 1,
level: 1,
primaryTerm: 'or',
condition: 1
},
{
id: 6,
children: [
{
primaryTerm: 'test3',
level: 2,
condition: 0,
id: 7,
children: [],
parentId: 6
},
{
id: 8,
children: [],
parentId: 6,
primaryTerm: 'test4',
level: 2,
condition: 0
},
{
id: 9,
children: [
{
id: 10,
children: [
{
primaryTerm: 'test5',
level: 3,
condition: 0,
id: 11,
children: [],
parentId: 10
},
{
id: 12,
children: [],
parentId: 10,
primaryTerm: 'test5',
level: 3,
condition: 0
}
],
parentId: 9,
level: 2,
primaryTerm: 'and',
condition: 2
}
],
parentId: 1,
level: 1
}
],
parentId: 0,
level: 1,
primaryTerm: 'or',
condition: 1
},
{
id: 13,
children: [
{
primaryTerm: 'test6',
level: 2,
condition: 0,
id: 14,
children: [],
parentId: 13
},
{
id: 15,
children: [],
parentId: 13,
primaryTerm: 'test7',
level: 2,
condition: 0
}
],
parentId: 0,
level: 1,
primaryTerm: 'or',
condition: 1
}
],
parentId: 0,
level: 0,
primaryTerm: 'and',
condition: 2
}
]
as you can see object with id: #9 is an extra object that should not be there that is the issue im dealing with. thank you
CodePudding user response：
This should get you started:
function parse(tokens, level) {
let expr = []
while (tokens.length) {
let tok = tokens[0]
if (tok.level < level) {
break;
}
if (tok.level === level) {
expr.push(tok.primaryTerm);
tokens.shift();
continue;
}
expr.push(parse(tokens, tok.level))
}
return {op: expr[1], args: expr.filter((_, n) => n % 2 === 0)}
}
For your input, parse(stackTest.predicates, 1) returns this AST:
{
"op": "and",
"args": [
"test1",
"test2",
{
"op": "or",
"args": [
"test3",
"test4",
{
"op": "and",
"args": [
"test5",
"test5"
]
}
]
}
]
}
CodePudding user response：
This is an approach with an array for the operator for every level.
The tree contains always sub trees with an operator as root and operands as leaves. Any operand can contais sub trees as well.
If a level is deeper than the level before, it creates a new sub tree with the operand at top and children for the operands.
const
predicates = [{ primaryTerm: "test1", level: 1, condition: 0 }, { primaryTerm: "and", level: 1, condition: 2, }, { primaryTerm: "test2", level: 1, condition: 0 }, { primaryTerm: "and", level: 1, condition: 2 }, { primaryTerm: "test3", level: 2, condition: 0 }, { primaryTerm: "or", level: 2, condition: 1 }, { primaryTerm: "test4", level: 2, condition: 0 }, { primaryTerm: "or", level: 2, condition: 1 }, { primaryTerm: "test5", level: 3, condition: 0 }, { primaryTerm: "and", level: 3, condition: 2 }, { primaryTerm: "test5", level: 3, condition: 0 }],
result = [],
levels = [{ children: result }];
let id = 1,
lastLevel = -Infinity;
predicates.forEach(o => {
const level = o.level;
if (level > lastLevel) {
// generate new operator
// assign children to levels
levels[level - 1].children.push(levels[level] = { id, parentId: levels[level - 1]?.id || 0, children: [] });
id ;
}
if (o.condition) { // update operators
if (!levels[level].condition) Object.assign(levels[level], o);
} else { // assign levels
levels[level].children.push({ id, parentId: levels[level].id, ...o, children: [] });
id ;
}
lastLevel = level;
});
console.log(result);.as-console-wrapper { max-height: 100% !important; top: 0; }