missing_detector.rb

##
# Finds the lowest missing positive integer in an array.
#
# The request was to do this in linear time and constant space.
#
class MissingDetector
  def initialize(array)
    @array = array
  end

  def process
    @array.each_with_index do |value, idx|
      resolve(value, idx)
    end

    (1..@array.size).find do |pos_int|
      destination_holds_incorrect_value?(pos_int)
    end || @array.size + 1
  end

  private

  def resolve(value, idx)
    return unless work_to_do?(value, idx)

    swap_into_correct_location(value, idx)
    resolve(@array[idx], idx)
  end

  def work_to_do?(value, idx)
    idx != correct_index_for(value) &&
      destination_is_in_bounds?(value) &&
      destination_holds_incorrect_value?(value)
  end

  def swap_into_correct_location(value, current_idx)
    correct_idx = correct_index_for(value)

    @array[current_idx] = @array[correct_idx]
    @array[correct_idx] = value

    @swap_count += 1
  end

  def correct_index_for(value)
    value - 1
  end

  def destination_holds_incorrect_value?(value)
    @array[correct_index_for(value)] != value
  end

  def destination_is_in_bounds?(value)
    value > 0 && !@array[correct_index_for(value)].nil?
  end
end