Re: List container: Insert and Delete

[Darren New <dnew@san.rr.com>]

Ted Dennison wrote:
> Should we remove all basic-looking routines from either
> implementation with time behavior >=O(N).

Definitely not. All that will do is force people to recreate the
functionality they need anyway, except without the benefit of being able
to access the internal structures.

For example, I strongly suggest that there be a mechanism to translate
between positions and integer offsets and back. This is an O(N)
operation, obviously, compared to the O(1) of moving the position.
However, if someone has a list that they want to stuff out to a file,
along with an offset (say, the one currently on the screen), they need a
way to handle that. Denying the ability to translate between positions
and integers just means that someone's going to write code full of
things like
  offset := offset + 1;
  pos := Next(pos);

Indeed, Tcl for many many years had O(N) access to arrays (called
"lists" there, the maps being called arrays), and it wasn't really a
problem. If you had a 1000 element list, it was still quick enough. If
you had a really large list, you did it some other way if the
performance was too bad. So don't leave out functionality just because
it's hard to do *efficiently*. O(2**N) is still darn fast if N is 10 or
the multiplier is in microseconds.

Basically, the library has to be useful for small programs too, or
you've (a) missed the point and (b) done little to help promote Ada. The
languages that are great for million-line beasts and excrutiating for
100-line programs never really get very popular outside their niches.

-- 
Darren New 
San Diego, CA, USA (PST). Cryptokeys on demand.
   You will soon read a generic fortune cookie.