class Immutable::Deque

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.

@example

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 en.wikipedia.org/wiki/Deque “Deque” on Wikipedia

Public Class Methods

[](*items) click to toggle source

Create a new `Deque` populated with the given items. @return [Deque]

# File lib/immutable/deque.rb, line 42
def [](*items)
  items.empty? ? empty : new(items)
end
alloc(front, rear) click to toggle source

“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.

@return [Deque] @private

# 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() click to toggle source

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

@return [Deque]

# File lib/immutable/deque.rb, line 50
def empty
  @empty ||= self.new
end
new(items=[]) click to toggle source
# File lib/immutable/deque.rb, line 68
def initialize(items=[])
  @front = List.from_enum(items)
  @rear  = EmptyList
  freeze
end

Public Instance Methods

==(other)
Alias for: eql?
clear() click to toggle source

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.

@return [Deque]

# File lib/immutable/deque.rb, line 207
def clear
  self.class.empty
end
clone()
Alias for: dup
dequeue()
Alias for: shift
dup() click to toggle source

Return `self`. Since this is an immutable object duplicates are equivalent. @return [Deque]

# File lib/immutable/deque.rb, line 258
def dup
  self
end
Also aliased as: clone
empty?() click to toggle source

Return `true` if this `Deque` contains no items. @return [Boolean]

# File lib/immutable/deque.rb, line 76
def empty?
  @front.empty? && @rear.empty?
end
enqueue(item)
Alias for: push
entries()
Alias for: to_a
eql?(other) click to toggle source

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

@param other [Object] The collection to compare with @return [Boolean]

# 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
Also aliased as: ==
first() click to toggle source

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

@example

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

@return [Object]

# File lib/immutable/deque.rb, line 97
def first
  return @front.head unless @front.empty?
  @rear.last # memoize?
end
inspect() click to toggle source

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`.

@return [String]

# 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 { |a| a.reverse! }.each { |obj| result << ', ' if i > 0; result << obj.inspect; i += 1 }
  result << "]"
end
last() click to toggle source

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

@example

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

@return [Object]

# File lib/immutable/deque.rb, line 108
def last
  return @rear.head unless @rear.empty?
  @front.last # memoize?
end
length()
Alias for: size
marshal_dump() click to toggle source

@return [::Array] @private

# File lib/immutable/deque.rb, line 273
def marshal_dump
  to_a
end
marshal_load(array) click to toggle source

@private

# File lib/immutable/deque.rb, line 278
def marshal_load(array)
  initialize(array)
end
pop() click to toggle source

Return a new `Deque` with the last item removed.

@example

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

@return [Deque]

# 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) click to toggle source

@private

# File lib/immutable/deque.rb, line 264
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) click to toggle source

Return a new `Deque` with `item` added at the end.

@example

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

@param item [Object] The item to add @return [Deque]

# File lib/immutable/deque.rb, line 149
def push(item)
  self.class.alloc(@front, @rear.cons(item))
end
Also aliased as: enqueue
reverse() click to toggle source

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

@return [Deque]

# File lib/immutable/deque.rb, line 214
def reverse
  self.class.alloc(@rear, @front)
end
rotate(n) click to toggle source

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.

@example

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

@param n [Integer] number of positions to move elements by @return [Deque]

# File lib/immutable/deque.rb, line 124
def rotate(n)
  return self.class.empty if self.empty?

  n %= self.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
    (self.size - n).times { b = b.cons(a.head); a = a.tail }
  end

  self.class.alloc(a, b)
end
shift() click to toggle source

Return a new `Deque` with the first item removed.

@example

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

@return [Deque]

# 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
Also aliased as: dequeue
size() click to toggle source

Return the number of items in this `Deque`.

@example

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

@return [Integer]

# File lib/immutable/deque.rb, line 86
def size
  @front.size + @rear.size
end
Also aliased as: length
to_a() click to toggle source

Return an `Array` with the same elements, in the same order. @return [Array]

# File lib/immutable/deque.rb, line 230
def to_a
  @front.to_a.concat(@rear.to_a.tap { |a| a.reverse! })
end
Also aliased as: entries, to_ary
to_ary()
Alias for: to_a
to_list() click to toggle source

Return a {List} with the same elements, in the same order. @return [Immutable::List]

# File lib/immutable/deque.rb, line 238
def to_list
  @front.append(@rear.reverse)
end
unshift(item) click to toggle source

Return a new `Deque` with `item` added at the front.

@example

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

@param item [Object] The item to add @return [Deque]

# File lib/immutable/deque.rb, line 180
def unshift(item)
  self.class.alloc(@front.cons(item), @rear)
end