/*	Description: Header for classes etc. used in implementation of Prim's MST algorithm

	Revision history: 8/1/99/LY - initial version

					  10/1/99/LY - design experiments, settled on minor modifications	

					  12/1/99/LY - adjustments of namespaces

					  13/3/99/LY - final debugging

					  28/3/99/LY - improved complexity of heap operations

*/



#include <vector>

#include <functional>	

#include <iterator>	



using namespace std;



namespace MSTElem

{	//Record struct used to hold vertex information during execution of Prim()

	struct MSTElement

	{		//includes overloaded operators to make it a well-formed struct

		bool operator<(MSTElem::MSTElement& m) {return (key < m.key);}	

		bool operator<(const MSTElem::MSTElement& m) const {return (key < m.key);}

		bool operator==(MSTElem::MSTElement& m) {return (key == m.key);}

		bool operator==(const MSTElem::MSTElement& m) const {return (key == m.key);}

		unsigned int parent, key;

		unsigned char member;

		MSTElement**	heap_ptr;

	};

}



namespace EdgeType

{

	typedef	vector<unsigned int>			edge_type; 

	enum {u=0,v,weight};	//aliases for indices used to access edge_type

}



using EdgeType::edge_type;

using MSTElem::MSTElement;



typedef vector<edge_type >				adj_list;	

typedef vector<adj_list >				graph_container;

typedef vector<MSTElement >			MST_container;

typedef vector<MSTElement* >			queue_container;



/* Function object used in the generation of adjacency list data */

template <class T = edge_type,class G = graph_container> 

class AdjacencyListGenerator

{

public:

	AdjacencyListGenerator(unsigned int v_arg,unsigned int total_v_arg);

	void operator() (T& edge_type);

	static void Initialise(unsigned int v_arg,unsigned int max_weight_arg, G* graph_arg);

private:

	void Generator(T& x);

	unsigned int	v,v_index;

	static unsigned int max_weight,total_v;

	static G*	graph_ptr;

	static vector<unsigned int>	rnd_pool;

};



/* Function object used in the generation of directed graph input data for the MST algorithm */

	// make it an adaptable function object, just for the sake of completeness (adds no overhead) 

template <class T = adj_list,class G = graph_container>	

class GraphGenerator 

{													 

public:	

	GraphGenerator(unsigned int v_arg,unsigned int degree_arg,unsigned int max_weight_arg,G& graph_arg); 

	void operator() (T& adj_list);

private:

	unsigned int	v,max_degree; //private state variables

};



#include "graph.cpp"