forester/java/src/org/forester/phylogeny/iterators/PostorderTreeIterator.java

   1 // $Id:
   2 // FORESTER -- software libraries and applications
   3 // for evolutionary biology research and applications.
   4 //
   5 // Copyright (C) 2008-2009 Christian M. Zmasek
   6 // Copyright (C) 2008-2009 Burnham Institute for Medical Research
   7 // All rights reserved
   8 //
   9 // This library is free software; you can redistribute it and/or
  10 // modify it under the terms of the GNU Lesser General Public
  11 // License as published by the Free Software Foundation; either
  12 // version 2.1 of the License, or (at your option) any later version.
  13 //
  14 // This library is distributed in the hope that it will be useful,
  15 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  16 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  17 // Lesser General Public License for more details.
  18 //
  19 // You should have received a copy of the GNU Lesser General Public
  20 // License along with this library; if not, write to the Free Software
  21 // Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
  22 //
  23 // Contact: phylosoft @ gmail . com
  24 // WWW: www.phylosoft.org/forester
  25
  26 package org.forester.phylogeny.iterators;
  27
  28 import java.util.NoSuchElementException;
  29 import java.util.Stack;
  30
  31 import org.forester.phylogeny.Phylogeny;
  32 import org.forester.phylogeny.PhylogenyNode;
  33
  34 /*
  35  * *
  36  */
  37 public class PostorderTreeIterator implements PhylogenyNodeIterator {
  38
  39     final private Phylogeny                   _tree;
  40     final private PhylogenyNode               _root;
  41     private boolean                           _has_next;
  42     final private Stack<PostOrderStackObject> _stack;
  43
  44     /**
  45      * @param t
  46      *            Phylogeny for which a Iterator is to be constructed.
  47      */
  48     public PostorderTreeIterator( final Phylogeny tree ) throws IllegalArgumentException {
  49         if ( tree.isEmpty() ) {
  50             throw new IllegalArgumentException( "Attempt to use PostorderTreeIterator on an empty phylogeny." );
  51         }
  52         _tree = tree;
  53         _root = getTree().getRoot();
  54         _stack = new Stack<PostOrderStackObject>();
  55         reset();
  56     }
  57
  58     private PhylogenyNode getRoot() {
  59         return _root;
  60     }
  61
  62     private Stack<PostOrderStackObject> getStack() {
  63         return _stack;
  64     }
  65
  66     private Phylogeny getTree() {
  67         return _tree;
  68     }
  69
  70     /**
  71      * DOCUMENT ME!
  72      *
  73      * @return DOCUMENT ME!
  74      */
  75     public boolean hasNext() {
  76         return _has_next;
  77     }
  78
  79     /**
  80      * Advances the Iterator by one.
  81      */
  82     public PhylogenyNode next() throws NoSuchElementException {
  83         if ( !hasNext() ) {
  84             throw new NoSuchElementException( "Attempt to call \"next()\" on iterator which has no more next elements." );
  85         }
  86         while ( true ) {
  87             final PostOrderStackObject si = getStack().pop();
  88             final PhylogenyNode node = si.getNode();
  89             final int phase = si.getPhase();
  90             // if ( node != null ) {
  91             if ( phase > node.getNumberOfDescendants() ) {
  92                 setHasNext( node != getRoot() );
  93                 return node;
  94             }
  95             else {
  96                 getStack().push( new PostOrderStackObject( node, ( phase + 1 ) ) );
  97                 if ( node.isInternal() ) {
  98                     getStack().push( new PostOrderStackObject( node.getChildNode( phase - 1 ), 1 ) );
  99                 }
 100                 // else {
 101                 // getStack().push( new PostOrderStackObject( null, 1 ) );
 102                 // }
 103             }
 104             // }
 105         }
 106     }
 107
 108     /**
 109      * Not supported.
 110      *
 111      */
 112     public void remove() {
 113         throw new UnsupportedOperationException();
 114     }
 115
 116     /**
 117      * DOCUMENT ME!
 118      */
 119     public void reset() {
 120         setHasNext( true );
 121         getStack().clear();
 122         getStack().push( new PostOrderStackObject( getTree().getRoot(), 1 ) );
 123     }
 124
 125     private void setHasNext( final boolean has_next ) {
 126         _has_next = has_next;
 127     }
 128 } // End of class PostorderTreeIterator.