[whatwg] DOMTokenList is unordered but yet requires sorting

[Kristof Zelechovski]

Uniqueness of tokens can be determined in O(n) only* if the tokens are
ordered in the source (any order would do) but there is no such requirement,
and it cannot be required for compatibility with the content in the wild and
because the standard supports inserting new tokens.

It is possible to ignore this issue and proceed as if the tokens were
ordered.  The result would be that remove would fail, or it would run in
quadratic time.

HTH,

Chris

 

* If all possible tokens are predefined and their number is finite and the
source is valid, uniqueness can be determined in constant time.  This
scenario, however, is better served by a bit field than by a token list.

 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.whatwg.org/pipermail/whatwg-whatwg.org/attachments/20090616/2435f7a7/attachment.htm>