Name: Anonymous 2013-10-13 15:14
Rate my deque.
#lang racket
(define (make-deque)
(define (make-deque-cell content prev next)
(define (set-prev! cell)
(set! prev cell))
(define (set-next! cell)
(set! next cell))
(lambda (m)
(cond ((eq? m 'set-prev!) set-prev!)
((eq? m 'set-next!) set-next!)
((eq? m 'content) content)
((eq? m 'prev) prev)
((eq? m 'next) next)
(else (error "Undefined operation -- MAKE-DEQUE-CELL" m)))))
(define front-cell '())
(define rear-cell '())
(define (empty?)
(null? front-cell))
(define (get-front)
(if (empty?)
(error "Cannot get front of an empty deque.")
(front-cell 'content)))
(define (get-rear)
(if (empty?)
(error "Cannot get rear of an empty deque.")
(rear-cell 'content)))
(define (initialize-deque element)
(define new-cell (make-deque-cell element '() '()))
(set! front-cell new-cell)
(set! rear-cell new-cell))
(define (clear-deque)
(set! front-cell '())
(set! rear-cell '()))
(define (insert-front! element)
(if (empty?)
(initialize-deque element)
(let ((new-front (make-deque-cell element '() front-cell)))
((front-cell 'set-prev!) new-front)
(set! front-cell new-front))))
(define (insert-rear! element)
(if (empty?)
(initialize-deque element)
(let ((new-rear (make-deque-cell element rear-cell '())))
((rear-cell 'set-next!) new-rear)
(set! rear-cell new-rear))))
(define (delete-front!)
(if (empty?)
(error "Cannot delete from an empty deque.")
(let ((new-front (front-cell 'next)))
(cond ((null? new-front) (clear-deque))
(else (set! front-cell new-front)
((front-cell 'set-prev!) '()))))))
(define (delete-rear!)
(if (empty?)
(error "Cannot delete from an empty deque.")
(let ((new-rear (rear-cell 'prev)))
(cond ((null? new-rear) (clear-deque))
(else (set! rear-cell new-rear)
((rear-cell 'set-next!) '()))))))
(lambda (m)
(cond
((eq? m 'front) (get-front))
((eq? m 'rear) (get-rear))
((eq? m 'insert-front!) insert-front!)
((eq? m 'insert-rear!) insert-rear!)
((eq? m 'delete-front!) (delete-front!))
((eq? m 'delete-rear!) (delete-rear!))
((eq? m 'empty?) (empty?))
(else (error "Undefined operation -- MAKE-DEQUE" m)))))