/usr/lib/ruby/vendor_ruby/hamster/deque.rb is in ruby-hamster 3.0.0-2.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 | 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
|