Class: Hamster::Deque

Inherits:
Object
  • Object
show all
Includes:
Immutable
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 retrieved, added and removed at the front and end of the sequence in constant time. 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.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 four basic operations that "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

Methods included from Immutable

included

Constructor Details

#initialize(items = []) ⇒ Deque

Returns a new instance of Deque.



71
72
73
74
 
# File 'lib/hamster/deque.rb', line 71

def initialize(items=[])
  @front = Hamster::List.from_enum(items)
  @rear  = EmptyList
end

Class Method Details

.[](*items) ⇒ Deque

Create a new Deque populated with the given items.

Returns:



45
46
47
 
# File 'lib/hamster/deque.rb', line 45

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

.alloc(front, rear) ⇒ Deque

"Raw" allocation of a new Deque. Used internally to create a new instance quickly after consing onto the front/rear lists or taking their tails.

Returns:



63
64
65
66
67
68
 
# File 'lib/hamster/deque.rb', line 63

def alloc(front, rear)
  result = allocate
  result.instance_variable_set(:@front, front)
  result.instance_variable_set(:@rear,  rear)
  result.freeze
end

.empty ⇒ Deque

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

Returns:



53
54
55
 
# File 'lib/hamster/deque.rb', line 53

def empty
  @empty ||= self.new
end

Instance Method Details

#clear ⇒ Deque

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.

Returns:



181
182
183
 
# File 'lib/hamster/deque.rb', line 181

def clear
  self.class.empty
end

#empty? ⇒ Boolean

Return true if this Deque contains no items.

Returns:

  • (Boolean) 


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

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.

Parameters:

  • other (Object) —

    The collection to compare with

Returns:

  • (Boolean) 


189
190
191
192
 
# File 'lib/hamster/deque.rb', line 189

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

#first ⇒ Object

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

Examples:

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

Returns:

  • (Object) 


99
100
101
102
 
# File 'lib/hamster/deque.rb', line 99

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

#inspect ⇒ String

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.

Returns:

  • (String) 


214
215
216
217
218
219
220
 
# File 'lib/hamster/deque.rb', line 214

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

#last ⇒ Object

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

Examples:

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

Returns:

  • (Object) 


110
111
112
113
 
# File 'lib/hamster/deque.rb', line 110

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

#marshal_dump ⇒ ::Array

Returns:

  • (::Array) 


232
233
234
 
# File 'lib/hamster/deque.rb', line 232

def marshal_dump
  to_a
end

#marshal_load(array) ⇒ Object 



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

def marshal_load(array)
  initialize(array)
end

#pop ⇒ Deque

Return a new Deque with the last item removed.

Examples:

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

Returns:



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

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

#pretty_print(pp) ⇒ Object 



223
224
225
226
227
228
 
# File 'lib/hamster/deque.rb', line 223

def pretty_print(pp)
  pp.group(1, "#{self.class}[", "]") do
    pp.breakable ''
    pp.seplist(self.to_a) { |obj| obj.pretty_print(pp) }
  end
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"]

Parameters:

  • item (Object) —

    The item to add

Returns:



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

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

#shift ⇒ Deque Also known as: dequeue

Return a new Deque with the first item removed.

Examples:

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

Returns:



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

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

#size ⇒ Integer Also known as: length

Return the number of items in this Deque.

Examples:

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

Returns:

  • (Integer) 


88
89
90
 
# File 'lib/hamster/deque.rb', line 88

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

#to_a ⇒ Array Also known as: entries, to_ary

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

Returns:

  • (Array) 


197
198
199
 
# File 'lib/hamster/deque.rb', line 197

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

#to_list ⇒ Hamster::List

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

Returns:



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

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"]

Parameters:

  • item (Object) —

    The item to add

Returns:



154
155
156
 
# File 'lib/hamster/deque.rb', line 154

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