Power-Programmierung/CD1.mdf/modula2/library/queuem2/deq2.txt

Text File | 1989-12-15 | 24KB | 578 lines

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

The following is my implementation 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 perform 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.

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 within 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 deques.      =
  =  Date Written:   10-29-89                                        =
  ====================================================================*)

DEFINITION MODULE PMPDeque;

(*------------- Procedures from JPI's TopSpeed Modula II -------------*)
FROM SYSTEM IMPORT BYTE;
(*--------------------------------------------------------------------*)


TYPE
    Deques;           (* opaque type defined in implementation module *)

(*  A deque is a circular queue allowing for both queue and stack     *)
(*  operations.  This module is generic, allowing for operations on   *)
(*  any data type.                                                    *)

(*  The deque must be initialized to NIL by calling Create (deque).   *)
(*  Create (deque) should only be called once.  DestroyDeque should   *)
(*  be called when the deque is no longer needed.                     *)

(*  Procedures to initialize/remove the deque:                        *)
(*            CreateDeque  - set deque to NIL                         *)
(*            DestroyDeque - remove deque from memory                 *)

(*  Functions providing status information on the deque:              *)
(*            Empty        - is deque NIL                             *)
(*            Full         - is deque full                            *)
(*            DequeLength  - number of nodes in deque                 *)
(*            DequePos     - node number containing data (if found)   *)
(*            InDeque      - is data in deque                         *)

(*  Procedures to enter data in the deque:                            *)
(*    <queue> Enqueue      - place data in rear of deque              *)
(*    <stack> Push         - place data in rear of deque              *)

(*  Procedures to remove data from the deque:                         *)
(*    <queue> Dequeue      - remove data from the front of the deque  *)
(*    <stack> Pop          - remove data from the rear of the deque   *)
(*            Serve        - remove nth item in the deque             *)

(*  Procedures to show data in the deque:                             *)
(*    <queue> Front        - show data from the front of the deque    *)
(*    <queue> Back         - show data from the rear of the deque     *)
(*    <stack> Top          - show data at top of the deque            *)
(*            Retrieve     - show data from nth item in the deque     *)


PROCEDURE CreateDeque  (VAR deque: Deques);
(* Creates the deque by making it NIL                                 *)
(* This procedure must be called prior to performing operations on    *)
(* the deque.                                                         *)

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

PROCEDURE DestroyDeque (VAR deque: Deques);
(* Destroys the deque by deallocating deque nodes and contents        *)
(* DestroyDeque should be called when the deque is no longer needed   *)
(* in memory.                                                         *)

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

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

PROCEDURE DequePos     (data: ARRAY OF BYTE; deque: Deques): CARDINAL;
(* Returns the number of the node containing the data (if found).     *)
(* Returns 0 if not found.  The front of the deque is treated as node *)
(* number one.                                                        *)

PROCEDURE InDeque      (data: ARRAY OF BYTE; deque: Deques): BOOLEAN;
(* Returns TRUE if data is found in deque.                            *)

PROCEDURE Enqueue      (data: ARRAY OF BYTE; VAR deque: Deques; VAR Ok: BOOLEAN);
(* Place data in node at the back of the deque.  Ok will be set to    *)
(* FALSE under the following conditions:  Deque is full.              *)

PROCEDURE Push         (data: ARRAY OF BYTE; VAR deque: Deques; VAR Ok: BOOLEAN);
(* Place data in node at the back of the deque.  Ok will be set to    *)
(* FALSE under the following conditions:  Deque is full.              *)

PROCEDURE Dequeue      (VAR data: ARRAY OF BYTE; VAR deque: Deques; VAR Ok: BOOLEAN);
(* Place contents from node at the front of the deque into data.      *)
(* Remove the front node of the deque.  Ok is set to FALSE upon the   *)
(* following conditions:  deque is empty, size of data does not equal *)
(* size of contents.                                                  *)

PROCEDURE Pop          (VAR data: ARRAY OF BYTE; VAR deque: Deques; VAR Ok: BOOLEAN);
(* Place contents from node at the back of the deque into data.       *)
(* Remove the back node of the deque.  Ok is set to FALSE upon the    *)
(* following conditions:  deque is empty, size of data does not equal *)
(* size of contents.                                                  *)

PROCEDURE Serve        (VAR data: ARRAY OF BYTE; nthItem: CARDINAL; VAR deque: Deques; VAR Ok: BOOLEAN);
(* Place contents from nth node of the deque into data.  Remove the   *)
(* nth node of the deque.  Ok is set to FALSE upon the following      *)
(* conditions:  deque is empty, size of data does not equal size of   *)
(* contents, nthItem is greater than number of nodes in the deque.    *)

PROCEDURE Front        (VAR data: ARRAY OF BYTE; deque: Deques; VAR Ok: BOOLEAN);
(* Place contents from node at the front of the deque into data.      *)
(* Ok is set to FALSE upon the following conditions:  deque is empty, *)
(* size of data does not equal size of contents.                      *)

PROCEDURE Back         (VAR data: ARRAY OF BYTE; deque: Deques; VAR Ok: BOOLEAN);
(* Place contents from node at the back of the deque into data.       *)
(* Ok is set to FALSE upon the following conditions:  deque is empty, *)
(* size of data does not equal size of contents.                      *)

PROCEDURE Top          (VAR data: ARRAY OF BYTE; deque: Deques; VAR Ok: BOOLEAN);
(* Place contents from node at the back (top) of the deque into data. *)
(* Ok is set to FALSE upon the following conditions:  deque is empty, *)
(* size of data does not equal size of contents.                      *)

PROCEDURE Retrieve     (VAR data: ARRAY OF BYTE; nthItem: CARDINAL; deque: Deques; VAR Ok: BOOLEAN);
(* Place contents from nth node of the deque into data.  Ok is set to *)
(* FALSE upon the following conditions:  deque is empty, size of data *)
(* does not equal size of contents.  nthItem is greater than number   *)
(* of nodes in the deque.                                             *)

END PMPDeque.


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


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

IMPLEMENTATION MODULE PMPDeque;

(*------------- Procedures from JPI's TopSpeed Modula II -------------*)
FROM AsmLib   IMPORT Compare, Move;
FROM SYSTEM   IMPORT ADDRESS, BYTE, TSIZE;
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;


(*--------------------------------------------------------------------*)
(*          Utility procedures used internally by PMPDeque.           *)
(*--------------------------------------------------------------------*)

PROCEDURE DeleteNode            (VAR node: Deques);
(* Deletes specified node from deque                                  *)

VAR
    nodeToDelete : Deques;             (* save pointer for deletion *)

BEGIN
    IF node^.next = node THEN          (* Delete last node in deque *)
       DEALLOCATE (node^.contents, node^.size);
       DEALLOCATE (node, TSIZE (DequeNodes));
       node := NIL;
    ELSE
       nodeToDelete := node;           (* Delete specified node     *)
       node := node^.next;
       nodeToDelete^.previous^.next := node;
       node^.previous := nodeToDelete^.previous;
       DEALLOCATE (nodeToDelete^.contents, nodeToDelete^.size);
       DEALLOCATE (nodeToDelete, TSIZE (DequeNodes));
    END;
END DeleteNode;

PROCEDURE InsertNodeAtEnd       (node: Deques; VAR deque: Deques);
(* Inserts specified node at end of deque                             *)

BEGIN
    IF Empty (deque) THEN              (* create front *)
       node^.next := node;
       node^.previous := node;
       deque := node;
    ELSE                               (* add to end   *)
       node^.next := deque;
       node^.previous := deque^.previous;
       deque^.previous^.next := node;
       deque^.previous := node;
    END;
END InsertNodeAtEnd;


(*--------------------------------------------------------------------*)
(*          Procedures exported by PMPDeque.                          *)
(*--------------------------------------------------------------------*)

PROCEDURE CreateDeque           (VAR deque: Deques);
(* Creates the deque by making it NIL                                 *)
(* This procedure must be called prior to performing operations on    *)
(* the deque.                                                         *)

BEGIN
    deque := NIL;
END CreateDeque;

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

BEGIN
    RETURN deque = NIL;
END Empty;

PROCEDURE DestroyDeque (VAR deque: Deques);
(* Destroys the deque by deallocating deque nodes and contents        *)
(* DestroyDeque should be called when the deque is no longer needed   *)
(* in memory.                                                         *)

BEGIN
    WHILE NOT Empty (deque) DO
          DeleteNode (deque);
    END;
END DestroyDeque;

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

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

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

VAR
    current : Deques;           (* cursor used to walk the deque *)
    count   : CARDINAL;         (* node counter *)

BEGIN
    count := 0;

    IF NOT Empty (deque) THEN
       current := deque^.previous;        (* start from back of deque *)

       REPEAT
             INC (count);
             current := current^.next;    (* and walk forward until   *)
       UNTIL current = deque^.previous;   (* we've reached the back   *)
    END;

    RETURN count;
END DequeLength;

PROCEDURE DequePos     (data: ARRAY OF BYTE; deque: Deques): CARDINAL;
(* Returns the number of the node containing the data (if found).     *)
(* Returns 0 if not found.  The front of the deque is treated as node *)
(* number one.                                                        *)

VAR
    count,                      (* node counter *)
    pos      : CARDINAL;        (* returned from AsmLib.Compare  *)
    current  : Deques;          (* cursor used to walk the deque *)

BEGIN
    count := 0;
    IF NOT Empty (deque) THEN
       current := deque^.previous;    (* start from the back of deque *)

       REPEAT
            INC (count);
            current := current^.next;
            pos := Compare (ADR (data), current^.contents, current^.size);
       UNTIL (current = deque^.previous) OR (pos = current^.size);
    END;

    IF pos = current^.size THEN        (* pos = size upon exact match *)
       RETURN count
    ELSE
       RETURN 0
    END;
END DequePos;

PROCEDURE InDeque      (data: ARRAY OF BYTE; deque: Deques): BOOLEAN;
(* Returns TRUE if data is found in deque.                            *)

BEGIN
    RETURN (DequePos (data, deque) # 0);
END InDeque;

PROCEDURE Enqueue      (data: ARRAY OF BYTE; VAR deque: Deques; VAR Ok: BOOLEAN);
(* Place data in node at the back of the deque.  Ok will be set to    *)
(* FALSE under the following conditions:  Deque is full.              *)

VAR
    newNode     : Deques;       (* used to create new node *)
    dataSize    : CARDINAL;     (* size of data *)

BEGIN
    dataSize := HIGH (data) + 1;
    Ok := NOT Full (dataSize);

    IF Ok THEN
       ALLOCATE (newNode, TSIZE (DequeNodes));
       ALLOCATE (newNode^.contents, dataSize);

       Move (ADR (data), newNode^.contents, dataSize);
       newNode^.size := dataSize;
       InsertNodeAtEnd (newNode, deque);
    END;
END Enqueue;

PROCEDURE Push         (data: ARRAY OF BYTE; VAR deque: Deques; VAR Ok: BOOLEAN);
(* Place data in node at the back of the deque.  Ok will be set to    *)
(* FALSE under the following conditions:  Deque is full.              *)

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

PROCEDURE Dequeue      (VAR data: ARRAY OF BYTE; VAR deque: Deques; VAR Ok: BOOLEAN);
(* Place contents from node at the front of the deque into data.      *)
(* Remove the front node of the deque.  Ok is set to FALSE upon the   *)
(* following conditions:  deque is empty, size of data does not equal *)
(* size of contents.                                                  *)

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 the size of contents *)

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

PROCEDURE Pop          (VAR data: ARRAY OF BYTE; VAR deque: Deques; VAR Ok: BOOLEAN);
(* Place contents from node at the back of the deque into data.       *)
(* Remove the back node of the deque.  Ok is set to FALSE upon the    *)
(* following conditions:  deque is empty, size of data does not equal *)
(* size of contents.                                                  *)

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

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

       IF deque^.next = deque THEN          (* only one node *)
          Ok := deque^.size = dataSize;

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

          IF Ok THEN
             Move (deque^.contents, ADR (data), deque^.size);
             DeleteNode (deque);
          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);
             DeleteNode (deque^.previous);
          END;
       END;
    END;
END Pop;

PROCEDURE Serve        (VAR data: ARRAY OF BYTE; nthItem: CARDINAL; VAR deque: Deques; VAR Ok: BOOLEAN);
(* Place contents from nth node of the deque into data.  Remove the   *)
(* nth node of the deque.  Ok is set to FALSE upon the following      *)
(* conditions:  deque is empty, size of data does not equal size of   *)
(* contents, nthItem is greater than number of nodes in the deque.    *)

VAR
    current        : Deques;    (* used to walk the deque *)
    dataSize,                   (* size of data *)
    numberOfNodes,              (* length of deque *)
    count          : CARDINAL;  (* node counter *)

BEGIN
    Ok := NOT Empty (deque);
    IF Ok THEN
       numberOfNodes := DequeLength (deque);

       Ok := (nthItem <= numberOfNodes) AND (nthItem > 0);

       (* nthItem must be less than length of deque & greater than 0 *)

       IF Ok THEN
          dataSize := HIGH (data) + 1;

          count := 0;
          current := deque^.previous;      (* start from back of deque *)

          REPEAT
                INC (count);               (* walk from back until we  *)
                current := current^.next;  (* have the nth Item        *)
          UNTIL count = nthItem;

          Ok := current^.size = dataSize;

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

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

             IF count = 1 THEN
                DeleteNode (deque)
             ELSE
                DeleteNode (current)
             END;
          END;
       END;
    END;
END Serve;

PROCEDURE Front        (VAR data: ARRAY OF BYTE; deque: Deques; VAR Ok: BOOLEAN);
(* Place contents from node at the front of the deque into data.      *)
(* Ok is set to FALSE upon the following conditions:  deque is empty, *)
(* size of data does not equal size of contents.                      *)

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 contents from node at the back of the deque into data.       *)
(* Ok is set to FALSE upon the following conditions:  deque is empty, *)
(* size of data does not equal size of contents.                      *)

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

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

       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 Back;

PROCEDURE Top          (VAR data: ARRAY OF BYTE; deque: Deques; VAR Ok: BOOLEAN);
(* Place contents from node at the back (top) of the deque into data. *)
(* Ok is set to FALSE upon the following conditions:  deque is empty, *)
(* size of data does not equal size of contents.                      *)

BEGIN
    Back (data, deque, Ok);
END Top;

PROCEDURE Retrieve     (VAR data: ARRAY OF BYTE; nthItem: CARDINAL; deque: Deques ; VAR Ok: BOOLEAN);
(* Place contents from nth node of the deque into data.  Ok is set to *)
(* FALSE upon the following conditions:  deque is empty, size of data *)
(* does not equal size of contents.  nthItem is greater than number   *)
(* of nodes in the deque.                                             *)

VAR
    current        : Deques;    (* used to walk the deque *)
    dataSize,                   (* size of data *)
    numberOfNodes,              (* length of deque *)
    count          : CARDINAL;  (* node counter *)

BEGIN
    Ok := NOT Empty (deque);
    IF Ok THEN
       numberOfNodes := DequeLength (deque);

       Ok := (nthItem <= numberOfNodes) AND (nthItem > 0);

       (* nthItem must be less than length of deque & greater than 0 *)

       IF Ok THEN
          dataSize := HIGH (data) + 1;

          count := 0;
          current := deque^.previous;      (* start from back of deque *)

          REPEAT
                INC (count);               (* walk from back until we  *)
                current := current^.next;  (* have the nth Item        *)
          UNTIL count = nthItem;

          Ok := current^.size = dataSize;

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

          IF Ok THEN
             Move (current^.contents, ADR (data), current^.size);
          END;
       END;
    END;
END Retrieve;

END PMPDeque.