001 /*
002 * CRIMSON
003 * Copyright (c) 2006, Stephen Fisher, Susan Davidson, and Junhyong Kim,
004 * University of Pennsylvania.
005 *
006 * This program is free software; you can redistribute it and/or
007 * modify it under the terms of the GNU General Public License as
008 * published by the Free Software Foundation; either version 2 of the
009 * License, or (at your option) any later version.
010 *
011 * This program is distributed in the hope that it will be useful, but
012 * WITHOUT ANY WARRANTY; without even the implied warranty of
013 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
014 * General Public License for more details.
015 *
016 * You should have received a copy of the GNU General Public License
017 * along with this program; if not, write to the Free Software
018 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
019 * 02110-1301 USA.
020 *
021 * @(#)Species.java
022 */
023
024 package edu.upenn.crimson;
025
026 import java.util.HashSet;
027 import java.util.Iterator;
028
029 /**
030 * A single species object.
031 *
032 * Species can only exist within a tree and thus the species is added
033 * to a tree when it is created. Because species must exist within
034 * trees, copy(Tree) is used instead of clone() when duplicating
035 * a species for inclusion in a subtree.
036 *
037 * @author Stephen Fisher
038 * @version $Id: Species.java,v 1.33 2007/05/16 18:55:58 fisher Exp $
039 */
040
041 public class Species implements Comparable {
042 /**
043 * The ID of the species. This must be unique for each
044 * Species and is case insensitive.
045 */
046 private String id = "";
047
048 /**
049 * Level from root to this species. Can't rely on level for
050 * determining if the species is a root because it's not
051 * guarenteed that level values will be computed for a tree.
052 */
053 private int level = 0;
054
055 /** Length from parent to this species (default = 1.0). */
056 private double stemLength = 0.0;
057
058 /** Length from root to this species. */
059 private double tempDepth = 0.0;
060
061 /** The parent will be null if this Species is the root. */
062 private Species parent = null;
063
064 /** This contains the set of children. */
065 private Species[] children = null;
066
067 /**
068 * This is used by nextChild() to allow for traversing the tree in
069 * a recursive like fashion but without using recursion.
070 * Recursion with very large trees is prone to memory issues.
071 */
072 private int childIndex = -1;
073
074 public Species(int id, Tree tree) {
075 this(String.valueOf(id), tree);
076 }
077
078 public Species(String id, Tree tree) {
079 this(id, 0.0, 0, tree);
080 }
081
082 public Species(String id, double stemLength, int level, Tree tree) {
083 this.id = id.trim().toUpperCase();
084 this.stemLength = stemLength;
085 this.level = level;
086
087 // by protecting against null trees, we are effectively
088 // allowing for the creation of species that are not attached
089 // to trees. These will need to be attached to a Tree
090 // manually.
091 if (tree != null) tree.addSpecies(this);
092 }
093
094 //--------------------------------------------------------------------------
095 // Setters and Getters
096
097 /** The species ID is forced to be upper case. */
098 public void setID(String id) { this.id = id.trim().toUpperCase(); }
099
100 public String getID() { return id; }
101
102 public void setStemLength(double stemLength) { this.stemLength = stemLength; }
103
104 public double getStemLength() { return stemLength; }
105
106 public void setTempDepth(double tempDepth) { this.tempDepth = tempDepth; }
107
108 public double getTempDepth() { return tempDepth; }
109
110 public void setLevel(int level) { this.level = level; }
111
112 public int getLevel() { return level; }
113
114 public void setParent(Species parent) { this.parent = parent; }
115
116 public Species getParent() { return parent; }
117
118 public Species[] getChildren() { return children; }
119
120 //--------------------------------------------------------------------------
121 // Miscellaneous Methods
122
123 /**
124 * This will compute the length to the root, assuming the parent's
125 * root length has already been computed.
126 */
127 public void computeTempDepth() {
128 // if null parent then we're root and have no root length
129 if (parent == null) { this.tempDepth = 0; }
130 else { this.tempDepth = parent.getTempDepth() + stemLength; }
131 }
132
133 /**
134 * This will compute the level of the species, assuming the
135 * parent's level has already been computed.
136 */
137 public void computeLevel() {
138 // if null parent then we're root and have a level of 0
139 if (parent == null) { this.level = 0; }
140 else { this.level = parent.getLevel() + 1; }
141 }
142
143 /**
144 * This will set the temporal depth and level at the same time.
145 * If both values are needed, this is more efficient than setting
146 * each value separately as it will only require propogating
147 * through the tree once.
148 */
149 public void setTempDepth_Level(double parentLength, int level) {
150 this.tempDepth = parentLength + stemLength;
151 this.level = level;
152
153 if (children != null) {
154 for (int i = 0; i < children.length; i++) {
155 children[i].setTempDepth_Level(this.tempDepth, level + 1);
156 }
157 }
158 }
159
160 /**
161 * This will add the child to the set of children and then set the
162 * parent of the child to be this Species object.
163 */
164 public void addChild(Species child) {
165 if (numChildren() == 0) {
166 children = new Species[1];
167 } else {
168 Species[] tmp = new Species[children.length + 1];
169 System.arraycopy(children, 0, tmp, 0, children.length);
170 children = tmp;
171 }
172 children[children.length - 1] = child;
173 child.parent = this;
174 }
175
176 /**
177 * This will remove the child from the set of children. Children
178 * can only be removed by the Tree, so that the Tree can
179 * track the species in the tree.
180 */
181 public void removeChild(Species child) {
182 if (children == null) {
183 return;
184 } else if (children.length == 1) {
185 children = null;
186 } else {
187 Species[] tmp = new Species[children.length - 1];
188 int j = 0;
189 for (int i = 0; i < children.length; i++) {
190 if (children[i] != child) tmp[j++] = children[i];
191 }
192 children = tmp;
193 }
194
195 child.parent = null;
196 }
197
198 /** Returns the number of children. */
199 public int numChildren() {
200 if (children == null) return 0;
201 else return children.length;
202 }
203
204 /**
205 * It is assumed that all trees have a single root. Thus the root
206 * will not have any siblings. If a species doesn't have a parent,
207 * then it is the root and will return an empty HashSet.
208 * Otherwise, the siblings are computed from the parent's
209 * children.
210 */
211 public HashSet getSiblings() {
212 HashSet siblings = new HashSet();
213
214 // if no parent, then this is a root
215 if (parent == null) return siblings;
216
217 // we know the parent has at least one child (us)
218 for (int i = 0; i < parent.children.length; i++) {
219 Species sibling = parent.children[i];
220 if (sibling != this) siblings.add(sibling);
221 }
222
223 return siblings;
224 }
225
226 /**
227 * Returns true if this species is a leaf (ie has no children).
228 */
229 public boolean isLeaf() {
230 if (children == null) return true;
231 else return false;
232 }
233
234 /**
235 * Returns true if this species doesn't have a parent. Can't rely
236 * on level for determining if the species is a root because it's
237 * not guarenteed that level values will be computed for a tree.
238 */
239 public boolean isRoot() {
240 if (parent == null) return true;
241 else return false;
242 }
243
244 /** Returns true if this node is binary. */
245 public boolean isBinary() {
246 if (isLeaf() || numChildren() == 2) {
247 return true;
248 } else {
249 // we have either 1 or more than 2 children, so not binary
250 return false;
251 }
252 }
253
254 /** We use the hash of the ID as the object's hash code. */
255 public int hashCode() { return id.hashCode(); }
256
257 /** When comparing Species to be equal, we compare their IDs. */
258 public boolean equals(Object obj) {
259 if ((obj != null) && (((Species) obj).getID() == id)) return true;
260 return false;
261 }
262
263 /**
264 * When comparing Species objects, we actually just compare the
265 * index values.
266 */
267 public int compareTo(Object obj) { return id.compareTo(((Species) obj).id); }
268
269 /**
270 * This will return a copy of the current species WITHOUT the
271 * parent, children, or level. This is meant to be used when
272 * coping a species from a tree to be included in a subtree. In
273 * this case, the level, parent, and children values are not
274 * meaningful. The current species is stored in origSpecies, so
275 * that tree sampling routines can connect this subtree to the
276 * original tree.
277 */
278 public Species copy(Tree tree) { return new Species(id, stemLength, 0, tree); }
279
280 public String toStringFull() {
281 String out = "";
282
283 out += "ID: " + id + "\n";
284 out += "Level: " + level + "\n";
285 out += "Stem Length: " + stemLength + "\n";
286 out += "Temporal Depth: " + tempDepth + "\n";
287 if (parent != null) {
288 out += "Parent: " + parent.id + "\n";
289 out += "Siblings: ";
290 for (Iterator i = getSiblings().iterator(); i.hasNext();) {
291 Species sibling = (Species) i.next();
292 if (sibling.id != id) out += sibling.id + ",";
293 }
294 out += "\n";
295 } else {
296 out += "Parent: null \n";
297 out += "Siblings: none \n";
298 }
299 if (children != null) {
300 out += "Children: ";
301 for (int i = 0; i < children.length; i++) {
302 out += children[i].id + ",";
303 }
304 out += "\n";
305 } else {
306 out += "Children: none \n";
307 }
308 return out;
309 }
310
311 public String toString() {
312 String out = "";
313
314 out += id + " [" + level + ", " + tempDepth + "]\n";
315
316 return out;
317 }
318
319 /**
320 * This will remove this internal species, linking all children to
321 * our parent and adjusting their stem lengths accordingly. If
322 * this Species is a leaf, then it won't do anything. It returns
323 * true if the species is collapsed and false otherwise. If a
324 * species is collapsed, it's up to the calling routine to remove
325 * the spacies from the Tree.
326 */
327 public boolean collapse() {
328 // nothing to do if this is a leaf
329 if (isLeaf()) return false;
330
331 // only collapse this species, if a single child
332 if (numChildren() == 1) {
333 // get our child
334 Species child = children[0];
335
336 // add child to our parent
337 if (parent == null) {
338 // we are the root, so our child will not have a
339 // stem length or a parent
340 child.setStemLength(0.0);
341 child.setParent(null);
342 } else {
343 // adjust stem length to include our stem length
344 child.setStemLength(stemLength + child.getStemLength());
345
346 // this will set our child's parent
347 parent.addChild(child);
348
349 // we're not root, so remove us from our parent
350 parent.removeChild(this);
351 }
352
353 return true;
354 }
355
356 return false;
357 }
358
359 //--------------------------------------------------------------------------
360 // Tree Related Functions: These functions treat the current
361 // species as a node in a tree.
362
363 /**
364 * This resets the index used by nextChild(). This must be called
365 * before nextChild() is used to traverse a tree.
366 */
367 public void resetChildIndex() {
368 if (numChildren() > 0) childIndex = 0;
369 else childIndex = -1;
370 }
371
372 /**
373 * This will return the true if this is the first child to be
374 * returned. It will return false if no children.
375 */
376 public boolean firstChild() {
377 if (childIndex == 0) return true;
378 else return false;
379 }
380
381 /** This will return true if there are more children. */
382 public boolean hasNextChild() {
383 if ((childIndex > -1) && (childIndex < children.length)) {
384 return true;
385 } else {
386 return false;
387 }
388 }
389
390 /**
391 * This will return the next child keeping track of the children
392 * returned. This can be used to traverse a tree in a recursive
393 * like fashion but without using a recursive routine. The method
394 * resetChildIndex() must be called prior to using this routine,
395 * to reset the index.
396 */
397 public Species nextChild() {
398 if ((childIndex > -1) && (childIndex < children.length)) {
399 childIndex++;
400 return children[childIndex-1];
401 } else {
402 return null;
403 }
404 }
405
406 /**
407 * This will print out this species and all children as a NEXUS
408 * formatted tree. This species will be the root of the tree.
409 * @XXX This will give a stack overflow for deep trees.
410 */
411 public String printNexus() {
412 String out = "";
413
414 if (! isLeaf()) {
415 // add children
416 out += "(";
417 out += children[0].printNexus();
418 for (int i = 1; i < children.length; i++) {
419 out += ", " + children[i].printNexus();
420 }
421 out += ")";
422 }
423
424 // add self
425 out += id + ":" + stemLength;
426
427 return out;
428 }
429
430 /**
431 * This will print out the tree, one species per line, indenting
432 * each level.
433 * @XXX This will give a stack overflow for deep trees.
434 */
435 public String printTree(String indent) {
436 String out = "";
437
438 out += level + " " + indent + id + ": " + tempDepth + " : " + stemLength + "\n";
439 if (children != null) {
440 for (int i = 0; i < children.length; i++) {
441 out += children[i].printTree(indent + ". ");
442 }
443 }
444
445 return out;
446 }
447
448 } // Species.java
449