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};

    }

}