Class: Algorithms::Containers::RubyDeque

Inherits:
Object
  • Object
show all
Includes:
Enumerable
Defined in:
lib/containers/deque.rb

Defined Under Namespace

Classes: Node

Instance Method Summary collapse

Constructor Details

#initialize(ary = []) ⇒ RubyDeque

Create a new Deque. Takes an optional array argument to initialize the Deque.

d = Containers::Deque.new([1, 2, 3])
d.front #=> 1
d.back #=> 3



19
20
21
22
23
24
 
# File 'lib/containers/deque.rb', line 19

def initialize(ary=[])
  @front = nil
  @back = nil
  @size = 0
  ary.to_a.each { |obj| push_back(obj) }
end

Instance Method Details

#back ⇒ Object

Returns the object at the back of the Deque but does not remove it.

d = Containers::Deque.new
d.push_front(1)
d.push_front(2)
d.back #=> 1



62
63
64
 
# File 'lib/containers/deque.rb', line 62

def back
  @back && @back.obj
end

#clear ⇒ Object

Removes all the objects in the Deque.



32
33
34
35
 
# File 'lib/containers/deque.rb', line 32

def clear
  @front = @back = nil
  @size = 0
end

#each_backward ⇒ Object Also known as: reverse_each

Iterate over the Deque in LIFO order.



156
157
158
159
160
161
162
163
 
# File 'lib/containers/deque.rb', line 156

def each_backward
  return unless @back
  node = @back
  while node
    yield node.obj
    node = node.left
  end
end

#each_forward ⇒ Object Also known as: each

Iterate over the Deque in FIFO order.



145
146
147
148
149
150
151
152
 
# File 'lib/containers/deque.rb', line 145

def each_forward
  return unless @front
  node = @front
  while node
    yield node.obj
    node = node.right
  end
end

#empty? ⇒ Boolean

Returns true if the Deque is empty, false otherwise.

Returns:

  • (Boolean) 


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

def empty?
  @size == 0
end

#front ⇒ Object

Returns the object at the front of the Deque but does not remove it.

d = Containers::Deque.new
d.push_front(1)
d.push_front(2)
d.front #=> 2



52
53
54
 
# File 'lib/containers/deque.rb', line 52

def front
  @front && @front.obj
end

#pop_back ⇒ Object

Returns the object at the back of the Deque and removes it.

d = Containers::Deque.new
d.push_front(1)
d.push_front(2)
d.pop_back #=> 1
d.size #=> 1



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

def pop_back
  return nil unless @back
  node = @back
  if @size == 1
    clear
    return node.obj
  else
    @back.left.right = nil
    @back = @back.left
  end
  @size -= 1
  node.obj
end

#pop_front ⇒ Object

Returns the object at the front of the Deque and removes it.

d = Containers::Deque.new
d.push_front(1)
d.push_front(2)
d.pop_front #=> 2
d.size #=> 1



109
110
111
112
113
114
115
116
117
118
119
120
121
 
# File 'lib/containers/deque.rb', line 109

def pop_front
  return nil unless @front
  node = @front
  if @size == 1
    clear
    return node.obj
  else
    @front.right.left = nil
    @front = @front.right
  end
  @size -= 1
  node.obj
end

#push_back(obj) ⇒ Object

Adds an object at the back of the Deque.

d = Containers::Deque.new([1, 2, 3])
d.push_back(4)
d.pop_back #=> 4



89
90
91
92
93
94
95
96
97
98
99
100
 
# File 'lib/containers/deque.rb', line 89

def push_back(obj)
  node = Node.new(nil, nil, obj)
  if @back
    node.left = @back
    @back.right = node
    @back = node
  else
    @front = @back = node
  end
  @size += 1
  obj
end

#push_front(obj) ⇒ Object

Adds an object at the front of the Deque.

d = Containers::Deque.new([1, 2, 3])
d.push_front(0)
d.pop_front #=> 0



71
72
73
74
75
76
77
78
79
80
81
82
 
# File 'lib/containers/deque.rb', line 71

def push_front(obj)
  node = Node.new(nil, nil, obj)
  if @front
    node.right = @front
    @front.left = node
    @front = node
  else
    @front = @back = node
  end
  @size += 1
  obj
end

#size ⇒ Object Also known as: length

Return the number of items in the Deque.

d = Containers::Deque.new([1, 2, 3])
d.size #=> 3



41
42
43
 
# File 'lib/containers/deque.rb', line 41

def size
  @size
end