xref: /webtrees/app/Services/ChartService.php (revision cab242e7d7a773b0a6dab130048696e26fd6612c) 
1<?php
2/**
3 * webtrees: online genealogy
4 * Copyright (C) 2019 webtrees development team
5 * This program is free software: you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation, either version 3 of the License, or
8 * (at your option) any later version.
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 * You should have received a copy of the GNU General Public License
14 * along with this program. If not, see <http://www.gnu.org/licenses/>.
15 */
16declare(strict_types=1);
17
18namespace Fisharebest\Webtrees\Services;
19
20use Fisharebest\Webtrees\Family;
21use Fisharebest\Webtrees\Individual;
22use Illuminate\Support\Collection;
23
24/**
25 * Find ancestors, descendants, cousins, etc for drawing charts.
26 */
27class ChartService
28{
29    /**
30     * Find the ancestors of an individual, indexed by their Sosa-Stradonitz number.
31     *
32     * @param Individual $individual  Start with this individual
33     * @param int        $generations Fetch this number of generations
34     *
35     * @return Collection|Individual[]
36     */
37    public function sosaStradonitzAncestors(Individual $individual, int $generations): Collection
38    {
39        $ancestors = [1 => $individual];
40
41        $queue = [1];
42
43        $max = 2 ** ($generations - 1);
44
45        while (!empty($queue)) {
46            $sosa_stradonitz_number = array_shift($queue);
47
48            if ($sosa_stradonitz_number >= $max) {
49                break;
50            }
51
52            $family = $ancestors[$sosa_stradonitz_number]->primaryChildFamily();
53
54            if ($family instanceof Family) {
55                if ($family->husband() instanceof Individual) {
56                    $ancestors[$sosa_stradonitz_number * 2] = $family->husband();
57                    $queue[] = $sosa_stradonitz_number * 2;
58                }
59
60                if ($family->wife() instanceof Individual) {
61                    $ancestors[$sosa_stradonitz_number * 2 + 1] = $family->wife();
62                    $queue[] = $sosa_stradonitz_number * 2 + 1;
63                }
64            }
65        }
66
67        return new Collection($ancestors);
68    }
69
70    /**
71     * Find the descendants of an individual.
72     *
73     * @param Individual $individual  Start with this individual
74     * @param int        $generations Fetch this number of generations
75     *
76     * @return Collection|Individual[]
77     */
78    public function descendants(Individual $individual, int $generations): Collection
79    {
80        $descendants = new Collection([$individual]);
81
82        if ($generations > 0) {
83            foreach ($individual->spouseFamilies() as $family) {
84                foreach ($family->children() as $child) {
85                    $descendants = $descendants->merge($this->descendants($child, $generations - 1));
86                }
87            }
88        }
89
90        return $descendants;
91    }
92
93    /**
94     * Find the descendants of an individual.
95     *
96     * @param Individual $individual  Start with this individual
97     * @param int        $generations Fetch this number of generations
98     *
99     * @return Collection|Family[]
100     */
101    public function descendantFamilies(Individual $individual, int $generations): Collection
102    {
103        $descendants = new Collection($individual->spouseFamilies());
104
105        if ($generations > 0) {
106            foreach ($descendants as $family) {
107                foreach ($family->children() as $child) {
108                    $descendants = $descendants->merge($this->descendantFamilies($child, $generations - 1));
109                }
110            }
111        }
112
113        return $descendants;
114    }
115}
116