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=-1.9 required=5.0 tests=BAYES_00 autolearn=ham
	autolearn_force=no version=3.4.4
X-Google-Language: ENGLISH,ASCII-7-bit
X-Google-Thread: 103376,ac39a12d5faf5b14
X-Google-Attributes: gid103376,public
X-Google-ArrivalTime: 2002-04-23 10:55:00 PST
Message-ID: <3CC59ED2.1000803@home.com>
From: "Warren W. Gay VE3WWG" <ve3wwg@home.com>
User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.0; en-US;
 rv:0.9.4) Gecko/20011128 Netscape6/6.2.1
X-Accept-Language: en-us
MIME-Version: 1.0
Newsgroups: comp.lang.ada
Subject: Re: Grace and Maps (was Re: Development process in the Ada community)
References: <3CB46975.90408@snafu.de> <3CBAFFEE.2080708@snafu.de>
 <4519e058.0204171036.6f0a7394@posting.google.com> <3CBDD795.4060706@snafu.de>
 <4519e058.0204180800.44fac012@posting.google.com> <3CBF0341.8020406@mail.com>
 <a9n0tk$6fs$1@nh.pace.co.uk>
 <4519e058.0204190529.559a47ae@posting.google.com>
 <a9p98h$8hn$1@nh.pace.co.uk> <3CC1C6B3.6060306@telepath.com>
 <3CC21747.5000501@telepath.com>
Content-Type: text/plain; charset=us-ascii; format=flowed
Content-Transfer-Encoding: 7bit
Date: Tue, 23 Apr 2002 17:50:11 GMT
NNTP-Posting-Host: 198.96.47.195
NNTP-Posting-Date: Tue, 23 Apr 2002 11:50:11 MDT
Organization: MetroNet Communications Group Inc.
Path: 
 archiver1.google.com!news1.google.com!newsfeed.stanford.edu!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!netnews.com!xfer02.netnews.com!newsin.iconnet.net!feed.tor.primus.ca!feed.nntp.primus.ca!newsfeed.torontointernetxchange.net!news.eol.ca!news1.tor.metronet.ca!nnrp1.tor.metronet.ca!not-for-mail
Xref: archiver1.google.com comp.lang.ada:22998
Date: 2002-04-23T17:50:11+00:00
List-Id: <comp.lang.ada>

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