/*
* Copyright 2010-2014 Ning, Inc.
*
* Ning 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 com.ning.billing.invoice.tree;
import java.math.BigDecimal;
import java.util.List;
import java.util.UUID;
import org.joda.time.LocalDate;
import com.google.common.base.Preconditions;
import com.google.common.collect.Lists;
public class NodeInterval {
private LocalDate start;
private LocalDate end;
private ItemsInterval items;
private NodeInterval parent;
private NodeInterval leftChild;
private NodeInterval rightSibling;
public NodeInterval() {
this.items = new ItemsInterval(this);
}
public NodeInterval(final NodeInterval parent, final Item item) {
this.start = item.getStartDate();
this.end = item.getEndDate();
this.items = new ItemsInterval(this, item);
this.parent = parent;
this.leftChild = null;
this.rightSibling = null;
}
/**
* Build the output list from the elements in the tree.
* <p/>
* In the simple mode, mergeMode = false, there is no limit in the depth of the tree,
* and the build strategy is to first consider the lowest child for a given period
* and go up the tree adding missing interval if needed. For e.g, one of the possible scenario:
* <pre>
* D1 D2
* |---------------------------------------------------| Plan P1
* D1' D2'
* |---------------|/////////////////////////////| Plan P2, REPAIR
*
* In that case we will generate:
* [D1,D1') on Plan P1; [D1', D2') on Plan P2, and [D2', D2) repair item
*
* <pre/>
*
* In the merge mode, the strategy is different, the tree is fairly shallow
* and the goal is to generate the repair items; @see mergeProposedItem
*
* @param output result list of items
* @param mergeMode mode used to produce output list
*/
public void build(final List<Item> output, final boolean mergeMode) {
// There is no sub-interval, just add our own items.
if (leftChild == null) {
items.buildFromItems(output, mergeMode);
return;
}
LocalDate curDate = start;
NodeInterval curChild = leftChild;
while (curChild != null) {
if (curChild.getStart().compareTo(curDate) > 0) {
items.buildForMissingInterval(curDate, curChild.getStart(), output, mergeMode);
}
curChild.build(output, mergeMode);
curDate = curChild.getEnd();
curChild = curChild.getRightSibling();
}
// Finally if there is a hole at the end, we build the missing piece from ourself
if (curDate.compareTo(end) < 0) {
items.buildForMissingInterval(curDate, end, output, mergeMode);
}
}
/**
* The merge tree is initially constructed by flattening all the existing items and reversing them (CANCEL node).
* That means that if we were to not merge any new proposed items, we would end up with only those reversed existing
* items, and they would all end up repaired-- which is what we want.
* <p/>
* However, if there are new proposed items, then we look to see if they are children one our existing reverse items
* so that we can generate the repair pieces missing. For e.g, below is one scenario among so many:
* <p/>
* <pre>
* D1 D2
* |---------------------------------------------------| (existing reversed (CANCEL) item
* D1' D2'
* |---------------| (proposed same plan)
* </pre>
* In that case we want to generated a repair for [D1, D1') and [D2',D2)
* <p/>
* Note that this tree is never very deep, only 3 levels max, with exiting at the first level
* and proposed that are the for the exact same plan but for different dates below.
*
* @param newNode a new proposed item
* @return true if the item was merged and will trigger a repair or false if the proposed item should be kept as such
* and no repair generated.
*/
public boolean mergeProposedItem(final NodeInterval newNode) {
Preconditions.checkState(newNode.getItems().size() == 1, "Expected new node to have only one item");
final Item newNodeItem = newNode.getItems().get(0);
if (!isRoot() && newNodeItem.getStartDate().compareTo(start) == 0 && newNodeItem.getEndDate().compareTo(end) == 0) {
items.cancelItems(newNodeItem);
return true;
}
computeRootInterval(newNode);
if (leftChild == null) {
// There is no existing items, only new proposed one, nothing to add in that merge tree
if (isRoot()) {
return false;
} else {
// Proposed item is the first child of an existing item with the same product info.
newNode.parent = this;
leftChild = newNode;
return true;
}
}
NodeInterval prevChild = null;
NodeInterval curChild = leftChild;
do {
if (curChild.isItemContained(newNodeItem)) {
final Item existingNodeItem = curChild.getItems().get(0);
Preconditions.checkState(curChild.getItems().size() == 1, "Expected existing node to have only one item");
if (existingNodeItem.isSameKind(newNodeItem)) {
// Proposed item has same product info than parent and is contained so insert it at the right place in the tree
curChild.mergeProposedItem(newNode);
return true;
} else {
return false;
}
}
if (newNodeItem.getStartDate().compareTo(curChild.getStart()) < 0) {
newNode.parent = this;
newNode.rightSibling = curChild;
if (prevChild == null) {
leftChild = newNode;
} else {
prevChild.rightSibling = newNode;
}
return true;
}
prevChild = curChild;
curChild = curChild.rightSibling;
} while (curChild != null);
if (isRoot()) {
// The new proposed item spans over a new interval, nothing to add in the merge tree
return false;
} else {
newNode.parent = this;
prevChild.rightSibling = newNode;
return true;
}
}
/**
* Add an existing item in the tree of items.
*
* @param newNode new existing item to be added
*/
public void addExistingItem(final NodeInterval newNode) {
final Item item = newNode.getItems().get(0);
if (!isRoot() && item.getStartDate().compareTo(start) == 0 && item.getEndDate().compareTo(end) == 0) {
items.insertSortedItem(item);
return;
}
computeRootInterval(newNode);
addNode(newNode);
}
/**
* Add the adjustment amount on the item specified by the targetId.
*
* @param adjustementDate date of the adjustment
* @param amount amount of the adjustment
* @param targetId item that has been adjusted
*/
public void addAdjustment(final LocalDate adjustementDate, final BigDecimal amount, final UUID targetId) {
NodeInterval node = findNode(adjustementDate, targetId);
Preconditions.checkNotNull(node, "Cannot add adjustement for item = " + targetId + ", date = " + adjustementDate);
node.setAdjustment(amount.negate(), targetId);
}
public boolean isItemContained(final Item item) {
return (item.getStartDate().compareTo(start) >= 0 &&
item.getStartDate().compareTo(end) <= 0 &&
item.getEndDate().compareTo(start) >= 0 &&
item.getEndDate().compareTo(end) <= 0);
}
public boolean isItemOverlap(final Item item) {
return ((item.getStartDate().compareTo(start) < 0 &&
item.getEndDate().compareTo(end) >= 0) ||
(item.getStartDate().compareTo(start) <= 0 &&
item.getEndDate().compareTo(end) > 0));
}
public boolean isRoot() {
return parent == null;
}
public LocalDate getStart() {
return start;
}
public LocalDate getEnd() {
return end;
}
public NodeInterval getParent() {
return parent;
}
public NodeInterval getLeftChild() {
return leftChild;
}
public NodeInterval getRightSibling() {
return rightSibling;
}
public int getNbChildren() {
int result = 0;
NodeInterval curChild = leftChild;
while (curChild != null) {
result++;
curChild = curChild.rightSibling;
}
return result;
}
public List<Item> getItems() {
return items.getItems();
}
public boolean containsItem(final UUID targetId) {
return items.containsItem(targetId);
}
private void addNode(final NodeInterval newNode) {
newNode.parent = this;
final Item item = newNode.getItems().get(0);
if (leftChild == null) {
leftChild = newNode;
return;
}
NodeInterval prevChild = null;
NodeInterval curChild = leftChild;
while (curChild != null) {
if (curChild.isItemContained(item)) {
curChild.addExistingItem(newNode);
return;
}
if (curChild.isItemOverlap(item)) {
rebalance(newNode);
return;
}
if (item.getStartDate().compareTo(curChild.getStart()) < 0) {
newNode.rightSibling = curChild;
if (prevChild == null) {
leftChild = newNode;
} else {
prevChild.rightSibling = newNode;
}
return;
}
prevChild = curChild;
curChild = curChild.rightSibling;
}
prevChild.rightSibling = newNode;
}
/**
* Since items may be added out of order, there is no guarantee that we don't suddenly have a new node
* whose interval emcompasses cuurent node(s). In which case we need to rebalance the tree.
*
* @param newNode node that triggered a rebalance operation
*/
private void rebalance(final NodeInterval newNode) {
final Item item = newNode.getItems().get(0);
NodeInterval prevRebalanced = null;
NodeInterval curChild = leftChild;
List<NodeInterval> toBeRebalanced = Lists.newLinkedList();
do {
if (curChild.isItemOverlap(item)) {
toBeRebalanced.add(curChild);
} else {
if (toBeRebalanced.size() > 0) {
break;
}
prevRebalanced = curChild;
}
curChild = curChild.rightSibling;
} while (curChild != null);
newNode.parent = this;
final NodeInterval lastNodeToRebalance = toBeRebalanced.get(toBeRebalanced.size() - 1);
newNode.rightSibling = lastNodeToRebalance.rightSibling;
lastNodeToRebalance.rightSibling = null;
if (prevRebalanced == null) {
leftChild = newNode;
} else {
prevRebalanced.rightSibling = newNode;
}
NodeInterval prev = null;
for (NodeInterval cur : toBeRebalanced) {
cur.parent = newNode;
if (prev == null) {
newNode.leftChild = cur;
} else {
prev.rightSibling = cur;
}
prev = cur;
}
}
private void computeRootInterval(final NodeInterval newNode) {
if (!isRoot()) {
return;
}
this.start = (start == null || start.compareTo(newNode.getStart()) > 0) ? newNode.getStart() : start;
this.end = (end == null || end.compareTo(newNode.getEnd()) < 0) ? newNode.getEnd() : end;
}
private void setAdjustment(final BigDecimal amount, final UUID linkedId) {
items.setAdjustment(amount, linkedId);
}
private NodeInterval findNode(final LocalDate date, final UUID targetItemId) {
Preconditions.checkState(isRoot(), "findNode can only be called from root");
return findNodeRecursively2(this, date, targetItemId);
}
// TODO That method should be use instead of findNodeRecursively2 to search the node more effectively using the time
// but unfortunately that fails because of our test that use the wrong date when doing adjustments.
private NodeInterval findNodeRecursively(final NodeInterval curNode, final LocalDate date, final UUID targetItemId) {
if (date.compareTo(curNode.getStart()) < 0 || date.compareTo(curNode.getEnd()) > 0) {
return null;
}
NodeInterval curChild = curNode.getLeftChild();
while (curChild != null) {
if (curChild.getStart().compareTo(date) <= 0 && curChild.getEnd().compareTo(date) >= 0) {
if (curChild.containsItem(targetItemId)) {
return curChild;
} else {
return findNodeRecursively(curChild, date, targetItemId);
}
}
curChild = curChild.getRightSibling();
}
return null;
}
private NodeInterval findNodeRecursively2(final NodeInterval curNode, final LocalDate date, final UUID targetItemId) {
if (!curNode.isRoot() && curNode.containsItem(targetItemId)) {
return curNode;
}
NodeInterval curChild = curNode.getLeftChild();
while (curChild != null) {
final NodeInterval result = findNodeRecursively2(curChild, date, targetItemId);
if (result != null) {
return result;
}
curChild = curChild.getRightSibling();
}
return null;
}
}