<div class="gmail_quote">On Mon, Jun 15, 2009 at 16:02, Kristof Zelechovski <span dir="ltr"><<a href="mailto:giecrilj@stegny.2a.pl">giecrilj@stegny.2a.pl</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">










<div lang="PL" link="blue" vlink="blue">

<div>

<p><font size="2" color="navy" face="Arial"><span lang="EN-US" style="font-size:10.0pt;font-family:Arial;color:navy">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.</span></font></p></div></div></blockquote><div>That is is not true. Just use a set/map to keep track of previously seen elements. It is a trivial thing to do.</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">

<div lang="PL" link="blue" vlink="blue"><div><p><font size="2" color="navy" face="Arial"><span lang="EN-US" style="font-size:10.0pt;font-family:Arial;color:navy"></span></font></p>

<p><font size="2" color="navy" face="Arial"><span lang="EN-US" style="font-size:10.0pt;font-family:Arial;color:navy">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.</span></font></p>

<p><font size="2" color="navy" face="Arial"><span lang="EN-US" style="font-size:10.0pt;font-family:Arial;color:navy">HTH,</span></font></p>

<p><font size="2" color="navy" face="Arial"><span lang="EN-US" style="font-size:10.0pt;font-family:Arial;color:navy">Chris</span></font></p>

<p><font size="2" color="navy" face="Arial"><span lang="EN-US" style="font-size:10.0pt;font-family:Arial;color:navy"> </span></font></p>

<p><font size="2" color="navy" face="Arial"><span lang="EN-US" style="font-size:10.0pt;font-family:Arial;color:navy">* 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.</span></font></p>

<p><font size="3" face="Times New Roman"><span lang="EN-US" style="font-size:12.0pt"> </span></font></p>

</div>

</div>


</blockquote></div><br><br clear="all"><br>-- <br>erik<br>