Class: Algorithmable::DataStructs::Deque

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

Defined Under Namespace

Classes: Node

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.



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

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

Instance Attribute Details

#size ⇒ Object (readonly)

Returns the value of attribute size.



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

def size
  @size
end

Instance Method Details

#clear ⇒ Object 



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

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

#each ⇒ Object

represent fifo iterator



92
93
94
95
96
97
98
99
 
# File 'lib/algorithmable/data_structs/deque.rb', line 92

def each
  return unless @front
  node = @front
  while node
    yield node.item
    node = node.next
  end
end

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


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

def empty?
  0 == size
end

#peek_back ⇒ Object 



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

def peek_back
  @back && @back.item
end

#peek_front ⇒ Object 



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

def peek_front
  @front && @front.item
end

#pop_back ⇒ Object 



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

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_front ⇒ Object 



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

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 



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

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 



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

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 ⇒ Object

represent lifo iterator



102
103
104
105
106
107
108
109
 
# File 'lib/algorithmable/data_structs/deque.rb', line 102

def reverse_each
  return unless @back
  node = @back
  while node
    yield node.item
    node = node.prev
  end
end