Q. Complete the following “TreeProcessingImpl” class ….. so that the unit tests shown below pass? Skeleton Code
|
1 2 3 4 5 6 7 8 |
package com.passing.unittests; import java.util.List; public interface Node<E> { E getValue(); List<Node<E>> getChildren(); } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
package com.passing.unittests; import java.util.List; public class NodeImpl<E> implements Node<E> { private E value; private List<Node<E>> children; public NodeImpl(E value, List<Node<E>> children) { this.value = value; this.children = children; } public E getValue() { return value; } public List<Node<E>> getChildren() { return children; } } |
|
1 2 3 4 5 6 |
package com.passing.unittests; public interface TreeProcessing<E> { abstract double getAverage(Node<E> node); abstract double getSum(Node<E> node); } |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
package com.passing.unittests; public class TreeProcessingImpl<E> implements TreeProcessing<Double> { public double getAverage(Node<Double> node) { return 0; } public double getSum(Node<Double> node) { return 0; } } |
Unit Tests
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
package com.passing.unittests; import java.util.Arrays; import java.util.List; import org.junit.Assert; import org.junit.Before; import org.junit.Test; public class TreeProcessingTest { private TreeProcessing<Double> tp = null; private Node<Double> numberRootNode; @Before public void init() { tp = new TreeProcessingImpl<Double>(); Node<Double> lvl2a = new NodeImpl<Double>(6.0, null); Node<Double> lvl2b = new NodeImpl<Double>(7.0, null); Node<Double> lvl2c = new NodeImpl<Double>(8.0, null); @SuppressWarnings("unchecked") List<Node<Double>> lvl2Children = Arrays.asList(lvl2a, lvl2b, lvl2c); Node<Double> lvl1a = new NodeImpl<Double>(5.0, lvl2Children); Node<Double> lvl1b = new NodeImpl<Double>(9.0, null); @SuppressWarnings("unchecked") List<Node<Double>> lvl1Children = Arrays.asList(lvl1a, lvl1b); numberRootNode = new NodeImpl<Double>(7.0, lvl1Children); } @Test public void testGetAverage() { Assert.assertEquals("Wrong", (6.0+7.0+8.0+5.0+9.0+7.0)/6, tp.getAverage(numberRootNode), 0.01); } @Test public void testSum() { Assert.assertEquals("Wrong", (6.0+7.0+8.0+5.0+9.0+7.0), tp.getSum(numberRootNode), 0.01); } } |
A. Solution 1:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
package com.passing.unittests; import java.util.ArrayDeque; import java.util.Deque; import java.util.List; public class TreeProcessingImpl<E> implements TreeProcessing<Double> { /** * Using iteration */ public double getAverage(Node<Double> node) { Deque<Node<Double>> stack = new ArrayDeque<Node<Double>>(20); stack.push(node); int nodeCount = 0; double total = 0.0; while (!stack.isEmpty()) { Node<Double> currentNode = stack.pop(); if (currentNode != null) { ++nodeCount; total += node.getValue(); } if (currentNode != null && currentNode.getChildren() != null) { List<Node<Double>> children = currentNode.getChildren(); for (Node<Double> child : children) { stack.push(child); } } } return total / nodeCount; } /** * Using recursion */ public double getSum(Node<Double> node) { double sum = 0.0; // handle node if (node != null) { sum += node.getValue(); } // handle children if (node != null && node.getChildren() != null) { for (Node<Double> child : node.getChildren()) { // recursion goes like sum + getSum(child) + getSum(child) + .... sum += getSum(child); } } return sum; // return sum } } |
Solution 2: Using recursion for getAverage(…) and iteration for getSum(…)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 |
package com.passing.unittests; import java.util.ArrayDeque; import java.util.Deque; import java.util.List; public class TreeProcessingImpl<E> implements TreeProcessing<Double> { /** * Using Recursion */ public double getAverage(Node<Double> node){ Result averageResult = getAverageResult(node, new Result()); return averageResult.getSum()/averageResult.getCount(); } private Result getAverageResult(Node<Double> node, Result result) { int count = 0; double sum = 0.0; if(result == null){ result = new Result(); } // handle node if (node != null) { sum += node.getValue(); result.setCount(++count); } // handle children if (node != null && node.getChildren() != null) { for (Node<Double> child : node.getChildren()) { getAverageResult(child, result); //recursion } } result.setSum(sum); return result; // return result } //inner class to store the result private static class Result { int count; double sum; public int getCount() { return count; } public void setCount(int count) { this.count = count; } public double getSum() { return sum; } public void setSum(double sum) { this.sum = sum; } } /** * Using iteration */ public double getSum(Node<Double> node) { Deque<Node<Double>> stack = new ArrayDeque<Node<Double>>(20); stack.push(node); double total = 0.0; while (!stack.isEmpty()) { Node<Double> currentNode = stack.pop(); if (currentNode != null) { total += node.getValue(); } if (currentNode != null && currentNode.getChildren() != null) { List<Node<Double>> children = currentNode.getChildren(); for (Node<Double> child : children) { stack.push(child); } } } return total; } } |
Key…
