module BerkeleyLibrary::Util::Arrays

Public Instance Methods

count_while(values:) { |x| ... } click to toggle source

Counts how many contiguous elements from the start of an sequence of values satisfy the given block.

@overload count_while(arr:)

Returns an enumerator.
@param values [Enumerable] the values
@return [Enumerator] the enumerator.

@overload count_while(arr:, &block)

Passes elements to the block until the block returns nil or false,
then stops iterating and returns the count of matching elements.
@param values [Enumerable] the values
@return [Integer] the count
# File lib/berkeley_library/util/arrays.rb, line 32
def count_while(values:)
  return to_enum(:count_while, values: values) unless block_given?

  values.inject(0) do |count, x|
    matched = yield x
    break count unless matched

    count + 1
  end
end
find_index(*args, in_array:, start_index: 0, &block) click to toggle source

Given a block or a value, finds the index of the first matching value at or after the specified start index.

@overload find_index(value, in_array:, start_index:)

Finds the first index of the specified value.
@param value [Object] the value to find
@param in_array [Array] the array to search
@param start_index [Integer] the index to start with
@return [Integer, nil] the index, or `nil` if no value matches

@overload find_index(&block)

Finds the index of the first value matching
the specified block.
@param in_array [Array] the array to search
@param start_index [Integer] the index to start with
@yieldreturn [Boolean] whether the element matches
@return [Integer, nil] the index, or `nil` if no value matches

@overload find_index

@param in_array [Array] the array to search
@param start_index [Integer] the index to start with
@return [Enumerator] a new enumerator
# File lib/berkeley_library/util/arrays.rb, line 92
def find_index(*args, in_array:, start_index: 0, &block)
  raise ArgumentError, "wrong number of arguments (given #{value.length}, expected 0..1" if args.size > 1
  return Enumerator.new { |y| find_index(in_array: in_array, start_index: start_index, &y) } if args.empty? && !block_given?
  return unless (relative_index = in_array[start_index..].find_index(*args, &block))

  relative_index + start_index
end
find_indices(for_array:, in_array:, &block) click to toggle source

Given two lists, one of which is a superset of the other, with elements in the same order (but possibly with additional elements in the superset), returns an array the length of the subset, containing for each element in the subset the index of the corresponding element in the superset.

@overload find_matching_indices(for_array:, in_array:)

For each value in `for_array`, finds the index of the first equal value
in `in_array` after the previously matched value.
@param in_array [Array] the list of values to look in
@param for_array [Array] the values to look for
@return [Array<Integer>, nil] the indices in `in_array` of each value in `for_array`,
  or `nil` if not all values could be found

@overload find_matching_indices(for_array:, in_array:)

For each value in `for_array`, finds the index of the first value
in `in_array` after the previously matched value that matches
the specified match function.
@param in_array [Array] the list of values to look in
@param for_array [Array] the values to look for
@yieldparam source [Object] the value to compare
@yieldparam target [Object] the value to compare against
@return [Array<Integer>, nil] the indices in `in_array` of each value in `for_array`,
  or `nil` if not all values could be found
# File lib/berkeley_library/util/arrays.rb, line 66
def find_indices(for_array:, in_array:, &block)
  return find_indices_matching(for_array, in_array, &block) if block_given?

  find_all_indices(for_array, in_array)
end
invert(arr) click to toggle source

Given an array of unique integers _a<sub>1</sub>_, returns a new array _a<sub>2</sub>_ in which the value at each index _i<sub>2</sub>_ is the index _i<sub>1</sub>_ at which that value was found in _a<sub>1</sub>_. E.g., given `[0, 2, 3]`, returns `[0, nil, 1, 2]`. The indices need not be in order but must be unique.

@param arr [Array<Integer>, nil] the array to invert. @return [Array<Integer, nil>, nil] the inverted array, or nil if the input array is nil @raise TypeError if `arr` is not an array of integers @raise ArgumentError if `arr` contains duplicate values

# File lib/berkeley_library/util/arrays.rb, line 110
def invert(arr)
  return unless arr

  # noinspection RubyNilAnalysis
  Array.new(arr.size).tap do |inv|
    arr.each_with_index do |v, i|
      next inv[v] = i unless (prev_index = inv[v])

      raise ArgumentError, "Duplicate value #{v} at index #{i} already found at #{prev_index}"
    end
  end
end
merge(a1, a2) click to toggle source

Merges two arrays in an order-preserving manner. @param a1 [Array] the first array @param a2 [Array] the second array @return [Array] a merged array that is an ordered superset of both `a1` and `a2` @see Arrays#ordered_superset?

# File lib/berkeley_library/util/arrays.rb, line 128
def merge(a1, a2)
  return a1 if a2.empty?
  return a2 if a1.empty?

  shorter, longer = a1.size > a2.size ? [a2, a1] : [a1, a2]
  do_merge(shorter, longer)
end
ordered_superset?(superset:, subset:) click to toggle source

Recursively checks whether the specified list contains, in the same order, all values in the other specified list (additional codes in between are fine)

@param subset [Array] the values to look for @param superset [Array] the list of values to look in @return boolean True if all values were found, false otherwise

# File lib/berkeley_library/util/arrays.rb, line 16
def ordered_superset?(superset:, subset:)
  !find_indices(in_array: superset, for_array: subset).nil?
end

Private Instance Methods

do_merge(shorter, longer) click to toggle source
# File lib/berkeley_library/util/arrays.rb, line 138
def do_merge(shorter, longer)
  shorter.each_with_index do |v, ix_s|
    next unless (ix_l = longer.find_index(v))

    shorter_unmatched = shorter[0...ix_s]
    longer_unmatched = longer[0...ix_l]
    all_unmatched = sort_by_first_and_flatten(shorter_unmatched, longer_unmatched)
    return (all_unmatched << v) + merge(shorter[ix_s + 1..], longer[ix_l + 1..])
  end

  sort_by_first_and_flatten(longer, shorter)
end
find_all_indices(source, target) click to toggle source
# File lib/berkeley_library/util/arrays.rb, line 159
def find_all_indices(source, target)
  source.each_with_object([]) do |src, target_indices|
    target_offset = (target_indices.last&.+ 1) || 0
    return nil unless (target_index = find_index(src, in_array: target, start_index: target_offset))

    target_indices << target_index
  end
end
find_indices_matching(source, target) { |src, tgt| ... } click to toggle source
# File lib/berkeley_library/util/arrays.rb, line 168
def find_indices_matching(source, target)
  source.each_with_object([]) do |src, target_indices|
    target_offset = (target_indices.last&.+ 1) || 0
    return nil unless (target_index = find_index(in_array: target, start_index: target_offset) { |tgt| yield src, tgt })

    target_indices << target_index
  end
end
sort_by_first_and_flatten(a1, a2) click to toggle source
# File lib/berkeley_library/util/arrays.rb, line 151
def sort_by_first_and_flatten(a1, a2)
  return a1 if a2.empty?
  return a2 if a1.empty?
  return a2 + a1 if a1.first.respond_to?(:>) && a1.first > a2.first

  a1 + a2
end