Re: Common sense...

["chris.danx" <spamoff.danx@ntlworld.com>]

"Jeffrey Carter" <jrcarter@acm.org> wrote in message
news:3D26473B.581C61BC@acm.org...
> "chris.danx" wrote:
> >
> > "Jeffrey Carter" <jrcarter@acm.org> wrote in message
> > news:3D25E607.E59E11E2@acm.org...
> > > Deleting nodes from an iterator is erroneous and should raise an
> > > exception.
> >
> > ok but how would you enforce that.  Just not support it?  That's no
bother
> > as the iterators aren't written yet.
>
> The PragmAda Reusable Components' list components' iterators will raise
> an exception (Invalid_Position) if the client-supplied action deletes
> the current node. This is a consequence of assigning a unique ID to each
> list, marking each Position and node with the ID of the associated list,
> and invalidating the ID when a node is deleted.

That is similar to the method the list package uses.  Each list is assigned
an ID, each position within the list has that ID, and an exception is
generated if the ID assigned to the position and the ID of the list don't
match.  This ensures consistancy on removal of nodes.

Additionally, each node in the list holds a count of the number of iterators
and the number of objects which point to it (called positions as they
represent a position in a list).  When both counts go to zero can a node be
deallocated.  If a call to remove/delete is placed on a node, and the count
of either is not zero, the node is marked and skipped by the appropriate
subprograms (next, previous, has_next, has_previous, head, last).

I have my doubts as to whether this will be useful, some ops will be O(1) in
best case and O(n) in worst, when they would usually be O(1) in best,
average, and worst cases.   Perhaps it would be better to raise an exception
if a node held by an iterator is deallocated.  Alternatively, the node could
be marked but not deallocated until the counts both go to zero; with the
effect that any position which holds

So many choices, arghhhhhh!