spec/collection/mex_spec.cr

• View this file on GitHub
• Last update: 2022-03-25 20:11:13+09:00

Depends on

• src/collection/mex.cr

Code

require "spec"
require "../../src/collection/mex"

describe Enumerable do
  it "#mex_sorted" do
    (0...100).mex_sorted.should eq 100
    (1..).mex_sorted.should eq 0
    Array(Int32).new.mex_sorted.should eq 0
    [0, 1, 2, 4].mex_sorted.should eq 3
    [0, 0, 1, 2, 2, 4].mex_sorted.should eq 3
    [-3, -2, 0, 2].mex_sorted.should eq 1
  end

  it "#mex" do
    a = (0...100).to_a
    a.mex.should eq 100
    a.shuffle.mex.should eq 100
    (a * 2).shuffle.mex.should eq 100
    Set{3, 4, 0, 7, 1, 2, 6, 3}.mex.should eq 5
  end
end

require "spec"

# require "../../src/collection/mex"
module Enumerable(T)
  # Returns the minimum value of the complement set.
  def mex_sorted : T
    reduce(T.zero) do |now, x|
      next now if x < T.zero
      return now if now < x
      x.succ
    end
  end

  # :ditto:
  def mex : T
    to_a.sort!.mex_sorted
  end
end

describe Enumerable do
  it "#mex_sorted" do
    (0...100).mex_sorted.should eq 100
    (1..).mex_sorted.should eq 0
    Array(Int32).new.mex_sorted.should eq 0
    [0, 1, 2, 4].mex_sorted.should eq 3
    [0, 0, 1, 2, 2, 4].mex_sorted.should eq 3
    [-3, -2, 0, 2].mex_sorted.should eq 1
  end

  it "#mex" do
    a = (0...100).to_a
    a.mex.should eq 100
    a.shuffle.mex.should eq 100
    (a * 2).shuffle.mex.should eq 100
    Set{3, 4, 0, 7, 1, 2, 6, 3}.mex.should eq 5
  end
end

Back to top page