fuzzy.ts

export default class Fuzzy {
    readonly score: number;
    readonly ranges: Range[];

    constructor(score: number, ranges: Range[]) {
        this.score = score;
        this.ranges = ranges;
    }

    static analyze(term: string, query: string): Fuzzy {
        if (!term || !query)
            return new Fuzzy(0, []);

        let map = Array.from(Array(term.length), () => new Array(query.length));
        let max: Node | null = null;

        for (let qi = query.length - 1; qi >= 0; qi--)
        for (let ti = term.length - 1; ti >= 0; ti--) {
            let t = term[ti];
            let q = query[qi];
            let weight: number;

            if (q === t) {
                weight = 4;
            } else if (q.localeCompare(t, undefined, { sensitivity: 'base' }) === 0) {
                weight = 3;
            } else {
                continue;
            }

            if (query.length == 1) {
                weight += 2;
            }

            let next: Node | null = null;
            let currentScore = weight;

            for (let y = qi + 1; y < query.length; y++) {
                for (let x = ti + 1; x < term.length; x++) {
                    let child = map[x][y];

                    if (!child) {
                        continue;
                    }

                    let childScore = child.score + (ti + 1 == x ? 1 : 0);

                    if (!next || childScore > next.score) {
                        next = child;
                    }
                }

                if (next) {
                    currentScore += next.score;

                    if (next.next && ti + 2 == next.next.x) {
                        currentScore += 2;
                    } else if (ti + 1 == next.x) {
                        currentScore += 4;
                    }

                    break;
                }
            }

            map[ti][qi] = new Node(ti, currentScore, next);

            if (max == null || max.score <= currentScore) {
                max = map[ti][qi];
            }
        }

        if (!max) {
            return new Fuzzy(0, []);
        }

        let node = max.next;
        let prevNode = max;
        let startX = max.x;
        let ranges: Range[] = [];

        while (node) {
            if (prevNode.x < node.x - 1) {
                ranges.push(new Range(startX, prevNode.x + 1));
                startX = node.x;
            }

            prevNode = node;
            node = node.next;
        }

        if (startX <= prevNode.x) {
            ranges.push(new Range(startX, prevNode.x + 1));
        }

        return new Fuzzy(max.score / (query.length * 6.0), ranges);
    }
}

class Range {
    readonly start: number;
    readonly end: number;

    constructor(start: number, end: number) {
        this.start = start;
        this.end = end;
    }
}

class Node {
    readonly x: number;
    readonly score: number;
    readonly next: Node | null;

    constructor(x: number, score: number, next: Node | null) {
        this.x = x;
        this.score = score;
        this.next = next;
    }
}