/************************************************************************\
|* 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 EpsilonRealKMSVisitor extends RealizationVisitor implements Processor {
	Strategy<EpsilonReal> strategies;
	EpsilonReal[][] tableau;
	Rational shift;
	int p1level, p2level;

	Map<String, Integer> vars = new HashMap<String, Integer>();
	Map<String, Integer> equs = new HashMap<String, Integer>();
	private Integer getIdx(String s, Map<String, Integer> map) {
		Integer result = map.get(s);
		if (result == null) {
			result = map.size();
			map.put(s, result);
		}
		return result;
	}	

	private void print() {
		System.out.println("tableau");
		for (EpsilonReal[] eq : tableau) {
			for (EpsilonReal e : eq) {
				System.out.print(e + "\t");
			}
			System.out.println();
		}
		System.out.println();
		String[] srav = new String[vars.size()];
		String[] suqe = new String[equs.size()];
		for (Map.Entry<String, Integer> entry : vars.entrySet()) {
			srav[entry.getValue()] = entry.getKey();
		}
		for (Map.Entry<String, Integer> entry : equs.entrySet()) {
			suqe[entry.getValue()] = entry.getKey();
		}
		System.out.print("Max");
		for (int i = 0 ; i < tableau[0].length ; i++) {
			if (! tableau[0][i].isZero()) {
				System.out.print(" " + tableau[0][i] + "*\"" + srav[i] + "\"");
			}
		}
		System.out.println("\nSubj. to:");
		for (int j = 1 ; j < tableau.length ; j++) {
			System.out.print(suqe[j] + ":\t");
			for (int i = 1 ; i < tableau[j].length ; i++) {
				if (! tableau[j][i].isZero()) {
					System.out.print(" " + tableau[j][i].negate() + "*\"" + srav[i] + "\"");
				}
			}
			System.out.println(" <= " + tableau[j][0]);
		}
	}

	public void visitExtensiveForm(ExtensiveForm ef) {
		SizeVisitor sv = new SizeVisitor();
		ef.visitBy(sv);
		shift = sv.getMinPayoff().negate().add(Rational.ONE);
		int x = sv.p1realSize(),
			y = sv.p2realSize(),
			p = sv.p1infoSize(),
			q = sv.p2infoSize();
		tableau = new EpsilonReal[x + y + q][x + y + p];
		for (EpsilonReal[] array : tableau) {
			Arrays.fill(array, EpsilonReal.ZERO);
		}
		vars.clear();
		equs.clear();
		getIdx("COST", equs);
		getIdx("cons", vars);
		int equidx, varidx;

		// COST
		equidx = getIdx("COST", equs);
		varidx = getIdx("P" + p1know, vars);
		tableau[equidx][varidx] = EpsilonReal.ONE.negate();
		
		// E
		equidx = getIdx(p1real, equs);
		varidx = getIdx("P" + p1know, vars);
		tableau[equidx][varidx] = EpsilonReal.ONE;
		
		// F
		equidx = getIdx("Q" + p2know, equs);
		varidx = getIdx(p2real, vars);
		tableau[equidx][varidx] = EpsilonReal.ONE;

		// f
		equidx = getIdx("Q" + p2know, equs);
		varidx = getIdx("cons", vars);
		tableau[equidx][varidx] = EpsilonReal.ONE.negate();

		super.visitExtensiveForm(ef);
		//print();
	}

	public void visitImpPlayerNode(ImpPlayerNode node) {
		int equidx, varidx;
		switch (node.getPlayer()) {
			case 1:
				p1level++;
				equidx = getIdx(p1real, equs);
				varidx = getIdx("P" + p1know, vars);
				tableau[equidx][varidx] = EpsilonReal.ONE.negate();
				for (GameTree child : node) {
					equidx = getIdx(p1know + child.getP1Learn(), equs);
					tableau[equidx][varidx] = EpsilonReal.ONE;
					int tmpidx = getIdx("U" + p1know + child.getP1Learn(), vars);
					tableau[equidx][tmpidx] = EpsilonReal.ONE.negate();
					tableau[0][tmpidx] = new EpsilonReal(1, p1level);
				}
				super.visitImpPlayerNode(node);
				p1level--;
				break;
			case 2:
				p2level++;
				equidx = getIdx("Q" + p2know, equs);
				varidx = getIdx(p2real, vars);
				tableau[equidx][varidx] = EpsilonReal.ONE.negate();
				for (GameTree child : node) {
					varidx = getIdx(p2know + child.getP2Learn(), vars);
					tableau[equidx][varidx] = EpsilonReal.ONE;
					int tmpidx = getIdx("V" + p2know + child.getP2Learn(), equs);
					tableau[tmpidx][varidx] = EpsilonReal.ONE;
					tableau[tmpidx][0] = new EpsilonReal(-1, p2level);
				}
				super.visitImpPlayerNode(node);
				p2level--;
				break;
		}
	}	

	public void visitGameLeaf(GameLeaf leaf) {
		int p1realidx = getIdx(p1real, equs),
			p2realidx = getIdx(p2real, vars);
		tableau[p1realidx][p2realidx] = 
			tableau[p1realidx][p2realidx]
			.subtract(new EpsilonReal(prob.multiply(leaf.getValue().add(shift))));
	}

	public Strategy<EpsilonReal> getStrategies() {
		if (strategies == null) {
			LPDictionary<EpsilonReal> d = new LPDictionary<EpsilonReal>(tableau);
			//System.err.println(d);
			/*if (d.pivotToPCxSolution() == LPDictionary.Status.INFEASIBLE) {
				System.err.println("PCx solution discarded");
				EpsilonReal[] approx = new EpsilonReal[tableau.length + tableau[0].length - 1];
				Arrays.fill(approx, EpsilonReal.ZERO);
				d.pivotToSolution(approx);
			}
			assert d.isFeasible();
			LPDictionary.Status stat = d.onePhaseSimplex();*/
			LPDictionary.Status stat = d.twoPhaseSimplex();
			//int tmp = 0;
			//for (EpsilonReal[] er : tableau) System.err.println("tableau[" + (tmp++) + "][0] = " + er[0]);
			assert stat == LPDictionary.Status.OPTIMAL;
			EpsilonReal[] solu = d.getSolution();
			EpsilonReal[] dual = d.getDualSolution();
			Map<String, EpsilonReal> vals = new HashMap<String, EpsilonReal>();
			for (Map.Entry<String, Integer> entry : equs.entrySet()) {
				if (entry.getKey().startsWith("p1")) {
					vals.put(entry.getKey(), dual[d.n + entry.getValue()]);
				}
			}
			for (Map.Entry<String, Integer> entry : vars.entrySet()) {
				if (entry.getKey().startsWith("p2")) {
					vals.put(entry.getKey(), solu[entry.getValue()]);
				}
			}
			strategies = new Strategy<EpsilonReal>(vals);
		}
		return strategies;
	}

	public void process(ExtensiveForm ef, PrintStream out) {
		ef.visitBy(this);
		ef.flushTree();
		getStrategies();
		tableau = null;
		CounterStrategyVisitor<EpsilonReal> cv = new CounterStrategyVisitor<EpsilonReal>(strategies);
		ef.visitBy(cv);
		Strategy<EpsilonReal> counter = cv.getCounterStrategies();
		ValueVisitor<EpsilonReal> vv = new ValueVisitor<EpsilonReal>(strategies, strategies);
		ef.visitBy(vv);
		EpsilonReal value = vv.getValue();
		vv = new ValueVisitor<EpsilonReal>(strategies, counter);
		ef.visitBy(vv);
		EpsilonReal lowvalue = vv.getValue();
		vv = new ValueVisitor<EpsilonReal>(counter, strategies);
		ef.visitBy(vv);
		EpsilonReal highvalue = vv.getValue();
		StrategyPrintVisitor<EpsilonReal> spv = new StrategyPrintVisitor<EpsilonReal>();
		ef.visitBy(spv);
		out.println("An optimal strategy:");
		spv.print(strategies, ef, out);
		out.println("Value: " + value.rationalValue() + "  ~" + (highvalue.subtract(lowvalue)).rationalValue());
	}
}