heapsortinganimator.java

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

package sortingAnimation;

import graphicAnimation.*;
import graphicAnimation.intContainerAnimationView.*;

import java.awt.*;

/**
 * 用于堆排序的演示器，使用树形数组视图进行展示
 * @author 周晓聪
 * @since 2007/7/30
 */
public class HeapSortingAnimator extends SortingArrayAnimator {
	// 树形数组视图作为辅助视图，但实际上占据演示区域的大部分，在父类 SortingArrayAnimator 保存的
	// arrayView 使用圆形视图用于展示已经排好序的元素
	protected IntArrayTreeAnimationView auxView = null;
	
	public HeapSortingAnimator() {
		auxView = new IntArrayTreeAnimationView();
	}
	public HeapSortingAnimator(AnimationDriver animationManager) {
		super(animationManager);
		auxView = new IntArrayTreeAnimationView();
	}
	public HeapSortingAnimator(AnimationArea area) {
		super(area); 
		auxView = new IntArrayTreeAnimationView();
	}
	public HeapSortingAnimator(AnimationArea area, AnimationDriver animationManager) {
		super(area, animationManager);
		auxView = new IntArrayTreeAnimationView();
	}

	/**
	 * 创建堆排序时以圆形整数视图为元素视图的数组视图，这个视图处于树形视图的上方，展示那些已经排好序
	 * 的数组元素
	 * @param data 参与排序数组
	 * @param leftdown 数组视图的左下角起始坐标
	 * @param elementWidth 数组元素宽度
	 * @param spacingWidth 数组元素之间的间隔宽度
	 * @param valueColor 显示数组元素的整数数值时使用的颜色
	 */
	public void createHeapAnimationScene(int[] data, Point leftdown, int elementWidth, int spacingWidth, Color valueColor) {
		arrayView = new IntArrayStickAnimationView(leftdown, elementWidth, spacingWidth, dataColor);
		((IntArrayStickAnimationView)arrayView).createElementCircleAnimationView(data, valueColor);
		for (int i = 0; i < data.length; i++) arrayView.hideElement(i);
	}
	
	/**
	 * 创建堆排序时的树形数组视图，这个视图是展示堆排序（当数组长度比较少的时候）的主要视图
	 * @param data 参与排序的数组 
	 * @param leftdown 整个视图的左下角起始坐标
	 * @param elementWidth 数组元素宽度
	 * @param valueColor 显示数组元素的整数数值时使用的颜色
	 * @param totalWidth 整个视图的宽度，需要总高度和总宽度的信息来计算树的节点位置
	 * @param totalHeight 整个视图的高度
	 */
	public void createHeapTreeAnimatorScene(int[] data, Point leftdown, int elementWidth, Color valueColor, int totalWidth, int totalHeight) {
		auxView.setElementWidth(elementWidth);
		auxView.setStartPosition(leftdown);
		auxView.createElementTreeAnimationView(data, valueColor, totalWidth, totalHeight);
		auxView.setArrayColor(dataColor);
		update();
	}

	/**
	 * 以标志正在比较的颜色展示两个正在比较的两个数组元素
	 */
	public void showCompareScene(int firstIndex, int secondIndex) {
		auxView.setElementColor(firstIndex, compareColor);
		auxView.setElementColor(secondIndex, compareColor);
		update();
		sleep(stepDelay);
		auxView.setElementColor(firstIndex, dataColor);
		auxView.setElementColor(secondIndex, dataColor);
		update();
	}
	
	/**
	 * 分别以标志选中和标志正在比较的颜色展示被选中的元素与另一个元素的比较
	 */
	public void showCompareSelectedScene(int index) {
		if (selectedIndex < 0) return;

		// 假定选中的元素已经设置了正确的颜色，因此这里就不再对选中的元素设置颜色
		auxView.setElementColor(index, compareColor);
		update();
		sleep(stepDelay);
		auxView.setElementColor(index, dataColor);
		update();
	}

	/**
	 * 展示 index 处的元素被选中，即以标志被选中的颜色展示该元素
	 */
	public void showSelectScene(int index) {
		// 将原先选中的元素恢复成正常的颜色值
		if (selectedIndex >= 0) auxView.setElementColor(selectedIndex, dataColor);
		// 记录新的被选中的元素的下标及整数数值
		selectedIndex = index;
		selectedData = auxView.getElementValue(selectedIndex);
		// 设置其为正被选中的颜色
		auxView.setElementColor(selectedIndex, selectColor);
		update();
	}

	/**
	 * 以动画的形式展示树形视图中的 treeIndex 处的元素移动到圆形视图中的 dataIndex 处，这在堆排序算法
	 * 中是将树根元素放置到已经排好序的位置，然后还要将树形数组视图的 dataIndex 处的元素视图移动到
	 * treeIndex 处（即当前的树根处），以便进行下一次的堆调整。
	 */
	public void showSwapScene(int treeIndex, int dataIndex) {
		AnimationPath path;
		int delay = animationManager.getDelay();		// 使用与动画驱动器相同的延迟
		
		// 记住树形视图中 treeIndex 处的元素视图的位置和整数数值，因为我们将用该视图来展示动画效果
		// 展示完毕之后，会将其移动到原来的位置然后隐藏起来
		Point oldPos = auxView.getElementPosition(treeIndex);
		int data = auxView.getElementValue(treeIndex);
		
		// 创建从树形数组视图的 treeIndex 处的元素视图到圆形数组视图的 dataIndex 处的元素视图
		// 的动画路径，这个路径就是这两个视图之间的直线路径
		path = createSwapElementPath(treeIndex, dataIndex);
		// 下面根据该动画路径展示动画效果，这里为了简单起见没有使用动画驱动器
		for (int i = 0; i < path.size(); i++) {
			auxView.moveElementTo(treeIndex, path.get(i));
			update();
			sleep(delay);
		}
		// 展示圆形数组视图中的dataIndex 处的元素视图
		arrayView.setElementValue(dataIndex, data);
		arrayView.showElement(dataIndex);
		update();
		
		// 恢复树型数组视图的 treeIndex 处的元素视图位置（这个恢复是重要的，因为下面的移动需要该位置
		// 信息），并将其隐藏起来。
		auxView.moveElementTo(treeIndex, oldPos);
		auxView.hideElement(treeIndex);

		// 下面移动树形数组视图的 dataIndex 处的元素视图到 treeIndex 处，方法与上面类似，只是这一次
		// 是在树形视图范围内移动而已
		oldPos = auxView.getElementPosition(dataIndex);
		data = auxView.getElementValue(dataIndex);
		
		path = createMoveElementPath(dataIndex, treeIndex);
		for (int i = 0; i < path.size(); i++) {
			auxView.moveElementTo(dataIndex, path.get(i));
			update();
			sleep(delay);
		}
		// 设置 treeIndex 处的视图中保存的数组元素值为原来 dataIndex 处的元素值，因为将dataIndex 处
		// 的视图移动到 treeIndex 处了。
		auxView.setElementValue(treeIndex, data);
		// 重新使得 treeIndex 处的元素视图可见，因为实际上需要隐藏的是 dataIndex 处的视图
		auxView.showElement(treeIndex);
		// 恢复 dataIndex 处的元素视图的位置，这个位置可能在后面计算动画路径时需要
		auxView.moveElementTo(dataIndex, oldPos);
		// dataIndex 处的元素视图不再需要展示，因为我们实际上将它交换到 treeIndex 处了。
		auxView.hideElement(dataIndex);
		// 减少整个树所要展示的数组元素个数，因为我们将已经排好序的元素放到圆形视图中去展示了
		auxView.decreaseDataSize();
		update();

		sleep(stepDelay);
	}
	
	/**
	 * 展示在树形视图内将 fromIndex 处的元素视图移动到 toIndex 处，从而以动画的形式展示在堆排序时将 
	 * fromIndex 处的元素赋值到 toIndex 处的过程
	 */
	public void showMoveElementScene(int fromIndex, int toIndex) {
		AnimationPath path;
		int delay = animationManager.getDelay();

		// 保存 fromIndex 处视图的原来位置，以便恢复
		Point oldPos = auxView.getElementPosition(fromIndex);
		int data = auxView.getElementValue(fromIndex);
		
		// 创建从 fromIndex 处视图到 toIndex 处视图的动画路径，并运行
		path = createMoveElementPath(fromIndex, toIndex);
		for (int i = 0; i < path.size(); i++) {
			auxView.moveElementTo(fromIndex, path.get(i));
			update();
			sleep(delay);
		}
		
		// 恢复 fromIndex 处的视图，然后将其隐藏起来，这一步很重要，因为下面可能又有元素要移动到
		// 这个位置来，我们需要这个位置信息来计算移动的动画路径
		auxView.moveElementTo(fromIndex, oldPos);
		auxView.hideElement(fromIndex);
		// 设置 toIndex 处的元素视图的整数数值为 fromIndex 处的整数值
		auxView.setElementValue(toIndex, data);
		// 将 toIndex 处的元素视图可见，从屏幕的效果来看，就是 fromIndex 处的视图移动到 toIndex 处
		// 之后不动了。注意，toIndex 处原先的元素视图可能作为上一次移动的源下标从而被隐藏起来，因此
		// 这里需要使得它可见
		auxView.showElement(toIndex);
		update();
		sleep(stepDelay);
	}
	

	/**
	 * 以动画的形式展示将选中的元素放到 index 处
	 */
	public void showPlaceScene(int index) {
		int delay = animationManager.getDelay();
		// 先利用 index 处的位置生成动画路径
		AnimationPath path;
		path = createMoveElementPath(selectedIndex, index);

		// 注意，selectedIndex 处的元素（即selectedData)及其模型可能已经被改变（例如调用 move() 进行
		// 元素移动时覆盖了选中元素的模型），因此下面利用放置的目标元素的模型来重建 selectedData 的
		// 模型，这是合理的，因为放置的目标元素模型最终要被覆盖。
		Point selectedPos = auxView.getElementPosition(selectedIndex);
		auxView.setElementColor(index, selectColor);
		auxView.setElementValue(index, selectedData);
		auxView.moveElementTo(index, selectedPos);
		auxView.showElement(index);		// 目标位置处的元素通常已经被隐藏了，所以这里重新显示。

		for (int i = 0; i < path.size(); i++) {
			auxView.moveElementTo(index, path.get(i));
			update();
			sleep(delay);
		}
		auxView.setElementColor(index, dataColor);
		update();
	}
	
	/**
	 * 创建在树形数组视图的 fromIndex 处的元素视图移动到 toIndex 处的元素视图的动画路径，这个路径
	 * 是这两个视图位置之间的直线路径
	 */
	public AnimationPath createMoveElementPath(int fromIndex, int toIndex) {
		AnimationPath path = new AnimationPath();

		Point start = auxView.getElementPosition(fromIndex);
		Point end = auxView.getElementPosition(toIndex);
		
		path.addStartPoint(start);
		path.moveTo(end, unitMoving);
		return path;
	}

	/**
	 * 创建从树形数组视图的 treeIndex 处的元素视图移动到圆形数组视图的 dataIndex 处元素视图的动画
	 * 路径，这个路径也是这两个视图位置之间的直线路径
	 */
	public AnimationPath createSwapElementPath(int treeIndex, int dataIndex) {
		AnimationPath path = new AnimationPath();

		// 注意交换时，是将树型数组的 treeIndex 处元素放到 盒子型或圆形数组 的 dataIndex 处 
		Point start = auxView.getElementPosition(treeIndex);
		Point end = arrayView.getElementPosition(dataIndex);
		
		path.addStartPoint(start);
		path.moveTo(end, unitMoving);
		return path;
	}

	/** 
	 * 绘制该演示器所管理的两个数组视图
	 */
	public void paint(Graphics gc) {
		if (!visible) return;
		auxView.paint(gc);
		arrayView.paint(gc);
	}
}