#pragma region CPL License
/*
Nuclex Native Framework
Copyright (C) 2002-2015 Nuclex Development Labs

This library is free software; you can redistribute it and/or
modify it under the terms of the IBM Common Public License as
published by the IBM Corporation; either version 1.0 of the
License, or (at your option) any later version.

This library is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
IBM Common Public License for more details.

You should have received a copy of the IBM Common Public
License along with this library
*/
#pragma endregion // CPL License

#ifndef NUCLEX_GEOMETRY_LINES_GENERATORS_POLYLINE2GENERATOR_H
#define NUCLEX_GEOMETRY_LINES_GENERATORS_POLYLINE2GENERATOR_H

#include "Nuclex/Geometry/Config.h"
#include "Nuclex/Geometry/Lines/PolyLine2.h"
#include "Nuclex/Geometry/Lines/Line2.h"

namespace Nuclex { namespace Geometry { namespace Lines { namespace Generators {

  // ------------------------------------------------------------------------------------------- //

  /// <summary>Primitive generation methods for 2D poly lines</summary>
  template <typename TScalar>
  class PolyLine2Generator {

    #pragma region class DouglasPeuckerSimplifier

    /// <summary>Simplifies poly lines using the Douglas-Peucker algorithm</summary>
    private: class DouglasPeuckerSimplifier {

      /// <summary>Range of indices, left index and right index (inclusive)</summary>
      private: typedef std::pair<std::size_t, std::size_t> IndexRange;

      /// <summary>Initializes a new Douglas-Peucker poly line simplifier</summary>
      /// <param name="polyLine">Poly line of which a simplified version will be built</param>
      public: DouglasPeuckerSimplifier(const PolyLine2<TScalar> &polyLine) :
        polyLine(polyLine) {}

      /// <summary>
      ///   Builds a simplified poly line out of the poly line the simplifier was constructed with
      /// </summary>
      /// <param name="maximumError">
      ///   Distance under which a vertex will be collapsed into the line segment it lies on
      /// </param>
      /// <returns>The simplified poly line</returns>
      public: PolyLine2<TScalar> GetSimplified(TScalar maximumError) const {
        std::size_t vertexCount = this->polyLine.Vertices.size();
        if(vertexCount < 3) {
          return this->polyLine.Subset(0, vertexCount);
        }

        PolyLine2<TScalar> result;
        result.Vertices.reserve(vertexCount / 4);
        result.Vertices.push_back(this->polyLine.Vertices[0]);

        eliminateOrSplit(
          IndexRange(0, vertexCount - 1), maximumError * maximumError, result
        );

        return result;
      }

      /// <summary>
      ///   Eliminates all points within the span or performs a recursive split on the vertex
      ///   with the largest error
      /// </summary>
      /// <param name="span">Span in which vertices will be analyzed</param>
      /// <param name="maximumSquaredError">
      ///   Distance under which a vertex will be collapsed into the line segment it lies on
      /// </param>
      /// <param name="output">Poly line in which the final vertices will be placed</param>
      private: void eliminateOrSplit(
        const IndexRange &span, TScalar maximumSquaredError, PolyLine2<TScalar> &output
      ) const {
        Line2<TScalar> line = Line2<TScalar>::FromSegment(
          this->polyLine.Vertices[span.first], this->polyLine.Vertices[span.second]
        );

        // This method will only be called with at least 1 interior vertex
        assert((span.first + 1 < span.second) && "eliminateOrSplit() has at least 3 vertices");

        // Initialize the largest error using the first interior vertex
        std::size_t largestErrorIndex = span.first + 1;
        TScalar largestSquaredError = getSquaredPerpendicularDistance(
          line, this->polyLine.Vertices[largestErrorIndex]
        );

        // Scan the remaining interior vertices to find the one with the largest deviation
        for(std::size_t index = span.first + 2; index < span.second; ++index) {
          TScalar currentSquaredError = getSquaredPerpendicularDistance(
            line, this->polyLine.Vertices[index]
          );
          if(currentSquaredError > largestSquaredError) {
            largestErrorIndex = index;
            largestSquaredError = currentSquaredError;
          }
        }

        // If all vertices are below the maximum error, eliminate all of them
        if(largestSquaredError < maximumSquaredError) {
          output.Vertices.push_back(this->polyLine.Vertices[span.second]);
        } else {
          if(largestErrorIndex > span.first + 1) { // Is the segment long enough to simplify?
            eliminateOrSplit(
              IndexRange(0, largestErrorIndex), maximumSquaredError, output
            );
          } else {
            output.Vertices.push_back(this->polyLine.Vertices[largestErrorIndex]);
          }
          if(span.second > largestErrorIndex + 1) { // Is the segment long enough to simplify?
            eliminateOrSplit(
              IndexRange(largestErrorIndex, span.second), maximumSquaredError, output
            );
          } else {
            output.Vertices.push_back(this->polyLine.Vertices[span.second]);
          }
        }
      }

      /// <summary>Calculates the squared distance of a point to a line</summary>
      /// <param name="line">Line to which the distance will be calculated</param>
      /// <param name="point">Point whose distance to the line will be calculated</param>
      /// <returns>The squared distance of the point to the line</returns>
      private: static TScalar getSquaredPerpendicularDistance(
        const Line2<TScalar> &line, const Point2<TScalar> &point
      ) {
        Vector2<TScalar> pointOffset = point - line.Origin;
        TScalar t = Vector2<TScalar>::Dot(pointOffset, line.Direction);

        return Point2<TScalar>::SquaredDistanceBetween(
          point, line.Origin + (line.Direction * t)
        );
      }

      private: DouglasPeuckerSimplifier(const DouglasPeuckerSimplifier &) = delete;
      private: DouglasPeuckerSimplifier &operator =(const DouglasPeuckerSimplifier &) = delete;

      /// <summary>Poly line that is being simplified</summary>
      private: const PolyLine2<TScalar> polyLine;

    };

    #pragma endregion // class DouglasPeuckerSimplifier

    #pragma region class SpineMerger

    /// <summary>Merges poly lines by finding common spines</summary>
    private: class SpineMerger {

      /// <summary>Initializes a new spine merger for a set of poly lines</summary>
      /// <param name="polyLines">Lines the spine merger will merge</param>
      /// <param name="count">Number of poly lines in the input array</param>
      public: SpineMerger(const PolyLine2<TScalar> *polyLines, std::size_t count) :
        polyLines(polyLines, count) {}

      // Method
      // - find beginning order and indices (B, A10, 

      /// <summary>Merges the input poly lines into a single output poly line</summary>
      /// <param name="minimumOverlap">
      ///   Minimum number of poly lines that need to overlap to be covered in the output line
      /// </param>
      /// <returns>The merged poly line</returns>
      public: PolyLine2<TScalar> Merge(std::size_t minimumOverlapCount = 1) const {
        LineAndVertexIndex optimalStartingPoint;
        for(std::size_t index = 0; index < this->count; ++index) {
          //Point2<TScalar>
          
        }
      }

      /// <summary>
      ///   Addresses one vertex by the index of its poly line and the vertex itself
      /// </summary>
      private: typedef std::pair<std::size_t, std::size_t> LineAndVertexIndex;

      /// <summary>Contains one index for each input poly line</summary>
      private: typedef std::vector<std::size_t> LineIndices;

      /// <summary>Poly lines that will be merged</summary>
      private: const PolyLine2<TScalar> *polyLines;
      /// <summary>Number of poly lines that will be merged</summary>
      private: std::size_t count;

    };

    #pragma endregion // class SpineMerger

    /// <summary>Creates a simplified poly line using the Douglas-Peucker algorithm</summary>
    /// <param name="polyLine">Poly line that will be simplified</param>
    /// <param name="maximumError">Maximum error under which vertices can be eliminated</param>
    public: static PolyLine2<TScalar> GetDouglasPeuckerSimplified(
      const PolyLine2<TScalar> &polyLine, TScalar maximumError
    ) {
      return DouglasPeuckerSimplifier(polyLine).GetSimplified(maximumError);
    }

    /// <summary>Merges the overlapping sections of the specified poly lines</summary>
    /// <param name="polyLines">Poly lines that will be averaged</param>
    /// <param name="count">Number of poly lines that will be averaged</param>
    public: static PolyLine2<TScalar> GetSpineMerged(
      const PolyLine2<TScalar> *polyLines, std::size_t count
    ) {
      return SpineMerger(polyLines, count).Merge();
    }

  };

  // ------------------------------------------------------------------------------------------- //

}}}} // namespace Nuclex::Geometry::Lines::Generators

#endif // NUCLEX_GEOMETRY_LINES_GENERATORS_POLYLINE2GENERATOR_H