Subversion Repositories SmartDukaan

package com.smartdukaan.cron.offercircular;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Faithful port of Python's difflib.SequenceMatcher.ratio() (Ratcliff/Obershelp
 * gestalt pattern matching): 2 * matched_characters / total_length.
 *
 * Needed because the product matcher's REVIEW vs CATALOG_GAP decision turns on a
 * 0.75 similarity threshold. Any other similarity measure - Levenshtein, Jaro-Winkler,
 * plain LCS - scores differently and would silently reclassify products, so this has
 * to reproduce difflib rather than merely approximate it.
 *
 * difflib's autojunk heuristic only engages for sequences of length >= 200; product
 * names are far shorter, so junk handling is deliberately omitted.
 */
public final class SequenceRatio {

    private SequenceRatio() { }

    public static double ratio(String a, String b) {
        int total = a.length() + b.length();
        if (total == 0) {
            return 1.0;
        }
        // char -> ascending indices in b, mirroring difflib's b2j index
        Map<Character, List<Integer>> b2j = new HashMap<>();
        for (int j = 0; j < b.length(); j++) {
            b2j.computeIfAbsent(b.charAt(j), k -> new ArrayList<>()).add(j);
        }
        return 2.0 * countMatches(a, b, b2j) / total;
    }

    /** Sum of difflib's matching block sizes, computed iteratively to avoid deep
     *  recursion on long strings. */
    private static int countMatches(String a, String b, Map<Character, List<Integer>> b2j) {
        int matches = 0;
        Deque<int[]> queue = new ArrayDeque<>();
        queue.push(new int[]{0, a.length(), 0, b.length()});
        while (!queue.isEmpty()) {
            int[] range = queue.pop();
            int alo = range[0], ahi = range[1], blo = range[2], bhi = range[3];
            int[] match = findLongestMatch(a, b, b2j, alo, ahi, blo, bhi);
            int i = match[0], j = match[1], size = match[2];
            if (size == 0) {
                continue;
            }
            matches += size;
            if (alo < i && blo < j) {
                queue.push(new int[]{alo, i, blo, j});
            }
            if (i + size < ahi && j + size < bhi) {
                queue.push(new int[]{i + size, ahi, j + size, bhi});
            }
        }
        return matches;
    }

    /** @return {besti, bestj, bestsize} */
    private static int[] findLongestMatch(String a, String b, Map<Character, List<Integer>> b2j,
                                          int alo, int ahi, int blo, int bhi) {
        int besti = alo, bestj = blo, bestsize = 0;
        Map<Integer, Integer> j2len = new HashMap<>();
        for (int i = alo; i < ahi; i++) {
            Map<Integer, Integer> newJ2Len = new HashMap<>();
            List<Integer> indices = b2j.get(a.charAt(i));
            if (indices != null) {
                for (int j : indices) {
                    if (j < blo) {
                        continue;
                    }
                    if (j >= bhi) {
                        break;                     // indices are ascending
                    }
                    int k = j2len.getOrDefault(j - 1, 0) + 1;
                    newJ2Len.put(j, k);
                    if (k > bestsize) {
                        besti = i - k + 1;
                        bestj = j - k + 1;
                        bestsize = k;
                    }
                }
            }
            j2len = newJ2Len;
        }
        // grow the block outward over equal characters, as difflib does when there is
        // no junk to skip
        while (besti > alo && bestj > blo && a.charAt(besti - 1) == b.charAt(bestj - 1)) {
            besti--;
            bestj--;
            bestsize++;
        }
        while (besti + bestsize < ahi && bestj + bestsize < bhi
                && a.charAt(besti + bestsize) == b.charAt(bestj + bestsize)) {
            bestsize++;
        }
        return new int[]{besti, bestj, bestsize};
    }
}