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
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
“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
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
# File lib/hamster/deque.rb, line 71 def initialize(items=[]) @front = Hamster::List.from_enum(items) @rear = EmptyList end
Public Instance Methods
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
Return `true` if this `Deque` contains no items. @return [Boolean]
# File lib/hamster/deque.rb, line 78 def empty? @front.empty? && @rear.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]
# 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
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
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
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
@return [::Array] @private
# File lib/hamster/deque.rb, line 232 def marshal_dump to_a end
@private
# File lib/hamster/deque.rb, line 237 def marshal_load(array) initialize(array) end
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
@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
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
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
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
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
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
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