Class: Algorithmable::DataStructs::Deque

Inherits:
Object
  • Object
show all
Includes:
Errors
Defined in:
lib/algorithmable/data_structs/deque.rb

Constant Summary

Constants included from Errors

Errors::NoSuchElementError

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(collection = []) ⇒ Deque

Returns a new instance of Deque.


11
12
13
14
15
16
# File 'lib/algorithmable/data_structs/deque.rb', line 11

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

Instance Attribute Details

#sizeObject (readonly)

Returns the value of attribute size


9
10
11
# File 'lib/algorithmable/data_structs/deque.rb', line 9

def size
  @size
end

Instance Method Details

#clearObject


22
23
24
25
26
# File 'lib/algorithmable/data_structs/deque.rb', line 22

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

#each(&block) ⇒ Object

represent fifo iterator


93
94
95
# File 'lib/algorithmable/data_structs/deque.rb', line 93

def each(&block)
  collect_items(:forward).each(&block)
end

#empty?Boolean

Returns:

  • (Boolean)

18
19
20
# File 'lib/algorithmable/data_structs/deque.rb', line 18

def empty?
  0 == size
end

#map(&block) ⇒ Object


106
107
108
# File 'lib/algorithmable/data_structs/deque.rb', line 106

def map(&block)
  each.map(&block)
end

#peek_backObject


32
33
34
# File 'lib/algorithmable/data_structs/deque.rb', line 32

def peek_back
  @back && @back.item
end

#peek_frontObject


28
29
30
# File 'lib/algorithmable/data_structs/deque.rb', line 28

def peek_front
  @front && @front.item
end

#pop_backObject


78
79
80
81
82
83
84
85
86
87
88
89
90
# File 'lib/algorithmable/data_structs/deque.rb', line 78

def pop_back
  fail NoSuchElementError unless @back
  node = @back
  if @size == 1
    clear
    return node.item
  else
    @back.prev.next = nil
    @back = @back.prev
  end
  @size -= 1
  node.item
end

#pop_frontObject


64
65
66
67
68
69
70
71
72
73
74
75
76
# File 'lib/algorithmable/data_structs/deque.rb', line 64

def pop_front
  fail NoSuchElementError unless @front
  node = @front
  if 1 == @size
    clear
    return node.item
  else
    @front.next.prev = nil
    @front = @front.next
  end
  @size -= 1
  node.item
end

#push_back(obj) ⇒ Object


50
51
52
53
54
55
56
57
58
59
60
61
62
# File 'lib/algorithmable/data_structs/deque.rb', line 50

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

#push_front(obj) ⇒ Object


36
37
38
39
40
41
42
43
44
45
46
47
48
# File 'lib/algorithmable/data_structs/deque.rb', line 36

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

#reverse_each(&block) ⇒ Object

represent lifo iterator


98
99
100
# File 'lib/algorithmable/data_structs/deque.rb', line 98

def reverse_each(&block)
  collect_items(:backward).each(&block)
end

#to_aObject


102
103
104
# File 'lib/algorithmable/data_structs/deque.rb', line 102

def to_a
  each.to_a
end