Index: /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/io/FormattedOutput.java =================================================================== --- /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/io/FormattedOutput.java (revision 1573) +++ /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/io/FormattedOutput.java (revision 1573) @@ -0,0 +1,311 @@ +// FormattedOutput.java +// +// (c) 1999-2001 PAL Development Core Team +// +// This package may be distributed under the +// terms of the Lesser GNU General Public License (LGPL) + +package de.ugoe.cs.autoquest.tasktrees.alignment.pal.io; + +import java.io.*; +import java.text.*; +import java.util.*; +import java.math.*; + +/** + * tools to simplify formatted output to a stream + * + * @version $Id: FormattedOutput.java,v 1.14 2001/07/13 14:39:13 korbinian Exp $ + * + * @author Korbinian Strimmer + * @author Alexei Drummond + */ +public class FormattedOutput implements Serializable +{ + // + // Public stuff + // + + /** + * create instance of this class + * (note that there is no public constructor + * as this class is a singleton) + */ + public synchronized static FormattedOutput getInstance() + { + if (singleton == null) + { + singleton = new FormattedOutput(); + } + + return singleton; + } + + /** + * print decimal number with a prespecified number + * of digits after the point + * + * @param out output stream + * @param number to be printed + * @param width number of fraction digits + * + * @return length of the string printed + */ + public int displayDecimal(PrintWriter out, double number, int width) + { + String s = getDecimalString(number, width); + + out.print(s); + + return s.length(); + } + + /** + * Returns a decimal string representation of a number with + * constrained width. + */ + public synchronized String getDecimalString(double number, int width) { + nf.setMinimumFractionDigits(width); + nf.setMaximumFractionDigits(width); + + return nf.format(number); + } + + private static final double round(double number, int sf) { + double decimals = Math.floor(Math.log(number) / Math.log(10.0)); + double power = Math.pow(10, decimals - sf+1); + number /= power; + number = Math.round(number); + number *= power; + return number; + } + + //public String getSFString(double number, int sf) { + // double decimals = Math.floor(Math.log(number) / Math.log(10.0)); + // double power = Math.pow(10, decimals - sf); + // number /= power; + // number = Math.round(number); + // number *= power; + // + // return "" + number; + //} + + /** Used by getSFString3() */ + private SFStringInfo getSFStringInfo(String buffer,int sf, boolean includeRightZeros, boolean previousCarry) { + char[] b2 = new char[(includeRightZeros ? buffer.length() : Math.min(sf,buffer.length()))]; + boolean carry = (sf>=buffer.length() ? previousCarry : buffer.charAt(sf) >= '5'); + for(int i = b2.length-1 ; i >=0; i--) { + if(i='5'; + b2[i] = '0'; + } + } + return new SFStringInfo(new String(b2), carry); + + } + + /** + * An alternative version of getSFString which works on the actual string + * Returns a string representing the given number to the number + * of significant figures requested. + */ + public String getSFString(double number, int sf) { + String s = number+""; + String preFullStop = null; + String postFullStop = null; + String postE = null; + + int fullStopIndex = s.indexOf('.'); + int eIndex = s.indexOf('e'); + if(eIndex<0) { + eIndex = s.indexOf('E'); + } + + if(eIndex>=0) { + postE = s.substring(eIndex+1); + } + eIndex = s.length(); + if(fullStopIndex>=0) { + postFullStop = s.substring(fullStopIndex+1,eIndex); + + } else { + fullStopIndex = eIndex; + } + + preFullStop = s.substring(0,fullStopIndex); + + SFStringInfo postFSI = null; + + + boolean postCarry = false; + if(postFullStop!=null) { + int postSF = sf - preFullStop.length(); + if(postSF>0) { + postFSI = getSFStringInfo(postFullStop, postSF, false,false); + postCarry = postFSI.carry; + } else { + + postCarry = postFullStop.charAt(0)>='5'; + } + + } + SFStringInfo preFSI; + preFSI = getSFStringInfo(preFullStop,sf,true,postCarry); + if(preFSI.carry) { + preFSI.string = "1"+preFSI.string; + } + String b; + if(postFSI!=null) { + b = preFSI.string+"."+postFSI.string; + } else { + b = preFSI.string; + } + if(postE != null) { + b+='e'+postE; + } + + while (b.charAt(b.length() - 1) == '0') { + b = b.substring(0, b.length()-1); + } + if (b.charAt(b.length() - 1) == '.') { + b = b.substring(0, b.length()-1); + } + + return b; + } + /** + * print label with a prespecified length + * (label will be shortened or spaces will introduced, if necessary) + * + * @param out output stream + * @param label label to be printed + * @param width desired length + */ + public void displayLabel(PrintWriter out, String label, int width) + { + int len = label.length(); + + if (len == width) + { + // Print as is + out.print(label); + } + else if (len < width) + { + // fill rest with spaces + out.print(label); + multiplePrint(out, ' ', width - len); + } + else + { + // Print first width characters + for (int i = 0; i < width; i++) + { + out.print(label.charAt(i)); + } + } + } + + /** + * print integer, aligned to a reference number, + * (introducing space at the left side) + * + * @param out output stream + * @param num number to be printed + * @param maxNum reference number + */ + public void displayInteger(PrintWriter out, int num, int maxNum) + { + int lenNum = Integer.toString(num).length(); + int lenMaxNum = Integer.toString(maxNum).length(); + + if (lenNum < lenMaxNum) + { + multiplePrint(out, ' ', lenMaxNum - lenNum); + } + out.print(num); + } + + /** + * print whitespace of length of a string displaying a given integer + * + * @param output stream + * @param maxNum number + */ + public void displayIntegerWhite(PrintWriter out, int maxNum) + { + int lenMaxNum = Integer.toString(maxNum).length(); + + multiplePrint(out, ' ', lenMaxNum); + } + + /** + * repeatedly print a character + * + * @param out output stream + * @param c character + * @param num number of repeats + */ + public void multiplePrint(PrintWriter out, char c, int num) + { + for (int i = 0; i < num; i++) + { + out.print(c); + } + } + + /** + * returns of string of a given length of a single character. + * + * @param size length of the string required + * @param c character + */ + public static String space(int size, char c) { + StringBuffer sb = new StringBuffer(); + for (int i = 0; i < size; i++) { + sb.append(c); + } + return new String(sb); + } + + + // + // Private stuff + // + + // private constructor + private FormattedOutput() + { + nf = NumberFormat.getInstance(Locale.UK); + nf.setGroupingUsed(false); + } + + private static FormattedOutput singleton = null; + + private NumberFormat nf; +} + +/** + * helper class + */ +class SFStringInfo +{ + String string; + boolean carry; + + public SFStringInfo(String s, boolean c) + { + this.string = s; + this.carry = c; + } +} Index: /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/io/OutputTarget.java =================================================================== --- /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/io/OutputTarget.java (revision 1573) +++ /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/io/OutputTarget.java (revision 1573) @@ -0,0 +1,107 @@ +// OutputTarget.java +// +// (c) 1999-2001 PAL Development Core Team +// +// This package may be distributed under the +// terms of the Lesser GNU General Public License (LGPL) + + +package de.ugoe.cs.autoquest.tasktrees.alignment.pal.io; + +import java.io.BufferedWriter; +import java.io.FileWriter; +import java.io.IOException; +import java.io.PrintWriter; +import java.io.StringWriter; + + + + +/** + * convenience class to create output streams linked to + * files, stdout, and strings + * + * @version $Id: OutputTarget.java,v 1.3 2001/07/13 14:39:13 korbinian Exp $ + * + * @author Korbinian Strimmer + */ +public class OutputTarget extends PrintWriter +{ + // + // Public stuff + // + + /** + * open file for writing + * + * @param name file name + * + * @return output stream + */ + public static OutputTarget openFile(String name) + throws IOException + { + return new OutputTarget( + new PrintWriter( + new BufferedWriter( + new FileWriter(name)))); + } + + /** + * open standard out + * + * @return output stream + */ + public static OutputTarget openStdOut() + { + return new OutputTarget(new PrintWriter(System.out)); + } + + /** + * "open" string to write into + * + * @return output stream + */ + public static OutputTarget openString() + { + StringWriter sw = new StringWriter(); + + return new OutputTarget(new PrintWriter(sw), sw); + } + + /** + * get string corresponding to current stream created by openString() + * + * @return string + */ + public String getString() + { + if (stringWriter == null) + { + return ""; + } + else + { + return stringWriter.toString(); + } + } + + + // + // Private stuff + // + + private StringWriter stringWriter; + + // Private constructor + private OutputTarget(PrintWriter out) + { + super(out); + } + + private OutputTarget(PrintWriter out, StringWriter sw) + { + super(out); + stringWriter = sw; + } +} Index: /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/misc/Attribute.java =================================================================== --- /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/misc/Attribute.java (revision 1573) +++ /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/misc/Attribute.java (revision 1573) @@ -0,0 +1,82 @@ +// Attribute.java +// +// (c) 1999-2001 PAL Development Core Team +// +// This package may be distributed under the +// terms of the Lesser GNU General Public License (LGPL) + +package de.ugoe.cs.autoquest.tasktrees.alignment.pal.misc; + + + +/** + * An immutable attribute has a name and value. + * A convenience constructor for conversion from + * string to types Boolean, Integer, Double, Float is available. + * + * @version $Id: Attribute.java,v 1.1 2001/11/21 22:17:07 alexi Exp $ + * + * @author Alexei Drummond + */ + + +public class Attribute { + + public static final String STRING = "string"; + public static final String INTEGER = "integer"; + public static final String BOOLEAN = "boolean"; + public static final String DOUBLE = "double"; + public static final String FLOAT = "float"; + + /** the name of this attribute */ + private String name = null; + + /** the value of this attribute */ + private Object value = null; + + /** + * @param name the name of the attribute. + * @param val the value as a string + * @param type a string description of the type the value is. One of 'boolean', + * 'integer', 'double', 'float', 'string' + */ + public Attribute(String name, String val, String type) { + + this.name = name; + + if (type == null) { + try { + value = new Integer(val); + } catch (NumberFormatException nfe1) { + try { + value = new Double(val); + } catch (NumberFormatException nfe2) { + value = val; + } + } + } else if (type.equals(BOOLEAN)) { + value = new Boolean(val); + } else if (type.equals(INTEGER)) { + value = new Integer(val); + } else if (type.equals(DOUBLE)) { + value = new Double(val); + } else if (type.equals(FLOAT)) { + value = new Float(val); + } + value = val; + } + + public Attribute(String name, Object value) { + this.name = name; + this.value = value; + } + + public String getName() { + return name; + } + + public Object getValue() { + return value; + } +} + Index: /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/misc/BranchLimits.java =================================================================== --- /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/misc/BranchLimits.java (revision 1573) +++ /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/misc/BranchLimits.java (revision 1573) @@ -0,0 +1,39 @@ +// BranchLimits.java +// +// (c) 1999-2001 PAL Development Core Team +// +// This package may be distributed under the +// terms of the Lesser GNU General Public License (LGPL) + + +package de.ugoe.cs.autoquest.tasktrees.alignment.pal.misc; + + +/** + * limits for branch lengths + * + * @version $Id: BranchLimits.java,v 1.9 2001/09/09 22:15:16 alexi Exp $ + * + * @author Korbinian Strimmer + */ +public interface BranchLimits +{ + // + // Public stuff + // + + /** minimum branch length */ + double MINARC = 1.0e-9; + + /** maximum branch length */ + double MAXARC = 100.0; + + /** default branch length */ + double DEFAULT_LENGTH = 0.04; + + /** maximum tolerated error when determining branch lengths */ + double ABSTOL = 5.0e-07; + + /** desired fractional digits when determining branch lengths */ + int FRACDIGITS = 6; +} Index: /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/misc/Identifier.java =================================================================== --- /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/misc/Identifier.java (revision 1573) +++ /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/misc/Identifier.java (revision 1573) @@ -0,0 +1,95 @@ +// Identifier.java +// +// (c) 1999-2000 PAL Development Core Team +// +// This package may be distributed under the +// terms of the Lesser GNU General Public License (LGPL) + +package de.ugoe.cs.autoquest.tasktrees.alignment.pal.misc; + +import java.io.Serializable; +import de.ugoe.cs.autoquest.tasktrees.alignment.pal.util.Comparable; + +/** + * An identifier for some sampled data. This will most often be + * for example, the accession number of a DNA sequence, or the + * taxonomic name that the sequence represents, et cetera. + * + * @version $Id: Identifier.java,v 1.6 2001/12/02 22:32:18 matt Exp $ + * + * @author Alexei Drummond + */ + + +public class Identifier implements + Comparable, Nameable { + + private String name = null; + + + public static Identifier ANONYMOUS = new Identifier(""); + + public Identifier() {} + + public Identifier(String name) { + setName(name); + } + + public String toString() { + return getName(); + } + + // implements Comparable interface + + public int compareTo(Object c) { + + return getName().compareTo(((Identifier)c).getName()); + } + + public boolean equals(Object c) { + + if (c instanceof Identifier) { + return getName().equals(((Identifier)c).getName()); + } else return false; + } + + // implements Nameable interface + + public String getName() { + return name; + } + + public void setName(String s) { + name = s; + } + /** + * Translates an array of identifiers into an array of strings + */ + public final static String[] getNames(Identifier[] ids) { + String[] names = new String[ids.length]; + for(int i = 0 ; i < names.length ; i++) { + names[i] = ids[i].getName(); + } + return names; + } + /** + * Translates an array of identifiers into an array of strings, with optional removal of particular identifier + * @param toIgnoreIndex the index of an idetifier to ignore, if <0 no element is ignored + */ + public final static String[] getNames(Identifier[] ids, int toIgnore) { + if(toIgnore<0||toIgnore>=ids.length) { + return getNames(ids); + } + String[] names = new String[ids.length-1]; + int index = 0; + for(int i = 0 ; i < names.length ; i++) { + if(i!=toIgnore) { + names[index] = ids[i].getName(); + index++; + } + } + return names; + } + +} + Index: /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/misc/LabelMapping.java =================================================================== --- /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/misc/LabelMapping.java (revision 1573) +++ /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/misc/LabelMapping.java (revision 1573) @@ -0,0 +1,61 @@ +// LableMapping.java +// +// (c) 1999-2001 PAL Development Core Team +// +// This package may be distributed under the +// terms of the Lesser GNU General Public License (LGPL) + +package de.ugoe.cs.autoquest.tasktrees.alignment.pal.misc; + +/** + * Title: LabelMapping + * Description: Allows for the substitution of one label for another + * @author Matthew Goode + * @version 1.0 + */ +import java.util.*; +public class LabelMapping implements java.io.Serializable { + Hashtable mappings_ = new Hashtable(); + public LabelMapping() { } + + public void addMapping(String id, String label) { + mappings_.put(id,label); + } + public void addMapping(Identifier id, String label) { + if(id!=null&&id.getName()!=null) { + mappings_.put(id.getName(),label); + } + } + /** + * @param names Names + * @param colours associated colours + * @note assumes parallel arrays + */ + public void addMappings(String[] ids, String[] labels) { + for(int i = 0 ; i < ids.length ; i++) { + mappings_.put(ids[i],labels[i]); + } + } + + public String getLabel(String id, String defaultLabel) { + if(id==null||!mappings_.containsKey(id)) { + return defaultLabel; + } + return mappings_.get(id).toString(); + } + public String getLabel(Identifier id, String defaultLabel) { + if(id==null) { + return defaultLabel; + } + return getLabel(id.getName(),defaultLabel); + } + public String getLabel(Identifier id) { + return getLabel(id.getName(),id.getName()); + } + public Identifier getLabelIdentifier(Identifier id) { + if(id==null) { + return null; + } + return new Identifier(getLabel(id.getName(),id.getName())); + } +} Index: /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/misc/Nameable.java =================================================================== --- /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/misc/Nameable.java (revision 1573) +++ /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/misc/Nameable.java (revision 1573) @@ -0,0 +1,33 @@ +// Nameable.java +// +// (c) 1999-2001 PAL Development Core Team +// +// This package may be distributed under the +// terms of the Lesser GNU General Public License (LGPL) + +package de.ugoe.cs.autoquest.tasktrees.alignment.pal.misc; + + +/** + * interface for classes that can be named. + * + * @version $Id: Nameable.java,v 1.2 2001/07/13 14:39:13 korbinian Exp $ + * + * @author Alexei Drummond + */ +public interface Nameable +{ + /** + * get the name of this object. + * + * @return name of this object. + */ + String getName(); + + /** + * set the name of this object. + * + * @param name the new name. + */ + void setName(String name); +} Index: /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/misc/Utils.java =================================================================== --- /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/misc/Utils.java (revision 1573) +++ /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/misc/Utils.java (revision 1573) @@ -0,0 +1,113 @@ +// Utils.java +// +// (c) 1999-2001 PAL Development Core Team +// +// This package may be distributed under the +// terms of the Lesser GNU General Public License (LGPL) + +package de.ugoe.cs.autoquest.tasktrees.alignment.pal.misc; + + + +/** + * Provides some miscellaneous methods. + * + * @version $Id: Utils.java,v 1.9 2001/11/20 19:58:45 alexi Exp $ + * + * @author Matthew Goode + */ +public class Utils { + + /** Clones an array of doubles + * @return null if input is null, otherwise return complete copy. + */ + public static final double[] getCopy(double[] array) { + + if(array == null) { + return null; + } + double[] copy = new double[array.length]; + System.arraycopy(array,0,copy,0,array.length); + return copy; + } + + /** + * Clones an array of doubles + * @return null if input is null, otherwise return complete copy. + */ + public static final double[][] getCopy(double[][] array) { + + if(array == null) { + return null; + } + double[][] copy = new double[array.length][]; + for(int i = 0 ; i < copy.length ; i++) { + copy[i] = new double[array[i].length]; + System.arraycopy(array[i],0,copy[i],0,array[i].length); + } + return copy; + } + + /** + * Clones an array of ints + * @return null if input is null, otherwise return complete copy. + */ + public static final int[] getCopy(int[] array) { + if(array == null) { + return null; + } + int[] copy = new int[array.length]; + System.arraycopy(array,0,copy,0,array.length); + return copy; + } + + /** Copies all of source into dest - assumes dest to be large enough */ + public static final void copy(double[][] source, double[][] dest) { + for(int i = 0 ; i < source.length ; i++) { + System.arraycopy(source[i],0,dest[i],0,source[i].length); + } + } + + /** + * A simple toString method for an array of doubles. + * No fancy formating. + * Puts spaces between each value + */ + public static final String toString(double[] array) { + StringBuffer sb = new StringBuffer(array.length*7); + for(int i = 0 ; i < array.length ; i++) { + sb.append(array[i]); + sb.append(' '); + } + return sb.toString(); + } + /** + * A simple toString method for an array of ints. + * No fancy formating. + * Puts spaces between each value + */ + public static final String toString(int[] array) { + StringBuffer sb = new StringBuffer(array.length*7); + for(int i = 0 ; i < array.length ; i++) { + sb.append(array[i]); + sb.append(' '); + } + return sb.toString(); + } + + /** + * A simple toString method for an array of doubles. + * No fancy formating. + * Puts spaces between each value + */ + public static final String toString(double[][] array) { + String ss = ""; + for(int i = 0 ; i < array.length ; i++) { + ss+= i+":"+toString(array[i])+'\n'; + } + return ss; + } +} + + + Index: /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/tree/AttributeNode.java =================================================================== --- /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/tree/AttributeNode.java (revision 1573) +++ /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/tree/AttributeNode.java (revision 1573) @@ -0,0 +1,61 @@ +// AttributeNode.java +// +// (c) 1999-2001 PAL Development Core Team +// +// This package may be distributed under the +// terms of the Lesser GNU General Public License (LGPL) + + +package de.ugoe.cs.autoquest.tasktrees.alignment.pal.tree; + + +import java.io.*; +import java.util.Enumeration; + + +/** + * interface for a node (includes branch) in a binary/non-binary + * rooted/unrooted tree. Unlike its superclass this node + * can have an arbitrary number of named attributes associated with it. + * + * @version $Id: AttributeNode.java,v 1.4 2001/12/03 11:04:39 korbinian Exp $ + * + * @author Alexei Drummond + * @author Korbinian Strimmer + * + */ + +public interface AttributeNode extends Node { + + /** attribute name for the standard error on a node's height. */ + String NODE_HEIGHT_SE = "node height SE"; + + /** attribute name for the probability of the clade defined by an internal node. */ + String CLADE_PROBABILITY = "clade probability"; + + /** attribute name for the probability of the subtree defined by an internal node. */ + String SUBTREE_PROBABILITY = "subtree probability"; + + /** attribute name for the mean height of this clade in a group of trees. */ + String MEAN_CLADE_HEIGHT = "mean clade height"; + + /** + * Sets a named attribute to the given value. + * @param name the name of the attribute + * @param value the value to set the attribute + */ + void setAttribute(String name, Object value); + + /** + * @return the attribute with the given name or null if it doesn't exist. + * @param name the name of the attribute. + */ + Object getAttribute(String name); + + /** + * @return an enumeration of the attributes that this node has. + */ + Enumeration getAttributeNames(); + +} + Index: /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/tree/FengDoolittleNode.java =================================================================== --- /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/tree/FengDoolittleNode.java (revision 1573) +++ /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/tree/FengDoolittleNode.java (revision 1573) @@ -0,0 +1,467 @@ +// SimpleNode.java +// +// (c) 1999-2001 PAL Development Core Team +// +// This package may be distributed under the +// terms of the Lesser GNU General Public License (LGPL) + + +package de.ugoe.cs.autoquest.tasktrees.alignment.pal.tree; + + +import java.util.ArrayList; + +import de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.NumberSequence; +import de.ugoe.cs.autoquest.tasktrees.alignment.pal.misc.Identifier; +import de.ugoe.cs.autoquest.tasktrees.alignment.pal.misc.LabelMapping; + + +/** + * data structure for a node (includes branch) in a binary/non-binary + * rooted/unrooted tree + * + * @version $Id: SimpleNode.java,v 1.20 2002/01/14 04:16:53 matt Exp $ + * + * @author Korbinian Strimmer + * @author Alexei Drummond + */ +public class FengDoolittleNode implements Node { + + /** parent node */ + private Node parent; + + /** number of node as displayed */ + private int number; + + /** sequences associated with node */ + private ArrayList sequences; + + /** length of branch to parent node */ + private double length; + + /** standard error of length of branch to parent node */ + private double lengthSE; + + /** height of this node */ + private double height; + + /** identifier of node/associated branch */ + private Identifier identifier; + + private Node[] child; + + // the following constructors should eventually become + // "friendly" to prevent anyone calling them directly. + // Instead, the NodeFactory should be used! + + /** constructor default node */ + public FengDoolittleNode() + { + parent = null; + child = null; + length = 0.0; + lengthSE = 0.0; + height = 0.0; + identifier = Identifier.ANONYMOUS; + + number = 0; + sequences = new ArrayList(); + } + + public FengDoolittleNode(String name, double branchLength) { + this(); + identifier = new Identifier(name); + length = branchLength; + } + + + public void reset() + { + parent = null; + child = null; + length = 0.0; + lengthSE = 0.0; + height = 0.0; + identifier = Identifier.ANONYMOUS; + + number = 0; + sequences = null; + } + + public FengDoolittleNode(Node n, boolean keepIds) { + init(n, keepIds); + for (int i = 0; i < n.getChildCount(); i++) { + addChild(new FengDoolittleNode(n.getChild(i), keepIds)); + } + } + + public FengDoolittleNode(Node n, LabelMapping lm) { + init(n, true, lm); + for (int i = 0; i < n.getChildCount(); i++) { + addChild(new FengDoolittleNode(n.getChild(i), lm)); + } + } + + + /** constructor used to clone a node and all children */ + public FengDoolittleNode(Node n) + { + this(n, true); + } + + + + protected void init(Node n) { + init(n, true); + } + /** + * Initialized node instance variables based on given Node. + * children are ignored. + */ + protected void init(Node n, boolean keepId) { + init(n,keepId,null); + } + /** + * Initialized node instance variables based on given Node. + * children are ignored. + * @param lm - may be null + */ + protected void init(Node n, boolean keepId, LabelMapping lm) { + parent = null; + length = n.getBranchLength(); + lengthSE = n.getBranchLengthSE(); + height = n.getNodeHeight(); + if (keepId) { + if(lm!=null) { + identifier = lm.getLabelIdentifier(n.getIdentifier()); + } else { + identifier = n.getIdentifier(); + } + } else { identifier = Identifier.ANONYMOUS; } + + number = n.getNumber(); + sequences = n.getSequences(); + child = null; + } + + /** + * Returns the parent node of this node. + */ + public final Node getParent() { + return parent; + } + + /** Set the parent node of this node. */ + public void setParent(Node node) + { + parent = node; + } + + /** + * removes parent. + */ + public final void removeParent() { + parent = null; + } + + /** + * Returns the sequence at this node, in the form of a String. + */ + public String getSequenceString(int index) { + return sequences.get(index).getSequence().toString(); + } + + /** + * Returns the sequence at this node, in the form of an array of bytes. + */ + public NumberSequence getSequence(int index) { + return sequences.get(index); + } + + /** + * Sets the sequence at this node, in the form of an array of bytes. + */ + public void setSequence(int index,NumberSequence s) { + sequences.set(index, s); + } + + /** + * Get the length of the branch attaching this node to its parent. + */ + public final double getBranchLength() { + return length; + } + + /** + * Set the length of the branch attaching this node to its parent. + */ + public final void setBranchLength(double value) { + length = value; + } + + /** + * Get the length SE of the branch attaching this node to its parent. + */ + public final double getBranchLengthSE() { + return lengthSE; + } + + /** + * Set the length SE of the branch attaching this node to its parent. + */ + public final void setBranchLengthSE(double value) { + lengthSE = value; + } + + + /** + * Get the height of this node relative to the most recent node. + */ + public final double getNodeHeight() { + return height; + } + + /** + * Set the height of this node relative to the most recent node. + */ + public final void setNodeHeight(double value) { + height = Math.abs(value); + } + + /** + * Returns the identifier for this node. + */ + public final Identifier getIdentifier() { + return identifier; + } + + /** + * Set identifier for this node. + */ + public final Identifier setIdentifier(Identifier id) { + identifier = id; + return identifier; + } + + public void setNumber(int n) { + number = n; + } + + public int getNumber() { + return number; + } + + /** + * get child node + * + * @param n number of child + * + * @return child node + */ + public Node getChild(int n) + { + return child[n]; + } + + /** + * set child node + * + * @param n number + * @node node new child node + */ + public void setChild(int n, Node node) + { + child[n] = node; + child[n].setParent(this); + } + + /** + * check whether this node is an internal node + * + * @return result (true or false) + */ + public boolean hasChildren() + { + return !isLeaf(); + } + + /** + * check whether this node is an external node + * + * @return result (true or false) + */ + public boolean isLeaf() { + return (getChildCount() == 0); + } + + /** + * check whether this node is a root node + * + * @return result (true or false) + */ + public boolean isRoot() + { + if (parent == null) + { + return true; + } + else + { + return false; + } + } + + + /** + * add new child node + * + * @param n new child node + */ + public void addChild(Node n) + { + insertChild(n, getChildCount()); + } + + /** + * add new child node (insertion at a specific position) + * + * @param n new child node + + @param pos position + */ + public void insertChild(Node n, int pos) + { + int numChildren = getChildCount(); + + Node[] newChild = new Node[numChildren + 1]; + + for (int i = 0; i < pos; i++) + { + newChild[i] = child[i]; + } + newChild[pos] = n; + for (int i = pos; i < numChildren; i++) + { + newChild[i+1] = child[i]; + } + + child = newChild; + + n.setParent(this); + } + + + /** + * remove child + * + * @param n number of child to be removed + */ + public Node removeChild(int n) + { + int numChildren = getChildCount(); + + if (n >= numChildren) + { + throw new IllegalArgumentException("Nonexistent child"); + } + Node[] newChild = new Node[numChildren-1]; + + for (int i = 0; i < n; i++) + { + newChild[i] = child[i]; + } + + for (int i = n; i < numChildren-1; i++) + { + newChild[i] = child[i+1]; + } + + Node removed = child[n]; + + //remove parent link from removed child! + removed.setParent(null); + + child = newChild; + + return removed; + } + + + + /** + * join two children, introducing a new node/branch in the tree + * that replaces the first child + * + * @param n1 number of first child + * @param n2 number of second child + */ + public void joinChildren( int n1, int n2) { + + if (n1 == n2) { + throw new IllegalArgumentException("CHILDREN MUST BE DIFFERENT"); + } + + int c1, c2; + if (n2 < n1) + { + c1 = n2; + c2 = n1; + } + else + { + c1 = n1; + c2 = n2; + } + + Node newNode = NodeFactory.createNode(); + + Node child1 = this.getChild(c1); + Node child2 = this.getChild(c2); + + setChild(c1, newNode); + newNode.setParent(this); + this.removeChild(c2); // now parent of child2 = null + + newNode.addChild(child1); + newNode.addChild(child2); + + if(newNode instanceof FengDoolittleNode) { + ((FengDoolittleNode) newNode).alignSequences(); + } + + } + + + /** + * Returns the number of children this node has. + */ + public final int getChildCount() { + if (child == null) return 0; + return child.length; + } + + + public ArrayList getSequences() { + return sequences; + } + + + private void alignSequences() { + if(this.getChildCount()<3) { + + Node node1 = getChild(0); + Node node2 = getChild(1); + + int seqCount1 = node1.getSequences().size(); + int seqCount2 = node2.getSequences().size(); + + + + } + else { + + } + + } + + +} Index: /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/tree/NeighborJoiningTree.java =================================================================== --- /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/tree/NeighborJoiningTree.java (revision 1573) +++ /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/tree/NeighborJoiningTree.java (revision 1573) @@ -0,0 +1,204 @@ +// NeighborJoiningTree.java +// +// (c) 1999-2001 PAL Development Core Team +// +// This package may be distributed under the +// terms of the Lesser GNU General Public License (LGPL) + + +// computational complexity O(numSeqs^3) + + +package de.ugoe.cs.autoquest.tasktrees.alignment.pal.tree; + +import de.ugoe.cs.autoquest.tasktrees.alignment.matrix.UPGMAMatrix; + + +/** + * constructs a neighbor-joining tree from pairwise distances + * + * @version $Id: NeighborJoiningTree.java,v 1.9 2001/07/13 14:39:13 korbinian Exp $ + * + * @author Korbinian Strimmer + * @author Alexei Drummond + */ +public class NeighborJoiningTree extends SimpleTree +{ + // + // Public stuff + // + + /** + * construct NJ tree + * + * @param m distance matrix + */ + public NeighborJoiningTree(UPGMAMatrix m) + { + if (m.size() < 3) + { + new IllegalArgumentException("LESS THAN 3 TAXA IN DISTANCE MATRIX"); + } + + init(m); + + //while (numClusters > 3) + while (true) + { + findNextPair(); + newBranchLengths(); + if (numClusters == 3) + { + break; + } + newCluster(); + } + + finish(); + } + + + // + // Private stuff + // + + private int numClusters; + private Node newCluster; + private int besti, abi; + private int bestj, abj; + private int[] alias; + private double[][] distance; + private double[] r; + private double scale; + + private double getDist(int a, int b) + { + return distance[alias[a]][alias[b]]; + } + + private void init(UPGMAMatrix m) + { + numClusters = m.size(); + + distance = new double[numClusters][numClusters]; + for (int i = 0; i < numClusters; i++) + { + for (int j = 0; j < numClusters; j++) + { + distance[i][j] = m.get(i,j); + } + } + + for (int i = 0; i < numClusters; i++) + { + Node tmp = NodeFactory.createNode(); + //tmp.setIdentifier(m.getIdentifier(i)); + getRoot().addChild(tmp); + } + + alias = new int[numClusters]; + for (int i = 0; i < numClusters; i++) + { + alias[i] = i; + } + + r = new double[numClusters]; + } + + private void finish() + { + if (besti != 0 && bestj != 0) + { + getRoot().getChild(0).setBranchLength(updatedDistance(besti, bestj, 0)); + } + else if (besti != 1 && bestj != 1) + { + getRoot().getChild(1).setBranchLength(updatedDistance(besti, bestj, 1)); + } + else + { + getRoot().getChild(2).setBranchLength(updatedDistance(besti, bestj, 2)); + } + distance = null; + + // make node heights available also + NodeUtils.lengths2Heights(getRoot()); + } + + private void findNextPair() + { + for (int i = 0; i < numClusters; i++) + { + r[i] = 0; + for (int j = 0; j < numClusters; j++) + { + r[i] += getDist(i,j); + } + } + + besti = 0; + bestj = 1; + double smax = -1.0; + scale = 1.0/(numClusters-2); + for (int i = 0; i < numClusters-1; i++) + { + for (int j = i+1; j < numClusters; j++) + { + double sij = (r[i] + r[j] ) * scale - getDist(i, j); + + if (sij > smax) + { + smax = sij; + besti = i; + bestj = j; + } + } + } + abi = alias[besti]; + abj = alias[bestj]; + } + + private void newBranchLengths() + { + double dij = getDist(besti, bestj); + double li = (dij + (r[besti]-r[bestj])*scale)*0.5; + double lj = dij - li; // = (dij + (r[bestj]-r[besti])*scale)*0.5 + + getRoot().getChild(besti).setBranchLength(li); + getRoot().getChild(bestj).setBranchLength(lj); + } + + private void newCluster() + { + // Update distances + for (int k = 0; k < numClusters; k++) + { + if (k != besti && k != bestj) + { + int ak = alias[k]; + distance[ak][abi] = distance[abi][ak] = updatedDistance(besti, bestj, k); + } + } + distance[abi][abi] = 0.0; + + // Replace besti with new cluster + getRoot().joinChildren(besti, bestj); + + // Update alias + for (int i = bestj; i < numClusters-1; i++) + { + alias[i] = alias[i+1]; + } + + numClusters--; + } + + /** + * compute updated distance between the new cluster (i,j) + * to any other cluster k + */ + private double updatedDistance(int i, int j, int k) + { + return (getDist(k, i) + getDist(k, j) - getDist(i, j))*0.5; + } +} Index: /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/tree/Node.java =================================================================== --- /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/tree/Node.java (revision 1573) +++ /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/tree/Node.java (revision 1573) @@ -0,0 +1,141 @@ +// Node.java +// +// (c) 1999-2001 PAL Development Core Team +// +// This package may be distributed under the +// terms of the Lesser GNU General Public License (LGPL) + + +package de.ugoe.cs.autoquest.tasktrees.alignment.pal.tree; + + +import java.util.ArrayList; + +import de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.NumberSequence; +import de.ugoe.cs.autoquest.tasktrees.alignment.pal.misc.Identifier; + + + +/** + * interface for a node (includes branch) in a binary/non-binary + * rooted/unrooted tree + * + * @version $Id: Node.java,v 1.20 2001/11/20 07:35:44 matt Exp $ + * + * @author Alexei Drummond + * @author Korbinian Strimmer + * + */ + +public interface Node { + + /** Returns the parent node of this node. */ + Node getParent(); + + /** Set the parent node of this node. */ + void setParent(Node node); + + /** Returns the sequence at this node */ + NumberSequence getSequence(int index); + + /** Sets the sequence using an array of bytes. */ + void setSequence(int index,NumberSequence seq); + + /** return the index of this node */ + int getNumber(); + + /** set the index of this node */ + void setNumber(int number); + + /** Get the length of the branch attaching this node to its parent. */ + double getBranchLength(); + + /** Set the length of the branch attaching this node to its parent. */ + void setBranchLength(double value); + + /** Get the length SE of the branch attaching this node to its parent. */ + double getBranchLengthSE(); + + /** Set the length SE of the branch attaching this node to its parent. */ + void setBranchLengthSE(double value); + + /** Get the height of this node relative to the most recent node. */ + double getNodeHeight(); + + /** Set the height of this node relative to the most recent node. */ + void setNodeHeight(double value); + + /** Returns the identifier for this node. */ + Identifier getIdentifier(); + + /** Set identifier for this node. */ + Identifier setIdentifier(Identifier id); + + /** + * Returns the number of children this node has. + */ + int getChildCount(); + + /** + * check whether this node is an external node + * + * @return result (true or false) + */ + boolean isLeaf(); + + /** + * check whether this node is a root node + * + * @return result (true or false) + */ + boolean isRoot(); + + /** + * get child node + * + * @param n number of child + * + * @return child node + */ + Node getChild(int n); + + /** + * set child node + * + * @param n number + * @node node new child node + */ + void setChild(int n, Node node); + + /** + * add new child node + * + * @param c new child node + */ + void addChild(Node c); + + /** + * add new child node (insertion at a specific position) + * + * @param c new child node + + @param pos position + */ + void insertChild(Node c, int pos); + + + /** + * remove child + * + * @param n number of child to be removed + */ + Node removeChild(int n); + + + ArrayList getSequences(); + + + void joinChildren( int n1, int n2); + + + +} Index: /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/tree/NodeFactory.java =================================================================== --- /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/tree/NodeFactory.java (revision 1573) +++ /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/tree/NodeFactory.java (revision 1573) @@ -0,0 +1,39 @@ +// NodeFactory.java +// +// (c) 1999-2001 PAL Development Core Team +// +// This package may be distributed under the +// terms of the Lesser GNU General Public License (LGPL) + + +package de.ugoe.cs.autoquest.tasktrees.alignment.pal.tree; + + +/** + * Creates nodes + * + * The purpose of this class is to decouple the creation of + * a class of type "Node" from its actual implementation. This + * class should be used instead of calling the constructor + * of an implementation of "Node" + * (at the moment "SimpleNode") as it may change in the future.

+ * + * Other plans: add features here to recyle old nodes rather than + * leaving them to the Java garbage collector + * + * @author Korbinian Strimmer + */ +public class NodeFactory +{ + /** create a node */ + public static Node createNode() + { + return new FengDoolittleNode(); + } + + /** constructor used to clone a node and all children */ + public static Node createNode(Node node) + { + return new FengDoolittleNode(node); + } +} Index: /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/tree/NodeUtils.java =================================================================== --- /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/tree/NodeUtils.java (revision 1573) +++ /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/tree/NodeUtils.java (revision 1573) @@ -0,0 +1,737 @@ +// NodeUtils.java +// +// (c) 1999-2001 PAL Development Core Team +// +// This package may be distributed under the +// terms of the Lesser GNU General Public License (LGPL) + + +package de.ugoe.cs.autoquest.tasktrees.alignment.pal.tree; + +import java.io.*; + +import de.ugoe.cs.autoquest.tasktrees.alignment.pal.io.FormattedOutput; +import de.ugoe.cs.autoquest.tasktrees.alignment.pal.misc.BranchLimits; +import de.ugoe.cs.autoquest.tasktrees.alignment.pal.misc.Identifier; + + +/** + * Helper routines for dealing with nodes. + * + * @version $Id: NodeUtils.java,v 1.19 2002/01/08 02:09:53 alexi Exp $ + * + * @author Alexei Drummond + * @author Korbinian Strimmer + */ +public class NodeUtils { + + /** + * Converts lengths to heights, *without* assuming contemporaneous + * tips. + */ + public static void lengths2Heights(Node root) { + + lengths2Heights(root, getGreatestDistance(root)); + } + + /** + * Converts lengths to heights, but maintains tip heights. + */ + public static void lengths2HeightsKeepTips(Node node, boolean useMax) { + + if (!node.isLeaf()) { + for (int i = 0; i < node.getChildCount(); i++) { + lengths2HeightsKeepTips(node.getChild(i), useMax); + } + + double totalHL = 0.0; + double maxHL = 0.0; + double hl = 0.0; + double maxH = 0.0; + double h = 0.0; + for (int i = 0; i < node.getChildCount(); i++) { + h = node.getChild(i).getNodeHeight(); + hl = node.getChild(i).getBranchLength() + h; + if (hl > maxHL) maxHL = hl; + if (h > maxH) maxH = h; + totalHL += hl; + } + if (useMax) { + hl = maxHL; // set parent height to maximum parent height implied by children + } else { + hl = totalHL / node.getChildCount(); // get mean parent height + if (hl < maxH) hl = maxHL; // if mean parent height is not greater than all children height, fall back on max parent height. + } + node.setNodeHeight(hl); // set new parent height + + // change lengths in children to reflect changes. + for (int i = 0; i < node.getChildCount(); i++) { + h = node.getChild(i).getNodeHeight(); + node.getChild(i).setBranchLength(hl - h); + } + } + } + + + /** + * sets this nodes height value to newHeight and all children's + * height values based on length of branches. + */ + private static void lengths2Heights(Node node, double newHeight) { + + if (!node.isRoot()) { + newHeight -= node.getBranchLength(); + node.setNodeHeight(newHeight); + } else { + node.setNodeHeight(newHeight); + } + + for (int i = 0; i < node.getChildCount(); i++) { + lengths2Heights(node.getChild(i), newHeight); + } + } + + /** + * Exchange field info between two nodes. Specifically + * identifiers, branch lengths, node heights and branch length + * SEs. + */ + public static void exchangeInfo(Node node1, Node node2) { + + Identifier swaps; + double swapd; + + swaps = node1.getIdentifier(); + node1.setIdentifier(node2.getIdentifier()); + node2.setIdentifier(swaps); + + swapd = node1.getBranchLength(); + node1.setBranchLength(node2.getBranchLength()); + node2.setBranchLength(swapd); + + swapd = node1.getNodeHeight(); + node1.setNodeHeight(node2.getNodeHeight()); + node2.setNodeHeight(swapd); + + swapd = node1.getBranchLengthSE(); + node1.setBranchLengthSE(node2.getBranchLengthSE()); + node2.setBranchLengthSE(swapd); + } + + /** + * determines branch lengths of this and all descendent nodes + * from heights + */ + public static void heights2Lengths(Node node) { + heights2Lengths(node, true); //respect minimum + } + + /** + * determines branch lengths of this and all descendent nodes + * from heights + */ + public static void heights2Lengths(Node node, boolean respectMinimum) { + + for (int i = 0; i < node.getChildCount(); i++) { + heights2Lengths(node.getChild(i)); + } + + if (node.isRoot()) { + node.setBranchLength(0.0); + } + else { + node.setBranchLength(node.getParent().getNodeHeight() - node.getNodeHeight()); + if (respectMinimum && (node.getBranchLength() < BranchLimits.MINARC)) + { + node.setBranchLength(BranchLimits.MINARC); + } + } + } + + /** + * determines branch lengths of this node and its immediate descendent nodes + * from heights. + */ + public static void localHeights2Lengths(Node node, boolean respectMinimum) { + + for (int i = 0; i < node.getChildCount(); i++) { + Node child = node.getChild(i); + + child.setBranchLength(node.getNodeHeight() - child.getNodeHeight()); + } + + if (node.isRoot()) { + node.setBranchLength(0.0); + } + else { + node.setBranchLength(node.getParent().getNodeHeight() - node.getNodeHeight()); + if (respectMinimum && (node.getBranchLength() < BranchLimits.MINARC)) + { + node.setBranchLength(BranchLimits.MINARC); + } + } + } + + + /** + * Get the distance to furthest leaf from this nodes parent. + */ + private static double getGreatestDistance(Node node) { + + double distance = 0.0; + if (!node.isLeaf()) { + if (!node.isRoot()) { + distance = node.getBranchLength(); + } + double max = getGreatestDistance(node.getChild(0)); + double posmax = 0.0; + for (int i = 1; i < node.getChildCount(); i++) { + posmax = getGreatestDistance(node.getChild(i)); + if (posmax > max) max = posmax; + } + distance += max; + + return distance; + } else { + return node.getBranchLength(); + } + } + + /** + * Finds the largest child (in terms of node height). + */ + public static double findLargestChild(Node node) { + // find child with largest height + double max = node.getChild(0).getNodeHeight(); + for (int j = 1; j < node.getChildCount(); j++) + { + if (node.getChild(j).getNodeHeight() > max) + { + max = node.getChild(j).getNodeHeight(); + } + } + return max; + } + + /** + * remove child + * + * @param node child node to be removed + */ + public static void removeChild(Node parent, Node child) + { + int rm = -1; + for (int i = 0; i < parent.getChildCount(); i++) + { + if (child == parent.getChild(i)) + { + rm = i; + break; + } + } + + parent.removeChild(rm); + } + + /** + * remove internal branch (collapse node with its parent) + * + * @param node node associated with internal branch + */ + public static void removeBranch(Node node) + { + if (node.isRoot() || node.isLeaf()) + { + throw new IllegalArgumentException("INTERNAL NODE REQUIRED (NOT ROOT)"); + } + + Node parent = node.getParent(); + + // add childs of node to parent + // (node still contains the link to childs + // to allow later restoration) + int numChilds = node.getChildCount(); + for (int i = 0; i < numChilds; i++) + { + parent.addChild(node.getChild(i)); + } + + // remove node from parent + // (link to parent is restored and the + // position is stored) + int rm = -1; + for (int i = 0; i < parent.getChildCount(); i++) + { + if (node == parent.getChild(i)) + { + rm = i; + break; + } + } + parent.removeChild(rm); + node.setParent(parent); + node.setNumber(rm); + } + + /** + * restore internal branch + * + * @param node node associated with internal branch + */ + public static void restoreBranch(Node node) + { + if (node.isRoot() || node.isLeaf()) + { + throw new IllegalArgumentException("INTERNAL NODE REQUIRED (NOT ROOT)"); + } + + Node parent = node.getParent(); + + // remove childs of node from parent and make node their parent + int numChilds = node.getChildCount(); + for (int i = 0; i < numChilds; i++) + { + Node c = node.getChild(i); + removeChild(parent, c); + c.setParent(node); + } + + // insert node into parent + parent.insertChild(node, node.getNumber()); + } + + + + /** + * join two childs, introducing a new node/branch in the tree + * that replaces the first child + * + * @param n1 number of first child + * @param n2 number of second child + */ + public static void joinChilds(Node node, int n1, int n2) { + + if (n1 == n2) { + throw new IllegalArgumentException("CHILDREN MUST BE DIFFERENT"); + } + + int c1, c2; + if (n2 < n1) + { + c1 = n2; + c2 = n1; + } + else + { + c1 = n1; + c2 = n2; + } + + Node newNode = NodeFactory.createNode(); + + Node child1 = node.getChild(c1); + Node child2 = node.getChild(c2); + + node.setChild(c1, newNode); + newNode.setParent(node); + node.removeChild(c2); // now parent of child2 = null + + newNode.addChild(child1); + newNode.addChild(child2); + } + + /** + * determine preorder successor of this node + * + * @return next node + */ + public static Node preorderSuccessor(Node node) { + + Node next = null; + + if (node.isLeaf()) { + Node cn = node, ln = null; // Current and last node + + // Go up + do + { + if (cn.isRoot()) + { + next = cn; + break; + } + ln = cn; + cn = cn.getParent(); + } + while (cn.getChild(cn.getChildCount()-1) == ln); + + // Determine next node + if (next == null) + { + // Go down one node + for (int i = 0; i < cn.getChildCount()-1; i++) + { + if (cn.getChild(i) == ln) + { + next = cn.getChild(i+1); + break; + } + } + } + } + else + { + next = node.getChild(0); + } + + return next; + } + + /** + * determine postorder successor of a node + * + * @return next node + */ + public static Node postorderSuccessor(Node node) { + + Node cn = null; + Node parent = node.getParent(); + + if (node.isRoot()) + { + cn = node; + } + else + { + + // Go up one node + if (parent.getChild(parent.getChildCount()-1) == node) { + return parent; + } + // Go down one node + for (int i = 0; i < parent.getChildCount()-1; i++) + { + if (parent.getChild(i) == node) + { + cn = parent.getChild(i+1); + break; + } + } + } + + // Go down until leaf + while (cn.getChildCount() > 0) + { + + cn = cn.getChild(0); + } + + return cn; + } + + /** + * prints node in New Hamshire format. + */ + static void printNH(PrintWriter out, Node node, + boolean printLengths, boolean printInternalLabels) { + + printNH(out, node, printLengths, printInternalLabels, 0, true); + } + + + static int printNH(PrintWriter out, Node node, + boolean printLengths, boolean printInternalLabels, int column, boolean breakLines) { + + if (breakLines) column = breakLine(out, column); + + if (!node.isLeaf()) + { + out.print("("); + column++; + + for (int i = 0; i < node.getChildCount(); i++) + { + if (i != 0) + { + out.print(","); + column++; + } + + column = printNH(out, node.getChild(i), printLengths, printInternalLabels, column, breakLines); + } + + out.print(")"); + column++; + } + + if (!node.isRoot()) + { + if (node.isLeaf() || printInternalLabels) + { + if (breakLines) column = breakLine(out, column); + + String id = node.getIdentifier().toString(); + out.print(id); + column += id.length(); + } + + if (printLengths) + { + out.print(":"); + column++; + + if (breakLines) column = breakLine(out, column); + + column += FormattedOutput.getInstance().displayDecimal(out, node.getBranchLength(), 7); + } + } + + return column; + } + + private static int breakLine(PrintWriter out, int column) + { + if (column > 70) + { + out.println(); + column = 0; + } + + return column; + } + /** + * Returns the first nodes in this tree that has the + * required identifiers. + * @return null if none of the identifiers names match nodes in tree, else return array which may have + * null "blanks" for corresponding identifiers that do not match any node in the tree + */ + public static final Node[] findByIdentifier(Node node, String[] identifierNames) { + Node[] nodes = new Node[identifierNames.length]; + boolean foundSomething = false; + for(int i = 0 ; i < nodes.length ; i++) { + nodes[i] = findByIdentifier(node,identifierNames[i]); + foundSomething = foundSomething||(nodes[i]!=null); + } + if(!foundSomething) { + return null; + } + return nodes; + } + /** + * Returns the first nodes in this tree that has the + * required identifiers. + */ + public static final Node[] findByIdentifier(Node node, Identifier[] identifiers) { + Node[] nodes = new Node[identifiers.length]; + for(int i = 0 ; i < nodes.length ; i++) { + nodes[i] = findByIdentifier(node,identifiers[i]); + } + return nodes; + } + /** + * Returns the first node in this tree that has the + * required identifier. + */ + public static final Node findByIdentifier(Node node, Identifier identifier) { + return findByIdentifier(node,identifier.getName()); + } + /** + * Returns the first node in this tree that has the + * required identifier. + */ + public static final Node findByIdentifier(Node node, String identifierName) { + + + if (node.getIdentifier().getName().equals(identifierName)) { + return node; + } else { + Node pos = null; + for (int i = 0; i < node.getChildCount(); i++) { + pos = findByIdentifier(node.getChild(i), identifierName); + if (pos != null) return pos; + } + + return pos; + } + } + + /** + * Root tree at this node. + */ + public static Node root(Node node) { + + if (!node.isRoot()) { + + Node myParent = node.getParent(); + removeChild(myParent, node); + + root(myParent); + + while (myParent.getChildCount() == 1) { + myParent = myParent.getChild(0); + } + + node.addChild(myParent); + lengths2Heights(node); + } + return node; + } + + /** + * Root the tree above the node with this identifier. + */ + public static Node rootAbove(Identifier id, Node root) { + return rootAbove(findByIdentifier(root, id)); + } + + /** + * Root tree above this node; + */ + public static Node rootAbove(Node node) { + + if (!node.isRoot()) { + + Node root = NodeFactory.createNode(); + + Node myParent = node.getParent(); + removeChild(myParent, node); + + root(myParent); + + while (myParent.getChildCount() == 1) { + myParent = myParent.getChild(0); + } + + root.addChild(myParent); + root.addChild(node); + + lengths2Heights(root); + + return root; + + } else return node; + } + + /** + * determine distance to root + * + * @return distance to root + */ + public static double getDistanceToRoot(Node node) + { + if (node.isRoot()) + { + return 0.0; + } + else + { + return node.getBranchLength() + getDistanceToRoot(node.getParent()); + } + } + + /** + * Return the number of terminal leaves below this node or 1 if this is + * a terminal leaf. + */ + public static int getLeafCount(Node node) { + + int count = 0; + if (!node.isLeaf()) { + for (int i = 0; i < node.getChildCount(); i++) { + count += getLeafCount(node.getChild(i)); + } + } else { + count = 1; + } + return count; + } + /** + * For two nodes in the tree true if the first node is the ancestor of the second + * + * @param possibleAncestor the node that may be the ancestor of the other node + * @param node the node that may have the other node as it's ancestor + */ + public static boolean isAncestor(Node possibleAncestor, Node node) { + if(node==possibleAncestor) { + return true; + } + while(!node.isRoot()){ + node = node.getParent(); + if(node==possibleAncestor) { + return true; + } + } + return false; + } + + /** + * For a set of nodes in the tree returns the common ancestor closest to all nodes (most recent common ancestor) + * + * @param nodes the nodes to check, is okay if array elements are null! + * @returns null if a at least one node is disjoint from the others nodes disjoint + */ + public static Node getFirstCommonAncestor(Node[] nodes) { + Node currentCA = nodes[0]; + for(int i = 1; i < nodes.length ;i++) { + if(currentCA!=null&&nodes[i]!=null) { + currentCA = getFirstCommonAncestor(currentCA,nodes[i]); + if(currentCA==null) { + return null; + } + } + } + return currentCA; + } + /** + * For two nodes in the tree returns the common ancestor closest to both nodes (most recent common ancestor) + * + * @param nodeOne + * @param nodeTwo + * @returns null if two nodes disjoint (from different trees). May also return either nodeOne or nodeTwo if one node is an ancestor of the other + */ + public static Node getFirstCommonAncestor(Node nodeOne, Node nodeTwo) { + if(isAncestor(nodeTwo, nodeOne)) { + return nodeTwo; + } + if(isAncestor(nodeOne, nodeTwo)) { + return nodeOne; + } + while(!nodeTwo.isRoot()) { + nodeTwo = nodeTwo.getParent(); + if(isAncestor(nodeTwo, nodeOne)) { + return nodeTwo; + } + } + return null; + } + + /** returns number of branches centered around an internal node in an unrooted tree */ + public static final int getUnrootedBranchCount(Node center) { + if (center.isRoot()) { + return center.getChildCount(); + } + else { + return center.getChildCount()+1; + } + } + + /** Attempts to remove the root of a tree by making it polyficating (as opposed to bificating). + */ + public static final Node getUnrooted(Node root) { + if(!root.isRoot()) { + return root; //Already unrooted + } + Node left = root.getChild(0); + Node right = root.getChild(1); + /*if(left.getChildCount()==1) { + if(l + } */ + if(left.getChildCount()>1) { + return root(left); + } + if(right.getChildCount()>1) { + return root(right); + } + return root; //Can't do much + } +} Index: /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/tree/SimpleTree.java =================================================================== --- /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/tree/SimpleTree.java (revision 1573) +++ /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/tree/SimpleTree.java (revision 1573) @@ -0,0 +1,281 @@ +// SimpleTree.java +// +// (c) 1999-2001 PAL Development Core Team +// +// This package may be distributed under the +// terms of the Lesser GNU General Public License (LGPL) + + +package de.ugoe.cs.autoquest.tasktrees.alignment.pal.tree; + +import java.io.PrintWriter; +import java.io.Serializable; +import java.io.StringWriter; +import java.util.Hashtable; + +import de.ugoe.cs.autoquest.tasktrees.alignment.pal.misc.Identifier; +import de.ugoe.cs.autoquest.tasktrees.alignment.pal.misc.LabelMapping; + + + +/** + * data structure for a binary/non-binary rooted/unrooted trees + * + * @version $Id: SimpleTree.java,v 1.19 2002/01/13 23:13:24 matt Exp $ + * + * @author Alexei Drummond + * @author Korbinian Strimmer + * + */ +public class SimpleTree implements Tree +{ + // + // This class has explicit serialization code so if you alter any fields please alter + // the serialization code too (make sure you use a new version number - see readObject/writeObject + // Thanks, Matthew + + // + // Public stuff + // + + // + // Private stuff + /** root node */ + private Node root; + + /** list of internal nodes (including root) */ + private Node[] internalNode = null; + + /** number of internal nodes (including root) */ + private int numInternalNodes; + + /** list of external nodes */ + private Node[] externalNode = null; + + /** number of external nodes */ + private int numExternalNodes; + + /** attributes attached to this tree. */ + private Hashtable[] attributes = null; + + + + /** constructor tree consisting solely of root node */ + public SimpleTree() { + + // Default configuration + root = new FengDoolittleNode(); + root.setIdentifier(new Identifier("ROOT")); + root.setBranchLength(0.0); + root.setBranchLengthSE(0.0); + } + + /** constructor taking a root node */ + public SimpleTree(Node r) { + + root = r; + createNodeList(); + } + + /** clone constructor */ + public SimpleTree(Tree tree) + { + root = new FengDoolittleNode(tree.getRoot()); + createNodeList(); + } + + /** clone constructor */ + public SimpleTree(Tree tree, boolean keepIdentifiers) + { + root = new FengDoolittleNode(tree.getRoot(), keepIdentifiers); + createNodeList(); + } + /** + * clone constructor + * @param lm - a label mapping use for translating the original label names into something else + */ + public SimpleTree(Tree tree, LabelMapping lm) + { + root = new FengDoolittleNode(tree.getRoot(), lm); + createNodeList(); + } + + + + /** + * Returns the number of external nodes. + */ + public final int getExternalNodeCount() { + if(externalNode==null) { + createNodeList(); + } + return numExternalNodes; + } + + /** + * Returns the ith external node. + */ + public final Node getExternalNode(int i) { + if(externalNode==null) { + createNodeList(); + } + return externalNode[i]; + } + + /** + * Returns the number of internal nodes. + */ + public final int getInternalNodeCount() { + if(internalNode==null) { + createNodeList(); + } + return numInternalNodes; + } + + /** + * Returns the ith internal node. + */ + public final Node getInternalNode(int i) { + if(internalNode==null) { + createNodeList(); + } + return internalNode[i]; + } + + /** + * Returns the root node of this tree. + */ + public final Node getRoot() { + return root; + } + + /** + * Set a new node as root node. + */ + public final void setRoot(Node r) { + root = r; + createNodeList(); + } + + /** count and list external and internal nodes and + compute heights of each node */ + public void createNodeList() + { + numInternalNodes = 0; + numExternalNodes = 0; + Node node = root; + do + { + node = NodeUtils.postorderSuccessor(node); + if (node.isLeaf()) + { + node.setNumber(numExternalNodes); + numExternalNodes++; + } + else + { + node.setNumber(numInternalNodes); + numInternalNodes++; + } + } + while(node != root); + + internalNode = new Node[numInternalNodes]; + externalNode = new Node[numExternalNodes]; + node = root; + do + { + node = NodeUtils.postorderSuccessor(node); + if (node.isLeaf()) + { + externalNode[node.getNumber()] = node; + } + else + { + internalNode[node.getNumber()] = node; + } + } + while(node != root); + + // compute heights if it seems necessary + if (root.getNodeHeight() == 0.0) { + NodeUtils.lengths2Heights(root); + } + } + + /** + * return node with number num (as displayed in ASCII tree) + * + * @param num number of node + * + * @return node + */ + public Node findNode(int num) + { + createNodeList(); + + if (num <= numExternalNodes) + { + return externalNode[num-1]; + } + else + { + return internalNode[num-1-numExternalNodes]; + } + } + + private int getIndex(Node node) { + if (node.isLeaf()) return node.getNumber(); + return getExternalNodeCount() + node.getNumber(); + } + + /** + * Sets an named attribute for a given node. + * @param node the node whose attribute is being set. + * @param name the name of the attribute. + * @param value the new value of the attribute. + */ + public void setAttribute(Node node, String name, Object value) { + if (node instanceof AttributeNode) { + ((AttributeNode)node).setAttribute(name, value); + } else { + int index = getIndex(node); + if (attributes == null) { + attributes = new Hashtable[getExternalNodeCount() + getInternalNodeCount()]; + } + if (attributes[index] == null) { + attributes[index] = new Hashtable(); + } + attributes[index].put(name, value); + } + } + + public String toString() { + StringWriter sw = new StringWriter(); + NodeUtils.printNH(new PrintWriter(sw), getRoot(), false, true, 0, true); + sw.write(";"); + return sw.toString(); + } + + /** + * @return an object representing the named attributed for the numbered node. + * @param node the node being interrogated. + * @param name the name of the attribute of interest. + */ + public Object getAttribute(Node node, String name) { + if (node instanceof AttributeNode) { + return ((AttributeNode)node).getAttribute(name); + } else { + int index = getIndex(node); + if (attributes == null || attributes[index] == null) { + return null; + } + return attributes[index].get(name); + } + } + + + + + +} Index: /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/tree/Tree.java =================================================================== --- /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/tree/Tree.java (revision 1573) +++ /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/tree/Tree.java (revision 1573) @@ -0,0 +1,75 @@ +// Tree.java +// +// (c) 1999-2001 PAL Development Core Team +// +// This package may be distributed under the +// terms of the Lesser GNU General Public License (LGPL) + + +package de.ugoe.cs.autoquest.tasktrees.alignment.pal.tree; + + + +/** + * Interface for a phylogenetic or genealogical tree. + * + * @version $Id: Tree.java,v 1.17 2001/11/20 03:44:49 alexi Exp $ + * + * @author Alexei Drummond + */ +public interface Tree { + + /** + * @return the root node of this tree. + */ + Node getRoot(); + + /** + * This method constructs a tree from the given root node. + * @param root the root node of the tree to construct. + */ + void setRoot(Node root); + + /** + * @return a count of the number of external nodes (tips) in this + * tree. + */ + int getExternalNodeCount(); + + /** + * @return a count of the number of internal nodes (and hence clades) + * in this tree. + */ + int getInternalNodeCount(); + + /** + * @return the ith external node in the tree. + */ + Node getExternalNode(int i); + + /** + * @return the ith internal node in the tree. + */ + Node getInternalNode(int i); + + /** + * This method is called to ensure that the calls to other methods + * in this interface are valid. + */ + void createNodeList(); + + /** + * Sets an named attribute for a given node. + * @param node the node whose attribute is being set. + * @param name the name of the attribute. + * @param value the new value of the attribute. + */ + void setAttribute(Node node, String name, Object value); + + /** + * @return an object representing the named attributed for the numbered node. + * @param node the node being interrogated. + * @param name the name of the attribute of interest. + */ + Object getAttribute(Node node, String name); +} Index: /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/tree/TreeParseException.java =================================================================== --- /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/tree/TreeParseException.java (revision 1573) +++ /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/tree/TreeParseException.java (revision 1573) @@ -0,0 +1,28 @@ +// TreeParseException.java +// +// (c) 1999-2001 PAL Development Core Team +// +// This package may be distributed under the +// terms of the Lesser GNU General Public License (LGPL) + + +package de.ugoe.cs.autoquest.tasktrees.alignment.pal.tree; + + +/** + * exception thrown by ReadTree + * + * @author Korbinian Strimmer + */ +public class TreeParseException extends Exception +{ + + private static final long serialVersionUID = -6890313232581908150L; + + public TreeParseException() {} + + public TreeParseException(String msg) + { + super(msg); + } +} Index: /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/tree/UPGMATree.java =================================================================== --- /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/tree/UPGMATree.java (revision 1573) +++ /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/tree/UPGMATree.java (revision 1573) @@ -0,0 +1,215 @@ +// UPGMATree.java +// +// (c) 1999-2001 PAL Development Core Team +// +// This package may be distributed under the +// terms of the Lesser GNU General Public License (LGPL) + +// Known bugs and limitations: +// - computational complexity O(numSeqs^3) +// (this could be brought down to O(numSeqs^2) +// but this needs more clever programming ...) + + +package de.ugoe.cs.autoquest.tasktrees.alignment.pal.tree; + +import java.util.ArrayList; + +import de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.NumberSequence; +import de.ugoe.cs.autoquest.tasktrees.alignment.matrix.UPGMAMatrix; +import de.ugoe.cs.autoquest.tasktrees.alignment.pal.misc.Identifier; + + +/** + * constructs a UPGMA tree from pairwise distances + * + * @version $Id: UPGMATree.java,v 1.9 2001/07/13 14:39:13 korbinian Exp $ + * + * @author Korbinian Strimmer + * @author Alexei Drummond + */ +public class UPGMATree extends SimpleTree +{ + // + // Public stuff + // + + /** + * constructor UPGMA tree + * @param numberseqs + * + * @param m distance matrix + */ + public UPGMATree(ArrayList numberseqs, UPGMAMatrix m) + { + if (m.size() < 2) + { + new IllegalArgumentException("LESS THAN 2 TAXA IN DISTANCE MATRIX"); + } + + + init(m); + + while (true) + { + findNextPair(); + newBranchLengths(); + + if (numClusters == 2) + { + break; + } + + newCluster(); + } + + finish(); + createNodeList(); + } + + + // + // Private stuff + // + private ArrayList numberseqs; + private int numClusters; + private int besti, abi; + private int bestj, abj; + private int[] alias; + private double[][] distance; + + private double[] height; + private int[] oc; + + private double getDist(int a, int b) + { + return distance[alias[a]][alias[b]]; + } + + private void init(UPGMAMatrix m) + { + numClusters = m.size(); + + distance = new double[numClusters][numClusters]; + for (int i = 0; i < numClusters; i++) + { + for (int j = 0; j < numClusters; j++) + { + distance[i][j] = m.get(i,j); + } + } + + for (int i = 0; i < numClusters; i++) + { + Node tmp = NodeFactory.createNode(); + tmp.setIdentifier(new Identifier(Integer.toString(i))); + tmp.setSequence(0, numberseqs.get(i)); + getRoot().addChild(tmp); + } + + alias = new int[numClusters]; + for (int i = 0; i < numClusters; i++) + { + alias[i] = i; + } + + height = new double[numClusters]; + oc = new int[numClusters]; + for (int i = 0; i < numClusters; i++) + { + height[i] = 0.0; + oc[i] = 1; + } + } + + private void finish() + { + distance = null; + } + + private void findNextPair() + { + besti = 0; + bestj = 1; + double dmin = getDist(0, 1); + for (int i = 0; i < numClusters-1; i++) + { + for (int j = i+1; j < numClusters; j++) + { + if (getDist(i, j) < dmin) + { + dmin = getDist(i, j); + besti = i; + bestj = j; + } + } + } + abi = alias[besti]; + abj = alias[bestj]; + System.out.println("Found best pair: " + abi + "/" +abj + " - "+ besti+ "/"+bestj +" with distance " + dmin); + + } + + private void newBranchLengths() + { + double dij = getDist(besti, bestj); + + getRoot().getChild(besti).setBranchLength(dij/2.0-height[abi]); + getRoot().getChild(bestj).setBranchLength(dij/2.0-height[abj]); + } + + private void newCluster() + { + // Update distances + for (int k = 0; k < numClusters; k++) + { + if (k != besti && k != bestj) + { + int ak = alias[k]; + double updated = updatedDistance(besti,bestj,k); + distance[ak][abi] = distance[abi][ak] = updated; + } + } + distance[abi][abi] = 0.0; + + // Update UPGMA variables + height[abi] = getDist(besti, bestj)/2.0; + oc[abi] += oc[abj]; + + // Index besti now represent the new cluster + getRoot().joinChildren(besti, bestj); + + // Update alias + for (int i = bestj; i < numClusters-1; i++) + { + alias[i] = alias[i+1]; + } + + numClusters--; + } + + + /** + * compute updated distance between the new cluster (i,j) + * to any other cluster k + */ + private double updatedDistance(int i, int j, int k) + { + int ai = alias[i]; + int aj = alias[j]; + + double ocsum = (double) (oc[ai]+oc[aj]); + double idist = getDist(k,i); + double jdist = getDist(k,j); + //TODO: Dirty hack to deal with infinity, insert proper solution here + if(Double.isInfinite(idist)) { + idist = 100; + } + if(Double.isInfinite(jdist)) { + jdist = 100; + } + + return (oc[ai]/ocsum)*idist+ + (oc[aj]/ocsum)*jdist; + } +} Index: /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/util/Comparable.java =================================================================== --- /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/util/Comparable.java (revision 1573) +++ /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/util/Comparable.java (revision 1573) @@ -0,0 +1,35 @@ +// Comparable.java +// +// (c) 1999-2001 PAL Development Core Team +// +// This package may be distributed under the +// terms of the Lesser GNU General Public License (LGPL) + +package de.ugoe.cs.autoquest.tasktrees.alignment.pal.util; + +/** + * interface for an object that is comparable. + * This interface is analogous to the Comparable interface in + * Java 1.2, and it should be superceded by the JDK 1.2 collections + * framework when PAL is moved to 1.2. + * + * @version $Id: Comparable.java,v 1.2 2001/07/13 14:39:13 korbinian Exp $ + * + * @author Alexei Drummond + */ +public interface Comparable +{ + /** + * Returns a number representing the ordering relationship that + * the object has with the given object. + * A negative number indicates that the object is "smaller" than + * the parameter, a positive number means it is "larger" and zero + * indicates that the objects are equal. + */ + int compareTo(Object o); + + /** + * Returns true if this object is equal to the given object. + */ + boolean equals(Object o); +} Index: /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/util/ComparableDouble.java =================================================================== --- /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/util/ComparableDouble.java (revision 1573) +++ /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/util/ComparableDouble.java (revision 1573) @@ -0,0 +1,49 @@ +// ComparableDouble.java +// +// (c) 1999-2001 PAL Development Core Team +// +// This package may be distributed under the +// terms of the Lesser GNU General Public License (LGPL) + +package de.ugoe.cs.autoquest.tasktrees.alignment.pal.util; + +/** + * This class is unfortunate but necessary to conform to JDK 1.1 + * + * @version $Id: ComparableDouble.java,v 1.3 2001/07/13 14:39:13 korbinian Exp $ + * + * @author Alexei Drummond + */ +public class ComparableDouble implements Comparable { + + private double value; + + public ComparableDouble(double d) { + value = d; + } + + public int compareTo(Object o) { + + ComparableDouble cd = (ComparableDouble)o; + + if (value < cd.value) { + return -1; + } else if (value > cd.value) { + return 1; + } else return 0; + } + + public boolean equals(Object o) { + + ComparableDouble cd = (ComparableDouble)o; + return cd.value == value; + } + + public double doubleValue() { + return value; + } + + public String toString() { + return value + ""; + } +} Index: /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/util/Comparator.java =================================================================== --- /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/util/Comparator.java (revision 1573) +++ /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/util/Comparator.java (revision 1573) @@ -0,0 +1,36 @@ +// Comparator.java +// +// (c) 1999-2001 PAL Development Core Team +// +// This package may be distributed under the +// terms of the Lesser GNU General Public License (LGPL) + +package de.ugoe.cs.autoquest.tasktrees.alignment.pal.util; + +/** + * interface for an object that can compare other objects for the + * purposes of ordering them. + * This interface is analogous to the Comparator interface in + * Java 1.2 and higher, and it should be superceded by the collections + * framework when PAL is moved to 1.2 or higher. + * + * @version $Id: Comparator.java,v 1.2 2001/07/13 14:39:13 korbinian Exp $ + * + * @author Alexei Drummond + */ +public interface Comparator +{ + /** + * Returns a number representing the ordering relationship that + * the two objects have. + * A negative number indicates that the first object is "smaller" than + * the second object, a positive number means it is "larger" and zero + * indicates that the objects are equal. + */ + int compare(Object o1, Object o2); + + /** + * Returns true if the two objects are equal. + */ + boolean equals(Object o1, Object o2); +}