#include <quad_tree.h>
#include <union.h>
#include <iterator>
#include <set>

QuadTree::QuadTree(Box b) : b{b}, level{0} {}

QuadTree::QuadTree(Box b, int level = 0) : b{b}, level{level} {}

void QuadTree::collectUniqueTriangleFragments(const Triangle &t, std::set<int> &seen, std::vector<Triangle> &result) const {
    if (seen.count(t.fragmentId) > 0) {
        return;
    }

    result.push_back(t);
    seen.insert(t.fragmentId);
}

std::vector<Triangle> QuadTree::visibleSurface() const {
    std::set<int> seen;
    return visibleSurface(seen);
}

std::vector<Triangle> QuadTree::visibleSurface(std::set<int> & seen) const
{
    std::vector<Triangle> result;

    for (const Triangle &t : triangles) {
        collectUniqueTriangleFragments(t, seen, result);
    }
    for (const QuadTree &c : children)
    {
        std::vector<Triangle> childResult = c.visibleSurface(seen);
        result.insert(result.end(), childResult.begin(), childResult.end());
    }

    return result;
}

void QuadTree::split()
{
    const int nextLevel = level + 1;
    children = {
        QuadTree(b.firstQuadrant(), nextLevel),
        QuadTree(b.secondQuadrant(), nextLevel),
        QuadTree(b.thirdQuadrant(), nextLevel),
        QuadTree(b.fourthQuadrant(), nextLevel)};
}

void QuadTree::addTriangle(const Triangle &triangle)
{
    if (!b.intersects(triangle))
    {
        return;
    }

    if (triangles.empty())
    {
        triangles.push_back(triangle);
        return;
    }

    if (!children.empty())
    {
        for (QuadTree &child : children)
        {
            child.addTriangle(triangle);
        }
        return;
    }

    std::vector<Triangle> currentTriangleFragments{triangle};

    // triangles that are not the current triangle and that have already been unioned
    std::vector<Triangle> otherTriangleFragments;
    for (const auto &otherTriangle : triangles)
    {
        for (const auto &fragment : currentTriangleFragments)
        {
            auto newTriangles = unionize(triangle, otherTriangle);
            std::vector<Triangle> bottoms;
            if (newTriangles.size() > 1)
            {
                bottoms = {newTriangles.begin(), newTriangles.begin() + newTriangles.size() - 2};
            }
            const Triangle &top = newTriangles.back();
            otherTriangleFragments.push_back(top);
            if (top.mainTriangleId == triangle.mainTriangleId)
            {
                otherTriangleFragments.insert(otherTriangleFragments.begin(), bottoms.begin(), bottoms.end());
            }
            else
            {
                currentTriangleFragments.insert(currentTriangleFragments.begin(), bottoms.begin(), bottoms.end());
            }
        }
    }

    // split
    if (level >= QUADTREE_MAX_DEPTH) {
        triangles.insert(triangles.end(), currentTriangleFragments.begin(), currentTriangleFragments.end());
        triangles.insert(triangles.end(), otherTriangleFragments.begin(), otherTriangleFragments.end());
        return;
    }
    split();
    for (QuadTree &q : children)
    {
        for (const Triangle &t : otherTriangleFragments)
        {
            q.addNonIntersectingTriangle(t);
        }
        for (const Triangle &t : currentTriangleFragments)
        {
            q.addNonIntersectingTriangle(t);
        }
    }

    triangles.clear();
}

int QuadTree::pointIntersection(const Point &p) const
{
    if (b.intersects(p))
    {
        for (const Triangle &triangle : triangles)
        {
            if (triangle.pointInTriangle(p))
            {
                return triangle.mainTriangleId;
            }
        }

        for (const QuadTree &child : children)
        {
            int id = child.pointIntersection(p);
            if (id != POINT_NOT_IN_QUADTREE)
            {
                return id;
            }
        }
    }

    return POINT_NOT_IN_QUADTREE;
}

void QuadTree::addNonIntersectingTriangle(const Triangle &t)
{
    if (b.intersects(t))
    {
        triangles.push_back(t);
    }
}