intarraytreeanimationview.java

用JAVA实现排序等简单算法的演示

package graphicAnimation.intContainerAnimationView;

import java.awt.*;

import graphicAnimation.*;
import graphicAnimation.intAnimationView.*;

/**
 * 将数组看作二叉树，然后以二叉树的形式展示整个数组
 * @author 周晓聪
 * @since 2007/7/25
 *
 */
public class IntArrayTreeAnimationView extends AnimationView {
	protected IntAnimationView[] elements = null;			// 展示的数组元素的视图
	protected LineAnimationView[] nodeLines = null;		// 展示元素节点之间连线的视图
	
	protected int elementWidth = 20;						// 元素的宽度
	protected int dataSize = 0;							// 当前需要展示的有效元素范围，因为我们总是以完全二叉树来计算各个节点的位置
	
	public IntArrayTreeAnimationView() { }
	public IntArrayTreeAnimationView(Point pos, int elementWidth, Color color) {
		super(pos, color);
		this.elementWidth = elementWidth;
	}

	/**
	 * 在总宽度为 totalWidth，总高度为 totalHeight 的范围内生成树（主要是各节点的位置，以及节点之间的连线）
	 */
	public void createElementTreeAnimationView(int[] data, Color valueColor, int totalWidth, int totalHeight) {
		dataSize = data.length;

		int[] power2 = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512};		// 2 的各次幂
		int height = 0;												// 用于计算树高
		
		for (height = 0; power2[height] <= data.length && height < power2.length; height++);
		if (height <= 1 || height == power2.length) return; 	// 节点小于等于1或节点太多不使用树展示
		
		int size = power2[height] - 1;							// 数组作为完全二叉树时的节点数
		elements = new IntCircleAnimationView[size];			// 数组元素使用圆形视图
		
		// 计算最底层叶子节点的位置
		int x = position.x + elementWidth/2;					// 第一个节点的圆心位置
		int y = position.y;										// 最底层节点的y坐标是整个树的y坐标
		int xSpace = (totalWidth - 2 * x)/(size/2);				// 最底层节点x坐标之间的间隔
		for (int index = size/2; index < size; index++) {
			// 这一部分是最底层节点的数组下标
			int value = 0;
			if (index < data.length) value = data[index];		// 注意，真正的数组元素不一定有 size 这么多
			elements[index] = new IntCircleAnimationView(value, new Point(x, y), color, valueColor, elementWidth/2);
			if (index >= data.length) elements[index].hide();	// 隐藏真正数组元素以外的节点，我们只是利用其计算节点的位置
			x = x + xSpace;
		}
		
		// 计算内部节点的位置，内部节点总是处在它的两个儿子节点的 x 坐标中间
		int ySpace = (totalHeight - 2 * elementWidth)/height;	// 各层节点y坐标之间的间隔
		y = y - ySpace;				// 往上一层
		int layer = height - 2;		// 目前内部节点所在的层，根节点在0层，因此叶子节点在 height-1层，内部节点从 height-2层开始
		for (int index = size/2-1; index >= 0; index--) {
			// 逐层计算内部节点的位置，index 处节点的儿子节点在 2*index+1 和 2*index+2
			x = (elements[2*index+1].getPosition().x +elements[2*index+2].getPosition().x)/2;
			// index 处应该有真正的数组元素 data[index]，因为只有叶子节点才会超出真正数组的范围!
			elements[index] = new IntCircleAnimationView(data[index], new Point(x, y), color, valueColor, elementWidth/2);
			
			if (layer >= 0) {
				if (index == power2[layer]-1) {
					// 当 index 等于 power2[layer]-1 的时候树应该再往上一层
					y = y - ySpace;
					layer = layer-1;
				}
			}
		}
		
		// 生成节点之间连线，节点之间的连线至多有 data.length-1 条，即每个节点指向它父亲的连线，而根节点没有父亲
		nodeLines = new LineAnimationView[data.length-1];
		int lineIndex = nodeLines.length-1;
		for (int index = data.length-1; index > 0; index--) {
			Point point1 = elements[index].getPosition();
			// index 处节点的父亲在 (index-1)/2
			Point point2 = elements[(index-1)/2].getPosition(); 
			// 创建从 index 处到 index 的父亲处（即 (index-1)/2 处）之间的连线
			nodeLines[lineIndex] = new LineAnimationView(point1, point2, color);
			lineIndex = lineIndex - 1;
		}
	}
	

	/**
	 * 返回某个数组元素的视图
	 * @param index 该元素的下标
	 */
	public IntAnimationView getElementAnimationView(int index) { return elements[index]; }
	
	/**
	 * 返回数组元素的个数
	 * @return 如果已经创建数组元素模型则返回相应元素个数，否则返回 0
	 */
	public int getArrayLength() {
		if (elements == null) return 0;
		else return elements.length; 
	}
	
	/**
	 * 重新设置所有数组元素的值
	 * @param data 新的元素值所在的数组
	 */
	public void setElementValue(int[] data) {
		for (int index = 0; index < data.length; index++) {
			elements[index].setValue(data[index]);
		}
	}
	
	/**
	 * 重新设置某个数组元素的值
	 * @param index 该数组元素的下标
	 * @param value 该数组元素的新的值
	 */
	public void setElementValue(int index, int value) {
		elements[index].setValue(value);
	}
	
	/**
	 * 返回某个数组元素的值
	 * @param index 该数组元素的下标
	 * @return 该数组元素的值
	 */
	public int getElementValue(int index) {
		return elements[index].getValue();
	}
	
	/**
	 * 设置展示某个数组元素的颜色值，这个方法可使得某些数组元素用一些特别的颜色展示
	 * @param index 该数组元素的下标
	 * @param nColor 新的颜色
	 */
	public void setElementColor(int index, Color color) {
		elements[index].setColor(color);
	}

	/**
	 * 返回数组元素视图的颜色
	 * @param index 该元素的下标
	 */
	public Color getElementColor(int index) {
		return elements[index].getColor();
	}
	
	/** 
	 * 设置展示整个数组元素的颜色值
	 * @param color 颜色值
	 */
	public void setArrayColor(Color color) {
		setColor(color);
		for (int i = 0; i < elements.length; i++) elements[i].setColor(color);
	}
	
	/**
	 * 移动数组某个元素到新的位置
	 * @param index 该元素的下标
	 * @param newPos 新的位置
	 */
	public void moveElementTo(int index, Point newPos) {
		elements[index].moveTo(newPos);
	}
	
	/**
	 *  设置每个元素的矩形框的宽度
	 * @param width 宽度值
	 */
	public void setElementWidth(int width) { elementWidth = width; }
	
	/**
	 *  设置演示数组元素的起始位置，所有元素矩形框的位置根据该起始位置计算。注意对于纵坐标(y值）
	 * 	而言，所有元素矩形框均画在该起始值的上方（而不是下方）
	 * @param position 起始位置
	 */
	public void setStartPosition(Point position) { this.position = new Point(position); }
	/**
	 *  设置演示数组元素的起始位置，所有元素矩形框的位置根据该起始位置计算。注意对于纵坐标(y值）
	 * 	而言，所有元素矩形框均画在该起始值的上方（而不是下方）
	 * @param x, y 起始位置
	 */
	public void setStartPosition(int x, int y) { this.position = new Point(x, y); }

	/**
	 * 返回起始位置
	 * @return 起始位置
	 */
	public Point getStartPosition() { return position; }
	
	/** 
	 * 返回每个数组元素的矩形框宽度
	 * @return 宽度值
	 */
	public int getElementWidth() { return elementWidth; }
	
	
	/** 
	 * 返回某个数组元素的位置
	 * @param index 该元素的下标
	 * @return 位置值
	 */
	public Point getElementPosition(int index) { return elements[index].getPosition(); }

	/**
	 * 隐藏某个元素的视图
	 * @param index  该元素的下标
	 */
	public void hideElement(int index) {
		elements[index].hide();
	}
	
	/**
	 * 使某个元素的视图可见
	 * @param index  该元素的下标
	 */
	public void showElement(int index) {
		elements[index].show();
	}
	
	/**
	 * 减少需要展示的数组元素范围，这用于堆排序中，我们将已排序好的元素用其他视图展示，而不用树来展示
	 * 因此提供一个缩小用树展示的数组元素范围的方法
	 *
	 */
	public void decreaseDataSize() {
		dataSize = dataSize - 1;
	}
	
	/**
	 * 在屏幕上画出该整数数组
	 * @param gc 所使用的图形上下文
	 */
	public void paint(Graphics gc) {
		if (!visible) return;
		if (elements == null) return;
		
		// 先画所有节点之间的连线
		for (int index = 0; index < nodeLines.length; index++) {
			if (isLineVisible(index)) nodeLines[index].paint(gc);
		}
		// 再画所有的节点
		for (int index = 0; index < dataSize; index++) elements[index].paint(gc);
	}
	
	/**
	 * 判断 index 处的连线是否应该显示，我们希望当该连线的一个端点是被隐藏的叶子节点时，就不要显示
	 * 该连线。而如果该连线的两端都是内部节点，则即使该内部节点被暂时隐藏也要画出该连线。
	 * @param index
	 * @return
	 */
	private boolean isLineVisible(int index) {
		// 注意 index 处的线连的是 index+1处的节点及其父亲
		if (2*(index+1) > dataSize) { // 这是叶子节点
			if (!elements[index+1].isVisible()) return false;
		}
		return true;
	}
}