MI ammunition : linked lists

MI ammunition : linked lists

[amado.alves]

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 ;-)

Re: MI ammunition : linked lists

[Stephen Leake]

"amado.alves" <amado.alves@netcabo.pt> writes:

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

Hmm. I've been using doubly linked lists, and never felt a lack of MI.

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

Ok so far.

> 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):

Why is "null" ugly? It's a perfectly reasonable value.

>                ______               ______      ______
>    ______     |      |             |      |    |      |
>   |      |<-----Prev |<--- ... <-----Prev |<-----Prev |
>   | Next----->| Next-----> ... --->| Next----->|______|
>   |______|    |______|             |______|    
> 
> It is clear that the middle nodes combine the attributes of the first
> and last nodes. 

Now the "first" and "last" nodes are of a different type than the
"middle" nodes. When I insert a node, the "last" node changes type!

This is a hammer looking for a nail; I'll just use my screwdriver,
thank you.

-- 
-- Stephe

Re: MI ammunition : linked lists

[Frank J. Lhota]

Even where MI is available, I would not implement linked lists this way. Do
we really want the type of a node vary depending on its position on the
list? Do we want to convert the type of end nodes when a new node is added,
or when an end node is removed? Frankly, I just don't see this as the
optimal way to implement lists.

Re: MI ammunition : linked lists

[Jean-Pierre Rosen]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 1209 bytes --]


"amado.alves" <amado.alves@netcabo.pt> a �crit dans le message de news:mailman.293.1068136383.25614.comp.lang.ada@ada-france.org...
>A very common programming task where multiple inheritance (MI) would be
>handy: implementation of doubly linked lists.
[snip]

>  type Middle_Node is new First_Node with Last_Node;
I would take this as a typical example of abuse of MI.
Inheritance should reflect an "is a" relationship. Do you fill comfortable stating that a middle node is a first node and a last
node at the same time?

>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.
So you trade checking a null value for checking a node belonging to a certain class, with a number of extra conversions required....

My advice would be: use MI (and SI as well)  IF AND ONLY IF it makes things simpler.
Don't bother if people tell you that you are not "purely object oriented" ;-)

-- 
---------------------------------------------------------
           J-P. Rosen (rosen@adalog.fr)
Visit Adalog's web site at http://www.adalog.fr

RE: MI ammunition : linked lists

[amado.alves]

<<When I insert a node, the "last" node changes type!>>

Yes, I can see that is a problem for Ada. I guess no tagged types for linked lists then.

This must the shortest MI thread ever :-)

Thanks.

RE: MI ammunition : linked lists

[amado.alves]

<<Frankly, I just don't see this as the optimal way to implement lists.>>

You're probably right. My idea was making the available operations directly dependent on the node type (e.g. no Previous for First). But it seems the cons (type change) beat the pros. Thanks.

Re: MI ammunition : linked lists

[Wes Groleau]

Jean-Pierre Rosen wrote:
> My advice would be: use MI (and SI as well)  IF AND ONLY IF it makes things simpler.
> Don't bother if people tell you that you are not "purely object oriented" ;-)

Really.  Java, which hypes itself as being so great
because it's "pure OO" is _NOT_ pure OO.  (And doesn't
need to be, although it would be nice if one did not
have to handle OO objects and primitives in different ways.)

-- 
Wes Groleau
   ----
   The man who reads nothing at all is better educated
   than the man who reads nothing but newspapers.
                             -- Thomas Jefferson

RE: MI ammunition : linked lists

[amado.alves]

<<Inheritance should reflect an "is a" relationship. Do you fill comfortable stating that a middle node is a first node and a last
node at the same time?...>>

I do saying a Node_Pointing_Both_Ways is a Node_Pointing_Forward and a Node_Pointing_Backward.

But I agree with the general advice. Thanks.

Re: MI ammunition : linked lists

[Simon Wright]

"Jean-Pierre Rosen" <rosen@adalog.fr> writes:

> "amado.alves" <amado.alves@netcabo.pt> a �crit dans le message de news:mailman.293.1068136383.25614.comp.lang.ada@ada-france.org...
> >A very common programming task where multiple inheritance (MI) would be
> >handy: implementation of doubly linked lists.
> [snip]
> 
> >  type Middle_Node is new First_Node with Last_Node;
> I would take this as a typical example of abuse of MI.  Inheritance
> should reflect an "is a" relationship. Do you fill comfortable
> stating that a middle node is a first node and a last node at the
> same time?

I think the names are wrong: Followed_Node and Preceded_Node might be
better. In which case a Middle_Node would indeed be both.

I think the problem occurs when adding at the front or back of the
list -- what was a Preceded_Node (at the end) now has to be replaced
by a Middle_Node, which means that the next-to-last node has to have
its Followed_By pointer changed to access the new next-to-last node
.. grim .. similar problems on deletion .. really not worth the
aggravation!

> My advice would be: use MI (and SI as well) IF AND ONLY IF it makes
> things simpler.  Don't bother if people tell you that you are not
> "purely object oriented" ;-)

Yes!

-- 
Simon Wright                               100% Ada, no bugs.

Re: MI ammunition : linked lists

[Dmitry A. Kazakov]

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

Re: MI ammunition : linked lists

[Dmitry A. Kazakov]

On 06 Nov 2003 21:03:59 +0000, Simon Wright <simon@pushface.org>
wrote:

>"Jean-Pierre Rosen" <rosen@adalog.fr> writes:
>
>> "amado.alves" <amado.alves@netcabo.pt> a �crit dans le message de news:mailman.293.1068136383.25614.comp.lang.ada@ada-france.org...
>> >A very common programming task where multiple inheritance (MI) would be
>> >handy: implementation of doubly linked lists.
>> [snip]
>> 
>> >  type Middle_Node is new First_Node with Last_Node;
>> I would take this as a typical example of abuse of MI.  Inheritance
>> should reflect an "is a" relationship. Do you fill comfortable
>> stating that a middle node is a first node and a last node at the
>> same time?
>
>I think the names are wrong: Followed_Node and Preceded_Node might be
>better. In which case a Middle_Node would indeed be both.
>
>I think the problem occurs when adding at the front or back of the
>list -- what was a Preceded_Node (at the end) now has to be replaced
>by a Middle_Node, which means that the next-to-last node has to have
>its Followed_By pointer changed to access the new next-to-last node
>.. grim .. similar problems on deletion .. really not worth the
>aggravation!

The nodes have to mutate. This is a semantical problem, and by no
means one of MI. See my response to the original post. The problem is
that if we distinguish nodes in any way, no matter how this difference
is exposed, we have to mutate a root node into a middle node an back.
This has nothing to do with whether middle nodes are descendants of
root nodes or not.

BTW in an Ada implementation of graphs, I did, the nodes were still
mutating, being SI.

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

Re: MI ammunition : linked lists

[Dmitry A. Kazakov]

Frank J. Lhota wrote:

> Even where MI is available, I would not implement linked lists this way.
> Do we really want the type of a node vary depending on its position on the
> list? Do we want to convert the type of end nodes when a new node is
> added, or when an end node is removed?

YES!

There are two opposite variants of list design. One of them, most people
seems keeping in mind, is to have a list element and then to add object
specific things:

type List_Element is ...;
type My_Object_In_A_List is new List_Element with private;

This sort of design faces many problems. What if My_Object_... has to be in
many lists simultaneously? No way. Then to the problem you and others
mention. It exists because an inheritance by extension from List_Element
fixes the representation of My_Object_... This is inherently bad. You can
argue that to have different representations for root, middle and end nodes
is wrong, and flatten them to be of same type, as all here propose. Let
accept it for a minute. How about another challenge. What if we have
different list representation? What if there is Double_Linked_List_Element,
Array_List_Element, Persistent_List_Element, Remote_List_Element and
My_Object could be put in either of them? By inheriting form a specific
element type, we produce different object types, depending on the element
representation. And if you move an object from one list to another it still
has to mutate! - This has nothing to do with MI! -

An alternative design could be objects independent from list elements. A
"list element" could act as a smart pointer to My_Object_...'Class. If you
do this, then mutating a list element would cause no problem, because it
would not affect the object itself. It is just like to get another pointer
to it. Because List_Elements are small (up to two fields), it would be very
efficient [assuming that List_Elements could be by-value]. In this case MI
would offer a type-safe representation for list elements. It is a clear
advantage. The problem with this approach is that:

1. user-defined access types are presently not supported, which makes
implementation of smart pointers (by controlled types) very difficult and
inefficient;

2. access types and user-defined by-value types cannot be tagged;

3. initialization / finalization is allowed for controlled types only;

4. there is no MI, after all.

I think that to fix 1-3 [and arguably 4] would drastically improve Ada, at
least much more than introdicing += or saturated arithmetics.

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

Re: MI ammunition : linked lists

[Lutz Donnerhacke]

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

Re: MI ammunition : linked lists

[Marius Amado Alves]

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.

Re: MI ammunition : linked lists

[Lutz Donnerhacke]

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

Re: MI ammunition : linked lists

[Marius Amado Alves]

On Tue, 2003-11-11 at 09:32, Lutz Donnerhacke wrote:
> ...
>   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;

I think you've failed to define List1 before using it here. But anyway
this does not look like data being shared between lists. It looks like a
list of lists, which a different thing entirely. Recursive containers. A
fascinating subject, because there is so many ways to do it, depending
on many factors, the principal perhaps being the features of the
container library used. I also abhor pointers, and prefer static
polymorphism. I discuss this in AI-302, and possibly in Ada-Europe 2004.
Actually in the case of data sharing between containers, I don't think
you can escape some sort of pointing. But you can avoid access types.
With the proper container library, you can select one container to be
the "master" (not in the ARM sense), and then make the elements of a
second container reference the elements of the master in terms of
iterators or whatever types the master provides for element
identification.

Re: MI ammunition : linked lists

[Lutz Donnerhacke]

* Marius Amado Alves wrote:
> On Tue, 2003-11-11 at 09:32, Lutz Donnerhacke wrote:
>>   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;
>
> I think you've failed to define List1 before using it here.

My fault.
 package Base_List2 is new Double_Linked_List (List1.Object); use Base_List2;

> But anyway this does not look like data being shared between lists.

generic
   type Node(<>) is abstract tagged limited private;
package Double_Linked_List is
   type Object is abstract limited new Node with private;
   type List ist limited private;
   ...
private
   type Node_Ptr is access all Object;
   type Object is abstract limited new Node with record
      next, prev : Node_Ptr := Object'Access;
   end record;
   
   type List is limited record
     start, end : Node_Ptr := List'Access;
   end record;
end Double_Linked_List;
   

> It looks like a list of lists, which a different thing entirely.
> Recursive containers.

No, it's a plain mixin.

> Actually in the case of data sharing between containers, I don't think
> you can escape some sort of pointing.

Of course, but you should hide them in the enclosing structure. It's bad
design to collect pointers explicitly.

Re: MI ammunition : linked lists

[Robert I. Eachus]

Lutz Donnerhacke wrote:
> * Marius Amado Alves wrote:

> My fault.
>  package Base_List2 is new Double_Linked_List (List1.Object); use Base_List2;
Should be Base_List1.Object, right?

>>But anyway this does not look like data being shared between lists.

It is.  What is going on is that you have two doubly linked lists and 
Objects can be on one or the other list, or both, and in different 
orders in the two lists.  Using mix-ins this way is very powerful.  I 
have used a slightly more complex version of this to create a sparse 
matrix type.  Since the elements are kept in sorted order by each index, 
most matrix operations can be completed in times proportional to the 
number of non-zero entries.  (Oh, and the matrix and vector objects are 
controlled, but the package maintains a collection of free nodes, which 
are not controlled, and allocates more as needed 1000 at a time.)

-- 
                                           Robert I. Eachus

100% Ada, no bugs--the only way to create software.

Re: MI ammunition : linked lists

[Marius Amado Alves]

On Tue, 2003-11-11 at 16:09, Robert I. Eachus wrote:
> > * Marius Amado Alves wrote:
> >>But anyway this does not look like data being shared between lists.
> 
> It is.  What is going on is that you have two doubly linked lists and 
> Objects can be on one or the other list, or both, and in different 
> orders in the two lists.

You're right. I misunderstood slightly. Sorry.

> Using mix-ins this way is very powerful.  I 
> have used a slightly more complex version of this to create a sparse 
> matrix type.  Since the elements are kept in sorted order by each index, 
> most matrix operations can be completed in times proportional to the 
> number of non-zero entries...

Sounds great. I'd love to see a complete example. Don't you have the
"type change problem" when you deleted an object from one list but not
the other?

Re: MI ammunition : linked lists

[Georg Bauhaus]

amado.alves <amado.alves@netcabo.pt> wrote:
: <<Inheritance should reflect an "is a" relationship. Do you fill comfortable stating that a middle node is a first node and a last
: node at the same time?...>>
: 
: I do saying a Node_Pointing_Both_Ways is a Node_Pointing_Forward and a Node_Pointing_Backward.
: 
: But I agree with the general advice. Thanks.

Maybe there is another clear picture, if you think of slightly
more complex structure than a list. You can "ask" a node, "do
you have a predecessor/successor?", but what question are you
going to ask a graph node?
For example, if a star is a node with indegree >= 5, does it
make sense to employ any kind of ihneritance to reflect an
indegree of 5?


Georg

Re: MI ammunition : linked lists

[Marius Amado Alves]

On Tue, 2003-11-11 at 18:38, Georg Bauhaus wrote:
> amado.alves <amado.alves@netcabo.pt> wrote:
> : <<Inheritance should reflect an "is a" relationship. Do you fill comfortable stating that a middle node is a first node and a last
> : node at the same time?...>>
> : 
> : I do saying a Node_Pointing_Both_Ways is a Node_Pointing_Forward and a Node_Pointing_Backward.
> : 
> : But I agree with the general advice. Thanks.
> 
> Maybe there is another clear picture, if you think of slightly
> more complex structure than a list. You can "ask" a node, "do
> you have a predecessor/successor?", but what question are you
> going to ask a graph node?
> For example, if a star is a node with indegree >= 5, does it
> make sense to employ any kind of ihneritance to reflect an
> indegree of 5?

The main question to be a asked a graph node is "what nodes are attached
to you?" The reply is a iterator over the corresponding nodes.

(Note another reply in this thread made the same claim for MI for linked
lists regarding names with different names than mine but with the same
exact meaning.)

Re: MI ammunition : linked lists

[Georg Bauhaus]

Marius Amado Alves <amado.alves@netcabo.pt> wrote:
: On Tue, 2003-11-11 at 18:38, Georg Bauhaus wrote:
:> amado.alves <amado.alves@netcabo.pt> wrote:
:> : <<Inheritance should reflect an "is a" relationship. Do you fill comfortable stating that a middle node is a first node and a last
:> : node at the same time?...>>
:> : 
:> : I do saying a Node_Pointing_Both_Ways is a Node_Pointing_Forward and a Node_Pointing_Backward.
:> : 
:> : But I agree with the general advice. Thanks.
:> 
:> Maybe there is another clear picture, if you think of slightly
:> more complex structure than a list. You can "ask" a node, "do
:> you have a predecessor/successor?", but what question are you
:> going to ask a graph node?
:> For example, if a star is a node with indegree >= 5, does it
:> make sense to employ any kind of ihneritance to reflect an
:> indegree of 5?
: 
: The main question to be a asked a graph node is "what nodes are attached
: to you?" The reply is a iterator over the corresponding nodes.
: 
: (Note another reply in this thread made the same claim for MI for linked
: lists regarding names with different names than mine but with the same
: exact meaning.)

Hm, interesting, so the structural relation between nodes in a graph is
provided by an iterator pointing to 0 or more of the neigbours in some
order. That could be applied to lists as well... 

Still the reply is an iterator
pointing_to_this_neighbour, and then also
pointing_to_the_next_neighbour, and then also
..., and finally
???

O.K., I'll stop insiting and iterating.


Georg

Re: MI ammunition : linked lists

[Lutz Donnerhacke]

* Marius Amado Alves wrote:
> Sounds great. I'd love to see a complete example. Don't you have the
> "type change problem" when you deleted an object from one list but not
> the other?

No.

RE: MI ammunition : linked lists

[amado.alves]

"...so the structural relation between nodes in a graph is
provided by an iterator pointing to 0 or more of the neigbours in some
order. That could be applied to lists as well... "

Exactly. Actually I'm entertaining the idea of a list being a particular case of tree namely of a tree with a fixed or bounded fanout (outdegree) of 1.