graph.hpp

#pragma once
#ifndef __GRAPH_H__
#define __GRAPH_H__

#include <exception>
#include <vector>
#include "Queue.h"
using std::vector;

//Use int instead of size_t so it can be used as a 2d dir vector
struct Vertex
{
	int x;
	int y;
	Vertex() = default;
	Vertex(int x, int y)
	{
		this->x = x;
		this->y = y;
	}
};
typedef vector<Vertex> vv;
//Using the vertex as a 2d vector array used later to write shorter code
Vertex directions[] = { {1,0}, {-1,0}, {0,1}, {0,-1} };

template<typename T>
class Graph
{
public:
	Graph();
	~Graph();
	Graph(const Graph&);
	void operator=(const Graph&) = delete;

	/*
	 * Motivation: Override operator[][] and use it ie graph[2][3]
	 * Idea: Override operator[] to return an object on which operator[] could be used again
	 * to get a result. 
	 * Realization: Use the design pattern Proxy.
	 * Define it inside the class so no further use of template<> is needed
	 */
	class Proxy
	{
		Graph* gr;
		size_t row;
	public:
		Proxy(Graph* gr, size_t i) : gr(gr), row(i)
		{}

		T& operator[](size_t col)
		{
			return (*gr).data[row][col];
		}
	};

public:
	//cannot define it out of the class because Proxy is declared here
	Proxy operator[](size_t idx)
	{
		return Proxy(this, idx);
	}
	void initialize();
	void free();
	size_t get_width() const;
	size_t get_height() const;
	//Implements BFS to get all reachable vertices from a given vertex
	void get_reachable(const Vertex&, vv&);
	//TODO (Ivan): Ask someone smarter for the functions accessing rights!!!
	void fill(T, size_t, size_t);
	void all_paths_between(const Vertex&, const Vertex&);
private:
	inline bool inBound(int x, int y);
	void backtrack(Graph, const Vertex&, const Vertex&, vv path);
	void free(size_t);
private:
	T** data;
	size_t size_x, size_y;
};

template<typename T>
inline bool Graph<T>::inBound(int x, int y)
{
	return !(x < 0 || x >= size_x || y < 0 || y >= size_y);
}

template<typename T>
Graph<T>::Graph(const Graph& other)
{
	this->size_x = other.size_x;
	this->size_y = other.size_y;
	this->data = new T*[size_x];
	if (!data)
	{
		//TODO (Ivan): Handle better this situation
		throw "Bad alloc in the cpy ctor!";
	}

	for (size_t i = 0; i < size_x; i++)
	{
		data[i] = new T[size_y];
		if (!data[i])
		{
			this->free(i);
			throw "Bad alloc in the cpy ctor!";
		}
	}

	for (size_t i = 0; i < size_x; i++)
	{
		for (size_t j = 0; j < size_y; j++)
		{
			this->data[i][j] = other.data[i][j];
		}
	}
}

template<typename T>
Graph<T>::Graph()
{
	data = nullptr;
	size_x = 0;
	size_y = 0;
}

template<typename T>
void Graph<T>::initialize()
{
	std::cin >> size_x >> size_y;

	data = new T*[size_x];
	if (!data)
	{
		throw std::bad_alloc();
	}

	for (size_t i = 0; i < size_x; i++)
	{
		data[i] = new T[size_y];
		if (!data[i])
			free(i);
	}

	for (size_t x = 0; x < size_x; x++)
	{
		for (size_t y = 0; y < size_y; y++)
		{
			std::cin >> data[x][y];
		}
	}
}

template<typename T>
void Graph<T>::free(size_t up_to)
{
	if (data)
	{
		for (size_t i = 0; i < up_to; i++)
			delete[] data[i];
	}
	delete[] data;
}

template<typename T>
void Graph<T>::free()
{
	if (data)
	{
		for (size_t i = 0; i < size_x; i++)
			delete[] data[i];

		delete[] data;
	}
}

template<typename T>
size_t Graph<T>::get_height() const
{
	return this->size_x;
}

template<typename T>
size_t Graph<T>::get_width() const
{
	return this->size_y;
}

template<typename T>
Graph<T>::~Graph()
{
	this->free();
}


/*
 * @param v - the node from which we start the traverse
 * @param reachable - vector of vertices in which we push the reachable vertices
 * Algorithm - Implementing the Breadth-First search algorithm 
 * using self-written circular queue 
 */
template<typename T>
void Graph<T>::get_reachable(const Vertex& v, vv& reachable)
{
	//Add function which checks if vertex is in bound
	Graph<bool> visited;
	visited.fill(false, this->get_height(), this->get_width());
	Queue<Vertex> q;
	visited[v.x][v.y] = true;
	q.enqueue(v);

	Vertex tmp;
	int tmp_y, tmp_x;
	while (!q.empty())
	{
		tmp = q.front();
		q.dequeue();

		for (auto& a : directions)
		{
			tmp_x = tmp.x + a.x;
			tmp_y = tmp.y + a.y;
			if (tmp_x < 0 || tmp_x >= this->get_width()
				|| tmp_y < 0 || tmp_y >= this->get_height())
				; //do nothing if out of bound

			else if(data[tmp_x][tmp_y] == '.' && visited[tmp_x][tmp_y] == false)
			{
				visited[tmp_x][tmp_y] = true;
				reachable.push_back(Vertex(tmp_x, tmp_y));
				q.enqueue(Vertex(tmp_x, tmp_y));
			}
		}
	}
}
/*
 * @param start - the starting node
 * @param end - the ending node
 * For practical purposes we suppose that we cannot go through a vertex
 * more than one time otherwise we could end with an infinite loop (a bad thing)
 */
template<typename T>
void Graph<T>::all_paths_between(const Vertex& start, const Vertex& end)
{
	Graph<char> visited;
	visited.fill('0', this->get_height(), this->get_width());

	visited[start.x][start.y] = true;
	int tmp_x, tmp_y;
	for (auto& a : directions)
	{
		vv path;
		path.push_back(start);
		tmp_x = start.x + a.x;
		tmp_y = start.y + a.y;
		path.emplace_back(Vertex(tmp_x, tmp_y));
		backtrack(visited, Vertex(tmp_x, tmp_y), end, path);
	}
}

template<typename T>
void Graph<T>::backtrack(Graph visited, const Vertex& curr, const Vertex& end, vv path)
{
	if (curr.x == end.x && curr.y == end.y)
	{
		for (size_t i = 0; i < path.size(); i++)
			std::cout << "(" << path[i].x << "," << path[i].y << ")";

		std::cout << "\n";
	}
	else
	{
		int tmp_x, tmp_y;
		for (auto& a : directions)
		{
			tmp_x = curr.x + a.x;
			tmp_y = curr.y + a.y;
			if (inBound(tmp_x, tmp_y))
			{
				if (visited[tmp_x][tmp_y] == '0' && data[tmp_x][tmp_y] == '.')
				{
					visited[tmp_x][tmp_y] = '1';
					path.emplace_back(Vertex(tmp_x, tmp_y));
					backtrack(visited, Vertex(tmp_x, tmp_y), end, path);
				}
			}
		}
	}
}

template<typename T>
void Graph<T>::fill(T val, size_t x, size_t y)
{
	this->free();
	this->size_x = x;
	this->size_y = y;

	data = new T*[size_x];
	for (size_t i = 0; i < size_x; i++)
	{
		data[i] = new T[size_y];
		for (size_t j = 0; j < size_y; j++)
			data[i][j] = val;
	}
}
#endif