import java.util.*;
import java.awt.*;
import java.awt .event .*;
import java.applet.*;

class PolyElement
{
	public double num;// 
	public int index;// figer
}

class Poly
{
	private LinkedList m_lsA;
	private LinkedList m_lsB;
	private LinkedList m_lsResult;
	private int m_nFlag;
	
	public Poly()
	{
		m_lsA = new LinkedList();
		m_lsB = new LinkedList();
		m_lsResult = new LinkedList();
	}
	
	public boolean initPoly(String a, String b)
	{
		if(initLinkedList(a, m_lsA) && initLinkedList(b, m_lsB))
			return true;
		else
			return false;
	}
	public void stepAdd()
	{
		PolyElement a = new PolyElement();
		PolyElement b = new PolyElement();
		if(!m_lsA.isEmpty() && !m_lsB.isEmpty())
		{
			a = (PolyElement)m_lsA.getFirst();
			b = (PolyElement)m_lsB.getFirst();
			switch(cmp(a, b))
			{
				case -1:
					m_lsResult.add(b);
					m_lsB.removeFirst();
					break;
				case 0:
					a.num += b.num;
					if(a.num != 0)
					{
						m_lsResult.add(a);
					}
					m_lsA.removeFirst();
					m_lsB.removeFirst();
					break;
				case 1:
					m_lsResult.add(a);
					m_lsA.removeFirst();
					break;
				default:
					break;	
			}
		}
		else
		if(!m_lsA.isEmpty())
		{
			a = (PolyElement)m_lsA.getFirst();
			m_lsResult.add(a);
			m_lsA.removeFirst();
		}
		else
		{
			b = (PolyElement)m_lsB.getFirst();
			m_lsResult.add(b);
			m_lsB.removeFirst();
		}
	}
	public LinkedList addPoly()
	{
		PolyElement a = new PolyElement();
		PolyElement b = new PolyElement();
		
		while(!m_lsA.isEmpty() && !m_lsB.isEmpty())
		{
			a = (PolyElement)m_lsA.getFirst();
			b = (PolyElement)m_lsB.getFirst();
			switch(cmp(a, b))
			{
				case -1:
					m_lsResult.add(b);
					m_lsB.removeFirst();
					break;
				case 0:
					a.num += b.num;
					if(a.num != 0)
					{
						m_lsResult.add(a);
					}
					m_lsA.removeFirst();
					m_lsB.removeFirst();
					break;
				case 1:
					m_lsResult.add(a);
					m_lsA.removeFirst();
					break;
				default:
					break;	
			}
		}
		if(!m_lsA.isEmpty())
			while(!m_lsA.isEmpty())
			{
				PolyElement p = (PolyElement)m_lsA.getFirst();
				m_lsResult.add(p);
				m_lsA.removeFirst();
			}
		else
			while(!m_lsB.isEmpty())
			{
				PolyElement p = (PolyElement)m_lsB.getFirst();
				m_lsResult.add(p);
				m_lsB.removeFirst();
			}
		
		return m_lsResult;
	}
	
	private int cmp(PolyElement a, PolyElement b)
	{
		switch(m_nFlag)
		{
			case 1:
				if(a.index > b.index)
				{
					//m_nIndex = 2;
					return 1;
				}
				else
					if(a.index == b.index)
					{	
						//m_nIndex = 3;
						return 0;
					}
					else
					{	//m_nIndex = 1;
						return -1;
					}
			case 2:
				if(a.index > b.index)
				{
					//m_nIndex = 2;
					return -1;
				}
				else
					if(a.index == b.index)
					{
						//m_nIndex = 3;
						return 0;
					}
					else
					{
						//m_nIndex = 1;
						return 1;
					}
			default:
				return 1;
		}			
	}
	
	public boolean initLinkedList(String s, LinkedList ls)
	{
		ls.clear();
		System.out.println(s);
		
		StringBuffer buffer = new StringBuffer();
		for(int i = 0; i < s.length(); i ++)
		{
			char c = s.charAt(i);
			if((c != '\u0020') && (c != '\u0009'))
			{
				if((c == 'x') || (c == 'X'))
					buffer.append('x');
				else
				{
					if((c == '+') || (c == '-') )
						buffer.append(' ');
					buffer.append(c);
				}
			}
		}
		s = buffer.toString();
		StringTokenizer token = new StringTokenizer(s, " ");
		LinkedList lsString = new LinkedList();
		while(token.hasMoreTokens())
		{
			String ss = token.nextToken();
			lsString.add(ss);
		}
		
		while(!lsString.isEmpty())
		{
			String strOld = (String)lsString.getFirst();
			int index = strOld.indexOf("x");
			if(index != -1)
			{
				String sNum = strOld.substring(0, index);
				String sIndex = strOld.substring(index+1,strOld.length()); 
				double dbNum = Double.valueOf(sNum).doubleValue();
				int nIndex = Integer.valueOf(sIndex).intValue();
				PolyElement poly = new PolyElement();
				poly.num = dbNum;
				poly.index = nIndex;
				ls.add(poly);
			}
			lsString.removeFirst();
		}
		if(ls.size() >= 2)
		{
			PolyElement pFirst = (PolyElement)ls.getFirst();
			PolyElement pLast = (PolyElement)ls.getLast();
			if(pFirst.index > pLast.index)
				m_nFlag = 1;// order
			else
				m_nFlag = 2;// the opposite order
		}
		else
			m_nFlag = 1;
		return true;
	}
	public LinkedList getLinkedList(int nIndex)
	{
		switch(nIndex)
		{
			case 1:		// return m_lsA;
				return m_lsA;
			case 2:
				return m_lsB;
			case 3:
				return m_lsResult;
			default:
				return null;
		}
	}
}
public class PolyDemo extends Applet implements ActionListener
{
	
	public	Poly 		m_poly;
	public	Button		m_btnStep,m_btnReset,m_btnGo;
	public	TextField	m_tfDataFirst;
	public	TextField	m_tfDataSecond;
	public  int		m_nStep=-1,m_nLength=0; 
	private TextArea	m_taCodeSource;
	
	private String		m_sPoly1 = "1x2-2x4-3x7-6x9";
	private String		m_sPoly2 = "1x1-2x3+7x7-5x8+9x9";
	
	private String[]		m_sCode={"AddPoly(Poly a, Poly b){",			//0
					"PolyElement* pA = GetFirst(a);",			//1
					"PolyElement* pB = GetFirst(b);",			//2
					"while((*pA != NULL) && (*pB != NULL)){",		//3
					"	int result = compareIndex(*pA, *pB);",		//4
					"	switch(result)",				//5
					"	{",						//6
					"		case 1:		// *pA index number is smaller",//7
					"			addPolyElementToResult(*pA);",		//8	
					"			pA = *pA->pNext;",			//9
					"		case 0:		// *pA index number is equal the *pB's",//10
					"			addPolyElementToResult(*pA+*pB);",		//11
					"			pA = *pA->pNext;",				//12
					"		case -1:	// *pB index number is smaller",	//13
					"			addPolyElementToResult(*pB);",			//14
					"			pB = *pB->pNext;",				//15
					"	}",								//16
					"}",									//17
					"AddRestToResult();",							//18
				"}"};
	public int m_nIndex;// 0 express initialization
			    // 1 express A < B
			    // 2 express A > B
			    // 3 express A = B								//19
	private String		m_sMessageS = "该项指数较小，插入结果中";
	private String		m_sMessageE = "两项指数相等，系数运算";
	private int		m_nLeft = 350;
	private int		m_nFirst = 50;
	private int 		m_nSecond = 150;
	private int 		m_nResult = 250;
	private int 		m_nWidth = 60;
	private int 		m_nHeight = 30;
	private int 		m_nInterval = 5;
	private int 		m_nOrigin = 350;
	
	public void actionPerformed(ActionEvent e)
	{
		if(e.getSource ()==m_btnReset)
		{
			reset();
		}
		else if(e.getSource ()==m_btnStep)
		{
			step();
		}
		else if(e.getSource ()==m_btnGo)
		{
			go();
		}
	}
	
	private void addComponent(Component c,int x,int y,int width,int height)
	{
		c.setLocation (x,y);
		c.setSize (width,height);		
		add(c);
	}
	public void showSourceCode()
	{
		m_taCodeSource.setText("");
		for(int i=0;i<m_sCode.length ;i++)
			m_taCodeSource.append (m_sCode[i]+"\r\n");
	}
	public void getCurrentSource()
	{
		if(m_poly.getLinkedList(1).size() == 0 || m_poly.getLinkedList(2).size() == 0)
		{
			m_nStep = 0;
			m_nLength = 0;
			return ;
		}
		PolyElement pFirst = (PolyElement)m_poly.getLinkedList(1).getFirst();
		PolyElement pSecond = (PolyElement)m_poly.getLinkedList(2).getFirst();
		if(pFirst.index < pSecond.index)
			m_nIndex = 1;
		else
			if(pFirst.index > pSecond.index)
				m_nIndex = 2;
			else
				m_nIndex = 3;
		switch(m_nIndex)
		{
			case 0:
				m_nStep = 0;
				m_nLength = 0;
				break;
			case 1:
				m_nStep = 7;
				m_nLength = 3;
				break;
			case 2:
				m_nStep = 13;
				m_nLength = 3;
				break;
			case 3:
				m_nStep = 10;
				m_nLength = 3;
				break;
			default :
				m_nStep = 0;
				m_nLength = 0;
				
		}
	}
	public void showCode()
	{
		getCurrentSource();
		//m_taCodeSource.setText(" "+ m_nIndex);
		if(m_nStep==-1)
		{
			m_taCodeSource.select (0,0);
			return;		
		}
		int nStart=0;
		int nEnd=0;
		for(int i=0;i<m_nStep;i++)
			nStart+=m_sCode[i].length()+3;
		//nStart+=1;
		nEnd = nStart;
		for(int i=0;i<m_nLength;i++)
			nEnd += m_sCode[m_nStep+i].length()+2;
		m_taCodeSource.select(nStart,nEnd);		
	}
	public void reset()
	{
		m_sPoly1 = m_tfDataFirst.getText();
		m_sPoly2 = m_tfDataSecond.getText();
		m_poly.getLinkedList(3).clear();
		m_poly.initPoly(m_sPoly1, m_sPoly2);
		repaint();
	}
	private void step()
	{
		m_poly.stepAdd();
		showCode();
		repaint();
	}
	private void go()
	{
		while(!m_poly.getLinkedList(1).isEmpty() || !m_poly.getLinkedList(2).isEmpty())
		{
			m_poly.stepAdd();
			repaint();
		}
	}
	
	public void paint(Graphics g)
	{
		drawFirstPoly(g);
		drawSecondPoly(g);
		drawResultPoly(g);
		drawCur(g);
	}
	public void drawCur(Graphics g)
	{
		m_nLeft = m_nOrigin;
		PolyElement pFirst = (PolyElement)m_poly.getLinkedList(1).getFirst();
		PolyElement pSecond = (PolyElement)m_poly.getLinkedList(2).getFirst();
		g.setColor(Color.red);
		if(pFirst.index < pSecond.index)
		{
			g.drawLine(m_nLeft+m_nWidth/2,m_nFirst, m_nLeft+m_nWidth/2, m_nFirst-30);
			g.drawLine(m_nLeft+m_nWidth/2,m_nFirst, m_nLeft+m_nWidth/2-10,m_nFirst-10);
			g.drawLine(m_nLeft+m_nWidth/2,m_nFirst, m_nLeft+m_nWidth/2+10,m_nFirst-10);
			g.drawString(m_sMessageS, m_nLeft+m_nWidth/2, m_nFirst-30);
		}
		else
			if(pFirst.index == pSecond.index)
			{
				g.drawLine(m_nLeft+m_nWidth/2,m_nFirst, m_nLeft+m_nWidth/2, m_nFirst-30);
				g.drawLine(m_nLeft+m_nWidth/2,m_nFirst, m_nLeft+m_nWidth/2-10,m_nFirst-10);
				g.drawLine(m_nLeft+m_nWidth/2,m_nFirst, m_nLeft+m_nWidth/2+10,m_nFirst-10);
				g.drawString(m_sMessageE, m_nLeft+m_nWidth/2, m_nFirst-30);
				
				g.drawLine(m_nLeft+m_nWidth/2,m_nSecond, m_nLeft+m_nWidth/2, m_nSecond-30);
				g.drawLine(m_nLeft+m_nWidth/2,m_nSecond, m_nLeft+m_nWidth/2-10,m_nSecond-10);
				g.drawLine(m_nLeft+m_nWidth/2,m_nSecond, m_nLeft+m_nWidth/2+10,m_nSecond-10);
				g.drawString(m_sMessageE, m_nLeft+m_nWidth/2, m_nSecond-30);
			}
			else
			{
				g.drawLine(m_nLeft+m_nWidth/2,m_nSecond, m_nLeft+m_nWidth/2, m_nSecond-30);
				g.drawLine(m_nLeft+m_nWidth/2,m_nSecond, m_nLeft+m_nWidth/2-10,m_nSecond-10);
				g.drawLine(m_nLeft+m_nWidth/2,m_nSecond, m_nLeft+m_nWidth/2+10,m_nSecond-10);
				g.drawString(m_sMessageS, m_nLeft+m_nWidth/2, m_nSecond-30);
			}
					
		
	}
	public void drawFirstPoly(Graphics g)
	{
		m_nLeft = m_nOrigin;
		for(int i = 0; i < m_poly.getLinkedList(1).size(); i ++)
		{
			m_nLeft += m_nInterval;
			g.setColor(Color.red);
			g.fillRect(m_nLeft+i*m_nWidth, m_nFirst, m_nWidth, m_nHeight);
			g.setColor(Color.black);
			g.drawLine(m_nLeft+i*m_nWidth+m_nWidth/3,m_nFirst, m_nLeft+i*m_nWidth+m_nWidth/3, m_nFirst+m_nHeight);
			g.drawLine(m_nLeft+i*m_nWidth+2*m_nWidth/3,m_nFirst, m_nLeft+i*m_nWidth+2*m_nWidth/3, m_nFirst+m_nHeight);
			g.drawRect(m_nLeft+i*m_nWidth, m_nFirst, m_nWidth, m_nHeight);
			LinkedList ls = m_poly.getLinkedList(1);
			PolyElement p = (PolyElement)ls.get(i);
			Double d = new Double(p.num);
			g.drawString(d.toString(),m_nLeft+i*m_nWidth, m_nFirst+13);
			Integer index = new Integer(p.index);
			g.drawString("x",m_nLeft+i*m_nWidth+m_nWidth/3+6, m_nFirst+13);
			g.drawString(index.toString(),m_nLeft+i*m_nWidth+2*m_nWidth/3+2, m_nFirst+13);
		}
	}
	public void drawSecondPoly(Graphics g)
	{
		m_nLeft = m_nOrigin;
		for(int i = 0; i < m_poly.getLinkedList(2).size(); i ++)
		{
			m_nLeft += m_nInterval;
			g.setColor(Color.red);
			g.fillRect(m_nLeft+i*m_nWidth, m_nSecond, m_nWidth, m_nHeight);
			g.setColor(Color.black);
			g.drawLine(m_nLeft+i*m_nWidth+m_nWidth/3,m_nSecond, m_nLeft+i*m_nWidth+m_nWidth/3, m_nSecond+m_nHeight);
			g.drawLine(m_nLeft+i*m_nWidth+2*m_nWidth/3,m_nSecond, m_nLeft+i*m_nWidth+2*m_nWidth/3, m_nSecond+m_nHeight);
			g.drawRect(m_nLeft+i*m_nWidth, m_nSecond, m_nWidth, m_nHeight);
			LinkedList ls = m_poly.getLinkedList(2);
			PolyElement p = (PolyElement)ls.get(i);
			Double d = new Double(p.num);
			g.drawString(d.toString(),m_nLeft+i*m_nWidth, m_nSecond+13);
			Integer index = new Integer(p.index);
			g.drawString("x",m_nLeft+i*m_nWidth+m_nWidth/3+6, m_nSecond+13);
			g.drawString(index.toString(),m_nLeft+i*m_nWidth+2*m_nWidth/3+2, m_nSecond+13);
		}
	}
	public void drawResultPoly(Graphics g)
	{
		m_nLeft = m_nOrigin;
		for(int i = 0; i < m_poly.getLinkedList(3).size(); i ++)
		{
			m_nLeft += m_nInterval;
			g.setColor(Color.red);
			g.fillRect(m_nLeft+i*m_nWidth, m_nResult, m_nWidth, m_nHeight);
			g.setColor(Color.black);
			g.drawLine(m_nLeft+i*m_nWidth+m_nWidth/3,m_nResult, m_nLeft+i*m_nWidth+m_nWidth/3, m_nResult+m_nHeight);
			g.drawLine(m_nLeft+i*m_nWidth+2*m_nWidth/3,m_nResult, m_nLeft+i*m_nWidth+2*m_nWidth/3, m_nResult+m_nHeight);
			g.drawRect(m_nLeft+i*m_nWidth, m_nResult, m_nWidth, m_nHeight);
			LinkedList ls = m_poly.getLinkedList(3);
			PolyElement p = (PolyElement)ls.get(i);
			Double d = new Double(p.num);
			g.drawString(d.toString(),m_nLeft+i*m_nWidth, m_nResult+13);
			Integer index = new Integer(p.index);
			g.drawString("x",m_nLeft+i*m_nWidth+m_nWidth/3+6, m_nResult+13);
			g.drawString(index.toString(),m_nLeft+i*m_nWidth+2*m_nWidth/3+2, m_nResult+13);
		}
	}
	public void init()
	{
		setLayout(null);
	
		m_taCodeSource		=new TextArea(18,50);
		m_taCodeSource.		setEditable (false);
		m_taCodeSource.		setBackground (Color.white );	
		showSourceCode();
		
		m_btnStep		=new Button("单步执行");		
		m_btnReset		=new Button("重置数据");
		m_btnGo			=new Button("连续执行");			
			
		m_tfDataFirst		=new TextField (m_sPoly1);
		m_tfDataSecond		=new TextField (m_sPoly2);
		
		m_btnStep.		addActionListener (this);
		m_btnReset.		addActionListener (this);
		m_btnGo.		addActionListener (this);
		
		
		int nHeight		=20;
		int nWidth		=15;
			
		addComponent(m_taCodeSource,20,20,300,280);
	
		addComponent(m_btnReset,20, 320,nWidth*5,nHeight);
		addComponent(m_btnStep, 120,320,nWidth*5,nHeight);
		addComponent(m_btnGo,	240,320,nWidth*5,nHeight);
				
		addComponent(m_tfDataFirst,	450,320,nWidth*12,nHeight);
		addComponent(m_tfDataSecond,	450,360,nWidth*12,nHeight);
		
		m_poly = new Poly();
		m_poly.initPoly(m_sPoly1,m_sPoly2);
		
		showCode();
		
	}
}
