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     @Override
  76     public boolean hasNext() {
  77         return _has_next;
  78     }
  79
  80     /**
  81      * Advances the Iterator by one.
  82      */
  83     @Override
  84     public PhylogenyNode next() throws NoSuchElementException {
  85         if ( !hasNext() ) {
  86             throw new NoSuchElementException( "Attempt to call \"next()\" on iterator which has no more next elements." );
  87         }
  88         while ( true ) {
  89             final PostOrderStackObject si = getStack().pop();
  90             final PhylogenyNode node = si.getNode();
  91             final int phase = si.getPhase();
  92             // if ( node != null ) {
  93             if ( phase > node.getNumberOfDescendants() ) {
  94                 setHasNext( node != getRoot() );
  95                 return node;
  96             }
  97             else {
  98                 getStack().push( new PostOrderStackObject( node, ( phase + 1 ) ) );
  99                 if ( node.isInternal() ) {
 100                     getStack().push( new PostOrderStackObject( node.getChildNode( phase - 1 ), 1 ) );
 101                 }
 102                 // else {
 103                 // getStack().push( new PostOrderStackObject( null, 1 ) );
 104                 // }
 105             }
 106             // }
 107         }
 108     }
 109
 110     /**
 111      * Not supported.
 112      *
 113      */
 114     @Override
 115     public void remove() {
 116         throw new UnsupportedOperationException();
 117     }
 118
 119     /**
 120      * DOCUMENT ME!
 121      */
 122     @Override
 123     public void reset() {
 124         setHasNext( true );
 125         getStack().clear();
 126         getStack().push( new PostOrderStackObject( getTree().getRoot(), 1 ) );
 127     }
 128
 129     private void setHasNext( final boolean has_next ) {
 130         _has_next = has_next;
 131     }
 132 } // End of class PostorderTreeIterator.