/*
 * Copyright (c) 2006
 *  Morten Slot Kristensen, Århus, Denmark.  All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

#include <iomanip>
#include <sstream>
#include <math.h>
#include <vector>
#include <fcntl.h>
#include <stdio.h>
#include "matrix.hpp"
#include "operations.hpp"
using namespace std;

/*
 * Multiplicates two matrices and returns the product
 */
matrix multiplicate(matrix *first, matrix *second)
{
	matrix result(first->get_rows(), second->get_columns());
	float v;

	for(int i=0; i<result.get_rows(); i++)
	{
		matrix row = get_row(i, first);
		for(int j=0; j<result.get_columns(); j++)
		{
			matrix column = get_column(j, second);
			v = 0.0;
		
			for(int h=0; h<row.get_columns(); h++)
			{
				v += row.get_value(0, h) * column.get_value(h, 0);
			}

			result.set_value(i, j, v);
		}
	}

	return result;
}

/*
 * Multiplicates a matrix with a number and returns the product
 */
matrix multiplicate(matrix *m, float number)
{
	matrix result(m->get_rows(), m->get_columns());

	for(int i=0; i<result.get_rows(); i++)
	{
		for(int j=0; j<result.get_columns(); j++)
		{
			result.set_value(i, j, m->get_value(i, j)*number);
		}
	}

	return result;
}

/*
 * Sums two matrices and returns the result
 */
matrix add(matrix *first, matrix *second)
{
	matrix result(first->get_rows(), first->get_columns());

	for(int i=0; i<first->get_rows(); i++)
	{
		for(int j=0; j<first->get_columns(); j++)
		{
			result.set_value(i, j, first->get_value(i, j) +
					second->get_value(i, j));
		}
	}

	return result;
}

/*
 * Substracts two matrices and returns the result
 */
matrix substract(matrix *first, matrix *second)
{
	matrix result(first->get_rows(), first->get_columns());

	for(int i=0; i<first->get_rows(); i++)
	{
		for(int j=0; j<first->get_columns(); j++)
		{
			result.set_value(i, j, first->get_value(i, j) -
					second->get_value(i, j));
		}
	}

	return result;
}

/*
 * Inverts a given matrix and returns the result
 */
matrix invert(matrix *m)
{
	matrix result(m->get_rows(), m->get_columns());

	for(int i=0; i<m->get_rows(); i++)
	{
		for(int j=0; j<m->get_columns(); j++)
		{
			float v = m->get_value(i, j);

			if(v == 0)
				result.set_value(i, j, 0);
			else
				result.set_value(i, j, 1/v);
		}
	}

	return result;
}

/*
 * Transposes a given matrix and returns the result
 */
matrix transpose(matrix *m)
{
	matrix result(m->get_columns(), m->get_rows());

	for(int i=0; i<result.get_rows(); i++)
	{
		matrix column = get_column(i, m);
		for(int j=0; j<column.get_rows(); j++)
		{
			result.set_value(i, j, column.get_value(j, 0));
		}
	}

	return result;
}

/*
 * Retrieves the determinant of a given matrix
 */
float determinant(matrix *m)
{
	float det = 0.0;
	int done = 0, lsize = m->get_rows(), swt = 1;
	vector<matrix> list;

	// put the first one in at once
	list.push_back(*m);

	// run while m.row>2,col>2
	while(m->get_rows() > 2 && m->get_columns() > 2)
	{
		vector<matrix>::iterator it;
		vector<matrix>::iterator end = list.end();

		// go through the items and compute new matrices
		// breaking the first into smaller matrices untill
		// there is only 2x2's left
		for(it = list.begin(); it != end; it++)
		{
			if(it->get_rows() > 2 && it->get_columns() > 2)
			{
				matrix tmp = *it;
				for(int i=0; i<tmp.get_columns(); i++)
				{
					matrix m2 = get_matrix_ex_r_c(0, i, &tmp);
					m2.set_temp(tmp.get_value(0, i)*tmp.get_temp());
					lsize = m2.get_rows();
					list.push_back(m2);
				}
			}
		}
		
		// delete the matrices from the previos run-through
		// so only the new-generated ones remain
		for(it = list.begin(); it != list.end(); it++)
		{
			if(it->get_rows() > lsize)
				list.erase(it);
		}

		// when there's only 2x2's left then break
		done = 1;
		for(it = list.begin(); it != list.end(); it++)
		{
			if(it->get_rows() > 2 && it->get_columns() > 2)
			{
				done = 0;
			}
		}

		if(done)
			break;
	}

	// calculate the determinant
	// NOTE: add the first result and the next then switch between adding and substracting
	int add = 2;
	for(vector<matrix>::iterator it = list.begin(); it != list.end(); it++)
	{
		if(add == 1)
		{
			det -= it->get_temp()*((it->get_value(0, 0)*it->get_value(1, 1)) - (it->get_value(1, 0)*it->get_value(0, 1)));
			add = 0;
		}
		else if(add == 2)
		{
			det = it->get_temp()*((it->get_value(0, 0)*it->get_value(1, 1)) - (it->get_value(1, 0)*it->get_value(0, 1)));
			add = 1;
		}
		else if(add == 0)
		{
			det += it->get_temp()*((it->get_value(0, 0)*it->get_value(1, 1)) - (it->get_value(1, 0)*it->get_value(0, 1)));
			add = 1;
		}
	}

	return det;
}

/*
 * Retrieves a given row from a matrix and returns it as matrix
 */
matrix get_row(int row, matrix *m)
{
	matrix result(1, m->get_columns());

	for(int i=0; i<m->get_columns(); i++)
	{
		result.set_value(0, i, m->get_value(row, i));
	}

	return result;
}

/*
 * Retrieves a given column from a matrix and returns it as matrix
 */
matrix get_column(int column, matrix *m)
{
	matrix result(m->get_rows(), 1);

	for(int i=0; i<m->get_rows(); i++)
	{
		result.set_value(i, 0, m->get_value(i, column));
	}

	return result;
}

/*
 * Retrieves the matrix except for the row and column
 */
matrix get_matrix_ex_r_c(int row, int column, matrix *mat)
{
	matrix result(mat->get_rows()-1, mat->get_columns()-1);

	int x = 0, y = 0, a_col = 0;
	for(int i=0; i<mat->get_rows(); i++)
	{
		for(int j=0; j<mat->get_columns(); j++)
		{
			if(i != row && j != column)
			{
				result.set_value(y, x, mat->get_value(i, j));
				x++;
				a_col = 1;
			}
		}

		if(a_col)
		{
			y++;
			a_col = 0;
		}

		x = 0;
	}
	
	return result;
}

/*
 * Determines if two matrices are equal
 */
int is_identical(matrix *first, matrix *second)
{
	if(first->get_rows() == second->get_rows() && first->get_columns() == second->get_columns())
	{
		int equal = 1;

		for(int i=0; i<first->get_rows(); i++)
		{
			for(int j=0; j<first->get_columns(); j++)
			{
				if(first->get_value(i, j) != second->get_value(i, j))
					equal = 0;
			}
		}

		return equal;
	}
	else
		return 0;
}

/*
 * Generates a random number from 'min' to 'max' from '/dev/random'
 */
int random_number(int min, int max)
{
	static int dev_fd = open("/dev/random", O_RDONLY);
	int bytes_to_read;
	unsigned rnd_val;
	char* next_byte = (char*)&rnd_val;
	
	bytes_to_read = sizeof(rnd_val);

	do
	{
		int bytes_read;
		bytes_read = read(dev_fd, next_byte, bytes_to_read);
		bytes_to_read -= bytes_read;
		next_byte += bytes_read;
	} while(bytes_to_read > 0);

	return min+(rnd_val%(max-min+1));
}

/*
 * Generates a text representation of a matrix
 */
string gen_text_matrix(matrix *m)
{
	string result = "", 
		   biggest = "";
	vector<TabItem> tab_info;

	// go through every column and get the biggest value
	for(int i=0; i<m->get_columns(); i++)
	{
		matrix row = get_column(i, m);
		biggest = "";

		for(int h=0; h<row.get_rows(); h++)
		{
			float tmp = row.get_value(h, 0);
			if(to_string(tmp).length() > biggest.length())
				biggest = to_string(tmp);
		}

		float tabs = ceil((float)biggest.length()/3.0);

		TabItem tab_item;
		tab_item.num_tabs = tabs;
		tab_item.val_one_tab = atof(biggest.c_str());
		tab_info.push_back(tab_item);
	}

	// go through every TabItem at make the highest
	// number of tabs the same for every column
	// but not the ones that equals TabItem's 
	// 'val_one_tab' and the ones which calced
	// tab is equal to 'val_one_tab'

	for(int i=0; i<m->get_rows(); i++)
	{
		for(int j=0; j<m->get_columns(); j++)
		{
			int col=0;
			TabItem tab_item;
			for(vector<TabItem>::iterator it = tab_info.begin();
					it != tab_info.end(); it++)
			{
				if(col == j)
					tab_item = *it;

				col++;
			}

			float val = m->get_value(i, j);
			result += to_string(val);
			float tab = ceil((float)to_string(val).length()/3.0);
			
			// add the number of tabs described in 
			// (tab_item.num_tabs - the ones for the singular + 1)
			for(int h=0; h<(tab_item.num_tabs-tab+1); h++)
			  result += "\t";
		}
		
		result += "\n";
	}

	return result;
}

/*
 * Generates a matrix from an imported
 * text representation
 */
matrix gen_matrix_from_text(int rows, int columns, const string &mdata)
{
	/*
	  Format of text matrix:

	  	 rows\n
		 columns\n
		 x,x,x,x,x,x,x,x,... (as many items as rows*columns)
		 (separated bt commas!)
	 */

	matrix result(rows, columns);

	vector<string> tokens;
	string del = ",";
	tokenize_string(mdata, tokens, del);

	int pos = 0;
	for(vector<string>::iterator it = tokens.begin();
			it !=  tokens.end(); it++)
	{
		float value = atof(it->c_str());
		result.set_value_t(pos, value);

		pos++;
	}

	return result;
}

/*
 * Tokenizes a string into a vector with the specified delimiter
 */
void tokenize_string(const string &str, vector<string> &tokens, const string &delimiters)
{
    // Skip delimiters at beginning.
    string::size_type lastPos = str.find_first_not_of(delimiters, 0);

    // Find first "non-delimiter".
    string::size_type pos = str.find_first_of(delimiters, lastPos);
    
	while (string::npos != pos || string::npos != lastPos)
    {
    	tokens.push_back(str.substr(lastPos, pos - lastPos));
    	
		// Skip delimiters.  Note the "not_of"
    	lastPos = str.find_first_not_of(delimiters, pos);
    	
		// Find next "non-delimiter"
    	pos = str.find_first_of(delimiters, lastPos);
    }
}

/*
 * Generates the text to write to a file
 * when exporting the matrix
 */
string export_matrix(matrix *m)
{
	string result = to_string(m->get_rows())+"\n"
		+to_string(m->get_columns())+"\n";

	for(int i=0; i<m->get_rows(); i++)
	{
		for(int j=0; j<m->get_columns(); j++)
		{
			result += to_string(m->get_value(i, j)) + ",";
		}
	}

	// skip the last comma
	return result.substr(0, result.length()-1);
}