/*********************************************************************
 *  Author  : Tino Weinkauf and Wiebke K�pp
 *  Init    : Thursday, November 23, 2017 - 16:54:12
 *
 *  Project : KTH Inviwo Modules
 *
 *  License : Follows the Inviwo BSD license model
 *********************************************************************
 */

#include "treeorder.h"

namespace treeorder {

void orderAsInserted(TemporalTree::TTreeOrder& order, const TemporalTree& tree) {
    auto leaves = tree.getLeaves();

    order.reserve(leaves.size());

    for (auto leaf : leaves) {
        order.push_back(leaf);
    }
}

void dfs(size_t nodeIndex, std::vector<bool>& visited, TemporalTree::TTreeOrder& order,
         const TemporalTree& tree, const TemporalTree::TAdjacency& edges) {
    visited[nodeIndex] = true;

    if (tree.isLeaf(nodeIndex)) {
        order.push_back(nodeIndex);
    }

    const auto itHierarchyEdges = edges.find(nodeIndex);

    // not a leaf -> process children?
    if (itHierarchyEdges != edges.end()) {
        auto& children = itHierarchyEdges->second;
        for (auto child : children) {
            if (!visited[child]) {
                dfs(child, visited, order, tree, edges);
            }
        }
    }
}

void orderAsDepthFirst(TemporalTree::TTreeOrder& order, const TemporalTree& tree,
                       const TemporalTree::TAdjacency& edges) {
    std::vector<bool> visited(tree.nodes.size(), false);
    dfs(0, visited, order, tree, edges);
}

bool fitsWithTree(const TemporalTree& tree, const TemporalTree::TTreeOrder& leafOrder) {
    auto leaves = tree.getLeaves();

    // if sizes already mismatch, not all leaves can be contained
    if (leaves.size() != leafOrder.size()) {
        return false;
    }

    // Check that all the leaves are part of the sort vector
    std::set<size_t> indexSetOrder(leafOrder.begin(), leafOrder.end());

    for (auto leaf : leaves) {
        if (indexSetOrder.find(leaf) == indexSetOrder.end()) {
            return false;
        }
    }

    return true;
}

void sortNodesByOrder(const TemporalTree::TTreeOrderMap& orderMap, const TemporalTree& tree,
                      std::vector<size_t>& nodeIndices) {
    std::sort(nodeIndices.begin(), nodeIndices.end(),
              [&orderMap, &tree](const size_t a, const size_t b) -> bool {
                  auto itIndexA = orderMap.find(a);
                  auto itIndexB = orderMap.find(b);
                  // If either index a or b are not in the order, we cannot sort the given
                  assert(itIndexA != orderMap.end() && itIndexB != orderMap.end());

                  // Compare by sort indices (first cases should only occur when we are comparing
                  // non-leaves)
                  if (itIndexA->second == itIndexB->second) {
                      // Sort by beginning times
                      return tree.nodes[a].startTime() < tree.nodes[b].startTime();
                  }
                  return itIndexA->second < itIndexB->second;
              });
}

TemporalTree::TTreeOrderMap expandToFullTree(const TemporalTree& tree,
                                             const TemporalTree::TTreeOrderMap& leafOrderMap) {
    TemporalTree::TTreeOrderMap treeOrderMap(leafOrderMap);
    setToMinInChildren(0, tree, treeOrderMap);
    return treeOrderMap;
}

void toSimpleOrder(TemporalTree::TTreeOrder& order, const TemporalTree::TTreeOrderMap& orderMap) {
    order.resize(orderMap.size());

    for (const auto indexSortIndexPair : orderMap) {
        order[indexSortIndexPair.second] = indexSortIndexPair.first;
    }
}

void toOrderMap(TemporalTree::TTreeOrderMap& orderMap, const TemporalTree::TTreeOrder& order) {
    for (size_t index = 0; index < order.size(); index++) {
        orderMap.insert_or_assign(order[index], index);
    }
}

//@todo: Might only work for no edgecrossings??
size_t setToMinInChildren(const size_t nodeIndex, const TemporalTree& tree,
                          TemporalTree::TTreeOrderMap& orderMap) {
    const auto itHierarchyEdges = tree.edgesHierarchy.find(nodeIndex);

    // Is it a leaf or a parent?
    // Leaf only has one order value: the one already given in the order
    if (itHierarchyEdges != tree.edgesHierarchy.end()) {
        // Parents: visit children, ask them

        // Shorthand for the children
        const std::vector<size_t>& Children = itHierarchyEdges->second;

        // Call recursively, order for children
        size_t orderMin = std::numeric_limits<size_t>::max();
        for (const size_t idChild : Children) {
            size_t orderMinChild = setToMinInChildren(idChild, tree, orderMap);
            // Update?
            if (orderMinChild < orderMin) orderMin = orderMinChild;
        }
        orderMap[nodeIndex] = orderMin;
    }
    return orderMap[nodeIndex];
}

void fillPosition(vector<int>& orderIndex, size_t nodeIndex, TemporalTree& tree, TemporalTree::TTreeOrderMap& treeorderMap) {
    if (tree.isLeaf(nodeIndex)) {
        orderIndex[nodeIndex] = treeorderMap[nodeIndex];
        return;
    }
    int minPosition = INT_MAX;
    for (auto child: tree.edgesHierarchy[nodeIndex]) {
        fillPosition(orderIndex, child, tree, treeorderMap);
        minPosition = min(minPosition, orderIndex[child]);
    }
    orderIndex[nodeIndex] = minPosition;
}

void fillPreorder(vector<int>& index, int& cnter, TemporalTree& tree, int v) {
    index[v] = cnter++;

    if (!tree.isLeaf(v)) {
        for (auto w: tree.edgesHierarchy[v]) {
            fillPreorder(index, cnter, tree, w);
        }
    }
}

void fillPostorder(vector<int>& index, int& cnter, TemporalTree& tree, size_t v) {
    if (!tree.isLeaf(v)) {
        for (auto w: tree.edgesHierarchy[v]) {
            fillPostorder(index, cnter, tree, w);
        }
    }    
    index[v] = cnter++;
}

bool isChildDescRelation(vector<int>& preorderIndex, vector<int>& postorderIndex, size_t u, size_t v) {
    return (preorderIndex[u] < preorderIndex[v]) != (postorderIndex[u] < postorderIndex[v]);
}

int countCrossings(TemporalTree tree) {  
    assert(!tree.order.empty());
    TemporalTree TDeaggregated = tree.getSelfDeaggregated();
    TemporalTree::TTreeOrderMap treeorderMap;
    toOrderMap(treeorderMap, TDeaggregated.order);

    // the position of each node in the order
    // this also includes inner nodes, we just take the position of any leaf
    vector<int> orderIndex(TDeaggregated.nodes.size());
    vector<int> preOrderIndex(TDeaggregated.nodes.size());
    vector<int> postOrderIndex(TDeaggregated.nodes.size());
    int cnter = 0;
    fillPreorder(preOrderIndex, cnter, TDeaggregated, 0);
    cnter = 0;
    fillPostorder(postOrderIndex, cnter, TDeaggregated, 0);
    fillPosition(orderIndex, 0, TDeaggregated, treeorderMap);
    
    map<int, vector<size_t>> t_nodes;
    for (size_t i = 1; i < TDeaggregated.nodes.size(); i++) {
        t_nodes[TDeaggregated.nodes[i].startTime()].push_back(i);
    }

    size_t cntCrossings = 0;
    for (auto const& [time, nodesattime] : t_nodes) {
        // edges that go from one time to the next
        vector<pair<size_t,size_t>> edges;
        for (auto v: nodesattime) {
            if (TDeaggregated.edgesTime.find(v) != TDeaggregated.edgesTime.end()) {
                for (auto w: TDeaggregated.edgesTime[v]) {
                    assert (TDeaggregated.nodes[v].startTime() != TDeaggregated.nodes[w].startTime());
                    edges.push_back({v,w});
                }
            }
        }
        // now check for every pair of edges if they cross
        for (size_t i = 0; i < edges.size(); i++) {
            for (size_t j = i+1; j < edges.size(); j++) {
                auto e1 = edges[i];                    
                auto e2 = edges[j];
                
                if (e1.first == e2.first || e1.second == e2.second)continue;
                // we dont want do count those crossings
                if (isChildDescRelation(preOrderIndex, postOrderIndex, e1.first, e2.first) || isChildDescRelation(preOrderIndex, postOrderIndex, e1.second, e2.second)) continue;
                
                // now check crossing
                if ((orderIndex[e1.first]<orderIndex[e2.first]) != (orderIndex[e1.second]<orderIndex[e2.second])) {
                    cntCrossings++;
                }
            }
        }
    }
    return cntCrossings;
}

int countLeafEdgeCrossings(TemporalTree tree) {  
    assert(!tree.order.empty());
    TemporalTree TDeaggregated = tree.getSelfDeaggregated();
    TemporalTree::TTreeOrderMap treeorderMap;
    toOrderMap(treeorderMap, TDeaggregated.order);

    // the position of each node in the order
    // this also includes inner nodes, we just take the position of any leaf
    vector<int> orderIndex(TDeaggregated.nodes.size());
    vector<int> preOrderIndex(TDeaggregated.nodes.size());
    vector<int> postOrderIndex(TDeaggregated.nodes.size());
    int cnter = 0;
    fillPreorder(preOrderIndex, cnter, TDeaggregated, 0);
    cnter = 0;
    fillPostorder(postOrderIndex, cnter, TDeaggregated, 0);
    fillPosition(orderIndex, 0, TDeaggregated, treeorderMap);
    
    map<int, vector<size_t>> t_nodes;
    for (size_t i = 1; i < TDeaggregated.nodes.size(); i++) {
        t_nodes[TDeaggregated.nodes[i].startTime()].push_back(i);
    }

    size_t cntCrossings = 0;
    TDeaggregated.computeLeafEdges();
    for (auto const& [time, nodesattime] : t_nodes) {
        // edges that go from one time to the next
        vector<pair<size_t,size_t>> edges;
        for (auto v: nodesattime) {
            if (TDeaggregated.leafEdges.find(v) != TDeaggregated.leafEdges.end()) {
                for (auto w: TDeaggregated.leafEdges[v]) {      
                    edges.push_back({v,w});
                }
            }
        }
        // now check for every pair of edges if they cross
        for (size_t i = 0; i < edges.size(); i++) {
            for (size_t j = i+1; j < edges.size(); j++) {
                auto e1 = edges[i];                    
                auto e2 = edges[j];
                
                if (e1.first == e2.first || e1.second == e2.second)continue;
                // we dont want do count those crossings
                if (isChildDescRelation(preOrderIndex, postOrderIndex, e1.first, e2.first) || isChildDescRelation(preOrderIndex, postOrderIndex, e1.second, e2.second)) continue;
                
                // now check crossing
                if ((orderIndex[e1.first]<orderIndex[e2.first]) != (orderIndex[e1.second]<orderIndex[e2.second])) {
                    cntCrossings++;
                }
            }
        }
    }
    return cntCrossings;
}

}  // namespace treeorder
