This documentation is automatically generated by online-judge-tools/verification-helper
require "spec" require "../../../src/datastructure/sset/bucket" private alias S = SSet::Bucket(Int32, 1, 170, 1) describe "SSet::Bucket(Int32)" do it "{}" do S{3, 1, 4, 1, 5}.to_a.should eq [1, 3, 4, 5] end it ".new" do s = S.new [1, 2, 1, 3, 4] s.to_a.should eq [1, 2, 3, 4] end it "#size" do s = S.new s.size.should eq 0 s.add 1 s.size.should eq 1 s.add 1 s.size.should eq 1 s.delete 1 s.size.should eq 0 end it "#empty?" do s = S.new s.empty?.should be_true s.add 1 s.empty?.should be_false end it "#clear" do s = S.new s.add 1 s.clear.size.should eq 0 end it "#add?" do s = S.new s.add?(1).should be_true s.add?(1).should be_false end it "#add, #<<" do s = S.new s.add(1).add(2).add(1) s.size.should eq 2 s << 3 << 4 << 3 s.size.should eq 4 end it "#min?, #min, #max?, #max" do s = S.new s.min?.should be_nil s.max?.should be_nil expect_raises(S::EmptyError) { s.min } expect_raises(S::EmptyError) { s.max } s << 1 << 2 s.min?.should eq 1 s.max?.should eq 2 s.min.should eq 1 s.max.should eq 2 end it "#each" do s = S{3, 1, 4, 1, 5} a = [] of Int32 s.each { |x| a << x } a.should eq [1, 3, 4, 5] a.each.to_a.should eq [1, 3, 4, 5] end it "#reverse_each" do s = S{3, 1, 4, 1, 5} a = [] of Int32 s.reverse_each { |x| a << x } a.should eq [5, 4, 3, 1] end it "#[]" do s = S{3, 1, 4, 1, 5} s[0].should eq 1 s[1].should eq 3 s[2].should eq 4 s[3].should eq 5 s[-1].should eq 5 s[-2].should eq 4 s[-3].should eq 3 s[-4].should eq 1 expect_raises(IndexError) { s[4] } expect_raises(IndexError) { s[-5] } end it "#includes?" do s = S{1, 3, 5} {1, 3, 5}.each { |x| s.includes?(x).should be_true } {0, 2, 4}.each { |x| s.includes?(x).should be_false } end it "#count" do s = S{1, 1, 2, 3, 4} [0, 1, 1, 1, 1, 0].each_with_index do |c, x| s.count(x).should eq c end end it "#index" do s = S{1, 1, 2, 3, 4} [nil, 0, 1, 2, 3, nil].each_with_index do |expected, x| s.index(x).should eq expected end end it "#index_left, #index_right" do s = S{1, 1, 2, 3, 4} [{0, 0}, {0, 1}, {1, 2}, {2, 3}, {3, 4}, {4, 4}].each_with_index do |(l, r), x| s.index_left(x).should eq l s.index_right(x).should eq r end end it "#le, #le!" do s = S{1, 3} [nil, 1, 1, 3, 3].each_with_index { |e, x| s.le(x).should eq e } expect_raises(NilAssertionError) { s.le!(0) } [1, 1, 3, 3].each_with_index(1) { |e, x| s.le!(x).should eq e } end it "#lt, #lt!" do s = S{1, 3} [nil, nil, 1, 1, 3, 3].each_with_index { |e, x| s.lt(x).should eq e } expect_raises(NilAssertionError) { s.lt!(0) } expect_raises(NilAssertionError) { s.lt!(1) } [1, 1, 3, 3].each_with_index(2) { |e, x| s.lt!(x).should eq e } end it "#ge, #ge!" do s = S{1, 3} [1, 1, 3, 3, nil].each_with_index { |e, x| s.ge(x).should eq e } expect_raises(NilAssertionError) { s.ge!(4) } [1, 1, 3, 3].each_with_index { |e, x| s.ge!(x).should eq e } end it "#gt, #gt!" do s = S{1, 3} [1, 3, 3, nil, nil].each_with_index { |e, x| s.gt(x).should eq e } expect_raises(NilAssertionError) { s.gt!(3) } expect_raises(NilAssertionError) { s.gt!(4) } [1, 3, 3].each_with_index { |e, x| s.gt!(x).should eq e } end {% for op in [:&, :|, :+, :-] %} it "\#{{op.id}}" do a = S{0, 1, 2, 2, 3} b = {1, 1, 2, 3, 4, 5} expected = a.to_set {{op.id}} b.to_set (a {{op.id}} b).to_a.should eq expected.to_a end {% end %} it "#to_a" do s = S{1, 3, 2, 4} s.to_a.should eq [1, 2, 3, 4] end it "#to_s" do s = S{1, 2, 3, 4} s.to_s.should eq "SSet::Bucket{1, 2, 3, 4}" end it "includes Enumerable" do s = S{1, 2, 3, 4} s.all? { |x| x > 0 }.should be_true end it "includes Iterable" do s = S{1, 2, 3, 4} s.cycle(2).to_a.should eq [1, 2, 3, 4, 1, 2, 3, 4] end it "includes Indexable" do s = S{1, 2, 3, 4} s.values_at(0, 1, 2, 3).should eq({1, 2, 3, 4}) end end
require "spec" # require "../../../src/datastructure/sset/bucket" # reference: https://github.com/tatyam-prime/SortedSet/blob/main/SortedSet.py class SSet::Bucket(T, BUCKET_RATIO, REBUILD_RATIO, BSEARCH) include Enumerable(T) include Iterable(T) include Indexable(T) getter size = 0 @buckets = [] of Array(T) def initialize end def initialize(a : Enumerable(T)) build a.to_a.sort!.uniq! end private def build(a : Array(T)) : Nil @size = a.size bucket_size = Math.sqrt(size / BUCKET_RATIO).ceil.to_i @buckets = Array.new(bucket_size) { |i| a[size * i // bucket_size...size * (i + 1) // bucket_size] } end private def build build to_a end def empty? : Bool @size == 0 end def clear @size = 0 @buckets.clear end def min? : T? empty? ? nil : @buckets.first.first end def min : T min? || raise EmptyError.new end def max? : T? empty? ? nil : @buckets.last.last end def max : T max? || raise EmptyError.new end def each(&) : Nil @buckets.each do |bucket| bucket.each do |object| yield object end end end private class ItemIterator(T) include Iterator(T) def initialize(@buckets : Array(Array(T))) @i, @j = 0, 0 end def next if @buckets.size == @i stop else @buckets[@i][@j].tap do @j += 1 @i, @j = @i + 1, 0 if @buckets[@i].size == @j end end end end def each ItemIterator(T).new(@buckets) end def reverse_each(&) : Nil @buckets.reverse_each do |bucket| bucket.reverse_each do |object| yield object end end end private def find_bucket(object : T) {% if BSEARCH > 0 %} @buckets.bsearch { |bucket| object <= bucket.last } || @buckets.last {% else %} @buckets.find(@buckets.last) { |bucket| object <= bucket.last } {% end %} end def includes?(object : T) : Bool false if empty? find_bucket(object).bsearch { |x| x >= object } == object end def unsafe_fetch(index : Int) : T @buckets.each do |bucket| return bucket.unsafe_fetch(index) if index < bucket.size index -= bucket.size end raise "Bug" end def add?(object : T) : Bool if size == 0 @buckets = [[object]] @size = 1 return true end a = find_bucket(object) i = a.bsearch_index { |x| x >= object } return false if i && a[i] == object i ? a.insert(i, object) : a.push(object) @size += 1 build if a.size > @buckets.size * REBUILD_RATIO true end def add(object : T) : self add?(object) self end def <<(object : T) : self add(object) end def concat(elems) : self elems.each { |object| add(object) } self end def delete(object : T) : Bool return false if empty? a = find_bucket(object) i = a.bsearch_index { |x| x >= object } return false if i.nil? || a[i] != object a.delete_at(i) @size -= 1 build if a.empty? true end def count(object : T) : Int32 includes?(object) ? 1 : 0 end def index(object : T) : Int32? offset = 0 @buckets.each do |bucket| if bucket.last >= object i = bucket.bsearch_index { |x| x >= object }.not_nil! return offset + i if bucket[i] == object end end end def index_left(object : T) : Int32 @buckets.reduce(0) do |offset, bucket| if bucket.last >= object return offset + bucket.bsearch_index { |x| x >= object }.not_nil! end offset + bucket.size end end def index_right(object : T) : Int32? @buckets.reduce(0) do |offset, bucket| if bucket.last > object return offset + bucket.bsearch_index { |x| x > object }.not_nil! end offset + bucket.size end end def le(object : T) : T? @buckets.reverse_each do |bucket| if bucket.first <= object i = bucket.bsearch_index { |x| x > object } || bucket.size return bucket[i - 1] end end end def lt(object : T) : T? @buckets.reverse_each do |bucket| if bucket.first < object i = bucket.bsearch_index { |x| x >= object } || bucket.size return bucket[i - 1] end end end def ge(object : T) : T? {% if BSEARCH > 0 %} @buckets.bsearch { |bucket| bucket.last >= object }.try do |bucket| bucket.bsearch { |x| x >= object }.not_nil! end {% else %} @buckets.each do |bucket| if bucket.last >= object return bucket.bsearch { |x| x >= object }.not_nil! end end {% end %} end def gt(object : T) : T? @buckets.each do |bucket| if bucket.last > object return bucket.bsearch { |x| x > object }.not_nil! end end end {% for method in [:le, :lt, :ge, :gt] %} def {{method.id}}!(object : T) : T {{method.id}}(object).not_nil! end {% end %} {% for op in [:&, :|, :^, :+, :-] %} def {{op.id}}(other : Enumerable(T)) : self SSet::Bucket(T, BUCKET_RATIO, REBUILD_RATIO, BSEARCH).new (self.to_set {{op.id}} other.to_set) end {% end %} def to_a : Array(T) @buckets.each_with_object(Array(T).new size) do |bucket, a| a.concat bucket end end def to_s(io : IO) : Nil io << "SSet::Bucket{" join(", ", io) io << "}" end def inspect(io : IO) : Nil @buckets.inspect(io) end end private alias S = SSet::Bucket(Int32, 1, 170, 1) describe "SSet::Bucket(Int32)" do it "{}" do S{3, 1, 4, 1, 5}.to_a.should eq [1, 3, 4, 5] end it ".new" do s = S.new [1, 2, 1, 3, 4] s.to_a.should eq [1, 2, 3, 4] end it "#size" do s = S.new s.size.should eq 0 s.add 1 s.size.should eq 1 s.add 1 s.size.should eq 1 s.delete 1 s.size.should eq 0 end it "#empty?" do s = S.new s.empty?.should be_true s.add 1 s.empty?.should be_false end it "#clear" do s = S.new s.add 1 s.clear.size.should eq 0 end it "#add?" do s = S.new s.add?(1).should be_true s.add?(1).should be_false end it "#add, #<<" do s = S.new s.add(1).add(2).add(1) s.size.should eq 2 s << 3 << 4 << 3 s.size.should eq 4 end it "#min?, #min, #max?, #max" do s = S.new s.min?.should be_nil s.max?.should be_nil expect_raises(S::EmptyError) { s.min } expect_raises(S::EmptyError) { s.max } s << 1 << 2 s.min?.should eq 1 s.max?.should eq 2 s.min.should eq 1 s.max.should eq 2 end it "#each" do s = S{3, 1, 4, 1, 5} a = [] of Int32 s.each { |x| a << x } a.should eq [1, 3, 4, 5] a.each.to_a.should eq [1, 3, 4, 5] end it "#reverse_each" do s = S{3, 1, 4, 1, 5} a = [] of Int32 s.reverse_each { |x| a << x } a.should eq [5, 4, 3, 1] end it "#[]" do s = S{3, 1, 4, 1, 5} s[0].should eq 1 s[1].should eq 3 s[2].should eq 4 s[3].should eq 5 s[-1].should eq 5 s[-2].should eq 4 s[-3].should eq 3 s[-4].should eq 1 expect_raises(IndexError) { s[4] } expect_raises(IndexError) { s[-5] } end it "#includes?" do s = S{1, 3, 5} {1, 3, 5}.each { |x| s.includes?(x).should be_true } {0, 2, 4}.each { |x| s.includes?(x).should be_false } end it "#count" do s = S{1, 1, 2, 3, 4} [0, 1, 1, 1, 1, 0].each_with_index do |c, x| s.count(x).should eq c end end it "#index" do s = S{1, 1, 2, 3, 4} [nil, 0, 1, 2, 3, nil].each_with_index do |expected, x| s.index(x).should eq expected end end it "#index_left, #index_right" do s = S{1, 1, 2, 3, 4} [{0, 0}, {0, 1}, {1, 2}, {2, 3}, {3, 4}, {4, 4}].each_with_index do |(l, r), x| s.index_left(x).should eq l s.index_right(x).should eq r end end it "#le, #le!" do s = S{1, 3} [nil, 1, 1, 3, 3].each_with_index { |e, x| s.le(x).should eq e } expect_raises(NilAssertionError) { s.le!(0) } [1, 1, 3, 3].each_with_index(1) { |e, x| s.le!(x).should eq e } end it "#lt, #lt!" do s = S{1, 3} [nil, nil, 1, 1, 3, 3].each_with_index { |e, x| s.lt(x).should eq e } expect_raises(NilAssertionError) { s.lt!(0) } expect_raises(NilAssertionError) { s.lt!(1) } [1, 1, 3, 3].each_with_index(2) { |e, x| s.lt!(x).should eq e } end it "#ge, #ge!" do s = S{1, 3} [1, 1, 3, 3, nil].each_with_index { |e, x| s.ge(x).should eq e } expect_raises(NilAssertionError) { s.ge!(4) } [1, 1, 3, 3].each_with_index { |e, x| s.ge!(x).should eq e } end it "#gt, #gt!" do s = S{1, 3} [1, 3, 3, nil, nil].each_with_index { |e, x| s.gt(x).should eq e } expect_raises(NilAssertionError) { s.gt!(3) } expect_raises(NilAssertionError) { s.gt!(4) } [1, 3, 3].each_with_index { |e, x| s.gt!(x).should eq e } end {% for op in [:&, :|, :+, :-] %} it "\#{{op.id}}" do a = S{0, 1, 2, 2, 3} b = {1, 1, 2, 3, 4, 5} expected = a.to_set {{op.id}} b.to_set (a {{op.id}} b).to_a.should eq expected.to_a end {% end %} it "#to_a" do s = S{1, 3, 2, 4} s.to_a.should eq [1, 2, 3, 4] end it "#to_s" do s = S{1, 2, 3, 4} s.to_s.should eq "SSet::Bucket{1, 2, 3, 4}" end it "includes Enumerable" do s = S{1, 2, 3, 4} s.all? { |x| x > 0 }.should be_true end it "includes Iterable" do s = S{1, 2, 3, 4} s.cycle(2).to_a.should eq [1, 2, 3, 4, 1, 2, 3, 4] end it "includes Indexable" do s = S{1, 2, 3, 4} s.values_at(0, 1, 2, 3).should eq({1, 2, 3, 4}) end end