Description
In this laboratory assignment, you will write OCaml functions that perform operations on mutable queues. The queues will be implemented as circular doubly-linked lists with head nodes—sometimes called symmetric lists. Queues and symmetric lists are often discussed in a data structures course, like the one that is a prerequisite for CSCI 2041. This assignment assumes that you are familiar with such lists.
1. Theory.
We’ll start with some terminology. A singly-linked list is built from zero or more nodes, each of which has a pointer to the node that follows it. A doubly-linked list is also built from zero or more nodes, but now each node has a pointer both to the node that precedes it, and to the node that follows it. A circular doubly-linked list is a doubly linked list of zero or more nodes, whose last node (if any) points to its first node, and vice versa. A circular doubly-linked list with a head node is a circular-doubly linked list of one or more nodes. Within the list, the head node eliminates special cases when adding nodes to the list, or when deleting nodes from the list.
For example, the following diagram shows a circular doubly-linked list with a head node (pointed to by the variable head). Each node has a left pointer, a data object called an element (shown as an upper case letter), and a right pointer.
Note that the head node is always present, even in an empty list. If the list is empty, then the left and right pointers of the head node point back to the head node itself.
A queue is a finite, ordered series of elements, in which all additions occur at one end, called the rear of the queue, and all deletions occur at the opposite end, called the front of the queue. For example, a line of people waiting to enter a theater is a queue, because people join the line at the rear, and leave the line at the front.
A circular doubly-linked list with a head node can implement a queue. The rear of the queue is the node on the left of the head node (with element E in the diagram). When we add a new element to the queue, we add the node containing the element on the left of the head node. Similarly, the front of the queue is the node on the right of the head node (with element A in the diagram). When we delete an old element from the queue, we delete the node containing the element on the right of the head node.
If we implement a queue in this way, then we need not make special case tests to determine if the queue is empty. This is because the queue is never empty—the head node is always present!
2. Implementation.
For this laboratory assignment, you must implement your queue as a circular doubly-linked list with a head node. Each node in the list has the type 'base mutyQueue, which is defined as follows.
type 'base mutyQueue =
MutyQueueNode
of 'base ∗
'base mutyQueue ref ∗
'base mutyQueue ref ;;
Each node has three parts: an immutable element of type 'base, a variable left pointer, whose value has the type 'base mutyQueue, and a right pointer, whose value also has the 'base mutyQueue.
Note that OCaml uses the name ref in two different ways. The expression ref v returns a new variable whose value is v. For example, ref 17 returns a variable whose value is the int 17. However, t ref is the type of a variable whose values have the type t. For example, int ref is the type of a variable whose values have the type int. Do not confuse the two uses of the name ref!
You must write the following functions. They perform operations on the circular doubly linked lists that implement queues.
- mutyQueueMake s
Return the head node of a new queue, whose element is s, and whose left and right pointers point back to the head node itself. The element s will be returned if you try to dequeue an element from the queue when it is empty. The queue has type t mutyQueue, where t is the type of s.
- mutyQueueEmpty q
Test if the queue with head node q is empty. Return true if it is, and return false if it is not. Do not change q in any way!
- mutyQueueEnqueue q e
Add a node to the left of the head node q. This node contains the element e. Return ().
- mutyQueueDequeue q
If q is empty, then return s from mutyQueueMake above. Otherwise, get the node on the right of the head node q. It contains the element e. Delete that node and return e.
Here are some hints.
-
All your functions must run in O(1) time, without loops or recursions.
-
Most objects in OCaml are accessed through pointers, although the language doesn’t make that explicit. Some other languages, such as Python, treat objects that way too.
-
Queues are represented by pointers to their head nodes. Whenever you see q in the above descriptions, it means a pointer to the head node of a circular doubly-linked list.
-
The function mutyQueueMake must make a head node, whose left and right pointers point back to the head node itself. Such a node can be made easily using let rec, like this. Code to initialize the head node’s element goes in place of ‘‘...’’.
let rec h = MutyQueueNode (..., ref h, ref h)
in hDo not make a node and then assign values to its left and right pointers, as you would in an imperative programming language—that will not work in OCaml!
-
Use match–with to access the elements, left pointers, and right pointers of nodes. Note that the left and right pointers are variables—they are not the values of variables! If v is a variable, then ! v returns v’s value, and ref x returns a variable whose value is x. Also, ref ! v makes a new variable with the same value as v.
-
The function mutyQueueEmpty must test if the left and right pointers of the head node point back to the head node. To make this test, use the OCaml operator ‘==’. It tests if two pointers point to the same object. Do not use ‘=’, because it may try to traverse your circular lists and run out of stack space.
-
When mutyQueueEnqueue adds a new node from a queue, then the queue must still be circular after the node is added. When mutyQueueDequeue removes an old node from a queue, then the queue must still be circular after the node is removed. Never delete the queue’s head node!
-
If you write mutyQueueDequeue correctly, then you will not need a special case check for an empty queue. The same code that deletes a node from a non-empty list will leave an empty list (with just a head node) unchanged, and will return the element in the head node.
3. Deliverables.
The file tests7.ml contains a definition of the type 'base mutyQueueNode as discussed above. It also contains some tests, worth 35 points. Insert your code into this file, then run it with OCaml. When you think your code is correct, then submit your file to Canvas. If you do not know how to submit your work, then please ask your lab TA’s. It must be submitted by 11:55 PM on Tuesday, November 2, 2021.
