<!DOCTYPE html>
<!-- ========================================== kroc camen of camen design ============================================= -->
<title>code · Creating a Nested HTML Comment Thread From a Linear List, by Magic!</title>
<link rel="stylesheet" type="text/css" href="/design/design.css" />
<meta name="viewport" content="width=device-width, maximum-scale=1.0, user-scalable=no" />
<link rel="alternate" type="application/rss+xml" href="/code/rss" title="Just code" />
<link rel="canonical" href="/code/linear_recursion" />
<!-- =================================================================================================================== -->
	<h1><a href="/" rel="index">
		Camen Design
		<li><a href="/">all</a></li>
		<li><a href="/projects">projects</a></li>
		<li><a href="http://forum.camendesign.com">forum</a></li>
		<li><a href="/quote/">quote</a></li>
		<li><a href="/writing/">writing</a></li>
		<li><a href="/blog/">blog</a></li>
		<li><a href="/photo/">photo</a></li>
		<li><a href="/code/" rel="tag">code</a></li>
		<li><a href="/art/">art</a></li>
		<li><a href="/link/">link</a></li>
		<li><a href="/poem/">poem</a></li>
		<li><a href="/audio/">audio</a></li>
		<li><a href="/web-dev/">web-dev</a></li>
		<li><a href="/annoyances/">annoyances</a></li>
		<li><a href="/eve/">eve</a></li>
		<li><a href="/code-is-art/">code-is-art</a></li>
		<li><a href="/inspiration/">inspiration</a></li>
		<li><a href="/windows/">windows</a></li>
		<li><a href="/gift/">gift</a></li>
		<li><a href="/gaming/">gaming</a></li>
		<li><a href="/mac/">mac</a></li>
		<li><a href="/osnews/">osnews</a></li>
		<li><a href="/c64/">c64</a></li>
		<li><a href="/linux/">linux</a></li>
	<a rel="previous" href="/code/video_for_everybody">
		older article →
	</a><a rel="next" href="/code/the_next_web">
		← newer article
<!-- =================================================================================================================== -->
	<!-- date published or updated -->
	<time pubdate datetime="2011-01-04T21:47:00+00:00">
		<sup>9:47<abbr>pm</abbr> • 2011</sup>
		<abbr title="January">Jan</abbr> 4
	<!-- categories -->
		<li><a href="/code/linear_recursion" rel="bookmark tag">code</a></li>
		<li><a href="/web-dev/linear_recursion">web-dev</a></li>
		<li><a href="/code-is-art/linear_recursion">code-is-art</a></li>
	<!-- licence -->
		<a rel="license" href="http://creativecommons.org/licenses/by/3.0/deed.en_GB">c</a>
		share + remix
	<!-- enclosure -->
	<a type="application/x-httpd-php" href="/code/linear_recursion/linear_recursion.php">
		linear_recursion <em></em>
<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -->
<h1>Creating a Nested HTML Comment Thread From a Linear List, by Magic!</h1>
	<strong>If you have ever created a comment system for a website that supports nested replies</strong> you will know
	that one of the messiest parts of the code is taking a flat list of comments from the database, where usually you
	have a field for each comment that states what the parent comment is to that comment, and outputting a nested HTML
	structure where replies sit within their respective comments.
	<a href="code/linear_recursion/thread.png" type="image/png">
		<img src="/code/linear_recursion/thread.jpg" alt="Screenshot of a typical comment thread" width="640" height="387" />
	<figcaption>A typical comment thread showing nested replies</figcaption>
	Normally, the method to deal with this is to convert this linear list into a node tree, replicating the
	relationships of the comments in a programming object which you can then recurse through and output.
	The problem with this approach is that it’s hard to do and requires lots of separate functions and objects and you
	end up writing a thousand lines of code in order to do it properly and cleanly.
	The alternative method is to do it procedurally, limit the nesting depth to a certain amount and just write
	absolutely crazy, insane kitten-killing, spaghetti code (<a href="http://xkcd.com/292/">with GOTOs</a>) that no
	mother could love. It’ll get the job done quickly, but it will eat at your soul all the way from the hard drive.
	I was not prepared to do it either way, so I invented a hybrid approach that achieves the end result in very little
	code and as elegantly as possible. The down side is that you should never code this way unless you know what you are
		There once was a master programmer who wrote unstructured programs. A novice programmer, seeking to imitate
		him, also began to write unstructured programs. When the novice asked the master to evaluate his progress,
		the master criticized him for writing unstructured programs, saying, “What is appropriate for the master
		is not appropriate for the novice. You must understand the Tao before transcending structure.”
	<cite><a href="http://www.canonical.org/~kragen/tao-of-programming.html">The Tao of Programming</a></cite>
	My code <em>linearly traverses an array using a recursive function</em>. That, in just about any programming school
	of thought is <em>bad</em> coding and not to be done! However, I am a hacker, and transcend to a skill level where
	all wrongs are also tools to be used and abused for art. This code works, and that is all that matters—there is no
	good or bad, just code.

<h2 id="initialise">Initialise Data</h2>
	Let’s initialise the code using an example table of data, like this. You could imagine that this has been pulled
	from an SQL query. Each comment has a <samp>parent</samp> field that will point to the ID of the comment it is in
	reply to, a parent of “<samp>0</samp>” will mean the comment is at root level.

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

<h2 id="nestsort">Nest and Sort</h2>
	First, we need to sort these comments. Sorting by date alone won’t really work because the newest comment might be
	a reply to an old comment in the middle of the thread. We need to first get the comment nesting sorted and then sort
	each branch of the tree by date.
	The answer to this that I stumbled upon is that when you sort words alphabetically the presence of two words that
	start with the same letter is handled by comparing the second letters, and if they are the same, so on through the
	letters until some result is reached. I imagined an alphabetic structure below where each reply inherited the
	parent’s identifier, and each new branch increased the identifier in alphabetical order:

<pre>A	&lt;- first comment
A|B	&lt;- child comment
A|B|C	&lt;- another child
A|B|D	&lt;- sibling
E	&lt;- sibling of first comment</pre>

	We achieve this by encoding the comment date/time to base 36 (A-Z, 0-9) which can easily be sorted. When a comment
	has a parent, we chain the “sort codes” together to make sibling comments share part of the same code, and thus
	appear next to each other.

<pre><code>function sortcode (&amp;$comments, $comment_id) {
	$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']), 10, 36);

//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 =&gt; &amp;$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 ($sort, SORT_ASC, $comments);

	Now we have a linear array, but sorted according to the nesting depth and time of the comment!

<h2 id="output">Output HTML</h2>

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

function template_comments (&amp;$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 = &lt;&lt;&lt;HTML
	&lt;header&gt;by:${comment['name']} on:${comment['datetime']}&lt;/header&gt;

	//we leave `&lt;article&gt;` 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 . "&lt;/article&gt;\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 &gt; $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 . "&lt;/article&gt;\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 .= "&lt;/article&gt;\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	&lt;- 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 . "&lt;/article&gt;\n";

	The <a href="/code/linear_recursion/linear_recursion.php">final code</a> (attached to this article) outputs a
	correctly nested set of comments:
<img src="/code/linear_recursion/result.png" alt="Screenshot of nested comments in a web browser" width="640" height="566" />
	I hope this has been most educational.
	<br /><br />
	Kind regards,<br />
	<em>Kroc Camen.</em>
<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -->
	<nav><a href="http://forum.camendesign.com">‹ Discuss this in the Forum ›</a></nav>
	<a href="mailto:kroc@camendesign.com">kroc@camendesign.com</a>
		<a href="/code/linear_recursion.rem">Rem</a> •
		<a href="/code/linear_recursion.html">HTML</a> •
		<a href="/design/">CSS</a> •
		<a href="/.system/">PHP</a> •
		<a href="/.htaccess">.htaccess</a>
	<form method="get" action="https://duckduckgo.com">
		<input type="hidden" name="sites" value="camendesign.com" />
		<input type="search" name="q" placeholder="search…" />
		<input type="submit" value="Go" />
<!-- =================================================================================================== code is art === -->