[whatwg] DOMTokenList is unordered but yet requires sorting
erik.arvidsson at gmail.com
Mon Jun 15 16:08:04 PDT 2009
On Mon, Jun 15, 2009 at 16:02, Kristof Zelechovski <giecrilj at stegny.2a.pl>wrote:
> 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.
That is is not true. Just use a set/map to keep track of previously seen
elements. It is a trivial thing to do.
> 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...
More information about the whatwg