forester/java/src/org/forester/phylogeny/iterators/PreorderTreeIterator.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 public final class PreorderTreeIterator implements PhylogenyNodeIterator {
  35
  36     final private Phylogeny            _tree;
  37     final private Stack<PhylogenyNode> _stack;
  38
  39     /**
  40      * @param tree
  41      *            Phylogeny for which a Iterator is to be constructed.
  42      */
  43     public PreorderTreeIterator( final Phylogeny tree ) throws IllegalArgumentException {
  44         if ( tree.isEmpty() ) {
  45             throw new IllegalArgumentException( "Attempt to use PreorderTreeIterator on empty tree." );
  46         }
  47         _stack = new Stack<PhylogenyNode>();
  48         _tree = tree;
  49         reset();
  50     }
  51
  52     public PreorderTreeIterator( final PhylogenyNode node ) throws IllegalArgumentException {
  53         _stack = new Stack<PhylogenyNode>();
  54         _tree = null;
  55         reset( node );
  56     }
  57
  58     /*
  59      * (non-Javadoc)
  60      *
  61      * @see java.util.Iterator#hasNext()
  62      */
  63     @Override
  64     public final boolean hasNext() {
  65         return !_stack.isEmpty();
  66     }
  67
  68     /**
  69      * Advances the Iterator by one.
  70      */
  71     @Override
  72     public final PhylogenyNode next() throws NoSuchElementException {
  73         if ( !hasNext() ) {
  74             throw new NoSuchElementException( "Attempt to call \"next()\" on iterator which has no more next elements." );
  75         }
  76         final PhylogenyNode node = _stack.pop();
  77         if ( !node.isExternal() ) {
  78             for( int i = node.getNumberOfDescendants() - 1; i >= 0; --i ) {
  79                 _stack.push( node.getChildNode( i ) );
  80             }
  81         }
  82         return node;
  83     }
  84
  85     /**
  86      * Not supported.
  87      *
  88      */
  89     @Override
  90     public final void remove() {
  91         throw new UnsupportedOperationException();
  92     }
  93
  94     @Override
  95     public final void reset() {
  96         _stack.clear();
  97         _stack.push( _tree.getRoot() );
  98     }
  99
 100     private final void reset( final PhylogenyNode node ) {
 101         _stack.clear();
 102         _stack.push( node );
 103     }
 104 }