I answered a similar question recently. I'm sharing it here because I think it provides a relevant foundation for this post. Before we begin though, we must first address the irregular shape of your input data -
const data2 =
{ name:"root"
, children:
Array.from
( Object.entries(data.root)
, ([ country, _ ]) =>
Object.assign({ name:country }, _)
)
}
console.log(JSON.stringify(data2, null, 2))
Now we can see data2 is a uniform { name, children: [ ... ]} shape -
{
"name": "root",
"children": [
{
"name": "Europe",
"children": [
{ "name": "Germany" },
{
"name": "England",
"children": [
{
"name": "London",
"search_words": [ "city", "capital" ],
"children": [
{
"name": "Westminster",
"search_words": [ "borough" ]
}
]
},
{
"name": "Manchester",
"search_words": [ "city" ]
}
]
},
{
"name": "France",
"children": [
{
"name": "Paris",
"search_words": [ "city", "capital" ]
}
]
}
]
},
{
"name": "North America",
"children": [
{
"name": "Canada",
"children": [
{ "name": "Toronto" },
{ "name": "Ottawa" }
]
},
{ "name": "United States" }
]
}
]
}
Now we write a generic depth-first traversal function, dft -
function* dft (t, path = [])
{ for (const _ of t.children ?? [])
yield* dft(_, [...path, t.name ])
yield [path, t]
}
Our dft function gives us a path to each element, e, in our input tree, t -
["root","Europe"]
{"name":"Germany"}
["root","Europe","England","London"]
{name:"Westminster", search_words:["borough"]}
["root","Europe","England"]
{name:"London", search_words:["city","capital"], children:[...]}
["root","Europe","England"]
{name:"Manchester", search_words:["city"]}
["root","Europe"]
{name:"England", children:[...]}
["root","Europe","France"]
{name:"Paris", search_words:["city","capital"]}
["root","Europe"]
{name:"France", children:[...]}
["root"]
{name:"Europe", children:[...]}
["root","North America","Canada"]
{name:"Toronto"}
Now that we know that path to each of the nodes, we can create an index which uses the path and any search_words to link back to the node -
const index = t =>
Array.from
( dft(t)
, ([path, e]) =>
[ [...path, e.name, ...e.search_words ?? [] ] // all words to link to e
, e // e
]
)
.reduce
( (m, [ words, e ]) =>
insertAll(m, words, e) // update the index using generic helper
, new Map
)
This depends on a generic helper insertAll -
const insertAll = (m, keys, value) =>
keys.reduce
( (m, k) =>
m.set(k, [ ...m.get(k) ?? [], value ])
, m
)
With index finished, we have a way to create a fast lookup for any search term -
const myIndex =
index(data2)
console.log(myIndex)
Map
{ "Europe" =>
[{"name":"Germany"},{"name":"Westminster",...},{"name":"London",...},{"name":"Manchester",...},{"name":"England"...},{"name":"Manchester",...}]},{"name":"Paris",...},{"name":"France"...},{"name":"Europe"...},{"name":"Manchester",...}]},{"name":"France"...}]}]
, "Germany" =>
[{"name":"Germany"}]
, "England" =>
[{"name":"Westminster",...},{"name":"London",...},{"name":"Manchester",...},{"name":"England"...},{"name":"Manchester",...}]}]
, "London" =>
[{"name":"Westminster",...},{"name":"London",...}]
, "Westminster" =>
[{"name":"Westminster",...}]
, "borough" =>
[{"name":"Westminster",...}]
, "city" =>
[{"name":"London",...},{"name":"Manchester",...},{"name":"Paris",...}]
, "capital" =>
[{"name":"London",...},{"name":"Paris",...}]
, "Manchester" =>
[{"name":"Manchester",...}]
, "France" =>
[{"name":"Paris",...},{"name":"France"...}]
, "Paris" =>
[{"name":"Paris",...}]
, "North America" =>
[{"name":"Toronto"},{"name":"Ottawa"},{"name":"Canada"...},{"name":"United States"},{"name":"North America"...},
{"name":"United States"}]}]
, "Canada" =>
[{"name":"Toronto"},{"name":"Ottawa"},{"name":"Canada"...}]
, "Toronto" =>
[{"name":"Toronto"}]
, "Ottawa" =>
[{"name":"Ottawa"}]
, "United States" =>
[{"name":"United States"}]
}
This should highlight the remaining inconsistencies in your data. For example, you have some nodes nested under city, capital, or borough. Also worth noting that we should probably use s.toLowerCase() on all of the index keys so that lookups can be case-insensitive. This is an exercise left for the reader.
Creating the index is easy and you only need to do it once -
const myIndex =
index(data2)
Your index can be reused for as many lookups as you need -
console.log(myIndex.get("Toronto") ?? [])
console.log(myIndex.get("France") ?? [])
console.log(myIndex.get("Paris") ?? [])
console.log(myIndex.get("Canada") ?? [])
console.log(myIndex.get("Zorp") ?? [])
[{"name":"Toronto"}]
[{"name":"Paris",...},{"name":"France"...}]
[{"name":"Paris",...}]
[{"name":"Toronto"},{"name":"Ottawa"},{"name":"Canada"...}]
[]
Inserting the results in you Vue application is left for you.
