Inc, Dec, GetMax, GetMin

all_one.rb

class AllOne
  def initialize()
    @sorted = []
    @positions = {}
    @leftmost = {}
    @count = {}
  end

  def inc(key)
    if (pos = @positions[key])
      current_value = @sorted[pos].last
      new_value = current_value + 1
      my_leftmost = @leftmost[current_value]

      swap(my_leftmost, pos) if my_leftmost != pos
      @sorted[my_leftmost][1] += 1

      # If I'm first key of new value:
      @leftmost[new_value] ||= my_leftmost
      @count[new_value] ||= 0

      decrement_count(current_value)
      # Leftmost of old value now moves to the right, unless it was deleted completely.
      @leftmost[current_value] += 1 if @leftmost.has_key?(current_value)
      @count[new_value] += 1
    else
      # New value.
      @leftmost[1] ||= @sorted.size
      @count[1] ||= 0
      @count[1] += 1
      @positions[key] = @sorted.size
      @sorted << [key, 1]
    end
  end

  def dec(key)
    return unless (pos = @positions[key])

    current_value = @sorted[pos].last
    new_value = current_value - 1
    my_rightmost = @leftmost[current_value] + @count[current_value] - 1

    swap(my_rightmost, pos) if my_rightmost != pos

    if current_value == 1
      @sorted.pop
      @positions.delete(key)
    else
      @sorted[my_rightmost][1] -= 1
      @leftmost[new_value] ||= my_rightmost + 1
      @count[new_value] ||= 0
      @leftmost[new_value] -= 1
      @count[new_value] += 1
    end
    decrement_count(current_value)
  end

  def get_max_key()
    @sorted.first&.first || ''
  end

  def get_min_key()
    @sorted.last&.first || ''
  end

  def errors
    expected_counts = @sorted.map(&:last).group_by(&:itself).transform_values(&:size)
    [
      ("Sort failure: #{@sorted}" if @sorted.map(&:last).each_cons(2).any? { |a, b| a < b }),
      ("Forward position failure: #{@sorted} / #{@positions}" if @positions.any? { |k, v|
        @sorted[v].first != k
      }),
      ("Reverse position failure: #{@sorted} / #{@positions}" if @sorted.each_with_index.any? { |(k, _), i|
        @positions[k] != i
      }),
      ("Leftmost has wrong keys: #{@sorted} / #{@leftmost}" if @sorted.map(&:last).uniq.sort != @leftmost.keys.sort),
      ("Leftmost has wrong values: #{@sorted} / #{@leftmost}" unless @leftmost.all? { |k, v|
        v == 0 || @sorted[v - 1].last > k
      }),
      ("Count has wrong keys: #{@sorted} / #{@count}" if @sorted.map(&:last).uniq.sort != @count.keys.sort),
      ("Count has wrong values: #{@sorted} / #{@count}" unless @count.all? { |k, v|
        v == expected_counts[k]
      }),
    ].compact
  end

  private

  def swap(pos1, pos2)
    key1 = @sorted[pos1].first
    key2 = @sorted[pos2].first
    @sorted[pos1][0], @sorted[pos2][0] = [key2, key1]
    @positions[key1] = pos2
    @positions[key2] = pos1
  end

  def decrement_count(count)
    @count[count] -= 1
    if @count[count] == 0
      @count.delete(count)
      @leftmost.delete(count)
    end
  end
end

if true
  randoms = 1000.times.map {
    100.times.map { "#{%w(+ -).sample}#{%w(a b c d e).sample}" }
  }

  ([
    %w(+a +b +b +b),
    %w(+a +b +a +a),
    %w(+a -a),
    %w(+a +a -a),
  ] + randoms).each { |cmds|
    ao = AllOne.new
    cmds.each_with_index { |s, i|
      case s[0]
      when ?+; ao.inc(s[1..-1])
      when ?-; ao.dec(s[1..-1])
      else raise "Unknown #{s}"
      end
      unless ao.errors.empty?
        puts "#{cmds[0..i]}"
        puts ao.errors
        break
      end
    }
    puts ?- * 19
  }
end