Class: Immutable::Queue

Inherits:
Object
  • Object
show all
Includes:
Headable
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.

Direct Known Subclasses

OutputRestrictedDeque

Class Method Summary collapse

Instance Method Summary collapse

Methods included from Headable

#==, #[], #each, #each_index, #eql?, #fetch, #find, #first, #foldl, #foldl1, #foldr, #foldr1, #hash, #index, #inspect, #null?, #rindex, #shift, #to_list

Methods included from Foldable

#foldl, #length, #product, #sum

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

Creates a new queue populated with the given objects.

Parameters:

  • elements (Array<Object>) —

    the elements of the queue.

Returns:

  • (Queue) —

    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
  new(Stream.empty, Nil, Stream.empty)
end

Instance Method Details

#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.empty?
end

#head ⇒ Object

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

Returns:

  • (Object) —

    the first element of self.



53
54
55
 
# File 'lib/immutable/queue.rb', line 53

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.



43
44
45
 
# File 'lib/immutable/queue.rb', line 43

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::EmptyError is raised.

Returns:

  • (Queue) —

    the elements after the head of self.



61
62
63
64
65
66
67
 
# File 'lib/immutable/queue.rb', line 61

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