ADT Lib (7)

[Michael van Acken <mvacken@t-online.de>]

IR> MVA> With such semantics, I can add these methods to container again.  The
IR> MVA> question is: Is it worthwhile to have methods with such vague
IR> MVA> semantics?  Does anyone second this?
IR> MVA> 
IR> MVA> Another question: With the above specification, is it guaranteed that
IR> MVA> the statement sequence
IR> MVA>   c.Add(foo); c. Remove(foo);
IR> MVA> is a "no operation", i.e., will not change the state of `c' or the
IR> MVA> system?
IR> 
IR> Hmmm.  Add followed by Remove should be a no operation.  The only
IR> suggestion I see is to make Remove symmetrical to Add:
IR> 
IR> PROCEDURE (c: Container) Remove* (obj: AcObject.Object);
IR> (* Removes obj from c.  Post-condition is that obj is not a
IR>  member of c.  If obj is in in c multiple times, all copies are removed.
IR>  If obj is not in c then nothing is done.
IR> *)
IR> 
IR> The semantics are unusual and by being functions of AcContainer,
IR> all ADTs are forced to provide an implementation!  So I'm not sure
IR> the convenience of generic Add/Remove is worth it.

I agree with this.  If we make Add/Remove a required part of the
Container interface, then all specializations must support this.  If
we cannot stick some useful semantics to these procedures, they remain
in fact unusable.  Therefore I am not including them in AcContainer.

--------

For the module AcContainer I have introduced a method `Apply' and a
predicate `HasApply'.  In AcContainer.Mod they are defined like this: 

PROCEDURE (c: Container) Apply* (op: AcObjFct.Operator);
(* Successively applies operator `op' to the elements of `c'.  This procedure
   is only available for specializations of container that hold objects.  The
   procedure is a "no operation" for all other containers.
   
   For example, the module `String' defines a character based container, and 
   does not implement this procedure.  See also `HasApply'.  *)
  END Apply;

PROCEDURE (c: Container) HasApply* (): BOOLEAN;
(* Returns TRUE, if the container `c' provides a functional type-bound 
   procedure `Apply'.  If result is FALSE, `Apply' is a "no operation".  *)
  BEGIN
    RETURN FALSE
  END HasApply;

The concrete implementation in ListDL.Mod has these specs:

PROCEDURE (l: List) Apply* (op: AcObjFct.Operator);
(* Successively applies operator `op' to the elements of `l'.  The procedure
   `op.Apply' must not perform any structural modifications on `l' (like 
   insertion, removal, or moving elements), or the result of this procedure is
   undefined.
   cost: O(n) time, O(1) space, disregarding any effects of `op.Apply'  *)

Note that I have not included the iterators `Map' and `Select' in the
interface of AcContainer.  IMO these methods are not generalized
enough to impose them on all container implementations.


As always, you can get the most recent files from
http://home.t-online.de/home/mvacken

This time I have added the full implementation of ListDL.Mod.  None of
the procs has been tested, but debugging them should be not much of a
problem.  After all, all of them are quite simple and very small.  I
won't repost the module interface here.  If you are interested, get
the file from the ftp server.  Note: To use the modules, you will need
oo2c 1.3.7 or higher.

-- mva