ADT List

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

MKG has not refined his container module, and he won't be able to so
during this month.  Therefore I am volunteering to be the official OOC
ADT Library godfather.  Because no one else seems to be eager to fill
this vacancy, this means I am immediately accepted for this job ;-)

I want to coordinate the development of some basic ADTs, starting with
the list class brought up by MKG.  The general framework is, as he
described it, the "single root model".  Note that I do not intend to
participate in the implementation of these modules.  I want to
restrict myself to drawing up the modules specifications.  Once the
specs are sound, the actual implementation should be simple.  Read: I
am expecting other people to implement the modules we agree upon.

I am starting the discussion (again) with the first draft of a module
interface.  Please keep in mind, that this module is intended as a
role model for a whole family of ADT implementations.  Any faults that
we make here will make us unhappy further on.  Right now I ONLY want
to see comments that apply to this module, its general design, or its
base classes.  Also, comments should be as precise as possible,
preferably accompanied by a piece of pseudo code.


Notes:
======

Naming of entities in the module is open for discussion.

I left most procedure specifications empty.  IMO most of them are
obvious.  Because this is a very first draft, I want to start small.
All exported entities will get full descriptions in the future.

Because other ADTs may need further procedure arguments, `Init' and
`New' are implemented as normal procedures.  If they would be a
type-bound procedures, we would be forced to have parameterless `Init'
and `New' for all out ADTs.

Most operations are destructive.  E.g., `Reverse' and `Filter' act
upon the list itself, instead of creating a modified copy.  If
desired, the user can explicitly call `Copy'.


Open questions:
===============

Should we allow to store the NIL object in a list?

How many specializations should be provide in the module interface?
E.g., `Append' and `Prepend' are simple specializations of
`InsertAfter' and `InsertBefore'.  We have `Remove'.  Do we need
specialized procedures to remove the first/last element?

Currently, ADT List is a direct descendant of the type `Object'.
Should we define a intermediate (possibly abstract) type
Container/Collection/Bag?  And what properties should this
intermediate type have?  [If anyone answers to this with "let's
introduce xyz" WITHOUT giving a detailed outline and a module
interface, I am seriously annoyed.]

Persistence.  Should we integrate generic load/store mechanisms into
our library?  I think there are three different approaches to this
problem in the Oberon community: the one presented in Moessenboeck's
"OOP in O2", the one used by Gadgets, and the version described in
Templ's diss "Meta-programming in Oberon".  I cannot comment on the
pros and cons of the approaches, because I do not know Gadgets at all.

Another thing: I wondered why we should not provide two
implementations of certain ADTs, e.g. a "single root" list for
flexibility and a "low-overhead" list (as presented by MKG at the very
beginning of this thread) for efficiency.  I would expect, that
libraries like VO use the "flexible" implementation, while specialized
data structures in a user's program may prefer the "low-overhead"
variant.  Well, just an idea.  We need the specs for the "flexible"
list before we can derive a low-cost subset from it.

-- mva


------------------------------------------------------------------------

MODULE StdTypes;

TYPE
  Object* = POINTER TO ObjectDesc;
  ObjectDesc* = RECORD
  END;
  
TYPE
  Operator* = POINTER TO OperatorDesc;
  OperatorDesc* = RECORD
  END;

TYPE
  Function* = POINTER TO FunctionDesc;
  FunctionDesc* = RECORD
  END;

TYPE
  Predicate* = POINTER TO PredicateDesc;
  PredicateDesc* = RECORD
  END;

PROCEDURE (op: Operator) Apply (obj: Object);
  END Apply;

PROCEDURE (fct: Function) Apply (obj: Object): Object;
  BEGIN
    RETURN NIL
  END Apply;

PROCEDURE (pred: Predicate) Apply (obj: Object): BOOLEAN;
  BEGIN
    RETURN FALSE
  END Apply;

END StdTypes.

------------------------------------------------------------------------

MODULE List;

IMPORT
  StdTypes;
  
TYPE
  Node* = POINTER TO NodeDesc;
  NodeDesc = RECORD
    next-, prev-: Node;
    (* The read-only fields `next' and `prev' are provided for efficient 
       navigation.  A value of NIL designates the end of the list. *)
    obj-: StdTypes.Object;
    (* Data of the list element.  *)
  END;
  
  List* = POINTER TO ListDesc;
  ListDesc* = RECORD
    (StdTypes.ObjectDesc)
    head, tail: Node;
  END;


(* Constructors and Deconstructors
   ======================================================================== *)
   
PROCEDURE Init* (l: List);
(* Initializes the instance of `List' to the empty list.  *)
  BEGIN
    l. head := NIL;
    l. tail := NIL
  END Init;

PROCEDURE New*(): List;
(* Creates an instance of `List', and initializes it to the empty list.  *)
  VAR
    l: List;
  BEGIN
    NEW (l);
    Init (l);
    RETURN l
  END New;

PROCEDURE Destroy* (VAR l: List);
(* Removes all elements from list `l' and destroys the list object itself.
   The variable parameter `l' is set to NIL.
   Note: The user is not required to call this procedure.  Resources like 
   unused lists are automatically freed by the garbage collector.  This
   procedure is provided for convenience, both for the user and the garbage
   collector.  *)
  END Destroy;

PROCEDURE (l: List) Copy* (): List;
(* Creates a copy of the given list `l'.  *)
  END Copy;
  

(* Node Insertion
   ======================================================================== *)

PROCEDURE (l: List) Append* (obj: StdTypes.Object);
  END Append;
  
PROCEDURE (l: List) Prepend* (obj: StdTypes.Object);
  END Prepend;

PROCEDURE (l: List) InsertAfter* (node: Node; obj: StdTypes.Object);
  END InsertAfter;
  
PROCEDURE (l: List) InsertBefore* (node: Node; obj: StdTypes.Object);
  END InsertBefore;
  
PROCEDURE (l: List) AppendList* (src: List);
(* Afterwards, `src' is reduced to the empty list.  *)
  END AppendList;


(* Node Removal
   ======================================================================== *)
   
PROCEDURE (l: List) Remove* (node: Node);
(* Note: Operations on a removed node are undefined.  In practice, the fields 
   of a removed node are set to NIL, to limit the scope of potential unwanted
   side effects, and to simplify debugging.  *)
  END Remove;
  
PROCEDURE (l: List) Replace* (node: Node; obj: StdTypes.Object);
  END Replace;
  

(* List Permutations
   ======================================================================== *)
   
PROCEDURE (l: List) Reverse*;
  END Reverse;

PROCEDURE (l: List) MoveAfter* (dest, node: Node);
  END MoveAfter;
  
PROCEDURE (l: List) MoveBefore* (dest, node: Node);
  END MoveBefore;
  

(* Node Retrieval
   ======================================================================== *)

PROCEDURE (l: List) First* (): Node;
  END First;
  
PROCEDURE (l: List) Last* (): Node;
  END Last;
  
PROCEDURE (l: List) Get* (obj: StdTypes.Object): Node;
  END Get;
  

(* Iterators
   ======================================================================== *)

PROCEDURE (l: List) Apply* (op: StdTypes.Operator);
(* Successively applies operator `op' to the elements of `l'.  *)
  END Apply;

PROCEDURE (l: List) Map* (fct: StdTypes.Function): List;
(* Successively applies the function `fct' to the elements of `l', and collects
   the results into a new list.  The list `l' is not destroyed.  *)
  END Map;

PROCEDURE (l: List) Filter* (pred: StdTypes.Predicate);
(* Successively applies the predicate `fct' to the elements of `l'.  Nodes,
   for which `pred' evaluates to FALSE, are removed from the list.  *)
  END Filter;


(* Miscellaneous
   ======================================================================== *)

PROCEDURE (l: List) IsEmpty* (): BOOLEAN;
  END IsEmpty;

PROCEDURE (l: List) Length* (): LONGINT;
  END Length;

END List.