Fill sparse array

Question

I have a sparse array, for example:

rare = [[0,1], [2,3], [4,5], [7,8]]

I want to plot a chart with these data, each pair are point coordinates. As you can see I don't have points for x=1, x=3 , x=5, x=6

I want to fill the array with the previous values, so for the above example I will get:

filled = [[0,1], [1,1], [2,3], [3,3], [4,5], [5,5], [6,5], [7,8]

As you can see, for calculating the y value, I simply take the last y value I used.

What is the best aproach to accomplish this ?

Answer 1

rare = [[0,1], [2,3], [4,5], [7,8]]

filled = rare.inject([]) do |filled, point|
  extras = if filled.empty?
             []
           else
             (filled.last[0] + 1 ... point[0]).collect do |x|
               [x, filled.last[1]]
             end
           end
  filled + extras + [point]
end

p filled
# => [[0, 1], [1, 1], [2, 3], [3, 3], [4, 5], [5, 5], [6, 5], [7, 8]]

Answer 2

An inject solution:

filled = rare.inject([]) do |filled_acc, (pair_x, pair_y)|
  padded_pairs = unless filled_acc.empty?    
    last_x, last_y = filled_acc.last
    (last_x+1...pair_x).map { |x| [x, last_y] }
  end || []
  filled_acc + padded_pairs + [[pair_x, pair_y]] 
end

More about Enumerable#inject and functional programming with Ruby here.

Answer 3

Range.new(*rare.transpose.first.sort.values_at(0,-1)).inject([]){|a,i|
  a<<[i, Hash[rare][i] || a.last.last]
}

Step-by-step explanation:

1. rare.transpose.first.sort.values_at(0,-1) finds min and max x ([0,7] in your example)
2. Range.new() makes a range out of it (0..7)
3. inject iterates through the range and for every x returns pair [x,y], where y is:
   1. y from input array, where defined
   2. y from previously evaluated pair, where not

Note: here are some other ways of finding min and max x:

[:min,:max].map{|m| Hash[rare].keys.send m}
rare.map{|el| el.first}.minmax # Ruby 1.9, by steenslag

Answer 4

irb(main):001:0> rare = [[0,1], [2,3], [4,5], [7,8]]
=> [[0, 1], [2, 3], [4, 5], [7, 8]]
irb(main):002:0> r=rare.transpose
=> [[0, 2, 4, 7], [1, 3, 5, 8]]
irb(main):003:0> iv = (r[0][0]..r[0][-1]).to_a.select {|w| !r[0].include?(w) }
=> [1, 3, 5, 6]
irb(main):004:0> r[1][-1]=r[1][-2]
=> 5
irb(main):005:0> p (iv.zip(r[1]) + rare).sort
[[0, 1], [1, 1], [2, 3], [3, 3], [4, 5], [5, 5], [6, 5], [7, 8]]
=> [[0, 1], [1, 1], [2, 3], [3, 3], [4, 5], [5, 5], [6, 5], [7, 8]]