text:
#include <algorithm>

#ifdef _WIN32
    #pragma warning(push, 0)
    #include <boost/polygon/polygon.hpp>
    #pragma warning(pop)
#else
    #include <boost/polygon/polygon.hpp>
#endif

#include <cradle/geometry/angle.hpp>
#include <cradle/geometry/clipper.hpp>
#include <cradle/geometry/intersection.hpp>
#include <cradle/geometry/polygonal.hpp>

namespace cradle {

// COMMON FUNCTIONS

static vector<2,double> get_corner(box<2,double> const& box, int index)
{
    vector<2,double> corner;
    while(index >= 4)
    {
        index -= 4;
    }
    switch (index)
    {
        case 0:
            return box.corner;
        case 1:
            return box.corner + make_vector(box.size[0], 0.);
        case 2:
            return box.corner + make_vector(box.size[0], box.size[1]);
        case 3:
            return box.corner + make_vector(0., box.size[1]);
    }
    return make_vector(0.,0.);
}

// POLYGONS

polygon2 make_polygon2(std::vector<vertex2> const& vertices)
{
    polygon2 poly;
    initialize(&poly.vertices, vertices);
    return poly;
}

double get_area(polygon2 const& poly)
{
    return get_area_and_centroid(poly).first;
}

vector2d get_centroid(polygon2 const& poly)
{
    return get_area_and_centroid(poly).second;
}

std::pair<double, vector2d> get_area_and_centroid(polygon2 const& poly)
{
    double a = 0.0;
    double cx = 0.0;
    double cy = 0.0;
    for (polygon2_edge_view ev(poly); !ev.done(); ev.advance())
    {
        double cross = ev.p0()[0] * ev.p1()[1] - ev.p0()[1] * ev.p1()[0];
        a += cross;
        cx += (ev.p0()[0] + ev.p1()[0]) * cross;
        cy += (ev.p0()[1] + ev.p1()[1]) * cross;
    }
    double scale = 3.0 * a;
    return std::make_pair(std::fabs(0.5 * a),
        make_vector(cx / scale, cy / scale));
}

polygon2 scale(polygon2 const& poly, double factor)
{
    return scale(poly, make_vector(factor, factor));
}

struct point_scaling_fn
{
    vector<2,double> factor;
    vertex2 operator()(vertex2 const& src) const
    {
        return make_vector(src[0] * factor[0], src[1] * factor[1]);
    }
};

polygon2 scale(polygon2 const& poly, vector<2,double> const& factor)
{
    point_scaling_fn fn;
    fn.factor = factor;
    return map_points(poly, fn);
}

bool is_inside(polygon2 const& poly, vector<2,double> const& p)
{
    bool c = false;
    for (polygon2_edge_view ev(poly); !ev.done(); ev.advance())
    {
        if (((ev.p0()[1] <= p[1] && p[1] < ev.p1()[1]) ||
            (ev.p1()[1] <= p[1] && p[1] < ev.p0()[1]))
         && (p[0] < (ev.p1()[0] - ev.p0()[0]) * (p[1] - ev.p0()[1]) /
            (ev.p1()[1] - ev.p0()[1]) + ev.p0()[0]))
        {
            c = !c;
        }
    }
    return c;
}

bool is_inside(polygon2 const& parent_poly, polygon2 const& child_poly)
{
    for (auto const& point : child_poly.vertices)
    {
        if (!is_inside(parent_poly, point))
        {
            return false;
        }
    }
    return true;
}

bool is_ccw(polygon2 const& poly)
{
    assert(poly.vertices.size() > 2);
    vector<2,double> edge0 = poly.vertices[1] - poly.vertices[0];
    vector<2,double> edge1 = poly.vertices[2] - poly.vertices[1];
    return (edge0[0] * edge1[1]) - (edge0[1] * edge1[0]) > 0;
}

polygon2 as_polygon(box<2,double> const& box)
{
    polygon2 poly;
    vertex2* vertices = allocate(&poly.vertices, 4);
    vertices[0] = box.corner;
    vertices[1] = box.corner + make_vector(box.size[0], 0.);
    vertices[2] = box.corner + box.size;
    vertices[3] = box.corner + make_vector(0., box.size[1]);
    return poly;
}

polygon2 as_polygon(circle<double> const& circle, unsigned n_segments)
{
    polygon2 poly;
    vertex2* vertices = allocate(&poly.vertices, n_segments);
    for (unsigned i = 0; i < n_segments; ++i)
    {
        angle<double,radians> a(2 * pi * i / n_segments);
        vertices[i] =
            make_vector(cos(a), sin(a)) * circle.radius + circle.center;
    }
    return poly;
}

polygon2 as_polygon(triangle<2,double> const& tri)
{
    polygon2 poly;
    vertex2* vertices = allocate(&poly.vertices, 3);
    for (unsigned i = 0; i != 3; ++i)
        vertices[i] = tri[i];
    return poly;
}

// POLYSETS

void create_polyset(polyset* set, polygon2 const& poly)
{
    *set = polyset();
    set->polygons.push_back(poly);
}

polyset make_polyset(polygon2 const& poly)
{
    polyset p;
    create_polyset(&p, poly);
    return p;
}

void add_polygon(polyset& set, polygon2 const& poly)
{
    polyset addition;
    create_polyset(&addition, poly);
    if (set.polygons.empty())
        swap(set, addition);
    else
        do_set_operation(&set, set_operation::UNION, addition, set);
}
void add_hole(polyset& set, polygon2 const& hole)
{
    assert(!set.polygons.empty());
    polyset subtraction;
    create_polyset(&subtraction, hole);
    do_set_operation(&set, set_operation::DIFFERENCE, set, subtraction);
}

polyset remove_polyset_holes(
    polyset const& original_shape)
{
    polyset shape = original_shape;

    while (!shape.holes.empty())
    {
        do_set_operation(
            &shape,
            set_operation::UNION,
            shape,
            make_polyset(shape.holes.front()));
    }

    return shape;
}

polyset scale(polyset const& set, double factor)
{
    return scale(set, make_vector(factor, factor));
}
polyset scale(polyset const& set, cradle::vector<2,double> const& factor)
{
    point_scaling_fn fn;
    fn.factor = factor;
    return map_points(set, fn);
}

std::pair<double, vector2d> static
get_area_and_centroid(polyset const& set)
{
    double area = 0;
    auto centroid = make_vector(0., 0.);
    for (auto const& i : set.polygons)
    {
        auto pair = get_area_and_centroid(i);
        area += pair.first;
        centroid += pair.second * pair.first;
    }
    for (auto const& i : set.holes)
    {
        auto pair = get_area_and_centroid(i);
        area -= get_area(i);
        centroid -= pair.second * pair.first;
    }
    centroid /= area;
    return std::make_pair(area, centroid);
}

double get_area(polyset const& set)
{
    return get_area_and_centroid(set).first;
}

vector2d get_centroid(polyset const& set)
{
    auto pair = get_area_and_centroid(set);
    if (pair.first == 0)
        throw exception("centroid requested for empty polyset");
    return pair.second;
}

bool is_inside(polyset const& set, vector<2,double> const& p)
{
    int inside_count = 0;
    for (auto const& i : set.polygons)
    {
        if (is_inside(i, p))
            ++inside_count;
    }
    for (auto const& i : set.holes)
    {
        if (is_inside(i, p))
            --inside_count;
    }
    return inside_count > 0;
}

typedef line_segment<2, double> line_segment2;

double distance_to_polyset(vector<2,double> const& p, polyset const& set)
{
    double d2p = 1.0e10;
    size_t polygon_count = set.polygons.size();
    for (size_t k = 0; k < polygon_count; ++k)
    {
        size_t vertex_count = set.polygons[k].vertices.n_elements;
        auto v0 = set.polygons[k].vertices.elements[vertex_count - 1];
        for (size_t i = 0; i < vertex_count; ++i)
        {
            // Get segment end point
            auto v1 = set.polygons[k].vertices.elements[i];
            line_segment2 segment(v0, v1);
            auto len = length(segment);

            // Ensure the line segment has finite length
            if (len >= 1.0e-8)
            {
                // Discretize line segment and determine distance
                double spacing = 0.25;
                int split_count = std::min(std::max(int(std::ceil(len / spacing)), 2), 30);
                for (int j = 0; j < split_count; ++j)
                {
                    double dist = distance(segment, p);

                    if (dist < std::fabs(d2p))
                    {
                        bool pip = point_in_polygon(p, set.polygons[k]);
                        d2p = pip ? -dist : dist;
                    }
                }
            }

            // Increment segment start point
            v0 = v1;
        }
    }

    // Handle Holes too
    size_t hole_count = set.holes.size();
    for (size_t k = 0; k < hole_count; ++k)
    {
        size_t vertex_count = set.holes[k].vertices.n_elements;
        auto v0 = set.holes[k].vertices.elements[vertex_count - 1];
        for (size_t i = 0; i < vertex_count; ++i)
        {
            // Get segment end point
            auto v1 = set.holes[k].vertices.elements[i];
            line_segment2 segment(v0, v1);
            auto len = length(segment);

            // Ensure the line segment has finite length
            if (len >= 1.0e-8)
            {
                // Discretize line segment and determine distance
                double spacing = 0.25;
                int split_count = std::min(std::max(int(std::ceil(len / spacing)), 2), 30);
                for (int j = 0; j < split_count; ++j)
                {
                    double dist = distance(segment, p);

                    if (dist < std::fabs(d2p))
                    {
                        bool pip = point_in_polygon(p, set.holes[k]);
                        d2p = pip ? dist : -dist;
                    }
                }
            }

            // Increment segment start point
            v0 = v1;
        }
    }

    return d2p;
}

namespace {

    typedef boost::polygon::point_data<int> boost_point;

    typedef boost::polygon::polygon_data<int> boost_polygon;

    typedef boost::polygon::polygon_with_holes_data<int>
        boost_polygon_with_holes;

    typedef boost::polygon::polygon_set_data<int> boost_polygon_set;

    void to_boost_polygon(boost_polygon& bp, polygon2 const& poly)
    {
        size_t n_points = poly.vertices.size();
        bp.coords_.resize(n_points);
        for (size_t i = 0; i != n_points; ++i)
        {
            vector<2,double> const& p = poly.vertices[i];
            bp.coords_[i] = boost_polygon::point_type(
                int(p[0] / clipper_integer_precision),
                int(p[1] / clipper_integer_precision));
        }
    }

    void to_boost_polygon(boost_polygon_set& boost_set,
        polyset const& cradle_set)
    {
        using namespace boost::polygon::operators;
        boost_set.clear();
        for (auto const& i : cradle_set.polygons)
        {
            boost_polygon poly;
            to_boost_polygon(poly, i);
            boost_set ^= poly;
        }
        for (auto const& i : cradle_set.holes)
        {
            boost_polygon poly;
            to_boost_polygon(poly, i);
            boost_set ^= poly;
        }
    }

    vector<2,double>
    from_boost_point(boost_point const& p)
    {
        return make_vector<double>(
            double(p.x()) * clipper_integer_precision,
            double(p.y()) * clipper_integer_precision);
    }

    void from_boost_polygon(polygon2& poly, boost_polygon const& bp)
    {
        size_t n_points = bp.size();
        if (n_points != 0)
        {
            // The first and last vertices are the same, so skip the last.
            --n_points;
            vertex2* vertices = allocate(&poly.vertices, n_points);
            for (size_t i = 0; i != n_points; ++i)
                vertices[i] = from_boost_point(bp.coords_[i]);
        }
        else
            clear(&poly.vertices);
    }

    void from_boost_polygon(polyset& cradle_set,
        boost_polygon_set const& boost_set)
    {
        cradle_set = polyset();
        std::vector<boost_polygon_with_holes> boost_polys;
        boost_set.get(boost_polys);
        for (auto const& bp : boost_polys)
        {
            polygon2 poly;
            from_boost_polygon(poly, bp.self_);
            cradle_set.polygons.push_back(poly);
            for (auto const& bh : bp.holes_)
            {
                polygon2 hole;
                from_boost_polygon(hole, bh);
                cradle_set.holes.push_back(hole);
            }
        }
    }

    void from_boost_polygon(std::vector<polygon2>& polys,
        boost_polygon_set const& set)
    {
        std::vector<boost_polygon> boost_polys;
        set.get(boost_polys);
        size_t n_polys = boost_polys.size();
        polys.resize(n_polys);
        for (size_t i = 0; i != n_polys; ++i)
        {
            boost_polygon const& bp = boost_polys[i];
            polygon2& poly = polys[i];
            from_boost_polygon(poly, bp);
        }
    }

} // anonymous namespace

std::vector<polygon2> as_polygon_list(polyset const& set)
{
    boost_polygon_set boost_set;
    to_boost_polygon(boost_set, set);
    std::vector<polygon2> polygons;
    from_boost_polygon(polygons, boost_set);
    return polygons;
}

bool almost_equal(polyset const& set1, polyset const& set2, double tolerance)
{
    polyset xor_;
    do_set_operation(&xor_, set_operation::XOR, set1, set2);
    return almost_equal(get_area(xor_), 0., tolerance);
}

bool almost_equal(polyset const& set1, polyset const& set2)
{
    polyset xor_;
    do_set_operation(&xor_, set_operation::XOR, set1, set2);
    return almost_equal(get_area(xor_), 0.);
}

void do_set_operation(
    polyset* result,
    set_operation op,
    polyset const& set1,
    polyset const& set2)
{
    ClipperLib::Clipper clipper;
    clipper.AddPolygons(to_clipper(set1), ClipperLib::ptSubject);
    clipper.AddPolygons(to_clipper(set2), ClipperLib::ptClip);
    ClipperLib::ClipType clipper_op;
    switch (op)
    {
     case set_operation::UNION:
        clipper_op = ClipperLib::ctUnion;
        break;
     case set_operation::INTERSECTION:
        clipper_op = ClipperLib::ctIntersection;
        break;
     case set_operation::DIFFERENCE:
        clipper_op = ClipperLib::ctDifference;
        break;
     case set_operation::XOR:
        clipper_op = ClipperLib::ctXor;
        break;
     default:
         throw exception("set operation undefined");
    }
    ClipperLib::Polygons solution;
    clipper.Execute(clipper_op, solution);
    from_clipper(result, solution);
}

api(fun)
polyset
polyset_combination(set_operation op, std::vector<polyset> const& polysets)
{
    if (polysets.empty())
    {
        return polyset();
    }
    else if (polysets.size() == 1)
    {
        return polysets[0];
    }
    polyset tmp[2];
    int output_index = 0;
    polyset const* input = &polysets.front();
    auto i = polysets.begin();
    ++i;
    for (; i != polysets.end(); ++i)
    {
        output_index = 1 - output_index;
        auto output = &tmp[output_index];
        do_set_operation(output, op, *input, *i);
        input = output;
    }
    return tmp[output_index];
}

// Triangulate a convex Boost polygon.
// Note that this does NOT clear the list of triangles.
// It simply pushes more triangles onto the back of it.
static void
triangulate_boost_polygon(
    std::vector<triangle<2,double> >& tris, boost_polygon const& poly)
{
    size_t n_points = poly.size();
    if (n_points > 0)
    {
        // The first and last vertices are the same, so skip the last.
        --n_points;
        for (size_t i = 2; i < n_points; ++i)
        {
            triangle<2,double> tri;
            tri[0] = from_boost_point(poly.coords_[0]);
            tri[1] = from_boost_point(poly.coords_[i - 1]);
            tri[2] = from_boost_point(poly.coords_[i]);
            tris.push_back(tri);
        }
    }
}

std::vector<triangle<2,double> >
triangulate_polyset(polyset const& set)
{
    boost_polygon_set boost_set;
    to_boost_polygon(boost_set, set);
    std::vector<boost_polygon> trapezoids;
    boost_set.get_trapezoids(trapezoids);
    size_t n_trapezoids = trapezoids.size();
    std::vector<triangle<2,double> > tris;
    tris.reserve(n_trapezoids * 2);
    for (size_t i = 0; i != n_trapezoids; ++i)
        triangulate_boost_polygon(tris, trapezoids[i]);
    return tris;
}

void
expand(polyset* dst, polyset const& src, double amount)
{
    using namespace boost::polygon::operators;
    auto clipper_in = to_clipper(src);
    ClipperLib::Polygons clipper_out;
    OffsetPaths(clipper_in, clipper_out, amount / clipper_integer_precision,
        ClipperLib::jtRound, ClipperLib::etClosed);
    from_clipper(dst, clipper_out);
}

polyset polyset_expansion(polyset const& src, double amount)
{
    polyset result;
    expand(&result, src, amount);
    return result;
}

void create_polyset_from_polygons(polyset* set,
    std::vector<polygon2> const& polygons)
{
    using namespace boost::polygon::operators;
    boost_polygon_set boost_set;
    for (std::vector<polygon2>::const_iterator
        i = polygons.begin(); i != polygons.end(); ++i)
    {
        boost_polygon bp;
        to_boost_polygon(bp, *i);
        boost_set += bp;
    }
    from_boost_polygon(*set, boost_set);
}

// STRUCTURES

bool is_inside(structure_geometry_slice const& s, double p)
{
    return ((p >= s.position - (s.thickness / 2.)) &&
        (p < s.position + (s.thickness / 2.)));
}

void static
reset_structure_to_slice_list(
    structure_geometry* structure,
    slice_description_list const& slices)
{
    structure->slices.clear();
    structure->master_slice_list.clear();
    structure->master_slice_list = slices;
}

structure_geometry static
remove_empty_slices(structure_geometry const& structure)
{
    structure_geometry result;
    result.master_slice_list = structure.master_slice_list;
    for (auto const& slice : structure.slices)
    {
        if (!is_empty(slice.second))
        {
            result.slices.insert(slice);
        }
    }
    return result;
}

polyset
get_slice(structure_geometry const& structure, double position)
{
    auto slice = get_structure_slice(structure, position);
    if (slice)
    {
        return get(slice).region;
    }

    return polyset();
}

structure_geometry_slice
find_slice_at_exact_position(
    structure_polyset_list const& slices,
    double position,
    double thickness)
{
    auto s = slices.find(position);
    if (s != slices.end())
    {
        return structure_geometry_slice(position, thickness, s->second);
    }
    return structure_geometry_slice(position, thickness, polyset());
}

optional<structure_geometry_slice>
get_structure_slice(structure_geometry const& structure, double position)
{
    auto const& masters = structure.master_slice_list;
    auto const& slices = structure.slices;
    auto p = position;

    if (masters.size() == 0 ||
        p < masters[0].position - 0.5 * masters[0].thickness ||
        p > masters.back().position + 0.5 * masters.back().thickness)
    {
        return none;
    }

    for (size_t i = 1; i < masters.size(); ++i)
    {
        if (p < masters[i].position)
        {
            if (p - masters[i - 1].position < masters[i].position - p)
            {
                return
                    some(
                        find_slice_at_exact_position(
                            slices,
                            masters[i - 1].position,
                            masters[i - 1].thickness));
            }
            else
            {
                return
                    some(
                        find_slice_at_exact_position(
                            slices,
                            masters[i].position,
                            masters[i].thickness));
            }
        }
    }
    // Valid case when p is past the last slice position, but within its thickness
    return
        some(
            find_slice_at_exact_position(
                slices,
                masters.rbegin()->position,
                masters.rbegin()->thickness));
}

std::vector<structure_geometry_slice>
get_structure_slices(structure_geometry const& structure, double p_low, double p_high)
{
    auto const& masters = structure.master_slice_list;
    auto const& slices = structure.slices;

    std::vector<structure_geometry_slice> output;

    if (masters.size() == 0 ||
        p_low > masters.back().position + 0.5 * masters.back().thickness ||
        p_high < masters[0].position - 0.5 * masters[0].thickness)
    {
        return output;
    }

    // Find the start and end slice indices
    // Note: the initial value set below is critical to this functioning properly
    size_t i_start = masters.size();

    for (size_t i = 1; i < masters.size(); ++i)
    {
        if (p_low < masters[i].position)
        {
            if (p_low - masters[i - 1].position < masters[i].position - p_low)
            {
                i_start = i - 1;
            }
            else
            {
                i_start = i;
            }
            output.push_back(
                find_slice_at_exact_position(
                    slices,
                    masters[i_start].position,
                    masters[i_start].thickness));
            break;
        }
    }

    for (size_t i = i_start + 1; i < masters.size(); ++i)
    {
        if (p_high < masters[i].position)
        {
            if (p_high - masters[i - 1].position < masters[i].position - p_high)
            {
                // Last slice is already in the list, just return now
                return output;
            }
            else
            {
                // Add the last slice and then return
                output.push_back(
                    find_slice_at_exact_position(
                        slices,
                        masters[i].position,
                        masters[i].thickness));
                return output;
            }
        }

        // Slice is within limits, add it
        output.push_back(
            find_slice_at_exact_position(
                slices,
                masters[i].position,
                masters[i].thickness));
    }

    // All slices have been added (but never reached p_high position), just return
    return output;
}

void static
fold_in(double& volume, vector3d& centroid,
    std::pair<double,vector2d> const& area_and_centroid,
    double z, double thickness)
{
    volume += area_and_centroid.first * thickness;
    centroid += unslice(area_and_centroid.second, 2, z) *
        area_and_centroid.first * thickness;
}

void static
fold_in_above(double& volume, vector3d& centroid,
    std::pair<double,vector2d> const& area_and_centroid,
    double z, double thickness)
{
    fold_in(volume, centroid, area_and_centroid, z + thickness / 2, thickness);
}

void static
fold_in_below(double& volume, vector3d& centroid,
    std::pair<double,vector2d> const& area_and_centroid,
    double z, double thickness)
{
    fold_in(volume, centroid, area_and_centroid, z - thickness / 2, thickness);
}

std::pair<double,vector3d> static
get_volume_and_centroid(structure_geometry const& structure)
{
    auto volume = 0.;
    auto centroid = make_vector(0., 0., 0.);

    auto const& masters = structure.master_slice_list;
    auto const& slices = structure.slices;

    auto begin_m = masters.begin();
    auto end_m = masters.end();
    auto i = begin_m;
    auto end_slice = slices.end();

    while (i != end_m)
    {
        auto slice = slices.find(i->position);
        if (slice != end_slice && get_area(slice->second) != 0.)
        {
            break;
        }
        ++i;
    }

    for (; i != end_m; ++i)
    {
        auto slice = slices.find(i->position);
        if (slice == end_slice) { continue; }

        auto i_info = get_area_and_centroid(slice->second);

        // Add lower half of slice thickness
        auto temp = i;
        if (i == begin_m)
        {
            fold_in_below(volume, centroid, i_info, i->position, i->thickness * 0.5);
        }
        else
        {
            --temp;
            fold_in_below(
                volume, centroid,
                i_info,
                i->position,
                0.5 * (i->position - temp->position));
        }

        // Add upper half of slice thickness
        temp = i;
        ++temp;
        if (temp == end_m)
        {
            fold_in_above(volume, centroid, i_info, i->position, i->thickness * 0.5);
        }
        else
        {
            fold_in_above(
                volume, centroid,
                i_info,
                i->position,
                0.5 * (temp->position - i->position));
        }
    }

    if (volume != 0.)
    {
        centroid /= volume;
    }

    return std::make_pair(volume, centroid);
}

double get_volume(structure_geometry const& structure)
{
    return get_volume_and_centroid(structure).first;
}

vector3d get_centroid(
    structure_geometry const& structure)
{
    auto pair = get_volume_and_centroid(structure);
    if (pair.first == 0)
        throw exception("centroid requested for empty structure");
    return pair.second;
}

bool is_inside(structure_geometry const& structure, vector<3,double> const& p)
{
    auto s = get_slice(structure, p[2]);
    return is_inside(s, slice(p, 2));
}

slice_description_list
get_slice_descriptions(structure_geometry const& s)
{
    return s.master_slice_list;
}

bool
almost_equal(
    structure_geometry const& volume1,
    structure_geometry const& volume2,
    double tolerance)
{
    if (volume1.master_slice_list.size() != volume2.master_slice_list.size())
        return false;

    auto i1 = volume1.master_slice_list.begin();
    auto end1 = volume1.master_slice_list.end();
    auto i2 = volume2.master_slice_list.begin();

    auto const& slices1 = volume1.slices;
    auto const& slices2 = volume2.slices;

    for (; i1 != end1; ++i1, ++i2)
    {
        if (!almost_equal(i1->position, i2->position, tolerance) ||
            !almost_equal(i1->thickness, i2->thickness, tolerance))
        {
            return false;
        }
        auto r1 = find_slice_at_exact_position(slices1, i1->position, i1->thickness);
        auto r2 = find_slice_at_exact_position(slices2, i2->position, i2->thickness);
        if (!almost_equal(r1.region, r2.region, tolerance))
        {
            return false;
        }
    }

    return true;
}

bool almost_equal(structure_geometry const& a, structure_geometry const& b)
{
    return almost_equal(a, b, default_equality_tolerance<double>());
}

void do_set_operation(
    structure_geometry* result,
    set_operation op,
    structure_geometry const& structure1,
    structure_geometry const& structure2)
{
    if (structure1.master_slice_list != structure2.master_slice_list)
    {
        throw exception("structure set_operation requires matching master lists");
    }

    auto const& master_slices = structure1.master_slice_list;

    result->master_slice_list = master_slices;
    result->slices.clear();
    for (auto const& i : master_slices)
    {
        auto s1 =
            find_slice_at_exact_position(structure1.slices, i.position, i.thickness);
        auto s2 =
            find_slice_at_exact_position(structure2.slices, i.position, i.thickness);

        if (!is_empty(s1.region) || !is_empty(s2.region))
        {
            polyset region;
            do_set_operation(&region, op, s1.region, s2.region);
            if (!is_empty(region))
            {
                result->slices[i.position] = region;
            }
        }
    }
}

structure_geometry
structure_combination(
    set_operation op,
    std::vector<structure_geometry> const& structures)
{
    if (structures.size() < 2)
    {
        throw exception("structure_combination requires at least two structures");
    }
    structure_geometry tmp[2];
    int output_index = 0;
    structure_geometry const* input = &structures.front();
    auto i = structures.begin();
    ++i;
    for (; i != structures.end(); ++i)
    {
        output_index = 1 - output_index;
        auto output = &tmp[output_index];
        do_set_operation(output, op, *input, *i);
        input = output;
    }
    return tmp[output_index];
}

std::vector<double>
slice_position_list(structure_geometry const& structure)
{
    return map(
        [](slice_description const& slice)
        {
            return slice.position;
        },
        structure.master_slice_list);
}

void expand_in_2d(
    structure_geometry* result,
    structure_geometry const& structure,
    double amount)
{
    auto slice_descriptions = get_slice_descriptions(structure);
    reset_structure_to_slice_list(result, slice_descriptions);
    for (auto const& slice : structure.slices)
    {
        polyset p;
        expand(&p, slice.second, amount);
        result->slices[slice.first] = p;
    }
}

box<2,double>
bounding_box(polygon2 const& poly)
{
    optional<box<2,double> > box;
    compute_bounding_box(box, poly);
    // If there is no box, then the polygon is empty, so just return any box.
    return box ? box.get() :
        make_box(make_vector(0., 0.), make_vector(0., 0.));
}
void compute_bounding_box(
    optional<box<2,double> >& box,
    polygon2 const& poly)
{
    vertex2_array::const_iterator
        i = poly.vertices.begin(),
        end = poly.vertices.end();
    if (i == end)
        return;

    vector<2,double> min, max;
    if (box)
    {
        min = get_low_corner(box.get());
        max = get_high_corner(box.get());
    }
    else
    {
        min = *i;
        max = *i;
        ++i;
    }

    for (; i != end; ++i)
    {
        for (unsigned j = 0; j != 2; ++j)
        {
            if ((*i)[j] < min[j])
                min[j] = (*i)[j];
            if ((*i)[j] > max[j])
                max[j] = (*i)[j];
        }
    }

    box = cradle::box<2,double>(min, max - min);
}

// for a polyset
box<2,double> bounding_box(polyset const& region)
{
    optional<box<2,double> > box;
    compute_bounding_box(box, region);
    // If there is no box, then the polyset is empty, so just return any box.
    return box ? box.get() :
        make_box(make_vector(0., 0.), make_vector(0., 0.));
}
void compute_bounding_box(optional<box<2,double> >& box, polyset const& region)
{
    for (auto const& i : region.polygons)
        compute_bounding_box(box, i);
}

// for a structure_geometry
box<3,double> bounding_box(structure_geometry const& structure)
{
    optional<box<3,double> > box;
    compute_bounding_box(box, structure);
    // If there is no box, then the structure is empty, so just return any box.
    return box ? box.get() :
        make_box(make_vector(0., 0., 0.), make_vector(0., 0., 0.));
}
void compute_bounding_box(optional<box<3,double> >& box,
    structure_geometry const& structure)
{
    optional<cradle::box<2,double> > xy_box;
    if (box)
    {
        xy_box = slice(box.get(), 2);
    }

    double zmin = 1.0e100;
    double zmax = -1.0e100;
    auto master_slices = get_slice_descriptions(structure);
    for (auto const& m_slice : master_slices)
    {
        auto slice =
            find_slice_at_exact_position(
                structure.slices,
                m_slice.position,
                m_slice.thickness);
        if (!is_empty(slice.region))
        {
            compute_bounding_box(xy_box, slice.region);

            if (slice.position - 0.5 * slice.thickness < zmin)
            {
                zmin = slice.position - 0.5 * slice.thickness;
            }
            if (slice.position + 0.5 * slice.thickness > zmax)
            {
                zmax = slice.position + 0.5 * slice.thickness;
            }
        }
    }

    if (!structure.slices.empty() && xy_box)
    {
        //double z_min = structure.slices.begin()->position -
        //    structure.slices.begin()->thickness / 2;
        //auto last = structure.slices.end();
        //--last;
        //double z_max = last->position + last->thickness / 2;

        vector<2,double> const& xy_corner = xy_box.get().corner;
        vector<2,double> const& xy_size = xy_box.get().size;

        box = cradle::box<3,double>(
            make_vector(xy_corner[0], xy_corner[1], zmin),
            make_vector(xy_size[0], xy_size[1], zmax - zmin));
    }
}

bool
overlapping(
    box3d const& box,
    structure_geometry const& sg,
    unsigned structure_axis,
    optional<box3d> const& sg_bounds)
{
    if (sg_bounds)
    {
        if (!overlapping(box, get(sg_bounds)))
        {
            return false;
        }
    }

    // Get slices that the box contains
    auto slices =
        get_structure_slices(
            sg,
            box.corner[structure_axis],
            get_high_corner(box)[structure_axis]);

    // Check for overlap on each slice
    for (auto const& s : slices)
    {
        if (s.region.polygons.size() == 0)
        {
            continue;
        }

        auto const box2 = slice(box, structure_axis);

        // Check center of voxel as this may be a fast "short-circuit" for many cases
        if (point_in_polyset(get_center(box2), s.region))
        {
            return true;
        }
        else
        {
            // Check all points in the polyset
            // Note this isn't 100% accurate because holes can actually make a polygon
            // vertex outside and we don't catch that case
            for (auto const& p : s.region.polygons)
            {
                for (auto const& v : p.vertices)
                {
                    if (contains(box2, v))
                    {
                        return true;
                    }
                }
            }
        }
    }

    return false;
}

bool almost_equal(polygon2 const& a, polygon2 const& b, double tolerance)
{
    polyset region_a, region_b, xor_region;
    create_polyset(&region_a, a);
    create_polyset(&region_b, b);
    do_set_operation(&xor_region, set_operation::XOR, region_a, region_b);
    return almost_equal(get_area(xor_region), 0., tolerance);
}
bool almost_equal(polygon2 const& a, polygon2 const& b)
{
    polyset region_a, region_b, xor_region;
    create_polyset(&region_a, a);
    create_polyset(&region_b, b);
    do_set_operation(&xor_region, set_operation::XOR, region_a, region_b);
    return almost_equal(get_area(xor_region), 0.);
}

}

max_stars_repo_name: dotdecimal/open-cradle

max_issues_repo_name: dotdecimal/open-cradle

max_forks_repo_name: dotdecimal/open-cradle


text:
/*
 File:      logcat-colorize.cpp

 Purpose:   Colorizes Android's logcat output in command-line windows
            Works on linux/mac terminals only.

 Author:    BRAGA, Bruno <bruno.braga@gmail.com>
 Author:    CARLON, Luca <carlon.luca@gmail.com>

 Copyright:
            Licensed under the Apache License, Version 2.0 (the "License");
            you may not use this file except in compliance with the License.
            You may obtain a copy of the License at

            http://www.apache.org/licenses/LICENSE-2.0

            Unless required by applicable law or agreed to in writing, software
            distributed under the License is distributed on an "AS IS" BASIS,
            WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
            implied. See the License for the specific language governing
            permissions and limitations under the License.

 Notes:
            Bugs, issues and requests are welcome at:
            https://github.com/carlonluca/logcat-colorize/issues

 Dependencies:

            libboost-regex-dev
            libboost-program-options-dev

 Compiling:
            See Makefile.
*/

#include <unistd.h>
#include <string>
#include <iostream>
#include <stdio.h>
#include <boost/regex.hpp>
#include <boost/program_options.hpp>
#include <boost/algorithm/string.hpp>
#include <boost/format.hpp>
using namespace std;

const string NAME = "logcat-colorize";
const string VERSION = "0.7.0";

const int SUCCESS = 0;
const int ERROR_UNKNOWN = 1;

const string HELP =
    NAME + " v" + VERSION + "\n"
    "\n"
    "A simple script to colorize Android debugger's logcat output.\n"
    "To use this, you MUST pipe from adb output. See examples below.\n"
    "Valid ONLY for Tag, Process, Brief, Time and ThreadTime formats.\n"
    "Other formats are simply not parsed here.\n"
    "\n"
    "Usage: adb logcat [options] | " + NAME + " [options] \n"
    "\n"
    "Options:\n"
    "   -i, --ignore        does not output non-matching data\n"
    "                       (by default, those are printed out without colorizing)\n"
    "   -h, --help          prints this help information\n"
    "   -s, --spotlight     highlight pattern in the output, value as REGEXP\n"
    "                       (i.e, -s '\bWORD\b'\n"
    "\n"
    "Examples:\n"
    "    Simplest usage:\n"
    "    adb logcat | " + NAME + "\n"
    "\n"
    "    Using specific device, with time details, and filtering:\n"
    "    adb -s emulator-5556 logcat -v time System.err:V *:S | " + NAME + "\n"
    "\n"
    "    Piping to grep for regex filtering (much better than adb filter):\n"
    "    adb logcat -v time | egrep -i '(sensor|wifi)' | " + NAME + "\n"
    "\n"
    "Author: BRAGA, Bruno <bruno.braga@gmail.com>\n"
    "Author: CARLON, Luca <carlon.luca@gmail.com>\n"
    "\n"
    "    Comments or bugs are welcome at:\n"
    "    https://github.com/carlonluca/logcat-colorize/issues\n";

class Color {

public:
    static const string fblack;
    static const string fred;
    static const string fgreen;
    static const string fyellow;
    static const string fblue;
    static const string fpurple;
    static const string fcyan;
    static const string fwhite;
    static const string fgrey;
    static const string bblack;
    static const string bred;
    static const string bgreen;
    static const string byellow;
    static const string bblue;
    static const string bpurple;
    static const string bcyan;
    static const string bwhite;
    static const string bold;
    static const string underline;
    static const string reset;
};

const string Color::fblack     = "\033[0;30m";
const string Color::fred       = "\033[0;31m";
const string Color::fgreen     = "\033[0;32m";
const string Color::fyellow    = "\033[0;33m";
const string Color::fblue      = "\033[0;34m";
const string Color::fpurple    = "\033[0;35m";
const string Color::fcyan      = "\033[0;36m";
const string Color::fwhite     = "\033[0;37m";
const string Color::fgrey      = "\033[1;30m";
const string Color::bblack     = "\033[40m";
const string Color::bred       = "\033[41m";
const string Color::bgreen     = "\033[42m";
const string Color::byellow    = "\033[43m";
const string Color::bblue      = "\033[44m";
const string Color::bpurple    = "\033[45m";
const string Color::bcyan      = "\033[46m";
const string Color::bwhite     = "\033[47m";
const string Color::bold       = "\033[1m";
const string Color::underline  = "\033[4m";
const string Color::reset      = "\033[0m";

struct Logcat {
    string date;
    string level;
    string tag;
    string process;
    string message;
    string thread;
};

class Format {

protected:
    Logcat l;
    boost::regex pattern;
    boost::regex spotlight_pattern;
    string spotlight_color;
    boost::smatch match(const string& raw) {
        string::const_iterator start;
        start = raw.begin();
        boost::smatch results;
        boost::match_flag_type flags = boost::match_default;
        boost::regex_search(start, raw.end(), results, this->pattern, flags);
        return results;
    }

public:
    void setSpotlight(const string& spotlight) {
        this->spotlight_pattern = (boost::format("(%1%)") % spotlight).str();
    }
    const int type = -1;
    Format(const string& pattern) {
        this->l = Logcat { /*date   */ "",
                           /*level  */ "",
                           /*tag    */ "",
                           /*process*/ "",
                           /*message*/ "",
                           /*thread */ "" };
        this->pattern = pattern;
        this->spotlight_color = "\033[0;41m$1\033[0;0m";
    }
    virtual ~Format() {};
    static const int BRIEF;
    static const int PROCESS;
    static const int TAG;
    static const int RAW;
    static const int TIME;
    static const int THREADTIME;
    static const int LONG;

    virtual void parse(const string raw) = 0;
    virtual bool valid() { return false; }
    void print() {

        string out = "";

        // date
        if (this->l.date != "")
            out += Color::fpurple + " " + this->l.date + " " + Color::reset;

        // level
        if (this->l.level != "") {
            if (this->l.level == "V") out += Color::fwhite + Color::bcyan   + Color::bold + " " + this->l.level + " " + Color::reset;
            if (this->l.level == "D") out += Color::fwhite + Color::bblue   + Color::bold + " " + this->l.level + " " + Color::reset;
            if (this->l.level == "I") out += Color::fwhite + Color::bgreen  + Color::bold + " " + this->l.level + " " + Color::reset;
            if (this->l.level == "W") out += Color::fwhite + Color::byellow + Color::bold + " " + this->l.level + " " + Color::reset;
            if (this->l.level == "E") out += Color::fwhite + Color::bred    + Color::bold + " " + this->l.level + " " + Color::reset;
            if (this->l.level == "F") out += Color::fwhite + Color::bred    + Color::bold + " " + this->l.level + " " + Color::reset;
        }

        // process/thread
        if (this->l.process != "") {
            out += " " + Color::fcyan + Color::bblack + "[" + this->l.process + (this->l.thread != "" ? "/" + this->l.thread : "") + "]" + Color::reset;
        }

        // tag
        if (this->l.tag != "")
            out += " " + Color::fwhite + this->l.tag + Color::reset;

        // log message
        string message;
        if (!spotlight_pattern.empty()) {
            message = boost::regex_replace(this->l.message,spotlight_pattern,spotlight_color);
        } else {
            message = this->l.message;
        }

        if (this->l.message != "") {
            if (this->l.level == "V") out += Color::fblack + " " + message;
            if (this->l.level == "D") out += Color::fblue + " " + message;
            if (this->l.level == "I") out += Color::fgreen + " " + message;
            if (this->l.level == "W") out += Color::fyellow + " " + message;
            if (this->l.level == "E") out += Color::fred + " " + message;
            if (this->l.level == "F") out += Color::fred + " " + message;
        }
        out +=  Color::reset;
        cout << out << endl;
    }
};

const int Format::BRIEF      = 0;
const int Format::PROCESS    = 1;
const int Format::TAG        = 2;
const int Format::RAW        = 3;
const int Format::TIME       = 4;
const int Format::THREADTIME = 5;
const int Format::LONG       = 6;

class Tag : public Format {

public:
    const int type = Format::TAG;
    Tag() : Format("^([VDIWEF])/(.*?): (.*)$") {}
    ~Tag() {}
    virtual void parse(const string raw) {
        boost::smatch matches = this->match(raw);
        if (matches.size() >= 3) {
            this->l.date = "";
            this->l.level = matches[1];
            this->l.message = matches[3];
            this->l.process = "";
            this->l.tag = matches[2];
            this->l.thread = "";
        }
    }
    virtual bool valid() {
        return this->l.level != "";
    }
};

class Process : public Format {

public:
    const int type = Format::PROCESS;
    Process() : Format("^([VDIWEF])\\(([ 0-9]{1,})\\) (.*) \\(((.*?))\\)$") {}
    ~Process() {}
    virtual void parse(const string raw) {
        boost::smatch matches = this->match(raw);
        if (matches.size() >= 4) {
            this->l.date = "";
            this->l.level = matches[1];
            this->l.message = matches[3];
            this->l.process = matches[2];
            this->l.tag = matches[4];
            this->l.thread = "";
        }
    }
    virtual bool valid() {
        return this->l.level != "" && this->l.process != "";
    }
};

class Brief : public Format {

public:
    const int type = Format::BRIEF;
    Brief() : Format("^([VDIWEF])/(.*?)\\(([ 0-9]{1,})\\): (.*)$") {}
    ~Brief() {}
    virtual void parse(const string raw) {
        boost::smatch matches = this->match(raw);
        if (matches.size() >= 5) {
            this->l.date = "";
            this->l.level = matches[1];
            this->l.message = matches[4];
            this->l.process = matches[3];
            this->l.tag = matches[2];
            this->l.thread = "";
        }
    }
    virtual bool valid() {
        return this->l.level != "" && this->l.process != "";
    }
};

class Time : public Format {

public:
    const int type = Format::TIME;
    Time() : Format("^([0-9]{2}-[0-9]{2} [0-9]{2}:[0-9]{2}:[0-9]{2}.[0-9]{3}):? ([VDIWEF])/(.*?)\\(([ 0-9]{1,})\\): (.*)$") {}
    ~Time() {}
    virtual void parse(string raw) {
        boost::smatch matches = this->match(raw);
        if (matches.size() >= 6) {
            this->l.date = matches[1];
            this->l.level = matches[2];
            this->l.message = matches[5];
            this->l.process = matches[4];
            this->l.tag = matches[3];
            this->l.thread = "";
        }
    }
    virtual bool valid() {
        return this->l.date != "" && this->l.level != "" && this->l.process != "";
    }
};

class ThreadTime : public Format {

public:
    const int type = Format::THREADTIME;
    ThreadTime() : Format("^([0-9]{2}-[0-9]{2} [0-9]{2}:[0-9]{2}:[0-9]{2}.[0-9]{3})[[:space:]]*([0-9]{1,})[[:space:]]*([0-9]{1,}) ([VDIWEF]) (.*?): (.*)$") {}
    ~ThreadTime() {}
    virtual void parse(string raw) {
        boost::smatch matches = this->match(raw);
        if (matches.size() >= 7) {
            this->l.date = matches[1];
            this->l.level = matches[4];
            this->l.message = matches[6];
            this->l.process = matches[2];
            this->l.tag = matches[5];
            this->l.thread = matches[3];
        }
    }
    virtual bool valid() {
        return this->l.date != "" && this->l.level != "" && this->l.process != "" && this->l.thread != "";
    }
};

Format* getFormat(const string raw) {

    //
    // At this point we don't know yet which format is being used, so guess it
    // (from the more complex first)
    //
    Format * out = NULL;
    out = new ThreadTime();
    out->parse(raw);
    if (!out->valid()) {
        out = NULL;
        out = new Time();
        out->parse(raw);
        if (!out->valid()) {
            out = NULL;
            out = new Brief();
            out->parse(raw);
            if (!out->valid()) {
                out = NULL;
                out = new Process();
                out->parse(raw);
                if (!out->valid()) {
                    out = NULL;
                    out = new Tag();
                    out->parse(raw);
                    if (!out->valid()) {
                        out = NULL;
                    }
                }
            }
        }
    }
    return out;
}

int main(int argc, char** argv) {
    try {
        // parse command line arguments, if available
        bool ignore = false;
        namespace po = boost::program_options;
        po::options_description desc("Options");
        desc.add_options()
          ("help,h", "")
          ("spotlight,s",po::value<string>(), "")
          ("ignore,i", "");

        po::variables_map vm;
        po::store(po::parse_command_line(argc, argv, desc), vm);
        if (vm.count("help")) {
            std::cout << HELP << std::endl;
            return SUCCESS;
        }
        if (vm.count("ignore")) ignore = true;
        po::notify(vm);

        if (!isatty(fileno(stdin))) {
            /*
            Stdin is coming from a pipe or redirection
            That's how we want to use this program
            */

            string line;
            Format *f = NULL;

            while (getline(cin, line)) {
                if (f == NULL) {
                    // only need to do this once
                    f = getFormat(line);
                    if (f != NULL) {
                        if (vm.count("spotlight")) {
                            std::string line = vm["spotlight"].as<string>();
                            f->setSpotlight(line);
                        }
                    }
                }
                if (f == NULL) {
                    if (!ignore)
                        cout << line << endl;
                    continue;
                }

                // execute parsing
                f->parse(line);
                if (f->valid()) {
                    f->print();
                }
                else {
                    // hum... it matched before, but not in this line
                    // maybe something went wrong or not properly parseable
                    // according to the expected REGEX
                    if (!ignore)
                        cout << line << endl;
                }
            }
            delete f;
        }
        else {
            /*
            Stdin is the terminal, so there is nothing to do
            just display help information and exit
            */
            std::cout << HELP << std::endl;
        }

    }
    catch(std::exception& e) {
        std::cerr << "Oops! Something went wrong. Error: " << e.what() << std::endl;
        return ERROR_UNKNOWN;
    }
    return SUCCESS;
}

ext: cpp

max_stars_repo_name: ferreus/logcat-colorize

max_issues_repo_name: ferreus/logcat-colorize

max_forks_repo_name: ferreus/logcat-colorize


text:
// Copyright 2020, Beeri 15.  All rights reserved.
// Author: Roman Gershman (romange@gmail.com)
//

#include "util/uring/proactor.h"

#include <liburing.h>
#include <string.h>
#include <sys/eventfd.h>
#include <sys/poll.h>

#include <boost/fiber/operations.hpp>
#include <boost/fiber/scheduler.hpp>

#include "absl/base/attributes.h"
#include "base/logging.h"
#include "base/macros.h"
#include "util/uring/uring_fiber_algo.h"

#define URING_CHECK(x)                                                           \
  do {                                                                           \
    int __res_val = (x);                                                         \
    if (UNLIKELY(__res_val < 0)) {                                               \
      char buf[128];                                                             \
      char* str = strerror_r(-__res_val, buf, sizeof(buf));                      \
      LOG(FATAL) << "Error " << (-__res_val) << " evaluating '" #x "': " << str; \
    }                                                                            \
  } while (false)

#ifndef __NR_io_uring_enter
#define __NR_io_uring_enter 426
#endif

using namespace boost;
namespace ctx = boost::context;

namespace util {
namespace uring {

namespace {

inline int sys_io_uring_enter(int fd, unsigned to_submit, unsigned min_complete, unsigned flags,
                              sigset_t* sig) {
  return syscall(__NR_io_uring_enter, fd, to_submit, min_complete, flags, sig, _NSIG / 8);
}

ABSL_ATTRIBUTE_NOINLINE int wait_for_cqe(io_uring* ring, sigset_t* sig = NULL) {
  // res must be 0 or -1.
  int res = sys_io_uring_enter(ring->ring_fd, 0, 1, IORING_ENTER_GETEVENTS, sig);
  if (res == 0 || errno == EINTR)
    return res;
  DCHECK_EQ(-1, res);
  res = errno;

  LOG(FATAL) << "Error " << (res) << " evaluating sys_io_uring_enter: " << strerror(res);
  return 0;
}

struct signal_state {
  struct Item {
    Proactor* proactor = nullptr;
    std::function<void(int)> cb;
  };

  Item signal_map[_NSIG];
};

signal_state* get_signal_state() {
  static signal_state state;

  return &state;
}

void SigAction(int signal, siginfo_t*, void*) {
  signal_state* state = get_signal_state();
  DCHECK_LT(signal, _NSIG);

  auto& item = state->signal_map[signal];
  auto cb = [signal, &item] { item.cb(signal); };

  if (item.proactor && item.cb) {
    item.proactor->AsyncFiber(std::move(cb));
  } else {
    LOG(ERROR) << "Tangling signal handler " << signal;
  }
}

inline uint64_t GetClockNanos() {
  timespec ts;
  clock_gettime(CLOCK_MONOTONIC, &ts);
  return ts.tv_sec * std::nano::den + ts.tv_nsec;
}

inline unsigned CQReadyCount(const io_uring& ring) {
  return io_uring_smp_load_acquire(ring.cq.ktail) - *ring.cq.khead;
}

unsigned IoRingPeek(const io_uring& ring, io_uring_cqe* cqes, unsigned count) {
  unsigned ready = CQReadyCount(ring);
  if (!ready)
    return 0;

  count = count > ready ? ready : count;
  unsigned head = *ring.cq.khead;
  unsigned mask = *ring.cq.kring_mask;
  unsigned last = head + count;
  for (int i = 0; head != last; head++, i++) {
    cqes[i] = ring.cq.cqes[head & mask];
  }
  return count;
}

constexpr uint64_t kIgnoreIndex = 0;
constexpr uint64_t kWakeIndex = 1;
constexpr uint64_t kUserDataCbIndex = 1024;
constexpr uint32_t kSpinLimit = 200;

}  // namespace

thread_local Proactor::TLInfo Proactor::tl_info_;

Proactor::Proactor() : task_queue_(128) {
  wake_fd_ = eventfd(0, EFD_CLOEXEC | EFD_NONBLOCK);
  CHECK_GT(wake_fd_, 0);

  volatile ctx::fiber dummy;  // For some weird reason I need this to pull
                              // boost::context into linkage.
}

Proactor::~Proactor() {
  CHECK(is_stopped_);
  if (thread_id_ != -1U) {
    io_uring_queue_exit(&ring_);
  }
  close(wake_fd_);

  signal_state* ss = get_signal_state();
  for (size_t i = 0; i < arraysize(ss->signal_map); ++i) {
    if (ss->signal_map[i].proactor == this) {
      ss->signal_map[i].proactor = nullptr;
      ss->signal_map[i].cb = nullptr;
    }
  }
}

void Proactor::Stop() {
  AsyncBrief([this] { is_stopped_ = true; });
  VLOG(1) << "Proactor::StopFinish";
}

void Proactor::Run(unsigned ring_depth, int wq_fd) {
  VLOG(1) << "Proactor::Run";
  Init(ring_depth, wq_fd);

  main_loop_ctx_ = fibers::context::active();
  fibers::scheduler* sched = main_loop_ctx_->get_scheduler();

  UringFiberAlgo* scheduler = new UringFiberAlgo(this);
  sched->set_algo(scheduler);
  this_fiber::properties<UringFiberProps>().set_name("ioloop");

  is_stopped_ = false;

  constexpr size_t kBatchSize = 64;
  struct io_uring_cqe cqes[kBatchSize];
  uint32_t tq_seq = 0;
  uint32_t num_stalls = 0;
  uint32_t spin_loops = 0, num_task_runs = 0;
  Tasklet task;

  while (true) {
    int num_submitted = io_uring_submit(&ring_);

    if (num_submitted >= 0) {
      if (num_submitted)
        DVLOG(2) << "Submitted " << num_submitted;
    } else if (num_submitted == -EBUSY) {
      VLOG(1) << "EBUSY " << num_submitted;
      num_submitted = 0;
    } else {
      URING_CHECK(num_submitted);
    }

    num_task_runs = 0;

    uint64_t task_start = 0;

    tq_seq = tq_seq_.load(std::memory_order_acquire);

    // This should handle wait-free and "submit-free" short CPU tasks enqued using Async/Await
    // calls. We allocate the quota of 500K nsec (500usec) of CPU time per iteration.
    while (task_queue_.try_dequeue(task)) {
      ++num_task_runs;
      tl_info_.monotonic_time = GetClockNanos();
      task();
      if (task_start == 0) {
        task_start = tl_info_.monotonic_time;
      } else if (task_start + 500000 < tl_info_.monotonic_time) {
        break;
      }
    }

    if (num_task_runs) {
      // Should we put 'notify' inside the loop? It might improve the latency.
      task_queue_avail_.notifyAll();
    }

    uint32_t cqe_count = IoRingPeek(ring_, cqes, kBatchSize);
    if (cqe_count) {
      // Once we copied the data we can mark the cqe consumed.
      io_uring_cq_advance(&ring_, cqe_count);
      DVLOG(2) << "Fetched " << cqe_count << " cqes";
      DispatchCompletions(cqes, cqe_count);
      sqe_avail_.notifyAll();
    }

    if (tq_seq & 1) {   // We allow dispatch fiber to run.
      tq_seq_.fetch_and(~1, std::memory_order_relaxed);
      this_fiber::yield();
    }

    if (sched->has_ready_fibers()) {
      // Suspend this fiber until others will run and get blocked.
      // Eventually UringFiberAlgo will resume back this fiber in suspend_until
      // function.
      DVLOG(2) << "Suspend ioloop";
      tl_info_.monotonic_time = GetClockNanos();
      sched->suspend();

      DVLOG(2) << "Resume ioloop";
      continue;
    }

    if (cqe_count || io_uring_sq_ready(&ring_))
      continue;

    // Lets spin a bit to make a system a bit more responsive.
    if (++spin_loops < kSpinLimit) {
      // pthread_yield(); We should not spin using sched_yield it burns fuckload of cpu.
      continue;
    }

    spin_loops = 0;  // Reset the spinning.

    /**
     * If tq_seq_ has changed since it was cached into tq_seq, then
     * EmplaceTaskQueue succeeded and we might have more tasks to execute - lets
     * run the loop again. Otherwise, set tq_seq_ to WAIT_SECTION, hinting that
     * we are going to stall now. Other threads will need to wake-up the ring
     * (see WakeRing()) but only the they will actually syscall only once.
     */
    if (tq_seq_.compare_exchange_weak(tq_seq, WAIT_SECTION_STATE, std::memory_order_acquire)) {
      if (is_stopped_)
        break;
      DVLOG(1) << "wait_for_cqe";
      int res = wait_for_cqe(&ring_);
      DVLOG(1) << "Woke up " << res << "/" << tq_seq_.load(std::memory_order_acquire);

      tq_seq = 0;
      ++num_stalls;

      // Reset all except the LSB bit that signals that we need to switch to dispatch fiber.
      tq_seq_.fetch_and(1, std::memory_order_release);
    }
  }

  VLOG(1) << "wakeups/stalls: " << tq_wakeups_.load() << "/" << num_stalls;

  VLOG(1) << "centries size: " << centries_.size();
  centries_.clear();
}

void Proactor::Init(size_t ring_size, int wq_fd) {
  CHECK_EQ(0, ring_size & (ring_size - 1));
  CHECK_GE(ring_size, 8);
  CHECK_EQ(0, thread_id_) << "Init was already called";

  io_uring_params params;
  memset(&params, 0, sizeof(params));

  // Optionally reuse the already created work-queue from another uring.
  if (wq_fd > 0) {
    params.flags |= IORING_SETUP_ATTACH_WQ;
    params.wq_fd = wq_fd;
  }

  // it seems that SQPOLL requires registering each fd, including sockets fds.
  // need to check if its worth pursuing.
  // For sure not in short-term.
  // params.flags = IORING_SETUP_SQPOLL;
  URING_CHECK(io_uring_queue_init_params(ring_size, &ring_, &params));
  fast_poll_f_ = (params.features & IORING_FEAT_FAST_POLL) != 0;
  if (!fast_poll_f_) {
    LOG_FIRST_N(INFO, 1) << "IORING_FEAT_FAST_POLL feature is not present in the kernel";
  }

  if (0 == (params.features & IORING_FEAT_NODROP)) {
    LOG_FIRST_N(INFO, 1) << "IORING_FEAT_NODROP feature is not present in the kernel";
  }

  if (params.features & IORING_FEAT_SINGLE_MMAP) {
    size_t sz = ring_.sq.ring_sz + params.sq_entries * sizeof(struct io_uring_sqe);
    LOG_FIRST_N(INFO, 1) << "IORing with " << params.sq_entries << " allocated " << sz
                         << " bytes, cq_entries is " << *ring_.cq.kring_entries;
  }
  CHECK_EQ(ring_size, params.sq_entries);  // Sanity.

  struct io_uring_sqe* sqe = io_uring_get_sqe(&ring_);
  CHECK_NOTNULL(sqe);

  io_uring_prep_poll_add(sqe, wake_fd_, POLLIN);
  sqe->user_data = kWakeIndex;

  centries_.resize(params.sq_entries);
  next_free_ = 0;
  for (size_t i = 0; i < centries_.size() - 1; ++i) {
    centries_[i].val = i + 1;
  }

  thread_id_ = pthread_self();
  tl_info_.is_proactor_thread = true;
}

void Proactor::WakeRing() {
  DVLOG(1) << "Wake ring " << tq_seq_.load(std::memory_order_relaxed);

  tq_wakeups_.fetch_add(1, std::memory_order_relaxed);
  uint64_t val = 1;

  CHECK_EQ(8, write(wake_fd_, &val, sizeof(uint64_t)));
}

void Proactor::DispatchCompletions(io_uring_cqe* cqes, unsigned count) {
  for (unsigned i = 0; i < count; ++i) {
    auto& cqe = cqes[i];

    // I allocate range of 1024 reserved values for the internal Proactor use.

    if (cqe.user_data >= kUserDataCbIndex) {  // our heap range surely starts higher than 1k.
      size_t index = cqe.user_data - kUserDataCbIndex;
      DCHECK_LT(index, centries_.size());
      auto& e = centries_[index];
      DCHECK(e.cb) << index;

      CbType func;
      auto payload = e.val;
      func.swap(e.cb);

      e.val = next_free_;
      next_free_ = index;

      func(cqe.res, payload, this);
      continue;
    }

    if (cqe.user_data == kIgnoreIndex)
      continue;

    if (cqe.user_data == kWakeIndex) {
      // We were woken up. Need to rearm wake_fd_ poller.
      DCHECK_GE(cqe.res, 0);

      DVLOG(1) << "Wakeup " << cqe.res << "/" << cqe.flags;

      CHECK_EQ(8, read(wake_fd_, &cqe.user_data, 8));  // Pull the data

      // TODO: to move io_uring_get_sqe call from here to before we stall.
      struct io_uring_sqe* sqe = io_uring_get_sqe(&ring_);
      CHECK(sqe);  // We just consumed CQEs. I assume it's enough to get an SQE.
      io_uring_prep_poll_add(sqe, wake_fd_, POLLIN);  // And rearm.
      sqe->user_data = kWakeIndex;
    } else {
      LOG(ERROR) << "Unrecognized user_data " << cqe.user_data;
    }
  }
}

SubmitEntry Proactor::GetSubmitEntry(CbType cb, int64_t payload) {
  io_uring_sqe* res = io_uring_get_sqe(&ring_);
  if (res == NULL) {
    fibers::context* current = fibers::context::active();
    CHECK(current != main_loop_ctx_) << "SQE overflow in the main context";

    sqe_avail_.await([this] { return io_uring_sq_space_left(&ring_) > 0; });
    res = io_uring_get_sqe(&ring_);  // now we should have the space.
    CHECK(res);
  }

  if (cb) {
    if (next_free_ < 0) {
      RegrowCentries();
      DCHECK_GT(next_free_, 0);
    }

    res->user_data = next_free_ + kUserDataCbIndex;
    DCHECK_LT(next_free_, centries_.size());

    auto& e = centries_[next_free_];
    DCHECK(!e.cb);  // cb is undefined.
    DVLOG(1) << "GetSubmitEntry: index: " << next_free_ << ", socket: " << payload;

    next_free_ = e.val;
    e.cb = std::move(cb);
    e.val = payload;
    e.opcode = -1;
  } else {
    res->user_data = kIgnoreIndex;
  }

  return SubmitEntry{res};
}

void Proactor::RegisterSignal(std::initializer_list<uint16_t> l, std::function<void(int)> cb) {
  auto* state = get_signal_state();

  struct sigaction sa;
  memset(&sa, 0, sizeof(sa));

  if (cb) {
    sa.sa_flags = SA_SIGINFO;
    sa.sa_sigaction = &SigAction;

    for (uint16_t val : l) {
      CHECK(!state->signal_map[val].cb) << "Signal " << val << " was already registered";
      state->signal_map[val].cb = cb;
      state->signal_map[val].proactor = this;

      CHECK_EQ(0, sigaction(val, &sa, NULL));
    }
  } else {
    sa.sa_handler = SIG_DFL;

    for (uint16_t val : l) {
      CHECK(state->signal_map[val].cb) << "Signal " << val << " was already registered";
      state->signal_map[val].cb = nullptr;
      state->signal_map[val].proactor = nullptr;

      CHECK_EQ(0, sigaction(val, &sa, NULL));
    }
  }
}

void Proactor::RegrowCentries() {
  size_t prev = centries_.size();
  VLOG(1) << "RegrowCentries from " << prev << " to " << prev * 2;

  centries_.resize(prev * 2);  // grow by 2.
  next_free_ = prev;
  for (; prev < centries_.size() - 1; ++prev)
    centries_[prev].val = prev + 1;
}

}  // namespace uring
}  // namespace util

ext: cc

max_stars_repo_name: ekatz-quotient/gaia

max_issues_repo_name: ekatz-quotient/gaia

max_forks_repo_name: ekatz-quotient/gaia


text:
//  Copyright (c) 2001-2011 Hartmut Kaiser
//
//  Distributed under the Boost Software License, Version 1.0. (See accompanying
//  file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)

#if !defined(BOOST_SPIRIT_KARMA_CREATE_NOV_21_2009_0340PM)
#define BOOST_SPIRIT_KARMA_CREATE_NOV_21_2009_0340PM

#if defined(_MSC_VER)
#pragma once
#endif

#include <boost/spirit/home/karma/auto/meta_create.hpp>

///////////////////////////////////////////////////////////////////////////////
namespace boost { namespace spirit { namespace result_of
{
    ///////////////////////////////////////////////////////////////////////////
    template <typename T>
    struct create_generator
      : spirit::traits::meta_create<karma::domain, T> {};
}}}

///////////////////////////////////////////////////////////////////////////////
namespace boost { namespace spirit { namespace karma
{
    // Main API function for generator creation from data type
    template <typename T>
    typename result_of::create_generator<T>::type
    create_generator()
    {
        return spirit::traits::meta_create<karma::domain, T>::call();
    }
}}}

///////////////////////////////////////////////////////////////////////////////
namespace boost { namespace spirit { namespace traits
{
    // Meta function returning true if create_generator does return a valid
    // generator for the given type T.
    template <typename T>
    struct create_generator_exists
      : meta_create_exists<karma::domain, T> {};
}}}

#endif

ext: hpp

max_stars_repo_name: rudylee/expo

max_issues_repo_name: rudylee/expo

max_forks_repo_name: rudylee/expo


text:
// Boost.Geometry (aka GGL, Generic Geometry Library)

// Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.

// This file was modified by Oracle on 2013, 2014, 2015, 2017, 2018, 2019.
// Modifications copyright (c) 2013-2019 Oracle and/or its affiliates.

// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle

// Use, modification and distribution is subject to the Boost Software License,
// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)

#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURN_INFO_HELPERS_HPP
#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURN_INFO_HELPERS_HPP

#include <boost/geometry/algorithms/detail/direction_code.hpp>
#include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
#include <boost/geometry/algorithms/detail/recalculate.hpp>
#include <boost/geometry/core/assert.hpp>
#include <boost/geometry/geometries/segment.hpp> // referring_segment
#include <boost/geometry/policies/relate/direction.hpp>
#include <boost/geometry/policies/relate/intersection_points.hpp>
#include <boost/geometry/policies/relate/tupled.hpp>
#include <boost/geometry/policies/robustness/rescale_policy_tags.hpp>
#include <boost/geometry/strategies/intersection_result.hpp>

namespace boost { namespace geometry {

#ifndef DOXYGEN_NO_DETAIL
namespace detail { namespace overlay {

enum turn_position { position_middle, position_front, position_back };

template <typename Point, typename SegmentRatio>
struct turn_operation_linear
    : public turn_operation<Point, SegmentRatio>
{
    turn_operation_linear()
        : position(position_middle)
        , is_collinear(false)
    {}

    turn_position position;
    bool is_collinear; // valid only for Linear geometry
};

template
<
    typename TurnPointCSTag,
    typename UniqueSubRange1,
    typename UniqueSubRange2,
    typename SideStrategy
>
struct side_calculator
{
    typedef typename UniqueSubRange1::point_type point1_type;
    typedef typename UniqueSubRange2::point_type point2_type;

    inline side_calculator(UniqueSubRange1 const& range_p,
                           UniqueSubRange2 const& range_q,
                           SideStrategy const& side_strategy)
        : m_side_strategy(side_strategy)
        , m_range_p(range_p)
        , m_range_q(range_q)
    {}

    inline int pk_wrt_p1() const { return m_side_strategy.apply(get_pi(), get_pj(), get_pk()); }
    inline int pk_wrt_q1() const { return m_side_strategy.apply(get_qi(), get_qj(), get_pk()); }
    inline int qk_wrt_p1() const { return m_side_strategy.apply(get_pi(), get_pj(), get_qk()); }
    inline int qk_wrt_q1() const { return m_side_strategy.apply(get_qi(), get_qj(), get_qk()); }

    inline int pk_wrt_q2() const { return m_side_strategy.apply(get_qj(), get_qk(), get_pk()); }
    inline int qk_wrt_p2() const { return m_side_strategy.apply(get_pj(), get_pk(), get_qk()); }

    // Necessary when rescaling turns off:
    inline int qj_wrt_p1() const { return m_side_strategy.apply(get_pi(), get_pj(), get_qj()); }
    inline int qj_wrt_p2() const { return m_side_strategy.apply(get_pj(), get_pk(), get_qj()); }
    inline int pj_wrt_q1() const { return m_side_strategy.apply(get_qi(), get_qj(), get_pj()); }
    inline int pj_wrt_q2() const { return m_side_strategy.apply(get_qj(), get_qk(), get_pj()); }

    inline point1_type const& get_pi() const { return m_range_p.at(0); }
    inline point1_type const& get_pj() const { return m_range_p.at(1); }
    inline point1_type const& get_pk() const { return m_range_p.at(2); }

    inline point2_type const& get_qi() const { return m_range_q.at(0); }
    inline point2_type const& get_qj() const { return m_range_q.at(1); }
    inline point2_type const& get_qk() const { return m_range_q.at(2); }

    // Used side-strategy, owned by the calculator,
    // created from .get_side_strategy()
    SideStrategy m_side_strategy;

    // Used ranges - owned by get_turns or (for robust points) by intersection_info_base
    UniqueSubRange1 const& m_range_p;
    UniqueSubRange2 const& m_range_q;
};

template<typename Point, typename UniqueSubRange, typename RobustPolicy>
struct robust_subrange_adapter
{
    typedef Point point_type;

    robust_subrange_adapter(UniqueSubRange const& unique_sub_range,
                     Point const& robust_point_i, Point const& robust_point_j,
                     RobustPolicy const& robust_policy)

        : m_unique_sub_range(unique_sub_range)
        , m_robust_policy(robust_policy)
        , m_robust_point_i(robust_point_i)
        , m_robust_point_j(robust_point_j)
        , m_k_retrieved(false)
    {}

    std::size_t size() const { return m_unique_sub_range.size(); }

    //! Get precalculated point
    Point const& at(std::size_t index) const
    {
        BOOST_GEOMETRY_ASSERT(index < size());
        switch (index)
        {
            case 0 : return m_robust_point_i;
            case 1 : return m_robust_point_j;
            case 2 : return get_point_k();
            default : return m_robust_point_i;
        }
    }

private :
    Point const& get_point_k() const
    {
        if (! m_k_retrieved)
        {
            geometry::recalculate(m_robust_point_k, m_unique_sub_range.at(2), m_robust_policy);
            m_k_retrieved = true;
        }
        return m_robust_point_k;
    }

    UniqueSubRange const& m_unique_sub_range;
    RobustPolicy const& m_robust_policy;

    Point const& m_robust_point_i;
    Point const& m_robust_point_j;
    mutable Point m_robust_point_k;

    mutable bool m_k_retrieved;
};

template
<
    typename UniqueSubRange1, typename UniqueSubRange2,
    typename RobustPolicy
>
struct robust_point_calculator
{
    typedef typename geometry::robust_point_type
        <
            typename UniqueSubRange1::point_type, RobustPolicy
        >::type robust_point1_type;
    typedef typename geometry::robust_point_type
        <
            typename UniqueSubRange2::point_type, RobustPolicy
        >::type robust_point2_type;

    inline robust_point_calculator(UniqueSubRange1 const& range_p,
                                   UniqueSubRange2 const& range_q,
                                   RobustPolicy const& robust_policy)
        : m_robust_policy(robust_policy)
        , m_range_p(range_p)
        , m_range_q(range_q)
        , m_pk_retrieved(false)
        , m_qk_retrieved(false)
    {
        // Calculate pi,pj and qi,qj which are almost always necessary
        // But don't calculate pk/qk yet, which is retrieved (taking
        // more time) and not always necessary.
        geometry::recalculate(m_rpi, range_p.at(0), robust_policy);
        geometry::recalculate(m_rpj, range_p.at(1), robust_policy);
        geometry::recalculate(m_rqi, range_q.at(0), robust_policy);
        geometry::recalculate(m_rqj, range_q.at(1), robust_policy);
    }

    inline robust_point1_type const& get_rpk() const
    {
        if (! m_pk_retrieved)
        {
            geometry::recalculate(m_rpk, m_range_p.at(2), m_robust_policy);
            m_pk_retrieved = true;
        }
        return m_rpk;
    }
    inline robust_point2_type const& get_rqk() const
    {
        if (! m_qk_retrieved)
        {
            geometry::recalculate(m_rqk, m_range_q.at(2), m_robust_policy);
            m_qk_retrieved = true;
        }
        return m_rqk;
    }

    robust_point1_type m_rpi, m_rpj;
    robust_point2_type m_rqi, m_rqj;

private :
    RobustPolicy const& m_robust_policy;
    UniqueSubRange1 const& m_range_p;
    UniqueSubRange2 const& m_range_q;

    // On retrieval
    mutable robust_point1_type m_rpk;
    mutable robust_point2_type m_rqk;
    mutable bool m_pk_retrieved;
    mutable bool m_qk_retrieved;
};

// Default version (empty - specialized below)
template
<
    typename UniqueSubRange1, typename UniqueSubRange2,
    typename TurnPoint, typename UmbrellaStrategy,
    typename RobustPolicy,
    typename Tag = typename rescale_policy_type<RobustPolicy>::type
>
class intersection_info_base {};

// Version with rescaling, having robust points
template
<
    typename UniqueSubRange1, typename UniqueSubRange2,
    typename TurnPoint, typename UmbrellaStrategy,
    typename RobustPolicy
>
class intersection_info_base<UniqueSubRange1, UniqueSubRange2,
        TurnPoint, UmbrellaStrategy, RobustPolicy, rescale_policy_tag>
{
    typedef robust_point_calculator
    <
        UniqueSubRange1, UniqueSubRange2,
        RobustPolicy
    >
    robust_calc_type;

public:
    typedef segment_intersection_points
    <
        TurnPoint,
        geometry::segment_ratio<boost::long_long_type>
    > intersection_point_type;
    typedef policies::relate::segments_tupled
        <
            policies::relate::segments_intersection_points
                <
                    intersection_point_type
                >,
            policies::relate::segments_direction
        > intersection_policy_type;

    typedef typename intersection_policy_type::return_type result_type;

    typedef typename robust_calc_type::robust_point1_type robust_point1_type;
    typedef typename robust_calc_type::robust_point2_type robust_point2_type;

    typedef robust_subrange_adapter<robust_point1_type, UniqueSubRange1, RobustPolicy> robust_subrange1;
    typedef robust_subrange_adapter<robust_point2_type, UniqueSubRange2, RobustPolicy> robust_subrange2;

    typedef typename cs_tag<TurnPoint>::type cs_tag;

    typedef typename UmbrellaStrategy::side_strategy_type side_strategy_type;
    typedef side_calculator<cs_tag, robust_subrange1, robust_subrange2,
             side_strategy_type> side_calculator_type;

    typedef side_calculator
        <
            cs_tag, robust_subrange2, robust_subrange1,
            side_strategy_type
        > robust_swapped_side_calculator_type;

    intersection_info_base(UniqueSubRange1 const& range_p,
                           UniqueSubRange2 const& range_q,
                           UmbrellaStrategy const& umbrella_strategy,
                           RobustPolicy const& robust_policy)
        : m_range_p(range_p)
        , m_range_q(range_q)
        , m_robust_calc(range_p, range_q, robust_policy)
        , m_robust_range_p(range_p, m_robust_calc.m_rpi, m_robust_calc.m_rpj, robust_policy)
        , m_robust_range_q(range_q, m_robust_calc.m_rqi, m_robust_calc.m_rqj, robust_policy)
        , m_side_calc(m_robust_range_p, m_robust_range_q,
                      umbrella_strategy.get_side_strategy())
        , m_result(umbrella_strategy.apply(range_p, range_q,
                       intersection_policy_type(),
                       m_robust_range_p, m_robust_range_q))
    {}

    inline bool p_is_last_segment() const { return m_range_p.is_last_segment(); }
    inline bool q_is_last_segment() const { return m_range_q.is_last_segment(); }

    inline robust_point1_type const& rpi() const { return m_robust_calc.m_rpi; }
    inline robust_point1_type const& rpj() const { return m_robust_calc.m_rpj; }
    inline robust_point1_type const& rpk() const { return m_robust_calc.get_rpk(); }

    inline robust_point2_type const& rqi() const { return m_robust_calc.m_rqi; }
    inline robust_point2_type const& rqj() const { return m_robust_calc.m_rqj; }
    inline robust_point2_type const& rqk() const { return m_robust_calc.get_rqk(); }

    inline side_calculator_type const& sides() const { return m_side_calc; }

    robust_swapped_side_calculator_type get_swapped_sides() const
    {
        robust_swapped_side_calculator_type result(
                            m_robust_range_q, m_robust_range_p,
                            m_side_calc.m_side_strategy);
        return result;
    }

private :

    // Owned by get_turns
    UniqueSubRange1 const& m_range_p;
    UniqueSubRange2 const& m_range_q;

    // Owned by this class
    robust_calc_type m_robust_calc;
    robust_subrange1 m_robust_range_p;
    robust_subrange2 m_robust_range_q;
    side_calculator_type m_side_calc;

protected :
    result_type m_result;
};

// Version without rescaling
template
<
    typename UniqueSubRange1, typename UniqueSubRange2,
    typename TurnPoint, typename UmbrellaStrategy,
    typename RobustPolicy
>
class intersection_info_base<UniqueSubRange1, UniqueSubRange2,
        TurnPoint, UmbrellaStrategy, RobustPolicy, no_rescale_policy_tag>
{
public:

    typedef segment_intersection_points<TurnPoint> intersection_point_type;
    typedef policies::relate::segments_tupled
        <
            policies::relate::segments_intersection_points
                <
                    intersection_point_type
                >,
            policies::relate::segments_direction
        > intersection_policy_type;

    typedef typename intersection_policy_type::return_type result_type;

    typedef typename UniqueSubRange1::point_type point1_type;
    typedef typename UniqueSubRange2::point_type point2_type;

    typedef typename UmbrellaStrategy::cs_tag cs_tag;

    typedef typename UmbrellaStrategy::side_strategy_type side_strategy_type;
    typedef side_calculator<cs_tag, UniqueSubRange1, UniqueSubRange2, side_strategy_type> side_calculator_type;

    typedef side_calculator
        <
            cs_tag, UniqueSubRange2, UniqueSubRange1,
            side_strategy_type
        > swapped_side_calculator_type;

    intersection_info_base(UniqueSubRange1 const& range_p,
                           UniqueSubRange2 const& range_q,
                           UmbrellaStrategy const& umbrella_strategy,
                           no_rescale_policy const& )
        : m_range_p(range_p)
        , m_range_q(range_q)
        , m_side_calc(range_p, range_q,
                      umbrella_strategy.get_side_strategy())
        , m_result(umbrella_strategy.apply(range_p, range_q, intersection_policy_type()))
    {}

    inline bool p_is_last_segment() const { return m_range_p.is_last_segment(); }
    inline bool q_is_last_segment() const { return m_range_q.is_last_segment(); }

    inline point1_type const& rpi() const { return m_side_calc.get_pi(); }
    inline point1_type const& rpj() const { return m_side_calc.get_pj(); }
    inline point1_type const& rpk() const { return m_side_calc.get_pk(); }

    inline point2_type const& rqi() const { return m_side_calc.get_qi(); }
    inline point2_type const& rqj() const { return m_side_calc.get_qj(); }
    inline point2_type const& rqk() const { return m_side_calc.get_qk(); }

    inline side_calculator_type const& sides() const { return m_side_calc; }

    swapped_side_calculator_type get_swapped_sides() const
    {
        swapped_side_calculator_type result(
            m_range_q, m_range_p,
            m_side_calc.m_side_strategy);
        return result;
    }

private :
    // Owned by get_turns
    UniqueSubRange1 const& m_range_p;
    UniqueSubRange2 const& m_range_q;

    // Owned by this class
    side_calculator_type m_side_calc;

protected :
    result_type m_result;
};

template
<
    typename UniqueSubRange1, typename UniqueSubRange2,
    typename TurnPoint,
    typename UmbrellaStrategy,
    typename RobustPolicy
>
class intersection_info
    : public intersection_info_base<UniqueSubRange1, UniqueSubRange2,
        TurnPoint, UmbrellaStrategy, RobustPolicy>
{
    typedef intersection_info_base<UniqueSubRange1, UniqueSubRange2,
        TurnPoint, UmbrellaStrategy, RobustPolicy> base;

public:

    typedef typename UniqueSubRange1::point_type point1_type;
    typedef typename UniqueSubRange2::point_type point2_type;

    typedef UmbrellaStrategy intersection_strategy_type;
    typedef typename UmbrellaStrategy::side_strategy_type side_strategy_type;
    typedef typename UmbrellaStrategy::cs_tag cs_tag;

    typedef typename base::side_calculator_type side_calculator_type;
    typedef typename base::result_type result_type;

    typedef typename boost::tuples::element<0, result_type>::type i_info_type; // intersection_info
    typedef typename boost::tuples::element<1, result_type>::type d_info_type; // dir_info

    intersection_info(UniqueSubRange1 const& range_p,
                      UniqueSubRange2 const& range_q,
                      UmbrellaStrategy const& umbrella_strategy,
                      RobustPolicy const& robust_policy)
        : base(range_p, range_q,
               umbrella_strategy, robust_policy)
        , m_intersection_strategy(umbrella_strategy)
        , m_robust_policy(robust_policy)
    {}

    inline result_type const& result() const { return base::m_result; }
    inline i_info_type const& i_info() const { return base::m_result.template get<0>(); }
    inline d_info_type const& d_info() const { return base::m_result.template get<1>(); }

    inline side_strategy_type get_side_strategy() const
    {
        return m_intersection_strategy.get_side_strategy();
    }

    // TODO: it's more like is_spike_ip_p
    inline bool is_spike_p() const
    {
        if (base::p_is_last_segment())
        {
            return false;
        }
        if (base::sides().pk_wrt_p1() == 0)
        {
            // p:  pi--------pj--------pk
            // or: pi----pk==pj

            if (! is_ip_j<0>())
            {
                return false;
            }

            // TODO: why is q used to determine spike property in p?
            bool const has_qk = ! base::q_is_last_segment();
            int const qk_p1 = has_qk ? base::sides().qk_wrt_p1() : 0;
            int const qk_p2 = has_qk ? base::sides().qk_wrt_p2() : 0;

            if (qk_p1 == -qk_p2)
            {
                if (qk_p1 == 0)
                {
                    // qk is collinear with both p1 and p2,
                    // verify if pk goes backwards w.r.t. pi/pj
                    return direction_code<cs_tag>(base::rpi(), base::rpj(), base::rpk()) == -1;
                }

                // qk is at opposite side of p1/p2, therefore
                // p1/p2 (collinear) are opposite and form a spike
                return true;
            }
        }

        return false;
    }

    inline bool is_spike_q() const
    {
        if (base::q_is_last_segment())
        {
            return false;
        }

        // See comments at is_spike_p
        if (base::sides().qk_wrt_q1() == 0)
        {
            if (! is_ip_j<1>())
            {
                return false;
            }

            // TODO: why is p used to determine spike property in q?
            bool const has_pk = ! base::p_is_last_segment();
            int const pk_q1 = has_pk ? base::sides().pk_wrt_q1() : 0;
            int const pk_q2 = has_pk ? base::sides().pk_wrt_q2() : 0;

            if (pk_q1 == -pk_q2)
            {
                if (pk_q1 == 0)
                {
                    return direction_code<cs_tag>(base::rqi(), base::rqj(), base::rqk()) == -1;
                }

                return true;
            }
        }

        return false;
    }

private:
    template <std::size_t OpId>
    bool is_ip_j() const
    {
        int arrival = d_info().arrival[OpId];
        bool same_dirs = d_info().dir_a == 0 && d_info().dir_b == 0;

        if (same_dirs)
        {
            if (i_info().count == 2)
            {
                return arrival != -1;
            }
            else
            {
                return arrival == 0;
            }
        }
        else
        {
            return arrival == 1;
        }
    }

    UmbrellaStrategy const& m_intersection_strategy;
    RobustPolicy const& m_robust_policy;
};

}} // namespace detail::overlay
#endif // DOXYGEN_NO_DETAIL

}} // namespace boost::geometry

#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURN_INFO_HELPERS_HPP

max_stars_repo_name: cpp-pm/boost

max_issues_repo_name: cpp-pm/boost

max_forks_repo_name: cpp-pm/boost