2 Deques

Version: 5.0.1.2

2 Deques

Following Deque data structures implement and provide the functions deque, empty?, enqueue, enqueue-front, head, tail, last, init and deque->list. All the deque structures are polymorphic and have the type (Deque A).

2.1 Bankers Deque

2.2 Implicit Deque

2.3 Real-Time Deque

2.1 Bankers Deque

(require "bankers-deque.ss")

Bankers Deques are Amortized double ended deques also known as deque developed using Bankers method. Provides amortized running time of O(1) for the operations head, tail, last, init, enqueue-front and enqueue. Uses lazy evaluation and memoization to achieve the amortized running time.

(deque a ...) → (Deque A)

a : A

Function deque creates a Bankers Deque with the given inputs.

Example:

> (deque 1 2 3 4 5 6)

- : (Deque Positive-Fixnum)

#<Deque>

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

empty : (Deque Nothing)

An empty deque

(empty? dq) → Boolean

dq : (Deque A)

Function empty? checks if the given deque is empty.

Examples:

> (empty? empty)

- : Boolean

> (empty? (deque 1 2))

- : Boolean

(enqueue a deq) → (Deque A)

a : A

deq : (Deque A)

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

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

(enqueue-front a deq) → (Deque A)

a : A

deq : (Deque A)

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

- : (Deque Positive-Fixnum)

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

(head deq) → A

deq : (Deque A)

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

- : Positive-Fixnum

> (head empty)

head: given deque is empty

In the above example, (head empty) throws an error since the given deque is empty.

(last deq) → A

deq : (Deque A)

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

- : Positive-Fixnum

> (last empty)

last: given deque is empty

In the above example, (last empty)throws an error since the given deque is empty.

(tail deq) → (Deque A)

deq : (Deque A)

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

#<Deque>

> (tail empty)

tail: given deque is empty

In the above example, (tail (deque 1 2 3 4 5 6)), removes the head of the given deque returns (deque 2 3 4 5 6).

(init deq) → (Deque A)

deq : (Deque A)

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

#<Deque>

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

(deque->list deq) → (Listof A)

deq : (Deque A)

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.

Examples:

> (deque->list (deque 10 2 34 4 15 6))

- : (Listof Positive-Fixnum)

'(10 2 34 4 15 6)

> (deque->list empty)

- : (Listof Nothing)

'()

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

Examples:

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

- : (Listof Exact-Positive-Integer)

'(2 3 4 5 6 7)

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

- : (Listof Exact-Positive-Integer)

'(1 4 9 16 25 36)

(foldl func init deq1 deq2 ...) → C

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

init : C

deq1 : (Deque A)

deq2 : (Deque B)

Function foldl is similar to foldl

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

Examples:
  > (foldl + 0 (deque 1 2 3 4 5 6))
  - : Exact-Nonnegative-Integer
  21
  > (foldl * 1 (deque 1 2 3 4 5 6) (deque 1 2 3 4 5 6))
  - : Exact-Positive-Integer
  518400

(foldr func init deq1 deq2 ...) → C

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

init : C

deq1 : (Deque A)

deq2 : (Deque B)

Function foldr is similar to foldr

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

Examples:
  > (foldr + 0 (deque 1 2 3 4 5 6))
  - : Exact-Nonnegative-Integer
  21
  > (foldr * 1 (deque 1 2 3 4 5 6) (deque 1 2 3 4 5 6))
  - : Exact-Positive-Integer
  518400

(filter func que) → (Deque A)

func : (A -> Boolean)

que : (Deque A)

Function filter is similar to filter.

Examples:

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

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

- : (Listof Positive-Fixnum)

'(6)

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

- : (Listof Positive-Fixnum)

'(1 2 3 4)

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

- : (Listof Positive-Fixnum)

'(1 2 3 4 5)

(remove func que) → (Deque A)

func : (A -> Boolean)

que : (Deque A)

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

Examples:

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

(deque 1 2 3 4 5 6)))

- : (Listof Positive-Fixnum)

'(1 2 3 4 5)

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

(deque 1 2 3 4 5 6)))

- : (Listof Positive-Fixnum)

'(5 6)

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

(deque 1 2 3 4 5 6)))

- : (Listof Positive-Fixnum)

'(6)

2.2 Implicit Deque

(require "implicitdeque.ss")

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.

(deque a ...) → (Deque A)

a : A

Function deque creates a Implicit Deque with the given inputs.

Example:
  > (deque 1 2 3 4 5 6)
  - : (U (Shallow Positive-Fixnum) (Deep Positive-Fixnum))
  #<Deep>

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

empty : (Deque Nothing)

An empty deque

(empty? dq) → Boolean

dq : (Deque A)

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

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

(enqueue a deq) → (Deque A)

a : A

deq : (Deque A)

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-Fixnum) (Deep Positive-Fixnum))

#<Deep>

In the above example, enqueue adds the element 10 to (deque 1 2 3 4 5 6 10).

(enqueue-front a deq) → (Deque A)

a : A

deq : (Deque A)

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-Fixnum) (Deep Positive-Fixnum))

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

(head deq) → A

deq : (Deque A)

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

- : Positive-Fixnum

> (head empty)

head: given deque is empty

(last deq) → A

deq : (Deque A)

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

- : Positive-Fixnum

> (last empty)

last: given deque is empty

(tail deq) → (Deque A)

deq : (Deque A)

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-Fixnum) (Deep Positive-Fixnum))

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

(init deq) → (Deque A)

deq : (Deque A)

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-Fixnum) (Deep Positive-Fixnum))

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

(deque->list deq) → (Listof A)

deq : (Deque A)

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-Fixnum)
  '(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.

Examples:

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

- : (Listof Exact-Positive-Integer)

'(2 3 4 5 6 7)

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

- : (Listof Exact-Positive-Integer)

'(1 4 9 16 25 36)

(foldl func init deq1 deq2 ...) → C

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

init : C

deq1 : (Deque A)

deq2 : (Deque B)

Function foldl is similar to foldl

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

Examples:
  > (foldl + 0 (deque 1 2 3 4 5 6))
  - : Exact-Nonnegative-Integer
  21
  > (foldl * 1 (deque 1 2 3 4 5 6) (deque 1 2 3 4 5 6))
  - : Exact-Positive-Integer
  518400

(foldr func init deq1 deq2 ...) → C

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

init : C

deq1 : (Deque A)

deq2 : (Deque B)

Function foldr is similar to foldr

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

Examples:
  > (foldr + 0 (deque 1 2 3 4 5 6))
  - : Exact-Nonnegative-Integer
  21
  > (foldr * 1 (deque 1 2 3 4 5 6) (deque 1 2 3 4 5 6))
  - : Exact-Positive-Integer
  518400

(filter func que) → (Deque A)

func : (A -> Boolean)

que : (Deque A)

Function filter is similar to filter.

Examples:

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

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

- : (Listof Positive-Fixnum)

'(6)

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

- : (Listof Positive-Fixnum)

'(1 2 3 4)

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

- : (Listof Positive-Fixnum)

'(1 2 3 4 5)

(remove func que) → (Deque A)

func : (A -> Boolean)

que : (Deque A)

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

Examples:

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

(deque 1 2 3 4 5 6)))

- : (Listof Positive-Fixnum)

'(1 2 3 4 5)

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

(deque 1 2 3 4 5 6)))

- : (Listof Positive-Fixnum)

'(5 6)

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

(deque 1 2 3 4 5 6)))

- : (Listof Positive-Fixnum)

'(6)

2.3 Real-Time Deque

(require "realtimedeque.ss")

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.

(deque a ...) → (Deque A)

a : A

Function deque creates a Real-Time Deque with the given inputs.

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

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

empty : (Deque Nothing)

An empty deque

(empty? dq) → Boolean

dq : (Deque A)

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

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

(enqueue a deq) → (Deque A)

a : A

deq : (Deque A)

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 Positive-Fixnum)

#<Deque>

In the above example, enqueue adds the element 10 to the end of (deque 1 2 3 4 5 6).

(enqueue-front a deq) → (Deque A)

a : A

deq : (Deque A)

Functionenqueue-front takes an element and a deque and adds the given element to the front of deque.

Example:

> (enqueue-front 10 (deque 1 2 3 4 5 6))

- : (Deque Positive-Fixnum)

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

(head deq) → A

deq : (Deque A)

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

- : Positive-Fixnum

> (head empty)

head: given deque is empty

(last deq) → A

deq : (Deque A)

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

- : Positive-Fixnum

> (last empty)

last: given deque is empty

(tail deq) → (Deque A)

deq : (Deque A)

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 Positive-Fixnum)

#<Deque>

> (tail empty)

tail: given deque is empty

In the above example, (tail (deque 1 2 3 4 5 6)), removes the head of the given deque returns (deque 2 3 4 5 6).

(init deq) → (Deque A)

deq : (Deque A)

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 Positive-Fixnum)

#<Deque>

> (init empty)

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

(deque->list deq) → (Listof A)

deq : (Deque A)

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-Fixnum)
  '(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.

Examples:

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

- : (Listof Exact-Positive-Integer)

'(2 3 4 5 6 7)

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

- : (Listof Exact-Positive-Integer)

'(1 4 9 16 25 36)

(foldl func init deq1 deq2 ...) → C

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

init : C

deq1 : (Deque A)

deq2 : (Deque B)

Function foldl is similar to foldl

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

Examples:
  > (foldl + 0 (deque 1 2 3 4 5 6))
  - : Exact-Nonnegative-Integer
  21
  > (foldl * 1 (deque 1 2 3 4 5 6) (deque 1 2 3 4 5 6))
  - : Exact-Positive-Integer
  518400

(foldr func init deq1 deq2 ...) → C

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

init : C

deq1 : (Deque A)

deq2 : (Deque B)

Function foldr is similar to foldr

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

Examples:
  > (foldr + 0 (deque 1 2 3 4 5 6))
  - : Exact-Nonnegative-Integer
  21
  > (foldr * 1 (deque 1 2 3 4 5 6) (deque 1 2 3 4 5 6))
  - : Exact-Positive-Integer
  518400

(filter func que) → (Deque A)

func : (A -> Boolean)

que : (Deque A)

Function filter is similar to filter.

Examples:

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

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

- : (Listof Positive-Fixnum)

'(6)

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

- : (Listof Positive-Fixnum)

'(1 2 3 4)

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

- : (Listof Positive-Fixnum)

'(1 2 3 4 5)

(remove func que) → (Deque A)

func : (A -> Boolean)

que : (Deque A)

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

Examples:

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

(deque 1 2 3 4 5 6)))

- : (Listof Positive-Fixnum)

'(1 2 3 4 5)

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

(deque 1 2 3 4 5 6)))

- : (Listof Positive-Fixnum)

'(5 6)

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

(deque 1 2 3 4 5 6)))

- : (Listof Positive-Fixnum)

'(6)

← 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