lib/hamster/deque.rb
require "hamster/immutable"
require "hamster/list"
module Hamster
# 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 http://en.wikipedia.org/wiki/Deque "Deque" on Wikipedia
#
class Deque
include Immutable
class << self
# Create a new `Deque` populated with the given items.
# @return [Deque]
def [](*items)
items.empty? ? empty : new(items)
end
# Return an empty `Deque`. If used on a subclass, returns an empty instance
# of that class.
#
# @return [Deque]
def empty
@empty ||= self.new
end
# "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
def alloc(front, rear)
result = allocate
result.instance_variable_set(:@front, front)
result.instance_variable_set(:@rear, rear)
result.freeze
end
end
def initialize(items=[])
@front = Hamster::List.from_enum(items)
@rear = EmptyList
end
# Return `true` if this `Deque` contains no items.
# @return [Boolean]
def empty?
@front.empty? && @rear.empty?
end
# Return the number of items in this `Deque`.
#
# @example
# Hamster::Deque["A", "B", "C"].size #=> 3
#
# @return [Integer]
def size
@front.size + @rear.size
end
alias :length :size
# Return the first item in the `Deque`. If the deque is empty, return `nil`.
#
# @example
# Hamster::Deque["A", "B", "C"].first #=> "A"
#
# @return [Object]
def first
return @front.head unless @front.empty?
@rear.last # memoize?
end
# Return the last item in the `Deque`. If the deque is empty, return `nil`.
#
# @example
# Hamster::Deque["A", "B", "C"].last #=> "C"
#
# @return [Object]
def last
return @rear.head unless @rear.empty?
@front.last # memoize?
end
# 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]
def push(item)
self.class.alloc(@front, @rear.cons(item))
end
alias :enqueue :push
# Return a new `Deque` with the last item removed.
#
# @example
# Hamster::Deque["A", "B", "C"].pop
# # => Hamster::Deque["A", "B"]
#
# @return [Deque]
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
# 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]
def unshift(item)
self.class.alloc(@front.cons(item), @rear)
end
# Return a new `Deque` with the first item removed.
#
# @example
# Hamster::Deque["A", "B", "C"].shift
# # => Hamster::Deque["B", "C"]
#
# @return [Deque]
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
alias :dequeue :shift
# 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]
def clear
self.class.empty
end
# Return true if `other` has the same type and contents as this `Deque`.
#
# @param other [Object] The collection to compare with
# @return [Boolean]
def eql?(other)
return true if other.equal?(self)
instance_of?(other.class) && to_ary.eql?(other.to_ary)
end
alias :== :eql?
# Return an `Array` with the same elements, in the same order.
# @return [Array]
def to_a
@front.to_a.concat(@rear.to_a.tap { |a| a.reverse! })
end
alias :entries :to_a
alias :to_ary :to_a
# Return a {List} with the same elements, in the same order.
# @return [Hamster::List]
def to_list
@front.append(@rear.reverse)
end
# 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]
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
# @private
def pretty_print(pp)
pp.group(1, "#{self.class}[", "]") do
pp.breakable ''
pp.seplist(self.to_a) { |obj| obj.pretty_print(pp) }
end
end
# @return [::Array]
# @private
def marshal_dump
to_a
end
# @private
def marshal_load(array)
initialize(array)
end
end
# The canonical empty `Deque`. Returned by `Deque[]` when
# invoked with no arguments; also returned by `Deque.empty`. Prefer using this
# one rather than creating many empty deques using `Deque.new`.
#
# @private
EmptyDeque = Hamster::Deque.empty
end