#include "staticlabeler.h"
#include "staticlabeling.h"
#include "labeledpoint.h"
#include "labelmodel.h"
#include "assertions.h"
#include <algorithm>
#include <vector>
#ifdef PRODUCE_TIMINGS
#  include <chrono>
#  include <iostream>
#endif

StaticLabeler::StaticLabeler()
{
}

StaticLabeler::~StaticLabeler()
{
}

namespace {
    bool leftToRight(LabeledPoint const* point1, LabeledPoint const* point2)
    {
        QPointF const& p1 = point1->position(); QPointF const& p2 = point2->position();
        return p1.x() < p2.x() || (p1.x() == p2.x() && p1.y() < p2.y());
    }

    template <typename Function>
    int performGreedySweep(std::vector<LabeledPoint*>& points, Function const& assignLabel)
    {
        // O(n^2)-time implementation of GreedySweep---instead of O(n log n) time---
        // because it's much simpler, and more than fast enough for our experiments.
        int freeLabels = 0;
        std::size_t n = points.size();
        std::vector<LabelCandidates> nonfreeCandidates;
        nonfreeCandidates.reserve(n);
        for (std::size_t i = 0; i < n; ++i) {
            nonfreeCandidates.emplace_back( points[i]->labelCandidates() );
        }
        for (std::size_t i = 0; i < n; ++i) {
            auto freeCandidates = nonfreeCandidates[i];
            for (std::size_t j = 0; j < i; ++j) {
                freeCandidates.removeIntersecting( points[j]->labelCenter() );
            }
            for (std::size_t j = i+1; j < n; ++j) {
                freeCandidates.removeAlmostBlocking( nonfreeCandidates[j] );
                assert(!nonfreeCandidates[j].isEmpty());
            }
            if (!freeCandidates.isEmpty()) {
                auto&& freeLabelCenter = freeCandidates.leftmostPoint();
                assignLabel(points[i], freeLabelCenter);
                ++freeLabels;
                for (std::size_t j = i+1; j < n; ++j) {
                    nonfreeCandidates[j].removeIntersecting( freeLabelCenter );
                    assert(!nonfreeCandidates[j].isEmpty());
                }
            } else {
                auto&& nonfreeLabelCenter = nonfreeCandidates[i].leftmostPoint();
                assignLabel(points[i], nonfreeLabelCenter);
            }
        }
        return freeLabels;
    }

    int greedySweep(std::vector<LabeledPoint*>& points, LabelModel const& labelModel, SweepDirection const& dir)
    {
        if (points.empty()) { return 0; }

        // rotate/mirror the points and label candidates so that we can sweep
        // left-to-right instead of in the given direction `dir`
        for (auto point : points) {
            dir.transform(*point);
        }

        // do the actual work, undoing the earlier rotation/mirroring one point
        // at a time as we assign labels to them
        std::sort(points.begin(), points.end(), leftToRight);
        int freeLabels = performGreedySweep(points,
            [&](LabeledPoint* point, QPointF labelCenter) {
                dir.untransform(*point);
                dir.untransform(labelCenter);
                point->setLabel(labelCenter, labelModel);
            });
        return freeLabels;
    }

    int fourGreedySweeps(std::vector<LabeledPoint*>& points, LabelModel const& labelModel)
    {
#ifdef PRODUCE_TIMINGS
        typedef std::chrono::high_resolution_clock clock_type;
        clock_type::time_point start = clock_type::now();
#endif
        SweepDirection sweepDirections[] = { SweepDirection::LeftToRight(), SweepDirection::RightToLeft(),
                                             SweepDirection::TopToBottom(), SweepDirection::BottomToTop() };
        int numSweeps = sizeof(sweepDirections)/sizeof(sweepDirections[0]);
        int besti = 0;
        int bestFree = greedySweep(points, labelModel, sweepDirections[0]);
        for (int i = 1; i < numSweeps; ++i) {
            int free = greedySweep(points, labelModel, sweepDirections[i]);
            if (free > bestFree) {
                besti = i;
                bestFree = free;
            }
        }
        // Now that we know which of the four labelings was best, we have to redo it.  We could prevent this with
        // some more data copying.  For large n that should be faster, since copying is O(n) and labeling is O(n^2).
        // TODO: is copying faster for practical n?  (And does it even matter, given that we are already fast enough?)
        if (besti != numSweeps-1) {
            greedySweep(points, labelModel, sweepDirections[besti]);
        }
#ifdef PRODUCE_TIMINGS
        clock_type::time_point stop = clock_type::now();
        qreal runtime = 1e-6*std::chrono::duration_cast<std::chrono::nanoseconds>(stop - start).count();
        std::cout << "FourGreedySweeps on " << points.size() << " points: " << runtime << " ms" << std::endl;
#endif
        return bestFree;
    }

} // anonymous namespace

GreedySweepLabeler::GreedySweepLabeler(SweepDirection dir)
    : _dir(dir)
{
}

void GreedySweepLabeler::computeLabeling(StaticLabeling& labeling) const
{
    std::vector<LabeledPoint*> points;
    points.reserve(labeling.points());
    for (LabeledPoint& point : labeling.labeledPoints()) {
        points.emplace_back(&point);
    }
    greedySweep(points, labeling.labelModel(), _dir);
    labeling.recomputeLabelFreenesses();
}

FourGreedySweepsLabeler::FourGreedySweepsLabeler()
{
}

void FourGreedySweepsLabeler::computeLabeling(StaticLabeling& labeling) const
{
    std::vector<LabeledPoint*> points;
    points.reserve(labeling.points());
    for (LabeledPoint& point : labeling.labeledPoints()) {
        points.emplace_back(&point);
    }
    fourGreedySweeps(points, labeling.labelModel());
    labeling.recomputeLabelFreenesses();
}
