Re: Container Library?

["Mark K. Gardner" <mkgardne@rtsl3.cs.uiuc.edu>]

(I am placing Michael's reply before my original post, for convenience.)

MVA> Could you give some Oberon-2 pseudo code for this? The involved
MVA> types and their interaction aren't clear to me from this
MVA> description.

Sorry about being too brief. Here is a module which should illustrate
what I mean. (BTW, the module compiles and runs under oo2c v1.3.2.)

(*==================================================================*)
MODULE LinkedList;
  IMPORT
    Out;

  TYPE
    (* "Abstract" base type for elements of a linked list *)
    Element* = POINTER TO ElementDesc;
    ElementDesc* = RECORD
      next, prev : Element;
    END;
    
    (* The linked list type *)
    LinkedList* = POINTER TO ListDesc;
    ListDesc* = RECORD
      head : Element;
    END;

    (* A procedure for operating on elements of the linked list *)
    Operator* = PROCEDURE (element : Element);
  
  (*------------------------------------------------------------------
    Create a linked list.
   *)
  PROCEDURE CreateList* () : LinkedList;
    VAR
      list : LinkedList;
      sentinel : Element;
  BEGIN
    NEW(list);
    NEW(sentinel);
    list.head := sentinel;
    sentinel.next := sentinel;
    sentinel.prev := sentinel;
    RETURN list;
  END CreateList;

  (*------------------------------------------------------------------
    Add an element to the head of a linked list.
   *)
  PROCEDURE (list : LinkedList) Prepend* (element : Element);
  BEGIN
    element.next := list.head.next;
    element.next.prev := element;
    element.prev := list.head;
    list.head.next := element;
  END Prepend;
  
  (*------------------------------------------------------------------
    Delete the element from the linked list.
    Do nothing if the element isn't in the list.
   *)
  PROCEDURE (list : LinkedList) Delete* (element : Element);
    VAR
      current : Element;
  BEGIN
    ASSERT(element # list.head);
    current := list.head.next;
    WHILE (current # element) & (current # list.head) DO
      current := current.next;
    END;
    IF (current = element) & (element # list.head) THEN
      element.next.prev := element.prev;
      element.prev.next := element.next;
	    (* Be GC friendly! *)
	    element.prev := NIL;
      element.next := NIL;
    END;
  END Delete;
  
  (*------------------------------------------------------------------
    Get the last element of the list.
    Return NIL if the list is empty.
   *)
  PROCEDURE (list : LinkedList) Last* () : Element;
    VAR
      element : Element;
  BEGIN
    element := list.head.prev;
    IF element = list.head THEN
      element := NIL;
    END;
    RETURN element;
  END Last;

  (*------------------------------------------------------------------
    Operate on every element of the linked list. 
    
    BE CAREFUL: if you modify the list, the operator 
    must not change the current element's next field.)
   *)
  PROCEDURE (list : LinkedList) Operate* (operate : Operator);
    VAR
      current : Element;
  BEGIN
    current := list.head.next;
    WHILE current # list.head DO
      operate(current);
      current := current.next;
    END
  END Operate;
  
  (*------------------------------------------------------------------
    Test the module.
   *)
  PROCEDURE Test* ();
    TYPE
      IntElement = POINTER TO IntElemDesc;
      IntElemDesc = RECORD (ElementDesc)
        value : INTEGER;
      END;
    VAR
      list : LinkedList;

    PROCEDURE Create () : LinkedList;
      VAR
        i : INTEGER;
        list : LinkedList;
        element : IntElement;
    BEGIN
      list := CreateList();
      FOR i := 1 TO 10 DO
        NEW(element);
        element.value := i;
        list.Prepend(element);
      END;
      RETURN list;
    END Create;

    PROCEDURE Print (element : Element);
      VAR
        myElement : IntElement;
    BEGIN
	    IF element # list.head THEN
        myElement := element(IntElement);
        Out.LongInt(myElement.value, 0);
        Out.Ln();
      END
    END Print;

  BEGIN (* Test *)
    list := Create();
    list.Operate(Print);
    Out.Ln();
    list.Delete(list.Last());
    list.Operate(Print);
  END Test;

BEGIN (* Linked List *)
  Test();
END LinkedList.
(*==================================================================*)

MKG> My design makes each container a record type which manipulates
MKG> pointers to adapter records containing the actual data. Type
MKG> bound procedures are used to perform all the requisite operations
MKG> on the container. (I favor TBP, although conventional procedures
MKG> can be used.) To use the container, one would extend the
MKG> appropriate adapter type to contain the actual data.

To add an INTEGER to the linked list, one needs to define an
"adapter", in this case IntElement, as an extension of the Element
type so data can be placed into the container. In general, an adapter
will need to be made for each type of data which a container holds.

This design provides type safety (but seems a little awkward and
inefficient to me). Either adapters for the built-in types can be
included in each container module of the library or users can be left
to create all adapters. The former choice would increase the size of
executables unless unused types and code can be stripped out. As I
think that would be an unrealistic expectation of the compiler (it is
actually the responsiblity of the linker), I would suggest we let
users create their own adapters.

Mark

-- 
Mark K. Gardner (mkgardne@cs.uiuc.edu)
University of Illinois at Urbana-Champaign
Real-Time Systems Laboratory
--