#include "staticlabeling.h"
#include "staticlabeler.h"
#include "labelmodel.h"
#include "assertions.h"
#include <iterator> // std::next
#include <set>
#include <unordered_set>
#include <algorithm>
#include <limits>

StaticLabeling::StaticLabeling(StaticLabeling&& other)
    : _labels(std::move(other._labels))
    , _time(std::move(other._time))
    , _totalFreeArea(std::move(other._totalFreeArea))
    , _labelModel(std::move(other._labelModel))
{
    other._totalFreeArea = 0;
}

StaticLabeling& StaticLabeling::operator=(StaticLabeling&& other)
{
    if (this != &other) {
        _labels = std::move(other._labels);
        _time = std::move(other._time);
        _totalFreeArea = std::move(other._totalFreeArea);
        _labelModel = std::move(other._labelModel);
        other._totalFreeArea = 0;
    }
    return *this;
}

bool StaticLabeling::isDefinedFor(AirplaneID airplane) const
{
    return _labels.find(airplane) != _labels.end();
}

LabeledPoint const& StaticLabeling::operator[](AirplaneID airplane) const
{
    auto i = _labels.find(airplane);
    assert(i != _labels.end());
    return i->second;
}

StaticLabeling::const_range StaticLabeling::labeledPoints() const
{
    return const_range( boost::make_transform_iterator(_labels.cbegin(), TakeValue()),
                        boost::make_transform_iterator(_labels.cend(), TakeValue()) );
}
StaticLabeling::range StaticLabeling::labeledPoints()
{
    return range( boost::make_transform_iterator(_labels.begin(), TakeValue()),
                  boost::make_transform_iterator(_labels.end(), TakeValue()) );
}

int StaticLabeling::freeLabels(qreal freenessThreshold) const
{
    freenessThreshold -= 1e-5;
    int result = 0;
    for (auto& keyValue : _labels) {
        LabeledPoint const& p = keyValue.second;
        result += p.labelFreeness() >= freenessThreshold ? 1 : 0;
    }
    return result;
}

namespace {

enum WhichSide { LeftSide, RightSide };

class LabelEvent {
public:
    LabelEvent(LabeledPoint* p, qreal x)
        : _x(x), _p(p)
    {}
    LabeledPoint const* point() const { return _p; }
    LabeledPoint* point() { return _p; }
    qreal x() const { return _x; }
    WhichSide side() const { return _x < _p->labelCenter().x() ? LeftSide : RightSide; }

private:
    qreal _x;
    LabeledPoint* _p;
};

class VerticalSegment {
public:
    VerticalSegment(LabeledPoint* p, qreal top, qreal bottom)
        : _top(top), _bottom(bottom), _p(p)
    {}
    LabeledPoint const* point() const { return _p; }
    LabeledPoint* point() { return _p; }
    qreal top() const { return _top; }
    qreal& top()      { return _top; }
    qreal bottom() const { return _bottom; }
    qreal& bottom()      { return _bottom; }

private:
    qreal _top, _bottom;
    LabeledPoint* _p;
};

struct MoreLeftmost {
    bool operator()(LabelEvent const& e1, LabelEvent const& e2) const
    {
        qreal x1 = e1.x(), x2 = e2.x();
        if (x1 < x2) {
            return true;
        } else if (x1 > x2) {
            return false;
        } else {
            return e1.point() < e2.point();
        }
    }
};

struct HigherTop {
    bool operator()(VerticalSegment const& s1, VerticalSegment const& s2) const
    {
        qreal y1 = s1.top(), y2 = s2.top();
        if (y1 < y2) {
            return true;
        } else if (y1 > y2) {
            return false;
        } else {
            return s1.point() < s2.point();
        }
    }
};

struct LabelsOnSweepline
{
    explicit LabelsOnSweepline(LabelModel const& labelModel)
        : _labelWidth(labelModel.labelWidth()),
          _labelHeight(labelModel.labelHeight())
    {
    }

    void add(LabeledPoint* p)
    {
        p->labelFreeness() = 0.0;
        _labels.emplace(p);
    }
    void remove(LabeledPoint* p)
    {
        p->labelFreeness() /= (_labelWidth * _labelHeight);
        _labels.erase(p);
    }

    qreal computeFreeArea(qreal stripWidth)
    {
        std::set<VerticalSegment, HigherTop> segments;
        for (auto p : _labels) {
            qreal y = p->labelCenter().y();
            // NOTE: GCC 4.7.2's std::set apparently does not have emplace yet (even though
            // std::unordered_set does) -> use insert
            segments.insert( VerticalSegment(p, y - _labelHeight/2.0, y + _labelHeight/2.0) );
        }

        qreal result = 0.0;
        while (!segments.empty()) {
            VerticalSegment s1 = *segments.begin();
            segments.erase(segments.begin());
            qreal freeHeight;
            if (segments.empty()) { // s1 is only/last segment
                freeHeight = s1.bottom() - s1.top();
            } else {
                VerticalSegment s2 = *segments.begin();
                if (s2.bottom() <= s1.bottom()) { // s2 contained in s1
                    freeHeight = s2.top() - s1.top();
                    s1.top() = s2.bottom();
                    segments.erase(segments.begin());
                    segments.insert(s1);
                } else if (s2.top() < s1.bottom()) { // s2 overlaps bottom of s1
                    freeHeight = s2.top() - s1.top();
                    s2.top() = s1.bottom();
                    segments.erase(segments.begin());
                    segments.insert(s2);
                } else { // s1 and s2 are disjoint
                    freeHeight = s1.bottom() - s1.top();
                }
            }
            s1.point()->labelFreeness() += stripWidth * freeHeight;
            result += stripWidth * freeHeight;
        }
        return result;
    }
private:
    std::unordered_set<LabeledPoint*> _labels;
    qreal _labelWidth, _labelHeight;
};

} // unnamed namespace

void StaticLabeling::recomputeLabelFreenesses()
{
    // The standard sweepline algorithm for Klee's Measure Problem, but
    // with a different computation on the sweepline.
    if (_labels.empty()) {
        _totalFreeArea = 0.0;
        return;
    }

    std::vector<LabelEvent> events;
    events.reserve(2*_labels.size());
    for (auto& keyValue: _labels) {
        LabeledPoint* p = &keyValue.second;
        qreal x = p->labelCenter().x();
        events.emplace_back(p, x - _labelModel->labelWidth()/2.0);
        events.emplace_back(p, x + _labelModel->labelWidth()/2.0);
    }
    std::sort(events.begin(), events.end(), MoreLeftmost());

    LabelsOnSweepline sweepline(*_labelModel);
    qreal freeArea = 0.0;
    qreal lastX = events.front().x();
    for (auto& event : events) {
        qreal currentX = event.x();
        freeArea += sweepline.computeFreeArea(currentX - lastX);
        if (event.side() == LeftSide) {
            sweepline.add(event.point());
        } else {
            sweepline.remove(event.point());
        }
        lastX = currentX;
    }
    _totalFreeArea = freeArea;
}

qreal StaticLabeling::summedLabelArea() const
{
    return points() * (qreal)_labelModel->labelArea();
}
