/* @Description: FuzzyWuzzy alghoritm in Salesforce (Support InvocableMethod)
 * @Author: munawirrahman => munawirrahman@gmail.com
 * @Credits: 
 * xdrop (part of the code, ported from: https://github.com/xdrop/fuzzywuzzy)
 * seatgeek
 * Adam Cohen
 * David Necas (python-Levenshtein)
 * Mikko Ohtamaa (python-Levenshtein)
 * Antti Haapala (python-Levenshtein)
 * Tobias Burdow (burdoto)
 * visit munawirrahman.medium.com for more cool stuffs!
*/

public class FuzzyWuzzy {
//Start of Invocable Support
    public class Request {
        @InvocableVariable(label='String01' required=True description='1st String to Compare')
        public String String01;
        @InvocableVariable(label='String02' required=True description='2nd String to Compare')
        public String String02;
        @InvocableVariable(label='FuzzyWuzzy Logic' required=True description='SimpleRatio or PartialRatio')
        public String FuzzyWuzzy_logic;
    }
    public class Response {
        @InvocableVariable(label='Score')
        public Integer Score;
    }
    @invocableMethod(label='FuzzyWuzzy Scoring' )
    public static List<Response> execute (List<Request> requests) {
        List<Response> responseList = new List<Response>();
        for (Request curRequest : requests) {
            Response response = new Response();
            if(curRequest.FuzzyWuzzy_logic=='SimpleRatio'){response.Score=SimpleRatio(curRequest.String01,curRequest.String02);}
            else if(curRequest.FuzzyWuzzy_logic=='PartialRatio'){response.Score=PartialRatio(curRequest.String01,curRequest.String02);}
            else{response.Score=Null;}
            responseList.add(response);
        }
        return responseList;
    }
    
// Start of constructs
    public class EditOp {
        public EditType type;
        public Integer spos; // source block pos
        public Integer dpos; // destination block pos
    }
    public enum EditType {EQUAL,REPLACE,KEEP,INSRT,DLT}
    
    public class MatchingBlock {
        public Integer spos;
        public Integer dpos;
        public Integer length;
	}
    public class OpCode {
        public EditType type;
        public Integer sbeg, send;
        public Integer dbeg, dend;
	}
    
// Start of levenshtein algo
    public static EditOp[] getEditOps(String s1, String s2) {
        return getEditOps(s1.length(), s1, s2.length(), s2);
    }
    private static EditOp[] getEditOps(Integer len1, String s1, Integer len2, String s2) {
        Integer len1o, len2o;
        Integer i;
        Integer[] matrix;
        String[] c1 = s1.split('');
        String[] c2 = s2.split('');

        Integer p1 = 0;
        Integer p2 = 0;

        len1o = 0;

        while (len1 > 0 && len2 > 0 && c1[p1].equals(c2[p2])) {
            len1--;
            len2--;

            p1++;
            p2++;

            len1o++;
        }

        len2o = len1o;

        /* strip common suffix */
        while (len1 > 0 && len2 > 0 && c1[p1 + len1 - 1].equals(c2[p2 + len2 - 1])) {
            len1--;
            len2--;
        }

        len1++;
        len2++;

        matrix = new Integer[len2 * len1];

        for (i = 0; i < len2; i++)
            matrix[i] = i;
        for (i = 1; i < len1; i++)
            matrix[len2 * i] = i;

        for (i = 1; i < len1; i++) {

            Integer ptrPrev = (i - 1) * len2;
            Integer ptrC = i * len2;
            Integer ptrEnd = ptrC + len2 - 1;

            String String1 = c1[p1 + i - 1];
            Integer ptrString2 = p2;

            Integer x = i;

            ptrC++;

            while (ptrC <= ptrEnd) {

                Integer c3 = matrix[ptrPrev++] + (String1 != c2[ptrString2++] ? 1 : 0);
                x++;

                if (x > c3) {
                    x = c3;
                }

                c3 = matrix[ptrPrev] + 1;

                if (x > c3) {
                    x = c3;
                }

                matrix[ptrC++] = x;

            }

        }


        return editOpsFromCostMatrix(len1, c1, p1, len1o, len2, c2, p2, len2o, matrix);
    }
    
    private static EditOp[] editOpsFromCostMatrix(Integer len1, String[] c1, Integer p1, Integer o1,
                                                  Integer len2, String[] c2, Integer p2, Integer o2,
                                                  Integer[] matrix) {

        Integer i, j, pos;

        Integer ptr;

        EditOp[] ops;

        Integer dir = 0;

        pos = matrix[len1 * len2 - 1];

        ops = new EditOp[pos];

        i = len1 - 1;
        j = len2 - 1;

        ptr = len1 * len2 - 1;

        while (i > 0 || j > 0) {

            if (i != 0 && j != 0 && matrix[ptr] == matrix[ptr - len2 - 1]
                    && c1[p1 + i - 1] == c2[p2 + j - 1]) {

                i--;
                j--;
                ptr -= len2 + 1;
                dir = 0;

                continue;

            }

            if (dir < 0 && j != 0 && matrix[ptr] == matrix[ptr - 1] + 1) {

                EditOp eop = new EditOp();

                pos--;
                ops[pos] = eop;
                eop.type = EditType.INSRT;
                eop.spos = i + o1;
                eop.dpos = --j + o2;
                ptr--;

                continue;
            }

            if (dir > 0 && i != 0 && matrix[ptr] == matrix[ptr - len2] + 1) {

                EditOp eop = new EditOp();

                pos--;
                ops[pos] = eop;
                eop.type = EditType.DLT;
                eop.spos = --i + o1;
                eop.dpos = j + o2;
                ptr -= len2;

                continue;

            }

            if (i != 0 && j != 0 && matrix[ptr] == matrix[ptr - len2 - 1] + 1) {

                pos--;

                EditOp eop = new EditOp();
                ops[pos] = eop;

                eop.type = EditType.REPLACE;
                eop.spos = --i + o1;
                eop.dpos = --j + o2;

                ptr -= len2 + 1;
                dir = 0;
                continue;

            }

            if (dir == 0 && j != 0 && matrix[ptr] == matrix[ptr - 1] + 1) {

                pos--;
                EditOp eop = new EditOp();
                ops[pos] = eop;
                eop.type = EditType.INSRT;
                eop.spos = i + o1;
                eop.dpos = --j + o2;
                ptr--;
                dir = -1;

                continue;
            }

            if (dir == 0 && i != 0 && matrix[ptr] == matrix[ptr - len2] + 1) {
                pos--;
                EditOp eop = new EditOp();
                ops[pos] = eop;

                eop.type = EditType.DLT;
                eop.spos = --i + o1;
                eop.dpos = j + o2;
                ptr -= len2;
                dir = 1;
                continue;
            }

        }

        return ops;
	}
    
    public static MatchingBlock[] getMatchingBlocks(String s1, String s2) {
		return getMatchingBlocks(s1.length(), s2.length(), getEditOps(s1, s2));
    }
    private static MatchingBlock[] getMatchingBlocks(Integer len1, Integer len2, EditOp[] ops) {
        Integer n = ops.size();
        Integer numberOfMatchingBlocks, i, spos, dpos;
        numberOfMatchingBlocks = 0;
        Integer o = 0;
        spos = dpos = 0;
        EditType type;
        for (i = n; i != 0; ) {
            while (ops[o].type == EditType.KEEP && --i != 0) {
                o++;
            }

            if (i == 0)
                break;

            if (spos < ops[o].spos || dpos < ops[o].dpos) {

                numberOfMatchingBlocks++;
                spos = ops[o].spos;
                dpos = ops[o].dpos;

            }

            type = ops[o].type;

            switch on type {
                when REPLACE{
                    do {
                        spos++;
                        dpos++;
                        i--;
                        o++;
                    } while (i != 0 && ops[o].type == type &&
                            spos == ops[o].spos && dpos == ops[o].dpos);
                    break;
                }

                when DLT{
                    do {
                        spos++;
                        i--;
                        o++;
                    } while (i != 0 && ops[o].type == type &&
                            spos == ops[o].spos && dpos == ops[o].dpos);
                    break;
                }

                when INSRT{
                    do {
                        dpos++;
                        i--;
                        o++;
                    } while (i != 0 && ops[o].type == type &&
                            spos == ops[o].spos && dpos == ops[o].dpos);
                    break;
                }

                when else{
                    break;
                }
            }
        }

        if (spos < len1 || dpos < len2) {
            numberOfMatchingBlocks++;
        }

        MatchingBlock[] matchingBlocks = new MatchingBlock[numberOfMatchingBlocks + 1];

        o = 0;
        spos = dpos = 0;
        Integer mbIndex = 0;


        for (i = n; i != 0; ) {

            while (ops[o].type == EditType.KEEP && --i != 0)
                o++;

            if (i == 0)
                break;

            if (spos < ops[o].spos || dpos < ops[o].dpos) {
                MatchingBlock mb = new MatchingBlock();

                mb.spos = spos;
                mb.dpos = dpos;
                mb.length = ops[o].spos - spos;
                spos = ops[o].spos;
                dpos = ops[o].dpos;

                matchingBlocks[mbIndex++] = mb;

            }

            type = ops[o].type;

            switch on type {
                when REPLACE{
                    do {
                        spos++;
                        dpos++;
                        i--;
                        o++;
                    } while (i != 0 && ops[o].type == type &&
                            spos == ops[o].spos && dpos == ops[o].dpos);
                    break;
                }

                when DLT{
                    do {
                        spos++;
                        i--;
                        o++;
                    } while (i != 0 && ops[o].type == type &&
                            spos == ops[o].spos && dpos == ops[o].dpos);
                    break;
                }

                when INSRT{
                    do {
                        dpos++;
                        i--;
                        o++;
                    } while (i != 0 && ops[o].type == type &&
                            spos == ops[o].spos && dpos == ops[o].dpos);
                    break;
                }

                when else{
                    break;
                }
            }
        }

        if (spos < len1 || dpos < len2) {
            //System.assertEquals(len1 - spos, len2 - dpos);

            MatchingBlock mb = new MatchingBlock();
            mb.spos = spos;
            mb.dpos = dpos;
            mb.length = len1 - spos;

            matchingBlocks[mbIndex++] = mb;
        }
		System.assertEquals(numberOfMatchingBlocks, mbIndex);

        MatchingBlock finalBlock = new MatchingBlock();
        finalBlock.spos = len1;
        finalBlock.dpos = len2;
        finalBlock.length = 0;

        matchingBlocks[mbIndex] = finalBlock;


        return matchingBlocks;
    }
        
    public static Integer levEditDistance(String s1, String s2, Integer xcost) {
        Integer i;
        Integer half;
        String[] c1 = s1.split('');
        String[] c2 = s2.split('');
        System.debug('C1 IS: '+ c1);
        System.debug('C2 IS: '+ c2);
        Integer str1 = 0;
        Integer str2 = 0;
        Integer len1 = s1.length();
        Integer len2 = s2.length();
        /* strip common prefix */
        while (len1 > 0 && len2 > 0 && c1[str1].equals(c2[str2])) {
            len1--;
            len2--;
            str1++;
            str2++;
        }
        /* strip common suffix */
        while (len1 > 0 && len2 > 0 && c1[str1 + len1 - 1].equals(c2[str2 + len2 - 1])) {
            len1--;
            len2--;
        }
          /* catch trivial cases */
        if (len1 == 0)
            return len2;
        if (len2 == 0)
            return len1;
        /* make the inner cycle (i.e. str2) the longer one */
        if (len1 > len2) {
            Integer nx = len1;
            Integer temp = str1;
            len1 = len2;
            len2 = nx;
            str1 = str2;
            str2 = temp;
            String[] t = c2;
            c2 = c1;
            c1 = t;
        }
        /* check len1 == 1 separately */
        if (len1 == 1) {
            if (xcost != 0) {
                return len2 + 1 - 2 * memchr(c2, str2, c1[str1], len2);
            }
        }
        len1++;
        len2++;
        half = len1 >> 1;
        Integer[] row = new Integer[len2];
        Integer ending = len2 - 1;
        for (i = 0; i < len2 - (xcost != 0 ? 0 : half); i++)
            row[i] = i;
        /* go through the matrix and compute the costs.  yes, this is an extremely
         * obfuscated version, but also extremely memory-conservative and relatively
         * fast.  */
        if (xcost != 0) {
            for (i = 1; i < len1; i++) {
                Integer p = 1;
                String ch1 = c1[str1 + i - 1];
                Integer c2p = str2;
                Integer D = i;
                Integer x = i;
                while (p <= ending) {
                    if (ch1.equals(c2[c2p++])) {
                        x = --D;
                    } else {
                        x++;
                    }
                    D = row[p];
                    D++;

                    if (x > D)
                        x = D;
                    row[p++] = x;
                }
            }
        }
        i = row[ending];
        return i;
    }
	private static Integer memchr(String[] haystack, Integer offset, String needle, Integer num) {
        if (num != 0) {
            Integer p = 0;
            do {
                if (haystack[offset + p].equals(needle))
                    return 1;
                p++;
            } while (--num != 0);
        }
        return 0;
    }
    public static double getRatio(String s1, String s2) {
        Integer len1 = s1.length();
        Integer len2 = s2.length();
        Integer lensum = len1 + len2;
        Integer editDistance = levEditDistance(s1, s2, 1);
        return (lensum - editDistance) / (double) lensum;

    }
    public static Integer SimpleRatio(String s1, String s2) {
        return (Integer) Math.round(100 * getRatio(s1, s2));
    }
    public static Integer PartialRatio(String s1, String s2) {
        String shorter;
        String longer;

        if (s1.length() < s2.length()){

            shorter = s1;
            longer = s2;

        } else {

            shorter = s2;
            longer = s1;

        }

        MatchingBlock[] matchingBlocks = getMatchingBlocks(shorter, longer);

        List<Double> scores = new List<Double>();

        for (MatchingBlock mb : matchingBlocks) {

            Integer dist = mb.dpos - mb.spos;

            Integer long_start = dist > 0 ? dist : 0;
            Integer long_end = long_start + shorter.length();

            if(long_end > longer.length()) long_end = longer.length();

            String long_substr = longer.substring(long_start, long_end);

            double ratio = getRatio(shorter, long_substr);

            if (ratio > .995) {
                return 100;
            } else {
                scores.add(ratio);
            }

        }
		scores.sort();
        return (Integer) Math.round(100 * scores[scores.size()-1]);

    }
}
