class StableMatching::Roommate::PhaseIIIRunner

Public Class Methods

new(preference_table, opts = {}) click to toggle source
# File lib/stable-matching/roommate/phase_iii_runner.rb, line 100
def initialize(preference_table, opts = {})
  @preference_table = preference_table
  @logger = opts.fetch(:logger)
end

Public Instance Methods

run() click to toggle source
# File lib/stable-matching/roommate/phase_iii_runner.rb, line 105
def run
  # The output of previous phase may have resulted in a complete
  # table, in which case this step doesn't need to be run
  return @preference_table if @preference_table.complete?

  while table_is_stable? && !@preference_table.complete?
    x = [@preference_table.members_with_multiple_preferences.first]
    y = [nil]

    until any_repeats?(x)
      # require 'pry'; binding.pry if x.last.second_preference.nil?
      y << x.last.second_preference
      x << y.last.last_preference
    end

    detect_and_reject_cycles(x, y)
  end
end

Private Instance Methods

any_repeats?(arr) click to toggle source
# File lib/stable-matching/roommate/phase_iii_runner.rb, line 126
def any_repeats?(arr)
  arr.uniq.count != arr.count
end
detect_and_reject_cycles(x, y) click to toggle source
# File lib/stable-matching/roommate/phase_iii_runner.rb, line 130
def detect_and_reject_cycles(x, y)
  x, y = retrieve_cycle(x, y)

  msg = "Found cycle: "
  y.each_with_index { |_, i| msg << "(#{x[i].name}, #{y[i].name})" }
  @logger.debug(msg)

  x.each_with_index do |r1, i|
    r2 = y[i]
    @logger.debug("Mutually rejecting '#{r1.name}', '#{r2.name}'")
    r2.reject!(r1)
  end
end
retrieve_cycle(x, y) click to toggle source
# File lib/stable-matching/roommate/phase_iii_runner.rb, line 144
def retrieve_cycle(x, y)
  repeated_member = x.detect { |i| x.count(i) > 1 }

  first_index = 1
  last_index = x.count - x.reverse.index(repeated_member) - 1

  [x[first_index..last_index], y[first_index..last_index]]
end
table_is_stable?() click to toggle source
# File lib/stable-matching/roommate/phase_iii_runner.rb, line 153
def table_is_stable?
  return true if @preference_table.stable?
  raise StableMatching::NoStableSolutionError, "No stable match found!"
end