#ifndef slic3r_Layer_hpp_
#define slic3r_Layer_hpp_

#include "libslic3r.h"
#include "BoundingBox.hpp"
#include "Flow.hpp"
#include "SurfaceCollection.hpp"
#include "ExtrusionEntityCollection.hpp"
#include "RegionExpansion.hpp"


namespace Slic3r {

class ExPolygon;
using ExPolygons = std::vector<ExPolygon>;
class Layer;
using LayerPtrs = std::vector<Layer*>;
class LayerRegion;
using LayerRegionPtrs = std::vector<LayerRegion*>;
class PrintRegion;
class PrintObject;

namespace FillAdaptive {
    struct Octree;
};

namespace FillLightning {
    class Generator;
};

class LayerRegion
{
public:
    Layer*                      layer()         { return m_layer; }
    const Layer*                layer() const   { return m_layer; }
    const PrintRegion&          region() const  { return *m_region; }

    const SurfaceCollection& get_slices() const { return slices; }

    // collection of surfaces generated by slicing the original geometry
    // divided by type top/bottom/internal
    SurfaceCollection           slices;
    // Backed up slices before they are split into top/bottom/internal.
    // Only backed up for multi-region layers or layers with elephant foot compensation.
    //FIXME Review whether not to simplify the code by keeping the raw_slices all the time.
    ExPolygons                  raw_slices;

    // collection of extrusion paths/loops filling gaps
    // These fills are generated by the perimeter generator.
    // They are not printed on their own, but they are copied to this->fills during infill generation.
    ExtrusionEntityCollection   thin_fills;

    // Unspecified fill polygons, used for overhang detection ("ensure vertical wall thickness feature")
    // and for re-starting of infills.
    ExPolygons                  fill_expolygons;
    // collection of surfaces for infill generation
    SurfaceCollection           fill_surfaces;
    // BBS: Unspecified fill polygons, used for interecting when we don't want the infill/perimeter overlap
    ExPolygons                  fill_no_overlap_expolygons;

    // collection of expolygons representing the bridged areas (thus not
    // needing support material)
//    Polygons                    bridged;

    // collection of polylines representing the unsupported bridge edges
    Polylines          			unsupported_bridge_edges;

    // ordered collection of extrusion paths/loops to build all perimeters
    // (this collection contains only ExtrusionEntityCollection objects)
    ExtrusionEntityCollection   perimeters;

    // ordered collection of extrusion paths to fill surfaces
    // (this collection contains only ExtrusionEntityCollection objects)
    ExtrusionEntityCollection   fills;

    Flow    flow(FlowRole role) const;
    Flow    flow(FlowRole role, double layer_height) const;
    Flow    bridging_flow(FlowRole role, bool thick_bridge = false) const;

    void    slices_to_fill_surfaces_clipped();
    void    prepare_fill_surfaces();
    //BBS
    void    make_perimeters(const SurfaceCollection &slices, SurfaceCollection* fill_surfaces, ExPolygons* fill_no_overlap);
    void    process_external_surfaces(const Layer *lower_layer, const Polygons *lower_layer_covered);
    double  infill_area_threshold() const;
    // Trim surfaces by trimming polygons. Used by the elephant foot compensation at the 1st layer.
    void    trim_surfaces(const Polygons &trimming_polygons);
    // Single elephant foot compensation step, used by the elephant foor compensation at the 1st layer.
    // Trim surfaces by trimming polygons (shrunk by an elephant foot compensation step), but don't shrink narrow parts so much that no perimeter would fit.
    void    elephant_foot_compensation_step(const float elephant_foot_compensation_perimeter_step, const Polygons &trimming_polygons);

    void    export_region_slices_to_svg(const char *path) const;
    void    export_region_fill_surfaces_to_svg(const char *path) const;
    // Export to "out/LayerRegion-name-%d.svg" with an increasing index with every export.
    void    export_region_slices_to_svg_debug(const char *name) const;
    void    export_region_fill_surfaces_to_svg_debug(const char *name) const;

    // Is there any valid extrusion assigned to this LayerRegion?
    bool    has_extrusions() const { return ! this->perimeters.entities.empty() || ! this->fills.entities.empty(); }
    //BBS
    void    simplify_infill_extrusion_entity() { simplify_entity_collection(&fills); }
    void    simplify_wall_extrusion_entity() { simplify_entity_collection(&perimeters); }
private:
    void    simplify_entity_collection(ExtrusionEntityCollection* entity_collection);
    void    simplify_path(ExtrusionPath* path);
    void    simplify_multi_path(ExtrusionMultiPath* multipath);
    void    simplify_loop(ExtrusionLoop* loop);

protected:
    friend class Layer;
    friend class PrintObject;

    LayerRegion(Layer *layer, const PrintRegion *region) : m_layer(layer), m_region(region) {}
    ~LayerRegion() {}

private:
    Layer             *m_layer;
    const PrintRegion *m_region;
};

class Layer
{
public:
    // Sequential index of this layer in PrintObject::m_layers, offsetted by the number of raft layers.
    size_t              id() const          { return m_id; }
    void                set_id(size_t id)   { m_id = id; }
    PrintObject*        object()            { return m_object; }
    const PrintObject*  object() const      { return m_object; }

    Layer              *upper_layer;
    Layer              *lower_layer;
    bool                slicing_errors;
    coordf_t            slice_z;       // Z used for slicing in unscaled coordinates
    coordf_t            print_z;       // Z used for printing in unscaled coordinates
    coordf_t            height;        // layer height in unscaled coordinates
    coordf_t            bottom_z() const { return this->print_z - this->height; }

    // BBS
    mutable ExPolygons          sharp_tails;
    mutable ExPolygons          cantilevers;
    mutable std::vector<float>  sharp_tails_height;

    // Collection of expolygons generated by slicing the possibly multiple meshes of the source geometry
    // (with possibly differing extruder ID and slicing parameters) and merged.
    // For the first layer, if the Elephant foot compensation is applied, this lslice is uncompensated, therefore
    // it includes the Elephant foot effect, thus it corresponds to the shape of the printed 1st layer.
    // These lslices aka islands are chained by the shortest traverse distance and this traversal
    // order will be applied by the G-code generator to the extrusions fitting into these lslices.
    // These lslices are also used to detect overhangs and overlaps between successive layers, therefore it is important
    // that the 1st lslice is not compensated by the Elephant foot compensation algorithm.
    ExPolygons 				 lslices;
    ExPolygons 				 lslices_extrudable;  // BBS: the extrudable part of lslices used for tree support
    std::vector<BoundingBox> lslices_bboxes;

    // BBS
    ExPolygons              loverhangs;
    BoundingBox             loverhangs_bbox;
    size_t                  region_count() const { return m_regions.size(); }
    const LayerRegion*      get_region(int idx) const { return m_regions[idx]; }
    LayerRegion*            get_region(int idx) { return m_regions[idx]; }
    LayerRegion*            add_region(const PrintRegion *print_region);
    const LayerRegionPtrs&  regions() const { return m_regions; }
    // Test whether whether there are any slices assigned to this layer.
    bool                    empty() const;
    void                    make_slices();
    // Backup and restore raw sliced regions if needed.
    //FIXME Review whether not to simplify the code by keeping the raw_slices all the time.
    void                    backup_untyped_slices();
    void                    restore_untyped_slices();
    // To improve robustness of detect_surfaces_type() when reslicing (working with typed slices), see GH issue #7442.
    void                    restore_untyped_slices_no_extra_perimeters();
    // Slices merged into islands, to be used by the elephant foot compensation to trim the individual surfaces with the shrunk merged slices.
    ExPolygons              merged(float offset) const;
    template <class T> bool any_internal_region_slice_contains(const T &item) const {
        for (const LayerRegion *layerm : m_regions) if (layerm->slices.any_internal_contains(item)) return true;
        return false;
    }
    template <class T> bool any_bottom_region_slice_contains(const T &item) const {
        for (const LayerRegion *layerm : m_regions) if (layerm->slices.any_bottom_contains(item)) return true;
        return false;
    }
    void                    make_perimeters();
    // Phony version of make_fills() without parameters for Perl integration only.
    void                    make_fills() { this->make_fills(nullptr, nullptr); }
    void                    make_fills(FillAdaptive::Octree* adaptive_fill_octree, FillAdaptive::Octree* support_fill_octree, FillLightning::Generator* lightning_generator = nullptr);
    Polylines               generate_sparse_infill_polylines_for_anchoring(FillAdaptive::Octree *adaptive_fill_octree,
        FillAdaptive::Octree *support_fill_octree,
        FillLightning::Generator* lightning_generator) const;

    void 					make_ironing();

    void                    export_region_slices_to_svg(const char *path) const;
    void                    export_region_fill_surfaces_to_svg(const char *path) const;
    // Export to "out/LayerRegion-name-%d.svg" with an increasing index with every export.
    void                    export_region_slices_to_svg_debug(const char *name) const;
    void                    export_region_fill_surfaces_to_svg_debug(const char *name) const;

    // Is there any valid extrusion assigned to this LayerRegion?
    virtual bool            has_extrusions() const { for (auto layerm : m_regions) if (layerm->has_extrusions()) return true; return false; }

    //BBS
    void simplify_wall_extrusion_path() { for (auto layerm : m_regions) layerm->simplify_wall_extrusion_entity();}
    void simplify_infill_extrusion_path() { for (auto layerm : m_regions) layerm->simplify_infill_extrusion_entity(); }
    //BBS: this function calculate the maximum void grid area of sparse infill of this layer. Just estimated value
    coordf_t get_sparse_infill_max_void_area();

    // FN_HIGHER_EQUAL: the provided object pointer has a Z value >= of an internal threshold.
    // Find the first item with Z value >= of an internal threshold of fn_higher_equal.
    // If no vec item with Z value >= of an internal threshold of fn_higher_equal is found, return vec.size()
    // If the initial idx is size_t(-1), then use binary search.
    // Otherwise search linearly upwards.
    template<typename IteratorType, typename IndexType, typename FN_HIGHER_EQUAL>
    static IndexType idx_higher_or_equal(IteratorType begin, IteratorType end, IndexType idx, FN_HIGHER_EQUAL fn_higher_equal)
    {
        auto size = int(end - begin);
        if (size == 0) {
            idx = 0;
            }
        else if (idx == IndexType(-1)) {
            // First of the batch of layers per thread pool invocation. Use binary search.
            int idx_low = 0;
            int idx_high = std::max(0, size - 1);
            while (idx_low + 1 < idx_high) {
                int idx_mid = (idx_low + idx_high) / 2;
                if (fn_higher_equal(begin[idx_mid]))
                    idx_high = idx_mid;
                else
                    idx_low = idx_mid;
                }
            idx = fn_higher_equal(begin[idx_low]) ? idx_low :
                (fn_higher_equal(begin[idx_high]) ? idx_high : size);
            }
        else {
            // For the other layers of this batch of layers, search incrementally, which is cheaper than the binary search.
            while (int(idx) < size && !fn_higher_equal(begin[idx]))
                ++idx;
            }
        return idx;
    }

protected:
    friend class PrintObject;
    friend std::vector<Layer*> new_layers(PrintObject*, const std::vector<coordf_t>&);
    friend std::string fix_slicing_errors(PrintObject* object, LayerPtrs&, const std::function<void()>&, int &);

    Layer(size_t id, PrintObject *object, coordf_t height, coordf_t print_z, coordf_t slice_z) :
        upper_layer(nullptr), lower_layer(nullptr), slicing_errors(false),
        slice_z(slice_z), print_z(print_z), height(height),
        m_id(id), m_object(object) {}
    virtual ~Layer();

//BBS: method to simplify support path
    void    simplify_support_entity_collection(ExtrusionEntityCollection* entity_collection);
    void    simplify_support_path(ExtrusionPath* path);
    void    simplify_support_multi_path(ExtrusionMultiPath* multipath);
    void    simplify_support_loop(ExtrusionLoop* loop);

private:
    // Sequential index of layer, 0-based, offsetted by number of raft layers.
    size_t              m_id;
    PrintObject        *m_object;
    LayerRegionPtrs     m_regions;
};

enum SupportInnerType {
    stInnerNormal,
    stInnerTree
};

class SupportLayer : public Layer
{
public:
    // Polygons covered by the supports: base, interface and contact areas.
    // Used to suppress retraction if moving for a support extrusion over these support_islands.
    ExPolygons                  support_islands;
    // Extrusion paths for the support base and for the support interface and contacts.
    ExtrusionEntityCollection   support_fills;
    SupportInnerType            support_type = stInnerNormal;

    // for tree supports
    ExPolygons base_areas;


    // Is there any valid extrusion assigned to this LayerRegion?
    virtual bool                has_extrusions() const { return ! support_fills.empty(); }

    // Zero based index of an interface layer, used for alternating direction of interface / contact layers.
    size_t                      interface_id() const { return m_interface_id; }

    void simplify_support_extrusion_path() { this->simplify_support_entity_collection(&support_fills); }

protected:
    friend class PrintObject;
    friend class TreeSupport;

    // The constructor has been made public to be able to insert additional support layers for the skirt or a wipe tower
    // between the raft and the object first layer.
    SupportLayer(size_t id, size_t interface_id, PrintObject *object, coordf_t height, coordf_t print_z, coordf_t slice_z) :
        Layer(id, object, height, print_z, slice_z), m_interface_id(interface_id), support_type(stInnerNormal) {}
    virtual ~SupportLayer() = default;

    size_t m_interface_id;

    // for tree support
    ExPolygons                                roof_areas;
    ExPolygons                                roof_1st_layer; // the layer just below roof. When working with PolySupport, this layer should be printed with regular material
    ExPolygons                                floor_areas;
    ExPolygons                                roof_gap_areas; // the areas in the gap between support roof and overhang
    enum AreaType { BaseType = 0, RoofType = 1, FloorType = 2, Roof1stLayer = 3 };
    struct AreaGroup
    {
        ExPolygon *area;
        int        type;
        int interface_id = 0;
        coordf_t   dist_to_top; // mm dist to top
        bool need_infill = false;
        bool need_extra_wall = false;
        AreaGroup(ExPolygon *a, int t, coordf_t d) : area(a), type(t), dist_to_top(d) {}
    };
    std::vector<AreaGroup>                    area_groups;
};

template<typename LayerContainer>
inline std::vector<float> zs_from_layers(const LayerContainer &layers)
{
    std::vector<float> zs;
    zs.reserve(layers.size());
    for (const Layer *l : layers)
        zs.emplace_back((float)l->slice_z);
    return zs;
}

extern BoundingBox get_extents(const LayerRegion &layer_region);
extern BoundingBox get_extents(const LayerRegionPtrs &layer_regions);


struct ExpansionZone {
    ExPolygons expolygons;
    Algorithm::RegionExpansionParameters parameters;
    bool expanded_into = false;
};

/**
* Extract bridging surfaces from "surfaces", expand them into "shells" using expansion_params,
* detect bridges.
* Trim "shells" by the expanded bridges.
*/
Surfaces expand_bridges_detect_orientations(
    Surfaces &surfaces,
    std::vector<ExpansionZone>& expansion_zones,
    const float closing_radius
);

/**
* Extract bridging surfaces from "surfaces", expand them into "shells" using expansion_params.
* Trim "shells" by the expanded bridges.
*/
Surfaces expand_merge_surfaces(
    Surfaces &surfaces,
    SurfaceType surface_type,
    std::vector<ExpansionZone>& expansion_zones,
    const float closing_radius,
    const double bridge_angle = -1
);

}

#endif