Class: Immutable::Deque

Inherits:
Object
  • Object
show all
Defined in:
lib/immutable/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. ‘Deque`s 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:

Immutable::Deque.new([:first, :second, :third])
Immutable::Deque[1, 2, 3, 4, 5]

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

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

Like all immutable-ruby 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 = Immutable::Deque.empty               # => Immutable::Deque[]
deque = deque.push('a').push('b').push('c')  # => Immutable::Deque['a', 'b', 'c']
deque.first                                  # => 'a'
deque.last                                   # => 'c'
deque = deque.shift                          # => Immutable::Deque['b', 'c']

See Also:

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(items = []) ⇒ Deque

Returns a new instance of Deque.



68
69
70
71
72
 
# File 'lib/immutable/deque.rb', line 68

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

Class Method Details

.[](*items) ⇒ Deque

Create a new Deque populated with the given items.

Returns:



42
43
44
 
# File 'lib/immutable/deque.rb', line 42

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:



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

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:



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

def empty
  @empty ||= 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:



207
208
209
 
# File 'lib/immutable/deque.rb', line 207

def clear
  self.class.empty
end

#dup ⇒ Deque Also known as: clone

Return self. Since this is an immutable object duplicates are equivalent.

Returns:



258
259
260
 
# File 'lib/immutable/deque.rb', line 258

def dup
  self
end

#empty? ⇒ Boolean

Return true if this Deque contains no items.

Returns:



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

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:

  • The collection to compare with

Returns:



222
223
224
225
 
# File 'lib/immutable/deque.rb', line 222

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:

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

Returns:



97
98
99
100
 
# File 'lib/immutable/deque.rb', line 97

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:



247
248
249
250
251
252
253
 
# File 'lib/immutable/deque.rb', line 247

def inspect
  result = "#{self.class}["
  i = 0
  @front.each { |obj| result << ', ' if i > 0; result << obj.inspect; i += 1 }
  @rear.to_a.tap(&: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:

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

Returns:



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

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

#marshal_dump ⇒ ::Array

Returns:



273
274
275
 
# File 'lib/immutable/deque.rb', line 273

def marshal_dump
  to_a
end

#marshal_load(array) ⇒ Object 



278
279
280
 
# File 'lib/immutable/deque.rb', line 278

def marshal_load(array)
  initialize(array)
end

#pop ⇒ Deque

Return a new Deque with the last item removed.

Examples:

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

Returns:



161
162
163
164
165
166
167
168
169
170
 
# File 'lib/immutable/deque.rb', line 161

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 



264
265
266
267
268
269
 
# File 'lib/immutable/deque.rb', line 264

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

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

Parameters:

  • The item to add

Returns:



149
150
151
 
# File 'lib/immutable/deque.rb', line 149

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

#reverse ⇒ Deque

Return a new Deque with the same items, but in reverse order.

Returns:



214
215
216
 
# File 'lib/immutable/deque.rb', line 214

def reverse
  self.class.alloc(@rear, @front)
end

#rotate(n) ⇒ Deque

Return a new Deque with elements rotated by n positions. A positive rotation moves elements to the right, negative to the left, and 0 is a no-op.

Examples:

Immutable::Deque["A", "B", "C"].rotate(1)
# => Immutable::Deque["C", "A", "B"]
Immutable::Deque["A", "B", "C"].rotate(-1)
# => Immutable::Deque["B", "C", "A"]

Parameters:

  • number of positions to move elements by

Returns:



124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
 
# File 'lib/immutable/deque.rb', line 124

def rotate(n)
  return self.class.empty if empty?

  n %= size
  return self if n == 0

  a, b = @front, @rear

  if b.size >= n
    n.times { a = a.cons(b.head); b = b.tail }
  else
    (size - n).times { b = b.cons(a.head); a = a.tail }
  end

  self.class.alloc(a, b)
end

#shift ⇒ Deque Also known as: dequeue

Return a new Deque with the first item removed.

Examples:

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

Returns:



191
192
193
194
195
196
197
198
199
200
 
# File 'lib/immutable/deque.rb', line 191

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:

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

Returns:



86
87
88
 
# File 'lib/immutable/deque.rb', line 86

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:



230
231
232
 
# File 'lib/immutable/deque.rb', line 230

def to_a
  @front.to_a.concat(@rear.to_a.tap(&:reverse!))
end

#to_list ⇒ Immutable::List

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

Returns:



238
239
240
 
# File 'lib/immutable/deque.rb', line 238

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

#unshift(item) ⇒ Deque

Return a new Deque with item added at the front.

Examples:

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

Parameters:

  • The item to add

Returns:



180
181
182
 
# File 'lib/immutable/deque.rb', line 180

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