1 package org.broadinstitute.hellbender.tools.spark.pathseq;
2 
3 import com.esotericsoftware.kryo.Kryo;
4 import com.esotericsoftware.kryo.io.Input;
5 import com.esotericsoftware.kryo.io.Output;
6 import org.broadinstitute.hellbender.CommandLineProgramTest;
7 import org.broadinstitute.hellbender.exceptions.UserException;
8 import org.testng.Assert;
9 import org.testng.annotations.Test;
10 
11 import java.io.*;
12 import java.util.ArrayList;
13 import java.util.HashSet;
14 import java.util.List;
15 import java.util.Set;
16 
17 public class PSTreeUnitTest extends CommandLineProgramTest {
18 
19     @Test
testSerialize()20     public void testSerialize() throws Exception {
21         final PSTree tree = new PSTree(1);
22         tree.addNode(2, "n2", 1, 0, "none");
23         tree.addNode(3, "n3", 1, 0, "none");
24         tree.addNode(4, "n4", 2, 0, "none");
25 
26         try {
27             final File tempFile = createTempFile("test", ".dat");
28             final Kryo kryo = new Kryo();
29             kryo.setReferences(false);
30             Output output = new Output(new FileOutputStream(tempFile));
31             kryo.writeObject(output, tree);
32             output.close();
33 
34             final Input input = new Input(new FileInputStream(tempFile));
35             final PSTree treeIn = kryo.readObject(input, PSTree.class);
36             Assert.assertEquals(treeIn, tree);
37         } catch (FileNotFoundException e) {
38             throw new IOException("Error with Kryo IO", e);
39         }
40     }
41 
42     @Test
testAddNode()43     public void testAddNode() throws Exception {
44         final PSTree tree = new PSTree(1);
45         tree.addNode(2, "n2", 1, 0, "none");
46         tree.addNode(3, "n3", 1, 0, "none");
47         try {
48             tree.addNode(1, "new_root", 1, 0, "root");
49             Assert.fail("Was able to add root node");
50         } catch (IllegalArgumentException e) {
51         }
52         try {
53             tree.addNode(PSTree.NULL_NODE, "n3", 3, 0, "none");
54             Assert.fail("Was able to add node with null id");
55         } catch (IllegalArgumentException e) {
56         }
57         try {
58             tree.addNode(3, null, 3, 0, "none");
59             Assert.fail("Was able to add node with null name");
60         } catch (IllegalArgumentException e) {
61         }
62         try {
63             tree.addNode(3, "n3", PSTree.NULL_NODE, 0, "none");
64             Assert.fail("Was able to add node with null parent");
65         } catch (IllegalArgumentException e) {
66         }
67         try {
68             tree.addNode(3, "n3", 3, 0, null);
69             Assert.fail("Was able to add node with null rank");
70         } catch (IllegalArgumentException e) {
71         }
72     }
73 
74     @Test
testCheckStructure()75     public void testCheckStructure() throws Exception {
76         PSTree tree = new PSTree(1);
77         tree.checkStructure();
78         tree.addNode(4, "n4", 2, 0, "none");
79         tree.addNode(2, "n2", 1, 0, "none");
80         tree.addNode(3, "n3", 1, 0, "none");
81         tree.checkStructure();
82 
83         tree = new PSTree(1);
84         tree.addNode(2, "n2", 2, 0, "none");
85         try {
86             tree.checkStructure();
87             Assert.fail("Tree validated when node self-referencing");
88         } catch (UserException.BadInput e) {
89         }
90 
91         tree = new PSTree(1);
92         tree.addNode(2, "n2", 1, 0, "none");
93         tree.addNode(3, "n3", 1, 0, "none");
94         tree.addNode(4, "n4", 2, 0, "none");
95         tree.addNode(4, "n4", 3, 0, "none");
96         try {
97             tree.checkStructure();
98             Assert.fail("Tree validated when node parent-child points were incorrect");
99         } catch (UserException.BadInput e) {
100         }
101     }
102 
103     @Test
testGetChildrenOf()104     public void testGetChildrenOf() throws Exception {
105         final PSTree tree = new PSTree(1);
106         tree.addNode(2, "n2", 1, 0, "none");
107         tree.addNode(3, "n3", 1, 0, "none");
108         tree.addNode(4, "n4", 2, 0, "none");
109         final Integer[] expectedChildren = {2, 3};
110         Assert.assertEquals(tree.getChildrenOf(1).toArray(), expectedChildren);
111     }
112 
113     @Test
testGetNodeIDs()114     public void testGetNodeIDs() throws Exception {
115         final PSTree tree = new PSTree(1);
116         tree.addNode(2, "n2", 1, 0, "none");
117         final Set<Integer> expectedIDs = new HashSet<>();
118         expectedIDs.add(1);
119         expectedIDs.add(2);
120         Assert.assertEquals(tree.getNodeIDs(), expectedIDs);
121     }
122 
123     @Test
testGetNameOf()124     public void testGetNameOf() throws Exception {
125         final PSTree tree = new PSTree(1);
126         tree.addNode(2, "n2", 1, 0, "rank_of_2");
127         Assert.assertEquals(tree.getNameOf(1), "root", "Name of root was not 'root'");
128         Assert.assertEquals(tree.getNameOf(2), "n2");
129     }
130 
131     @Test
testGetParentOf()132     public void testGetParentOf() throws Exception {
133         final PSTree tree = new PSTree(1);
134         tree.addNode(2, "n2", 1, 0, "none");
135         Assert.assertEquals(tree.getParentOf(1), PSTree.NULL_NODE, "Parent of root was not null");
136         Assert.assertEquals(tree.getParentOf(2), 1);
137     }
138 
139     @Test
testGetRankOf()140     public void testGetRankOf() throws Exception {
141         final PSTree tree = new PSTree(1);
142         tree.addNode(2, "n2", 1, 0, "rank_of_2");
143         Assert.assertEquals(tree.getRankOf(1), "root", "Rank of root was not 'root'");
144         Assert.assertEquals(tree.getRankOf(2), "rank_of_2");
145     }
146 
147     @Test
testGetLengthOf()148     public void testGetLengthOf() throws Exception {
149         final PSTree tree = new PSTree(1);
150         tree.addNode(2, "n2", 1, 10, "rank_of_2");
151         Assert.assertEquals(tree.getLengthOf(1), 0, "Length of root was not 0");
152         Assert.assertEquals(tree.getLengthOf(2), 10);
153     }
154 
155     @Test
testHasNode()156     public void testHasNode() throws Exception {
157         final PSTree tree = new PSTree(1);
158         tree.addNode(2, "n2", 1, 0, "none");
159         Assert.assertTrue(tree.hasNode(1), "Tree did not contain root");
160         Assert.assertTrue(tree.hasNode(2));
161         Assert.assertFalse(tree.hasNode(3));
162     }
163 
164     @Test
testRetainNodes()165     public void testRetainNodes() throws Exception {
166         final PSTree tree = new PSTree(1);
167         tree.checkStructure();
168         tree.addNode(2, "n2", 1, 0, "none");
169         tree.addNode(3, "n3", 1, 0, "none");
170         tree.addNode(4, "n4", 2, 0, "none");
171 
172         final Set<Integer> nodesToKeep = new HashSet<>();
173         nodesToKeep.add(1);
174         nodesToKeep.add(2);
175         nodesToKeep.add(4);
176         tree.retainNodes(nodesToKeep);
177         Assert.assertEquals(tree.getNodeIDs(), nodesToKeep);
178     }
179 
180     @Test
testSetNameOf()181     public void testSetNameOf() throws Exception {
182         final PSTree tree = new PSTree(1);
183         tree.checkStructure();
184         tree.addNode(2, "n2", 1, 0, "none");
185         tree.setNameOf(2, "node_2");
186         Assert.assertEquals(tree.getNameOf(2), "node_2");
187         try {
188             tree.setNameOf(1, "not_root");
189             Assert.fail("Was able to set root name");
190         } catch (IllegalArgumentException e) {
191         }
192         try {
193             tree.setNameOf(PSTree.NULL_NODE, "");
194             Assert.fail("Was able to set node name with id null");
195         } catch (IllegalArgumentException e) {
196         }
197         try {
198             tree.setNameOf(2, null);
199             Assert.fail("Was able to set node name to null");
200         } catch (IllegalArgumentException e) {
201         }
202     }
203 
204     @Test
testSetRankOf()205     public void testSetRankOf() throws Exception {
206         final PSTree tree = new PSTree(1);
207         tree.checkStructure();
208         tree.addNode(2, "n2", 1, 0, "none");
209         tree.setRankOf(2, "rank_2");
210         Assert.assertEquals(tree.getRankOf(2), "rank_2");
211         try {
212             tree.setRankOf(1, "not_root");
213             Assert.fail("Was able to set root rank");
214         } catch (IllegalArgumentException e) {
215         }
216         try {
217             tree.setRankOf(PSTree.NULL_NODE, "");
218             Assert.fail("Was able to set node rank with id null");
219         } catch (IllegalArgumentException e) {
220         }
221         try {
222             tree.setRankOf(2, null);
223             Assert.fail("Was able to set node rank to null");
224         } catch (IllegalArgumentException e) {
225         }
226     }
227 
228     @Test
testSetLengthOf()229     public void testSetLengthOf() throws Exception {
230         final PSTree tree = new PSTree(1);
231         tree.checkStructure();
232         tree.addNode(2, "n2", 1, 0, "none");
233         tree.setLengthOf(2, 5);
234         Assert.assertEquals(tree.getLengthOf(2), 5);
235         try {
236             tree.setLengthOf(1, 5);
237             Assert.fail("Was able to set root length");
238         } catch (IllegalArgumentException e) {
239         }
240         try {
241             tree.setLengthOf(PSTree.NULL_NODE, 5);
242             Assert.fail("Was able to set node length with id null");
243         } catch (IllegalArgumentException e) {
244         }
245     }
246 
247     @Test
testGetPathOf()248     public void testGetPathOf() throws Exception {
249         final PSTree tree = new PSTree(1);
250         tree.checkStructure();
251         tree.addNode(2, "n2", 1, 0, "none");
252         tree.addNode(3, "n3", 1, 0, "none");
253         tree.addNode(4, "n4", 2, 0, "none");
254         final Integer[] expectedPath = {4, 2, 1};
255         final List<Integer> path = tree.getPathOf(4);
256         Assert.assertEquals(path.toArray(), expectedPath);
257         final List<Integer> path_null = tree.getPathOf(PSTree.NULL_NODE);
258         Assert.assertEquals(path_null, new ArrayList<String>());
259 
260         try {
261             tree.getPathOf(5);
262             Assert.fail("Did not throw UserException when asking for path of non-existent node");
263         } catch (UserException e) {
264         }
265     }
266 
267     @Test
testGetLCA()268     public void testGetLCA() throws Exception {
269         final PSTree tree = new PSTree(1);
270         tree.checkStructure();
271         tree.addNode(2, "n2", 1, 0, "none");
272         tree.addNode(3, "n3", 1, 0, "none");
273         tree.addNode(4, "n4", 2, 0, "none");
274         tree.addNode(5, "n5", 3, 0, "none");
275         tree.addNode(6, "n6", 3, 0, "none");
276         tree.addNode(7, "n7", 5, 0, "none");
277 
278         final ArrayList<Integer> nodes = new ArrayList<>();
279         try {
280             tree.getLCA(nodes);
281             Assert.fail("Did not throw exception when asking for LCA of empty set");
282         } catch (Exception e) {
283         }
284 
285         int lca;
286 
287         nodes.clear();
288         nodes.add(1);
289         lca = tree.getLCA(nodes);
290         Assert.assertEquals(1, lca);
291 
292         nodes.clear();
293         nodes.add(4);
294         nodes.add(5);
295         lca = tree.getLCA(nodes);
296         Assert.assertEquals(1, lca);
297 
298         nodes.clear();
299         nodes.add(6);
300         nodes.add(7);
301         lca = tree.getLCA(nodes);
302         Assert.assertEquals(3, lca);
303 
304         nodes.clear();
305         nodes.add(5);
306         nodes.add(7);
307         lca = tree.getLCA(nodes);
308         Assert.assertEquals(5, lca);
309 
310         tree.addNode(8, "n8", 9, 0, "none");
311         nodes.clear();
312         nodes.add(8);
313         nodes.add(2);
314         try {
315             tree.getLCA(nodes);
316             Assert.fail("Did not throw exception when asking for LCA a disconnected node");
317         } catch (Exception e) {
318         }
319     }
320 
321     @Test
testRemoveUnreachableNodes()322     public void testRemoveUnreachableNodes() throws Exception {
323         PSTree tree = new PSTree(1);
324         tree.checkStructure();
325         tree.addNode(2, "n2", 1, 0, "none");
326         tree.addNode(3, "n3", 1, 0, "none");
327         Assert.assertEquals(tree.removeUnreachableNodes(), new HashSet<String>());
328 
329         tree.addNode(4, "n4", 8, 0, "none");
330         tree.addNode(5, "n5", 6, 0, "none");
331         final HashSet<Integer> trueUnreachable = new HashSet<>(2);
332         trueUnreachable.add(4);
333         trueUnreachable.add(5);
334         trueUnreachable.add(6);
335         trueUnreachable.add(8);
336         Assert.assertEquals(tree.removeUnreachableNodes(), trueUnreachable);
337     }
338 
339     @Test
testToString()340     public void testToString() throws Exception {
341         final PSTree tree = new PSTree(1);
342         tree.checkStructure();
343         tree.addNode(2, "n2", 1, 0, "none");
344         tree.addNode(3, "n3", 1, 0, "none");
345         tree.addNode(4, "n4", 2, 0, "none");
346         Assert.assertTrue(!tree.toString().isEmpty());
347         tree.toString();
348     }
349 
350     @Test
testHashCode()351     public void testHashCode() throws Exception {
352         final PSTree tree = new PSTree(1);
353         tree.addNode(2, "n2", 1, 0, "none");
354         tree.addNode(3, "n3", 1, 0, "none");
355         final PSTree tree2 = new PSTree(1);
356         tree2.addNode(2, "n2", 1, 0, "none");
357         tree2.addNode(3, "n3", 1, 0, "none");
358         final PSTree tree3 = new PSTree(1);
359         tree3.addNode(2, "n2", 1, 0, "none");
360         tree3.addNode(3, "not_n3", 1, 0, "none");
361         Assert.assertEquals(tree.hashCode(), tree2.hashCode());
362         Assert.assertNotEquals(tree.hashCode(), tree3.hashCode());
363     }
364 
365 }