MI ammunition : linked lists

["amado.alves" <amado.alves@netcabo.pt>]

A very common programming task where multiple inheritance (MI) would be handy: implementation of doubly linked lists.

A linked list is a chain of nodes. The first node links to the second, the last node links to the penultimate, and each of the others nodes links to both the previous and the next. (Each node usually also carries a payload, which we can ignore here.)

  First <-----> Second <-----> ... <-----> Penultimate <-----> Last

Often (always?) a non OOP design is used with only one type for all kinds of nodes, with null values in the unused slots:
   ___________      ______               ______      ___________
  |           |    |      |             |      |    |           |
  | Prev=null |<-----Prev |<--- ... <-----Prev |<-----Prev      |
  | Next---------->| Next-----> ... --->| Next----->| Next=null |
  |___________|    |______|             |______|    |___________|

An OOP design does away with the ugly nulls (however it introduces one-of-a-kind objects, which also some people consider ugly):
               ______               ______      ______
   ______     |      |             |      |    |      |
  |      |<-----Prev |<--- ... <-----Prev |<-----Prev |
  | Next----->| Next-----> ... --->| Next----->|______|
  |______|    |______|             |______|    

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;

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;

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.

Well, just a thought for those with too much free time on their hands ;-)