//Copyright (c) 2021 Ultimaker B.V.
//CuraEngine is released under the terms of the AGPLv3 or higher.

#ifndef INFILL_H
#define INFILL_H

#include "infill/LightningGenerator.h"
#include "infill/ZigzagConnectorProcessor.h"
#include "types/EnumSettings.h" //For infill types.
#include "types/Angle.h"
#include "settings/Settings.h"
#include "utils/ExtrusionLine.h"
#include "utils/IntPoint.h"
#include "utils/section_type.h"

namespace cura52
{

    class AABB;
    class SierpinskiFillProvider;
    class SliceMeshStorage;

    class Infill
    {
        friend class InfillTest;

        EFillMethod pattern; //!< the space filling pattern of the infill to generate
        bool zig_zaggify; //!< Whether to connect the end pieces of the support lines via the wall
        bool connect_lines; //!< Whether the lines and zig_zaggification are generated by the connectLines algorithm
        bool connect_polygons; //!< Whether to connect as much polygons together into a single path
        Polygons outer_contour; //!< The area that originally needs to be filled with infill. The input of the algorithm.
        Polygons inner_contour; //!< The part of the contour that will get filled with an infill pattern. Equals outer_contour minus the extra infill walls.
        coord_t infill_line_width; //!< The line width of the infill lines to generate
        coord_t line_distance; //!< The distance between two infill lines / polygons
        coord_t infill_overlap; //!< the distance by which to overlap with the actual area within which to generate infill
        size_t infill_multiplier; //!< the number of infill lines next to each other
        AngleDegrees fill_angle; //!< for linear infill types: the angle of the infill lines (or the angle of the grid)
        coord_t z; //!< height of the layer for which we generate infill
        coord_t shift; //!< shift of the scanlines in the direction perpendicular to the fill_angle
        coord_t max_resolution; //!< Min feature size of the output
        coord_t max_deviation; //!< Max deviation fro the original poly when enforcing max_resolution
        size_t wall_line_count; //!< Number of walls to generate at the boundary of the infill region, spaced \ref infill_line_width apart
        coord_t small_area_width; //!< Maximum width of a small infill region to be filled with walls
        const Point infill_origin; //!< origin of the infill pattern
        bool skip_line_stitching; //!< Whether to bypass the line stitching normally performed for polyline type infills
        bool fill_gaps; //!< Whether to fill gaps in strips of infill that would be too thin to fit the infill lines. If disabled, those areas are left empty.
        bool connected_zigzags; //!< (ZigZag) Whether endpieces of zigzag infill should be connected to the nearest infill line on both sides of the zigzag connector
        bool use_endpieces; //!< (ZigZag) Whether to include endpieces: zigzag connector segments from one infill line to itself
        bool skip_some_zags;  //!< (ZigZag) Whether to skip some zags
        size_t zag_skip_count;  //!< (ZigZag) To skip one zag in every N if skip some zags is enabled
        coord_t pocket_size; //!< The size of the pockets at the intersections of the fractal in the cross 3d pattern
        bool mirror_offset; //!< Indication in which offset direction the extra infill lines are made
        Point current_position;
		double min_area;
        static constexpr double one_over_sqrt_2 = 0.7071067811865475244008443621048490392848359376884740; //!< 1.0 / sqrt(2.0)
    public:

		Infill(EFillMethod pattern
			, bool zig_zaggify
			, bool connect_polygons
			, const Polygons& in_outline
			, coord_t infill_line_width
			, coord_t line_distance
			, coord_t infill_overlap
			, size_t infill_multiplier
			, AngleDegrees fill_angle
			, coord_t z
			, coord_t shift
			, coord_t max_resolution
			, coord_t max_deviation
			, size_t wall_line_count = 0
			, const Point& infill_origin = Point()
			, bool skip_line_stitching = false
			, bool fill_gaps = true
			, bool connected_zigzags = false
			, bool use_endpieces = false
			, bool skip_some_zags = false
			, size_t zag_skip_count = 0
			, coord_t pocket_size = 0
			, coord_t min_area = 0
		)
			: pattern(pattern)
			, zig_zaggify(zig_zaggify)
			, connect_polygons(connect_polygons)
			, outer_contour(in_outline)
			, infill_line_width(infill_line_width)
			, line_distance(line_distance)
			, infill_overlap(infill_overlap)
			, infill_multiplier(infill_multiplier)
			, fill_angle(fill_angle)
			, z(z)
			, shift(shift)
			, max_resolution(max_resolution)
			, max_deviation(max_deviation)
			, wall_line_count(wall_line_count)
			, infill_origin(infill_origin)
			, skip_line_stitching(skip_line_stitching)
			, fill_gaps(fill_gaps)
			, connected_zigzags(connected_zigzags)
			, use_endpieces(use_endpieces)
			, skip_some_zags(skip_some_zags)
			, zag_skip_count(zag_skip_count)
			, pocket_size(pocket_size)
			, mirror_offset(zig_zaggify)
			, min_area(min_area)
        {
            //TODO: The connected lines algorithm is only available for linear-based infill, for now.
            //We skip ZigZag, Cross and Cross3D because they have their own algorithms. Eventually we want to replace all that with the new algorithm.
            //Cubic Subdivision ends lines in the center of the infill so it won't be effective.
            connect_lines = zig_zaggify && (pattern == EFillMethod::LINES || pattern == EFillMethod::TRIANGLES || pattern == EFillMethod::GRID || pattern == EFillMethod::CUBIC || pattern == EFillMethod::TETRAHEDRAL || pattern == EFillMethod::QUARTER_CUBIC || pattern == EFillMethod::TRIHEXAGON);
            small_area_width = 0;
			if (min_area>0)
			{
				for (int n = 0; n < outer_contour.paths.size(); n++)
				{
					if (std::abs(INT2MM2(ClipperLib::Area(outer_contour.paths[n]))) < min_area * 0.35)
					{
						outer_contour.paths.erase(outer_contour.paths.begin() + n);
						n--;
					}
				}
			}
            current_position = Point();
        }

        /*!
         * Generate the infill.
         *
         * \param toolpaths (output) The resulting variable-width paths (from the extra walls around the pattern). Binned by inset_idx.
         * \param result_polygons (output) The resulting polygons (from concentric infill)
         * \param result_lines (output) The resulting line segments (from linear infill types)
         * \param settings A settings storage to use for generating variable-width walls.
         * \param cross_fill_provider Any pre-computed cross infill pattern, if the Cross or Cross3D pattern is selected.
         * \param mesh A mesh for which to generate infill (should only be used for non-helper-mesh objects).
         * \param[in] cross_fill_provider The cross fractal subdivision decision functor
         */
        void generate(std::vector<VariableWidthLines>& toolpaths, Polygons& result_polygons, Polygons& result_lines, const Settings& settings, const SierpinskiFillProvider* cross_fill_provider = nullptr, const LightningLayer* lightning_layer = nullptr, const SliceMeshStorage* mesh = nullptr);

        Polygons generateWallToolPathsT(std::vector<VariableWidthLines>& toolpaths, Polygons& outer_contour, const size_t wall_line_count, const coord_t line_width, const coord_t infill_overlap, const Settings& settings, int layer_idx, cura54::SectionType section_type);

        void generateThomas(std::vector<VariableWidthLines>& toolpaths,
            Polygons& result_polygons,
            Polygons& result_lines,
            const Settings& settings,
            int layer_idx,
            cura54::SectionType section_type,
            const SierpinskiFillProvider* cross_fill_provider,
            const LightningLayer* lightning_trees,
            const SliceMeshStorage* mesh);

        /*!
         * Generate the wall toolpaths of an infill area. It will return the inner contour and set the inner-contour.
         * This function is called within the generate() function but can also be called stand-alone
         *
         * \param toolpaths [out] The generated toolpaths. Binned by inset_idx.
         * \param outer_contour [in,out] the outer contour, this is offsetted with the infill overlap
         * \param wall_line_count [in] The number of walls that needs to be generated
         * \param line_width [in] The optimum wall line width of the walls
         * \param infill_overlap [in] The overlap of the infill
         * \param settings [in] A settings storage to use for generating variable-width walls.
         * \return The inner contour of the wall toolpaths
         */
        static Polygons generateWallToolPaths(std::vector<VariableWidthLines>& toolpaths, Polygons& outer_contour, const size_t wall_line_count, const coord_t line_width, const coord_t infill_overlap, const Settings& settings);

        void setCurrentPosition(const Point position) { current_position = position; }
    private:
        /*!
         * Generate the infill pattern without the infill_multiplier functionality
         */
        void _generate(std::vector<VariableWidthLines>& toolpaths, Polygons& result_polygons, Polygons& result_lines, const Settings& settings, const SierpinskiFillProvider* cross_fill_pattern = nullptr, const LightningLayer* lightning_layer = nullptr, const SliceMeshStorage* mesh = nullptr);

        /*!
         * Multiply the infill lines, so that any single line becomes [infill_multiplier] lines next to each other.
         *
         * This is done in a way such that there is not overlap between the lines
         * except the middle original one if the multiplier is odd.
         *
         * This introduces a lot of line segments.
         *
         * \param[in,out] result_polygons The polygons to be multiplied (input and output)
         * \param[in,out] result_lines The lines to be multiplied (input and output)
         */
        void multiplyInfill(Polygons& result_polygons, Polygons& result_lines);

        struct InfillLineSegment
        {
            /*!
             * Creates a new infill line segment.
             *
             * The previous and next line segments will not yet be connected. You
             * have to set those separately.
             * \param start Where the line segment starts.
             * \param end Where the line segment ends.
             */
            InfillLineSegment(const Point start, const size_t start_segment, const size_t start_polygon, const Point end, const size_t end_segment, const size_t end_polygon)
                : start(start)
                , start_segment(start_segment)
                , start_polygon(start_polygon)
                , end(end)
                , end_segment(end_segment)
                , end_polygon(end_polygon)
                , previous(nullptr)
                , next(nullptr)
            {
            };

            /*!
             * Where the line segment starts.
             */
            Point start;

            /*!
             * Which polygon line segment the start of this infill line belongs to.
             *
             * This is an index of a vertex in the PolygonRef that this infill line
             * is inside. It is used to disambiguate between the start and end of
             * the line segment.
             */
            size_t start_segment;

            /*!
             * Which polygon the start of this infill line belongs to.
             *
             * This is an index of a PolygonRef that this infill line
             * is inside. It is used to know which polygon the start segment belongs to.
             */
            size_t start_polygon;

            /*!
             * Where the line segment ends.
             */
            Point end;

            /*!
             * Which polygon line segment the end of this infill line belongs to.
             *
             * This is an index of a vertex in the PolygonRef that this infill line
             * is inside. It is used to disambiguate between the start and end of
             * the line segment.
             */
            size_t end_segment;

            /*!
             * Which polygon the end of this infill line belongs to.
             *
             * This is an index of a PolygonRef that this infill line
             * is inside. It is used to know which polygon the end segment belongs to.
             */
            size_t end_polygon;

            /*!
             * The previous line segment that this line segment is connected to, if
             * any.
             */
            InfillLineSegment* previous;

            /*!
             * The next line segment that this line segment is connected to, if any.
             */
            InfillLineSegment* next;

            /*!
             * Compares two infill line segments for equality.
             *
             * This is necessary for putting line segments in a hash set.
             * \param other The line segment to compare this line segment with.
             */
            bool operator ==(const InfillLineSegment& other) const;
        };

        /*!
         * Stores the infill lines (a vector) for each line of a polygon (a vector)
         * for each polygon in a Polygons object that we create a zig-zaggified
         * infill pattern for.
         */
        std::vector<std::vector<std::vector<InfillLineSegment*>>> crossings_on_line;

        /*!
         * Generate gyroid infill
         * \param result_polylines (output) The resulting polylines
         * \param result_polygons (output) The resulting polygons, if zigzagging accidentally happened to connect gyroid lines in a circle.
         */
        void generateGyroidInfill(Polygons& result_polylines, Polygons& result_polygons);

        /*!
         * Generate lightning fill aka minfill aka 'Ribbed Support Vault Infill', see Tricard,Claux,Lefebvre/'Ribbed Support Vaults for 3D Printing of Hollowed Objects'
         * see https://hal.archives-ouvertes.fr/hal-02155929/document
         * \param result (output) The resulting polygons
         */
        void generateLightningInfill(const LightningLayer* lightning_layer, Polygons& result_lines);

        /*!
         * Generate sparse concentric infill
         *
         * \param toolpaths (output) The resulting toolpaths. Binned by inset_idx.
         * \param inset_value The offset between each consecutive two polygons
         */
        void generateConcentricInfill(std::vector<VariableWidthLines>& toolpaths, const Settings& settings);

        void generateHoneycombInfill(Polygons& result, int _line_distance);

        /*!
         * Generate a rectangular grid of infill lines
         * \param[out] result (output) The resulting lines
         */
        void generateGridInfill(Polygons& result);

        /*!
         * Generate a shifting triangular grid of infill lines, which combine with consecutive layers into a cubic pattern
         * \param[out] result (output) The resulting lines
         */
        void generateCubicInfill(Polygons& result);

        /*!
         * Generate a double shifting square grid of infill lines, which combine with consecutive layers into a tetrahedral pattern
         * \param[out] result (output) The resulting lines
         */
        void generateTetrahedralInfill(Polygons& result);

        /*!
         * Generate a double shifting square grid of infill lines, which combine with consecutive layers into a quarter cubic pattern
         * \param[out] result (output) The resulting lines
         */
        void generateQuarterCubicInfill(Polygons& result);

        /*!
         * Generate a single shifting square grid of infill lines.
         * This is used in tetrahedral infill (Octet infill) and in Quarter Cubic infill.
         *
         * \param pattern_z_shift The amount by which to shift the whole pattern down
         * \param angle_shift The angle to add to the infill_angle
         * \param[out] result (output) The resulting lines
         */
        void generateHalfTetrahedralInfill(float pattern_z_shift, int angle_shift, Polygons& result);

        /*!
         * Generate a triangular grid of infill lines
         * \param[out] result (output) The resulting lines
         */
        void generateTriangleInfill(Polygons& result);

        /*!
         * Generate a triangular grid of infill lines
         * \param[out] result (output) The resulting lines
         */
        void generateTrihexagonInfill(Polygons& result);

        /*!
         * Generate a 3d pattern of subdivided cubes on their points
         * \param[out] result The resulting lines
         * \param[in] mesh Where the Cubic Subdivision Infill precomputation is stored
         */
        void generateCubicSubDivInfill(Polygons& result, const SliceMeshStorage& mesh);

        /*!
         * Generate a 3d pattern of subdivided cubes on their points
         * \param[in] cross_fill_provider Where the cross fractal precomputation is stored
         * \param[out] result_polygons The resulting polygons
         * \param[out] result_lines The resulting lines
         */
        void generateCrossInfill(const SierpinskiFillProvider& cross_fill_provider, Polygons& result_polygons, Polygons& result_lines);

        /*!
         * Convert a mapping from scanline to line_segment-scanline-intersections (\p cut_list) into line segments, using the even-odd rule
         * \param[out] result (output) The resulting lines
         * \param rotation_matrix The rotation matrix (un)applied to enforce the angle of the infill
         * \param scanline_min_idx The lowest index of all scanlines crossing the polygon
         * \param line_distance The distance between two lines which are in the same direction
         * \param boundary The axis aligned boundary box within which the polygon is
         * \param cut_list A mapping of each scanline to all y-coordinates (in the space transformed by rotation_matrix) where the polygons are crossing the scanline
         * \param total_shift total shift of the scanlines in the direction perpendicular to the fill_angle.
         */
        void addLineInfill(Polygons& result,
            const PointMatrix& rotation_matrix,
            const int scanline_min_idx,
            const int line_distance,
            const AABB boundary,
            std::vector<std::vector<coord_t>>& cut_list,
            coord_t total_shift);

        /*!
         * generate lines within the area of \p in_outline, at regular intervals of \p line_distance
         *
         * idea:
         * intersect a regular grid of 'scanlines' with the area inside \p in_outline
         *
         * \param[out] result (output) The resulting lines
         * \param line_distance The distance between two lines which are in the same direction
         * \param infill_rotation The angle of the generated lines
         * \param extra_shift extra shift of the scanlines in the direction perpendicular to the infill_rotation
         */
        void generateLineInfill(Polygons& result, int line_distance, const double& infill_rotation, coord_t extra_shift);

        /*!
         * Function for creating linear based infill types (Lines, ZigZag).
         *
         * This function implements the basic functionality of Infill::generateLineInfill (see doc of that function),
         * but makes calls to a ZigzagConnectorProcessor which handles what to do with each line segment - scanline intersection.
         *
         * It is called only from Infill::generateLineinfill and Infill::generateZigZagInfill.
         *
         * \param[out] result (output) The resulting lines
         * \param line_distance The distance between two lines which are in the same direction
         * \param rotation_matrix The rotation matrix (un)applied to enforce the angle of the infill
         * \param zigzag_connector_processor The processor used to generate zigzag connectors
         * \param connected_zigzags Whether to connect the endpiece zigzag segments on both sides to the same infill line
         * \param extra_shift extra shift of the scanlines in the direction perpendicular to the fill_angle
         */
        void generateLinearBasedInfill(Polygons& result, const int line_distance, const PointMatrix& rotation_matrix, ZigzagConnectorProcessor& zigzag_connector_processor, const bool connected_zigzags, coord_t extra_shift);

        /*!
         *
         * generate lines within the area of [in_outline], at regular intervals of [line_distance]
         * idea:
         * intersect a regular grid of 'scanlines' with the area inside [in_outline] (see generateLineInfill)
         * zigzag:
         * include pieces of boundary, connecting the lines, forming an accordion like zigzag instead of separate lines    |_|^|_|
         *
         * Note that ZigZag consists of 3 types:
         * - without endpieces
         * - with disconnected endpieces
         * - with connected endpieces
         *
         *     <--
         *     ___
         *    |   |   |
         *    |   |   |
         *    |   |___|
         *         -->
         *
         *        ^ = even scanline
         *  ^            ^ no endpieces
         *
         * start boundary from even scanline! :D
         *
         *
         *                 v  disconnected end piece: leave out last line segment
         *          _____
         *   |     |     |  \                     .
         *   |     |     |  |
         *   |_____|     |__/
         *
         *   ^     ^     ^    scanlines
         *
         *
         *                 v  connected end piece
         *          ________
         *   |     |     |  \                      .
         *   |     |     |  |
         *   |_____|     |__/                       .
         *
         *   ^     ^     ^    scanlines
         *
         * \param[out] result (output) The resulting lines
         * \param line_distance The distance between two lines which are in the same direction
         * \param infill_rotation The angle of the generated lines
         */
        void generateZigZagInfill(Polygons& result, const coord_t line_distance, const double& infill_rotation);

        /*!
         * determine how far the infill pattern should be shifted based on the values of infill_origin and \p infill_rotation
         *
         * \param[in] infill_rotation the angle the infill pattern is rotated through
         *
         * \return the distance the infill pattern should be shifted
         */
        coord_t getShiftOffsetFromInfillOriginAndRotation(const double& infill_rotation);

        /*!
         * Connects infill lines together so that they form polylines.
         *
         * In most cases it will end up with only one long line that is more or less
         * optimal. The lines are connected on their ends by extruding along the
         * border of the infill area, similar to the zigzag pattern.
         * \param[in/out] result_lines The lines to connect together.
         */
        void connectLines(Polygons& result_lines);
    };

}//namespace cura52

#endif // INFILL_H
