Complex sortin of an array of objects...

[linus72982]

Phew, okay, I'm at my wits end on how to accomplish this task.  My client wants a forum program, but she wants it different from normal in that the forum page won't show just the main threads where you would have to click to see the replies, etc - she wants the forum page to display threads and replies in a tiered fashion.  Something like this:

 

- Thread 1
   - Reply 1-1
      - Reply 1-1-1
   - Reply 1-2
   - Reply 1-3
      - Reply 1-3-1
         - Reply 1-3-1-1
            - Reply 1-3-1-1-1
         - Reply 1-3-1-2
      - Reply 1-3-2
- Thread 2
- Thread 3
   - Reply 3-1

etc

 

So, the threads should be arranged in order of their property timeLastChanged (which is updated on replies to it, replies to replies of it, edits, etc) which produces the "bumping" functionality.  Then the replies under it should be arranged in order of their property timeStarted (which is the timestamp of when it got created).  Now, I have the script so far to the point where I have 3 arrays of objects (stickyObjs, mainsObjs, replyObjs) and these objects are instances of Post with their properties being their database values (author, timeStarted, subject, etc).  Now, I have thought to arrange these arrays into one big array of objects in the order that they should appear on the page (don't worry about the indent, that's done elsewhere.)  Anyway, how would I go about sorting these arrays into one big array of objects in the order they should appear with those two sorting criteria above (sorting criteria is stickies, 1st main in the order of last available timeLastChanged, any replies to mains, replies to replies, ad nauseum in order of timeStarted, then the next main in the order of timeLastChanged, etc.)  I have gone through many possible ways, all of which are incredibly complex and involve many copies of arrays and pointers to objects in arrays and iteration counters and GAH!  Does anyone know of an easy way to accomplish this sorting?  Here is what I have so far:

 

class Category {

public $title;
public $majCatID;
public $catID;
public $modLevel;
public $postingLevel;
public $hostedByUID;
public $order;
public $shortName;
public $info;
public $stickyObjs;
public $mainsObjs;
public $replyObjs;
private $database;

public function __construct($catID) {
	$this->database = new TBDatabase;
	$result = $this->database->getIntRow(CAT_TABLE, 'catID', $catID);
	$row = $this->database->fetchAssoc($result);
	$this->title = $row['title'];
	$this->majCatID = $row['majCatID'];
	$this->catID = $row['catID'];
	$this->modLevel = $row['modLevel'];
	$this->postingLevel = $row['postingLevel'];
	$this->hostedByUID = $row['hostedByUID'];
	$this->order = $row['order'];
	$this->shortName = $row['shortName'];
	$this->info = $row['info'];
	$this->pointer = 0;
	}
public function sortPosts() {
	$table = $this->shortName."_threads";
	$this->getStickyObjs();
	$numStickies = count($this->stickyObjs);
	$this->getMainObjs();
	$numMains = count($this->mainsObjs);
	$this->getReplyObjs();
	$numReplies = count($this->replyObjs);
	}
private function getStickyObjs() {
	$result = $this->database->getPostResources($this->shortName, $this->catID, "AND isSticky = 1");
	if (!$result) {
		$this->stickyObjs = false;
		return;
		}
	$i = 1;
	while ($row = $this->database->fetchAssoc($result)) {
		$this->stickyObjs[$i] = new Post($row);
		$i++;
		}
	return;
	}
private function getMainObjs() {
	$result = $this->database->getPostResources($this->shortName, $this->catID, "AND isReply = 0");
	if (!$result) {
		$this->mainsObjs = false;
		return;
		}
	$i = 1;
	while ($row = $this->database->fetchAssoc($result)) {
		$this->mainsObjs[$i] = new Post($row);
		$i++;
		}
	return;
	}
private function getReplyObjs() {
	$result = $this->database->getPostResources($this->shortName, $this->catID, "AND isReply != 0");
	if (!$result) {
		$this->replyObjs = false;
		return;
		}
	$i = 1;
	while ($row = $this->database->fetchAssoc($result)) {
		$this->replyObjs[$i] = new Post($row);
		$i++;
		}
	return;
	}
}

 

Thanks!

[btherl]

I hope you are sorting threads rather than posts.. otherwise it could get very complicated.

 

Regardless of which you are sorting, if you can express your sorting by comparing two objects and saying which should go first, then the way to go is usort() with a custom sort function.  But if your sorting is not that simple (such as sorting posts but expecting them to end up with a thread structure), then I wouldn't even attempt that - I would put them into threads first and then sort.

[linus72982]

I hope you are sorting threads rather than posts.. otherwise it could get very complicated.

 

Regardless of which you are sorting, if you can express your sorting by comparing two objects and saying which should go first, then the way to go is usort() with a custom sort function.  But if your sorting is not that simple (such as sorting posts but expecting them to end up with a thread structure), then I wouldn't even attempt that - I would put them into threads first and then sort.

 

Well, I call main threads "threads" and replies I call "replies" - they are all objects of the "Post" class - meaning they are all a post of some sort, but they are separated into 3 different arrays of objects (replyObjs, mainsObjs, and stickyObjs).

 

As to putting them in threads first, do you mean sorting posts into threads first and then sorting?  I'm still left with the same problem.  The stickies and mains are easy, it's the replies that get very tiered and even within their parent main thread as a structure, they are still quite difficult to sort the way I showed up top.  It's all very confusing.

[btherl]

Hmm, so is the problem that you have some threads (aka mains), and a bunch of replies, and you're not sure how to put those replies into the tree-like structure in your first post?

 

The first way I think of is to do it like this:

 

For each thread t

  For each reply r

    Is r a reply to t?  If yes, put it in a replies array under t

    For each reply rr

      Is rr a reply to r?  If yes, put it in a replies array under r

      .. and recursively call a function that looks for replies to rr, and so on until you get to a reply with no replies

    End for each (rr)

  End for each ®

End for each (t)

 

Then you have everything in a tree structure.  This algorithm is not the most efficient, and it's probably better to index the replies by what they are replying to first, but it'll work.  Then you can sort your threads by stickiness and "last reply", and the replies by "time started".

 

Have you already worked out how to calculate "last reply" time for the threads?  If not you can calculate it while creating the tree structure above - each time you add a reply under the thread (or a reply under a reply under a thread, and so on) then you can remember which reply has the most recent time.  Then once you've found all replies, assign that time to the entire thread as the "last reply" time.

 

The basic strategy I'm using is to put everything into the right structure first, and calculate any additional metadata (like the most recent reply for a thread) first.  And then the sorting should be easy (in theory).

[linus72982]

I figured it out.  I ended up taking a different approach, actually.  Instead of grabbing every post into 3 arrays of objects, I found it worked easier with nested while loops - basically grab the result resource for only replies that are replies to the current main I'm working with and then if they have replies, loop the same function.  This is kind of what I was trying to do last night with nested foreach loops trying to sort the arrays, but this is much less resource consuming I think.

 

The biggest piece I was missing was how to make a variable unique to only that "instance" of a function.  I was having trouble with functions looping to themselves to find more replies because all of my variables would change so I came up with:

 

private function getReplies($iteration) {
	$varIterate = "resultReplies".$iteration;
	$varIterate2 = "rowReplies".$iteration;
	$$varIterate = $this->database->getPostResource($this->table, $this->catID, "AND isReply = ".$this->orderedObjs[$this->pointer]->TID);
	while ($$varIterate2 = $this->database->fetchAssoc($$varIterate)) {
		$this->pointer++;
		$this->orderedObjs[$this->pointer] = new Post($$varIterate2);
		if ($iteration < 6)
			$this->orderedObjs[$this->pointer]->tierIndent = $iteration * 20;
		else
			$this->orderedObjs[$this->pointer]->tierIndent = 100;
		if ($this->orderedObjs[$this->pointer]->numReplies > 0) {
			$iteration2 = $iteration + 1;
			$this->getReplies($iteration2);
			}
		}
	return;
	}

 

So, now I send the function a "seed" in the form of $iteration.  Then I had the issue whereby incrementing $iteration within the same "instance" of the function would change the value of iteration before I left that function, so I added a second variable ($iteration2) that could change as much as it wanted as it wasn't tied to any actual functionality and used that as the seed to send the function, the variables to use for each iteration of the function would have a different name as I essentially am adding $iteration2 to each variable variable name.  Each iteration it counts up so if I have 4 nested functions working their loops, each is working off variables of a different name so they don't mess with each other   That was the key.

[btherl]

That is pretty cryptic code there.  I'm not sure why you had trouble, as any variable not declared global is local to a function.  If you call the same function recursively you will get new copies of those variables for each call.

 

The common situations where variables are not function scoped are:

 

1.  $this->var is object instance scope

2.  class::var is class scope

3.  "global $var" makes $var global scope for that function only (You can still use $var locally within other functions)

4.  When dealing with external resources like databases, some sharing may occur.  But typically, a resource named with a local variable (such as $result = mysql_query(...)) will be local to the function only.