forester/java/src/org/forester/tools/TreeSplitMatrix.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.tools;
  27
  28 import java.util.ArrayList;
  29 import java.util.HashMap;
  30 import java.util.HashSet;
  31 import java.util.List;
  32 import java.util.Map;
  33 import java.util.Set;
  34 import java.util.SortedMap;
  35 import java.util.TreeMap;
  36
  37 import org.forester.phylogeny.Phylogeny;
  38 import org.forester.phylogeny.PhylogenyNode;
  39 import org.forester.phylogeny.iterators.PhylogenyNodeIterator;
  40
  41 public class TreeSplitMatrix {
  42
  43     private final SortedMap<PhylogenyNode, List<Boolean>> _data;
  44     private final Map<Integer, Integer>                   _positive_counts;
  45     private final boolean                                 _strict;
  46
  47     public TreeSplitMatrix( final Phylogeny evaluator, final boolean strict, final Phylogeny target ) {
  48         Set<PhylogenyNode> target_external_nodes = null;
  49         if ( !strict ) {
  50             if ( ( target == null ) || target.isEmpty() ) {
  51                 throw new IllegalArgumentException( "target must not be null or empty if non-strict evalution is expected" );
  52             }
  53             target_external_nodes = new HashSet<PhylogenyNode>();
  54             for( final PhylogenyNodeIterator it = target.iteratorExternalForward(); it.hasNext(); ) {
  55                 final PhylogenyNode n = it.next();
  56                 if ( target_external_nodes.contains( n ) ) {
  57                     throw new IllegalArgumentException( "node [" + n.toString() + "] of target is not unique" );
  58                 }
  59                 target_external_nodes.add( n );
  60             }
  61         }
  62         _data = new TreeMap<PhylogenyNode, List<Boolean>>();
  63         _positive_counts = new HashMap<Integer, Integer>();
  64         _strict = strict;
  65         decompose( evaluator, target_external_nodes );
  66     }
  67
  68     /**
  69      * If strict is true, target nodes (all external nodes of the phylogeny for
  70      * which support values are to be calculated) is not used for anything during construction.
  71      *
  72      *
  73      * @param target
  74      * @param evaluator
  75      * @param strict
  76      */
  77     public TreeSplitMatrix( final Phylogeny evaluator,
  78                             final boolean strict,
  79                             final Set<PhylogenyNode> target_external_nodes ) {
  80         if ( !strict && ( ( target_external_nodes == null ) || target_external_nodes.isEmpty() ) ) {
  81             throw new IllegalArgumentException( "target nodes list must not be null or empty if non-strict evalution is expected" );
  82         }
  83         _data = new TreeMap<PhylogenyNode, List<Boolean>>();
  84         _positive_counts = new HashMap<Integer, Integer>();
  85         _strict = strict;
  86         decompose( evaluator, target_external_nodes );
  87     }
  88
  89     private boolean contains( final PhylogenyNode node ) {
  90         return _data.keySet().contains( node );
  91     }
  92
  93     private void decompose( final Phylogeny phy, final Set<PhylogenyNode> target_external_nodes ) {
  94         setUpKeys( phy, target_external_nodes );
  95         setUpValues( phy, target_external_nodes );
  96         sanityCheck();
  97     }
  98
  99     private int getNumberOfTrueValuesAt( final int index ) {
 100         if ( _positive_counts.containsKey( index ) ) {
 101             return _positive_counts.get( index );
 102         }
 103         return 0;
 104     }
 105
 106     private boolean getValue( final PhylogenyNode node, final int index ) {
 107         if ( _data.containsKey( node ) ) {
 108             return _data.get( node ).get( index );
 109         }
 110         return false;
 111     }
 112
 113     private char getValueAsChar( final PhylogenyNode node, final int index ) {
 114         if ( getValue( node, index ) ) {
 115             return '.';
 116         }
 117         else {
 118             return ' ';
 119         }
 120     }
 121
 122     private Set<PhylogenyNode> keySet() {
 123         return _data.keySet();
 124     }
 125
 126     public boolean match( final Set<PhylogenyNode> query_nodes ) {
 127         final Set<PhylogenyNode> my_query_nodes = query_nodes;
 128         if ( _strict ) {
 129             if ( !keySet().containsAll( my_query_nodes ) ) {
 130                 throw new IllegalArgumentException( "external nodes of target and evaluator do not match" );
 131             }
 132         }
 133         //else {
 134         //THIS IS WRONG
 135         // my_query_nodes.retainAll( keySet() );
 136         //}
 137         for( int i = 0; i < size(); ++i ) {
 138             if ( match( my_query_nodes, i ) ) {
 139                 return true;
 140             }
 141         }
 142         return false;
 143     }
 144
 145     private boolean match( final Set<PhylogenyNode> query_nodes, final int i ) {
 146         final int counts = getNumberOfTrueValuesAt( i );
 147         final int q_counts = query_nodes.size();
 148         boolean positive_matches = true;
 149         boolean negative_matches = true;
 150         if ( q_counts != counts ) {
 151             positive_matches = false;
 152         }
 153         if ( q_counts != ( keySet().size() - counts ) ) {
 154             negative_matches = false;
 155         }
 156         if ( !positive_matches && !negative_matches ) {
 157             return false;
 158         }
 159         for( final PhylogenyNode query_node : query_nodes ) {
 160             if ( !contains( query_node ) ) {
 161                 if ( _strict ) {
 162                     //TODO remove me after testing
 163                     throw new RuntimeException( "this should not have happened, for query " + query_node + ":\n"
 164                             + toString() );
 165                 }
 166                 else {
 167                     return false; //TODO really?!?!?
 168                 }
 169             }
 170             if ( getValue( query_node, i ) ) {
 171                 negative_matches = false;
 172             }
 173             else {
 174                 positive_matches = false;
 175             }
 176             if ( !positive_matches && !negative_matches ) {
 177                 return false;
 178             }
 179         }
 180         return true;
 181     }
 182
 183     private void sanityCheck() {
 184         int size = -1;
 185         for( final PhylogenyNode key : keySet() ) {
 186             if ( size < 0 ) {
 187                 size = size( key );
 188             }
 189             else if ( size != size( key ) ) {
 190                 throw new RuntimeException( "this should not have happened: failed to build split matrix" );
 191             }
 192         }
 193     }
 194
 195     private void setUpKeys( final Phylogeny phy, final Set<PhylogenyNode> target_external_nodes ) {
 196         for( final PhylogenyNodeIterator it = phy.iteratorExternalForward(); it.hasNext(); ) {
 197             final PhylogenyNode n = it.next();
 198             if ( _strict || target_external_nodes.contains( n ) ) {
 199                 if ( _data.containsKey( n ) ) {
 200                     throw new IllegalArgumentException( "node '" + n.toString() + "' of evaluator is not unique" );
 201                 }
 202                 _data.put( n, new ArrayList<Boolean>() );
 203             }
 204         }
 205     }
 206
 207     private void setUpValues( final Phylogeny phy, final Set<PhylogenyNode> target_external_nodes ) {
 208         int index = 0;
 209         for( final PhylogenyNodeIterator it = phy.iteratorPreorder(); it.hasNext(); ) {
 210             final PhylogenyNode node = it.next();
 211             final List<PhylogenyNode> current_ext_descs = node.getAllExternalDescendants();
 212             for( final PhylogenyNode key : keySet() ) {
 213                 //if ( _strict || target_external_nodes.contains( key ) ) {
 214                 if ( current_ext_descs.contains( key ) ) {
 215                     _data.get( key ).add( index, true );
 216                     if ( !_positive_counts.containsKey( index ) ) {
 217                         _positive_counts.put( index, 1 );
 218                     }
 219                     else {
 220                         _positive_counts.put( index, _positive_counts.get( index ) + 1 );
 221                     }
 222                 }
 223                 else {
 224                     _data.get( key ).add( index, false );
 225                 }
 226                 //}
 227             }
 228             index++;
 229         }
 230     }
 231
 232     private int size() {
 233         for( final PhylogenyNode key : keySet() ) {
 234             return size( key );
 235         }
 236         return 0;
 237     }
 238
 239     private int size( final PhylogenyNode node ) {
 240         return _data.get( node ).size();
 241     }
 242
 243     @Override
 244     public String toString() {
 245         final StringBuffer sb = new StringBuffer();
 246         for( final PhylogenyNode key : keySet() ) {
 247             sb.append( key.getName() );
 248             sb.append( ":" );
 249             for( int i = 0; i < size( key ); ++i ) {
 250                 sb.append( " " );
 251                 sb.append( getValueAsChar( key, i ) );
 252             }
 253             sb.append( "\n" );
 254         }
 255         return sb.toString();
 256     }
 257 }