Re: ADT Lib (5)

[Tim Teulings <tim@edge.ping.de>]

Hallo!

Ok, here are the interfaces for the ADTs Stack and Queue. I only have
taken them from a recently quoted book (Gting) and there are thus not
my personal proposal but they are completly open for discussion in this
list.

I'm also adding a first version of the alterate ADT ListLISP. If time
allows I also will make a proposal for hashtables and/or binary tree,
too.

(none of the modules was compiled, syntactical errors are likely)

(*	$Id$	*)
MODULE AcQueue;

(*
    $Log$
*)


IMPORT
  AcObject, AcContainer;
  
TYPE
  Queue*     = POINTER TO QueueDesc;
  QueueDesc* = RECORD (AcContainer.ContainerDesc)
               END;


  PROCEDURE Init* (q: Queue);
  (* Initializes the instance of `List' to the empty list.  *)
  END Init;

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

  PROCEDURE Destroy* (q: Queue);
  BEGIN
    AcContainer.Destroy (q);
    (* ... *)
  END Destroy;

  (**
    Returns TRUE, if queue is empty, else FALSE.
  **)

  PROCEDURE (q : Queue) Empty*():BOOLEAN;
  END Empty;

  (**
    Returns the first value stored within the queue.
  **)

  PROCEDURE (q : Queue) Front*():AcObject.Object;
  (* pre: ~Queue.Empty() *)
  END Front;

  (**
    removes the first value stored in the queue from the queue.
  **)

  PROCEDURE (q : Queue) Dequeue*();
  (* pre: ~Queue.Empty() *)
  END Dequeue;

  (**
    Appends the given value to the end of the queue.
  **)

  PROCEDURE (q : Queue) Enqueue*(obj: AcObject.Object);
  END Enqueue;

  (**
    Clear the queue, removing all values in the queue. Afterwards
    the queue is empty,
  **)

  PROCEDURE (q : Queue) Clear*();
  END Clear;

END AcQueue.

Possible alternative names for Front:   First
Possible alternative names for Enqueue: RAppend
Possible alternative names for Dequeue: Rest

(*	$Id$	*)
MODULE AcStack;

(*
    $Log$
*)


IMPORT
  AcObject, AcContainer;
  
TYPE
  Stack*     = POINTER TO StackDesc;
  StackDesc* = RECORD (AcContainer.ContainerDesc)
               END;


  PROCEDURE Init* (s: Stack);
  (* Initializes the instance of `List' to the empty list.  *)
  END Init;

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

  PROCEDURE Destroy* (s: Stack);
  BEGIN
    AcContainer.Destroy (s);
    (* ... *)
  END Destroy;

  (**
    Returns TRUE, if stack is empty, else FALSE.
  **)

  PROCEDURE (s : Stack) Empty*():BOOLEAN;
  END Empty;

  (**
    Pops element onto the stack.
  **)

  PROCEDURE (s : Stack) Push*(obj: AcObject.Object);
  END Push;

  (**
    Removes the top lement from the stack.
  **)

  PROCEDURE (s : Stack) Pop*();
  (* pre: ~Stack.Empty() *)
  END Pop;

  (**
    Return the value of the top element.
  **)

  PROCEDURE (s : Stack) Top*():AcObject.Object;
  (* pre: ~Stack.Empty() *)
  END Top;

  (**
    Clear the stack, removing all values on the stack. Afterwards
    the stack is empty,
  **)

  PROCEDURE (s : Stack) Clear*();
  END Clear;

END AcStack.

(*	$Id$	*)
MODULE ListLISP;

(*
    $Log$
*)


IMPORT
  AcObject, AcContainer;
  
TYPE
  List*     = POINTER TO ListDesc;
  ListDesc* = RECORD (AcContainer.ContainerDesc)
              END;


  (* Constructors and Deconstructors
     ======================================================================== *)
   
  PROCEDURE Init* (l: List);
  (* Initializes the instance of `List' to the empty list.  *)
  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* (l: List);
  BEGIN
    AcContainer.Destroy (l);
    (* ... *)
  END Destroy;


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

  PROCEDURE (l: List) Append* (obj: AcObject.Object):List;
  (* pre: obj # NIL *)
  END Append;


  PROCEDURE (l: List) Concat* (list: List):List;
  (* pre: list # NIL *)
  END Concat;


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

  PROCEDURE (l: List) First* (): AcObject.Object;
  END First;
  
  PROCEDURE (l: List) Rest* (): List;
  END Last;


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

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

END ListLISP.

I do not have much knowledge about LISP so I'm not adding semantical
information to the various methods. In fact I'm not sure, how First and
Rest do work. Do they return completely new lists (by allocating their
own List elements), reusing the values or do they manipulate the list
nodes destroying the old list? I'm also not sure what other elementary
methods a LISP list should have. Suggestions welcome.

-- 
Gru...
       Tim.