/**************************************************************************************
* GPDD.h
* GPDD is the class for Graph-Pair Decision Diagram.

*        Symbolic Circuit Analysis With GPDDs (Graph-Pair Decision Diagram)
*
// Weiwei CHEN, Guoyong SHI; 03-31-2006
// School of Microelectronics, Shanghai Jiao Tong Univ.
// {shiguoyong}@ic.sjtu.edu.cn
**************************************************************************************/


#ifndef GPDD_H
#define GPDD_H

#include<map>
#include <vector>
#include <string>


#include "Hashtree.h"
#include "gpdd_struct.h"
#include "GPDDnode.h"

//#include "MOS.h"
//#include "../Device/Device.h"		// with HybridSim

/**
	The class of graph-pair decision diagram (GPDD).
*/

//class Device;

class GPDD : public AnyObject
{
private:
	//the order number of sensitivity element designated
	int SensIndex;
	
	/// the number of the nodes in the graph of the circuit.
//		int N;							
	int NumNodes;							

	int	NumMOSDevices;

	/// the number of graph edges of the whole circuit.
	int 	NumEdges;							

	int 	NumEdges_L;	// number of edges in the Left Graph						
	int 	NumEdges_R;	// number of edges in the Right Graph	
	
	int 	VsN;	/// the number of the VS edges
	int 	VcN;	/// the number of the VC edges
	int 	CsN;	/// the number of the CS edges		
	int 	CcN;	/// the number of the CC edges			
	
	int DpenSrcN;  /// the number of the dependent sources

	/// the number of the lumped symbols in the graph of the circuit.
		int NumSymbols;						
	
	/// the total number of the symbols in the graph of the circuit.
		int TotalNumSymbols;

	/// the number of the terms in the symbolic expression of the transfer funcion of the circuit. 
		double NumTerms;

	/// the list of the edges in the graph of the circuit.
		Edge *EdgeList;			
	
	/// the list of the lumped symbols in the graph of the circuit.
		SymbNode **LumpedSymbList;		// lumped symbol list		
	
	/// the list of all the symbols in the graph of the circuit.
	SymbNode 	**FullSymbList;			// **SNoLumplist;
	SymbNode 	**ExpSymbList;
	SymbNode 	*SymbListTemp;

	SymbNode	SymbOne;			// symbol for GPDD vertex "One"
	SymbNode	SymbZero;			// symbol for GPDD vertex "Zero"

///	MOS  *MOS_List;

	/// the root node of the tree pair decision diagram.
		GPDDnode * pGPDDroot;			

	/// the 1-terminal node of the tree pair decision diagram.
		GPDDnode * VertexOne;

	/// the 0-terminal node of the tree pair decision diagram.
		GPDDnode * VertexZero;

	int 	*PathStack;		// *PathArray;
	int 	StackTop;
	int 	TermSign;

	
	/// the list for GPDD reduce.	
		GPDDnode ** ReduceList;

	/// the list to collect all the GPDD nodes.
		std::vector<GPDDnode*> NodeList;

	/// the 1-terminal node of the decision diagram for the coefficients of the s-variable.
		sCoeffNode *sCoeffOne;
	
	/// the 0-terminal node of the decision diagram for the coefficients of the s-variable.
		sCoeffNode *sCoeffZero;
	
	/// the 1-terminal node of the expanded GPDD decision diagram (no lumped symbols).
		ExpGPDDnode *ExpOne;

	/// the 0-terminal node of the expanded GPDD decision diagram (no lumped symbols).
		ExpGPDDnode *ExpZero;

	// (Newly added by G. Shi, 09-05-2010)
	bool 	LumpedExpandedFlag;	// indicates whether the GPDD has been "lump-expanded".
	bool		sExpandedFlag;			// indicates whether the GPDD has been "s-expanded".

	bool		TraversalMark;		// a global mark for GPDD traversal
	/*  	A global traversal mark is useful in many functions that require a full traversal of the GPDD.
		By maintaining a global vertex flag, it is not needed to mark/unmark all vertices
		before starting a complete traversal. Use the existing flag as the reference, 
		and check whether a vertex is visited by flipping the previous flag.

		Before and after a traversal, all GPDD vertices are maintained at a uniform flag, which
		is set to BDDnode::mark in the base class. Initially, all vertices are marked `false' and
		the global flag also is `false'.
		
		(A technique used in HybridSim. G. Shi, 09-16-2010)
	*/

	// Numbers used to trace GPDD paths
	int CountOfMinusTerms;
	int CountOfPlusTerms;

	// Quantities for statistics
	int TotalExpandedGPDDnodes;
	int TotalGPDDnodes;
	int NodeCreationCount;
	int SubgraphCount;
	int SubgraphSharingCount;
	int GPDDnodeSharingCount;
	
	int NumNodesRemoved;

	/// the number of the GPDD nodes after Reduce.
	int NumNodesRemaining;					
	
	int sCoeffNodeCount;
	// Flags
	int *PermMark;
	int *NodeMark;
	int MaxNumNodes;
	
public:	
		inline void IncTotalGpddNodes() { TotalGPDDnodes++;}
		
	/// the root node of the expanded GPDD decision diagram (no lumped symbols).
	ExpGPDDnode *ExpGPDDroot;

	/// the unique table for the reduced subgraphs
	HashTree **uniqSubgraph;

	/// the unique table for the GPDD nodes.
	HashTree ***uniqGPDD;

	/// the unique table for the nodes of the coefficients of s-variables.
	HashTree ***uniqCoeffGPDD;

	/// the unique table for the expandded GPDD nodes.
	HashTree ***uniqExpGPDD;

	/// Hash table: map symbol name to its SymbNode
	map<const string, SymbNode *> SymbHashTable;
	
public:
	GPDD();

	/**
		The constructor of GPDD with parameters.
		@param nn the number of the nodes in the graph of the circuit to analysis.
		@param en the number of the edges in the graph of the circuit to analysis.
		@param edge_list the list of the edges  in the graph of the circuit to analysis.
	*/
	GPDD(int num_nodes,  int num_edges, Edge_g * edge_list);
	GPDD(int num_nodes,  int num_edges, int num_mosfets, Edge_g * edge_list);

///	GPDD(int nn,  int en, vector<Device *> &dev_vec);	// For use with HybridSim

	~GPDD();

		inline int GetSensitivityIndex() {return SensIndex;}
		
		inline void SetSensitivityIndex(int  index) {  SensIndex = index;}
	/**
		Get the number of the edges in the graph of the circuit to analysis.
	*/
	inline int GetNumEdges() {return NumEdges;}

	/**
		Get the number of the nodes in the graph of the circuit to analysis.
	*/
	inline int GetNumNodes() {return NumNodes;} 

	/**
		Get the number of the lumped symbols in the graph of the circuit to analysis.
	*/
	inline int GetNumSymbols() {return NumSymbols;}

	/**
		Get the number of the voltage controlled sources in the circuit to analysis.
	*/
	inline int GetNumVS() {return VsN;}
	
	/**
		Get the number of the voltage controlling sources in the circuit to analysis.
	*/
	inline int GetNumVC() {return VcN;} 

	/**
		Get the number of the current controlled sources in the circuit to analysis.
	*/
	inline int GetNumCS() {return CsN;}

	/**
		Get the number of the current controlling sources in the circuit to analysis.
	*/
	inline int GetNumCC() {return CcN;}

	/**
		Get the number of the dependent sources in the circuit to analysis.
	*/
	inline int GetNumDependentSource() {return DpenSrcN;}
//	inline unsigned int GetNumTerms() {return NumTerms;}

	/**
		Get the number of the terms in the transfer function (TF).
	*/
	inline double GetNumTerms() {return NumTerms;}


	/**
		Get the root of the tree pair decision diagram.
	*/
	inline GPDDnode* GetGPDDroot() {return pGPDDroot;}

	inline ExpGPDDnode* GetExpGPDDroot() {return ExpGPDDroot;}
	
	// --------------Add by Xu Hui------------ //
	inline void SetGPDDroot(GPDDnode *p) {pGPDDroot = p;}

	inline GPDDnode ** SetReduceList(GPDDnode **p) {ReduceList = p;}

	inline void SetReduceNodeNum(int i) {NumNodesRemoved = i;}
	inline void AddReduceNodeNum() {NumNodesRemoved++;}
	
	inline std::vector<GPDDnode*> & GetNodeList() {return NodeList;}

//	inline void SetRNodeNum(int i) {NumNodesRemaining = i;}   // (not needed)
	// --------------Add by Xu Hui------------ //
	
	inline double	GetSymbolValue(int index) 	{ return  LumpedSymbList[index]->value; }
	inline double	GetSymbolValue_i(int index) 	{ return  LumpedSymbList[index]->imag; }

	double GetSymbolValue(int index, const char *name);
	int  	GetSymbolValue(const std::string &symbname, double &value);

	int 	SetNewValue(const std::string &symbname, double &oldvalue, double newvalue);

	inline void SetSymbolValue(int index, double value){ \
		LumpedSymbList[index]->value = value; }
	inline void SetSymbolValue_i(int index, double value)  \
		{ LumpedSymbList[index]->imag = value;}

	
///	inline double	GetSymSens(int index) { return  LumpedSymbList[index]->sens; }

	/**
		Get the name of the symbol with index <I> index</I>.
		@param index the index of the symbol whose name should be returned.
	*/
	inline char*	GetSymbolName(int index) { return  LumpedSymbList[index]->symbname; }

//	inline double   GetSensImag(int index) { return LumpedSymbList[index]->sens_i; }    // (not used)

	/**
		Get the symbol list LumpedSymbList.
		Each entry in the LumpedSymbList is a pointor to a SymbNode.
	*/
	inline SymbNode ** GetLumpedSymbList() {return LumpedSymbList;}

	inline Edge * GetEdgeList() {return EdgeList;}

//******** Sensitivity relevant functions (below) ****************************

	int   LookupSymbolIndex(const char * name);
	
//	void Modify_value(double new_value, int tag, char * name);
	void  ChangeSymbolValue(int index, const char * name, double new_value);

	//! Change the value of a specific component
	//! 2008-10-29 22:46; Li Ji
	int 	SetNewValue(const std::string &symbname, double newvalue);
	int   VariationByPercentage(const string &symbname, double percent);


///	void EvaluateSymbolAtFreq(double freq);

	void EvaluateAllSymbolsAtFreq(double freq);
	

	inline GPDDnode *GetVertexOne() {return VertexOne;}
	inline GPDDnode *GetVertexZero() {return VertexZero;}
	
	inline sCoeffNode *Get_sCoeffOne() {return sCoeffOne;}
	inline sCoeffNode *Get_sCoeffZero() {return sCoeffZero;}

	inline bool  LumpExpanded()	{ return LumpedExpandedFlag; }
	inline bool  sExpanded()		{ return sExpandedFlag; }


//******** Sensitivity relevant functions (above) ****************************

	/**
		The function to create the edge list.
	*/
	int CreateEdgeList(Edge_g * edge_list);

	/**
	  The function to create the edge list from Subckt (used in HybridSim).
	*/
///	int CreateEdgeList(vector<Device *> &dev_vec);

	int CreateSymbList();

	/**
		The function to add symbols into the symbol list LumpedSymbList.
		The symbols could be lumped are managed in this function.
	*/
	void AddSymbol(Edge *p_edge);

	/**
		The function to sort the symbols before constructing a GPDD.
		Heuristic ordering are applied in this function.
		<BR><EM><B>Not implemented perfectly yet!</B><EM>
	*/
	void SortSymbList();

	/**
		The function to set the paired edges. If the two edges are related to one dependent source, 
		they should be the paired edges with each other.
	*/
	void SetPairing();
	
	/**
		The function to initialate the left graph for further graph reduction.
		The left graph should remove all the edges with type VC.
	*/
	EdgeInfo* InitLeftGraph(int &signL);

	/**
		The function to initialate the right graph for further graph reduction.
		The left graph should remove all the edges with type CS.
	*/
	EdgeInfo* InitRightGraph(int &signR);

	void 	InitGPDDroot();

	EdgeInfo* CreateLeftGraph(int optype, GPDDnode *fatherVertex, int sonEdges, 
				int fatherNodes, int &sonNodes, int &signL);
	
	EdgeInfo* CreateRightGraph(int optype, GPDDnode *fatherVertex, int sonEdges, 
				int fatherNodes, int &sonNodes, int &signR);

	
	GPDDnode* CreateGPDDnode(GPDDnode * pParent, int optype);

	void 	GraphReduction();	/*** The key member function of GPDD ***/
	/** Recursive implementation **/
	
	/**
		Create the GPDD by a non-recursive implementation. 
	*/
	void 	GraphReduction_NR();

	
	/**
		Binary decision: Reduce the graph-pair by the EXCLUDE operation (i.e., SYMBOL_OUT).
		Recursive implementation.
	*/
	GPDDnode* Reduction_EXCLUDE_R(GPDDnode * pParent);
	
	/**
		Binary decision: Reduce the graph-pair by the INCLUDE operation (i.e., SYMBOL_IN).
		Recursive implementation.
	*/
	GPDDnode* Reduction_INCLUDE_R(GPDDnode * pParent);
	

	/**
		Get the total number of nodes in the reduced graph.
		@param pEdgeInfo the pointor to the array representing the reduced graph.
		@param e_size the number of the edges in the reduced graph.
	*/
	int GetNodeSize(EdgeInfo *pEdgeInfo, int e_size);
	
	/**
		Check whether any CC or VS edges are remaining in the remaining edges
		when only one node is left at the end of graph reduction.
	*/
//	int CheckValidTree(EdgeInfo *edgelist, int numedges);
	int CC_VS_Left(EdgeInfo *edgelist, int numedges);
	
	/**
		Detect if a valid tree could be generated from this reduced graph.
		@param pEdgeInfo the pointer to the reduced graph from which the valid tree is generated.
		@param e_size the number of the edges in the reduced graph.
		@param n_size the number of the nodes in the reduced graph.
	*/
	int DetectTree(EdgeInfo *pEdgeInfo, int e_size, int n_size);

	/**
		Get the permuation number of this reduced graph.
		The number is used to determine the sign of the reduced graph generated by current reduced graph.
		@param pEdgeInfo the pointer to the current reduced graph from which the valid tree is generated.
		@param e_size the number of the edges in the reduced graph.
		@param n_size the number of the nodes in the reduced graph.
	*/
	int   GetPermNum(EdgeInfo *pEdgeInfo, int e_size, int n);

	/**
		Print the infos of the symbols in the circuit.
	*/
	void  PrintSymbols();

	void  PrintCircuitStatistics();
	
	void  PrintPartialEdgeList(EdgeInfo *edgelist, int length);
	void  PrintFullEdgeList();
	
	void  PrintGraph(std::ostream &out);   // print the circuit graph edges
	void  PrintGPDD(std::ostream &out);	  // Print the whole GPDD.
	void  PrintGPDD_R(std::ostream &out, GPDDnode *p);

	void  PrintGPDDStatistics();

	void UnMarkAllNodes(BDDnode* p, int type);
	void UnMarkNode_R(GPDDnode *p);

	/**
		Print all the terms in the GPDD. The terms are represented by the paths that go along
		the solid arrows.
		@param out the ostream object for console output.
	*/
	void PrintTerms(std::ostream &out);
	void PrintTerms_R(std::ostream &out, GPDDnode *p);

	void PrintTransferFunction(std::ostream &out);
	void PrintTransferFunction_R(std::ostream &out, GPDDnode *p);

	void  CountGPDDTerms();
	double CountGPDDTerms_R(GPDDnode *p);

	Subgraph *ShareSubgraph(Subgraph* p);

	GPDDnode *ShareGPDDnode(GPDDnode *p, int &hashed);

	/**
		Count the number of the valide edges in the reduced graph.
		The valid edges should not be self-looped.
		@param pe the pointer to the reduced graph.
		@param En the number of the edges in the reduced graph.
		@return int number of valid edges.
	*/
	int  CountValidEdges(EdgeInfo *pe, int En);

	/**
		Collect all the nodes in the GPDD into the vector ReducedList[] for GPDD reduce.
	*/
	void CollectNodes();
	void CollectNodes_R(GPDDnode * p);
	
	void  FlipTraversalMark() 	{  TraversalMark = !TraversalMark;}
	bool  GetTraversalMark() 	{  return TraversalMark;}
	void  SetTraversalMark(bool mark) 	{  TraversalMark = mark;}

	int 	Reduce();

	/**
		Garbage collection.
		When performing GPDD reduce, the GPDD nodes belonging to the isomorphic reduced graphs
		should be released.
	*/
	void GC();

	/**
		Garbage collection in the specified unique table.
		Unreferred nodes will be released.
		@param i the first dimension of the unique table.
		@param j the second dimension of the unique table.
	*/
	void doGC(int i, int j);

	/**
		Set the label of all the GPDD nodes.
		The label is used in GPDD reduce.
		@param ReduceHTree the unique table for GPDD reduction. The number of the nodes with the same label
		should always be 1 for a reduced GPDD.
	*/
	void SetAllNodeLabels( HashTree ***ReduceHTree);

	/**
		Recursively set the label of all the GPDD nodes.
		The label is used in GPDD reduce.
		@param ReduceHTree the unique table for GPDD reduction. The number of the nodes with the same label
		should always be 1 for a reduced GPDD.
		@param p the root of the subGPDD whose nodes' lables are to be set.
		@param level the entry of the unique table.
	*/
//	void SetNodeLabelR(GPDDnode *p, HashTree **ReduceHTree, int level);
	void SetNodeLabel(GPDDnode *p, HashTree **ReduceHTree);
	

// Operations for extracting the coefficients of s-polynomial.
	/**
		Reference all the nodes in GPDD.
	*/
	void ReferenceAllNodes();
	void Reference_R(GPDDnode *p);

	/**
		Reset all the node references in GPDD.	
	*/
	void ResetAllReferences(BDDnode*p, int type);
	void ResetReference_R(GPDDnode *p);


	/**
		Extract the coeffcients of the s-variables in the transfer function.
		The symbols should not be lumped for s-coeffcients extraction.
	*/
	void 	sExpandGPDD();

	/**
		Recursively create the coeffcients of the s-polynomials in the transfer function.
	    <BR><UL>					a0 + a1 * s + a2 * s^2 + ... + am * s^m </UL> 
				TF =    --------------------------------------------------------
		<BR><UL>				    b0 + b1 * s + b2 * s^2 + ... + bn * s^n</UL>

		The approximate poles/zeros could be achieved by the coefficients of the s-variables, e.g.
		<BR><PRE>  pole_i = -bi / bi+1 </PRE>
		<PRE> zero_i = -ai / ai+1 </PRE>
		@param p the root of the expanded subGPDD whose coeffcients of s-variables should be extracted.
	*/
	void 	CreateCoeffList(ExpGPDDnode * p);

	/**
		Print all the coeffcients of the s-polynomials.
	*/
	void  Print_sPolynomialCoeffs(ostream &out);

	/**
		Print all terms of the coeffcient of one s-exponent.
	*/
	//void PrintScoeffPath(std::ostream &out, sCoeffNode *psCoeffNode, int iSign = 1);
	void  PrintCoefficient(ostream &out, sCoeffNode *coefnode, int sign);
	void  PrintCoefficient_R(ostream &out, sCoeffNode *coefnode);

	/**
		The function to share the sCoeffNode.
		We use a unqiue table to perform the hash scheme in this function.
		@param p the point to the sCoeffNode to hash.
		@param tag a reference parameter to tell if the node is hashed or not. 1 - hashed; 0 - not hashed. Although
		this is a parameter of the function, since it is a refecence, we change its value in the function and it plays
		as a return value of the function.
		@return the hashed sCoeffNode. If sCoeffNode is not in the unique table, it will be put into
		the unique table and it will be returned directly; If the sCoeffNode is already in the unique table, 
		the sCoeffNode will be released and the existing one will be returned.
	*/
	sCoeffNode *Share_sCoeffNode(sCoeffNode *&p, int& tag);

	/**
		Expand the GPDD nodes whose symbol is lumped.
		<BR><EM><B>x is a symbol with parallaled edges a, b, c.</B></EM>
		The node x will be expanded with nodes x, a, b, c in the expanded GPDD. Below is an example 
		for the GPDD is expansion.
		<BR><PRE>   x -> a -> b -> c 
		(ss: sign attached to the short edge; so: sign attached to the open edge)			</PRE>
		<PRE>				   x				</PRE>
		<PRE>			signs / \ signo			</PRE>
		<PRE>				 s   o				</PRE>   
		<PRE>				/ \ / \				</PRE>
		<PRE>			  ...........			</PRE>
		<PRE> expand =>							</PRE>
		<PRE>				  x					</PRE>
		<PRE>			  ss / \ 1				</PRE>
		<PRE>				/    a				</PRE>
		<PRE>			   /    / \ 1			</PRE>
		<PRE>			  |  ss/    b			</PRE>
		<PRE>			  |   /    / \ 1		</PRE>
		<PRE>			  |  / ss-/   c			</PRE>
		<PRE>			  | /  -/ ss-/  \ so	</PRE>
		<PRE>			  |/ -/ --/      o		</PRE>
		<PRE>			   s            / \		</PRE>
        <PRE>			  / \	      ......	</PRE>
		<PRE>			 .......				</PRE>

	*/
	int 	ExpandLumpedGPDD();

	/**
		Recursively expand the GPDD nodes whose symbol is lumped.
		@param p the root of the subGPDD to be expanded.
	*/
	ExpGPDDnode *ExpandLumpedGPDD_R(GPDDnode* p);

	/**
		The function to share the ExpGPDDnode.
		We use a unqiue table to perform the hash scheme in this function.
		@param p the point to the ExpGPDDnode to hash.
		@param tag a reference parameter to tell if the node is hashed or not. 1 - hashed; 0 - not hashed. Although
		this is a parameter of the function, since it is a refecence, we change its value in the function and it plays
		as a return value of the function.
		@return the hashed ExpGPDDnode. If ExpGPDDnode is not in the unique table, it will be put into
		the unique table and it will be returned directly; If the ExpGPDDnode is already in the unique table, 
		the ExpGPDDnode will be released and the existing one will be returned.
	*/
	ExpGPDDnode *Share_ExpandedGPDDnode(ExpGPDDnode *p, int& tag);

	void CleanExpandedGPDDnodes();
	void CleanExpandedGPDDnodes_R(ExpGPDDnode *&p);

	void CountNumTermsForAllCoeff();

	void CountNumTermsOneCoeff_R(sCoeffNode* p);

	void RunSymbolStatistics();

	void MarkAllNodes(BDDnode* p, int type);

	int GetCountOfMinusTerms() const {return CountOfMinusTerms;}
	int GetCountOfPlusTerms() const {return CountOfPlusTerms;}

	int GetTotalExpandedGPDDnodes() const {return TotalExpandedGPDDnodes;}
	int GetTotalGPDDnodes() const {return TotalGPDDnodes;}
	int GetNodeCreationCount() const {return NodeCreationCount;}
	int GetSubgraphCount() const {return SubgraphCount;}
	int GetSubgraphSharingCount() const {return SubgraphSharingCount;}
	int GetGPDDnodeSharingCount() const {return GPDDnodeSharingCount;}
	
	int GetNumNodesRemoved() const {return NumNodesRemoved;}

	/**
		Get the number of the GPDD nodes after redundancy reduction.
	*/
	inline int GetNumNodesRemaining() {return NumNodesRemaining;}
	
	int Get_sCoeffNodeCount() const {return sCoeffNodeCount;}
};


#endif

