Re: [PHP] Re: creating a threaded message system--sorting messages
Dan McCullough wrote:
I've come into this discussion pretty late so please bear with me if I
go over something that has been ruled out.
You are trying to print out in a threaded method the first post in a
thread followed by each post after that, that is a child/reply to that
post. Is that correct?
So something like
Example 1
Thread1
Post1
Post2
Post3
Post4
.
or
Example 2
Thread1
Post1
Post2 - reply to post 1
Post3 - reply to post 2
Post4 - reply to post 1
Post5 - reply to post 1
Post6 - reply to post 2
Post7 - reply to post 3
Not a valid example, because there is no guaruntee that the posts are in
order. In your example, the order could easily be:
Thread 1
Post 1
Post 6
Post 7
Post 2
Post 3
Post 4
Post 5
Since somebody can reply to any leaf in the tree at any time.
Example 1 is very common and is the easiest to implement. From what I
remember you would need a couple of DB tables for post, post_thread,
post_post, thread
So for your question thread isnt very relative but I thought I would
throw it in.
thread {
threadid int(11) auto_increment,
threadname
threadsort
...
thread_post {
threadid int(11)
postid int(11)
Tables that serve only to tie two other tables together are a waste. I
suggest you look up your normal forms again. But to sum up the
reasoning, there is no point to have thread_post because you can simply
have a threadid field in the post table, because it's a one-to-many
relationship. A post can't belong to more than one thread.
post {
postid int(11) auto_increment,
postname
posttext
...
post_post
postid int(11),
postid2 int(11)
Same thing, I think. A post can't have more than one parent, so you
might as well put the parent id into the post table. Unless you have one
post_post row for every parent that a post has. This spams the
database like nobody's business, but makes queries easier.
Please note I have two kids fighting over the cat, trying to cook
dinner and stave off a flood of water from the rising river so the SQL
structure is for example.
You can get everything in one query from the DB and lay it out based
on the id of the post, if you DB is properly indexed and setup and
queries are optimized you'll hardly notice a blip when the load gets
up. You do not want to be doing multiple queries on a page when one
well written query will do the trick.
I'm not seeing it. Unless you have a many to many relationship on
post_post, you're going to need multiple queries. Unless I'm missing
some SQL syntax that allows references to previously found rows. It's
been a long while since I did advanced SQL queries.
I think your example relies on getting everything in one query by
getting all posts with the same threadid, and then sorting by ID, but
the problem is that we don't want to sort posts by ID, since a higher ID
might could easily go before a post with a lower ID based on where
people replied.
Regards, Adam.
--
PHP General Mailing List (http://www.php.net/)
To unsubscribe, visit: http://www.php.net/unsub.php
Re: Re: [PHP] Re: creating a threaded message system--sorting messages
Thanks to everybody who posted on this thread. I wanted to post back
the solution I came up with after removing the DB query from the
recursion. In case anyone else is trying to accomplish the same thing,
this is how I solved it (criticisms welcome, and note that I have not
tested it extensively yet):
DB structure
table: discussion_posts
post_id (auto increment, unique, primary index)
parent_id (post_id corresponding to this post's parent)
discussion_id (to allow multiple discussions, not required but I added
a discussions
member_id (to identify the post to the particular member posting the post)
table as well to store the discussion description and unique ID for
each discussion)
dt_posted (date/time the post was posted)
subject (title of the particular post)
post_text (substance of the post)
So the user selects a particular discussion from a list of
discussions. We query the database for the post_id of the first post
in the discussion requested, this post will have a parent_id of '0' or
NULL since it has no parent. We then query the DB for all the posts in
the discussion joining the members table using member_id to grab the
member's first and last name (or any other member info desired). We
order this query info by dt_posted.
We then write the contents of our second query into a two-dimensional
array ($workArr):
while ([EMAIL PROTECTED]($result)) {
foreach ($row as $key = $value) {
if ($key==post_id) $numerKey=value;
$workArr[$key][$numerKey]=$value;
}
}
The processing of the threads into proper order looks like this:
function processthread($post_id, $workArr) {
echo ul class=\posting\;
echo h3{$workArr['subject'][$post_id]} (#{$post_id})/h3\n;
echo h4by {$workArr['first_name'][$post_id]}
{$workArr['last_name'][$post_id]} .bull; on .
fixdate($workArr['dt_posted'][$post_id]) . /h4;
echo li{$workArr['post_text'][$post_id]}/li\n;
echo h5reply to this/h5;
// find all children, call itself on those too
foreach ($workArr['post_id'] as $value) {
if ($workArr['parent_id'][$value]==$post_id) {
processthread($workArr['post_id'][$value], $workArr);
} // end if
} // foreach
echo /ul;
}
And somewhere in the HTML, where appropriate, the function
processthread is called for the first time passing it the $post_id
value we determined in the first query (the very first post of the
discussion) and the $workArr array.
Use of unordered lists for design/layout is helpful here since
browsers will by default indent lists within lists and list items
within their respective list. This saves some PHP and CSS troubles if
one were to use div or p structure instead, as I found out.
Apologies for any formatting issues and vagaries about the data
structure and variable naming in this post.
- Ben
--
PHP General Mailing List (http://www.php.net/)
To unsubscribe, visit: http://www.php.net/unsub.php
Re: [PHP] Re: creating a threaded message system--sorting messages
Ben Liu wrote:
Thanks to everybody who posted on this thread. I wanted to post back
the solution I came up with after removing the DB query from the
recursion. In case anyone else is trying to accomplish the same thing,
this is how I solved it (criticisms welcome, and note that I have not
tested it extensively yet):
DB structure
table: discussion_posts
post_id (auto increment, unique, primary index)
parent_id (post_id corresponding to this post's parent)
discussion_id (to allow multiple discussions, not required but I added
a discussions
member_id (to identify the post to the particular member posting the post)
table as well to store the discussion description and unique ID for
each discussion)
dt_posted (date/time the post was posted)
subject (title of the particular post)
post_text (substance of the post)
So the user selects a particular discussion from a list of
discussions. We query the database for the post_id of the first post
in the discussion requested, this post will have a parent_id of '0' or
NULL since it has no parent. We then query the DB for all the posts in
the discussion joining the members table using member_id to grab the
member's first and last name (or any other member info desired). We
order this query info by dt_posted.
We then write the contents of our second query into a two-dimensional
array ($workArr):
while ([EMAIL PROTECTED]($result)) {
foreach ($row as $key = $value) {
if ($key==post_id) $numerKey=value;
$workArr[$key][$numerKey]=$value;
}
}
The processing of the threads into proper order looks like this:
function processthread($post_id, $workArr) {
echo ul class=\posting\;
echo h3{$workArr['subject'][$post_id]} (#{$post_id})/h3\n;
echo h4by {$workArr['first_name'][$post_id]}
{$workArr['last_name'][$post_id]} .bull; on .
fixdate($workArr['dt_posted'][$post_id]) . /h4;
echo li{$workArr['post_text'][$post_id]}/li\n;
echo h5reply to this/h5;
// find all children, call itself on those too
foreach ($workArr['post_id'] as $value) {
if ($workArr['parent_id'][$value]==$post_id) {
processthread($workArr['post_id'][$value], $workArr);
} // end if
} // foreach
echo /ul;
}
And somewhere in the HTML, where appropriate, the function
processthread is called for the first time passing it the $post_id
value we determined in the first query (the very first post of the
discussion) and the $workArr array.
Use of unordered lists for design/layout is helpful here since
browsers will by default indent lists within lists and list items
within their respective list. This saves some PHP and CSS troubles if
one were to use div or p structure instead, as I found out.
Apologies for any formatting issues and vagaries about the data
structure and variable naming in this post.
- Ben
I think that will work, but there is one huge improvement you can make.
You are making millions of copies of your work array! Not only do you
pass the entire array by value recursively, but foreach makes copies of
the arrays it loops through! So who knows how many copies of the darned
work array are being spawned left and right. This can be a memory leak,
consuming lots of memory until it finishes the recursion.
The first thing you can do is tell the function the array is to be
handled by reference:
function processthread($post_id, $workArr) {
You never change the work array, I think, so you can just keep referring
back to the original. The second thing to do is to make the foreach work
on references instead of copies. I actually think that since what we
have in our function is now a reference, the foreach WILL NOT copy it.
But if it still does, there is always the fallback of doing a foreach on
array_keys($workArr). Then each $value would be the key, which you'd use
to reference $workArr.
Regards, Adam.
--
PHP General Mailing List (http://www.php.net/)
To unsubscribe, visit: http://www.php.net/unsub.php
Re: Re: [PHP] Re: creating a threaded message system--sorting messages
On 6/30/06, Adam Zey [EMAIL PROTECTED] wrote:
I think that will work, but there is one huge improvement you can make.
You are making millions of copies of your work array! Not only do you
pass the entire array by value recursively, but foreach makes copies of
the arrays it loops through! So who knows how many copies of the darned
work array are being spawned left and right. This can be a memory leak,
consuming lots of memory until it finishes the recursion.
Yipes!
The first thing you can do is tell the function the array is to be
handled by reference:
function processthread($post_id, $workArr) {
Added your suggestion, works fine.
You never change the work array, I think, so you can just keep referring
back to the original.
yes, that is correct. $workArr is never modified.
The second thing to do is to make the foreach work
on references instead of copies. I actually think that since what we
have in our function is now a reference, the foreach WILL NOT copy it.
Anyone have any ideas on this? Is the foreach loop in fact copying
$workArr? And how could we tell (test for it) if it were?
But if it still does, there is always the fallback of doing a foreach on
array_keys($workArr). Then each $value would be the key, which you'd use
to reference $workArr.
I'm sorry, you lost me here a bit.
Regards, Adam.
--
PHP General Mailing List (http://www.php.net/)
To unsubscribe, visit: http://www.php.net/unsub.php
Re: [PHP] Re: creating a threaded message system--sorting messages
Ben Liu wrote:
The second thing to do is to make the foreach work
on references instead of copies. I actually think that since what we
have in our function is now a reference, the foreach WILL NOT copy it.
Anyone have any ideas on this? Is the foreach loop in fact copying
$workArr? And how could we tell (test for it) if it were?
I should note that the DEFAULT behaviour of foreach is to make a copy of
the array you pass it. What I'm saying is that, now that we're passing
it a reference to an array instead of an actual array, is that enough to
stop it from copying? The manual seems to indicate that, but is a bit vague.
But if it still does, there is always the fallback of doing a foreach on
array_keys($workArr). Then each $value would be the key, which you'd use
to reference $workArr.
I'm sorry, you lost me here a bit.
I mean, do this:
foreach ( array_keys($workArr) as $key ) {
echo $workArr[$key]['foo'];
}
instead of this:
foreach ( $workArr as $key = $value ) {
echo $value['foo'];
}
Both let you do the same thing, you just reference data differently, and
the first example involves working with the original array, so foreach
has no chance to copy it. HOWEVER, if my above supposition about foreach
not copying a reference is correct, you wouldn't need to do this. It's
just a backup plan.
Regards, Adam.
--
PHP General Mailing List (http://www.php.net/)
To unsubscribe, visit: http://www.php.net/unsub.php
Re: [PHP] Re: creating a threaded message system--sorting messages
On Jun 30, 2006, at 5:04 PM, Adam Zey wrote:
I mean, do this:
foreach ( array_keys($workArr) as $key ) {
echo $workArr[$key]['foo'];
}
instead of this:
foreach ( $workArr as $key = $value ) {
echo $value['foo'];
}
Okay, I think I get the idea.
So using my code example...
this:
foreach ($workArr['post_id'] as $value) {
if ($workArr['parent_id'][$value]==$post_id) {
processthread($workArr['post_id'][$value], $workArr);
} // end if
would become this?:
foreach (arraykeys($workArr['post_id'] as $key) {
if ($workArr['parent_id'][$key]==$post_id) {
processthread($workArr['post_id'][$key], $workArr);
} // end if
Seems to work just fine. Will take the hamsters running in my brain a
little more time to fully understand it... :-)
Thanks again for all your help.
- Ben
Both let you do the same thing, you just reference data
differently, and the first example involves working with the
original array, so foreach has no chance to copy it. HOWEVER, if my
above supposition about foreach not copying a reference is correct,
you wouldn't need to do this. It's just a backup plan.
Regards, Adam.
smime.p7s
Description: S/MIME cryptographic signature
[PHP] Re: creating a threaded message system--sorting messages
Ben Liu wrote: This question might deviate from PHP into the domain of MySQL but I thought best to post here first. I'm building a message board system with PHP/MySQL. I'm trying to present the messages to the users in threaded order rather than flat. I'm having a lot of trouble figuring out how to sort the posts so they appear in the correct threaded order. I don't think I can do this purely with a SQL query. If it can be done this way, please suggest how and I'll take this question to the MySQL list. I think I have figured out the basic logic, I just have no idea how to translate it into code. Also, I may have the logic wrong. Anyhow this is what I have so far: relevant data structure loosely: post_id (unique, autoincrement, primary index) parent_id (if the post is a child, this field contains the post_id of its parent) ... 1) Query the database for all messages under a certain topic, sort by parent_id then post_id 2) Somehow resort the data so that each group of children is directly after their parent. Do this in order of ascending parent_id. Can this be done with usort() and some programatic logic/algorithm? How do you sort groups of items together rather than comparing each array element to the next array element (ie: sorting one item at a time)? Should this be done with a recursive algorithm? Anyone with experience writing code for this type of message board, or implementing existing code? Thanks for any help in advance. - Ben Just throwing an idea out there, but you can do the sorting entirely in the SQL query. The trick is to figure out the best way. The first idea that came to mind (and it sucks, but it works), is a text field with padded numbers separated by dots, and the number is the position in relation to the parent. So, with this: Post 1 Post 3 Post 5 Post 6 Post 4 Post 7 Post 2 Post 8 Now, to the helper field would contain this for each post: Post 1: 1 Post 2: 2 Post 3: 1.1 Post 4: 1.2 Post 5: 1.1.1 Post 6: 1.1.2 Post 7: 1.2.1 Post 8: 2.1 Now, by pure ascii sorting in that field, that would sort out to: Post 1: 1 Post 3: 1.1 Post 5: 1.1.1 Post 6: 1.1.2 Post 4: 1.2 Post 7: 1.2.1 Post 2: 2 Post 8: 2.1 Which is the correct sort order. The depth of the post (how far to indent it?) could be told in PHP by counting the number of periods, or storing it in the database. Now, how to figure out what to put in that field for each post? We need to do two things. First, each post needs to store the number of children. Next, when a new post is made, we do three things (Keeping in mind that in real life I'd pad each entry in the sort helper field with zeros on the left up to some large number): 1) Get the sort helper field of the parent and the parent's child count field 2) Take the parent's sort help field, and add on a period and the parent's child count plus one, insert the child. 3) Update the parent's child count. OK, now, this method sucks. It's slow, and limits the number of child posts to whatever you pad (In itself, not a big issue, if each post can only have, say, a thousand direct childs (which each themselves can have a thousand childs), not a huge issue). The slow part from ascii sorting everything is the problem, I'd think. I've never done threaded anything before, so I assume there's a better solution. I'm just saying that the job CAN be done entirely with SQL sorting. And probably faster than your proposed method of resorting everything once PHP gets ahold of it. It should be noted that you'd need each post to have a sort of superparent field that stored the topmost parent so that you could do something simple like selecting ten superparents and all their children. Regards, Adam. -- PHP General Mailing List (http://www.php.net/) To unsubscribe, visit: http://www.php.net/unsub.php
[PHP] Re: creating a threaded message system--sorting messages
Ben Liu wrote: SOLVED, almost. I read the article suggested by K.Bear and found the recommended solution to be a bit more complicated than I wanted to implement. I then found another way to do this using the existing Adjacency List Model through a recursive function. So basically, you query the database for the post_id of the very first post in the discussion. You then call a function that displays that post, searches for all children of that post and then calls itself recursively on each of the children it discovers. This works great for spitting out the posts in the proper order. Now I'm trying to figure out how to make sure the indenting looks right in the browser. - Ben Wouldn't that involve a separate SQL query for every post? Avoid that at all costs. That's insanely slow and wasteful. Recursive functions have no business using SQL queries. I'd suggest you start looking for a more sane method of doing this. Regards, Adam. -- PHP General Mailing List (http://www.php.net/) To unsubscribe, visit: http://www.php.net/unsub.php
RE: [PHP] Re: creating a threaded message system--sorting messages
Hello, As Adam pointed out, this can be deadly to your database, especially as the number of posts grows. If you want to go that route, I would recommend selecting all the posts in that particular thread and sorting the data out in PHP somehow. No need to slam your database with (potentially) hundreds of queries to display a discussion. Multiply that by several page views at once... If you don't mind the extra work and investigation, I would recommend downloading some PHP forum software that supports threaded discussion and see how they implement it. I found several listed in DMOZ: http://dmoz.org/Computers/Programming/Languages/PHP/Scripts/Forums/ Let us know what you come up with! I'd like to see how you work this out. This is a good computer science type of problem with practical application - the kind of stuff they should have taught me in school but never did. ~(o: Best of luck, -K.Bear SOLVED, almost. I read the article suggested by K.Bear and found the recommended solution to be a bit more complicated than I wanted to implement. I then found another way to do this using the existing Adjacency List Model through a recursive function. So basically, you query the database for the post_id of the very first post in the discussion. You then call a function that displays that post, searches for all children of that post and then calls itself recursively on each of the children it discovers. This works great for spitting out the posts in the proper order. Now I'm trying to figure out how to make sure the indenting looks right in the browser. - Ben Wouldn't that involve a separate SQL query for every post? -- PHP General Mailing List (http://www.php.net/) To unsubscribe, visit: http://www.php.net/unsub.php
Re: [PHP] Re: creating a threaded message system--sorting messages
I've come into this discussion pretty late so please bear with me if I
go over something that has been ruled out.
You are trying to print out in a threaded method the first post in a
thread followed by each post after that, that is a child/reply to that
post. Is that correct?
So something like
Example 1
Thread1
Post1
Post2
Post3
Post4
.
or
Example 2
Thread1
Post1
Post2 - reply to post 1
Post3 - reply to post 2
Post4 - reply to post 1
Post5 - reply to post 1
Post6 - reply to post 2
Post7 - reply to post 3
Example 1 is very common and is the easiest to implement. From what I
remember you would need a couple of DB tables for post, post_thread,
post_post, thread
So for your question thread isnt very relative but I thought I would
throw it in.
thread {
threadid int(11) auto_increment,
threadname
threadsort
...
thread_post {
threadid int(11)
postid int(11)
post {
postid int(11) auto_increment,
postname
posttext
...
post_post
postid int(11),
postid2 int(11)
Please note I have two kids fighting over the cat, trying to cook
dinner and stave off a flood of water from the rising river so the SQL
structure is for example.
You can get everything in one query from the DB and lay it out based
on the id of the post, if you DB is properly indexed and setup and
queries are optimized you'll hardly notice a blip when the load gets
up. You do not want to be doing multiple queries on a page when one
well written query will do the trick.
Either way if this is more what you are looking for we can get into
specifics later.
Dan
On 6/29/06, KermodeBear [EMAIL PROTECTED] wrote:
Hello,
As Adam pointed out, this can be deadly to your database, especially as the
number of posts grows. If you want to go that route, I would recommend
selecting all the posts in that particular thread and sorting the data out
in PHP somehow. No need to slam your database with (potentially) hundreds of
queries to display a discussion. Multiply that by several page views at
once...
If you don't mind the extra work and investigation, I would recommend
downloading some PHP forum software that supports threaded discussion and
see how they implement it. I found several listed in DMOZ:
http://dmoz.org/Computers/Programming/Languages/PHP/Scripts/Forums/
Let us know what you come up with! I'd like to see how you work this out.
This is a good computer science type of problem with practical application -
the kind of stuff they should have taught me in school but never did. ~(o:
Best of luck,
-K.Bear
SOLVED, almost. I read the article suggested by K.Bear and found the
recommended solution to be a bit more complicated than I wanted to
implement. I then found another way to do this using the existing
Adjacency List Model through a recursive function. So basically, you
query the database for the post_id of the very first post in the
discussion. You then call a function that displays that post, searches
for all children of that post and then calls itself recursively on
each of the children it discovers. This works great for spitting out
the posts in the proper order. Now I'm trying to figure out how to
make sure the indenting looks right in the browser.
- Ben
Wouldn't that involve a separate SQL query for every post?
--
PHP General Mailing List (http://www.php.net/)
To unsubscribe, visit: http://www.php.net/unsub.php
--
PHP General Mailing List (http://www.php.net/)
To unsubscribe, visit: http://www.php.net/unsub.php
