The answer is probably obvious but not to me at this moment, so I was wondering if somebody who is better with sorting algorithms can help lead me in the right direction. This is not homework, I am legitimately trying to work within an existing design for something work related.
Essentially I start with an unordered list of data objects that represent something similar to forum comments. These objects MAY explicitly have one and only one direct parent. In other words
Parent (1...*) ----------- (1...1) Child
A child has a reference to its parent, however a parent cannot see its children (explicitly).
Typically when sorting a list one would pass a comparator which given any two data objects in the collection should return an integer number that represents the distance between the two objects in a graph. The distance between two completely unrelated comments will be based on the Timestamp value of the data object.
The issue is that any two data objects can and should only be compared by timestamp with other data objects from the same parent branch. Here is an example:
DO1 - Time(1000ms)
|___DO3 - Time(5000ms)
DO2 - Time(2000ms)
DO1 and DO2 compared will result in a negative number so those two are sorted correctly relative to each other. DO3 to DO1 is likewise correct because I can assume that any branch above a comment must be less than. The problem comes with comparing DO3 to DO2. I thought that I should compare the highest order parent to DO2 in this case and that works until there are DO children under DO3.
I am trying to figure out if the current object graph is even enough information for a comparator to correctly return an appropriate number for any two comparisons. Perhaps the comparator needs to be initialized with the unordered list first so that it can build a tree structure where I can see a list of children from any given parent explicitly? Or perhaps I need to refactor? At this stage I am not concerned about performance. Thank you.