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 07:54:40 PST
Path: 
 archiver1.google.com!news1.google.com!newsfeed.stanford.edu!canoe.uoregon.edu!logbridge.uoregon.edu!hammer.uoregon.edu!skates!not-for-mail
From: Stephen Leake <stephen.a.leake.1@gsfc.nasa.gov>
Newsgroups: comp.lang.ada
Subject: Re: Grace and Maps (was Re: Development process in the Ada community)
Date: 23 Apr 2002 10:46:38 -0400
Organization: NASA Goddard Space Flight Center (skates.gsfc.nasa.gov)
Message-ID: <u8z7epj5d.fsf@gsfc.nasa.gov>
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>
NNTP-Posting-Host: anarres.gsfc.nasa.gov
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
X-Trace: skates.gsfc.nasa.gov 1019573569 6162 128.183.220.71 (23 Apr 2002
 14:52:49 GMT)
X-Complaints-To: usenet@news.gsfc.nasa.gov
NNTP-Posting-Date: 23 Apr 2002 14:52:49 GMT
User-Agent: Gnus/5.09 (Gnus v5.9.0) Emacs/21.2
Xref: archiver1.google.com comp.lang.ada:22989
Date: 2002-04-23T14:52:49+00:00
List-Id: <comp.lang.ada>

Ted Dennison <dennison@telepath.com> writes:

> 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).
> 
> Maps should provide an interface consistent with Lists, as far as is
> practicable.
> 
> Comments?

These work for me.

We could add something about no memory leaks, but maybe that's implied.

One of the requirements for Grace.Lists was that it be useable with
one instantiation. That had a significant impact on the final design.
Do we want to keep that in general for Grace? I think not, if we have
any intention of it being used in serious work. Both the Booch
Components and SAL generally need several instantiations to get useful
stuff, because they provide more flexibility.

-- 
-- Stephe