<!DOCTYPE html>
<head>
<meta charset="utf-8" />
<title>Linear Recursion Example, © Kroc Camen 2011 CC-BY</title>
<style>
article {border: 1px solid blue; margin: 20px; padding: 20px;}
</style>
</head><body>
<?php

//PHP 5.3 issues a warning if the timezone is not set when using date-related commands
date_default_timezone_set ('UTC');
error_reporting (-1);

$comments = array (
=> array (
"parent" => 0, "datetime" => "2011/01/04 15:25:00""name" => "Alice",
"text"   => "Mario is better than Sonic! Mario has always had successful games, where".
"as Sonic’s games have been sucking for a decade"
),
=> array (
"parent" => 1, "datetime" => "2011/01/04 15:27:00""name" => "Bob",
"text"   => "Er, aren’t we forgetting Hotel Mario?"
),
=> array (
"parent" => 0, "datetime" => "2011/01/04 15:32:00""name" => "Alex",
"text"   => "*Sits in the corner curled into a ball rocking…* Don’t want Shadow… Don’t want Shadow…"
),
=> array (
"parent" => 1, "datetime" => "2011/01/04 16:02:00""name" => "Bill",
"text"   => "At least Sega have been trying new things; Nintendo have been making the same damn".
"game for the last 25 years!"
),
=> array (
"parent" => 4, "datetime" => "2011/01/04 16:14:00""name" => "Charlie",
"text"   => "Everything after Sonic and Knuckles doesn’t exist in my eyes."
)
);

/* === sort ============================================================================================================= */

//this function will be used next to tag each comment in such a way it can be sorted by both nesting and date
//this works by chaining together the comment timestamps of related comments,
//e.g. A <- first comment
// A|B <- child comment
// A|B|C <- another child
// A|B|D <- sibling
// E <- sibling of first comment
//
function sortcode (&$comments$comment_id) {
//shorthand…
$parent = @$comments[$comment_id]['parent'];
//if a parent exists, get its sort code first
return ($parent sortcode ($comments$parent).'|' '').
//and then append this comment’s code (an alpha-numeric version of the comment timestamp)
base_convert (strtotime ($comments[$comment_id]['datetime']), 1036);
}

//apply the sort codes to the comments, and also collect them into an array which we will use to sort
//the `$comments` array to have comments in the correctly nested order
foreach ($comments as $comment_id => &$comment)
//can’t use `$comment['sort]` because you can’t add to an array whilst inside it with foreach (byref)
$sort[] = $comments[$comment_id]['sort'] = sortcode ($comments$comment_id)
;
//sort the comments using the sort codes. this works by having an array of sortable alpha-numeric keys that are in the same
//original order as the comments that they came from. `array_multisort` then sorts both, matching any change in order in
//`$sort` with `$comments` too
array_multisort ($sortSORT_ASC$comments);

/* === output =========================================================================================================== */

//generate the nested HTML from the flat list of comments
reset ($comments); echo template_comments ($comments);

/* watch out, this gets complex! the list of comments is in a linear array and we have to turn this into a nested thread
   of comments. we do this by iterating over the linear array and recursing to do HTML nesting, however the array pointer
   continues to move linearly! this is considered *bad* programming just about anywhere, but it does solve our problem
   incredibly efficiently */
function template_comments (&$comments) {
//retrieve the current comment from the list. the first time this function is called, this will obviously be the
//first comment--though ensure you have called `reset ()` on the array if it’s been used previously!
$comment current ($comments);

//the sort code that we applied earlier strings together comment timestamps in a chain according to depth,
//i.e. "ABC|DEF|GHI". by splitting the sort code we can determine the current nesting depth of the comment
$this_depth count (explode ('|'$comment['sort'])) - 1;

//prepare the current comment. note how this is stored in a variable with no context to the previous comments.
//this is where the recursion comes into play, appending trees of comments together whilst still operating on a
//array, travelled linearly
$html = <<<HTML
<article>
<header>by:
${comment['name']} on:${comment['datetime']}</header>

${comment['text']}


HTML;
//we leave `<article>` open, as any child comments will go inside

//get the next comment: if we have run out of comments, then finish the HTML for this comment
if (!$comment next ($comments)) return $html "</article>\n";

//determine the depth of the next comment so that we know if this will be added in parallel,
//as a child, or fold back to the parent
$next_depth count (explode ('|'$comment['sort'])) - 1;

//next comment will be a child?
if ($next_depth $this_depth) {
//insert the next comment within the current one (child). note that this recursive call will continue to
//insert child and sibling comments until that branch is complete and returns back to this point here
$html .= template_comments ($comments);

//NOTE: when we recursed (above), it will have moved the array pointer forward 1 *OR MORE* places;
//which means that `$comment` is no longer pointing to the current location in the comment list!
//let’s get a new reference (if we’ve not run out of comments)
if (!$comment current ($comments)) return $html "</article>\n";

//get the depth level of this next comment; we’ve handled all children already so it could only be one of
//two possibilities: either it’s a sibiling of the comment we started out with at the top of this function
//or it’s part of a parent thread and this particular tree has stopped branching
$next_depth count (explode ('|'$comment['sort'])) - 1;
}

//is the next comment a sibling of the current comment?
//(that is, it is another reply to the same parent comment)
if ($next_depth == $this_depth
//append the next comment at the same level, no nesting
$html .= "</article>\n\n" template_comments ($comments)
;

//lastly, when all other options have been expended, the next comment is not part of this thread
//e.g. A
// A|B
// A|B|C
// A|B|D
// E <- this comment is the beginning of a new thread

//we fold back through the recursion, this will automagically drop us back to the correct recursion level where
//the next comment is a sibling of another comment
return $html "</article>\n";
}

?></body>