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: https://sites.google.com/site/cmzmasek/home/software/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 final 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     final private PhylogenyNode getRoot() {
  59         return _root;
  60     }
  61
  62     final private Stack<PostOrderStackObject> getStack() {
  63         return _stack;
  64     }
  65
  66     final private Phylogeny getTree() {
  67         return _tree;
  68     }
  69
  70     @Override
  71     final public boolean hasNext() {
  72         return _has_next;
  73     }
  74
  75     /**
  76      * Advances the Iterator by one.
  77      */
  78     @Override
  79     final public PhylogenyNode next() throws NoSuchElementException {
  80         if ( !hasNext() ) {
  81             throw new NoSuchElementException( "Attempt to call \"next()\" on iterator which has no more next elements." );
  82         }
  83         while ( true ) {
  84             final PostOrderStackObject si = getStack().pop();
  85             final PhylogenyNode node = si.getNode();
  86             final int phase = si.getPhase();
  87             if ( phase > node.getNumberOfDescendants() ) {
  88                 setHasNext( node != getRoot() );
  89                 return node;
  90             }
  91             else {
  92                 getStack().push( new PostOrderStackObject( node, ( phase + 1 ) ) );
  93                 if ( node.isInternal() ) {
  94                     getStack().push( new PostOrderStackObject( node.getChildNode( phase - 1 ), 1 ) );
  95                 }
  96             }
  97         }
  98     }
  99
 100     @Override
 101     final public void remove() {
 102         throw new UnsupportedOperationException();
 103     }
 104
 105     @Override
 106     final public void reset() {
 107         setHasNext( true );
 108         getStack().clear();
 109         getStack().push( new PostOrderStackObject( getTree().getRoot(), 1 ) );
 110     }
 111
 112     final private void setHasNext( final boolean has_next ) {
 113         _has_next = has_next;
 114     }
 115 }