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
g305894
(U (Pairof Positive-Byte g305894) (Promiseof g305894) Null))
Integer
(Rec
g305896
(U (Pairof Positive-Byte g305896) (Promiseof g305896) 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
g305987
(U (Pairof Positive-Byte g305987) (Promiseof g305987) Null))
Integer
(Rec
g305989
(U (Pairof Positive-Byte g305989) (Promiseof g305989) 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
g306798
(U (Pairof Positive-Byte g306798) (Promiseof g306798) Null))
Integer
(Rec
g306800
(U (Pairof Positive-Byte g306800) (Promiseof g306800) Null))
Integer)))
'(1 . #<Deque>)
> (head+tail (build-deque 5 (λ:([x : Integer]) (* x x))))
- : (Pairof
Integer
#(struct:Deque
((Rec g306824 (U (Pairof Integer g306824) (Promiseof g306824) Null))
Integer
(Rec g306826 (U (Pairof Integer g306826) (Promiseof g306826) 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
g306867
(U (Pairof Positive-Byte g306867) (Promiseof g306867) Null))
Integer
(Rec
g306869
(U (Pairof Positive-Byte g306869) (Promiseof g306869) Null))
Integer)))
'(5 . #<Deque>)
> (last+init (build-deque 5 (λ:([x : Integer]) (* x x))))
- : (Pairof
Integer
#(struct:Deque
((Rec g306893 (U (Pairof Integer g306893) (Promiseof g306893) Null))
Integer
(Rec g306895 (U (Pairof Integer g306895) (Promiseof g306895) 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
g310544
(U (Boxof (U (-> (Pairof Integer g310544)) (Pairof Integer g310544)))
Null))
Integer
(Rec
g310547
(U (Boxof (U (-> (Pairof Integer g310547)) (Pairof Integer g310547)))
Null))
(Rec
g310550
(U (Boxof (U (-> (Pairof Integer g310550)) (Pairof Integer g310550)))
Null))
Integer
(Rec
g310553
(U (Boxof (U (-> (Pairof Integer g310553)) (Pairof Integer g310553)))
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
g310585
(U (Boxof (U (-> (Pairof Integer g310585)) (Pairof Integer g310585)))
Null))
Integer
(Rec
g310588
(U (Boxof (U (-> (Pairof Integer g310588)) (Pairof Integer g310588)))
Null))
(Rec
g310591
(U (Boxof (U (-> (Pairof Integer g310591)) (Pairof Integer g310591)))
Null))
Integer
(Rec
g310594
(U (Boxof (U (-> (Pairof Integer g310594)) (Pairof Integer g310594)))
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
g310606
(U (Boxof (U (-> (Pairof Integer g310606)) (Pairof Integer g310606)))
Null))
Integer
(Rec
g310609
(U (Boxof (U (-> (Pairof Integer g310609)) (Pairof Integer g310609)))
Null))
(Rec
g310612
(U (Boxof (U (-> (Pairof Integer g310612)) (Pairof Integer g310612)))
Null))
Integer
(Rec
g310615
(U (Boxof (U (-> (Pairof Integer g310615)) (Pairof Integer g310615)))
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
g310665
(U (Boxof (U (-> (Pairof Integer g310665)) (Pairof Integer g310665)))
Null))
Integer
(Rec
g310668
(U (Boxof (U (-> (Pairof Integer g310668)) (Pairof Integer g310668)))
Null))
(Rec
g310671
(U (Boxof (U (-> (Pairof Integer g310671)) (Pairof Integer g310671)))
Null))
Integer
(Rec
g310674
(U (Boxof (U (-> (Pairof Integer g310674)) (Pairof Integer g310674)))
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
g310708
(U (Boxof (U (-> (Pairof Integer g310708)) (Pairof Integer g310708)))
Null))
Integer
(Rec
g310711
(U (Boxof (U (-> (Pairof Integer g310711)) (Pairof Integer g310711)))
Null))
(Rec
g310714
(U (Boxof (U (-> (Pairof Integer g310714)) (Pairof Integer g310714)))
Null))
Integer
(Rec
g310717
(U (Boxof (U (-> (Pairof Integer g310717)) (Pairof Integer g310717)))
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
g311091
(U (Boxof (U (-> (Pairof Integer g311091)) (Pairof Integer g311091)))
Null))
Integer
(Rec
g311094
(U (Boxof (U (-> (Pairof Integer g311094)) (Pairof Integer g311094)))
Null))
(Rec
g311097
(U (Boxof (U (-> (Pairof Integer g311097)) (Pairof Integer g311097)))
Null))
Integer
(Rec
g311100
(U (Boxof (U (-> (Pairof Integer g311100)) (Pairof Integer g311100)))
Null)))))
'(1 . #<Deque>)
> (head+tail (build-deque 5 (λ:([x : Integer]) (* x x))))
- : (Pairof
Integer
#(struct:Deque
((Rec
g311117
(U (Boxof (U (-> (Pairof Integer g311117)) (Pairof Integer g311117)))
Null))
Integer
(Rec
g311120
(U (Boxof (U (-> (Pairof Integer g311120)) (Pairof Integer g311120)))
Null))
(Rec
g311123
(U (Boxof (U (-> (Pairof Integer g311123)) (Pairof Integer g311123)))
Null))
Integer
(Rec
g311126
(U (Boxof (U (-> (Pairof Integer g311126)) (Pairof Integer g311126)))
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
g311160
(U (Boxof (U (-> (Pairof Integer g311160)) (Pairof Integer g311160)))
Null))
Integer
(Rec
g311163
(U (Boxof (U (-> (Pairof Integer g311163)) (Pairof Integer g311163)))
Null))
(Rec
g311166
(U (Boxof (U (-> (Pairof Integer g311166)) (Pairof Integer g311166)))
Null))
Integer
(Rec
g311169
(U (Boxof (U (-> (Pairof Integer g311169)) (Pairof Integer g311169)))
Null)))))
'(5 . #<Deque>)
> (last+init (build-deque 5 (λ:([x : Integer]) (* x x))))
- : (Pairof
Integer
#(struct:Deque
((Rec
g311186
(U (Boxof (U (-> (Pairof Integer g311186)) (Pairof Integer g311186)))
Null))
Integer
(Rec
g311189
(U (Boxof (U (-> (Pairof Integer g311189)) (Pairof Integer g311189)))
Null))
(Rec
g311192
(U (Boxof (U (-> (Pairof Integer g311192)) (Pairof Integer g311192)))
Null))
Integer
(Rec
g311195
(U (Boxof (U (-> (Pairof Integer g311195)) (Pairof Integer g311195)))
Null)))))
'(16 . #<Deque>)
> (last+init (empty Integer)) last+init: given deque is empty