/*
Copyright 2012-2022 Ronald Römer

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.
*/

#ifndef __vtkPolyDataBooleanFilter_h
#define __vtkPolyDataBooleanFilter_h

#include <vector>
#include <deque>
#include <map>
#include <set>
#include <utility>
#include <iostream>

#include <vtkPolyDataAlgorithm.h>
#include <vtkKdTree.h>
#include <vtkModifiedBSPTree.h>

#include "Utilities.h"

#define OPER_NONE 0
#define OPER_UNION 1
#define OPER_INTERSECTION 2
#define OPER_DIFFERENCE 3
#define OPER_DIFFERENCE2 4

enum class Capt {
    NOT,
    EDGE,
    A,
    B
};

enum class Side {
    NONE,
    START,
    END
};

enum class Loc {
    NONE,
    INSIDE,
    OUTSIDE
};

class StripPt {
public:
    StripPt () : t(0), capt(Capt::NOT), catched(true) {
        edge[0] = NOTSET;
        edge[1] = NOTSET;
    }

    double t;
    Capt capt;
    double captPt[3];

    vtkIdType ind, edge[2];

    double pt[3];
    double cutPt[3];

    friend std::ostream& operator<< (std::ostream &out, const StripPt &s) {
        out << "ind " << s.ind
            << ", edge [" << s.edge[0] << ", " << s.edge[1] << "]"
            << ", t " << s.t
            << ", capt " << s.capt
            << ", polyId " << s.polyId;
        return out;
    }

    std::vector<Pair> history;

    vtkIdType polyId;

    bool catched;
};

class StripPtR {
public:
    StripPtR () = delete;

    StripPtR (vtkIdType ind, std::size_t strip) : ind(ind), strip(strip), ref(NOTSET), side(Side::NONE) {
        desc[0] = NOTSET;
        desc[1] = NOTSET;
    }

    vtkIdType ind;
    std::size_t strip;
    vtkIdType ref, desc[2];
    Side side;

    friend std::ostream& operator<< (std::ostream &out, const StripPtR &s) {
        out << "ind " << s.ind
            << ", desc [" << s.desc[0] << ", " << s.desc[1] << "]"
            << ", strip " << s.strip
            << ", side " << s.side
            << ", ref " << s.ref;
        return out;
    }
};

typedef std::map<vtkIdType, StripPt> StripPtsType;
typedef std::deque<StripPtR> StripType;
typedef std::vector<StripType> StripsType;

class PStrips {
public:
    PStrips (vtkPolyData *pd, vtkIdType cellId) {
        const vtkIdType *cell;
        vtkIdType numPts;

        pd->GetCellPoints(cellId, numPts, cell);

        for (vtkIdType i = 0; i < numPts; i++) {
            poly.push_back(cell[i]);
        }

        ComputeNormal(pd->GetPoints(), n, numPts, cell);

        base = Base(pd->GetPoints(), numPts, cell);
    }

    StripPtsType pts;
    StripsType strips;

    double n[3];
    IdsType poly;
    Base base;
};

typedef std::map<vtkIdType, PStrips> PolyStripsType;

typedef std::vector<std::reference_wrapper<StripPtR>> RefsType;

// Merger

typedef std::vector<std::size_t> GroupType;

typedef std::map<vtkIdType, std::size_t> SourcesType;

class Conn {
public:
    Conn () = delete;
    Conn (double d, vtkIdType i, vtkIdType j) : d(d), i(i), j(j) {}

    double d;
    vtkIdType i, j;

    bool operator< (const Conn &other) const {
        return d < other.d;
    }

    friend std::ostream& operator<< (std::ostream &out, const Conn &c) {
        out << "Conn(d=" << c.d
            << ", i=" << c.i
            << ", j=" << c.j
            << ")";
        return out;
    }

};

struct ConnCmp {
    bool operator() (const Conn &a, const Conn &b) const {
        return std::tie(a.i, a.j) < std::tie(b.i, b.j);
    }
};

typedef std::vector<Conn> ConnsType;
typedef std::map<std::size_t, ConnsType> PolyConnsType;

inline std::ostream& operator<< (std::ostream &out, const PolyConnsType& polyConns) {
    PolyConnsType::const_iterator itr;

    for (itr = polyConns.begin(); itr != polyConns.end(); ++itr) {
        out << itr->first << ": [";
        for (auto &conn : itr->second) {
            out << conn << ", ";
        }
        out << "]" << std::endl;
    }

    return out;
}

class Prio {
public:
    Prio () = delete;
    Prio (const Conn &conn, const std::set<std::size_t> &solvable, double d) : conn(conn), solvable(solvable), d(d) {}

    Conn conn;
    std::set<std::size_t> solvable;
    double d;

    friend std::ostream& operator<< (std::ostream &out, const Prio &p) {
        out << "Prio(conn=" << p.conn
            << ", d=" << p.d
            << ")";
        return out;
    }
};

struct Cmp {
    bool operator() (const Prio &a, const Prio &b) const {
        const auto _a = a.solvable.size(),
            _b = b.solvable.size();
        return std::tie(_a, a.d) < std::tie(_b, b.d);
    }
};

typedef std::set<Prio, Cmp> PriosType;

typedef std::map<std::size_t, Prio> PolyPriosType;

class Merger {
    vtkPolyData *pd;
    const PStrips &pStrips;
    vtkIdType origId;

    PolysType polys;
public:
    Merger (vtkPolyData *pd, const PStrips &pStrips, const StripsType &strips, const IdsType &descIds, vtkIdType origId);
    void Run ();

private:
    void MergeGroup (const GroupType &group, PolysType &merged);
    bool FindConns (vtkPolyData *lines, vtkSmartPointer<vtkKdTree> kdTree, vtkSmartPointer<vtkModifiedBSPTree> bspTree, PolyConnsType &polyConns, const IndexedPolysType &indexedPolys, const SourcesType &sources, int &n);
};

class VTK_EXPORT vtkPolyDataBooleanFilter : public vtkPolyDataAlgorithm {
    vtkPolyData *resultA, *resultB, *resultC;

    vtkSmartPointer<vtkPolyData> modPdA, modPdB, contLines;

    vtkSmartPointer<vtkCellData> cellDataA, cellDataB;
    vtkSmartPointer<vtkIdTypeArray> cellIdsA, cellIdsB;

    vtkIdTypeArray *contsA, *contsB;

    unsigned long timePdA, timePdB;

    PolyStripsType polyStripsA, polyStripsB;

    void GetStripPoints (vtkPolyData *pd, vtkIdTypeArray *sources, PStrips &pStrips, IdsType &lines);
    bool GetPolyStrips (vtkPolyData *pd, vtkIdTypeArray *conts, vtkIdTypeArray *sources, PolyStripsType &polyStrips);
    void RemoveDuplicates (IdsType &lines);
    void CompleteStrips (PStrips &pStrips);
    bool HasArea (const StripType &strip) const;
    bool CutCells (vtkPolyData *pd, PolyStripsType &polyStrips);
    void RestoreOrigPoints (vtkPolyData *pd, PolyStripsType &polyStrips);
    void DisjoinPolys (vtkPolyData *pd, PolyStripsType &polyStrips);
    void ResolveOverlaps (vtkPolyData *pd, vtkIdTypeArray *conts, PolyStripsType &polyStrips);
    void AddAdjacentPoints (vtkPolyData *pd, vtkIdTypeArray *conts, PolyStripsType &polyStrips);
    void MergePoints (vtkPolyData *pd, PolyStripsType &polyStrips);
    bool CombineRegions ();

    int OperMode;

public:
    vtkTypeMacro(vtkPolyDataBooleanFilter, vtkPolyDataAlgorithm);
    static vtkPolyDataBooleanFilter* New ();

    vtkSetClampMacro(OperMode, int, OPER_NONE, OPER_DIFFERENCE2);
    vtkGetMacro(OperMode, int);

    void SetOperModeToNone () { OperMode = OPER_NONE; Modified(); }
    void SetOperModeToUnion () { OperMode = OPER_UNION; Modified(); }
    void SetOperModeToIntersection () { OperMode = OPER_INTERSECTION; Modified(); }
    void SetOperModeToDifference () { OperMode = OPER_DIFFERENCE; Modified(); }
    void SetOperModeToDifference2 () { OperMode = OPER_DIFFERENCE2; Modified(); }

protected:
    vtkPolyDataBooleanFilter ();
    ~vtkPolyDataBooleanFilter ();

    int ProcessRequest (vtkInformation *request, vtkInformationVector **inputVector, vtkInformationVector *outputVector) override;

    void PrintSelf (ostream&, vtkIndent) override {};

private:
    vtkPolyDataBooleanFilter (const vtkPolyDataBooleanFilter&) = delete;
    void operator= (const vtkPolyDataBooleanFilter&) = delete;

};

#endif