6.2.901.900
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
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.
A banker’s deque of type A.
Function
deque creates a Bankers Deque with the given inputs.
Example: |
| > (deque 1 2 3 4 5 6) | - : (Deque Positive-Byte) | #<Deque> |
|
In the above example, the deque obtained will have 1 as its head element.
An empty deque of type t.
Examples: |
| > (empty Nothing) | - : (Deque Nothing) | #<Deque> | | > (empty Integer) | - : (Deque Integer) | #<Deque> |
|
Function
empty? checks if the given deque is empty.
Function
enqueue takes an element and a deque and enqueues
the given element in the
deque.
Example: |
| > (enqueue 10 (deque 3 2 4)) | - : (Deque Positive-Byte) | #<Deque> |
|
In the above example,
(enqueue 10 deq) adds the element 10 to
(deque 3 2 4). 10 will be the last element in the deque.
Function
enqueue-front takes an element and a deque and puts
the given element to the front of the given 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.
Function
head takes a deque and gives the first element in the
deque if deque is not empty else throws an error.
Examples: |
| > (head (deque 5 2 3)) | - : Integer [more precisely: Positive-Byte] | 5 | | > (head (empty Integer)) | head: given deque is empty |
|
In the above example, (head (empty Integer)) throws an error
since the given deque is empty.
Function
last takes a deque and gives the last element in the
deque if deque is not empty else throws an error.
Examples: |
| > (last (deque 1 2 3 4 5 6)) | - : Integer [more precisely: Positive-Byte] | 6 | | > (last (empty Integer)) | last: given deque is empty |
|
In the above example, (last (empty Integer))throws an error
since the given deque is empty.
Function
tail takes a deque and returns the given deque
without the first element if the given deque is non empty else throws an
error.
Examples: |
| > (tail (deque 1 2 3 4 5 6)) | - : (Deque Positive-Byte) | #<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).
Function
init takes a deque and returns the given deque
without the last element if the given deque is not empty else throws an error.
Examples: |
| > (init (deque 1 2 3 4 5 6)) | - : (Deque Positive-Byte) | #<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 and returns (deque 1 2 3 4 5).
Function
deque->list takes a deque and returns a list of
elements. The list will have head of the given deque as its first element.
If the given deque is empty, then it returns an empty list.
(map func deq1 deq2 ...) → (Deque A)
|
| func : (A B ... B -> C) |
| deq1 : (Deque A) |
| deq2 : (Deque B) |
Function
map is similar to
map for lists.
(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.
Examples: |
| > (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 |
|
(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.
Examples: |
| > (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 |
|
Examples: |
| > (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) |
|
Function
remove is similar to
filter but
remove removes the elements which match the predicate.
Examples: |
| - : (Listof Positive-Byte) | '(1 2 3 4 5) | | - : (Listof Positive-Byte) | '(5 6) | | - : (Listof Positive-Byte) | '(6) |
|
(andmap func deq1 deq2 ...) → Boolean
|
| func : (A B ... B -> Boolean) |
| deq1 : (Deque A) |
| deq2 : (Deque B) |
(ormap func deq1 deq2 ...) → Boolean
|
| func : (A B ... B -> Boolean) |
| deq1 : (Deque A) |
| deq2 : (Deque B) |
Function
head+tail returns a pair containing the head and the tail of
the given deque.
Examples: |
| > (head+tail (deque 1 2 3 4 5)) | - : (Pairof Positive-Byte (Deque Positive-Byte)) | '(1 . #<Deque>) | | > (head+tail (build-deque 5 (λ:([x : Integer]) (* x x)))) | - : (Pairof Integer (Deque Integer)) | '(0 . #<Deque>) | | > (head+tail (empty Integer)) | head+tail: given deque is empty |
|
Function
last+init returns a pair containing the last element and
the init of the given deque.
Examples: |
| > (last+init (deque 1 2 3 4 5)) | - : (Pairof Positive-Byte (Deque Positive-Byte)) | '(5 . #<Deque>) | | > (last+init (build-deque 5 (λ:([x : Integer]) (* x x)))) | - : (Pairof Integer (Deque Integer)) | '(16 . #<Deque>) | | > (last+init (empty Integer)) | last+init: given deque is empty |
|
2.2 Implicit Deque
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.
Implicit double ended queue of type A.
Function
deque creates a Implicit Deque with the given inputs.
Example: |
| > (deque 1 2 3 4 5 6) | - : (U (Shallow Positive-Byte) (Deep Positive-Byte)) | #<Deep> |
|
In the above example, the deque obtained will have 1 as its head element.
An empty deque
Function
empty? checks if the given deque is empty or not.
Function
enqueue takes an element and a deque and enqueues
the given element into the deque.
Example: |
| > (enqueue 10 (deque 1 2 3 4 5 6)) | - : (U (Shallow Positive-Byte) (Deep Positive-Byte)) | #<Deep> |
|
In the above example, enqueue adds the element 10 to
(deque 1 2 3 4 5 6 10).
Function
enqueue-front takes an element and a deque and puts
the given element to the front of the given deque.
Example: |
| > (enqueue-front 10 (deque 5 6 3 4)) | - : (U (Shallow Positive-Byte) (Deep 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.
Function
head takes a deque and gives the first element in the
deque if deque is not empty else throws an error.
Examples: |
| > (head (deque 1 2 3 4 5 6)) | - : Integer [more precisely: Positive-Byte] | 1 | | > (head empty) | head: given deque is empty |
|
Function
last takes a deque and gives the last element in the
queue if deque is not empty else throws an error.
Examples: |
| > (last (deque 1 2 3 4 5 6)) | - : Integer [more precisely: Positive-Byte] | 6 | | > (last empty) | last: given deque is empty |
|
Function
tail takes a deque and returns a deque with rest
elements if its a non empty deque else throws an error.
Examples: |
| > (tail (deque 1 2 3 4 5 6)) | - : (U (Shallow Positive-Byte) (Deep Positive-Byte)) | #<Deep> | | > (tail empty) | tail: given deque is empty |
|
In the above example, (tail (deque 1 2 3 4 5 6)), removes 1
and returns (tail (deque 2 3 4 5 6)).
Function
init takes a deque and returns a deque without the
last element if its a non empty deque else throws an error.
Examples: |
| > (init (deque 1 2 3 4 5 6)) | - : (U (Shallow Positive-Byte) (Deep Positive-Byte)) | #<Deep> | | > (init empty) | init: given deque is empty |
|
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)
Function
deque->list takes a deque and returns a list of
elements. The list will have head of the given deque as its first element.
If the given deque is empty, then it returns an empty list.
Example: |
| > (deque->list (deque 10 2 34 4 15 6)) | - : (Listof Positive-Byte) | '(10 2 34 4 15 6) |
|
(map func deq1 deq2 ...) → (Deque A)
|
| func : (A B ... B -> C) |
| deq1 : (Deque A) |
| deq2 : (Deque B) |
Function
map is similar to
map for lists.
(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.
Examples: |
| > (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 |
|
(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.
Examples: |
| > (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 |
|
Examples: |
| > (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) |
|
Function
remove is similar to
filter but
remove removes the elements which match the predicate.
Examples: |
| - : (Listof Positive-Byte) | '(1 2 3 4 5) | | - : (Listof Positive-Byte) | '(5 6) | | - : (Listof Positive-Byte) | '(6) |
|
(andmap func deq1 deq2 ...) → Boolean
|
| func : (A B ... B -> Boolean) |
| deq1 : (Deque A) |
| deq2 : (Deque B) |
(ormap func deq1 deq2 ...) → Boolean
|
| func : (A B ... B -> Boolean) |
| deq1 : (Deque A) |
| deq2 : (Deque B) |
Function
head+tail returns a pair containing the head and the tail of
the given deque.
Examples: |
| > (head+tail (deque 1 2 3 4 5)) | - : (Pairof Positive-Byte (U (Shallow Positive-Byte) (Deep Positive-Byte))) | '(1 . #<Deep>) | | > (head+tail (build-deque 5 (λ:([x : Integer]) (* x x)))) | - : (Pairof Integer (U (Shallow Integer) (Deep Integer))) | '(0 . #<Deep>) | | > (head+tail empty) | head+tail: given deque is empty |
|
Function
last+init returns a pair containing the last element and
the init of the given deque.
Examples: |
| > (last+init (deque 1 2 3 4 5)) | - : (Pairof Positive-Byte (U (Shallow Positive-Byte) (Deep Positive-Byte))) | '(5 . #<Deep>) | | > (last+init (build-deque 5 (λ:([x : Integer]) (* x x)))) | - : (Pairof Integer (U (Shallow Integer) (Deep Integer))) | '(16 . #<Deep>) | | > (last+init empty) | last+init: given deque is empty |
|
2.3 Real-Time Deque
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.
Real-time double ended queue of type A.
Function
deque creates a Real-Time Deque with the given inputs.
Example: |
| > (deque 1 2 3 4 5 6) | - : (Deque Integer) | #<Deque> |
|
In the above example, the deque obtained will have 1 as its head element.
An empty deque.
Function
empty? checks if the given deque is empty or not.
Function
enqueue takes an element and a deque and enqueues
the given element into the deque.
Example: |
| > (enqueue 10 (deque 1 2 3 4 5 6)) | - : (Deque Integer) | #<Deque> |
|
In the above example, enqueue adds the element 10 to the end of
(deque 1 2 3 4 5 6).
Function
enqueue-front takes an element and a deque and adds
the given element to the front of 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).
Function
head takes a deque and gives the first element in the
deque if deque is not empty else throws an error.
Examples: |
| > (head (deque 1 2 3 4 5 6)) | - : Integer | 1 | | > (head (empty Integer)) | head: given deque is empty |
|
Function
last takes a deque and gives the last element in the
queue if deque is not empty else throws an error.
Examples: |
| > (last (deque 1 2 3 4 5 6)) | - : Integer | 6 | | > (last (empty Integer)) | last: given deque is empty |
|
Function
tail takes a deque and returns a deque with rest
elements if its a non empty deque else throws an error.
Examples: |
| > (tail (deque 1 2 3 4 5 6)) | - : (Deque Integer) | #<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).
Function
init takes a deque and returns a deque without the
last element if its a non empty deque else throws an error.
Examples: |
| > (init (deque 1 2 3 4 5 6)) | - : (Deque Integer) | #<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).
Function
deque->list takes a deque and returns a list of
elements. The list will have head of the given deque as its first element.
If the given deque is empty, then it returns an empty list.
(map func deq1 deq2 ...) → (Deque A)
|
| func : (A B ... B -> C) |
| deq1 : (Deque A) |
| deq2 : (Deque B) |
Function
map is similar to
map for lists.
(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.
(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.
Examples: |
| > (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) |
|
Function
remove is similar to
filter but
remove removes the elements which match the predicate.
Examples: |
| - : (Listof Integer) | '(1 2 3 4 5) | | - : (Listof Integer) | '(5 6) | | - : (Listof Integer) | '(6) |
|
(andmap func deq1 deq2 ...) → Boolean
|
| func : (A B ... B -> Boolean) |
| deq1 : (Deque A) |
| deq2 : (Deque B) |
(ormap func deq1 deq2 ...) → Boolean
|
| func : (A B ... B -> Boolean) |
| deq1 : (Deque A) |
| deq2 : (Deque B) |
Function
head+tail returns a pair containing the head and the tail of
the given deque.
Examples: |
| > (head+tail (deque 1 2 3 4 5)) | - : (Pairof Integer (Deque Integer)) | '(1 . #<Deque>) | | > (head+tail (build-deque 5 (λ:([x : Integer]) (* x x)))) | - : (Pairof Integer (Deque Integer)) | '(0 . #<Deque>) | | > (head+tail (empty Integer)) | head+tail: given deque is empty |
|
Function
last+init returns a pair containing the last element and
the init of the given deque.
Examples: |
| > (last+init (deque 1 2 3 4 5)) | - : (Pairof Integer (Deque Integer)) | '(5 . #<Deque>) | | > (last+init (build-deque 5 (λ:([x : Integer]) (* x x)))) | - : (Pairof Integer (Deque Integer)) | '(16 . #<Deque>) | | > (last+init (empty Integer)) | last+init: given deque is empty |
|