Re: topological sort

Subject: Re: topological sort
From: "Peter B. West" <pbwest@xxxxxxxxxxxxxx>
Date: Sun, 12 Nov 2000 10:16:38 +0000
Joerg,

I did not see this response; I must have dropped a digest somewhere. 
I'm not a logician or a mathematician so I don't follow your discussion
of the select conditions, I'm afraid.

Joerg wrote:
....
> > I finally decided that the select was:
> > NOT processed
> > AND (
> > NOT (
> > field/type/ref exists
> > AND
> > NOT field/type/ref reference processed
> > )
> > )
> 
> Should be correct.
> The problem here is that quantifiers and predicates are (implicitely)
> used. The condition should read
>   NOT processed
>   AND NOT EXISTS field :
>     EXISTS type/ref
>     AND NOT type/ref : processed
> A count()=0 means NOT EXISTS.
> 
....
> > becomes
> > NOT processed
> > AND (
> > field/type/ref does NOT exist
> > OR
> > field/type/ref reference processed
> > )
> 
> More precisely
>   NOT processed
>   AND NOT EXISTS field/type/ref
>       OR FORALL field/type/ref : processed
> You are distributing over a predicate and over quantifiers. A FORALL
> would have a representation like
>   count(node[predicate])=count(node)
> 
....
> One select constructs the actualprocessed variable, the other produces
> the desired output, in my example only the struct name. In the real
> application, processing of struct elements is more complex.
> 
> Well, rescanning the actualprocessed variable may be faster than doing
> two selects. I will check it.

Can you just do the struct element processing at the point each node is
resolved?
....
> > Anyway, the
> > following stylesheet seems to work in the same way as the orginal, on
> > the same data.
> 
> Incomplete test case :-) Try again after inserting either
>     <field>
>       <name>D2</name>
>       <type><long/></type>
>     </field>
> or
>     <field>
>       <name>D2</name>
>       <type><ref>A</ref></type>
>     </field> 
> into the D struct, which will both cause D to be processed before E
> despite the dependency. 
> Your style sheet does not match the predicate expression above.

I don't understand the terminology, but I think I see what you mean. 
For a node to qualify, it must have ONLY non-ref type children, or ALL
of its ref children references must have been processed.  Is that why
you were obliged to use the count() conditions?

Peter
-- 
Peter B. West  pbwest@xxxxxxxxxxxxxx  http://powerup.com.au/~pbwest
"Lord, to whom shall we go?"


 XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list


Current Thread