2 // FORESTER -- software libraries and applications
3 // for evolutionary biology research and applications.
5 // Copyright (C) 2008-2009 Christian M. Zmasek
6 // Copyright (C) 2008-2009 Burnham Institute for Medical Research
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.
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.
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
23 // Contact: phylosoft @ gmail . com
24 // WWW: www.phylosoft.org/forester
26 package org.forester.tools;
28 import java.util.ArrayList;
29 import java.util.HashMap;
30 import java.util.HashSet;
31 import java.util.List;
34 import java.util.SortedMap;
35 import java.util.TreeMap;
37 import org.forester.phylogeny.Phylogeny;
38 import org.forester.phylogeny.PhylogenyNode;
39 import org.forester.phylogeny.iterators.PhylogenyNodeIterator;
41 public class TreeSplitMatrix {
43 private final SortedMap<PhylogenyNode, List<Boolean>> _data;
44 private final Map<Integer, Integer> _positive_counts;
45 private final boolean _strict;
47 public TreeSplitMatrix( final Phylogeny evaluator, final boolean strict, final Phylogeny target ) {
48 Set<PhylogenyNode> target_external_nodes = null;
50 if ( ( target == null ) || target.isEmpty() ) {
51 throw new IllegalArgumentException( "target must not be null or empty if non-strict evalution is expected" );
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" );
59 target_external_nodes.add( n );
62 _data = new TreeMap<PhylogenyNode, List<Boolean>>();
63 _positive_counts = new HashMap<Integer, Integer>();
65 decompose( evaluator, target_external_nodes );
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.
77 public TreeSplitMatrix( final Phylogeny evaluator,
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" );
83 _data = new TreeMap<PhylogenyNode, List<Boolean>>();
84 _positive_counts = new HashMap<Integer, Integer>();
86 decompose( evaluator, target_external_nodes );
89 private boolean contains( final PhylogenyNode node ) {
90 return _data.keySet().contains( node );
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 );
99 private int getNumberOfTrueValuesAt( final int index ) {
100 if ( _positive_counts.containsKey( index ) ) {
101 return _positive_counts.get( index );
106 private boolean getValue( final PhylogenyNode node, final int index ) {
107 if ( _data.containsKey( node ) ) {
108 return _data.get( node ).get( index );
113 private char getValueAsChar( final PhylogenyNode node, final int index ) {
114 if ( getValue( node, index ) ) {
122 private Set<PhylogenyNode> keySet() {
123 return _data.keySet();
126 public boolean match( final Set<PhylogenyNode> query_nodes ) {
127 final Set<PhylogenyNode> my_query_nodes = query_nodes;
129 if ( !keySet().containsAll( my_query_nodes ) ) {
130 throw new IllegalArgumentException( "external nodes of target and evaluator do not match" );
135 // my_query_nodes.retainAll( keySet() );
137 for( int i = 0; i < size(); ++i ) {
138 if ( match( my_query_nodes, i ) ) {
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;
153 if ( q_counts != ( keySet().size() - counts ) ) {
154 negative_matches = false;
156 if ( !positive_matches && !negative_matches ) {
159 for( final PhylogenyNode query_node : query_nodes ) {
160 if ( !contains( query_node ) ) {
162 //TODO remove me after testing
163 throw new RuntimeException( "this should not have happened, for query " + query_node + ":\n"
167 return false; //TODO really?!?!?
170 if ( getValue( query_node, i ) ) {
171 negative_matches = false;
174 positive_matches = false;
176 if ( !positive_matches && !negative_matches ) {
183 private void sanityCheck() {
185 for( final PhylogenyNode key : keySet() ) {
189 else if ( size != size( key ) ) {
190 throw new RuntimeException( "this should not have happened: failed to build split matrix" );
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" );
202 _data.put( n, new ArrayList<Boolean>() );
207 private void setUpValues( final Phylogeny phy, final Set<PhylogenyNode> target_external_nodes ) {
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 );
220 _positive_counts.put( index, _positive_counts.get( index ) + 1 );
224 _data.get( key ).add( index, false );
233 for( final PhylogenyNode key : keySet() ) {
239 private int size( final PhylogenyNode node ) {
240 return _data.get( node ).size();
244 public String toString() {
245 final StringBuffer sb = new StringBuffer();
246 for( final PhylogenyNode key : keySet() ) {
247 sb.append( key.getName() );
249 for( int i = 0; i < size( key ); ++i ) {
251 sb.append( getValueAsChar( key, i ) );
255 return sb.toString();