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
g298173
(U (Pairof Positive-Byte g298173) (Promiseof g298173) Null))
Integer
(Rec
g298175
(U (Pairof Positive-Byte g298175) (Promiseof g298175) 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
g298266
(U (Pairof Positive-Byte g298266) (Promiseof g298266) Null))
Integer
(Rec
g298268
(U (Pairof Positive-Byte g298268) (Promiseof g298268) 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
g299077
(U (Pairof Positive-Byte g299077) (Promiseof g299077) Null))
Integer
(Rec
g299079
(U (Pairof Positive-Byte g299079) (Promiseof g299079) Null))
Integer)))
'(1 . #<Deque>)
> (head+tail (build-deque 5 (λ:([x : Integer]) (* x x))))
- : (Pairof
Integer
#(struct:Deque
((Rec g299103 (U (Pairof Integer g299103) (Promiseof g299103) Null))
Integer
(Rec g299105 (U (Pairof Integer g299105) (Promiseof g299105) 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
g299146
(U (Pairof Positive-Byte g299146) (Promiseof g299146) Null))
Integer
(Rec
g299148
(U (Pairof Positive-Byte g299148) (Promiseof g299148) Null))
Integer)))
'(5 . #<Deque>)
> (last+init (build-deque 5 (λ:([x : Integer]) (* x x))))
- : (Pairof
Integer
#(struct:Deque
((Rec g299172 (U (Pairof Integer g299172) (Promiseof g299172) Null))
Integer
(Rec g299174 (U (Pairof Integer g299174) (Promiseof g299174) 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
g302823
(U (Boxof (U (-> (Pairof Integer g302823)) (Pairof Integer g302823)))
Null))
Integer
(Rec
g302826
(U (Boxof (U (-> (Pairof Integer g302826)) (Pairof Integer g302826)))
Null))
(Rec
g302829
(U (Boxof (U (-> (Pairof Integer g302829)) (Pairof Integer g302829)))
Null))
Integer
(Rec
g302832
(U (Boxof (U (-> (Pairof Integer g302832)) (Pairof Integer g302832)))
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
g302864
(U (Boxof (U (-> (Pairof Integer g302864)) (Pairof Integer g302864)))
Null))
Integer
(Rec
g302867
(U (Boxof (U (-> (Pairof Integer g302867)) (Pairof Integer g302867)))
Null))
(Rec
g302870
(U (Boxof (U (-> (Pairof Integer g302870)) (Pairof Integer g302870)))
Null))
Integer
(Rec
g302873
(U (Boxof (U (-> (Pairof Integer g302873)) (Pairof Integer g302873)))
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
g302885
(U (Boxof (U (-> (Pairof Integer g302885)) (Pairof Integer g302885)))
Null))
Integer
(Rec
g302888
(U (Boxof (U (-> (Pairof Integer g302888)) (Pairof Integer g302888)))
Null))
(Rec
g302891
(U (Boxof (U (-> (Pairof Integer g302891)) (Pairof Integer g302891)))
Null))
Integer
(Rec
g302894
(U (Boxof (U (-> (Pairof Integer g302894)) (Pairof Integer g302894)))
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
g302944
(U (Boxof (U (-> (Pairof Integer g302944)) (Pairof Integer g302944)))
Null))
Integer
(Rec
g302947
(U (Boxof (U (-> (Pairof Integer g302947)) (Pairof Integer g302947)))
Null))
(Rec
g302950
(U (Boxof (U (-> (Pairof Integer g302950)) (Pairof Integer g302950)))
Null))
Integer
(Rec
g302953
(U (Boxof (U (-> (Pairof Integer g302953)) (Pairof Integer g302953)))
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
g302987
(U (Boxof (U (-> (Pairof Integer g302987)) (Pairof Integer g302987)))
Null))
Integer
(Rec
g302990
(U (Boxof (U (-> (Pairof Integer g302990)) (Pairof Integer g302990)))
Null))
(Rec
g302993
(U (Boxof (U (-> (Pairof Integer g302993)) (Pairof Integer g302993)))
Null))
Integer
(Rec
g302996
(U (Boxof (U (-> (Pairof Integer g302996)) (Pairof Integer g302996)))
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
g303370
(U (Boxof (U (-> (Pairof Integer g303370)) (Pairof Integer g303370)))
Null))
Integer
(Rec
g303373
(U (Boxof (U (-> (Pairof Integer g303373)) (Pairof Integer g303373)))
Null))
(Rec
g303376
(U (Boxof (U (-> (Pairof Integer g303376)) (Pairof Integer g303376)))
Null))
Integer
(Rec
g303379
(U (Boxof (U (-> (Pairof Integer g303379)) (Pairof Integer g303379)))
Null)))))
'(1 . #<Deque>)
> (head+tail (build-deque 5 (λ:([x : Integer]) (* x x))))
- : (Pairof
Integer
#(struct:Deque
((Rec
g303396
(U (Boxof (U (-> (Pairof Integer g303396)) (Pairof Integer g303396)))
Null))
Integer
(Rec
g303399
(U (Boxof (U (-> (Pairof Integer g303399)) (Pairof Integer g303399)))
Null))
(Rec
g303402
(U (Boxof (U (-> (Pairof Integer g303402)) (Pairof Integer g303402)))
Null))
Integer
(Rec
g303405
(U (Boxof (U (-> (Pairof Integer g303405)) (Pairof Integer g303405)))
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
g303439
(U (Boxof (U (-> (Pairof Integer g303439)) (Pairof Integer g303439)))
Null))
Integer
(Rec
g303442
(U (Boxof (U (-> (Pairof Integer g303442)) (Pairof Integer g303442)))
Null))
(Rec
g303445
(U (Boxof (U (-> (Pairof Integer g303445)) (Pairof Integer g303445)))
Null))
Integer
(Rec
g303448
(U (Boxof (U (-> (Pairof Integer g303448)) (Pairof Integer g303448)))
Null)))))
'(5 . #<Deque>)
> (last+init (build-deque 5 (λ:([x : Integer]) (* x x))))
- : (Pairof
Integer
#(struct:Deque
((Rec
g303465
(U (Boxof (U (-> (Pairof Integer g303465)) (Pairof Integer g303465)))
Null))
Integer
(Rec
g303468
(U (Boxof (U (-> (Pairof Integer g303468)) (Pairof Integer g303468)))
Null))
(Rec
g303471
(U (Boxof (U (-> (Pairof Integer g303471)) (Pairof Integer g303471)))
Null))
Integer
(Rec
g303474
(U (Boxof (U (-> (Pairof Integer g303474)) (Pairof Integer g303474)))
Null)))))
'(16 . #<Deque>)
> (last+init (empty Integer)) last+init: given deque is empty