[whatwg] DOMTokenList is unordered but yet requires sorting

Kristof Zelechovski giecrilj at stegny.2a.pl
Mon Jun 15 16:02:27 PDT 2009

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.




* 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-0002.htm>

More information about the whatwg mailing list