On Tue, Jul 28, 2009 at 5:52 AM, Jonas Sicking wrote:
>> By the way, preserving duplicates shouldn't be much code complexity if
>> I'm not mistaken.
>
> I take it you mean *removing* duplicates here, right?
Oops, yes.
>> The only required code change would be to use a hashset when parsing
>> the
On Mon, Jul 27, 2009 at 8:24 PM, Sylvain Pasche wrote:
> On Tue, Jul 28, 2009 at 2:17 AM, Ian Hickson wrote:
>> On Sun, 12 Jul 2009, Jonas Sicking wrote:
>>> >>
>>> >> Oh, I have forseen that. Is it really necessary to remove duplicates
>>> >> ? I imagine DOMTokenList to be similar to what can be a
> On Mon, 13 Jul 2009, Sylvain wrote:
>>
>> This is a bit unrelated, but when looking at the DOMTokenList
>> implementation, I had an idea about an alternative algorithm that could
>> be easier to implement and could also be described more simply in the
>> spec. The disadvantage is that the DOMToke
On Tue, Jul 28, 2009 at 2:17 AM, Ian Hickson wrote:
> On Sun, 12 Jul 2009, Jonas Sicking wrote:
>> >>
>> >> Oh, I have forseen that. Is it really necessary to remove duplicates
>> >> ? I imagine DOMTokenList to be similar to what can be achieved with a
>> >> String.split(), but then it would be jus
On Sun, 12 Jul 2009, Jonas Sicking wrote:
> >>
> >> Oh, I have forseen that. Is it really necessary to remove duplicates
> >> ? I imagine DOMTokenList to be similar to what can be achieved with a
> >> String.split(), but then it would be just more duplicate
> >> functionality.
> >
> > If we don'
On Mon, Jul 13, 2009 at 6:24 AM, news.gmane.org wrote:
> On 7/13/2009 7:26 AM, Jonas Sicking wrote:
>>
>> On Sun, Jul 12, 2009 at 9:00 PM, Ian Hickson wrote:
>>>
>>> If we don't remove duplicates, then things like the .toggle() method
>>> could
>>> have some quite weird effects.
>>
>> Such as? The
On 7/13/2009 7:26 AM, Jonas Sicking wrote:
On Sun, Jul 12, 2009 at 9:00 PM, Ian Hickson wrote:
If we don't remove duplicates, then things like the .toggle() method could
have some quite weird effects.
Such as? The only one I can think of is that calling .toggle() would
remove multiple items.
On Sun, Jul 12, 2009 at 9:00 PM, Ian Hickson wrote:
> On Mon, 15 Jun 2009, João Eiras wrote:
>> On Mon, 15 Jun 2009 21:38:05 +0200, Darin Adler wrote:
>> > On Jun 15, 2009, at 12:22 PM, Ian Hickson wrote:
>> > > On Tue, 9 Jun 2009, Erik Arvidsson wrote:
>> > > >
>> > > > I was about to follow up o
On Mon, 15 Jun 2009, João Eiras wrote:
> On Mon, 15 Jun 2009 21:38:05 +0200, Darin Adler wrote:
> > On Jun 15, 2009, at 12:22 PM, Ian Hickson wrote:
> > > On Tue, 9 Jun 2009, Erik Arvidsson wrote:
> > > >
> > > > I was about to follow up on this. Requiring sorting which is O(n
> > > > log n) for
On Jun 15, 2009, at 4:19 PM, Kristof Zelechovski wrote:
The complexity of using a set implemented as hash table is quadratic
in the
number of elements because of hash collisions.
Removing duplicates from a list of length N using an auxiliary set is
average-case O(N) because insertion and
The complexity of using a set implemented as hash table is quadratic in the
number of elements because of hash collisions.
Chris
On Mon, Jun 15, 2009 at 16:12, Aryeh Gregor
> wrote:
> On Mon, Jun 15, 2009 at 7:11 PM, Kristof
> Zelechovski wrote:
> > The complexity of using a set/map is logarithmic in the size of the set.
>
> Not if it's implemented as a hash table.
>
> Is DOMTokenList really expected to store lists large e
On Mon, Jun 15, 2009 at 7:11 PM, Kristof
Zelechovski wrote:
> The complexity of using a set/map is logarithmic in the size of the set.
Not if it's implemented as a hash table.
Is DOMTokenList really expected to store lists large enough that this
asymptotic behavior matters, though?
The complexity of using a set/map is logarithmic in the size of the set.
Multiply by the number of steps, you get what it takes.
Chris
On Mon, Jun 15, 2009 at 16:02, Kristof Zelechovski 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
> becaus
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 ign
On Mon, Jun 15, 2009 at 12:38, Darin Adler wrote:
>
>
> Since DOMTokenList requires uniqueness, then I suspect it's still O(n log
> n) even without sorting, not O(n).
That can be done in O(n).
--
erik
On Mon, 15 Jun 2009 21:38:05 +0200, Darin Adler wrote:
On Jun 15, 2009, at 12:22 PM, Ian Hickson wrote:
On Tue, 9 Jun 2009, Erik Arvidsson wrote:
I was about to follow up on this. Requiring sorting which is O(n
log n) for something that can be done in O(n) makes thing slower
without any
On Jun 15, 2009, at 12:22 PM, Ian Hickson wrote:
On Tue, 9 Jun 2009, Erik Arvidsson wrote:
I was about to follow up on this. Requiring sorting which is O(n
log n) for something that can be done in O(n) makes thing slower
without any real benefit. Like João said the order should be
defi
On Wed, 10 Jun 2009, João Eiras wrote:
> >
> > Ensuring consistency between browsers, to reduce the likelihood that
> > any particular browser's ordering becomes important and then forcing
> > that browser's ordering (which could be some arbitrary ordering
> > dependent on some particular hash
I was about to follow up on this. Requiring
sorting which is O(n log n) for something that can be done in O(n)
makes thing slower
without any real benefit.
Like João said the order should be defined as the order of the class content
attribute.
On Tue, Jun 9, 2009 at 16:00, João Eiras wrote:
>
>
Ensuring consistency between browsers, to reduce the likelihood that any
particular browser's ordering becomes important and then forcing that
browser's ordering (which could be some arbitrary ordering dependent on
some particular hash function, say) into the platform de facto.
This is similar
On Wed, 13 May 2009, Erik Arvidsson wrote:
>
> Section 2.9.3 DOMTokenList says:
>
> The DOMTokenList interface represents an interface to an underlying
> string that consists of an *unordered* set of unique space-separated
> tokens.
>
>
> Yet, the item method says:
>
> The item(index) method
DOMTokenList, as an object, is semantically unordered, therefore an
arbitrary ordering can be used for enumeration. The item method of
DOMTokenList provides an enumerator and imposes such an ordering.
Since no other enumerator is available to counter the claim, it may be
tempting to say, as a simp
On Mon, May 18, 2009 at 00:18, Simon Pieters wrote:
> Immagine if it is specified that the order is not relevant and
> implementations can use any order (so long as it's stable). So one UA uses
> one order and another uses another. Then one of those UAs becomes very
> popular. Web pages start to d
On Thu, 14 May 2009 22:58:20 +0200, Erik Arvidsson
wrote:
On Thu, May 14, 2009 at 00:30, Kristof Zelechovski
wrote:
If a token list represented an ordered set, it could not be sorted to
get an
item because the host would have to preserve the original (document)
order
of tokens.
The que
On Thu, May 14, 2009 at 00:30, Kristof Zelechovski
wrote:
> If a token list represented an ordered set, it could not be sorted to get an
> item because the host would have to preserve the original (document) order
> of tokens.
The question is why does the set need to be ordered at all as long as
If a token list represented an ordered set, it could not be sorted to get an
item because the host would have to preserve the original (document) order
of tokens.
Chris
Section 2.9.3 DOMTokenList says:
The DOMTokenList interface represents an interface to an underlying string
that consists of an *unordered* set of unique space-separated tokens.
Yet, the item method says:
The item(index) method must split the underlying string on spaces, *sort the
resulting lis
29 matches
Mail list logo
