Class: Immutable::Queue

Inherits:
Object
  • Object
show all
Includes:
Enumerable
Defined in:
lib/immutable/queue.rb

Overview

Immutable::Queue is an implementation of real-time queues described in “Purely Functional Data Structures” by Chris Okasaki.

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(front, rear, schedule) ⇒ Queue

Queue.new is for internal use only. Use empty or [] instead.



11
12
13
14
15
 
# File 'lib/immutable/queue.rb', line 11

def initialize(front, rear, schedule)
  @front = front
  @rear = rear
  @schedule = schedule
end

Class Method Details

.[](*elements) ⇒ List

Creates a new queue populated with the given objects.

Parameters:

  • elements (Array<Object>) —

    the elements of the queue.

Returns:

  • (List) —

    the new queue.



28
29
30
 
# File 'lib/immutable/queue.rb', line 28

def self.[](*elements)
  elements.inject(empty, &:snoc)
end

.empty ⇒ Queue

Returns an empty queue.

Returns:

  • (Queue) —

    the empty queue.



20
21
22
 
# File 'lib/immutable/queue.rb', line 20

def self.empty
  Queue.new(Stream.null, Nil, Stream.null)
end

Instance Method Details

#each(&block) ⇒ Object

Calls block once for each element in self.



93
94
95
96
97
98
 
# File 'lib/immutable/queue.rb', line 93

def each(&block)
  unless @front.null?
    yield(head)
    tail.each(&block)
  end
end

#empty? ⇒ true, false

Returns whether self is empty.

Returns:

  • (true, false) —

    true if self is empty; otherwise, false.



35
36
37
 
# File 'lib/immutable/queue.rb', line 35

def empty?
  @front.null?
end

#head ⇒ Object

Returns the first element of self. If self is empty, Immutable::List::EmptyError is raised.

Returns:

  • (Object) —

    the first element of self.



76
77
78
 
# File 'lib/immutable/queue.rb', line 76

def head
  @front.head
end

#snoc(x) ⇒ Queue Also known as: push

Adds a new element at the end of self.

Parameters:

  • x (Object) —

    the element to add.

Returns:

  • (Queue) —

    a new queue.



67
68
69
 
# File 'lib/immutable/queue.rb', line 67

def snoc(x)
  queue(@front, Cons[x, @rear], @schedule)
end

#tail ⇒ Queue

Returns the elements after the head of self. If self is empty, Immutable::List::EmptyError is raised.

Returns:

  • (Queue) —

    the elements after the head of self.



84
85
86
87
88
89
90
 
# File 'lib/immutable/queue.rb', line 84

def tail
  if @front.null?
    raise List::EmptyError
  else
    queue(@front.tail, @rear, @schedule)
  end
end