[whatwg] DOMTokenList is unordered but yet requires sorting

Erik Arvidsson 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.
> 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/20090615/644b4d2f/attachment-0002.htm>

More information about the whatwg mailing list