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
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
“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
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
# File lib/immutable/deque.rb, line 68 def initialize(items=[]) @front = List.from_enum(items) @rear = EmptyList freeze 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/immutable/deque.rb, line 207 def clear self.class.empty end
Return `self`. Since this is an immutable object duplicates are equivalent. @return [Deque]
# File lib/immutable/deque.rb, line 258 def dup self end
Return `true` if this `Deque` contains no items. @return [Boolean]
# File lib/immutable/deque.rb, line 76 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/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
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
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
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
@return [::Array] @private
# File lib/immutable/deque.rb, line 273 def marshal_dump to_a end
@private
# File lib/immutable/deque.rb, line 278 def marshal_load(array) initialize(array) end
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
@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
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
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
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
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
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
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
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
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