Class: Hamster::Deque
- Inherits:
-
Object
- Object
- Hamster::Deque
- Includes:
- Immutable
- Defined in:
- lib/hamster/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`:
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.
Class Method Summary collapse
-
.[](*items) ⇒ Deque
Create a new ‘Deque` populated with the given items.
-
.alloc(front, rear) ⇒ Deque
“Raw” allocation of a new ‘Deque`.
-
.empty ⇒ Deque
Return an empty ‘Deque`.
Instance Method Summary collapse
-
#clear ⇒ Deque
Return an empty ‘Deque` instance, of the same class as this one.
-
#empty? ⇒ Boolean
Return ‘true` if this `Deque` contains no items.
-
#eql?(other) ⇒ Boolean
(also: #==)
Return true if ‘other` has the same type and contents as this `Deque`.
-
#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-readable `String`.
-
#last ⇒ Object
Return the last item in the ‘Deque`.
- #marshal_dump ⇒ ::Array
- #marshal_load(array) ⇒ Object
-
#pop ⇒ Deque
Return a new ‘Deque` with the last item removed.
- #pretty_print(pp) ⇒ Object
-
#push(item) ⇒ Deque
(also: #enqueue)
Return a new ‘Deque` with `item` added at the end.
-
#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 ⇒ Hamster::List
Return a List with the same elements, in the same order.
-
#unshift(item) ⇒ Deque
Return a new ‘Deque` with `item` added at the front.
Methods included from Immutable
Constructor Details
Class Method Details
.[](*items) ⇒ Deque
Create a new ‘Deque` populated with the given items.
45 46 47 |
# File 'lib/hamster/deque.rb', line 45 def [](*items) items.empty? ? empty : new(items) end |
.alloc(front, rear) ⇒ Deque
“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.
63 64 65 66 67 68 |
# 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 ⇒ Deque
Return an empty ‘Deque`. If used on a subclass, returns an empty instance of that class.
53 54 55 |
# File 'lib/hamster/deque.rb', line 53 def empty @empty ||= self.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.
181 182 183 |
# File 'lib/hamster/deque.rb', line 181 def clear self.class.empty end |
#empty? ⇒ Boolean
Return ‘true` if this `Deque` contains no items.
78 79 80 |
# File 'lib/hamster/deque.rb', line 78 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`.
189 190 191 192 |
# 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 |
#first ⇒ Object
Return the first item in the ‘Deque`. If the deque is empty, return `nil`.
99 100 101 102 |
# File 'lib/hamster/deque.rb', line 99 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`.
214 215 216 217 218 219 220 |
# 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 ⇒ Object
Return the last item in the ‘Deque`. If the deque is empty, return `nil`.
110 111 112 113 |
# File 'lib/hamster/deque.rb', line 110 def last return @rear.head unless @rear.empty? @front.last # memoize? end |
#marshal_dump ⇒ ::Array
232 233 234 |
# File 'lib/hamster/deque.rb', line 232 def marshal_dump to_a end |
#marshal_load(array) ⇒ Object
237 238 239 |
# File 'lib/hamster/deque.rb', line 237 def marshal_load(array) initialize(array) end |
#pop ⇒ Deque
Return a new ‘Deque` with the last item removed.
135 136 137 138 139 140 141 142 143 144 |
# 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) ⇒ Object
223 224 225 226 227 228 |
# 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) ⇒ Deque Also known as: enqueue
Return a new ‘Deque` with `item` added at the end.
123 124 125 |
# File 'lib/hamster/deque.rb', line 123 def push(item) self.class.alloc(@front, @rear.cons(item)) end |
#shift ⇒ Deque Also known as: dequeue
Return a new ‘Deque` with the first item removed.
165 166 167 168 169 170 171 172 173 174 |
# 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 |
#size ⇒ Integer Also known as: length
Return the number of items in this ‘Deque`.
88 89 90 |
# File 'lib/hamster/deque.rb', line 88 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.
197 198 199 |
# File 'lib/hamster/deque.rb', line 197 def to_a @front.to_a.concat(@rear.to_a.tap { |a| a.reverse! }) end |
#to_list ⇒ Hamster::List
Return a List with the same elements, in the same order.
205 206 207 |
# File 'lib/hamster/deque.rb', line 205 def to_list @front.append(@rear.reverse) end |
#unshift(item) ⇒ Deque
Return a new ‘Deque` with `item` added at the front.
154 155 156 |
# File 'lib/hamster/deque.rb', line 154 def unshift(item) self.class.alloc(@front.cons(item), @rear) end |