threads.php

<?php

function get_posts() {
    $db = new PDO("mysql:host=localhost;dbname=threads", "user", "password");

    $pStmt = $db->query("SELECT * FROM post");
    $posts = $pStmt->fetchAll(PDO::FETCH_ASSOC);
    $pStmt->closeCursor();

    // Convert flat posts array to threaded dictionary

    // Recursively find a parent in the thread, return a reference to it
    function &find_parent(&$posts, $id) {
        $ref = null;

        foreach ($posts as $i => $p) {
            if ($i == $id) {
                $ref =& $posts[$i];
                break;
            }

            if (isset($p["replies"])) {
                $in_replies =& find_parent($posts[$i]["replies"], $id);
                if ($in_replies) {
                    $ref =& $in_replies;
                    break;
                }
            }
        }

        return $ref;
    }

    $thread = array();
    // Run until all posts have been threaded (maybe infinite if there's a bug :)
    while (count($posts) > 0) {
        // Foreach post
        foreach ($posts as $i => $p) {
            // If the post has a parent, find a reference to it in the thread
            if (!is_null($p["parent"])) {
                $parent =& find_parent($thread, $p["parent"]);
                if ($parent) {
                    // Create the replies array if it doesn't exist
                    if (!isset($parent["replies"])) {
                        $parent["replies"] = array();
                    }
                    // Append it to replies
                    $parent["replies"][$p["id"]] = $p;
                    // Remove from the unsorted posts list
                    unset($posts[$i]);
                }
                // Otherwise, wait until it shows up in the thread
            } else {
                // Top-level posts can be threaded immediately
                $thread[$p["id"]] = $p;
                // Remove from the unsorted posts list
                unset($posts[$i]);
            }
        }
    }
    return $thread;
}


function print_posts(array $posts) {
    echo "<ul>";
    foreach ($posts as $id => $post) {
        echo "<li>[" . $id . "] " . $post["post"];
        if (isset($post["replies"]) && is_array($post["replies"])) {
            print_posts($post["replies"]);
        }
        echo "</li>";
    }
    echo "</ul>";
}
print_posts(get_posts());

threads.sql

CREATE TABLE `post` (
  `id` int(11) PRIMARY KEY AUTO_INCREMENT,
  `post` text,
  `parent` int(11) DEFAULT NULL
);

INSERT INTO `post` VALUES (1,'Top-level comment',NULL);
INSERT INTO `post` VALUES (2,'Top-level comment 2',NULL);
INSERT INTO `post` VALUES (3,'reply to #2',2);
INSERT INTO `post` VALUES (4,'reply to #3',3);
INSERT INTO `post` VALUES (5,'Top-level',NULL);
INSERT INTO `post` VALUES (6,'Reply to #2',2);
INSERT INTO `post` VALUES (7,'Reply to #2',2);
INSERT INTO `post` VALUES (8,'Reply to #2',2);
INSERT INTO `post` VALUES (9,'Reply to #2',2);
INSERT INTO `post` VALUES (10,'Reply to #7',7);
INSERT INTO `post` VALUES (11,'Reply to #7',7);
INSERT INTO `post` VALUES (12,'Reply to #10',10);
INSERT INTO `post` VALUES (13,'Reply to #12',12);