1 Queues

Version: 5.0.1.6

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

1.2 Physicist’s Queue

1.3 Implicit Queue

1.4 Bootstraped Queue

1.5 Real-Time Queue

1.6 Hood-Melville Queue

1.1 Banker’s Queue

(require (planet krhari/pfds:1:5/bankers-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

(Queue A)

A banker’s queue of type A.

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

a : A

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

Example:
  > (queue 1 2 3 4 5 6)
  - : (Queue Positive-Fixnum)
  #<Queue>

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

(empty t) → (Queue A)

t : A

An empty queue instantiated to type t.

Examples:

> (empty Nothing)

- : (Queue Nothing)

#<Queue>

> (empty Integer)

- : (Queue Integer)

#<Queue>

(empty? que) → Boolean

que : (Queue A)

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

Examples:
  > (empty? (queue 1 2 3 4 5 6))
  - : Boolean
  #f
  > (empty? (empty Integer))
  - : Boolean
  #t

(enqueue a que) → (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 4 5 6))

- : (Queue Positive-Fixnum)

#<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).

(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 10 4 3 12))

- : Positive-Fixnum

> (head (empty Integer))

head: given queue is empty

(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 4 5 6))
  - : (Queue Positive-Fixnum)
  #<Queue>
  > (tail (empty Integer))
  tail: given queue is empty

In the above example, (tail (queue 4 5 6)), returns (queue 5 6).

(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 10 2 34 4 15 6))
  - : (Listof Positive-Fixnum)
  '(10 2 34 4 15 6)
  > (queue->list (empty Integer))
  - : (Listof Integer)
  '()

(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.

Examples:

> (queue->list (map add1 (queue 1 2 3 4 5 6)))

- : (Listof Exact-Positive-Integer)

'(2 3 4 5 6 7)

> (queue->list (map * (queue 1 2 3 4 5 6) (queue 1 2 3 4 5 6)))

- : (Listof Exact-Positive-Integer)

'(1 4 9 16 25 36)

(fold func init que1 que2 ...) → C

func : (C A B ... 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 1 2 3 4 5 6))
  - : Exact-Nonnegative-Integer
  21
  > (fold * 1 (queue 1 2 3 4 5 6) (queue 1 2 3 4 5 6))
  - : Exact-Positive-Integer
  518400

(filter func que) → (Queue A)

func : (A -> Boolean)

que : (Queue A)

Function filter is similar to filter.

Examples:

> (define que (queue 1 2 3 4 5 6))

> (queue->list (filter (λ: ([x : Integer]) (> x 5)) que))

- : (Listof Positive-Fixnum)

'(6)

> (queue->list (filter (λ: ([x : Integer]) (< x 5)) que))

- : (Listof Positive-Fixnum)

'(1 2 3 4)

> (queue->list (filter (λ: ([x : Integer]) (<= x 5)) que))

- : (Listof Positive-Fixnum)

'(1 2 3 4 5)

(remove func que) → (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]) (> x 5))

(queue 1 2 3 4 5 6)))

- : (Listof Positive-Fixnum)

'(1 2 3 4 5)

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

(queue 1 2 3 4 5 6)))

- : (Listof Positive-Fixnum)

'(5 6)

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

(queue 1 2 3 4 5 6)))

- : (Listof Positive-Fixnum)

'(6)

(andmap func que1 que2 ...) → Boolean

func : (A B ... B -> Boolean)

que1 : (Queue A)

que2 : (Queue B)

Function andmap is similar to andmap.

Examples:
  > (andmap even? (queue 1 2 3 4 5 6))
  - : Boolean
  #f
  > (andmap odd? (queue 1 2 3 4 5 6))
  - : Boolean
  #f
  > (andmap positive? (queue 1 2 3 4 5 6))
  - : Boolean
  #t
  > (andmap negative? (queue -1 -2))
  - : Boolean
  #t

(ormap func que1 que2 ...) → Boolean

func : (A B ... B -> Boolean)

que1 : (Queue A)

que2 : (Queue B)

Function ormap is similar to ormap.

Examples:
  > (ormap even? (queue 1 2 3 4 5 6))
  - : Boolean
  #t
  > (ormap odd? (queue 1 2 3 4 5 6))
  - : Boolean
  #t
  > (ormap positive? (queue -1 -2 3 4 -5 6))
  - : Boolean
  #t
  > (ormap negative? (queue 1 -2))
  - : Boolean
  #t

(build-queue size func) → (Queue A)

size : Natural

func : (Natural -> A)

Function build-queue is similar to build-list.

Examples:

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

- : (Listof Integer)

'(1 2 3 4 5)

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

- : (Listof Integer)

'(0 1 4 9 16)

(head+tail que) → (Pair A (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 1 2 3 4 5))

- : (Pairof Positive-Fixnum (Queue Positive-Fixnum))

'(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

(require (planet krhari/pfds:1:5/physicists-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.

(Queue A)

A physicist’s queue of type A.

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

a : A

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

Example:
  > (queue 1 2 3 4 5 6)
  - : (Queue Positive-Fixnum)
  #<Queue>

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

(empty t) → (Queue A)

t : A

An empty queue.

(empty? que) → Boolean

que : (Queue A)

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

Examples:
  > (empty? (queue 1 2 3 4 5 6))
  - : Boolean
  #f
  > (empty? (empty Integer))
  - : Boolean
  #t

(enqueue a que) → (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 1 2 3 4 5 6))

- : (Queue Positive-Fixnum)

#<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).

(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 1 2 3 4 5 6))

- : Positive-Fixnum

> (head (empty Integer))

head: given queue is empty

(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 1 2 3 4 5 6))

- : (Queue Positive-Fixnum)

#<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).

(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 10 2 34 4 15 6))
  - : (Listof Positive-Fixnum)
  '(10 2 34 4 15 6)
  > (queue->list (empty Integer))
  - : (Listof Integer)
  '()

(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.

Examples:

> (queue->list (map add1 (queue 1 2 3 4 5 6)))

- : (Listof Exact-Positive-Integer)

'(2 3 4 5 6 7)

> (queue->list (map * (queue 1 2 3 4 5 6) (queue 1 2 3 4 5 6)))

- : (Listof Exact-Positive-Integer)

'(1 4 9 16 25 36)

(fold func init que1 que2 ...) → C

func : (C A B ... 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 1 2 3 4 5 6))
  - : Exact-Nonnegative-Integer
  21
  > (fold * 1 (queue 1 2 3 4 5 6) (queue 1 2 3 4 5 6))
  - : Exact-Positive-Integer
  518400

(filter func que) → (Queue A)

func : (A -> Boolean)

que : (Queue A)

Function filter is similar to filter.

Examples:

> (define que (queue 1 2 3 4 5 6))

> (queue->list (filter (λ: ([x : Integer]) (> x 5)) que))

- : (Listof Positive-Fixnum)

'(6)

> (queue->list (filter (λ: ([x : Integer]) (< x 5)) que))

- : (Listof Positive-Fixnum)

'(1 2 3 4)

> (queue->list (filter (λ: ([x : Integer]) (<= x 5)) que))

- : (Listof Positive-Fixnum)

'(1 2 3 4 5)

(remove func que) → (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]) (> x 5))

(queue 1 2 3 4 5 6)))

- : (Listof Positive-Fixnum)

'(1 2 3 4 5)

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

(queue 1 2 3 4 5 6)))

- : (Listof Positive-Fixnum)

'(5 6)

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

(queue 1 2 3 4 5 6)))

- : (Listof Positive-Fixnum)

'(6)

(andmap func que1 que2 ...) → Boolean

func : (A B ... B -> Boolean)

que1 : (Queue A)

que2 : (Queue B)

Function andmap is similar to andmap.

(ormap func que1 que2 ...) → Boolean

func : (A B ... B -> Boolean)

que1 : (Queue A)

que2 : (Queue B)

Function ormap is similar to ormap.

(build-queue size func) → (Queue A)

size : Natural

func : (Natural -> A)

Function build-queue is similar to build-list.

Examples:

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

- : (Listof Integer)

'(1 2 3 4 5)

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

- : (Listof Integer)

'(0 1 4 9 16)

(head+tail que) → (Pair A (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 1 2 3 4 5))

- : (Pairof Positive-Fixnum (Queue Positive-Fixnum))

'(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

(require (planet krhari/pfds:1:5/implicitqueue))

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.

(Queue A)

A implicit queue of type A.

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

a : A

Function queue creates a Implicit Queue with the given inputs.

Example:

> (queue 1 2 3 4 5 6)

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

#<Deep>

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

empty : (Queue Nothing)

An empty queue.

(empty? que) → Boolean

que : (Queue A)

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

Examples:
  > (empty? (queue 1 2 3 4 5 6))
  - : Boolean
  #f
  > (empty? empty)
  - : Boolean
  #t

(enqueue a que) → (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 1 2 3 4 5 6))

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

#<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).

(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 1 2 3 4 5 6))

- : Positive-Fixnum

> (head empty)

head: given queue is empty

(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 1 2 3 4 5 6))

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

#<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).

(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 10 2 34 4 15 6))
  - : (Listof Positive-Fixnum)
  '(10 2 34 4 15 6)
  > (queue->list empty)
  - : (Listof Nothing)
  '()

(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.

Examples:

> (queue->list (map add1 (queue 1 2 3 4 5 6)))

- : (Listof Exact-Positive-Integer)

'(2 3 4 5 6 7)

> (queue->list (map * (queue 1 2 3 4 5 6) (queue 1 2 3 4 5 6)))

- : (Listof Exact-Positive-Integer)

'(1 4 9 16 25 36)

(fold func init que1 que2 ...) → C

func : (C A B ... 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 1 2 3 4 5 6))
  - : Exact-Nonnegative-Integer
  21
  > (fold * 1 (queue 1 2 3 4 5 6) (queue 1 2 3 4 5 6))
  - : Exact-Positive-Integer
  518400

(filter func que) → (Queue A)

func : (A -> Boolean)

que : (Queue A)

Function filter is similar to filter.

Examples:

> (define que (queue 1 2 3 4 5 6))

> (queue->list (filter (λ: ([x : Integer]) (> x 5)) que))

- : (Listof Positive-Fixnum)

'(6)

> (queue->list (filter (λ: ([x : Integer]) (< x 5)) que))

- : (Listof Positive-Fixnum)

'(1 2 3 4)

> (queue->list (filter (λ: ([x : Integer]) (<= x 5)) que))

- : (Listof Positive-Fixnum)

'(1 2 3 4 5)

(remove func que) → (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]) (> x 5))

(queue 1 2 3 4 5 6)))

- : (Listof Positive-Fixnum)

'(1 2 3 4 5)

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

(queue 1 2 3 4 5 6)))

- : (Listof Positive-Fixnum)

'(5 6)

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

(queue 1 2 3 4 5 6)))

- : (Listof Positive-Fixnum)

'(6)

(andmap func que1 que2 ...) → Boolean

func : (A B ... B -> Boolean)

que1 : (Queue A)

que2 : (Queue B)

Function andmap is similar to andmap.

(ormap func que1 que2 ...) → Boolean

func : (A B ... B -> Boolean)

que1 : (Queue A)

que2 : (Queue B)

Function ormap is similar to ormap.

(build-queue size func) → (Queue A)

size : Natural

func : (Natural -> A)

Function build-queue is similar to build-list.

Examples:

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

- : (Listof Integer)

'(1 2 3 4 5)

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

- : (Listof Integer)

'(0 1 4 9 16)

(head+tail que) → (Pair A (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 1 2 3 4 5))

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

'(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

(require (planet krhari/pfds:1:5/bootstrapedqueue))

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.

(Queue A)

A bootstrapped queue of type A.

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

a : A

Function queue creates a Bootstraped Queue with the given inputs.

Example:

> (queue 1 2 3 4 5 6)

- : (U Null (IntQue Positive-Fixnum))

#<IntQue>

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

empty : (Queue Nothing)

An empty queue.

(empty? que) → Boolean

que : (Queue A)

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

Examples:
  > (empty? (queue 1 2 3 4 5 6))
  - : Boolean
  #f
  > (empty? empty)
  - : Boolean
  #t

(enqueue a que) → (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 1 2 3 4 5 6))

- : (U Null (IntQue Positive-Fixnum))

#<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.

(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 1 2 3 4 5 6))

- : Positive-Fixnum

> (head empty)

head: given queue is empty

(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 1 2 3 4 5 6))

- : (U Null (IntQue Positive-Fixnum))

#<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).

(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 10 2 34 4 15 6))
  - : (Listof Positive-Fixnum)
  '(10 2 34 4 15 6)
  > (queue->list empty)
  - : (Listof Nothing)
  '()

(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.

Examples:

> (queue->list (map add1 (queue 1 2 3 4 5 6)))

- : (Listof Exact-Positive-Integer)

'(2 3 4 5 6 7)

> (queue->list (map * (queue 1 2 3 4 5 6) (queue 1 2 3 4 5 6)))

- : (Listof Exact-Positive-Integer)

'(1 4 9 16 25 36)

(fold func init que1 que2 ...) → C

func : (C A B ... 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 1 2 3 4 5 6))
  - : Exact-Nonnegative-Integer
  21
  > (fold * 1 (queue 1 2 3 4 5 6) (queue 1 2 3 4 5 6))
  - : Exact-Positive-Integer
  518400

(filter func que) → (Queue A)

func : (A -> Boolean)

que : (Queue A)

Function filter is similar to filter.

Examples:

> (define que (queue 1 2 3 4 5 6))

> (queue->list (filter (λ: ([x : Integer]) (> x 5)) que))

- : (Listof Positive-Fixnum)

'(6)

> (queue->list (filter (λ: ([x : Integer]) (< x 5)) que))

- : (Listof Positive-Fixnum)

'(1 2 3 4)

> (queue->list (filter (λ: ([x : Integer]) (<= x 5)) que))

- : (Listof Positive-Fixnum)

'(1 2 3 4 5)

(remove func que) → (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]) (> x 5))

(queue 1 2 3 4 5 6)))

- : (Listof Positive-Fixnum)

'(1 2 3 4 5)

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

(queue 1 2 3 4 5 6)))

- : (Listof Positive-Fixnum)

'(5 6)

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

(queue 1 2 3 4 5 6)))

- : (Listof Positive-Fixnum)

'(6)

(andmap func que1 que2 ...) → Boolean

func : (A B ... B -> Boolean)

que1 : (Queue A)

que2 : (Queue B)

Function andmap is similar to andmap.

(ormap func que1 que2 ...) → Boolean

func : (A B ... B -> Boolean)

que1 : (Queue A)

que2 : (Queue B)

Function ormap is similar to ormap.

(build-queue size func) → (Queue A)

size : Natural

func : (Natural -> A)

Function build-queue is similar to build-list.

Examples:

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

- : (Listof Integer)

'(1 2 3 4 5)

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

- : (Listof Integer)

'(0 1 4 9 16)

(head+tail que) → (Pair A (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 1 2 3 4 5))

- : (Pairof Positive-Fixnum (U Null (IntQue Positive-Fixnum)))

'(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

(require (planet krhari/pfds:1:5/realtimequeue))

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.

(Queue A)

A real-time queue of type A.

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

a : A

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

Example:

> (queue 1 2 3 4 5 6)

- : (Queue Positive-Fixnum)

#<Queue>

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

(empty t) → (Queue A)

t : A

An empty queue.

Examples:

> (empty Nothing)

- : (Queue Nothing)

#<Queue>

> (empty Integer)

- : (Queue Integer)

#<Queue>

(empty? que) → Boolean

que : (Queue A)

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

Examples:
  > (empty? (queue 1 2 3 4 5 6))
  - : Boolean
  #f
  > (empty? (empty Integer))
  - : Boolean
  #t

(enqueue a que) → (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 1 2 3 4 5 6))

- : (Queue Positive-Fixnum)

#<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).

(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 1 2 3 4 5 6))

- : Positive-Fixnum

> (head (empty Integer))

head: given queue is empty

(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 1 2 3 4 5 6))
  - : (Queue Positive-Fixnum)
  #<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).

(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 10 2 34 4 15 6))
  - : (Listof Positive-Fixnum)
  '(10 2 34 4 15 6)

(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.

Examples:

> (queue->list (map add1 (queue 1 2 3 4 5 6)))

- : (Listof Exact-Positive-Integer)

'(2 3 4 5 6 7)

> (queue->list (map * (queue 1 2 3 4 5 6) (queue 1 2 3 4 5 6)))

- : (Listof Exact-Positive-Integer)

'(1 4 9 16 25 36)

(fold func init que1 que2 ...) → C

func : (C A B ... 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 1 2 3 4 5 6))
  - : Exact-Nonnegative-Integer
  21
  > (fold * 1 (queue 1 2 3 4 5 6) (queue 1 2 3 4 5 6))
  - : Exact-Positive-Integer
  518400

(filter func que) → (Queue A)

func : (A -> Boolean)

que : (Queue A)

Function filter is similar to filter.

Examples:

> (define que (queue 1 2 3 4 5 6))

> (queue->list (filter (λ: ([x : Integer]) (> x 5)) que))

- : (Listof Positive-Fixnum)

'(6)

> (queue->list (filter (λ: ([x : Integer]) (< x 5)) que))

- : (Listof Positive-Fixnum)

'(1 2 3 4)

> (queue->list (filter (λ: ([x : Integer]) (<= x 5)) que))

- : (Listof Positive-Fixnum)

'(1 2 3 4 5)

(remove func que) → (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]) (> x 5))

(queue 1 2 3 4 5 6)))

- : (Listof Positive-Fixnum)

'(1 2 3 4 5)

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

(queue 1 2 3 4 5 6)))

- : (Listof Positive-Fixnum)

'(5 6)

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

(queue 1 2 3 4 5 6)))

- : (Listof Positive-Fixnum)

'(6)

(andmap func que1 que2 ...) → Boolean

func : (A B ... B -> Boolean)

que1 : (Queue A)

que2 : (Queue B)

Function andmap is similar to andmap.

(ormap func que1 que2 ...) → Boolean

func : (A B ... B -> Boolean)

que1 : (Queue A)

que2 : (Queue B)

Function ormap is similar to ormap.

(build-queue size func) → (Queue A)

size : Natural

func : (Natural -> A)

Function build-queue is similar to build-list.

Examples:

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

- : (Listof Integer)

'(1 2 3 4 5)

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

- : (Listof Integer)

'(0 1 4 9 16)

(head+tail que) → (Pair A (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 1 2 3 4 5))

- : (Pairof Positive-Fixnum (Queue Positive-Fixnum))

'(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

(require (planet krhari/pfds:1:5/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.

(Queue A)

A Hood-Melville queue of type A.

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

a : A

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

Example:

> (queue 1 2 3 4 5 6)

- : (Queue Positive-Fixnum)

#<Queue>

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

empty : (Queue Nothing)

An empty queue.

(empty? que) → Boolean

que : (Queue A)

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

Examples:
  > (empty? (queue 1 2 3 4 5 6))
  - : Boolean
  #f
  > (empty? empty)
  - : Boolean
  #t

(enqueue a que) → (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 1 2 3 4 5 6))

- : (Queue Positive-Fixnum)

#<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).

(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 1 2 3 4 5 6))

- : Positive-Fixnum

> (head empty)

head: given queue is empty

(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 1 2 3 4 5 6))

- : (Queue Positive-Fixnum)

#<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).

(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 10 2 34 4 15 6))

- : (Listof Positive-Fixnum)

'(10 2 34 4 15 6)

> (queue->list empty)

- : (Listof Nothing)

'()

(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.

Examples:

> (queue->list (map add1 (queue 1 2 3 4 5 6)))

- : (Listof Exact-Positive-Integer)

'(2 3 4 5 6 7)

> (queue->list (map * (queue 1 2 3 4 5 6) (queue 1 2 3 4 5 6)))

- : (Listof Exact-Positive-Integer)

'(1 4 9 16 25 36)

(fold func init que1 que2 ...) → C

func : (C A B ... 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 1 2 3 4 5 6))
  - : Exact-Nonnegative-Integer
  21
  > (fold * 1 (queue 1 2 3 4 5 6) (queue 1 2 3 4 5 6))
  - : Exact-Positive-Integer
  518400

(filter func que) → (Queue A)

func : (A -> Boolean)

que : (Queue A)

Function filter is similar to filter.

Examples:

> (define que (queue 1 2 3 4 5 6))

> (queue->list (filter (λ: ([x : Integer]) (> x 5)) que))

- : (Listof Positive-Fixnum)

'(6)

> (queue->list (filter (λ: ([x : Integer]) (< x 5)) que))

- : (Listof Positive-Fixnum)

'(1 2 3 4)

> (queue->list (filter (λ: ([x : Integer]) (<= x 5)) que))

- : (Listof Positive-Fixnum)

'(1 2 3 4 5)

(remove func que) → (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]) (> x 5))

(queue 1 2 3 4 5 6)))

- : (Listof Positive-Fixnum)

'(1 2 3 4 5)

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

(queue 1 2 3 4 5 6)))

- : (Listof Positive-Fixnum)

'(5 6)

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

(queue 1 2 3 4 5 6)))

- : (Listof Positive-Fixnum)

'(6)

(andmap func que1 que2 ...) → Boolean

func : (A B ... B -> Boolean)

que1 : (Queue A)

que2 : (Queue B)

Function andmap is similar to andmap.

(ormap func que1 que2 ...) → Boolean

func : (A B ... B -> Boolean)

que1 : (Queue A)

que2 : (Queue B)

Function ormap is similar to ormap.

(build-queue size func) → (Queue A)

size : Natural

func : (Natural -> A)

Function build-queue is similar to build-list.

Examples:

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

- : (Listof Integer)

'(1 2 3 4 5)

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

- : (Listof Integer)

'(0 1 4 9 16)

(head+tail que) → (Pair A (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 1 2 3 4 5))

- : (Pairof Positive-Fixnum (Queue Positive-Fixnum))

'(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

← prev up next →

1	Queues
2	Deques
3	Heaps
4	Random Access Lists
5	Catenable List
6	VList
7	Streams
8	Red-Black Trees
9	Tries
10	Sets
11	Treap

1.1	Banker’s Queue
1.2	Physicist’s Queue
1.3	Implicit Queue
1.4	Bootstraped Queue
1.5	Real-Time Queue
1.6	Hood-Melville Queue