2 Deques
Double ended queues (or deque) are queues where elements can be added or removed from either end. The deque data structures provided by this library implement and provide the following operations: deque, empty?, enqueue, enqueue-front, head, tail, last, init and deque->list.
2.1 Bankers Deque
(require pfds/deque/bankers) | package: pfds |
Bankers deques are amortized double ended deques developed using the Bankers method. They provide an amortized running time of O(1) for the operations head, tail, last, init, enqueue-front and enqueue. They use lazy evaluation and memoization to achieve the amortized running time.
syntax
(Deque A)
> (deque 1 2 3 4 5 6)
- : #(struct:Deque
((Rec
g298411
(U (Pairof Positive-Byte g298411) (Promiseof g298411) Null))
Integer
(Rec
g298413
(U (Pairof Positive-Byte g298413) (Promiseof g298413) Null))
Integer))
#<Deque>
In the above example, the deque obtained will have 1 as its head element.
procedure
(enqueue-front a deq) → (Deque A)
a : A deq : (Deque A)
> (enqueue-front 10 (deque 5 6 3 4))
- : #(struct:Deque
((Rec
g298504
(U (Pairof Positive-Byte g298504) (Promiseof g298504) Null))
Integer
(Rec
g298506
(U (Pairof Positive-Byte g298506) (Promiseof g298506) Null))
Integer))
#<Deque>
In the above example, (enqueue-front 10 (deque 5 6 3 4)) adds 10 to the front of the (deque 5 6 3 4). 10 will be the head element.
In the above example, (head (empty Integer)) throws an error since the given deque is empty.
In the above example, (last (empty Integer))throws an error since the given deque is empty.
In the above example, (tail (deque 1 2 3 4 5 6)), removes the head of the given deque returns (deque 2 3 4 5 6).
In the above example, (init (deque 1 2 3 4 5 6)), removes the last element 6 and returns (deque 1 2 3 4 5).
procedure
(deque->list deq) → (Listof A)
deq : (Deque A)
> (deque->list (deque 10 2 34 4 15 6)) - : (Listof Positive-Byte)
'(10 2 34 4 15 6)
> (deque->list (empty Integer)) - : (Listof Integer)
'()
> (deque->list (map add1 (deque 1 2 3 4 5 6))) - : (Listof Positive-Index)
'(2 3 4 5 6 7)
> (deque->list (map * (deque 1 2 3 4 5 6) (deque 1 2 3 4 5 6))) - : (Listof Positive-Index)
'(1 4 9 16 25 36)
procedure
(foldl func init deq1 deq2 ...) → C
func : (C A B ... B -> C) init : C deq1 : (Deque A) deq2 : (Deque B)
foldl currently does not produce correct results when the given function is non-commutative.
> (foldl + 0 (deque 1 2 3 4 5 6)) - : Integer [more precisely: Nonnegative-Integer]
21
> (foldl * 1 (deque 1 2 3 4 5 6) (deque 1 2 3 4 5 6)) - : Integer [more precisely: Positive-Integer]
518400
procedure
(foldr func init deq1 deq2 ...) → C
func : (C A B ... B -> C) init : C deq1 : (Deque A) deq2 : (Deque B)
foldr currently does not produce correct results when the given function is non-commutative.
> (foldr + 0 (deque 1 2 3 4 5 6)) - : Integer [more precisely: Nonnegative-Integer]
21
> (foldr * 1 (deque 1 2 3 4 5 6) (deque 1 2 3 4 5 6)) - : Integer [more precisely: Positive-Integer]
518400
> (define que (deque 1 2 3 4 5 6)) > (deque->list (filter (λ: ([x : Integer]) (> x 5)) que)) - : (Listof Positive-Byte)
'(6)
> (deque->list (filter (λ: ([x : Integer]) (< x 5)) que)) - : (Listof Positive-Byte)
'(1 2 3 4)
> (deque->list (filter (λ: ([x : Integer]) (<= x 5)) que)) - : (Listof Positive-Byte)
'(1 2 3 4 5)
> (deque->list (remove (λ: ([x : Integer]) (> x 5)) (deque 1 2 3 4 5 6))) - : (Listof Positive-Byte)
'(1 2 3 4 5)
> (deque->list (remove (λ: ([x : Integer]) (< x 5)) (deque 1 2 3 4 5 6))) - : (Listof Positive-Byte)
'(5 6)
> (deque->list (remove (λ: ([x : Integer]) (<= x 5)) (deque 1 2 3 4 5 6))) - : (Listof Positive-Byte)
'(6)
procedure
(andmap func deq1 deq2 ...) → Boolean
func : (A B ... B -> Boolean) deq1 : (Deque A) deq2 : (Deque B)
> (andmap even? (deque 1 2 3 4 5 6)) - : Boolean
#f
> (andmap odd? (deque 1 2 3 4 5 6)) - : Boolean
#f
> (andmap positive? (deque 1 2 3 4 5 6)) - : Boolean
#t
> (andmap negative? (deque -1 -2)) - : Boolean
#t
procedure
(ormap func deq1 deq2 ...) → Boolean
func : (A B ... B -> Boolean) deq1 : (Deque A) deq2 : (Deque B)
> (ormap even? (deque 1 2 3 4 5 6)) - : Boolean
#t
> (ormap odd? (deque 1 2 3 4 5 6)) - : Boolean
#t
> (ormap positive? (deque -1 -2 3 4 -5 6)) - : Boolean
#t
> (ormap negative? (deque 1 -2)) - : Boolean
#t
procedure
(build-deque size func) → (Deque A)
size : Natural func : (Natural -> A)
> (deque->list (build-deque 5 (λ:([x : Integer]) (add1 x)))) - : (Listof Integer)
'(1 2 3 4 5)
> (deque->list (build-deque 5 (λ:([x : Integer]) (* x x)))) - : (Listof Integer)
'(0 1 4 9 16)
> (head+tail (deque 1 2 3 4 5))
- : (Pairof
Positive-Byte
#(struct:Deque
((Rec
g299315
(U (Pairof Positive-Byte g299315) (Promiseof g299315) Null))
Integer
(Rec
g299317
(U (Pairof Positive-Byte g299317) (Promiseof g299317) Null))
Integer)))
'(1 . #<Deque>)
> (head+tail (build-deque 5 (λ:([x : Integer]) (* x x))))
- : (Pairof
Integer
#(struct:Deque
((Rec g299341 (U (Pairof Integer g299341) (Promiseof g299341) Null))
Integer
(Rec g299343 (U (Pairof Integer g299343) (Promiseof g299343) Null))
Integer)))
'(0 . #<Deque>)
> (head+tail (empty Integer)) head+tail: given deque is empty
> (last+init (deque 1 2 3 4 5))
- : (Pairof
Positive-Byte
#(struct:Deque
((Rec
g299384
(U (Pairof Positive-Byte g299384) (Promiseof g299384) Null))
Integer
(Rec
g299386
(U (Pairof Positive-Byte g299386) (Promiseof g299386) Null))
Integer)))
'(5 . #<Deque>)
> (last+init (build-deque 5 (λ:([x : Integer]) (* x x))))
- : (Pairof
Integer
#(struct:Deque
((Rec g299410 (U (Pairof Integer g299410) (Promiseof g299410) Null))
Integer
(Rec g299412 (U (Pairof Integer g299412) (Promiseof g299412) Null))
Integer)))
'(16 . #<Deque>)
> (last+init (empty Integer)) last+init: given deque is empty
2.2 Implicit Deque
(require pfds/deque/implicit) | package: pfds |
Deques obtained by applying Implicit Recursive Slowdown. Provides amortized running time of O(1) for the operations head, tail, last, init, enqueue-front and enqueue. Implicit Recursive Slowdown combines laziness and technique called Recursive Slow-Down developed by Kaplan and Tarjan in their paper Persistant Lists with Catenation via Recursive Slow-Down.
syntax
(Deque A)
> (deque 1 2 3 4 5 6) - : (U (Deep Positive-Byte) (Shallow Positive-Byte))
#<Deep>
In the above example, the deque obtained will have 1 as its head element.
In the above example, enqueue adds the element 10 to (deque 1 2 3 4 5 6 10).
procedure
(enqueue-front a deq) → (Deque A)
a : A deq : (Deque A)
> (enqueue-front 10 (deque 5 6 3 4)) - : (U (Deep Positive-Byte) (Shallow Positive-Byte))
#<Deep>
In the above example, (enqueue-front 10 (deque 5 6 3 4)) adds 10 to the front of the (deque 5 6 3 4). 10 will be the head element.
In the above example, (tail (deque 1 2 3 4 5 6)), removes 1 and returns (tail (deque 2 3 4 5 6)).
In the above example, (init (deque 1 2 3 4 5 6)), removes the last element 6 and returns (deque 1 2 3 4 5)
procedure
(deque->list deq) → (Listof A)
deq : (Deque A)
> (deque->list (deque 10 2 34 4 15 6)) - : (Listof Positive-Byte)
'(10 2 34 4 15 6)
> (deque->list (map add1 (deque 1 2 3 4 5 6))) - : (Listof Positive-Index)
'(2 3 4 5 6 7)
> (deque->list (map * (deque 1 2 3 4 5 6) (deque 1 2 3 4 5 6))) - : (Listof Positive-Index)
'(1 4 9 16 25 36)
procedure
(foldl func init deq1 deq2 ...) → C
func : (C A B ... B -> C) init : C deq1 : (Deque A) deq2 : (Deque B)
foldl currently does not produce correct results when the given function is non-commutative.
> (foldl + 0 (deque 1 2 3 4 5 6)) - : Integer [more precisely: Nonnegative-Integer]
21
> (foldl * 1 (deque 1 2 3 4 5 6) (deque 1 2 3 4 5 6)) - : Integer [more precisely: Positive-Integer]
518400
procedure
(foldr func init deq1 deq2 ...) → C
func : (C A B ... B -> C) init : C deq1 : (Deque A) deq2 : (Deque B)
foldr currently does not produce correct results when the given function is non-commutative.
> (foldr + 0 (deque 1 2 3 4 5 6)) - : Integer [more precisely: Nonnegative-Integer]
21
> (foldr * 1 (deque 1 2 3 4 5 6) (deque 1 2 3 4 5 6)) - : Integer [more precisely: Positive-Integer]
518400
> (define que (deque 1 2 3 4 5 6)) > (deque->list (filter (λ: ([x : Integer]) (> x 5)) que)) - : (Listof Positive-Byte)
'(6)
> (deque->list (filter (λ: ([x : Integer]) (< x 5)) que)) - : (Listof Positive-Byte)
'(1 2 3 4)
> (deque->list (filter (λ: ([x : Integer]) (<= x 5)) que)) - : (Listof Positive-Byte)
'(1 2 3 4 5)
> (deque->list (remove (λ: ([x : Integer]) (> x 5)) (deque 1 2 3 4 5 6))) - : (Listof Positive-Byte)
'(1 2 3 4 5)
> (deque->list (remove (λ: ([x : Integer]) (< x 5)) (deque 1 2 3 4 5 6))) - : (Listof Positive-Byte)
'(5 6)
> (deque->list (remove (λ: ([x : Integer]) (<= x 5)) (deque 1 2 3 4 5 6))) - : (Listof Positive-Byte)
'(6)
procedure
(andmap func deq1 deq2 ...) → Boolean
func : (A B ... B -> Boolean) deq1 : (Deque A) deq2 : (Deque B)
> (andmap even? (deque 1 2 3 4 5 6)) - : Boolean
#f
> (andmap odd? (deque 1 2 3 4 5 6)) - : Boolean
#f
> (andmap positive? (deque 1 2 3 4 5 6)) - : Boolean
#t
> (andmap negative? (deque -1 -2)) - : Boolean
#t
procedure
(ormap func deq1 deq2 ...) → Boolean
func : (A B ... B -> Boolean) deq1 : (Deque A) deq2 : (Deque B)
> (ormap even? (deque 1 2 3 4 5 6)) - : Boolean
#t
> (ormap odd? (deque 1 2 3 4 5 6)) - : Boolean
#t
> (ormap positive? (deque -1 -2 3 4 -5 6)) - : Boolean
#t
> (ormap negative? (deque 1 -2)) - : Boolean
#t
procedure
(build-deque size func) → (Deque A)
size : Natural func : (Natural -> A)
> (deque->list (build-deque 5 (λ:([x : Integer]) (add1 x)))) - : (Listof Integer)
'(1 2 3 4 5)
> (deque->list (build-deque 5 (λ:([x : Integer]) (* x x)))) - : (Listof Integer)
'(0 1 4 9 16)
2.3 Real-Time Deque
(require pfds/deque/real-time) | package: pfds |
Real-Time Deques eliminate the amortization by using two techniques Scheduling and a variant of Global Rebuilding called Lazy Rebuilding. The data structure gives a worst case running time of O(1) for the operations head, tail, last, init, enqueue-front and enqueue.
syntax
(Deque A)
> (deque 1 2 3 4 5 6)
- : #(struct:Deque
((Rec
g303061
(U (Boxof (U (-> (Pairof Integer g303061)) (Pairof Integer g303061)))
Null))
Integer
(Rec
g303064
(U (Boxof (U (-> (Pairof Integer g303064)) (Pairof Integer g303064)))
Null))
(Rec
g303067
(U (Boxof (U (-> (Pairof Integer g303067)) (Pairof Integer g303067)))
Null))
Integer
(Rec
g303070
(U (Boxof (U (-> (Pairof Integer g303070)) (Pairof Integer g303070)))
Null))))
#<Deque>
In the above example, the deque obtained will have 1 as its head element.
> (enqueue 10 (deque 1 2 3 4 5 6))
- : #(struct:Deque
((Rec
g303102
(U (Boxof (U (-> (Pairof Integer g303102)) (Pairof Integer g303102)))
Null))
Integer
(Rec
g303105
(U (Boxof (U (-> (Pairof Integer g303105)) (Pairof Integer g303105)))
Null))
(Rec
g303108
(U (Boxof (U (-> (Pairof Integer g303108)) (Pairof Integer g303108)))
Null))
Integer
(Rec
g303111
(U (Boxof (U (-> (Pairof Integer g303111)) (Pairof Integer g303111)))
Null))))
#<Deque>
In the above example, enqueue adds the element 10 to the end of (deque 1 2 3 4 5 6).
procedure
(enqueue-front a deq) → (Deque A)
a : A deq : (Deque A)
> (enqueue-front 10 (deque 1 2 3 4 5 6))
- : #(struct:Deque
((Rec
g303123
(U (Boxof (U (-> (Pairof Integer g303123)) (Pairof Integer g303123)))
Null))
Integer
(Rec
g303126
(U (Boxof (U (-> (Pairof Integer g303126)) (Pairof Integer g303126)))
Null))
(Rec
g303129
(U (Boxof (U (-> (Pairof Integer g303129)) (Pairof Integer g303129)))
Null))
Integer
(Rec
g303132
(U (Boxof (U (-> (Pairof Integer g303132)) (Pairof Integer g303132)))
Null))))
#<Deque>
In the above example, enqueue adds the element 10 to the front of (deque 1 2 3 4 5 6) and returns (deque 10 1 2 3 4 5 6).
> (tail (deque 1 2 3 4 5 6))
- : #(struct:Deque
((Rec
g303182
(U (Boxof (U (-> (Pairof Integer g303182)) (Pairof Integer g303182)))
Null))
Integer
(Rec
g303185
(U (Boxof (U (-> (Pairof Integer g303185)) (Pairof Integer g303185)))
Null))
(Rec
g303188
(U (Boxof (U (-> (Pairof Integer g303188)) (Pairof Integer g303188)))
Null))
Integer
(Rec
g303191
(U (Boxof (U (-> (Pairof Integer g303191)) (Pairof Integer g303191)))
Null))))
#<Deque>
> (tail (empty Integer)) tail: given deque is empty
In the above example, (tail (deque 1 2 3 4 5 6)), removes the head of the given deque returns (deque 2 3 4 5 6).
> (init (deque 1 2 3 4 5 6))
- : #(struct:Deque
((Rec
g303225
(U (Boxof (U (-> (Pairof Integer g303225)) (Pairof Integer g303225)))
Null))
Integer
(Rec
g303228
(U (Boxof (U (-> (Pairof Integer g303228)) (Pairof Integer g303228)))
Null))
(Rec
g303231
(U (Boxof (U (-> (Pairof Integer g303231)) (Pairof Integer g303231)))
Null))
Integer
(Rec
g303234
(U (Boxof (U (-> (Pairof Integer g303234)) (Pairof Integer g303234)))
Null))))
#<Deque>
> (init (empty Integer)) init: given deque is empty
In the above example, (init (deque 1 2 3 4 5 6)), removes the last element 6 of the given deque and returns (deque 1 2 3 4 5).
procedure
(deque->list deq) → (Listof A)
deq : (Deque A)
> (deque->list (deque 10 2 34 4 15 6)) - : (Listof Integer)
'(10 2 34 4 15 6)
> (deque->list (map add1 (deque 1 2 3 4 5 6))) - : (Listof Integer)
'(2 3 4 5 6 7)
> (deque->list (map * (deque 1 2 3 4 5 6) (deque 1 2 3 4 5 6))) - : (Listof Integer)
'(1 4 9 16 25 36)
procedure
(foldl func init deq1 deq2 ...) → C
func : (C A B ... B -> C) init : C deq1 : (Deque A) deq2 : (Deque B)
foldl currently does not produce correct results when the given function is non-commutative.
> (foldl + 0 (deque 1 2 3 4 5 6)) - : Integer
21
> (foldl * 1 (deque 1 2 3 4 5 6) (deque 1 2 3 4 5 6)) - : Integer
518400
procedure
(foldr func init deq1 deq2 ...) → C
func : (C A B ... B -> C) init : C deq1 : (Deque A) deq2 : (Deque B)
foldr currently does not produce correct results when the given function is non-commutative.
> (foldr + 0 (deque 1 2 3 4 5 6)) - : Integer
21
> (foldr * 1 (deque 1 2 3 4 5 6) (deque 1 2 3 4 5 6)) - : Integer
518400
> (define que (deque 1 2 3 4 5 6)) > (deque->list (filter (λ: ([x : Integer]) (> x 5)) que)) - : (Listof Integer)
'(6)
> (deque->list (filter (λ: ([x : Integer]) (< x 5)) que)) - : (Listof Integer)
'(1 2 3 4)
> (deque->list (filter (λ: ([x : Integer]) (<= x 5)) que)) - : (Listof Integer)
'(1 2 3 4 5)
> (deque->list (remove (λ: ([x : Integer]) (> x 5)) (deque 1 2 3 4 5 6))) - : (Listof Integer)
'(1 2 3 4 5)
> (deque->list (remove (λ: ([x : Integer]) (< x 5)) (deque 1 2 3 4 5 6))) - : (Listof Integer)
'(5 6)
> (deque->list (remove (λ: ([x : Integer]) (<= x 5)) (deque 1 2 3 4 5 6))) - : (Listof Integer)
'(6)
procedure
(andmap func deq1 deq2 ...) → Boolean
func : (A B ... B -> Boolean) deq1 : (Deque A) deq2 : (Deque B)
> (andmap even? (deque 1 2 3 4 5 6)) - : Boolean
#f
> (andmap odd? (deque 1 2 3 4 5 6)) - : Boolean
#f
> (andmap positive? (deque 1 2 3 4 5 6)) - : Boolean
#t
> (andmap negative? (deque -1 -2)) - : Boolean
#t
procedure
(ormap func deq1 deq2 ...) → Boolean
func : (A B ... B -> Boolean) deq1 : (Deque A) deq2 : (Deque B)
> (ormap even? (deque 1 2 3 4 5 6)) - : Boolean
#t
> (ormap odd? (deque 1 2 3 4 5 6)) - : Boolean
#t
> (ormap positive? (deque -1 -2 3 4 -5 6)) - : Boolean
#t
> (ormap negative? (deque 1 -2)) - : Boolean
#t
procedure
(build-deque size func) → (Deque A)
size : Natural func : (Natural -> A)
> (deque->list (build-deque 5 (λ:([x : Integer]) (add1 x)))) - : (Listof Integer)
'(1 2 3 4 5)
> (deque->list (build-deque 5 (λ:([x : Integer]) (* x x)))) - : (Listof Integer)
'(0 1 4 9 16)
> (head+tail (deque 1 2 3 4 5))
- : (Pairof
Integer
#(struct:Deque
((Rec
g303608
(U (Boxof (U (-> (Pairof Integer g303608)) (Pairof Integer g303608)))
Null))
Integer
(Rec
g303611
(U (Boxof (U (-> (Pairof Integer g303611)) (Pairof Integer g303611)))
Null))
(Rec
g303614
(U (Boxof (U (-> (Pairof Integer g303614)) (Pairof Integer g303614)))
Null))
Integer
(Rec
g303617
(U (Boxof (U (-> (Pairof Integer g303617)) (Pairof Integer g303617)))
Null)))))
'(1 . #<Deque>)
> (head+tail (build-deque 5 (λ:([x : Integer]) (* x x))))
- : (Pairof
Integer
#(struct:Deque
((Rec
g303634
(U (Boxof (U (-> (Pairof Integer g303634)) (Pairof Integer g303634)))
Null))
Integer
(Rec
g303637
(U (Boxof (U (-> (Pairof Integer g303637)) (Pairof Integer g303637)))
Null))
(Rec
g303640
(U (Boxof (U (-> (Pairof Integer g303640)) (Pairof Integer g303640)))
Null))
Integer
(Rec
g303643
(U (Boxof (U (-> (Pairof Integer g303643)) (Pairof Integer g303643)))
Null)))))
'(0 . #<Deque>)
> (head+tail (empty Integer)) head+tail: given deque is empty
> (last+init (deque 1 2 3 4 5))
- : (Pairof
Integer
#(struct:Deque
((Rec
g303677
(U (Boxof (U (-> (Pairof Integer g303677)) (Pairof Integer g303677)))
Null))
Integer
(Rec
g303680
(U (Boxof (U (-> (Pairof Integer g303680)) (Pairof Integer g303680)))
Null))
(Rec
g303683
(U (Boxof (U (-> (Pairof Integer g303683)) (Pairof Integer g303683)))
Null))
Integer
(Rec
g303686
(U (Boxof (U (-> (Pairof Integer g303686)) (Pairof Integer g303686)))
Null)))))
'(5 . #<Deque>)
> (last+init (build-deque 5 (λ:([x : Integer]) (* x x))))
- : (Pairof
Integer
#(struct:Deque
((Rec
g303703
(U (Boxof (U (-> (Pairof Integer g303703)) (Pairof Integer g303703)))
Null))
Integer
(Rec
g303706
(U (Boxof (U (-> (Pairof Integer g303706)) (Pairof Integer g303706)))
Null))
(Rec
g303709
(U (Boxof (U (-> (Pairof Integer g303709)) (Pairof Integer g303709)))
Null))
Integer
(Rec
g303712
(U (Boxof (U (-> (Pairof Integer g303712)) (Pairof Integer g303712)))
Null)))))
'(16 . #<Deque>)
> (last+init (empty Integer)) last+init: given deque is empty