#!/usr/bin/ruby

$:.unshift File.join(File.dirname(__FILE__), "..", "lib")

require 'test/unit'
require 'log4r'
require 'ConstraintSolver'

include Log4r

module ConstraintSolver
    class ConstraintSolverTest < Test::Unit::TestCase
	def setup
	    @var1 = Variable.new("x", Domain.new([ 1, 2 ].to_set), nil, 1)
	    @var2 = Variable.new("y", Domain.new([ 1, 2 ].to_set), nil, 2)
	    @var3 = Variable.new("z", Domain.new([ 1, 2 ].to_set), nil, 3)
	    relation = BinaryRelation.new("!=")
	    constraint1 = BinaryConstraint.new(@var1, @var2, relation)
	    constraint2 = BinaryConstraint.new(@var1, @var3, relation.clone)
	    constraint3 = BinaryConstraint.new(@var2, @var3, relation.clone)
	    @meritMap = { 1 => 2, 2 => 1 }
	    @solvableProblem = Problem.new([ @var1, @var2 ], ConstraintList.new([ constraint1 ]), @meritMap)
	    @unsolvableProblem = Problem.new([ @var1, @var2, @var3 ],
					     ConstraintList.new([ constraint1, constraint2, constraint3 ]))
	    @solver = ConstraintSolver.new
	end

	def testConstructor
	    assert_nothing_raised { ConstraintSolver.new }
	end

	def testSolvableProblem
	    #@solver.log.outputters = Outputter.stderr
	    solutions, nodeChecks, constraintChecks = @solver.solve(@solvableProblem)
	    assert_equal(false, solutions.empty?)
	    assert_equal(2, solutions.size)
	    @var1.value = 2
	    @var2.value = 1
	    assert_equal(Solution.new([ @var1, @var2 ], @meritMap), solutions[0])
	    assert_equal(5, solutions[0].merit)
	    @var1.value = 1
	    @var2.value = 2
	    assert_equal(Solution.new([ @var1, @var2 ], @meritMap), solutions[1])
	    assert_equal(4, solutions[1].merit)
	    @var1.reset
	    @var2.reset
	    assert_equal(4, nodeChecks)
	    assert_equal(4, constraintChecks)
	end

	def testUnsolvableProblem
	    #@solver.log.outputters = Outputter.stderr
	    solutions, nodeChecks, constraintChecks = @solver.solve(@unsolvableProblem)
	    assert_equal(true, solutions.empty?)
	    assert_equal(2, nodeChecks)
	    assert_equal(10, constraintChecks)
	end

	def testAllDifferentProblem
	    x = Variable.new("x", Domain.new([ 1, 2, 3 ].to_set))
	    y = Variable.new("y", Domain.new([ 1, 2, 3 ].to_set))
	    z = Variable.new("z", Domain.new([ 1, 2, 3 ].to_set))
	    constraint = AllDifferentConstraint.new([ x, y, z ])
	    #@solver.log.outputters = Outputter.stderr
	    solutions, nodeChecks, constraintChecks = @solver.solve(Problem.new([ x, y, z ], constraint))
	    assert_equal(6, solutions.size)
	    assert_equal(15, nodeChecks)
	    #assert_equal(27, constraintChecks)
	end

	def testAllDifferentWithoutAllDifferent
	    x = Variable.new("x", Domain.new([ 1, 2, 3 ].to_set))
	    y = Variable.new("y", Domain.new([ 1, 2, 3 ].to_set))
	    z = Variable.new("z", Domain.new([ 1, 2, 3 ].to_set))
	    relation = BinaryRelation.new("!=")
	    c1 = BinaryConstraint.new(x, y, relation)
	    c2 = BinaryConstraint.new(x, z, relation.clone)
	    c3 = BinaryConstraint.new(y, z, relation.clone)
	    #@solver.log.outputters = Outputter.stderr
	    solutions, nodeChecks, constraintChecks =
		@solver.solve(Problem.new([ x, y, z ], ConstraintList.new([ c1, c2, c3 ]))) 
	    assert_equal(6, solutions.size)
	    assert_equal(15, nodeChecks)
	    assert_equal(48, constraintChecks)
	end

	def testVariableAndValueOrdering
	    meritMap = { "foo" => 1, "bar" => 2, "foobar" => 3 }
	    x = Variable.new("x", Domain.new([ "foo", "bar", "foobar" ].to_set), nil, 1)
	    y = Variable.new("y", Domain.new([ "foo", "bar", "foobar" ].to_set), nil, 2)
	    c = AllDifferentConstraint.new([ x, y ])
	    #@solver.log.outputters = Outputter.stderr
	    solutions = @solver.solve(Problem.new([ x, y ], c, meritMap))[0]
	    assert_equal(6, solutions.size)
	    assert_equal(8, solutions[0].merit)
	    assert_equal(7, solutions[1].merit)
	    assert_equal(7, solutions[2].merit)
	    assert_equal(5, solutions[3].merit)
	    assert_equal(5, solutions[4].merit)
	    assert_equal(4, solutions[5].merit)
	end

	def testPreemptiveSolving
	    x = Variable.new("x", Domain.new([ 1, 2, 3 ].to_set))
	    y = Variable.new("y", Domain.new([ 1, 2, 3 ].to_set))
	    z = Variable.new("z", Domain.new([ 1, 2 ].to_set))
	    constraint = AllDifferentConstraint.new([ x, y, z ])
	    #@solver.log.outputters = Outputter.stderr
	    allSolutions = @solver.solve(Problem.new([ x, y, z ], constraint))[0]
	    assert_equal(4, allSolutions.size)
	    firstSolution = @solver.solve(Problem.new([ x, y, z ], constraint, {}, true))[0]
	    assert_equal(1, firstSolution.size)
	    assert_equal(allSolutions[0], firstSolution[0])
	end

	def testPartialAssignment
	    x = Variable.new("x", Domain.new([ 1, 2, 3 ].to_set), 1)
	    y = Variable.new("y", Domain.new([ 1, 2, 3 ].to_set))
	    z = Variable.new("z", Domain.new([ 1, 2, 3 ].to_set))
	    constraint = AllDifferentConstraint.new([ x, y, z ])
	    #@solver.log.outputters = Outputter.stderr
	    solutions = @solver.solve(Problem.new([ x, y, z ], constraint))[0]
	    assert_equal(2, solutions.size)
	end

	def testSeveralAllDiff
	    a = Variable.new("11", Domain.new([ 1, 2 ].to_set))
	    b = Variable.new("12", Domain.new([ 1, 2 ].to_set), 2)
	    c = Variable.new("21", Domain.new([ 1, 2 ].to_set))
	    d = Variable.new("22", Domain.new([ 1, 2 ].to_set), 2)
	    constraints = ConstraintList.new
	    constraints << AllDifferentConstraint.new([ a, b ])
	    constraints << AllDifferentConstraint.new([ c, d ])
	    constraints << AllDifferentConstraint.new([ a, c ])
	    constraints << AllDifferentConstraint.new([ b, d ])
	    solutions = @solver.solve(Problem.new([ a, b, c, d ], constraints))[0]
	    assert_equal(0, solutions.size)
	end

	def testSoftConstraints
	    x = Variable.new("x", Domain.new([ 1 ].to_set))
	    y = Variable.new("y", Domain.new([ 1 ].to_set))
	    constraints = ConstraintList.new
	    constraints << BinaryConstraint.new(x, y, BinaryRelation.new("!="), 0.5)
	    problem = Problem.new([ x, y ], constraints, {}, false, 1)
	    #@solver.log.outputters = Outputter.stderr
	    solutions, nodeChecks, constraintChecks = @solver.solve(problem)
	    assert_equal(1, solutions.size)
	    assert_equal(1, solutions[0].variables[0].value)
	    assert_equal(1, solutions[0].variables[1].value)
	    assert_equal(0.5, solutions[0].violation)
	    assert_equal(4, nodeChecks)
	    assert_equal(1, constraintChecks)

	    x.value = 1
	    y.value = 1
	    #@solver.log.outputters = Outputter.stderr
	    solutions, nodeChecks, constraintChecks = @solver.solve(problem)
	    assert_equal(1, solutions.size)
	    assert_equal(1, solutions[0].variables[0].value)
	    assert_equal(1, solutions[0].variables[1].value)
	    assert_equal(0.5, solutions[0].violation)
	    assert_equal(2, nodeChecks)
	    assert_equal(1, constraintChecks)
	end

	def testComplexSoftConstraints
	    a = Variable.new("a", Domain.new([ 1, 2, 3 ].to_set))
	    b = Variable.new("b", Domain.new([ 1, 2, 3 ].to_set))
	    c = Variable.new("c", Domain.new([ 1, 2, 3 ].to_set))
	    d = Variable.new("d", Domain.new([ 1, 2, 3 ].to_set))
	    constraints = ConstraintList.new
	    constraints << AllDifferentConstraint.new([ a, b, c, d ], 0.1)
	    rel = BinaryRelation.new("<")
	    constraints << BinaryConstraint.new(a, b, rel, 0.5)
	    constraints << BinaryConstraint.new(b, c, rel, 0.5)
	    constraints << BinaryConstraint.new(c, d, rel, 0.5)
	    problem = Problem.new([ a, b, c, d ], constraints, {}, false, 1)
	    #@solver.log.outputters = Outputter.stderr
	    solutions, nodeChecks, constraintChecks = @solver.solve(problem)
	    assert_equal(15, solutions.size)
	    assert_equal(90, nodeChecks)
	    assert_equal(220, constraintChecks)
	    solutions.each { |solution|
		assert_equal(0.6, solution.violation)
	    }
	end

	def testTimeLimitHardConstraints
	    x = Variable.new("x", Domain.new([ 1, 2, 3 ].to_set))
	    y = Variable.new("y", Domain.new([ 1, 2, 3 ].to_set))
	    z = Variable.new("z", Domain.new([ 1, 2, 3 ].to_set))
	    relation = BinaryRelation.new("!=")
	    c1 = BinaryConstraint.new(x, y, relation)
	    c2 = BinaryConstraint.new(x, z, relation.clone)
	    c3 = BinaryConstraint.new(y, z, relation.clone)
	    #@solver.log.outputters = Outputter.stderr
	    solutions, nodeChecks, constraintChecks =
		@solver.solve(Problem.new([ x, y, z ], ConstraintList.new([ c1, c2, c3 ])), 0.000001) 
	    assert_equal(1, solutions.size)
	    assert_equal(-3, solutions[0].merit)
	    assert_equal(3, solutions[0].violation)
	end

	def testTimeLimitSoftConstraints
	    x = Variable.new("x", Domain.new([ 1, 2, 3 ].to_set))
	    y = Variable.new("y", Domain.new([ 1, 2, 3 ].to_set))
	    z = Variable.new("z", Domain.new([ 1, 2, 3 ].to_set))
	    relation = BinaryRelation.new("!=")
	    c1 = BinaryConstraint.new(x, y, relation, 0.2)
	    c2 = BinaryConstraint.new(x, z, relation.clone, 0.5)
	    c3 = BinaryConstraint.new(y, z, relation.clone, 1)
	    #@solver.log.outputters = Outputter.stderr
	    # Depending on the time limit and the particular machine,
	    # constraints will be discarded. Change the value and enable logging
	    # to see for yourself.
	    timeLimit = 0.0014
	    solutions, nodeChecks, constraintChecks =
		@solver.solve(Problem.new([ x, y, z ], ConstraintList.new([ c1, c2, c3 ]), {}, true, 1), timeLimit) 
	    assert_equal(1, solutions.size)
	end

	def testTimeLimitSoftAllDiff
	    x = Variable.new("x", Domain.new([ 1, 2 ].to_set))
	    y = Variable.new("y", Domain.new([ 1, 2 ].to_set))
	    constraint = AllDifferentConstraint.new([ x, y ], 1)
	    #@solver.log.outputters = Outputter.stderr
	    solutions, nodeChecks, constraintChecks = @solver.solve(Problem.new([ x, y ], constraint,
										{ 1 => 1, 2 => 2 }, false, 0), 10)
	    assert_equal(2, solutions.size)
	    assert_equal(4, nodeChecks)
	end

	def testTupleConstraint
	    x = Variable.new("x", Domain.new([ 1, 2, 3 ].to_set))
	    y = Variable.new("y", Domain.new([ 1, 2, 3 ].to_set))
	    z = Variable.new("z", Domain.new([ 1, 2, 3 ].to_set))
	    constraint = TupleConstraint.new([ x, y, z ], [ [ 1, 2, 3 ], [ 3, 2, 1 ] ])
	    #@solver.log.outputters = Outputter.stderr
	    solutions, nodeChecks, constraintChecks = @solver.solve(Problem.new([ x, y, z ], constraint))
	    assert_equal(2, solutions.size)
	    assert_equal(7, nodeChecks)
	    assert_equal(0, constraintChecks)

	    assert_equal(1, solutions[0].variables[0].value)
	    assert_equal(2, solutions[0].variables[1].value)
	    assert_equal(3, solutions[0].variables[2].value)

	    assert_equal(3, solutions[1].variables[0].value)
	    assert_equal(2, solutions[1].variables[1].value)
	    assert_equal(1, solutions[1].variables[2].value)
	end

	def testOneOfEqualsConstraint
	    x = Variable.new("x", Domain.new([ 1, 2 ].to_set))
	    y = Variable.new("y", Domain.new([ 1, 2 ].to_set))
	    constraint = OneOfEqualsConstraint.new([ x, y ], 2)
	    #@solver.log.outputters = Outputter.stderr
	    solutions, nodeChecks, constraintChecks = @solver.solve(Problem.new([ x, y ], constraint))
	    assert_equal(3, solutions.size)
	    assert_equal(5, nodeChecks)
	    assert_equal(0, constraintChecks)

	    assert_equal(1, solutions[0].variables[0].value)
	    assert_equal(2, solutions[0].variables[1].value)

	    assert_equal(2, solutions[1].variables[0].value)
	    assert_equal(1, solutions[1].variables[1].value)

	    assert_equal(2, solutions[2].variables[0].value)
	    assert_equal(2, solutions[2].variables[1].value)
	end
    end
end