Re: ADT Lib (3)

[Ian Rae <ianrae@istar.ca>]

I don't have time for a lot of thought about ADTs but here are a few
points.

1. I like the general approach that is trying to find a balance between
power
 and convenience.  NodeDesc having next and prev pointers seems worthwhile
 because its highly convenient.

2. A RemoveAll function would also be convenient.  It would return the list
to
 an empty state without destroying any objects.

3. Riders need to traverse the list in a known order -- the order of the
items in
 the list!  MVA's suggestion that 

MVA>In particular, no assumptions are made over the particular order in
MVA>which data elements are visited.  The only guarantee is this: as long

seems to make sense only for unordered data types like sets.

4. Riders should have a Reset function that moves them back to the
beginning
 of the list.  Much more convenient and efficient than having to create a
new
 rider if you need to traverse a list several times.

5. Some solution needs to be found for destructive traversal of lists using
Riders.
Often one needs to do something like

   //remove all items in list matching 'target'
   r :=mylist.NewRider();
   obj := r.Next();
   WHILE (obj # NIL) DO (* for each element.. *)
      IF obj.foo(blah) = target THEN
	mylist.Remove(obj);
      END;
      obj := r.Next()
   END;	

  Probably this should be done by a sub-type so as not to
  burden the ordinary Rider which only supports non-destructive traversal.

  Perhaps NewRider should be follow a factory pattern that creates a
  variety of rider types based on its arguments.  Then the user could
  specify a fast rider or a 'safe' rider (for non-destructive traversal).

   PROCEDURE (l: List) NewRider(whichType: INTEGER): Rider;

My 2 cents for today.

--Ian