/***************************************************************************
    FPGA Brook Source Code
    Copyright (C) by Frank Franjo Plavec 2006-2012

    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 1, or (at your option)
    any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program; if not, write to the Free Software
    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.

    The full text of the GNU General Public License in the file named
    LICENSE.cTool.
*****************************************************************************/

#ifndef __GRAPH_H__
#define __GRAPH_H__

#define BRCC_COLLECTOR "BRCC__BRCC_COLLECTOR"
#define BRCC_DISTRIBUTOR "BRCC__BRCC_DISTRIBUTOR"
#define BRCC_DOUBLE_DISTRIBUTOR "BRCC__BRCC_DOUBLE_DISTRIBUTOR"
#define BRCC_COLLECTOR_DISTRIBUTOR "BRCC__BRCC__COLLECTOR_DISTRIBUTOR"
#define BRCC_COLLECTOR_DOUBLE_DISTRIBUTOR "BRCC__BRCC__COLLECTOR_DOUBLE_DISTRIBUTOR"

#include <string>
#include <list>

extern void fatal (std::string msg);

enum ReduceNodeHandling {
	Normal = 0,			// No special handling
	Reduce_2d_1d,		// 2-D reduction got converted into pure 1-D reduction
	Reduce_2d_2Phase,	// 2-D reduction got converted into a 2-phase reduction (1-D first, then non-replicated 2-D)
	Reduce_2d_2Phase_Both_Replicated	// 2-D reduction got converted into a 2-phase reduction (1-D first, then replicated 2-D)
};

struct StreamStruct {
	std::string stream;
	std::string stream_var;
	bool stream_of_arrays;
	int array_size;
	int word_size;
	StreamStruct(): stream_of_arrays(false), word_size(4){};
};

class GraphEdge;

class GraphNode {
	friend class Graph;
public:
	std::string name;
	unsigned int replication_factor;	// This is actually a misnomer - this variable contains desired speedup
	int insize_dim0;
	int insize_dim1;
	int reducesize_dim0;
	int reducesize_dim1;
	int node_order;	// When node's destination in a reduction tree is a collector node, this number will contain 
					// a unique id (starting at 0) for this node, to distinguish it from other nodes that feed into the same
					// collector node. This is necessary so that we can connect nodes in the correct order to the ports
					// of the collector node
	int node_order_distributor; // When node is a destination of an edge from a double round-robin distributor
								// this number will contain a unique id (starting at 0) for this node,
								// to distinguish it from other nodes fed by the same double distributor
								// This is necessary so that we can connect nodes in the correct order to the ports
								// of the double distributor node
	std::list <struct StreamStruct> in_streams;
	std::list <struct StreamStruct> out_streams;
	std::list <GraphEdge> out_edges;

	ReduceNodeHandling reducenodehandling;	// This value determines how a 2-D reduction kernel should be handled

	// The following parameters only make sense for leaf nodes in a replicated reduction tree
	// They help us generate correct code for each replica of the reduction kernel
	bool is_leaf;	// True if the node is leaf in a reduction tree
	int elements_to_process_2; // for leaf node determines the number of elements to process when the counter is equal or higher than the threshold
	int my_index; // for leaf node contains an ordinal number that determines the position of the current leaf among the leafs in this particular tree
				  // The difference between this and what replication_factor contains is that this number is unique within the tree (but not among multiple trees)
	              // replication_factor is only unique within multiple trees
	int counter_threshold; // for leaf node determines counter threshold
	// End of parameters that only make sense for leaf nodes in a replicated reduction tree

	bool visited;				// Some algorithms may make use of this flag to mark nodes that have already been processed
	bool preceded_by_a_collector;	// This boolean will only be set for double distributor nodes preceded by a collector node
									// This is useful, so that we can generate collector double distributor, instead of collector
									// and double distributor separately (this would not be feasible, because C2H does not allow us to connect them)
	int elements_to_process_1;	// for leaf node determines the number of elements to process when the counter is lower than the threshold
								// for non-leaf node determines how many elements should be processed before the next reduction begins
								// i.e. how many elements of the input should be processed before one output is produced
	int total_elements_to_process; // for any tree node determines how many elements should be processed in total
	int replicated_leaves;	// This number will only be meaningfull for replicated reduction kernels
							// It will contain the number of replicas that are leaves of the tree implementing replication
							// This number will be stored in the node in the original dataflow graph
							// This information is useful so that we can connect all edges to the tree correctly
							// For kernels with multiple trees, this value will contain the number of leaves in EACH tree
							// This means that the total number of leaves is: trees*replicated_leaves

	int replicated_nodes;	// This number will only be meaningfull for replicated reduction kernels
							// It will contain the total number of nodes in the tree implementing replication
							// This number will be stored in the node in the original dataflow graph
							// This information is useful so that we can generate the correct number of copies of the code
							// For kernels with multiple trees, this value will contain the total number of nodes in all trees
	int trees;				// This number will only be meaningfull for replicated reduction kernels
							// It will contain the number of trees built to implement replication, when one tree is not enough
							// This number will be stored in the node in the original dataflow graph
							// This information is useful so that we can generate the correct number of copies of the code
	int nodes_in_phase_2;	// For 2D-2D reductions that have been replicated, this value will contain
							// the number of nodes in the second phase of reduction
	GraphNode* copy_ptr;	// This pointer will point to the node in the copy of the graph
							// In case of replicated nodes it will point to ONE other replica of the node
							// Other replicas will be linked as a single-linked list through this same pointer
	GraphNode* phase_2_ptr;	// For 2D-2D reductions that have been replicated, this pointer will point
							// to the first node in the second phase of reduction

	GraphNode (std::string name);
	GraphNode (std::string name, unsigned int replication_factor);
	bool isReduce() { return reduce; }
	void setReduce() { reduce = true;}
	int inEdges() { return this->in_edges.size(); }

private:
	// "in" edges will just point to appropriate "out" edges, to avoid duplication and inconsistency
	std::list <GraphEdge*> in_edges;
	bool reduce;
	int weight;				// Weight is used by the Huffman algorithm to build minimum reduction tree (see Graph::build_trees)
	GraphNode* root_reduction_replica;	// This pointer will only be used for replicated reduction kernels
										// It will point to the root of the tree implementing replicated reduction
	GraphEdge* findEdgeNoDestinationPtr (std::string name);
	void addInEdge (GraphEdge *edge);
	GraphEdge & addOutEdge (GraphEdge &edge);
};


class GraphEdge {
public:
	std::string name;
	std::string source_var;
	std::string dest_var;
	bool stream_of_arrays;
	int array_size;
	int word_size;
	GraphNode *destination;

	GraphEdge (std::string name) : name(name) { destination = NULL; stream_of_arrays = false;};
	GraphEdge (std::string name, GraphNode &destination) : name(name), destination(&destination) { stream_of_arrays = false;};
	GraphEdge (const GraphEdge &original) : name(original.name), destination (original.destination) { stream_of_arrays = false;};

	GraphEdge& operator=(const GraphEdge &right);
};


class Graph {
public:
	std::list <GraphNode> nodes;

	GraphNode& addNode (GraphNode &node);
	GraphEdge& addEdge (std::string name, GraphNode &source, bool stream_of_arrays, int array_size, int word_size);
	GraphEdge& addEdge (std::string name, GraphNode &source, GraphNode &destination, bool stream_of_arrays, int array_size, int word_size);
	void addEdgeDestination (GraphEdge &edge, GraphNode &destination);
	void Connect ();
	void Replicate (Graph &);
	void debugPrint ();
	void debugPrintEdges ();
	void printDot (std::stringstream &out);

private:
	void build_trees (GraphNode &original, int num_trees, int in_size, int reduce_size, double speedup, unsigned int &collectors, unsigned int &doubles, std::string in_stream_name, std::string reduce_stream_name, int word_size);
};
#endif