source: project/release/5/yasos/trunk/queues.scm @ 36339

Last change on this file since 36339 was 36339, checked in by iraikov, 4 months ago

yasos: rename yasos based data structure models to yasos-<name> to avoid collisions with other eggs

File size: 1.6 KB
Line 
1                 
2;;; queues with amortized constant-time access to data
3(module yasos-queues   
4        (make-queue queue? empty? protocol size state front clear! deq! enq!)
5       
6(import scheme (chicken base) (chicken format)
7        (except yasos object object-with-ancestors))
8                 
9;; interface     
10(define-predicate queue?)
11(define-operation (empty? obj))
12(define-operation (clear! obj))
13(define-operation (front obj))
14(define-operation (deq! obj))
15(define-operation (enq! obj x))
16(define-operation (state obj))
17                 
18;; implementation
19(define (make-queue)
20  (let ((in '()) (out '()))
21    (operations ()
22      ((queue? self) #t)
23      ((empty? self) (and (null? in) (null? out)))
24      ((size self) (+ (length in) (length out)))
25      ((show self . optional-arg)
26       (if (null? optional-arg)
27         (show self #t)
28         (format (car optional-arg)
29                 "#,~s~%"
30                 (cons 'queue (append out (reverse in))))))
31      ((state self) ; for inheritance
32       (lambda () (vector in out)))
33      ((front self)
34       (if (and (null? in) (null? out))
35         (error 'front "queue empty")
36         (begin
37           (when (null? out)
38             (set! out (reverse in))
39             (set! in '()))
40           (car out))))
41      ((enq! self x) (set! in (cons x in)))
42      ((deq! self)
43       (if (and (null? in) (null? out))
44         (error 'deq! "queue empty")
45         (begin
46           (when (null? out)
47             (set! out (reverse in))
48             (set! in '()))
49           (set! out (cdr out)))))
50      ((clear! self) (set! in '()) (set! out '())))))
51
52) ; module queues
Note: See TracBrowser for help on using the repository browser.