home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD1.mdf / modula2 / library / queuem2 / deq1.txt next >
Text File  |  1989-12-15  |  14KB  |  387 lines
  1. (*====================================================================*)
  2. (*                  Peter M. Perchansky                               *)
  3. (*              412-1 Springside, Drive East                          *)
  4. (*                 Shillington, PA  19607                             *)
  5. (*                                                                    *)
  6. (*             CompuServe 71301,344                                   *)
  7. (*             FidoNet    1:273/101                                   *)
  8. (*             Interlink                                              *)
  9. (*====================================================================*)
  10.  
  11. The following is my implentation of a generic deque using JPI's TopSpeed
  12. Modula-2 (version 1.17).  A deque is a form of double-ended queue (or
  13. stack depending on your point of view).  The deque abstract data type
  14. allows you to do both queue and stack operations.
  15.  
  16. The queue operations are based on the following:  The front of the queue
  17. is the root node.  Enqueueing data will place the node at the rear of
  18. the queue.  Dequeueing (serving) data will remove the node from the
  19. front of the queue.
  20.  
  21. The stack operations are based on the following:  The top of the stack
  22. is the end node.  Pushing data will place the node at the rear (top) of
  23. the stack.  Popping data will remove data from the rear (top) of the
  24. stack.
  25.  
  26. Most procedures set a boolean value (Ok) to FALSE upon hitting an error
  27. condition.  You are responsible for handling these errors in the calling
  28. module.  Errors that can occur are as follows:  Enqueue or Push was
  29. performed on a full deque; Dequeue, Pop, Front, or Back was performed on
  30. an empty deque; the contents being retrieved in Dequeue, Pop, Front, or
  31. Back did not match the size of the VARed variable holder.
  32.  
  33. This library module is generic.  Any data type (both standard and
  34. user-defined) can be operated on in the deque.  You can even mix and
  35. match data types witin the deque; however, you are responsible for
  36. keeping track of what types are in the deque.
  37.  
  38. Future versions of this module will include procedures to compare
  39. deques, append one deque to another deque, search for elements within
  40. the deque, etc.
  41.  
  42. Please feel free to contact me via postal mail, CompuServe, FidoNet, or
  43. Interlink (language or Pascal Conference <they are working on adding a
  44. Modula-2 Conference>) if you have any questions or comments.
  45.  
  46. <-------------------------- cut here --------------------------------->
  47.  
  48. (*====================================================================
  49.   =  Program Id:     PMPDEQUE                                        =
  50.   =  Programmer:     Peter M. Perchansky                             =
  51.   =  Purpose:        Export procedures for dealing with circular     =
  52.   =                  deques.                                         =
  53.   =  Date Written:   10-29-89                                        =
  54.   ====================================================================*)
  55.  
  56. DEFINITION MODULE PMPDeque;
  57.  
  58. FROM SYSTEM IMPORT BYTE;
  59.  
  60. TYPE
  61.     Deques;            (* opaque type *)
  62.  
  63. PROCEDURE Empty        (deque : Deques) : BOOLEAN;
  64. (* Return TRUE if the deque is NIL *)
  65.  
  66. PROCEDURE Full         (size : CARDINAL) : BOOLEAN;
  67. (* Return TRUE if there is no Available memory for another deque node *)
  68.  
  69. PROCEDURE CreateDeque  (VAR deque : Deques);
  70. (* Creates the deque by making it NIL *)
  71.  
  72. PROCEDURE DestroyDeque (VAR deque : Deques);
  73. (* Destroys the deque by deallocating deque nodes *)
  74.  
  75. PROCEDURE DequeLength (deque : Deques) : CARDINAL;
  76. (* Returns the number of nodes in the deque *)
  77.  
  78. PROCEDURE Enqueue      (data : ARRAY OF BYTE; VAR deque : Deques; VAR Ok : BOOLEAN);
  79. (* Place data in node at back of deque.  Ok is set FALSE upon error *)
  80.  
  81. PROCEDURE Push         (data : ARRAY OF BYTE; VAR deque : Deques; VAR Ok : BOOLEAN);
  82. (* Place data in node bat back of deque.  Ok is set FALSE upon error *)
  83.  
  84. PROCEDURE Dequeue      (VAR data : ARRAY OF BYTE; VAR deque : Deques; VAR Ok : BOOLEAN);
  85. (* Place data from front of deque.  Remove front of deque.  Ok is set *)
  86. (* to FALSE upon error                                                *)
  87.  
  88. PROCEDURE Pop          (VAR data : ARRAY OF BYTE; VAR deque : Deques; VAR Ok : BOOLEAN);
  89. (* Place data from back of deque.  Remove back of deque.  Ok is set   *)
  90. (* to FALSE upon error                                                *)
  91.  
  92. PROCEDURE Front        (VAR data : ARRAY OF BYTE; deque : Deques; VAR Ok : BOOLEAN);
  93. (* Place data fron front of deque.  Ok is set FALSE upon error *)
  94.  
  95. PROCEDURE Back         (VAR data : ARRAY OF BYTE; deque : Deques; VAR Ok : BOOLEAN);
  96. (* Place data from back of deque.  Ok is set FALSE upon error *)
  97.  
  98. END PMPDeque.
  99.  
  100. <-------------------------- cut here --------------------------------->
  101.  
  102. (*====================================================================
  103.   =  Program Id:     PMPDEQUE                                        =
  104.   =  Programmer:     Peter M. Perchansky                             =
  105.   =  Purpose:        Export procedures for dealing with circular     =
  106.   =                  deques.                                         =
  107.   =  Date Written:   10-29-89                                        =
  108.   ====================================================================*)
  109.  
  110. IMPLEMENTATION MODULE PMPDeque;
  111.  
  112. (*============= Procedures from JPI's TopSpeed Modula II =============*)
  113. FROM Lib      IMPORT Move;
  114. FROM SYSTEM   IMPORT ADDRESS, BYTE, SIZE;
  115. FROM Storage  IMPORT ALLOCATE, Available, DEALLOCATE;
  116.  
  117. TYPE
  118.     Deques        = POINTER TO DequeNodes;  (* opaque type defined *)
  119.  
  120.     DequeNodes    = RECORD                  (* node *)
  121.                       contents : ADDRESS;   (* contents of node *)
  122.                       size     : CARDINAL;  (* size of contents *)
  123.                       next     : Deques;    (* pointer to next node *)
  124.                       previous : Deques;    (* pointer to prev node *)
  125.                     END;
  126.  
  127. PROCEDURE Empty        (deque : Deques) : BOOLEAN;
  128. (* Return TRUE if the deque is NIL *)
  129.  
  130. BEGIN
  131.     RETURN deque = NIL;
  132. END Empty;
  133.  
  134. PROCEDURE Full         (size : CARDINAL) : BOOLEAN;
  135. (* Return TRUE if there is no Available memory for another deque node *)
  136.  
  137. BEGIN
  138.     RETURN (NOT (Available (SIZE (DequeNodes)) AND Available (size)));
  139. END Full;
  140.  
  141. PROCEDURE CreateDeque  (VAR deque : Deques);
  142. (* Creates the deque by making it NIL *)
  143.  
  144. BEGIN
  145.     deque := NIL;
  146. END CreateDeque;
  147.  
  148. PROCEDURE DestroyDeque (VAR deque : Deques);
  149. (* Destroys the deque by deallocating deque nodes *)
  150.  
  151. VAR
  152.     temp    : Deques;
  153.  
  154. BEGIN
  155.     WHILE NOT Empty (deque) DO
  156.           (* if at the front of the deque, then remove the front *)
  157.           (* and make the deque empty                            *)
  158.  
  159.           IF deque^.next = deque THEN
  160.              DEALLOCATE (deque^.contents, deque^.size);
  161.              DEALLOCATE (deque, SIZE (DequeNodes));
  162.              deque := NIL;
  163.           ELSE
  164.  
  165.           (* otherwise continue removing the front of the deque  *)
  166.           (* until deque^.next = deque                           *)
  167.  
  168.              temp := deque;
  169.              deque := deque^.next;
  170.              temp^.previous^.next := deque;
  171.              deque^.previous := temp^.previous;
  172.              DEALLOCATE (temp^.contents, temp^.size);
  173.              DEALLOCATE (temp, SIZE (DequeNodes));
  174.           END;
  175.     END;
  176. END DestroyDeque;
  177.  
  178. PROCEDURE DequeLength (deque : Deques) : CARDINAL;
  179. (* Returns the number of nodes in the deque *)
  180.  
  181. VAR
  182.     current : Deques;
  183.     count   : CARDINAL;
  184.  
  185. BEGIN
  186.     IF NOT Empty (deque) THEN
  187.  
  188.        IF deque^.next = deque THEN          (* only front exists *)
  189.           count := 1;
  190.        ELSE
  191.           count := 1;                       (* count front *)
  192.           current := deque^.next;
  193.  
  194.           WHILE current # deque DO          (* walk from 2nd until front *)
  195.                 INC (count);
  196.                 current := current^.next;
  197.           END;
  198.        END;
  199.     ELSE
  200.        count := 0;
  201.     END;
  202.  
  203.     RETURN count;
  204. END DequeLength;
  205.  
  206. PROCEDURE Enqueue      (data : ARRAY OF BYTE; VAR deque : Deques; VAR Ok : BOOLEAN);
  207. (* Place data in node at back of deque.  Ok is set FALSE upon error *)
  208.  
  209. VAR
  210.     temp        : Deques;
  211.     dataSize    : CARDINAL;     (* size of data *)
  212.  
  213. BEGIN
  214.     dataSize := HIGH (data) + 1;
  215.     Ok := NOT Full (dataSize);
  216.     IF Ok THEN
  217.        ALLOCATE (temp, SIZE (DequeNodes));
  218.        ALLOCATE (temp^.contents, dataSize);
  219.        Move (ADR (data), temp^.contents, dataSize);
  220.        temp^.size := dataSize;
  221.  
  222.        IF deque = NIL THEN          (* create front *)
  223.           temp^.next := temp;
  224.           temp^.previous := temp;
  225.           deque := temp;
  226.        ELSE                         (* add to end   *)
  227.           temp^.next := deque;
  228.           temp^.previous := deque^.previous;
  229.           deque^.previous^.next := temp;
  230.           deque^.previous := temp;
  231.        END;
  232.     END;
  233. END Enqueue;
  234.  
  235. PROCEDURE Push         (data : ARRAY OF BYTE; VAR deque : Deques; VAR Ok : BOOLEAN);
  236. (* Place data in node bat back of deque.  Ok is set FALSE upon error *)
  237.  
  238. BEGIN
  239.     Enqueue (data, deque, Ok);
  240. END Push;
  241.  
  242. PROCEDURE Dequeue      (VAR data : ARRAY OF BYTE; VAR deque : Deques; VAR Ok : BOOLEAN);
  243. (* Place data from front of deque.  Remove front of deque.  Ok is set *)
  244. (* to FALSE upon error                                                *)
  245.  
  246. VAR
  247.     temp        : Deques;
  248.     dataSize    : CARDINAL;     (* size of data *)
  249.  
  250. BEGIN
  251.     Ok := NOT Empty (deque);
  252.     IF Ok THEN
  253.        dataSize := HIGH (data) + 1;
  254.  
  255.        Ok := deque^.size = dataSize;
  256.  
  257.        (* size of data must equal the size of contents *)
  258.  
  259.        IF Ok THEN
  260.           Move (deque^.contents, ADR (data), deque^.size);
  261.  
  262.           (* if at front of the deque, then remove the front *)
  263.           (* and set the deque to NIL                        *)
  264.  
  265.           IF deque^.next = deque THEN
  266.              DEALLOCATE (deque^.contents, deque^.size);
  267.              DEALLOCATE (deque, SIZE (DequeNodes));
  268.              deque := NIL;
  269.           ELSE
  270.  
  271.           (* otherwise remove the front of the queue, and    *)
  272.           (* make the second node the front                  *)
  273.  
  274.              temp := deque;
  275.              deque := deque^.next;
  276.              temp^.previous^.next := deque;
  277.              deque^.previous := temp^.previous;
  278.              DEALLOCATE (temp^.contents, temp^.size);
  279.              DEALLOCATE (temp, SIZE (DequeNodes));
  280.           END;
  281.        END;
  282.     END;
  283. END Dequeue;
  284.  
  285. PROCEDURE Pop          (VAR data : ARRAY OF BYTE; VAR deque : Deques; VAR Ok : BOOLEAN);
  286. (* Place data from back of deque.  Remove back of deque.  Ok is set   *)
  287. (* to FALSE upon error                                                *)
  288.  
  289. VAR
  290.   temp       : Deques;
  291.   dataSize   : CARDINAL;        (* size of data *)
  292.  
  293. BEGIN
  294.     Ok := NOT Empty (deque);
  295.     IF Ok THEN
  296.        dataSize := HIGH (data) + 1;
  297.  
  298.        (* if at front of the deque, then remove the front *)
  299.        (* and set the deque to NIL                        *)
  300.  
  301.        IF deque^.next = deque THEN
  302.  
  303.           Ok := deque^.size = dataSize;
  304.  
  305.           (* size of data must equal size of contents *)
  306.  
  307.           IF Ok THEN
  308.              Move (deque^.contents, ADR (data), deque^.size);
  309.              DEALLOCATE (deque^.contents, deque^.size);
  310.              DEALLOCATE (deque, SIZE (DequeNodes));
  311.              deque := NIL;
  312.           END;
  313.        ELSE
  314.  
  315.        (* otherwise remove the back of the queue *)
  316.  
  317.           Ok := deque^.previous^.size = dataSize;
  318.  
  319.           (* size of data must equal size of contents *)
  320.  
  321.           IF Ok THEN
  322.              Move (deque^.previous^.contents, ADR (data), deque^.previous^.size);
  323.              temp := deque^.previous;
  324.              deque^.previous^.previous^.next := deque;
  325.              deque^.previous := temp^.previous;
  326.              temp^.next := NIL;
  327.              temp^.previous := NIL;
  328.              DEALLOCATE (temp^.contents, temp^.size);
  329.              DEALLOCATE (temp, SIZE (DequeNodes));
  330.           END;
  331.        END;
  332.     END;
  333. END Pop;
  334.  
  335. PROCEDURE Front        (VAR data : ARRAY OF BYTE; deque : Deques; VAR Ok : BOOLEAN);
  336. (* Place data fron front of deque.  Ok is set FALSE upon error *)
  337.  
  338. VAR
  339.     dataSize : CARDINAL;        (* size of data *)
  340.  
  341. BEGIN
  342.     Ok := NOT Empty (deque);
  343.     IF Ok THEN
  344.        dataSize := HIGH (data) + 1;
  345.        Ok := deque^.size = dataSize;
  346.  
  347.        (* size of data must equal size of contents *)
  348.  
  349.        IF Ok THEN
  350.           Move (deque^.contents, ADR (data), deque^.size);
  351.        END;
  352.     END;
  353. END Front;
  354.  
  355. PROCEDURE Back         (VAR data : ARRAY OF BYTE; deque : Deques; VAR Ok : BOOLEAN);
  356. (* Place data from back of deque.  Ok is set FALSE upon error *)
  357.  
  358. VAR
  359.     dataSize : CARDINAL;        (* size of data *)
  360.  
  361. BEGIN
  362.     Ok := NOT Empty (deque);
  363.     IF Ok THEN
  364.        dataSize := HIGH (data) + 1;
  365.  
  366.        IF deque^.next = deque THEN
  367.           Ok := deque^.size = dataSize;
  368.  
  369.           (* size of data must equal size of contents *)
  370.  
  371.           IF Ok THEN
  372.              Move (deque^.contents, ADR (data), deque^.size);
  373.           END;
  374.        ELSE
  375.           Ok := deque^.previous^.size = dataSize;
  376.  
  377.           (* size of data must equal size of contents *)
  378.  
  379.           IF Ok THEN
  380.              Move (deque^.previous^.contents, ADR (data), deque^.previous^.size);
  381.           END;
  382.        END;
  383.     END;
  384. END Back;
  385.  
  386. END PMPDeque.