src/datastructure/smultiset/bucket.cr

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

Required by

• spec/datastructure/smultiset/bucket_spec.cr

Code

# reference: https://github.com/tatyam-prime/SortedSet/blob/main/SortedSet.py
class SMultiSet::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!
  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) : self
    if size == 0
      @buckets = [[object]]
      @size = 1
      return self
    end

    a = find_bucket(object)
    i = a.bsearch_index { |x| x >= object }
    i ? a.insert(i, object) : a.push(object)
    @size += 1
    build if a.size > @buckets.size * REBUILD_RATIO
    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?
    index_right(object) - index_left(object)
  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
      SMultiSet::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 << "SMultiSet::Bucket{"
    join(", ", io)
    io << "}"
  end

  def inspect(io : IO) : Nil
    @buckets.inspect(io)
  end
end

# reference: https://github.com/tatyam-prime/SortedSet/blob/main/SortedSet.py
class SMultiSet::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!
  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) : self
    if size == 0
      @buckets = [[object]]
      @size = 1
      return self
    end

    a = find_bucket(object)
    i = a.bsearch_index { |x| x >= object }
    i ? a.insert(i, object) : a.push(object)
    @size += 1
    build if a.size > @buckets.size * REBUILD_RATIO
    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?
    index_right(object) - index_left(object)
  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
      SMultiSet::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 << "SMultiSet::Bucket{"
    join(", ", io)
    io << "}"
  end

  def inspect(io : IO) : Nil
    @buckets.inspect(io)
  end
end

Back to top page