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
g301520
(U (Pairof Positive-Byte g301520) (Promiseof g301520) Null))
Integer
(Rec
g301522
(U (Pairof Positive-Byte g301522) (Promiseof g301522) 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
g301613
(U (Pairof Positive-Byte g301613) (Promiseof g301613) Null))
Integer
(Rec
g301615
(U (Pairof Positive-Byte g301615) (Promiseof g301615) 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
g302424
(U (Pairof Positive-Byte g302424) (Promiseof g302424) Null))
Integer
(Rec
g302426
(U (Pairof Positive-Byte g302426) (Promiseof g302426) Null))
Integer)))
'(1 . #<Deque>)
> (head+tail (build-deque 5 (λ:([x : Integer]) (* x x))))
- : (Pairof
Integer
#(struct:Deque
((Rec g302450 (U (Pairof Integer g302450) (Promiseof g302450) Null))
Integer
(Rec g302452 (U (Pairof Integer g302452) (Promiseof g302452) 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
g302493
(U (Pairof Positive-Byte g302493) (Promiseof g302493) Null))
Integer
(Rec
g302495
(U (Pairof Positive-Byte g302495) (Promiseof g302495) Null))
Integer)))
'(5 . #<Deque>)
> (last+init (build-deque 5 (λ:([x : Integer]) (* x x))))
- : (Pairof
Integer
#(struct:Deque
((Rec g302519 (U (Pairof Integer g302519) (Promiseof g302519) Null))
Integer
(Rec g302521 (U (Pairof Integer g302521) (Promiseof g302521) 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
g306166
(U (Boxof (U (-> (Pairof Integer g306166)) (Pairof Integer g306166)))
Null))
Integer
(Rec
g306169
(U (Boxof (U (-> (Pairof Integer g306169)) (Pairof Integer g306169)))
Null))
(Rec
g306172
(U (Boxof (U (-> (Pairof Integer g306172)) (Pairof Integer g306172)))
Null))
Integer
(Rec
g306175
(U (Boxof (U (-> (Pairof Integer g306175)) (Pairof Integer g306175)))
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
g306207
(U (Boxof (U (-> (Pairof Integer g306207)) (Pairof Integer g306207)))
Null))
Integer
(Rec
g306210
(U (Boxof (U (-> (Pairof Integer g306210)) (Pairof Integer g306210)))
Null))
(Rec
g306213
(U (Boxof (U (-> (Pairof Integer g306213)) (Pairof Integer g306213)))
Null))
Integer
(Rec
g306216
(U (Boxof (U (-> (Pairof Integer g306216)) (Pairof Integer g306216)))
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
g306228
(U (Boxof (U (-> (Pairof Integer g306228)) (Pairof Integer g306228)))
Null))
Integer
(Rec
g306231
(U (Boxof (U (-> (Pairof Integer g306231)) (Pairof Integer g306231)))
Null))
(Rec
g306234
(U (Boxof (U (-> (Pairof Integer g306234)) (Pairof Integer g306234)))
Null))
Integer
(Rec
g306237
(U (Boxof (U (-> (Pairof Integer g306237)) (Pairof Integer g306237)))
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
g306287
(U (Boxof (U (-> (Pairof Integer g306287)) (Pairof Integer g306287)))
Null))
Integer
(Rec
g306290
(U (Boxof (U (-> (Pairof Integer g306290)) (Pairof Integer g306290)))
Null))
(Rec
g306293
(U (Boxof (U (-> (Pairof Integer g306293)) (Pairof Integer g306293)))
Null))
Integer
(Rec
g306296
(U (Boxof (U (-> (Pairof Integer g306296)) (Pairof Integer g306296)))
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
g306330
(U (Boxof (U (-> (Pairof Integer g306330)) (Pairof Integer g306330)))
Null))
Integer
(Rec
g306333
(U (Boxof (U (-> (Pairof Integer g306333)) (Pairof Integer g306333)))
Null))
(Rec
g306336
(U (Boxof (U (-> (Pairof Integer g306336)) (Pairof Integer g306336)))
Null))
Integer
(Rec
g306339
(U (Boxof (U (-> (Pairof Integer g306339)) (Pairof Integer g306339)))
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
g306713
(U (Boxof (U (-> (Pairof Integer g306713)) (Pairof Integer g306713)))
Null))
Integer
(Rec
g306716
(U (Boxof (U (-> (Pairof Integer g306716)) (Pairof Integer g306716)))
Null))
(Rec
g306719
(U (Boxof (U (-> (Pairof Integer g306719)) (Pairof Integer g306719)))
Null))
Integer
(Rec
g306722
(U (Boxof (U (-> (Pairof Integer g306722)) (Pairof Integer g306722)))
Null)))))
'(1 . #<Deque>)
> (head+tail (build-deque 5 (λ:([x : Integer]) (* x x))))
- : (Pairof
Integer
#(struct:Deque
((Rec
g306739
(U (Boxof (U (-> (Pairof Integer g306739)) (Pairof Integer g306739)))
Null))
Integer
(Rec
g306742
(U (Boxof (U (-> (Pairof Integer g306742)) (Pairof Integer g306742)))
Null))
(Rec
g306745
(U (Boxof (U (-> (Pairof Integer g306745)) (Pairof Integer g306745)))
Null))
Integer
(Rec
g306748
(U (Boxof (U (-> (Pairof Integer g306748)) (Pairof Integer g306748)))
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
g306782
(U (Boxof (U (-> (Pairof Integer g306782)) (Pairof Integer g306782)))
Null))
Integer
(Rec
g306785
(U (Boxof (U (-> (Pairof Integer g306785)) (Pairof Integer g306785)))
Null))
(Rec
g306788
(U (Boxof (U (-> (Pairof Integer g306788)) (Pairof Integer g306788)))
Null))
Integer
(Rec
g306791
(U (Boxof (U (-> (Pairof Integer g306791)) (Pairof Integer g306791)))
Null)))))
'(5 . #<Deque>)
> (last+init (build-deque 5 (λ:([x : Integer]) (* x x))))
- : (Pairof
Integer
#(struct:Deque
((Rec
g306808
(U (Boxof (U (-> (Pairof Integer g306808)) (Pairof Integer g306808)))
Null))
Integer
(Rec
g306811
(U (Boxof (U (-> (Pairof Integer g306811)) (Pairof Integer g306811)))
Null))
(Rec
g306814
(U (Boxof (U (-> (Pairof Integer g306814)) (Pairof Integer g306814)))
Null))
Integer
(Rec
g306817
(U (Boxof (U (-> (Pairof Integer g306817)) (Pairof Integer g306817)))
Null)))))
'(16 . #<Deque>)
> (last+init (empty Integer)) last+init: given deque is empty