src/datastructure/imos_2d.cr

• View this file on GitHub
• Last update: 2022-04-16 07:49:21+00:00

Verified with

• test/collection/compress_test.cr
• test/datastructure/cul_sum_2d_2_test.cr
• test/datastructure/cul_sum_2d_imos_2d_test.cr

Code

class Imos2D(T)
  getter height : Int32, width : Int32
  @built = false

  def initialize(@height, @width, init_val : T = T.zero)
    @table = Array(Array(T)).new(@height + 1) do
      Array(T).new(@width + 1, init_val)
    end
  end

  def add(ys : Int, yc : Int, xs : Int, xc : Int, val : T) : Nil
    raise "self had been called `#build`" if @built
    raise ArgumentError.new "Negative count: #{yc}" if yc < 0
    raise ArgumentError.new "Negative count: #{xc}" if xc < 0
    @table[ys + yc][xs + xc] += val
    @table[ys + yc][xs] -= val
    @table[ys][xs + xc] -= val
    @table[ys][xs] += val
  end

  def add(y : Range, x : Range, val : T) : Nil
    ys, yc = Indexable.range_to_index_and_count(y, height) || raise IndexError.new
    xs, xc = Indexable.range_to_index_and_count(x, width) || raise IndexError.new
    add(ys, yc, xs, xc, val)
  end

  def build : Array(Array(T))
    raise "self had been called `#build`" if @built
    @built = true
    (0..height).each do |y|
      (1..width).each do |x|
        @table[y][x] += @table[y][x - 1]
      end
    end
    (1..height).each do |y|
      (0..width).each do |x|
        @table[y][x] += @table[y - 1][x]
      end
    end
    (0...height).map { |i| @table[i][0...width] }
  end

  def [](y : Int32, x : Int32) : T
    raise "self had not been called `#build`" unless @built
    @table[y][x]
  end
end

class Imos2D(T)
  getter height : Int32, width : Int32
  @built = false

  def initialize(@height, @width, init_val : T = T.zero)
    @table = Array(Array(T)).new(@height + 1) do
      Array(T).new(@width + 1, init_val)
    end
  end

  def add(ys : Int, yc : Int, xs : Int, xc : Int, val : T) : Nil
    raise "self had been called `#build`" if @built
    raise ArgumentError.new "Negative count: #{yc}" if yc < 0
    raise ArgumentError.new "Negative count: #{xc}" if xc < 0
    @table[ys + yc][xs + xc] += val
    @table[ys + yc][xs] -= val
    @table[ys][xs + xc] -= val
    @table[ys][xs] += val
  end

  def add(y : Range, x : Range, val : T) : Nil
    ys, yc = Indexable.range_to_index_and_count(y, height) || raise IndexError.new
    xs, xc = Indexable.range_to_index_and_count(x, width) || raise IndexError.new
    add(ys, yc, xs, xc, val)
  end

  def build : Array(Array(T))
    raise "self had been called `#build`" if @built
    @built = true
    (0..height).each do |y|
      (1..width).each do |x|
        @table[y][x] += @table[y][x - 1]
      end
    end
    (1..height).each do |y|
      (0..width).each do |x|
        @table[y][x] += @table[y - 1][x]
      end
    end
    (0...height).map { |i| @table[i][0...width] }
  end

  def [](y : Int32, x : Int32) : T
    raise "self had not been called `#build`" unless @built
    @table[y][x]
  end
end

Back to top page