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 ||= 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:



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

def clear
  self.class.empty
end

#dup ⇒ Deque Also known as: clone

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

Returns:



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

def dup
  self
end

#empty? ⇒ Boolean

Return true if this Deque contains no items.

Returns:

  • (Boolean) 


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:

  • other (Object) —

    The collection to compare with

Returns:

  • (Boolean) 


187
188
189
190
 
# File 'lib/immutable/deque.rb', line 187

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:

  • (Object) 


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:

  • (String) 


212
213
214
215
216
217
218
 
# File 'lib/immutable/deque.rb', line 212

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:

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

Returns:

  • (Object) 


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:

  • (::Array) 


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

def marshal_dump
  to_a
end

#marshal_load(array) ⇒ Object 



243
244
245
 
# File 'lib/immutable/deque.rb', line 243

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:



133
134
135
136
137
138
139
140
141
142
 
# File 'lib/immutable/deque.rb', line 133

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 



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

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:

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

Parameters:

  • item (Object) —

    The item to add

Returns:



121
122
123
 
# File 'lib/immutable/deque.rb', line 121

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:

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

Returns:



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

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:

  • (Integer) 


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:

  • (Array) 


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

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

#to_list ⇒ Immutable::List

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

Returns:



203
204
205
 
# File 'lib/immutable/deque.rb', line 203

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:

  • item (Object) —

    The item to add

Returns:



152
153
154
 
# File 'lib/immutable/deque.rb', line 152

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