xonecas.io
5119
Lh

lazy-history / files

lazy-history / internal / search / search.go

1.8 KB
1package search
2
3import (
4	"sort"
5	"strings"
6
7	"github.com/samber/lo"
8)
9
10type SearchResult struct {
11	Value    string
12	Distance int
13}
14
15func Search(slice []string, substring string) []string {
16	results := search(slice, substring)
17
18	return lo.Map(results, func(result SearchResult, _ int) string {
19		return result.Value
20	})
21}
22
23// Search a slice of strings for a substring and sort by levenshtein distance.
24func search(slice []string, substring string) []SearchResult {
25	// search for the substring in the slice
26	matches := lo.Filter(slice, func(item string, _ int) bool {
27		return strings.Contains(item, substring)
28	})
29
30	results := lo.Reduce(matches, func(agg []SearchResult, item string, index int) []SearchResult {
31		// Skip lines that already exist in the results
32		contains := lo.ContainsBy(agg, func(result SearchResult) bool {
33			return result.Value == item
34		})
35		if contains {
36			return agg
37		}
38		distance := levenshteinDistance(item, substring)
39		agg = append(agg, SearchResult{Value: item, Distance: distance})
40
41		return agg
42	}, []SearchResult{})
43
44	sort.Slice(results, func(i, j int) bool {
45		return results[i].Distance < results[j].Distance
46	})
47
48	return results
49}
50
51func levenshteinDistance(s, t string) int {
52	// Create matrix of size (lenS+1)*(lenT+1)
53	lenS := len(s)
54	lenT := len(t)
55
56	// Initialize the matrix
57	d := make([][]int, lenS+1)
58	for i := range d {
59		d[i] = make([]int, lenT+1)
60		d[i][0] = i // Fill first column
61	}
62	for j := range d[0] {
63		d[0][j] = j // Fill first row
64	}
65
66	// Fill the matrix
67	for i := 1; i <= lenS; i++ {
68		for j := 1; j <= lenT; j++ {
69			cost := 1
70			if s[i-1] == t[j-1] {
71				cost = 0
72			}
73
74			d[i][j] = min(
75				d[i-1][j]+1,      // deletion
76				d[i][j-1]+1,      // insertion
77				d[i-1][j-1]+cost, // substitution
78			)
79		}
80	}
81
82	return d[lenS][lenT]
83}