/**
 * DealSelector.java
 * Theodoros Lappas
 * http://www.cs.ucr.edu/~tlappas/
 */
package solver;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.FileWriter;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Vector;

public class DealSelector {

	private int marketNum; // number of markets
	private int couponCapacity; // total coupon budget

	// max number of deals that can be selected from the same market
	private int marketLimit;

	private int largestMarket;// upper bound on the number of merchants per
								// market

	private int couponDiv; // used to bucketize coupons in 10s 100s etc

	private float[][] revenueTable;

	private int[][] backTrackingTable;

	private Vector<Vector<Deal>> deals;

	private String resultsFile;

	public static void main(String args[]) throws Exception {

		int capacity = Integer.parseInt(args[0]);
		int maxNumberOfDealsPerMarket = Integer.parseInt(args[1]);
		int div = Integer.parseInt(args[2]);
		String inFile = args[3];
		String outFile = args[4];

		DealSelector selector = new DealSelector(capacity,
				maxNumberOfDealsPerMarket, div, inFile, outFile);

		float totalRevenue = selector.run();

		System.out.println(totalRevenue);
	}

	/**
	 * Constructor
	 * 
	 * @param mNum
	 * @param cCap
	 * @param marLim
	 * @param larMar
	 * @param cDiv
	 * @throws Exception
	 */
	public DealSelector(int cCap, int marLim, int cDiv, String inFile,
			String outFile) throws Exception {

		couponCapacity = cCap;
		marketLimit = marLim;

		deals = new Vector<Vector<Deal>>();
		int maxPossibleCouponsSold = loadDealsPerMarket(inFile);

		// marketNum =3;// mNum;
		// largestMarket = larMar;
		couponDiv = cDiv;

		resultsFile = outFile;

		// -------------Initialize tables------------------------
		revenueTable = new float[marketNum + 1][couponCapacity + 1];
		backTrackingTable = new int[marketNum + 1][couponCapacity + 1];

		couponCapacity = Math.min(couponCapacity, maxPossibleCouponsSold);
		couponCapacity /= couponDiv;

	}

	private float run() throws Exception {

		float val, highestRevenue;
		int winnerC;
		float[] finalInnerRow = null;

		FileWriter fw = new FileWriter(this.resultsFile);

		int[][][][] merchantBacktracking = new int[marketNum + 1][][][];

		// for each market
		for (int market = 1; market < marketNum + 1; ++market) {

			MerchantSelector inner = new MerchantSelector(largestMarket,
					marketLimit, couponCapacity);

			inner.run(deals.get(market).size() - 1, deals.get(market));

			finalInnerRow = inner.getFinalRow();
			// evaluate revenue outcomes for different coupon assignements to
			// the current merchant and get the best one.
			for (int c = 0; c < couponCapacity + 1; ++c) {
				highestRevenue = -Float.MAX_VALUE;
				winnerC = -1;
				for (int c1 = 0; c1 <= c; ++c1) {
					val = revenueTable[market - 1][c - c1] + finalInnerRow[c1];
					if (highestRevenue < val) {
						highestRevenue = val;
						winnerC = c1;
					}
				}
				revenueTable[market][c] = highestRevenue;
				backTrackingTable[market][c] = winnerC;
			}

			merchantBacktracking[market] = inner.getBackTrackingTable();
			inner = null;
		}

		// ----Backtracking-------------------------

		int capacityPtr = couponCapacity;
		int myBudget;

		// for each market
		for (int market = marketNum; market >= 1; --market) {

			myBudget = backTrackingTable[market][capacityPtr];

			if (myBudget == 0) {
				// System.out.println("Market " + market + " gets nothing");
				continue;
			}

			capacityPtr -= myBudget;

			// System.out.println();
			fw.write("Market " + market + " : " + myBudget + " coupons\n");
			int merchantBT[][][] = merchantBacktracking[market];

			int myLimit = marketLimit;
			for (int merchant = deals.get(market).size() - 1; merchant >= 1; --merchant) {

				if (merchantBT[merchant][myBudget][myLimit] > 0) {
					fw.write("\tMerchant " + merchant + " : "
							+ merchantBT[merchant][myBudget][myLimit]
							+ " coupons\n");
					myLimit--;
				}

			}
			// fw.write("\n");

		}
		fw.close();
		return revenueTable[marketNum][couponCapacity];
	}

	/**
	 * Loads the deals per market. One market per line. Tab separated. Each
	 * field is C:B, where C is the coupons expected to be bought for this deal
	 * and B is the deal's benefit.
	 * 
	 * @param dealsFile
	 * @param cDiv
	 *            divisor for scaling the DP table
	 * @param marketLimit
	 *            max number of deals allowed per Market (diversity constraint)
	 * @return the max number of deals that are possible to be absorbed by any
	 *         market
	 * @throws Exception
	 */
	private int loadDealsPerMarket(String dealsFile) throws Exception {

		deals.add(null);
		BufferedReader br = new BufferedReader(new FileReader(dealsFile));
		int maxPossibleCoupons = 0;
		int marketCnt = 1;
		while (br.ready()) {
			marketNum++;
			String line = br.readLine();
			String toks[] = line.split("\t");
			this.largestMarket = Math.max(this.largestMarket, toks.length);

			PriorityQueue<Integer> PQ = new PriorityQueue<Integer>(10,
					Collections.reverseOrder());

			Vector<Deal> dealsInMarket = new Vector<Deal>();
			dealsInMarket.add(null);

			// for each deal
			for (int l = 1; l < toks.length; ++l) {
				String tok = toks[l];
				int coupons = Integer.parseInt(tok.substring(0,
						tok.indexOf(":")));
				float benefitPerCoupon = Float.parseFloat(tok.substring(tok
						.indexOf(":") + 1));
				float revenue = coupons * benefitPerCoupon;

				// round coupons
				if (couponDiv > 1) {
					coupons = new Double(Math.ceil(coupons * 1d / couponDiv))
							.intValue();
				}

				PQ.add(coupons);
				dealsInMarket.add(new Deal(coupons, marketCnt, revenue));
			}

			// add the capacities of the @marketLimit deals that require the
			// most coupons for this market
			for (int i = 0; i < marketLimit; ++i) {
				maxPossibleCoupons += (PQ.poll());
			}

			deals.add(dealsInMarket);

			marketCnt++;
		}
		br.close();
		return maxPossibleCoupons;
	}

}