1// Copyright (C) 2023 The Android Open Source Project 2// 3// Licensed under the Apache License, Version 2.0 (the "License"); 4// you may not use this file except in compliance with the License. 5// You may obtain a copy of the License at 6// 7// http://www.apache.org/licenses/LICENSE-2.0 8// 9// Unless required by applicable law or agreed to in writing, software 10// distributed under the License is distributed on an "AS IS" BASIS, 11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12// See the License for the specific language governing permissions and 13// limitations under the License. 14 15export interface FuzzySegment { 16 matching: boolean; 17 value: string; 18} 19 20export interface FuzzyResult<T> { 21 item: T; 22 segments: FuzzySegment[]; 23} 24 25export type KeyLookup<T> = (x: T) => string; 26 27// Finds approx matching in arbitrary lists of items. 28export class FuzzyFinder<T> { 29 private items: T[]; 30 private keyLookup: KeyLookup<T>; 31 32 // Because we operate on arbitrary lists, a key lookup function is required to 33 // so we know which part of the list is to be be searched. It should return 34 // the relevant search string for each item. 35 constructor(items: ArrayLike<T>, keyLookup: KeyLookup<T>) { 36 this.items = Array.from(items); 37 this.keyLookup = keyLookup; 38 } 39 40 // Return a list of all items that match the serch term. 41 find(searchTerm: string): FuzzyResult<T>[] { 42 const result: FuzzyResult<T>[] = []; 43 const indicies: number[] = new Array(searchTerm.length); 44 45 for (const item of this.items) { 46 const key = this.keyLookup(item); 47 if (match(searchTerm, key, indicies)) { 48 const segments = indiciesToSegments(indicies, key); 49 result.push({item, segments}); 50 } 51 } 52 53 return result; 54 } 55} 56 57// Given a list of indicies of matching chars, and the original value, produce 58// a list of match/nomatch segments. 59function indiciesToSegments(indicies: number[], text: string): FuzzySegment[] { 60 const segments: FuzzySegment[] = []; 61 let nextIndex = 0; 62 let match = ''; 63 for (const i of indicies) { 64 if (nextIndex < i) { 65 // If we had a match segment from before, add it now. 66 if (match !== '') { 67 segments.push({matching: true, value: match}); 68 match = ''; 69 } 70 // Missed some indicies - wrap them up into a nomatch segment. 71 segments.push({matching: false, value: text.slice(nextIndex, i)}); 72 } 73 74 // Append this matching char to the previous match. 75 match += text[i]; 76 nextIndex = i + 1; 77 } 78 79 // Add any lingering match segment. 80 if (match !== '') { 81 segments.push({matching: true, value: match}); 82 } 83 84 // Add final nomatch segment if there is anything left. 85 if (nextIndex < text.length) { 86 segments.push({matching: false, value: text.slice(nextIndex)}); 87 } 88 89 return segments; 90} 91 92// Evaluate whether |searchTerm| is found in |text|. 93// |indicies| is an array of numbers the same length as |searchTerm|, into which 94// we place the indicies of the matching chars in |text|. 95function match(searchTerm: string, text: string, indicies: number[]): boolean { 96 let j = 0; // index into the searchTerm. 97 let success: boolean = true; 98 99 // For each char of the searchTerm... 100 for (let i = 0; i < searchTerm.length; ++i) { 101 const char = searchTerm[i].toLowerCase(); 102 // ...advance the text index until we find the char. 103 for (; j < text.length; ++j) { 104 // If we find it add it to the segment and move on. 105 if (text[j].toLowerCase() === char) { 106 indicies[i] = j; 107 break; 108 } 109 } 110 111 // Failed to find searchTerm[i] in text: give up. 112 if (j === text.length) { 113 success = false; 114 break; 115 } 116 117 ++j; 118 } 119 120 return success; 121} 122