splitline.java

生物物种进化历程的演示

		if (array.length == 2)
			return "["+ (array[1]-array[0]) + "]";
		else if (array.length < 2) return "[]";
		String s = "[" + (array[1]-array[0]) + ", ";
		for (int i = 1; i < array.length-2; i++)
			s += (array[i+1]-array[i]) + ", ";
		s += array[array.length-1]-array[array.length-2] + "]";
		return s;	
	}

	public String toString()
	{
		String s = "too slow for debugging[";// + absoluteValues[0] + ", ";
//		for (int i = 1; i < splitValues.length-1; i++)
//			s += absoluteValues[i] + ", ";
//		s += absoluteValues[splitValues.length-1] + "]";
		return s;
	}
	
	public void setAbsoluteValue(int index, double value)
	{
		if (index > -1 && index < size)
			splitCells[index].absoluteValue = value;
		else
			System.out.println("Illegal absolute value index: " + index);
	}
	
	public double getAbsoluteValue(int index, int frameNum)
	{
	    //System.out.println("getAbsVal Illegal absolute value index: " + index + " " + this.size + " " + isHorizontal());
		if (index == -1)
			return minStuckValue;
		if (index == size)
			return maxStuckValue;
		computePlaceThisFrame(index, frameNum);
		if (index > -1 && index < size)
			return splitCells[index].absoluteValue;
		System.out.println("getAbsVal Illegal absolute value index: " + index + " " + this.size + " " +  isHorizontal());
		return -1f;
	}
	
	
	// returns index position (in the int array) of the index that is smaller than or equal to the root index
	// min and max index into splitIndices
	private int getIndexForRangeSplit(int[] splitIndices, int rootIndex, int min, int max)
	{
		if (rootIndex == splitIndices[min] || rootIndex == splitIndices[max])
		{
			System.out.println("Error: root index ("+ rootIndex+") shouldn't equal splitIndices[min] ("+splitIndices[min]+
					") or splitIndices[max] ("+splitIndices[max]+") when finding a split range");
			
		}
		int mid = (min+max)/2;
		while (min+1 < max && splitIndices[mid] != rootIndex)
		{
			if (splitIndices[mid] < rootIndex)
				min = mid;
			else
				max = mid;
			mid = (min+max)/2;
		}
		mid = (min+max)/2;
		return mid;
	}
	
	// newSplitValues is normalized (all values are between min=0 and max=1 from min to max) prior to calling
	// newSplitValues[min and max] may therefore be assumed to be 0 and 1 respectively and should not be modified
	private void resizeRanges(int[] splitIndices, double[] startValues, double[] endValues, int numSteps,
		int currRootIndex, int min, int max, Hashtable newToMove)
	{
		int frameNum = ad.getFrameNum();
//		System.out.println("Resizing ranges: min:" + min + " max:"+ max +" root:"+ rootIndex+" "+ doubleArrayDiffsToString(endValues, startValues));
 		if (max <= min)
 		{
			System.out.println("min == max in resize ranges: min:" + min + " max:"+ max +" root:"+ currRootIndex);
			return;
 		}
		if (max - min <= 1)
		{
			return; // base case, no splitlines to move inside a region with no ranges being resized
		}
		
		int index = getIndexForRangeSplit(splitIndices, currRootIndex, min, max);
		int xy = horizontal ? AccordionDrawer.X : AccordionDrawer.Y;
		double rootStartSize = startValues[max] - startValues[min];
		double rootEndSize = endValues[max] - endValues[min];
//		for (int i = min; i < max - 1; i++)
//		{
//			if (startValues[i] > startValues[i+1] || endValues[i] > endValues[i+1])
//			{
//				System.out.println("An error in position " + i + " " + startValues[i] + " " + startValues[i+1] + " " + endValues[i] + " " + endValues[i+1]);
//				return;
//			}	
//		}
		if (rootStartSize < 0 || rootEndSize < 0)
		{
			System.out.println("this is probably a synchronization problem");
			return; // what else can we do?  this is probably a synchronization problem
		}
		if (splitIndices[index] == currRootIndex) // some split is on the current root index, the easy case
			// 
		{
			// adjust the root index splitline location
			//double rootOldLocation = startValues[index];
			//double rootNewLocation = endValues[index];
			
			SplitTransition st = new SplitTransition(this, currRootIndex,
			(endValues[index]-endValues[min])/(rootEndSize),numSteps);
//			ad.toMove.add(st);

			newToMove.put(st.getHashKey(), st);
//			System.out.println("Added to move queue: " + ad.toMove);			
			
			// left side
			resizeRanges(splitIndices, startValues, endValues, numSteps,
				getSplitRoot(splitIndices[min], splitIndices[index], splitIndices[max], true),
				min, index, newToMove);
			
			// right side
			resizeRanges(splitIndices, startValues, endValues, numSteps,
				getSplitRoot(splitIndices[min], splitIndices[index], splitIndices[max], false),
				index, max, newToMove);
		}
		else // root is inside a range, this should be the common case (10 steps)
		{
			// step 1: move split at root index to right location
			double rootOldLocation = getAbsoluteValue(currRootIndex, frameNum); // relative to screen width
//			double rootOldSplit = splitCells[currRootIndex].splitValue; // relative to root region (min, max)
			double rootOldRangeSize = startValues[index+1] - startValues[index]; // size relative to index,index+1
			double rootNewRangeSize = endValues[index+1] - endValues[index]; // size relative to index,index+1
			if (rootNewRangeSize > 1 || rootNewRangeSize < 0)
				System.out.println("bad new root range size");
			double rootRatio = rootNewRangeSize/rootOldRangeSize; // ratio, can move split in index,index+1 range
			
			// relative to split region (index, index+1)
			double rootNewSplitTemp = rootRatio * // moving factor in index,index+1 range 
				(rootOldLocation-startValues[index]) + // normalize to the initial range position, old location is also a start position, both relative to screen width
				endValues[index]; // normalize to final range position 
			double rootNewSplit = (rootNewSplitTemp - endValues[min]) / (rootEndSize); // relative to root region (min, max)
			if (rootNewSplit > 1 || rootNewSplit < 0)
				System.out.println("bad new root split");
			double rootNewLocation = rootNewSplit * rootEndSize + endValues[min]; // relative to absolute location
			if (rootNewLocation > 1 || rootNewLocation < 0)
				System.out.println("bad new root location");
			SplitTransition st = new SplitTransition(this, currRootIndex, rootNewSplit,numSteps);
//			ad.toMove.add(st);
			newToMove.put(st.getHashKey(), st);
//			System.out.println("Added to move queue: " + ad.toMove);
			
			// step 2: store split on the right side boundary of root
			double tempEnd = endValues[index+1];    // store old range info for temporary over-write with current root
			double tempStart = startValues[index+1];
			int tempIndex = splitIndices[index+1]; // (will write this back on return from recursion)
			
			// step 3: write root split info into right side boundary of root
			endValues[index+1] = rootNewLocation;
			startValues[index+1] = rootOldLocation;
			splitIndices[index+1] = currRootIndex;
			
			// step 4: recursion on left side (min is same, max is index+1)
			if (rootNewLocation > 1 || rootNewLocation < 0)
				System.out.println("bad new root location");
			resizeRanges(splitIndices, startValues, endValues, numSteps,
				getSplitRoot(splitIndices[min], splitIndices[index+1], splitIndices[max], true),
//				(splitIndices[min]+rootIndex+1)/2,
				min, index+1, newToMove);
			
			// step 5: put right side split back in from temp variables (undo step 2, overwrite step 3 data but is still in variables)
			endValues[index+1] = tempEnd;
			startValues[index+1] = tempStart;
			splitIndices[index+1] = tempIndex;
			
			// step 6: store split on the left side boundary of root (see step 2 for similar action)
			tempEnd = endValues[index];
			tempStart = startValues[index];
			tempIndex = splitIndices[index];
			
			// step 7: write root split info into left side boundary of root (see step 3 for similar action)
			endValues[index] = rootNewLocation;
			startValues[index] = rootOldLocation;
			splitIndices[index] = currRootIndex;
			
			// step 8: recursion on right side (min is index, max is same)
			if (rootNewLocation > 1 || rootNewLocation < 0)
				System.out.println("bad new root location");
			resizeRanges(splitIndices, startValues, endValues, numSteps,
				getSplitRoot(splitIndices[min], splitIndices[index], splitIndices[max], false),
//				(splitIndices[index]+splitIndices[max]+1)/2,
				index, max, newToMove);
			
			// step 9: put left side split back in from temp variables (see step 5 for similar action, this undoes step 6)
			endValues[index] = tempEnd;
			startValues[index] = tempStart;
			splitIndices[index] = tempIndex;
			
			// done!
		}
	}
	
	// true when the first range was to the right of the min stuck position
	static private boolean createMin = false;
	
	// true when the last range was to the left of the max stuck position
	static private boolean createMax = false;
	
	// create range of indices of split lines for ranges in group
	// this includes the min/max stuck position split lines (if not already in a group)
	private int[] createIndexRanges(AbstractRangeList group)
	{
		int[] rangesTemp = group.getSplitIndices(horizontal);
		if (group.size() == 1 && 
			rangesTemp[0] == -1 && 
			rangesTemp[rangesTemp.length-1] == size)
			return null; // one range that covers the entire screen space 
		int minOffset = 0;
		createMin = false;
		createMax = false;
		int rangeSize = rangesTemp.length;
		if (rangesTemp[0] != -1) // first range doesn't include the min stuck position
		{
			rangeSize++;
			createMin = true;
			minOffset = 1;
		}
		if (rangesTemp[rangesTemp.length-1] != size) // last range doesn't include the max stuck position
		{
			rangeSize++;
			createMax = true;
		}
		int[] ranges = new int[rangeSize];
		for (int i = 0; i < rangesTemp.length; i++)
		{
			ranges[i + minOffset ] = rangesTemp[i]; 
		}
		if (createMin) ranges[0] = -1;
		if (createMax) ranges[ranges.length-1] = size;
		return ranges;
	}
	
	private double getTotalExtent(double[] extent)
	{
		double totalExtent = 0f;
		for (int i = 0; i < extent.length; i++)
		{
			totalExtent += extent[i];
		}
		return totalExtent;
	}
	
	public void resizeForest(AbstractRangeList group, int numSteps, Hashtable newToMove, double inflateIncr)
	{
		int frameNum = ad.getFrameNum();
		if (group.size() == 0) return; // no ranges
		int[] ranges = createIndexRanges(group); // sets createMin, createMax
		
//		System.out.print("RANGES: [");
//		for (int i = 0; i < ranges.length; i++)
//		{
//		    System.out.print(ranges[i]);
//		    if (i < ranges.length-1)
//		        System.out.print(", ");
//		    else
//		        System.out.println("]");
//		}
		
		if (ranges == null) return; // range covers everything
		if (group.size() == 1 &&
			getAbsoluteValue(ranges[(1+(createMin?1:0))], frameNum) -
				getAbsoluteValue(ranges[0+(createMin?1:0)], frameNum) +
				inflateIncr < ad.minContextInside)
			return;
		double stuckRangeSize = maxStuckValue - minStuckValue;
		
		double[] startValues = new double[ranges.length]; // where the splitlines start
		double[] endValues = new double[ranges.length]; // where the splitlines will go
		double[] extent = group.getSizesOfAllRanges(this, frameNum); // initial size of all ranges
		double noShrink = group.getUnshrinkableTotal(ad, this, frameNum); // total of all shrinking regions that will not shrink
		double oldTotalExtent = getTotalExtent(extent);
//		double inflateIncr = ad.inflateIncr;
		int rangesInPeriphery = (createMin ? 0 : 1) + (createMax ? 0 : 1);
//		double foo = ad.minContextPeriphery * (2-rangesInPeriphery);
//		double bar = (ranges.length - 1) * ad.minContextInside;
		double minGrowSize = stuckRangeSize - // stuck size 
//				ad.minContextPeriphery * (2-rangesInPeriphery) - // room for peripheries 
				noShrink; // room between ranges and peripheries
		if (oldTotalExtent + noShrink >= minGrowSize) // new potential size of ranges
		{
			System.out.println("Too much squishing, not going to grow (maybe too many ranges? " + ranges.length + ")");
			return; // don't grow any more
		}
//		double minShrinkSize = stuckRangeSize - // stuck size
//		ad.minContextPeriphery * rangesInPeriphery - // room for peripheries (range items)
//		noShrink; // room between ranges
		double oldTotalNonExtent = stuckRangeSize - oldTotalExtent;
		
		for (int i = 0; i < ranges.length; i++)
		{
			startValues[i] = getAbsoluteValue(ranges[i], frameNum);
		}
		endValues[0] = startValues[0]; // stuck
		endValues[ranges.length-1] = startValues[ranges.length-1]; // stuck
		
		int numRealRanges = extent.length;
		int numRealNonRanges = numRealRanges - 1; // size if min/max stuck lines were in groups 
		if (createMin) // min wasn't initially a range line
			numRealNonRanges++;
		if (createMax) // max wasn't initially a range line
			numRealNonRanges++;
		
		int startAt = 0;
		int endAt = ranges.length - 1;
		// after this, startAt will point to the min splitline index of the minimum range to grow
		//  and endAt will point to the max splitline index of the maximum range to grow
		// if either createMin or Max, those ranges will be resized and the inflateIncr will be adjusted accordingly
	
		{
			if (oldTotalExtent + inflateIncr > minGrowSize)
				inflateIncr = minGrowSize - oldTotalExtent;
//			System.out.println("inflateIncr: " + inflateIncr);
			// note: since inflateIncr is being used here it should not be altered after this point
			double newTotalExtent = oldTotalExtent + inflateIncr;
			double newTotalNonExtent = oldTotalNonExtent - inflateIncr;
			double totalExtentRatio = newTotalExtent/oldTotalExtent;
			double totalNonExtentRatio = newTotalNonExtent/oldTotalNonExtent;
			
			double firstRange = startValues[startAt+1]-startValues[startAt];
			double lastRange = startValues[endAt]-startValues[endAt-1];
			if (createMin)
			{
			// the periphery shouldn't be reduced if this is true:
				if (firstRange < ad.minContextPeriphery)
				{
					System.out.println("Area before first range might be squished too small");
					endValues[startAt+1] = startValues[startAt+1];
				}
				else
				{ // adjust the periphery
					endValues[startAt+1] = startValues[startAt] + firstRange*totalNonExtentRatio;
					if (endValues[startAt+1]-endValues[startAt] < ad.minContextPeriphery)
						// note: this loses some exactness with the resizing by not refactoring wrt min periphery
						endValues[startAt+1] = endValues[startAt] + (double)ad.minContextPeriphery;
				}
				startAt++;
			}
			if (createMax)
			{
				if (lastRange < ad.minContextPeriphery)
				{
				//	note: this loses some exactness with the resizing by not refactoring wrt min periphery
					System.out.println("Area after last range might be squished too small");
					endValues[endAt-1] = startValues[endAt-1];
				}
				else
				{
					endValues[endAt-1] = startValues[endAt] - lastRange*totalNonExtentRatio;
					if (endValues[endAt]-endValues[endAt-1] < ad.minContextPeriphery)
						// note: this loses some exactness with the resizing by not refactoring wrt min periphery
						endValues[endAt-1] = endValues[endAt] - (double)ad.minContextPeriphery;
				}
				endAt--;
			}
			for (int i = startAt; i <= endAt; i+=2)
			{ // ranges to grow start at i, end at i+1
				endValues[i+1] = startValues[i+1] - startValues[i];
				endValues[i+1] *= totalExtentRatio;
				endValues[i+1] += endValues[i]; // end of last range
			  // start of next range
				if (i+2 < endValues.length)
				{
					endValues[i+2] = startValues[i+2] - startValues[i+1];
					if (endValues[i+2] > ad.minContextInside)
						endValues[i+2] *= totalNonExtentRatio;
					endValues[i+2] += endValues[i+1];
				}
//				if (endValues[i+2] - endValues[i+1] < ad.minContextInside)
//				{
//					double halfAddBack = ((startValues[i+2]-startValues[i+1]) - ad.minContextInside)/2;
//					if (halfAddBack > 0)
//					{
//						endValues[i+1] = startValues[i+1] + halfAddBack;
//						endValues[i+2] = startValues[i+2] - halfAddBack;
//					}
//					else
//					{
//						System.out.println("Not moving, min context inside is too small: " + (endValues[i+1]-endValues[i]) + " " + (endValues[i+3]-endValues[i+2]));
//						endValues[i+1] = startValues[i+1];
//						endValues[i+2] = startValues[i+2];
//						System.out.println("Real: " + (endValues[i+1]-endValues[i]) + " " + (endValues[i+3]-endValues[i+2]));
//					}
//				}
			}
			
//			if (totalExtent + inflateIncr > 1)
//				inflateIncr = 1 - numRealNonRanges
		}

		
		// now resize the calculated ranges
		int min = 0, max = ranges.length - 1;
		//System.out.println("START: " + doubleArrayToRangeString(startValues));
		//System.out.println("END: " + doubleArrayToRangeString(endValues));
		//System.out.println("DIFF: " + doubleArrayDiffsToString(startValues, endValues));
		resizeRanges(ranges, startValues, endValues, numSteps, rootIndex, min, max, newToMove);
		// do movement transactions here
			
	}
	
	/**
	 * v is constructed recursively
	 * don't add individual cells between adjacent split lines