Class: Immutable::Deque
- Inherits:
-
Object
- Object
- Immutable::Deque
- Defined in:
- lib/immutable/deque.rb
Overview
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.
Class Method Summary collapse
-
.[](*items) ⇒ Deque
Create a new
Deque
populated with the given items. -
.empty ⇒ Deque
Return an empty
Deque
.
Instance Method Summary collapse
-
#clear ⇒ Deque
Return an empty
Deque
instance, of the same class as this one. -
#dup ⇒ Deque
(also: #clone)
Return
self
. -
#empty? ⇒ Boolean
Return
true
if thisDeque
contains no items. -
#eql?(other) ⇒ Boolean
(also: #==)
Return true if
other
has the same type and contents as thisDeque
. -
#first ⇒ Object
Return the first item in the
Deque
. -
#initialize(items = []) ⇒ Deque
constructor
A new instance of Deque.
-
#inspect ⇒ String
Return the contents of this
Deque
as a programmer-readableString
. -
#last ⇒ Object
Return the last item in the
Deque
. -
#pop ⇒ Deque
Return a new
Deque
with the last item removed. -
#push(item) ⇒ Deque
(also: #enqueue)
Return a new
Deque
withitem
added at the end. -
#reverse ⇒ Deque
Return a new
Deque
with the same items, but in reverse order. -
#rotate(n) ⇒ Deque
Return a new
Deque
with elements rotated byn
positions. -
#shift ⇒ Deque
(also: #dequeue)
Return a new
Deque
with the first item removed. -
#size ⇒ Integer
(also: #length)
Return the number of items in this
Deque
. -
#to_a ⇒ Array
(also: #entries, #to_ary)
Return an
Array
with the same elements, in the same order. -
#to_list ⇒ Immutable::List
Return a List with the same elements, in the same order.
-
#unshift(item) ⇒ Deque
Return a new
Deque
withitem
added at the front.
Constructor Details
Class Method Details
.[](*items) ⇒ Deque
Create a new Deque
populated with the given items.
42 43 44 |
# File 'lib/immutable/deque.rb', line 42 def [](*items) items.empty? ? empty : new(items) end |
.empty ⇒ Deque
Return an empty Deque
. If used on a subclass, returns an empty instance
of that class.
50 51 52 |
# File 'lib/immutable/deque.rb', line 50 def empty @empty ||= new end |
Instance Method Details
#clear ⇒ Deque
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.
207 208 209 |
# File 'lib/immutable/deque.rb', line 207 def clear self.class.empty end |
#dup ⇒ Deque Also known as: clone
Return self
. Since this is an immutable object duplicates are
equivalent.
258 259 260 |
# File 'lib/immutable/deque.rb', line 258 def dup self end |
#empty? ⇒ Boolean
Return true
if this Deque
contains no items.
76 77 78 |
# File 'lib/immutable/deque.rb', line 76 def empty? @front.empty? && @rear.empty? end |
#eql?(other) ⇒ Boolean Also known as: ==
Return true if other
has the same type and contents as this Deque
.
222 223 224 225 |
# 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 |
#first ⇒ Object
Return the first item in the Deque
. If the deque is empty, return nil
.
97 98 99 100 |
# File 'lib/immutable/deque.rb', line 97 def first return @front.head unless @front.empty? @rear.last # memoize? end |
#inspect ⇒ String
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
.
247 248 249 250 251 252 253 |
# 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(&:reverse!).each { |obj| result << ', ' if i > 0; result << obj.inspect; i += 1 } result << ']' end |
#last ⇒ Object
Return the last item in the Deque
. If the deque is empty, return nil
.
108 109 110 111 |
# File 'lib/immutable/deque.rb', line 108 def last return @rear.head unless @rear.empty? @front.last # memoize? end |
#pop ⇒ Deque
Return a new Deque
with the last item removed.
161 162 163 164 165 166 167 168 169 170 |
# 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 |
#push(item) ⇒ Deque Also known as: enqueue
Return a new Deque
with item
added at the end.
149 150 151 |
# File 'lib/immutable/deque.rb', line 149 def push(item) self.class.alloc(@front, @rear.cons(item)) end |
#reverse ⇒ Deque
Return a new Deque
with the same items, but in reverse order.
214 215 216 |
# File 'lib/immutable/deque.rb', line 214 def reverse self.class.alloc(@rear, @front) end |
#rotate(n) ⇒ Deque
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.
124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 |
# File 'lib/immutable/deque.rb', line 124 def rotate(n) return self.class.empty if empty? n %= 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 (size - n).times { b = b.cons(a.head); a = a.tail } end self.class.alloc(a, b) end |
#shift ⇒ Deque Also known as: dequeue
Return a new Deque
with the first item removed.
191 192 193 194 195 196 197 198 199 200 |
# 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 |
#size ⇒ Integer Also known as: length
Return the number of items in this Deque
.
86 87 88 |
# File 'lib/immutable/deque.rb', line 86 def size @front.size + @rear.size end |
#to_a ⇒ Array Also known as: entries, to_ary
Return an Array
with the same elements, in the same order.
230 231 232 |
# File 'lib/immutable/deque.rb', line 230 def to_a @front.to_a.concat(@rear.to_a.tap(&:reverse!)) end |
#to_list ⇒ Immutable::List
Return a List with the same elements, in the same order.
238 239 240 |
# File 'lib/immutable/deque.rb', line 238 def to_list @front.append(@rear.reverse) end |
#unshift(item) ⇒ Deque
Return a new Deque
with item
added at the front.
180 181 182 |
# File 'lib/immutable/deque.rb', line 180 def unshift(item) self.class.alloc(@front.cons(item), @rear) end |