mergesortinganimator.java

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

package sortingAnimation;

import java.awt.Color;
import java.awt.Graphics;
import java.awt.Point;

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

/**
 * 用于展示合并排序的特殊演示器
 * @author 周晓聪
 * @since 2007/7/30
 *
 */
public class MergeSortingAnimator extends SortingArrayAnimator {
	protected int[] mergingData = null;				// 合并排序时所使用辅助临时数组
	protected IntArrayStickAnimationView auxView = null;	// 合并排序时所使用辅助临时数组的视图
	
	public MergeSortingAnimator() {
		auxView = new IntArrayStickAnimationView();
	}
	public MergeSortingAnimator(AnimationDriver animationManager) {
		super(animationManager);
		auxView = new IntArrayStickAnimationView();
	}
	public MergeSortingAnimator(AnimationArea area) {
		super(area); 
		auxView = new IntArrayStickAnimationView();
	}
	public MergeSortingAnimator(AnimationArea area, AnimationDriver animationManager) {
		super(area, animationManager);
		auxView = new IntArrayStickAnimationView();
	}

	/**
	 * 创建演示合并排序时所使用的辅助临时数组视图
	 * @param data 辅助数组
	 * @param leftdown 视图的左下角起始位置
	 * @param elementWidth 数组元素的宽度
	 * @param spacingWidth 数组元素之间的间隔
	 * @param valueColor 显示数组元素整数数值的颜色
	 */
	public void createMergeAnimatorScene(int[] data, Point leftdown, int elementWidth, int spacingWidth, Color valueColor) {
		auxView.setElementWidth(elementWidth);
		auxView.setSpacingWidth(spacingWidth);
		auxView.setStartPosition(leftdown);
		auxView.createElementBoxAnimationView(data, valueColor);
		auxView.setArrayColor(dataColor);
		for (int i = 0; i < data.length; i++) auxView.hideElement(i);
	}

	/**
	 * 设置正在辅助临时数组
	 */
	public void setMergingData(int[] data) {
		mergingData = data;
	}
	
	/**
	 * 用动画展示从合并用临时数组中往排序数组中拷贝元素的过程，拷贝的元素是从下标 startIndex（包括）
	 * 到 endIndex（不包括）
	 */
	public void showCopyMergeDataScene(int startIndex, int endIndex) {
		AnimationPath path;
		int delay = animationManager.getDelay();
		
		for (int index = startIndex; index < endIndex; index++) {
			// 利用辅助临时数组中的元素视图来展示动画，先将其原来位置保存，以便恢复
			Point oldPos = auxView.getElementPosition(index);
			int data = auxView.getElementValue(index);
			
			// 创建从临时数组 index 处元素视图到正排序数组 index 处元素视图的动画路径，并运行该动画
			path = createMergeToDataPath(index, index);
			for (int i = 0; i < path.size(); i++) {
				auxView.moveElementTo(index, path.get(i));
				update();
				sleep(delay);
			}
			// 恢复合并用临时数组该元素的视图，并将其隐藏（拷贝之后就不再显示出来了），而将排序数组
			// 该元素的视图显示出来
			auxView.moveElementTo(index, oldPos);
			auxView.hideElement(index);
			arrayView.setElementValue(index, data);
			arrayView.showElement(index);
			update();
		}
		
	}
	
	/**
	 * 用动画展示将排序数组中 dataIndex 处元素拷贝到临时数组的 mergeIndex 处
	 */
	public void showCopyDataScene(int mergeIndex, int dataIndex) {
		AnimationPath path;
		int delay = animationManager.getDelay();

		// 我们使用排序数组中的 dataIndex 处的元素视图来执行动画，所以先将其位置保存起来以便后面恢复
		Point oldPos = arrayView.getElementPosition(dataIndex);
		int data = arrayView.getElementValue(dataIndex);
		
		// 创建从排序数组视图中的 dataIndex 处的元素视图到临时数组视图的 mergeIndex 处元素视图的
		// 动画路径，并运行之
		path = createDataToMergePath(mergeIndex, dataIndex);
		for (int i = 0; i < path.size(); i++) {
			arrayView.moveElementTo(dataIndex, path.get(i));
			update();
			sleep(delay);
		}
		
		// 恢复排序数组视图中的 dataIndex 处的元素视图，这个恢复很重要，因为在将临时数组中的元素
		// 拷贝回来的时候，需要该视图的位置信息来计算动画路径
		arrayView.moveElementTo(dataIndex, oldPos);
		// 拷贝到临时数组中之后，暂时将 dataIndex 处的元素视图隐藏起来，等拷贝回来时再重新可见
		arrayView.hideElement(dataIndex);
		// 设置临时数组中的 mergeIndex 处的元素视图的整数数值，然后将其显示出来
		auxView.setElementValue(mergeIndex, data);
		auxView.showElement(mergeIndex);
		update();
	}
	
	/**
	 * 创建从合并用临时数组 mergeIndex 处的元素到排序数组 dataIndex 处元素的动画路径
	 */
	private AnimationPath createMergeToDataPath(int mergeIndex, int dataIndex) {
		AnimationPath path = new AnimationPath();
		Point mergePos = auxView.getElementPosition(mergeIndex);
		Point dataPos = arrayView.getElementPosition(dataIndex);
		
		path.addStartPoint(mergePos);
		int vDistance = dataPos.y - mergePos.y;
		int hDistance = dataPos.x - mergePos.x;
		
		// 该动画路径由三部分组成，先走一半的垂直距离，然后在水平方向移动到目标，再最后走另外一般的垂直
		// 距离。我们假定辅助临时数组的视图在排序数组视图的上方或下方
		if (vDistance > 0) path.moveDown(vDistance/2, unitMoving);
		else path.moveUp(-vDistance/2, unitMoving);
		if (hDistance > 0) path.moveRight(hDistance, unitMoving);
		else path.moveLeft(-hDistance, unitMoving);
		if (vDistance > 0) path.moveDown(vDistance/2, unitMoving);
		else path.moveUp(-vDistance/2, unitMoving);
		
		return path;
	}
	
	/**
	 * 创建从排序数组 dataIndex 处的元素到合并用临时数组 mergeIndex 处元素的动画路径
	 */
	private AnimationPath createDataToMergePath(int mergeIndex, int dataIndex) {
		AnimationPath path = new AnimationPath();
		Point dataPos = arrayView.getElementPosition(dataIndex);
		Point mergePos = auxView.getElementPosition(mergeIndex);

		// 假定排序数组的视图总是在合并用数组视图的下方
		int vDistance = dataPos.y - mergePos.y;
		int hDistance = mergePos.x - dataPos.x;
		
		AnimationView viewer = arrayView.getElementAnimationView(dataIndex);
		if (viewer instanceof IntRectAnimationView) {
			// 这种情况下移动的垂直距离要减去矩形框的高度
			vDistance = vDistance - ((IntRectAnimationView) viewer).getHeight();
		}
		
		// 该动画路径也是先移动一半的垂直距离，然后水平移动到目标，再移动一半的垂直距离，不过
		// 为简单起见，这里我们假定排序数组的视图总是在合并用辅助临时数组视图的下放
		path.addStartPoint(dataPos);
		path.moveUp(vDistance/2, unitMoving);
		if (hDistance > 0) path.moveRight(hDistance, unitMoving);
		else path.moveLeft(-hDistance, unitMoving);
		path.moveUp(vDistance/2, unitMoving);
		
		return path;
	}
	
	/**
	 *  绘制该演示器所管理的排序数组视图和临时数组视图
	 */
	public void paint(Graphics gc) {
		if (!visible) return;
		auxView.paint(gc);
		arrayView.paint(gc);
	}
}