heap.java

java算法大全

	    int destX = destNode.x;
	    int destY = destNode.y;
	    int sourceX = movingNode.x;

	    movingNode.y -= 20; redraw();
	    movingNode.y -= 20; redraw();

	    for (int l = 0; l < 5; l++) {
		movingNode.x += (destX - sourceX)/5;
		arrayNode.x += (newNode.x - sourceX)/5;
	    	redraw();
	    }
	    movingNode.x = destX;
	    arrayNode.x = newNode.x;

	    redraw();

	    int srcY = node.y;
	    for (int k = 0; k < 5; k++) {
		movingNode.y += (destY - srcY)/5;
		redraw();
	    }
	    hideMovingNode();
	    node.x = destX; node.y = destY;
	    insert(node);
	    runningCom = null;
	    redraw();
    }

    public void setHeap(int[] a) {
	if (a.length > posnList.size())
	    calNodesCoord(a.length);
	tree = null;
	nodeList = new Vector();
	for (int i = 0; i < a.length; i++)
	    insert(new Node(a[i]));
    } // setData()

    private void insert(Node node) {
	nodeList.addElement(node);
	if (posnList.size() >= nodeList.size()) {
	    node.x = ((Node)posnList.elementAt(nodeList.size()-1)).x;
	    node.y = ((Node)posnList.elementAt(nodeList.size()-1)).y;
	}
	if (tree == null) {
	    tree = node;
	} else {
	    // locate blank branch to link to this node
	    for (int i = 0; i < nodeList.size()-1; i++) {
		Node n = (Node)nodeList.elementAt(i);
		if (n.getLeftNode() == null) {
		    n.setLeftNode(node);
		    break;
		} else if (n.getRightNode() == null) {
		    n.setRightNode(node);
		    break;
	   	}
	    }
	}
    }

    public int heapSize() {
	return nodeList.size();
    }

    public void setNode(int i, int val) {
	((Node)nodeList.elementAt(i)).setWeight(val);
    }

    private void calNodesCoord(int size) {
	// count max number of nodes needed
	int i =  0; int sum = power(2, i++);
	while (sum < size)
	    sum += power(2, i++);
	max_node_per_level = power(2, i-1);
	depth = i-1;

	int max_nodes = sum;
	// insert nodes with no value into position tree
	Node backTree = tree; // backup current tree
	Vector backNodeList = nodeList; nodeList = new Vector(); 
	posnList = new Vector();
	for (int j = 0; j < max_nodes; j++) {
	    Node node = new Node(-1);
	    insert(node);
	}
	posn = tree;
	posnList = nodeList;
	tree = backTree;
	nodeList = backNodeList;
	

	// assign Y
	int curDepth = 0; sum = power(2, 0);
	int offset = drawingPanel.offset + 30;
	//int yStart = drawingPanel.panel_height/2 -100 - depth*20;
	int yStart = 100;
	for (int j = 0; j < posnList.size(); j++) {
	    Node node = (Node)posnList.elementAt(j);

	    if ( (j+1) > sum) {
		curDepth++; sum += power(2, curDepth);
	    }
	    node.depth = curDepth;

	    node.y = yStart + curDepth*40;

	    // assign X for bottom level
	    if (curDepth == depth) {
		node.x = 22 + offset;
		offset = node.x;
	    }
	}

	// assign remaining X
	for (int j = posnList.size() - 1; j >= 0; j--) {
	    Node node = (Node)posnList.elementAt(j);

	    if (node.depth == depth)
		continue;

	    if (node.getLeftNode() != null && node.depth == depth-1) {
		node.x = node.getLeftNode().x + 12;
	    } else if (node.getLeftNode() != null && 
		node.getRightNode() != null) {
		node.x = (node.getLeftNode().x + node.getRightNode().x)/2;
	    } else {
		// both children null -> can only at depth - 1
		int l = left(j+1);
	    }
	}
    }

    /* ------------------------ Utils -------------------- */

    public int power(int num, int pow) {
	int result = 1;
	for (int i = 0; i < pow; i++)
	    result *= num;
	return result;
    }

    public int parent(int i) {
	return (i/2);
    }

    public int left(int i) {
        return (2*i);
    }

    public int right(int i) {
        return (2*i + 1);
    }
 
    /* ------------------------ Graphical Primitives ------------------ */

    public void drawTree(Graphics g) {
	for (int i = 0; i < inputList.size(); i++) {
	    drawLeafNode(g, (Node)inputList.elementAt(i));
	}
	// draw input box
	if (inputList.size() > 0)
	    new ComBox( ((Node)inputList.lastElement()).x + 50,
			bottomMostPosn(posn) + 85, "Input",
		Color.white, darkBlue, fixFont ).draw(g);


	for (int i = 0; i < heapSize(); i++) {
	    Node node = (Node)nodeList.elementAt(i);
	    drawNode(g, node);
	}

	for (int i = 0; i < outputList.size(); i++)
	    drawLeafNode(g, (Node)outputList.elementAt(i));

	if (movingNode.getWeight() > -1)
	    drawNode(g, movingNode);

        for (int i = 0; i < heapArray.size(); i++) {
            Node node = (Node)heapArray.elementAt(i);
            drawArrayNode(g, node.x, node.y, node);
        }

	if (exchanging)
	    drawArrow(g, aPoints);

	// draw tree box
	new ComBox( ((Node)posnList.lastElement()).x + 40,
		((Node)posnList.lastElement()).y - 40, 
		"tree representation of the same heap",
		Color.white, darkRed, fixFont ).draw(g);

	// draw array box
	if (inputList.size() == 0)
	    new ComBox( max_size*22 + drawingPanel.offset + 30,
		bottomMostPosn(posn) + 50,
		"array representation of the heap",
		Color.white, darkRed, fixFont ).draw(g);

	// draw output box
	new ComBox( drawingPanel.offset,
		10, "Output",
		Color.white, darkBlue, fixFont).draw(g);

	if (runningCom != null)
	    runningCom.draw(g);
    }

    public void drawArrow(Graphics g, Point[] points) {
	// remember: no drawPolyline in jdk1.0.*
	int[] axPoints = new int[3], ayPoints = new int[3];
	g.setColor( Color.magenta );
	if (points.length < 3) {
	  Point endArrow = points[1], startArrow = points[0];
	  if (endArrow.y == startArrow.y) {
	    g.drawLine(startArrow.x, startArrow.y, endArrow.x, endArrow.y);
	    axPoints[0] = endArrow.x; ayPoints[0] = endArrow.y;
	    int unit = (endArrow.x - startArrow.x)/
			Math.abs(endArrow.x - startArrow.x);
	    axPoints[1] = endArrow.x - unit*2;
	    ayPoints[1] = endArrow.y - 2;
	    axPoints[2] = endArrow.x - unit*2;
	    ayPoints[2] = endArrow.y + 2;
	    g.fillPolygon(axPoints, ayPoints, 3);
	  } else if (endArrow.x == startArrow.x) {
	    g.drawLine(startArrow.x, startArrow.y, endArrow.x, endArrow.y);
	    axPoints[0] = endArrow.x; ayPoints[0] = endArrow.y;
	    int unit = (endArrow.y - startArrow.y)/
			Math.abs(endArrow.y - startArrow.y);
	    axPoints[1] = endArrow.x - 1;
	    ayPoints[1] = endArrow.y - unit*2;
	    axPoints[2] = endArrow.x + 2;
	    ayPoints[2] = endArrow.y - unit*2;
	    g.fillPolygon(axPoints, ayPoints, 3);
	  }
	} else if (points.length == 3) {
	    // draw a line for the first and second points then use
	    // drawArrow to draw the remaining segment
	    g.drawLine(points[0].x, points[0].y, points[1].x, points[1].y);
	    Point[] line = new Point[2];
	    line[0] = points[1];
	    line[1] = points[2];
	    drawArrow(g, line);
	}
    }

    public int treeWidth(Node node) {
        return (rightMostPosn(node) - leftMostPosn(node));
    }
 
    public int leftMostPosn(Node node) {
        if (node.isLeaf())
            return node.x;
        else
            return leftMostPosn(node.getLeftNode());
    }
 
    public int rightMostPosn(Node node) {
        if (node.isLeaf())
            return (node.x + 20);
        else
            return rightMostPosn(node.getRightNode());
    }
 
    public int treeHeight(Node node) {
        return (bottomMostPosn(node) - node.y);
    }
 
    public int bottomMostPosn(Node node) {
        if (node.isLeaf())
            return (node.y + 30);
        else {
            int rightBottom = bottomMostPosn(node.getRightNode());
            int leftBottom = bottomMostPosn(node.getLeftNode());
            return (rightBottom > leftBottom ? rightBottom : leftBottom);
        }
    }

    public void drawLeafNode(Graphics g, Node node) {
        int x = node.x; int y = node.y;
        int weight = node.getWeight();
        if (node.highlight)
            g.setColor(Color.black);
        else
            g.setColor( Color.blue );
        g.fillRect(x, y, 20, 30);
	g.setColor(Color.black);
	g.drawRect(x, y, 20, 30);
        g.setFont(hugeFont);
        g.setColor( Color.yellow );
        g.drawString(""+weight, x+2, y+25);
    }

    public void drawArrayNode(Graphics g, int x, int y, Node node) {
        int weight = node.getWeight();
        if (node.highlight)
            g.setColor(Color.black);
        else
            g.setColor( Color.red );
        g.fillRect(x, y, 20, 30);
	g.setColor(Color.black);
	g.drawRect(x, y, 20, 30);
        g.setFont(hugeFont);
        g.setColor( Color.yellow );
        g.drawString(""+weight, x+2, y+25);
    }
 
    public void drawNode(Graphics g, Node node) {
        if (node.highlight)
            g.setColor(Color.black);
        else
            g.setColor( darkgreen );
        g.fillRect(node.x, node.y, 20, 30);
	g.setColor(Color.black);
	g.drawRect(node.x, node.y, 20, 30);
        g.setColor( Color.white );
	g.setFont( hugeFont );
        g.drawString(""+node.getWeight(), node.x + 2, node.y+25);
 
        // draw links to children
	if (node.getLeftNode() != null) {
            g.setColor( Color.black );
            g.drawLine(node.x + 6, node.y + 30,
                node.getLeftNode().x + 10, node.getLeftNode().y);
	    if (node.highlightLeft) {
                g.drawLine(node.x + 5, node.y + 30,
                    node.getLeftNode().x + 9, node.getLeftNode().y);
                g.drawLine(node.x + 4, node.y + 30,
                    node.getLeftNode().x + 8, node.getLeftNode().y);
	    }
	}

	if (node.getRightNode() != null) {
            g.drawLine(node.x + 14, node.y + 30,
                node.getRightNode().x + 10, node.getRightNode().y);
	    if (node.highlightRight) {
                g.drawLine(node.x + 15, node.y + 30,
                    node.getRightNode().x + 11, node.getRightNode().y);
                g.drawLine(node.x + 16, node.y + 30,
                    node.getRightNode().x + 12, node.getRightNode().y);
	    }
	}
    }

    public void moveNode(Node node, int dx, int dy) {
        node.x += dx;
        node.y += dy;
        if (!node.isLeaf()) {
            moveNode(node.getLeftNode(), dx, dy);
            moveNode(node.getRightNode(), dx, dy);
        }
    }
}