/* 
 1 interpolate.h is the main include file for the RegionInterpolation2Algebra.
 All classes and functions are declared here.

*/

#ifndef INTERPOLATE_HXX
#define INTERPOLATE_HXX

#include <string>
#include <vector>
#include <set>
#include <cassert>
#include <sstream>
#include <cmath>
#include <iostream>
#include <algorithm>

#include "config.h"
#include "librip.h"

#define DEBUG(l,m) do { if (l <= DEBUGLEVEL) { cerr << m << endl; } } while (0)

#if defined(LUA5_1) || defined(LUA5_2)
#define USE_LUA
#define LUA_FUNCTION(FNAME) int luafunc_ ## FNAME(lua_State *L)
#define LUA_ADD_FUNCTION(FNAME) lua_pushcfunction(L, luafunc_ ## FNAME); \
                                lua_setglobal(L, #FNAME)
#endif


// Forward-declarations of the classes
class Pt;
class Seg;
class Face;
class MSeg;
class MSegs;
class MFace;
class MFaces;
class Poly;

class Interval { // a time interval
public:
    double start; // start point in ms since epoch
    double end;   // end point in ms since epoch
    bool lc;      // left-closed interval?
    bool rc;      // right-closed interval?
    
    Interval(double start, double end, bool lc, bool rc) : 
             start(start), end(end), lc(lc), rc(rc) {};
    Interval(string start, string end, bool lc, bool rc);
    Interval() : start(0), end(0), lc(true), rc(true) {};
    string startstr(); // start in YYYY-mm-dd-HH:MM:ss.SSS
    string endstr();   // end   in YYYY-mm-dd-HH:MM:ss.SSS
};


class Pt { // a point
public:
    // Fields
    double x, y;
    int valid;
    long double angle, dist;

    //Constructors
    Pt();
    Pt(double x, double y);
    
    // Operators
    bool operator<(const Pt& a) const;
    bool operator==(const Pt& a) const;
    Pt operator-(const Pt& a) const;
    Pt operator-() const; // Unary minus
    Pt operator+(const Pt& a) const;
    Pt operator/(double a) const;
    Pt operator*(const Pt& a) const;
    
    // Methods
    bool lessPolar(const Pt& a) const;  // comparison by polar angle/distance
    void calcPolar(const Pt& pt); // calculates polar coordinates with origin p
    double distance(Pt p); // calculates the distance to p
    string ToString() const;
    
    // Static functions
    static double sign(const Pt& a, const Pt& b, const Pt& c); // checks order
    static bool insideTriangle(const Pt& a, const Pt& b, const Pt& c,
            const Pt& x); // checks if x is inside the triangle (a b c)
};

class Seg { // a segment
public:
    // Fields
    Pt s, e;    // start- and endpoint
    int valid;

    // Constructors
    Seg();
    Seg(Pt s, Pt e);
    
    // Operators
    bool operator==(const Seg& a) const;
    bool operator<(const Seg& a) const;
    
    // Methods
    long double angle() const; // calculates angle with x-axis
    void ChangeDir(); // changes the direction of the segment
    bool intersects(const Seg& seg) const; // checks for intersection with seg
    string ToString() const;
};

class Face { // a face
private:
    int cur;

public:
    // Fields
    vector<Seg> v; // the segments of this face in ccw-order (start lower-left)
    vector<Face> holes; // the list holes of this face
    vector<Seg> convexhull; // the convex hull
    Face *parent; // the parent face of this face
    Pt peerPoint; // point on a peer-face to collapse to
    Seg hullSeg; // segment on hull of the parent face if this is a concavity
    bool ishole; // true if this face is a hole in another face
    int used; // used by matchFaces if this face was paired with another face
    int isdst; // is this face from the source- or destination-region
    pair<Pt, Pt> bbox; // bounding-box of this face

    // Constructors
    Face();
    Face(RList le, bool withHoles);   // Construct from RList
    Face(vector<Seg> v); // Construct from list of segments
    
    // Methods
    void AddSeg(Seg a); // Add a new segment
    void Close();       // Close the face
    Face ConvexHull();  // Calculate the convex hull
    Seg Begin(); // Traversal: Go to first segment
    Seg Next();  // Traversal: Advance one segment
    Seg Prev();  // Traversal: Go back one segment
    Seg Cur();   // Traversal: Get the current segment
    bool End();  // Traversal: Check if we are past the last segment
    void Sort(); // Sort the segments (start lower-left, counterclockwise)
    vector<Pt> getPoints(); // Get the list of corner points in correct order
    pair<Pt, Pt> GetBoundingBox(); // Get the bounding box of this face
    Pt GetMiddle(); // Get the center of the bounding box
    Pt GetCentroid(); // Calculate the centroid of this face
    MSegs collapse(bool close); // collapse the face
    MSegs collapse(bool close, Pt dst); // collapse the face to a given point
    MFace collapseWithHoles(bool close); // include the holes when collapsing
    Pt collapsePoint(); // Determine the best collapse point for this face
    MSegs GetMSegs(bool triangles, Pt off); // convert to a static moving face
    MSegs GetMSegs(bool triangles); // convert to a static moving face
    MFace GetMFace(bool triangles, Pt off); // convert to a static moving face
    MFace GetMFace(bool triangles); // convert to a static moving face
    double distance(Face r); // calculate the distance of the middle points
    double GetArea(); // calculate the area of this face
    Face ClipEar();  // Clip an ear for triangulation
    vector<MSegs> Evaporate(bool close); // calculate evaporation-msegs
    void AddHole (Face hole); // Add a new hole to this face
    bool isEmpty() const; // Check, if this is an empty face
    bool Check(); // Check, if this face is valid
    void IntegrateHoles(); // Integrate holes into the cycle for triangulation
    void Transform (Pt off, Pt scale); // Transform by offset and scale factor
    bool Merge (Face m); // Merge two adjacent faces into one
    string ToString() const;
    Poly MakePoly (double offx, double offy, double scalex, double scaley,
                   bool withholes);
    Poly MakePoly (bool withholes);
    Pt findX (double x); // Find first point with specified x-coordinate
    Pt findY (double Y); // Find first point with specified y-coordinate

    // Static functions
    static vector<Face> getFaces(RList le); // Get faces from RList
    static pair<Pt, Pt> GetBoundingBox(vector<Face> faces);
    static pair<Pt, Pt> GetBoundingBox(std::set<Face*> faces);
    static vector<Seg> sortSegs(vector<Seg> v); // Sort segs to a cycle
    static MFaces CreateMFaces(vector<Face> *faces);
};

class MSeg { // a moving segment
public:
    // Fields
    Pt is, ie, fs, fe; // Points of initial and final segment
    vector<Pt> ip, fp; // Intermediary points if MSeg was merged

    // Constructors
    MSeg();
    MSeg(Pt is, Pt ie, Pt fs, Pt fe); // Construct from segments' endpoints
    
    // Operators
    bool operator==(const MSeg& a) const;
    bool operator<(const MSeg& a) const;
    
    // Methods
    bool intersects(const MSeg& a, bool checkSegs) const;
    bool Merge(const MSeg& a); // Merge two MSegs if collinear
    bool Split(MSeg& n, MSeg& m1, MSeg& m2); // Split MSeg on "n"
    void ChangeDirection(); // Change the orientation
    MSeg divide(double start, double end); // restrict interval
    void reverse(); // Swap initial and final segment of this moving segment 
    string ToString() const;
};

class MSegs { // a set of moving segments
public:
    // Fields
    vector<MSeg> msegs; // the msegs which make up a cycle
    Face sreg, dreg; // the faces from which this msegs were calculated
    int iscollapsed; // >0 if the face collapses or expands
    int isevaporating; // >0 if the face evaporates
    pair<Pt,Pt> bbox; // corner-points of the bounding box

    // Constructor
    MSegs();
    
    // Methods
    void AddMSeg(MSeg m); // Add a new MSeg to the cycle
    bool MergeConcavity(MSegs c); // Merge a concavity cycle if possible
    void updateBBox(MSeg& seg); // Update the bounding box after adding seg
    pair<Pt, Pt> calculateBBox(); // Calculate the bounding box
    Face CreateBorderFace(bool initial); // Create static mface from border
    int findNext(int index, bool check); // get successor of segment at index
    int findNext(MSeg cur, int start, bool check); // get successor of cur
    MSegs divide(double start, double end); // restrict the interval
    pair<MSegs, MSegs> kill(); // create pair of expanding/collapsing faces
    bool intersects(const MSegs& a, bool matchIdent, bool matchSegs) const;
    void reverse(); // Swaps the initial and final segment of this set
    string ToString() const;
    
};

class MFace { // a complete cycle of moving segments aka moving face
public:
    // Fields
    MSegs face; // the moving segments which make up this face
    bool needStartRegion, needEndRegion; // this face needs a start/end-region
    vector<MSegs> holes; // list of holes
    vector<MFace> cvs; // list of pending concavities
    pair<Pt, Pt> bbox; // the bounding box of this mface
    int half;

    // Constructors
    MFace();
    MFace(MSegs face); // Construct from an MSegs-object
    
    // Methods
    bool Check();                // Check if this MFace is a valid cycle
    bool SortCycle();            // Sort this cycle
    vector<MFace> SplitCycle(); // Sort and split this cycle if possible
    void EliminateSpikes();      // Eliminate empty spikes after merge
    void AddConcavity(MFace c);  // Add a concavity to this cycle
    vector<MFace> MergeConcavities();  // Merge previously added concavities
    RList ToListExpr();       // Create a list expression
    MFace divide(double start, double end); // restrict the interval
    Face CreateBorderFace(bool src); // get face from border of the interval
    void PrintMRegionListExpr(); // Output list expression for debugging
    bool isEmpty(); // Check, if this is an empty mface
    void reverse(); // Swaps the initial and final segment of this moving face
    string ToString();
};

class MFaces { // a set of moving faces
public:
    // Fields
    vector<MFace> faces; // List of mface-objects
    vector<Face> *sregs, *dregs; // lists of faces from which it was created
    bool needSEvap, needDEvap; // evaporation- or condensation-phase is needed

    // Constructor
    MFaces();
    MFaces(MFace face);
    
    // Methods
    void AddMFace(MFace face); // Add a new mface to this mfaces-object
    RList ToListExpr(Interval iv, double start, double end, int half);
    RList ToMListExpr(Interval iv); // create RList-Expressions
    MFaces divide(double start, double end); // restrict the interval
    vector<Face> CreateBorderFaces(bool src); // create faces from border
    MFaces CreateBorderMFaces(bool src); // create static mfaces from border
    string ToString();
    
    // Static functions
    static RList fallback(vector<Face> *s, vector<Face> *d, Interval iv);
};

class RotatingPlane { // the rotating plane algorithm
public:
    // Fields
    MFace mface; // mface created by rotating plane algorithm
    vector<Face> scvs, dcvs; // source- and destination-concavity

    // Constructor (this constructor already does all the work)
    RotatingPlane(Face *src, Face *dst, int depth, bool evap);
};

class Matches {
public:
    vector<Face *> src;
    vector<Face *> dst;

    Matches();
    Matches(Face *s, Face *d);
    bool isValid();
    void markUsed();
    Face* srcface();
    Face* dstface();
};

vector<MFace> MergeFaces (Matches& m);

// Function prototypes

MFaces interpolate(vector<Face> *sregs, vector<Face> *dregs, int depth,
        bool evap, string args);

vector<Matches> matchFaces(
        vector<Face> *src, vector<Face> *dst, int depth,
        string args);

typedef vector<Matches> (*matchFaces_t)(vector<Face> *src,
        vector<Face> *dst, int depth, string args);

// Prototypes of the matchFaces-strategies
vector<Matches> matchFacesSimple(vector<Face> *src,
        vector<Face> *dst, int depth, string args);
vector<Matches> matchFacesNull(vector<Face> *src,
        vector<Face> *dst, int depth, string args);
vector<Matches> matchFacesLowerLeft(vector<Face> *src,
        vector<Face> *dst, int depth, string args);
vector<Matches> matchFacesDistance(vector<Face> *src,
        vector<Face> *dst, int depth, string args);
vector<Matches> matchFacesLua(vector<Face> *src,
        vector<Face> *dst, int depth, string args);

#include "poly2.h"

#endif /* INTERPOLATE_HXX */