/************************************************************************\
|* gtf is a framework for analyzing two-player zero-sum games           *|
|* Copyright (C) 2005 Troels Bjerre Sorensen                            *|
|*                                                                      *|
|* This program is free software; you can redistribute it and/or modify *|
|* it under the terms of the GNU General Public License as published by *|
|* the Free Software Foundation; either version 2 of the License, or    *|
|* (at your option) any later version.                                  *|
|*                                                                      *|
|* This program is distributed in the hope that it will be useful, but  *|
|* WITHOUT ANY WARRANTY; without even the implied warranty of           *|
|* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU    *|
|* General Public License for more details.                             *|
|*                                                                      *|
|* You should have received a copy of the GNU General Public License    *|
|* along with this program; if not, write to the                        *|
|* Free Software Foundation, Inc., 59 Temple Place - Suite 330,         *|
|* Boston, MA 02111-1307, USA.                                          *|
\************************************************************************/

package gtf;

import gtf.game.*;
import gtf.util.*;
import java.io.*;
import java.util.*;

public class KollerMegiddoVisitor extends RealizationVisitor implements Processor {
	MPS<DoubleReal> problem;
	String name;
	Strategy<DoubleReal> strategies;
	DoubleReal shift;
	
	Map<String, String> vars = new HashMap<String, String>();
	private String getVarName(String s) {
		String result = vars.get(s);
		if (result == null) {
			result = "X" + vars.size();
			vars.put(s, result);
		}
		return result;
	}	

	public void visitExtensiveForm(ExtensiveForm ef) {
		SizeVisitor sv = new SizeVisitor();
		ef.visitBy(sv);
		shift = sv.getMinPayoff().negate().approxAdd(DoubleReal.ONE);
		String p1realvar = getVarName(p1real);
		String p2realvar = getVarName(p2real);
		String cost = "P" + p1realvar;
		name = ef.getName();
		problem = new MPS<DoubleReal>(name);
		problem.declareEquation("N", "COST");
		problem.declareFreeVariable(cost);
		problem.setCoef(cost, "COST", DoubleReal.ONE);
		problem.declareEquation("G", p1realvar);
		problem.setCoef(cost, p1realvar, DoubleReal.ONE);
		String eq = "Q" + p2realvar;
		problem.declareEquation("E", eq);
		problem.setCoef(p2realvar, eq, DoubleReal.ONE);
		problem.setRHS(eq, DoubleReal.ONE);
		super.visitExtensiveForm(ef);
	}

	public void visitImpPlayerNode(ImpPlayerNode node) {
		String var, eq;
		switch (node.getPlayer()) {
			case 1:
				var = "P" + getVarName(p1know);
				problem.declareFreeVariable(var);
				eq = getVarName(p1real);
				problem.declareEquation("G", eq);
				problem.setCoef(var, eq, DoubleReal.ONE.negate());
				for (GameTree child : node) {
					eq = getVarName(p1know + child.getPlayerLearn(1));
					problem.setCoef(var, eq, DoubleReal.ONE);
				}					
				break;
			case 2:
				var = getVarName(p2real);
				eq = "Q" + getVarName(p2know);
				problem.declareEquation("E", eq);
				problem.setCoef(var, eq, DoubleReal.ONE.negate());
				for (GameTree child : node) {
					var = getVarName(p2know + child.getPlayerLearn(2));
					problem.setCoef(var, eq, DoubleReal.ONE);
				}
				break;
		}
		super.visitImpPlayerNode(node);
	}	

	public void visitGameLeaf(GameLeaf leaf) {
		String var = getVarName(p2real);
		String eq = getVarName(p1real);
		problem.declareEquation("G", eq);
		problem.addCoef(var, eq, prob.approxMultiply(leaf.getPlayerValue(2)));
	}

	public Strategy<DoubleReal> getStrategies() {
		if (strategies == null) strategies = new PCx().solve(problem, vars);
		return strategies;
	}

	public void process(ExtensiveForm ef, PrintStream out) {
		ef.visitBy(this);
		getStrategies();
		CounterStrategyVisitor<DoubleReal> cv = new CounterStrategyVisitor<DoubleReal>(strategies);
		ef.visitBy(cv);
		Strategy<DoubleReal> counter = cv.getCounterStrategies();
		ValueVisitor<DoubleReal> vv = new ValueVisitor<DoubleReal>(strategies, strategies);
		ef.visitBy(vv);
		DoubleReal value = vv.getValue();
		vv = new ValueVisitor<DoubleReal>(strategies, counter);
		ef.visitBy(vv);
		DoubleReal lowvalue = vv.getValue();
		vv = new ValueVisitor<DoubleReal>(counter, strategies);
		ef.visitBy(vv);
		DoubleReal highvalue = vv.getValue();
		out.println("An optimal strategy:");
		strategies.print(out);
		out.println("\nValue: " + value + "  ~" + (highvalue.subtract(lowvalue)));
	}
}