Лабораторная работа 23 / Graph

// Copyright (C) 1991 - 1999 Rational Software Corporation

#if defined (_MSC_VER) && (_MSC_VER >= 1000)
#pragma once
#endif
#ifndef _INC_GRAPH_470A7E3D0232_INCLUDED
#define _INC_GRAPH_470A7E3D0232_INCLUDED

#include "stdafx.h"
#include "GraphStructureException.h"
#include "Iterator.h"

//##ModelId=470A7E3D0232
template<class T  >
class Graph 
{
private:
	//##ModelId=470A8A0701D4
	int** rel_matrix;

	//##ModelId=470A87F701B5
	int current_size;

	//##ModelId=470E2C7F000F
	int elems_num;

	//##ModelId=470A888C032C
	T* elems;

	//##ModelId=471B4FA8002E
	bool is_initialized;

	//##ModelId=470E2C7F002E
	int** init_matrix(int size) {

		if (size == 0) return NULL;

		int**matrix = NULL;

		matrix = new int*[size];
		for (int i = 0; i<size; i++) {
			matrix[i] = new int[size];
		}

		for(i=0;i<size;i++)
			for(int j =0;j<size;j++)
				matrix[i][j]=0;
		return matrix;
	}

	//##ModelId=470E2C7F007D
	T* init_vector(int size) {
		T*new_vector;
		if (size>0) {
			new_vector = new T[size];
			for (int i=0;i<size; i++) {
				new_vector[i]=NULL;
			}
		} else {
			new_vector = NULL;
		}
		return new_vector;
	}

	//##ModelId=470E2C7F00DA
	void expand(int new_size) {
		
		if(new_size <= current_size) return; // Expansion is not needed

		int**new_matrix = init_matrix(new_size);
		T*new_vec = init_vector(new_size);

		for (int i = 0; i < current_size; i++) {
			for (int j=0; j<current_size; j++) {
				new_matrix[i][j]=rel_matrix[i][j];
			}
		}

		for (i = 0; i < current_size; i++ ) {
			new_vec[i] = elems[i];
		}

		delete[] elems;
		for (i = 0; i < current_size; i++) {
			delete[] rel_matrix[i];
		}
		delete[] rel_matrix;

		elems = new_vec;
		rel_matrix = new_matrix;
		current_size = new_size;
	}

	void collapse() {
		
		int real_size = 0;
		
		for (int i = 0; i<current_size; i++) {
			if (elems[i] != NULL) real_size = i+1;
		}

		int new_size = real_size;

		if (real_size == current_size) return;

		int**new_matrix = init_matrix(new_size);
		T*new_vec = init_vector(new_size);

		for (i = 0; i < real_size; i++) {
			for (int j=0; j<real_size; j++) {
				new_matrix[i][j]=rel_matrix[i][j];
			}
		}

		for (i = 0; i < real_size; i++ ) {
			new_vec[i] = elems[i];
		}

		delete[] elems;

		for (i = 0; i < current_size; i++) {
			delete[] rel_matrix[i];
		}
		delete[] rel_matrix;

		elems = new_vec;
		rel_matrix = new_matrix;
		current_size = new_size;


	}

public:

	int getCurrentSize() const
	{
		return elems_num;
	}

	int getRealMemSize() {
		int real_size = 0;
		for (int i=0;i<current_size;i++) {
			if(elems[i]!=NULL) real_size = i+1;
		}
		return real_size;
	}

	int getNumberOfElements() const {
		return elems_num;  
	}

	int getNodeByVal(T& elem) {

		int position = -1;

		for (int i = 0; i < current_size; i++ ) {
			if (elems[i] == elem) { 
				position = i;	
			}
		}

		if (position == -1) throw GraphStructureException("node doesn't exist");

		return (position+1);
	}

	T getValByNode(int node) {
		if (node > current_size ) throw GraphStructureException("node doesn't exist"); // throw exception

		if (this->elems[node-1]==NULL) {
			throw GraphStructureException("node doesn't exist");
		}		
		
		return elems[node-1];
		
	}

	T* getNodesFrom(int node, int* size) {
		T* array = NULL;
		
		int realsize=0;
		for (int i=0; i < current_size; i++) {
			if ( rel_matrix[i][node-1] == 1 ) {realsize++;}
		}

		if(realsize!=0) { // there are some elements
			array = new T[realsize];
			int j=0;

			for (i=0;i<current_size; i++) {
				if(rel_matrix[i][node-1] == 1) {
					array[j++] = getValByNode(i+1);
				}
			}
		}
		*size = realsize;
		return array;
	}

	//##ModelId=470A81D2009C
	Graph()
	{
		// ToDo: Add your specialized code here and/or call the base class
		elems_num = 0;
		current_size = 0;
		is_initialized = false;
		rel_matrix = init_matrix(current_size);
		elems = init_vector(current_size);

		pInnerIterator = new GraphIterator(this);
	}


	//##ModelId=470A81D2031D
	virtual ~Graph()
	{
		// ToDo: Add your specialized code here and/or call the base class
		for (int i = 0; i < current_size; i++) {
			delete rel_matrix[i];
		}
		delete rel_matrix;
		delete elems;
	}


	//##ModelId=470A821C0242
	void add(T & elem, int num, int num_attach)
	{
		if (num <= 0) throw GraphStructureException("wrong node value");

		if (!is_initialized) throw GraphStructureException("graph not initialized"); // throw exception.

		if (num_attach > current_size ) throw GraphStructureException("node to attach doesn't exist"); // throw exception

		if (num == num_attach) throw GraphStructureException("can not attach node to itself");

		if (this->elems[num_attach-1]!=NULL ) {

			expand(num);

			if (this->elems[num-1]!=NULL) throw GraphStructureException("node already exists"); //throw exception. Already exist!

			(this->elems[num-1])=elem;
			rel_matrix[num_attach-1][num-1] = 1;

		} else {
			throw GraphStructureException("node to attach doesn't exist");
		}

		elems_num++;

	}

	void add(T& elem, int num) {

		if (num <= 0) throw GraphStructureException("wrong node value");

		if (!is_initialized) {
			init(elem,num); 
			return; 
		}

		expand(num);

		if (this->elems[num-1]!=NULL) throw GraphStructureException("node already exists"); //throw exception. Already exist!

		(this->elems[num-1])=elem;
		
		elems_num++;

	}

	void add(T& elem) {
		int num = current_size+1;
		add(elem,num);
	}

	//##ModelId=4720ED05036B
	void link(int node, int to) {

		if (!is_initialized) throw GraphStructureException("graph not initialized"); // throw exception.

		if (node > current_size ) throw GraphStructureException("node doesn't exist"); // throw exception

		if (node == to) throw GraphStructureException("can not attach node to itself");

		if (this->elems[to-1]!=NULL && this->elems[node-1]!=NULL) {

			if (rel_matrix[to-1][node-1] == 1) 
				throw GraphStructureException("link already exist");
			else rel_matrix[to-1][node-1] = 1;

		} else {
			throw GraphStructureException("node to attach doesn't exist");
		}		
	}

	//##ModelId=4720ED050399
	void unlink(int from, int to) {

		if (!is_initialized) throw GraphStructureException("graph not initialized"); // throw exception.

		if (from > current_size || to > current_size) throw GraphStructureException("node doesn't exist"); // throw exception

		if (rel_matrix[from-1][to-1] == 1) {

			rel_matrix[from-1][to-1] = 0;

		} else {
			throw GraphStructureException("link doesn't exist");
		}		
	}

	//##ModelId=4720ED0503C8
	void removeByNode(int node) {
		if (node > current_size ) throw GraphStructureException("node doesn't exist"); // throw exception

		if (this->elems[node-1]!=NULL) {
			
			for (int i = 0; i < current_size; i++ ) {
				rel_matrix[node-1][i] = 0; // remove all ways from this node.
			}

			for (i = 0; i < current_size; i++) {
				rel_matrix[i][node-1] = 0; // remove all ways to this node.
			}

			elems[node-1] = NULL;
			elems_num--;

			collapse();

		} else {
			throw GraphStructureException("node doesn't exist");
		}
	}

	void removeByVal(T elem) {
		
		int position = -1;

		for (int i = 0; i < current_size; i++ ) {
			if (elems[i] == elem) { 
				position = i; break;	
			}
		}

		if (position == -1) throw GraphStructureException("node doesn't exist");

		for (i = 0; i < current_size; i++ ) {
			rel_matrix[position][i] = 0; // remove all ways from this node.
		}

		for (i = 0; i < current_size; i++) {
			rel_matrix[i][position] = 0; // remove all ways to this node.
		}

		elems[position] = NULL;
		elems_num--;

		collapse();
	}

	void setRelMatrix(int** matrix) {
		rel_matrix = matrix;
	}

	int** getRelMatrix() {
		return rel_matrix;
	}

	//##ModelId=471BAF6A00CB
	Iterator<T>* iterator() {
		Iterator<T>*i = new Graph::GraphIterator(this); 
		return i;
	}

	//##ModelId=471B4FA8006D
	void init(T& elem, int num) {
		
		if (is_initialized ) throw GraphStructureException("already initialized");

		expand(num);
		elems[num-1] = elem;
		is_initialized = true;
		elems_num = 1;
	}

	public:
	//##ModelId=471B587701A5
	class GraphIterator :virtual public Iterator<T>
		{
		private: 
		//##ModelId=471BAF6A0138
			int position_index;
		//##ModelId=471BAF6A0187
			Graph<T>* graph;
		public:
		
		//##ModelId=471BAF6A0198
			GraphIterator(Graph<T>* g) {
				position_index = 0;
				graph = g;
			}
			
		//##ModelId=471BB2CA034B
			virtual ~GraphIterator() {
				graph = NULL;
			}
	
		//##ModelId=471BAF6A01A6
			T next() {
				
				position_index+=1;
				for (int i = position_index; i < graph->current_size; i++ ) {
					if (graph->elems[i]!=NULL) {
						position_index=i; 
						return graph->elems[i];
					}
				}

				return NULL;
				
			}
			 
		//##ModelId=471BAF6A01A7
			bool hasNext() {

				graph->current_size;
				for (int i = position_index+1; i < graph->current_size; i++ ) {
					if (graph->elems[i]!=NULL) return true;
				}
				return false;
			}
			
			bool hasPrevious() {
				for (int i = position_index-1; i >= 0; i-- ) {
					if (graph->elems[i]!=NULL) return true;
				}
				return false;
			}

			T previous() {

				position_index-=1;
				
				for (int i = position_index; i >= 0; i-- ) {
					if (graph->elems[i]!=NULL) {
						position_index=i; 
						return graph->elems[i];
					}
				}

				return NULL;
			}

			T first() {
				for (int i = 0; i < graph->current_size; i++) {
					if (graph->elems[i]!=NULL) {
						position_index=i; 
						return graph->elems[i];
					}
				}

				return NULL;
			}

			T last() {
				for (int i = graph->current_size-1; i>=0 ; i--) {
					if (graph->elems[i]!=NULL) {
						position_index=i; 
						return graph->elems[i];
					}
				}

				return NULL;
			}

			T current() {
				if (graph->elems[position_index] != NULL)
				return graph->elems[position_index];
				return NULL;
			}

			bool endNext() {
				if (position_index == graph->current_size) return true;
				return false;

			}

			bool endPrevious() {

				if (graph->current_size == 0) return true;

				int tmp = position_index;
				for (tmp;tmp>=0;tmp--) {
					if(graph->elems[tmp] != NULL) {
						return false;
					}
				}

				return true;
			}
	};

	friend class Graph<T>::GraphIterator;
	
	public:
	Graph::GraphIterator* pInnerIterator;
};

#endif /* _INC_GRAPH_470A7E3D0232_INCLUDED */