I have a json tree structure that I want to normalize into something like a hashmap and then denormalize it back to a tree if needed. I have a very dynamic tree that I want to use as state in my react-redux project, but for that I somehow need to transform the data so that I can access it without having to search elements recursively in the tree each time I want to update/access the state.
const actual = {
id: "1",
type: 'Container',
data: {},
items: [
{
id: "2",
type: "Subcontainer",
data: {
title: "A custom title",
text: "A random Headline"
},
items: []
},
{
id: "3",
type: "Subcontainer",
data: {
title: "A custom title",
text: "A random Headline"
},
items: []
}
]
};
Now I want to transform it into something like:
const expected = {
1: {
id: "1",
type: 'Container',
data: {},
items: [1, 2]
},
2: {
id: "2",
type: "Subcontainer",
data: {
title: "A custom title",
text: "A random Headline"
},
items: []
},
3: {
id: "3",
type: "Subcontainer",
data: {
title: "A custom title",
text: "A random Headline"
},
items: []
}
};
I found a JS lib called Normalizr, but I absolutely don't get how to create the schemas for it to work.
That was my last try, and it returns only the inner two items and also directly the data object inside without id, items around:
const data = new schema.Entity("data");
const item = new schema.Object({ data });
item.define({ items: new schema.Array(item) });
const items = new schema.Array(item);
const normalizedData = normalize(mock, items);
CodePudding user response：
I would recommend .flatMap for this kind of transformations:
const flattenTree = element => [
element,
...element.data.items.flatMap(normalizeTree)
]
This move you from this shape:
{
id: 1,
data: { items: [
{
id: 2,
data: { items: [
{ id: 3, data: { items: [] } },
] }
] }
}
to this one:
[
{ id: 1, data: {...}},
{ id: 2, data: {...}},
{ id: 3, data: {...}},
]
Then once you have a flat array, you can transform it further to remove the references and create an object from entries:
const normalizedTree = element => {
let flat = flattenTree(element)
// only keep the id of each items:
// [{ id: 1, data:{...}}] -> [1]
// for (const el of flat) {
// el.data.items = el.data.items.map(child => child.id)
// }
// note that the for loop will change the initial data
// to preserve it you can achieve the same result with
// a map that will copy every elements:
const noRefs = flat.map(el => ({
...el,
data: {
...el.data,
items: el.data.items.map(child => child.id),
},
}))
// then if you need an object, 2 steps, get entries, [id, elem]:
const entries = noRefs.map(({ id, ...element }) => [id, element])
// then the built-in `Object.fromEntries` do all the work for you
// using the first part of the entry as key and last as value:
return Object.fromEntries(entries)
// if you have multiple objects with the same id's, only the last one
// will be in your returned object
}
CodePudding user response：
I'm not going to worry too much about the types, since you can alter those to meet your needs. Going off you're example, I will define
interface Tree {
id: string;
type: string;
data: {
title?: string;
text?: string;
items: Tree[];
}
}
interface NormalizedTree {
[k: string]: {
id: string;
type: string;
data: {
title?: string;
text?: string;
items: string[]
}
}
}
and we want to implement function normalize(tree: Tree): NormalizedTree and function denormalize(norm: NormalizedTree): Tree.
The normalize() function is fairly straightforward since you can recursively walk the tree and collect the normalized trees into one big normalized tree:
function normalize(tree: Tree): NormalizedTree {
return Object.assign({
[tree.id]: {
...tree,
data: {
...tree.data,
items: tree.data.items.map(v => v.id)
}
},
}, ...tree.data.items.map(normalize));
}
In English, we are making a single normalized tree with a property with key tree.id and a value that's the same as tree except the data.items property is mapped to just the ids. And then we are mapping each element of data.items with normalize to get a list of normalized trees that we spread into that normalized tree via the Object.assign() method. Let's make sure it works:
const normalizedMock = normalize(mock);
console.log(normalizedMock);
/* {
"1": {
"id": "1",
"type": "Container",
"data": {
"items": [
"2",
"3"
]
}
},
"2": {
"id": "2",
"type": "Subcontainer",
"data": {
"title": "A custom title",
"text": "A random Headline",
"items": []
}
},
"3": {
"id": "3",
"type": "Subcontainer",
"data": {
"title": "A custom title",
"text": "A random Headline",
"items": []
}
}
} */
Looks good.
The denormalize() function is a little trickier, because we need to trust that the normalized tree is valid and actually represents a tree with a single root and no cycles. And we need to find and return that root. Here's one approach:
function denormalize(norm: NormalizedTree): Tree {
// make Trees with no children
const treeHash: Record<string, Tree> =
Object.fromEntries(Object.entries(norm).
map(([k, v]) => [k, { ...v, data: { ...v.data, items: [] } }])
);
// keep track of trees with no parents
const parentlessTrees =
Object.fromEntries(Object.entries(norm).map(([k, v]) => [k, true]));
Object.values(norm).forEach(v => {
// hook up children
treeHash[v.id].data.items = v.data.items.map(k => treeHash[k]);
// trees that are children do have parents, remove from parentlessTrees
v.data.items.forEach(k => delete parentlessTrees[k]);
})
const parentlessTreeIds = Object.keys(parentlessTrees);
if (parentlessTreeIds.length !== 1)
throw new Error("uh oh, there are "
parentlessTreeIds.length
" parentless trees, but there should be exactly 1");
return treeHash[parentlessTreeIds[0]];
}
In English... first we copy the normalized tree into a new treeHash object where all the data.items are empty. This will eventually hold our denormalized trees, but right now there are no children.
Then, in order to help us find the root, we make a set of all the ids of the trees, from which we will remove any ids corresponding to trees with parents. When we're all done, there should hopefully be a single id left, that of the root.
Then we start populating the children of treeHash's properties, by mapping the corresponding data.items array from the normalized tree to an array of properties of treeHash. And we remove all of these child ids from parentlessTreeIds.
Finally, we should have exactly one property in parentlessTreeIds. If not, we have some kind of forest, or cycle, and we throw an error. But assuming we do have a single parentless tree, we return it.
Let's test it out:
const reconsitutedMock = denormalize(normalizedMock);
console.log(reconsitutedMock);
/* {
"id": "1",
"type": "Container",
"data": {
"items": [
{
"id": "2",
"type": "Subcontainer",
"data": {
"title": "A custom title",
"text": "A random Headline",
"items": []
}
},
{
"id": "3",
"type": "Subcontainer",
"data": {
"title": "A custom title",
"text": "A random Headline",
"items": []
}
}
]
}
} */
Also looks good.