Re: Getting the index for an element in mutually referencing containers

["Randy Brukardt" <randy@rrsoftware.com>]

"Simon Wright" <simon@pushface.org> wrote in message 
news:ly37ekcikw.fsf@pushface.org...
> "Randy Brukardt" <randy@rrsoftware.com> writes:
>
>> "Mart van de Wege" <mvdwege@gmail.com> wrote in message
>> news:86wpbxneuz.fsf@gaheris.avalon.lan...
>>> Simon Wright <simon@pushface.org> writes:
>> ...
>>>> But, I really think you're going to need to use access types here. A
>>>> Person is a unique object, and should only exist once in your data
>>>> structures. A Child should hold references to its Parent(s) and vice
>>>> versa; if a Child holds *copies* of its Parents, what happens when
>>>> you change the Parent's data in one place? how are you going to find
>>>> all the copies and change all of them?
>>>>
>>> That was what I was afraid of. I like the way Ada usually takes care
>>> of this for you, but I've been trying to work it out during downtime
>>> today at work, and I'm afraid it's indeed time to grab the access
>>> types out of the toolbox.
>>
>> The trick in such cases is to have a global "person" vector, which
>> contains all of the actual Person objects. Then use the cursors into
>> that array in your other data structures. That's gives the needed
>> level of indirection without involving any actual access types
>> (meaning that you let Ada do the storage management, and depending on
>> your container implementation, also reduce/eliminate the danger of
>> dangling access types).
>
> In the general case, you'd need to cope with deleting (the equivalent
> of) Person objects.

True, but that's the dangling cursor problem, and you're certainly no worse 
off with a dangling cursor than a dangling access type. (And the container 
implementation might have detection for dangling cursors, that's not likely 
with access types.)

> And wouldn't even appending a new Person risk invalidating any existing
> cursors? AARM A18(5.k) says "Cursors *generally* remain valid as long as
> the container exists and the element referenced is not deleted",
> emphasis added. AdaCore's Vector implementation would be OK with
> inserting elements _after_ the Cursor concerned, since the Cursor is
> based on an index into an array. See discussion at AARM A18.2(240) ff.

With the exception of the Vector container, cursors always stay valid 
through operations on the container. They continue to point at the same 
element no matter what insertions/deletions occur, until of course the 
container itself is destroyed. (Generally, one can't reliably detect cursors 
that point into a destroyed container [since all of the data structures have 
been recycled], but that is a lot less likely problem than a cursor that 
points at a deleted element of a still-existing container.)

The Vector container allows "sliding" of elements, which may (or may not) 
cause a cursor to become invalid. But that can only happen with an 
insertion/deletion *in front* of the cursor -- never with Append. There's a 
bunch of special rules in the RM for that case.

If keeping the cursor stable is a priority, I'd use a list or map container 
rather than a vector. For "Person", a map seems likely (you'd want to be 
able to look them up by name, I'd think).

> I quite like the idea of using an indefinite container to hold the
> Person objects, but I think I'd use a Map with the key an integer
> (Natural?), with the next key held in a private global, incremented as
> each new Person is created. The reference to a Person would be the
> associated key.

That would work but would probably be extra work for no real reason. The 
only real advantage that I can see is that you'd get real dangling reference 
detection with that (without depending upon the container implementation). 
YMMV, of course.

> One disadvantage to this design is that Containers hold non-limited
> types. Your users run the risk of writing code that gets hold of a copy
> of the object and modifies that, rather than modifying the actual
> object.

Right. Not much that can be done about that, unfortunately. Limited types 
seem to defy reusable containerization. I've tried to design such a 
container, but there's always some reason that it won't work without 
introducing access types.

The one thing I've done with Claw programs is to declare the type 
non-limited controlled and override Adjust to raise Program_Error. [Claw 
uses non-limited types, so if you have a window extension that you don't 
want copied, you have to take some action.] But that won't work with the 
containers, as the initial copy would raise Program_Error. If you can live 
with only having default initialization, then you could modify the elements 
in place in such a scenario. But that limits one to definite types.

                               Randy.