CODEWITHSUNDEEP
phprecursionmultidimensional-arraycountchildren
Janus Bahs Jacquet
Janus Bahs Jacquet

Reputation: 920

(PHP) Aggregate counting of children in multidimensional array being populated in recursive function

I have a table in a MySQL database that represents a genetic language tree. Each row is a language with an ID and a parent ID; for example:

id   | language            | parent
-----+---------------------+--------
1    | Proto-Indo-European | NULL
6    | Celtic              | 1
8    | Insular Celtic      | 6
9    | Goidelic            | 8
14   | Irish               | 9
16   | Manx                | 9
21   | British             | 8
22   | Welsh               | 21
109  | Germanic            | 1
115  | West Germanic       | 109
117  | Anglo-Saxon         | 115
118  | Anglic              | 117
119  | Old English         | 118

My goal is to turn these rows into a pretty nested HTML list with aggregate counters after each language that has any child languages, using a simple recursive PHP function, resulting in something like this (based on the languages in the example rows above):

  • Proto-Indo-European (11)
    • Celtic (6)
      • Insular Celtic (5)
        • Goidelic (2)
          • Irish
          • Manx
        • British (1)
          • Welsh
    • Germanic (4)
      • West Germanic (3)
        • Anglo-Saxon (2)
          • Anglic (1)
            • Old English

I have the following PHP function (simplified here), which creates a multidimensional array with the proper structure:

function select_languages_hierarchical($parent = NULL) {
    global $db;
    $branch = array();
    $query = "SELECT * FROM languages WHERE parent = $parent";

    if ($q = $db->query($query)) {
        while ($row = $q->fetch_assoc()) {
            $element['id'] = $row['id'];
            $element['name'] = $row['language'];
            $children = select_languages_hierarchical($row['id']);

            if ($children) {
                $element['children'] = $children;
            }

            $branch[] = $element;
        }
    }
    return $branch;
}

This produces an array that matches the nested list above, with nested arrays being in the children element of each array.

However, I simply cannot for the life of me, despite much brain-racking, Googling, and looking through oodles of recursion, aggregation-counting, and array-counting questions here on SO, figure out a way to create the counters that describe the number of descendent languages for each language.

Whatever I do, wherever I create, modify, and use my counter variables, and whatever I try counting (whether doing a ˋ$count++ˋ every time I iterate over a language, do a ˋcount($children)ˋ, etc.), I always end up with results where the counter is not reset when the function reaches a ‘higher’ level, so that I get lists like this instead:

  • Proto-Indo-European (12)
    • Celtic (6)
      • Insular Celtic (5)
        • Goidelic (2)
          • Irish
          • Manx
        • British (4)
          • Welsh
    • Germanic (9)
      • West Germanic (12)
        • Anglo-Saxon (14)
          • Anglic (15)
            • Old English

– Or something like that—the numbers and how they add up vary in the various different implementations I’ve attempted; but they all have in common that the counter keeps being increased throughout, without ever being reset. Or alternatively, if I do try to reset it at some point, naturally it gets reset on every iteration, leaving me with:

  • Proto-Indo-European (2)
    • Celtic (2)
      • Insular Celtic (1)
        • Goidelic (2)
          • Irish
          • Manx
        • British (1)
          • Welsh
    • Germanic (1)
      • West Germanic (1)
        • Anglo-Saxon (1)
          • Anglic (1)
            • Old English

Clearly, logic is not my strong suit here.

Can someone help my brain from spontaneously combusting and/or imploding by suggesting a way for me to achieve the kind of ‘intelligent tallying’ that I’m looking for here?

Upvotes: 1

Views: 1277

Answers (1)

Marc B
Marc B

Reputation: 360602

Thinking about it, instead of running a zillion recursive queries in PHP, you could just do a basic select * and build your tree in PHP, and do the counting there. Of cousre, this'd only be useful if you want the entire language tree.

$lang = array();
$sql = "SELECT * FROM languages";
... run query ...
while($row = fetch results) {
     // store this lang's node
     $lang[$row['id']]['name'] = $row['name']; 

     // add this language to its parent's child array
     $lang[$row['parent']]['children'][$row['id']] = $row['id'];

     // increment its parent's counter
     $lang[$row['parent']]['count']++;
}

Now, this will probably spew out a bunch of warnings about undefined arrays and whatnot, since I'm not testing for the existence of a parent before trying to updates it's counts. But that's just some basic if (!isset()) { initialize node } type stuff.

Output into your nested <ul> would be a recursive function, but since you've now got the child-node counts in your tree already, it'll be much simpler:

function output($id = 1) { // assuming "1" is your tree root node
   echo '<li>' . $lang[$id]['name'] . '(' . $lang[$id]['count'] . ')';
   if ($lang[$id]['count'] > 0) {
       echo '<ul>';
       foreach($lang[$id]['children'] as $childID) {
            output($childID);
       }
       echo '</ul>';
   }
   echo '</li>';
}

Upvotes: 1

Related Questions