#include "Matrix.h"



void Matrix::rehash() //Theta(capacity)
{
	MatrixElement* newHashTable = new MatrixElement[capacity * 2];
	capacity *= 2;
	for (int i = 0; i < capacity/2; i++)
	{
		if (hashTable[i].line != -1)
		{
			int hk = hash(hashTable[i].line, hashTable[i].column);
			int x = 0;
			while (newHashTable[(hk + probing(x))%capacity].line != -1)
				x++;
			newHashTable[(hk + probing(x)) % capacity].line = hashTable[i].line;
			newHashTable[(hk + probing(x)) % capacity].column = hashTable[i].column;
			newHashTable[(hk + probing(x)) % capacity].value = hashTable[i].value;
		}
	}
	delete[] hashTable;
	hashTable = newHashTable;
}

Matrix::Matrix(int nrLines, int nrCols) //Theta(1)
{
	if (nrLines < 1 || nrCols < 1)
		throw std::exception();
	this->nrX = nrLines;
	this->nrY = nrCols;
	this->hashTable = new MatrixElement[8];
	this->size = 0;
	this->capacity = 8;
}

int Matrix::nrLines() const //Theta(1)
{
	return this->nrX;
}

int Matrix::nrColumns() const //Theta(1)
{
	return this->nrY;
}

TElem Matrix::element(int i, int j) const //Theta(1)
{
	if (i < 0 || j < 0 || i > nrX || j > nrY)

		throw std::exception();
	int hk = hash(i, j);
	int x = 0;
	while (hashTable[(hk + probing(x))%capacity].line != -1)
	{
		if (hashTable[(hk + probing(x)) % capacity].line == i && hashTable[(hk + probing(x)) % capacity].column == j)
			return hashTable[(hk + probing(x)) % capacity].value;
		x++;
	}
	return NULL_TELEM;
}


TElem Matrix::modify(int i, int j, TElem e)//Theta(1)
{
	if (i < 0 || j < 0 || i > nrX || j > nrY)
		throw std::exception();
	if (size == (int)(capacity*alpha))
		rehash();
	int hk = hash(i, j);
	int x = 0;

	while (hashTable[(hk + probing(x)) % capacity].line != -1)
	{
		if (hashTable[(hk + probing(x)) % capacity].line == i && hashTable[(hk + probing(x)) % capacity].column == j)
		{
			TElem val = hashTable[(hk + probing(x)) % capacity].value;
			hashTable[(hk + probing(x)) % capacity].value = e;
			if (e == NULL_TELEM && val != NULL_TELEM)
				size--;
			size++;
			return val;
		}
		x++;
	}
	hashTable[(hk + probing(x)) % capacity].line = i;
	hashTable[(hk + probing(x)) % capacity].column = j;
	hashTable[(hk + probing(x)) % capacity].value = e;
	size++;
	return NULL_TELEM;
}


int Matrix::hash(int i, int j) const //Theta(1)
{
	return i + j;

}

int Matrix::probing(int x) const //Theta(1)
{
	return x * (x + 1) / 2;
}

Matrix::~Matrix()
{
	delete[] hashTable;
}