6.2.901.900
1 Queues
Following queue structures implement and provide the functions
empty?, enqueue, head, tail, queue and queue->list. All the queue
structures are polymorphic.
1.1 Banker’s Queue
A Queue is nothing but a FIFO data structure. A Banker’s Queue is a
amortized queue obtained using Bankers method. It provides a amortized
running time of O(1) for head, tail
and enqueue operations. To obtain this amortized running time,
the data structure uses the techniques, lazy evaluation and
memoization. Banker’s Queue internally uses Streams for lazy
evaluation. For Streams, see Streams
A banker’s queue of type A.
Function
queue creates a Banker’s Queue with the given inputs.
Example: |
| > (queue 1 2 3 4 5 6) | - : (Queue Positive-Byte) | #<Queue> |
|
In the above example, the queue obtained will have 1 as its head element.
An empty queue instantiated to type t.
Examples: |
| > (empty Nothing) | - : (Queue Nothing) | #<Queue> | | > (empty Integer) | - : (Queue Integer) | #<Queue> |
|
Function
empty? checks if the given queue is empty or not.
Function
enqueue takes an element and a queue and adds the given
element into the
queue.
Example: |
| > (enqueue 10 (queue 4 5 6)) | - : (Queue Positive-Byte) | #<Queue> |
|
In the above example, (enqueue 10 (queue 4 5 6)) enqueues 10 to the
end of the queue and returns (queue 4 5 6 10).
Function
head takes a
queue and returns the first element
in the queue if its a non empty queue else throws an error.
Examples: |
| > (head (queue 10 4 3 12)) | - : Integer [more precisely: Positive-Byte] | 10 | | > (head (empty Integer)) | head: given queue is empty |
|
Function
tail takes a queue and returns the same queue
without the first element. If the queue is empty it throws an error.
Examples: |
| > (tail (queue 4 5 6)) | - : (Queue Positive-Byte) | #<Queue> | | > (tail (empty Integer)) | tail: given queue is empty |
|
In the above example, (tail (queue 4 5 6)), returns
(queue 5 6).
Function
queue->list takes a queue and returns a list of
elements. The list will have head of the given queue as its first element.
(map func que1 que2 ...) → (Queue A)
|
| func : (A B ... B -> C) |
| que1 : (Queue A) |
| que2 : (Queue B) |
Function
map is similar to
map for lists.
(fold func init que1 que2 ...) → C
|
| func : (C A B ... B -> C) |
| init : C |
| que1 : (Queue A) |
| que2 : (Queue B) |
fold currently does not produce correct results when the
given function is non-commutative.
Examples: |
| > (fold + 0 (queue 1 2 3 4 5 6)) | - : Integer [more precisely: Nonnegative-Integer] | 21 | | > (fold * 1 (queue 1 2 3 4 5 6) (queue 1 2 3 4 5 6)) | - : Integer [more precisely: Positive-Integer] | 518400 |
|
Examples: |
| > (define que (queue 1 2 3 4 5 6)) | | | > (queue->list (filter (λ: ([x : Integer]) (> x 5)) que)) | - : (Listof Positive-Byte) | '(6) | | > (queue->list (filter (λ: ([x : Integer]) (< x 5)) que)) | - : (Listof Positive-Byte) | '(1 2 3 4) | | > (queue->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 que1 que2 ...) → Boolean
|
| func : (A B ... B -> Boolean) |
| que1 : (Queue A) |
| que2 : (Queue B) |
(ormap func que1 que2 ...) → Boolean
|
| func : (A B ... B -> Boolean) |
| que1 : (Queue A) |
| que2 : (Queue B) |
Function
head+tail returns a pair containing the head and the tail of
the given queue.
Examples: |
| > (head+tail (queue 1 2 3 4 5)) | - : (Pairof Positive-Byte (Queue Positive-Byte)) | '(1 . #<Queue>) | | > (head+tail (build-queue 5 (λ:([x : Integer]) (* x x)))) | - : (Pairof Integer (Queue Integer)) | '(0 . #<Queue>) | | > (head+tail (empty Integer)) | head+tail: given queue is empty |
|
1.2 Physicist’s Queue
A Queue is nothing but a FIFO data structure. A Physicist’s queue ia a
Amortized queues obtained by Physicist’s method. Provides a amortized
running time of O(1) for head, tail
and enqueue operations. Physicists’s Queue uses lazy evaluation
and memoization to get this amortized running time.
A physicist’s queue of type A.
Function
queue creates a Physicist’s Queue with the given inputs.
Example: |
| > (queue 1 2 3 4 5 6) | - : (Queue Integer) | #<Queue> |
|
In the above example, the queue obtained will have 1 as its head element
An empty queue.
Function
empty? checks if the given queue is empty or not.
Function
enqueue takes an element and a queue and enqueues
the given element into the queue.
Example: |
| > (enqueue 10 (queue 1 2 3 4 5 6)) | - : (Queue Integer) | #<Queue> |
|
In the above example, enqueue adds the element 10 to
(queue 1 2 3 4 5 6) and returns (queue 1 2 3 4 5 6 10).
Function
head takes a queue and gives the first element in the
queue if its a non empty queue else throws an error.
Examples: |
| > (head (queue 1 2 3 4 5 6)) | - : Integer | 1 | | > (head (empty Integer)) | head: given queue is empty |
|
Function
tail takes a queue and returns a queue with rest
elements if its a non empty queue else throws an error.
Examples: |
| > (tail (queue 1 2 3 4 5 6)) | - : (Queue Integer) | #<Queue> | | > (tail (empty Integer)) | tail: given queue is empty |
|
In the above example, (tail (queue 1 2 3 4 5 6)), returns
(queue 2 3 4 5 6).
Function
queue->list takes a queue and returns a list of
elements. The list will have head of the given queue as its first element.
If the given queue is empty, then it returns an empty list.
(map func que1 que2 ...) → (Queue A)
|
| func : (A B ... B -> C) |
| que1 : (Queue A) |
| que2 : (Queue B) |
Function
map is similar to
map for lists.
(fold func init que1 que2 ...) → C
|
| func : (C A B ... B -> C) |
| init : C |
| que1 : (Queue A) |
| que2 : (Queue B) |
fold currently does not produce correct results when the
given function is non-commutative.
Examples: |
| > (define que (queue 1 2 3 4 5 6)) | | | > (queue->list (filter (λ: ([x : Integer]) (> x 5)) que)) | - : (Listof Integer) | '(6) | | > (queue->list (filter (λ: ([x : Integer]) (< x 5)) que)) | - : (Listof Integer) | '(1 2 3 4) | | > (queue->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 que1 que2 ...) → Boolean
|
| func : (A B ... B -> Boolean) |
| que1 : (Queue A) |
| que2 : (Queue B) |
(ormap func que1 que2 ...) → Boolean
|
| func : (A B ... B -> Boolean) |
| que1 : (Queue A) |
| que2 : (Queue B) |
Function
head+tail returns a pair containing the head and the tail of
the given queue.
Examples: |
| > (head+tail (queue 1 2 3 4 5)) | - : (Pairof Integer (Queue Integer)) | '(1 . #<Queue>) | | > (head+tail (build-queue 5 (λ:([x : Integer]) (* x x)))) | - : (Pairof Integer (Queue Integer)) | '(0 . #<Queue>) | | > (head+tail (empty Integer)) | head+tail: given queue is empty |
|
1.3 Implicit Queue
Queues obtained by applying the technique called
Implicit Recursive Slowdown. Provides a amortized
running time of O(1) for the operations
head, tail 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.
A implicit queue of type A.
Function
queue creates a Implicit Queue with the
given inputs.
Example: |
| > (queue 1 2 3 4 5 6) | - : (U (Shallow Positive-Byte) (Deep Positive-Byte)) | #<Deep> |
|
In the above example, the queue obtained will have 1 as its head element.
An empty queue.
Function
empty? checks if the given queue is empty or not.
Function
enqueue takes an element and a queue and enqueues
the given element into the queue.
Example: |
| > (enqueue 10 (queue 1 2 3 4 5 6)) | - : (U (Shallow Positive-Byte) (Deep Positive-Byte)) | #<Deep> |
|
In the above example, enqueue adds the element 10 to
of (queue 1 2 3 4 5 6) and returns (queue 1 2 3 4 5 6 10).
Function
head takes a queue and gives the first element in the
queue if queue is not empty else throws an error.
Examples: |
| > (head (queue 1 2 3 4 5 6)) | - : Integer [more precisely: Positive-Byte] | 1 | | > (head empty) | head: given queue is empty |
|
Function
tail takes a queue and returns a queue with rest
elements if its a non empty queue else throws an error.
Examples: |
| > (tail (queue 1 2 3 4 5 6)) | - : (U (Shallow Positive-Byte) (Deep Positive-Byte)) | #<Deep> | | > (tail empty) | tail: given queue is empty |
|
In the above example,
(tail (queue 1 2 3 4 5 6)), removes the head of
the given queue returns
(queue 2 3 4 5 6).
Function
queue->list takes a queue and returns a list of
elements. The list will have head of the given queue as its first element.
If the given queue is empty, then it returns an empty list.
(map func que1 que2 ...) → (Queue A)
|
| func : (A B ... B -> C) |
| que1 : (Queue A) |
| que2 : (Queue B) |
Function
map is similar to
map for lists.
(fold func init que1 que2 ...) → C
|
| func : (C A B ... B -> C) |
| init : C |
| que1 : (Queue A) |
| que2 : (Queue B) |
fold currently does not produce correct results when the
given function is non-commutative.
Examples: |
| > (fold + 0 (queue 1 2 3 4 5 6)) | - : Integer [more precisely: Nonnegative-Integer] | 21 | | > (fold * 1 (queue 1 2 3 4 5 6) (queue 1 2 3 4 5 6)) | - : Integer [more precisely: Positive-Integer] | 518400 |
|
Examples: |
| > (define que (queue 1 2 3 4 5 6)) | | | > (queue->list (filter (λ: ([x : Integer]) (> x 5)) que)) | - : (Listof Positive-Byte) | '(6) | | > (queue->list (filter (λ: ([x : Integer]) (< x 5)) que)) | - : (Listof Positive-Byte) | '(1 2 3 4) | | > (queue->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 que1 que2 ...) → Boolean
|
| func : (A B ... B -> Boolean) |
| que1 : (Queue A) |
| que2 : (Queue B) |
(ormap func que1 que2 ...) → Boolean
|
| func : (A B ... B -> Boolean) |
| que1 : (Queue A) |
| que2 : (Queue B) |
Function
head+tail returns a pair containing the head and the tail of
the given queue.
Examples: |
| > (head+tail (queue 1 2 3 4 5)) | - : (Pairof Positive-Byte (U (Shallow Positive-Byte) (Deep Positive-Byte))) | '(1 . #<Deep>) | | > (head+tail (build-queue 5 (λ:([x : Integer]) (* x x)))) | - : (Pairof Integer (U (Shallow Integer) (Deep Integer))) | '(0 . #<Deep>) | | > (head+tail empty) | head: given queue is empty |
|
1.4 Bootstraped Queue
Bootstrapped Queue use a structural bootstrapping technique called
Structural Decomposition. The data structure gives a worst
case running time of O(1) for the operation
head and O(log*(n)) for
tail and enqueue. Internally uses Physicist’s Queue.
A bootstrapped queue of type A.
Function
queue creates a Bootstraped Queue with the
given inputs.
Example: |
| > (queue 1 2 3 4 5 6) | - : (U Null (IntQue Integer)) | #<IntQue> |
|
In the above example, the queue obtained will have 1 as its first element.
An empty queue.
Function
empty? checks if the given queue is empty or not.
Function
enqueue takes an element and a queue and enqueues
the given element into the queue.
Example: |
| > (enqueue 10 (queue 1 2 3 4 5 6)) | - : (U Null (IntQue Integer)) | #<IntQue> |
|
In the above example, (enqueue 10 (queue 1 2 3 4 5 6)) adds the
10 to the queue (queue 1 2 3 4 5 6). 10 as its last element.
Function
head takes a queue and gives the first element in the
queue if queue is not empty else throws an error.
Function
tail takes a queue and returns the same queue without
the first element of the given queue if its a non empty queue else throws an
error.
Examples: |
| > (tail (queue 1 2 3 4 5 6)) | - : (U Null (IntQue Integer)) | #<IntQue> | | > (tail empty) | tail: given queue is empty |
|
In the above example, (tail (queue 1 2 3 4 5 6)), removes the head of
the given queue returns (queue 2 3 4 5 6).
Function
queue->list takes a queue and returns a list of
elements. The list will have head of the given queue as its first element.
If the given queue is empty, then it returns an empty list.
(map func que1 que2 ...) → (Queue A)
|
| func : (A B ... B -> C) |
| que1 : (Queue A) |
| que2 : (Queue B) |
Function
map is similar to
map for lists.
(fold func init que1 que2 ...) → C
|
| func : (C A B ... B -> C) |
| init : C |
| que1 : (Queue A) |
| que2 : (Queue B) |
fold currently does not produce correct results when the
given function is non-commutative.
Examples: |
| > (define que (queue 1 2 3 4 5 6)) | | | > (queue->list (filter (λ: ([x : Integer]) (> x 5)) que)) | - : (Listof Integer) | '(6) | | > (queue->list (filter (λ: ([x : Integer]) (< x 5)) que)) | - : (Listof Integer) | '(1 2 3 4) | | > (queue->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 que1 que2 ...) → Boolean
|
| func : (A B ... B -> Boolean) |
| que1 : (Queue A) |
| que2 : (Queue B) |
(ormap func que1 que2 ...) → Boolean
|
| func : (A B ... B -> Boolean) |
| que1 : (Queue A) |
| que2 : (Queue B) |
Function
head+tail returns a pair containing the head and the tail of
the given queue.
Examples: |
| > (head+tail (queue 1 2 3 4 5)) | - : (Pairof Integer (U Null (IntQue Integer))) | '(1 . #<IntQue>) | | > (head+tail (build-queue 5 (λ:([x : Integer]) (* x x)))) | - : (Pairof Integer (U Null (IntQue Integer))) | '(0 . #<IntQue>) | | > (head+tail empty) | head+tail: given queue is empty |
|
1.5 Real-Time Queue
Real-Time Queues eliminate the amortization by employing laziness and
a technique called Scheduling. The data structure gives a worst
case running time of O(1) for the operations
head, tail and enqueue.
A real-time queue of type A.
Function
queue creates a Real-Time Queue with the
given inputs.
Example: |
| > (queue 1 2 3 4 5 6) | - : (Queue Integer) | #<Queue> |
|
In the above example, the queue obtained will have 1 as its first element.
An empty queue.
Examples: |
| > (empty Nothing) | - : (Queue Nothing) | #<Queue> | | > (empty Integer) | - : (Queue Integer) | #<Queue> |
|
Function
empty? checks if the given queue is empty or not.
Function
enqueue takes an element and a queue and enqueues
the given element into the queue.
Example: |
| > (enqueue 10 (queue 1 2 3 4 5 6)) | - : (Queue Integer) | #<Queue> |
|
In the above example, (enqueue 10 que) adds 10 to the end of
(queue 1 2 3 4 5 6) and returns (queue 1 2 3 4 5 6 10).
Function
head takes a queue and gives the first element in the
queue if queue is not empty else throws an error.
Examples: |
| > (head (queue 1 2 3 4 5 6)) | - : Integer | 1 | | > (head (empty Integer)) | head: given queue is empty |
|
Function
tail takes a queue and returns the same queue without
head element of the given queue if its a non empty queue else throws an error.
Examples: |
| > (tail (queue 1 2 3 4 5 6)) | - : (Queue Integer) | #<Queue> | | > (tail (empty Integer)) | tail: given queue is empty |
|
In the above example, (tail (queue 1 2 3 4 5 6)), returns
(queue 2 3 4 5 6).
Function
queue->list takes a queue and returns a list of
elements. The list will have head of the given queue as its first element.
If the given queue is empty, then it returns an empty list.
(map func que1 que2 ...) → (Queue A)
|
| func : (A B ... B -> C) |
| que1 : (Queue A) |
| que2 : (Queue B) |
Function
map is similar to
map for lists.
(fold func init que1 que2 ...) → C
|
| func : (C A B ... B -> C) |
| init : C |
| que1 : (Queue A) |
| que2 : (Queue B) |
fold currently does not produce correct results when the
given function is non-commutative.
Examples: |
| > (define que (queue 1 2 3 4 5 6)) | | | > (queue->list (filter (λ: ([x : Integer]) (> x 5)) que)) | - : (Listof Integer) | '(6) | | > (queue->list (filter (λ: ([x : Integer]) (< x 5)) que)) | - : (Listof Integer) | '(1 2 3 4) | | > (queue->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 que1 que2 ...) → Boolean
|
| func : (A B ... B -> Boolean) |
| que1 : (Queue A) |
| que2 : (Queue B) |
(ormap func que1 que2 ...) → Boolean
|
| func : (A B ... B -> Boolean) |
| que1 : (Queue A) |
| que2 : (Queue B) |
Function
head+tail returns a pair containing the head and the tail of
the given queue.
Examples: |
| > (head+tail (queue 1 2 3 4 5)) | - : (Pairof Integer (Queue Integer)) | '(1 . #<Queue>) | | > (head+tail (build-queue 5 (λ:([x : Integer]) (* x x)))) | - : (Pairof Integer (Queue Integer)) | '(0 . #<Queue>) | | > (head+tail (empty Integer)) | head+tail: given queue is empty |
|
1.6 Hood-Melville Queue
Similar to real-time queues in many ways. But the implementation is
much more complicated than Real-Time Queue. Uses a technique called
Global Rebuilding. The data structure gives a worst case
running time of O(1) for the operations
head, tail and enqueue.
A Hood-Melville queue of type A.
Function
queue creates a Hood-Melville with the
given inputs.
Example: |
| > (queue 1 2 3 4 5 6) | - : (Queue Positive-Byte) | #<Queue> |
|
In the above example, the queue obtained will have 1 as its head element.
An empty queue.
Function
empty? checks if the given queue is empty or not.
Function
enqueue takes an element and a queue and enqueues
the given element into the queue.
Example: |
| > (enqueue 10 (queue 1 2 3 4 5 6)) | - : (Queue Positive-Byte) | #<Queue> |
|
In the above example, enqueue adds the element 10 to
(queue 1 2 3 4 5 6) and returns (queue 1 2 3 4 5 6 10).
Function
head takes a queue and gives the first element in the
queue if queue is not empty else throws an error.
Examples: |
| > (head (queue 1 2 3 4 5 6)) | - : Integer [more precisely: Positive-Byte] | 1 | | > (head empty) | head: given queue is empty |
|
Function
tail takes a queue and returns a queue with rest
elements if its a non empty queue else throws an error.
Examples: |
| > (tail (queue 1 2 3 4 5 6)) | - : (Queue Positive-Byte) | #<Queue> | | > (tail empty) | tail: given queue is empty |
|
In the above example, (tail (queue 1 2 3 4 5 6)), returns
(queue 2 3 4 5 6).
Function
queue->list takes a queue and returns a list of
elements. The list will have head of the given queue as its first element.
If the given queue is empty, then it returns an empty list.
For
(map func que1 que2 ...) → (Queue A)
|
| func : (A B ... B -> C) |
| que1 : (Queue A) |
| que2 : (Queue B) |
Function
map is similar to
map for lists.
(fold func init que1 que2 ...) → C
|
| func : (C A B ... B -> C) |
| init : C |
| que1 : (Queue A) |
| que2 : (Queue B) |
fold currently does not produce correct results when the
given function is non-commutative.
Examples: |
| > (fold + 0 (queue 1 2 3 4 5 6)) | - : Integer [more precisely: Nonnegative-Integer] | 21 | | > (fold * 1 (queue 1 2 3 4 5 6) (queue 1 2 3 4 5 6)) | - : Integer [more precisely: Positive-Integer] | 518400 |
|
Examples: |
| > (define que (queue 1 2 3 4 5 6)) | | | > (queue->list (filter (λ: ([x : Integer]) (> x 5)) que)) | - : (Listof Positive-Byte) | '(6) | | > (queue->list (filter (λ: ([x : Integer]) (< x 5)) que)) | - : (Listof Positive-Byte) | '(1 2 3 4) | | > (queue->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 que1 que2 ...) → Boolean
|
| func : (A B ... B -> Boolean) |
| que1 : (Queue A) |
| que2 : (Queue B) |
(ormap func que1 que2 ...) → Boolean
|
| func : (A B ... B -> Boolean) |
| que1 : (Queue A) |
| que2 : (Queue B) |
Function
head+tail returns a pair containing the head and the tail of
the given queue.
Examples: |
| > (head+tail (queue 1 2 3 4 5)) | - : (Pairof Positive-Byte (Queue Positive-Byte)) | '(1 . #<Queue>) | | > (head+tail (build-queue 5 (λ:([x : Integer]) (* x x)))) | - : (Pairof Integer (Queue Integer)) | '(0 . #<Queue>) | | > (head+tail empty) | head+tail: given queue is empty |
|