Re: Select a parrent node with s CSS selector?

----- Original Message ----- 
From: "Steven Pemberton" <steven.pemberton@cwi.nl>
To: "Andrew Fedoniouk" <news@terrainformatica.com>; "Ilia Goranov" 
<css-babailiica@babailiica.com>; <www-style@w3.org>
Sent: Tuesday, April 24, 2007 2:33 PM
Subject: Re: Select a parrent node with s CSS selector?


> On Mon, 23 Apr 2007 09:25:32 +0200, Andrew Fedoniouk 
> <news@terrainformatica.com> wrote:
>> >   ----- Original Message -----
>> >   From: Ilia Goranov
> ...
>> >   My proposal to the working group is to use the "less than" character
>> - > closing tag brace to set to which part of the selector the rule have 
>> to > apply. In the example above:
>> >
>> >   body>div.content p.description<a:link
>
>> So to find style of p.description CSS engine will need to scan
>> 1) all parents ( for body>div.content )
>> 2) *and* all it is children ( for a:link )
>>
>> Computational complexity of style resolving is O( n * m * d)  currently
>> where n - number of DOM elements,
>> m - number of styles.
>>
>> Your proposal changes the compelxity to O( n * n * m * d )  that is 
>> highly non-desirable as you may expect.
>
> Are you sure about this? CSS is currently designed so that you can decide 
> when you are at an element which styles apply, and presumably 
> implementations use that knowledge. Consequently if you added this rule to 
> such implementations it would indeed blow the complexity up. But it is not 
> inherent complexity; since the selector ">" and the proposed "<" are 
> symmetrical, I would expect at worst only a linear increase in complexity. 
> It would just need a different algorithm.

...since the selector ">" and the proposed "<" are  symmetrical,...

They are far from being symmetrical.

A > B - any element B that has immediate parent of A

So to check for B selector - O(1),
for A selector - O(1)
and "immediate parent" is always known so also O(1).
And integral complexity = O(n)

A < B - any element A that has B among its n children.

You need to check for A - O(1).
and all n children for B selector

n * O(1) + O(1) = O(n)

So time needed to test for the selector
is dependent from number of children of the element.

In fact main bottleneck of style resolving
is not selector tests per se.
But in any case selectors that are O(n) complex
where n is a number of children or characters and
not desirable.

Andrew Fedoniouk.
http://terrainformatica.com


>
> Steven Pemberton
>

Received on Wednesday, 25 April 2007 05:14:28 UTC