Robert Smith committed c4eb54c

Make STACK, QUEUE, and ENQUEUE type safe.

Comments (0)

Files changed (1)

 (defstruct (stack (:constructor %make-stack)
                   (:predicate stackp))
-  elements)
+  (elements nil :type list))
 (defun make-stack ()
   "Create a new empty stack."
 (defstruct (queue (:constructor %make-queue)
                   (:predicate queuep))
-  elements
-  last)
+  (elements nil :type list)
+  (last nil :type (or null (cons t (member nil)))))
 (defun make-queue ()
   "Create a new empty queue."
 (defun list-to-queue (list)
   "Convert the list LIST into a queue. Note: LIST may be modified."
-  (make-queue :elements list
-              :last (last list)))
+  (%make-queue :elements list
+               :last (last list)))
 (defun enqueue (queue obj)
   "Add an element OBJ to the end of the queue QUEUE."
   (let ((last (list obj)))
     (if (queue-empty-p queue)
-        (setf (queue-last queue)     last
-              (queue-elements queue) last)
-        (setf (cdr (queue-last queue)) last
-              (queue-last queue)       last)))
+        ;; Set up the queue with the first element. Note that the same
+        ;; reference to the singleton list is shared by both
+        (setf (queue-elements queue) last
+              (queue-last queue)     last)
+        ;; We can now append elements to QUEUE-ELEMENTS simply by
+        ;; modifying QUEUE-LAST, whose reference is shared by
+        ;; QUEUE-ELEMENTS,
+        ;;
+        ;; We do this instead of a single SETF for type safety of
+        ;; QUEUE-LAST.
+        (let ((old (queue-last queue)))
+          (setf (queue-last queue) last
+                (cdr old)          last))))
 (defun dequeue (queue)
   "Remove and return an element from the queue QUEUE."
   (pop (queue-elements queue)))
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.