optmatmult.java

java算法大全

	    DimIndicator d = new DimIndicator((p2.getX()+p2.getRight())/2,
		p2.getY() + 2, p2.getX(), p2.getRight(),
		"cost["+(c_index+1)+","+right+"]",
		drawingPanel.getFixFont());
	    drawingPanel.addDrawingObj(d);
	    drawingPanel.repaint(); drawingPanel.delay();

	    fb2 = new FloatingBox(""+cost.elem(c_index+1, right),
		drawingPanel.getFixFont());
	    Point p = cost.getPosn(c_index+1, right);
	    fb2.move(p.x, p.y);
	    drawingPanel.addDrawingObj(fb2);
	    drawingPanel.repaint(); drawingPanel.delay(); drawingPanel.delay();
	    Vector traj = new Vector();
	    traj.addElement(new Point(fb2.getX(), fb2.getY()));
	    traj.addElement(new Point(d.getX()-32, fb2.getY()));
	    traj.addElement(new Point(d.getX()-32, d.getY()+15));
	    drawingPanel.animate(fb2, traj);
	    frame.waitStep();

	    drawingPanel.repaint(); drawingPanel.delay();
	    drawingPanel.removeObj(d);
	    traj = new Vector();
	    traj.addElement(new Point(fb2.getX(), fb2.getY()));
	    traj.addElement(new Point(p2.getRight() + 50, fb2.getY()));
	    drawingPanel.animate(fb2, traj);
	    tmpR.move(fb2.getX(), p2.getY());
	    drawingPanel.addDrawingObj(tmpR);
	    drawingPanel.repaint(); drawingPanel.delay();
	}

	DimIndicator d1 = new DimIndicator((p1.getX()+p1.getRight())/2,
		p1.getY() + 2, p1.getX(), p1.getRight(),
		""+ dims[left].height + "x" + dims[c_index].width,
		drawingPanel.getFixFont());
	drawingPanel.addDrawingObj(d1);
	drawingPanel.repaint(); drawingPanel.delay();
	frame.waitStep();

	drawingPanel.removeObj(d1);
	d1 = new DimIndicator((p2.getX()+p2.getRight())/2,
		p2.getY() + 2, p2.getX(), p2.getRight(),
		"" + dims[c_index+1].height + "x" + dims[right].width,
		drawingPanel.getFixFont());
	drawingPanel.addDrawingObj(d1);
	drawingPanel.repaint(); drawingPanel.delay();
	frame.waitStep();

	drawingPanel.removeObj(d1);
	com.setText("Cost = " + dims[left].height + "x" + 
		dims[c_index+1].height + "x" + dims[right].width + " = " +
		(dims[left].height*dims[c_index+1].height*dims[right].width));
	drawingPanel.repaint(); drawingPanel.delay();

	FloatingBox box = new FloatingBox(""+
		(dims[left].height*dims[c_index+1].height*dims[right].width),
		drawingPanel.getFixFont());
	box.move(p1.getX(), p2.getY() + 17);
	drawingPanel.addDrawingObj(box);
	drawingPanel.repaint();drawingPanel.delay();
	frame.waitStep();

	com.setText("Adding to form total cost...");
	drawingPanel.repaint();drawingPanel.delay();
	Vector traj0 = new Vector(), traj1 = new Vector(), 
	    traj2 = new Vector();
	int numAnim = 1;
	traj0.addElement(new Point(box.getX(), box.getY()));
	traj0.addElement(new Point(p2.getRight() + 10, box.getY()));
	traj0.addElement(new Point(p2.getRight() + 10, 
			p2.getY() - 13));
	drawingPanel.setAnimStep(5);
	if (fb1 != null) {
	    numAnim++;
	    traj1.addElement(new Point(fb1.getX(), fb1.getY()));
	    traj1.addElement(new Point(p2.getRight() + 10, fb1.getY()));
	    traj1.addElement(new Point(p2.getRight() + 10, 
			p2.getY() - 13));
	}
	if (fb2 != null) {
	    numAnim++;
	    traj2.addElement(new Point(fb2.getX(), fb2.getY()));
	    traj2.addElement(new Point(p2.getRight() + 10, fb2.getY()));
	    traj2.addElement(new Point(p2.getRight() + 10, 
			p2.getY() - 13));
	}
	DrawingObj[] animObjs = new DrawingObj[numAnim];
	Vector[] trajs = new Vector[numAnim];
	animObjs[0] = box; trajs[0] = traj0;
	int count = 1;
	if (fb1 != null) {
	    animObjs[count] = fb1;
	    trajs[count++] = traj1;
	}
	if (fb2 != null) {
	    animObjs[count] = fb2;
	    trajs[count++] = traj2;
	}
	drawingPanel.removeObj(tmpL);
	drawingPanel.removeObj(tmpR);
	drawingPanel.animate(animObjs, trajs);

	box.setText("" +
		(dims[left].height * dims[c_index].width * dims[right].width +
		 CostSubTree(left, c_index) + CostSubTree(c_index+1, right)));
	drawingPanel.removeObj(fb1);
	drawingPanel.removeObj(fb2);
	drawingPanel.repaint(); drawingPanel.delay();
	frame.waitStep();
	drawingPanel.removeCom(com);
	objs[0] = p1; objs[1] = p2; objs[2] = box;
	return objs;
    } // animateCost()

    private DrawingObj[] animateBest(DrawingObj[] objs, DrawingObj[] bestObjs) {
	ComBox com = new ComBox(30+3*66, 135,
		"This parenthesisation gives the best cost so far...",
		drawingPanel.getFixFont());
	drawingPanel.addCom(com);
	drawingPanel.repaint(); drawingPanel.delay();

	if (bestObjs != null) {
	    ComBox com2 = new ComBox(30+3*66+10, 145,
		"Remove previous best..", drawingPanel.getFixFont());
	    drawingPanel.addCom(com2);
	    drawingPanel.repaint(); drawingPanel.delay();
	    for (int k = 0; k < 5; k++) {
	        for (int i = 0; i < bestObjs.length; i++)
		    drawingPanel.removeObj(bestObjs[i]);
	        drawingPanel.repaint(); drawingPanel.delay();
	        for (int i = 0; i < bestObjs.length; i++)
		    drawingPanel.addDrawingObj(bestObjs[i]);
	        drawingPanel.repaint(); drawingPanel.delay();
	    }
	    for (int i = 0; i < bestObjs.length; i++)
		drawingPanel.removeObj(bestObjs[i]);
	    drawingPanel.removeCom(com2);
	    drawingPanel.repaint(); drawingPanel.delay();
	}
	Vector traj1 = new Vector(), traj2 = new Vector(), traj3 = new Vector();
	traj1.addElement(new Point(objs[0].getX(), objs[0].getY()));
	traj2.addElement(new Point(objs[1].getX(), objs[1].getY()));
	traj3.addElement(new Point(objs[2].getX(), objs[2].getY()));
	int dx = 30+3*66 - objs[0].getX();
	traj1.addElement(new Point(objs[0].getX() + dx, objs[0].getY()));
	traj2.addElement(new Point(objs[1].getX() + dx, objs[1].getY()));
	traj3.addElement(new Point(objs[2].getX() + dx, objs[2].getY()));
	Vector[] trajs = new Vector[3];
	trajs[0] = traj1; trajs[1] = traj2; trajs[2] = traj3;
	drawingPanel.animate(objs, trajs);

	drawingPanel.removeCom(com);
	bestObjs = objs;
	frame.waitStep();
	return bestObjs;
    } // animateBest()

    private void animateRemoveObjs(DrawingObj[] objs) {
	ComBox com = new ComBox(objs[0].getX(), objs[0].getY() + 20,
		"Higher cost.. Dispose!", drawingPanel.getFixFont());
	drawingPanel.addCom(com);
	drawingPanel.repaint(); drawingPanel.delay();

	Vector traj1 = new Vector(), traj2 = new Vector(), traj3 = new Vector();
	traj1.addElement(new Point(objs[0].getX(), objs[0].getY()));
	traj2.addElement(new Point(objs[1].getX(), objs[1].getY()));
	traj3.addElement(new Point(objs[2].getX(), objs[2].getY()));
	int dx = 700;
	traj1.addElement(new Point(objs[0].getX() + dx, objs[0].getY()));
	traj2.addElement(new Point(objs[1].getX() + dx, objs[1].getY()));
	traj3.addElement(new Point(objs[2].getX() + dx, objs[2].getY()));
	Vector[] trajs = new Vector[3];
	trajs[0] = traj1; trajs[1] = traj2; trajs[2] = traj3;
	drawingPanel.setAnimStep(10);
	drawingPanel.animate(objs, trajs);
	drawingPanel.setAnimStep(5);

	drawingPanel.removeCom(com);
	for (int i = 0; i < objs.length; i++)
	    drawingPanel.removeObj(objs[i]); 
    } // animateRemoveObjs()

    private void animateStoreInMat(DrawingObj[] bestObjs, int left, int right,
		int bestIndex) {
	ComBox com = new ComBox(30+3*66, 135,
		"Moving optimal cost to cost matrix...",
		drawingPanel.getFixFont());
	drawingPanel.addCom(com);
	drawingPanel.repaint(); drawingPanel.delay();
	com.setText("Cost for matrix multiplication of A"+left+" to A"+right+
	    " is stored in matrix at column = "+left+ " and row = "+right);
	com.move(20, 60);
	drawingPanel.repaint(); drawingPanel.delay();
	Vector traj = new Vector();
	traj.addElement(new Point(bestObjs[2].getX(), bestObjs[2].getY()));
	traj.addElement(new Point(bestObjs[2].getX(), 
			cost.getPosn(left, right).y));
	traj.addElement(new Point(
		cost.getPosn(left, right).x, cost.getPosn(left, right).y));
	drawingPanel.setAnimStep(10);
	drawingPanel.animate(bestObjs[2], traj);
	frame.waitStep();

	Parenthesis p1 = (Parenthesis)bestObjs[0];
	DimIndicator d = new DimIndicator((p1.getRight() - 7),
		p1.getY() + 2, p1.getRight() - 14, p1.getRight(),
		""+bestIndex, drawingPanel.getFixFont());
	drawingPanel.addDrawingObj(d);
	com.setText("The index of the last matrix in the left sub-product is" +
	    " going to the same position of the best matrix.");
	com.move(20, 60);
	drawingPanel.repaint(); drawingPanel.delay();
	frame.waitStep();
	drawingPanel.removeObj(d);
	FloatingBox fb = new FloatingBox("" + bestIndex, 
		drawingPanel.getFixFont());
	fb.move(d.getX()-32, d.getY() + 15);
	drawingPanel.addDrawingObj(fb);
	Point p = best.getPosn(left, right);
	traj = new Vector();
	traj.addElement(new Point(fb.getX(), fb.getY()));
	traj.addElement(new Point(fb.getX(), p.y));
	traj.addElement(new Point(p.x, p.y));
	drawingPanel.animate(fb, traj);
	
	drawingPanel.removeObj(fb);
	drawingPanel.removeCom(com);
	for (int i = 0; i < bestObjs.length; i++)
	    drawingPanel.removeObj(bestObjs[i]);
	drawingPanel.setAnimStep(5);
    } // animateStoreInMat()

    private void formBestParenthesisation() {
	int bestIndex = best.elem(0, n-1);
	best.setHighlight2(0, n-1);
	drawingPanel.repaint(); drawingPanel.delay();
	Parenthesis leftP, rightP;
	if (bestIndex+1 > 2)
	    leftP = formParen(0, bestIndex, Color.blue);
	else {
	    Subscript[] s1 = new Subscript[bestIndex+1];
	    for (int i = 0; i <= bestIndex; i++)
		s1[i] = new Subscript("A", ""+i);
	    leftP = new Parenthesis(s1, drawingPanel.getFixFont());
	}

	if (n - bestIndex - 1 > 2)
	    rightP = formParen(bestIndex+1, n-1, Color.blue);
	else {
	    Subscript[] s2 = new Subscript[n - bestIndex - 1];
	    for (int i = bestIndex + 1; i < n; i++)
		s2[i - bestIndex - 1] = new Subscript("A", ""+i);
	    rightP = new Parenthesis(s2, drawingPanel.getFixFont());
	}
	leftP.move(450, 120);
	rightP.move(leftP.getRight(), 120);
	drawingPanel.addDrawingObj(leftP);
	drawingPanel.addDrawingObj(rightP);
	ShadowLabel result = new ShadowLabel("Best Parenthesisation");
	result.setColor(darkGreen);
	result.move(450, 100);
	drawingPanel.addDrawingObj(result);
	drawingPanel.repaint(); drawingPanel.delay();
	animateFormParen(leftP, rightP);
    }

    private Parenthesis formParen(int left, int right, Color col) {
	Parenthesis result = null;
	int bestIndex = best.elem(left, right);
	best.setHighlight2(left, right);
	drawingPanel.repaint(); drawingPanel.delay();

	Parenthesis leftP, rightP;
	if (bestIndex-left+1 > 2)
	    leftP = formParen(left, bestIndex, darkGreen);
	else {
	    Subscript[] s1 = new Subscript[bestIndex-left+1];
	    for (int i = left; i <= bestIndex; i++)
		s1[i-left] = new Subscript("A", ""+i);
	    leftP = new Parenthesis(s1, drawingPanel.getFixFont());
	}

	if (right - bestIndex > 2)
	    rightP = formParen(bestIndex+1, right, darkGreen);
	else {
	    Subscript[] s2 = new Subscript[right - bestIndex];
	    for (int i = bestIndex + 1; i <= right; i++)
		s2[i - bestIndex - 1] = new Subscript("A", ""+i);
	    rightP = new Parenthesis(s2, drawingPanel.getFixFont());
	}
	
	leftP.setColor(col);
	rightP.setColor(col);
	Parenthesis[] arrayP = new Parenthesis[2];
	arrayP[0] = leftP;
	arrayP[1] = rightP;
	result = new Parenthesis(arrayP, drawingPanel.getFixFont());
	return result;
    }

    private void animateFormParen(Parenthesis left, Parenthesis right) {
	ComBox com = new ComBox(420, 50,
		"This parenthesis is obtained from best matrix...",
		drawingPanel.getFixFont());
	DimIndicator d = new DimIndicator(left.getRight() - 16,
		left.getY() + 2, left.getRight() - 23, left.getRight() - 9,
		"best[0,"+(n-1)+"]", drawingPanel.getFixFont());
	drawingPanel.addDrawingObj(d);
	drawingPanel.addCom(com);
	drawingPanel.repaint(); drawingPanel.delay();
	FloatingBox fb = new FloatingBox(""+best.elem(0,5),
		drawingPanel.getFixFont());
	Point src = best.getPosn(0, 5);
	fb.move(src.x, src.y);
	drawingPanel.addDrawingObj(fb);
	drawingPanel.repaint(); drawingPanel.delay();
	Vector traj = new Vector();
	traj.addElement(new Point(fb.getX(), fb.getY()));
	traj.addElement(new Point(d.getX() - 32, fb.getY()));
	traj.addElement(new Point(d.getX() - 32, d.getY() + 15));
	drawingPanel.animate(fb, traj);
	drawingPanel.removeObj(fb);
	drawingPanel.repaint(); drawingPanel.delay();
	frame.waitStep();
	drawingPanel.removeObj(d);

	left = right.getLeftParen();
	d = new DimIndicator(left.getRight() - 16,
		left.getY() + 2, left.getRight() - 23, left.getRight() - 9,
		"best[2,5]", drawingPanel.getFixFont());
	drawingPanel.addDrawingObj(d);
	drawingPanel.repaint(); drawingPanel.delay();
	fb.setText(""+best.elem(2,5));
	src = best.getPosn(2, 5);
	fb.move(src.x, src.y);
	drawingPanel.addDrawingObj(fb);
	drawingPanel.repaint(); drawingPanel.delay();
	traj = new Vector();
	traj.addElement(new Point(fb.getX(), fb.getY()));
	traj.addElement(new Point(d.getX() - 32, fb.getY()));
	traj.addElement(new Point(d.getX() - 32, d.getY() + 15));
	drawingPanel.animate(fb, traj);
	drawingPanel.removeObj(fb);
	drawingPanel.repaint(); drawingPanel.delay();
	frame.waitStep();
	drawingPanel.removeObj(d);

	left = left.getLeftParen();
	d = new DimIndicator(left.getRight() - 16,
		left.getY() + 2, left.getRight() - 23, left.getRight() - 9,
		"best[2,4]", drawingPanel.getFixFont());
	drawingPanel.addDrawingObj(d);
	drawingPanel.repaint(); drawingPanel.delay();
	fb.setText(""+best.elem(2,4));
	src = best.getPosn(2, 4);
	fb.move(src.x, src.y);
	drawingPanel.addDrawingObj(fb);
	drawingPanel.repaint(); drawingPanel.delay();
	traj = new Vector();
	traj.addElement(new Point(fb.getX(), fb.getY()));
	traj.addElement(new Point(d.getX() - 32, fb.getY()));
	traj.addElement(new Point(d.getX() - 32, d.getY() + 15));
	drawingPanel.animate(fb, traj);
	drawingPanel.removeObj(fb);
	drawingPanel.repaint(); drawingPanel.delay();
	frame.waitStep();
	drawingPanel.removeObj(d);

	drawingPanel.removeCom(com);
    }
} // class OptMatMult