BoundedRollup implements StreamingRollup<K, V> { public static <K, V extends AdditiveValue<V>> BoundedRollup<K, V> create( V emptyValue, int maxNodes) { return new BoundedRollup<K, V>(maxNodes); } private  BoundedRollup(int maxNodes); static BoundedRollup<K, V> create(
      V emptyValue, int maxNodes); @Override void feedRow(Iterator<K> leafPath, V v); @Override MapNode<K, V> finish(); @Override String toString();  }
@Test public void nodeAndLeafCount() { final List<int[]> list = Lists.newArrayList(); IntArrayCallback callback = new ListCollector(list); for (int n = 0; n < 8; ++n) { list.clear(); TestUtils.generateSpecWithExactSum(n, 2 * n, callback); Collections.sort(list, IntArrayComparator.INSTANCE); BoundedRollup<Integer, LongContent> rollup = BoundedRollup.create(TestUtils.ZERO_LONG_CONTENT, Integer.MAX_VALUE); MapNode<Integer, LongContent> actual = createTree(list, rollup); checkTreeIsComplete(list, n, actual); } }
@Test public void oneNodeAtMost() { final List<int[]> list = Lists.newArrayList(); IntArrayCallback callback = new ListCollector(list); for (int n = 0; n < 8; ++n) { list.clear(); TestUtils.generateSpecWithExactSum(n, 2 * n, callback); Collections.sort(list, IntArrayComparator.INSTANCE); BoundedRollup<Integer, LongContent> rollup = BoundedRollup.create(TestUtils.ZERO_LONG_CONTENT, 1); MapNode<Integer, LongContent> actual = createTree(list, rollup); Assert.assertEquals(MapNode.create(new LongContent(list.size()), ImmutableMap.<Integer, MapNode<Integer, LongContent>>of()), actual); } }
@Test public void subtreeIsOptimalWithinConstraints() { final List<int[]> list = Lists.newArrayList(); IntArrayCallback callback = new ListCollector(list); for (int n = 0; n < 3; ++n) { list.clear(); TestUtils.generateSpecWithExactSum(n, 2 * n, callback); Collections.sort(list, IntArrayComparator.INSTANCE); BoundedRollup<Integer, LongContent> rollup = BoundedRollup.create(TestUtils.ZERO_LONG_CONTENT, Integer.MAX_VALUE); MapNode<Integer, LongContent> fullTreeRoot = createTree(list, rollup); checkTreeIsComplete(list, n, fullTreeRoot); int fullTreeSize = fullTreeRoot.subtreeSizeAndLeafCount()[0]; for (int i = 1; i <= fullTreeSize + 5; ++i) { List<List<MapNode<Integer, LongContent>>> allPossibleExpansions = allPossibleExpansions(fullTreeRoot, i); BoundedRollup<Integer, LongContent> constrainedRollup = BoundedRollup.create(TestUtils.ZERO_LONG_CONTENT, i); MapNode<Integer, LongContent> constrainedTreeRoot = createTree(list, constrainedRollup); List<MapNode<Integer, LongContent>> actual = constrainedTreeRoot.preorder(); List<List<MapNode<Integer, LongContent>>> all = toSortedValueListList(allPossibleExpansions); List<MapNode<Integer, LongContent>> constrained = toSortedValueList(actual); List<List<MapNode<Integer, LongContent>>> allSameSize = Lists.newArrayList(); for (List<MapNode<Integer, LongContent>> row : all) { Assert.assertTrue(row.size() <= constrained.size()); if (row.size() == constrained.size()) { allSameSize.add(row); } } Assert.assertEquals(Collections.max(allSameSize, new ListComparator<MapNode<Integer, LongContent>>( new MapNodeValueComparator<Integer, LongContent>())), constrained); } } }
@Test public void allPossibleExpansionsForRootOnly() { MapNode<Integer, String> root = MapNode.create("x", ImmutableMap.<Integer, MapNode<Integer, String>>of()); Assert.assertTrue(allPossibleExpansions(root, 0).isEmpty()); for (int i = 1; i < 3; ++i) { MoreAsserts.assertContentsAnyOrder(allPossibleExpansions(root, i), ImmutableList.of(root)); } }
@Test public void allPossibleExpansionsForThreeNodes() { MapNode<Integer, String> rightGrandchild = MapNode.create("d", ImmutableMap.<Integer, MapNode<Integer, String>>of()); MapNode<Integer, String> rightChild = MapNode.create("c", ImmutableMap.<Integer, MapNode<Integer, String>>of(2, rightGrandchild)); MapNode<Integer, String> leftChild = MapNode.create("b", ImmutableMap.<Integer, MapNode<Integer, String>>of()); MapNode<Integer, String> root = MapNode.create( "a", ImmutableMap.<Integer, MapNode<Integer, String>>of(0, leftChild, 1, rightChild)); Assert.assertTrue(allPossibleExpansions(root, 0).isEmpty()); MoreAsserts.assertContentsAnyOrder(allPossibleExpansions(root, 1), ImmutableList.of(root)); MoreAsserts.assertContentsAnyOrder(allPossibleExpansions(root, 2), ImmutableList.of(root)); MoreAsserts.assertContentsAnyOrder(toIdentitySetList(allPossibleExpansions(root, 3)), toIdentitySet(ImmutableList.of(root)), toIdentitySet(ImmutableList.of(root, leftChild, rightChild))); List<Set<MapNode<Integer, String>>> actual = toIdentitySetList(allPossibleExpansions(root, 4)); MoreAsserts.assertContentsAnyOrder(actual, toIdentitySet(ImmutableList.of(root)), toIdentitySet(ImmutableList.of(root, leftChild, rightChild)), toIdentitySet(ImmutableList.of(root, leftChild, rightChild, rightGrandchild))); }