Re: Grace and Maps (was Re: Development process in the Ada community)

["Warren W. Gay VE3WWG" <ve3wwg@home.com>]

Ted Dennison wrote:

> Ted Dennison wrote:
>> Marin David Condic wrote:
>>> I don't think you need to have the full-blown project setup done in 
>>> order to
>>> discuss an interface to Maps. What would you suggest as a means of 
>>> getting
>>> that ball rolling? Would you like someone to take the Lists spec and 
>>> turn it
>>> into a strawman for Maps? (I hear you're a little preoccupied at the
>>> moment... :-)
>>
>> Yeah, that would be a good start. Right now in addtion to this I'm 
> 
> On second thought, we really ought to get some kind of consensus on 
> requirements before rushing headlong into design. If nothing else, it 
> will save a lot of arguments.
> 
> Requirements I think ought to be included (using the usual should/shall 
> language):
> 
> Maps shall provide for key lookup in no worse than O(logn) average time 
> and O(n) worst case (where n is the # of elements in the map).
> 
> Maps shall provide for creation of a sorted list or array, or traversal 
> in sorted order, in no worse than O(n) time. (In other words, the map is 
> kept sorted as elements are added).


I'm not sure about this sort requirement. Many applications only need to
fetch a value based upon a key. Requiring that the map be sorted will
probably impose suboptimal performance if your requirement doesn't require
sorting.

The sort requirment could be made as part of iteration, and optionally
at that. Just my $0.02 Cdn, which isn't worth much these days ;-)

-- 
Warren W. Gay VE3WWG
http://home.cogeco.ca/~ve3wwg