Details
diff --git a/invoice/src/main/java/org/killbill/billing/invoice/tree/TreePrinter.java b/invoice/src/main/java/org/killbill/billing/invoice/tree/TreePrinter.java
new file mode 100644
index 0000000..72a5bdd
--- /dev/null
+++ b/invoice/src/main/java/org/killbill/billing/invoice/tree/TreePrinter.java
@@ -0,0 +1,281 @@
+/*
+ * Copyright 2014-2016 Groupon, Inc
+ * Copyright 2014-2016 The Billing Project, LLC
+ *
+ * The Billing Project licenses this file to you under the Apache License, version 2.0
+ * (the "License"); you may not use this file except in compliance with the
+ * License. You may obtain a copy of the License at:
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+ * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+ * License for the specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.killbill.billing.invoice.tree;
+
+import java.util.HashMap;
+import java.util.LinkedHashMap;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Map;
+import java.util.SortedMap;
+import java.util.TreeMap;
+import java.util.concurrent.atomic.AtomicInteger;
+
+public class TreePrinter {
+
+ public static String print(final ItemsNodeInterval root) {
+ return print(buildCoordinates(root));
+ }
+
+ private static String print(final SortedMap<XY, ItemsNodeInterval> tree) {
+ // Make left most node start at X=0
+ translate(tree);
+
+ final AtomicInteger totalOrdering = new AtomicInteger(64);
+ final Map<String, ItemsNodeInterval> legend = new LinkedHashMap<String, ItemsNodeInterval>();
+
+ final List<StringBuilder> builders = new LinkedList<StringBuilder>();
+ for (int level = 0; level >= maxOffset(tree).Y; level--) {
+ builders.add(new StringBuilder());
+ // Draw edges for that level
+ drawLevel(true, level, tree, builders, totalOrdering, legend);
+
+ // Draw nodes for that level
+ builders.add(new StringBuilder());
+ drawLevel(false, level, tree, builders, totalOrdering, legend);
+ }
+
+ final StringBuilder builder = new StringBuilder();
+ for (final StringBuilder levelBuilder : builders) {
+ builder.append(levelBuilder.toString());
+ }
+
+ builder.append("\n");
+ for (final String key : legend.keySet()) {
+ builder.append(key).append(": ");
+ appendNodeDetails(legend.get(key), builder);
+ builder.append("\n");
+ }
+ return builder.toString();
+ }
+
+ private static void drawLevel(final boolean drawEdges,
+ final int level,
+ final SortedMap<XY, ItemsNodeInterval> tree,
+ final List<StringBuilder> builders,
+ final AtomicInteger totalOrdering,
+ final Map<String, ItemsNodeInterval> legend) {
+ if (drawEdges && level == 0) {
+ // Nothing to do for root
+ return;
+ }
+
+ final StringBuilder builder = builders.get(builders.size() - 1);
+
+ int posX = 0;
+ boolean sibling;
+ for (final XY levelXY : tree.keySet()) {
+ if (levelXY.Y > level) {
+ // Sorted - we haven't reached that level yet
+ continue;
+ } else if (levelXY.Y < level) {
+ // Sorted - we are done for that level
+ break;
+ }
+
+ sibling = levelXY.parent == null;
+ while (posX < levelXY.X) {
+ if (drawEdges || !sibling || level == 0) {
+ builder.append(" ");
+ } else {
+ // Link siblings
+ builder.append("-");
+ }
+ posX++;
+ }
+
+ if (drawEdges) {
+ if (sibling) {
+ builder.append(" ");
+ } else {
+ builder.append("/");
+ }
+ } else {
+ if (sibling && level != 0) {
+ builder.append("");
+ }
+
+ // Print this node
+ String node = Character.toString((char) totalOrdering.incrementAndGet());
+ if (sibling && level != 0) {
+ node = node.toLowerCase();
+ }
+ legend.put(node, tree.get(levelXY));
+ builder.append(node);
+ }
+ posX++;
+ }
+ builder.append("\n");
+ }
+
+ private static void appendNodeDetails(final ItemsNodeInterval interval, final StringBuilder builder) {
+ builder.append("[")
+ .append(interval.getStart())
+ .append(",")
+ .append(interval.getEnd())
+ .append("]");
+
+ if (interval.getItems().isEmpty()) {
+ return;
+ }
+
+ builder.append("(");
+ final List<Item> items = interval.getItems();
+ for (int i = 0; i < items.size(); i++) {
+ final Item item = items.get(i);
+ if (i > 0) {
+ builder.append(",");
+ }
+ builder.append(item.getAction().name().charAt(0));
+ }
+ builder.append(")");
+ }
+
+ public static SortedMap<XY, ItemsNodeInterval> buildCoordinates(final ItemsNodeInterval root) {
+ final XY reference = new XY(0, 0);
+
+ final SortedMap<XY, ItemsNodeInterval> result = new TreeMap<XY, ItemsNodeInterval>();
+ result.put(reference, root);
+ result.putAll(buildCoordinates(root, reference));
+
+ return result;
+ }
+
+ public static Map<XY, ItemsNodeInterval> buildCoordinates(final ItemsNodeInterval root, final XY initialCoords) {
+ final Map<XY, ItemsNodeInterval> result = new HashMap<XY, ItemsNodeInterval>();
+ if (root == null) {
+ return result;
+ }
+
+ // Compute the coordinate of the left most child
+ ItemsNodeInterval curChild = (ItemsNodeInterval) root.getLeftChild();
+ if (curChild == null) {
+ return result;
+ }
+
+ XY curXY = leftChildXY(initialCoords);
+ result.put(curXY, curChild);
+ // Compute the coordinates of the tree below that child
+ result.putAll(buildCoordinates(curChild, curXY));
+
+ curChild = (ItemsNodeInterval) curChild.getRightSibling();
+ while (curChild != null) {
+ curXY = rightSiblingXY(curXY);
+
+ // Compute the coordinates of the tree below that child
+ final Map<XY, ItemsNodeInterval> subtree = buildCoordinates(curChild, curXY);
+ final XY offset = translate(subtree);
+ translate(offset, curXY);
+ result.put(curXY, curChild);
+ result.putAll(subtree);
+
+ curChild = (ItemsNodeInterval) curChild.getRightSibling();
+ }
+
+ return result;
+ }
+
+ private static XY translate(final Map<XY, ItemsNodeInterval> subtree) {
+ final XY offset = maxOffset(subtree);
+ for (final XY xy : subtree.keySet()) {
+ translate(offset, xy);
+ }
+ return offset;
+ }
+
+ private static void translate(final XY offset, final XY xy) {
+ xy.X = xy.X - offset.X;
+ }
+
+ private static XY maxOffset(final Map<XY, ItemsNodeInterval> tree) {
+ final XY res = new XY(0, 0);
+ for (final XY xy : tree.keySet()) {
+ if (xy.X < res.X) {
+ res.X = xy.X;
+ }
+ if (xy.Y < res.Y) {
+ res.Y = xy.Y;
+ }
+ }
+ return res;
+ }
+
+ private static XY leftChildXY(final XY parent) {
+ return new XY(parent.X - 1, parent.Y - 1, parent);
+ }
+
+ private static XY rightSiblingXY(final XY leftSibling) {
+ return new XY(leftSibling.X + 1, leftSibling.Y);
+ }
+
+ static class XY implements Comparable<XY> {
+
+ int X;
+ int Y;
+ XY parent;
+
+ public XY(final int x, final int y) {
+ this(x, y, null);
+ }
+
+ public XY(final int x, final int y, final XY parent) {
+ X = x;
+ Y = y;
+ this.parent = parent;
+ }
+
+ @Override
+ public String toString() {
+ final StringBuilder sb = new StringBuilder("(");
+ sb.append(X);
+ sb.append(",").append(Y);
+ sb.append(')');
+ return sb.toString();
+ }
+
+ @Override
+ public boolean equals(final Object o) {
+ if (this == o) {
+ return true;
+ }
+ if (o == null || getClass() != o.getClass()) {
+ return false;
+ }
+
+ final XY xy = (XY) o;
+
+ if (X != xy.X) {
+ return false;
+ }
+ return Y == xy.Y;
+
+ }
+
+ @Override
+ public int hashCode() {
+ int result = X;
+ result = 31 * result + Y;
+ return result;
+ }
+
+ @Override
+ public int compareTo(final XY o) {
+ return Y == o.Y ? X < o.X ? -1 : X == o.X ? 0 : 1 : Y < o.Y ? 1 : -1;
+ }
+ }
+}
diff --git a/invoice/src/test/java/org/killbill/billing/invoice/tree/TestSubscriptionItemTree.java b/invoice/src/test/java/org/killbill/billing/invoice/tree/TestSubscriptionItemTree.java
index 9f592b3..26f4170 100644
--- a/invoice/src/test/java/org/killbill/billing/invoice/tree/TestSubscriptionItemTree.java
+++ b/invoice/src/test/java/org/killbill/billing/invoice/tree/TestSubscriptionItemTree.java
@@ -63,6 +63,58 @@ public class TestSubscriptionItemTree extends InvoiceTestSuiteNoDB {
private final String phaseName = "my-phase";
private final Currency currency = Currency.USD;
+ @Test(groups = "fast", description = "Complex multi-level tree, mostly used to test the tree printer")
+ public void testMultipleLevels() throws Exception {
+ final LocalDate startDate = new LocalDate(2014, 1, 1);
+ final LocalDate endDate = new LocalDate(2014, 2, 1);
+
+ final LocalDate startRepairDate1 = new LocalDate(2014, 1, 10);
+ final LocalDate endRepairDate1 = new LocalDate(2014, 1, 15);
+
+ final LocalDate startRepairDate11 = new LocalDate(2014, 1, 10);
+ final LocalDate endRepairDate12 = new LocalDate(2014, 1, 12);
+
+ final LocalDate startRepairDate2 = new LocalDate(2014, 1, 20);
+ final LocalDate endRepairDate2 = new LocalDate(2014, 1, 25);
+
+ final LocalDate startRepairDate21 = new LocalDate(2014, 1, 22);
+ final LocalDate endRepairDate22 = new LocalDate(2014, 1, 23);
+
+ final BigDecimal rate = BigDecimal.TEN;
+ final BigDecimal amount = rate;
+
+ final InvoiceItem initial = new RecurringInvoiceItem(invoiceId, accountId, bundleId, subscriptionId, planName, phaseName, startDate, endDate, amount, rate, currency);
+
+ final InvoiceItem newItem1 = new RecurringInvoiceItem(invoiceId, accountId, bundleId, subscriptionId, planName, phaseName, startRepairDate1, endRepairDate1, amount, rate, currency);
+ final InvoiceItem repair1 = new RepairAdjInvoiceItem(invoiceId, accountId, startRepairDate1, endRepairDate1, amount.negate(), currency, initial.getId());
+
+ final InvoiceItem newItem11 = new RecurringInvoiceItem(invoiceId, accountId, bundleId, subscriptionId, planName, phaseName, startRepairDate11, endRepairDate12, amount, rate, currency);
+ final InvoiceItem repair12 = new RepairAdjInvoiceItem(invoiceId, accountId, startRepairDate11, endRepairDate12, amount.negate(), currency, newItem1.getId());
+
+ final InvoiceItem newItem2 = new RecurringInvoiceItem(invoiceId, accountId, bundleId, subscriptionId, planName, phaseName, startRepairDate2, endRepairDate2, amount, rate, currency);
+ final InvoiceItem repair2 = new RepairAdjInvoiceItem(invoiceId, accountId, startRepairDate2, endRepairDate2, amount.negate(), currency, initial.getId());
+
+ final InvoiceItem newItem21 = new RecurringInvoiceItem(invoiceId, accountId, bundleId, subscriptionId, planName, phaseName, startRepairDate21, endRepairDate22, amount, rate, currency);
+ final InvoiceItem repair22 = new RepairAdjInvoiceItem(invoiceId, accountId, startRepairDate21, endRepairDate22, amount.negate(), currency, newItem2.getId());
+
+ final SubscriptionItemTree tree = new SubscriptionItemTree(subscriptionId, invoiceId);
+ tree.addItem(initial);
+ tree.addItem(newItem1);
+ tree.addItem(repair1);
+ tree.addItem(newItem11);
+ tree.addItem(repair12);
+ tree.addItem(newItem2);
+ tree.addItem(repair2);
+ tree.addItem(newItem21);
+ tree.addItem(repair22);
+
+ tree.build();
+ //printTree(tree);
+
+ tree.flatten(true);
+ //printTree(tree);
+ }
+
@Test(groups = "fast")
public void testWithExistingSplitRecurring() {
@@ -1441,9 +1493,13 @@ public class TestSubscriptionItemTree extends InvoiceTestSuiteNoDB {
Assert.assertEquals(previousExistingSize, 3);
}
- private void printTree(final SubscriptionItemTree tree) throws IOException {
+ private void printTreeJSON(final SubscriptionItemTree tree) throws IOException {
final ByteArrayOutputStream outputStream = new ByteArrayOutputStream();
tree.getRoot().jsonSerializeTree(OBJECT_MAPPER, outputStream);
System.out.println(outputStream.toString("UTF-8"));
}
+
+ private void printTree(final SubscriptionItemTree tree) throws IOException {
+ System.out.println(TreePrinter.print(tree.getRoot()));
+ }
}
diff --git a/invoice/src/test/java/org/killbill/billing/invoice/tree/TestTreePrinter.java b/invoice/src/test/java/org/killbill/billing/invoice/tree/TestTreePrinter.java
new file mode 100644
index 0000000..6159bdc
--- /dev/null
+++ b/invoice/src/test/java/org/killbill/billing/invoice/tree/TestTreePrinter.java
@@ -0,0 +1,140 @@
+/*
+ * Copyright 2014-2016 Groupon, Inc
+ * Copyright 2014-2016 The Billing Project, LLC
+ *
+ * The Billing Project licenses this file to you under the Apache License, version 2.0
+ * (the "License"); you may not use this file except in compliance with the
+ * License. You may obtain a copy of the License at:
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+ * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+ * License for the specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.killbill.billing.invoice.tree;
+
+import java.math.BigDecimal;
+import java.util.Map;
+import java.util.SortedMap;
+
+import org.joda.time.LocalDate;
+import org.killbill.billing.invoice.InvoiceTestSuiteNoDB;
+import org.killbill.billing.invoice.api.InvoiceItem;
+import org.killbill.billing.invoice.tree.Item.ItemAction;
+import org.killbill.billing.invoice.tree.TreePrinter.XY;
+import org.mockito.Mockito;
+import org.testng.Assert;
+import org.testng.annotations.BeforeMethod;
+import org.testng.annotations.Test;
+
+public class TestTreePrinter extends InvoiceTestSuiteNoDB {
+
+ private ItemsNodeInterval root;
+ private ItemsNodeInterval node11;
+ private ItemsNodeInterval node21;
+ private ItemsNodeInterval node22;
+ private ItemsNodeInterval node12;
+ private ItemsNodeInterval node23;
+ private ItemsNodeInterval node31;
+
+ @BeforeMethod(groups = "fast")
+ public void setUp() throws Exception {
+ final InvoiceItem item = Mockito.mock(InvoiceItem.class);
+ Mockito.when(item.getAmount()).thenReturn(BigDecimal.ZERO);
+
+ root = new ItemsNodeInterval(null, new Item(item, new LocalDate(2016, 1, 1), new LocalDate(2016, 2, 1), null, ItemAction.ADD));
+
+ node11 = new ItemsNodeInterval(root, new Item(item, new LocalDate(2016, 1, 10), new LocalDate(2016, 1, 15), null, ItemAction.ADD));
+ node21 = new ItemsNodeInterval(node11, new Item(item, new LocalDate(2016, 1, 10), new LocalDate(2016, 1, 12), null, ItemAction.ADD));
+ node22 = new ItemsNodeInterval(node11, new Item(item, new LocalDate(2016, 1, 14), new LocalDate(2016, 1, 15), null, ItemAction.ADD));
+
+ node12 = new ItemsNodeInterval(root, new Item(item, new LocalDate(2016, 1, 20), new LocalDate(2016, 1, 25), null, ItemAction.ADD));
+ node23 = new ItemsNodeInterval(node12, new Item(item, new LocalDate(2016, 1, 22), new LocalDate(2016, 1, 24), null, ItemAction.ADD));
+ node31 = new ItemsNodeInterval(node23, new Item(item, new LocalDate(2016, 1, 22), new LocalDate(2016, 1, 23), null, ItemAction.ADD));
+ }
+
+ @Test(groups = "fast")
+ public void testSimpleTranslate() throws Exception {
+ root.leftChild = node11;
+ node11.rightSibling = node12;
+ node12.leftChild = node23;
+
+ final SortedMap<XY, ItemsNodeInterval> coords = TreePrinter.buildCoordinates(root);
+ Assert.assertEquals(coords.size(), 4);
+ Assert.assertEquals(coords.get(new XY(0, 0)), root);
+ Assert.assertEquals(coords.get(new XY(-1, -1)), node11);
+ Assert.assertEquals(coords.get(new XY(1, -1)), node12);
+ Assert.assertEquals(coords.get(new XY(0, -2)), node23);
+ //System.out.println(TreePrinter.print(root));
+ }
+
+ @Test(groups = "fast")
+ public void testComplexMultiLevelTree() throws Exception {
+ Map<XY, ItemsNodeInterval> coords = TreePrinter.buildCoordinates(root);
+ Assert.assertEquals(coords.size(), 1);
+ Assert.assertEquals(coords.get(new XY(0, 0)), root);
+
+ root.leftChild = node11;
+
+ coords = TreePrinter.buildCoordinates(root);
+ Assert.assertEquals(coords.size(), 2);
+ Assert.assertEquals(coords.get(new XY(0, 0)), root);
+ Assert.assertEquals(coords.get(new XY(-1, -1)), node11);
+
+ node11.rightSibling = node12;
+
+ coords = TreePrinter.buildCoordinates(root);
+ Assert.assertEquals(coords.size(), 3);
+ Assert.assertEquals(coords.get(new XY(0, 0)), root);
+ Assert.assertEquals(coords.get(new XY(-1, -1)), node11);
+ Assert.assertEquals(coords.get(new XY(0, -1)), node12);
+
+ node11.leftChild = node21;
+
+ coords = TreePrinter.buildCoordinates(root);
+ Assert.assertEquals(coords.size(), 4);
+ Assert.assertEquals(coords.get(new XY(0, 0)), root);
+ Assert.assertEquals(coords.get(new XY(-1, -1)), node11);
+ Assert.assertEquals(coords.get(new XY(0, -1)), node12);
+ Assert.assertEquals(coords.get(new XY(-2, -2)), node21);
+
+ node21.rightSibling = node22;
+
+ coords = TreePrinter.buildCoordinates(root);
+ Assert.assertEquals(coords.size(), 5);
+ Assert.assertEquals(coords.get(new XY(0, 0)), root);
+ Assert.assertEquals(coords.get(new XY(-1, -1)), node11);
+ Assert.assertEquals(coords.get(new XY(0, -1)), node12);
+ Assert.assertEquals(coords.get(new XY(-2, -2)), node21);
+ Assert.assertEquals(coords.get(new XY(-1, -2)), node22);
+
+ node12.leftChild = node23;
+ //System.out.println(TreePrinter.print(root));
+
+ coords = TreePrinter.buildCoordinates(root);
+ Assert.assertEquals(coords.size(), 6);
+ Assert.assertEquals(coords.get(new XY(0, 0)), root);
+ Assert.assertEquals(coords.get(new XY(-1, -1)), node11);
+ Assert.assertEquals(coords.get(new XY(1, -1)), node12); // (0,-1) before translation
+ Assert.assertEquals(coords.get(new XY(-2, -2)), node21);
+ Assert.assertEquals(coords.get(new XY(-1, -2)), node22);
+ Assert.assertEquals(coords.get(new XY(0, -2)), node23); // (-1,-2) before translation
+
+ node23.leftChild = node31;
+ //System.out.println(TreePrinter.print(root));
+
+ coords = TreePrinter.buildCoordinates(root);
+ Assert.assertEquals(coords.size(), 7);
+ Assert.assertEquals(coords.get(new XY(0, 0)), root);
+ Assert.assertEquals(coords.get(new XY(-1, -1)), node11);
+ Assert.assertEquals(coords.get(new XY(2, -1)), node12); // (1,-1) before translation
+ Assert.assertEquals(coords.get(new XY(-2, -2)), node21);
+ Assert.assertEquals(coords.get(new XY(-1, -2)), node22);
+ Assert.assertEquals(coords.get(new XY(1, -2)), node23); // (0,-2) before translation
+ Assert.assertEquals(coords.get(new XY(0, -3)), node31); // (-1,-3) before translation
+ }
+}
