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.



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

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

.emptyQueue

Returns an 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.



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

def empty?
  @front.empty?
end

#headObject

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



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.



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

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

#tailQueue

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



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