[whatwg] Question on Limits in Adaption Agency Algorithm
minamide at cs.tsukuba.ac.jp
Mon Dec 17 17:55:23 PST 2012
>> "xyz" is inserted as a child of <i> and the order between "abc" and
>> "xyz" is reversed in the tree. We would like to know whether this is an
>> intended behaviour of the specification.
> Yeah that's definitely not intentional.
> Does anyone have any preference for how this is fixed?
The easiest fix will be just to remove the limit of the inner loop.
Unfortunately, this makes the complexity of current implementations of the
adoption agency algorithm in O(n^2). This is because "remove node from
the stack of open elements" is in O(n) on implementations as far as I
9.5 If node is not in the list of active formatting elements, then remove
node from the stack of open elements and then go back to the step labeled
* WebKit : stack of open elements is implemented as a singly-linked list.
* Firefox : stack of open elements is implemented as an array.
(need to move elements in the array to remove)
I'm not sure whether this is ok or not.
(I thought the operation remove node was implemented in O(1).
For example, by using doubly linked list.)
More information about the whatwg