class Bundler::PubGrub::PartialSolution

def add_assignment(assignment)
  term = assignment.term
  package = term.package
  @assignments << assignment
  @assignments_by[package] << assignment
  @required[package] = true if term.positive?
  if @terms.key?(package)
    old_term = @terms[package]
    @terms[package] = old_term.intersect(term)
  else
    @terms[package] = term
  end
  @relation_cache[package].clear
  @cumulative_assignments[assignment] = @terms[package]
end

def backtrack(previous_level)
  @backtracking = true
  new_assignments = assignments.select do |assignment|
    assignment.decision_level <= previous_level
  end
  new_decisions = Hash[decisions.first(previous_level)]
  reset!
  @decisions = new_decisions
  new_assignments.each do |assignment|
    add_assignment(assignment)
  end
end

def decide(package, version)
  @attempted_solutions += 1 if @backtracking
  @backtracking = false;
  decisions[package] = version
  assignment = Assignment.decision(package, version, decision_level, assignments.length)
  add_assignment(assignment)
end

def decision_level
  @decisions.length
end

def derive(term, cause)
  add_assignment(Assignment.new(term, cause, decision_level, assignments.length))
end

def initialize
  reset!
  @attempted_solutions = 1
  @backtracking = false
end

def relation(term)
  package = term.package
  return :overlap if !@terms.key?(package)
  @relation_cache[package][term] ||=
    @terms[package].relation(term)
end

def reset!
  # { Array<Assignment> }
  @assignments = []
  # { Package => Array<Assignment> }
  @assignments_by = Hash.new { |h,k| h[k] = [] }
  @cumulative_assignments = {}.compare_by_identity
  # { Package => Package::Version }
  @decisions = {}
  # { Package => Term }
  @terms = {}
  @relation_cache = Hash.new { |h,k| h[k] = {} }
  # { Package => Boolean }
  @required = {}
end

def satisfier(term)
  assignment =
    @assignments_by[term.package].bsearch do |assignment_by|
      @cumulative_assignments[assignment_by].satisfies?(term)
    end
  assignment || raise("#{term} unsatisfied")
end

def satisfies?(term)
  relation(term) == :subset
end

def unsatisfied
  @required.keys.reject do |package|
    @decisions.key?(package)
  end.map do |package|
    @terms[package]
  end
end