splitline.java

生物物种进化历程的演示

/*
 * Created on Apr 20, 2004
 *
 * To change the template for this generated file go to
 * Window>Preferences>Java>Code Generation>Code and Comments
 */
package AccordionDrawer;

/**
 * @author hilde
 *
 * To change the template for this generated type comment go to
 * Window>Preferences>Java>Code Generation>Code and Comments
 */

// Maintain a list of gridcells and indices that represent some split lines
//  - a split line is a horizontal or vertical collection of splits, in some order, with min and max stuck positions
//  - on creation of a gridcell (one that is not a leaf), check for a splitline that's already created, else add the gridcell as the splitline
//  - return the index when checking new gridcells

import java.util.Hashtable;
import java.util.TreeSet;
import java.awt.Color;

import gl4java.*;

public class SplitLine {
	
	public static final double defaultMinStuckValue = 0.001f;
	public static final double defaultMaxStuckValue = 0.999f;
	
	// the accordion drawer that owns this splitline
	AccordionDrawer ad;
	
	// true if this is the horizontal splitline
	boolean horizontal;
	
	// number of elements
	int size;

	// some collection, let's try a Vector
	//  - set size of vector to number of splitlines possible (bottomsize - 1)
	//  - position of gridcell is index of splitline on level 0 grid (lowest level, which is complete, at most bottomsize)
	//  - calculate the index by following path from root (left is 0, right is +1, shift left on descent, similar to russian peasant method)
	//
	// maybe try a hashtable later?
	//  - hash key is index of splitline on level 0 grid (lowest level, which is complete, at most bottomsize)
	//  - hash value is the grid cell
	//  - ignore leaf cells (just don't call here when they get created)
	// verify: the reverse lookup (grid cell to index) is never needed in the old code, it's stored in gridcell
	//  - adding new cells dynamically wouldn't work well, of course
	// for later perhaps: a reference count table for each index => maybe remove the gridcell when not drawn for more dynamic action?
//	Vector splits; // Vector of GridCells
//	double[] splitValues; // each in range of [0,1]
//	double[] absoluteValues; // all monotonic increasing in range of [0,1]
//	int[] computedFrame; // frame number for each splitline
	SplitCell[] splitCells;
	final double SplitResetValue = 0.5f;
	int rootIndex;
	
	double minStuckValue, maxStuckValue;
	
	// set fullGrid to true for a drawer that we know is full 
	public SplitLine(AccordionDrawer ad, boolean horizontal, double minStuckValue, double maxStuckValue, int bottomGridSize)
	{
		this.ad = ad;
		this.horizontal = horizontal;
		this.minStuckValue = minStuckValue;
		this.maxStuckValue = maxStuckValue;
		//size = horizontal ? (ad.bottomSize[AccordionDrawer.X]-1) *2 : (ad.bottomSize[AccordionDrawer.Y]-1) ;
		size = bottomGridSize;
//		splits = new Vector();
		splitCells = new SplitCell[size];
//		absoluteValues = new double[size];
//		computedFrame = new int[size];
		rootIndex = getThisRoot(-1, size);
System.out.println("root index: " + rootIndex + " size: " + size);
		
		System.out.println(ad.getOlduvaiObject());
		int minkey = ad.getOlduvaiObject().getMinObjectKey();
		int maxkey = ad.getOlduvaiObject().getMaxObjectKey();
		int middle = (minkey + maxkey) / 2; 
		if (size > 0)
		    initSplitValuesRecurse(-1, rootIndex, size, rootIndex, minkey, middle, maxkey);
		resetSplitValues();
	}
	
	public void setCullingObject(int splitLinePos, Object obj)
	{
		splitCells[splitLinePos].cullingObject = obj;
	}
	
	public Object getCullingObject(int splitLinePos)
	{
		return splitCells[splitLinePos].cullingObject;
	}
	
	public static int getThisRoot(int min, int max)
	{
		return (min + max + 1) / 2;
	}
	
	public static int getSplitRoot(int min, int split, int max, boolean left)
	{
		if (left)
			return getThisRoot(min, split); // (min + split + 1) / 2;
		else
			return getThisRoot(split, max); //(split + max + 1) / 2;
	}
	
	private void initSplitValuesRecurse(int min, int mid, int max, int parent, int start, int middle, int end)
	{
		splitCells[mid] = new SplitCell(min, max);
//		splitCells[mid].max = max;
//		splitCells[mid].min = min;
		
		splitCells[mid].cullingObject = null;
		    
		splitCells[mid].parent = parent;
		if (min + 1 == max) return;
		
		
		
		// dynamic? set another stopping condition such as computedFrame == -1
		splitCells[mid].kid = new int[2];
		splitCells[mid].splitValue = (double)(mid-min) / (double)(max - min);//(double)(mid - min) / (double)(max - min);
		splitCells[mid].computedFrame = -1; // recompute the position of absolute location for each split line
		splitCells[mid].absoluteValue = -1;
		
		splitCells[mid].kid[0] = getSplitRoot(min, mid, max, true);
		splitCells[mid].kid[1] = getSplitRoot(min, mid, max, false);
		
//		int newMiddle[] = new int[2];
//		newMiddle[0] = getSplitRoot(start, middle, end, true);
//		newMiddle[1] = getSplitRoot(start, middle, end, false);
		
		if (splitCells[mid].kid[0] != -1 && splitCells[splitCells[mid].kid[0]] == null)
			initSplitValuesRecurse(min, splitCells[mid].kid[0], mid, mid, 0,0,0);
		else
			splitCells[mid].kid[0] = -1;
		if (splitCells[mid].kid[1] != size && splitCells[splitCells[mid].kid[1]] == null)
			initSplitValuesRecurse(mid, splitCells[mid].kid[1], max, mid, 0,0,0);
		else
			splitCells[mid].kid[1] = -1;
	}
	
	
	private void resetSplitValuesRecurse(int min, int mid, int max, int start, int middle, int end)
	{
		if (min + 1 == max) return;
		// dynamic? set another stopping condition such as computedFrame == -1
		
		
		//splitCells[mid].splitValue = (double)(middle-start) / (double)(end -start); 
		splitCells[mid].splitValue = (double)(mid - min) / (double)(max - min);
		splitCells[mid].computedFrame = -1; // recompute the position of absolute location for each split line
		splitCells[mid].absoluteValue = -1;
		//int minkey = ad.getOlduvaiObject().getMinObjectKey();
		int newMiddle[] = new int[2];
		if( horizontal )
		{
			newMiddle[0] = getSplitRoot((int)start, (int)middle, (int)end, true); //ad.getOlduvaiObject().getObjectKeyAt(splitCells[mid].kid[0]); // 
			newMiddle[1] = getSplitRoot((int)start, (int)middle, (int)end, false); //ad.getOlduvaiObject().getObjectKeyAt(splitCells[mid].kid[1]); // 
		}
		else
		{
			newMiddle[0] = getSplitRoot((int)start, (int)middle, (int)end, true); //ad.getOlduvaiObject().getObjectKeyAt(splitCells[mid].kid[0]);
			newMiddle[1] = getSplitRoot((int)start, (int)middle, (int)end, false); //ad.getOlduvaiObject().getObjectKeyAt(splitCells[mid].kid[1]);
		}
		resetSplitValuesRecurse(min, splitCells[mid].kid[0], mid, start, newMiddle[0], middle);
		resetSplitValuesRecurse(mid, splitCells[mid].kid[1], max, middle, newMiddle[1], end);
	}
	
	public void resetSplitValues()
	{
		int minkey, maxkey, middle;
	
			minkey = ad.getOlduvaiObject().getMinObjectKey();
			maxkey = ad.getOlduvaiObject().getMaxObjectKey() - minkey;
			middle = maxkey / 2; // ad.getOlduvaiObject().getObjectKeyAt(rootIndex); // 
			minkey = 0;
		

		
		resetSplitValuesRecurse(-1, rootIndex, size, minkey, middle, maxkey);

		// may need to adjust position to stuck values
		// - done in computePlaceThisFrame
		// must call computePlaceThisFrame before drawing anything after a reset
	}

	// set the min/maxline for the cell
	// set the splitCell index for the cell
	// call this for each internal node LeafGridCell
	// - internal tree nodes call this since they know their min/max lines
	// cellgeom should be set for cell before calling this
	// cellSplitIndex is the index into the splitCells data structure
	public void addCell(GridCell cell, int minLine, int maxLine)
	{
		int xy = horizontal ? 0 : 1;
		cell.minLine[xy] = minLine;
		cell.maxLine[xy] = maxLine;
	}
	
	// set the min/maxline for the cell
	// call this for each LeafGridCell
	// cellSplitIndex is the index into the splitCells data structure, above the cell
	public void addCell(GridCell cell, int splitCellIndex)
	{
		int xy = horizontal ? 0 : 1;
		cell.minLine[xy] = splitCellIndex-1;
		cell.maxLine[xy] = splitCellIndex;
	}
	
	
	// use absolute values to return the split index at the screen position
	public int getSplitLineIndex(double screenPosition, double pixelSize, int frameNum)
	{
		if (screenPosition < minStuckValue || screenPosition > maxStuckValue)
			return -2;
		int min = -1;
		int max = size;  //horizontal ? (ad.bottomSize[AccordionDrawer.X]-1) * 2 : (ad.bottomSize[AccordionDrawer.Y]-1);
		int mid = getThisRoot(min, max);
		while (min + 1 != max && getAbsoluteValue(max, frameNum) - getAbsoluteValue(min, frameNum) > pixelSize)
		{
			if (screenPosition < getAbsoluteValue(mid, frameNum))
			{
				max = mid;
				mid = getThisRoot(min, mid);
			}
			else
			{
				min = mid;
				mid = getThisRoot(mid, max);
			}
		}
		
		if (screenPosition > getAbsoluteValue(min, frameNum) || screenPosition < getAbsoluteValue(max, frameNum))
			return mid;
		System.out.println("Error in getSplitLineIndex searching for the value: " + screenPosition);
		return -2;
	}
	

	/**
	 * @param f
	 */
	public void setMaxStuckValue(double f) {
		maxStuckValue = f;
	}

	/**
	 * @param f
	 */
	public void setMinStuckValue(double f) {
		minStuckValue = f;
	}

	/**
	 * @return
	 */
	public double getMaxStuckValue() {
		return maxStuckValue;
	}

	/**
	 * @return
	 */
	public double getMinStuckValue() {
		return minStuckValue;
	}
	
	// return the index of the minline
	public int getMinLine(int cellIndex)
	{
		return splitCells[cellIndex].min;
	}

	public int getMaxLine(int cellIndex)
	{
		return splitCells[cellIndex].max;
	}
	
	public int getParentSplitIndex(int cellIndex)
	{
		return splitCells[cellIndex].parent;
	}
	
	public boolean isRoot(int cellIndex)
	{
		return cellIndex == rootIndex;
	}
	
	// return true if this split is to the left of its parent
	public boolean isSplitLeftChild(int cellIndex)
	{
		if (isRoot(cellIndex)) return false;
		return splitCells[splitCells[cellIndex].parent].kid[0] == cellIndex;
	}
	
	/**
	 * Computes min[], max[], and splitPos, the minimum, maximum and
	 * split point coordinates for this GridCell in absolute window
	 * coordinates. 
	 * 
	 * Absolute coordinates are computed hierarchically from the
	 * relative position of the splits. Values computed are minimum
	 * boundary, maximum boundary, split position, and area. All these
	 * are computed in both window and screen coordinates. All these
	 * fields should never be accessed directly, only through the
	 * "get" access functions, so that this computation takes place
	 * when needed.
	 * 
	 * This data is updated only if it is stale, it is cached for the
	 * duration of a frame. The current frame number (frameNum) is the
	 * determiner of staleness, recompute whenever it's incremented.
	 * Note that incrementing can happen based in internal
	 * computation, not just an actual frame boundary visible to the
	 * user.
	 *
	 * @author   Tamara Munzner
	 *   */

	// compute new value for absoluteValues[cellIndex]
	private static final double threshold = 1e-5; // stop computing when adjacent lines are this close together
	public void computePlaceThisFrame(int cellIndex, int frameNum)
	{ // cell index is a split index of a cell
//		int frameNum = ad.getFrameNum();
		if (cellIndex == -1 || cellIndex == size )
		{
////				System.out.println("cellIndex is a stuck value, can't compute place with this cellIndex: " + cellIndex);
			return;
		}
		if (cellIndex > -1 && cellIndex < size &&
			frameNum > splitCells[cellIndex].computedFrame)
		{
			int xy = horizontal ? AccordionDrawer.X : AccordionDrawer.Y;
			boolean thisCellIsLeft;
	 		if (!isRoot(cellIndex))
	 		{
				int parent = getParentSplitIndex(cellIndex);
				computePlaceThisFrame(parent, frameNum);
				if (isSplitLeftChild(cellIndex))
				{
					int minLine = getMinLine(parent);
					double parMinPosition = minLine == -1 ?
						minStuckValue :
						splitCells[minLine].absoluteValue; // absolute position of min line
					double parSplitPosition = size == 0 ?
						maxStuckValue :
						splitCells[parent].absoluteValue;
					double range = parSplitPosition - parMinPosition; // size of parent min split
					splitCells[cellIndex].absoluteValue = parMinPosition + range * splitCells[cellIndex].splitValue;
					if (splitCells[cellIndex].absoluteValue < minStuckValue || splitCells[cellIndex].absoluteValue > maxStuckValue)
						System.out.println("Bad absolute value: " + cellIndex + " " + splitCells[cellIndex].absoluteValue + " " + minStuckValue + " " + maxStuckValue);
				}
				else
				{ // right split child
					int maxLine = getMaxLine(parent);
					double parMaxPosition = maxLine == size ?
						maxStuckValue :
						splitCells[maxLine].absoluteValue; // absolute position of max line
					double parSplitPosition = size == 0 ?
						minStuckValue :
						splitCells[parent].absoluteValue;
					double range = parMaxPosition - parSplitPosition; // size of parent max split
					splitCells[cellIndex].absoluteValue = parSplitPosition + range * splitCells[cellIndex].splitValue;
					if (splitCells[cellIndex].absoluteValue < minStuckValue || splitCells[cellIndex].absoluteValue > maxStuckValue)
						System.out.println("Bad absolute value: " + cellIndex + " " + splitCells[cellIndex].absoluteValue + " " + minStuckValue + " " + maxStuckValue);
				}
			}
			else
			{ // root node, parent doesn't really exist, this cell is in position 0 so it is on the left of the imaginary parent
				double myMinPosition = minStuckValue;
				double myMaxPosition = maxStuckValue;
				double range = myMaxPosition - myMinPosition;
				splitCells[cellIndex].absoluteValue = myMinPosition + range * splitCells[cellIndex].splitValue;
				if (splitCells[cellIndex].absoluteValue < minStuckValue || splitCells[cellIndex].absoluteValue > maxStuckValue)
					System.out.println("Bad absolute value: " + cellIndex + " " + splitCells[cellIndex].absoluteValue + " " + minStuckValue + " " + maxStuckValue);
			}
			splitCells[cellIndex].computedFrame = frameNum;
		}
	}

	private String intArrayToString(int[] array)
	{
		String s = "[" + array[0] + ", ";
		for (int i = 1; i < array.length-1; i++)
			s += array[i] + ", ";
		s += array[array.length-1] + "]";
		return s;	
	}
	private String doubleArrayDiffsToString(double[] array, double[] array2)
	{
		String s = "[" + (array[0]-array2[0]) + ", ";
		for (int i = 1; i < array.length-1; i++)
			s += (array[i]-array2[i]) + ", ";
		s += (array[array.length-1]-array2[array.length-1]) + "]";
		return s;	
	}
	private String doubleArrayToString(double[] array)
	{
		String s = "[" + array[0] + ", ";
		for (int i = 1; i < array.length-1; i++)
			s += array[i] + ", ";
		s += array[array.length-1] + "]";
		return s;	
	}
	private String doubleArrayToRangeString(double[] array)
	{