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

#size ⇒ Object (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

#clear ⇒ Object 



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



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

def peek_back
  @back && @back.item
end

#peek_front ⇒ Object 



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

def peek_front
  @front && @front.item
end

#pop_back ⇒ Object 



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



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



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

def to_a
  each.to_a
end