Class: Immutable::Deque

Inherits:
Object
  • Object
show all
Includes:
Consable
Defined in:
lib/immutable/deque.rb

Overview

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

Class Method Summary collapse

Instance Method Summary collapse

Methods included from Consable

#+, #drop, #drop_while, #filter, #flat_map, #flatten, included, #intercalate, #intersperse, #map, #prepend, #rev_map, #reverse, #subsequences, #take, #take_while, #transpose, #unshift, #zip, #zip_with

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, #product, #sum

Constructor Details

#initialize(front, front_len, front_schedule, rear, rear_len, rear_schedule) ⇒ Deque

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



12
13
14
15
16
17
18
19
20
21
 
# File 'lib/immutable/deque.rb', line 12

def initialize(front, front_len, front_schedule,
               rear, rear_len, rear_schedule)
  @front = front
  @front_len = front_len
  @front_schedule = front_schedule
  @rear = rear
  @rear_len = rear_len
  @rear_schedule = rear_schedule
  @c = 3  # @c should be 2 or 3
end

Class Method Details

.[](*elements) ⇒ Deque

Creates a new deque populated with the given objects.

Parameters:

  • elements (Array<Object>) —

    the elements of the deque.

Returns:

  • (Deque) —

    the new deque.



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

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

.empty ⇒ Deque

Returns an empty deque.

Returns:

  • (Deque) —

    the empty deque.



26
27
28
29
 
# File 'lib/immutable/deque.rb', line 26

def self.empty
  Deque.new(Stream.empty, 0, Stream.empty,
            Stream.empty, 0, Stream.empty)
end

Instance Method Details

#cons(x) ⇒ Deque

Adds a new element at the head of self.

Parameters:

  • x (Object) —

    the element to add.

Returns:

  • (Deque) —

    a new deque.



57
58
59
60
61
 
# File 'lib/immutable/deque.rb', line 57

def cons(x)
  queue(Stream.cons(->{x}, ->{@front}), @front_len + 1,
        exec1(@front_schedule),
        @rear, @rear_len, exec1(@rear_schedule))
end

#empty? ⇒ true, false

Returns whether self is empty.

Returns:

  • (true, false) —

    true if self is empty; otherwise, false.



42
43
44
 
# File 'lib/immutable/deque.rb', line 42

def empty?
  length == 0
end

#head ⇒ Object

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

Returns:

  • (Object) —

    the first element of self.



67
68
69
70
71
72
73
74
75
76
77
 
# File 'lib/immutable/deque.rb', line 67

def head
  if @front.empty?
    if @rear.empty?
      raise EmptyError
    else
      @rear.head
    end
  else
    @front.head
  end
end

#init ⇒ Deque Also known as: pop

Returns all the elements of self except the last one. If self is empty, Immutable::EmptyError is raised.

Returns:

  • (Deque) —

    the elements of self except the last one.



129
130
131
132
133
134
135
136
137
138
139
140
 
# File 'lib/immutable/deque.rb', line 129

def init
  if @rear.empty?
    if @front.empty?
      raise EmptyError
    else
      self.class.empty
    end
  else
    queue(@front, @front_len, exec2(@front_schedule),
          @rear.tail, @rear_len - 1, exec2(@rear_schedule))
  end
end

#last ⇒ Object

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

Returns:

  • (Object) —

    the last element of self.



112
113
114
115
116
117
118
119
120
121
122
 
# File 'lib/immutable/deque.rb', line 112

def last
  if @rear.empty?
    if @front.empty?
      raise EmptyError
    else
      @front.head
    end
  else
    @rear.head
  end
end

#length ⇒ Integer

Returns the number of elements in self. May be zero.

Returns:

  • (Integer) —

    the number of elements in self.



49
50
51
 
# File 'lib/immutable/deque.rb', line 49

def length
  @front_len + @rear_len
end

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

Adds a new element at the end of self.

Parameters:

  • x (Object) —

    the element to add.

Returns:

  • (Deque) —

    a new queue.



100
101
102
103
104
 
# File 'lib/immutable/deque.rb', line 100

def snoc(x)
  queue(@front, @front_len, exec1(@front_schedule),
        Stream.cons(->{x}, ->{@rear}), @rear_len + 1,
        exec1(@rear_schedule))
end

#tail ⇒ Deque

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

Returns:

  • (Deque) —

    the elements after the head of self.



83
84
85
86
87
88
89
90
91
92
93
94
 
# File 'lib/immutable/deque.rb', line 83

def tail
  if @front.empty?
    if @rear.empty?
      raise EmptyError
    else
      self.class.empty
    end
  else
    queue(@front.tail, @front_len - 1, exec2(@front_schedule),
          @rear, @rear_len, exec2(@rear_schedule))
  end
end