Re: In a pickle.

[Stephen Leake <stephen.a.leake.1@gsfc.nasa.gov>]

"chris.danx" <spamoff.danx@ntlworld.com> writes:

> The task of implementing iterators is proving very difficult, can
> anyone please offer some guidance/pointers?  

I've just put up my Grace.Lists implementation; see 

http://users.erols.com/leakstan/Stephe/index.html

It does "safe" iterators; iterators are invalidated if the item they
point to is deleted, etc.

> I want operations on a node which would invalidate iterators to take
> place only when one iterator references a node. For example deleting
> a node should only occur when one, and only one iterator points to
> it (if more than one iterator points to the node an exception should
> occur).

Grace does not require this. I guess you're doing something like
"reference counting garbage collection". 

So Grace iterators are not exactly what you want. But there may be
some implementation ideas you can use.

> First I tried a scheme involving counting the number of iterators
> that reference a node, but this approach lead to a very complex
> implementation, so it's back to the drawing board. :(

Complexity is sometimes necessary :).

> One difficulty encountered is in signalling that we are done with a
> node. Suppose the statement
> 
> Iterator := Next (Iterator);
> 
> is allowed.  Prior to the call Iterator points to a node in the list
> (if it did not Next would raise Invalid_Iterator_Error), which it will
> leave after the assignment.  The node needs to know an iterator has
> left, but how?  Finalize can decrement the counter but it's difficult
> to control exactly when.  Consider this...
> 
> function Next (Iterator : in Iterator_Type) return Iterator_Type is
>     Temp : Iterator_Type;
> begin
>     ...
>     return Temp;
> end Next;
> 
> After return Temp; Temp will be finalized so we need to record that
> temp is just temporary.  Then we have the problem of intelligently
> adjusting the iterator on the left hand-side. :(

Yes, using temporaries causes complexity. You might try using
aggregates instead; that gives you more direct control over what's
going on. Neither Initialize nor Finalize is called on an aggregate.

> Now I know why John English skipped the issue in "ada: the craft..."
> (I didn't fully appreciate Johns' warning on this) and why other
> list implementations either skip the issue or are quite complex.

Welcome to the club :). Implementing the Grace iterators was much more
challenging than I thought it would be. And I haven't really tested it
yet; that's more work than I want to do right now.

> Is there a better solution to this problem???

Since I'm not sure what your real top level problem is, I can't say.
Can you say more about why you want reference counted iterators?

-- 
-- Stephe