/******************************************************************************
 *
 * Project:  Marching square algorithm
 * Purpose:  Core algorithm implementation for contour line generation.
 * Author:   Oslandia <infos at oslandia dot com>
 *
 ******************************************************************************
 * Copyright (c) 2018, Oslandia <infos at oslandia dot com>
 *
 * SPDX-License-Identifier: MIT
 ****************************************************************************/
#ifndef MARCHING_SQUARE_POLYGON_RING_APPENDER_H
#define MARCHING_SQUARE_POLYGON_RING_APPENDER_H

#include <vector>
#include <list>
#include <map>
#include <deque>
#include <cassert>
#include <iterator>

#include "point.h"
#include "ogr_geometry.h"

namespace marching_squares
{

// Receive rings of different levels and organize them
// into multi-polygons with possible interior rings when requested.
template <typename PolygonWriter> class PolygonRingAppender
{
  private:
    struct Ring
    {
        Ring() : points(), interiorRings()
        {
        }

        Ring(const Ring &other) = default;
        Ring &operator=(const Ring &other) = default;

        LineString points;

        mutable std::vector<Ring> interiorRings;

        const Ring *closestExterior = nullptr;

        bool isIn(const Ring &other) const
        {
            // Check if this is inside other using the winding number algorithm
            auto checkPoint = this->points.front();
            int windingNum = 0;
            auto otherIter = other.points.begin();
            // p1 and p2 define each segment of the ring other that will be
            // tested
            auto p1 = *otherIter;
            while (true)
            {
                otherIter++;
                if (otherIter == other.points.end())
                {
                    break;
                }
                auto p2 = *otherIter;
                if (p1.y <= checkPoint.y)
                {
                    if (p2.y > checkPoint.y)
                    {
                        if (isLeft(p1, p2, checkPoint))
                        {
                            ++windingNum;
                        }
                    }
                }
                else
                {
                    if (p2.y <= checkPoint.y)
                    {
                        if (!isLeft(p1, p2, checkPoint))
                        {
                            --windingNum;
                        }
                    }
                }
                p1 = p2;
            }
            return windingNum != 0;
        }

#ifdef DEBUG
        size_t id() const
        {
            return size_t(static_cast<const void *>(this)) & 0xffff;
        }

        void print(std::ostream &ostr) const
        {
            ostr << id() << ":";
            for (const auto &pt : points)
            {
                ostr << pt.x << "," << pt.y << " ";
            }
        }
#endif
    };

    void processTree(const std::vector<Ring> &tree, int level)
    {
        if (level % 2 == 0)
        {
            for (auto &r : tree)
            {
                writer_.addPart(r.points);
                for (auto &innerRing : r.interiorRings)
                {
                    writer_.addInteriorRing(innerRing.points);
                }
            }
        }
        for (auto &r : tree)
        {
            processTree(r.interiorRings, level + 1);
        }
    }

    // level -> rings
    std::map<double, std::vector<Ring>> rings_;

    PolygonWriter &writer_;

  public:
    const bool polygonize = true;

    PolygonRingAppender(PolygonWriter &writer) : rings_(), writer_(writer)
    {
    }

    void addLine(double level, LineString &ls, bool)
    {
        auto &levelRings = rings_[level];
        if (ls.empty())
        {
            return;
        }
        // Create a new ring from the LineString
        Ring newRing;
        newRing.points.swap(ls);
        // This queue holds the rings to be checked
        std::deque<Ring *> queue;
        std::transform(levelRings.begin(), levelRings.end(),
                       std::back_inserter(queue), [](Ring &r) { return &r; });
        Ring *parentRing = nullptr;
        while (!queue.empty())
        {
            Ring *curRing = queue.front();
            queue.pop_front();
            if (newRing.isIn(*curRing))
            {
                // We know that there should only be one ring per level that we
                // should fit in, so we can discard the rest of the queue and
                // try again with the children of this ring
                parentRing = curRing;
                queue.clear();
                std::transform(curRing->interiorRings.begin(),
                               curRing->interiorRings.end(),
                               std::back_inserter(queue),
                               [](Ring &r) { return &r; });
            }
        }
        // Get a pointer to the list we need to check for rings to include in
        // this ring
        std::vector<Ring> *parentRingList;
        if (parentRing == nullptr)
        {
            parentRingList = &levelRings;
        }
        else
        {
            parentRingList = &(parentRing->interiorRings);
        }
        // We found a valid parent, so we need to:
        // 1. Find all the inner rings of the parent that are inside the new
        // ring
        auto trueGroupIt = std::partition(
            parentRingList->begin(), parentRingList->end(),
            [newRing](Ring &pRing) { return !pRing.isIn(newRing); });
        // 2. Move those rings out of the parent and into the new ring's
        // interior rings
        std::move(trueGroupIt, parentRingList->end(),
                  std::back_inserter(newRing.interiorRings));
        // 3. Get rid of the moved-from elements in the parent's interior rings
        parentRingList->erase(trueGroupIt, parentRingList->end());
        // 4. Add the new ring to the parent's interior rings
        parentRingList->push_back(newRing);
    }

    ~PolygonRingAppender()
    {
        // If there's no rings, nothing to do here
        if (rings_.size() == 0)
            return;

        // Traverse tree of rings
        for (auto &r : rings_)
        {
            // For each level, create a multipolygon by traversing the tree of
            // rings and adding a part for every other level
            writer_.startPolygon(r.first);
            processTree(r.second, 0);
            writer_.endPolygon();
        }
    }
};

}  // namespace marching_squares

#endif