I have a Person class with the following properties: name, birth and descendants in the form of an array of other Person classes.
Right now I am trying to implement a function that can traverse this family tree starting from the original Person class and return an array which contains all Person classes whose birth year is after 1970 but struggling really badly with implementing the recursion.
My issue is that I don't know how to recurse deeper down the family tree after checking the birth dates of the first and second layer of the tree.
Just wondering if anyone had any pointers.
class Person {
constructor(name, birth) {
this.name = name;
this.birth = birth;
this.desc = [];
}
adddesc(person) {
this.desc.push(person);
}
post1970() {
let res = [];
let birth = this.birth;
let descendants = this.desc;
if (birth > 1970) return this;
for (let i = 0; i < descendants.length; i ) {
let child = descendants[i];
let curr = child.post1970(); //What should I do after this line?
console.log(curr)
}
return res;
}
}
const original = new Person('root', 1900)
let desc1 = new Person("andrew", 1940);
let desc2 = new Person("sarah", 1960);
let desc3 = new Person("charlie", 1980);
let desc4 = new Person("david", 1990);
let desc5 = new Person("ethan", 2000);
original.adddesc(desc1); //Andrew Charlie
original.adddesc(desc3);
desc1.adddesc(desc2); //Andrew: Sarah
desc3.adddesc(desc4); //Charlie: David
desc4.adddesc(desc5); //David: Ethan
original.post1970();
CodePudding user response：
I have a few up-front design suggestions:
post1970()is overly-rigid. The year should be a parameter. Otherwise, you have to write the whole function all over again just to filter by 1969 or any other year. A contract likebornAfter(year)would be a better approach, or generalize further and make it an arbitrary predicate likefilterDescendants(predicateFunction).- Avoid
letunless you absolutely have to use it.constmakes your code safer and more expressive. Whenever I seelet, I feel like the programmer is trying to tell me "I intend to reassign this variable". That's a red herring in most cases, including this -- useconst. Reassignments are a crutch and tend to make code hard to follow. descmakes me think "description".descendantsis much clearer. I'd also make this an array for the constructor; if you want adder/setter/getters as well, that's fine too, but it's a bit awkward not to allow the object to be built in one shot and have to store it in an intermediate variable to set its properties incrementally.- It's a little odd to have these tree-oriented filtering functions on the
Personclass. You might want aFamilyTreeclass that has a rootPerson. This makes the code read likeFamilyTree.filterBy(e => e.birthDate > 1970)rather than the less-intuitivePerson.filterDescendantsBy(e => e.birthDate > 1970). - If you're doing non-hierarchical filtering like this frequently, the tree data structure might be the wrong choice. You could have a secondary array that's built once, or just use the array directly without a tree. Without more information about your use case and the size of your dataset, it's impossible to make a recommendation here other than to note that traversing the whole tree on every filter operation feels wasteful -- for the code below, there's no need for the tree abstraction at all; just go straight to an array and filter away. I assume you're adding other methods later that would actually make sense on a tree.
Anyway, the core of the tree-to-array conversion is the generic descendantsToArray which uses Array#flatMap to recursively build an array of children, then flatten them into a final result array. Once you've built a result array of the whole tree, you can then use an Array#filter call to get your desired result. Finally, I've used Array#map to simplify the output so you won't see a bunch of nested objects.
class Person {
constructor(name, birthDate, descendants=[]) {
this.name = name;
this.birthDate = birthDate;
this.descendants = descendants;
}
descendantsToArray() {
return [this].concat(
...this.descendants.flatMap(e => e.descendantsToArray())
);
}
filterDescendants(predicate) {
return this.descendantsToArray().filter(predicate);
}
}
const root = new Person(
"root",
1900,
[
new Person(
"andrew",
1940,
[new Person("sarah", 1960)]
),
new Person(
"charlie",
1980,
[
new Person(
"david",
1990,
[new Person("ethan", 1990)]
)
]
),
],
);
const peopleBornAfter1970 = root
.filterDescendants(e => e.birthDate > 1970)
.map(e => e.name)
;
console.log(peopleBornAfter1970);If efficiency is a big issue, filtering as a second step is a bit wasteful, so you might try a generator function to be space-conscious. The overall recursive pattern is the same though.
CodePudding user response：
Several notes:
First, I agree with ggorlen's first four points, and partially agree with the fifth. It's all good advice, and please do consider it.
Second, If you're looking for a minimal change to your existing code, it might look like this:
post1970() {
let res = [];
let birth = this.birth;
let descendants = this.desc;
// if (birth > 1970) return this; // No, we will need to return an array of people
if (birth > 1970) res .push (this)
for (let i = 0; i < descendants.length; i ) {
let child = descendants[i];
let curr = child.post1970(); // Q: What should I do after this line?
res = res .concat (curr) // A: this! :-)
// console.log(curr)
}
return res;
}
(but notice that this immediately disallows ggorlen's const-over-let suggestion, as we reassign res along the way. This is one reason I don't personally like this code.)
Third, I agree with ggorlen's goal of making this code more flexible. Here I suggest plain functions instead of class methods. This can also be carried on to using plain objects rather than class instances for your entire tree, but the same code will work with either. Here is how I would approach this:
const treeFilter = (getChildren) => (pred) => (node) => [
... (pred (node) ? [node] : []),
... (getChildren (node) || []) .flatMap (treeFilter (getChildren) (pred))
]
const familyTreeFilter = treeFilter (n => n .desc)
const post1970 = familyTreeFilter (n => n .birth > 1970)
const original = {name: "root", birth: 1900, desc: [{name: "andrew", birth: 1940, desc: [{name: "sarah", birth: 1960, desc: []}]}, {name: "charlie", birth: 1980, desc: [{name: "david", birth: 1990, desc: [{name: "ethan", birth: 2000,desc: []}]}]}]}
console .log (
post1970 (original) /* for display --> */ .map (n => n .name)
)We start with treeFilter, which takes a function describing the tree structure (here our children are in the node desc [which, yes, sounds like it would mean "description" rather than "descendants"], but might have other possibilities, such as children.) This returns a function that takes a predicate -- feed the predicate a value and it reports whether we want to include that value. It returns a function that takes a tree, and returns the matching elements of your tree as a flat array.
The advantage to this curried version is that we can reuse our simple post1970 on any similarly structured tree. We can reuse familyTreeFilter to create other filters for such descendant-child structures. Perhaps we want all the people that have birth before 2000, or those where the name begins with 'c', or those with at least four descendants. Each of those would be trivial to write this way. And we can reuse treeFilter to describe filters on entirely different tree structures, again, with trivial implementations.
Fourth, if these levels of abstraction are overwhelming, it's easy enough to combine them, inlining them one-by-one to get a custom function for your use-case. I rarely find this necessary, but I might do so on a performance-intensive block of code or if I needed to add the function in some short form (say as a comment on a Stack Overflow post.