class Hamster::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`:

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.

@example

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 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/hamster/deque.rb, line 45
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/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() click to toggle source

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

@return [Deque]

# File lib/hamster/deque.rb, line 53
def empty
  @empty ||= self.new
end
new(items=[]) click to toggle source
# File lib/hamster/deque.rb, line 71
def initialize(items=[])
  @front = Hamster::List.from_enum(items)
  @rear  = EmptyList
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/hamster/deque.rb, line 181
def clear
  self.class.empty
end
dequeue()
Alias for: shift
empty?() click to toggle source

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

# File lib/hamster/deque.rb, line 78
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/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
Also aliased as: ==
first() click to toggle source

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

@example

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

@return [Object]

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

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

@example

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

@return [Object]

# File lib/hamster/deque.rb, line 110
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/hamster/deque.rb, line 232
def marshal_dump
  to_a
end
marshal_load(array) click to toggle source

@private

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

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

@example

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

@return [Deque]

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

@private

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

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

@example

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

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

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

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

@example

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

@return [Deque]

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

Return the number of items in this `Deque`.

@example

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

@return [Integer]

# File lib/hamster/deque.rb, line 88
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/hamster/deque.rb, line 197
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 [Hamster::List]

# File lib/hamster/deque.rb, line 205
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

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

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

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