<commit_before>//Copyright (c) 2021 <NAME>.
//CuraEngine is released under the terms of the AGPLv3 or higher.

#ifndef PATHORDERMONOTONIC_H
#define PATHORDERMONOTONIC_H

#include <cmath> //For std::sin() and std::cos().
#include <unordered_set> //To track starting points of monotonic sequences.
#include <unordered_map> //To track monotonic sequences.

#include "PathOrder.h"
#include "PathOrderPath.h"

namespace cura
{

/*!
 * Class that orders paths monotonically.
 *
 * This is a utility class that changes the order in which things are printed,
 * to ensure that they are printed in the same major direction. Printing
 * adjacent lines in the same direction ensures that they layer on top of each
 * other in the same way. That helps to make the entire surface look consistent.
 *
 * To use this class, first create an instance and provide some parameters as
 * metadata. Then add polygons and polylines to the class. Then call the
 * \ref optimize function to compute the order. Finally, print the polygons and
 * polylines in the \ref paths field in the order in which they are given.
 *
 * In the output of this class, polylines and polygons are combined into a
 * single list: \ref paths . Each path contains a pointer to the original
 * polygon data, as well as whether that data represented a polygon or a
 * polyline, which direction to print the path in, and where to start along the
 * path.
 *
 * The monotonic order does not use the Z seam settings. It is meant to apply
 * only to polylines. If given polygons, it will place the seam in the location
 * closest to the source direction of the monotonicity vector.
 */
template<typename PathType>
class PathOrderMonotonic : public PathOrder<PathType>
{
public:
    using Path = PathOrderPath<PathType>;
    using PathOrder<PathType>::coincident_point_distance;

    PathOrderMonotonic(const AngleRadians monotonic_direction, const coord_t max_adjacent_distance, const Point start_point)
      //The monotonic vector needs to rotate clockwise instead of counter-clockwise, the same as how the infill patterns are generated.
    : monotonic_vector(-std::cos(monotonic_direction) * monotonic_vector_resolution, std::sin(monotonic_direction) * monotonic_vector_resolution)
    , max_adjacent_distance(max_adjacent_distance)
    {
        this->start_point = start_point;
    }

    void optimize()
    {
        if(this->paths.empty())
        {
            return;
        }

        //Get the vertex data and store it in the paths.
        for(Path& path : this->paths)
        {
            path.converted = path.getVertexData();
        }

        std::vector<Path> reordered; //To store the result in. At the end, we'll std::swap with the real paths.
        reordered.reserve(this->paths.size());

        //First print all the looping polygons, if there are any.
        std::vector<Path*> polylines; //Also find all polylines and store them in a vector that we can sort in-place without making copies all the time.
        this->detectLoops(); //Always filter out loops. We don't specifically want to print those in monotonic order.
        for(Path& path : this->paths)
        {
            if(path.is_closed || path.vertices->size() <= 1)
            {
                reordered.push_back(path);
            }
            else
            {
                polylines.push_back(&path);
                // Assign an invalid starting vertex to indicate we don't know the starting point yet.
                polylines.back()->start_vertex = polylines.back()->converted->size();
            }
        }

        //Sort the polylines by their projection on the monotonic vector. This helps find adjacent lines quickly.
        std::sort(polylines.begin(), polylines.end(), [this](Path* a, Path* b) {
            const coord_t a_start_projection = dot(a->converted->front(), monotonic_vector);
            const coord_t a_end_projection = dot(a->converted->back(), monotonic_vector);
            const coord_t a_projection = std::min(a_start_projection, a_end_projection); //The projection of a path is the endpoint furthest back of the two endpoints.

            const coord_t b_start_projection = dot(b->converted->front(), monotonic_vector);
            const coord_t b_end_projection = dot(b->converted->back(), monotonic_vector);
            const coord_t b_projection = std::min(b_start_projection, b_end_projection);

            return a_projection < b_projection;
        });
        //Create a bucket grid to be able to find adjacent lines quickly.
        SparsePointGridInclusive<Path*> line_bucket_grid(MM2INT(2)); //Grid size of 2mm.
        for(Path* polyline : polylines)
        {
            if(! polyline->converted->empty())
            {
                line_bucket_grid.insert(polyline->converted->front(), polyline);
                line_bucket_grid.insert(polyline->converted->back(), polyline);
            }
        }

        //Create sequences of line segments that get printed together in a monotonic direction.
        //There are several constraints we impose here:
        // - Strings of incident polylines are printed in sequence. That is, if their endpoints are incident.
        //   - The endpoint of the string that is earlier in the monotonic direction will get printed first.
        //   - The start_vertex of this line will already be set to indicate where to start from.
        // - If a line overlaps with another line in the perpendicular direction, and is within max_adjacent_distance (~1 line width) in the monotonic direction, it must be printed in monotonic order.
        //   - The earlier line is marked as being in sequence with the later line.
        //   - The later line is no longer a starting point, unless there are multiple adjacent lines before it.
        //The ``starting_lines`` set indicates possible locations to start from. Each starting line represents one "sequence", which is either a set of adjacent line segments or a string of polylines.
        //The ``connections`` map indicates, starting from each starting segment, the sequence of line segments to print in order.
        //Note that for performance reasons, the ``connections`` map will sometimes link the end of one segment to the start of the next segment. This link should be ignored.
        const Point perpendicular = turn90CCW(monotonic_vector); //To project on to detect adjacent lines.

        std::unordered_set<Path*> connected_lines; //Lines that are reachable from one of the starting lines through its connections.
        std::unordered_set<Path*> starting_lines; //Starting points of a linearly connected segment.
        std::unordered_map<Path*, Path*> connections; //For each polyline, which polyline it overlaps with, closest in the projected order.

        for(auto polyline_it = polylines.begin(); polyline_it != polylines.end(); polyline_it++)
        {
            if(connections.find(*polyline_it) != connections.end()) //Already connected this one through a polyline.
            {
                continue;
            }
            //First find out if this polyline is part of a string of polylines.
            std::deque<Path*> polystring = findPolylineString(*polyline_it, line_bucket_grid, monotonic_vector);

            //If we're part of a string of polylines, connect up the whole string and mark all of them as being connected.
            if(polystring.size() > 1)
            {
                starting_lines.insert(polystring[0]);
                for(size_t i = 0; i < polystring.size() - 1; ++i) //Iterate over every pair of adjacent polylines in the string (so skip the last one)!
                {
                    connections[polystring[i]] = polystring[i + 1];
                    connected_lines.insert(polystring[i + 1]);

                    //Even though we chain polylines, we still want to find lines that they overlap with.
                    //The strings of polylines may still have weird shapes which interweave with other strings of polylines or loose lines.
                    //So when a polyline string comes into contact with other lines, we still want to guarantee their order.
                    //So here we will look for which lines they come into contact with, and thus mark those as possible starting points, so that they function as a new junction.
                    const std::vector<Path*> overlapping_lines = getOverlappingLines(std::find(polylines.begin(), polylines.end(), polystring[i]), perpendicular, polylines);
                    for(Path* overlapping_line : overlapping_lines)
                    {
                        if(std::find(polystring.begin(), polystring.end(), overlapping_line) == polystring.end()) //Mark all overlapping lines not part of the string as possible starting points.
                        {
                            starting_lines.insert(overlapping_line);
                            starting_lines.insert(polystring[i + 1]); //Also be able to re-start from this point in the string.
                        }
                    }
                }
            }
            else //Not a string of polylines, but simply adjacent line segments.
            {
                if(connected_lines.find(*polyline_it) == connected_lines.end()) //Nothing connects to this line yet.
                {
                    starting_lines.insert(*polyline_it); //This is a starting point then.
                }
                const std::vector<Path*> overlapping_lines = getOverlappingLines(polyline_it, perpendicular, polylines);
                if(overlapping_lines.size() == 1) //If we're not a string of polylines, but adjacent to only one other polyline, create a sequence of polylines.
                {
                    connections[*polyline_it] = overlapping_lines[0];
                    if(connected_lines.contains(overlapping_lines[0])) //This line was already connected to.
                    {
                        starting_lines.insert(overlapping_lines[0]); //Multiple lines connect to it, so we must be able to start there.<commit_msg>Use contains instead of find<commit_after>//Copyright (c) 2021 Ultimaker B.V.
//CuraEngine is released under the terms of the AGPLv3 or higher.

#ifndef PATHORDERMONOTONIC_H
#define PATHORDERMONOTONIC_H

#include <cmath> //For std::sin() and std::cos().
#include <unordered_set> //To track starting points of monotonic sequences.
#include <unordered_map> //To track monotonic sequences.

#include "PathOrder.h"
#include "PathOrderPath.h"

namespace cura
{

/*!
 * Class that orders paths monotonically.
 *
 * This is a utility class that changes the order in which things are printed,
 * to ensure that they are printed in the same major direction. Printing
 * adjacent lines in the same direction ensures that they layer on top of each
 * other in the same way. That helps to make the entire surface look consistent.
 *
 * To use this class, first create an instance and provide some parameters as
 * metadata. Then add polygons and polylines to the class. Then call the
 * \ref optimize function to compute the order. Finally, print the polygons and
 * polylines in the \ref paths field in the order in which they are given.
 *
 * In the output of this class, polylines and polygons are combined into a
 * single list: \ref paths . Each path contains a pointer to the original
 * polygon data, as well as whether that data represented a polygon or a
 * polyline, which direction to print the path in, and where to start along the
 * path.
 *
 * The monotonic order does not use the Z seam settings. It is meant to apply
 * only to polylines. If given polygons, it will place the seam in the location
 * closest to the source direction of the monotonicity vector.
 */
template<typename PathType>
class PathOrderMonotonic : public PathOrder<PathType>
{
public:
    using Path = PathOrderPath<PathType>;
    using PathOrder<PathType>::coincident_point_distance;

    PathOrderMonotonic(const AngleRadians monotonic_direction, const coord_t max_adjacent_distance, const Point start_point)
      //The monotonic vector needs to rotate clockwise instead of counter-clockwise, the same as how the infill patterns are generated.
    : monotonic_vector(-std::cos(monotonic_direction) * monotonic_vector_resolution, std::sin(monotonic_direction) * monotonic_vector_resolution)
    , max_adjacent_distance(max_adjacent_distance)
    {
        this->start_point = start_point;
    }

    void optimize()
    {
        if(this->paths.empty())
        {
            return;
        }

        //Get the vertex data and store it in the paths.
        for(Path& path : this->paths)
        {
            path.converted = path.getVertexData();
        }

        std::vector<Path> reordered; //To store the result in. At the end, we'll std::swap with the real paths.
        reordered.reserve(this->paths.size());

        //First print all the looping polygons, if there are any.
        std::vector<Path*> polylines; //Also find all polylines and store them in a vector that we can sort in-place without making copies all the time.
        this->detectLoops(); //Always filter out loops. We don't specifically want to print those in monotonic order.
        for(Path& path : this->paths)
        {
            if(path.is_closed || path.vertices->size() <= 1)
            {
                reordered.push_back(path);
            }
            else
            {
                polylines.push_back(&path);
                // Assign an invalid starting vertex to indicate we don't know the starting point yet.
                polylines.back()->start_vertex = polylines.back()->converted->size();
            }
        }

        //Sort the polylines by their projection on the monotonic vector. This helps find adjacent lines quickly.
        std::sort(polylines.begin(), polylines.end(), [this](Path* a, Path* b) {
            const coord_t a_start_projection = dot(a->converted->front(), monotonic_vector);
            const coord_t a_end_projection = dot(a->converted->back(), monotonic_vector);
            const coord_t a_projection = std::min(a_start_projection, a_end_projection); //The projection of a path is the endpoint furthest back of the two endpoints.

            const coord_t b_start_projection = dot(b->converted->front(), monotonic_vector);
            const coord_t b_end_projection = dot(b->converted->back(), monotonic_vector);
            const coord_t b_projection = std::min(b_start_projection, b_end_projection);

            return a_projection < b_projection;
        });
        //Create a bucket grid to be able to find adjacent lines quickly.
        SparsePointGridInclusive<Path*> line_bucket_grid(MM2INT(2)); //Grid size of 2mm.
        for(Path* polyline : polylines)
        {
            if(! polyline->converted->empty())
            {
                line_bucket_grid.insert(polyline->converted->front(), polyline);
                line_bucket_grid.insert(polyline->converted->back(), polyline);
            }
        }

        //Create sequences of line segments that get printed together in a monotonic direction.
        //There are several constraints we impose here:
        // - Strings of incident polylines are printed in sequence. That is, if their endpoints are incident.
        //   - The endpoint of the string that is earlier in the monotonic direction will get printed first.
        //   - The start_vertex of this line will already be set to indicate where to start from.
        // - If a line overlaps with another line in the perpendicular direction, and is within max_adjacent_distance (~1 line width) in the monotonic direction, it must be printed in monotonic order.
        //   - The earlier line is marked as being in sequence with the later line.
        //   - The later line is no longer a starting point, unless there are multiple adjacent lines before it.
        //The ``starting_lines`` set indicates possible locations to start from. Each starting line represents one "sequence", which is either a set of adjacent line segments or a string of polylines.
        //The ``connections`` map indicates, starting from each starting segment, the sequence of line segments to print in order.
        //Note that for performance reasons, the ``connections`` map will sometimes link the end of one segment to the start of the next segment. This link should be ignored.
        const Point perpendicular = turn90CCW(monotonic_vector); //To project on to detect adjacent lines.

        std::unordered_set<Path*> connected_lines; //Lines that are reachable from one of the starting lines through its connections.
        std::unordered_set<Path*> starting_lines; //Starting points of a linearly connected segment.
        std::unordered_map<Path*, Path*> connections; //For each polyline, which polyline it overlaps with, closest in the projected order.

        for(auto polyline_it = polylines.begin(); polyline_it != polylines.end(); polyline_it++)
        {
            if(connections.contains(*polyline_it)) //Already connected this one through a polyline.
            {
                continue;
            }
            //First find out if this polyline is part of a string of polylines.
            std::deque<Path*> polystring = findPolylineString(*polyline_it, line_bucket_grid, monotonic_vector);

            //If we're part of a string of polylines, connect up the whole string and mark all of them as being connected.
            if(polystring.size() > 1)
            {
                starting_lines.insert(polystring[0]);
                for(size_t i = 0; i < polystring.size() - 1; ++i) //Iterate over every pair of adjacent polylines in the string (so skip the last one)!
                {
                    connections[polystring[i]] = polystring[i + 1];
                    connected_lines.insert(polystring[i + 1]);

                    //Even though we chain polylines, we still want to find lines that they overlap with.
                    //The strings of polylines may still have weird shapes which interweave with other strings of polylines or loose lines.
                    //So when a polyline string comes into contact with other lines, we still want to guarantee their order.
                    //So here we will look for which lines they come into contact with, and thus mark those as possible starting points, so that they function as a new junction.
                    const std::vector<Path*> overlapping_lines = getOverlappingLines(std::find(polylines.begin(), polylines.end(), polystring[i]), perpendicular, polylines);
                    for(Path* overlapping_line : overlapping_lines)
                    {
                        if(std::find(polystring.begin(), polystring.end(), overlapping_line) == polystring.end()) //Mark all overlapping lines not part of the string as possible starting points.
                        {
                            starting_lines.insert(overlapping_line);
                            starting_lines.insert(polystring[i + 1]); //Also be able to re-start from this point in the string.
                        }
                    }
                }
            }
            else //Not a string of polylines, but simply adjacent line segments.
            {
                if(! connected_lines.contains(*polyline_it)) //Nothing connects to this line yet.
                {
                    starting_lines.insert(*polyline_it); //This is a starting point then.
                }
                const std::vector<Path*> overlapping_lines = getOverlappingLines(polyline_it, perpendicular, polylines);
                if(overlapping_lines.size() == 1) //If we're not a string of polylines, but adjacent to only one other polyline, create a sequence of polylines.
                {
                    connections[*polyline_it] = overlapping_lines[0];
                    if(connected_lines.contains(overlapping_lines[0])) //This line was already connected to.
                    {
                        starting_lines.insert(overlapping_lines[0]); //Multiple lines connect to it, so we must be able to start there.
{'fraction_non_alphanumeric': 0.07860478982410812, 'fraction_numerical': 0.002285600715492398, 'mean_word_length': 2.5248686514886165, 'pattern_counts': {'":': 0, '<': 42, '<?xml version=': 0, '>': 86, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '94952', 'n_tokens_mistral': 5314, 'n_tokens_neox': 4977, 'n_words': 2071}