SLBSA

slbsa.rb

require "set"
class SLBSA
  def initialize max_size, &block
    @max_size = max_size
    @values = []
    @scores = []
    @calculate = block
    @set = Set.new
  end
  def push value
    return if @set.include? value
    @set.add value
    score = @calculate.call value
    index = @scores.bsearch_index{ |_| (score <=> _) < 1 } || @scores.size
    return if @max_size <= index
    @scores.insert index, score
    @values.insert index, value
    return if @scores.size <= @max_size
    return if @scores[@max_size - 1] == @scores.last
    @scores.replace @scores.take @max_size
    @values.replace @values.take @max_size
  end
  def to_a
    @values
  end
  def scores
    @scores
  end
  def size
    @values.size
  end
end

SLBSA.new(10){ |_| _ % 10 }.then do |slbsa|
  [10,20,11,21,12,22,13,23,14,24].shuffle.each{ |_| slbsa.push _ }
  fail slbsa.to_a.inspect unless [10,11,12,13,14,20,21,22,23,24] == slbsa.to_a.sort
  slbsa.push 34
  slbsa.push 34
  slbsa.push 44
  fail slbsa.to_a.inspect unless [10,11,12,13,14,20,21,22,23,24,34,44] == slbsa.to_a.sort
  slbsa.push 33
  fail slbsa.to_a.inspect unless [10,11,12,13,14,20,21,22,23,24,33,34,44] == slbsa.to_a.sort
  slbsa.push 43
  fail slbsa.to_a.inspect unless [10,11,12,13,20,21,22,23,33,43] == slbsa.to_a.sort
end