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
g298512
(U (Pairof Positive-Byte g298512) (Promiseof g298512) Null))
Integer
(Rec
g298514
(U (Pairof Positive-Byte g298514) (Promiseof g298514) 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
g298605
(U (Pairof Positive-Byte g298605) (Promiseof g298605) Null))
Integer
(Rec
g298607
(U (Pairof Positive-Byte g298607) (Promiseof g298607) 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
g299416
(U (Pairof Positive-Byte g299416) (Promiseof g299416) Null))
Integer
(Rec
g299418
(U (Pairof Positive-Byte g299418) (Promiseof g299418) Null))
Integer)))
'(1 . #<Deque>)
> (head+tail (build-deque 5 (λ:([x : Integer]) (* x x))))
- : (Pairof
Integer
#(struct:Deque
((Rec g299442 (U (Pairof Integer g299442) (Promiseof g299442) Null))
Integer
(Rec g299444 (U (Pairof Integer g299444) (Promiseof g299444) 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
g299485
(U (Pairof Positive-Byte g299485) (Promiseof g299485) Null))
Integer
(Rec
g299487
(U (Pairof Positive-Byte g299487) (Promiseof g299487) Null))
Integer)))
'(5 . #<Deque>)
> (last+init (build-deque 5 (λ:([x : Integer]) (* x x))))
- : (Pairof
Integer
#(struct:Deque
((Rec g299511 (U (Pairof Integer g299511) (Promiseof g299511) Null))
Integer
(Rec g299513 (U (Pairof Integer g299513) (Promiseof g299513) 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
g303162
(U (Boxof (U (-> (Pairof Integer g303162)) (Pairof Integer g303162)))
Null))
Integer
(Rec
g303165
(U (Boxof (U (-> (Pairof Integer g303165)) (Pairof Integer g303165)))
Null))
(Rec
g303168
(U (Boxof (U (-> (Pairof Integer g303168)) (Pairof Integer g303168)))
Null))
Integer
(Rec
g303171
(U (Boxof (U (-> (Pairof Integer g303171)) (Pairof Integer g303171)))
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
g303203
(U (Boxof (U (-> (Pairof Integer g303203)) (Pairof Integer g303203)))
Null))
Integer
(Rec
g303206
(U (Boxof (U (-> (Pairof Integer g303206)) (Pairof Integer g303206)))
Null))
(Rec
g303209
(U (Boxof (U (-> (Pairof Integer g303209)) (Pairof Integer g303209)))
Null))
Integer
(Rec
g303212
(U (Boxof (U (-> (Pairof Integer g303212)) (Pairof Integer g303212)))
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
g303224
(U (Boxof (U (-> (Pairof Integer g303224)) (Pairof Integer g303224)))
Null))
Integer
(Rec
g303227
(U (Boxof (U (-> (Pairof Integer g303227)) (Pairof Integer g303227)))
Null))
(Rec
g303230
(U (Boxof (U (-> (Pairof Integer g303230)) (Pairof Integer g303230)))
Null))
Integer
(Rec
g303233
(U (Boxof (U (-> (Pairof Integer g303233)) (Pairof Integer g303233)))
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
g303283
(U (Boxof (U (-> (Pairof Integer g303283)) (Pairof Integer g303283)))
Null))
Integer
(Rec
g303286
(U (Boxof (U (-> (Pairof Integer g303286)) (Pairof Integer g303286)))
Null))
(Rec
g303289
(U (Boxof (U (-> (Pairof Integer g303289)) (Pairof Integer g303289)))
Null))
Integer
(Rec
g303292
(U (Boxof (U (-> (Pairof Integer g303292)) (Pairof Integer g303292)))
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
g303326
(U (Boxof (U (-> (Pairof Integer g303326)) (Pairof Integer g303326)))
Null))
Integer
(Rec
g303329
(U (Boxof (U (-> (Pairof Integer g303329)) (Pairof Integer g303329)))
Null))
(Rec
g303332
(U (Boxof (U (-> (Pairof Integer g303332)) (Pairof Integer g303332)))
Null))
Integer
(Rec
g303335
(U (Boxof (U (-> (Pairof Integer g303335)) (Pairof Integer g303335)))
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
g303709
(U (Boxof (U (-> (Pairof Integer g303709)) (Pairof Integer g303709)))
Null))
Integer
(Rec
g303712
(U (Boxof (U (-> (Pairof Integer g303712)) (Pairof Integer g303712)))
Null))
(Rec
g303715
(U (Boxof (U (-> (Pairof Integer g303715)) (Pairof Integer g303715)))
Null))
Integer
(Rec
g303718
(U (Boxof (U (-> (Pairof Integer g303718)) (Pairof Integer g303718)))
Null)))))
'(1 . #<Deque>)
> (head+tail (build-deque 5 (λ:([x : Integer]) (* x x))))
- : (Pairof
Integer
#(struct:Deque
((Rec
g303735
(U (Boxof (U (-> (Pairof Integer g303735)) (Pairof Integer g303735)))
Null))
Integer
(Rec
g303738
(U (Boxof (U (-> (Pairof Integer g303738)) (Pairof Integer g303738)))
Null))
(Rec
g303741
(U (Boxof (U (-> (Pairof Integer g303741)) (Pairof Integer g303741)))
Null))
Integer
(Rec
g303744
(U (Boxof (U (-> (Pairof Integer g303744)) (Pairof Integer g303744)))
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
g303778
(U (Boxof (U (-> (Pairof Integer g303778)) (Pairof Integer g303778)))
Null))
Integer
(Rec
g303781
(U (Boxof (U (-> (Pairof Integer g303781)) (Pairof Integer g303781)))
Null))
(Rec
g303784
(U (Boxof (U (-> (Pairof Integer g303784)) (Pairof Integer g303784)))
Null))
Integer
(Rec
g303787
(U (Boxof (U (-> (Pairof Integer g303787)) (Pairof Integer g303787)))
Null)))))
'(5 . #<Deque>)
> (last+init (build-deque 5 (λ:([x : Integer]) (* x x))))
- : (Pairof
Integer
#(struct:Deque
((Rec
g303804
(U (Boxof (U (-> (Pairof Integer g303804)) (Pairof Integer g303804)))
Null))
Integer
(Rec
g303807
(U (Boxof (U (-> (Pairof Integer g303807)) (Pairof Integer g303807)))
Null))
(Rec
g303810
(U (Boxof (U (-> (Pairof Integer g303810)) (Pairof Integer g303810)))
Null))
Integer
(Rec
g303813
(U (Boxof (U (-> (Pairof Integer g303813)) (Pairof Integer g303813)))
Null)))))
'(16 . #<Deque>)
> (last+init (empty Integer)) last+init: given deque is empty