class Immutable::Vector
A `Vector` is an ordered, integer-indexed collection of objects. Like Ruby's `Array`, `Vector` indexing starts at zero and negative indexes count back from the end.
`Vector` has a similar interface to `Array`. The main difference is methods that would destructively update an `Array` (such as {#insert} or {#delete_at}) instead return new `Vectors` and leave the existing one unchanged.
### Creating New Vectors
Immutable::Vector.new([:first, :second, :third]) Immutable::Vector[1, 2, 3, 4, 5]
### Retrieving Items from Vectors
vector = Immutable::Vector[1, 2, 3, 4, 5] vector[0] # => 1 vector[-1] # => 5 vector[0,3] # => Immutable::Vector[1, 2, 3] vector[1..-1] # => Immutable::Vector[2, 3, 4, 5] vector.first # => 1 vector.last # => 5
### Creating Modified Vectors
vector.add(6) # => Immutable::Vector[1, 2, 3, 4, 5, 6] vector.insert(1, :a, :b) # => Immutable::Vector[1, :a, :b, 2, 3, 4, 5] vector.delete_at(2) # => Immutable::Vector[1, 2, 4, 5] vector + [6, 7] # => Immutable::Vector[1, 2, 3, 4, 5, 6, 7]
Constants
- BITS_PER_LEVEL
@private
- BLOCK_SIZE
@private
- INDEX_MASK
@private
Attributes
Return the number of items in this `Vector` @return [Integer]
Return the number of items in this `Vector` @return [Integer]
Public Class Methods
Create a new `Vector` populated with the given items. @return [Vector]
# File lib/immutable/vector.rb, line 56 def [](*items) new(items.freeze) end
“Raw” allocation of a new `Vector`. Used internally to create a new instance quickly after building a modified trie.
@return [Vector] @private
# File lib/immutable/vector.rb, line 73 def alloc(root, size, levels) obj = allocate obj.instance_variable_set(:@root, root) obj.instance_variable_set(:@size, size) obj.instance_variable_set(:@levels, levels) obj.freeze end
Return an empty `Vector`. If used on a subclass, returns an empty instance of that class.
@return [Vector]
# File lib/immutable/vector.rb, line 64 def empty @empty ||= self.new end
# File lib/immutable/vector.rb, line 82 def initialize(items=[].freeze) items = items.to_a if items.size <= 32 items = items.dup.freeze if !items.frozen? @root, @size, @levels = items, items.size, 0 else root, size, levels = items, items.size, 0 while root.size > 32 root = root.each_slice(32).to_a levels += 1 end @root, @size, @levels = root.freeze, size, levels end freeze end
Public Instance Methods
Repetition. Return a new `Vector` built by concatenating `times` copies of this one together.
@example
Immutable::Vector["A", "B"] * 3 # => Immutable::Vector["A", "B", "A", "B", "A", "B"]
@param times [Integer] The number of times to repeat the elements in this vector @return [Vector]
# File lib/immutable/vector.rb, line 778 def *(times) return self.class.empty if times == 0 return self if times == 1 result = (to_a * times) result.is_a?(Array) ? self.class.new(result) : result end
Return a new `Vector` built by concatenating this one with `other`. `other` can be any object which is convertible to an `Array` using `#to_a`.
@example
Immutable::Vector["A", "B", "C"] + ["D", "E"] # => Immutable::Vector["A", "B", "C", "D", "E"]
@param other [Enumerable] The collection to concatenate onto this vector @return [Vector]
# File lib/immutable/vector.rb, line 631 def +(other) other = other.to_a other = other.dup if other.frozen? replace_suffix(@size, other) end
Return a new `Vector` with `item` added after the last occupied position.
@example
Immutable::Vector[1, 2].add(99) # => Immutable::Vector[1, 2, 99]
@param item [Object] The object to insert at the end of the vector @return [Vector]
# File lib/immutable/vector.rb, line 132 def add(item) update_root(@size, item) end
Assumes all elements are nested, indexable collections, and searches through them, comparing `obj` with the first element of each nested collection. Return the first nested collection which matches, or `nil` if none is found. Behaviour is undefined when elements do not meet assumptions (i.e. are not indexable collections).
@example
v = Immutable::Vector[["A", 10], ["B", 20], ["C", 30]] v.assoc("B") # => ["B", 20]
@param obj [Object] The object to search for @return [Object]
# File lib/immutable/vector.rb, line 1263 def assoc(obj) each do |array| next if !array.respond_to?(:[]) return array if obj == array[0] end nil end
Finds a value from this `Vector` which meets the condition defined by the provided block, using a binary search. The vector must already be sorted with respect to the block. See Ruby's `Array#bsearch` for details, behaviour is equivalent.
@example
v = Immutable::Vector[1, 3, 5, 7, 9, 11, 13] # Block returns true/false for exact element match: v.bsearch { |e| e > 4 } # => 5 # Block returns number to match an element in 4 <= e <= 7: v.bsearch { |e| 1 - e / 4 } # => 7
@yield Once for at most `log n` elements, where `n` is the size of the
vector. The exact elements and ordering are undefined.
@yieldreturn [Boolean] `true` if this element matches the criteria, `false` otherwise. @yieldreturn [Integer] See `Array#bsearch` for details. @yieldparam [Object] element element to be evaluated @return [Object] The matched element, or `nil` if none found. @raise TypeError if the block returns a non-numeric, non-boolean, non-nil
value.
# File lib/immutable/vector.rb, line 1157 def bsearch return enum_for(:bsearch) if not block_given? low, high, result = 0, @size, nil while low < high mid = (low + ((high - low) >> 1)) val = get(mid) v = yield val if v.is_a? Numeric if v == 0 return val elsif v > 0 high = mid else low = mid + 1 end elsif v == true result = val high = mid elsif !v low = mid + 1 else raise TypeError, "wrong argument type #{v.class} (must be numeric, true, false, or nil)" end end result end
Return an empty `Vector` instance, of the same class as this one. Useful if you have multiple subclasses of `Vector` and want to treat them polymorphically.
@return [Vector]
# File lib/immutable/vector.rb, line 1188 def clear self.class.empty end
When invoked with a block, yields all combinations of length `n` of items from the `Vector`, and then returns `self`. There is no guarantee about which order the combinations will be yielded.
If no block is given, an `Enumerator` is returned instead.
@example
v = Immutable::Vector[5, 6, 7, 8] v.combination(3) { |c| puts "Combination: #{c}" } Combination: [5, 6, 7] Combination: [5, 6, 8] Combination: [5, 7, 8] Combination: [6, 7, 8] #=> Immutable::Vector[5, 6, 7, 8]
@return [self, Enumerator]
# File lib/immutable/vector.rb, line 857 def combination(n) return enum_for(:combination, n) if not block_given? return self if n < 0 || @size < n if n == 0 yield [] elsif n == 1 each { |item| yield [item] } elsif n == @size yield self.to_a else combos = lambda do |result,index,remaining| while @size - index > remaining if remaining == 1 yield result.dup << get(index) else combos[result.dup << get(index), index+1, remaining-1] end index += 1 end index.upto(@size-1) { |i| result << get(i) } yield result end combos[[], 0, n] end self end
Return a new `Vector` with all items which are equal to `obj` removed. `#==` is used for checking equality.
@example
Immutable::Vector["C", "B", "A", "B"].delete("B") # => Immutable::Vector["C", "A"]
@param obj [Object] The object to remove (every occurrence) @return [Vector]
# File lib/immutable/vector.rb, line 504 def delete(obj) select { |item| item != obj } end
Return a new `Vector` with the element at `index` removed. If the given `index` does not exist, return `self`.
@example
Immutable::Vector["A", "B", "C", "D"].delete_at(2) # => Immutable::Vector["A", "B", "D"]
@param index [Integer] The index to remove @return [Vector]
# File lib/immutable/vector.rb, line 400 def delete_at(index) return self if index >= @size || index < -@size index += @size if index < 0 suffix = flatten_suffix(@root, @levels * BITS_PER_LEVEL, index, []) replace_suffix(index, suffix.tap { |a| a.shift }) end
Return the value of successively indexing into a nested collection. If any of the keys is not present, return `nil`.
@example
v = Immutable::Vector[9, Immutable::Hash[c: 'a', d: 4]] v.dig(1, :c) # => "a" v.dig(1, :f) # => nil
@return [Object]
# File lib/immutable/vector.rb, line 291 def dig(key, *rest) value = self[key] if rest.empty? || value.nil? value else value.dig(*rest) end end
Drop the first `n` elements and return the rest in a new `Vector`.
@example
Immutable::Vector["A", "B", "C", "D", "E", "F"].drop(2) # => Immutable::Vector["C", "D", "E", "F"]
@param n [Integer] The number of elements to remove @return [Vector] @raise ArgumentError if `n` is negative.
# File lib/immutable/vector.rb, line 721 def drop(n) return self if n == 0 return self.class.empty if n >= @size raise ArgumentError, "attempt to drop negative size" if n < 0 self.class.new(flatten_suffix(@root, @levels * BITS_PER_LEVEL, n, [])) end
Drop elements up to, but not including, the first element for which the block returns `nil` or `false`. Gather the remaining elements into a new `Vector`. If no block is given, an `Enumerator` is returned instead.
@example
Immutable::Vector[1, 3, 5, 7, 6, 4, 2].drop_while { |e| e < 5 } # => Immutable::Vector[5, 7, 6, 4, 2]
@return [Vector, Enumerator]
# File lib/immutable/vector.rb, line 750 def drop_while return enum_for(:drop_while) if not block_given? self.class.new(super) end
Return `self`. Since this is an immutable object duplicates are equivalent. @return [Vector]
# File lib/immutable/vector.rb, line 1325 def dup self end
Call the given block once for each item in the vector, passing each item from first to last successively to the block. If no block is given, an `Enumerator` is returned instead.
@example
Immutable::Vector["A", "B", "C"].each { |e| puts "Element: #{e}" } Element: A Element: B Element: C # => Immutable::Vector["A", "B", "C"]
@return [self, Enumerator]
# File lib/immutable/vector.rb, line 457 def each(&block) return to_enum unless block_given? traverse_depth_first(@root, @levels, &block) self end
Return `true` if this `Vector` contains no items.
@return [Boolean]
# File lib/immutable/vector.rb, line 101 def empty? @size == 0 end
Return true if `other` has the same type and contents as this `Vector`.
@param other [Object] The collection to compare with @return [Boolean]
# File lib/immutable/vector.rb, line 1310 def eql?(other) return true if other.equal?(self) return false unless instance_of?(other.class) && @size == other.size @root.eql?(other.instance_variable_get(:@root)) end
Retrieve the value at `index` with optional default.
@overload fetch(index)
Retrieve the value at the given index, or raise an `IndexError` if not found. @param index [Integer] The index to look up @raise [IndexError] if index does not exist @example v = Immutable::Vector["A", "B", "C", "D"] v.fetch(2) # => "C" v.fetch(-1) # => "D" v.fetch(4) # => IndexError: index 4 outside of vector bounds
@overload fetch(index) { |index| … }
Retrieve the value at the given index, or return the result of yielding the block if not found. @yield Once if the index is not found. @yieldparam [Integer] index The index which does not exist @yieldreturn [Object] Default value to return @param index [Integer] The index to look up @example v = Immutable::Vector["A", "B", "C", "D"] v.fetch(2) { |i| i * i } # => "C" v.fetch(4) { |i| i * i } # => 16
@overload fetch(index, default)
Retrieve the value at the given index, or return the provided `default` value if not found. @param index [Integer] The index to look up @param default [Object] Object to return if the key is not found @example v = Immutable::Vector["A", "B", "C", "D"] v.fetch(2, "Z") # => "C" v.fetch(4, "Z") # => "Z"
@return [Object]
# File lib/immutable/vector.rb, line 270 def fetch(index, default = (missing_default = true)) if index >= -@size && index < @size get(index) elsif block_given? yield(index) elsif !missing_default default else raise IndexError, "index #{index} outside of vector bounds" end end
Replace a range of indexes with the given object.
@overload fill(object)
Return a new `Vector` of the same size, with every index set to `object`. @param [Object] object Fill value. @example Immutable::Vector["A", "B", "C", "D", "E", "F"].fill("Z") # => Immutable::Vector["Z", "Z", "Z", "Z", "Z", "Z"]
@overload fill(object, index)
Return a new `Vector` with all indexes from `index` to the end of the vector set to `object`. @param [Object] object Fill value. @param [Integer] index Starting index. May be negative. @example Immutable::Vector["A", "B", "C", "D", "E", "F"].fill("Z", 3) # => Immutable::Vector["A", "B", "C", "Z", "Z", "Z"]
@overload fill(object, index, length)
Return a new `Vector` with `length` indexes, beginning from `index`, set to `object`. Expands the `Vector` if `length` would extend beyond the current length. @param [Object] object Fill value. @param [Integer] index Starting index. May be negative. @param [Integer] length @example Immutable::Vector["A", "B", "C", "D", "E", "F"].fill("Z", 3, 2) # => Immutable::Vector["A", "B", "C", "Z", "Z", "F"] Immutable::Vector["A", "B"].fill("Z", 1, 5) # => Immutable::Vector["A", "Z", "Z", "Z", "Z", "Z"]
@return [Vector] @raise [IndexError] if index is out of negative range.
# File lib/immutable/vector.rb, line 822 def fill(object, index = 0, length = nil) raise IndexError if index < -@size index += @size if index < 0 length ||= @size - index # to the end of the array, if no length given if index < @size suffix = flatten_suffix(@root, @levels * BITS_PER_LEVEL, index, []) suffix.fill(object, 0, length) elsif index == @size suffix = Array.new(length, object) else suffix = Array.new(index - @size, nil).concat(Array.new(length, object)) index = @size end replace_suffix(index, suffix) end
Return the first item in the `Vector`. If the vector is empty, return `nil`.
@example
Immutable::Vector["A", "B", "C"].first # => "A"
@return [Object]
# File lib/immutable/vector.rb, line 111 def first get(0) end
Return a new `Vector` with the concatenated results of running the block once for every element in this `Vector`.
@example
Immutable::Vector[1, 2, 3].flat_map { |x| [x, -x] } # => Immutable::Vector[1, -1, 2, -2, 3, -3]
@return [Vector]
# File lib/immutable/vector.rb, line 531 def flat_map return enum_for(:flat_map) if not block_given? return self if empty? self.class.new(super) end
Return a new `Vector` with all nested vectors and arrays recursively “flattened out”. That is, their elements inserted into the new `Vector` in the place where the nested array/vector originally was. If an optional `level` argument is provided, the flattening will only be done recursively that number of times. A `level` of 0 means not to flatten at all, 1 means to only flatten nested arrays/vectors which are directly contained within this `Vector`.
@example
v = Immutable::Vector["A", Immutable::Vector["B", "C", Immutable::Vector["D"]]] v.flatten(1) # => Immutable::Vector["A", "B", "C", Immutable::Vector["D"]] v.flatten # => Immutable::Vector["A", "B", "C", "D"]
@param level [Integer] The depth to which flattening should be applied @return [Vector]
# File lib/immutable/vector.rb, line 610 def flatten(level = -1) return self if level == 0 array = self.to_a if array.frozen? self.class.new(array.flatten(level).freeze) elsif array.flatten!(level) # returns nil if no changes were made self.class.new(array.freeze) else self end end
Retrieve the item at `index`. If there is none (either the provided index is too high or too low), return `nil`.
@example
v = Immutable::Vector["A", "B", "C", "D"] v.get(2) # => "C" v.get(-1) # => "D" v.get(4) # => nil
@param index [Integer] The index to retrieve @return [Object]
# File lib/immutable/vector.rb, line 223 def get(index) return nil if @size == 0 index += @size if index < 0 return nil if index >= @size || index < 0 leaf_node_for(@root, @levels * BITS_PER_LEVEL, index)[index & INDEX_MASK] end
See `Object#hash`. @return [Integer]
# File lib/immutable/vector.rb, line 1318 def hash reduce(0) { |hash, item| (hash << 5) - hash + item.hash } end
Return a new `Vector` with the given values inserted before the element at `index`. If `index` is greater than the current length, `nil` values are added to pad the `Vector` to the required size.
@example
Immutable::Vector["A", "B", "C", "D"].insert(2, "X", "Y", "Z") # => Immutable::Vector["A", "B", "X", "Y", "Z", "C", "D"] Immutable::Vector[].insert(2, "X", "Y", "Z") # => Immutable::Vector[nil, nil, "X", "Y", "Z"]
@param index [Integer] The index where the new items should go @param items [Array] The items to add @return [Vector] @raise [IndexError] if index exceeds negative range.
# File lib/immutable/vector.rb, line 374 def insert(index, *items) raise IndexError if index < -@size index += @size if index < 0 if index < @size suffix = flatten_suffix(@root, @levels * BITS_PER_LEVEL, index, []) suffix.unshift(*items) elsif index == @size suffix = items else suffix = Array.new(index - @size, nil).concat(items) index = @size end replace_suffix(index, suffix) end
Return the last item in the `Vector`. If the vector is empty, return `nil`.
@example
Immutable::Vector["A", "B", "C"].last # => "C"
@return [Object]
# File lib/immutable/vector.rb, line 121 def last get(-1) end
Invoke the given block once for each item in the vector, and return a new `Vector` containing the values returned by the block. If no block is provided, return an enumerator.
@example
Immutable::Vector[3, 2, 1].map { |e| e * e } # => Immutable::Vector[9, 4, 1]
@return [Vector, Enumerator]
# File lib/immutable/vector.rb, line 516 def map return enum_for(:map) if not block_given? return self if empty? self.class.new(super) end
@return [::Array] @private
# File lib/immutable/vector.rb, line 1332 def marshal_dump to_a end
@private
# File lib/immutable/vector.rb, line 1337 def marshal_load(array) initialize(array.freeze) end
Yields all permutations of length `n` of items from the `Vector`, and then returns `self`. If no length `n` is specified, permutations of all elements will be yielded.
There is no guarantee about which order the permutations will be yielded in.
If no block is given, an `Enumerator` is returned instead.
@example
v = Immutable::Vector[5, 6, 7] v.permutation(2) { |p| puts "Permutation: #{p}" } Permutation: [5, 6] Permutation: [5, 7] Permutation: [6, 5] Permutation: [6, 7] Permutation: [7, 5] Permutation: [7, 6] # => Immutable::Vector[5, 6, 7]
@return [self, Enumerator]
# File lib/immutable/vector.rb, line 960 def permutation(n = @size) return enum_for(:permutation, n) if not block_given? if n < 0 || @size < n # yield nothing elsif n == 0 yield [] elsif n == 1 each { |item| yield [item] } else used, result = [], [] perms = lambda do |index| 0.upto(@size-1) do |i| if !used[i] result[index] = get(i) if index < n-1 used[i] = true perms[index+1] used[i] = false else yield result.dup end end end end perms[0] end self end
Return a new `Vector` with the last element removed. Return `self` if empty.
@example
Immutable::Vector["A", "B", "C"].pop # => Immutable::Vector["A", "B"]
@return [Vector]
# File lib/immutable/vector.rb, line 415 def pop return self if @size == 0 replace_suffix(@size-1, []) end
Cartesian product or multiplication.
@overload product(*vectors)
Return a `Vector` of all combinations of elements from this `Vector` and each of the given vectors or arrays. The length of the returned `Vector` is the product of `self.size` and the size of each argument vector or array. @example v1 = Immutable::Vector[1, 2, 3] v2 = Immutable::Vector["A", "B"] v1.product(v2) # => [[1, "A"], [1, "B"], [2, "A"], [2, "B"], [3, "A"], [3, "B"]]
@overload product
Return the result of multiplying all the items in this `Vector` together. @example Immutable::Vector[1, 2, 3, 4, 5].product # => 120
@return [Vector]
Immutable::Enumerable#product
# File lib/immutable/vector.rb, line 1058 def product(*vectors) # if no vectors passed, return "product" as in result of multiplying all items return super if vectors.empty? vectors.unshift(self) if vectors.any?(&:empty?) return block_given? ? self : [] end counters = Array.new(vectors.size, 0) bump_counters = lambda do i = vectors.size-1 counters[i] += 1 while counters[i] == vectors[i].size counters[i] = 0 i -= 1 return true if i == -1 # we are done counters[i] += 1 end false # not done yet end build_array = lambda do array = [] counters.each_with_index { |index,i| array << vectors[i][index] } array end if block_given? while true yield build_array[] return self if bump_counters[] end else result = [] while true result << build_array[] return result if bump_counters[] end end end
Assumes all elements are nested, indexable collections, and searches through them, comparing `obj` with the second element of each nested collection. Return the first nested collection which matches, or `nil` if none is found. Behaviour is undefined when elements do not meet assumptions (i.e. are not indexable collections).
@example
v = Immutable::Vector[["A", 10], ["B", 20], ["C", 30]] v.rassoc(20) # => ["B", 20]
@param obj [Object] The object to search for @return [Object]
# File lib/immutable/vector.rb, line 1283 def rassoc(obj) each do |array| next if !array.respond_to?(:[]) return array if obj == array[1] end nil end
When invoked with a block, yields all repeated combinations of length `n` of items from the `Vector`, and then returns `self`. A “repeated combination” is one in which any item from the `Vector` can appear consecutively any number of times.
There is no guarantee about which order the combinations will be yielded in.
If no block is given, an `Enumerator` is returned instead.
@example
v = Immutable::Vector[5, 6, 7, 8] v.repeated_combination(2) { |c| puts "Combination: #{c}" } Combination: [5, 5] Combination: [5, 6] Combination: [5, 7] Combination: [5, 8] Combination: [6, 6] Combination: [6, 7] Combination: [6, 8] Combination: [7, 7] Combination: [7, 8] Combination: [8, 8] # => Immutable::Vector[5, 6, 7, 8]
@return [self, Enumerator]
# File lib/immutable/vector.rb, line 910 def repeated_combination(n) return enum_for(:repeated_combination, n) if not block_given? if n < 0 # yield nothing elsif n == 0 yield [] elsif n == 1 each { |item| yield [item] } elsif @size == 0 # yield nothing else combos = lambda do |result,index,remaining| while index < @size-1 if remaining == 1 yield result.dup << get(index) else combos[result.dup << get(index), index, remaining-1] end index += 1 end item = get(index) remaining.times { result << item } yield result end combos[[], 0, n] end self end
When invoked with a block, yields all repeated permutations of length `n` of items from the `Vector`, and then returns `self`. A “repeated permutation” is one where any item from the `Vector` can appear any number of times, and in any position (not just consecutively)
If no length `n` is specified, permutations of all elements will be yielded. There is no guarantee about which order the permutations will be yielded in.
If no block is given, an `Enumerator` is returned instead.
@example
v = Immutable::Vector[5, 6, 7] v.repeated_permutation(2) { |p| puts "Permutation: #{p}" } Permutation: [5, 5] Permutation: [5, 6] Permutation: [5, 7] Permutation: [6, 5] Permutation: [6, 6] Permutation: [6, 7] Permutation: [7, 5] Permutation: [7, 6] Permutation: [7, 7] # => Immutable::Vector[5, 6, 7]
@return [self, Enumerator]
# File lib/immutable/vector.rb, line 1015 def repeated_permutation(n = @size) return enum_for(:repeated_permutation, n) if not block_given? if n < 0 # yield nothing elsif n == 0 yield [] elsif n == 1 each { |item| yield [item] } else result = [] perms = lambda do |index| 0.upto(@size-1) do |i| result[index] = get(i) if index < n-1 perms[index+1] else yield result.dup end end end perms[0] end self end
Return a new `Vector` with the same elements as this one, but in reverse order.
@example
Immutable::Vector["A", "B", "C"].reverse # => Immutable::Vector["C", "B", "A"]
@return [Vector]
# File lib/immutable/vector.rb, line 572 def reverse self.class.new(((array = to_a).frozen? ? array.reverse : array.reverse!).freeze) end
Call the given block once for each item in the vector, from last to first.
@example
Immutable::Vector["A", "B", "C"].reverse_each { |e| puts "Element: #{e}" } Element: C Element: B Element: A
@return [self]
# File lib/immutable/vector.rb, line 474 def reverse_each(&block) return enum_for(:reverse_each) unless block_given? reverse_traverse_depth_first(@root, @levels, &block) self end
Find the index of an element, starting from the end of the vector. Returns `nil` if no element is found.
@overload rindex(obj)
Return the index of the last element which is `#==` to `obj`. @example v = Immutable::Vector[7, 8, 9, 7, 8, 9] v.rindex(8) # => 4
@overload rindex
Return the index of the last element for which the block returns true. @yield [element] Once for each element, last to first, until the block returns true. @example v = Immutable::Vector[7, 8, 9, 7, 8, 9] v.rindex { |e| e.even? } # => 4
@return [Integer]
# File lib/immutable/vector.rb, line 1236 def rindex(obj = (missing_arg = true)) i = @size - 1 if missing_arg if block_given? reverse_each { |item| return i if yield item; i -= 1 } nil else enum_for(:rindex) end else reverse_each { |item| return i if item == obj; i -= 1 } nil end end
Return a new `Vector` with the same elements, but rotated so that the one at index `count` is the first element of the new vector. If `count` is positive, the elements will be shifted left, and those shifted past the lowest position will be moved to the end. If `count` is negative, the elements will be shifted right, and those shifted past the last position will be moved to the beginning.
@example
v = Immutable::Vector["A", "B", "C", "D", "E", "F"] v.rotate(2) # => Immutable::Vector["C", "D", "E", "F", "A", "B"] v.rotate(-1) # => Immutable::Vector["F", "A", "B", "C", "D", "E"]
@param count [Integer] The number of positions to shift items by @return [Vector]
# File lib/immutable/vector.rb, line 589 def rotate(count = 1) return self if (count % @size) == 0 self.class.new(((array = to_a).frozen? ? array.rotate(count) : array.rotate!(count)).freeze) end
Return a randomly chosen item from this `Vector`. If the vector is empty, return `nil`.
@example
Immutable::Vector[1, 2, 3, 4, 5].sample # => 2
@return [Object]
# File lib/immutable/vector.rb, line 1198 def sample get(rand(@size)) end
Return a new `Vector` containing all elements for which the given block returns true.
@example
Immutable::Vector["Bird", "Cow", "Elephant"].select { |e| e.size >= 4 } # => Immutable::Vector["Bird", "Elephant"]
@return [Vector] @yield [element] Once for each element.
# File lib/immutable/vector.rb, line 489 def select return enum_for(:select) unless block_given? reduce(self.class.empty) { |vector, item| yield(item) ? vector.add(item) : vector } end
Return a new `Vector` with a new value at the given `index`. If `index` is greater than the length of the vector, the returned vector will be padded with `nil`s to the correct size.
@overload set(index, item)
Return a new `Vector` with the item at `index` replaced by `item`. @param item [Object] The object to insert into that position @example Immutable::Vector[1, 2, 3, 4].set(2, 99) # => Immutable::Vector[1, 2, 99, 4] Immutable::Vector[1, 2, 3, 4].set(-1, 99) # => Immutable::Vector[1, 2, 3, 99] Immutable::Vector[].set(2, 99) # => Immutable::Vector[nil, nil, 99]
@overload set(index)
Return a new `Vector` with the item at `index` replaced by the return value of the block. @yield (existing) Once with the existing value at the given `index`. @example Immutable::Vector[1, 2, 3, 4].set(2) { |v| v * 10 } # => Immutable::Vector[1, 2, 30, 4]
@param index [Integer] The index to update. May be negative. @return [Vector]
# File lib/immutable/vector.rb, line 165 def set(index, item = yield(get(index))) raise IndexError, "index #{index} outside of vector bounds" if index < -@size index += @size if index < 0 if index > @size suffix = Array.new(index - @size, nil) suffix << item replace_suffix(@size, suffix) else update_root(index, item) end end
Return a new `Vector` with the first element removed. If empty, return `self`.
@example
Immutable::Vector["A", "B", "C"].shift # => Immutable::Vector["B", "C"]
@return [Vector]
# File lib/immutable/vector.rb, line 440 def shift delete_at(0) end
Return a new `Vector` with the same elements as this one, but randomly permuted.
@example
Immutable::Vector[1, 2, 3, 4].shuffle # => Immutable::Vector[4, 1, 3, 2]
@return [Vector]
# File lib/immutable/vector.rb, line 543 def shuffle self.class.new(((array = to_a).frozen? ? array.shuffle : array.shuffle!).freeze) end
Return specific objects from the `Vector`. All overloads return `nil` if the starting index is out of range.
@overload vector.slice(index)
Returns a single object at the given `index`. If `index` is negative, count backwards from the end. @param index [Integer] The index to retrieve. May be negative. @return [Object] @example v = Immutable::Vector["A", "B", "C", "D", "E", "F"] v[2] # => "C" v[-1] # => "F" v[6] # => nil
@overload vector.slice(index, length)
Return a subvector starting at `index` and continuing for `length` elements or until the end of the `Vector`, whichever occurs first. @param start [Integer] The index to start retrieving items from. May be negative. @param length [Integer] The number of items to retrieve. @return [Vector] @example v = Immutable::Vector["A", "B", "C", "D", "E", "F"] v[2, 3] # => Immutable::Vector["C", "D", "E"] v[-2, 3] # => Immutable::Vector["E", "F"] v[20, 1] # => nil
@overload vector.slice(index..end)
Return a subvector starting at `index` and continuing to index `end` or the end of the `Vector`, whichever occurs first. @param range [Range] The range of indices to retrieve. @return [Vector] @example v = Immutable::Vector["A", "B", "C", "D", "E", "F"] v[2..3] # => Immutable::Vector["C", "D"] v[-2..100] # => Immutable::Vector["E", "F"] v[20..21] # => nil
# File lib/immutable/vector.rb, line 340 def slice(arg, length = (missing_length = true)) if missing_length if arg.is_a?(Range) from, to = arg.begin, arg.end from += @size if from < 0 to += @size if to < 0 to += 1 if !arg.exclude_end? length = to - from length = 0 if length < 0 subsequence(from, length) else get(arg) end else arg += @size if arg < 0 subsequence(arg, length) end end
Return a new `Vector` with the same items, but sorted.
@overload sort
Compare elements with their natural sort key (`#<=>`). @example Immutable::Vector["Elephant", "Dog", "Lion"].sort # => Immutable::Vector["Dog", "Elephant", "Lion"]
@overload sort
Uses the block as a comparator to determine sorted order. @yield [a, b] Any number of times with different pairs of elements. @yieldreturn [Integer] Negative if the first element should be sorted lower, positive if the latter element, or 0 if equal. @example Immutable::Vector["Elephant", "Dog", "Lion"].sort { |a,b| a.size <=> b.size } # => Immutable::Vector["Dog", "Lion", "Elephant"]
@return [Vector]
# File lib/immutable/vector.rb, line 692 def sort self.class.new(super) end
Return a new `Vector` with the same items, but sorted. The sort order is determined by mapping the items through the given block to obtain sort keys, and then sorting the keys according to their natural sort order (`#<=>`).
@yield [element] Once for each element. @yieldreturn a sort key object for the yielded element. @example
Immutable::Vector["Elephant", "Dog", "Lion"].sort_by { |e| e.size } # => Immutable::Vector["Dog", "Lion", "Elephant"]
@return [Vector]
Immutable::Enumerable#sort_by
# File lib/immutable/vector.rb, line 708 def sort_by self.class.new(super) end
Return only the first `n` elements in a new `Vector`.
@example
Immutable::Vector["A", "B", "C", "D", "E", "F"].take(4) # => Immutable::Vector["A", "B", "C", "D"]
@param n [Integer] The number of elements to retain @return [Vector]
# File lib/immutable/vector.rb, line 736 def take(n) return self if n >= @size self.class.new(super) end
Gather elements up to, but not including, the first element for which the block returns `nil` or `false`, and return them in a new `Vector`. If no block is given, an `Enumerator` is returned instead.
@example
Immutable::Vector[1, 3, 5, 7, 6, 4, 2].take_while { |e| e < 5 } # => Immutable::Vector[1, 3]
@return [Vector, Enumerator]
# File lib/immutable/vector.rb, line 764 def take_while return enum_for(:take_while) if not block_given? self.class.new(super) end
Return an `Array` with the same elements, in the same order. The returned `Array` may or may not be frozen.
@return [Array]
# File lib/immutable/vector.rb, line 1295 def to_a if @levels == 0 # When initializing a Vector with 32 or less items, we always make # sure @root is frozen, so we can return it directly here @root else flatten_node(@root, @levels * BITS_PER_LEVEL, []) end end
Assume all elements are vectors or arrays and transpose the rows and columns. In other words, take the first element of each nested vector/array and gather them together into a new `Vector`. Do likewise for the second, third, and so on down to the end of each nested vector/array. Gather all the resulting `Vectors` into a new `Vector` and return it.
This operation is closely related to {#zip}. The result is almost the same as calling {#zip} on the first nested vector/array with the others supplied as arguments.
@example
Immutable::Vector[["A", 10], ["B", 20], ["C", 30]].transpose # => Immutable::Vector[Immutable::Vector["A", "B", "C"], Immutable::Vector[10, 20, 30]]
@return [Vector] @raise [IndexError] if elements are not of the same size. @raise [TypeError] if an element can not be implicitly converted to an array (using `#to_ary`)
# File lib/immutable/vector.rb, line 1118 def transpose return self.class.empty if empty? result = Array.new(first.size) { [] } 0.upto(@size-1) do |i| source = get(i) if source.size != result.size raise IndexError, "element size differs (#{source.size} should be #{result.size})" end 0.upto(result.size-1) do |j| result[j].push(source[j]) end end result.map! { |a| self.class.new(a) } self.class.new(result) end
Return a new `Vector` with no duplicate elements, as determined by `#hash` and `#eql?`. For each group of equivalent elements, only the first will be retained.
@example
Immutable::Vector["A", "B", "C", "B"].uniq # => Immutable::Vector["A", "B", "C"] Immutable::Vector["a", "A", "b"].uniq(&:upcase) # => Immutable::Vector["a", "b"]
@return [Vector]
# File lib/immutable/vector.rb, line 555 def uniq(&block) array = self.to_a if array.frozen? self.class.new(array.uniq(&block).freeze) elsif array.uniq!(&block) # returns nil if no changes were made self.class.new(array.freeze) else self end end
Return a new `Vector` with `object` inserted before the first element, moving the other elements upwards.
@example
Immutable::Vector["A", "B"].unshift("Z") # => Immutable::Vector["Z", "A", "B"]
@param object [Object] The value to prepend @return [Vector]
# File lib/immutable/vector.rb, line 429 def unshift(object) insert(0, object) end
Return a new `Vector` with a deeply nested value modified to the result of the given code block. When traversing the nested `Vector`s and `Hash`es, non-existing keys are created with empty `Hash` values.
The code block receives the existing value of the deeply nested key (or `nil` if it doesn't exist). This is useful for “transforming” the value associated with a certain key.
Note that the original `Vector` and sub-`Vector`s and sub-`Hash`es are left unmodified; new data structure copies are created along the path wherever needed.
@example
v = Immutable::Vector[123, 456, 789, Immutable::Hash["a" => Immutable::Vector[5, 6, 7]]] v.update_in(3, "a", 1) { |value| value + 9 } # => Immutable::Vector[123, 456, 789, Immutable::Hash["a" => Immutable::Vector[5, 15, 7]]]
@param key_path [Object(s)] List
of keys which form the path to the key to be modified @yield [value] The previously stored value @yieldreturn [Object] The new value to store @return [Vector]
# File lib/immutable/vector.rb, line 198 def update_in(*key_path, &block) if key_path.empty? raise ArgumentError, "must have at least one key in path" end key = key_path[0] if key_path.size == 1 new_value = block.call(get(key)) else value = fetch(key, Immutable::EmptyHash) new_value = value.update_in(*key_path[1..-1], &block) end set(key, new_value) end
Return a new `Vector` with only the elements at the given `indices`, in the order specified by `indices`. If any of the `indices` do not exist, `nil`s will appear in their places.
@example
v = Immutable::Vector["A", "B", "C", "D", "E", "F"] v.values_at(2, 4, 5) # => Immutable::Vector["C", "E", "F"]
@param indices [Array] The indices to retrieve and gather into a new `Vector` @return [Vector]
# File lib/immutable/vector.rb, line 1212 def values_at(*indices) self.class.new(indices.map { |i| get(i) }.freeze) end
Combine two vectors by “zipping” them together. `others` should be arrays and/or vectors. The corresponding elements from this `Vector` and each of `others` (that is, the elements with the same indices) will be gathered into arrays.
If `others` contains fewer elements than this vector, `nil` will be used for padding.
@overload zip(*others)
Return a new vector containing the new arrays. @return [Vector]
@overload zip(*others)
@yield [pair] once for each array @return [nil]
@example
v1 = Immutable::Vector["A", "B", "C"] v2 = Immutable::Vector[1, 2] v1.zip(v2) # => Immutable::Vector[["A", 1], ["B", 2], ["C", nil]]
@param others [Array] The arrays/vectors to zip together with this one @return [Vector]
# File lib/immutable/vector.rb, line 663 def zip(*others) if block_given? super else self.class.new(super) end end
Private Instance Methods
# File lib/immutable/vector.rb, line 1423 def flatten_node(node, bitshift, result) if bitshift == 0 result.concat(node) elsif bitshift == BITS_PER_LEVEL node.each { |a| result.concat(a) } else bitshift -= BITS_PER_LEVEL node.each { |a| flatten_node(a, bitshift, result) } end result end
# File lib/immutable/vector.rb, line 1389 def flatten_range(node, bitshift, from, to) from_slot = (from >> bitshift) & INDEX_MASK to_slot = (to >> bitshift) & INDEX_MASK if bitshift == 0 # are we at the bottom? node.slice(from_slot, to_slot-from_slot+1) elsif from_slot == to_slot flatten_range(node[from_slot], bitshift - BITS_PER_LEVEL, from, to) else # the following bitmask can be used to pick out the part of the from/to indices # which will be used to direct path BELOW this node mask = ((1 << bitshift) - 1) result = [] if from & mask == 0 flatten_node(node[from_slot], bitshift - BITS_PER_LEVEL, result) else result.concat(flatten_range(node[from_slot], bitshift - BITS_PER_LEVEL, from, from | mask)) end (from_slot+1).upto(to_slot-1) do |slot_index| flatten_node(node[slot_index], bitshift - BITS_PER_LEVEL, result) end if to & mask == mask flatten_node(node[to_slot], bitshift - BITS_PER_LEVEL, result) else result.concat(flatten_range(node[to_slot], bitshift - BITS_PER_LEVEL, to & ~mask, to)) end result end end
# File lib/immutable/vector.rb, line 1442 def flatten_suffix(node, bitshift, from, result) from_slot = (from >> bitshift) & INDEX_MASK if bitshift == 0 if from_slot == 0 result.concat(node) else result.concat(node.slice(from_slot, 32)) # entire suffix of node. excess length is ignored by #slice end else mask = ((1 << bitshift) - 1) if from & mask == 0 from_slot.upto(node.size-1) do |i| flatten_node(node[i], bitshift - BITS_PER_LEVEL, result) end elsif child = node[from_slot] flatten_suffix(child, bitshift - BITS_PER_LEVEL, from, result) (from_slot+1).upto(node.size-1) do |i| flatten_node(node[i], bitshift - BITS_PER_LEVEL, result) end end result end end
# File lib/immutable/vector.rb, line 1353 def leaf_node_for(node, bitshift, index) while bitshift > 0 node = node[(index >> bitshift) & INDEX_MASK] bitshift -= BITS_PER_LEVEL end node end
# File lib/immutable/vector.rb, line 1499 def replace_node_suffix(node, bitshift, from, suffix) from_slot = (from >> bitshift) & INDEX_MASK if bitshift == 0 if from_slot == 0 suffix.shift(32) else node.take(from_slot).concat(suffix.shift(32 - from_slot)) end else mask = ((1 << bitshift) - 1) if from & mask == 0 if from_slot == 0 new_node = suffix.shift(32 * (1 << bitshift)) while bitshift != 0 new_node = new_node.each_slice(32).to_a bitshift -= BITS_PER_LEVEL end new_node else result = node.take(from_slot) remainder = suffix.shift((32 - from_slot) * (1 << bitshift)) while bitshift != 0 remainder = remainder.each_slice(32).to_a bitshift -= BITS_PER_LEVEL end result.concat(remainder) end elsif child = node[from_slot] result = node.take(from_slot) result.push(replace_node_suffix(child, bitshift - BITS_PER_LEVEL, from, suffix)) remainder = suffix.shift((31 - from_slot) * (1 << bitshift)) while bitshift != 0 remainder = remainder.each_slice(32).to_a bitshift -= BITS_PER_LEVEL end result.concat(remainder) else raise "Shouldn't happen" end end end
# File lib/immutable/vector.rb, line 1467 def replace_suffix(from, suffix) # new suffix can go directly after existing elements raise IndexError if from > @size root, levels = @root, @levels if (from >> (BITS_PER_LEVEL * (@levels + 1))) != 0 # index where new suffix goes doesn't fall within current tree # we will need to deepen tree root = [root].freeze levels += 1 end new_size = from + suffix.size root = replace_node_suffix(root, levels * BITS_PER_LEVEL, from, suffix) if !suffix.empty? levels.times { suffix = suffix.each_slice(32).to_a } root.concat(suffix) while root.size > 32 root = root.each_slice(32).to_a levels += 1 end else while root.size == 1 && levels > 0 root = root[0] levels -= 1 end end self.class.alloc(root.freeze, new_size, levels) end
# File lib/immutable/vector.rb, line 1348 def reverse_traverse_depth_first(node, level, &block) return node.reverse_each(&block) if level == 0 node.reverse_each { |child| reverse_traverse_depth_first(child, level - 1, &block) } end
# File lib/immutable/vector.rb, line 1435 def subsequence(from, length) return nil if from > @size || from < 0 || length < 0 length = @size - from if @size < from + length return self.class.empty if length == 0 self.class.new(flatten_range(@root, @levels * BITS_PER_LEVEL, from, from + length - 1)) end
# File lib/immutable/vector.rb, line 1343 def traverse_depth_first(node, level, &block) return node.each(&block) if level == 0 node.each { |child| traverse_depth_first(child, level - 1, &block) } end
# File lib/immutable/vector.rb, line 1375 def update_leaf_node(node, bitshift, index, item) slot_index = (index >> bitshift) & INDEX_MASK if bitshift > 0 old_child = node[slot_index] || [] item = update_leaf_node(old_child, bitshift - BITS_PER_LEVEL, index, item) end existing_item = node[slot_index] if existing_item.equal?(item) node else node.dup.tap { |n| n[slot_index] = item }.freeze end end
# File lib/immutable/vector.rb, line 1361 def update_root(index, item) root, levels = @root, @levels while index >= (1 << (BITS_PER_LEVEL * (levels + 1))) root = [root].freeze levels += 1 end new_root = update_leaf_node(root, levels * BITS_PER_LEVEL, index, item) if new_root.equal?(root) self else self.class.alloc(new_root, @size > index ? @size : index + 1, levels) end end