Re: Data_Error and Enumeration_IO

[Niklas Holsti <niklas.holsti@tidorum.invalid>]

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