[whatwg] DOMTokenList is unordered but yet requires sorting

[Erik Arvidsson]

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.
>
>
>



-- 
erik
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.whatwg.org/pipermail/whatwg-whatwg.org/attachments/20090615/644b4d2f/attachment-0002.htm>