(*====================================================================*)
(*                  Peter M. Perchansky                               *)
(*              412-1 Springside, Drive East                          *)
(*                 Shillington, PA  19607                             *)
(*                                                                    *)
(*             CompuServe 71301,344                                   *)
(*             FidoNet    1:273/101                                   *)
(*             Interlink                                              *)
(*====================================================================*)

The following is my implentation of a generic deque using JPI's TopSpeed
Modula-2 (version 1.17).  A deque is a form of double-ended queue (or
stack depending on your point of view).  The deque abstract data type
allows you to do both queue and stack operations.

The queue operations are based on the following:  The front of the queue
is the root node.  Enqueueing data will place the node at the rear of
the queue.  Dequeueing (serving) data will remove the node from the
front of the queue.

The stack operations are based on the following:  The top of the stack
is the end node.  Pushing data will place the node at the rear (top) of
the stack.  Popping data will remove data from the rear (top) of the
stack.

Most procedures set a boolean value (Ok) to FALSE upon hitting an error
condition.  You are responsible for handling these errors in the calling
module.  Errors that can occur are as follows:  Enqueue or Push was
performed on a full deque; Dequeue, Pop, Front, or Back was performed on
an empty deque; the contents being retrieved in Dequeue, Pop, Front, or
Back did not match the size of the VARed variable holder.

This library module is generic.  Any data type (both standard and
user-defined) can be operated on in the deque.  You can even mix and
match data types witin the deque; however, you are responsible for
keeping track of what types are in the deque.

Future versions of this module will include procedures to compare
deques, append one deque to another deque, search for elements within
the deque, etc.

Please feel free to contact me via postal mail, CompuServe, FidoNet, or
Interlink (language or Pascal Conference <they are working on adding a
Modula-2 Conference>) if you have any questions or comments.

<-------------------------- cut here --------------------------------->

(*====================================================================
  =  Program Id:     PMPDEQUE                                        =
  =  Programmer:     Peter M. Perchansky                             =
  =  Purpose:        Export procedures for dealing with circular     =
  =                  deques.                                         =
  =  Date Written:   10-29-89                                        =
  ====================================================================*)

DEFINITION MODULE PMPDeque;

FROM SYSTEM IMPORT BYTE;

TYPE
    Deques;            (* opaque type *)

PROCEDURE Empty        (deque : Deques) : BOOLEAN;
(* Return TRUE if the deque is NIL *)

PROCEDURE Full         (size : CARDINAL) : BOOLEAN;
(* Return TRUE if there is no Available memory for another deque node *)

PROCEDURE CreateDeque  (VAR deque : Deques);
(* Creates the deque by making it NIL *)

PROCEDURE DestroyDeque (VAR deque : Deques);
(* Destroys the deque by deallocating deque nodes *)

PROCEDURE DequeLength (deque : Deques) : CARDINAL;
(* Returns the number of nodes in the deque *)

PROCEDURE Enqueue      (data : ARRAY OF BYTE; VAR deque : Deques; VAR Ok : BOOLEAN);
(* Place data in node at back of deque.  Ok is set FALSE upon error *)

PROCEDURE Push         (data : ARRAY OF BYTE; VAR deque : Deques; VAR Ok : BOOLEAN);
(* Place data in node bat back of deque.  Ok is set FALSE upon error *)

PROCEDURE Dequeue      (VAR data : ARRAY OF BYTE; VAR deque : Deques; VAR Ok : BOOLEAN);
(* Place data from front of deque.  Remove front of deque.  Ok is set *)
(* to FALSE upon error                                                *)

PROCEDURE Pop          (VAR data : ARRAY OF BYTE; VAR deque : Deques; VAR Ok : BOOLEAN);
(* Place data from back of deque.  Remove back of deque.  Ok is set   *)
(* to FALSE upon error                                                *)

PROCEDURE Front        (VAR data : ARRAY OF BYTE; deque : Deques; VAR Ok : BOOLEAN);
(* Place data fron front of deque.  Ok is set FALSE upon error *)

PROCEDURE Back         (VAR data : ARRAY OF BYTE; deque : Deques; VAR Ok : BOOLEAN);
(* Place data from back of deque.  Ok is set FALSE upon error *)

END PMPDeque.

<-------------------------- cut here --------------------------------->

(*====================================================================
  =  Program Id:     PMPDEQUE                                        =
  =  Programmer:     Peter M. Perchansky                             =
  =  Purpose:        Export procedures for dealing with circular     =
  =                  deques.                                         =
  =  Date Written:   10-29-89                                        =
  ====================================================================*)

IMPLEMENTATION MODULE PMPDeque;

(*============= Procedures from JPI's TopSpeed Modula II =============*)
FROM Lib      IMPORT Move;
FROM SYSTEM   IMPORT ADDRESS, BYTE, SIZE;
FROM Storage  IMPORT ALLOCATE, Available, DEALLOCATE;

TYPE
    Deques        = POINTER TO DequeNodes;  (* opaque type defined *)

    DequeNodes    = RECORD                  (* node *)
                      contents : ADDRESS;   (* contents of node *)
                      size     : CARDINAL;  (* size of contents *)
                      next     : Deques;    (* pointer to next node *)
                      previous : Deques;    (* pointer to prev node *)
                    END;

PROCEDURE Empty        (deque : Deques) : BOOLEAN;
(* Return TRUE if the deque is NIL *)

BEGIN
    RETURN deque = NIL;
END Empty;

PROCEDURE Full         (size : CARDINAL) : BOOLEAN;
(* Return TRUE if there is no Available memory for another deque node *)

BEGIN
    RETURN (NOT (Available (SIZE (DequeNodes)) AND Available (size)));
END Full;

PROCEDURE CreateDeque  (VAR deque : Deques);
(* Creates the deque by making it NIL *)

BEGIN
    deque := NIL;
END CreateDeque;

PROCEDURE DestroyDeque (VAR deque : Deques);
(* Destroys the deque by deallocating deque nodes *)

VAR
    temp    : Deques;

BEGIN
    WHILE NOT Empty (deque) DO
          (* if at the front of the deque, then remove the front *)
          (* and make the deque empty                            *)

          IF deque^.next = deque THEN
             DEALLOCATE (deque^.contents, deque^.size);
             DEALLOCATE (deque, SIZE (DequeNodes));
             deque := NIL;
          ELSE

          (* otherwise continue removing the front of the deque  *)
          (* until deque^.next = deque                           *)

             temp := deque;
             deque := deque^.next;
             temp^.previous^.next := deque;
             deque^.previous := temp^.previous;
             DEALLOCATE (temp^.contents, temp^.size);
             DEALLOCATE (temp, SIZE (DequeNodes));
          END;
    END;
END DestroyDeque;

PROCEDURE DequeLength (deque : Deques) : CARDINAL;
(* Returns the number of nodes in the deque *)

VAR
    current : Deques;
    count   : CARDINAL;

BEGIN
    IF NOT Empty (deque) THEN

       IF deque^.next = deque THEN          (* only front exists *)
          count := 1;
       ELSE
          count := 1;                       (* count front *)
          current := deque^.next;

          WHILE current # deque DO          (* walk from 2nd until front *)
                INC (count);
                current := current^.next;
          END;
       END;
    ELSE
       count := 0;
    END;

    RETURN count;
END DequeLength;

PROCEDURE Enqueue      (data : ARRAY OF BYTE; VAR deque : Deques; VAR Ok : BOOLEAN);
(* Place data in node at back of deque.  Ok is set FALSE upon error *)

VAR
    temp        : Deques;
    dataSize    : CARDINAL;     (* size of data *)

BEGIN
    dataSize := HIGH (data) + 1;
    Ok := NOT Full (dataSize);
    IF Ok THEN
       ALLOCATE (temp, SIZE (DequeNodes));
       ALLOCATE (temp^.contents, dataSize);
       Move (ADR (data), temp^.contents, dataSize);
       temp^.size := dataSize;

       IF deque = NIL THEN          (* create front *)
          temp^.next := temp;
          temp^.previous := temp;
          deque := temp;
       ELSE                         (* add to end   *)
          temp^.next := deque;
          temp^.previous := deque^.previous;
          deque^.previous^.next := temp;
          deque^.previous := temp;
       END;
    END;
END Enqueue;

PROCEDURE Push         (data : ARRAY OF BYTE; VAR deque : Deques; VAR Ok : BOOLEAN);
(* Place data in node bat back of deque.  Ok is set FALSE upon error *)

BEGIN
    Enqueue (data, deque, Ok);
END Push;

PROCEDURE Dequeue      (VAR data : ARRAY OF BYTE; VAR deque : Deques; VAR Ok : BOOLEAN);
(* Place data from front of deque.  Remove front of deque.  Ok is set *)
(* to FALSE upon error                                                *)

VAR
    temp        : Deques;
    dataSize    : CARDINAL;     (* size of data *)

BEGIN
    Ok := NOT Empty (deque);
    IF Ok THEN
       dataSize := HIGH (data) + 1;

       Ok := deque^.size = dataSize;

       (* size of data must equal the size of contents *)

       IF Ok THEN
          Move (deque^.contents, ADR (data), deque^.size);

          (* if at front of the deque, then remove the front *)
          (* and set the deque to NIL                        *)

          IF deque^.next = deque THEN
             DEALLOCATE (deque^.contents, deque^.size);
             DEALLOCATE (deque, SIZE (DequeNodes));
             deque := NIL;
          ELSE

          (* otherwise remove the front of the queue, and    *)
          (* make the second node the front                  *)

             temp := deque;
             deque := deque^.next;
             temp^.previous^.next := deque;
             deque^.previous := temp^.previous;
             DEALLOCATE (temp^.contents, temp^.size);
             DEALLOCATE (temp, SIZE (DequeNodes));
          END;
       END;
    END;
END Dequeue;

PROCEDURE Pop          (VAR data : ARRAY OF BYTE; VAR deque : Deques; VAR Ok : BOOLEAN);
(* Place data from back of deque.  Remove back of deque.  Ok is set   *)
(* to FALSE upon error                                                *)

VAR
  temp       : Deques;
  dataSize   : CARDINAL;        (* size of data *)

BEGIN
    Ok := NOT Empty (deque);
    IF Ok THEN
       dataSize := HIGH (data) + 1;

       (* if at front of the deque, then remove the front *)
       (* and set the deque to NIL                        *)

       IF deque^.next = deque THEN

          Ok := deque^.size = dataSize;

          (* size of data must equal size of contents *)

          IF Ok THEN
             Move (deque^.contents, ADR (data), deque^.size);
             DEALLOCATE (deque^.contents, deque^.size);
             DEALLOCATE (deque, SIZE (DequeNodes));
             deque := NIL;
          END;
       ELSE

       (* otherwise remove the back of the queue *)

          Ok := deque^.previous^.size = dataSize;

          (* size of data must equal size of contents *)

          IF Ok THEN
             Move (deque^.previous^.contents, ADR (data), deque^.previous^.size);
             temp := deque^.previous;
             deque^.previous^.previous^.next := deque;
             deque^.previous := temp^.previous;
             temp^.next := NIL;
             temp^.previous := NIL;
             DEALLOCATE (temp^.contents, temp^.size);
             DEALLOCATE (temp, SIZE (DequeNodes));
          END;
       END;
    END;
END Pop;

PROCEDURE Front        (VAR data : ARRAY OF BYTE; deque : Deques; VAR Ok : BOOLEAN);
(* Place data fron front of deque.  Ok is set FALSE upon error *)

VAR
    dataSize : CARDINAL;        (* size of data *)

BEGIN
    Ok := NOT Empty (deque);
    IF Ok THEN
       dataSize := HIGH (data) + 1;
       Ok := deque^.size = dataSize;

       (* size of data must equal size of contents *)

       IF Ok THEN
          Move (deque^.contents, ADR (data), deque^.size);
       END;
    END;
END Front;

PROCEDURE Back         (VAR data : ARRAY OF BYTE; deque : Deques; VAR Ok : BOOLEAN);
(* Place data from back of deque.  Ok is set FALSE upon error *)

VAR
    dataSize : CARDINAL;        (* size of data *)

BEGIN
    Ok := NOT Empty (deque);
    IF Ok THEN
       dataSize := HIGH (data) + 1;

       IF deque^.next = deque THEN
          Ok := deque^.size = dataSize;

          (* size of data must equal size of contents *)

          IF Ok THEN
             Move (deque^.contents, ADR (data), deque^.size);
          END;
       ELSE
          Ok := deque^.previous^.size = dataSize;

          (* size of data must equal size of contents *)

          IF Ok THEN
             Move (deque^.previous^.contents, ADR (data), deque^.previous^.size);
          END;
       END;
    END;
END Back;

END PMPDeque.