deque

1 files changed, 57 insertions, 0 deletions

diff --git a/coding-exercises/3/21.rkt b/coding-exercises/3/21.rkt
index 646a8f7..f81c2a6 100644
--- a/coding-exercises/3/21.rkt
+++ b/coding-exercises/3/21.rkt
@@ -81,3 +81,60 @@
 ((qobj 'delete-queue!))
 (qobj 'print-queue)
 ;; 23
+(define (make-deque) (mcons '() '()))
+;; internal
+(define (front-ptr-deque q) (mcar q))
+(define (rear-ptr-deque q) (mcdr q))
+(define (empty-deque? q) (and (null? (front-ptr-deque q)) (null? (rear-ptr-deque q))))
+;; selectors
+(define (front-deque q) (mcar (mcar (front-ptr-deque q))))
+(define (rear-deque q) (mcar (mcar (rear-ptr-deque q))))
+;; mutators
+(define (front-insert-deque! q data)
+  (let ((item (mlist (mlist data))))
+    (cond ((empty-deque? q) (set-mcar! q item) (set-mcdr! q item) q)
+          (else (set-mcdr! (mcar (front-ptr-deque q)) item)
+                (set-mcdr! item (front-ptr-deque q))
+                (set-mcar! q item)
+                q))))
+(define (rear-insert-deque! q data)
+  (let ((item (mlist (mlist data))))
+    (cond ((empty-deque? q) (set-mcar! q item) (set-mcdr! q item) q)
+          (else (set-mcdr! (mcar item) (rear-ptr-deque q))
+                (set-mcdr! (rear-ptr-deque q) item)
+                (set-mcdr! q item)
+                q))))
+(define (rear-delete-deque! q)
+    (cond ((empty-deque? q) (error "DELETE-REAR deque, tried calling delete on empty deque."))
+          (else (let ((prev-ptr (mcdr (mcar (rear-ptr-deque q))))
+                      (item (mcar (mcar (rear-ptr-deque q)))))
+                  (set-mcdr! q prev-ptr)
+                  (if (null? prev-ptr)
+                    (set-mcar! q prev-ptr)
+                    (set-mcdr! (rear-ptr-deque q) '()))
+                  item))))
+(define (front-delete-deque! q)
+    (cond ((empty-deque? q) (error "DELETE-FRONT deque, tried calling delete on empty deque."))
+          (else (let ((next-ptr (mcdr (front-ptr-deque q)))
+                      (item (mcar (mcar (front-ptr-deque q)))))
+                  (set-mcar! q next-ptr)
+                  (if (null? next-ptr)
+                    (set-mcdr! q next-ptr)
+                    (set-mcdr! (mcar (front-ptr-deque q)) '()))
+                  item))))
+(define (print-deque q)
+  (define (rec fn items)
+    (cond ((null? items) '())
+          (else (cons (fn (mcar items)) (rec fn (mcdr items))))))
+  (display (rec (lambda (item)
+                  (mcar item))
+                (front-ptr-deque q))))
+(define dq1 (make-deque))
+(rear-insert-deque! dq1 'a)
+(rear-insert-deque! dq1 'b)
+(rear-insert-deque! dq1 'c)
+(print-deque dq1)
+(rear-delete-deque! dq1)
+(front-delete-deque! dq1)
+(rear-delete-deque! dq1)
+(print-deque dq1)