I have a flat list of tasks, like this:
<tasks>
<task id="b">
<label>Task B</label>
<depends on="a"/>
</task>
<task id="a.1" parent="a">
<label>Task A.1</label>
<depends on="a.2"/>
</task>
<task id="a.2" parent="a">
<label>Task A.2</label>
</task>
<task id="a.2.i" parent="a.2">
<label>Task A.2.i</label>
</task>
<task id="a">
<label>Task A</label>
</task>
</tasks>
(Actually, each task is an indepedent file in some directory, the files are
concat-ed together to generate the flat list you see here.)
Note that each task may have a single parent, and each may have zero or more
tasks that it depends upon, as long as they share the same parent. The
tasks appear in an aribrary order (due to the nature of how the document is
constructed).
I've built an XSLT stylesheet that converts this flat list into a nested
list, according to the parent attribute (by simple recursion over the tasks
whose parent attribute equals my id attribute). The result looks like this:
<tasks>
<task id="b">
<label>Task B</label>
<depends on="a"/>
</task>
<task id="a">
<label>Task A</label>
<task id="a.1" parent="a">
<label>Task A.1</label>
<depends on="a.2"/>
</task>
<task id="a.2" parent="a">
<label>Task A.2</label>
<task id="a.2.i" parent="a.2">
<label>Task A.2.i</label>
</task>
</task>
</task>
</tasks>
I later convert this nested list into HTML, in a pretty straighforward
fashion. The result looks something like this:
1) Task B
2) Task A
2.1) Task A.1
2.2) Task A.2
2.2.1) Task A.2.i
Note that the <depends> element defines a partial order among the children
of a given task. (I can, at creation time, restrict the <depends> values so
that a task only depends upon its siblings, and that cycles are prevented.)
Hence I'd like to be able to display this final list in its logical order,
i.e., a task only appears after the siblings it depends upon. E.g., for the
above list, this would be:
1) Task A
1.1) Task A.2
1.1.1) Task A.2.i
1.2) Task A.1
2) Task B
I realize there are several total/linear orderings represented by the
partial ordering defined by <depends>, but I'm OK with that. E.g., if I've
got:
A -> C A---C
B -> C (which is / for the poset friendly)
B -> D B---D
Then any of:
A,B,C,D
B,A,C,D
A,B,D,C
B,A,D,C
B,D,A,C
is acceptable.
Can anyone suggest how I might do this? I've played around with logic like
'before I process a task, process all of the siblings upon which the task
depends', but this suffers from several problems, at least in my
implementations.
I'm using John Clark's XP/XT, and while I'm not entirely opposed to a
XT-specific solution, I prefer a parser independent solution if the
performance is reasonable.
Thanks,
-rod
______________________________________________________
Get Your Private, Free Email at http://www.hotmail.com
XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list