//
// x = max(v) where v is IntVar[] and x is IntVar
//

package weeSeepy.constraints;

import weeSeepy.problem.*;
import weeSeepy.variables.*;
import weeSeepy.reversibles.*;

public class Max extends Constraint {

    IntVar x;
    IntVar[] v;
    ReversibleInt  indexOfLargest;
    ReversibleInt  largestMax;
    ReversibleInt  largestInst;
    ReversibleInt  largestMin;
    ReversibleBool entailed;
    ReversibleInt[] support; // support[x] = i where v[i] contains x
    int n, m, xLwb, xUpb;

    public Max(Problem pb,IntVar x,IntVar[] v){
	super(pb);
	this.x          = x;
	this.v          = v;
	this.n          = v.length;
	name            = "Max";
	largestInst     = new ReversibleInt(pb,Integer.MIN_VALUE);
	largestMin      = new ReversibleInt(pb,Integer.MIN_VALUE);
	largestMax  = new ReversibleInt(pb,Integer.MIN_VALUE);
	indexOfLargest  = new ReversibleInt(pb,-1);
	entailed        = new ReversibleBool(pb,false);
	xLwb            = x.getLwb();
	xUpb            = x.getUpb();
	m               = xUpb - xLwb + 1;
	support         = new ReversibleInt[m];

	addVariables(v);
	addVariable(x);
	for (int i=0;i<m;i++) support[i] = new ReversibleInt(pb,0);
    }

    public void propagate(){
	findLargestMax();
	findLargestMin();
	x.removeAbove(largestMax.getValue());
	x.removeBelow(largestMin.getValue());
	for (Integer val : x) 
	    if (!supported(val)) x.remove(val);
	for (IntVar y : v) y.removeAbove(x.max());
    }

    public void propagateInit(){
	propagate();
    }
    
    public void propagateRemoval(IntVar y, int val){
	if (!y.equals(x) && !supported(val)) x.remove(val);
    }
    
    public void propagateUPB(IntVar y){
	if (y.equals(x)){
	    for (IntVar z : v) z.removeAbove(x.max());
	    findLargestMax();
	}
	if (!y.equals(x)){
	    if (y.equals(v[indexOfLargest.getValue()])){
		findLargestMax();
		x.removeAbove(largestMax.getValue());
	    }
	    for (int val : x)
		if (val > y.max() && !supported(val)) x.remove(val);
	}
    }
    
    public void propagateLWB(IntVar y){
	if (!y.equals(x)) x.removeBelow(y.min());
    }
    
    public void propagateInstantiate(IntVar y){
	if (y.equals(x)){
	    if (x.max() < largestMax.getValue()){
		for (IntVar w : v) w.removeAbove(x.getValue());
		findLargestMax();
	    }
	    if (uniqueLargest()){
		v[indexOfLargest.getValue()].instantiate(x.getValue());
		largestInst.setValue(x.getValue());
	    }
	}
	if (!y.equals(x)){
	    x.removeBelow(y.getValue());
	    if (y.equals(v[indexOfLargest.getValue()]) && y.getValue() < largestMax.getValue()){
		findLargestMax();
		x.removeAbove(largestMax.getValue());
	    }
	    largestInst.setValue(Math.max(largestInst.getValue(),y.getValue()));
	    for (int val : x) if (!supported(val)) x.remove(val);
	}
	entailed.setValue(x.isInstantiated() && x.getValue() == largestInst.getValue());
    }

    public boolean isEntailed(){
	return x.isInstantiated() && x.getValue() == largestInst.getValue();
    }

    public Constraint makeOpposite(){
	return new Null(pb);
    }

    public boolean isLegal(){
	for (int val : x)
	    if (!supported(val)) return false;
	return x.max() == largestMax.getValue();
    }

    void findLargestMax(){
	int largest = Integer.MIN_VALUE;
	int index   = 0;
	for (int i=0;i<n;i++)
	    if (v[i].max() > largest){
		largest = v[i].max();
		index = i;
	    }
	largestMax.setValue(largest);
	indexOfLargest.setValue(index);
    }

    void findLargestMin(){
	for (int i=0;i<n;i++)
	    largestMin.setValue(Math.max(largestMin.getValue(),v[i].min()));
    }
    //
    // Find the largest lower bound in v.
    // x cannot be smaller than that!
    //

    boolean uniqueLargest(){
	int largest = largestMax.getValue();
	for (int i=indexOfLargest.getValue()+1;i<n;i++)
	    if (v[i].max() == largest) return false;
	return true;
    }
    //
    // Is the largest value in v unique?
    // Search starts after location of first largest found
    // Must be called after clean call to findLargest
    //

    boolean supported(int val){
	for (int i=support[val - xLwb].getValue();i<n;i++)
	    if (v[i].contains(val)){
		support[val - xLwb].setValue(i);
		return true;
	    }
	support[val - xLwb].setValue(n);
	return false;
    }
    //
    // Doess the value val in x.domain have support in array v?
    //
	    
}