#!/usr/bin/ruby

require 'log4r'
include Log4r

%w(AbstractConstraint AllDifferentConstraint BinaryConstraint
    TupleConstraint OneOfEqualsConstraint ConstraintList ConstraintSolver Domain
    extensions Problem Solution Variable).each { |file| require file }

module ConstraintSolver
    class ConstraintSolver
	attr_reader :log
	# Initialises a new solver.
	def initialize(log=nil)
	    if log.nil?
		@log = Logger.new(self.class.to_s)
	    else
		@log = log
	    end
	end

	# Attempts to solve the constraint satisfaction problem passed as an
	# argument and returns a list of all solutions. If there are no
	# solutions, an empty list is returned. The second argument is the time
	# limit to find a solution to the problem in seconds. This parameter is optional.
	# A queue of constraint lists to consider is assembled at the beginning
	# and only contains the initial list of constraints. While the problem
	# is solved, additional constraint lists may be added to the queue. The
	# new lists are relaxed versions of the problem with soft constraints
	# removed. These are processed one at a time.
	def solve(problem, limit=false)
	    @limit = limit
	    @problem = problem
	    @constraintChecks = 0
	    @nodeChecks = 0
	    @solutions = []
	    @time = Time.now
	    sortedConstraints = @problem.constraints.sort { |a,b| a.violationCost <=> b.violationCost }
	    if @limit
		a = @limit * 100
		@discardTimes = Hash.new
		b = Math.log((a * sortedConstraints.last.violationCost / @limit) + 1) / @limit
		sortedConstraints.each { |cons|
		    time = Math.log((a * cons.violationCost / @limit) + 1) / b
		    if not @discardTimes.has_key?(time)
			@discardTimes[time] = []
		    end
		    @discardTimes[time] << cons
		}
	    end
	    @constraintsQueue = [ [ sortedConstraints, 0 ] ]
	    while not @constraintsQueue.empty?
		@timeDroppedConstraints = []
		constraints = @constraintsQueue.shift
		retval = assignNextVariable(@problem.variables.sort { |a,b| b.merit <=> a.merit },
				   constraints[0], constraints[1])
		break if (retval == :solution and @problem.firstSolution) or (retval == :timeout)
		@constraintsQueue.uniq!
	    end
	    return @solutions, @nodeChecks, @constraintChecks
	end

	private

	# Attempts to assign a value that is consistent with all constraints to
	# the next variable. Arguments are the list of variables left to
	# process, the list of constraints to consider, and a measure for the
	# current violation of constraints.
	# Returns :solution iff a solution to the constraint satisfaction problem was
	# found; i.e. before the call there was only one unassigned variable and
	# a value that is consistent with all constraints was found in its
	# domain or the sum of the cost of all violated constraints is less than
	# the maximum cost for the problem. Else :noSolution if no solution was
	# found or :timeout if the time limit for solving was exceeded is
	# returned.
	# If a constraint is violated, but the cost still below the maximum
	# cost, a new list of constraints without the offending constraint is
	# added to the queue of list of constraints to process. It is not
	# processed immediately because first all the prunings have to be
	# undone, so the exploration of the current search tree finishes and
	# cleans up after itself.
	# This method calls checkNode to test a particular assignment.
	def assignNextVariable(variables, constraints, violation)
	    if @limit
		return :timeout unless (Time.now - @time) < @limit or @solutions.empty?
		discard = @discardTimes.keys.partition { |t| t <= Time.now - @time }[0]
		discardConstraints = discard.collect { |k| @discardTimes[k] }.flatten
		discardConstraints &= constraints
		unless discardConstraints.empty?
		    @log.info("Running out of time, discarding constraints " + discardConstraints.join(", "))
		    constraints -= discardConstraints
		    @timeDroppedConstraints += discardConstraints
		end
	    end
	    retval = :noSolution
	    current = variables.first
	    if current.assigned?
		allHolds = true
		constraints.allWithVariable(current).each { |constraint|
		    @constraintChecks += 1
		    holds = constraint.holds?
		    if holds == false
			if (violation + constraint.violationCost) <= @problem.maxViolation
			    @log.debug("Discarding constraint " + constraint.to_s +
				", cost " + constraint.violationCost.to_s)
			    @constraintsQueue << [ constraints - constraint, violation + constraint.violationCost ]
			end
			allHolds = false
		    end
		    break unless allHolds
		}
		retval = checkNode(current, variables, constraints, violation) if allHolds
	    else
		values = current.domain.sort { |a,b|
		    (@problem.meritMap.has_key?(b) ? @problem.meritMap[b] : 0) <=>
		    (@problem.meritMap.has_key?(a) ? @problem.meritMap[a] : 0)
		}
		values.each { |value|
		    current.value = value
		    retval = checkNode(current, variables, constraints, violation)
		    break if (retval == :solution and @problem.firstSolution) or (retval == :timeout)
		}
		current.reset
	    end
	    return retval
	end

	# Checks a particular node in the search tree. Arguments to the method
	# are the current node denoted by an assigned variablem the list of
	# variables to process, the list of constraints to consider, and the
	# current measure of violation cost.
	# The method revises the constraints that the current variable is
	# involved in, terminates the search if a domain wipeout occured or
	# records a solution if one is found. Violated constraints may be
	# disregarded if the cost of their violation plus the current costs of
	# constraint violations is less than the maximum violation allowed for
	# the problem.
	# If the assignment is consistent but there are still unprocessed
	# variables, it recursively calls assignNextVariable. Returns :solution iff a
	# solution was found, :noSolution if none was found and :timeout if the
	# time limit for solving the problem was exceeded.
	def checkNode(node, variables, constraints, violation)
	    retval = :noSolution
	    @nodeChecks += 1
	    @log.debug("Checking node " + node.to_s)
	    revisedDomains, wipeout, constraints, violation = reviseConstraints(node, constraints, violation)
	    unless wipeout # if a domain was wiped out we can skip the rest of the subtree
		if variables.size == 1
		    @constraintChecks += @timeDroppedConstraints.size
		    violation += @timeDroppedConstraints.inject(0) { |cost,cons|
			cost + (cons.holds? ? 0 : cons.violationCost )
		    }
		    solution = Solution.new(@problem.variables, @problem.meritMap, violation)
		    unless @solutions.include?(solution)
			@log.info("Found solution " + solution.to_s)
			@solutions << solution
		    end
		    retval = (@limit and (Time.now - @time) > @limit) ? :timeout : :solution
		else
		    retval = assignNextVariable(variables.rest, constraints, violation)
		end
	    end
	    revisedDomains.each { |domain| domain.undoPruning }
	    return retval
	end

	# Revises all constraints that involve <i>variable</i>. Additional
	# arguments are the list of constraints to consider, and the current
	# cost of constraint violations.
	# If a domain is wiped out during pruning, a new list of constraints
	# with the constraint that caused the wipeout removed is added to the
	# queue of constraint lists to process, the offending constraint is
	# removed from the list of constraints, the cost of violation updated,
	# and the pruning of the domains undone.
	# Returns the list of domains that have been revised, a boolean
	# indicating whether a domain was wiped out during pruning, the list of
	# constraints, and the current cost of violation.
	def reviseConstraints(variable, constraints, violation)
	    revisedDomains = []
	    wipeout = false
	    queue = constraints.notAllAssignedWithVariable(variable)
	    while not queue.empty?
		revisedConstraint = queue.shift
		revisedVariables, checks, wipeout = revisedConstraint.revise
		@log.debug("Revising constraint " + revisedConstraint.to_s + ", pruned " + revisedVariables.join(", "))
		@constraintChecks += checks
		if wipeout
		    if (violation + revisedConstraint.violationCost) <= @problem.maxViolation
			constraints -= revisedConstraint
			violation += revisedConstraint.violationCost
			@log.debug("Discarding constraint " + revisedConstraint.to_s +
			    ", cost " + revisedConstraint.violationCost.to_s)
			@constraintsQueue << [ constraints,
					       violation ]
			wipeout = false
			revisedVariables.each { |var| var.domain.undoPruning }
		    else
			revisedVariables.each { |var| revisedDomains << var.domain }
			break
		    end
		else
		    revisedVariables.each { |var|
			revisedDomains << var.domain
			constraints.notAllAssignedWithVariable(var).each { |constraint|
			    queue << constraint unless queue.include?(constraint) or constraint == revisedConstraint
			}
		    }
		end
	    end
	    return revisedDomains, wipeout, constraints, violation
	end
    end
end