Re: MI ammunition : linked lists

[Marius Amado Alves <amado.alves@netcabo.pt>]

On Mon, 2003-11-10 at 14:51, Lutz Donnerhacke wrote:
> * amado.alves wrote:
> > A very common programming task where multiple inheritance (MI) would be
> > handy: implementation of doubly linked lists.
> 
> Single instantiated doubly linked lists.
> 
> Usually I need nodes which are member in multiple lists or trees. That's why
> I prefer a mixin design which allows me to specify the required list the
> node is member of directly.
> 
> Please clarify how you approach deal with multiple membership.

I think you mean you need your "data" (payload, cargo, element...) to
participate in different structures. Not strictly the "node".

I was discussing only the structural relations of nodes (next, prev).

There are a number of ways to attach data to a node. If the data must be
shared between different structures a straightforward way is to have the
node type have a component that points to the (logical) data.
 _______      _______
|       |    |       |     _______
| Next ----->| Next------>|       | 
|       |<-----Prev  |<-----Prev  | (List 1)
| Datum |    |       |    |       |
|___|___|    | Datum |    | Datum |
    |        |___|___|    |___|___|
    |            |            |
  _\|/_        _\|/_        _\|/_
 |     |      |     |      |     |  (Data)
 |_____|      |_____|      |_____|
   /|\          /|\          /|\
 ___|___      ___|___         |
|   |   |    |   |   |     ___|___
| Datum |    | Datum |    |   |   |
|       |    |       |    | Datum | (List 2)
| Next ----->| Next------>|       | 
|_______|<-----Prev  |<-----Prev  |
             |_______|    |_______|

Note I have already conceded that polymorphism for lists in Ada is
troublesome because your need to change the type of certain nodes upon
certain update operations to the list (and in Ada you cannot change the
type of an object). I do not think polymorphism poses a problem with
respect to sharing data.