Re: MI ammunition : linked lists

[Lutz Donnerhacke <lutz@iks-jena.de>]

* Marius Amado Alves wrote:
> On Mon, 2003-11-10 at 14:51, Lutz Donnerhacke wrote:
>> 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".

Yep.

> 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.

I do not like access types. They provide additional error sources.

>  _______      _______
>|       |    |       |     _______
>| Next ----->| Next------>|       | 
>|       |<-----Prev  |<-----Prev  | (List 1)
>| Datum |    |       |    |       |
>|___|___|    | Datum |    | Datum |
>     |        |___|___|    |___|___|
>     |            |            |
>   _\|/_        _\|/_        _\|/_
> |     |      |     |      |     |  (Data)
> |_____|      |_____|      |_____|
>    /|\          /|\          /|\
>  ___|___      ___|___         |
>|   |   |    |   |   |     ___|___
>| Datum |    | Datum |    |   |   |
>|       |    |       |    | Datum | (List 2)
>| Next ----->| Next------>|       | 
>|_______|<-----Prev  |<-----Prev  |
>              |_______|    |_______|

My structure looks like the following:
  
  Datum
  Node1  <- List1
  Node2  <- List2
--------------------
  type Base is limited tagged record
    d : Datum;
  end record;
  
  package Base_List1 is new Double_Linked_List (Base);  use Base_List1;
  package Base_List2 is new Double_Linked_List (List1); use Base_List2;
  
  type Node is new Base_List2.Object;
  
  list1 : Base_List1.List;
  list2 : Base_List2.List;
--------------------

Choosing the right part of the data structure is done by static polymorphism
at compile time.