A circular array-based implementation of a rolling window.

circular-window.rkt

#lang racket/base

;; A circular array to let us efficiently walk a window across a sequence.

(struct window (elts      ;; (vectorof X) of length n
                capacity  ;; natural
                start     ;; natural
                count     ;; natural
                )
  #:mutable)

;; new-window: natural -> (windowof x)
(define (new-window k)
  (window (make-vector k) k 0 0))


;; window-empty?: (windowof x) -> boolean
(define (window-empty? w)
  (= (window-count w)
     0))


;; window-full?: (windowof x) -> boolean
(define (window-full? w)
  (= (window-count w)
     (window-capacity w)))



;; window-ref: (windowof x) natural -> 
(define (window-ref w i)
  (unless (< i (window-count w))
    (error 'window-ref "out of range"))
  (vector-ref (window-elts w)
              (modulo (+ (window-start w) i)
                      (window-capacity w))))


;; window-add-end!: (windowof x) x -> void
(define (window-add-end! w v)
  (when (window-full? w)
    (error 'window-add-end! "full"))
  (vector-set! (window-elts w)
               (modulo (+ (window-start w) (window-count w))
                       (window-capacity w))
               v)
  (set-window-count! w (add1 (window-count w))))


;; window-remove-front!: (windowof x) -> x
(define (window-remove-front! w)
  (when (window-empty? w)
    (error 'window-remove-front! "empty"))
  (define v (vector-ref (window-elts w)
                        (window-start w)))
  (set-window-start! w (modulo (add1 (window-start w))
                               (window-capacity w)))
  (set-window-count! w (sub1 (window-count w)))
  v)



(module+ test
  (require rackunit
           racket/block)
  (block
   (define w (new-window 3))
   (check-true (window-empty? w))
   (check-false (window-full? w))
   (window-add-end! w 'x)
   (check-false (window-empty? w))
   (check-false (window-full? w))
   (window-add-end! w 'y)
   (check-false (window-empty? w))
   (check-false (window-full? w))
   
   (check-equal? (window-remove-front! w) 'x)
   
   (window-add-end! w 'z)
   (window-add-end! w 'last)
   (check-false (window-empty? w))
   (check-true (window-full? w))
   
   (check-equal? (window-ref w 0) 'y)
   (check-equal? (window-ref w 1) 'z)
   (check-equal? (window-ref w 2) 'last)
   
   (check-equal? (window-remove-front! w) 'y)
   
   (check-false (window-empty? w))
   (check-false (window-full? w))

   (check-equal? (window-remove-front! w) 'z)

   (check-false (window-empty? w))
   (check-false (window-full? w))
   
   (check-equal? (window-remove-front! w) 'last)
   
   (check-true (window-empty? w))
   (check-false (window-full? w))))