spec/datastructure/sset/bucket_spec.cr

• View this file on GitHub
• Last update: 2022-01-22 15:32:00+09:00

Depends on

• src/datastructure/sset/bucket.cr

Code

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

Back to top page