#!/usr/bin/ruby

require 'extensions'
require 'AbstractConstraint'
require 'GraphUtils'
require 'set'

module ConstraintSolver
    # Represents the all different constraint.
    class AllDifferentConstraint < AbstractConstraint
	attr_reader :variables, :violationCost
	# Initialises a new all different constraint.
	# The constructor takes the list of variables that must be different as
	# an argument. Optionally, a cost for violating the constraint can be
	# specified.
	def initialize(variables, violationCost=1)
	    if variables.empty? or variables.size == 1
		raise ArgumentError, "List of variables must contain at least two elements!"
	    end
	    @variables = variables
	    @violationCost = violationCost
	end

	# Checks whether all the variables have different values assigned to
	# them.
	def holds?
	    assigned = @variables.select { |var| var.assigned? }
	    assigned.each { |variable|
		assigned.eachAfter(variable) { |otherVariable|
		    if variable.value == otherVariable.value
			return false
		    end
		}
	    }
	    return true
	end

	def allAssigned?
	    @variables.each { |var|
		return false if not var.assigned?
	    }
	    return true
	end

	def include?(variable)
	    @variables.include?(variable)
	end

	def to_s
	    @variables.collect { |var| var.name }.join(" != ")
	end

	def to_s_full
	    @variables.collect { |var| var.to_s }.join(" != ")
	end

	def ==(constraint)
	    return false unless constraint.kind_of?(AllDifferentConstraint)
	    (@variables == constraint.variables) and (@violationCost == constraint.violationCost)
	end

	def each
	    @variables.each { |var|
		yield var
	    }
	end

	def revise_decomposed_local
	    revisedVariables = []
	    wipeout = false
	    pruneList = Set.new
	    assignedVariables, unassignedVariables = @variables.partition { |var| var.assigned? }
	    pruneList.merge(assignedVariables.collect { |var| var.value })
	    unassignedVariables.find_all { |var| var.domain.include_any?(pruneList) }.each { |var|
		begin
		    var.domain.prune(pruneList)
		rescue DomainWipeoutException
		    wipeout = true
		end
		revisedVariables << var
		break if wipeout
	    }
	    unless wipeout
		workQueue = unassignedVariables.find_all { |var| var.domain.size == 1 }
		while not workQueue.empty?
		    currentVariable = workQueue.shift
		    currentValue = currentVariable.domain.first
		    ((unassignedVariables - [ currentVariable ]).find_all { |var|
			var.domain.include?(currentValue)
		    }).each { |var|
			begin
			    var.domain.prune(currentValue)
			rescue DomainWipeoutException
			    wipeout = true
			end
			revisedVariables << var
			break if wipeout
			workQueue << var if var.domain.size == 1
		    }
		end

		unless wipeout
		    # check satisfiability
		    valueList = Set.new
		    unassignedVariables.each { |var|
			valueList.merge(var.values)
		    }
		    if unassignedVariables.size > valueList.size
			wipeout = true
		    end
		end
	    end
	    return revisedVariables, 0, wipeout
	end

	# hyperarc consistency algorithm due Regin (1994)
	def revise_hyperarc
	    wipeout = false
	    unless @value_graph
		e = Hash.new
		@variables.each { |var|
		    e[var.name] = var.domain.values.dup
		}
		@value_graph = GraphUtils::BipartiteGraph.new(e.keys.to_set, e.values.to_set.flatten, e)
	    else
		# update graph
		@value_graph.e.clear
		@variables.each { |var|
		    @value_graph.e[var.name] = var.domain.values.dup
		}
		# The set of values is not updated because spurious values with
		# no edges attached to them add only minimal overhead
		#@value_graph.y = @value_graph.e.values.to_set.flatten
	    end

	    matching = @value_graph.maximum_matching
	    if matching.size < @variables.size
		return [], 0, true
	    end

	    pruneMap = @value_graph.removable_values(matching)

	    revisedVariables = Array.new
	    pruneMap.each { |name,pruneList|
		var = @variables.find { |var| var.name == name }
		begin
		    var.domain.prune(pruneList)
		rescue DomainWipeoutException
		    wipeout = true
		end
		revisedVariables << var
		break if wipeout
	    }

	    return revisedVariables, 0, wipeout
	end

	alias_method :revise, :revise_decomposed_local
    end
end