/************************************************************************\
|* 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 RationalReducedKMSVisitor extends RealizationVisitor implements Processor {
	Strategy<Rational> strategies;
	Rational[][] tableau;

	Map<String, List<Pair<Integer, Rational>>> 
		vars = new HashMap<String, List<Pair<Integer, Rational>>>(),
		equs = new HashMap<String, List<Pair<Integer, Rational>>>();

	int varnum, equnum;

	private List<Pair<Integer, Rational>> getIdx(String s, Map<String, List<Pair<Integer, Rational>>> map) {
		List<Pair<Integer, Rational>> result = map.get(s);
		if (result == null) {
			//System.err.println((map == vars ? "var\t" + varnum : "equ\t" + equnum) + "\t" + s);
			result = new ArrayList<Pair<Integer, Rational>>();
			int idx = map == vars ? varnum++ : equnum++;
			result.add(new Pair<Integer, Rational>(idx, Rational.ONE));
			map.put(s, result);
		}
		return result;
	}	

	private void setIdx(String s, Map<String, List<Pair<Integer, Rational>>> map, List<Pair<Integer, Rational>> elm) {
		map.put(s, elm);
	}

	public void visitExtensiveForm(ExtensiveForm ef) {
		SizeVisitor sv = new SizeVisitor();
		ef.visitBy(sv);
		int x = sv.p1realSize(),
			y = sv.p2realSize(),
			p = sv.p1infoSize(),
			q = sv.p2infoSize();
		tableau = new Rational[x - p + q][y - q + p];
		for (Rational[] array : tableau) {
			Arrays.fill(array, Rational.ZERO);
		}
		vars.clear();
		equs.clear();
		getIdx("COST", equs); // Setting cost idx to 0
		getIdx("cons", vars); // Setting cons idx to 0
		int equidx, varidx;

		// E
		List<Pair<Integer, Rational>> al = new ArrayList<Pair<Integer, Rational>>();
		al.add(new Pair<Integer, Rational>(0, Rational.ONE.negate()));
		//setIdx(p1real, equs, al);
		setIdx(p1real, equs, getIdx("cons", vars));
		
		// F
		setIdx(p2real, vars, getIdx("cons", vars));
		
		super.visitExtensiveForm(ef);
	}

	public void visitImpPlayerNode(ImpPlayerNode node) {
		switch (node.getPlayer()) {
			case 1:
				if (! vars.containsKey("P" + p1know)) {
					int varidx = getIdx("P" + p1know, vars).iterator().next().first;
					for (Pair<Integer, Rational> equidx : getIdx(p1real, equs)) {
						tableau[equidx.first][varidx] = equidx.second.negate();
					}
					List<String> childreallist = new ArrayList<String>();
					for (GameTree child : node) childreallist.add(p1know + child.getP1Learn());
					String[] childreals = childreallist.toArray(new String[childreallist.size()]);
					Arrays.sort(childreals);
					List<Pair<Integer, Rational>> childlist = new ArrayList<Pair<Integer, Rational>>();
					childlist.addAll(getIdx(p1real, equs));
					for (int i = 1 ; i < childreals.length ; i++) {
						int equidx = getIdx(childreals[i], equs).iterator().next().first;
						tableau[equidx][varidx] = Rational.ONE;
						childlist.add(new Pair<Integer, Rational>(equidx, Rational.ONE.negate()));
					}
					setIdx(childreals[0], equs, childlist);
				}
				break;
			case 2:
				if (! equs.containsKey("Q" + p2know)) {
					int equidx = getIdx("Q" + p2know, equs).iterator().next().first;
					for (Pair<Integer, Rational> varidx : getIdx(p2real, vars)) {
						tableau[equidx][varidx.first] = varidx.second;
					}
					List<String> childreallist = new ArrayList<String>();
					for (GameTree child : node) childreallist.add(p2know + child.getP2Learn());
					String[] childreals = childreallist.toArray(new String[childreallist.size()]);
					Arrays.sort(childreals);
					List<Pair<Integer, Rational>> childlist = new ArrayList<Pair<Integer, Rational>>();
					childlist.addAll(getIdx(p2real, vars));
					for (int i = 1 ; i < childreals.length ; i++) {
						int varidx = getIdx(childreals[i], vars).iterator().next().first;
						tableau[equidx][varidx] = Rational.ONE.negate();
						childlist.add(new Pair<Integer, Rational>(equidx, Rational.ONE.negate()));
					}
					setIdx(childreals[0], vars, childlist);
				}
				break;
		}
		super.visitImpPlayerNode(node);
	}	

	public void visitGameLeaf(GameLeaf leaf) {
		for (Pair<Integer, Rational> p1realidx : getIdx(p1real, equs)) {
			for (Pair<Integer, Rational> p2realidx : getIdx(p2real, vars)) {
				tableau[p1realidx.first][p2realidx.first] = 
					tableau[p1realidx.first][p2realidx.first]
					.subtract(prob
							.multiply(leaf.getValue())
							.multiply(p1realidx.second)
							.multiply(p2realidx.second));
			}
		}
	}

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

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