rangelist.java

生物物种进化历程的演示

/*
   Copyright (c) 2002 Compaq Computer Corporation
   
   SOFTWARE RELEASE
   
   Permission is hereby granted, free of charge, to any person obtaining
   a copy of this software and associated documentation files (the
   "Software"), to deal in the Software without restriction, including
   without limitation the rights to use, copy, modify, merge, publish,
   distribute, sublicense, and/or sell copies of the Software, and to
   permit persons to whom the Software is furnished to do so, subject to
   the following conditions:
   
   - Redistributions of source code must retain the above copyright
     notice, this list of conditions and the following disclaimer.
   
   - Redistributions in binary form must reproduce the above copyright
     notice, this list of conditions and the following disclaimer in the
     documentation and/or other materials provided with the distribution.
   
   - Neither the names of Compaq Research, Compaq Computer Corporation
     nor the names of its contributors may be used to endorse or promote
     products derived from this Software without specific prior written
     permission.
   
   THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
   EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
   MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. 
   IN NO EVENT SHALL COMPAQ COMPUTER CORPORATION BE LIABLE FOR ANY CLAIM,
   DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
   OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR
   THE USE OR OTHER DEALINGS IN THE SOFTWARE. 
*/

package AccordionTreeDrawer;

import java.awt.Color;
import java.util.*;

import AccordionDrawer.AbstractRangeList;
import AccordionDrawer.AccordionDrawer;
import AccordionDrawer.SplitCell;
import AccordionDrawer.SplitLine;

/**
 * A class representing a list of RangeInTrees. A RangeInTree
 * represents ordered pair (min,max)) of TreeNodes.
 *
 * This class is a helper class for TreeJuxtaposer and keeps a
 * resizeable array of RangeInTree's.
 *
 * Note that each RangeInTrees item in a RangeList can be associated
 * with a different Tree.
 * 
 * @see TreeJuxtaposer.RangeInList
 * @see AccordionDrawer.TreeNode
 * 
 * @author  Tamara Munzner
 * */

public class RangeList extends AbstractRangeList {

    /**
     * Resizeable array (linked list) of RangeInTree objects
     */
    TreeSet ranges; // resizeable array of RangeInTree objects
	public static boolean returnObject = false;
	public static RangeInTree matchRange;
    boolean enabled; 
    Color col;
    int key;
        
    /*
     * Only highlight group items for this tree, not all the others
     */ 
    boolean thisTreeOnly;

    public RangeList(int i) {
	col = new Color((float).5, (float).5, (float).5);
	enabled = true;
	ranges = new TreeSet();
	thisTreeOnly = false;
	key = i;
    }
    public RangeList(int i, Color c, boolean on, boolean only) {
	key = i;
	col = c;
	enabled = on;
	ranges = new TreeSet();
	thisTreeOnly = only;
    }
//    public void addRange(int min, int max, AccordionTreeDrawer t) {
//	RangeInTree r = new RangeInTree(min, max, t);
//	ranges.add(r);
//    }
	public void addRange(int min, int max, AccordionTreeDrawer t) { // add range with intersection checking, this means the list is ordered
	returnObject = true;
	RangeInTree addTree = new RangeInTree(min, max, t); // new range to add
	RangeInTree intersectRange;
	while (ranges.contains(addTree))
	{
		ranges.remove(matchRange);
		addTree = new RangeInTree(Math.min(addTree.min, matchRange.min), Math.max(addTree.max, matchRange.max), t);
		matchRange = null;
	}
	insertInOrder(addTree);
	returnObject = false;
	}
	
	private void insertInOrder(RangeInTree seq)
	{
		ranges.add(seq);
	}
    
    public void removeRange(int min, int max, AccordionTreeDrawer t) {
	RangeInTree r = null;
	Iterator iter = ranges.iterator();
	while (iter.hasNext())
	{
		RangeInTree curr = (RangeInTree)iter.next();
		if (curr.min == min && curr.max == max && curr.atd == t)
		{
			r = curr;
			break;
		}
	}
	// delete if it it's identical to something previously passed in...
	if (r != null)
		ranges.remove(r); 
    }

    public void clear() {
	ranges.clear();
    }

    void print() {
	RangeInTree rt;
	Iterator iter = ranges.iterator();
	while (iter.hasNext())
	{
	    rt = (RangeInTree)iter.next();
	    System.out.println(" treekey " + rt.atd.getKey() + " min " + rt.min + " max " + rt.max);
	}
    }

    public boolean getEnabled() {return enabled;}
    public void setEnabled(boolean on) { enabled = on;}
    public void setColor(Color c) {col = new Color(c.getRed(), c.getGreen(), c.getBlue(), key);}
    public Color getColor() {return col;}
    public boolean isThisTreeOnly() { return thisTreeOnly;}
    public void setThisTreeOnly(boolean on) { thisTreeOnly = on;}
    public int getKey() { return key; }
	public void setKey(int key) { this.key = key; setColor(col);  }
    public int size() { return ranges.size(); }
	
	public TreeSet getRanges() {
		return ranges;
	}
	
//	public RangeInTree getRange(int i){
//		return (RangeInTree)ranges.get(i);
//	}

	public RangeInTree getFirst(){
		return (RangeInTree)ranges.first();
	}
	
	public RangeInTree getLast(){
		return (RangeInTree)ranges.last();
	}
	
	public int getNumRanges()
	{
		return ranges.size();
	}
	
	
	public String toString()
	{
		String returnString = key+"[";
		Iterator iter = ranges.iterator();
		RangeInTree next = null;
		if (iter.hasNext())
			next =(RangeInTree)iter.next(); 
		while (next != null && iter.hasNext())
		{
			returnString += next + ",\n\t";
			next = (RangeInTree)iter.next();
		}
		if (ranges.size() > 0)
			returnString += next;
		returnString += "]";
		return returnString;
	}
	/* (non-Javadoc)
	 * @see AccordionDrawer.AbstractRangeList#getSplitIndices(boolean)
	 */
	public int[] getSplitIndices(boolean horizontal) {
		int xy = horizontal ? AccordionTreeDrawer.X : AccordionTreeDrawer.Y;
		int[] returnArray = new int[ranges.size() * 2];
		Iterator iter = ranges.iterator();
		int i = 0;
		while (iter.hasNext())
		{
			RangeInTree currRange = (RangeInTree)iter.next(); 
			returnArray[i*2] = currRange.min-1;
			returnArray[i*2+1] = currRange.max;
			i++;
		}
//		System.out.print("GETSPLITS: [");
//		for (i = 0; i < returnArray.length; i++)
//		{
//		    System.out.print(returnArray[i]);
//		    if (i < returnArray.length-1)
//		        System.out.print(", ");
//		    else
//		        System.out.println("]");
//		}
		return returnArray;
	}
	
	/* (non-Javadoc)
	 * @see AccordionDrawer.AbstractRangeList#getSizesOfAllRanges(AccordionDrawer.SplitLine)
	 */
	// ranges should be cell index ranges
	public double[] getSizesOfAllRanges(SplitLine splitLine, int frameNum) {
		Iterator iter = ranges.iterator();
		double[] size = new double[size()];
		int i = 0;
		while (iter.hasNext())
		{
			RangeInTree range = (RangeInTree)iter.next();
			size[i++] = range.getSize(splitLine, frameNum);
		}
		return size;
	}
	public double getUnshrinkableTotal(AccordionDrawer ad, SplitLine splitLine, int frameNum)
	{
		double size = 0.0;
		if (ranges.size() == 0) return size;
		Iterator iter = ranges.iterator();
		RangeInTree rit = (RangeInTree)iter.next();
		RangeInTree betweenRanges = new RangeInTree(0, rit.min-1, rit.atd); // 0 since getsize subtracts 1 from min
		double betweenSize = betweenRanges.getSize(splitLine, frameNum);
		if (betweenSize < ad.minContextPeriphery)
			size += betweenSize;
		int prevMax = rit.max;
		while (iter.hasNext())
		{
			rit = (RangeInTree)iter.next();
			if (iter.hasNext())
			{
				betweenRanges = new RangeInTree(prevMax+1, rit.min-1, rit.atd); // min+1 since getsize subtracts 1 from min
				betweenSize = betweenRanges.getSize(splitLine, frameNum);
				if (betweenSize < ad.minContextInside)
					size += betweenSize;
			}
			prevMax = rit.max;
		}
		betweenRanges = new RangeInTree(rit.max+1, splitLine.getSize(), rit.atd);
		betweenSize = betweenRanges.getSize(splitLine, frameNum);
		if (betweenSize < ad.minContextPeriphery)
			size += betweenSize;
		return size;
	}
	/* (non-Javadoc)
	 * @see AccordionDrawer.AbstractRangeList#onlyThisAD(AccordionDrawer.AccordionDrawer)
	 */
	public AbstractRangeList onlyThisAD(AccordionDrawer d) {
		RangeList newR = new RangeList(key);
		Iterator iter = ranges.iterator();
		while (iter.hasNext())
		{
			RangeInTree r = (RangeInTree)iter.next();
			if (r.atd == d)
				newR.insertInOrder(r);
		}
		return newR;
	}

	// return a range of node indices on splitlines (min+1, max)
	// all ranges are ranges of tree nodes
	// added boolean horiz to fix off-by-one problems between compressing adjacent ranges and comparing adjacent ranges for additions
	public RangeList nodeKeyToSplitLine(int xy, boolean horiz)
	{
		RangeList newR = new RangeList(key);
		Iterator iter = ranges.iterator();
		while (iter.hasNext())
		{
			RangeInTree rit = (RangeInTree)iter.next();
			RangeInTree splitLineRange = rit.getSplitLineRange(xy, horiz);
			newR.addRange(splitLineRange.min, splitLineRange.max, rit.atd);
		}
		return newR;	
	}
	/* (non-Javadoc)
	 * @see AccordionDrawer.AbstractRangeList#flipRangeToShrink()
	 */
	public AbstractRangeList flipRangeToShrink(int xy, AccordionDrawer ad) {
		RangeList returnRangeList = new RangeList(this.key);
		int splitLineSize = ad.getSplitLine(xy).getSize()-1; 
		if (ranges.size() == 0)
		{
			returnRangeList.addRange( 0, splitLineSize, (AccordionTreeDrawer) ad );
			return returnRangeList;
		}
		Iterator flipIter = ranges.iterator();
		RangeInTree prev = (RangeInTree)flipIter.next();
		if (prev.atd != ad)
			System.out.println("Error, drawers don't match: " + prev.atd + " " + ad);
		if (prev.min > 0)
			returnRangeList.addRange(0, prev.min-1, (AccordionTreeDrawer)ad);
		while( flipIter.hasNext())
		{
			RangeInTree curr = (RangeInTree)flipIter.next();
			if (curr.atd != ad)
				System.out.println("Error, drawers don't match: " + curr.atd + " " + ad);
			// do something
			returnRangeList.addRange( prev.max+1, curr.min-1, (AccordionTreeDrawer)ad );
			prev = curr; 
		}
		if (prev.max < splitLineSize)
			returnRangeList.addRange(prev.max+1, splitLineSize, (AccordionTreeDrawer)ad);
		return returnRangeList;
	}


	
    public RangeInTree returnRangeOverlap(RangeInTree rit)
    {
		RangeInTree returnRange = null;
		matchRange = null;
		returnObject = true;
		if (ranges.contains(rit) && matchRange != null)
			returnRange = matchRange;
		matchRange = null;
		returnObject = false;
		return returnRange;
	}
	
	public void cutRange(RangeInTree rit)
	{
		RangeInTree matchingRange = returnRangeOverlap(rit);
		if (matchingRange != null) {
			ranges.remove(matchingRange);
			if (rit.min > matchingRange.min)
				addRange(matchingRange.min, rit.min - 1, rit.atd);
			if (rit.max < matchingRange.max)
				addRange(rit.max + 1, matchingRange.max, rit.atd);
		}
	}
	
	public boolean isThisRangeInList(int min, int max, AccordionTreeDrawer atd)
	{
	    RangeInTree.doAdj = false;
	    boolean returnValue = ranges.contains(new RangeInTree(min, max, atd));
	    RangeInTree.doAdj = true;
	    return returnValue;
	}
	
//	RangeList blockForest = new RangeList(group, asd.listOfSites, siteSplits);
	public RangeList(RangeList group, TreeSet siteList, SplitLine siteSplits)
	{
		Iterator iter = group.ranges.iterator();
		ranges = new TreeSet();
		while (iter.hasNext())
		{
			RangeInTree ritOrig = (RangeInTree)iter.next();
			SplitCell scBlock = SplitCell.getOverlapSplitCell(siteList, new SplitCell(ritOrig.min-1, ritOrig.max));
			int scBlockMinCell = scBlock.min+1;
			if (ritOrig.max - ritOrig.min < scBlock.max - scBlockMinCell)
			{
				int ritOrigCenter = (ritOrig.min + ritOrig.max) / 2; // don't use center of block, use center of marked group
				int dist[] = {ritOrigCenter - scBlockMinCell, scBlock.max - ritOrigCenter};
				int growSize = dist[0] > dist[1] ? dist[0] : dist[1]; // max distance should be beyond risOrig.min,max from center
				ranges.add(new RangeInTree(ritOrigCenter - growSize, ritOrigCenter + growSize, ritOrig.atd));
			}
			else
				ranges.add(ritOrig); // block for this range is too small
		}
	}

};