From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=0.4 required=5.0 tests=BAYES_00,FORGED_MUA_MOZILLA
	autolearn=no autolearn_force=no version=3.4.4
X-Google-Thread: 103376,5c3042563529d4f3
X-Google-NewGroupId: yes
X-Google-Attributes: gida07f3367d7,domainid0,public,usenet
X-Google-Language: ENGLISH,ASCII-7-bit
Received: by 10.68.197.100 with SMTP id it4mr3275415pbc.5.1326543932238;
        Sat, 14 Jan 2012 04:25:32 -0800 (PST)
Path: 
 lh20ni181086pbb.0!nntp.google.com!news1.google.com!news4.google.com!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail
From: Niklas Holsti <niklas.holsti@tidorum.invalid>
Newsgroups: comp.lang.ada
Subject: Re: Data_Error and Enumeration_IO
Date: Sat, 14 Jan 2012 14:25:30 +0200
Organization: Tidorum Ltd
Message-ID: <9ndahrFeruU1@mid.individual.net>
References: 
 <3f3d626a-1b8c-49af-aa85-9e586029a817@z12g2000yqm.googlegroups.com>
 <jensq1$45b$1@munin.nbi.dk>
 <c098273e-b8ff-4eca-9096-717f4e416960@r5g2000yqc.googlegroups.com>
 <jeq9ib$1ouu$1@adenine.netfront.net> <jeqh4g$peo$1@munin.nbi.dk>
Mime-Version: 1.0
X-Trace: individual.net 0aQEM8SCcpoGibY+LBHXwA7shGOwFD/varwo/bG1UAkkBoGR0p
Cancel-Lock: sha1:8wrGwdXD0nLfYbqe3ck+DxwkAtc=
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.6;
 rv:9.0) Gecko/20111222 Thunderbird/9.0.1
In-Reply-To: <jeqh4g$peo$1@munin.nbi.dk>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Date: 2012-01-14T14:25:30+02:00
List-Id: <comp.lang.ada>

On 12-01-14 02:09 , Randy Brukardt wrote:
>> On 01/13/2012 02:30 PM, John McCormick wrote:
>>>
...
>>>  Yet when you
>>> enter "abc" in my original example for enumeration IO, it cannot
>>> recognize that no valid enumeration literal starts with an a.  It has
>>> to process the entire identifier before it can see that. So the crux
>>> of my question is why doesn't the consumption of characters for
>>> enumeration input behave like that of real input. It doesn't really
>>> matter other than to satisfy my curiosity.

> Right. The important point here is that the consumption of characters is not
> related in any way to the actual subtype being read; it only depends on the
> syntax of the appropriate literals.
...
> As to why it is done this way, it's hard to imagine how else it could be
> done. To reject the "abc" example at the 'a', for instance, we would have to
> do a brute force search in a table of potentially hundreds of enumeration
> literals to see if any start with 'a', then repeat that to see if any start
> with "ab", and so on. If the literals are long and the number of literals is
> high, this is going to be a N**2 algorithm -- and I don't think I want my
> input to do that (there is a built-in denial of service possibility).

While I am satisfied with the way that Ada does enumeration input now, 
the literals in an enumerated type could be arranged in a data structure 
(a trie) that would allow a (nearly) constant-time, 
character-by-character check that the input read so far can be a prefix 
of a literal of the given type or subtype. The complexity order of input 
would still be (nearly) linear in the number of characters.

In fact, while the input scanning phase would no doubt be a bit slower, 
the final conversion from the text string into an enumeration value 
would need no additional time, so the whole input function might become 
faster, and the 'Value function might also become faster.

-- 
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
       .      @       .