Re: List container: Insert and Delete

["Nick Roberts" <nickroberts@adaos.worldonline.co.uk>]

"Jeffrey Carter" <jeffrey.carter@boeing.com> wrote in message
news:3BEFF9D6.607480D@boeing.com...
> Nick Roberts wrote:
> >
> > Your delicate distinction between an 'iterator' and a 'position' is a
little
> > silly. The reasons why it should not be done with iterators are the same
as
> > the reasons why it should not be done with positions.
>
> No, the idea that they are the same is a little silly. An iterator, by
> definition, is something that iterates. A position within a list does
> not iterate. If you can provide an example of a position iterating I
> will change my position.

I knew I'd get a rocketing for that one! You are, of course, quite right.

> > The indexed operations will, of course, be of O(1) for the bounded list,
yet
> > being both based on the abstract list type, they will be algorithmically
> > interchangeable. So there is a deeper reason for my insistence on
indexed
> > operations: I am trying to make a bigger plan 'come together'.
>
> They will be O(N) in both versions, unless you make the extremely poor
> implementation decision for the bounded version to implement insertions
> and deletions by moving entire slices of the underlying array. I suspect
> such an implementation will be universally considered unacceptable.
> Making insertions and deletions O(N) so that indexing can be O(1) is a
> poor choice, especially considering that both can be O(1).

I will investigate the possibilities for the implementation of the bounded
version. As Ted Dennison intimates somewhere (in answer to this post?), I
think an indexed implementation is an interesting idea, but it's performance
under various conditions is likely to be a complex matter.

> > Finally, my proposal includes all the usual head and tail dicing
operations.
> > Chopping off, or adding on, one item to either end of a list will be the
> > most frequently used operations anyway, for which arguments about
indexing
> > don't apply. The indexed operations are mainly there for convenience. As
I
> > showed in an example in another thread, really serious manipulations of
> > lists are best done sequentially.
>
> There are no "usual" head and tail operations for a list. In decades of
> using and implementing data structure libraries, TED's specification is
> the first I've encountered that emphasizes dequeue- and string-like
> operations.

There are in functional languages such as LISP. I think they'll be handy for
lists sometimes, and are not difficult to implement.

> The whole point of a list is that insertions and deletions are needed at
> arbitrary positions. If you're only operating at the ends of the
> sequence, then you want a dequeue, not a list, and you should not be
> using a list.

Okay, I agree, and I'm writing a new proposal that has a complete set of
'cursor' operations that do just what (I assume) your position-based
strategy intended. Hope to get this to Ted (for his web site) soon (maybe
2-3 days).

> > I hope you will look at my proposal, and perhaps be a little more
convinced!
>
> I'll take a look.

My thanks, Jeff, for your patience!

--
Best wishes,
Nick Roberts