/*
	this files implements the Suffix Tree Algorithm by Fan Chia-Hao (Grant).
	you could use this file to do any further using without notifying me.
	Suggestions or opinions please mail to grant@cobra.ee.ntu.edu.tw directly.
*/
import java.lang.*;
import java.lang.Math;
import java.util.*;
import javax.swing.*;
import java.awt.*;
import java.awt.event.*;
import java.applet.*;


public class SuffixTree extends JApplet implements AdjustmentListener {

	private static int x_scale = 50;
	private static int y_scale = 50;
	private static int ini_x = 50;
	private static int ini_y = 50;
    private static boolean gbranching = true;
    private static ArrayList stateList = null;
    private static int stateindex = 0;
    private static int treenodeid = 0;

    private inputFrame fr;
	private Node n;
	private TreeNode tn;
	private JScrollBar cp1;
	private JScrollBar cp2;
	protected drawPannel jp;
	private static int horizontal;
	private static int vertical;
    private int w;
    private int h;
    private int l;

    public void init() {
        horizontal = 640;
        vertical = 400;
        w = 1;
        h = 1;
        l = 1;
        n = null;
        tn = null;

    	Container c = getContentPane();
		c.setBackground(Color.black);

		horizontal = (int) Math.pow(w , h) * y_scale;
		vertical = (h) * x_scale + l * 20;

		if(horizontal<800)
			horizontal = 800;

		if(vertical<600)
			vertical = 600;

        JPanel p;
        c.add("Center", p = new JPanel());
        p.setBackground(Color.black);
        p.setLayout(new BorderLayout(1, 1));
        p.setSize(640, 480);

		cp1 = new JScrollBar(JScrollBar.HORIZONTAL, 0, 1, 0 , horizontal);
		cp1.addAdjustmentListener(this);
		p.add(cp1,BorderLayout.SOUTH);

		cp2 = new JScrollBar(JScrollBar.VERTICAL, 0, 1, 0 , vertical);
		cp2.addAdjustmentListener(this);
		p.add(cp2,BorderLayout.EAST);

		jp = new drawPannel(tn, n, (h) * x_scale + l);
		jp.setBackground(Color.black);
		jp.setSize(horizontal, vertical);
		p.add(jp, BorderLayout.CENTER);

        fr = new inputFrame(this);
        fr.show();
    }

    protected void AssignValue(int index) {
        drawValues dv = (drawValues)stateList.get(index - 1);
        TreeNode pvttn = dv.getTreeNode();
        Node pvtn = dv.getNode();
        int pvtw = dv.getw();
        int pvth = dv.geth();
        int pvtl = dv.getl();

		horizontal = (int) Math.pow(pvtw , pvth) * y_scale;
		vertical = (pvth) * x_scale + l * 20;
		if(horizontal<800)
			horizontal = 800;

		if(vertical<600)
			vertical = 600;

		l = pvtl;

        cp1.setMaximum(horizontal);
        cp2.setMaximum(vertical);
        jp.setSize(horizontal, vertical);
        jp.rebuild(pvttn, pvtn, (pvth) * x_scale + l);
        jp.repaint();
        jp.updateUI();
    }

	public void adjustmentValueChanged(AdjustmentEvent e) {
		JScrollBar sb = (JScrollBar)e.getSource();
		if(sb==cp2) {
			jp.setLocation(0 - cp1.getValue(), 0 - cp2.getValue());
			jp.setCursor(cp1.getValue(), cp2.getValue());
			jp.repaint();
			jp.updateUI();
		} else if(sb==cp1) {
			jp.setLocation(0 -cp1.getValue(), 0 - cp2.getValue());
			jp.setCursor(cp1.getValue(), cp2.getValue());
			jp.repaint();
			jp.updateUI();
		}
    }


    public void start() {
        if(fr != null) {
	        fr.show();
    	}
    }

    public void stop() {
        if (fr != null) {
            fr.hide();
        }
    }

    public void destroy() {
        if (fr != null) {
            fr.dispose();
            fr = null;
        }
    }


    private static class inputFrame extends JFrame implements ActionListener {
        JTextField tf;
        JButton cmb;
        JButton ns;
        JButton ps;
        SuffixTree tst;
        
        inputFrame(SuffixTree st) {
            tst = st;
        	setTitle("control panel");

        	Container c = getContentPane();
    		c.setBackground(Color.black);

    	    JPanel p;
        	c.add("North", p = new JPanel());
    	    p.add(new JLabel("input string:"));
        	p.add(tf = new JTextField("", 25));
    	    tf.setEditable(true);

	        p.add(cmb = new JButton("Compute"));
	        cmb.addActionListener(this);
    	    p.add(ns = new JButton("Next Step"));
    	    ns.addActionListener(this);
    	    p.add(ps = new JButton("Previous Step"));
    	    ps.addActionListener(this);
    	    ns.setEnabled(false);
    	    ps.setEnabled(false);
    	    pack();
        }

        public void actionPerformed(ActionEvent e) {
            if(e.getSource()==cmb) {
                if(tf.getText().length()==0) {
                    ns.setEnabled(false);
                    ps.setEnabled(false);
                    stateindex = 0;
                    return;
                } else if(compute()) {
                    treenodeid = 0;
                    if(stateList.size()>1) {
                        ns.setEnabled(true);
                    }
                    ps.setEnabled(false);
                    stateindex = 1;
                    tst.AssignValue(stateindex);
                    return;
                } else {
                    ns.setEnabled(false);
                    ps.setEnabled(false);
                    stateindex = 0;
                    return;
                }
            } else if(e.getSource()==ns) {
                stateindex++;
                tst.AssignValue(stateindex);

                if(stateindex>1&&stateList.size()>1) {
                    ps.setEnabled(true);
                } else {
                    ps.setEnabled(false);
                }

                if(stateList.size()<=stateindex) {
                    ns.setEnabled(false);
                }
            } else if(e.getSource()==ps) {
                stateindex--;
                tst.AssignValue(stateindex);

                if(stateList.size()<=stateindex) {
                    ns.setEnabled(false);
                } else {
                    ns.setEnabled(true);
                }

                if(1>=stateindex) {
                    ps.setEnabled(false);
                }
            }
        }

        private boolean compute() {
            stateList = new ArrayList();
			gbranching = true;

		    String inputStr;	// the input string
		    inputStr = tf.getText();

	    	FirstNodePointer fnp =  new FirstNodePointer();
    		Node CurrentNode = fnp.getNode();

		    int x = 0;
	    	int y = 0;
    		int count = 0;

		    do {
	    		count++;

    			if(gbranching) {
			    	y++;
		    	} else {
	    			x++;
    			}

			    if (y > x) {
		    		x = y;
	    		}
    			if (x==inputStr.length() + 1)
			        break;

		    	CurrentNode = CurrentNode.iterate(x - 1, inputStr);
	    		//draw out
    			ArrayList al;
			    al = preprocessing(fnp.getNode(), 0);
	    		Node cNode = fnp.getNode();
		    	TreeNode ctNode = CopyNodes(cNode, al, CurrentNode);
    			drawingNodes(ctNode, al, count, CurrentNode);

	    	} while (x<inputStr.length()||y<inputStr.length());

            if(stateList.size()>0)
                return true;
            else
                return false;
        }

	    private static TreeNode CopyNodes(Node n, ArrayList al, Node cn) {
		    Integer aobj = (Integer) al.get(0);
    		Integer bobj = (Integer) al.get(1);
	    	int w = aobj.intValue();
		    int h = bobj.intValue();
    		int x, y, midx, midy;
	    	int level = 1;
		    ArrayList nl = new ArrayList();
    		ArrayList tnl = new ArrayList();

		    TreeNode ctNode = new TreeNode(true, ini_x + (x_scale / 2) * (int) Math.pow(w, h), ini_y, n.getID());
	    	nl.add(n);
    		tnl.add(ctNode);

		    int x_whole = (x_scale) * (int) Math.pow(w, h);
	    	int nos = w * (int)Math.pow(w, level - 1);
    		int x_level = x_whole / (nos + 1);

	    	level++;
    		for(int j = 0; j < n.getEdgesLength(); j++) {
		    	x = ini_x + (x_scale / 2) * (int) Math.pow(w, h) - (x_level * (w - 1) / 2) + j * x_level;
	    		y = ini_y + y_scale;

    			midx = (x + ini_x + x_scale / 2 * (int)Math.pow(w ,h)) / 2;
			    midy = (y + ini_y) / 2;

		    	TreeLink te = ctNode.AddLink(n.getEdge(j));
	    		TreeNode tn = te.AddTreeNode(n.getEdge(j).getNode(true), x, y);
    			if(n.getEdge(j).getNode(false)!=null) {
			    	te.AddTreeNode(n.getEdge(j).getNode(false), midx, midy);
		    	}
	    		rCopyNodes(tn, n.getEdge(j).getNode(true), x, y, nl, tnl, w, h, level);
    		}
		    for(int i = 0; i < nl.size(); i++) {
	    		Node cursorNode = (Node) nl.get(i);
    			if(cursorNode.QuickCacheNode()!=null) {
			    	for (int j = 0; j < nl.size(); j++) {
		    			Node judgeNode = (Node) nl.get(j);
	    				if(cursorNode.QuickCacheNode().getID()==judgeNode.getID()) {
    						TreeNode cursorTreeNode = (TreeNode) tnl.get(i);
						    TreeNode judgeTreeNode = (TreeNode) tnl.get(j);
					    	cursorTreeNode.setqXY(judgeTreeNode.x(),judgeTreeNode.y());
				    	}
			    	}
		    	}
	    	}

    		for (int i = 0; i < ctNode.getEdgesLength(); i++) {
			    recDraw(ctNode.getTreeLink(i).getTreeNode(true));
		    }
	    	return ctNode;
    	}
	    private static void recDraw(TreeNode ctNode) {
    		for (int i = 0; i < ctNode.getEdgesLength(); i++) {
		    	recDraw(ctNode.getTreeLink(i).getTreeNode(true));
	    	}
    	}
	    private static void rCopyNodes(TreeNode ctn, Node n, int ix, int iy, ArrayList nl, ArrayList tnl, int w, int h, int level) {
    		int x, y, midx, midy;
		    nl.add(n);
	    	tnl.add(ctn);

    		int x_whole = (x_scale) * (int)Math.pow(w, h);
		    int nos = w * (int)Math.pow(w, level - 1);
	    	int x_level = x_whole / (nos + 1);

    		level++;

    		for(int j = 0; j < n.getEdgesLength(); j++) {
			    x = ix - (x_level * (w - 1) / 2) + j * x_level;
		    	y = iy + y_scale;

	    		midx = (x + ix) / 2;
    			midy = (y + iy) / 2;

    			TreeLink te = ctn.AddLink(n.getEdge(j));
			    TreeNode tn = te.AddTreeNode(n.getEdge(j).getNode(true), x, y);
		    	if(n.getEdge(j).getNode(false)!=null) {
	    			te.AddTreeNode(n.getEdge(j).getNode(false), midx, midy);
    			}
			    rCopyNodes(tn, n.getEdge(j).getNode(true), x, y, nl, tnl, w, h, level);
		    }
	    }

    	private static ArrayList preprocessing(Node n, int ht) {
	    	ArrayList al = new ArrayList();
    		int max_w = 0;
		    int max_h = 0;
	    	int line_count = n.getEdgesLength();
    		max_w = n.getEdgesLength();
		    max_h = ht;
	    	ht++;
    		Integer tm_w;
		    Integer tm_h;
	    	Integer tm_l;

    		for(int j = 0; j < n.getEdgesLength(); j++ ) {
			    ArrayList alt = preprocessing(n.getNode(j, true), ht);
		    	tm_w = (Integer) alt.get(0);
	    		tm_h = (Integer) alt.get(1);
    			tm_l = (Integer) alt.get(2);
			    if(max_w<tm_w.intValue()) {
		    		max_w = tm_w.intValue();
	    		}
    			if(max_h<tm_h.intValue()) {
			    	max_h = tm_h.intValue();
		    	}
	    		line_count = line_count + tm_l.intValue();
    		}

		    Integer a = new Integer(max_w);
	    	Integer b = new Integer(max_h);
    		Integer c = new Integer(line_count);
		    al.add(a);
	    	al.add(b);
    		al.add(c);
		    return al;
	    }
    	private static void drawingNodes(TreeNode tn, ArrayList al, int no, Node n){
		    Integer aobj = (Integer) al.get(0);
	    	Integer bobj = (Integer) al.get(1);
    		Integer cobj = (Integer) al.get(2);
		    int w = aobj.intValue();
	    	int h = bobj.intValue();
    		int l = cobj.intValue();

            drawValues dv = new drawValues(tn, w, h, l, n);
            stateList.add(dv);
    	}
    }

    private static class drawValues {
        private TreeNode pvttn;
        private int pvtw;
        private int pvth;
        private int pvtl;
        private Node pvtn;
        drawValues(TreeNode tn, int w, int h, int l, Node n) {
            pvttn = tn;
            pvtw = w;
            pvth = h;
            pvtl = l;
            pvtn = n;
        }
        protected TreeNode getTreeNode() {
            return pvttn;
        }
        protected int getw() {
            return pvtw;
        }
        protected int geth() {
            return pvth;
        }
        protected int getl() {
            return pvtl;
        }
        protected Node getNode() {
            return pvtn;
        }
    }

	private static class drawPannel extends JPanel {
		private Node n;
		private TreeNode tn;
		private static int id;
		private int cid;
		private int ini_x;
		private int ini_y;
		private int ini_sp;
		private int string_count;

		drawPannel(TreeNode ctn, Node cn, int sp) {
			id++;
			cid = id;
			n = cn;
			tn = ctn;
			ini_x = 0;
			ini_y = 0;
			ini_sp = sp;
			string_count = 0;
		}
		protected void rebuild(TreeNode ctn, Node cn, int sp) {
			n = cn;
			tn = ctn;
			ini_x = 0;
			ini_y = 0;
			ini_sp = sp;
			string_count = 0;
		}
		public void paint(Graphics g) {
		    if(tn==null||n==null) {
		        g.setFont(new Font("", Font.BOLD, 24));
		        g.drawString("Welcome!!!", 40, 40);
		        g.drawString("Input string in upper frame!!!", 40, 70);
            }
            else {
			    drawNode(g, tn, n, -1, -1, -1, -1, -1, -1);
            }
		}
		protected void setCursor(int x, int y) {
			ini_x = -x;
			ini_y = -y;
			string_count = 0;
		}
		private void drawNode(Graphics g, TreeNode ctn, Node cn, int px, int py, int pid, int link_k, int link_s, int link_e) {
			g.setColor(Color.blue);
			g.fillOval(ctn.x() + ini_x, ctn.y() + ini_y, 10, 10);
			g.setColor(Color.white);
			String s = new String();
			g.drawString(s.valueOf(ctn.getID()), ctn.x() - 7 + ini_x, ctn.y() - 2 + ini_y);

			// draw line between itself to parent node
			if(px!=-1) {
				g.setColor(Color.yellow);
				g.drawLine(ctn.x() + 5 + ini_x, ctn.y() + ini_y, px + 5 + ini_x, py + 10 + ini_y);
				g.setColor(Color.white);
				String sd = new String();
				sd = "link between node:" + pid + " and node:" + ctn.getID() + " have key:" + link_k + " and label [" + link_s + "," + link_e + "]";
				g.drawString(sd, 20 + ini_x, ini_sp + ini_y + 100 + 20 * string_count);
				string_count++;
			}

			// draw current node with red ring
			if(cn.getID()==ctn.getID()) {
				g.setColor(Color.red);
				g.drawOval(ctn.x() - 2 + ini_x, ctn.y() - 2 + ini_y, 12, 12);
			}

			// draw the cache node link with a arrow
			if(ctn.qx()!=-1) {
				g.setColor(Color.green);
				g.drawLine(ctn.x() + ini_x, ctn.y() + ini_y, ctn.qx() + ini_x, ctn.qy() + ini_y);
				g.fillRect(ctn.qx() + ini_x, ctn.qy() + ini_y - 5, 5, 5);
			}

			for(int j = 0 ; j < ctn.getEdgesLength(); j++) {
				drawNode(g, ctn.getTreeLink(j).getTreeNode(true), cn, ctn.x(), ctn.y(), ctn.getID(), ctn.getTreeLink(j).kValue(), ctn.getTreeLink(j).sindex(), ctn.getTreeLink(j).eindex());
				if(ctn.getTreeLink(j).getTreeNode(false)!=null) {
					drawImpNode(g, ctn.getTreeLink(j).getTreeNode(false), cn, ctn.x(), ctn.y());
				}
			}
		}
		private void drawImpNode(Graphics g, TreeNode ctn, Node cn, int px, int py) {
			g.setColor(Color.cyan);
			g.fillOval(ctn.x() + ini_x, ctn.y() + ini_y, 10, 10);
			g.setColor(Color.white);
			String s = new String();
			g.drawString(s.valueOf(ctn.getID()), ctn.x() - 7 + ini_x, ctn.y() - 2 + ini_y);

			if(cn.getID()==ctn.getID()) {
				g.setColor(Color.red);
				g.drawOval(ctn.x() - 2 + ini_x, ctn.y() - 2 + ini_y, 12, 12);
			}
		}
	}

	private static class FirstNodePointer {
		private Node fn;
		FirstNodePointer() {
			fn = new Node();
		}
		public Node getNode() {
			return fn;
		}
		public int getNodeID() {
			return fn.getID();
		}
	}

    private static class Node {
    	private int cid;
    	private ArrayList elist;
    	private boolean nodetype;
    	private Node qcNode;
    	private Edge parentEdge;
    	private boolean isbranching;

    	Node(boolean nt) {
    		treenodeid++;
    		cid = treenodeid;
			elist = new ArrayList();
			nodetype = nt;
			qcNode = null;
			parentEdge = null;
			isbranching = true;
    	}

    	Node() {
    		treenodeid++;
    		cid = treenodeid;
			elist = new ArrayList();
			nodetype = true;
			qcNode = null;
			parentEdge = null;
			isbranching = true;
    	}
    	// get node id
    	public int getID() {
    		return cid;
    	}
    	public Node iterate(int index, String str) {
    		// get the match Node
    		Node retNode = null;
    		boolean isfound = false;
    		int comp;
    		int foundindex = 0;

			if(nodetype) {
	    		for(int i = 0; i < elist.size(); i++) {
    				Edge e = (Edge) elist.get(i);
					comp = e.StartIndex() + e.k();
    				if(str.charAt(index)==str.charAt(comp - 1)) {
						isfound = true;
						foundindex = i;
	    				break;
    				}
    			}
    		} else {
    			comp = parentEdge.StartIndex() + parentEdge.k();
				if(str.charAt(index)==str.charAt(comp - 1)) {
					isfound = true;
				}
    		}
    		// branching node
    		if(!isfound) {
    			isbranching = true;
    			gbranching = true;
    			if(nodetype) {
    				this.AddNode(index + 1, -1);
    				retNode = this;
    			} else {
    				this.SplitNode(index + 1, -1);
    			}
    			// try to find parent branching node
    			Edge pe = parentEdge;

    			if(!(pe==null)) {
    				int uplinklen = pe.EndIndex() - pe.StartIndex() + 1;
    				Node pn = pe.ParentNode();
					Node loopNode = pn.QuickCacheNode();

					if(loopNode==pn) {
					    if(uplinklen==1) {
    						qcNode = pn;
	    					retNode = loopNode;
	    				} else {
    						retNode = gotoNode(uplinklen - 1, loopNode, index - 1, str);
	    					qcNode = retNode;
	    				}
					} else {
						retNode = gotoNode(uplinklen, loopNode, index - 1, str);
						qcNode = retNode;
					}
    			} else {
    				qcNode = this;
    				retNode = this;
    			}
    		//add implicit node
    		} else {
    			
    			isbranching = false;
    			gbranching = false;
    			if(nodetype) {
	    			Node tNode = getNode(foundindex);
    				if(tNode.getEdgesLength()==0) {
    					Node impn = AddNode(foundindex);
    					retNode = impn;
    				} else if (tNode.parentEdge.StartIndex() < tNode.parentEdge.EndIndex()) {
    					Node impn = AddNode(foundindex);
    					retNode = impn;
    				} else {
    					retNode = tNode;
	    			}
	    		} else {
	    			if(parentEdge.k() + 1 == (parentEdge.EndIndex() - parentEdge.StartIndex() + 1)) {
	    				parentEdge.deleteNode(false);
						retNode = parentEdge.getNode(true);
	    			} else {
	    				parentEdge.k(parentEdge.k() + 1);
	    				retNode = this;
	    			}
	    		}    				
    		}
    		return retNode;
    	}
    	// goto Node from some given Node
    	private Node gotoNode(int downloadlen, Node startNode, int index, String str) {
    		Node tmpNode = startNode;

    		tmpNode = startNode.move(str, index - downloadlen + 1, downloadlen, index + 1);
    		return tmpNode;
    	}
    	private Node move(String str, int curi, int len, int cursorindex) {
			Node tmpNode = null;
			int comp;
			boolean isfound = false;

    		for(int i = 0; i < elist.size(); i++) {
    			Edge e = (Edge) elist.get(i);
				int si = e.StartIndex();
				int ei = e.EndIndex();

    			if(str.charAt(curi)==str.charAt(si - 1)) {
    				isfound = true;
    				if(ei == -1) {
    					for(int k = 0; k < len; k++)
    						tmpNode = AddNode(i);
    				} else if(len >= (ei - si + 1)) {
    					comp = ei - si + 1;
    					Node curNode = e.getNode(true);
    					if(len - comp > 0)
    					    tmpNode = curNode.move(str, curi + comp, len - comp, cursorindex);
                        else
                            tmpNode = curNode;
					} else {
					    for(int k = 0; k < len; k++)
						    tmpNode = AddNode(i);
					}
    				break;
    			}
    		}
    		if(!isfound) {
    			tmpNode = AddNode(cursorindex + 1, -1);
    		}
    		return tmpNode;
    	} 
    	// split Node
    	private Node SplitNode(int csi, int cei) {
			int si;
			int ei;
			int pei;

    		// get the parent Edge
    		Edge pe = this.ParentEdge();
    		Node pn = pe.ParentNode();
    		Node expn = pe.getNode(true);

			// attch this node to its parent
			si = pe.StartIndex();
			pei = pe.EndIndex();
			ei = pe.k() + si - 1;
			pn.AttachNode(this, true, si, ei);

			// add two branching node
			this.AddNode(csi, cei);
			si = pe.StartIndex() + pe.k();
			ei = pei;
			this.AttachNode(expn, true, si, ei);

    		// delete original edge
    		pn.DeleteEdge(pe);

			return this;
    	}
    	// add an implicit node with edge
    	private Node AddNode(int index) {
			Edge e = (Edge) elist.get(index);
			// only add 1 to k value each time
			e.k(e.k() + 1);
			Node n = e.getNode(false);

			if(n==null)
				n = e.AddNode(false);

    		return n;
    	}
    	// add an explicit node with edge
    	private Node AddNode(int si, int ei) {
    		Edge e = new Edge(si, ei, this);
    		elist.add(e);
			Node n = e.AddNode(true);

    		return n;
    	}
    	private Node AddNode() {
    		Edge e = new Edge(this);
    		elist.add(e);
			Node n = e.AddNode();

    		return n;
    	}
    	private Node AttachNode(Node n, boolean nType, int si, int ei) {
			Edge e = new Edge(si, ei, this);
			elist.add(e);
			e.AttachNode(n, nType);

    		return n;
    	}
    	private Node AttachNode(Node n, boolean nType) {
			Edge e = new Edge(this);
			elist.add(e);
			e.AttachNode(n, nType);

    		return n;
    	}
    	public Node getNode(int i) {
    		Edge e = (Edge) elist.get(i);
    		Node n = (Node) e.getNode();
    		return n;
    	}
    	public Node getNode(int i, boolean nType) {
    		Edge e = (Edge) elist.get(i);
    		Node n = e.getNode(nType);
    		return n;
    	}
    	// get edge
    	public Edge getEdge(int i) {
    		Edge e = (Edge) elist.get(i);
    		return e;
    	}
    	public int getEdgesLength() {
    		return elist.size();
    	}
    	protected void ParentEdge(Edge edge) {
    		parentEdge = edge;
    	}
    	public Edge ParentEdge() {
    		return parentEdge;
    	}
    	public void DeleteEdge(Edge e) {
    		elist.remove(elist.indexOf(e));
    	}
    	// to set or Suffix Link
    	public void QuickCacheNode(Node n) {
    		qcNode = n;
    	}
    	public Node QuickCacheNode() {
    		return qcNode;
    	}
    	// to set or reterive the node-type implicit or explicit
    	public void NodeType(boolean ntype) {
    		nodetype = ntype;	//true. explicit node	false. implicit node
    	}
    	public boolean NodeType() {
    		return nodetype;
    	}
    	public boolean IsBranching() {
    		return isbranching;
    	}
    }
    private static class Edge {
    	private static int id;
    	private int eid;
    	private Node parentNode;
    	private Node ImplicitNode;
    	private Node ExplicitNode;
    	private int pvtK;
    	private int pvtStartIndex;
    	private int pvtEndIndex;    	

    	Edge(int si, int ei, Node pN) {
    		id++;
    		eid = id;
    		parentNode = pN;
    		ImplicitNode = null;
    		ExplicitNode = null;    		
    		pvtK = 0;
    		pvtStartIndex = si;
    		pvtEndIndex = ei;
    	}

    	Edge(Node pN) {
    		id++;
    		eid = id;
    		parentNode = pN;
    		ImplicitNode = null;
    		ExplicitNode = null;
    		pvtK = 0;
    		pvtStartIndex = 0;
    		pvtEndIndex = -1;
    	}
    	public int getID() {
    		return eid;
    	}
    	public Node ParentNode() {
    		return parentNode;
    	}
    	protected void ParentNode(Node pN) {
    		parentNode = pN;
    	}
		public Node AddNode() {
			Node n = new Node();
			ExplicitNode = n;
			n.NodeType(true);
			n.ParentEdge(this);
			return n;
		}
		public Node AddNode(boolean nType) {
			Node n = new Node();
			if(nType)
				ExplicitNode = n;
			else
				ImplicitNode = n;
			n.NodeType(nType);
			n.ParentEdge(this);
			return n;
		}
		public Node AttachNode(Node n, boolean nType) {
			if(nType) {
				ExplicitNode = n;
			} else {
				ImplicitNode = n;
			}
			n.NodeType(nType);
			n.ParentEdge(this);
			return n;
		}
		public Node getNode() {
			return ExplicitNode;
		}
		public Node getNode(boolean nType) {
			if(nType)
				return ExplicitNode;
			else
				return ImplicitNode;
		}
		public void deleteNode(boolean nType) {
			if(nType)
				ExplicitNode = null;
			else
				ImplicitNode = null;
		}
		protected void k(int inK) {
			pvtK = inK;
		}
		public int k() {
			return pvtK;
		}
		public void StartIndex(int si) {
			pvtStartIndex = si;
		}
		public int StartIndex() {
			return pvtStartIndex;
		}
		public void EndIndex(int ei) {
			pvtEndIndex = ei;
		}
		public int EndIndex() {
			return pvtEndIndex;
		}
    }

    public static class TreeNode {
    	int pvtx;
    	int pvty;
    	int pvtid;
    	boolean pvtNodeType;

		int pvtqx;
		int pvtqy;
    	
    	ArrayList al;

		TreeNode(boolean nt, int x, int y, int id) {
			pvtNodeType = nt;
			pvtx = x;
			pvty = y;
			pvtqx = -1;
			pvtqy = -1;
			pvtid = id;
			al = new ArrayList();
		}

		public TreeLink AddLink(Edge e) {
			TreeLink tl = new TreeLink(e.k(), e.StartIndex(), e.EndIndex(), e.getID());
			al.add(tl);
			return tl;
		}

		protected void setqXY(int x, int y) {
			pvtqx = x;
			pvtqy = y;
		}
		public int qy() {
			return pvtqy;
		}
		public int qx() {
			return pvtqx;
		}
		public int y() {
			return pvty;
		}
    	public int x() {
    		return pvtx;
    	}
    	public int getID() {
    		return pvtid;
    	}
    	public TreeLink getTreeLink(int i) {
    		TreeLink tl = (TreeLink) al.get(i);
    		return tl;
    	}
    	public int getEdgesLength() {
    		return al.size();
    	}
    }
    public static class TreeLink {
    	int pvtk;
    	int pvtsi;
    	int pvtei;
		TreeNode pvtEn;
		TreeNode pvtIn;
		int pvtid;

    	TreeLink(int k, int si, int ei, int id) {
    		pvtk = k;
    		pvtsi = si;
    		pvtei = ei;
    		pvtid = id;
    	}
    	public TreeNode AddTreeNode(Node n, int x, int y) {
    		TreeNode tn = null;
    		if(n.NodeType()) {
    			tn = new TreeNode(n.NodeType(), x, y, n.getID());
    			pvtEn = tn;
    		} else {
    			tn = new TreeNode(n.NodeType(), x, y, n.getID());
    			pvtIn = tn;
    		}
    		return tn;
    	}
    	public TreeNode getTreeNode(boolean nt) {
    		TreeNode retTreeNode;
    		if(nt) {
    			retTreeNode = pvtEn;
    		} else {
    			retTreeNode = pvtIn;
    		}
    		return retTreeNode;
    	}
    	public int kValue() {
    		return pvtk;
    	}
    	public int sindex() {
    		return pvtsi;
    	}
    	public int eindex() {
    		return pvtei;
    	}
    }
}