/*
 1 matchFaces contains matching-strategies to pair faces from source- and
 destination-regions.
 
 All strategies must have the following signature:
 
 vector<Matches> fn(vector<Face> *src, vector<Face> *dst,
                    int depth, string args);
 
 and must be registered with a name in the struct matchFacesStrategies below.

*/

#include "interpolate.h"

#include <string>


#ifdef USE_LUA

// This is the interface to Lua, the mainly used strategy.
vector<Matches> _matchFacesLua(vector<Face> *src,
        vector<Face> *dst, int depth, string args);

vector<Matches> matchFacesLua(vector<Face> *src,
        vector<Face> *dst, int depth, string args) {
    return _matchFacesLua(src, dst, depth, args);
}
#endif

/*
 1.1 ~matchFacesNull~ does not match any faces.
 Mainly for testing- and demonstration-purposes.
 
*/
vector<Matches> matchFacesNull(vector<Face> *src,
        vector<Face> *dst, int depth, string args) {
    vector<Matches> ret;

    return ret;
}

/*
 1.2 ~matchFacesSimple~ matches faces in the order they are in the list.
 Mainly for testing- and demonstration-purposes.
 
*/
vector<Matches> matchFacesSimple(vector<Face> *src,
        vector<Face> *dst, int depth, string args) {
    vector<Matches> ret;

    for (unsigned int i = 0; (i < src->size() || (i < dst->size())); i++) {
        if ((i < src->size()) && (i < dst->size())) {
            Matches p(&((*src)[i]), &((*dst)[i]));
            ret.push_back(p);
        }
    }

    return ret;
}


// Helper function for matchFacesLowerLeft below to sort a list of faces by
// their lower-(leftmost)-point
static bool sortLowerLeft(const Face& r1, const Face& r2) {
    if (r1.isEmpty())
        return true;
    else if (r2.isEmpty()) 
        return false;
    else
        return r1.v[0].s < r2.v[0].s;
}

/*
 1.3 ~matchFacesLowerLeft~ matches the faces by the lowest-(leftmost)-point.
 It is used in the evaporation-phase, when we only need to match faces
 with identical hull.
 
*/
vector<Matches> matchFacesLowerLeft(vector<Face> *src,
        vector<Face> *dst, int depth, string args) {
    vector<Matches> ret;

    // Sort the faces by their lower-(leftmost)-point which is always the first
    // point if the face is sorted correctly (which it should be!)
    std::sort(src->begin(), src->end(), sortLowerLeft);
    std::sort(dst->begin(), dst->end(), sortLowerLeft);

    // Traverse the two lists in parallel and try to find matches
    unsigned int i = 0, j = 0;
    while (i < src->size() && j < dst->size()) {

        if ((*src)[i].isEmpty()) {
            i++;
        } else if ((*dst)[j].isEmpty()) {
            j++;
        } else {
            Pt p1 = (*src)[i].v[0].s;
            Pt p2 = (*dst)[j].v[0].s;
            if (p1 == p2) {
                (*src)[i].used = 1;
                (*dst)[j].used = 1;
                ret.push_back(Matches(&(*src)[i], &(*dst)[j]));
                i++;
                j++;
            } else if (p1 < p2) {
                i++;
            } else {
                j++;
            }
        }
    }

    return ret;
}

// Helper class for matchFacesCriterion
class matchItem {
public:
    Face *s, *d;
    double val;
    
    matchItem(Face *s, Face *d, double val) : s(s), d(d), val(val) {};
    bool operator<(const matchItem& a) const { return val < a.val; }
};

// Try to find a suitable offset and scale for this set of faces.
// After transformation, the bounding box of the parent of these faces will be
// (0/0) - (SCALESIZE/SCALESIZE). If there is no parent, the common bounding box
// of all faces of the set is used.
// SCALESIZE is defined in interpolate.h.
static pair<Pt, Pt> getOffsetAndScale (vector<Face> *fcs) {
    if (fcs->empty())
        return pair<Pt,Pt>(Pt(0,0), Pt(1,1));
    Face *parent = ((*fcs)[0]).parent;
    pair<Pt, Pt> bbox, ret;
    if (parent) {
        // If we have a parent face, use its bounding box
        bbox = parent->GetBoundingBox();
    } else {
        // otherwise get the common bounding box of all faces in this set
        bbox = Face::GetBoundingBox(*fcs);
    }
    
    
    ret.first = -bbox.first;
        
    if ((bbox.second.x > bbox.first.x) &&
        (bbox.second.y > bbox.first.y)) {
        // Calculate the factor which scales the bounding box to SCALESIZE
        // (defined in interpolate.h) in each direction.
        Pt scale(SCALESIZE / (bbox.second.x - bbox.first.x),
                 SCALESIZE / (bbox.second.y - bbox.first.y));
        ret.second = scale;
    } else {
        // The factor would be invalid (FPE), so just use 1
        ret.second = Pt(1, 1);
    }
    
    return ret;
}

/*
 1.4 ~matchFacesCriterion~ is a framework for matching-strategies.
 It takes the two lists of faces and a scoring-function ~fn~, which calculates
 a score for each pair of faces. A smaller score wins over higher scores.
 Then, the results are sorted by this value and the best pairings are taken
 into the result list. An optional threshold defines the maximum score a
 pair may have to be a candidate for the result list.
 
*/
static vector<Matches> matchFacesCriterion(vector<Face> *src,
        vector<Face> *dst, int depth,
        double (*fn)(Face *src, Face *dst), double thres) {
    vector<Matches> ret;
    vector<matchItem> mtab;
    
    // Get source- and destination-transform-values
    pair<Pt, Pt> stf = getOffsetAndScale(src);
    pair<Pt, Pt> dtf = getOffsetAndScale(dst);
    
    for (unsigned int i = 0; i < src->size(); i++) {
        for (unsigned int j = 0; j < dst->size(); j++) {
            Face s = (*src)[i], d = (*dst)[j];
            s.Transform(stf.first, stf.second);
            d.Transform(dtf.first, dtf.second);
            double val = fn(&s, &d);
            if (val < thres) {
                mtab.push_back(matchItem(&((*src)[i]), &((*dst)[i]), val));
            }
        }
    }
    std::sort(mtab.begin(), mtab.end());
    std::vector<matchItem>::iterator it = mtab.begin();
    while (it != mtab.end()) {
        if (!it->s->used && !it->d->used) {
            it->s->used = 1;
            it->d->used = 1;
            ret.push_back(Matches(it->s, it->d));
        }
        it++;
    }
    
    return ret;
}

// Helper-function for matchFacesOverlap below. Calculates a score from the
// overlapping area of two faces.
static double overlap (Face *src, Face *dst) {
    Poly r1 = src->MakePoly(false);
    Poly r2 = dst->MakePoly(false);

    // Calculate the areas of the two faces
    double a1 = r1.Area();
    double a2 = r2.Area();

    // Calculate the intersection of the regions in "intersect"
    double ai = r1.IntersectionArea(r2); // Calculate the area

    // Calculate the average overlap percentage between a1 and a2
    double ret = (ai*100/a1+ai*100/a2)/2;

    // Subtract the value from 100, since matchFacesCriterion tries to minimize
    return 100-ret;
}

/*
 1.5 ~matchFacesOverlap~ uses matchFacesCriterion for matching faces by their
 overlapping area. The average overlap must be 30 percent minimum if no other
 value is given.
 
*/
static vector<Matches> matchFacesOverlap(vector<Face> *src,
        vector<Face> *dst, int depth, string args) {
    int minpercent = atoi(args.c_str());
    if ((minpercent <= 0) || (minpercent > 100))
        minpercent = 30;
    return matchFacesCriterion(src, dst, depth, overlap, (100 - minpercent));
}

#define nrMatchFacesStrategies (sizeof(matchFacesStrategies)/            \
                                sizeof(matchFacesStrategies[0]))


// Helper-Function for matchFacesDistance
static double distance (Face *src, Face *dst) {
    return src->GetMiddle().distance(dst->GetMiddle());
}

/*
 1.6 ~matchFacesDistance~ uses a distance-based scoring function. It tries
 to pair faces with low distance.
 
*/
vector<Matches> matchFacesDistance(vector<Face> *src,
        vector<Face> *dst, int depth, string args) {
    return matchFacesCriterion(src, dst, depth, distance, 1000000);
}

/*
 1.7 ~matchFacesMW~ tries to match Faces at the highest level by distance but
 then doesn't try to match concavities or holes. This is about what McKenney
 and Webb suggested (hence the name MW).
 
*/
vector<Matches> matchFacesMW(vector<Face> *src,
        vector<Face> *dst, int depth, string args) {
    if (depth == 0) {
        return matchFacesDistance(src, dst, depth, "");
    } else {
        return matchFacesNull(src, dst, depth, "");
    }
}


// Register all matching strategies in this list.
// The argument for interpolate2 must be in the form "<name>[:<paramstring>]"
// to select the function
static struct {
    string name;
    matchFaces_t fn;
} matchFacesStrategies[] = {
    //The first is also the default strategy if Lua is not compiled
    { "overlap", matchFacesOverlap },
    { "distance", matchFacesDistance },
    { "null", matchFacesNull },
    { "simple", matchFacesSimple },
    { "mw", matchFacesMW },
    { "lowerleft", matchFacesLowerLeft }
};

/*
 2 ~matchFaces~ is the interface to all matching strategies.
 It prepares the lists of faces, calls the real matching function and cleans
 up afterwards.
 
 This function is called with the two lists ~src~ and ~dst~ of source- and
 destinationfaces, the current recursionlevel ~depth~
 and the string-argument which configures the matching-strategy. It returns
 the pairs of faces, which should be interpolated with each other.
 
 The args-string should be in this form:  "<name>[:<paramstring>]"
 
 paramstring could be also composed from several parameters, for example
 "<arg1>,<arg2>,...,<argn>", but it is the responsibility of the matching
 function to parse that.
 
 where "name" is searched in the strategies above and the corresponding
 function is called with the name stripped from the args-string.
 
 If "name" is not found and Lua is compiled, then call Lua with the full
 args-string. If Lua is not compiled, use the first strategy in the
 list above as the default-strategy.
 
*/
vector<Matches> matchFaces(
        vector<Face> *src, vector<Face> *dst, int depth,
        string args) {
    vector<Matches> pairs, ret;
    
    // Mark all faces as unused and if they are from the source- or
    // destination-set.
    for (unsigned int i = 0; i < src->size(); i++) {
        (*src)[i].used = 0;
        (*src)[i].isdst = 0;
    }
    for (unsigned int i = 0; i < dst->size(); i++) {
        (*dst)[i].used = 0;
        (*dst)[i].isdst = 1;
    }

    // Try to find the matching-strategy defined in the argument-string.
    matchFaces_t fn = NULL;
    string fname = args, fargs = "";
    size_t pos = fname.find(':');   // Find the index of the colon
    if (pos != string::npos) {
        // Split it into name and params, if a colon is present
        fname = args.substr(0, pos);
        fargs = args.substr(pos+1, string::npos);
    } else {
        // Otherwise the argument string consists only of the name (we assume)
        fname = args;
    }
    
    for (unsigned int i = 0; i < nrMatchFacesStrategies; i++) {
        if (matchFacesStrategies[i].name == fname) {
            fn = matchFacesStrategies[i].fn;
            break;
        }
    }
    
    if (fn) {
        // If we have found a matching function, call it here
        pairs = fn(src, dst, depth, fargs);
    } else {
        // Otherwise use a default strategy
#ifdef USE_LUA
        // which is Lua, if it is compiled
        pairs = matchFacesLua(src, dst, depth, args);
#else
        // or the first strategy in the list otherwise
        pairs = matchFacesStrategies[0].fn(src, dst, depth, fargs);
#endif
    }

    // The function above may have used the ~used~-attribute, so reset it
    for (unsigned int i = 0; i < src->size(); i++) {
        (*src)[i].used = 0;
    }
    for (unsigned int i = 0; i < dst->size(); i++) {
        (*dst)[i].used = 0;
    }

    // Put all sane pairs of faces into the return-list
    for (unsigned int i = 0; i < pairs.size(); i++) {
        // Ignore a pair if: one partner is NULL, already used or from the
        // wrong set
        if (!pairs[i].isValid()) {
            DEBUG(3, "Found invalid pair!");
            continue;
        }
        // This pairing seems ok, mark the members as used 
        pairs[i].markUsed();
        ret.push_back(pairs[i]); // and put it into the list
    }

    // All faces left are not in a real pairing, put them into the list
    // without a partner
    for (unsigned int i = 0; i < src->size(); i++) {
        if (!(*src)[i].used) {
            ret.push_back(Matches(&(*src)[i], NULL));
        }
    }
    for (unsigned int i = 0; i < dst->size(); i++) {
        if (!(*dst)[i].used) {
            ret.push_back(Matches(NULL, &(*dst)[i]));
        }
    }

    return ret;
}