Class: Deque

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

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(arg = [], value = nil, initial_capacity: 0) ⇒ Deque

Returns a new instance of Deque.



8
9
10
11
12
13
14
15
16
 
# File 'lib/deque.rb', line 8

def initialize(arg = [], value = nil, initial_capacity: 0)
  ary = arg
  ary = Array.new(arg, value) if arg.is_a?(Integer)
  @n = [initial_capacity, ary.size].max + 1
  @buf = ary + [nil] * (@n - ary.size)
  @head = 0
  @tail = ary.size
  @reverse_count = 0
end

Class Method Details

.[](*args) ⇒ Object 



4
5
6
 
# File 'lib/deque.rb', line 4

def self.[](*args)
  new(args)
end

Instance Method Details

#<<(x) ⇒ Object 



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

def <<(x)
  reversed? ? __unshift(x) : __push(x)
end

#==(other) ⇒ Object 



113
114
115
116
117
 
# File 'lib/deque.rb', line 113

def ==(other)
  return false unless size == other.size

  to_a == other.to_a
end

#[](a, b = nil) ⇒ Object 



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

def [](a, b = nil)
  if b
    slice2(a, b)
  elsif a.is_a?(Range)
    s = a.begin
    t = a.end
    t -= 1 if a.exclude_end?
    slice2(s, t - s + 1)
  else
    slice1(a)
  end
end

#[]=(idx, value) ⇒ Object 



109
110
111
 
# File 'lib/deque.rb', line 109

def []=(idx, value)
  @buf[__index(idx)] = value
end

#at(idx) ⇒ Object 



79
80
81
 
# File 'lib/deque.rb', line 79

def at(idx)
  slice1(idx)
end

#clear ⇒ Object 



166
167
168
169
170
171
172
173
 
# File 'lib/deque.rb', line 166

def clear
  @n = 1
  @buf = []
  @head = 0
  @tail = 0
  @reverse_count = 0
  self
end

#dig(*args) ⇒ Object 



136
137
138
139
140
141
142
143
144
145
146
 
# File 'lib/deque.rb', line 136

def dig(*args)
  case args.size
  when 0
    raise ArgumentError.new("wrong number of arguments (given 0, expected 1+)")
  when 1
    self[args[0].to_int]
  else
    i = args.shift.to_int
    self[i]&.dig(*args)
  end
end

#each(&block) ⇒ Object 



148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
 
# File 'lib/deque.rb', line 148

def each(&block)
  return enum_for(:each) unless block_given?

  if @head <= @tail
    if reversed?
      @buf[@head...@tail].reverse_each(&block)
    else
      @buf[@head...@tail].each(&block)
    end
  elsif reversed?
    @buf[0...@tail].reverse_each(&block)
    @buf[@head..-1].reverse_each(&block)
  else
    @buf[@head..-1].each(&block)
    @buf[0...@tail].each(&block)
  end
end

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


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

def empty?
  size == 0
end

#hash ⇒ Object 



119
120
121
 
# File 'lib/deque.rb', line 119

def hash
  to_a.hash
end

#inspect ⇒ Object 



240
241
242
243
244
 
# File 'lib/deque.rb', line 240

def inspect
  "Deque#{to_a}"
  # "Deque#{to_a}(@n=#{@n}, @buf=#{@buf}, @head=#{@head}, @tail=#{@tail}, "\
  # "size #{size}#{' full' if __full?}#{' rev' if reversed?})"
end

#join(sep = $OFS) ⇒ Object 



175
176
177
 
# File 'lib/deque.rb', line 175

def join(sep = $OFS)
  to_a.join(sep)
end

#last ⇒ Object 



55
56
57
 
# File 'lib/deque.rb', line 55

def last
  self[-1]
end

#pop ⇒ Object 



47
48
49
 
# File 'lib/deque.rb', line 47

def pop
  reversed? ? __shift : __pop
end

#push(*args) ⇒ Object Also known as: append 



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

def push(*args)
  args.each{ |x| self << x }
  self
end

#replace(other) ⇒ Object 



209
210
211
212
213
214
215
216
217
 
# File 'lib/deque.rb', line 209

def replace(other)
  ary = other.to_a
  @n = ary.size + 1
  @buf = ary + [nil] * (@n - ary.size)
  @head = 0
  @tail = ary.size
  @reverse_count = 0
  self
end

#reverse ⇒ Object 



123
124
125
 
# File 'lib/deque.rb', line 123

def reverse
  dup.reverse!
end

#reverse! ⇒ Object 



127
128
129
130
 
# File 'lib/deque.rb', line 127

def reverse!
  @reverse_count += 1
  self
end

#reversed? ⇒ Boolean

Returns:

  • (Boolean) 


132
133
134
 
# File 'lib/deque.rb', line 132

def reversed?
  @reverse_count & 1 == 1
end

#rotate(cnt = 1) ⇒ Object 



188
189
190
191
192
193
194
195
196
197
 
# File 'lib/deque.rb', line 188

def rotate(cnt = 1)
  return self if cnt == 0

  cnt %= size if cnt < 0 || size > cnt

  ret = dup
  @buf = @buf.dup
  cnt.times{ ret.push(ret.shift) }
  ret
end

#rotate!(cnt = 1) ⇒ Object 



179
180
181
182
183
184
185
186
 
# File 'lib/deque.rb', line 179

def rotate!(cnt = 1)
  return self if cnt == 0

  cnt %= size if cnt < 0 || size > cnt

  cnt.times{ push(shift) }
  self
end

#sample ⇒ Object 



199
200
201
202
203
 
# File 'lib/deque.rb', line 199

def sample
  return nil if empty?

  self[rand(size)]
end

#shift ⇒ Object 



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

def shift
  reversed? ? __pop : __shift
end

#shuffle ⇒ Object 



205
206
207
 
# File 'lib/deque.rb', line 205

def shuffle
  Deque.new(to_a.shuffle)
end

#size ⇒ Object Also known as: length 



22
23
24
 
# File 'lib/deque.rb', line 22

def size
  (@tail - @head) % @n
end

#slice(idx) ⇒ Object 



59
60
61
62
63
64
 
# File 'lib/deque.rb', line 59

def slice(idx)
  sz = size
  return nil if idx < -sz || sz <= idx

  @buf[__index(idx)]
end

#swap(i, j) ⇒ Object 



219
220
221
222
223
224
 
# File 'lib/deque.rb', line 219

def swap(i, j)
  i = __index(i)
  j = __index(j)
  @buf[i], @buf[j] = @buf[j], @buf[i]
  self
end

#to_a ⇒ Object 



226
227
228
 
# File 'lib/deque.rb', line 226

def to_a
  __to_a
end

#to_s ⇒ Object 



236
237
238
 
# File 'lib/deque.rb', line 236

def to_s
  "#{self.class}#{to_a}"
end

#unshift(*args) ⇒ Object Also known as: prepend 



37
38
39
40
41
42
43
44
 
# File 'lib/deque.rb', line 37

def unshift(*args)
  if reversed?
    args.reverse_each{ |e|  __push(e) }
  else
    args.reverse_each{ |e| __unshift(e) }
  end
  self
end