class Array ## # call-seq: # ary.uniq! -> ary or nil # ary.uniq! { |item| ... } -> ary or nil # # Removes duplicate elements from +self+. # Returns nil if no changes are made (that is, no # duplicates are found). # # a = [ "a", "a", "b", "b", "c" ] # a.uniq! #=> ["a", "b", "c"] # b = [ "a", "b", "c" ] # b.uniq! #=> nil # c = [["student","sam"], ["student","george"], ["teacher","matz"]] # c.uniq! { |s| s.first } # => [["student", "sam"], ["teacher", "matz"]] # def uniq!(&block) hash = {} if block self.each do |val| key = block.call(val) hash[key] = val unless hash.key?(key) end result = hash.values else hash = {} self.each do |val| hash[val] = val end result = hash.keys end if result.size == self.size nil else self.replace(result) end end ## # call-seq: # ary.uniq -> new_ary # ary.uniq { |item| ... } -> new_ary # # Returns a new array by removing duplicate values in +self+. # # a = [ "a", "a", "b", "b", "c" ] # a.uniq #=> ["a", "b", "c"] # # b = [["student","sam"], ["student","george"], ["teacher","matz"]] # b.uniq { |s| s.first } # => [["student", "sam"], ["teacher", "matz"]] # def uniq(&block) ary = self[0..-1] ary.uniq!(&block) ary end ## # call-seq: # ary - other_ary -> new_ary # # Array Difference---Returns a new array that is a copy of # the original array, removing any items that also appear in # other_ary. (If you need set-like behavior, see the # library class Set.) # # [ 1, 1, 2, 2, 3, 3, 4, 5 ] - [ 1, 2, 4 ] #=> [ 3, 3, 5 ] # def -(elem) raise TypeError, "can't convert #{elem.class} into Array" unless elem.class == Array hash = {} array = [] idx = 0 len = elem.size while idx < len hash[elem[idx]] = true idx += 1 end idx = 0 len = size while idx < len v = self[idx] array << v unless hash[v] idx += 1 end array end ## # call-seq: # ary.difference(other_ary1, other_ary2, ...) -> new_ary # # Returns a new array that is a copy of the original array, removing all # occurrences of any item that also appear in +other_ary+. The order is # preserved from the original array. # def difference(*args) ary = self args.each do |x| ary = ary - x end ary end ## # call-seq: # ary | other_ary -> new_ary # # Set Union---Returns a new array by joining this array with # other_ary, removing duplicates. # # [ "a", "b", "c" ] | [ "c", "d", "a" ] # #=> [ "a", "b", "c", "d" ] # def |(elem) raise TypeError, "can't convert #{elem.class} into Array" unless elem.class == Array ary = self + elem ary.uniq! or ary end ## # call-seq: # ary.union(other_ary,...) -> new_ary # # Set Union---Returns a new array by joining this array with # other_ary, removing duplicates. # # ["a", "b", "c"].union(["c", "d", "a"], ["a", "c", "e"]) # #=> ["a", "b", "c", "d", "e"] # def union(*args) ary = self.dup args.each do |x| ary.concat(x) ary.uniq! end ary end ## # call-seq: # ary & other_ary -> new_ary # # Set Intersection---Returns a new array # containing elements common to the two arrays, with no duplicates. # # [ 1, 1, 3, 5 ] & [ 1, 2, 3 ] #=> [ 1, 3 ] # def &(elem) raise TypeError, "cannot convert #{elem.class} into Array" unless elem.class == Array hash = {} array = [] idx = 0 len = elem.size while idx < len hash[elem[idx]] = true idx += 1 end idx = 0 len = size while idx < len v = self[idx] if hash[v] array << v hash.delete v end idx += 1 end array end ## # call-seq: # ary.intersection(other_ary,...) -> new_ary # # Set Intersection---Returns a new array containing elements common to # this array and other_arys, removing duplicates. The order is # preserved from the original array. # # [1, 2, 3].intersection([3, 4, 1], [1, 3, 5]) #=> [1, 3] # def intersection(*args) ary = self args.each do |x| ary = ary & x end ary end ## # call-seq: # ary.intersect?(other_ary) -> true or false # # Returns +true+ if the array and +other_ary+ have at least one element in # common, otherwise returns +false+. # # a = [ 1, 2, 3 ] # b = [ 3, 4, 5 ] # c = [ 5, 6, 7 ] # a.intersect?(b) #=> true # a.intersect?(c) #=> false def intersect?(ary) raise TypeError, "cannot convert #{ary.class} into Array" unless ary.class == Array hash = {} if self.length > ary.length shorter = ary longer = self else shorter = self longer = ary end idx = 0 len = shorter.size while idx < len hash[shorter[idx]] = true idx += 1 end idx = 0 len = size while idx < len v = longer[idx] if hash[v] return true end idx += 1 end false end ## # call-seq: # ary.flatten -> new_ary # ary.flatten(level) -> new_ary # # Returns a new array that is a one-dimensional flattening of this # array (recursively). That is, for every element that is an array, # extract its elements into the new array. If the optional # level argument determines the level of recursion to flatten. # # s = [ 1, 2, 3 ] #=> [1, 2, 3] # t = [ 4, 5, 6, [7, 8] ] #=> [4, 5, 6, [7, 8]] # a = [ s, t, 9, 10 ] #=> [[1, 2, 3], [4, 5, 6, [7, 8]], 9, 10] # a.flatten #=> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] # a = [ 1, 2, [3, [4, 5] ] ] # a.flatten(1) #=> [1, 2, 3, [4, 5]] # def flatten(depth=nil) res = Array.new(self) res.flatten! depth res end ## # call-seq: # ary.flatten! -> ary or nil # ary.flatten!(level) -> array or nil # # Flattens +self+ in place. # Returns nil if no modifications were made (i.e., # ary contains no subarrays.) If the optional level # argument determines the level of recursion to flatten. # # a = [ 1, 2, [3, [4, 5] ] ] # a.flatten! #=> [1, 2, 3, 4, 5] # a.flatten! #=> nil # a #=> [1, 2, 3, 4, 5] # a = [ 1, 2, [3, [4, 5] ] ] # a.flatten!(1) #=> [1, 2, 3, [4, 5]] # def flatten!(depth=nil) modified = false ar = [] idx = 0 len = size while idx < len e = self[idx] if e.is_a?(Array) && (depth.nil? || depth > 0) ar += e.flatten(depth.nil? ? nil : depth - 1) modified = true else ar << e end idx += 1 end if modified self.replace(ar) else nil end end # for efficiency def reverse_each(&block) return to_enum :reverse_each unless block i = self.size - 1 while i>=0 block.call(self[i]) i -= 1 end self end ## # call-seq: # ary.fetch(index) -> obj # ary.fetch(index, default) -> obj # ary.fetch(index) { |index| block } -> obj # # Tries to return the element at position +index+, but throws an IndexError # exception if the referenced +index+ lies outside of the array bounds. This # error can be prevented by supplying a second argument, which will act as a # +default+ value. # # Alternatively, if a block is given it will only be executed when an # invalid +index+ is referenced. # # Negative values of +index+ count from the end of the array. # # a = [ 11, 22, 33, 44 ] # a.fetch(1) #=> 22 # a.fetch(-1) #=> 44 # a.fetch(4, 'cat') #=> "cat" # a.fetch(100) { |i| puts "#{i} is out of bounds" } # #=> "100 is out of bounds" # def fetch(n, ifnone=NONE, &block) #warn "block supersedes default value argument" if !n.nil? && ifnone != NONE && block idx = n if idx < 0 idx += size end if idx < 0 || size <= idx return block.call(n) if block if ifnone == NONE raise IndexError, "index #{n} outside of array bounds: #{-size}...#{size}" end return ifnone end self[idx] end ## # call-seq: # ary.fill(obj) -> ary # ary.fill(obj, start [, length]) -> ary # ary.fill(obj, range ) -> ary # ary.fill { |index| block } -> ary # ary.fill(start [, length] ) { |index| block } -> ary # ary.fill(range) { |index| block } -> ary # # The first three forms set the selected elements of +self+ (which # may be the entire array) to +obj+. # # A +start+ of +nil+ is equivalent to zero. # # A +length+ of +nil+ is equivalent to the length of the array. # # The last three forms fill the array with the value of the given block, # which is passed the absolute index of each element to be filled. # # Negative values of +start+ count from the end of the array, where +-1+ is # the last element. # # a = [ "a", "b", "c", "d" ] # a.fill("x") #=> ["x", "x", "x", "x"] # a.fill("w", -1) #=> ["x", "x", "x", "w"] # a.fill("z", 2, 2) #=> ["x", "x", "z", "z"] # a.fill("y", 0..1) #=> ["y", "y", "z", "z"] # a.fill { |i| i*i } #=> [0, 1, 4, 9] # a.fill(-2) { |i| i*i*i } #=> [0, 1, 8, 27] # a.fill(1, 2) { |i| i+1 } #=> [0, 2, 3, 27] # a.fill(0..1) { |i| i+1 } #=> [1, 2, 3, 27] # def fill(arg0=nil, arg1=nil, arg2=nil, &block) if arg0.nil? && arg1.nil? && arg2.nil? && !block raise ArgumentError, "wrong number of arguments (given 0, expected 1..3)" end beg = len = 0 if block if arg0.nil? && arg1.nil? && arg2.nil? # ary.fill { |index| block } -> ary beg = 0 len = self.size elsif !arg0.nil? && arg0.kind_of?(Range) # ary.fill(range) { |index| block } -> ary beg = arg0.begin beg += self.size if beg < 0 len = arg0.end len += self.size if len < 0 len += 1 unless arg0.exclude_end? elsif !arg0.nil? # ary.fill(start [, length] ) { |index| block } -> ary beg = arg0 beg += self.size if beg < 0 if arg1.nil? len = self.size else len = arg0 + arg1 end end else if !arg0.nil? && arg1.nil? && arg2.nil? # ary.fill(obj) -> ary beg = 0 len = self.size elsif !arg0.nil? && !arg1.nil? && arg1.kind_of?(Range) # ary.fill(obj, range ) -> ary beg = arg1.begin beg += self.size if beg < 0 len = arg1.end len += self.size if len < 0 len += 1 unless arg1.exclude_end? elsif !arg0.nil? && !arg1.nil? # ary.fill(obj, start [, length]) -> ary beg = arg1 beg += self.size if beg < 0 if arg2.nil? len = self.size else len = beg + arg2 end end end i = beg if block while i < len self[i] = block.call(i) i += 1 end else while i < len self[i] = arg0 i += 1 end end self end ## # call-seq: # ary.delete_if { |item| block } -> ary # ary.delete_if -> Enumerator # # Deletes every element of +self+ for which block evaluates to +true+. # # The array is changed instantly every time the block is called, not after # the iteration is over. # # See also Array#reject! # # If no block is given, an Enumerator is returned instead. # # scores = [ 97, 42, 75 ] # scores.delete_if {|score| score < 80 } #=> [97] def delete_if(&block) return to_enum :delete_if unless block idx = 0 while idx < self.size do if block.call(self[idx]) self.delete_at(idx) else idx += 1 end end self end ## # call-seq: # ary.reject! { |item| block } -> ary or nil # ary.reject! -> Enumerator # # Equivalent to Array#delete_if, deleting elements from +self+ for which the # block evaluates to +true+, but returns +nil+ if no changes were made. # # The array is changed instantly every time the block is called, not after # the iteration is over. # # See also Enumerable#reject and Array#delete_if. # # If no block is given, an Enumerator is returned instead. def reject!(&block) return to_enum :reject! unless block len = self.size idx = 0 while idx < self.size do if block.call(self[idx]) self.delete_at(idx) else idx += 1 end end if self.size == len nil else self end end ## # call-seq: # ary.insert(index, obj...) -> ary # # Inserts the given values before the element with the given +index+. # # Negative indices count backwards from the end of the array, where +-1+ is # the last element. # # a = %w{ a b c d } # a.insert(2, 99) #=> ["a", "b", 99, "c", "d"] # a.insert(-2, 1, 2, 3) #=> ["a", "b", 99, "c", 1, 2, 3, "d"] def insert(idx, *args) idx += self.size + 1 if idx < 0 self[idx, 0] = args self end ## # call-seq: # ary.bsearch {|x| block } -> elem # # By using binary search, finds a value from this array which meets # the given condition in O(log n) where n is the size of the array. # # You can use this method in two use cases: a find-minimum mode and # a find-any mode. In either case, the elements of the array must be # monotone (or sorted) with respect to the block. # # In find-minimum mode (this is a good choice for typical use case), # the block must return true or false, and there must be an index i # (0 <= i <= ary.size) so that: # # - the block returns false for any element whose index is less than # i, and # - the block returns true for any element whose index is greater # than or equal to i. # # This method returns the i-th element. If i is equal to ary.size, # it returns nil. # # ary = [0, 4, 7, 10, 12] # ary.bsearch {|x| x >= 4 } #=> 4 # ary.bsearch {|x| x >= 6 } #=> 7 # ary.bsearch {|x| x >= -1 } #=> 0 # ary.bsearch {|x| x >= 100 } #=> nil # # In find-any mode (this behaves like libc's bsearch(3)), the block # must return a number, and there must be two indices i and j # (0 <= i <= j <= ary.size) so that: # # - the block returns a positive number for ary[k] if 0 <= k < i, # - the block returns zero for ary[k] if i <= k < j, and # - the block returns a negative number for ary[k] if # j <= k < ary.size. # # Under this condition, this method returns any element whose index # is within i...j. If i is equal to j (i.e., there is no element # that satisfies the block), this method returns nil. # # ary = [0, 4, 7, 10, 12] # # try to find v such that 4 <= v < 8 # ary.bsearch {|x| 1 - (x / 4).truncate } #=> 4 or 7 # # try to find v such that 8 <= v < 10 # ary.bsearch {|x| 4 - (x / 2).truncate } #=> nil # # You must not mix the two modes at a time; the block must always # return either true/false, or always return a number. It is # undefined which value is actually picked up at each iteration. def bsearch(&block) return to_enum :bsearch unless block if idx = bsearch_index(&block) self[idx] else nil end end ## # call-seq: # ary.bsearch_index {|x| block } -> int or nil # # By using binary search, finds an index of a value from this array which # meets the given condition in O(log n) where n is the size of the array. # # It supports two modes, depending on the nature of the block and they are # exactly the same as in the case of #bsearch method with the only difference # being that this method returns the index of the element instead of the # element itself. For more details consult the documentation for #bsearch. def bsearch_index(&block) return to_enum :bsearch_index unless block low = 0 high = size satisfied = false while low < high mid = ((low+high)/2).truncate res = block.call self[mid] case res when 0 # find-any mode: Found! return mid when Numeric # find-any mode: Continue... in_lower_half = res < 0 when true # find-min mode in_lower_half = true satisfied = true when false, nil # find-min mode in_lower_half = false else raise TypeError, 'invalid block result (must be numeric, true, false or nil)' end if in_lower_half high = mid else low = mid + 1 end end satisfied ? low : nil end ## # call-seq: # ary.keep_if { |item| block } -> ary # ary.keep_if -> Enumerator # # Deletes every element of +self+ for which the given block evaluates to # +false+. # # See also Array#select! # # If no block is given, an Enumerator is returned instead. # # a = [1, 2, 3, 4, 5] # a.keep_if { |val| val > 3 } #=> [4, 5] def keep_if(&block) return to_enum :keep_if unless block idx = 0 while idx < self.size do if block.call(self[idx]) idx += 1 else self.delete_at(idx) end end self end ## # call-seq: # ary.select! {|item| block } -> ary or nil # ary.select! -> Enumerator # # Invokes the given block passing in successive elements from +self+, # deleting elements for which the block returns a +false+ value. # # If changes were made, it will return +self+, otherwise it returns +nil+. # # See also Array#keep_if # # If no block is given, an Enumerator is returned instead. def select!(&block) return to_enum :select! unless block result = [] idx = 0 len = size while idx < len elem = self[idx] result << elem if block.call(elem) idx += 1 end return nil if len == result.size self.replace(result) end ## # call-seq: # ary.index(val) -> int or nil # ary.index {|item| block } -> int or nil # # Returns the _index_ of the first object in +ary+ such that the object is # == to +obj+. # # If a block is given instead of an argument, returns the _index_ of the # first object for which the block returns +true+. Returns +nil+ if no # match is found. # # ISO 15.2.12.5.14 def index(val=NONE, &block) return to_enum(:find_index, val) if !block && val == NONE if block idx = 0 len = size while idx < len return idx if block.call self[idx] idx += 1 end else return self.__ary_index(val) end nil end ## # call-seq: # ary.dig(idx, ...) -> object # # Extracts the nested value specified by the sequence of idx # objects by calling +dig+ at each step, returning +nil+ if any # intermediate step is +nil+. # def dig(idx,*args) n = self[idx] if args.size > 0 n&.dig(*args) else n end end ## # call-seq: # ary.permutation { |p| block } -> ary # ary.permutation -> Enumerator # ary.permutation(n) { |p| block } -> ary # ary.permutation(n) -> Enumerator # # When invoked with a block, yield all permutations of length +n+ of the # elements of the array, then return the array itself. # # If +n+ is not specified, yield all permutations of all elements. # # The implementation makes no guarantees about the order in which the # permutations are yielded. # # If no block is given, an Enumerator is returned instead. # # Examples: # # a = [1, 2, 3] # a.permutation.to_a #=> [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] # a.permutation(1).to_a #=> [[1],[2],[3]] # a.permutation(2).to_a #=> [[1,2],[1,3],[2,1],[2,3],[3,1],[3,2]] # a.permutation(3).to_a #=> [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] # a.permutation(0).to_a #=> [[]] # one permutation of length 0 # a.permutation(4).to_a #=> [] # no permutations of length 4 def permutation(n=self.size, &block) return to_enum(:permutation, n) unless block size = self.size if n == 0 yield [] elsif 0 < n && n <= size i = 0 while i 0 ary = self[0...i] + self[i+1..-1] ary.permutation(n-1) do |c| yield result + c end else yield result end i += 1 end end self end ## # call-seq: # ary.combination(n) { |c| block } -> ary # ary.combination(n) -> Enumerator # # When invoked with a block, yields all combinations of length +n+ of elements # from the array and then returns the array itself. # # The implementation makes no guarantees about the order in which the # combinations are yielded. # # If no block is given, an Enumerator is returned instead. # # Examples: # # a = [1, 2, 3, 4] # a.combination(1).to_a #=> [[1],[2],[3],[4]] # a.combination(2).to_a #=> [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]] # a.combination(3).to_a #=> [[1,2,3],[1,2,4],[1,3,4],[2,3,4]] # a.combination(4).to_a #=> [[1,2,3,4]] # a.combination(0).to_a #=> [[]] # one combination of length 0 # a.combination(5).to_a #=> [] # no combinations of length 5 def combination(n, &block) return to_enum(:combination, n) unless block size = self.size if n == 0 yield [] elsif n == 1 i = 0 while i new_ary # # Assumes that self is an array of arrays and transposes the rows and columns. # # If the length of the subarrays don't match, an IndexError is raised. # # Examples: # # a = [[1,2], [3,4], [5,6]] # a.transpose #=> [[1, 3, 5], [2, 4, 6]] def transpose return [] if empty? column_count = nil self.each do |row| raise TypeError unless row.is_a?(Array) column_count ||= row.size raise IndexError, 'element size differs' unless column_count == row.size end Array.new(column_count) do |column_index| self.map { |row| row[column_index] } end end ## # call-seq: # ary.to_h -> Hash # ary.to_h{|item| ... } -> Hash # # Returns the result of interpreting array as an array of # [key, value] pairs. If a block is given, it should # return [key, value] pairs to construct a hash. # # [[:foo, :bar], [1, 2]].to_h # # => {:foo => :bar, 1 => 2} # [1, 2].to_h{|x| [x, x*2]} # # => {1 => 2, 2 => 4} # def to_h(&blk) h = {} self.each do |v| v = blk.call(v) if blk raise TypeError, "wrong element type #{v.class}" unless Array === v raise ArgumentError, "wrong array length (expected 2, was #{v.length})" unless v.length == 2 h[v[0]] = v[1] end h end alias append push alias prepend unshift alias filter! select! ## # call-seq: # ary.product(*arys) -> array # ary.product(*arys) { |item| ... } -> self def product(*arys, &block) size = arys.size i = size while i > 0 i -= 1 unless arys[i].kind_of?(Array) raise TypeError, "no implicit conversion into Array" end end i = size total = self.size total *= arys[i -= 1].size while i > 0 if block result = self list = ->(*, e) { block.call e } class << list; alias []= call; end else result = [nil] * total list = result end i = 0 while i < total group = [nil] * (size + 1) j = size n = i while j > 0 j -= 1 a = arys[j] b = a.size group[j + 1] = a[n % b] n /= b end group[0] = self[n] list[i] = group i += 1 end result end ## # call-seq: # ary.repeated_combination(n) { |combination| ... } -> self # ary.repeated_combination(n) -> enumerator # # A +combination+ method that contains the same elements. def repeated_combination(n, &block) raise TypeError, "no implicit conversion into Integer" unless 0 <=> n return to_enum(:repeated_combination, n) unless block __repeated_combination(n, false, &block) end ## # call-seq: # ary.repeated_permutation(n) { |permutation| ... } -> self # ary.repeated_permutation(n) -> enumerator # # A +permutation+ method that contains the same elements. def repeated_permutation(n, &block) raise TypeError, "no implicit conversion into Integer" unless 0 <=> n return to_enum(:repeated_permutation, n) unless block __repeated_combination(n, true, &block) end def __repeated_combination(n, permutation, &block) case n when 0 yield [] when 1 i = 0 while i < self.size yield [self[i]] i += 1 end else if n > 0 v = [0] * n while true tmp = [nil] * n i = 0 while i < n tmp[i] = self[v[i]] i += 1 end yield tmp tmp = self.size i = n - 1 while i >= 0 v[i] += 1 break if v[i] < tmp i -= 1 end break unless v[0] < tmp i = 1 while i < n unless v[i] < tmp if permutation v[i] = 0 else v[i] = v[i - 1] end end i += 1 end end end end self end end