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.1Banker’s Queue

1.2Physicist’s Queue

1.3Implicit Queue

1.4Bootstraped Queue

1.5Real-Time Queue

1.6Hood-Melville Queue

1.1Banker’s Queue🔗 i

(require pfds/queue/bankers ) package: pfds

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

syntax
( Queue A)

A banker’s queue of type A.

procedure
( queue a...)→(Queue A)
a:A

Function queue creates a Banker’s Queue with the given inputs.

Example:

> (queue 123456)

- : #(struct:Queue

((Rec

g292706

(U (Pairof Positive-Byte g292706) (Promiseof g292706) Null))

Integer

(Listof Positive-Byte)

Integer))

#<Queue>

In the above example, the queue obtained will have 1 as its head element.

procedure
( empty t)→(Queue Nothing)
t:A

An empty queue instantiated to type t.

Examples:

> (empty Nothing)

- : (Queue Nothing)

#<Queue>
> (empty Integer)

- : (Queue Integer)

#<Queue>

procedure
( empty? que)→Boolean
que:(Queue A)

Function empty? checks if the given queue is empty or not.

Examples:

> (empty? (queue 123456))

- : Boolean

#f
> (empty? (empty Integer))

- : Boolean

#t

procedure
( enqueue aque)→(Queue A)
a:A
que:(Queue A)

Function enqueue takes an element and a queue and adds the given element into the queue .

Example:

> (enqueue 10(queue 456))

- : #(struct:Queue

((Rec

g292784

(U (Pairof Positive-Byte g292784) (Promiseof g292784) Null))

Integer

(Listof Positive-Byte)

Integer))

#<Queue>

In the above example, (enqueue 10(queue 456)) enqueues 10 to the end of the queue and returns (queue 45610).

procedure
( head que)→A
que:(Queue A)

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 104312))

- : Integer [more precisely: Positive-Byte]

10
> (head (empty Integer))

head: given queue is empty

procedure
( tail que)→(Queue A)
que:(Queue A)

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 456))

- : #(struct:Queue

((Rec

g292844

(U (Pairof Positive-Byte g292844) (Promiseof g292844) Null))

Integer

(Listof Positive-Byte)

Integer))

#<Queue>
> (tail (empty Integer))

tail: given queue is empty

In the above example, (tail (queue 456)), returns (queue 56).

procedure
( queue->list que)→(Queue A)
que:(Queue A)

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.

Examples:

> (queue->list (queue 102344156))

- : (Listof Positive-Byte)

'(10 2 34 4 15 6)
> (queue->list (empty Integer))

- : (Listof Integer)

'()

procedure
( map funcque1que2...)→(Queue A)
func:(AB...B->C)
que1:(Queue A)
que2:(Queue B)

Function map is similar to map for lists.

Examples:

> (queue->list (map add1(queue 123456)))

- : (Listof Positive-Index)

'(2 3 4 5 6 7)
> (queue->list (map *(queue 123456)(queue 123456)))

- : (Listof Positive-Index)

'(1 4 9 16 25 36)

procedure
( fold funcinitque1que2...)→C
func:(CAB...B->C)
init:C
que1:(Queue A)
que2:(Queue B)

Function fold is similar to foldl or foldr

fold currently does not produce correct results when the given function is non-commutative.

Examples:

> (fold +0(queue 123456))

- : Integer [more precisely: Nonnegative-Integer]

21
> (fold *1(queue 123456)(queue 123456))

- : Integer [more precisely: Positive-Integer]

518400

procedure
( filter funcque)→(Queue A)
func:(A->Boolean)
que:(Queue A)

Function filter is similar to filter .

Examples:

> (defineque(queue 123456))
> (queue->list (filter (λ:([x:Integer])(>x5))que))

- : (Listof Positive-Byte)

'(6)
> (queue->list (filter (λ:([x:Integer])(<x5))que))

- : (Listof Positive-Byte)

'(1 2 3 4)
> (queue->list (filter (λ:([x:Integer])(<=x5))que))

- : (Listof Positive-Byte)

'(1 2 3 4 5)

procedure
( remove funcque)→(Queue A)
func:(A->Boolean)
que:(Queue A)

Function remove is similar to filter but remove removes the elements which match the predicate.

Examples:

> (queue->list (remove (λ:([x:Integer])(>x5))
(queue 123456)))

- : (Listof Positive-Byte)

'(1 2 3 4 5)

> (queue->list (remove (λ:([x:Integer])(<x5))
(queue 123456)))

- : (Listof Positive-Byte)

'(5 6)

> (queue->list (remove (λ:([x:Integer])(<=x5))
(queue 123456)))

- : (Listof Positive-Byte)

'(6)

procedure
( andmap funcque1que2...)→Boolean
func:(AB...B->Boolean)
que1:(Queue A)
que2:(Queue B)

Function andmap is similar to andmap .

Examples:

> (andmap even?(queue 123456))

- : Boolean

#f
> (andmap odd?(queue 123456))

- : Boolean

#f
> (andmap positive?(queue 123456))

- : Boolean

#t
> (andmap negative?(queue -1-2))

- : Boolean

#t

procedure
( ormap funcque1que2...)→Boolean
func:(AB...B->Boolean)
que1:(Queue A)
que2:(Queue B)

Function ormap is similar to ormap .

Examples:

> (ormap even?(queue 123456))

- : Boolean

#t
> (ormap odd?(queue 123456))

- : Boolean

#t
> (ormap positive?(queue -1-234-56))

- : Boolean

#t
> (ormap negative?(queue 1-2))

- : Boolean

#t

procedure
( build-queue sizefunc)→(Queue A)
size:Natural
func:(Natural->A)

Function build-queue is similar to build-list .

Examples:

> (queue->list (build-queue 5(λ:([x:Integer])(add1x))))

- : (Listof Integer)

'(1 2 3 4 5)
> (queue->list (build-queue 5(λ:([x:Integer])(*xx))))

- : (Listof Integer)

'(0 1 4 9 16)

procedure
( head+tail que)→(PairA(Queue A))
que:(Queue A)

Function head+tail returns a pair containing the head and the tail of the given queue.

Examples:

> (head+tail (queue 12345))

- : (Pairof

Positive-Byte

#(struct:Queue

((Rec

g293581

(U (Pairof Positive-Byte g293581) (Promiseof g293581) Null))

Integer

(Listof Positive-Byte)

Integer)))

'(1 . #<Queue>)
> (head+tail (build-queue 5(λ:([x:Integer])(*xx))))

- : (Pairof

Integer

#(struct:Queue

((Rec g293604 (U (Pairof Integer g293604) (Promiseof g293604) Null))

Integer

(Listof Integer)

Integer)))

'(0 . #<Queue>)
> (head+tail (empty Integer))

head+tail: given queue is empty

1.2Physicist’s Queue🔗 i

(require pfds/queue/physicists ) package: pfds

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.

syntax
( Queue A)

A physicist’s queue of type A.

procedure
( queue a...)→(Queue A)
a:A

Function queue creates a Physicist’s Queue with the given inputs.

Example:

> (queue 123456)

- : #(struct:Queue

((Listof Integer)

(Boxof (U (-> (Listof Integer)) (Listof Integer)))

Integer

(Listof Integer)

Integer))

#<Queue>

In the above example, the queue obtained will have 1 as its head element

procedure
( empty t)→(Queue A)
t:A

An empty queue.

procedure
( empty? que)→Boolean
que:(Queue A)

Function empty? checks if the given queue is empty or not.

Examples:

> (empty? (queue 123456))

- : Boolean

#f
> (empty? (empty Integer))

- : Boolean

#t

procedure
( enqueue aque)→(Queue A)
a:A
que:(Queue A)

Function enqueue takes an element and a queue and enqueues the given element into the queue.

Example:

> (enqueue 10(queue 123456))

- : #(struct:Queue

((Listof Integer)

(Boxof (U (-> (Listof Integer)) (Listof Integer)))

Integer

(Listof Integer)

Integer))

#<Queue>

In the above example, enqueue adds the element 10 to (queue 123456) and returns (queue 12345610).

procedure
( head que)→A
que:(Queue A)

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 123456))

- : Integer

1
> (head (empty Integer))

head: given queue is empty

procedure
( tail que)→(Queue A)
que:(Queue A)

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 123456))

- : #(struct:Queue

((Listof Integer)

(Boxof (U (-> (Listof Integer)) (Listof Integer)))

Integer

(Listof Integer)

Integer))

#<Queue>
> (tail (empty Integer))

tail: given queue is empty

In the above example, (tail (queue 123456)), returns (queue 23456).

procedure
( queue->list que)→(Queue A)
que:(Queue A)

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.

Examples:

> (queue->list (queue 102344156))

- : (Listof Integer)

'(10 2 34 4 15 6)
> (queue->list (empty Integer))

- : (Listof Integer)

'()

procedure
( map funcque1que2...)→(Queue A)
func:(AB...B->C)
que1:(Queue A)
que2:(Queue B)

Function map is similar to map for lists.

Examples:

> (queue->list (map add1(queue 123456)))

- : (Listof Integer)

'(2 3 4 5 6 7)
> (queue->list (map *(queue 123456)(queue 123456)))

- : (Listof Integer)

'(1 4 9 16 25 36)

procedure
( fold funcinitque1que2...)→C
func:(CAB...B->C)
init:C
que1:(Queue A)
que2:(Queue B)

Function fold is similar to foldl or foldr

fold currently does not produce correct results when the given function is non-commutative.

Examples:

> (fold +0(queue 123456))

- : Integer

21
> (fold *1(queue 123456)(queue 123456))

- : Integer

518400

procedure
( filter funcque)→(Queue A)
func:(A->Boolean)
que:(Queue A)

Function filter is similar to filter .

Examples:

> (defineque(queue 123456))
> (queue->list (filter (λ:([x:Integer])(>x5))que))

- : (Listof Integer)

'(6)
> (queue->list (filter (λ:([x:Integer])(<x5))que))

- : (Listof Integer)

'(1 2 3 4)
> (queue->list (filter (λ:([x:Integer])(<=x5))que))

- : (Listof Integer)

'(1 2 3 4 5)

procedure
( remove funcque)→(Queue A)
func:(A->Boolean)
que:(Queue A)

Function remove is similar to filter but remove removes the elements which match the predicate.

Examples:

> (queue->list (remove (λ:([x:Integer])(>x5))
(queue 123456)))

- : (Listof Integer)

'(1 2 3 4 5)

> (queue->list (remove (λ:([x:Integer])(<x5))
(queue 123456)))

- : (Listof Integer)

'(5 6)

> (queue->list (remove (λ:([x:Integer])(<=x5))
(queue 123456)))

- : (Listof Integer)

'(6)

procedure
( andmap funcque1que2...)→Boolean
func:(AB...B->Boolean)
que1:(Queue A)
que2:(Queue B)

Function andmap is similar to andmap .

Examples:

> (andmap even?(queue 123456))

- : Boolean

#f
> (andmap odd?(queue 123456))

- : Boolean

#f
> (andmap positive?(queue 123456))

- : Boolean

#t
> (andmap negative?(queue -1-2))

- : Boolean

#t

procedure
( ormap funcque1que2...)→Boolean
func:(AB...B->Boolean)
que1:(Queue A)
que2:(Queue B)

Function ormap is similar to ormap .

Examples:

> (ormap even?(queue 123456))

- : Boolean

#t
> (ormap odd?(queue 123456))

- : Boolean

#t
> (ormap positive?(queue -1-234-56))

- : Boolean

#t
> (ormap negative?(queue 1-2))

- : Boolean

#t

procedure
( build-queue sizefunc)→(Queue A)
size:Natural
func:(Natural->A)

Function build-queue is similar to build-list .

Examples:

> (queue->list (build-queue 5(λ:([x:Integer])(add1x))))

- : (Listof Integer)

'(1 2 3 4 5)
> (queue->list (build-queue 5(λ:([x:Integer])(*xx))))

- : (Listof Integer)

'(0 1 4 9 16)

procedure
( head+tail que)→(PairA(Queue A))
que:(Queue A)

Function head+tail returns a pair containing the head and the tail of the given queue.

Examples:

> (head+tail (queue 12345))

- : (Pairof

Integer

#(struct:Queue

((Listof Integer)

(Boxof (U (-> (Listof Integer)) (Listof Integer)))

Integer

(Listof Integer)

Integer)))

'(1 . #<Queue>)
> (head+tail (build-queue 5(λ:([x:Integer])(*xx))))

- : (Pairof

Integer

#(struct:Queue

((Listof Integer)

(Boxof (U (-> (Listof Integer)) (Listof Integer)))

Integer

(Listof Integer)

Integer)))

'(0 . #<Queue>)
> (head+tail (empty Integer))

head+tail: given queue is empty

1.3Implicit Queue🔗 i

(require pfds/queue/implicit ) package: pfds

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.

syntax
( Queue A)

A implicit queue of type A.

procedure
( queue a...)→(Queue A)
a:A

Function queue creates a Implicit Queue with the given inputs.

Example:

> (queue 123456)

- : (U (Deep Positive-Byte) (Shallow Positive-Byte))

#<Deep>

In the above example, the queue obtained will have 1 as its head element.

value
empty :(Queue Nothing)

An empty queue.

procedure
( empty? que)→Boolean
que:(Queue A)

Function empty? checks if the given queue is empty or not.

Examples:

> (empty? (queue 123456))

- : Boolean

#f
> (empty? empty )

- : Boolean

#t

procedure
( enqueue aque)→(Queue A)
a:A
que:(Queue A)

Functionenqueue takes an element and a queue and enqueues the given element into the queue.

Example:

> (enqueue 10(queue 123456))

- : (U (Deep Positive-Byte) (Shallow Positive-Byte))

#<Deep>

In the above example, enqueue adds the element 10 to of (queue 123456) and returns (queue 12345610).

procedure
( head que)→A
que:(Queue A)

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 123456))

- : Integer [more precisely: Positive-Byte]

1
> (head empty )

head: given queue is empty

procedure
( tail que)→(Queue A)
que:(Queue A)

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 123456))

- : (U (Deep Positive-Byte) (Shallow Positive-Byte))

#<Deep>
> (tail empty )

tail: given queue is empty

In the above example, (tail (queue 123456)), removes the head of the given queue returns (queue 23456).

procedure
( queue->list que)→(Queue A)
que:(Queue A)

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.

Examples:

> (queue->list (queue 102344156))

- : (Listof Positive-Byte)

'(10 2 34 4 15 6)
> (queue->list empty )

- : (Listof Nothing)

'()

procedure
( map funcque1que2...)→(Queue A)
func:(AB...B->C)
que1:(Queue A)
que2:(Queue B)

Function map is similar to map for lists.

Examples:

> (queue->list (map add1(queue 123456)))

- : (Listof Positive-Index)

'(2 3 4 5 6 7)
> (queue->list (map *(queue 123456)(queue 123456)))

- : (Listof Positive-Index)

'(1 4 9 16 25 36)

procedure
( fold funcinitque1que2...)→C
func:(CAB...B->C)
init:C
que1:(Queue A)
que2:(Queue B)

Function fold is similar to foldl or foldr

fold currently does not produce correct results when the given function is non-commutative.

Examples:

> (fold +0(queue 123456))

- : Integer [more precisely: Nonnegative-Integer]

21
> (fold *1(queue 123456)(queue 123456))

- : Integer [more precisely: Positive-Integer]

518400

procedure
( filter funcque)→(Queue A)
func:(A->Boolean)
que:(Queue A)

Function filter is similar to filter .

Examples:

> (defineque(queue 123456))
> (queue->list (filter (λ:([x:Integer])(>x5))que))

- : (Listof Positive-Byte)

'(6)
> (queue->list (filter (λ:([x:Integer])(<x5))que))

- : (Listof Positive-Byte)

'(1 2 3 4)
> (queue->list (filter (λ:([x:Integer])(<=x5))que))

- : (Listof Positive-Byte)

'(1 2 3 4 5)

procedure
( remove funcque)→(Queue A)
func:(A->Boolean)
que:(Queue A)

Function remove is similar to filter but remove removes the elements which match the predicate.

Examples:

> (queue->list (remove (λ:([x:Integer])(>x5))
(queue 123456)))

- : (Listof Positive-Byte)

'(1 2 3 4 5)

> (queue->list (remove (λ:([x:Integer])(<x5))
(queue 123456)))

- : (Listof Positive-Byte)

'(5 6)

> (queue->list (remove (λ:([x:Integer])(<=x5))
(queue 123456)))

- : (Listof Positive-Byte)

'(6)

procedure
( andmap funcque1que2...)→Boolean
func:(AB...B->Boolean)
que1:(Queue A)
que2:(Queue B)

Function andmap is similar to andmap .

Examples:

> (andmap even?(queue 123456))

- : Boolean

#f
> (andmap odd?(queue 123456))

- : Boolean

#f
> (andmap positive?(queue 123456))

- : Boolean

#t
> (andmap negative?(queue -1-2))

- : Boolean

#t

procedure
( ormap funcque1que2...)→Boolean
func:(AB...B->Boolean)
que1:(Queue A)
que2:(Queue B)

Function ormap is similar to ormap .

Examples:

> (ormap even?(queue 123456))

- : Boolean

#t
> (ormap odd?(queue 123456))

- : Boolean

#t
> (ormap positive?(queue -1-234-56))

- : Boolean

#t
> (ormap negative?(queue 1-2))

- : Boolean

#t

procedure
( build-queue sizefunc)→(Queue A)
size:Natural
func:(Natural->A)

Function build-queue is similar to build-list .

Examples:

> (queue->list (build-queue 5(λ:([x:Integer])(add1x))))

- : (Listof Integer)

'(1 2 3 4 5)
> (queue->list (build-queue 5(λ:([x:Integer])(*xx))))

- : (Listof Integer)

'(0 1 4 9 16)

procedure
( head+tail que)→(PairA(Queue A))
que:(Queue A)

Function head+tail returns a pair containing the head and the tail of the given queue.

Examples:

> (head+tail (queue 12345))

- : (Pairof Positive-Byte (U (Deep Positive-Byte) (Shallow Positive-Byte)))

'(1 . #<Deep>)
> (head+tail (build-queue 5(λ:([x:Integer])(*xx))))

- : (Pairof Integer (U (Deep Integer) (Shallow Integer)))

'(0 . #<Deep>)
> (head+tail empty )

head: given queue is empty

1.4Bootstraped Queue🔗 i

(require pfds/queue/bootstrapped ) package: pfds

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.

syntax
( Queue A)

A bootstrapped queue of type A.

procedure
( queue a...)→(Queue A)
a:A

Function queue creates a Bootstraped Queue with the given inputs.

Example:

> (queue 123456)

- : (U (IntQue Integer) Null)

#<IntQue>

In the above example, the queue obtained will have 1 as its first element.

value
empty :(Queue Nothing)

An empty queue.

procedure
( empty? que)→Boolean
que:(Queue A)

Function empty? checks if the given queue is empty or not.

Examples:

> (empty? (queue 123456))

- : Boolean

#f
> (empty? empty )

- : Boolean

#t

procedure
( enqueue aque)→(Queue A)
a:A
que:(Queue A)

Function enqueue takes an element and a queue and enqueues the given element into the queue.

Example:

> (enqueue 10(queue 123456))

- : (U (IntQue Integer) Null)

#<IntQue>

In the above example, (enqueue 10(queue 123456)) adds the 10 to the queue (queue 123456). 10 as its last element.

procedure
( head que)→A
que:(Queue A)

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 123456))

- : Integer

1
> (head empty )

head: given queue is empty

procedure
( tail que)→(Queue A)
que:(Queue A)

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 123456))

- : (U (IntQue Integer) Null)

#<IntQue>
> (tail empty )

tail: given queue is empty

In the above example, (tail (queue 123456)), removes the head of the given queue returns (queue 23456).

procedure
( queue->list que)→(Queue A)
que:(Queue A)

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.

Examples:

> (queue->list (queue 102344156))

- : (Listof Integer)

'(10 2 34 4 15 6)
> (queue->list empty )

- : (Listof Nothing)

'()

procedure
( map funcque1que2...)→(Queue A)
func:(AB...B->C)
que1:(Queue A)
que2:(Queue B)

Function map is similar to map for lists.

Examples:

> (queue->list (map add1(queue 123456)))

- : (Listof Integer)

'(2 3 4 5 6 7)
> (queue->list (map *(queue 123456)(queue 123456)))

- : (Listof Integer)

'(1 4 9 16 25 36)

procedure
( fold funcinitque1que2...)→C
func:(CAB...B->C)
init:C
que1:(Queue A)
que2:(Queue B)

Function fold is similar to foldl or foldr

fold currently does not produce correct results when the given function is non-commutative.

Examples:

> (fold +0(queue 123456))

- : Integer

21
> (fold *1(queue 123456)(queue 123456))

- : Integer

518400

procedure
( filter funcque)→(Queue A)
func:(A->Boolean)
que:(Queue A)

Function filter is similar to filter .

Examples:

> (defineque(queue 123456))
> (queue->list (filter (λ:([x:Integer])(>x5))que))

- : (Listof Integer)

'(6)
> (queue->list (filter (λ:([x:Integer])(<x5))que))

- : (Listof Integer)

'(1 2 3 4)
> (queue->list (filter (λ:([x:Integer])(<=x5))que))

- : (Listof Integer)

'(1 2 3 4 5)

procedure
( remove funcque)→(Queue A)
func:(A->Boolean)
que:(Queue A)

Function remove is similar to filter but remove removes the elements which match the predicate.

Examples:

> (queue->list (remove (λ:([x:Integer])(>x5))
(queue 123456)))

- : (Listof Integer)

'(1 2 3 4 5)

> (queue->list (remove (λ:([x:Integer])(<x5))
(queue 123456)))

- : (Listof Integer)

'(5 6)

> (queue->list (remove (λ:([x:Integer])(<=x5))
(queue 123456)))

- : (Listof Integer)

'(6)

procedure
( andmap funcque1que2...)→Boolean
func:(AB...B->Boolean)
que1:(Queue A)
que2:(Queue B)

Function andmap is similar to andmap .

Examples:

> (andmap even?(queue 123456))

- : Boolean

#f
> (andmap odd?(queue 123456))

- : Boolean

#f
> (andmap positive?(queue 123456))

- : Boolean

#t
> (andmap negative?(queue -1-2))

- : Boolean

#t

procedure
( ormap funcque1que2...)→Boolean
func:(AB...B->Boolean)
que1:(Queue A)
que2:(Queue B)

Function ormap is similar to ormap .

Examples:

> (ormap even?(queue 123456))

- : Boolean

#t
> (ormap odd?(queue 123456))

- : Boolean

#t
> (ormap positive?(queue -1-234-56))

- : Boolean

#t
> (ormap negative?(queue 1-2))

- : Boolean

#t

procedure
( build-queue sizefunc)→(Queue A)
size:Natural
func:(Natural->A)

Function build-queue is similar to build-list .

Examples:

> (queue->list (build-queue 5(λ:([x:Integer])(add1x))))

- : (Listof Integer)

'(1 2 3 4 5)
> (queue->list (build-queue 5(λ:([x:Integer])(*xx))))

- : (Listof Integer)

'(0 1 4 9 16)

procedure
( head+tail que)→(PairA(Queue A))
que:(Queue A)

Function head+tail returns a pair containing the head and the tail of the given queue.

Examples:

> (head+tail (queue 12345))

- : (Pairof Integer (U (IntQue Integer) Null))

'(1 . #<IntQue>)
> (head+tail (build-queue 5(λ:([x:Integer])(*xx))))

- : (Pairof Integer (U (IntQue Integer) Null))

'(0 . #<IntQue>)
> (head+tail empty )

head+tail: given queue is empty

1.5Real-Time Queue🔗 i

(require pfds/queue/real-time ) package: pfds

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 .

syntax
( Queue A)

A real-time queue of type A.

procedure
( queue a...)→(Queue A)
a:A

Function queue creates a Real-Time Queue with the given inputs.

Example:

> (queue 123456)

- : #(struct:Queue

((Rec

g301744

(U (Boxof (U (-> (Pairof Integer g301744)) (Pairof Integer g301744)))

Null))

(Listof Integer)

(Rec

g301747

(U (Boxof (U (-> (Pairof Integer g301747)) (Pairof Integer g301747)))

Null))))

#<Queue>

In the above example, the queue obtained will have 1 as its first element.

procedure
( empty t)→(Queue A)
t:A

An empty queue.

Examples:

> (empty Nothing)

- : (Queue Nothing)

#<Queue>
> (empty Integer)

- : (Queue Integer)

#<Queue>

procedure
( empty? que)→Boolean
que:(Queue A)

Function empty? checks if the given queue is empty or not.

Examples:

> (empty? (queue 123456))

- : Boolean

#f
> (empty? (empty Integer))

- : Boolean

#t

procedure
( enqueue aque)→(Queue A)
a:A
que:(Queue A)

Functionenqueue takes an element and a queue and enqueues the given element into the queue.

Example:

> (enqueue 10(queue 123456))

- : #(struct:Queue

((Rec

g301800

(U (Boxof (U (-> (Pairof Integer g301800)) (Pairof Integer g301800)))

Null))

(Listof Integer)

(Rec

g301803

(U (Boxof (U (-> (Pairof Integer g301803)) (Pairof Integer g301803)))

Null))))

#<Queue>

In the above example, (enqueue 10que) adds 10 to the end of (queue 123456) and returns (queue 12345610).

procedure
( head que)→A
que:(Queue A)

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 123456))

- : Integer

1
> (head (empty Integer))

head: given queue is empty

procedure
( tail que)→(Queue A)
que:(Queue A)

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 123456))

- : #(struct:Queue

((Rec

g301840

(U (Boxof (U (-> (Pairof Integer g301840)) (Pairof Integer g301840)))

Null))

(Listof Integer)

(Rec

g301843

(U (Boxof (U (-> (Pairof Integer g301843)) (Pairof Integer g301843)))

Null))))

#<Queue>
> (tail (empty Integer))

tail: given queue is empty

In the above example, (tail (queue 123456)), returns (queue 23456).

procedure
( queue->list que)→(Queue A)
que:(Queue A)

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.

Example:

> (queue->list (queue 102344156))

- : (Listof Integer)

'(10 2 34 4 15 6)

procedure
( map funcque1que2...)→(Queue A)
func:(AB...B->C)
que1:(Queue A)
que2:(Queue B)

Function map is similar to map for lists.

Examples:

> (queue->list (map add1(queue 123456)))

- : (Listof Integer)

'(2 3 4 5 6 7)
> (queue->list (map *(queue 123456)(queue 123456)))

- : (Listof Integer)

'(1 4 9 16 25 36)

procedure
( fold funcinitque1que2...)→C
func:(CAB...B->C)
init:C
que1:(Queue A)
que2:(Queue B)

Function fold is similar to foldl or foldr

fold currently does not produce correct results when the given function is non-commutative.

Examples:

> (fold +0(queue 123456))

- : Integer

21
> (fold *1(queue 123456)(queue 123456))

- : Integer

518400

procedure
( filter funcque)→(Queue A)
func:(A->Boolean)
que:(Queue A)

Function filter is similar to filter .

Examples:

> (defineque(queue 123456))
> (queue->list (filter (λ:([x:Integer])(>x5))que))

- : (Listof Integer)

'(6)
> (queue->list (filter (λ:([x:Integer])(<x5))que))

- : (Listof Integer)

'(1 2 3 4)
> (queue->list (filter (λ:([x:Integer])(<=x5))que))

- : (Listof Integer)

'(1 2 3 4 5)

procedure
( remove funcque)→(Queue A)
func:(A->Boolean)
que:(Queue A)

Function remove is similar to filter but remove removes the elements which match the predicate.

Examples:

> (queue->list (remove (λ:([x:Integer])(>x5))
(queue 123456)))

- : (Listof Integer)

'(1 2 3 4 5)

> (queue->list (remove (λ:([x:Integer])(<x5))
(queue 123456)))

- : (Listof Integer)

'(5 6)

> (queue->list (remove (λ:([x:Integer])(<=x5))
(queue 123456)))

- : (Listof Integer)

'(6)

procedure
( andmap funcque1que2...)→Boolean
func:(AB...B->Boolean)
que1:(Queue A)
que2:(Queue B)

Function andmap is similar to andmap .

Examples:

> (andmap even?(queue 123456))

- : Boolean

#f
> (andmap odd?(queue 123456))

- : Boolean

#f
> (andmap positive?(queue 123456))

- : Boolean

#t
> (andmap negative?(queue -1-2))

- : Boolean

#t

procedure
( ormap funcque1que2...)→Boolean
func:(AB...B->Boolean)
que1:(Queue A)
que2:(Queue B)

Function ormap is similar to ormap .

Examples:

> (ormap even?(queue 123456))

- : Boolean

#t
> (ormap odd?(queue 123456))

- : Boolean

#t
> (ormap positive?(queue -1-234-56))

- : Boolean

#t
> (ormap negative?(queue 1-2))

- : Boolean

#t

procedure
( build-queue sizefunc)→(Queue A)
size:Natural
func:(Natural->A)

Function build-queue is similar to build-list .

Examples:

> (queue->list (build-queue 5(λ:([x:Integer])(add1x))))

- : (Listof Integer)

'(1 2 3 4 5)
> (queue->list (build-queue 5(λ:([x:Integer])(*xx))))

- : (Listof Integer)

'(0 1 4 9 16)

procedure
( head+tail que)→(PairA(Queue A))
que:(Queue A)

Function head+tail returns a pair containing the head and the tail of the given queue.

Examples:

> (head+tail (queue 12345))

- : (Pairof

Integer

#(struct:Queue

((Rec

g302223

(U (Boxof (U (-> (Pairof Integer g302223)) (Pairof Integer g302223)))

Null))

(Listof Integer)

(Rec

g302226

(U (Boxof (U (-> (Pairof Integer g302226)) (Pairof Integer g302226)))

Null)))))

'(1 . #<Queue>)
> (head+tail (build-queue 5(λ:([x:Integer])(*xx))))

- : (Pairof

Integer

#(struct:Queue

((Rec

g302242

(U (Boxof (U (-> (Pairof Integer g302242)) (Pairof Integer g302242)))

Null))

(Listof Integer)

(Rec

g302245

(U (Boxof (U (-> (Pairof Integer g302245)) (Pairof Integer g302245)))

Null)))))

'(0 . #<Queue>)
> (head+tail (empty Integer))

head+tail: given queue is empty

1.6Hood-Melville Queue🔗 i

(require pfds/queue/hood-melville ) package: pfds

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 .

syntax
( Queue A)

A Hood-Melville queue of type A.

procedure
( queue a...)→(Queue A)
a:A

Function queue creates a Hood-Melville with the given inputs.

Example:

> (queue 123456)

- : #(struct:Queue

(Integer

(Listof Positive-Byte)

(U (Appending Positive-Byte)

(Done Positive-Byte)

(Reversing Positive-Byte)

Null)

Integer

(Listof Positive-Byte)))

#<Queue>

In the above example, the queue obtained will have 1 as its head element.

value
empty :(Queue Nothing)

An empty queue.

procedure
( empty? que)→Boolean
que:(Queue A)

Function empty? checks if the given queue is empty or not.

Examples:

> (empty? (queue 123456))

- : Boolean

#f
> (empty? empty )

- : Boolean

#t

procedure
( enqueue aque)→(Queue A)
a:A
que:(Queue A)

Function enqueue takes an element and a queue and enqueues the given element into the queue.

Example:

> (enqueue 10(queue 123456))

- : #(struct:Queue

(Integer

(Listof Positive-Byte)

(U (Appending Positive-Byte)

(Done Positive-Byte)

(Reversing Positive-Byte)

Null)

Integer

(Listof Positive-Byte)))

#<Queue>

In the above example, enqueue adds the element 10 to (queue 123456) and returns (queue 12345610).

procedure
( head que)→A
que:(Queue A)

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 123456))

- : Integer [more precisely: Positive-Byte]

1
> (head empty )

head: given queue is empty

procedure
( tail que)→(Queue A)
que:(Queue A)

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 123456))

- : #(struct:Queue

(Integer

(Listof Positive-Byte)

(U (Appending Positive-Byte)

(Done Positive-Byte)

(Reversing Positive-Byte)

Null)

Integer

(Listof Positive-Byte)))

#<Queue>
> (tail empty )

tail: given queue is empty

In the above example, (tail (queue 123456)), returns (queue 23456).

procedure
( queue->list que)→(Queue A)
que:(Queue A)

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

Examples:

> (queue->list (queue 102344156))

- : (Listof Positive-Byte)

'(10 2 34 4 15 6)
> (queue->list empty )

- : (Listof Nothing)

'()

procedure
( map funcque1que2...)→(Queue A)
func:(AB...B->C)
que1:(Queue A)
que2:(Queue B)

Function map is similar to map for lists.

Examples:

> (queue->list (map add1(queue 123456)))

- : (Listof Positive-Index)

'(2 3 4 5 6 7)
> (queue->list (map *(queue 123456)(queue 123456)))

- : (Listof Positive-Index)

'(1 4 9 16 25 36)

procedure
( fold funcinitque1que2...)→C
func:(CAB...B->C)
init:C
que1:(Queue A)
que2:(Queue B)

Function fold is similar to foldl or foldr

fold currently does not produce correct results when the given function is non-commutative.

Examples:

> (fold +0(queue 123456))

- : Integer [more precisely: Nonnegative-Integer]

21
> (fold *1(queue 123456)(queue 123456))

- : Integer [more precisely: Positive-Integer]

518400

procedure
( filter funcque)→(Queue A)
func:(A->Boolean)
que:(Queue A)

Function filter is similar to filter .

Examples:

> (defineque(queue 123456))
> (queue->list (filter (λ:([x:Integer])(>x5))que))

- : (Listof Positive-Byte)

'(6)
> (queue->list (filter (λ:([x:Integer])(<x5))que))

- : (Listof Positive-Byte)

'(1 2 3 4)
> (queue->list (filter (λ:([x:Integer])(<=x5))que))

- : (Listof Positive-Byte)

'(1 2 3 4 5)

procedure
( remove funcque)→(Queue A)
func:(A->Boolean)
que:(Queue A)

Function remove is similar to filter but remove removes the elements which match the predicate.

Examples:

> (queue->list (remove (λ:([x:Integer])(>x5))
(queue 123456)))

- : (Listof Positive-Byte)

'(1 2 3 4 5)

> (queue->list (remove (λ:([x:Integer])(<x5))
(queue 123456)))

- : (Listof Positive-Byte)

'(5 6)

> (queue->list (remove (λ:([x:Integer])(<=x5))
(queue 123456)))

- : (Listof Positive-Byte)

'(6)

procedure
( andmap funcque1que2...)→Boolean
func:(AB...B->Boolean)
que1:(Queue A)
que2:(Queue B)

Function andmap is similar to andmap .

Examples:

> (andmap even?(queue 123456))

- : Boolean

#f
> (andmap odd?(queue 123456))

- : Boolean

#f
> (andmap positive?(queue 123456))

- : Boolean

#t
> (andmap negative?(queue -1-2))

- : Boolean

#t

procedure
( ormap funcque1que2...)→Boolean
func:(AB...B->Boolean)
que1:(Queue A)
que2:(Queue B)

Function ormap is similar to ormap .

Examples:

> (ormap even?(queue 123456))

- : Boolean

#t
> (ormap odd?(queue 123456))

- : Boolean

#t
> (ormap positive?(queue -1-234-56))

- : Boolean

#t
> (ormap negative?(queue 1-2))

- : Boolean

#t

procedure
( build-queue sizefunc)→(Queue A)
size:Natural
func:(Natural->A)

Function build-queue is similar to build-list .

Examples:

> (queue->list (build-queue 5(λ:([x:Integer])(add1x))))

- : (Listof Integer)

'(1 2 3 4 5)
> (queue->list (build-queue 5(λ:([x:Integer])(*xx))))

- : (Listof Integer)

'(0 1 4 9 16)

procedure
( head+tail que)→(PairA(Queue A))
que:(Queue A)

Function head+tail returns a pair containing the head and the tail of the given queue.

Examples:

> (head+tail (queue 12345))

- : (Pairof

Positive-Byte

#(struct:Queue

(Integer

(Listof Positive-Byte)

(U (Appending Positive-Byte)

(Done Positive-Byte)

(Reversing Positive-Byte)

Null)

Integer

(Listof Positive-Byte))))

'(1 . #<Queue>)
> (head+tail (build-queue 5(λ:([x:Integer])(*xx))))

- : (Pairof

Integer

#(struct:Queue

(Integer

(Listof Integer)

(U (Appending Integer) (Done Integer) (Reversing Integer) Null)

Integer

(Listof Integer))))

'(0 . #<Queue>)
> (head+tail empty )

head+tail: given queue is empty

top ← prev up next →