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

- (Queue) initialize(front, rear, schedule)

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

+ (Queue) [](*elements)

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

+ (Queue) empty

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

- (true, false) empty?

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

- (Object) head

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

- (Queue) snoc(x) 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

- (Queue) tail

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