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,a644fa9cd1a3869a
X-Google-Attributes: gid103376,public
X-Google-ArrivalTime: 2001-11-13 08:53:18 PST
Newsgroups: comp.lang.ada
Path: 
 archiver1.google.com!news1.google.com!newsfeed.stanford.edu!news.ems.psu.edu!news.cis.ohio-state.edu!news.maxwell.syr.edu!nntp.abs.net!uunet!dca.uu.net!ash.uu.net!xyzzy!nntp
From: Jeffrey Carter <jeffrey.carter@boeing.com>
Subject: Re: List container: Insert and Delete
X-Nntp-Posting-Host: e246420.msc.az.boeing.com
Content-Type: text/plain; charset=us-ascii
Message-ID: <3BF14752.B3F3FBC@boeing.com>
Sender: nntp@news.boeing.com (Boeing NNTP News Access)
Content-Transfer-Encoding: 7bit
Organization: The Boeing Company
X-Accept-Language: en
References: <mailman.1005507140.5856.comp.lang.ada@ada.eu.org>
 <9sn4qm$13g29j$2@ID-25716.news.dfncis.de>
 <Z0JH7.21323$xS6.32782@www.newsranger.com>
 <9sok8i$142am0$2@ID-25716.news.dfncis.de> <3BF004F4.F74AE461@boeing.com>
 <9sp5up$g5o$1@nh.pace.co.uk> <3BF0827A.DCF2213C@acm.org>
 <9sra40$b8p$1@nh.pace.co.uk> <5DaI7.23016$xS6.35866@www.newsranger.com>
Mime-Version: 1.0
Date: Tue, 13 Nov 2001 16:16:18 GMT
X-Mailer: Mozilla 4.73 [en]C-CCK-MCD Boeing Kit  (WinNT; U)
Xref: archiver1.google.com comp.lang.ada:16423
Date: 2001-11-13T16:16:18+00:00
List-Id: <comp.lang.ada>

Ted Dennison wrote:
> 
> In article <9sra40$b8p$1@nh.pace.co.uk>, Marin David Condic says...
> >
> But I see no need that a Bounded package and an Unbounded package
> >have to be plug compatible. You very seldom would want to unplug the one and
> 
> I'd agree with this. The only compelling reason I could see for it would be if
> we were using some kind of root tagged type to implement both (which we aren't),
> and wanted to allow for dynamic dispatching on classwide list pointers.
> 
> I'm curious what people think about the extent of the compatability they should
> have though. Should the look mostly alike, except for routines that don't make
> sense in that context? Should we remove all basic-looking routines from either
> implementation with time behavior >=O(N). Should the interface for bounded be
> completely redesigned around things that you can do with bounded implementations
> that you can't easily do with unbounded ones?

I've never actually encountered a situation that needed a bounded list,
so I really can't comment (not that I'll let that stop me). I have
encountered situations that needed a bounded queue, however. I have
sometimes used an unbounded queue for a quick test of functionality, and
then converted to an unbounded queue, since the packages I use have
identical interfaces except for the Is_Full function and the
Full/Storage_Exhausted exceptions.

However, all data structures are abstractions with specific interfaces,
and a specific implementation still needs to provide that interface. For
a list, there are basic operations to obtain positions within the list
and to insert, delete, and update at a specific position; these are
independent of the implementation.

For a list, the only basic operation that is O(N) in time is usually
Length; it is of course possible to make Length O(1) by keeping a count,
but that doesn't seem to be necessary. I would want every operation to
have its time complexity and pre- and post-conditions (where applicable)
clearly documented.

-- 
Jeffrey Carter