Re: MI ammunition : linked lists

[Dmitry A. Kazakov <mailbox@dmitry-kazakov.de>]

On Thu, 6 Nov 2003 16:32:16 -0000, "amado.alves"
<amado.alves@netcabo.pt> wrote:

>A very common programming task where multiple inheritance (MI) would be handy: implementation of doubly linked lists.
>
>It is clear that the middle nodes combine the attributes of the first and last nodes. This is where linguistic MI could help:
>
>  type Node is tagged ...;
>
>  type Node_Ptr is access Node'Class;
>
>  type First_Node is new Node with record
>    Next : Node_Ptr;
>  end record;
>
>  type Last_Node is new Node with record
>    Prev : Node_Ptr;
>  end record;
>
>  type Middle_Node is new First_Node with Last_Node;

Well if you want it, it should be sort of:

   type Node is abstract tagged ...;
      -- There is no dangling nodes
   type Node_Ptr is access Node'Class;

   type First_Node is new Node with private;
   type First_Node_Ptr is access First_Node'Class;
      -- Cannot define First_Node without pointers to Last_Node

   type Last_Node is new Node with private;
   type Last_Node_Ptr is access Last_Node'Class;

   type Middle_Node is new First_Node, Last_Node with private;

private
   type First_Node is new Node with record
       Next : Last_Node_Ptr;
          -- Only a Last_Node'Class can follow me
   end record;

   type Last_Node is new Node with record
       Prev : First_Node_Ptr;
          -- Only a First_Node'Class can precede me
   end record;

   type Middle_Node is new First_Node, Last_Node with null record;

>Of course the alternative is no big deal, syntactically:
>
>  type Middle_Node is new Node with record
>    Prev : Node_Ptr;
>    Next : Node_Ptr;
>  end record;

Which is semantically wrong.

1. IF you want to map node precedence to types, then you have to
consequently follow this. See above.

2. The alternative is that all nodes are same and thus there is no
reason to distinguish them as First / Middle / Last. And as a
consequence, they have to be moved into the private part, for they
become an implementation detail then.

>But, semantically, MI would allow conversions between Middle_Node and any the other two extended types. Whether this would be useful for linked lists remains to be ascertained. I confess I have not implemented them this way yet.

I did and I missed MI much, because as I said, the alternative design
of Middle_Node is unclean. As a result, time to time the clients HAVE
to use casts from Node_Ptr to more specific types. This is BAD.

BTW. You will ahve to add "all" to the node access types, if you have
many of them. Pool specific access types are tagged-unfriendly in Ada.

---
Regards,
Dmitry Kazakov
www.dmitry-kazakov.de