/*
 * 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.LinkedList;
import java.util.List;
import java.util.UUID;

import org.joda.time.LocalDate;

import com.ning.billing.invoice.api.InvoiceItem;

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;
    }

    public void build(final List<Item> output, boolean addRepair) {

        // There is no sub-interval, just add our own items.
        if (leftChild == null) {
            items.buildFromItems(output, addRepair);
            return;
        }

        LocalDate curDate = start;
        NodeInterval curChild = leftChild;
        while (curChild != null) {
            if (curChild.getStart().compareTo(curDate) > 0) {
                items.buildForMissingInterval(curDate, curChild.getStart(), output, addRepair);
            }
            curChild.build(output, addRepair);
            curDate = curChild.getEnd();
            curChild = curChild.getRightSibling();
        }
        if (curDate.compareTo(end) < 0) {
            items.buildForMissingInterval(curDate, end, output, addRepair);
        }
    }

    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 void addAdjustment(final LocalDate adjustementDate, final BigDecimal amount, final UUID linkedId) {
        NodeInterval node = findNode(adjustementDate, linkedId);
        if (node == null) {
            throw new TreeNodeException("Cannot add adjustement for item = " + linkedId + ", date = " + adjustementDate);
        }
        node.setAdjustment(amount.negate(), linkedId);
    }

    private void setAdjustment(final BigDecimal amount, final UUID linkedId) {
        items.setAdjustment(amount, linkedId);
    }

    private NodeInterval findNode(final LocalDate date, final UUID targetItemId) {
        if (!isRoot()) {
            throw new TreeNodeException("findNode can only be called from root");
        }
        return findNodeRecursively(this, date, targetItemId);
    }

    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;
    }

    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) {
            leftChild = newNode;
            return true;
        }

        NodeInterval prevChild = null;
        NodeInterval curChild = leftChild;
        do {
            Preconditions.checkState(!curChild.isItemOverlap(newNodeItem), "Item " + newNodeItem + " overlaps " + curChild);

            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)) {
                    curChild.mergeProposedItem(newNode);
                    return true;
                } else {
                    return false;
                }
            }

            if (newNodeItem.getStartDate().compareTo(curChild.getStart()) < 0) {
                newNode.rightSibling = curChild;
                if (prevChild == null) {
                    leftChild = newNode;
                } else {
                    prevChild.rightSibling = newNode;
                }
                return true;
            }
            prevChild = curChild;
            curChild = curChild.rightSibling;
        } while (curChild != null);

        prevChild.rightSibling = newNode;
        return true;
    }

    public void addNodeInterval(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);
    }

    // STEPH TODO are parents correctly maintained and/or do we need them?
    private void addNode(final NodeInterval newNode) {
        final Item item = newNode.getItems().get(0);
        if (leftChild == null) {
            leftChild = newNode;
            return;
        }

        NodeInterval prevChild = null;
        NodeInterval curChild = leftChild;
        do {
            if (curChild.isItemContained(item)) {
                curChild.addNodeInterval(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;
        } while (curChild != null);

        prevChild.rightSibling = newNode;
    }

    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.rightSibling = toBeRebalanced.get(toBeRebalanced.size() - 1).rightSibling;
        if (prevRebalanced == null) {
            leftChild = newNode;
        } else {
            prevRebalanced.rightSibling = newNode;
        }

        NodeInterval prev = null;
        for (NodeInterval cur : toBeRebalanced) {
            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;
    }

    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 List<Item> getItems() {
        return items.getItems();
    }

    public boolean containsItem(final UUID targetId) {
        return items.containsItem(targetId);
    }
}
