#include "hourglass.h"
#include "geomutils.h"
#include "assertions.h"
#include <boost/range/adaptor/reversed.hpp>
#include <boost/range/algorithm/min_element.hpp>
#include <boost/range/algorithm/max_element.hpp>
#include <iostream>
#include <array>

using namespace boost::adaptors;

namespace {

inline void doExtendLeftChain(qreal time, qreal label, std::vector<QPointF>& initialChain,
                              std::deque<QPointF>& leftChain, std::deque<QPointF>& rightChain,
                              bool (*isLeftTurn)(QPointF const&,QPointF const&,QPointF const&) )
{
    QPointF C(time, label);
    // Check if we can link the new point into the existing left chain,
    // forming its new end point.
    while (!leftChain.empty()) {
        QPointF const& cusp = initialChain.back();
        std::size_t s = leftChain.size();
        QPointF const& B = leftChain[s-1];
        QPointF const& A = (s >= 2) ? leftChain[s-2] : cusp;
        bool canLinkHere = isLeftTurn(A, B, C);
        if (canLinkHere) {
            assert(B.x() != C.x());
            leftChain.emplace_back(std::move(C));
            return;
        }
        leftChain.pop_back();
    }
    // No?  Then we must be able to link to the cusp, forming a new 1-link left chain.
    // However, we may first need to advance the cusp along the right chain before this is allowed.
    while (true) {
        QPointF const& cusp = initialChain.back();
        bool canLinkToCusp = rightChain.empty() || isLeftTurn(cusp, rightChain.front(), C);
        if (canLinkToCusp) {
            if (cusp != C) {
                assert(cusp.x() != C.x());
                leftChain.emplace_back(std::move(C));
            }
            return;
        }
        initialChain.emplace_back( std::move(rightChain.front()) );
        rightChain.pop_front();
    }
}

} // unnamed namespace

void Funnel::extendLeftChain(qreal time, qreal label)
{
    doExtendLeftChain(time, label, _initialChain, _leftChain, _rightChain, isLeftTurn);
}
void Funnel::extendRightChain(qreal time, qreal label)
{
    doExtendLeftChain(time, label, _initialChain, _rightChain, _leftChain, isRightTurn);
}

std::deque<QPointF>& Funnel::upperChain()
{
    Funnel const* self = const_cast<Funnel const*>(this);
    return const_cast<std::deque<QPointF>&>( self->upperChain() );
}
std::deque<QPointF> const& Funnel::upperChain() const
{
    return (_leftChain.empty() || _initialChain.front().x() < _leftChain.back().x())
         ? _leftChain : _rightChain;
}

std::deque<QPointF>& Funnel::lowerChain()
{
    Funnel const* self = const_cast<Funnel const*>(this);
    return const_cast<std::deque<QPointF>&>( self->lowerChain() );
}
std::deque<QPointF> const& Funnel::lowerChain() const
{
    return (_leftChain.empty() || _initialChain.front().x() < _leftChain.back().x())
         ? _rightChain : _leftChain;
}

std::vector<QPointF> Funnel::getPathToPoint(qreal label)
{
    extendLeftChain(endTime(), label);
    _initialChain.reserve( _initialChain.size() + _leftChain.size() );
    std::move(_leftChain.begin(), _leftChain.end(), std::back_inserter(_initialChain));
    return std::move(_initialChain);
}
std::vector<QPointF> Funnel::getPathToEdge()
{
    auto& upper = upperChain();
    auto& lower = lowerChain();
    qreal time = endTime();

    // NOTE: Qt's y-axis is backwards from mathematics.  Hence "lowest point" means "highest y-coordinate".
    // TODO: use ternary search?  (can be done because both chains are unimodal)
    QPointF lowestPointOnUpperChain = cusp();
    std::size_t upperEnd = 0;
    for (std::size_t i = 0; i < upper.size(); ++i) {
        if (upper[i].y() > lowestPointOnUpperChain.y()) {
            lowestPointOnUpperChain = upper[i];
            upperEnd = i + 1;
        }
    }
    QPointF highestPointOnLowerChain = cusp();
    std::size_t lowerEnd = 0;
    for (std::size_t i = 0; i < lower.size(); ++i) {
        if (lower[i].y() < highestPointOnLowerChain.y()) {
            highestPointOnLowerChain = lower[i];
            lowerEnd = i + 1;
        }
    }

    if (std::abs(lowestPointOnUpperChain.x() - time) <=
        std::abs(highestPointOnLowerChain.x() - time))
    {
        _initialChain.reserve(_initialChain.size()+upperEnd+1);
        std::move(upper.begin(), upper.begin()+upperEnd,
                  std::back_inserter(_initialChain));
    } else {
        _initialChain.reserve(_initialChain.size()+lowerEnd+1);
        std::move(lower.begin(), lower.begin()+lowerEnd,
                  std::back_inserter(_initialChain));
    }
    if (_initialChain.back().x() != time) {
        _initialChain.emplace_back(time, _initialChain.back().y());
    }
    return std::move(_initialChain);
}

qreal Funnel::startTime() const
{
    return _initialChain.front().x();
}
qreal Funnel::endTime() const
{
    assert(_leftChain.empty() == _rightChain.empty());
    if (_leftChain.empty()) {
        return _initialChain.back().x();
    } else {
        assert(_leftChain.back().x() == _rightChain.back().x());
        return _leftChain.back().x();
    }
}

qreal Funnel::startLabel() const
{
    return _initialChain.front().y();
}
PerimeterRange Funnel::endRange() const
{
    assert(_leftChain.empty() == _rightChain.empty());
    if (_leftChain.empty()) {
        qreal y = _initialChain.back().y();
        return {y, y};
    } else {
        qreal y1 = _leftChain.back().y();
        qreal y2 = _rightChain.back().y();
        if (y1 > y2) { std::swap(y1, y2); }
        return {y1, y2};
    }
}

template <class Range>
void printPath(Range const& points, char const* color = "black")
{
    std::cout << "<path stroke=\"" << color << "\">\n";
    char c = 'm';
    for (auto&& p : points) {
        std::cout << 10*p.x() << " " << p.y() << " " << c << "\n";
        c = 'l';
    }
    std::cout << "</path>\n";
}
template <class Range>
void printPath(QPointF const& firstPoint, Range const& otherPoints, char const* color = "black")
{
    std::cout << "<path stroke=\"" << color << "\">\n";
    std::cout << 10*firstPoint.x() << " " << firstPoint.y() << " m\n";
    for (auto&& p : otherPoints) {
        std::cout << 10*p.x() << " " << p.y() << " l\n";
    }
    std::cout << "</path>\n";
}

void Funnel::printForIpe() const
{
    std::cout << "<group>\n";
    printPath(_initialChain, "gold");
    if (!_rightChain.empty()) {
        printPath(_initialChain.back(), _rightChain, "blue");
    }
    if (!_leftChain.empty()) {
        printPath(_initialChain.back(), _leftChain, "red");
    }
    std::cout << "</group>" << std::endl;
}

// From an upper and a lower funnel for a closed hourglass, construct its left- and right-facing funnels.
void Funnel::constructClosedHourglass(Funnel& upperIn_rightOut, Funnel& lowerIn_leftOut)
{
    std::deque<QPointF> upperChain, lowerChain;
    QPointF p = Funnel::splitAtFirstSharedPoint(upperIn_rightOut, lowerIn_leftOut, upperChain, lowerChain);
    lowerIn_leftOut.reset({p}, std::move(lowerChain), std::move(upperChain));
}

QPointF Funnel::splitAtFirstSharedPoint(Funnel& funnel1, Funnel& funnel2,
                                        std::deque<QPointF>& remainder1, std::deque<QPointF>& remainder2)
{
    auto& chain1 = funnel1._initialChain;
    auto& chain2 = funnel2._initialChain;
    auto i1 = chain1.begin();
    auto i2 = chain2.begin();
    while (*i1 != *i2) {
        assert(i1 != chain1.end() && i2 != chain2.end());
        if (i1->x() < i2->x()) { ++i1; } else { ++i2; }
    }

    QPointF sharedPoint = *i1;
    std::move(chain1.begin(), i1, std::front_inserter(remainder1));
    std::move(chain2.begin(), i2, std::front_inserter(remainder2));
    chain1.erase(chain1.begin(), i1);
    chain2.erase(chain2.begin(), i2);
    return std::move(sharedPoint);
}

namespace {

std::vector<QPointF> straightenUntil(QPointF const& p, std::vector<QPointF>&& path)
{
    // TODO: binary search on x-coordinate?
    auto i = std::find(path.begin(), path.end(), p);
    assert(i != path.end());
    if (i != path.begin()) {
        path.erase(std::next(path.begin()), i);
    }
    path.front().ry() = p.y();
    return std::move(path);
}

} // unnamed namespace

void Hourglass::finalizeHourglass()
{
    //    A\          ,C           A\       ,C
    //      `.    ,..'               `-----'
    //        :--'  F\                 _____
    //      ,' E      \              ,'     `D
    //    B/           D           B/
    //    closed hourglass         open hourglass

    // A "closed hourglass" consists of two funnels facing in opposite directions, with their cusps
    // connected by a path called its "string".  We store the closed hourglass depicted on the left
    // so that `leftFacingFunnel()` is the funnel from E to AB, and `rightFacingFunnel()` is the
    // funnel from E to CD (including the string E-->F).

    // An "open hourglass" consists of a disjoint upper and lower chain, for which there exists a
    // separating line.  Even though such a structure does not "naturally" contain any funnels, it
    // will be convenient to use them any way.  We store the open hourglass depicted on the right
    // with `upperFunnel()` being the funnel from A to CD and `lowerFunnel()` being the funnel
    // from B to CD.

    // It is this latter representation that we are given for `finalizeHourglass`.  In this
    // representation, the hourglass is closed if and only if `upperFunnel()` and `lowerFunnel()`
    // share any points.  These shared points (E-->F) forms the string of the closed hourglass, and
    // its end point (F) must be the cusp of both funnels.  Finding the starting point (E) of the
    // string, and then constructing `leftFacingFunnel()` and `rightFacingFunnel()` is done with a
    // helper function in the `Funnel` class.

    _isClosed = upperFunnel().cusp() == lowerFunnel().cusp();
    if (_isClosed) {
        Funnel::constructClosedHourglass(leftFacingFunnel(), rightFacingFunnel());
    }
}

std::vector<QPointF> Hourglass::getPathFromClosedHourglass()
{
    // In a closed hourglass, the shortest path from the source to the target edge consists of the
    // string, plus shortest point-to-edge paths from the string's endpoints to the source and
    // target edges.

    std::vector<QPointF> prefix = leftFacingFunnel().getPathToEdge();
    std::reverse(prefix.begin(), prefix.end());
    std::vector<QPointF> suffix = rightFacingFunnel().getPathToEdge();
    std::move(std::next(suffix.begin()), suffix.end(), std::back_inserter(prefix));
    //               ^---------- `prefix.back()` and `suffix.front()` refer to the same endpoint
    return std::move(prefix); // of the string (E); using `std::next` avoids a duplicated point
}

std::vector<QPointF> Hourglass::getPathFromOpenHourglass()
{
    // For an open hourglass, consider the horizontal tangent to the upper chain (at `top`), and the horizontal
    // tangent to the lower chain (at `bottom`).  If the former is above the latter, then any horizontal line
    // between these two tangents avoids the hourglass while connecting the source and target edge, yielding a
    // 1-link shortest path between these edges.
    QPointF top = bottomPointAlong(upperFunnel().upperPath());
    QPointF bottom = topPointAlong(lowerFunnel().lowerPath());
    if (top.y() <= bottom.y()) {
        qreal label = top.y(); // TODO: is there a more intelligent choice to be made here?
        return { {startTime(), label}, {endTime(), label} };
    } else {
        // Otherwise, the shortest path must begin and end with the horizontal tangents at `top` and `bottom`
        // (in horizontal order), and "cross over" from one chain of the hourglass to the other in between.
        // The cross-over path can be found in the funnel containing both `top` and `bottom`.
        QPointF* left; Funnel* funnel;
        if (top.x() <= bottom.x()) {
            left = &top;
            funnel = &upperFunnel();
        } else {
            left = &bottom;
            funnel = &lowerFunnel();
        }
        // `getPathToEdge` gives us the correct cross-over + ending tangent, but the subpath until `left` is not
        // necessarily a single horizontal segment yet.  `straightenUntil` fixes this.
        // This is a slight inefficiency; the vertices removed by `straightenUntil` should not have been added to
        // the path in the first place.  It's simpler this way, though.
        return straightenUntil(*left, funnel->getPathToEdge());
    }
}

PerimeterRange Hourglass::startRange() const
{
    if (_isClosed) {
        return leftFacingFunnel().endRange();
    } else {
        return {upperFunnel().startLabel(), lowerFunnel().startLabel()};
    }
}
PerimeterRange Hourglass::endRange() const
{
    if (_isClosed) {
        return rightFacingFunnel().endRange();
    } else {
        return upperFunnel().endRange(); // == lowerFunnel.endRange();
    }
}

QPointF Hourglass::firstUpperTangency(QPointF const& direction) const
{
    if (_isClosed) {
        return firstTangencyToLeftTurningPath( leftFacingFunnel().upperPathFromCusp() | reversed, direction );
    } else {
        return firstTangencyToLeftTurningPath( upperFunnel().upperPath(), direction );
    }
}
QPointF Hourglass::firstLowerTangency(QPointF const& direction) const
{
    if (_isClosed) {
        return firstTangencyToRightTurningPath( leftFacingFunnel().lowerPathFromCusp() | reversed, direction );
    } else {
        return firstTangencyToRightTurningPath( lowerFunnel().lowerPath(), direction );
    }
}
QPointF Hourglass::lastUpperTangency(QPointF const& direction) const
{
    if (_isClosed) {
        return firstTangencyToRightTurningPath( rightFacingFunnel().upperPathFromCusp() | reversed, direction );
    } else {
        return firstTangencyToRightTurningPath( upperFunnel().upperPath() | reversed, direction );
    }
}
QPointF Hourglass::lastLowerTangency(QPointF const& direction) const
{
    if (_isClosed) {
        return firstTangencyToLeftTurningPath( rightFacingFunnel().lowerPathFromCusp() | reversed, direction );
    } else {
        return firstTangencyToLeftTurningPath( lowerFunnel().lowerPath() | reversed, direction );
    }
}

PerimeterRange Hourglass::trimmedRange(WhichSide side, qreal trimming) const
{
    PerimeterRange untrimmed = (side == Start) ? startRange() : endRange();

    qreal time, dx;
    if (side == Start) { time = startTime(); dx = +1.0; }
    else               { time = endTime();   dx = -1.0; }
    QPointF upDirection(dx, -trimming);
    QPointF downDirection(dx, +trimming);
/*
    std::cout << "<page>\n"
              << "<layer name=\"alpha\"/>\n"
              << "<view layers=\"alpha\" active=\"alpha\"/>\n";
    printForIpe();
*/
    QPointF upperTangencies[] = { pointOfTangency(side, Upper, downDirection),
                                  pointOfTangency(side, Lower, downDirection) };
    QPointF lowerTangencies[] = { pointOfTangency(side, Lower, upDirection),
                                  pointOfTangency(side, Upper, upDirection) };
    qreal tops[2], bottoms[2];
    for (int i = 0; i < 2; ++i) {
        tops[i]    = projectOntoVerticalLine(time, upperTangencies[i], downDirection);
        bottoms[i] = projectOntoVerticalLine(time, lowerTangencies[i], upDirection);
    }

    qreal top;
    if (xDistance(upperTangencies[1], time) < xDistance(upperTangencies[0], time) && tops[1] <= tops[0]) {
        top = tops[1];
    } else {
        top = tops[0];
    }
    top = std::max(untrimmed.first, top);

    qreal bottom;
    if (xDistance(lowerTangencies[1], time) < xDistance(lowerTangencies[0], time) && bottoms[1] >= bottoms[0]) {
        bottom = bottoms[1];
    } else {
        bottom = bottoms[0];
    }
    bottom = std::min(untrimmed.second, bottom);

/*
    std::cout << "<path stroke=\"black\">\n";
    std::cout << "0 0 m\n";
    std::cout << 10*downDirection.x() << " " << downDirection.y() << " l\n";
    std::cout << "</path>\n";
    std::cout << "<path stroke=\"black\">\n";
    std::cout << "0 0 m\n";
    std::cout << 10*upDirection.x() << " " << upDirection.y() << " l\n";
    std::cout << "</path>\n";

    for (int i = 0; i < 2; ++i) {
        std::cout << "<path stroke=\"seagreen\">\n";
        std::cout << 10*upperTangencies[i].x() << " " << upperTangencies[i].y() << " m\n";
        std::cout << 10*time << " " << tops[i] << " l\n";
        std::cout << "</path>\n";
    }

    for (int i = 0; i < 2; ++i) {
        std::cout << "<path stroke=\"seagreen\">\n";
        std::cout << 10*lowerTangencies[i].x() << " " << lowerTangencies[i].y() << " m\n";
        std::cout << 10*time << " " << bottoms[i] << " l\n";
        std::cout << "</path>\n";
    }
    std::cout << "<path stroke=\"seagreen\">\n"
              << 10*time << " " << top << " m\n"
              << 10*time << " " << bottom << " l\n"
              << "</path>\n";
    }

    QPointF upperTangency = upperTangencies[ boost::min_element<boost::return_begin_found>(tops).size() ];
    QPointF lowerTangency = lowerTangencies[ boost::max_element<boost::return_begin_found>(bottoms).size() ];
    std::cout << "<path stroke=\"seagreen\">\n"
              << 10*upperTangency.x() << " " << upperTangency.y() << " m\n"
              << 10*time << " " << top << " l\n"
              << 10*time << " " << bottom << " l\n"
              << 10*lowerTangency.x() << " " << lowerTangency.y() << " l\n"
              << "</path>\n";
    }

    std::cout << "</page>" << std::endl;
*/
    assert(top <= bottom);
    PerimeterRange check = (side == Start) ? startRange() : endRange();
    shiftPerimeterRangeOntoValue(check, top, 204);
    assert(check.first <= top && bottom <= check.second);
    return {top, bottom};
}

void Hourglass::printForIpe() const
{
    std::cout << "<group>\n";
    if (_isClosed) {
        leftFacingFunnel().printForIpe();
        rightFacingFunnel().printForIpe();
    } else {
        printPath(upperFunnel().upperPath(), "red");
        printPath(lowerFunnel().lowerPath(), "blue");
    }
    std::cout << "</group>" << std::endl;
}
