// Source: "Software Design ...", John A Robinson, Newnes, 2004, Chapter 17.
#include <string>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
using namespace std;
class stable {	
// The 2D table of tcells plus row and column labels
class tcell {
// Structure of each cell in the table: basic unit of the collection
	bool cellused;
	int rowindex;
	int colindex;
	string content;
public:
	tcell() {
		cellused = 0;
		content = "";
		rowindex = colindex = -1;
		};
	~tcell() {
		};
	void setindices(const int r, const int c) {
		rowindex = r;
		colindex = c;
		};
	void setval(const string& cont) {
		cellused = 1;
		content = cont;
		};
	void delval() {
		cellused = 0;
		content = "";
		};
	const string getval() {
		return content;
		};
	const int row() {
		return rowindex;
		};
	const int col() {
		return colindex;
		};
	const bool used() {
		return cellused;
		};
	};
	int max_rows;	// Set on instantiation
	int max_cols;	// Set on instantiation
	int lowest_available_row; // Row numbers equal to or higher than
				  // this are not yet used.
	int lowest_available_col; // No rows have entries is this or any
				  // higher numbered column
	tcell *rlabel;	// Row labels are outsize the table itself
			// in a 1D array
	tcell *clabel;	// Column labels are outsize the table itself
			// in a 1D array
	tcell **cell;	// The array of pointers to arrays (rows) of cells
	void read(istream& in, const bool withlabels, const char coldelim, 
					const char rowdelim) {
		// Read from file with or without labels.
		reset();
		string line;
		int startindex;	// -1 for with labels, because first row and
				// column are before zeroth row and colum; 
				// 0 for without labels.
		if (withlabels)
			startindex = -1;
		else 
			startindex = 0;
		int r = startindex;
		while(!in.eof()) {
			getline(in,line, rowdelim);
			if ((line == "")&&in.eof())	// Nothing after final rowdelim
				break;
			int c = startindex;
			string temp;
			string::size_type currpos, delimpos;
			currpos = 0;
			while ((delimpos = line.find(coldelim, currpos)) 
							!= string::npos){
				temp = line.substr(currpos,delimpos-currpos);
				if ((r ==-1)&&(c==-1)) {
					if (currpos != delimpos) {
						cout << 
"Warning: readwithlabels from file that doesn't begin with a column\n\
delimiter. The first entry will be lost.\n";
						}
					c++;
					}
				else if (r == -1) 
					setcollabel(c++,temp);
				else if (c == -1) {
					setrowlabel(r,temp);
					c++;
					}
				else
					set(r,c++,temp);
				currpos = delimpos+1;
				}
			temp = line.substr(currpos);
			if (r == -1)
				setcollabel(c,temp);
			else if (c == -1)
				setrowlabel(r,temp);
			else
				set(r,c,temp);
			r++;
			}
		if (!withlabels) { // Reset all labels
			for (r = 0; r < lowest_available_row; r++)
				rlabel[r].setval("");
			for (int c = 0; c < lowest_available_col; c++)
				clabel[c].setval("");
			}
		};
	int write(ostream& out, const bool withlabels, const char coldelim, 
			const char rowdelim, const bool includelastrowdelim) {
		int i, j;
		if (withlabels) {
			out << coldelim;	// Top left corner: No label
			for (i = 0; i < lowest_available_col-1; i++)
				out << clabel[i].getval() << coldelim;
			out << clabel[i].getval() << rowdelim;
			}
		for (i = 0; i < lowest_available_row; i++) {
			if (withlabels)
				out << rlabel[i].getval() << coldelim;
			// Don't output column delimiters after last entry on a row
			int last_used = lowest_available_col-1;
			while ((last_used >= 0) && !cell[i][last_used].used())
				last_used--;
			for (j = 0; j < last_used; j++)
				out << cell[i][j].getval() << coldelim;
			if (last_used >= 0)
				out << cell[i][j].getval();
			if ((i < lowest_available_row-1) || includelastrowdelim)
				out << rowdelim;
			}
		};
public:
	stable(const int r = 2048, const int c = 256) {
		max_rows = r;
		max_cols = c;
		lowest_available_row = 0;
		lowest_available_col = 0;
		rlabel = new tcell[max_rows]; // Row labels
		clabel = new tcell[max_cols]; // Column labels
		cell = new tcell *[max_rows];  // All the cells
		for (int i = 0; i < max_rows; i++)
			cell[i] = 0;
		};
	~stable() {
		for (int i = 0; i < max_rows; i++) {
			if (cell[i])
				delete [] cell[i];
			}
		delete [] cell;
		delete [] clabel;
		delete [] rlabel;
		};
	void reset() {	// Clean up the table for reuse
		for (int i = 0; i < max_rows; i++) {
			if (cell[i]) {
				for (int j = 0; j < max_cols; j++)
					cell[i][j].delval();
				}
			}
		lowest_available_row = 0;
		lowest_available_col = 0;
		}
	int nrows() {
		return lowest_available_row;
		}
	int ncols() {
		return lowest_available_col;
		}
	int set(const int row, const int col, const string& val) {
		if ((row < 0)||(col < 0)||(row >= max_rows)||(col >= max_cols))
			return -1;
		if (row >= lowest_available_row) {
			while (lowest_available_row <= row) {
				if (!cell[lowest_available_row])
					cell[lowest_available_row] = new tcell[max_cols];
				lowest_available_row++;
				}
			}
		if (col >= lowest_available_col)
			lowest_available_col = col+1;
		if (!cell[row])
			cell[row] = new tcell[max_cols];
		cell[row][col].setval(val);
		return 0;
		};
	template <class T>
	int set(const int row, const int col, const T& val) {
		ostringstream os;
		os << val;
		return set(row, col,os.str());
		}
	int set(const string& row, const string& col, const string& val) {
		int r;	// Integer value of row
		if (!findrowlabel(row, r)) {
		// Not already in array.
			if (lowest_available_row == max_rows)
				return -1;
			// Otherwise, use r = lowest_available_row and
			// move lowest_available_row up
			r = lowest_available_row++;
			rlabel[r].setval(row);
			if (!cell[r])
				cell[r] = new tcell[max_cols];
			}
		int c;	// Integer value of column
		if (findcollabel(col, c)) {
			cell[r][c].setval(val);
			return 0;
			}
		// Not already in array.
		if (lowest_available_col == max_cols)
			return -1;
		c = lowest_available_col++;
		clabel[c].setval(col);
		cell[r][c].setval(val);
		return 0;
		};
	template <class T>
	int set(const string& row, const string& col, const T& val) {
		ostringstream os;
		os << val;
		return set(row, col,os.str());
		}
	int setrowlabel(const int row, const string& val) {
		if ((row < 0)||(row >= max_rows))
			return -1;
		if (row >= lowest_available_row) {
			while (lowest_available_row <= row) {
				if (!cell[lowest_available_row])
					cell[lowest_available_row] = new tcell[max_cols];
				lowest_available_row++;
				}
			}
		rlabel[row].setval(val);
		return 0;
		};
	int setcollabel(const int col, const string& val) {
		if ((col < 0)||(col >= max_cols))
			return -1;
		if (col >= lowest_available_col)
			lowest_available_col = col+1;
		clabel[col].setval(val);
		return 0;
		};
	void readwithoutlabels(istream& in, const char coldelim = '\t', const char rowdelim = '\n') {
		read(in, false, coldelim, rowdelim);
		};
	void readwithoutlabels(const string& instring, const char coldelim = '\t', const char rowdelim = '\n') {
		istringstream is(instring);
		readwithoutlabels(is, coldelim, rowdelim);
		};
	void readwithoutlabels(const char *p, const char coldelim = '\t', const char rowdelim = '\n') {
		string instring(p);
		istringstream is(instring);
		readwithoutlabels(is, coldelim, rowdelim);
		};
	void readwithlabels(istream& in, const char coldelim = '\t', const char rowdelim = '\n') {
		read(in, true, coldelim, rowdelim);
		};
	void readwithlabels(const string& instring, const char coldelim = '\t', const char rowdelim = '\n') {
		istringstream is(instring);
		readwithoutlabels(is, coldelim, rowdelim);
		};
	void readwithlabels(const char *p, const char coldelim = '\t', const char rowdelim = '\n') {
		string instring(p);
		istringstream is(instring);
		readwithoutlabels(is, coldelim, rowdelim);
		};

	int get(const int row, const int col, string& val) {
		if ((row < 0)||(col < 0)||(row >= max_rows)||(col >= max_cols)){
			val = "";
			return -1;
			}
		if (!cell[row][col].used()) {
			// Works for row, col greater than lowest_available too
			val = "";
			return 0;
			}
		val = cell[row][col].getval();
		return 1;
		};
	template <class T>
	int get(const int row, const int col, T& val) {
		string thestring;
		int retval = get(row, col, thestring);
		istringstream is(thestring);
		is >> val;
		return retval;
		}
	int get(const string& row, const string& col, string& val) {
		int r;	// Integer value of row
		for (r = 0; r < lowest_available_row; r++) {
			if (rlabel[r].getval() == row)
				break;
			}
		if (r == lowest_available_row) {
			val = "";
			return 0;
			}
		for (int c = 0; c < lowest_available_col; c++) {
			if (clabel[c].getval() == col) {
				val = cell[r][c].getval();
				return 1;
				}
			}
		val = "";
		return 0;
		};
	template <class T>
	int get(const string& row, const string& col, T& val) {
		string thestring;
		int retval = get(row, col, thestring);
		istringstream is(thestring);
		is >> val;
		return retval;
		}
	int getrowlabel(const int row, string& val) {
		if ((row < 0)||(row >= max_rows)) {
			val = "";
			return -1;
			}
		if (!rlabel[row].used()) {
			val = "";
			return 0;
			}
		val = rlabel[row].getval();
		return 1;
		};
	int getcollabel(const int col, string& val) {
		if ((col < 0)||(col >= max_cols)) {
			val = "";
			return -1;
			}
		if (!clabel[col].used()) {
			val = "";
			return 0;
			}
		val = clabel[col].getval();
		return 1;
		}
	int findafter(const string& val, int& row, int& col) {
		if ((row < 0)||(col < 0)||(row >= lowest_available_row)||
				(col >= lowest_available_col))
			return 0;
		for (int r = row; r < lowest_available_row; r++) {
			// First loop for start row starting at col
			for (int c = col; c < lowest_available_col; c++) {
				if (cell[r][c].used()) {
					if (cell[r][c].getval() == val) {
						row = r;
						col = c;
						return 1;
						}
					}
				}
			// Remaining loops start at column 0
			col = 0;
			}
		return 0;
		};
	template <class T>
	int findafter(const T& val, int& row, int& col) {
		ostringstream os;
		os << val;
		return findafter(os.str(), row, col);
		}
	int findbefore(const string& val, int& row, int& col) {
		if ((row < 0)||(col < 0)||(row >= lowest_available_row)||
				(col >= lowest_available_col))
			return 0;
		for (int r = row; r >= 0; r--) {
			// First loop for start row starting at col
			for (int c = col; c >= 0; c--) {
				if (cell[r][c].used()) {
					if (cell[r][c].getval() == val) {
						row = r;
						col = c;
						return 1;
						}
					}
				}
			// Remaining loops start at last column
			col = lowest_available_col-1;
			}
		return 0;
		};
	template <class T>
	int findbefore(const T& val, int& row, int& col) {
		ostringstream os;
		os << val;
		return findbefore(os.str(), row, col);
		}
	int find(const string& val, int& row, int& col) {
		row = 0;
		col = 0;
		return findafter(val, row, col);
		}
	template <class T>
	int find(const T& val, int& row, int& col) {
		ostringstream os;
		os << val;
		return find(os.str(), row, col);
		}
	int findrowlabel(const string& val, int& row) {
		for (int r = 0; r < lowest_available_row; r++) {
			if (rlabel[r].used()) {
				if (rlabel[r].getval() == val) {
					row = r;
					return 1;
					}
				}
			}
		return 0;
		};
	int findcollabel(const string& val, int& col) {
		for (int c = 0; c < lowest_available_col; c++) {
			if (clabel[c].used()) {
				if (clabel[c].getval() == val) {
					col = c;
					return 1;
					}
				}
			}
		return 0;
		};

	int writewithlabels(ostream& out, const char coldelim = '\t', 
				const char rowdelim = '\n', 
				const bool includelastrowdelim = 1) {
		return write(out, true, coldelim, rowdelim, includelastrowdelim);
		};
	int writewithlabels(string& ostring, const char coldelim = '\t', 
				const char rowdelim = '\n', 
				const bool includelastrowdelim = 1) {
		ostringstream os;
		int retval = writewithlabels(os, coldelim, rowdelim,includelastrowdelim);
		ostring = os.str();
		return retval;
		}
	int writewithoutlabels(ostream& out, const char coldelim = '\t', 
				const char rowdelim = '\n', 
				const bool includelastrowdelim = 1) {
		return write(out, false, coldelim, rowdelim, includelastrowdelim);
		};
	int writewithoutlabels(string& ostring, const char coldelim = '\t', 
				const char rowdelim = '\n', 
				const bool includelastrowdelim = 1) {
		ostringstream os;
		int retval = writewithoutlabels(os, coldelim, rowdelim,includelastrowdelim);
		ostring = os.str();
		return retval;
		}
	void print() {
		cout << "\t";	// Top left corner: No label
		int i;
		for (i = 0; i < lowest_available_col; i++)
			cout << clabel[i].getval().substr(0,6) << "\t";
		cout << endl;
		for (i = 0; i < lowest_available_row; i++) {
			cout << rlabel[i].getval().substr(0,6) << "\t";
			for (int j = 0; j < lowest_available_col; j++)
				cout << cell[i][j].getval().substr(0,6) << "\t";
			cout << endl;
			}
		};
	};

// Test program
int main(int argc, char *argv[]) {
	if (argc < 2) {
		cerr << "Usage: stable files_containing_Infinity\n";
		return -1;
		}
	stable intab;
	stable outtab;
	stable parsetab;
	for (int a = 1; a < argc; a++) {
		string prefix;
		parsetab.readwithoutlabels(argv[a], '.', '/');
		parsetab.get(parsetab.nrows()-1,0,prefix); // Get string between last '/' and first following '.'
		ifstream i(argv[a]);
	 	if (i == 0) {
			cerr << "can't open " << argv[a] << endl;
	 		return -1;
	 		}
		intab.readwithoutlabels(i, ' ');
		i.close();
		int row, col;
		if (intab.find("Infinity",row, col)) {
			string value;
			intab.get(row,col-1,value);
			string suffix;
			intab.get(row-1,0,suffix);
			outtab.set(prefix,suffix,value);
			}
		}
	int endcol = outtab.ncols();
	int btpccol;
	int bestcol;
	outtab.findcollabel("\"btpc5a",btpccol);
	double btpcval, bestval, currval;
	string bestname;
	for (int r = 0; r < outtab.nrows(); r++) {
		bestval = 64;	// Ridiculously high
		for (int c = 0; c < outtab.ncols(); c++) {
			if (c == btpccol)
				outtab.get(r,c,btpcval);
			else {
				outtab.get(r,c,currval);
				if (currval < bestval) {
					bestval = currval;
					bestcol = c;
					}
				}
			}
		outtab.getcollabel(bestcol, bestname);
		ostringstream os;
		if (bestval < btpcval) {
			bestval = (btpcval-bestval)*100.0/bestval;
			os << bestname << " beats BTPC by " << bestval << " percent\n";
			}
		else {
			bestval = (bestval-btpcval)*100.0/btpcval;
			os << "BTPC beats " << bestname << " by " << bestval << " percent\n";
			}
		outtab.set(r,endcol,os.str());
		}
	outtab.setcollabel(endcol,"Result");
	outtab.print();
	ofstream o("losslesstable");
	outtab.writewithlabels(o);
	o.close();
	cout << "Reparse of last file:\n";
	string lastfile;
	parsetab.writewithoutlabels(lastfile,'.','/',0);
	cout << lastfile << endl;
	}