Class: Hamster::Deque

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

Overview

A Deque (or double-ended queue) is an ordered, sequential collection of objects, which allows elements to be efficiently added and removed at the front and end of the sequence. Retrieving the elements at the front and end is also efficient. This makes Deque perfect for use as an immutable queue or stack.

A Deque differs from a Vector in that vectors allow indexed access to any element in the collection. Deques only allow access to the first and last element. But adding and removing from the ends of a Deque is faster than adding and removing from the ends of a Vector.

To create a new Deque:

Hamster.deque('a', 'b', 'c')
Hamster::Deque.new([:first, :second, :third])
Hamster::Deque[1, 2, 3, 4, 5]

Or you can start with an empty deque and build it up:

Hamster::Deque.empty.push('b').push('c').unshift('a')

Like all Hamster collections, Deque is immutable. The 4 basic operations which "modify" deques (#push, #pop, #shift, and #unshift) all return a new collection and leave the existing one unchanged.

Examples:

deque = Hamster::Deque.empty                 # => Hamster::Deque[]
deque = deque.push('a').push('b').push('c')  # => Hamster::Deque['a', 'b', 'c']
deque.first                                  # => 'a'
deque.last                                   # => 'c'
deque = deque.shift                          # => Hamster::Deque['b', 'c']

See Also:

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(items = []) ⇒ Deque


76
77
78
79
# File 'lib/hamster/deque.rb', line 76

def initialize(items=[])
  @front = items.to_list
  @rear  = EmptyList
end

Class Method Details

.[](*items) ⇒ Deque

Create a new Deque populated with the given items.


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

def [](*items)
  items.empty? ? empty : new(items)
end

.emptyDeque

Return an empty Deque. If used on a subclass, returns an empty instance of that class.


58
59
60
# File 'lib/hamster/deque.rb', line 58

def empty
  @empty ||= self.new
end

Instance Method Details

#clearDeque

Return an empty Deque instance, of the same class as this one. Useful if you have multiple subclasses of Deque and want to treat them polymorphically.


186
187
188
# File 'lib/hamster/deque.rb', line 186

def clear
  self.class.empty
end

#empty?Boolean

Return true if this Deque contains no items.


83
84
85
# File 'lib/hamster/deque.rb', line 83

def empty?
  @front.empty? && @rear.empty?
end

#eql?(other) ⇒ Boolean Also known as: ==

Return true if other has the same type and contents as this Deque.


194
195
196
197
# File 'lib/hamster/deque.rb', line 194

def eql?(other)
  return true if other.equal?(self)
  instance_of?(other.class) && to_ary.eql?(other.to_ary)
end

#firstObject

Return the first item in the Deque. If the deque is empty, return nil.

Examples:

Hamster::Deque["A", "B", "C"].first  #=> "A"

104
105
106
107
# File 'lib/hamster/deque.rb', line 104

def first
  return @front.head unless @front.empty?
  @rear.last # memoize?
end

#inspectString

Return the contents of this Deque as a programmer-readable String. If all the items in the deque are serializable as Ruby literal strings, the returned string can be passed to eval to reconstitute an equivalent Deque.


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

def inspect
  result = "#{self.class}["
  i = 0
  @front.each { |obj| result << ', ' if i > 0; result << obj.inspect; i += 1 }
  @rear.to_a.tap { |a| a.reverse! }.each { |obj| result << ', ' if i > 0; result << obj.inspect; i += 1 }
  result << "]"
end

#lastObject

Return the last item in the Deque. If the deque is empty, return nil.

Examples:

Hamster::Deque["A", "B", "C"].last  #=> "C"

115
116
117
118
# File 'lib/hamster/deque.rb', line 115

def last
  return @rear.head unless @rear.empty?
  @front.last # memoize?
end

#popDeque

Return a new Deque with the last item removed.

Examples:

Hamster::Deque["A", "B", "C"].pop
# => Hamster::Deque["A", "B"]

140
141
142
143
144
145
146
147
148
149
# File 'lib/hamster/deque.rb', line 140

def pop
  front, rear = @front, @rear

  if rear.empty?
    return self.class.empty if front.empty?
    front, rear = EmptyList, front.reverse
  end

  self.class.alloc(front, rear.tail)
end

#push(item) ⇒ Deque Also known as: enqueue

Return a new Deque with item added at the end.

Examples:

Hamster::Deque["A", "B", "C"].add("Z")
# => Hamster::Deque["A", "B", "C", "Z"]

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

def push(item)
  self.class.alloc(@front, @rear.cons(item))
end

#shiftDeque Also known as: dequeue

Return a new Deque with the first item removed.

Examples:

Hamster::Deque["A", "B", "C"].shift
# => Hamster::Deque["B", "C"]

170
171
172
173
174
175
176
177
178
179
# File 'lib/hamster/deque.rb', line 170

def shift
  front, rear = @front, @rear

  if front.empty?
    return self.class.empty if rear.empty?
    front, rear = rear.reverse, EmptyList
  end

  self.class.alloc(front.tail, rear)
end

#sizeInteger Also known as: length

Return the number of items in this Deque.

Examples:

Hamster::Deque["A", "B", "C"].size  #=> 3

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

def size
  @front.size + @rear.size
end

#to_aArray Also known as: entries, to_ary

Return an Array with the same elements, in the same order.


202
203
204
# File 'lib/hamster/deque.rb', line 202

def to_a
  @front.to_a.concat(@rear.to_a.tap { |a| a.reverse! })
end

#to_listHamster::List

Return a List with the same elements, in the same order.


210
211
212
# File 'lib/hamster/deque.rb', line 210

def to_list
  @front.append(@rear.reverse)
end

#unshift(item) ⇒ Deque

Return a new Deque with item added at the front.

Examples:

Hamster::Deque["A", "B", "C"].unshift("Z")
# => Hamster::Deque["Z", "A", "B", "C"]

159
160
161
# File 'lib/hamster/deque.rb', line 159

def unshift(item)
  self.class.alloc(@front.cons(item), @rear)
end